Previously unknown 'C' behavior (to me).

[tggzzz]

Still, shifting a 32 bit value left by 32 places could reasonably be expected to be problematic.  NO, I wouldn't have thought of it!  I'm not that smart, before the fact.  After the fact, I could see where the compiler would only allow 5 bits of shift count (0..31) and 32 modulo 32 is 0 so no shift occurs.  Seems reasonable.  After the fact...  Why there are two results is interesting.  I guess the compiler writer (another programmer) didn't consider the effect of optimization.

Don't feel too bad about it! The vast majority of C/C++ practitioners are the same, whether or not they like to admit it.

How many people have ever read the formal definition of ANY language. 

Normal users shouldn't have to read the formal definition. People implementing language tools (compilers etc) need to. They need a good formal definition, otherwise we are back to "operational semantics" where in order to see what it will do, you have to do it and observe what was done.

At the edges, what should happen when a 32 bit value is shifted left about a bazillion places?  Let's suppose the definition actually provides an answer.  How do we know that the compiler writer met the requirements?

We can't. But without a good unambiguous definition you can't even write the tests because you don't know what is meant to happen.

And the folklore told by language experts is that is exactly what occurs with C/C++; in some cases the compiler writers have had to ask experienced users "what is meant by X".

How can we ever test everything.  Yes, I know GCC comes with a validation suite but I can't say that I ever looked at it.  Is it complete?  Well, it's pretty clear something slipped by...

You don't have to assume anything slipped by. Nasal daemons do occur in the C/C++ world.

This idea of correctness is a serious problem in the nuclear industry, as it should be.  The verification programs were written in a very specific dialect of Fortran on a very specific computer with very specific libraries and there would be no changes.  Ever!  That created a situation where obsolete hardware was being maintained indefinitely simply because nobody wanted to go back through the task of verifying the verification programs.  The NRC had already bought off on the existing code/hardware.  I don't think there was a 'patch of the month' program.

ISTR recall adverts for people with PDP-11 experience, because they were going to continue to be used until the 2040s!

A reactor is no place to find out that Intel has another bug in the FPU.

And what about that problem in the 14th decimal place of the SINH function?  What's with that?  No, I don't know if there is a real problem, I'm making it up.  But you don't know that!  Now everybody is going to go looking at the e^x code.

Those are implementation issues, not definition issues. Besides, anyone that relies on the exact value of floating point numbers is living in a state of sin (not sine )

[tggzzz]

A defensive programmer might have masked the sum of the two shift counts with 0x1F to force it into range or perhaps even deliberately handled the situation where the sum is greater than 31.  I guess if you don't know how the compiler is going to react, you can take the position of defending against it.

Precisely.

And, of course, you would have to assume that the compiler correctly implemented your defensive code, and/or didn't optimise it away!

[GeorgeOfTheJungle]

And the trap is quietly sitting there just waiting to catch the next unsuspecting poor guy.

Or not...

Honestly I also would have expected (uint32_t) 0xffffffff << 32 to be 0

[Kalvin]

A defensive programmer might have masked the sum of the two shift counts with 0x1F to force it into range or perhaps even deliberately handled the situation where the sum is greater than 31.  I guess if you don't know how the compiler is going to react, you can take the position of defending against it.

... and create incorrect result. For example, what will happen if the shift count is 32 and you mask it with 0x1F ...

[rstofer]

A defensive programmer might have masked the sum of the two shift counts with 0x1F to force it into range or perhaps even deliberately handled the situation where the sum is greater than 31.  I guess if you don't know how the compiler is going to react, you can take the position of defending against it.

... and create incorrect result. For example, what will happen if the shift count is 32 and you mask it with 0x1F ...

It will go to 0 and be caught in the following code

Code: [Select]

shift_count &= 0x1f;
if (shift_count > 0) {
  value = value << shift_count;
}
else {
  <do whatever you want when shift_count = 0>
}

Something like that...

There is no point in shifting a 32 bit quantity 32+ bits to the left.  You can set the value to 0 or trap on an erroneous shift_count.

[Kalvin]

A defensive programmer might have masked the sum of the two shift counts with 0x1F to force it into range or perhaps even deliberately handled the situation where the sum is greater than 31.  I guess if you don't know how the compiler is going to react, you can take the position of defending against it.

... and create incorrect result. For example, what will happen if the shift count is 32 and you mask it with 0x1F ...

It will go to 0 and be caught in the following code

Code: [Select]

shift_count &= 0x1f;
if (shift_count > 0) {
  value = value << shift_count;
}
else {
  <do whatever you want when shift_count = 0>
}

Something like that...

There is no point in shifting a 32 bit quantity 32+ bits to the left.  You can set the value to 0 or trap on an erroneous shift_count.

Your code will fail miserably and give you incorrect value if the shift count happens to be 33 or more ...

[GeorgeOfTheJungle]

Your code will fail miserably and give you incorrect value if the shift count happens to be 33 or more ...

Yes it will...

[rstofer]

Your code will fail miserably and give you incorrect value if the shift count happens to be 33 or more ...

Yes it will...

Why would you want to shift a 32 bit value more than 31 places?  OK, I can almost see shifting 32 places to clear the value but, really, is that the best way to set a value to 0?  Why not just trap the condition and set the directly to 0?  Then you know how it will turn out!

Of course, there is the possibility that 'value' is something other than 32 bits so maybe testing against 8*sizeof(value)-1 (which the compiler will treat as a constant) is a better upper limit.  If somebody seriously wants to shift beyond the end bit position then 8 * sizeof(value) would work.

You would still need to test against 0 either to prevent shifting zero places (why bother?) or shifting to a negative number of bits (if shift_count is signed).  One is a nop and the other just has to be a mistake.

Right or wrong, I'm going to define shift_count as unsigned and just mask it into the range of 0..31.  I should certainly know enough about the range of shift_count values to know if that is satisfactory.

[brucehoult]

It will go to 0 and be caught in the following code

Code: [Select]

shift_count &= 0x1f;
if (shift_count > 0) {
  value = value << shift_count;
}
else {
  <do whatever you want when shift_count = 0>
}


Yeah, nah. You might want to check for great than zero *before* masking it.

There is no point in shifting a 32 bit quantity 32+ bits to the left.  You can set the value to 0 or trap on an erroneous shift_count.

Code like the following is VERY common:

Code: [Select]

v = (u<<n) | (u>>(32-n))

It's a left rotate.

Incidentally, it works perfectly regardless of whether u<<32 and u>>32 give 0 or u :-)  (quiz: why?)

You'd better hope that n isn't outside the range 0..32 though, unless you've got a CPU that only uses the lower bits. If in any doubt, use (n%32) in both places -- the compiler will optimize it away if it's not needed. And if it *is* needed ... then you need it.

[Bruce Abbott]

Why would you want to shift a 32 bit value more than 31 places?

'Why' is irrelevant. The question is if you want to do that, how do do it in the language you are using? In assember you can shift as many times as you like and the result is well defined. In C it isn't so you have to trap or avoid out-of-range values. That's the price you pay for efficient portability.

Normal users shouldn't have to read the formal definition.

So you think 'normal' users should be able to just wing it and hope for the best? No wonder there's so much crap code out there (and crap coders).

Speaking of which... how often have you looked at some new language or platform touted as being more powerful and easier to use, only to discover that the 'formal definitions' are either suspiciously terse or non-existent? But that's how it is these days - devices are made 'user-friendly' so you don't need a manual to use them - then you spend hours trying to figure out how to use them properly (and never really knowing whether you are doing it right).

 
   

[IanB]

In assembler you can shift as many times as you like and the result is well defined. In C it isn't so you have to trap or avoid out-of-range values.

If I remember previous comments in the thread, then apparently not. If the hardware masks off all but the lower 5 bits of the shift argument before applying it, then even in assembly the results may not be what you hoped for.

This may be well defined by the hardware specification, but fewer people read the hardware manual than read the compiler manual...

[westfw]

Code like the following is VERY common:
v = (u<<n) | (u>>(32-n))
It's a left rotate.

Clearly what we need is a language with a native "rotate" operator!
(I'm amused that if this "undefined behavior" slips into someone's C "rotate" code, it's essentially because they were avoiding using assembly language (where there was probably a native "rotate" instruction that would have worked better.))

[whine, whine, C is such an awful language]

Someone asked for a credible replacement a while back.  I haven't seen any actual suggestions...

My latest complaint is that some C compilers have stopped doing what I ask them to, because (apparently) the compiler writers have decided that they'd rather use those "undefined behavior" sections to "teach us a lesson", rather than have code follow the expected behavior.
I mean, if you do embedded programming, you'd expect:

Code: [Select]

    for (uint8_t count=1; count != 0; count++) {
       // Stuff
    }to terminate after about 255 loops, right?   Not be optimized into an infinite loop because "integer overflow behavior is undefined and the optimizer decided that you'll never hit zero by incrementing an unsigned variable" ?   Ha hah!  Surprise!

Code: [Select]

  for (uint8_t i=0x80; i != 0; i>>=1) {}Isn't generating the obvious code, either :-(
( http://www.avrfreaks.net/forum/avr-gcc-creating-loop-counters-out-nothing-no-reason )

[tggzzz]

Normal users shouldn't have to read the formal definition.

So you think 'normal' users should be able to just wing it and hope for the best? No wonder there's so much crap code out there (and crap coders).

Ideally yes, since the code's behaviour would be obvious from looking at it. That is obviously possible with languages like LISP and Forth, since they are so simple; other languages approach that ideal.
For most languages that won't be possible, but the formal definition should be readable and understandable.

With C/C++, the standards are so dense, impenetrable and incomprehensible that even the language designers have arguments about what various sections mean and whether or not one section conflicts with another.[1] Mere mortals - including compiler writers - are caught in the crossfire. The result is "operational semantics", where you have to run each compiler and each compiler version to find out what it actually does.

Speaking of which... how often have you looked at some new language or platform touted as being more powerful and easier to use, only to discover that the 'formal definitions' are either suspiciously terse or non-existent? But that's how it is these days - devices are made 'user-friendly' so you don't need a manual to use them - then you spend hours trying to figure out how to use them properly (and never really knowing whether you are doing it right).

Well, .... yes

It isn't a new phenomenon. As Tony Hoare (Quicksort, CSP, synchronisation/monitors, etc) wryly quipped long ago about one of the first high level languages, Algol-60 was an improvement on many of its successors.

[1] at first the design committee didn't believe the C++ template language was Turing-complete; they hadn't intended that was the case! Then their noses were rubbed in that fact when they saw a simple program that could never finish being compiled - because the compiler was (very slowly) emitting the sequence of prime numbers during compilation. The language itself was out of control.

[brucehoult]

Normal users shouldn't have to read the formal definition.

So you think 'normal' users should be able to just wing it and hope for the best? No wonder there's so much crap code out there (and crap coders).

[/quote]

JavaScript has got to be the worst offender here! The semantic fuckups in it are legion.

[brucehoult]

Code like the following is VERY common:
v = (u<<n) | (u>>(32-n))
It's a left rotate.

Clearly what we need is a language with a native "rotate" operator!
(I'm amused that if this "undefined behavior" slips into someone's C "rotate" code, it's essentially because they were avoiding using assembly language (where there was probably a native "rotate" instruction that would have worked better.))

Any decent compiler in the last 20 years will in fact turn that into a rotate instruction, if one exists.

I mean, if you do embedded programming, you'd expect:

Code: [Select]

    for (uint8_t count=1; count != 0; count++) {
       // Stuff
    }to terminate after about 255 loops, right?   Not be optimized into an infinite loop because "integer overflow behavior is undefined and the optimizer decided that you'll never hit zero by incrementing an unsigned variable" ?   Ha hah!  Surprise!

Maybe better read the manual :-)  That will work fine. Overflow for unsigned integers is well defined. They are N bit binary modulo arithmetic, whether the underlying CPU is binary or not. Guaranteed. Decimal or trinary or whatever computers have to work harder to make shifts and & and | and ^ and ~ work the same as in binary.

It's *signed* integers where it's undefined.

[NorthGuy]

I mean, if you do embedded programming, you'd expect:

Code: [Select]

    for (uint8_t count=1; count != 0; count++) {
       // Stuff
    }to terminate after about 255 loops, right?   Not be optimized into an infinite loop because "integer overflow behavior is undefined and the optimizer decided that you'll never hit zero by incrementing an unsigned variable" ?   Ha hah!  Surprise!

This is not accurate because

"A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned integer type is
reduced modulo the number that is one greater than the largest value that can be
represented by the resulting type". (C99 6.2.5.9)

To nitpick, this citation doesn't apply here because of the integer promotion. When "count++" is calculated, the value of "count" must be fetched, converted to "int" (this is called integer promotion), then 1 is added and the result is assigned back to "count". While assigning the value to "count", the result is converted to the type of "count" using this rule:

"if the new type is unsigned, the value is converted by repeatedly adding or
subtracting one more than the maximum value that can be represented in the new type
until the value is in the range of the new type".(C99 6.3.1.3.2)

Thus, 255+1=256 should be converted to 0 when assigned to "count" (which is uint8_t), producing the exact result you would expect.

Therefore, the code should work as expected. Optimizing it to infinite loop would be against C99.

The development of the C standard took a long time and a lot of thinking, so it is very good at producing the most reasonable behaviour for the vast majority of the situations.

[rstofer]

The shift count for the ARM barrel shifter is just 5 bits and considered unsigned.  Shifts of 0..31 are allowed.  Masking the count with 0x1F makes a lot of sense even though the hardware is going to do it anyway.  At the very least, it documents the programmer's intent.  I haven't looked but I would expect a similar hardware limitation on every CPU that implements a multi-bit shift.

[tggzzz]

The development of the C standard took a long time and a lot of thinking, so it is very good at producing the most reasonable behaviour for the vast majority of the situations.

Yes, but... You need to define the criteria by which "most reasonable" is determined.

Is it so that it caters for mainstream and baroque machine architectures?
Is it so that non-expert users can understand and predict what will happen?
Is it so that compiler and tool writers can understand and predict what will happen?
Is it so that the pre-existing compilers don't have to radically change the code they generate?
Is it so that the committee can agree they understand the standard, and that the standard is finished?
etc etc.

[GeorgeOfTheJungle]

The shift count for the ARM barrel shifter is just 5 bits and considered unsigned.  Shifts of 0..31 are allowed.  Masking the count with 0x1F makes a lot of sense even though the hardware is going to do it anyway.  At the very least, it documents the programmer's intent.  I haven't looked but I would expect a similar hardware limitation on every CPU that implements a multi-bit shift.

Why would you want to do that? Why mask with 0x1f (or %32)? How is shifting say 32 times/bits to the left the same as not shifting? Or shifting 33 times/bits to the left the same as shifting once?

[TNorthover]

The shift count for the ARM barrel shifter is just 5 bits and considered unsigned.

If only it was that simple. If the amount is variable then what you actually get is "x << (amt % 256)". Unless it's 64-bit, in which case what you said holds. Unless it's actually a NEON instruction (both 32-bit and 64-bit), in which case it's the byte that matters again but it's signed and you get a right shift if it's negative (either arithmetic or logical, depending on preference).

Basically it's a complete mess and that's why no-one should be relying on the behaviour of out of range shifts in portable code (or ever, really).

[NorthGuy]

Yes, but... You need to define the criteria by which "most reasonable" is determined.

Is it so that it caters for mainstream and baroque machine architectures?
Is it so that non-expert users can understand and predict what will happen?
Is it so that compiler and tool writers can understand and predict what will happen?
Is it so that the pre-existing compilers don't have to radically change the code they generate?
Is it so that the committee can agree they understand the standard, and that the standard is finished?
etc etc.

It is so that it hinders you the least.

[hamster_nz]

I'm thinking that the definition of "shifts of more than n bits shift is undefined" came later on in life for C.

The intent of shift operations is clear
: 'there was n bits in the bed, and the little one said "Roll over, roll over", so they all rolled over and one fell out'

At the time of the early versions of C most CPUs would not have a barrel shifter, so
"n>>6" would end up as 6 "shift left" opcodes or a small loop, or maybe a CISC instruction that took 'quite a few' cycles to execute. Hence why even within the 80x86s the behavior varies

"The C Programming Language" (edition 2) makes no reference to masking the shift count.

I can't be bothered to research it, but I would bet that when barrel shifters became common it broke code, and the standard was updated to note this as "undefined" behavior.

The whole "mask the shift operand" is just what hardware does, it isn't what it should do. It should do this:

Code: [Select]

if(n > 31) /* Protect against broken barrel shifters */
  a = 0;
else
  a <<= n;


[IanB]

To nitpick, this citation doesn't apply here because of the integer promotion. When "count++" is calculated, the value of "count" must be fetched, converted to "int" (this is called integer promotion) ...

Can you explain why count must be converted to int? Why can the ++ operator not be applied directly to an unsigned char type?

[hamster_nz]

To nitpick, this citation doesn't apply here because of the integer promotion. When "count++" is calculated, the value of "count" must be fetched, converted to "int" (this is called integer promotion) ...

Can you explain why count must be converted to int? Why can the ++ operator not be applied directly to an unsigned char type?

It is a reflection that the intent of C's promotion rules, aimed at using the native word size of the platform.

if the range of type being used can fit into an 'int', then it is computed as an 'int'. eg.

A contrived example being:

Code: [Select]

uint_8 a = 16;
int_8 b = -128;
int_8 c = -64;
a = a * b / c;

Will set a to 32

So the value of "(count++)" will be an int, even when "count" is a 'unsigned char'.

[NorthGuy]

Can you explain why count must be converted to int? Why can the ++ operator not be applied directly to an unsigned char type?

All operations on arithmetic operands which are shorter than "int" require integer promotion - they are first converted to "int" (or "unsigned int") then operated upon.

"If an int can represent all values of the original type (as restricted by the width, for a
bit-field), the value is converted to an int ; otherwise, it is converted to an unsigned
int . These are called the integer promotions". (C99 6.3.1.1.2)

Of course, in real life, the operations may be done without promotion, but only if the result is exactly the same as if the promotion has been applied.