Source file src/pkg/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 "io"
     8	
     9	// Each code is at most 16 bits long.
    10	const maxCodeLength = 16
    11	
    12	// Each decoded value is a uint8, so there are at most 256 such values.
    13	const maxNumValues = 256
    14	
    15	// Bit stream for the Huffman decoder.
    16	// The n least significant bits of a form the unread bits, to be read in MSB to LSB order.
    17	type bits struct {
    18		a int // accumulator.
    19		n int // the number of unread bits in a.
    20		m int // mask. m==1<<(n-1) when n>0, with m==0 when n==0.
    21	}
    22	
    23	// Huffman table decoder, specified in section C.
    24	type huffman struct {
    25		l        [maxCodeLength]int
    26		length   int                 // sum of l[i].
    27		val      [maxNumValues]uint8 // the decoded values, as sorted by their encoding.
    28		size     [maxNumValues]int   // size[i] is the number of bits to encode val[i].
    29		code     [maxNumValues]int   // code[i] is the encoding of val[i].
    30		minCode  [maxCodeLength]int  // min codes of length i, or -1 if no codes of that length.
    31		maxCode  [maxCodeLength]int  // max codes of length i, or -1 if no codes of that length.
    32		valIndex [maxCodeLength]int  // index into val of minCode[i].
    33	}
    34	
    35	// Reads bytes from the io.Reader to ensure that bits.n is at least n.
    36	func (d *decoder) ensureNBits(n int) error {
    37		for d.b.n < n {
    38			c, err := d.r.ReadByte()
    39			if err != nil {
    40				return err
    41			}
    42			d.b.a = d.b.a<<8 | int(c)
    43			d.b.n += 8
    44			if d.b.m == 0 {
    45				d.b.m = 1 << 7
    46			} else {
    47				d.b.m <<= 8
    48			}
    49			// Byte stuffing, specified in section F.1.2.3.
    50			if c == 0xff {
    51				c, err = d.r.ReadByte()
    52				if err != nil {
    53					return err
    54				}
    55				if c != 0x00 {
    56					return FormatError("missing 0xff00 sequence")
    57				}
    58			}
    59		}
    60		return nil
    61	}
    62	
    63	// The composition of RECEIVE and EXTEND, specified in section F.2.2.1.
    64	func (d *decoder) receiveExtend(t uint8) (int, error) {
    65		err := d.ensureNBits(int(t))
    66		if err != nil {
    67			return 0, err
    68		}
    69		d.b.n -= int(t)
    70		d.b.m >>= t
    71		s := 1 << t
    72		x := (d.b.a >> uint8(d.b.n)) & (s - 1)
    73		if x < s>>1 {
    74			x += ((-1) << t) + 1
    75		}
    76		return x, nil
    77	}
    78	
    79	// Processes a Define Huffman Table marker, and initializes a huffman struct from its contents.
    80	// Specified in section B.2.4.2.
    81	func (d *decoder) processDHT(n int) error {
    82		for n > 0 {
    83			if n < 17 {
    84				return FormatError("DHT has wrong length")
    85			}
    86			_, err := io.ReadFull(d.r, d.tmp[0:17])
    87			if err != nil {
    88				return err
    89			}
    90			tc := d.tmp[0] >> 4
    91			if tc > maxTc {
    92				return FormatError("bad Tc value")
    93			}
    94			th := d.tmp[0] & 0x0f
    95			const isBaseline = true // Progressive mode is not yet supported.
    96			if th > maxTh || isBaseline && th > 1 {
    97				return FormatError("bad Th value")
    98			}
    99			h := &d.huff[tc][th]
   100	
   101			// Read l and val (and derive length).
   102			h.length = 0
   103			for i := 0; i < maxCodeLength; i++ {
   104				h.l[i] = int(d.tmp[i+1])
   105				h.length += h.l[i]
   106			}
   107			if h.length == 0 {
   108				return FormatError("Huffman table has zero length")
   109			}
   110			if h.length > maxNumValues {
   111				return FormatError("Huffman table has excessive length")
   112			}
   113			n -= h.length + 17
   114			if n < 0 {
   115				return FormatError("DHT has wrong length")
   116			}
   117			_, err = io.ReadFull(d.r, h.val[0:h.length])
   118			if err != nil {
   119				return err
   120			}
   121	
   122			// Derive size.
   123			k := 0
   124			for i := 0; i < maxCodeLength; i++ {
   125				for j := 0; j < h.l[i]; j++ {
   126					h.size[k] = i + 1
   127					k++
   128				}
   129			}
   130	
   131			// Derive code.
   132			code := 0
   133			size := h.size[0]
   134			for i := 0; i < h.length; i++ {
   135				if size != h.size[i] {
   136					code <<= uint8(h.size[i] - size)
   137					size = h.size[i]
   138				}
   139				h.code[i] = code
   140				code++
   141			}
   142	
   143			// Derive minCode, maxCode, and valIndex.
   144			k = 0
   145			index := 0
   146			for i := 0; i < maxCodeLength; i++ {
   147				if h.l[i] == 0 {
   148					h.minCode[i] = -1
   149					h.maxCode[i] = -1
   150					h.valIndex[i] = -1
   151				} else {
   152					h.minCode[i] = k
   153					h.maxCode[i] = k + h.l[i] - 1
   154					h.valIndex[i] = index
   155					k += h.l[i]
   156					index += h.l[i]
   157				}
   158				k <<= 1
   159			}
   160		}
   161		return nil
   162	}
   163	
   164	// Returns the next Huffman-coded value from the bit stream, decoded according to h.
   165	// TODO(nigeltao): This decoding algorithm is simple, but slow. A lookahead table, instead of always
   166	// peeling off only 1 bit at at time, ought to be faster.
   167	func (d *decoder) decodeHuffman(h *huffman) (uint8, error) {
   168		if h.length == 0 {
   169			return 0, FormatError("uninitialized Huffman table")
   170		}
   171		for i, code := 0, 0; i < maxCodeLength; i++ {
   172			err := d.ensureNBits(1)
   173			if err != nil {
   174				return 0, err
   175			}
   176			if d.b.a&d.b.m != 0 {
   177				code |= 1
   178			}
   179			d.b.n--
   180			d.b.m >>= 1
   181			if code <= h.maxCode[i] {
   182				return h.val[h.valIndex[i]+code-h.minCode[i]], nil
   183			}
   184			code <<= 1
   185		}
   186		return 0, FormatError("bad Huffman code")
   187	}