Botan 3.14.1
Crypto and TLS for C&
mp_monty_mulx.cpp
Go to the documentation of this file.
1/*
2* (C) 2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/mp_mulx.h>
8
9#include <botan/mem_ops.h>
10#include <botan/internal/mp_core.h>
11#include <array>
12
13namespace Botan {
14
15namespace {
16
17// NOLINTBEGIN(*-macro-usage,*-no-assembler,*-const-correctness)
18// clang-format off
19
20/*
21* One word of out = t + x * b: the high half of the previous product arrives
22* on the overflow flag chain (ADOX) and the low half of this one on the
23* carry flag chain (ADCX), so the two chains never wait on each other.
24*/
25#define BOTAN_MULADD_STEP(D) \
26 "movq " D "(%[t]), %[tmp]\n\t" \
27 "adox %[carry], %[tmp]\n\t" \
28 "mulx " D "(%[x]), %[lo], %[carry]\n\t" \
29 "adcx %[lo], %[tmp]\n\t" \
30 "movq %[tmp], " D "(%[out])\n\t"
31
32/*
33* out[0..K) = t[0..K) + x[0..K) * b + carry for K steps, returning the carry
34* out. The two flag carries left after the last step are folded into its
35* product's high half, which fits since the sum is at most b.
36*/
37#define BOTAN_MULADD_ASM(STEPS) \
38 asm volatile("xorl %k[zero], %k[zero]\n\t" \
39 STEPS \
40 "adox %[zero], %[carry]\n\t" \
41 "adcx %[zero], %[carry]\n\t" \
42 : [carry] "+&r"(carry), [tmp] "=&r"(tmp), [lo] "=&r"(lo), [zero] "=&r"(zero) \
43 : [out] "r"(out), [t] "r"(t), [x] "r"(x), "d"(b) \
44 : "cc", "memory")
45
46#define BOTAN_MULADD_STEPS4 \
47 BOTAN_MULADD_STEP("0") \
48 BOTAN_MULADD_STEP("8") \
49 BOTAN_MULADD_STEP("16") \
50 BOTAN_MULADD_STEP("24")
51
52#define BOTAN_MULADD_STEPS8 \
53 BOTAN_MULADD_STEPS4 \
54 BOTAN_MULADD_STEP("32") \
55 BOTAN_MULADD_STEP("40") \
56 BOTAN_MULADD_STEP("48") \
57 BOTAN_MULADD_STEP("56")
58
59// out[0..8) = t[0..8) + x[0..8) * b + carry; out may be t or t - 1
60BOTAN_FORCE_INLINE word muladd8(word* out, const word* t, const word* x, word b, word carry) {
61 word tmp = 0;
62 word lo = 0;
63 word zero = 0;
66 return carry;
67}
68
69// out[0..4) = t[0..4) + x[0..4) * b + carry; out may be t or t - 1
70BOTAN_FORCE_INLINE word muladd4(word* out, const word* t, const word* x, word b, word carry) {
71 word tmp = 0;
72 word lo = 0;
73 word zero = 0;
76 return carry;
77}
78
79// clang-format on
80// NOLINTEND(*-macro-usage,*-no-assembler,*-const-correctness)
81
82/*
83* out[0..N+2) = t[0..N+2) + x[0..N) * b + c * B^(N+1), returning the carry
84* out of out[N+1]. out may be t or t - 1.
85*/
86BOTAN_FORCE_INLINE word monty_row(word* out, const word* t, const word* x, size_t N, word b, word c) {
87 word carry = 0;
88 // Advancing the pointers, rather than indexing, keeps the compiler from generating a slower loop
89 for(size_t i = N / 8; i != 0; --i) {
90 carry = muladd8(out, t, x, b, carry);
91 out += 8;
92 t += 8;
93 x += 8;
94 }
95 if(N % 8 >= 4) {
96 carry = muladd4(out, t, x, b, carry);
97 out += 4;
98 t += 4;
99 x += 4;
100 }
101 for(size_t i = N % 4; i != 0; --i) {
102 *out++ = word_madd3(*x++, b, *t++, &carry);
103 }
104
105 word c2 = 0;
106 out[0] = word_add(t[0], carry, &c2);
107 out[1] = word_add(t[1], c, &c2);
108 return c2;
109}
110
111} // namespace
112
113void bigint_mulx_monty_mul(word z[], const word x[], const word y[], const word p[], size_t N, word p_dash, word ws[]) {
114 // t[-1] receives the word shifted out by each reduction row
115 word* t = ws + 1;
116 clear_mem(ws, N + 3);
117
118 for(size_t i = 0; i != N; ++i) {
119 monty_row(t, t, x, N, y[i], 0);
120 const word m = t[0] * p_dash;
121 monty_row(t - 1, t, p, N, m, 0);
122 t[N + 1] = 0;
123 }
124
125 // The result is below 2p, with t[N] holding its top bit
126 bigint_monty_maybe_sub(N, z, t[N], t, p);
127}
128
129void bigint_mulx_monty_sqr(word z[], const word x[], const word p[], size_t N, word p_dash, word ws[]) {
130 bigint_mulx_sqr(ws, x, N);
131 bigint_mulx_monty_redc(z, ws, p, N, p_dash);
132}
133
134void bigint_mulx_sqr(word z[], const word x[], size_t N) {
135 clear_mem(z, 2 * N + 1);
136
137 /*
138 * x is split into a leading block of N % 8 words followed by blocks of 8
139 * words. Rows from the leading block cover every product x[i]*x[j] with
140 * j > i; rows from the other blocks cover only products with x[j] in a
141 * later block, so their lengths are multiples of 8.
142 */
143 const size_t lead = N % 8;
144
145 for(size_t i = 0; i != lead; ++i) {
146 monty_row(z + 2 * i + 1, z + 2 * i + 1, x + i + 1, N - i - 1, x[i], 0);
147 }
148
149 for(size_t b = lead; b + 8 < N; b += 8) {
150 for(size_t i = b; i != b + 8; ++i) {
151 monty_row(z + i + b + 8, z + i + b + 8, x + b + 8, N - b - 8, x[i], 0);
152 }
153 }
154
155 // Double the products while adding the squares not yet included, which together cover z[0..2N)
156 word carry = 0;
157 word top = 0;
158 auto double_and_add = [&](size_t k, word s) {
159 const word w = z[k];
160 z[k] = word_add((w << 1) | top, s, &carry);
161 top = w >> (WordInfo<word>::bits - 1);
162 };
163
164 for(size_t i = 0; i != lead; ++i) {
165 word hi = 0;
166 const word lo = word_madd2(x[i], x[i], &hi);
167 double_and_add(2 * i, lo);
168 double_and_add(2 * i + 1, hi);
169 }
170
171 for(size_t b = lead; b != N; b += 8) {
172 std::array<word, 16> sq{};
173 bigint_mulx_sqr8(sq.data(), x + b);
174 for(size_t k = 0; k != 16; ++k) {
175 double_and_add(2 * b + k, sq[k]);
176 }
177 }
178
179 // The square fits in 2N words
180 BOTAN_DEBUG_ASSERT(carry == 0 && top == 0);
181}
182
183void bigint_mulx_monty_redc(word r[], word z[], const word p[], size_t N, word p_dash) {
184 z[2 * N] = 0;
185
186 word c = 0;
187 for(size_t i = 0; i != N; ++i) {
188 const word m = z[i] * p_dash;
189 c = monty_row(z + i, z + i, p, N, m, c);
190 }
191
192 // The sum is below 2p * B^N, so the final carry is zero and the top bit is z[2N]
193 BOTAN_DEBUG_ASSERT(c == 0);
194 bigint_monty_maybe_sub(N, r, z[2 * N], z + N, p);
195}
196
197} // namespace Botan
198
199#undef BOTAN_MULADD_STEP
200#undef BOTAN_MULADD_ASM
201#undef BOTAN_MULADD_STEPS4
202#undef BOTAN_MULADD_STEPS8
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
#define BOTAN_MULADD_ASM(STEPS)
#define BOTAN_MULADD_STEPS8
#define BOTAN_MULADD_STEPS4
void bigint_mulx_monty_mul(word z[], const word x[], const word y[], const word p[], size_t N, word p_dash, word ws[])
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
void bigint_mulx_monty_redc(word r[], word z[], const word p[], size_t N, word p_dash)
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:111
void bigint_mulx_sqr(word z[], const word x[], size_t N)
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
void bigint_mulx_monty_sqr(word z[], const word x[], const word p[], size_t N, word p_dash, word ws[])
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
void bigint_mulx_sqr8(word z[16], const word x[8])
Definition mp_mulx.cpp:538
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118
void unpoison_asm_output(const W *ptr)
Definition mp_asmi.h:101
constexpr auto word_madd3(W a, W b, W c, W *d) -> W
Definition mp_asmi.h:158