Ciao, Il Sab, 26 Maggio 2018 10:47 am, Niels Möller ha scritto: > "Marco Bodrato" <bodr...@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/ _______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs