blob: 664d9be580d415c2c53e290b466c1ff0d86f39fe [file] [log] [blame]
Holger Hildebrandtfa074992020-03-27 15:42:06 +00001package lz4
2
3import (
4 "encoding/binary"
Holger Hildebrandtfa074992020-03-27 15:42:06 +00005 "math/bits"
khenaidoo7d3c5582021-08-11 18:09:44 -04006 "sync"
Holger Hildebrandtfa074992020-03-27 15:42:06 +00007)
8
9// blockHash hashes the lower 6 bytes into a value < htSize.
10func blockHash(x uint64) uint32 {
11 const prime6bytes = 227718039650203
12 return uint32(((x << (64 - 48)) * prime6bytes) >> (64 - hashLog))
13}
14
15// CompressBlockBound returns the maximum size of a given buffer of size n, when not compressible.
16func CompressBlockBound(n int) int {
17 return n + n/255 + 16
18}
19
20// UncompressBlock uncompresses the source buffer into the destination one,
21// and returns the uncompressed size.
22//
23// The destination buffer must be sized appropriately.
24//
25// An error is returned if the source data is invalid or the destination buffer is too small.
26func UncompressBlock(src, dst []byte) (int, error) {
27 if len(src) == 0 {
28 return 0, nil
29 }
30 if di := decodeBlock(dst, src); di >= 0 {
31 return di, nil
32 }
33 return 0, ErrInvalidSourceShortBuffer
34}
35
36// CompressBlock compresses the source buffer into the destination one.
37// This is the fast version of LZ4 compression and also the default one.
Holger Hildebrandtfa074992020-03-27 15:42:06 +000038//
khenaidoo7d3c5582021-08-11 18:09:44 -040039// The argument hashTable is scratch space for a hash table used by the
40// compressor. If provided, it should have length at least 1<<16. If it is
41// shorter (or nil), CompressBlock allocates its own hash table.
42//
43// The size of the compressed data is returned.
44//
45// If the destination buffer size is lower than CompressBlockBound and
46// the compressed size is 0 and no error, then the data is incompressible.
Holger Hildebrandtfa074992020-03-27 15:42:06 +000047//
48// An error is returned if the destination buffer is too small.
khenaidoo7d3c5582021-08-11 18:09:44 -040049func CompressBlock(src, dst []byte, hashTable []int) (_ int, err error) {
Holger Hildebrandtfa074992020-03-27 15:42:06 +000050 defer recoverBlock(&err)
51
khenaidoo7d3c5582021-08-11 18:09:44 -040052 // Return 0, nil only if the destination buffer size is < CompressBlockBound.
53 isNotCompressible := len(dst) < CompressBlockBound(len(src))
54
Holger Hildebrandtfa074992020-03-27 15:42:06 +000055 // adaptSkipLog sets how quickly the compressor begins skipping blocks when data is incompressible.
khenaidoo7d3c5582021-08-11 18:09:44 -040056 // This significantly speeds up incompressible data and usually has very small impact on compression.
Holger Hildebrandtfa074992020-03-27 15:42:06 +000057 // bytes to skip = 1 + (bytes since last match >> adaptSkipLog)
58 const adaptSkipLog = 7
Holger Hildebrandtfa074992020-03-27 15:42:06 +000059 if len(hashTable) < htSize {
khenaidoo7d3c5582021-08-11 18:09:44 -040060 htIface := htPool.Get()
61 defer htPool.Put(htIface)
62 hashTable = (*(htIface).(*[htSize]int))[:]
Holger Hildebrandtfa074992020-03-27 15:42:06 +000063 }
64 // Prove to the compiler the table has at least htSize elements.
65 // The compiler can see that "uint32() >> hashShift" cannot be out of bounds.
66 hashTable = hashTable[:htSize]
67
68 // si: Current position of the search.
69 // anchor: Position of the current literals.
khenaidoo7d3c5582021-08-11 18:09:44 -040070 var si, di, anchor int
71 sn := len(src) - mfLimit
72 if sn <= 0 {
73 goto lastLiterals
74 }
Holger Hildebrandtfa074992020-03-27 15:42:06 +000075
76 // Fast scan strategy: the hash table only stores the last 4 bytes sequences.
77 for si < sn {
78 // Hash the next 6 bytes (sequence)...
79 match := binary.LittleEndian.Uint64(src[si:])
80 h := blockHash(match)
81 h2 := blockHash(match >> 8)
82
83 // We check a match at s, s+1 and s+2 and pick the first one we get.
84 // Checking 3 only requires us to load the source one.
85 ref := hashTable[h]
86 ref2 := hashTable[h2]
87 hashTable[h] = si
88 hashTable[h2] = si + 1
89 offset := si - ref
90
91 // If offset <= 0 we got an old entry in the hash table.
92 if offset <= 0 || offset >= winSize || // Out of window.
93 uint32(match) != binary.LittleEndian.Uint32(src[ref:]) { // Hash collision on different matches.
94 // No match. Start calculating another hash.
95 // The processor can usually do this out-of-order.
96 h = blockHash(match >> 16)
97 ref = hashTable[h]
98
99 // Check the second match at si+1
100 si += 1
101 offset = si - ref2
102
103 if offset <= 0 || offset >= winSize ||
104 uint32(match>>8) != binary.LittleEndian.Uint32(src[ref2:]) {
105 // No match. Check the third match at si+2
106 si += 1
107 offset = si - ref
108 hashTable[h] = si
109
110 if offset <= 0 || offset >= winSize ||
111 uint32(match>>16) != binary.LittleEndian.Uint32(src[ref:]) {
112 // Skip one extra byte (at si+3) before we check 3 matches again.
113 si += 2 + (si-anchor)>>adaptSkipLog
114 continue
115 }
116 }
117 }
118
119 // Match found.
120 lLen := si - anchor // Literal length.
121 // We already matched 4 bytes.
122 mLen := 4
123
124 // Extend backwards if we can, reducing literals.
125 tOff := si - offset - 1
126 for lLen > 0 && tOff >= 0 && src[si-1] == src[tOff] {
127 si--
128 tOff--
129 lLen--
130 mLen++
131 }
132
133 // Add the match length, so we continue search at the end.
134 // Use mLen to store the offset base.
135 si, mLen = si+mLen, si+minMatch
136
137 // Find the longest match by looking by batches of 8 bytes.
khenaidoo7d3c5582021-08-11 18:09:44 -0400138 for si+8 < sn {
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000139 x := binary.LittleEndian.Uint64(src[si:]) ^ binary.LittleEndian.Uint64(src[si-offset:])
140 if x == 0 {
141 si += 8
142 } else {
143 // Stop is first non-zero byte.
144 si += bits.TrailingZeros64(x) >> 3
145 break
146 }
147 }
148
149 mLen = si - mLen
150 if mLen < 0xF {
151 dst[di] = byte(mLen)
152 } else {
153 dst[di] = 0xF
154 }
155
156 // Encode literals length.
157 if lLen < 0xF {
158 dst[di] |= byte(lLen << 4)
159 } else {
160 dst[di] |= 0xF0
161 di++
162 l := lLen - 0xF
163 for ; l >= 0xFF; l -= 0xFF {
164 dst[di] = 0xFF
165 di++
166 }
167 dst[di] = byte(l)
168 }
169 di++
170
171 // Literals.
172 copy(dst[di:di+lLen], src[anchor:anchor+lLen])
173 di += lLen + 2
174 anchor = si
175
176 // Encode offset.
177 _ = dst[di] // Bound check elimination.
178 dst[di-2], dst[di-1] = byte(offset), byte(offset>>8)
179
180 // Encode match length part 2.
181 if mLen >= 0xF {
182 for mLen -= 0xF; mLen >= 0xFF; mLen -= 0xFF {
183 dst[di] = 0xFF
184 di++
185 }
186 dst[di] = byte(mLen)
187 di++
188 }
189 // Check if we can load next values.
190 if si >= sn {
191 break
192 }
193 // Hash match end-2
194 h = blockHash(binary.LittleEndian.Uint64(src[si-2:]))
195 hashTable[h] = si - 2
196 }
197
khenaidoo7d3c5582021-08-11 18:09:44 -0400198lastLiterals:
199 if isNotCompressible && anchor == 0 {
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000200 // Incompressible.
201 return 0, nil
202 }
203
204 // Last literals.
205 lLen := len(src) - anchor
206 if lLen < 0xF {
207 dst[di] = byte(lLen << 4)
208 } else {
209 dst[di] = 0xF0
210 di++
211 for lLen -= 0xF; lLen >= 0xFF; lLen -= 0xFF {
212 dst[di] = 0xFF
213 di++
214 }
215 dst[di] = byte(lLen)
216 }
217 di++
218
219 // Write the last literals.
khenaidoo7d3c5582021-08-11 18:09:44 -0400220 if isNotCompressible && di >= anchor {
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000221 // Incompressible.
222 return 0, nil
223 }
224 di += copy(dst[di:di+len(src)-anchor], src[anchor:])
225 return di, nil
226}
227
khenaidoo7d3c5582021-08-11 18:09:44 -0400228// Pool of hash tables for CompressBlock.
229var htPool = sync.Pool{
230 New: func() interface{} {
231 return new([htSize]int)
232 },
233}
234
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000235// blockHash hashes 4 bytes into a value < winSize.
236func blockHashHC(x uint32) uint32 {
237 const hasher uint32 = 2654435761 // Knuth multiplicative hash.
238 return x * hasher >> (32 - winSizeLog)
239}
240
241// CompressBlockHC compresses the source buffer src into the destination dst
242// with max search depth (use 0 or negative value for no max).
243//
244// CompressBlockHC compression ratio is better than CompressBlock but it is also slower.
245//
khenaidoo7d3c5582021-08-11 18:09:44 -0400246// The size of the compressed data is returned.
247//
248// If the destination buffer size is lower than CompressBlockBound and
249// the compressed size is 0 and no error, then the data is incompressible.
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000250//
251// An error is returned if the destination buffer is too small.
khenaidoo7d3c5582021-08-11 18:09:44 -0400252func CompressBlockHC(src, dst []byte, depth int) (_ int, err error) {
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000253 defer recoverBlock(&err)
254
khenaidoo7d3c5582021-08-11 18:09:44 -0400255 // Return 0, nil only if the destination buffer size is < CompressBlockBound.
256 isNotCompressible := len(dst) < CompressBlockBound(len(src))
257
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000258 // adaptSkipLog sets how quickly the compressor begins skipping blocks when data is incompressible.
khenaidoo7d3c5582021-08-11 18:09:44 -0400259 // This significantly speeds up incompressible data and usually has very small impact on compression.
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000260 // bytes to skip = 1 + (bytes since last match >> adaptSkipLog)
261 const adaptSkipLog = 7
262
khenaidoo7d3c5582021-08-11 18:09:44 -0400263 var si, di, anchor int
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000264
265 // hashTable: stores the last position found for a given hash
266 // chainTable: stores previous positions for a given hash
267 var hashTable, chainTable [winSize]int
268
269 if depth <= 0 {
270 depth = winSize
271 }
272
khenaidoo7d3c5582021-08-11 18:09:44 -0400273 sn := len(src) - mfLimit
274 if sn <= 0 {
275 goto lastLiterals
276 }
277
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000278 for si < sn {
279 // Hash the next 4 bytes (sequence).
280 match := binary.LittleEndian.Uint32(src[si:])
281 h := blockHashHC(match)
282
283 // Follow the chain until out of window and give the longest match.
284 mLen := 0
285 offset := 0
286 for next, try := hashTable[h], depth; try > 0 && next > 0 && si-next < winSize; next = chainTable[next&winMask] {
287 // The first (mLen==0) or next byte (mLen>=minMatch) at current match length
288 // must match to improve on the match length.
289 if src[next+mLen] != src[si+mLen] {
290 continue
291 }
292 ml := 0
293 // Compare the current position with a previous with the same hash.
294 for ml < sn-si {
295 x := binary.LittleEndian.Uint64(src[next+ml:]) ^ binary.LittleEndian.Uint64(src[si+ml:])
296 if x == 0 {
297 ml += 8
298 } else {
299 // Stop is first non-zero byte.
300 ml += bits.TrailingZeros64(x) >> 3
301 break
302 }
303 }
304 if ml < minMatch || ml <= mLen {
305 // Match too small (<minMath) or smaller than the current match.
306 continue
307 }
308 // Found a longer match, keep its position and length.
309 mLen = ml
310 offset = si - next
311 // Try another previous position with the same hash.
312 try--
313 }
314 chainTable[si&winMask] = hashTable[h]
315 hashTable[h] = si
316
317 // No match found.
318 if mLen == 0 {
319 si += 1 + (si-anchor)>>adaptSkipLog
320 continue
321 }
322
323 // Match found.
324 // Update hash/chain tables with overlapping bytes:
325 // si already hashed, add everything from si+1 up to the match length.
326 winStart := si + 1
327 if ws := si + mLen - winSize; ws > winStart {
328 winStart = ws
329 }
330 for si, ml := winStart, si+mLen; si < ml; {
331 match >>= 8
332 match |= uint32(src[si+3]) << 24
333 h := blockHashHC(match)
334 chainTable[si&winMask] = hashTable[h]
335 hashTable[h] = si
336 si++
337 }
338
339 lLen := si - anchor
340 si += mLen
341 mLen -= minMatch // Match length does not include minMatch.
342
343 if mLen < 0xF {
344 dst[di] = byte(mLen)
345 } else {
346 dst[di] = 0xF
347 }
348
349 // Encode literals length.
350 if lLen < 0xF {
351 dst[di] |= byte(lLen << 4)
352 } else {
353 dst[di] |= 0xF0
354 di++
355 l := lLen - 0xF
356 for ; l >= 0xFF; l -= 0xFF {
357 dst[di] = 0xFF
358 di++
359 }
360 dst[di] = byte(l)
361 }
362 di++
363
364 // Literals.
365 copy(dst[di:di+lLen], src[anchor:anchor+lLen])
366 di += lLen
367 anchor = si
368
369 // Encode offset.
370 di += 2
371 dst[di-2], dst[di-1] = byte(offset), byte(offset>>8)
372
373 // Encode match length part 2.
374 if mLen >= 0xF {
375 for mLen -= 0xF; mLen >= 0xFF; mLen -= 0xFF {
376 dst[di] = 0xFF
377 di++
378 }
379 dst[di] = byte(mLen)
380 di++
381 }
382 }
383
khenaidoo7d3c5582021-08-11 18:09:44 -0400384 if isNotCompressible && anchor == 0 {
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000385 // Incompressible.
386 return 0, nil
387 }
388
389 // Last literals.
khenaidoo7d3c5582021-08-11 18:09:44 -0400390lastLiterals:
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000391 lLen := len(src) - anchor
392 if lLen < 0xF {
393 dst[di] = byte(lLen << 4)
394 } else {
395 dst[di] = 0xF0
396 di++
397 lLen -= 0xF
398 for ; lLen >= 0xFF; lLen -= 0xFF {
399 dst[di] = 0xFF
400 di++
401 }
402 dst[di] = byte(lLen)
403 }
404 di++
405
406 // Write the last literals.
khenaidoo7d3c5582021-08-11 18:09:44 -0400407 if isNotCompressible && di >= anchor {
Holger Hildebrandtfa074992020-03-27 15:42:06 +0000408 // Incompressible.
409 return 0, nil
410 }
411 di += copy(dst[di:di+len(src)-anchor], src[anchor:])
412 return di, nil
413}