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