ahash/
random_state.rs

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(feature = "nightly-arm-aes", target_arch = "aarch64", target_feature = "aes", not(miri)),
6        all(feature = "nightly-arm-aes", target_arch = "arm", target_feature = "aes", not(miri)),
7    ))] {
8        use crate::aes_hash::*;
9    } else {
10        use crate::fallback_hash::*;
11    }
12}
13cfg_if::cfg_if! {
14    if #[cfg(feature = "specialize")]{
15        use crate::BuildHasherExt;
16    }
17}
18cfg_if::cfg_if! {
19    if #[cfg(feature = "std")] {
20        extern crate std as alloc;
21    } else {
22        extern crate alloc;
23    }
24}
25
26#[cfg(feature = "atomic-polyfill")]
27use atomic_polyfill as atomic;
28#[cfg(not(feature = "atomic-polyfill"))]
29use core::sync::atomic;
30
31use alloc::boxed::Box;
32use atomic::{AtomicUsize, Ordering};
33use core::any::{Any, TypeId};
34use core::fmt;
35use core::hash::BuildHasher;
36use core::hash::Hasher;
37
38pub(crate) const PI: [u64; 4] = [
39    0x243f_6a88_85a3_08d3,
40    0x1319_8a2e_0370_7344,
41    0xa409_3822_299f_31d0,
42    0x082e_fa98_ec4e_6c89,
43];
44
45pub(crate) const PI2: [u64; 4] = [
46    0x4528_21e6_38d0_1377,
47    0xbe54_66cf_34e9_0c6c,
48    0xc0ac_29b7_c97c_50dd,
49    0x3f84_d5b5_b547_0917,
50];
51
52cfg_if::cfg_if! {
53    if #[cfg(all(feature = "compile-time-rng", any(test, fuzzing)))] {
54        #[inline]
55        fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
56            use const_random::const_random;
57
58            const RAND: [[u64; 4]; 2] = [
59                [
60                    const_random!(u64),
61                    const_random!(u64),
62                    const_random!(u64),
63                    const_random!(u64),
64                ], [
65                    const_random!(u64),
66                    const_random!(u64),
67                    const_random!(u64),
68                    const_random!(u64),
69                ]
70            ];
71            &RAND
72        }
73    } else if #[cfg(all(feature = "runtime-rng", not(fuzzing)))] {
74        #[inline]
75        fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
76            use crate::convert::Convert;
77
78            static SEEDS: OnceBox<[[u64; 4]; 2]> = OnceBox::new();
79
80            SEEDS.get_or_init(|| {
81                let mut result: [u8; 64] = [0; 64];
82                getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
83                Box::new(result.convert())
84            })
85        }
86    } else if #[cfg(feature = "compile-time-rng")] {
87        #[inline]
88        fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
89            use const_random::const_random;
90
91            const RAND: [[u64; 4]; 2] = [
92                [
93                    const_random!(u64),
94                    const_random!(u64),
95                    const_random!(u64),
96                    const_random!(u64),
97                ], [
98                    const_random!(u64),
99                    const_random!(u64),
100                    const_random!(u64),
101                    const_random!(u64),
102                ]
103            ];
104            &RAND
105        }
106    } else {
107        #[inline]
108        fn get_fixed_seeds() -> &'static [[u64; 4]; 2] {
109            &[PI, PI2]
110        }
111    }
112}
113
114cfg_if::cfg_if! {
115    if #[cfg(not(all(target_arch = "arm", target_os = "none")))] {
116        use once_cell::race::OnceBox;
117
118        static RAND_SOURCE: OnceBox<Box<dyn RandomSource + Send + Sync>> = OnceBox::new();
119    }
120}
121/// A supplier of Randomness used for different hashers.
122/// See [set_random_source].
123///
124/// If [set_random_source] aHash will default to the best available source of randomness.
125/// In order this is:
126/// 1. OS provided random number generator (available if the `runtime-rng` flag is enabled which it is by default) - This should be very strong.
127/// 2. Strong compile time random numbers used to permute a static "counter". (available if `compile-time-rng` is enabled.
128/// __Enabling this is recommended if `runtime-rng` is not possible__)
129/// 3. A static counter that adds the memory address of each [RandomState] created permuted with fixed constants.
130/// (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.
131/// (Rust enables ASLR by default)
132pub trait RandomSource {
133    fn gen_hasher_seed(&self) -> usize;
134}
135
136struct DefaultRandomSource {
137    counter: AtomicUsize,
138}
139
140impl DefaultRandomSource {
141    fn new() -> DefaultRandomSource {
142        DefaultRandomSource {
143            counter: AtomicUsize::new(&PI as *const _ as usize),
144        }
145    }
146
147    #[cfg(all(target_arch = "arm", target_os = "none"))]
148    const fn default() -> DefaultRandomSource {
149        DefaultRandomSource {
150            counter: AtomicUsize::new(PI[3] as usize),
151        }
152    }
153}
154
155impl RandomSource for DefaultRandomSource {
156    cfg_if::cfg_if! {
157        if #[cfg(all(target_arch = "arm", target_os = "none"))] {
158            fn gen_hasher_seed(&self) -> usize {
159                let stack = self as *const _ as usize;
160                let previous = self.counter.load(Ordering::Relaxed);
161                let new = previous.wrapping_add(stack);
162                self.counter.store(new, Ordering::Relaxed);
163                new
164            }
165        } else {
166            fn gen_hasher_seed(&self) -> usize {
167                let stack = self as *const _ as usize;
168                self.counter.fetch_add(stack, Ordering::Relaxed)
169            }
170        }
171    }
172}
173
174cfg_if::cfg_if! {
175        if #[cfg(all(target_arch = "arm", target_os = "none"))] {
176            #[inline]
177            fn get_src() -> &'static dyn RandomSource {
178                static RAND_SOURCE: DefaultRandomSource = DefaultRandomSource::default();
179                &RAND_SOURCE
180            }
181        } else {
182            /// Provides an optional way to manually supply a source of randomness for Hasher keys.
183            ///
184            /// The provided [RandomSource] will be used to be used as a source of randomness by [RandomState] to generate new states.
185            /// If this method is not invoked the standard source of randomness is used as described in the Readme.
186            ///
187            /// The source of randomness can only be set once, and must be set before the first RandomState is created.
188            /// If the source has already been specified `Err` is returned with a `bool` indicating if the set failed because
189            /// method was previously invoked (true) or if the default source is already being used (false).
190            #[cfg(not(all(target_arch = "arm", target_os = "none")))]
191            pub fn set_random_source(source: impl RandomSource + Send + Sync + 'static) -> Result<(), bool> {
192                RAND_SOURCE.set(Box::new(Box::new(source))).map_err(|s| s.as_ref().type_id() != TypeId::of::<&DefaultRandomSource>())
193            }
194
195            #[inline]
196            fn get_src() -> &'static dyn RandomSource {
197                RAND_SOURCE.get_or_init(|| Box::new(Box::new(DefaultRandomSource::new()))).as_ref()
198            }
199        }
200}
201
202/// Provides a [Hasher] factory. This is typically used (e.g. by [HashMap]) to create
203/// [AHasher]s in order to hash the keys of the map. See `build_hasher` below.
204///
205/// [build_hasher]: ahash::
206/// [Hasher]: std::hash::Hasher
207/// [BuildHasher]: std::hash::BuildHasher
208/// [HashMap]: std::collections::HashMap
209///
210/// There are multiple constructors each is documented in more detail below:
211///
212/// | Constructor   | Dynamically random? | Seed |
213/// |---------------|---------------------|------|
214/// |`new`          | Each instance unique|_[RandomSource]_|
215/// |`generate_with`| Each instance unique|`u64` x 4 + [RandomSource]|
216/// |`with_seed`    | Fixed per process   |`u64` + static random number|
217/// |`with_seeds`   | Fixed               |`u64` x 4|
218///
219#[derive(Clone)]
220pub struct RandomState {
221    pub(crate) k0: u64,
222    pub(crate) k1: u64,
223    pub(crate) k2: u64,
224    pub(crate) k3: u64,
225}
226
227impl fmt::Debug for RandomState {
228    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
229        f.pad("RandomState { .. }")
230    }
231}
232
233impl RandomState {
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    /// Calculates the hash of a single value. This provides a more convenient (and faster) way to obtain a hash:
423    /// For example:
424    #[cfg_attr(
425        feature = "std",
426        doc = r##" # Examples
427```
428    use std::hash::BuildHasher;
429    use ahash::RandomState;
430
431    let hash_builder = RandomState::new();
432    let hash = hash_builder.hash_one("Some Data");
433```
434    "##
435    )]
436    /// This is similar to:
437    #[cfg_attr(
438        feature = "std",
439        doc = r##" # Examples
440```
441    use std::hash::{BuildHasher, Hash, Hasher};
442    use ahash::RandomState;
443
444    let hash_builder = RandomState::new();
445    let mut hasher = hash_builder.build_hasher();
446    "Some Data".hash(&mut hasher);
447    let hash = hasher.finish();
448```
449    "##
450    )]
451    /// (Note that these two ways to get a hash may not produce the same value for the same data)
452    ///
453    /// This is intended as a convenience for code which *consumes* hashes, such
454    /// as the implementation of a hash table or in unit tests that check
455    /// whether a custom [`Hash`] implementation behaves as expected.
456    ///
457    /// This must not be used in any code which *creates* hashes, such as in an
458    /// implementation of [`Hash`].  The way to create a combined hash of
459    /// multiple values is to call [`Hash::hash`] multiple times using the same
460    /// [`Hasher`], not to call this method repeatedly and combine the results.
461    #[cfg(feature = "specialize")]
462    #[inline]
463    fn hash_one<T: Hash>(&self, x: T) -> u64 {
464        RandomState::hash_one(self, x)
465    }
466}
467
468#[cfg(feature = "specialize")]
469impl BuildHasherExt for RandomState {
470    #[inline]
471    fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 {
472        let mut hasher = AHasherU64 {
473            buffer: self.k1,
474            pad: self.k0,
475        };
476        value.hash(&mut hasher);
477        hasher.finish()
478    }
479
480    #[inline]
481    fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 {
482        let mut hasher = AHasherFixed(self.build_hasher());
483        value.hash(&mut hasher);
484        hasher.finish()
485    }
486
487    #[inline]
488    fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 {
489        let mut hasher = AHasherStr(self.build_hasher());
490        value.hash(&mut hasher);
491        hasher.finish()
492    }
493}
494
495#[cfg(test)]
496mod test {
497    use super::*;
498
499    #[test]
500    fn test_unique() {
501        let a = RandomState::generate_with(1, 2, 3, 4);
502        let b = RandomState::generate_with(1, 2, 3, 4);
503        assert_ne!(a.build_hasher().finish(), b.build_hasher().finish());
504    }
505
506    #[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
507    #[test]
508    fn test_not_pi() {
509        assert_ne!(PI, get_fixed_seeds()[0]);
510    }
511
512    #[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
513    #[test]
514    fn test_not_pi_const() {
515        assert_ne!(PI, get_fixed_seeds()[0]);
516    }
517
518    #[cfg(all(not(feature = "runtime-rng"), not(feature = "compile-time-rng")))]
519    #[test]
520    fn test_pi() {
521        assert_eq!(PI, get_fixed_seeds()[0]);
522    }
523
524    #[test]
525    fn test_with_seeds_const() {
526        const _CONST_RANDOM_STATE: RandomState = RandomState::with_seeds(17, 19, 21, 23);
527    }
528}
ahash/random_state.rs

ahash/
random_state.rs
