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