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