Add initial vectorized chacha20 implementation for 2-3x speedup #34083

Why separate this into an .ipp file if it's only included in a single .cpp file?

See branch here: https://github.com/theuni/bitcoin/commits/chacha20-vectorized/

I decided to exclude the impls which require runtime detection from this PR, as I think how that should be done is a separate conversation.

To answer your question more specifically: some impls may require different compilation flags (-mavx2/-mavx512vl), which have to be in their own compilation units.

Using #if !defined for these seems old school. Why not static constexpr bools, and if constexpr (..)?

Writing:

#if defined(__x86_64__) || defined(__amd64__)
#  define CHACHA20_VEC_DISABLE_STATES_16 true
#  define CHACHA20_VEC_DISABLE_STATES_8  true
#  define CHACHA20_VEC_DISABLE_STATES_6  true
#  define CHACHA20_VEC_DISABLE_STATES_4  false
#  define CHACHA20_VEC_DISABLE_STATES_2  false
#elif defined(__ARM_NEON)
...

static constexpr bool CHACHA20_VEC_ALL_MULTI_STATES_DISABLED =
    CHACHA20_VEC_DISABLE_STATES_16 &&
    CHACHA20_VEC_DISABLE_STATES_8 &&
    CHACHA20_VEC_DISABLE_STATES_6 &&
    CHACHA20_VEC_DISABLE_STATES_4 &&
    CHACHA20_VEC_DISABLE_STATES_2;

 void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const std::array<uint32_t, 12>& input) noexcept
 {
    if constexpr (CHACHA20_VEC_ALL_MULTI_STATES_DISABLED) return;
...
    if constexpr (!CHACHA20_VEC_DISABLE_STATES_16) {
         while(in_bytes.size() >= CHACHA20_VEC_BLOCKLEN * 16) {
...

seems to work right, and also seems like it avoids needing to put all the potentially unused code in a #if block.

Here's a branch that replaces the #defines and abstracts the recursive template stuff a bit more for your perusal https://github.com/ajtowns/bitcoin/commits/202512-pr34083-templates/

+1 for if constexpr, should simplify the code a lot (especially if we migrate from recursive templates as well)

if constexpr certainly makes more sense where possible. I'll have a look, thanks!

static_assert(sizeof(vec256) == 32) ? (Or sizeof(vec256) == 32 || ALL_MULTI_STATES_DISABLED)

I haven't used this before but the internets tells me we could use the attribute syntax here, something like:

template <typename T, size_t N>
using VectorType [[gnu::vector_size(sizeof(T) * N)]] = T;

using vec256 = VectorType<uint32_t, 8>;

Because they're compiler-specific, the code makes no assumptions about the size/structure/alignment of vec256. The only accesses are via operator[]. So afaik, there's no need to check for this.

Sorry, I meant just so you get an error if you're using a compiler ignores the __attribute__ entirely but still passes the #if in _base.cpp.

if constexpr (ITER + 1 < I) (we have a space after if constexpr elsewhere)

That's fine in a draft I guess, but in the final version I'd also appreciate a reformat - my OCD keeps flaring up for these :p

My understanding is that you're inverting the logic here: instead of

#define QUARTERROUND(a,b,c,d) \
    X(a,b,d,16) X(c,d,b,12) X(a,d,b,8) X(c,d,b,7)

This does the X(a,b,d,16) all four times via simd, then X(c,d,b,12) all four times, etc. And the simd part relies on the data for those four steps being exactly +4 units apart, which is why the shuffling and unshuffling is necessary for the second round. (Okay, not four times but eight times because each vec256 is two blocks)

Could use a little more explanation in the comment I think? But makes sense to me.

Makes sense to me too, but I'm not sure why doing it this way is preferable. Intuitively I would have expected that the vectors hold the same word spread over multiple blocks. But if I understand your approach here, we have multiple words over two blocks. Is it just easier to express the quarter rounds in this way?

Overflow happens every 274GB I guess, which presumably isn't worth putting much effort in to optimising around.

This is actually doing the opposite.. it's keeping the vectorized impl from having to worry about this case. In the current code, we have:

++j12;
if (!j12) ++j13;
...
input[8] = j12;
input[9] = j13;

So effectively input[8] and input[9] are treated as a single uint64_t. It's not possible to express "cast to uint64_t elements and increment" or "increment and overflow over there" with the vector extensions, so it turned out to be easier to just forbid the overflow cases from being vectorized at all.

Yeah, I was thinking about whether the code should just do the non-vectorized stuff to get past the overflow then immediately go back to vectorizing, rather than waiting for the next call. I think what you've got makes sense.

If you decide to keep it, consider subtracting from max instead:

    const bool overflow = blocks > std::numeric_limits<uint32_t>::max() - input[8];

can we assume that all big endian systems have __builtin_bswap32 available? https://github.com/bitcoin/bitcoin/blob/432b18ca8d0654318a8d882b28b20af2cb2d2e5d/src/compat/byteswap.h#L14-L16 indicates we could use our existing helpers here instead:

ALWAYS_INLINE void vec_byteswap(vec256& vec)
{
    if constexpr (std::endian::native == std::endian::big) {
        for (size_t i = 0; i < 8; ++i) {
            vec[i] = internal_bswap_32(vec[i]);
        }
    }
}

A small, fixed-size loop like this should be unrolled by every compiler, it's what we did in https://github.com/bitcoin/bitcoin/pull/31144/files#diff-f26d4597a7f5a5d4aa30053032d49427b402ef4fd7a1b3194cb75b2551d58ca4R48 as well.

(nit: could you please reformat the patch, it differs slightly from how clang-format is set for new code)

Thanks, yes, I meant to change that to internal_bswap_32 before pushing. Will do.

This still stands: vec_byteswap duplicates the host-endian branch around raw __builtin_bswap32 calls, while compat/endian.h already provides the same lane conversion through htole32_internal.

<details><summary>reuse endian helper for ChaCha20</summary>

diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index 92b0148d75..85b4e77395 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -6,11 +6,11 @@
 #define BITCOIN_CRYPTO_CHACHA20_VEC_128IMPL_H
 
 #include <attributes.h>
+#include <compat/endian.h>
 #include <crypto/chacha20_vec.h>
 
 #include <algorithm>
 #include <array>
-#include <bit>
 #include <cassert>
 #include <cstdint>
 #include <cstring>
@@ -22,18 +22,10 @@ static constexpr size_t BLOCKLEN = 64;
 
 using vec128 = uint32_t __attribute__((__vector_size__(16)));
 
-/** Endian-conversion for big-endian */
+/** Convert every lane to little-endian byte order (a no-op on little-endian hosts) */
 ALWAYS_INLINE void vec_byteswap(vec128& vec)
 {
-    if constexpr (std::endian::native == std::endian::big)
-    {
-        vec128 ret;
-        ret[0] = __builtin_bswap32(vec[0]);
-        ret[1] = __builtin_bswap32(vec[1]);
-        ret[2] = __builtin_bswap32(vec[2]);
-        ret[3] = __builtin_bswap32(vec[3]);
-        vec = ret;
-    }
+    vec = vec128{htole32_internal(vec[0]), htole32_internal(vec[1]), htole32_internal(vec[2]), htole32_internal(vec[3])};
 }
 
 /** Left-rotate vector */

</details>

But we could go a step futher and just inline it and use ReadLE32 and WriteLE32 which already express the required unaligned endian conversion.

<details><summary>reuse ChaCha20 endian I/O </summary>

diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index 92b0148d75..988174d02c 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -6,14 +6,13 @@
 #define BITCOIN_CRYPTO_CHACHA20_VEC_128IMPL_H
 
 #include <attributes.h>
+#include <crypto/common.h>
 #include <crypto/chacha20_vec.h>
 
 #include <algorithm>
 #include <array>
-#include <bit>
 #include <cassert>
 #include <cstdint>
-#include <cstring>
 #include <span>
 
 namespace chacha20_vec128 {
@@ -22,20 +21,6 @@ static constexpr size_t BLOCKLEN = 64;
 
 using vec128 = uint32_t __attribute__((__vector_size__(16)));
 
-/** Endian-conversion for big-endian */
-ALWAYS_INLINE void vec_byteswap(vec128& vec)
-{
-    if constexpr (std::endian::native == std::endian::big)
-    {
-        vec128 ret;
-        ret[0] = __builtin_bswap32(vec[0]);
-        ret[1] = __builtin_bswap32(vec[1]);
-        ret[2] = __builtin_bswap32(vec[2]);
-        ret[3] = __builtin_bswap32(vec[3]);
-        vec = ret;
-    }
-}
-
 /** Left-rotate vector */
 template <size_t BITS>
 ALWAYS_INLINE void vec_rotl(vec128& vec)
@@ -161,13 +146,11 @@ ALWAYS_INLINE void doubleround(std::array<vec128, I>& arr0, std::array<vec128, I
 /** XOR 16 input bytes with one state row and write them without assuming alignment or vec128's memory layout */
 ALWAYS_INLINE void vec_read_xor_write(std::span<const std::byte, 16> in_bytes, std::span<std::byte, 16> out_bytes, const vec128& vec)
 {
-    std::array<uint32_t, 4> temparr;
-    memcpy(temparr.data(), in_bytes.data(), in_bytes.size());
-    vec128 tempvec = vec;
-    vec_byteswap(tempvec);
-    tempvec ^= (vec128){temparr[0], temparr[1], temparr[2], temparr[3]};
-    temparr = {tempvec[0], tempvec[1], tempvec[2], tempvec[3]};
-    memcpy(out_bytes.data(), temparr.data(), out_bytes.size());
+    const vec128 result{vec ^ vec128{ReadLE32(in_bytes.data()), ReadLE32(in_bytes.data() + 4), ReadLE32(in_bytes.data() + 8), ReadLE32(in_bytes.data() + 12)}};
+    WriteLE32(out_bytes.data(), result[0]);
+    WriteLE32(out_bytes.data() + 4, result[1]);
+    WriteLE32(out_bytes.data() + 8, result[2]);
+    WriteLE32(out_bytes.data() + 12, result[3]);
 }
 
 /** Write each 64-byte state in row order */

</details>

And while we're here, the implementation indexes vec128 as four 32-bit lanes, but does not verify that the compiler honored the vector_size attribute, let's assert it to be sure.

<details><summary>verify ChaCha20 vector width</summary>

diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index 32dc166952..9545c4d8da 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -20,6 +20,7 @@ namespace chacha20_vec128 {
 static constexpr size_t BLOCKLEN = 64;
 
 using vec128 = uint32_t __attribute__((__vector_size__(16)));
+static_assert(sizeof(vec128) == 16);
 
 /** Left-rotate vector */
 template <size_t BITS>

</details>

It seems to me the existing standard test vectors are too short (mostly < 128 bytes) to trigger the vectorized optimization - can we extend the tests to runa and compare the new specializations (could show as skipped when the given architecture isn't available locally)?

Yep, will do.

Forcing vectorized operations on an emulated big-endian system (otherwise it falls back to the scalar implementation due to the safety checks):

diff --git a/src/crypto/chacha20_vec_base.cpp b/src/crypto/chacha20_vec_base.cpp
index 9fda9452a1..a2aa1e5552 100644
--- a/src/crypto/chacha20_vec_base.cpp
+++ b/src/crypto/chacha20_vec_base.cpp
@@ -20,7 +20,7 @@
 #  define CHACHA20_VEC_DISABLE_STATES_8
 #  define CHACHA20_VEC_DISABLE_STATES_6
 #  define CHACHA20_VEC_DISABLE_STATES_4
-#  define CHACHA20_VEC_DISABLE_STATES_2
+//#  define CHACHA20_VEC_DISABLE_STATES_2
 #endif

 #include <crypto/chacha20_vec.ipp>

and running the crypto_tests:

brew install podman pigz qemu
podman machine init
podman machine start

podman run --platform linux/s390x -it --rm ubuntu:latest /bin/bash -c \
  'apt-get update && \
   DEBIAN_FRONTEND=noninteractive apt-get install -y \
   git build-essential cmake ccache pkg-config \
   libevent-dev libboost-dev libssl-dev libsqlite3-dev python3 && \
   git clone https://github.com/bitcoin/bitcoin.git && cd bitcoin && \
   git fetch origin pull/34083/head:chacha20-vec && git checkout chacha20-vec && \
   sed -i "s/#  define CHACHA20_VEC_DISABLE_STATES_2/\/\/#  define CHACHA20_VEC_DISABLE_STATES_2/" src/crypto/chacha20_vec_base.cpp && \
   cmake -B build -DBUILD_BENCH=OFF -DBUILD_GUI=OFF -DBUILD_DAEMON=OFF -DBUILD_TX=OFF -DENABLE_IPC=OFF -DENABLE_WALLET=OFF -DENABLE_ZMQ=OFF -DENABLE_UPNP=OFF -DENABLE_NATPMP=OFF && \
   cmake --build build --target test_bitcoin -j1 && \ ./build/bin/test_bitcoin --run_test=crypto_tests'

We're getting a lot of failures:

Running 17 test cases...
./test/crypto_tests.cpp(155): error: in "crypto_tests/chacha20_testvector": check hexout == HexStr(outres) has failed [a3fbf07df3fa2fde4f376ca23e82737041605d9f4f4f57bd8cff2c1d4b7955ec2a97948bd3722915c8f3d337f7d370050e9e96d647b7c39f56e031ca5eb6250d4042e02785ececfa4b4bb5e8ead0440e20b6e8db09d881a7c6132f420e52795042bdfa7773d8a9051447b3291ce1411c680465552aa6c405b7764d5e87bea85ad00f8449ed8f72d0d662ab052691ca66424bc86d2df80ea41f43abf937d3259dc4b2d0dfb48a6c9139ddd7f76966e928e635553ba76c5c879d7b35d49eb2e62b0871cdac638939e25e8a1e0ef9d5280fa8ca328b351c3c765989cbcf3daa8b6ccc3aaf9f3979c92b3720fc88dc95ed84a1be059c6499b9fda236e7e818b04b0bc39c1e876b193bfe5569753f88128cc08aaa9b63d1a16f80ef2554d7189c411f5869ca52c5b83fa36ff216b9c1d30062bebcfd2dc5bce0911934fda79a86f6e698ced759c3ff9b6477338f3da4f9cd8514ea9982ccafb341b2384dd902f3d1ab7ac61dd29c6f21ba5b862f3730e37cfdc4fd806c22f221 != c2ece71ceded38c04f376ca225cc3d6b463409986f263e9db1994a204b6844ec6e9695cfc52b7003e3b6961ceac96a18138981cb4ee5919649b263d542b82b114a57f52d8ba2a2f4540af4f7f49f0b1072a7f9891b97ceb5c61c20420143685f169add2373c4b505122eda2f5df3535d555637680dc5a722b83209519ae7f147c11a9158f48479c9926ea7412ac69d6a584ac97768e412e1514fa7b737ce389dc4bbd9df9cc422b95ccfc5926171fe20e9284834a77646878d7a34c485b3e7300c3589a8448b3bc53b980c6bced42938afc1398c2f1a3a6c2887c5be68a18039cb2fba983271c1202a73af95c79ae29faafb40973694b4afa523f2ef13b84300c39c1e876b193bfe5569753f88128cc08aaa9b63d1a16f80ef2554d7189c411f5869ca52c5b83fa36ff216b9c1d30062bebcfd2dc5bce0911934fda79a86f6e698ced759c3ff9b6477338f3da4f9cd8514ea9982ccafb341b2384dd902f3d1ab7ac61dd29c6f21ba5b862f3730e37cfdc4fd806c22f221]
...
./test/crypto_tests.cpp(185): error: in "crypto_tests/chacha20_testvector": check hexout == HexStr(outres) has failed [a3fbf07df3fa2fde4f376ca23e82737041605d9f4f4f57bd8cff2c1d4b7955ec2a97948bd3722915c8f3d337f7d370050e9e96d647b7c39f56e031ca5eb6250d4042e02785ececfa4b4bb5e8ead0440e20b6e8db09d881a7c6132f420e52795042bdfa7773d8a9051447b3291ce1411c680465552aa6c405b7764d5e87bea85ad00f8449ed8f72d0d662ab052691ca66424bc86d2df80ea41f43abf937d3259dc4b2d0dfb48a6c9139ddd7f76966e928e635553ba76c5c879d7b35d49eb2e62b0871cdac638939e25e8a1e0ef9d5280fa8ca328b351c3c765989cbcf3daa8b6ccc3aaf9f3979c92b3720fc88dc95ed84a1be059c6499b9fda236e7e818b04b0bc39c1e876b193bfe5569753f88128cc08aaa9b63d1a16f80ef2554d7189c411f5869ca52c5b83fa36ff216b9c1d30062bebcfd2dc5bce0911934fda79a86f6e698ced759c3ff9b6477338f3da4f9cd8514ea9982ccafb341b2384dd902f3d1ab7ac61dd29c6f21ba5b862f3730e37cfdc4fd806c22f221 != a3fbf07df3fa2fde4f376ca23e82737041605d9f4f4f57bd8cff2c1d4b7955ec2a97948bd3722915c8f3d337f7d370050e9e96d647b7c39f56e031ca5eb6250d4a57f52d8ba2a2f4540af4f7f49f0b1072a7f9891b97ceb5c61c20420143685f169add2373c4b505122eda2f5df3535d555637680dc5a722b83209519ae7f147c11a9158f48479c9926ea7412ac69d6a584ac97768e412e1514fa7b737ce389dc4bbd9df9cc422b95ccfc5926171fe20e9284834a77646878d7a34c485b3e7300871cdac638939e25e8a1e0ef9d5280fa8ca328b351c3c765989cbcf3daa8b6ccc3aaf9f3979c92b3720fc88dc95ed84a1be059c6499b9fda236e7e818b04b0bc39c1e876b193bfe5569753f88128cc08aaa9b63d1a16f80ef2554d7189c411f5869ca52c5b83fa36ff216b9c1d30062bebcfd2dc5bce0911934fda79a86f6e698ced759c3ff9b6477338f3da4f9cd8514ea9982ccafb341b2384dd902f3d1ab7ac61dd29c6f21ba5b862f3730e37cfdc4fd806c22f221]
./test/crypto_tests.cpp(272): error: in "crypto_tests/chacha20poly1305_testvectors": check cipher == expected_cipher has failed
...
./test/crypto_tests.cpp(337): error: in "crypto_tests/chacha20poly1305_testvectors": check decipher == plain has failed

*** 37 failures are detected in the test module "Bitcoin Core Test Suite"

This appears to be an endianness issue in vec_read_xor_write: the current implementation swaps the result of the XOR, but on Big Endian systems we must swap the state vec before the XOR.

Changing it to:

diff --git a/src/crypto/chacha20_vec.ipp b/src/crypto/chacha20_vec.ipp
index 46a159ce01..cfc0535a92 100644
--- a/src/crypto/chacha20_vec.ipp
+++ b/src/crypto/chacha20_vec.ipp
@@ -174,8 +174,9 @@ ALWAYS_INLINE void vec_read_xor_write(std::span<const std::byte, 32> in_bytes, s
 {
     std::array<uint32_t, 8> temparr;
     memcpy(temparr.data(), in_bytes.data(), in_bytes.size());
-    vec256 tempvec = vec ^ (vec256){temparr[0], temparr[1], temparr[2], temparr[3], temparr[4], temparr[5], temparr[6], temparr[7]};
+    vec256 tempvec = vec;
     vec_byteswap(tempvec);
+    tempvec ^= (vec256){temparr[0], temparr[1], temparr[2], temparr[3], temparr[4], temparr[5], temparr[6], temparr[7]};
     temparr = {tempvec[0], tempvec[1], tempvec[2], tempvec[3], tempvec[4], tempvec[5], tempvec[6], tempvec[7]};
     memcpy(out_bytes.data(), temparr.data(), out_bytes.size());
 }

Makes it pass for me.

We should find a way to exercise this via CI and benchmarks, maybe similarly to SHA256AutoDetect in https://github.com/bitcoin/bitcoin/blob/bdb8eadcdc193f398ebad83911d3297b5257e721/src/crypto/sha256.cpp#L585-L690 which would enable us running benchmarks and tests selectively.

Thanks for catching this! I forgot to mention in the PR description that big-endian was best-effort and untested. I figured our c-i would catch any obvious bugs. Agree it's not great that it didn't :(

Thanks for the quick fix too :)

I had the same disappointment when implementing the obfuscation optimization. :) @maflcko do we have a big-endian nightly that supports vectorized operations? Would it have caught this?

See #33436, but it was slow despite having the gui and the fuzz tests disabled. I am running it as part of nightly, so any issues will be caught before a release, but I am not sure if catching everything in pull requests is possible.

Maybe it is possible to split the task into two: One for a cross-compile, which should be faster than a "native" compile via qemu. And another to run the tests, similar to the windows-cross tests.

Actually, I ran the CI config locally, but it didn't catch this, as the platform opts out. The CI doesn't run the sed -i "s/# define CHACHA20_VEC_DISABLE_STATES_2/\/\/# define CHACHA20_VEC_DISABLE_STATES_2/" src/crypto/chacha20_vec_base.cpp && \ portion, so it would not have caught this, even if the task was run.

Thanks for checking @maflcko, that's why I asked. The vectorized operations are obviously supported, but for some reason were not triggered for me either. @theuni, is this just an emulation anomaly or we were just too cautious? I understdood that @achow101 has access to real big-endian power9 machine that we might be able to test this on when it's ready.

@l0rinc As the code is written at the moment, all platforms must opt-in to vectorization as opposed to opting out. I'm not sure that's the best approach, but I figured that was a reasonable starting point.

My reasoning for that was: consider non-x86, non-arm+neon platforms. For the most part, I'm assuming they're under-powered. Enabling (for example) 4x blocks/sec for mipsel would probably cause a drastic slowdown. Obviously there are lots of other powerful platforms, but I figured those would be added over time.

So if there's a big-endian architecture (or more ideally, a specific instruction set ala __ARM_NEON) that demonstrates a performance gain from calculating multiple states at once, it should be added here.

Of course, we could go the opposite direction and opt all platforms IN to all states, and instead opt-out the slow ones.

tl;dr: If we want a big-endian platform to be supported, we need to opt one in or provide an override.

Hmmm, it seems to me we're doing heavy recursive templates here to unroll loops. My understanding (and experience with the mentioned Obfuscation PR) is that modern compilers are good at unrolling fixed-bound loops. Can you please try if this also works and results in the same speedup?

template <size_t BITS, size_t I>
ALWAYS_INLINE void arr_add_xor_rot(std::array<vec256, I>& arr0, const std::array<vec256, I>& arr1, std::array<vec256, I>& arr2)
{
    for (size_t i{0}; i < I; ++i) {
        arr0[i] += arr1[i];
        arr2[i] ^= arr0[i];
        vec_rotl<BITS>(arr2[i]);
    }
}

(nit: the size is often N instead of I)

Alternatively, with a compile-time loop:

/** Perform add/xor/rotate for the round function */
template <size_t BITS, size_t I>
ALWAYS_INLINE void arr_add_xor_rot(std::array<vec256, I>& arr0, const std::array<vec256, I>& arr1, std::array<vec256, I>& arr2)
{
    [&]<size_t... ITER>(std::index_sequence<ITER...>) {
        ((
            arr0[ITER] += arr1[ITER],
            arr2[ITER] ^= arr0[ITER],
            vec_rotl<BITS>(arr2[ITER])
        ), ...);
    }(std::make_index_sequence<I>());
}

See updated title description where I touched on this.

I found (with lots of experimentation here) that different compilers use complicated and unpredictable heuristics to decide whether or not to unroll loops. Even if an unroll-able loop is detected, unrolling may be skipped because of the function size (as is the case here because it's huge).

So, I'd like to not take chances on unrolling. That means one of:

• Manual unrolling
• Macro-based (as-in REPEAT10())
• A pragma
• Recursive template based

c++26 introduces template for, which is what we really want.

I'm up for whichever of those is generally preferred, as long as it's explicit rather than implicit.

Is there any way we could help that would make you reconsider? I don't mind running the benchmarks on a few platforms, as long as we can have simpler code. The current template magic is not something I would like to see more of - modern C++20 should be able to handle the situations we have here. I don't mind experimenting with this if you don't want to.

@theuni See my std::make_index_sequence based I demonstrated above. It's template based, but doesn't need recursion, and doesn't rely on compiler unrolling. It simply expands to an expression (a[0] = v, a[1] = v, a[2] = v, ...) e.g.

https://www.agner.org/optimize/optimizing_cpp.pdf contains a few useful examples:

The automatic vectorization works best if the following conditions are satisfied:

1. Use a compiler with good support for automatic vectorization, such as Gnu, Clang, or Intel.

2. Use the latest version of the compiler. The compilers are becoming better and better at vectorization.

3. If the arrays or structures are accessed through pointers or references then tell the compiler explicitly that pointers do not alias, if appropriate, using the __restrict or restrict keyword.

4. Use appropriate compiler options to enable the desired instruction set (/arch:SSE2, /arch:AVX etc. for Windows, -msse2, -mavx512f, etc. for Linux)

5. Use the less restrictive floating point options. For Gnu and Clang compilers, use the options -O2 -fno-trapping-math -fno-math-errno -fno-signed-zeros (-ffast-math works as well, but functions like isnan(x) do not work under -ffast-math).

6. Align arrays and big structures by 16 for SSE2, preferably 32 for AVX and preferably 64 for AVX512.

7. The loop count should preferably be a constant that is divisible by the number of elements in a vector.

8. If arrays are accessed through pointers so that the alignment is not visible in the scope of the function where you want vectorization then follow the advice given above.

9. Minimize the use of branches at the vector element level.

10. Avoid table lookup at the vector element level.

Similarly in https://en.algorithmica.org/hpc/simd/auto-vectorization useful hints:

The other way, specific to SIMD, is the “ignore vector dependencies” pragma. It is a general way to inform the compiler that there are no dependencies between the loop iterations:

#pragma GCC ivdep for (int i = 0; i < n; i++)

Could we use https://github.com/bitcoin/bitcoin/blob/e16c22fe025f82166c7f3f15a37c96bf4a06e4cf/src/attributes.h#L19-L25 instead?

There's a lot of repetition here - could we extract that to an ALWAYS_INLINE lambda and have something like:

    if constexpr (ENABLE_16) process_blocks(16);
    else if constexpr (ENABLE_8)  process_blocks(8);
...

I haven't implemented it locally, maybe it's naive, let me know what you think.

I believe it's possible to use compile-time loops here instead of recursive templates (if runtime loops don't get optimized sufficiently):

/** Store a vector in all array elements */
template <size_t I>
ALWAYS_INLINE void arr_set_vec256(std::array<vec256, I>& arr, const vec256& vec)
{
    [&]<size_t... ITER>(std::index_sequence<ITER...>) {
        ((std::get<ITER>(arr) = vec),...);
    }(std::make_index_sequence<I>());
}

I avoided lambdas as I've historically observed lots of optims being skipped (with clang, at least) when using them. But since you/@ajtowns/@l0rinc have all made the same comment, I'll play around and see if these indeed compile down to nothing as one would hope.

It can be done with a helper function too, but that's not as concise:

template <size_t I, size_t... ITER>
ALWAYS_INLINE void arr_set_vec256_inner(std::array<vec256, I>& arr, const vec256& vec, std::index_sequence<ITER...>)
{
    ((std::get<ITER>(arr) = vec),...);
}

/** Store a vector in all array elements */
template <size_t I>
ALWAYS_INLINE void arr_set_vec256(std::array<vec256, I>& arr, const vec256& vec)
{
    arr_set_vec256_inner(arr, vec, std::make_index_sequence<I>());
}

Writing this as:

    template<size_t... ITER> using iseq = std::index_sequence<ITER>;
    static constexpr ISEQ = std::make_index_sequence<I>();
    
    template<size_t... ITER>
    ALWAYS_INLINE void arr_set_vec256(iseq<ITER>, std::array<vec256, I>& arr, const vec256& vec)
    {
        ((std::get<ITER>(arr) = vec), ...);
    }

   ...
        arr_set_vec256(ISEQ, arr0, num256);

doesn't seem too bad, and avoids lambdas? Possibly still a bit clumsy if you can't capture I by putting everything in a class? Might still be a bit clumsy for add_xor_rot.

Is there a particular reason for the aversion to the current approach? It seems easier to read and probably also to debug to me.

I think this function should get a short description too. Wasn't immediately clear to me that it attempts to peel off larger blocks first before potentially finishing with a few smaller blocks.

3bddf59 chacha20: Add generic vectorized chacha20 implementation:

We could avoid a copy by making it a span instead:

    void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, 12> input) noexcept;

The vector backend already advances the remaining input and output spans, so the wrapper and extracted scalar helper are unnecessary.

Could we pass the state as a fixed-extent span, dispatch vector groups at the start of ChaCha20Aligned::Crypt, and let its existing scalar loop process the remainder?

<details><summary>simplify `ChaCha20Aligned::Crypt`</summary>

diff --git a/src/crypto/chacha20.cpp b/src/crypto/chacha20.cpp
index b7500237a5..891a157d57 100644
--- a/src/crypto/chacha20.cpp
+++ b/src/crypto/chacha20.cpp
@@ -170,13 +170,11 @@ static inline void chacha20_crypt(std::span<const std::byte> in_bytes, std::span
     std::byte* c = out_bytes.data();
     size_t blocks = out_bytes.size() / ChaCha20Aligned::BLOCKLEN;
     assert(blocks * ChaCha20Aligned::BLOCKLEN == out_bytes.size());
-
+    if (!blocks) return;
 
     uint32_t x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15;
     uint32_t j4, j5, j6, j7, j8, j9, j10, j11, j12, j13, j14, j15;
 
-    if (!blocks) return;
-
     j4 = input[0];
     j5 = input[1];
     j6 = input[2];
@@ -288,20 +286,14 @@ static inline void chacha20_crypt(std::span<const std::byte> in_bytes, std::span
 
 inline void ChaCha20Aligned::Crypt(std::span<const std::byte> in_bytes, std::span<std::byte> out_bytes) noexcept
 {
-    assert(in_bytes.size() == out_bytes.size());
-    size_t blocks = out_bytes.size() / ChaCha20Aligned::BLOCKLEN;
-    assert(blocks * ChaCha20Aligned::BLOCKLEN == out_bytes.size());
 #ifdef ENABLE_CHACHA20_VEC
     // The vectorized implementation cannot increment the first nonce word
+    const size_t blocks{out_bytes.size() / BLOCKLEN};
     assert(blocks < std::numeric_limits<uint32_t>::max() - input[8]);
-    const auto state = std::to_array(input);
-    chacha20_vec::chacha20_crypt_vectorized(in_bytes, out_bytes, state);
-    const size_t blocks_written = blocks - (out_bytes.size() / ChaCha20Aligned::BLOCKLEN);
-    input[8] += blocks_written;
+    chacha20_vec::chacha20_crypt_vectorized(in_bytes, out_bytes, input);
+    input[8] += blocks - out_bytes.size() / BLOCKLEN;
 #endif
-    if (in_bytes.size()) {
-        chacha20_crypt(in_bytes, out_bytes, input);
-    }
+    chacha20_crypt(in_bytes, out_bytes, input);
 }
 
 void ChaCha20::Keystream(std::span<std::byte> out) noexcept
diff --git a/src/crypto/chacha20_vec.cpp b/src/crypto/chacha20_vec.cpp
index 80f03f99ed..080eaa59e6 100644
--- a/src/crypto/chacha20_vec.cpp
+++ b/src/crypto/chacha20_vec.cpp
@@ -13,7 +13,7 @@ namespace chacha20_vec {
 
 static_assert(BLOCKLEN == chacha20_vec128::BLOCKLEN);
 
-void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const std::array<uint32_t, 12>& input) noexcept
+void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept
 {
     assert(in_bytes.size() == out_bytes.size());
     chacha20_vec128::ChaCha20Vectorized crypter(input);
diff --git a/src/crypto/chacha20_vec.h b/src/crypto/chacha20_vec.h
index c0c172c0d8..9b58dd6d1c 100644
--- a/src/crypto/chacha20_vec.h
+++ b/src/crypto/chacha20_vec.h
@@ -5,7 +5,6 @@
 #ifndef BITCOIN_CRYPTO_CHACHA20_VEC_H
 #define BITCOIN_CRYPTO_CHACHA20_VEC_H
 
-#include <array>
 #include <cstdint>
 #include <cstddef>
 #include <span>
@@ -20,6 +19,7 @@
 
 namespace chacha20_vec {
 static constexpr uint16_t BLOCKLEN{64};
+static constexpr uint16_t STATE_WORDS{12};
 
 enum class VectorTarget {
     X86_64,
@@ -32,7 +32,7 @@ constexpr VectorTarget TARGET{VectorTarget::X86_64};
 constexpr VectorTarget TARGET{VectorTarget::AARCH64};
 #endif
 
-void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const std::array<uint32_t, 12>& input) noexcept;
+void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept;
 } // namespace chacha20_vec
 
 #endif // ENABLE_CHACHA20_VEC
diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index 27f2d41b9f..fd876d3c09 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -249,7 +249,7 @@ class ChaCha20Vectorized
     const vec128 state1;
     vec128 state2;
 public:
-    ALWAYS_INLINE ChaCha20Vectorized(const std::array<uint32_t, 12>& input) noexcept
+    ALWAYS_INLINE ChaCha20Vectorized(std::span<const uint32_t, chacha20_vec::STATE_WORDS> input) noexcept
         : state0((vec128){input[0], input[1], input[2], input[3]})
         , state1((vec128){input[4], input[5], input[6], input[7]})
         , state2((vec128){input[8], input[9], input[10], input[11]})

</details>

3bddf59 chacha20: Add generic vectorized chacha20 implementation:

We might have mentioned this before but we can reduce duplication by extracting this to something like:

template <size_t STATES>
ALWAYS_INLINE void process_blocks(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const vec256& state0, const vec256& state1, vec256& state2)
{
    static constexpr vec256 increment = (vec256){STATES, 0, 0, 0, STATES, 0, 0, 0};
    while (in_bytes.size() >= CHACHA20_VEC_BLOCKLEN * STATES) {
        multi_block_crypt<STATES>(in_bytes, out_bytes, state0, state1, state2);
        state2 += increment;
        in_bytes = in_bytes.subspan(CHACHA20_VEC_BLOCKLEN * STATES);
        out_bytes = out_bytes.subspan(CHACHA20_VEC_BLOCKLEN * STATES);
    }
}

and use it as e.g.

    process_blocks<16>(in_bytes, out_bytes, state0, state1, state2);

Local benchmarks indicate it retains the performance.

3bddf59 chacha20: Add generic vectorized chacha20 implementation:

Could we simplify this by using memcpy directly between byte spans and vec256 instead, something like:

    vec256 tempvec;
    memcpy(&tempvec, in_bytes.data(), sizeof(tempvec));
    vec_byteswap(tempvec);
    tempvec ^= vec;
    vec_byteswap(tempvec);
    memcpy(out_bytes.data(), &tempvec, sizeof(tempvec));

We're taking 16 bytes per row, the comment should be updated

/** XOR 16 input bytes with one state row and write them without assuming alignment or vec128's memory layout */

/** Write each 64-byte state in row order */

nums256 is easy to mistake for the vector width here.

    static constexpr vec128 constants{0x61707865, 0x3320646e, 0x79622d32, 0x6b206574};

Is there a specific reason for redefining ALWAYS_INLINE here? The other crypto backends already use (sha256_*.cpp, siphash.h) the one from attributes.h, could we do that here, too?

Now that we're relying on __builtin_shufflevector after the GCC codegen issues (and since we only enable this on x86_64, amd64, and aarch64), should we guard the feature macros before using them?

#if defined(__has_attribute) && defined(__has_builtin)
  #if __has_attribute(vector_size) && __has_builtin(__builtin_shufflevector) && (defined(__x86_64__) || defined(__amd64__) || defined(__aarch64__))
    #define ENABLE_CHACHA20_VEC 1
  #endif
#endif

The dispatcher then needs neither a separate target guard nor an x86-named boolean whose alternative implicitly means AArch64.

<details><summary>limit ChaCha20 vector targets</summary>

diff --git a/src/crypto/chacha20_vec.cpp b/src/crypto/chacha20_vec.cpp
index e79f98b6ad..80f03f99ed 100644
--- a/src/crypto/chacha20_vec.cpp
+++ b/src/crypto/chacha20_vec.cpp
@@ -9,35 +9,18 @@
 
 #include <cassert>
 
-#if defined(__x86_64__) || defined(__amd64__)
-static constexpr bool target_x86_64 = true;
-#else
-static constexpr bool target_x86_64 = false;
-#endif
-
-#if defined(__aarch64__)
-static constexpr bool target_arm64 = true;
-#else
-static constexpr bool target_arm64 = false;
-#endif
-
-static constexpr bool use_vectorized = target_x86_64 || target_arm64;
-
 namespace chacha20_vec {
 
 static_assert(BLOCKLEN == chacha20_vec128::BLOCKLEN);
 
 void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const std::array<uint32_t, 12>& input) noexcept
 {
-    if constexpr (!use_vectorized) {
-        return;
-    }
     assert(in_bytes.size() == out_bytes.size());
     chacha20_vec128::ChaCha20Vectorized crypter(input);
 
     while(in_bytes.size() >= BLOCKLEN) {
         size_t blocks = out_bytes.size() / BLOCKLEN;
-        if constexpr(target_x86_64) {
+        if constexpr(TARGET == VectorTarget::X86_64) {
             // 4 is faster than 3 + 1
             // 4 + 4 is faster than 3 + 3 + 2
             if  (blocks == 8 || blocks == 4) {
@@ -49,7 +32,7 @@ void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<s
             } else {
                 crypter.CryptStates<3>(in_bytes, out_bytes);
             }
-        } else if constexpr (target_arm64) {
+        } else if constexpr (TARGET == VectorTarget::AARCH64) {
             // 15 is faster than 8 + 4 + 1 + 1 + 1
             // 12 is faster than 8 + 4
             if (blocks == 15 ) {
diff --git a/src/crypto/chacha20_vec.h b/src/crypto/chacha20_vec.h
index 456b1864bd..c0c172c0d8 100644
--- a/src/crypto/chacha20_vec.h
+++ b/src/crypto/chacha20_vec.h
@@ -10,19 +10,30 @@
 #include <cstddef>
 #include <span>
 
-#ifdef __has_attribute
-  #if __has_attribute(vector_size)
+#if defined(__has_attribute) && defined(__has_builtin)
+  #if __has_attribute(vector_size) && __has_builtin(__builtin_shufflevector) && (defined(__x86_64__) || defined(__amd64__) || defined(__aarch64__))
     #define ENABLE_CHACHA20_VEC 1
   #endif
 #endif
 
 #ifdef ENABLE_CHACHA20_VEC
 
-namespace chacha20_vec
-{
-    static constexpr size_t BLOCKLEN = 64;
-    void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const std::array<uint32_t, 12>& input) noexcept;
-}
+namespace chacha20_vec {
+static constexpr uint16_t BLOCKLEN{64};
+
+enum class VectorTarget {
+    X86_64,
+    AARCH64,
+};
+
+#if defined(__x86_64__) || defined(__amd64__)
+constexpr VectorTarget TARGET{VectorTarget::X86_64};
+#elif defined(__aarch64__)
+constexpr VectorTarget TARGET{VectorTarget::AARCH64};
+#endif
+
+void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, const std::array<uint32_t, 12>& input) noexcept;
+} // namespace chacha20_vec
 
 #endif // ENABLE_CHACHA20_VEC

</details>

I find it hard to understand when the same method has mutually exclusive implementations. Usually we could extract the parts to dedicated methods with well known boundaries and the top method could simply be responsible for dispatching to the appropriate impl.

Here the x86-64 and AArch64 dispatchers are long if/else if chains inside chacha20_crypt_vectorized, so the common entry point owns both target selection and every grouping rule. Some cases only emerge from branch order, such as 8 blocks reaching the AArch64 fallback because no exact case matches first.

Could we move each target loop into a named helper, express exact group counts with switch, and leave the entry point only to select one constexpr target?

<details><summary>split ChaCha20 target dispatch</summary>

diff --git a/src/crypto/chacha20_vec.cpp b/src/crypto/chacha20_vec.cpp
index 080eaa59e6..6214c726f7 100644
--- a/src/crypto/chacha20_vec.cpp
+++ b/src/crypto/chacha20_vec.cpp
@@ -13,59 +13,66 @@ namespace chacha20_vec {
 
 static_assert(BLOCKLEN == chacha20_vec128::BLOCKLEN);
 
-void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept
+namespace {
+
+[[maybe_unused]] ALWAYS_INLINE void CryptX86_64(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept
 {
     assert(in_bytes.size() == out_bytes.size());
-    chacha20_vec128::ChaCha20Vectorized crypter(input);
+    chacha20_vec128::ChaCha20Vectorized crypter{input};
 
-    while(in_bytes.size() >= BLOCKLEN) {
-        size_t blocks = out_bytes.size() / BLOCKLEN;
-        if constexpr(TARGET == VectorTarget::X86_64) {
-            // 4 is faster than 3 + 1
-            // 4 + 4 is faster than 3 + 3 + 2
-            if  (blocks == 8 || blocks == 4) {
-                crypter.CryptStates<4>(in_bytes, out_bytes);
-            } else if (blocks == 2) {
-                crypter.CryptStates<2>(in_bytes, out_bytes);
-            } else if (blocks == 1) {
-                crypter.CryptStates<1>(in_bytes, out_bytes);
-            } else {
-                crypter.CryptStates<3>(in_bytes, out_bytes);
-            }
-        } else if constexpr (TARGET == VectorTarget::AARCH64) {
-            // 15 is faster than 8 + 4 + 1 + 1 + 1
-            // 12 is faster than 8 + 4
-            if (blocks == 15 ) {
-                crypter.CryptStates<15>(in_bytes, out_bytes);
-            } else if (blocks == 14) {
-                crypter.CryptStates<14>(in_bytes, out_bytes);
-            } else if (blocks == 13) {
-                crypter.CryptStates<13>(in_bytes, out_bytes);
-            } else if (blocks == 12) {
-                crypter.CryptStates<12>(in_bytes, out_bytes);
-            } else if (blocks == 11) {
-                crypter.CryptStates<11>(in_bytes, out_bytes);
-            } else if (blocks == 10) {
-                crypter.CryptStates<10>(in_bytes, out_bytes);
-            } else if (blocks == 9) {
-                crypter.CryptStates<9>(in_bytes, out_bytes);
-            } else if (blocks == 7) {
-                crypter.CryptStates<7>(in_bytes, out_bytes);
-            } else if (blocks == 6) {
-                crypter.CryptStates<6>(in_bytes, out_bytes);
-            } else if (blocks == 5) {
-                crypter.CryptStates<5>(in_bytes, out_bytes);
-            } else if (blocks == 4) {
-                crypter.CryptStates<4>(in_bytes, out_bytes);
-            } else if  (blocks >= 8 ) {
-                crypter.CryptStates<8>(in_bytes, out_bytes);
-            } else {
-                break;
-            }
+    while (in_bytes.size() >= BLOCKLEN) {
+        const size_t blocks = out_bytes.size() / BLOCKLEN;
+        // 4 is faster than 3 + 1
+        // 4 + 4 is faster than 3 + 3 + 2
+        switch (blocks) {
+        case 1: crypter.CryptStates<1>(in_bytes, out_bytes); break;
+        case 2: crypter.CryptStates<2>(in_bytes, out_bytes); break;
+        default: crypter.CryptStates<3>(in_bytes, out_bytes); break;
+        case 4:
+        case 8: crypter.CryptStates<4>(in_bytes, out_bytes); break;
         }
     }
 }
 
+[[maybe_unused]] ALWAYS_INLINE void CryptAArch64(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept
+{
+    assert(in_bytes.size() == out_bytes.size());
+    chacha20_vec128::ChaCha20Vectorized crypter{input};
+
+    // 15 is faster than 8 + 4 + 1 + 1 + 1
+    // 12 is faster than 8 + 4
+    while (in_bytes.size() >= BLOCKLEN) {
+        const size_t blocks = out_bytes.size() / BLOCKLEN;
+        if (blocks < 4) break;
+        switch (blocks) {
+        case 3: crypter.CryptStates<3>(in_bytes, out_bytes); break;
+        case 4: crypter.CryptStates<4>(in_bytes, out_bytes); break;
+        case 5: crypter.CryptStates<5>(in_bytes, out_bytes); break;
+        case 6: crypter.CryptStates<6>(in_bytes, out_bytes); break;
+        case 7: crypter.CryptStates<7>(in_bytes, out_bytes); break;
+        default: crypter.CryptStates<8>(in_bytes, out_bytes); break;
+        case 9: crypter.CryptStates<9>(in_bytes, out_bytes); break;
+        case 10: crypter.CryptStates<10>(in_bytes, out_bytes); break;
+        case 11: crypter.CryptStates<11>(in_bytes, out_bytes); break;
+        case 12: crypter.CryptStates<12>(in_bytes, out_bytes); break;
+        case 13: crypter.CryptStates<13>(in_bytes, out_bytes); break;
+        case 14: crypter.CryptStates<14>(in_bytes, out_bytes); break;
+        case 15: crypter.CryptStates<15>(in_bytes, out_bytes); break;
+        }
+    }
+}
+
+} // namespace
+
+void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept
+{
+    if constexpr (TARGET == VectorTarget::X86_64) {
+        CryptX86_64(in_bytes, out_bytes, input);
+    } else if constexpr (TARGET == VectorTarget::AARCH64) {
+        CryptAArch64(in_bytes, out_bytes, input);
+    }
+}
+
 } // namespace chacha20_vec
 
 #endif // ENABLE_CHACHA20_VEC
diff --git a/src/crypto/chacha20_vec.h b/src/crypto/chacha20_vec.h
index 9b58dd6d1c..d190f45bbb 100644
--- a/src/crypto/chacha20_vec.h
+++ b/src/crypto/chacha20_vec.h
@@ -31,6 +31,7 @@ constexpr VectorTarget TARGET{VectorTarget::X86_64};
 #elif defined(__aarch64__)
 constexpr VectorTarget TARGET{VectorTarget::AARCH64};
 #endif
+constexpr uint16_t MIN_BLOCKS{TARGET == VectorTarget::AARCH64 ? 3 : 1}; // Shorter AArch64 inputs are faster in scalar code
 
 void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept;
 } // namespace chacha20_vec

</details>

Now that we have vec_add_xor_rot, could we reuse the single-vector helper in the array recursion?

<details><summary>reuse ChaCha20 vector round helper</summary>

diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index 3d207697f0..9342c78b6d 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -100,13 +100,7 @@ ALWAYS_INLINE void vec_add_xor_rot(vec128& x, const vec128& y, vec128& z)
 template <size_t BITS, size_t I, size_t ITER = 0>
 ALWAYS_INLINE void arr_add_xor_rot(std::array<vec128, I>& arr0, const std::array<vec128, I>& arr1, std::array<vec128, I>& arr2)
 {
-    vec128& x = std::get<ITER>(arr0);
-    const vec128& y = std::get<ITER>(arr1);
-    vec128& z = std::get<ITER>(arr2);
-
-    x += y;
-    z ^= x;
-    vec_rotl<BITS>(z);
+    vec_add_xor_rot<BITS>(std::get<ITER>(arr0), std::get<ITER>(arr1), std::get<ITER>(arr2));
 
     if constexpr(ITER + 1 < I ) arr_add_xor_rot<BITS, I, ITER + 1>(arr0, arr1, arr2);
 }
 

</details>

arr_shuf0, arr_shuf1, and arr_shuf2 differ only in their lane rotation, while doubleround carries an unused template parameter.

Could we express each rotation through arr_shuf<ROT> and drop the unused parameter?

<details><summary>generalize ChaCha20 vector shuffles</summary>

diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index 9342c78b6d..92b0148d75 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -118,60 +118,43 @@ The second round:
             QUARTERROUND( x2, x7, x8,x13);
             QUARTERROUND( x3, x4, x9,x14);
 
-After the first round, arr_shuf0, arr_shuf1, and arr_shuf2 are used to shuffle
-the layout to prepare for the second round.
+After the first round, arr_shuf<1>, arr_shuf<2> and arr_shuf<3> rotate the
+lanes to prepare for the second round.
 
-After the second round, they are used (in reverse) to restore the original
-layout.
+After the second round, the same rotations are applied in reverse to restore
+the original layout.
 
 */
 
-template <size_t I, size_t ITER = 0>
-ALWAYS_INLINE void arr_shuf0(std::array<vec128, I>& arr)
-{
-    vec128& x = std::get<ITER>(arr);
-    x = vec128{x[1], x[2], x[3], x[0]};
-
-    if constexpr(ITER + 1 < I ) arr_shuf0<I, ITER + 1>(arr);
-}
-
-template <size_t I, size_t ITER = 0>
-ALWAYS_INLINE void arr_shuf1(std::array<vec128, I>& arr)
+/** Rotate the lanes of every array element left by ROT positions */
+template <size_t ROT, size_t I, size_t ITER = 0>
+ALWAYS_INLINE void arr_shuf(std::array<vec128, I>& arr)
 {
     vec128& x = std::get<ITER>(arr);
-    x = vec128{x[2], x[3], x[0], x[1]};
+    x = vec128{x[ROT % 4], x[(ROT + 1) % 4], x[(ROT + 2) % 4], x[(ROT + 3) % 4]};
 
-    if constexpr(ITER + 1 < I ) arr_shuf1<I, ITER + 1>(arr);
-}
-
-template <size_t I, size_t ITER = 0>
-ALWAYS_INLINE void arr_shuf2(std::array<vec128, I>& arr)
-{
-    vec128& x = std::get<ITER>(arr);
-    x = vec128{x[3], x[0], x[1], x[2]};
-
-    if constexpr(ITER + 1 < I ) arr_shuf2<I, ITER + 1>(arr);
+    if constexpr (ITER + 1 < I) arr_shuf<ROT, I, ITER + 1>(arr);
 }
 
 /* Main round function. */
-template <size_t I, size_t ITER = 0>
-ALWAYS_INLINE void doubleround(std::array<vec128, I>& arr0, std::array<vec128, I>& arr1, std::array<vec128, I>&arr2, std::array<vec128, I>&arr3)
+template <size_t I>
+ALWAYS_INLINE void doubleround(std::array<vec128, I>& arr0, std::array<vec128, I>& arr1, std::array<vec128, I>& arr2, std::array<vec128, I>& arr3)
 {
     for(unsigned i = 0; i < 10; i++) {
         arr_add_xor_rot<16>(arr0, arr1, arr3);
         arr_add_xor_rot<12>(arr2, arr3, arr1);
         arr_add_xor_rot<8>(arr0, arr1, arr3);
         arr_add_xor_rot<7>(arr2, arr3, arr1);
-        arr_shuf0(arr1);
-        arr_shuf1(arr2);
-        arr_shuf2(arr3);
+        arr_shuf<1>(arr1);
+        arr_shuf<2>(arr2);
+        arr_shuf<3>(arr3);
         arr_add_xor_rot<16>(arr0, arr1, arr3);
         arr_add_xor_rot<12>(arr2, arr3, arr1);
         arr_add_xor_rot<8>(arr0, arr1, arr3);
         arr_add_xor_rot<7>(arr2, arr3, arr1);
-        arr_shuf2(arr1);
-        arr_shuf1(arr2);
-        arr_shuf0(arr3);
+        arr_shuf<3>(arr1);
+        arr_shuf<2>(arr2);
+        arr_shuf<1>(arr3);
     }
 }

</details>

The existing ChaCha20 benchmarks jump from 4 blocks to 16,384 blocks, so they do not isolate the 2-3-block paths or AArch64 exact 12-15-state groups.

Instead of documenting how each platform behaved (or next to, as @ajtowns suggested), could we cover those four boundary sizes?

<details><summary>benchmark ChaCha20 dispatch groups</summary>

diff --git a/src/bench/chacha20.cpp b/src/bench/chacha20.cpp
index cc2b57ebbe..c1c5aed142 100644
--- a/src/bench/chacha20.cpp
+++ b/src/bench/chacha20.cpp
@@ -48,11 +48,41 @@ static void CHACHA20_64BYTES(benchmark::Bench& bench)
     CHACHA20(bench, BUFFER_SIZE_TINY);
 }
 
+static void CHACHA20_128BYTES(benchmark::Bench& bench)
+{
+    CHACHA20(bench, ChaCha20Aligned::BLOCKLEN * 2);
+}
+
+static void CHACHA20_192BYTES(benchmark::Bench& bench)
+{
+    CHACHA20(bench, ChaCha20Aligned::BLOCKLEN * 3);
+}
+
 static void CHACHA20_256BYTES(benchmark::Bench& bench)
 {
     CHACHA20(bench, BUFFER_SIZE_SMALL);
 }
 
+static void CHACHA20_768BYTES(benchmark::Bench& bench)
+{
+    CHACHA20(bench, ChaCha20Aligned::BLOCKLEN * 12);
+}
+
+static void CHACHA20_832BYTES(benchmark::Bench& bench)
+{
+    CHACHA20(bench, ChaCha20Aligned::BLOCKLEN * 13);
+}
+
+static void CHACHA20_896BYTES(benchmark::Bench& bench)
+{
+    CHACHA20(bench, ChaCha20Aligned::BLOCKLEN * 14);
+}
+
+static void CHACHA20_960BYTES(benchmark::Bench& bench)
+{
+    CHACHA20(bench, ChaCha20Aligned::BLOCKLEN * 15);
+}
+
 static void CHACHA20_1MB(benchmark::Bench& bench)
 {
     CHACHA20(bench, BUFFER_SIZE_LARGE);
@@ -74,7 +104,13 @@ static void FSCHACHA20POLY1305_1MB(benchmark::Bench& bench)
 }
 
 BENCHMARK(CHACHA20_64BYTES);
+BENCHMARK(CHACHA20_128BYTES);
+BENCHMARK(CHACHA20_192BYTES);
 BENCHMARK(CHACHA20_256BYTES);
+BENCHMARK(CHACHA20_768BYTES);
+BENCHMARK(CHACHA20_832BYTES);
+BENCHMARK(CHACHA20_896BYTES);
+BENCHMARK(CHACHA20_960BYTES);
 BENCHMARK(CHACHA20_1MB);
 BENCHMARK(FSCHACHA20POLY1305_64BYTES);
 BENCHMARK(FSCHACHA20POLY1305_256BYTES);

</details>

Similarly, the FSChaCha20Poly1305 benchmarks jump from 256 bytes to 1 MiB, so they miss the partial-to-exact fifth ChaCha block transition used in the BIP324 comparison.

Could we benchmark 318, 319, and 320-byte inputs to keep that P2P-sized transition visible?

<details><summary>benchmark BIP324 ChaCha sizes</summary>

diff --git a/src/bench/chacha20.cpp b/src/bench/chacha20.cpp
index c1c5aed142..264d3fbd94 100644
--- a/src/bench/chacha20.cpp
+++ b/src/bench/chacha20.cpp
@@ -98,6 +98,21 @@ static void FSCHACHA20POLY1305_256BYTES(benchmark::Bench& bench)
     FSCHACHA20POLY1305(bench, BUFFER_SIZE_SMALL);
 }
 
+static void FSCHACHA20POLY1305_BIP324_318BYTES(benchmark::Bench& bench)
+{
+    FSCHACHA20POLY1305(bench, 318);
+}
+
+static void FSCHACHA20POLY1305_BIP324_319BYTES(benchmark::Bench& bench)
+{
+    FSCHACHA20POLY1305(bench, 319);
+}
+
+static void FSCHACHA20POLY1305_BIP324_320BYTES(benchmark::Bench& bench)
+{
+    FSCHACHA20POLY1305(bench, 320);
+}
+
 static void FSCHACHA20POLY1305_1MB(benchmark::Bench& bench)
 {
     FSCHACHA20POLY1305(bench, BUFFER_SIZE_LARGE);
@@ -114,4 +129,7 @@ BENCHMARK(CHACHA20_960BYTES);
 BENCHMARK(CHACHA20_1MB);
 BENCHMARK(FSCHACHA20POLY1305_64BYTES);
 BENCHMARK(FSCHACHA20POLY1305_256BYTES);
+BENCHMARK(FSCHACHA20POLY1305_BIP324_318BYTES);
+BENCHMARK(FSCHACHA20POLY1305_BIP324_319BYTES);
+BENCHMARK(FSCHACHA20POLY1305_BIP324_320BYTES);
 BENCHMARK(FSCHACHA20POLY1305_1MB);

</details>

The AArch64 backend handles 4 or more blocks, yet 1-3-block Crypt calls still construct its vector state before returning to scalar code.

Could we expose the backend's minimum block count and skip shorter calls consistently (diff is against my other changes that I applied locally, may not apply cleanly)?

<details><summary>skip short ChaCha20 vector calls</summary>

diff --git a/src/crypto/chacha20.cpp b/src/crypto/chacha20.cpp
index 891a157d57..9a833702b0 100644
--- a/src/crypto/chacha20.cpp
+++ b/src/crypto/chacha20.cpp
@@ -290,8 +290,10 @@ inline void ChaCha20Aligned::Crypt(std::span<const std::byte> in_bytes, std::spa
     // The vectorized implementation cannot increment the first nonce word
     const size_t blocks{out_bytes.size() / BLOCKLEN};
     assert(blocks < std::numeric_limits<uint32_t>::max() - input[8]);
-    chacha20_vec::chacha20_crypt_vectorized(in_bytes, out_bytes, input);
-    input[8] += blocks - out_bytes.size() / BLOCKLEN;
+    if (blocks >= chacha20_vec::MIN_BLOCKS) {
+        chacha20_vec::chacha20_crypt_vectorized(in_bytes, out_bytes, input);
+        input[8] += blocks - out_bytes.size() / BLOCKLEN;
+    }
 #endif
     chacha20_crypt(in_bytes, out_bytes, input);
 }
diff --git a/src/crypto/chacha20_vec.cpp b/src/crypto/chacha20_vec.cpp
index 82ce9bc633..0b2a2e0114 100644
--- a/src/crypto/chacha20_vec.cpp
+++ b/src/crypto/chacha20_vec.cpp
@@ -43,7 +43,7 @@ namespace {
     // 12 is faster than 8 + 4
     while (in_bytes.size() >= BLOCKLEN) {
         const size_t blocks = out_bytes.size() / BLOCKLEN;
-        if (blocks < 4) break;
+        if (blocks < MIN_BLOCKS) break;
         switch (blocks) {
         case 4: crypter.CryptStates<4>(in_bytes, out_bytes); break;
         case 5: crypter.CryptStates<5>(in_bytes, out_bytes); break;
diff --git a/src/crypto/chacha20_vec.h b/src/crypto/chacha20_vec.h
index 9b58dd6d1c..0c3a335026 100644
--- a/src/crypto/chacha20_vec.h
+++ b/src/crypto/chacha20_vec.h
@@ -31,6 +31,7 @@ constexpr VectorTarget TARGET{VectorTarget::X86_64};
 #elif defined(__aarch64__)
 constexpr VectorTarget TARGET{VectorTarget::AARCH64};
 #endif
+constexpr uint16_t MIN_BLOCKS{TARGET == VectorTarget::AARCH64 ? 4 : 1}; // Shorter AArch64 inputs are faster in scalar code
 
 void chacha20_crypt_vectorized(std::span<const std::byte>& in_bytes, std::span<std::byte>& out_bytes, std::span<const uint32_t, STATE_WORDS> input) noexcept;
 } // namespace chacha20_vec

</details>

Slightly unrelated, but my IDE flagged these: ChaCha20::Keystream expresses fixed-count buffer copies with matching end iterators, while both buffering paths leave derived counts mutable and Crypt checks a size only for emptiness.

<details><summary>simplify ChaCha20 buffered paths</summary>

diff --git a/src/crypto/chacha20.cpp b/src/crypto/chacha20.cpp
index 9a833702b0..140f2baab9 100644
--- a/src/crypto/chacha20.cpp
+++ b/src/crypto/chacha20.cpp
@@ -303,7 +303,7 @@ void ChaCha20::Keystream(std::span<std::byte> out) noexcept
     if (out.empty()) return;
     if (m_bufleft) {
         unsigned reuse = std::min<size_t>(m_bufleft, out.size());
-        std::copy(m_buffer.end() - m_bufleft, m_buffer.end() - m_bufleft + reuse, out.begin());
+        std::copy_n(m_buffer.end() - m_bufleft, reuse, out.begin());
         m_bufleft -= reuse;
         out = out.subspan(reuse);
     }
@@ -314,7 +314,7 @@ void ChaCha20::Keystream(std::span<std::byte> out) noexcept
     }
     if (!out.empty()) {
         m_aligned.Keystream(m_buffer);
-        std::copy(m_buffer.begin(), m_buffer.begin() + out.size(), out.begin());
+        std::copy_n(m_buffer.begin(), out.size(), out.begin());
         m_bufleft = m_aligned.BLOCKLEN - out.size();
     }
 }
@@ -323,7 +323,7 @@ void ChaCha20::Crypt(std::span<const std::byte> input, std::span<std::byte> outp
 {
     assert(input.size() == output.size());
 
-    if (!input.size()) return;
+    if (input.empty()) return;
     if (m_bufleft) {
         unsigned reuse = std::min<size_t>(m_bufleft, input.size());
         for (unsigned i = 0; i < reuse; i++) {

</details>

My concern with all these branches is that I'm not sure all of them are properly tested.

The differential fuzzer currently chooses an arbitrary byte count and stops at 64 blocks.

Could we derive the input size from named blocks in [0, 100] plus tail_bytes in [0, BLOCKLEN - 1]? This preserves empty inputs, makes every vector group directly selectable, and keeps the implementation as the independent oracle.

<details><summary>fuzz ChaCha20 vector groups</summary>

diff --git a/src/test/fuzz/crypto_diff_fuzz_chacha20.cpp b/src/test/fuzz/crypto_diff_fuzz_chacha20.cpp
index 5e2f84d621..34cf8447b4 100644
--- a/src/test/fuzz/crypto_diff_fuzz_chacha20.cpp
+++ b/src/test/fuzz/crypto_diff_fuzz_chacha20.cpp
@@ -322,18 +322,21 @@ FUZZ_TARGET(crypto_diff_fuzz_chacha20)
                 assert(counter == ctx.input[12]);
             },
             [&] {
-                uint32_t integralInRange = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096);
-                std::vector<uint8_t> output(integralInRange);
+                constexpr uint16_t MAX_BLOCKS{100}; // Leaves room for future 256- and 512-bit vector dispatches
+                const uint16_t blocks{fuzzed_data_provider.ConsumeIntegralInRange<uint16_t>(0, MAX_BLOCKS)};
+                const uint8_t tail_bytes{fuzzed_data_provider.ConsumeIntegralInRange<uint8_t>(0, ChaCha20Aligned::BLOCKLEN - 1)};
+                const uint32_t size{uint32_t{blocks} * ChaCha20Aligned::BLOCKLEN + tail_bytes};
+                std::vector<uint8_t> output(size);
                 const std::vector<uint8_t> input = ConsumeFixedLengthByteVector(fuzzed_data_provider, output.size());
                 chacha20.Crypt(MakeByteSpan(input), MakeWritableByteSpan(output));
-                std::vector<uint8_t> djb_output(integralInRange);
+                std::vector<uint8_t> djb_output(size);
                 ECRYPT_encrypt_bytes(&ctx, input.data(), djb_output.data(), input.size());
                 assert(output == djb_output);
                 // DJB's version seeks forward to a multiple of 64 bytes after every operation. Correct for that.
                 uint32_t old_counter = counter;
-                counter += (integralInRange + 63) >> 6;
+                counter += (size + ChaCha20Aligned::BLOCKLEN - 1) / ChaCha20Aligned::BLOCKLEN;
                 if (counter < old_counter) ++nonce.first;
-                if (integralInRange & 63) {
+                if (size % ChaCha20Aligned::BLOCKLEN) {
                     chacha20.Seek(nonce, counter);
                 }
                 assert(counter == ctx.input[12]);

</details>

Is 15 also faster than e.g. 8+7? On my M4 Max, processing 14 and 15 blocks as 8+6 and 8+7 is faster than using exact 14- and 15-state groups.

These shuffles temporarily view the same 128 bits as 16- or 8-bit lanes, then convert the result back to four 32-bit lanes.

Could we use std::bit_cast for both same-size conversions instead of reinterpret_cast and the C-style cast?

<details><summary>bit-cast ChaCha20 vector lanes </summary>

diff --git a/src/crypto/chacha20_vec_128impl.h b/src/crypto/chacha20_vec_128impl.h
index f8fcbfb2ec..f77c50f5c7 100644
--- a/src/crypto/chacha20_vec_128impl.h
+++ b/src/crypto/chacha20_vec_128impl.h
@@ -10,6 +10,7 @@
 
 #include <algorithm>
 #include <array>
+#include <bit>
 #include <cassert>
 #include <cstdint>
 #include <span>
@@ -34,7 +35,8 @@ ALWAYS_INLINE
 void vec_rotl<16>(vec128& vec)
 {
     using vec128_u16 = uint16_t __attribute__((__vector_size__(16)));
-    vec = (vec128)__builtin_shufflevector(reinterpret_cast<vec128_u16>(vec), vec128_u16{}, 1, 0, 3, 2, 5, 4, 7, 6);
+    const auto halfwords{std::bit_cast<vec128_u16>(vec)};
+    vec = std::bit_cast<vec128>(__builtin_shufflevector(halfwords, vec128_u16{}, 1, 0, 3, 2, 5, 4, 7, 6));
 }
 #endif
 
@@ -44,7 +46,8 @@ ALWAYS_INLINE
 void vec_rotl<8>(vec128& vec)
 {
     using vec128_u8 = uint8_t __attribute__((__vector_size__(16)));
-    vec = (vec128)__builtin_shufflevector(reinterpret_cast<vec128_u8>(vec), vec128_u8{}, 3,0,1,2,7,4,5,6,11,8,9,10,15,12,13,14);
+    const auto bytes{std::bit_cast<vec128_u8>(vec)};
+    vec = std::bit_cast<vec128>(__builtin_shufflevector(bytes, vec128_u8{}, 3, 0, 1, 2, 7, 4, 5, 6, 11, 8, 9, 10, 15, 12, 13, 14));
 }
 #endif

</details>

Nit: formatting

Corecheck measures the one-block vector path slower, while CryptStates<3> improved the 192-byte median from 0.98 to 0.86 ns/byte on this Apple M4 Max.

Could we expose target minimums of two blocks on x86-64 and three on AArch64, and leave shorter calls scalar?

The dependency lint treats matching .h and .cpp basenames as one module, which creates chacha20_vec -> chacha20_vec_128impl -> chacha20_vec if the implementation header includes the shared interface.

Could we rename this TU to chacha20_vec_dispatch.cpp, include chacha20_vec.h from the implementation header, and keep one definition of BLOCKLEN and STATE_WORDS?

This function always calls the non-constexpr multi_block_crypt, so it cannot be evaluated at compile time, we can probably drop the constexpr.

nit: Could we make this explicit?