[Gmp-commit] /var/hg/gmp: 2 new changesets

[mercurial at gmplib.org]

details:   /var/hg/gmp/rev/4801183929c4
changeset: 16288:4801183929c4
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Sun Feb 09 22:25:03 2014 +0100
description:
Fixed off-by-one problem in tuning of mpn_sec_powm.

details:   /var/hg/gmp/rev/a0e2c942ea0b
changeset: 16289:a0e2c942ea0b
user:      Niels M?ller <nisse at lysator.liu.se>
date:      Sun Feb 09 22:27:47 2014 +0100
description:
mpn_sec_powm: Delete handling of winsize > initial ebi.

diffstat:

 ChangeLog              |  11 +++++++++++
 mpn/generic/sec_powm.c |  17 ++++++++++++-----
 tune/tuneup.c          |  14 ++++++++++++--
 3 files changed, 35 insertions(+), 7 deletions(-)

diffs (99 lines):

diff -r 3c807e1d8cbf -r a0e2c942ea0b ChangeLog
--- a/ChangeLog	Sun Feb 09 08:23:38 2014 +0100
+++ b/ChangeLog	Sun Feb 09 22:27:47 2014 +0100
@@ -1,3 +1,14 @@
+2014-02-09  Niels Möller  <nisse at lysator.liu.se>
+
+	* tune/tuneup.c (tune_powm_sec): Avoid timing of the nonsensical
+	parameters nbits = 1, winsize = 2. Decrement tabulated values, to
+	better match the > comparison when the table is used.
+
+	* mpn/generic/sec_powm.c (win_size): Comment why we always get
+	win_size(eb) <= eb. Make the table const.
+	(mpn_sec_powm): Deleted handling of winsize > initial ebi. For
+	now, replaced with an ASSERT_ALWAYS.
+
 2014-02-08 Marco Bodrato <bodrato at mail.dm.unipi.it>
 
 	* mini-gmp/mini-gmp.c (mpz_realloc2, mpz_limbs_read, mpz_limbs_modify
diff -r 3c807e1d8cbf -r a0e2c942ea0b mpn/generic/sec_powm.c
--- a/mpn/generic/sec_powm.c	Sun Feb 09 08:23:38 2014 +0100
+++ b/mpn/generic/sec_powm.c	Sun Feb 09 22:27:47 2014 +0100
@@ -183,6 +183,9 @@
 #define getbit(p,bi) \
   ((p[(bi - 1) / GMP_NUMB_BITS] >> (bi - 1) % GMP_NUMB_BITS) & 1)
 
+/* FIXME: Maybe some things would get simpler if all callers ensure
+   that bi >= nbits. As far as I understand, with the current code bi
+   < nbits can happen only for the final iteration. */
 static inline mp_limb_t
 getbits (const mp_limb_t *p, mp_bitcnt_t bi, int nbits)
 {
@@ -222,9 +225,15 @@
 win_size (mp_bitcnt_t eb)
 {
   int k;
-  static mp_bitcnt_t x[] = {0,POWM_SEC_TABLE,~(mp_bitcnt_t)0};
+  /* Find k, such that x[k-1] < eb <= x[k].
+
+     We require that x[k] >= k, then it follows that eb > x[k-1] >=
+     k-1, which implies k <= eb.
+  */
+  static const mp_bitcnt_t x[] = {0,POWM_SEC_TABLE,~(mp_bitcnt_t)0};
   for (k = 1; eb > x[k]; k++)
     ;
+  ASSERT (k <= eb);
   return k;
 }
 #endif
@@ -323,10 +332,8 @@
     }
 
   expbits = getbits (ep, ebi, windowsize);
-  if (ebi < windowsize)
-    ebi = 0;
-  else
-    ebi -= windowsize;
+  ASSERT_ALWAYS (ebi >= windowsize);
+  ebi -= windowsize;
 
   mpn_sec_tabselect (rp, pp, n, 1 << windowsize, expbits);
 
diff -r 3c807e1d8cbf -r a0e2c942ea0b tune/tuneup.c
--- a/tune/tuneup.c	Sun Feb 09 08:23:38 2014 +0100
+++ b/tune/tuneup.c	Sun Feb 09 22:27:47 2014 +0100
@@ -1911,7 +1911,10 @@
 
   printf ("#define POWM_SEC_TABLE  ");
 
-  for (nbits = 1; nbits <= n_max * GMP_NUMB_BITS; )
+  /* For nbits == 1, we should always use k == 1, so no need to tune
+     that. Starting with nbits == 2 also ensure that nbits always is
+     larger than the windowsize k+1. */
+  for (nbits = 2; nbits <= n_max * GMP_NUMB_BITS; )
     {
       n = (nbits - 1) / GMP_NUMB_BITS + 1;
 
@@ -1952,6 +1955,10 @@
 	  if (possible_nbits_cutoff)
 	    {
 	      /* Two consecutive sizes indicate k increase, obey.  */
+
+	      /* Must always have x[k] >= k */
+	      ASSERT_ALWAYS (possible_nbits_cutoff >= k);
+
 	      if (k > 1)
 		printf (",");
 	      printf ("%ld", (long) possible_nbits_cutoff);
@@ -1962,7 +1969,10 @@
 	    {
 	      /* One measurement indicate k increase, save nbits for further
 		 consideration.  */
-	      possible_nbits_cutoff = nbits;
+	      /* The new larger k gets used for sizes > the cutoff
+		 value, hence the cutoff should be one less than the
+		 smallest size where it gives a speedup. */
+	      possible_nbits_cutoff = nbits - 1;
 	    }
 	}
       else