mock_upcloud/
rng.rs

1//! **The one generator, so a seed names a run forever.**
2//!
3//! SplitMix64 (Steele/Lea/Flood, 2014), thirty lines, in this crate rather than
4//! behind a dependency. A seeded harness is only replayable if the STREAM is
5//! stable, and a PRNG crate is free to change its stream in a minor release —
6//! `rand` has done it twice. When the stream lives here, a seed printed by a
7//! failing run in September still reproduces it in March.
8
9/// A deterministic 64-bit stream. Cheap enough to make one per request.
10#[derive(Clone, Debug)]
11pub struct SplitMix64 {
12    state: u64,
13}
14
15impl SplitMix64 {
16    pub fn new(seed: u64) -> SplitMix64 {
17        SplitMix64 { state: seed }
18    }
19
20    /// Derive an independent stream from this one and a label, so two features
21    /// seeded from the same run never correlate. (`hash` is FNV-1a, also here,
22    /// also for stream stability.)
23    pub fn derive(seed: u64, label: &str) -> SplitMix64 {
24        SplitMix64::new(seed ^ fnv1a(label))
25    }
26
27    pub fn next_u64(&mut self) -> u64 {
28        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
29        let mut z = self.state;
30        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
31        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
32        z ^ (z >> 31)
33    }
34
35    /// Uniform in `[0, n)`. Rejection-sampled, not modulo: a modulo fold skews
36    /// the low values, and a fault that fires 0.4 % too often is a fault whose
37    /// measured rate is a lie.
38    pub fn below(&mut self, n: u64) -> u64 {
39        assert!(n > 0, "below(0)");
40        let zone = u64::MAX - (u64::MAX % n) - 1;
41        loop {
42            let v = self.next_u64();
43            if v <= zone {
44                return v % n;
45            }
46        }
47    }
48
49    /// `true` with probability `num / den`.
50    pub fn chance(&mut self, num: u64, den: u64) -> bool {
51        self.below(den) < num
52    }
53
54    /// Uniform in `[lo, hi]` inclusive.
55    pub fn range(&mut self, lo: u64, hi: u64) -> u64 {
56        assert!(hi >= lo);
57        lo + self.below(hi - lo + 1)
58    }
59
60    /// Fisher–Yates, so a shuffled address pool is a permutation and never
61    /// hands the same address to two servers.
62    pub fn shuffle<T>(&mut self, v: &mut [T]) {
63        if v.len() < 2 {
64            return;
65        }
66        for i in (1..v.len()).rev() {
67            let j = self.below(i as u64 + 1) as usize;
68            v.swap(i, j);
69        }
70    }
71}
72
73pub fn fnv1a(s: &str) -> u64 {
74    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
75    for b in s.as_bytes() {
76        h ^= *b as u64;
77        h = h.wrapping_mul(0x1000_0000_01b3);
78    }
79    h
80}
81
82#[cfg(test)]
83mod tests {
84    use super::*;
85
86    /// The stream is the contract. If this test ever has to be updated, every
87    /// seed ever printed by a failing run has stopped meaning anything.
88    #[test]
89    fn the_stream_is_pinned() {
90        let mut r = SplitMix64::new(0);
91        assert_eq!(r.next_u64(), 16294208416658607535);
92        assert_eq!(r.next_u64(), 7960286522194355700);
93        assert_eq!(r.next_u64(), 487617019471545679);
94    }
95
96    #[test]
97    fn below_is_uniform_enough_to_measure_a_rate() {
98        let mut r = SplitMix64::new(7);
99        let mut hits = 0;
100        for _ in 0..100_000 {
101            if r.chance(1, 100) {
102                hits += 1;
103            }
104        }
105        // 1 % of 100 000 is 1 000; three sigma is ~94.
106        assert!((900..=1100).contains(&hits), "{hits}");
107    }
108
109    #[test]
110    fn shuffle_is_a_permutation() {
111        let mut r = SplitMix64::new(3);
112        let mut v: Vec<u32> = (0..64).collect();
113        r.shuffle(&mut v);
114        let mut back = v.clone();
115        back.sort_unstable();
116        assert_eq!(back, (0..64).collect::<Vec<_>>());
117        assert_ne!(v, back, "a shuffle that is the identity is not a shuffle");
118    }
119
120    #[test]
121    fn derive_decorrelates() {
122        let mut a = SplitMix64::derive(99, "out_of_stock");
123        let a = a.next_u64();
124        let mut b = SplitMix64::derive(99, "price_reset");
125        let b = b.next_u64();
126        assert_ne!(a, b);
127    }
128}
mock_upcloud/rng.rs

mock_upcloud/
rng.rs
