Botan 3.14.1
Crypto and TLS for C&
kyber_avx2.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/kyber_avx2.h>
8
9#include <botan/internal/isa_extn.h>
10#include <botan/internal/kyber_polynomial.h>
11#include <array>
12#include <immintrin.h>
13
15
16namespace {
17
18// NOLINTBEGIN(portability-simd-intrinsics)
19
20/**
21 * SIMD type of 16 signed 16-bit elements
22 */
23class SIMD_16x16 final {
24 public:
25 using native_type = __m256i;
26
27 SIMD_16x16(const SIMD_16x16&) = default;
28 SIMD_16x16& operator=(const SIMD_16x16&) = default;
29 SIMD_16x16(SIMD_16x16&&) = default;
30 SIMD_16x16& operator=(SIMD_16x16&&) = default;
31 ~SIMD_16x16() = default;
32
33 BOTAN_FN_ISA_AVX2 explicit SIMD_16x16(native_type x) : m_simd(x) {}
34
35 static BOTAN_FN_ISA_AVX2 SIMD_16x16 splat(int16_t v) { return SIMD_16x16(_mm256_set1_epi16(v)); }
36
37 static BOTAN_FN_ISA_AVX2 SIMD_16x16 load(const int16_t in[]) {
38 return SIMD_16x16(_mm256_loadu_si256(reinterpret_cast<const __m256i*>(in)));
39 }
40
41 BOTAN_FN_ISA_AVX2 void store(int16_t out[]) const {
42 _mm256_storeu_si256(reinterpret_cast<__m256i*>(out), m_simd);
43 }
44
45 BOTAN_FN_ISA_AVX2 SIMD_16x16 operator+(const SIMD_16x16& o) const {
46 return SIMD_16x16(_mm256_add_epi16(m_simd, o.m_simd));
47 }
48
49 BOTAN_FN_ISA_AVX2 SIMD_16x16 operator-(const SIMD_16x16& o) const {
50 return SIMD_16x16(_mm256_sub_epi16(m_simd, o.m_simd));
51 }
52
53 /// The low 16 bits of the lane products
54 BOTAN_FN_ISA_AVX2 SIMD_16x16 mul_lo(const SIMD_16x16& o) const {
55 return SIMD_16x16(_mm256_mullo_epi16(m_simd, o.m_simd));
56 }
57
58 /// The high 16 bits of the signed lane products
59 BOTAN_FN_ISA_AVX2 SIMD_16x16 mul_hi(const SIMD_16x16& o) const {
60 return SIMD_16x16(_mm256_mulhi_epi16(m_simd, o.m_simd));
61 }
62
63 /// Arithmetic right shift of each lane
64 template <int SHIFT>
65 BOTAN_FN_ISA_AVX2 SIMD_16x16 sra() const {
66 return SIMD_16x16(_mm256_srai_epi16(m_simd, SHIFT));
67 }
68
69 /// Lane i is taken from other if bit i of MASK is set
70 template <int MASK>
71 BOTAN_FN_ISA_AVX2 SIMD_16x16 blend(const SIMD_16x16& other) const {
72 return SIMD_16x16(_mm256_blend_epi16(m_simd, other.m_simd, MASK));
73 }
74
75 /// Permutes the 32-bit words within each 128-bit half
76 template <int CTRL>
77 BOTAN_FN_ISA_AVX2 SIMD_16x16 shuffle_32() const {
78 return SIMD_16x16(_mm256_shuffle_epi32(m_simd, CTRL));
79 }
80
81 /// Permutes the bytes within each 128-bit half using the indexes in tbl
82 BOTAN_FN_ISA_AVX2 SIMD_16x16 byte_shuffle(const SIMD_16x16& tbl) const {
83 return SIMD_16x16(_mm256_shuffle_epi8(m_simd, tbl.m_simd));
84 }
85
86 /// Swaps the two 16-bit halves of each 32-bit lane
87 BOTAN_FN_ISA_AVX2 SIMD_16x16 swap_16_halves() const {
88 // clang-format off
89 const SIMD_16x16 tbl(
90 _mm256_setr_epi8(
91 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13,
92 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9, 14, 15, 12, 13));
93 // clang-format on
94
95 return byte_shuffle(tbl);
96 }
97
98 /// The low 128-bit halves of a and b
99 static BOTAN_FN_ISA_AVX2 SIMD_16x16 concat_lo128(const SIMD_16x16& a, const SIMD_16x16& b) {
100 return SIMD_16x16(_mm256_permute2x128_si256(a.m_simd, b.m_simd, 0x20));
101 }
102
103 /// The high 128-bit halves of a and b
104 static BOTAN_FN_ISA_AVX2 SIMD_16x16 concat_hi128(const SIMD_16x16& a, const SIMD_16x16& b) {
105 return SIMD_16x16(_mm256_permute2x128_si256(a.m_simd, b.m_simd, 0x31));
106 }
107
108 /// Interleaves the low 64-bit words of each 128-bit half of a and b
109 static BOTAN_FN_ISA_AVX2 SIMD_16x16 interleave_lo64(const SIMD_16x16& a, const SIMD_16x16& b) {
110 return SIMD_16x16(_mm256_unpacklo_epi64(a.m_simd, b.m_simd));
111 }
112
113 /// Interleaves the high 64-bit words of each 128-bit half of a and b
114 static BOTAN_FN_ISA_AVX2 SIMD_16x16 interleave_hi64(const SIMD_16x16& a, const SIMD_16x16& b) {
115 return SIMD_16x16(_mm256_unpackhi_epi64(a.m_simd, b.m_simd));
116 }
117
118 private:
119 native_type m_simd;
120};
121
122// NOLINTEND(portability-simd-intrinsics)
123
124/// A zeta together with zeta * q^-1 mod 2^16, as used by fqmul_const
125struct Zeta {
126 SIMD_16x16 z;
127 SIMD_16x16 zq;
128};
129
130using Lanes = std::array<int16_t, 16>;
131
132/**
133 * The precomputed zetas in the lane orders the kernels consume them in.
134 *
135 * The layers with butterfly distance 8, 4 and 2 operate on each block of 32
136 * coefficients held in two registers, regrouped so that every lane pairs up
137 * with the lane of the other register. The forward and inverse tables hold
138 * the zetas of those layers in that lane order.
139 *
140 * The basemul zetas are in the even lanes, the odd lanes are unused.
141 */
142class Tables final {
143 public:
144 static consteval Tables create() {
145 // z * q^-1 mod 2^16, the second multiplier of a Montgomery multiplication by z
146 const auto times_qinv = [](int32_t z) -> int16_t {
147 // Using unsigned arithmetic to work around a false positive warning with GCC -fwrapv
148 const uint32_t zq = static_cast<uint32_t>(z) * static_cast<uint32_t>(KyberPolyTraits::q_inverse());
149 return static_cast<int16_t>(static_cast<uint16_t>(zq));
150 };
151
152 // The scalar Montgomery reduction
153 const auto mont_reduce = [&](int32_t a) -> int16_t {
154 const int16_t u = times_qinv(a);
155 const int32_t t = a - static_cast<int32_t>(u) * KyberConstants::Q;
156 return static_cast<int16_t>(t >> 16);
157 };
158
159 Tables t;
160 const auto& zetas = KyberPolyTraits::zeta_table();
161
162 for(size_t i = 0; i < 128; ++i) {
163 t.m_z[i] = zetas[i];
164 t.m_zq[i] = times_qinv(zetas[i]);
165 }
166
167 for(size_t blk = 0; blk < 8; ++blk) {
168 for(size_t l = 0; l < 16; ++l) {
169 // Lanes 0..7 hold coefficients 0..7 of the block, lanes 8..15 hold 16..23
170 const size_t g8 = l / 8;
171 // Lanes 0..3, 4..7, 8..11, 12..15 hold the first half of each group of 8
172 const size_t g4 = l / 4;
173 // Lane pairs hold the first half of the groups of 4, in this order
174 constexpr std::array<size_t, 8> g2_order = {0, 2, 1, 3, 4, 6, 5, 7};
175 const size_t g2 = g2_order[l / 2];
176
177 t.m_f8[blk][l] = zetas[16 + 2 * blk + g8];
178 t.m_f4[blk][l] = zetas[32 + 4 * blk + g4];
179 t.m_f2[blk][l] = zetas[64 + 8 * blk + g2];
180 t.m_i8[blk][l] = zetas[31 - (2 * blk + g8)];
181 t.m_i4[blk][l] = zetas[63 - (4 * blk + g4)];
182 t.m_i2[blk][l] = zetas[127 - (8 * blk + g2)];
183
184 t.m_f8q[blk][l] = times_qinv(t.m_f8[blk][l]);
185 t.m_f4q[blk][l] = times_qinv(t.m_f4[blk][l]);
186 t.m_f2q[blk][l] = times_qinv(t.m_f2[blk][l]);
187 t.m_i8q[blk][l] = times_qinv(t.m_i8[blk][l]);
188 t.m_i4q[blk][l] = times_qinv(t.m_i4[blk][l]);
189 t.m_i2q[blk][l] = times_qinv(t.m_i2[blk][l]);
190 }
191 }
192
193 for(size_t v = 0; v < 16; ++v) {
194 for(size_t l = 0; l < 16; l += 2) {
195 const size_t pair = 8 * v + l / 2;
196 const int16_t z = zetas[64 + pair / 2];
197 t.m_b[v][l] = (pair % 2 == 0) ? z : static_cast<int16_t>(-z);
198 t.m_bq[v][l] = times_qinv(t.m_b[v][l]);
199 }
200 }
201
202 // The final scaling of the inverse NTT, folded into its last layer
204 t.m_fmq = times_qinv(t.m_fm);
205 t.m_fz = mont_reduce(static_cast<int32_t>(zetas[1]) * t.m_fm);
206 t.m_fzq = times_qinv(t.m_fz);
207
208 return t;
209 }
210
211 /// The zeta of butterfly k, for the layers with distance 16 and above
212 BOTAN_FN_ISA_AVX2 Zeta zeta(size_t k) const { return {SIMD_16x16::splat(m_z[k]), SIMD_16x16::splat(m_zq[k])}; }
213
214 BOTAN_FN_ISA_AVX2 Zeta forward_8(size_t blk) const { return lanes(m_f8[blk], m_f8q[blk]); }
215
216 BOTAN_FN_ISA_AVX2 Zeta forward_4(size_t blk) const { return lanes(m_f4[blk], m_f4q[blk]); }
217
218 BOTAN_FN_ISA_AVX2 Zeta forward_2(size_t blk) const { return lanes(m_f2[blk], m_f2q[blk]); }
219
220 BOTAN_FN_ISA_AVX2 Zeta inverse_8(size_t blk) const { return lanes(m_i8[blk], m_i8q[blk]); }
221
222 BOTAN_FN_ISA_AVX2 Zeta inverse_4(size_t blk) const { return lanes(m_i4[blk], m_i4q[blk]); }
223
224 BOTAN_FN_ISA_AVX2 Zeta inverse_2(size_t blk) const { return lanes(m_i2[blk], m_i2q[blk]); }
225
226 /// The basemul zetas of register v of the polynomial
227 BOTAN_FN_ISA_AVX2 Zeta basemul(size_t v) const { return lanes(m_b[v], m_bq[v]); }
228
229 /// The scaling factor of the inverse NTT
230 BOTAN_FN_ISA_AVX2 Zeta final_scale() const { return {SIMD_16x16::splat(m_fm), SIMD_16x16::splat(m_fmq)}; }
231
232 /// The zeta of the last inverse NTT layer, with the scaling factor folded in
233 BOTAN_FN_ISA_AVX2 Zeta final_zeta() const { return {SIMD_16x16::splat(m_fz), SIMD_16x16::splat(m_fzq)}; }
234
235 // This needs to be public due to a MSVC bug, use ::create
236 constexpr Tables() = default;
237
238 private:
239 static BOTAN_FN_ISA_AVX2 Zeta lanes(const Lanes& z, const Lanes& zq) {
240 return {SIMD_16x16::load(z.data()), SIMD_16x16::load(zq.data())};
241 }
242
243 std::array<int16_t, 128> m_z{};
244 std::array<int16_t, 128> m_zq{};
245 std::array<Lanes, 8> m_f8{};
246 std::array<Lanes, 8> m_f8q{};
247 std::array<Lanes, 8> m_f4{};
248 std::array<Lanes, 8> m_f4q{};
249 std::array<Lanes, 8> m_f2{};
250 std::array<Lanes, 8> m_f2q{};
251 std::array<Lanes, 8> m_i8{};
252 std::array<Lanes, 8> m_i8q{};
253 std::array<Lanes, 8> m_i4{};
254 std::array<Lanes, 8> m_i4q{};
255 std::array<Lanes, 8> m_i2{};
256 std::array<Lanes, 8> m_i2q{};
257 std::array<Lanes, 16> m_b{};
258 std::array<Lanes, 16> m_bq{};
259 int16_t m_fm = 0;
260 int16_t m_fmq = 0;
261 int16_t m_fz = 0;
262 int16_t m_fzq = 0;
263};
264
265constexpr Tables TABLES = Tables::create();
266
267/// Montgomery multiplication by a constant
268BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE SIMD_16x16 fqmul_const(SIMD_16x16 a, const Zeta& zeta, SIMD_16x16 q) {
269 const auto hi = a.mul_hi(zeta.z);
270 const auto u = a.mul_lo(zeta.zq);
271 return hi - u.mul_hi(q);
272}
273
274/// Montgomery multiplication of two variables
275BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE SIMD_16x16 fqmul(SIMD_16x16 a, SIMD_16x16 b, SIMD_16x16 qinv, SIMD_16x16 q) {
276 const auto hi = a.mul_hi(b);
277 const auto u = a.mul_lo(b).mul_lo(qinv);
278 return hi - u.mul_hi(q);
279}
280
281BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE SIMD_16x16 barrett(SIMD_16x16 a, SIMD_16x16 v, SIMD_16x16 q) {
282 const auto t = a.mul_hi(v).sra<10>();
283 return a - t.mul_lo(q);
284}
285
286BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE void ct_butterfly(SIMD_16x16& a, SIMD_16x16& b, const Zeta& zeta, SIMD_16x16 q) {
287 const auto t = fqmul_const(b, zeta, q);
288 b = a - t;
289 a = a + t;
290}
291
292/// Gentleman-Sande butterfly; the sum is left unreduced
293BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE void gs_butterfly(SIMD_16x16& a, SIMD_16x16& b, const Zeta& zeta, SIMD_16x16 q) {
294 const auto t = b - a;
295 a = a + b;
296 b = fqmul_const(t, zeta, q);
297}
298
299/*
300 * Regroupings of a block of 32 coefficients between the register layouts of
301 * consecutive layers. Coefficient i of the block is in register a (i < 16)
302 * or b (i >= 16) at the distance 16 layer, and each layer below halves the
303 * distance between the lanes that pair up. Each helper converts in both
304 * directions unless noted.
305 */
306
307/// Distance 16 <-> 8: a = {0..7, 16..23}, b = {8..15, 24..31}
308BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE void swap_halves(SIMD_16x16& a, SIMD_16x16& b) {
309 const auto x = SIMD_16x16::concat_lo128(a, b);
310 const auto y = SIMD_16x16::concat_hi128(a, b);
311 a = x;
312 b = y;
313}
314
315/// Distance 8 <-> 4: a = {0..3, 8..11, 16..19, 24..27}, b = {4..7, ...}
316BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE void interleave64(SIMD_16x16& a, SIMD_16x16& b) {
317 const auto x = SIMD_16x16::interleave_lo64(a, b);
318 const auto y = SIMD_16x16::interleave_hi64(a, b);
319 a = x;
320 b = y;
321}
322
323/// Distance 4 -> 2: a = {0,1, 8,9, 4,5, 12,13, 16,17, 24,25, 20,21, 28,29}, b = a + 2
324BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE void distance_4_to_2(SIMD_16x16& a, SIMD_16x16& b) {
325 a = a.shuffle_32<0xD8>();
326 b = b.shuffle_32<0xD8>();
327 interleave64(a, b);
328}
329
330/// Distance 2 -> 4
331BOTAN_FN_ISA_AVX2 BOTAN_FORCE_INLINE void distance_2_to_4(SIMD_16x16& a, SIMD_16x16& b) {
332 interleave64(a, b);
333 a = a.shuffle_32<0xD8>();
334 b = b.shuffle_32<0xD8>();
335}
336
337} // namespace
338
339/*
340 * Same structure as KyberPolyTraits::ntt: no reduction between the layers
341 * (the coefficients stay below 8q in magnitude), Barrett at the end.
342 */
343BOTAN_FN_ISA_AVX2 void ntt(std::span<int16_t, 256> p) {
344 int16_t* c = p.data();
345 const auto q = SIMD_16x16::splat(KyberConstants::Q);
346
347 size_t k = 1;
348 for(size_t len = 128; len >= 16; len >>= 1) {
349 for(size_t start = 0; start < 256; start += 2 * len, ++k) {
350 const Zeta zeta = TABLES.zeta(k);
351 for(size_t j = start; j < start + len; j += 16) {
352 auto a = SIMD_16x16::load(c + j);
353 auto b = SIMD_16x16::load(c + j + len);
354 ct_butterfly(a, b, zeta, q);
355 a.store(c + j);
356 b.store(c + j + len);
357 }
358 }
359 }
360
361 const auto v = SIMD_16x16::splat(KyberPolyTraits::BARRETT_V);
362 for(size_t blk = 0; blk < 8; ++blk) {
363 int16_t* cb = c + 32 * blk;
364 auto a = SIMD_16x16::load(cb);
365 auto b = SIMD_16x16::load(cb + 16);
366
367 swap_halves(a, b);
368 ct_butterfly(a, b, TABLES.forward_8(blk), q);
369 interleave64(a, b);
370 ct_butterfly(a, b, TABLES.forward_4(blk), q);
371 distance_4_to_2(a, b);
372 ct_butterfly(a, b, TABLES.forward_2(blk), q);
373 distance_2_to_4(a, b);
374 interleave64(a, b);
375 swap_halves(a, b);
376
377 barrett(a, v, q).store(cb);
378 barrett(b, v, q).store(cb + 16);
379 }
380}
381
382/*
383 * Unlike KyberPolyTraits::inverse_ntt, the sums are only reduced after every
384 * second layer. Starting from coefficients in (-q, q), a layer at most
385 * doubles the magnitude of its sums, while its differences are reduced by the
386 * Montgomery multiplication. So the sums reach 4q before each reduction and
387 * the differences fed to the multiplication stay below 4q, both well within
388 * the 16-bit lanes. The final scaling by f * R is folded into the last layer.
389 */
390BOTAN_FN_ISA_AVX2 void inverse_ntt(std::span<int16_t, 256> p) {
391 int16_t* c = p.data();
392 const auto q = SIMD_16x16::splat(KyberConstants::Q);
393 const auto v = SIMD_16x16::splat(KyberPolyTraits::BARRETT_V);
394
395 for(size_t blk = 0; blk < 8; ++blk) {
396 int16_t* cb = c + 32 * blk;
397 auto a = SIMD_16x16::load(cb);
398 auto b = SIMD_16x16::load(cb + 16);
399
400 swap_halves(a, b);
401 interleave64(a, b);
402 distance_4_to_2(a, b);
403 gs_butterfly(a, b, TABLES.inverse_2(blk), q);
404 distance_2_to_4(a, b);
405 gs_butterfly(a, b, TABLES.inverse_4(blk), q);
406 a = barrett(a, v, q);
407 interleave64(a, b);
408 gs_butterfly(a, b, TABLES.inverse_8(blk), q);
409 swap_halves(a, b);
410
411 a.store(cb);
412 b.store(cb + 16);
413 }
414
415 const Zeta scale = TABLES.final_scale();
416
417 size_t k = 15;
418 for(size_t len = 16; len <= 128; len <<= 1) {
419 const bool reduce = (len == 16 || len == 64);
420 const bool last = (len == 128);
421
422 for(size_t start = 0; start < 256; start += 2 * len, --k) {
423 const Zeta zeta = last ? TABLES.final_zeta() : TABLES.zeta(k);
424 for(size_t j = start; j < start + len; j += 16) {
425 auto a = SIMD_16x16::load(c + j);
426 auto b = SIMD_16x16::load(c + j + len);
427 gs_butterfly(a, b, zeta, q);
428 if(reduce) {
429 a = barrett(a, v, q);
430 }
431 if(last) {
432 a = fqmul_const(a, scale, q);
433 }
434 a.store(c + j);
435 b.store(c + j + len);
436 }
437 }
438 }
439}
440
441/*
442 * Works on the interleaved (a0, a1) pairs directly: the products of matching
443 * and of swapped lanes give a0*b0, a1*b1 and a0*b1, a1*b0, from which the two
444 * result coefficients are assembled with one more multiplication by zeta.
445 */
446BOTAN_FN_ISA_AVX2 void poly_pointwise_montgomery(std::span<int16_t, 256> result,
447 std::span<const int16_t, 256> lhs,
448 std::span<const int16_t, 256> rhs) {
449 const auto q = SIMD_16x16::splat(KyberConstants::Q);
450 const auto qinv = SIMD_16x16::splat(KyberPolyTraits::q_inverse());
451
452 for(size_t i = 0; i < 16; ++i) {
453 const auto a = SIMD_16x16::load(lhs.data() + 16 * i);
454 const auto b = SIMD_16x16::load(rhs.data() + 16 * i);
455
456 const auto ab = fqmul(a, b, qinv, q);
457 const auto ab_swapped = fqmul(a, b.swap_16_halves(), qinv, q);
458
459 const auto zeta_a1b1 = fqmul_const(ab.swap_16_halves(), TABLES.basemul(i), q);
460
461 const auto r0 = ab + zeta_a1b1;
462 const auto r1 = ab_swapped + ab_swapped.swap_16_halves();
463
464 r0.blend<0xAA>(r1).store(result.data() + 16 * i);
465 }
466}
467
468} // namespace Botan::Kyber_AVX2
static constexpr T Q
modulus
static constexpr T inverse_ntt_scale()
static constexpr const std::array< T, N/2 > & zeta_table()
Constants shared with the SIMD kernels.
static constexpr T q_inverse()
#define BOTAN_FORCE_INLINE
Definition compiler.h:86
BOTAN_FN_ISA_AVX2 void inverse_ntt(std::span< int16_t, 256 > p)
BOTAN_FN_ISA_AVX2 void ntt(std::span< int16_t, 256 > p)
BOTAN_FN_ISA_AVX2 void poly_pointwise_montgomery(std::span< int16_t, 256 > result, std::span< const int16_t, 256 > lhs, std::span< const int16_t, 256 > rhs)
OctetString operator+(const OctetString &k1, const OctetString &k2)
Definition symkey.cpp:99
BigInt operator-(const BigInt &x, const BigInt &y)
Definition bigint.h:1216
RetT reduce(const std::vector< KeyT > &keys, RetT acc, ReducerT reducer)
Definition stl_util.h:30