//! Query support for changed-path Bloom filters stored in commit-graph files.
use bstr::BStr;
use crate::{BloomFilterSettings, File, Graph, Position, file, from_be_u32};
const SEED0: u32 = 0x293a_e76f;
const SEED1: u32 = 0x7e64_6e2c;
const BITS_PER_WORD: u64 = 8;
/// Precomputed hash positions for a path using Bloom filter settings.
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct BloomKey {
h0: u32,
h1: u32,
num_hashes: u32,
}
impl BloomKey {
/// Build a key for `path`.
///
/// `path` must use `/` as separator.
pub fn from_path(path: &BStr, settings: BloomFilterSettings) -> Self {
Self::from_bytes(path.as_ref(), settings)
}
/// Build keys for `path` and each directory prefix.
///
/// For `a/b/c`, this yields keys for `a/b/c`, `a/b`, and `a`.
/// `path` must use `/` as separator.
pub fn from_path_with_prefixes(path: &BStr, settings: BloomFilterSettings) -> Vec<Self> {
let bytes = path.as_ref();
let mut out = vec![Self::from_bytes(bytes, settings)];
let mut idx = bytes.len();
while idx > 0 {
idx -= 1;
if bytes[idx] == b'/' {
out.push(Self::from_bytes(&bytes[..idx], settings));
}
}
out
}
pub(crate) fn from_bytes(path: &[u8], settings: BloomFilterSettings) -> Self {
let (h0, h1) = match settings.hash_version {
1 => (murmur3_v1(SEED0, path), murmur3_v1(SEED1, path)),
2 => (murmur3_v2(SEED0, path), murmur3_v2(SEED1, path)),
version => panic!(
"BUG: unsupported Bloom hash version {version} should have been filtered earlier"
),
};
Self {
h0,
h1,
num_hashes: settings.num_hashes,
}
}
/// Set the bits of this key in `filter_data`.
pub(crate) fn add_to(&self, filter_data: &mut [u8]) {
let modulo = (filter_data.len() as u64) * BITS_PER_WORD;
for i in 0..self.num_hashes {
let hash = self.h0.wrapping_add(i.wrapping_mul(self.h1));
let bit_pos = u64::from(hash) % modulo;
filter_data[(bit_pos / BITS_PER_WORD) as usize] |= 1u8 << (bit_pos % BITS_PER_WORD);
}
}
/// Query whether this key may be contained in `filter_data`.
///
/// Returns `None` if the filter is unusable (empty data), `Some(false)` on a definite miss,
/// and `Some(true)` on a possible hit.
pub fn contains(&self, filter_data: &[u8]) -> Option<bool> {
let modulo = (filter_data.len() as u64) * BITS_PER_WORD;
if modulo == 0 {
return None;
}
for i in 0..self.num_hashes {
let hash = self.h0.wrapping_add(i.wrapping_mul(self.h1));
let bit_pos = u64::from(hash) % modulo;
let byte_pos = (bit_pos / BITS_PER_WORD) as usize;
let mask = 1u8 << (bit_pos % BITS_PER_WORD);
if filter_data[byte_pos] & mask == 0 {
return Some(false);
}
}
Some(true)
}
}
impl File {
/// Query if `path` may be present in the changed-path Bloom filter for commit `pos`.
///
/// Checks the full path and each of its leading directories, which reduces false positives.
pub fn maybe_contains_path(&self, pos: file::Position, path: &BStr) -> Option<bool> {
let settings = self.bloom_filter_settings?;
let data = self.bloom_filter_at(pos)?;
let keys = BloomKey::from_path_with_prefixes(path, settings);
for key in &keys {
match key.contains(data) {
Some(false) => return Some(false),
None => return None,
Some(true) => {}
}
}
Some(true)
}
/// Query if all `keys` may be present in the changed-path Bloom filter for commit `pos`.
pub fn maybe_contains_all_keys(&self, pos: file::Position, keys: &[BloomKey]) -> Option<bool> {
let data = self.bloom_filter_at(pos)?;
if data.is_empty() {
return None;
}
Some(keys.iter().all(|key| key.contains(data) == Some(true)))
}
/// Return the raw changed-path Bloom filter bytes stored for commit `pos`, as written in the `BDAT` chunk.
///
/// Returns `None` if this file has no usable Bloom filters or `pos` is out of bounds.
/// An empty slice means the filter wasn't computed, which is distinct from a filter for no changed paths.
/// Interpret the bytes with [`File::bloom_filter_settings()`].
pub fn bloom_filter_at(&self, pos: file::Position) -> Option<&[u8]> {
self.bloom_filter_settings?;
let index_offset = self.bloom_filter_index_offset?;
let data_offset = self.bloom_filter_data_offset?;
if pos.0 >= self.num_commits() {
return None;
}
let lex = pos.0 as usize;
let end = from_be_u32(&self.data[index_offset + lex * 4..][..4]);
let start = if lex == 0 {
0
} else {
from_be_u32(&self.data[index_offset + (lex - 1) * 4..][..4])
};
let start = start as usize;
let end = end as usize;
if start > end || end > self.bloom_filter_data_len {
return None;
}
let start = data_offset.checked_add(start)?;
let end = data_offset.checked_add(end)?;
self.data.get(start..end)
}
}
impl Graph {
/// Query by commit id if `path` may be present in changed-path Bloom filters.
pub fn maybe_contains_path_by_id(
&self,
id: impl AsRef<gix_hash::oid>,
path: &BStr,
) -> Option<bool> {
let pos = self.lookup(id)?;
self.maybe_contains_path(pos, path)
}
/// Query by graph position if `path` may be present in changed-path Bloom filters.
pub fn maybe_contains_path(&self, pos: Position, path: &BStr) -> Option<bool> {
self.commit_at(pos).maybe_contains_path(path)
}
}
pub(crate) fn murmur3_v1(seed: u32, data: &[u8]) -> u32 {
murmur3(seed, data, true)
}
pub(crate) fn murmur3_v2(seed: u32, data: &[u8]) -> u32 {
murmur3(seed, data, false)
}
fn murmur3(seed: u32, data: &[u8], sign_extend: bool) -> u32 {
const C1: u32 = 0xcc9e_2d51;
const C2: u32 = 0x1b87_3593;
const R1: u32 = 15;
const R2: u32 = 13;
const M: u32 = 5;
const N: u32 = 0xe654_6b64;
let byte_to_u32 = |byte: u8| {
if sign_extend {
u32::from_ne_bytes(i32::from(i8::from_ne_bytes([byte])).to_ne_bytes())
} else {
u32::from(byte)
}
};
let mut seed = seed;
let chunks = data.chunks_exact(4);
let tail = chunks.remainder();
for chunk in chunks {
let byte1 = byte_to_u32(chunk[0]);
let byte2 = byte_to_u32(chunk[1]) << 8;
let byte3 = byte_to_u32(chunk[2]) << 16;
let byte4 = byte_to_u32(chunk[3]) << 24;
let mut k = byte1 | byte2 | byte3 | byte4;
k = k.wrapping_mul(C1);
k = k.rotate_left(R1);
k = k.wrapping_mul(C2);
seed ^= k;
seed = seed.rotate_left(R2).wrapping_mul(M).wrapping_add(N);
}
let mut k1 = 0u32;
match tail.len() {
3 => {
k1 ^= byte_to_u32(tail[2]) << 16;
k1 ^= byte_to_u32(tail[1]) << 8;
k1 ^= byte_to_u32(tail[0]);
}
2 => {
k1 ^= byte_to_u32(tail[1]) << 8;
k1 ^= byte_to_u32(tail[0]);
}
1 => {
k1 ^= byte_to_u32(tail[0]);
}
0 => {}
_ => unreachable!("remainder is shorter than 4 bytes"),
}
if !tail.is_empty() {
k1 = k1.wrapping_mul(C1);
k1 = k1.rotate_left(R1);
k1 = k1.wrapping_mul(C2);
seed ^= k1;
}
seed ^= data.len() as u32;
seed ^= seed >> 16;
seed = seed.wrapping_mul(0x85eb_ca6b);
seed ^= seed >> 13;
seed = seed.wrapping_mul(0xc2b2_ae35);
seed ^= seed >> 16;
seed
}
#[cfg(test)]
mod tests {
use super::{BITS_PER_WORD, BloomKey, murmur3_v2};
use crate::BloomFilterSettings;
use bstr::BStr;
fn filter_bytes_for_path(path: &[u8], settings: BloomFilterSettings, len: usize) -> Vec<u8> {
let key = BloomKey::from_path(BStr::new(path), settings);
let mut out = vec![0u8; len];
let modulo = (len as u64) * BITS_PER_WORD;
for i in 0..key.num_hashes {
let hash = key.h0.wrapping_add(i.wrapping_mul(key.h1));
let bit_pos = u64::from(hash) % modulo;
let byte_pos = (bit_pos / BITS_PER_WORD) as usize;
out[byte_pos] |= 1u8 << (bit_pos % BITS_PER_WORD);
}
out
}
#[test]
fn murmur3_known_vectors_match_git_and_reference_values() {
assert_eq!(murmur3_v2(0, b""), 0x0000_0000);
assert_eq!(murmur3_v2(0, b"Hello world!"), 0x627b_0c2c);
assert_eq!(
murmur3_v2(0, b"The quick brown fox jumps over the lazy dog"),
0x2e4f_f723
);
}
#[test]
fn murmur3_v2_matches_git_high_bit_vector() {
assert_eq!(murmur3_v2(0, b"\x99\xaa\xbb\xcc\xdd\xee\xff"), 0xa183_ccfd);
}
#[test]
fn bloom_key_for_empty_path_matches_git_v1_vector() {
let settings = BloomFilterSettings {
hash_version: 1,
num_hashes: 7,
bits_per_entry: 10,
};
let key = BloomKey::from_path(BStr::new(b""), settings);
assert_eq!(
(0..key.num_hashes)
.map(|i| key.h0.wrapping_add(i.wrapping_mul(key.h1)))
.collect::<Vec<_>>(),
&[
0x5615_800c,
0x5b96_6560,
0x6117_4ab4,
0x6698_3008,
0x6c19_155c,
0x7199_fab0,
0x771a_e004
]
);
}
#[test]
fn bloom_key_for_empty_path_matches_git_v2_vector() {
let settings = BloomFilterSettings {
hash_version: 2,
num_hashes: 7,
bits_per_entry: 10,
};
let key = BloomKey::from_path(BStr::new(b""), settings);
assert_eq!(
(0..key.num_hashes)
.map(|i| key.h0.wrapping_add(i.wrapping_mul(key.h1)))
.collect::<Vec<_>>(),
&[
0x5615_800c,
0x5b96_6560,
0x6117_4ab4,
0x6698_3008,
0x6c19_155c,
0x7199_fab0,
0x771a_e004
]
);
}
#[test]
fn bloom_key_for_high_bit_path_differs_between_versions() {
let path = BStr::new(b"\xc2\xa2");
let v1 = BloomKey::from_path(
path,
BloomFilterSettings {
hash_version: 1,
num_hashes: 7,
bits_per_entry: 10,
},
);
let v2 = BloomKey::from_path(
path,
BloomFilterSettings {
hash_version: 2,
num_hashes: 7,
bits_per_entry: 10,
},
);
assert_ne!(v1, v2);
}
#[test]
fn bloom_filter_for_high_bit_path_matches_git_v1_and_v2_vectors() {
let path = b"\xc2\xa2";
assert_eq!(
filter_bytes_for_path(
path,
BloomFilterSettings {
hash_version: 1,
num_hashes: 7,
bits_per_entry: 10,
},
2,
),
vec![0x52, 0xa9]
);
assert_eq!(
filter_bytes_for_path(
path,
BloomFilterSettings {
hash_version: 2,
num_hashes: 7,
bits_per_entry: 10,
},
2,
),
vec![0xc0, 0x1f]
);
}
}