ppvm_traits/traits/
hash.rs

1// SPDX-FileCopyrightText: 2026 The PPVM Authors
2// SPDX-License-Identifier: Apache-2.0
3
4//! Hashers for internal maps and cached Pauli-word hashes.
5
6use std::collections::HashMap;
7use std::hash::{BuildHasher, Hasher};
8
9/// Fast hasher for internal maps and word hashes, with a fixed seed.
10/// Iteration is reproducible for the same build and insertion order.
11pub type FoldBuildHasher = foldhash::fast::FixedState;
12
13/// A [`HashMap`] using [`FoldBuildHasher`].
14pub type FoldHashMap<K, V> = HashMap<K, V, FoldBuildHasher>;
15
16/// Computes and finalizes cached Pauli-word hashes.
17/// Custom hashers can use the defaults with an empty implementation.
18pub trait HashFinalize {
19    /// Hash a Pauli word given its bit arrays as byte slices (X, Z, and for
20    /// lossy words the loss bits), each `storage_bytes` long.
21    #[inline(always)]
22    fn word_hash(parts: &[&[u8]], storage_bytes: usize) -> u64
23    where
24        Self: BuildHasher + Default,
25    {
26        let mut hasher = Self::default().build_hasher();
27        for part in parts {
28            hasher.write(part);
29        }
30        Self::finalize_hash(hasher.finish(), storage_bytes)
31    }
32
33    /// Adjust the raw digest computed by the default
34    /// [`word_hash`](Self::word_hash). The default returns it unchanged.
35    #[inline(always)]
36    fn finalize_hash(raw: u64, _storage_bytes: usize) -> u64 {
37        raw
38    }
39}
40
41impl HashFinalize for fxhash::FxBuildHasher {
42    // FxHash can collapse distinct X/Z planes to the same digest; use foldhash
43    // for the word's cached hash while retaining FxHash for map lookup.
44    #[inline(always)]
45    fn word_hash(parts: &[&[u8]], _storage_bytes: usize) -> u64 {
46        let mut hasher = FoldBuildHasher::default().build_hasher();
47        for part in parts {
48            hasher.write(part);
49        }
50        hasher.finish()
51    }
52}
53
54#[cfg(all(
55    feature = "gxhash",
56    target_feature = "aes",
57    any(target_arch = "x86_64", target_arch = "aarch64")
58))]
59impl HashFinalize for gxhash::GxBuildHasher {}
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64    use std::collections::HashSet;
65
66    const KEYS: u64 = 1 << 14;
67
68    /// Distinct values among the low 16 bits, which a hash map uses as the bucket.
69    fn buckets(hashes: impl Iterator<Item = u64>) -> usize {
70        hashes.map(|h| h & 0xFFFF).collect::<HashSet<_>>().len()
71    }
72
73    #[test]
74    fn fold_build_hasher_spreads_high_bit_keys() {
75        let fold = FoldBuildHasher::default();
76        let usize_keys = (0..KEYS).map(|k| fold.hash_one((k as usize) << (usize::BITS - 14)));
77        let u128_keys = (0..KEYS).map(|k| fold.hash_one(u128::from(k) << 114));
78        assert!(buckets(usize_keys) > KEYS as usize / 2);
79        assert!(buckets(u128_keys) > KEYS as usize / 2);
80    }
81
82    // Every Pauli string on the top 7 qubits, hashed the way a map with FxHash
83    // sees a word: FxHash over the cached word hash.
84    #[test]
85    fn fxhash_word_hash_spreads_top_qubit_words() {
86        let fx = fxhash::FxBuildHasher::default();
87        for bytes in [8, 16, 64] {
88            let n_qubits = 8 * bytes;
89            let hashes = (0..KEYS).map(|code| {
90                let (mut x, mut z) = (vec![0u8; bytes], vec![0u8; bytes]);
91                for j in 0..7 {
92                    let (q, pauli) = (n_qubits - 7 + j, (code >> (2 * j)) & 3);
93                    x[q / 8] |= ((pauli & 1) as u8) << (q % 8);
94                    z[q / 8] |= ((pauli >> 1) as u8) << (q % 8);
95                }
96                let cached = <fxhash::FxBuildHasher as HashFinalize>::word_hash(&[&x, &z], bytes);
97                fx.hash_one(cached)
98            });
99            assert!(buckets(hashes) > KEYS as usize / 2, "{n_qubits} qubits");
100        }
101    }
102}
ppvm_traits/traits/hash.rs

ppvm_traits/traits/
hash.rs
