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

// REF: https://github.com/python/cpython/blob/3.10/Lib/fractions.py#L637
//      https://github.com/python/cpython/blob/3.10/Python/pyhash.c#L92
//      https://docs.rs/num-rational/0.4.0/src/num_rational/lib.rs.html#394-408

use crate::NumHash;

use num_modular::ModularCoreOps;
use num_traits::Float;
use core::hash::{Hash, Hasher};

const P64: u64 = 0xFFFFFFFFFFFFFFC5; // largest prime under 2^64
const M61: i64 = 0x1FFFFFFFFFFFFFFF; // largest mersenne prime under 2^64
const HASH_INF: i64 = i64::MAX;

// Case1: directly hash the i64 and u64 number
impl NumHash for i64 {
    #[inline]
    fn num_hash<H: Hasher>(&self, state: &mut H) {
        (self % M61).hash(state)
    }
}
impl NumHash for u64 {
    #[inline]
    fn num_hash<H: Hasher>(&self, state: &mut H) {
        ((self % M61 as u64) as i64).hash(state)
    }
}

// Case2: convert other integers to 64 bit integer
macro_rules! impl_hash_for_small_sint {
    ($($signed:ty)*) => ($(
        impl NumHash for $signed {
            #[inline]
            fn num_hash<H: Hasher>(&self, state: &mut H) {
                (&(*self as i64)).num_hash(state)
            }
        }
    )*);
}
impl_hash_for_small_sint! { i8 i16 i32 isize }

macro_rules! impl_hash_for_small_uint {
    ($($unsigned:ty)*) => ($(
        impl NumHash for $unsigned {
            #[inline]
            fn num_hash<H: Hasher>(&self, state: &mut H) {
                (&(*self as u64)).num_hash(state)
            }
        }
    )*);
}
impl_hash_for_small_uint! { u8 u16 u32 usize }

impl NumHash for u128 {
    #[inline]
    fn num_hash<H: Hasher>(&self, state: &mut H) {
        ((self % M61 as u128) as i64).hash(state)
    }
}
impl NumHash for i128 {
    #[inline]
    fn num_hash<H: Hasher>(&self, state: &mut H) {
        ((self % M61 as i128) as i64).hash(state)
    }
}

// Case3: for rational(a, b), the hash is `hash(a * b^-1 mod M61)`
macro_rules! impl_hash_for_float {
    ($($float:ty)*) => ($(
        impl NumHash for $float {
            fn num_hash<H: Hasher>(&self, state: &mut H) {
                if self.is_nan() {
                    0i64.num_hash(state) // assign 0 to nan
                } else if self.is_infinite() {
                    if self.is_sign_positive() {
                        HASH_INF.num_hash(state)
                    } else {
                        (-HASH_INF).num_hash(state)
                    }
                } else {
                    let (mantissa, exp, sign) = self.integer_decode();
                    // m * 2^e mod M61 = m * 2^(e mod 61) mod M61
                    let exp = if exp > 0 { (exp as u64) % 61 } else { ModularCoreOps::<u64>::negm(&(-exp as u64), &61) };
                    let v = mantissa.mulm(1u64 << ((exp as u64) % 61), &(M61 as u64));
                    (v as i64 * sign as i64).hash(state);
                }
            }
        }
    )*);
}
impl_hash_for_float! { f32 f64 }

// Case4: for a + b*sqrt(r), the hash is `hash(a + P64*b^2*r)`