max / alloy

3.1 KB · 87 lines History Blame Raw

1	//! The one source of randomness, written out rather than depended on.
2	//!
3	//! splitmix64, which is Steele/Lea/Flood's finaliser applied to a Weyl
4	//! sequence: add a fixed odd constant, then avalanche. Thirteen lines, no
5	//! state beyond the counter, and it is the algorithm `rand`'s own `SmallRng`
6	//! seeds from.
7	//!
8	//! It is here rather than taken from a crate for the same reason every pattern
9	//! in this binary is an automaton and not a drawing: what the backdrop shows
10	//! has to be something a reader can derive. A seeded stream that fits on a
11	//! screen is derivable. A dependency is a thing to trust.
12
13	pub(crate) struct Rng(u64);
14
15	impl Rng {
16	pub(crate) fn new(seed: u64) -> Self {
17	Self(seed)
18	}
19
20	pub(crate) fn next_u64(&mut self) -> u64 {
21	self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
22	let mut z = self.0;
23	z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
24	z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
25	z ^ (z >> 31)
26	}
27
28	/// A fair coin. The top bit, because the finaliser's high bits are the
29	/// ones it works hardest on.
30	pub(crate) fn coin(&mut self) -> bool {
31	self.next_u64() >> 63 == 1
32	}
33
34	/// Uniform over `0..n`, by Lemire's multiply-shift. Biased by at most
35	/// `n / 2^64`, which for a screen coordinate is not a bias anyone can see;
36	/// the rejection loop that would remove it is the only branch in this file
37	/// whose running time is not fixed.
38	pub(crate) fn below(&mut self, n: usize) -> usize {
39	if n <= 1 {
40	return 0;
41	}
42	((u128::from(self.next_u64()) * n as u128) >> 64) as usize
43	}
44	}
45
46	#[cfg(test)]
47	mod tests {
48	use super::Rng;
49
50	/// The published test vector for splitmix64 seeded at zero. If this drifts
51	/// the generator has been edited into something else, and every `--seed`
52	/// render in the test suite below is comparing against a different stream.
53	#[test]
54	fn the_stream_is_splitmix64() {
55	let mut rng = Rng::new(0);
56	assert_eq!(rng.next_u64(), 0xE220_A839_7B1D_CDAF);
57	assert_eq!(rng.next_u64(), 0x6E78_9E6A_A1B9_65F4);
58	assert_eq!(rng.next_u64(), 0x06C4_5D18_8009_454F);
59	}
60
61	/// `below` must stay inside the range it is given, including at the two
62	/// sizes a one-column or one-row surface produces.
63	#[test]
64	fn below_stays_in_range() {
65	let mut rng = Rng::new(12345);
66	for n in [1usize, 2, 3, 80, 257] {
67	for _ in 0..2000 {
68	assert!(rng.below(n) < n, "below({n}) escaped its range");
69	}
70	}
71	assert_eq!(rng.below(0), 0);
72	}
73
74	/// A coin that came up the same way every time would freeze 10 PRINT into
75	/// diagonal stripes and seed Life with an empty board, and both failures
76	/// look like a design choice rather than a broken generator.
77	#[test]
78	fn the_coin_is_not_stuck() {
79	let mut rng = Rng::new(99);
80	let heads = (0..10_000).filter(\|_\| rng.coin()).count();
81	assert!(
82	(4700..5300).contains(&heads),
83	"10000 flips gave {heads} heads"
84	);
85	}
86	}
87