Likely GMP bug

[Marco Bodrato]

Ciao,

Il Sab, 26 Maggio 2018 10:47 am, Niels Möller ha scritto:
> "Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
>> That's the culprit:
>>
>>   if (size > 1)
>>     {
>>       ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
>>       goto strip_u_maybe;
>>     }

> Ah, that's subtle! Thank's for tracking it down. Do you know if it
> results in a miscomputation on the typical (32-bit) machines where (x >>
> 32) == x?

In my opinion, both cases (x >> 32) == x and (x >> 32) == 0 do not give a
miscomputation, but you should ask to the author of that GCD_1_METHOD:
https://gmplib.org/repo/gmp/rev/e9de1fea3ad2 :-)

> Alternatively, change only the branch that have this problem,
> something like this (untested):

> --- 180,189 ----
>         {
>         strip_u_maybe:
> +         count_trailing_zeros (c, ulimb);
>           vlimb >>= 1;
> !         ulimb >>= 1;
> !         /* c+1 is not always a valid shift count. */
> !         ulimb >>= c;
> !         continue;
>         }
>         count_trailing_zeros (c, t);

I strongly disagree. Two reasons.

The first: there are two "goto strip_u_maybe" in the code, the other one is
  if ((ulimb >> 16) > vlimb)
    {
      ulimb %= vlimb;
      if (ulimb == 0)
	goto done;
      goto strip_u_maybe;
    }
This case does not need any correction. That's why, to "change only the
branch that have this problem", we should change the code before the goto,
not after it.

The second: gotos are dangerous, as we can see... A block
  if (0) { /* we can not enter here from the previous line */
    label_for_goto:
      __some_code;
      continue; /* in no cases we execute the next line */
  }
placed in a random place inside a loop... sounds like a good way to
obfuscate the algorithm.

If you prefer a smaller patch, I can suggest:

diff -r a2b594f11916 mpn/generic/gcd_1.c
--- a/mpn/generic/gcd_1.c       Sun May 13 16:13:42 2018 +0200
+++ b/mpn/generic/gcd_1.c       Sat May 26 11:50:22 2018 +0200
@@ -86,6 +86,7 @@
       if (ulimb == 0)
        goto done;

+      ulimb >>= 1 ^ ulimb & 1;
       goto strip_u_maybe;
     }


But I personally vote for the one in my previous e-mail. It was an
inexpensive check adding a shortcut for some (admittedly rare) cases and,
as a side effect, avoiding the undefined behaviour.

Ĝis,
m

-- 
http://bodrato.it/papers/