Add a generic 64x64->128 multiplication op.

Use it to merge mp_msvc64 (was using MSVC _umul128 intrinsic) and
mp_asm64 (was using inline asm) into mp_word64, which calls the new
mul64x64_128 function. That function wraps any available compiler
intrinsics or CPU instructions.

6 files changed, 66 insertions, 213 deletions

diff --git a/src/math/mp/info.txt b/src/math/mp/info.txt
index bf7f40d3c..531eee4e4 100644
--- a/src/math/mp/info.txt
+++ b/src/math/mp/info.txt
@@ -19,5 +19,5 @@ mp_core.h
 </header:internal>
 
 <requires>
-mp_x86_64|mp_msvc64|mp_asm64|mp_x86_32|mp_x86_32_msvc|mp_generic
+mp_x86_64|mp_word64|mp_x86_32|mp_x86_32_msvc|mp_generic
 </requires>
diff --git a/src/math/mp/mp_asm64/info.txt b/src/math/mp/mp_asm64/info.txt
deleted file mode 100644
index 9af7c4ae7..000000000
--- a/src/math/mp/mp_asm64/info.txt
+++ /dev/null
@@ -1,24 +0,0 @@
-mp_bits 64
-
-load_on dep
-
-<header:internal>
-mp_asm.h
-mp_generic:mp_asmi.h
-</header:internal>
-
-<arch>
-alpha
-ia64
-mips64
-ppc64
-sparc64
-</arch>
-
-# The inline asm only works with gcc, but it looks like (at least on
-# UltraSPARC), using 64-bit words and the sythensized multiply is a 5 to 25%
-# win, so it's probably worth using elsewhere.
-<cc>
-gcc
-sunstudio
-</cc>
diff --git a/src/math/mp/mp_asm64/mp_asm.h b/src/math/mp/mp_asm64/mp_asm.h
deleted file mode 100644
index 625ea1c4f..000000000
--- a/src/math/mp/mp_asm64/mp_asm.h
+++ /dev/null
@@ -1,120 +0,0 @@
-/*
-* MPI Multiply-Add Core
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_MP_MADD_H__
-#define BOTAN_MP_MADD_H__
-
-#include <botan/mp_types.h>
-
-namespace Botan {
-
-#if (BOTAN_MP_WORD_BITS != 64)
-   #error The mp_asm64 module requires that BOTAN_MP_WORD_BITS == 64
-#endif
-
-#if defined(BOTAN_TARGET_ARCH_IS_ALPHA)
-
-#define BOTAN_WORD_MUL(a,b,z1,z0) do {                   \
-   asm("umulh %1,%2,%0" : "=r" (z0) : "r" (a), "r" (b)); \
-   z1 = a * b;                                           \
-} while(0);
-
-#elif defined(BOTAN_TARGET_ARCH_IS_IA64)
-
-#define BOTAN_WORD_MUL(a,b,z1,z0) do {                     \
-   asm("xmpy.hu %0=%1,%2" : "=f" (z0) : "f" (a), "f" (b)); \
-   z1 = a * b;                                             \
-} while(0);
-
-#elif defined(BOTAN_TARGET_ARCH_IS_PPC64)
-
-#define BOTAN_WORD_MUL(a,b,z1,z0) do {                           \
-   asm("mulhdu %0,%1,%2" : "=r" (z0) : "r" (a), "r" (b) : "cc"); \
-   z1 = a * b;                                                   \
-} while(0);
-
-#elif defined(BOTAN_TARGET_ARCH_IS_MIPS64)
-
-#define BOTAN_WORD_MUL(a,b,z1,z0) do {                            \
-   typedef unsigned int uint128_t __attribute__((mode(TI)));      \
-   uint128_t r = (uint128_t)a * b;                                \
-   z0 = (r >> 64) & 0xFFFFFFFFFFFFFFFF;                           \
-   z1 = (r      ) & 0xFFFFFFFFFFFFFFFF;                           \
-} while(0);
-
-#else
-
-// Do a 64x64->128 multiply using four 64x64->64 multiplies
-// plus some adds and shifts. Last resort for CPUs like UltraSPARC,
-// with 64-bit registers/ALU, but no 64x64->128 multiply.
-inline void bigint_2word_mul(word a, word b, word* z1, word* z0)
-   {
-   const size_t MP_HWORD_BITS = BOTAN_MP_WORD_BITS / 2;
-   const word MP_HWORD_MASK = ((word)1 << MP_HWORD_BITS) - 1;
-
-   const word a_hi = (a >> MP_HWORD_BITS);
-   const word a_lo = (a & MP_HWORD_MASK);
-   const word b_hi = (b >> MP_HWORD_BITS);
-   const word b_lo = (b & MP_HWORD_MASK);
-
-   word x0 = a_hi * b_hi;
-   word x1 = a_lo * b_hi;
-   word x2 = a_hi * b_lo;
-   word x3 = a_lo * b_lo;
-
-   x2 += x3 >> (MP_HWORD_BITS);
-   x2 += x1;
-
-   if(x2 < x1) // timing channel
-      x0 += ((word)1 << MP_HWORD_BITS);
-
-   *z0 = x0 + (x2 >> MP_HWORD_BITS);
-   *z1 = ((x2 & MP_HWORD_MASK) << MP_HWORD_BITS) + (x3 & MP_HWORD_MASK);
-   }
-
-#define BOTAN_WORD_MUL(a,b,z1,z0) bigint_2word_mul(a, b, &z1, &z0)
-
-#endif
-
-/*
-* Word Multiply/Add
-*/
-inline word word_madd2(word a, word b, word* c)
-   {
-   word z0 = 0, z1 = 0;
-
-   BOTAN_WORD_MUL(a, b, z1, z0);
-
-   z1 += *c;
-   z0 += (z1 < *c);
-
-   *c = z0;
-   return z1;
-   }
-
-/*
-* Word Multiply/Add
-*/
-inline word word_madd3(word a, word b, word c, word* d)
-   {
-   word z0 = 0, z1 = 0;
-
-   BOTAN_WORD_MUL(a, b, z1, z0);
-
-   z1 += c;
-   z0 += (z1 < c);
-
-   z1 += *d;
-   z0 += (z1 < *d);
-
-   *d = z0;
-   return z1;
-   }
-
-}
-
-#endif
diff --git a/src/math/mp/mp_msvc64/mp_asm.h b/src/math/mp/mp_msvc64/mp_asm.h
deleted file mode 100644
index 8e4535c35..000000000
--- a/src/math/mp/mp_msvc64/mp_asm.h
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
-* Multiply-Add for 64-bit MSVC
-* (C) 2010 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_MP_ASM_H__
-#define BOTAN_MP_ASM_H__
-
-#include <botan/mp_types.h>
-#include <intrin.h>
-
-#if (BOTAN_MP_WORD_BITS != 64)
-   #error The mp_msvc64 module requires that BOTAN_MP_WORD_BITS == 64
-#endif
-
-#pragma intrinsic(_umul128)
-
-namespace Botan {
-
-extern "C" {
-
-/*
-* Word Multiply
-*/
-inline word word_madd2(word a, word b, word* c)
-   {
-   word hi, lo;
-   lo = _umul128(a, b, &hi);
-
-   lo += *c;
-   hi += (lo < *c); // carry?
-
-   *c = hi;
-   return lo;
-   }
-
-/*
-* Word Multiply/Add
-*/
-inline word word_madd3(word a, word b, word c, word* d)
-   {
-   word hi, lo;
-   lo = _umul128(a, b, &hi);
-
-   lo += c;
-   hi += (lo < c); // carry?
-
-   lo += *d;
-   hi += (lo < *d); // carry?
-
-   *d = hi;
-   return lo;
-   }
-
-}
-
-}
-
-#endif
diff --git a/src/math/mp/mp_msvc64/info.txt b/src/math/mp/mp_word64/info.txt
index fa7d90fed..a12221f4e 100644
--- a/src/math/mp/mp_msvc64/info.txt
+++ b/src/math/mp/mp_word64/info.txt
@@ -1,17 +1,18 @@
-load_on dep
-
 mp_bits 64
 
+load_on dep
+
 <header:internal>
 mp_asm.h
 mp_generic:mp_asmi.h
 </header:internal>
 
 <arch>
-x86_64
+alpha
 ia64
+mips64
+ppc64
+s390x
+sparc64
+x86_64
 </arch>
-
-<cc>
-msvc
-</cc>
diff --git a/src/math/mp/mp_word64/mp_asm.h b/src/math/mp/mp_word64/mp_asm.h
new file mode 100644
index 000000000..76d2bb918
--- /dev/null
+++ b/src/math/mp/mp_word64/mp_asm.h
@@ -0,0 +1,57 @@
+/*
+* MPI Multiply-Add Core
+* (C) 1999-2007 Jack Lloyd
+*
+* Distributed under the terms of the Botan license
+*/
+
+#ifndef BOTAN_MP_MADD_H__
+#define BOTAN_MP_MADD_H__
+
+#include <botan/mp_types.h>
+#include <botan/internal/mul128.h>
+
+namespace Botan {
+
+#if (BOTAN_MP_WORD_BITS != 64)
+   #error The mp_word64 module requires that BOTAN_MP_WORD_BITS == 64
+#endif
+
+/*
+* Word Multiply/Add
+*/
+inline word word_madd2(word a, word b, word* c)
+   {
+   word z0 = 0, z1 = 0;
+
+   mul64x64_128(a, b, &z1, &z0);
+
+   z1 += *c;
+   z0 += (z1 < *c);
+
+   *c = z0;
+   return z1;
+   }
+
+/*
+* Word Multiply/Add
+*/
+inline word word_madd3(word a, word b, word c, word* d)
+   {
+   word z0 = 0, z1 = 0;
+
+   mul64x64_128(a, b, &z1, &z0);
+
+   z1 += c;
+   z0 += (z1 < c);
+
+   z1 += *d;
+   z0 += (z1 < *d);
+
+   *d = z0;
+   return z1;
+   }
+
+}
+
+#endif