1// SPDX-License-Identifier: MIT
2
3package git
4
5// deltaVarint reads a little-endian base-128 size of a delta header.
6func deltaVarint(d []byte, p int) (v uint64, next int, ok bool) {
7 var shift uint
8 for p < len(d) {
9 c := d[p]
10 p++
11 if shift > 56 {
12 return 0, 0, false
13 }
14 v |= uint64(c&0x7f) << shift
15 shift += 7
16 if c&0x80 == 0 {
17 return v, p, true
18 }
19 }
20 return 0, 0, false
21}
22
23// deltaHeader parses the base size and the result size of a delta.
24func deltaHeader(d []byte) (baseSize, resultSize uint64, body int, err error) {
25 var ok bool
26 baseSize, p, ok := deltaVarint(d, 0)
27 if !ok {
28 return 0, 0, 0, corrupt("delta: bad base size")
29 }
30 resultSize, p, ok = deltaVarint(d, p)
31 if !ok {
32 return 0, 0, 0, corrupt("delta: bad result size")
33 }
34 return baseSize, resultSize, p, nil
35}
36
37// applyDelta applies delta to base and writes the result into dst, whose
38// length is the result size announced by the delta header (checked by the
39// caller with deltaHeader). Every copy and insert is bounds checked.
40func applyDelta(dst, base, delta []byte, body int) error {
41 out := 0
42 p := body
43 for p < len(delta) {
44 op := delta[p]
45 p++
46 switch {
47 case op&0x80 != 0:
48 var off, size uint64
49 for i := uint(0); i < 4; i++ {
50 if op&(1<<i) != 0 {
51 if p >= len(delta) {
52 return corrupt("delta: truncated copy offset")
53 }
54 off |= uint64(delta[p]) << (8 * i)
55 p++
56 }
57 }
58 for i := uint(0); i < 3; i++ {
59 if op&(0x10<<i) != 0 {
60 if p >= len(delta) {
61 return corrupt("delta: truncated copy size")
62 }
63 size |= uint64(delta[p]) << (8 * i)
64 p++
65 }
66 }
67 if size == 0 {
68 size = 0x10000
69 }
70 if off > uint64(len(base)) || size > uint64(len(base))-off {
71 return corrupt("delta: copy %d+%d outside base of %d", off, size, len(base))
72 }
73 if size > uint64(len(dst)-out) {
74 return corrupt("delta: result longer than announced")
75 }
76 copy(dst[out:], base[off:off+size])
77 out += int(size)
78 case op != 0:
79 n := int(op)
80 if n > len(delta)-p {
81 return corrupt("delta: truncated insert")
82 }
83 if n > len(dst)-out {
84 return corrupt("delta: result longer than announced")
85 }
86 copy(dst[out:], delta[p:p+n])
87 p += n
88 out += n
89 default:
90 return corrupt("delta: reserved opcode 0")
91 }
92 }
93 if out != len(dst) {
94 return corrupt("delta: result of %d bytes, %d announced", out, len(dst))
95 }
96 return nil
97}
98
99// patch applies a delta to base and returns the result, which is at most
100// limit bytes. It is the allocating form of applyDelta, for tests and fuzzing.
101func patch(base, delta []byte, limit int64) ([]byte, error) {
102 bs, rs, body, err := deltaHeader(delta)
103 if err != nil {
104 return nil, err
105 }
106 if bs != uint64(len(base)) {
107 return nil, corrupt("delta: base is %d bytes, delta expects %d", len(base), bs)
108 }
109 if rs > uint64(limit) {
110 return nil, ErrTooLarge
111 }
112 dst := make([]byte, rs)
113 if err := applyDelta(dst, base, delta, body); err != nil {
114 return nil, err
115 }
116 return dst, nil
117}