Source file src/compress/flate/deflate.go

Documentation: compress/flate

     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  }
   254  
   255  // findMatch finds the longest match starting at pos in the hash chain starting
   256  // at prevHead. It searches up to d.chain entries in the chain.
   257  func (d *compressor) findMatch(pos int32, prevHead int32, lookahead int32) (length, offset int32, ok bool) {
   258  	minMatchLook := min(lookahead, maxMatchLength)
   259  
   260  	win := d.window[0 : pos+minMatchLook]
   261  
   262  	// We quit when we get a match that's at least nice long
   263  	nice := min(d.nice, int32(len(win))-pos)
   264  
   265  	// If we've got a match that's good enough, only look in 1/4 the chain.
   266  	tries := d.chain
   267  	length = minMatchLength - 1
   268  
   269  	wEnd := win[pos+length]
   270  	wPos := win[pos:]
   271  	minIndex := max(pos-windowSize, 0)
   272  	offset = 0
   273  
   274  	// Minimum gain to accept a match.
   275  	cGain := 4
   276  
   277  	// Some like it higher (CSV), some like it lower (JSON)
   278  	const baseCost = 3
   279  	// Base is 4 bytes at with an additional cost.
   280  	// Matches must be better than this.
   281  
   282  	for i := prevHead; tries > 0; tries-- {
   283  		if wEnd == win[i+length] {
   284  			n := int32(matchLen(win[i:i+minMatchLook], wPos))
   285  			if n > length {
   286  				if d.chain >= 100 {
   287  					// Calculate gain. Estimates the gains of the new match compared to emitting as literals.
   288  					newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
   289  					if newGain <= cGain {
   290  						goto next
   291  					}
   292  					cGain = newGain
   293  				}
   294  				length = n
   295  				offset = pos - i
   296  				ok = true
   297  				if n >= nice {
   298  					// The match is good enough that we don't try to find a better one.
   299  					break
   300  				}
   301  				wEnd = win[pos+n]
   302  			}
   303  		}
   304  	next:
   305  		if i <= minIndex {
   306  			// hashPrev[i & windowMask] has already been overwritten, so stop now.
   307  			break
   308  		}
   309  		i = d.state.hashPrev[i&windowMask] - d.state.hashOffset
   310  		if i < minIndex {
   311  			break
   312  		}
   313  	}
   314  	return
   315  }
   316  
   317  // writeStoredBlock writes an uncompressed block to the stream.
   318  func (d *compressor) writeStoredBlock(buf []byte) error {
   319  	if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
   320  		return d.w.err
   321  	}
   322  	d.w.writeBytes(buf)
   323  	return d.w.err
   324  }
   325  
   326  // hash4 returns a hash representation of the first 4 bytes
   327  // of the supplied slice.
   328  // The caller must ensure that len(b) >= 4.
   329  func hash4(b []byte) uint32 {
   330  	return hash4u(loadLE32(b, 0), hashBits)
   331  }
   332  
   333  // hash4 returns the hash of u to fit in a hash table with h bits.
   334  // Preferably h should be a constant and should always be <32.
   335  func hash4u(u uint32, h uint8) uint32 {
   336  	return (u * prime4bytes) >> (32 - h)
   337  }
   338  
   339  // bulkHash4 sets dst[i] = hash4(b[i:i+4]) for all i <= len(b)-4.
   340  func bulkHash4(b []byte, dst []uint32) {
   341  	if len(b) < 4 {
   342  		return
   343  	}
   344  	hb := loadLE32(b, 0)
   345  
   346  	dst[0] = hash4u(hb, hashBits)
   347  	end := len(b) - 4 + 1
   348  	for i := 1; i < end; i++ {
   349  		hb = (hb >> 8) | uint32(b[i+3])<<24
   350  		dst[i] = hash4u(hb, hashBits)
   351  	}
   352  }
   353  
   354  // initDeflate initializes d for levels 7-9.
   355  func (d *compressor) initDeflate() {
   356  	d.window = make([]byte, 2*windowSize)
   357  	d.byteAvailable = false
   358  	d.err = nil
   359  	if d.state == nil {
   360  		return
   361  	}
   362  	s := d.state
   363  	s.index = 0
   364  	s.hashOffset = 1
   365  	s.length = minMatchLength - 1
   366  	s.offset = 0
   367  	s.chainHead = -1
   368  }
   369  
   370  // tryBetterMatchAtEnd checks whether a better match exists at the end of the
   371  // previous match and, if so, emits the skipped literals and adjusts the match.
   372  // Returns the (possibly updated) prevLength and prevOffset.
   373  func (d *compressor) tryBetterMatchAtEnd(prevLength, prevOffset, lookahead int32) (newLen, newOff int32) {
   374  	// We start checking at checkOff from the current match position.
   375  	// This allows up to two additional literals, but that could be
   376  	// compensated by a higher quality match.
   377  	// If the match looks better, we extend backwards.
   378  	const checkOff = 2
   379  	s := d.state
   380  
   381  	if prevLength >= maxMatchLength-checkOff {
   382  		return prevLength, prevOffset
   383  	}
   384  	prevIndex := s.index - 1
   385  	if prevIndex+prevLength >= s.maxInsertIndex {
   386  		return prevLength, prevOffset
   387  	}
   388  
   389  	end := min(lookahead, maxMatchLength+checkOff) + prevIndex
   390  	minIndex := max(s.index-windowSize, 0)
   391  
   392  	h := hash4(d.window[prevIndex+prevLength:])
   393  	ch2 := s.hashHead[h] - s.hashOffset - prevLength
   394  	if prevIndex-ch2 == prevOffset || ch2 <= minIndex+checkOff {
   395  		return prevLength, prevOffset
   396  	}
   397  
   398  	length := int32(matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:]))
   399  	if length <= prevLength {
   400  		return prevLength, prevOffset
   401  	}
   402  
   403  	prevLength = length
   404  	prevOffset = prevIndex - ch2
   405  
   406  	for i := int32(checkOff - 1); i >= 0; i-- {
   407  		if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i] {
   408  			for j := range i + 1 {
   409  				d.tokens.AddLiteral(d.window[prevIndex+j])
   410  				if d.tokens.n == maxFlateBlockTokens {
   411  					if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   412  						return prevLength, prevOffset
   413  					}
   414  					d.tokens.Reset()
   415  				}
   416  				s.index++
   417  				if s.index < s.maxInsertIndex {
   418  					h := hash4(d.window[s.index:])
   419  					ch := s.hashHead[h]
   420  					s.chainHead = ch
   421  					s.hashPrev[s.index&windowMask] = ch
   422  					s.hashHead[h] = s.index + s.hashOffset
   423  				}
   424  			}
   425  			break
   426  		}
   427  		prevLength++
   428  	}
   429  	return prevLength, prevOffset
   430  }
   431  
   432  // skipLiterals emits extra literal bytes during long runs of incompressible data,
   433  // skipping ahead to avoid futile match searches. Returns false on write error.
   434  func (d *compressor) skipLiterals() bool {
   435  	s := d.state
   436  	n := int32(s.literalCounter) - d.chain
   437  	if n <= 0 {
   438  		return true
   439  	}
   440  	n = 1 + n>>6
   441  	for range n {
   442  		if s.index >= d.windowEnd-1 {
   443  			break
   444  		}
   445  		d.tokens.AddLiteral(d.window[s.index-1])
   446  		if d.tokens.n == maxFlateBlockTokens {
   447  			if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   448  				return false
   449  			}
   450  			d.tokens.Reset()
   451  		}
   452  		if s.index < s.maxInsertIndex {
   453  			h := hash4(d.window[s.index:])
   454  			ch := s.hashHead[h]
   455  			s.chainHead = ch
   456  			s.hashPrev[s.index&windowMask] = ch
   457  			s.hashHead[h] = s.index + s.hashOffset
   458  		}
   459  		s.index++
   460  	}
   461  	d.tokens.AddLiteral(d.window[s.index-1])
   462  	d.byteAvailable = false
   463  	if d.tokens.n == maxFlateBlockTokens {
   464  		if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   465  			return false
   466  		}
   467  		d.tokens.Reset()
   468  	}
   469  	return true
   470  }
   471  
   472  // deflateLazy encodes the current window using lazy matching.
   473  // Lazy matching defers emitting a match to see if the next position yields a better one.
   474  // Unique to levels 7-9 is that more than 2 matches are potentially checked
   475  // until a good/nice one is found.
   476  func (d *compressor) deflateLazy() {
   477  	s := d.state
   478  
   479  	if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
   480  		return
   481  	}
   482  	if d.windowEnd != s.index && d.chain > 100 {
   483  		// Get literal huffman coder.
   484  		// This is used to estimate the cost of emitting a literal.
   485  		if d.h == nil {
   486  			d.h = newHuffmanEncoder(maxFlateBlockTokens)
   487  		}
   488  		var tmp [256]uint16
   489  		toIndex := d.window[s.index:d.windowEnd]
   490  		toIndex = toIndex[:min(len(toIndex), maxFlateBlockTokens)]
   491  		for _, v := range toIndex {
   492  			tmp[v]++
   493  		}
   494  		d.h.generate(tmp[:], 15)
   495  	}
   496  
   497  	s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
   498  
   499  	for {
   500  		lookahead := d.windowEnd - s.index
   501  		if lookahead < minMatchLength+maxMatchLength {
   502  			if !d.sync {
   503  				return
   504  			}
   505  			if lookahead == 0 {
   506  				// Flush current output block if any.
   507  				if d.byteAvailable {
   508  					// There is still one pending token that needs to be flushed
   509  					d.tokens.AddLiteral(d.window[s.index-1])
   510  					d.byteAvailable = false
   511  				}
   512  				if d.tokens.n > 0 {
   513  					if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   514  						return
   515  					}
   516  					d.tokens.Reset()
   517  				}
   518  				return
   519  			}
   520  		}
   521  		if s.index < s.maxInsertIndex {
   522  			h := hash4(d.window[s.index:])
   523  			ch := s.hashHead[h]
   524  			s.chainHead = ch
   525  			s.hashPrev[s.index&windowMask] = ch
   526  			s.hashHead[h] = s.index + s.hashOffset
   527  		}
   528  		prevLength := s.length
   529  		prevOffset := s.offset
   530  		s.length = minMatchLength - 1
   531  		s.offset = 0
   532  		minIndex := max(s.index-windowSize, 0)
   533  
   534  		if s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
   535  			if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, lookahead); ok {
   536  				s.length = newLength
   537  				s.offset = newOffset
   538  			}
   539  		}
   540  
   541  		if prevLength >= minMatchLength && s.length <= prevLength {
   542  			prevLength, prevOffset = d.tryBetterMatchAtEnd(prevLength, prevOffset, lookahead)
   543  			if d.err != nil {
   544  				return
   545  			}
   546  
   547  			// There was a match at the previous step, and the current match is
   548  			// not better. Output the previous match.
   549  			d.tokens.AddMatch(uint32(prevLength-3), uint32(prevOffset-minOffsetSize))
   550  
   551  			// Insert in the hash table all strings up to the end of the match.
   552  			// index and index-1 are already inserted. If there is not enough
   553  			// lookahead, the last two strings are not inserted into the hash
   554  			// table.
   555  			newIndex := s.index + prevLength - 1
   556  			end := min(newIndex, s.maxInsertIndex)
   557  			end += minMatchLength - 1
   558  			startindex := min(s.index+1, s.maxInsertIndex)
   559  			tocheck := d.window[startindex:end]
   560  			dstSize := len(tocheck) - minMatchLength + 1
   561  			if dstSize > 0 {
   562  				dst := s.hashMatch[:dstSize]
   563  				bulkHash4(tocheck, dst)
   564  				var newH uint32
   565  				for i, val := range dst {
   566  					di := int32(i) + startindex
   567  					newH = val & hashMask
   568  					s.hashPrev[di&windowMask] = s.hashHead[newH]
   569  					s.hashHead[newH] = di + s.hashOffset
   570  				}
   571  			}
   572  
   573  			s.index = newIndex
   574  			d.byteAvailable = false
   575  			s.length = minMatchLength - 1
   576  			if d.tokens.n == maxFlateBlockTokens {
   577  				if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   578  					return
   579  				}
   580  				d.tokens.Reset()
   581  			}
   582  			s.literalCounter = 0
   583  			continue
   584  		}
   585  		if s.length >= minMatchLength {
   586  			s.literalCounter = 0
   587  		}
   588  		if d.byteAvailable {
   589  			s.literalCounter++
   590  			d.tokens.AddLiteral(d.window[s.index-1])
   591  			if d.tokens.n == maxFlateBlockTokens {
   592  				if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
   593  					return
   594  				}
   595  				d.tokens.Reset()
   596  			}
   597  			s.index++
   598  			if !d.skipLiterals() {
   599  				return
   600  			}
   601  		} else {
   602  			s.index++
   603  			d.byteAvailable = true
   604  		}
   605  	}
   606  }
   607  
   608  // store will store the current window if it has filled or if we are in sync.
   609  func (d *compressor) store() {
   610  	if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
   611  		d.err = d.writeStoredBlock(d.window[:d.windowEnd])
   612  		d.windowEnd = 0
   613  	}
   614  }
   615  
   616  // fillBlock appends b to d.window, returning the number of bytes copied.
   617  // If n < len(b), the window is filled.
   618  func (d *compressor) fillBlock(b []byte) int {
   619  	n := copy(d.window[d.windowEnd:], b)
   620  	d.windowEnd += int32(n)
   621  	return n
   622  }
   623  
   624  // deflateHuff compresses and stores the current window
   625  // (if it has filled or if we are in sync or flush).
   626  // It uses Huffman-only encoding.
   627  func (d *compressor) deflateHuff() {
   628  	if int(d.windowEnd) < len(d.window) && !d.sync || d.windowEnd == 0 {
   629  		return
   630  	}
   631  	d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
   632  	d.err = d.w.err
   633  	d.windowEnd = 0
   634  }
   635  
   636  // deflateFast encodes the current window
   637  // if it has filled or if we are doing sync/flush.
   638  // It uses the level 1-6 fast encoding.
   639  func (d *compressor) deflateFast() {
   640  	// We only compress if we have maxStoreBlockSize.
   641  	if int(d.windowEnd) < len(d.window) {
   642  		if !d.sync {
   643  			return
   644  		}
   645  		// Handle extremely small sizes.
   646  		if d.windowEnd < 128 {
   647  			if d.windowEnd == 0 {
   648  				return
   649  			}
   650  			if d.windowEnd <= 32 {
   651  				d.err = d.writeStoredBlock(d.window[:d.windowEnd])
   652  			} else {
   653  				d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
   654  				d.err = d.w.err
   655  			}
   656  			d.tokens.Reset()
   657  			d.windowEnd = 0
   658  			d.fast.reset()
   659  			return
   660  		}
   661  	}
   662  
   663  	d.fast.encode(&d.tokens, d.window[:d.windowEnd])
   664  	// If we made zero matches, store the block as is.
   665  	if d.tokens.n == 0 {
   666  		d.err = d.writeStoredBlock(d.window[:d.windowEnd])
   667  		// If we removed less than 1/16th, huffman compress the block.
   668  	} else if int32(d.tokens.n) > d.windowEnd-(d.windowEnd>>4) {
   669  		d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
   670  		d.err = d.w.err
   671  	} else {
   672  		d.w.writeBlockDynamic(&d.tokens, false, d.window[:d.windowEnd], d.sync)
   673  		d.err = d.w.err
   674  	}
   675  	d.tokens.Reset()
   676  	d.windowEnd = 0
   677  }
   678  
   679  // write adds b to the compressor.
   680  // It can only return a short length if an error occurs.
   681  func (d *compressor) write(b []byte) (n int, err error) {
   682  	if d.err != nil {
   683  		return 0, d.err
   684  	}
   685  	n = len(b)
   686  	for len(b) > 0 {
   687  		if int(d.windowEnd) == len(d.window) || d.sync {
   688  			d.step(d)
   689  		}
   690  		b = b[d.fill(d, b):]
   691  		if d.err != nil {
   692  			return 0, d.err
   693  		}
   694  	}
   695  	return n, d.err
   696  }
   697  
   698  // syncFlush will flush the compressor by writing
   699  // any remaining window and writing a stored block
   700  // to byte-align the output.
   701  func (d *compressor) syncFlush() error {
   702  	if d.err != nil {
   703  		return d.err
   704  	}
   705  	d.sync = true
   706  	d.step(d)
   707  	if d.err == nil {
   708  		d.w.writeStoredHeader(0, false)
   709  		d.w.flush()
   710  		d.err = d.w.err
   711  	}
   712  	d.sync = false
   713  	return d.err
   714  }
   715  
   716  // init a new encode with new writer and compression level.
   717  func (d *compressor) init(w io.Writer, level int) (err error) {
   718  	d.w = newHuffmanBitWriter(w)
   719  
   720  	switch {
   721  	case level == NoCompression:
   722  		d.window = make([]byte, maxStoreBlockSize)
   723  		d.fill = (*compressor).fillBlock
   724  		d.step = (*compressor).store
   725  	case level == HuffmanOnly:
   726  		d.w.logNewTablePenalty = 10
   727  		d.window = make([]byte, 32<<10)
   728  		d.fill = (*compressor).fillBlock
   729  		d.step = (*compressor).deflateHuff
   730  	case level == DefaultCompression:
   731  		level = 6
   732  		fallthrough
   733  	case 1 <= level && level <= 6:
   734  		d.w.logNewTablePenalty = 7
   735  		d.fast = newFastEnc(level)
   736  		d.window = make([]byte, maxStoreBlockSize)
   737  		d.fill = (*compressor).fillBlock
   738  		d.step = (*compressor).deflateFast
   739  	case 7 <= level && level <= 9:
   740  		d.w.logNewTablePenalty = 8
   741  		d.state = &advancedState{}
   742  		d.compressionLevel = levels[level]
   743  		d.initDeflate()
   744  		d.fill = (*compressor).fillDeflate
   745  		d.step = (*compressor).deflateLazy
   746  	default:
   747  		return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
   748  	}
   749  	d.level = level
   750  	return nil
   751  }
   752  
   753  // reset resets the compressor with a new output writer.
   754  func (d *compressor) reset(w io.Writer) {
   755  	d.w.reset(w)
   756  	d.sync = false
   757  	d.err = nil
   758  	d.windowEnd = 0
   759  	// We only need to reset a few things for fast encoders.
   760  	if d.fast != nil {
   761  		d.fast.reset()
   762  		d.tokens.Reset()
   763  		return
   764  	}
   765  	if d.compressionLevel.chain == 0 {
   766  		return
   767  	}
   768  	s := d.state
   769  	s.chainHead = -1
   770  	clear(s.hashHead[:])
   771  	clear(s.hashPrev[:])
   772  	s.hashOffset = 1
   773  	s.index = 0
   774  	d.blockStart, d.byteAvailable = 0, false
   775  	d.tokens.Reset()
   776  	s.length = minMatchLength - 1
   777  	s.offset = 0
   778  	s.literalCounter = 0
   779  	s.maxInsertIndex = 0
   780  }
   781  
   782  var errWriterClosed = errors.New("flate: closed writer")
   783  
   784  // close flushes any uncompressed data and writes an EOF block.
   785  func (d *compressor) close() error {
   786  	if d.err == errWriterClosed {
   787  		return nil
   788  	}
   789  	if d.err != nil {
   790  		return d.err
   791  	}
   792  	d.sync = true
   793  	d.step(d)
   794  	if d.err != nil {
   795  		return d.err
   796  	}
   797  	if d.w.writeStoredHeader(0, true); d.w.err != nil {
   798  		return d.w.err
   799  	}
   800  	d.w.flush()
   801  	if d.w.err != nil {
   802  		return d.w.err
   803  	}
   804  	d.err = errWriterClosed
   805  	d.w.reset(nil)
   806  	return nil
   807  }
   808  
   809  // NewWriter returns a new [Writer] compressing data at the given level.
   810  // Following zlib, levels range from 1 ([BestSpeed]) to 9 ([BestCompression]);
   811  // higher levels typically run slower but compress more. Level 0
   812  // ([NoCompression]) does not attempt any compression; it only adds the
   813  // necessary DEFLATE framing.
   814  // Level -1 ([DefaultCompression]) uses the default compression level.
   815  // Level -2 ([HuffmanOnly]) will use Huffman compression only, giving
   816  // a very fast compression for all types of input, but sacrificing considerable
   817  // compression efficiency.
   818  //
   819  // If level is in the range [-2, 9] then the error returned will be nil.
   820  // Otherwise the error returned will be non-nil.
   821  //
   822  // Note that the exact bytes written to w are not covered by the Go 1
   823  // compatibility promise. Callers, including tests, should not depend on the
   824  // exact written bytes.
   825  func NewWriter(w io.Writer, level int) (*Writer, error) {
   826  	var dw Writer
   827  	if err := dw.d.init(w, level); err != nil {
   828  		return nil, err
   829  	}
   830  	return &dw, nil
   831  }
   832  
   833  // NewWriterDict is like [NewWriter] but initializes the new
   834  // [Writer] with a preset dictionary. The returned [Writer] behaves
   835  // as if the dictionary had been written to it without producing
   836  // any compressed output. The compressed data written to w
   837  // can only be decompressed by a reader initialized with the
   838  // same dictionary (see [NewReaderDict]).
   839  //
   840  // Note that the exact bytes written to w are not covered by the Go 1
   841  // compatibility promise. Callers, including tests, should not depend on the
   842  // exact written bytes.
   843  func NewWriterDict(w io.Writer, level int, dict []byte) (*Writer, error) {
   844  	zw, err := NewWriter(w, level)
   845  	if err != nil {
   846  		return nil, err
   847  	}
   848  	zw.d.fillWindow(dict)
   849  	// Clone dict so we can Reset without changing the provided slice.
   850  	zw.dict = slices.Clone(dict)
   851  	return zw, err
   852  }
   853  
   854  // A Writer takes data written to it and writes the compressed
   855  // form of that data to an underlying writer (see [NewWriter]).
   856  type Writer struct {
   857  	d    compressor
   858  	dict []byte
   859  }
   860  
   861  // Write writes data to w, which will eventually write the
   862  // compressed form of data to its underlying writer.
   863  func (w *Writer) Write(data []byte) (n int, err error) {
   864  	return w.d.write(data)
   865  }
   866  
   867  // Flush flushes any pending data to the underlying writer.
   868  // It is useful mainly in compressed network protocols, to ensure that
   869  // a remote reader has enough data to reconstruct a packet.
   870  // Flush does not return until the data has been written.
   871  // Calling Flush when there is no pending data still causes the [Writer]
   872  // to emit a sync marker of at least 4 bytes.
   873  // If the underlying writer returns an error, Flush returns that error.
   874  //
   875  // In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
   876  func (w *Writer) Flush() error {
   877  	// For more about flushing:
   878  	// https://www.bolet.org/~pornin/deflate-flush.html
   879  	return w.d.syncFlush()
   880  }
   881  
   882  // Close flushes and closes the writer.
   883  func (w *Writer) Close() error {
   884  	return w.d.close()
   885  }
   886  
   887  // Reset discards the writer's state and makes it equivalent to
   888  // the result of NewWriter or NewWriterDict called with dst
   889  // and w's level and dictionary.
   890  func (w *Writer) Reset(dst io.Writer) {
   891  	w.d.reset(dst)
   892  	w.d.fillWindow(w.dict)
   893  }
   894  

View as plain text