zstd_rs/
xxh64.rs

1//! XXH64 (seed 0 in zstd), streaming, used for the optional frame content checksum.
2const P1: u64 = 0x9E37_79B1_85EB_CA87;
3const P2: u64 = 0xC2B2_AE3D_27D4_EB4F;
4const P3: u64 = 0x1656_67B1_9E37_79F9;
5const P4: u64 = 0x85EB_CA77_C2B2_AE63;
6const P5: u64 = 0x27D4_EB2F_1656_67C5;
7
8#[inline(always)]
9fn round(acc: u64, lane: u64) -> u64 {
10    acc.wrapping_add(lane.wrapping_mul(P2)).rotate_left(31).wrapping_mul(P1)
11}
12
13#[inline(always)]
14fn merge(acc: u64, v: u64) -> u64 {
15    (acc ^ round(0, v)).wrapping_mul(P1).wrapping_add(P4)
16}
17
18#[inline(always)]
19fn le64(b: &[u8]) -> u64 {
20    let mut a = [0u8; 8];
21    a.copy_from_slice(&b[..8]);
22    u64::from_le_bytes(a)
23}
24
25/// Incremental XXH64 state.
26#[derive(Clone)]
27pub struct Xxh64 {
28    v: [u64; 4],
29    buf: [u8; 32],
30    buf_len: usize,
31    total: u64,
32    seed: u64,
33}
34
35impl Xxh64 {
36    /// Starts a hash with the given seed (zstd uses 0).
37    pub fn new(seed: u64) -> Self {
38        Xxh64 {
39            v: [seed.wrapping_add(P1).wrapping_add(P2), seed.wrapping_add(P2), seed, seed.wrapping_sub(P1)],
40            buf: [0; 32],
41            buf_len: 0,
42            total: 0,
43            seed,
44        }
45    }
46
47    fn stripe(v: &mut [u64; 4], s: &[u8]) {
48        v[0] = round(v[0], le64(&s[0..]));
49        v[1] = round(v[1], le64(&s[8..]));
50        v[2] = round(v[2], le64(&s[16..]));
51        v[3] = round(v[3], le64(&s[24..]));
52    }
53
54    /// Feeds more bytes.
55    pub fn update(&mut self, mut data: &[u8]) {
56        self.total = self.total.wrapping_add(data.len() as u64);
57        if self.buf_len > 0 {
58            let take = (32 - self.buf_len).min(data.len());
59            self.buf[self.buf_len..self.buf_len + take].copy_from_slice(&data[..take]);
60            self.buf_len += take;
61            data = &data[take..];
62            if self.buf_len < 32 {
63                return;
64            }
65            let b = self.buf;
66            Self::stripe(&mut self.v, &b);
67            self.buf_len = 0;
68        }
69        let mut chunks = data.chunks_exact(32);
70        for c in &mut chunks {
71            Self::stripe(&mut self.v, c);
72        }
73        let rest = chunks.remainder();
74        self.buf[..rest.len()].copy_from_slice(rest);
75        self.buf_len = rest.len();
76    }
77
78    /// Returns the 64-bit digest (the state is not consumed).
79    pub fn digest(&self) -> u64 {
80        let mut h = if self.total >= 32 {
81            let v = self.v;
82            let mut h =
83                v[0].rotate_left(1).wrapping_add(v[1].rotate_left(7)).wrapping_add(v[2].rotate_left(12)).wrapping_add(v[3].rotate_left(18));
84            for x in v {
85                h = merge(h, x);
86            }
87            h
88        } else {
89            self.seed.wrapping_add(P5)
90        };
91        h = h.wrapping_add(self.total);
92        let mut rest = &self.buf[..self.buf_len];
93        while rest.len() >= 8 {
94            h ^= round(0, le64(rest));
95            h = h.rotate_left(27).wrapping_mul(P1).wrapping_add(P4);
96            rest = &rest[8..];
97        }
98        if rest.len() >= 4 {
99            let w = u32::from_le_bytes([rest[0], rest[1], rest[2], rest[3]]) as u64;
100            h ^= w.wrapping_mul(P1);
101            h = h.rotate_left(23).wrapping_mul(P2).wrapping_add(P3);
102            rest = &rest[4..];
103        }
104        for &b in rest {
105            h ^= (b as u64).wrapping_mul(P5);
106            h = h.rotate_left(11).wrapping_mul(P1);
107        }
108        h ^= h >> 33;
109        h = h.wrapping_mul(P2);
110        h ^= h >> 29;
111        h = h.wrapping_mul(P3);
112        h ^ (h >> 32)
113    }
114}
115
116/// One-shot XXH64.
117pub fn xxh64(data: &[u8], seed: u64) -> u64 {
118    let mut h = Xxh64::new(seed);
119    h.update(data);
120    h.digest()
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn known_vectors() {
129        assert_eq!(xxh64(b"", 0), 0xEF46_DB37_51D8_E999);
130        assert_eq!(xxh64(b"a", 0), 0xD24E_C4F1_A98C_6E5B);
131        assert_eq!(xxh64(b"abc", 0), 0x44BC_2CF5_AD77_0999);
132        let long = b"Nobody inspects the spammish repetition";
133        assert_eq!(xxh64(long, 0), 0xFBCE_A83C_8A37_8BF1);
134    }
135
136    #[test]
137    fn streaming_matches_one_shot() {
138        let data: alloc::vec::Vec<u8> = (0..1000u32).map(|i| (i * 7 + 3) as u8).collect();
139        for split in [0, 1, 7, 31, 32, 33, 500, 999, 1000] {
140            let mut h = Xxh64::new(0);
141            h.update(&data[..split]);
142            h.update(&data[split..]);
143            assert_eq!(h.digest(), xxh64(&data, 0), "split {split}");
144        }
145    }
146}
zstd_rs/xxh64.rs

zstd_rs/
xxh64.rs
