// 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 jpeg

import (
	
)

// maxCodeLength is the maximum (inclusive) number of bits in a Huffman code.
const maxCodeLength = 16

// maxNCodes is the maximum (inclusive) number of codes in a Huffman tree.
const maxNCodes = 256

// lutSize is the log-2 size of the Huffman decoder's look-up table.
const lutSize = 8

// huffman is a Huffman decoder, specified in section C.
type huffman struct {
	// length is the number of codes in the tree.
	nCodes int32
	// lut is the look-up table for the next lutSize bits in the bit-stream.
	// The high 8 bits of the uint16 are the encoded value. The low 8 bits
	// are 1 plus the code length, or 0 if the value is too large to fit in
	// lutSize bits.
	lut [1 << lutSize]uint16
	// vals are the decoded values, sorted by their encoding.
	vals [maxNCodes]uint8
	// minCodes[i] is the minimum code of length i, or -1 if there are no
	// codes of that length.
	minCodes [maxCodeLength]int32
	// maxCodes[i] is the maximum code of length i, or -1 if there are no
	// codes of that length.
	maxCodes [maxCodeLength]int32
	// valsIndices[i] is the index into vals of minCodes[i].
	valsIndices [maxCodeLength]int32
}

// errShortHuffmanData means that an unexpected EOF occurred while decoding
// Huffman data.
var errShortHuffmanData = FormatError("short Huffman data")

// ensureNBits reads bytes from the byte buffer to ensure that d.bits.n is at
// least n. For best performance (avoiding function calls inside hot loops),
// the caller is the one responsible for first checking that d.bits.n < n.
func ( *decoder) ( int32) error {
	for {
		,  := .readByteStuffedByte()
		if  != nil {
			if  == io.EOF {
				return errShortHuffmanData
			}
			return 
		}
		.bits.a = .bits.a<<8 | uint32()
		.bits.n += 8
		if .bits.m == 0 {
			.bits.m = 1 << 7
		} else {
			.bits.m <<= 8
		}
		if .bits.n >=  {
			break
		}
	}
	return nil
}

// receiveExtend is the composition of RECEIVE and EXTEND, specified in section
// F.2.2.1.
func ( *decoder) ( uint8) (int32, error) {
	if .bits.n < int32() {
		if  := .ensureNBits(int32());  != nil {
			return 0, 
		}
	}
	.bits.n -= int32()
	.bits.m >>= 
	 := int32(1) << 
	 := int32(.bits.a>>uint8(.bits.n)) & ( - 1)
	if  < >>1 {
		 += ((-1) << ) + 1
	}
	return , nil
}

// processDHT processes a Define Huffman Table marker, and initializes a huffman
// struct from its contents. Specified in section B.2.4.2.
func ( *decoder) ( int) error {
	for  > 0 {
		if  < 17 {
			return FormatError("DHT has wrong length")
		}
		if  := .readFull(.tmp[:17]);  != nil {
			return 
		}
		 := .tmp[0] >> 4
		if  > maxTc {
			return FormatError("bad Tc value")
		}
		 := .tmp[0] & 0x0f
		// The baseline th <= 1 restriction is specified in table B.5.
		if  > maxTh || (.baseline &&  > 1) {
			return FormatError("bad Th value")
		}
		 := &.huff[][]

		// Read nCodes and h.vals (and derive h.nCodes).
		// nCodes[i] is the number of codes with code length i.
		// h.nCodes is the total number of codes.
		.nCodes = 0
		var  [maxCodeLength]int32
		for  := range  {
			[] = int32(.tmp[+1])
			.nCodes += []
		}
		if .nCodes == 0 {
			return FormatError("Huffman table has zero length")
		}
		if .nCodes > maxNCodes {
			return FormatError("Huffman table has excessive length")
		}
		 -= int(.nCodes) + 17
		if  < 0 {
			return FormatError("DHT has wrong length")
		}
		if  := .readFull(.vals[:.nCodes]);  != nil {
			return 
		}

		// Derive the look-up table.
		for  := range .lut {
			.lut[] = 0
		}
		var ,  uint32
		for  := uint32(0);  < lutSize; ++ {
			 <<= 1
			for  := int32(0);  < []; ++ {
				// The codeLength is 1+i, so shift code by 8-(1+i) to
				// calculate the high bits for every 8-bit sequence
				// whose codeLength's high bits matches code.
				// The high 8 bits of lutValue are the encoded value.
				// The low 8 bits are 1 plus the codeLength.
				 := uint8( << (7 - ))
				 := uint16(.vals[])<<8 | uint16(2+)
				for  := uint8(0);  < 1<<(7-); ++ {
					.lut[|] = 
				}
				++
				++
			}
		}

		// Derive minCodes, maxCodes, and valsIndices.
		var ,  int32
		for ,  := range  {
			if  == 0 {
				.minCodes[] = -1
				.maxCodes[] = -1
				.valsIndices[] = -1
			} else {
				.minCodes[] = 
				.maxCodes[] =  +  - 1
				.valsIndices[] = 
				 += 
				 += 
			}
			 <<= 1
		}
	}
	return nil
}

// decodeHuffman returns the next Huffman-coded value from the bit-stream,
// decoded according to h.
func ( *decoder) ( *huffman) (uint8, error) {
	if .nCodes == 0 {
		return 0, FormatError("uninitialized Huffman table")
	}

	if .bits.n < 8 {
		if  := .ensureNBits(8);  != nil {
			if  != errMissingFF00 &&  != errShortHuffmanData {
				return 0, 
			}
			// There are no more bytes of data in this segment, but we may still
			// be able to read the next symbol out of the previously read bits.
			// First, undo the readByte that the ensureNBits call made.
			if .bytes.nUnreadable != 0 {
				.unreadByteStuffedByte()
			}
			goto 
		}
	}
	if  := .lut[(.bits.a>>uint32(.bits.n-lutSize))&0xff];  != 0 {
		 := ( & 0xff) - 1
		.bits.n -= int32()
		.bits.m >>= 
		return uint8( >> 8), nil
	}

:
	for ,  := 0, int32(0);  < maxCodeLength; ++ {
		if .bits.n == 0 {
			if  := .ensureNBits(1);  != nil {
				return 0, 
			}
		}
		if .bits.a&.bits.m != 0 {
			 |= 1
		}
		.bits.n--
		.bits.m >>= 1
		if  <= .maxCodes[] {
			return .vals[.valsIndices[]+-.minCodes[]], nil
		}
		 <<= 1
	}
	return 0, FormatError("bad Huffman code")
}

func ( *decoder) () (bool, error) {
	if .bits.n == 0 {
		if  := .ensureNBits(1);  != nil {
			return false, 
		}
	}
	 := .bits.a&.bits.m != 0
	.bits.n--
	.bits.m >>= 1
	return , nil
}

func ( *decoder) ( int32) (uint32, error) {
	if .bits.n <  {
		if  := .ensureNBits();  != nil {
			return 0, 
		}
	}
	 := .bits.a >> uint32(.bits.n-)
	 &= (1 << uint32()) - 1
	.bits.n -= 
	.bits.m >>= uint32()
	return , nil
}