rucc_base/
hash.rs

1//! A hasher for the maps the compiler keys by its own small numbers.
2//!
3//! The standard library hashes with SipHash, which is built to stand up to somebody choosing keys
4//! that collide. A register, a value or an instruction is a small number the compiler handed out
5//! itself, so there is nobody choosing them, and on jtckdint's `test.c` hashing them with SipHash
6//! was more than a percent of the build in more than one pass. [`Mix`] does one rotate, one
7//! exclusive or and one multiply per word instead.
8//!
9//! Nothing may read the order of a map hashed with this any more than one hashed with SipHash.
10//! The order is fixed for a given set of keys, but it is a fact about the hash and not about the
11//! input, and `spec/02-the-goal.md` asks for output that only depends on the input.
12
13use std::collections::{HashMap, HashSet};
14use std::hash::{BuildHasherDefault, Hasher};
15
16/// A map hashed with [`Mix`].
17pub type Map<K, V> = HashMap<K, V, BuildHasherDefault<Mix>>;
18
19/// A set hashed with [`Mix`].
20pub type Set<T> = HashSet<T, BuildHasherDefault<Mix>>;
21
22/// Hashes a word at a time, with a rotate, an exclusive or and a multiply for each.
23///
24/// The multiply spreads each word over the high bits, which are the ones the table reads. Bytes
25/// are taken eight at a time, so a name costs one step per eight bytes of it.
26#[derive(Debug, Default, Clone, Copy)]
27pub struct Mix(u64);
28
29impl Mix {
30    fn mix(&mut self, word: u64) {
31        self.0 = (self.0.rotate_left(5) ^ word).wrapping_mul(0x9e37_79b9_7f4a_7c15);
32    }
33}
34
35impl Hasher for Mix {
36    fn finish(&self) -> u64 {
37        self.0
38    }
39
40    fn write(&mut self, bytes: &[u8]) {
41        for chunk in bytes.chunks(8) {
42            let mut word = [0; 8];
43            word[..chunk.len()].copy_from_slice(chunk);
44            self.mix(u64::from_le_bytes(word));
45        }
46    }
47
48    fn write_u8(&mut self, byte: u8) {
49        self.mix(u64::from(byte));
50    }
51
52    fn write_u16(&mut self, half: u16) {
53        self.mix(u64::from(half));
54    }
55
56    fn write_u32(&mut self, word: u32) {
57        self.mix(u64::from(word));
58    }
59
60    fn write_u64(&mut self, word: u64) {
61        self.mix(word);
62    }
63
64    fn write_usize(&mut self, word: usize) {
65        self.mix(word as u64);
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use std::hash::{BuildHasher, BuildHasherDefault};
72
73    use super::{Map, Mix, Set};
74
75    /// The same key hashes the same way every time, and a map and a set built with it find what
76    /// was put in them.
77    #[test]
78    fn a_key_hashes_the_same_way_every_time_and_is_found_again() {
79        let build = BuildHasherDefault::<Mix>::default();
80        assert_eq!(build.hash_one((3u8, 17u32)), build.hash_one((3u8, 17u32)));
81        assert_ne!(build.hash_one(1u32), build.hash_one(2u32));
82        assert_ne!(build.hash_one("add.i32"), build.hash_one("add.i64"));
83
84        let mut map: Map<u32, usize> = Map::default();
85        let mut set: Set<&str> = Set::default();
86        for number in 0..1000 {
87            map.insert(number * 7, number as usize);
88        }
89        for name in ["mov", "movzx", "movsx", "lea", "a name longer than eight bytes"] {
90            set.insert(name);
91        }
92        assert!((0..1000).all(|number| map[&(number * 7)] == number as usize));
93        assert_eq!(map.get(&1), None);
94        assert!(set.contains("a name longer than eight bytes"));
95        assert!(!set.contains("a name longer than eight byte"));
96    }
97}
rucc_base/hash.rs

rucc_base/
hash.rs
