use std::{mem::size_of, sync::Arc};
use super::{FormatFault, hash::filter_partition};
const MAX_BUILD_ATTEMPTS: usize = 100;
const MAX_SEGMENT_LENGTH: u32 = 262_144;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct FuseParams {
pub seed: u64,
pub segment_length: u32,
pub segment_count_length: u32,
}
impl FuseParams {
pub(crate) fn array_len(&self) -> usize {
self.segment_count_length as usize + 2 * self.segment_length as usize
}
pub(crate) fn validate(&self, fingerprints_len: usize) -> Result<(), FormatFault> {
if !self.segment_length.is_power_of_two() {
return Err(FormatFault::corrupt(format!(
"filter segment length {} is not a power of two",
self.segment_length
)));
}
if self.segment_count_length == 0
|| !self
.segment_count_length
.is_multiple_of(self.segment_length)
{
return Err(FormatFault::corrupt(format!(
"filter segment count length {} is not a multiple of {}",
self.segment_count_length, self.segment_length
)));
}
let total = u64::from(self.segment_count_length) + 2 * u64::from(self.segment_length);
if total > u64::from(u32::MAX) + 1 || usize::try_from(total).is_err() {
return Err(FormatFault::corrupt(
"filter positions exceed addressable range",
));
}
if self.array_len() != fingerprints_len {
return Err(FormatFault::corrupt(format!(
"filter holds {fingerprints_len} fingerprints, its parameters need {}",
self.array_len()
)));
}
Ok(())
}
}
#[inline]
fn murmur64(mut k: u64) -> u64 {
k ^= k >> 33;
k = k.wrapping_mul(0xff51_afd7_ed55_8ccd);
k ^= k >> 33;
k = k.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
k ^= k >> 33;
k
}
#[inline]
fn mix(key: u64, seed: u64) -> u64 {
murmur64(key.wrapping_add(seed))
}
#[inline]
fn fingerprint(hash: u64) -> u8 {
(hash ^ (hash >> 32)) as u8
}
fn splitmix64(state: &mut u64) -> u64 {
*state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = *state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
#[inline]
fn positions(hash: u64, p: &FuseParams) -> [usize; 3] {
let mask = p.segment_length - 1;
let h0 = ((hash as u128 * p.segment_count_length as u128) >> 64) as u32;
let mut h1 = h0 + p.segment_length;
let mut h2 = h1 + p.segment_length;
h1 ^= ((hash >> 18) as u32) & mask;
h2 ^= (hash as u32) & mask;
[h0 as usize, h1 as usize, h2 as usize]
}
fn layout_for(n: usize) -> (u32, u32) {
const ARITY: u32 = 3;
let segment_length = if n == 0 {
4
} else {
let exponent = ((n as f64).ln() / 3.33_f64.ln() + 2.25).floor() as u32;
(1u32 << exponent).min(MAX_SEGMENT_LENGTH)
};
let capacity = if n > 1 {
let factor = (0.875 + 0.25 * 1_000_000_f64.ln() / (n as f64).ln()).max(1.125);
(n as f64 * factor).round() as u32
} else {
0
};
let initial = capacity.div_ceil(segment_length);
let segment_count = if initial < ARITY {
1
} else {
initial - (ARITY - 1)
};
(segment_length, segment_count * segment_length)
}
#[inline]
#[cfg(test)]
pub(crate) fn fuse8_contains(key: u64, params: &FuseParams, fingerprints: &[u8]) -> bool {
let hash = mix(key, params.seed);
let [h0, h1, h2] = positions(hash, params);
fingerprint(hash) ^ fingerprints[h0] ^ fingerprints[h1] ^ fingerprints[h2] == 0
}
pub(crate) fn fuse8_build(keys: &[u64]) -> Option<(FuseParams, Vec<u8>)> {
let n = keys.len();
let (formula_length, formula_count_length) = layout_for(n);
let array_len = formula_count_length as usize + 2 * formula_length as usize;
let may_halve = n > 4 && n < 1_000_000;
let mut rng = 1u64;
let mut count = vec![0u32; array_len];
let mut xor = vec![0u64; array_len];
let mut queue: Vec<u32> = Vec::with_capacity(array_len);
let mut stack: Vec<(u64, u8)> = Vec::with_capacity(n);
for attempt in 0..MAX_BUILD_ATTEMPTS {
let seed = splitmix64(&mut rng);
let (segment_length, segment_count_length) = if may_halve && attempt % 4 == 1 {
(formula_length / 2, formula_count_length + formula_length)
} else {
(formula_length, formula_count_length)
};
let params = FuseParams {
seed,
segment_length,
segment_count_length,
};
count.fill(0);
xor.fill(0);
queue.clear();
stack.clear();
for &key in keys {
let hash = mix(key, seed);
for p in positions(hash, ¶ms) {
count[p] += 1;
xor[p] ^= hash;
}
}
queue.extend((0..array_len as u32).filter(|&slot| count[slot as usize] == 1));
while let Some(slot) = queue.pop() {
let slot = slot as usize;
if count[slot] != 1 {
continue;
}
let hash = xor[slot];
let at = positions(hash, ¶ms);
let Some(found) = at.iter().position(|&p| p == slot) else {
break;
};
stack.push((hash, found as u8));
for p in at {
count[p] -= 1;
xor[p] ^= hash;
if count[p] == 1 {
queue.push(p as u32);
}
}
}
if stack.len() != n {
continue;
}
let mut fingerprints = vec![0u8; array_len];
for &(hash, found) in stack.iter().rev() {
let at = positions(hash, ¶ms);
let f = found as usize;
fingerprints[at[f]] =
fingerprint(hash) ^ fingerprints[at[(f + 1) % 3]] ^ fingerprints[at[(f + 2) % 3]];
}
return Some((params, fingerprints));
}
None
}
pub(crate) const FILTER_KIND_FUSE8: u8 = 1;
pub(crate) const PARTITION_TARGET_KEYS: u64 = 524_288;
pub(crate) const MAX_PARTITION_BITS: u8 = 16;
const FILTER_HEADER_LEN: usize = 8;
const PART_RECORD_LEN: usize = 32;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum FilterBuildError {
OutOfOrder,
ConstructionFailed { partition: usize, keys: usize },
SizeLimitExceeded,
}
fn wire_u32(value: usize) -> Result<u32, FilterBuildError> {
u32::try_from(value).map_err(|_| FilterBuildError::SizeLimitExceeded)
}
fn checked_section_end(start: usize, len: usize) -> Result<usize, FilterBuildError> {
start
.checked_add(len)
.filter(|&end| end <= isize::MAX as usize)
.ok_or(FilterBuildError::SizeLimitExceeded)
}
struct BuiltPart {
keys: u32,
params: FuseParams,
fingerprints: Vec<u8>,
}
pub(crate) struct PartitionedFilterBuilder {
bits: u8,
pending: Vec<u64>,
parts: Vec<BuiltPart>,
}
impl PartitionedFilterBuilder {
pub(crate) fn new(bits: u8) -> Self {
assert!(
bits <= MAX_PARTITION_BITS,
"filter partition bits exceed 16"
);
Self {
bits,
pending: Vec::new(),
parts: Vec::with_capacity(1usize << bits),
}
}
pub(crate) fn push(&mut self, h: u64) -> Result<(), FilterBuildError> {
let partition = filter_partition(h, self.bits);
if partition < self.parts.len() {
return Err(FilterBuildError::OutOfOrder);
}
while self.parts.len() < partition {
self.close_partition()?;
}
match self.pending.last() {
Some(&last) if last == h => Ok(()),
Some(&last) if last > h => Err(FilterBuildError::OutOfOrder),
_ => {
self.pending.push(h);
Ok(())
}
}
}
fn close_partition(&mut self) -> Result<(), FilterBuildError> {
let keys = std::mem::take(&mut self.pending);
let part = if keys.is_empty() {
BuiltPart {
keys: 0,
params: FuseParams {
seed: 0,
segment_length: 0,
segment_count_length: 0,
},
fingerprints: Vec::new(),
}
} else {
let key_count = wire_u32(keys.len())?;
let (params, fingerprints) =
fuse8_build(&keys).ok_or(FilterBuildError::ConstructionFailed {
partition: self.parts.len(),
keys: keys.len(),
})?;
BuiltPart {
keys: key_count,
params,
fingerprints,
}
};
self.parts.push(part);
Ok(())
}
pub(crate) fn finish(mut self) -> Result<Vec<u8>, FilterBuildError> {
let total = 1usize << self.bits;
while self.parts.len() < total {
self.close_partition()?;
}
let count = wire_u32(total)?;
let table_len = total
.checked_mul(PART_RECORD_LEN)
.ok_or(FilterBuildError::SizeLimitExceeded)?;
let table_end = checked_section_end(FILTER_HEADER_LEN, table_len)?;
let mut section_end = table_end;
for part in &self.parts {
wire_u32(part.fingerprints.len())?;
section_end = checked_section_end(section_end, part.fingerprints.len())?;
u64::try_from(section_end).map_err(|_| FilterBuildError::SizeLimitExceeded)?;
}
let mut out = Vec::with_capacity(section_end);
out.push(FILTER_KIND_FUSE8);
out.push(self.bits);
out.extend_from_slice(&0u16.to_le_bytes());
out.extend_from_slice(&count.to_le_bytes());
let mut offset = table_end;
for part in &self.parts {
let wire_offset =
u64::try_from(offset).map_err(|_| FilterBuildError::SizeLimitExceeded)?;
let wire_len = wire_u32(part.fingerprints.len())?;
out.extend_from_slice(&wire_offset.to_le_bytes());
out.extend_from_slice(&wire_len.to_le_bytes());
out.extend_from_slice(&part.keys.to_le_bytes());
out.extend_from_slice(&part.params.seed.to_le_bytes());
out.extend_from_slice(&part.params.segment_length.to_le_bytes());
out.extend_from_slice(&part.params.segment_count_length.to_le_bytes());
offset = checked_section_end(offset, part.fingerprints.len())?;
}
for part in &self.parts {
out.extend_from_slice(&part.fingerprints);
}
Ok(out)
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct PartMeta {
pub(crate) offset: usize,
pub(crate) len: usize,
pub(crate) keys: u32,
pub(crate) params: FuseParams,
}
#[derive(Debug, PartialEq, Eq)]
pub(crate) struct FilterTable {
pub(crate) bits: u8,
pub(crate) parts: Vec<PartMeta>,
}
impl FilterTable {
pub(crate) fn parse(bytes: &[u8], section_len: usize) -> Result<Self, FormatFault> {
if bytes.len() < FILTER_HEADER_LEN {
return Err(FormatFault::corrupt(
"filter section is shorter than its header",
));
}
let kind = bytes[0];
let bits = bytes[1];
let reserved = u16::from_le_bytes([bytes[2], bytes[3]]);
let count = u32::from_le_bytes(bytes[4..8].try_into().expect("4 bytes")) as usize;
if kind != FILTER_KIND_FUSE8 {
return Err(FormatFault::unsupported(format!("filter kind {kind}")));
}
if reserved != 0 {
return Err(FormatFault::unsupported(format!(
"filter reserved bytes {reserved:#x}"
)));
}
if bits > MAX_PARTITION_BITS {
return Err(FormatFault::corrupt(format!(
"filter has {bits} partition bits"
)));
}
if count != 1usize << bits {
return Err(FormatFault::corrupt(format!(
"filter lists {count} partitions for {bits} bits"
)));
}
let table_end = Self::head_len(bits);
if bytes.len() < table_end {
return Err(FormatFault::corrupt("filter partition table is truncated"));
}
let mut parts = Vec::with_capacity(count);
let mut expected_offset = table_end;
for i in 0..count {
let at = FILTER_HEADER_LEN + i * PART_RECORD_LEN;
let rec = &bytes[at..at + PART_RECORD_LEN];
let offset = u64::from_le_bytes(rec[0..8].try_into().expect("8 bytes"));
let len = u32::from_le_bytes(rec[8..12].try_into().expect("4 bytes")) as usize;
let keys = u32::from_le_bytes(rec[12..16].try_into().expect("4 bytes"));
let params = FuseParams {
seed: u64::from_le_bytes(rec[16..24].try_into().expect("8 bytes")),
segment_length: u32::from_le_bytes(rec[24..28].try_into().expect("4 bytes")),
segment_count_length: u32::from_le_bytes(rec[28..32].try_into().expect("4 bytes")),
};
if offset != expected_offset as u64 {
return Err(FormatFault::corrupt(format!(
"filter partition {i} starts at {offset}, expected {expected_offset}"
)));
}
if keys == 0 {
if len != 0
|| params.seed != 0
|| params.segment_length != 0
|| params.segment_count_length != 0
{
return Err(FormatFault::corrupt(format!(
"empty filter partition {i} has data or parameters"
)));
}
} else {
params.validate(len)?;
}
expected_offset = expected_offset.checked_add(len).ok_or_else(|| {
FormatFault::corrupt("filter partition lengths overflow addressable range")
})?;
if expected_offset > section_len {
return Err(FormatFault::corrupt(format!(
"filter partition {i} ends outside the section"
)));
}
parts.push(PartMeta {
offset: offset as usize,
len,
keys,
params,
});
}
if expected_offset != section_len {
return Err(FormatFault::corrupt(format!(
"filter section is {} bytes, its table accounts for {expected_offset}",
section_len
)));
}
Ok(Self { bits, parts })
}
pub(crate) fn head_len(bits: u8) -> usize {
FILTER_HEADER_LEN + (1usize << bits) * PART_RECORD_LEN
}
pub(crate) fn resident_bytes(&self) -> usize {
size_of::<Self>() + self.parts.capacity() * size_of::<PartMeta>()
}
pub(crate) fn encode_head(&self) -> Vec<u8> {
let mut out = vec![FILTER_KIND_FUSE8, self.bits, 0, 0];
out.extend_from_slice(&(self.parts.len() as u32).to_le_bytes());
for p in &self.parts {
out.extend_from_slice(&(p.offset as u64).to_le_bytes());
out.extend_from_slice(&(p.len as u32).to_le_bytes());
out.extend_from_slice(&p.keys.to_le_bytes());
out.extend_from_slice(&p.params.seed.to_le_bytes());
out.extend_from_slice(&p.params.segment_length.to_le_bytes());
out.extend_from_slice(&p.params.segment_count_length.to_le_bytes());
}
out
}
}
pub(crate) struct PartitionedFilter {
table: Arc<FilterTable>,
bytes: Arc<[u8]>,
}
impl PartitionedFilter {
pub(crate) fn parse(bytes: Arc<[u8]>) -> Result<Self, FormatFault> {
let table = Arc::new(FilterTable::parse(&bytes, bytes.len())?);
Ok(Self { table, bytes })
}
pub(crate) fn with_table(table: Arc<FilterTable>, bytes: Arc<[u8]>) -> Self {
Self { table, bytes }
}
pub(crate) fn into_bytes(self) -> Arc<[u8]> {
self.bytes
}
#[cfg(test)]
pub(crate) fn table(&self) -> &Arc<FilterTable> {
&self.table
}
#[inline]
pub(crate) fn may_contain(&self, h: u64) -> bool {
match probe(&self.table, h) {
Probe::Absent => false,
Probe::At { fingerprint, at } => {
probe_matches(fingerprint, at.map(|p| self.bytes[p as usize]))
}
}
}
#[cfg(test)]
pub(crate) fn keys(&self) -> u64 {
self.table.parts.iter().map(|p| u64::from(p.keys)).sum()
}
pub(crate) fn resident_bytes(&self) -> usize {
self.bytes.len()
}
}
pub(crate) enum Probe {
Absent,
At { fingerprint: u8, at: [u64; 3] },
}
pub(crate) fn probe(table: &FilterTable, h: u64) -> Probe {
let part = &table.parts[filter_partition(h, table.bits)];
if part.keys == 0 {
return Probe::Absent;
}
let hash = mix(h, part.params.seed);
let at = positions(hash, &part.params).map(|p| part.offset as u64 + p as u64);
Probe::At {
fingerprint: fingerprint(hash),
at,
}
}
pub(crate) fn probe_matches(fingerprint: u8, bytes: [u8; 3]) -> bool {
fingerprint ^ bytes[0] ^ bytes[1] ^ bytes[2] == 0
}
pub(crate) fn build_sorted_filter(hashes: &mut Vec<u64>) -> Result<Vec<u8>, FilterBuildError> {
hashes.sort_unstable();
hashes.dedup();
let bits = super::hash::partition_bits_for(
hashes.len() as u64,
PARTITION_TARGET_KEYS,
MAX_PARTITION_BITS,
);
let mut builder = PartitionedFilterBuilder::new(bits);
for &h in hashes.iter() {
builder.push(h)?;
}
builder.finish()
}
#[cfg(test)]
mod tests {
#[test]
fn a_probe_of_fetched_bytes_matches_independent_fuse_membership() {
let mut hashes: Vec<u64> = (0..50_000u64)
.map(|i| i.wrapping_mul(0x9e37_79b9_7f4a_7c15))
.collect();
let section = build_sorted_filter(&mut hashes).unwrap();
let filter = PartitionedFilter::parse(Arc::from(section.clone())).unwrap();
let mut state = 7u64;
for i in 0..200_000u64 {
let h = if i % 2 == 0 {
hashes[(i as usize / 2) % hashes.len()]
} else {
splitmix64(&mut state)
};
let cold = match probe(filter.table(), h) {
Probe::Absent => false,
Probe::At { fingerprint, at } => {
probe_matches(fingerprint, at.map(|p| section[p as usize]))
}
};
let part = &filter.table().parts[filter_partition(h, filter.table().bits)];
let independent = part.keys != 0
&& fuse8_contains(
h,
&part.params,
§ion[part.offset..part.offset + part.len],
);
assert_eq!(cold, independent, "hash {h:#x}");
if i % 2 == 0 {
assert!(cold, "inserted hash {h:#x}");
}
}
}
use super::*;
use std::sync::Arc;
use xorf::{BinaryFuse8, Filter};
fn sorted_hashes(n: usize, seed: u64) -> Vec<u64> {
distinct_keys(n, seed)
}
fn build_section(hashes: &[u64], bits: u8) -> Vec<u8> {
let mut b = PartitionedFilterBuilder::new(bits);
for &h in hashes {
b.push(h).unwrap();
}
b.finish().unwrap()
}
#[test]
fn by_key_filters_sort_dedup_and_partition_independently() {
let mut hashes = sorted_hashes(PARTITION_TARGET_KEYS as usize + 1, 31);
hashes.reverse();
hashes.extend_from_within(..100);
let full = build_sorted_filter(&mut hashes).unwrap();
let filter = PartitionedFilter::parse(Arc::from(full.clone())).unwrap();
assert_eq!(full[1], 1);
assert!(hashes.windows(2).all(|w| w[0] < w[1]));
assert!(hashes.iter().all(|h| filter.may_contain(*h)));
let mut prefixes = vec![7, 3, 7, 3, 1, 7];
let small = build_sorted_filter(&mut prefixes).unwrap();
assert_eq!(small[1], 0);
assert_eq!(prefixes, [1, 3, 7]);
}
#[test]
fn a_partitioned_filter_round_trips() {
let hashes = sorted_hashes(40_000, 21);
for bits in [0u8, 3, 6] {
let section = build_section(&hashes, bits);
let filter = PartitionedFilter::parse(Arc::from(section)).unwrap();
assert_eq!(filter.keys(), hashes.len() as u64);
assert!(filter.resident_bytes() >= filter.bytes.len());
for &h in &hashes {
assert!(filter.may_contain(h), "false negative with {bits} bits");
}
let mut state = 5u64;
let hits = (0..200_000)
.filter(|_| filter.may_contain(splitmix(&mut state)))
.count();
assert!(hits < 1_400, "{hits} false positives with {bits} bits");
}
}
#[test]
fn an_empty_partition_answers_absent() {
let hashes: Vec<u64> = (1..=1_000u64).collect();
let section = build_section(&hashes, 2);
let filter = PartitionedFilter::parse(Arc::from(section)).unwrap();
assert!(filter.may_contain(500));
assert!(!filter.may_contain(u64::MAX));
assert!(!filter.may_contain(1u64 << 63));
}
#[test]
fn a_filter_with_no_keys_is_valid() {
let section = build_section(&[], 4);
let filter = PartitionedFilter::parse(Arc::from(section)).unwrap();
assert_eq!(filter.keys(), 0);
assert!(!filter.may_contain(0));
assert!(!filter.may_contain(u64::MAX));
}
#[test]
fn repeated_hashes_are_counted_once() {
let mut b = PartitionedFilterBuilder::new(1);
for h in [10u64, 10, 10, 20, 20, u64::MAX, u64::MAX] {
b.push(h).unwrap();
}
let filter = PartitionedFilter::parse(Arc::from(b.finish().unwrap())).unwrap();
assert_eq!(filter.keys(), 3);
for h in [10u64, 20, u64::MAX] {
assert!(filter.may_contain(h));
}
}
#[test]
fn hashes_must_arrive_in_order() {
let mut b = PartitionedFilterBuilder::new(2);
b.push(100).unwrap();
assert_eq!(b.push(99), Err(FilterBuildError::OutOfOrder));
let mut b = PartitionedFilterBuilder::new(2);
b.push(u64::MAX).unwrap();
assert_eq!(b.push(1), Err(FilterBuildError::OutOfOrder));
}
#[cfg(target_pointer_width = "64")]
#[test]
fn filter_wire_fields_reject_values_above_u32_max() {
assert_eq!(wire_u32(u32::MAX as usize).unwrap(), u32::MAX);
assert_eq!(
wire_u32(u32::MAX as usize + 1),
Err(FilterBuildError::SizeLimitExceeded)
);
}
#[test]
fn filter_section_length_rejects_arithmetic_overflow() {
assert_eq!(checked_section_end(8, 32).unwrap(), 40);
assert_eq!(
checked_section_end(usize::MAX, 1),
Err(FilterBuildError::SizeLimitExceeded)
);
}
#[test]
fn a_damaged_section_is_rejected_before_any_query() {
let good = build_section(&sorted_hashes(5_000, 1), 2);
let parse = |bytes: Vec<u8>| PartitionedFilter::parse(Arc::from(bytes));
let mut kind = good.clone();
kind[0] = 9;
assert!(matches!(parse(kind), Err(FormatFault::Unsupported(_))));
let mut reserved = good.clone();
reserved[2] = 1;
assert!(matches!(parse(reserved), Err(FormatFault::Unsupported(_))));
let mut bits = good.clone();
bits[1] = 17;
assert!(matches!(parse(bits), Err(FormatFault::Corrupt(_))));
let mut count = good.clone();
count[4..8].copy_from_slice(&5u32.to_le_bytes());
assert!(matches!(parse(count), Err(FormatFault::Corrupt(_))));
let mut zero_segment_length = good.clone();
zero_segment_length[32..36].copy_from_slice(&0u32.to_le_bytes());
assert!(matches!(
parse(zero_segment_length),
Err(FormatFault::Corrupt(_))
));
let mut non_power_of_two_segment_length = good.clone();
non_power_of_two_segment_length[32..36].copy_from_slice(&3u32.to_le_bytes());
assert!(matches!(
parse(non_power_of_two_segment_length),
Err(FormatFault::Corrupt(_))
));
let mut outside = good.clone();
outside[8..16].copy_from_slice(&(good.len() as u64).to_le_bytes());
assert!(matches!(parse(outside), Err(FormatFault::Corrupt(_))));
let mut overlap = good.clone();
overlap[40..48].copy_from_slice(&8u64.to_le_bytes());
assert!(matches!(parse(overlap), Err(FormatFault::Corrupt(_))));
let empty = build_section(&[], 1);
let mut bad_empty = empty.clone();
bad_empty[24..32].copy_from_slice(&1u64.to_le_bytes());
assert!(matches!(parse(bad_empty), Err(FormatFault::Corrupt(_))));
assert!(matches!(
parse(good[..good.len() - 1].to_vec()),
Err(FormatFault::Corrupt(_))
));
assert!(matches!(
parse(good[..7].to_vec()),
Err(FormatFault::Corrupt(_))
));
assert!(matches!(parse(Vec::new()), Err(FormatFault::Corrupt(_))));
}
fn splitmix(state: &mut u64) -> u64 {
*state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
let mut z = *state;
z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
z ^ (z >> 31)
}
fn distinct_keys(n: usize, seed: u64) -> Vec<u64> {
let mut state = seed;
let mut keys: Vec<u64> = (0..n).map(|_| splitmix(&mut state)).collect();
keys.sort_unstable();
keys.dedup();
while keys.len() < n {
keys.push(splitmix(&mut state));
keys.sort_unstable();
keys.dedup();
}
keys
}
fn false_positive_rate(params: &FuseParams, fp: &[u8], probes: usize) -> f64 {
let mut state = 0xfeed_u64;
let hits = (0..probes)
.filter(|_| fuse8_contains(splitmix(&mut state), params, fp))
.count();
hits as f64 / probes as f64
}
#[test]
fn every_key_is_found_at_every_size() {
let sizes = [
1, 2, 3, 4, 5, 10, 100, 1_000, 10_000, 100_000, 524_288, 9, 28, 92, 304, 1_010, 3_362,
11_194, 37_273, 124_118, 413_310,
];
for n in sizes {
let keys = distinct_keys(n, n as u64);
let (params, fp) = fuse8_build(&keys).unwrap_or_else(|| panic!("build failed at {n}"));
params.validate(fp.len()).unwrap();
for &k in &keys {
assert!(
fuse8_contains(k, ¶ms, &fp),
"false negative at size {n}"
);
}
}
}
#[test]
fn false_positives_stay_near_one_in_256() {
for n in [10_000usize, 100_000, 524_288] {
let keys = distinct_keys(n, 3);
let (params, fp) = fuse8_build(&keys).unwrap();
let rate = false_positive_rate(¶ms, &fp, 400_000);
assert!(rate < 0.006, "size {n}: rate {rate}");
assert!(rate > 0.002, "size {n}: rate {rate} is suspiciously low");
}
}
#[test]
fn size_is_about_nine_bits_per_key() {
let n = 524_288;
let keys = distinct_keys(n, 5);
let (_, fp) = fuse8_build(&keys).unwrap();
let bits_per_key = fp.len() as f64 * 8.0 / n as f64;
assert!(bits_per_key < 9.5, "{bits_per_key}");
}
#[test]
fn our_query_reads_a_reference_filter() {
let keys = distinct_keys(50_000, 11);
let reference = BinaryFuse8::try_from(&keys).unwrap();
let params = FuseParams {
seed: reference.descriptor.seed,
segment_length: reference.descriptor.segment_length,
segment_count_length: reference.descriptor.segment_count_length,
};
params.validate(reference.fingerprints.len()).unwrap();
let mut state = 99u64;
let probes = keys
.iter()
.copied()
.chain((0..200_000).map(|_| splitmix(&mut state)));
for k in probes {
assert_eq!(
fuse8_contains(k, ¶ms, &reference.fingerprints),
reference.contains(&k),
"disagreement on {k:#x}"
);
}
}
#[test]
fn our_filter_has_the_reference_size() {
for n in [1usize, 5, 1_000, 37_273, 100_000] {
let keys = distinct_keys(n, 17);
let (_, fp) = fuse8_build(&keys).unwrap();
let reference = BinaryFuse8::try_from(&keys).unwrap();
assert_eq!(fp.len(), reference.fingerprints.len(), "size {n}");
}
}
#[test]
fn duplicate_keys_make_the_build_fail() {
assert!(fuse8_build(&[7, 7]).is_none());
}
#[test]
fn parameters_that_would_index_out_of_bounds_are_rejected() {
let keys = distinct_keys(1_000, 1);
let (good, fp) = fuse8_build(&keys).unwrap();
let zero = FuseParams {
segment_length: 0,
..good
};
assert!(matches!(
zero.validate(fp.len()),
Err(FormatFault::Corrupt(_))
));
let odd = FuseParams {
segment_length: good.segment_length + 1,
..good
};
assert!(matches!(
odd.validate(fp.len()),
Err(FormatFault::Corrupt(_))
));
let ragged = FuseParams {
segment_count_length: good.segment_count_length + 1,
..good
};
assert!(matches!(
ragged.validate(fp.len()),
Err(FormatFault::Corrupt(_))
));
assert!(matches!(
good.validate(fp.len() - 1),
Err(FormatFault::Corrupt(_))
));
}
#[cfg(target_pointer_width = "64")]
#[test]
fn overflowing_position_arithmetic_is_rejected() {
let params = FuseParams {
seed: 1,
segment_length: 1,
segment_count_length: u32::MAX,
};
assert!(matches!(
params.validate(u32::MAX as usize + 2),
Err(FormatFault::Corrupt(_))
));
}
#[test]
fn the_filter_section_has_the_documented_layout() {
#[rustfmt::skip]
const HEAD: [u8; 72] = [
0x01, 0x01, 0x00, 0x00, 0x02, 0x00, 0x00, 0x00, 0x48, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0c, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0xc1, 0x5c, 0x02, 0x89, 0xec, 0x2d, 0x0a, 0x91, 0x04, 0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x54, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, ];
let section = build_section(&[0], 1);
assert_eq!(section.len(), 84);
assert_eq!(section[..72], HEAD);
let filter = PartitionedFilter::parse(Arc::from(section)).unwrap();
assert!(filter.may_contain(0));
assert_eq!(filter.keys(), 1);
}
fn with_duplicates(n: usize, seed: u64, dup_every: usize) -> Vec<u64> {
let mut state = seed;
let mut hashes: Vec<u64> = (0..n).map(|_| splitmix(&mut state)).collect();
hashes.sort_unstable();
let mut out = Vec::with_capacity(n + n / dup_every + 1);
for (i, &h) in hashes.iter().enumerate() {
out.push(h);
if i % dup_every == 0 {
out.push(h);
}
}
out
}
proptest::proptest! {
#![proptest_config(proptest::prelude::ProptestConfig::with_cases(12))]
#[test]
fn proptest_partitioned_filter_has_no_false_negatives(
n in proptest::prop_oneof![0usize..=1_000_000, 524_288usize..1_000_000],
seed in proptest::prelude::any::<u64>(),
dup_every in 1usize..=64,
bits in 0u8..=2,
) {
let hashes = with_duplicates(n, seed, dup_every);
let filter = PartitionedFilter::parse(Arc::from(build_section(&hashes, bits))).unwrap();
let mut distinct = hashes.clone();
distinct.dedup();
proptest::prop_assert_eq!(filter.keys(), distinct.len() as u64);
for &h in &distinct {
proptest::prop_assert!(filter.may_contain(h), "false negative for {:#x}", h);
}
}
}
}