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 pub 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 + range.start
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 assert_eq!(r1.rand_i32(), r2.next_u32() as i32);
279 }
280 }
281
282 {
283 let seed = 3141592653;
284 let inc = 0xDEADBEEF;
285 let mut r1 = Rand32::new_inc(seed, inc);
286 let mut r2 = PCG32::seed(seed, inc);
287 for _ in 0..1000 {
288 assert_eq!(r1.rand_u32(), r2.next_u32());
289 assert_eq!(r1.rand_i32(), r2.next_u32() as i32);
290 }
291 }
292 }
293
294 #[test]
295 fn test_rand64_vs_randomize() {
296 // Generate some random numbers and validate them against
297 // a known-good generator.
298 {
299 let seed = 54321;
300 let mut r1 = Rand64::new(seed);
301 let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
302 for _ in 0..1000 {
303 assert_eq!(r1.rand_u64(), r2.next_u64());
304 assert_eq!(r1.rand_i64(), r2.next_u64() as i64);
305 }
306 }
307
308 {
309 let seed = 3141592653;
310 let inc = 0xDEADBEEF;
311 let mut r1 = Rand64::new_inc(seed, inc);
312 let mut r2 = PCG64::seed(seed, inc);
313 for _ in 0..1000 {
314 assert_eq!(r1.rand_u64(), r2.next_u64());
315 assert_eq!(r1.rand_i64(), r2.next_u64() as i64);
316 }
317 }
318 }
319
320 #[test]
321 fn test_float32() {
322 {
323 let seed = 2718281828;
324 let mut r1 = Rand32::new(seed);
325 let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
326 for _ in 0..1000 {
327 // First just make sure they both work with randomize's
328 // f32 conversion function -- sanity checks.
329 let i1 = r1.rand_u32();
330 let i2 = r2.next_u32();
331 assert_eq!(i1, i2);
332 let f1 = randomize::f32_half_open_right(i1);
333 let f2 = randomize::f32_half_open_right(i2);
334 // We can directly compare floats 'cause we do no math, it's
335 // literally the same bitwise algorithm with the same inputs.
336 assert_eq!(f1, f2);
337
338 // Make sure result is in [0.0, 1.0)
339 assert!(f1 >= 0.0);
340 assert!(f1 < 1.0);
341 }
342
343 // At least make sure our float's from rand_float() are in the valid range.
344 for _ in 0..1000 {
345 let f1 = r1.rand_float();
346 assert!(f1 >= 0.0);
347 assert!(f1 < 1.0);
348 }
349
350 /*
351 TODO: Randomize changed its int-to-float conversion functions and now they don't
352 match ours.
353 for _ in 0..1000 {
354 // Now make sure our own float conversion function works.
355 let f1 = r1.rand_float();
356 //let f2 = randomize::f32_half_open_right(r2.next_u32());
357 let f2 = randomize::f32_open(r2.next_u32());
358 assert_eq!(f1, f2);
359 assert!(f1 >= 0.0);
360 assert!(f1 < 1.0);
361 }
362 */
363 }
364 }
365
366 #[test]
367 fn test_float64() {
368 {
369 let seed = 2718281828;
370 let mut r1 = Rand64::new(seed);
371 let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
372 for _ in 0..1000 {
373 // First just make sure they both work with randomize's
374 // f64 conversion function -- sanity checks.
375 let i1 = r1.rand_u64();
376 let i2 = r2.next_u64();
377 assert_eq!(i1, i2);
378 let f1 = randomize::f64_half_open_right(i1);
379 let f2 = randomize::f64_half_open_right(i2);
380 // We can directly compare floats 'cause we do no math, it's
381 // literally the same bitwise algorithm with the same inputs.
382 assert_eq!(f1, f2);
383
384 // Make sure result is in [0.0, 1.0)
385 assert!(f1 >= 0.0);
386 assert!(f1 < 1.0);
387 }
388
389 // At least make sure our float's from rand_float() are in the valid range.
390 for _ in 0..1000 {
391 let f1 = r1.rand_float();
392 assert!(f1 >= 0.0);
393 assert!(f1 < 1.0);
394 }
395
396 /*
397 TODO: Randomize changed its int-to-float conversion functions and now they don't
398 match ours.
399 for _ in 0..1000 {
400 // Now make sure our own float conversion function works.
401 let f1 = r1.rand_float();
402 //let f2 = randomize::f32_half_open_right(r2.next_u32());
403 let f2 = randomize::f32_open(r2.next_u32());
404 assert_eq!(f1, f2);
405 assert!(f1 >= 0.0);
406 assert!(f1 < 1.0);
407 }
408 */
409 }
410 }
411
412 #[test]
413 fn test_randrange32() {
414 // Make sure ranges are valid and in the given range
415 let seed = 2342_3141;
416 let mut r1 = Rand32::new(seed);
417 for _ in 0..1000 {
418 // Generate our bounds at random
419 let a = r1.rand_u32();
420 let b = r1.rand_u32();
421 if a == b {
422 continue;
423 }
424 let (low, high) = if a < b { (a, b) } else { (b, a) };
425
426 // Get a number in that range
427 let in_range = r1.rand_range(low..high);
428 assert!(in_range >= low);
429 assert!(in_range < high);
430 }
431 }
432
433 #[test]
434 fn test_randrange64() {
435 // Make sure ranges are valid and in the given range
436 let seed = 2342_2718;
437 let mut r1 = Rand64::new(seed);
438 for _ in 0..1000 {
439 // Generate our bounds at random
440 let a = r1.rand_u64();
441 let b = r1.rand_u64();
442 if a == b {
443 continue;
444 }
445 let (low, high) = if a < b { (a, b) } else { (b, a) };
446
447 // Get a number in that range
448 let in_range = r1.rand_range(low..high);
449 assert!(in_range >= low);
450 assert!(in_range < high);
451 }
452 }
453
454 #[test]
455 fn test_rand32_vs_rand() {
456 use rand_core::RngCore;
457 use rand_pcg;
458 {
459 let seed = 54321;
460 let mut r1 = Rand32::new(seed);
461 let mut r2 = rand_pcg::Pcg32::new(seed, Rand32::DEFAULT_INC);
462 for _ in 0..1000 {
463 assert_eq!(r1.rand_u32(), r2.next_u32());
464 }
465 }
466
467 {
468 let seed = 3141592653;
469 let inc = 0xDEADBEEF;
470 let mut r1 = Rand32::new_inc(seed, inc);
471 let mut r2 = rand_pcg::Pcg32::new(seed, inc);
472 for _ in 0..1000 {
473 assert_eq!(r1.rand_u32(), r2.next_u32());
474 }
475 }
476 }
477
478 // This doesn't work 'cause for 64-bit output `rand` uses
479 // PCG-XSL-RR
480 // and we use
481 // PCG-XSH-RR
482 /*
483 #[test]
484 fn test_rand64_vs_rand() {
485 use rand_pcg;
486 use rand_core::RngCore;
487 {
488 let seed = 54321;
489 let mut r1 = Rand64::new(seed);
490 let mut r2 = rand_pcg::Pcg64::new(seed, Rand64::DEFAULT_INC);
491 for _ in 0..1000 {
492 assert_eq!(r1.rand(), r2.next_u64());
493 }
494 }
495
496 {
497 let seed = 3141592653;
498 let inc = 0xDEADBEEF;
499 let mut r1 = Rand64::new_inc(seed, inc);
500 let mut r2 = rand_pcg::Pcg64::new(seed, inc);
501 for _ in 0..1000 {
502 assert_eq!(r1.rand(), r2.next_u64());
503 }
504 }
505 }
506 */
507
508 // Test vs. random-fast-rng, which I will call rfr
509 // rfr's float conversion uses yet a different algorithm
510 // than ours, so we can't really check that.
511 #[test]
512 fn test_rand32_vs_rfr() {
513 use random_fast_rng as rfr;
514 use rfr::Random;
515 {
516 let seed = 54321;
517 let mut r1 = Rand32::new(seed);
518 let mut r2 = rfr::FastRng::seed(seed, Rand32::DEFAULT_INC);
519 for _ in 0..1000 {
520 assert_eq!(r1.rand_u32(), r2.get_u32());
521 }
522 }
523
524 {
525 let seed = 3141592653;
526 let inc = 0xDEADBEEF;
527 let mut r1 = Rand32::new_inc(seed, inc);
528 let mut r2 = rfr::FastRng::seed(seed, inc);
529 for _ in 0..1000 {
530 assert_eq!(r1.rand_u32(), r2.get_u32());
531 }
532 }
533 }
534
535 /// Make sure that saving a RNG state and restoring
536 /// it works.
537 /// See https://todo.sr.ht/~icefox/oorandom/1
538 #[test]
539 fn test_save_restore() {
540 {
541 let seed = 54321;
542 let mut r1 = Rand32::new(seed);
543 let s1 = r1.state();
544 let mut r2 = Rand32::from_state(s1);
545 assert_eq!(r1, r2);
546 for _ in 0..1000 {
547 assert_eq!(r1.rand_u32(), r2.rand_u32());
548 }
549 }
550
551 {
552 let seed = 3141592653;
553 let inc = 0xDEADBEEF;
554 let mut r1 = Rand32::new_inc(seed, inc);
555 let s1 = r1.state();
556 let mut r2 = Rand32::from_state(s1);
557 assert_eq!(r1, r2);
558 for _ in 0..1000 {
559 assert_eq!(r1.rand_u32(), r2.rand_u32());
560 }
561 }
562
563 {
564 let seed = 54321;
565 let mut r1 = Rand64::new(seed);
566 let s1 = r1.state();
567 let mut r2 = Rand64::from_state(s1);
568 assert_eq!(r1, r2);
569 for _ in 0..1000 {
570 assert_eq!(r1.rand_u64(), r2.rand_u64());
571 }
572 }
573
574 {
575 let seed = 3141592653;
576 let inc = 0xDEADBEEF;
577 let mut r1 = Rand64::new_inc(seed, inc);
578 let s1 = r1.state();
579 let mut r2 = Rand64::from_state(s1);
580 assert_eq!(r1, r2);
581 for _ in 0..1000 {
582 assert_eq!(r1.rand_u64(), r2.rand_u64());
583 }
584 }
585 }
586}
587