JenkHash 0.1.6

//! Implementation of the SpookyHash algorithm.
//!
//! SpookyHash is a fast hash function designed by Bob Jenkins, optimized for modern
//! 64-bit processors. It can produce hash values of different sizes (32-bit, 64-bit,
//! or 128-bit) and is designed to be extremely fast while maintaining good distribution
//! properties. The name "Spooky" reflects its speed and efficiency.

use crate::extensions::ext_slice_u8::ExtSliceU8;

const SC_NUM_VARS: u8 = 12;
const SC_BLOCK_SIZE: u8 = SC_NUM_VARS * 8;
const SC_BUF_SIZE: u8 = 2 * SC_BLOCK_SIZE;
const SC_CONST: u64 = 0xdeadbeefdeadbeef;

/// A hasher implementing the SpookyHash algorithm.
///
/// SpookyHash is a 128-bit noncryptographic hash function designed by Bob Jenkins.
/// It is optimized for modern 64-bit processors and provides excellent performance
/// characteristics while maintaining strong distribution properties suitable for
/// checksums and hash table lookups.
///
/// The public API provides several hashing functions for different use cases:
///
/// - **[`hash128`](Self::hash128)** - Produces a 128-bit hash (two `u64` values).
///   This is the main function and automatically selects the optimal algorithm based
///   on message length.
///
/// - **[`hash64`](Self::hash64)** - Produces a 64-bit hash. A convenience function
///   that returns the first half of the 128-bit hash.
///
/// - **[`hash32`](Self::hash32)** - Produces a 32-bit hash. A convenience function
///   that returns the lower 32 bits of the 64-bit hash.
///
/// - **[`short`](Self::short)** - Optimized for short messages (typically less than
///   192 bytes). Can be called directly when you know the message is short.
///
/// All functions use seed values that can be used to produce different hash values
/// for the same input, useful for hash table implementations requiring multiple
/// hash functions.
///
/// # Examples
///
/// Hashing a message:
///
/// ```
/// use JenkHash::Spooky;
///
/// let message = b"The quick brown fox jumps over the lazy dog".repeat(6);
/// let (hash1, hash2) = Spooky::hash128(&message, 0, 0);
/// assert_eq!((hash1, hash2), (0x4F120CC64DAE2E36, 0xBAE002B3C64ED326));
/// ```
///
/// Using seeds for different hash values:
///
/// ```
/// use JenkHash::Spooky;
///
/// let data = b"hello world";
/// let (h1, h2) = Spooky::hash128(data, 0, 0);
/// let (h3, h4) = Spooky::hash128(data, 1, 2);
/// // Different seeds produce different hash values
/// assert_ne!((h1, h2), (h3, h4));
/// ```
///
/// Producing a 64-bit hash:
///
/// ```
/// use JenkHash::Spooky;
///
/// let hash = Spooky::hash64(b"hello world", 0);
/// assert_eq!(hash, 0x6F62EC31A409CFEA);
/// ```
///
/// Producing a 32-bit hash:
///
/// ```
/// use JenkHash::Spooky;
///
/// let hash = Spooky::hash32(b"The quick brown fox jumps over the lazy dog", 0);
/// assert_eq!(hash, 0x11D417BC);
/// ```
pub struct Spooky {}

const ALLOW_UNALIGNED_READS: bool = true;
impl Spooky {
    /// left rotate a 64-bit value by k bytes
    #[inline]
    const fn rot64(x: u64, k: i32) -> u64 {
        (x << k) | (x >> (64 - k))
    }
    #[inline]
    #[rustfmt::skip]
    const fn mix(data: [u64; 12], mut states: [u64; 12]) -> [u64; 12] {
        states[00] = states[00].wrapping_add(data[00]); states[02] ^= states[10]; states[11] ^= states[00]; states[00] = Self::rot64(states[00],11); states[11] = states[11].wrapping_add(states[01]);
        states[01] = states[01].wrapping_add(data[01]); states[03] ^= states[11]; states[00] ^= states[01]; states[01] = Self::rot64(states[01],32); states[00] = states[00].wrapping_add(states[02]);
        states[02] = states[02].wrapping_add(data[02]); states[04] ^= states[00]; states[01] ^= states[02]; states[02] = Self::rot64(states[02],43); states[01] = states[01].wrapping_add(states[03]);
        states[03] = states[03].wrapping_add(data[03]); states[05] ^= states[01]; states[02] ^= states[03]; states[03] = Self::rot64(states[03],31); states[02] = states[02].wrapping_add(states[04]);
        states[04] = states[04].wrapping_add(data[04]); states[06] ^= states[02]; states[03] ^= states[04]; states[04] = Self::rot64(states[04],17); states[03] = states[03].wrapping_add(states[05]);
        states[05] = states[05].wrapping_add(data[05]); states[07] ^= states[03]; states[04] ^= states[05]; states[05] = Self::rot64(states[05],28); states[04] = states[04].wrapping_add(states[06]);
        states[06] = states[06].wrapping_add(data[06]); states[08] ^= states[04]; states[05] ^= states[06]; states[06] = Self::rot64(states[06],39); states[05] = states[05].wrapping_add(states[07]);
        states[07] = states[07].wrapping_add(data[07]); states[09] ^= states[05]; states[06] ^= states[07]; states[07] = Self::rot64(states[07],57); states[06] = states[06].wrapping_add(states[08]);
        states[08] = states[08].wrapping_add(data[08]); states[10] ^= states[06]; states[07] ^= states[08]; states[08] = Self::rot64(states[08],55); states[07] = states[07].wrapping_add(states[09]);
        states[09] = states[09].wrapping_add(data[09]); states[11] ^= states[07]; states[08] ^= states[09]; states[09] = Self::rot64(states[09],54); states[08] = states[08].wrapping_add(states[10]);
        states[10] = states[10].wrapping_add(data[10]); states[00] ^= states[08]; states[09] ^= states[10]; states[10] = Self::rot64(states[10],22); states[09] = states[09].wrapping_add(states[11]);
        states[11] = states[11].wrapping_add(data[11]); states[01] ^= states[09]; states[10] ^= states[11]; states[11] = Self::rot64(states[11],46); states[10] = states[10].wrapping_add(states[00]);

        states
    }
    #[inline]
    #[rustfmt::skip]
    const fn end_partial(mut states: [u64; 12]) -> [u64; 12] {
        states[11] = states[11].wrapping_add(states[01]); states[02] ^= states[11]; states[01] = Self::rot64(states[01], 44);
        states[00] = states[00].wrapping_add(states[02]); states[03] ^= states[00]; states[02] = Self::rot64(states[02], 15);
        states[01] = states[01].wrapping_add(states[03]); states[04] ^= states[01]; states[03] = Self::rot64(states[03], 34);
        states[02] = states[02].wrapping_add(states[04]); states[05] ^= states[02]; states[04] = Self::rot64(states[04], 21);
        states[03] = states[03].wrapping_add(states[05]); states[06] ^= states[03]; states[05] = Self::rot64(states[05], 38);
        states[04] = states[04].wrapping_add(states[06]); states[07] ^= states[04]; states[06] = Self::rot64(states[06], 33);
        states[05] = states[05].wrapping_add(states[07]); states[08] ^= states[05]; states[07] = Self::rot64(states[07], 10);
        states[06] = states[06].wrapping_add(states[08]); states[09] ^= states[06]; states[08] = Self::rot64(states[08], 13);
        states[07] = states[07].wrapping_add(states[09]); states[10] ^= states[07]; states[09] = Self::rot64(states[09], 38);
        states[08] = states[08].wrapping_add(states[10]); states[11] ^= states[08]; states[10] = Self::rot64(states[10], 53);
        states[09] = states[09].wrapping_add(states[11]); states[00] ^= states[09]; states[11] = Self::rot64(states[11], 42);
        states[10] = states[10].wrapping_add(states[00]); states[01] ^= states[10]; states[00] = Self::rot64(states[00], 54);

        states
    }
    #[inline]
    const fn end(mut states: [u64; 12]) -> [u64; 12] {
        states = Self::end_partial(states);
        states = Self::end_partial(states);
        states = Self::end_partial(states);

        states
    }
    #[inline]
    #[rustfmt::skip]
    const fn short_mix(mut states: [u64; 4]) -> [u64; 4] {
        states[2] = Self::rot64(states[2], 50);  states[2] = states[2].wrapping_add(states[3]);  states[0] ^= states[2];
        states[3] = Self::rot64(states[3], 52);  states[3] = states[3].wrapping_add(states[0]);  states[1] ^= states[3];
        states[0] = Self::rot64(states[0], 30);  states[0] = states[0].wrapping_add(states[1]);  states[2] ^= states[0];
        states[1] = Self::rot64(states[1], 41);  states[1] = states[1].wrapping_add(states[2]);  states[3] ^= states[1];
        states[2] = Self::rot64(states[2], 54);  states[2] = states[2].wrapping_add(states[3]);  states[0] ^= states[2];
        states[3] = Self::rot64(states[3], 48);  states[3] = states[3].wrapping_add(states[0]);  states[1] ^= states[3];
        states[0] = Self::rot64(states[0], 38);  states[0] = states[0].wrapping_add(states[1]);  states[2] ^= states[0];
        states[1] = Self::rot64(states[1], 37);  states[1] = states[1].wrapping_add(states[2]);  states[3] ^= states[1];
        states[2] = Self::rot64(states[2], 62);  states[2] = states[2].wrapping_add(states[3]);  states[0] ^= states[2];
        states[3] = Self::rot64(states[3], 34);  states[3] = states[3].wrapping_add(states[0]);  states[1] ^= states[3];
        states[0] = Self::rot64(states[0], 05);  states[0] = states[0].wrapping_add(states[1]);  states[2] ^= states[0];
        states[1] = Self::rot64(states[1], 36);  states[1] = states[1].wrapping_add(states[2]);  states[3] ^= states[1];

        states
    }
    #[inline]
    #[rustfmt::skip]
    const fn short_end(mut states: [u64; 4]) -> [u64; 4] {
        states[3] ^= states[2];  states[2] = Self::rot64(states[2], 15);  states[3] = states[3].wrapping_add(states[2]);
        states[0] ^= states[3];  states[3] = Self::rot64(states[3], 52);  states[0] = states[0].wrapping_add(states[3]);
        states[1] ^= states[0];  states[0] = Self::rot64(states[0], 26);  states[1] = states[1].wrapping_add(states[0]);
        states[2] ^= states[1];  states[1] = Self::rot64(states[1], 51);  states[2] = states[2].wrapping_add(states[1]);
        states[3] ^= states[2];  states[2] = Self::rot64(states[2], 28);  states[3] = states[3].wrapping_add(states[2]);
        states[0] ^= states[3];  states[3] = Self::rot64(states[3], 09);  states[0] = states[0].wrapping_add(states[3]);
        states[1] ^= states[0];  states[0] = Self::rot64(states[0], 47);  states[1] = states[1].wrapping_add(states[0]);
        states[2] ^= states[1];  states[1] = Self::rot64(states[1], 54);  states[2] = states[2].wrapping_add(states[1]);
        states[3] ^= states[2];  states[2] = Self::rot64(states[2], 32);  states[3] = states[3].wrapping_add(states[2]);
        states[0] ^= states[3];  states[3] = Self::rot64(states[3], 25);  states[0] = states[0].wrapping_add(states[3]);
        states[1] ^= states[0];  states[0] = Self::rot64(states[0], 63);  states[1] = states[1].wrapping_add(states[0]);

        states
    }

    /// Computes a 128-bit hash for short messages.
    ///
    /// This function is optimized for messages that are typically less than 192 bytes,
    /// though it can handle messages of any length. It is used internally by
    /// [`hash128`](Self::hash128) for short messages, but can also be called directly
    /// when you know the message is short and want to avoid the length check overhead.
    ///
    /// # Arguments
    ///
    /// * `data` - The byte slice to hash
    /// * `seed1` - The first seed value (can be 0 or a previous hash value for chaining)
    /// * `seed2` - The second seed value (can be 0 or a previous hash value for chaining)
    ///
    /// # Returns
    ///
    /// A tuple of two `u64` values representing the 128-bit hash: `(hash1, hash2)`.
    ///
    /// # Examples
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let (hash1, hash2) = Spooky::short(b"The quick brown fox jumps over the lazy dog", 0, 0);
    /// assert_eq!((hash1, hash2), (0x3E4A0F8311D417BC, 0xEE491890D39F45EB));
    /// ```
    ///
    /// Chaining hash values:
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let (h1, h2) = Spooky::short(b"first", 0, 0);
    /// let (h3, h4) = Spooky::short(b"second", h1, h2);
    /// ```
    pub fn short(mut data: &[u8], mut seed1: u64, mut seed2: u64) -> (u64, u64) {
        let starting_length = data.len();
        let mut remainder: usize = data.len() % 32;
        let mut states = [seed1, seed2, SC_CONST, SC_CONST];

        if starting_length > 15 {
            let chunks = data.chunks_exact(32);
            for chunk in chunks {
                states[2] = states[2].wrapping_add(chunk[8 * 0..].read_u64_unchecked());
                states[3] = states[3].wrapping_add(chunk[8 * 1..].read_u64_unchecked());
                states = Self::short_mix(states);
                states[0] = states[0].wrapping_add(chunk[8 * 2..].read_u64_unchecked());
                states[1] = states[1].wrapping_add(chunk[8 * 3..].read_u64_unchecked());
                data = &data[8 * 4..]
            }

            if remainder >= 16 {
                states[2] = states[2].wrapping_add(data[8 * 0..].read_u64_unchecked());
                states[3] = states[3].wrapping_add(data[8 * 1..].read_u64_unchecked());
                states = Self::short_mix(states);

                data = &data[8 * 2..];
                remainder = remainder.wrapping_sub(16);
            }
        }

        states[3] = (starting_length as u64) << 56;

        if remainder == 15 {
            states[3] = states[3].wrapping_add((data[14] as u64) << 48)
        }
        if (14..=15).contains(&remainder) {
            states[3] = states[3].wrapping_add((data[13] as u64) << 40)
        }
        if (13..=15).contains(&remainder) {
            states[3] = states[3].wrapping_add((data[12] as u64) << 32)
        }
        if (12..=15).contains(&remainder) {
            states[3] = states[3].wrapping_add(data[4 * 2..].read_u32_unchecked() as u64);
            states[2] = states[2].wrapping_add(data[8 * 0..].read_u64_unchecked());
        }
        if remainder == 11 {
            states[3] = states[3].wrapping_add((data[10] as u64) << 16);
        }
        if (10..=11).contains(&remainder) {
            states[3] = states[3].wrapping_add((data[09] as u64) << 8);
        }
        if (09..=11).contains(&remainder) {
            states[3] = states[3].wrapping_add((data[08] as u64));
        }
        if (08..=11).contains(&remainder) {
            states[2] = states[2].wrapping_add(data[8 * 0..].read_u64_unchecked());
        }
        if remainder == 07 {
            states[2] = states[2].wrapping_add((data[06] as u64) << 48)
        }
        if (06..=07).contains(&remainder) {
            states[2] = states[2].wrapping_add((data[05] as u64) << 40)
        }
        if (05..=07).contains(&remainder) {
            states[2] = states[2].wrapping_add((data[04] as u64) << 32)
        }
        if (04..=07).contains(&remainder) {
            states[2] = states[2].wrapping_add(data[4 * 0..].read_u32_unchecked() as u64);
        }
        if remainder == 03 {
            states[2] = states[2].wrapping_add((data[02] as u64) << 16)
        }
        if (02..=03).contains(&remainder) {
            states[2] = states[2].wrapping_add((data[01] as u64) << 8)
        }
        if (01..=03).contains(&remainder) {
            states[2] = states[2].wrapping_add((data[00] as u64))
        }
        if remainder == 00 {
            states[2] = states[2].wrapping_add(SC_CONST);
            states[3] = states[3].wrapping_add(SC_CONST);
        }

        states = Self::short_end(states);

        (states[0], states[1])
    }

    /// Computes a 128-bit hash for messages of any length.
    ///
    /// This is the main hashing function for SpookyHash. It automatically selects
    /// the optimal algorithm based on message length:
    ///
    /// - For messages shorter than 192 bytes, it delegates to [`short`](Self::short)
    ///   for optimal performance.
    /// - For longer messages, it uses a more sophisticated algorithm that processes
    ///   data in blocks for maximum throughput.
    ///
    /// The function produces a 128-bit hash value suitable for hash tables, checksums,
    /// and other applications requiring fast, well-distributed hash values.
    ///
    /// # Arguments
    ///
    /// * `data` - The byte slice to hash
    /// * `seed1` - The first seed value (can be 0 or a previous hash value for chaining)
    /// * `seed2` - The second seed value (can be 0 or a previous hash value for chaining)
    ///
    /// # Returns
    ///
    /// A tuple of two `u64` values representing the 128-bit hash: `(hash1, hash2)`.
    ///
    /// # Examples
    ///
    /// Hashing a short message:
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let (hash1, hash2) = Spooky::hash128(b"hello world", 0, 0);
    /// ```
    ///
    /// Hashing a longer message:
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let message = b"The quick brown fox jumps over the lazy dog".repeat(6);
    /// let (hash1, hash2) = Spooky::hash128(&message, 0, 0);
    /// assert_eq!((hash1, hash2), (0x4F120CC64DAE2E36, 0xBAE002B3C64ED326));
    /// ```
    ///
    /// Using seeds for different hash values:
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let data = b"example data";
    /// let (h1, h2) = Spooky::hash128(data, 0, 0);
    /// let (h3, h4) = Spooky::hash128(data, 1, 2);
    /// // Different seeds produce different hash values
    /// assert_ne!((h1, h2), (h3, h4));
    /// ```
    #[rustfmt::skip]
    pub fn hash128(mut input: &[u8], mut seed1: u64, mut seed2: u64) -> (u64, u64) {
        if input.len() < SC_BUF_SIZE as usize {
            return Self::short(input, seed1, seed2);
        }

        let mut states = [seed1, seed2, SC_CONST, seed1, seed2, SC_CONST, seed1, seed2, SC_CONST, seed1, seed2, SC_CONST];

        let chunks = input.chunks_exact((SC_BLOCK_SIZE) as usize);
        let remaining_data = chunks.remainder();

        if ALLOW_UNALIGNED_READS || (input.as_ptr() as usize & 7 == 0) {
            for chunk in chunks {
                states = Self::mix([
                    chunk[8 * 00..].read_u64_unchecked(), chunk[8 * 01..].read_u64_unchecked(),
                    chunk[8 * 02..].read_u64_unchecked(), chunk[8 * 03..].read_u64_unchecked(),
                    chunk[8 * 04..].read_u64_unchecked(), chunk[8 * 05..].read_u64_unchecked(),
                    chunk[8 * 06..].read_u64_unchecked(), chunk[8 * 07..].read_u64_unchecked(),
                    chunk[8 * 08..].read_u64_unchecked(), chunk[8 * 09..].read_u64_unchecked(),
                    chunk[8 * 10..].read_u64_unchecked(), chunk[8 * 11..].read_u64_unchecked(),
                ], states);
            }
        } else {todo!()}

        let mut remainder = [0u8; SC_NUM_VARS as usize * size_of::<u64>()];
        remainder[..remaining_data.len()].copy_from_slice(remaining_data);
        remainder[(SC_BLOCK_SIZE as usize)-1] = remaining_data.len() as u8;

        states = Self::mix([
            remainder[8 * 00..].read_u64_unchecked(), remainder[8 * 01..].read_u64_unchecked(),
            remainder[8 * 02..].read_u64_unchecked(), remainder[8 * 03..].read_u64_unchecked(),
            remainder[8 * 04..].read_u64_unchecked(), remainder[8 * 05..].read_u64_unchecked(),
            remainder[8 * 06..].read_u64_unchecked(), remainder[8 * 07..].read_u64_unchecked(),
            remainder[8 * 08..].read_u64_unchecked(), remainder[8 * 09..].read_u64_unchecked(),
            remainder[8 * 10..].read_u64_unchecked(), remainder[8 * 11..].read_u64_unchecked(),
        ], states);

        states = Self::end(states);

        (states[0], states[1])
    }

    /// Computes a 64-bit hash for messages of any length.
    ///
    /// This is a convenience function that produces a 64-bit hash value by computing
    /// the full 128-bit hash and returning the first 64 bits. It provides the same
    /// performance characteristics as [`hash128`](Self::hash128) but returns a
    /// single value for simpler use cases.
    ///
    /// # Arguments
    ///
    /// * `input` - The byte slice to hash
    /// * `seed1` - The seed value (can be 0 or a previous hash value for chaining)
    ///
    /// # Returns
    ///
    /// A 64-bit hash value.
    ///
    /// # Examples
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let hash = Spooky::hash64(b"hello world", 0);
    /// ```
    ///
    /// Using a seed:
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let hash1 = Spooky::hash64(b"data", 0);
    /// let hash2 = Spooky::hash64(b"data", 1);
    /// // Different seeds produce different hash values
    /// assert_ne!(hash1, hash2);
    /// ```
    pub fn hash64(input: &[u8], seed1: u64) -> u64 {
        let (seed, _) = Self::hash128(input, seed1, seed1);
        seed
    }

    /// Computes a 32-bit hash for messages of any length.
    ///
    /// This is a convenience function that produces a 32-bit hash value by computing
    /// the full 128-bit hash and returning the lower 32 bits. It provides the same
    /// performance characteristics as [`hash128`](Self::hash128) but returns a
    /// single 32-bit value for use cases that don't require the full hash width.
    ///
    /// # Arguments
    ///
    /// * `input` - The byte slice to hash
    /// * `seed1` - The seed value (can be 0 or a previous hash value for chaining)
    ///
    /// # Returns
    ///
    /// A 32-bit hash value.
    ///
    /// # Examples
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let hash = Spooky::hash32(b"The quick brown fox jumps over the lazy dog", 0);
    /// assert_eq!(hash, 0x11D417BC);
    /// ```
    ///
    /// Using a seed:
    ///
    /// ```
    /// use JenkHash::Spooky;
    ///
    /// let hash1 = Spooky::hash32(b"data", 0);
    /// let hash2 = Spooky::hash32(b"data", 1);
    /// // Different seeds produce different hash values
    /// assert_ne!(hash1, hash2);
    /// ```
    pub fn hash32(input: &[u8], seed1: u32) -> u32 {
        let (seed, _) =Self::hash128(input, seed1 as u64, seed1 as u64);
        seed as u32
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{DEFAULT_TEST_STRING, Spooky};

    #[test]
    fn test_short_short() {
        let str = DEFAULT_TEST_STRING;
        let seed1 = 0;
        let seed2 = 0;

        let (seed1, seed2) = Spooky::short(str, seed1, seed2);

        assert_eq!((seed1, seed2), (0x3E4A0F8311D417BC, 0xEE491890D39F45EB))
    }

    #[test]
    fn test_short_long() {
        let str = DEFAULT_TEST_STRING.repeat(6);
        let seed1 = 0;
        let seed2 = 0;

        let (seed1, seed2) = Spooky::short(&*str, seed1, seed2);

        assert_eq!((seed1, seed2), (0x9120BB631D547D7E, 0x27791CE5610C03CC))
    }

    #[test]
    fn test_hash128_long() {
        let str = DEFAULT_TEST_STRING.repeat(6);
        let seed1 = 0;
        let seed2 = 0;

        let (seed1, seed2) = Spooky::hash128(&*str, seed1, seed2);

        assert_eq!((seed1, seed2), (0x4F120CC64DAE2E36, 0xBAE002B3C64ED326))
    }
    #[test]
    fn test_hash128_short() {
        let str = DEFAULT_TEST_STRING;
        let seed1 = 0;
        let seed2 = 0;

        let (seed1, seed2) = Spooky::hash128(&*str, seed1, seed2);

        assert_eq!((seed1, seed2), (0x3E4A0F8311D417BC, 0xEE491890D39F45EB))
    }
    
    #[test]
    fn test_hash32() {
        let str = DEFAULT_TEST_STRING;

        let seed = Spooky::hash32(&*str, 0);

        assert_eq!(seed, 0x11D417BC)
    }
}