Move Montgomery reduction algorithm into mp_asm.cpp

Move the inner-most loop of Montgomery into bigint_mul_add_words, in
mp_muladd.cpp

Use bigint_mul_add_words for the inner loop of bigint_simple_multiply

Move the compare/subtract at the end of the Montomgery algorithm into
bigint_monty_redc

5 files changed, 66 insertions, 65 deletions

diff --git a/src/mp_asm.cpp b/src/mp_asm.cpp
index e45a92e2c..88cc8b6e1 100644
--- a/src/mp_asm.cpp
+++ b/src/mp_asm.cpp
@@ -177,23 +177,39 @@ void bigint_linmul3(word z[], const word x[], u32bit x_size, word y)
 void bigint_simple_mul(word z[], const word x[], u32bit x_size,
                                  const word y[], u32bit y_size)
    {
-   const u32bit blocks = y_size - (y_size % 8);
-
    clear_mem(z, x_size + y_size);
 
    for(u32bit j = 0; j != x_size; ++j)
+      z[j+y_size] = bigint_mul_add_words(z + j, y, y_size, x[j]);
+   }
+
+/*************************************************
+* Montgomery Reduction Algorithm                 *
+*************************************************/
+void bigint_monty_redc(word z[], u32bit z_size,
+                       const word x[], u32bit x_size, word u)
+   {
+   for(u32bit j = 0; j != x_size; ++j)
       {
-      const word x_j = x[j];
-      word carry = 0;
+      word* z_j = z + j;
 
-      for(u32bit k = 0; k != blocks; k += 8)
-         carry = word8_madd3(z + j + k, y + k, x_j, carry);
+      const word y = z_j[0] * u;
 
-      for(u32bit k = blocks; k != y_size; ++k)
-         z[j+k] = word_madd3(x_j, y[k], z[j+k], carry, &carry);
+      word carry = bigint_mul_add_words(z_j, x, x_size, y);
 
-      z[j+y_size] = carry;
+      word z_sum = z_j[x_size] + carry;
+      carry = (z_sum < z_j[x_size]);
+      z_j[x_size] = z_sum;
+
+      for(u32bit k = x_size + 1; carry && k != z_size - j; ++k)
+         {
+         ++z_j[k];
+         carry = !z_j[k];
+         }
       }
+
+   if(bigint_cmp(z + x_size, x_size + 1, x, x_size) >= 0)
+      bigint_sub2(z + x_size, x_size + 1, x, x_size);
    }
 
 }
diff --git a/src/mp_monty.cpp b/src/mp_monty.cpp
deleted file mode 100644
index 3347cfa4f..000000000
--- a/src/mp_monty.cpp
+++ /dev/null
@@ -1,49 +0,0 @@
-/*************************************************
-* Montgomery Reduction Source File               *
-* (C) 1999-2006 The Botan Project                *
-*************************************************/
-
-#include <botan/mp_asm.h>
-#include <botan/mp_asmi.h>
-#include <botan/mp_core.h>
-
-namespace Botan {
-
-extern "C" {
-
-/*************************************************
-* Montgomery Reduction Algorithm                 *
-*************************************************/
-void bigint_monty_redc(word z[], u32bit z_size,
-                       const word x[], u32bit x_size, word u)
-   {
-   for(u32bit j = 0; j != x_size; ++j)
-      {
-      word* z_j = z + j;
-
-      const word y = z_j[0] * u;
-      word carry = 0;
-
-      const u32bit blocks = x_size - (x_size % 8);
-
-      for(u32bit k = 0; k != blocks; k += 8)
-         carry = word8_madd3(z_j + k, x + k, y, carry);
-
-      for(u32bit k = blocks; k != x_size; ++k)
-         z_j[k] = word_madd3(x[k], y, z_j[k], carry, &carry);
-
-      word z_sum = z_j[x_size] + carry;
-      carry = (z_sum < z_j[x_size]);
-      z_j[x_size] = z_sum;
-
-      for(u32bit k = x_size + 1; carry && k != z_size - j; ++k)
-         {
-         ++z_j[k];
-         carry = !z_j[k];
-         }
-      }
-   }
-
-}
-
-}
diff --git a/src/mp_muladd.cpp b/src/mp_muladd.cpp
new file mode 100644
index 000000000..715467a88
--- /dev/null
+++ b/src/mp_muladd.cpp
@@ -0,0 +1,34 @@
+/*************************************************
+* Multiply/Add Algorithm Source File             *
+* (C) 1999-2006 The Botan Project                *
+*************************************************/
+
+#include <botan/mp_asm.h>
+#include <botan/mp_asmi.h>
+#include <botan/mp_core.h>
+
+namespace Botan {
+
+extern "C" {
+
+/*************************************************
+* Multiply/Add Words                             *
+*************************************************/
+word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y)
+   {
+   const u32bit blocks = x_size - (x_size % 8);
+
+   word carry = 0;
+
+   for(u32bit j = 0; j != blocks; j += 8)
+      carry = word8_madd3(z + j, x + j, y, carry);
+
+   for(u32bit j = blocks; j != x_size; ++j)
+      z[j] = word_madd3(x[j], y, z[j], carry, &carry);
+
+   return carry;
+   }
+
+}
+
+}
diff --git a/src/mp_shift.cpp b/src/mp_shift.cpp
index a7ed06caa..3233b5408 100644
--- a/src/mp_shift.cpp
+++ b/src/mp_shift.cpp
@@ -45,10 +45,13 @@ void bigint_shr1(word x[], u32bit x_size, u32bit word_shift, u32bit bit_shift)
       return;
       }
 
-   for(u32bit j = 0; j != x_size - word_shift; ++j)
-      x[j] = x[j + word_shift];
-   for(u32bit j = x_size - word_shift; j != x_size; ++j)
-      x[j] = 0;
+   if(word_shift)
+      {
+      for(u32bit j = 0; j != x_size - word_shift; ++j)
+         x[j] = x[j + word_shift];
+      for(u32bit j = x_size - word_shift; j != x_size; ++j)
+         x[j] = 0;
+      }
 
    if(bit_shift)
       {
diff --git a/src/powm_mnt.cpp b/src/powm_mnt.cpp
index 747510d87..9b4916b67 100644
--- a/src/powm_mnt.cpp
+++ b/src/powm_mnt.cpp
@@ -55,9 +55,6 @@ inline void montgomery_reduce(BigInt& out, MemoryRegion<word>& z_buf,
 
    bigint_monty_redc(z, z_size, x, x_size, u);
 
-   if(bigint_cmp(z + x_size, x_size + 1, x, x_size) >= 0)
-      bigint_sub2(z + x_size, x_size + 1, x, x_size);
-
    out.get_reg().set(z + x_size, x_size + 1);
    }