Remove mp_mulop.cpp

It had two functions, both only called from one place (mp_karat.cpp).
Both multiple and square ops were O(n**2), so drop square and just
call mul in mp_karat.cpp for either case

6 files changed, 42 insertions, 93 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;
-      }
-   }
-
-}