dive_stdlib/random/
source.rs1use super::primes::PRIMES;
4
5pub trait RandomSource {
26 fn next_bits(&mut self, bits: u32) -> i32;
29
30 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 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 #[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 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 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 fn next_prime(&mut self) -> i32 {
74 let len = PRIMES.len();
75 let mut index = len;
76 while index == len {
77 #[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 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
107const 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#[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 #[must_use]
134 pub const fn new(seed: i64) -> Self {
135 Self {
136 state: Self::scramble(seed),
137 }
138 }
139
140 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 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 #[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 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}