1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package jpeg
6
7import (
8	"io"
9)
10
11// maxCodeLength is the maximum (inclusive) number of bits in a Huffman code.
12const maxCodeLength = 16
13
14// maxNCodes is the maximum (inclusive) number of codes in a Huffman tree.
15const maxNCodes = 256
16
17// lutSize is the log-2 size of the Huffman decoder's look-up table.
18const lutSize = 8
19
20// huffman is a Huffman decoder, specified in section C.
21type huffman struct {
22	// length is the number of codes in the tree.
23	nCodes int32
24	// lut is the look-up table for the next lutSize bits in the bit-stream.
25	// The high 8 bits of the uint16 are the encoded value. The low 8 bits
26	// are 1 plus the code length, or 0 if the value is too large to fit in
27	// lutSize bits.
28	lut [1 << lutSize]uint16
29	// vals are the decoded values, sorted by their encoding.
30	vals [maxNCodes]uint8
31	// minCodes[i] is the minimum code of length i, or -1 if there are no
32	// codes of that length.
33	minCodes [maxCodeLength]int32
34	// maxCodes[i] is the maximum code of length i, or -1 if there are no
35	// codes of that length.
36	maxCodes [maxCodeLength]int32
37	// valsIndices[i] is the index into vals of minCodes[i].
38	valsIndices [maxCodeLength]int32
39}
40
41// errShortHuffmanData means that an unexpected EOF occurred while decoding
42// Huffman data.
43var errShortHuffmanData = FormatError("short Huffman data")
44
45// ensureNBits reads bytes from the byte buffer to ensure that d.bits.n is at
46// least n. For best performance (avoiding function calls inside hot loops),
47// the caller is the one responsible for first checking that d.bits.n < n.
48func (d *decoder) ensureNBits(n int32) error {
49	for {
50		c, err := d.readByteStuffedByte()
51		if err != nil {
52			if err == io.ErrUnexpectedEOF {
53				return errShortHuffmanData
54			}
55			return err
56		}
57		d.bits.a = d.bits.a<<8 | uint32(c)
58		d.bits.n += 8
59		if d.bits.m == 0 {
60			d.bits.m = 1 << 7
61		} else {
62			d.bits.m <<= 8
63		}
64		if d.bits.n >= n {
65			break
66		}
67	}
68	return nil
69}
70
71// receiveExtend is the composition of RECEIVE and EXTEND, specified in section
72// F.2.2.1.
73func (d *decoder) receiveExtend(t uint8) (int32, error) {
74	if d.bits.n < int32(t) {
75		if err := d.ensureNBits(int32(t)); err != nil {
76			return 0, err
77		}
78	}
79	d.bits.n -= int32(t)
80	d.bits.m >>= t
81	s := int32(1) << t
82	x := int32(d.bits.a>>uint8(d.bits.n)) & (s - 1)
83	if x < s>>1 {
84		x += ((-1) << t) + 1
85	}
86	return x, nil
87}
88
89// processDHT processes a Define Huffman Table marker, and initializes a huffman
90// struct from its contents. Specified in section B.2.4.2.
91func (d *decoder) processDHT(n int) error {
92	for n > 0 {
93		if n < 17 {
94			return FormatError("DHT has wrong length")
95		}
96		if err := d.readFull(d.tmp[:17]); err != nil {
97			return err
98		}
99		tc := d.tmp[0] >> 4
100		if tc > maxTc {
101			return FormatError("bad Tc value")
102		}
103		th := d.tmp[0] & 0x0f
104		// The baseline th <= 1 restriction is specified in table B.5.
105		if th > maxTh || (d.baseline && th > 1) {
106			return FormatError("bad Th value")
107		}
108		h := &d.huff[tc][th]
109
110		// Read nCodes and h.vals (and derive h.nCodes).
111		// nCodes[i] is the number of codes with code length i.
112		// h.nCodes is the total number of codes.
113		h.nCodes = 0
114		var nCodes [maxCodeLength]int32
115		for i := range nCodes {
116			nCodes[i] = int32(d.tmp[i+1])
117			h.nCodes += nCodes[i]
118		}
119		if h.nCodes == 0 {
120			return FormatError("Huffman table has zero length")
121		}
122		if h.nCodes > maxNCodes {
123			return FormatError("Huffman table has excessive length")
124		}
125		n -= int(h.nCodes) + 17
126		if n < 0 {
127			return FormatError("DHT has wrong length")
128		}
129		if err := d.readFull(h.vals[:h.nCodes]); err != nil {
130			return err
131		}
132
133		// Derive the look-up table.
134		clear(h.lut[:])
135		var x, code uint32
136		for i := uint32(0); i < lutSize; i++ {
137			code <<= 1
138			for j := int32(0); j < nCodes[i]; j++ {
139				// The codeLength is 1+i, so shift code by 8-(1+i) to
140				// calculate the high bits for every 8-bit sequence
141				// whose codeLength's high bits matches code.
142				// The high 8 bits of lutValue are the encoded value.
143				// The low 8 bits are 1 plus the codeLength.
144				base := uint8(code << (7 - i))
145				lutValue := uint16(h.vals[x])<<8 | uint16(2+i)
146				for k := uint8(0); k < 1<<(7-i); k++ {
147					h.lut[base|k] = lutValue
148				}
149				code++
150				x++
151			}
152		}
153
154		// Derive minCodes, maxCodes, and valsIndices.
155		var c, index int32
156		for i, n := range nCodes {
157			if n == 0 {
158				h.minCodes[i] = -1
159				h.maxCodes[i] = -1
160				h.valsIndices[i] = -1
161			} else {
162				h.minCodes[i] = c
163				h.maxCodes[i] = c + n - 1
164				h.valsIndices[i] = index
165				c += n
166				index += n
167			}
168			c <<= 1
169		}
170	}
171	return nil
172}
173
174// decodeHuffman returns the next Huffman-coded value from the bit-stream,
175// decoded according to h.
176func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
177	if h.nCodes == 0 {
178		return 0, FormatError("uninitialized Huffman table")
179	}
180
181	if d.bits.n < 8 {
182		if err := d.ensureNBits(8); err != nil {
183			if err != errMissingFF00 && err != errShortHuffmanData {
184				return 0, err
185			}
186			// There are no more bytes of data in this segment, but we may still
187			// be able to read the next symbol out of the previously read bits.
188			// First, undo the readByte that the ensureNBits call made.
189			if d.bytes.nUnreadable != 0 {
190				d.unreadByteStuffedByte()
191			}
192			goto slowPath
193		}
194	}
195	if v := h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]; v != 0 {
196		n := (v & 0xff) - 1
197		d.bits.n -= int32(n)
198		d.bits.m >>= n
199		return uint8(v >> 8), nil
200	}
201
202slowPath:
203	for i, code := 0, int32(0); i < maxCodeLength; i++ {
204		if d.bits.n == 0 {
205			if err := d.ensureNBits(1); err != nil {
206				return 0, err
207			}
208		}
209		if d.bits.a&d.bits.m != 0 {
210			code |= 1
211		}
212		d.bits.n--
213		d.bits.m >>= 1
214		if code <= h.maxCodes[i] {
215			return h.vals[h.valsIndices[i]+code-h.minCodes[i]], nil
216		}
217		code <<= 1
218	}
219	return 0, FormatError("bad Huffman code")
220}
221
222func (d *decoder) decodeBit() (bool, error) {
223	if d.bits.n == 0 {
224		if err := d.ensureNBits(1); err != nil {
225			return false, err
226		}
227	}
228	ret := d.bits.a&d.bits.m != 0
229	d.bits.n--
230	d.bits.m >>= 1
231	return ret, nil
232}
233
234func (d *decoder) decodeBits(n int32) (uint32, error) {
235	if d.bits.n < n {
236		if err := d.ensureNBits(n); err != nil {
237			return 0, err
238		}
239	}
240	ret := d.bits.a >> uint32(d.bits.n-n)
241	ret &= (1 << uint32(n)) - 1
242	d.bits.n -= n
243	d.bits.m >>= uint32(n)
244	return ret, nil
245}
246