murmur3_32/
lib.rs

1#![no_std]
2
3#[cfg(any(test, feature = "std"))]
4mod io;
5#[cfg(any(test, feature = "std"))]
6pub use io::Murmur3Io;
7
8const C1: u32 = 0xcc9e_2d51;
9const C2: u32 = 0x1b87_3593;
10const D: u32 = 0xe654_6b64;
11const FMIX1: u32 = 0x85eb_ca6b;
12const FMIX2: u32 = 0xc2b2_ae35;
13
14const DEFAULT_SEED: u32 = 0;
15
16pub struct Murmur3 {
17    h: u32,
18    len: u32,
19    remainder: [u8; 4],
20    remainder_len: u8,
21}
22impl Murmur3 {
23    #[inline]
24    pub fn new(seed: u32) -> Self {
25        Self {
26            h: seed,
27            remainder: [0, 0, 0, 0],
28            remainder_len: 0,
29            len: 0,
30        }
31    }
32    #[inline]
33    pub fn hash<B: AsRef<[u8]>>(seed: u32, data: B) -> u32 {
34        hash_bytes(seed, data.as_ref())
35    }
36    #[inline(always)]
37    fn spare(&mut self) -> &mut [u8] {
38        &mut self.remainder[self.remainder_len as usize..]
39    }
40    #[inline]
41    pub fn write(&mut self, data: &[u8]) {
42        self.len = self.len.wrapping_add(data.len() as u32);
43        if self.remainder_len as usize + data.len() < 4 {
44            self.spare()[..data.len()].copy_from_slice(data);
45            self.remainder_len += data.len() as u8;
46            return;
47        }
48        let spare = self.spare();
49        let (first, data) = &data.split_at(spare.len());
50        spare.copy_from_slice(first);
51        self.h = one_round(self.h, self.remainder);
52
53        let mut it = data.chunks_exact(4);
54        for chunk in it.by_ref() {
55            self.h = one_round(self.h, chunk.try_into().unwrap());
56        }
57        self.remainder_len = data.len() as u8 & 3;
58        self.remainder[..self.remainder_len as usize].copy_from_slice(it.remainder());
59    }
60    #[inline]
61    pub fn finish(mut self) -> u32 {
62        let rem_len = self.remainder_len as usize;
63        if rem_len > 0 {
64            self.remainder[rem_len..].fill(0);
65            self.h ^= calc_k(self.remainder);
66        }
67        fmix32(self.h ^ self.len)
68    }
69}
70
71#[inline(always)]
72fn calc_k(chunk: [u8; 4]) -> u32 {
73    u32::from_le_bytes(chunk)
74        .wrapping_mul(C1)
75        .rotate_left(15)
76        .wrapping_mul(C2)
77}
78#[inline(always)]
79fn one_round(h: u32, chunk: [u8; 4]) -> u32 {
80    (h ^ calc_k(chunk))
81        .rotate_left(13)
82        .wrapping_mul(5)
83        .wrapping_add(D)
84}
85#[inline(always)]
86fn fmix32(mut h: u32) -> u32 {
87    h = (h ^ h >> 16).wrapping_mul(FMIX1);
88    h = (h ^ h >> 13).wrapping_mul(FMIX2);
89    h ^ h >> 16
90}
91
92#[inline]
93fn hash_bytes(mut seed: u32, data: &[u8]) -> u32 {
94    let mut it = data.chunks_exact(4);
95    for chunk in it.by_ref() {
96        seed = one_round(seed, chunk.try_into().unwrap());
97    }
98    let rem = it.remainder();
99    if rem.len() > 0 {
100        let mut last_chunk = [0, 0, 0, 0];
101        last_chunk[..rem.len()].copy_from_slice(rem);
102        seed ^= calc_k(last_chunk);
103    }
104    fmix32(seed ^ data.len() as u32)
105}
106
107impl core::hash::Hasher for Murmur3 {
108    fn write(&mut self, bytes: &[u8]) {
109        self.write(bytes);
110    }
111    fn finish(&self) -> u64 {
112        let mut h = self.h;
113        let rem_len = self.remainder_len as usize;
114        if rem_len > 0 {
115            let mut rem = self.remainder;
116            rem[rem_len..].fill(0);
117            h ^= calc_k(rem);
118        }
119        fmix32(h ^ self.len) as _
120    }
121}
122
123impl core::default::Default for Murmur3 {
124    fn default() -> Self {
125        Self::new(DEFAULT_SEED)
126    }
127}
128
129#[cfg(test)]
130mod test {
131    extern crate std;
132
133    use super::*;
134    use std::{
135        io::{self, Write},
136        vec::Vec,
137    };
138
139    fn hash(bytes: &[u8]) -> u32 {
140        const SEED: u32 = 3_242_157_231;
141
142        let mut hasher = Murmur3::new(SEED);
143        let mut hasher2 = Murmur3::new(SEED);
144        let mut buf = Vec::<u8>::new();
145        let mut writer = Murmur3Io::new(SEED, &mut buf);
146
147        hasher.write(bytes);
148        std::hash::Hasher::write(&mut hasher2, bytes);
149        writer.write(bytes).unwrap();
150        assert_eq!(hasher.len as usize, bytes.len());
151        assert_eq!(hasher2.len as usize, bytes.len());
152        assert_eq!(writer.hasher.len as usize, bytes.len());
153        let (ret, _) = writer.finish();
154        assert_eq!(Murmur3::hash(SEED, bytes), ret);
155        assert_eq!(hasher.finish(), ret);
156        assert_eq!(std::hash::Hasher::finish(&hasher2), ret as u64);
157
158        let mut reader = Murmur3Io::new(SEED, buf.as_slice());
159        io::copy(&mut reader, &mut io::empty()).unwrap();
160        let (hash, _) = reader.finish();
161        assert_eq!(hash, ret);
162        ret
163    }
164
165    #[test]
166    fn murmur3() {
167        assert_eq!(hash(b""), 36_859_204);
168        assert_eq!(hash(b"a"), 3_144_985_375);
169        assert_eq!(hash(b"ab"), 3_262_304_301);
170        assert_eq!(hash(b"abc"), 476_091_040);
171        assert_eq!(hash(b"abcd"), 412_992_581);
172        assert_eq!(hash(b"abcde"), 2_747_833_956);
173        assert_eq!(hash(b"abcdefghijklmnop"), 2_078_305_053);
174    }
175}
murmur3_32/lib.rs

murmur3_32/
lib.rs
