1 use crate::convert::*; 2 use crate::operations::*; 3 #[cfg(feature = "specialize")] 4 use crate::HasherExt; 5 use core::hash::Hasher; 6 use crate::RandomState; 7 8 /// A `Hasher` for hashing an arbitrary stream of bytes. 9 /// 10 /// Instances of [`AHasher`] represent state that is updated while hashing data. 11 /// 12 /// Each method updates the internal state based on the new data provided. Once 13 /// all of the data has been provided, the resulting hash can be obtained by calling 14 /// `finish()` 15 /// 16 /// [Clone] is also provided in case you wish to calculate hashes for two different items that 17 /// start with the same data. 18 /// 19 #[derive(Debug, Clone)] 20 pub struct AHasher { 21 enc: u128, 22 sum: u128, 23 key: u128, 24 } 25 26 impl AHasher { 27 /// Creates a new hasher keyed to the provided keys. 28 /// 29 /// Normally hashers are created via `AHasher::default()` for fixed keys or `RandomState::new()` for randomly 30 /// generated keys and `RandomState::with_seeds(a,b)` for seeds that are set and can be reused. All of these work at 31 /// map creation time (and hence don't have any overhead on a per-item bais). 32 /// 33 /// This method directly creates the hasher instance and performs no transformation on the provided seeds. This may 34 /// be useful where a HashBuilder is not desired, such as for testing purposes. 35 /// 36 /// # Example 37 /// 38 /// ``` 39 /// use std::hash::Hasher; 40 /// use ahash::AHasher; 41 /// 42 /// let mut hasher = AHasher::new_with_keys(1234, 5678); 43 /// 44 /// hasher.write_u32(1989); 45 /// hasher.write_u8(11); 46 /// hasher.write_u8(9); 47 /// hasher.write(b"Huh?"); 48 /// 49 /// println!("Hash is {:x}!", hasher.finish()); 50 /// ``` 51 #[inline] new_with_keys(key1: u128, key2: u128) -> Self52 pub fn new_with_keys(key1: u128, key2: u128) -> Self { 53 Self { 54 enc: key1, 55 sum: key2, 56 key: key1 ^ key2, 57 } 58 } 59 60 #[inline] from_random_state(rand_state: &RandomState) -> Self61 pub(crate) fn from_random_state(rand_state: &RandomState) -> Self { 62 let key1 = [rand_state.k0, rand_state.k1].convert(); 63 let key2 = [rand_state.k2, rand_state.k3].convert(); 64 Self { 65 enc: key1, 66 sum: key2, 67 key: key1 ^ key2, 68 } 69 } 70 71 #[inline(always)] add_in_length(&mut self, length: u64)72 fn add_in_length(&mut self, length: u64) { 73 //This will be scrambled by the next AES round. 74 let mut enc: [u64; 2] = self.enc.convert(); 75 enc[0] = enc[0].wrapping_add(length); 76 self.enc = enc.convert(); 77 } 78 79 #[inline(always)] hash_in(&mut self, new_value: u128)80 fn hash_in(&mut self, new_value: u128) { 81 self.enc = aesenc(self.enc, new_value); 82 self.sum = shuffle_and_add(self.sum, new_value); 83 } 84 85 #[inline(always)] hash_in_2(&mut self, v1: u128, v2: u128)86 fn hash_in_2(&mut self, v1: u128, v2: u128) { 87 self.enc = aesenc(self.enc, v1); 88 self.sum = shuffle_and_add(self.sum, v1); 89 self.enc = aesenc(self.enc, v2); 90 self.sum = shuffle_and_add(self.sum, v2); 91 } 92 } 93 94 #[cfg(feature = "specialize")] 95 impl HasherExt for AHasher { 96 #[inline] hash_u64(self, value: u64) -> u6497 fn hash_u64(self, value: u64) -> u64 { 98 let mask = self.sum as u64; 99 let rot = (self.enc & 64) as u32; 100 folded_multiply(value ^ mask, crate::fallback_hash::MULTIPLE).rotate_left(rot) 101 } 102 103 #[inline] short_finish(&self) -> u64104 fn short_finish(&self) -> u64 { 105 let combined = aesdec(self.sum, self.enc); 106 let result: [u64; 2] = aesenc(combined, combined).convert(); 107 result[0] 108 } 109 } 110 111 /// Provides [Hasher] methods to hash all of the primitive types. 112 /// 113 /// [Hasher]: core::hash::Hasher 114 impl Hasher for AHasher { 115 #[inline] write_u8(&mut self, i: u8)116 fn write_u8(&mut self, i: u8) { 117 self.write_u64(i as u64); 118 } 119 120 #[inline] write_u16(&mut self, i: u16)121 fn write_u16(&mut self, i: u16) { 122 self.write_u64(i as u64); 123 } 124 125 #[inline] write_u32(&mut self, i: u32)126 fn write_u32(&mut self, i: u32) { 127 self.write_u64(i as u64); 128 } 129 130 #[inline] write_u128(&mut self, i: u128)131 fn write_u128(&mut self, i: u128) { 132 self.hash_in(i); 133 } 134 135 #[inline] write_usize(&mut self, i: usize)136 fn write_usize(&mut self, i: usize) { 137 self.write_u64(i as u64); 138 } 139 140 #[inline] write_u64(&mut self, i: u64)141 fn write_u64(&mut self, i: u64) { 142 self.write_u128(i as u128); 143 } 144 145 #[inline] 146 #[allow(clippy::collapsible_if)] write(&mut self, input: &[u8])147 fn write(&mut self, input: &[u8]) { 148 let mut data = input; 149 let length = data.len(); 150 self.add_in_length(length as u64); 151 //A 'binary search' on sizes reduces the number of comparisons. 152 if data.len() < 8 { 153 let value: [u64; 2] = if data.len() >= 2 { 154 if data.len() >= 4 { 155 //len 4-8 156 [data.read_u32().0 as u64, data.read_last_u32() as u64] 157 } else { 158 //len 2-3 159 [data.read_u16().0 as u64, data[data.len() - 1] as u64] 160 } 161 } else { 162 if data.len() > 0 { 163 [data[0] as u64, 0] 164 } else { 165 [0, 0] 166 } 167 }; 168 self.hash_in(value.convert()); 169 } else { 170 if data.len() > 32 { 171 if data.len() > 64 { 172 let tail = data.read_last_u128x4(); 173 let mut current: [u128; 4] = [self.key; 4]; 174 current[0] = aesenc(current[0], tail[0]); 175 current[1] = aesenc(current[1], tail[1]); 176 current[2] = aesenc(current[2], tail[2]); 177 current[3] = aesenc(current[3], tail[3]); 178 let mut sum: [u128; 2] = [self.key, self.key]; 179 sum[0] = add_by_64s(sum[0].convert(), tail[0].convert()).convert(); 180 sum[1] = add_by_64s(sum[1].convert(), tail[1].convert()).convert(); 181 sum[0] = shuffle_and_add(sum[0], tail[2]); 182 sum[1] = shuffle_and_add(sum[1], tail[3]); 183 while data.len() > 64 { 184 let (blocks, rest) = data.read_u128x4(); 185 current[0] = aesenc(current[0], blocks[0]); 186 current[1] = aesenc(current[1], blocks[1]); 187 current[2] = aesenc(current[2], blocks[2]); 188 current[3] = aesenc(current[3], blocks[3]); 189 sum[0] = shuffle_and_add(sum[0], blocks[0]); 190 sum[1] = shuffle_and_add(sum[1], blocks[1]); 191 sum[0] = shuffle_and_add(sum[0], blocks[2]); 192 sum[1] = shuffle_and_add(sum[1], blocks[3]); 193 data = rest; 194 } 195 self.hash_in_2(aesenc(current[0], current[1]), aesenc(current[2], current[3])); 196 self.hash_in(add_by_64s(sum[0].convert(), sum[1].convert()).convert()); 197 } else { 198 //len 33-64 199 let (head, _) = data.read_u128x2(); 200 let tail = data.read_last_u128x2(); 201 self.hash_in_2(head[0], head[1]); 202 self.hash_in_2(tail[0], tail[1]); 203 } 204 } else { 205 if data.len() > 16 { 206 //len 17-32 207 self.hash_in_2(data.read_u128().0, data.read_last_u128()); 208 } else { 209 //len 9-16 210 let value: [u64; 2] = [data.read_u64().0, data.read_last_u64()]; 211 self.hash_in(value.convert()); 212 } 213 } 214 } 215 } 216 #[inline] finish(&self) -> u64217 fn finish(&self) -> u64 { 218 let combined = aesdec(self.sum, self.enc); 219 let result: [u64; 2] = aesenc(aesenc(combined, self.key), combined).convert(); 220 result[0] 221 } 222 } 223 224 #[cfg(test)] 225 mod tests { 226 use super::*; 227 use crate::convert::Convert; 228 use crate::operations::aesenc; 229 use crate::RandomState; 230 use std::hash::{BuildHasher, Hasher}; 231 #[test] test_sanity()232 fn test_sanity() { 233 let mut hasher = RandomState::with_seeds(1, 2, 3,4).build_hasher(); 234 hasher.write_u64(0); 235 let h1 = hasher.finish(); 236 hasher.write(&[1, 0, 0, 0, 0, 0, 0, 0]); 237 let h2 = hasher.finish(); 238 assert_ne!(h1, h2); 239 } 240 241 #[cfg(feature = "compile-time-rng")] 242 #[test] test_builder()243 fn test_builder() { 244 use std::collections::HashMap; 245 use std::hash::BuildHasherDefault; 246 247 let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default(); 248 map.insert(1, 3); 249 } 250 251 #[cfg(feature = "compile-time-rng")] 252 #[test] test_default()253 fn test_default() { 254 let hasher_a = AHasher::default(); 255 let a_enc: [u64; 2] = hasher_a.enc.convert(); 256 let a_sum: [u64; 2] = hasher_a.sum.convert(); 257 assert_ne!(0, a_enc[0]); 258 assert_ne!(0, a_enc[1]); 259 assert_ne!(0, a_sum[0]); 260 assert_ne!(0, a_sum[1]); 261 assert_ne!(a_enc[0], a_enc[1]); 262 assert_ne!(a_sum[0], a_sum[1]); 263 assert_ne!(a_enc[0], a_sum[0]); 264 assert_ne!(a_enc[1], a_sum[1]); 265 let hasher_b = AHasher::default(); 266 let b_enc: [u64; 2] = hasher_b.enc.convert(); 267 let b_sum: [u64; 2] = hasher_b.sum.convert(); 268 assert_eq!(a_enc[0], b_enc[0]); 269 assert_eq!(a_enc[1], b_enc[1]); 270 assert_eq!(a_sum[0], b_sum[0]); 271 assert_eq!(a_sum[1], b_sum[1]); 272 } 273 274 #[test] test_hash()275 fn test_hash() { 276 let mut result: [u64; 2] = [0x6c62272e07bb0142, 0x62b821756295c58d]; 277 let value: [u64; 2] = [1 << 32, 0xFEDCBA9876543210]; 278 result = aesenc(value.convert(), result.convert()).convert(); 279 result = aesenc(result.convert(), result.convert()).convert(); 280 let mut result2: [u64; 2] = [0x6c62272e07bb0142, 0x62b821756295c58d]; 281 let value2: [u64; 2] = [1, 0xFEDCBA9876543210]; 282 result2 = aesenc(value2.convert(), result2.convert()).convert(); 283 result2 = aesenc(result2.convert(), result.convert()).convert(); 284 let result: [u8; 16] = result.convert(); 285 let result2: [u8; 16] = result2.convert(); 286 assert_ne!(hex::encode(result), hex::encode(result2)); 287 } 288 289 #[test] test_conversion()290 fn test_conversion() { 291 let input: &[u8] = "dddddddd".as_bytes(); 292 let bytes: u64 = as_array!(input, 8).convert(); 293 assert_eq!(bytes, 0x6464646464646464); 294 } 295 } 296