commit 51be4c74a70bfdcfa108768dde7ff034d782d387
parent 8412665afd9d5d9140642eea48055b43387d1a2b
Author: finwo <finwo@pm.me>
Date: Sat, 10 Oct 2026 17:12:45 +0200
named-register permutation with fused theta and 4x round unroll
Diffstat:
3 files changed, 216 insertions(+), 72 deletions(-)
diff --git a/README.md b/README.md
@@ -42,12 +42,13 @@ Backends register from constructors; the highest available priority wins
`kf_batch_name()` report the active ones. `KECCAK_FAST_NO_BMI`,
`KECCAK_FAST_NO_AVX2` and `KECCAK_FAST_NO_AVX512` drop those backends.
-The scalar backend is the donor, pinned to the x86-64 baseline
+The scalar backend is pinned to the x86-64 baseline
(`no-avx,no-avx2,no-avx512f,no-bmi,no-bmi2`) so a consumer's `-march=native`
-cannot vectorize it or emit BMI. The round loop is unrolled 4x, which beats
-both no unroll and a full 24x unroll. `scalar+bmi` is the same permutation with
-`bmi` enabled, which turns chi's `not`+`and` into `andn`; gcc also gets `rorx`
-for the rotates. About 11% faster than the donor.
+cannot vectorize it or emit BMI. Its permutation keeps the 25 lanes in named
+locals, fuses theta into the previous round's chi, and unrolls the round loop
+4x; that beats both no unroll and a full 24x unroll. `scalar+bmi` is the same
+permutation with `bmi` enabled, which turns chi's `not`+`and` into `andn`; gcc
+also gets `rorx` for the rotates. About 20% faster than the donor.
## Dev
@@ -61,6 +62,7 @@ rejected), `BENCH_CPU=<n>` selects the core.
## License
-See `LICENSE.md`. The scalar backend is derived from `coruus/keccak-tiny`
-(David Leon Gil, CC0).
+See `LICENSE.md`. The sponge is derived from `coruus/keccak-tiny` (David Leon
+Gil, CC0); the scalar permutation follows XKCP's public-domain `opt64`
+structure.
diff --git a/src/backend/scalar-impl.h b/src/backend/scalar-impl.h
@@ -17,16 +17,6 @@ static inline int memset_s(void *dest, size_t destsz, int ch, size_t count) {
}
#endif
-static const uint8_t rho[24] = {
- 1, 3, 6, 10, 15, 21,
- 28, 36, 45, 55, 2, 14,
- 27, 41, 56, 8, 25, 43,
- 62, 18, 39, 61, 20, 44};
-static const uint8_t pi[24] = {
- 10, 7, 11, 17, 18, 3,
- 5, 16, 8, 21, 24, 4,
- 15, 23, 19, 13, 12, 2,
- 20, 14, 22, 9, 6, 1};
static const uint64_t RC[24] = {
1ULL, 0x8082ULL, 0x800000000000808aULL, 0x8000000080008000ULL,
0x808bULL, 0x80000001ULL, 0x8000000080008081ULL, 0x8000000000008009ULL,
@@ -36,62 +26,8 @@ static const uint64_t RC[24] = {
0x8000000080008081ULL, 0x8000000000008080ULL, 0x80000001ULL, 0x8000000080008008ULL};
#define rol(x, s) (((x) << s) | ((x) >> (64 - s)))
-#define REPEAT6(e) e e e e e e
-#define REPEAT24(e) REPEAT6(e e e e)
-#define REPEAT5(e) e e e e e
-#define FOR5(v, s, e) \
- v = 0; \
- REPEAT5(e; v += s;)
-
-/* Round loop unrolled 4x, after armed-keccak's roundx4: enough straight-line
- work for the scheduler without the register spills a full 24x unroll causes. */
-#ifndef KF_UNROLL
-#define KF_UNROLL 4
-#endif
-
-#define KF_STR_(x) #x
-#define KF_STR(x) KF_STR_(x)
-#if KF_UNROLL > 0 && defined(__clang__)
-#define KF_UNROLL_PRAGMA _Pragma(KF_STR(clang loop unroll_count(KF_UNROLL)))
-#elif KF_UNROLL > 0 && defined(__GNUC__)
-#define KF_UNROLL_PRAGMA _Pragma(KF_STR(GCC unroll KF_UNROLL))
-#else
-#define KF_UNROLL_PRAGMA
-#endif
-
-#define KF_ROUNDS(FIRST) \
- uint64_t *a = (uint64_t *)state; \
- uint64_t b[5] = {0}; \
- uint64_t t = 0; \
- uint8_t x, y; \
- KF_UNROLL_PRAGMA \
- for (int i = (FIRST); i < 24; i++) { \
- /* theta */ \
- FOR5(x, 1, b[x] = 0; FOR5(y, 5, b[x] ^= a[x + y];)) \
- FOR5(x, 1, FOR5(y, 5, a[y + x] ^= b[(x + 4) % 5] ^ rol(b[(x + 1) % 5], 1);)) \
- /* rho and pi */ \
- t = a[1]; \
- x = 0; \
- REPEAT24(b[0] = a[pi[x]]; \
- a[pi[x]] = rol(t, rho[x]); \
- t = b[0]; \
- x++;) \
- /* chi */ \
- FOR5(y, 5, \
- FOR5(x, 1, b[x] = a[y + x];) \
- FOR5(x, 1, a[y + x] = b[x] ^ ((~b[(x + 1) % 5]) & b[(x + 2) % 5]);)) \
- /* iota */ \
- a[0] ^= RC[i]; \
- }
-
-static inline void keccakf(void *state) {
- KF_ROUNDS(0)
-}
-
-static inline void keccak12(void *state) {
- KF_ROUNDS(12)
-}
+#include "scalar-perm.h"
#define _(S) do { S } while (0)
#define FOR(i, ST, L, S) \
diff --git a/src/backend/scalar-perm.h b/src/backend/scalar-perm.h
@@ -0,0 +1,206 @@
+#ifndef FINWO_SCALAR_PERM_H
+#define FINWO_SCALAR_PERM_H
+
+/* Keccak-p[1600] with the 25 lanes held in named locals rather than an indexed
+ array, so the scheduler can keep them in registers; theta is fused into the
+ previous round's chi (prepareTheta) and the round loop is unrolled 4x. */
+
+#define KFP_LOAD(P, S) \
+ P##0 = S[0]; \
+ P##1 = S[1]; \
+ P##2 = S[2]; \
+ P##3 = S[3]; \
+ P##4 = S[4]; \
+ P##5 = S[5]; \
+ P##6 = S[6]; \
+ P##7 = S[7]; \
+ P##8 = S[8]; \
+ P##9 = S[9]; \
+ P##10 = S[10]; \
+ P##11 = S[11]; \
+ P##12 = S[12]; \
+ P##13 = S[13]; \
+ P##14 = S[14]; \
+ P##15 = S[15]; \
+ P##16 = S[16]; \
+ P##17 = S[17]; \
+ P##18 = S[18]; \
+ P##19 = S[19]; \
+ P##20 = S[20]; \
+ P##21 = S[21]; \
+ P##22 = S[22]; \
+ P##23 = S[23]; \
+ P##24 = S[24]; \
+
+#define KFP_STORE(S, P) \
+ S[0] = P##0; \
+ S[1] = P##1; \
+ S[2] = P##2; \
+ S[3] = P##3; \
+ S[4] = P##4; \
+ S[5] = P##5; \
+ S[6] = P##6; \
+ S[7] = P##7; \
+ S[8] = P##8; \
+ S[9] = P##9; \
+ S[10] = P##10; \
+ S[11] = P##11; \
+ S[12] = P##12; \
+ S[13] = P##13; \
+ S[14] = P##14; \
+ S[15] = P##15; \
+ S[16] = P##16; \
+ S[17] = P##17; \
+ S[18] = P##18; \
+ S[19] = P##19; \
+ S[20] = P##20; \
+ S[21] = P##21; \
+ S[22] = P##22; \
+ S[23] = P##23; \
+ S[24] = P##24; \
+
+#define KFP_INIT_C(SRC) \
+ c0 = SRC##0 ^ SRC##5 ^ SRC##10 ^ SRC##15 ^ SRC##20; \
+ c1 = SRC##1 ^ SRC##6 ^ SRC##11 ^ SRC##16 ^ SRC##21; \
+ c2 = SRC##2 ^ SRC##7 ^ SRC##12 ^ SRC##17 ^ SRC##22; \
+ c3 = SRC##3 ^ SRC##8 ^ SRC##13 ^ SRC##18 ^ SRC##23; \
+ c4 = SRC##4 ^ SRC##9 ^ SRC##14 ^ SRC##19 ^ SRC##24; \
+
+#define KFP_R(SRC, DST, RCIDX) \
+ d0 = c4 ^ rol(c1, 1); \
+ d1 = c0 ^ rol(c2, 1); \
+ d2 = c1 ^ rol(c3, 1); \
+ d3 = c2 ^ rol(c4, 1); \
+ d4 = c3 ^ rol(c0, 1); \
+ SRC##0 ^= d0; \
+ b0 = SRC##0; \
+ SRC##6 ^= d1; \
+ b1 = rol(SRC##6, 44); \
+ SRC##12 ^= d2; \
+ b2 = rol(SRC##12, 43); \
+ SRC##18 ^= d3; \
+ b3 = rol(SRC##18, 21); \
+ SRC##24 ^= d4; \
+ b4 = rol(SRC##24, 14); \
+ DST##0 = b0 ^ ((~b1) & b2); \
+ DST##1 = b1 ^ ((~b2) & b3); \
+ DST##2 = b2 ^ ((~b3) & b4); \
+ DST##3 = b3 ^ ((~b4) & b0); \
+ DST##4 = b4 ^ ((~b0) & b1); \
+ DST##0 ^= RC[RCIDX]; \
+ c0 = DST##0; \
+ c1 = DST##1; \
+ c2 = DST##2; \
+ c3 = DST##3; \
+ c4 = DST##4; \
+ SRC##3 ^= d3; \
+ b5 = rol(SRC##3, 28); \
+ SRC##9 ^= d4; \
+ b6 = rol(SRC##9, 20); \
+ SRC##10 ^= d0; \
+ b7 = rol(SRC##10, 3); \
+ SRC##16 ^= d1; \
+ b8 = rol(SRC##16, 45); \
+ SRC##22 ^= d2; \
+ b9 = rol(SRC##22, 61); \
+ DST##5 = b5 ^ ((~b6) & b7); \
+ DST##6 = b6 ^ ((~b7) & b8); \
+ DST##7 = b7 ^ ((~b8) & b9); \
+ DST##8 = b8 ^ ((~b9) & b5); \
+ DST##9 = b9 ^ ((~b5) & b6); \
+ c0 ^= DST##5; \
+ c1 ^= DST##6; \
+ c2 ^= DST##7; \
+ c3 ^= DST##8; \
+ c4 ^= DST##9; \
+ SRC##1 ^= d1; \
+ b10 = rol(SRC##1, 1); \
+ SRC##7 ^= d2; \
+ b11 = rol(SRC##7, 6); \
+ SRC##13 ^= d3; \
+ b12 = rol(SRC##13, 25); \
+ SRC##19 ^= d4; \
+ b13 = rol(SRC##19, 8); \
+ SRC##20 ^= d0; \
+ b14 = rol(SRC##20, 18); \
+ DST##10 = b10 ^ ((~b11) & b12); \
+ DST##11 = b11 ^ ((~b12) & b13); \
+ DST##12 = b12 ^ ((~b13) & b14); \
+ DST##13 = b13 ^ ((~b14) & b10); \
+ DST##14 = b14 ^ ((~b10) & b11); \
+ c0 ^= DST##10; \
+ c1 ^= DST##11; \
+ c2 ^= DST##12; \
+ c3 ^= DST##13; \
+ c4 ^= DST##14; \
+ SRC##4 ^= d4; \
+ b15 = rol(SRC##4, 27); \
+ SRC##5 ^= d0; \
+ b16 = rol(SRC##5, 36); \
+ SRC##11 ^= d1; \
+ b17 = rol(SRC##11, 10); \
+ SRC##17 ^= d2; \
+ b18 = rol(SRC##17, 15); \
+ SRC##23 ^= d3; \
+ b19 = rol(SRC##23, 56); \
+ DST##15 = b15 ^ ((~b16) & b17); \
+ DST##16 = b16 ^ ((~b17) & b18); \
+ DST##17 = b17 ^ ((~b18) & b19); \
+ DST##18 = b18 ^ ((~b19) & b15); \
+ DST##19 = b19 ^ ((~b15) & b16); \
+ c0 ^= DST##15; \
+ c1 ^= DST##16; \
+ c2 ^= DST##17; \
+ c3 ^= DST##18; \
+ c4 ^= DST##19; \
+ SRC##2 ^= d2; \
+ b20 = rol(SRC##2, 62); \
+ SRC##8 ^= d3; \
+ b21 = rol(SRC##8, 55); \
+ SRC##14 ^= d4; \
+ b22 = rol(SRC##14, 39); \
+ SRC##15 ^= d0; \
+ b23 = rol(SRC##15, 41); \
+ SRC##21 ^= d1; \
+ b24 = rol(SRC##21, 2); \
+ DST##20 = b20 ^ ((~b21) & b22); \
+ DST##21 = b21 ^ ((~b22) & b23); \
+ DST##22 = b22 ^ ((~b23) & b24); \
+ DST##23 = b23 ^ ((~b24) & b20); \
+ DST##24 = b24 ^ ((~b20) & b21); \
+ c0 ^= DST##20; \
+ c1 ^= DST##21; \
+ c2 ^= DST##22; \
+ c3 ^= DST##23; \
+ c4 ^= DST##24; \
+
+#define KFP_R2(SRC, DST, I) KFP_R(SRC, DST, I) KFP_R(DST, SRC, I + 1)
+#define KFP_R4(SRC, DST, I) KFP_R2(SRC, DST, I) KFP_R2(SRC, DST, I + 2)
+#define KFP_R12(SRC, DST, I) \
+ KFP_R4(SRC, DST, I) KFP_R4(SRC, DST, I + 4) KFP_R4(SRC, DST, I + 8)
+
+#define KFP_DECL(P) \
+ uint64_t P##0, P##1, P##2, P##3, P##4, P##5, P##6, P##7, P##8, P##9, \
+ P##10, P##11, P##12, P##13, P##14, P##15, P##16, P##17, P##18, P##19, \
+ P##20, P##21, P##22, P##23, P##24
+
+#define KFP_BODY(ROUNDS) \
+ uint64_t *s = (uint64_t *)state; \
+ KFP_DECL(a); \
+ KFP_DECL(e); \
+ KFP_DECL(b); \
+ uint64_t c0, c1, c2, c3, c4, d0, d1, d2, d3, d4; \
+ KFP_LOAD(a, s) \
+ KFP_INIT_C(a) \
+ ROUNDS \
+ KFP_STORE(s, a)
+
+static inline void keccakf(void *state) {
+ KFP_BODY(for (int i = 0; i < 24; i += 4) { KFP_R4(a, e, i) })
+}
+
+static inline void keccak12(void *state) {
+ KFP_BODY(for (int i = 12; i < 24; i += 4) { KFP_R4(a, e, i) })
+}
+
+#endif /* FINWO_SCALAR_PERM_H */
