1package store
2
3import (
4 "encoding/binary"
5 "fmt"
6)
7
8const (
9 deltaBlockSize = 16
10 deltaMaxDepth = 5
11
12 deltaOpCopy = byte(0x01)
13 deltaOpInsert = byte(0x02)
14 deltaMagic = "ADP1"
15)
16
17func ComputeDelta(base, target []byte) []byte {
18 type blockKey [deltaBlockSize]byte
19
20 table := make(map[blockKey]int32, len(base)/deltaBlockSize+1)
21 for i := 0; i+deltaBlockSize <= len(base); i += deltaBlockSize {
22 var k blockKey
23 copy(k[:], base[i:])
24 if _, exists := table[k]; !exists {
25 table[k] = int32(i)
26 }
27 }
28
29 buf := make([]byte, 0, len(target)/2+8)
30 buf = append(buf, deltaMagic...)
31 buf = binary.BigEndian.AppendUint32(buf, uint32(len(target)))
32
33 pending := make([]byte, 0, 256)
34
35 flushInsert := func() {
36 for len(pending) > 0 {
37 n := len(pending)
38 if n > 0xFFFF {
39 n = 0xFFFF
40 }
41 buf = append(buf, deltaOpInsert)
42 buf = binary.BigEndian.AppendUint32(buf, uint32(n))
43 buf = append(buf, pending[:n]...)
44 pending = pending[n:]
45 }
46 }
47
48 i := 0
49 for i < len(target) {
50 bestSrc, bestLen := 0, 0
51 if i+deltaBlockSize <= len(target) {
52 var k blockKey
53 copy(k[:], target[i:])
54 if srcOff, ok := table[k]; ok {
55 s := int(srcOff)
56 l := deltaBlockSize
57 for i+l < len(target) && s+l < len(base) && target[i+l] == base[s+l] {
58 l++
59 }
60 bestLen = l
61 bestSrc = s
62 }
63 }
64 if bestLen >= deltaBlockSize {
65 flushInsert()
66 totalLen := bestLen
67 for totalLen > 0 {
68 chunk := totalLen
69 if chunk > 0xFFFF {
70 chunk = 0xFFFF
71 }
72 buf = append(buf, deltaOpCopy)
73 buf = binary.BigEndian.AppendUint32(buf, uint32(bestSrc))
74 buf = binary.BigEndian.AppendUint32(buf, uint32(chunk))
75 bestSrc += chunk
76 totalLen -= chunk
77 }
78 i += bestLen
79 } else {
80 pending = append(pending, target[i])
81 i++
82 }
83 }
84 flushInsert()
85 return buf
86}
87
88func ApplyDelta(base, delta []byte) ([]byte, error) {
89 if len(delta) < 8 {
90 return nil, fmt.Errorf("delta: stream too short (%d bytes)", len(delta))
91 }
92 if string(delta[:4]) != deltaMagic {
93 return nil, fmt.Errorf("delta: invalid magic %q", delta[:4])
94 }
95 targetSize := int(binary.BigEndian.Uint32(delta[4:8]))
96 out := make([]byte, 0, targetSize)
97
98 pos := 8
99 for pos < len(delta) {
100 op := delta[pos]
101 pos++
102 switch op {
103 case deltaOpCopy:
104 if pos+8 > len(delta) {
105 return nil, fmt.Errorf("delta: COPY instruction truncated at pos %d", pos)
106 }
107 srcOff := int(binary.BigEndian.Uint32(delta[pos : pos+4]))
108 length := int(binary.BigEndian.Uint32(delta[pos+4 : pos+8]))
109 pos += 8
110 if srcOff < 0 || length < 0 || srcOff+length > len(base) {
111 return nil, fmt.Errorf("delta: COPY out of bounds (srcOff=%d len=%d baseLen=%d)",
112 srcOff, length, len(base))
113 }
114 out = append(out, base[srcOff:srcOff+length]...)
115
116 case deltaOpInsert:
117 if pos+4 > len(delta) {
118 return nil, fmt.Errorf("delta: INSERT length truncated at pos %d", pos)
119 }
120 length := int(binary.BigEndian.Uint32(delta[pos : pos+4]))
121 pos += 4
122 if pos+length > len(delta) {
123 return nil, fmt.Errorf("delta: INSERT data truncated (need %d, have %d)", length, len(delta)-pos)
124 }
125 out = append(out, delta[pos:pos+length]...)
126 pos += length
127
128 default:
129 return nil, fmt.Errorf("delta: unknown opcode 0x%02x at pos %d", op, pos-1)
130 }
131 }
132 if len(out) != targetSize {
133 return nil, fmt.Errorf("delta: size mismatch (expected %d, got %d)", targetSize, len(out))
134 }
135 return out, nil
136}