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.EOF {
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		if th > maxTh || !d.progressive && th > 1 {
105			return FormatError("bad Th value")
106		}
107		h := &d.huff[tc][th]
108
109		// Read nCodes and h.vals (and derive h.nCodes).
110		// nCodes[i] is the number of codes with code length i.
111		// h.nCodes is the total number of codes.
112		h.nCodes = 0
113		var nCodes [maxCodeLength]int32
114		for i := range nCodes {
115			nCodes[i] = int32(d.tmp[i+1])
116			h.nCodes += nCodes[i]
117		}
118		if h.nCodes == 0 {
119			return FormatError("Huffman table has zero length")
120		}
121		if h.nCodes > maxNCodes {
122			return FormatError("Huffman table has excessive length")
123		}
124		n -= int(h.nCodes) + 17
125		if n < 0 {
126			return FormatError("DHT has wrong length")
127		}
128		if err := d.readFull(h.vals[:h.nCodes]); err != nil {
129			return err
130		}
131
132		// Derive the look-up table.
133		for i := range h.lut {
134			h.lut[i] = 0
135		}
136		var x, code uint32
137		for i := uint32(0); i < lutSize; i++ {
138			code <<= 1
139			for j := int32(0); j < nCodes[i]; j++ {
140				// The codeLength is 1+i, so shift code by 8-(1+i) to
141				// calculate the high bits for every 8-bit sequence
142				// whose codeLength's high bits matches code.
143				// The high 8 bits of lutValue are the encoded value.
144				// The low 8 bits are 1 plus the codeLength.
145				base := uint8(code << (7 - i))
146				lutValue := uint16(h.vals[x])<<8 | uint16(2+i)
147				for k := uint8(0); k < 1<<(7-i); k++ {
148					h.lut[base|k] = lutValue
149				}
150				code++
151				x++
152			}
153		}
154
155		// Derive minCodes, maxCodes, and valsIndices.
156		var c, index int32
157		for i, n := range nCodes {
158			if n == 0 {
159				h.minCodes[i] = -1
160				h.maxCodes[i] = -1
161				h.valsIndices[i] = -1
162			} else {
163				h.minCodes[i] = c
164				h.maxCodes[i] = c + n - 1
165				h.valsIndices[i] = index
166				c += n
167				index += n
168			}
169			c <<= 1
170		}
171	}
172	return nil
173}
174
175// decodeHuffman returns the next Huffman-coded value from the bit-stream,
176// decoded according to h.
177func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
178	if h.nCodes == 0 {
179		return 0, FormatError("uninitialized Huffman table")
180	}
181
182	if d.bits.n < 8 {
183		if err := d.ensureNBits(8); err != nil {
184			if err != errMissingFF00 && err != errShortHuffmanData {
185				return 0, err
186			}
187			// There are no more bytes of data in this segment, but we may still
188			// be able to read the next symbol out of the previously read bits.
189			// First, undo the readByte that the ensureNBits call made.
190			if d.bytes.nUnreadable != 0 {
191				d.unreadByteStuffedByte()
192			}
193			goto slowPath
194		}
195	}
196	if v := h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]; v != 0 {
197		n := (v & 0xff) - 1
198		d.bits.n -= int32(n)
199		d.bits.m >>= n
200		return uint8(v >> 8), nil
201	}
202
203slowPath:
204	for i, code := 0, int32(0); i < maxCodeLength; i++ {
205		if d.bits.n == 0 {
206			if err := d.ensureNBits(1); err != nil {
207				return 0, err
208			}
209		}
210		if d.bits.a&d.bits.m != 0 {
211			code |= 1
212		}
213		d.bits.n--
214		d.bits.m >>= 1
215		if code <= h.maxCodes[i] {
216			return h.vals[h.valsIndices[i]+code-h.minCodes[i]], nil
217		}
218		code <<= 1
219	}
220	return 0, FormatError("bad Huffman code")
221}
222
223func (d *decoder) decodeBit() (bool, error) {
224	if d.bits.n == 0 {
225		if err := d.ensureNBits(1); err != nil {
226			return false, err
227		}
228	}
229	ret := d.bits.a&d.bits.m != 0
230	d.bits.n--
231	d.bits.m >>= 1
232	return ret, nil
233}
234
235func (d *decoder) decodeBits(n int32) (uint32, error) {
236	if d.bits.n < n {
237		if err := d.ensureNBits(n); err != nil {
238			return 0, err
239		}
240	}
241	ret := d.bits.a >> uint32(d.bits.n-n)
242	ret &= (1 << uint32(n)) - 1
243	d.bits.n -= n
244	d.bits.m >>= uint32(n)
245	return ret, nil
246}
247