oorandom/lib.rs
1//! A tiny, robust PRNG implementation.
2//!
3//! More specifically, it implements a single GOOD PRNG algorithm,
4//! which is currently a permuted congruential generator. It has two
5//! implementations, one that returns `u32` and one that returns
6//! `u64`. It also has functions that return floats or integer
7//! ranges. And that's it. What more do you need?
8//!
9//! For more info on PCG generators, see http://www.pcg-random.org/
10//!
11//! This was designed as a minimalist utility for video games. No
12//! promises are made about its quality, and if you use it for
13//! cryptography you will get what you deserve.
14//!
15//! Works with `#![no_std]`, has no global state, no dependencies
16//! apart from some in the unit tests, and is generally neato.
17
18#![forbid(unsafe_code)]
19#![forbid(missing_docs)]
20#![forbid(missing_debug_implementations)]
21#![forbid(unused_results)]
22#![no_std]
23use core::ops::Range;
24
25/// A PRNG producing a 32-bit output.
26///
27/// The current implementation is `PCG-XSH-RR`.
28#[derive(Copy, Clone, Debug, PartialEq)]
29pub struct Rand32 {
30 state: u64,
31 inc: u64,
32}
33
34impl Rand32 {
35 /// The default value for `increment`.
36 /// This is basically arbitrary, it comes from the
37 /// PCG reference C implementation:
38 /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L284
39 pub const DEFAULT_INC: u64 = 1442695040888963407;
40
41 /// This is the number that you have to Really Get Right.
42 ///
43 /// The value used here is from the PCG C implementation:
44 /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L278
45 pub(crate) const MULTIPLIER: u64 = 6364136223846793005;
46
47 /// Creates a new PRNG with the given seed and a default increment.
48 pub fn new(seed: u64) -> Self {
49 Self::new_inc(seed, Self::DEFAULT_INC)
50 }
51
52 /// Creates a new PRNG. The two inputs, `seed` and `increment`,
53 /// determine what you get; `increment` basically selects which
54 /// sequence of all those possible the PRNG will produce, and the
55 /// `seed` selects where in that sequence you start.
56 ///
57 /// Both are arbitrary; increment must be an odd number but this
58 /// handles that for you
59 pub fn new_inc(seed: u64, increment: u64) -> Self {
60 let mut rng = Self {
61 state: 0,
62 inc: increment.wrapping_shl(1) | 1,
63 };
64 // This initialization song-and-dance is a little odd,
65 // but seems to be just how things go.
66 let _ = rng.rand_u32();
67 rng.state = rng.state.wrapping_add(seed);
68 let _ = rng.rand_u32();
69 rng
70 }
71
72 /// Returns the internal state of the PRNG. This allows
73 /// you to save a PRNG and create a new one that will resume
74 /// from the same spot in the sequence.
75 pub fn state(&self) -> (u64, u64) {
76 (self.state, self.inc)
77 }
78
79 /// Creates a new PRNG from a saved state from `Rand32::state()`.
80 /// This is NOT quite the same as `new_inc()` because `new_inc()` does
81 /// a little extra setup work to initialize the state.
82 pub fn from_state(state: (u64, u64)) -> Self {
83 let (state, inc) = state;
84 Self { state, inc }
85 }
86
87 /// Produces a random `u32` in the range `[0, u32::MAX]`.
88 pub fn rand_u32(&mut self) -> u32 {
89 let oldstate: u64 = self.state;
90 self.state = oldstate
91 .wrapping_mul(Self::MULTIPLIER)
92 .wrapping_add(self.inc);
93 let xorshifted: u32 = (((oldstate >> 18) ^ oldstate) >> 27) as u32;
94 let rot: u32 = (oldstate >> 59) as u32;
95 xorshifted.rotate_right(rot)
96 }
97
98 /// Produces a random `i32` in the range `[i32::MIN, i32::MAX]`.
99 pub fn rand_i32(&mut self) -> i32 {
100 self.rand_u32() as i32
101 }
102
103 /// Produces a random `f32` in the range `[0.0, 1.0)`.
104 pub fn rand_float(&mut self) -> f32 {
105 // This impl was taken more or less from `rand`, see
106 // <https://docs.rs/rand/0.7.0/src/rand/distributions/float.rs.html#104-117>
107 // There MAY be better ways to do this, see:
108 // https://mumble.net/~campbell/2014/04/28/uniform-random-float
109 // https://mumble.net/~campbell/2014/04/28/random_real.c
110 // https://github.com/Lokathor/randomize/issues/34
111 const TOTAL_BITS: u32 = 32;
112 const PRECISION: u32 = core::f32::MANTISSA_DIGITS + 1;
113 const MANTISSA_SCALE: f32 = 1.0 / ((1u32 << PRECISION) as f32);
114 let mut u = self.rand_u32();
115 u >>= TOTAL_BITS - PRECISION;
116 u as f32 * MANTISSA_SCALE
117 }
118
119 /// Produces a random within the given bounds. Like any `Range`,
120 /// it includes the lower bound and excludes the upper one.
121 ///
122 /// This should be faster than `Self::rand() % end + start`, but the
123 /// real advantage is it's more convenient. Requires that
124 /// `range.end <= range.start`.
125 pub fn rand_range(&mut self, range: Range<u32>) -> u32 {
126 // This is harder to do well than it looks, it seems. I don't
127 // trust Lokathor's implementation 'cause I don't understand
128 // it, so I went to numpy's, which points me to "Lemire's
129 // rejection algorithm": http://arxiv.org/abs/1805.10941
130 //
131 // Algorithms 3, 4 and 5 in that paper all seem fine modulo
132 // minor performance differences, so this is algorithm 5.
133 // It uses numpy's implementation, `buffered_bounded_lemire_uint32()`
134
135 debug_assert!(range.start < range.end);
136 let range_starting_from_zero = 0..(range.end - range.start);
137
138 let s: u32 = range_starting_from_zero.end;
139 let mut m: u64 = u64::from(self.rand_u32()) * u64::from(s);
140 let mut leftover: u32 = (m & 0xFFFF_FFFF) as u32;
141
142 if leftover < s {
143 // TODO: verify the wrapping_neg() here
144 let threshold: u32 = s.wrapping_neg() % s;
145 while leftover < threshold {
146 m = u64::from(self.rand_u32()).wrapping_mul(u64::from(s));
147 leftover = (m & 0xFFFF_FFFF) as u32;
148 }
149 }
150 (m >> 32) as u32 + range.start
151 }
152}
153
154/// A PRNG producing a 64-bit output.
155///
156/// The current implementation is `PCG-XSH-RR`.
157// BUGGO: The recommended algorithm is PCG-XSL-RR?
158// See https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2405
159// Not sure if it matters?
160#[derive(Copy, Clone, Debug, PartialEq)]
161pub struct Rand64 {
162 state: u128,
163 inc: u128,
164}
165
166impl Rand64 {
167 /// The default value for `increment`.
168 ///
169 /// The value used here is from the PCG default C implementation: http://www.pcg-random.org/download.html
170 pub const DEFAULT_INC: u128 = 0x2FE0E169_FFBD06E3_5BC307BD_4D2F814F;
171
172 /// This is the number that you have to Really Get Right.
173 ///
174 /// The value used here is from the PCG C implementation:
175 /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L288
176 pub(crate) const MULTIPLIER: u128 = 47026247687942121848144207491837523525;
177
178 /// Creates a new PRNG with the given seed and a default increment.
179 pub fn new(seed: u128) -> Self {
180 Self::new_inc(seed, Self::DEFAULT_INC)
181 }
182
183 /// Same as `Rand32::new_inc()`
184 fn new_inc(seed: u128, increment: u128) -> Self {
185 let mut rng = Self {
186 state: 0,
187 inc: increment.wrapping_shl(1) | 1,
188 };
189 let _ = rng.rand_u64();
190 rng.state = rng.state.wrapping_add(seed);
191 let _ = rng.rand_u64();
192 rng
193 }
194
195 /// Returns the internal state of the PRNG. This allows
196 /// you to save a PRNG and create a new one that will resume
197 /// from the same spot in the sequence.
198 pub fn state(&self) -> (u128, u128) {
199 (self.state, self.inc)
200 }
201
202 /// Creates a new PRNG from a saved state from `Rand32::state()`.
203 /// This is NOT quite the same as `new_inc()` because `new_inc()` does
204 /// a little extra setup work to initialize the state.
205 pub fn from_state(state: (u128, u128)) -> Self {
206 let (state, inc) = state;
207 Self { state, inc }
208 }
209
210 /// Produces a random `u64` in the range`[0, u64::MAX]`.
211 pub fn rand_u64(&mut self) -> u64 {
212 let oldstate: u128 = self.state;
213 self.state = oldstate
214 .wrapping_mul(Self::MULTIPLIER)
215 .wrapping_add(self.inc);
216 let xorshifted: u64 = (((oldstate >> 29) ^ oldstate) >> 58) as u64;
217 let rot: u32 = (oldstate >> 122) as u32;
218 xorshifted.rotate_right(rot)
219 }
220
221 /// Produces a random `i64` in the range `[i64::MIN, i64::MAX]`.
222 pub fn rand_i64(&mut self) -> i64 {
223 self.rand_u64() as i64
224 }
225
226 /// Produces a random `f64` in the range `[0.0, 1.0)`.
227 pub fn rand_float(&mut self) -> f64 {
228 const TOTAL_BITS: u32 = 64;
229 const PRECISION: u32 = core::f64::MANTISSA_DIGITS + 1;
230 const MANTISSA_SCALE: f64 = 1.0 / ((1u64 << PRECISION) as f64);
231 let mut u = self.rand_u64();
232 u >>= TOTAL_BITS - PRECISION;
233 u as f64 * MANTISSA_SCALE
234 }
235
236 /// Produces a random within the given bounds. Like any `Range`,
237 /// it includes the lower bound and excludes the upper one.
238 ///
239 /// This should be faster than `Self::rand() % end + start`, but the
240 /// real advantage is it's more convenient. Requires that
241 /// `range.end <= range.start`.
242 pub fn rand_range(&mut self, range: Range<u64>) -> u64 {
243 // Same as `Rand32::rand_range()`
244 debug_assert!(range.start < range.end);
245 let range_starting_from_zero = 0..(range.end - range.start);
246
247 let s: u64 = range_starting_from_zero.end;
248 let mut m: u128 = u128::from(self.rand_u64()) * u128::from(s);
249 let mut leftover: u64 = (m & 0xFFFFFFFF_FFFFFFFF) as u64;
250
251 if leftover < s {
252 // TODO: Verify the wrapping_negate() here
253 let threshold: u64 = s.wrapping_neg() % s;
254 while leftover < threshold {
255 m = u128::from(self.rand_u64()) * u128::from(s);
256 leftover = (m & 0xFFFFFFFF_FFFFFFFF) as u64;
257 }
258 }
259 (m.wrapping_shr(64)) as u64
260 }
261}
262
263#[cfg(test)]
264mod tests {
265 use super::*;
266 use randomize::{self, PCG32, PCG64};
267
268 #[test]
269 fn test_rand32_vs_randomize() {
270 // Generate some random numbers and validate them against
271 // a known-good generator.
272 {
273 let seed = 54321;
274 let mut r1 = Rand32::new(seed);
275 let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
276 for _ in 0..1000 {
277 assert_eq!(r1.rand_u32(), r2.next_u32());
278 }
279 }
280
281 {
282 let seed = 3141592653;
283 let inc = 0xDEADBEEF;
284 let mut r1 = Rand32::new_inc(seed, inc);
285 let mut r2 = PCG32::seed(seed, inc);
286 for _ in 0..1000 {
287 assert_eq!(r1.rand_u32(), r2.next_u32());
288 }
289 }
290 }
291
292 #[test]
293 fn test_rand64_vs_randomize() {
294 // Generate some random numbers and validate them against
295 // a known-good generator.
296 {
297 let seed = 54321;
298 let mut r1 = Rand64::new(seed);
299 let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
300 for _ in 0..1000 {
301 assert_eq!(r1.rand_u64(), r2.next_u64());
302 }
303 }
304
305 {
306 let seed = 3141592653;
307 let inc = 0xDEADBEEF;
308 let mut r1 = Rand64::new_inc(seed, inc);
309 let mut r2 = PCG64::seed(seed, inc);
310 for _ in 0..1000 {
311 assert_eq!(r1.rand_u64(), r2.next_u64());
312 }
313 }
314 }
315
316 #[test]
317 fn test_float32() {
318 {
319 let seed = 2718281828;
320 let mut r1 = Rand32::new(seed);
321 let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
322 for _ in 0..1000 {
323 // First just make sure they both work with randomize's
324 // f32 conversion function -- sanity checks.
325 let i1 = r1.rand_u32();
326 let i2 = r2.next_u32();
327 assert_eq!(i1, i2);
328 let f1 = randomize::f32_half_open_right(i1);
329 let f2 = randomize::f32_half_open_right(i2);
330 // We can directly compare floats 'cause we do no math, it's
331 // literally the same bitwise algorithm with the same inputs.
332 assert_eq!(f1, f2);
333
334 // Make sure result is in [0.0, 1.0)
335 assert!(f1 >= 0.0);
336 assert!(f1 < 1.0);
337 }
338
339 /*
340 TODO: Randomize changed its int-to-float conversion functions and now they don't
341 match ours.
342 for _ in 0..1000 {
343 // Now make sure our own float conversion function works.
344 let f1 = r1.rand_float();
345 //let f2 = randomize::f32_half_open_right(r2.next_u32());
346 let f2 = randomize::f32_open(r2.next_u32());
347 assert_eq!(f1, f2);
348 assert!(f1 >= 0.0);
349 assert!(f1 < 1.0);
350 }
351 */
352 }
353 }
354
355 #[test]
356 fn test_float64() {
357 {
358 let seed = 2718281828;
359 let mut r1 = Rand64::new(seed);
360 let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
361 for _ in 0..1000 {
362 // First just make sure they both work with randomize's
363 // f64 conversion function -- sanity checks.
364 let i1 = r1.rand_u64();
365 let i2 = r2.next_u64();
366 assert_eq!(i1, i2);
367 let f1 = randomize::f64_half_open_right(i1);
368 let f2 = randomize::f64_half_open_right(i2);
369 // We can directly compare floats 'cause we do no math, it's
370 // literally the same bitwise algorithm with the same inputs.
371 assert_eq!(f1, f2);
372
373 // Make sure result is in [0.0, 1.0)
374 assert!(f1 >= 0.0);
375 assert!(f1 < 1.0);
376 }
377
378 /*
379 TODO: Randomize changed its int-to-float conversion functions and now they don't
380 match ours.
381 for _ in 0..1000 {
382 // Now make sure our own float conversion function works.
383 let f1 = r1.rand_float();
384 //let f2 = randomize::f32_half_open_right(r2.next_u32());
385 let f2 = randomize::f32_open(r2.next_u32());
386 assert_eq!(f1, f2);
387 assert!(f1 >= 0.0);
388 assert!(f1 < 1.0);
389 }
390 */
391 }
392 }
393
394 #[test]
395 fn test_randrange() {
396 // Make sure ranges are valid and in the given range
397 let seed = 2342_4223;
398 let mut r1 = Rand32::new(seed);
399 for _ in 0..1000 {
400 // Generate our bounds at random
401 let a = r1.rand_u32();
402 let b = r1.rand_u32();
403 if a == b {
404 continue;
405 }
406 let (low, high) = if a < b { (a, b) } else { (b, a) };
407
408 // Get a number in that range
409 let in_range = r1.rand_range(low..high);
410 assert!(in_range >= low);
411 assert!(in_range < high);
412 }
413 }
414
415 #[test]
416 fn test_rand32_vs_rand() {
417 use rand_core::RngCore;
418 use rand_pcg;
419 {
420 let seed = 54321;
421 let mut r1 = Rand32::new(seed);
422 let mut r2 = rand_pcg::Pcg32::new(seed, Rand32::DEFAULT_INC);
423 for _ in 0..1000 {
424 assert_eq!(r1.rand_u32(), r2.next_u32());
425 }
426 }
427
428 {
429 let seed = 3141592653;
430 let inc = 0xDEADBEEF;
431 let mut r1 = Rand32::new_inc(seed, inc);
432 let mut r2 = rand_pcg::Pcg32::new(seed, inc);
433 for _ in 0..1000 {
434 assert_eq!(r1.rand_u32(), r2.next_u32());
435 }
436 }
437 }
438
439 // This doesn't work 'cause for 64-bit output `rand` uses
440 // PCG-XSL-RR
441 // and we use
442 // PCG-XSH-RR
443 /*
444 #[test]
445 fn test_rand64_vs_rand() {
446 use rand_pcg;
447 use rand_core::RngCore;
448 {
449 let seed = 54321;
450 let mut r1 = Rand64::new(seed);
451 let mut r2 = rand_pcg::Pcg64::new(seed, Rand64::DEFAULT_INC);
452 for _ in 0..1000 {
453 assert_eq!(r1.rand(), r2.next_u64());
454 }
455 }
456
457 {
458 let seed = 3141592653;
459 let inc = 0xDEADBEEF;
460 let mut r1 = Rand64::new_inc(seed, inc);
461 let mut r2 = rand_pcg::Pcg64::new(seed, inc);
462 for _ in 0..1000 {
463 assert_eq!(r1.rand(), r2.next_u64());
464 }
465 }
466 }
467 */
468
469 // Test vs. random-fast-rng, which I will call rfr
470 // rfr's float conversion uses yet a different algorithm
471 // than ours, so we can't really check that.
472 #[test]
473 fn test_rand32_vs_rfr() {
474 use random_fast_rng as rfr;
475 use rfr::Random;
476 {
477 let seed = 54321;
478 let mut r1 = Rand32::new(seed);
479 let mut r2 = rfr::FastRng::seed(seed, Rand32::DEFAULT_INC);
480 for _ in 0..1000 {
481 assert_eq!(r1.rand_u32(), r2.get_u32());
482 }
483 }
484
485 {
486 let seed = 3141592653;
487 let inc = 0xDEADBEEF;
488 let mut r1 = Rand32::new_inc(seed, inc);
489 let mut r2 = rfr::FastRng::seed(seed, inc);
490 for _ in 0..1000 {
491 assert_eq!(r1.rand_u32(), r2.get_u32());
492 }
493 }
494 }
495
496 /// Make sure that saving a RNG state and restoring
497 /// it works.
498 /// See https://todo.sr.ht/~icefox/oorandom/1
499 #[test]
500 fn test_save_restore() {
501 {
502 let seed = 54321;
503 let mut r1 = Rand32::new(seed);
504 let s1 = r1.state();
505 let mut r2 = Rand32::from_state(s1);
506 assert_eq!(r1, r2);
507 for _ in 0..1000 {
508 assert_eq!(r1.rand_u32(), r2.rand_u32());
509 }
510 }
511
512 {
513 let seed = 3141592653;
514 let inc = 0xDEADBEEF;
515 let mut r1 = Rand32::new_inc(seed, inc);
516 let s1 = r1.state();
517 let mut r2 = Rand32::from_state(s1);
518 assert_eq!(r1, r2);
519 for _ in 0..1000 {
520 assert_eq!(r1.rand_u32(), r2.rand_u32());
521 }
522 }
523
524 {
525 let seed = 54321;
526 let mut r1 = Rand64::new(seed);
527 let s1 = r1.state();
528 let mut r2 = Rand64::from_state(s1);
529 assert_eq!(r1, r2);
530 for _ in 0..1000 {
531 assert_eq!(r1.rand_u64(), r2.rand_u64());
532 }
533 }
534
535 {
536 let seed = 3141592653;
537 let inc = 0xDEADBEEF;
538 let mut r1 = Rand64::new_inc(seed, inc);
539 let s1 = r1.state();
540 let mut r2 = Rand64::from_state(s1);
541 assert_eq!(r1, r2);
542 for _ in 0..1000 {
543 assert_eq!(r1.rand_u64(), r2.rand_u64());
544 }
545 }
546 }
547}