use std::{collections::VecDeque, fs, path::Path};
use crate::{HashKind, ObjectId, Result, error::invalid};
const FULL_DAG: u16 = 0x0001;
pub(crate) struct BitmapIndex {
data: Vec<u8>,
hash: HashKind,
}
impl BitmapIndex {
pub(crate) fn open(path: &Path, hash: HashKind) -> Result<Option<Self>> {
let data = match fs::read(path) {
Ok(data) => data,
Err(error) if error.kind() == std::io::ErrorKind::NotFound => return Ok(None),
Err(error) => return Err(error.into()),
};
if data.get(..4) != Some(b"BITM") || read_u16(&data, 4)? != 1 {
return Err(invalid("invalid reachability bitmap header"));
}
if read_u16(&data, 6)? & FULL_DAG == 0 {
return Err(invalid("reachability bitmap is not a full DAG"));
}
Ok(Some(Self { data, hash }))
}
pub(crate) fn reachable(
&self,
commit_position: usize,
order: &[ObjectId],
max_objects: usize,
) -> Result<Option<Vec<ObjectId>>> {
if order.len() > max_objects {
return Err(crate::GitError::LimitExceeded {
resource: "bitmap objects",
limit: max_objects,
});
}
let entries = usize::try_from(read_u32(&self.data, 8)?)
.map_err(|_| invalid("bitmap entry count overflow"))?;
let mut cursor = 12_usize
.checked_add(self.hash.bytes())
.ok_or_else(|| invalid("bitmap header overflow"))?;
for _ in 0..4 {
let _ = read_ewah(&self.data, &mut cursor, order.len())?;
}
let mut previous = VecDeque::<Vec<u64>>::with_capacity(160);
for index in 0..entries {
let position = usize::try_from(read_u32(&self.data, cursor)?)
.map_err(|_| invalid("bitmap commit position overflow"))?;
cursor += 4;
let xor_offset = usize::from(take(&self.data, &mut cursor)?);
let _flags = take(&self.data, &mut cursor)?;
let mut words = read_ewah(&self.data, &mut cursor, order.len())?;
if xor_offset > 0 {
if xor_offset > index || xor_offset > previous.len() {
return Err(invalid("bitmap XOR offset is out of bounds"));
}
let base = &previous[previous.len() - xor_offset];
if base.len() != words.len() {
return Err(invalid("bitmap XOR operands differ in length"));
}
for (word, base) in words.iter_mut().zip(base) {
*word ^= base;
}
}
if position == commit_position {
return Ok(Some(expand(&words, order)));
}
previous.push_back(words);
if previous.len() > 160 {
previous.pop_front();
}
}
Ok(None)
}
}
fn read_ewah(input: &[u8], cursor: &mut usize, max_bits: usize) -> Result<Vec<u64>> {
let bits = usize::try_from(read_u32(input, *cursor)?)
.map_err(|_| invalid("EWAH bit count overflow"))?;
*cursor += 4;
if bits > max_bits.div_ceil(64) * 64 {
return Err(invalid("EWAH bitmap exceeds object order"));
}
let word_count = usize::try_from(read_u32(input, *cursor)?)
.map_err(|_| invalid("EWAH word count overflow"))?;
*cursor += 4;
let mut encoded = Vec::with_capacity(word_count);
for _ in 0..word_count {
encoded.push(read_u64(input, *cursor)?);
*cursor += 8;
}
let rlw_position = usize::try_from(read_u32(input, *cursor)?)
.map_err(|_| invalid("EWAH RLW position overflow"))?;
*cursor += 4;
if word_count > 0 && rlw_position >= word_count {
return Err(invalid("EWAH RLW position is out of bounds"));
}
let output_words = bits.div_ceil(64);
let mut output = Vec::with_capacity(output_words);
let mut at = 0;
while at < encoded.len() {
let rlw = encoded[at];
at += 1;
let repeated = usize::try_from((rlw >> 1) & 0xffff_ffff)
.map_err(|_| invalid("EWAH run length overflow"))?;
let literals =
usize::try_from(rlw >> 33).map_err(|_| invalid("EWAH literal length overflow"))?;
let repeated_word = if rlw & 1 == 0 { 0 } else { u64::MAX };
append_repeated(&mut output, repeated_word, repeated, output_words)?;
if at.saturating_add(literals) > encoded.len()
|| output.len().saturating_add(literals) > output_words
{
return Err(invalid("EWAH literal words are out of bounds"));
}
output.extend_from_slice(&encoded[at..at + literals]);
at += literals;
}
output.resize(output_words, 0);
if !bits.is_multiple_of(64)
&& let Some(last) = output.last_mut()
{
*last &= (1_u64 << (bits % 64)) - 1;
}
Ok(output)
}
fn append_repeated(output: &mut Vec<u64>, word: u64, count: usize, max: usize) -> Result<()> {
if output.len().saturating_add(count) > max {
return Err(invalid("EWAH run exceeds bit count"));
}
output.resize(output.len() + count, word);
Ok(())
}
fn expand(words: &[u64], order: &[ObjectId]) -> Vec<ObjectId> {
let mut result = Vec::new();
for (word_index, word) in words.iter().copied().enumerate() {
let mut remaining = word;
while remaining != 0 {
let bit = usize::try_from(remaining.trailing_zeros()).expect("u32 fits usize");
let position = word_index * 64 + bit;
if let Some(id) = order.get(position) {
result.push(*id);
}
remaining &= remaining - 1;
}
}
result
}
fn take(input: &[u8], cursor: &mut usize) -> Result<u8> {
let value = *input
.get(*cursor)
.ok_or_else(|| invalid("truncated bitmap entry"))?;
*cursor += 1;
Ok(value)
}
fn read_u16(input: &[u8], offset: usize) -> Result<u16> {
let bytes = input
.get(offset..offset + 2)
.ok_or_else(|| invalid("truncated bitmap integer"))?;
Ok(u16::from_be_bytes(bytes.try_into().expect("two bytes")))
}
fn read_u32(input: &[u8], offset: usize) -> Result<u32> {
let bytes = input
.get(offset..offset + 4)
.ok_or_else(|| invalid("truncated bitmap integer"))?;
Ok(u32::from_be_bytes(bytes.try_into().expect("four bytes")))
}
fn read_u64(input: &[u8], offset: usize) -> Result<u64> {
let bytes = input
.get(offset..offset + 8)
.ok_or_else(|| invalid("truncated bitmap integer"))?;
Ok(u64::from_be_bytes(bytes.try_into().expect("eight bytes")))
}
#[cfg(test)]
mod tests {
use super::{expand, read_ewah};
use crate::ObjectId;
#[test]
fn expands_set_bits_in_order() {
let ids = [
"1111111111111111111111111111111111111111",
"2222222222222222222222222222222222222222",
]
.map(|value| value.parse::<ObjectId>().unwrap());
assert_eq!(expand(&[2], &ids), vec![ids[1]]);
}
#[test]
fn decodes_literal_and_repeated_ewah_words() {
let mut literal = Vec::new();
literal.extend(64_u32.to_be_bytes());
literal.extend(2_u32.to_be_bytes());
literal.extend((1_u64 << 33).to_be_bytes());
literal.extend(2_u64.to_be_bytes());
literal.extend(0_u32.to_be_bytes());
let mut cursor = 0;
assert_eq!(read_ewah(&literal, &mut cursor, 2).unwrap(), vec![2]);
assert_eq!(cursor, literal.len());
let mut repeated = Vec::new();
repeated.extend(64_u32.to_be_bytes());
repeated.extend(1_u32.to_be_bytes());
repeated.extend(3_u64.to_be_bytes());
repeated.extend(0_u32.to_be_bytes());
let mut cursor = 0;
assert_eq!(
read_ewah(&repeated, &mut cursor, 64).unwrap(),
vec![u64::MAX]
);
}
#[test]
fn rejects_malformed_ewah_streams() {
let mut excessive = Vec::new();
excessive.extend(65_u32.to_be_bytes());
excessive.extend(0_u32.to_be_bytes());
excessive.extend(0_u32.to_be_bytes());
assert!(read_ewah(&excessive, &mut 0, 64).is_err());
let mut bad_rlw = Vec::new();
bad_rlw.extend(64_u32.to_be_bytes());
bad_rlw.extend(1_u32.to_be_bytes());
bad_rlw.extend((1_u64 << 33).to_be_bytes());
bad_rlw.extend(1_u32.to_be_bytes());
assert!(read_ewah(&bad_rlw, &mut 0, 64).is_err());
let mut oversized_run = Vec::new();
oversized_run.extend(64_u32.to_be_bytes());
oversized_run.extend(1_u32.to_be_bytes());
oversized_run.extend((2_u64 << 1).to_be_bytes());
oversized_run.extend(0_u32.to_be_bytes());
assert!(read_ewah(&oversized_run, &mut 0, 64).is_err());
}
}