Botan 3.14.1
Crypto and TLS for C&
monty_exp_avx512.cpp
Go to the documentation of this file.
1/*
2* Montgomery exponentiation using AVX-512 IFMA
3* (C) 2026 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/internal/monty_exp_avx512.h>
9
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/mp_core.h>
12#include <botan/internal/mul128.h>
13#include <botan/internal/simd_8x64.h>
14#include <array>
15
16namespace Botan {
17
18namespace {
19
20static_assert(std::same_as<word, uint64_t>);
21
22constexpr size_t DigitBits = 52;
23constexpr uint64_t DigitMask = (static_cast<uint64_t>(1) << DigitBits) - 1;
24
25/*
26* Number of radix 2^52 digits used for a modulus of p_bits
27*
28* The two extra bits ensure 4*p < 2^(52*k), so the Montgomery products of
29* values in [0, 2p) are again in [0, 2p) without any conditional subtraction.
30*/
31constexpr size_t ifma_digits(size_t p_bits) {
32 return (p_bits + 2 + DigitBits - 1) / DigitBits;
33}
34
35/*
36* Low 52 bits of a*b
37*
38* The product is kept opaque to the optimizer; otherwise the SLP vectorizer
39* folds pairs of these into a high latency vector multiply, which puts the
40* vector unit on the critical path the scalar chain exists to avoid.
41*/
42inline uint64_t lo52(uint64_t a, uint64_t b) {
43 return CT::value_barrier(a * b) & DigitMask;
44}
45
46/*
47* Bits 52..103 of a*b, for a and b < 2^52
48*
49* Pre-shifting a by 12 places exactly these bits in the upper word
50*/
51inline uint64_t hi52(uint64_t a, uint64_t b) {
52 uint64_t lo = 0;
53 uint64_t hi = 0;
54 mul64x64_128(a << (64 - DigitBits), b, &lo, &hi);
55 return hi;
56}
57
58template <size_t N>
59BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX512 void shift_lanes_down(std::array<SIMD_8x64, N>& v) {
60 for(size_t i = 0; i + 1 < N; ++i) {
61 v[i] = SIMD_8x64::alignr<1>(v[i + 1], v[i]);
62 }
63 v[N - 1] = SIMD_8x64::alignr<1>(SIMD_8x64(), v[N - 1]);
64}
65
66template <size_t N>
67BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX512 void shift_lanes_up(std::array<SIMD_8x64, N>& v) {
68 for(size_t i = N - 1; i > 0; --i) {
69 v[i] = SIMD_8x64::alignr<7>(v[i], v[i - 1]);
70 }
71 v[0] = SIMD_8x64::alignr<7>(v[0], SIMD_8x64());
72}
73
74/*
75* Convert lanes holding values below 2^60 into proper 52 bit digits
76*/
77template <size_t N>
78BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX512 void normalize_digits(std::array<SIMD_8x64, N>& r) {
79 static_assert(N <= 16, "Lane masks must fit in two words");
80
81 const auto mask = SIMD_8x64::splat(DigitMask);
82 const auto one = SIMD_8x64::splat(1);
83
84 // Pass the excess above 52 bits one lane up; afterwards all lanes are below 2^53
85 auto carry = r;
86 for(size_t i = 0; i != N; ++i) {
87 carry[i] = carry[i].template shr<DigitBits>();
88 r[i] &= mask;
89 }
90 shift_lanes_up(carry);
91 for(size_t i = 0; i != N; ++i) {
92 r[i] += carry[i];
93 }
94
95 /*
96 * Now a lane >= 2^52 generates a carry and a lane == 2^52-1 propagates one.
97 * Integer addition on the lane masks resolves the entire carry chain at once:
98 * carry_in = ((gen << 1) + prop) ^ prop, computed here on two words.
99 */
100 std::array<uint64_t, 2> gen = {};
101 std::array<uint64_t, 2> prop = {};
102 for(size_t i = 0; i != N; ++i) {
103 gen[i / 8] |= static_cast<uint64_t>(r[i].lanes_gt(mask)) << (8 * (i % 8));
104 prop[i / 8] |= static_cast<uint64_t>(r[i].lanes_eq(mask)) << (8 * (i % 8));
105 }
106
107 uint64_t c = 0;
108 const uint64_t sum0 = word_add(gen[0] << 1, prop[0], &c);
109 const uint64_t sum1 = word_add((gen[1] << 1) | (gen[0] >> 63), prop[1], &c);
110 const std::array<uint64_t, 2> carry_in = {sum0 ^ prop[0], sum1 ^ prop[1]};
111
112 for(size_t i = 0; i != N; ++i) {
113 const auto lanes = static_cast<uint8_t>(carry_in[i / 8] >> (8 * (i % 8)));
114 r[i] = SIMD_8x64::masked_add(lanes, r[i], one) & mask;
115 }
116}
117
118/*
119* One round of operand scanning Montgomery multiplication: add a*b_i and p*y_i
120* to the accumulators, shifting them down a lane in between. The low halves of
121* the products are added before the shift and the high halves after it, which
122* puts them in the right lane for free. Using separate accumulators for the
123* a*b and p*y products halves the dependency chain.
124*
125* Only vectors First and up of a take part, and within vector First only the
126* lanes selected by a_mask; squaring uses this to skip the lanes below the
127* current digit.
128*/
129template <size_t First, size_t N>
130BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX512 void monty_round(std::array<SIMD_8x64, N>& acc_a,
131 std::array<SIMD_8x64, N>& acc_p,
132 const std::array<SIMD_8x64, N>& av,
133 const std::array<SIMD_8x64, N>& pv,
134 const SIMD_8x64& bv,
135 const SIMD_8x64& yv,
136 uint8_t a_mask) {
137 acc_a[First] = acc_a[First].masked_madd52lo(a_mask, av[First], bv);
138 for(size_t j = First + 1; j < N; ++j) {
139 acc_a[j] = acc_a[j].madd52lo(av[j], bv);
140 }
141 for(size_t j = 0; j != N; ++j) {
142 acc_p[j] = acc_p[j].madd52lo(pv[j], yv);
143 }
144
145 shift_lanes_down(acc_a);
146 shift_lanes_down(acc_p);
147
148 acc_a[First] = acc_a[First].masked_madd52hi(a_mask, av[First], bv);
149 for(size_t j = First + 1; j < N; ++j) {
150 acc_a[j] = acc_a[j].madd52hi(av[j], bv);
151 }
152 for(size_t j = 0; j != N; ++j) {
153 acc_p[j] = acc_p[j].madd52hi(pv[j], yv);
154 }
155}
156
157/*
158* Store the final accumulator as normalized digits. The vector lanes never
159* received the limb 0 carries; the last one is still missing.
160*/
161template <size_t N>
162BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX512 void store_digits(std::array<SIMD_8x64, N>& acc,
163 uint64_t carry,
164 std::span<uint64_t, 8 * N> z) {
165 acc[0] = SIMD_8x64::masked_add(0x01, acc[0], SIMD_8x64::splat(carry));
166
167 normalize_digits(acc);
168
169 for(size_t i = 0; i != N; ++i) {
170 acc[i].store_le(&z[8 * i]);
171 }
172}
173
174// Return true if the words encode a value below 2^bits (used in debug assertions)
175[[maybe_unused]] bool fits_in_bits(std::span<const word> words, size_t bits) {
176 for(size_t i = 0; i != words.size(); ++i) {
177 const size_t offset = WordInfo<word>::bits * i;
178 if(offset >= bits && words[i] != 0) {
179 return false;
180 }
181 if(offset < bits && offset + WordInfo<word>::bits > bits && (words[i] >> (bits - offset)) != 0) {
182 return false;
183 }
184 }
185 return true;
186}
187
188/**
189* A modulus in radix 2^52 form, with Montgomery multiplication using IFMA
190*
191* N is the number of 8 lane vectors required to hold the digits
192*/
193template <size_t N>
194class IFMA_Modulus final {
195 public:
196 static constexpr size_t Lanes = 8 * N;
197
198 using Digits = std::array<uint64_t, Lanes>;
199
200 explicit IFMA_Modulus(const Montgomery_Params& params);
201
202 const Montgomery_Params& params() const { return m_params; }
203
204 /**
205 * Montgomery multiplication: z = a*b / 2^(52*k) mod p
206 *
207 * Inputs and output are in [0, 2p). The output may alias either input.
208 */
209 void mul(std::span<uint64_t, Lanes> z,
210 std::span<const uint64_t, Lanes> a,
211 std::span<const uint64_t, Lanes> b) const;
212
213 /**
214 * Montgomery squaring: z = a*a / 2^(52*k) mod p
215 *
216 * Input and output are in [0, 2p). The output may alias the input.
217 */
218 void sqr(std::span<uint64_t, Lanes> z, std::span<const uint64_t, Lanes> a) const;
219
220 /**
221 * Return 1 in the radix 2^52 Montgomery domain
222 */
223 const Digits& one() const { return m_one; }
224
225 /**
226 * Convert a Montgomery_Int into the radix 2^52 Montgomery domain
227 */
228 Digits from_monty_int(const Montgomery_Int& x) const;
229
230 /**
231 * Convert from the radix 2^52 Montgomery domain into a Montgomery_Int
232 */
233 Montgomery_Int to_monty_int(std::span<const uint64_t, Lanes> x) const;
234
235 private:
236 template <size_t First>
237 void sqr_rounds(std::array<SIMD_8x64, N>& acc_a,
238 std::array<SIMD_8x64, N>& acc_p,
239 const std::array<SIMD_8x64, N>& av,
240 const std::array<SIMD_8x64, N>& pv,
241 std::span<const uint64_t, Lanes> a,
242 std::span<const uint64_t, 2 * Lanes> diag,
243 uint64_t& s,
244 uint64_t& carry) const;
245
246 // Convert words encoding a value below 2^(52*k) into digits
247 Digits to_digits(std::span<const word> words) const;
248
249 Montgomery_Params m_params;
250 Digits m_p;
251 Digits m_r1; // R = 2^(64*n) mod p, the Montgomery_Int domain constant
252 Digits m_c; // R'^2/R = 2^(104*k - 64*n) mod p, converting R*x into R'*x
253 Digits m_one; // R' = 2^(52*k) mod p
254 uint64_t m_k0;
255 size_t m_digits;
256};
257
258template <size_t N>
259IFMA_Modulus<N>::IFMA_Modulus(const Montgomery_Params& params) :
260 m_params(params), m_k0(params.p_dash() & DigitMask), m_digits(ifma_digits(params.p().bits())) {
261 BOTAN_ASSERT_NOMSG(m_digits > 1 && m_digits <= Lanes);
262
263 m_p = to_digits(params.p()._as_span());
264 m_r1 = to_digits(params.R1()._as_span());
265
266 /*
267 * Derive C = 2^(2*rp - r) from R = 2^r or R^2 = 2^(2*r) using the existing
268 * Montgomery multiplication, which computes x*y*2^(-r).
269 */
270 const size_t r = WordInfo<word>::bits * params.p_words();
271 const size_t rp = DigitBits * m_digits;
272
273 secure_vector<word> ws;
274 if(rp >= r) {
275 m_c = to_digits(params.mul(params.R2(), BigInt::power_of_2(2 * (rp - r)), ws)._as_span());
276 } else {
277 m_c = to_digits(params.mul(params.R1(), BigInt::power_of_2(2 * rp - r), ws)._as_span());
278 }
279
280 // R * C / R' = R'
281 this->mul(m_one, m_r1, m_c);
282}
283
284template <size_t N>
285typename IFMA_Modulus<N>::Digits IFMA_Modulus<N>::to_digits(std::span<const word> words) const {
286 Digits d = {};
287 for(size_t i = 0; i != m_digits; ++i) {
288 const size_t bit = DigitBits * i;
289 const size_t w = bit / 64;
290 const size_t sh = bit % 64;
291
292 uint64_t v = (w < words.size()) ? (words[w] >> sh) : 0;
293 if(sh > 64 - DigitBits && w + 1 < words.size()) {
294 v |= words[w + 1] << (64 - sh);
295 }
296 d[i] = v & DigitMask;
297 }
298
299 BOTAN_DEBUG_ASSERT(fits_in_bits(words, DigitBits * m_digits));
300
301 return d;
302}
303
304template <size_t N>
305typename IFMA_Modulus<N>::Digits IFMA_Modulus<N>::from_monty_int(const Montgomery_Int& x) const {
306 // x is R*v mod p, multiplying by C converts it to R'*v
307 const Digits v = to_digits(x.repr());
308 Digits r = {};
309 this->mul(r, v, m_c);
310 return r;
311}
312
313template <size_t N>
314Montgomery_Int IFMA_Modulus<N>::to_monty_int(std::span<const uint64_t, Lanes> x) const {
315 Digits z = {};
316 this->mul(z, x, m_r1);
317
318 // z is now x*R mod p in [0, 2p), as normalized digits
319 const size_t n = m_params.p_words();
320 secure_vector<word> w(n + 1);
321 for(size_t i = 0; i != m_digits; ++i) {
322 const size_t bit = DigitBits * i;
323 const size_t wi = bit / 64;
324 const size_t sh = bit % 64;
325
326 w[wi] |= z[i] << sh;
327 if(sh > 64 - DigitBits && wi + 1 < w.size()) {
328 w[wi + 1] |= z[i] >> (64 - sh);
329 }
330 }
331
332 secure_vector<word> r(n);
333 bigint_monty_maybe_sub(n, r.data(), w[n], w.data(), m_params.p()._data());
334 return Montgomery_Int(m_params, std::span<const word>{r});
335}
336
337/*
338* Operand scanning Montgomery multiplication in radix 2^52
339*
340* Each round multiplies the whole of a (and of p) by one digit of b (resp
341* the quotient digit y) using IFMA, then shifts the accumulator down a lane.
342*
343* The lowest lane is where the next quotient digit comes from, and waiting
344* for the vector unit to produce it would stall the whole loop. Instead the
345* scalar unit tracks the exact value of limb 0 one round ahead, using the
346* lane 1 values from the previous round, and the vector lanes never see the
347* limb 0 carries at all; the final one is added back at the end.
348*/
349template <size_t N>
350void BOTAN_FN_ISA_AVX512 IFMA_Modulus<N>::mul(std::span<uint64_t, Lanes> z,
351 std::span<const uint64_t, Lanes> a,
352 std::span<const uint64_t, Lanes> b) const {
353 std::array<SIMD_8x64, N> av;
354 std::array<SIMD_8x64, N> pv;
355 for(size_t i = 0; i != N; ++i) {
356 av[i] = SIMD_8x64::load_le(&a[8 * i]);
357 pv[i] = SIMD_8x64::load_le(&m_p[8 * i]);
358 }
359
360 /*
361 * The contributions of a*b_i to limbs 0 and 1 in each round depend only
362 * on b, so they are computed for all rounds up front
363 */
364 std::array<uint64_t, Lanes> ab0 = {}; // lo52(a0 * b_i)
365 std::array<uint64_t, Lanes> ab1 = {}; // hi52(a0 * b_i) + lo52(a1 * b_i)
366 {
367 const auto a0v = SIMD_8x64::splat(a[0]);
368 const auto a1v = SIMD_8x64::splat(a[1]);
369 for(size_t i = 0; i != N; ++i) {
370 const auto bv = SIMD_8x64::load_le(&b[8 * i]);
371 SIMD_8x64().madd52lo(a0v, bv).store_le(&ab0[8 * i]);
372 SIMD_8x64().madd52hi(a0v, bv).madd52lo(a1v, bv).store_le(&ab1[8 * i]);
373 }
374 }
375
376 std::array<SIMD_8x64, N> acc_a;
377 std::array<SIMD_8x64, N> acc_p;
378
379 const uint64_t p0 = m_p[0];
380 const uint64_t p1 = m_p[1];
381 const uint64_t k0 = m_k0;
382
383 uint64_t s = 0; // exact value of limb 0
384 uint64_t carry = 0;
385
386 for(size_t i = 0; i != m_digits; ++i) {
387 const uint64_t t = s + ab0[i];
388 const uint64_t y = (t * k0) & DigitMask;
389
390 // y was chosen such that t + lo52(p0 * y) is a multiple of 2^52
391 carry = (t + DigitMask) >> DigitBits;
392
393 // Everything that lands in limb 1 this round is the next limb 0
394 const uint64_t limb1 = (acc_a[0] + acc_p[0]).template extract<1>();
395 s = limb1 + carry + hi52(p0, y) + lo52(p1, y) + ab1[i];
396
397 monty_round<0>(acc_a, acc_p, av, pv, SIMD_8x64::splat(b[i]), SIMD_8x64::splat(y), 0xFF);
398 }
399
400 for(size_t i = 0; i != N; ++i) {
401 acc_a[i] += acc_p[i];
402 }
403
404 store_digits(acc_a, carry, z);
405}
406
407/*
408* Montgomery squaring
409*
410* Each product a_j*a_i with j != i appears twice in the square, so each round
411* only forms the products with j above the current digit i, and the
412* accumulator is doubled whenever it is read. That skips entire vectors once
413* the digit has passed them. The squares a_i^2 are added separately: their
414* low half belongs at position 2i and their high half at position 2i+1.
415*/
416template <size_t N>
417void BOTAN_FN_ISA_AVX512 IFMA_Modulus<N>::sqr(std::span<uint64_t, Lanes> z, std::span<const uint64_t, Lanes> a) const {
418 std::array<SIMD_8x64, N> av;
419 std::array<SIMD_8x64, N> pv;
420 for(size_t i = 0; i != N; ++i) {
421 av[i] = SIMD_8x64::load_le(&a[8 * i]);
422 pv[i] = SIMD_8x64::load_le(&m_p[8 * i]);
423 }
424
425 std::array<uint64_t, 2 * Lanes> diag = {};
426 for(size_t i = 0; i != N; ++i) {
427 const auto lo = SIMD_8x64().madd52lo(av[i], av[i]);
428 const auto hi = SIMD_8x64().madd52hi(av[i], av[i]);
429 SIMD_8x64::interleave_lo(lo, hi).store_le(&diag[16 * i]);
430 SIMD_8x64::interleave_hi(lo, hi).store_le(&diag[16 * i + 8]);
431 }
432
433 std::array<SIMD_8x64, N> acc_a;
434 std::array<SIMD_8x64, N> acc_p;
435
436 uint64_t s = diag[0]; // exact value of limb 0
437 uint64_t carry = 0;
438
439 this->sqr_rounds<0>(acc_a, acc_p, av, pv, a, diag, s, carry);
440
441 // The positions from k onwards are what remains after the k shifts
442 for(size_t i = 0; i != N; ++i) {
443 acc_a[i] = acc_a[i] + acc_a[i] + acc_p[i] + SIMD_8x64::load_le(&diag[m_digits + 8 * i]);
444 }
445
446 store_digits(acc_a, carry, z);
447}
448
449/*
450* The rounds for the digits held in vector First, in which the products with
451* the lanes below the digit are skipped
452*/
453template <size_t N>
454template <size_t First>
455void BOTAN_FN_ISA_AVX512 IFMA_Modulus<N>::sqr_rounds(std::array<SIMD_8x64, N>& acc_a,
456 std::array<SIMD_8x64, N>& acc_p,
457 const std::array<SIMD_8x64, N>& av,
458 const std::array<SIMD_8x64, N>& pv,
459 std::span<const uint64_t, Lanes> a,
460 std::span<const uint64_t, 2 * Lanes> diag,
461 uint64_t& s,
462 uint64_t& carry) const {
463 const uint64_t p0 = m_p[0];
464 const uint64_t p1 = m_p[1];
465 const uint64_t k0 = m_k0;
466
467 // The only product below the diagonal landing in limb 1 is a_0*a_1 in round 0
468 uint64_t a0a1 = (First == 0) ? 2 * lo52(a[0], a[1]) : 0;
469
470 for(size_t d = 0; d != 8; ++d) {
471 const size_t i = 8 * First + d;
472 if(i == m_digits) {
473 return;
474 }
475
476 const uint64_t y = (s * k0) & DigitMask;
477
478 // y was chosen such that s + lo52(p0 * y) is a multiple of 2^52
479 carry = (s + DigitMask) >> DigitBits;
480
481 // Everything that lands in limb 1 this round is the next limb 0
482 const uint64_t limb1 = (acc_a[0] + acc_a[0] + acc_p[0]).template extract<1>();
483 s = limb1 + carry + hi52(p0, y) + lo52(p1, y) + diag[i + 1] + a0a1;
484 a0a1 = 0;
485
486 const auto a_mask = static_cast<uint8_t>(0xFF << (d + 1));
487 monty_round<First>(acc_a, acc_p, av, pv, SIMD_8x64::splat(a[i]), SIMD_8x64::splat(y), a_mask);
488 }
489
490 if constexpr(First + 1 < N) {
491 this->sqr_rounds<First + 1>(acc_a, acc_p, av, pv, a, diag, s, carry);
492 }
493}
494
495template <size_t N>
496class Montgomery_Exponentiation_AVX512 final : public Montgomery_Exponentiation_State {
497 public:
498 static constexpr size_t Lanes = IFMA_Modulus<N>::Lanes;
499
500 using Digits = typename IFMA_Modulus<N>::Digits;
501
502 Montgomery_Exponentiation_AVX512(const Montgomery_Int& g, size_t window_bits) :
503 m_monty(g._params()), m_window_bits(window_bits) {
504 const size_t window_size = static_cast<size_t>(1) << m_window_bits;
505
506 m_table.resize(window_size * Lanes);
507
508 const Digits g_digits = m_monty.from_monty_int(g);
509
510 copy_mem(entry(0), std::span{m_monty.one()});
511 copy_mem(entry(1), std::span{g_digits});
512
513 for(size_t i = 2; i != window_size; ++i) {
514 if(i % 2 == 0) {
515 m_monty.sqr(entry(i), entry(i / 2));
516 } else {
517 m_monty.mul(entry(i), entry(1), entry(i - 1));
518 }
519 }
520 }
521
522 Montgomery_Int exponentiation(const BigInt& scalar, size_t max_k_bits) const override {
523 BOTAN_ARG_CHECK(scalar.signum() >= 0, "Invalid scalar for Montgomery exponentiation");
524 BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
525
526 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
527
528 if(exp_nibbles == 0) {
529 return Montgomery_Int::one(m_monty.params());
530 }
531
532 Digits x = {};
533 Digits e = {};
534
535 ct_lookup(x, scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits));
536
537 for(size_t i = exp_nibbles - 1; i > 0; --i) {
538 for(size_t j = 0; j != m_window_bits; ++j) {
539 m_monty.sqr(x, x);
540 }
541 ct_lookup(e, scalar.get_substring(m_window_bits * (i - 1), m_window_bits));
542 m_monty.mul(x, x, e);
543 }
544
545 return m_monty.to_monty_int(x);
546 }
547
548 Montgomery_Int exponentiation_vartime(const BigInt& scalar) const override {
549 const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
550
551 if(exp_nibbles == 0) {
552 return Montgomery_Int::one(m_monty.params());
553 }
554
555 Digits x = {};
556 copy_mem(std::span{x}, entry(scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits)));
557
558 for(size_t i = exp_nibbles - 1; i > 0; --i) {
559 for(size_t j = 0; j != m_window_bits; ++j) {
560 m_monty.sqr(x, x);
561 }
562
563 const uint32_t nibble = scalar.get_substring(m_window_bits * (i - 1), m_window_bits);
564 if(nibble > 0) {
565 m_monty.mul(x, x, entry(nibble));
566 }
567 }
568
569 return m_monty.to_monty_int(x);
570 }
571
572 private:
573 std::span<uint64_t, Lanes> entry(size_t i) {
574 return std::span{m_table}.subspan(i * Lanes).template first<Lanes>();
575 }
576
577 std::span<const uint64_t, Lanes> entry(size_t i) const {
578 return std::span{m_table}.subspan(i * Lanes).template first<Lanes>();
579 }
580
581 void BOTAN_FN_ISA_AVX512 ct_lookup(Digits& out, size_t idx) const {
582 std::array<SIMD_8x64, N> acc;
583
584 const size_t window_size = static_cast<size_t>(1) << m_window_bits;
585
586 for(size_t i = 0; i != window_size; ++i) {
587 const auto mask = SIMD_8x64::splat(CT::Mask<uint64_t>::is_equal(idx, i).value());
588 const auto e = entry(i);
589 for(size_t j = 0; j != N; ++j) {
590 acc[j] = SIMD_8x64::choose(mask, SIMD_8x64::load_le(&e[8 * j]), acc[j]);
591 }
592 }
593
594 for(size_t j = 0; j != N; ++j) {
595 acc[j].store_le(&out[8 * j]);
596 }
597 }
598
599 IFMA_Modulus<N> m_monty;
600 secure_vector<uint64_t> m_table;
601 size_t m_window_bits;
602};
603
604template <size_t N>
605std::unique_ptr<Montgomery_Exponentiation_State> make_monty_exp(const Montgomery_Int& g, size_t window_bits) {
606 return std::make_unique<Montgomery_Exponentiation_AVX512<N>>(g, window_bits);
607}
608
609} // namespace
610
611std::unique_ptr<Montgomery_Exponentiation_State> make_monty_exp_avx512(const Montgomery_Int& g, size_t window_bits) {
612 const size_t vectors = (ifma_digits(g._params().p().bits()) + 7) / 8;
613
614 switch(vectors) {
615 case 2: /* 415 - 830 bits */
616 return make_monty_exp<2>(g, window_bits);
617 case 3: /* 831 - 1246 bits */
618 return make_monty_exp<3>(g, window_bits);
619 case 4: /* 1247 - 1662 bits */
620 return make_monty_exp<4>(g, window_bits);
621 case 5: /* 1663 - 2078 bits */
622 return make_monty_exp<5>(g, window_bits);
623 case 6: /* 2079 - 2494 bits */
624 return make_monty_exp<6>(g, window_bits);
625 case 7: /* 2495 - 2910 bits */
626 return make_monty_exp<7>(g, window_bits);
627 case 8: /* 2911 - 3326 bits */
628 return make_monty_exp<8>(g, window_bits);
629 case 9: /* 3327 - 3742 bits */
630 return make_monty_exp<9>(g, window_bits);
631 case 10: /* 3743 - 4158 bits */
632 return make_monty_exp<10>(g, window_bits);
633 default:
634 // Moduli under 415 bits or over 4158 bits do not seem of practical interest
635 return nullptr;
636 }
637}
638
639} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
size_t bits() const
Definition bigint.cpp:308
const Montgomery_Params & _params() const
Definition monty.h:216
const BigInt & p() const
Definition monty.h:41
static SIMD_8x64 BOTAN_FN_ISA_SIMD_8X64 masked_add(uint8_t lanes, const SIMD_8x64 &a, const SIMD_8x64 &b)
Definition simd_8x64.h:314
static BOTAN_FN_ISA_SIMD_8X64 SIMD_8x64 splat(uint64_t v)
Definition simd_8x64.h:319
static SIMD_8x64 BOTAN_FN_ISA_SIMD_8X64 alignr(const SIMD_8x64 &hi, const SIMD_8x64 &lo)
Definition simd_8x64.h:239
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
constexpr T value_barrier(T x)
constexpr auto word_add(W x, W y, W *carry) -> W
Definition mp_asmi.h:260
std::unique_ptr< Montgomery_Exponentiation_State > make_monty_exp_avx512(const Montgomery_Int &g, size_t window_bits)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
Definition mp_core.h:229
constexpr void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)
Definition mul128.h:24