Repository navigation
Expand file tree
/
Copy pathdelta.go
More file actions
222 lines (184 loc) · 4.92 KB
/
Copy pathdelta.go
File metadata and controls
222 lines (184 loc) · 4.92 KB
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
package gitgo
import (
"bytes"
"fmt"
"io"
"os"
)
// patchDelta will apply a delta to a base.
func patchDelta(start io.ReadSeeker, delta io.Reader) (io.Reader, error) {
base := errReadSeeker{start, nil}
deltar := newErrReader(delta)
// First, read the source and target lengths (varints)
// we can ignore err as long as we check deltar.err at the end
// we have no need for the targetLength right now, so we discard it
sourceLength, _ := parseVarInt(deltar)
_, _ = parseVarInt(deltar)
if deltar.err != nil {
return nil, deltar.err
}
result := bytes.NewBuffer(nil)
//result = io.MultiWriter(result, os.Stderr)
// Now, the rest of the bytes are either copy or insert instructions
// If the MSB is set, it is a copy
for {
bs := make([]byte, 1)
n := deltar.read(bs)
if n == 0 {
break
}
// b represents our command itself (opcode)
b := bs[0]
switch b & 128 {
case 128:
// b is a copy instruction
// the last four bits represent the offset from the base (source)
var baseOffset int
if (b & 1) > 0 {
baseOffset = baseOffset | int(uint(deltar.readByte()))
}
if (b & 2) > 0 {
baseOffset = baseOffset | int((uint(deltar.readByte()) << 8))
}
if (b & 4) > 0 {
baseOffset = baseOffset | int((uint(deltar.readByte()) << 16))
}
if (b & 8) > 0 {
baseOffset = baseOffset | int((uint(deltar.readByte()) << 24))
}
// read the number of bytes to copy from source→target
// if the fifth bit from the right is set, read the next byte
// The number of copy bytes must fit into
var numBytes uint
if (b & 16) > 0 {
numBytes = numBytes | uint(uint(deltar.readByte()))
}
if (b & 32) > 0 {
numBytes = numBytes | uint((uint(deltar.readByte()) << 8))
}
if (b & 64) > 0 {
numBytes = numBytes | uint((uint(deltar.readByte()) << 16))
}
// Default to 0x10000 due to overflow
if numBytes == 0 {
numBytes = 65536
}
// read numBytes from source, starting at baseOffset
// and write that to the target
base.Seek(int64(baseOffset), os.SEEK_SET)
buf := make([]byte, numBytes)
base.read(buf)
_, err := result.Write(buf)
if err != nil {
return result, err
}
case 0:
if b == 0 {
// cmd == 0 is reserved for future encoding extensions
return nil, fmt.Errorf("cannot process delta opcode 0")
}
// insert instruction
// this means we write data directly from delta to the target
// b itself tells us the number of bytes to write to the target
// the MSB is not set, so the maximum number to insert is 127 bytes
numBytes := int(b)
buf := make([]byte, numBytes)
deltar.read(buf)
_, err := result.Write(buf)
if err != nil {
return nil, err
}
default:
return nil, fmt.Errorf("invalid opcode %08b", b)
}
}
n, err := base.Seek(0, os.SEEK_END)
if err != nil {
return nil, err
}
if n != int64(sourceLength) {
return nil, fmt.Errorf("expected to read %d bytes and read %d", sourceLength, n)
}
if deltar.err == io.EOF {
return result, nil
}
return result, deltar.err
}
func parseVarInt(r io.Reader) (int, error) {
// The MSB of the first byte indicates whether to read
// the next byte
_bytes := make([]byte, 1)
_, err := r.Read(_bytes)
if err != nil {
return 0, err
}
_byte := _bytes[0]
// The most-significant byte (MSB)
// tells us whether we need to read more bytes
// to get the encoded object size
MSB := (_byte & 128) // will be either 128 or 0
// This will extract the last seven bits of the byte
var objectSize = int((uint(_byte) & 127))
// shift the first size by 0
// and the rest by (i-1) * 7
var shift uint
// If the most-significant bit is 0, this is the last byte
// for the object size
for MSB > 0 {
shift += 7
// Keep reading the size until the MSB is 0
_bytes := make([]byte, 1)
_, err := r.Read(_bytes)
if err != nil {
return 0, err
}
_byte := _bytes[0]
MSB = (_byte & 128)
objectSize += int((uint(_byte) & 127) << shift)
}
return objectSize, nil
}
type errReader struct {
r io.Reader
n int
err error
}
// Turn an io.Reader into an errReader.
// If r is already an io.Reader, this is a no-op
func newErrReader(r io.Reader) errReader {
er, ok := r.(errReader)
if !ok {
er = errReader{r, 0, nil}
}
return er
}
// Read, but only if no errors have been encountered
// in a previous read (including io.EOF)
func (er *errReader) read(buf []byte) int {
var n int
if er.err != nil {
return 0
}
n, er.err = io.ReadFull(er.r, buf)
er.n += n
return n
}
// Like read(), but expect a single byte
func (er *errReader) readByte() byte {
b := make([]byte, 1)
n := er.read(b)
if n != 1 && er.err != nil {
if er.err == io.EOF {
er.err = io.EOF
return b[0]
}
er.err = fmt.Errorf("expected to read single byte and read none")
}
return b[0]
}
// Should not actually be called
// Defined only to ensure that errReader is itself an ioReader
func (er errReader) Read(buf []byte) (int, error) {
n := er.read(buf)
return n, er.err
}