enc_fast.go raw
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 >= e.bufferReset-int32(len(e.hist)) {
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 length := 4 + e.matchlen(s+6, repIndex+4, src)
137 seq.matchLen = uint32(length - zstdMinMatch)
138
139 // We might be able to match backwards.
140 // Extend as long as we can.
141 start := s + 2
142 // We end the search early, so we don't risk 0 literals
143 // and have to do special offset treatment.
144 startLimit := nextEmit + 1
145
146 sMin := max(s-e.maxMatchOff, 0)
147 for repIndex > sMin && start > startLimit && src[repIndex-1] == src[start-1] && seq.matchLen < maxMatchLength-zstdMinMatch {
148 repIndex--
149 start--
150 seq.matchLen++
151 }
152 addLiterals(&seq, start)
153
154 // rep 0
155 seq.offset = 1
156 if debugSequences {
157 println("repeat sequence", seq, "next s:", s)
158 }
159 blk.sequences = append(blk.sequences, seq)
160 s += length + 2
161 nextEmit = s
162 if s >= sLimit {
163 if debugEncoder {
164 println("repeat ended", s, length)
165
166 }
167 break encodeLoop
168 }
169 cv = load6432(src, s)
170 continue
171 }
172 coffset0 := s - (candidate.offset - e.cur)
173 coffset1 := s - (candidate2.offset - e.cur) + 1
174 if coffset0 < e.maxMatchOff && uint32(cv) == candidate.val {
175 // found a regular match
176 t = candidate.offset - e.cur
177 if debugAsserts && s <= t {
178 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
179 }
180 if debugAsserts && s-t > e.maxMatchOff {
181 panic("s - t >e.maxMatchOff")
182 }
183 break
184 }
185
186 if coffset1 < e.maxMatchOff && uint32(cv>>8) == candidate2.val {
187 // found a regular match
188 t = candidate2.offset - e.cur
189 s++
190 if debugAsserts && s <= t {
191 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
192 }
193 if debugAsserts && s-t > e.maxMatchOff {
194 panic("s - t >e.maxMatchOff")
195 }
196 if debugAsserts && t < 0 {
197 panic("t<0")
198 }
199 break
200 }
201 s += stepSize + ((s - nextEmit) >> (kSearchStrength - 1))
202 if s >= sLimit {
203 break encodeLoop
204 }
205 cv = load6432(src, s)
206 }
207 // A 4-byte match has been found. We'll later see if more than 4 bytes.
208 offset2 = offset1
209 offset1 = s - t
210
211 if debugAsserts && s <= t {
212 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
213 }
214
215 if debugAsserts && canRepeat && int(offset1) > len(src) {
216 panic("invalid offset")
217 }
218
219 // Extend the 4-byte match as long as possible.
220 l := e.matchlen(s+4, t+4, src) + 4
221
222 // Extend backwards
223 tMin := max(s-e.maxMatchOff, 0)
224 for t > tMin && s > nextEmit && src[t-1] == src[s-1] && l < maxMatchLength {
225 s--
226 t--
227 l++
228 }
229
230 // Write our sequence.
231 var seq seq
232 seq.litLen = uint32(s - nextEmit)
233 seq.matchLen = uint32(l - zstdMinMatch)
234 if seq.litLen > 0 {
235 blk.literals = append(blk.literals, src[nextEmit:s]...)
236 }
237 // Don't use repeat offsets
238 seq.offset = uint32(s-t) + 3
239 s += l
240 if debugSequences {
241 println("sequence", seq, "next s:", s)
242 }
243 blk.sequences = append(blk.sequences, seq)
244 nextEmit = s
245 if s >= sLimit {
246 break encodeLoop
247 }
248 cv = load6432(src, s)
249
250 // Check offset 2
251 if o2 := s - offset2; canRepeat && load3232(src, o2) == uint32(cv) {
252 // We have at least 4 byte match.
253 // No need to check backwards. We come straight from a match
254 l := 4 + e.matchlen(s+4, o2+4, src)
255
256 // Store this, since we have it.
257 nextHash := hashLen(cv, hashLog, tableFastHashLen)
258 e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
259 seq.matchLen = uint32(l) - zstdMinMatch
260 seq.litLen = 0
261 // Since litlen is always 0, this is offset 1.
262 seq.offset = 1
263 s += l
264 nextEmit = s
265 if debugSequences {
266 println("sequence", seq, "next s:", s)
267 }
268 blk.sequences = append(blk.sequences, seq)
269
270 // Swap offset 1 and 2.
271 offset1, offset2 = offset2, offset1
272 if s >= sLimit {
273 break encodeLoop
274 }
275 // Prepare next loop.
276 cv = load6432(src, s)
277 }
278 }
279
280 if int(nextEmit) < len(src) {
281 blk.literals = append(blk.literals, src[nextEmit:]...)
282 blk.extraLits = len(src) - int(nextEmit)
283 }
284 blk.recentOffsets[0] = uint32(offset1)
285 blk.recentOffsets[1] = uint32(offset2)
286 if debugEncoder {
287 println("returning, recent offsets:", blk.recentOffsets, "extra literals:", blk.extraLits)
288 }
289 }
290
291 // EncodeNoHist will encode a block with no history and no following blocks.
292 // Most notable difference is that src will not be copied for history and
293 // we do not need to check for max match length.
294 func (e *fastEncoder) EncodeNoHist(blk *blockEnc, src []byte) {
295 const (
296 inputMargin = 8
297 minNonLiteralBlockSize = 1 + 1 + inputMargin
298 )
299 if debugEncoder {
300 if len(src) > maxCompressedBlockSize {
301 panic("src too big")
302 }
303 }
304
305 // Protect against e.cur wraparound.
306 if e.cur >= e.bufferReset {
307 for i := range e.table[:] {
308 e.table[i] = tableEntry{}
309 }
310 e.cur = e.maxMatchOff
311 }
312
313 s := int32(0)
314 blk.size = len(src)
315 if len(src) < minNonLiteralBlockSize {
316 blk.extraLits = len(src)
317 blk.literals = blk.literals[:len(src)]
318 copy(blk.literals, src)
319 return
320 }
321
322 sLimit := int32(len(src)) - inputMargin
323 // stepSize is the number of bytes to skip on every main loop iteration.
324 // It should be >= 2.
325 const stepSize = 2
326
327 // TEMPLATE
328 const hashLog = tableBits
329 // seems global, but would be nice to tweak.
330 const kSearchStrength = 6
331
332 // nextEmit is where in src the next emitLiteral should start from.
333 nextEmit := s
334 cv := load6432(src, s)
335
336 // Relative offsets
337 offset1 := int32(blk.recentOffsets[0])
338 offset2 := int32(blk.recentOffsets[1])
339
340 addLiterals := func(s *seq, until int32) {
341 if until == nextEmit {
342 return
343 }
344 blk.literals = append(blk.literals, src[nextEmit:until]...)
345 s.litLen = uint32(until - nextEmit)
346 }
347 if debugEncoder {
348 println("recent offsets:", blk.recentOffsets)
349 }
350
351 encodeLoop:
352 for {
353 // t will contain the match offset when we find one.
354 // When existing the search loop, we have already checked 4 bytes.
355 var t int32
356
357 // We will not use repeat offsets across blocks.
358 // By not using them for the first 3 matches
359
360 for {
361 nextHash := hashLen(cv, hashLog, tableFastHashLen)
362 nextHash2 := hashLen(cv>>8, hashLog, tableFastHashLen)
363 candidate := e.table[nextHash]
364 candidate2 := e.table[nextHash2]
365 repIndex := s - offset1 + 2
366
367 e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
368 e.table[nextHash2] = tableEntry{offset: s + e.cur + 1, val: uint32(cv >> 8)}
369
370 if len(blk.sequences) > 2 && load3232(src, repIndex) == uint32(cv>>16) {
371 // Consider history as well.
372 var seq seq
373 length := 4 + e.matchlen(s+6, repIndex+4, src)
374
375 seq.matchLen = uint32(length - zstdMinMatch)
376
377 // We might be able to match backwards.
378 // Extend as long as we can.
379 start := s + 2
380 // We end the search early, so we don't risk 0 literals
381 // and have to do special offset treatment.
382 startLimit := nextEmit + 1
383
384 sMin := max(s-e.maxMatchOff, 0)
385 for repIndex > sMin && start > startLimit && src[repIndex-1] == src[start-1] {
386 repIndex--
387 start--
388 seq.matchLen++
389 }
390 addLiterals(&seq, start)
391
392 // rep 0
393 seq.offset = 1
394 if debugSequences {
395 println("repeat sequence", seq, "next s:", s)
396 }
397 blk.sequences = append(blk.sequences, seq)
398 s += length + 2
399 nextEmit = s
400 if s >= sLimit {
401 if debugEncoder {
402 println("repeat ended", s, length)
403
404 }
405 break encodeLoop
406 }
407 cv = load6432(src, s)
408 continue
409 }
410 coffset0 := s - (candidate.offset - e.cur)
411 coffset1 := s - (candidate2.offset - e.cur) + 1
412 if coffset0 < e.maxMatchOff && uint32(cv) == candidate.val {
413 // found a regular match
414 t = candidate.offset - e.cur
415 if debugAsserts && s <= t {
416 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
417 }
418 if debugAsserts && s-t > e.maxMatchOff {
419 panic("s - t >e.maxMatchOff")
420 }
421 if debugAsserts && t < 0 {
422 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))
423 }
424 break
425 }
426
427 if coffset1 < e.maxMatchOff && uint32(cv>>8) == candidate2.val {
428 // found a regular match
429 t = candidate2.offset - e.cur
430 s++
431 if debugAsserts && s <= t {
432 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
433 }
434 if debugAsserts && s-t > e.maxMatchOff {
435 panic("s - t >e.maxMatchOff")
436 }
437 if debugAsserts && t < 0 {
438 panic("t<0")
439 }
440 break
441 }
442 s += stepSize + ((s - nextEmit) >> (kSearchStrength - 1))
443 if s >= sLimit {
444 break encodeLoop
445 }
446 cv = load6432(src, s)
447 }
448 // A 4-byte match has been found. We'll later see if more than 4 bytes.
449 offset2 = offset1
450 offset1 = s - t
451
452 if debugAsserts && s <= t {
453 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
454 }
455
456 if debugAsserts && t < 0 {
457 panic(fmt.Sprintf("t (%d) < 0 ", t))
458 }
459 // Extend the 4-byte match as long as possible.
460 l := e.matchlen(s+4, t+4, src) + 4
461
462 // Extend backwards
463 tMin := max(s-e.maxMatchOff, 0)
464 for t > tMin && s > nextEmit && src[t-1] == src[s-1] {
465 s--
466 t--
467 l++
468 }
469
470 // Write our sequence.
471 var seq seq
472 seq.litLen = uint32(s - nextEmit)
473 seq.matchLen = uint32(l - zstdMinMatch)
474 if seq.litLen > 0 {
475 blk.literals = append(blk.literals, src[nextEmit:s]...)
476 }
477 // Don't use repeat offsets
478 seq.offset = uint32(s-t) + 3
479 s += l
480 if debugSequences {
481 println("sequence", seq, "next s:", s)
482 }
483 blk.sequences = append(blk.sequences, seq)
484 nextEmit = s
485 if s >= sLimit {
486 break encodeLoop
487 }
488 cv = load6432(src, s)
489
490 // Check offset 2
491 if o2 := s - offset2; len(blk.sequences) > 2 && load3232(src, o2) == uint32(cv) {
492 // We have at least 4 byte match.
493 // No need to check backwards. We come straight from a match
494 l := 4 + e.matchlen(s+4, o2+4, src)
495
496 // Store this, since we have it.
497 nextHash := hashLen(cv, hashLog, tableFastHashLen)
498 e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
499 seq.matchLen = uint32(l) - zstdMinMatch
500 seq.litLen = 0
501 // Since litlen is always 0, this is offset 1.
502 seq.offset = 1
503 s += l
504 nextEmit = s
505 if debugSequences {
506 println("sequence", seq, "next s:", s)
507 }
508 blk.sequences = append(blk.sequences, seq)
509
510 // Swap offset 1 and 2.
511 offset1, offset2 = offset2, offset1
512 if s >= sLimit {
513 break encodeLoop
514 }
515 // Prepare next loop.
516 cv = load6432(src, s)
517 }
518 }
519
520 if int(nextEmit) < len(src) {
521 blk.literals = append(blk.literals, src[nextEmit:]...)
522 blk.extraLits = len(src) - int(nextEmit)
523 }
524 if debugEncoder {
525 println("returning, recent offsets:", blk.recentOffsets, "extra literals:", blk.extraLits)
526 }
527 // We do not store history, so we must offset e.cur to avoid false matches for next user.
528 if e.cur < e.bufferReset {
529 e.cur += int32(len(src))
530 }
531 }
532
533 // Encode will encode the content, with a dictionary if initialized for it.
534 func (e *fastEncoderDict) Encode(blk *blockEnc, src []byte) {
535 const (
536 inputMargin = 8
537 minNonLiteralBlockSize = 1 + 1 + inputMargin
538 )
539 if e.allDirty || len(src) > 32<<10 {
540 e.fastEncoder.Encode(blk, src)
541 e.allDirty = true
542 return
543 }
544 // Protect against e.cur wraparound.
545 for e.cur >= e.bufferReset-int32(len(e.hist)) {
546 if len(e.hist) == 0 {
547 e.table = [tableSize]tableEntry{}
548 e.cur = e.maxMatchOff
549 break
550 }
551 // Shift down everything in the table that isn't already too far away.
552 minOff := e.cur + int32(len(e.hist)) - e.maxMatchOff
553 for i := range e.table[:] {
554 v := e.table[i].offset
555 if v < minOff {
556 v = 0
557 } else {
558 v = v - e.cur + e.maxMatchOff
559 }
560 e.table[i].offset = v
561 }
562 e.cur = e.maxMatchOff
563 break
564 }
565
566 s := e.addBlock(src)
567 blk.size = len(src)
568 if len(src) < minNonLiteralBlockSize {
569 blk.extraLits = len(src)
570 blk.literals = blk.literals[:len(src)]
571 copy(blk.literals, src)
572 return
573 }
574
575 // Override src
576 src = e.hist
577 sLimit := int32(len(src)) - inputMargin
578 // stepSize is the number of bytes to skip on every main loop iteration.
579 // It should be >= 2.
580 const stepSize = 2
581
582 // TEMPLATE
583 const hashLog = tableBits
584 // seems global, but would be nice to tweak.
585 const kSearchStrength = 7
586
587 // nextEmit is where in src the next emitLiteral should start from.
588 nextEmit := s
589 cv := load6432(src, s)
590
591 // Relative offsets
592 offset1 := int32(blk.recentOffsets[0])
593 offset2 := int32(blk.recentOffsets[1])
594
595 addLiterals := func(s *seq, until int32) {
596 if until == nextEmit {
597 return
598 }
599 blk.literals = append(blk.literals, src[nextEmit:until]...)
600 s.litLen = uint32(until - nextEmit)
601 }
602 if debugEncoder {
603 println("recent offsets:", blk.recentOffsets)
604 }
605
606 encodeLoop:
607 for {
608 // t will contain the match offset when we find one.
609 // When existing the search loop, we have already checked 4 bytes.
610 var t int32
611
612 // We will not use repeat offsets across blocks.
613 // By not using them for the first 3 matches
614 canRepeat := len(blk.sequences) > 2
615
616 for {
617 if debugAsserts && canRepeat && offset1 == 0 {
618 panic("offset0 was 0")
619 }
620
621 nextHash := hashLen(cv, hashLog, tableFastHashLen)
622 nextHash2 := hashLen(cv>>8, hashLog, tableFastHashLen)
623 candidate := e.table[nextHash]
624 candidate2 := e.table[nextHash2]
625 repIndex := s - offset1 + 2
626
627 e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
628 e.markShardDirty(nextHash)
629 e.table[nextHash2] = tableEntry{offset: s + e.cur + 1, val: uint32(cv >> 8)}
630 e.markShardDirty(nextHash2)
631
632 if canRepeat && repIndex >= 0 && load3232(src, repIndex) == uint32(cv>>16) {
633 // Consider history as well.
634 var seq seq
635 length := 4 + e.matchlen(s+6, repIndex+4, src)
636
637 seq.matchLen = uint32(length - zstdMinMatch)
638
639 // We might be able to match backwards.
640 // Extend as long as we can.
641 start := s + 2
642 // We end the search early, so we don't risk 0 literals
643 // and have to do special offset treatment.
644 startLimit := nextEmit + 1
645
646 sMin := max(s-e.maxMatchOff, 0)
647 for repIndex > sMin && start > startLimit && src[repIndex-1] == src[start-1] && seq.matchLen < maxMatchLength-zstdMinMatch {
648 repIndex--
649 start--
650 seq.matchLen++
651 }
652 addLiterals(&seq, start)
653
654 // rep 0
655 seq.offset = 1
656 if debugSequences {
657 println("repeat sequence", seq, "next s:", s)
658 }
659 blk.sequences = append(blk.sequences, seq)
660 s += length + 2
661 nextEmit = s
662 if s >= sLimit {
663 if debugEncoder {
664 println("repeat ended", s, length)
665
666 }
667 break encodeLoop
668 }
669 cv = load6432(src, s)
670 continue
671 }
672 coffset0 := s - (candidate.offset - e.cur)
673 coffset1 := s - (candidate2.offset - e.cur) + 1
674 if coffset0 < e.maxMatchOff && uint32(cv) == candidate.val {
675 // found a regular match
676 t = candidate.offset - e.cur
677 if debugAsserts && s <= t {
678 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
679 }
680 if debugAsserts && s-t > e.maxMatchOff {
681 panic("s - t >e.maxMatchOff")
682 }
683 break
684 }
685
686 if coffset1 < e.maxMatchOff && uint32(cv>>8) == candidate2.val {
687 // found a regular match
688 t = candidate2.offset - e.cur
689 s++
690 if debugAsserts && s <= t {
691 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
692 }
693 if debugAsserts && s-t > e.maxMatchOff {
694 panic("s - t >e.maxMatchOff")
695 }
696 if debugAsserts && t < 0 {
697 panic("t<0")
698 }
699 break
700 }
701 s += stepSize + ((s - nextEmit) >> (kSearchStrength - 1))
702 if s >= sLimit {
703 break encodeLoop
704 }
705 cv = load6432(src, s)
706 }
707 // A 4-byte match has been found. We'll later see if more than 4 bytes.
708 offset2 = offset1
709 offset1 = s - t
710
711 if debugAsserts && s <= t {
712 panic(fmt.Sprintf("s (%d) <= t (%d)", s, t))
713 }
714
715 if debugAsserts && canRepeat && int(offset1) > len(src) {
716 panic("invalid offset")
717 }
718
719 // Extend the 4-byte match as long as possible.
720 l := e.matchlen(s+4, t+4, src) + 4
721
722 // Extend backwards
723 tMin := max(s-e.maxMatchOff, 0)
724 for t > tMin && s > nextEmit && src[t-1] == src[s-1] && l < maxMatchLength {
725 s--
726 t--
727 l++
728 }
729
730 // Write our sequence.
731 var seq seq
732 seq.litLen = uint32(s - nextEmit)
733 seq.matchLen = uint32(l - zstdMinMatch)
734 if seq.litLen > 0 {
735 blk.literals = append(blk.literals, src[nextEmit:s]...)
736 }
737 // Don't use repeat offsets
738 seq.offset = uint32(s-t) + 3
739 s += l
740 if debugSequences {
741 println("sequence", seq, "next s:", s)
742 }
743 blk.sequences = append(blk.sequences, seq)
744 nextEmit = s
745 if s >= sLimit {
746 break encodeLoop
747 }
748 cv = load6432(src, s)
749
750 // Check offset 2
751 if o2 := s - offset2; canRepeat && load3232(src, o2) == uint32(cv) {
752 // We have at least 4 byte match.
753 // No need to check backwards. We come straight from a match
754 l := 4 + e.matchlen(s+4, o2+4, src)
755
756 // Store this, since we have it.
757 nextHash := hashLen(cv, hashLog, tableFastHashLen)
758 e.table[nextHash] = tableEntry{offset: s + e.cur, val: uint32(cv)}
759 e.markShardDirty(nextHash)
760 seq.matchLen = uint32(l) - zstdMinMatch
761 seq.litLen = 0
762 // Since litlen is always 0, this is offset 1.
763 seq.offset = 1
764 s += l
765 nextEmit = s
766 if debugSequences {
767 println("sequence", seq, "next s:", s)
768 }
769 blk.sequences = append(blk.sequences, seq)
770
771 // Swap offset 1 and 2.
772 offset1, offset2 = offset2, offset1
773 if s >= sLimit {
774 break encodeLoop
775 }
776 // Prepare next loop.
777 cv = load6432(src, s)
778 }
779 }
780
781 if int(nextEmit) < len(src) {
782 blk.literals = append(blk.literals, src[nextEmit:]...)
783 blk.extraLits = len(src) - int(nextEmit)
784 }
785 blk.recentOffsets[0] = uint32(offset1)
786 blk.recentOffsets[1] = uint32(offset2)
787 if debugEncoder {
788 println("returning, recent offsets:", blk.recentOffsets, "extra literals:", blk.extraLits)
789 }
790 }
791
792 // ResetDict will reset and set a dictionary if not nil
793 func (e *fastEncoder) Reset(d *dict, singleBlock bool) {
794 e.resetBase(d, singleBlock)
795 if d != nil {
796 panic("fastEncoder: Reset with dict")
797 }
798 }
799
800 // ResetDict will reset and set a dictionary if not nil
801 func (e *fastEncoderDict) Reset(d *dict, singleBlock bool) {
802 e.resetBase(d, singleBlock)
803 if d == nil {
804 return
805 }
806
807 // Init or copy dict table
808 if len(e.dictTable) != len(e.table) || d.id != e.lastDictID {
809 if len(e.dictTable) != len(e.table) {
810 e.dictTable = make([]tableEntry, len(e.table))
811 }
812 if true {
813 end := e.maxMatchOff + int32(len(d.content)) - 8
814 for i := e.maxMatchOff; i < end; i += 2 {
815 const hashLog = tableBits
816
817 cv := load6432(d.content, i-e.maxMatchOff)
818 nextHash := hashLen(cv, hashLog, tableFastHashLen) // 0 -> 6
819 nextHash1 := hashLen(cv>>8, hashLog, tableFastHashLen) // 1 -> 7
820 e.dictTable[nextHash] = tableEntry{
821 val: uint32(cv),
822 offset: i,
823 }
824 e.dictTable[nextHash1] = tableEntry{
825 val: uint32(cv >> 8),
826 offset: i + 1,
827 }
828 }
829 }
830 e.lastDictID = d.id
831 e.allDirty = true
832 }
833
834 e.cur = e.maxMatchOff
835 dirtyShardCnt := 0
836 if !e.allDirty {
837 for i := range e.tableShardDirty {
838 if e.tableShardDirty[i] {
839 dirtyShardCnt++
840 }
841 }
842 }
843
844 const shardCnt = tableShardCnt
845 const shardSize = tableShardSize
846 if e.allDirty || dirtyShardCnt > shardCnt*4/6 {
847 //copy(e.table[:], e.dictTable)
848 e.table = *(*[tableSize]tableEntry)(e.dictTable)
849 for i := range e.tableShardDirty {
850 e.tableShardDirty[i] = false
851 }
852 e.allDirty = false
853 return
854 }
855 for i := range e.tableShardDirty {
856 if !e.tableShardDirty[i] {
857 continue
858 }
859
860 //copy(e.table[i*shardSize:(i+1)*shardSize], e.dictTable[i*shardSize:(i+1)*shardSize])
861 *(*[shardSize]tableEntry)(e.table[i*shardSize:]) = *(*[shardSize]tableEntry)(e.dictTable[i*shardSize:])
862 e.tableShardDirty[i] = false
863 }
864 e.allDirty = false
865 }
866
867 func (e *fastEncoderDict) markAllShardsDirty() {
868 e.allDirty = true
869 }
870
871 func (e *fastEncoderDict) markShardDirty(entryNum uint32) {
872 e.tableShardDirty[entryNum/tableShardSize] = true
873 }
874