criterion/stats/
rand_util.rs

Help
1use rand_core::{RngCore, SeedableRng};
2use rand_os::OsRng;
3use rand_xoshiro::Xoshiro256StarStar;
4
5use std::cell::RefCell;
6
7pub type Rng = Xoshiro256StarStar;
8
9thread_local! {
10    static SEED_RAND: RefCell<OsRng> = RefCell::new(OsRng::new().unwrap());
11}
12
13pub fn new_rng() -> Rng {
14    SEED_RAND.with(|r| {
15        let mut seed = [0u8; 32];
16        r.borrow_mut().fill_bytes(&mut seed);
17        Xoshiro256StarStar::from_seed(seed)
18    })
19}
20
21/// Source of uniform random numbers within a range of usize values.
22pub struct Range {
23    low: usize,
24    range: usize,
25    zone: usize,
26}
27impl Range {
28    pub fn new_exclusive(low: usize, high: usize) -> Range {
29        Range::new_inclusive(low, high - 1)
30    }
31
32    pub fn new_inclusive(low: usize, high: usize) -> Range {
33        let max = ::std::usize::MAX;
34        assert!(low < high);
35        assert!(high < max);
36        let range = high.wrapping_sub(low).wrapping_add(1);
37        let ints_to_reject = (max - range + 1) % range;
38        let zone = max - ints_to_reject;
39
40        Range { low, range, zone }
41    }
42
43    pub fn sample<R: RngCore>(&self, rng: &mut R) -> usize {
44        loop {
45            let value: usize = rng.next_u64() as usize;
46
47            if value <= self.zone {
48                return (value % self.range) + self.low;
49            }
50        }
51    }
52}
53
54#[cfg(test)]
55mod test {
56    use super::*;
57    use quickcheck::TestResult;
58    use std::cmp;
59
60    quickcheck! {
61        fn range_returns_samples_in_range(low: usize, high: usize) -> TestResult {
62            let (low, high) = (cmp::min(low, high), cmp::max(low, high));
63            if (high - low) < 2 || high == ::std::usize::MAX {
64                return TestResult::discard();
65            }
66
67            let mut rng = new_rng();
68            let range = Range::new_inclusive(low, high);
69
70            for _ in 0..1000 {
71                let value = range.sample(&mut rng);
72                if !(low <= value && value <= high) {
73                    return TestResult::from_bool(false);
74                }
75            }
76
77            return TestResult::from_bool(true);
78        }
79    }
80
81    struct CountingRng {
82        count: u64,
83    }
84    impl ::rand_core::RngCore for CountingRng {
85        fn next_u32(&mut self) -> u32 {
86            self.next_u64() as u32
87        }
88
89        fn next_u64(&mut self) -> u64 {
90            let value = self.count;
91            self.count = self.count.wrapping_add(1);
92            value
93        }
94
95        fn fill_bytes(&mut self, _dest: &mut [u8]) {
96            unimplemented!()
97        }
98
99        fn try_fill_bytes(
100            &mut self,
101            _dest: &mut [u8],
102        ) -> ::std::result::Result<(), ::rand_core::Error> {
103            unimplemented!()
104        }
105    }
106
107    // These are arbitrary
108    const SIZE: usize = 17;
109    const ROUNDS: usize = 200;
110
111    #[test]
112    fn range_is_uniform() {
113        let mut rng = CountingRng { count: 0 };
114        let range = Range::new_exclusive(0, SIZE);
115        let mut array = [0usize; SIZE];
116
117        for _ in 0..(ROUNDS * SIZE) {
118            let index = range.sample(&mut rng);
119            array[index] += 1;
120        }
121
122        assert_eq!([ROUNDS; SIZE], array);
123    }
124
125    #[test]
126    fn range_is_uniform_outside_of_zone() {
127        // Check that range is still uniform when provided with numbers near u64::MAX.
128        let mut rng = CountingRng {
129            count: ::std::u64::MAX - ((SIZE * ROUNDS) / 2) as u64,
130        };
131        let range = Range::new_exclusive(0, SIZE);
132        let mut array = [0usize; SIZE];
133
134        for _ in 0..(ROUNDS * SIZE) {
135            let index = range.sample(&mut rng);
136            array[index] += 1;
137        }
138
139        assert_eq!([ROUNDS; SIZE], array);
140    }
141}
criterion/stats/rand_util.rs

criterion/stats/
rand_util.rs
