//! `perchance` is a simple random number generation library, tuned for ease of use: create an instance of [`PerchanceContext`] and go.
//!
//! Note that `perchance` is **not** cryptographically secure and ***should not*** be used in any context where security is a concern.
//!
//! When the `std` feature is enabled (by default), there's a global [`PerchanceContext`] provided, too.
//!
//! # Example
//!
//! First, create a [`PerchanceContext`]:
//!
//! ```rust
//! # let my_seed = 0;
//! let mut rng = perchance::PerchanceContext::new(my_seed);
//! ```
//!
//! Or, if you have the `std` feature enabled, obtain the global [`PerchanceContext`] object:
//!
//! ```rust
//! // Seed the global context first. You may do so manually, or, on platforms that support it,
//! // obtain a seed to pass into it by calling `perchance::gen_time_seed()`.
//! perchance::seed_global(0x5F3759DF); // ;)
//!
//! let mut rng = perchance::global();
//! ```
//!
//! Then, start letting things happen perchance!
//!
//! ```rust
//! # perchance::seed_global(0x5F3759DF);
//! # let mut rng = perchance::global();
//! let between_0_and_1 = rng.uniform_f32();
//! let dice_roll = rng.uniform_range_i32(1..=6);
//! let random_direction = rng.uniform_sphere_surface_vec3();
//! let thing_should_happen = rng.get_bool();
//!
//! enum Event {
//! Thing1,
//! Thing2,
//! Thing3,
//! }
//! let which_should_happen = rng.choose(&[Event::Thing1, Event::Thing2, Event::Thing3]);
//! ```
//!
//! Some of the convenience functions exist in multiple flavors with different
//! return types.
//!
//! Perchance does NOT guarantee the same random number generator across new versions of the crate.
#![allow(clippy::disallowed_types)] // allow usage of std::sync::Mutex (instead of parking_lot) as this is typically intended for Wasm
use core::ops::Bound;
use core::ops::RangeBounds;
/// The raw random number generator.
/// As of may 2020, this is the same generator used by `rand::SmallRng`.
///
/// It is small, fast and simple. Based on the `rand_pcg` crate, but
/// without a dependency to keep the dependency tree smaller.
#[derive(Clone)]
struct Rng(u128);
const MULTIPLIER: u128 = 0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645;
impl Rng {
#[inline]
#[allow(unused)]
pub const fn from_seed(seed: u128) -> Self {
// state must be odd:
Self((seed << 1) | 1)
}
#[inline]
fn next_u32(&mut self) -> u32 {
self.next_u64() as u32
}
#[inline]
fn next_u64(&mut self) -> u64 {
self.0 = self.0.wrapping_mul(MULTIPLIER);
// Output function XSL RR ("xorshift low (bits), random rotation"):
const XSHIFT: u32 = 64; // (128 - 64 + 64) / 2
const ROTATE: u32 = 122; // 128 - 6
let rot = (self.0 >> ROTATE) as u32;
let xsl = ((self.0 >> XSHIFT) as u64) ^ (self.0 as u64);
xsl.rotate_right(rot)
}
}
macro_rules! impl_get_bounds {
(float, $fn_name:ident, $t:ty) => {
/// Returned start is inclusive, returned end is exclusive
/// Ignores inclusivity of input bounds.
/// Unbounded gets set to `$t::MIN` or `$t::MAX` respectively.
fn $fn_name<R: RangeBounds<$t>>(bounds: R) -> ($t, $t) {
let start = match bounds.start_bound() {
Bound::Included(&b) | Bound::Excluded(&b) => b,
Bound::Unbounded => <$t>::MIN,
};
let end = match bounds.end_bound() {
Bound::Included(&b) | Bound::Excluded(&b) => b,
Bound::Unbounded => <$t>::MAX,
};
(start, end)
}
};
(int, $fn_name:ident, $t:ty) => {
/// Returned start is inclusive, returned end is exclusive.
/// Unbounded gets set to `$t::MIN` or `$t::MAX` respectively.
/// Panics on overflow, if:
/// - lower bound exclusive and = `$t::MAX`
/// - upper bound inclusive and = `$t::MAX`
fn $fn_name<R: RangeBounds<$t>>(bounds: R) -> ($t, $t) {
let start = match bounds.start_bound() {
Bound::Included(&b) => b,
Bound::Excluded(&b) => b.checked_add(1).unwrap(),
Bound::Unbounded => <$t>::MIN,
};
let end = match bounds.end_bound() {
Bound::Included(&b) => b.checked_add(1).unwrap(),
Bound::Excluded(&b) => b,
Bound::Unbounded => <$t>::MAX,
};
(start, end)
}
};
}
impl_get_bounds!(float, get_f32_bounds, f32);
impl_get_bounds!(int, get_usize_bounds, usize);
impl_get_bounds!(int, get_i32_bounds, i32);
#[derive(Clone)]
pub struct PerchanceContext(Rng);
impl PerchanceContext {
/// Returns a new `PerchanceContext`, seeded with `seed`.
///
/// Two `PerchanceContext`s seeded with the same number will generate the same
/// sequence of outputs, given an identical sequence of calls to its member functions.
///
/// Since `perchance` is not yet stabilized we reserve the right to change the
/// random number generator algorithm, meaning the same seed may produce different
/// numbers on different version of `perchance`.
pub const fn new(seed: u128) -> Self {
Self(Rng::from_seed(seed))
}
/// 50/50 chance
pub fn get_bool(&mut self) -> bool {
self.0.next_u64() & 1 == 1
}
/// All 32 bits of the number are random.
pub fn get_u32(&mut self) -> u32 {
self.0.next_u32()
}
/// All 64 bits of the number are random.
pub fn get_u64(&mut self) -> u64 {
self.0.next_u64()
}
/// All 128 bits of the number are random.
pub fn get_u128(&mut self) -> u128 {
(u128::from(self.0.next_u64()) << 64) | u128::from(self.0.next_u64())
}
/// Returns a number strictly less than the given max.
/// Returns 0 if max is zero.
pub fn u64_less_than(&mut self, max: u64) -> u64 {
if max == 0 {
return 0;
}
// We can only easily generate an integral number of bits of randomness,
// i.e. numbers within a range [0, 2^n).
// In particular, we can NOT do `get_u64() % max` due to the pigenhole principle.
// We then pick the smallest power-of-two zone containing the our max.
// So for instance, for max=6 we pick three bits of randomness, i.e. a range of [0, 8).
// We generate numbers in this range until we get on below our max.
// This is not the most efficient way of doing this, but it is the simplest.
let significant_bits = 64 - max.leading_zeros();
let mask = if significant_bits == 64 {
u64::MAX
} else {
(1 << significant_bits) - 1
};
loop {
let num = self.get_u64() & mask;
if num < max {
return num;
}
}
}
/// Returns a `usize` that is less than the given number.
/// If the given number is zero, None is returned.
pub fn usize_less_than(&mut self, end: usize) -> usize {
self.u64_less_than(end as u64) as usize
}
/// Chose one of the given values at random.
/// panics if the given slice is empty
pub fn choose<'slice, T>(&mut self, slice: &'slice [T]) -> &'slice T {
&slice[self.usize_less_than(slice.len())]
}
/// Chose one of the given values at random.
/// panics if the given slice is empty
pub fn choose_mut<'slice, T>(&mut self, slice: &'slice mut [T]) -> &'slice mut T {
&mut slice[self.usize_less_than(slice.len())]
}
/// Chose one of the given values at random.
/// Returns `None` if the given iterator is empty.
pub fn choose_it<T>(&mut self, it: impl Iterator<Item = T>) -> Option<T> {
// reservoir sampling
let mut chosen = None;
for (i, value) in it.enumerate() {
if self.usize_less_than(i + 1) == 0 {
chosen = Some(value);
}
}
chosen
}
/// Returns a random integer uniformly distributed over `range`.
/// Panics if the range is invalid (end < start) or if the range bounds would overflow an i32.
/// Example: `let dice = rng.uniform_range_i32(0..6);`
pub fn uniform_range_i32<R: RangeBounds<i32>>(&mut self, range: R) -> i32 {
// Switch to i64 to prevent overflows
let (start, end) = get_i32_bounds(range);
let start = i64::from(start);
let end = i64::from(end);
let range_size = end - start;
assert!(range_size >= 0);
let value = start + self.u64_less_than(range_size as u64) as i64;
value as i32
}
/// Returns a random usize uniformly distributed over `range`.
/// Panics if the range is invalid (end < start) or if the range bounds would overflow a usize.
/// Example: `let array_index = rng.uniform_range_usize(0..array.len());`
pub fn uniform_range_usize<R: RangeBounds<usize>>(&mut self, range: R) -> usize {
let (start, end) = get_usize_bounds(range);
assert!(end >= start);
start + self.usize_less_than(end - start)
}
/// Returns a random floating point number in the range [0.0, 1.0).
pub fn uniform_f32(&mut self) -> f32 {
// Construct a floating point number between 1.0 and 2.0 directly from the bits for maximally uniform coverage.
// Subtract 1.0 to get to the 0..1 range.
f32::from_bits(0x3F80_0000 | (self.get_u32() >> 9)) - 1.0
}
/// Returns a random floating point number in the range [0.0, 1.0).
pub fn uniform_f64(&mut self) -> f64 {
// Construct a floating point number between 1.0 and 2.0 directly from the bits for maximally uniform coverage.
// Subtract 1.0 to get to the 0..1 range.
let exponent = 1023; // 0
let mantissa = self.get_u64() >> 12;
f64::from_bits((exponent << 52) | mantissa) - 1.0
}
/// Returns a random floating point number uniformly distributed over `range`.
///
/// Note that this ignores the inclusivity of the range (always assumes an inclusive
/// lower bound and an exclusive upper bound). An unbonded lower and upper bound will be set to
/// `f32::MIN` and `f32::MAX` respectively.
pub fn uniform_range_f32<R: RangeBounds<f32>>(&mut self, range: R) -> f32 {
self.uniform_range_f32_raw(get_f32_bounds(range))
}
#[inline]
fn uniform_range_f32_raw(&mut self, (start, end): (f32, f32)) -> f32 {
self.uniform_f32() * (end - start) + start
}
/// A normally distributed value with standard deviation=1
pub fn normal_f32(&mut self) -> f32 {
// Basic Box-Muller transform
let mut r;
#[allow(clippy::blocks_in_if_conditions)]
while {
r = (-2.0 * self.uniform_f64().ln()).sqrt();
!r.is_finite()
} {}
let angle = 2.0 * core::f64::consts::PI * self.uniform_f64();
let s = angle.sin();
(r * s) as f32
}
/// Two independent normally distributed values
#[cfg(feature = "macaw")]
pub fn normal_vec2(&mut self) -> macaw::Vec2 {
// Basic Box-Muller transform
let mut r;
#[allow(clippy::blocks_in_if_conditions)]
while {
r = (-2.0 * self.uniform_f64().ln()).sqrt();
!r.is_finite()
} {}
let angle = 2.0 * core::f64::consts::PI * self.uniform_f64();
let (s, c) = angle.sin_cos();
macaw::Vec2::new((r * s) as f32, (r * c) as f32)
}
/// Three independent normally distributed values
#[cfg(feature = "macaw")]
pub fn normal_vec3(&mut self) -> macaw::Vec3 {
self.normal_vec2().extend(self.normal_f32())
}
/// Returns a Vec2 where both components are uniformly distributed over `range`.
#[cfg(feature = "macaw")]
pub fn uniform_square_vec2<R: RangeBounds<f32>>(&mut self, range: R) -> macaw::Vec2 {
let bounds = get_f32_bounds(range);
macaw::Vec2::new(
self.uniform_range_f32_raw(bounds),
self.uniform_range_f32_raw(bounds),
)
}
/// Returns a Vec3 where all three components are uniformly distributed over `range`.
#[cfg(feature = "macaw")]
pub fn uniform_cube_vec3<R: RangeBounds<f32>>(&mut self, range: R) -> macaw::Vec3 {
let bounds = get_f32_bounds(range);
macaw::Vec3::new(
self.uniform_range_f32_raw(bounds),
self.uniform_range_f32_raw(bounds),
self.uniform_range_f32_raw(bounds),
)
}
/// Returns a uniformly random point that lies inside the bounding box.
#[cfg(feature = "macaw")]
pub fn uniform_bounds_vec3(&mut self, bounds: macaw::BoundingBox) -> macaw::Vec3 {
macaw::Vec3::new(
self.uniform_range_f32_raw((bounds.min.x, bounds.max.x)),
self.uniform_range_f32_raw((bounds.min.y, bounds.max.y)),
self.uniform_range_f32_raw((bounds.min.z, bounds.max.z)),
)
}
/// Returns a uniformly random point that lies inside the rectangle.
#[cfg(feature = "macaw")]
pub fn uniform_rectangle_vec2(&mut self, min: macaw::Vec2, max: macaw::Vec2) -> macaw::Vec2 {
macaw::Vec2::new(
self.uniform_range_f32_raw((min.x, max.x)),
self.uniform_range_f32_raw((min.y, max.y)),
)
}
/// Returns a random Vec2 within a circular disc.
#[cfg(feature = "macaw")]
pub fn uniform_disc_vec2(&mut self) -> macaw::Vec2 {
// TODO: Use a better algorithm. Should still be fast enough though.
loop {
let val = self.uniform_square_vec2(-1.0..1.0);
if val.length_squared() < 1.0 {
return val;
}
}
}
/// Returns a random Vec3 on the surface of a sphere with radius 1.0.
#[cfg(feature = "macaw")]
pub fn uniform_sphere_surface_vec3(&mut self) -> macaw::Vec3 {
let x = self.uniform_f32();
let y = self.uniform_f32();
let tau = 2.0 * core::f32::consts::PI;
let z = 1.0f32 - 2.0f32 * x;
let xy = ((0.0f32).max(1.0f32 - z * z)).sqrt();
let sn = (tau * y).sin();
let cs = (tau * y).cos();
macaw::Vec3::new(sn * xy, cs * xy, z)
}
/// Returns a random Vec3 within the volume of a sphere.
#[cfg(feature = "macaw")]
pub fn uniform_sphere_volume_vec3(&mut self) -> macaw::Vec3 {
// TODO: Use a better algorithm. Should still be fast enough though.
loop {
let val = self.uniform_cube_vec3(-1.0..1.0);
if val.length_squared() < 1.0 {
return val;
}
}
}
/// Return a an integer index, weighted by the given weights.
/// For instance, `rng.weighted_choice_f32(&[1.0, 3.0, 2.0])` will return
/// `0` with a `1/6` probability,
/// `1` with a `3/6` probability,
/// `2` with a `2/6` probability.
///
/// If the weights sum to zero, a fair choice is returned.
///
/// The function panics if the given weight list is empty, or contain non-finite or negative numbers.
pub fn weighted_choice_f32(&mut self, weights: &[f32]) -> usize {
assert!(!weights.is_empty());
let sum: f64 = weights.iter().map(|&w| f64::from(w)).sum();
assert!(sum.is_finite());
if sum == 0.0 {
self.usize_less_than(weights.len())
} else {
let pos = self.uniform_f64() * sum;
let mut cumulative_sum = 0.0;
for (i, w) in weights.iter().take(weights.len() - 1).enumerate() {
cumulative_sum += f64::from(*w);
if pos < cumulative_sum {
return i;
}
}
weights.len() - 1
}
}
/// Like [`Self::weighted_choice_f32`], but returns a sampler that allows you to much more efficiently sample multiple choices with the same weights.
///
/// Complexity for `N` samples with `C` weights is `C + N*log(C)` instead of `C + N*C` when using `weighted_choice_f32`.
///
/// Panics if given a NaN weight.
pub fn weighted_choices_f32(&mut self, weights: &[f32]) -> WeightedSampler<'_> {
use ordered_float::NotNan;
assert!(!weights.is_empty());
let zero = NotNan::<f64>::default();
let mut sum = zero;
let mut cum = Vec::with_capacity(weights.len());
cum.resize(weights.len(), zero);
for (c, v) in cum.iter_mut().zip(weights) {
sum += NotNan::new(f64::from(*v)).expect("weighted_choices_f32 was given a NaN weight");
*c = sum;
}
WeightedSampler {
context: self,
cumulative_weights: cum,
}
}
}
pub struct WeightedSampler<'a> {
context: &'a mut PerchanceContext,
cumulative_weights: Vec<ordered_float::NotNan<f64>>,
}
impl<'a> WeightedSampler<'a> {
/// Returns an index sampled according to the given weights.
///
/// See [`PerchanceContext::weighted_choice_f32`] for more details.
pub fn sample(&mut self) -> usize {
// Note: guaranteed to contain at least one element
let weight_sum = *self.cumulative_weights.last().unwrap();
let value = ordered_float::NotNan::new(self.context.uniform_f64()).unwrap() * weight_sum;
match self.cumulative_weights.binary_search(&value) {
Ok(index) | Err(index) => index,
}
}
}
mod global_ctx {
use super::*;
use once_cell::sync::Lazy;
use std::sync::Mutex;
#[cfg(not(target_family = "wasm"))]
use std::time::SystemTime;
#[cfg(not(target_family = "wasm"))]
use std::time::UNIX_EPOCH;
#[cfg(not(target_family = "wasm"))]
const TWO_POW_64: u128 = 2u128.pow(64);
#[cfg(not(target_family = "wasm"))]
const TWO_POW_96: u128 = 2u128.pow(96);
static GLOBAL_RNG: Lazy<Mutex<PerchanceContext>> =
Lazy::new(|| Mutex::new(PerchanceContext::new(0)));
static HAS_BEEN_SEEDED: std::sync::atomic::AtomicBool =
std::sync::atomic::AtomicBool::new(false);
/// Returns the global [`PerchanceContext`]. You **must** seed it by calling
/// [`perchance::seed_global`](self::seed_global) at least once before calling this function or else
/// it will panic.
///
/// Call methods on it like [`PerchanceContext::get_u32`] to get random numbers from anywhere in your module.
pub fn global<'a>() -> std::sync::MutexGuard<'a, PerchanceContext> {
assert!(
global_has_been_seeded(),
"You must call `perchance::seed_global` before using the global perchance instance."
);
GLOBAL_RNG.lock().unwrap()
}
/// Seed (or reseed) the global [`PerchanceContext`] returned by [`perchance::global`](self::global).
///
/// After calling this at least once, [`perchance::global_has_been_seeded`](self::global_has_been_seeded) will return true.
pub fn seed_global(seed: u128) {
HAS_BEEN_SEEDED.store(true, std::sync::atomic::Ordering::SeqCst);
*global() = PerchanceContext::new(seed);
}
/// Generates a seed that may be passed to [`perchance::seed_global`](self::seed_global) based on the
/// system clock.
#[cfg(not(target_family = "wasm"))]
pub fn gen_time_seed() -> u128 {
SystemTime::now()
.duration_since(UNIX_EPOCH)
.map(|duration| {
u128::from(duration.as_secs()) // u64 as bits 0..64 of u128
| (u128::from(duration.subsec_millis()) * TWO_POW_64) // put u32 into bits 64..96 of u128
| (u128::from(duration.subsec_micros()) * TWO_POW_96) // put u32 into bits 96..128 of u128
})
.unwrap()
}
/// Returns `true` if [`perchance::seed_global`](self::seed_global) has been called at least once.
pub fn global_has_been_seeded() -> bool {
HAS_BEEN_SEEDED.load(std::sync::atomic::Ordering::SeqCst)
}
}
pub use global_ctx::*;