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

ahash/
random_state.rs
