level1.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 1 uses a single small table with 5 byte hashes.
     8  type fastEncL1 struct {
     9  	fastGen
    10  	table [tableSize]tableEntry
    11  }
    12  
    13  func (e *fastEncL1) encode(dst *tokens, src []byte) {
    14  	const (
    15  		inputMargin            = 12 - 1
    16  		minNonLiteralBlockSize = 1 + 1 + inputMargin
    17  		hashBytes              = 5
    18  	)
    19  
    20  	// Protect against e.cur wraparound.
    21  	for e.cur >= bufferReset {
    22  		if len(e.hist) == 0 {
    23  			clear(e.table[:])
    24  			e.cur = maxMatchOffset
    25  			break
    26  		}
    27  		// Shift down everything in the table that isn't already too far away.
    28  		minOff := e.cur + int32(len(e.hist)) - maxMatchOffset
    29  		for i := range e.table[:] {
    30  			v := e.table[i].offset
    31  			if v <= minOff {
    32  				v = 0
    33  			} else {
    34  				v = v - e.cur + maxMatchOffset
    35  			}
    36  			e.table[i].offset = v
    37  		}
    38  		e.cur = maxMatchOffset
    39  	}
    40  
    41  	s := e.addBlock(src)
    42  
    43  	if len(src) < minNonLiteralBlockSize {
    44  		// We do not fill the token table.
    45  		// This will be picked up by caller.
    46  		dst.n = uint16(len(src))
    47  		return
    48  	}
    49  
    50  	// Override src
    51  	src = e.hist
    52  
    53  	// nextEmit is where in src the next emitLiterals should start from.
    54  	nextEmit := s
    55  
    56  	// sLimit is when to stop looking for offset/length copies. The inputMargin
    57  	// lets us use a fast path for emitLiterals in the main loop, while we are
    58  	// looking for copies.
    59  	sLimit := int32(len(src) - inputMargin)
    60  
    61  	cv := loadLE64(src, s)
    62  
    63  	for {
    64  		const skipLog = 5
    65  		const doEvery = 2
    66  
    67  		nextS := s
    68  		var candidate tableEntry
    69  		var t int32
    70  		for {
    71  			nextHash := hashLen(cv, tableBits, hashBytes)
    72  			candidate = e.table[nextHash]
    73  			nextS = s + doEvery + (s-nextEmit)>>skipLog
    74  			if nextS > sLimit {
    75  				goto emitRemainder
    76  			}
    77  
    78  			now := loadLE64(src, nextS)
    79  			e.table[nextHash] = tableEntry{offset: s + e.cur}
    80  			nextHash = hashLen(now, tableBits, hashBytes)
    81  			t = candidate.offset - e.cur
    82  			if s-t < maxMatchOffset && uint32(cv) == loadLE32(src, t) {
    83  				e.table[nextHash] = tableEntry{offset: nextS + e.cur}
    84  				break
    85  			}
    86  
    87  			// Do one right away...
    88  			cv = now
    89  			s = nextS
    90  			nextS++
    91  			candidate = e.table[nextHash]
    92  			now >>= 8
    93  			e.table[nextHash] = tableEntry{offset: s + e.cur}
    94  
    95  			t = candidate.offset - e.cur
    96  			if s-t < maxMatchOffset && uint32(cv) == loadLE32(src, t) {
    97  				e.table[nextHash] = tableEntry{offset: nextS + e.cur}
    98  				break
    99  			}
   100  			cv = now
   101  			s = nextS
   102  		}
   103  
   104  		// A 4-byte match has been found. We'll later see if more than 4 bytes
   105  		// match. But, prior to the match, src[nextEmit:s] are unmatched. Emit
   106  		// them as literal bytes.
   107  		for {
   108  			// Invariant: we have a 4-byte match at s, and no need to emit any
   109  			// literal bytes prior to s.
   110  
   111  			// Extend the 4-byte match as long as possible.
   112  			l := e.matchLenLong(int(s+4), int(t+4), src) + 4
   113  
   114  			// Extend backwards
   115  			for t > 0 && s > nextEmit && loadLE8(src, t-1) == loadLE8(src, s-1) {
   116  				s--
   117  				t--
   118  				l++
   119  			}
   120  			if nextEmit < s {
   121  				for _, v := range src[nextEmit:s] {
   122  					dst.tokens[dst.n] = token(v)
   123  					dst.litHist[v]++
   124  					dst.n++
   125  				}
   126  			}
   127  
   128  			// Save the match found. Same as 'dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))'
   129  			xOffset := uint32(s - t - baseMatchOffset)
   130  			xLength := l
   131  			oc := offsetCode(xOffset)
   132  			xOffset |= oc << 16
   133  			for xLength > 0 {
   134  				xl := xLength
   135  				if xl > 258 {
   136  					if xl > 258+baseMatchLength {
   137  						xl = 258
   138  					} else {
   139  						xl = 258 - baseMatchLength
   140  					}
   141  				}
   142  				xLength -= xl
   143  				xl -= baseMatchLength
   144  				dst.extraHist[lengthCodes1[uint8(xl)]]++
   145  				dst.offHist[oc]++
   146  				dst.tokens[dst.n] = token(matchType | uint32(xl)<<lengthShift | xOffset)
   147  				dst.n++
   148  			}
   149  			s += l
   150  			nextEmit = s
   151  			if nextS >= s {
   152  				s = nextS + 1
   153  			}
   154  			if s >= sLimit {
   155  				// Index first pair after match end.
   156  				if int(s+l+8) < len(src) {
   157  					cv := loadLE64(src, s)
   158  					e.table[hashLen(cv, tableBits, hashBytes)] = tableEntry{offset: s + e.cur}
   159  				}
   160  				goto emitRemainder
   161  			}
   162  
   163  			// We could immediately start working at s now, but to improve
   164  			// compression we first update the hash table at s-2 and at s. If
   165  			// another emitCopy is not our next move, also calculate nextHash
   166  			// at s+1. At least on GOARCH=amd64, these three hash calculations
   167  			// are faster as one load64 call (with some shifts) instead of
   168  			// three load32 calls.
   169  			x := loadLE64(src, s-2)
   170  			o := e.cur + s - 2
   171  			prevHash := hashLen(x, tableBits, hashBytes)
   172  			e.table[prevHash] = tableEntry{offset: o}
   173  			x >>= 16
   174  			currHash := hashLen(x, tableBits, hashBytes)
   175  			candidate = e.table[currHash]
   176  			e.table[currHash] = tableEntry{offset: o + 2}
   177  
   178  			t = candidate.offset - e.cur
   179  			if s-t > maxMatchOffset || uint32(x) != loadLE32(src, t) {
   180  				cv = x >> 8
   181  				s++
   182  				break
   183  			}
   184  		}
   185  	}
   186  
   187  emitRemainder:
   188  	if int(nextEmit) < len(src) {
   189  		// If nothing was added, don't encode literals.
   190  		if dst.n == 0 {
   191  			return
   192  		}
   193  		emitLiterals(dst, src[nextEmit:])
   194  	}
   195  }
   196
View as plain text