shuyi_core/
rng.rs

1//! Seeded random numbers for a deterministic simulation.
2//!
3//! [`SimRng`] is a PCG32 (XSH RR, 64-bit state) written in this crate, so its
4//! output is fixed by this file alone: same seed ⇒ same numbers on every
5//! platform and every dependency version. It is serialisable so a game's
6//! state (and its RNG position) can be saved, rewound and replayed.
7//!
8//! Game rules take a [`RandomSource`], so tests can inject a [`ScriptedRng`]
9//! that returns a given list of rolls.
10
11use alloc::vec::Vec;
12
13use serde::{Deserialize, Serialize};
14
15/// Where game rules get their random numbers from.
16pub trait RandomSource {
17    /// A uniform, unbiased integer in `0..=99`.
18    fn roll_percent(&mut self) -> u8;
19
20    /// A uniform, unbiased integer in `0..n`. `n` must be at least 1; `0`
21    /// gives `0`.
22    fn roll_below(&mut self, n: u32) -> u32;
23}
24
25/// The PCG32 multiplier (O'Neill, "PCG: A Family of Simple Fast
26/// Space-Efficient Statistically Good Algorithms for Random Number
27/// Generation", 2014).
28const PCG_MULTIPLIER: u64 = 6_364_136_223_846_793_005;
29
30/// The stream every [`SimRng::new`] uses. Any odd increment works; one fixed
31/// stream keeps a seed a complete description of the sequence.
32const DEFAULT_STREAM: u64 = 54;
33
34/// The largest multiple of 100 that fits in `2^32`: a `u32` below this,
35/// taken mod 100, is uniform in `0..=99`.
36const PERCENT_LIMIT: u32 = (u32::MAX / 100) * 100;
37
38/// The most redraws one [`SimRng::roll_percent`] makes.
39const MAX_REDRAWS: u32 = 16;
40
41/// The seeded simulation RNG, kept in the game's state.
42#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
43#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
44pub struct SimRng {
45    state: u64,
46    inc: u64,
47}
48
49impl SimRng {
50    /// A generator seeded with `seed`.
51    pub fn new(seed: u64) -> Self {
52        Self::with_stream(seed, DEFAULT_STREAM)
53    }
54
55    /// PCG32's reference seeding (`pcg32_srandom_r`) with stream `stream`.
56    fn with_stream(seed: u64, stream: u64) -> Self {
57        let mut rng = Self {
58            state: 0,
59            inc: (stream << 1) + 1,
60        };
61        rng.next_u32();
62        rng.state = rng.state.wrapping_add(seed);
63        rng.next_u32();
64        rng
65    }
66
67    /// The next 32 random bits.
68    pub fn next_u32(&mut self) -> u32 {
69        let old = self.state;
70        self.state = old.wrapping_mul(PCG_MULTIPLIER).wrapping_add(self.inc);
71        // XSH RR output: the top 32 of the xorshifted 64 bits, rotated by the
72        // top 5 bits of the old state. Both truncations are the algorithm.
73        #[allow(clippy::cast_possible_truncation)]
74        let xorshifted = (((old >> 18) ^ old) >> 27) as u32;
75        #[allow(clippy::cast_possible_truncation)]
76        let rot = (old >> 59) as u32;
77        xorshifted.rotate_right(rot)
78    }
79
80    /// A uniform integer in `0..=99`. Rejection sampling: draws that would
81    /// make low values more likely (the top `2^32 mod 100` values) are
82    /// thrown away and redrawn, at most 16 times. Each draw is
83    /// rejected with chance `96 / 2^32`, so the cap is never reached in
84    /// practice; it only guarantees the loop ends.
85    pub fn roll_percent(&mut self) -> u8 {
86        let mut x = self.next_u32();
87        for _ in 0..MAX_REDRAWS {
88            if accepted(x) {
89                break;
90            }
91            x = self.next_u32();
92        }
93        u8::try_from(x % 100).unwrap_or(u8::MAX)
94    }
95
96    /// A uniform integer in `0..n` (`0` when `n` is 0). Rejection sampling
97    /// as in [`Self::roll_percent`]: draws at or above the largest multiple
98    /// of `n` that fits in `2^32` are redrawn, at most 16 times.
99    pub fn roll_below(&mut self, n: u32) -> u32 {
100        if n == 0 {
101            return 0;
102        }
103        let mut x = self.next_u32();
104        for _ in 0..MAX_REDRAWS {
105            if accepted_below(x, n) {
106                break;
107            }
108            x = self.next_u32();
109        }
110        x % n
111    }
112}
113
114/// The largest multiple of `n` (≥ 1) that is at most `u32::MAX`: a `u32`
115/// below it, taken mod `n`, is uniform.
116fn below_limit(n: u32) -> u32 {
117    (u32::MAX / n) * n
118}
119
120/// Whether `x mod n` is unbiased: `x` is below [`below_limit`]`(n)`.
121fn accepted_below(x: u32, n: u32) -> bool {
122    x < below_limit(n)
123}
124
125/// Whether `x mod 100` is unbiased: `x` is below [`PERCENT_LIMIT`].
126fn accepted(x: u32) -> bool {
127    x < PERCENT_LIMIT
128}
129
130impl RandomSource for SimRng {
131    fn roll_percent(&mut self) -> u8 {
132        SimRng::roll_percent(self)
133    }
134
135    fn roll_below(&mut self, n: u32) -> u32 {
136        SimRng::roll_below(self, n)
137    }
138}
139
140/// A [`RandomSource`] that returns a fixed list of rolls, in order. For
141/// tests that need an exact trace of rolls. Percent rolls and
142/// [`roll_below`](RandomSource::roll_below) draws come from two separate
143/// lists.
144#[derive(Debug, Clone, PartialEq, Eq, Default)]
145pub struct ScriptedRng {
146    rolls: Vec<u8>,
147    next: usize,
148    below: Vec<u32>,
149    next_below: usize,
150}
151
152impl ScriptedRng {
153    /// Returns `rolls` one by one. Each must be in `0..=99`.
154    pub fn new(rolls: impl Into<Vec<u8>>) -> Self {
155        Self {
156            rolls: rolls.into(),
157            ..Self::default()
158        }
159    }
160
161    /// Also returns `draws`, one by one, from
162    /// [`roll_below`](RandomSource::roll_below).
163    #[must_use]
164    pub fn with_below(mut self, draws: impl Into<Vec<u32>>) -> Self {
165        self.below = draws.into();
166        self
167    }
168
169    /// How many percent rolls have been taken so far.
170    pub fn consumed(&self) -> usize {
171        self.next
172    }
173
174    /// How many `roll_below` draws have been taken so far.
175    pub fn consumed_below(&self) -> usize {
176        self.next_below
177    }
178}
179
180impl RandomSource for ScriptedRng {
181    /// # Panics
182    ///
183    /// When the script is used up: the test expected fewer rolls.
184    fn roll_percent(&mut self) -> u8 {
185        let Some(&roll) = self.rolls.get(self.next) else {
186            panic!("ScriptedRng ran out after {} rolls", self.next);
187        };
188        self.next += 1;
189        roll
190    }
191
192    /// # Panics
193    ///
194    /// When the draws are used up, or the next one isn't below `n`: the
195    /// test expected other draws.
196    fn roll_below(&mut self, n: u32) -> u32 {
197        let Some(&draw) = self.below.get(self.next_below) else {
198            panic!("ScriptedRng ran out after {} draws", self.next_below);
199        };
200        assert!(draw < n.max(1), "scripted draw {draw} is not below {n}");
201        self.next_below += 1;
202        draw
203    }
204}
205
206#[cfg(test)]
207mod tests {
208    use super::*;
209
210    #[test]
211    fn percent_limit_is_the_largest_multiple_of_100_in_u32() {
212        assert_eq!(PERCENT_LIMIT % 100, 0);
213        assert_eq!(u64::from(PERCENT_LIMIT) + 100, (1u64 << 32) + 4);
214        assert_eq!(PERCENT_LIMIT, 4_294_967_200);
215    }
216
217    #[test]
218    fn biased_draws_are_rejected() {
219        assert!(accepted(0));
220        assert!(accepted(PERCENT_LIMIT - 1));
221        assert!(!accepted(PERCENT_LIMIT));
222        assert!(!accepted(u32::MAX));
223    }
224
225    #[test]
226    fn matches_pcg32_reference_output() {
227        // First outputs of the PCG reference `pcg32-demo` (seed 42, stream 54).
228        let mut rng = SimRng::with_stream(42, 54);
229        let got: Vec<u32> = (0..6).map(|_| rng.next_u32()).collect();
230        assert_eq!(
231            got,
232            [
233                0xa15c_02b7,
234                0x7b47_f409,
235                0xba1d_3330,
236                0x83d2_f293,
237                0xbfa4_784b,
238                0xcbed_606e
239            ]
240        );
241    }
242
243    #[test]
244    fn fixed_seed_gives_fixed_rolls() {
245        let mut rng = SimRng::new(2026);
246        let got: Vec<u8> = (0..10).map(|_| rng.roll_percent()).collect();
247        assert_eq!(got, [74, 36, 25, 49, 16, 67, 87, 89, 28, 12]);
248    }
249
250    #[test]
251    fn different_seeds_differ() {
252        let a: Vec<u32> = {
253            let mut r = SimRng::new(1);
254            (0..4).map(|_| r.next_u32()).collect()
255        };
256        let b: Vec<u32> = {
257            let mut r = SimRng::new(2);
258            (0..4).map(|_| r.next_u32()).collect()
259        };
260        assert_ne!(a, b);
261    }
262
263    #[test]
264    fn serialised_rng_resumes_the_same_sequence() {
265        let mut rng = SimRng::new(7);
266        for _ in 0..5 {
267            rng.next_u32();
268        }
269        let text = ron::to_string(&rng).expect("serialise");
270        let mut copy: SimRng = ron::from_str(&text).expect("deserialise");
271        assert_eq!(copy, rng);
272        let a: Vec<u8> = (0..20).map(|_| rng.roll_percent()).collect();
273        let b: Vec<u8> = (0..20).map(|_| copy.roll_percent()).collect();
274        assert_eq!(a, b);
275    }
276
277    #[test]
278    fn roll_percent_is_roughly_uniform() {
279        // Chi-square over 100 buckets (99 degrees of freedom: mean 99,
280        // sd ≈ 14). Seeded, so the value is fixed; the bound is ~4 sd.
281        let mut rng = SimRng::new(12_345);
282        let n = 100_000;
283        let mut counts = [0u32; 100];
284        for _ in 0..n {
285            counts[usize::from(rng.roll_percent())] += 1;
286        }
287        let expected = f64::from(n) / 100.0;
288        let chi2: f64 = counts
289            .iter()
290            .map(|&c| (f64::from(c) - expected).powi(2) / expected)
291            .sum();
292        assert!(chi2 < 155.0, "chi-square {chi2}");
293    }
294
295    #[test]
296    fn roll_percent_trait_matches_inherent() {
297        let mut a = SimRng::new(9);
298        let mut b = SimRng::new(9);
299        for _ in 0..50 {
300            assert_eq!(RandomSource::roll_percent(&mut a), b.roll_percent());
301        }
302    }
303
304    #[test]
305    fn scripted_rng_replays_its_script() {
306        let mut rng = ScriptedRng::new([3, 99, 0]);
307        assert_eq!(rng.consumed(), 0);
308        assert_eq!(rng.roll_percent(), 3);
309        assert_eq!(rng.roll_percent(), 99);
310        assert_eq!(rng.consumed(), 2);
311        assert_eq!(rng.roll_percent(), 0);
312        assert_eq!(rng.consumed(), 3);
313    }
314
315    #[test]
316    fn below_limit_is_a_multiple_of_n() {
317        assert_eq!(below_limit(1), u32::MAX);
318        assert_eq!(below_limit(100), PERCENT_LIMIT);
319        assert_eq!(below_limit(3), u32::MAX);
320        assert_eq!(below_limit(280), 4_294_967_040);
321        assert_eq!(below_limit(u32::MAX), u32::MAX);
322    }
323
324    #[test]
325    fn biased_below_draws_are_rejected() {
326        // 280 × 15_339_168 = 4_294_967_040: draws from there on are redrawn.
327        assert!(accepted_below(0, 280));
328        assert!(accepted_below(4_294_967_039, 280));
329        assert!(!accepted_below(4_294_967_040, 280));
330        assert!(!accepted_below(u32::MAX, 280));
331    }
332
333    #[test]
334    fn roll_below_stays_in_range_and_is_fixed_by_the_seed() {
335        let mut rng = SimRng::new(2026);
336        let got: Vec<u32> = (0..10).map(|_| rng.roll_below(280)).collect();
337        assert!(got.iter().all(|&r| r < 280));
338        let mut again = SimRng::new(2026);
339        let same: Vec<u32> = (0..10)
340            .map(|_| RandomSource::roll_below(&mut again, 280))
341            .collect();
342        assert_eq!(got, same);
343        assert_eq!(rng.roll_below(0), 0);
344        assert_eq!(rng.roll_below(1), 0);
345    }
346
347    #[test]
348    fn roll_below_is_roughly_uniform() {
349        // Chi-square over 7 buckets (6 degrees of freedom: mean 6, sd ≈ 3.5).
350        let mut rng = SimRng::new(99);
351        let n = 70_000;
352        let mut counts = [0u32; 7];
353        for _ in 0..n {
354            counts[rng.roll_below(7) as usize] += 1;
355        }
356        let expected = f64::from(n) / 7.0;
357        let chi2: f64 = counts
358            .iter()
359            .map(|&c| (f64::from(c) - expected).powi(2) / expected)
360            .sum();
361        assert!(chi2 < 25.0, "chi-square {chi2}");
362    }
363
364    #[test]
365    fn scripted_rng_replays_its_draws() {
366        let mut rng = ScriptedRng::new([4]).with_below([7, 0]);
367        assert_eq!(rng.roll_below(10), 7);
368        assert_eq!(rng.roll_percent(), 4);
369        assert_eq!(rng.roll_below(1), 0);
370        assert_eq!((rng.consumed(), rng.consumed_below()), (1, 2));
371    }
372
373    #[test]
374    #[should_panic(expected = "not below 5")]
375    fn scripted_rng_checks_draws_are_in_range() {
376        ScriptedRng::new([]).with_below([5]).roll_below(5);
377    }
378
379    #[test]
380    #[should_panic(expected = "ran out after 0 draws")]
381    fn scripted_rng_panics_when_draws_run_out() {
382        ScriptedRng::new([]).roll_below(5);
383    }
384
385    #[test]
386    #[should_panic(expected = "ran out after 1 rolls")]
387    fn scripted_rng_panics_when_exhausted() {
388        let mut rng = ScriptedRng::new([5]);
389        rng.roll_percent();
390        rng.roll_percent();
391    }
392}
shuyi_core/rng.rs

shuyi_core/
rng.rs
