crates/gunnar-bitmap/src/bitmap.rs
//! An uncompressed bitmap over pack positions, and the set algebra a fetch is
//! made of.
//!
//! "Pack position" means rank by offset within the `.pack`, not `.idx` position;
//! see [`crate::pack_order`] before turning any of these bits into an object id.
//!
//! The whole point of a reachability bitmap is that `want`/`have` becomes
//! `OR` then `AND NOT` instead of a commit graph walk. That is this file.
//!
//! Every operation that takes an [`Ewah`] consumes it in compressed form, run by
//! run. Expanding first and then operating would make a run of a million zero
//! words cost a million iterations, which is the cost the format exists to
//! avoid.
use crate::ewah::{Chunk, Ewah, BITS_IN_WORD};
use crate::words::{self, Op};
/// A dense bitmap addressed by pack position.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Bitmap {
words: Vec<u64>,
}
impl Bitmap {
/// An empty bitmap with no words.
pub fn new() -> Self {
Bitmap::default()
}
/// An all-zero bitmap with room for `bits` bits.
pub fn with_capacity_bits(bits: usize) -> Self {
Bitmap {
words: vec![0; bits.div_ceil(BITS_IN_WORD)],
}
}
/// Expand a compressed bitmap.
///
/// The result has exactly as many words as the stream describes, not
/// `bit_size / 64`; see [`crate::ewah`] for why those differ.
pub fn from_ewah(ewah: &Ewah) -> Self {
Bitmap {
words: ewah.words().collect(),
}
}
/// The backing words, low position first.
pub fn words(&self) -> &[u64] {
&self.words
}
/// Number of words, i.e. the addressable range divided by 64.
pub fn word_len(&self) -> usize {
self.words.len()
}
/// Whether the bit at `pos` is set. Out of range reads as unset.
pub fn get(&self, pos: u32) -> bool {
let (w, b) = split(pos);
self.words.get(w).is_some_and(|word| word >> b & 1 == 1)
}
/// Set the bit at `pos`, growing the bitmap if needed.
pub fn set(&mut self, pos: u32) {
let (w, b) = split(pos);
if w >= self.words.len() {
self.words.resize(w + 1, 0);
}
self.words[w] |= 1 << b;
}
/// Clear the bit at `pos`. Out of range is a no-op.
pub fn unset(&mut self, pos: u32) {
let (w, b) = split(pos);
if let Some(word) = self.words.get_mut(w) {
*word &= !(1 << b);
}
}
/// Number of set bits.
pub fn count_ones(&self) -> u64 {
self.words.iter().map(|w| w.count_ones() as u64).sum()
}
/// Whether no bit is set.
pub fn is_empty(&self) -> bool {
self.words.iter().all(|w| *w == 0)
}
/// Iterate set bit positions in ascending order.
pub fn iter_set_bits(&self) -> impl Iterator<Item = u32> + '_ {
self.words.iter().enumerate().flat_map(|(wi, word)| {
let mut rest = *word;
std::iter::from_fn(move || {
if rest == 0 {
return None;
}
let b = rest.trailing_zeros();
rest &= rest - 1;
Some((wi * BITS_IN_WORD) as u32 + b)
})
})
}
fn grow_to(&mut self, words: usize) {
if self.words.len() < words {
self.words.resize(words, 0);
}
}
/// `self |= other`.
pub fn or_with(&mut self, other: &Bitmap) {
self.grow_to(other.words.len());
words::apply(Op::Or, &mut self.words, &other.words);
}
/// `self &= !other`. This is the exclusion half of a fetch.
///
/// Does not grow: `x &= !0` is the identity, so words past the end of
/// `other` are already correct and allocating them would only make the
/// answer bigger, never different.
pub fn and_not_with(&mut self, other: &Bitmap) {
words::apply(Op::AndNot, &mut self.words, &other.words);
}
/// `self &= other`.
pub fn and_with(&mut self, other: &Bitmap) {
// `x &= 0` past the end of `other` clears, so the tail is zeroed
// explicitly rather than left alone. Growing first keeps the word
// length equal to the old behaviour's, which `to_ewah` can see.
self.grow_to(other.words.len());
words::apply(Op::And, &mut self.words, &other.words);
if self.words.len() > other.words.len() {
self.words[other.words.len()..].fill(0);
}
}
/// `self ^= other`.
pub fn xor_with(&mut self, other: &Bitmap) {
self.grow_to(other.words.len());
words::apply(Op::Xor, &mut self.words, &other.words);
}
/// `self |= ewah`, walking the compressed stream directly.
pub fn or_ewah(&mut self, ewah: &Ewah) {
self.apply_ewah(ewah, Op::Or)
}
/// `self ^= ewah`, walking the compressed stream directly.
///
/// This is what resolves an XOR-compressed entry against its base.
pub fn xor_ewah(&mut self, ewah: &Ewah) {
self.apply_ewah(ewah, Op::Xor)
}
/// `self &= !ewah`, walking the compressed stream directly.
pub fn and_not_ewah(&mut self, ewah: &Ewah) {
self.apply_ewah(ewah, Op::AndNot)
}
fn apply_ewah(&mut self, ewah: &Ewah, op: Op) {
let mut at = 0usize;
for chunk in ewah.chunks() {
match chunk {
Chunk::Run {
value: false,
count,
} => {
match op {
// Zero words are the identity for these three, so the
// whole run is one addition. This is the fast path that
// makes bitmap arithmetic worth doing at all.
Op::Or | Op::Xor | Op::AndNot => {}
// ...but NOT for AND, where a zero run clears. Skipping
// it here would leave the bits set and return a
// *larger* set that looks like a successful answer.
Op::And => {
let end = (at + count).min(self.words.len());
if at < end {
self.words[at..end].fill(0);
}
}
}
at += count;
}
Chunk::Run { value: true, count } => {
match op {
// OR with all-ones only needs to touch words that exist
// or that we are about to create.
Op::Or => {
self.grow_to(at + count);
self.words[at..at + count].fill(u64::MAX);
}
Op::Xor => {
self.grow_to(at + count);
for w in &mut self.words[at..at + count] {
*w = !*w;
}
}
Op::AndNot => {
let end = (at + count).min(self.words.len());
if at < end {
self.words[at..end].fill(0);
}
}
// All-ones is the identity for AND.
Op::And => {}
}
at += count;
}
Chunk::Literals(literals) => {
match op {
// A literal can set a bit past the current end, so the
// two growing operations reserve first. `AndNot` and
// `And` can only ever clear, so a word that does not
// exist is already the right answer.
Op::Or | Op::Xor => self.grow_to(at + literals.len()),
Op::AndNot | Op::And => {}
}
// Clamped rather than `get_mut`-and-`break`: a loop with an
// early exit cannot be vectorised at all. `at` may itself be
// past the end once `grow_to` has been skipped above.
//
// There is no vector dispatch here, and `src/words.rs`
// carries the measurement that settled it: 95.0% of real
// literal runs are shorter than one AVX2 register.
let from = at.min(self.words.len());
words::apply(op, &mut self.words[from..], literals);
at += literals.len();
}
}
}
}
/// Compress with the word-at-a-time builder, git's `bitmap_to_ewah`.
pub fn to_ewah(&self) -> Ewah {
Ewah::from_words(self.words.iter().copied())
}
/// Drop trailing all-zero words.
///
/// Never call this before comparing against a git-written bitmap: git keeps
/// the trailing words its allocation happened to have, so trimming changes
/// the bytes even though it does not change the set.
pub fn trim(&mut self) {
while self.words.last() == Some(&0) {
self.words.pop();
}
}
}
fn split(pos: u32) -> (usize, u32) {
(pos as usize / BITS_IN_WORD, pos % BITS_IN_WORD as u32)
}