Something went wrong. Try again.
A knot based on walgit / s3 compare and swap that supports HA and Kubernetes
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142use super::bitset::Bitset;use super::ewah::Ewah;use super::{BitmapEntryOffset, IndexPosition};use crate::error::GitError;
const OPT_LOOKUP_TABLE: u16 = 0x10;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]]); if flags & OPT_LOOKUP_TABLE == 0 { return Err(GitError::Backend( "bitmap lacks the lookup table extension".to_string(), )); } 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 table_len = entry_count .checked_mul(TRIPLET_LEN) .filter(|len| header_len + len <= body.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(); if !table.is_sorted_by_key(|(commit_pos, _, _)| *commit_pos) { return Err(GitError::Backend( "bitmap lookup table isn't sorted".to_string(), )); }
Ok(Bitmaps { body, types: &body[header_len..], table, num_objects, })}