integer overflow in mpn/get_d.c from GMP 5.1.2

[Vincent Lefevre]

On 2013-09-20 16:06:49 +0200, Niels Möller wrote:
> Vincent Lefevre <vincent at vinc17.net> writes:
> 
> > In GMP 5.1.2, there's an integer overflow in mpn/get_d.c:
> >
> >   if (UNLIKELY ((unsigned long) (GMP_NUMB_BITS * size)
> >                 > (unsigned long) (LONG_MAX - exp)))
> >
> > It should be replaced by:
> >
> >   if (UNLIKELY ((unsigned long) (GMP_NUMB_BITS * size)
> >                 > (unsigned long) LONG_MAX - exp))
> >
> > This integer overflow triggers the following failure
> 
> Assuming your C compiler uses two's complement representation for signed
> values, I'm not sure I understand why that change makes any difference.

Because there's no undefined behavior on unsigned arithmetic, and
on signed arithmetic, an integer overflow is undefined behavior,
whatever the representation. And undefined behavior could lead to
"incorrect code" due to advanced optimizations (I suppose that VRP
might have such an effect, in particular when combined with LTO,
for library functions).

> Casting the result makes it clear that the result should be intepreted
> as unsigned long. If you change it to (unsigned long) LONG_MAX - exp,
> the type depends on C conversion rules. Which are a bit obscure. But as
> far as I understand, the result is still of type unsigned long, and it's
> the value of exp which is gets converted from long to unsigned long.

Actually for "long" arguments, this forces unsigned long arithmetic
on the subtraction.

> And the result should be in the range 0 to LONG_MAX - LONG_MIN, which
> usually is the same as ULONG_MAX, and hence it always fits (but with
> no margin!) in an unsigned long. 

Yes, the result fits in the unsigned long, but without the cast on
one of the arguments, the cast is too late: the subtraction is done
in signed arithmetic (long), and LONG_MAX - LONG_MIN doesn't fit in
a "long".

-- 
Vincent Lefèvre <vincent at vinc17.net> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)