const BITS: u32 = 61;
const MODULUS: u64 = (1u64 << BITS) - 1;
const INF: i64 = 314159;
const IMAG: u64 = 1000003;
pub const NONE: i64 = 0xFCA8_6420;
fn avoid_minus_one(x: u64) -> i64 {
if x == u64::MAX {
-2
} else {
x as i64
}
}
pub fn int_i64(n: i64) -> i64 {
let magnitude = n.unsigned_abs() % MODULUS;
let signed = if n < 0 {
(magnitude as i64).wrapping_neg() as u64
} else {
magnitude
};
avoid_minus_one(signed)
}
pub fn int_big(b: &num_bigint::BigInt) -> i64 {
use num_traits::ToPrimitive;
let modulus = num_bigint::BigInt::from(MODULUS);
let magnitude = num_bigint::BigInt::from(b.magnitude().clone()) % &modulus;
let magnitude = magnitude.to_u64().unwrap_or(0);
let signed = if b.sign() == num_bigint::Sign::Minus {
(magnitude as i64).wrapping_neg() as u64
} else {
magnitude
};
avoid_minus_one(signed)
}
pub fn double(v: f64) -> Option<i64> {
if v.is_nan() {
return None;
}
if v.is_infinite() {
return Some(if v > 0.0 { INF } else { -INF });
}
let (mut m, mut e) = frexp(v);
let sign: i64 = if m < 0.0 {
m = -m;
-1
} else {
1
};
let mut x: u64 = 0;
while m != 0.0 {
x = ((x << 28) & MODULUS) | (x >> (BITS - 28));
m *= 268435456.0; e -= 28;
let y = m as u64; m -= y as f64;
x += y;
if x >= MODULUS {
x -= MODULUS;
}
}
let e = if e >= 0 {
(e % BITS as i32) as u32
} else {
BITS - 1 - ((-1 - e) % BITS as i32) as u32
};
x = ((x << e) & MODULUS) | (x >> (BITS - e));
let x = (x as i64).wrapping_mul(sign) as u64;
Some(avoid_minus_one(x))
}
fn frexp(v: f64) -> (f64, i32) {
if v == 0.0 || !v.is_finite() {
return (v, 0);
}
let bits = v.to_bits();
let raw_exp = ((bits >> 52) & 0x7ff) as i32;
if raw_exp == 0 {
let (m, e) = frexp(v * 9007199254740992.0); return (m, e - 53);
}
let mantissa = f64::from_bits((bits & !(0x7ffu64 << 52)) | (1022u64 << 52));
(mantissa, raw_exp - 1022)
}
pub fn complex(re: f64, im: f64) -> Option<i64> {
let hre = double(re)?;
let him = double(im)?;
let combined = (hre as u64).wrapping_add((him as u64).wrapping_mul(IMAG));
Some(avoid_minus_one(combined))
}
pub fn buffer(data: &[u8]) -> i64 {
let (k0, k1) = hash_secret();
buffer_keyed(k0, k1, data)
}
fn buffer_keyed(k0: u64, k1: u64, data: &[u8]) -> i64 {
if data.is_empty() {
return 0;
}
let x = siphash13(k0, k1, data);
if x == u64::MAX {
return -2;
}
x as i64
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HashSeed {
Fixed(u32),
Random,
}
pub fn parse_hash_seed(raw: Option<&str>) -> Option<HashSeed> {
let s = match raw {
None | Some("") => return Some(HashSeed::Random),
Some("random") => return Some(HashSeed::Random),
Some(s) => s,
};
let b = s.as_bytes();
let mut i = 0;
while i < b.len() && (b[i] as char).is_ascii_whitespace() {
i += 1;
}
let neg = match b.get(i) {
Some(b'-') => {
i += 1;
true
}
Some(b'+') => {
i += 1;
false
}
_ => false,
};
let digits_start = i;
let mut n: u64 = 0;
while i < b.len() && b[i].is_ascii_digit() {
n = n.saturating_mul(10).saturating_add((b[i] - b'0') as u64);
i += 1;
}
if i == digits_start || i != b.len() {
return None;
}
let n = if neg { 0u64.wrapping_sub(n) } else { n };
if n > 4_294_967_295 {
return None;
}
Some(HashSeed::Fixed(n as u32))
}
fn lcg_urandom(x0: u32, out: &mut [u8]) {
let mut x = x0;
for slot in out.iter_mut() {
x = x.wrapping_mul(214013);
x = x.wrapping_add(2531011);
*slot = ((x >> 16) & 0xff) as u8;
}
}
pub fn hash_secret() -> (u64, u64) {
static SECRET: std::sync::OnceLock<(u64, u64)> = std::sync::OnceLock::new();
*SECRET.get_or_init(|| {
let seed = std::env::var("PYTHONHASHSEED").ok();
match parse_hash_seed(seed.as_deref()) {
Some(HashSeed::Fixed(n)) => secret_for(n),
None => secret_for(0),
Some(HashSeed::Random) => random_secret(),
}
})
}
fn secret_for(seed: u32) -> (u64, u64) {
if seed == 0 {
return (0, 0);
}
let mut secret = [0u8; 24];
lcg_urandom(seed, &mut secret);
(
u64::from_le_bytes(secret[0..8].try_into().unwrap()),
u64::from_le_bytes(secret[8..16].try_into().unwrap()),
)
}
fn random_secret() -> (u64, u64) {
use std::hash::{BuildHasher, Hasher};
let state = std::collections::hash_map::RandomState::new();
let mut a = state.build_hasher();
a.write_u8(0);
let mut b = state.build_hasher();
b.write_u8(1);
(a.finish(), b.finish())
}
fn siphash13(k0: u64, k1: u64, src: &[u8]) -> u64 {
fn half_round(a: &mut u64, b: &mut u64, c: &mut u64, d: &mut u64, s: u32, t: u32) {
*a = a.wrapping_add(*b);
*c = c.wrapping_add(*d);
*b = b.rotate_left(s) ^ *a;
*d = d.rotate_left(t) ^ *c;
*a = a.rotate_left(32);
}
fn single_round(v0: &mut u64, v1: &mut u64, v2: &mut u64, v3: &mut u64) {
half_round(v0, v1, v2, v3, 13, 16);
half_round(v2, v1, v0, v3, 17, 21);
}
let mut b: u64 = (src.len() as u64) << 56;
let mut v0 = k0 ^ 0x736f6d6570736575;
let mut v1 = k1 ^ 0x646f72616e646f6d;
let mut v2 = k0 ^ 0x6c7967656e657261;
let mut v3 = k1 ^ 0x7465646279746573;
let mut chunks = src.chunks_exact(8);
for chunk in &mut chunks {
let mi = u64::from_le_bytes(chunk.try_into().unwrap());
v3 ^= mi;
single_round(&mut v0, &mut v1, &mut v2, &mut v3);
v0 ^= mi;
}
let mut t = [0u8; 8];
let rest = chunks.remainder();
t[..rest.len()].copy_from_slice(rest);
b |= u64::from_le_bytes(t);
v3 ^= b;
single_round(&mut v0, &mut v1, &mut v2, &mut v3);
v0 ^= b;
v2 ^= 0xff;
single_round(&mut v0, &mut v1, &mut v2, &mut v3);
single_round(&mut v0, &mut v1, &mut v2, &mut v3);
single_round(&mut v0, &mut v1, &mut v2, &mut v3);
(v0 ^ v1) ^ (v2 ^ v3)
}
pub fn string(s: &str) -> i64 {
buffer(&ucs_units(s))
}
fn ucs_units(s: &str) -> Vec<u8> {
let max = s.chars().map(|c| c as u32).max().unwrap_or(0);
if max < 0x100 {
s.chars().map(|c| c as u8).collect()
} else if max < 0x10000 {
s.chars().flat_map(|c| (c as u16).to_le_bytes()).collect()
} else {
s.chars().flat_map(|c| (c as u32).to_le_bytes()).collect()
}
}
pub fn tuple(element_hashes: &[i64]) -> i64 {
const XXPRIME_1: u64 = 11400714785074694791;
const XXPRIME_2: u64 = 14029467366897019727;
const XXPRIME_5: u64 = 2870177450012600261;
let mut acc: u64 = XXPRIME_5;
for &lane in element_hashes {
acc = acc.wrapping_add((lane as u64).wrapping_mul(XXPRIME_2));
acc = acc.rotate_left(31);
acc = acc.wrapping_mul(XXPRIME_1);
}
acc = acc.wrapping_add((element_hashes.len() as u64) ^ (XXPRIME_5 ^ 3527539));
if acc == u64::MAX {
return 1546275796;
}
acc as i64
}
pub fn slice(bound_hashes: &[i64; 3]) -> i64 {
const XXPRIME_1: u64 = 11400714785074694791;
const XXPRIME_2: u64 = 14029467366897019727;
const XXPRIME_5: u64 = 2870177450012600261;
let mut acc: u64 = XXPRIME_5;
for &lane in bound_hashes {
acc = acc.wrapping_add((lane as u64).wrapping_mul(XXPRIME_2));
acc = acc.rotate_left(31);
acc = acc.wrapping_mul(XXPRIME_1);
}
if acc == u64::MAX {
return 1546275796;
}
acc as i64
}
pub fn frozenset(element_hashes: &[i64]) -> i64 {
fn shuffle_bits(h: u64) -> u64 {
((h ^ 89869747) ^ (h << 16)).wrapping_mul(3644798167)
}
let mut hash: u64 = 0;
for &h in element_hashes {
hash ^= shuffle_bits(h as u64);
}
hash ^= ((element_hashes.len() as u64).wrapping_add(1)).wrapping_mul(1927868237);
hash ^= (hash >> 11) ^ (hash >> 25);
hash = hash.wrapping_mul(69069).wrapping_add(907133923);
if hash == u64::MAX {
return 590923713;
}
hash as i64
}
#[cfg(test)]
mod tests {
use super::*;
fn string0(s: &str) -> i64 {
buffer_keyed(0, 0, &ucs_units(s))
}
fn buffer0(b: &[u8]) -> i64 {
buffer_keyed(0, 0, b)
}
#[test]
fn matches_cpython_integers() {
assert_eq!(int_i64(0), 0);
assert_eq!(int_i64(1), 1);
assert_eq!(int_i64(7), 7);
assert_eq!(int_i64(-7), -7);
assert_eq!(int_i64(-1), -2);
assert_eq!(int_i64(-2), -2);
assert_eq!(int_i64(2305843009213693951), 0); assert_eq!(int_i64(2305843009213693952), 1); assert_eq!(int_i64(4611686018427387904), 2); assert_eq!(int_i64(-2305843009213693951), 0);
assert_eq!(int_i64(-2305843009213693952), -2); assert_eq!(int_i64(-4611686018427387904), -2);
assert_eq!(int_i64(i64::MIN), -4);
}
#[test]
fn matches_cpython_bignums() {
let p = |s: &str| -> num_bigint::BigInt { s.parse().unwrap() };
assert_eq!(int_big(&p("18446744073709551616")), 8);
assert_eq!(int_big(&p("-18446744073709551616")), -8);
assert_eq!(int_big(&p("1180591620717411315769")), 12857); assert_eq!(int_big(&p("-1180591620717411315769")), -12857);
assert_eq!(
int_big(&p("1000000000000000000000000000000")),
465258685558744706
);
}
#[test]
fn matches_cpython_floats() {
assert_eq!(double(0.0), Some(0));
assert_eq!(double(-0.0), Some(0));
assert_eq!(double(1.0), Some(1));
assert_eq!(double(-1.0), Some(-2)); assert_eq!(double(2.5), Some(1152921504606846978));
assert_eq!(double(0.5), Some(1152921504606846976));
assert_eq!(double(-0.5), Some(-1152921504606846976));
assert_eq!(double(3.15), Some(345876451382053891));
assert_eq!(double(0.1), Some(230584300921369408));
assert_eq!(double(1e300), Some(1224995262755759164));
assert_eq!(double(-1e300), Some(-1224995262755759164));
assert_eq!(double(f64::INFINITY), Some(314159));
assert_eq!(double(f64::NEG_INFINITY), Some(-314159));
assert_eq!(double(f64::NAN), None);
assert_eq!(double(5e-324), Some(16777216));
}
#[test]
fn numeric_tower_agrees_across_types() {
assert_eq!(double(1.0).unwrap(), int_i64(1));
assert_eq!(double(2.0).unwrap(), int_i64(2));
assert_eq!(double(-3.0).unwrap(), int_i64(-3));
assert_eq!(double(0.0).unwrap(), int_i64(0));
assert_eq!(complex(1.0, 0.0).unwrap(), int_i64(1));
assert_eq!(
double(9007199254740992.0).unwrap(),
int_i64(9007199254740992)
);
}
#[test]
fn matches_cpython_complex() {
assert_eq!(complex(1.0, 2.0), Some(2000007));
assert_eq!(complex(0.0, 1.0), Some(1000003));
assert_eq!(complex(3.0, -4.0), Some(-4000009));
assert_eq!(complex(2.5, -0.5), Some(-2305843009213693950));
}
#[test]
fn matches_cpython_str_and_bytes() {
assert_eq!(string0(""), 0);
assert_eq!(buffer0(b""), 0);
assert_eq!(string0("a"), 4644417185603328019);
assert_eq!(buffer0(b"a"), 4644417185603328019);
assert_eq!(string0("abc"), -4594863902769663758);
assert_eq!(buffer0(b"abc"), -4594863902769663758);
assert_eq!(string0("hello world"), -5642461784034726774);
assert_eq!(string0("\u{e9}"), 6047309291227476195);
assert_eq!(string0("\u{65e5}"), -2037161330753641417);
assert_eq!(string0("\u{1f600}"), -3536540696076613844);
assert_eq!(string(""), 0);
assert_eq!(buffer(b""), 0);
}
#[test]
fn matches_cpython_tuple() {
assert_eq!(tuple(&[]), 5740354900026072187);
assert_eq!(tuple(&[int_i64(1)]), -6644214454873602895);
assert_eq!(tuple(&[int_i64(1), int_i64(2)]), -3550055125485641917);
assert_eq!(
tuple(&[int_i64(1), int_i64(2), int_i64(3)]),
529344067295497451
);
assert_eq!(
tuple(&[int_i64(0), int_i64(0), int_i64(0)]),
3010437511937009226
);
assert_eq!(tuple(&[string0("a")]), 7319529274390396360);
assert_eq!(
tuple(&[int_i64(1), tuple(&[int_i64(2), int_i64(3)])]),
7267574591690527098
);
}
#[test]
fn matches_cpython_frozenset() {
assert_eq!(frozenset(&[]), 133146708735736);
assert_eq!(frozenset(&[int_i64(1)]), -558064481276695278);
assert_eq!(frozenset(&[int_i64(1), int_i64(2)]), -1826646154956904602);
assert_eq!(
frozenset(&[int_i64(1), int_i64(2), int_i64(3)]),
-272375401224217160
);
assert_eq!(frozenset(&[string0("a")]), -7857795138424989601);
}
#[test]
fn frozenset_hash_is_order_independent() {
let a = frozenset(&[int_i64(1), int_i64(2), int_i64(3)]);
let b = frozenset(&[int_i64(3), int_i64(1), int_i64(2)]);
let c = frozenset(&[int_i64(2), int_i64(3), int_i64(1)]);
assert_eq!(a, b);
assert_eq!(b, c);
}
#[test]
fn parses_hash_seed_like_cpython() {
use HashSeed::*;
assert_eq!(parse_hash_seed(None), Some(Random));
assert_eq!(parse_hash_seed(Some("")), Some(Random));
assert_eq!(parse_hash_seed(Some("random")), Some(Random));
assert_eq!(parse_hash_seed(Some("0")), Some(Fixed(0)));
assert_eq!(parse_hash_seed(Some("42")), Some(Fixed(42)));
assert_eq!(parse_hash_seed(Some(" 42")), Some(Fixed(42)));
assert_eq!(parse_hash_seed(Some("\t42")), Some(Fixed(42)));
assert_eq!(parse_hash_seed(Some("007")), Some(Fixed(7)));
assert_eq!(parse_hash_seed(Some("+7")), Some(Fixed(7)));
assert_eq!(parse_hash_seed(Some("-0")), Some(Fixed(0)));
assert_eq!(parse_hash_seed(Some("4294967295")), Some(Fixed(4294967295)));
assert_eq!(parse_hash_seed(Some("42 ")), None);
assert_eq!(parse_hash_seed(Some(" 42 ")), None);
assert_eq!(parse_hash_seed(Some(" ")), None);
assert_eq!(parse_hash_seed(Some("abc")), None);
assert_eq!(parse_hash_seed(Some("42abc")), None);
assert_eq!(parse_hash_seed(Some("1e3")), None);
assert_eq!(parse_hash_seed(Some("0x10")), None);
assert_eq!(parse_hash_seed(Some("-1")), None);
assert_eq!(parse_hash_seed(Some("4294967296")), None);
}
#[test]
fn matches_cpython_str_hash_under_every_pinned_seed() {
let cases: [(u32, i64, i64); 6] = [
(0, -4594863902769663758, 9013747392277146282),
(1, -4667308735975688587, -5634034666027049350),
(2, 4069345407874332860, 2105905292856817549),
(42, 3869580338025362921, -4491887112347156947),
(123456, -1666233593715650805, 4052602468391041882),
(4294967295, -6122489556238538401, 2562532176708456890),
];
for (seed, abc, xyz) in cases {
let (k0, k1) = secret_for(seed);
assert_eq!(buffer_keyed(k0, k1, b"abc"), abc, "hash('abc') @ {seed}");
assert_eq!(buffer_keyed(k0, k1, b"xyz"), xyz, "hash(b'xyz') @ {seed}");
assert_eq!(buffer_keyed(k0, k1, b""), 0, "hash('') @ {seed}");
}
}
#[test]
fn seed_zero_is_the_zero_key_not_the_lcg_of_zero() {
assert_eq!(secret_for(0), (0, 0));
let mut lcg_of_zero = [0u8; 24];
lcg_urandom(0, &mut lcg_of_zero);
assert_ne!(lcg_of_zero, [0u8; 24]);
}
#[test]
fn never_returns_minus_one() {
assert_ne!(int_i64(-1), -1);
assert_ne!(double(-1.0).unwrap(), -1);
assert_ne!(int_big(&"-1".parse::<num_bigint::BigInt>().unwrap()), -1);
for n in -600i64..600 {
assert_ne!(int_i64(n), -1, "int_i64({n})");
}
}
}