Source file src/image/jpeg/huffman.go

     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	
     5	package jpeg
     6	
     7	import (
     8		"io"
     9	)
    10	
    11	// maxCodeLength is the maximum (inclusive) number of bits in a Huffman code.
    12	const maxCodeLength = 16
    13	
    14	// maxNCodes is the maximum (inclusive) number of codes in a Huffman tree.
    15	const maxNCodes = 256
    16	
    17	// lutSize is the log-2 size of the Huffman decoder's look-up table.
    18	const lutSize = 8
    19	
    20	// huffman is a Huffman decoder, specified in section C.
    21	type 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.
    43	var 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.
    48	func (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.
    73	func (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.
    91	func (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			for i := range h.lut {
   135				h.lut[i] = 0
   136			}
   137			var x, code uint32
   138			for i := uint32(0); i < lutSize; i++ {
   139				code <<= 1
   140				for j := int32(0); j < nCodes[i]; j++ {
   141					// The codeLength is 1+i, so shift code by 8-(1+i) to
   142					// calculate the high bits for every 8-bit sequence
   143					// whose codeLength's high bits matches code.
   144					// The high 8 bits of lutValue are the encoded value.
   145					// The low 8 bits are 1 plus the codeLength.
   146					base := uint8(code << (7 - i))
   147					lutValue := uint16(h.vals[x])<<8 | uint16(2+i)
   148					for k := uint8(0); k < 1<<(7-i); k++ {
   149						h.lut[base|k] = lutValue
   150					}
   151					code++
   152					x++
   153				}
   154			}
   155	
   156			// Derive minCodes, maxCodes, and valsIndices.
   157			var c, index int32
   158			for i, n := range nCodes {
   159				if n == 0 {
   160					h.minCodes[i] = -1
   161					h.maxCodes[i] = -1
   162					h.valsIndices[i] = -1
   163				} else {
   164					h.minCodes[i] = c
   165					h.maxCodes[i] = c + n - 1
   166					h.valsIndices[i] = index
   167					c += n
   168					index += n
   169				}
   170				c <<= 1
   171			}
   172		}
   173		return nil
   174	}
   175	
   176	// decodeHuffman returns the next Huffman-coded value from the bit-stream,
   177	// decoded according to h.
   178	func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
   179		if h.nCodes == 0 {
   180			return 0, FormatError("uninitialized Huffman table")
   181		}
   182	
   183		if d.bits.n < 8 {
   184			if err := d.ensureNBits(8); err != nil {
   185				if err != errMissingFF00 && err != errShortHuffmanData {
   186					return 0, err
   187				}
   188				// There are no more bytes of data in this segment, but we may still
   189				// be able to read the next symbol out of the previously read bits.
   190				// First, undo the readByte that the ensureNBits call made.
   191				if d.bytes.nUnreadable != 0 {
   192					d.unreadByteStuffedByte()
   193				}
   194				goto slowPath
   195			}
   196		}
   197		if v := h.lut[(d.bits.a>>uint32(d.bits.n-lutSize))&0xff]; v != 0 {
   198			n := (v & 0xff) - 1
   199			d.bits.n -= int32(n)
   200			d.bits.m >>= n
   201			return uint8(v >> 8), nil
   202		}
   203	
   204	slowPath:
   205		for i, code := 0, int32(0); i < maxCodeLength; i++ {
   206			if d.bits.n == 0 {
   207				if err := d.ensureNBits(1); err != nil {
   208					return 0, err
   209				}
   210			}
   211			if d.bits.a&d.bits.m != 0 {
   212				code |= 1
   213			}
   214			d.bits.n--
   215			d.bits.m >>= 1
   216			if code <= h.maxCodes[i] {
   217				return h.vals[h.valsIndices[i]+code-h.minCodes[i]], nil
   218			}
   219			code <<= 1
   220		}
   221		return 0, FormatError("bad Huffman code")
   222	}
   223	
   224	func (d *decoder) decodeBit() (bool, error) {
   225		if d.bits.n == 0 {
   226			if err := d.ensureNBits(1); err != nil {
   227				return false, err
   228			}
   229		}
   230		ret := d.bits.a&d.bits.m != 0
   231		d.bits.n--
   232		d.bits.m >>= 1
   233		return ret, nil
   234	}
   235	
   236	func (d *decoder) decodeBits(n int32) (uint32, error) {
   237		if d.bits.n < n {
   238			if err := d.ensureNBits(n); err != nil {
   239				return 0, err
   240			}
   241		}
   242		ret := d.bits.a >> uint32(d.bits.n-n)
   243		ret &= (1 << uint32(n)) - 1
   244		d.bits.n -= n
   245		d.bits.m >>= uint32(n)
   246		return ret, nil
   247	}
   248	

View as plain text