Add an x86 assembly implementation of bigint_mul_add_words, which is

the core loop of bigint_monty_redc.

4 files changed, 134 insertions, 3 deletions

diff --git a/modules/alg_ia32/asm_macr.h b/modules/alg_ia32/asm_macr.h
index faa55aa96..8b2224103 100644
--- a/modules/alg_ia32/asm_macr.h
+++ b/modules/alg_ia32/asm_macr.h
@@ -40,9 +40,20 @@ func_name:
    cmpl IMM(NUM), REG;                 \
    jne LABEL##_LOOP
 
-#define LOOP_UNTIL(REG, NUM, LABEL) \
-   cmpl NUM, REG;                   \
-   jne LABEL##_LOOP
+#define LOOP_UNTIL_LT(REG, NUM, LABEL) \
+   cmpl IMM(NUM), REG;                 \
+   jge LABEL##_LOOP
+
+/*************************************************
+ Conditional Jumps                              *
+*************************************************/
+#define JUMP_IF_ZERO(REG, LABEL) \
+   cmpl IMM(0), REG;             \
+   jz LABEL
+
+#define JUMP_IF_LT(REG, NUM, LABEL) \
+   cmpl IMM(NUM), REG;              \
+   jl LABEL
 
 /*************************************************
 * Register Names                                 *
@@ -89,9 +100,11 @@ func_name:
 
 #define ADD(TO, FROM) addl FROM, TO
 #define ADD_IMM(TO, NUM) addl IMM(NUM), TO
+#define ADD_W_CARRY(TO1, TO2, FROM) addl FROM, TO1; adcl IMM(0), TO2;
 #define SUB_IMM(TO, NUM) subl IMM(NUM), TO
 #define ADD2_IMM(TO, FROM, NUM) leal NUM(FROM), TO
 #define ADD3_IMM(TO, FROM, NUM) leal NUM(TO,FROM,1), TO
+#define MUL(REG) mull REG
 
 #define CLEAR_CARRY() clc
 
diff --git a/modules/alg_ia32/modinfo.txt b/modules/alg_ia32/modinfo.txt
index 02581578f..285137fda 100644
--- a/modules/alg_ia32/modinfo.txt
+++ b/modules/alg_ia32/modinfo.txt
@@ -4,6 +4,7 @@ replace_file md4.cpp
 replace_file md5.cpp
 replace_file sha160.cpp
 replace_file serpent.cpp
+replace_file mp_monty.cpp
 
 add_file asm_macr.h
 
@@ -11,6 +12,7 @@ add_file md4core.S
 add_file md5core.S
 add_file sha1core.S
 add_file serp_asm.S
+add_file mp_muladd.S
 
 <arch>
 ia32
diff --git a/modules/alg_ia32/mp_monty.cpp b/modules/alg_ia32/mp_monty.cpp
new file mode 100644
index 000000000..90bf71e56
--- /dev/null
+++ b/modules/alg_ia32/mp_monty.cpp
@@ -0,0 +1,44 @@
+/*************************************************
+* 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" word bigint_mul_add_words(word[], const word[], u32bit, word);
+
+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 = bigint_mul_add_words(z_j, x, x_size, y);
+
+      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/modules/alg_ia32/mp_muladd.S b/modules/alg_ia32/mp_muladd.S
new file mode 100644
index 000000000..9196ef7f1
--- /dev/null
+++ b/modules/alg_ia32/mp_muladd.S
@@ -0,0 +1,72 @@
+
+#include <botan/asm_macr.h>
+
+START_LISTING(mp_muladd.S)
+
+/*
+word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y)
+   {
+   word carry = 0;
+
+   for(u32bit j = 0; j != x_size; ++j)
+      {
+      u64bit zx = (u64bit)x[j] * y + z[j] + carry;
+      z[j] = (word)zx;
+      carry = (word)(zx >> BOTAN_MP_WORD_BITS);
+      }
+
+   return carry;
+   }
+*/
+START_FUNCTION(bigint_mul_add_words)
+   SPILL_REGS()
+#define PUSHED 4
+
+   ASSIGN(EBX, ARG(2)) /* x[] */
+   ASSIGN(ECX, ARG(1)) /* z[] */
+   ASSIGN(ESI, ARG(3)) /* x_size */
+   ASSIGN(EBP, ARG(4)) /* y */
+   ZEROIZE(EDI)
+
+#define MULADD_OP(N)                       \
+   ASSIGN(EAX, ARRAY4(EBX, N))           ; \
+   MUL(EBP)                              ; \
+   ADD_W_CARRY(EAX, EDX, EDI)            ; \
+   ADD_W_CARRY(EAX, EDX, ARRAY4(ECX, N)) ; \
+   ASSIGN(ARRAY4(ECX, N), EAX)           ; \
+   ASSIGN(EDI, EDX)                      ;
+
+   JUMP_IF_ZERO(ESI, .MUL_ADD_DONE)
+   JUMP_IF_LT(ESI, 8, .MULADD1_LOOP)
+
+START_LOOP(.MULADD8)
+   MULADD_OP(0)
+   MULADD_OP(1)
+   MULADD_OP(2)
+   MULADD_OP(3)
+   MULADD_OP(4)
+   MULADD_OP(5)
+   MULADD_OP(6)
+   MULADD_OP(7)
+
+   SUB_IMM(ESI, 8)
+   ADD_IMM(EBX, 32)
+   ADD_IMM(ECX, 32)
+LOOP_UNTIL_LT(ESI, 8, .MULADD8)
+
+   JUMP_IF_ZERO(ESI, .MUL_ADD_DONE)
+
+START_LOOP(.MULADD1)
+   MULADD_OP(0)
+
+   SUB_IMM(ESI, 1)
+   ADD_IMM(EBX, 4)
+   ADD_IMM(ECX, 4)
+LOOP_UNTIL_EQ(ESI, 0, .MULADD1)
+
+.MUL_ADD_DONE:
+
+   ASSIGN(EAX, EDI)
+#undef PUSHED
+   RESTORE_REGS()
+END_FUNCTION(bigint_mul_add_words)