vrd/
pcg.rs

1// Copyright © 2023-2026 vrd. All rights reserved.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! PCG (Permuted Congruential Generator) family - O'Neill, 2014.
5//!
6//! Two variants exported:
7//!
8//! - [`Pcg32`](crate::pcg::Pcg32) - PCG-XSH-RR-64/32. 16-byte
9//!   state, 32-bit output. The smallest-state member of the family;
10//!   faster per `u32` than Xoshiro256++ on most CPUs.
11//! - [`Pcg64`](crate::pcg::Pcg64) - PCG-XSL-RR-128/64. 32-byte
12//!   state, 64-bit output. Same state size as Xoshiro256++ with
13//!   native 64-bit output.
14//!
15//! Both are statistically excellent (pass TestU01 BigCrush) but are
16//! **not** CSPRNGs - same caveat as Xoshiro and MT.
17//!
18//! Reference: O'Neill, M. E. (2014), *PCG: A Family of Simple Fast
19//! Space-Efficient Statistically Good Algorithms for Random Number
20//! Generation*. <https://www.pcg-random.org/>.
21
22use core::convert::Infallible;
23use rand::rand_core::{SeedableRng, TryRng};
24
25// ---------------------------------------------------------------------------
26// PCG-XSH-RR-64/32
27// ---------------------------------------------------------------------------
28
29/// PCG-XSH-RR-64/32 generator. 16-byte state (one `u64` LCG state plus
30/// a 64-bit stream-selecting increment); 32-bit output per call via
31/// XOR-shift-high followed by random rotation.
32///
33/// # Examples
34///
35/// ```
36/// use vrd::pcg::Pcg32;
37///
38/// let mut rng = Pcg32::from_u64_seed(0xCAFE_F00D);
39/// let _ = rng.next_u32();
40/// ```
41#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
42#[cfg_attr(
43    feature = "serde",
44    derive(serde::Serialize, serde::Deserialize)
45)]
46pub struct Pcg32 {
47    /// 64-bit LCG state - updated as `state = state * MULT + inc`
48    /// on every call.
49    state: u64,
50    /// Stream-selecting odd increment. Allows independent
51    /// substreams sharing the same multiplier.
52    inc: u64,
53}
54
55/// LCG multiplier - from the reference PCG implementation
56/// (O'Neill 2014). 64-bit prime with full period.
57const PCG32_MULT: u64 = 6_364_136_223_846_793_005;
58/// Default increment when a stream selector isn't given. Any odd
59/// number works; this one matches O'Neill's reference C.
60const PCG32_DEFAULT_INC: u64 = 1_442_695_040_888_963_407;
61
62impl Pcg32 {
63    /// Builds a `Pcg32` from a 64-bit seed and a 63-bit stream
64    /// selector. Internally bumps the increment to the
65    /// nearest odd value to ensure a full-period LCG.
66    pub fn from_seed_stream(seed: u64, stream: u64) -> Self {
67        let mut rng = Self {
68            state: 0,
69            inc: (stream << 1) | 1,
70        };
71        let _ = rng.next_u32();
72        rng.state = rng.state.wrapping_add(seed);
73        let _ = rng.next_u32();
74        rng
75    }
76
77    /// Convenience constructor from a single `u64` seed; uses the
78    /// canonical PCG default stream.
79    ///
80    /// # Examples
81    ///
82    /// ```
83    /// use vrd::pcg::Pcg32;
84    ///
85    /// let mut rng = Pcg32::from_u64_seed(42);
86    /// assert_ne!(rng.next_u32(), 0);
87    /// ```
88    pub fn from_u64_seed(seed: u64) -> Self {
89        Self::from_seed_stream(seed, PCG32_DEFAULT_INC)
90    }
91
92    /// Generates the next random `u32`.
93    ///
94    /// # Examples
95    ///
96    /// ```
97    /// use vrd::pcg::Pcg32;
98    ///
99    /// let mut rng = Pcg32::from_u64_seed(1);
100    /// let n = rng.next_u32();
101    /// # let _ = n;
102    /// ```
103    #[inline]
104    pub fn next_u32(&mut self) -> u32 {
105        let old = self.state;
106        self.state =
107            old.wrapping_mul(PCG32_MULT).wrapping_add(self.inc);
108        // XSH-RR - XOR-shift-high then random-rotate.
109        let xorshifted = (((old >> 18) ^ old) >> 27) as u32;
110        let rot = (old >> 59) as u32;
111        xorshifted.rotate_right(rot)
112    }
113
114    /// Generates the next random `u64` by concatenating two `u32`s.
115    #[inline]
116    pub fn next_u64(&mut self) -> u64 {
117        let lo = u64::from(self.next_u32());
118        let hi = u64::from(self.next_u32());
119        (hi << 32) | lo
120    }
121
122    /// Fills `dest` with random bytes.
123    pub fn fill_bytes(&mut self, dest: &mut [u8]) {
124        let mut i = 0;
125        while i + 4 <= dest.len() {
126            let bytes = self.next_u32().to_le_bytes();
127            dest[i..i + 4].copy_from_slice(&bytes);
128            i += 4;
129        }
130        if i < dest.len() {
131            let bytes = self.next_u32().to_le_bytes();
132            let remaining = dest.len() - i;
133            dest[i..].copy_from_slice(&bytes[..remaining]);
134        }
135    }
136}
137
138impl TryRng for Pcg32 {
139    type Error = Infallible;
140
141    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
142        Ok(self.next_u32())
143    }
144
145    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
146        Ok(self.next_u64())
147    }
148
149    fn try_fill_bytes(
150        &mut self,
151        dest: &mut [u8],
152    ) -> Result<(), Self::Error> {
153        self.fill_bytes(dest);
154        Ok(())
155    }
156}
157
158impl SeedableRng for Pcg32 {
159    type Seed = [u8; 16];
160
161    fn from_seed(seed: [u8; 16]) -> Self {
162        let state = u64::from_le_bytes([
163            seed[0], seed[1], seed[2], seed[3], seed[4], seed[5],
164            seed[6], seed[7],
165        ]);
166        let stream = u64::from_le_bytes([
167            seed[8], seed[9], seed[10], seed[11], seed[12], seed[13],
168            seed[14], seed[15],
169        ]);
170        Self::from_seed_stream(state, stream | 1)
171    }
172}
173
174// ---------------------------------------------------------------------------
175// PCG-XSL-RR-128/64
176// ---------------------------------------------------------------------------
177
178/// PCG-XSL-RR-128/64 generator. 32-byte state (one `u128` LCG state
179/// plus a 128-bit increment); 64-bit output per call via
180/// XOR-shift-low followed by random rotation.
181///
182/// # Examples
183///
184/// ```
185/// use vrd::pcg::Pcg64;
186///
187/// let mut rng = Pcg64::from_u128_seed(0xCAFE_F00D);
188/// let _ = rng.next_u64();
189/// ```
190#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
191#[cfg_attr(
192    feature = "serde",
193    derive(serde::Serialize, serde::Deserialize)
194)]
195pub struct Pcg64 {
196    /// 128-bit LCG state - updated as `state = state * MULT + inc`
197    /// on every call.
198    state: u128,
199    /// Stream-selecting odd increment.
200    inc: u128,
201}
202
203/// 128-bit LCG multiplier from O'Neill's reference C++
204/// implementation (PCG-XSL-RR-128-64, `default_multiplier`).
205const PCG64_MULT: u128 = 0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645;
206/// Default 128-bit increment when no stream selector is given.
207const PCG64_DEFAULT_INC: u128 =
208    0x5851_F42D_4C95_7F2D_1405_7B7E_F767_814F;
209
210impl Pcg64 {
211    /// Builds a `Pcg64` from a 128-bit seed and a 127-bit stream
212    /// selector. The increment is bumped to the nearest odd value
213    /// to ensure a full-period LCG.
214    pub fn from_seed_stream(seed: u128, stream: u128) -> Self {
215        let mut rng = Self {
216            state: 0,
217            inc: (stream << 1) | 1,
218        };
219        let _ = rng.next_u64();
220        rng.state = rng.state.wrapping_add(seed);
221        let _ = rng.next_u64();
222        rng
223    }
224
225    /// Convenience constructor from a single `u128` seed using the
226    /// canonical PCG default stream.
227    ///
228    /// # Examples
229    ///
230    /// ```
231    /// use vrd::pcg::Pcg64;
232    ///
233    /// let mut rng = Pcg64::from_u128_seed(42);
234    /// assert_ne!(rng.next_u64(), 0);
235    /// ```
236    pub fn from_u128_seed(seed: u128) -> Self {
237        Self::from_seed_stream(seed, PCG64_DEFAULT_INC)
238    }
239
240    /// Generates the next random `u64`.
241    ///
242    /// # Examples
243    ///
244    /// ```
245    /// use vrd::pcg::Pcg64;
246    ///
247    /// let mut rng = Pcg64::from_u128_seed(1);
248    /// let n = rng.next_u64();
249    /// # let _ = n;
250    /// ```
251    #[inline]
252    pub fn next_u64(&mut self) -> u64 {
253        let old = self.state;
254        self.state =
255            old.wrapping_mul(PCG64_MULT).wrapping_add(self.inc);
256        // XSL-RR - XOR-shift-low then random-rotate (6-bit rot).
257        let half = ((old >> 64) as u64) ^ (old as u64);
258        let rot = (old >> 122) as u32;
259        half.rotate_right(rot)
260    }
261
262    /// Generates the next random `u32` by taking the high 32 bits.
263    #[inline]
264    pub fn next_u32(&mut self) -> u32 {
265        (self.next_u64() >> 32) as u32
266    }
267
268    /// Fills `dest` with random bytes.
269    pub fn fill_bytes(&mut self, dest: &mut [u8]) {
270        let mut i = 0;
271        while i + 8 <= dest.len() {
272            let bytes = self.next_u64().to_le_bytes();
273            dest[i..i + 8].copy_from_slice(&bytes);
274            i += 8;
275        }
276        if i < dest.len() {
277            let bytes = self.next_u64().to_le_bytes();
278            let remaining = dest.len() - i;
279            dest[i..].copy_from_slice(&bytes[..remaining]);
280        }
281    }
282}
283
284impl TryRng for Pcg64 {
285    type Error = Infallible;
286
287    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
288        Ok(self.next_u32())
289    }
290
291    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
292        Ok(self.next_u64())
293    }
294
295    fn try_fill_bytes(
296        &mut self,
297        dest: &mut [u8],
298    ) -> Result<(), Self::Error> {
299        self.fill_bytes(dest);
300        Ok(())
301    }
302}
303
304impl SeedableRng for Pcg64 {
305    type Seed = [u8; 32];
306
307    fn from_seed(seed: [u8; 32]) -> Self {
308        let state = u128::from_le_bytes([
309            seed[0], seed[1], seed[2], seed[3], seed[4], seed[5],
310            seed[6], seed[7], seed[8], seed[9], seed[10], seed[11],
311            seed[12], seed[13], seed[14], seed[15],
312        ]);
313        let stream = u128::from_le_bytes([
314            seed[16], seed[17], seed[18], seed[19], seed[20], seed[21],
315            seed[22], seed[23], seed[24], seed[25], seed[26], seed[27],
316            seed[28], seed[29], seed[30], seed[31],
317        ]);
318        Self::from_seed_stream(state, stream | 1)
319    }
320}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325
326    #[test]
327    fn pcg32_deterministic() {
328        let mut a = Pcg32::from_u64_seed(42);
329        let mut b = Pcg32::from_u64_seed(42);
330        for _ in 0..16 {
331            assert_eq!(a.next_u32(), b.next_u32());
332        }
333    }
334
335    #[test]
336    fn pcg32_nonzero_from_zero_seed() {
337        let mut rng = Pcg32::from_u64_seed(0);
338        assert_ne!(rng.next_u32(), 0);
339    }
340
341    #[test]
342    fn pcg32_fill_bytes_unaligned() {
343        let mut rng = Pcg32::from_u64_seed(7);
344        let mut buf = [0u8; 17];
345        rng.fill_bytes(&mut buf);
346        assert!(buf.iter().any(|&b| b != 0));
347    }
348
349    #[test]
350    fn pcg64_deterministic() {
351        let mut a = Pcg64::from_u128_seed(0xDEAD_BEEF);
352        let mut b = Pcg64::from_u128_seed(0xDEAD_BEEF);
353        for _ in 0..16 {
354            assert_eq!(a.next_u64(), b.next_u64());
355        }
356    }
357
358    #[test]
359    fn pcg64_nonzero_from_zero_seed() {
360        let mut rng = Pcg64::from_u128_seed(0);
361        assert_ne!(rng.next_u64(), 0);
362    }
363
364    #[test]
365    fn pcg64_fill_bytes_unaligned() {
366        let mut rng = Pcg64::from_u128_seed(1);
367        let mut buf = [0u8; 33];
368        rng.fill_bytes(&mut buf);
369        assert!(buf.iter().any(|&b| b != 0));
370    }
371
372    #[test]
373    fn pcg32_try_rng_impl() {
374        let mut rng = Pcg32::from_u64_seed(1);
375        assert!(rng.try_next_u32().is_ok());
376        assert!(rng.try_next_u64().is_ok());
377        let mut buf = [0u8; 8];
378        assert!(rng.try_fill_bytes(&mut buf).is_ok());
379    }
380
381    #[test]
382    fn pcg64_try_rng_impl() {
383        let mut rng = Pcg64::from_u128_seed(1);
384        assert!(rng.try_next_u32().is_ok());
385        assert!(rng.try_next_u64().is_ok());
386        let mut buf = [0u8; 8];
387        assert!(rng.try_fill_bytes(&mut buf).is_ok());
388    }
389
390    #[test]
391    fn pcg32_seedable_rng() {
392        let seed = [3u8; 16];
393        let mut a = <Pcg32 as SeedableRng>::from_seed(seed);
394        let mut b = <Pcg32 as SeedableRng>::from_seed(seed);
395        assert_eq!(a.next_u32(), b.next_u32());
396    }
397
398    #[test]
399    fn pcg64_seedable_rng() {
400        let seed = [3u8; 32];
401        let mut a = <Pcg64 as SeedableRng>::from_seed(seed);
402        let mut b = <Pcg64 as SeedableRng>::from_seed(seed);
403        assert_eq!(a.next_u64(), b.next_u64());
404    }
405}
vrd/pcg.rs

vrd/
pcg.rs
