Inline the contents of mp_core.cpp

2 files changed, 429 insertions, 601 deletions

diff --git a/src/lib/math/mp/mp_core.cpp b/src/lib/math/mp/mp_core.cpp
deleted file mode 100644
index 5dbf3558a..000000000
--- a/src/lib/math/mp/mp_core.cpp
+++ /dev/null
@@ -1,549 +0,0 @@
-/*
-* MPI Add, Subtract, Word Multiply
-* (C) 1999-2010,2016 Jack Lloyd
-*     2006 Luca Piccarreta
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#include <botan/internal/mp_core.h>
-#include <botan/internal/mp_asmi.h>
-#include <botan/internal/ct_utils.h>
-#include <botan/exceptn.h>
-#include <botan/mem_ops.h>
-
-namespace Botan {
-
-/*
-* If cond == 0, does nothing.
-* If cond > 0, swaps x[0:size] with y[0:size]
-* Runs in constant time
-*/
-void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
-   {
-   const word mask = CT::expand_mask(cnd);
-
-   for(size_t i = 0; i != size; ++i)
-      {
-      const word a = x[i];
-      const word b = y[i];
-      x[i] = CT::select(mask, b, a);
-      y[i] = CT::select(mask, a, b);
-      }
-   }
-
-/*
-* If cond > 0 adds x[0:size] to y[0:size] and returns carry
-* Runs in constant time
-*/
-word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
-   {
-   const word mask = CT::expand_mask(cnd);
-
-   word carry = 0;
-
-   const size_t blocks = size - (size % 8);
-   word z[8] = { 0 };
-
-   for(size_t i = 0; i != blocks; i += 8)
-      {
-      carry = word8_add3(z, x + i, y + i, carry);
-
-      for(size_t j = 0; j != 8; ++j)
-         x[i+j] = CT::select(mask, z[j], x[i+j]);
-      }
-
-   for(size_t i = blocks; i != size; ++i)
-      {
-      z[0] = word_add(x[i], y[i], &carry);
-      x[i] = CT::select(mask, z[0], x[i]);
-      }
-
-   return carry & mask;
-   }
-
-/*
-* If cond > 0 subs x[0:size] to y[0:size] and returns borrow
-* Runs in constant time
-*/
-word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
-   {
-   const word mask = CT::expand_mask(cnd);
-
-   word carry = 0;
-
-   const size_t blocks = size - (size % 8);
-   word z[8] = { 0 };
-
-   for(size_t i = 0; i != blocks; i += 8)
-      {
-      carry = word8_sub3(z, x + i, y + i, carry);
-
-      for(size_t j = 0; j != 8; ++j)
-         x[i+j] = CT::select(mask, z[j], x[i+j]);
-      }
-
-   for(size_t i = blocks; i != size; ++i)
-      {
-      z[0] = word_sub(x[i], y[i], &carry);
-      x[i] = CT::select(mask, z[0], x[i]);
-      }
-
-   return carry & mask;
-   }
-
-void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
-   {
-   const size_t blocks = size - (size % 8);
-
-   word carry = 0;
-   word borrow = 0;
-
-   word t0[8] = { 0 };
-   word t1[8] = { 0 };
-
-   for(size_t i = 0; i != blocks; i += 8)
-      {
-      carry = word8_add3(t0, x + i, y + i, carry);
-      borrow = word8_sub3(t1, x + i, y + i, borrow);
-
-      for(size_t j = 0; j != 8; ++j)
-         x[i+j] = CT::select(mask, t0[j], t1[j]);
-      }
-
-   for(size_t i = blocks; i != size; ++i)
-      {
-      const word a = word_add(x[i], y[i], &carry);
-      const word s = word_sub(x[i], y[i], &borrow);
-
-      x[i] = CT::select(mask, a, s);
-      }
-   }
-
-void bigint_cnd_abs(word cnd, word x[], size_t size)
-   {
-   const word mask = CT::expand_mask(cnd);
-
-   word carry = mask & 1;
-   for(size_t i = 0; i != size; ++i)
-      {
-      const word z = word_add(~x[i], 0, &carry);
-      x[i] = CT::select(mask, z, x[i]);
-      }
-   }
-
-/*
-* Two Operand Addition, No Carry
-*/
-word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
-   {
-   word carry = 0;
-
-   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
-
-   const size_t blocks = y_size - (y_size % 8);
-
-   for(size_t i = 0; i != blocks; i += 8)
-      carry = word8_add2(x + i, y + i, carry);
-
-   for(size_t i = blocks; i != y_size; ++i)
-      x[i] = word_add(x[i], y[i], &carry);
-
-   for(size_t i = y_size; i != x_size; ++i)
-      x[i] = word_add(x[i], 0, &carry);
-
-   return carry;
-   }
-
-/*
-* Three Operand Addition, No Carry
-*/
-word bigint_add3_nc(word z[], const word x[], size_t x_size,
-                              const word y[], size_t y_size)
-   {
-   if(x_size < y_size)
-      { return bigint_add3_nc(z, y, y_size, x, x_size); }
-
-   word carry = 0;
-
-   const size_t blocks = y_size - (y_size % 8);
-
-   for(size_t i = 0; i != blocks; i += 8)
-      carry = word8_add3(z + i, x + i, y + i, carry);
-
-   for(size_t i = blocks; i != y_size; ++i)
-      z[i] = word_add(x[i], y[i], &carry);
-
-   for(size_t i = y_size; i != x_size; ++i)
-      z[i] = word_add(x[i], 0, &carry);
-
-   return carry;
-   }
-
-/*
-* Two Operand Addition
-*/
-void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
-   {
-   x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
-   }
-
-/*
-* Three Operand Addition
-*/
-void bigint_add3(word z[], const word x[], size_t x_size,
-                           const word y[], size_t y_size)
-   {
-   z[x_size > y_size ? x_size : y_size] +=
-      bigint_add3_nc(z, x, x_size, y, y_size);
-   }
-
-/*
-* Two Operand Subtraction
-*/
-word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
-   {
-   word borrow = 0;
-
-   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
-
-   const size_t blocks = y_size - (y_size % 8);
-
-   for(size_t i = 0; i != blocks; i += 8)
-      borrow = word8_sub2(x + i, y + i, borrow);
-
-   for(size_t i = blocks; i != y_size; ++i)
-      x[i] = word_sub(x[i], y[i], &borrow);
-
-   for(size_t i = y_size; i != x_size; ++i)
-      x[i] = word_sub(x[i], 0, &borrow);
-
-   return borrow;
-   }
-
-/*
-* Two Operand Subtraction x = y - x
-*/
-void bigint_sub2_rev(word x[],  const word y[], size_t y_size)
-   {
-   word borrow = 0;
-
-   const size_t blocks = y_size - (y_size % 8);
-
-   for(size_t i = 0; i != blocks; i += 8)
-      borrow = word8_sub2_rev(x + i, y + i, borrow);
-
-   for(size_t i = blocks; i != y_size; ++i)
-      x[i] = word_sub(y[i], x[i], &borrow);
-
-   BOTAN_ASSERT(!borrow, "y must be greater than x");
-   }
-
-word bigint_sub_abs(word z[],
-                    const word x[], const word y[], size_t N,
-                    word ws[])
-   {
-   // Subtract in both direction then conditional copy out the result
-
-   word* ws0 = ws;
-   word* ws1 = ws + N;
-
-   word borrow0 = 0;
-   word borrow1 = 0;
-
-   const size_t blocks = N - (N % 8);
-
-   for(size_t i = 0; i != blocks; i += 8)
-      {
-      borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
-      borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
-      }
-
-   for(size_t i = blocks; i != N; ++i)
-      {
-      ws0[i] = word_sub(x[i], y[i], &borrow0);
-      ws1[i] = word_sub(y[i], x[i], &borrow1);
-      }
-
-   word mask = CT::conditional_copy_mem(borrow1, z, ws0, ws1, N);
-
-   return CT::select<word>(mask, 0, 1);
-   }
-
-/*
-* Three Operand Subtraction
-*/
-word bigint_sub3(word z[], const word x[], size_t x_size,
-                           const word y[], size_t y_size)
-   {
-   word borrow = 0;
-
-   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
-
-   const size_t blocks = y_size - (y_size % 8);
-
-   for(size_t i = 0; i != blocks; i += 8)
-      borrow = word8_sub3(z + i, x + i, y + i, borrow);
-
-   for(size_t i = blocks; i != y_size; ++i)
-      z[i] = word_sub(x[i], y[i], &borrow);
-
-   for(size_t i = y_size; i != x_size; ++i)
-      z[i] = word_sub(x[i], 0, &borrow);
-
-   return borrow;
-   }
-
-/*
-* Two Operand Linear Multiply
-*/
-void bigint_linmul2(word x[], size_t x_size, word y)
-   {
-   const size_t blocks = x_size - (x_size % 8);
-
-   word carry = 0;
-
-   for(size_t i = 0; i != blocks; i += 8)
-      carry = word8_linmul2(x + i, y, carry);
-
-   for(size_t i = blocks; i != x_size; ++i)
-      x[i] = word_madd2(x[i], y, &carry);
-
-   x[x_size] = carry;
-   }
-
-/*
-* Three Operand Linear Multiply
-*/
-void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
-   {
-   const size_t blocks = x_size - (x_size % 8);
-
-   word carry = 0;
-
-   for(size_t i = 0; i != blocks; i += 8)
-      carry = word8_linmul3(z + i, x + i, y, carry);
-
-   for(size_t i = blocks; i != x_size; ++i)
-      z[i] = word_madd2(x[i], y, &carry);
-
-   z[x_size] = carry;
-   }
-
-/*
-* Single Operand Left Shift
-*/
-void bigint_shl1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
-   {
-   if(word_shift)
-      {
-      copy_mem(x + word_shift, x, x_size);
-      clear_mem(x, word_shift);
-      }
-
-   if(bit_shift)
-      {
-      word carry = 0;
-      for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
-         {
-         word temp = x[j];
-         x[j] = (temp << bit_shift) | carry;
-         carry = (temp >> (BOTAN_MP_WORD_BITS - bit_shift));
-         }
-      }
-   }
-
-namespace {
-
-void bigint_shift_right_1(word x[], size_t x_size)
-   {
-   word carry = 0;
-   size_t top = x_size;
-
-   while(top)
-      {
-      word w = x[top-1];
-      x[top-1] = (w >> 1) | carry;
-      carry = (w << (BOTAN_MP_WORD_BITS - 1));
-
-      top--;
-      }
-   }
-
-}
-
-/*
-* Single Operand Right Shift
-*/
-void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
-   {
-   if(word_shift == 0 && bit_shift == 1)
-      return bigint_shift_right_1(x, x_size);
-
-   if(x_size < word_shift)
-      {
-      clear_mem(x, x_size);
-      return;
-      }
-
-   if(word_shift)
-      {
-      copy_mem(x, x + word_shift, x_size - word_shift);
-      clear_mem(x + x_size - word_shift, word_shift);
-      }
-
-   if(bit_shift)
-      {
-      word carry = 0;
-
-      size_t top = x_size - word_shift;
-
-      while(top >= 4)
-         {
-         word w = x[top-1];
-         x[top-1] = (w >> bit_shift) | carry;
-         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
-
-         w = x[top-2];
-         x[top-2] = (w >> bit_shift) | carry;
-         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
-
-         w = x[top-3];
-         x[top-3] = (w >> bit_shift) | carry;
-         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
-
-         w = x[top-4];
-         x[top-4] = (w >> bit_shift) | carry;
-         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
-
-         top -= 4;
-         }
-
-      while(top)
-         {
-         word w = x[top-1];
-         x[top-1] = (w >> bit_shift) | carry;
-         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
-
-         top--;
-         }
-      }
-   }
-
-/*
-* Two Operand Left Shift
-*/
-void bigint_shl2(word y[], const word x[], size_t x_size,
-                 size_t word_shift, size_t bit_shift)
-   {
-   for(size_t j = 0; j != x_size; ++j)
-      y[j + word_shift] = x[j];
-   if(bit_shift)
-      {
-      word carry = 0;
-      for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
-         {
-         word w = y[j];
-         y[j] = (w << bit_shift) | carry;
-         carry = (w >> (BOTAN_MP_WORD_BITS - bit_shift));
-         }
-      }
-   }
-
-/*
-* Two Operand Right Shift
-*/
-void bigint_shr2(word y[], const word x[], size_t x_size,
-                 size_t word_shift, size_t bit_shift)
-   {
-   if(x_size < word_shift) return;
-
-   for(size_t j = 0; j != x_size - word_shift; ++j)
-      y[j] = x[j + word_shift];
-   if(bit_shift)
-      {
-      word carry = 0;
-      for(size_t j = x_size - word_shift; j > 0; --j)
-         {
-         word w = y[j-1];
-         y[j-1] = (w >> bit_shift) | carry;
-         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
-         }
-      }
-   }
-
-/*
-* Compare two MP integers
-*/
-int32_t bigint_cmp(const word x[], size_t x_size,
-                   const word y[], size_t y_size)
-   {
-   if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
-
-   while(x_size > y_size)
-      {
-      if(x[x_size-1])
-         return 1;
-      x_size--;
-      }
-
-   for(size_t i = x_size; i > 0; --i)
-      {
-      if(x[i-1] > y[i-1])
-         return 1;
-      if(x[i-1] < y[i-1])
-         return -1;
-      }
-
-   return 0;
-   }
-
-/*
-* Do a 2-word/1-word Division
-*/
-word bigint_divop(word n1, word n0, word d)
-   {
-   if(d == 0)
-      throw Invalid_Argument("bigint_divop divide by zero");
-
-#if defined(BOTAN_HAS_MP_DWORD)
-   return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d;
-#else
-
-   word high = n1 % d, quotient = 0;
-
-   for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
-      {
-      word high_top_bit = (high & MP_WORD_TOP_BIT);
-
-      high <<= 1;
-      high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
-      quotient <<= 1;
-
-      if(high_top_bit || high >= d)
-         {
-         high -= d;
-         quotient |= 1;
-         }
-      }
-
-   return quotient;
-#endif
-   }
-
-/*
-* Do a 2-word/1-word Modulo
-*/
-word bigint_modop(word n1, word n0, word d)
-   {
-#if defined(BOTAN_HAS_MP_DWORD)
-   return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
-#else
-   word z = bigint_divop(n1, n0, d);
-   word dummy = 0;
-   z = word_madd2(z, d, &dummy);
-   return (n0-z);
-#endif
-   }
-
-}
diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 9430c3753..5244261d7 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -1,6 +1,6 @@
 /*
 * MPI Algorithms
-* (C) 1999-2010 Jack Lloyd
+* (C) 1999-2010,2018 Jack Lloyd
 *     2006 Luca Piccarreta
 *     2016 Matthias Gierlings
 *
@@ -11,6 +11,10 @@
 #define BOTAN_MP_CORE_OPS_H_
 
 #include <botan/types.h>
+#include <botan/exceptn.h>
+#include <botan/mem_ops.h>
+#include <botan/internal/mp_asmi.h>
+#include <botan/internal/ct_utils.h>
 
 namespace Botan {
 
@@ -23,22 +27,78 @@ const word MP_WORD_MAX = MP_WORD_MASK;
 * If cond > 0, swaps x[0:size] with y[0:size]
 * Runs in constant time
 */
-BOTAN_TEST_API
-void bigint_cnd_swap(word cnd, word x[], word y[], size_t size);
+inline void bigint_cnd_swap(word cnd, word x[], word y[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   for(size_t i = 0; i != size; ++i)
+      {
+      const word a = x[i];
+      const word b = y[i];
+      x[i] = CT::select(mask, b, a);
+      y[i] = CT::select(mask, a, b);
+      }
+   }
 
 /*
 * If cond > 0 adds x[0:size] and y[0:size] and returns carry
 * Runs in constant time
 */
-BOTAN_TEST_API
-word bigint_cnd_add(word cnd, word x[], const word y[], size_t size);
+inline word bigint_cnd_add(word cnd, word x[], const word y[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   word carry = 0;
+
+   const size_t blocks = size - (size % 8);
+   word z[8] = { 0 };
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      carry = word8_add3(z, x + i, y + i, carry);
+
+      for(size_t j = 0; j != 8; ++j)
+         x[i+j] = CT::select(mask, z[j], x[i+j]);
+      }
+
+   for(size_t i = blocks; i != size; ++i)
+      {
+      z[0] = word_add(x[i], y[i], &carry);
+      x[i] = CT::select(mask, z[0], x[i]);
+      }
+
+   return carry & mask;
+   }
 
 /*
 * If cond > 0 subtracts x[0:size] and y[0:size] and returns borrow
 * Runs in constant time
 */
-BOTAN_TEST_API
-word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
+inline word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   word carry = 0;
+
+   const size_t blocks = size - (size % 8);
+   word z[8] = { 0 };
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      carry = word8_sub3(z, x + i, y + i, carry);
+
+      for(size_t j = 0; j != 8; ++j)
+         x[i+j] = CT::select(mask, z[j], x[i+j]);
+      }
+
+   for(size_t i = blocks; i != size; ++i)
+      {
+      z[0] = word_sub(x[i], y[i], &carry);
+      x[i] = CT::select(mask, z[0], x[i]);
+      }
+
+   return carry & mask;
+   }
 
 /*
 * Equivalent to
@@ -47,15 +107,99 @@ word bigint_cnd_sub(word cnd, word x[], const word y[], size_t size);
 *
 * Mask must be either 0 or all 1 bits
 */
-void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size);
+inline void bigint_cnd_addsub(word mask, word x[], const word y[], size_t size)
+   {
+   const size_t blocks = size - (size % 8);
+
+   word carry = 0;
+   word borrow = 0;
+
+   word t0[8] = { 0 };
+   word t1[8] = { 0 };
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      carry = word8_add3(t0, x + i, y + i, carry);
+      borrow = word8_sub3(t1, x + i, y + i, borrow);
+
+      for(size_t j = 0; j != 8; ++j)
+         x[i+j] = CT::select(mask, t0[j], t1[j]);
+      }
+
+   for(size_t i = blocks; i != size; ++i)
+      {
+      const word a = word_add(x[i], y[i], &carry);
+      const word s = word_sub(x[i], y[i], &borrow);
+
+      x[i] = CT::select(mask, a, s);
+      }
+   }
 
 /*
 * 2s complement absolute value
 * If cond > 0 sets x to ~x + 1
 * Runs in constant time
 */
-BOTAN_TEST_API
-void bigint_cnd_abs(word cnd, word x[], size_t size);
+inline void bigint_cnd_abs(word cnd, word x[], size_t size)
+   {
+   const word mask = CT::expand_mask(cnd);
+
+   word carry = mask & 1;
+   for(size_t i = 0; i != size; ++i)
+      {
+      const word z = word_add(~x[i], 0, &carry);
+      x[i] = CT::select(mask, z, x[i]);
+      }
+   }
+
+/**
+* Two operand addition with carry out
+*/
+inline word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size)
+   {
+   word carry = 0;
+
+   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
+
+   const size_t blocks = y_size - (y_size % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      carry = word8_add2(x + i, y + i, carry);
+
+   for(size_t i = blocks; i != y_size; ++i)
+      x[i] = word_add(x[i], y[i], &carry);
+
+   for(size_t i = y_size; i != x_size; ++i)
+      x[i] = word_add(x[i], 0, &carry);
+
+   return carry;
+   }
+
+/**
+* Three operand addition with carry out
+*/
+inline word bigint_add3_nc(word z[],
+                           const word x[], size_t x_size,
+                           const word y[], size_t y_size)
+   {
+   if(x_size < y_size)
+      { return bigint_add3_nc(z, y, y_size, x, x_size); }
+
+   word carry = 0;
+
+   const size_t blocks = y_size - (y_size % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      carry = word8_add3(z + i, x + i, y + i, carry);
+
+   for(size_t i = blocks; i != y_size; ++i)
+      z[i] = word_add(x[i], y[i], &carry);
+
+   for(size_t i = y_size; i != x_size; ++i)
+      z[i] = word_add(x[i], 0, &carry);
+
+   return carry;
+   }
 
 /**
 * Two operand addition
@@ -64,45 +208,89 @@ void bigint_cnd_abs(word cnd, word x[], size_t size);
 * @param y the second operand
 * @param y_size size of y (must be >= x_size)
 */
-void bigint_add2(word x[], size_t x_size,
-                 const word y[], size_t y_size);
+inline void bigint_add2(word x[], size_t x_size,
+                        const word y[], size_t y_size)
+   {
+   x[x_size] += bigint_add2_nc(x, x_size, y, y_size);
+   }
 
 /**
 * Three operand addition
 */
-void bigint_add3(word z[],
-                 const word x[], size_t x_size,
-                 const word y[], size_t y_size);
+inline void bigint_add3(word z[],
+                        const word x[], size_t x_size,
+                        const word y[], size_t y_size)
+   {
+   z[x_size > y_size ? x_size : y_size] +=
+      bigint_add3_nc(z, x, x_size, y, y_size);
+   }
 
 /**
-* Two operand addition with carry out
+* Two operand subtraction
 */
-word bigint_add2_nc(word x[], size_t x_size, const word y[], size_t y_size);
+inline word bigint_sub2(word x[], size_t x_size,
+                        const word y[], size_t y_size)
+   {
+   word borrow = 0;
 
-/**
-* Three operand addition with carry out
-*/
-word bigint_add3_nc(word z[],
-                    const word x[], size_t x_size,
-                    const word y[], size_t y_size);
+   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
 
-/**
-* Two operand subtraction
-*/
-word bigint_sub2(word x[], size_t x_size,
-                 const word y[], size_t y_size);
+   const size_t blocks = y_size - (y_size % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      borrow = word8_sub2(x + i, y + i, borrow);
+
+   for(size_t i = blocks; i != y_size; ++i)
+      x[i] = word_sub(x[i], y[i], &borrow);
+
+   for(size_t i = y_size; i != x_size; ++i)
+      x[i] = word_sub(x[i], 0, &borrow);
+
+   return borrow;
+   }
 
 /**
 * Two operand subtraction, x = y - x; assumes y >= x
 */
-void bigint_sub2_rev(word x[], const word y[], size_t y_size);
+inline void bigint_sub2_rev(word x[], const word y[], size_t y_size)
+   {
+   word borrow = 0;
+
+   const size_t blocks = y_size - (y_size % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      borrow = word8_sub2_rev(x + i, y + i, borrow);
+
+   for(size_t i = blocks; i != y_size; ++i)
+      x[i] = word_sub(y[i], x[i], &borrow);
+
+   BOTAN_ASSERT(!borrow, "y must be greater than x");
+   }
 
 /**
 * Three operand subtraction
 */
-word bigint_sub3(word z[],
-                 const word x[], size_t x_size,
-                 const word y[], size_t y_size);
+inline word bigint_sub3(word z[],
+                        const word x[], size_t x_size,
+                        const word y[], size_t y_size)
+   {
+   word borrow = 0;
+
+   BOTAN_ASSERT(x_size >= y_size, "Expected sizes");
+
+   const size_t blocks = y_size - (y_size % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      borrow = word8_sub3(z + i, x + i, y + i, borrow);
+
+   for(size_t i = blocks; i != y_size; ++i)
+      z[i] = word_sub(x[i], y[i], &borrow);
+
+   for(size_t i = y_size; i != x_size; ++i)
+      z[i] = word_sub(x[i], 0, &borrow);
+
+   return borrow;
+   }
 
 /**
 * Return abs(x-y), ie if x >= y, then compute z = x - y
@@ -116,30 +304,161 @@ word bigint_sub3(word z[],
 * @param N length of x and y
 * @param ws array of at least 2*N words
 */
-word bigint_sub_abs(word z[],
-                    const word x[], const word y[], size_t N,
-                    word ws[]);
+inline word bigint_sub_abs(word z[],
+                           const word x[], const word y[], size_t N,
+                           word ws[])
+   {
+   // Subtract in both direction then conditional copy out the result
 
-/*
-* Shift Operations
-*/
-void bigint_shl1(word x[], size_t x_size,
-                 size_t word_shift, size_t bit_shift);
+   word* ws0 = ws;
+   word* ws1 = ws + N;
+
+   word borrow0 = 0;
+   word borrow1 = 0;
+
+   const size_t blocks = N - (N % 8);
+
+   for(size_t i = 0; i != blocks; i += 8)
+      {
+      borrow0 = word8_sub3(ws0 + i, x + i, y + i, borrow0);
+      borrow1 = word8_sub3(ws1 + i, y + i, x + i, borrow1);
+      }
 
-void bigint_shr1(word x[], size_t x_size,
-                 size_t word_shift, size_t bit_shift);
+   for(size_t i = blocks; i != N; ++i)
+      {
+      ws0[i] = word_sub(x[i], y[i], &borrow0);
+      ws1[i] = word_sub(y[i], x[i], &borrow1);
+      }
 
-void bigint_shl2(word y[], const word x[], size_t x_size,
-                 size_t word_shift, size_t bit_shift);
+   word mask = CT::conditional_copy_mem(borrow1, z, ws0, ws1, N);
 
-void bigint_shr2(word y[], const word x[], size_t x_size,
-                 size_t word_shift, size_t bit_shift);
+   return CT::select<word>(mask, 0, 1);
+   }
+
+/*
+* Shift Operations
+*/
+inline void bigint_shl1(word x[], size_t x_size,
+                        size_t word_shift, size_t bit_shift)
+   {
+   if(word_shift)
+      {
+      copy_mem(x + word_shift, x, x_size);
+      clear_mem(x, word_shift);
+      }
+
+   if(bit_shift)
+      {
+      word carry = 0;
+      for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
+         {
+         word temp = x[j];
+         x[j] = (temp << bit_shift) | carry;
+         carry = (temp >> (BOTAN_MP_WORD_BITS - bit_shift));
+         }
+      }
+   }
+
+inline void bigint_shr1(word x[], size_t x_size,
+                        size_t word_shift, size_t bit_shift)
+   {
+   if(x_size < word_shift)
+      {
+      clear_mem(x, x_size);
+      return;
+      }
+
+   if(word_shift)
+      {
+      copy_mem(x, x + word_shift, x_size - word_shift);
+      clear_mem(x + x_size - word_shift, word_shift);
+      }
+
+   if(bit_shift)
+      {
+      word carry = 0;
+
+      size_t top = x_size - word_shift;
+
+      while(top)
+         {
+         word w = x[top-1];
+         x[top-1] = (w >> bit_shift) | carry;
+         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
+
+         top--;
+         }
+      }
+   }
+
+inline void bigint_shl2(word y[], const word x[], size_t x_size,
+                        size_t word_shift, size_t bit_shift)
+   {
+   for(size_t j = 0; j != x_size; ++j)
+      y[j + word_shift] = x[j];
+   if(bit_shift)
+      {
+      word carry = 0;
+      for(size_t j = word_shift; j != x_size + word_shift + 1; ++j)
+         {
+         word w = y[j];
+         y[j] = (w << bit_shift) | carry;
+         carry = (w >> (BOTAN_MP_WORD_BITS - bit_shift));
+         }
+      }
+   }
+
+inline void bigint_shr2(word y[], const word x[], size_t x_size,
+                        size_t word_shift, size_t bit_shift)
+   {
+   if(x_size < word_shift) return;
+
+   for(size_t j = 0; j != x_size - word_shift; ++j)
+      y[j] = x[j + word_shift];
+   if(bit_shift)
+      {
+      word carry = 0;
+      for(size_t j = x_size - word_shift; j > 0; --j)
+         {
+         word w = y[j-1];
+         y[j-1] = (w >> bit_shift) | carry;
+         carry = (w << (BOTAN_MP_WORD_BITS - bit_shift));
+         }
+      }
+   }
 
 /*
 * Linear Multiply
 */
-void bigint_linmul2(word x[], size_t x_size, word y);
-void bigint_linmul3(word z[], const word x[], size_t x_size, word y);
+inline void bigint_linmul2(word x[], size_t x_size, word y)
+   {
+   const size_t blocks = x_size - (x_size % 8);
+
+   word carry = 0;
+
+   for(size_t i = 0; i != blocks; i += 8)
+      carry = word8_linmul2(x + i, y, carry);
+
+   for(size_t i = blocks; i != x_size; ++i)
+      x[i] = word_madd2(x[i], y, &carry);
+
+   x[x_size] = carry;
+   }
+
+inline void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
+   {
+   const size_t blocks = x_size - (x_size % 8);
+
+   word carry = 0;
+
+   for(size_t i = 0; i != blocks; i += 8)
+      carry = word8_linmul3(z + i, x + i, y, carry);
+
+   for(size_t i = blocks; i != x_size; ++i)
+      z[i] = word_madd2(x[i], y, &carry);
+
+   z[x_size] = carry;
+   }
 
 /**
 * Montgomery Reduction
@@ -161,18 +480,76 @@ void bigint_monty_redc(word z[],
 /**
 * Compare x and y returning early
 */
-int32_t bigint_cmp(const word x[], size_t x_size,
-                   const word y[], size_t y_size);
+inline int32_t bigint_cmp(const word x[], size_t x_size,
+                          const word y[], size_t y_size)
+   {
+   if(x_size < y_size) { return (-bigint_cmp(y, y_size, x, x_size)); }
+
+   while(x_size > y_size)
+      {
+      if(x[x_size-1])
+         return 1;
+      x_size--;
+      }
+
+   for(size_t i = x_size; i > 0; --i)
+      {
+      if(x[i-1] > y[i-1])
+         return 1;
+      if(x[i-1] < y[i-1])
+         return -1;
+      }
+
+   return 0;
+   }
 
 /**
 * Compute ((n1<<bits) + n0) / d
 */
-word bigint_divop(word n1, word n0, word d);
+inline word bigint_divop(word n1, word n0, word d)
+   {
+   if(d == 0)
+      throw Invalid_Argument("bigint_divop divide by zero");
+
+#if defined(BOTAN_HAS_MP_DWORD)
+   return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) / d;
+#else
+
+   word high = n1 % d, quotient = 0;
+
+   for(size_t i = 0; i != BOTAN_MP_WORD_BITS; ++i)
+      {
+      word high_top_bit = (high & MP_WORD_TOP_BIT);
+
+      high <<= 1;
+      high |= (n0 >> (BOTAN_MP_WORD_BITS-1-i)) & 1;
+      quotient <<= 1;
+
+      if(high_top_bit || high >= d)
+         {
+         high -= d;
+         quotient |= 1;
+         }
+      }
+
+   return quotient;
+#endif
+   }
 
 /**
 * Compute ((n1<<bits) + n0) % d
 */
-word bigint_modop(word n1, word n0, word d);
+inline word bigint_modop(word n1, word n0, word d)
+   {
+#if defined(BOTAN_HAS_MP_DWORD)
+   return ((static_cast<dword>(n1) << BOTAN_MP_WORD_BITS) | n0) % d;
+#else
+   word z = bigint_divop(n1, n0, d);
+   word dummy = 0;
+   z = word_madd2(z, d, &dummy);
+   return (n0-z);
+#endif
+   }
 
 /*
 * Comba Multiplication / Squaring