agdb/utilities/
stable_hash.rs

1use std::ops::BitXor;
2
3const HASH_CONSTANT: u64 = 0x517cc1b727220a95;
4
5pub trait StableHash {
6    fn stable_hash(&self) -> u64;
7
8    fn add_to_hash(hash: &mut u64, value: u64) {
9        *hash = hash
10            .rotate_left(5)
11            .bitxor(value)
12            .wrapping_mul(HASH_CONSTANT);
13    }
14}
15
16impl StableHash for i64 {
17    fn stable_hash(&self) -> u64 {
18        *self as u64
19    }
20}
21
22impl StableHash for u64 {
23    fn stable_hash(&self) -> u64 {
24        *self
25    }
26}
27
28impl StableHash for String {
29    fn stable_hash(&self) -> u64 {
30        self.as_bytes().stable_hash()
31    }
32}
33
34impl StableHash for &[u8] {
35    fn stable_hash(&self) -> u64 {
36        const CHUNK_SIZE: usize = std::mem::size_of::<u64>();
37        let chunks = self.len() / CHUNK_SIZE;
38        let remainder = self.len() % CHUNK_SIZE;
39        let mut hash = 0_u64;
40
41        for chunk in 0..chunks {
42            let begin = chunk * CHUNK_SIZE;
43            let end = begin + CHUNK_SIZE;
44            let mut data = [0_u8; CHUNK_SIZE];
45            data.copy_from_slice(&self[begin..end]);
46            Self::add_to_hash(&mut hash, u64::from_le_bytes(data).stable_hash());
47        }
48
49        if remainder != 0 {
50            let begin = chunks * CHUNK_SIZE;
51            let end = begin + remainder;
52            let mut data = [0_u8; CHUNK_SIZE];
53            data[0..remainder].copy_from_slice(&self[begin..end]);
54            Self::add_to_hash(&mut hash, u64::from_le_bytes(data).stable_hash());
55        }
56
57        Self::add_to_hash(&mut hash, (self.len() as u64).stable_hash());
58
59        hash
60    }
61}
62
63impl StableHash for Vec<u8> {
64    fn stable_hash(&self) -> u64 {
65        self.as_slice().stable_hash()
66    }
67}
68
69impl<T: StableHash> StableHash for Vec<T> {
70    fn stable_hash(&self) -> u64 {
71        let mut hash = 0_u64;
72
73        for value in self {
74            Self::add_to_hash(&mut hash, value.stable_hash());
75        }
76
77        Self::add_to_hash(&mut hash, (self.len() as u64).stable_hash());
78
79        hash
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn i64() {
89        assert_eq!(10_i64.stable_hash(), 10_u64);
90    }
91
92    #[test]
93    fn u64() {
94        assert_eq!(10_u64.stable_hash(), 10_u64);
95    }
96
97    #[test]
98    fn string() {
99        assert_eq!("".to_string().stable_hash(), 0);
100
101        let string_hash = "Hello, World!".to_string().stable_hash();
102        let other_string_hash = "Hello".to_string().stable_hash();
103
104        assert_ne!(string_hash, 0);
105        assert_ne!(" ".to_string().stable_hash(), 0);
106        assert_ne!(string_hash, other_string_hash);
107        assert_eq!(string_hash, "Hello, World!".to_string().stable_hash());
108    }
109
110    #[test]
111    fn vec_u8() {
112        let vec_hash = vec![1_u8, 2_u8, 3_u8].stable_hash();
113        let other_vec_hash = vec![3_u8, 2_u8, 1_u8].stable_hash();
114
115        assert_ne!(vec_hash, 0);
116        assert_ne!(vec![0_u8].stable_hash(), 0);
117        assert_ne!(vec_hash, other_vec_hash);
118        assert_eq!(vec_hash, vec![1_u8, 2_u8, 3_u8].stable_hash());
119    }
120
121    #[test]
122    fn vec_64() {
123        let vec_hash = vec![1_u64, 2_u64, 3_u64].stable_hash();
124        let other_vec_hash = vec![1_i64, 2_i64, 3_i64].stable_hash();
125
126        assert_ne!(vec_hash, 0);
127        assert_ne!(vec![0_u64].stable_hash(), 0);
128        assert_eq!(vec_hash, other_vec_hash);
129        assert_eq!(vec_hash, vec![1_u64, 2_u64, 3_u64].stable_hash());
130    }
131}
agdb/utilities/stable_hash.rs

agdb/utilities/
stable_hash.rs
