// Copyright 2014 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 hpack

import (
	
	
	
	
)

var bufPool = sync.Pool{
	New: func() interface{} { return new(bytes.Buffer) },
}

// HuffmanDecode decodes the string in v and writes the expanded
// result to w, returning the number of bytes written to w and the
// Write call's return value. At most one Write call is made.
func ( io.Writer,  []byte) (int, error) {
	 := bufPool.Get().(*bytes.Buffer)
	.Reset()
	defer bufPool.Put()
	if  := huffmanDecode(, 0, );  != nil {
		return 0, 
	}
	return .Write(.Bytes())
}

// HuffmanDecodeToString decodes the string in v.
func ( []byte) (string, error) {
	 := bufPool.Get().(*bytes.Buffer)
	.Reset()
	defer bufPool.Put()
	if  := huffmanDecode(, 0, );  != nil {
		return "", 
	}
	return .String(), nil
}

// ErrInvalidHuffman is returned for errors found decoding
// Huffman-encoded strings.
var ErrInvalidHuffman = errors.New("hpack: invalid Huffman-encoded data")

// huffmanDecode decodes v to buf.
// If maxLen is greater than 0, attempts to write more to buf than
// maxLen bytes will return ErrStringLength.
func ( *bytes.Buffer,  int,  []byte) error {
	 := getRootHuffmanNode()
	 := 
	// cur is the bit buffer that has not been fed into n.
	// cbits is the number of low order bits in cur that are valid.
	// sbits is the number of bits of the symbol prefix being decoded.
	, ,  := uint(0), uint8(0), uint8(0)
	for ,  := range  {
		 = <<8 | uint()
		 += 8
		 += 8
		for  >= 8 {
			 := byte( >> ( - 8))
			 = .children[]
			if  == nil {
				return ErrInvalidHuffman
			}
			if .children == nil {
				if  != 0 && .Len() ==  {
					return ErrStringLength
				}
				.WriteByte(.sym)
				 -= .codeLen
				 = 
				 = 
			} else {
				 -= 8
			}
		}
	}
	for  > 0 {
		 = .children[byte(<<(8-))]
		if  == nil {
			return ErrInvalidHuffman
		}
		if .children != nil || .codeLen >  {
			break
		}
		if  != 0 && .Len() ==  {
			return ErrStringLength
		}
		.WriteByte(.sym)
		 -= .codeLen
		 = 
		 = 
	}
	if  > 7 {
		// Either there was an incomplete symbol, or overlong padding.
		// Both are decoding errors per RFC 7541 section 5.2.
		return ErrInvalidHuffman
	}
	if  := uint(1<< - 1); & !=  {
		// Trailing bits must be a prefix of EOS per RFC 7541 section 5.2.
		return ErrInvalidHuffman
	}

	return nil
}

// incomparable is a zero-width, non-comparable type. Adding it to a struct
// makes that struct also non-comparable, and generally doesn't add
// any size (as long as it's first).
type incomparable [0]func()

type node struct {
	_ incomparable

	// children is non-nil for internal nodes
	children *[256]*node

	// The following are only valid if children is nil:
	codeLen uint8 // number of bits that led to the output of sym
	sym     byte  // output symbol
}

func () *node {
	return &node{children: new([256]*node)}
}

var (
	buildRootOnce       sync.Once
	lazyRootHuffmanNode *node
)

func () *node {
	buildRootOnce.Do(buildRootHuffmanNode)
	return lazyRootHuffmanNode
}

func () {
	if len(huffmanCodes) != 256 {
		panic("unexpected size")
	}
	lazyRootHuffmanNode = newInternalNode()
	// allocate a leaf node for each of the 256 symbols
	 := new([256]node)

	for ,  := range huffmanCodes {
		 := huffmanCodeLen[]

		 := lazyRootHuffmanNode
		for  > 8 {
			 -= 8
			 := uint8( >> )
			if .children[] == nil {
				.children[] = newInternalNode()
			}
			 = .children[]
		}
		 := 8 - 
		,  := int(uint8(<<)), int(1<<)

		[].sym = byte()
		[].codeLen = 
		for  := ;  < +; ++ {
			.children[] = &[]
		}
	}
}

// AppendHuffmanString appends s, as encoded in Huffman codes, to dst
// and returns the extended buffer.
func ( []byte,  string) []byte {
	// This relies on the maximum huffman code length being 30 (See tables.go huffmanCodeLen array)
	// So if a uint64 buffer has less than 32 valid bits can always accommodate another huffmanCode.
	var (
		 uint64 // buffer
		 uint   // number valid of bits present in x
	)
	for  := 0;  < len(); ++ {
		 := []
		 += uint(huffmanCodeLen[])
		 <<= huffmanCodeLen[] % 64
		 |= uint64(huffmanCodes[])
		if  >= 32 {
			 %= 32             // Normally would be -= 32 but %= 32 informs compiler 0 <= n <= 31 for upcoming shift
			 := uint32( >> ) // Compiler doesn't combine memory writes if y isn't uint32
			 = append(, byte(>>24), byte(>>16), byte(>>8), byte())
		}
	}
	// Add padding bits if necessary
	if  :=  % 8;  > 0 {
		const (
			    = 0x3fffffff
			   = 30
			 =  >> ( - 8)
		)
		 := 8 - 
		 = ( << ) | ( >> )
		 +=  // 8 now divides into n exactly
	}
	// n in (0, 8, 16, 24, 32)
	switch  / 8 {
	case 0:
		return 
	case 1:
		return append(, byte())
	case 2:
		 := uint16()
		return append(, byte(>>8), byte())
	case 3:
		 := uint16( >> 8)
		return append(, byte(>>8), byte(), byte())
	}
	//	case 4:
	 := uint32()
	return append(, byte(>>24), byte(>>16), byte(>>8), byte())
}

// HuffmanEncodeLength returns the number of bytes required to encode
// s in Huffman codes. The result is round up to byte boundary.
func ( string) uint64 {
	 := uint64(0)
	for  := 0;  < len(); ++ {
		 += uint64(huffmanCodeLen[[]])
	}
	return ( + 7) / 8
}