Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: left shift count >= width of type

Reply
Thread Tools

Re: left shift count >= width of type

 
 
James Kuyper
Guest
Posts: n/a
 
      11-02-2011
On 11/02/2011 05:55 AM, Alessandro Basili wrote:
> Hi,
> here's a simple program snippet that I'm dealing with and worried about
> potential pitfalls:
>
> #define BITS_PER_UNIT 32
> [...]
> int foo, bar;
>
> bar = 0xAAAA5555;
> foo = bar & ~ ((int) 1 << BITS_PER_UNIT);
> [...]
>
> Strictly speaking the shift operations should report a warning (left
> shift count >= width of type), since 1 is of type int (correct me if I'm
> wrong).


There's no guarantee that the shift count >= the width of the type,
since 'int' could be, for instance, a 64-bit type.

The relevant clause is phrased in terms of whether not the the result
can be represented in the type, not the width of the type, For the
expression E1 << E2, "If E1 has a signed type and nonnegative value, and
E1 x 2^E2 is representable in the result type, then that is the
resulting value; otherwise, the behavior is undefined" (6.5.7p5)

Therefore, for a 32-bit int, even 1 << 31 is problematic. That's an
example of why it's better to use unsigned types for most bit-masking
purposes.

However - and this is the key point - this is not a constraint, it's
undefined behavior. Conforming implementations are NOT required to issue
a diagnostic.

> Since this snippet is part of a very old implementation of g21k compiler
> for ADSP21xxx, I'm wondering why do we need to shift at all, isn't the
> above foo assignment equal to the following:
>
> foo = bar;


Since this code has undefined behavior if INT_MAX < pow(2,32), I would
hope that it was intended for an implementation where INT_MAX >
pow(2,32). I have no idea whether the "g2lk compiler for ADSP21xxx" is
such an implementation. If it were, then the foo assignment statement
would not be equivalent to "foo = bar".

However, it seem more plausible that the author of this code didn't know
or care about the fact that it had undefined behavior; it did what he
wanted it to do on the particular implementation where it needed to
work, and no attention was paid to whether or not it would do so
anywhere else.
--
James Kuyper
 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      11-02-2011
James Kuyper <(E-Mail Removed)> writes:
[...]
> There's no guarantee that the shift count >= the width of the type,
> since 'int' could be, for instance, a 64-bit type.
>
> The relevant clause is phrased in terms of whether not the the result
> can be represented in the type, not the width of the type, For the
> expression E1 << E2, "If E1 has a signed type and nonnegative value, and
> E1 x 2^E2 is representable in the result type, then that is the
> resulting value; otherwise, the behavior is undefined" (6.5.7p5)
>
> Therefore, for a 32-bit int, even 1 << 31 is problematic. That's an
> example of why it's better to use unsigned types for most bit-masking
> purposes.
>
> However - and this is the key point - this is not a constraint, it's
> undefined behavior. Conforming implementations are NOT required to issue
> a diagnostic.


In addition (C99 6.5.7):

If the value of the right operand is negative or is greater than or
equal to the width of the promoted left operand, the behavior is
undefined.

So for a 32-bit type, even 0<<32 or 0>>32 has undefined behavior, even
though the mathematical result is representable.

[...]

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
 
 
 
Alessandro Basili
Guest
Posts: n/a
 
      11-04-2011
On 11/2/2011 12:34 PM, James Kuyper wrote:
[...]
>
> The relevant clause is phrased in terms of whether not the the result
> can be represented in the type, not the width of the type, For the
> expression E1 << E2, "If E1 has a signed type and nonnegative value, and
> E1 x 2^E2 is representable in the result type, then that is the
> resulting value; otherwise, the behavior is undefined" (6.5.7p5)
>
> Therefore, for a 32-bit int, even 1 << 31 is problematic. That's an
> example of why it's better to use unsigned types for most bit-masking
> purposes.


thanks for pointing that out. I indeed agree that bit masking may result
in unexpected behavior if signed are used instead of unsigned, that's
why I'm usually used to have my own data types not to get confused.

>
> However - and this is the key point - this is not a constraint, it's
> undefined behavior. Conforming implementations are NOT required to issue
> a diagnostic.
>


And I believe that is what happened in this case. Has to be said that
this code is nearly 10 year old and back then probably gcc was not as
rigorous as is today.

>> Since this snippet is part of a very old implementation of g21k compiler
>> for ADSP21xxx, I'm wondering why do we need to shift at all, isn't the
>> above foo assignment equal to the following:
>>
>> foo = bar;

>
> Since this code has undefined behavior if INT_MAX < pow(2,32), I would
> hope that it was intended for an implementation where INT_MAX >
> pow(2,32). I have no idea whether the "g2lk compiler for ADSP21xxx" is
> such an implementation. If it were, then the foo assignment statement
> would not be equivalent to "foo = bar".


Got your point. Indeed, compiling on my machine where INT_MAX <
pow(2,32) the behavior is undefined, while it may very well be that in
the author's case the INT_MAX > pow(2,32).
That is also why there is a definition used in the code:

> #if HOST_BITS_PER_LONG > HOST_BITS_PER_INT
> #define HOST_BITS_PER_WIDE_INT HOST_BITS_PER_LONG
> #define HOST_WIDE_INT long
> #else
> #define HOST_BITS_PER_WIDE_INT HOST_BITS_PER_INT
> #define HOST_WIDE_INT int
> #endif


where there's a clear intention to distinguish between the two cases.
Essential point is that apparently no attention was paid to the fact
that int might be signed.

>
> However, it seem more plausible that the author of this code didn't know
> or care about the fact that it had undefined behavior; it did what he
> wanted it to do on the particular implementation where it needed to
> work, and no attention was paid to whether or not it would do so
> anywhere else.


Considering that this compiler is specific for a family of DSPs, I
rather think that was the case back then.


 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      11-04-2011
On 11/04/2011 12:46 PM, Alessandro Basili wrote:
> On 11/2/2011 12:34 PM, James Kuyper wrote:

....
>> However - and this is the key point - this is not a constraint, it's
>> undefined behavior. Conforming implementations are NOT required to issue
>> a diagnostic.
>>

>
> And I believe that is what happened in this case.


<nit-pick> The fact that this code has "undefined behavior" is why
whatever actually happens is permissible, regardless of what actually
happens. "Undefined behavior" is not a specific kind of behavior that
can happen or not happen.</nit-pick>
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
shift left/shift right in VHDL deepak21 Software 0 05-06-2012 09:01 AM
Re: left shift count >= width of type Thad Smith C Programming 0 11-03-2011 02:22 AM
Java left shift and right shift operators. Sanny Java 38 04-29-2011 10:02 PM
Left Shift / Right Shift Operators Santosh Nayak C Programming 16 11-30-2006 05:10 PM
left shift then right shift an unsigned int Wenjie C++ 3 07-11-2003 08:22 PM



Advertisments