1 use std::cell::Cell;
2
3 /// Fast random number generate.
4 ///
5 /// Implement xorshift64+: 2 32-bit xorshift sequences added together.
6 /// Shift triplet `[17,7,16]` was calculated as indicated in Marsaglia's
7 /// Xorshift paper: <https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf>
8 /// This generator passes the SmallCrush suite, part of TestU01 framework:
9 /// <http://simul.iro.umontreal.ca/testu01/tu01.html>
10 #[derive(Debug)]
11 pub(crate) struct FastRand {
12 one: Cell<u32>,
13 two: Cell<u32>,
14 }
15
16 impl FastRand {
17 /// Initializes a new, thread-local, fast random number generator.
new(seed: u64) -> FastRand18 pub(crate) fn new(seed: u64) -> FastRand {
19 let one = (seed >> 32) as u32;
20 let mut two = seed as u32;
21
22 if two == 0 {
23 // This value cannot be zero
24 two = 1;
25 }
26
27 FastRand {
28 one: Cell::new(one),
29 two: Cell::new(two),
30 }
31 }
32
fastrand_n(&self, n: u32) -> u3233 pub(crate) fn fastrand_n(&self, n: u32) -> u32 {
34 // This is similar to fastrand() % n, but faster.
35 // See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
36 let mul = (self.fastrand() as u64).wrapping_mul(n as u64);
37 (mul >> 32) as u32
38 }
39
fastrand(&self) -> u3240 fn fastrand(&self) -> u32 {
41 let mut s1 = self.one.get();
42 let s0 = self.two.get();
43
44 s1 ^= s1 << 17;
45 s1 = s1 ^ s0 ^ s1 >> 7 ^ s0 >> 16;
46
47 self.one.set(s0);
48 self.two.set(s1);
49
50 s0.wrapping_add(s1)
51 }
52 }
53
54 // Used by the select macro and `StreamMap`
55 #[cfg(any(feature = "macros"))]
56 #[doc(hidden)]
57 #[cfg_attr(not(feature = "macros"), allow(unreachable_pub))]
thread_rng_n(n: u32) -> u3258 pub fn thread_rng_n(n: u32) -> u32 {
59 thread_local! {
60 static THREAD_RNG: FastRand = FastRand::new(crate::loom::rand::seed());
61 }
62
63 THREAD_RNG.with(|rng| rng.fastrand_n(n))
64 }
65