anode/
rand.rs

1use crate::inf_iterator::InfIterator;
2use std::marker::PhantomData;
3use std::ops::Range;
4use std::time::{Duration, SystemTime};
5
6/// A minimal specification of a 64-bit random number generator.
7pub trait Rand64 {
8    /// Return the next random `u64`.
9    fn next_u64(&mut self) -> u64;
10
11    /// Returns a `bool` with a probability `p` of being true.
12    ///
13    /// # Example
14    /// ```
15    /// use anode::rand::{Probability, Rand64, Xorshift};
16    /// let mut rng = Xorshift::default();
17    /// println!("{}", rng.gen_bool(Probability::new(1.0 / 3.0)));
18    /// ```
19    #[inline]
20    fn gen_bool(&mut self, p: Probability) -> bool {
21        let cutoff = (p.0 * u64::MAX as f64) as u64;
22        let mut next = self.next_u64();
23        if next == u64::MAX {
24            // guarantees that gen_bool(p=1.0) is never true
25            next = u64::MAX - 1;
26        }
27        #[cfg(test)]
28        dbg!((cutoff, next));
29        next < cutoff
30    }
31}
32
33/// Represents a probability in the range \[0, 1\].
34#[derive(Clone, Copy)]
35pub struct Probability(f64);
36
37impl Probability {
38    /// Creates a new [`Probability`] value, bounded in the range \[0, 1\].
39    ///
40    /// # Example
41    /// ```
42    /// use anode::rand::Probability;
43    /// let p = Probability::new(0.25);
44    /// assert_eq!(0.25, p.into());
45    /// ```
46    ///
47    /// # Panics
48    /// If `p < 0` or `p > 1`.
49    pub fn new(p: f64) -> Self {
50        assert!(p >= 0f64, "p ({p}) cannot be less than 0");
51        assert!(p <= 1f64, "p ({p}) cannot be greater than 1");
52        Self(p)
53    }
54}
55
56impl From<Probability> for f64 {
57    fn from(p: Probability) -> Self {
58        p.0
59    }
60}
61
62impl From<f64> for Probability {
63    fn from(p: f64) -> Self {
64        Probability::new(p)
65    }
66}
67
68/// The means for seeding an RNG.
69pub trait Seeded {
70    type Rng: Rand64;
71
72    /// Creates a new [`Rand64`] instance from the given seed.
73    fn seed(seed: u64) -> Self::Rng;
74}
75
76/// Randomly chooses a duration from a range.
77pub trait RandDuration {
78    fn gen_range(&mut self, range: Range<Duration>) -> Duration;
79}
80
81impl<R: Rand64> RandDuration for R {
82    #[inline(always)]
83    fn gen_range(&mut self, range: Range<Duration>) -> Duration {
84        if range.is_empty() {
85            return range.start;
86        }
87        let span = (range.end - range.start).as_nanos();
88        if span <= u64::MAX as u128 {
89            let span = span as u64;
90            let random = span.gen(self);
91            range.start + Duration::from_nanos(random)
92        } else {
93            let random = span.gen(self);
94            range.start + duration_from_nanos(random)
95        }
96    }
97}
98
99trait GenSpan {
100    fn gen(&self, rng: &mut impl Rand64) -> Self;
101}
102
103impl GenSpan for u64 {
104    #[inline(always)]
105    fn gen(&self, rng: &mut impl Rand64) -> Self {
106        rng.next_u64() % self
107    }
108}
109
110impl GenSpan for u128 {
111    #[inline(always)]
112    fn gen(&self, rng: &mut impl Rand64) -> Self {
113        let random = (rng.next_u64() as u128) << 64 | (rng.next_u64() as u128);
114        random % self
115    }
116}
117
118/// [`Duration::from_nanos`] has limited range, which [was not reverted post-stabilisation](https://github.com/rust-lang/rust/issues/51107).
119/// This function permits the creation of a [`Duration]` from a `u128`, making it consistent with
120/// [`Duration::as_nanos`].
121#[inline(always)]
122pub const fn duration_from_nanos(nanos: u128) -> Duration {
123    const NANOS_PER_SEC: u128 = 1_000_000_000;
124    let secs = (nanos / NANOS_PER_SEC) as u64;
125    let nanos = (nanos % NANOS_PER_SEC) as u32;
126    Duration::new(secs, nanos)
127}
128
129pub struct FixedDuration;
130
131pub const FIXED_DURATION: FixedDuration = FixedDuration;
132
133impl Default for FixedDuration {
134    #[inline(always)]
135    fn default() -> Self {
136        Self
137    }
138}
139
140impl RandDuration for FixedDuration {
141    #[inline(always)]
142    fn gen_range(&mut self, range: Range<Duration>) -> Duration {
143        const NANOSECOND: Duration = Duration::new(0, 1);
144        if range.is_empty() {
145            range.end
146        } else {
147            range.end - NANOSECOND
148        }
149    }
150}
151
152/// Basic [Xorshift](https://en.wikipedia.org/wiki/Xorshift) RNG.
153pub struct Xorshift {
154    seed: u64,
155}
156
157impl Default for Xorshift {
158    fn default() -> Self {
159        Self::seed(1)
160    }
161}
162
163impl Rand64 for Xorshift {
164    fn next_u64(&mut self) -> u64 {
165        let mut s = self.seed;
166        s ^= s << 13;
167        s ^= s >> 7;
168        s ^= s << 17;
169        self.seed = s;
170        s
171    }
172}
173
174impl Seeded for Xorshift {
175    type Rng = Xorshift;
176
177    #[inline]
178    fn seed(seed: u64) -> Self::Rng {
179        // a zero seed disables Xorshift, rendering it (effectively) a constant; hence, we avoid it
180        Self { seed: if seed == 0 { u64::MAX >> 1 } else { seed } }
181    }
182}
183
184#[derive(Debug)]
185pub struct CyclicSeed(u64);
186
187impl CyclicSeed {
188    #[inline]
189    pub fn new(seed: u64) -> Self {
190        Self(seed)
191    }
192}
193
194impl Default for CyclicSeed {
195    #[inline]
196    fn default() -> Self {
197        Self(0)
198    }
199}
200
201impl InfIterator for CyclicSeed {
202    type Item = u64;
203
204    #[inline]
205    fn next(&mut self) -> Self::Item {
206        let current = self.0;
207        self.0 = if current == u64::MAX { 0 } else { current + 1 };
208        current
209    }
210}
211
212pub struct LazyRand64<S: Seeded, F: FnOnce() -> u64> {
213    state: Option<InitState<S::Rng, F>>,
214    __phantom_data: PhantomData<S>,
215}
216
217impl<S: Seeded, F: FnOnce() -> u64> LazyRand64<S, F> {
218    pub fn lazy(f: F) -> Self {
219        Self {
220            state: Some(InitState::Uninit(f)),
221            __phantom_data: PhantomData::default(),
222        }
223    }
224
225    pub fn eager(rng: S::Rng) -> Self {
226        Self {
227            state: Some(InitState::Ready(rng)),
228            __phantom_data: PhantomData::default(),
229        }
230    }
231}
232
233enum InitState<R: Rand64, F: FnOnce() -> u64> {
234    Uninit(F),
235    Ready(R),
236}
237
238impl<S: Seeded, F: FnOnce() -> u64> Rand64 for LazyRand64<S, F> {
239    fn next_u64(&mut self) -> u64 {
240        match self.state.take() {
241            Some(InitState::Uninit(f)) => {
242                let seed = f();
243                let mut rng = S::seed(seed);
244                let next = rng.next_u64();
245                self.state = Some(InitState::<S::Rng, F>::Ready(rng));
246                next
247            }
248            Some(InitState::Ready(mut rng)) => {
249                let next = rng.next_u64();
250                self.state = Some(InitState::Ready(rng));
251                next
252            }
253            None => unreachable!(),
254        }
255    }
256}
257
258/// Derives a seed from the system clock by XORing the upper 64 bits of the nanosecond timestamp
259/// with the lower 64 bits.
260pub fn clock_seed() -> u64 {
261    let time = SystemTime::now()
262        .duration_since(SystemTime::UNIX_EPOCH)
263        .unwrap()
264        .as_nanos();
265    let folded = (time >> 64) ^ time;
266    folded as u64
267}
268
269#[cfg(test)]
270mod tests;
anode/rand.rs

anode/
rand.rs
