use super::bitset::Bitset;
use super::ewah::Ewah;
use super::{BitmapEntryOffset, IndexPosition};
use knot_git::GitError;
const OPT_LOOKUP_TABLE: u16 = 0x10;
const OPT_HASH_CACHE: u16 = 0x4;
const TRIPLET_LEN: usize = 16;
pub(crate) struct Bitmaps<'a> {
body: &'a [u8],
types: &'a [u8],
table: Vec<(IndexPosition, BitmapEntryOffset, u32)>,
num_objects: usize,
}
impl Bitmaps<'_> {
pub(crate) fn types(&self) -> Result<[Ewah; 4], GitError> {
let (commits, rest) = Ewah::decode(self.types)?;
let (trees, rest) = Ewah::decode(rest)?;
let (blobs, rest) = Ewah::decode(rest)?;
let (tags, _) = Ewah::decode(rest)?;
Ok([commits, trees, blobs, tags])
}
pub(crate) fn bitmap(&self, position: IndexPosition) -> Result<Option<Bitset>, GitError> {
match self
.table
.binary_search_by_key(&position, |(pos, _, _)| *pos)
{
Ok(row) => self.decode_chain(row).map(Some),
Err(_) => Ok(None),
}
}
fn decode_chain(&self, mut row: usize) -> Result<Bitset, GitError> {
let mut bits = Bitset::zeros(self.num_objects);
for _ in 0..self.table.len() {
let (commit_pos, offset, xor_row) = self.table[row];
let (xor_offset, vector) = self.decode_at(commit_pos, offset)?;
bits.xor_ewah(&vector, self.num_objects)?;
if xor_offset == 0 {
return Ok(bits);
}
row = usize::try_from(xor_row)
.ok()
.filter(|row| *row < self.table.len())
.ok_or_else(|| GitError::Backend("bitmap xor row out of range".to_string()))?;
}
Err(GitError::Backend("bitmap xor chain loops".to_string()))
}
fn decode_at(
&self,
commit_pos: IndexPosition,
offset: BitmapEntryOffset,
) -> Result<(u8, Ewah), GitError> {
let start = usize::try_from(offset.get())
.ok()
.filter(|start| *start <= self.body.len())
.ok_or_else(|| GitError::Backend("bitmap entry offset out of range".to_string()))?;
let entry = &self.body[start..];
if entry.len() < 6 {
return Err(GitError::Backend(
"truncated bitmap entry header".to_string(),
));
}
if u32::from_be_bytes([entry[0], entry[1], entry[2], entry[3]]) != commit_pos.get() {
return Err(GitError::Backend(
"bitmap lookup points at the wrong commit".to_string(),
));
}
let (vector, _) = Ewah::decode(&entry[6..])?;
Ok((entry[4], vector))
}
}
pub(crate) fn parse(
bytes: &[u8],
kind: gix::hash::Kind,
num_objects: usize,
) -> Result<Bitmaps<'_>, GitError> {
let raw = kind.len_in_bytes();
let header_len = 12 + raw;
if bytes.len() < header_len + raw || &bytes[..4] != b"BITM" {
return Err(GitError::Backend("bitmap header isn't BITM".to_string()));
}
let version = u16::from_be_bytes([bytes[4], bytes[5]]);
if version != 1 {
return Err(GitError::Backend(format!(
"unsupported bitmap version {version}"
)));
}
let flags = u16::from_be_bytes([bytes[6], bytes[7]]);
let entry_count = u32::from_be_bytes([bytes[8], bytes[9], bytes[10], bytes[11]]) as usize;
let (body, trailer) = bytes.split_at(bytes.len() - raw);
let mut hasher = gix::hash::hasher(kind);
hasher.update(body);
let digest = hasher
.try_finalize()
.map_err(|error| GitError::Backend(format!("bitmap checksum: {error}")))?;
if digest.as_slice() != trailer {
return Err(GitError::Backend("bitmap checksum mismatch".to_string()));
}
let cache_len = if flags & OPT_HASH_CACHE != 0 {
num_objects.checked_mul(4)
} else {
Some(0)
}
.filter(|len| *len <= body.len() - header_len)
.ok_or_else(|| GitError::Backend("bitmap hash cache overflows the file".to_string()))?;
let body = &body[..body.len() - cache_len];
let table = if flags & OPT_LOOKUP_TABLE == 0 {
scan_entries(body, header_len, entry_count)?
} else {
let table_len = entry_count
.checked_mul(TRIPLET_LEN)
.filter(|len| *len <= body.len() - header_len)
.ok_or_else(|| {
GitError::Backend("bitmap lookup table overflows the file".to_string())
})?;
let region = &body[body.len() - table_len..];
let table: Vec<(IndexPosition, BitmapEntryOffset, u32)> = (0..entry_count)
.map(|index| {
let base = index * TRIPLET_LEN;
let commit_pos = u32::from_be_bytes(region[base..base + 4].try_into().unwrap());
let offset = u64::from_be_bytes(region[base + 4..base + 12].try_into().unwrap());
let xor_row = u32::from_be_bytes(region[base + 12..base + 16].try_into().unwrap());
(
IndexPosition::new(commit_pos),
BitmapEntryOffset::new(offset),
xor_row,
)
})
.collect();
table
};
if table.windows(2).any(|pair| pair[0].0 >= pair[1].0) {
return Err(GitError::Backend(
"bitmap lookup table isn't sorted".to_string(),
));
}
Ok(Bitmaps {
body,
types: &body[header_len..],
table,
num_objects,
})
}
fn scan_entries(
body: &[u8],
header_len: usize,
count: usize,
) -> Result<Vec<(IndexPosition, BitmapEntryOffset, u32)>, GitError> {
let mut rest = &body[header_len..];
for _ in 0..4 {
rest = Ewah::decode(rest)?.1;
}
if count > rest.len() / 18 {
return Err(GitError::Backend("truncated bitmap entries".to_string()));
}
let mut entries = Vec::with_capacity(count);
for index in 0..count {
let offset = body.len() - rest.len();
let (head, vector) = rest
.split_at_checked(6)
.ok_or_else(|| GitError::Backend("truncated bitmap entry header".to_string()))?;
let position = u32::from_be_bytes(head[..4].try_into().unwrap());
let xor = match head[4] {
0 => u32::MAX,
delta => index
.checked_sub(delta as usize)
.ok_or_else(|| GitError::Backend("bitmap xor offset out of range".to_string()))?
as u32,
};
rest = Ewah::decode(vector)?.1;
entries.push((
IndexPosition::new(position),
BitmapEntryOffset::new(offset as u64),
xor,
));
}
if !rest.is_empty() {
return Err(GitError::Backend(
"unexpected bytes after bitmap entries".to_string(),
));
}
let mut rows: Vec<_> = (0..entries.len()).collect();
rows.sort_unstable_by_key(|index| entries[*index].0);
let mut row_of = vec![0u32; entries.len()];
for (row, index) in rows.iter().enumerate() {
row_of[*index] = row as u32;
}
Ok(rows
.into_iter()
.map(|index| {
let (position, offset, xor) = entries[index];
(
position,
offset,
if xor == u32::MAX {
xor
} else {
row_of[xor as usize]
},
)
})
.collect())
}