rapidhash/
rng.rs

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

rapidhash/
rng.rs
