1 use crate::convert::*; 2 use crate::operations::folded_multiply; 3 #[cfg(feature = "specialize")] 4 use crate::HasherExt; 5 use core::hash::Hasher; 6 use crate::RandomState; 7 use crate::random_state::PI; 8 9 ///This constant come from Kunth's prng (Empirically it works better than those from splitmix32). 10 pub(crate) const MULTIPLE: u64 = 6364136223846793005; 11 const ROT: u32 = 23; //17 12 13 /// A `Hasher` for hashing an arbitrary stream of bytes. 14 /// 15 /// Instances of [`AHasher`] represent state that is updated while hashing data. 16 /// 17 /// Each method updates the internal state based on the new data provided. Once 18 /// all of the data has been provided, the resulting hash can be obtained by calling 19 /// `finish()` 20 /// 21 /// [Clone] is also provided in case you wish to calculate hashes for two different items that 22 /// start with the same data. 23 /// 24 #[derive(Debug, Clone)] 25 pub struct AHasher { 26 buffer: u64, 27 pad: u64, 28 extra_keys: [u64; 2], 29 } 30 31 impl AHasher { 32 /// Creates a new hasher keyed to the provided key. 33 #[inline] 34 #[allow(dead_code)] // Is not called if non-fallback hash is used. new_with_keys(key1: u128, key2: u128) -> AHasher35 pub fn new_with_keys(key1: u128, key2: u128) -> AHasher { 36 let pi: [u128; 2] = PI.convert(); 37 let key1: [u64; 2] = (key1 ^ pi[0]).convert(); 38 let key2: [u64; 2] = (key2 ^ pi[1]).convert(); 39 AHasher { 40 buffer: key1[0], 41 pad: key1[1], 42 extra_keys: key2, 43 } 44 } 45 46 #[inline] 47 #[allow(dead_code)] // Is not called if non-fallback hash is used. from_random_state(rand_state: &RandomState) -> AHasher48 pub(crate) fn from_random_state(rand_state: &RandomState) -> AHasher { 49 AHasher { 50 buffer: rand_state.k0, 51 pad: rand_state.k1, 52 extra_keys: [rand_state.k2, rand_state.k3], 53 } 54 } 55 56 /// This update function has the goal of updating the buffer with a single multiply 57 /// FxHash does this but is vulnerable to attack. To avoid this input needs to be masked to with an 58 /// unpredictable value. Other hashes such as murmurhash have taken this approach but were found vulnerable 59 /// to attack. The attack was based on the idea of reversing the pre-mixing (Which is necessarily 60 /// reversible otherwise bits would be lost) then placing a difference in the highest bit before the 61 /// multiply used to mix the data. Because a multiply can never affect the bits to the right of it, a 62 /// subsequent update that also differed in this bit could result in a predictable collision. 63 /// 64 /// This version avoids this vulnerability while still only using a single multiply. It takes advantage 65 /// of the fact that when a 64 bit multiply is performed the upper 64 bits are usually computed and thrown 66 /// away. Instead it creates two 128 bit values where the upper 64 bits are zeros and multiplies them. 67 /// (The compiler is smart enough to turn this into a 64 bit multiplication in the assembly) 68 /// Then the upper bits are xored with the lower bits to produce a single 64 bit result. 69 /// 70 /// To understand why this is a good scrambling function it helps to understand multiply-with-carry PRNGs: 71 /// https://en.wikipedia.org/wiki/Multiply-with-carry_pseudorandom_number_generator 72 /// If the multiple is chosen well, this creates a long period, decent quality PRNG. 73 /// Notice that this function is equivalent to this except the `buffer`/`state` is being xored with each 74 /// new block of data. In the event that data is all zeros, it is exactly equivalent to a MWC PRNG. 75 /// 76 /// This is impervious to attack because every bit buffer at the end is dependent on every bit in 77 /// `new_data ^ buffer`. For example suppose two inputs differed in only the 5th bit. Then when the 78 /// multiplication is performed the `result` will differ in bits 5-69. More specifically it will differ by 79 /// 2^5 * MULTIPLE. However in the next step bits 65-128 are turned into a separate 64 bit value. So the 80 /// differing bits will be in the lower 6 bits of this value. The two intermediate values that differ in 81 /// bits 5-63 and in bits 0-5 respectively get added together. Producing an output that differs in every 82 /// bit. The addition carries in the multiplication and at the end additionally mean that the even if an 83 /// attacker somehow knew part of (but not all) the contents of the buffer before hand, 84 /// they would not be able to predict any of the bits in the buffer at the end. 85 #[inline(always)] update(&mut self, new_data: u64)86 fn update(&mut self, new_data: u64) { 87 self.buffer = folded_multiply(new_data ^ self.buffer, MULTIPLE); 88 } 89 90 /// Similar to the above this function performs an update using a "folded multiply". 91 /// However it takes in 128 bits of data instead of 64. Both halves must be masked. 92 /// 93 /// This makes it impossible for an attacker to place a single bit difference between 94 /// two blocks so as to cancel each other. 95 /// 96 /// However this is not sufficient. to prevent (a,b) from hashing the same as (b,a) the buffer itself must 97 /// be updated between calls in a way that does not commute. To achieve this XOR and Rotate are used. 98 /// Add followed by xor is not the same as xor followed by add, and rotate ensures that the same out bits 99 /// can't be changed by the same set of input bits. To cancel this sequence with subsequent input would require 100 /// knowing the keys. 101 #[inline(always)] large_update(&mut self, new_data: u128)102 fn large_update(&mut self, new_data: u128) { 103 let block: [u64; 2] = new_data.convert(); 104 let combined = folded_multiply(block[0] ^ self.extra_keys[0], block[1] ^ self.extra_keys[1]); 105 self.buffer = (combined.wrapping_add(self.buffer) ^ self.pad).rotate_left(ROT); 106 } 107 } 108 109 #[cfg(feature = "specialize")] 110 impl HasherExt for AHasher { 111 #[inline] hash_u64(self, value: u64) -> u64112 fn hash_u64(self, value: u64) -> u64 { 113 let rot = (self.pad & 64) as u32; 114 folded_multiply(value ^ self.buffer, MULTIPLE).rotate_left(rot) 115 } 116 117 #[inline] short_finish(&self) -> u64118 fn short_finish(&self) -> u64 { 119 self.buffer.wrapping_add(self.pad) 120 } 121 } 122 123 /// Provides [Hasher] methods to hash all of the primitive types. 124 /// 125 /// [Hasher]: core::hash::Hasher 126 impl Hasher for AHasher { 127 #[inline] write_u8(&mut self, i: u8)128 fn write_u8(&mut self, i: u8) { 129 self.update(i as u64); 130 } 131 132 #[inline] write_u16(&mut self, i: u16)133 fn write_u16(&mut self, i: u16) { 134 self.update(i as u64); 135 } 136 137 #[inline] write_u32(&mut self, i: u32)138 fn write_u32(&mut self, i: u32) { 139 self.update(i as u64); 140 } 141 142 #[inline] write_u64(&mut self, i: u64)143 fn write_u64(&mut self, i: u64) { 144 self.update(i as u64); 145 } 146 147 #[inline] write_u128(&mut self, i: u128)148 fn write_u128(&mut self, i: u128) { 149 self.large_update(i); 150 } 151 152 #[inline] write_usize(&mut self, i: usize)153 fn write_usize(&mut self, i: usize) { 154 self.write_u64(i as u64); 155 } 156 157 #[inline] 158 #[allow(clippy::collapsible_if)] write(&mut self, input: &[u8])159 fn write(&mut self, input: &[u8]) { 160 let mut data = input; 161 let length = data.len() as u64; 162 //Needs to be an add rather than an xor because otherwise it could be canceled with carefully formed input. 163 self.buffer = self.buffer.wrapping_add(length).wrapping_mul(MULTIPLE); 164 //A 'binary search' on sizes reduces the number of comparisons. 165 if data.len() > 8 { 166 if data.len() > 16 { 167 let tail = data.read_last_u128(); 168 self.large_update(tail); 169 while data.len() > 16 { 170 let (block, rest) = data.read_u128(); 171 self.large_update(block); 172 data = rest; 173 } 174 } else { 175 self.large_update([data.read_u64().0, data.read_last_u64()].convert()); 176 } 177 } else { 178 if data.len() >= 2 { 179 if data.len() >= 4 { 180 let block = [data.read_u32().0 as u64, data.read_last_u32() as u64]; 181 self.large_update(block.convert()); 182 } else { 183 let value = [data.read_u16().0 as u32, data[data.len() - 1] as u32]; 184 self.update(value.convert()); 185 } 186 } else { 187 if data.len() > 0 { 188 self.update(data[0] as u64); 189 } 190 } 191 } 192 } 193 #[inline] finish(&self) -> u64194 fn finish(&self) -> u64 { 195 let rot = (self.buffer & 63) as u32; 196 folded_multiply(self.buffer, self.pad).rotate_left(rot) 197 } 198 } 199 200 #[cfg(test)] 201 mod tests { 202 use crate::convert::Convert; 203 use crate::fallback_hash::*; 204 205 #[test] test_hash()206 fn test_hash() { 207 let mut hasher = AHasher::new_with_keys(0, 0); 208 let value: u64 = 1 << 32; 209 hasher.update(value); 210 let result = hasher.buffer; 211 let mut hasher = AHasher::new_with_keys(0, 0); 212 let value2: u64 = 1; 213 hasher.update(value2); 214 let result2 = hasher.buffer; 215 let result: [u8; 8] = result.convert(); 216 let result2: [u8; 8] = result2.convert(); 217 assert_ne!(hex::encode(result), hex::encode(result2)); 218 } 219 220 #[test] test_conversion()221 fn test_conversion() { 222 let input: &[u8] = "dddddddd".as_bytes(); 223 let bytes: u64 = as_array!(input, 8).convert(); 224 assert_eq!(bytes, 0x6464646464646464); 225 } 226 } 227