Source file src/github.com/klauspost/compress/s2/encode_go.go

Documentation: github.com/klauspost/compress/s2

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

View as plain text