tig_core/
delta.rs

1//! packfile の delta (git 独自形式) の適用。
2//!
3//! delta は「base サイズ、結果サイズ、命令列」から成る。命令は base からの
4//! copy と literal の insert の 2 種。
5
6use alloc::vec::Vec;
7
8use crate::err::{Error, Result};
9
10/// delta を base に適用し、結果の object body を返す。
11pub fn apply(base: &[u8], delta: &[u8]) -> Result<Vec<u8>> {
12    let mut pos = 0;
13    let base_size = read_varint(delta, &mut pos)?;
14    if base_size != base.len() as u64 {
15        return Err(Error::Corrupt("delta base size"));
16    }
17    let result_size = read_varint(delta, &mut pos)?;
18    let mut out = Vec::with_capacity(result_size as usize);
19
20    while pos < delta.len() {
21        let op = delta[pos];
22        pos += 1;
23        if op & 0x80 != 0 {
24            // copy 命令: bit 0-3 が offset、bit 4-6 が size の存在フラグ。
25            let mut offset: usize = 0;
26            for i in 0..4 {
27                if op & (1 << i) != 0 {
28                    let b = *delta.get(pos).ok_or(Error::UnexpectedEof)?;
29                    offset |= usize::from(b) << (8 * i);
30                    pos += 1;
31                }
32            }
33            let mut size: usize = 0;
34            for i in 0..3 {
35                if op & (1 << (4 + i)) != 0 {
36                    let b = *delta.get(pos).ok_or(Error::UnexpectedEof)?;
37                    size |= usize::from(b) << (8 * i);
38                    pos += 1;
39                }
40            }
41            // size 0 は 0x10000 を意味する (git の仕様)。
42            if size == 0 {
43                size = 0x10000;
44            }
45            let src = base
46                .get(offset..offset.checked_add(size).ok_or(Error::UnexpectedEof)?)
47                .ok_or(Error::Corrupt("delta copy range"))?;
48            out.extend_from_slice(src);
49        } else if op != 0 {
50            // insert 命令: op が literal の byte 数。
51            let n = usize::from(op);
52            let src = delta.get(pos..pos + n).ok_or(Error::UnexpectedEof)?;
53            out.extend_from_slice(src);
54            pos += n;
55        } else {
56            return Err(Error::Corrupt("delta opcode 0"));
57        }
58    }
59
60    if out.len() as u64 != result_size {
61        return Err(Error::Corrupt("delta result size"));
62    }
63    Ok(out)
64}
65
66/// delta header の可変長整数 (LSB first、7 bit 単位)。
67fn read_varint(data: &[u8], pos: &mut usize) -> Result<u64> {
68    let mut value: u64 = 0;
69    let mut shift = 0;
70    loop {
71        let b = *data.get(*pos).ok_or(Error::UnexpectedEof)?;
72        *pos += 1;
73        value |= u64::from(b & 0x7f) << shift;
74        if b & 0x80 == 0 {
75            return Ok(value);
76        }
77        shift += 7;
78        if shift >= 64 {
79            return Err(Error::Corrupt("varint overflow"));
80        }
81    }
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn insert_only() {
90        // base サイズ 0、結果サイズ 5、literal 5 byte。
91        let delta = [0, 5, 5, b'h', b'e', b'l', b'l', b'o'];
92        assert_eq!(apply(b"", &delta).unwrap(), b"hello");
93    }
94
95    #[test]
96    fn copy_and_insert() {
97        // base "hello world" から offset 6 size 5 を copy し、"!" を insert。
98        let delta = [11, 6, 0x91, 6, 5, 1, b'!'];
99        assert_eq!(apply(b"hello world", &delta).unwrap(), b"world!");
100    }
101
102    #[test]
103    fn size_mismatch_rejected() {
104        let delta = [0, 4, 5, b'h', b'e', b'l', b'l', b'o'];
105        assert!(apply(b"", &delta).is_err());
106    }
107
108    #[test]
109    fn out_of_range_copy_rejected() {
110        let delta = [5, 5, 0x91, 4, 5];
111        assert!(apply(b"abcde", &delta).is_err());
112    }
113}
tig_core/delta.rs

tig_core/
delta.rs
