src/lib.rs - platform/external/rust/crates/oorandom - Git at Google

 //! A tiny, robust PRNG implementation.
 //!
 //! More specifically, it implements a single GOOD PRNG algorithm,
 //! which is currently a permuted congruential generator.  It has two
 //! implementations, one that returns `u32` and one that returns
 //! `u64`.  It also has functions that return floats or integer
 //! ranges.  And that's it.  What more do you need?
 //!
 //! For more info on PCG generators, see http://www.pcg-random.org/
 //!
 //! This was designed as a minimalist utility for video games.  No
 //! promises are made about its quality, and if you use it for
 //! cryptography you will get what you deserve.
 //!
 //! Works with `#![no_std]`, has no global state, no dependencies
 //! apart from some in the unit tests, and is generally neato.

 #![forbid(unsafe_code)]
 #![forbid(missing_docs)]
 #![forbid(missing_debug_implementations)]
 #![forbid(unused_results)]
 #![no_std]
 use core::ops::Range;

 /// A PRNG producing a 32-bit output.
 ///
 /// The current implementation is `PCG-XSH-RR`.
 #[derive(Copy, Clone, Debug, PartialEq)]
 pub struct Rand32 {
     state: u64,
     inc: u64,
 }

 impl Rand32 {
     /// The default value for `increment`.
     /// This is basically arbitrary, it comes from the
     /// PCG reference C implementation:
     /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L284
     pub const DEFAULT_INC: u64 = 1442695040888963407;

     /// This is the number that you have to Really Get Right.
     ///
     /// The value used here is from the PCG C implementation:
     /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L278
     pub(crate) const MULTIPLIER: u64 = 6364136223846793005;

     /// Creates a new PRNG with the given seed and a default increment.
     pub fn new(seed: u64) -> Self {
         Self::new_inc(seed, Self::DEFAULT_INC)
     }

     /// Creates a new PRNG.  The two inputs, `seed` and `increment`,
     /// determine what you get; `increment` basically selects which
     /// sequence of all those possible the PRNG will produce, and the
     /// `seed` selects where in that sequence you start.
     ///
     /// Both are arbitrary; increment must be an odd number but this
     /// handles that for you
     pub fn new_inc(seed: u64, increment: u64) -> Self {
         let mut rng = Self {
             state: 0,
             inc: increment.wrapping_shl(1) | 1,
         };
         // This initialization song-and-dance is a little odd,
         // but seems to be just how things go.
         let _ = rng.rand_u32();
         rng.state = rng.state.wrapping_add(seed);
         let _ = rng.rand_u32();
         rng
     }

     /// Returns the internal state of the PRNG.  This allows
     /// you to save a PRNG and create a new one that will resume
     /// from the same spot in the sequence.
     pub fn state(&self) -> (u64, u64) {
         (self.state, self.inc)
     }

     /// Creates a new PRNG from a saved state from `Rand32::state()`.
     /// This is NOT quite the same as `new_inc()` because `new_inc()` does
     /// a little extra setup work to initialize the state.
     pub fn from_state(state: (u64, u64)) -> Self {
         let (state, inc) = state;
         Self { state, inc }
     }

     /// Produces a random `u32` in the range `[0, u32::MAX]`.
     pub fn rand_u32(&mut self) -> u32 {
         let oldstate: u64 = self.state;
         self.state = oldstate
             .wrapping_mul(Self::MULTIPLIER)
             .wrapping_add(self.inc);
         let xorshifted: u32 = (((oldstate >> 18) ^ oldstate) >> 27) as u32;
         let rot: u32 = (oldstate >> 59) as u32;
         xorshifted.rotate_right(rot)
     }

     /// Produces a random `i32` in the range `[i32::MIN, i32::MAX]`.
     pub fn rand_i32(&mut self) -> i32 {
         self.rand_u32() as i32
     }

     /// Produces a random `f32` in the range `[0.0, 1.0)`.
     pub fn rand_float(&mut self) -> f32 {
         // This impl was taken more or less from `rand`, see
         // <https://docs.rs/rand/0.7.0/src/rand/distributions/float.rs.html#104-117>
         // There MAY be better ways to do this, see:
         // https://mumble.net/~campbell/2014/04/28/uniform-random-float
         // https://mumble.net/~campbell/2014/04/28/random_real.c
         // https://github.com/Lokathor/randomize/issues/34
         const TOTAL_BITS: u32 = 32;
         const PRECISION: u32 = core::f32::MANTISSA_DIGITS + 1;
         const MANTISSA_SCALE: f32 = 1.0 / ((1u32 << PRECISION) as f32);
         let mut u = self.rand_u32();
         u >>= TOTAL_BITS - PRECISION;
         u as f32 * MANTISSA_SCALE
     }

     /// Produces a random within the given bounds.  Like any `Range`,
     /// it includes the lower bound and excludes the upper one.
     ///
     /// This should be faster than `Self::rand() % end + start`, but the
     /// real advantage is it's more convenient.  Requires that
     /// `range.end <= range.start`.
     pub fn rand_range(&mut self, range: Range<u32>) -> u32 {
         // This is harder to do well than it looks, it seems.  I don't
         // trust Lokathor's implementation 'cause I don't understand
         // it, so I went to numpy's, which points me to "Lemire's
         // rejection algorithm": http://arxiv.org/abs/1805.10941
         //
         // Algorithms 3, 4 and 5 in that paper all seem fine modulo
         // minor performance differences, so this is algorithm 5.
         // It uses numpy's implementation, `buffered_bounded_lemire_uint32()`

         debug_assert!(range.start < range.end);
         let range_starting_from_zero = 0..(range.end - range.start);

         let s: u32 = range_starting_from_zero.end;
         let mut m: u64 = u64::from(self.rand_u32()) * u64::from(s);
         let mut leftover: u32 = (m & 0xFFFF_FFFF) as u32;

         if leftover < s {
             // TODO: verify the wrapping_neg() here
             let threshold: u32 = s.wrapping_neg() % s;
             while leftover < threshold {
                 m = u64::from(self.rand_u32()).wrapping_mul(u64::from(s));
                 leftover = (m & 0xFFFF_FFFF) as u32;
             }
         }
         (m >> 32) as u32 + range.start
     }
 }

 /// A PRNG producing a 64-bit output.
 ///
 /// The current implementation is `PCG-XSH-RR`.
 // BUGGO: The recommended algorithm is PCG-XSL-RR?
 // See https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2405
 // Not sure if it matters?
 #[derive(Copy, Clone, Debug, PartialEq)]
 pub struct Rand64 {
     state: u128,
     inc: u128,
 }

 impl Rand64 {
     /// The default value for `increment`.
     ///
     /// The value used here is from the PCG default C implementation: http://www.pcg-random.org/download.html
     pub const DEFAULT_INC: u128 = 0x2FE0E169_FFBD06E3_5BC307BD_4D2F814F;

     /// This is the number that you have to Really Get Right.
     ///
     /// The value used here is from the PCG C implementation:
     /// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L288
     pub(crate) const MULTIPLIER: u128 = 47026247687942121848144207491837523525;

     /// Creates a new PRNG with the given seed and a default increment.
     pub fn new(seed: u128) -> Self {
         Self::new_inc(seed, Self::DEFAULT_INC)
     }

     /// Same as `Rand32::new_inc()`
     pub fn new_inc(seed: u128, increment: u128) -> Self {
         let mut rng = Self {
             state: 0,
             inc: increment.wrapping_shl(1) | 1,
         };
         let _ = rng.rand_u64();
         rng.state = rng.state.wrapping_add(seed);
         let _ = rng.rand_u64();
         rng
     }

     /// Returns the internal state of the PRNG.  This allows
     /// you to save a PRNG and create a new one that will resume
     /// from the same spot in the sequence.
     pub fn state(&self) -> (u128, u128) {
         (self.state, self.inc)
     }

     /// Creates a new PRNG from a saved state from `Rand32::state()`.
     /// This is NOT quite the same as `new_inc()` because `new_inc()` does
     /// a little extra setup work to initialize the state.
     pub fn from_state(state: (u128, u128)) -> Self {
         let (state, inc) = state;
         Self { state, inc }
     }

     /// Produces a random `u64` in the range`[0, u64::MAX]`.
     pub fn rand_u64(&mut self) -> u64 {
         let oldstate: u128 = self.state;
         self.state = oldstate
             .wrapping_mul(Self::MULTIPLIER)
             .wrapping_add(self.inc);
         let xorshifted: u64 = (((oldstate >> 29) ^ oldstate) >> 58) as u64;
         let rot: u32 = (oldstate >> 122) as u32;
         xorshifted.rotate_right(rot)
     }

     /// Produces a random `i64` in the range `[i64::MIN, i64::MAX]`.
     pub fn rand_i64(&mut self) -> i64 {
         self.rand_u64() as i64
     }

     /// Produces a random `f64` in the range `[0.0, 1.0)`.
     pub fn rand_float(&mut self) -> f64 {
         const TOTAL_BITS: u32 = 64;
         const PRECISION: u32 = core::f64::MANTISSA_DIGITS + 1;
         const MANTISSA_SCALE: f64 = 1.0 / ((1u64 << PRECISION) as f64);
         let mut u = self.rand_u64();
         u >>= TOTAL_BITS - PRECISION;
         u as f64 * MANTISSA_SCALE
     }

     /// Produces a random within the given bounds.  Like any `Range`,
     /// it includes the lower bound and excludes the upper one.
     ///
     /// This should be faster than `Self::rand() % end + start`, but the
     /// real advantage is it's more convenient.  Requires that
     /// `range.end <= range.start`.
     pub fn rand_range(&mut self, range: Range<u64>) -> u64 {
         // Same as `Rand32::rand_range()`
         debug_assert!(range.start < range.end);
         let range_starting_from_zero = 0..(range.end - range.start);

         let s: u64 = range_starting_from_zero.end;
         let mut m: u128 = u128::from(self.rand_u64()) * u128::from(s);
         let mut leftover: u64 = (m & 0xFFFFFFFF_FFFFFFFF) as u64;

         if leftover < s {
             // TODO: Verify the wrapping_negate() here
             let threshold: u64 = s.wrapping_neg() % s;
             while leftover < threshold {
                 m = u128::from(self.rand_u64()) * u128::from(s);
                 leftover = (m & 0xFFFFFFFF_FFFFFFFF) as u64;
             }
         }
         (m.wrapping_shr(64)) as u64 + range.start
     }
 }

 #[cfg(test)]
 mod tests {
     use super::*;
     use randomize::{self, PCG32, PCG64};

     #[test]
     fn test_rand32_vs_randomize() {
         // Generate some random numbers and validate them against
         // a known-good generator.
         {
             let seed = 54321;
             let mut r1 = Rand32::new(seed);
             let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.next_u32());
                 assert_eq!(r1.rand_i32(), r2.next_u32() as i32);
             }
         }

         {
             let seed = 3141592653;
             let inc = 0xDEADBEEF;
             let mut r1 = Rand32::new_inc(seed, inc);
             let mut r2 = PCG32::seed(seed, inc);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.next_u32());
                 assert_eq!(r1.rand_i32(), r2.next_u32() as i32);
             }
         }
     }

     #[test]
     fn test_rand64_vs_randomize() {
         // Generate some random numbers and validate them against
         // a known-good generator.
         {
             let seed = 54321;
             let mut r1 = Rand64::new(seed);
             let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u64(), r2.next_u64());
                 assert_eq!(r1.rand_i64(), r2.next_u64() as i64);
             }
         }

         {
             let seed = 3141592653;
             let inc = 0xDEADBEEF;
             let mut r1 = Rand64::new_inc(seed, inc);
             let mut r2 = PCG64::seed(seed, inc);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u64(), r2.next_u64());
                 assert_eq!(r1.rand_i64(), r2.next_u64() as i64);
             }
         }
     }

     #[test]
     fn test_float32() {
         {
             let seed = 2718281828;
             let mut r1 = Rand32::new(seed);
             let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
             for _ in 0..1000 {
                 // First just make sure they both work with randomize's
                 // f32 conversion function -- sanity checks.
                 let i1 = r1.rand_u32();
                 let i2 = r2.next_u32();
                 assert_eq!(i1, i2);
                 let f1 = randomize::f32_half_open_right(i1);
                 let f2 = randomize::f32_half_open_right(i2);
                 // We can directly compare floats 'cause we do no math, it's
                 // literally the same bitwise algorithm with the same inputs.
                 assert_eq!(f1, f2);

                 // Make sure result is in [0.0, 1.0)
                 assert!(f1 >= 0.0);
                 assert!(f1 < 1.0);
             }

             // At least make sure our float's from rand_float() are in the valid range.
             for _ in 0..1000 {
                 let f1 = r1.rand_float();
                 assert!(f1 >= 0.0);
                 assert!(f1 < 1.0);
             }

             /*
             TODO: Randomize changed its int-to-float conversion functions and now they don't
             match ours.
                         for _ in 0..1000 {
                             // Now make sure our own float conversion function works.
                             let f1 = r1.rand_float();
                             //let f2 = randomize::f32_half_open_right(r2.next_u32());
                             let f2 = randomize::f32_open(r2.next_u32());
                             assert_eq!(f1, f2);
                             assert!(f1 >= 0.0);
                             assert!(f1 < 1.0);
                         }
                          */
         }
     }

     #[test]
     fn test_float64() {
         {
             let seed = 2718281828;
             let mut r1 = Rand64::new(seed);
             let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
             for _ in 0..1000 {
                 // First just make sure they both work with randomize's
                 // f64 conversion function -- sanity checks.
                 let i1 = r1.rand_u64();
                 let i2 = r2.next_u64();
                 assert_eq!(i1, i2);
                 let f1 = randomize::f64_half_open_right(i1);
                 let f2 = randomize::f64_half_open_right(i2);
                 // We can directly compare floats 'cause we do no math, it's
                 // literally the same bitwise algorithm with the same inputs.
                 assert_eq!(f1, f2);

                 // Make sure result is in [0.0, 1.0)
                 assert!(f1 >= 0.0);
                 assert!(f1 < 1.0);
             }

             // At least make sure our float's from rand_float() are in the valid range.
             for _ in 0..1000 {
                 let f1 = r1.rand_float();
                 assert!(f1 >= 0.0);
                 assert!(f1 < 1.0);
             }

             /*
             TODO: Randomize changed its int-to-float conversion functions and now they don't
             match ours.
                         for _ in 0..1000 {
                             // Now make sure our own float conversion function works.
                             let f1 = r1.rand_float();
                             //let f2 = randomize::f32_half_open_right(r2.next_u32());
                             let f2 = randomize::f32_open(r2.next_u32());
                             assert_eq!(f1, f2);
                             assert!(f1 >= 0.0);
                             assert!(f1 < 1.0);
                         }
                          */
         }
     }

     #[test]
     fn test_randrange32() {
         // Make sure ranges are valid and in the given range
         let seed = 2342_3141;
         let mut r1 = Rand32::new(seed);
         for _ in 0..1000 {
             // Generate our bounds at random
             let a = r1.rand_u32();
             let b = r1.rand_u32();
             if a == b {
                 continue;
             }
             let (low, high) = if a < b { (a, b) } else { (b, a) };

             // Get a number in that range
             let in_range = r1.rand_range(low..high);
             assert!(in_range >= low);
             assert!(in_range < high);
         }
     }

     #[test]
     fn test_randrange64() {
         // Make sure ranges are valid and in the given range
         let seed = 2342_2718;
         let mut r1 = Rand64::new(seed);
         for _ in 0..1000 {
             // Generate our bounds at random
             let a = r1.rand_u64();
             let b = r1.rand_u64();
             if a == b {
                 continue;
             }
             let (low, high) = if a < b { (a, b) } else { (b, a) };

             // Get a number in that range
             let in_range = r1.rand_range(low..high);
             assert!(in_range >= low);
             assert!(in_range < high);
         }
     }

     #[test]
     fn test_rand32_vs_rand() {
         use rand_core::RngCore;
         use rand_pcg;
         {
             let seed = 54321;
             let mut r1 = Rand32::new(seed);
             let mut r2 = rand_pcg::Pcg32::new(seed, Rand32::DEFAULT_INC);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.next_u32());
             }
         }

         {
             let seed = 3141592653;
             let inc = 0xDEADBEEF;
             let mut r1 = Rand32::new_inc(seed, inc);
             let mut r2 = rand_pcg::Pcg32::new(seed, inc);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.next_u32());
             }
         }
     }

     // This doesn't work 'cause for 64-bit output `rand` uses
     // PCG-XSL-RR
     // and we use
     // PCG-XSH-RR
     /*
         #[test]
         fn test_rand64_vs_rand() {
             use rand_pcg;
             use rand_core::RngCore;
             {
                 let seed = 54321;
                 let mut r1 = Rand64::new(seed);
                 let mut r2 = rand_pcg::Pcg64::new(seed, Rand64::DEFAULT_INC);
                 for _ in 0..1000 {
                     assert_eq!(r1.rand(), r2.next_u64());
                 }
             }

             {
                 let seed = 3141592653;
                 let inc = 0xDEADBEEF;
                 let mut r1 = Rand64::new_inc(seed, inc);
                 let mut r2 = rand_pcg::Pcg64::new(seed, inc);
                 for _ in 0..1000 {
                     assert_eq!(r1.rand(), r2.next_u64());
                 }
             }
         }
     */

     // Test vs. random-fast-rng, which I will call rfr
     // rfr's float conversion uses yet a different algorithm
     // than ours, so we can't really check that.
     #[test]
     fn test_rand32_vs_rfr() {
         use random_fast_rng as rfr;
         use rfr::Random;
         {
             let seed = 54321;
             let mut r1 = Rand32::new(seed);
             let mut r2 = rfr::FastRng::seed(seed, Rand32::DEFAULT_INC);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.get_u32());
             }
         }

         {
             let seed = 3141592653;
             let inc = 0xDEADBEEF;
             let mut r1 = Rand32::new_inc(seed, inc);
             let mut r2 = rfr::FastRng::seed(seed, inc);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.get_u32());
             }
         }
     }

     /// Make sure that saving a RNG state and restoring
     /// it works.
     /// See https://todo.sr.ht/~icefox/oorandom/1
     #[test]
     fn test_save_restore() {
         {
             let seed = 54321;
             let mut r1 = Rand32::new(seed);
             let s1 = r1.state();
             let mut r2 = Rand32::from_state(s1);
             assert_eq!(r1, r2);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.rand_u32());
             }
         }

         {
             let seed = 3141592653;
             let inc = 0xDEADBEEF;
             let mut r1 = Rand32::new_inc(seed, inc);
             let s1 = r1.state();
             let mut r2 = Rand32::from_state(s1);
             assert_eq!(r1, r2);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u32(), r2.rand_u32());
             }
         }

         {
             let seed = 54321;
             let mut r1 = Rand64::new(seed);
             let s1 = r1.state();
             let mut r2 = Rand64::from_state(s1);
             assert_eq!(r1, r2);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u64(), r2.rand_u64());
             }
         }

         {
             let seed = 3141592653;
             let inc = 0xDEADBEEF;
             let mut r1 = Rand64::new_inc(seed, inc);
             let s1 = r1.state();
             let mut r2 = Rand64::from_state(s1);
             assert_eq!(r1, r2);
             for _ in 0..1000 {
                 assert_eq!(r1.rand_u64(), r2.rand_u64());
             }
         }
     }
 }
	//! A tiny, robust PRNG implementation.
	//!
	//! More specifically, it implements a single GOOD PRNG algorithm,
	//! which is currently a permuted congruential generator. It has two
	//! implementations, one that returns `u32` and one that returns
	//! `u64`. It also has functions that return floats or integer
	//! ranges. And that's it. What more do you need?
	//!
	//! For more info on PCG generators, see http://www.pcg-random.org/
	//!
	//! This was designed as a minimalist utility for video games. No
	//! promises are made about its quality, and if you use it for
	//! cryptography you will get what you deserve.
	//!
	//! Works with `#![no_std]`, has no global state, no dependencies
	//! apart from some in the unit tests, and is generally neato.

	#![forbid(unsafe_code)]
	#![forbid(missing_docs)]
	#![forbid(missing_debug_implementations)]
	#![forbid(unused_results)]
	#![no_std]
	use core::ops::Range;

	/// A PRNG producing a 32-bit output.
	///
	/// The current implementation is `PCG-XSH-RR`.
	#[derive(Copy, Clone, Debug, PartialEq)]
	pub struct Rand32 {
	state: u64,
	inc: u64,
	}

	impl Rand32 {
	/// The default value for `increment`.
	/// This is basically arbitrary, it comes from the
	/// PCG reference C implementation:
	/// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L284
	pub const DEFAULT_INC: u64 = 1442695040888963407;

	/// This is the number that you have to Really Get Right.
	///
	/// The value used here is from the PCG C implementation:
	/// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L278
	pub(crate) const MULTIPLIER: u64 = 6364136223846793005;

	/// Creates a new PRNG with the given seed and a default increment.
	pub fn new(seed: u64) -> Self {
	Self::new_inc(seed, Self::DEFAULT_INC)
	}

	/// Creates a new PRNG. The two inputs, `seed` and `increment`,
	/// determine what you get; `increment` basically selects which
	/// sequence of all those possible the PRNG will produce, and the
	/// `seed` selects where in that sequence you start.
	///
	/// Both are arbitrary; increment must be an odd number but this
	/// handles that for you
	pub fn new_inc(seed: u64, increment: u64) -> Self {
	let mut rng = Self {
	state: 0,
	inc: increment.wrapping_shl(1) \| 1,
	};
	// This initialization song-and-dance is a little odd,
	// but seems to be just how things go.
	let _ = rng.rand_u32();
	rng.state = rng.state.wrapping_add(seed);
	let _ = rng.rand_u32();
	rng
	}

	/// Returns the internal state of the PRNG. This allows
	/// you to save a PRNG and create a new one that will resume
	/// from the same spot in the sequence.
	pub fn state(&self) -> (u64, u64) {
	(self.state, self.inc)
	}

	/// Creates a new PRNG from a saved state from `Rand32::state()`.
	/// This is NOT quite the same as `new_inc()` because `new_inc()` does
	/// a little extra setup work to initialize the state.
	pub fn from_state(state: (u64, u64)) -> Self {
	let (state, inc) = state;
	Self { state, inc }
	}

	/// Produces a random `u32` in the range `[0, u32::MAX]`.
	pub fn rand_u32(&mut self) -> u32 {
	let oldstate: u64 = self.state;
	self.state = oldstate
	.wrapping_mul(Self::MULTIPLIER)
	.wrapping_add(self.inc);
	let xorshifted: u32 = (((oldstate >> 18) ^ oldstate) >> 27) as u32;
	let rot: u32 = (oldstate >> 59) as u32;
	xorshifted.rotate_right(rot)
	}

	/// Produces a random `i32` in the range `[i32::MIN, i32::MAX]`.
	pub fn rand_i32(&mut self) -> i32 {
	self.rand_u32() as i32
	}

	/// Produces a random `f32` in the range `[0.0, 1.0)`.
	pub fn rand_float(&mut self) -> f32 {
	// This impl was taken more or less from `rand`, see
	// <https://docs.rs/rand/0.7.0/src/rand/distributions/float.rs.html#104-117>
	// There MAY be better ways to do this, see:
	// https://mumble.net/~campbell/2014/04/28/uniform-random-float
	// https://mumble.net/~campbell/2014/04/28/random_real.c
	// https://github.com/Lokathor/randomize/issues/34
	const TOTAL_BITS: u32 = 32;
	const PRECISION: u32 = core::f32::MANTISSA_DIGITS + 1;
	const MANTISSA_SCALE: f32 = 1.0 / ((1u32 << PRECISION) as f32);
	let mut u = self.rand_u32();
	u >>= TOTAL_BITS - PRECISION;
	u as f32 * MANTISSA_SCALE
	}

	/// Produces a random within the given bounds. Like any `Range`,
	/// it includes the lower bound and excludes the upper one.
	///
	/// This should be faster than `Self::rand() % end + start`, but the
	/// real advantage is it's more convenient. Requires that
	/// `range.end <= range.start`.
	pub fn rand_range(&mut self, range: Range<u32>) -> u32 {
	// This is harder to do well than it looks, it seems. I don't
	// trust Lokathor's implementation 'cause I don't understand
	// it, so I went to numpy's, which points me to "Lemire's
	// rejection algorithm": http://arxiv.org/abs/1805.10941
	//
	// Algorithms 3, 4 and 5 in that paper all seem fine modulo
	// minor performance differences, so this is algorithm 5.
	// It uses numpy's implementation, `buffered_bounded_lemire_uint32()`

	debug_assert!(range.start < range.end);
	let range_starting_from_zero = 0..(range.end - range.start);

	let s: u32 = range_starting_from_zero.end;
	let mut m: u64 = u64::from(self.rand_u32()) * u64::from(s);
	let mut leftover: u32 = (m & 0xFFFF_FFFF) as u32;

	if leftover < s {
	// TODO: verify the wrapping_neg() here
	let threshold: u32 = s.wrapping_neg() % s;
	while leftover < threshold {
	m = u64::from(self.rand_u32()).wrapping_mul(u64::from(s));
	leftover = (m & 0xFFFF_FFFF) as u32;
	}
	}
	(m >> 32) as u32 + range.start
	}
	}

	/// A PRNG producing a 64-bit output.
	///
	/// The current implementation is `PCG-XSH-RR`.
	// BUGGO: The recommended algorithm is PCG-XSL-RR?
	// See https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L2405
	// Not sure if it matters?
	#[derive(Copy, Clone, Debug, PartialEq)]
	pub struct Rand64 {
	state: u128,
	inc: u128,
	}

	impl Rand64 {
	/// The default value for `increment`.
	///
	/// The value used here is from the PCG default C implementation: http://www.pcg-random.org/download.html
	pub const DEFAULT_INC: u128 = 0x2FE0E169_FFBD06E3_5BC307BD_4D2F814F;

	/// This is the number that you have to Really Get Right.
	///
	/// The value used here is from the PCG C implementation:
	/// https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h#L288
	pub(crate) const MULTIPLIER: u128 = 47026247687942121848144207491837523525;

	/// Creates a new PRNG with the given seed and a default increment.
	pub fn new(seed: u128) -> Self {
	Self::new_inc(seed, Self::DEFAULT_INC)
	}

	/// Same as `Rand32::new_inc()`
	pub fn new_inc(seed: u128, increment: u128) -> Self {
	let mut rng = Self {
	state: 0,
	inc: increment.wrapping_shl(1) \| 1,
	};
	let _ = rng.rand_u64();
	rng.state = rng.state.wrapping_add(seed);
	let _ = rng.rand_u64();
	rng
	}

	/// Returns the internal state of the PRNG. This allows
	/// you to save a PRNG and create a new one that will resume
	/// from the same spot in the sequence.
	pub fn state(&self) -> (u128, u128) {
	(self.state, self.inc)
	}

	/// Creates a new PRNG from a saved state from `Rand32::state()`.
	/// This is NOT quite the same as `new_inc()` because `new_inc()` does
	/// a little extra setup work to initialize the state.
	pub fn from_state(state: (u128, u128)) -> Self {
	let (state, inc) = state;
	Self { state, inc }
	}

	/// Produces a random `u64` in the range`[0, u64::MAX]`.
	pub fn rand_u64(&mut self) -> u64 {
	let oldstate: u128 = self.state;
	self.state = oldstate
	.wrapping_mul(Self::MULTIPLIER)
	.wrapping_add(self.inc);
	let xorshifted: u64 = (((oldstate >> 29) ^ oldstate) >> 58) as u64;
	let rot: u32 = (oldstate >> 122) as u32;
	xorshifted.rotate_right(rot)
	}

	/// Produces a random `i64` in the range `[i64::MIN, i64::MAX]`.
	pub fn rand_i64(&mut self) -> i64 {
	self.rand_u64() as i64
	}

	/// Produces a random `f64` in the range `[0.0, 1.0)`.
	pub fn rand_float(&mut self) -> f64 {
	const TOTAL_BITS: u32 = 64;
	const PRECISION: u32 = core::f64::MANTISSA_DIGITS + 1;
	const MANTISSA_SCALE: f64 = 1.0 / ((1u64 << PRECISION) as f64);
	let mut u = self.rand_u64();
	u >>= TOTAL_BITS - PRECISION;
	u as f64 * MANTISSA_SCALE
	}

	/// Produces a random within the given bounds. Like any `Range`,
	/// it includes the lower bound and excludes the upper one.
	///
	/// This should be faster than `Self::rand() % end + start`, but the
	/// real advantage is it's more convenient. Requires that
	/// `range.end <= range.start`.
	pub fn rand_range(&mut self, range: Range<u64>) -> u64 {
	// Same as `Rand32::rand_range()`
	debug_assert!(range.start < range.end);
	let range_starting_from_zero = 0..(range.end - range.start);

	let s: u64 = range_starting_from_zero.end;
	let mut m: u128 = u128::from(self.rand_u64()) * u128::from(s);
	let mut leftover: u64 = (m & 0xFFFFFFFF_FFFFFFFF) as u64;

	if leftover < s {
	// TODO: Verify the wrapping_negate() here
	let threshold: u64 = s.wrapping_neg() % s;
	while leftover < threshold {
	m = u128::from(self.rand_u64()) * u128::from(s);
	leftover = (m & 0xFFFFFFFF_FFFFFFFF) as u64;
	}
	}
	(m.wrapping_shr(64)) as u64 + range.start
	}
	}

	#[cfg(test)]
	mod tests {
	use super::*;
	use randomize::{self, PCG32, PCG64};

	#[test]
	fn test_rand32_vs_randomize() {
	// Generate some random numbers and validate them against
	// a known-good generator.
	{
	let seed = 54321;
	let mut r1 = Rand32::new(seed);
	let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.next_u32());
	assert_eq!(r1.rand_i32(), r2.next_u32() as i32);
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand32::new_inc(seed, inc);
	let mut r2 = PCG32::seed(seed, inc);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.next_u32());
	assert_eq!(r1.rand_i32(), r2.next_u32() as i32);
	}
	}
	}

	#[test]
	fn test_rand64_vs_randomize() {
	// Generate some random numbers and validate them against
	// a known-good generator.
	{
	let seed = 54321;
	let mut r1 = Rand64::new(seed);
	let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u64(), r2.next_u64());
	assert_eq!(r1.rand_i64(), r2.next_u64() as i64);
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand64::new_inc(seed, inc);
	let mut r2 = PCG64::seed(seed, inc);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u64(), r2.next_u64());
	assert_eq!(r1.rand_i64(), r2.next_u64() as i64);
	}
	}
	}

	#[test]
	fn test_float32() {
	{
	let seed = 2718281828;
	let mut r1 = Rand32::new(seed);
	let mut r2 = PCG32::seed(seed, Rand32::DEFAULT_INC);
	for _ in 0..1000 {
	// First just make sure they both work with randomize's
	// f32 conversion function -- sanity checks.
	let i1 = r1.rand_u32();
	let i2 = r2.next_u32();
	assert_eq!(i1, i2);
	let f1 = randomize::f32_half_open_right(i1);
	let f2 = randomize::f32_half_open_right(i2);
	// We can directly compare floats 'cause we do no math, it's
	// literally the same bitwise algorithm with the same inputs.
	assert_eq!(f1, f2);

	// Make sure result is in [0.0, 1.0)
	assert!(f1 >= 0.0);
	assert!(f1 < 1.0);
	}

	// At least make sure our float's from rand_float() are in the valid range.
	for _ in 0..1000 {
	let f1 = r1.rand_float();
	assert!(f1 >= 0.0);
	assert!(f1 < 1.0);
	}

	/*
	TODO: Randomize changed its int-to-float conversion functions and now they don't
	match ours.
	for _ in 0..1000 {
	// Now make sure our own float conversion function works.
	let f1 = r1.rand_float();
	//let f2 = randomize::f32_half_open_right(r2.next_u32());
	let f2 = randomize::f32_open(r2.next_u32());
	assert_eq!(f1, f2);
	assert!(f1 >= 0.0);
	assert!(f1 < 1.0);
	}
	*/
	}
	}

	#[test]
	fn test_float64() {
	{
	let seed = 2718281828;
	let mut r1 = Rand64::new(seed);
	let mut r2 = PCG64::seed(seed, Rand64::DEFAULT_INC);
	for _ in 0..1000 {
	// First just make sure they both work with randomize's
	// f64 conversion function -- sanity checks.
	let i1 = r1.rand_u64();
	let i2 = r2.next_u64();
	assert_eq!(i1, i2);
	let f1 = randomize::f64_half_open_right(i1);
	let f2 = randomize::f64_half_open_right(i2);
	// We can directly compare floats 'cause we do no math, it's
	// literally the same bitwise algorithm with the same inputs.
	assert_eq!(f1, f2);

	// Make sure result is in [0.0, 1.0)
	assert!(f1 >= 0.0);
	assert!(f1 < 1.0);
	}

	// At least make sure our float's from rand_float() are in the valid range.
	for _ in 0..1000 {
	let f1 = r1.rand_float();
	assert!(f1 >= 0.0);
	assert!(f1 < 1.0);
	}

	/*
	TODO: Randomize changed its int-to-float conversion functions and now they don't
	match ours.
	for _ in 0..1000 {
	// Now make sure our own float conversion function works.
	let f1 = r1.rand_float();
	//let f2 = randomize::f32_half_open_right(r2.next_u32());
	let f2 = randomize::f32_open(r2.next_u32());
	assert_eq!(f1, f2);
	assert!(f1 >= 0.0);
	assert!(f1 < 1.0);
	}
	*/
	}
	}

	#[test]
	fn test_randrange32() {
	// Make sure ranges are valid and in the given range
	let seed = 2342_3141;
	let mut r1 = Rand32::new(seed);
	for _ in 0..1000 {
	// Generate our bounds at random
	let a = r1.rand_u32();
	let b = r1.rand_u32();
	if a == b {
	continue;
	}
	let (low, high) = if a < b { (a, b) } else { (b, a) };

	// Get a number in that range
	let in_range = r1.rand_range(low..high);
	assert!(in_range >= low);
	assert!(in_range < high);
	}
	}

	#[test]
	fn test_randrange64() {
	// Make sure ranges are valid and in the given range
	let seed = 2342_2718;
	let mut r1 = Rand64::new(seed);
	for _ in 0..1000 {
	// Generate our bounds at random
	let a = r1.rand_u64();
	let b = r1.rand_u64();
	if a == b {
	continue;
	}
	let (low, high) = if a < b { (a, b) } else { (b, a) };

	// Get a number in that range
	let in_range = r1.rand_range(low..high);
	assert!(in_range >= low);
	assert!(in_range < high);
	}
	}

	#[test]
	fn test_rand32_vs_rand() {
	use rand_core::RngCore;
	use rand_pcg;
	{
	let seed = 54321;
	let mut r1 = Rand32::new(seed);
	let mut r2 = rand_pcg::Pcg32::new(seed, Rand32::DEFAULT_INC);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.next_u32());
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand32::new_inc(seed, inc);
	let mut r2 = rand_pcg::Pcg32::new(seed, inc);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.next_u32());
	}
	}
	}

	// This doesn't work 'cause for 64-bit output `rand` uses
	// PCG-XSL-RR
	// and we use
	// PCG-XSH-RR
	/*
	#[test]
	fn test_rand64_vs_rand() {
	use rand_pcg;
	use rand_core::RngCore;
	{
	let seed = 54321;
	let mut r1 = Rand64::new(seed);
	let mut r2 = rand_pcg::Pcg64::new(seed, Rand64::DEFAULT_INC);
	for _ in 0..1000 {
	assert_eq!(r1.rand(), r2.next_u64());
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand64::new_inc(seed, inc);
	let mut r2 = rand_pcg::Pcg64::new(seed, inc);
	for _ in 0..1000 {
	assert_eq!(r1.rand(), r2.next_u64());
	}
	}
	}
	*/

	// Test vs. random-fast-rng, which I will call rfr
	// rfr's float conversion uses yet a different algorithm
	// than ours, so we can't really check that.
	#[test]
	fn test_rand32_vs_rfr() {
	use random_fast_rng as rfr;
	use rfr::Random;
	{
	let seed = 54321;
	let mut r1 = Rand32::new(seed);
	let mut r2 = rfr::FastRng::seed(seed, Rand32::DEFAULT_INC);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.get_u32());
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand32::new_inc(seed, inc);
	let mut r2 = rfr::FastRng::seed(seed, inc);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.get_u32());
	}
	}
	}

	/// Make sure that saving a RNG state and restoring
	/// it works.
	/// See https://todo.sr.ht/~icefox/oorandom/1
	#[test]
	fn test_save_restore() {
	{
	let seed = 54321;
	let mut r1 = Rand32::new(seed);
	let s1 = r1.state();
	let mut r2 = Rand32::from_state(s1);
	assert_eq!(r1, r2);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.rand_u32());
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand32::new_inc(seed, inc);
	let s1 = r1.state();
	let mut r2 = Rand32::from_state(s1);
	assert_eq!(r1, r2);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u32(), r2.rand_u32());
	}
	}

	{
	let seed = 54321;
	let mut r1 = Rand64::new(seed);
	let s1 = r1.state();
	let mut r2 = Rand64::from_state(s1);
	assert_eq!(r1, r2);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u64(), r2.rand_u64());
	}
	}

	{
	let seed = 3141592653;
	let inc = 0xDEADBEEF;
	let mut r1 = Rand64::new_inc(seed, inc);
	let s1 = r1.state();
	let mut r2 = Rand64::from_state(s1);
	assert_eq!(r1, r2);
	for _ in 0..1000 {
	assert_eq!(r1.rand_u64(), r2.rand_u64());
	}
	}
	}
	}