forked from RustPython/RustPython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpyhash.rs
More file actions
92 lines (80 loc) · 2.43 KB
/
pyhash.rs
File metadata and controls
92 lines (80 loc) · 2.43 KB
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
use num_bigint::BigInt;
use num_traits::ToPrimitive;
use std::hash::{Hash, Hasher};
use crate::obj::objfloat;
use crate::pyobject::PyObjectRef;
use crate::pyobject::PyResult;
use crate::vm::VirtualMachine;
pub type PyHash = i64;
pub type PyUHash = u64;
/// 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 CUTOFF: usize = 7;
pub fn hash_float(value: f64) -> PyHash {
// cpython _Py_HashDouble
if !value.is_finite() {
return if value.is_infinite() {
if value > 0.0 {
INF
} else {
-INF
}
} else {
NAN
};
}
let frexp = objfloat::ufrexp(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;
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);
x as PyHash * value.signum() as PyHash
}
pub fn hash_value<T: Hash>(data: &T) -> PyHash {
let mut hasher = std::collections::hash_map::DefaultHasher::new();
data.hash(&mut hasher);
hasher.finish() as PyHash
}
pub fn hash_iter<'a, I: std::iter::Iterator<Item = &'a PyObjectRef>>(
iter: I,
vm: &VirtualMachine,
) -> PyResult<PyHash> {
let mut hasher = std::collections::hash_map::DefaultHasher::new();
for element in iter {
let item_hash = vm._hash(&element)?;
item_hash.hash(&mut hasher);
}
Ok(hasher.finish() as PyHash)
}
pub fn hash_bigint(value: &BigInt) -> PyHash {
match value.to_i64() {
Some(i64_value) => (i64_value % MODULUS as i64),
None => (value % MODULUS).to_i64().unwrap(),
}
}