diff options
| -rw-r--r-- | include/mp_core.h | 9 | ||||
| -rw-r--r-- | src/mp_karat.cpp | 23 | ||||
| -rw-r--r-- | src/mp_mulop.cpp | 46 |
3 files changed, 45 insertions, 33 deletions
diff --git a/include/mp_core.h b/include/mp_core.h index 9df4a41e4..7ec0d0c49 100644 --- a/include/mp_core.h +++ b/include/mp_core.h @@ -38,10 +38,15 @@ void bigint_shr1(word[], u32bit, u32bit, u32bit); void bigint_shr2(word[], const word[], u32bit, u32bit, u32bit); /************************************************* -* Multiplication and Squaring Operations * +* Simple O(N^2) Multiplication and Squaring * *************************************************/ -word bigint_mul_add_words(word[], const word[], u32bit, word); +void bigint_simple_mul(word z[], const word x[], u32bit x_size, + const word y[], u32bit y_size); +void bigint_simple_sqr(word z[], const word x[], u32bit x_size); +/************************************************* +* Linear Multiply * +*************************************************/ void bigint_linmul2(word[], u32bit, word); void bigint_linmul3(word[], const word[], u32bit, word); void bigint_linmul_add(word[], u32bit, const word[], u32bit, word); diff --git a/src/mp_karat.cpp b/src/mp_karat.cpp index 38a700a88..770846b4e 100644 --- a/src/mp_karat.cpp +++ b/src/mp_karat.cpp @@ -12,29 +12,6 @@ namespace Botan { namespace { /************************************************* -* Simple O(N^2) Multiplication * -*************************************************/ -void bigint_simple_mul(word z[], const word x[], u32bit x_size, - const word y[], u32bit y_size) - { - 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]); - } - -/************************************************* -* Simple O(N^2) Squaring * -*************************************************/ -void bigint_simple_sqr(word z[], const word x[], u32bit x_size) - { - clear_mem(z, 2*x_size); - - for(u32bit j = 0; j != x_size; ++j) - z[j+x_size] = bigint_mul_add_words(z + j, x, x_size, x[j]); - } - -/************************************************* * Karatsuba Multiplication Operation * *************************************************/ void karatsuba_mul(word z[], const word x[], const word y[], u32bit N, diff --git a/src/mp_mulop.cpp b/src/mp_mulop.cpp index 90449d9ff..6a476998c 100644 --- a/src/mp_mulop.cpp +++ b/src/mp_mulop.cpp @@ -6,27 +6,57 @@ #include <botan/mp_asm.h> #include <botan/mp_asmi.h> #include <botan/mp_core.h> +#include <botan/mem_ops.h> namespace Botan { extern "C" { /************************************************* -* Multiply/Add Words * +* Simple O(N^2) Multiplication * *************************************************/ -word bigint_mul_add_words(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 = x_size - (x_size % 8); - word carry = 0; + clear_mem(z, x_size + y_size); - for(u32bit i = 0; i != blocks; i += 8) - carry = word8_madd3(z + i, x + i, y, carry); + for(u32bit i = 0; i != y_size; ++i) + { + word carry = 0; - for(u32bit i = blocks; i != x_size; ++i) - z[i] = word_madd3(x[i], y, z[i], &carry); + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_madd3(z + i + j, x + j, y[i], carry); - return carry; + for(u32bit j = blocks; j != x_size; ++j) + z[i+j] = word_madd3(x[j], y[i], z[i+j], &carry); + + z[x_size+i] = carry; + } + } + +/************************************************* +* Simple O(N^2) Squaring * +*************************************************/ +void bigint_simple_sqr(word z[], const word x[], u32bit x_size) + { + const u32bit blocks = x_size - (x_size % 8); + + clear_mem(z, 2*x_size); + + for(u32bit i = 0; i != x_size; ++i) + { + word carry = 0; + + for(u32bit j = 0; j != blocks; j += 8) + carry = word8_madd3(z + i + j, x + j, x[i], carry); + + for(u32bit j = blocks; j != x_size; ++j) + z[i+j] = word_madd3(x[j], x[i], z[i+j], &carry); + + z[x_size+i] = carry; + } } } |