Repository: randombit/botan
Pull request #3205 (2023-01-21 18:02:03)

Add AVX2 implementation of Argon2's BLAMKA function
About 10-20% faster on Skylake


Patch:
diff --git a/configure.py b/configure.py
index 0c878336d..9dd7fe6a8 100755
--- a/configure.py
+++ b/configure.py
@@ -2547,6 +2547,12 @@ class ModulesChooser:
                 self._to_load.remove('compression')
                 self._not_using_because['no enabled compression schemes'].add('compression')
 
+        # The AVX2 implementation of Argon2 fails when compiled by GCC in
+        # amalgamation mode.
+        if 'argon2_avx2' in self._to_load and self._options.amalgamation and self._options.compiler == 'gcc':
+            self._to_load.remove('argon2_avx2')
+            self._not_using_because['disabled due to compiler bug'].add('argon2_avx2')
+
         self._resolve_dependencies_for_all_modules()
 
         for not_a_dep in self._maybe_dep:
diff --git a/src/lib/pbkdf/argon2/argon2.cpp b/src/lib/pbkdf/argon2/argon2.cpp
index 3555a9a93..05d896800 100644
--- a/src/lib/pbkdf/argon2/argon2.cpp
+++ b/src/lib/pbkdf/argon2/argon2.cpp
@@ -15,8 +15,7 @@
    #include <botan/internal/thread_pool.h>
 #endif
 
-#if defined(BOTAN_HAS_ARGON2_SSSE3)
-   #include <botan/internal/argon2_ssse3.h>
+#if defined(BOTAN_HAS_ARGON2_AVX2) || defined(BOTAN_HAS_ARGON2_SSSE3)
    #include <botan/internal/cpuid.h>
 #endif
 
@@ -174,13 +173,22 @@ BOTAN_FORCE_INLINE void blamka_G(uint64_t& A, uint64_t& B, uint64_t& C, uint64_t
    B = rotr<63>(B ^ C);
    }
 
-void blamka(uint64_t T[128])
+}
+
+void Argon2::blamka(uint64_t N[128], uint64_t T[128])
    {
+#if defined(BOTAN_HAS_ARGON2_AVX2)
+   if(CPUID::has_avx2())
+      return Argon2::blamka_avx2(N, T);
+#endif
+
 #if defined(BOTAN_HAS_ARGON2_SSSE3)
    if(CPUID::has_ssse3())
-      return blamka_ssse3(T);
+      return Argon2::blamka_ssse3(N, T);
 #endif
 
+   copy_mem(T, N, 128);
+
    for(size_t i = 0; i != 128; i += 16)
       {
       blamka_G(T[i+  0], T[i+  4], T[i+  8], T[i+ 12]);
@@ -206,8 +214,13 @@ void blamka(uint64_t T[128])
       blamka_G(T[i+ 16], T[i+ 49], T[i+ 64], T[i+ 97]);
       blamka_G(T[i+ 17], T[i+ 32], T[i+ 65], T[i+112]);
       }
+
+   for(size_t i = 0; i != 128; ++i)
+      N[i] ^= T[i];
    }
 
+namespace {
+
 void gen_2i_addresses(uint64_t T[128], uint64_t B[128],
                       size_t n, size_t lane, size_t slice, size_t memory,
                       size_t time, size_t mode, size_t cnt)
@@ -224,12 +237,7 @@ void gen_2i_addresses(uint64_t T[128], uint64_t B[128],
 
    for(size_t r = 0; r != 2; ++r)
       {
-      copy_mem(T, B, 128);
-
-      blamka(T);
-
-      for(size_t i = 0; i != 128; ++i)
-         B[i] ^= T[i];
+      Argon2::blamka(B, T);
       }
    }
 
@@ -308,13 +316,14 @@ void process_block(secure_vector<uint64_t>& B,
       const uint64_t random = use_2i ? addresses[index % 128] : B.at(128*prev);
       const size_t new_offset = index_alpha(random, lanes, segments, threads, n, slice, lane, index);
 
+      uint64_t N[128];
       for(size_t i = 0; i != 128; ++i)
-         T[i] = B[128*prev+i] ^ B[128*new_offset+i];
+         N[i] = B[128*prev+i] ^ B[128*new_offset+i];
 
-      blamka(T);
+      Argon2::blamka(N, T);
 
       for(size_t i = 0; i != 128; ++i)
-         B[128*offset + i] ^= T[i] ^ B[128*prev+i] ^ B[128*new_offset+i];
+         B[128*offset + i] ^= N[i];
 
       index += 1;
       }
diff --git a/src/lib/pbkdf/argon2/argon2.h b/src/lib/pbkdf/argon2/argon2.h
index 409eec13d..25833e9e3 100644
--- a/src/lib/pbkdf/argon2/argon2.h
+++ b/src/lib/pbkdf/argon2/argon2.h
@@ -58,7 +58,18 @@ class BOTAN_PUBLIC_API(2,11) Argon2 final : public PasswordHash
 
       size_t total_memory_usage() const override { return M() * 1024; }
 
+      /**
+      * Argon2's BLAMKA function
+      */
+      static void blamka(uint64_t N[128], uint64_t T[128]);
    private:
+#if defined(BOTAN_HAS_ARGON2_AVX2)
+      static void blamka_avx2(uint64_t N[128], uint64_t T[128]);
+#endif
+
+#if defined(BOTAN_HAS_ARGON2_SSSE3)
+      static void blamka_ssse3(uint64_t N[128], uint64_t T[128]);
+#endif
 
       void argon2(uint8_t output[], size_t output_len,
                   const char* password, size_t password_len,
diff --git a/src/lib/pbkdf/argon2/argon2_avx2/argon2_avx2.cpp b/src/lib/pbkdf/argon2/argon2_avx2/argon2_avx2.cpp
new file mode 100644
index 000000000..43b0fe5c1
--- /dev/null
+++ b/src/lib/pbkdf/argon2/argon2_avx2/argon2_avx2.cpp
@@ -0,0 +1,256 @@
+/**
+* (C) 2023 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/argon2.h>
+#include <immintrin.h>
+
+namespace Botan {
+
+namespace {
+
+class SIMD_4x64 final
+   {
+   public:
+      SIMD_4x64& operator=(const SIMD_4x64& other) = default;
+      SIMD_4x64(const SIMD_4x64& other) = default;
+
+      SIMD_4x64& operator=(SIMD_4x64&& other) = default;
+      SIMD_4x64(SIMD_4x64&& other) = default;
+
+      BOTAN_FUNC_ISA("avx2")
+      SIMD_4x64() // zero initialized
+         {
+         m_simd = _mm256_setzero_si256();
+         }
+
+      // Load two halves at different addresses
+      static BOTAN_FUNC_ISA("avx2")
+      SIMD_4x64 load_le2(const void* inl, const void* inh)
+         {
+         return SIMD_4x64(_mm256_loadu2_m128i(
+                             reinterpret_cast<const __m128i*>(inl),
+                             reinterpret_cast<const __m128i*>(inh)));
+         }
+
+      static BOTAN_FUNC_ISA("avx2")
+      SIMD_4x64 load_le(const void* in)
+         {
+         return SIMD_4x64(_mm256_loadu_si256(reinterpret_cast<const __m256i*>(in)));
+         }
+
+      void store_le(uint64_t out[4]) const
+         {
+         this->store_le(reinterpret_cast<uint8_t*>(out));
+         }
+
+      BOTAN_FUNC_ISA("avx2")
+      void store_le(uint8_t out[]) const
+         {
+         _mm256_storeu_si256(reinterpret_cast<__m256i*>(out), m_simd);
+         }
+
+      BOTAN_FUNC_ISA("avx2")
+      void store_le2(void* outh, void* outl)
+         {
+         _mm256_storeu2_m128i(
+            reinterpret_cast<__m128i*>(outh),
+            reinterpret_cast<__m128i*>(outl),
+            m_simd);
+         }
+
+      SIMD_4x64 operator+(const SIMD_4x64& other) const
+         {
+         SIMD_4x64 retval(*this);
+         retval += other;
+         return retval;
+         }
+
+      SIMD_4x64 operator^(const SIMD_4x64& other) const
+         {
+         SIMD_4x64 retval(*this);
+         retval ^= other;
+         return retval;
+         }
+
+      BOTAN_FUNC_ISA("avx2")
+      void operator+=(const SIMD_4x64& other)
+         {
+         m_simd = _mm256_add_epi64(m_simd, other.m_simd);
+         }
+
+      BOTAN_FUNC_ISA("avx2")
+      void operator^=(const SIMD_4x64& other)
+         {
+         m_simd = _mm256_xor_si256(m_simd, other.m_simd);
+         }
+
+      template<size_t ROT>
+      BOTAN_FUNC_ISA("avx2")
+      SIMD_4x64 rotr() const
+         {
+         static_assert(ROT > 0 && ROT < 64, "Invalid rotation constant");
+
+         if constexpr(ROT == 16)
+            {
+            auto tab = _mm256_setr_epi8(
+               2, 3, 4, 5, 6, 7, 0, 1, 10, 11, 12, 13, 14, 15, 8, 9,
+               2, 3, 4, 5, 6, 7, 0, 1, 10, 11, 12, 13, 14, 15, 8, 9);
+            return SIMD_4x64(_mm256_shuffle_epi8(m_simd, tab));
+            }
+         else if constexpr(ROT == 24)
+            {
+            auto tab = _mm256_setr_epi8(
+               3, 4, 5, 6, 7, 0, 1, 2, 11, 12, 13, 14, 15, 8, 9, 10,
+               3, 4, 5, 6, 7, 0, 1, 2, 11, 12, 13, 14, 15, 8, 9, 10);
+            return SIMD_4x64(_mm256_shuffle_epi8(m_simd, tab));
+         }
+         else if constexpr(ROT == 32)
+            {
+            auto tab = _mm256_setr_epi8(
+               4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11,
+               4, 5, 6, 7, 0, 1, 2, 3, 12, 13, 14, 15, 8, 9, 10, 11);
+            return SIMD_4x64(_mm256_shuffle_epi8(m_simd, tab));
+            }
+         else
+            {
+            return SIMD_4x64(_mm256_or_si256(_mm256_srli_epi64(m_simd, static_cast<int>(ROT)),
+                                             _mm256_slli_epi64(m_simd, static_cast<int>(64-ROT))));
+            }
+         }
+
+      template<size_t ROT>
+      SIMD_4x64 rotl() const
+         {
+         return this->rotr<64-ROT>();
+         }
+
+      // Argon2 specific operation
+      static BOTAN_FUNC_ISA("avx2")
+      SIMD_4x64 mul2_32(SIMD_4x64 x, SIMD_4x64 y)
+         {
+         const __m256i m = _mm256_mul_epu32(x.m_simd, y.m_simd);
+         return SIMD_4x64(_mm256_add_epi64(m, m));
+         }
+
+      template<uint8_t CTRL>
+      static BOTAN_FUNC_ISA("avx2") SIMD_4x64 permute_4x64(SIMD_4x64 x)
+         {
+         return SIMD_4x64(_mm256_permute4x64_epi64(x.m_simd, CTRL));
+         }
+
+      // Argon2 specific
+      static void twist(
+         SIMD_4x64& B,
+         SIMD_4x64& C,
+         SIMD_4x64& D)
+         {
+         B = SIMD_4x64::permute_4x64<0b00'11'10'01>(B);
+         C = SIMD_4x64::permute_4x64<0b01'00'11'10>(C);
+         D = SIMD_4x64::permute_4x64<0b10'01'00'11>(D);
+         }
+
+      // Argon2 specific
+      static void untwist(
+         SIMD_4x64& B,
+         SIMD_4x64& C,
+         SIMD_4x64& D)
+         {
+         B = SIMD_4x64::permute_4x64<0b10'01'00'11>(B);
+         C = SIMD_4x64::permute_4x64<0b01'00'11'10>(C);
+         D = SIMD_4x64::permute_4x64<0b00'11'10'01>(D);
+         }
+
+      explicit BOTAN_FUNC_ISA("avx2") SIMD_4x64(__m256i x) : m_simd(x) {}
+   private:
+      __m256i m_simd;
+   };
+
+BOTAN_FORCE_INLINE void blamka_G(
+   SIMD_4x64& A,
+   SIMD_4x64& B,
+   SIMD_4x64& C,
+   SIMD_4x64& D)
+   {
+   A += B + SIMD_4x64::mul2_32(A, B);
+   D ^= A;
+   D = D.rotr<32>();
+
+   C += D + SIMD_4x64::mul2_32(C, D);
+   B ^= C;
+   B = B.rotr<24>();
+
+   A += B + SIMD_4x64::mul2_32(A, B);
+   D ^= A;
+   D = D.rotr<16>();
+
+   C += D + SIMD_4x64::mul2_32(C, D);
+   B ^= C;
+   B = B.rotr<63>();
+   }
+
+BOTAN_FORCE_INLINE void blamka_R(
+   SIMD_4x64& A,
+   SIMD_4x64& B,
+   SIMD_4x64& C,
+   SIMD_4x64& D)
+   {
+   blamka_G(A, B, C, D);
+
+   SIMD_4x64::twist(B, C, D);
+   blamka_G(A, B, C, D);
+   SIMD_4x64::untwist(B, C, D);
+   }
+
+}
+
+BOTAN_FUNC_ISA("avx2")
+void Argon2::blamka_avx2(uint64_t N[128], uint64_t T[128])
+   {
+   for(size_t i = 0; i != 8; ++i)
+      {
+      SIMD_4x64 A = SIMD_4x64::load_le(&N[16*i + 4*0]);
+      SIMD_4x64 B = SIMD_4x64::load_le(&N[16*i + 4*1]);
+      SIMD_4x64 C = SIMD_4x64::load_le(&N[16*i + 4*2]);
+      SIMD_4x64 D = SIMD_4x64::load_le(&N[16*i + 4*3]);
+
+      blamka_R(A, B, C, D);
+
+      A.store_le(&T[16*i + 4*0]);
+      B.store_le(&T[16*i + 4*1]);
+      C.store_le(&T[16*i + 4*2]);
+      D.store_le(&T[16*i + 4*3]);
+      }
+
+   for(size_t i = 0; i != 8; ++i)
+      {
+      SIMD_4x64 A = SIMD_4x64::load_le2(&T[2*i + 32*0], &T[2*i + 32*0 + 16]);
+      SIMD_4x64 B = SIMD_4x64::load_le2(&T[2*i + 32*1], &T[2*i + 32*1 + 16]);
+      SIMD_4x64 C = SIMD_4x64::load_le2(&T[2*i + 32*2], &T[2*i + 32*2 + 16]);
+      SIMD_4x64 D = SIMD_4x64::load_le2(&T[2*i + 32*3], &T[2*i + 32*3 + 16]);
+
+      blamka_R(A, B, C, D);
+
+      A.store_le2(&T[2*i + 32*0], &T[2*i + 32*0 + 16]);
+      B.store_le2(&T[2*i + 32*1], &T[2*i + 32*1 + 16]);
+      C.store_le2(&T[2*i + 32*2], &T[2*i + 32*2 + 16]);
+      D.store_le2(&T[2*i + 32*3], &T[2*i + 32*3 + 16]);
+      }
+
+   for(size_t i = 0; i != 128 / 8; ++i)
+      {
+      SIMD_4x64 n0 = SIMD_4x64::load_le(&N[8*i]);
+      SIMD_4x64 n1 = SIMD_4x64::load_le(&N[8*i+4]);
+      SIMD_4x64 t0 = SIMD_4x64::load_le(&T[8*i]);
+      SIMD_4x64 t1 = SIMD_4x64::load_le(&T[8*i+4]);
+
+      n0 ^= t0;
+      n1 ^= t1;
+      n0.store_le(&N[8*i]);
+      n1.store_le(&N[8*i+4]);
+      }
+   }
+
+}
diff --git a/src/lib/pbkdf/argon2/argon2_avx2/info.txt b/src/lib/pbkdf/argon2/argon2_avx2/info.txt
new file mode 100644
index 000000000..6c412a4b2
--- /dev/null
+++ b/src/lib/pbkdf/argon2/argon2_avx2/info.txt
@@ -0,0 +1,12 @@
+<defines>
+ARGON2_AVX2 -> 20221216
+</defines>
+
+<module_info>
+name -> "Argon2 AVX2"
+brief -> "Argon2 using AVX2 instructions"
+</module_info>
+
+<isa>
+avx2
+</isa>
diff --git a/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.cpp b/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.cpp
index 382ba3aa5..3b2159628 100644
--- a/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.cpp
+++ b/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.cpp
@@ -4,7 +4,7 @@
 * Botan is released under the Simplified BSD License (see license.txt)
 */
 
-#include <botan/internal/argon2_ssse3.h>
+#include <botan/argon2.h>
 #include <tmmintrin.h>
 
 namespace Botan {
@@ -228,32 +228,57 @@ BOTAN_FORCE_INLINE void blamka_R(
 
 }
 
-void blamka_ssse3(uint64_t T[128])
+void Argon2::blamka_ssse3(uint64_t N[128], uint64_t T[128])
    {
    for(size_t i = 0; i != 8; ++i)
       {
       SIMD_2x64 Tv[8];
-      for(size_t j = 0; j != 8; ++j)
-         Tv[j] = SIMD_2x64::load_le(&T[2*(8*i+j)]);
+      for(size_t j = 0; j != 4; ++j)
+         {
+         Tv[2*j] = SIMD_2x64::load_le(&N[16*i+4*j]);
+         Tv[2*j+1] = SIMD_2x64::load_le(&N[16*i+4*j+2]);
+         }
 
       blamka_R(Tv[0], Tv[1], Tv[2], Tv[3],
                Tv[4], Tv[5], Tv[6], Tv[7]);
 
-      for(size_t j = 0; j != 8; ++j)
-         Tv[j].store_le(&T[2*(8*i+j)]);
+      for(size_t j = 0; j != 4; ++j)
+         {
+         Tv[2*j].store_le(&T[16*i + 4*j]);
+         Tv[2*j+1].store_le(&T[16*i + 4*j + 2]);
+         }
       }
 
    for(size_t i = 0; i != 8; ++i)
       {
       SIMD_2x64 Tv[8];
-      for(size_t j = 0; j != 8; ++j)
-         Tv[j] = SIMD_2x64::load_le(&T[2*(i+8*j)]);
+      for(size_t j = 0; j != 4; ++j)
+         {
+         Tv[2*j] = SIMD_2x64::load_le(&T[2*i + 32*j]);
+         Tv[2*j+1] = SIMD_2x64::load_le(&T[2*i + 32*j + 16]);
+         }
 
       blamka_R(Tv[0], Tv[1], Tv[2], Tv[3],
                Tv[4], Tv[5], Tv[6], Tv[7]);
 
-      for(size_t j = 0; j != 8; ++j)
-         Tv[j].store_le(&T[2*(i+8*j)]);
+      for(size_t j = 0; j != 4; ++j)
+         {
+         Tv[2*j].store_le(&T[2*i + 32*j]);
+         Tv[2*j+1].store_le(&T[2*i + 32*j + 16]);
+         }
+      }
+
+   for(size_t i = 0; i != 128 / 4; ++i)
+      {
+      SIMD_2x64 n0 = SIMD_2x64::load_le(&N[4*i]);
+      SIMD_2x64 n1 = SIMD_2x64::load_le(&N[4*i+2]);
+      SIMD_2x64 t0 = SIMD_2x64::load_le(&T[4*i]);
+      SIMD_2x64 t1 = SIMD_2x64::load_le(&T[4*i+2]);
+
+      n0 ^= t0;
+      n1 ^= t1;
+      n0.store_le(&N[4*i]);
+      n1.store_le(&N[4*i+2]);
       }
    }
 
diff --git a/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.h b/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.h
deleted file mode 100644
index adf64c64e..000000000
--- a/src/lib/pbkdf/argon2/argon2_ssse3/argon2_ssse3.h
+++ /dev/null
@@ -1,18 +0,0 @@
-/**
-* (C) 2022 Jack Lloyd
-*
-* Botan is released under the Simplified BSD License (see license.txt)
-*/
-
-#ifndef BOTAN_ARGON2_SSSE3_H_
-#define BOTAN_ARGON2_SSSE3_H_
-
-#include <botan/types.h>
-
-namespace Botan {
-
-void blamka_ssse3(uint64_t T[128]);
-
-}
-
-#endif


Test patch:
diff --git a/src/tests/data/argon2.vec b/src/tests/data/argon2.vec
index e4db43da3..12d407a88 100644
--- a/src/tests/data/argon2.vec
+++ b/src/tests/data/argon2.vec
@@ -1,3 +1,4 @@
+#test cpuid avx2 ssse3
 
 # First three are the official test vectors
 
diff --git a/src/tests/runner/test_runner.cpp b/src/tests/runner/test_runner.cpp
index cb22c0b0f..c8487c2db 100644
--- a/src/tests/runner/test_runner.cpp
+++ b/src/tests/runner/test_runner.cpp
@@ -271,6 +271,8 @@ bool needs_serialization(const std::string& test_name)
       return true;
    if(test_name == "block" || test_name == "hash" || test_name == "mac" || test_name == "stream" || test_name == "aead")
       return true;
+   if(test_name == "argon2")
+      return true;
    if(test_name == "ecc_unit")
       return false;
    return false;