Skip to main content

dive_stdlib/random/
source.rs

1//! The bit source every random draw is built on, and `java.util.Random`, bit-exact.
2
3use super::primes::PRIMES;
4
5/// A source of random bits, with the derived draws TLC uses.
6///
7/// Everything TLC draws reduces to `java.util.Random.next(bits)`: `nextInt(bound)`,
8/// `nextLong` and `nextDouble` are fixed functions of successive `next` calls. So a
9/// source only implements [`RandomSource::next_bits`]; the provided methods are
10/// Java 17's algorithms (`java/util/Random.java`), and give TLC's values exactly when
11/// the bits are [`JavaRandom`]'s.
12///
13/// The trait is object safe. Any `FnMut(u32) -> i32` is a source, so an evaluator
14/// that must not name this crate (`dive-eval` sits below `dive-stdlib` in the
15/// layering) can carry a `&mut dyn FnMut(u32) -> i32` and the operators accept it:
16///
17/// ```
18/// use dive_stdlib::random::{JavaRandom, RandomSource};
19/// let mut rng = JavaRandom::new(7);
20/// let mut bits = |n| rng.next_bits(n);
21/// let f: &mut dyn FnMut(u32) -> i32 = &mut bits;
22/// // RandomElement(1..1000000) with -seed 7, as TLC draws it.
23/// assert_eq!(1 + (f.next_double() * 1_000_000.0).floor() as i64, 730_700);
24/// ```
25pub trait RandomSource {
26    /// The next `bits` random bits (`1..=32`), as `java.util.Random.next(bits)`:
27    /// non-negative for `bits < 32`, any `i32` for 32.
28    fn next_bits(&mut self, bits: u32) -> i32;
29
30    /// `Random.nextDouble()`: a double in `[0, 1)` from 53 bits.
31    fn next_double(&mut self) -> f64 {
32        let hi = i64::from(self.next_bits(26));
33        let lo = i64::from(self.next_bits(27));
34        #[allow(clippy::cast_precision_loss, reason = "exact: the value has 53 bits")]
35        let n = ((hi << 27) + lo) as f64;
36        n * DOUBLE_UNIT
37    }
38
39    /// `Random.nextInt(bound)`, or `None` when `bound <= 0` (where Java throws
40    /// `IllegalArgumentException`). Draws nothing for a bad bound.
41    fn next_int_bounded(&mut self, bound: i32) -> Option<i32> {
42        if bound <= 0 {
43            return None;
44        }
45        let mut r = self.next_bits(31);
46        let m = bound - 1;
47        if bound & m == 0 {
48            // A power of two: the high bits.
49            #[allow(clippy::cast_possible_truncation, reason = "result < bound")]
50            return Some(((i64::from(bound) * i64::from(r)) >> 31) as i32);
51        }
52        let mut u = r;
53        loop {
54            r = u % bound;
55            // Java: `u - r + m < 0` in int arithmetic rejects the biased tail.
56            if u.wrapping_sub(r).wrapping_add(m) < 0 {
57                u = self.next_bits(31);
58            } else {
59                return Some(r);
60            }
61        }
62    }
63
64    /// `Random.nextLong()`.
65    fn next_long(&mut self) -> i64 {
66        let hi = i64::from(self.next_bits(32));
67        let lo = i64::from(self.next_bits(32));
68        (hi << 32).wrapping_add(lo)
69    }
70
71    /// `RandomGenerator.nextPrime(Random)`: one of TLC's 1341 primes near 1.28
72    /// million, chosen with one `nextDouble`.
73    fn next_prime(&mut self) -> i32 {
74        let len = PRIMES.len();
75        let mut index = len;
76        while index == len {
77            // `(int) Math.floor(r.nextDouble() * index)`; `index` is `len` here.
78            #[allow(
79                clippy::cast_possible_truncation,
80                clippy::cast_sign_loss,
81                clippy::cast_precision_loss,
82                reason = "0 <= nextDouble * len < len"
83            )]
84            {
85                index = (self.next_double() * len as f64).floor() as usize;
86            }
87        }
88        PRIMES[index]
89    }
90
91    /// `(int) Math.floor(nextDouble() * size)`: TLC's index into a set of `size`
92    /// elements (`SetEnumValue.randomElement`, `IntervalValue.randomElement`,
93    /// `SimulationWorker.randomState`). `size` 0 gives 0, as in TLC, after drawing.
94    fn next_index(&mut self, size: u64) -> u64 {
95        #[allow(
96            clippy::cast_possible_truncation,
97            clippy::cast_sign_loss,
98            clippy::cast_precision_loss,
99            reason = "0 <= nextDouble * size < size; sizes past 2^53 lose precision \
100                      deterministically (dive mode only: TLC sizes are ints)"
101        )]
102        let i = (self.next_double() * size as f64).floor() as u64;
103        i
104    }
105}
106
107/// `0x1.0p-53`, Java's `DOUBLE_UNIT`.
108const DOUBLE_UNIT: f64 = f64::EPSILON / 2.0;
109
110impl<F: FnMut(u32) -> i32 + ?Sized> RandomSource for F {
111    fn next_bits(&mut self, bits: u32) -> i32 {
112        self(bits)
113    }
114}
115
116/// `java.util.Random`, bit-exact: the 48-bit linear congruential generator of
117/// Knuth, TAOCP vol. 2 ยง3.2.1, as Java specifies it.
118///
119/// TLC draws all of its pseudo-random choices from instances of this class (or of its
120/// subclass `tlc2.util.RandomGenerator`, which only adds counting and
121/// [`RandomSource::next_prime`]).
122#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
123pub struct JavaRandom {
124    state: u64,
125}
126
127const MULTIPLIER: u64 = 0x0005_DEEC_E66D;
128const ADDEND: u64 = 0xB;
129const MASK: u64 = (1 << 48) - 1;
130
131impl JavaRandom {
132    /// `new Random(seed)`.
133    #[must_use]
134    pub const fn new(seed: i64) -> Self {
135        Self {
136            state: Self::scramble(seed),
137        }
138    }
139
140    /// `setSeed(seed)`.
141    pub const fn set_seed(&mut self, seed: i64) {
142        self.state = Self::scramble(seed);
143    }
144
145    #[allow(
146        clippy::cast_sign_loss,
147        reason = "two's complement bits, as Java's long"
148    )]
149    const fn scramble(seed: i64) -> u64 {
150        (seed as u64 ^ MULTIPLIER) & MASK
151    }
152
153    /// `RandomGenerator.setSeed(seed, aril)`: reseed, then skip `aril` doubles (TLC's
154    /// `-aril` for simulation).
155    pub fn set_seed_aril(&mut self, seed: i64, aril: u64) {
156        self.set_seed(seed);
157        for _ in 0..aril {
158            let _ = self.next_double();
159        }
160    }
161}
162
163impl RandomSource for JavaRandom {
164    fn next_bits(&mut self, bits: u32) -> i32 {
165        debug_assert!((1..=32).contains(&bits));
166        self.state = self.state.wrapping_mul(MULTIPLIER).wrapping_add(ADDEND) & MASK;
167        // `(int)(seed >>> (48 - bits))`: keep the low 32 bits of the shifted value.
168        #[allow(clippy::cast_possible_truncation, reason = "Java's (int) cast")]
169        let v = (self.state >> (48 - bits)) as u32;
170        v.cast_signed()
171    }
172}
173
174#[cfg(test)]
175mod tests {
176    use super::*;
177
178    #[test]
179    fn matches_java_for_seed_7() {
180        // `java.util.Random(7)`: floor(nextDouble() * 1000000), from the pinned JRE.
181        let mut r = JavaRandom::new(7);
182        let got: Vec<u64> = (0..10).map(|_| r.next_index(1_000_000)).collect();
183        assert_eq!(
184            got,
185            [
186                730_699, 749_169, 348_309, 897_277, 708_177, 351_914, 120_736, 849_913, 83_219,
187                928_748
188            ]
189        );
190    }
191
192    #[test]
193    fn bad_bound_draws_nothing() {
194        let mut r = JavaRandom::new(1);
195        let before = r;
196        assert_eq!(r.next_int_bounded(0), None);
197        assert_eq!(r.next_int_bounded(-5), None);
198        assert_eq!(r, before);
199    }
200}