1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112

use crate::AHasher;
use core::hash::BuildHasher;
use core::sync::atomic::AtomicUsize;
use core::sync::atomic::Ordering;

#[cfg(feature = "compile-time-rng")]
use const_random::const_random;

///This constant come from Kunth's prng
pub(crate) const MULTIPLE: u64 = 6364136223846793005;
pub(crate) const INCREMENT: u64 = 1442695040888963407;

// Const random provides randomized starting key with no runtime cost.
#[cfg(feature = "compile-time-rng")]
const INIT_SEED: u64 = const_random!(u64);

#[cfg(not(feature = "compile-time-rng"))]
const INIT_SEED: u64 = INCREMENT;

static SEED: AtomicUsize = AtomicUsize::new(INIT_SEED as usize);

/// Provides a [Hasher] factory. This is typically used (e.g. by [`HashMap`]) to create
/// [AHasher]s in order to hash the keys of the map. See `build_hasher` below.
///
/// [build_hasher]: ahash::
/// [Hasher]: std::hash::Hasher
/// [BuildHasher]: std::hash::BuildHasher
/// [HashMap]: std::collections::HashMap
#[derive(Clone)]
pub struct RandomState {
    pub(crate) k0: u64,
    pub(crate) k1: u64,
}

impl RandomState {
    #[inline]
    pub fn new() -> RandomState {
        //Using a self pointer. When running with ASLR this is a random value.
        let previous = SEED.load(Ordering::Relaxed) as u64;
        let stack_mem_loc = &previous as *const _ as u64;
        //This is similar to the update function in the fallback.
        //only one multiply is needed because memory locations are not under an attackers control.
        let current_seed = previous
            .wrapping_add(stack_mem_loc)
            .wrapping_mul(MULTIPLE)
            .rotate_right(31);
        SEED.store(current_seed as usize, Ordering::Relaxed);
        let (k0, k1) = scramble_keys(&SEED as *const _ as u64, current_seed);
        RandomState { k0, k1 }
    }

    /// Allows for explicetly setting the seeds to used.
    pub fn with_seeds(k0: u64, k1: u64) -> RandomState {
        RandomState { k0, k1 }
    }
}

pub(crate) fn scramble_keys(k0: u64, k1: u64) -> (u64, u64) {
    //Scramble seeds (based on xoroshiro128+)
    //This is intentionally not similar the hash algorithm
    let result1 = k0.wrapping_add(k1);
    let k1 = k1 ^ k0;
    let k0 = k0.rotate_left(24) ^ k1 ^ (k1.wrapping_shl(16));
    let result2 = k0.wrapping_add(k1.rotate_left(37));
    (result2, result1)
}

impl Default for RandomState {
    #[inline]
    fn default() -> Self {
        Self::new()
    }
}

impl BuildHasher for RandomState {
    type Hasher = AHasher;

    /// Constructs a new [AHasher] with keys based on compile time generated constants** and the location
    /// this object was constructed at in memory. This means that two different [BuildHasher]s will will generate
    /// [AHasher]s that will return different hashcodes, but [Hasher]s created from the same [BuildHasher]
    /// will generate the same hashes for the same input data.
    ///
    /// ** - only if the `compile-time-rng` feature is enabled.
    ///
    /// # Examples
    ///
    /// ```
    /// use ahash::{AHasher, RandomState};
    /// use std::hash::{Hasher, BuildHasher};
    ///
    /// let build_hasher = RandomState::new();
    /// let mut hasher_1 = build_hasher.build_hasher();
    /// let mut hasher_2 = build_hasher.build_hasher();
    ///
    /// hasher_1.write_u32(1234);
    /// hasher_2.write_u32(1234);
    ///
    /// assert_eq!(hasher_1.finish(), hasher_2.finish());
    ///
    /// let other_build_hasher = RandomState::new();
    /// let mut different_hasher = other_build_hasher.build_hasher();
    /// different_hasher.write_u32(1234);
    /// assert_ne!(different_hasher.finish(), hasher_1.finish());
    /// ```
    /// [Hasher]: std::hash::Hasher
    /// [BuildHasher]: std::hash::BuildHasher
    /// [HashMap]: std::collections::HashMap
    #[inline]
    fn build_hasher(&self) -> AHasher {
        AHasher::new_with_keys(self.k0, self.k1)
    }
}