[Gmp-commit] /home/hgfiles/gmp: Further mpn_powm, mpn_powm_sec fixes.
mercurial at gmplib.org
mercurial at gmplib.org
Wed Dec 16 19:52:58 CET 2009
details: /home/hgfiles/gmp/rev/2bcc9cdf29da
changeset: 13093:2bcc9cdf29da
user: Torbjorn Granlund <tege at gmplib.org>
date: Wed Dec 16 19:52:54 2009 +0100
description:
Further mpn_powm, mpn_powm_sec fixes.
diffstat:
ChangeLog | 7 +++++++
mpn/generic/powm.c | 46 +++++++++++++++++++++++++++++++++++-----------
mpn/generic/powm_sec.c | 22 ++++++++++++----------
3 files changed, 54 insertions(+), 21 deletions(-)
diffs (199 lines):
diff -r ee417dae4cb4 -r 2bcc9cdf29da ChangeLog
--- a/ChangeLog Wed Dec 16 19:22:57 2009 +0100
+++ b/ChangeLog Wed Dec 16 19:52:54 2009 +0100
@@ -1,3 +1,10 @@
+2009-12-16 Torbjorn Granlund <tege at gmplib.org>
+
+ * mpn/generic/powm.c: Use mp_bitcnt_t for bit counts.
+ Handle REDC_1_TO_REDC_N_THRESHOLD < MUL_TOOM22_THRESHOLD in
+ non-WANT_REDC_2 INNERLOOP expansion code.
+ * mpn/generic/powm_sec.c: Use mp_bitcnt_t for bit counts.
+
2009-12-16 Niels Möller <nisse at lysator.liu.se>
* tests/mpz/t-gcd.c (main): Added test case to exercise the
diff -r ee417dae4cb4 -r 2bcc9cdf29da mpn/generic/powm.c
--- a/mpn/generic/powm.c Wed Dec 16 19:22:57 2009 +0100
+++ b/mpn/generic/powm.c Wed Dec 16 19:52:54 2009 +0100
@@ -81,7 +81,7 @@
((p[(bi - 1) / GMP_LIMB_BITS] >> (bi - 1) % GMP_LIMB_BITS) & 1)
static inline mp_limb_t
-getbits (const mp_limb_t *p, unsigned long bi, int nbits)
+getbits (const mp_limb_t *p, mp_bitcnt_t bi, int nbits)
{
int nbits_in_r;
mp_limb_t r;
@@ -105,10 +105,10 @@
}
static inline int
-win_size (unsigned long eb)
+win_size (mp_bitcnt_t eb)
{
int k;
- static unsigned long x[] = {1,7,25,81,241,673,1793,4609,11521,28161,~0ul};
+ static mp_bitcnt_t x[] = {1,7,25,81,241,673,1793,4609,11521,28161,~0ul};
for (k = 0; eb > x[k]; k++)
;
return k;
@@ -142,7 +142,7 @@
{
mp_limb_t ip[2], *mip;
int cnt;
- long ebi;
+ mp_bitcnt_t ebi;
int windowsize, this_windowsize;
mp_limb_t expbits;
mp_ptr pp, this_pp;
@@ -156,7 +156,7 @@
TMP_MARK;
count_leading_zeros (cnt, ep[en - 1]);
- ebi = en * GMP_LIMB_BITS - cnt;
+ ebi = (mp_bitcnt_t) en * GMP_LIMB_BITS - cnt;
#if 0
if (bn < n)
@@ -243,9 +243,10 @@
}
expbits = getbits (ep, ebi, windowsize);
- ebi -= windowsize;
- if (ebi < 0)
+ if (ebi < windowsize)
ebi = 0;
+ else
+ ebi -= windowsize;
count_trailing_zeros (cnt, expbits);
ebi += cnt;
@@ -270,13 +271,14 @@
significant bit is 1. */ \
\
expbits = getbits (ep, ebi, windowsize); \
- ebi -= windowsize; \
this_windowsize = windowsize; \
- if (ebi < 0) \
+ if (ebi < windowsize) \
{ \
- this_windowsize += ebi; \
+ this_windowsize -= windowsize - ebi; \
ebi = 0; \
} \
+ else \
+ ebi -= windowsize; \
\
count_trailing_zeros (cnt, expbits); \
this_windowsize -= cnt; \
@@ -362,7 +364,28 @@
}
#else /* WANT_REDC_2 */
-
+#if REDC_1_TO_REDC_N_THRESHOLD < MUL_TOOM22_THRESHOLD
+ if (BELOW_THRESHOLD (n, REDC_1_TO_REDC_N_THRESHOLD))
+ {
+#undef MPN_MUL_N
+#undef MPN_SQR_N
+#undef MPN_REDUCE
+#define MPN_MUL_N(r,a,b,n) mpn_mul_basecase (r,a,n,b,n)
+#define MPN_SQR_N(r,a,n) mpn_sqr_basecase (r,a,n)
+#define MPN_REDUCE(rp,tp,mp,n,mip) mpn_redc_1 (rp, tp, mp, n, mip[0])
+ INNERLOOP;
+ }
+ else if (BELOW_THRESHOLD (n, MUL_TOOM22_THRESHOLD))
+ {
+#undef MPN_MUL_N
+#undef MPN_SQR_N
+#undef MPN_REDUCE
+#define MPN_MUL_N(r,a,b,n) mpn_mul_basecase (r,a,n,b,n)
+#define MPN_SQR_N(r,a,n) mpn_sqr_basecase (r,a,n)
+#define MPN_REDUCE(rp,tp,mp,n,mip) mpn_redc_n (rp, tp, mp, n, mip)
+ INNERLOOP;
+ }
+#else
if (BELOW_THRESHOLD (n, MUL_TOOM22_THRESHOLD))
{
#undef MPN_MUL_N
@@ -383,6 +406,7 @@
#define MPN_REDUCE(rp,tp,mp,n,mip) mpn_redc_1 (rp, tp, mp, n, mip[0])
INNERLOOP;
}
+#endif
else
{
#undef MPN_MUL_N
diff -r ee417dae4cb4 -r 2bcc9cdf29da mpn/generic/powm_sec.c
--- a/mpn/generic/powm_sec.c Wed Dec 16 19:22:57 2009 +0100
+++ b/mpn/generic/powm_sec.c Wed Dec 16 19:52:54 2009 +0100
@@ -160,7 +160,7 @@
((p[(bi - 1) / GMP_LIMB_BITS] >> (bi - 1) % GMP_LIMB_BITS) & 1)
static inline mp_limb_t
-getbits (const mp_limb_t *p, unsigned long bi, int nbits)
+getbits (const mp_limb_t *p, mp_bitcnt_t bi, int nbits)
{
int nbits_in_r;
mp_limb_t r;
@@ -184,10 +184,10 @@
}
static inline int
-win_size (unsigned long eb)
+win_size (mp_bitcnt_t eb)
{
int k;
- static unsigned long x[] = {1,4,27,100,325,1026,2905,7848,20457,51670,~0ul};
+ static mp_bitcnt_t x[] = {1,4,27,100,325,1026,2905,7848,20457,51670,~0ul};
for (k = 0; eb > x[k]; k++)
;
return k;
@@ -221,7 +221,7 @@
{
mp_limb_t minv;
int cnt;
- long ebi;
+ mp_bitcnt_t ebi;
int windowsize, this_windowsize;
mp_limb_t expbits;
mp_ptr pp, this_pp;
@@ -235,7 +235,7 @@
TMP_MARK;
count_leading_zeros (cnt, ep[en - 1]);
- ebi = en * GMP_LIMB_BITS - cnt;
+ ebi = (mp_bitcnt_t) en * GMP_LIMB_BITS - cnt;
windowsize = win_size (ebi);
@@ -259,22 +259,24 @@
}
expbits = getbits (ep, ebi, windowsize);
- ebi -= windowsize;
- if (ebi < 0)
+ if (ebi < windowsize)
ebi = 0;
+ else
+ ebi -= windowsize;
MPN_COPY (rp, pp + n * expbits, n);
while (ebi != 0)
{
expbits = getbits (ep, ebi, windowsize);
- ebi -= windowsize;
this_windowsize = windowsize;
- if (ebi < 0)
+ if (ebi < windowsize)
{
- this_windowsize += ebi;
+ this_windowsize -= windowsize - ebi;
ebi = 0;
}
+ else
+ ebi -= windowsize;
do
{
More information about the gmp-commit
mailing list