1use crate::permute::{laine_karras_permutation, reverse_and_shuffle};
24use crate::reverse::{reverse_bits16, reverse_bits32};
25use crate::rotate::rotate_bytes;
26
27#[rustfmt::skip]
34const DIRECTIONS: [[u16; 16]; 4] = [
35 [
36 0b1000000000000000, 0b0100000000000000, 0b0010000000000000, 0b0001000000000000,
37 0b0000100000000000, 0b0000010000000000, 0b0000001000000000, 0b0000000100000000,
38 0b0000000010000000, 0b0000000001000000, 0b0000000000100000, 0b0000000000010000,
39 0b0000000000001000, 0b0000000000000100, 0b0000000000000010, 0b0000000000000001,
40 ],
41 [
42 0b1111111111111111, 0b0101010101010101, 0b0011001100110011, 0b0001000100010001,
43 0b0000111100001111, 0b0000010100000101, 0b0000001100000011, 0b0000000100000001,
44 0b0000000011111111, 0b0000000001010101, 0b0000000000110011, 0b0000000000010001,
45 0b0000000000001111, 0b0000000000000101, 0b0000000000000011, 0b0000000000000001,
46 ],
47 [
48 0b1110011110011110, 0b0111100111100111, 0b0011000100100011, 0b0001001000110001,
49 0b0000111000001001, 0b0000011100001110, 0b0000001100000010, 0b0000000100000011,
50 0b0000000011100111, 0b0000000001111001, 0b0000000000110001, 0b0000000000010010,
51 0b0000000000001110, 0b0000000000000111, 0b0000000000000011, 0b0000000000000001,
52 ],
53 [
54 0b1001111001111001, 0b0111100111100111, 0b0010001100010010, 0b0001001000110001,
55 0b0000100100000111, 0b0000011100001110, 0b0000001000000001, 0b0000000100000011,
56 0b0000000010011110, 0b0000000001111001, 0b0000000000100011, 0b0000000000010010,
57 0b0000000000001001, 0b0000000000000111, 0b0000000000000010, 0b0000000000000001,
58 ],
59];
60
61const TABLES: [[[u16; 256]; 2]; 4] = {
67 let mut t = [[[0u16; 256]; 2]; 4];
68 let mut d = 0;
69 while d < 4 {
70 let mut half = 0;
71 while half < 2 {
72 let mut b = 0;
73 while b < 256 {
74 let mut bits = 0u16;
75 let mut k = 0;
76 while k < 8 {
77 if b & (1 << k) != 0 {
78 bits ^= DIRECTIONS[d][k + 8 * half];
79 }
80 k += 1;
81 }
82 t[d][half][b] = bits;
83 b += 1;
84 }
85 half += 1;
86 }
87 d += 1;
88 }
89 t
90};
91
92#[inline]
98pub fn sz_reversed_basis(index: u16, dimension: usize) -> u16 {
99 debug_assert!(dimension <= 3);
100
101 if dimension == 0 {
102 return reverse_bits16(index);
105 }
106
107 let t = &TABLES[dimension];
108 t[0][(index & 0xff) as usize] ^ t[1][(index >> 8) as usize]
109}
110
111#[inline]
121pub const fn sz_to_reversed(mut index: u16, dimension: usize) -> u16 {
122 debug_assert!(dimension <= 3);
123
124 match dimension {
125 1 => {
126 index ^= (index & 0xff00) >> 8;
127 index ^= (index & 0xf0f0) >> 4;
128 index ^= (index & 0xcccc) >> 2;
129 index ^= (index & 0xaaaa) >> 1;
130 }
131 2 => {
132 index ^= (index & 0xaa00) >> 9;
133 index ^= (index & 0xaa00) >> 8;
134 index ^= (index & 0x5500) >> 7;
135 index ^= (index & 0x4040) >> 6;
136 index ^= (index & 0xa0a0) >> 5;
137 index ^= (index & 0x5050) >> 4;
138 index ^= (index & 0xd8d8) >> 3;
139 index ^= (index & 0xcccc) >> 2;
140 index ^= (index & 0xeeee) >> 1;
141 }
142 3 => {
143 index ^= (index & 0xaa00) >> 9;
144 index ^= (index & 0x5500) >> 8;
145 index ^= (index & 0x5500) >> 7;
146 index ^= (index & 0x4040) >> 6;
147 index ^= (index & 0xa0a0) >> 5;
148 index ^= (index & 0xa0a0) >> 4;
149 index ^= (index & 0xd8d8) >> 3;
150 index ^= (index & 0x4444) >> 2;
151 index ^= (index & 0x4444) >> 1;
152 }
153 _ => {}
154 }
155
156 index
157}
158
159#[inline]
162pub const fn scramble_and_reverse(value: u32, seed: u32) -> u32 {
163 reverse_bits32(laine_karras_permutation(value, seed))
164}
165
166#[inline]
172pub fn shuffled_scrambled_sobol<const DEPTH: usize>(index: u32, seed: u32) -> [u32; DEPTH] {
173 const {
174 assert!(
175 DEPTH >= 1 && DEPTH <= 4,
176 "Pattern depth must be within [1, 4]"
177 )
178 };
179
180 let index = reverse_and_shuffle(index, seed);
181
182 let mut sample = [0u32; DEPTH];
183 let mut i = 0;
184 while i < DEPTH {
185 let s = sz_reversed_basis((index >> 16) as u16, i) as u32;
188 sample[i] = scramble_and_reverse(s, rotate_bytes(seed, i as i32));
189 i += 1;
190 }
191 sample
192}
193
194#[cfg(test)]
195mod tests {
196 use super::*;
197 use crate::pcg;
198
199 #[test]
202 fn tables_match_the_direction_matrix_loop() {
203 for (d, matrix) in DIRECTIONS.iter().enumerate() {
204 for index in 0..=u16::MAX {
205 let mut bits = 0u16;
206 for (k, &column) in matrix.iter().enumerate() {
207 if index & (1 << k) != 0 {
208 bits ^= column;
209 }
210 }
211 let want = if d == 0 { reverse_bits16(index) } else { bits };
212 assert_eq!(sz_reversed_basis(index, d), want, "d={d} index={index}");
213 }
214 }
215 }
216
217 fn sz_reversed_basis_program(mut index: u16, dimension: usize) -> u16 {
220 match dimension {
221 1 => {
222 index ^= (index & 0x00ff) << 8;
223 index ^= (index & 0x0f0f) << 4;
224 index ^= (index & 0x3333) << 2;
225 index ^= (index & 0x5555) << 1;
226 }
227 2 => {
228 index ^= (index & 0x0055) << 9;
229 index ^= (index & 0x0055) << 8;
230 index ^= (index & 0x00aa) << 7;
231 index ^= (index & 0x0202) << 6;
232 index ^= (index & 0x0505) << 5;
233 index ^= (index & 0x0a0a) << 4;
234 index ^= (index & 0x1b1b) << 3;
235 index ^= (index & 0x3333) << 2;
236 index ^= (index & 0x7777) << 1;
237 }
238 3 => {
239 index ^= (index & 0x0055) << 9;
240 index ^= (index & 0x00aa) << 8;
241 index ^= (index & 0x00aa) << 7;
242 index ^= (index & 0x0202) << 6;
243 index ^= (index & 0x0505) << 5;
244 index ^= (index & 0x0505) << 4;
245 index ^= (index & 0x1b1b) << 3;
246 index ^= (index & 0x2222) << 2;
247 index ^= (index & 0x2222) << 1;
248 }
249 _ => {}
250 }
251 reverse_bits16(index)
252 }
253
254 #[test]
256 fn tables_match_upstream_reversed_basis_program() {
257 for d in 0..4 {
258 for index in 0..=u16::MAX {
259 assert_eq!(
260 sz_reversed_basis(index, d),
261 sz_reversed_basis_program(index, d),
262 "d={d} index={index}"
263 );
264 }
265 }
266 }
267
268 #[test]
270 fn to_reversed_is_reversed_basis_of_the_reversed_index() {
271 for d in 0..4 {
272 for index in 0..=u16::MAX {
273 assert_eq!(
274 sz_to_reversed(index, d),
275 sz_reversed_basis(reverse_bits16(index), d),
276 "d={d} index={index}"
277 );
278 }
279 }
280 }
281
282 #[test]
285 fn dimension_3_chains_from_dimension_2() {
286 for index in 0..=u16::MAX {
287 assert_eq!(
288 sz_to_reversed(sz_to_reversed(index, 2), 1),
289 sz_to_reversed(index, 3),
290 "index={index}"
291 );
292 }
293 }
294
295 #[test]
298 fn draw_matches_upstream_host_path() {
299 for seed in [0u32, 1, pcg::hash(7), 0xdead_beef, u32::MAX] {
300 for index in (0..1u32 << 16).step_by(7).chain([u32::MAX, 1 << 20]) {
301 let shuffled = reverse_and_shuffle(index, seed);
302 let natural = reverse_bits16((shuffled >> 16) as u16);
303 let mut value = [0u16; 4];
304 for i in 0..4 {
305 value[i] = if i == 3 {
306 sz_to_reversed(value[2], 1)
307 } else {
308 sz_to_reversed(natural, i)
309 };
310 }
311 let want: [u32; 4] = std::array::from_fn(|i| {
312 scramble_and_reverse(value[i] as u32, rotate_bytes(seed, i as i32))
313 });
314 assert_eq!(shuffled_scrambled_sobol::<4>(index, seed), want);
315 }
316 }
317 }
318
319 #[test]
320 fn dim0_is_van_der_corput() {
321 for index in [0u16, 1, 2, 3, 255, 12345, 65535] {
323 assert_eq!(sz_reversed_basis(index, 0), reverse_bits16(index));
324 }
325 }
326
327 #[test]
328 fn first_sample_is_origin() {
329 let s = shuffled_scrambled_sobol::<4>(0, pcg::hash(0));
331 let s2 = shuffled_scrambled_sobol::<4>(0, pcg::hash(0));
335 assert_eq!(s, s2);
336 }
337
338 #[test]
342 fn is_02_net() {
343 const M: u32 = 8;
344 const N: u32 = 1 << M;
345 let seed = pcg::hash(0);
346
347 for i in 0..=M {
348 let x_res = 1u32 << i;
349 let y_res = 1u32 << (M - i);
350 assert_eq!(x_res * y_res, N);
351
352 let x_width = u32::MAX / x_res;
353 let y_width = u32::MAX / y_res;
354
355 let mut strata = vec![false; N as usize];
356 for index in 0..N {
357 let out = shuffled_scrambled_sobol::<2>(index, seed);
358 let x = out[0] / x_width;
359 let y = out[1] / y_width;
360 let cell = (y * x_res + x) as usize;
361 assert!(!strata[cell], "stratum {cell} occupied twice");
362 strata[cell] = true;
363 }
364 assert!(strata.iter().all(|&b| b));
365 }
366 }
367
368 #[test]
369 fn direction_matrices_are_triangular_with_unit_diagonal() {
370 for (dim, matrix) in DIRECTIONS.iter().enumerate() {
373 for (k, &col) in matrix.iter().enumerate() {
374 assert_eq!(col.leading_zeros() as usize, k, "dim {dim} col {k}");
375 }
376 }
377 }
378
379 #[test]
380 fn direction_dim0_is_the_identity_in_reversed_order() {
381 for (k, &col) in DIRECTIONS[0].iter().enumerate() {
382 assert_eq!(col, 1 << (15 - k));
383 }
384 }
385
386 #[test]
387 fn direction_dim1_is_the_pascal_triangle_matrix() {
388 for (k, &col) in DIRECTIONS[1].iter().enumerate() {
392 let mut expected = 0u16;
393 for j in 0..16 {
394 if (j & k) == k {
395 expected |= 1 << (15 - j);
396 }
397 }
398 assert_eq!(col, expected, "col {k}");
399 }
400 }
401
402 #[test]
403 fn every_direction_column_ends_with_the_unit_column() {
404 for matrix in &DIRECTIONS {
405 assert_eq!(matrix[15], 1);
406 }
407 }
408
409 #[test]
410 fn dim0_shortcut_matches_the_generic_matrix_path() {
411 for index in 0..=u16::MAX {
412 let mut bits = 0u16;
413 for (k, &col) in DIRECTIONS[0].iter().enumerate() {
414 if index & (1 << k) != 0 {
415 bits ^= col;
416 }
417 }
418 assert_eq!(bits, sz_reversed_basis(index, 0));
419 }
420 }
421
422 #[test]
423 fn reversed_index_is_a_bijection_in_each_dimension() {
424 for dim in 0..4 {
425 let mut seen = vec![false; 1 << 16];
426 for index in 0..=u16::MAX {
427 let v = sz_reversed_basis(index, dim) as usize;
428 assert!(!seen[v], "dim {dim}");
429 seen[v] = true;
430 }
431 }
432 }
433
434 #[test]
435 fn scramble_and_reverse_composes_lk_and_reverse() {
436 for v in [0u32, 1, 0xffff, 0x8000_0000, u32::MAX] {
437 for seed in [0u32, 7, 0xdead_beef] {
438 assert_eq!(
439 scramble_and_reverse(v, seed),
440 reverse_bits32(laine_karras_permutation(v, seed))
441 );
442 }
443 }
444 }
445
446 #[test]
447 fn shuffled_uses_the_top_16_bits_of_the_shuffled_index() {
448 let seed = pcg::hash(5);
450 for index in [0u32, 3, 1000, 65535] {
451 let shuffled = reverse_and_shuffle(index, seed);
452 let r = (shuffled >> 16) as u16;
453 let expected: [u32; 4] = std::array::from_fn(|d| {
454 scramble_and_reverse(sz_reversed_basis(r, d) as u32, rotate_bytes(seed, d as i32))
455 });
456 assert_eq!(shuffled_scrambled_sobol::<4>(index, seed), expected);
457 }
458 }
459
460 #[test]
461 fn is_02_net_for_several_seeds_and_sizes() {
462 for seed in [pcg::hash(1), pcg::hash(2), 0, u32::MAX] {
463 for m in 1..=10u32 {
464 let n = 1u32 << m;
465 for i in 0..=m {
466 let xb = i;
467 let yb = m - i;
468 let mut strata = vec![false; n as usize];
469 for index in 0..n {
470 let out = shuffled_scrambled_sobol::<2>(index, seed);
471 let x = if xb == 0 { 0 } else { out[0] >> (32 - xb) };
472 let y = if yb == 0 { 0 } else { out[1] >> (32 - yb) };
473 let cell = ((y << xb) | x) as usize;
474 assert!(!strata[cell], "seed {seed:#x} m={m}");
475 strata[cell] = true;
476 }
477 }
478 }
479 }
480 }
481}