Re: left shift count >= width of type

Discussion in 'C Programming' started by James Kuyper, Nov 2, 2011.

  1. James Kuyper

    James Kuyper Guest

    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
     
    James Kuyper, Nov 2, 2011
    #1
    1. Advertising

  2. James Kuyper <> 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.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Nov 2, 2011
    #2
    1. Advertising

  3. 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.
     
    Alessandro Basili, Nov 4, 2011
    #3
  4. James Kuyper

    James Kuyper Guest

    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>
     
    James Kuyper, Nov 4, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wenjie
    Replies:
    3
    Views:
    1,057
    Ron Samuel Klatchko
    Jul 11, 2003
  2. Santosh Nayak

    Left Shift / Right Shift Operators

    Santosh Nayak, Nov 30, 2006, in forum: C Programming
    Replies:
    16
    Views:
    1,480
    CBFalconer
    Nov 30, 2006
  3. Sanny
    Replies:
    38
    Views:
    3,501
    Thomas Richter
    Apr 29, 2011
  4. pc
    Replies:
    2
    Views:
    1,358
    crisgoogle
    Jun 8, 2011
  5. Thad Smith

    Re: left shift count >= width of type

    Thad Smith, Nov 3, 2011, in forum: C Programming
    Replies:
    0
    Views:
    583
    Thad Smith
    Nov 3, 2011
Loading...

Share This Page