Slight tweak to generic mpn_modexact_1c_odd
David Sparks
sparks05 at proton.me
Sat Feb 7 00:19:52 CET 2026
The code
if (s > c)
{
l = s-c;
h = l % d;
if (h != 0)
h = d - h;
}
could avoid the second branch by using "h = (l-1) % d + 1"
instead, which returns a modulus in the range 1 <= h <= d,
allowing the d - h to be unconditional.
Since s > c (strict), l > 0, so there's room for the -1.
And of course, "d - (h + 1)" can be turned into "d - 1 - h",
taking the increment off the critical path.
But then this leads to the fact that (s-c)-1 = -(c-s)-1 = ~(c-s),
which turns into the following patch:
diff --git a/mpn/generic/mode1o.c b/mpn/generic/mode1o.c
index 9ba0ae1cc..fcd6c01b9 100644
--- a/mpn/generic/mode1o.c
+++ b/mpn/generic/mode1o.c
@@ -127,18 +127,11 @@ mpn_modexact_1c_odd (mp_srcptr src, mp_size_t size, mp_limb_t d,
if (size == 1)
{
s = src[0];
- if (s > c)
- {
- l = s-c;
- h = l % d;
- if (h != 0)
- h = d - h;
- }
+ l = c-s;
+ if (c >= s)
+ h = l % d;
else
- {
- l = c-s;
- h = l % d;
- }
+ h = d - 1 - (~l % d);
return h;
}
I swapped the order of the branches to let the code reader
see the simple case first and get the hint that the obscure
code is equivalent.
Placing the computation of l before the branch is intended to
help even the dimmest compiler see the chance to use the carry
flag from the subtraction for the branch condition.
(I agree that the above contribution to the collective work of
GMPlib is a "work for hire" with copyright owned by the GMPlib
maintainers and/or the FSF as the "hiring party".)
More information about the gmp-devel
mailing list