Schauble@mit-multics.arpa (Paul Schauble) (12/23/85)
I suspect that most of the people who have been recently flaming in the right-shift debate don't understand the problem. So...doning asbestos suit... The shift instruction that is normally taken as equivalent to divide is right shift with sign extension. That is, the sign bit fills in the bits vacated by the shift. Assuming a 16 bit binary machine and starting with -15(decimal) or FFF1(hex) and repeatedly shifting right 1 bit gives: Shifts Hex Decimal ----------------------------------- 0 FFF1 -15 1 FFF8 -8 2 FFFC -4 3 FFFE -2 4 FFFF -1 5 FFFF -1 >5 FFFF -1 Starting with -16 and dividing by 2, using the standard divide, gives Divides Decimal ----------------------------------- 0 -15 1 -7 2 -3 3 -1 4 0 >4 0 Anyone still think they're the same thing? This optimization only works if the numbers are known to be non-negative. A Pascal compiler may make this optimization, becausethe programmer may specify the range for variables, but not C. BTW, is >> defined to be a sign-extended shift or a zero extended shift and under what circumstances. Paul Schauble @ MIT-Multics
ark@alice.UucP (Andrew Koenig) (12/23/85)
> Anyone still think they're the same thing? This optimization only works > if the numbers are known to be non-negative. A Pascal compiler may make > this optimization, becausethe programmer may specify the range for > variables, but not C. Moral: a C compiler can substitute a right shift for a divide by a constant power of two if and only if the LHS of the expression is an unsigned integer type. By the way, a right shift of a signed quanitity is not required to be an arithmetic shift.
bzs@bu-cs.UUCP (Barry Shein) (12/24/85)
>BTW, is >> defined to be a sign-extended shift or a zero extended shift >and under what circumstances. > > Paul > Schauble @ MIT-Multics It should be controlled by the types of the things being shifted, not the operator: int foo, bar ; unsigned int thing, stuff ; foo = foo >> bar ; thing = thing >> stuff ; Expect the former to generate signed shift and the latter to generate an unsigned, casts are often useful to accomplish this. -Barry Shein, Boston University
jj@nrcvax.UUCP (Utah) (12/24/85)
In article <974@brl-tgr.ARPA> Schauble@mit-multics.arpa (Paul Schauble) writes: > >BTW, is >> defined to be a sign-extended shift or a zero extended shift >and under what circumstances. > > Paul > Schauble @ MIT-Multics The way that I interpreted this when generating machine code (68000) for a >> X was that if a was 'signed' (char, short, int, and long in our implementation) the compiler generated an arithmetic shift. If a was 'unsigned' (unsigned char, unsigned short, unsigned int, unsigned long), it generated a bitwise (logical?) shift. BTW, most C compilers I have seen do not fold the following constant expression correctly: ((unsigned long)0xFFFFFFFF) >> 1 /* or anything w/sign bit on */ Seems like the constant folding function in the compiler only does arithmetic shifts. ------------------------------------------------------------------------- Jeff Jennings Network Research Corp. ihnp4!nrcvax!nrcutah!jj 923 Executive Park Drive Suite C ucbvax!calma!nrcvax!nrcutah!jj Salt Lake City, Utah 84117, U.S.A. {sdcsvax,hplabs}!sdcrdcf!psivax!nrcvax!nrcutah!jj (801) 266-9194
steve@jplgodo.UUCP (Steve Schlaifer x3171 156/224) (12/24/85)
> I suspect that most of the people who have been recently flaming in > the right-shift debate don't understand the problem. So...doning > asbestos suit... > > The shift instruction that is normally taken as equivalent to divide is > right shift with sign extension. That is, the sign bit fills in the bits > vacated by the shift. Assuming a 16 bit binary machine and starting with > -15(decimal) or FFF1(hex) and repeatedly shifting right 1 bit gives: > And assuming 2's complement arithmetic... > Shifts Hex Decimal > ----------------------------------- > 0 FFF1 -15 > 1 FFF8 -8 > 2 FFFC -4 > 3 FFFE -2 > 4 FFFF -1 > 5 FFFF -1 > >5 FFFF -1 > > Starting with -16 and dividing by 2, using the standard divide, gives > > Divides Decimal > ----------------------------------- > 0 -15 > 1 -7 > 2 -3 > 3 -1 > 4 0 > >4 0 > > Anyone still think they're the same thing? This optimization only works > if the numbers are known to be non-negative. A Pascal compiler may make > this optimization, becausethe programmer may specify the range for > variables, but not C. > NB: On 1's complement machines like the Univac (Sperry) 1100 mainframes, the sign extended right shift works just like a divide by 2. > Shifts Hex Decimal ----------------------------------- 0 FFF0 -15 1 FFF8 -7 2 FFFC -3 3 FFFE -1 4 FFFF -0 5 FFFF -0 >5 FFFF -0 Steve Schlaifer (jplgodo!steve)
kanner@tymix.UUCP (Herb Kanner) (12/26/85)
In article <974@brl-tgr.ARPA> Schauble@mit-multics.arpa (Paul Schauble) writes: >BTW, is >> defined to be a sign-extended shift or a zero extended shift >and under what circumstances. > I'm doing this at home from memory, without a copy of K & R at hand, so, please, no flames if I get it slightly wrong. My recollection of their definition of >> is that if the shifted variable is of type unsigned, it must be a zero-extended shift. If the shifted variable is of type int, it may be sign extended if the underlying hardware possesses such an instruction--I think this is a relatively non-commital way of saying that it will probably be implemented as a sign-extended shift on machines using two-complement notation for negative numbers. -- Herb Kanner Tymnet, Inc. ...!hplabs!oliveb!tymix!kanner
gnu@l5.uucp (John Gilmore) (12/27/85)
You can compile divides to right-shifts without *too* much effort...
The Sun Unix "3.0 Pilot" compiler compiles this:
int i = -15;
int j;
main() {
j = i / 4;
}
----into----
_main:
link a6,#0
movl _i,d0
jge L2000000
addql #3,d0
L2000000:
asrl #2,d0
movl d0,_j
unlk a6
rts
---- Still a lot faster than a divide!franka@mmintl.UUCP (Frank Adams) (12/27/85)
In article <974@brl-tgr.ARPA> Schauble@mit-multics.arpa (Paul Schauble) writes: >This optimization only works >if the numbers are known to be non-negative. A Pascal compiler may make >this optimization, becausethe programmer may specify the range for >variables, but not C. And you were doing so well up to this point! :-) Of course a C compiler can make this optimization, because the variables may be declared unsigned. By the way, the FORTRAN compiler for the DEC-10 would process an integer divide by two by checking the sign, incrementing if negative, and then doing a right shift. Since the divide took special setup (the single vs double length operands problem), this didn't necessarily even take more space than a divide instruction. Frank Adams ihpn4!philabs!pwa-b!mmintl!franka Multimate International 52 Oakland Ave North E. Hartford, CT 06108
emjej@uokvax.UUCP (12/29/85)
And still wrong, because after all the significant bits go away, you get -1 instead of 0, which you should get. I guess some things have to be rediscovered occasionally. James Jones Anybody's compiler have sufficient smarts to puzzle out control flow and turn the example given into an assignment of -3 (or is that -4? not many computers do integer division the way we learned it back in foundations or ring theory!) to the variable?
johnl@ima.UUCP (01/02/86)
Now that we know that right shifting is not the same as division, has anybody ever come up with a plausible reason for computers to have arithmetic shift instructions on twos complement machines (other than that they're easy to implement and poorly educated engineers might have thought they were the same as division)? For positive numbers, they give the same result as unsigned shifts, and for negative numbers they give the wrong answer. Followups to net.arch, please. John Levine, ima!johnl
golde@uw-beaver (Helmut Golde) (01/03/86)
Microsoft C for 8086/8088 seems to successfully optimizes integer divides into right shift, when optimizing for reduced execution speed. Here's is the actual code produced (with comment for those unfamiliar with the 8086). Y = X / 2 ------> mov ax,X ;mov variable X into register ax cwd ;convert AX to double word, high part in DX sub ax, dx ;ax -= dx sar ax,1 ;shift arithmetic right ax 1 bit mov Y,ax ;move ax to variable Y So far so good. It seems to work. But get how it compiles larger divisions! Y = X / 8 (or any other power of 2) ------------> mov ax, X ;register ax = variable X cwd ;word to double word, high part in dx xor ax,dx ;ax = ax xor dx sub ax,dx ;ax -= dx mov cx,3 ;cx = 3 (or whatever the shift count should be) sar ax,cx ;shift ax arithmetic right cx bits xor ax,dx ;ax = ax xor dx sub ax,dx ;ax -= dx mov Y,ax ;variable Y = ax It even seems to work, and I guess it is faster than an integer divide. Amazing, though. --Peter Golde
tombre@crin.UUCP (Karl Tombre) (01/06/86)
In article <124000005@ima.UUCP> johnl@ima.UUCP writes: > >Now that we know that right shifting is not the same as division, has >anybody ever come up with a plausible reason for computers to have >arithmetic shift instructions on twos complement machines (other than that >they're easy to implement and poorly educated engineers might have thought >they were the same as division)? You can use shift instructions for other things than divisions: In some binary image processing programs (for example thinning), you have to scan an image (considered as a 2D matrix of bits) in order to find particular 3x3 window patterns where you can change the central pixel. A fast way for doing this is the use of a look-up table and of coding in one word of the neighborhood. Here is the considered neighborhood: 1 4 7 ___________________ 2 5 8 which is coded as follows |1|2|3|4|5|6|7|8|9| 3 6 9 ------------------- Well, there are 512 possible configurations, I thus can use a look-up table of 512 entries, where I put a 1 (true) for each interesting configuration. Now, to scan one line of the image, you use shift instructions the following way: typedef PIXEL /*whatever you use to code pixels*/ PIXEL *pl, /*pointer in preceding line*/ *cl, /* current line*/ *fl; /* following line*/ int window; /*where I code the window configuration*/ /* skip most of the function... I just want to show how you go from one point to the next*/ /* window codes one window configuration. When I go to the next point on the current line, I do the following : */ window = ( window << 1) | (*pl & 01); /*preceding line*/ window = ( window << 1) | (*cl & 01); /*current line*/ window = ( window << 1) | (*fl & 01); /*following line*/ window &= 0x1ff; /*to keep only the 9 lowest bits*/ This is just a little example of the usefulness of shift instructions. If they didn't exist, it wouldn't run quite as fast on the machine. > Followups to net.arch, please. > >John Levine, ima!johnl Well, I think this was more a C answer than an architecture answer. I only wanted to show that I find shifts quite useful. But perhaps you were thinking of something else... -- --- Karl Tombre @ CRIN (Centre de Recherche en Informatique de Nancy) UUCP: ...!vmucnam!crin!tombre or ...!inria!crin!tombre COSAC: crin/tombre POST: Karl Tombre, CRIN, B.P. 239, 54506 VANDOEUVRE CEDEX, France Les plus desesperes sont les chants les plus beaux, Et j'en sais d'immortels qui sont de purs sanglots. Alfred de Musset.
mcelroy.wbst@xerox.arpa (nanc) (01/10/86)
Liz, Thank you for thinking of me but, I won't be able to attend the party. ~ nanc
rwl@uvacs.UUCP (01/15/86)
> > Liz, > Thank you for thinking of me but, I won't be able to attend > the party. > > > ~ nanc Hey, Liz, listen -- if the party's anywhere near DC, I think I'll be able to make it instead. I'm in the book. -- Ray Lubinsky University of Virginia, Dept. of Computer Science uucp: decvax!mcnc!ncsu!uvacs!rwl