aboutsummaryrefslogtreecommitdiff
path: root/tests
diff options
context:
space:
mode:
authorPaul Duncan <pabs@pablotron.org>2023-09-18 19:05:15 -0400
committerPaul Duncan <pabs@pablotron.org>2023-09-18 19:05:15 -0400
commit006ed7e29912cacfe8a5aacdaab13e76aadb96a5 (patch)
tree5c2071dc48c47630f3925294ab9c8e74da3cfddf /tests
parent5c30fe15905c373dc815af7eab1aea40ebb92ae4 (diff)
downloadsha3-006ed7e29912cacfe8a5aacdaab13e76aadb96a5.tar.bz2
sha3-006ed7e29912cacfe8a5aacdaab13e76aadb96a5.zip
tests/permute/permute.c: add comments
Diffstat (limited to 'tests')
-rw-r--r--tests/permute/permute.c62
1 files changed, 52 insertions, 10 deletions
diff --git a/tests/permute/permute.c b/tests/permute/permute.c
index 9ba5095..7c8afa6 100644
--- a/tests/permute/permute.c
+++ b/tests/permute/permute.c
@@ -12,6 +12,7 @@
// number of rounds for permute()
#define SHA3_NUM_ROUNDS 24
+// scalar impl of theta step
static void theta_scalar(uint64_t a[static 25]) {
const uint64_t c[5] = {
a[0] ^ a[5] ^ a[10] ^ a[15] ^ a[20],
@@ -36,6 +37,7 @@ static void theta_scalar(uint64_t a[static 25]) {
a[20] ^= d[0]; a[21] ^= d[1]; a[22] ^= d[2]; a[23] ^= d[3]; a[24] ^= d[4];
}
+// scalar impl of rho step
static void rho_scalar(uint64_t a[static 25]) {
a[1] = ROL(a[1], 1); // 1 % 64 = 1
a[2] = ROL(a[2], 62); // 190 % 64 = 62
@@ -63,6 +65,7 @@ static void rho_scalar(uint64_t a[static 25]) {
a[24] = ROL(a[24], 14); // 78 % 64 = 14
}
+// scalar impl of pi step
static void pi_scalar(uint64_t a[static 25]) {
uint64_t t[25] = { 0 };
memcpy(t, a, sizeof(t));
@@ -92,6 +95,7 @@ static void pi_scalar(uint64_t a[static 25]) {
a[24] = t[21];
}
+// scalar impl of chi step
static void chi_scalar(uint64_t a[static 25]) {
uint64_t t[25] = { 0 };
memcpy(t, a, sizeof(t));
@@ -122,6 +126,7 @@ static void chi_scalar(uint64_t a[static 25]) {
a[24] = t[24] ^ (~t[20] & t[21]);
}
+// scalar impl of iota step
static void iota_scalar(uint64_t a[static 25], const int i) {
// round constants (ambiguous in spec)
static const uint64_t RCS[] = {
@@ -136,7 +141,7 @@ static void iota_scalar(uint64_t a[static 25], const int i) {
a[0] ^= RCS[i];
}
-// keccak permutation (scalar implementation).
+// scalar impl of keccak permutation.
void permute_scalar(uint64_t a[static 25], const size_t num_rounds) {
for (int i = 0; i < (int) num_rounds; i++) {
theta_scalar(a);
@@ -150,6 +155,7 @@ void permute_scalar(uint64_t a[static 25], const size_t num_rounds) {
#ifdef __AVX512F__
#include <immintrin.h>
+// avx512 impl of theta step
static void theta_avx512(uint64_t s[static 25]) {
// unaligned load mask and permutation indices
uint8_t mask = 0x1f;
@@ -190,6 +196,7 @@ static void theta_avx512(uint64_t s[static 25]) {
_mm512_mask_storeu_epi64((void*) (s + 20), m, r4);
}
+// avx512 impl of rho step
static void rho_avx512(uint64_t s[static 25]) {
// unaligned load mask and rotate values
uint8_t mask = 0x1f;
@@ -229,6 +236,15 @@ static void rho_avx512(uint64_t s[static 25]) {
_mm512_mask_storeu_epi64((void*) (s + 20), m, r4);
}
+// avx512 impl of pi step
+//
+// note: i originally tried a simpler implementation which just copied
+// the state array out to a temporary buffer and then gathered it back
+// in shuffled order.
+//
+// the "simpler" implementation did not work correctly, so i rewrote the
+// shuffling as in-register permutations (which should actually be
+// faster).
static void pi_avx512(uint64_t s[static 25]) {
// mask bytes
uint8_t mask = 0x1f,
@@ -241,14 +257,8 @@ static void pi_avx512(uint64_t s[static 25]) {
m01 = _load_mask8(&m01b),
m23 = _load_mask8(&m23b),
m4 = _load_mask8(&m4b);
- // permutation indices (offsets into state array)
- // static uint64_t vs0[8] = { 0, 6, 12, 18, 24, 0, 0, 0 },
- // vs1[8] = { 3, 9, 10, 16, 22, 0, 0, 0 },
- // vs2[8] = { 1, 7, 13, 19, 20, 0, 0, 0 },
- // vs3[8] = { 4, 5, 11, 17, 23, 0, 0, 0 },
- // vs4[8] = { 2, 8, 14, 15, 21, 0, 0, 0 };
- // permutation indices
+ // permutation indices (offsets into state array)
//
// (note: these are masked so only the relevant indices for
// _mm512_maskz_permutex2var_epi64() in each array are filled in)
@@ -334,6 +344,7 @@ static void pi_avx512(uint64_t s[static 25]) {
_mm512_mask_storeu_epi64((void*) (s + 20), m, t4);
}
+// avx512 impl of chi step
static void chi_avx512(uint64_t s[static 25]) {
// mask bytes
uint8_t mask = 0x1f;
@@ -384,6 +395,7 @@ static void chi_avx512(uint64_t s[static 25]) {
_mm512_mask_storeu_epi64((void*) (s + 20), m, t4);
}
+// avx512 impl of iota step
static void iota_avx512(uint64_t s[static 25], const int i) {
// round constants (ambiguous in spec)
static const uint64_t RCS[] = {
@@ -407,7 +419,7 @@ static void iota_avx512(uint64_t s[static 25], const int i) {
_mm512_mask_storeu_epi64((void*) s, m0, t0);
}
-// keccak permutation (slow avx512 implementation).
+// slow avx512 impl of keccak permutation.
void permute_avx512(uint64_t a[static 25], const size_t num_rounds) {
for (int i = 0; i < (int) num_rounds; i++) {
theta_avx512(a);
@@ -418,7 +430,18 @@ void permute_avx512(uint64_t a[static 25], const size_t num_rounds) {
}
}
-// keccak permutation (fast avx512 implementation).
+// fast avx512 impl of keccak permutation
+//
+// this version is similar to permute_avx_512_slow(), except the
+// function calls are inlined as blocks, duplicate definitions have
+// been removed, and the state array loads and stores only happen at the
+// beginning and end of the function.
+//
+// there are still several optimizations that can be done. for example:
+// - iota does not need to reload the round constant every round
+// (only every 8th round)
+// - some spills could be addressed
+// - probably more unnecessary register usage
void permute_avx512_fast(uint64_t s[static 25], const size_t num_rounds) {
// unaligned load mask and permutation indices
uint8_t mask = 0x1f;
@@ -654,6 +677,14 @@ void permute_avx512_fast(uint64_t s[static 25], const size_t num_rounds) {
}
#endif /* __AVX512F__ */
+// verify that both state arrays are identical.
+//
+// if the state arrays are equal, print "$TEST_NAME passed" to standard
+// output. if the state arrays are NOT equal, then print the contents
+// of both state arrays with the differing cells highlighted to standard
+// error, then exit with an error.
+//
+// used by test_*() functions below.
static void check(const char *name, uint64_t a_scalar[static 25], uint64_t a_avx512[static 25]) {
// compare
if (!memcmp(a_scalar, a_avx512, 25 * sizeof(uint64_t))) {
@@ -689,6 +720,7 @@ static void check(const char *name, uint64_t a_scalar[static 25], uint64_t a_avx
exit(-1);
}
+// test avx512 theta
static void test_theta(void) {
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
uint64_t a_avx512[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -700,6 +732,7 @@ static void test_theta(void) {
check("test_theta()", a_scalar, a_avx512);
}
+// test avx512 rho
static void test_rho(void) {
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
uint64_t a_avx512[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -711,6 +744,7 @@ static void test_rho(void) {
check("test_rho()", a_scalar, a_avx512);
}
+// test avx512 pi
static void test_pi(void) {
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
uint64_t a_avx512[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -722,6 +756,7 @@ static void test_pi(void) {
check("test_pi()", a_scalar, a_avx512);
}
+// test avx512 chi
static void test_chi(void) {
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
uint64_t a_avx512[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -733,6 +768,7 @@ static void test_chi(void) {
check("test_chi()", a_scalar, a_avx512);
}
+// test avx512 iota
static void test_iota(void) {
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
uint64_t a_avx512[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -751,6 +787,7 @@ static void test_iota(void) {
}
}
+// test avx512 permute_slow
static void test_permute_slow(void) {
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
uint64_t a_avx512[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -763,6 +800,7 @@ static void test_permute_slow(void) {
check("test_permute_slow()", a_scalar, a_avx512);
}
+// test avx512 permute_fast
static void test_permute_fast(void) {
#ifdef __AVX512F__
uint64_t a_scalar[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -777,8 +815,10 @@ static void test_permute_fast(void) {
#endif /* __AVX512F__ */
}
+// number of times to run permutation in timing tests below
#define NUM_TIME_PERMUTES 10000000
+// time scalar keccak permutation
static void time_permute_scalar(void) {
uint64_t a[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -794,6 +834,7 @@ static void time_permute_scalar(void) {
printf("time_permute_scalar(): %zu\n", t1 - t0);
}
+// time slow avx512 keccak permutation
static void time_permute_avx512_slow(void) {
#ifdef __AVX512F__
uint64_t a[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };
@@ -813,6 +854,7 @@ static void time_permute_avx512_slow(void) {
#endif /* __AVX512F__ */
}
+// time fast avx512 keccak permutation
static void time_permute_avx512_fast(void) {
#ifdef __AVX512F__
uint64_t a[25] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 };