crates/gunnar-bitmap/src/file.rs
//! The `.bitmap` file: header, the four type indexes, and one bitmap per
//! selected commit.
//!
//! # Layout
//!
//! ```text
//! "BITM" 4 bytes
//! version 2 bytes, big endian, always 1
//! flags 2 bytes, big endian
//! entry count 4 bytes, big endian
//! pack checksum 20 bytes (SHA-1) or 32 (SHA-256)
//!
//! commits, trees, blobs, tags 4 EWAH bitmaps, in that order
//!
//! per entry, `entry count` times:
//! commit's .idx position 4 bytes, big endian
//! xor offset 1 byte
//! flags 1 byte
//! EWAH bitmap
//!
//! lookup table entry count * 16 bytes, only if BITMAP_OPT_LOOKUP_TABLE
//! name hashes object count * 4 bytes, only if BITMAP_OPT_HASH_CACHE
//! checksum 20 or 32 bytes, over everything above
//! ```
//!
//! The width of the two checksums follows the repository's hash, which is why
//! [`Index::from_bytes`] takes a [`gix_hash::Kind`] rather than assuming 20:
//! there are real SHA-256 `.bitmap` fixtures on this machine and they parse to
//! garbage under a hardcoded SHA-1 header width.
//!
//! # Where the optional sections actually sit
//!
//! The published format documentation describes the lookup table as "the last
//! `N * (4 + 8 + 4)` bytes (preceding the name-hash cache and trailing hash)",
//! which reads as though the table came *after* the cache. It does not. Checked
//! on 2026-08-04 against a `.bitmap` written by git 2.53 with
//! `pack.writeBitmapLookupTable=true`: the table starts immediately after the
//! last entry, and the name-hash cache follows it. Reading it the other way
//! round yields triplets whose offsets point outside the file, which is how the
//! ordering was settled rather than by re-reading the sentence.
//!
//! A triplet's `offset` addresses the **start of the 6-byte entry record**, not
//! the EWAH inside it — also measured, not assumed.
//!
//! # Two position spaces, in one file
//!
//! This is the sharpest edge in the whole format, and nothing in the
//! documentation warns about it:
//!
//! * the **bits inside every bitmap** are *pack* positions — rank by offset in
//! the `.pack`;
//! * the **`commit_index_pos` of an entry** (and of a lookup-table triplet) is
//! an *`.idx`* position — rank by object id.
//!
//! git reads the first with `offset_to_pack_pos()` and the second with
//! `nth_packed_object_id()`. Measured on a git-2.53 fixture, 2026-08-04: reading
//! the 106 entry positions as `.idx` positions yields 106 commits out of 106;
//! reading them as pack positions yields objects scattered across all four
//! types, because in pack order the 199 commits occupy positions 0..=198 only.
//!
//! Neither mistake produces an error. Both produce a well-formed answer about
//! the wrong objects, which is why [`crate::PackOrder`] exists and why the field
//! is named `commit_index_pos` rather than `commit_pos`.
use crate::{Bitmap, Error, Ewah};
use gix_hash::ObjectId;
/// The four bytes every bitmap index starts with.
pub const MAGIC: &[u8; 4] = b"BITM";
/// The only version that exists.
pub const VERSION: u16 = 1;
/// Header flag bits.
pub mod flags {
/// Required. The pack or MIDX is closed under parent links.
pub const FULL_DAG: u16 = 0x1;
/// A 32-bit name hash per object is appended near the end of the file.
pub const HASH_CACHE: u16 = 0x4;
/// A `(commit_index_pos, offset, xor_row)` table is appended, so a reader can jump
/// straight to one commit's bitmap instead of parsing every earlier entry.
pub const LOOKUP_TABLE: u16 = 0x10;
}
/// One stored commit bitmap, exactly as it appears on disk.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Entry {
/// Position of this commit in the **`.idx`**, i.e. its rank by object id.
///
/// Deliberately not the same space as the bits inside [`Entry::bitmap`],
/// which are pack positions. See the module documentation.
pub commit_index_pos: u32,
/// How many entries back the XOR base is; 0 means the bitmap is stored whole.
pub xor_offset: u8,
/// Entry flags. `0x1` means "reusable when rebuilding".
pub flags: u8,
/// The bitmap **as stored** — still XOR-compressed if `xor_offset != 0`.
pub bitmap: Ewah,
}
/// One row of the optional commit lookup table.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Triplet {
/// `.idx` position of the commit this row describes, like
/// [`Entry::commit_index_pos`].
pub commit_index_pos: u32,
/// Byte offset of the entry record, counted from the start of the file.
pub offset: u64,
/// Row of the triplet whose bitmap this one is XOR-compressed against, or
/// `u32::MAX` for none.
pub xor_row: u32,
}
/// A parsed `.bitmap` index.
#[derive(Clone, Debug)]
pub struct Index {
version: u16,
flags: u16,
object_hash: gix_hash::Kind,
pack_checksum: ObjectId,
/// commits, trees, blobs, tags — in that order.
types: [Ewah; 4],
entries: Vec<Entry>,
lookup_table: Option<Vec<Triplet>>,
name_hashes: Option<Vec<u32>>,
num_objects: Option<u32>,
checksum: ObjectId,
checksum_matches: bool,
}
impl Index {
/// Read and parse a `.bitmap` from disk.
pub fn at(
path: impl AsRef<std::path::Path>,
object_hash: gix_hash::Kind,
) -> Result<Self, Error> {
let data = std::fs::read(path)?;
Index::from_bytes(&data, object_hash)
}
/// Parse a `.bitmap` from memory.
pub fn from_bytes(data: &[u8], object_hash: gix_hash::Kind) -> Result<Self, Error> {
let hash_len = object_hash.len_in_bytes();
let head = data.get(..12).ok_or(Error::UnexpectedEof {
wanted: "bitmap header",
})?;
let magic: [u8; 4] = head[..4].try_into().expect("4 bytes");
if &magic != MAGIC {
return Err(Error::Magic {
expected: MAGIC,
actual: magic,
});
}
let version = u16::from_be_bytes(head[4..6].try_into().expect("2 bytes"));
if version != VERSION {
return Err(Error::Version { actual: version });
}
let flags = u16::from_be_bytes(head[6..8].try_into().expect("2 bytes"));
if flags & flags::FULL_DAG == 0 {
return Err(Error::MissingFullDag { flags });
}
let entry_count = u32::from_be_bytes(head[8..12].try_into().expect("4 bytes")) as usize;
let mut at = 12;
let pack_checksum = read_hash(data, &mut at, hash_len, "pack checksum")?;
let mut types = [Ewah::new(), Ewah::new(), Ewah::new(), Ewah::new()];
for slot in &mut types {
let (ewah, used) = Ewah::from_bytes(data.get(at..).ok_or(Error::UnexpectedEof {
wanted: "type bitmap",
})?)?;
*slot = ewah;
at += used;
}
let mut entries = Vec::with_capacity(entry_count);
for _ in 0..entry_count {
let head = data.get(at..at + 6).ok_or(Error::UnexpectedEof {
wanted: "bitmap entry header",
})?;
let commit_index_pos = u32::from_be_bytes(head[..4].try_into().expect("4 bytes"));
let xor_offset = head[4];
let entry_flags = head[5];
at += 6;
let (bitmap, used) = Ewah::from_bytes(data.get(at..).ok_or(Error::UnexpectedEof {
wanted: "entry bitmap",
})?)?;
at += used;
entries.push(Entry {
commit_index_pos,
xor_offset,
flags: entry_flags,
bitmap,
});
}
// Every xor base must point backwards and land inside the file, or
// resolution would either loop forever or read a bitmap that is not
// there. Rejecting here means `resolve` cannot fail later.
for (i, entry) in entries.iter().enumerate() {
if entry.xor_offset != 0 && (entry.xor_offset as usize) > i {
return Err(Error::XorBeforeStart {
entry: i,
offset: entry.xor_offset,
});
}
}
let lookup_table = if flags & flags::LOOKUP_TABLE != 0 {
let mut rows = Vec::with_capacity(entry_count);
for _ in 0..entry_count {
let row = data.get(at..at + 16).ok_or(Error::UnexpectedEof {
wanted: "lookup table triplet",
})?;
rows.push(Triplet {
commit_index_pos: u32::from_be_bytes(row[..4].try_into().expect("4 bytes")),
offset: u64::from_be_bytes(row[4..12].try_into().expect("8 bytes")),
xor_row: u32::from_be_bytes(row[12..16].try_into().expect("4 bytes")),
});
at += 16;
}
Some(rows)
} else {
None
};
let tail = data
.len()
.checked_sub(at + hash_len)
.ok_or(Error::UnexpectedEof {
wanted: "bitmap trailing checksum",
})?;
let (name_hashes, num_objects) = if flags & flags::HASH_CACHE != 0 {
if tail % 4 != 0 {
return Err(Error::TrailingBytes { tail });
}
let count = tail / 4;
let mut hashes = Vec::with_capacity(count);
for i in 0..count {
let b = &data[at + i * 4..at + i * 4 + 4];
hashes.push(u32::from_be_bytes(b.try_into().expect("4 bytes")));
}
at += tail;
(Some(hashes), Some(count as u32))
} else {
if tail != 0 {
return Err(Error::TrailingBytes { tail });
}
(None, None)
};
let body_end = at;
let checksum = read_hash(data, &mut at, hash_len, "bitmap checksum")?;
// Computed eagerly, checked on request. Without it a truncated file is
// indistinguishable from a valid smaller one: the object count is
// derived from how many bytes are left, not stated anywhere, so lopping
// the tail off yields a file that parses cleanly and reports fewer
// objects. Measured 2026-08-04: truncating a 28 520-byte bitmap to
// 14 260 parsed as a perfectly good index over 571 objects instead of
// 4136. git never notices either, because it validates the count
// against the pack it already has open; a standalone reader has no pack.
let mut hasher = gix_hash::hasher(object_hash);
hasher.update(&data[..body_end]);
let checksum_matches = hasher
.try_finalize()
.map(|c| c == checksum)
.unwrap_or(false);
Ok(Index {
version,
flags,
object_hash,
pack_checksum,
types,
entries,
lookup_table,
name_hashes,
num_objects,
checksum,
checksum_matches,
})
}
/// Always 1.
pub fn version(&self) -> u16 {
self.version
}
/// Raw header flags; see [`flags`].
pub fn flags(&self) -> u16 {
self.flags
}
/// The hash this index was parsed with.
pub fn object_hash(&self) -> gix_hash::Kind {
self.object_hash
}
/// Checksum of the pack or MIDX this index belongs to.
pub fn pack_checksum(&self) -> &gix_hash::oid {
&self.pack_checksum
}
/// Checksum trailing the bitmap file itself.
pub fn checksum(&self) -> &gix_hash::oid {
&self.checksum
}
/// Whether the trailing checksum matches the file body.
///
/// Following gix convention this is a query rather than a parse failure, so
/// that a caller can still inspect a damaged file. Note git itself never
/// checks this field.
pub fn verify_checksum(&self) -> Result<(), Error> {
if self.checksum_matches {
Ok(())
} else {
Err(Error::ChecksumMismatch {
expected: self.checksum,
})
}
}
/// Cross-check the derived object count against the pack this index belongs
/// to.
///
/// The count is inferred from the size of the name-hash cache, so it is only
/// as trustworthy as the file length. Call this whenever the pack is at hand.
pub fn verify_object_count(&self, pack_objects: u32) -> Result<(), Error> {
match self.num_objects {
Some(n) if n != pack_objects => Err(Error::ObjectCountMismatch {
in_bitmap: n,
in_pack: pack_objects,
}),
_ => Ok(()),
}
}
/// The stored commit entries, in file order.
pub fn entries(&self) -> &[Entry] {
&self.entries
}
/// The optional lookup table, if the file carries one.
pub fn lookup_table(&self) -> Option<&[Triplet]> {
self.lookup_table.as_deref()
}
/// The optional per-object name hash cache.
pub fn name_hashes(&self) -> Option<&[u32]> {
self.name_hashes.as_deref()
}
/// Objects in the underlying pack, when the file carries a hash cache to
/// derive it from.
pub fn num_objects(&self) -> Option<u32> {
self.num_objects
}
/// The type index for `kind`, telling which pack positions hold that type.
pub fn type_bitmap(&self, kind: crate::kind::Kind) -> &Ewah {
use crate::kind::Kind::*;
match kind {
Commit => &self.types[0],
Tree => &self.types[1],
Blob => &self.types[2],
Tag => &self.types[3],
}
}
/// The four type indexes as stored: commits, trees, blobs, tags.
pub fn type_bitmaps(&self) -> &[Ewah; 4] {
&self.types
}
/// Resolve entry `index` into a plain bitmap, undoing XOR compression.
///
/// An entry with `xor_offset == y` stores `actual XOR resolved(index - y)`,
/// and the base may itself be XOR-compressed, so this walks the chain to a
/// whole bitmap and folds back down. Real bitmaps lean on this heavily: in
/// the fixture packs on this machine, 103 of 106 entries in one file were
/// XOR-compressed against their immediate predecessor.
///
/// The walk is iterative rather than recursive because the chain length is
/// attacker-controlled data; git caps the offset at 160 but the *chain* has
/// no such cap and a recursive resolver would blow the stack on a crafted
/// file.
pub fn resolve(&self, index: usize) -> Option<Bitmap> {
let mut chain = Vec::new();
let mut at = index;
loop {
let entry = self.entries.get(at)?;
chain.push(at);
if entry.xor_offset == 0 {
break;
}
// Proved non-underflowing while parsing.
at -= entry.xor_offset as usize;
}
let mut acc = Bitmap::from_ewah(&self.entries[*chain.last().expect("non-empty")].bitmap);
for &link in chain.iter().rev().skip(1) {
acc.xor_ewah(&self.entries[link].bitmap);
}
Some(acc)
}
/// Index of the entry for the commit at **`.idx` position** `pos`, if any.
pub fn entry_index_of_commit(&self, pos: u32) -> Option<usize> {
// A linear scan, deliberately: entry counts here are in the hundreds to
// low thousands, and a map would have to be built at parse time for
// every caller including the ones that only round-trip the file.
// `Index::commit_index_positions` exists for callers that want to build their
// own map once.
self.entries.iter().position(|e| e.commit_index_pos == pos)
}
/// The resolved bitmap for the commit at **`.idx` position** `pos`.
///
/// The returned bitmap is addressed by *pack* position, not `.idx` position.
pub fn bitmap_for_commit(&self, pos: u32) -> Option<Bitmap> {
self.resolve(self.entry_index_of_commit(pos)?)
}
/// `.idx` positions of every commit that has a stored bitmap.
pub fn commit_index_positions(&self) -> impl Iterator<Item = u32> + '_ {
self.entries.iter().map(|e| e.commit_index_pos)
}
}
fn read_hash(
data: &[u8],
at: &mut usize,
len: usize,
wanted: &'static str,
) -> Result<ObjectId, Error> {
let bytes = data
.get(*at..*at + len)
.ok_or(Error::UnexpectedEof { wanted })?;
*at += len;
ObjectId::try_from(bytes).map_err(|_| Error::UnexpectedEof { wanted })
}