23class SIMD_16x16 final {
25 using native_type = __m256i;
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;
33 BOTAN_FN_ISA_AVX2
explicit SIMD_16x16(native_type x) : m_simd(x) {}
35 static BOTAN_FN_ISA_AVX2 SIMD_16x16 splat(int16_t v) {
return SIMD_16x16(_mm256_set1_epi16(v)); }
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)));
41 BOTAN_FN_ISA_AVX2
void store(int16_t out[])
const {
42 _mm256_storeu_si256(
reinterpret_cast<__m256i*
>(out), m_simd);
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));
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));
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));
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));
65 BOTAN_FN_ISA_AVX2 SIMD_16x16 sra()
const {
66 return SIMD_16x16(_mm256_srai_epi16(m_simd, SHIFT));
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));
77 BOTAN_FN_ISA_AVX2 SIMD_16x16 shuffle_32()
const {
78 return SIMD_16x16(_mm256_shuffle_epi32(m_simd, CTRL));
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));
87 BOTAN_FN_ISA_AVX2 SIMD_16x16 swap_16_halves()
const {
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));
95 return byte_shuffle(tbl);
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));
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));
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));
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));
130using Lanes = std::array<int16_t, 16>;
144 static consteval Tables create() {
146 const auto times_qinv = [](int32_t z) -> int16_t {
149 return static_cast<int16_t
>(
static_cast<uint16_t
>(zq));
153 const auto mont_reduce = [&](int32_t a) -> int16_t {
154 const int16_t u = times_qinv(a);
156 return static_cast<int16_t
>(t >> 16);
162 for(
size_t i = 0; i < 128; ++i) {
164 t.m_zq[i] = times_qinv(zetas[i]);
167 for(
size_t blk = 0; blk < 8; ++blk) {
168 for(
size_t l = 0; l < 16; ++l) {
170 const size_t g8 = l / 8;
172 const size_t g4 = l / 4;
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];
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)];
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]);
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]);
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);
212 BOTAN_FN_ISA_AVX2 Zeta zeta(
size_t k)
const {
return {SIMD_16x16::splat(m_z[k]), SIMD_16x16::splat(m_zq[k])}; }
214 BOTAN_FN_ISA_AVX2 Zeta forward_8(
size_t blk)
const {
return lanes(m_f8[blk], m_f8q[blk]); }
216 BOTAN_FN_ISA_AVX2 Zeta forward_4(
size_t blk)
const {
return lanes(m_f4[blk], m_f4q[blk]); }
218 BOTAN_FN_ISA_AVX2 Zeta forward_2(
size_t blk)
const {
return lanes(m_f2[blk], m_f2q[blk]); }
220 BOTAN_FN_ISA_AVX2 Zeta inverse_8(
size_t blk)
const {
return lanes(m_i8[blk], m_i8q[blk]); }
222 BOTAN_FN_ISA_AVX2 Zeta inverse_4(
size_t blk)
const {
return lanes(m_i4[blk], m_i4q[blk]); }
224 BOTAN_FN_ISA_AVX2 Zeta inverse_2(
size_t blk)
const {
return lanes(m_i2[blk], m_i2q[blk]); }
227 BOTAN_FN_ISA_AVX2 Zeta basemul(
size_t v)
const {
return lanes(m_b[v], m_bq[v]); }
230 BOTAN_FN_ISA_AVX2 Zeta final_scale()
const {
return {SIMD_16x16::splat(m_fm), SIMD_16x16::splat(m_fmq)}; }
233 BOTAN_FN_ISA_AVX2 Zeta final_zeta()
const {
return {SIMD_16x16::splat(m_fz), SIMD_16x16::splat(m_fzq)}; }
236 constexpr Tables() =
default;
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())};
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{};
265constexpr Tables TABLES = Tables::create();
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);
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);
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);
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);
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;
296 b = fqmul_const(t, zeta, q);
309 const auto x = SIMD_16x16::concat_lo128(a, b);
310 const auto y = SIMD_16x16::concat_hi128(a, b);
317 const auto x = SIMD_16x16::interleave_lo64(a, b);
318 const auto y = SIMD_16x16::interleave_hi64(a, b);
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>();
331BOTAN_FN_ISA_AVX2
BOTAN_FORCE_INLINE void distance_2_to_4(SIMD_16x16& a, SIMD_16x16& b) {
333 a = a.shuffle_32<0xD8>();
334 b = b.shuffle_32<0xD8>();
343BOTAN_FN_ISA_AVX2
void ntt(std::span<int16_t, 256> p) {
344 int16_t* c = p.data();
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);
356 b.store(c + j + len);
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);
368 ct_butterfly(a, b, TABLES.forward_8(blk), q);
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);
377 barrett(a, v, q).store(cb);
378 barrett(b, v, q).store(cb + 16);
391 int16_t* c = p.data();
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);
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);
408 gs_butterfly(a, b, TABLES.inverse_8(blk), q);
415 const Zeta scale = TABLES.final_scale();
418 for(
size_t len = 16; len <= 128; len <<= 1) {
419 const bool reduce = (len == 16 || len == 64);
420 const bool last = (len == 128);
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);
429 a = barrett(a, v, q);
432 a = fqmul_const(a, scale, q);
435 b.store(c + j + len);
447 std::span<const int16_t, 256> lhs,
448 std::span<const int16_t, 256> rhs) {
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);
456 const auto ab = fqmul(a, b, qinv, q);
457 const auto ab_swapped = fqmul(a, b.swap_16_halves(), qinv, q);
459 const auto zeta_a1b1 = fqmul_const(ab.swap_16_halves(), TABLES.basemul(i), q);
461 const auto r0 = ab + zeta_a1b1;
462 const auto r1 = ab_swapped + ab_swapped.swap_16_halves();
464 r0.blend<0xAA>(r1).store(result.data() + 16 * i);