Skip to main content

zero_client/hash/
xxhash32.rs

1//! xxHash32 over UTF-8 bytes, and the wider `h64`/`h128` built from it
2//! (`packages/shared/src/hash.ts`).
3
4pub const PRIME1: u32 = 2_654_435_761;
5pub const PRIME2: u32 = 2_246_822_519;
6pub const PRIME3: u32 = 3_266_489_917;
7pub const PRIME4: u32 = 668_265_263;
8pub const PRIME5: u32 = 374_761_393;
9
10#[inline]
11pub fn round(acc: u32, word: u32) -> u32 {
12    acc.wrapping_add(word.wrapping_mul(PRIME2))
13        .rotate_left(13)
14        .wrapping_mul(PRIME1)
15}
16
17#[inline]
18pub fn avalanche(mut acc: u32) -> u32 {
19    acc ^= acc >> 15;
20    acc = acc.wrapping_mul(PRIME2);
21    acc ^= acc >> 13;
22    acc = acc.wrapping_mul(PRIME3);
23    acc ^= acc >> 16;
24    acc
25}
26
27/// Reference xxHash32 of `bytes` with `seed`.
28pub fn hash(bytes: &[u8], seed: u32) -> u32 {
29    let word = |b: &[u8]| u32::from_le_bytes([b[0], b[1], b[2], b[3]]);
30    let mut rest = bytes;
31    let mut acc = if bytes.len() >= 16 {
32        let mut v = [
33            seed.wrapping_add(PRIME1).wrapping_add(PRIME2),
34            seed.wrapping_add(PRIME2),
35            seed,
36            seed.wrapping_sub(PRIME1),
37        ];
38        while rest.len() >= 16 {
39            for (lane, chunk) in v.iter_mut().zip(rest[..16].as_chunks::<4>().0) {
40                *lane = round(*lane, word(chunk));
41            }
42            rest = &rest[16..];
43        }
44        v[0].rotate_left(1)
45            .wrapping_add(v[1].rotate_left(7))
46            .wrapping_add(v[2].rotate_left(12))
47            .wrapping_add(v[3].rotate_left(18))
48    } else {
49        seed.wrapping_add(PRIME5)
50    };
51    acc = acc.wrapping_add(bytes.len() as u32);
52    while rest.len() >= 4 {
53        acc = acc
54            .wrapping_add(word(rest).wrapping_mul(PRIME3))
55            .rotate_left(17)
56            .wrapping_mul(PRIME4);
57        rest = &rest[4..];
58    }
59    for &b in rest {
60        acc = acc
61            .wrapping_add(u32::from(b).wrapping_mul(PRIME5))
62            .rotate_left(11)
63            .wrapping_mul(PRIME1);
64    }
65    avalanche(acc)
66}
67
68/// `h32(s)`: xxHash32 of the UTF-8 bytes of `s`, seed 0.
69pub fn h32(s: &str) -> u32 {
70    hash(s.as_bytes(), 0)
71}
72
73/// `h64(s)`: the seed-0 digest in the high word, seed-1 in the low word.
74pub fn h64(s: &str) -> u64 {
75    u64::from(hash(s.as_bytes(), 0)) << 32 | u64::from(hash(s.as_bytes(), 1))
76}
77
78/// `h128(s)`: the digests for seeds 0 to 3, highest-order word first.
79pub fn h128(s: &str) -> u128 {
80    (0..4).fold(0, |r, seed| r << 32 | u128::from(hash(s.as_bytes(), seed)))
81}