//! A fast hasher for the in-memory graphs (spec §25): their keys begin with
//! BLAKE3 hashes, so the bytes are already uniform and SipHash's cost buys
//! nothing. A per-process random seed keeps bucket placement unpredictable,
//! so keys chosen by someone else cannot be aimed at one bucket.

use std::hash::{BuildHasher, Hasher};
use std::sync::OnceLock;

fn seed() -> u64 {
    static SEED: OnceLock<u64> = OnceLock::new();
    *SEED.get_or_init(rand::random::<u64>)
}

/// Builds [`FastHasher`]s with the process seed.
#[derive(Clone, Copy, Debug)]
pub struct FastState(u64);

impl Default for FastState {
    fn default() -> FastState {
        FastState(seed())
    }
}

impl BuildHasher for FastState {
    type Hasher = FastHasher;
    fn build_hasher(&self) -> FastHasher {
        FastHasher(self.0)
    }
}

/// Folds each 8-byte word into the state with a multiply and rotate, then
/// finishes with SplitMix64's mixer so every input bit reaches every output bit.
pub struct FastHasher(u64);

impl FastHasher {
    #[inline]
    fn mix(&mut self, word: u64) {
        self.0 = (self.0 ^ word)
            .wrapping_mul(0x9e37_79b9_7f4a_7c15)
            .rotate_left(31);
    }
}

impl Hasher for FastHasher {
    #[inline]
    fn write(&mut self, bytes: &[u8]) {
        let mut chunks = bytes.chunks_exact(8);
        for c in &mut chunks {
            self.mix(u64::from_le_bytes(c.try_into().unwrap()));
        }
        let rest = chunks.remainder();
        if !rest.is_empty() {
            let mut b = [0u8; 8];
            b[..rest.len()].copy_from_slice(rest);
            self.mix(u64::from_le_bytes(b) ^ ((rest.len() as u64) << 59));
        }
    }

    #[inline]
    fn write_u8(&mut self, n: u8) {
        self.mix(n as u64 | 0x100);
    }

    #[inline]
    fn write_u32(&mut self, n: u32) {
        self.mix(n as u64 | 0x1_0000_0000);
    }

    #[inline]
    fn write_u64(&mut self, n: u64) {
        self.mix(n);
    }

    #[inline]
    fn write_usize(&mut self, n: usize) {
        self.mix(n as u64);
    }

    #[inline]
    fn finish(&self) -> u64 {
        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)
    }
}

pub type FastMap<K, V> = std::collections::HashMap<K, V, FastState>;
pub type FastSet<K> = std::collections::HashSet<K, FastState>;

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

    fn h<T: Hash + ?Sized>(state: &FastState, v: &T) -> u64 {
        state.hash_one(v)
    }

    #[test]
    fn distinct_keys_spread_and_equal_keys_agree() {
        let s = FastState(42);
        let a = ([7u8; 32], 1u32);
        assert_eq!(h(&s, &a), h(&s, &a));
        assert_ne!(h(&s, &a), h(&s, &([7u8; 32], 2u32)), "the index matters");
        assert_ne!(
            h(&s, &[1u8, 2, 3][..]),
            h(&s, &[1u8, 2, 3, 0][..]),
            "length matters"
        );
        // Consecutive indices of one change land in different buckets of a small table.
        let buckets: std::collections::HashSet<u64> =
            (0..64u32).map(|i| h(&s, &([9u8; 32], i)) & 63).collect();
        assert!(buckets.len() > 32, "{} of 64 buckets used", buckets.len());
        assert_ne!(
            h(&FastState(1), &a),
            h(&FastState(2), &a),
            "the seed matters"
        );
    }

    #[test]
    fn maps_work() {
        let mut m: FastMap<([u8; 32], u32), u32> = FastMap::default();
        for i in 0..10_000u32 {
            m.insert(([(i % 251) as u8; 32], i), i);
        }
        assert_eq!(m.len(), 10_000);
        assert_eq!(m[&([77u8; 32], 77)], 77);
    }
}