tig_core/
pack.rs

1//! packfile (version 2) の解析。
2//!
3//! pack は「12 byte header + object entry の列 + SHA-1 trailer」から成る。entry の
4//! 圧縮後長は記録されないため、先頭から順に伸長しながら境界を求める。parse 時に
5//! 全 entry を一度 materialize して oid を確定し、oid 順の index (entry あたり
6//! 24 byte) を構築する。object の内容は保持せず、読み出しのたびに伸長し直す
7//! (メモリを CPU で贖う方針)。
8
9use alloc::vec::Vec;
10
11use crate::delta;
12use crate::err::{Error, Result};
13use crate::object::Kind;
14use crate::oid::Oid;
15use crate::sha1;
16use crate::zlib;
17
18/// 解析済みの packfile。`data` は pack 全体 (header と trailer を含む)。
19pub struct Pack<'a> {
20    data: &'a [u8],
21    /// trailer (SHA-1) を除いた末尾位置。
22    content_end: usize,
23    /// oid 順に整列した (oid, entry の開始 offset)。
24    index: Vec<(Oid, u32)>,
25}
26
27/// entry の種別 code (pack 形式の生値)。
28const OBJ_COMMIT: u8 = 1;
29const OBJ_TREE: u8 = 2;
30const OBJ_BLOB: u8 = 3;
31const OBJ_TAG: u8 = 4;
32const OBJ_OFS_DELTA: u8 = 6;
33const OBJ_REF_DELTA: u8 = 7;
34
35/// delta chain 長の上限。循環参照 (破損データ) の検出を兼ねる。
36const MAX_DELTA_DEPTH: usize = 4096;
37
38/// [`Pack::parse`] が delta 解決の途中結果を保持する一時 cache の既定予算 (byte)。
39/// 解析中のみ確保し、`Pack` には残らない。
40pub const DEFAULT_BASE_CACHE_BYTES: usize = 64 * 1024;
41/// base cache の entry 数の上限 (線形探索で済む範囲に抑える)。
42const BASE_CACHE_ENTRIES: usize = 64;
43
44/// delta 解決の途中結果 (entry offset → object) の上限付き cache。
45///
46/// pass 2 では同じ base を持つ delta が連続しがちで、cache が無いと base を
47/// その都度伸長し直す。予算を超えたら古いものから捨てる (FIFO)。予算より
48/// 大きい object は保持しない。
49struct BaseCache {
50    entries: Vec<(u32, Kind, Vec<u8>)>,
51    bytes: usize,
52    budget: usize,
53}
54
55impl BaseCache {
56    fn new(budget: usize) -> Self {
57        Self {
58            entries: Vec::new(),
59            bytes: 0,
60            budget,
61        }
62    }
63
64    fn get(&self, offset: usize) -> Option<(Kind, &[u8])> {
65        self.entries
66            .iter()
67            .find(|(o, _, _)| *o as usize == offset)
68            .map(|(_, kind, body)| (*kind, body.as_slice()))
69    }
70
71    fn insert(&mut self, offset: usize, kind: Kind, body: &[u8]) {
72        if body.len() > self.budget || self.get(offset).is_some() {
73            return;
74        }
75        while !self.entries.is_empty()
76            && (self.bytes + body.len() > self.budget || self.entries.len() >= BASE_CACHE_ENTRIES)
77        {
78            let (_, _, evicted) = self.entries.remove(0);
79            self.bytes -= evicted.len();
80        }
81        self.bytes += body.len();
82        self.entries.push((offset as u32, kind, body.to_vec()));
83    }
84}
85
86impl<'a> Pack<'a> {
87    pub fn parse(data: &'a [u8]) -> Result<Self> {
88        Self::parse_with_cache(data, DEFAULT_BASE_CACHE_BYTES)
89    }
90
91    /// [`Pack::parse`] の base cache 予算を指定する版。`0` で cache を無効化する
92    /// (メモリの厳しい環境向け。解析時間は delta chain の重複分だけ延びる)。
93    pub fn parse_with_cache(data: &'a [u8], cache_bytes: usize) -> Result<Self> {
94        if data.len() < 12 + 20 {
95            return Err(Error::UnexpectedEof);
96        }
97        if &data[0..4] != b"PACK" {
98            return Err(Error::Corrupt("pack magic"));
99        }
100        if u32::from_be_bytes(data[4..8].try_into().unwrap()) != 2 {
101            return Err(Error::Unsupported("pack version"));
102        }
103        if data.len() as u64 > u64::from(u32::MAX) {
104            return Err(Error::Unsupported("pack larger than 4 GiB"));
105        }
106        let count = u32::from_be_bytes(data[8..12].try_into().unwrap()) as usize;
107
108        let content_end = data.len() - 20;
109        if sha1::digest(&data[..content_end]) != data[content_end..] {
110            return Err(Error::Checksum("pack trailer"));
111        }
112
113        // pass 1: 全 entry を走査して境界を確定し、delta でない object の oid を求める。
114        let mut index: Vec<(Oid, u32)> = Vec::with_capacity(count.min(1 << 16));
115        let mut pending: Vec<u32> = Vec::new();
116        let mut offset = 12usize;
117        for _ in 0..count {
118            if offset >= content_end {
119                return Err(Error::UnexpectedEof);
120            }
121            let (code, size, pos) = entry_header(data, offset, content_end)?;
122            let (_, zlib_start) = base_ref(data, code, pos, offset, content_end)?;
123            let inflated = zlib::inflate_zlib(&data[zlib_start..content_end], Some(size))?;
124            if inflated.data.len() != size {
125                return Err(Error::Corrupt("entry size"));
126            }
127            match code {
128                OBJ_COMMIT | OBJ_TREE | OBJ_BLOB | OBJ_TAG => {
129                    let kind = kind_of(code)?;
130                    index.push((
131                        crate::object::compute_oid(kind, &inflated.data),
132                        offset as u32,
133                    ));
134                }
135                _ => pending.push(offset as u32),
136            }
137            offset = zlib_start + inflated.consumed;
138        }
139        if offset != content_end {
140            return Err(Error::Corrupt("trailing bytes after entries"));
141        }
142        index.sort_unstable();
143
144        // pass 2: delta entry を base の解決可能なものから順に materialize する。
145        // ofs delta の base は常に前方にあるが、ref delta は任意の位置を指せるため、
146        // 進展が無くなるまで繰り返す (通常は 1 回で完了する)。
147        let mut cache = BaseCache::new(cache_bytes);
148        while !pending.is_empty() {
149            let mut unresolved = Vec::new();
150            let mut resolved_any = false;
151            for &entry_offset in &pending {
152                match materialize(
153                    data,
154                    content_end,
155                    &index,
156                    entry_offset as usize,
157                    Some(&mut cache),
158                ) {
159                    Ok((kind, body)) => {
160                        index.push((crate::object::compute_oid(kind, &body), entry_offset));
161                        resolved_any = true;
162                    }
163                    Err(Error::MissingBase) => unresolved.push(entry_offset),
164                    Err(e) => return Err(e),
165                }
166            }
167            if !resolved_any {
168                return Err(Error::MissingBase);
169            }
170            index.sort_unstable();
171            pending = unresolved;
172        }
173
174        Ok(Self {
175            data,
176            content_end,
177            index,
178        })
179    }
180
181    /// pack 内の object 数。
182    pub fn len(&self) -> usize {
183        self.index.len()
184    }
185
186    pub fn is_empty(&self) -> bool {
187        self.index.is_empty()
188    }
189
190    pub fn contains(&self, oid: &Oid) -> bool {
191        lookup(&self.index, oid).is_some()
192    }
193
194    /// pack 内の全 oid (oid 順)。
195    pub fn oids(&self) -> impl Iterator<Item = &Oid> {
196        self.index.iter().map(|(oid, _)| oid)
197    }
198
199    /// object を読み出す (delta は都度解決する)。
200    pub fn read_object(&self, oid: &Oid) -> Result<Option<(Kind, Vec<u8>)>> {
201        match lookup(&self.index, oid) {
202            None => Ok(None),
203            Some(offset) => materialize(
204                self.data,
205                self.content_end,
206                &self.index,
207                offset as usize,
208                None,
209            )
210            .map(Some),
211        }
212    }
213}
214
215impl crate::Odb for Pack<'_> {
216    fn read(&self, oid: &Oid) -> Option<(Kind, Vec<u8>)> {
217        // parse 時に全 entry の materialize が成功しているため、ここでの失敗は
218        // 実質的に到達しない。
219        self.read_object(oid).ok().flatten()
220    }
221}
222
223fn lookup(index: &[(Oid, u32)], oid: &Oid) -> Option<u32> {
224    index
225        .binary_search_by(|(o, _)| o.cmp(oid))
226        .ok()
227        .map(|i| index[i].1)
228}
229
230fn kind_of(code: u8) -> Result<Kind> {
231    match code {
232        OBJ_COMMIT => Ok(Kind::Commit),
233        OBJ_TREE => Ok(Kind::Tree),
234        OBJ_BLOB => Ok(Kind::Blob),
235        OBJ_TAG => Ok(Kind::Tag),
236        _ => Err(Error::Corrupt("object type code")),
237    }
238}
239
240/// entry の base 参照。
241enum BaseRef {
242    None,
243    /// base entry の絶対 offset。
244    Offset(usize),
245    Oid(Oid),
246}
247
248/// entry 先頭の type/size varint を読む。返り値は (type code, 伸長後サイズ, 次の位置)。
249fn entry_header(data: &[u8], offset: usize, end: usize) -> Result<(u8, usize, usize)> {
250    let mut pos = offset;
251    let mut byte = *data
252        .get(pos)
253        .filter(|_| pos < end)
254        .ok_or(Error::UnexpectedEof)?;
255    pos += 1;
256    let code = (byte >> 4) & 0x07;
257    let mut size = usize::from(byte & 0x0f);
258    let mut shift = 4;
259    while byte & 0x80 != 0 {
260        byte = *data
261            .get(pos)
262            .filter(|_| pos < end)
263            .ok_or(Error::UnexpectedEof)?;
264        pos += 1;
265        if shift >= usize::BITS {
266            return Err(Error::Corrupt("entry size varint"));
267        }
268        size |= usize::from(byte & 0x7f) << shift;
269        shift += 7;
270    }
271    Ok((code, size, pos))
272}
273
274/// type/size varint の直後にある base 参照を読む。返り値は (base, zlib stream の開始位置)。
275///
276/// 読み取りは `end` (trailer の手前) で打ち切る。trailer は checksum であって
277/// entry の一部ではなく、境界検査を怠ると checksum 込みで細工した pack が
278/// `zlib_start > end` の slice を作り panic に至る。
279fn base_ref(
280    data: &[u8],
281    code: u8,
282    pos: usize,
283    entry_offset: usize,
284    end: usize,
285) -> Result<(BaseRef, usize)> {
286    match code {
287        OBJ_COMMIT | OBJ_TREE | OBJ_BLOB | OBJ_TAG => Ok((BaseRef::None, pos)),
288        OBJ_OFS_DELTA => {
289            // 負 offset の varint (MSB first、継続時に +1 する git 独自形式)。
290            let mut p = pos;
291            let mut byte = *data
292                .get(p)
293                .filter(|_| p < end)
294                .ok_or(Error::UnexpectedEof)?;
295            p += 1;
296            let mut value = u64::from(byte & 0x7f);
297            while byte & 0x80 != 0 {
298                byte = *data
299                    .get(p)
300                    .filter(|_| p < end)
301                    .ok_or(Error::UnexpectedEof)?;
302                p += 1;
303                value = value
304                    .checked_add(1)
305                    .and_then(|v| v.checked_shl(7))
306                    .ok_or(Error::Corrupt("ofs delta varint"))?
307                    | u64::from(byte & 0x7f);
308            }
309            let base = (entry_offset as u64)
310                .checked_sub(value)
311                .filter(|&b| b >= 12)
312                .ok_or(Error::Corrupt("ofs delta base offset"))?;
313            Ok((BaseRef::Offset(base as usize), p))
314        }
315        OBJ_REF_DELTA => {
316            if pos + 20 > end {
317                return Err(Error::UnexpectedEof);
318            }
319            let bytes = &data[pos..pos + 20];
320            Ok((
321                BaseRef::Oid(Oid::from_bytes(bytes.try_into().unwrap())),
322                pos + 20,
323            ))
324        }
325        _ => Err(Error::Corrupt("object type code")),
326    }
327}
328
329/// offset の entry を delta chain を解決しつつ復元する。
330///
331/// 再帰を使わず、chain を配列に積んでから base 側から適用する。組み込みの
332/// 小さい stack でも chain 長に依存せず動作する。`cache` があれば chain の
333/// 途中で cache 済みの object に当たった時点で打ち切り、復元した各段を
334/// cache へ入れる。
335fn materialize(
336    data: &[u8],
337    content_end: usize,
338    index: &[(Oid, u32)],
339    offset: usize,
340    mut cache: Option<&mut BaseCache>,
341) -> Result<(Kind, Vec<u8>)> {
342    // chain: 適用すべき delta entry の (entry offset, zlib 開始位置, 伸長後サイズ)
343    // (外側から順)。
344    let mut chain: Vec<(usize, usize, usize)> = Vec::new();
345    let mut cur = offset;
346
347    let (kind, mut body) = loop {
348        if chain.len() > MAX_DELTA_DEPTH {
349            return Err(Error::Corrupt("delta chain too deep"));
350        }
351        if let Some((kind, body)) = cache.as_deref().and_then(|c| c.get(cur)) {
352            break (kind, body.to_vec());
353        }
354        let (code, size, pos) = entry_header(data, cur, content_end)?;
355        let (base, zlib_start) = base_ref(data, code, pos, cur, content_end)?;
356        match base {
357            BaseRef::None => {
358                let inflated = zlib::inflate_zlib(&data[zlib_start..content_end], Some(size))?;
359                if inflated.data.len() != size {
360                    return Err(Error::Corrupt("entry size"));
361                }
362                let kind = kind_of(code)?;
363                if let Some(c) = cache.as_deref_mut() {
364                    c.insert(cur, kind, &inflated.data);
365                }
366                break (kind, inflated.data);
367            }
368            BaseRef::Offset(base_offset) => {
369                chain.push((cur, zlib_start, size));
370                cur = base_offset;
371            }
372            BaseRef::Oid(oid) => {
373                chain.push((cur, zlib_start, size));
374                cur = lookup(index, &oid).ok_or(Error::MissingBase)? as usize;
375            }
376        }
377    };
378
379    for &(entry_offset, zlib_start, size) in chain.iter().rev() {
380        let inflated = zlib::inflate_zlib(&data[zlib_start..content_end], Some(size))?;
381        if inflated.data.len() != size {
382            return Err(Error::Corrupt("entry size"));
383        }
384        body = delta::apply(&body, &inflated.data)?;
385        if let Some(c) = cache.as_deref_mut() {
386            c.insert(entry_offset, kind, &body);
387        }
388    }
389    Ok((kind, body))
390}
391
392/// object の列から packfile (version 2、非 delta) を生成する。
393///
394/// entry の zlib stream は fixed Huffman で圧縮する (`zlib::deflate_zlib`)。
395/// delta は生成しない (docs/design.md)。
396#[cfg(feature = "write")]
397pub fn write_pack(objects: &[(Kind, &[u8])]) -> Vec<u8> {
398    let mut out = Vec::new();
399    out.extend_from_slice(b"PACK");
400    out.extend_from_slice(&2u32.to_be_bytes());
401    out.extend_from_slice(&(objects.len() as u32).to_be_bytes());
402
403    for (kind, body) in objects {
404        let code: u8 = match kind {
405            Kind::Commit => OBJ_COMMIT,
406            Kind::Tree => OBJ_TREE,
407            Kind::Blob => OBJ_BLOB,
408            Kind::Tag => OBJ_TAG,
409        };
410        let mut size = body.len();
411        let mut byte = (code << 4) | (size & 0x0f) as u8;
412        size >>= 4;
413        while size > 0 {
414            out.push(byte | 0x80);
415            byte = (size & 0x7f) as u8;
416            size >>= 7;
417        }
418        out.push(byte);
419        out.extend_from_slice(&zlib::deflate_zlib(body));
420    }
421
422    let digest = sha1::digest(&out);
423    out.extend_from_slice(&digest);
424    out
425}
426
427#[cfg(test)]
428mod tests {
429    use super::*;
430
431    /// content に正しい SHA-1 trailer を付けて pack として成立させる。
432    /// checksum は転送誤り検出であって悪意への防御ではないため、細工された
433    /// pack も checksum は正しくなり得る。
434    fn with_trailer(mut content: Vec<u8>) -> Vec<u8> {
435        let digest = sha1::digest(&content);
436        content.extend_from_slice(&digest);
437        content
438    }
439
440    fn header(count: u32) -> Vec<u8> {
441        let mut c = Vec::new();
442        c.extend_from_slice(b"PACK");
443        c.extend_from_slice(&2u32.to_be_bytes());
444        c.extend_from_slice(&count.to_be_bytes());
445        c
446    }
447
448    // ref delta の 20 byte base oid が trailer に食い込む pack を拒否すること
449    // (panic ではなくエラーで返す)。
450    #[test]
451    fn ref_delta_base_into_trailer_rejected() {
452        let mut c = header(1);
453        c.push(0x70); // type=ref_delta, size=0
454        c.extend_from_slice(&[0xaa; 5]); // base oid の途中で entry 領域が尽きる
455        assert!(Pack::parse(&with_trailer(c)).is_err());
456    }
457
458    // ofs delta の負 offset varint が trailer に食い込む pack を拒否すること。
459    #[test]
460    fn ofs_delta_varint_into_trailer_rejected() {
461        let mut c = header(1);
462        c.push(0x60); // type=ofs_delta, size=0
463        c.extend_from_slice(&[0x80; 3]); // 継続 bit が立ったまま entry 領域が尽きる
464        assert!(Pack::parse(&with_trailer(c)).is_err());
465    }
466
467    // 空 (entry 0 件) の pack は正常に解析できること。
468    #[test]
469    fn empty_pack() {
470        let pack = with_trailer(header(0));
471        assert!(Pack::parse(&pack).unwrap().is_empty());
472    }
473
474    // 書いた pack を自前の parser (git との差分テスト済み) で往復できること。
475    #[cfg(feature = "write")]
476    #[test]
477    fn write_pack_roundtrip() {
478        let blob = b"hello\n".as_slice();
479        let large: Vec<u8> = (0..100_000usize).map(|i| (i % 251) as u8).collect();
480        let objects = [(Kind::Blob, blob), (Kind::Blob, large.as_slice())];
481        let data = write_pack(&objects);
482
483        let pack = Pack::parse(&data).unwrap();
484        assert_eq!(pack.len(), 2);
485        for (kind, body) in &objects {
486            let oid = crate::object::compute_oid(*kind, body);
487            let (got_kind, got_body) = pack.read_object(&oid).unwrap().unwrap();
488            assert_eq!(got_kind, *kind);
489            assert_eq!(got_body, *body);
490        }
491    }
492}
tig_core/pack.rs

tig_core/
pack.rs
