abnf-oracle 0.1.1

//! SplitMix64, inline (SCOPE.md 10, D15).
//!
//! The library target has no required dependencies, so the generator brings its own RNG. Any
//! small, well-specified generator would do; SplitMix64 is 40 lines, has no state beyond a
//! `u64`, and is published in enough places that the stream is easy to re-derive if this file
//! is ever lost.
//!
//! The determinism contract is per crate version (D15), but the stream is locked by the test
//! vectors below so that a refactor cannot change it by accident.

/// A SplitMix64 generator.
///
/// Deterministic from its seed, with a period of 2^64 and no correlation between nearby seeds
/// worth worrying about at this crate's scale.
#[derive(Clone, Debug)]
pub(crate) struct SplitMix64 {
    state: u64,
}

impl SplitMix64 {
    /// Creates a generator from a seed. Every `u64` is a valid seed, including zero.
    pub(crate) const fn new(seed: u64) -> Self {
        Self { state: seed }
    }

    /// Returns the next value in the stream.
    pub(crate) fn next_u64(&mut self) -> u64 {
        self.state = self.state.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.state;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }

    /// Returns a uniformly distributed value in `0..n`, or `0` when `n` is zero.
    ///
    /// Rejection sampling, not `% n`: modulo bias would be invisible in the output and would
    /// quietly skew both numeric-range selection and branch selection towards low values.
    pub(crate) fn below(&mut self, n: u64) -> u64 {
        if n <= 1 {
            return 0;
        }
        // Reject the unrepresentable tail so that every residue class has the same number of
        // preimages. `zone` is the largest multiple of `n` that fits, minus one.
        let zone = u64::MAX - (u64::MAX % n) - 1;
        loop {
            let value = self.next_u64();
            if value <= zone {
                return value % n;
            }
        }
    }

    /// Returns `true` or `false` with equal probability.
    ///
    /// Uses the high bit, which has the best avalanche behaviour of the word.
    pub(crate) fn bool(&mut self) -> bool {
        self.next_u64() >> 63 == 1
    }
}

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

    /// The published SplitMix64 stream for seed 0. These are not self-generated: they are the
    /// reference values the algorithm is known by, which is what makes this a conformance test
    /// rather than a snapshot of whatever this file happens to do.
    const SEED_0: [u64; 4] = [
        0xE220_A839_7B1D_CDAF,
        0x6E78_9E6A_A1B9_65F4,
        0x06C4_5D18_8009_454F,
        0xF88B_B8A8_724C_81EC,
    ];

    /// Seed 1, as a second anchor. Regression lock: generated by this implementation, whose
    /// seed-0 stream matches the reference above.
    const SEED_1: [u64; 4] = [
        0x910A_2DEC_8902_5CC1,
        0xBEEB_8DA1_658E_EC67,
        0xF893_A2EE_FB32_555E,
        0x71C1_8690_EE42_C90B,
    ];

    #[test]
    fn stream_matches_committed_vectors() {
        for (seed, expected) in [(0, SEED_0), (1, SEED_1)] {
            let mut rng = SplitMix64::new(seed);
            let actual: Vec<u64> = (0..4).map(|_| rng.next_u64()).collect();
            assert_eq!(actual, expected, "stream changed for seed {seed}");
        }
    }

    #[test]
    fn same_seed_gives_the_same_stream() {
        let mut a = SplitMix64::new(12345);
        let mut b = SplitMix64::new(12345);
        for _ in 0..100 {
            assert_eq!(a.next_u64(), b.next_u64());
        }
    }

    #[test]
    fn below_stays_in_range() {
        let mut rng = SplitMix64::new(7);
        for n in [1_u64, 2, 3, 10, 255, 1 << 32] {
            for _ in 0..200 {
                assert!(rng.below(n) < n, "below({n}) escaped its range");
            }
        }
    }

    #[test]
    fn below_degenerate_bounds_are_zero() {
        let mut rng = SplitMix64::new(0);
        assert_eq!(rng.below(0), 0);
        assert_eq!(rng.below(1), 0);
    }

    #[test]
    fn below_is_roughly_uniform() {
        // A smoke test for gross bias, not a statistical one. With 60_000 draws over 6 buckets,
        // each bucket should land near 10_000; a modulo-biased implementation over a small
        // range would not show up here, which is why correctness rests on the rejection loop
        // itself and this test only guards against something badly broken.
        let mut rng = SplitMix64::new(99);
        let mut buckets = [0_u32; 6];
        for _ in 0..60_000 {
            buckets[rng.below(6) as usize] += 1;
        }
        for (i, count) in buckets.iter().enumerate() {
            assert!(
                (8_500..11_500).contains(count),
                "bucket {i} got {count} of 60000 draws"
            );
        }
    }

    #[test]
    fn bool_is_balanced() {
        let mut rng = SplitMix64::new(4);
        let trues = (0..10_000).filter(|_| rng.bool()).count();
        assert!(
            (4_500..5_500).contains(&trues),
            "{trues} of 10000 were true"
        );
    }
}