347 lines
13 KiB
Rust
347 lines
13 KiB
Rust
//! Deterministic, reproducible RNG (spec §4.4, §7).
|
||
//!
|
||
//! [`Rng`] wraps [`rand_chacha::ChaCha8Rng`] — a portable, byte-stable stream
|
||
//! cipher RNG. The same seed yields the same sequence on every machine and
|
||
//! every run; we never touch `thread_rng`/`rand::random()`.
|
||
//!
|
||
//! The keystone feature is [`Rng::fork`]: it derives an *independent* child
|
||
//! stream from the parent's **basis seed** plus a label. Forking does not draw
|
||
//! from or otherwise mutate the parent (`fork(&self)`), so a child stream is a
|
||
//! pure function of `(basis_seed, label)` — independent of how many values were
|
||
//! pulled from the parent first. The [`Pipeline`](crate) leans on this to give
|
||
//! each pass its own sub-stream keyed by `"<pass name>#<occurrence>"`, which is
|
||
//! what makes inserting or reordering a pass non-destructive to existing seeds.
|
||
|
||
use rand_chacha::ChaCha8Rng;
|
||
// `rand_core` is not a direct dependency; reach its traits through the
|
||
// re-export on `rand_chacha` so the two stay version-locked. `Rng` carries
|
||
// `next_u64`; `SeedableRng` carries `seed_from_u64`.
|
||
use rand_chacha::rand_core::{Rng as _, SeedableRng};
|
||
|
||
/// A deterministic random number generator backed by ChaCha8.
|
||
///
|
||
/// Construct one with [`Rng::from_seed`], draw values with [`range`](Rng::range),
|
||
/// [`chance`](Rng::chance), [`choose`](Rng::choose) and [`shuffle`](Rng::shuffle),
|
||
/// and derive isolated child streams with [`fork`](Rng::fork).
|
||
#[derive(Clone, Debug)]
|
||
pub struct Rng {
|
||
/// The stable basis used for all forks: the seed this `Rng` was built from.
|
||
/// Forking mixes *this* (never the live ChaCha state) with the label, so a
|
||
/// fork is independent of how many draws the parent has taken.
|
||
basis_seed: u64,
|
||
/// The live ChaCha8 stream that actually produces random words.
|
||
inner: ChaCha8Rng,
|
||
}
|
||
|
||
impl Rng {
|
||
/// Create an `Rng` from a 64-bit seed, storing the seed as the fork basis.
|
||
///
|
||
/// The seed is expanded into ChaCha8's 256-bit key by ChaCha8's own
|
||
/// portable `seed_from_u64`, so two `Rng`s built from the same `u64`
|
||
/// produce identical streams everywhere.
|
||
pub fn from_seed(seed: u64) -> Self {
|
||
Self {
|
||
basis_seed: seed,
|
||
inner: ChaCha8Rng::seed_from_u64(seed),
|
||
}
|
||
}
|
||
|
||
/// Derive an independent child `Rng` from a stable basis (this `Rng`'s
|
||
/// originating seed) combined with `label`.
|
||
///
|
||
/// This **does not** advance or otherwise mutate `self` (note `&self`), and
|
||
/// the result depends only on `(self.basis_seed, label)` — never on how many
|
||
/// values have already been drawn from `self`. Distinct labels (including
|
||
/// `"name#0"` vs `"name#1"`) yield distinct streams.
|
||
///
|
||
/// The label→seed mix is the explicit, fixed integer routine in
|
||
/// [`mix_seed`] (splitmix64 + FNV-1a), chosen because it is stable across
|
||
/// runs and crate versions. We deliberately avoid
|
||
/// `std::collections::hash_map::DefaultHasher`, whose output is
|
||
/// unspecified and version-unstable (spec §7).
|
||
pub fn fork(&self, label: &str) -> Rng {
|
||
Rng::from_seed(mix_seed(self.basis_seed, label))
|
||
}
|
||
|
||
/// Draw a `u64` of raw randomness from the live stream.
|
||
fn next_u64(&mut self) -> u64 {
|
||
self.inner.next_u64()
|
||
}
|
||
|
||
/// Return an integer in the **half-open** range `[lo, hi)` — `lo` inclusive,
|
||
/// `hi` exclusive (so `range(0, 3)` yields one of `0, 1, 2`).
|
||
///
|
||
/// If `hi <= lo` the range is empty; we return `lo` rather than panicking
|
||
/// (no panics on valid input — spec §8). Uniformity is achieved with
|
||
/// Lemire-style rejection sampling over the `u64` span, so the result is
|
||
/// unbiased across the whole range.
|
||
pub fn range(&mut self, lo: i32, hi: i32) -> i32 {
|
||
if hi <= lo {
|
||
return lo;
|
||
}
|
||
// Width fits in u64: (hi - lo) where hi > lo and both are i32.
|
||
let span = (hi as i64 - lo as i64) as u64;
|
||
lo + self.below(span) as i32
|
||
}
|
||
|
||
/// Uniform integer in `[0, span)` for `span > 0`, via rejection sampling to
|
||
/// avoid modulo bias. `span` is assumed non-zero by callers.
|
||
fn below(&mut self, span: u64) -> u64 {
|
||
// Largest multiple of `span` that fits in u64; anything at or above the
|
||
// threshold would skew the distribution, so we reject and redraw.
|
||
let threshold = u64::MAX - (u64::MAX % span);
|
||
loop {
|
||
let x = self.next_u64();
|
||
if x < threshold {
|
||
return x % span;
|
||
}
|
||
}
|
||
}
|
||
|
||
/// Return `true` with probability `p`.
|
||
///
|
||
/// `p` is clamped to `[0.0, 1.0]`, so out-of-range probabilities are
|
||
/// saturated rather than panicking. `p <= 0.0` is always `false`,
|
||
/// `p >= 1.0` is always `true`.
|
||
pub fn chance(&mut self, p: f64) -> bool {
|
||
if p <= 0.0 {
|
||
return false;
|
||
}
|
||
if p >= 1.0 {
|
||
return true;
|
||
}
|
||
// Map the next u64 into a uniform f64 in [0, 1) and compare.
|
||
// 53 bits gives the full mantissa precision of an f64.
|
||
let bits = self.next_u64() >> 11; // top 53 bits
|
||
let unit = bits as f64 / (1u64 << 53) as f64;
|
||
unit < p
|
||
}
|
||
|
||
/// Return a reference to a uniformly chosen element of `items`, or `None`
|
||
/// if the slice is empty.
|
||
pub fn choose<'a, T>(&mut self, items: &'a [T]) -> Option<&'a T> {
|
||
if items.is_empty() {
|
||
return None;
|
||
}
|
||
let idx = self.below(items.len() as u64) as usize;
|
||
items.get(idx)
|
||
}
|
||
|
||
/// Shuffle `items` in place into a uniformly random permutation.
|
||
///
|
||
/// Uses an in-place Fisher–Yates shuffle built on our own [`range`] so the
|
||
/// permutation is fully determined by the stream and identical on every
|
||
/// machine. A slice of length 0 or 1 is left unchanged.
|
||
pub fn shuffle<T>(&mut self, items: &mut [T]) {
|
||
let len = items.len();
|
||
if len < 2 {
|
||
return;
|
||
}
|
||
// Walk from the end; swap each element with a random earlier-or-equal
|
||
// index. Iterate down to 1 because index 0 has nothing left to swap.
|
||
for i in (1..len).rev() {
|
||
let j = self.below((i + 1) as u64) as usize;
|
||
items.swap(i, j);
|
||
}
|
||
}
|
||
}
|
||
|
||
/// Mix a 64-bit basis seed with a label into a fresh 64-bit seed for [`Rng::fork`].
|
||
///
|
||
/// This is the load-bearing determinism primitive (spec §7), so the algorithm
|
||
/// is spelled out explicitly and uses only fixed integer arithmetic — no
|
||
/// `DefaultHasher`, no version-unstable hashing.
|
||
///
|
||
/// Recipe:
|
||
/// 1. Start from a splitmix64 scramble of the basis seed (so the basis is well
|
||
/// diffused before any label bytes are folded in).
|
||
/// 2. Fold each label byte in with the FNV-1a step (`xor` then multiply by the
|
||
/// 64-bit FNV prime), which makes the result order-sensitive across bytes —
|
||
/// so `"name#0"` and `"name#1"` diverge.
|
||
/// 3. Run one final splitmix64 finalizer to avalanche the combined value.
|
||
fn mix_seed(basis: u64, label: &str) -> u64 {
|
||
// The 64-bit FNV-1a offset basis and prime (fixed, well-known constants).
|
||
const FNV_PRIME: u64 = 0x0000_0100_0000_01B3;
|
||
|
||
let mut state = splitmix64(basis);
|
||
for &byte in label.as_bytes() {
|
||
state ^= byte as u64;
|
||
state = state.wrapping_mul(FNV_PRIME);
|
||
}
|
||
splitmix64(state)
|
||
}
|
||
|
||
/// One round of the splitmix64 finalizer: a fixed, portable integer avalanche.
|
||
fn splitmix64(seed: u64) -> u64 {
|
||
// Constants from the reference splitmix64 (Steele, Lea & Flood 2014).
|
||
let mut z = seed.wrapping_add(0x9E37_79B9_7F4A_7C15);
|
||
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
|
||
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
|
||
z ^ (z >> 31)
|
||
}
|
||
|
||
#[cfg(test)]
|
||
mod tests {
|
||
use super::*;
|
||
|
||
/// Same seed → identical sequence of `range` draws.
|
||
#[test]
|
||
fn same_seed_reproduces_sequence() {
|
||
let mut a = Rng::from_seed(0xABCD_1234);
|
||
let mut b = Rng::from_seed(0xABCD_1234);
|
||
let seq_a: Vec<i32> = (0..64).map(|_| a.range(0, 1000)).collect();
|
||
let seq_b: Vec<i32> = (0..64).map(|_| b.range(0, 1000)).collect();
|
||
assert_eq!(seq_a, seq_b);
|
||
}
|
||
|
||
/// Different seeds should (overwhelmingly) produce different sequences.
|
||
#[test]
|
||
fn distinct_seeds_diverge() {
|
||
let mut a = Rng::from_seed(1);
|
||
let mut b = Rng::from_seed(2);
|
||
let seq_a: Vec<i32> = (0..64).map(|_| a.range(0, 1_000_000)).collect();
|
||
let seq_b: Vec<i32> = (0..64).map(|_| b.range(0, 1_000_000)).collect();
|
||
assert_ne!(seq_a, seq_b);
|
||
}
|
||
|
||
/// `fork` is order-independent: the child stream does not depend on how many
|
||
/// values were drawn from the parent beforehand, and forking does not mutate
|
||
/// the parent.
|
||
#[test]
|
||
fn fork_is_order_independent() {
|
||
let parent = Rng::from_seed(99);
|
||
|
||
// Fork immediately.
|
||
let mut early = parent.fork("a");
|
||
|
||
// Now draw a bunch from a *clone* of the parent, then fork.
|
||
let mut drained = parent.clone();
|
||
for _ in 0..50 {
|
||
let _ = drained.range(0, 100);
|
||
}
|
||
let mut late = drained.fork("a");
|
||
|
||
let early_seq: Vec<i32> = (0..32).map(|_| early.range(0, 10_000)).collect();
|
||
let late_seq: Vec<i32> = (0..32).map(|_| late.range(0, 10_000)).collect();
|
||
assert_eq!(early_seq, late_seq, "fork must depend only on basis seed + label");
|
||
}
|
||
|
||
/// `fork(&self)` does not advance the parent's own stream.
|
||
#[test]
|
||
fn fork_does_not_mutate_parent() {
|
||
let mut parent = Rng::from_seed(7);
|
||
let before: Vec<i32> = {
|
||
let mut probe = parent.clone();
|
||
(0..16).map(|_| probe.range(0, 1000)).collect()
|
||
};
|
||
// Forking should leave `parent`'s stream untouched.
|
||
let _child = parent.fork("whatever");
|
||
let after: Vec<i32> = (0..16).map(|_| parent.range(0, 1000)).collect();
|
||
assert_eq!(before, after);
|
||
}
|
||
|
||
/// Distinct labels produce distinct streams.
|
||
#[test]
|
||
fn distinct_labels_diverge() {
|
||
let parent = Rng::from_seed(42);
|
||
let mut a = parent.fork("a");
|
||
let mut b = parent.fork("b");
|
||
let seq_a: Vec<i32> = (0..32).map(|_| a.range(0, 1_000_000)).collect();
|
||
let seq_b: Vec<i32> = (0..32).map(|_| b.range(0, 1_000_000)).collect();
|
||
assert_ne!(seq_a, seq_b);
|
||
}
|
||
|
||
/// The pipeline's occurrence-keying scheme works: `"name#0"` and `"name#1"`
|
||
/// must yield distinct streams.
|
||
#[test]
|
||
fn occurrence_keys_diverge() {
|
||
let parent = Rng::from_seed(2024);
|
||
let mut zero = parent.fork("name#0");
|
||
let mut one = parent.fork("name#1");
|
||
let seq_zero: Vec<i32> = (0..32).map(|_| zero.range(0, 1_000_000)).collect();
|
||
let seq_one: Vec<i32> = (0..32).map(|_| one.range(0, 1_000_000)).collect();
|
||
assert_ne!(seq_zero, seq_one);
|
||
}
|
||
|
||
/// `choose` on an empty slice returns `None`; on a non-empty slice it
|
||
/// returns an in-bounds element.
|
||
#[test]
|
||
fn choose_empty_and_nonempty() {
|
||
let mut rng = Rng::from_seed(5);
|
||
let empty: [i32; 0] = [];
|
||
assert_eq!(rng.choose(&empty), None);
|
||
|
||
let items = [10, 20, 30, 40];
|
||
for _ in 0..64 {
|
||
let picked = rng.choose(&items).copied();
|
||
assert!(picked.map(|v| items.contains(&v)).unwrap_or(false));
|
||
}
|
||
}
|
||
|
||
/// `shuffle` is a permutation: it preserves the multiset of elements.
|
||
#[test]
|
||
fn shuffle_is_a_permutation() {
|
||
let mut rng = Rng::from_seed(123);
|
||
let mut items: Vec<i32> = (0..50).collect();
|
||
let original = items.clone();
|
||
rng.shuffle(&mut items);
|
||
|
||
// Same multiset.
|
||
let mut sorted = items.clone();
|
||
sorted.sort_unstable();
|
||
assert_eq!(sorted, original);
|
||
|
||
// And the same shuffle reproduces under the same seed.
|
||
let mut rng2 = Rng::from_seed(123);
|
||
let mut items2: Vec<i32> = (0..50).collect();
|
||
rng2.shuffle(&mut items2);
|
||
assert_eq!(items, items2);
|
||
}
|
||
|
||
/// Tiny / empty slices are left untouched by `shuffle`.
|
||
#[test]
|
||
fn shuffle_trivial_slices() {
|
||
let mut rng = Rng::from_seed(1);
|
||
let mut empty: Vec<i32> = vec![];
|
||
rng.shuffle(&mut empty);
|
||
assert!(empty.is_empty());
|
||
|
||
let mut single = vec![42];
|
||
rng.shuffle(&mut single);
|
||
assert_eq!(single, vec![42]);
|
||
}
|
||
|
||
/// `range` honors the half-open convention and the degenerate `hi <= lo`
|
||
/// contract (returns `lo`, never panics).
|
||
#[test]
|
||
fn range_bounds_are_half_open() {
|
||
let mut rng = Rng::from_seed(77);
|
||
for _ in 0..256 {
|
||
let v = rng.range(3, 7);
|
||
assert!((3..7).contains(&v), "expected [3,7), got {v}");
|
||
}
|
||
// Degenerate ranges return `lo`.
|
||
assert_eq!(rng.range(5, 5), 5);
|
||
assert_eq!(rng.range(5, 2), 5);
|
||
// Negative bounds work too.
|
||
for _ in 0..256 {
|
||
let v = rng.range(-5, -1);
|
||
assert!((-5..-1).contains(&v), "expected [-5,-1), got {v}");
|
||
}
|
||
}
|
||
|
||
/// `chance` saturates outside `[0, 1]` and is reproducible.
|
||
#[test]
|
||
fn chance_saturates_and_reproduces() {
|
||
let mut rng = Rng::from_seed(9);
|
||
assert!(!rng.chance(0.0));
|
||
assert!(!rng.chance(-1.0));
|
||
assert!(rng.chance(1.0));
|
||
assert!(rng.chance(2.0));
|
||
|
||
// p = 0.5 over many draws should land somewhere in the middle.
|
||
let mut a = Rng::from_seed(2);
|
||
let hits = (0..10_000).filter(|_| a.chance(0.5)).count();
|
||
assert!((4000..6000).contains(&hits), "0.5 chance produced {hits}/10000");
|
||
}
|
||
}
|