1use core::hash::Hash;
2cfg_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}
12cfg_if::cfg_if! {
13 if #[cfg(feature = "specialize")]{
14 use crate::BuildHasherExt;
15 }
16}
17cfg_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")]
26use atomic_polyfill as atomic;
27#[cfg(not(feature = "atomic-polyfill"))]
28use core::sync::atomic;
29
30use alloc::boxed::Box;
31use atomic::{AtomicUsize, Ordering};
32use core::any::{Any, TypeId};
33use core::fmt;
34use core::hash::BuildHasher;
35use core::hash::Hasher;
36
37pub(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
44pub(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
51cfg_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
113cfg_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)
131pub trait RandomSource {
132 fn gen_hasher_seed(&self) -> usize;
133}
134
135struct DefaultRandomSource {
136 counter: AtomicUsize,
137}
138
139impl 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
154impl 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
173cfg_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)]
219pub struct RandomState {
220 pub(crate) k0: u64,
221 pub(crate) k1: u64,
222 pub(crate) k2: u64,
223 pub(crate) k3: u64,
224}
225
226impl fmt::Debug for RandomState {
227 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
228 f.pad("RandomState { .. }")
229 }
230}
231
232impl 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"))]
376impl Default for RandomState {
377 #[inline]
378 fn default() -> Self {
379 Self::new()
380 }
381}
382
383impl 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")]
470impl 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)]
497mod 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