Merge mp_sqr.cpp and mp_mul.cpp into mp_karat.cpp, since there is a lot

of similar-but-not-identical code between them. (Can't merge for performance
reasons, squaring is a special case of multiplication allowing extra
optimizations)

2 files changed, 132 insertions, 147 deletions

diff --git a/src/mp_mul.cpp b/src/mp_karat.cpp
index 27b8e07be..89e5b4d16 100644
--- a/src/mp_mul.cpp
+++ b/src/mp_karat.cpp
@@ -1,6 +1,6 @@
 /*************************************************
-* Karatsuba Multiplication Source File           *
-* (C) 1999-2007 Jack Lloyd                       *
+* Karatsuba Multiplication/Squaring Source File  *
+* (C) 1999-2008 Jack Lloyd                       *
 *************************************************/
 
 #include <botan/mp_core.h>
@@ -23,6 +23,17 @@ void bigint_simple_mul(word z[], const word x[], u32bit x_size,
    }
 
 /*************************************************
+* 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,
@@ -82,6 +93,56 @@ void karatsuba_mul(word z[], const word x[], const word y[], u32bit N,
    }
 
 /*************************************************
+* Karatsuba Squaring Operation                   *
+*************************************************/
+void karatsuba_sqr(word z[], const word x[], u32bit N, word workspace[])
+   {
+   const u32bit KARATSUBA_SQR_LOWER_SIZE = BOTAN_KARAT_SQR_THRESHOLD;
+
+   if(N == 6)
+      bigint_comba_sqr6(z, x);
+   else if(N == 8)
+      bigint_comba_sqr8(z, x);
+   else if(N < KARATSUBA_SQR_LOWER_SIZE || N % 2)
+      bigint_simple_sqr(z, x, N);
+   else
+      {
+      const u32bit N2 = N / 2;
+
+      const word* x0 = x;
+      const word* x1 = x + N2;
+      word* z0 = z;
+      word* z1 = z + N;
+
+      const s32bit cmp = bigint_cmp(x0, N2, x1, N2);
+
+      clear_mem(workspace, 2*N);
+
+      if(cmp)
+         {
+         if(cmp > 0)
+            bigint_sub3(z0, x0, N2, x1, N2);
+         else
+            bigint_sub3(z0, x1, N2, x0, N2);
+
+         karatsuba_sqr(workspace, z0, N2, workspace+N);
+         }
+
+      karatsuba_sqr(z0, x0, N2, workspace+N);
+      karatsuba_sqr(z1, x1, N2, workspace+N);
+
+      word carry = bigint_add3_nc(workspace+N, z0, N, z1, N);
+      carry += bigint_add2_nc(z + N2, N, workspace + N, N);
+      bigint_add2_nc(z + N + N2, N2, &carry, 1);
+
+      if(cmp == 0)
+         bigint_add2(z + N2, 2*N-N2, workspace, N);
+      else
+         bigint_sub2(z + N2, 2*N-N2, workspace, N);
+      }
+   }
+
+/*************************************************
 * Pick a good size for the Karatsuba multiply    *
 *************************************************/
 u32bit karatsuba_size(u32bit z_size,
@@ -126,6 +187,34 @@ u32bit karatsuba_size(u32bit z_size,
    }
 
 /*************************************************
+* Pick a good size for the Karatsuba squaring    *
+*************************************************/
+u32bit karatsuba_size(u32bit z_size, u32bit x_size, u32bit x_sw)
+   {
+   if(x_sw == x_size)
+      {
+      if(x_sw % 2)
+         return 0;
+      return x_sw;
+      }
+
+   for(u32bit j = x_sw; j <= x_size; ++j)
+      {
+      if(j % 2)
+         continue;
+
+      if(2*j > z_size)
+         return 0;
+
+      if(j % 4 == 2 && (j+2) <= x_size && 2*(j+2) <= z_size)
+         return j+2;
+      return j;
+      }
+
+   return 0;
+   }
+
+/*************************************************
 * Handle small operand multiplies                *
 *************************************************/
 void handle_small_mul(word z[], u32bit z_size,
@@ -151,6 +240,24 @@ void handle_small_mul(word z[], u32bit z_size,
       bigint_simple_mul(z, x, x_sw, y, y_sw);
    }
 
+/*************************************************
+* Handle small operand squarings                 *
+*************************************************/
+void handle_small_sqr(word z[], u32bit z_size,
+                      const word x[], u32bit x_size, u32bit x_sw)
+   {
+   if(x_sw == 1)
+      bigint_linmul3(z, x, x_sw, x[0]);
+   else if(x_sw <= 4 && x_size >= 4 && z_size >= 8)
+      bigint_comba_sqr4(z, x);
+   else if(x_sw <= 6 && x_size >= 6 && z_size >= 12)
+      bigint_comba_sqr6(z, x);
+   else if(x_sw <= 8 && x_size >= 8 && z_size >= 16)
+      bigint_comba_sqr8(z, x);
+   else
+      bigint_simple_sqr(z, x, x_sw);
+   }
+
 }
 
 /*************************************************
@@ -177,4 +284,27 @@ void bigint_mul(word z[], u32bit z_size, word workspace[],
       bigint_simple_mul(z, x, x_sw, y, y_sw);
    }
 
+/*************************************************
+* Squaring Algorithm Dispatcher                  *
+*************************************************/
+void bigint_sqr(word z[], u32bit z_size, word workspace[],
+                const word x[], u32bit x_size, u32bit x_sw)
+   {
+   if(x_size <= 8 || x_sw <= 8)
+      {
+      handle_small_sqr(z, z_size, x, x_size, x_sw);
+      return;
+      }
+
+   const u32bit N = karatsuba_size(z_size, x_size, x_sw);
+
+   if(N)
+      {
+      clear_mem(workspace, 2*N);
+      karatsuba_sqr(z, x, N, workspace);
+      }
+   else
+      bigint_simple_sqr(z, x, x_sw);
+   }
+
 }
diff --git a/src/mp_sqr.cpp b/src/mp_sqr.cpp
deleted file mode 100644
index 1cf97afe4..000000000
--- a/src/mp_sqr.cpp
+++ /dev/null
@@ -1,145 +0,0 @@
-/*************************************************
-* Karatsuba Squaring Source File                 *
-* (C) 1999-2007 Jack Lloyd                       *
-*************************************************/
-
-#include <botan/mp_core.h>
-#include <botan/mem_ops.h>
-
-namespace Botan {
-
-namespace {
-
-/*************************************************
-* 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 Squaring Operation                   *
-*************************************************/
-void karatsuba_sqr(word z[], const word x[], u32bit N, word workspace[])
-   {
-   const u32bit KARATSUBA_SQR_LOWER_SIZE = BOTAN_KARAT_SQR_THRESHOLD;
-
-   if(N == 6)
-      bigint_comba_sqr6(z, x);
-   else if(N == 8)
-      bigint_comba_sqr8(z, x);
-   else if(N < KARATSUBA_SQR_LOWER_SIZE || N % 2)
-      bigint_simple_sqr(z, x, N);
-   else
-      {
-      const u32bit N2 = N / 2;
-
-      const word* x0 = x;
-      const word* x1 = x + N2;
-      word* z0 = z;
-      word* z1 = z + N;
-
-      const s32bit cmp = bigint_cmp(x0, N2, x1, N2);
-
-      clear_mem(workspace, 2*N);
-
-      if(cmp)
-         {
-         if(cmp > 0)
-            bigint_sub3(z0, x0, N2, x1, N2);
-         else
-            bigint_sub3(z0, x1, N2, x0, N2);
-
-         karatsuba_sqr(workspace, z0, N2, workspace+N);
-         }
-
-      karatsuba_sqr(z0, x0, N2, workspace+N);
-      karatsuba_sqr(z1, x1, N2, workspace+N);
-
-      word carry = bigint_add3_nc(workspace+N, z0, N, z1, N);
-      carry += bigint_add2_nc(z + N2, N, workspace + N, N);
-      bigint_add2_nc(z + N + N2, N2, &carry, 1);
-
-      if(cmp == 0)
-         bigint_add2(z + N2, 2*N-N2, workspace, N);
-      else
-         bigint_sub2(z + N2, 2*N-N2, workspace, N);
-      }
-   }
-
-/*************************************************
-* Pick a good size for the Karatsuba squaring    *
-*************************************************/
-u32bit karatsuba_size(u32bit z_size, u32bit x_size, u32bit x_sw)
-   {
-   if(x_sw == x_size)
-      {
-      if(x_sw % 2)
-         return 0;
-      return x_sw;
-      }
-
-   for(u32bit j = x_sw; j <= x_size; ++j)
-      {
-      if(j % 2)
-         continue;
-
-      if(2*j > z_size)
-         return 0;
-
-      if(j % 4 == 2 && (j+2) <= x_size && 2*(j+2) <= z_size)
-         return j+2;
-      return j;
-      }
-
-   return 0;
-   }
-
-/*************************************************
-* Handle small operand squarings                 *
-*************************************************/
-void handle_small_sqr(word z[], u32bit z_size,
-                      const word x[], u32bit x_size, u32bit x_sw)
-   {
-   if(x_sw == 1)
-      bigint_linmul3(z, x, x_sw, x[0]);
-   else if(x_sw <= 4 && x_size >= 4 && z_size >= 8)
-      bigint_comba_sqr4(z, x);
-   else if(x_sw <= 6 && x_size >= 6 && z_size >= 12)
-      bigint_comba_sqr6(z, x);
-   else if(x_sw <= 8 && x_size >= 8 && z_size >= 16)
-      bigint_comba_sqr8(z, x);
-   else
-      bigint_simple_sqr(z, x, x_sw);
-   }
-
-}
-
-/*************************************************
-* Squaring Algorithm Dispatcher                  *
-*************************************************/
-void bigint_sqr(word z[], u32bit z_size, word workspace[],
-                const word x[], u32bit x_size, u32bit x_sw)
-   {
-   if(x_size <= 8 || x_sw <= 8)
-      {
-      handle_small_sqr(z, z_size, x, x_size, x_sw);
-      return;
-      }
-
-   const u32bit N = karatsuba_size(z_size, x_size, x_sw);
-
-   if(N)
-      {
-      clear_mem(workspace, 2*N);
-      karatsuba_sqr(z, x, N, workspace);
-      }
-   else
-      bigint_simple_sqr(z, x, x_sw);
-   }
-
-}