This is an automated email from the git hooks/post-receive script. ppm-guest pushed a commit to annotated tag v0.32 in repository libmath-prime-util-perl.
commit 2b325866b976864f33614f553e1f0655c8ce964b Author: Dana Jacobsen <d...@acm.org> Date: Thu Sep 12 10:26:34 2013 -0700 standardize variable names --- mulmod.h | 120 +++++++++++++++++++++++++++++++++------------------------------ 1 file changed, 63 insertions(+), 57 deletions(-) diff --git a/mulmod.h b/mulmod.h index 7f263a9..2eff302 100644 --- a/mulmod.h +++ b/mulmod.h @@ -19,38 +19,36 @@ /* We have 64-bit available, but UV is 32-bit. Do the math in 64-bit. * Even if it is emulated, it should be as fast or faster than us doing it. */ - #define addmod(n,a,m) (UV)(((uint64_t)(n)+(uint64_t)(a)) % ((uint64_t)(m))) - #define mulmod(a,b,m) (UV)(((uint64_t)(a)*(uint64_t)(b)) % ((uint64_t)(m))) - #define sqrmod(n,m) (UV)(((uint64_t)(n)*(uint64_t)(n)) % ((uint64_t)(m))) + #define addmod(a,b,n) (UV)( ((uint64_t)(a) + (b)) % (n) ) + #define mulmod(a,b,n) (UV)( ((uint64_t)(a) * (b)) % (n) ) + #define sqrmod(a,n) (UV)( ((uint64_t)(a) * (a)) % (n) ) #elif defined(__GNUC__) && defined(__x86_64__) /* GCC on a 64-bit Intel x86, help from WraithX and Wojciech Izykowski */ /* Beware: if (a*b)/c > 2^64, there will be an FP exception */ - static INLINE UV _mulmod(UV a, UV b, UV c) { + static INLINE UV _mulmod(UV a, UV b, UV n) { UV d, dummy; /* d will get a*b mod c */ asm ("mulq %3\n\t" /* mul a*b -> rdx:rax */ "divq %4\n\t" /* (a*b)/c -> quot in rax remainder in rdx */ :"=a"(dummy), "=&d"(d) /* output */ - :"a"(a), "rm"(b), "rm"(c) /* input */ + :"a"(a), "rm"(b), "rm"(n) /* input */ :"cc" /* mulq and divq can set conditions */ ); - /* A version for _MSC_VER: - * - * __asm { mov rax, qword ptr a - * mul qword ptr b - * div qword ptr c - * mov qword ptr d, rdx } - */ return d; } - #define mulmod(a,b,m) _mulmod(a,b,m) - #define sqrmod(n,m) _mulmod(n,n,m) + #define mulmod(a,b,n) _mulmod(a,b,n) + #define sqrmod(a,n) _mulmod(a,a,n) + /* A version for _MSC_VER: + * __asm { mov rax, qword ptr a + * mul qword ptr b + * div qword ptr c + * mov qword ptr d, rdx } */ /* addmod from Kruppa 2010 page 67 */ - static INLINE UV _addmod(UV a, UV b, UV m) { + static INLINE UV _addmod(UV a, UV b, UV n) { UV r = a+b; - UV t = a-m; + UV t = a-n; asm ("add %2, %1\n\t" /* t := t + b */ "cmovc %1, %0\n\t" /* if (carry) r := t */ :"+r" (r), "+&r" (t) @@ -72,84 +70,92 @@ typedef unsigned __int128 uint128_t; #endif - #define mulmod(a,b,m) (UV)(((uint128_t)(a)*(uint128_t)(b)) % ((uint128_t)(m))) - #define sqrmod(n,m) (UV)(((uint128_t)(n)*(uint128_t)(n)) % ((uint128_t)(m))) + #define mulmod(a,b,n) (UV)( ((uint128_t)(a) * (b)) % (n) ) + #define sqrmod(a,n) (UV)( ((uint128_t)(a) * (a)) % (n) ) #else /* UV is the largest integral type available (that we know of). */ /* Do it by hand */ - static INLINE UV _mulmod(UV a, UV b, UV m) { + static INLINE UV _mulmod(UV a, UV b, UV n) { UV r = 0; - if (a >= m) a %= m; /* Careful attention from the caller should make */ - if (b >= m) b %= m; /* these unnecessary. */ + if (a >= n) a %= n; /* Careful attention from the caller should make */ + if (b >= n) b %= n; /* these unnecessary. */ if (a < b) { UV t = a; a = b; b = t; } - while (b > 0) { - if (b & 1) r = ((m-r) > a) ? r+a : r+a-m; /* r = (r + a) % m */ - b >>= 1; - if (b) a = ((m-a) > a) ? a+a : a+a-m; /* a = (a + a) % m */ + if (n <= (UV_MAX>>1)) { + while (b > 0) { + if (b & 1) { r += a; if (r >= n) r -= n; } + b >>= 1; + if (b) { a += a; if (a >= n) a -= n; } + } + } else { + while (b > 0) { + if (b & 1) r = ((n-r) > a) ? r+a : r+a-n; /* r = (r + a) % n */ + b >>= 1; + if (b) a = ((n-a) > a) ? a+a : a+a-n; /* a = (a + a) % n */ + } } return r; } - #define mulmod(a,b,m) (((a)|(b)) < HALF_WORD) ? ((a)*(b))%(m):_mulmod(a,b,m) - #define sqrmod(n,m) ((n) < HALF_WORD) ? ((n)*(n))%(m):_mulmod(n,n,m) + #define mulmod(a,b,n) ((((a)|(b)) < HALF_WORD) ? ((a)*(b))%(n):_mulmod(a,b,n)) + #define sqrmod(a,n) (((a) < HALF_WORD) ? ((a)*(a))%(n):_mulmod(a,a,n)) #endif #ifndef addmod - #define addmod(a,b,m) ((((m)-(a)) > (b)) ? ((a)+(b)) : ((a)+(b)-(m))) + #define addmod(a,b,n) ((((n)-(a)) > (b)) ? ((a)+(b)) : ((a)+(b)-(n))) #endif /* We need to make sure a and b get evaluated into UVs, then do the * subtract into a UV before the addmod. */ -static INLINE UV submod(UV a, UV b, UV m) { - UV t1 = m - b; - return addmod(a, t1, m); +static INLINE UV submod(UV a, UV b, UV n) { + UV t1 = n - b; + return addmod(a, t1, n); } -/* n^2 + a mod m */ -#define sqraddmod(n, a, m) addmod(sqrmod(n,m), a,m) -/* i*j + a mod m */ -#define muladdmod(i, j, a, m) addmod(mulmod(i,j,m), a, m) -/* i*j - a mod m */ -#define mulsubmod(i, j, a, m) submod(mulmod(i,j,m), a, m) +/* a^2 + c mod n */ +#define sqraddmod(a, c, n) addmod(sqrmod(a,n), c, n) +/* a*b + c mod n */ +#define muladdmod(a, b, c, n) addmod(mulmod(a,b,n), c, n) +/* a*b - c mod n */ +#define mulsubmod(a, b, c, n) submod(mulmod(a,b,n), c, n) -/* n^power mod m */ +/* a^k mod n */ #ifndef HALF_WORD - static INLINE UV powmod(UV n, UV power, UV m) { + static INLINE UV powmod(UV a, UV k, UV n) { UV t = 1; - if (n >= m) n %= m; - while (power) { - if (power & 1) t = mulmod(t, n, m); - power >>= 1; - if (power) n = sqrmod(n, m); + if (a >= n) a %= n; + while (k) { + if (k & 1) t = mulmod(t, a, n); + k >>= 1; + if (k) a = sqrmod(a, n); } return t; } #else - static INLINE UV powmod(UV n, UV power, UV m) { + static INLINE UV powmod(UV a, UV k, UV n) { UV t = 1; - if (n >= m) n %= m; - if (m < HALF_WORD) { - while (power) { - if (power & 1) t = (t*n)%m; - power >>= 1; - if (power) n = (n*n)%m; + if (a >= n) a %= n; + if (n < HALF_WORD) { + while (k) { + if (k & 1) t = (t*a)%n; + k >>= 1; + if (k) a = (a*a)%n; } } else { - while (power) { - if (power & 1) t = mulmod(t, n, m); - power >>= 1; - if (power) n = sqrmod(n,m); + while (k) { + if (k & 1) t = mulmod(t, a, n); + k >>= 1; + if (k) a = sqrmod(a, n); } } return t; } #endif -/* n^power + a mod m */ -#define powaddmod(n, p, a, m) addmod(powmod(n,p,m),a,m) +/* a^k + c mod n */ +#define powaddmod(a, k, c, n) addmod(powmod(a,k,n),c,n) #endif -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git _______________________________________________ Pkg-perl-cvs-commits mailing list Pkg-perl-cvs-commits@lists.alioth.debian.org http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits