cubefs

1
package zstd
2

3
import (
4
	"fmt"
5
	"math/bits"
6

7
	"github.com/klauspost/compress/zstd/internal/xxhash"
8
)
9

10
const (
11
	dictShardBits = 6
12
)
13

14
type fastBase struct {
15
	// cur is the offset at the start of hist
16
	cur int32
17
	// maximum offset. Should be at least 2x block size.
18
	maxMatchOff int32
19
	hist        []byte
20
	crc         *xxhash.Digest
21
	tmp         [8]byte
22
	blk         *blockEnc
23
	lastDictID  uint32
24
	lowMem      bool
25
}
26

27
// CRC returns the underlying CRC writer.
28
func (e *fastBase) CRC() *xxhash.Digest {
29
	return e.crc
30
}
31

32
// AppendCRC will append the CRC to the destination slice and return it.
33
func (e *fastBase) AppendCRC(dst []byte) []byte {
34
	crc := e.crc.Sum(e.tmp[:0])
35
	dst = append(dst, crc[7], crc[6], crc[5], crc[4])
36
	return dst
37
}
38

39
// WindowSize returns the window size of the encoder,
40
// or a window size small enough to contain the input size, if > 0.
41
func (e *fastBase) WindowSize(size int64) int32 {
42
	if size > 0 && size < int64(e.maxMatchOff) {
43
		b := int32(1) << uint(bits.Len(uint(size)))
44
		// Keep minimum window.
45
		if b < 1024 {
46
			b = 1024
47
		}
48
		return b
49
	}
50
	return e.maxMatchOff
51
}
52

53
// Block returns the current block.
54
func (e *fastBase) Block() *blockEnc {
55
	return e.blk
56
}
57

58
func (e *fastBase) addBlock(src []byte) int32 {
59
	if debugAsserts && e.cur > bufferReset {
60
		panic(fmt.Sprintf("ecur (%d) > buffer reset (%d)", e.cur, bufferReset))
61
	}
62
	// check if we have space already
63
	if len(e.hist)+len(src) > cap(e.hist) {
64
		if cap(e.hist) == 0 {
65
			e.ensureHist(len(src))
66
		} else {
67
			if cap(e.hist) < int(e.maxMatchOff+maxCompressedBlockSize) {
68
				panic(fmt.Errorf("unexpected buffer cap %d, want at least %d with window %d", cap(e.hist), e.maxMatchOff+maxCompressedBlockSize, e.maxMatchOff))
69
			}
70
			// Move down
71
			offset := int32(len(e.hist)) - e.maxMatchOff
72
			copy(e.hist[0:e.maxMatchOff], e.hist[offset:])
73
			e.cur += offset
74
			e.hist = e.hist[:e.maxMatchOff]
75
		}
76
	}
77
	s := int32(len(e.hist))
78
	e.hist = append(e.hist, src...)
79
	return s
80
}
81

82
// ensureHist will ensure that history can keep at least this many bytes.
83
func (e *fastBase) ensureHist(n int) {
84
	if cap(e.hist) >= n {
85
		return
86
	}
87
	l := e.maxMatchOff
88
	if (e.lowMem && e.maxMatchOff > maxCompressedBlockSize) || e.maxMatchOff <= maxCompressedBlockSize {
89
		l += maxCompressedBlockSize
90
	} else {
91
		l += e.maxMatchOff
92
	}
93
	// Make it at least 1MB.
94
	if l < 1<<20 && !e.lowMem {
95
		l = 1 << 20
96
	}
97
	// Make it at least the requested size.
98
	if l < int32(n) {
99
		l = int32(n)
100
	}
101
	e.hist = make([]byte, 0, l)
102
}
103

104
// useBlock will replace the block with the provided one,
105
// but transfer recent offsets from the previous.
106
func (e *fastBase) UseBlock(enc *blockEnc) {
107
	enc.reset(e.blk)
108
	e.blk = enc
109
}
110

111
func (e *fastBase) matchlen(s, t int32, src []byte) int32 {
112
	if debugAsserts {
113
		if s < 0 {
114
			err := fmt.Sprintf("s (%d) < 0", s)
115
			panic(err)
116
		}
117
		if t < 0 {
118
			err := fmt.Sprintf("s (%d) < 0", s)
119
			panic(err)
120
		}
121
		if s-t > e.maxMatchOff {
122
			err := fmt.Sprintf("s (%d) - t (%d) > maxMatchOff (%d)", s, t, e.maxMatchOff)
123
			panic(err)
124
		}
125
		if len(src)-int(s) > maxCompressedBlockSize {
126
			panic(fmt.Sprintf("len(src)-s (%d) > maxCompressedBlockSize (%d)", len(src)-int(s), maxCompressedBlockSize))
127
		}
128
	}
129
	a := src[s:]
130
	b := src[t:]
131
	b = b[:len(a)]
132
	end := int32((len(a) >> 3) << 3)
133
	for i := int32(0); i < end; i += 8 {
134
		if diff := load6432(a, i) ^ load6432(b, i); diff != 0 {
135
			return i + int32(bits.TrailingZeros64(diff)>>3)
136
		}
137
	}
138

139
	a = a[end:]
140
	b = b[end:]
141
	for i := range a {
142
		if a[i] != b[i] {
143
			return int32(i) + end
144
		}
145
	}
146
	return int32(len(a)) + end
147
}
148

149
// Reset the encoding table.
150
func (e *fastBase) resetBase(d *dict, singleBlock bool) {
151
	if e.blk == nil {
152
		e.blk = &blockEnc{lowMem: e.lowMem}
153
		e.blk.init()
154
	} else {
155
		e.blk.reset(nil)
156
	}
157
	e.blk.initNewEncode()
158
	if e.crc == nil {
159
		e.crc = xxhash.New()
160
	} else {
161
		e.crc.Reset()
162
	}
163
	if d != nil {
164
		low := e.lowMem
165
		if singleBlock {
166
			e.lowMem = true
167
		}
168
		e.ensureHist(d.DictContentSize() + maxCompressedBlockSize)
169
		e.lowMem = low
170
	}
171

172
	// We offset current position so everything will be out of reach.
173
	// If above reset line, history will be purged.
174
	if e.cur < bufferReset {
175
		e.cur += e.maxMatchOff + int32(len(e.hist))
176
	}
177
	e.hist = e.hist[:0]
178
	if d != nil {
179
		// Set offsets (currently not used)
180
		for i, off := range d.offsets {
181
			e.blk.recentOffsets[i] = uint32(off)
182
			e.blk.prevRecentOffsets[i] = e.blk.recentOffsets[i]
183
		}
184
		// Transfer litenc.
185
		e.blk.dictLitEnc = d.litEnc
186
		e.hist = append(e.hist, d.content...)
187
	}
188
}
189