rapidhash/
rng.rs

1#[cfg(feature = "rng")]
2use rand_core::{RngCore, SeedableRng, impls};
3use crate::rapid_const::{rapid_mix, RAPID_SECRET};
4use crate::RAPID_SEED;
5
6/// Generate a random number using rapidhash mixing.
7///
8/// This RNG is deterministic and optimised for throughput. It is not a cryptographic random number
9/// generator.
10///
11/// This implementation is equivalent in logic and performance to
12/// [wyhash::wyrng](https://docs.rs/wyhash/latest/wyhash/fn.wyrng.html) and
13/// [fasthash::u64](https://docs.rs/fastrand/latest/fastrand/), but uses rapidhash
14/// constants/secrets.
15///
16/// The weakness with this RNG is that at best it's a single cycle over the u64 space, as the seed
17/// is simple a position in a constant sequence. Future work could involve using a wider state to
18/// ensure we can generate many different sequences.
19#[inline]
20pub fn rapidrng_fast(seed: &mut u64) -> u64 {
21    *seed = seed.wrapping_add(RAPID_SECRET[0]);
22    rapid_mix(*seed, *seed ^ RAPID_SECRET[1])
23}
24
25/// Generate a random number non-deterministically by re-seeding with the current time.
26///
27/// This is not a cryptographic random number generator.
28///
29/// Note fetching system time requires a syscall and is therefore much slower than [rapidrng_fast].
30/// It can also be used to seed [rapidrng_fast].
31///
32/// Requires the `std` feature and a platform that supports [std::time::SystemTime].
33///
34/// # Example
35/// ```rust
36/// use rapidhash::{rapidrng_fast, rapidrng_time};
37///
38/// // choose a non-deterministic random seed (50-100ns)
39/// let mut seed = rapidrng_time(&mut 0);
40///
41/// // rapid fast deterministic random numbers (~1ns/iter)
42/// for _ in 0..10 {
43///     println!("{}", rapidrng_fast(&mut seed));
44/// }
45/// ```
46#[cfg(feature = "std")]
47#[inline]
48pub fn rapidrng_time(seed: &mut u64) -> u64 {
49    let time = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
50    // NOTE limited entropy: only a few of the time.as_secs bits will change between calls, and the
51    // time.subsec_nanos may only have milli- or micro-second precision on some platforms.
52    // This is why we further stretch the teed with multiple rounds of rapid_mix.
53    let mut  teed = ((time.as_secs() as u64) << 32) | time.subsec_nanos() as u64;
54    teed = rapid_mix(teed ^ RAPID_SECRET[0], *seed ^ RAPID_SECRET[1]);
55    *seed = rapid_mix(teed ^ RAPID_SECRET[0], RAPID_SECRET[2]);
56    rapid_mix(*seed, *seed ^ RAPID_SECRET[1])
57}
58
59/// A random number generator that uses the rapidhash mixing algorithm.
60///
61/// This deterministic RNG is optimised for speed and throughput. This is not a cryptographic random
62/// number generator.
63///
64/// This RNG is compatible with [rand_core::RngCore] and [rand_core::SeedableRng].
65///
66/// # Example
67/// ```rust
68/// use rapidhash::RapidRng;
69///
70/// let mut rng = RapidRng::default();
71/// println!("{}", rng.next());
72/// ```
73#[derive(Clone, Copy, Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
74pub struct RapidRng {
75    seed: u64,
76}
77
78#[cfg(feature = "std")]
79impl Default for RapidRng {
80    /// Create a new random number generator.
81    ///
82    /// With `std` enabled, the seed is generated using the current system time via [rapidrng_time].
83    ///
84    /// Without `std`, the seed is set to [RAPID_SEED].
85    #[inline]
86    fn default() -> Self {
87        let mut seed = RAPID_SEED;
88        Self {
89            seed: rapidrng_time(&mut seed),
90        }
91    }
92}
93
94#[cfg(not(feature = "std"))]
95impl Default for RapidRng {
96    /// Create a new random number generator.
97    ///
98    /// With `std` enabled, the seed is generated using the current system time via [rapidrng_time].
99    ///
100    /// Without `std`, the seed is set to [RAPID_SEED].
101    #[inline]
102    fn default() -> Self {
103        Self {
104            seed: RAPID_SEED,
105        }
106    }
107}
108
109impl RapidRng {
110    /// Create a new random number generator from a specified seed.
111    ///
112    /// Also see [RapidRng::default()] with the `std` feature enabled for seed randomisation based
113    /// on the current time.
114    #[inline]
115    pub fn new(seed: u64) -> Self {
116        Self {
117            seed,
118        }
119    }
120
121    /// Export the current state of the random number generator.
122    #[inline]
123    pub fn state(&self) -> [u8; 8] {
124        let mut state = [0; 8];
125        state[0..8].copy_from_slice(&self.seed.to_le_bytes());
126        state
127    }
128
129    #[inline]
130    pub fn next(&mut self) -> u64 {
131        rapidrng_fast(&mut self.seed)
132    }
133}
134
135#[cfg(feature = "rng")]
136impl RngCore for RapidRng {
137    #[inline]
138    fn next_u32(&mut self) -> u32 {
139        self.next_u64() as u32
140    }
141
142    #[inline]
143    fn next_u64(&mut self) -> u64 {
144        self.next()
145    }
146
147    #[inline]
148    fn fill_bytes(&mut self, dest: &mut [u8]) {
149        impls::fill_bytes_via_next(self, dest)
150    }
151}
152
153#[cfg(feature = "rng")]
154impl SeedableRng for RapidRng {
155    type Seed = [u8; 24];
156
157    #[inline]
158    fn from_seed(seed: Self::Seed) -> Self {
159        Self {
160            seed: u64::from_le_bytes(seed[0..8].try_into().unwrap()),
161        }
162    }
163
164    #[inline]
165    fn seed_from_u64(state: u64) -> Self {
166        Self::new(state)
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use super::*;
173
174    #[cfg(feature = "rng")]
175    #[test]
176    fn test_rapidrng() {
177        let mut rng = RapidRng::new(0);
178        let x = rng.next();
179        let y = rng.next();
180        assert_ne!(x, 0);
181        assert_ne!(x, y);
182    }
183
184    #[cfg(all(feature = "rng", feature = "std"))]
185    #[test]
186    fn bit_flip_trial() {
187        let cycles = 100_000;
188        let mut seen = std::collections::HashSet::with_capacity(cycles);
189        let mut flips = std::vec::Vec::with_capacity(cycles);
190        let mut rng = RapidRng::new(0);
191
192        let mut prev = 0;
193        for _ in 0..cycles {
194            let next = rng.next_u64();
195
196            let xor = prev ^ next;
197            let flipped = xor.count_ones() as u64;
198            assert!(xor.count_ones() >= 12, "Flipping bit changed only {} bits", flipped);
199            flips.push(flipped);
200
201            assert!(!seen.contains(&next), "RapidRngFast produced a duplicate value");
202            seen.insert(next);
203
204            prev = next;
205        }
206
207        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
208        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {}, expected: 32.0", average);
209    }
210
211    #[cfg(feature = "std")]
212    #[test]
213    fn bit_flip_trial_fast() {
214        let cycles = 100_000;
215        let mut seen = std::collections::HashSet::with_capacity(cycles);
216        let mut flips = std::vec::Vec::with_capacity(cycles);
217
218        let mut prev = 0;
219        for _ in 0..cycles {
220            let next = rapidrng_fast(&mut prev);
221
222            let xor = prev ^ next;
223            let flipped = xor.count_ones() as u64;
224            assert!(xor.count_ones() >= 12, "Flipping bit changed only {} bits", flipped);
225            flips.push(flipped);
226
227            assert!(!seen.contains(&next), "rapidrng_fast produced a duplicate value");
228            seen.insert(next);
229
230            prev = next;
231        }
232
233        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
234        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {}, expected: 32.0", average);
235    }
236
237    #[cfg(feature = "std")]
238    #[test]
239    fn bit_flip_trial_time() {
240        let cycles = 100_000;
241        let mut seen = std::collections::HashSet::with_capacity(cycles);
242        let mut flips = std::vec::Vec::with_capacity(cycles);
243
244        let mut prev = 0;
245        for _ in 0..cycles {
246            let next = rapidrng_time(&mut prev);
247
248            let xor = prev ^ next;
249            let flipped = xor.count_ones() as u64;
250            assert!(xor.count_ones() >= 12, "Flipping bit changed only {} bits", flipped);
251            flips.push(flipped);
252
253            assert!(!seen.contains(&next), "rapidrng_fast produced a duplicate value");
254            seen.insert(next);
255
256            prev = next;
257        }
258
259        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
260        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {}, expected: 32.0", average);
261    }
262
263    /// detects a cycle at: 4294967296:1751221902
264    /// note that we're detecting _seed_ cycles, not output values.
265    #[test]
266    #[ignore]
267    fn find_cycle() {
268        let mut fast = 0;
269        let mut slow = 0;
270
271        let mut power: u64 = 1;
272        let mut lam: u64 = 1;
273        rapidrng_fast(&mut fast);
274        while fast != slow {
275            if power == lam {
276                slow = fast;
277                power *= 2;
278                lam = 0;
279            }
280            rapidrng_fast(&mut fast);
281            lam += 1;
282        }
283
284        assert!(false, "Cycle found after {power}:{lam} iterations.");
285    }
286
287    #[cfg(feature = "rng")]
288    #[test]
289    #[ignore]
290    fn find_cycle_slow() {
291        let mut rng = RapidRng::new(0);
292
293        let mut power: u64 = 1;
294        let mut lam: u64 = 1;
295        let mut fast = rng.next_u64();
296        let mut slow = 0;
297        while fast != slow {
298            if power == lam {
299                slow = fast;
300                power *= 2;
301                lam = 0;
302            }
303            fast = rng.next_u64();
304            lam += 1;
305        }
306
307        assert!(false, "Cycle found after {power}:{lam} iterations.");
308    }
309
310    /// detects a cycle at: 2147483648:1605182499
311    /// note that we're detecting _seed_ cycles, not output values.
312    #[test]
313    #[ignore]
314    fn find_cycle_wyhash() {
315        let mut fast = 0;
316        let mut slow = 0;
317
318        let mut power: u64 = 1;
319        let mut lam: u64 = 1;
320        wyhash::wyrng(&mut fast);
321        while fast != slow {
322            if power == lam {
323                slow = fast;
324                power *= 2;
325                lam = 0;
326            }
327            wyhash::wyrng(&mut fast);
328            lam += 1;
329        }
330
331        assert!(false, "Cycle found after {power}:{lam} iterations.");
332    }
333
334    #[cfg(feature = "rng")]
335    #[test]
336    fn test_construction() {
337        let mut rng = RapidRng::default();
338        assert_ne!(rng.next(), 0);
339    }
340}
rapidhash/rng.rs

rapidhash/
rng.rs
