Skip to main content

openqmc/
pcg.rs

1//! Port of `oqmc/pcg.h` — the PCG-RXS-M-XS-32 PRNG by Melissa O'Neill, used
2//! both as a classic sequential PRNG and (via [`hash`]) as a stateless parallel
3//! hash function per Jarzynski & Olano, "Hash Functions for GPU Rendering".
4//! Constants are taken from <https://github.com/imneme/pcg-c>.
5
6use crate::float::uint_to_float;
7
8/// LCG state-transition: advance the PRNG index along the sequence.
9#[inline]
10pub const fn state_transition(state: u32) -> u32 {
11    state.wrapping_mul(747796405).wrapping_add(2891336453)
12}
13
14/// Output permutation of the state (the RXS-M-XS steps), giving a usable value.
15#[inline]
16pub const fn output(mut state: u32) -> u32 {
17    // RXS
18    state ^= state >> (4 + (state >> 28));
19    // M
20    state = state.wrapping_mul(277803737);
21    // XS
22    state ^= state >> 22;
23    state
24}
25
26/// Default-initialise the PRNG state (zero seed).
27#[inline]
28pub const fn init() -> u32 {
29    state_transition(0)
30}
31
32/// Initialise the PRNG state from a seed.
33#[inline]
34pub const fn init_seed(seed: u32) -> u32 {
35    init().wrapping_add(seed)
36}
37
38/// Stateless hash of an input key.
39#[inline]
40pub const fn hash(key: u32) -> u32 {
41    output(state_transition(key))
42}
43
44/// Advance `state` and return the next value in the sequence.
45#[inline]
46pub fn rng(state: &mut u32) -> u32 {
47    *state = state_transition(*state);
48    output(*state)
49}
50
51/// A sequential PCG PRNG stream.
52///
53/// This is not part of the upstream C++ headers as a standalone type, but it is
54/// exactly the mechanism `State64Bit::drawRnd` uses internally (run `pcg::rng`
55/// on a running state). It is the natural source for *unbounded* or *incidental*
56/// random streams — Russian roulette, volume delta-tracking — where stratified
57/// QMC dimensions do not apply, and a convenient uniform RNG for testing.
58#[derive(Clone, Copy, Debug)]
59pub struct Rng {
60    state: u32,
61}
62
63impl Rng {
64    /// Seed a stream. The seed is used directly as the running state (matching
65    /// `State64Bit::drawRnd`, which seeds with `patternId + sampleId`).
66    #[inline]
67    pub const fn new(seed: u32) -> Self {
68        Self { state: seed }
69    }
70
71    /// Next raw 32-bit value.
72    #[inline]
73    pub fn next_u32(&mut self) -> u32 {
74        rng(&mut self.state)
75    }
76
77    /// Next value in `[0, 1)`.
78    #[inline]
79    pub fn next_f32(&mut self) -> f32 {
80        uint_to_float(self.next_u32())
81    }
82
83    /// Next two values, each in `[0, 1)`.
84    #[inline]
85    pub fn next_2d(&mut self) -> [f32; 2] {
86        [self.next_f32(), self.next_f32()]
87    }
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    const PRIMES: [u32; 20] = [
95        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
96    ];
97
98    // Mirrors src/tests/pcg.cpp structural invariants.
99    #[test]
100    fn state_transition_changes() {
101        assert_ne!(state_transition(0), 0);
102        for p in PRIMES {
103            assert_ne!(state_transition(p), p);
104        }
105    }
106
107    #[test]
108    fn output_permutation_fixes_zero() {
109        assert_eq!(output(0), 0);
110        for p in PRIMES {
111            assert_ne!(output(p), p);
112        }
113    }
114
115    #[test]
116    fn init_default_equals_zero_seed() {
117        assert_eq!(init(), init_seed(0));
118    }
119
120    #[test]
121    fn hash_equals_rng_on_init() {
122        // hash(state) == rng(state) when state is freshly initialised.
123        for seed in PRIMES {
124            let mut state = init_seed(seed);
125            let h = hash(state);
126            let r = rng(&mut state);
127            assert_eq!(h, r);
128        }
129    }
130
131    #[test]
132    fn rng_stream_is_deterministic() {
133        let mut a = Rng::new(0xC0FF_EE00);
134        let mut b = Rng::new(0xC0FF_EE00);
135        for _ in 0..16 {
136            assert_eq!(a.next_u32(), b.next_u32());
137        }
138    }
139}