poly1305_avx2.cpp

Go to the documentation of this file.

/*
* (C) 2026 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
 
#include <botan/internal/poly1305.h>
 
#include <botan/internal/isa_extn.h>
#include <immintrin.h>
 
namespace Botan {
 
// NOLINTBEGIN(portability-simd-intrinsics)
 
namespace {
 
constexpr uint32_t MASK26 = 0x3FFFFFF;
 
/*
* 4x26 values packed in a 256-bit register
*
* The 26 bit is somewhat a lie; we actually use the full 64 bit width
* but assume that after a 32x32->64 multiply there is still enough
* space to store sums into 64 bits. We could pack slightly more bits,
* but 26x5 = 130 is enough.
*/
class SIMD_4x26 final {
   public:
      BOTAN_FN_ISA_AVX2 SIMD_4x26() : m_v(_mm256_setzero_si256()) {}
 
      // Construct from raw __m256i (for vectorized loading)
      static BOTAN_FN_ISA_AVX2 SIMD_4x26 from_raw(__m256i v) { return SIMD_4x26(v); }
 
      // Pack 4 values into lanes (high to low: v3, v2, v1, v0)
      static BOTAN_FN_ISA_AVX2 SIMD_4x26 set(uint32_t v3, uint32_t v2, uint32_t v1, uint32_t v0) {
         return SIMD_4x26(_mm256_set_epi32(0, v3, 0, v2, 0, v1, 0, v0));
      }
 
      // Multiply by 5: 5*x = (x << 2) + x
      BOTAN_FN_ISA_AVX2 SIMD_4x26 mul_5() const { return SIMD_4x26(_mm256_add_epi32(_mm256_slli_epi32(m_v, 2), m_v)); }
 
      friend SIMD_4x26 BOTAN_FN_ISA_AVX2 operator+(const SIMD_4x26& x, const SIMD_4x26& y) {
         return SIMD_4x26(_mm256_add_epi64(x.raw(), y.raw()));
      }
 
      friend SIMD_4x26 BOTAN_FN_ISA_AVX2 operator*(const SIMD_4x26& x, const SIMD_4x26& y) {
         return SIMD_4x26(_mm256_mul_epi32(x.raw(), y.raw()));
      }
 
      // Horizontal sum of 4x64-bit values
      BOTAN_FN_ISA_AVX2 uint64_t horizontal_add64() const {
         uint64_t tmp[4];
         _mm256_storeu_si256(reinterpret_cast<__m256i*>(tmp), m_v);
         return tmp[0] + tmp[1] + tmp[2] + tmp[3];
      }
 
      __m256i BOTAN_FN_ISA_AVX2 raw() const { return m_v; }
 
   private:
      explicit BOTAN_FN_ISA_AVX2 SIMD_4x26(__m256i v) : m_v(v) {}
 
      __m256i m_v;
};
 
/*
* Vectorized load of 4 message blocks into radix 2^26 representation
*
* Loads 64 bytes (4 blocks), deinterleaves t0/t1 halves, and converts
* to radix 2^26 using vector shift/mask operations.
*
* Lane ordering: block 0 in lane 3, block 3 in lane 0 (reversed for multiply)
*/
BOTAN_FN_ISA_AVX2 void load_4_blocks_26(SIMD_4x26& msg_0,
                                        SIMD_4x26& msg_1,
                                        SIMD_4x26& msg_2,
                                        SIMD_4x26& msg_3,
                                        SIMD_4x26& msg_4,
                                        const uint8_t* m,
                                        std::array<uint32_t, 5> h) {
   // Load 64 bytes (4 blocks of 16 bytes each)
   const __m256i d0 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(m));
   const __m256i d1 = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(m + 32));
 
   // Deinterleave: extract low 64-bit (t0) and high 64-bit (t1) from each block
   // unpacklo/hi work within 128-bit lanes: pairs adjacent blocks
   const __m256i t0_mixed = _mm256_unpacklo_epi64(d0, d1);  // [blk3_lo, blk1_lo, blk2_lo, blk0_lo]
   const __m256i t1_mixed = _mm256_unpackhi_epi64(d0, d1);  // [blk3_hi, blk1_hi, blk2_hi, blk0_hi]
 
   const __m256i t0 = _mm256_permute4x64_epi64(t0_mixed, 0b00100111);
   const __m256i t1 = _mm256_permute4x64_epi64(t1_mixed, 0b00100111);
 
   // Constants for radix conversion
   const __m256i mask26 = _mm256_set1_epi64x(MASK26);
   const __m256i hibit_vec = _mm256_set1_epi64x(1 << 24);
 
   // Convert to radix 2^26:
   // limb0 = t0[25:0]
   // limb1 = t0[51:26]
   // limb2 = t0[63:52] | t1[13:0] << 12 (bits 52-77)
   // limb3 = t1[39:14] (bits 78-103)
   // limb4 = t1[63:40] | hibit (bits 104-127 + 2^128 marker)
   __m256i limb0 = _mm256_and_si256(t0, mask26);
   __m256i limb1 = _mm256_and_si256(_mm256_srli_epi64(t0, 26), mask26);
   __m256i limb2 = _mm256_and_si256(_mm256_or_si256(_mm256_srli_epi64(t0, 52), _mm256_slli_epi64(t1, 12)), mask26);
   __m256i limb3 = _mm256_and_si256(_mm256_srli_epi64(t1, 14), mask26);
   __m256i limb4 = _mm256_or_si256(_mm256_srli_epi64(t1, 40), hibit_vec);
 
   // Add h to lane 3 (block 0): h + m[0] before multiply by r^4
   limb0 = _mm256_add_epi64(limb0, _mm256_set_epi64x(h[0], 0, 0, 0));
   limb1 = _mm256_add_epi64(limb1, _mm256_set_epi64x(h[1], 0, 0, 0));
   limb2 = _mm256_add_epi64(limb2, _mm256_set_epi64x(h[2], 0, 0, 0));
   limb3 = _mm256_add_epi64(limb3, _mm256_set_epi64x(h[3], 0, 0, 0));
   limb4 = _mm256_add_epi64(limb4, _mm256_set_epi64x(h[4], 0, 0, 0));
 
   msg_0 = SIMD_4x26::from_raw(limb0);
   msg_1 = SIMD_4x26::from_raw(limb1);
   msg_2 = SIMD_4x26::from_raw(limb2);
   msg_3 = SIMD_4x26::from_raw(limb3);
   msg_4 = SIMD_4x26::from_raw(limb4);
}
 
// NOLINTEND(portability-simd-intrinsics)
 
// Convert radix-2^26 limbs back to radix-2^44
BOTAN_FORCE_INLINE BOTAN_FN_ISA_AVX2 void convert_26_to_44(uint64_t& r0,
                                                           uint64_t& r1,
                                                           uint64_t& r2,
                                                           const std::array<uint32_t, 5> in) {
   constexpr uint64_t M44 = 0xFFFFFFFFFFF;
   constexpr uint64_t M42 = 0x3FFFFFFFFFF;
 
   // Expand to 64 bits
   const uint64_t i0 = in[0];
   const uint64_t i1 = in[1];
   const uint64_t i2 = in[2];
   const uint64_t i3 = in[3];
   const uint64_t i4 = in[4];
 
   r0 = (i0 | (i1 << 26)) & M44;
   r1 = ((i1 >> 18) | (i2 << 8) | (i3 << 34)) & M44;
   r2 = ((i3 >> 10) | (i4 << 16)) & M42;
}
 
// Convert radix-2^44 limbs to radix-2^26
BOTAN_FORCE_INLINE std::array<uint32_t, 5> convert_44_to_26(uint64_t r0, uint64_t r1, uint64_t r2) {
   std::array<uint32_t, 5> out{};
   out[0] = static_cast<uint32_t>(r0) & MASK26;                       // bits 0-25
   out[1] = static_cast<uint32_t>((r0 >> 26) | (r1 << 18)) & MASK26;  // bits 26-51
   out[2] = static_cast<uint32_t>(r1 >> 8) & MASK26;                  // bits 52-77
   out[3] = static_cast<uint32_t>((r1 >> 34) | (r2 << 10)) & MASK26;  // bits 78-103
   out[4] = static_cast<uint32_t>(r2 >> 16) & MASK26;                 // bits 104-129
   return out;
}
 
inline void BOTAN_FN_ISA_AVX2
load_r(SIMD_4x26& r0, SIMD_4x26& r1, SIMD_4x26& r2, SIMD_4x26& r3, SIMD_4x26& r4, const secure_vector<uint64_t>& X) {
   // TODO do this in vector registers instead
   const auto t = convert_44_to_26(X[5], X[6], X[7]);
   const auto t2 = convert_44_to_26(X[8], X[9], X[10]);
   const auto t3 = convert_44_to_26(X[11], X[12], X[13]);
   const auto t4 = convert_44_to_26(X[14], X[15], X[16]);
 
   r0 = SIMD_4x26::set(t4[0], t3[0], t2[0], t[0]);
   r1 = SIMD_4x26::set(t4[1], t3[1], t2[1], t[1]);
   r2 = SIMD_4x26::set(t4[2], t3[2], t2[2], t[2]);
   r3 = SIMD_4x26::set(t4[3], t3[3], t2[3], t[3]);
   r4 = SIMD_4x26::set(t4[4], t3[4], t2[4], t[4]);
}
 
}  // namespace
 
/*
* Process 4 blocks at a time using AVX2
* h = (h + m[0]) * r^4 + m[1] * r^3 + m[2] * r^2 + m[3] * r
*/
size_t BOTAN_FN_ISA_AVX2 Poly1305::poly1305_avx2_blocks(secure_vector<uint64_t>& X, const uint8_t m[], size_t blocks) {
   if(blocks < 4) {
      return 0;
   }
 
   const size_t incoming_blocks = blocks;
 
   auto h = convert_44_to_26(X[2], X[3], X[4]);
 
   SIMD_4x26 r0;
   SIMD_4x26 r1;
   SIMD_4x26 r2;
   SIMD_4x26 r3;
   SIMD_4x26 r4;
   load_r(r0, r1, r2, r3, r4, X);
 
   const auto r1_5 = r1.mul_5();
   const auto r2_5 = r2.mul_5();
   const auto r3_5 = r3.mul_5();
   const auto r4_5 = r4.mul_5();
 
   while(blocks >= 4) {
      // Load 4 message blocks, convert to radix 2^26, and add h to block 0
      SIMD_4x26 m0;
      SIMD_4x26 m1;
      SIMD_4x26 m2;
      SIMD_4x26 m3;
      SIMD_4x26 m4;
      load_4_blocks_26(m0, m1, m2, m3, m4, m, h);
 
      const auto d0 = m0 * r0 + m1 * r4_5 + m2 * r3_5 + m3 * r2_5 + m4 * r1_5;
      const auto d1 = m0 * r1 + m1 * r0 + m2 * r4_5 + m3 * r3_5 + m4 * r2_5;
      const auto d2 = m0 * r2 + m1 * r1 + m2 * r0 + m3 * r4_5 + m4 * r3_5;
      const auto d3 = m0 * r3 + m1 * r2 + m2 * r1 + m3 * r0 + m4 * r4_5;
      const auto d4 = m0 * r4 + m1 * r3 + m2 * r2 + m3 * r1 + m4 * r0;
 
      const uint64_t h0_64 = d0.horizontal_add64();
      uint64_t h1_64 = d1.horizontal_add64();
      uint64_t h2_64 = d2.horizontal_add64();
      uint64_t h3_64 = d3.horizontal_add64();
      uint64_t h4_64 = d4.horizontal_add64();
 
      h1_64 += h0_64 >> 26;
      h[0] = static_cast<uint32_t>(h0_64) & MASK26;
      h2_64 += h1_64 >> 26;
      h[1] = static_cast<uint32_t>(h1_64) & MASK26;
      h3_64 += h2_64 >> 26;
      h[2] = static_cast<uint32_t>(h2_64) & MASK26;
      h4_64 += h3_64 >> 26;
      h[3] = static_cast<uint32_t>(h3_64) & MASK26;
 
      const uint64_t c = h4_64 >> 26;
      h[4] = static_cast<uint32_t>(h4_64) & MASK26;
 
      uint64_t carry = c * 5;
      carry += h[0];
      h[0] = static_cast<uint32_t>(carry) & MASK26;
      carry >>= 26;
      carry += h[1];
      h[1] = static_cast<uint32_t>(carry) & MASK26;
      carry >>= 26;
      carry += h[2];
      h[2] = static_cast<uint32_t>(carry) & MASK26;
      carry >>= 26;
      carry += h[3];
      h[3] = static_cast<uint32_t>(carry) & MASK26;
      carry >>= 26;
      h[4] += static_cast<uint32_t>(carry);
 
      m += 64;
      blocks -= 4;
   }
 
   convert_26_to_44(X[2], X[3], X[4], h);
 
   return (incoming_blocks - blocks);
}
 
}  // namespace Botan