Skip to main content

openqmc/
lookup.rs

1//! Port of `oqmc/lookup.h` — randomised table lookups. A single pre-computed
2//! table (PMJ samples, blue-noise ranks) can be re-used across domains by
3//! shuffling the index and XOR-scrambling the value (random digit scramble,
4//! Kollig & Keller).
5
6use crate::permute::shuffle;
7use crate::rotate::rotate_bytes;
8
9/// Random digit scramble: XOR the value with a random number (fast, structure-
10/// preserving). The seed must be constant for a given sequence.
11#[inline]
12pub const fn random_digit_scramble(value: u32, hash: u32) -> u32 {
13    value ^ hash
14}
15
16/// Compute a randomised value from a pre-computed table.
17///
18/// `TABLE` is the row width of the table, `DEPTH` (1..=4, `<= TABLE`) the output
19/// count. The index is shuffled progressively; an index beyond the table length
20/// wraps (mask to 16 bits) and reuses samples.
21#[inline]
22pub fn shuffled_scrambled_lookup<const TABLE: usize, const DEPTH: usize>(
23    index: u32,
24    hash: u32,
25    table: &[[u32; TABLE]],
26) -> [u32; DEPTH] {
27    const { assert!(TABLE >= DEPTH, "Table width must be >= depth") };
28    const {
29        assert!(
30            DEPTH >= 1 && DEPTH <= 4,
31            "Pattern depth must be within [1, 4]"
32        )
33    };
34
35    let index = shuffle(index, hash);
36
37    let mut sample = [0u32; DEPTH];
38    let mut i = 0;
39    while i < DEPTH {
40        let row = &table[(index & 0xffff) as usize];
41        sample[i] = random_digit_scramble(row[i], rotate_bytes(hash, i as i32));
42        i += 1;
43    }
44    sample
45}
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn scramble_is_xor() {
53        assert_eq!(random_digit_scramble(0xf0f0_f0f0, 0x0f0f_0f0f), u32::MAX);
54        assert_eq!(random_digit_scramble(7, 0), 7);
55        assert_eq!(random_digit_scramble(random_digit_scramble(9, 5), 5), 9);
56    }
57
58    #[test]
59    fn lookup_indexes_the_shuffled_row_and_scrambles_columns() {
60        let table: Vec<[u32; 4]> = (0..65536u32).map(|i| [i, i + 1, i + 2, i + 3]).collect();
61        for hash in [0u32, 1, 0xdead_beef] {
62            for index in [0u32, 5, 65535, 70000] {
63                let row = (shuffle(index, hash) & 0xffff) as usize;
64                let out = shuffled_scrambled_lookup::<4, 4>(index, hash, &table);
65                for (k, &o) in out.iter().enumerate() {
66                    assert_eq!(o, table[row][k] ^ rotate_bytes(hash, k as i32));
67                }
68            }
69        }
70    }
71
72    #[test]
73    fn lookup_depth_can_be_smaller_than_the_table_width() {
74        let table: Vec<[u32; 4]> = (0..65536u32).map(|i| [i; 4]).collect();
75        let full = shuffled_scrambled_lookup::<4, 4>(42, 3, &table);
76        assert_eq!(
77            &full[..1],
78            &shuffled_scrambled_lookup::<4, 1>(42, 3, &table)[..]
79        );
80        assert_eq!(
81            &full[..2],
82            &shuffled_scrambled_lookup::<4, 2>(42, 3, &table)[..]
83        );
84        assert_eq!(
85            &full[..3],
86            &shuffled_scrambled_lookup::<4, 3>(42, 3, &table)[..]
87        );
88    }
89
90    #[test]
91    fn lookup_covers_every_row_once_over_a_full_index_range() {
92        let table: Vec<[u32; 1]> = (0..65536u32).map(|i| [i]).collect();
93        let hash = 0x1234_5678;
94        let mut seen = vec![false; 65536];
95        for index in 0..65536u32 {
96            let row = (shuffled_scrambled_lookup::<1, 1>(index, hash, &table)[0] ^ hash) as usize;
97            assert!(!seen[row]);
98            seen[row] = true;
99        }
100    }
101}