Skip to main content

openqmc/
stochastic.rs

1//! Port of `oqmc/stochastic.h` — progressive multi-jittered (0,2) sequence
2//! construction (Helmer et al., "Stochastic Generation of (t,s) Sample
3//! Sequences"). Builds the first pair of dimensions; the second pair is a
4//! randomisation of the first. Used to fill the PMJ sampler's cache.
5
6use crate::lookup::shuffled_scrambled_lookup;
7use crate::pcg;
8
9/// XOR tables for the progressive (0,2) construction, from stochastic.h.
10#[rustfmt::skip]
11const PMJ_XORS: [[u16; 16]; 2] = [
12    [
13        0b0000000000000000, 0b0000000000000000, 0b0000000000000010, 0b0000000000000110,
14        0b0000000000000110, 0b0000000000001110, 0b0000000000110110, 0b0000000001001110,
15        0b0000000000010110, 0b0000000000101110, 0b0000001001110110, 0b0000011011001110,
16        0b0000011100010110, 0b0000110000101110, 0b0011000001110110, 0b0100000011001110,
17    ],
18    [
19        0b0000000000000000, 0b0000000000000001, 0b0000000000000011, 0b0000000000000011,
20        0b0000000000000111, 0b0000000000011011, 0b0000000000100111, 0b0000000000001011,
21        0b0000000000010111, 0b0000000100111011, 0b0000001101100111, 0b0000001110001011,
22        0b0000011000010111, 0b0001100000111011, 0b0010000001100111, 0b0000000010001011,
23    ],
24];
25
26/// Fill `table` (length `nsamples`, each a 4D sample) with a progressive
27/// multi-jittered (0,2) sequence.
28///
29/// `nsamples` must be `2^16`: the final randomised lookup shuffles indices across
30/// the full 16-bit range, so a smaller table would be indexed out of bounds. This
31/// matches upstream, which only ever calls it with `State64Bit::maxIndexSize`.
32pub fn stochastic_pmj_init(nsamples: usize, table: &mut [[u32; 4]]) {
33    assert_eq!(nsamples, 1 << 16, "PMJ init requires a full 2^16 table");
34    assert!(table.len() >= nsamples);
35
36    let mut buffer = vec![[0u32; 2]; nsamples];
37
38    let mut state = pcg::init();
39
40    for slot in &mut buffer[0] {
41        *slot = pcg::rng(&mut state);
42    }
43
44    let mut prev_len = 1usize;
45    let mut log_n = 0u32;
46    while prev_len < nsamples {
47        let mut i1 = 0usize;
48        let mut i2 = prev_len;
49        while i1 < prev_len && i2 < nsamples {
50            for k in 0..2 {
51                let swap_bit = 0x8000_0000u32 >> log_n;
52                let bit_mask = swap_bit - 1;
53
54                let j = i1 ^ PMJ_XORS[k][log_n as usize] as usize;
55
56                let prev_stratum = buffer[j][k] & !bit_mask;
57                let next_stratum = prev_stratum ^ swap_bit;
58
59                buffer[i2][k] = next_stratum | (pcg::rng(&mut state) & bit_mask);
60            }
61            i1 += 1;
62            i2 += 1;
63        }
64        prev_len *= 2;
65        log_n += 1;
66    }
67
68    for (i, row) in table.iter_mut().enumerate().take(nsamples) {
69        let a = shuffled_scrambled_lookup::<2, 2>(i as u32, pcg::hash(0), &buffer);
70        let b = shuffled_scrambled_lookup::<2, 2>(i as u32, pcg::hash(1), &buffer);
71        row[0] = a[0];
72        row[1] = a[1];
73        row[2] = b[0];
74        row[3] = b[1];
75    }
76}
77
78#[cfg(test)]
79mod tests {
80    use super::*;
81
82    const FULL: usize = 1 << 16;
83
84    #[test]
85    fn init_is_deterministic() {
86        let mut a = vec![[0u32; 4]; FULL];
87        let mut b = vec![[0u32; 4]; FULL];
88        stochastic_pmj_init(FULL, &mut a);
89        stochastic_pmj_init(FULL, &mut b);
90        assert_eq!(a, b);
91    }
92
93    // The first pair of a PMJ(0,2) sequence is a (0,2)-net (mirrors the Sobol
94    // 02Sequence test): for a 2^M prefix, every power-of-two stratification holds
95    // exactly one point.
96    #[test]
97    fn first_pair_is_02_net() {
98        const M: u32 = 8;
99        const N: usize = 1 << M;
100        let mut table = vec![[0u32; 4]; FULL];
101        stochastic_pmj_init(FULL, &mut table);
102        let table = &table[..N];
103
104        for i in 0..=M {
105            let x_res = 1u32 << i;
106            let y_res = 1u32 << (M - i);
107            let x_width = u32::MAX / x_res;
108            let y_width = u32::MAX / y_res;
109
110            let mut strata = vec![false; N];
111            for s in table {
112                let x = s[0] / x_width;
113                let y = s[1] / y_width;
114                let cell = (x + y * x_res) as usize;
115                assert!(!strata[cell], "stratum {cell} occupied twice");
116                strata[cell] = true;
117            }
118            assert!(strata.iter().all(|&b| b));
119        }
120    }
121
122    #[test]
123    fn xor_tables_point_inside_the_previous_prefix() {
124        // Row `log_n` of the table is XORed onto indices below 2^log_n, so its
125        // entries must stay below 2^log_n to remain in bounds.
126        for (k, row) in PMJ_XORS.iter().enumerate() {
127            assert_eq!(row[0], 0, "k={k}");
128            for (log_n, &x) in row.iter().enumerate().skip(1) {
129                assert!(
130                    (x as usize) < (1 << log_n),
131                    "k={k} log_n={log_n} xor={x:#b}"
132                );
133            }
134        }
135    }
136
137    #[test]
138    fn xor_tables_are_the_upstream_constants() {
139        assert_eq!(PMJ_XORS[0][2], 0b10);
140        assert_eq!(PMJ_XORS[0][15], 0b0100000011001110);
141        assert_eq!(PMJ_XORS[1][1], 0b1);
142        assert_eq!(PMJ_XORS[1][15], 0b0000000010001011);
143    }
144
145    #[test]
146    #[should_panic(expected = "PMJ init requires a full 2^16 table")]
147    fn rejects_partial_tables() {
148        let mut t = vec![[0u32; 4]; 16];
149        stochastic_pmj_init(16, &mut t);
150    }
151
152    #[test]
153    fn second_pair_is_also_a_02_net() {
154        const M: u32 = 8;
155        const N: usize = 1 << M;
156        let mut table = vec![[0u32; 4]; FULL];
157        stochastic_pmj_init(FULL, &mut table);
158        for i in 0..=M {
159            let xb = i;
160            let yb = M - i;
161            let mut strata = vec![false; N];
162            for s in &table[..N] {
163                let x = if xb == 0 { 0 } else { s[2] >> (32 - xb) };
164                let y = if yb == 0 { 0 } else { s[3] >> (32 - yb) };
165                let cell = ((y << xb) | x) as usize;
166                assert!(!strata[cell]);
167                strata[cell] = true;
168            }
169        }
170    }
171
172    #[test]
173    fn every_dimension_permutes_the_16_bit_strata() {
174        let mut table = vec![[0u32; 4]; FULL];
175        stochastic_pmj_init(FULL, &mut table);
176        for d in 0..4 {
177            let mut seen = vec![false; FULL];
178            for s in &table {
179                let cell = (s[d] >> 16) as usize;
180                assert!(!seen[cell], "dim {d}");
181                seen[cell] = true;
182            }
183        }
184    }
185}