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 }