motion_core/
random.rs

1//! Key-derived deterministic random streams without global or frame-local state.
2
3use std::hash::{Hash, Hasher};
4use std::ops::Range;
5
6use crate::Vector2;
7
8/// A reproducible local random stream derived entirely from a hashed key.
9///
10/// Key bytes use FNV-1a, followed by SplitMix64 for each sample. Integer hashing
11/// uses little-endian bytes and widens usize/isize to 64 bits. Custom Hash
12/// implementations must themselves be deterministic. Rust's Hash encodings are
13/// not a serialization format; cross-version key encoding stability is not
14/// promised. This generator is not cryptographic and has no shared mutable state.
15///
16/// ```
17/// use motion_core::Random;
18/// let mut first = Random::from_key(("spark", 42_u64));
19/// let mut second = Random::from_key(("spark", 42_u64));
20/// assert_eq!(first.next_float(), second.next_float());
21/// assert!((10.0..20.0).contains(&first.range(10.0..20.0)));
22/// assert_eq!(first.choose(&[7]), Some(&7));
23/// ```
24#[derive(Clone, Debug)]
25pub struct Random {
26    state: u64,
27}
28
29impl Random {
30    /// Starts a fresh stream; equal keys reproduce the same sequence.
31    pub fn from_key(key: impl Hash) -> Self {
32        let mut hasher = KeyHasher(0xcbf29ce484222325);
33        key.hash(&mut hasher);
34        Self {
35            state: hasher.finish(),
36        }
37    }
38
39    /// Starts a counter-keyed particle stream without Hash encoding or shared state.
40    /// Equal seed/index/step values are independent of traversal and worker count.
41    pub fn for_particle(seed: u64, index: u64, step: u64) -> Self {
42        fn mix(mut value: u64) -> u64 {
43            value = (value ^ (value >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
44            value = (value ^ (value >> 27)).wrapping_mul(0x94d049bb133111eb);
45            value ^ (value >> 31)
46        }
47        Self {
48            state: mix(seed
49                ^ mix(index.wrapping_add(0x9e3779b97f4a7c15))
50                ^ mix(step.wrapping_add(0xd1b54a32d192ed03))),
51        }
52    }
53
54    fn next_bits(&mut self) -> u64 {
55        self.state = self.state.wrapping_add(0x9e3779b97f4a7c15);
56        let mut value = self.state;
57        value = (value ^ (value >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
58        value = (value ^ (value >> 27)).wrapping_mul(0x94d049bb133111eb);
59        value ^ (value >> 31)
60    }
61
62    /// Returns one of 2^53 equally spaced floating-point values in [0, 1).
63    pub fn next_float(&mut self) -> f64 {
64        (self.next_bits() >> 11) as f64 / (1_u64 << 53) as f64
65    }
66
67    /// Samples a finite half-open interval, including adjacent float endpoints.
68    ///
69    /// Rounding is clamped below the upper endpoint; no overflowing endpoint
70    /// subtraction is performed.
71    ///
72    /// # Panics
73    /// Panics for an empty, reversed or nonfinite range; see [`Self::try_range`].
74    pub fn range(&mut self, range: Range<f64>) -> f64 {
75        self.try_range(range)
76            .unwrap_or_else(|error| panic!("{}", error.message))
77    }
78
79    /// Samples like [`Self::range`], reporting an invalid range without
80    /// advancing the stream.
81    pub fn try_range(&mut self, range: Range<f64>) -> Result<f64, crate::ValidationError> {
82        if !(range.start.is_finite() && range.end.is_finite() && range.start < range.end) {
83            return Err(crate::ValidationError::invalid(
84                "random",
85                "range",
86                "random range must have finite, strictly increasing endpoints",
87            ));
88        }
89        let progress = self.next_float();
90        let value = range.start * (1.0 - progress) + range.end * progress;
91        Ok(value.max(range.start).min(range.end.next_down()))
92    }
93
94    /// Samples a uniform angle using deterministic libm trigonometry.
95    pub fn unit_vector(&mut self) -> Vector2 {
96        let angle = self.next_float() * std::f64::consts::TAU;
97        Vector2::new(libm::cos(angle), libm::sin(angle))
98    }
99
100    /// Selects an element without modulo bias; an empty slice returns None.
101    pub fn choose<'a, Value>(&mut self, values: &'a [Value]) -> Option<&'a Value> {
102        if values.is_empty() {
103            return None;
104        }
105        let count = u64::try_from(values.len()).expect("slice length fits u64");
106        let threshold = count.wrapping_neg() % count;
107        loop {
108            let bits = self.next_bits();
109            if bits >= threshold {
110                return Some(&values[(bits % count) as usize]);
111            }
112        }
113    }
114}
115
116struct KeyHasher(u64);
117
118impl Hasher for KeyHasher {
119    fn finish(&self) -> u64 {
120        self.0
121    }
122
123    fn write(&mut self, bytes: &[u8]) {
124        for byte in bytes {
125            self.0 = (self.0 ^ u64::from(*byte)).wrapping_mul(0x100000001b3);
126        }
127    }
128
129    fn write_u8(&mut self, value: u8) {
130        self.write(&value.to_le_bytes());
131    }
132
133    fn write_u16(&mut self, value: u16) {
134        self.write(&value.to_le_bytes());
135    }
136
137    fn write_u32(&mut self, value: u32) {
138        self.write(&value.to_le_bytes());
139    }
140
141    fn write_u64(&mut self, value: u64) {
142        self.write(&value.to_le_bytes());
143    }
144
145    fn write_u128(&mut self, value: u128) {
146        self.write(&value.to_le_bytes());
147    }
148
149    fn write_usize(&mut self, value: usize) {
150        self.write_u64(value as u64);
151    }
152
153    fn write_i8(&mut self, value: i8) {
154        self.write(&value.to_le_bytes());
155    }
156
157    fn write_i16(&mut self, value: i16) {
158        self.write(&value.to_le_bytes());
159    }
160
161    fn write_i32(&mut self, value: i32) {
162        self.write(&value.to_le_bytes());
163    }
164
165    fn write_i64(&mut self, value: i64) {
166        self.write(&value.to_le_bytes());
167    }
168
169    fn write_i128(&mut self, value: i128) {
170        self.write(&value.to_le_bytes());
171    }
172
173    fn write_isize(&mut self, value: isize) {
174        self.write_i64(value as i64);
175    }
176}
177
178#[cfg(test)]
179mod tests {
180    use super::*;
181
182    #[test]
183    fn fixed_sequence_matches_independent_integer_reference() {
184        let mut random = Random::from_key(42_u64);
185        assert_eq!(random.state, 0xff3add6b3789daef);
186        for expected in [
187            0xa4e6579fd9ba8f6d,
188            0x14e9a1cc21726518,
189            0x29700e43bfeb9b12,
190            0xebc4f50c4cfbc8c4,
191        ] {
192            assert_eq!(random.next_bits(), expected);
193        }
194        let mut random = Random::from_key(42_u64);
195        assert_eq!(random.next_float(), 0.6441397443065658);
196        assert_eq!(
197            Random::from_key(42_usize).state,
198            Random::from_key(42_u64).state
199        );
200        assert_eq!(
201            Random::from_key(-42_isize).state,
202            Random::from_key(-42_i64).state
203        );
204    }
205
206    #[test]
207    fn equal_keys_and_cloned_streams_are_repeatable_without_global_state() {
208        let mut first = Random::from_key(("spark", 27_u32));
209        let mut same = first.clone();
210        let mut different = Random::from_key(("spark", 28_u32));
211        for _ in 0..1024 {
212            let value = first.next_float();
213            assert!((0.0..1.0).contains(&value));
214            assert_eq!(value, same.next_float());
215        }
216        assert_ne!(same.next_float(), different.next_float());
217        let expected = Random::from_key("parallel").next_float();
218        std::thread::scope(|scope| {
219            let handles: Vec<_> = (0..8)
220                .map(|_| scope.spawn(|| Random::from_key("parallel").next_float()))
221                .collect();
222            for handle in handles {
223                assert_eq!(handle.join().unwrap(), expected);
224            }
225        });
226    }
227
228    #[test]
229    fn ranges_vectors_and_choices_obey_their_domains() {
230        let mut random = Random::from_key("domains");
231        let ranges = [
232            -f64::MAX..f64::MAX,
233            f64::MAX.next_down()..f64::MAX,
234            -f64::MAX..(-f64::MAX).next_up(),
235            0.0..f64::from_bits(1),
236            -f64::from_bits(1)..0.0,
237            1.0..1.0_f64.next_up(),
238            -3.0..7.0,
239        ];
240        let choices = [2, 5, 9];
241        let mut seen = [false; 3];
242        for _ in 0..2048 {
243            for range in &ranges {
244                let value = random.range(range.clone());
245                assert!(range.contains(&value), "{range:?}: {value:?}");
246            }
247            let vector = random.unit_vector();
248            assert!((vector.x * vector.x + vector.y * vector.y - 1.0).abs() <= 4.0 * f64::EPSILON);
249            let choice = random.choose(&choices).unwrap();
250            seen[choices.iter().position(|value| value == choice).unwrap()] = true;
251        }
252        assert_eq!(seen, [true; 3]);
253        assert_eq!(random.choose::<u32>(&[]), None);
254        assert_eq!(random.choose(&[7]), Some(&7));
255    }
256
257    #[test]
258    fn invalid_ranges_fail_explicitly() {
259        for range in [
260            0.0..0.0,
261            2.0..1.0,
262            f64::NAN..1.0,
263            0.0..f64::INFINITY,
264            f64::NEG_INFINITY..0.0,
265        ] {
266            assert!(std::panic::catch_unwind(|| Random::from_key(0_u32).range(range)).is_err());
267        }
268    }
269}
motion_core/random.rs

motion_core/
random.rs
