// 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 (
	maxBitsLimit = 16
	// number of valid literals
	literalCount = 286
)

// hcode is a huffman code with a bit code and bit length.
type hcode uint32

func ( hcode) () uint8 {
	return uint8()
}

func ( hcode) () uint64 {
	return uint64( >> 8)
}

func ( hcode) () bool {
	return  == 0
}

type huffmanEncoder struct {
	codes    []hcode
	bitCount [17]int32

	// Allocate a reusable buffer with the longest possible frequency table.
	// Possible lengths are codegenCodeCount, offsetCodeCount and literalCount.
	// The largest of these is literalCount, so we allocate for that case.
	freqcache [literalCount + 1]literalNode
}

type literalNode struct {
	literal uint16
	freq    uint16
}

// A levelInfo describes the state of the constructed tree for a given depth.
type levelInfo struct {
	// Our level.  for better printing
	level int32

	// The frequency of the last node at this level
	lastFreq int32

	// The frequency of the next character to add to this level
	nextCharFreq int32

	// The frequency of the next pair (from level below) to add to this level.
	// Only valid if the "needed" value of the next lower level is 0.
	nextPairFreq int32

	// The number of chains remaining to generate for this level before moving
	// up to the next level
	needed int32
}

// set sets the code and length of an hcode.
func ( *hcode) ( uint16,  uint8) {
	* = hcode() | (hcode() << 8)
}

func ( uint16,  uint8) hcode {
	return hcode() | (hcode() << 8)
}

func ( uint16,  byte) uint16 {
	return bits.Reverse16( << ((16 - ) & 15))
}

func () literalNode { return literalNode{math.MaxUint16, math.MaxUint16} }

func ( int) *huffmanEncoder {
	// Make capacity to next power of two.
	 := uint(bits.Len32(uint32( - 1)))
	return &huffmanEncoder{codes: make([]hcode, , 1<<)}
}

// Generates a HuffmanCode corresponding to the fixed literal table
func () *huffmanEncoder {
	 := newHuffmanEncoder(literalCount)
	 := .codes
	var  uint16
	for  = 0;  < literalCount; ++ {
		var  uint16
		var  uint8
		switch {
		case  < 144:
			// size 8, 000110000  .. 10111111
			 =  + 48
			 = 8
		case  < 256:
			// size 9, 110010000 .. 111111111
			 =  + 400 - 144
			 = 9
		case  < 280:
			// size 7, 0000000 .. 0010111
			 =  - 256
			 = 7
		default:
			// size 8, 11000000 .. 11000111
			 =  + 192 - 280
			 = 8
		}
		[] = newhcode(reverseBits(, ), )
	}
	return 
}

func () *huffmanEncoder {
	 := newHuffmanEncoder(30)
	 := .codes
	for  := range  {
		[] = newhcode(reverseBits(uint16(), 5), 5)
	}
	return 
}

var fixedLiteralEncoding = generateFixedLiteralEncoding()
var fixedOffsetEncoding = generateFixedOffsetEncoding()

func ( *huffmanEncoder) ( []uint16) int {
	var  int
	for ,  := range  {
		if  != 0 {
			 += int() * int(.codes[].len())
		}
	}
	return 
}

func ( *huffmanEncoder) ( []byte) int {
	var  int
	for ,  := range  {
		 += int(.codes[].len())
	}
	return 
}

// canReuseBits returns the number of bits or math.MaxInt32 if the encoder cannot be reused.
func ( *huffmanEncoder) ( []uint16) int {
	var  int
	for ,  := range  {
		if  != 0 {
			 := .codes[]
			if .zero() {
				return math.MaxInt32
			}
			 += int() * int(.len())
		}
	}
	return 
}

// Return the number of literals assigned to each bit size in the Huffman encoding
//
// This method is only called when list.length >= 3
// The cases of 0, 1, and 2 literals are handled by special case code.
//
// list  An array of the literals with non-zero frequencies
//
//	and their associated frequencies. The array is in order of increasing
//	frequency, and has as its last element a special element with frequency
//	MaxInt32
//
// maxBits     The maximum number of bits that should be used to encode any literal.
//
//	Must be less than 16.
//
// return      An integer array in which array[i] indicates the number of literals
//
//	that should be encoded in i bits.
func ( *huffmanEncoder) ( []literalNode,  int32) []int32 {
	if  >= maxBitsLimit {
		panic("flate: maxBits too large")
	}
	 := int32(len())
	 = [0 : +1]
	[] = maxNode()

	// The tree can't have greater depth than n - 1, no matter what. This
	// saves a little bit of work in some small cases
	if  > -1 {
		 =  - 1
	}

	// Create information about each of the levels.
	// A bogus "Level 0" whose sole purpose is so that
	// level1.prev.needed==0.  This makes level1.nextPairFreq
	// be a legitimate value that never gets chosen.
	var  [maxBitsLimit]levelInfo
	// leafCounts[i] counts the number of literals at the left
	// of ancestors of the rightmost node at level i.
	// leafCounts[i][j] is the number of literals at the left
	// of the level j ancestor.
	var  [maxBitsLimit][maxBitsLimit]int32

	// Descending to only have 1 bounds check.
	 := int32([2].freq)
	 := int32([1].freq)
	 := int32([0].freq) + int32([1].freq)

	for  := int32(1);  <= ; ++ {
		// For every level, the first two items are the first two characters.
		// We initialize the levels as if we had already figured this out.
		[] = levelInfo{
			level:        ,
			lastFreq:     ,
			nextCharFreq: ,
			nextPairFreq: ,
		}
		[][] = 2
		if  == 1 {
			[].nextPairFreq = math.MaxInt32
		}
	}

	// We need a total of 2*n - 2 items at top level and have already generated 2.
	[].needed = 2* - 4

	 := uint32()
	for  < 16 {
		 := &[]
		if .nextPairFreq == math.MaxInt32 && .nextCharFreq == math.MaxInt32 {
			// We've run out of both leafs and pairs.
			// End all calculations for this level.
			// To make sure we never come back to this level or any lower level,
			// set nextPairFreq impossibly large.
			.needed = 0
			[+1].nextPairFreq = math.MaxInt32
			++
			continue
		}

		 := .lastFreq
		if .nextCharFreq < .nextPairFreq {
			// The next item on this row is a leaf node.
			 := [][] + 1
			.lastFreq = .nextCharFreq
			// Lower leafCounts are the same of the previous node.
			[][] = 
			 := []
			if .literal < math.MaxUint16 {
				.nextCharFreq = int32(.freq)
			} else {
				.nextCharFreq = math.MaxInt32
			}
		} else {
			// The next item on this row is a pair from the previous row.
			// nextPairFreq isn't valid until we generate two
			// more values in the level below
			.lastFreq = .nextPairFreq
			// Take leaf counts from the lower level, except counts[level] remains the same.
			if true {
				 := [][]
				[] = [-1]
				[][] = 
			} else {
				copy([][:], [-1][:])
			}
			[.level-1].needed = 2
		}

		if .needed--; .needed == 0 {
			// We've done everything we need to do for this level.
			// Continue calculating one level up. Fill in nextPairFreq
			// of that level with the sum of the two nodes we've just calculated on
			// this level.
			if .level ==  {
				// All done!
				break
			}
			[.level+1].nextPairFreq =  + .lastFreq
			++
		} else {
			// If we stole from below, move down temporarily to replenish it.
			for [-1].needed > 0 {
				--
			}
		}
	}

	// Somethings is wrong if at the end, the top level is null or hasn't used
	// all of the leaves.
	if [][] !=  {
		panic("leafCounts[maxBits][maxBits] != n")
	}

	 := .bitCount[:+1]
	 := 1
	 := &[]
	for  := ;  > 0; -- {
		// chain.leafCount gives the number of literals requiring at least "bits"
		// bits to encode.
		[] = [] - [-1]
		++
	}
	return 
}

// Look at the leaves and assign them a bit count and an encoding as specified
// in RFC 1951 3.2.2
func ( *huffmanEncoder) ( []int32,  []literalNode) {
	 := uint16(0)
	for ,  := range  {
		 <<= 1
		if  == 0 ||  == 0 {
			continue
		}
		// The literals list[len(list)-bits] .. list[len(list)-bits]
		// are encoded using "bits" bits, and get the values
		// code, code + 1, ....  The code values are
		// assigned in literal order (not frequency order).
		 := [len()-int():]

		sortByLiteral()
		for ,  := range  {
			.codes[.literal] = newhcode(reverseBits(, uint8()), uint8())
			++
		}
		 = [0 : len()-int()]
	}
}

// Update this Huffman Code object to be the minimum code for the specified frequency count.
//
// freq  An array of frequencies, in which frequency[i] gives the frequency of literal i.
// maxBits  The maximum number of bits to use for any literal.
func ( *huffmanEncoder) ( []uint16,  int32) {
	 := .freqcache[:len()+1]
	 := .codes[:len()]
	// Number of non-zero literals
	 := 0
	// Set list to be the set of all non-zero literals and their frequencies
	for ,  := range  {
		if  != 0 {
			[] = literalNode{uint16(), }
			++
		} else {
			[] = 0
		}
	}
	[] = literalNode{}

	 = [:]
	if  <= 2 {
		// Handle the small cases here, because they are awkward for the general case code. With
		// two or fewer literals, everything has bit length 1.
		for ,  := range  {
			// "list" is in order of increasing literal value.
			.codes[.literal].set(uint16(), 1)
		}
		return
	}
	sortByFreq()

	// Get the number of literals for each bit count
	 := .bitCounts(, )
	// And do the assignment
	.assignEncodingAndSize(, )
}

// atLeastOne clamps the result between 1 and 15.
func ( float32) float32 {
	if  < 1 {
		return 1
	}
	if  > 15 {
		return 15
	}
	return 
}

func ( []byte,  []uint16) {
	if true && len() >= 8<<10 {
		// Split for bigger inputs
		histogramSplit(, )
	} else {
		 = [:256]
		for ,  := range  {
			[]++
		}
	}
}

func ( []byte,  []uint16) {
	// Tested, and slightly faster than 2-way.
	// Writing to separate arrays and combining is also slightly slower.
	 = [:256]
	for len()&3 != 0 {
		[[0]]++
		 = [1:]
	}
	 := len() / 4
	, , ,  := [:], [:], [+:], [++:]
	, ,  = [:len()], [:len()], [:len()]
	for ,  := range  {
		 := &[]
		 := &[[]]
		 := &[[]]
		 := &[[]]
		*++
		*++
		*++
		*++
	}
}