alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::collections::HashMap;
2use std::path::Path;
3
4use gix::ObjectId;
5use gix::object::Kind;
6use gix::objs::{Find, Write};
7use gix_pack::data::{Entry, entry::Header};
8
9use crate::error::{PackError, PackLimit};
10use crate::ids::{DeltaDepth, PackOffset, Rounds};
11use crate::meter::{PackLimits, inflate_into, pack_object_count};
12
13struct Raw {
14 offset: PackOffset,
15 header: Header,
16 data: Vec<u8>,
17}
18
19#[derive(Clone, Copy)]
20struct Resolved {
21 oid: ObjectId,
22 depth: DeltaDepth,
23}
24
25fn malformed(message: &str) -> PackError {
26 PackError::Pack(message.to_string())
27}
28
29pub fn resolve(
30 objects_dir: &Path,
31 pack: &[u8],
32 limits: &PackLimits,
33 kind: gix::hash::Kind,
34) -> Result<(), PackError> {
35 let mut raws = parse_entries(pack, kind)?;
36 let odb = gix::odb::at_opts(
37 objects_dir,
38 std::iter::empty(),
39 gix::odb::store::init::Options {
40 object_hash: kind,
41 ..Default::default()
42 },
43 )
44 .map_err(|error| PackError::Pack(error.to_string()))?;
45 let mut done: HashMap<PackOffset, Resolved> = HashMap::new();
46 let mut by_oid: HashMap<ObjectId, DeltaDepth> = HashMap::new();
47 resolve_rounds(
48 &mut raws,
49 &odb,
50 &mut done,
51 &mut by_oid,
52 limits.max_delta_depth,
53 Rounds::new(limits.max_delta_depth.get() + 2),
54 )
55}
56
57fn parse_entries(pack: &[u8], kind: gix::hash::Kind) -> Result<Vec<Raw>, PackError> {
58 let hash_len = kind.len_in_bytes();
59 let trailer = pack
60 .len()
61 .checked_sub(hash_len)
62 .ok_or_else(|| malformed("packfile is truncated"))?;
63 let num_objects = pack_object_count(pack)?;
64
65 (0..num_objects.get())
66 .try_fold((Vec::new(), PackOffset::new(12)), |(mut acc, offset), _| {
67 let mut reader: &[u8] = pack
68 .get(offset.get() as usize..trailer)
69 .ok_or_else(|| malformed("entry offset past pack end"))?;
70 let entry = Entry::from_read(&mut reader, offset.get(), hash_len)
71 .map_err(|error| PackError::Pack(error.to_string()))?;
72 let data_start = entry.data_offset as usize;
73 let mut data = Vec::with_capacity(entry.decompressed_size as usize);
74 let consumed = inflate_into(
75 pack.get(data_start..)
76 .ok_or_else(|| malformed("entry body past pack end"))?,
77 entry.decompressed_size,
78 &mut data,
79 )?;
80 acc.push(Raw {
81 offset,
82 header: entry.header,
83 data,
84 });
85 Ok::<_, PackError>((acc, PackOffset::new(entry.data_offset + consumed)))
86 })
87 .map(|(acc, _)| acc)
88}
89
90fn resolve_rounds(
91 raws: &mut [Raw],
92 odb: &gix::odb::Handle,
93 done: &mut HashMap<PackOffset, Resolved>,
94 by_oid: &mut HashMap<ObjectId, DeltaDepth>,
95 max_depth: DeltaDepth,
96 rounds_left: Rounds,
97) -> Result<(), PackError> {
98 let pending: Vec<usize> = (0..raws.len())
99 .filter(|index| !done.contains_key(&raws[*index].offset))
100 .collect();
101 if pending.is_empty() {
102 return Ok(());
103 }
104 let Some(remaining) = rounds_left.next() else {
105 return Err(PackError::LimitExceeded(PackLimit::DeltaDepth));
106 };
107 let progressed = pending.iter().try_fold(false, |progressed, &index| {
108 match resolve_one(&raws[index], odb, done, by_oid, max_depth)? {
109 Some((kind, data, depth)) => {
110 let oid = odb
111 .write_buf(kind, &data)
112 .map_err(|error| PackError::Pack(error.to_string()))?;
113 by_oid.insert(oid, depth);
114 done.insert(raws[index].offset, Resolved { oid, depth });
115 raws[index].data = Vec::new();
116 Ok::<_, PackError>(true)
117 }
118 None => Ok(progressed),
119 }
120 })?;
121 if !progressed {
122 return Err(malformed("pack contains unresolvable delta"));
123 }
124 resolve_rounds(raws, odb, done, by_oid, max_depth, remaining)
125}
126
127fn apply_delta_checked(
128 base_kind: Kind,
129 base_data: &[u8],
130 base_depth: DeltaDepth,
131 delta: &[u8],
132 max_depth: DeltaDepth,
133) -> Result<(Kind, Vec<u8>, DeltaDepth), PackError> {
134 let depth = base_depth.deeper();
135 if depth.exceeds(max_depth) {
136 return Err(PackError::LimitExceeded(PackLimit::DeltaDepth));
137 }
138 Ok((base_kind, apply_delta(base_data, delta)?, depth))
139}
140
141fn resolve_one(
142 raw: &Raw,
143 odb: &gix::odb::Handle,
144 done: &HashMap<PackOffset, Resolved>,
145 by_oid: &HashMap<ObjectId, DeltaDepth>,
146 max_depth: DeltaDepth,
147) -> Result<Option<(Kind, Vec<u8>, DeltaDepth)>, PackError> {
148 match &raw.header {
149 Header::Commit | Header::Tree | Header::Blob | Header::Tag => {
150 let kind = raw
151 .header
152 .as_kind()
153 .ok_or_else(|| malformed("base entry has no object kind"))?;
154 Ok(Some((kind, raw.data.clone(), DeltaDepth::ZERO)))
155 }
156 Header::OfsDelta { base_distance } => {
157 let base_offset = raw
158 .offset
159 .checked_sub_distance(*base_distance)
160 .filter(|_| *base_distance != 0)
161 .ok_or_else(|| malformed("ofs-delta base out of range"))?;
162 match done.get(&base_offset) {
163 Some(base) => {
164 let mut buf = Vec::new();
165 let found = odb
166 .try_find(&base.oid, &mut buf)
167 .map_err(|error| PackError::Pack(error.to_string()))?
168 .ok_or_else(|| malformed("ofs-delta base missing from odb"))?;
169 apply_delta_checked(found.kind, found.data, base.depth, &raw.data, max_depth)
170 .map(Some)
171 }
172 None => Ok(None),
173 }
174 }
175 Header::RefDelta { base_id } => {
176 let base_depth = by_oid.get(base_id).copied();
177 let mut buf = Vec::new();
178 match odb
179 .try_find(base_id, &mut buf)
180 .map_err(|error| PackError::Pack(error.to_string()))?
181 {
182 Some(base) => apply_delta_checked(
183 base.kind,
184 base.data,
185 base_depth.unwrap_or(DeltaDepth::ZERO),
186 &raw.data,
187 max_depth,
188 )
189 .map(Some),
190 None => Ok(None),
191 }
192 }
193 }
194}
195
196enum Op<'a> {
197 Copy { start: usize, len: usize },
198 Insert(&'a [u8]),
199}
200
201fn read_varint(delta: &[u8], pos: &mut usize) -> Result<u64, PackError> {
202 let mut shift = 0u32;
203 let mut value = 0u64;
204 loop {
205 let byte = *delta
206 .get(*pos)
207 .ok_or_else(|| malformed("delta size header truncated"))?;
208 *pos += 1;
209 value |= u64::from(byte & 0x7f) << shift;
210 shift += 7;
211 if byte & 0x80 == 0 {
212 return Ok(value);
213 }
214 if shift >= u64::BITS {
215 return Err(malformed("delta size header overflows"));
216 }
217 }
218}
219
220fn assemble(
221 cmd: u8,
222 bit_base: u32,
223 count: u32,
224 delta: &[u8],
225 pos: &mut usize,
226) -> Result<u64, PackError> {
227 (0..count).try_fold(0u64, |acc, index| {
228 if cmd & (1 << (bit_base + index)) == 0 {
229 return Ok(acc);
230 }
231 let byte = *delta
232 .get(*pos)
233 .ok_or_else(|| malformed("delta copy operand truncated"))?;
234 *pos += 1;
235 Ok(acc | (u64::from(byte) << (8 * index)))
236 })
237}
238
239fn ops<'a>(delta: &'a [u8]) -> impl Iterator<Item = Result<Op<'a>, PackError>> {
240 let mut pos = 0usize;
241 std::iter::from_fn(move || {
242 (pos < delta.len()).then(|| {
243 let cmd = delta[pos];
244 pos += 1;
245 if cmd & 0x80 != 0 {
246 let offset = assemble(cmd, 0, 4, delta, &mut pos)?;
247 let raw_size = assemble(cmd, 4, 3, delta, &mut pos)?;
248 let size = if raw_size == 0 { 0x10000 } else { raw_size };
249 Ok(Op::Copy {
250 start: offset as usize,
251 len: size as usize,
252 })
253 } else if cmd != 0 {
254 let len = cmd as usize;
255 let bytes = delta
256 .get(pos..pos + len)
257 .ok_or_else(|| malformed("delta insert truncated"))?;
258 pos += len;
259 Ok(Op::Insert(bytes))
260 } else {
261 Err(malformed("delta uses reserved opcode 0"))
262 }
263 })
264 })
265}
266
267fn apply_delta(base: &[u8], delta: &[u8]) -> Result<Vec<u8>, PackError> {
268 let mut pos = 0usize;
269 let base_size = read_varint(delta, &mut pos)?;
270 if base_size as usize != base.len() {
271 return Err(malformed("delta base size doesn't match its base object"));
272 }
273 let target_size = read_varint(delta, &mut pos)?;
274 let out =
275 ops(&delta[pos..]).try_fold(Vec::with_capacity(target_size as usize), |mut out, op| {
276 match op? {
277 Op::Copy { start, len } => {
278 let end = start
279 .checked_add(len)
280 .ok_or_else(|| malformed("delta copy range overflows"))?;
281 out.extend_from_slice(
282 base.get(start..end)
283 .ok_or_else(|| malformed("delta copy reads past base"))?,
284 );
285 }
286 Op::Insert(bytes) => out.extend_from_slice(bytes),
287 }
288 Ok::<_, PackError>(out)
289 })?;
290 if out.len() as u64 != target_size {
291 return Err(malformed("delta produced wrong target size"));
292 }
293 Ok(out)
294}
295
296#[cfg(test)]
297mod tests {
298 use super::*;
299
300 #[test]
301 fn apply_delta_reconstructs_copy_and_insert() {
302 let base = b"hello world";
303 let delta = [0x0b, 0x06, 0x90, 0x05, 0x01, b'!'];
304 assert_eq!(apply_delta(base, &delta).unwrap(), b"hello!");
305 }
306
307 #[test]
308 fn apply_delta_rejects_a_base_size_mismatch() {
309 let delta = [0x05, 0x00];
310 assert!(apply_delta(b"hi", &delta).is_err());
311 }
312
313 #[test]
314 fn apply_delta_rejects_a_copy_past_the_base() {
315 let delta = [0x02, 0x10, 0x90, 0xff];
316 assert!(apply_delta(b"hi", &delta).is_err());
317 }
318
319 #[test]
320 fn apply_delta_rejects_a_truncated_insert() {
321 let delta = [0x02, 0x05, 0x05, b'a', b'b'];
322 assert!(apply_delta(b"hi", &delta).is_err());
323 }
324
325 #[test]
326 fn apply_delta_rejects_the_reserved_opcode() {
327 let delta = [0x02, 0x00, 0x00];
328 assert!(apply_delta(b"hi", &delta).is_err());
329 }
330
331 #[test]
332 fn apply_delta_rejects_a_truncated_size_header() {
333 let delta = [0x80];
334 assert!(apply_delta(b"", &delta).is_err());
335 }
336}