Botan  2.9.0
Crypto and TLS for C++11
mp_madd.h
Go to the documentation of this file.
1 /*
2 * Lowest Level MPI Algorithms
3 * (C) 1999-2008,2013 Jack Lloyd
4 * 2006 Luca Piccarreta
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #ifndef BOTAN_MP_WORD_MULADD_H_
10 #define BOTAN_MP_WORD_MULADD_H_
11 
12 #include <botan/types.h>
13 #include <botan/mul128.h>
14 
15 namespace Botan {
16 
17 #if (BOTAN_MP_WORD_BITS == 32)
18  typedef uint64_t dword;
19  #define BOTAN_HAS_MP_DWORD
20 
21 #elif (BOTAN_MP_WORD_BITS == 64)
22  #if defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
23  typedef uint128_t dword;
24  #define BOTAN_HAS_MP_DWORD
25  #else
26  // No native 128 bit integer type; use mul64x64_128 instead
27  #endif
28 
29 #else
30  #error BOTAN_MP_WORD_BITS must be 32 or 64
31 #endif
32 
33 #if defined(BOTAN_TARGET_ARCH_IS_X86_32) && (BOTAN_MP_WORD_BITS == 32)
34 
35  #if defined(BOTAN_USE_GCC_INLINE_ASM)
36  #define BOTAN_MP_USE_X86_32_ASM
37  #elif defined(BOTAN_BUILD_COMPILER_IS_MSVC)
38  #define BOTAN_MP_USE_X86_32_MSVC_ASM
39  #endif
40 
41 #elif defined(BOTAN_TARGET_ARCH_IS_X86_64) && (BOTAN_MP_WORD_BITS == 64) && defined(BOTAN_USE_GCC_INLINE_ASM)
42  #define BOTAN_MP_USE_X86_64_ASM
43 #endif
44 
45 #if defined(BOTAN_MP_USE_X86_32_ASM) || defined(BOTAN_MP_USE_X86_64_ASM)
46  #define ASM(x) x "\n\t"
47 #endif
48 
49 /*
50 * Word Multiply/Add
51 */
52 inline word word_madd2(word a, word b, word* c)
53  {
54 #if defined(BOTAN_MP_USE_X86_32_ASM)
55  asm(
56  ASM("mull %[b]")
57  ASM("addl %[c],%[a]")
58  ASM("adcl $0,%[carry]")
59 
60  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
61  : "0"(a), "1"(b), [c]"g"(*c) : "cc");
62 
63  return a;
64 
65 #elif defined(BOTAN_MP_USE_X86_64_ASM)
66  asm(
67  ASM("mulq %[b]")
68  ASM("addq %[c],%[a]")
69  ASM("adcq $0,%[carry]")
70 
71  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
72  : "0"(a), "1"(b), [c]"g"(*c) : "cc");
73 
74  return a;
75 
76 #elif defined(BOTAN_HAS_MP_DWORD)
77  const dword s = static_cast<dword>(a) * b + *c;
78  *c = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
79  return static_cast<word>(s);
80 #else
81  static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
82 
83  word hi = 0, lo = 0;
84 
85  mul64x64_128(a, b, &lo, &hi);
86 
87  lo += *c;
88  hi += (lo < *c); // carry?
89 
90  *c = hi;
91  return lo;
92 #endif
93  }
94 
95 /*
96 * Word Multiply/Add
97 */
98 inline word word_madd3(word a, word b, word c, word* d)
99  {
100 #if defined(BOTAN_MP_USE_X86_32_ASM)
101  asm(
102  ASM("mull %[b]")
103 
104  ASM("addl %[c],%[a]")
105  ASM("adcl $0,%[carry]")
106 
107  ASM("addl %[d],%[a]")
108  ASM("adcl $0,%[carry]")
109 
110  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
111  : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
112 
113  return a;
114 
115 #elif defined(BOTAN_MP_USE_X86_64_ASM)
116  asm(
117  ASM("mulq %[b]")
118 
119  ASM("addq %[c],%[a]")
120  ASM("adcq $0,%[carry]")
121 
122  ASM("addq %[d],%[a]")
123  ASM("adcq $0,%[carry]")
124 
125  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
126  : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
127 
128  return a;
129 
130 #elif defined(BOTAN_HAS_MP_DWORD)
131  const dword s = static_cast<dword>(a) * b + c + *d;
132  *d = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
133  return static_cast<word>(s);
134 #else
135  static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
136 
137  word hi = 0, lo = 0;
138 
139  mul64x64_128(a, b, &lo, &hi);
140 
141  lo += c;
142  hi += (lo < c); // carry?
143 
144  lo += *d;
145  hi += (lo < *d); // carry?
146 
147  *d = hi;
148  return lo;
149 #endif
150  }
151 
152 #if defined(ASM)
153  #undef ASM
154 #endif
155 
156 }
157 
158 #endif
void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)
Definition: mul128.h:83
void carry(int64_t &h0, int64_t &h1)
word word_madd3(word a, word b, word c, word *d)
Definition: mp_madd.h:98
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:52
Definition: alg_id.cpp:13