Likely GMP bug

[Niels Möller]

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,
> 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... https://en.wikipedia.org/wiki/COMEFROM

Regards,
/Niels

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