Re: proposed gnulib-related additions to Autoconf

[Ralf Wildenhues]

Hi Paul,

* Paul Eggert wrote on Wed, Apr 05, 2006 at 09:15:58AM CEST:
> Ralf Wildenhues <address@hidden> writes:
> 
> >> +    AC_COMPILE_IFELSE(
> >> +      [AC_LANG_BOOL_COMPILE_TRY([AC_INCLUDES_DEFAULT([$4])],
> >> +   [$ac_max < $ac_max1 && ($1) $ac_max1 == $ac_max1])],
> >
> > Strictly speaking, for signed types this invokes undefined behavior, if
> > we shifted too far in `$ac_max1', so we can't be certain that the
> > outcome of this test will be good to use.  We rely on the fact that in
> > practice, this isn't a problem, right?
> 
> Yes, that's right.  I doubt whether any host would ever violate this
> property.  I don't think C99 + LIA-1 can violate it, and that's sort
> of the wave of the future anyway.

Ah, thanks.  Head to read up on what LIA-1 is first..

What I think you're trying to tell me is this: either the semantics are
wrap-around or some notification (exception or so).  But LIA-1 does not
specify bit-shift operations, as far as I can see.

And while that implies that we may be a bit out in the cold, I also
have some empirical indications that our current algorithm isn't quite
there yet:

For example, on x86_64-unknown-linux-gnu, GCC 3.4.4 and SVN trunk will,
when computing
   (((1U << k) - 1) << 1) + 1

for increasing integer k at program run time, produce the expected
wrap-around semantics for both signed and unsigned ints.  However,
at compile time, it will simply max out at the highest value once it
overflows, see this table for unsigned ints:

   k      runtime compile-time
------------------------------
   1            3            3
   2            7            7
   3           15           15
*snip*

  27    268435455    268435455
  28    536870911    536870911
  29   1073741823   1073741823
  30   2147483647   2147483647
  31   4294967295   4294967295
  32            1   4294967295
  33            3   4294967295
  34            7   4294967295


If a similar behavior may be observed on a system with a non-power-of-2
number of value bits for unsigned ints, this has consequences for our
algorithm.  I think we can simulate this situation by starting off with
a weird $ac_bits value, say 7.  After a few tests,

  $ac_max1 will be (((1U << 55) - 1) << 1) + 1
           which is computed as 4294967295

  $ac_max  will be (((1U << 27) - 1) << 1) + 1
           which is computed as 268435455

Erroneously, we thus decide 56 bits are ok, and try 110.  Here the
  $ac_max < $ac_max1
finally fails, but we end up with a wrong answer of 56 bits instead of
32.  Similar failures occur for signed quantities.

I believe this could be fixed by going back to the previous value of
$ac_max (so a tripel ac_max, ac_max1, ac_max2 would work).  But that
would mean we'd have to do many tests (> value_bits / 2) even for
"normal" systems which have power-of-2 bit sizes.

But maybe it is already sufficient to just compare our current
candidate for maximum with the next possible smaller one, like this:

    ac_bits1=`expr $ac_bits '*' 2`
    ac_shiftbits=`expr $ac_bits1 - 1 - $ac_signbit`
    ac_max1="(((($ac_1 << $ac_shiftbits) - 1) << 1) + 1)"
    ac_max2="(((($ac_1 << ($ac_shiftbits - 1)) - 1) << 1) + 1)"

    AC_COMPILE_IFELSE(
      [AC_LANG_BOOL_COMPILE_TRY([AC_INCLUDES_DEFAULT([$3])],
         [$ac_max < $ac_max1 && ($1) $ac_max1 == $ac_max1
          && $ac_max2 < $ac_max1])],
      [ac_bits=$ac_bits1; ac_max=$ac_max1],
      [break])

What do you think?

This is allowed by the compiler, right?

Cheers,
Ralf