encode_go.go raw
1 //go:build !amd64 || appengine || !gc || noasm
2 // +build !amd64 appengine !gc noasm
3
4 package s2
5
6 import (
7 "bytes"
8 "math/bits"
9 )
10
11 const hasAmd64Asm = false
12
13 // encodeBlock encodes a non-empty src to a guaranteed-large-enough dst. It
14 // assumes that the varint-encoded length of the decompressed bytes has already
15 // been written.
16 //
17 // It also assumes that:
18 //
19 // len(dst) >= MaxEncodedLen(len(src))
20 func encodeBlock(dst, src []byte) (d int) {
21 if len(src) < minNonLiteralBlockSize {
22 return 0
23 }
24 if len(src) <= 64<<10 {
25 return encodeBlockGo64K(dst, src)
26 }
27 return encodeBlockGo(dst, src)
28 }
29
30 // encodeBlockBetter encodes a non-empty src to a guaranteed-large-enough dst. It
31 // assumes that the varint-encoded length of the decompressed bytes has already
32 // been written.
33 //
34 // It also assumes that:
35 //
36 // len(dst) >= MaxEncodedLen(len(src))
37 func encodeBlockBetter(dst, src []byte) (d int) {
38 if len(src) <= 64<<10 {
39 return encodeBlockBetterGo64K(dst, src)
40 }
41 return encodeBlockBetterGo(dst, src)
42 }
43
44 // encodeBlockBetter encodes a non-empty src to a guaranteed-large-enough dst. It
45 // assumes that the varint-encoded length of the decompressed bytes has already
46 // been written.
47 //
48 // It also assumes that:
49 //
50 // len(dst) >= MaxEncodedLen(len(src))
51 func encodeBlockBetterSnappy(dst, src []byte) (d int) {
52 if len(src) <= 64<<10 {
53 return encodeBlockBetterSnappyGo64K(dst, src)
54 }
55 return encodeBlockBetterSnappyGo(dst, src)
56 }
57
58 // encodeBlock encodes a non-empty src to a guaranteed-large-enough dst. It
59 // assumes that the varint-encoded length of the decompressed bytes has already
60 // been written.
61 //
62 // It also assumes that:
63 //
64 // len(dst) >= MaxEncodedLen(len(src))
65 func encodeBlockSnappy(dst, src []byte) (d int) {
66 if len(src) < minNonLiteralBlockSize {
67 return 0
68 }
69 if len(src) <= 64<<10 {
70 return encodeBlockSnappyGo64K(dst, src)
71 }
72 return encodeBlockSnappyGo(dst, src)
73 }
74
75 // emitLiteral writes a literal chunk and returns the number of bytes written.
76 //
77 // It assumes that:
78 //
79 // dst is long enough to hold the encoded bytes
80 // 0 <= len(lit) && len(lit) <= math.MaxUint32
81 func emitLiteral(dst, lit []byte) int {
82 if len(lit) == 0 {
83 return 0
84 }
85 const num = 63<<2 | tagLiteral
86 i, n := 0, uint(len(lit)-1)
87 switch {
88 case n < 60:
89 dst[0] = uint8(n)<<2 | tagLiteral
90 i = 1
91 case n < 1<<8:
92 dst[1] = uint8(n)
93 dst[0] = 60<<2 | tagLiteral
94 i = 2
95 case n < 1<<16:
96 dst[2] = uint8(n >> 8)
97 dst[1] = uint8(n)
98 dst[0] = 61<<2 | tagLiteral
99 i = 3
100 case n < 1<<24:
101 dst[3] = uint8(n >> 16)
102 dst[2] = uint8(n >> 8)
103 dst[1] = uint8(n)
104 dst[0] = 62<<2 | tagLiteral
105 i = 4
106 default:
107 dst[4] = uint8(n >> 24)
108 dst[3] = uint8(n >> 16)
109 dst[2] = uint8(n >> 8)
110 dst[1] = uint8(n)
111 dst[0] = 63<<2 | tagLiteral
112 i = 5
113 }
114 return i + copy(dst[i:], lit)
115 }
116
117 // emitRepeat writes a repeat chunk and returns the number of bytes written.
118 // Length must be at least 4 and < 1<<24
119 func emitRepeat(dst []byte, offset, length int) int {
120 // Repeat offset, make length cheaper
121 length -= 4
122 if length <= 4 {
123 dst[0] = uint8(length)<<2 | tagCopy1
124 dst[1] = 0
125 return 2
126 }
127 if length < 8 && offset < 2048 {
128 // Encode WITH offset
129 dst[1] = uint8(offset)
130 dst[0] = uint8(offset>>8)<<5 | uint8(length)<<2 | tagCopy1
131 return 2
132 }
133 if length < (1<<8)+4 {
134 length -= 4
135 dst[2] = uint8(length)
136 dst[1] = 0
137 dst[0] = 5<<2 | tagCopy1
138 return 3
139 }
140 if length < (1<<16)+(1<<8) {
141 length -= 1 << 8
142 dst[3] = uint8(length >> 8)
143 dst[2] = uint8(length >> 0)
144 dst[1] = 0
145 dst[0] = 6<<2 | tagCopy1
146 return 4
147 }
148 const maxRepeat = (1 << 24) - 1
149 length -= 1 << 16
150 left := 0
151 if length > maxRepeat {
152 left = length - maxRepeat + 4
153 length = maxRepeat - 4
154 }
155 dst[4] = uint8(length >> 16)
156 dst[3] = uint8(length >> 8)
157 dst[2] = uint8(length >> 0)
158 dst[1] = 0
159 dst[0] = 7<<2 | tagCopy1
160 if left > 0 {
161 return 5 + emitRepeat(dst[5:], offset, left)
162 }
163 return 5
164 }
165
166 // emitCopy writes a copy chunk and returns the number of bytes written.
167 //
168 // It assumes that:
169 //
170 // dst is long enough to hold the encoded bytes
171 // 1 <= offset && offset <= math.MaxUint32
172 // 4 <= length && length <= 1 << 24
173 func emitCopy(dst []byte, offset, length int) int {
174 if offset >= 65536 {
175 i := 0
176 if length > 64 {
177 // Emit a length 64 copy, encoded as 5 bytes.
178 dst[4] = uint8(offset >> 24)
179 dst[3] = uint8(offset >> 16)
180 dst[2] = uint8(offset >> 8)
181 dst[1] = uint8(offset)
182 dst[0] = 63<<2 | tagCopy4
183 length -= 64
184 if length >= 4 {
185 // Emit remaining as repeats
186 return 5 + emitRepeat(dst[5:], offset, length)
187 }
188 i = 5
189 }
190 if length == 0 {
191 return i
192 }
193 // Emit a copy, offset encoded as 4 bytes.
194 dst[i+0] = uint8(length-1)<<2 | tagCopy4
195 dst[i+1] = uint8(offset)
196 dst[i+2] = uint8(offset >> 8)
197 dst[i+3] = uint8(offset >> 16)
198 dst[i+4] = uint8(offset >> 24)
199 return i + 5
200 }
201
202 // Offset no more than 2 bytes.
203 if length > 64 {
204 off := 3
205 if offset < 2048 {
206 // emit 8 bytes as tagCopy1, rest as repeats.
207 dst[1] = uint8(offset)
208 dst[0] = uint8(offset>>8)<<5 | uint8(8-4)<<2 | tagCopy1
209 length -= 8
210 off = 2
211 } else {
212 // Emit a length 60 copy, encoded as 3 bytes.
213 // Emit remaining as repeat value (minimum 4 bytes).
214 dst[2] = uint8(offset >> 8)
215 dst[1] = uint8(offset)
216 dst[0] = 59<<2 | tagCopy2
217 length -= 60
218 }
219 // Emit remaining as repeats, at least 4 bytes remain.
220 return off + emitRepeat(dst[off:], offset, length)
221 }
222 if length >= 12 || offset >= 2048 {
223 // Emit the remaining copy, encoded as 3 bytes.
224 dst[2] = uint8(offset >> 8)
225 dst[1] = uint8(offset)
226 dst[0] = uint8(length-1)<<2 | tagCopy2
227 return 3
228 }
229 // Emit the remaining copy, encoded as 2 bytes.
230 dst[1] = uint8(offset)
231 dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1
232 return 2
233 }
234
235 // emitCopyNoRepeat writes a copy chunk and returns the number of bytes written.
236 //
237 // It assumes that:
238 //
239 // dst is long enough to hold the encoded bytes
240 // 1 <= offset && offset <= math.MaxUint32
241 // 4 <= length && length <= 1 << 24
242 func emitCopyNoRepeat(dst []byte, offset, length int) int {
243 if offset >= 65536 {
244 i := 0
245 if length > 64 {
246 // Emit a length 64 copy, encoded as 5 bytes.
247 dst[4] = uint8(offset >> 24)
248 dst[3] = uint8(offset >> 16)
249 dst[2] = uint8(offset >> 8)
250 dst[1] = uint8(offset)
251 dst[0] = 63<<2 | tagCopy4
252 length -= 64
253 if length >= 4 {
254 // Emit remaining as repeats
255 return 5 + emitCopyNoRepeat(dst[5:], offset, length)
256 }
257 i = 5
258 }
259 if length == 0 {
260 return i
261 }
262 // Emit a copy, offset encoded as 4 bytes.
263 dst[i+0] = uint8(length-1)<<2 | tagCopy4
264 dst[i+1] = uint8(offset)
265 dst[i+2] = uint8(offset >> 8)
266 dst[i+3] = uint8(offset >> 16)
267 dst[i+4] = uint8(offset >> 24)
268 return i + 5
269 }
270
271 // Offset no more than 2 bytes.
272 if length > 64 {
273 // Emit a length 60 copy, encoded as 3 bytes.
274 // Emit remaining as repeat value (minimum 4 bytes).
275 dst[2] = uint8(offset >> 8)
276 dst[1] = uint8(offset)
277 dst[0] = 59<<2 | tagCopy2
278 length -= 60
279 // Emit remaining as repeats, at least 4 bytes remain.
280 return 3 + emitCopyNoRepeat(dst[3:], offset, length)
281 }
282 if length >= 12 || offset >= 2048 {
283 // Emit the remaining copy, encoded as 3 bytes.
284 dst[2] = uint8(offset >> 8)
285 dst[1] = uint8(offset)
286 dst[0] = uint8(length-1)<<2 | tagCopy2
287 return 3
288 }
289 // Emit the remaining copy, encoded as 2 bytes.
290 dst[1] = uint8(offset)
291 dst[0] = uint8(offset>>8)<<5 | uint8(length-4)<<2 | tagCopy1
292 return 2
293 }
294
295 // matchLen returns how many bytes match in a and b
296 //
297 // It assumes that:
298 //
299 // len(a) <= len(b)
300 func matchLen(a []byte, b []byte) int {
301 b = b[:len(a)]
302 var checked int
303 if len(a) > 4 {
304 // Try 4 bytes first
305 if diff := load32(a, 0) ^ load32(b, 0); diff != 0 {
306 return bits.TrailingZeros32(diff) >> 3
307 }
308 // Switch to 8 byte matching.
309 checked = 4
310 a = a[4:]
311 b = b[4:]
312 for len(a) >= 8 {
313 b = b[:len(a)]
314 if diff := load64(a, 0) ^ load64(b, 0); diff != 0 {
315 return checked + (bits.TrailingZeros64(diff) >> 3)
316 }
317 checked += 8
318 a = a[8:]
319 b = b[8:]
320 }
321 }
322 b = b[:len(a)]
323 for i := range a {
324 if a[i] != b[i] {
325 return int(i) + checked
326 }
327 }
328 return len(a) + checked
329 }
330
331 // input must be > inputMargin
332 func calcBlockSize(src []byte, _ *[32768]byte) (d int) {
333 // Initialize the hash table.
334 const (
335 tableBits = 13
336 maxTableSize = 1 << tableBits
337 )
338
339 var table [maxTableSize]uint32
340
341 // sLimit is when to stop looking for offset/length copies. The inputMargin
342 // lets us use a fast path for emitLiteral in the main loop, while we are
343 // looking for copies.
344 sLimit := len(src) - inputMargin
345
346 // Bail if we can't compress to at least this.
347 dstLimit := len(src) - len(src)>>5 - 5
348
349 // nextEmit is where in src the next emitLiteral should start from.
350 nextEmit := 0
351
352 // The encoded form must start with a literal, as there are no previous
353 // bytes to copy, so we start looking for hash matches at s == 1.
354 s := 1
355 cv := load64(src, s)
356
357 // We search for a repeat at -1, but don't output repeats when nextEmit == 0
358 repeat := 1
359
360 for {
361 candidate := 0
362 for {
363 // Next src position to check
364 nextS := s + (s-nextEmit)>>6 + 4
365 if nextS > sLimit {
366 goto emitRemainder
367 }
368 hash0 := hash6(cv, tableBits)
369 hash1 := hash6(cv>>8, tableBits)
370 candidate = int(table[hash0])
371 candidate2 := int(table[hash1])
372 table[hash0] = uint32(s)
373 table[hash1] = uint32(s + 1)
374 hash2 := hash6(cv>>16, tableBits)
375
376 // Check repeat at offset checkRep.
377 const checkRep = 1
378 if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) {
379 base := s + checkRep
380 // Extend back
381 for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; {
382 i--
383 base--
384 }
385 d += emitLiteralSize(src[nextEmit:base])
386
387 // Extend forward
388 candidate := s - repeat + 4 + checkRep
389 s += 4 + checkRep
390 for s <= sLimit {
391 if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
392 s += bits.TrailingZeros64(diff) >> 3
393 break
394 }
395 s += 8
396 candidate += 8
397 }
398
399 d += emitCopyNoRepeatSize(repeat, s-base)
400 nextEmit = s
401 if s >= sLimit {
402 goto emitRemainder
403 }
404
405 cv = load64(src, s)
406 continue
407 }
408
409 if uint32(cv) == load32(src, candidate) {
410 break
411 }
412 candidate = int(table[hash2])
413 if uint32(cv>>8) == load32(src, candidate2) {
414 table[hash2] = uint32(s + 2)
415 candidate = candidate2
416 s++
417 break
418 }
419 table[hash2] = uint32(s + 2)
420 if uint32(cv>>16) == load32(src, candidate) {
421 s += 2
422 break
423 }
424
425 cv = load64(src, nextS)
426 s = nextS
427 }
428
429 // Extend backwards
430 for candidate > 0 && s > nextEmit && src[candidate-1] == src[s-1] {
431 candidate--
432 s--
433 }
434
435 // Bail if we exceed the maximum size.
436 if d+(s-nextEmit) > dstLimit {
437 return 0
438 }
439
440 // A 4-byte match has been found. We'll later see if more than 4 bytes
441 // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
442 // them as literal bytes.
443
444 d += emitLiteralSize(src[nextEmit:s])
445
446 // Call emitCopy, and then see if another emitCopy could be our next
447 // move. Repeat until we find no match for the input immediately after
448 // what was consumed by the last emitCopy call.
449 //
450 // If we exit this loop normally then we need to call emitLiteral next,
451 // though we don't yet know how big the literal will be. We handle that
452 // by proceeding to the next iteration of the main loop. We also can
453 // exit this loop via goto if we get close to exhausting the input.
454 for {
455 // Invariant: we have a 4-byte match at s, and no need to emit any
456 // literal bytes prior to s.
457 base := s
458 repeat = base - candidate
459
460 // Extend the 4-byte match as long as possible.
461 s += 4
462 candidate += 4
463 for s <= len(src)-8 {
464 if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
465 s += bits.TrailingZeros64(diff) >> 3
466 break
467 }
468 s += 8
469 candidate += 8
470 }
471
472 d += emitCopyNoRepeatSize(repeat, s-base)
473 if false {
474 // Validate match.
475 a := src[base:s]
476 b := src[base-repeat : base-repeat+(s-base)]
477 if !bytes.Equal(a, b) {
478 panic("mismatch")
479 }
480 }
481
482 nextEmit = s
483 if s >= sLimit {
484 goto emitRemainder
485 }
486
487 if d > dstLimit {
488 // Do we have space for more, if not bail.
489 return 0
490 }
491 // Check for an immediate match, otherwise start search at s+1
492 x := load64(src, s-2)
493 m2Hash := hash6(x, tableBits)
494 currHash := hash6(x>>16, tableBits)
495 candidate = int(table[currHash])
496 table[m2Hash] = uint32(s - 2)
497 table[currHash] = uint32(s)
498 if uint32(x>>16) != load32(src, candidate) {
499 cv = load64(src, s+1)
500 s++
501 break
502 }
503 }
504 }
505
506 emitRemainder:
507 if nextEmit < len(src) {
508 // Bail if we exceed the maximum size.
509 if d+len(src)-nextEmit > dstLimit {
510 return 0
511 }
512 d += emitLiteralSize(src[nextEmit:])
513 }
514 return d
515 }
516
517 // length must be > inputMargin.
518 func calcBlockSizeSmall(src []byte, _ *[2048]byte) (d int) {
519 // Initialize the hash table.
520 const (
521 tableBits = 9
522 maxTableSize = 1 << tableBits
523 )
524
525 var table [maxTableSize]uint32
526
527 // sLimit is when to stop looking for offset/length copies. The inputMargin
528 // lets us use a fast path for emitLiteral in the main loop, while we are
529 // looking for copies.
530 sLimit := len(src) - inputMargin
531
532 // Bail if we can't compress to at least this.
533 dstLimit := len(src) - len(src)>>5 - 5
534
535 // nextEmit is where in src the next emitLiteral should start from.
536 nextEmit := 0
537
538 // The encoded form must start with a literal, as there are no previous
539 // bytes to copy, so we start looking for hash matches at s == 1.
540 s := 1
541 cv := load64(src, s)
542
543 // We search for a repeat at -1, but don't output repeats when nextEmit == 0
544 repeat := 1
545
546 for {
547 candidate := 0
548 for {
549 // Next src position to check
550 nextS := s + (s-nextEmit)>>6 + 4
551 if nextS > sLimit {
552 goto emitRemainder
553 }
554 hash0 := hash6(cv, tableBits)
555 hash1 := hash6(cv>>8, tableBits)
556 candidate = int(table[hash0])
557 candidate2 := int(table[hash1])
558 table[hash0] = uint32(s)
559 table[hash1] = uint32(s + 1)
560 hash2 := hash6(cv>>16, tableBits)
561
562 // Check repeat at offset checkRep.
563 const checkRep = 1
564 if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) {
565 base := s + checkRep
566 // Extend back
567 for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; {
568 i--
569 base--
570 }
571 d += emitLiteralSize(src[nextEmit:base])
572
573 // Extend forward
574 candidate := s - repeat + 4 + checkRep
575 s += 4 + checkRep
576 for s <= sLimit {
577 if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
578 s += bits.TrailingZeros64(diff) >> 3
579 break
580 }
581 s += 8
582 candidate += 8
583 }
584
585 d += emitCopyNoRepeatSize(repeat, s-base)
586 nextEmit = s
587 if s >= sLimit {
588 goto emitRemainder
589 }
590
591 cv = load64(src, s)
592 continue
593 }
594
595 if uint32(cv) == load32(src, candidate) {
596 break
597 }
598 candidate = int(table[hash2])
599 if uint32(cv>>8) == load32(src, candidate2) {
600 table[hash2] = uint32(s + 2)
601 candidate = candidate2
602 s++
603 break
604 }
605 table[hash2] = uint32(s + 2)
606 if uint32(cv>>16) == load32(src, candidate) {
607 s += 2
608 break
609 }
610
611 cv = load64(src, nextS)
612 s = nextS
613 }
614
615 // Extend backwards
616 for candidate > 0 && s > nextEmit && src[candidate-1] == src[s-1] {
617 candidate--
618 s--
619 }
620
621 // Bail if we exceed the maximum size.
622 if d+(s-nextEmit) > dstLimit {
623 return 0
624 }
625
626 // A 4-byte match has been found. We'll later see if more than 4 bytes
627 // match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
628 // them as literal bytes.
629
630 d += emitLiteralSize(src[nextEmit:s])
631
632 // Call emitCopy, and then see if another emitCopy could be our next
633 // move. Repeat until we find no match for the input immediately after
634 // what was consumed by the last emitCopy call.
635 //
636 // If we exit this loop normally then we need to call emitLiteral next,
637 // though we don't yet know how big the literal will be. We handle that
638 // by proceeding to the next iteration of the main loop. We also can
639 // exit this loop via goto if we get close to exhausting the input.
640 for {
641 // Invariant: we have a 4-byte match at s, and no need to emit any
642 // literal bytes prior to s.
643 base := s
644 repeat = base - candidate
645
646 // Extend the 4-byte match as long as possible.
647 s += 4
648 candidate += 4
649 for s <= len(src)-8 {
650 if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
651 s += bits.TrailingZeros64(diff) >> 3
652 break
653 }
654 s += 8
655 candidate += 8
656 }
657
658 d += emitCopyNoRepeatSize(repeat, s-base)
659 if false {
660 // Validate match.
661 a := src[base:s]
662 b := src[base-repeat : base-repeat+(s-base)]
663 if !bytes.Equal(a, b) {
664 panic("mismatch")
665 }
666 }
667
668 nextEmit = s
669 if s >= sLimit {
670 goto emitRemainder
671 }
672
673 if d > dstLimit {
674 // Do we have space for more, if not bail.
675 return 0
676 }
677 // Check for an immediate match, otherwise start search at s+1
678 x := load64(src, s-2)
679 m2Hash := hash6(x, tableBits)
680 currHash := hash6(x>>16, tableBits)
681 candidate = int(table[currHash])
682 table[m2Hash] = uint32(s - 2)
683 table[currHash] = uint32(s)
684 if uint32(x>>16) != load32(src, candidate) {
685 cv = load64(src, s+1)
686 s++
687 break
688 }
689 }
690 }
691
692 emitRemainder:
693 if nextEmit < len(src) {
694 // Bail if we exceed the maximum size.
695 if d+len(src)-nextEmit > dstLimit {
696 return 0
697 }
698 d += emitLiteralSize(src[nextEmit:])
699 }
700 return d
701 }
702
703 // emitLiteral writes a literal chunk and returns the number of bytes written.
704 //
705 // It assumes that:
706 //
707 // dst is long enough to hold the encoded bytes
708 // 0 <= len(lit) && len(lit) <= math.MaxUint32
709 func emitLiteralSize(lit []byte) int {
710 if len(lit) == 0 {
711 return 0
712 }
713 switch {
714 case len(lit) <= 60:
715 return len(lit) + 1
716 case len(lit) <= 1<<8:
717 return len(lit) + 2
718 case len(lit) <= 1<<16:
719 return len(lit) + 3
720 case len(lit) <= 1<<24:
721 return len(lit) + 4
722 default:
723 return len(lit) + 5
724 }
725 }
726
727 func cvtLZ4BlockAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) {
728 panic("cvtLZ4BlockAsm should be unreachable")
729 }
730
731 func cvtLZ4BlockSnappyAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) {
732 panic("cvtLZ4BlockSnappyAsm should be unreachable")
733 }
734
735 func cvtLZ4sBlockAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) {
736 panic("cvtLZ4sBlockAsm should be unreachable")
737 }
738
739 func cvtLZ4sBlockSnappyAsm(dst []byte, src []byte) (uncompressed int, dstUsed int) {
740 panic("cvtLZ4sBlockSnappyAsm should be unreachable")
741 }
742