vendor/ahash-0.7.6/src/aes_hash.rs

   1 use crate::convert::*;
   2 #[cfg(feature = "specialize")]
   3 use crate::fallback_hash::MULTIPLE;
   4 use crate::operations::*;
   5 use crate::RandomState;
   6 use core::hash::Hasher;
   7 use crate::random_state::PI;
   8
   9 /// A `Hasher` for hashing an arbitrary stream of bytes.
  10 ///
  11 /// Instances of [`AHasher`] represent state that is updated while hashing data.
  12 ///
  13 /// Each method updates the internal state based on the new data provided. Once
  14 /// all of the data has been provided, the resulting hash can be obtained by calling
  15 /// `finish()`
  16 ///
  17 /// [Clone] is also provided in case you wish to calculate hashes for two different items that
  18 /// start with the same data.
  19 ///
  20 #[derive(Debug, Clone)]
  21 pub struct AHasher {
  22     enc: u128,
  23     sum: u128,
  24     key: u128,
  25 }
  26
  27 impl AHasher {
  28     /// Creates a new hasher keyed to the provided keys.
  29     ///
  30     /// Normally hashers are created via `AHasher::default()` for fixed keys or `RandomState::new()` for randomly
  31     /// generated keys and `RandomState::with_seeds(a,b)` for seeds that are set and can be reused. All of these work at
  32     /// map creation time (and hence don't have any overhead on a per-item bais).
  33     ///
  34     /// This method directly creates the hasher instance and performs no transformation on the provided seeds. This may
  35     /// be useful where a HashBuilder is not desired, such as for testing purposes.
  36     ///
  37     /// # Example
  38     ///
  39     /// ```
  40     /// use std::hash::Hasher;
  41     /// use ahash::AHasher;
  42     ///
  43     /// let mut hasher = AHasher::new_with_keys(1234, 5678);
  44     ///
  45     /// hasher.write_u32(1989);
  46     /// hasher.write_u8(11);
  47     /// hasher.write_u8(9);
  48     /// hasher.write(b"Huh?");
  49     ///
  50     /// println!("Hash is {:x}!", hasher.finish());
  51     /// ```
  52     #[inline]
  53     pub fn new_with_keys(key1: u128, key2: u128) -> Self {
  54         let pi: [u128; 2] = PI.convert();
  55         let key1 = key1 ^ pi[0];
  56         let key2 = key2 ^ pi[1];
  57         Self {
  58             enc: key1,
  59             sum: key2,
  60             key: key1 ^ key2,
  61         }
  62     }
  63
  64     #[allow(unused)] // False positive
  65     pub(crate) fn test_with_keys(key1: u128, key2: u128) -> Self {
  66         Self {
  67             enc: key1,
  68             sum: key2,
  69             key: key1 ^ key2,
  70         }
  71     }
  72
  73
  74     #[inline]
  75     pub(crate) fn from_random_state(rand_state: &RandomState) -> Self {
  76         let key1 = [rand_state.k0, rand_state.k1].convert();
  77         let key2 = [rand_state.k2, rand_state.k3].convert();
  78         Self {
  79             enc: key1,
  80             sum: key2,
  81             key: key1 ^ key2,
  82         }
  83     }
  84
  85     #[inline(always)]
  86     fn add_in_length(&mut self, length: u64) {
  87         //This will be scrambled by the next AES round.
  88         let mut enc: [u64; 2] = self.enc.convert();
  89         enc[0] = enc[0].wrapping_add(length);
  90         self.enc = enc.convert();
  91     }
  92
  93     #[inline(always)]
  94     fn hash_in(&mut self, new_value: u128) {
  95         self.enc = aesenc(self.enc, new_value);
  96         self.sum = shuffle_and_add(self.sum, new_value);
  97     }
  98
  99     #[inline(always)]
 100     fn hash_in_2(&mut self, v1: u128, v2: u128) {
 101         self.enc = aesenc(self.enc, v1);
 102         self.sum = shuffle_and_add(self.sum, v1);
 103         self.enc = aesenc(self.enc, v2);
 104         self.sum = shuffle_and_add(self.sum, v2);
 105     }
 106
 107     #[inline]
 108     #[cfg(feature = "specialize")]
 109     fn short_finish(&self) -> u64 {
 110         let combined = aesdec(self.sum, self.enc);
 111         let result: [u64; 2] = aesenc(combined, combined).convert();
 112         result[0]
 113     }
 114 }
 115
 116 /// Provides [Hasher] methods to hash all of the primitive types.
 117 ///
 118 /// [Hasher]: core::hash::Hasher
 119 impl Hasher for AHasher {
 120     #[inline]
 121     fn write_u8(&mut self, i: u8) {
 122         self.write_u64(i as u64);
 123     }
 124
 125     #[inline]
 126     fn write_u16(&mut self, i: u16) {
 127         self.write_u64(i as u64);
 128     }
 129
 130     #[inline]
 131     fn write_u32(&mut self, i: u32) {
 132         self.write_u64(i as u64);
 133     }
 134
 135     #[inline]
 136     fn write_u128(&mut self, i: u128) {
 137         self.hash_in(i);
 138     }
 139
 140     #[inline]
 141     #[cfg(any(target_pointer_width = "64", target_pointer_width = "32", target_pointer_width = "16"))]
 142     fn write_usize(&mut self, i: usize) {
 143         self.write_u64(i as u64);
 144     }
 145
 146     #[inline]
 147     #[cfg(target_pointer_width = "128")]
 148     fn write_usize(&mut self, i: usize) {
 149         self.write_u128(i as u128);
 150     }
 151
 152     #[inline]
 153     fn write_u64(&mut self, i: u64) {
 154         self.write_u128(i as u128);
 155     }
 156
 157     #[inline]
 158     #[allow(clippy::collapsible_if)]
 159     fn write(&mut self, input: &[u8]) {
 160         let mut data = input;
 161         let length = data.len();
 162         self.add_in_length(length as u64);
 163         //A 'binary search' on sizes reduces the number of comparisons.
 164         if data.len() <= 8 {
 165             let value = read_small(data);
 166             self.hash_in(value.convert());
 167         } else {
 168             if data.len() > 32 {
 169                 if data.len() > 64 {
 170                     let tail = data.read_last_u128x4();
 171                     let mut current: [u128; 4] = [self.key; 4];
 172                     current[0] = aesenc(current[0], tail[0]);
 173                     current[1] = aesenc(current[1], tail[1]);
 174                     current[2] = aesenc(current[2], tail[2]);
 175                     current[3] = aesenc(current[3], tail[3]);
 176                     let mut sum: [u128; 2] = [self.key, self.key];
 177                     sum[0] = add_by_64s(sum[0].convert(), tail[0].convert()).convert();
 178                     sum[1] = add_by_64s(sum[1].convert(), tail[1].convert()).convert();
 179                     sum[0] = shuffle_and_add(sum[0], tail[2]);
 180                     sum[1] = shuffle_and_add(sum[1], tail[3]);
 181                     while data.len() > 64 {
 182                         let (blocks, rest) = data.read_u128x4();
 183                         current[0] = aesenc(current[0], blocks[0]);
 184                         current[1] = aesenc(current[1], blocks[1]);
 185                         current[2] = aesenc(current[2], blocks[2]);
 186                         current[3] = aesenc(current[3], blocks[3]);
 187                         sum[0] = shuffle_and_add(sum[0], blocks[0]);
 188                         sum[1] = shuffle_and_add(sum[1], blocks[1]);
 189                         sum[0] = shuffle_and_add(sum[0], blocks[2]);
 190                         sum[1] = shuffle_and_add(sum[1], blocks[3]);
 191                         data = rest;
 192                     }
 193                     self.hash_in_2(aesenc(current[0], current[1]), aesenc(current[2], current[3]));
 194                     self.hash_in(add_by_64s(sum[0].convert(), sum[1].convert()).convert());
 195                 } else {
 196                     //len 33-64
 197                     let (head, _) = data.read_u128x2();
 198                     let tail = data.read_last_u128x2();
 199                     self.hash_in_2(head[0], head[1]);
 200                     self.hash_in_2(tail[0], tail[1]);
 201                 }
 202             } else {
 203                 if data.len() > 16 {
 204                     //len 17-32
 205                     self.hash_in_2(data.read_u128().0, data.read_last_u128());
 206                 } else {
 207                     //len 9-16
 208                     let value: [u64; 2] = [data.read_u64().0, data.read_last_u64()];
 209                     self.hash_in(value.convert());
 210                 }
 211             }
 212         }
 213     }
 214     #[inline]
 215     fn finish(&self) -> u64 {
 216         let combined = aesdec(self.sum, self.enc);
 217         let result: [u64; 2] = aesenc(aesenc(combined, self.key), combined).convert();
 218         result[0]
 219     }
 220 }
 221
 222 #[cfg(feature = "specialize")]
 223 pub(crate) struct AHasherU64 {
 224     pub(crate) buffer: u64,
 225     pub(crate) pad: u64,
 226 }
 227
 228 /// A specialized hasher for only primitives under 64 bits.
 229 #[cfg(feature = "specialize")]
 230 impl Hasher for AHasherU64 {
 231     #[inline]
 232     fn finish(&self) -> u64 {
 233         let rot = (self.pad & 63) as u32;
 234         self.buffer.rotate_left(rot)
 235     }
 236
 237     #[inline]
 238     fn write(&mut self, _bytes: &[u8]) {
 239         unreachable!("Specialized hasher was called with a different type of object")
 240     }
 241
 242     #[inline]
 243     fn write_u8(&mut self, i: u8) {
 244         self.write_u64(i as u64);
 245     }
 246
 247     #[inline]
 248     fn write_u16(&mut self, i: u16) {
 249         self.write_u64(i as u64);
 250     }
 251
 252     #[inline]
 253     fn write_u32(&mut self, i: u32) {
 254         self.write_u64(i as u64);
 255     }
 256
 257     #[inline]
 258     fn write_u64(&mut self, i: u64) {
 259         self.buffer = folded_multiply(i ^ self.buffer, MULTIPLE);
 260     }
 261
 262     #[inline]
 263     fn write_u128(&mut self, _i: u128) {
 264         unreachable!("Specialized hasher was called with a different type of object")
 265     }
 266
 267     #[inline]
 268     fn write_usize(&mut self, _i: usize) {
 269         unreachable!("Specialized hasher was called with a different type of object")
 270     }
 271 }
 272
 273 #[cfg(feature = "specialize")]
 274 pub(crate) struct AHasherFixed(pub AHasher);
 275
 276 /// A specialized hasher for fixed size primitives larger than 64 bits.
 277 #[cfg(feature = "specialize")]
 278 impl Hasher for AHasherFixed {
 279     #[inline]
 280     fn finish(&self) -> u64 {
 281         self.0.short_finish()
 282     }
 283
 284     #[inline]
 285     fn write(&mut self, bytes: &[u8]) {
 286         self.0.write(bytes)
 287     }
 288
 289     #[inline]
 290     fn write_u8(&mut self, i: u8) {
 291         self.write_u64(i as u64);
 292     }
 293
 294     #[inline]
 295     fn write_u16(&mut self, i: u16) {
 296         self.write_u64(i as u64);
 297     }
 298
 299     #[inline]
 300     fn write_u32(&mut self, i: u32) {
 301         self.write_u64(i as u64);
 302     }
 303
 304     #[inline]
 305     fn write_u64(&mut self, i: u64) {
 306         self.0.write_u64(i);
 307     }
 308
 309     #[inline]
 310     fn write_u128(&mut self, i: u128) {
 311         self.0.write_u128(i);
 312     }
 313
 314     #[inline]
 315     fn write_usize(&mut self, i: usize) {
 316         self.0.write_usize(i);
 317     }
 318 }
 319
 320 #[cfg(feature = "specialize")]
 321 pub(crate) struct AHasherStr(pub AHasher);
 322
 323 /// A specialized hasher for strings
 324 /// Note that the other types don't panic because the hash impl for String tacks on an unneeded call. (As does vec)
 325 #[cfg(feature = "specialize")]
 326 impl Hasher for AHasherStr {
 327     #[inline]
 328     fn finish(&self) -> u64 {
 329         let result : [u64; 2] = self.0.enc.convert();
 330         result[0]
 331     }
 332
 333     #[inline]
 334     fn write(&mut self, bytes: &[u8]) {
 335         if bytes.len() > 8 {
 336             self.0.write(bytes);
 337             self.0.enc = aesdec(self.0.sum, self.0.enc);
 338             self.0.enc = aesenc(aesenc(self.0.enc, self.0.key), self.0.enc);
 339         } else {
 340             self.0.add_in_length(bytes.len() as u64);
 341             let value = read_small(bytes).convert();
 342             self.0.sum = shuffle_and_add(self.0.sum, value);
 343             self.0.enc = aesdec(self.0.sum, self.0.enc);
 344             self.0.enc = aesenc(aesenc(self.0.enc, self.0.key), self.0.enc);
 345         }
 346     }
 347
 348     #[inline]
 349     fn write_u8(&mut self, _i: u8) {}
 350
 351     #[inline]
 352     fn write_u16(&mut self, _i: u16) {}
 353
 354     #[inline]
 355     fn write_u32(&mut self, _i: u32) {}
 356
 357     #[inline]
 358     fn write_u64(&mut self, _i: u64) {}
 359
 360     #[inline]
 361     fn write_u128(&mut self, _i: u128) {}
 362
 363     #[inline]
 364     fn write_usize(&mut self, _i: usize) {}
 365 }
 366
 367 #[cfg(test)]
 368 mod tests {
 369     use super::*;
 370     use crate::convert::Convert;
 371     use crate::operations::aesenc;
 372     use crate::RandomState;
 373     use std::hash::{BuildHasher, Hasher};
 374     #[test]
 375     fn test_sanity() {
 376         let mut hasher = RandomState::with_seeds(1, 2, 3, 4).build_hasher();
 377         hasher.write_u64(0);
 378         let h1 = hasher.finish();
 379         hasher.write(&[1, 0, 0, 0, 0, 0, 0, 0]);
 380         let h2 = hasher.finish();
 381         assert_ne!(h1, h2);
 382     }
 383
 384     #[cfg(feature = "compile-time-rng")]
 385     #[test]
 386     fn test_builder() {
 387         use std::collections::HashMap;
 388         use std::hash::BuildHasherDefault;
 389
 390         let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default();
 391         map.insert(1, 3);
 392     }
 393
 394     #[cfg(feature = "compile-time-rng")]
 395     #[test]
 396     fn test_default() {
 397         let hasher_a = AHasher::default();
 398         let a_enc: [u64; 2] = hasher_a.enc.convert();
 399         let a_sum: [u64; 2] = hasher_a.sum.convert();
 400         assert_ne!(0, a_enc[0]);
 401         assert_ne!(0, a_enc[1]);
 402         assert_ne!(0, a_sum[0]);
 403         assert_ne!(0, a_sum[1]);
 404         assert_ne!(a_enc[0], a_enc[1]);
 405         assert_ne!(a_sum[0], a_sum[1]);
 406         assert_ne!(a_enc[0], a_sum[0]);
 407         assert_ne!(a_enc[1], a_sum[1]);
 408         let hasher_b = AHasher::default();
 409         let b_enc: [u64; 2] = hasher_b.enc.convert();
 410         let b_sum: [u64; 2] = hasher_b.sum.convert();
 411         assert_eq!(a_enc[0], b_enc[0]);
 412         assert_eq!(a_enc[1], b_enc[1]);
 413         assert_eq!(a_sum[0], b_sum[0]);
 414         assert_eq!(a_sum[1], b_sum[1]);
 415     }
 416
 417     #[test]
 418     fn test_hash() {
 419         let mut result: [u64; 2] = [0x6c62272e07bb0142, 0x62b821756295c58d];
 420         let value: [u64; 2] = [1 << 32, 0xFEDCBA9876543210];
 421         result = aesenc(value.convert(), result.convert()).convert();
 422         result = aesenc(result.convert(), result.convert()).convert();
 423         let mut result2: [u64; 2] = [0x6c62272e07bb0142, 0x62b821756295c58d];
 424         let value2: [u64; 2] = [1, 0xFEDCBA9876543210];
 425         result2 = aesenc(value2.convert(), result2.convert()).convert();
 426         result2 = aesenc(result2.convert(), result.convert()).convert();
 427         let result: [u8; 16] = result.convert();
 428         let result2: [u8; 16] = result2.convert();
 429         assert_ne!(hex::encode(result), hex::encode(result2));
 430     }
 431
 432     #[test]
 433     fn test_conversion() {
 434         let input: &[u8] = "dddddddd".as_bytes();
 435         let bytes: u64 = as_array!(input, 8).convert();
 436         assert_eq!(bytes, 0x6464646464646464);
 437     }
 438 }
 439