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 */
word_madd2(word a,word b,word * c)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 */
word_madd3(word a,word b,word c,word * d)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
147