Likely GMP bug
nisse at lysator.liu.se
Mon May 28 11:56:57 UTC 2018
tg at gmplib.org (Torbjörn Granlund) writes:
> It really worries me that our crazy broad testing did not catch this
> until now. This makes me much less confident about GMP's correctness,
Here we have a bug where assumptions made by the code are violated, with
a pretty low probability given random inputs. And which results in an
actual miscomputation with *even* lower probability.
So found thanks to ubsan, not the testcode's validation of the result.
It's good to use ASSERTs to document assumptions made, even if an
ASSERT (c <= GMP_LIMB_BITS - 2) was missing in this case.
I think another contributing factor is that gcd_1 does two different
things: The tight loop to compute gcd of two words, and somewhat hairy
logic to reduce larger numbers before entering the loop. If we had gcd_1
doing the reduction and then calling a gcd_11 (ulimb, vlimb) to do the
remaining work, where the latter function has a well defined interface
with its own tests, it had been harder and less tempting to do the
> Replacement code should not jump into loops. This bug (but not the
> shortcoming of the test suite) should teach us that lesson.
goto has its uses, but this case with multiple target labels is more
like the infamous COME FROM... https://en.wikipedia.org/wiki/COMEFROM
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.
More information about the gmp-bugs