//! The one source of randomness, written out rather than depended on.
//!
//! splitmix64, which is Steele/Lea/Flood's finaliser applied to a Weyl
//! sequence: add a fixed odd constant, then avalanche. Thirteen lines, no
//! state beyond the counter, and it is the algorithm `rand`'s own `SmallRng`
//! seeds from.
//!
//! It is here rather than taken from a crate for the same reason every pattern
//! in this binary is an automaton and not a drawing: what the backdrop shows
//! has to be something a reader can derive. A seeded stream that fits on a
//! screen is derivable. A dependency is a thing to trust.

pub(crate) struct Rng(u64);

impl Rng {
    pub(crate) fn new(seed: u64) -> Self {
        Self(seed)
    }

    pub(crate) fn next_u64(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }

    /// A fair coin. The top bit, because the finaliser's high bits are the
    /// ones it works hardest on.
    pub(crate) fn coin(&mut self) -> bool {
        self.next_u64() >> 63 == 1
    }

    /// Uniform over `0..n`, by Lemire's multiply-shift. Biased by at most
    /// `n / 2^64`, which for a screen coordinate is not a bias anyone can see;
    /// the rejection loop that would remove it is the only branch in this file
    /// whose running time is not fixed.
    pub(crate) fn below(&mut self, n: usize) -> usize {
        if n <= 1 {
            return 0;
        }
        ((u128::from(self.next_u64()) * n as u128) >> 64) as usize
    }
}

#[cfg(test)]
mod tests {
    use super::Rng;

    /// The published test vector for splitmix64 seeded at zero. If this drifts
    /// the generator has been edited into something else, and every `--seed`
    /// render in the test suite below is comparing against a different stream.
    #[test]
    fn the_stream_is_splitmix64() {
        let mut rng = Rng::new(0);
        assert_eq!(rng.next_u64(), 0xE220_A839_7B1D_CDAF);
        assert_eq!(rng.next_u64(), 0x6E78_9E6A_A1B9_65F4);
        assert_eq!(rng.next_u64(), 0x06C4_5D18_8009_454F);
    }

    /// `below` must stay inside the range it is given, including at the two
    /// sizes a one-column or one-row surface produces.
    #[test]
    fn below_stays_in_range() {
        let mut rng = Rng::new(12345);
        for n in [1usize, 2, 3, 80, 257] {
            for _ in 0..2000 {
                assert!(rng.below(n) < n, "below({n}) escaped its range");
            }
        }
        assert_eq!(rng.below(0), 0);
    }

    /// A coin that came up the same way every time would freeze 10 PRINT into
    /// diagonal stripes and seed Life with an empty board, and both failures
    /// look like a design choice rather than a broken generator.
    #[test]
    fn the_coin_is_not_stuck() {
        let mut rng = Rng::new(99);
        let heads = (0..10_000).filter(|_| rng.coin()).count();
        assert!(
            (4700..5300).contains(&heads),
            "10000 flips gave {heads} heads"
        );
    }
}