1 files changed, 165 insertions, 0 deletions
diff --git a/src/lib/math/mp/mp_madd.h b/src/lib/math/mp/mp_madd.h
new file mode 100644
index 000000000..0567622d9
--- /dev/null
+++ b/src/lib/math/mp/mp_madd.h
@@ -0,0 +1,165 @@
+/*
+* Lowest Level MPI Algorithms
+* (C) 1999-2008,2013 Jack Lloyd
+*     2006 Luca Piccarreta
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_MP_WORD_MULADD_H__
+#define BOTAN_MP_WORD_MULADD_H__
+
+#include <botan/mp_types.h>
+#include <botan/mul128.h>
+
+namespace Botan {
+
+#if (BOTAN_MP_WORD_BITS == 8)
+  typedef u16bit dword;
+  #define BOTAN_HAS_MP_DWORD
+#elif (BOTAN_MP_WORD_BITS == 16)
+  typedef u32bit dword;
+  #define BOTAN_HAS_MP_DWORD
+#elif (BOTAN_MP_WORD_BITS == 32)
+  typedef u64bit dword;
+  #define BOTAN_HAS_MP_DWORD
+#elif (BOTAN_MP_WORD_BITS == 64)
+  #if defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
+    typedef uint128_t dword;
+    #define BOTAN_HAS_MP_DWORD
+  #else
+    // No native 128 bit integer type; use mul64x64_128 instead
+  #endif
+
+#else
+  #error BOTAN_MP_WORD_BITS must be 8, 16, 32, or 64
+#endif
+
+#if defined(BOTAN_TARGET_ARCH_IS_X86_32) && (BOTAN_MP_WORD_BITS == 32)
+
+  #if defined(BOTAN_USE_GCC_INLINE_ASM)
+    #define BOTAN_MP_USE_X86_32_ASM
+    #define ASM(x) x "\n\t"
+  #elif defined(BOTAN_TARGET_COMPILER_IS_MSVC)
+    #define BOTAN_MP_USE_X86_32_MSVC_ASM
+  #endif
+
+#elif defined(BOTAN_TARGET_ARCH_IS_X86_64) && (BOTAN_MP_WORD_BITS == 64) && (BOTAN_USE_GCC_INLINE_ASM)
+  #define BOTAN_MP_USE_X86_64_ASM
+  #define ASM(x) x "\n\t"
+#endif
+
+#if defined(BOTAN_MP_USE_X86_32_ASM) || defined(BOTAN_MP_USE_X86_64_ASM)
+  #define ASM(x) x "\n\t"
+#endif
+
+/*
+* Word Multiply/Add
+*/
+inline word word_madd2(word a, word b, word* c)
+   {
+#if defined(BOTAN_MP_USE_X86_32_ASM)
+   asm(
+      ASM("mull %[b]")
+      ASM("addl %[c],%[a]")
+      ASM("adcl $0,%[carry]")
+
+      : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
+      : "0"(a), "1"(b), [c]"g"(*c) : "cc");
+
+   return a;
+
+#elif defined(BOTAN_MP_USE_X86_64_ASM)
+      asm(
+      ASM("mulq %[b]")
+      ASM("addq %[c],%[a]")
+      ASM("adcq $0,%[carry]")
+
+      : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
+      : "0"(a), "1"(b), [c]"g"(*c) : "cc");
+
+   return a;
+
+#elif defined(BOTAN_HAS_MP_DWORD)
+   const dword s = static_cast<dword>(a) * b + *c;
+   *c = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
+   return static_cast<word>(s);
+#else
+   static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
+
+   word hi = 0, lo = 0;
+
+   mul64x64_128(a, b, &lo, &hi);
+
+   lo += *c;
+   hi += (lo < *c); // carry?
+
+   *c = hi;
+   return lo;
+#endif
+   }
+
+/*
+* Word Multiply/Add
+*/
+inline word word_madd3(word a, word b, word c, word* d)
+   {
+#if defined(BOTAN_MP_USE_X86_32_ASM)
+   asm(
+      ASM("mull %[b]")
+
+      ASM("addl %[c],%[a]")
+      ASM("adcl $0,%[carry]")
+
+      ASM("addl %[d],%[a]")
+      ASM("adcl $0,%[carry]")
+
+      : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
+      : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
+
+   return a;
+
+#elif defined(BOTAN_MP_USE_X86_64_ASM)
+   asm(
+      ASM("mulq %[b]")
+
+      ASM("addq %[c],%[a]")
+      ASM("adcq $0,%[carry]")
+
+      ASM("addq %[d],%[a]")
+      ASM("adcq $0,%[carry]")
+
+      : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
+      : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
+
+   return a;
+
+#elif defined(BOTAN_HAS_MP_DWORD)
+   const dword s = static_cast<dword>(a) * b + c + *d;
+   *d = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
+   return static_cast<word>(s);
+#else
+   static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
+
+   word hi = 0, lo = 0;
+
+   mul64x64_128(a, b, &lo, &hi);
+
+   lo += c;
+   hi += (lo < c); // carry?
+
+   lo += *d;
+   hi += (lo < *d); // carry?
+
+   *d = hi;
+   return lo;
+#endif
+   }
+
+#if defined(ASM)
+  #undef ASM
+#endif
+
+}
+
+#endif