xxhash/
xxh64.rs

1use crate::Checksum;
2
3const PRIME64_1: u64 = 0x9E3779B185EBCA87;
4const PRIME64_2: u64 = 0xC2B2AE3D27D4EB4F;
5const PRIME64_3: u64 = 0x165667B19E3779F9;
6const PRIME64_4: u64 = 0x85EBCA77C2B2AE63;
7const PRIME64_5: u64 = 0x27D4EB2F165667C5;
8
9/// XXH64 hash (64-bit).
10///
11/// The classic 64-bit xxHash algorithm. Accepts an optional `u64` seed via
12/// [`with_seed`](Xxh64::with_seed) (defaults to 0).
13///
14/// # Example
15///
16/// ```rust
17/// use xxhash::{Xxh64, Checksum};
18///
19/// let hash = Xxh64::checksum(b"hello");
20/// assert_eq!(hash, 0x26C7827D889F6DA3);
21/// ```
22#[derive(Clone)]
23pub struct Xxh64 {
24    seed: u64,
25    v: [u64; 4],
26    total_len: u64,
27    has_stripes: bool,
28    buf: [u8; 32],
29    buf_len: u8,
30}
31
32impl Xxh64 {
33    /// Create a new XXH64 hasher with the given seed.
34    #[inline]
35    pub const fn with_seed(seed: u64) -> Self {
36        Xxh64 {
37            seed,
38            v: [0; 4],
39            total_len: 0,
40            has_stripes: false,
41            buf: [0u8; 32],
42            buf_len: 0,
43        }
44    }
45
46    #[inline]
47    fn init_stripes(&mut self) {
48        self.v[0] = self.seed.wrapping_add(PRIME64_1).wrapping_add(PRIME64_2);
49        self.v[1] = self.seed.wrapping_add(PRIME64_2);
50        self.v[2] = self.seed;
51        self.v[3] = self.seed.wrapping_sub(PRIME64_1);
52        self.has_stripes = true;
53    }
54
55    #[inline]
56    fn process_stripe(&mut self, stripe: &[u8]) {
57        debug_assert_eq!(stripe.len(), 32);
58        for i in 0..4 {
59            let lane = u64::from_le_bytes(stripe[i * 8..(i + 1) * 8].try_into().unwrap());
60            self.v[i] = self.v[i].wrapping_add(lane.wrapping_mul(PRIME64_2));
61            self.v[i] = self.v[i].rotate_left(31);
62            self.v[i] = self.v[i].wrapping_mul(PRIME64_1);
63        }
64    }
65
66    #[inline]
67    fn process_8bytes(acc: &mut u64, data: &[u8]) {
68        let lane = u64::from_le_bytes(data.try_into().unwrap());
69        let k1 = lane.wrapping_mul(PRIME64_2).rotate_left(31).wrapping_mul(PRIME64_1);
70        *acc ^= k1;
71        *acc = acc.rotate_left(27).wrapping_mul(PRIME64_1).wrapping_add(PRIME64_4);
72    }
73
74    #[inline]
75    fn process_4bytes(acc: &mut u64, data: &[u8]) {
76        let lane = u32::from_le_bytes(data.try_into().unwrap()) as u64;
77        *acc ^= lane.wrapping_mul(PRIME64_1);
78        *acc = acc.rotate_left(23).wrapping_mul(PRIME64_2).wrapping_add(PRIME64_3);
79    }
80
81    #[inline]
82    fn process_1byte(acc: &mut u64, byte: u8) {
83        *acc ^= (byte as u64).wrapping_mul(PRIME64_5);
84        *acc = acc.rotate_left(11).wrapping_mul(PRIME64_1);
85    }
86}
87
88impl Checksum for Xxh64 {
89    type Output = u64;
90
91    #[inline]
92    fn new() -> Self {
93        Self::with_seed(0)
94    }
95
96    fn update(&mut self, data: &[u8]) {
97        self.total_len += data.len() as u64;
98        let mut data = data;
99
100        if self.buf_len > 0 {
101            let take = (32 - self.buf_len as usize).min(data.len());
102            self.buf[self.buf_len as usize..self.buf_len as usize + take].copy_from_slice(&data[..take]);
103            self.buf_len += take as u8;
104            data = &data[take..];
105
106            if self.buf_len == 32 {
107                if !self.has_stripes {
108                    self.init_stripes();
109                }
110                let stripe = self.buf;
111                self.process_stripe(&stripe);
112                self.buf_len = 0;
113            }
114        }
115
116        if self.has_stripes {
117            let chunks = data.chunks_exact(32);
118            let remainder = chunks.remainder();
119            for stripe in chunks {
120                self.process_stripe(stripe);
121            }
122            data = remainder;
123        } else if data.len() >= 32 {
124            self.init_stripes();
125            let chunks = data.chunks_exact(32);
126            let remainder = chunks.remainder();
127            for stripe in chunks {
128                self.process_stripe(stripe);
129            }
130            data = remainder;
131        }
132
133        if !data.is_empty() {
134            self.buf[..data.len()].copy_from_slice(data);
135            self.buf_len = data.len() as u8;
136        }
137    }
138
139    fn sum(self) -> Self::Output {
140        let mut h64: u64;
141
142        if self.total_len >= 32 {
143            h64 = self.v[0]
144                .rotate_left(1)
145                .wrapping_add(self.v[1].rotate_left(7))
146                .wrapping_add(self.v[2].rotate_left(12))
147                .wrapping_add(self.v[3].rotate_left(18));
148            h64 = xxh64_merge_round(h64, self.v[0]);
149            h64 = xxh64_merge_round(h64, self.v[1]);
150            h64 = xxh64_merge_round(h64, self.v[2]);
151            h64 = xxh64_merge_round(h64, self.v[3]);
152        } else {
153            h64 = self.seed.wrapping_add(PRIME64_5);
154        }
155
156        h64 = h64.wrapping_add(self.total_len);
157
158        let mut idx = 0usize;
159        while idx + 8 <= self.buf_len as usize {
160            Self::process_8bytes(&mut h64, &self.buf[idx..idx + 8]);
161            idx += 8;
162        }
163        if idx + 4 <= self.buf_len as usize {
164            Self::process_4bytes(&mut h64, &self.buf[idx..idx + 4]);
165            idx += 4;
166        }
167        while idx < self.buf_len as usize {
168            Self::process_1byte(&mut h64, self.buf[idx]);
169            idx += 1;
170        }
171
172        avalanche(h64)
173    }
174}
175
176#[inline]
177const fn xxh64_merge_round(mut acc: u64, val: u64) -> u64 {
178    let mut val = val.wrapping_mul(PRIME64_2);
179    val = val.rotate_left(31);
180    val = val.wrapping_mul(PRIME64_1);
181    acc ^= val;
182    acc = acc.wrapping_mul(PRIME64_1).wrapping_add(PRIME64_4);
183    acc
184}
185
186#[inline]
187const fn avalanche(mut h64: u64) -> u64 {
188    h64 ^= h64 >> 33;
189    h64 = h64.wrapping_mul(PRIME64_2);
190    h64 ^= h64 >> 29;
191    h64 = h64.wrapping_mul(PRIME64_3);
192    h64 ^= h64 >> 32;
193    h64
194}
195
196impl core::fmt::Debug for Xxh64 {
197    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
198        f.debug_struct("Xxh64").finish()
199    }
200}
201
202impl Default for Xxh64 {
203    #[inline]
204    fn default() -> Self {
205        Self::with_seed(0)
206    }
207}
208
209// ---------------------------------------------------------------------------
210// Standalone const one-shot function
211// ---------------------------------------------------------------------------
212
213/// Compute the XXH64 hash of `data` in a single call.
214///
215/// Available as a `const fn` for compile-time hashing with seed=0.
216///
217/// # Example
218///
219/// ```rust
220/// use xxhash::xxh64;
221///
222/// let hash: u64 = xxh64(b"hello");
223/// assert_eq!(hash, 0x26C7827D889F6DA3);
224/// ```
225#[inline]
226pub const fn xxh64(data: &[u8]) -> u64 {
227    let len = data.len();
228    let seed: u64 = 0;
229    let mut h64: u64;
230
231    if len >= 32 {
232        let mut v = [
233            seed.wrapping_add(PRIME64_1).wrapping_add(PRIME64_2),
234            seed.wrapping_add(PRIME64_2),
235            seed,
236            seed.wrapping_sub(PRIME64_1),
237        ];
238        let mut p = 0;
239        while p + 32 <= len {
240            let mut i = 0;
241            while i < 4 {
242                let off = p + i * 8;
243                let lane = u64::from_le_bytes([
244                    data[off],
245                    data[off + 1],
246                    data[off + 2],
247                    data[off + 3],
248                    data[off + 4],
249                    data[off + 5],
250                    data[off + 6],
251                    data[off + 7],
252                ]);
253                v[i] = v[i].wrapping_add(lane.wrapping_mul(PRIME64_2));
254                v[i] = v[i].rotate_left(31);
255                v[i] = v[i].wrapping_mul(PRIME64_1);
256                i += 1;
257            }
258            p += 32;
259        }
260        h64 = v[0]
261            .rotate_left(1)
262            .wrapping_add(v[1].rotate_left(7))
263            .wrapping_add(v[2].rotate_left(12))
264            .wrapping_add(v[3].rotate_left(18));
265        h64 = xxh64_merge_round(h64, v[0]);
266        h64 = xxh64_merge_round(h64, v[1]);
267        h64 = xxh64_merge_round(h64, v[2]);
268        h64 = xxh64_merge_round(h64, v[3]);
269    } else {
270        h64 = seed.wrapping_add(PRIME64_5);
271    }
272
273    h64 = h64.wrapping_add(len as u64);
274
275    let mut p = (len / 32) * 32;
276    while p + 8 <= len {
277        let lane = u64::from_le_bytes([
278            data[p],
279            data[p + 1],
280            data[p + 2],
281            data[p + 3],
282            data[p + 4],
283            data[p + 5],
284            data[p + 6],
285            data[p + 7],
286        ]);
287        let k1 = lane.wrapping_mul(PRIME64_2).rotate_left(31).wrapping_mul(PRIME64_1);
288        h64 ^= k1;
289        h64 = h64.rotate_left(27).wrapping_mul(PRIME64_1).wrapping_add(PRIME64_4);
290        p += 8;
291    }
292    if p + 4 <= len {
293        let lane = u32::from_le_bytes([data[p], data[p + 1], data[p + 2], data[p + 3]]) as u64;
294        h64 ^= lane.wrapping_mul(PRIME64_1);
295        h64 = h64.rotate_left(23).wrapping_mul(PRIME64_2).wrapping_add(PRIME64_3);
296        p += 4;
297    }
298    while p < len {
299        h64 ^= (data[p] as u64).wrapping_mul(PRIME64_5);
300        h64 = h64.rotate_left(11).wrapping_mul(PRIME64_1);
301        p += 1;
302    }
303
304    let mut h = h64;
305    h ^= h >> 33;
306    h = h.wrapping_mul(PRIME64_2);
307    h ^= h >> 29;
308    h = h.wrapping_mul(PRIME64_3);
309    h ^= h >> 32;
310    h
311}
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316    use crate::{Checksum, test_helpers::fill_test_buffer};
317
318    /// Canonical prime used as seed in the official C test vectors.
319    const TEST_SEED: u64 = 0x9E3779B1; // PRIME32 in C test file, but seed is u64
320
321    #[test]
322    fn test_empty() {
323        assert_eq!(Xxh64::checksum(b""), 0xEF46DB3751D8E999);
324    }
325
326    #[test]
327    fn test_hello() {
328        assert_eq!(Xxh64::checksum(b"hello"), 0x26C7827D889F6DA3);
329    }
330
331    #[test]
332    fn test_fox() {
333        assert_eq!(
334            Xxh64::checksum(b"The quick brown fox jumps over the lazy dog"),
335            0x0B242D361FDA71BC
336        );
337    }
338
339    #[test]
340    fn test_incremental() {
341        let mut h = Xxh64::new();
342        h.update(b"The quick brown ");
343        h.update(b"fox jumps over ");
344        h.update(b"the lazy dog");
345        assert_eq!(h.sum(), 0x0B242D361FDA71BC);
346    }
347
348    /// Official XXH64 test vectors from the C reference's `xsum_sanity_check.c`.
349    #[test]
350    fn test_official_vectors() {
351        let cases: &[(usize, u64, u64)] = &[
352            (0, 0, 0xEF46DB3751D8E999),
353            (0, TEST_SEED, 0xAC75FDA2929B17EF),
354            (1, 0, 0xE934A84ADB052768),
355            (1, TEST_SEED, 0x5014607643A9B4C3),
356            (4, 0, 0x9136A0DCA57457EE),
357            (14, 0, 0x8282DCC4994E35C8),
358            (14, TEST_SEED, 0xC3BD6BF63DEB6DF0),
359            (222, 0, 0xB641AE8CB691C174),
360            (222, TEST_SEED, 0x20CB8AB7AE10C14A),
361        ];
362
363        for &(len, seed, expected) in cases {
364            let buf = fill_test_buffer(len);
365            let mut h = Xxh64::with_seed(seed);
366            h.update(&buf);
367            assert_eq!(h.sum(), expected, "XXH64 length {len} seed {seed:#x}");
368        }
369    }
370
371    /// Byte-at-a-time incremental hashing produces the same result as one-shot.
372    #[test]
373    fn test_byte_at_a_time() {
374        let cases: &[(usize, u64, u64)] = &[
375            (0, 0, 0xEF46DB3751D8E999),
376            (1, TEST_SEED, 0x5014607643A9B4C3),
377            (14, 0, 0x8282DCC4994E35C8),
378            (222, TEST_SEED, 0x20CB8AB7AE10C14A),
379        ];
380
381        for &(len, seed, expected) in cases {
382            let buf = fill_test_buffer(len);
383            let mut h = Xxh64::with_seed(seed);
384            for b in &buf {
385                h.update(&[*b]);
386            }
387            assert_eq!(h.sum(), expected, "XXH64 byte-at-a-time length {len} seed {seed:#x}");
388        }
389    }
390
391    /// The `const fn` one-shot produces the same result as the trait-based
392    /// [`Checksum::checksum`] and is usable at compile time.
393    #[test]
394    fn test_const_fn() {
395        assert_eq!(xxh64(b""), Xxh64::checksum(b""));
396        assert_eq!(xxh64(b"hello"), Xxh64::checksum(b"hello"));
397        assert_eq!(
398            xxh64(b"The quick brown fox jumps over the lazy dog"),
399            Xxh64::checksum(b"The quick brown fox jumps over the lazy dog")
400        );
401        let buf = &[0x42u8; 256];
402        assert_eq!(xxh64(buf), Xxh64::checksum(buf));
403    }
404}
xxhash/xxh64.rs

xxhash/
xxh64.rs
