xxhash/
xxh32.rs

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

xxhash/
xxh32.rs
