1 | use core::hash::Hash; |
2 | cfg_if::cfg_if! { |
3 | if #[cfg(any( |
4 | all(any(target_arch = "x86" , target_arch = "x86_64" ), target_feature = "aes" , not(miri)), |
5 | all(any(target_arch = "arm" , target_arch = "aarch64" ), any(target_feature = "aes" , target_feature = "crypto" ), not(miri), feature = "stdsimd" ) |
6 | ))] { |
7 | use crate::aes_hash::*; |
8 | } else { |
9 | use crate::fallback_hash::*; |
10 | } |
11 | } |
12 | cfg_if::cfg_if! { |
13 | if #[cfg(feature = "specialize" )]{ |
14 | use crate::BuildHasherExt; |
15 | } |
16 | } |
17 | cfg_if::cfg_if! { |
18 | if #[cfg(feature = "std" )] { |
19 | extern crate std as alloc; |
20 | } else { |
21 | extern crate alloc; |
22 | } |
23 | } |
24 | |
25 | #[cfg (feature = "atomic-polyfill" )] |
26 | use atomic_polyfill as atomic; |
27 | #[cfg (not(feature = "atomic-polyfill" ))] |
28 | use core::sync::atomic; |
29 | |
30 | use alloc::boxed::Box; |
31 | use atomic::{AtomicUsize, Ordering}; |
32 | use core::any::{Any, TypeId}; |
33 | use core::fmt; |
34 | use core::hash::BuildHasher; |
35 | use core::hash::Hasher; |
36 | |
37 | pub(crate) const PI: [u64; 4] = [ |
38 | 0x243f_6a88_85a3_08d3, |
39 | 0x1319_8a2e_0370_7344, |
40 | 0xa409_3822_299f_31d0, |
41 | 0x082e_fa98_ec4e_6c89, |
42 | ]; |
43 | |
44 | pub(crate) const PI2: [u64; 4] = [ |
45 | 0x4528_21e6_38d0_1377, |
46 | 0xbe54_66cf_34e9_0c6c, |
47 | 0xc0ac_29b7_c97c_50dd, |
48 | 0x3f84_d5b5_b547_0917, |
49 | ]; |
50 | |
51 | cfg_if::cfg_if! { |
52 | if #[cfg(all(feature = "compile-time-rng" , any(test, fuzzing)))] { |
53 | #[inline ] |
54 | fn get_fixed_seeds() -> &'static [[u64; 4]; 2] { |
55 | use const_random::const_random; |
56 | |
57 | const RAND: [[u64; 4]; 2] = [ |
58 | [ |
59 | const_random!(u64), |
60 | const_random!(u64), |
61 | const_random!(u64), |
62 | const_random!(u64), |
63 | ], [ |
64 | const_random!(u64), |
65 | const_random!(u64), |
66 | const_random!(u64), |
67 | const_random!(u64), |
68 | ] |
69 | ]; |
70 | &RAND |
71 | } |
72 | } else if #[cfg(all(feature = "runtime-rng" , not(fuzzing)))] { |
73 | #[inline ] |
74 | fn get_fixed_seeds() -> &'static [[u64; 4]; 2] { |
75 | use crate::convert::Convert; |
76 | |
77 | static SEEDS: OnceBox<[[u64; 4]; 2]> = OnceBox::new(); |
78 | |
79 | SEEDS.get_or_init(|| { |
80 | let mut result: [u8; 64] = [0; 64]; |
81 | getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed." ); |
82 | Box::new(result.convert()) |
83 | }) |
84 | } |
85 | } else if #[cfg(feature = "compile-time-rng" )] { |
86 | #[inline ] |
87 | fn get_fixed_seeds() -> &'static [[u64; 4]; 2] { |
88 | use const_random::const_random; |
89 | |
90 | const RAND: [[u64; 4]; 2] = [ |
91 | [ |
92 | const_random!(u64), |
93 | const_random!(u64), |
94 | const_random!(u64), |
95 | const_random!(u64), |
96 | ], [ |
97 | const_random!(u64), |
98 | const_random!(u64), |
99 | const_random!(u64), |
100 | const_random!(u64), |
101 | ] |
102 | ]; |
103 | &RAND |
104 | } |
105 | } else { |
106 | #[inline ] |
107 | fn get_fixed_seeds() -> &'static [[u64; 4]; 2] { |
108 | &[PI, PI2] |
109 | } |
110 | } |
111 | } |
112 | |
113 | cfg_if::cfg_if! { |
114 | if #[cfg(not(all(target_arch = "arm" , target_os = "none" )))] { |
115 | use once_cell::race::OnceBox; |
116 | |
117 | static RAND_SOURCE: OnceBox<Box<dyn RandomSource + Send + Sync>> = OnceBox::new(); |
118 | } |
119 | } |
120 | /// A supplier of Randomness used for different hashers. |
121 | /// See [set_random_source]. |
122 | /// |
123 | /// If [set_random_source] aHash will default to the best available source of randomness. |
124 | /// In order this is: |
125 | /// 1. OS provided random number generator (available if the `runtime-rng` flag is enabled which it is by default) - This should be very strong. |
126 | /// 2. Strong compile time random numbers used to permute a static "counter". (available if `compile-time-rng` is enabled. |
127 | /// __Enabling this is recommended if `runtime-rng` is not possible__) |
128 | /// 3. A static counter that adds the memory address of each [RandomState] created permuted with fixed constants. |
129 | /// (Similar to above but with fixed keys) - This is the weakest option. The strength of this heavily depends on whether or not ASLR is enabled. |
130 | /// (Rust enables ASLR by default) |
131 | pub trait RandomSource { |
132 | fn gen_hasher_seed(&self) -> usize; |
133 | } |
134 | |
135 | struct DefaultRandomSource { |
136 | counter: AtomicUsize, |
137 | } |
138 | |
139 | impl DefaultRandomSource { |
140 | fn new() -> DefaultRandomSource { |
141 | DefaultRandomSource { |
142 | counter: AtomicUsize::new(&PI as *const _ as usize), |
143 | } |
144 | } |
145 | |
146 | #[cfg (all(target_arch = "arm" , target_os = "none" ))] |
147 | const fn default() -> DefaultRandomSource { |
148 | DefaultRandomSource { |
149 | counter: AtomicUsize::new(PI[3] as usize), |
150 | } |
151 | } |
152 | } |
153 | |
154 | impl RandomSource for DefaultRandomSource { |
155 | cfg_if::cfg_if! { |
156 | if #[cfg(all(target_arch = "arm" , target_os = "none" ))] { |
157 | fn gen_hasher_seed(&self) -> usize { |
158 | let stack = self as *const _ as usize; |
159 | let previous = self.counter.load(Ordering::Relaxed); |
160 | let new = previous.wrapping_add(stack); |
161 | self.counter.store(new, Ordering::Relaxed); |
162 | new |
163 | } |
164 | } else { |
165 | fn gen_hasher_seed(&self) -> usize { |
166 | let stack = self as *const _ as usize; |
167 | self.counter.fetch_add(stack, Ordering::Relaxed) |
168 | } |
169 | } |
170 | } |
171 | } |
172 | |
173 | cfg_if::cfg_if! { |
174 | if #[cfg(all(target_arch = "arm" , target_os = "none" ))] { |
175 | #[inline ] |
176 | fn get_src() -> &'static dyn RandomSource { |
177 | static RAND_SOURCE: DefaultRandomSource = DefaultRandomSource::default(); |
178 | &RAND_SOURCE |
179 | } |
180 | } else { |
181 | /// Provides an optional way to manually supply a source of randomness for Hasher keys. |
182 | /// |
183 | /// The provided [RandomSource] will be used to be used as a source of randomness by [RandomState] to generate new states. |
184 | /// If this method is not invoked the standard source of randomness is used as described in the Readme. |
185 | /// |
186 | /// The source of randomness can only be set once, and must be set before the first RandomState is created. |
187 | /// If the source has already been specified `Err` is returned with a `bool` indicating if the set failed because |
188 | /// method was previously invoked (true) or if the default source is already being used (false). |
189 | #[cfg (not(all(target_arch = "arm" , target_os = "none" )))] |
190 | pub fn set_random_source(source: impl RandomSource + Send + Sync + 'static) -> Result<(), bool> { |
191 | RAND_SOURCE.set(Box::new(Box::new(source))).map_err(|s| s.as_ref().type_id() != TypeId::of::<&DefaultRandomSource>()) |
192 | } |
193 | |
194 | #[inline ] |
195 | fn get_src() -> &'static dyn RandomSource { |
196 | RAND_SOURCE.get_or_init(|| Box::new(Box::new(DefaultRandomSource::new()))).as_ref() |
197 | } |
198 | } |
199 | } |
200 | |
201 | /// Provides a [Hasher] factory. This is typically used (e.g. by [HashMap]) to create |
202 | /// [AHasher]s in order to hash the keys of the map. See `build_hasher` below. |
203 | /// |
204 | /// [build_hasher]: ahash:: |
205 | /// [Hasher]: std::hash::Hasher |
206 | /// [BuildHasher]: std::hash::BuildHasher |
207 | /// [HashMap]: std::collections::HashMap |
208 | /// |
209 | /// There are multiple constructors each is documented in more detail below: |
210 | /// |
211 | /// | Constructor | Dynamically random? | Seed | |
212 | /// |---------------|---------------------|------| |
213 | /// |`new` | Each instance unique|_[RandomSource]_| |
214 | /// |`generate_with`| Each instance unique|`u64` x 4 + [RandomSource]| |
215 | /// |`with_seed` | Fixed per process |`u64` + static random number| |
216 | /// |`with_seeds` | Fixed |`u64` x 4| |
217 | /// |
218 | #[derive (Clone)] |
219 | pub struct RandomState { |
220 | pub(crate) k0: u64, |
221 | pub(crate) k1: u64, |
222 | pub(crate) k2: u64, |
223 | pub(crate) k3: u64, |
224 | } |
225 | |
226 | impl fmt::Debug for RandomState { |
227 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
228 | f.pad("RandomState { .. }" ) |
229 | } |
230 | } |
231 | |
232 | impl RandomState { |
233 | |
234 | /// Create a new `RandomState` `BuildHasher` using random keys. |
235 | /// |
236 | /// Each instance will have a unique set of keys derived from [RandomSource]. |
237 | /// |
238 | #[inline ] |
239 | pub fn new() -> RandomState { |
240 | let src = get_src(); |
241 | let fixed = get_fixed_seeds(); |
242 | Self::from_keys(&fixed[0], &fixed[1], src.gen_hasher_seed()) |
243 | } |
244 | |
245 | /// Create a new `RandomState` `BuildHasher` based on the provided seeds, but in such a way |
246 | /// that each time it is called the resulting state will be different and of high quality. |
247 | /// This allows fixed constant or poor quality seeds to be provided without the problem of different |
248 | /// `BuildHasher`s being identical or weak. |
249 | /// |
250 | /// This is done via permuting the provided values with the value of a static counter and memory address. |
251 | /// (This makes this method somewhat more expensive than `with_seeds` below which does not do this). |
252 | /// |
253 | /// The provided values (k0-k3) do not need to be of high quality but they should not all be the same value. |
254 | #[inline ] |
255 | pub fn generate_with(k0: u64, k1: u64, k2: u64, k3: u64) -> RandomState { |
256 | let src = get_src(); |
257 | let fixed = get_fixed_seeds(); |
258 | RandomState::from_keys(&fixed[0], &[k0, k1, k2, k3], src.gen_hasher_seed()) |
259 | } |
260 | |
261 | fn from_keys(a: &[u64; 4], b: &[u64; 4], c: usize) -> RandomState { |
262 | let &[k0, k1, k2, k3] = a; |
263 | let mut hasher = AHasher::from_random_state(&RandomState { k0, k1, k2, k3 }); |
264 | hasher.write_usize(c); |
265 | let mix = |l: u64, r: u64| { |
266 | let mut h = hasher.clone(); |
267 | h.write_u64(l); |
268 | h.write_u64(r); |
269 | h.finish() |
270 | }; |
271 | RandomState { |
272 | k0: mix(b[0], b[2]), |
273 | k1: mix(b[1], b[3]), |
274 | k2: mix(b[2], b[1]), |
275 | k3: mix(b[3], b[0]), |
276 | } |
277 | } |
278 | |
279 | /// Internal. Used by Default. |
280 | #[inline ] |
281 | pub(crate) fn with_fixed_keys() -> RandomState { |
282 | let [k0, k1, k2, k3] = get_fixed_seeds()[0]; |
283 | RandomState { k0, k1, k2, k3 } |
284 | } |
285 | |
286 | /// Build a `RandomState` from a single key. The provided key does not need to be of high quality, |
287 | /// but all `RandomState`s created from the same key will produce identical hashers. |
288 | /// (In contrast to `generate_with` above) |
289 | /// |
290 | /// This allows for explicitly setting the seed to be used. |
291 | /// |
292 | /// Note: This method does not require the provided seed to be strong. |
293 | #[inline ] |
294 | pub fn with_seed(key: usize) -> RandomState { |
295 | let fixed = get_fixed_seeds(); |
296 | RandomState::from_keys(&fixed[0], &fixed[1], key) |
297 | } |
298 | |
299 | /// Allows for explicitly setting the seeds to used. |
300 | /// All `RandomState`s created with the same set of keys key will produce identical hashers. |
301 | /// (In contrast to `generate_with` above) |
302 | /// |
303 | /// Note: If DOS resistance is desired one of these should be a decent quality random number. |
304 | /// If 4 high quality random number are not cheaply available this method is robust against 0s being passed for |
305 | /// one or more of the parameters or the same value being passed for more than one parameter. |
306 | /// It is recommended to pass numbers in order from highest to lowest quality (if there is any difference). |
307 | #[inline ] |
308 | pub const fn with_seeds(k0: u64, k1: u64, k2: u64, k3: u64) -> RandomState { |
309 | RandomState { |
310 | k0: k0 ^ PI2[0], |
311 | k1: k1 ^ PI2[1], |
312 | k2: k2 ^ PI2[2], |
313 | k3: k3 ^ PI2[3], |
314 | } |
315 | } |
316 | |
317 | /// Calculates the hash of a single value. This provides a more convenient (and faster) way to obtain a hash: |
318 | /// For example: |
319 | #[cfg_attr ( |
320 | feature = "std" , |
321 | doc = r##" # Examples |
322 | ``` |
323 | use std::hash::BuildHasher; |
324 | use ahash::RandomState; |
325 | |
326 | let hash_builder = RandomState::new(); |
327 | let hash = hash_builder.hash_one("Some Data"); |
328 | ``` |
329 | "## |
330 | )] |
331 | /// This is similar to: |
332 | #[cfg_attr ( |
333 | feature = "std" , |
334 | doc = r##" # Examples |
335 | ``` |
336 | use std::hash::{BuildHasher, Hash, Hasher}; |
337 | use ahash::RandomState; |
338 | |
339 | let hash_builder = RandomState::new(); |
340 | let mut hasher = hash_builder.build_hasher(); |
341 | "Some Data".hash(&mut hasher); |
342 | let hash = hasher.finish(); |
343 | ``` |
344 | "## |
345 | )] |
346 | /// (Note that these two ways to get a hash may not produce the same value for the same data) |
347 | /// |
348 | /// This is intended as a convenience for code which *consumes* hashes, such |
349 | /// as the implementation of a hash table or in unit tests that check |
350 | /// whether a custom [`Hash`] implementation behaves as expected. |
351 | /// |
352 | /// This must not be used in any code which *creates* hashes, such as in an |
353 | /// implementation of [`Hash`]. The way to create a combined hash of |
354 | /// multiple values is to call [`Hash::hash`] multiple times using the same |
355 | /// [`Hasher`], not to call this method repeatedly and combine the results. |
356 | #[inline ] |
357 | pub fn hash_one<T: Hash>(&self, x: T) -> u64 |
358 | where |
359 | Self: Sized, |
360 | { |
361 | use crate::specialize::CallHasher; |
362 | T::get_hash(&x, self) |
363 | } |
364 | } |
365 | |
366 | /// Creates an instance of RandomState using keys obtained from the random number generator. |
367 | /// Each instance created in this way will have a unique set of keys. (But the resulting instance |
368 | /// can be used to create many hashers each or which will have the same keys.) |
369 | /// |
370 | /// This is the same as [RandomState::new()] |
371 | /// |
372 | /// NOTE: For safety this trait impl is only available available if either of the flags `runtime-rng` (on by default) or |
373 | /// `compile-time-rng` are enabled. This is to prevent weakly keyed maps from being accidentally created. Instead one of |
374 | /// constructors for [RandomState] must be used. |
375 | #[cfg (any(feature = "compile-time-rng" , feature = "runtime-rng" , feature = "no-rng" ))] |
376 | impl Default for RandomState { |
377 | #[inline ] |
378 | fn default() -> Self { |
379 | Self::new() |
380 | } |
381 | } |
382 | |
383 | impl BuildHasher for RandomState { |
384 | type Hasher = AHasher; |
385 | |
386 | /// Constructs a new [AHasher] with keys based on this [RandomState] object. |
387 | /// This means that two different [RandomState]s will will generate |
388 | /// [AHasher]s that will return different hashcodes, but [Hasher]s created from the same [BuildHasher] |
389 | /// will generate the same hashes for the same input data. |
390 | /// |
391 | #[cfg_attr ( |
392 | feature = "std" , |
393 | doc = r##" # Examples |
394 | ``` |
395 | use ahash::{AHasher, RandomState}; |
396 | use std::hash::{Hasher, BuildHasher}; |
397 | |
398 | let build_hasher = RandomState::new(); |
399 | let mut hasher_1 = build_hasher.build_hasher(); |
400 | let mut hasher_2 = build_hasher.build_hasher(); |
401 | |
402 | hasher_1.write_u32(1234); |
403 | hasher_2.write_u32(1234); |
404 | |
405 | assert_eq!(hasher_1.finish(), hasher_2.finish()); |
406 | |
407 | let other_build_hasher = RandomState::new(); |
408 | let mut different_hasher = other_build_hasher.build_hasher(); |
409 | different_hasher.write_u32(1234); |
410 | assert_ne!(different_hasher.finish(), hasher_1.finish()); |
411 | ``` |
412 | "## |
413 | )] |
414 | /// [Hasher]: std::hash::Hasher |
415 | /// [BuildHasher]: std::hash::BuildHasher |
416 | /// [HashMap]: std::collections::HashMap |
417 | #[inline ] |
418 | fn build_hasher(&self) -> AHasher { |
419 | AHasher::from_random_state(self) |
420 | } |
421 | |
422 | |
423 | /// Calculates the hash of a single value. This provides a more convenient (and faster) way to obtain a hash: |
424 | /// For example: |
425 | #[cfg_attr ( |
426 | feature = "std" , |
427 | doc = r##" # Examples |
428 | ``` |
429 | use std::hash::BuildHasher; |
430 | use ahash::RandomState; |
431 | |
432 | let hash_builder = RandomState::new(); |
433 | let hash = hash_builder.hash_one("Some Data"); |
434 | ``` |
435 | "## |
436 | )] |
437 | /// This is similar to: |
438 | #[cfg_attr ( |
439 | feature = "std" , |
440 | doc = r##" # Examples |
441 | ``` |
442 | use std::hash::{BuildHasher, Hash, Hasher}; |
443 | use ahash::RandomState; |
444 | |
445 | let hash_builder = RandomState::new(); |
446 | let mut hasher = hash_builder.build_hasher(); |
447 | "Some Data".hash(&mut hasher); |
448 | let hash = hasher.finish(); |
449 | ``` |
450 | "## |
451 | )] |
452 | /// (Note that these two ways to get a hash may not produce the same value for the same data) |
453 | /// |
454 | /// This is intended as a convenience for code which *consumes* hashes, such |
455 | /// as the implementation of a hash table or in unit tests that check |
456 | /// whether a custom [`Hash`] implementation behaves as expected. |
457 | /// |
458 | /// This must not be used in any code which *creates* hashes, such as in an |
459 | /// implementation of [`Hash`]. The way to create a combined hash of |
460 | /// multiple values is to call [`Hash::hash`] multiple times using the same |
461 | /// [`Hasher`], not to call this method repeatedly and combine the results. |
462 | #[cfg (feature = "specialize" )] |
463 | #[inline ] |
464 | fn hash_one<T: Hash>(&self, x: T) -> u64 { |
465 | RandomState::hash_one(self, x) |
466 | } |
467 | } |
468 | |
469 | #[cfg (feature = "specialize" )] |
470 | impl BuildHasherExt for RandomState { |
471 | #[inline ] |
472 | fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
473 | let mut hasher = AHasherU64 { |
474 | buffer: self.k0, |
475 | pad: self.k1, |
476 | }; |
477 | value.hash(&mut hasher); |
478 | hasher.finish() |
479 | } |
480 | |
481 | #[inline ] |
482 | fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
483 | let mut hasher = AHasherFixed(self.build_hasher()); |
484 | value.hash(&mut hasher); |
485 | hasher.finish() |
486 | } |
487 | |
488 | #[inline ] |
489 | fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 { |
490 | let mut hasher = AHasherStr(self.build_hasher()); |
491 | value.hash(&mut hasher); |
492 | hasher.finish() |
493 | } |
494 | } |
495 | |
496 | #[cfg (test)] |
497 | mod test { |
498 | use super::*; |
499 | |
500 | #[test ] |
501 | fn test_unique() { |
502 | let a = RandomState::generate_with(1, 2, 3, 4); |
503 | let b = RandomState::generate_with(1, 2, 3, 4); |
504 | assert_ne!(a.build_hasher().finish(), b.build_hasher().finish()); |
505 | } |
506 | |
507 | #[cfg (all(feature = "runtime-rng" , not(all(feature = "compile-time-rng" , test))))] |
508 | #[test ] |
509 | fn test_not_pi() { |
510 | assert_ne!(PI, get_fixed_seeds()[0]); |
511 | } |
512 | |
513 | #[cfg (all(feature = "compile-time-rng" , any(not(feature = "runtime-rng" ), test)))] |
514 | #[test ] |
515 | fn test_not_pi_const() { |
516 | assert_ne!(PI, get_fixed_seeds()[0]); |
517 | } |
518 | |
519 | #[cfg (all(not(feature = "runtime-rng" ), not(feature = "compile-time-rng" )))] |
520 | #[test ] |
521 | fn test_pi() { |
522 | assert_eq!(PI, get_fixed_seeds()[0]); |
523 | } |
524 | |
525 | #[test ] |
526 | fn test_with_seeds_const() { |
527 | const _CONST_RANDOM_STATE: RandomState = RandomState::with_seeds(17, 19, 21, 23); |
528 | } |
529 | } |
530 | |