kevy_hash/

lib.rs

//! kevy-hash — fast, well-distributed hashing for kevy's single-trust-domain
//! keyspace. Zero dependencies.
//!
//! std's `HashMap` is a hashbrown Swiss table (excellent — kevy keeps it) keyed
//! by `SipHash-1-3` (DoS-resistant, but a tax a single-threaded-per-shard
//! keyspace facing no adversarial cross-trust key collisions does not need).
//! This crate supplies the hasher that table should use instead: an FxHash-style
//! word-at-a-time absorb plus a murmur3 [`fmix64`] avalanche finalizer.
//!
//! Measured (via `kevy-store/examples/bench_keyspace.rs`): ~4× faster
//! hashing, ~1.2–2.8× faster GET-hit, ~1.1–1.7× faster GET-miss than
//! SipHash, with no clustering.
//! The finalizer is **essential** — the bare Fx absorb (no `fmix64`) clusters
//! 30–50× on low-entropy sequential keys like `"key:0".."key:99999"`.
//!
//! **Not DoS-resistant.** There is no random seed, so an attacker who can choose
//! keys *and* observe timing could force collisions. kevy's keyspace lives
//! inside one trust domain per shard, so this is the right trade; do not reuse
//! this hasher for maps fed untrusted, adversarially-chosen keys across a trust
//! boundary.
//!
//! ```
//! use kevy_hash::FxHashMap;
//!
//! let mut m: FxHashMap<Vec<u8>, u64> = FxHashMap::default();
//! m.insert(b"key".to_vec(), 1);
//! assert_eq!(m.get(b"key".as_slice()), Some(&1));
//! ```
#![forbid(unsafe_code)]
#![warn(missing_docs)]
#![cfg_attr(not(feature = "std"), no_std)]

#[cfg(feature = "alloc")]
extern crate alloc;

#[cfg(feature = "alloc")]
use alloc::vec::Vec;
use core::hash::{BuildHasherDefault, Hasher};
#[cfg(feature = "std")]
use std::collections::{HashMap, HashSet};

mod crc16;
pub use crc16::{crc16, key_hash_slot};

/// FxHash mixing constant (rustc's `rustc-hash` seed).
const SEED: u64 = 0x517c_c1b7_2722_0a95;
const ROTATE: u32 = 5;

/// murmur3 `fmix64` avalanche — spreads every input bit across all 64 output
/// bits. ~6 ALU ops, applied once on [`Hasher::finish`]. This is what the bare
/// Fx absorb lacks, and why it clusters without it.
/// # Examples
///
/// It is a bijection on `u64` — no two inputs collide — and it moves every
/// bit, which is exactly what the bare Fx absorb does not do:
///
/// ```
/// use kevy_hash::fmix64;
/// assert_ne!(fmix64(0), fmix64(1));
///
/// // One input bit flipped moves about half the output bits.
/// let moved = (fmix64(0) ^ fmix64(1)).count_ones();
/// assert_eq!(moved, 33);
/// assert!((16..48).contains(&moved), "avalanche moved {moved} bits");
/// ```
///
/// Zero is a fixed point — every step is a shift-xor or a multiply, and
/// each leaves zero alone. That is a property of murmur3's finalizer, not
/// a defect, and it is why the absorb seeds the state rather than starting
/// it empty:
///
/// ```
/// assert_eq!(kevy_hash::fmix64(0), 0);
/// ```
#[inline]
pub fn fmix64(mut h: u64) -> u64 {
    h ^= h >> 33;
    h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
    h ^= h >> 33;
    h = h.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
    h ^= h >> 33;
    h
}

#[inline]
fn mix(state: u64, word: u64) -> u64 {
    (state.rotate_left(ROTATE) ^ word).wrapping_mul(SEED)
}

/// Two-stream pipelined hash_bytes inspired by rustc-hash 2.x's design
/// (`rustc-hash/src/lib.rs#hash_bytes`). The key trick is keeping two
/// independent state words `s0` / `s1` updated via 64×64→128 widening
/// multiplication (one `mul`+`mulhi` on aarch64, one `mul` on x86_64),
/// XORing the two halves of the product to mix top with bottom. The two
/// streams are independent of each other in the bulk loop, so LLVM can
/// schedule them on two ALU ports per cycle.
///
/// Lengths ≤ 16: XOR-only absorb of two reads (start + end), then a
/// single `multiply_mix` of the two streams. The XOR-only absorb is fast
/// because there's no ALU dependency between the two reads.
///
/// Lengths > 16: per-16-byte iteration, `s1 <- multiply_mix(s0 ^ x,
/// CONST ^ y); s0 <- s1`. The `CONST` (digits of pi) prevents the
/// all-zeros input from collapsing.
///
/// Final mix: `multiply_mix(s0, s1) ^ len` — folds length in so that
/// `"abc"` and `"ab\0c"` hash differently (the XOR-only short path
/// doesn't distinguish length-by-position without this).
///
/// Then `fmix64` to give us the anti-clustering avalanche we need (the
/// rustc-hash design assumes its consumer mixes again; we don't, so we
/// avalanche ourselves — same property as the legacy [`FxHasher`] path).
#[inline]
// A byte-faithful transcription of rustc-hash 2.x's `hash_bytes`
// (verified identical for every length 0..200) with `fmix64` appended.
// Splitting it would diverge from the upstream it is checked against,
// which is the whole reason it can be checked at all. The reason given
// here used to be codegen, which is not one of the two classes the rule
// allows; this is the second one.
// LOC-WAIVER: vendored engine core — see the note above.
fn hash_bytes_pipelined(bytes: &[u8]) -> u64 {
    // Constants — digits of pi (matches rustc-hash 2.x for cross-bench
    // sanity; the actual choice doesn't matter beyond "non-zero, not
    // sharing structure with input distributions").
    const S1: u64 = 0x243f_6a88_85a3_08d3;
    const S2: u64 = 0x1319_8a2e_0370_7344;
    const ANTI_ZERO: u64 = 0xa409_3822_299f_31d0;
    let len = bytes.len();
    let mut s0 = S1;
    let mut s1 = S2;

    if len <= 16 {
        if len >= 8 {
            // Read first 8 and last 8 (may overlap when 8 ≤ len ≤ 15).
            s0 ^= u64::from_le_bytes(bytes[0..8].try_into().expect("the len >= 8 arm"));
            s1 ^= u64::from_le_bytes(bytes[len - 8..].try_into().expect("the len >= 8 arm"));
        } else if len >= 4 {
            s0 ^= u64::from(u32::from_le_bytes(bytes[0..4].try_into().expect("the len >= 4 arm")));
            s1 ^= u64::from(u32::from_le_bytes(
                bytes[len - 4..].try_into().expect("the len >= 4 arm"),
            ));
        } else if len > 0 {
            // 1-3 byte tail: form a 3-byte key (lo, mid, hi) that
            // distinguishes "ab" from "ba" etc.
            let lo = bytes[0];
            let mid = bytes[len / 2];
            let hi = bytes[len - 1];
            s0 ^= u64::from(lo);
            s1 ^= (u64::from(hi) << 8) | u64::from(mid);
        }
        // len == 0 falls through with s0 == S1, s1 == S2 unchanged.
    } else {
        // Bulk: drop the very last byte from the bulk slice so the suffix
        // 16 bytes can partially overlap with bulk's tail (this is what
        // rustc-hash 2.x does; it makes the suffix path uniform).
        let mut bulk = &bytes[..len - 1];
        while let Some((chunk, rest)) = bulk.split_first_chunk::<16>() {
            let x = u64::from_le_bytes(chunk[..8].try_into().expect("chunk is [u8; 16]"));
            let y = u64::from_le_bytes(chunk[8..].try_into().expect("chunk is [u8; 16]"));
            let t = multiply_mix(s0 ^ x, ANTI_ZERO ^ y);
            s0 = s1;
            s1 = t;
            bulk = rest;
        }
        // Suffix 16 bytes (may overlap with last bulk iter).
        let suffix = &bytes[len - 16..];
        s0 ^= u64::from_le_bytes(suffix[0..8].try_into().expect("suffix is the last 16 bytes"));
        s1 ^= u64::from_le_bytes(suffix[8..16].try_into().expect("suffix is the last 16 bytes"));
    }

    let folded = multiply_mix(s0, s1) ^ (len as u64);
    fmix64(folded)
}

/// 64×64→128 widening multiply, XOR'ing the two halves of the product.
/// Single `mul` on x86_64, one `mul`+one `mulhi` on aarch64. Mixes top and
/// bottom of the product so the entire output fluctuates with small
/// changes in the input.
#[inline]
fn multiply_mix(x: u64, y: u64) -> u64 {
    let full = u128::from(x).wrapping_mul(u128::from(y));
    let lo = full as u64;
    let hi = (full >> 64) as u64;
    lo ^ hi
}

/// Fast, well-distributed [`Hasher`] for kevy's keyspace. Word-at-a-time absorb
/// (FxHash-style) finished with [`fmix64`]. See the crate docs for the security
/// trade-off.
/// # Examples
///
/// ```
/// use core::hash::Hasher;
/// use kevy_hash::FxHasher;
///
/// let mut h = FxHasher::default();
/// h.write(b"user:1000");
/// let a = h.finish();
///
/// let mut h = FxHasher::default();
/// h.write(b"user:1001");
/// assert_ne!(a, h.finish(), "one byte apart must not share a hash");
/// ```
///
/// **The result depends on how the bytes were split across `write` calls.**
/// The absorb consumes each call word-at-a-time and handles that call's own
/// tail, so the same bytes delivered in different chunks land on different
/// values. This is inherited from FxHash and is not a defect, but it means
/// a hash is only comparable with one built the same way — feed a whole
/// key in one `write`:
///
/// ```
/// use core::hash::Hasher;
/// use kevy_hash::FxHasher;
///
/// let mut whole = FxHasher::default();
/// whole.write(b"abcdefgh");
///
/// let mut split = FxHasher::default();
/// split.write(b"abcd");
/// split.write(b"efgh");
/// assert_ne!(whole.finish(), split.finish());
/// ```
/// # Not injective over byte strings
///
/// The absorb consumes whole words and zero-extends a short tail, and
/// nothing folds in the total length — so distinct inputs share a value
/// in three families, all with the same cause:
///
/// * a zero-extended 1–3 byte tail is indistinguishable from a 4-byte
///   one: `"aaa"` and `"a\0\0\0aa"`;
/// * `mix(0, 0) == 0`, so leading zero words are absorbed with no
///   effect — `""`, `"\0\0\0\0"` and `"\0\0\0\0\0\0\0\0"` all hash to
///   **0**, and prefixing any key with four NULs leaves its hash
///   unchanged;
/// * a 4-byte tail and an 8-byte word with four trailing zeros agree.
///
/// Measured: over the 1,093 strings of length ≤ 6 from `{a, b, NUL}`,
/// **27 collision classes**. A uniform 64-bit hash on that many inputs
/// would be expected to produce none.
///
/// Whether it reaches you depends on how `Hash` feeds the bytes.
/// `Hash for [u8]` writes a length prefix, so `FxHashMap<Vec<u8>, _>`
/// and `FxHashMap<SmallBytes, _>` — everything kevy itself uses — are
/// unaffected, and the measurement above gives 0 classes for them.
/// `Hash for str` writes only a `0xff` terminator, so **`&str` and
/// `String` keys do reach it**, which is what the 27 are.
///
/// The fix is to fold the total length into [`Hasher::finish`], six
/// lines, and it changes every value this type produces — which the note
/// on [`KevyHash for [u8]`](KevyHash) says this path deliberately does
/// not do. That is an owner decision, still open. Until it is taken, this
/// section is here so the behaviour is chosen rather than discovered.
///
/// (One tempting non-fix, for the record: seeding the initial state to a
/// non-zero constant. Measured, it makes all three families *worse* —
/// 39 classes instead of 27 — because it removes the only case the
/// zero-absorption collapsed.)
#[derive(Debug, Default)]
pub struct FxHasher(u64);

impl Hasher for FxHasher {
    #[inline]
    fn finish(&self) -> u64 {
        fmix64(self.0)
    }

    #[inline]
    fn write(&mut self, mut bytes: &[u8]) {
        let mut state = self.0;
        while bytes.len() >= 8 {
            let word = u64::from_le_bytes(bytes[..8].try_into().expect("the len >= 8 loop guard"));
            state = mix(state, word);
            bytes = &bytes[8..];
        }
        if bytes.len() >= 4 {
            let word =
                u64::from(u32::from_le_bytes(bytes[..4].try_into().expect("the len >= 4 guard")));
            state = mix(state, word);
            bytes = &bytes[4..];
        }
        for &b in bytes {
            state = mix(state, u64::from(b));
        }
        self.0 = state;
    }

    // Fixed-width integer keys (e.g. connection-id maps) skip the byte loop.
    #[inline]
    fn write_u64(&mut self, i: u64) {
        self.0 = mix(self.0, i);
    }
    #[inline]
    fn write_usize(&mut self, i: usize) {
        self.0 = mix(self.0, i as u64);
    }
}

/// [`BuildHasher`](std::hash::BuildHasher) for [`FxHasher`]. Seedless, so equal
/// keys hash equally across instances and process runs.
///
/// ```
/// use std::hash::BuildHasher;
/// use kevy_hash::FxBuildHasher;
/// let (a, b) = (FxBuildHasher::default(), FxBuildHasher::default());
/// assert_eq!(a.hash_one(b"key"), b.hash_one(b"key"), "no per-instance seed");
/// ```
pub type FxBuildHasher = BuildHasherDefault<FxHasher>;

/// Single-call hashing for kevy's per-command hot path.
///
/// `std::hash::Hasher` is a state-machine API — every hash is `Hasher::default()`
/// → `write_*` → `finish`, with `BuildHasher` indirection on top. For
/// `kevy-map`'s open-addressing table the keyspace is a small handful of
/// well-known leaf types (`[u8]`, `u32`, `u64`, `i32`); we get a faster, inline-
/// friendly hash by exposing one method on each that produces the final mixed
/// 64-bit value in one go.
///
/// **The integer impls** agree with feeding the value through
/// [`FxHasher`] and calling `finish`, so for those the trait is a
/// dispatch shortcut and nothing more. **The `[u8]` impl does not** — it
/// takes the two-stream pipelined path, and its own documentation says
/// so.
///
/// That distinction used to be stated as "all impls must agree", forty
/// lines above the note admitting one of them does not. This is not a
/// typo to tidy: the sentence declared exactly the property that makes
/// mixing the two safe, so a caller who used `FxHashMap` in one place
/// and `kevy_hash()` in another and compared across them would have been
/// silently wrong, on the strength of a guarantee written here.
///
/// `kevy-map` consumes both the full hash (for bucket index) and its top
/// 7 bits (for the metadata byte).
/// # Examples
///
/// The point of the trait is that a leaf type hashes in one call, with no
/// `Hasher` to build and no dispatch to pay:
///
/// ```
/// use kevy_hash::KevyHash;
/// assert_ne!(1u64.kevy_hash(), 2u64.kevy_hash());
/// assert_ne!(b"a"[..].kevy_hash(), b"b"[..].kevy_hash());
/// ```
///
/// The integer impls agree with routing the same value through
/// [`FxHasher`], which is what lets the dispatch be cut without changing
/// the hash:
///
/// ```
/// use core::hash::Hasher;
/// use kevy_hash::{FxHasher, KevyHash};
///
/// let mut h = FxHasher::default();
/// h.write_u64(0x0123_4567_89ab_cdef);
/// assert_eq!(0x0123_4567_89ab_cdefu64.kevy_hash(), h.finish());
/// ```
///
/// # Implementing it
///
/// The trait is open: `kevy-map` keys a map by any `K: KevyHash + Eq`, so
/// a key type of your own implements it. An implementation must uphold:
///
/// * **Equal values hash equally.** `a == b` implies
///   `a.kevy_hash() == b.kevy_hash()`, as with [`core::hash::Hash`].
/// * **Borrowed forms agree.** If `K: Borrow<Q>` and a map of `K` is
///   looked up by `&Q`, then `k.kevy_hash() == k.borrow().kevy_hash()` —
///   the rule `Vec<u8>` and `[u8]` follow here.
/// * **Every bit moves.** `kevy-map` takes the bucket from the low bits
///   and a tag from the top seven, so a hash whose high bits barely vary
///   degrades lookups to a scan. Finishing with [`fmix64`] gives this.
///
/// A hash that breaks the first two loses entries; one that breaks the
/// third is slow but correct.
///
/// ```
/// use kevy_hash::{KevyHash, fmix64};
///
/// #[derive(PartialEq, Eq)]
/// struct Port(u16);
///
/// impl KevyHash for Port {
///     fn kevy_hash(&self) -> u64 {
///         fmix64(u64::from(self.0) | 1 << 32)
///     }
/// }
/// assert_ne!(Port(1).kevy_hash(), Port(2).kevy_hash());
/// ```
pub trait KevyHash {
    /// Compute the final mixed 64-bit hash of `self` in one call.
    ///
    /// ```
    /// use kevy_hash::KevyHash;
    /// let a = b"user:1".as_slice().kevy_hash();
    /// assert_eq!(a, b"user:1".to_vec().as_slice().kevy_hash(), "depends only on the bytes");
    /// assert_ne!(a, b"user:2".as_slice().kevy_hash());
    /// assert_ne!(1u64.kevy_hash(), 2u64.kevy_hash());
    /// ```
    fn kevy_hash(&self) -> u64;
}

impl KevyHash for [u8] {
    /// Byte-slice hash. Uses the **two-stream pipelined** path internally
    /// for ILP on the bench's 8-64 byte keyspace, closing the prior 1 ns
    /// gap vs rustc-hash 2.x's `hash_bytes`. The final `fmix64` retains
    /// the anti-clustering guarantee that the
    /// `no_catastrophic_clustering_on_low_entropy_keys` test enforces.
    ///
    /// Note: the result diverges from the legacy [`FxHasher`] absorb path —
    /// callers using `FxHashMap<Vec<u8>, _>` route through std's
    /// `Hash::hash → Hasher::write → finish` (the legacy single-stream
    /// path), which intentionally stays put for cross-instance hash
    /// stability with anything that depended on the v0.polish bit pattern.
    /// The `KevyHash for [u8]` impl is for one-call hot paths like
    /// `kevy-map::find_by_borrow`, which is the only one we measure.
    #[inline]
    fn kevy_hash(&self) -> u64 {
        hash_bytes_pipelined(self)
    }
}

#[cfg(feature = "alloc")]
impl KevyHash for Vec<u8> {
    #[inline]
    fn kevy_hash(&self) -> u64 {
        self.as_slice().kevy_hash()
    }
}

impl KevyHash for u64 {
    #[inline]
    fn kevy_hash(&self) -> u64 {
        fmix64(mix(0, *self))
    }
}

impl KevyHash for u32 {
    #[inline]
    fn kevy_hash(&self) -> u64 {
        fmix64(mix(0, u64::from(*self)))
    }
}

impl KevyHash for i32 {
    #[inline]
    fn kevy_hash(&self) -> u64 {
        // Sign-extend to u64 so equal i32 values hash the same as if widened
        // through the integer path; negatives' top bits still fmix64 away.
        fmix64(mix(0, i64::from(*self) as u64))
    }
}

impl KevyHash for usize {
    #[inline]
    fn kevy_hash(&self) -> u64 {
        fmix64(mix(0, *self as u64))
    }
}

/// A [`HashMap`] using [`FxHasher`] instead of SipHash.
///
/// ```
/// use kevy_hash::FxHashMap;
/// let mut m: FxHashMap<&str, u32> = FxHashMap::default();
/// m.insert("a", 1);
/// *m.entry("a").or_insert(0) += 1;
/// assert_eq!(m["a"], 2);
/// ```
#[cfg(feature = "std")]
pub type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;

/// A [`HashSet`] using [`FxHasher`] instead of SipHash.
///
/// ```
/// use kevy_hash::FxHashSet;
/// let s: FxHashSet<u64> = [1, 2, 2, 3].into_iter().collect();
/// assert_eq!(s.len(), 3);
/// assert!(s.contains(&2));
/// ```
#[cfg(feature = "std")]
pub type FxHashSet<T> = HashSet<T, FxBuildHasher>;

// Send and Sync are part of the public contract: a change that loses
// either fails to compile here rather than in a caller.
const _: () = {
    const fn send_sync<T: Send + Sync>() {}
    send_sync::<FxHasher>();
};

#[cfg(test)]
mod tests;