overflow in LIMBS_PER_DIGIT_IN_BASE
tg at gmplib.org
Tue Dec 17 11:18:29 UTC 2013
Zimmermann Paul <Paul.Zimmermann at inria.fr> writes:
with ABI=32, the macro LIMBS_PER_DIGIT_IN_BASE might overflow for large input
strings, as demonstrated by the following program: mp_bases[b].log2b is
3196634803, thus with ndigits=721334514 we have
_ph = floor(3196634803*ndigits/2^32) = 536870912 = 2^29, then 8*_ph = 2^32
overflows to 0, and the return value is 2. As a consequence, this leads to
an out-of-bound write and the program aborts (here I've added some debug
statements to print intermediate values):
#define N 721334514
#define B 62
721334514*log(62)/log(2) > 2^32 which means this is outside of the
claimed precision of 2^32 bits on a 32-bit computer.
That's why that macro is written in an overflowish manner. One could
make it more resilient to overflow when 8 | GMP_LIMB_BITS, but I see no
point in such a change.
A possible improvement would be to detect the anomalous situation in
mpz_set_str, and issue an overflow error. I'll put that on my todo
list, but won't do it soon.
Please encrypt, key id 0xC8601622
"A week in the lab saves an hour in the library."
More information about the gmp-bugs