8#include <botan/internal/monty_exp_avx512.h>
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>
20static_assert(std::same_as<word, uint64_t>);
22constexpr size_t DigitBits = 52;
23constexpr uint64_t DigitMask = (
static_cast<uint64_t
>(1) << DigitBits) - 1;
31constexpr size_t ifma_digits(
size_t p_bits) {
32 return (p_bits + 2 + DigitBits - 1) / DigitBits;
42inline uint64_t lo52(uint64_t a, uint64_t b) {
51inline uint64_t hi52(uint64_t a, uint64_t b) {
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) {
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) {
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");
86 for(
size_t i = 0; i != N; ++i) {
87 carry[i] = carry[i].template shr<DigitBits>();
90 shift_lanes_up(carry);
91 for(
size_t i = 0; i != N; ++i) {
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));
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]};
112 for(
size_t i = 0; i != N; ++i) {
113 const auto lanes =
static_cast<uint8_t
>(carry_in[i / 8] >> (8 * (i % 8)));
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,
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);
141 for(
size_t j = 0; j != N; ++j) {
142 acc_p[j] = acc_p[j].madd52lo(pv[j], yv);
145 shift_lanes_down(acc_a);
146 shift_lanes_down(acc_p);
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);
152 for(
size_t j = 0; j != N; ++j) {
153 acc_p[j] = acc_p[j].madd52hi(pv[j], yv);
162BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX512
void store_digits(std::array<SIMD_8x64, N>& acc,
164 std::span<uint64_t, 8 * N> z) {
167 normalize_digits(acc);
169 for(
size_t i = 0; i != N; ++i) {
170 acc[i].store_le(&z[8 * i]);
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) {
178 if(offset >= bits && words[i] != 0) {
181 if(offset < bits && offset +
WordInfo<word>::bits > bits && (words[i] >> (bits - offset)) != 0) {
194class IFMA_Modulus final {
196 static constexpr size_t Lanes = 8 * N;
198 using Digits = std::array<uint64_t, Lanes>;
200 explicit IFMA_Modulus(
const Montgomery_Params& params);
202 const Montgomery_Params& params()
const {
return m_params; }
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;
218 void sqr(std::span<uint64_t, Lanes> z, std::span<const uint64_t, Lanes> a)
const;
223 const Digits& one()
const {
return m_one; }
228 Digits from_monty_int(
const Montgomery_Int& x)
const;
233 Montgomery_Int to_monty_int(std::span<const uint64_t, Lanes> x)
const;
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,
244 uint64_t& carry)
const;
247 Digits to_digits(std::span<const word> words)
const;
249 Montgomery_Params m_params;
260 m_params(params), m_k0(params.p_dash() & DigitMask), m_digits(ifma_digits(params.p().bits())) {
263 m_p = to_digits(params.p()._as_span());
264 m_r1 = to_digits(params.R1()._as_span());
270 const size_t r = WordInfo<word>::bits * params.p_words();
271 const size_t rp = DigitBits * m_digits;
273 secure_vector<word> ws;
275 m_c = to_digits(params.mul(params.R2(), BigInt::power_of_2(2 * (rp - r)), ws)._as_span());
277 m_c = to_digits(params.mul(params.R1(), BigInt::power_of_2(2 * rp - r), ws)._as_span());
281 this->mul(m_one, m_r1, m_c);
285typename IFMA_Modulus<N>::Digits IFMA_Modulus<N>::to_digits(std::span<const word> words)
const {
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;
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);
296 d[i] = v & DigitMask;
305typename IFMA_Modulus<N>::Digits IFMA_Modulus<N>::from_monty_int(
const Montgomery_Int& x)
const {
307 const Digits v = to_digits(x.repr());
309 this->mul(r, v, m_c);
314Montgomery_Int IFMA_Modulus<N>::to_monty_int(std::span<const uint64_t, Lanes> x)
const {
316 this->mul(z, x, m_r1);
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;
327 if(sh > 64 - DigitBits && wi + 1 < w.size()) {
328 w[wi + 1] |= z[i] >> (64 - sh);
332 secure_vector<word> r(n);
334 return Montgomery_Int(m_params, std::span<const word>{r});
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]);
364 std::array<uint64_t, Lanes> ab0 = {};
365 std::array<uint64_t, Lanes> ab1 = {};
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]);
376 std::array<SIMD_8x64, N> acc_a;
377 std::array<SIMD_8x64, N> acc_p;
379 const uint64_t p0 = m_p[0];
380 const uint64_t p1 = m_p[1];
381 const uint64_t k0 = m_k0;
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;
391 carry = (t + DigitMask) >> DigitBits;
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];
397 monty_round<0>(acc_a, acc_p, av, pv, SIMD_8x64::splat(b[i]), SIMD_8x64::splat(y), 0xFF);
400 for(
size_t i = 0; i != N; ++i) {
401 acc_a[i] += acc_p[i];
404 store_digits(acc_a, carry, z);
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]);
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]);
433 std::array<SIMD_8x64, N> acc_a;
434 std::array<SIMD_8x64, N> acc_p;
436 uint64_t s = diag[0];
439 this->sqr_rounds<0>(acc_a, acc_p, av, pv, a, diag, s, carry);
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]);
446 store_digits(acc_a, carry, z);
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,
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;
468 uint64_t a0a1 = (First == 0) ? 2 * lo52(a[0], a[1]) : 0;
470 for(
size_t d = 0; d != 8; ++d) {
471 const size_t i = 8 * First + d;
476 const uint64_t y = (s * k0) & DigitMask;
479 carry = (s + DigitMask) >> DigitBits;
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;
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);
490 if constexpr(First + 1 < N) {
491 this->sqr_rounds<First + 1>(acc_a, acc_p, av, pv, a, diag, s, carry);
496class Montgomery_Exponentiation_AVX512 final :
public Montgomery_Exponentiation_State {
498 static constexpr size_t Lanes = IFMA_Modulus<N>::Lanes;
500 using Digits =
typename IFMA_Modulus<N>::Digits;
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;
506 m_table.resize(window_size * Lanes);
508 const Digits g_digits = m_monty.from_monty_int(g);
510 copy_mem(entry(0), std::span{m_monty.one()});
511 copy_mem(entry(1), std::span{g_digits});
513 for(
size_t i = 2; i != window_size; ++i) {
515 m_monty.sqr(entry(i), entry(i / 2));
517 m_monty.mul(entry(i), entry(1), entry(i - 1));
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");
526 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
528 if(exp_nibbles == 0) {
529 return Montgomery_Int::one(m_monty.params());
535 ct_lookup(x, scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits));
537 for(
size_t i = exp_nibbles - 1; i > 0; --i) {
538 for(
size_t j = 0; j != m_window_bits; ++j) {
541 ct_lookup(e, scalar.get_substring(m_window_bits * (i - 1), m_window_bits));
542 m_monty.mul(x, x, e);
545 return m_monty.to_monty_int(x);
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;
551 if(exp_nibbles == 0) {
552 return Montgomery_Int::one(m_monty.params());
556 copy_mem(std::span{x}, entry(scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits)));
558 for(
size_t i = exp_nibbles - 1; i > 0; --i) {
559 for(
size_t j = 0; j != m_window_bits; ++j) {
563 const uint32_t nibble = scalar.get_substring(m_window_bits * (i - 1), m_window_bits);
565 m_monty.mul(x, x, entry(nibble));
569 return m_monty.to_monty_int(x);
573 std::span<uint64_t, Lanes> entry(
size_t i) {
574 return std::span{m_table}.subspan(i * Lanes).template first<Lanes>();
577 std::span<const uint64_t, Lanes> entry(
size_t i)
const {
578 return std::span{m_table}.subspan(i * Lanes).template first<Lanes>();
581 void BOTAN_FN_ISA_AVX512 ct_lookup(Digits& out,
size_t idx)
const {
582 std::array<SIMD_8x64, N> acc;
584 const size_t window_size =
static_cast<size_t>(1) << m_window_bits;
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]);
594 for(
size_t j = 0; j != N; ++j) {
595 acc[j].store_le(&out[8 * j]);
599 IFMA_Modulus<N> m_monty;
600 secure_vector<uint64_t> m_table;
601 size_t m_window_bits;
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);
612 const size_t vectors = (ifma_digits(g.
_params().
p().
bits()) + 7) / 8;
616 return make_monty_exp<2>(g, window_bits);
618 return make_monty_exp<3>(g, window_bits);
620 return make_monty_exp<4>(g, window_bits);
622 return make_monty_exp<5>(g, window_bits);
624 return make_monty_exp<6>(g, window_bits);
626 return make_monty_exp<7>(g, window_bits);
628 return make_monty_exp<8>(g, window_bits);
630 return make_monty_exp<9>(g, window_bits);
632 return make_monty_exp<10>(g, window_bits);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
const Montgomery_Params & _params() const
static SIMD_8x64 BOTAN_FN_ISA_SIMD_8X64 masked_add(uint8_t lanes, const SIMD_8x64 &a, const SIMD_8x64 &b)
static BOTAN_FN_ISA_SIMD_8X64 SIMD_8x64 splat(uint64_t v)
static SIMD_8x64 BOTAN_FN_ISA_SIMD_8X64 alignr(const SIMD_8x64 &hi, const SIMD_8x64 &lo)
#define BOTAN_FORCE_INLINE
constexpr T value_barrier(T x)
constexpr auto word_add(W x, W y, W *carry) -> W
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)
constexpr void bigint_monty_maybe_sub(size_t N, W z[], W x0, const W x[], const W p[])
constexpr void mul64x64_128(uint64_t a, uint64_t b, uint64_t *lo, uint64_t *hi)