cubefs

1
// Copyright 2019+ Klaus Post. All rights reserved.
2
// License information can be found in the LICENSE file.
3
// Based on work by Yann Collet, released under BSD License.
4

5
package zstd
6

7
import (
8
	"fmt"
9
)
10

11
const (
12
	tableBits        = 15                               // Bits used in the table
13
	tableSize        = 1 << tableBits                   // Size of the table
14
	tableShardCnt    = 1 << (tableBits - dictShardBits) // Number of shards in the table
15
	tableShardSize   = tableSize / tableShardCnt        // Size of an individual shard
16
	tableFastHashLen = 6
17
	tableMask        = tableSize - 1 // Mask for table indices. Redundant, but can eliminate bounds checks.
18
	maxMatchLength   = 131074
19
)
20

21
type tableEntry struct {
22
	val    uint32
23
	offset int32
24
}
25

26
type fastEncoder struct {
27
	fastBase
28
	table [tableSize]tableEntry
29
}
30

31
type fastEncoderDict struct {
32
	fastEncoder
33
	dictTable       []tableEntry
34
	tableShardDirty [tableShardCnt]bool
35
	allDirty        bool
36
}
37

38
// Encode mimmics functionality in zstd_fast.c
39
func (e *fastEncoder) Encode(blk *blockEnc, src []byte) {
40
	const (
41
		inputMargin            = 8
42
		minNonLiteralBlockSize = 1 + 1 + inputMargin
43
	)
44

45
	// Protect against e.cur wraparound.
46
	for e.cur >= bufferReset {
47
		if len(e.hist) == 0 {
48
			for i := range e.table[:] {
49
				e.table[i] = tableEntry{}
50
			}
51
			e.cur = e.maxMatchOff
52
			break
53
		}
54
		// Shift down everything in the table that isn't already too far away.
55
		minOff := e.cur + int32(len(e.hist)) - e.maxMatchOff
56
		for i := range e.table[:] {
57
			v := e.table[i].offset
58
			if v < minOff {
59
				v = 0
60
			} else {
61
				v = v - e.cur + e.maxMatchOff
62
			}
63
			e.table[i].offset = v
64
		}
65
		e.cur = e.maxMatchOff
66
		break
67
	}
68

69
	s := e.addBlock(src)
70
	blk.size = len(src)
71
	if len(src) < minNonLiteralBlockSize {
72
		blk.extraLits = len(src)
73
		blk.literals = blk.literals[:len(src)]
74
		copy(blk.literals, src)
75
		return
76
	}
77

78
	// Override src
79
	src = e.hist
80
	sLimit := int32(len(src)) - inputMargin
81
	// stepSize is the number of bytes to skip on every main loop iteration.
82
	// It should be >= 2.
83
	const stepSize = 2
84

85
	// TEMPLATE
86
	const hashLog = tableBits
87
	// seems global, but would be nice to tweak.
88
	const kSearchStrength = 6
89

90
	// nextEmit is where in src the next emitLiteral should start from.
91
	nextEmit := s
92
	cv := load6432(src, s)
93

94
	// Relative offsets
95
	offset1 := int32(blk.recentOffsets[0])
96
	offset2 := int32(blk.recentOffsets[1])
97

98
	addLiterals := func(s *seq, until int32) {
99
		if until == nextEmit {
100
			return
101
		}
102
		blk.literals = append(blk.literals, src[nextEmit:until]...)
103
		s.litLen = uint32(until - nextEmit)
104
	}
105
	if debugEncoder {
106
		println("recent offsets:", blk.recentOffsets)
107
	}
108

109
encodeLoop:
110
	for {
111
		// t will contain the match offset when we find one.
112
		// When existing the search loop, we have already checked 4 bytes.
113
		var t int32
114

115
		// We will not use repeat offsets across blocks.
116
		// By not using them for the first 3 matches
117
		canRepeat := len(blk.sequences) > 2
118

119
		for {
120
			if debugAsserts && canRepeat && offset1 == 0 {
121
				panic("offset0 was 0")
122
			}
123

124
			nextHash := hashLen(cv, hashLog, tableFastHashLen)
125
			nextHash2 := hashLen(cv>>8, hashLog, tableFastHashLen)
126
			candidate := e.table[nextHash]
127
			candidate2 := e.table[nextHash2]
128
			repIndex := s - offset1 + 2
129

130
			e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
131
			e.table[nextHash2] = tableEntry{offset: s + e.cur + 1, val: uint32(cv >> 8)}
132

133
			if canRepeat && repIndex >= 0 && load3232(src, repIndex) == uint32(cv>>16) {
134
				// Consider history as well.
135
				var seq seq
136
				var length int32
137
				length = 4 + e.matchlen(s+6, repIndex+4, src)
138
				seq.matchLen = uint32(length - zstdMinMatch)
139

140
				// We might be able to match backwards.
141
				// Extend as long as we can.
142
				start := s + 2
143
				// We end the search early, so we don't risk 0 literals
144
				// and have to do special offset treatment.
145
				startLimit := nextEmit + 1
146

147
				sMin := s - e.maxMatchOff
148
				if sMin < 0 {
149
					sMin = 0
150
				}
151
				for repIndex > sMin && start > startLimit && src[repIndex-1] == src[start-1] && seq.matchLen < maxMatchLength-zstdMinMatch {
152
					repIndex--
153
					start--
154
					seq.matchLen++
155
				}
156
				addLiterals(&seq, start)
157

158
				// rep 0
159
				seq.offset = 1
160
				if debugSequences {
161
					println("repeat sequence", seq, "next s:", s)
162
				}
163
				blk.sequences = append(blk.sequences, seq)
164
				s += length + 2
165
				nextEmit = s
166
				if s >= sLimit {
167
					if debugEncoder {
168
						println("repeat ended", s, length)
169

170
					}
171
					break encodeLoop
172
				}
173
				cv = load6432(src, s)
174
				continue
175
			}
176
			coffset0 := s - (candidate.offset - e.cur)
177
			coffset1 := s - (candidate2.offset - e.cur) + 1
178
			if coffset0 < e.maxMatchOff && uint32(cv) == candidate.val {
179
				// found a regular match
180
				t = candidate.offset - e.cur
181
				if debugAsserts && s <= t {
182
					panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
183
				}
184
				if debugAsserts && s-t > e.maxMatchOff {
185
					panic("s - t >e.maxMatchOff")
186
				}
187
				break
188
			}
189

190
			if coffset1 < e.maxMatchOff && uint32(cv>>8) == candidate2.val {
191
				// found a regular match
192
				t = candidate2.offset - e.cur
193
				s++
194
				if debugAsserts && s <= t {
195
					panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
196
				}
197
				if debugAsserts && s-t > e.maxMatchOff {
198
					panic("s - t >e.maxMatchOff")
199
				}
200
				if debugAsserts && t < 0 {
201
					panic("t<0")
202
				}
203
				break
204
			}
205
			s += stepSize + ((s - nextEmit) >> (kSearchStrength - 1))
206
			if s >= sLimit {
207
				break encodeLoop
208
			}
209
			cv = load6432(src, s)
210
		}
211
		// A 4-byte match has been found. We'll later see if more than 4 bytes.
212
		offset2 = offset1
213
		offset1 = s - t
214

215
		if debugAsserts && s <= t {
216
			panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
217
		}
218

219
		if debugAsserts && canRepeat && int(offset1) > len(src) {
220
			panic("invalid offset")
221
		}
222

223
		// Extend the 4-byte match as long as possible.
224
		l := e.matchlen(s+4, t+4, src) + 4
225

226
		// Extend backwards
227
		tMin := s - e.maxMatchOff
228
		if tMin < 0 {
229
			tMin = 0
230
		}
231
		for t > tMin && s > nextEmit && src[t-1] == src[s-1] && l < maxMatchLength {
232
			s--
233
			t--
234
			l++
235
		}
236

237
		// Write our sequence.
238
		var seq seq
239
		seq.litLen = uint32(s - nextEmit)
240
		seq.matchLen = uint32(l - zstdMinMatch)
241
		if seq.litLen > 0 {
242
			blk.literals = append(blk.literals, src[nextEmit:s]...)
243
		}
244
		// Don't use repeat offsets
245
		seq.offset = uint32(s-t) + 3
246
		s += l
247
		if debugSequences {
248
			println("sequence", seq, "next s:", s)
249
		}
250
		blk.sequences = append(blk.sequences, seq)
251
		nextEmit = s
252
		if s >= sLimit {
253
			break encodeLoop
254
		}
255
		cv = load6432(src, s)
256

257
		// Check offset 2
258
		if o2 := s - offset2; canRepeat && load3232(src, o2) == uint32(cv) {
259
			// We have at least 4 byte match.
260
			// No need to check backwards. We come straight from a match
261
			l := 4 + e.matchlen(s+4, o2+4, src)
262

263
			// Store this, since we have it.
264
			nextHash := hashLen(cv, hashLog, tableFastHashLen)
265
			e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
266
			seq.matchLen = uint32(l) - zstdMinMatch
267
			seq.litLen = 0
268
			// Since litlen is always 0, this is offset 1.
269
			seq.offset = 1
270
			s += l
271
			nextEmit = s
272
			if debugSequences {
273
				println("sequence", seq, "next s:", s)
274
			}
275
			blk.sequences = append(blk.sequences, seq)
276

277
			// Swap offset 1 and 2.
278
			offset1, offset2 = offset2, offset1
279
			if s >= sLimit {
280
				break encodeLoop
281
			}
282
			// Prepare next loop.
283
			cv = load6432(src, s)
284
		}
285
	}
286

287
	if int(nextEmit) < len(src) {
288
		blk.literals = append(blk.literals, src[nextEmit:]...)
289
		blk.extraLits = len(src) - int(nextEmit)
290
	}
291
	blk.recentOffsets[0] = uint32(offset1)
292
	blk.recentOffsets[1] = uint32(offset2)
293
	if debugEncoder {
294
		println("returning, recent offsets:", blk.recentOffsets, "extra literals:", blk.extraLits)
295
	}
296
}
297

298
// EncodeNoHist will encode a block with no history and no following blocks.
299
// Most notable difference is that src will not be copied for history and
300
// we do not need to check for max match length.
301
func (e *fastEncoder) EncodeNoHist(blk *blockEnc, src []byte) {
302
	const (
303
		inputMargin            = 8
304
		minNonLiteralBlockSize = 1 + 1 + inputMargin
305
	)
306
	if debugEncoder {
307
		if len(src) > maxBlockSize {
308
			panic("src too big")
309
		}
310
	}
311

312
	// Protect against e.cur wraparound.
313
	if e.cur >= bufferReset {
314
		for i := range e.table[:] {
315
			e.table[i] = tableEntry{}
316
		}
317
		e.cur = e.maxMatchOff
318
	}
319

320
	s := int32(0)
321
	blk.size = len(src)
322
	if len(src) < minNonLiteralBlockSize {
323
		blk.extraLits = len(src)
324
		blk.literals = blk.literals[:len(src)]
325
		copy(blk.literals, src)
326
		return
327
	}
328

329
	sLimit := int32(len(src)) - inputMargin
330
	// stepSize is the number of bytes to skip on every main loop iteration.
331
	// It should be >= 2.
332
	const stepSize = 2
333

334
	// TEMPLATE
335
	const hashLog = tableBits
336
	// seems global, but would be nice to tweak.
337
	const kSearchStrength = 6
338

339
	// nextEmit is where in src the next emitLiteral should start from.
340
	nextEmit := s
341
	cv := load6432(src, s)
342

343
	// Relative offsets
344
	offset1 := int32(blk.recentOffsets[0])
345
	offset2 := int32(blk.recentOffsets[1])
346

347
	addLiterals := func(s *seq, until int32) {
348
		if until == nextEmit {
349
			return
350
		}
351
		blk.literals = append(blk.literals, src[nextEmit:until]...)
352
		s.litLen = uint32(until - nextEmit)
353
	}
354
	if debugEncoder {
355
		println("recent offsets:", blk.recentOffsets)
356
	}
357

358
encodeLoop:
359
	for {
360
		// t will contain the match offset when we find one.
361
		// When existing the search loop, we have already checked 4 bytes.
362
		var t int32
363

364
		// We will not use repeat offsets across blocks.
365
		// By not using them for the first 3 matches
366

367
		for {
368
			nextHash := hashLen(cv, hashLog, tableFastHashLen)
369
			nextHash2 := hashLen(cv>>8, hashLog, tableFastHashLen)
370
			candidate := e.table[nextHash]
371
			candidate2 := e.table[nextHash2]
372
			repIndex := s - offset1 + 2
373

374
			e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
375
			e.table[nextHash2] = tableEntry{offset: s + e.cur + 1, val: uint32(cv >> 8)}
376

377
			if len(blk.sequences) > 2 && load3232(src, repIndex) == uint32(cv>>16) {
378
				// Consider history as well.
379
				var seq seq
380
				length := 4 + e.matchlen(s+6, repIndex+4, src)
381

382
				seq.matchLen = uint32(length - zstdMinMatch)
383

384
				// We might be able to match backwards.
385
				// Extend as long as we can.
386
				start := s + 2
387
				// We end the search early, so we don't risk 0 literals
388
				// and have to do special offset treatment.
389
				startLimit := nextEmit + 1
390

391
				sMin := s - e.maxMatchOff
392
				if sMin < 0 {
393
					sMin = 0
394
				}
395
				for repIndex > sMin && start > startLimit && src[repIndex-1] == src[start-1] {
396
					repIndex--
397
					start--
398
					seq.matchLen++
399
				}
400
				addLiterals(&seq, start)
401

402
				// rep 0
403
				seq.offset = 1
404
				if debugSequences {
405
					println("repeat sequence", seq, "next s:", s)
406
				}
407
				blk.sequences = append(blk.sequences, seq)
408
				s += length + 2
409
				nextEmit = s
410
				if s >= sLimit {
411
					if debugEncoder {
412
						println("repeat ended", s, length)
413

414
					}
415
					break encodeLoop
416
				}
417
				cv = load6432(src, s)
418
				continue
419
			}
420
			coffset0 := s - (candidate.offset - e.cur)
421
			coffset1 := s - (candidate2.offset - e.cur) + 1
422
			if coffset0 < e.maxMatchOff && uint32(cv) == candidate.val {
423
				// found a regular match
424
				t = candidate.offset - e.cur
425
				if debugAsserts && s <= t {
426
					panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
427
				}
428
				if debugAsserts && s-t > e.maxMatchOff {
429
					panic("s - t >e.maxMatchOff")
430
				}
431
				if debugAsserts && t < 0 {
432
					panic(fmt.Sprintf("t (%d) < 0, candidate.offset: %d, e.cur: %d, coffset0: %d, e.maxMatchOff: %d", t, candidate.offset, e.cur, coffset0, e.maxMatchOff))
433
				}
434
				break
435
			}
436

437
			if coffset1 < e.maxMatchOff && uint32(cv>>8) == candidate2.val {
438
				// found a regular match
439
				t = candidate2.offset - e.cur
440
				s++
441
				if debugAsserts && s <= t {
442
					panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
443
				}
444
				if debugAsserts && s-t > e.maxMatchOff {
445
					panic("s - t >e.maxMatchOff")
446
				}
447
				if debugAsserts && t < 0 {
448
					panic("t<0")
449
				}
450
				break
451
			}
452
			s += stepSize + ((s - nextEmit) >> (kSearchStrength - 1))
453
			if s >= sLimit {
454
				break encodeLoop
455
			}
456
			cv = load6432(src, s)
457
		}
458
		// A 4-byte match has been found. We'll later see if more than 4 bytes.
459
		offset2 = offset1
460
		offset1 = s - t
461

462
		if debugAsserts && s <= t {
463
			panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
464
		}
465

466
		if debugAsserts && t < 0 {
467
			panic(fmt.Sprintf("t (%d) < 0 ", t))
468
		}
469
		// Extend the 4-byte match as long as possible.
470
		l := e.matchlen(s+4, t+4, src) + 4
471

472
		// Extend backwards
473
		tMin := s - e.maxMatchOff
474
		if tMin < 0 {
475
			tMin = 0
476
		}
477
		for t > tMin && s > nextEmit && src[t-1] == src[s-1] {
478
			s--
479
			t--
480
			l++
481
		}
482

483
		// Write our sequence.
484
		var seq seq
485
		seq.litLen = uint32(s - nextEmit)
486
		seq.matchLen = uint32(l - zstdMinMatch)
487
		if seq.litLen > 0 {
488
			blk.literals = append(blk.literals, src[nextEmit:s]...)
489
		}
490
		// Don't use repeat offsets
491
		seq.offset = uint32(s-t) + 3
492
		s += l
493
		if debugSequences {
494
			println("sequence", seq, "next s:", s)
495
		}
496
		blk.sequences = append(blk.sequences, seq)
497
		nextEmit = s
498
		if s >= sLimit {
499
			break encodeLoop
500
		}
501
		cv = load6432(src, s)
502

503
		// Check offset 2
504
		if o2 := s - offset2; len(blk.sequences) > 2 && load3232(src, o2) == uint32(cv) {
505
			// We have at least 4 byte match.
506
			// No need to check backwards. We come straight from a match
507
			l := 4 + e.matchlen(s+4, o2+4, src)
508

509
			// Store this, since we have it.
510
			nextHash := hashLen(cv, hashLog, tableFastHashLen)
511
			e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
512
			seq.matchLen = uint32(l) - zstdMinMatch
513
			seq.litLen = 0
514
			// Since litlen is always 0, this is offset 1.
515
			seq.offset = 1
516
			s += l
517
			nextEmit = s
518
			if debugSequences {
519
				println("sequence", seq, "next s:", s)
520
			}
521
			blk.sequences = append(blk.sequences, seq)
522

523
			// Swap offset 1 and 2.
524
			offset1, offset2 = offset2, offset1
525
			if s >= sLimit {
526
				break encodeLoop
527
			}
528
			// Prepare next loop.
529
			cv = load6432(src, s)
530
		}
531
	}
532

533
	if int(nextEmit) < len(src) {
534
		blk.literals = append(blk.literals, src[nextEmit:]...)
535
		blk.extraLits = len(src) - int(nextEmit)
536
	}
537
	if debugEncoder {
538
		println("returning, recent offsets:", blk.recentOffsets, "extra literals:", blk.extraLits)
539
	}
540
	// We do not store history, so we must offset e.cur to avoid false matches for next user.
541
	if e.cur < bufferReset {
542
		e.cur += int32(len(src))
543
	}
544
}
545

546
// Encode will encode the content, with a dictionary if initialized for it.
547
func (e *fastEncoderDict) Encode(blk *blockEnc, src []byte) {
548
	const (
549
		inputMargin            = 8
550
		minNonLiteralBlockSize = 1 + 1 + inputMargin
551
	)
552
	if e.allDirty || len(src) > 32<<10 {
553
		e.fastEncoder.Encode(blk, src)
554
		e.allDirty = true
555
		return
556
	}
557
	// Protect against e.cur wraparound.
558
	for e.cur >= bufferReset {
559
		if len(e.hist) == 0 {
560
			for i := range e.table[:] {
561
				e.table[i] = tableEntry{}
562
			}
563
			e.cur = e.maxMatchOff
564
			break
565
		}
566
		// Shift down everything in the table that isn't already too far away.
567
		minOff := e.cur + int32(len(e.hist)) - e.maxMatchOff
568
		for i := range e.table[:] {
569
			v := e.table[i].offset
570
			if v < minOff {
571
				v = 0
572
			} else {
573
				v = v - e.cur + e.maxMatchOff
574
			}
575
			e.table[i].offset = v
576
		}
577
		e.cur = e.maxMatchOff
578
		break
579
	}
580

581
	s := e.addBlock(src)
582
	blk.size = len(src)
583
	if len(src) < minNonLiteralBlockSize {
584
		blk.extraLits = len(src)
585
		blk.literals = blk.literals[:len(src)]
586
		copy(blk.literals, src)
587
		return
588
	}
589

590
	// Override src
591
	src = e.hist
592
	sLimit := int32(len(src)) - inputMargin
593
	// stepSize is the number of bytes to skip on every main loop iteration.
594
	// It should be >= 2.
595
	const stepSize = 2
596

597
	// TEMPLATE
598
	const hashLog = tableBits
599
	// seems global, but would be nice to tweak.
600
	const kSearchStrength = 7
601

602
	// nextEmit is where in src the next emitLiteral should start from.
603
	nextEmit := s
604
	cv := load6432(src, s)
605

606
	// Relative offsets
607
	offset1 := int32(blk.recentOffsets[0])
608
	offset2 := int32(blk.recentOffsets[1])
609

610
	addLiterals := func(s *seq, until int32) {
611
		if until == nextEmit {
612
			return
613
		}
614
		blk.literals = append(blk.literals, src[nextEmit:until]...)
615
		s.litLen = uint32(until - nextEmit)
616
	}
617
	if debugEncoder {
618
		println("recent offsets:", blk.recentOffsets)
619
	}
620

621
encodeLoop:
622
	for {
623
		// t will contain the match offset when we find one.
624
		// When existing the search loop, we have already checked 4 bytes.
625
		var t int32
626

627
		// We will not use repeat offsets across blocks.
628
		// By not using them for the first 3 matches
629
		canRepeat := len(blk.sequences) > 2
630

631
		for {
632
			if debugAsserts && canRepeat && offset1 == 0 {
633
				panic("offset0 was 0")
634
			}
635

636
			nextHash := hashLen(cv, hashLog, tableFastHashLen)
637
			nextHash2 := hashLen(cv>>8, hashLog, tableFastHashLen)
638
			candidate := e.table[nextHash]
639
			candidate2 := e.table[nextHash2]
640
			repIndex := s - offset1 + 2
641

642
			e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
643
			e.markShardDirty(nextHash)
644
			e.table[nextHash2] = tableEntry{offset: s + e.cur + 1, val: uint32(cv >> 8)}
645
			e.markShardDirty(nextHash2)
646

647
			if canRepeat && repIndex >= 0 && load3232(src, repIndex) == uint32(cv>>16) {
648
				// Consider history as well.
649
				var seq seq
650
				var length int32
651
				length = 4 + e.matchlen(s+6, repIndex+4, src)
652

653
				seq.matchLen = uint32(length - zstdMinMatch)
654

655
				// We might be able to match backwards.
656
				// Extend as long as we can.
657
				start := s + 2
658
				// We end the search early, so we don't risk 0 literals
659
				// and have to do special offset treatment.
660
				startLimit := nextEmit + 1
661

662
				sMin := s - e.maxMatchOff
663
				if sMin < 0 {
664
					sMin = 0
665
				}
666
				for repIndex > sMin && start > startLimit && src[repIndex-1] == src[start-1] && seq.matchLen < maxMatchLength-zstdMinMatch {
667
					repIndex--
668
					start--
669
					seq.matchLen++
670
				}
671
				addLiterals(&seq, start)
672

673
				// rep 0
674
				seq.offset = 1
675
				if debugSequences {
676
					println("repeat sequence", seq, "next s:", s)
677
				}
678
				blk.sequences = append(blk.sequences, seq)
679
				s += length + 2
680
				nextEmit = s
681
				if s >= sLimit {
682
					if debugEncoder {
683
						println("repeat ended", s, length)
684

685
					}
686
					break encodeLoop
687
				}
688
				cv = load6432(src, s)
689
				continue
690
			}
691
			coffset0 := s - (candidate.offset - e.cur)
692
			coffset1 := s - (candidate2.offset - e.cur) + 1
693
			if coffset0 < e.maxMatchOff && uint32(cv) == candidate.val {
694
				// found a regular match
695
				t = candidate.offset - e.cur
696
				if debugAsserts && s <= t {
697
					panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
698
				}
699
				if debugAsserts && s-t > e.maxMatchOff {
700
					panic("s - t >e.maxMatchOff")
701
				}
702
				break
703
			}
704

705
			if coffset1 < e.maxMatchOff && uint32(cv>>8) == candidate2.val {
706
				// found a regular match
707
				t = candidate2.offset - e.cur
708
				s++
709
				if debugAsserts && s <= t {
710
					panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
711
				}
712
				if debugAsserts && s-t > e.maxMatchOff {
713
					panic("s - t >e.maxMatchOff")
714
				}
715
				if debugAsserts && t < 0 {
716
					panic("t<0")
717
				}
718
				break
719
			}
720
			s += stepSize + ((s - nextEmit) >> (kSearchStrength - 1))
721
			if s >= sLimit {
722
				break encodeLoop
723
			}
724
			cv = load6432(src, s)
725
		}
726
		// A 4-byte match has been found. We'll later see if more than 4 bytes.
727
		offset2 = offset1
728
		offset1 = s - t
729

730
		if debugAsserts && s <= t {
731
			panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
732
		}
733

734
		if debugAsserts && canRepeat && int(offset1) > len(src) {
735
			panic("invalid offset")
736
		}
737

738
		// Extend the 4-byte match as long as possible.
739
		l := e.matchlen(s+4, t+4, src) + 4
740

741
		// Extend backwards
742
		tMin := s - e.maxMatchOff
743
		if tMin < 0 {
744
			tMin = 0
745
		}
746
		for t > tMin && s > nextEmit && src[t-1] == src[s-1] && l < maxMatchLength {
747
			s--
748
			t--
749
			l++
750
		}
751

752
		// Write our sequence.
753
		var seq seq
754
		seq.litLen = uint32(s - nextEmit)
755
		seq.matchLen = uint32(l - zstdMinMatch)
756
		if seq.litLen > 0 {
757
			blk.literals = append(blk.literals, src[nextEmit:s]...)
758
		}
759
		// Don't use repeat offsets
760
		seq.offset = uint32(s-t) + 3
761
		s += l
762
		if debugSequences {
763
			println("sequence", seq, "next s:", s)
764
		}
765
		blk.sequences = append(blk.sequences, seq)
766
		nextEmit = s
767
		if s >= sLimit {
768
			break encodeLoop
769
		}
770
		cv = load6432(src, s)
771

772
		// Check offset 2
773
		if o2 := s - offset2; canRepeat && load3232(src, o2) == uint32(cv) {
774
			// We have at least 4 byte match.
775
			// No need to check backwards. We come straight from a match
776
			l := 4 + e.matchlen(s+4, o2+4, src)
777

778
			// Store this, since we have it.
779
			nextHash := hashLen(cv, hashLog, tableFastHashLen)
780
			e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
781
			e.markShardDirty(nextHash)
782
			seq.matchLen = uint32(l) - zstdMinMatch
783
			seq.litLen = 0
784
			// Since litlen is always 0, this is offset 1.
785
			seq.offset = 1
786
			s += l
787
			nextEmit = s
788
			if debugSequences {
789
				println("sequence", seq, "next s:", s)
790
			}
791
			blk.sequences = append(blk.sequences, seq)
792

793
			// Swap offset 1 and 2.
794
			offset1, offset2 = offset2, offset1
795
			if s >= sLimit {
796
				break encodeLoop
797
			}
798
			// Prepare next loop.
799
			cv = load6432(src, s)
800
		}
801
	}
802

803
	if int(nextEmit) < len(src) {
804
		blk.literals = append(blk.literals, src[nextEmit:]...)
805
		blk.extraLits = len(src) - int(nextEmit)
806
	}
807
	blk.recentOffsets[0] = uint32(offset1)
808
	blk.recentOffsets[1] = uint32(offset2)
809
	if debugEncoder {
810
		println("returning, recent offsets:", blk.recentOffsets, "extra literals:", blk.extraLits)
811
	}
812
}
813

814
// ResetDict will reset and set a dictionary if not nil
815
func (e *fastEncoder) Reset(d *dict, singleBlock bool) {
816
	e.resetBase(d, singleBlock)
817
	if d != nil {
818
		panic("fastEncoder: Reset with dict")
819
	}
820
}
821

822
// ResetDict will reset and set a dictionary if not nil
823
func (e *fastEncoderDict) Reset(d *dict, singleBlock bool) {
824
	e.resetBase(d, singleBlock)
825
	if d == nil {
826
		return
827
	}
828

829
	// Init or copy dict table
830
	if len(e.dictTable) != len(e.table) || d.id != e.lastDictID {
831
		if len(e.dictTable) != len(e.table) {
832
			e.dictTable = make([]tableEntry, len(e.table))
833
		}
834
		if true {
835
			end := e.maxMatchOff + int32(len(d.content)) - 8
836
			for i := e.maxMatchOff; i < end; i += 3 {
837
				const hashLog = tableBits
838

839
				cv := load6432(d.content, i-e.maxMatchOff)
840
				nextHash := hashLen(cv, hashLog, tableFastHashLen)      // 0 -> 5
841
				nextHash1 := hashLen(cv>>8, hashLog, tableFastHashLen)  // 1 -> 6
842
				nextHash2 := hashLen(cv>>16, hashLog, tableFastHashLen) // 2 -> 7
843
				e.dictTable[nextHash] = tableEntry{
844
					val:    uint32(cv),
845
					offset: i,
846
				}
847
				e.dictTable[nextHash1] = tableEntry{
848
					val:    uint32(cv >> 8),
849
					offset: i + 1,
850
				}
851
				e.dictTable[nextHash2] = tableEntry{
852
					val:    uint32(cv >> 16),
853
					offset: i + 2,
854
				}
855
			}
856
		}
857
		e.lastDictID = d.id
858
		e.allDirty = true
859
	}
860

861
	e.cur = e.maxMatchOff
862
	dirtyShardCnt := 0
863
	if !e.allDirty {
864
		for i := range e.tableShardDirty {
865
			if e.tableShardDirty[i] {
866
				dirtyShardCnt++
867
			}
868
		}
869
	}
870

871
	const shardCnt = tableShardCnt
872
	const shardSize = tableShardSize
873
	if e.allDirty || dirtyShardCnt > shardCnt*4/6 {
874
		copy(e.table[:], e.dictTable)
875
		for i := range e.tableShardDirty {
876
			e.tableShardDirty[i] = false
877
		}
878
		e.allDirty = false
879
		return
880
	}
881
	for i := range e.tableShardDirty {
882
		if !e.tableShardDirty[i] {
883
			continue
884
		}
885

886
		copy(e.table[i*shardSize:(i+1)*shardSize], e.dictTable[i*shardSize:(i+1)*shardSize])
887
		e.tableShardDirty[i] = false
888
	}
889
	e.allDirty = false
890
}
891

892
func (e *fastEncoderDict) markAllShardsDirty() {
893
	e.allDirty = true
894
}
895

896
func (e *fastEncoderDict) markShardDirty(entryNum uint32) {
897
	e.tableShardDirty[entryNum/tableShardSize] = true
898
}
899