1 //! # aHash
2 //!
3 //! This hashing algorithm is intended to be a high performance, (hardware specific), keyed hash function.
4 //! This can be seen as a DOS resistant alternative to `FxHash`, or a fast equivalent to `SipHash`.
5 //! It provides a high speed hash algorithm, but where the result is not predictable without knowing a Key.
6 //! This allows it to be used in a `HashMap` without allowing for the possibility that an malicious user can
7 //! induce a collision.
8 //!
9 //! # How aHash works
10 //!
11 //! aHash uses the hardware AES instruction on x86 processors to provide a keyed hash function.
12 //! It uses two rounds of AES per hash. So it should not be considered cryptographically secure.
13 #![deny(clippy::correctness, clippy::complexity, clippy::perf)]
14 #![allow(clippy::pedantic, clippy::cast_lossless, clippy::unreadable_literal)]
15
16 #![cfg_attr(all(not(test), not(feature = "std")), no_std)]
17
18 #[macro_use]
19 mod convert;
20
21 #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes"))]
22 mod aes_hash;
23 mod fallback_hash;
24 #[cfg(test)]
25 mod hash_quality_test;
26
27 #[cfg(feature = "std")]
28 mod hash_map;
29 #[cfg(feature = "std")]
30 mod hash_set;
31
32 #[cfg(feature = "compile-time-rng")]
33 use const_random::const_random;
34
35 use core::hash::BuildHasher;
36 use core::sync::atomic::AtomicUsize;
37 use core::sync::atomic::Ordering;
38
39 #[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes"))]
40 pub use crate::aes_hash::AHasher;
41
42 #[cfg(not(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes")))]
43 pub use crate::fallback_hash::AHasher;
44
45 #[cfg(feature = "std")]
46 pub use crate::hash_map::AHashMap;
47 #[cfg(feature = "std")]
48 pub use crate::hash_set::AHashSet;
49
50 ///This constant come from Kunth's prng
51 const MULTIPLE: u64 = 6364136223846793005;
52
53 // Const random provides randomized starting key with no runtime cost.
54 #[cfg(feature = "compile-time-rng")]
55 static SEED: AtomicUsize = AtomicUsize::new(const_random!(u64));
56
57 #[cfg(not(feature = "compile-time-rng"))]
58 static SEED: AtomicUsize = AtomicUsize::new(MULTIPLE as usize);
59
60 /// Provides a default [Hasher] compile time generated constants for keys.
61 /// This is typically used in conjunction with [`BuildHasherDefault`] to create
62 /// [AHasher]s in order to hash the keys of the map.
63 ///
64 /// # Example
65 /// ```
66 /// use std::hash::BuildHasherDefault;
67 /// use ahash::{AHasher, ABuildHasher};
68 /// use std::collections::HashMap;
69 ///
70 /// let mut map: HashMap<i32, i32, ABuildHasher> = HashMap::default();
71 /// map.insert(12, 34);
72 /// ```
73 ///
74 /// [BuildHasherDefault]: std::hash::BuildHasherDefault
75 /// [Hasher]: std::hash::Hasher
76 /// [HashMap]: std::collections::HashMap
77 #[cfg(feature = "compile-time-rng")]
78 impl Default for AHasher {
79 /// Constructs a new [AHasher] with compile time generated constants for keys.
80 /// This means the keys will be the same from one instance to another,
81 /// but different from build to the next. So if it is possible for a potential
82 /// attacker to have access to the compiled binary it would be better
83 /// to specify keys generated at runtime.
84 ///
85 /// This is defined only if the `compile-time-rng` feature is enabled.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use ahash::AHasher;
91 /// use std::hash::Hasher;
92 ///
93 /// let mut hasher_1 = AHasher::default();
94 /// let mut hasher_2 = AHasher::default();
95 ///
96 /// hasher_1.write_u32(1234);
97 /// hasher_2.write_u32(1234);
98 ///
99 /// assert_eq!(hasher_1.finish(), hasher_2.finish());
100 /// ```
101 #[inline]
default() -> AHasher102 fn default() -> AHasher {
103 AHasher::new_with_keys(const_random!(u64), const_random!(u64))
104 }
105 }
106
107 /// Provides a [Hasher] factory. This is typically used (e.g. by [`HashMap`]) to create
108 /// [AHasher]s in order to hash the keys of the map. See `build_hasher` below.
109 ///
110 /// [build_hasher]: ahash::
111 /// [Hasher]: std::hash::Hasher
112 /// [BuildHasher]: std::hash::BuildHasher
113 /// [HashMap]: std::collections::HashMap
114 #[derive(Clone)]
115 pub struct ABuildHasher {
116 k0: u64,
117 k1: u64,
118 }
119
120 impl ABuildHasher {
121 #[inline]
new() -> ABuildHasher122 pub fn new() -> ABuildHasher {
123 //Using a self pointer. When running with ASLR this is a random value.
124 let previous = SEED.load(Ordering::Relaxed) as u64;
125 let stack_mem_loc = &previous as *const _ as u64;
126 //This is similar to the update function in the fallback.
127 //only one multiply is needed because memory locations are not under an attackers control.
128 let current_seed = previous.wrapping_mul(MULTIPLE).wrapping_add(stack_mem_loc).rotate_left(31);
129 SEED.store(current_seed as usize, Ordering::Relaxed);
130 ABuildHasher {
131 k0: &SEED as *const _ as u64,
132 k1: current_seed
133 }
134 }
135 }
136
137 impl Default for ABuildHasher {
138 #[inline]
default() -> Self139 fn default() -> Self {
140 Self::new()
141 }
142 }
143
144 impl BuildHasher for ABuildHasher {
145 type Hasher = AHasher;
146
147 /// Constructs a new [AHasher] with keys based on compile time generated constants** and the location
148 /// of the this object in memory. This means that two different [BuildHasher]s will will generate
149 /// [AHasher]s that will return different hashcodes, but [Hasher]s created from the same [BuildHasher]
150 /// will generate the same hashes for the same input data.
151 ///
152 /// ** - only if the `compile-time-rng` feature is enabled.
153 ///
154 /// # Examples
155 ///
156 /// ```
157 /// use ahash::{AHasher, ABuildHasher};
158 /// use std::hash::{Hasher, BuildHasher};
159 ///
160 /// let build_hasher = ABuildHasher::new();
161 /// let mut hasher_1 = build_hasher.build_hasher();
162 /// let mut hasher_2 = build_hasher.build_hasher();
163 ///
164 /// hasher_1.write_u32(1234);
165 /// hasher_2.write_u32(1234);
166 ///
167 /// assert_eq!(hasher_1.finish(), hasher_2.finish());
168 ///
169 /// let other_build_hasher = ABuildHasher::new();
170 /// let mut different_hasher = other_build_hasher.build_hasher();
171 /// different_hasher.write_u32(1234);
172 /// assert_ne!(different_hasher.finish(), hasher_1.finish());
173 /// ```
174 /// [Hasher]: std::hash::Hasher
175 /// [BuildHasher]: std::hash::BuildHasher
176 /// [HashMap]: std::collections::HashMap
177 #[inline]
build_hasher(&self) -> AHasher178 fn build_hasher(&self) -> AHasher {
179 let (k0, k1) = scramble_keys(self.k0, self.k1);
180 AHasher::new_with_keys(k0, k1)
181 }
182 }
183
scramble_keys(k0: u64, k1: u64) -> (u64, u64)184 pub(crate) fn scramble_keys(k0: u64, k1: u64) -> (u64, u64) {
185 //Scramble seeds (based on xoroshiro128+)
186 //This is intentionally not similar the hash algorithm
187 let result1 = k0.wrapping_add(k1);
188 let k1 = k1 ^ k0;
189 let k0 = k0.rotate_left(24) ^ k1 ^ (k1.wrapping_shl(16));
190 let result2 = k0.wrapping_add(k1.rotate_left(37));
191 (result2, result1)
192 }
193
194 #[cfg(test)]
195 mod test {
196 use crate::convert::Convert;
197 use crate::*;
198 use core::hash::BuildHasherDefault;
199 use std::collections::HashMap;
200
201 #[test]
test_default_builder()202 fn test_default_builder() {
203 let mut map = HashMap::<u32, u64, BuildHasherDefault<AHasher>>::default();
204 map.insert(1, 3);
205 }
206 #[test]
test_builder()207 fn test_builder() {
208 let mut map = HashMap::<u32, u64, ABuildHasher>::default();
209 map.insert(1, 3);
210 }
211
212 #[test]
test_conversion()213 fn test_conversion() {
214 let input: &[u8] = b"dddddddd";
215 let bytes: u64 = as_array!(input, 8).convert();
216 assert_eq!(bytes, 0x6464646464646464);
217 }
218
219 #[test]
test_ahasher_construction()220 fn test_ahasher_construction() {
221 let _ = AHasher::new_with_keys(1245, 5678);
222 }
223 }
224