alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use super::bitset::Bitset;
2use super::{BitmapEntryOffset, IndexPosition};
3use crate::error::GitError;
4
5const OPT_LOOKUP_TABLE: u16 = 0x10;
6const TRIPLET_LEN: usize = 16;
7
8pub(crate) struct Bitmaps<'a> {
9 body: &'a [u8],
10 table: Vec<(IndexPosition, BitmapEntryOffset)>,
11 num_objects: usize,
12}
13
14impl Bitmaps<'_> {
15 pub(crate) fn bitmap(&self, position: IndexPosition) -> Result<Option<Bitset>, GitError> {
16 match self.table.binary_search_by_key(&position, |(pos, _)| *pos) {
17 Ok(index) => self.decode_at(position, self.table[index].1).map(Some),
18 Err(_) => Ok(None),
19 }
20 }
21
22 fn decode_at(
23 &self,
24 commit_pos: IndexPosition,
25 offset: BitmapEntryOffset,
26 ) -> Result<Bitset, GitError> {
27 let start = usize::try_from(offset.get())
28 .ok()
29 .filter(|start| *start <= self.body.len())
30 .ok_or_else(|| GitError::Backend("bitmap entry offset out of range".to_string()))?;
31 let entry = &self.body[start..];
32 if entry.len() < 6 {
33 return Err(GitError::Backend(
34 "truncated bitmap entry header".to_string(),
35 ));
36 }
37 if u32::from_be_bytes([entry[0], entry[1], entry[2], entry[3]]) != commit_pos.get() {
38 return Err(GitError::Backend(
39 "bitmap lookup points at the wrong commit".to_string(),
40 ));
41 }
42 if entry[4] != 0 {
43 return Err(GitError::Backend(
44 "xor-compressed bitmap entries are unsupported".to_string(),
45 ));
46 }
47 let (vector, _) = decode(&entry[6..])?;
48 Bitset::from_ewah(&vector, self.num_objects)
49 }
50}
51
52pub(crate) fn parse(
53 bytes: &[u8],
54 kind: gix::hash::Kind,
55 num_objects: usize,
56) -> Result<Bitmaps<'_>, GitError> {
57 let raw = kind.len_in_bytes();
58 let header_len = 12 + raw;
59 if bytes.len() < header_len + raw || &bytes[..4] != b"BITM" {
60 return Err(GitError::Backend("bitmap header isn't BITM".to_string()));
61 }
62 let version = u16::from_be_bytes([bytes[4], bytes[5]]);
63 if version != 1 {
64 return Err(GitError::Backend(format!(
65 "unsupported bitmap version {version}"
66 )));
67 }
68 let flags = u16::from_be_bytes([bytes[6], bytes[7]]);
69 if flags & OPT_LOOKUP_TABLE == 0 {
70 return Err(GitError::Backend(
71 "bitmap lacks the lookup table extension".to_string(),
72 ));
73 }
74 let entry_count = u32::from_be_bytes([bytes[8], bytes[9], bytes[10], bytes[11]]) as usize;
75
76 let (body, trailer) = bytes.split_at(bytes.len() - raw);
77 let mut hasher = gix_hash::hasher(kind);
78 hasher.update(body);
79 let digest = hasher
80 .try_finalize()
81 .map_err(|error| GitError::Backend(format!("bitmap checksum: {error}")))?;
82 if digest.as_slice() != trailer {
83 return Err(GitError::Backend("bitmap checksum mismatch".to_string()));
84 }
85
86 let table_len = entry_count
87 .checked_mul(TRIPLET_LEN)
88 .filter(|len| header_len + len <= body.len())
89 .ok_or_else(|| GitError::Backend("bitmap lookup table overflows the file".to_string()))?;
90 let region = &body[body.len() - table_len..];
91 let mut table: Vec<(IndexPosition, BitmapEntryOffset)> = (0..entry_count)
92 .map(|index| {
93 let base = index * TRIPLET_LEN;
94 let commit_pos = u32::from_be_bytes(region[base..base + 4].try_into().unwrap());
95 let offset = u64::from_be_bytes(region[base + 4..base + 12].try_into().unwrap());
96 (
97 IndexPosition::new(commit_pos),
98 BitmapEntryOffset::new(offset),
99 )
100 })
101 .collect();
102 table.sort_unstable_by_key(|(commit_pos, _)| *commit_pos);
103
104 Ok(Bitmaps {
105 body,
106 table,
107 num_objects,
108 })
109}
110
111fn decode(data: &[u8]) -> Result<(gix_bitmap::ewah::Vec, &[u8]), GitError> {
112 gix_bitmap::ewah::decode(data)
113 .map_err(|error| GitError::Backend(format!("ewah decode: {error:?}")))
114}