1use crate::lookup::shuffled_scrambled_lookup;
7use crate::pcg;
8
9#[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
26pub 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 #[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 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}