libgo/go/compress/flate/inflate.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 flate implements the DEFLATE compressed data format, described in
   6 // RFC 1951.  The gzip and zlib packages implement access to DEFLATE-based file
   7 // formats.
   8 package flate
   9
  10 import (
  11         "bufio"
  12         "io"
  13         "strconv"
  14 )
  15
  16 const (
  17         maxCodeLen = 16    // max length of Huffman code
  18         maxHist    = 32768 // max history required
  19         // The next three numbers come from the RFC, section 3.2.7.
  20         maxLit   = 286
  21         maxDist  = 32
  22         numCodes = 19 // number of codes in Huffman meta-code
  23 )
  24
  25 // A CorruptInputError reports the presence of corrupt input at a given offset.
  26 type CorruptInputError int64
  27
  28 func (e CorruptInputError) Error() string {
  29         return "flate: corrupt input before offset " + strconv.FormatInt(int64(e), 10)
  30 }
  31
  32 // An InternalError reports an error in the flate code itself.
  33 type InternalError string
  34
  35 func (e InternalError) Error() string { return "flate: internal error: " + string(e) }
  36
  37 // A ReadError reports an error encountered while reading input.
  38 type ReadError struct {
  39         Offset int64 // byte offset where error occurred
  40         Err    error // error returned by underlying Read
  41 }
  42
  43 func (e *ReadError) Error() string {
  44         return "flate: read error at offset " + strconv.FormatInt(e.Offset, 10) + ": " + e.Err.Error()
  45 }
  46
  47 // A WriteError reports an error encountered while writing output.
  48 type WriteError struct {
  49         Offset int64 // byte offset where error occurred
  50         Err    error // error returned by underlying Write
  51 }
  52
  53 func (e *WriteError) Error() string {
  54         return "flate: write error at offset " + strconv.FormatInt(e.Offset, 10) + ": " + e.Err.Error()
  55 }
  56
  57 // Huffman decoder is based on
  58 // J. Brian Connell, ``A Huffman-Shannon-Fano Code,''
  59 // Proceedings of the IEEE, 61(7) (July 1973), pp 1046-1047.
  60 type huffmanDecoder struct {
  61         // min, max code length
  62         min, max int
  63
  64         // limit[i] = largest code word of length i
  65         // Given code v of length n,
  66         // need more bits if v > limit[n].
  67         limit [maxCodeLen + 1]int
  68
  69         // base[i] = smallest code word of length i - seq number
  70         base [maxCodeLen + 1]int
  71
  72         // codes[seq number] = output code.
  73         // Given code v of length n, value is
  74         // codes[v - base[n]].
  75         codes []int
  76 }
  77
  78 // Initialize Huffman decoding tables from array of code lengths.
  79 func (h *huffmanDecoder) init(bits []int) bool {
  80         // Count number of codes of each length,
  81         // compute min and max length.
  82         var count [maxCodeLen + 1]int
  83         var min, max int
  84         for _, n := range bits {
  85                 if n == 0 {
  86                         continue
  87                 }
  88                 if min == 0 || n < min {
  89                         min = n
  90                 }
  91                 if n > max {
  92                         max = n
  93                 }
  94                 count[n]++
  95         }
  96         if max == 0 {
  97                 return false
  98         }
  99
 100         h.min = min
 101         h.max = max
 102
 103         // For each code range, compute
 104         // nextcode (first code of that length),
 105         // limit (last code of that length), and
 106         // base (offset from first code to sequence number).
 107         code := 0
 108         seq := 0
 109         var nextcode [maxCodeLen]int
 110         for i := min; i <= max; i++ {
 111                 n := count[i]
 112                 nextcode[i] = code
 113                 h.base[i] = code - seq
 114                 code += n
 115                 seq += n
 116                 h.limit[i] = code - 1
 117                 code <<= 1
 118         }
 119
 120         // Make array mapping sequence numbers to codes.
 121         if len(h.codes) < len(bits) {
 122                 h.codes = make([]int, len(bits))
 123         }
 124         for i, n := range bits {
 125                 if n == 0 {
 126                         continue
 127                 }
 128                 code := nextcode[n]
 129                 nextcode[n]++
 130                 seq := code - h.base[n]
 131                 h.codes[seq] = i
 132         }
 133         return true
 134 }
 135
 136 // Hard-coded Huffman tables for DEFLATE algorithm.
 137 // See RFC 1951, section 3.2.6.
 138 var fixedHuffmanDecoder = huffmanDecoder{
 139         7, 9,
 140         [maxCodeLen + 1]int{7: 23, 199, 511},
 141         [maxCodeLen + 1]int{7: 0, 24, 224},
 142         []int{
 143                 // length 7: 256-279
 144                 256, 257, 258, 259, 260, 261, 262,
 145                 263, 264, 265, 266, 267, 268, 269,
 146                 270, 271, 272, 273, 274, 275, 276,
 147                 277, 278, 279,
 148
 149                 // length 8: 0-143
 150                 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
 151                 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
 152                 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
 153                 32, 33, 34, 35, 36, 37, 38, 39, 40, 41,
 154                 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,
 155                 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
 156                 62, 63, 64, 65, 66, 67, 68, 69, 70, 71,
 157                 72, 73, 74, 75, 76, 77, 78, 79, 80, 81,
 158                 82, 83, 84, 85, 86, 87, 88, 89, 90, 91,
 159                 92, 93, 94, 95, 96, 97, 98, 99, 100,
 160                 101, 102, 103, 104, 105, 106, 107, 108,
 161                 109, 110, 111, 112, 113, 114, 115, 116,
 162                 117, 118, 119, 120, 121, 122, 123, 124,
 163                 125, 126, 127, 128, 129, 130, 131, 132,
 164                 133, 134, 135, 136, 137, 138, 139, 140,
 165                 141, 142, 143,
 166
 167                 // length 8: 280-287
 168                 280, 281, 282, 283, 284, 285, 286, 287,
 169
 170                 // length 9: 144-255
 171                 144, 145, 146, 147, 148, 149, 150, 151,
 172                 152, 153, 154, 155, 156, 157, 158, 159,
 173                 160, 161, 162, 163, 164, 165, 166, 167,
 174                 168, 169, 170, 171, 172, 173, 174, 175,
 175                 176, 177, 178, 179, 180, 181, 182, 183,
 176                 184, 185, 186, 187, 188, 189, 190, 191,
 177                 192, 193, 194, 195, 196, 197, 198, 199,
 178                 200, 201, 202, 203, 204, 205, 206, 207,
 179                 208, 209, 210, 211, 212, 213, 214, 215,
 180                 216, 217, 218, 219, 220, 221, 222, 223,
 181                 224, 225, 226, 227, 228, 229, 230, 231,
 182                 232, 233, 234, 235, 236, 237, 238, 239,
 183                 240, 241, 242, 243, 244, 245, 246, 247,
 184                 248, 249, 250, 251, 252, 253, 254, 255,
 185         },
 186 }
 187
 188 // The actual read interface needed by NewReader.
 189 // If the passed in io.Reader does not also have ReadByte,
 190 // the NewReader will introduce its own buffering.
 191 type Reader interface {
 192         io.Reader
 193         ReadByte() (c byte, err error)
 194 }
 195
 196 // Decompress state.
 197 type decompressor struct {
 198         // Input source.
 199         r       Reader
 200         roffset int64
 201         woffset int64
 202
 203         // Input bits, in top of b.
 204         b  uint32
 205         nb uint
 206
 207         // Huffman decoders for literal/length, distance.
 208         h1, h2 huffmanDecoder
 209
 210         // Length arrays used to define Huffman codes.
 211         bits     [maxLit + maxDist]int
 212         codebits [numCodes]int
 213
 214         // Output history, buffer.
 215         hist  [maxHist]byte
 216         hp    int  // current output position in buffer
 217         hw    int  // have written hist[0:hw] already
 218         hfull bool // buffer has filled at least once
 219
 220         // Temporary buffer (avoids repeated allocation).
 221         buf [4]byte
 222
 223         // Next step in the decompression,
 224         // and decompression state.
 225         step     func(*decompressor)
 226         final    bool
 227         err      error
 228         toRead   []byte
 229         hl, hd   *huffmanDecoder
 230         copyLen  int
 231         copyDist int
 232 }
 233
 234 func (f *decompressor) nextBlock() {
 235         if f.final {
 236                 if f.hw != f.hp {
 237                         f.flush((*decompressor).nextBlock)
 238                         return
 239                 }
 240                 f.err = io.EOF
 241                 return
 242         }
 243         for f.nb < 1+2 {
 244                 if f.err = f.moreBits(); f.err != nil {
 245                         return
 246                 }
 247         }
 248         f.final = f.b&1 == 1
 249         f.b >>= 1
 250         typ := f.b & 3
 251         f.b >>= 2
 252         f.nb -= 1 + 2
 253         switch typ {
 254         case 0:
 255                 f.dataBlock()
 256         case 1:
 257                 // compressed, fixed Huffman tables
 258                 f.hl = &fixedHuffmanDecoder
 259                 f.hd = nil
 260                 f.huffmanBlock()
 261         case 2:
 262                 // compressed, dynamic Huffman tables
 263                 if f.err = f.readHuffman(); f.err != nil {
 264                         break
 265                 }
 266                 f.hl = &f.h1
 267                 f.hd = &f.h2
 268                 f.huffmanBlock()
 269         default:
 270                 // 3 is reserved.
 271                 f.err = CorruptInputError(f.roffset)
 272         }
 273 }
 274
 275 func (f *decompressor) Read(b []byte) (int, error) {
 276         for {
 277                 if len(f.toRead) > 0 {
 278                         n := copy(b, f.toRead)
 279                         f.toRead = f.toRead[n:]
 280                         return n, nil
 281                 }
 282                 if f.err != nil {
 283                         return 0, f.err
 284                 }
 285                 f.step(f)
 286         }
 287         panic("unreachable")
 288 }
 289
 290 func (f *decompressor) Close() error {
 291         if f.err == io.EOF {
 292                 return nil
 293         }
 294         return f.err
 295 }
 296
 297 // RFC 1951 section 3.2.7.
 298 // Compression with dynamic Huffman codes
 299
 300 var codeOrder = [...]int{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}
 301
 302 func (f *decompressor) readHuffman() error {
 303         // HLIT[5], HDIST[5], HCLEN[4].
 304         for f.nb < 5+5+4 {
 305                 if err := f.moreBits(); err != nil {
 306                         return err
 307                 }
 308         }
 309         nlit := int(f.b&0x1F) + 257
 310         if nlit > maxLit {
 311                 return CorruptInputError(f.roffset)
 312         }
 313         f.b >>= 5
 314         ndist := int(f.b&0x1F) + 1
 315         // maxDist is 32, so ndist is always valid.
 316         f.b >>= 5
 317         nclen := int(f.b&0xF) + 4
 318         // numCodes is 19, so nclen is always valid.
 319         f.b >>= 4
 320         f.nb -= 5 + 5 + 4
 321
 322         // (HCLEN+4)*3 bits: code lengths in the magic codeOrder order.
 323         for i := 0; i < nclen; i++ {
 324                 for f.nb < 3 {
 325                         if err := f.moreBits(); err != nil {
 326                                 return err
 327                         }
 328                 }
 329                 f.codebits[codeOrder[i]] = int(f.b & 0x7)
 330                 f.b >>= 3
 331                 f.nb -= 3
 332         }
 333         for i := nclen; i < len(codeOrder); i++ {
 334                 f.codebits[codeOrder[i]] = 0
 335         }
 336         if !f.h1.init(f.codebits[0:]) {
 337                 return CorruptInputError(f.roffset)
 338         }
 339
 340         // HLIT + 257 code lengths, HDIST + 1 code lengths,
 341         // using the code length Huffman code.
 342         for i, n := 0, nlit+ndist; i < n; {
 343                 x, err := f.huffSym(&f.h1)
 344                 if err != nil {
 345                         return err
 346                 }
 347                 if x < 16 {
 348                         // Actual length.
 349                         f.bits[i] = x
 350                         i++
 351                         continue
 352                 }
 353                 // Repeat previous length or zero.
 354                 var rep int
 355                 var nb uint
 356                 var b int
 357                 switch x {
 358                 default:
 359                         return InternalError("unexpected length code")
 360                 case 16:
 361                         rep = 3
 362                         nb = 2
 363                         if i == 0 {
 364                                 return CorruptInputError(f.roffset)
 365                         }
 366                         b = f.bits[i-1]
 367                 case 17:
 368                         rep = 3
 369                         nb = 3
 370                         b = 0
 371                 case 18:
 372                         rep = 11
 373                         nb = 7
 374                         b = 0
 375                 }
 376                 for f.nb < nb {
 377                         if err := f.moreBits(); err != nil {
 378                                 return err
 379                         }
 380                 }
 381                 rep += int(f.b & uint32(1<<nb-1))
 382                 f.b >>= nb
 383                 f.nb -= nb
 384                 if i+rep > n {
 385                         return CorruptInputError(f.roffset)
 386                 }
 387                 for j := 0; j < rep; j++ {
 388                         f.bits[i] = b
 389                         i++
 390                 }
 391         }
 392
 393         if !f.h1.init(f.bits[0:nlit]) || !f.h2.init(f.bits[nlit:nlit+ndist]) {
 394                 return CorruptInputError(f.roffset)
 395         }
 396
 397         return nil
 398 }
 399
 400 // Decode a single Huffman block from f.
 401 // hl and hd are the Huffman states for the lit/length values
 402 // and the distance values, respectively.  If hd == nil, using the
 403 // fixed distance encoding associated with fixed Huffman blocks.
 404 func (f *decompressor) huffmanBlock() {
 405         for {
 406                 v, err := f.huffSym(f.hl)
 407                 if err != nil {
 408                         f.err = err
 409                         return
 410                 }
 411                 var n uint // number of bits extra
 412                 var length int
 413                 switch {
 414                 case v < 256:
 415                         f.hist[f.hp] = byte(v)
 416                         f.hp++
 417                         if f.hp == len(f.hist) {
 418                                 // After the flush, continue this loop.
 419                                 f.flush((*decompressor).huffmanBlock)
 420                                 return
 421                         }
 422                         continue
 423                 case v == 256:
 424                         // Done with huffman block; read next block.
 425                         f.step = (*decompressor).nextBlock
 426                         return
 427                 // otherwise, reference to older data
 428                 case v < 265:
 429                         length = v - (257 - 3)
 430                         n = 0
 431                 case v < 269:
 432                         length = v*2 - (265*2 - 11)
 433                         n = 1
 434                 case v < 273:
 435                         length = v*4 - (269*4 - 19)
 436                         n = 2
 437                 case v < 277:
 438                         length = v*8 - (273*8 - 35)
 439                         n = 3
 440                 case v < 281:
 441                         length = v*16 - (277*16 - 67)
 442                         n = 4
 443                 case v < 285:
 444                         length = v*32 - (281*32 - 131)
 445                         n = 5
 446                 default:
 447                         length = 258
 448                         n = 0
 449                 }
 450                 if n > 0 {
 451                         for f.nb < n {
 452                                 if err = f.moreBits(); err != nil {
 453                                         f.err = err
 454                                         return
 455                                 }
 456                         }
 457                         length += int(f.b & uint32(1<<n-1))
 458                         f.b >>= n
 459                         f.nb -= n
 460                 }
 461
 462                 var dist int
 463                 if f.hd == nil {
 464                         for f.nb < 5 {
 465                                 if err = f.moreBits(); err != nil {
 466                                         f.err = err
 467                                         return
 468                                 }
 469                         }
 470                         dist = int(reverseByte[(f.b&0x1F)<<3])
 471                         f.b >>= 5
 472                         f.nb -= 5
 473                 } else {
 474                         if dist, err = f.huffSym(f.hd); err != nil {
 475                                 f.err = err
 476                                 return
 477                         }
 478                 }
 479
 480                 switch {
 481                 case dist < 4:
 482                         dist++
 483                 case dist >= 30:
 484                         f.err = CorruptInputError(f.roffset)
 485                         return
 486                 default:
 487                         nb := uint(dist-2) >> 1
 488                         // have 1 bit in bottom of dist, need nb more.
 489                         extra := (dist & 1) << nb
 490                         for f.nb < nb {
 491                                 if err = f.moreBits(); err != nil {
 492                                         f.err = err
 493                                         return
 494                                 }
 495                         }
 496                         extra |= int(f.b & uint32(1<<nb-1))
 497                         f.b >>= nb
 498                         f.nb -= nb
 499                         dist = 1<<(nb+1) + 1 + extra
 500                 }
 501
 502                 // Copy history[-dist:-dist+length] into output.
 503                 if dist > len(f.hist) {
 504                         f.err = InternalError("bad history distance")
 505                         return
 506                 }
 507
 508                 // No check on length; encoding can be prescient.
 509                 if !f.hfull && dist > f.hp {
 510                         f.err = CorruptInputError(f.roffset)
 511                         return
 512                 }
 513
 514                 p := f.hp - dist
 515                 if p < 0 {
 516                         p += len(f.hist)
 517                 }
 518                 for i := 0; i < length; i++ {
 519                         f.hist[f.hp] = f.hist[p]
 520                         f.hp++
 521                         p++
 522                         if f.hp == len(f.hist) {
 523                                 // After flush continue copying out of history.
 524                                 f.copyLen = length - (i + 1)
 525                                 f.copyDist = dist
 526                                 f.flush((*decompressor).copyHuff)
 527                                 return
 528                         }
 529                         if p == len(f.hist) {
 530                                 p = 0
 531                         }
 532                 }
 533         }
 534         panic("unreached")
 535 }
 536
 537 func (f *decompressor) copyHuff() {
 538         length := f.copyLen
 539         dist := f.copyDist
 540         p := f.hp - dist
 541         if p < 0 {
 542                 p += len(f.hist)
 543         }
 544         for i := 0; i < length; i++ {
 545                 f.hist[f.hp] = f.hist[p]
 546                 f.hp++
 547                 p++
 548                 if f.hp == len(f.hist) {
 549                         f.copyLen = length - (i + 1)
 550                         f.flush((*decompressor).copyHuff)
 551                         return
 552                 }
 553                 if p == len(f.hist) {
 554                         p = 0
 555                 }
 556         }
 557
 558         // Continue processing Huffman block.
 559         f.huffmanBlock()
 560 }
 561
 562 // Copy a single uncompressed data block from input to output.
 563 func (f *decompressor) dataBlock() {
 564         // Uncompressed.
 565         // Discard current half-byte.
 566         f.nb = 0
 567         f.b = 0
 568
 569         // Length then ones-complement of length.
 570         nr, err := io.ReadFull(f.r, f.buf[0:4])
 571         f.roffset += int64(nr)
 572         if err != nil {
 573                 f.err = &ReadError{f.roffset, err}
 574                 return
 575         }
 576         n := int(f.buf[0]) | int(f.buf[1])<<8
 577         nn := int(f.buf[2]) | int(f.buf[3])<<8
 578         if uint16(nn) != uint16(^n) {
 579                 f.err = CorruptInputError(f.roffset)
 580                 return
 581         }
 582
 583         if n == 0 {
 584                 // 0-length block means sync
 585                 f.flush((*decompressor).nextBlock)
 586                 return
 587         }
 588
 589         f.copyLen = n
 590         f.copyData()
 591 }
 592
 593 func (f *decompressor) copyData() {
 594         // Read f.dataLen bytes into history,
 595         // pausing for reads as history fills.
 596         n := f.copyLen
 597         for n > 0 {
 598                 m := len(f.hist) - f.hp
 599                 if m > n {
 600                         m = n
 601                 }
 602                 m, err := io.ReadFull(f.r, f.hist[f.hp:f.hp+m])
 603                 f.roffset += int64(m)
 604                 if err != nil {
 605                         f.err = &ReadError{f.roffset, err}
 606                         return
 607                 }
 608                 n -= m
 609                 f.hp += m
 610                 if f.hp == len(f.hist) {
 611                         f.copyLen = n
 612                         f.flush((*decompressor).copyData)
 613                         return
 614                 }
 615         }
 616         f.step = (*decompressor).nextBlock
 617 }
 618
 619 func (f *decompressor) setDict(dict []byte) {
 620         if len(dict) > len(f.hist) {
 621                 // Will only remember the tail.
 622                 dict = dict[len(dict)-len(f.hist):]
 623         }
 624
 625         f.hp = copy(f.hist[:], dict)
 626         if f.hp == len(f.hist) {
 627                 f.hp = 0
 628                 f.hfull = true
 629         }
 630         f.hw = f.hp
 631 }
 632
 633 func (f *decompressor) moreBits() error {
 634         c, err := f.r.ReadByte()
 635         if err != nil {
 636                 if err == io.EOF {
 637                         err = io.ErrUnexpectedEOF
 638                 }
 639                 return err
 640         }
 641         f.roffset++
 642         f.b |= uint32(c) << f.nb
 643         f.nb += 8
 644         return nil
 645 }
 646
 647 // Read the next Huffman-encoded symbol from f according to h.
 648 func (f *decompressor) huffSym(h *huffmanDecoder) (int, error) {
 649         for n := uint(h.min); n <= uint(h.max); n++ {
 650                 lim := h.limit[n]
 651                 if lim == -1 {
 652                         continue
 653                 }
 654                 for f.nb < n {
 655                         if err := f.moreBits(); err != nil {
 656                                 return 0, err
 657                         }
 658                 }
 659                 v := int(f.b & uint32(1<<n-1))
 660                 v <<= 16 - n
 661                 v = int(reverseByte[v>>8]) | int(reverseByte[v&0xFF])<<8 // reverse bits
 662                 if v <= lim {
 663                         f.b >>= n
 664                         f.nb -= n
 665                         return h.codes[v-h.base[n]], nil
 666                 }
 667         }
 668         return 0, CorruptInputError(f.roffset)
 669 }
 670
 671 // Flush any buffered output to the underlying writer.
 672 func (f *decompressor) flush(step func(*decompressor)) {
 673         f.toRead = f.hist[f.hw:f.hp]
 674         f.woffset += int64(f.hp - f.hw)
 675         f.hw = f.hp
 676         if f.hp == len(f.hist) {
 677                 f.hp = 0
 678                 f.hw = 0
 679                 f.hfull = true
 680         }
 681         f.step = step
 682 }
 683
 684 func makeReader(r io.Reader) Reader {
 685         if rr, ok := r.(Reader); ok {
 686                 return rr
 687         }
 688         return bufio.NewReader(r)
 689 }
 690
 691 // NewReader returns a new ReadCloser that can be used
 692 // to read the uncompressed version of r.  It is the caller's
 693 // responsibility to call Close on the ReadCloser when
 694 // finished reading.
 695 func NewReader(r io.Reader) io.ReadCloser {
 696         var f decompressor
 697         f.r = makeReader(r)
 698         f.step = (*decompressor).nextBlock
 699         return &f
 700 }
 701
 702 // NewReaderDict is like NewReader but initializes the reader
 703 // with a preset dictionary.  The returned Reader behaves as if
 704 // the uncompressed data stream started with the given dictionary,
 705 // which has already been read.  NewReaderDict is typically used
 706 // to read data compressed by NewWriterDict.
 707 func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser {
 708         var f decompressor
 709         f.setDict(dict)
 710         f.r = makeReader(r)
 711         f.step = (*decompressor).nextBlock
 712         return &f
 713 }