aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2018-11-09 11:48:16 -0500
committerJack Lloyd <[email protected]>2018-11-09 12:33:56 -0500
commitddb9808ef59168174e8299b02fea4e84ac2742e3 (patch)
treef5257434831239900c9b82a9c5cada7f28be7510 /src
parent99050e91c4373594f74f2e40f9cd4897aacc0026 (diff)
Inline the contents of mp_core.cpp
Diffstat (limited to 'src')
-rw-r--r--src/lib/math/mp/mp_core.cpp549
-rw-r--r--src/lib/math/mp/mp_core.h481
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