Skip to main content

openqmc/
permute.rs

1//! Port of `oqmc/permute.h` — hash-based permutations. A Laine & Karras style
2//! permutation (from "Stratified Sampling for Stochastic Transparency"), with
3//! the improved constants from Nathan Vegdahl's "Building a Better LK Hash".
4//! Combined with bit reversal before and after, this forms an efficient
5//! hash-based Owen scramble.
6
7use crate::reverse::reverse_bits32;
8
9/// Laine & Karras style permutation: lower bits affect higher bits but not the
10/// reverse, so paired with reversal it becomes a hash-based Owen scramble.
11#[inline]
12pub const fn laine_karras_permutation(mut value: u32, seed: u32) -> u32 {
13    value ^= value.wrapping_mul(0x3d20adea);
14    value = value.wrapping_add(seed);
15    value = value.wrapping_mul((seed >> 16) | 1);
16    value ^= value.wrapping_mul(0x05526c56);
17    value ^= value.wrapping_mul(0x53a22864);
18    value
19}
20
21/// Reverse the bits, then apply the permutation.
22#[inline]
23pub const fn reverse_and_shuffle(value: u32, seed: u32) -> u32 {
24    laine_karras_permutation(reverse_bits32(value), seed)
25}
26
27/// A full hash-based Owen scramble (reverse, permute, reverse).
28#[inline]
29pub const fn shuffle(value: u32, seed: u32) -> u32 {
30    reverse_bits32(reverse_and_shuffle(value, seed))
31}
32
33#[cfg(test)]
34mod tests {
35    use super::*;
36
37    const PRIMES: [u32; 20] = [
38        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
39    ];
40
41    // Mirrors src/tests/permute.cpp:Reverse — reverse_and_shuffle == LK(reverse).
42    #[test]
43    fn reverse_matches_composition() {
44        let values: [u32; 3] = [
45            0b01010101010101010011001100110011,
46            0b11111111000000001111000011110000,
47            0b11111111111111110000000011111111,
48        ];
49        for value in values {
50            for prime in PRIMES {
51                let reversed = reverse_bits32(value);
52                let v2 = laine_karras_permutation(reversed, prime);
53                assert_eq!(reverse_and_shuffle(value, prime), v2);
54            }
55        }
56    }
57
58    // Mirrors src/tests/permute.cpp:FullPermutation — over a 4-bit range the
59    // low nibble of `shuffle` is a bijection.
60    #[test]
61    fn full_permutation_is_bijection() {
62        const SIZE: usize = 1 << 4;
63        for prime in PRIMES {
64            let mut seen = [false; SIZE];
65            for i in 0..SIZE as u32 {
66                let permuted = reverse_bits32(reverse_and_shuffle(i, prime));
67                assert_eq!(permuted, shuffle(i, prime));
68                let index = (permuted & (SIZE as u32 - 1)) as usize;
69                assert!(!seen[index]);
70                seen[index] = true;
71            }
72            assert!(seen.iter().all(|&b| b));
73        }
74    }
75}