fxhash/
lib.rs

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
28use std::collections::{HashMap, HashSet};
29use std::default::Default;
30use std::hash::{Hasher, Hash, BuildHasherDefault};
31use std::ops::BitXor;
32
33extern crate byteorder;
34use byteorder::{ByteOrder, NativeEndian};
35
36/// A builder for default Fx hashers.
37pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
38
39/// A `HashMap` using a default Fx hasher.
40pub type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;
41
42/// A `HashSet` using a default Fx hasher.
43pub type FxHashSet<V> = HashSet<V, FxBuildHasher>;
44
45const ROTATE: u32 = 5;
46const SEED64: u64 = 0x517cc1b727220a95;
47const SEED32: u32 = (SEED64 & 0xFFFF_FFFF) as u32;
48
49#[cfg(target_pointer_width = "32")]
50const SEED: usize = SEED32 as usize;
51#[cfg(target_pointer_width = "64")]
52const SEED: usize = SEED64 as usize;
53
54trait HashWord {
55    fn hash_word(&mut self, Self);
56}
57
58macro_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
71impl_hash_word!(usize = SEED, u32 = SEED32, u64 = SEED64);
72
73#[inline]
74fn 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]
88fn 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")]
109fn write(hash: usize, bytes: &[u8]) -> usize {
110    write32(hash as u32, bytes) as usize
111}
112
113#[inline]
114#[cfg(target_pointer_width = "64")]
115fn 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)]
127pub struct FxHasher {
128    hash: usize,
129}
130
131impl Default for FxHasher {
132    #[inline]
133    fn default() -> FxHasher {
134        FxHasher { hash: 0 }
135    }
136}
137
138impl Hasher for FxHasher {
139    #[inline]
140    fn write(&mut self, bytes: &[u8]) {
141        self.hash = write(self.hash, bytes);
142    }
143
144    #[inline]
145    fn write_u8(&mut self, i: u8) {
146        self.hash.hash_word(i as usize);
147    }
148
149    #[inline]
150    fn write_u16(&mut self, i: u16) {
151        self.hash.hash_word(i as usize);
152    }
153
154    #[inline]
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")]
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")]
168    fn write_u64(&mut self, i: u64) {
169        self.hash.hash_word(i as usize);
170    }
171
172    #[inline]
173    fn write_usize(&mut self, i: usize) {
174        self.hash.hash_word(i);
175    }
176
177    #[inline]
178    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)]
191pub struct FxHasher64 {
192    hash: u64,
193}
194
195impl Default for FxHasher64 {
196    #[inline]
197    fn default() -> FxHasher64 {
198        FxHasher64 { hash: 0 }
199    }
200}
201
202impl Hasher for FxHasher64 {
203    #[inline]
204    fn write(&mut self, bytes: &[u8]) {
205        self.hash = write64(self.hash, bytes);
206    }
207
208    #[inline]
209    fn write_u8(&mut self, i: u8) {
210        self.hash.hash_word(i as u64);
211    }
212
213    #[inline]
214    fn write_u16(&mut self, i: u16) {
215        self.hash.hash_word(i as u64);
216    }
217
218    #[inline]
219    fn write_u32(&mut self, i: u32) {
220        self.hash.hash_word(i as u64);
221    }
222
223    fn write_u64(&mut self, i: u64) {
224        self.hash.hash_word(i);
225    }
226
227    #[inline]
228    fn write_usize(&mut self, i: usize) {
229        self.hash.hash_word(i as u64);
230    }
231
232    #[inline]
233    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)]
246pub struct FxHasher32 {
247    hash: u32,
248}
249
250impl Default for FxHasher32 {
251    #[inline]
252    fn default() -> FxHasher32 {
253        FxHasher32 { hash: 0 }
254    }
255}
256
257impl Hasher for FxHasher32 {
258    #[inline]
259    fn write(&mut self, bytes: &[u8]) {
260        self.hash = write32(self.hash, bytes);
261    }
262
263    #[inline]
264    fn write_u8(&mut self, i: u8) {
265        self.hash.hash_word(i as u32);
266    }
267
268    #[inline]
269    fn write_u16(&mut self, i: u16) {
270        self.hash.hash_word(i as u32);
271    }
272
273    #[inline]
274    fn write_u32(&mut self, i: u32) {
275        self.hash.hash_word(i);
276    }
277
278    #[inline]
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")]
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")]
292    fn write_usize(&mut self, i: usize) {
293        self.write_u64(i as u64);
294    }
295
296    #[inline]
297    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]
304pub 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]
312pub 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]
320pub 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}
fxhash/lib.rs

fxhash/
lib.rs
