devela/data/codec/hash/
fnv.rs

Help
1// devela::data::codec::hash::fnv
2
3use crate::{concat as cc, stringify as fy, Cast, ConstDefault, Hasher, HasherBuildDefault};
4
5/// A builder for default Fnv hashers.
6pub type HasherBuildFnv = HasherBuildDefault<HasherFnv<usize>>;
7
8/// A Fowler–Noll–Vo hasher, implemented for
9/// [u32](#impl-HasherFnv<u32>),
10/// [u64](#impl-HasherFnv<u64>),
11/// [u128](#impl-HasherFnv<u128>) &
12/// [usize](#impl-HasherFnv<usize>).
13///
14/// It uses the `fnv-1a` variation which gives better avalanche characteristics.
15///
16/// See
17/// - <https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function>
18/// - <http://www.isthe.com/chongo/tech/comp/fnv>
19#[must_use]
20#[derive(Clone, Copy, Debug, PartialEq, Eq)]
21pub struct HasherFnv<T> {
22    state: T,
23}
24
25const BASIS32: u32 = 0x811c_9dc5;
26const PRIME32: u32 = 0x0100_0193;
27const BASIS64: u64 = 0xcbf2_9ce4_8422_2325;
28const PRIME64: u64 = 0x0000_0100_0000_01B3;
29const BASIS128: u128 = 0x6c62_272e_07bb_0142_62b8_2175_6295_c58d;
30const PRIME128: u128 = 0x0000_0000_0100_0000_0000_0000_0000_013B;
31
32macro_rules! impl_fnv {
33    () => {
34        impl_fnv![u32:BASIS32:PRIME32, u64:BASIS64:PRIME64, u128:BASIS128:PRIME128];
35        #[cfg(target_pointer_width = "32")]
36        impl_fnv![usize:BASIS32:PRIME32];
37        #[cfg(target_pointer_width = "64")]
38        impl_fnv![usize:BASIS64:PRIME64];
39    };
40
41    ($($t:ty:$basis:ident:$prime:ident),+) =>  { $( impl_fnv![@$t:$basis:$prime]; )+ };
42    (@$t:ty:$basis:ident:$prime:ident) =>  {
43
44        impl ConstDefault for HasherFnv<$t> { const DEFAULT: Self = Self { state: $basis as $t }; }
45        impl Default for HasherFnv<$t> { fn default() -> Self { Self::DEFAULT } }
46
47        impl HasherFnv<$t> {
48            /* state-full methods */
49
50            /// Returns a default FNV hasher.
51            pub const fn new() -> Self { Self::DEFAULT }
52
53            /// Returns an FNV hasher with the given `input` data.
54            pub const fn with(input: &[u8]) -> Self { Self { state: Self::hash(input) } }
55
56            /// Returns the current hash value.
57            #[must_use]
58            pub const fn get(&self) -> $t { self.state }
59
60            /// Returns the hash value with lazy mod mapping to the given `range`.
61            #[must_use]
62            pub const fn get_hash_mod_lazy(&self, range: $t) -> $t {
63                self.state % range
64            }
65
66            /// Returns the hash value with retried mod mapping to the given `range`.
67            #[must_use]
68            pub const fn get_hash_mod_retry(&self, range: $t) -> $t {
69                Self::mod_retry_hash(self.state, range)
70            }
71
72            /// Returns the hash value xor folded to `n` bits.
73            ///
74            /// # Panics
75            #[doc =  cc!["Panics in debug if `n` exceeds [`", fy![$t], "::BITS`]."]]
76            #[must_use]
77            pub const fn get_hash_n_bits(&self, n: usize) -> $t {
78                Self::fold_hash(self.state, n)
79            }
80
81            /// Updates the hasher with more data.
82            ///
83            /// Allows the hasher to receive additional bytes incrementally.
84            pub const fn update(&mut self, input: &[u8]) {
85                let mut i = 0;
86                while i < input.len() {
87                    self.state ^= input[i] as $t;
88                    self.state = self.state.wrapping_mul($prime as $t);
89                    i += 1;
90                }
91            }
92
93            /// Resets the inner state to the default basis value.
94            pub const fn reset(&mut self) {
95                self.state = $basis as $t;
96            }
97
98            /* state-less methods */
99
100            /// Computes the FNV hash of the provided byte slice.
101            #[must_use]
102            pub const fn hash(input: &[u8]) -> $t {
103                let mut hash = $basis as $t;
104                let mut i = 0;
105                while i < input.len() {
106                    hash ^= input[i] as $t;
107                    hash = hash.wrapping_mul($prime as $t);
108                    i += 1;
109                }
110                hash
111            }
112
113            /// Maps the computed FNV hash to the given `range` using lazy mod mapping.
114            ///
115            /// This method only does an additional mod at the end.
116            /// But there's a small bias against the larger values.
117            #[must_use]
118            pub const fn hash_mod_lazy(input: &[u8], range: $t) -> $t {
119                Self::hash(input) % range
120            }
121
122            /// Maps the computed FNV hash to the given `range` using retried mod mapping.
123            #[must_use]
124            pub const fn hash_mod_retry(input: &[u8], range: $t) -> $t {
125                let mut hash = Self::hash(input);
126                let retry_level = (<$t>::MAX / range) * range;
127                while hash >= retry_level {
128                    hash = (hash.wrapping_mul($prime as $t)).wrapping_add($basis as $t);
129                }
130                hash % range
131            }
132
133            /// Computes the FNV hash of the provided byte slice, xor folded to `n` bits.
134            ///
135            /// # Panics
136            #[doc =  cc!["Panics in debug if `n` exceeds [`", fy![$t], "::BITS`]."]]
137            #[must_use]
138            pub const fn hash_n_bits(input: &[u8], n: usize) -> $t {
139                Self::fold_hash(Self::hash(input), n)
140            }
141
142            /* helper methods */
143
144            /// Reduces a hash to `n` bits using xor folding.
145            ///
146            /// # Panics
147            #[doc =  cc!["Panics in debug if `n` exceeds [`", fy![$t], "::BITS`]."]]
148            #[must_use]
149            pub const fn fold_hash(mut hash: $t, n: usize) -> $t {
150                debug_assert![n <= <$t>::BITS as usize];
151                let full_bits = <$t>::BITS as usize;
152                let mask = (1 << n) - 1;
153                // if n < full_bits { // MAYBE an alterantive to panicking
154                let right_shifted = hash >> (full_bits - n);
155                hash ^= right_shifted;
156                hash & mask
157            }
158
159            /// Maps a hash to the given `range` using retried mod mapping.
160            ///
161            /// Ensures that the hash value is uniform and unbiased within the range.
162            #[must_use]
163            pub const fn mod_retry_hash(mut hash: $t, range: $t) -> $t {
164                let retry_level = (<$t>::MAX / range) * range;
165                while hash >= retry_level {
166                    hash = (hash.wrapping_mul($prime as $t)).wrapping_add($basis as $t);
167                }
168                hash % range
169            }
170        }
171
172        impl Hasher for HasherFnv<$t> {
173            fn write(&mut self, bytes: &[u8]) {
174                for byte in bytes {
175                    self.state ^= <$t>::from(*byte);
176                    self.state = self.state.wrapping_mul($prime as $t);
177                }
178            }
179            fn finish(&self) -> u64 {
180                Cast(self.state).wrapping_cast_to_u64()
181            }
182        }
183    };
184}
185impl_fnv!();
186
187#[cfg(test)]
188mod tests {
189    use super::HasherFnv;
190
191    #[test]
192    fn fnv1a_32() {
193        assert_eq!(HasherFnv::<u32>::hash(b""), 0x811c9dc5);
194        assert_eq!(HasherFnv::<u32>::hash(b"a"), 0xe40c292c);
195        assert_eq!(HasherFnv::<u32>::hash(b"foobar"), 0xbf9cf968);
196    }
197    #[test]
198    fn fnv1a_64() {
199        assert_eq!(HasherFnv::<u64>::hash(b""), 0xcbf29ce484222325);
200        assert_eq!(HasherFnv::<u64>::hash(b"a"), 0xaf63dc4c8601ec8c);
201        assert_eq!(HasherFnv::<u64>::hash(b"foobar"), 0x85944171f73967e8);
202    }
203    #[test]
204    fn fnv1a_128() {
205        assert_eq!(HasherFnv::<u128>::hash(b""), 0x6C62272E07BB014262B821756295C58D);
206        assert_eq!(HasherFnv::<u128>::hash(b"a"), 0xD228CB696F1A8CAF78912B704E4A8964);
207        assert_eq!(HasherFnv::<u128>::hash(b"foobar"), 0x343E1662793C64BF6F0D3597BA446F18);
208    }
209}
devela/data/codec/hash/fnv.rs

devela/data/codec/hash/
fnv.rs
