weavatrix-git 0.2.0

Dependency-free, evidence-carrying Git repository reader
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use crate::{GitError, Result, error::invalid};

pub(super) fn apply(base: &[u8], delta: &[u8], limit: usize) -> Result<Vec<u8>> {
    let mut cursor = 0;
    let base_size = read_varint(delta, &mut cursor)?;
    if base_size != base.len() {
        return Err(invalid("pack delta base size mismatch"));
    }
    let result_size = read_varint(delta, &mut cursor)?;
    if result_size > limit {
        return Err(GitError::LimitExceeded {
            resource: "delta result bytes",
            limit,
        });
    }
    let mut result = Vec::with_capacity(result_size);
    while cursor < delta.len() {
        let opcode = delta[cursor];
        cursor += 1;
        if opcode & 0x80 != 0 {
            copy(base, delta, &mut cursor, opcode, &mut result, limit)?;
        } else if opcode != 0 {
            let count = usize::from(opcode);
            let end = cursor
                .checked_add(count)
                .ok_or_else(|| invalid("delta insert overflow"))?;
            let bytes = delta
                .get(cursor..end)
                .ok_or_else(|| invalid("truncated delta insert"))?;
            extend(&mut result, bytes, limit)?;
            cursor = end;
        } else {
            return Err(invalid("reserved pack delta opcode"));
        }
    }
    if result.len() != result_size {
        return Err(invalid("pack delta result size mismatch"));
    }
    Ok(result)
}

fn copy(
    base: &[u8],
    delta: &[u8],
    cursor: &mut usize,
    opcode: u8,
    output: &mut Vec<u8>,
    limit: usize,
) -> Result<()> {
    let mut offset = 0_usize;
    let mut size = 0_usize;
    for index in 0..4 {
        if opcode & (1 << index) != 0 {
            offset |= usize::from(take(delta, cursor)?) << (index * 8);
        }
    }
    for index in 0..3 {
        if opcode & (1 << (index + 4)) != 0 {
            size |= usize::from(take(delta, cursor)?) << (index * 8);
        }
    }
    if size == 0 {
        size = 0x1_0000;
    }
    let end = offset
        .checked_add(size)
        .ok_or_else(|| invalid("delta copy overflow"))?;
    let bytes = base
        .get(offset..end)
        .ok_or_else(|| invalid("delta copy exceeds base"))?;
    extend(output, bytes, limit)
}

fn take(input: &[u8], cursor: &mut usize) -> Result<u8> {
    let value = *input
        .get(*cursor)
        .ok_or_else(|| invalid("truncated pack delta"))?;
    *cursor += 1;
    Ok(value)
}

fn read_varint(input: &[u8], cursor: &mut usize) -> Result<usize> {
    let mut value = 0_usize;
    let mut shift = 0;
    loop {
        let byte = take(input, cursor)?;
        value = value
            .checked_add(usize::from(byte & 0x7f) << shift)
            .ok_or_else(|| invalid("pack delta varint overflow"))?;
        if byte & 0x80 == 0 {
            return Ok(value);
        }
        shift += 7;
        if shift >= usize::BITS {
            return Err(invalid("pack delta varint is too long"));
        }
    }
}

fn extend(output: &mut Vec<u8>, bytes: &[u8], limit: usize) -> Result<()> {
    if output
        .len()
        .checked_add(bytes.len())
        .is_none_or(|size| size > limit)
    {
        return Err(GitError::LimitExceeded {
            resource: "delta result bytes",
            limit,
        });
    }
    output.extend_from_slice(bytes);
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::apply;

    #[test]
    fn applies_insert_and_copy_delta() {
        let delta = [5, 11, 0x91, 0, 5, 6, b' ', b'w', b'o', b'r', b'l', b'd'];
        assert_eq!(apply(b"hello", &delta, 20).unwrap(), b"hello world");
    }

    #[test]
    fn rejects_malformed_delta_programs() {
        assert!(apply(b"hello", &[4, 0], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 0], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 2, b'a'], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 1, b'a'], 0).is_err());
        assert!(apply(b"hello", &[5, 1, 0x91], 20).is_err());
        assert!(apply(b"hello", &[5, 1, 0x91, 9, 1], 20).is_err());
        assert!(apply(b"hello", &[0x80; 20], 20).is_err());
    }
}