cuttlefish_rs/
hash.rs

1use std::hash::{BuildHasherDefault, Hasher};
2
3const WY_SALT: [u64; 4] = [
4    4167021922371662411,
5    7320285940802167691,
6    14307255741305819987,
7    10859488101230029397,
8];
9
10#[inline]
11fn mum(a: u64, b: u64) -> u64 {
12    let r = (a as u128).wrapping_mul(b as u128);
13    (r as u64) ^ (r >> 64) as u64
14}
15
16#[inline]
17fn mum_parts(a: u64, b: u64) -> (u64, u64) {
18    let product = (a as u128).wrapping_mul(b as u128);
19    (product as u64, (product >> 64) as u64)
20}
21
22#[inline]
23fn mix(a: u64, b: u64) -> u64 {
24    mum(a ^ WY_SALT[0], b ^ WY_SALT[1])
25}
26
27#[inline]
28fn read_u64_le(bytes: &[u8]) -> u64 {
29    let mut buf = [0u8; 8];
30    buf[..bytes.len()].copy_from_slice(bytes);
31    u64::from_le_bytes(buf)
32}
33
34pub fn hash_bytes(bytes: &[u8], seed: u64) -> u64 {
35    let mut h = seed ^ WY_SALT[2] ^ bytes.len() as u64;
36    let mut chunks = bytes.chunks_exact(16);
37    for chunk in &mut chunks {
38        let a = u64::from_le_bytes(chunk[..8].try_into().unwrap());
39        let b = u64::from_le_bytes(chunk[8..16].try_into().unwrap());
40        h = mix(h ^ a, b);
41    }
42
43    let rem = chunks.remainder();
44    if rem.len() > 8 {
45        h = mix(h ^ read_u64_le(&rem[..8]), read_u64_le(&rem[8..]));
46    } else if !rem.is_empty() {
47        h = mix(h, read_u64_le(rem));
48    }
49
50    mum(h ^ WY_SALT[3], h.rotate_left(32) ^ WY_SALT[0])
51}
52
53pub type FastBuildHasher = BuildHasherDefault<FastHasher>;
54
55#[derive(Clone, Default)]
56pub struct FastHasher {
57    state: u64,
58}
59
60impl Hasher for FastHasher {
61    #[inline]
62    fn finish(&self) -> u64 {
63        mum(
64            self.state ^ WY_SALT[3],
65            self.state.rotate_left(32) ^ WY_SALT[0],
66        )
67    }
68
69    #[inline]
70    fn write(&mut self, bytes: &[u8]) {
71        let mut chunks = bytes.chunks_exact(8);
72        for chunk in &mut chunks {
73            self.write_u64(u64::from_le_bytes(chunk.try_into().unwrap()));
74        }
75        let rem = chunks.remainder();
76        if !rem.is_empty() {
77            self.write_u64(read_u64_le(rem));
78        }
79    }
80
81    #[inline]
82    fn write_u8(&mut self, i: u8) {
83        self.write_u64(i as u64);
84    }
85
86    #[inline]
87    fn write_u16(&mut self, i: u16) {
88        self.write_u64(i as u64);
89    }
90
91    #[inline]
92    fn write_u32(&mut self, i: u32) {
93        self.write_u64(i as u64);
94    }
95
96    #[inline]
97    fn write_u64(&mut self, i: u64) {
98        self.state = mix(self.state ^ i, i.rotate_left(32));
99    }
100
101    #[inline]
102    fn write_u128(&mut self, i: u128) {
103        self.write_u64(i as u64);
104        self.write_u64((i >> 64) as u64);
105    }
106
107    #[inline]
108    fn write_usize(&mut self, i: usize) {
109        self.write_u64(i as u64);
110    }
111}
112
113#[inline]
114pub fn hash_u64(value: u64, seed: u64) -> u64 {
115    let h = seed ^ WY_SALT[2] ^ 8;
116    let h = mix(h, value);
117    mum(h ^ WY_SALT[3], h.rotate_left(32) ^ WY_SALT[0])
118}
119
120// Exact len=8 specialization of the wyhash version used by C++ minimizers.
121#[inline]
122pub fn wyhash_u64(value: u64, mut seed: u64) -> u64 {
123    seed ^= mum(seed ^ WY_SALT[0], WY_SALT[1]);
124    let a = value.rotate_left(32) ^ WY_SALT[1];
125    let b = value ^ seed;
126    let (a, b) = mum_parts(a, b);
127    mum(a ^ WY_SALT[0] ^ 8, b ^ WY_SALT[1])
128}
129
130#[inline]
131pub fn hash_two_u64(first: u64, second: u64) -> u64 {
132    let h = mix(first, first.rotate_left(32));
133    let h = mix(h ^ second, second.rotate_left(32));
134    mum(h ^ WY_SALT[3], h.rotate_left(32) ^ WY_SALT[0])
135}
136
137#[inline]
138pub fn fast_u64_hash(value: u64, seed: u64) -> u64 {
139    let value = value ^ seed;
140    let mixed = (value ^ (value >> 23)).wrapping_mul(0x9E37_79B9_7F4A_7C15);
141    mixed ^ (mixed >> 29)
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn hash_is_seeded_and_stable() {
150        assert_eq!(hash_u64(42, 0), hash_u64(42, 0));
151        assert_ne!(hash_u64(42, 0), hash_u64(42, 1));
152    }
153
154    #[test]
155    fn hash_u64_matches_byte_hash() {
156        for seed in [0, 1, 17, u64::MAX] {
157            for value in [0, 1, 42, u32::MAX as u64, u64::MAX] {
158                assert_eq!(
159                    hash_u64(value, seed),
160                    hash_bytes(&value.to_le_bytes(), seed)
161                );
162            }
163        }
164    }
165
166    #[test]
167    fn hash_two_u64_matches_fast_hasher_writes() {
168        for first in [0, 1, 42, u64::MAX] {
169            for second in [0, 7, u32::MAX as u64, u64::MAX] {
170                let mut hasher = FastHasher::default();
171                hasher.write_u64(first);
172                hasher.write_u64(second);
173                assert_eq!(hash_two_u64(first, second), hasher.finish());
174            }
175        }
176    }
177
178    #[test]
179    fn wyhash_u64_matches_cpp_minimizer_hash() {
180        assert_eq!(wyhash_u64(0, 0), 7_824_564_342_066_666_581);
181        assert_eq!(wyhash_u64(1, 0), 17_550_070_827_293_468_892);
182        assert_eq!(wyhash_u64(42, 0), 7_038_757_716_059_073_700);
183        assert_eq!(
184            wyhash_u64(0x1234_5678_9abc_def0, 0),
185            6_800_848_065_093_387_582
186        );
187    }
188}
cuttlefish_rs/hash.rs

cuttlefish_rs/
hash.rs
