Botan  2.19.1
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_USE_GCC_INLINE_ASM)
34 
35  #if defined(BOTAN_TARGET_ARCH_IS_X86_32) && (BOTAN_MP_WORD_BITS == 32)
36  #define BOTAN_MP_USE_X86_32_ASM
37  #elif defined(BOTAN_TARGET_ARCH_IS_X86_64) && (BOTAN_MP_WORD_BITS == 64)
38  #define BOTAN_MP_USE_X86_64_ASM
39  #endif
40 
41 #endif
42 
43 /*
44 * Word Multiply/Add
45 */
46 inline word word_madd2(word a, word b, word* c)
47  {
48 #if defined(BOTAN_MP_USE_X86_32_ASM)
49  asm(R"(
50  mull %[b]
51  addl %[c],%[a]
52  adcl $0,%[carry]
53  )"
54  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
55  : "0"(a), "1"(b), [c]"g"(*c) : "cc");
56 
57  return a;
58 
59 #elif defined(BOTAN_MP_USE_X86_64_ASM)
60  asm(R"(
61  mulq %[b]
62  addq %[c],%[a]
63  adcq $0,%[carry]
64  )"
65  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*c)
66  : "0"(a), "1"(b), [c]"g"(*c) : "cc");
67 
68  return a;
69 
70 #elif defined(BOTAN_HAS_MP_DWORD)
71  const dword s = static_cast<dword>(a) * b + *c;
72  *c = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
73  return static_cast<word>(s);
74 #else
75  static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
76 
77  word hi = 0, lo = 0;
78 
79  mul64x64_128(a, b, &lo, &hi);
80 
81  lo += *c;
82  hi += (lo < *c); // carry?
83 
84  *c = hi;
85  return lo;
86 #endif
87  }
88 
89 /*
90 * Word Multiply/Add
91 */
92 inline word word_madd3(word a, word b, word c, word* d)
93  {
94 #if defined(BOTAN_MP_USE_X86_32_ASM)
95  asm(R"(
96  mull %[b]
97 
98  addl %[c],%[a]
99  adcl $0,%[carry]
100 
101  addl %[d],%[a]
102  adcl $0,%[carry]
103  )"
104  : [a]"=a"(a), [b]"=rm"(b), [carry]"=&d"(*d)
105  : "0"(a), "1"(b), [c]"g"(c), [d]"g"(*d) : "cc");
106 
107  return a;
108 
109 #elif defined(BOTAN_MP_USE_X86_64_ASM)
110  asm(R"(
111  mulq %[b]
112  addq %[c],%[a]
113  adcq $0,%[carry]
114  addq %[d],%[a]
115  adcq $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_HAS_MP_DWORD)
123  const dword s = static_cast<dword>(a) * b + c + *d;
124  *d = static_cast<word>(s >> BOTAN_MP_WORD_BITS);
125  return static_cast<word>(s);
126 #else
127  static_assert(BOTAN_MP_WORD_BITS == 64, "Unexpected word size");
128 
129  word hi = 0, lo = 0;
130 
131  mul64x64_128(a, b, &lo, &hi);
132 
133  lo += c;
134  hi += (lo < c); // carry?
135 
136  lo += *d;
137  hi += (lo < *d); // carry?
138 
139  *d = hi;
140  return lo;
141 #endif
142  }
143 
144 }
145 
146 #endif
void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)
Definition: mul128.h:85
void carry(int64_t &h0, int64_t &h1)
word word_madd3(word a, word b, word c, word *d)
Definition: mp_madd.h:92
word word_madd2(word a, word b, word *c)
Definition: mp_madd.h:46
Definition: alg_id.cpp:13