//! 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()`
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
}
}
#[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());
}
}
{
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());
}
}
}
#[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());
}
}
{
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());
}
}
}
#[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);
}
/*
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);
}
/*
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_randrange() {
// Make sure ranges are valid and in the given range
let seed = 2342_4223;
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_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());
}
}
}
}