commit 4f8228dfa93cf459cf5af338e04bdacaddfa4110
parent 84898a129c15d87587135e8c245742617b0d0e7b
Author: finwo <finwo@pm.me>
Date: Sat, 10 Oct 2026 18:50:19 +0200
turboshake batching
Diffstat:
10 files changed, 131 insertions(+), 29 deletions(-)
diff --git a/README.md b/README.md
@@ -14,11 +14,12 @@ kf_shake256_batch(count, in, inlen, out, outlen); /* equal-length, packed */
```
The one-shots (`kf_shake128`, `kf_shake256`, `kf_sha3_224`, `kf_sha3_256`,
-`kf_sha3_384`, `kf_sha3_512`) are `kf_hash_fn` table entries: a call is one
-indirect jump. Batch variants are `kf_<algo>_batch`, taking `count`
-equal-length messages packed back to back. `kf_turboshake128` and
-`kf_turboshake256` implement TurboSHAKE (same sponge over Keccak-p[1600,12],
-domain `0x1F`), about 1.9x faster than SHAKE.
+`kf_sha3_384`, `kf_sha3_512`, `kf_turboshake128`, `kf_turboshake256`) are
+`kf_hash_fn` table entries: a call is one indirect jump. Batch variants are
+`kf_<algo>_batch`, taking `count` equal-length messages packed back to back.
+TurboSHAKE is the same sponge over Keccak-p[1600,12] with domain `0x1F`, about
+1.9x faster than SHAKE; its batch entries use a separately registered 12-round
+permutation.
## Build
diff --git a/bench/bench.c b/bench/bench.c
@@ -71,6 +71,7 @@ static double time_batch(kf_batch_fn fn, size_t count, const uint8_t *in,
typedef struct {
const char *label;
kf_batch_perm_fn perm;
+ kf_batch_perm_fn perm12;
int lanes;
} batch_t;
@@ -80,14 +81,16 @@ static void case_all(const char *title, const oneshot_t *os, int nos,
size_t outlen, uint8_t *in, uint8_t *out, int reps,
uint64_t target_ns) {
double bd = -1.0, bos[4], bbs[4];
- size_t iters = pick_iters(donor, out, outlen, in, inlen, target_ns);
+ kf_fn iters_fn = donor ? donor : os[0].fn;
+ size_t iters = pick_iters(iters_fn, out, outlen, in, inlen, target_ns);
for (int i = 0; i < nos; i++) bos[i] = -1.0;
for (int i = 0; i < nbs; i++) bbs[i] = -1.0;
size_t biters = 0;
if (nbs > 0) {
- kf_batch_perm = bs[0].perm;
- kf_batch_lanes = bs[0].lanes;
+ kf_batch_perm = bs[0].perm;
+ kf_batch_perm12 = bs[0].perm12;
+ kf_batch_lanes = bs[0].lanes;
double per = time_batch(batch_fn, count, in, inlen, out, outlen, 200);
if (per <= 0.0) per = 1.0;
biters = (size_t)((double)target_ns / (per * (double)count));
@@ -95,22 +98,27 @@ static void case_all(const char *title, const oneshot_t *os, int nos,
}
for (int r = 0; r < reps; r++) {
- double d = time_once(donor, out, outlen, in, inlen, iters);
- if (bd < 0.0 || d < bd) bd = d;
+ if (donor != NULL) {
+ double d = time_once(donor, out, outlen, in, inlen, iters);
+ if (bd < 0.0 || d < bd) bd = d;
+ }
for (int i = 0; i < nos; i++) {
double v = time_once(os[i].fn, out, outlen, in, inlen, iters);
if (bos[i] < 0.0 || v < bos[i]) bos[i] = v;
}
for (int i = 0; i < nbs; i++) {
- kf_batch_perm = bs[i].perm;
- kf_batch_lanes = bs[i].lanes;
+ kf_batch_perm = bs[i].perm;
+ kf_batch_perm12 = bs[i].perm12;
+ kf_batch_lanes = bs[i].lanes;
double v = time_batch(batch_fn, count, in, inlen, out, outlen, biters);
if (bbs[i] < 0.0 || v < bbs[i]) bbs[i] = v;
}
}
printf("%s\n", title);
- printf(" %-10s %9.2f ns/hash %9.3f Mh/s\n", "donor", bd, 1000.0 / bd);
+ if (donor != NULL) {
+ printf(" %-10s %9.2f ns/hash %9.3f Mh/s\n", "donor", bd, 1000.0 / bd);
+ }
for (int i = 0; i < nos; i++)
printf(" %-10s %9.2f ns/hash %9.3f Mh/s\n", os[i].label, bos[i],
1000.0 / bos[i]);
@@ -149,16 +157,20 @@ int main(void) {
{"scalar", kf_scalar_shake256},
{kf_backend_name(), kf_shake256},
};
+ const oneshot_t ts256[] = {
+ {"scalar", kf_scalar_turboshake256},
+ {kf_backend_name(), kf_turboshake256},
+ };
batch_t batch[4];
int nb = 0;
#if (defined(__x86_64__) || defined(_M_X64) || defined(__i386__)) && \
!defined(KECCAK_FAST_NO_AVX2)
- batch[nb++] = (batch_t){"avx2 x4", kf_avx2_batch, 4};
+ batch[nb++] = (batch_t){"avx2 x4", kf_avx2_batch, kf_avx2_batch12, 4};
#endif
#if (defined(__x86_64__) || defined(_M_X64) || defined(__i386__)) && \
!defined(KECCAK_FAST_NO_AVX512)
- batch[nb++] = (batch_t){"avx512 x8", kf_avx512_batch, 8};
+ batch[nb++] = (batch_t){"avx512 x8", kf_avx512_batch, kf_avx512_batch12, 8};
#endif
case_all("SHA3-256 32->32, per hash", sha3, 2, batch, nb, kct_sha3_256,
@@ -169,6 +181,8 @@ int main(void) {
kf_shake256_batch, 64, 32, 32, in, out, reps, target_ns);
case_all("SHAKE256 32->1088, per hash", shake, 2, batch, nb, kct_shake256,
kf_shake256_batch, 64, 32, 1088, in, out, reps, target_ns);
+ case_all("TurboSHAKE256 32->32, per hash", ts256, 2, batch, nb, NULL,
+ kf_turboshake256_batch, 64, 32, 32, in, out, reps, target_ns);
printf("sink %llu\n", (unsigned long long)g_sink);
return 0;
diff --git a/src/backend/avx2.c b/src/backend/avx2.c
@@ -100,6 +100,22 @@ static void kf_permute_x4(uint64_t s[4][25]) {
}
__attribute__((target("avx2")))
+static void kf_permute_x4_12(uint64_t s[4][25]) {
+ __m256i v[25];
+ uint64_t tmp[4];
+
+ for (int j = 0; j < 25; j++) {
+ for (int i = 0; i < 4; i++) tmp[i] = s[i][j];
+ v[j] = _mm256_loadu_si256((const __m256i *)tmp);
+ }
+ for (int i = 12; i < 24; i++) kf_avx2_round_x4(v, RC[i]);
+ for (int j = 0; j < 25; j++) {
+ _mm256_storeu_si256((__m256i *)tmp, v[j]);
+ for (int i = 0; i < 4; i++) s[i][j] = tmp[i];
+ }
+}
+
+__attribute__((target("avx2")))
void kf_avx2_batch(uint64_t states[][25], size_t count) {
size_t i = 0;
for (; i + 4 <= count; i += 4) {
@@ -110,12 +126,22 @@ void kf_avx2_batch(uint64_t states[][25], size_t count) {
}
}
+__attribute__((target("avx2")))
+void kf_avx2_batch12(uint64_t states[][25], size_t count) {
+ size_t i = 0;
+ for (; i + 4 <= count; i += 4) {
+ kf_permute_x4_12(&states[i]);
+ }
+ if (i < count) kf_scalar_batch12(&states[i], count - i);
+}
+
__attribute__((constructor)) static void kf_avx2_register(void) {
if (!__builtin_cpu_supports("avx2")) {
return;
}
if (kf_batch_priority <= KF_PRIO_AVX2) {
kf_batch_perm = kf_avx2_batch;
+ kf_batch_perm12 = kf_avx2_batch12;
kf_batch_priority = KF_PRIO_AVX2;
kf_batch_lanes = 4;
kf_batch_label = "avx2";
diff --git a/src/backend/avx512.c b/src/backend/avx512.c
@@ -96,6 +96,22 @@ static void kf_permute_x8(uint64_t s[8][25]) {
}
__attribute__((target("avx512f")))
+static void kf_permute_x8_12(uint64_t s[8][25]) {
+ __m512i v[25];
+ uint64_t tmp[8];
+
+ for (int j = 0; j < 25; j++) {
+ for (int i = 0; i < 8; i++) tmp[i] = s[i][j];
+ v[j] = _mm512_loadu_si512((const __m512i *)tmp);
+ }
+ for (int i = 12; i < 24; i++) kf_avx512_round_x8(v, RC[i]);
+ for (int j = 0; j < 25; j++) {
+ _mm512_storeu_si512((__m512i *)tmp, v[j]);
+ for (int i = 0; i < 8; i++) s[i][j] = tmp[i];
+ }
+}
+
+__attribute__((target("avx512f")))
void kf_avx512_batch(uint64_t states[][25], size_t count) {
size_t i = 0;
for (; i + 8 <= count; i += 8) {
@@ -106,12 +122,22 @@ void kf_avx512_batch(uint64_t states[][25], size_t count) {
}
}
+__attribute__((target("avx512f")))
+void kf_avx512_batch12(uint64_t states[][25], size_t count) {
+ size_t i = 0;
+ for (; i + 8 <= count; i += 8) {
+ kf_permute_x8_12(&states[i]);
+ }
+ if (i < count) kf_scalar_batch12(&states[i], count - i);
+}
+
__attribute__((constructor)) static void kf_avx512_register(void) {
if (!__builtin_cpu_supports("avx512f")) {
return;
}
if (kf_batch_priority <= KF_PRIO_AVX512) {
kf_batch_perm = kf_avx512_batch;
+ kf_batch_perm12 = kf_avx512_batch12;
kf_batch_priority = KF_PRIO_AVX512;
kf_batch_lanes = 8;
kf_batch_label = "avx512";
diff --git a/src/backend/scalar.c b/src/backend/scalar.c
@@ -35,6 +35,12 @@ void kf_scalar_batch(uint64_t states[][25], size_t count) {
}
}
+void kf_scalar_batch12(uint64_t states[][25], size_t count) {
+ for (size_t i = 0; i < count; i++) {
+ keccak12(states[i]);
+ }
+}
+
__attribute__((constructor)) static void kf_scalar_register(void) {
if (kf_backend_priority <= KF_PRIO_SCALAR) {
kf_shake128 = kf_scalar_shake128;
@@ -50,6 +56,7 @@ __attribute__((constructor)) static void kf_scalar_register(void) {
}
if (kf_batch_priority <= KF_PRIO_SCALAR) {
kf_batch_perm = kf_scalar_batch;
+ kf_batch_perm12 = kf_scalar_batch12;
kf_batch_priority = KF_PRIO_SCALAR;
kf_batch_lanes = 1;
kf_batch_label = "scalar";
diff --git a/src/backend/scalar_bmi.c b/src/backend/scalar_bmi.c
@@ -28,6 +28,12 @@ void kf_bmi_batch(uint64_t states[][25], size_t count) {
}
}
+void kf_bmi_batch12(uint64_t states[][25], size_t count) {
+ for (size_t i = 0; i < count; i++) {
+ keccak12(states[i]);
+ }
+}
+
__attribute__((constructor)) static void kf_bmi_register(void) {
#if defined(__clang__)
if (!__builtin_cpu_supports("bmi")) {
@@ -50,6 +56,7 @@ __attribute__((constructor)) static void kf_bmi_register(void) {
}
if (kf_batch_priority <= KF_PRIO_BMI) {
kf_batch_perm = kf_bmi_batch;
+ kf_batch_perm12 = kf_bmi_batch12;
kf_batch_priority = KF_PRIO_BMI;
kf_batch_lanes = 1;
kf_batch_label = "scalar+bmi";
diff --git a/src/keccak-fast-internal.h b/src/keccak-fast-internal.h
@@ -16,6 +16,7 @@ typedef void (*kf_batch_perm_fn)(uint64_t states[][25], size_t count);
#define KF_PRIO_AVX512 30
extern kf_batch_perm_fn kf_batch_perm;
+extern kf_batch_perm_fn kf_batch_perm12;
extern int kf_batch_priority;
extern int kf_batch_lanes;
@@ -41,18 +42,22 @@ int kf_scalar_turboshake256(uint8_t *out, size_t outlen, const uint8_t *in,
size_t inlen);
void kf_scalar_permute(uint64_t state[25]);
void kf_scalar_batch(uint64_t states[][25], size_t count);
+void kf_scalar_batch12(uint64_t states[][25], size_t count);
#if (defined(__x86_64__) || defined(_M_X64) || defined(__i386__)) && \
!defined(KECCAK_FAST_NO_BMI)
void kf_bmi_batch(uint64_t states[][25], size_t count);
+void kf_bmi_batch12(uint64_t states[][25], size_t count);
#endif
#if (defined(__x86_64__) || defined(_M_X64) || defined(__i386__)) && \
!defined(KECCAK_FAST_NO_AVX2)
void kf_avx2_batch(uint64_t states[][25], size_t count);
+void kf_avx2_batch12(uint64_t states[][25], size_t count);
#endif
#if (defined(__x86_64__) || defined(_M_X64) || defined(__i386__)) && \
!defined(KECCAK_FAST_NO_AVX512)
void kf_avx512_batch(uint64_t states[][25], size_t count);
+void kf_avx512_batch12(uint64_t states[][25], size_t count);
#endif
#endif
diff --git a/src/keccak-fast.c b/src/keccak-fast.c
@@ -21,6 +21,7 @@ int kf_backend_priority = KF_PRIO_SCALAR;
const char *kf_backend_label = "scalar";
kf_batch_perm_fn kf_batch_perm = kf_scalar_batch;
+kf_batch_perm_fn kf_batch_perm12 = kf_scalar_batch12;
int kf_batch_priority = KF_PRIO_SCALAR;
int kf_batch_lanes = 1;
const char *kf_batch_label = "scalar";
@@ -38,9 +39,10 @@ static void kf_wipe(void *p, size_t n) {
fn(p, 0, n);
}
-static void kf_sponge_group(const uint8_t *in, size_t inlen, uint8_t *out,
- size_t outlen, size_t base, size_t count,
- size_t rate, uint8_t delim) {
+static void kf_sponge_group(kf_batch_perm_fn perm, const uint8_t *in,
+ size_t inlen, uint8_t *out, size_t outlen,
+ size_t base, size_t count, size_t rate,
+ uint8_t delim) {
uint64_t states[KF_LANES_MAX][25] = {0};
uint8_t *a = (uint8_t *)states;
const uint8_t *p[KF_LANES_MAX];
@@ -57,7 +59,7 @@ static void kf_sponge_group(const uint8_t *in, size_t inlen, uint8_t *out,
for (size_t j = 0; j < rate; j++) a[i * 200 + j] ^= p[i][j];
p[i] += rate;
}
- kf_batch_perm(states, count);
+ perm(states, count);
remaining -= rate;
}
@@ -66,7 +68,7 @@ static void kf_sponge_group(const uint8_t *in, size_t inlen, uint8_t *out,
a[i * 200 + remaining] ^= delim;
a[i * 200 + rate - 1] ^= 0x80;
}
- kf_batch_perm(states, count);
+ perm(states, count);
size_t outrem = outlen;
while (outrem >= rate) {
@@ -75,7 +77,7 @@ static void kf_sponge_group(const uint8_t *in, size_t inlen, uint8_t *out,
o[i] += rate;
}
outrem -= rate;
- kf_batch_perm(states, count);
+ perm(states, count);
}
for (size_t i = 0; i < count; i++) {
memcpy(o[i], a + i * 200, outrem);
@@ -84,9 +86,9 @@ static void kf_sponge_group(const uint8_t *in, size_t inlen, uint8_t *out,
kf_wipe(states, sizeof states);
}
-static int kf_batch_impl(kf_hash_fn one, size_t count, const uint8_t *in,
- size_t inlen, uint8_t *out, size_t outlen,
- size_t rate, uint8_t delim) {
+static int kf_batch_impl(kf_hash_fn one, kf_batch_perm_fn perm, size_t count,
+ const uint8_t *in, size_t inlen, uint8_t *out,
+ size_t outlen, size_t rate, uint8_t delim) {
if (count == 0) return 0;
if ((out == NULL) || ((in == NULL) && inlen != 0) || (rate >= 200)) return -1;
@@ -97,7 +99,7 @@ static int kf_batch_impl(kf_hash_fn one, size_t count, const uint8_t *in,
if (lanes > 1) {
size_t l = (size_t)lanes;
for (; base + l <= count; base += l) {
- kf_sponge_group(in, inlen, out, outlen, base, l, rate, delim);
+ kf_sponge_group(perm, in, inlen, out, outlen, base, l, rate, delim);
}
}
for (; base < count; base++) {
@@ -109,15 +111,21 @@ static int kf_batch_impl(kf_hash_fn one, size_t count, const uint8_t *in,
#define KF_DEFSHAKE_BATCH(bits) \
int kf_shake##bits##_batch(size_t count, const uint8_t *in, size_t inlen, \
uint8_t *out, size_t outlen) { \
- return kf_batch_impl(kf_shake##bits, count, in, inlen, out, outlen, \
- KF_RATE(bits), KF_DOMAIN_SHAKE); \
+ return kf_batch_impl(kf_shake##bits, kf_batch_perm, count, in, inlen, out, \
+ outlen, KF_RATE(bits), KF_DOMAIN_SHAKE); \
}
#define KF_DEFSHA3_BATCH(bits) \
int kf_sha3_##bits##_batch(size_t count, const uint8_t *in, size_t inlen, \
uint8_t *out, size_t outlen) { \
if (outlen > ((bits) / 8)) return -1; \
- return kf_batch_impl(kf_sha3_##bits, count, in, inlen, out, outlen, \
- KF_RATE(bits), KF_DOMAIN_SHA3); \
+ return kf_batch_impl(kf_sha3_##bits, kf_batch_perm, count, in, inlen, out, \
+ outlen, KF_RATE(bits), KF_DOMAIN_SHA3); \
+ }
+#define KF_DEFTURBOSHAKE_BATCH(bits) \
+ int kf_turboshake##bits##_batch(size_t count, const uint8_t *in, \
+ size_t inlen, uint8_t *out, size_t outlen) { \
+ return kf_batch_impl(kf_turboshake##bits, kf_batch_perm12, count, in, \
+ inlen, out, outlen, KF_RATE(bits), KF_DOMAIN_SHAKE); \
}
KF_DEFSHAKE_BATCH(128)
@@ -126,3 +134,5 @@ KF_DEFSHA3_BATCH(224)
KF_DEFSHA3_BATCH(256)
KF_DEFSHA3_BATCH(384)
KF_DEFSHA3_BATCH(512)
+KF_DEFTURBOSHAKE_BATCH(128)
+KF_DEFTURBOSHAKE_BATCH(256)
diff --git a/src/keccak-fast.h b/src/keccak-fast.h
@@ -28,6 +28,10 @@ int kf_sha3_384_batch(size_t count, const uint8_t *in, size_t inlen,
uint8_t *out, size_t outlen);
int kf_sha3_512_batch(size_t count, const uint8_t *in, size_t inlen,
uint8_t *out, size_t outlen);
+int kf_turboshake128_batch(size_t count, const uint8_t *in, size_t inlen,
+ uint8_t *out, size_t outlen);
+int kf_turboshake256_batch(size_t count, const uint8_t *in, size_t inlen,
+ uint8_t *out, size_t outlen);
const char *kf_backend_name(void);
const char *kf_batch_name(void);
diff --git a/test/batch.c b/test/batch.c
@@ -35,6 +35,8 @@ int main(void) {
{"sha3_256", kf_sha3_256, kf_sha3_256_batch, 32},
{"sha3_384", kf_sha3_384, kf_sha3_384_batch, 48},
{"sha3_512", kf_sha3_512, kf_sha3_512_batch, 64},
+ {"turboshake128", kf_turboshake128, kf_turboshake128_batch, 32},
+ {"turboshake256", kf_turboshake256, kf_turboshake256_batch, 64},
};
static const size_t counts[] = {1, 3, 4, 5, 8, 17};
static const size_t inlens[] = {32, 200};
