mpi: Add _gcry_mpih_mod.

* mpi/mpi-internal.h (mpih_mod, _gcry_mpih_mod): New.
* mpi/mpih-const-time.c (_gcry_mpih_mod): New.

Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>

2 files changed, 41 insertions, 0 deletions

diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
index fd44c0a8..4111d905 100644
--- a/mpi/mpi-internal.h
+++ b/mpi/mpi-internal.h
@@ -260,6 +260,7 @@ mpi_limb_t _gcry_mpih_rshift( mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
 #define mpih_sub_n_cond(w,u,v,s,o) _gcry_mpih_sub_n_cond ((w),(u),(v),(s),(o))
 #define mpih_swap_cond(u,v,s,o) _gcry_mpih_swap_cond ((u),(v),(s),(o))
 #define mpih_abs_cond(w,u,s,o) _gcry_mpih_abs_cond ((w),(u),(s),(o))
+#define mpih_mod(v,vs,u,us) _gcry_mpih_mod ((v),(vs),(u),(us))
 
 void _gcry_mpih_set_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
                           unsigned long op_enable);
@@ -271,6 +272,8 @@ void _gcry_mpih_swap_cond (mpi_ptr_t up, mpi_ptr_t vp, mpi_size_t usize,
                            unsigned long op_enable);
 void _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up,
                           mpi_size_t usize, unsigned long op_enable);
+mpi_ptr_t _gcry_mpih_mod (mpi_ptr_t vp, mpi_size_t vsize,
+                          mpi_ptr_t up, mpi_size_t usize);
 
 
 /* Define stuff for longlong.h.  */
diff --git a/mpi/mpih-const-time.c b/mpi/mpih-const-time.c
index ea8d5292..d91bf1a9 100644
--- a/mpi/mpih-const-time.c
+++ b/mpi/mpih-const-time.c
@@ -23,6 +23,8 @@
 #include "mpi-internal.h"
 #include "g10lib.h"
 
+#define A_LIMB_1 ((mpi_limb_t)1)
+
 /*
  *  W = U when OP_ENABLED=1
  *  otherwise, W keeps old value
@@ -142,3 +144,39 @@ _gcry_mpih_abs_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize,
       wp[i] = up[i] ^ (mask & (x ^ up[i]));
     }
 }
+
+
+/*
+ * Allocating memory for W,
+ * compute W = V % U, then return W
+ */
+mpi_ptr_t
+_gcry_mpih_mod (mpi_ptr_t vp, mpi_size_t vsize,
+                mpi_ptr_t up, mpi_size_t usize)
+{
+  int secure;
+  mpi_ptr_t rp;
+  mpi_size_t i;
+
+  secure = _gcry_is_secure (vp);
+  rp = mpi_alloc_limb_space (usize, secure);
+  MPN_ZERO (rp, usize);
+
+  for (i = 0; i < vsize * BITS_PER_MPI_LIMB; i++)
+    {
+      unsigned int j = vsize * BITS_PER_MPI_LIMB - 1 - i;
+      unsigned int limbno = j / BITS_PER_MPI_LIMB;
+      unsigned int bitno = j % BITS_PER_MPI_LIMB;
+      mpi_limb_t limb = vp[limbno];
+      unsigned int the_bit = ((limb & (A_LIMB_1 << bitno)) ? 1 : 0);
+      mpi_limb_t underflow;
+
+      _gcry_mpih_lshift (rp, rp, usize, 1);
+      rp[0] |= the_bit;
+
+      underflow = _gcry_mpih_sub_n (rp, rp, up, usize);
+      mpih_add_n_cond (rp, rp, up, usize, underflow);
+    }
+
+  return rp;
+}