mpi: Revise mpi_powm.
authorNIIBE Yutaka <gniibe@fsij.org>
Wed, 11 Feb 2015 13:30:02 +0000 (22:30 +0900)
committerNIIBE Yutaka <gniibe@fsij.org>
Fri, 27 Feb 2015 05:03:57 +0000 (14:03 +0900)
* mpi/mpi-pow.c (_gcry_mpi_powm): Rename the table to PRECOMP.

--

The name of precomputed table was b_2i3 which stands for BASE^(2*I+3).
But it's too cryptic, so, it's renamed.  Besides, we needed to
distinguish the case of I==0, that was not good.  Since it's OK to
increase the size of table by one, it's BASE^(2*I+1), now.

mpi/mpi-pow.c

index 0f0947f..930d344 100644 (file)
@@ -381,7 +381,7 @@ mul_mod (mpi_ptr_t xp, mpi_size_t *xsize_p,
      *xsize_p = rsize + ssize;
 }
 
-#define SIZE_B_2I3 ((1 << (5 - 1)) - 1)
+#define SIZE_PRECOMP ((1 << (5 - 1)))
 
 /****************
  * RES = BASE ^ EXPO mod MOD
@@ -417,8 +417,8 @@ _gcry_mpi_powm (gcry_mpi_t res,
   unsigned int bp_nlimbs = 0;
   unsigned int ep_nlimbs = 0;
   unsigned int xp_nlimbs = 0;
-  mpi_ptr_t b_2i3[SIZE_B_2I3]; /* Pre-computed array: BASE^3, ^5, ^7, ... */
-  mpi_size_t b_2i3size[SIZE_B_2I3];
+  mpi_ptr_t precomp[SIZE_PRECOMP]; /* Pre-computed array: BASE^1, ^3, ^5, ... */
+  mpi_size_t precomp_size[SIZE_PRECOMP];
   mpi_size_t W;
   mpi_ptr_t base_u;
   mpi_size_t base_u_size;
@@ -555,31 +555,23 @@ _gcry_mpi_powm (gcry_mpi_t res,
     memset( &karactx, 0, sizeof karactx );
     negative_result = (ep[0] & 1) && bsign;
 
-    /* Precompute B_2I3[], BASE^(2 * i + 3), BASE^3, ^5, ^7, ... */
+    /* Precompute PRECOMP[], BASE^(2 * i + 1), BASE^1, ^3, ^5, ... */
     if (W > 1)                  /* X := BASE^2 */
       mul_mod (xp, &xsize, bp, bsize, bp, bsize, mp, msize, &karactx);
-    for (i = 0; i < (1 << (W - 1)) - 1; i++)
-      {                         /* B_2I3[i] = BASE^(2 * i + 3) */
-        if (i == 0)
-          {
-            base_u = bp;
-            base_u_size = bsize;
-          }
-        else
-          {
-            base_u = b_2i3[i-1];
-            base_u_size = b_2i3size[i-1];
-          }
-
+    base_u = precomp[0] = mpi_alloc_limb_space (bsize, esec);
+    base_u_size = precomp_size[0] = bsize;
+    MPN_COPY (precomp[0], bp, bsize);
+    for (i = 1; i < (1 << (W - 1)); i++)
+      {                         /* PRECOMP[i] = BASE^(2 * i + 1) */
         if (xsize >= base_u_size)
           mul_mod (rp, &rsize, xp, xsize, base_u, base_u_size,
                    mp, msize, &karactx);
         else
           mul_mod (rp, &rsize, base_u, base_u_size, xp, xsize,
                    mp, msize, &karactx);
-        b_2i3[i] = mpi_alloc_limb_space (rsize, esec);
-        b_2i3size[i] = rsize;
-        MPN_COPY (b_2i3[i], rp, rsize);
+        base_u = precomp[i] = mpi_alloc_limb_space (rsize, esec);
+        base_u_size = precomp_size[i] = rsize;
+        MPN_COPY (precomp[i], rp, rsize);
       }
 
     i = esize - 1;
@@ -667,16 +659,8 @@ _gcry_mpi_powm (gcry_mpi_t res,
               rsize = xsize;
             }
 
-          if (e0 == 0)
-            {
-              base_u = bp;
-              base_u_size = bsize;
-            }
-          else
-            {
-              base_u = b_2i3[e0 - 1];
-              base_u_size = b_2i3size[e0 -1];
-            }
+         base_u = precomp[e0];
+         base_u_size = precomp_size[e0];
 
           mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
                    mp, msize, &karactx);
@@ -703,16 +687,8 @@ _gcry_mpi_powm (gcry_mpi_t res,
 
     if (e != 0)
       {
-        if ((e>>1) == 0)
-          {
-            base_u = bp;
-            base_u_size = bsize;
-          }
-        else
-          {
-            base_u = b_2i3[(e>>1) - 1];
-            base_u_size = b_2i3size[(e>>1) -1];
-          }
+       base_u = precomp[(e>>1)];
+       base_u_size = precomp_size[(e>>1)];
 
         mul_mod (xp, &xsize, rp, rsize, base_u, base_u_size,
                  mp, msize, &karactx);
@@ -761,8 +737,8 @@ _gcry_mpi_powm (gcry_mpi_t res,
     MPN_NORMALIZE (rp, rsize);
 
     _gcry_mpih_release_karatsuba_ctx (&karactx );
-    for (i = 0; i < (1 << (W - 1)) - 1; i++)
-      _gcry_mpi_free_limb_space( b_2i3[i], esec ? b_2i3size[i] : 0 );
+    for (i = 0; i < (1 << (W - 1)); i++)
+      _gcry_mpi_free_limb_space( precomp[i], esec ? precomp_size[i] : 0 );
   }
 
   /* Fixup for negative results.  */