Update dependencies (#2007)

* Update dependencies

1 files changed, 594 insertions, 1 deletions

diff --git a/vendor/github.com/klauspost/compress/s2/encode_all.go b/vendor/github.com/klauspost/compress/s2/encode_all.go
index 8b16c38a..11657f09 100644
--- a/vendor/github.com/klauspost/compress/s2/encode_all.go
+++ b/vendor/github.com/klauspost/compress/s2/encode_all.go
@@ -8,6 +8,7 @@ package s2
 import (
 	"bytes"
 	"encoding/binary"
+	"fmt"
 	"math/bits"
 )
 
@@ -58,8 +59,9 @@ func encodeGo(dst, src []byte) []byte {
 // been written.
 //
 // It also assumes that:
+//
 //	len(dst) >= MaxEncodedLen(len(src)) &&
-// 	minNonLiteralBlockSize <= len(src) && len(src) <= maxBlockSize
+//	minNonLiteralBlockSize <= len(src) && len(src) <= maxBlockSize
 func encodeBlockGo(dst, src []byte) (d int) {
 	// Initialize the hash table.
 	const (
@@ -454,3 +456,594 @@ emitRemainder:
 	}
 	return d
 }
+
+// encodeBlockGo encodes a non-empty src to a guaranteed-large-enough dst. It
+// assumes that the varint-encoded length of the decompressed bytes has already
+// been written.
+//
+// It also assumes that:
+//
+//	len(dst) >= MaxEncodedLen(len(src)) &&
+//	minNonLiteralBlockSize <= len(src) && len(src) <= maxBlockSize
+func encodeBlockDictGo(dst, src []byte, dict *Dict) (d int) {
+	// Initialize the hash table.
+	const (
+		tableBits    = 14
+		maxTableSize = 1 << tableBits
+		maxAhead     = 8 // maximum bytes ahead without checking sLimit
+
+		debug = false
+	)
+	dict.initFast()
+
+	var table [maxTableSize]uint32
+
+	// sLimit is when to stop looking for offset/length copies. The inputMargin
+	// lets us use a fast path for emitLiteral in the main loop, while we are
+	// looking for copies.
+	sLimit := len(src) - inputMargin
+	if sLimit > MaxDictSrcOffset-maxAhead {
+		sLimit = MaxDictSrcOffset - maxAhead
+	}
+
+	// Bail if we can't compress to at least this.
+	dstLimit := len(src) - len(src)>>5 - 5
+
+	// nextEmit is where in src the next emitLiteral should start from.
+	nextEmit := 0
+
+	// The encoded form can start with a dict entry (copy or repeat).
+	s := 0
+
+	// Convert dict repeat to offset
+	repeat := len(dict.dict) - dict.repeat
+	cv := load64(src, 0)
+
+	// While in dict
+searchDict:
+	for {
+		// Next src position to check
+		nextS := s + (s-nextEmit)>>6 + 4
+		hash0 := hash6(cv, tableBits)
+		hash1 := hash6(cv>>8, tableBits)
+		if nextS > sLimit {
+			if debug {
+				fmt.Println("slimit reached", s, nextS)
+			}
+			break searchDict
+		}
+		candidateDict := int(dict.fastTable[hash0])
+		candidateDict2 := int(dict.fastTable[hash1])
+		candidate2 := int(table[hash1])
+		candidate := int(table[hash0])
+		table[hash0] = uint32(s)
+		table[hash1] = uint32(s + 1)
+		hash2 := hash6(cv>>16, tableBits)
+
+		// Check repeat at offset checkRep.
+		const checkRep = 1
+
+		if repeat > s {
+			candidate := len(dict.dict) - repeat + s
+			if repeat-s >= 4 && uint32(cv) == load32(dict.dict, candidate) {
+				// Extend back
+				base := s
+				for i := candidate; base > nextEmit && i > 0 && dict.dict[i-1] == src[base-1]; {
+					i--
+					base--
+				}
+				d += emitLiteral(dst[d:], src[nextEmit:base])
+				if debug && nextEmit != base {
+					fmt.Println("emitted ", base-nextEmit, "literals")
+				}
+				s += 4
+				candidate += 4
+				for candidate < len(dict.dict)-8 && s <= len(src)-8 {
+					if diff := load64(src, s) ^ load64(dict.dict, candidate); diff != 0 {
+						s += bits.TrailingZeros64(diff) >> 3
+						break
+					}
+					s += 8
+					candidate += 8
+				}
+				d += emitRepeat(dst[d:], repeat, s-base)
+				if debug {
+					fmt.Println("emitted dict repeat length", s-base, "offset:", repeat, "s:", s)
+				}
+				nextEmit = s
+				if s >= sLimit {
+					break searchDict
+				}
+				cv = load64(src, s)
+				continue
+			}
+		} else if uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) {
+			base := s + checkRep
+			// Extend back
+			for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; {
+				i--
+				base--
+			}
+			d += emitLiteral(dst[d:], src[nextEmit:base])
+			if debug && nextEmit != base {
+				fmt.Println("emitted ", base-nextEmit, "literals")
+			}
+
+			// Extend forward
+			candidate := s - repeat + 4 + checkRep
+			s += 4 + checkRep
+			for s <= sLimit {
+				if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
+					s += bits.TrailingZeros64(diff) >> 3
+					break
+				}
+				s += 8
+				candidate += 8
+			}
+			if debug {
+				// Validate match.
+				if s <= candidate {
+					panic("s <= candidate")
+				}
+				a := src[base:s]
+				b := src[base-repeat : base-repeat+(s-base)]
+				if !bytes.Equal(a, b) {
+					panic("mismatch")
+				}
+			}
+
+			if nextEmit > 0 {
+				// same as `add := emitCopy(dst[d:], repeat, s-base)` but skips storing offset.
+				d += emitRepeat(dst[d:], repeat, s-base)
+			} else {
+				// First match, cannot be repeat.
+				d += emitCopy(dst[d:], repeat, s-base)
+			}
+
+			nextEmit = s
+			if s >= sLimit {
+				break searchDict
+			}
+			if debug {
+				fmt.Println("emitted reg repeat", s-base, "s:", s)
+			}
+			cv = load64(src, s)
+			continue searchDict
+		}
+		if s == 0 {
+			cv = load64(src, nextS)
+			s = nextS
+			continue searchDict
+		}
+		// Start with table. These matches will always be closer.
+		if uint32(cv) == load32(src, candidate) {
+			goto emitMatch
+		}
+		candidate = int(table[hash2])
+		if uint32(cv>>8) == load32(src, candidate2) {
+			table[hash2] = uint32(s + 2)
+			candidate = candidate2
+			s++
+			goto emitMatch
+		}
+
+		// Check dict. Dicts have longer offsets, so we want longer matches.
+		if cv == load64(dict.dict, candidateDict) {
+			table[hash2] = uint32(s + 2)
+			goto emitDict
+		}
+
+		candidateDict = int(dict.fastTable[hash2])
+		// Check if upper 7 bytes match
+		if candidateDict2 >= 1 {
+			if cv^load64(dict.dict, candidateDict2-1) < (1 << 8) {
+				table[hash2] = uint32(s + 2)
+				candidateDict = candidateDict2
+				s++
+				goto emitDict
+			}
+		}
+
+		table[hash2] = uint32(s + 2)
+		if uint32(cv>>16) == load32(src, candidate) {
+			s += 2
+			goto emitMatch
+		}
+		if candidateDict >= 2 {
+			// Check if upper 6 bytes match
+			if cv^load64(dict.dict, candidateDict-2) < (1 << 16) {
+				s += 2
+				goto emitDict
+			}
+		}
+
+		cv = load64(src, nextS)
+		s = nextS
+		continue searchDict
+
+	emitDict:
+		{
+			if debug {
+				if load32(dict.dict, candidateDict) != load32(src, s) {
+					panic("dict emit mismatch")
+				}
+			}
+			// Extend backwards.
+			// The top bytes will be rechecked to get the full match.
+			for candidateDict > 0 && s > nextEmit && dict.dict[candidateDict-1] == src[s-1] {
+				candidateDict--
+				s--
+			}
+
+			// Bail if we exceed the maximum size.
+			if d+(s-nextEmit) > dstLimit {
+				return 0
+			}
+
+			// A 4-byte match has been found. We'll later see if more than 4 bytes
+			// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
+			// them as literal bytes.
+
+			d += emitLiteral(dst[d:], src[nextEmit:s])
+			if debug && nextEmit != s {
+				fmt.Println("emitted ", s-nextEmit, "literals")
+			}
+			{
+				// Invariant: we have a 4-byte match at s, and no need to emit any
+				// literal bytes prior to s.
+				base := s
+				repeat = s + (len(dict.dict)) - candidateDict
+
+				// Extend the 4-byte match as long as possible.
+				s += 4
+				candidateDict += 4
+				for s <= len(src)-8 && len(dict.dict)-candidateDict >= 8 {
+					if diff := load64(src, s) ^ load64(dict.dict, candidateDict); diff != 0 {
+						s += bits.TrailingZeros64(diff) >> 3
+						break
+					}
+					s += 8
+					candidateDict += 8
+				}
+
+				// Matches longer than 64 are split.
+				if s <= sLimit || s-base < 8 {
+					d += emitCopy(dst[d:], repeat, s-base)
+				} else {
+					// Split to ensure we don't start a copy within next block
+					d += emitCopy(dst[d:], repeat, 4)
+					d += emitRepeat(dst[d:], repeat, s-base-4)
+				}
+				if false {
+					// Validate match.
+					if s <= candidate {
+						panic("s <= candidate")
+					}
+					a := src[base:s]
+					b := dict.dict[base-repeat : base-repeat+(s-base)]
+					if !bytes.Equal(a, b) {
+						panic("mismatch")
+					}
+				}
+				if debug {
+					fmt.Println("emitted dict copy, length", s-base, "offset:", repeat, "s:", s)
+				}
+				nextEmit = s
+				if s >= sLimit {
+					break searchDict
+				}
+
+				if d > dstLimit {
+					// Do we have space for more, if not bail.
+					return 0
+				}
+
+				// Index and continue loop to try new candidate.
+				x := load64(src, s-2)
+				m2Hash := hash6(x, tableBits)
+				currHash := hash6(x>>8, tableBits)
+				candidate = int(table[currHash])
+				table[m2Hash] = uint32(s - 2)
+				table[currHash] = uint32(s - 1)
+				cv = load64(src, s)
+			}
+			continue
+		}
+	emitMatch:
+
+		// Extend backwards.
+		// The top bytes will be rechecked to get the full match.
+		for candidate > 0 && s > nextEmit && src[candidate-1] == src[s-1] {
+			candidate--
+			s--
+		}
+
+		// Bail if we exceed the maximum size.
+		if d+(s-nextEmit) > dstLimit {
+			return 0
+		}
+
+		// A 4-byte match has been found. We'll later see if more than 4 bytes
+		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
+		// them as literal bytes.
+
+		d += emitLiteral(dst[d:], src[nextEmit:s])
+		if debug && nextEmit != s {
+			fmt.Println("emitted ", s-nextEmit, "literals")
+		}
+		// Call emitCopy, and then see if another emitCopy could be our next
+		// move. Repeat until we find no match for the input immediately after
+		// what was consumed by the last emitCopy call.
+		//
+		// If we exit this loop normally then we need to call emitLiteral next,
+		// though we don't yet know how big the literal will be. We handle that
+		// by proceeding to the next iteration of the main loop. We also can
+		// exit this loop via goto if we get close to exhausting the input.
+		for {
+			// Invariant: we have a 4-byte match at s, and no need to emit any
+			// literal bytes prior to s.
+			base := s
+			repeat = base - candidate
+
+			// Extend the 4-byte match as long as possible.
+			s += 4
+			candidate += 4
+			for s <= len(src)-8 {
+				if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
+					s += bits.TrailingZeros64(diff) >> 3
+					break
+				}
+				s += 8
+				candidate += 8
+			}
+
+			d += emitCopy(dst[d:], repeat, s-base)
+			if debug {
+				// Validate match.
+				if s <= candidate {
+					panic("s <= candidate")
+				}
+				a := src[base:s]
+				b := src[base-repeat : base-repeat+(s-base)]
+				if !bytes.Equal(a, b) {
+					panic("mismatch")
+				}
+			}
+			if debug {
+				fmt.Println("emitted src copy, length", s-base, "offset:", repeat, "s:", s)
+			}
+			nextEmit = s
+			if s >= sLimit {
+				break searchDict
+			}
+
+			if d > dstLimit {
+				// Do we have space for more, if not bail.
+				return 0
+			}
+			// Check for an immediate match, otherwise start search at s+1
+			x := load64(src, s-2)
+			m2Hash := hash6(x, tableBits)
+			currHash := hash6(x>>16, tableBits)
+			candidate = int(table[currHash])
+			table[m2Hash] = uint32(s - 2)
+			table[currHash] = uint32(s)
+			if debug && s == candidate {
+				panic("s == candidate")
+			}
+			if uint32(x>>16) != load32(src, candidate) {
+				cv = load64(src, s+1)
+				s++
+				break
+			}
+		}
+	}
+
+	// Search without dict:
+	if repeat > s {
+		repeat = 0
+	}
+
+	// No more dict
+	sLimit = len(src) - inputMargin
+	if s >= sLimit {
+		goto emitRemainder
+	}
+	if debug {
+		fmt.Println("non-dict matching at", s, "repeat:", repeat)
+	}
+	cv = load64(src, s)
+	if debug {
+		fmt.Println("now", s, "->", sLimit, "out:", d, "left:", len(src)-s, "nextemit:", nextEmit, "dstLimit:", dstLimit, "s:", s)
+	}
+	for {
+		candidate := 0
+		for {
+			// Next src position to check
+			nextS := s + (s-nextEmit)>>6 + 4
+			if nextS > sLimit {
+				goto emitRemainder
+			}
+			hash0 := hash6(cv, tableBits)
+			hash1 := hash6(cv>>8, tableBits)
+			candidate = int(table[hash0])
+			candidate2 := int(table[hash1])
+			table[hash0] = uint32(s)
+			table[hash1] = uint32(s + 1)
+			hash2 := hash6(cv>>16, tableBits)
+
+			// Check repeat at offset checkRep.
+			const checkRep = 1
+			if repeat > 0 && uint32(cv>>(checkRep*8)) == load32(src, s-repeat+checkRep) {
+				base := s + checkRep
+				// Extend back
+				for i := base - repeat; base > nextEmit && i > 0 && src[i-1] == src[base-1]; {
+					i--
+					base--
+				}
+				d += emitLiteral(dst[d:], src[nextEmit:base])
+				if debug && nextEmit != base {
+					fmt.Println("emitted ", base-nextEmit, "literals")
+				}
+				// Extend forward
+				candidate := s - repeat + 4 + checkRep
+				s += 4 + checkRep
+				for s <= sLimit {
+					if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
+						s += bits.TrailingZeros64(diff) >> 3
+						break
+					}
+					s += 8
+					candidate += 8
+				}
+				if debug {
+					// Validate match.
+					if s <= candidate {
+						panic("s <= candidate")
+					}
+					a := src[base:s]
+					b := src[base-repeat : base-repeat+(s-base)]
+					if !bytes.Equal(a, b) {
+						panic("mismatch")
+					}
+				}
+				if nextEmit > 0 {
+					// same as `add := emitCopy(dst[d:], repeat, s-base)` but skips storing offset.
+					d += emitRepeat(dst[d:], repeat, s-base)
+				} else {
+					// First match, cannot be repeat.
+					d += emitCopy(dst[d:], repeat, s-base)
+				}
+				if debug {
+					fmt.Println("emitted src repeat length", s-base, "offset:", repeat, "s:", s)
+				}
+				nextEmit = s
+				if s >= sLimit {
+					goto emitRemainder
+				}
+
+				cv = load64(src, s)
+				continue
+			}
+
+			if uint32(cv) == load32(src, candidate) {
+				break
+			}
+			candidate = int(table[hash2])
+			if uint32(cv>>8) == load32(src, candidate2) {
+				table[hash2] = uint32(s + 2)
+				candidate = candidate2
+				s++
+				break
+			}
+			table[hash2] = uint32(s + 2)
+			if uint32(cv>>16) == load32(src, candidate) {
+				s += 2
+				break
+			}
+
+			cv = load64(src, nextS)
+			s = nextS
+		}
+
+		// Extend backwards.
+		// The top bytes will be rechecked to get the full match.
+		for candidate > 0 && s > nextEmit && src[candidate-1] == src[s-1] {
+			candidate--
+			s--
+		}
+
+		// Bail if we exceed the maximum size.
+		if d+(s-nextEmit) > dstLimit {
+			return 0
+		}
+
+		// A 4-byte match has been found. We'll later see if more than 4 bytes
+		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
+		// them as literal bytes.
+
+		d += emitLiteral(dst[d:], src[nextEmit:s])
+		if debug && nextEmit != s {
+			fmt.Println("emitted ", s-nextEmit, "literals")
+		}
+		// Call emitCopy, and then see if another emitCopy could be our next
+		// move. Repeat until we find no match for the input immediately after
+		// what was consumed by the last emitCopy call.
+		//
+		// If we exit this loop normally then we need to call emitLiteral next,
+		// though we don't yet know how big the literal will be. We handle that
+		// by proceeding to the next iteration of the main loop. We also can
+		// exit this loop via goto if we get close to exhausting the input.
+		for {
+			// Invariant: we have a 4-byte match at s, and no need to emit any
+			// literal bytes prior to s.
+			base := s
+			repeat = base - candidate
+
+			// Extend the 4-byte match as long as possible.
+			s += 4
+			candidate += 4
+			for s <= len(src)-8 {
+				if diff := load64(src, s) ^ load64(src, candidate); diff != 0 {
+					s += bits.TrailingZeros64(diff) >> 3
+					break
+				}
+				s += 8
+				candidate += 8
+			}
+
+			d += emitCopy(dst[d:], repeat, s-base)
+			if debug {
+				// Validate match.
+				if s <= candidate {
+					panic("s <= candidate")
+				}
+				a := src[base:s]
+				b := src[base-repeat : base-repeat+(s-base)]
+				if !bytes.Equal(a, b) {
+					panic("mismatch")
+				}
+			}
+			if debug {
+				fmt.Println("emitted src copy, length", s-base, "offset:", repeat, "s:", s)
+			}
+			nextEmit = s
+			if s >= sLimit {
+				goto emitRemainder
+			}
+
+			if d > dstLimit {
+				// Do we have space for more, if not bail.
+				return 0
+			}
+			// Check for an immediate match, otherwise start search at s+1
+			x := load64(src, s-2)
+			m2Hash := hash6(x, tableBits)
+			currHash := hash6(x>>16, tableBits)
+			candidate = int(table[currHash])
+			table[m2Hash] = uint32(s - 2)
+			table[currHash] = uint32(s)
+			if debug && s == candidate {
+				panic("s == candidate")
+			}
+			if uint32(x>>16) != load32(src, candidate) {
+				cv = load64(src, s+1)
+				s++
+				break
+			}
+		}
+	}
+
+emitRemainder:
+	if nextEmit < len(src) {
+		// Bail if we exceed the maximum size.
+		if d+len(src)-nextEmit > dstLimit {
+			return 0
+		}
+		d += emitLiteral(dst[d:], src[nextEmit:])
+		if debug && nextEmit != s {
+			fmt.Println("emitted ", len(src)-nextEmit, "literals")
+		}
+	}
+	return d
+}