New mpn_get_str and mpn_set_str
tege at swox.com
Mon Oct 29 16:32:42 CET 2007
I've put new versions of mpn_get_str and mpn_set_str at
http://gmplib.org/devel/. This fixes a buffer overrun in mpn_get_str
present in previous prereleases, and boosts performance of about 20%
for mpn_get_str and about 30% for mpn_set_str.
Please note that the buffer overrun does not exist in released GMP
code, only in previous version of mpn_get_str made available from
gmplib.org/devel/. It is also difficult to trigger. I've only
triggered it with a "minithres" pseudo configuration, using minimal
threshold for artificially triggering bugs in our implementations of
subquadratic algorithms. The conditions are difficult to exactly
analyse, but adjusting the allocation to be safe was not hard.
Details on the overrun:
The overrun happened for the quotients computed by mpn_tdiv_qr called
from mpn_dc_get_str. The tmp area needs to accomodate all quotients in
any recursive chain, but the largest need will clearly happen for the
left-most call chain, and in that chain just before the basecase is
The worst case assumption is that the quotients become exactly as large
as the powers (precomputed in powtab). This implies that one more limb
per recursion might be needed than the allocation accomodated for. But
then the GET_STR_DC_THRESHOLD will stop recursion and leave a tail of
the tmp area (tail size roughly = GET_STR_DC_THRESHOLD), since the last
quotients will not be computed.
The conclusion is that the larger GET_STR_DC_THRESHOLD, the harder it
is to trigger the bug; only very large numbers (many millions of
digits) will risk to trigger it.
More information about the gmp-devel