Likely GMP bug

Niels Möller nisse at
Mon May 28 11:56:57 UTC 2018

tg at (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,
> actually.

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
obscure thing.

> 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...


Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.

More information about the gmp-bugs mailing list