crates/gunnar-bitmap/src/write.rs
//! Writing a `.bitmap` file that stock git reads.
//!
//! The writer is deliberately able to reproduce an existing file byte for byte
//! ([`XorPolicy::Explicit`]) as well as to choose its own XOR bases
//! ([`XorPolicy::PreviousIfSmaller`]). The first is what makes the round-trip
//! test meaningful: re-encoding a git-written file from its *decoded logical
//! bitmaps* and getting the identical bytes back proves the encoder against
//! stock git without git having to be involved. The second is what a real writer
//! does.
//!
//! # Not implemented: the lookup table
//!
//! The writer never emits `BITMAP_OPT_LOOKUP_TABLE`. The reader parses one
//! fine, so a round-trip of a file that has one is byte-identical up to the
//! flags word and then diverges. That is a real gap, not a design choice, and
//! `examples/decode_real` reports it as a `DIFF` rather than hiding it.
use crate::{Bitmap, Error, Ewah};
use gix_hash::ObjectId;
use std::io::Write;
/// How the writer picks an XOR base for each commit bitmap.
#[derive(Clone, Debug, Default)]
pub enum XorPolicy {
/// Store every bitmap whole. Always valid, always bigger.
None,
/// XOR against the immediately preceding entry when that encodes smaller.
///
/// This is what git's own output looks like in practice: of the 106 entries
/// in one fixture written by git 2.53, 103 use an offset of exactly 1.
#[default]
PreviousIfSmaller,
/// Use the given offset for each entry, in order. Offset 0 stores whole.
///
/// Used to reproduce an existing file exactly.
Explicit(Vec<u8>),
}
/// Builds a `.bitmap` file.
pub struct Writer {
object_hash: gix_hash::Kind,
pack_checksum: ObjectId,
types: [Ewah; 4],
commits: Vec<(u32, u8, Bitmap)>,
name_hashes: Option<Vec<u32>>,
xor: XorPolicy,
}
impl Writer {
/// Start a writer for the pack identified by `pack_checksum`.
pub fn new(object_hash: gix_hash::Kind, pack_checksum: ObjectId) -> Self {
Writer {
object_hash,
pack_checksum,
types: [Ewah::new(), Ewah::new(), Ewah::new(), Ewah::new()],
commits: Vec::new(),
name_hashes: None,
xor: XorPolicy::default(),
}
}
fn type_slot(kind: crate::kind::Kind) -> usize {
kind.slot()
}
/// Set a type index from strictly ascending pack positions.
///
/// This routes through the bit-at-a-time builder, which is what git uses for
/// the type indexes. Building them from words instead produces a valid but
/// *different* byte stream, so anything comparing against a real file would
/// fail here and nowhere else.
pub fn type_bitmap(
&mut self,
kind: crate::kind::Kind,
positions: impl IntoIterator<Item = u32>,
) -> Result<&mut Self, Error> {
self.types[Self::type_slot(kind)] = Ewah::from_set_bits(positions)?;
Ok(self)
}
/// Set a type index from an already-encoded bitmap.
pub fn type_bitmap_encoded(&mut self, kind: crate::kind::Kind, ewah: Ewah) -> &mut Self {
self.types[Self::type_slot(kind)] = ewah;
self
}
/// Append one commit's reachability bitmap, resolved (not XOR-compressed).
///
/// `commit_index_pos` is the commit's position in the **`.idx`**, while the
/// bits of `bitmap` are **pack** positions. The format really does mix the
/// two spaces like this; see [`crate::file`].
///
/// Order matters: XOR bases are chosen from earlier entries.
pub fn push_commit(&mut self, commit_index_pos: u32, flags: u8, bitmap: Bitmap) -> &mut Self {
self.commits.push((commit_index_pos, flags, bitmap));
self
}
/// Attach the 32-bit name hash cache, one per object in the pack.
pub fn name_hashes(&mut self, hashes: Vec<u32>) -> &mut Self {
self.name_hashes = Some(hashes);
self
}
/// Choose how XOR bases are picked.
pub fn xor_policy(&mut self, policy: XorPolicy) -> &mut Self {
self.xor = policy;
self
}
/// Serialize to `out`, returning the trailing checksum that was written.
pub fn write_to(&self, out: &mut impl Write) -> Result<ObjectId, Error> {
let mut buf = Vec::new();
buf.extend_from_slice(crate::file::MAGIC);
buf.extend_from_slice(&crate::file::VERSION.to_be_bytes());
let mut flags = crate::file::flags::FULL_DAG;
if self.name_hashes.is_some() {
flags |= crate::file::flags::HASH_CACHE;
}
buf.extend_from_slice(&flags.to_be_bytes());
buf.extend_from_slice(&(self.commits.len() as u32).to_be_bytes());
buf.extend_from_slice(self.pack_checksum.as_slice());
for ewah in &self.types {
ewah.write_to(&mut buf);
}
for (i, (pos, entry_flags, bitmap)) in self.commits.iter().enumerate() {
let (xor_offset, stored) = self.encode_entry(i, bitmap);
buf.extend_from_slice(&pos.to_be_bytes());
buf.push(xor_offset);
buf.push(*entry_flags);
stored.write_to(&mut buf);
}
if let Some(hashes) = &self.name_hashes {
for h in hashes {
buf.extend_from_slice(&h.to_be_bytes());
}
}
let mut hasher = gix_hash::hasher(self.object_hash);
hasher.update(&buf);
let checksum = hasher.try_finalize().map_err(|_| Error::UnexpectedEof {
wanted: "a complete hash over the bitmap body",
})?;
buf.extend_from_slice(checksum.as_slice());
out.write_all(&buf)?;
Ok(checksum)
}
/// Serialize to a fresh buffer.
pub fn to_vec(&self) -> Result<Vec<u8>, Error> {
let mut out = Vec::new();
self.write_to(&mut out)?;
Ok(out)
}
fn encode_entry(&self, i: usize, bitmap: &Bitmap) -> (u8, Ewah) {
let whole = || bitmap.to_ewah();
let against = |offset: u8| -> Ewah {
let base = &self.commits[i - offset as usize].2;
let mut x = bitmap.clone();
x.xor_with(base);
x.to_ewah()
};
match &self.xor {
XorPolicy::None => (0, whole()),
XorPolicy::Explicit(offsets) => match offsets.get(i).copied().unwrap_or(0) {
0 => (0, whole()),
offset if (offset as usize) <= i => (offset, against(offset)),
// An offset that would point before the file cannot be honoured;
// storing whole is the only safe answer and stays readable.
_ => (0, whole()),
},
XorPolicy::PreviousIfSmaller => {
if i == 0 {
return (0, whole());
}
let plain = whole();
let xored = against(1);
if xored.size_in_bytes() < plain.size_in_bytes() {
(1, xored)
} else {
(0, plain)
}
}
}
}
}