Likely GMP bug

[Marco Bodrato]

Ciao,

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;
    }

...

      if (0)
	{
	strip_u_maybe:
	  vlimb >>= 1;
	  t = ulimb;
	}

In this case, t is the result of MOR_OR_MODEXACT, maybe t == 2^31 .

I propose the following:


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;
     }


Ĝis,
m

-- 
http://bodrato.it/