JenkHash 0.3.0

//! Implementation of the Lookup2 hash algorithm (Jenkins hash function).
//!
//! Lookup2, also known as the Jenkins hash function, is Bob Jenkins' original hash function
//! designed for hash tables. It provides good distribution properties and was widely used
//! before the introduction of Lookup3. The algorithm processes input data and produces
//! a 32-bit hash value.
//!
//! # Features
//!
//! - Fast hashing with good avalanche properties
//! - Multiple variants optimized for different use cases
//! - Compatible with the `digest` crate traits
//! - Supports both streaming and one-shot hashing
//!
//! # Quick Start
//!
//! ```
//! use digest::Digest;
//! use JenkHash::lookup2::{Lookup2, Hash3};
//!
//! // One-shot hashing
//! let hash = Lookup2::<Hash3>::digest(b"hello world");
//! let hash_value = u32::from_le_bytes(hash[..].try_into().unwrap());
//!
//! // Streaming hashing
//! let mut hasher = Lookup2::<Hash3>::new();
//! hasher.update(b"hello ");
//! hasher.update(b"world");
//! let hash = hasher.finalize();
//! ```

use core::marker::PhantomData;
use digest::{HashMarker, OutputSizeUser};
use digest::typenum::U4;

mod hash;
mod hash2;
mod hash3;

pub use hash::Hash;
pub use hash2::Hash2;
pub use hash3::Hash3;

const GOLDEN_RATIO: u32 = 0x9e3779b9;

/// A hasher implementing the Lookup2 (Jenkins hash) algorithm.
///
/// Lookup2 is a hash function designed for hash table implementations. It provides
/// good avalanche properties, ensuring that small changes in input produce significant
/// changes in the output hash value. Every bit of the input affects every bit of the
/// output, making it suitable for hash table lookups and similar applications.
///
/// This implementation provides three variants through type parameters:
///
/// - **[`Hash`]** - Byte-oriented variant that works on all machines. This is the
///   most portable version, processing input as a byte slice.
///
/// - **[`Hash2`]** - Word-oriented variant optimized for speed. Requires that all
///   machines have the same endianness and that input is provided as an array of
///   `u32` values. This variant is faster than [`Hash`] when you have word-aligned data.
///
/// - **[`Hash3`]** - Little-endian optimized variant. Faster than [`Hash`] and works
///   deterministically on all machines by always interpreting bytes as little-endian.
///   This variant handles both aligned and unaligned memory access efficiently.
///
/// # Examples
///
///
/// # Examples
///
/// Using the recommended little-endian optimized variant:
///
/// ```
/// use digest::Digest;
/// use JenkHash::lookup2::{Lookup2, Hash3};
///
/// let hash = Lookup2::<Hash3>::digest(b"hello world");
/// let hash_value = u32::from_le_bytes(hash[..].try_into().unwrap());
/// ```
///
/// Using the word-oriented variant for maximum performance with aligned data:
///
/// ```
/// use JenkHash::lookup2::{Lookup2, Hash2};
///
/// let data: [u32; 3] = [0x12345678, 0x9abcdef0, 0xdeadbeef];
/// let hash = Lookup2::<Hash2>::hash(&data, 0);
/// assert_eq!(hash, 0xA94E6CA0);
/// ```
pub struct Lookup2<T> {
    phantom_data: PhantomData<T>,

    total_length: usize,
    state: [u32; 3],
    rem: [u8; 12],
    rem_offset: u8,
}

impl<T> Lookup2<T> {
    /// Creates a new hasher with the specified seed value.
    ///
    /// # Arguments
    ///
    /// * `seed` - Initial seed value for the hash function
    ///
    /// # Examples
    ///
    /// ```
    /// use JenkHash::lookup2::{Lookup2, Hash3};
    /// let hasher = Lookup2::<Hash3>::from_seed(0xDEADBEEF);
    /// ```
    pub fn from_seed(seed: u32) -> Self {
        Self {
            phantom_data: Default::default(),
            total_length: 0,
            state: [GOLDEN_RATIO, GOLDEN_RATIO, seed],
            rem: Default::default(),
            rem_offset: 0,
        }
    }
}

impl<T> Default for Lookup2<T> {
    /// Creates a new hasher with a seed value of 0.
    fn default() -> Self {
        Self::from_seed(0)
    }
}

impl<T> Lookup2<T> {
    #[inline] #[rustfmt::skip]
    const fn mix(mut state: [u32; 3])  -> [u32; 3] {
        state[0] = state[0].wrapping_sub(state[1]).wrapping_sub(state[2]); state[0] ^= state[2] >> 13;
        state[1] = state[1].wrapping_sub(state[2]).wrapping_sub(state[0]); state[1] ^= state[0] << 08;
        state[2] = state[2].wrapping_sub(state[0]).wrapping_sub(state[1]); state[2] ^= state[1] >> 13;
        state[0] = state[0].wrapping_sub(state[1]).wrapping_sub(state[2]); state[0] ^= state[2] >> 12;
        state[1] = state[1].wrapping_sub(state[2]).wrapping_sub(state[0]); state[1] ^= state[0] << 16;
        state[2] = state[2].wrapping_sub(state[0]).wrapping_sub(state[1]); state[2] ^= state[1] >> 05;
        state[0] = state[0].wrapping_sub(state[1]).wrapping_sub(state[2]); state[0] ^= state[2] >> 03;
        state[1] = state[1].wrapping_sub(state[2]).wrapping_sub(state[0]); state[1] ^= state[0] << 10;
        state[2] = state[2].wrapping_sub(state[0]).wrapping_sub(state[1]); state[2] ^= state[1] >> 15;
        state
    }
    #[inline] #[rustfmt::skip]
    const fn mix2(mut state: [u32; 3]) -> [u32; 3] {
        state[0] = state[0].wrapping_sub(state[1]).wrapping_sub(state[2]); state[0] ^= (state[2] >> 13);
        state[1] = state[1].wrapping_sub(state[2]).wrapping_sub(state[0]); state[1] ^= (state[0] <<  08);
        state[2] = state[2].wrapping_sub(state[0]).wrapping_sub(state[1]); state[2] ^= (state[1] & 0xffffffff) >> 13;
        state[0] = state[0].wrapping_sub(state[1]).wrapping_sub(state[2]); state[0] ^= (state[2] & 0xffffffff) >> 12;
        state[1] = state[1].wrapping_sub(state[2]).wrapping_sub(state[0]); state[1]  = (state[1] ^ (state[0] << 16)) & 0xffffffff;
        state[2] = state[2].wrapping_sub(state[0]).wrapping_sub(state[1]); state[2]  = (state[2] ^ (state[1] >>  5)) & 0xffffffff;
        state[0] = state[0].wrapping_sub(state[1]).wrapping_sub(state[2]); state[0]  = (state[0] ^ (state[2] >>  3)) & 0xffffffff;
        state[1] = state[1].wrapping_sub(state[2]).wrapping_sub(state[0]); state[1]  = (state[1] ^ (state[0] << 10)) & 0xffffffff;
        state[2] = state[2].wrapping_sub(state[0]).wrapping_sub(state[1]); state[2]  = (state[2] ^ (state[1] >> 15)) & 0xffffffff;
        state
    }
}

impl<T> HashMarker for Lookup2<T> {}
impl<T> OutputSizeUser for Lookup2<T> {
    type OutputSize = U4;
}



#[cfg(test)]
mod tests {
    use super::*;
    use digest::Digest;
    use crate::lookup2::hash3::Hash3;
    use crate::lookup2::hash2::Hash2;
    use crate::lookup2::hash::Hash;

    #[test]
    fn test_driver1_hash() {
        const EXPECTED: [u32; 256] = [
            0xBD49D10D, 0xA8AD3ABE, 0xF740E718, 0x18842F2C, 0x36BF9A03, 0x2DB2EEC7, 0xCF41BF0F,
            0xE3E7616E, 0xCF8C905B, 0xB8A9655C, 0x39FA335F, 0xFE945A0F, 0x3C6E8F66, 0x3773286C,
            0x201A2917, 0xC3BB9409, 0x8268CFDC, 0x17E17652, 0x93C76616, 0xD1922560, 0x64D34B59,
            0x24CA629, 0x1CB85985, 0xD98C5F19, 0x79B02A5, 0x30FFB50B, 0x2237FB68, 0xCE359FAE,
            0x2166B6B2, 0x8B7389F5, 0xE2EAC1E, 0x150E0833, 0x9FE7E4A1, 0xE7AACF45, 0x91AF5F9D,
            0x5DBC90EC, 0x4596AF00, 0x13A035E6, 0xAFEF6546, 0xE8B338E5, 0x74CAB39A, 0x72886F4F,
            0x479BE9DA, 0x4AF17BFD, 0x461B5BB7, 0x544778F, 0xC872D347, 0x9DE3205, 0x57FA2715,
            0x5027A995, 0x5F697158, 0x724FAFC5, 0x1E5BEDF5, 0x8A568091, 0x89D365C4, 0x82C8734F,
            0x4928DED8, 0xA402313F, 0xA8F4C06F, 0x35EFA6F8, 0xF10E6D62, 0x5C2AE4D8, 0x658E21EC,
            0x20DE7E60, 0x7A2A2572, 0x2065E4CF, 0xEB3DC16D, 0xC10F6869, 0xBDCD0FA3, 0x9702436,
            0x3196C9C1, 0xFDC7B9E2, 0x1D03F572, 0x53532729, 0xF0F9FDA6, 0xA3A63790, 0xFDC17D9D,
            0xA9DE6AF7, 0xB18373F3, 0x64AFC40B, 0xD0F07F0C, 0x23139D0A, 0x8141B068, 0x3D4322B7,
            0x550100C2, 0x3CB67A3A, 0x26C6C12C, 0x14181C5D, 0xAAE4C5F9, 0x274A92BC, 0xBA8FB0B4,
            0xF42FC6D3, 0xDB9B652C, 0x8ACBD43C, 0x8C08CBB1, 0xA84F24D7, 0x31F8A7F5, 0x57A0339A,
            0x8DE4ECDB, 0x23F51123, 0xE40005F7, 0x89BB5CAC, 0xA1E55F5, 0xEAC24E75, 0xA5C0866A,
            0xDF15B2CF, 0xA27D2BFD, 0x15A334B, 0xACE985CF, 0xA2B0B0EF, 0x672779FC, 0xEE3CCB17,
            0x48CF8831, 0xD884A85A, 0xD55BBF57, 0x5C38B259, 0xFE2A5A50, 0x2D8BB795, 0x714F931E,
            0x6B69A8E8, 0xC3841005, 0xBC4055CE, 0x21CC4C88, 0x716A7B5F, 0x7E6C0EA0, 0xCA44FC13,
            0x4F45BF3C, 0x30221FC, 0xAE659497, 0xDE707C30, 0x8B7B85AC, 0x52AC443C, 0x49656692,
            0x4F9847E8, 0x5BB37380, 0x64053C4, 0xC1E1ED23, 0xC11BA687, 0x980D3B40, 0x498BCD7E,
            0x82D87194, 0x809A33DB, 0xEAEECFFB, 0x8E173880, 0x41A883DA, 0xEEDD5CF7, 0x9730EF35,
            0xE9DDF853, 0x1A32A45, 0x71495610, 0x620ED714, 0xF0744E38, 0x263E7640, 0x51D858F3,
            0x59F6E95, 0x992370D8, 0x9B40E501, 0x3D7EBC52, 0xAD0C2258, 0xDE91D838, 0xA404BE60,
            0x2D4CF2F1, 0x9FA45F8F, 0x6C43A040, 0xB40A4828, 0x1FFC8759, 0x7D470AA2, 0x9D9A605B,
            0x341C8F4C, 0xF7FE1CB3, 0x7D3F2B85, 0xEBCF0FAB, 0x7947B905, 0xF5BCB5D0, 0x1709D367,
            0xDFC125DE, 0x5EA71F3F, 0xCBF758B1, 0x51151FD3, 0x71DF9A9C, 0xA6AEB5F8, 0xCD8F96D,
            0xC487ADE1, 0xB27418EF, 0xBE19E05D, 0x4B681783, 0x1F6EBD98, 0xC3AF6B94, 0x949A062B,
            0xFE27BB6B, 0xBD7AF8A3, 0x8F9CA5BA, 0x224EA48D, 0x50F09154, 0x6D3A6EFB, 0xDD502443,
            0x457BB0EF, 0xD2B71E48, 0xC1BE08B5, 0xC2F614D2, 0xF44F1A28, 0x17751F62, 0xA253DC8F,
            0x7F7FB970, 0x9EAF27B7, 0x5624BF66, 0xF9B5227, 0xAE2BC15E, 0xADDA5855, 0xFDC27316,
            0xC898DB89, 0x1D5BB4DB, 0xD1609A70, 0xE05D675B, 0x869825EE, 0x9C6742C8, 0x69A425C0,
            0x70DC8F9, 0x15013A08, 0x31FE4961, 0xDDB5C107, 0xFBB681F9, 0x7B69E09A, 0xCA766381,
            0x89EFF07E, 0xDE98315F, 0x3068E47E, 0xF36A41E9, 0x3C3CE061, 0xF9E60C87, 0x405E951D,
            0xDCAE4DF0, 0xD88DB9B5, 0xBD416969, 0x7D615B69, 0xC02ED60A, 0xB9B47D24, 0xAFBD5C89,
            0x69A7E15, 0xB7DCABFA, 0x6314327E, 0x4B17668D, 0xB9575296, 0x1D8B161B, 0x6CC1CC5D,
            0x6958A088, 0xB1AC152B, 0x7D5480F3, 0x5102012, 0x7410A083, 0xBE70639D, 0x608A05CE,
            0x63B0E5D9, 0xB3E58F82, 0x178E8B05, 0x4D2B4A36,
        ];
        let buf = [0u8; 256];
        let mut h = 0;

        for i in 0..256 {
            let mut hasher = Lookup2::<Hash>::from_seed(h);
            Digest::update(&mut hasher, &buf[..i]);
            let hash = hasher.finalize();
            h = u32::from_le_bytes(hash[..].try_into().unwrap());
            assert_eq!(EXPECTED[i], h, "Expected 0x{:X} got 0x{h:X}", EXPECTED[i]);
        }
    }

    #[test]
    fn test_driver1_hash2() {
        const EXPECTED: [u32; 256] = [
            0xBD49D10D, 0xE24E999D, 0xC4049D4D, 0x4DA29F9F, 0x506F5B9D, 0xC7DF8CBA, 0xA52BDDF6,
            0x97E7689A, 0xD678C2AD, 0xAA5006B5, 0x73A41910, 0xFDA22C6C, 0x45957D38, 0x76345F5A,
            0xB58712FC, 0x2BD31402, 0x38D4AD9A, 0x4FCDA155, 0xE67DB6B4, 0x7FAD23DA, 0x9785EE3C,
            0x1B19009B, 0xC3D701F5, 0xE2C8592E, 0x6CF900DA, 0x9C7C221C, 0x89AE545E, 0x5A72A22D,
            0x213A1765, 0x628DDEF8, 0x5218166A, 0x990979B0, 0x41F22AF8, 0xBEEA06A8, 0xA4AC945A,
            0x91D95480, 0xE3ABF974, 0xD608239B, 0xF528C2E3, 0x29634AD0, 0xBD924721, 0x67FF395C,
            0x200ADA79, 0xE1507139, 0xA33E6251, 0x2F1BAB29, 0x79CD6797, 0x701359E8, 0x20BC5E28,
            0x785F380F, 0x6546022F, 0x4CE9D45C, 0x80FEAC92, 0xBBD25C6D, 0xB0AAFD65, 0x6CC8B10,
            0x6BDA6DAB, 0x592C1E30, 0xCF50CBDC, 0xF433B6D, 0x9ECD5731, 0x650BAE18, 0x2493B89,
            0xC466CA6E, 0x87E62D37, 0x77B2370B, 0x7945CD36, 0xF850A369, 0xEE32FE97, 0x623D2A9B,
            0x8A88777A, 0x907E6021, 0xDBB2631B, 0xE080A1BD, 0xDE503404, 0xFC5B4894, 0xA705D70F,
            0x44C6A128, 0xD8045AAF, 0x84E3CDD0, 0xD2C7858D, 0x692D4B40, 0xAEA78312, 0xF94D40A2,
            0xDAA65C66, 0xD7523473, 0xF4F925E7, 0xE88FDADD, 0xC74CE3AF, 0x9D204D13, 0x79937A09,
            0x8CDB191F, 0xE4040730, 0x90BE2A71, 0x766EC461, 0xEFE4DEAA, 0xE627785D, 0x6DEB3429,
            0x257B93C7, 0x3CEEEE3A, 0x18A2C95A, 0x6D002985, 0x4F761C1E, 0xD752000E, 0x6EF64195,
            0x1F845EF0, 0xCA916601, 0x7EF9347D, 0xE1982DBE, 0x6ED33C7, 0x91DF61BC, 0xF436CE9A,
            0x4F0E4B94, 0x8E9FB775, 0xB91AFE35, 0xCB48584E, 0x1A343393, 0x2F650BFB, 0x4040EB86,
            0xCD557D1, 0x701D7715, 0x5AD98C3F, 0x45906833, 0xB8C532A9, 0xDED53E6E, 0x92DC9FC9,
            0xF3BBF8B0, 0x157C1FCE, 0x5D7E85DD, 0x7C52B3F, 0xE0E5A35, 0x4C274610, 0xB124FACC,
            0x1C72EB04, 0x55044FC6, 0xC0D3B3D5, 0xA39699BC, 0x9B8AA0A, 0xCECDB40A, 0xE132D15D,
            0x67D9F7DF, 0xC5FEADD5, 0x7DBF8128, 0xC4DF300F, 0x204C4B71, 0x9E91DFDC, 0x44C9A2B0,
            0xB97CE076, 0xA6BB2E62, 0x847F0CE7, 0xD8844E13, 0x8FE9F8D2, 0xB0543024, 0x2FF8CA53,
            0xE291D1CF, 0x7AFF9D2E, 0xFB75AB17, 0x65F9FE, 0xF367875E, 0xA2B49E88, 0xDA39100E,
            0x4E74CEDA, 0x8DFD0E1F, 0x52106600, 0xD8B57803, 0xC082721F, 0xF51D14CE, 0x30A9C834,
            0x7F442B06, 0xEDBF4111, 0xF6AEE865, 0x907F6F2, 0x363DC24D, 0x19F90371, 0x6E40586E,
            0x2EABCCC7, 0x80F0C08D, 0x1FA9653, 0x7DFB5947, 0x3FF7A452, 0x4F83DA97, 0xD8B42ADB,
            0xB32D832B, 0x1837B03E, 0xE8C11B80, 0x2BA39206, 0x3C1A113C, 0xAC5EDE24, 0x5AB68366,
            0xA34E07A5, 0xBAC9A7FD, 0xBDEDF9E0, 0xEA4FEC9B, 0x1F67293B, 0x511586A6, 0x14DF8EF,
            0x523B3A6, 0x6D2B4DD3, 0xA775B486, 0xA7AAFFB5, 0xBE0F0AB6, 0xCB9EF775, 0xDDA7ADBC,
            0x8B37ADCB, 0xA0D036B9, 0x7FE92046, 0x4373CD03, 0xE2B8966E, 0xE22F55DF, 0x379DF0AA,
            0x6F7A764C, 0x7F99F0C6, 0xBF3A3079, 0xF521E1EF, 0x7B60829, 0xE3396AC3, 0x101CB8EC,
            0x1F181048, 0xEE8CFF71, 0xA4242CD6, 0xBBFC1D03, 0xAA5B2A1F, 0xBFD8980A, 0xAD02F782,
            0xFB4D5791, 0xF9806CED, 0x427A137A, 0x169D5F48, 0x90C5670E, 0xA0793208, 0x1CEFF27A,
            0x385DDF73, 0xC135A9EB, 0x6BEC2DA4, 0x13BABE6, 0x4BBF3F4F, 0xE4018C33, 0xB8F4607E,
            0xD98471D7, 0x647B34E, 0x95C91823, 0x953493F, 0x1E033242, 0xCC8F51, 0x62B39FAD,
            0x70F902FC, 0xCB1E3810, 0xB6E2D5C6, 0xE8CA4757, 0xBBA5C55, 0x2CCA400C, 0x8E263A2A,
            0xC80FC180, 0xFE4A6334, 0xD992B34E, 0x66587A7B,
        ];
        let buf = [0_u32; 256];
        let mut h = 0;

        for i in 0..256 {
            h = Lookup2::<Hash2>::hash(&buf[..i], h);
            assert_eq!(EXPECTED[i], h, "Expected 0x{:X} got 0x{h:X}", EXPECTED[i]);
        }
    }

    #[test]
    fn test_driver3() {
        let q = b"This is the time for all good men to come to the aid of their country";
        let qq = b"xThis is the time for all good men to come to the aid of their country";
        let qqq = b"xxThis is the time for all good men to come to the aid of their country";
        let qqqq = b"xxxThis is the time for all good men to come to the aid of their country";

        const EXPECTED: u32 = 0xCF874E3D;

        let hash = Lookup2::<Hash3>::digest(q);
        assert_eq!(
            u32::from_le_bytes(hash[..].try_into().unwrap()),
            EXPECTED,
            "Endianness.  These should all be the same"
        );
        let hash = Lookup2::<Hash3>::digest(&qq[1..]);
        assert_eq!(
            u32::from_le_bytes(hash[..].try_into().unwrap()),
            EXPECTED,
            "Endianness.  These should all be the same"
        );
        let hash = Lookup2::<Hash3>::digest(&qqq[2..]);
        assert_eq!(
            u32::from_le_bytes(hash[..].try_into().unwrap()),
            EXPECTED,
            "Endianness.  These should all be the same"
        );
        let hash = Lookup2::<Hash3>::digest(&qqqq[3..]);
        assert_eq!(
            u32::from_le_bytes(hash[..].try_into().unwrap()),
            EXPECTED,
            "Endianness.  These should all be the same"
        );
    }

    #[test]
    fn test_string1() {
        let phrase = b"Yo mama is so fat that her bellybuttongs got an echo.";
        let mut hasher = Lookup2::<Hash>::new();
        Digest::update(&mut hasher, phrase);
        let hash = hasher.finalize();

        assert_eq!(u32::from_le_bytes(hash[..].try_into().unwrap()), 0x2CEB1226);
    }
    #[test]
    fn test_string2() {
        let phrase = b"Yo mama is so stupid that she failed a survey.";
        let mut hasher = Lookup2::<Hash3>::from_seed(0xDEADBEEF);
        Digest::update(&mut hasher, phrase);
        let hash2 = hasher.finalize();

        assert_eq!(u32::from_le_bytes(hash2[..].try_into().unwrap()), 0xD1215833);
    }
    #[test]
    fn test_mix() {
        let state = [346972, 5874, 5287068];

        let state = Lookup2::<Hash>::mix(state);

        assert_eq!(state, [0x44A7DB72, 0x725FD033, 0x8943E220])
    }

    #[test]
    fn test_mix2() {
        let state = [346972, 5874, 5287068];

        let state = Lookup2::<Hash>::mix2(state);

        assert_eq!(state, [0x44A7DB72, 0x725FD033, 0x8943E220])
    }
}