use std::sync::OnceLock;
use super::scalar::update_state_scalar;
type Matrix = [u32; 32];
const CHAIN_LEN: usize = u64::BITS as usize;
fn one_zero_byte_operator() -> Matrix {
let mut matrix = [0u32; 32];
for (bit, image) in matrix.iter_mut().enumerate() {
*image = update_state_scalar(1u32 << bit, &[0u8]);
}
matrix
}
#[inline]
fn apply(matrix: &Matrix, vector: u32) -> u32 {
let mut sum = 0u32;
let mut remaining = vector;
let mut bit = 0usize;
while remaining != 0 {
if remaining & 1 != 0 {
sum ^= matrix[bit];
}
remaining >>= 1;
bit += 1;
}
sum
}
#[inline]
fn square(matrix: &Matrix) -> Matrix {
let mut result = [0u32; 32];
for (bit, image) in result.iter_mut().enumerate() {
*image = apply(matrix, matrix[bit]);
}
result
}
fn doubling_chain() -> &'static [Matrix; CHAIN_LEN] {
static CHAIN: OnceLock<[Matrix; CHAIN_LEN]> = OnceLock::new();
CHAIN.get_or_init(|| {
let mut chain = [[0u32; 32]; CHAIN_LEN];
chain[0] = one_zero_byte_operator();
for previous in 1..CHAIN_LEN {
chain[previous] = square(&chain[previous - 1]);
}
chain
})
}
pub(crate) fn shift_zero_bytes(reg: u32, mut n: u64) -> u32 {
let chain = doubling_chain();
let mut result = reg;
let mut bit = 0usize;
while n != 0 {
if n & 1 != 0 {
result = apply(&chain[bit], result);
}
n >>= 1;
bit += 1;
}
result
}
#[inline]
pub(crate) fn combine(head: u32, tail_from_zero: u32, tail_len: u64) -> u32 {
shift_zero_bytes(head, tail_len) ^ tail_from_zero
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, clippy::expect_used, clippy::panic)]
use super::*;
use proptest::prelude::*;
fn next_u32(state: &mut u64) -> u32 {
*state = state
.wrapping_mul(6_364_136_223_846_793_005)
.wrapping_add(1);
(*state >> 32) as u32
}
#[test]
fn shift_by_zero_is_the_identity() {
assert_eq!(shift_zero_bytes(0x1234_5678, 0), 0x1234_5678);
assert_eq!(shift_zero_bytes(0, 0), 0);
assert_eq!(shift_zero_bytes(u32::MAX, 0), u32::MAX);
}
#[test]
fn shift_matches_folding_explicit_zero_bytes_exhaustively_for_small_n() {
let mut seed = 0xC0FF_EEEEu64;
for _ in 0..8 {
let reg = next_u32(&mut seed);
for n in 0u64..=64 {
let zeros = vec![0u8; n as usize];
let expected = update_state_scalar(reg, &zeros);
assert_eq!(shift_zero_bytes(reg, n), expected, "reg {reg:#010x} n {n}");
}
}
}
#[test]
fn shift_matches_folding_explicit_zero_bytes_at_power_of_two_boundaries() {
let mut seed = 0xFEED_FACEu64;
for shift in 0u32..=20 {
let base = 1u64 << shift;
for n in [base.saturating_sub(1), base, base + 1] {
let reg = next_u32(&mut seed);
let zeros = vec![0u8; n as usize];
let expected = update_state_scalar(reg, &zeros);
assert_eq!(shift_zero_bytes(reg, n), expected, "reg {reg:#010x} n {n}");
}
}
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(64))]
#[test]
fn shift_matches_folding_explicit_zero_bytes_randomly(
reg in any::<u32>(),
n in 0u64..=1_048_576,
) {
let zeros = vec![0u8; n as usize];
let expected = update_state_scalar(reg, &zeros);
prop_assert_eq!(shift_zero_bytes(reg, n), expected);
}
#[test]
fn combine_matches_sequential_folding(
initial in any::<u32>(),
prefix_seed in any::<u64>(),
prefix_len in 0usize..=2048,
suffix_seed in any::<u64>(),
suffix_len in 0usize..=2048,
) {
let mut ps = prefix_seed | 1;
let prefix: Vec<u8> = (0..prefix_len).map(|_| next_u32(&mut ps) as u8).collect();
let mut ss = suffix_seed | 1;
let suffix: Vec<u8> = (0..suffix_len).map(|_| next_u32(&mut ss) as u8).collect();
let head = update_state_scalar(initial, &prefix);
let tail_from_zero = update_state_scalar(0, &suffix);
let combined = combine(head, tail_from_zero, suffix.len() as u64);
let mut concatenated = prefix.clone();
concatenated.extend_from_slice(&suffix);
let sequential = update_state_scalar(initial, &concatenated);
prop_assert_eq!(combined, sequential);
}
}
}