//! 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() ); } }