level5.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 5 is similar to level 4, but for long matches two candidates are tested.
     8  // Once a match is found, when it stops it will attempt to find a match that extends further.
     9  type fastEncL5 struct {
    10  	fastGen
    11  	table  [tableSize]tableEntry
    12  	bTable [tableSize]tableEntryPrev
    13  }
    14  
    15  func (e *fastEncL5) encode(dst *tokens, src []byte) {
    16  	const (
    17  		inputMargin            = 12 - 1
    18  		minNonLiteralBlockSize = 1 + 1 + inputMargin
    19  		hashShortBytes         = 4
    20  	)
    21  
    22  	// Protect against e.cur wraparound.
    23  	for e.cur >= bufferReset {
    24  		if len(e.hist) == 0 {
    25  			clear(e.table[:])
    26  			clear(e.bTable[:])
    27  			e.cur = maxMatchOffset
    28  			break
    29  		}
    30  		// Shift down everything in the table that isn't already too far away.
    31  		minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
    32  		for i := range e.table[:] {
    33  			v := e.table[i].offset
    34  			if v <= minOff {
    35  				v = 0
    36  			} else {
    37  				v = v - e.cur + maxMatchOffset
    38  			}
    39  			e.table[i].offset = v
    40  		}
    41  		for i := range e.bTable[:] {
    42  			v := e.bTable[i]
    43  			if v.cur.offset <= minOff {
    44  				v.cur.offset = 0
    45  				v.prev.offset = 0
    46  			} else {
    47  				v.cur.offset = v.cur.offset - e.cur + maxMatchOffset
    48  				if v.prev.offset <= minOff {
    49  					v.prev.offset = 0
    50  				} else {
    51  					v.prev.offset = v.prev.offset - e.cur + maxMatchOffset
    52  				}
    53  			}
    54  			e.bTable[i] = v
    55  		}
    56  		e.cur = maxMatchOffset
    57  	}
    58  
    59  	s := e.addBlock(src)
    60  
    61  	// This check isn't in the Snappy implementation, but there, the caller
    62  	// instead of the callee handles this case.
    63  	if len(src) < minNonLiteralBlockSize {
    64  		// We do not fill the token table.
    65  		// This will be picked up by caller.
    66  		dst.n = uint16(len(src))
    67  		return
    68  	}
    69  
    70  	// Override src
    71  	src = e.hist
    72  
    73  	// nextEmit is where in src the next emitLiterals should start from.
    74  	nextEmit := s
    75  
    76  	// sLimit is when to stop looking for offset/length copies. The inputMargin
    77  	// lets us use a fast path for emitLiterals in the main loop, while we are
    78  	// looking for copies.
    79  	sLimit := int32(len(src) - inputMargin)
    80  
    81  	cv := loadLE64(src, s)
    82  	for {
    83  		const skipLog = 6
    84  		const doEvery = 1
    85  
    86  		nextS := s
    87  		var l int32
    88  		var t int32
    89  		for {
    90  			nextHashS := hashLen(cv, tableBits, hashShortBytes)
    91  			nextHashL := hashLen(cv, tableBits, hashLongBytes)
    92  
    93  			s = nextS
    94  			nextS = s + doEvery + (s-nextEmit)>>skipLog
    95  			if nextS > sLimit {
    96  				goto emitRemainder
    97  			}
    98  			// Fetch a short+long candidate
    99  			sCandidate := e.table[nextHashS]
   100  			lCandidate := e.bTable[nextHashL]
   101  			next := loadLE64(src, nextS)
   102  			entry := tableEntry{offset: s + e.cur}
   103  			e.table[nextHashS] = entry
   104  			eLong := &e.bTable[nextHashL]
   105  			eLong.cur, eLong.prev = entry, eLong.cur
   106  
   107  			nextHashS = hashLen(next, tableBits, hashShortBytes)
   108  			nextHashL = hashLen(next, tableBits, hashLongBytes)
   109  
   110  			t = lCandidate.cur.offset - e.cur
   111  			if s-t < maxMatchOffset {
   112  				if uint32(cv) == loadLE32(src, t) {
   113  					// Store the next match
   114  					e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
   115  					eLong := &e.bTable[nextHashL]
   116  					eLong.cur, eLong.prev = tableEntry{offset: nextS + e.cur}, eLong.cur
   117  
   118  					t2 := lCandidate.prev.offset - e.cur
   119  					if s-t2 < maxMatchOffset && uint32(cv) == loadLE32(src, t2) {
   120  						l = e.matchLenLimited(int(s+4), int(t+4), src) + 4
   121  						ml1 := e.matchLenLimited(int(s+4), int(t2+4), src) + 4
   122  						if ml1 > l {
   123  							t = t2
   124  							l = ml1
   125  							break
   126  						}
   127  					}
   128  					break
   129  				}
   130  				t = lCandidate.prev.offset - e.cur
   131  				if s-t < maxMatchOffset && uint32(cv) == loadLE32(src, t) {
   132  					// Store the next match
   133  					e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
   134  					eLong := &e.bTable[nextHashL]
   135  					eLong.cur, eLong.prev = tableEntry{offset: nextS + e.cur}, eLong.cur
   136  					break
   137  				}
   138  			}
   139  
   140  			t = sCandidate.offset - e.cur
   141  			if s-t < maxMatchOffset && uint32(cv) == loadLE32(src, t) {
   142  				// Found a 4 match...
   143  				l = e.matchLenLimited(int(s+4), int(t+4), src) + 4
   144  				lCandidate = e.bTable[nextHashL]
   145  				// Store the next match
   146  
   147  				e.table[nextHashS] = tableEntry{offset: nextS + e.cur}
   148  				eLong := &e.bTable[nextHashL]
   149  				eLong.cur, eLong.prev = tableEntry{offset: nextS + e.cur}, eLong.cur
   150  
   151  				// If the next long is a candidate, use that...
   152  				t2 := lCandidate.cur.offset - e.cur
   153  				if nextS-t2 < maxMatchOffset {
   154  					if loadLE32(src, t2) == uint32(next) {
   155  						ml := e.matchLenLimited(int(nextS+4), int(t2+4), src) + 4
   156  						if ml > l {
   157  							t = t2
   158  							s = nextS
   159  							l = ml
   160  							break
   161  						}
   162  					}
   163  					// If the previous long is a candidate, use that...
   164  					t2 = lCandidate.prev.offset - e.cur
   165  					if nextS-t2 < maxMatchOffset && loadLE32(src, t2) == uint32(next) {
   166  						ml := e.matchLenLimited(int(nextS+4), int(t2+4), src) + 4
   167  						if ml > l {
   168  							t = t2
   169  							s = nextS
   170  							l = ml
   171  							break
   172  						}
   173  					}
   174  				}
   175  				break
   176  			}
   177  			cv = next
   178  		}
   179  
   180  		if l == 0 {
   181  			// Extend the 4-byte match as long as possible.
   182  			l = e.matchLenLong(int(s+4), int(t+4), src) + 4
   183  		} else if l == maxMatchLength {
   184  			l += e.matchLenLong(int(s+l), int(t+l), src)
   185  		}
   186  
   187  		// Try to locate a better match by checking the end of best match...
   188  		if sAt := s + l; l < 30 && sAt < sLimit {
   189  			// Allow some bytes at the beginning to mismatch.
   190  			// Sweet spot is 2/3 bytes depending on input.
   191  			// 3 is only a little better when it is but sometimes a lot worse.
   192  			// The skipped bytes are tested in Extend backwards,
   193  			// and still picked up as part of the match if they do.
   194  			const skipBeginning = 2
   195  			eLong := e.bTable[hashLen(loadLE64(src, sAt), tableBits, hashLongBytes)].cur.offset
   196  			t2 := eLong - e.cur - l + skipBeginning
   197  			s2 := s + skipBeginning
   198  			off := s2 - t2
   199  			if t2 >= 0 && off < maxMatchOffset && off > 0 {
   200  				if l2 := e.matchLenLong(int(s2), int(t2), src); l2 > l {
   201  					t = t2
   202  					l = l2
   203  					s = s2
   204  				}
   205  			}
   206  		}
   207  
   208  		// Extend backwards
   209  		for t > 0 && s > nextEmit && src[t-1] == src[s-1] {
   210  			s--
   211  			t--
   212  			l++
   213  		}
   214  		if nextEmit < s {
   215  			for _, v := range src[nextEmit:s] {
   216  				dst.tokens[dst.n] = token(v)
   217  				dst.litHist[v]++
   218  				dst.n++
   219  			}
   220  		}
   221  
   222  		dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
   223  		s += l
   224  		nextEmit = s
   225  		if nextS >= s {
   226  			s = nextS + 1
   227  		}
   228  
   229  		if s >= sLimit {
   230  			goto emitRemainder
   231  		}
   232  
   233  		// Store every 3rd hash in-between.
   234  		const hashEvery = 3
   235  		i := s - l + 1
   236  		if i < s-1 {
   237  			cv := loadLE64(src, i)
   238  			t := tableEntry{offset: i + e.cur}
   239  			e.table[hashLen(cv, tableBits, hashShortBytes)] = t
   240  			eLong := &e.bTable[hashLen(cv, tableBits, hashLongBytes)]
   241  			eLong.cur, eLong.prev = t, eLong.cur
   242  
   243  			// Do an long at i+1
   244  			cv >>= 8
   245  			t = tableEntry{offset: t.offset + 1}
   246  			eLong = &e.bTable[hashLen(cv, tableBits, hashLongBytes)]
   247  			eLong.cur, eLong.prev = t, eLong.cur
   248  
   249  			// We only have enough bits for a short entry at i+2
   250  			cv >>= 8
   251  			t = tableEntry{offset: t.offset + 1}
   252  			e.table[hashLen(cv, tableBits, hashShortBytes)] = t
   253  
   254  			// Skip one - otherwise we risk hitting 's'
   255  			i += 4
   256  			for ; i < s-1; i += hashEvery {
   257  				cv := loadLE64(src, i)
   258  				t := tableEntry{offset: i + e.cur}
   259  				t2 := tableEntry{offset: t.offset + 1}
   260  				eLong := &e.bTable[hashLen(cv, tableBits, hashLongBytes)]
   261  				eLong.cur, eLong.prev = t, eLong.cur
   262  				e.table[hashLen(cv>>8, tableBits, hashShortBytes)] = t2
   263  			}
   264  		}
   265  
   266  		// We could immediately start working at s now, but to improve
   267  		// compression we first update the hash table at s-1 and at s.
   268  		x := loadLE64(src, s-1)
   269  		o := e.cur + s - 1
   270  		prevHashS := hashLen(x, tableBits, hashShortBytes)
   271  		prevHashL := hashLen(x, tableBits, hashLongBytes)
   272  		e.table[prevHashS] = tableEntry{offset: o}
   273  		eLong := &e.bTable[prevHashL]
   274  		eLong.cur, eLong.prev = tableEntry{offset: o}, eLong.cur
   275  		cv = x >> 8
   276  	}
   277  
   278  emitRemainder:
   279  	if int(nextEmit) < len(src) {
   280  		// If nothing was added, don't encode literals.
   281  		if dst.n == 0 {
   282  			return
   283  		}
   284  
   285  		emitLiterals(dst, src[nextEmit:])
   286  	}
   287  }
   288
View as plain text