Hello folks, the following might be of some interested to us, maybe a little project for Bug Day 5:
---------------------------- Original Message ---------------------------- Subject: New mpn_get_str and mpn_set_str From: "Torbjorn Granlund" <[EMAIL PROTECTED]> Date: Mon, October 29, 2007 4:32 pm To: [EMAIL PROTECTED] -------------------------------------------------------------------------- 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 invoked. 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. -- Torbjörn _______________________________________________ gmp-devel mailing list [EMAIL PROTECTED] http://swox.com/mailman/listinfo/gmp-devel Cheers, Michael --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
