git_zero_core/pack/
decode.rs

1//! Bounded SHA-1/SHA-256 pack consumption, based on Git's pack specification:
2//! https://git-scm.com/docs/pack-format. No recursion or allocation is used.
3use super::crc::crc32;
4use crate::{
5    Error, Object, ObjectFormat, ObjectId, ObjectKind, Result,
6    zlib::{InflateLimits, InflateStatus, Inflater, WINDOW_SIZE},
7};
8
9#[derive(Clone, Copy, Debug, Eq, PartialEq)]
10pub enum EntryKind {
11    Object(ObjectKind),
12    OffsetDelta { base_offset: u64 },
13    ReferenceDelta { base_id: ObjectId },
14}
15
16/// Pack-relative position, representation, and inflated length of one entry.
17#[derive(Clone, Copy, Debug, Eq, PartialEq)]
18pub struct EntryHeader {
19    pub offset: u64,
20    pub kind: EntryKind,
21    pub size: u64,
22}
23
24/// One checksummed/inflated entry. Delta data is an instruction stream rather
25/// than a Git object body; resolve it against an authenticated materialized base.
26pub struct Entry<'a> {
27    offset: u64,
28    compressed_offset: u64,
29    end_offset: u64,
30    crc: u32,
31    kind: EntryKind,
32    data: &'a [u8],
33    pack_id: ObjectId,
34}
35
36impl<'a> Entry<'a> {
37    pub fn offset(&self) -> u64 {
38        self.offset
39    }
40    pub fn end_offset(&self) -> u64 {
41        self.end_offset
42    }
43    /// First byte of the zlib stream, after type/size and delta-base metadata.
44    pub fn compressed_offset(&self) -> u64 {
45        self.compressed_offset
46    }
47    pub fn crc32(&self) -> u32 {
48        self.crc
49    }
50    pub fn kind(&self) -> EntryKind {
51        self.kind
52    }
53    pub fn data(&self) -> &'a [u8] {
54        self.data
55    }
56
57    /// Compare the entry's wire CRC with a trusted pack-index CRC. Packs do not
58    /// carry per-entry CRCs themselves; the complete pack hash is also checked.
59    pub fn verify_crc32(&self, expected: u32) -> Result<()> {
60        if self.crc == expected {
61            Ok(())
62        } else {
63            Err(Error::CorruptPack)
64        }
65    }
66
67    /// Materialize metadata/ID for a non-delta entry without copying its body.
68    pub fn object(&self) -> Option<ResolvedObject<'a>> {
69        let EntryKind::Object(kind) = self.kind else {
70            return None;
71        };
72        Some(ResolvedObject::new(
73            Object {
74                kind,
75                data: self.data,
76            },
77            Some((self.pack_id, self.offset)),
78            0,
79            self.pack_id.format(),
80        ))
81    }
82
83    /// Resolve one delta using a previously resolved entry or an external base.
84    /// Offset bases must come from this pack at exactly the advertised offset;
85    /// reference bases must have exactly the advertised canonical object ID.
86    /// Depth is carried by resolved values, and output/instruction/depth budgets
87    /// are checked before returning an object. Discard staging output on error.
88    pub fn resolve_delta<'out>(
89        &self,
90        base: &ResolvedObject<'_>,
91        output: &'out mut [u8],
92        limits: DeltaLimits,
93    ) -> Result<ResolvedObject<'out>> {
94        match self.kind {
95            EntryKind::Object(_) => return Err(Error::InvalidObject),
96            EntryKind::OffsetDelta { base_offset } => {
97                if base.location != Some((self.pack_id, base_offset)) {
98                    return Err(Error::ObjectNotFound);
99                }
100            }
101            EntryKind::ReferenceDelta { base_id } => {
102                if base.id != base_id {
103                    return Err(Error::ObjectNotFound);
104                }
105            }
106        }
107        if base.depth >= limits.max_depth {
108            return Err(Error::LimitExceeded);
109        }
110        let object = apply_delta(base.object, self.data, output, limits)?;
111        Ok(ResolvedObject::new(
112            object,
113            Some((self.pack_id, self.offset)),
114            base.depth + 1,
115            self.pack_id.format(),
116        ))
117    }
118}
119
120/// A canonical body with a computed ID and tracked delta depth. A decoded entry
121/// retains its pack/offset identity, preventing cross-pack offset-base confusion.
122pub struct ResolvedObject<'a> {
123    object: Object<'a>,
124    id: ObjectId,
125    location: Option<(ObjectId, u64)>,
126    depth: u32,
127}
128
129impl<'a> ResolvedObject<'a> {
130    fn new(
131        object: Object<'a>,
132        location: Option<(ObjectId, u64)>,
133        depth: u32,
134        format: ObjectFormat,
135    ) -> Self {
136        Self {
137            id: object.id_with_format(format),
138            object,
139            location,
140            depth,
141        }
142    }
143    /// Use a canonical object from host storage as a reference-delta base.
144    pub fn external(object: Object<'a>) -> Self {
145        Self::external_with_format(object, ObjectFormat::Sha1)
146    }
147    pub fn external_with_format(object: Object<'a>, format: ObjectFormat) -> Self {
148        Self::new(object, None, 0, format)
149    }
150    pub fn object(&self) -> Object<'a> {
151        self.object
152    }
153    pub fn id(&self) -> ObjectId {
154        self.id
155    }
156    pub fn offset(&self) -> Option<u64> {
157        self.location.map(|(_, offset)| offset)
158    }
159    pub fn delta_depth(&self) -> u32 {
160        self.depth
161    }
162    pub fn verify_id(&self, expected: ObjectId) -> Result<()> {
163        if self.id == expected {
164            Ok(())
165        } else {
166            Err(Error::CorruptPack)
167        }
168    }
169}
170
171/// Reader over one complete downloaded pack. Construction verifies its
172/// framing and hash; entries are then inflated/length-checked one at a time.
173/// Each call borrows caller staging storage and a reusable 32 KiB zlib window.
174/// Call `finish` (or read through `None`) to verify count and exact pack closure.
175/// Forward reference deltas require host base lookup; thin-pack bases may be
176/// supplied as `ResolvedObject::external`. No pack-index file parser is implied.
177pub struct Reader<'a> {
178    bytes: &'a [u8],
179    position: usize,
180    count: u32,
181    remaining: u32,
182    pack_id: ObjectId,
183}
184
185impl<'a> Reader<'a> {
186    pub fn new(pack: &'a [u8]) -> Result<Self> {
187        Self::new_with_format(pack, ObjectFormat::Sha1)
188    }
189    pub fn new_with_format(pack: &'a [u8], format: ObjectFormat) -> Result<Self> {
190        super::validate_with_format(pack, format)?;
191        let end = pack.len() - format.id_length();
192        let count = u32::from_be_bytes(pack[8..12].try_into().map_err(|_| Error::CorruptPack)?);
193        let pack_id = ObjectId::from_bytes(format, &pack[end..]).map_err(|_| Error::CorruptPack)?;
194        if count == 0 && end != 12 {
195            return Err(Error::CorruptPack);
196        }
197        Ok(Self {
198            bytes: &pack[..end],
199            position: 12,
200            count,
201            remaining: count,
202            pack_id,
203        })
204    }
205
206    pub fn object_count(&self) -> u32 {
207        self.count
208    }
209    pub fn remaining(&self) -> u32 {
210        self.remaining
211    }
212    pub fn position(&self) -> u64 {
213        self.position as u64
214    }
215    pub fn pack_id(&self) -> ObjectId {
216        self.pack_id
217    }
218
219    /// Inspect the next entry's declared inflated body/instruction size without
220    /// advancing. Hosts must apply their own budget before allocating storage.
221    /// The declaration is checked against the actual stream by `read_entry`.
222    pub fn next_entry_size(&self) -> Result<Option<u64>> {
223        Ok(self.entry_header()?.map(|(_, size, _)| size))
224    }
225
226    /// Read the next entry. Declared size is the inflated body/instruction size.
227    /// A staging-capacity or budget error preserves the cursor for retry.
228    /// Other errors also preserve the cursor; staging bytes may have changed.
229    pub fn read_entry<'out>(
230        &mut self,
231        output: &'out mut [u8],
232        window: &mut [u8; WINDOW_SIZE],
233        limits: InflateLimits,
234    ) -> Result<Option<Entry<'out>>> {
235        let Some((cursor, size, kind)) = self.entry_header()? else {
236            return Ok(None);
237        };
238        let start = self.position;
239        if size > limits.max_output {
240            return Err(Error::LimitExceeded);
241        }
242        let size = usize::try_from(size).map_err(|_| Error::BufferTooSmall)?;
243        let output = output.get_mut(..size).ok_or(Error::BufferTooSmall)?;
244        let progress = Inflater::new(window, limits)
245            .update(&self.bytes[cursor..], output, true)
246            .map_err(|error| match error {
247                Error::LimitExceeded => error,
248                _ => Error::CorruptPack,
249            })?;
250        if progress.status != InflateStatus::Finished || progress.written != size {
251            return Err(Error::CorruptPack);
252        }
253        let end = cursor + progress.consumed;
254        if self.remaining == 1 && end != self.bytes.len() {
255            return Err(Error::CorruptPack);
256        }
257        let crc = crc32(&self.bytes[start..end]);
258        self.position = end;
259        self.remaining -= 1;
260        Ok(Some(Entry {
261            offset: start as u64,
262            compressed_offset: cursor as u64,
263            end_offset: end as u64,
264            crc,
265            kind,
266            data: output,
267            pack_id: self.pack_id,
268        }))
269    }
270
271    fn entry_header(&self) -> Result<Option<(usize, u64, EntryKind)>> {
272        if self.remaining == 0 {
273            self.finish()?;
274            return Ok(None);
275        }
276        let (length, header) = parse_entry_header(
277            &self.bytes[self.position..],
278            self.position as u64,
279            self.pack_id.format(),
280        )
281        .map_err(|error| {
282            if error == Error::BufferTooSmall {
283                Error::CorruptPack
284            } else {
285                error
286            }
287        })?;
288        Ok(Some((self.position + length, header.size, header.kind)))
289    }
290
291    pub fn finish(&self) -> Result<()> {
292        if self.remaining == 0 && self.position == self.bytes.len() {
293            Ok(())
294        } else {
295            Err(Error::CorruptPack)
296        }
297    }
298}
299
300#[derive(Clone, Copy, Debug, Eq, PartialEq)]
301pub struct DeltaLimits {
302    pub max_output: u64,
303    pub max_instructions: u64,
304    /// Zero rejects every delta; one permits a delta against a plain base.
305    pub max_depth: u32,
306}
307
308/// Apply Git delta instructions to a canonical base, inheriting its object kind.
309/// Both size headers, source/target ranges, instruction count and exact closure
310/// are validated. The returned body is exposed only on success; staging output
311/// may have changed on error. This function applies one level; `resolve_delta`
312/// additionally tracks and bounds chain depth across resolved entries.
313pub fn apply_delta<'a>(
314    base: Object<'_>,
315    mut delta: &[u8],
316    output: &'a mut [u8],
317    limits: DeltaLimits,
318) -> Result<Object<'a>> {
319    if limits.max_depth == 0 {
320        return Err(Error::LimitExceeded);
321    }
322    let base_size = variable(&mut delta)?;
323    let result_size = variable(&mut delta)?;
324    if base_size != base.data.len() as u64 {
325        return Err(Error::CorruptPack);
326    }
327    if result_size > limits.max_output {
328        return Err(Error::LimitExceeded);
329    }
330    let size = usize::try_from(result_size).map_err(|_| Error::BufferTooSmall)?;
331    let output = output.get_mut(..size).ok_or(Error::BufferTooSmall)?;
332    let (mut written, mut instructions) = (0_usize, 0_u64);
333    while !delta.is_empty() {
334        if instructions == limits.max_instructions {
335            return Err(Error::LimitExceeded);
336        }
337        instructions += 1;
338        let opcode = take_byte(&mut delta)?;
339        let bytes = match opcode {
340            0 => return Err(Error::CorruptPack),
341            1..=127 => {
342                let size = usize::from(opcode);
343                let bytes = delta.get(..size).ok_or(Error::CorruptPack)?;
344                delta = &delta[size..];
345                bytes
346            }
347            _ => delta_copy(base.data, opcode, &mut delta)?,
348        };
349        let end = written.checked_add(bytes.len()).ok_or(Error::CorruptPack)?;
350        output
351            .get_mut(written..end)
352            .ok_or(Error::CorruptPack)?
353            .copy_from_slice(bytes);
354        written = end;
355    }
356    if written != output.len() {
357        return Err(Error::CorruptPack);
358    }
359    Ok(Object {
360        kind: base.kind,
361        data: output,
362    })
363}
364
365// Shared by the complete-pack reader and incremental intake. A missing byte
366// is distinct from malformed syntax so only the incremental caller can wait.
367pub(super) fn parse_entry_header(
368    bytes: &[u8],
369    offset: u64,
370    format: ObjectFormat,
371) -> Result<(usize, EntryHeader)> {
372    let mut cursor = 0;
373    let first = byte(bytes, &mut cursor)?;
374    let mut size = u64::from(first & 15);
375    let mut last = first;
376    let mut shift = 4;
377    while last & 128 != 0 {
378        last = byte(bytes, &mut cursor)?;
379        size |= chunk(u64::from(last & 127), shift)?;
380        shift += 7;
381    }
382    let kind = match (first >> 4) & 7 {
383        1 => EntryKind::Object(ObjectKind::Commit),
384        2 => EntryKind::Object(ObjectKind::Tree),
385        3 => EntryKind::Object(ObjectKind::Blob),
386        4 => EntryKind::Object(ObjectKind::Tag),
387        6 => EntryKind::OffsetDelta {
388            base_offset: offset_base(bytes, &mut cursor, offset)?,
389        },
390        7 => {
391            let end = cursor + format.id_length();
392            let id = bytes.get(cursor..end).ok_or(Error::BufferTooSmall)?;
393            cursor = end;
394            EntryKind::ReferenceDelta {
395                base_id: ObjectId::from_bytes(format, id)?,
396            }
397        }
398        _ => return Err(Error::CorruptPack),
399    };
400    Ok((cursor, EntryHeader { offset, kind, size }))
401}
402
403fn offset_base(bytes: &[u8], cursor: &mut usize, start: u64) -> Result<u64> {
404    let mut last = byte(bytes, cursor)?;
405    let mut distance = u64::from(last & 127);
406    while last & 128 != 0 {
407        last = byte(bytes, cursor)?;
408        distance = distance
409            .checked_add(1)
410            .and_then(|n| n.checked_mul(128))
411            .and_then(|n| n.checked_add(u64::from(last & 127)))
412            .ok_or(Error::CorruptPack)?;
413    }
414    let base = start.checked_sub(distance).ok_or(Error::CorruptPack)?;
415    if distance == 0 || base < 12 {
416        return Err(Error::CorruptPack);
417    }
418    Ok(base)
419}
420
421fn delta_copy<'a>(base: &'a [u8], opcode: u8, delta: &mut &[u8]) -> Result<&'a [u8]> {
422    let offset = sparse_parameter(opcode, 4, delta)?;
423    let count = sparse_parameter(opcode >> 4, 3, delta)?;
424    let count = if count == 0 { 65536 } else { count };
425    let offset = usize::try_from(offset).map_err(|_| Error::CorruptPack)?;
426    let end = offset
427        .checked_add(count as usize)
428        .ok_or(Error::CorruptPack)?;
429    base.get(offset..end).ok_or(Error::CorruptPack)
430}
431
432/// Copy operands omit bytes whose corresponding opcode bit is clear.
433#[inline]
434fn sparse_parameter(mut flags: u8, width: u32, bytes: &mut &[u8]) -> Result<u32> {
435    let mut value = 0;
436    for index in 0..width {
437        if flags & 1 != 0 {
438            value |= u32::from(take_byte(bytes)?) << (index * 8);
439        }
440        flags >>= 1;
441    }
442    Ok(value)
443}
444
445fn byte(bytes: &[u8], cursor: &mut usize) -> Result<u8> {
446    let result = bytes.get(*cursor).copied().ok_or(Error::BufferTooSmall)?;
447    *cursor += 1;
448    Ok(result)
449}
450
451fn take_byte(bytes: &mut &[u8]) -> Result<u8> {
452    let (&first, remaining) = bytes.split_first().ok_or(Error::CorruptPack)?;
453    *bytes = remaining;
454    Ok(first)
455}
456
457fn chunk(value: u64, shift: u32) -> Result<u64> {
458    if shift >= 64 || value > u64::MAX >> shift {
459        return Err(Error::CorruptPack);
460    }
461    Ok(value << shift)
462}
463
464// The buffered and resumable delta decoders share checked size accumulation.
465pub(super) fn variable_byte(value: &mut u64, shift: &mut u32, byte: u8) -> Result<Option<u64>> {
466    *value |= chunk(u64::from(byte & 127), *shift)?;
467    *shift += 7;
468    Ok((byte & 128 == 0).then_some(*value))
469}
470
471fn variable(bytes: &mut &[u8]) -> Result<u64> {
472    let (mut value, mut shift) = (0, 0);
473    loop {
474        if let Some(value) = variable_byte(&mut value, &mut shift, take_byte(bytes)?)? {
475            return Ok(value);
476        }
477    }
478}
git_zero_core/pack/decode.rs

git_zero_core/pack/
decode.rs
