Struct Block

Source

#[repr(transparent)]
struct Block([u32; 8]);

Expand description

A single 256-bit block, the basic unit of the Split Block Bloom Filter.

A block is eight contiguous 32-bit words ([u32; 8]). Each word is an independent bit-array of 32 positions:

  Block (256 bits total)
  ┌────────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┐
  │ word 0 │ word 1 │ word 2 │ word 3 │ word 4 │ word 5 │ word 6 │ word 7 │
  │ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│ 32 bits│
  └────────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┘

When a value is inserted, Block::mask picks one bit in each word (8 bits total), and those bits are OR’d in. When checking, we verify all 8 bits are set.

Tuple Fields§

§0: [u32; 8]

Implementations§

Source §

impl Block

Source

fn mask(x: u32) -> Self

Produce a block where each of the 8 words has exactly one bit set.

For each word i the bit position is derived from x:

  y = (x wrapping* SALT[i]) >> 27   // top 5 bits → value in 0..31
  word[i] = 1 << y                  // exactly one bit set per word

Because only the top 5 bits survive the shift, each word picks one of 32 possible bit positions. The eight SALT constants spread the choices so different words usually light up different positions.

Key property: the mask depends only on x (a u32) and the fixed SALT constants — it is independent of the filter size. This is why folding preserves bit patterns (see Lemma 2 in tests).

Source

fn insert(&mut self, hash: u32)

OR the mask bits into this block (block[i] |= mask[i]).

After insertion the 8 bits chosen by mask(hash) are guaranteed set; bits previously set by other hashes are preserved.

Source

fn check(&self, hash: u32) -> bool

Check membership: returns true when every bit from mask(hash) is already set in this block (block[i] & mask[i] != 0 for all 8 words).

A true result means “probably present” (other inserts may have set the same bits). A false is definitive — the value was never inserted.

Source §

impl Block

Source

fn count_ones(self) -> u32

Count the total number of set bits across all 8 words.

Computes popcount on each word separately and sums. Keeping the popcount separate from the OR allows the compiler to batch SIMD popcount instructions (e.g., cnt.16b on ARM NEON) instead of interleaving them with OR operations.