Skip to main content

openqmc/
owen.rs

1//! Port of `oqmc/owen.h` — Owen-scrambled SZ sequences via Brent Burley's
2//! hash-based construction ("Practical Hash-based Owen Scrambling").
3//!
4//! Since upstream `b6a204e` the generator matrices are the SZ sequences of
5//! Ahmed et al., "SZ Sequences: Binary-Constructed (0, 2^q)-Sequences"
6//! (SIGGRAPH Asia 2025), in place of the classic Sobol (Joe & Kuo) direction
7//! numbers. Dimensions 0 and 1 are identical to Sobol; dimensions 2 and 3
8//! differ, so that every pair of the four dimensions is a (0, 2)-sequence in
9//! base 4 and the four together a (0, 4)-sequence in base 16.
10//!
11//! Upstream evaluates the core as Ahmed-2024 shift-mask-xor programs, in two
12//! forms: [`sz_reversed_basis`] (bit-reversed index in, GPU path) and
13//! [`sz_to_reversed`] (natural-order index in, host path, with dimension 3
14//! chained from dimension 2 by eq. 13). Both are the same GF(2)
15//! matrix-vector product, `result = XOR over set bits k of DIRECTIONS[dim][k]`
16//! on the bit-reversed index. This port evaluates that product a byte at a
17//! time from compile-time 256-entry tables (3 KiB for dimensions 1–3), which
18//! needs no reversal and no chaining: two loads and one XOR per dimension.
19//! Exhaustive tests pin the tables to the matrices, to both upstream programs
20//! and to the eq. 13 chaining relation. Dimension 0 reduces to a 16-bit bit
21//! reversal.
22
23use crate::permute::{laine_karras_permutation, reverse_and_shuffle};
24use crate::reverse::{reverse_bits16, reverse_bits32};
25use crate::rotate::rotate_bytes;
26
27/// SZ generator matrices for dimensions 0..4, 16-bit precision, one column per
28/// index bit.
29///
30/// Copied verbatim from `directions[4][16]` in upstream's `src/tests/owen.cpp`
31/// (emitted by its `matrices` CLI tool). Dimensions 0 and 1 are the Sobol
32/// identity and Pascal matrices.
33#[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
61/// `DIRECTIONS` pre-multiplied a byte at a time: `TABLES[d][0][b]` is the XOR
62/// of `DIRECTIONS[d][k]` over the set bits `k` of the low byte `b`, and
63/// `TABLES[d][1][b]` the same for the high byte (`k + 8`). The product is
64/// linear over GF(2), so the XOR of the two entries is exactly the 16-step
65/// loop's result — the same values, in two loads.
66const 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/// SZ sequence value in the reversed basis, for a given dimension (0..4).
93///
94/// Port of `oqmc::szReversedBasis`: given a 16-bit index whose bits have been
95/// reversed, returns the SZ sequence value to 16 bits of precision, also with
96/// its bits reversed. Evaluated from byte tables; see the module docs.
97#[inline]
98pub fn sz_reversed_basis(index: u16, dimension: usize) -> u16 {
99    debug_assert!(dimension <= 3);
100
101    if dimension == 0 {
102        // directions[0] is the reversal permutation; the tables would give
103        // the same result.
104        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/// SZ sequence value from a natural-order index, for a given dimension (0..4).
112///
113/// Port of `oqmc::szToReversed`: as [`sz_reversed_basis`], but taking the
114/// index in its natural bit order, so
115/// `sz_to_reversed(i, d) == sz_reversed_basis(reverse_bits16(i), d)`. This is
116/// upstream's host-path shift-mask-xor program (Ahmed 2024, eq. 18), kept
117/// verbatim; it also satisfies the SZ pair relation
118/// `sz_to_reversed(sz_to_reversed(i, 2), 1) == sz_to_reversed(i, 3)`
119/// (Ahmed et al. 2025, eq. 13).
120#[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/// Permute an integer (Laine & Karras) and reverse the bits. Equivalent to an
160/// Owen scramble when the input bits are already reversed.
161#[inline]
162pub const fn scramble_and_reverse(value: u32, seed: u32) -> u32 {
163    reverse_bits32(laine_karras_permutation(value, seed))
164}
165
166/// Compute a randomised (Owen-scrambled, progressively shuffled) SZ sequence
167/// value. The name is kept from upstream (`oqmc::shuffledScrambledSobol`).
168///
169/// `DEPTH` is the dimensional output count (1..=4). The seed must be constant for
170/// a given sequence; an index greater than 2^16 will repeat values.
171#[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        // Upstream's host path computes sz_to_reversed(reverse_bits16(r), i),
186        // which is sz_reversed_basis(r, i): the tables consume r directly.
187        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    /// The byte tables are the 16-step loop, precomputed: every index, every
200    /// dimension, bit for bit.
201    #[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    /// Upstream's `szReversedBasis` left-shift program (the GPU path), kept
218    /// verbatim as the reference the byte tables are checked against.
219    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    // Mirrors src/tests/owen.cpp:SzReversedBasis.
255    #[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    // Mirrors src/tests/owen.cpp:SzToReversed.
269    #[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    // Mirrors src/tests/owen.cpp:SzPairRelation (Ahmed et al. 2025, eq. 13),
283    // which upstream's host path relies on to chain dimension 3 from 2.
284    #[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    /// Upstream's host-path draw: reverse once, `sz_to_reversed` per
296    /// dimension, dimension 3 chained from dimension 2.
297    #[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        // Dimension 0 (as in Sobol) is the radical inverse (bit reversal).
322        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        // Index 0 maps to the sequence origin for any seed.
330        let s = shuffled_scrambled_sobol::<4>(0, pcg::hash(0));
331        // reverse_and_shuffle(0, seed) = LK(reverse(0)=0, seed); index>>16 feeds
332        // sz_reversed_basis. The (0,2) net still contains the origin point.
333        // We only assert values are within the u32 range and deterministic here.
334        let s2 = shuffled_scrambled_sobol::<4>(0, pcg::hash(0));
335        assert_eq!(s, s2);
336    }
337
338    // Mirrors src/tests/owen.cpp:02Sequence — the first pair is a (0,2)-net:
339    // for every axis-aligned power-of-two stratification of n=2^m points, each
340    // stratum holds exactly one point.
341    #[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        // Column k has its leading one at bit 15 - k in every dimension, so
371        // each generator matrix is invertible over GF(2).
372        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        // SZ keeps Sobol dimension 1: the primitive polynomial x + 1, whose
389        // generator matrix is Pascal's triangle mod 2: column k has bits set
390        // where binomial(j, k) is odd, i.e. (j & k) == k.
391        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        // Reconstruct one sample from the pieces.
449        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}