use crate::{Result, error::invalid};
use super::{PathBloom, format::Chunk};
pub(super) struct Bloom {
index: Chunk,
data: Chunk,
version: u32,
hashes: u32,
}
impl Bloom {
pub(super) fn new(bytes: &[u8], index: Chunk, data: Chunk, count: usize) -> Result<Self> {
if index.end - index.start != count * 4 || data.end - data.start < 12 {
return Err(invalid("invalid commit-graph Bloom chunk length"));
}
let version = read_u32(bytes, data.start)?;
let hashes = read_u32(bytes, data.start + 4)?;
let bits_per_entry = read_u32(bytes, data.start + 8)?;
if !(1..=2).contains(&version) || hashes == 0 || hashes > 32 || bits_per_entry == 0 {
return Err(invalid("unsupported commit-graph Bloom parameters"));
}
Ok(Self {
index,
data,
version,
hashes,
})
}
pub(super) fn query(&self, bytes: &[u8], position: usize, path: &[u8]) -> Result<PathBloom> {
let end = usize::try_from(read_u32(bytes, self.index.start + position * 4)?)
.map_err(|_| invalid("Bloom filter offset overflow"))?;
let start = if position == 0 {
0
} else {
usize::try_from(read_u32(bytes, self.index.start + (position - 1) * 4)?)
.map_err(|_| invalid("Bloom filter offset overflow"))?
};
if start > end {
return Err(invalid("Bloom filter offsets are not monotonic"));
}
let filter_start = self
.data
.start
.checked_add(12 + start)
.ok_or_else(|| invalid("Bloom filter offset overflow"))?;
let filter_end = self
.data
.start
.checked_add(12 + end)
.ok_or_else(|| invalid("Bloom filter offset overflow"))?;
let filter = bytes
.get(filter_start..filter_end)
.filter(|value| !value.is_empty() && filter_end <= self.data.end)
.ok_or_else(|| invalid("Bloom filter is empty or out of bounds"))?;
let bit_count = u32::try_from(filter.len())
.ok()
.and_then(|length| length.checked_mul(8))
.ok_or_else(|| invalid("Bloom filter bit count overflow"))?;
if self.version == 1 && !path.is_ascii() {
return Ok(PathBloom::Maybe);
}
let first = murmur3(path, 0x293a_e76f);
let second = murmur3(path, 0x7e64_6e2c);
for index in 0..self.hashes {
let bit = first.wrapping_add(index.wrapping_mul(second)) % bit_count;
if filter[usize::try_from(bit / 8).expect("u32 fits usize")] & (1 << (bit % 8)) == 0 {
return Ok(PathBloom::DefinitelyNot);
}
}
Ok(PathBloom::Maybe)
}
}
fn murmur3(input: &[u8], seed: u32) -> u32 {
let mut hash = seed;
let mut chunks = input.chunks_exact(4);
for chunk in &mut chunks {
let mut value = u32::from_le_bytes(chunk.try_into().expect("four bytes"));
value = value.wrapping_mul(0xcc9e_2d51).rotate_left(15);
value = value.wrapping_mul(0x1b87_3593);
hash ^= value;
hash = hash
.rotate_left(13)
.wrapping_mul(5)
.wrapping_add(0xe654_6b64);
}
let remainder = chunks.remainder();
let mut tail = 0_u32;
for (shift, byte) in remainder.iter().enumerate() {
tail |= u32::from(*byte) << (shift * 8);
}
if !remainder.is_empty() {
tail = tail.wrapping_mul(0xcc9e_2d51).rotate_left(15);
hash ^= tail.wrapping_mul(0x1b87_3593);
}
hash ^= u32::try_from(input.len()).unwrap_or(u32::MAX);
hash ^= hash >> 16;
hash = hash.wrapping_mul(0x85eb_ca6b);
hash ^= hash >> 13;
hash = hash.wrapping_mul(0xc2b2_ae35);
hash ^ (hash >> 16)
}
fn read_u32(input: &[u8], offset: usize) -> Result<u32> {
let bytes = input
.get(offset..offset + 4)
.ok_or_else(|| invalid("truncated Bloom integer"))?;
Ok(u32::from_be_bytes(bytes.try_into().expect("four bytes")))
}
#[cfg(test)]
mod tests {
use super::murmur3;
#[test]
fn murmur3_matches_public_vectors() {
assert_eq!(murmur3(b"", 0), 0);
assert_eq!(murmur3(b"foo", 0), 0xf6a5_c420);
assert_eq!(murmur3(b"hello", 0), 0x248b_fa47);
}
}