kbvm/
phf.rs

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
use core::num::Wrapping;

#[non_exhaustive]
pub(crate) struct Hashes {
    pub(crate) g: u32,
    pub(crate) f1: u32,
    pub(crate) f2: u32,
}

#[inline]
pub(crate) fn displace(f1: u32, f2: u32, d1: u32, d2: u32) -> u32 {
    (Wrapping(d2) + Wrapping(f1) * Wrapping(d1) + Wrapping(f2)).0
}

#[inline]
pub(crate) fn hash<T>(x: &T, key: u64) -> Hashes
where
    T: ?Sized + PhfHash,
{
    let (upper, lower) = x.phf_hash(key);
    Hashes {
        g: (lower >> 32) as u32,
        f1: lower as u32,
        f2: upper,
    }
}

#[inline]
#[allow(dead_code)]
pub(crate) fn get_unwrapped_index(hashes: &Hashes, disps: &[(u32, u32)]) -> usize {
    let (d1, d2) = disps[(hashes.g % (disps.len() as u32)) as usize];
    displace(hashes.f1, hashes.f2, d1, d2) as usize
}

pub(crate) trait PhfHash {
    fn phf_hash(&self, key: u64) -> (u32, u64);
}

impl<T> PhfHash for &'_ T
where
    T: ?Sized + PhfHash,
{
    #[inline]
    fn phf_hash(&self, key: u64) -> (u32, u64) {
        (**self).phf_hash(key)
    }
}

impl PhfHash for [u8] {
    #[inline]
    fn phf_hash(&self, key: u64) -> (u32, u64) {
        const A: u32 = 2024877429;
        const B: u64 = 17099814477566751079;
        let mut a = key as u32;
        let mut b = key;
        for &x in self {
            a = (a ^ x as u32).wrapping_mul(A);
            b = (b ^ x as u64).wrapping_mul(B);
        }
        (a, b)
    }
}

impl PhfHash for str {
    #[inline]
    fn phf_hash(&self, key: u64) -> (u32, u64) {
        self.as_bytes().phf_hash(key)
    }
}

impl PhfHash for u32 {
    #[inline]
    fn phf_hash(&self, key: u64) -> (u32, u64) {
        const A: u32 = 2024877429;
        const B: u64 = 17099814477566751079;
        let a = (key as u32 ^ *self).wrapping_mul(A);
        let b = (key ^ *self as u64).wrapping_mul(B);
        (a, b)
    }
}

impl PhfHash for char {
    #[inline]
    fn phf_hash(&self, key: u64) -> (u32, u64) {
        (*self as u32).phf_hash(key)
    }
}