guy@gorodish.Sun.COM (Guy Harris) (07/19/88)
> I would certainly think so. The action of a shift on an unsigned is > pretty well defined, Yes, but the action of a shift *whose magnitude is equal to the number of bits in the operand* is not well defined by either K&R or by the January 11, 1988 ANSI C draft. K&R: 7.5 Shift operators ... The result is undefined if the right operand is negative, or greater than or equal to the length of the object in bits. ANSI C: 3.3.7 Bitwise shift operators ...If the value of the right operand is negative or is greater than or equal to the width in bits of the promoted left operand, the behavior is undefined. > x>>32 should work the same on any machine, 8, 16, 32, or 64 bits. Also, the > action of doing: > x >>= 16; x>>= 16; > better be the same as: > x = x>>32; Perhaps they *should*; however, neither the K&R nor the January 11 ANSI C draft specifications for the language require this. If you think that they should, I suggest you lobby the ANSI C committee.
rbutterworth@watmath.waterloo.edu (Ray Butterworth) (07/19/88)
In article <60290@sun.uucp>, guy@gorodish.Sun.COM (Guy Harris) writes: > > action of doing: > > x >>= 16; x>>= 16; > > better be the same as: > > x = x>>32; > > Perhaps they *should*; however, neither the K&R nor the January 11 ANSI C draft > specifications for the language require this. If you think that they should, I > suggest you lobby the ANSI C committee. I can see why the Committee should NOT require that (for n>0) "x >>= n;" be the same as "while (n--!=0) x>>=1;". Imagine a machine with 16 bit words and a logical right shift instruction that only looks at the lowest 4 bits of the shift size. "x >>= n;" could simply grab the 4 lower bits of "n" to determine the size of the shift. But if the Standard required the requested behaviour, the compiler would have to generate a lot of extra code for every shift to change it to a store-zero whenever "n" is greater than 15. e.g. LOAD n Put the shift size into the register. CMPI #15 Is it bigger than 15? TLTZ +3 LRS x No, shift x right by lower 4 bits of the register TRA +2 STZ x Yes, so store zero instead of simply LOAD n LRS x Shift x right by lower 4 bits of n No, I don't know of any such machine. Yes, I know it would be more efficient to change positions of the shift and store-zero cases.
hunt@spar.SPAR.SLB.COM (Neil Hunt) (07/20/88)
In article <60290@sun.uucp> guy@gorodish.Sun.COM (Guy Harris) writes: > 7.5 Shift operators > ... > The result is undefined if the right operand is negative, or greater > than or equal to the length of the object in bits. >ANSI C: > 3.3.7 Bitwise shift operators > ...If the value of the right operand is negative or is greater than or > equal to the width in bits of the promoted left operand, the behavior > is undefined. This has been a pet peeve of mine for a long time: does the following function work for applying a shift (left or right) to all pixels in a large image ? shift_pixel(image, count) struct image *image; int count; { int i, j; for(j = 0; j < image->rows; j++) for(i = 0; i < image->cols; i++) image->pixels[i][j] >>= count; } No, it doesn't; the last line has to be: if(count > 0) image->pixels[i][j] >>= count; else image->pixels[i][j] <<= -count; because of the stupid undefined rule about shifts. An alternative solution is rshift = count > 0 ? count : 0; lshift = count < 0 ? -count : 0; for(j = 0; j < image->rows; j++) for(i = 0; i < image->cols; i++) image->pixels[i][j] = ((image->pixels[i][j] >> rshift) << lshift); We are talking factors of two in execution time for these functions. What a pain !! Neil/. -- hunt@spar.slb.com ...{amdahl|decwrl|hplabs}!spar!hunt
arya@hawk.ulowell.edu (Arun Arya) (07/20/88)
In article <1818@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: >This has been a pet peeve of mine for a long time: does the following function >work for applying a shift (left or right) to all pixels in a large image ? > >shift_pixel(image, count) struct image *image; int count; >{ > int i, j; > > for(j = 0; j < image->rows; j++) > for(i = 0; i < image->cols; i++) > ... > if(count > 0) > image->pixels[i][j] >>= count; > else > image->pixels[i][j] <<= -count; > >because of the stupid undefined rule about shifts. > >An alternative solution is > ... What about a simple shift_pixel(image, count) struct image *image; int count; { int i, j; if(count > 0) shift_right(image,count); else if(count < 0) shift_left (image,-count); } where the two shift routines are identical but for the fact one has a <<, other a >>. It is often the case that attempts to merge code leads to slow code. The fact that separate left and right shifts exist is useful in that better code can be generated on machines that do them differently - signed left shift coincides with unsigned left shift, but not right shifts. >What a pain !! Hardly! But for a decent preprocessor, the effort would be even smaller. C is ugly, but for far more important reasons! Now if your count were a two dimensional array ..., but such a case in practice would be surprising to me.
levy@ttrdc.UUCP (Daniel R. Levy) (07/20/88)
In article <1818@spar.SPAR.SLB.COM>, hunt@spar.SPAR.SLB.COM (Neil Hunt) writes: # This has been a pet peeve of mine for a long time: does the following function # work for applying a shift (left or right) to all pixels in a large image ? # # shift_pixel(image, count) # struct image *image; # int count; # { # int i, j; # # for(j = 0; j < image->rows; j++) # for(i = 0; i < image->cols; i++) # image->pixels[i][j] >>= count; # } # # No, it doesn't; the last line has to be: # # if(count > 0) # image->pixels[i][j] >>= count; # else # image->pixels[i][j] <<= -count; # # because of the stupid undefined rule about shifts. # # An alternative solution is # # rshift = count > 0 ? count : 0; # lshift = count < 0 ? -count : 0; # # for(j = 0; j < image->rows; j++) # for(i = 0; i < image->cols; i++) # image->pixels[i][j] = # ((image->pixels[i][j] >> rshift) << lshift); # # We are talking factors of two in execution time for these functions. # What a pain !! To be perfectly honest, please note that the factor of two can be in code size rather than execution time. (See below.) My guess, having studied a few machine architectures, is that C is bringing you close to the hardware on this issue. Some machines don't implement "negative shift." If C were required to support a "negative shift" the compiler would have to work around the problem anyway on computers that don't implement such a shift, and a programmer usually has a better idea of what kind of tradeoff (code space versus execution time) to make in the workaround than the compiler does. register int r,c,i,j; register PIXEL **p; if (count == 0) return; c = image->cols; r = image->rows; p = image->pixels; if (count > 0) { for (j=0; j<r; j++) for (i=0; i<c; i++) p[i][j] >>= count; } else if (count < 0) { count = -count; for (j=0; j<r; j++) for (i=0; i<c; i++) p[i][j] <<= count; } -- |------------Dan Levy------------| THE OPINIONS EXPRESSED HEREIN ARE MINE ONLY | AT&T Data Systems Group | AND ARE NOT TO BE IMPUTED TO AT&T. | Skokie, Illinois | |-----Path: att!ttbcad!levy-----|
ok@quintus.uucp (Richard A. O'Keefe) (07/20/88)
In article <1818@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: >shift_pixel(image, count) > struct image *image; > int count; > { > int i, j; > > for(j = 0; j < image->rows; j++) > for(i = 0; i < image->cols; i++) > image->pixels[i][j] >>= count; > } >... the last line has to be: > > if(count > 0) > image->pixels[i][j] >>= count; > else > image->pixels[i][j] <<= -count; > It is better to move the "if" outside the loop. C arrays using the Algol convention rather than the Fortran one, it may be better to vary j faster than i (and it might be faster still to use pointers). void shift_pixel(image, count) struct image *image; int count; { int i, j; if (count > 0) { for (i = image->cols; --i >= 0; ) for (j = image->rows; --j >= 0; ) image->pixels[i][j] >>= count; } else if (count < 0) { count = -count; for (i = image->cols; --i >= 0; ) for (j = image->rows; --j >= 0; ) image->pixels[i][j] <<= count; } } The bottom line is that because the C standard specifies that shifting is undefined for negative or overlarge shift counts, it can generate **faster** code for (this version of) the operation you want than it could if shifting were more tightly specified. Since several machines take the bottom N bits of the shift count and assume it is negative, if you didn't write the if somewhere, the compiler would have to, and putting that if (count > 0) shift right; else shift left; in the inner loop would really hurt pipelined and vectored machines. (Unless the compiler was smart enough to move the test outside the loop, of course.)
cik@l.cc.purdue.edu (Herman Rubin) (07/20/88)
In article <2813@ttrdc.UUCP>, levy@ttrdc.UUCP (Daniel R. Levy) writes: > In article <1818@spar.SPAR.SLB.COM>, hunt@spar.SPAR.SLB.COM (Neil Hunt) writes: > # This has been a pet peeve of mine for a long time: does the following function > # work for applying a shift (left or right) to all pixels in a large image ? > # > # shift_pixel(image, count) > # struct image *image; > # int count; > # { > # int i, j; > # > # for(j = 0; j < image->rows; j++) > # for(i = 0; i < image->cols; i++) > # image->pixels[i][j] >>= count; > # } > # > # No, it doesn't; the last line has to be: > # > # if(count > 0) > # image->pixels[i][j] >>= count; > # else > # image->pixels[i][j] <<= -count; > # > # because of the stupid undefined rule about shifts. The articles go on about alternatives. HOWEVER: This merely points out the problems. One can give a restrictive rule about shifts, which will handle some of the questions. The alternative is to allow the programmer to specify what is wanted if the shift is not of the trivial types envisaged by K&R. Do I want to allow a shift by a negative quantity to be blocked or interpreted as a shift in the opposite direction? What does the hardware do about shifts of excessive amounts? What does it do if the shift amount is negative? I have certain procedures which use variable size right shifts. Now some of the computers I use only have left shifts--right shifts are negative left shifts. On those computers, I would produce the negatives of the shift amounts _initially_. On the computers which have separate right shift instructions and do not allow negative shifts, I would naturally do the other. The implementation of procedures needing shifts being different at different times, it is clear that either the compiler must be able to receive and handle all of the questions above, and all of the questions raised by the others who have posted about shifts, or that the programmer must be able to make these decisions, including which unsafe optimizations can be used, or some combination of the above. I know of no compilers which can even receive the information. Of course, one could put enough restrictions on the implementation of shift to avoid most of the problems. If one is not careful, the execution speed of a program can be reduced by a huge factor, and an algorithm which is efficient on one machine can crawl on another. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (07/20/88)
In article <1818@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: | In article <60290@sun.uucp> guy@gorodish.Sun.COM (Guy Harris) writes: | >ANSI C: | > 3.3.7 Bitwise shift operators | > ...If the value of the right operand is negative or is greater than or | > equal to the width in bits of the promoted left operand, the behavior | > is undefined. | So you have to build in an explicit check in every program, comparing the shift with the size of the item. On the other hand it sure makes the compilers look better, since no error checking means faster benchmarks to advertize. If I sound really disgusted about this, I am. Compilers on brain damaged hardware should work correctly. -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
alanf%smile@Sun.COM (Alan Fargusson) (07/21/88)
In article <1818@spar.SPAR.SLB.COM>, hunt@spar.SPAR.SLB.COM (Neil Hunt) writes: > rshift = count > 0 ? count : 0; > lshift = count < 0 ? -count : 0; > > for(j = 0; j < image->rows; j++) > for(i = 0; i < image->cols; i++) > image->pixels[i][j] = > ((image->pixels[i][j] >> rshift) << lshift); > > We are talking factors of two in execution time for these functions. > What a pain !! What is your solution? Since most (I think all) hardware does not handle shift count less then zero the compiler would have to generate the same code that it generates for your example above. - - - - - - - - - - - - - - - - - - - - - Alan Fargusson Sun Microsystems alanf@sun.com ..!sun!alanf
guy@gorodish.Sun.COM (Guy Harris) (07/21/88)
> | > 3.3.7 Bitwise shift operators > | > ...If the value of the right operand is negative or is greater than or > | > equal to the width in bits of the promoted left operand, the behavior > | > is undefined. > So you have to build in an explicit check in every program, comparing > the shift with the size of the item. No, you don't. You only have to build in explicit checks where "the value of the right operand" could be "negative or ... greater than or equal to the width in bits of the promoted left operand." For instance, an explict check would be a waste of time in #define NTH_BIT(bitarray, n) (bitarray[(n)/32] & (1 << ((n)%32)) since you already *know* that the RHS of the << is between 0 and 31 (we presume here that "bitarray" is an array of 32-bit integral quantities). Similarly, you don't need it for nblocks = nbytes >> LOG2_BYTESPERBLOCK if LOG2_BYTESPERBLOCK is a manifest constant that you know will be in the right range. I have run into only *one* piece of code where the fact that shifts of an amount greater than the number of bits in the object is undefined caused anything to break. It was a nuisance, but the code in question was commented, and had an #ifdef for one processor with this characteristic; I had to add two more (SPARC and 80386). I can live with that. > If I sound really disgusted about this, I am. Compilers on brain > damaged hardware should work correctly. So if you feel so strongly about it, *lobby the ANSI C people* (as I've already suggested); if you don't get them to change, you're not going to get everybody to change their compilers. (If they say "no", perhaps they have good reasons for saying so, so "I've already tried lobbying them" may not be a valid response.) As for what is or isn't "brain-damaged hardware", I'll let hardware designers speak for whether there's any performance advantage to, say, using the shift count modulo 32 rather than looking at it all. And as for "correctly", this is a matter of opinion; the only thing close to an *objective* definition for "correct" behavior of a C compiler is a C language spec, and neither K&R nor current ANSI C drafts specify what is and what isn't "correct" behavior here.
guy@gorodish.Sun.COM (Guy Harris) (07/21/88)
> Contrary to the other two follow-ups I've seen (when will > people learn not to react without thinking), yes you do have a > valid complaint. The C language (both K+R and X3J11) > guarantees that X >> n is a logical shift, with 0 padding on > the left, when X is an unsigned quantity, as it is in this > case. It is only when X is not unsigned, that a right shift is > implementation dependant. I don't know which follow-ups *you* saw; none of the ones *I* saw said *anything* about smearing the sign bit. All the ones I saw pointed out, quite correctly, that he did *not* have a valid complaint, because the result of shifting a signed *or* unsigned 32-bit quantity right by 32 bits is undefined. It might arguably be more correct to say that complaining that his compiler wasn't "doing the right thing" according to some language specification wasn't valid. He could, I suppose, complain that the language specification should say what happens when you shift by more than the size of the LHS, in bytes, or that the hardware shouldn't take the shift count modulo 32, or that the compiler should "do the right thing" even though it's not required by the language specification; these might or might not be considered valid complaints depending on your point of view.
jfh@rpp386.UUCP (John F. Haugh II) (07/22/88)
In article <11592@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > If I sound really disgusted about this, I am. Compilers on brain >damaged hardware should work correctly. i have to disagree. the only way to inform the compiler that the shift will always be by a positive amount is to cast the shift count to an unsigned and the only way to inform the compiler the value is in range is to have subranges ala pascal. C does not have subranges as pascal has and expecting bounds checking on all shift operations seems to deviate from the standard C idiom of little or no run time checking. C does not check array bounds, even where it is possible, and it should not be forced to check shift counts. - john. -- John F. Haugh II +--------- Cute Chocolate Quote --------- HASA, "S" Division | "USENET should not be confused with UUCP: killer!rpp386!jfh | something that matters, like CHOCOLATE" DOMAIN: jfh@rpp386.uucp | -- with my apologizes
jfh@rpp386.UUCP (John F. Haugh II) (07/22/88)
In article <60670@sun.uucp> alanf%smile@Sun.COM (Alan Fargusson) writes: >In article <1818@spar.SPAR.SLB.COM>, hunt@spar.SPAR.SLB.COM (Neil Hunt) writes: >> We are talking factors of two in execution time for these functions. >> What a pain !! > >What is your solution? the solution which neil missed was to sacrifice code size. he wrote >> rshift = count > 0 ? count : 0; >> lshift = count < 0 ? -count : 0; >> >> for(j = 0; j < image->rows; j++) >> for(i = 0; i < image->cols; i++) >> image->pixels[i][j] = where the test could have been if (count < 0) { count = - count; for ... image->pixels[i][j] = (image->pixels[i][j] >> count); } else { for ... image->pixels[i][j] = (image->pixels[i][j] << count); } this does not suffer a significant decrease in performance, the only added overhead being the initial test and the possible negation. - john. -- John F. Haugh II +--------- Cute Chocolate Quote --------- HASA, "S" Division | "USENET should not be confused with UUCP: killer!rpp386!jfh | something that matters, like CHOCOLATE" DOMAIN: jfh@rpp386.uucp | -- with my apologizes
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (07/25/88)
henry@utzoo.uucp (Henry Spencer) writes: | You have an out-of-date draft, I believe. The second-public-comment draft | (I haven't seen the third yet) explicitly forbids sizeof in this context. I believe what I have is current. I got it a week ago and it's marked as THIRD public review. The many references were all based on that draft. Another note, from the sizeof (3.3.3.4) section, line 23. Constraints =========== The _sizeof_ operator shall not be applied to an expression function type or an incomplete type, to the parenthesized name of such a type, or to an lvalue that designates a bitfield object. Chris Tokek said that there was a obscure phrase which disallowed use of sizeof in the preprocessor, but 3.8.1 on the #if says that the 2nd argument is a constant expression, and 3.4 (constant expressions) says: Constraints =========== Constant expression shall not contain assignment, increment, decrement, function call, or comma operators, except when they when they are contained within the operand of a sizeof operator. This is the only reference to constant expression in the index. If the semantics of the #if say that the first field is a constant expression, and the definition of constant expression specifically includes sizeof, either sizeof is legal in the expression of #if, or perhaps the phrase is a bit too obscure. I didn't think this was legal, but after some time checking the standard I thank that the standard *seems* to say that it is. Since this discussion has gotten split between comp.std.c, comp.lang.c and comp.arch, I have directed followup to comp.std.c, since the question has changed to a standards issue. -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/29/88)
In article <11592@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: >| > ...If the value of the right operand is negative or is greater than or >| > equal to the width in bits of the promoted left operand, the behavior >| > is undefined. > So you have to build in an explicit check in every program, comparing >the shift with the size of the item. No; the vast majority of shifts in C applications do not require the check. However, if the language guaranteed the behavior you want it to, then on many architectures a far larger percentage of shifts would have to perform the check (in the compiler-generated code). This is one of the many cases where C is deliberately permissive in order to allow a better fit to the hardware. It is of course not what an "ideal" programming language would do, where "ideal" includes the notion of suitable hardware.