libgo/go/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                 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 }