level4.go

     1  // Copyright 2026 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package flate
     6  
     7  // Level 4 uses two tables, one for short (4 bytes) and one for long (7 bytes) matches.
     8  type fastEncL4 struct {
     9  	fastGen
    10  	table  [tableSize]tableEntry
    11  	bTable [tableSize]tableEntry
    12  }
    13  
    14  func (e *fastEncL4) encode(dst *tokens, src []byte) {
    15  	const (
    16  		inputMargin            = 12 - 1
    17  		minNonLiteralBlockSize = 1 + 1 + inputMargin
    18  		hashShortBytes         = 4
    19  	)
    20  	// Protect against e.cur wraparound.
    21  	for e.cur >= bufferReset {
    22  		if len(e.hist) == 0 {
    23  			clear(e.table[:])
    24  			clear(e.bTable[:])
    25  			e.cur = maxMatchOffset
    26  			break
    27  		}
    28  		// Shift down everything in the table that isn't already too far away.
    29  		minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
    30  		for i := range e.table[:] {
    31  			v := e.table[i].offset
    32  			if v <= minOff {
    33  				v = 0
    34  			} else {
    35  				v = v - e.cur + maxMatchOffset
    36  			}
    37  			e.table[i].offset = v
    38  		}
    39  		for i := range e.bTable[:] {
    40  			v := e.bTable[i].offset
    41  			if v <= minOff {
    42  				v = 0
    43  			} else {
    44  				v = v - e.cur + maxMatchOffset
    45  			}
    46  			e.bTable[i].offset = v
    47  		}
    48  		e.cur = maxMatchOffset
    49  	}
    50  
    51  	s := e.addBlock(src)
    52  
    53  	// This check isn't in the Snappy implementation, but there, the caller
    54  	// instead of the callee handles this case.
    55  	if len(src) < minNonLiteralBlockSize {
    56  		// We do not fill the token table.
    57  		// This will be picked up by caller.
    58  		dst.n = uint16(len(src))
    59  		return
    60  	}
    61  
    62  	// Override src
    63  	src = e.hist
    64  	nextEmit := s
    65  
    66  	// sLimit is when to stop looking for offset/length copies. The inputMargin
    67  	// lets us use a fast path for emitLiterals in the main loop, while we are
    68  	// looking for copies.
    69  	sLimit := int32(len(src) - inputMargin)
    70  
    71  	// nextEmit is where in src the next emitLiterals should start from.
    72  	cv := loadLE64(src, s)
    73  	for {
    74  		const skipLog = 6
    75  		const doEvery = 1
    76  
    77  		nextS := s
    78  		var t int32
    79  		for {
    80  			nextHashS := hashLen(cv, tableBits, hashShortBytes)
    81  			nextHashL := hashLen(cv, tableBits, hashLongBytes)
    82  
    83  			s = nextS
    84  			nextS = s + doEvery + (s-nextEmit)>>skipLog
    85  			if nextS > sLimit {
    86  				goto emitRemainder
    87  			}
    88  			// Fetch a short+long candidate
    89  			sCandidate := e.table[nextHashS]
    90  			lCandidate := e.bTable[nextHashL]
    91  			next := loadLE64(src, nextS)
    92  			entry := tableEntry{offset: s + e.cur}
    93  			e.table[nextHashS] = entry
    94  			e.bTable[nextHashL] = entry
    95  
    96  			t = lCandidate.offset - e.cur
    97  			if s-t < maxMatchOffset && uint32(cv) == loadLE32(src, t) {
    98  				// We got a long match. Use that.
    99  				break
   100  			}
   101  
   102  			t = sCandidate.offset - e.cur
   103  			if s-t < maxMatchOffset && uint32(cv) == loadLE32(src, t) {
   104  				// Found a 4 match...
   105  				lCandidate = e.bTable[hashLen(next, tableBits, hashLongBytes)]
   106  
   107  				// If the next long is a candidate, check if we should use that instead...
   108  				lOff := lCandidate.offset - e.cur
   109  				if nextS-lOff < maxMatchOffset && loadLE32(src, lOff) == uint32(next) {
   110  					l1, l2 := matchLen(src[s+4:], src[t+4:]), matchLen(src[nextS+4:], src[nextS-lOff+4:])
   111  					if l2 > l1 {
   112  						s = nextS
   113  						t = lCandidate.offset - e.cur
   114  					}
   115  				}
   116  				break
   117  			}
   118  			cv = next
   119  		}
   120  
   121  		// A 4-byte match has been found. We'll later see if more than 4 bytes
   122  		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
   123  		// them as literal bytes.
   124  
   125  		// Extend the 4-byte match as long as possible.
   126  		l := e.matchLenLong(int(s+4), int(t+4), src) + 4
   127  
   128  		// Extend backwards
   129  		for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
   130  			s--
   131  			t--
   132  			l++
   133  		}
   134  		if nextEmit < s {
   135  			for _, v := range src[nextEmit:s] {
   136  				dst.tokens[dst.n] = token(v)
   137  				dst.litHist[v]++
   138  				dst.n++
   139  			}
   140  		}
   141  
   142  		dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
   143  		s += l
   144  		nextEmit = s
   145  		if nextS >= s {
   146  			s = nextS + 1
   147  		}
   148  
   149  		if s >= sLimit {
   150  			// Index first pair after match end.
   151  			if int(s+8) < len(src) {
   152  				cv := loadLE64(src, s)
   153  				e.table[hashLen(cv, tableBits, hashShortBytes)] = tableEntry{offset: s + e.cur}
   154  				e.bTable[hashLen(cv, tableBits, hashLongBytes)] = tableEntry{offset: s + e.cur}
   155  			}
   156  			goto emitRemainder
   157  		}
   158  
   159  		// Store every 3rd hash in-between
   160  		i := nextS
   161  		if i < s-1 {
   162  			cv := loadLE64(src, i)
   163  			t := tableEntry{offset: i + e.cur}
   164  			t2 := tableEntry{offset: t.offset + 1}
   165  			e.bTable[hashLen(cv, tableBits, hashLongBytes)] = t
   166  			e.bTable[hashLen(cv>>8, tableBits, hashLongBytes)] = t2
   167  			e.table[hashLen(cv>>8, tableBits, hashShortBytes)] = t2
   168  
   169  			i += 3
   170  			for ; i < s-1; i += 3 {
   171  				cv := loadLE64(src, i)
   172  				t := tableEntry{offset: i + e.cur}
   173  				t2 := tableEntry{offset: t.offset + 1}
   174  				e.bTable[hashLen(cv, tableBits, hashLongBytes)] = t
   175  				e.bTable[hashLen(cv>>8, tableBits, hashLongBytes)] = t2
   176  				e.table[hashLen(cv>>8, tableBits, hashShortBytes)] = t2
   177  			}
   178  		}
   179  
   180  		// We could immediately start working at s now, but to improve
   181  		// compression we first update the hash table at s-1 and at s.
   182  		x := loadLE64(src, s-1)
   183  		o := e.cur + s - 1
   184  		prevHashS := hashLen(x, tableBits, hashShortBytes)
   185  		prevHashL := hashLen(x, tableBits, hashLongBytes)
   186  		e.table[prevHashS] = tableEntry{offset: o}
   187  		e.bTable[prevHashL] = tableEntry{offset: o}
   188  		cv = x >> 8
   189  	}
   190  
   191  emitRemainder:
   192  	if int(nextEmit) < len(src) {
   193  		// If nothing was added, don't encode literals.
   194  		if dst.n == 0 {
   195  			return
   196  		}
   197  
   198  		emitLiterals(dst, src[nextEmit:])
   199  	}
   200  }
   201
View as plain text