tg at gmplib.org
Wed Jul 20 14:25:07 CEST 2011
Torbjorn Granlund <tg at gmplib.org> writes:
The bug is in GMP. It related to some calculations on the 64-bit
exponent using the 53 bits of accuracy of IEEE double. This leads to
rounding, making some internal sizes slightly too large, which in turn
causes a one-byte stack smash, overwriting the least sigificant byte of
a saved register, which contains a pointer, later to be passed to
I am really not sure how to solve this. By brain is in vacation mode,
so maybe I fail to see an obvious solution.
The problems is in mpf/get_str.c. There is the line,
e = (unsigned long) n_more_limbs_needed * (GMP_NUMB_BITS * mp_bases[base].chars_per_bit_exactly);
which computes an exponent for use by mpn_pow_1_highpart. I am looking
at the 20 lines of code staring around line 180. The value in
n_more_limbs_needed is large, with the bug report exponent, it becomes
With the approximation of log(2)/log(10) in chars_per_bit_exactly, e
becomes 405025890106316032. If it had been computed exactly, it would
have become 405025890106316169, i.e., 137 greater.
This rounding error results in a too small divisor (computed by
mpn_pow_1_highpart) and then an unexpected number of digits coming out
of mpn_get_str (a few lines later). This unexpected number of digits is
what smashes the stack, since tstr's allocation does not take rounding
errors into account.
So, the obvious solution is to analyse the maximum rounding error, and
fix tstr's allocation, right? The code is resilient in the sense that
too small exponents will not cause other harm than an intermediate
excess of digits.
Unfortunately, I am not sure extra allocation would work for all bases.
For base 10, the 53-bit logarithm approximation is smaller than the
exact value. For base 14, it is greater. Now, we will get a too large
exponent, and might perhaps divide our number to become zero...
Any suggestions? Calling mpf recursively to do the floating point
arithmetic more accurately will not be considered a realistic solution.
More information about the gmp-bugs