// 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 (
	// bits 0-16  	xoffset = offset - MIN_OFFSET_SIZE, or literal - 16 bits
	// bits 16-22	offsetcode - 5 bits
	// bits 22-30   xlength = length - MIN_MATCH_LENGTH - 8 bits
	// bits 30-32   type   0 = literal  1=EOF  2=Match   3=Unused - 2 bits
	lengthShift         = 22
	offsetMask          = 1<<lengthShift - 1
	typeMask            = 3 << 30
	literalType         = 0 << 30
	matchType           = 1 << 30
	matchOffsetOnlyMask = 0xffff
)

// The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
// is lengthCodes[length - MIN_MATCH_LENGTH]
var lengthCodes = [256]uint8{
	0, 1, 2, 3, 4, 5, 6, 7, 8, 8,
	9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
	13, 13, 13, 13, 14, 14, 14, 14, 15, 15,
	15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
	17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
	18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
	19, 19, 19, 19, 20, 20, 20, 20, 20, 20,
	20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
	21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
	21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
	22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
	22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
	23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
	24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
	24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
	24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 26, 26, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 27, 28,
}

// lengthCodes1 is length codes, but starting at 1.
var lengthCodes1 = [256]uint8{
	1, 2, 3, 4, 5, 6, 7, 8, 9, 9,
	10, 10, 11, 11, 12, 12, 13, 13, 13, 13,
	14, 14, 14, 14, 15, 15, 15, 15, 16, 16,
	16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
	18, 18, 18, 18, 18, 18, 18, 18, 19, 19,
	19, 19, 19, 19, 19, 19, 20, 20, 20, 20,
	20, 20, 20, 20, 21, 21, 21, 21, 21, 21,
	21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
	22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
	22, 22, 22, 22, 22, 22, 23, 23, 23, 23,
	23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
	23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
	24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 28, 28, 28, 28, 28, 28,
	28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	28, 28, 28, 28, 28, 29,
}

var offsetCodes = [256]uint32{
	0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
	8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
	10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
	11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
	12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
	13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
	13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
	14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
	15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
}

// offsetCodes14 are offsetCodes, but with 14 added.
var offsetCodes14 = [256]uint32{
	14, 15, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
	22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
	24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
	25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
	27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
	29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
}

type token uint32

type tokens struct {
	extraHist [32]uint16  // codes 256->maxnumlit
	offHist   [32]uint16  // offset codes
	litHist   [256]uint16 // codes 0->255
	nFilled   int
	n         uint16 // Must be able to contain maxStoreBlockSize
	tokens    [maxStoreBlockSize + 1]token
}

func ( *tokens) () {
	if .n == 0 {
		return
	}
	.n = 0
	.nFilled = 0
	for  := range .litHist[:] {
		.litHist[] = 0
	}
	for  := range .extraHist[:] {
		.extraHist[] = 0
	}
	for  := range .offHist[:] {
		.offHist[] = 0
	}
}

func ( *tokens) () {
	if .n == 0 {
		return
	}
	for ,  := range .litHist[:] {
		if  == 0 {
			.litHist[] = 1
			.nFilled++
		}
	}
	for ,  := range .extraHist[:literalCount-256] {
		if  == 0 {
			.nFilled++
			.extraHist[] = 1
		}
	}
	for ,  := range .offHist[:offsetCodeCount] {
		if  == 0 {
			.offHist[] = 1
		}
	}
}

func ( []token) tokens {
	var  tokens
	.indexTokens()
	return 
}

func ( *tokens) ( []token) {
	.Reset()
	for ,  := range  {
		if  < matchType {
			.AddLiteral(.literal())
			continue
		}
		.AddMatch(uint32(.length()), .offset()&matchOffsetOnlyMask)
	}
}

// emitLiteral writes a literal chunk and returns the number of bytes written.
func ( *tokens,  []byte) {
	for ,  := range  {
		.tokens[.n] = token()
		.litHist[]++
		.n++
	}
}

func ( *tokens) ( byte) {
	.tokens[.n] = token()
	.litHist[]++
	.n++
}

// from https://stackoverflow.com/a/28730362
func ( float32) float32 {
	 := int32(math.Float32bits())
	 := (float32)((( >> 23) & 255) - 128)
	 &= -0x7f800001
	 += 127 << 23
	 := math.Float32frombits(uint32())
	 += ((-0.34484843)*+2.02466578)* - 0.67487759
	return 
}

// EstimatedBits will return an minimum size estimated by an *optimal*
// compression of the block.
// The size of the block
func ( *tokens) () int {
	 := float32(0)
	 := int(0)
	 := 0
	 := int(.n) + .nFilled
	if  > 0 {
		 := 1.0 / float32()
		for ,  := range .litHist[:] {
			if  > 0 {
				 := float32()
				 += atLeastOne(-mFastLog2(*)) * 
			}
		}
		// Just add 15 for EOB
		 += 15
		for ,  := range .extraHist[1 : literalCount-256] {
			if  > 0 {
				 := float32()
				 += atLeastOne(-mFastLog2(*)) * 
				 += int(lengthExtraBits[&31]) * int()
				 += int()
			}
		}
	}
	if  > 0 {
		 := 1.0 / float32()
		for ,  := range .offHist[:offsetCodeCount] {
			if  > 0 {
				 := float32()
				 += atLeastOne(-mFastLog2(*)) * 
				 += int(offsetExtraBits[&31]) * int()
			}
		}
	}
	return int() + 
}

// AddMatch adds a match to the tokens.
// This function is very sensitive to inlining and right on the border.
func ( *tokens) ( uint32,  uint32) {
	if debugDeflate {
		if  >= maxMatchLength+baseMatchLength {
			panic(fmt.Errorf("invalid length: %v", ))
		}
		if  >= maxMatchOffset+baseMatchOffset {
			panic(fmt.Errorf("invalid offset: %v", ))
		}
	}
	 := offsetCode()
	 |=  << 16

	.extraHist[lengthCodes1[uint8()]]++
	.offHist[&31]++
	.tokens[.n] = token(matchType | <<lengthShift | )
	.n++
}

// AddMatchLong adds a match to the tokens, potentially longer than max match length.
// Length should NOT have the base subtracted, only offset should.
func ( *tokens) ( int32,  uint32) {
	if debugDeflate {
		if  >= maxMatchOffset+baseMatchOffset {
			panic(fmt.Errorf("invalid offset: %v", ))
		}
	}
	 := offsetCode()
	 |=  << 16
	for  > 0 {
		 := 
		if  > 258 {
			// We need to have at least baseMatchLength left over for next loop.
			if  > 258+baseMatchLength {
				 = 258
			} else {
				 = 258 - baseMatchLength
			}
		}
		 -= 
		 -= baseMatchLength
		.extraHist[lengthCodes1[uint8()]]++
		.offHist[&31]++
		.tokens[.n] = token(matchType | uint32()<<lengthShift | )
		.n++
	}
}

func ( *tokens) () {
	.tokens[.n] = token(endBlockMarker)
	.extraHist[0]++
	.n++
}

func ( *tokens) () []token {
	return .tokens[:.n]
}

// VarInt returns the tokens as varint encoded bytes.
func ( *tokens) () []byte {
	var  = make([]byte, binary.MaxVarintLen32*int(.n))
	var  int
	for ,  := range .tokens[:.n] {
		 += binary.PutUvarint([:], uint64())
	}
	return [:]
}

// FromVarInt restores t to the varint encoded tokens provided.
// Any data in t is removed.
func ( *tokens) ( []byte) error {
	var  = bytes.NewReader()
	var  []token
	for {
		,  := binary.ReadUvarint()
		if  == io.EOF {
			break
		}
		if  != nil {
			return 
		}
		 = append(, token())
	}
	.indexTokens()
	return nil
}

// Returns the type of a token
func ( token) () uint32 { return uint32() & typeMask }

// Returns the literal of a literal token
func ( token) () uint8 { return uint8() }

// Returns the extra offset of a match token
func ( token) () uint32 { return uint32() & offsetMask }

func ( token) () uint8 { return uint8( >> lengthShift) }

// Convert length to code.
func ( uint8) uint8 { return lengthCodes[] }

// Returns the offset code corresponding to a specific offset
func ( uint32) uint32 {
	if false {
		if  < uint32(len(offsetCodes)) {
			return offsetCodes[&255]
		} else if >>7 < uint32(len(offsetCodes)) {
			return offsetCodes[(>>7)&255] + 14
		} else {
			return offsetCodes[(>>14)&255] + 28
		}
	}
	if  < uint32(len(offsetCodes)) {
		return offsetCodes[uint8()]
	}
	return offsetCodes14[uint8(>>7)]
}