1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 #![deny(missing_docs)]
12
13 //! # Fx Hash
14 //!
15 //! This hashing algorithm was extracted from the Rustc compiler. This is the same hashing
16 //! algoirthm used for some internal operations in FireFox. The strength of this algorithm
17 //! is in hashing 8 bytes at a time on 64-bit platforms, where the FNV algorithm works on one
18 //! byte at a time.
19 //!
20 //! ## Disclaimer
21 //!
22 //! It is **not a cryptographically secure** hash, so it is strongly recommended that you do
23 //! not use this hash for cryptographic purproses. Furthermore, this hashing algorithm was
24 //! not designed to prevent any attacks for determining collisions which could be used to
25 //! potentially cause quadratic behavior in `HashMap`s. So it is not recommended to expose
26 //! this hash in places where collissions or DDOS attacks may be a concern.
27
28 use std::collections::{HashMap, HashSet};
29 use std::default::Default;
30 use std::hash::{Hasher, Hash, BuildHasherDefault};
31 use std::ops::BitXor;
32
33 extern crate byteorder;
34 use byteorder::{ByteOrder, NativeEndian};
35
36 /// A builder for default Fx hashers.
37 pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
38
39 /// A `HashMap` using a default Fx hasher.
40 pub type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;
41
42 /// A `HashSet` using a default Fx hasher.
43 pub type FxHashSet<V> = HashSet<V, FxBuildHasher>;
44
45 const ROTATE: u32 = 5;
46 const SEED64: u64 = 0x517cc1b727220a95;
47 const SEED32: u32 = (SEED64 & 0xFFFF_FFFF) as u32;
48
49 #[cfg(target_pointer_width = "32")]
50 const SEED: usize = SEED32 as usize;
51 #[cfg(target_pointer_width = "64")]
52 const SEED: usize = SEED64 as usize;
53
54 trait HashWord {
hash_word(&mut self, Self)55 fn hash_word(&mut self, Self);
56 }
57
58 macro_rules! impl_hash_word {
59 ($($ty:ty = $key:ident),* $(,)*) => (
60 $(
61 impl HashWord for $ty {
62 #[inline]
63 fn hash_word(&mut self, word: Self) {
64 *self = self.rotate_left(ROTATE).bitxor(word).wrapping_mul($key);
65 }
66 }
67 )*
68 )
69 }
70
71 impl_hash_word!(usize = SEED, u32 = SEED32, u64 = SEED64);
72
73 #[inline]
write32(mut hash: u32, mut bytes: &[u8]) -> u3274 fn write32(mut hash: u32, mut bytes: &[u8]) -> u32 {
75 while bytes.len() >= 4 {
76 let n = NativeEndian::read_u32(bytes);
77 hash.hash_word(n);
78 bytes = bytes.split_at(4).1;
79 }
80
81 for byte in bytes {
82 hash.hash_word(*byte as u32);
83 }
84 hash
85 }
86
87 #[inline]
write64(mut hash: u64, mut bytes: &[u8]) -> u6488 fn write64(mut hash: u64, mut bytes: &[u8]) -> u64 {
89 while bytes.len() >= 8 {
90 let n = NativeEndian::read_u64(bytes);
91 hash.hash_word(n);
92 bytes = bytes.split_at(8).1;
93 }
94
95 if bytes.len() >= 4 {
96 let n = NativeEndian::read_u32(bytes);
97 hash.hash_word(n as u64);
98 bytes = bytes.split_at(4).1;
99 }
100
101 for byte in bytes {
102 hash.hash_word(*byte as u64);
103 }
104 hash
105 }
106
107 #[inline]
108 #[cfg(target_pointer_width = "32")]
write(hash: usize, bytes: &[u8]) -> usize109 fn write(hash: usize, bytes: &[u8]) -> usize {
110 write32(hash as u32, bytes) as usize
111 }
112
113 #[inline]
114 #[cfg(target_pointer_width = "64")]
write(hash: usize, bytes: &[u8]) -> usize115 fn write(hash: usize, bytes: &[u8]) -> usize {
116 write64(hash as u64, bytes) as usize
117 }
118
119 /// This hashing algorithm was extracted from the Rustc compiler.
120 /// This is the same hashing algoirthm used for some internal operations in FireFox.
121 /// The strength of this algorithm is in hashing 8 bytes at a time on 64-bit platforms,
122 /// where the FNV algorithm works on one byte at a time.
123 ///
124 /// This hashing algorithm should not be used for cryptographic, or in scenarios where
125 /// DOS attacks are a concern.
126 #[derive(Debug, Clone)]
127 pub struct FxHasher {
128 hash: usize,
129 }
130
131 impl Default for FxHasher {
132 #[inline]
default() -> FxHasher133 fn default() -> FxHasher {
134 FxHasher { hash: 0 }
135 }
136 }
137
138 impl Hasher for FxHasher {
139 #[inline]
write(&mut self, bytes: &[u8])140 fn write(&mut self, bytes: &[u8]) {
141 self.hash = write(self.hash, bytes);
142 }
143
144 #[inline]
write_u8(&mut self, i: u8)145 fn write_u8(&mut self, i: u8) {
146 self.hash.hash_word(i as usize);
147 }
148
149 #[inline]
write_u16(&mut self, i: u16)150 fn write_u16(&mut self, i: u16) {
151 self.hash.hash_word(i as usize);
152 }
153
154 #[inline]
write_u32(&mut self, i: u32)155 fn write_u32(&mut self, i: u32) {
156 self.hash.hash_word(i as usize);
157 }
158
159 #[inline]
160 #[cfg(target_pointer_width = "32")]
write_u64(&mut self, i: u64)161 fn write_u64(&mut self, i: u64) {
162 self.hash.hash_word(i as usize);
163 self.hash.hash_word((i >> 32) as usize);
164 }
165
166 #[inline]
167 #[cfg(target_pointer_width = "64")]
write_u64(&mut self, i: u64)168 fn write_u64(&mut self, i: u64) {
169 self.hash.hash_word(i as usize);
170 }
171
172 #[inline]
write_usize(&mut self, i: usize)173 fn write_usize(&mut self, i: usize) {
174 self.hash.hash_word(i);
175 }
176
177 #[inline]
finish(&self) -> u64178 fn finish(&self) -> u64 {
179 self.hash as u64
180 }
181 }
182
183 /// This hashing algorithm was extracted from the Rustc compiler.
184 /// This is the same hashing algoirthm used for some internal operations in FireFox.
185 /// The strength of this algorithm is in hashing 8 bytes at a time on any platform,
186 /// where the FNV algorithm works on one byte at a time.
187 ///
188 /// This hashing algorithm should not be used for cryptographic, or in scenarios where
189 /// DOS attacks are a concern.
190 #[derive(Debug, Clone)]
191 pub struct FxHasher64 {
192 hash: u64,
193 }
194
195 impl Default for FxHasher64 {
196 #[inline]
default() -> FxHasher64197 fn default() -> FxHasher64 {
198 FxHasher64 { hash: 0 }
199 }
200 }
201
202 impl Hasher for FxHasher64 {
203 #[inline]
write(&mut self, bytes: &[u8])204 fn write(&mut self, bytes: &[u8]) {
205 self.hash = write64(self.hash, bytes);
206 }
207
208 #[inline]
write_u8(&mut self, i: u8)209 fn write_u8(&mut self, i: u8) {
210 self.hash.hash_word(i as u64);
211 }
212
213 #[inline]
write_u16(&mut self, i: u16)214 fn write_u16(&mut self, i: u16) {
215 self.hash.hash_word(i as u64);
216 }
217
218 #[inline]
write_u32(&mut self, i: u32)219 fn write_u32(&mut self, i: u32) {
220 self.hash.hash_word(i as u64);
221 }
222
write_u64(&mut self, i: u64)223 fn write_u64(&mut self, i: u64) {
224 self.hash.hash_word(i);
225 }
226
227 #[inline]
write_usize(&mut self, i: usize)228 fn write_usize(&mut self, i: usize) {
229 self.hash.hash_word(i as u64);
230 }
231
232 #[inline]
finish(&self) -> u64233 fn finish(&self) -> u64 {
234 self.hash
235 }
236 }
237
238 /// This hashing algorithm was extracted from the Rustc compiler.
239 /// This is the same hashing algoirthm used for some internal operations in FireFox.
240 /// The strength of this algorithm is in hashing 4 bytes at a time on any platform,
241 /// where the FNV algorithm works on one byte at a time.
242 ///
243 /// This hashing algorithm should not be used for cryptographic, or in scenarios where
244 /// DOS attacks are a concern.
245 #[derive(Debug, Clone)]
246 pub struct FxHasher32 {
247 hash: u32,
248 }
249
250 impl Default for FxHasher32 {
251 #[inline]
default() -> FxHasher32252 fn default() -> FxHasher32 {
253 FxHasher32 { hash: 0 }
254 }
255 }
256
257 impl Hasher for FxHasher32 {
258 #[inline]
write(&mut self, bytes: &[u8])259 fn write(&mut self, bytes: &[u8]) {
260 self.hash = write32(self.hash, bytes);
261 }
262
263 #[inline]
write_u8(&mut self, i: u8)264 fn write_u8(&mut self, i: u8) {
265 self.hash.hash_word(i as u32);
266 }
267
268 #[inline]
write_u16(&mut self, i: u16)269 fn write_u16(&mut self, i: u16) {
270 self.hash.hash_word(i as u32);
271 }
272
273 #[inline]
write_u32(&mut self, i: u32)274 fn write_u32(&mut self, i: u32) {
275 self.hash.hash_word(i);
276 }
277
278 #[inline]
write_u64(&mut self, i: u64)279 fn write_u64(&mut self, i: u64) {
280 self.hash.hash_word(i as u32);
281 self.hash.hash_word((i >> 32) as u32);
282 }
283
284 #[inline]
285 #[cfg(target_pointer_width = "32")]
write_usize(&mut self, i: usize)286 fn write_usize(&mut self, i: usize) {
287 self.write_u32(i as u32);
288 }
289
290 #[inline]
291 #[cfg(target_pointer_width = "64")]
write_usize(&mut self, i: usize)292 fn write_usize(&mut self, i: usize) {
293 self.write_u64(i as u64);
294 }
295
296 #[inline]
finish(&self) -> u64297 fn finish(&self) -> u64 {
298 self.hash as u64
299 }
300 }
301
302 /// A convenience function for when you need a quick 64-bit hash.
303 #[inline]
hash64<T: Hash + ?Sized>(v: &T) -> u64304 pub fn hash64<T: Hash + ?Sized>(v: &T) -> u64 {
305 let mut state = FxHasher64::default();
306 v.hash(&mut state);
307 state.finish()
308 }
309
310 /// A convenience function for when you need a quick 32-bit hash.
311 #[inline]
hash32<T: Hash + ?Sized>(v: &T) -> u32312 pub fn hash32<T: Hash + ?Sized>(v: &T) -> u32 {
313 let mut state = FxHasher32::default();
314 v.hash(&mut state);
315 state.finish() as u32
316 }
317
318 /// A convenience function for when you need a quick usize hash.
319 #[inline]
hash<T: Hash + ?Sized>(v: &T) -> usize320 pub fn hash<T: Hash + ?Sized>(v: &T) -> usize {
321 let mut state = FxHasher::default();
322 v.hash(&mut state);
323 state.finish() as usize
324 }