1 //! Fast, non-cryptographic hash used by rustc and Firefox.
2 
3 use core::default::Default;
4 use core::hash::{BuildHasherDefault, Hasher};
5 use core::mem::size_of;
6 use core::ops::BitXor;
7 
8 /// Type alias for a `HashBuilder` using the `fx` hash algorithm.
9 pub type FxHashBuilder = BuildHasherDefault<FxHasher>;
10 
11 /// A speedy hash algorithm for use within rustc. The hashmap in liballoc
12 /// by default uses SipHash which isn't quite as speedy as we want. In the
13 /// compiler we're not really worried about DOS attempts, so we use a fast
14 /// non-cryptographic hash.
15 ///
16 /// This is the same as the algorithm used by Firefox -- which is a homespun
17 /// one not based on any widely-known algorithm -- though modified to produce
18 /// 64-bit hash values instead of 32-bit hash values. It consistently
19 /// out-performs an FNV-based hash within rustc itself -- the collision rate is
20 /// similar or slightly worse than FNV, but the speed of the hash function
21 /// itself is much higher because it works on up to 8 bytes at a time.
22 pub struct FxHasher {
23     hash: usize,
24 }
25 
26 #[cfg(target_pointer_width = "32")]
27 const K: usize = 0x9e37_79b9;
28 #[cfg(target_pointer_width = "64")]
29 const K: usize = 0x517c_c1b7_2722_0a95;
30 
31 impl Default for FxHasher {
32     #[inline]
default() -> Self33     fn default() -> Self {
34         Self { hash: 0 }
35     }
36 }
37 
38 impl FxHasher {
39     #[inline]
add_to_hash(&mut self, i: usize)40     fn add_to_hash(&mut self, i: usize) {
41         self.hash = self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);
42     }
43 }
44 
45 impl Hasher for FxHasher {
46     #[inline]
write(&mut self, mut bytes: &[u8])47     fn write(&mut self, mut bytes: &[u8]) {
48         macro_rules! read_bytes {
49             ($ty:ty, $src:expr) => {{
50                 assert!(size_of::<$ty>() <= $src.len());
51                 let mut data: $ty = 0;
52                 unsafe {
53                     $src.as_ptr()
54                         .copy_to_nonoverlapping(&mut data as *mut $ty as *mut u8, size_of::<$ty>());
55                 }
56                 data
57             }};
58         }
59 
60         let mut hash = Self { hash: self.hash };
61         assert!(size_of::<usize>() <= 8);
62         while bytes.len() >= size_of::<usize>() {
63             hash.add_to_hash(read_bytes!(usize, bytes) as usize);
64             bytes = &bytes[size_of::<usize>()..];
65         }
66         if (size_of::<usize>() > 4) && (bytes.len() >= 4) {
67             hash.add_to_hash(read_bytes!(u32, bytes) as usize);
68             bytes = &bytes[4..];
69         }
70         if (size_of::<usize>() > 2) && bytes.len() >= 2 {
71             hash.add_to_hash(read_bytes!(u16, bytes) as usize);
72             bytes = &bytes[2..];
73         }
74         if (size_of::<usize>() > 1) && !bytes.is_empty() {
75             hash.add_to_hash(bytes[0] as usize);
76         }
77         self.hash = hash.hash;
78     }
79 
80     #[inline]
write_u8(&mut self, i: u8)81     fn write_u8(&mut self, i: u8) {
82         self.add_to_hash(i as usize);
83     }
84 
85     #[inline]
write_u16(&mut self, i: u16)86     fn write_u16(&mut self, i: u16) {
87         self.add_to_hash(i as usize);
88     }
89 
90     #[inline]
write_u32(&mut self, i: u32)91     fn write_u32(&mut self, i: u32) {
92         self.add_to_hash(i as usize);
93     }
94 
95     #[cfg(target_pointer_width = "32")]
96     #[inline]
97     #[allow(clippy::cast_possible_truncation)]
write_u64(&mut self, i: u64)98     fn write_u64(&mut self, i: u64) {
99         self.add_to_hash(i as usize);
100         self.add_to_hash((i >> 32) as usize);
101     }
102 
103     #[cfg(target_pointer_width = "64")]
104     #[inline]
105     #[allow(clippy::cast_possible_truncation)]
write_u64(&mut self, i: u64)106     fn write_u64(&mut self, i: u64) {
107         self.add_to_hash(i as usize);
108     }
109 
110     #[inline]
write_usize(&mut self, i: usize)111     fn write_usize(&mut self, i: usize) {
112         self.add_to_hash(i);
113     }
114 
115     #[inline]
finish(&self) -> u64116     fn finish(&self) -> u64 {
117         self.hash as u64
118     }
119 }
120