Subject: bug#7928: mktime test in configure: UB resulting in infinite loop

From: Bruno Haible <[email-masked]>
Date: Thu, 27 Jan 2011 19:42:10 +0100

Rich Felker wrote:
> > # define TYPE_MAXIMUM(t) \
> >   ((t) (! TYPE_SIGNED (t) \
> >         ? (t) -1 \
> >         : ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1))))
> 
> The last line of this macro has UB due to signed integer overflow in
> the << operation.

No there is no overflow here. The ~ operator has higher syntactic precedence
than the << operator, therefore the expression in the last line consists of
4 steps:
  1. Take a zero.
  2. Invert all bits.
  3. Shift left by n-1 bits.
  4. Invert all bits.

Taking <http://en.wikipedia.org/wiki/Signed_number_representations> as
reference, in all three cases (two's complement, one's complement, signed
magnitude) the results are:
  - after step 1: 000...00
  - after step 2: 111...11
  - after step 3: 100...00 (and no overflow here, in two's complement)
  - after step 4: 011...11

ISO C 99 says about the << operator:
  "The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated
   bits are filled with zeros. If E1 has an unsigned type, the value of
   the result is E1 × 2^E2 , reduced modulo one more than the maximum
   value representable in the result type. If E1 has a signed type and
   nonnegative value, and E1 × 2^E2 is representable in the result type,
   then that is the resulting value; otherwise, the behavior is undefined."

If you take the first sentence as a mandatory description of what <<
does, then ~ (~ (t) 0 << (sizeof (t) * CHAR_BIT - 1)) is the bit pattern
011...11 on all systems and with all compilers.

If you take the last sentence as more relevant than the first one, then
any shift of any negative value is undefined behaviour.

Do you mean to say that GCC produces undefined behaviour for shifts of
negative values, even those where the result is negative (no overflow)?
I've never seen a sign of that.

Bruno