Source file src/compress/flate/deflate.go

     1  // Copyright 2009 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  import (
     8  	"errors"
     9  	"fmt"
    10  	"io"
    11  	"math"
    12  	"slices"
    13  )
    14  
    15  const (
    16  	NoCompression      = 0
    17  	BestSpeed          = 1
    18  	BestCompression    = 9
    19  	DefaultCompression = -1
    20  
    21  	// HuffmanOnly disables Lempel-Ziv match searching and only performs Huffman
    22  	// entropy encoding. This mode is useful in compressing data that has
    23  	// already been compressed with an LZ style algorithm (e.g. Snappy or LZ4)
    24  	// that lacks an entropy encoder. Compression gains are achieved when
    25  	// certain bytes in the input stream occur more frequently than others.
    26  	//
    27  	// Note that HuffmanOnly produces a compressed output that is
    28  	// RFC 1951 compliant. That is, any valid DEFLATE decompressor will
    29  	// continue to be able to decompress this output.
    30  	HuffmanOnly = -2
    31  )
    32  
    33  const (
    34  	logWindowSize  = 15
    35  	windowSize     = 1 << logWindowSize
    36  	windowMask     = windowSize - 1
    37  	minMatchLength = 4   // The smallest match that the compressor looks for
    38  	maxMatchLength = 258 // The longest match for the compressor
    39  	minOffsetSize  = 1   // The shortest offset that makes any sense
    40  
    41  	// The maximum number of tokens we will encode at the time.
    42  	// Smaller sizes usually creates less optimal blocks.
    43  	// Bigger can make context switching slow.
    44  	// We use this for levels 7-9, so we make it big.
    45  	maxFlateBlockTokens = 1 << 15
    46  	maxStoreBlockSize   = 65535
    47  	hashBits            = 17 // After 17 performance degrades
    48  	hashSize            = 1 << hashBits
    49  	hashMask            = (1 << hashBits) - 1
    50  	maxHashOffset       = 1 << 28
    51  
    52  	skipNever = math.MaxInt32
    53  )
    54  
    55  // compressionLevel holds the parameters for levels 7-9.
    56  type compressionLevel struct {
    57  	good  int32 // "good enough" match length
    58  	lazy  int32 // don't try to find a later, better match above this length
    59  	nice  int32 // stop looking for a better match above this length
    60  	chain int32 // maximum number of hash chain entries to search
    61  	level int
    62  }
    63  
    64  var levels = []compressionLevel{
    65  	{}, // 0
    66  	// Level 1-6 uses specialized algorithm - values not used
    67  	{0, 0, 0, 0, 1},
    68  	{0, 0, 0, 0, 2},
    69  	{0, 0, 0, 0, 3},
    70  	{0, 0, 0, 0, 4},
    71  	{0, 0, 0, 0, 5},
    72  	{0, 0, 0, 0, 6},
    73  	// Levels 7-9 use increasingly more lazy matching
    74  	// and increasingly stringent conditions for "good enough".
    75  	{8, 12, 16, 24, 7},
    76  	{16, 30, 40, 64, 8},
    77  	{32, 258, 258, 1024, 9},
    78  }
    79  
    80  // advancedState contains state for levels 7-9, with bigger hash tables, etc.
    81  type advancedState struct {
    82  	// deflate state
    83  	length         int32
    84  	offset         int32
    85  	maxInsertIndex int32
    86  	chainHead      int32
    87  	hashOffset     int32
    88  
    89  	literalCounter uint16 // consecutive literal count; overflows to reset after 64KB.
    90  
    91  	// input window: unprocessed data is window[index:windowEnd]
    92  	index     int32
    93  	hashMatch [maxMatchLength + minMatchLength]uint32
    94  
    95  	// Input hash chains
    96  	// hashHead[hashValue] contains the largest inputIndex with the specified hash value
    97  	// If hashHead[hashValue] is within the current window, then
    98  	// hashPrev[hashHead[hashValue] & windowMask] contains the previous index
    99  	// with the same hash value.
   100  	hashHead [hashSize]int32
   101  	hashPrev [windowSize]int32
   102  }
   103  
   104  type compressor struct {
   105  	compressionLevel
   106  
   107  	h *huffmanEncoder   // huffman encoder, with state
   108  	w *huffmanBitWriter // writer for blocks
   109  
   110  	// compression algorithm
   111  	fill func(*compressor, []byte) int // copy data to window
   112  	step func(*compressor)             // process window
   113  
   114  	window     []byte // current window - size depends on encoder level
   115  	windowEnd  int32  // filled bytes in window
   116  	blockStart int32  // window index where current tokens start
   117  	err        error  // stateful error
   118  
   119  	// queued output tokens
   120  	tokens tokens         // tokens store for each block
   121  	fast   fastEnc        // encoder to use for blocks
   122  	state  *advancedState // chained encoder for level 7-9
   123  
   124  	sync          bool // requesting flush
   125  	byteAvailable bool // if true, still need to process window[index-1].
   126  }
   127  
   128  // fillDeflate will add b to the current window for levels 7-9.
   129  func (d *compressor) fillDeflate(b []byte) int {
   130  	s := d.state
   131  	if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
   132  		// shift the window by windowSize
   133  		copy(d.window[:], d.window[windowSize:2*windowSize])
   134  		s.index -= windowSize
   135  		d.windowEnd -= windowSize
   136  		if d.blockStart >= windowSize {
   137  			d.blockStart -= windowSize
   138  		} else {
   139  			d.blockStart = math.MaxInt32
   140  		}
   141  		s.hashOffset += windowSize
   142  		if s.hashOffset > maxHashOffset {
   143  			delta := s.hashOffset - 1
   144  			s.hashOffset -= delta
   145  			s.chainHead -= delta
   146  			// Note: range over &array to avoid copy (see go.dev/issue/18625).
   147  			for i, v := range &s.hashPrev {
   148  				s.hashPrev[i] = max(v-delta, 0)
   149  			}
   150  			for i, v := range &s.hashHead {
   151  				s.hashHead[i] = max(v-delta, 0)
   152  			}
   153  		}
   154  	}
   155  	n := copy(d.window[d.windowEnd:], b)
   156  	d.windowEnd += int32(n)
   157  	return n
   158  }
   159  
   160  // writeBlock will write tokens to output.
   161  // The provided index is where the block starts in d.window.
   162  func (d *compressor) writeBlock(tok *tokens, index int32, eof bool) error {
   163  	if index > 0 || eof {
   164  		var window []byte
   165  		if d.blockStart <= index {
   166  			window = d.window[d.blockStart:index]
   167  		}
   168  		d.blockStart = index
   169  		d.w.writeBlockDynamic(tok, eof, window, d.sync)
   170  		return d.w.err
   171  	}
   172  	return nil
   173  }
   174  
   175  // writeBlockSkip writes the current block and uses the number of tokens
   176  // to determine if the block should be stored when there are no matches, or
   177  // only Huffman encoded.
   178  func (d *compressor) writeBlockSkip(tok *tokens, index int32, eof bool) error {
   179  	if index > 0 || eof {
   180  		if d.blockStart <= index {
   181  			window := d.window[d.blockStart:index]
   182  			// If we removed less than a 64th of all literals
   183  			// we huffman compress the block.
   184  			if int(tok.n) > len(window)-(len(window)>>6) {
   185  				d.w.writeBlockHuff(eof, window, d.sync)
   186  			} else {
   187  				// Write a dynamic huffman block.
   188  				d.w.writeBlockDynamic(tok, eof, window, d.sync)
   189  			}
   190  		} else {
   191  			d.w.writeBlock(tok, eof, nil)
   192  		}
   193  		d.blockStart = index
   194  		return d.w.err
   195  	}
   196  	return nil
   197  }
   198  
   199  // fillWindow will fill the current window with the supplied
   200  // dictionary and calculate all hashes.
   201  // This is much faster than doing a full encode.
   202  // Should only be used after a start/reset.
   203  func (d *compressor) fillWindow(b []byte) {
   204  	// Do not fill window if we are in store-only or huffman mode.
   205  	if d.level <= 0 {
   206  		return
   207  	}
   208  	if d.fast != nil {
   209  		// encode the last data, but discard the result
   210  		if len(b) > maxMatchOffset {
   211  			b = b[len(b)-maxMatchOffset:]
   212  		}
   213  		d.fast.encode(&d.tokens, b)
   214  		d.tokens.Reset()
   215  		return
   216  	}
   217  	s := d.state
   218  	// If we are given too much, cut it.
   219  	if len(b) > windowSize {
   220  		b = b[len(b)-windowSize:]
   221  	}
   222  	// Add all to window.
   223  	n := int32(copy(d.window[d.windowEnd:], b))
   224  
   225  	// Calculate 256 hashes at the time (more L1 cache hits)
   226  	loops := (n + 256 - minMatchLength) / 256
   227  	for j := range loops {
   228  		startindex := j * 256
   229  		end := min(startindex+256+minMatchLength-1, n)
   230  		tocheck := d.window[startindex:end]
   231  		dstSize := len(tocheck) - minMatchLength + 1
   232  
   233  		if dstSize <= 0 {
   234  			continue
   235  		}
   236  
   237  		dst := s.hashMatch[:dstSize]
   238  		bulkHash4(tocheck, dst)
   239  		var newH uint32
   240  		for i, val := range dst {
   241  			di := int32(i) + startindex
   242  			newH = val & hashMask
   243  			// Get previous value with the same hash.
   244  			// Our chain should point to the previous value.
   245  			s.hashPrev[di&windowMask] = s.hashHead[newH]
   246  			// Set the head of the hash chain to us.
   247  			s.hashHead[newH] = di + s.hashOffset
   248  		}
   249  	}
   250  	// Update window information.
   251  	d.windowEnd += n
   252  	s.index = n
   253  	d.blockStart = d.windowEnd
   254  }
   255  
   256  // findMatch finds the longest match starting at pos in the hash chain starting
   257  // at prevHead. It searches up to d.chain entries in the chain.
   258  func (d *compressor) findMatch(pos int32, prevHead int32, lookahead int32) (length, offset int32, ok bool) {
   259  	minMatchLook := min(lookahead, maxMatchLength)
   260  
   261  	win := d.window[0 : pos+minMatchLook]
   262  
   263  	// We quit when we get a match that's at least nice long
   264  	nice := min(d.nice, int32(len(win))-pos)
   265  
   266  	// If we've got a match that's good enough, only look in 1/4 the chain.
   267  	tries := d.chain
   268  	length = minMatchLength - 1
   269  
   270  	wEnd := win[pos+length]
   271  	wPos := win[pos:]
   272  	minIndex := max(pos-windowSize, 0)
   273  	offset = 0
   274  
   275  	// Minimum gain to accept a match.
   276  	cGain := 4
   277  
   278  	// Some like it higher (CSV), some like it lower (JSON)
   279  	const baseCost = 3
   280  	// Base is 4 bytes at with an additional cost.
   281  	// Matches must be better than this.
   282  
   283  	for i := prevHead; tries > 0; tries-- {
   284  		if wEnd == win[i+length] {
   285  			n := int32(matchLen(win[i:i+minMatchLook], wPos))
   286  			if n > length {
   287  				if d.chain >= 100 {
   288  					// Calculate gain. Estimates the gains of the new match compared to emitting as literals.
   289  					newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
   290  					if newGain <= cGain {
   291  						goto next
   292  					}
   293  					cGain = newGain
   294  				}
   295  				length = n
   296  				offset = pos - i
   297  				ok = true
   298  				if n >= nice {
   299  					// The match is good enough that we don't try to find a better one.
   300  					break
   301  				}
   302  				wEnd = win[pos+n]
   303  			}
   304  		}
   305  	next:
   306  		if i <= minIndex {
   307  			// hashPrev[i & windowMask] has already been overwritten, so stop now.
   308  			break
   309  		}
   310  		i = d.state.hashPrev[i&windowMask] - d.state.hashOffset
   311  		if i < minIndex {
   312  			break
   313  		}
   314  	}
   315  	return
   316  }
   317  
   318  // writeStoredBlock writes an uncompressed block to the stream.
   319  func (d *compressor) writeStoredBlock(buf []byte) error {
   320  	if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
   321  		return d.w.err
   322  	}
   323  	d.w.writeBytes(buf)
   324  	return d.w.err
   325  }
   326  
   327  // hash4 returns a hash representation of the first 4 bytes
   328  // of the supplied slice.
   329  // The caller must ensure that len(b) >= 4.
   330  func hash4(b []byte) uint32 {
   331  	return hash4u(loadLE32(b, 0), hashBits)
   332  }
   333  
   334  // hash4 returns the hash of u to fit in a hash table with h bits.
   335  // Preferably h should be a constant and should always be <32.
   336  func hash4u(u uint32, h uint8) uint32 {
   337  	return (u * prime4bytes) >> (32 - h)
   338  }
   339  
   340  // bulkHash4 sets dst[i] = hash4(b[i:i+4]) for all i <= len(b)-4.
   341  func bulkHash4(b []byte, dst []uint32) {
   342  	if len(b) < 4 {
   343  		return
   344  	}
   345  	hb := loadLE32(b, 0)
   346  
   347  	dst[0] = hash4u(hb, hashBits)
   348  	end := len(b) - 4 + 1
   349  	for i := 1; i < end; i++ {
   350  		hb = (hb >> 8) | uint32(b[i+3])<<24
   351  		dst[i] = hash4u(hb, hashBits)
   352  	}
   353  }
   354  
   355  // initDeflate initializes d for levels 7-9.
   356  func (d *compressor) initDeflate() {
   357  	d.window = make([]byte, 2*windowSize)
   358  	d.byteAvailable = false
   359  	d.err = nil
   360  	if d.state == nil {
   361  		return
   362  	}
   363  	s := d.state
   364  	s.index = 0
   365  	s.hashOffset = 1
   366  	s.length = minMatchLength - 1
   367  	s.offset = 0
   368  	s.chainHead = -1
   369  }
   370  
   371  // tryBetterMatchAtEnd checks whether a better match exists at the end of the
   372  // previous match and, if so, emits the skipped literals and adjusts the match.
   373  // Returns the (possibly updated) prevLength and prevOffset.
   374  func (d *compressor) tryBetterMatchAtEnd(prevLength, prevOffset, lookahead int32) (newLen, newOff int32) {
   375  	// We start checking at checkOff from the current match position.
   376  	// This allows up to two additional literals, but that could be
   377  	// compensated by a higher quality match.
   378  	// If the match looks better, we extend backwards.
   379  	const checkOff = 2
   380  	s := d.state
   381  
   382  	if prevLength >= maxMatchLength-checkOff {
   383  		return prevLength, prevOffset
   384  	}
   385  	prevIndex := s.index - 1
   386  	if prevIndex+prevLength >= s.maxInsertIndex {
   387  		return prevLength, prevOffset
   388  	}
   389  
   390  	end := min(lookahead, maxMatchLength+checkOff) + prevIndex
   391  	minIndex := max(s.index-windowSize, 0)
   392  
   393  	h := hash4(d.window[prevIndex+prevLength:])
   394  	ch2 := s.hashHead[h] - s.hashOffset - prevLength
   395  	if prevIndex-ch2 == prevOffset || ch2 <= minIndex+checkOff {
   396  		return prevLength, prevOffset
   397  	}
   398  
   399  	length := int32(matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:]))
   400  	if length <= prevLength {
   401  		return prevLength, prevOffset
   402  	}
   403  
   404  	prevLength = length
   405  	prevOffset = prevIndex - ch2
   406  
   407  	for i := int32(checkOff - 1); i >= 0; i-- {
   408  		if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i] {
   409  			for j := range i + 1 {
   410  				d.tokens.AddLiteral(d.window[prevIndex+j])
   411  				if d.tokens.n == maxFlateBlockTokens {
   412  					if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   413  						return prevLength, prevOffset
   414  					}
   415  					d.tokens.Reset()
   416  				}
   417  				s.index++
   418  				if s.index < s.maxInsertIndex {
   419  					h := hash4(d.window[s.index:])
   420  					ch := s.hashHead[h]
   421  					s.chainHead = ch
   422  					s.hashPrev[s.index&windowMask] = ch
   423  					s.hashHead[h] = s.index + s.hashOffset
   424  				}
   425  			}
   426  			break
   427  		}
   428  		prevLength++
   429  	}
   430  	return prevLength, prevOffset
   431  }
   432  
   433  // skipLiterals emits extra literal bytes during long runs of incompressible data,
   434  // skipping ahead to avoid futile match searches. Returns false on write error.
   435  func (d *compressor) skipLiterals() bool {
   436  	s := d.state
   437  	n := int32(s.literalCounter) - d.chain
   438  	if n <= 0 {
   439  		return true
   440  	}
   441  	n = 1 + n>>6
   442  	for range n {
   443  		if s.index >= d.windowEnd-1 {
   444  			break
   445  		}
   446  		d.tokens.AddLiteral(d.window[s.index-1])
   447  		if d.tokens.n == maxFlateBlockTokens {
   448  			if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   449  				return false
   450  			}
   451  			d.tokens.Reset()
   452  		}
   453  		if s.index < s.maxInsertIndex {
   454  			h := hash4(d.window[s.index:])
   455  			ch := s.hashHead[h]
   456  			s.chainHead = ch
   457  			s.hashPrev[s.index&windowMask] = ch
   458  			s.hashHead[h] = s.index + s.hashOffset
   459  		}
   460  		s.index++
   461  	}
   462  	d.tokens.AddLiteral(d.window[s.index-1])
   463  	d.byteAvailable = false
   464  	if d.tokens.n == maxFlateBlockTokens {
   465  		if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   466  			return false
   467  		}
   468  		d.tokens.Reset()
   469  	}
   470  	return true
   471  }
   472  
   473  // deflateLazy encodes the current window using lazy matching.
   474  // Lazy matching defers emitting a match to see if the next position yields a better one.
   475  // Unique to levels 7-9 is that more than 2 matches are potentially checked
   476  // until a good/nice one is found.
   477  func (d *compressor) deflateLazy() {
   478  	s := d.state
   479  
   480  	if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
   481  		return
   482  	}
   483  	if d.windowEnd != s.index && d.chain > 100 {
   484  		// Get literal huffman coder.
   485  		// This is used to estimate the cost of emitting a literal.
   486  		if d.h == nil {
   487  			d.h = newHuffmanEncoder(maxFlateBlockTokens)
   488  		}
   489  		var tmp [256]uint16
   490  		toIndex := d.window[s.index:d.windowEnd]
   491  		toIndex = toIndex[:min(len(toIndex), maxFlateBlockTokens)]
   492  		for _, v := range toIndex {
   493  			tmp[v]++
   494  		}
   495  		d.h.generate(tmp[:], 15)
   496  	}
   497  
   498  	s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
   499  
   500  	for {
   501  		lookahead := d.windowEnd - s.index
   502  		if lookahead < minMatchLength+maxMatchLength {
   503  			if !d.sync {
   504  				return
   505  			}
   506  			if lookahead == 0 {
   507  				// Flush current output block if any.
   508  				if d.byteAvailable {
   509  					// There is still one pending token that needs to be flushed
   510  					d.tokens.AddLiteral(d.window[s.index-1])
   511  					d.byteAvailable = false
   512  				}
   513  				if d.tokens.n > 0 {
   514  					if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   515  						return
   516  					}
   517  					d.tokens.Reset()
   518  				}
   519  				return
   520  			}
   521  		}
   522  		if s.index < s.maxInsertIndex {
   523  			h := hash4(d.window[s.index:])
   524  			ch := s.hashHead[h]
   525  			s.chainHead = ch
   526  			s.hashPrev[s.index&windowMask] = ch
   527  			s.hashHead[h] = s.index + s.hashOffset
   528  		}
   529  		prevLength := s.length
   530  		prevOffset := s.offset
   531  		s.length = minMatchLength - 1
   532  		s.offset = 0
   533  		minIndex := max(s.index-windowSize, 0)
   534  
   535  		if s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
   536  			if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, lookahead); ok {
   537  				s.length = newLength
   538  				s.offset = newOffset
   539  			}
   540  		}
   541  
   542  		if prevLength >= minMatchLength && s.length <= prevLength {
   543  			prevLength, prevOffset = d.tryBetterMatchAtEnd(prevLength, prevOffset, lookahead)
   544  			if d.err != nil {
   545  				return
   546  			}
   547  
   548  			// There was a match at the previous step, and the current match is
   549  			// not better. Output the previous match.
   550  			d.tokens.AddMatch(uint32(prevLength-3), uint32(prevOffset-minOffsetSize))
   551  
   552  			// Insert in the hash table all strings up to the end of the match.
   553  			// index and index-1 are already inserted. If there is not enough
   554  			// lookahead, the last two strings are not inserted into the hash
   555  			// table.
   556  			newIndex := s.index + prevLength - 1
   557  			end := min(newIndex, s.maxInsertIndex)
   558  			end += minMatchLength - 1
   559  			startindex := min(s.index+1, s.maxInsertIndex)
   560  			tocheck := d.window[startindex:end]
   561  			dstSize := len(tocheck) - minMatchLength + 1
   562  			if dstSize > 0 {
   563  				dst := s.hashMatch[:dstSize]
   564  				bulkHash4(tocheck, dst)
   565  				var newH uint32
   566  				for i, val := range dst {
   567  					di := int32(i) + startindex
   568  					newH = val & hashMask
   569  					s.hashPrev[di&windowMask] = s.hashHead[newH]
   570  					s.hashHead[newH] = di + s.hashOffset
   571  				}
   572  			}
   573  
   574  			s.index = newIndex
   575  			d.byteAvailable = false
   576  			s.length = minMatchLength - 1
   577  			if d.tokens.n == maxFlateBlockTokens {
   578  				if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   579  					return
   580  				}
   581  				d.tokens.Reset()
   582  			}
   583  			s.literalCounter = 0
   584  			continue
   585  		}
   586  		if s.length >= minMatchLength {
   587  			s.literalCounter = 0
   588  		}
   589  		if d.byteAvailable {
   590  			s.literalCounter++
   591  			d.tokens.AddLiteral(d.window[s.index-1])
   592  			if d.tokens.n == maxFlateBlockTokens {
   593  				if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   594  					return
   595  				}
   596  				d.tokens.Reset()
   597  			}
   598  			s.index++
   599  			if !d.skipLiterals() {
   600  				return
   601  			}
   602  		} else {
   603  			s.index++
   604  			d.byteAvailable = true
   605  		}
   606  	}
   607  }
   608  
   609  // store will store the current window if it has filled or if we are in sync.
   610  func (d *compressor) store() {
   611  	if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
   612  		d.err = d.writeStoredBlock(d.window[:d.windowEnd])
   613  		d.windowEnd = 0
   614  	}
   615  }
   616  
   617  // fillBlock appends b to d.window, returning the number of bytes copied.
   618  // If n < len(b), the window is filled.
   619  func (d *compressor) fillBlock(b []byte) int {
   620  	n := copy(d.window[d.windowEnd:], b)
   621  	d.windowEnd += int32(n)
   622  	return n
   623  }
   624  
   625  // deflateHuff compresses and stores the current window
   626  // (if it has filled or if we are in sync or flush).
   627  // It uses Huffman-only encoding.
   628  func (d *compressor) deflateHuff() {
   629  	if int(d.windowEnd) < len(d.window) && !d.sync || d.windowEnd == 0 {
   630  		return
   631  	}
   632  	d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
   633  	d.err = d.w.err
   634  	d.windowEnd = 0
   635  }
   636  
   637  // deflateFast encodes the current window
   638  // if it has filled or if we are doing sync/flush.
   639  // It uses the level 1-6 fast encoding.
   640  func (d *compressor) deflateFast() {
   641  	// We only compress if we have maxStoreBlockSize.
   642  	if int(d.windowEnd) < len(d.window) {
   643  		if !d.sync {
   644  			return
   645  		}
   646  		// Handle extremely small sizes.
   647  		if d.windowEnd < 128 {
   648  			if d.windowEnd == 0 {
   649  				return
   650  			}
   651  			if d.windowEnd <= 32 {
   652  				d.err = d.writeStoredBlock(d.window[:d.windowEnd])
   653  			} else {
   654  				d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
   655  				d.err = d.w.err
   656  			}
   657  			d.tokens.Reset()
   658  			d.windowEnd = 0
   659  			d.fast.reset()
   660  			return
   661  		}
   662  	}
   663  
   664  	d.fast.encode(&d.tokens, d.window[:d.windowEnd])
   665  	// If we made zero matches, store the block as is.
   666  	if d.tokens.n == 0 {
   667  		d.err = d.writeStoredBlock(d.window[:d.windowEnd])
   668  		// If we removed less than 1/16th, huffman compress the block.
   669  	} else if int32(d.tokens.n) > d.windowEnd-(d.windowEnd>>4) {
   670  		d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
   671  		d.err = d.w.err
   672  	} else {
   673  		d.w.writeBlockDynamic(&d.tokens, false, d.window[:d.windowEnd], d.sync)
   674  		d.err = d.w.err
   675  	}
   676  	d.tokens.Reset()
   677  	d.windowEnd = 0
   678  }
   679  
   680  // write adds b to the compressor.
   681  // It can only return a short length if an error occurs.
   682  func (d *compressor) write(b []byte) (n int, err error) {
   683  	if d.err != nil {
   684  		return 0, d.err
   685  	}
   686  	n = len(b)
   687  	for len(b) > 0 {
   688  		if int(d.windowEnd) == len(d.window) || d.sync {
   689  			d.step(d)
   690  		}
   691  		b = b[d.fill(d, b):]
   692  		if d.err != nil {
   693  			return 0, d.err
   694  		}
   695  	}
   696  	return n, d.err
   697  }
   698  
   699  // syncFlush will flush the compressor by writing
   700  // any remaining window and writing a stored block
   701  // to byte-align the output.
   702  func (d *compressor) syncFlush() error {
   703  	if d.err != nil {
   704  		return d.err
   705  	}
   706  	d.sync = true
   707  	d.step(d)
   708  	if d.err == nil {
   709  		d.w.writeStoredHeader(0, false)
   710  		d.w.flush()
   711  		d.err = d.w.err
   712  	}
   713  	d.sync = false
   714  	return d.err
   715  }
   716  
   717  // init a new encode with new writer and compression level.
   718  func (d *compressor) init(w io.Writer, level int) (err error) {
   719  	d.w = newHuffmanBitWriter(w)
   720  
   721  	switch {
   722  	case level == NoCompression:
   723  		d.window = make([]byte, maxStoreBlockSize)
   724  		d.fill = (*compressor).fillBlock
   725  		d.step = (*compressor).store
   726  	case level == HuffmanOnly:
   727  		d.w.logNewTablePenalty = 10
   728  		d.window = make([]byte, 32<<10)
   729  		d.fill = (*compressor).fillBlock
   730  		d.step = (*compressor).deflateHuff
   731  	case level == DefaultCompression:
   732  		level = 6
   733  		fallthrough
   734  	case 1 <= level && level <= 6:
   735  		d.w.logNewTablePenalty = 7
   736  		d.fast = newFastEnc(level)
   737  		d.window = make([]byte, maxStoreBlockSize)
   738  		d.fill = (*compressor).fillBlock
   739  		d.step = (*compressor).deflateFast
   740  	case 7 <= level && level <= 9:
   741  		d.w.logNewTablePenalty = 8
   742  		d.state = &advancedState{}
   743  		d.compressionLevel = levels[level]
   744  		d.initDeflate()
   745  		d.fill = (*compressor).fillDeflate
   746  		d.step = (*compressor).deflateLazy
   747  	default:
   748  		return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
   749  	}
   750  	d.level = level
   751  	return nil
   752  }
   753  
   754  // reset resets the compressor with a new output writer.
   755  func (d *compressor) reset(w io.Writer) {
   756  	d.w.reset(w)
   757  	d.sync = false
   758  	d.err = nil
   759  	d.windowEnd = 0
   760  	// We only need to reset a few things for fast encoders.
   761  	if d.fast != nil {
   762  		d.fast.reset()
   763  		d.tokens.Reset()
   764  		return
   765  	}
   766  	if d.compressionLevel.chain == 0 {
   767  		return
   768  	}
   769  	s := d.state
   770  	s.chainHead = -1
   771  	clear(s.hashHead[:])
   772  	clear(s.hashPrev[:])
   773  	s.hashOffset = 1
   774  	s.index = 0
   775  	d.blockStart, d.byteAvailable = 0, false
   776  	d.tokens.Reset()
   777  	s.length = minMatchLength - 1
   778  	s.offset = 0
   779  	s.literalCounter = 0
   780  	s.maxInsertIndex = 0
   781  }
   782  
   783  var errWriterClosed = errors.New("flate: closed writer")
   784  
   785  // close flushes any uncompressed data and writes an EOF block.
   786  func (d *compressor) close() error {
   787  	if d.err == errWriterClosed {
   788  		return nil
   789  	}
   790  	if d.err != nil {
   791  		return d.err
   792  	}
   793  	d.sync = true
   794  	d.step(d)
   795  	if d.err != nil {
   796  		return d.err
   797  	}
   798  	if d.w.writeStoredHeader(0, true); d.w.err != nil {
   799  		return d.w.err
   800  	}
   801  	d.w.flush()
   802  	if d.w.err != nil {
   803  		return d.w.err
   804  	}
   805  	d.err = errWriterClosed
   806  	d.w.reset(nil)
   807  	return nil
   808  }
   809  
   810  // NewWriter returns a new [Writer] compressing data at the given level.
   811  // Following zlib, levels range from 1 ([BestSpeed]) to 9 ([BestCompression]);
   812  // higher levels typically run slower but compress more. Level 0
   813  // ([NoCompression]) does not attempt any compression; it only adds the
   814  // necessary DEFLATE framing.
   815  // Level -1 ([DefaultCompression]) uses the default compression level.
   816  // Level -2 ([HuffmanOnly]) will use Huffman compression only, giving
   817  // a very fast compression for all types of input, but sacrificing considerable
   818  // compression efficiency.
   819  //
   820  // If level is in the range [-2, 9] then the error returned will be nil.
   821  // Otherwise the error returned will be non-nil.
   822  //
   823  // Note that the exact bytes written to w are not covered by the Go 1
   824  // compatibility promise. Callers, including tests, should not depend on the
   825  // exact written bytes.
   826  func NewWriter(w io.Writer, level int) (*Writer, error) {
   827  	var dw Writer
   828  	if err := dw.d.init(w, level); err != nil {
   829  		return nil, err
   830  	}
   831  	return &dw, nil
   832  }
   833  
   834  // NewWriterDict is like [NewWriter] but initializes the new
   835  // [Writer] with a preset dictionary. The returned [Writer] behaves
   836  // as if the dictionary had been written to it without producing
   837  // any compressed output. The compressed data written to w
   838  // can only be decompressed by a reader initialized with the
   839  // same dictionary (see [NewReaderDict]).
   840  //
   841  // Note that the exact bytes written to w are not covered by the Go 1
   842  // compatibility promise. Callers, including tests, should not depend on the
   843  // exact written bytes.
   844  func NewWriterDict(w io.Writer, level int, dict []byte) (*Writer, error) {
   845  	zw, err := NewWriter(w, level)
   846  	if err != nil {
   847  		return nil, err
   848  	}
   849  	zw.d.fillWindow(dict)
   850  	// Clone dict so we can Reset without changing the provided slice.
   851  	zw.dict = slices.Clone(dict)
   852  	return zw, err
   853  }
   854  
   855  // A Writer takes data written to it and writes the compressed
   856  // form of that data to an underlying writer (see [NewWriter]).
   857  type Writer struct {
   858  	d    compressor
   859  	dict []byte
   860  }
   861  
   862  // Write writes data to w, which will eventually write the
   863  // compressed form of data to its underlying writer.
   864  func (w *Writer) Write(data []byte) (n int, err error) {
   865  	return w.d.write(data)
   866  }
   867  
   868  // Flush flushes any pending data to the underlying writer.
   869  // It is useful mainly in compressed network protocols, to ensure that
   870  // a remote reader has enough data to reconstruct a packet.
   871  // Flush does not return until the data has been written.
   872  // Calling Flush when there is no pending data still causes the [Writer]
   873  // to emit a sync marker of at least 4 bytes.
   874  // If the underlying writer returns an error, Flush returns that error.
   875  //
   876  // In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
   877  func (w *Writer) Flush() error {
   878  	// For more about flushing:
   879  	// https://www.bolet.org/~pornin/deflate-flush.html
   880  	return w.d.syncFlush()
   881  }
   882  
   883  // Close flushes and closes the writer.
   884  func (w *Writer) Close() error {
   885  	return w.d.close()
   886  }
   887  
   888  // Reset discards the writer's state and makes it equivalent to
   889  // the result of NewWriter or NewWriterDict called with dst
   890  // and w's level and dictionary.
   891  func (w *Writer) Reset(dst io.Writer) {
   892  	w.d.reset(dst)
   893  	w.d.fillWindow(w.dict)
   894  }
   895  

View as plain text