Compile-time Evaluable Keccak Permutation Constants Hampering Performance

[itzmeanjan]

I applied following git patch on commit 7501651 but it reduces performance of keccak permutation by ~2-3%. Hence I'm not making it part of crate release yet. I'll wait for const fn in Rust to improve.

Track rust-lang/rust#57563

diff --git a/src/keccak.rs b/src/keccak.rs
index 386298f..81c49de 100644
--- a/src/keccak.rs
+++ b/src/keccak.rs
@@ -5,64 +5,140 @@ use std::simd::u64x2;
 #[cfg(feature = "simdx4")]
 use std::simd::u64x4;
 
-/// Logarithm base 2 of bit width of lane of Keccak-p\[1600, 12\] permutation
+/// Logarithm base 2 of bit width of lane of Keccak-p\[1600, 12\] permutation.
 const L: usize = 6;
 
-/// Bit width of each lane of Keccak-p\[1600, 12\] permutation
+/// Bit width of each lane of Keccak-p\[1600, 12\] permutation.
 const W: usize = 1 << L;
 
-/// \# -of rounds of Keccak permutation is applied per iteration i.e. it's Keccak-p\[1600, 12\]
+/// \# -of lanes in keccak permutation state s.t. each lane is of 64 -bit width.
+const LANE_CNT: usize = 25;
+
+/// \# -of rounds of Keccak permutation is applied per iteration i.e. it's Keccak-p\[1600, 12\].
 const ROUNDS: usize = 12;
 
-/// Lane rotation factor table taken from https://github.com/itzmeanjan/sha3/blob/b5e897ed/include/keccak.hpp#L25-L35
-const ROT: [usize; 25] = [
-    0 % W,
-    1 % W,
-    190 % W,
-    28 % W,
-    91 % W,
-    36 % W,
-    300 % W,
-    6 % W,
-    55 % W,
-    276 % W,
-    3 % W,
-    10 % W,
-    171 % W,
-    153 % W,
-    231 % W,
-    105 % W,
-    45 % W,
-    15 % W,
-    21 % W,
-    136 % W,
-    210 % W,
-    66 % W,
-    253 % W,
-    120 % W,
-    78 % W,
-];
-
-/// Permutation table taken from https://github.com/itzmeanjan/sha3/blob/b5e897ed/include/keccak.hpp#L37-L48
-const PERM: [usize; 25] = [
-    0, 6, 12, 18, 24, 3, 9, 10, 16, 22, 1, 7, 13, 19, 20, 4, 5, 11, 17, 23, 2, 8, 14, 15, 21,
-];
-
-/// Round constants taken from https://github.com/itzmeanjan/sha3/blob/b5e897ed/include/keccak.hpp#L134-L141
-const RC: [u64; ROUNDS] = [
-    2147516555,
-    9223372036854775947,
-    9223372036854808713,
-    9223372036854808579,
-    9223372036854808578,
-    9223372036854775936,
-    32778,
-    9223372039002259466,
-    9223372039002292353,
-    9223372036854808704,
-    2147483649,
-    9223372039002292232,
-];
+/// Maximum number of rounds that can be supported by Keccak-f\[1600\] permutation.
+const MAX_ROUNDS: usize = 12 + 2 * L;
+
+/// Compile-time computed lane rotation factor table used when applying ρ step mapping function.
+const ROT: [usize; LANE_CNT] = compute_rotation_factors_table();
+
+/// Compile-time computed permutation table used when applying π step mapping function.
+const PERM: [usize; LANE_CNT] = compute_permutation_table();
+
+/// Compile-time computed round constants table used when applying ι step mapping function.
+const RC: [u64; ROUNDS] = compute_round_constants_table();
+
+/// Compile-time evaluable function for generating leftwards circular rotation offset
+/// for lanes of the keccak state array, computed following step 3(a), 3(b) of algorithm 2
+/// in section 3.2.2 of https://dx.doi.org/10.6028/NIST.FIPS.202.
+const fn compute_rotation_factors_table() -> [usize; LANE_CNT] {
+    let mut table = [0usize; LANE_CNT];
+
+    let mut x = 1;
+    let mut y = 0;
+    let mut t = 0;
+    while t <= 23 {
+        table[y * 5 + x] = ((t + 1) * (t + 2) / 2) % W;
+
+        let y_prime = (2 * x + 3 * y) % 5;
+        x = y;
+        y = y_prime;
+
+        t += 1;
+    }
+
+    table
+}
+
+/// Compile-time evaluable function for generating table used during application
+/// of π step mapping function on keccak-p\[1600, 12\] permutation state. See section
+/// 3.2.3 of the specification https://dx.doi.org/10.6028/NIST.FIPS.202.
+const fn compute_permutation_table() -> [usize; LANE_CNT] {
+    let mut table = [0usize; LANE_CNT];
+
+    let mut y = 0;
+    while y < 5 {
+        let mut x = 0;
+        while x < 5 {
+            table[y * 5 + x] = x * 5 + (x + 3 * y) % 5;
+            x += 1;
+        }
+        y += 1;
+    }
+
+    table
+}
+
+/// Compile-time evaluable computation of single bit of Keccak-p\[1600, 12\] round constant,
+/// using binary LFSR, defined by primitive polynomial x^8 + x^6 + x^5 + x^4 + 1.
+///
+/// See algorithm 5 in section 3.2.5 of http://dx.doi.org/10.6028/NIST.FIPS.202.
+/// Taken from https://github.com/itzmeanjan/sha3/blob/faef1bd6f/include/keccak.hpp#L53-L91.
+const fn rc(t: usize) -> bool {
+    // step 1 of algorithm 5
+    if t % 255 == 0 {
+        return true;
+    }
+
+    // step 2 of algorithm 5
+    //
+    // note, step 3.a of algorithm 5 is also being
+    // executed in this statement ( for first iteration, with i = 1 ) !
+    let mut r = 0b10000000u16;
+
+    // step 3 of algorithm 5
+    let mut i = 1;
+    while i <= t % 255 {
+        let b0 = r & 1;
+
+        r = (r & 0b011111111) ^ ((((r >> 8) & 1) ^ b0) << 8);
+        r = (r & 0b111101111) ^ ((((r >> 4) & 1) ^ b0) << 4);
+        r = (r & 0b111110111) ^ ((((r >> 3) & 1) ^ b0) << 3);
+        r = (r & 0b111111011) ^ ((((r >> 2) & 1) ^ b0) << 2);
+
+        // step 3.f of algorithm 5
+        //
+        // note, this statement also executes step 3.a for upcoming
+        // iterations ( i.e. when i > 1 )
+        r >>= 1;
+
+        i += 1;
+    }
+
+    ((r >> 7) & 1) == 1
+}
+
+/// Compile-time evaluable computation of a 64 -bit round constant, which is XOR-ed into
+/// the very first lane ( = lane(0, 0) ) of Keccak-p\[1600, 12\] permutation state.
+///
+/// Taken from https://github.com/itzmeanjan/sha3/blob/faef1bd6f/include/keccak.hpp#L93C1-L109C2
+const fn compute_round_constant(r_idx: usize) -> u64 {
+    let mut rc_word = 0;
+
+    let mut j = 0;
+    while j < (L + 1) {
+        let boff = (1usize << j) - 1;
+        rc_word |= (rc(j + 7 * r_idx) as u64) << boff;
+
+        j += 1;
+    }
+
+    rc_word
+}
+
+/// Compile-time evaluable computation of all round constants of Keccak-p\[1600, 12\] permutation.
+const fn compute_round_constants_table() -> [u64; ROUNDS] {
+    let mut table = [0u64; ROUNDS];
+
+    let mut r_idx = MAX_ROUNDS - ROUNDS;
+    while r_idx < MAX_ROUNDS {
+        table[r_idx - ROUNDS] = compute_round_constant(r_idx);
+        r_idx += 1;
+    }
+
+    table
+}
 
 /// Keccak-p\[1600, 12\] step mapping function θ, see section 3.2.1 of SHA3
 /// specification https://dx.doi.org/10.6028/NIST.FIPS.202