File: block.go

package info (click to toggle)
golang-github-pierrec-lz4 0.0~git20170519.0.5a3d224-2
  • links: PTS, VCS
  • area: main
  • in suites: buster, sid
  • size: 14,152 kB
  • ctags: 95
  • sloc: makefile: 7
file content (445 lines) | stat: -rw-r--r-- 10,997 bytes parent folder | download
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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
package lz4

import (
	"encoding/binary"
	"errors"
)

// block represents a frame data block.
// Used when compressing or decompressing frame blocks concurrently.
type block struct {
	compressed bool
	zdata      []byte // compressed data
	data       []byte // decompressed data
	offset     int    // offset within the data as with block dependency the 64Kb window is prepended to it
	checksum   uint32 // compressed data checksum
	err        error  // error while [de]compressing
}

var (
	// ErrInvalidSource is returned by UncompressBlock when a compressed block is corrupted.
	ErrInvalidSource = errors.New("lz4: invalid source")
	// ErrShortBuffer is returned by UncompressBlock, CompressBlock or CompressBlockHC when
	// the supplied buffer for [de]compression is too small.
	ErrShortBuffer = errors.New("lz4: short buffer")
)

// CompressBlockBound returns the maximum size of a given buffer of size n, when not compressible.
func CompressBlockBound(n int) int {
	return n + n/255 + 16
}

// UncompressBlock decompresses the source buffer into the destination one,
// starting at the di index and returning the decompressed size.
//
// The destination buffer must be sized appropriately.
//
// An error is returned if the source data is invalid or the destination buffer is too small.
func UncompressBlock(src, dst []byte, di int) (int, error) {
	si, sn, di0 := 0, len(src), di
	if sn == 0 {
		return 0, nil
	}

	for {
		// literals and match lengths (token)
		lLen := int(src[si] >> 4)
		mLen := int(src[si] & 0xF)
		if si++; si == sn {
			return di, ErrInvalidSource
		}

		// literals
		if lLen > 0 {
			if lLen == 0xF {
				for src[si] == 0xFF {
					lLen += 0xFF
					if si++; si == sn {
						return di - di0, ErrInvalidSource
					}
				}
				lLen += int(src[si])
				if si++; si == sn {
					return di - di0, ErrInvalidSource
				}
			}
			if len(dst)-di < lLen || si+lLen > sn {
				return di - di0, ErrShortBuffer
			}
			di += copy(dst[di:], src[si:si+lLen])

			if si += lLen; si >= sn {
				return di - di0, nil
			}
		}

		if si += 2; si >= sn {
			return di, ErrInvalidSource
		}
		offset := int(src[si-2]) | int(src[si-1])<<8
		if di-offset < 0 || offset == 0 {
			return di - di0, ErrInvalidSource
		}

		// match
		if mLen == 0xF {
			for src[si] == 0xFF {
				mLen += 0xFF
				if si++; si == sn {
					return di - di0, ErrInvalidSource
				}
			}
			mLen += int(src[si])
			if si++; si == sn {
				return di - di0, ErrInvalidSource
			}
		}
		// minimum match length is 4
		mLen += 4
		if len(dst)-di <= mLen {
			return di - di0, ErrShortBuffer
		}

		// copy the match (NB. match is at least 4 bytes long)
		// NB. past di, copy() would write old bytes instead of
		// the ones we just copied, so split the work into the largest chunk.
		for ; mLen >= offset; mLen -= offset {
			di += copy(dst[di:], dst[di-offset:di])
		}
		di += copy(dst[di:], dst[di-offset:di-offset+mLen])
	}
}

// CompressBlock compresses the source buffer starting at soffet into the destination one.
// This is the fast version of LZ4 compression and also the default one.
//
// The size of the compressed data is returned. If it is 0 and no error, then the data is incompressible.
//
// An error is returned if the destination buffer is too small.
func CompressBlock(src, dst []byte, soffset int) (int, error) {
	sn, dn := len(src)-mfLimit, len(dst)
	if sn <= 0 || dn == 0 || soffset >= sn {
		return 0, nil
	}
	var si, di int

	// fast scan strategy:
	// we only need a hash table to store the last sequences (4 bytes)
	var hashTable [1 << hashLog]int
	var hashShift = uint((minMatch * 8) - hashLog)

	// Initialise the hash table with the first 64Kb of the input buffer
	// (used when compressing dependent blocks)
	for si < soffset {
		h := binary.LittleEndian.Uint32(src[si:]) * hasher >> hashShift
		si++
		hashTable[h] = si
	}

	anchor := si
	fma := 1 << skipStrength
	for si < sn-minMatch {
		// hash the next 4 bytes (sequence)...
		h := binary.LittleEndian.Uint32(src[si:]) * hasher >> hashShift
		// -1 to separate existing entries from new ones
		ref := hashTable[h] - 1
		// ...and store the position of the hash in the hash table (+1 to compensate the -1 upon saving)
		hashTable[h] = si + 1
		// no need to check the last 3 bytes in the first literal 4 bytes as
		// this guarantees that the next match, if any, is compressed with
		// a lower size, since to have some compression we must have:
		// ll+ml-overlap > 1 + (ll-15)/255 + (ml-4-15)/255 + 2 (uncompressed size>compressed size)
		// => ll+ml>3+2*overlap => ll+ml>= 4+2*overlap
		// and by definition we do have:
		// ll >= 1, ml >= 4
		// => ll+ml >= 5
		// => so overlap must be 0

		// the sequence is new, out of bound (64kb) or not valid: try next sequence
		if ref < 0 || fma&(1<<skipStrength-1) < 4 ||
			(si-ref)>>winSizeLog > 0 ||
			src[ref] != src[si] ||
			src[ref+1] != src[si+1] ||
			src[ref+2] != src[si+2] ||
			src[ref+3] != src[si+3] {
			// variable step: improves performance on non-compressible data
			si += fma >> skipStrength
			fma++
			continue
		}
		// match found
		fma = 1 << skipStrength
		lLen := si - anchor
		offset := si - ref

		// encode match length part 1
		si += minMatch
		mLen := si // match length has minMatch already
		for si <= sn && src[si] == src[si-offset] {
			si++
		}
		mLen = si - mLen
		if mLen < 0xF {
			dst[di] = byte(mLen)
		} else {
			dst[di] = 0xF
		}

		// encode literals length
		if lLen < 0xF {
			dst[di] |= byte(lLen << 4)
		} else {
			dst[di] |= 0xF0
			if di++; di == dn {
				return di, ErrShortBuffer
			}
			l := lLen - 0xF
			for ; l >= 0xFF; l -= 0xFF {
				dst[di] = 0xFF
				if di++; di == dn {
					return di, ErrShortBuffer
				}
			}
			dst[di] = byte(l)
		}
		if di++; di == dn {
			return di, ErrShortBuffer
		}

		// literals
		if di+lLen >= dn {
			return di, ErrShortBuffer
		}
		di += copy(dst[di:], src[anchor:anchor+lLen])
		anchor = si

		// encode offset
		if di += 2; di >= dn {
			return di, ErrShortBuffer
		}
		dst[di-2], dst[di-1] = byte(offset), byte(offset>>8)

		// encode match length part 2
		if mLen >= 0xF {
			for mLen -= 0xF; mLen >= 0xFF; mLen -= 0xFF {
				dst[di] = 0xFF
				if di++; di == dn {
					return di, ErrShortBuffer
				}
			}
			dst[di] = byte(mLen)
			if di++; di == dn {
				return di, ErrShortBuffer
			}
		}
	}

	if anchor == 0 {
		// incompressible
		return 0, nil
	}

	// last literals
	lLen := len(src) - anchor
	if lLen < 0xF {
		dst[di] = byte(lLen << 4)
	} else {
		dst[di] = 0xF0
		if di++; di == dn {
			return di, ErrShortBuffer
		}
		lLen -= 0xF
		for ; lLen >= 0xFF; lLen -= 0xFF {
			dst[di] = 0xFF
			if di++; di == dn {
				return di, ErrShortBuffer
			}
		}
		dst[di] = byte(lLen)
	}
	if di++; di == dn {
		return di, ErrShortBuffer
	}

	// write literals
	src = src[anchor:]
	switch n := di + len(src); {
	case n > dn:
		return di, ErrShortBuffer
	case n >= sn:
		// incompressible
		return 0, nil
	}
	di += copy(dst[di:], src)
	return di, nil
}

// CompressBlockHC compresses the source buffer starting at soffet into the destination one.
// CompressBlockHC compression ratio is better than CompressBlock but it is also slower.
//
// The size of the compressed data is returned. If it is 0 and no error, then the data is not compressible.
//
// An error is returned if the destination buffer is too small.
func CompressBlockHC(src, dst []byte, soffset int) (int, error) {
	sn, dn := len(src)-mfLimit, len(dst)
	if sn <= 0 || dn == 0 || soffset >= sn {
		return 0, nil
	}
	var si, di int

	// Hash Chain strategy:
	// we need a hash table and a chain table
	// the chain table cannot contain more entries than the window size (64Kb entries)
	var hashTable [1 << hashLog]int
	var chainTable [winSize]int
	var hashShift = uint((minMatch * 8) - hashLog)

	// Initialise the hash table with the first 64Kb of the input buffer
	// (used when compressing dependent blocks)
	for si < soffset {
		h := binary.LittleEndian.Uint32(src[si:]) * hasher >> hashShift
		chainTable[si&winMask] = hashTable[h]
		si++
		hashTable[h] = si
	}

	anchor := si
	for si < sn-minMatch {
		// hash the next 4 bytes (sequence)...
		h := binary.LittleEndian.Uint32(src[si:]) * hasher >> hashShift

		// follow the chain until out of window and give the longest match
		mLen := 0
		offset := 0
		for next := hashTable[h] - 1; next > 0 && next > si-winSize; next = chainTable[next&winMask] - 1 {
			// the first (mLen==0) or next byte (mLen>=minMatch) at current match length must match to improve on the match length
			if src[next+mLen] == src[si+mLen] {
				for ml := 0; ; ml++ {
					if src[next+ml] != src[si+ml] || si+ml > sn {
						// found a longer match, keep its position and length
						if mLen < ml && ml >= minMatch {
							mLen = ml
							offset = si - next
						}
						break
					}
				}
			}
		}
		chainTable[si&winMask] = hashTable[h]
		hashTable[h] = si + 1

		// no match found
		if mLen == 0 {
			si++
			continue
		}

		// match found
		// update hash/chain tables with overlaping bytes:
		// si already hashed, add everything from si+1 up to the match length
		for si, ml := si+1, si+mLen; si < ml; {
			h := binary.LittleEndian.Uint32(src[si:]) * hasher >> hashShift
			chainTable[si&winMask] = hashTable[h]
			si++
			hashTable[h] = si
		}

		lLen := si - anchor
		si += mLen
		mLen -= minMatch // match length does not include minMatch

		if mLen < 0xF {
			dst[di] = byte(mLen)
		} else {
			dst[di] = 0xF
		}

		// encode literals length
		if lLen < 0xF {
			dst[di] |= byte(lLen << 4)
		} else {
			dst[di] |= 0xF0
			if di++; di == dn {
				return di, ErrShortBuffer
			}
			l := lLen - 0xF
			for ; l >= 0xFF; l -= 0xFF {
				dst[di] = 0xFF
				if di++; di == dn {
					return di, ErrShortBuffer
				}
			}
			dst[di] = byte(l)
		}
		if di++; di == dn {
			return di, ErrShortBuffer
		}

		// literals
		if di+lLen >= dn {
			return di, ErrShortBuffer
		}
		di += copy(dst[di:], src[anchor:anchor+lLen])
		anchor = si

		// encode offset
		if di += 2; di >= dn {
			return di, ErrShortBuffer
		}
		dst[di-2], dst[di-1] = byte(offset), byte(offset>>8)

		// encode match length part 2
		if mLen >= 0xF {
			for mLen -= 0xF; mLen >= 0xFF; mLen -= 0xFF {
				dst[di] = 0xFF
				if di++; di == dn {
					return di, ErrShortBuffer
				}
			}
			dst[di] = byte(mLen)
			if di++; di == dn {
				return di, ErrShortBuffer
			}
		}
	}

	if anchor == 0 {
		// incompressible
		return 0, nil
	}

	// last literals
	lLen := len(src) - anchor
	if lLen < 0xF {
		dst[di] = byte(lLen << 4)
	} else {
		dst[di] = 0xF0
		if di++; di == dn {
			return di, ErrShortBuffer
		}
		lLen -= 0xF
		for ; lLen >= 0xFF; lLen -= 0xFF {
			dst[di] = 0xFF
			if di++; di == dn {
				return di, ErrShortBuffer
			}
		}
		dst[di] = byte(lLen)
	}
	if di++; di == dn {
		return di, ErrShortBuffer
	}

	// write literals
	src = src[anchor:]
	switch n := di + len(src); {
	case n > dn:
		return di, ErrShortBuffer
	case n >= sn:
		// incompressible
		return 0, nil
	}
	di += copy(dst[di:], src)
	return di, nil
}