rustpython_common/

hash.rs

use core::hash::{BuildHasher, Hash, Hasher};
use malachite_bigint::BigInt;
use num_traits::ToPrimitive;
use siphasher::sip::SipHasher24;

pub type PyHash = i64;
pub type PyUHash = u64;

/// A PyHash value used to represent a missing hash value, e.g. means "not yet computed" for
/// `str`'s hash cache
pub const SENTINEL: PyHash = -1;

/// Prime multiplier used in string and various other hashes.
pub const MULTIPLIER: PyHash = 1_000_003; // 0xf4243
/// Numeric hashes are based on reduction modulo the prime 2**_BITS - 1
pub const BITS: usize = 61;
pub const MODULUS: PyUHash = (1 << BITS) - 1;
pub const INF: PyHash = 314_159;
pub const NAN: PyHash = 0;
pub const IMAG: PyHash = MULTIPLIER;
pub const ALGO: &str = "siphash24";
pub const HASH_BITS: usize = core::mem::size_of::<PyHash>() * 8;
// SipHasher24 takes 2 u64s as a seed
pub const SEED_BITS: usize = core::mem::size_of::<u64>() * 2 * 8;

// pub const CUTOFF: usize = 7;

#[derive(Clone, Copy)]
pub struct HashSecret {
    k0: u64,
    k1: u64,
}

impl BuildHasher for HashSecret {
    type Hasher = SipHasher24;

    fn build_hasher(&self) -> Self::Hasher {
        SipHasher24::new_with_keys(self.k0, self.k1)
    }
}

impl HashSecret {
    #[must_use]
    pub fn new(seed: u32) -> Self {
        let mut buf = [0u8; 16];
        lcg_urandom(seed, &mut buf);
        let (left, right) = buf.split_at(8);
        let k0 = u64::from_le_bytes(left.try_into().unwrap());
        let k1 = u64::from_le_bytes(right.try_into().unwrap());
        Self { k0, k1 }
    }

    /// Build a secret from explicit SipHash keys, bypassing seed derivation.
    /// Lets an embedder reproduce a fixed keying (e.g. a deterministic run) that
    /// [`new`](Self::new) cannot express through its `u32` seed.
    #[must_use]
    pub const fn from_keys(k0: u64, k1: u64) -> Self {
        Self { k0, k1 }
    }

    pub fn hash_value<T: Hash + ?Sized>(&self, data: &T) -> PyHash {
        fix_sentinel(mod_int(self.hash_one(data) as _))
    }

    pub fn hash_iter<'a, T: 'a, I, F, E>(&self, iter: I, hash_func: F) -> Result<PyHash, E>
    where
        I: IntoIterator<Item = &'a T>,
        F: Fn(&'a T) -> Result<PyHash, E>,
    {
        let mut hasher = self.build_hasher();
        for element in iter {
            let item_hash = hash_func(element)?;
            item_hash.hash(&mut hasher);
        }
        Ok(fix_sentinel(mod_int(hasher.finish() as PyHash)))
    }

    #[must_use]
    pub fn hash_bytes(&self, value: &[u8]) -> PyHash {
        if value.is_empty() {
            0
        } else {
            self.hash_value(value)
        }
    }

    #[must_use]
    pub fn hash_str(&self, value: &str) -> PyHash {
        self.hash_bytes(value.as_bytes())
    }
}

#[inline]
#[must_use]
pub const fn hash_pointer(value: usize) -> PyHash {
    // TODO: 32bit?
    let hash = (value >> 4) | value;
    hash as _
}

#[inline]
#[must_use]
pub const fn hash_float(value: f64) -> Option<PyHash> {
    // cpython _Py_HashDouble
    if !value.is_finite() {
        return if value.is_infinite() {
            Some(if value > 0.0 { INF } else { -INF })
        } else {
            None
        };
    }

    let frexp = super::float_ops::decompose_float(value);

    // process 28 bits at a time;  this should work well both for binary
    // and hexadecimal floating point.
    let mut m = frexp.0;
    let mut e = frexp.1;
    let mut x: PyUHash = 0;

    #[expect(clippy::while_float, reason = "keep this loop like CPython does it")]
    while m != 0.0 {
        x = ((x << 28) & MODULUS) | (x >> (BITS - 28));
        m *= 268_435_456.0; // 2**28
        e -= 28;
        let y = m as PyUHash; // pull out integer part
        m -= y as f64;
        x += y;
        if x >= MODULUS {
            x -= MODULUS;
        }
    }

    // adjust for the exponent;  first reduce it modulo BITS
    const BITS32: i32 = BITS as i32;
    e = if e >= 0 {
        e % BITS32
    } else {
        BITS32 - 1 - ((-1 - e) % BITS32)
    };
    x = ((x << e) & MODULUS) | (x >> (BITS32 - e));

    Some(fix_sentinel(x as PyHash * value.signum() as PyHash))
}

#[must_use]
pub fn hash_bigint(value: &BigInt) -> PyHash {
    let ret = if let Some(v) = value.to_i64() {
        mod_int(v)
    } else {
        // SAFETY:
        // MODULUS < i64::MAX, so value % MODULUS is guaranteed to be in the range of i64
        unsafe { (value % MODULUS).to_i64().unwrap_unchecked() }
    };

    fix_sentinel(ret)
}

#[inline]
#[must_use]
pub const fn hash_usize(data: usize) -> PyHash {
    fix_sentinel(mod_int(data as i64))
}

#[inline(always)]
#[must_use]
pub const fn fix_sentinel(x: PyHash) -> PyHash {
    if x == SENTINEL { -2 } else { x }
}

#[inline]
#[must_use]
pub const fn mod_int(value: i64) -> PyHash {
    value % MODULUS as i64
}

pub fn lcg_urandom(mut x: u32, buf: &mut [u8]) {
    for b in buf {
        x = x.wrapping_mul(214013);
        x = x.wrapping_add(2531011);
        *b = ((x >> 16) & 0xff) as u8;
    }
}

#[inline]
#[must_use]
pub const fn hash_object_id_raw(p: usize) -> PyHash {
    // TODO: Use commented logic when below issue resolved.
    // Ref: https://github.com/RustPython/RustPython/pull/3951#issuecomment-1193108966

    /* bottom 3 or 4 bits are likely to be 0; rotate y by 4 to avoid
    excessive hash collisions for dicts and sets */
    // p.rotate_right(4) as PyHash
    p as PyHash
}

#[inline]
#[must_use]
pub const fn hash_object_id(p: usize) -> PyHash {
    fix_sentinel(hash_object_id_raw(p))
}

#[must_use]
pub fn keyed_hash(key: u64, buf: &[u8]) -> u64 {
    let mut hasher = SipHasher24::new_with_keys(key, 0);
    buf.hash(&mut hasher);
    hasher.finish()
}

/// tuplehash: fold the element hashes of a tuple (xxHash-based).
///
/// The caller supplies each element's hash lazily; a hash computation may fail,
/// in which case the error short-circuits the fold.
pub fn hash_tuple<E>(
    element_hashes: impl IntoIterator<Item = Result<PyHash, E>>,
) -> Result<PyHash, E> {
    const PRIME1: PyUHash = cfg_select! {
        target_pointer_width = "64" => 11400714785074694791,
        target_pointer_width = "32" => 2654435761,
        _ => unreachable!(),
    };

    const PRIME2: PyUHash = cfg_select! {
        target_pointer_width = "64" => 14029467366897019727,
        target_pointer_width = "32" => 2246822519,
        _ => unreachable!(),
    };

    const PRIME5: PyUHash = cfg_select! {
        target_pointer_width = "64" => 2870177450012600261,
        target_pointer_width = "32" => 374761393,
        _ => unreachable!(),
    };

    const ROTATE: u32 = cfg_select! {
        target_pointer_width = "64" => 31,
        target_pointer_width = "32" => 13,
        _ => unreachable!(),
    };

    let mut acc = PRIME5;
    let mut len: PyUHash = 0;

    for element_hash in element_hashes {
        let lane = element_hash? as PyUHash;
        acc = acc.wrapping_add(lane.wrapping_mul(PRIME2));
        acc = acc.rotate_left(ROTATE);
        acc = acc.wrapping_mul(PRIME1);
        len += 1;
    }

    acc = acc.wrapping_add(len ^ (PRIME5 ^ 3527539));

    let acc_py_hash = acc as PyHash;
    if acc_py_hash == -1 {
        return Ok(1546275796);
    }

    Ok(acc_py_hash)
}

/// frozenset_hash: order-independent XOR-fold of a frozenset's element hashes.
///
/// The entry hashes are fed in one at a time via [`FrozenSetHash::add`], so the
/// caller keeps ownership of the iteration (which may hold a lock and compute
/// each element hash fallibly). The fold is commutative, so element order does
/// not affect the result.
pub struct FrozenSetHash {
    hash: u64,
}

impl FrozenSetHash {
    #[must_use]
    pub fn new(len: usize) -> Self {
        // Factor in the number of active entries
        Self {
            hash: (len as u64 + 1).wrapping_mul(1927868237),
        }
    }

    pub fn add(&mut self, element_hash: PyHash) {
        // Work to increase the bit dispersion for closely spaced hash values.
        // This is important because some use cases have many combinations of a
        // small number of elements with nearby hashes so that many distinct
        // combinations collapse to only a handful of distinct hash values.
        const fn shuffle_bits(h: u64) -> u64 {
            ((h ^ 89869747) ^ (h.wrapping_shl(16))).wrapping_mul(3644798167)
        }
        // Xor-in shuffled bits from every entry's hash field because xor is
        // commutative and a frozenset hash should be independent of order.
        self.hash ^= shuffle_bits(element_hash as u64);
    }

    #[must_use]
    pub fn finish(self) -> PyHash {
        let mut hash = self.hash;
        // Disperse patterns arising in nested frozen-sets
        hash ^= (hash >> 11) ^ (hash >> 25);
        hash = hash.wrapping_mul(69069).wrapping_add(907133923);
        // -1 is reserved as an error code
        if hash == u64::MAX {
            hash = 590923713;
        }
        hash as PyHash
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn from_keys_is_stable_and_seed_independent() {
        const K0: u64 = 0x0706_0504_0302_0100;
        const K1: u64 = 0x0f0e_0d0c_0b0a_0908;
        const LOCKED_DIGEST: PyHash = -1862661396243998188;

        // Two secrets built from the same explicit keys hash identically, and
        // the digest does not depend on the seed-derivation path.
        let a = HashSecret::from_keys(K0, K1);
        let b = HashSecret::from_keys(K0, K1);
        assert_eq!(a.hash_str("hello"), b.hash_str("hello"));
        assert_eq!(
            a.hash_bytes(b"a fixed message"),
            b.hash_bytes(b"a fixed message")
        );

        // Explicit keys drive the SipHasher-2-4 directly. `keyed_hash` pins
        // k1 = 0, so a secret built with the same k0 and k1 = 0 must reproduce
        // its raw digest.
        let zero_k1 = HashSecret::from_keys(K0, 0);
        assert_eq!(keyed_hash(K0, b"payload"), zero_k1.hash_one(b"payload"));

        // Locked digest so an accidental keying change is caught.
        assert_eq!(a.hash_str("determinism"), LOCKED_DIGEST);
    }
}