murmur3.rs

/// Murmur3 x86-64 128-bit hash; pretty much a direct port of Austin Appleby's murmur3 x86-64 128-bit hash.
/// A simpler conversion than some others.
/// NB: the endianness/ordering here can be very confusing; caveat scriptor
pub fn hash(bytes: &[u8]) -> u128
{
    let (mut h1, mut h2) = (0_u64, 0_u64);
    let (c1, c2) = (0x87c37b91114253d5_u64, 0x4cf5ad432745937f_u64);
    let n = bytes.len();
    let lower_round = |h, k: u64| h ^ k.wrapping_mul(c1).rotate_left(31).wrapping_mul(c2);
    let upper_round = |h, k: u64| h ^ k.wrapping_mul(c2).rotate_left(33).wrapping_mul(c1);

    for i in (0..n & !15).step_by(16) {
        unsafe {
            let (k1, k2) = (*(bytes[i..].as_ptr() as *const u64),
                            *(bytes[8+i..].as_ptr() as *const u64));
            h1 = lower_round(h1, k1).rotate_left(27).wrapping_add(h2).wrapping_mul(5).wrapping_add(0x52dce729);
            h2 = upper_round(h2, k2).rotate_left(31).wrapping_add(h1).wrapping_mul(5).wrapping_add(0x38495ab5);
        }
    }

    // take what's left
    let i = n - (n & 15);
    h1 = lower_round(h1, bytes[i..min(8+i, n)].iter().rev()
                     .fold(0_u64, |s, &b| (s << 8) | (b as u64)));
    if n-i > 8 {
        h2 = upper_round(h2, bytes[8+i..n].iter().rev()
                         .fold(0_u64, |s, &b| (s << 8) | (b as u64)));
    }

    // "finalization"
    h1 ^= n as u64;
    h2 ^= n as u64;
    h1 = h1.wrapping_add(h2);
    h2 = h2.wrapping_add(h1);
    // fmix
    let fmix = |k: u64| {
        let mut k = (k ^ (k >> 33)).wrapping_mul(0xff51afd7ed558ccd_u64);
        k = (k ^ (k >> 33)).wrapping_mul(0xc4ceb9fe1a85ec53_u64);
        k ^ (k >> 33)
    };
    h1 = fmix(h1);
    h2 = fmix(h2);
    h1 = h1.wrapping_add(h2);
    h2 = h2.wrapping_add(h1);
    ((h2 as u128) << 64) | h1 as u128
}