rapidhash/
rng.rs

1//! Fast random number generation using rapidhash mixing.
2
3#[cfg(feature = "rng")]
4use rand_core::{RngCore, SeedableRng, impls};
5use crate::util::mix::rapid_mix;
6
7/// Uses the V1 rapid seed.
8const RAPID_SEED: u64 = 0xbdd89aa982704029;
9
10/// Uses the V1 rapid secrets.
11const RAPID_SECRET: [u64; 3] = [0x2d358dccaa6c78a5, 0x8bb84b93962eacc9, 0x4b33a62ed433d4a3];
12
13/// Generate a random number using rapidhash mixing.
14///
15/// This RNG is deterministic and optimized for throughput. It is not a cryptographic random number
16/// generator.
17///
18/// This implementation is equivalent in logic and performance to
19/// [wyhash::wyrng](https://docs.rs/wyhash/latest/wyhash/fn.wyrng.html) and
20/// [fasthash::u64](https://docs.rs/fastrand/latest/fastrand/), but uses rapidhash
21/// constants/secrets.
22///
23/// The weakness with this RNG is that at best it's a single cycle over the u64 space, as the seed
24/// is simple a position in a constant sequence. Future work could involve using a wider state to
25/// ensure we can generate many different sequences.
26#[inline]
27pub fn rapidrng_fast(seed: &mut u64) -> u64 {
28    *seed = seed.wrapping_add(RAPID_SECRET[0]);
29    rapid_mix::<false>(*seed, *seed ^ RAPID_SECRET[1])
30}
31
32/// A lower quality version of [`rapidrng_fast`] with that's slightly faster, with optimisations for
33/// u32 platforms and those without wide-arithmetic support.
34///
35/// This is not a portable RNG, as it will produce different results on different platforms. Use
36/// [`rapidrng_fast`] if stable outputs are required.
37///
38/// Used in the rapidhash WASM benchmarks.
39#[inline]
40pub fn rapidrng_fast_not_portable(seed: &mut u64) -> u64 {
41    *seed = seed.wrapping_add(RAPID_SECRET[0]);
42    rapid_mix_np_low_quality(*seed, RAPID_SECRET[1])
43}
44
45/// A very fast low-quality mixing function used only for the ultra-fast PRNG.
46///
47/// Uses the standard `rapid_mix` for 64-bit architectures, and otherwise uses a very cheap
48/// u32-mix for platforms without wide-arithmetic support. This is even cheaper/lower quality than
49/// `rapid_mix_np`.
50#[inline(always)]
51fn rapid_mix_np_low_quality(x: u64, y: u64) -> u64 {
52    #[cfg(any(
53        all(
54            target_pointer_width = "64",
55            not(any(target_arch = "sparc64", target_arch = "wasm64")),
56        ),
57        target_arch = "aarch64",
58        target_arch = "x86_64",
59        all(target_family = "wasm", target_feature = "wide-arithmetic"),
60    ))]
61    {
62        rapid_mix::<false>(x, y)
63    }
64
65    #[cfg(not(any(
66        all(
67            target_pointer_width = "64",
68            not(any(target_arch = "sparc64", target_arch = "wasm64")),
69        ),
70        target_arch = "aarch64",
71        target_arch = "x86_64",
72        all(target_family = "wasm", target_feature = "wide-arithmetic"),
73    )))]
74    {
75        // u64 x u64 -> u128 product is prohibitively expensive on 32-bit.
76        // Decompose into 32-bit parts.
77        let lx = x as u32;
78        let ly = y as u32;
79        let hx = (x >> 32) as u32;
80        let hy = (y >> 32) as u32;
81
82        // u32 x u32 -> u64 the low bits of one with the high bits of the other.
83        let afull = (lx as u64) * (hy as u64);
84        let bfull = (hx as u64) * (ly as u64);
85
86        // Combine, swapping low/high of one of them so the upper bits of the
87        // product of one combine with the lower bits of the other.
88        afull ^ bfull.rotate_right(32)
89    }
90}
91
92/// Generate a random number non-deterministically by re-seeding with the current time.
93///
94/// This is not a cryptographic random number generator.
95///
96/// Note fetching system time requires a syscall and is therefore much slower than [rapidrng_fast].
97/// It can also be used to seed [rapidrng_fast].
98///
99/// Requires the `std` feature and a platform that supports [std::time::SystemTime].
100///
101/// # Example
102/// ```rust
103/// use rapidhash::rng::{rapidrng_fast, rapidrng_time};
104///
105/// // choose a non-deterministic random seed (50-100ns)
106/// let mut seed = rapidrng_time(&mut 0);
107///
108/// // rapid fast deterministic random numbers (~1ns/iter)
109/// for _ in 0..10 {
110///     println!("{}", rapidrng_fast(&mut seed));
111/// }
112/// ```
113#[cfg(any(
114    all(
115        feature = "std",
116        not(any(
117            miri,
118            all(target_family = "wasm", target_os = "unknown"),
119            target_os = "zkvm"
120        ))
121    ),
122    docsrs
123))]
124#[inline]
125pub fn rapidrng_time(seed: &mut u64) -> u64 {
126    let time = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap();
127    // NOTE limited entropy: only a few of the time.as_secs bits will change between calls, and the
128    // time.subsec_nanos may only have milli- or micro-second precision on some platforms.
129    // This is why we further stretch the teed with multiple rounds of rapid_mix.
130    let mut  teed = (time.as_secs() << 32) | time.subsec_nanos() as u64;
131    teed = rapid_mix::<false>(teed ^ RAPID_SECRET[0], *seed ^ RAPID_SECRET[1]);
132    *seed = rapid_mix::<false>(teed ^ RAPID_SECRET[0], RAPID_SECRET[2]);
133    rapid_mix::<false>(*seed, *seed ^ RAPID_SECRET[1])
134}
135
136/// A random number generator that uses the rapidhash mixing algorithm.
137///
138/// This deterministic RNG is optimized for speed and throughput. This is not a cryptographic random
139/// number generator.
140///
141/// This RNG is compatible with [`rand_core::RngCore`] and [`rand_core::SeedableRng`].
142///
143/// # Example
144/// ```rust
145/// use rapidhash::rng::RapidRng;
146///
147/// let mut rng = RapidRng::default();
148/// println!("{}", rng.next());
149/// ```
150#[derive(Clone, Copy, Debug, PartialEq, Eq, Ord, PartialOrd, Hash)]
151pub struct RapidRng {
152    seed: u64,
153}
154
155#[cfg(any(
156    all(
157        feature = "std",
158        not(any(
159            miri,
160            all(target_family = "wasm", target_os = "unknown"),
161            target_os = "zkvm"
162        ))
163    ),
164    docsrs
165))]
166impl Default for RapidRng {
167    /// Create a new random number generator.
168    ///
169    /// With `std` enabled, the seed is generated using the current system time via [rapidrng_time].
170    ///
171    /// Without `std`, the seed is set to the default seed.
172    #[inline]
173    fn default() -> Self {
174        let mut seed = RAPID_SEED;
175        Self {
176            seed: rapidrng_time(&mut seed),
177        }
178    }
179}
180
181#[cfg(not(any(
182    all(
183        feature = "std",
184        not(any(
185            miri,
186            all(target_family = "wasm", target_os = "unknown"),
187            target_os = "zkvm"
188        ))
189    ),
190    docsrs
191)))]
192impl Default for RapidRng {
193    /// Create a new random number generator.
194    ///
195    /// With `std` enabled, the seed is generated using the current system time via [rapidrng_time].
196    ///
197    /// Without `std`, the seed is set to [RAPID_SEED].
198    #[inline]
199    fn default() -> Self {
200        Self {
201            seed: RAPID_SEED,
202        }
203    }
204}
205
206impl RapidRng {
207    /// Create a new random number generator from a specified seed.
208    ///
209    /// Also see [RapidRng::default()] with the `std` feature enabled for seed randomisation based
210    /// on the current time.
211    #[inline]
212    pub fn new(seed: u64) -> Self {
213        Self {
214            seed,
215        }
216    }
217
218    /// Export the current state of the random number generator.
219    #[inline]
220    pub fn state(&self) -> [u8; 8] {
221        self.seed.to_le_bytes()
222    }
223
224    /// Get the next random number from this PRNG and iterate the state.
225    #[inline]
226    #[allow(clippy::should_implement_trait)]
227    pub fn next(&mut self) -> u64 {
228        rapidrng_fast(&mut self.seed)
229    }
230}
231
232#[cfg(feature = "rng")]
233impl RngCore for RapidRng {
234    #[inline]
235    fn next_u32(&mut self) -> u32 {
236        self.next_u64() as u32
237    }
238
239    #[inline]
240    fn next_u64(&mut self) -> u64 {
241        self.next()
242    }
243
244    #[inline]
245    fn fill_bytes(&mut self, dest: &mut [u8]) {
246        impls::fill_bytes_via_next(self, dest)
247    }
248}
249
250#[cfg(feature = "rng")]
251impl SeedableRng for RapidRng {
252    type Seed = [u8; 8];
253
254    #[inline]
255    fn from_seed(seed: Self::Seed) -> Self {
256        Self {
257            seed: u64::from_le_bytes(seed),
258        }
259    }
260
261    #[inline]
262    fn seed_from_u64(state: u64) -> Self {
263        Self::new(state)
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use super::*;
270
271    #[cfg(feature = "rng")]
272    #[test]
273    fn test_rapidrng() {
274        let mut rng = RapidRng::new(0);
275        let x = rng.next();
276        let y = rng.next();
277        assert_ne!(x, 0);
278        assert_ne!(x, y);
279    }
280
281    #[cfg(all(feature = "rng", feature = "std"))]
282    #[test]
283    fn bit_flip_trial() {
284        let cycles = 100_000;
285        let mut seen = std::collections::HashSet::with_capacity(cycles);
286        let mut flips = std::vec::Vec::with_capacity(cycles);
287        let mut rng = RapidRng::new(0);
288
289        let mut prev = 0;
290        for _ in 0..cycles {
291            let next = rng.next_u64();
292
293            let xor = prev ^ next;
294            let flipped = xor.count_ones() as u64;
295            assert!(xor.count_ones() >= 10, "Flipping bit changed only {} bits", flipped);
296            flips.push(flipped);
297
298            assert!(!seen.contains(&next), "RapidRngFast produced a duplicate value");
299            seen.insert(next);
300
301            prev = next;
302        }
303
304        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
305        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {}, expected: 32.0", average);
306    }
307
308    #[cfg(feature = "std")]
309    #[test]
310    fn bit_flip_trial_fast() {
311        let cycles = 100_000;
312        let mut seen = std::collections::HashSet::with_capacity(cycles);
313        let mut flips = std::vec::Vec::with_capacity(cycles);
314
315        let mut prev = 0;
316        for _ in 0..cycles {
317            let next = rapidrng_fast(&mut prev);
318
319            let xor = prev ^ next;
320            let flipped = xor.count_ones() as u64;
321            assert!(xor.count_ones() >= 10, "Flipping bit changed only {} bits", flipped);
322            flips.push(flipped);
323
324            assert!(!seen.contains(&next), "rapidrng_fast produced a duplicate value");
325            seen.insert(next);
326
327            prev = next;
328        }
329
330        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
331        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {}, expected: 32.0", average);
332    }
333
334    #[cfg(feature = "std")]
335    #[test]
336    fn bit_flip_trial_time() {
337        let cycles = 100_000;
338        let mut seen = std::collections::HashSet::with_capacity(cycles);
339        let mut flips = std::vec::Vec::with_capacity(cycles);
340
341        let mut prev = 0;
342        for _ in 0..cycles {
343            let next = rapidrng_time(&mut prev);
344
345            let xor = prev ^ next;
346            let flipped = xor.count_ones() as u64;
347            assert!(xor.count_ones() >= 10, "Flipping bit changed only {} bits", flipped);
348            flips.push(flipped);
349
350            assert!(!seen.contains(&next), "rapidrng_time produced a duplicate value");
351            seen.insert(next);
352
353            prev = next;
354        }
355
356        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
357        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {}, expected: 32.0", average);
358    }
359
360    /// detects a cycle at: 4294967296:1751221902
361    /// note that we're detecting _seed_ cycles, not output values.
362    #[test]
363    #[ignore]
364    fn find_cycle() {
365        let mut fast = 0;
366        let mut slow = 0;
367
368        let mut power: u64 = 1;
369        let mut lam: u64 = 1;
370        rapidrng_fast(&mut fast);
371        while fast != slow {
372            if power == lam {
373                slow = fast;
374                power *= 2;
375                lam = 0;
376            }
377            rapidrng_fast(&mut fast);
378            lam += 1;
379        }
380
381        panic!("Cycle found after {power}:{lam} iterations.");
382    }
383
384    #[cfg(feature = "rng")]
385    #[test]
386    #[ignore]
387    fn find_cycle_slow() {
388        let mut rng = RapidRng::new(0);
389
390        let mut power: u64 = 1;
391        let mut lam: u64 = 1;
392        let mut fast = rng.next_u64();
393        let mut slow = 0;
394        while fast != slow {
395            if power == lam {
396                slow = fast;
397                power *= 2;
398                lam = 0;
399            }
400            fast = rng.next_u64();
401            lam += 1;
402        }
403
404        assert!(false, "Cycle found after {power}:{lam} iterations.");
405    }
406
407    #[cfg(feature = "rng")]
408    #[test]
409    fn test_construction() {
410        let mut rng = RapidRng::default();
411        assert_ne!(rng.next(), 0);
412    }
413}
rapidhash/rng.rs

rapidhash/
rng.rs
