crates/gunnar-bitmap/src/ewah.rs
//! EWAH: Enhanced Word-Aligned Hybrid, in the exact serialization git uses.
//!
//! # The layout, as it is actually on disk
//!
//! Taken from `Documentation/technical/bitmap-format.txt` and then *checked
//! against every `.bitmap` file on this machine*, because a spec read is a
//! hypothesis. All integers are big-endian ("network byte order"):
//!
//! ```text
//! 4 bytes number of bits of the resulting UNCOMPRESSED bitmap
//! 4 bytes number of 64-bit words of the COMPRESSED stream that follows
//! N*8 bytes the compressed stream
//! 4 bytes word index of the current RLW
//! ```
//!
//! The compressed stream is a concatenation of chunks. Each chunk is one run
//! length word (RLW) followed by zero or more literal words:
//!
//! ```text
//! H L_1 L_2 ... L_M
//! ```
//!
//! `H` packs, from the *low* order bits upward:
//!
//! | bits | meaning |
//! |---------|----------------------------------|
//! | 0 | the repeated bit `B` |
//! | 1..=32 | repetition count `K` (32 bits) |
//! | 33..=63 | literal word count `M` (31 bits) |
//!
//! and expands to `K` words of all-`B` followed by the `M` literal words. Within
//! a word, bit 0 comes first in the stream.
//!
//! # Two compressors, not one — and the bytes differ
//!
//! This is the part a from-the-spec implementation gets wrong, and it is why
//! this module has two builders instead of one.
//!
//! git appends to an EWAH by two different routes, and they do not produce the
//! same bytes for the same set of bits:
//!
//! * [`Builder::push_word`] mirrors git's `ewah_add()`: whole 64-bit words at a
//! time. It is what `bitmap_to_ewah()` uses, so it is how every **per-commit
//! reachability bitmap** in a `.bitmap` file was written. `bit_size` ends at
//! `64 * words`.
//! * [`Builder::set_bit`] mirrors git's `ewah_set()`: one ascending bit at a
//! time, including the "we just completed a word of all ones, fold it back
//! into a run" collapse. It is how the four **type index bitmaps** (commits,
//! trees, blobs, tags) were written. `bit_size` ends at *the last bit set plus
//! one*, which is generally not a multiple of 64.
//!
//! The difference is not cosmetic. Measured on 2026-08-04 over the 52 real
//! `.bitmap` files stock git had produced on this machine: feeding the
//! word-at-a-time builder with the decoded words of a type bitmap reproduced 0
//! of 208 of them byte-for-byte, while the bit-at-a-time builder reproduced
//! 208/208. The word-at-a-time builder reproduced 4716/4716 of the per-commit
//! bitmaps. A single-compressor implementation cannot round-trip a real file,
//! and — worse — would look completely correct to any test written against its
//! own output.
use crate::Error;
/// Bits in one EWAH word. The format is defined in terms of 64-bit words and
/// this is not a tunable.
pub const BITS_IN_WORD: usize = 64;
const RLW_RUNNING_BITS: u32 = 32;
const RLW_LITERAL_BITS: u32 = 64 - 1 - RLW_RUNNING_BITS; // 31
const RLW_LARGEST_RUNNING_COUNT: u64 = (1 << RLW_RUNNING_BITS) - 1;
const RLW_LARGEST_LITERAL_COUNT: u64 = (1 << RLW_LITERAL_BITS) - 1;
const ALL_ONES: u64 = u64::MAX;
/// A compressed EWAH bitmap, holding exactly what is on disk.
///
/// Cloning is a `Vec` clone; the type is deliberately plain data so that a
/// decoded file can be re-encoded and compared byte for byte.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Ewah {
/// Number of bits of the uncompressed bitmap, as stored.
///
/// Note this is *not* redundant with the stream: for a bitmap written by
/// git's `ewah_set()` it is the highest set bit plus one, so the stream
/// expands to more bits than this. Round-tripping requires keeping it.
bit_size: u32,
/// The compressed stream, one entry per 64-bit word.
buffer: Vec<u64>,
/// Word index into `buffer` of the most recent RLW.
rlw: u32,
}
impl Default for Ewah {
fn default() -> Self {
Self::new()
}
}
impl Ewah {
/// An empty bitmap.
///
/// The buffer holds one zero RLW rather than being empty, matching git's
/// `ewah_new()`. It is not a detail: an empty type bitmap (a pack with no
/// tags, say) serializes as `bit_size=0, word_count=1, words=[0], rlw=0`,
/// and that is what every real fixture on this machine contains. An
/// implementation starting from a truly empty buffer writes `word_count=0`
/// and no longer matches git.
pub fn new() -> Self {
Ewah {
bit_size: 0,
buffer: vec![0],
rlw: 0,
}
}
/// Number of bits in the uncompressed bitmap, as recorded on disk.
pub fn bit_size(&self) -> u32 {
self.bit_size
}
/// Number of 64-bit words in the compressed stream.
pub fn compressed_words(&self) -> usize {
self.buffer.len()
}
/// Size in bytes this bitmap occupies on disk.
pub fn size_in_bytes(&self) -> usize {
4 + 4 + self.buffer.len() * 8 + 4
}
/// Decode one EWAH bitmap from the front of `data`.
///
/// Returns the bitmap and how many bytes it consumed, because `.bitmap`
/// files store these back to back with no length prefix around them.
pub fn from_bytes(data: &[u8]) -> Result<(Ewah, usize), Error> {
let bit_size = be_u32(data, 0).ok_or(Error::UnexpectedEof {
wanted: "ewah bit size",
})?;
let word_count = be_u32(data, 4).ok_or(Error::UnexpectedEof {
wanted: "ewah word count",
})? as usize;
let data_len = word_count.checked_mul(8).ok_or(Error::CorruptEwah {
reason: "compressed word count overflows a byte length",
})?;
let end = 8usize.checked_add(data_len).ok_or(Error::CorruptEwah {
reason: "compressed word count overflows a byte length",
})?;
if data.len() < end + 4 {
return Err(Error::UnexpectedEof {
wanted: "ewah compressed stream",
});
}
let mut buffer = Vec::with_capacity(word_count);
for i in 0..word_count {
let at = 8 + i * 8;
buffer.push(u64::from_be_bytes(
data[at..at + 8].try_into().expect("8 bytes"),
));
}
let rlw = be_u32(data, end).expect("length checked above");
if word_count == 0 {
// git's reader would set `self->rlw = buffer + 0` on an empty
// buffer and then read it. Refuse instead of pointing at nothing.
return Err(Error::CorruptEwah {
reason: "compressed stream has no words",
});
}
if rlw as usize >= word_count {
return Err(Error::CorruptEwah {
reason: "rlw position is outside the stream",
});
}
let ewah = Ewah {
bit_size,
buffer,
rlw,
};
ewah.validate()?;
Ok((ewah, end + 4))
}
/// Walk the chunk structure once, rejecting a stream that runs off its end.
///
/// Without this, a corrupt literal count makes every later reader either
/// panic on a slice or silently read a truncated bitmap. A truncated bitmap
/// is the dangerous one: it is a *smaller* object set, and a server that
/// trusted it would answer a fetch with objects missing.
fn validate(&self) -> Result<(), Error> {
let mut i = 0usize;
let mut seen_rlw = false;
while i < self.buffer.len() {
if i == self.rlw as usize {
seen_rlw = true;
}
let literals = rlw_literal_words(self.buffer[i]) as usize;
i += 1;
i = i.checked_add(literals).ok_or(Error::CorruptEwah {
reason: "literal word count overflows the stream length",
})?;
if i > self.buffer.len() {
return Err(Error::CorruptEwah {
reason: "a chunk claims more literal words than the stream holds",
});
}
}
if !seen_rlw {
return Err(Error::CorruptEwah {
reason: "the recorded rlw position is not the start of a chunk",
});
}
Ok(())
}
/// Append the on-disk form to `out`.
pub fn write_to(&self, out: &mut Vec<u8>) {
out.extend_from_slice(&self.bit_size.to_be_bytes());
out.extend_from_slice(&(self.buffer.len() as u32).to_be_bytes());
for word in &self.buffer {
out.extend_from_slice(&word.to_be_bytes());
}
out.extend_from_slice(&self.rlw.to_be_bytes());
}
/// The on-disk form as a fresh buffer.
pub fn to_vec(&self) -> Vec<u8> {
let mut out = Vec::with_capacity(self.size_in_bytes());
self.write_to(&mut out);
out
}
/// Iterate the chunks of the compressed stream without expanding runs.
///
/// This is what makes set operations cheap: a run of a million zero words is
/// one step, not a million. Materializing to words and then OR-ing would
/// throw away the entire point of the format.
pub fn chunks(&self) -> Chunks<'_> {
Chunks {
buffer: &self.buffer,
at: 0,
pending: None,
}
}
/// Iterate the uncompressed 64-bit words.
///
/// The count is decided by the stream, not by [`Ewah::bit_size`]; see the
/// module documentation for why those disagree for type bitmaps.
pub fn words(&self) -> Words<'_> {
Words {
chunks: self.chunks(),
run: None,
literals: [].iter(),
}
}
/// Number of uncompressed words the stream expands to.
pub fn word_len(&self) -> usize {
self.chunks()
.map(|c| match c {
Chunk::Run { count, .. } => count,
Chunk::Literals(words) => words.len(),
})
.sum()
}
/// Number of set bits, counted without expanding the runs.
pub fn count_ones(&self) -> u64 {
self.chunks()
.map(|c| match c {
Chunk::Run { value: true, count } => count as u64 * BITS_IN_WORD as u64,
Chunk::Run { value: false, .. } => 0,
Chunk::Literals(words) => words.iter().map(|w| w.count_ones() as u64).sum(),
})
.sum()
}
/// Compress a sequence of uncompressed words, exactly as git's `ewah_add()`.
///
/// This is the right builder for a per-commit reachability bitmap.
pub fn from_words(words: impl IntoIterator<Item = u64>) -> Ewah {
let mut b = Builder::new();
for w in words {
b.push_word(w);
}
b.finish()
}
/// Compress from strictly ascending set-bit positions, as git's `ewah_set()`.
///
/// This is the right builder for a type index bitmap. Positions must be
/// strictly increasing; git asserts the same and there is no ordering-free
/// path through its encoder.
pub fn from_set_bits(bits: impl IntoIterator<Item = u32>) -> Result<Ewah, Error> {
let mut b = Builder::new();
for bit in bits {
b.set_bit(bit)?;
}
Ok(b.finish())
}
}
/// One chunk of a compressed stream.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Chunk<'a> {
/// `count` consecutive words that are all-ones (`value == true`) or
/// all-zeros.
Run {
/// The bit every word in the run is filled with.
value: bool,
/// How many 64-bit words the run covers.
count: usize,
},
/// Literal words, stored verbatim.
Literals(&'a [u64]),
}
/// Iterator over [`Chunk`]s. See [`Ewah::chunks`].
pub struct Chunks<'a> {
buffer: &'a [u64],
at: usize,
pending: Option<&'a [u64]>,
}
impl<'a> Iterator for Chunks<'a> {
type Item = Chunk<'a>;
fn next(&mut self) -> Option<Chunk<'a>> {
if let Some(literals) = self.pending.take() {
if !literals.is_empty() {
return Some(Chunk::Literals(literals));
}
}
while self.at < self.buffer.len() {
let header = self.buffer[self.at];
self.at += 1;
let literals = rlw_literal_words(header) as usize;
// `Ewah::validate` has already proved this slice is in bounds.
let lit = &self.buffer[self.at..self.at + literals];
self.at += literals;
let run = rlw_running_len(header) as usize;
if run > 0 {
self.pending = Some(lit);
return Some(Chunk::Run {
value: rlw_run_bit(header),
count: run,
});
}
if !lit.is_empty() {
return Some(Chunk::Literals(lit));
}
// A chunk with neither a run nor literals carries no bits; skip it.
// The trailing empty RLW of an empty bitmap is exactly this case.
}
None
}
}
/// Iterator over the uncompressed words. See [`Ewah::words`].
pub struct Words<'a> {
chunks: Chunks<'a>,
run: Option<(u64, usize)>,
literals: std::slice::Iter<'a, u64>,
}
impl Iterator for Words<'_> {
type Item = u64;
fn next(&mut self) -> Option<u64> {
loop {
if let Some((word, left)) = self.run.as_mut() {
if *left > 0 {
*left -= 1;
return Some(*word);
}
self.run = None;
}
if let Some(w) = self.literals.next() {
return Some(*w);
}
match self.chunks.next()? {
Chunk::Run { value, count } => {
self.run = Some((if value { ALL_ONES } else { 0 }, count))
}
Chunk::Literals(words) => self.literals = words.iter(),
}
}
}
}
/// Builds a compressed stream, mirroring git's `struct ewah_bitmap` writer.
///
/// Both entry points are ports of git's own functions rather than a re-derivation
/// from the spec, because the spec describes what a *valid* stream looks like and
/// says nothing about which of the many valid encodings git picks. Only a port
/// reproduces the bytes.
pub struct Builder {
buffer: Vec<u64>,
rlw: usize,
bit_size: u64,
}
impl Default for Builder {
fn default() -> Self {
Self::new()
}
}
impl Builder {
/// An empty builder, matching git's `ewah_new()`.
pub fn new() -> Self {
Builder {
buffer: vec![0],
rlw: 0,
bit_size: 0,
}
}
fn literal_words(&self) -> u64 {
rlw_literal_words(self.buffer[self.rlw])
}
fn running_len(&self) -> u64 {
rlw_running_len(self.buffer[self.rlw])
}
fn run_bit(&self) -> bool {
rlw_run_bit(self.buffer[self.rlw])
}
fn set_run_bit(&mut self, value: bool) {
let w = &mut self.buffer[self.rlw];
*w = (*w & !1) | u64::from(value);
}
fn set_running_len(&mut self, len: u64) {
let w = &mut self.buffer[self.rlw];
*w = (*w & !(RLW_LARGEST_RUNNING_COUNT << 1)) | ((len & RLW_LARGEST_RUNNING_COUNT) << 1);
}
fn set_literal_words(&mut self, len: u64) {
let w = &mut self.buffer[self.rlw];
*w = (*w & !(RLW_LARGEST_LITERAL_COUNT << (1 + RLW_RUNNING_BITS)))
| ((len & RLW_LARGEST_LITERAL_COUNT) << (1 + RLW_RUNNING_BITS));
}
fn push_rlw(&mut self) {
self.buffer.push(0);
self.rlw = self.buffer.len() - 1;
}
/// git `add_empty_word`.
fn add_empty_word(&mut self, value: bool) {
let no_literal = self.literal_words() == 0;
let run_len = self.running_len();
if no_literal && run_len == 0 {
self.set_run_bit(value);
}
if no_literal && self.run_bit() == value && run_len < RLW_LARGEST_RUNNING_COUNT {
self.set_running_len(run_len + 1);
} else {
self.push_rlw();
self.set_run_bit(value);
self.set_running_len(1);
}
}
/// git `add_literal`.
fn add_literal(&mut self, word: u64) {
let current = self.literal_words();
if current >= RLW_LARGEST_LITERAL_COUNT {
self.push_rlw();
self.set_literal_words(1);
} else {
self.set_literal_words(current + 1);
}
self.buffer.push(word);
}
/// Append one uncompressed word. git `ewah_add`.
pub fn push_word(&mut self, word: u64) {
self.bit_size += BITS_IN_WORD as u64;
match word {
0 => self.add_empty_word(false),
ALL_ONES => self.add_empty_word(true),
w => self.add_literal(w),
}
}
/// Set one bit. git `ewah_set`.
///
/// Positions must arrive strictly ascending. git asserts `i >= bit_size`;
/// this returns an error rather than aborting, because the input to a bitmap
/// writer is often a caller's iteration order and getting that wrong should
/// be diagnosable rather than fatal.
pub fn set_bit(&mut self, bit: u32) -> Result<(), Error> {
let i = bit as u64;
if i < self.bit_size {
return Err(Error::BitsOutOfOrder {
bit,
bit_size: self.bit_size,
});
}
let dist = div_round_up(i + 1, BITS_IN_WORD as u64)
- div_round_up(self.bit_size, BITS_IN_WORD as u64);
self.bit_size = i + 1;
let in_word = 1u64 << (i % BITS_IN_WORD as u64);
if dist > 0 {
if dist > 1 {
for _ in 0..dist - 1 {
self.add_empty_word(false);
}
}
self.add_literal(in_word);
return Ok(());
}
if self.literal_words() == 0 {
// The bit lands inside the run this RLW is currently describing:
// shorten the run by one word and re-add that word as a literal.
self.set_running_len(self.running_len() - 1);
self.add_literal(in_word);
return Ok(());
}
let last = self.buffer.len() - 1;
self.buffer[last] |= in_word;
if self.buffer[last] == ALL_ONES {
// That literal just became a word of all ones; fold it into a run.
self.buffer[last] = 0;
self.buffer.pop();
let literals = self.literal_words();
self.set_literal_words(literals - 1);
self.add_empty_word(true);
}
Ok(())
}
/// Finish, producing the bitmap in its on-disk shape.
pub fn finish(self) -> Ewah {
Ewah {
bit_size: self.bit_size as u32,
buffer: self.buffer,
rlw: self.rlw as u32,
}
}
}
fn div_round_up(a: u64, b: u64) -> u64 {
a.div_ceil(b)
}
#[inline]
fn rlw_run_bit(word: u64) -> bool {
word & 1 != 0
}
#[inline]
fn rlw_running_len(word: u64) -> u64 {
(word >> 1) & RLW_LARGEST_RUNNING_COUNT
}
#[inline]
fn rlw_literal_words(word: u64) -> u64 {
word >> (1 + RLW_RUNNING_BITS)
}
fn be_u32(data: &[u8], at: usize) -> Option<u32> {
let bytes = data.get(at..at + 4)?;
Some(u32::from_be_bytes(bytes.try_into().expect("4 bytes")))
}