jim@bnr-rsc.UUCP (Jim Somerville) (07/13/88)
I have a question on how compilers should handle shifting. Consider the following: unsigned int x; /* ints are 32 bits */ unsigned int y; y = x>>32; /* the 32 could also be the value of another variable */ What should be the value of y after the shifting is complete? a) x b) 0 c) none of the above Do I have a valid complaint if the compiler I am using gives x? -- Jim Somerville (bnr-vpa!bnr-rsc!jim) Phone: (613) 763-4497 Bell-Northern Research Usenet:utgpu!bnr-vpa!bnr-rsc!jim P.O. Box 3511, Station C, Ottawa, Ontario, Canada, K1Y 4H7
mahar@weitek.UUCP (Mike Mahar) (07/16/88)
The question (x>>32) has come up. K&R and ANSI-C say the result is undefined.
The 68000 shift instruction will give you a 0.
The 80286 shift instruction will give you a 0.
The 80386 shift instruction will give you x.
The Weitek XL shift instruction will give you x.
I don't know what MIPS Co. 88000 or 29000 return but I suspect the C compiler
does what the instruction does.
The result stems from whether the machine truncates the shift amount to 5 bits
before doing the shift. It is easy to see why the C standards punt on the
issue.
--
Mike Mahar
UUCP: {turtlevax, cae780}!weitek!maharalanf%smile@Sun.COM (Alan Fargusson) (07/16/88)
In article <705@bnr-rsc.UUCP>, jim@bnr-rsc.UUCP (Jim Somerville) writes: > I have a question on how compilers should handle shifting. > What should be the value of y after the shifting is complete? > a) x > b) 0 > c) none of the above D: All of the above. It is implemetation dependent. > Do I have a valid complaint if the compiler I am using gives x? No. Since different hardware will implements the shift in different ways it would be rather difficult to define this. - - - - - - - - - - - - - - - - - - - - - Alan Fargusson Sun Microsystems alanf@sun.com ..!sun!alanf
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (07/18/88)
In article <705@bnr-rsc.UUCP> jim@bnr-rsc.UUCP (Jim Somerville) writes: | What should be the value of y after the shifting is complete? | a) x | b) 0 | c) none of the above | | Do I have a valid complaint if the compiler I am using gives x? I would certainly think so. The action of a shift on an unsigned is pretty well defined, and the compiler you mention is not doing it. 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; If your compiler isn't correcting for hardware characteristics I say it's broken. The idea of a C standard is that you don't have to build in a bunch of hardware checks at the source level. People will try to tell you that's the way the hardware shift works... there is no justification for that, you are talking about the C source, and it should work correctly. What is needed is compiler code to check for a constant shift of 31+ and load zero (no runtime penalty) and generated code for variable shifts which does (pseudocode): cmp shftreg,32 jnc lbl1 mov datareg,0 jmp lbl2 lbl1: shiftr datareg,shftreg lbl2: Of course the logic could be improved in a machine dependent way... in my opinion reliable operation is more important than speed. I have no objection to a compiler switch which allows "unsafe optimization," and use that feature in some places myself. "it doesn't matter how fast you get the wrong answer" -me -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
rogerk@mips.COM (Roger B.A. Klorese) (07/19/88)
In article <392@attila.weitek.UUCP> mahar@attila.UUCP (Mike Mahar) writes: >The question (x>>32) has come up. K&R and ANSI-C say the result is undefined. >I don't know what MIPS Co. 88000 or 29000 return but I suspect the C compiler >does what the instruction does. The M/1000 (MIPS R2000-based) gives x. -- Roger B.A. Klorese MIPS Computer Systems, Inc. {ames,decwrl,prls,pyramid}!mips!rogerk 25 Burlington Mall Rd, Suite 300 rogerk@mips.COM Burlington, MA 01803 I don't think we're in toto any more, Kansas... +1 617 270-0613
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.
baum@Apple.COM (Allen J. Baum) (07/19/88)
[] >In article <60137@sun.uucp> alanf%smile@Sun.COM (Alan Fargusson) writes: >In article <705@bnr-rsc.UUCP>, jim@bnr-rsc.UUCP (Jim Somerville) writes: >> I have a question on how compilers should handle shifting. > >> What should be the value of y after the shifting is complete? >> a) x >> b) 0 >> c) none of the above > >D: All of the above. It is implemetation dependent. > >> Do I have a valid complaint if the compiler I am using gives x? > >No. Since different hardware will implements the shift in different ways it >would be rather difficult to define this. Our Cray will give x!=0, since an int is 64 bits.... -- {decwrl,hplabs,ihnp4}!nsc!apple!baum (408)973-3385
earl@mips.COM (Earl Killian) (07/19/88)
In article <11556@steinmetz.ge.com> davidsen@steinmetz.ge.com (William E. Davidsen Jr) writes:
From: davidsen@steinmetz.ge.com (William E. Davidsen Jr)
Date: 18 Jul 88 15:19:38 GMT
I would certainly think so. The action of a shift on an unsigned is
pretty well defined, and the compiler you mention is not doing it. 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;
By extension
x >>= 16; x >>= 16; x >>= 16; x >>= 16;
x >>= 16; x >>= 16; x >>= 16; x >>= 16;
x >>= 16; x >>= 16; x >>= 16; x >>= 16;
x >>= 16; x >>= 16; x >>= 16; x >>= 16;
should give the same answer as
x >>= 256;
but I doubt very many C implementations do this. Most architectures
look at 5, 6, 7, or 8 bits of the shift count. It always seemed
inconsistent to me to look are more than 5 (i.e. log2(bitsperword))
without looking at all of them.
--
UUCP: {ames,decwrl,prls,pyramid}!mips!earl
USPS: MIPS Computer Systems, 930 Arques Ave, Sunnyvale CA, 94086rick@pcrat.UUCP (Rick Richardson) (07/19/88)
In article <392@attila.weitek.UUCP> mahar@attila.UUCP (Mike Mahar) writes: >The question (x>>32) has come up. K&R and ANSI-C say the result is undefined. >The 68000 shift instruction will give you a 0. >The 80286 shift instruction will give you a 0. This depends upon your 80286 compiler, whether x is an int or a long, and whether you try shift 16 or 32 bits. The AT&T 80286 compiler (GET THIS!) actually detects: some_long >> 32 some_int >> 32 and explicity generates code to give the result as "some_long" or "some_int"! At first, I thought this implementation choice was for consistency with the case where the shift count is a variable. But alas, if x is "32": some_long >> x gives result "0" some_int >> x gives result "some_int" So this compiler isn't even consistent in its treatment of this problem. -- Rick Richardson, PC Research, Inc. (201) 542-3734 (voice, nights) OR (201) 389-8963 (voice, days) uunet!pcrat!rick (UUCP) rick%pcrat.uucp@uunet.uu.net (INTERNET)
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (07/19/88)
In article <2620@wright.mips.COM> earl@mips.COM (Earl Killian) writes: | In article <11556@steinmetz.ge.com> davidsen@steinmetz.ge.com (William E. Davidsen Jr) writes: | | ... stuff I wrote ... | By extension | x >>= 16; x >>= 16; x >>= 16; x >>= 16; | x >>= 16; x >>= 16; x >>= 16; x >>= 16; | x >>= 16; x >>= 16; x >>= 16; x >>= 16; | x >>= 16; x >>= 16; x >>= 16; x >>= 16; | should give the same answer as | x >>= 256; | but I doubt very many C implementations do this. Most architectures | look at 5, 6, 7, or 8 bits of the shift count. It always seemed | inconsistent to me to look are more than 5 (i.e. log2(bitsperword)) | without looking at all of them. I consider this to be a major botch in an implementation, *particularly* on fixed shifts where the problem can be detected at compile time. There is *no* portable way to put in a check for shift out of range, unless you check the range at runtime, which is possible but messy. Guess it's a quality of implementation issue. I'm actually trying to see what various C compilers do with this. Perhpas the only portable way to do it is with a loop, one bit at a time. I think you were agreeing with me... -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
henry@utzoo.uucp (Henry Spencer) (07/20/88)
In article <11556@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > ... The action of a shift on an unsigned is pretty well defined... Not if it's shifting the full number of bits, it's not. Different machines handle this case differently. > If your compiler isn't correcting for hardware characteristics I say >it's broken. The idea of a C standard is that you don't have to build in >a bunch of hardware checks at the source level. Not quite. The idea of a C standard is to be a treaty between the user and the implementor. It tells the user what he can expect from the compiler, and -- just as important -- what he CAN'T expect from the compiler. One thing he cannot expect, in C, is for the compiler to try to cover up the underlying hardware. That is not the way C works. > What is needed is compiler code to check for a constant shift of 31+ >and load zero (no runtime penalty)... What if the shift count is a runtime quantity? Any such shift has to pay the penalty of bounds checking, even if the programmer knows full well that it's never more than (say) 3 bits. Please don't tell me that the penalty is only a few instructions; those few instructions can add up (especially if they include branches, which pipelined machines really hate). X3J11 has tried to avoid, on principle, any features that would require run-time checks on orthodox machines. Assigning specific semantics to overflow behavior -- which is what shifting all the bits out amounts to -- is such a feature in most cases. >...in my opinion reliable operation is more important than speed... Reliable operation means operation which obeys the rules of the language. If the language rules say -- as X3J11 does -- that the effect of such a shift is implementation-defined, then there is no reliability issue involved, except insofar as the programmer has to *understand* the language he is using in order to produce working programs. This is not Fortran or Pascal; C has always given people more than enough rope to hang themselves, for the sake of fast execution of programs written by those who *do* know what they're doing. Nobody ever said it was suitable for beginners. -- Anyone who buys Wisconsin cheese is| Henry Spencer at U of Toronto Zoology a traitor to mankind. --Pournelle |uunet!mnetor!utzoo! henry @zoo.toronto.edu
jlg@beta.lanl.gov (Jim Giles) (07/21/88)
In article <2620@wright.mips.COM>, earl@mips.COM (Earl Killian) writes: > [...] It always seemed > inconsistent to me to look are more than 5 (i.e. log2(bitsperword)) > without looking at all of them. But log2(bitsperword) is 6! 32 bits is only a half a word on a 'real' machine :-) J. Giles Los Alamos
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.
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (07/21/88)
In article <1988Jul19.173807.6604@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: | Reliable operation means operation which obeys the rules of the language. | If the language rules say -- as X3J11 does -- that the effect of such a | shift is implementation-defined, then there is no reliability issue | involved, except insofar as the programmer has to *understand* the language | he is using in order to produce working programs. This is not Fortran or | Pascal; C has always given people more than enough rope to hang themselves, | for the sake of fast execution of programs written by those who *do* know | what they're doing. Nobody ever said it was suitable for beginners. The rules may say anything is undefined, but that doesn't make it a good idea. At one time early in standards process, the question of having sizes known to the preprocessor was discussed. At that time my recollection is that sizeof was not to be allowed in a preprocessor constant expression, although reading the standard certainly seems to say it is at this time. Then the user could use conditional code as: #include <limits.h> #define UNSIGN_BIT (CHAR_BIT)*sizeof(unsigned)) #if UNSIGN_BIT < MAX_SHIFT /* brain damaged stuff, user runtime checks */ if (shift >= UNSIGN_BIT) valu = 0; else valu >>= shift; #else /* reasonable machine */ valu >>= shift; #endif My reason for saying the sizeof now seems legal is: section 3.8 p83 l15: #if takes a constant expression section 3.8.1 p84 l19-27: definition of const expr section 3.3.3.4 p43 l22: action of sizeof operator section 2.2.4.2 p13 l30-34: CHAR_BIT in limits.h The only thing disallowed in 3.8.1 is casts, and footnote 74 disallows keywords. However sizeof is an operator as defined in 3.3.3.4. If sizeof is NOT legal in preprocessor directives, then the standard should be clarified, and there is simply no way (known to me) to determine the size of int in bits at preprocessor time. It can be found, of course, at runtime, but that precludes use of conditional code to avoid checks where they are not needed. Yes, I've been programming C for awhile (since it was spelled B and ran on the GE600) and I can program around stuff like this. I'm sure Henry can, too. If C is ever going to be a portable general purpose language rather than a toy for hackers, programmers should not have to guess that two shifts of 10 don't give the same result as one shift of 20 (or whatever the sizes may be), or any of the other non-intuitive things which happen in the name of speed. Getting speed should be an "unsafe optimization," like dropping stack checking, ignoring alias problems, etc. It has a definite place and I don't deny that I would use it. The default should be to have the source code work as written. -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me
henry@utzoo.uucp (Henry Spencer) (07/22/88)
In article <440@softway.oz> stephenf@softway.UUCP (Stephen Frede) writes: >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. Sorry, Stephen, but in this case you're the one who's reacting without thinking. The first paragraph of the Semantics subsection of section 3.3.7 of the second-public-comment draft states: If the value of the right operand... is greater than or equal to the width in bits of the... left operand, the behavior is undefined. This applies to *all shifts*, not just signed ones. Somewhat further down we find another statement to the effect that right shifts of negative signed numbers give implementation-defined values. Note that these two statements don't say quite the same thing, either: right shift of a negative signed number yields an implementation-defined value, that is, a well-defined value that depends on the implementation in a way that the implementation is required to document, while shift-all-bits yields undefined behavior, that is, it can do anything it pleases. -- Anyone who buys Wisconsin cheese is| Henry Spencer at U of Toronto Zoology a traitor to mankind. --Pournelle |uunet!mnetor!utzoo! henry @zoo.toronto.edu
chris@mimsy.UUCP (Chris Torek) (07/22/88)
In article <440@softway.oz> stephenf@softway.oz (Stephen Frede) writes: >Contrary to the other two follow-ups I've seen .... 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. This is correct. The amount of the shift, however, must not be negative, or greater than or equal to the length of the object in bits (K&R, p. 189). Since this was `x >> 32' and x was a 32 bit (or smaller) object, the amount of the shift was too large, and the result is thus undefined, before we ever get to the question as to whether the result is implementation defined. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
chris@mimsy.UUCP (Chris Torek) (07/22/88)
In article <11606@steinmetz.ge.com> davidsen@steinmetz.ge.com (William E. Davidsen Jr) writes: >reading the [draft proposed X3J11 C] standard certainly seems to >say [that sizeof is allowed in preprocessor expressions] at this time. >... If sizeof is NOT legal in preprocessor directives, then the standard >should be clarified, ... It is explicitly disallowed in one tiny clause in the second most recent draft. (I have not yet had time to look at the most recent draft.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
henry@utzoo.uucp (Henry Spencer) (07/24/88)
In article <11606@steinmetz.ge.com> davidsen@crdos1.UUCP (bill davidsen) writes: > The rules may say anything is undefined, but that doesn't make it a >good idea. At one time early in standards process, the question of >having sizes known to the preprocessor was discussed. At that time my >recollection is that sizeof was not to be allowed in a preprocessor >constant expression, although reading the standard certainly seems to >say it is at this time. 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. >... If C is ever going to be a portable general purpose >language rather than a toy for hackers, programmers should not have to >guess that two shifts of 10 don't give the same result as one shift of >20 (or whatever the sizes may be), or any of the other non-intuitive >things which happen in the name of speed. To slightly misquote DMR: "if you want Pascal, you know where to find it". C is already a portable general purpose language, one which specializes in speed rather than in coddling novice C programmers. Consider an analogy. Effective and safe use of a fully-equipped vertical milling machine requires learning and practicing page after page of procedures and precautions; it is *not* something you can learn in five minutes, and the machine can -- literally -- kill you if you get sloppy. Building it out of soft plastic would make it much safer. However, for a real machining job, I want the metal one, despite its complex procedures and the very real dangers incurred in the name of rapid and precise machining. >... The default should be to have the source code work as written. It already does. When you write >> in a C program, that is the C >> operator you are writing, not some abstract mathematical version with different properties. -- Anyone who buys Wisconsin cheese is| Henry Spencer at U of Toronto Zoology a traitor to mankind. --Pournelle |uunet!mnetor!utzoo! henry @zoo.toronto.edu
stephenf@softway.oz (Stephen Frede) (07/25/88)
In article <440@softway.oz> stephenf@softway.oz (Stephen Frede (me)) writes: >Contrary to the other two follow-ups I've seen .... [silliness] I had hoped the cancel message would spread quick enough to save me too much embarassment. Unfortunately not, but I deserve it all. The followups to my article are of course correct. The other followups to the original article hadn't reached here when I originally posted. - Stephen
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
davidsen@steinmetz.ge.com (William E. Davidsen Jr) (07/26/88)
In article <12638@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: | In article <11606@steinmetz.ge.com> davidsen@steinmetz.ge.com | (William E. Davidsen Jr) writes: | >reading the [draft proposed X3J11 C] standard certainly seems to | >say [that sizeof is allowed in preprocessor expressions] at this time. | >... If sizeof is NOT legal in preprocessor directives, then the standard | >should be clarified, ... | | It is explicitly disallowed in one tiny clause in the second most recent | draft. (I have not yet had time to look at the most recent draft.) Actually I believe that the clause you mention was deleted. Here is a message and my reply: ================================================================ From: dmr@research.att.com Date: Tue, 26 Jul 88 01:15:16 EDT To: wedu@ge-crd.arpa Subject: #if sizeof p. 87, line 24-25 of the Jan draft (the constraint in 3.8.1) say "Additional restrictions apply.... The expression ... shall not contain a sizeof operator...." Dennis Ritchie ==== Subject: Re: #if sizeof Date: 26 Jul 88 08:36:16 EDT (Tue) From: davidsen@crdos1.UUCP (Wm E. Davidsen) Thanks for the reference from the January draft. The v3 draft in 3.8.1 constraints says: The expression that controls conditional inclusion shall be an integral constant expression except that: it shall not contain a cast; identifiers (including those lexically identical to keywords) are interpreted as described below{74}; and it may contain unary operator expressions of the form: defined identifier or defined ( identifier ) which evaluate to 1 if the identifier is currently defined as a macro name (that is, if it is predefined or if it has been the subject of a #define preprocessing directive without an intervening #undef directive with the same subject identifier), 0 if not. Each preprocessing token which remains after all macro replacements have occured shall be in the lexical form of a token. ---------------------------------------------------------------- 74 Because the controlling constant expression is evaluated during translation phase 4, all identifiers either are or are not macro names - there simply are no keywords, enumeration constants, and so on. Whatever was in the January draft seems to be removed. ================================================================ I can believe that this is a typo, although I would rather believe that sizeof is now allowed. -- bill davidsen (wedu@ge-crd.arpa) {uunet | philabs | seismo}!steinmetz!crdos1!davidsen "Stupidity, like virtue, is its own reward" -me