jdc_core/
fx.rs

1//! A fast, non-cryptographic hasher for compiler-internal maps keyed by
2//! block/variable indices (the rustc "FxHash" scheme).
3//!
4//! The decompiler builds and probes millions of tiny `HashSet<usize>` /
5//! `HashMap<usize, _>` universes per run (dominators, RPO, region walks).
6//! SipHash-1-3 (std default) costs ~15-20ns per probe; the rotate-xor-
7//! multiply mix below costs ~1ns and is what rustc itself uses for
8//! exactly this key shape. NOT for adversarial-input-facing tables.
9
10use std::hash::{BuildHasherDefault, Hasher};
11
12#[cfg(target_pointer_width = "64")]
13const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;
14#[cfg(target_pointer_width = "32")]
15const SEED: u64 = 0x9e_37_79_b9;
16
17#[derive(Default, Clone, Copy, Debug)]
18pub struct FxHasher {
19    hash: u64,
20}
21
22impl FxHasher {
23    #[inline]
24    fn add(&mut self, word: u64) {
25        self.hash = (self.hash.rotate_left(5) ^ word).wrapping_mul(SEED);
26    }
27}
28
29impl Hasher for FxHasher {
30    #[inline]
31    fn write(&mut self, bytes: &[u8]) {
32        let mut b = bytes;
33        while b.len() >= 8 {
34            let mut buf = [0u8; 8];
35            buf.copy_from_slice(&b[..8]);
36            self.add(u64::from_le_bytes(buf));
37            b = &b[8..];
38        }
39        if b.len() >= 4 {
40            let mut buf = [0u8; 4];
41            buf.copy_from_slice(&b[..4]);
42            self.add(u32::from_le_bytes(buf) as u64);
43            b = &b[4..];
44        }
45        for &byte in b {
46            self.add(byte as u64);
47        }
48    }
49    #[inline]
50    fn write_u8(&mut self, i: u8) {
51        self.add(i as u64);
52    }
53    #[inline]
54    fn write_u16(&mut self, i: u16) {
55        self.add(i as u64);
56    }
57    #[inline]
58    fn write_u32(&mut self, i: u32) {
59        self.add(i as u64);
60    }
61    #[inline]
62    fn write_u64(&mut self, i: u64) {
63        self.add(i);
64    }
65    #[inline]
66    fn write_usize(&mut self, i: usize) {
67        self.add(i as u64);
68    }
69    #[inline]
70    fn finish(&self) -> u64 {
71        self.hash
72    }
73}
74
75pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
76pub type FxHashMap<K, V> = std::collections::HashMap<K, V, FxBuildHasher>;
77pub type FxHashSet<T> = std::collections::HashSet<T, FxBuildHasher>;
jdc_core/fx.rs

jdc_core/
fx.rs
