Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #12514 > unrolled thread

left shift count >= width of type

Back to article view | Back to comp.lang.c

Contents

  left shift count >= width of type Alessandro Basili <alessandro.basili@cern.ch> - 2011-11-02 10:55 +0100
    Re: left shift count >= width of type James Kuyper <jameskuyper@verizon.net> - 2011-11-02 07:34 -0400
      Re: left shift count >= width of type Keith Thompson <kst-u@mib.org> - 2011-11-02 13:47 -0700
      Re: left shift count >= width of type Alessandro Basili <alessandro.basili@cern.ch> - 2011-11-04 17:46 +0100
        Re: left shift count >= width of type James Kuyper <jameskuyper@verizon.net> - 2011-11-04 13:12 -0400
          Re: left shift count >= width of type Alessandro Basili <alessandro.basili@cern.ch> - 2011-11-05 19:17 +0100
    Re: left shift count >= width of type Thad Smith <ThadSmith@acm.org> - 2011-11-02 20:22 -0600

#12514 — left shift count >= width of type

[Multipart message — attachments visible in raw view] — view raw

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).
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;

Hope someone can clarify.

Al

-- 
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[toc] | [next] | [standalone]

#12524

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

[toc] | [prev] | [next] | [standalone]

#12548

James Kuyper <jameskuyper@verizon.net> 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) kst-u@mib.org  <http://www.ghoti.net/~kst>
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#12699

[Multipart message — attachments visible in raw view] — view raw

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.

[toc] | [prev] | [next] | [standalone]

#12701

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>

[toc] | [prev] | [next] | [standalone]

#12782

[Multipart message — attachments visible in raw view] — view raw

On 11/4/2011 6:12 PM, James Kuyper wrote:
> 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>

That lack of control on "what actually happens" is the driving force to
resolve the "undefined behavior". But I believe I got your point.

[toc] | [prev] | [next] | [standalone]

#12567

On 11/2/2011 3: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).
> 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;

Others have mentioned the undefined behavior if int is 32 bits.

Let's assume that ints contain more than 33 bits to eliminate the undefined 
behavior.  I'll assume that ints are 40 bits.

The assignment to foo is equivalent to
  foo = bar & (int)0xfeffffffff;

when the programmer probably intended

  foo = bar & 0x00ffffffff;

To keep the lower BITS_PER_UNIT bits (at least one) I would have written

  foo = bar & (((1u << (BITS_PER_UNIT-1))-1)*2 +1);

That should work, assuming the implementation has at least BITS_PER_UNIT bits in 
an unsigned int.  If bar is an unsigned int, then replace 1u with 1ul.

The embedded compiler I work with optimizes out anding with all one bits, so it 
would have no run-time penalty.


Thad

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web