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 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. 177 func (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 203 slowPath: 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 223 func (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 235 func (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
