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