Likely GMP bug

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> Il Ven, 25 Maggio 2018 2:10 pm, Niels Möller ha scritto:
>> That fails with undefined behavior if by chance t == 2^31, so that c ==
>> 31.
>>
>> I don't see how that can happen, though, since ulimb, vlimb < 2^31
>> through out the loop, and t = (ulimb - vlimb) mod 2^32.
>
> ... but can jump inside the loop ...
>
> 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?

> 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 09:29:41 2018 +0200
> @@ -83,8 +83,13 @@
>         }
>
>        ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
> -      if (ulimb == 0)
> -       goto done;
> +      ASSERT_ALWAYS (POW2_P (0));
> +      if (POW2_P (ulimb))
> +       {
> +         if (ulimb != 0)
> +           vlimb = 1;
> +         goto done;
> +       }
>
>        goto strip_u_maybe;
>      }

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

*** /tmp/extdiff.B7tg0s/gmp.aab8a010d10f/mpn/generic/gcd_1.c
    2018-05-26 10:42:48.367993924 +0200
--- /home/nisse/hack/gmp/mpn/generic/gcd_1.c    2018-05-26
    10:42:42.999989642 +0200
*************** mpn_gcd_1 (mp_srcptr up, mp_size_t size,
*** 180,185 ****
        {
        strip_u_maybe:
          vlimb >>= 1;
!         t = ulimb;
        }
        count_trailing_zeros (c, t);
--- 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);

Regards,
/Niels

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