Botan  2.4.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/mp_types.h>
13 #include <botan/mul128.h>
14 
15 namespace Botan {
16 
17 #if (BOTAN_MP_WORD_BITS == 8)
18  typedef uint16_t dword;
19  #define BOTAN_HAS_MP_DWORD
20 #elif (BOTAN_MP_WORD_BITS == 16)
21  typedef uint32_t dword;
22  #define BOTAN_HAS_MP_DWORD
23 #elif (BOTAN_MP_WORD_BITS == 32)
24  typedef uint64_t dword;
25  #define BOTAN_HAS_MP_DWORD
26 #elif (BOTAN_MP_WORD_BITS == 64)
27  #if defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
28  typedef uint128_t dword;
29  #define BOTAN_HAS_MP_DWORD
30  #else
31  // No native 128 bit integer type; use mul64x64_128 instead
32  #endif
33 
34 #else
35  #error BOTAN_MP_WORD_BITS must be 8, 16, 32, or 64
36 #endif
37 
38 #if defined(BOTAN_TARGET_ARCH_IS_X86_32) && (BOTAN_MP_WORD_BITS == 32)
39 
40  #if defined(BOTAN_USE_GCC_INLINE_ASM)
41  #define BOTAN_MP_USE_X86_32_ASM
42  #define ASM(x) x "\n\t"
43  #elif defined(BOTAN_BUILD_COMPILER_IS_MSVC)
44  #define BOTAN_MP_USE_X86_32_MSVC_ASM
45  #endif
46 
47 #elif defined(BOTAN_TARGET_ARCH_IS_X86_64) && (BOTAN_MP_WORD_BITS == 64) && (BOTAN_USE_GCC_INLINE_ASM)
48  #define BOTAN_MP_USE_X86_64_ASM
49  #define ASM(x) x "\n\t"
50 #endif
51 
52 #if defined(BOTAN_MP_USE_X86_32_ASM) || defined(BOTAN_MP_USE_X86_64_ASM)
53  #define ASM(x) x "\n\t"
54 #endif
55 
56 /*
57 * Word Multiply/Add
58 */
59 inline word word_madd2(word a, word b, word* c)
60  {
61 #if defined(BOTAN_MP_USE_X86_32_ASM)
62  asm(
63  ASM("mull %[b]")
64  ASM("addl %[c],%[a]")
65  ASM("adcl $0,%[carry]")
66 
67  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
68  : "0"(a), "1"(b), [c]"g"(*c) : "cc");
69 
70  return a;
71 
72 #elif defined(BOTAN_MP_USE_X86_64_ASM)
73  asm(
74  ASM("mulq %[b]")
75  ASM("addq %[c],%[a]")
76  ASM("adcq $0,%[carry]")
77 
78  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
79  : "0"(a), "1"(b), [c]"g"(*c) : "cc");
80 
81  return a;
82 
83 #elif defined(BOTAN_HAS_MP_DWORD)
84  const dword s = static_cast<dword>(a) * b + *c;
85  *c = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
86  return static_cast<word>(s);
87 #else
88  static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
89 
90  word hi = 0, lo = 0;
91 
92  mul64x64_128(a, b, &lo, &hi);
93 
94  lo += *c;
95  hi += (lo < *c); // carry?
96 
97  *c = hi;
98  return lo;
99 #endif
100  }
101 
102 /*
103 * Word Multiply/Add
104 */
105 inline word word_madd3(word a, word b, word c, word* d)
106  {
107 #if defined(BOTAN_MP_USE_X86_32_ASM)
108  asm(
109  ASM("mull %[b]")
110 
111  ASM("addl %[c],%[a]")
112  ASM("adcl $0,%[carry]")
113 
114  ASM("addl %[d],%[a]")
115  ASM("adcl $0,%[carry]")
116 
117  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
118  : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
119 
120  return a;
121 
122 #elif defined(BOTAN_MP_USE_X86_64_ASM)
123  asm(
124  ASM("mulq %[b]")
125 
126  ASM("addq %[c],%[a]")
127  ASM("adcq $0,%[carry]")
128 
129  ASM("addq %[d],%[a]")
130  ASM("adcq $0,%[carry]")
131 
132  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
133  : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
134 
135  return a;
136 
137 #elif defined(BOTAN_HAS_MP_DWORD)
138  const dword s = static_cast<dword>(a) * b + c + *d;
139  *d = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
140  return static_cast<word>(s);
141 #else
142  static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
143 
144  word hi = 0, lo = 0;
145 
146  mul64x64_128(a, b, &lo, &hi);
147 
148  lo += c;
149  hi += (lo < c); // carry?
150 
151  lo += *d;
152  hi += (lo < *d); // carry?
153 
154  *d = hi;
155  return lo;
156 #endif
157  }
158 
159 #if defined(ASM)
160  #undef ASM
161 #endif
162 
163 }
164 
165 #endif
void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)
Definition: mul128.h:83
word word_madd3(word a, word b, word c, word *d)
Definition: mp_madd.h:105
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:59
Definition: alg_id.cpp:13
donna128 uint128_t
Definition: donna.cpp:63