djb2 0.1.0

#![no_std]

//! This algorithm (k=33) was first reported by dan bernstein many years ago (1991) in
//! comp.lang.c. another version of this algorithm (now favored by bernstein)
//! uses xor: hash(i) = hash(i - 1) * 33 ^ str[i]; the magic of number 33 (why it
//! works better than many other constants, prime or not) has never been
//! adequately explained.
//!
//! https://www.cse.yorku.ca/~oz/hash.html

/// Generate a 32 bit hash
///
/// Uses the improved XOR variant that bernstein now favors.
pub const fn hash(bytes: &[u8]) -> u32 {
    hash_with_initial(5381u32, bytes)
}

/// Generate a 32 bit hash (using a custom initial state)
///
/// This function is identical with `hash` when called with `5381`, but allows
/// appending more data to a previous hash.
pub const fn hash_with_initial(init: u32, bytes: &[u8]) -> u32 {
    let mut hash = init;

    // Ping me once `const_for` is stable: https://github.com/rust-lang/rust/issues/87575
    /*
    for &c in bytes {
        hash = (hash << 5).wrapping_add(hash) ^ (c as u32); /* hash * 33 ^ c */
    }
    */
    /* <meanwhile> */
    let mut i = 0;
    while i < bytes.len() {
        let c = bytes[i];
        hash = (hash << 5).wrapping_add(hash) ^ (c as u32); /* hash * 33 ^ c */
        i += 1;
    }
    /* </meanwhile> */

    hash
}

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

    #[test]
    fn test_empty() {
        let hash = hash(b"");
        assert_eq!(hash, 5381);
    }

    #[test]
    fn test_null() {
        let hash = hash(&[0]);
        assert_eq!(hash, (5381 << 5) + 5381);
    }

    #[test]
    fn test_hello_world() {
        let hash = hash(b"Ohai world!");
        assert_eq!(hash, 3256904681u32);
    }

    #[test]
    fn test_u32_max() {
        let hash = hash(&u32::MAX.to_be_bytes());
        assert_eq!(hash, 2083728837);
    }

    #[test]
    fn test_append_more() {
        let all_at_once = hash(b"foobar");

        let first = hash(b"foo");
        let second = hash_with_initial(first, b"bar");

        assert_eq!(all_at_once, second);
    }
}