// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package flate

import (
	
	
	
)

const (
	NoCompression      = 0
	BestSpeed          = 1
	BestCompression    = 9
	DefaultCompression = -1

	// HuffmanOnly disables Lempel-Ziv match searching and only performs Huffman
	// entropy encoding. This mode is useful in compressing data that has
	// already been compressed with an LZ style algorithm (e.g. Snappy or LZ4)
	// that lacks an entropy encoder. Compression gains are achieved when
	// certain bytes in the input stream occur more frequently than others.
	//
	// Note that HuffmanOnly produces a compressed output that is
	// RFC 1951 compliant. That is, any valid DEFLATE decompressor will
	// continue to be able to decompress this output.
	HuffmanOnly = -2
)

const (
	logWindowSize = 15
	windowSize    = 1 << logWindowSize
	windowMask    = windowSize - 1

	// The LZ77 step produces a sequence of literal tokens and <length, offset>
	// pair tokens. The offset is also known as distance. The underlying wire
	// format limits the range of lengths and offsets. For example, there are
	// 256 legitimate lengths: those in the range [3, 258]. This package's
	// compressor uses a higher minimum match length, enabling optimizations
	// such as finding matches via 32-bit loads and compares.
	baseMatchLength = 3       // The smallest match length per the RFC section 3.2.5
	minMatchLength  = 4       // The smallest match length that the compressor actually emits
	maxMatchLength  = 258     // The largest match length
	baseMatchOffset = 1       // The smallest match offset
	maxMatchOffset  = 1 << 15 // The largest match offset

	// The maximum number of tokens we put into a single flate block, just to
	// stop things from getting too large.
	maxFlateBlockTokens = 1 << 14
	maxStoreBlockSize   = 65535
	hashBits            = 17 // After 17 performance degrades
	hashSize            = 1 << hashBits
	hashMask            = (1 << hashBits) - 1
	maxHashOffset       = 1 << 24

	skipNever = math.MaxInt32
)

type compressionLevel struct {
	level, good, lazy, nice, chain, fastSkipHashing int
}

var levels = []compressionLevel{
	{0, 0, 0, 0, 0, 0}, // NoCompression.
	{1, 0, 0, 0, 0, 0}, // BestSpeed uses a custom algorithm; see deflatefast.go.
	// For levels 2-3 we don't bother trying with lazy matches.
	{2, 4, 0, 16, 8, 5},
	{3, 4, 0, 32, 32, 6},
	// Levels 4-9 use increasingly more lazy matching
	// and increasingly stringent conditions for "good enough".
	{4, 4, 4, 16, 16, skipNever},
	{5, 8, 16, 32, 32, skipNever},
	{6, 8, 16, 128, 128, skipNever},
	{7, 8, 32, 128, 256, skipNever},
	{8, 32, 128, 258, 1024, skipNever},
	{9, 32, 258, 258, 4096, skipNever},
}

type compressor struct {
	compressionLevel

	w          *huffmanBitWriter
	bulkHasher func([]byte, []uint32)

	// compression algorithm
	fill      func(*compressor, []byte) int // copy data to window
	step      func(*compressor)             // process window
	sync      bool                          // requesting flush
	bestSpeed *deflateFast                  // Encoder for BestSpeed

	// Input hash chains
	// hashHead[hashValue] contains the largest inputIndex with the specified hash value
	// If hashHead[hashValue] is within the current window, then
	// hashPrev[hashHead[hashValue] & windowMask] contains the previous index
	// with the same hash value.
	chainHead  int
	hashHead   [hashSize]uint32
	hashPrev   [windowSize]uint32
	hashOffset int

	// input window: unprocessed data is window[index:windowEnd]
	index         int
	window        []byte
	windowEnd     int
	blockStart    int  // window index where current tokens start
	byteAvailable bool // if true, still need to process window[index-1].

	// queued output tokens
	tokens []token

	// deflate state
	length         int
	offset         int
	hash           uint32
	maxInsertIndex int
	err            error

	// hashMatch must be able to contain hashes for the maximum match length.
	hashMatch [maxMatchLength - 1]uint32
}

func ( *compressor) ( []byte) int {
	if .index >= 2*windowSize-(minMatchLength+maxMatchLength) {
		// shift the window by windowSize
		copy(.window, .window[windowSize:2*windowSize])
		.index -= windowSize
		.windowEnd -= windowSize
		if .blockStart >= windowSize {
			.blockStart -= windowSize
		} else {
			.blockStart = math.MaxInt32
		}
		.hashOffset += windowSize
		if .hashOffset > maxHashOffset {
			 := .hashOffset - 1
			.hashOffset -= 
			.chainHead -= 

			// Iterate over slices instead of arrays to avoid copying
			// the entire table onto the stack (Issue #18625).
			for ,  := range .hashPrev[:] {
				if int() >  {
					.hashPrev[] = uint32(int() - )
				} else {
					.hashPrev[] = 0
				}
			}
			for ,  := range .hashHead[:] {
				if int() >  {
					.hashHead[] = uint32(int() - )
				} else {
					.hashHead[] = 0
				}
			}
		}
	}
	 := copy(.window[.windowEnd:], )
	.windowEnd += 
	return 
}

func ( *compressor) ( []token,  int) error {
	if  > 0 {
		var  []byte
		if .blockStart <=  {
			 = .window[.blockStart:]
		}
		.blockStart = 
		.w.writeBlock(, false, )
		return .w.err
	}
	return nil
}

// fillWindow will fill the current window with the supplied
// dictionary and calculate all hashes.
// This is much faster than doing a full encode.
// Should only be used after a reset.
func ( *compressor) ( []byte) {
	// Do not fill window if we are in store-only mode.
	if .compressionLevel.level < 2 {
		return
	}
	if .index != 0 || .windowEnd != 0 {
		panic("internal error: fillWindow called with stale data")
	}

	// If we are given too much, cut it.
	if len() > windowSize {
		 = [len()-windowSize:]
	}
	// Add all to window.
	 := copy(.window, )

	// Calculate 256 hashes at the time (more L1 cache hits)
	 := ( + 256 - minMatchLength) / 256
	for  := 0;  < ; ++ {
		 :=  * 256
		 :=  + 256 + minMatchLength - 1
		if  >  {
			 = 
		}
		 := .window[:]
		 := len() - minMatchLength + 1

		if  <= 0 {
			continue
		}

		 := .hashMatch[:]
		.bulkHasher(, )
		var  uint32
		for ,  := range  {
			 :=  + 
			 = 
			 := &.hashHead[&hashMask]
			// Get previous value with the same hash.
			// Our chain should point to the previous value.
			.hashPrev[&windowMask] = *
			// Set the head of the hash chain to us.
			* = uint32( + .hashOffset)
		}
		.hash = 
	}
	// Update window information.
	.windowEnd = 
	.index = 
}

// Try to find a match starting at index whose length is greater than prevSize.
// We only look at chainCount possibilities before giving up.
func ( *compressor) ( int,  int,  int,  int) (,  int,  bool) {
	 := maxMatchLength
	if  <  {
		 = 
	}

	 := .window[0 : +]

	// We quit when we get a match that's at least nice long
	 := len() - 
	if .nice <  {
		 = .nice
	}

	// If we've got a match that's good enough, only look in 1/4 the chain.
	 := .chain
	 = 
	if  >= .good {
		 >>= 2
	}

	 := [+]
	 := [:]
	 :=  - windowSize

	for  := ;  > 0; -- {
		if  == [+] {
			 := matchLen([:], , )

			if  >  && ( > minMatchLength || - <= 4096) {
				 = 
				 =  - 
				 = true
				if  >=  {
					// The match is good enough that we don't try to find a better one.
					break
				}
				 = [+]
			}
		}
		if  ==  {
			// hashPrev[i & windowMask] has already been overwritten, so stop now.
			break
		}
		 = int(.hashPrev[&windowMask]) - .hashOffset
		if  <  ||  < 0 {
			break
		}
	}
	return
}

func ( *compressor) ( []byte) error {
	if .w.writeStoredHeader(len(), false); .w.err != nil {
		return .w.err
	}
	.w.writeBytes()
	return .w.err
}

const hashmul = 0x1e35a7bd

// hash4 returns a hash representation of the first 4 bytes
// of the supplied slice.
// The caller must ensure that len(b) >= 4.
func hash4( []byte) uint32 {
	return ((uint32([3]) | uint32([2])<<8 | uint32([1])<<16 | uint32([0])<<24) * hashmul) >> (32 - hashBits)
}

// bulkHash4 will compute hashes using the same
// algorithm as hash4
func bulkHash4( []byte,  []uint32) {
	if len() < minMatchLength {
		return
	}
	 := uint32([3]) | uint32([2])<<8 | uint32([1])<<16 | uint32([0])<<24
	[0] = ( * hashmul) >> (32 - hashBits)
	 := len() - minMatchLength + 1
	for  := 1;  < ; ++ {
		 = ( << 8) | uint32([+3])
		[] = ( * hashmul) >> (32 - hashBits)
	}
}

// matchLen returns the number of matching bytes in a and b
// up to length 'max'. Both slices must be at least 'max'
// bytes in size.
func matchLen(,  []byte,  int) int {
	 = [:]
	 = [:len()]
	for ,  := range  {
		if [] !=  {
			return 
		}
	}
	return 
}

// encSpeed will compress and store the currently added data,
// if enough has been accumulated or we at the end of the stream.
// Any error that occurred will be in d.err
func ( *compressor) () {
	// We only compress if we have maxStoreBlockSize.
	if .windowEnd < maxStoreBlockSize {
		if !.sync {
			return
		}

		// Handle small sizes.
		if .windowEnd < 128 {
			switch {
			case .windowEnd == 0:
				return
			case .windowEnd <= 16:
				.err = .writeStoredBlock(.window[:.windowEnd])
			default:
				.w.writeBlockHuff(false, .window[:.windowEnd])
				.err = .w.err
			}
			.windowEnd = 0
			.bestSpeed.reset()
			return
		}

	}
	// Encode the block.
	.tokens = .bestSpeed.encode(.tokens[:0], .window[:.windowEnd])

	// If we removed less than 1/16th, Huffman compress the block.
	if len(.tokens) > .windowEnd-(.windowEnd>>4) {
		.w.writeBlockHuff(false, .window[:.windowEnd])
	} else {
		.w.writeBlockDynamic(.tokens, false, .window[:.windowEnd])
	}
	.err = .w.err
	.windowEnd = 0
}

func ( *compressor) () {
	.window = make([]byte, 2*windowSize)
	.hashOffset = 1
	.tokens = make([]token, 0, maxFlateBlockTokens+1)
	.length = minMatchLength - 1
	.offset = 0
	.byteAvailable = false
	.index = 0
	.hash = 0
	.chainHead = -1
	.bulkHasher = bulkHash4
}

func ( *compressor) () {
	if .windowEnd-.index < minMatchLength+maxMatchLength && !.sync {
		return
	}

	.maxInsertIndex = .windowEnd - (minMatchLength - 1)
	if .index < .maxInsertIndex {
		.hash = hash4(.window[.index : .index+minMatchLength])
	}

:
	for {
		if .index > .windowEnd {
			panic("index > windowEnd")
		}
		 := .windowEnd - .index
		if  < minMatchLength+maxMatchLength {
			if !.sync {
				break 
			}
			if .index > .windowEnd {
				panic("index > windowEnd")
			}
			if  == 0 {
				// Flush current output block if any.
				if .byteAvailable {
					// There is still one pending token that needs to be flushed
					.tokens = append(.tokens, literalToken(uint32(.window[.index-1])))
					.byteAvailable = false
				}
				if len(.tokens) > 0 {
					if .err = .writeBlock(.tokens, .index); .err != nil {
						return
					}
					.tokens = .tokens[:0]
				}
				break 
			}
		}
		if .index < .maxInsertIndex {
			// Update the hash
			.hash = hash4(.window[.index : .index+minMatchLength])
			 := &.hashHead[.hash&hashMask]
			.chainHead = int(*)
			.hashPrev[.index&windowMask] = uint32(.chainHead)
			* = uint32(.index + .hashOffset)
		}
		 := .length
		 := .offset
		.length = minMatchLength - 1
		.offset = 0
		 := .index - windowSize
		if  < 0 {
			 = 0
		}

		if .chainHead-.hashOffset >=  &&
			(.fastSkipHashing != skipNever &&  > minMatchLength-1 ||
				.fastSkipHashing == skipNever &&  >  &&  < .lazy) {
			if , ,  := .findMatch(.index, .chainHead-.hashOffset, minMatchLength-1, );  {
				.length = 
				.offset = 
			}
		}
		if .fastSkipHashing != skipNever && .length >= minMatchLength ||
			.fastSkipHashing == skipNever &&  >= minMatchLength && .length <=  {
			// There was a match at the previous step, and the current match is
			// not better. Output the previous match.
			if .fastSkipHashing != skipNever {
				.tokens = append(.tokens, matchToken(uint32(.length-baseMatchLength), uint32(.offset-baseMatchOffset)))
			} else {
				.tokens = append(.tokens, matchToken(uint32(-baseMatchLength), uint32(-baseMatchOffset)))
			}
			// Insert in the hash table all strings up to the end of the match.
			// index and index-1 are already inserted. If there is not enough
			// lookahead, the last two strings are not inserted into the hash
			// table.
			if .length <= .fastSkipHashing {
				var  int
				if .fastSkipHashing != skipNever {
					 = .index + .length
				} else {
					 = .index +  - 1
				}
				 := .index
				for ++;  < ; ++ {
					if  < .maxInsertIndex {
						.hash = hash4(.window[ : +minMatchLength])
						// Get previous value with the same hash.
						// Our chain should point to the previous value.
						 := &.hashHead[.hash&hashMask]
						.hashPrev[&windowMask] = *
						// Set the head of the hash chain to us.
						* = uint32( + .hashOffset)
					}
				}
				.index = 

				if .fastSkipHashing == skipNever {
					.byteAvailable = false
					.length = minMatchLength - 1
				}
			} else {
				// For matches this long, we don't bother inserting each individual
				// item into the table.
				.index += .length
				if .index < .maxInsertIndex {
					.hash = hash4(.window[.index : .index+minMatchLength])
				}
			}
			if len(.tokens) == maxFlateBlockTokens {
				// The block includes the current character
				if .err = .writeBlock(.tokens, .index); .err != nil {
					return
				}
				.tokens = .tokens[:0]
			}
		} else {
			if .fastSkipHashing != skipNever || .byteAvailable {
				 := .index - 1
				if .fastSkipHashing != skipNever {
					 = .index
				}
				.tokens = append(.tokens, literalToken(uint32(.window[])))
				if len(.tokens) == maxFlateBlockTokens {
					if .err = .writeBlock(.tokens, +1); .err != nil {
						return
					}
					.tokens = .tokens[:0]
				}
			}
			.index++
			if .fastSkipHashing == skipNever {
				.byteAvailable = true
			}
		}
	}
}

func ( *compressor) ( []byte) int {
	 := copy(.window[.windowEnd:], )
	.windowEnd += 
	return 
}

func ( *compressor) () {
	if .windowEnd > 0 && (.windowEnd == maxStoreBlockSize || .sync) {
		.err = .writeStoredBlock(.window[:.windowEnd])
		.windowEnd = 0
	}
}

// storeHuff compresses and stores the currently added data
// when the d.window is full or we are at the end of the stream.
// Any error that occurred will be in d.err
func ( *compressor) () {
	if .windowEnd < len(.window) && !.sync || .windowEnd == 0 {
		return
	}
	.w.writeBlockHuff(false, .window[:.windowEnd])
	.err = .w.err
	.windowEnd = 0
}

func ( *compressor) ( []byte) ( int,  error) {
	if .err != nil {
		return 0, .err
	}
	 = len()
	for len() > 0 {
		.step()
		 = [.fill(, ):]
		if .err != nil {
			return 0, .err
		}
	}
	return , nil
}

func ( *compressor) () error {
	if .err != nil {
		return .err
	}
	.sync = true
	.step()
	if .err == nil {
		.w.writeStoredHeader(0, false)
		.w.flush()
		.err = .w.err
	}
	.sync = false
	return .err
}

func ( *compressor) ( io.Writer,  int) ( error) {
	.w = newHuffmanBitWriter()

	switch {
	case  == NoCompression:
		.window = make([]byte, maxStoreBlockSize)
		.fill = (*compressor).fillStore
		.step = (*compressor).store
	case  == HuffmanOnly:
		.window = make([]byte, maxStoreBlockSize)
		.fill = (*compressor).fillStore
		.step = (*compressor).storeHuff
	case  == BestSpeed:
		.compressionLevel = levels[]
		.window = make([]byte, maxStoreBlockSize)
		.fill = (*compressor).fillStore
		.step = (*compressor).encSpeed
		.bestSpeed = newDeflateFast()
		.tokens = make([]token, maxStoreBlockSize)
	case  == DefaultCompression:
		 = 6
		fallthrough
	case 2 <=  &&  <= 9:
		.compressionLevel = levels[]
		.initDeflate()
		.fill = (*compressor).fillDeflate
		.step = (*compressor).deflate
	default:
		return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", )
	}
	return nil
}

func ( *compressor) ( io.Writer) {
	.w.reset()
	.sync = false
	.err = nil
	switch .compressionLevel.level {
	case NoCompression:
		.windowEnd = 0
	case BestSpeed:
		.windowEnd = 0
		.tokens = .tokens[:0]
		.bestSpeed.reset()
	default:
		.chainHead = -1
		for  := range .hashHead {
			.hashHead[] = 0
		}
		for  := range .hashPrev {
			.hashPrev[] = 0
		}
		.hashOffset = 1
		.index, .windowEnd = 0, 0
		.blockStart, .byteAvailable = 0, false
		.tokens = .tokens[:0]
		.length = minMatchLength - 1
		.offset = 0
		.hash = 0
		.maxInsertIndex = 0
	}
}

func ( *compressor) () error {
	if .err != nil {
		return .err
	}
	.sync = true
	.step()
	if .err != nil {
		return .err
	}
	if .w.writeStoredHeader(0, true); .w.err != nil {
		return .w.err
	}
	.w.flush()
	return .w.err
}

// NewWriter returns a new Writer compressing data at the given level.
// Following zlib, levels range from 1 (BestSpeed) to 9 (BestCompression);
// higher levels typically run slower but compress more. Level 0
// (NoCompression) does not attempt any compression; it only adds the
// necessary DEFLATE framing.
// Level -1 (DefaultCompression) uses the default compression level.
// Level -2 (HuffmanOnly) will use Huffman compression only, giving
// a very fast compression for all types of input, but sacrificing considerable
// compression efficiency.
//
// If level is in the range [-2, 9] then the error returned will be nil.
// Otherwise the error returned will be non-nil.
func ( io.Writer,  int) (*Writer, error) {
	var  Writer
	if  := .d.init(, );  != nil {
		return nil, 
	}
	return &, nil
}

// NewWriterDict is like NewWriter but initializes the new
// Writer with a preset dictionary. The returned Writer behaves
// as if the dictionary had been written to it without producing
// any compressed output. The compressed data written to w
// can only be decompressed by a Reader initialized with the
// same dictionary.
func ( io.Writer,  int,  []byte) (*Writer, error) {
	 := &dictWriter{}
	,  := NewWriter(, )
	if  != nil {
		return nil, 
	}
	.d.fillWindow()
	.dict = append(.dict, ...) // duplicate dictionary for Reset method.
	return , 
}

type dictWriter struct {
	w io.Writer
}

func ( *dictWriter) ( []byte) ( int,  error) {
	return .w.Write()
}

// A Writer takes data written to it and writes the compressed
// form of that data to an underlying writer (see NewWriter).
type Writer struct {
	d    compressor
	dict []byte
}

// Write writes data to w, which will eventually write the
// compressed form of data to its underlying writer.
func ( *Writer) ( []byte) ( int,  error) {
	return .d.write()
}

// Flush flushes any pending data to the underlying writer.
// It is useful mainly in compressed network protocols, to ensure that
// a remote reader has enough data to reconstruct a packet.
// Flush does not return until the data has been written.
// Calling Flush when there is no pending data still causes the Writer
// to emit a sync marker of at least 4 bytes.
// If the underlying writer returns an error, Flush returns that error.
//
// In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
func ( *Writer) () error {
	// For more about flushing:
	// https://www.bolet.org/~pornin/deflate-flush.html
	return .d.syncFlush()
}

// Close flushes and closes the writer.
func ( *Writer) () error {
	return .d.close()
}

// Reset discards the writer's state and makes it equivalent to
// the result of NewWriter or NewWriterDict called with dst
// and w's level and dictionary.
func ( *Writer) ( io.Writer) {
	if ,  := .d.w.writer.(*dictWriter);  {
		// w was created with NewWriterDict
		.w = 
		.d.reset()
		.d.fillWindow(.dict)
	} else {
		// w was created with NewWriter
		.d.reset()
	}
}