diff options
| -rw-r--r-- | src/lib/math/mp/info.txt | 3 | ||||
| -rw-r--r-- | src/lib/math/mp/mp_asm.cpp | 2 | ||||
| -rw-r--r-- | src/lib/math/mp/mp_comba.cpp | 3 | ||||
| -rw-r--r-- | src/lib/math/mp/mp_core.h | 9 | ||||
| -rw-r--r-- | src/lib/math/mp/mp_karat.cpp | 45 | ||||
| -rw-r--r-- | src/lib/math/mp/mp_mulop.cpp | 73 | ||||
| -rwxr-xr-x | src/scripts/comba.py | 8 |
7 files changed, 48 insertions, 95 deletions
diff --git a/src/lib/math/mp/info.txt b/src/lib/math/mp/info.txt index a47475f7b..6aa0142f3 100644 --- a/src/lib/math/mp/info.txt +++ b/src/lib/math/mp/info.txt @@ -1,11 +1,10 @@ -define BIGINT_MP 20131128 +define BIGINT_MP 20151225 <source> mp_asm.cpp mp_comba.cpp mp_karat.cpp mp_monty.cpp -mp_mulop.cpp mp_misc.cpp mp_shift.cpp </source> diff --git a/src/lib/math/mp/mp_asm.cpp b/src/lib/math/mp/mp_asm.cpp index cc573a792..b7d90552e 100644 --- a/src/lib/math/mp/mp_asm.cpp +++ b/src/lib/math/mp/mp_asm.cpp @@ -1,5 +1,5 @@ /* -* Lowest Level MPI Algorithms +* MPI Add, Subtract, Word Multiply * (C) 1999-2010 Jack Lloyd * 2006 Luca Piccarreta * diff --git a/src/lib/math/mp/mp_comba.cpp b/src/lib/math/mp/mp_comba.cpp index 0170c9fcd..1ebd29817 100644 --- a/src/lib/math/mp/mp_comba.cpp +++ b/src/lib/math/mp/mp_comba.cpp @@ -1,6 +1,7 @@ /* * Comba Multiplication and Squaring -* (C) 1999-2007,2011,2014 Jack Lloyd +* +* This file was automatically generated by comba.py * * Botan is released under the Simplified BSD License (see license.txt) */ diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index b97384d18..9921f1f07 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -81,15 +81,6 @@ void bigint_shr2(word y[], const word x[], size_t x_size, size_t word_shift, size_t bit_shift); /* -* Simple O(N^2) Multiplication and Squaring -*/ -void bigint_simple_mul(word z[], - const word x[], size_t x_size, - const word y[], size_t y_size); - -void bigint_simple_sqr(word z[], const word x[], size_t x_size); - -/* * Linear Multiply */ void bigint_linmul2(word x[], size_t x_size, word y); diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp index 96d9adae2..c7f179191 100644 --- a/src/lib/math/mp/mp_karat.cpp +++ b/src/lib/math/mp/mp_karat.cpp @@ -1,5 +1,5 @@ /* -* Karatsuba Multiplication/Squaring +* Multiplication and Squaring * (C) 1999-2010 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) @@ -16,6 +16,37 @@ namespace { const size_t KARATSUBA_MULTIPLY_THRESHOLD = 32; const size_t KARATSUBA_SQUARE_THRESHOLD = 32; +namespace { + +/* +* Simple O(N^2) Multiplication +*/ +void basecase_mul(word z[], + const word x[], size_t x_size, + const word y[], size_t y_size) + { + const size_t x_size_8 = x_size - (x_size % 8); + + clear_mem(z, x_size + y_size); + + for(size_t i = 0; i != y_size; ++i) + { + const word y_i = y[i]; + + word carry = 0; + + for(size_t j = 0; j != x_size_8; j += 8) + carry = word8_madd3(z + i + j, x + j, y_i, carry); + + for(size_t j = x_size_8; j != x_size; ++j) + z[i+j] = word_madd3(x[j], y_i, z[i+j], &carry); + + z[x_size+i] = carry; + } + } + +} + /* * Karatsuba Multiplication Operation */ @@ -31,7 +62,7 @@ void karatsuba_mul(word z[], const word x[], const word y[], size_t N, else if(N == 16) return bigint_comba_mul16(z, x, y); else - return bigint_simple_mul(z, x, N, y, N); + return basecase_mul(z, x, N, y, N); } const size_t N2 = N / 2; @@ -101,7 +132,7 @@ void karatsuba_sqr(word z[], const word x[], size_t N, word workspace[]) else if(N == 16) return bigint_comba_sqr16(z, x); else - return bigint_simple_sqr(z, x, N); + return basecase_mul(z, x, N, x, N); } const size_t N2 = N / 2; @@ -262,7 +293,7 @@ void bigint_mul(word z[], size_t z_size, word workspace[], y_sw < KARATSUBA_MULTIPLY_THRESHOLD || !workspace) { - bigint_simple_mul(z, x, x_sw, y, y_sw); + basecase_mul(z, x, x_sw, y, y_sw); } else { @@ -271,7 +302,7 @@ void bigint_mul(word z[], size_t z_size, word workspace[], if(N) karatsuba_mul(z, x, y, N, workspace); else - bigint_simple_mul(z, x, x_sw, y, y_sw); + basecase_mul(z, x, x_sw, y, y_sw); } } @@ -307,7 +338,7 @@ void bigint_sqr(word z[], size_t z_size, word workspace[], } else if(x_size < KARATSUBA_SQUARE_THRESHOLD || !workspace) { - bigint_simple_sqr(z, x, x_sw); + basecase_mul(z, x, x_sw, x, x_sw); } else { @@ -316,7 +347,7 @@ void bigint_sqr(word z[], size_t z_size, word workspace[], if(N) karatsuba_sqr(z, x, N, workspace); else - bigint_simple_sqr(z, x, x_sw); + basecase_mul(z, x, x_sw, x, x_sw); } } diff --git a/src/lib/math/mp/mp_mulop.cpp b/src/lib/math/mp/mp_mulop.cpp deleted file mode 100644 index 432c7ef53..000000000 --- a/src/lib/math/mp/mp_mulop.cpp +++ /dev/null @@ -1,73 +0,0 @@ -/* -* Simple O(N^2) Multiplication and Squaring -* (C) 1999-2008 Jack Lloyd -* -* Botan is released under the Simplified BSD License (see license.txt) -*/ - -#include <botan/internal/mp_core.h> -#include <botan/internal/mp_madd.h> -#include <botan/internal/mp_asmi.h> -#include <botan/mem_ops.h> - -namespace Botan { - -/* -* Simple O(N^2) Multiplication -*/ -void bigint_simple_mul(word z[], const word x[], size_t x_size, - const word y[], size_t y_size) - { - const size_t x_size_8 = x_size - (x_size % 8); - - clear_mem(z, x_size + y_size); - - for(size_t i = 0; i != y_size; ++i) - { - const word y_i = y[i]; - - word carry = 0; - - for(size_t j = 0; j != x_size_8; j += 8) - carry = word8_madd3(z + i + j, x + j, y_i, carry); - - for(size_t j = x_size_8; 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 -* -* This is exactly the same algorithm as bigint_simple_mul, however -* because C/C++ compilers suck at alias analysis it is good to have -* the version where the compiler knows that x == y -* -* There is an O(n^1.5) squaring algorithm specified in Handbook of -* Applied Cryptography, chapter 14 -* -*/ -void bigint_simple_sqr(word z[], const word x[], size_t x_size) - { - const size_t x_size_8 = x_size - (x_size % 8); - - clear_mem(z, 2*x_size); - - for(size_t i = 0; i != x_size; ++i) - { - const word x_i = x[i]; - word carry = 0; - - for(size_t j = 0; j != x_size_8; j += 8) - carry = word8_madd3(z + i + j, x + j, x_i, carry); - - for(size_t j = x_size_8; j != x_size; ++j) - z[i+j] = word_madd3(x[j], x_i, z[i+j], &carry); - - z[x_size+i] = carry; - } - } - -} diff --git a/src/scripts/comba.py b/src/scripts/comba.py index dcac14657..f0165a3ce 100755 --- a/src/scripts/comba.py +++ b/src/scripts/comba.py @@ -1,7 +1,10 @@ -#!/usr/bin/python +#!/usr/bin/python2 import sys +# (C) 2011,2014,2015 Jack Lloyd +# Botan is released under the Simplified BSD License (see license.txt) + # Used to generate src/lib/math/mp/mp_comba.cpp def comba_indexes(N): @@ -78,7 +81,8 @@ def main(args = None): print """/* * Comba Multiplication and Squaring -* (C) 1999-2007,2011,2014 Jack Lloyd +* +* This file was automatically generated by comba.py * * Botan is released under the Simplified BSD License (see license.txt) */ |