seahash 4.1.0

//! A highly optimized version of SeaHash.

use std::slice;

use helper;

/// A SeaHash state.
#[derive(Clone)]
pub struct State {
    /// `a`
    a: u64,
    /// `b`
    b: u64,
    /// `c`
    c: u64,
    /// `d`
    d: u64,
    /// The number of written bytes.
    written: u64,
}

impl State {
    /// Create a new state vector with some initial values.
    pub fn new(a: u64, b: u64, c: u64, d: u64) -> State {
        State {
            a: a,
            b: b,
            c: c,
            d: d,
            written: 0,
        }
    }

    /// Hash a buffer with some seed.
    pub fn hash(buf: &[u8], (mut a, mut b, mut c, mut d): (u64, u64, u64, u64)) -> State {
        unsafe {
            // We use 4 different registers to store seperate hash states, because this allows us
            // to update them seperately, and consequently exploiting ILP to update the states in
            // parallel.

            // The pointer to the current bytes.
            let mut ptr = buf.as_ptr();
            // The end of the "main segment", i.e. the biggest buffer s.t. the length is divisible
            // by 32.
            let end_ptr = buf.as_ptr().offset(buf.len() as isize & !0x1F);

            while end_ptr > ptr {
                // Modern CPUs allow the pointer arithmetic to be done in place, hence not
                // introducing tmpvars.
                a ^= helper::read_u64(ptr);
                b ^= helper::read_u64(ptr.offset(8));
                c ^= helper::read_u64(ptr.offset(16));
                d ^= helper::read_u64(ptr.offset(24));

                // Increment the pointer.
                ptr = ptr.offset(32);

                // Diffuse the updated registers. We hope that each of these are executed in
                // parallel.
                a = helper::diffuse(a);
                b = helper::diffuse(b);
                c = helper::diffuse(c);
                d = helper::diffuse(d);
            }

            // Calculate the number of excessive bytes. These are bytes that could not be handled
            // in the loop above.
            let mut excessive = buf.len() as usize + buf.as_ptr() as usize - end_ptr as usize;
            // Handle the excessive bytes.
            match excessive {
                0 => {}
                1..=7 => {
                    // 1 or more excessive.

                    // Write the last excessive bytes (<8 bytes).
                    a ^= helper::read_int(slice::from_raw_parts(ptr as *const u8, excessive));

                    // Diffuse.
                    a = helper::diffuse(a);
                }
                8 => {
                    // 8 bytes excessive.

                    // Mix in the partial block.
                    a ^= helper::read_u64(ptr);

                    // Diffuse.
                    a = helper::diffuse(a);
                }
                9..=15 => {
                    // More than 8 bytes excessive.

                    // Mix in the partial block.
                    a ^= helper::read_u64(ptr);

                    // Write the last excessive bytes (<8 bytes).
                    excessive = excessive - 8;
                    b ^= helper::read_int(slice::from_raw_parts(ptr.offset(8), excessive));

                    // Diffuse.
                    a = helper::diffuse(a);
                    b = helper::diffuse(b);
                }
                16 => {
                    // 16 bytes excessive.

                    // Mix in the partial block.
                    a = helper::diffuse(a ^ helper::read_u64(ptr));
                    b = helper::diffuse(b ^ helper::read_u64(ptr.offset(8)));
                }
                17..=23 => {
                    // 16 bytes or more excessive.

                    // Mix in the partial block.
                    a ^= helper::read_u64(ptr);
                    b ^= helper::read_u64(ptr.offset(8));

                    // Write the last excessive bytes (<8 bytes).
                    excessive = excessive - 16;
                    c ^= helper::read_int(slice::from_raw_parts(ptr.offset(16), excessive));

                    // Diffuse.
                    a = helper::diffuse(a);
                    b = helper::diffuse(b);
                    c = helper::diffuse(c);
                }
                24 => {
                    // 24 bytes excessive.

                    // Mix in the partial block.
                    a ^= helper::read_u64(ptr);
                    b ^= helper::read_u64(ptr.offset(8));
                    c ^= helper::read_u64(ptr.offset(16));

                    // Diffuse.
                    a = helper::diffuse(a);
                    b = helper::diffuse(b);
                    c = helper::diffuse(c);
                }
                _ => {
                    // More than 24 bytes excessive.

                    // Mix in the partial block.
                    a ^= helper::read_u64(ptr);
                    b ^= helper::read_u64(ptr.offset(8));
                    c ^= helper::read_u64(ptr.offset(16));

                    // Write the last excessive bytes (<8 bytes).
                    excessive = excessive - 24;
                    d ^= helper::read_int(slice::from_raw_parts(ptr.offset(24), excessive));

                    // Diffuse.
                    a = helper::diffuse(a);
                    b = helper::diffuse(b);
                    c = helper::diffuse(c);
                    d = helper::diffuse(d);
                }
            }
        }

        State {
            a: a,
            b: b,
            c: c,
            d: d,
            written: buf.len() as u64,
        }
    }

    /// Write another 64-bit integer into the state.
    pub fn push(&mut self, x: u64) {
        // Mix `x` into `a`.
        let a = helper::diffuse(self.a ^ x);

        //  Rotate around.
        //  _______________________
        // |                       v
        // a <---- b <---- c <---- d
        self.a = self.b;
        self.b = self.c;
        self.c = self.d;
        self.d = a;

        // Increase the written bytes counter.
        self.written += 8;
    }

    /// Remove the most recently written 64-bit integer from the state.
    ///
    /// Given the value of the most recently written u64 `last`, remove it from the state.
    pub fn pop(&mut self, last: u64) {
        // Un-mix `last` from `d`. Removes the recently written data.
        let d = helper::undiffuse(self.d) ^ last;

        //  Rotate back.
        //  _______________________
        // v                       |
        // a ----> b ----> c ----> d
        self.d = self.c;
        self.c = self.b;
        self.b = self.a;
        self.a = d;

        // Decrese the written bytes counter.
        self.written -= 8;
    }

    /// Finalize the state.
    #[inline]
    pub fn finalize(self) -> u64 {
        let State {
            written,
            mut a,
            b,
            mut c,
            d,
        } = self;

        // XOR the states together. Even though XOR is commutative, it doesn't matter, because the
        // state vector's initial components are mutually distinct, and thus swapping even and odd
        // chunks will affect the result, because it is sensitive to the initial condition.
        a ^= b;
        c ^= d;
        a ^= c;
        // XOR the number of written bytes in order to make the excessive bytes zero-sensitive
        // (without this, two excessive zeros would be equivalent to three excessive zeros). This
        // is know as length padding.
        a ^= written;

        // We diffuse to make the excessive bytes discrete (i.e. small changes shouldn't give small
        // changes in the output).
        helper::diffuse(a)
    }
}

/// Hash some buffer.
///
/// This is a highly optimized implementation of SeaHash. It implements numerous techniques to
/// improve performance:
///
/// - Register allocation: This makes a great deal out of making sure everything fits into
///   registers such that minimal memory accesses are needed. This works quite successfully on most
///   CPUs, and the only time it reads from memory is when it fetches the data of the buffer.
/// - Bulk reads: Like most other good hash functions, we read 8 bytes a time. This obviously
///   improves performance a lot
/// - Independent updates: We make sure very few statements next to each other depends on the
///   other. This means that almost always the CPU will be able to run the instructions in parallel.
/// - Loop unrolling: The hot loop is unrolled such that very little branches (one every 32 bytes)
///   are needed.
///
/// and more.
///
/// The seed of this hash function is prechosen.
pub fn hash(buf: &[u8]) -> u64 {
    hash_seeded(
        buf,
        0x16f11fe89b0d677c,
        0xb480a793d8e6c86c,
        0x6fe2e5aaf078ebc9,
        0x14f994a4c5259381,
    )
}

/// Hash some buffer according to a chosen seed.
///
/// The keys are expected to be chosen from a uniform distribution. The keys should be mutually
/// distinct to avoid issues with collisions if the lanes are permuted.
///
/// This is not secure, as [the key can be extracted with a bit of computational
/// work](https://github.com/ticki/tfs/issues/5), as such, it is recommended to have a fallback
/// hash function (adaptive hashing) in the case of hash flooding. It can be considered unbroken if
/// the output is not known (i.e. no malicious party has access to the raw values of the keys, only
/// a permutation thereof).), however I absolutely do not recommend using it for this. If you want
/// to be strict, this should only be used as a layer of obfuscation, such that the fallback (e.g.
/// SipHash) is harder to trigger.
///
/// In the future, I might strengthen the security if possible while having backward compatibility
/// with the default initialization vector.
pub fn hash_seeded(buf: &[u8], a: u64, b: u64, c: u64, d: u64) -> u64 {
    State::hash(buf, (a, b, c, d)).finalize()
}

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

    use reference;

    fn hash_match(a: &[u8]) {
        assert_eq!(hash(a), reference::hash(a));
        assert_eq!(
            hash_seeded(a, 1, 1, 1, 1),
            reference::hash_seeded(a, 1, 1, 1, 1)
        );
        assert_eq!(
            hash_seeded(a, 500, 2873, 2389, 9283),
            reference::hash_seeded(a, 500, 2873, 2389, 9283)
        );
        assert_eq!(
            hash_seeded(a, 238945723984, 872894734, 239478243, 28937498234),
            reference::hash_seeded(a, 238945723984, 872894734, 239478243, 28937498234)
        );
        assert_eq!(
            hash_seeded(a, !0, !0, !0, !0),
            reference::hash_seeded(a, !0, !0, !0, !0)
        );
        assert_eq!(
            hash_seeded(a, 0, 0, 0, 0),
            reference::hash_seeded(a, 0, 0, 0, 0)
        );
    }

    #[test]
    #[cfg_attr(miri, ignore)] // very slow to run on miri
    fn zero() {
        let arr = [0; 4096];
        for n in 0..4096 {
            hash_match(&arr[0..n]);
        }
    }

    #[test]
    fn seq() {
        let mut buf = [0; 4096];
        for i in 0..4096 {
            buf[i] = i as u8;
        }
        hash_match(&buf);
    }

    #[test]
    fn position_depedent() {
        let mut buf1 = [0; 4098];
        for i in 0..4098 {
            buf1[i] = i as u8;
        }
        let mut buf2 = [0; 4098];
        for i in 0..4098 {
            buf2[i] = i as u8 ^ 1;
        }

        assert!(hash(&buf1) != hash(&buf2));
    }

    #[test]
    fn shakespear() {
        hash_match(b"to be or not to be");
        hash_match(b"love is a wonderful terrible thing");
    }

    #[test]
    fn zero_senitive() {
        assert_ne!(hash(&[1, 2, 3, 4]), hash(&[1, 0, 2, 3, 4]));
        assert_ne!(hash(&[1, 2, 3, 4]), hash(&[1, 0, 0, 2, 3, 4]));
        assert_ne!(hash(&[1, 2, 3, 4]), hash(&[1, 2, 3, 4, 0]));
        assert_ne!(hash(&[1, 2, 3, 4]), hash(&[0, 1, 2, 3, 4]));
        assert_ne!(hash(&[0, 0, 0]), hash(&[0, 0, 0, 0, 0]));
    }

    #[test]
    fn not_equal() {
        assert_ne!(hash(b"to be or not to be "), hash(b"to be or not to be"));
        assert_ne!(hash(b"jkjke"), hash(b"jkjk"));
        assert_ne!(hash(b"ijkjke"), hash(b"ijkjk"));
        assert_ne!(hash(b"iijkjke"), hash(b"iijkjk"));
        assert_ne!(hash(b"iiijkjke"), hash(b"iiijkjk"));
        assert_ne!(hash(b"iiiijkjke"), hash(b"iiiijkjk"));
        assert_ne!(hash(b"iiiiijkjke"), hash(b"iiiiijkjk"));
        assert_ne!(hash(b"iiiiiijkjke"), hash(b"iiiiiijkjk"));
        assert_ne!(hash(b"iiiiiiijkjke"), hash(b"iiiiiiijkjk"));
        assert_ne!(hash(b"iiiiiiiijkjke"), hash(b"iiiiiiiijkjk"));
        assert_ne!(hash(b"ab"), hash(b"bb"));
    }

    #[test]
    fn push() {
        let mut state = State::new(1, 2, 3, 4);
        state.push(!0);
        state.push(0);

        assert_eq!(
            hash_seeded(
                &[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0, 0, 0, 0, 0, 0, 0, 0],
                1,
                2,
                3,
                4
            ),
            state.finalize()
        );
    }

    #[test]
    fn pop() {
        let mut state = State::new(1, 2, 3, 4);
        state.push(!0);
        state.push(0);
        state.pop(0);

        assert_eq!(
            hash_seeded(
                &[0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF],
                1,
                2,
                3,
                4
            ),
            state.finalize()
        );
    }
}