"Marco Bodrato" <bodr...@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. _______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs