mock-upcloud 0.1.3

//! **The one generator, so a seed names a run forever.**
//!
//! SplitMix64 (Steele/Lea/Flood, 2014), thirty lines, in this crate rather than
//! behind a dependency. A seeded harness is only replayable if the STREAM is
//! stable, and a PRNG crate is free to change its stream in a minor release —
//! `rand` has done it twice. When the stream lives here, a seed printed by a
//! failing run in September still reproduces it in March.

/// A deterministic 64-bit stream. Cheap enough to make one per request.
#[derive(Clone, Debug)]
pub struct SplitMix64 {
    state: u64,
}

impl SplitMix64 {
    pub fn new(seed: u64) -> SplitMix64 {
        SplitMix64 { state: seed }
    }

    /// Derive an independent stream from this one and a label, so two features
    /// seeded from the same run never correlate. (`hash` is FNV-1a, also here,
    /// also for stream stability.)
    pub fn derive(seed: u64, label: &str) -> SplitMix64 {
        SplitMix64::new(seed ^ fnv1a(label))
    }

    pub 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)
    }

    /// Uniform in `[0, n)`. Rejection-sampled, not modulo: a modulo fold skews
    /// the low values, and a fault that fires 0.4 % too often is a fault whose
    /// measured rate is a lie.
    pub fn below(&mut self, n: u64) -> u64 {
        assert!(n > 0, "below(0)");
        let zone = u64::MAX - (u64::MAX % n) - 1;
        loop {
            let v = self.next_u64();
            if v <= zone {
                return v % n;
            }
        }
    }

    /// `true` with probability `num / den`.
    pub fn chance(&mut self, num: u64, den: u64) -> bool {
        self.below(den) < num
    }

    /// Uniform in `[lo, hi]` inclusive.
    pub fn range(&mut self, lo: u64, hi: u64) -> u64 {
        assert!(hi >= lo);
        lo + self.below(hi - lo + 1)
    }

    /// Fisher–Yates, so a shuffled address pool is a permutation and never
    /// hands the same address to two servers.
    pub fn shuffle<T>(&mut self, v: &mut [T]) {
        if v.len() < 2 {
            return;
        }
        for i in (1..v.len()).rev() {
            let j = self.below(i as u64 + 1) as usize;
            v.swap(i, j);
        }
    }
}

pub fn fnv1a(s: &str) -> u64 {
    let mut h: u64 = 0xcbf2_9ce4_8422_2325;
    for b in s.as_bytes() {
        h ^= *b as u64;
        h = h.wrapping_mul(0x1000_0000_01b3);
    }
    h
}

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

    /// The stream is the contract. If this test ever has to be updated, every
    /// seed ever printed by a failing run has stopped meaning anything.
    #[test]
    fn the_stream_is_pinned() {
        let mut r = SplitMix64::new(0);
        assert_eq!(r.next_u64(), 16294208416658607535);
        assert_eq!(r.next_u64(), 7960286522194355700);
        assert_eq!(r.next_u64(), 487617019471545679);
    }

    #[test]
    fn below_is_uniform_enough_to_measure_a_rate() {
        let mut r = SplitMix64::new(7);
        let mut hits = 0;
        for _ in 0..100_000 {
            if r.chance(1, 100) {
                hits += 1;
            }
        }
        // 1 % of 100 000 is 1 000; three sigma is ~94.
        assert!((900..=1100).contains(&hits), "{hits}");
    }

    #[test]
    fn shuffle_is_a_permutation() {
        let mut r = SplitMix64::new(3);
        let mut v: Vec<u32> = (0..64).collect();
        r.shuffle(&mut v);
        let mut back = v.clone();
        back.sort_unstable();
        assert_eq!(back, (0..64).collect::<Vec<_>>());
        assert_ne!(v, back, "a shuffle that is the identity is not a shuffle");
    }

    #[test]
    fn derive_decorrelates() {
        let mut a = SplitMix64::derive(99, "out_of_stock");
        let a = a.next_u64();
        let mut b = SplitMix64::derive(99, "price_reset");
        let b = b.next_u64();
        assert_ne!(a, b);
    }
}