grit_lib/
bloom.rs

1//! Changed-path Bloom filters for commit-graph files (Git `bloom.c` compatible).
2
3use std::collections::BTreeSet;
4use thiserror::Error;
5
6/// Settings stored in the BDAT chunk header and used for hashing.
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub struct BloomFilterSettings {
9    /// `hash_version` field.
10    pub hash_version: u32,
11    /// `num_hashes` field.
12    pub num_hashes: u32,
13    /// `bits_per_entry` field.
14    pub bits_per_entry: u32,
15    /// `max_changed_paths` field.
16    pub max_changed_paths: u32,
17}
18
19impl Default for BloomFilterSettings {
20    fn default() -> Self {
21        Self {
22            hash_version: 1,
23            num_hashes: 7,
24            bits_per_entry: 10,
25            max_changed_paths: 512,
26        }
27    }
28}
29
30const BITS_PER_WORD: u64 = 8;
31/// `BLOOMDATA_HEADER_LEN` constant.
32pub const BLOOMDATA_HEADER_LEN: usize = 12;
33
34#[inline]
35fn rotate_left(value: u32, count: u32) -> u32 {
36    value.rotate_left(count)
37}
38
39#[inline]
40fn signed_char_u32(b: u8) -> u32 {
41    ((b as i8) as i32) as u32
42}
43
44fn murmur3_seeded_v2(mut seed: u32, data: &[u8]) -> u32 {
45    let c1: u32 = 0xcc9e2d51;
46    let c2: u32 = 0x1b873593;
47    let r1: u32 = 15;
48    let r2: u32 = 13;
49    let m: u32 = 5;
50    let n: u32 = 0xe6546b64;
51
52    let mut i = 0usize;
53    while i + 4 <= data.len() {
54        let mut k = (data[i] as u32)
55            | ((data[i + 1] as u32) << 8)
56            | ((data[i + 2] as u32) << 16)
57            | ((data[i + 3] as u32) << 24);
58        k = k.wrapping_mul(c1);
59        k = rotate_left(k, r1);
60        k = k.wrapping_mul(c2);
61        seed ^= k;
62        seed = rotate_left(seed, r2).wrapping_mul(m).wrapping_add(n);
63        i += 4;
64    }
65
66    let tail = &data[i..];
67    let mut k1: u32 = 0;
68    match tail.len() {
69        3 => {
70            k1 ^= (tail[2] as u32) << 16;
71            k1 ^= (tail[1] as u32) << 8;
72            k1 ^= tail[0] as u32;
73        }
74        2 => {
75            k1 ^= (tail[1] as u32) << 8;
76            k1 ^= tail[0] as u32;
77        }
78        1 => {
79            k1 ^= tail[0] as u32;
80        }
81        _ => {}
82    }
83    if !tail.is_empty() {
84        k1 = k1.wrapping_mul(c1);
85        k1 = rotate_left(k1, r1);
86        k1 = k1.wrapping_mul(c2);
87        seed ^= k1;
88    }
89
90    seed ^= data.len() as u32;
91    seed ^= seed >> 16;
92    seed = seed.wrapping_mul(0x85ebca6b);
93    seed ^= seed >> 13;
94    seed = seed.wrapping_mul(0xc2b2ae35);
95    seed ^= seed >> 16;
96    seed
97}
98
99fn murmur3_seeded_v1(mut seed: u32, data: &[u8]) -> u32 {
100    let c1: u32 = 0xcc9e2d51;
101    let c2: u32 = 0x1b873593;
102    let r1: u32 = 15;
103    let r2: u32 = 13;
104    let m: u32 = 5;
105    let n: u32 = 0xe6546b64;
106
107    let mut i = 0usize;
108    while i + 4 <= data.len() {
109        let mut k = signed_char_u32(data[i])
110            | (signed_char_u32(data[i + 1]) << 8)
111            | (signed_char_u32(data[i + 2]) << 16)
112            | (signed_char_u32(data[i + 3]) << 24);
113        k = k.wrapping_mul(c1);
114        k = rotate_left(k, r1);
115        k = k.wrapping_mul(c2);
116        seed ^= k;
117        seed = rotate_left(seed, r2).wrapping_mul(m).wrapping_add(n);
118        i += 4;
119    }
120
121    let tail = &data[i..];
122    let mut k1: u32 = 0;
123    match tail.len() {
124        3 => {
125            k1 ^= signed_char_u32(tail[2]) << 16;
126            k1 ^= signed_char_u32(tail[1]) << 8;
127            k1 ^= signed_char_u32(tail[0]);
128        }
129        2 => {
130            k1 ^= signed_char_u32(tail[1]) << 8;
131            k1 ^= signed_char_u32(tail[0]);
132        }
133        1 => {
134            k1 ^= signed_char_u32(tail[0]);
135        }
136        _ => {}
137    }
138    if !tail.is_empty() {
139        k1 = k1.wrapping_mul(c1);
140        k1 = rotate_left(k1, r1);
141        k1 = k1.wrapping_mul(c2);
142        seed ^= k1;
143    }
144
145    seed ^= data.len() as u32;
146    seed ^= seed >> 16;
147    seed = seed.wrapping_mul(0x85ebca6b);
148    seed ^= seed >> 13;
149    seed = seed.wrapping_mul(0xc2b2ae35);
150    seed ^= seed >> 16;
151    seed
152}
153
154fn murmur3_seeded(seed: u32, data: &[u8], hash_version: u32) -> u32 {
155    match hash_version {
156        2 => murmur3_seeded_v2(seed, data),
157        _ => murmur3_seeded_v1(seed, data),
158    }
159}
160
161/// Hash values for one path string (same length as `settings.num_hashes`).
162pub fn bloom_key_hashes(data: &[u8], settings: &BloomFilterSettings) -> Vec<u32> {
163    let seed0 = 0x293ae76f_u32;
164    let seed1 = 0x7e646e2c_u32;
165    let hash0 = murmur3_seeded(seed0, data, settings.hash_version);
166    let hash1 = murmur3_seeded(seed1, data, settings.hash_version);
167    let n = settings.num_hashes as usize;
168    let mut out = Vec::with_capacity(n);
169    for i in 0..n {
170        out.push(hash0.wrapping_add((i as u32).wrapping_mul(hash1)));
171    }
172    out
173}
174
175#[inline]
176fn get_bitmask(pos: u32) -> u8 {
177    1u8 << (pos & (BITS_PER_WORD as u32 - 1))
178}
179
180fn add_key_to_filter(key: &[u32], filter: &mut [u8], settings: &BloomFilterSettings) {
181    let mod_bits = (filter.len() as u64).saturating_mul(BITS_PER_WORD);
182    if mod_bits == 0 {
183        return;
184    }
185    for i in 0..settings.num_hashes as usize {
186        let Some(&h) = key.get(i) else {
187            break;
188        };
189        let hash_mod = (h as u64) % mod_bits;
190        let block_pos = (hash_mod / BITS_PER_WORD) as usize;
191        let bitmask = get_bitmask(hash_mod as u32);
192        if let Some(byte) = filter.get_mut(block_pos) {
193            *byte |= bitmask;
194        }
195    }
196}
197
198/// Invalid or missing Bloom filter data (zero-length filter, etc.).
199#[derive(Copy, Clone, Debug, Eq, PartialEq, Error)]
200#[error("invalid or empty Bloom filter")]
201pub struct BloomFilterInvalid;
202
203/// Returns `Ok(true)` if all bits for every key are set, `Ok(false)` if definitely not,
204/// `Err(BloomFilterInvalid)` if the filter has zero length (missing / invalid).
205pub fn bloom_filter_contains(
206    key: &[u32],
207    filter: &[u8],
208    settings: &BloomFilterSettings,
209) -> Result<bool, BloomFilterInvalid> {
210    let mod_bits = (filter.len() as u64).saturating_mul(BITS_PER_WORD);
211    if mod_bits == 0 {
212        return Err(BloomFilterInvalid);
213    }
214    for i in 0..settings.num_hashes as usize {
215        let Some(&h) = key.get(i) else {
216            return Err(BloomFilterInvalid);
217        };
218        let hash_mod = (h as u64) % mod_bits;
219        let block_pos = (hash_mod / BITS_PER_WORD) as usize;
220        let bitmask = get_bitmask(hash_mod as u32);
221        let Some(byte) = filter.get(block_pos) else {
222            return Err(BloomFilterInvalid);
223        };
224        if *byte & bitmask == 0 {
225            return Ok(false);
226        }
227    }
228    Ok(true)
229}
230
231/// Build keys for `path` and every directory prefix (Git `bloom_keyvec_new`).
232pub fn bloom_keyvec_for_path(path: &str, settings: &BloomFilterSettings) -> Vec<Vec<u32>> {
233    bloom_keyvec_for_bytes(path.as_bytes(), settings)
234}
235
236/// Build keys from raw Git path bytes, including every directory prefix.
237pub(crate) fn bloom_keyvec_for_bytes(
238    bytes: &[u8],
239    settings: &BloomFilterSettings,
240) -> Vec<Vec<u32>> {
241    if bytes.is_empty() {
242        return Vec::new();
243    }
244    let mut out = Vec::new();
245    out.push(bloom_key_hashes(bytes, settings));
246    let mut end = bytes.len();
247    while end > 0 {
248        let Some(pos) = bytes[..end].iter().rposition(|&b| b == b'/') else {
249            break;
250        };
251        if pos == 0 {
252            break;
253        }
254        out.push(bloom_key_hashes(&bytes[..pos], settings));
255        end = pos;
256    }
257    out
258}
259
260/// Every distinct path and parent directory for diff paths (Git `pathmap` order doesn't matter).
261pub fn collect_changed_paths_for_bloom(paths: &[String]) -> BTreeSet<String> {
262    let mut set = BTreeSet::new();
263    for p in paths {
264        let mut cur = p.clone();
265        loop {
266            set.insert(cur.clone());
267            let Some(pos) = cur.rfind('/') else {
268                break;
269            };
270            cur.truncate(pos);
271            if cur.is_empty() {
272                break;
273            }
274        }
275    }
276    set
277}
278
279/// Result of building a Bloom filter payload for one commit.
280#[derive(Debug, Clone, Copy, PartialEq, Eq)]
281pub enum BloomBuildOutcome {
282    /// `Normal` variant.
283    Normal,
284    /// `TruncatedLarge` variant.
285    TruncatedLarge,
286    /// `TruncatedEmpty` variant.
287    TruncatedEmpty,
288}
289
290/// Compute on-disk filter bytes for a commit's changed paths.
291///
292/// `raw_diff_entries` is the diff queue length before path de-duplication (Git `diff_queued_diff.nr`).
293pub fn build_bloom_filter_data(
294    changed_paths: &BTreeSet<String>,
295    raw_diff_entries: usize,
296    settings: &BloomFilterSettings,
297) -> (Vec<u8>, BloomBuildOutcome) {
298    let max = settings.max_changed_paths as usize;
299    if raw_diff_entries > max || changed_paths.len() > max {
300        return (vec![0xff], BloomBuildOutcome::TruncatedLarge);
301    }
302    let n_unique = changed_paths.len();
303    let bits_total = n_unique.saturating_mul(settings.bits_per_entry as usize);
304    let mut word_len = bits_total.div_ceil(8);
305    if word_len == 0 {
306        word_len = 1;
307    }
308    let outcome = if n_unique == 0 {
309        BloomBuildOutcome::TruncatedEmpty
310    } else {
311        BloomBuildOutcome::Normal
312    };
313    let mut data = vec![0u8; word_len];
314    for p in changed_paths {
315        let hashes = bloom_key_hashes(p.as_bytes(), settings);
316        add_key_to_filter(&hashes, &mut data, settings);
317    }
318    (data, outcome)
319}
320
321#[cfg(test)]
322mod tests {
323    use super::*;
324
325    #[test]
326    fn bloom_v1_and_v2_differ_on_high_bit_path_bytes() {
327        let path = "\u{0080}name";
328        let v1 = BloomFilterSettings {
329            hash_version: 1,
330            ..BloomFilterSettings::default()
331        };
332        let v2 = BloomFilterSettings {
333            hash_version: 2,
334            ..BloomFilterSettings::default()
335        };
336        let h1 = bloom_key_hashes(path.as_bytes(), &v1);
337        let h2 = bloom_key_hashes(path.as_bytes(), &v2);
338        assert_ne!(h1, h2);
339    }
340
341    #[test]
342    fn bloom_build_truncated_and_contains_roundtrip() {
343        let settings = BloomFilterSettings::default();
344        let mut paths = BTreeSet::new();
345        paths.insert("a.txt".to_owned());
346        paths.insert("dir/b.txt".to_owned());
347        let (data, outcome) = build_bloom_filter_data(&paths, 2, &settings);
348        assert_eq!(outcome, BloomBuildOutcome::Normal);
349        assert!(!data.is_empty());
350        let keys = bloom_keyvec_for_path("a.txt", &settings);
351        assert!(!keys.is_empty());
352        for key in &keys {
353            assert!(bloom_filter_contains(key, &data, &settings).unwrap());
354        }
355        let (empty, empty_out) = build_bloom_filter_data(&BTreeSet::new(), 0, &settings);
356        assert_eq!(empty_out, BloomBuildOutcome::TruncatedEmpty);
357        assert_eq!(empty.len(), 1);
358        let (large, large_out) =
359            build_bloom_filter_data(&paths, settings.max_changed_paths as usize + 1, &settings);
360        assert_eq!(large_out, BloomBuildOutcome::TruncatedLarge);
361        assert_eq!(large, vec![0xff]);
362    }
363
364    #[test]
365    fn collect_changed_paths_includes_parent_directories() {
366        let set = collect_changed_paths_for_bloom(&["deep/nested/file.txt".to_owned()]);
367        assert!(set.contains("deep"));
368        assert!(set.contains("deep/nested"));
369        assert!(set.contains("deep/nested/file.txt"));
370    }
371}
grit_lib/bloom.rs

grit_lib/
bloom.rs
