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 "sync" 15 ) 16 17 const ( 18 maxCodeLen = 16 // max length of Huffman code 19 // The next three numbers come from the RFC section 3.2.7, with the 20 // additional proviso in section 3.2.5 which implies that distance codes 21 // 30 and 31 should never occur in compressed data. 22 maxNumLit = 286 23 maxNumDist = 30 24 numCodes = 19 // number of codes in Huffman meta-code 25 ) 26 27 // Initialize the fixedHuffmanDecoder only once upon first use. 28 var fixedOnce sync.Once 29 var fixedHuffmanDecoder huffmanDecoder 30 31 // A CorruptInputError reports the presence of corrupt input at a given offset. 32 type CorruptInputError int64 33 34 func (e CorruptInputError) Error() string { 35 return "flate: corrupt input before offset " + strconv.FormatInt(int64(e), 10) 36 } 37 38 // An InternalError reports an error in the flate code itself. 39 type InternalError string 40 41 func (e InternalError) Error() string { return "flate: internal error: " + string(e) } 42 43 // A ReadError reports an error encountered while reading input. 44 // 45 // Deprecated: No longer returned. 46 type ReadError struct { 47 Offset int64 // byte offset where error occurred 48 Err error // error returned by underlying Read 49 } 50 51 func (e *ReadError) Error() string { 52 return "flate: read error at offset " + strconv.FormatInt(e.Offset, 10) + ": " + e.Err.Error() 53 } 54 55 // A WriteError reports an error encountered while writing output. 56 // 57 // Deprecated: No longer returned. 58 type WriteError struct { 59 Offset int64 // byte offset where error occurred 60 Err error // error returned by underlying Write 61 } 62 63 func (e *WriteError) Error() string { 64 return "flate: write error at offset " + strconv.FormatInt(e.Offset, 10) + ": " + e.Err.Error() 65 } 66 67 // Resetter resets a ReadCloser returned by NewReader or NewReaderDict to 68 // to switch to a new underlying Reader. This permits reusing a ReadCloser 69 // instead of allocating a new one. 70 type Resetter interface { 71 // Reset discards any buffered data and resets the Resetter as if it was 72 // newly initialized with the given reader. 73 Reset(r io.Reader, dict []byte) error 74 } 75 76 // The data structure for decoding Huffman tables is based on that of 77 // zlib. There is a lookup table of a fixed bit width (huffmanChunkBits), 78 // For codes smaller than the table width, there are multiple entries 79 // (each combination of trailing bits has the same value). For codes 80 // larger than the table width, the table contains a link to an overflow 81 // table. The width of each entry in the link table is the maximum code 82 // size minus the chunk width. 83 // 84 // Note that you can do a lookup in the table even without all bits 85 // filled. Since the extra bits are zero, and the DEFLATE Huffman codes 86 // have the property that shorter codes come before longer ones, the 87 // bit length estimate in the result is a lower bound on the actual 88 // number of bits. 89 // 90 // See the following: 91 // http://www.gzip.org/algorithm.txt 92 93 // chunk & 15 is number of bits 94 // chunk >> 4 is value, including table link 95 96 const ( 97 huffmanChunkBits = 9 98 huffmanNumChunks = 1 << huffmanChunkBits 99 huffmanCountMask = 15 100 huffmanValueShift = 4 101 ) 102 103 type huffmanDecoder struct { 104 min int // the minimum code length 105 chunks [huffmanNumChunks]uint32 // chunks as described above 106 links [][]uint32 // overflow links 107 linkMask uint32 // mask the width of the link table 108 } 109 110 // Initialize Huffman decoding tables from array of code lengths. 111 // Following this function, h is guaranteed to be initialized into a complete 112 // tree (i.e., neither over-subscribed nor under-subscribed). The exception is a 113 // degenerate case where the tree has only a single symbol with length 1. Empty 114 // trees are permitted. 115 func (h *huffmanDecoder) init(bits []int) bool { 116 // Sanity enables additional runtime tests during Huffman 117 // table construction. It's intended to be used during 118 // development to supplement the currently ad-hoc unit tests. 119 const sanity = false 120 121 if h.min != 0 { 122 *h = huffmanDecoder{} 123 } 124 125 // Count number of codes of each length, 126 // compute min and max length. 127 var count [maxCodeLen]int 128 var min, max int 129 for _, n := range bits { 130 if n == 0 { 131 continue 132 } 133 if min == 0 || n < min { 134 min = n 135 } 136 if n > max { 137 max = n 138 } 139 count[n]++ 140 } 141 142 // Empty tree. The decompressor.huffSym function will fail later if the tree 143 // is used. Technically, an empty tree is only valid for the HDIST tree and 144 // not the HCLEN and HLIT tree. However, a stream with an empty HCLEN tree 145 // is guaranteed to fail since it will attempt to use the tree to decode the 146 // codes for the HLIT and HDIST trees. Similarly, an empty HLIT tree is 147 // guaranteed to fail later since the compressed data section must be 148 // composed of at least one symbol (the end-of-block marker). 149 if max == 0 { 150 return true 151 } 152 153 code := 0 154 var nextcode [maxCodeLen]int 155 for i := min; i <= max; i++ { 156 code <<= 1 157 nextcode[i] = code 158 code += count[i] 159 } 160 161 // Check that the coding is complete (i.e., that we've 162 // assigned all 2-to-the-max possible bit sequences). 163 // Exception: To be compatible with zlib, we also need to 164 // accept degenerate single-code codings. See also 165 // TestDegenerateHuffmanCoding. 166 if code != 1<<uint(max) && !(code == 1 && max == 1) { 167 return false 168 } 169 170 h.min = min 171 if max > huffmanChunkBits { 172 numLinks := 1 << (uint(max) - huffmanChunkBits) 173 h.linkMask = uint32(numLinks - 1) 174 175 // create link tables 176 link := nextcode[huffmanChunkBits+1] >> 1 177 h.links = make([][]uint32, huffmanNumChunks-link) 178 for j := uint(link); j < huffmanNumChunks; j++ { 179 reverse := int(reverseByte[j>>8]) | int(reverseByte[j&0xff])<<8 180 reverse >>= uint(16 - huffmanChunkBits) 181 off := j - uint(link) 182 if sanity && h.chunks[reverse] != 0 { 183 panic("impossible: overwriting existing chunk") 184 } 185 h.chunks[reverse] = uint32(off<<huffmanValueShift | (huffmanChunkBits + 1)) 186 h.links[off] = make([]uint32, numLinks) 187 } 188 } 189 190 for i, n := range bits { 191 if n == 0 { 192 continue 193 } 194 code := nextcode[n] 195 nextcode[n]++ 196 chunk := uint32(i<<huffmanValueShift | n) 197 reverse := int(reverseByte[code>>8]) | int(reverseByte[code&0xff])<<8 198 reverse >>= uint(16 - n) 199 if n <= huffmanChunkBits { 200 for off := reverse; off < len(h.chunks); off += 1 << uint(n) { 201 // We should never need to overwrite 202 // an existing chunk. Also, 0 is 203 // never a valid chunk, because the 204 // lower 4 "count" bits should be 205 // between 1 and 15. 206 if sanity && h.chunks[off] != 0 { 207 panic("impossible: overwriting existing chunk") 208 } 209 h.chunks[off] = chunk 210 } 211 } else { 212 j := reverse & (huffmanNumChunks - 1) 213 if sanity && h.chunks[j]&huffmanCountMask != huffmanChunkBits+1 { 214 // Longer codes should have been 215 // associated with a link table above. 216 panic("impossible: not an indirect chunk") 217 } 218 value := h.chunks[j] >> huffmanValueShift 219 linktab := h.links[value] 220 reverse >>= huffmanChunkBits 221 for off := reverse; off < len(linktab); off += 1 << uint(n-huffmanChunkBits) { 222 if sanity && linktab[off] != 0 { 223 panic("impossible: overwriting existing chunk") 224 } 225 linktab[off] = chunk 226 } 227 } 228 } 229 230 if sanity { 231 // Above we've sanity checked that we never overwrote 232 // an existing entry. Here we additionally check that 233 // we filled the tables completely. 234 for i, chunk := range h.chunks { 235 if chunk == 0 { 236 // As an exception, in the degenerate 237 // single-code case, we allow odd 238 // chunks to be missing. 239 if code == 1 && i%2 == 1 { 240 continue 241 } 242 panic("impossible: missing chunk") 243 } 244 } 245 for _, linktab := range h.links { 246 for _, chunk := range linktab { 247 if chunk == 0 { 248 panic("impossible: missing chunk") 249 } 250 } 251 } 252 } 253 254 return true 255 } 256 257 // The actual read interface needed by NewReader. 258 // If the passed in io.Reader does not also have ReadByte, 259 // the NewReader will introduce its own buffering. 260 type Reader interface { 261 io.Reader 262 io.ByteReader 263 } 264 265 // Decompress state. 266 type decompressor struct { 267 // Input source. 268 r Reader 269 roffset int64 270 271 // Input bits, in top of b. 272 b uint32 273 nb uint 274 275 // Huffman decoders for literal/length, distance. 276 h1, h2 huffmanDecoder 277 278 // Length arrays used to define Huffman codes. 279 bits *[maxNumLit + maxNumDist]int 280 codebits *[numCodes]int 281 282 // Output history, buffer. 283 dict dictDecoder 284 285 // Temporary buffer (avoids repeated allocation). 286 buf [4]byte 287 288 // Next step in the decompression, 289 // and decompression state. 290 step func(*decompressor) 291 stepState int 292 final bool 293 err error 294 toRead []byte 295 hl, hd *huffmanDecoder 296 copyLen int 297 copyDist int 298 } 299 300 func (f *decompressor) nextBlock() { 301 for f.nb < 1+2 { 302 if f.err = f.moreBits(); f.err != nil { 303 return 304 } 305 } 306 f.final = f.b&1 == 1 307 f.b >>= 1 308 typ := f.b & 3 309 f.b >>= 2 310 f.nb -= 1 + 2 311 switch typ { 312 case 0: 313 f.dataBlock() 314 case 1: 315 // compressed, fixed Huffman tables 316 f.hl = &fixedHuffmanDecoder 317 f.hd = nil 318 f.huffmanBlock() 319 case 2: 320 // compressed, dynamic Huffman tables 321 if f.err = f.readHuffman(); f.err != nil { 322 break 323 } 324 f.hl = &f.h1 325 f.hd = &f.h2 326 f.huffmanBlock() 327 default: 328 // 3 is reserved. 329 f.err = CorruptInputError(f.roffset) 330 } 331 } 332 333 func (f *decompressor) Read(b []byte) (int, error) { 334 for { 335 if len(f.toRead) > 0 { 336 n := copy(b, f.toRead) 337 f.toRead = f.toRead[n:] 338 if len(f.toRead) == 0 { 339 return n, f.err 340 } 341 return n, nil 342 } 343 if f.err != nil { 344 return 0, f.err 345 } 346 f.step(f) 347 if f.err != nil && len(f.toRead) == 0 { 348 f.toRead = f.dict.readFlush() // Flush what's left in case of error 349 } 350 } 351 } 352 353 func (f *decompressor) Close() error { 354 if f.err == io.EOF { 355 return nil 356 } 357 return f.err 358 } 359 360 // RFC 1951 section 3.2.7. 361 // Compression with dynamic Huffman codes 362 363 var codeOrder = [...]int{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15} 364 365 func (f *decompressor) readHuffman() error { 366 // HLIT[5], HDIST[5], HCLEN[4]. 367 for f.nb < 5+5+4 { 368 if err := f.moreBits(); err != nil { 369 return err 370 } 371 } 372 nlit := int(f.b&0x1F) + 257 373 if nlit > maxNumLit { 374 return CorruptInputError(f.roffset) 375 } 376 f.b >>= 5 377 ndist := int(f.b&0x1F) + 1 378 if ndist > maxNumDist { 379 return CorruptInputError(f.roffset) 380 } 381 f.b >>= 5 382 nclen := int(f.b&0xF) + 4 383 // numCodes is 19, so nclen is always valid. 384 f.b >>= 4 385 f.nb -= 5 + 5 + 4 386 387 // (HCLEN+4)*3 bits: code lengths in the magic codeOrder order. 388 for i := 0; i < nclen; i++ { 389 for f.nb < 3 { 390 if err := f.moreBits(); err != nil { 391 return err 392 } 393 } 394 f.codebits[codeOrder[i]] = int(f.b & 0x7) 395 f.b >>= 3 396 f.nb -= 3 397 } 398 for i := nclen; i < len(codeOrder); i++ { 399 f.codebits[codeOrder[i]] = 0 400 } 401 if !f.h1.init(f.codebits[0:]) { 402 return CorruptInputError(f.roffset) 403 } 404 405 // HLIT + 257 code lengths, HDIST + 1 code lengths, 406 // using the code length Huffman code. 407 for i, n := 0, nlit+ndist; i < n; { 408 x, err := f.huffSym(&f.h1) 409 if err != nil { 410 return err 411 } 412 if x < 16 { 413 // Actual length. 414 f.bits[i] = x 415 i++ 416 continue 417 } 418 // Repeat previous length or zero. 419 var rep int 420 var nb uint 421 var b int 422 switch x { 423 default: 424 return InternalError("unexpected length code") 425 case 16: 426 rep = 3 427 nb = 2 428 if i == 0 { 429 return CorruptInputError(f.roffset) 430 } 431 b = f.bits[i-1] 432 case 17: 433 rep = 3 434 nb = 3 435 b = 0 436 case 18: 437 rep = 11 438 nb = 7 439 b = 0 440 } 441 for f.nb < nb { 442 if err := f.moreBits(); err != nil { 443 return err 444 } 445 } 446 rep += int(f.b & uint32(1<<nb-1)) 447 f.b >>= nb 448 f.nb -= nb 449 if i+rep > n { 450 return CorruptInputError(f.roffset) 451 } 452 for j := 0; j < rep; j++ { 453 f.bits[i] = b 454 i++ 455 } 456 } 457 458 if !f.h1.init(f.bits[0:nlit]) || !f.h2.init(f.bits[nlit:nlit+ndist]) { 459 return CorruptInputError(f.roffset) 460 } 461 462 // As an optimization, we can initialize the min bits to read at a time 463 // for the HLIT tree to the length of the EOB marker since we know that 464 // every block must terminate with one. This preserves the property that 465 // we never read any extra bytes after the end of the DEFLATE stream. 466 if f.h1.min < f.bits[endBlockMarker] { 467 f.h1.min = f.bits[endBlockMarker] 468 } 469 470 return nil 471 } 472 473 // Decode a single Huffman block from f. 474 // hl and hd are the Huffman states for the lit/length values 475 // and the distance values, respectively. If hd == nil, using the 476 // fixed distance encoding associated with fixed Huffman blocks. 477 func (f *decompressor) huffmanBlock() { 478 const ( 479 stateInit = iota // Zero value must be stateInit 480 stateDict 481 ) 482 483 switch f.stepState { 484 case stateInit: 485 goto readLiteral 486 case stateDict: 487 goto copyHistory 488 } 489 490 readLiteral: 491 // Read literal and/or (length, distance) according to RFC section 3.2.3. 492 { 493 v, err := f.huffSym(f.hl) 494 if err != nil { 495 f.err = err 496 return 497 } 498 var n uint // number of bits extra 499 var length int 500 switch { 501 case v < 256: 502 f.dict.writeByte(byte(v)) 503 if f.dict.availWrite() == 0 { 504 f.toRead = f.dict.readFlush() 505 f.step = (*decompressor).huffmanBlock 506 f.stepState = stateInit 507 return 508 } 509 goto readLiteral 510 case v == 256: 511 f.finishBlock() 512 return 513 // otherwise, reference to older data 514 case v < 265: 515 length = v - (257 - 3) 516 n = 0 517 case v < 269: 518 length = v*2 - (265*2 - 11) 519 n = 1 520 case v < 273: 521 length = v*4 - (269*4 - 19) 522 n = 2 523 case v < 277: 524 length = v*8 - (273*8 - 35) 525 n = 3 526 case v < 281: 527 length = v*16 - (277*16 - 67) 528 n = 4 529 case v < 285: 530 length = v*32 - (281*32 - 131) 531 n = 5 532 case v < maxNumLit: 533 length = 258 534 n = 0 535 default: 536 f.err = CorruptInputError(f.roffset) 537 return 538 } 539 if n > 0 { 540 for f.nb < n { 541 if err = f.moreBits(); err != nil { 542 f.err = err 543 return 544 } 545 } 546 length += int(f.b & uint32(1<<n-1)) 547 f.b >>= n 548 f.nb -= n 549 } 550 551 var dist int 552 if f.hd == nil { 553 for f.nb < 5 { 554 if err = f.moreBits(); err != nil { 555 f.err = err 556 return 557 } 558 } 559 dist = int(reverseByte[(f.b&0x1F)<<3]) 560 f.b >>= 5 561 f.nb -= 5 562 } else { 563 if dist, err = f.huffSym(f.hd); err != nil { 564 f.err = err 565 return 566 } 567 } 568 569 switch { 570 case dist < 4: 571 dist++ 572 case dist < maxNumDist: 573 nb := uint(dist-2) >> 1 574 // have 1 bit in bottom of dist, need nb more. 575 extra := (dist & 1) << nb 576 for f.nb < nb { 577 if err = f.moreBits(); err != nil { 578 f.err = err 579 return 580 } 581 } 582 extra |= int(f.b & uint32(1<<nb-1)) 583 f.b >>= nb 584 f.nb -= nb 585 dist = 1<<(nb+1) + 1 + extra 586 default: 587 f.err = CorruptInputError(f.roffset) 588 return 589 } 590 591 // No check on length; encoding can be prescient. 592 if dist > f.dict.histSize() { 593 f.err = CorruptInputError(f.roffset) 594 return 595 } 596 597 f.copyLen, f.copyDist = length, dist 598 goto copyHistory 599 } 600 601 copyHistory: 602 // Perform a backwards copy according to RFC section 3.2.3. 603 { 604 cnt := f.dict.tryWriteCopy(f.copyDist, f.copyLen) 605 if cnt == 0 { 606 cnt = f.dict.writeCopy(f.copyDist, f.copyLen) 607 } 608 f.copyLen -= cnt 609 610 if f.dict.availWrite() == 0 || f.copyLen > 0 { 611 f.toRead = f.dict.readFlush() 612 f.step = (*decompressor).huffmanBlock // We need to continue this work 613 f.stepState = stateDict 614 return 615 } 616 goto readLiteral 617 } 618 } 619 620 // Copy a single uncompressed data block from input to output. 621 func (f *decompressor) dataBlock() { 622 // Uncompressed. 623 // Discard current half-byte. 624 f.nb = 0 625 f.b = 0 626 627 // Length then ones-complement of length. 628 nr, err := io.ReadFull(f.r, f.buf[0:4]) 629 f.roffset += int64(nr) 630 if err != nil { 631 if err == io.EOF { 632 err = io.ErrUnexpectedEOF 633 } 634 f.err = err 635 return 636 } 637 n := int(f.buf[0]) | int(f.buf[1])<<8 638 nn := int(f.buf[2]) | int(f.buf[3])<<8 639 if uint16(nn) != uint16(^n) { 640 f.err = CorruptInputError(f.roffset) 641 return 642 } 643 644 if n == 0 { 645 f.toRead = f.dict.readFlush() 646 f.finishBlock() 647 return 648 } 649 650 f.copyLen = n 651 f.copyData() 652 } 653 654 // copyData copies f.copyLen bytes from the underlying reader into f.hist. 655 // It pauses for reads when f.hist is full. 656 func (f *decompressor) copyData() { 657 buf := f.dict.writeSlice() 658 if len(buf) > f.copyLen { 659 buf = buf[:f.copyLen] 660 } 661 662 cnt, err := io.ReadFull(f.r, buf) 663 f.roffset += int64(cnt) 664 f.copyLen -= cnt 665 f.dict.writeMark(cnt) 666 if err != nil { 667 if err == io.EOF { 668 err = io.ErrUnexpectedEOF 669 } 670 f.err = err 671 return 672 } 673 674 if f.dict.availWrite() == 0 || f.copyLen > 0 { 675 f.toRead = f.dict.readFlush() 676 f.step = (*decompressor).copyData 677 return 678 } 679 f.finishBlock() 680 } 681 682 func (f *decompressor) finishBlock() { 683 if f.final { 684 if f.dict.availRead() > 0 { 685 f.toRead = f.dict.readFlush() 686 } 687 f.err = io.EOF 688 } 689 f.step = (*decompressor).nextBlock 690 } 691 692 func (f *decompressor) moreBits() error { 693 c, err := f.r.ReadByte() 694 if err != nil { 695 if err == io.EOF { 696 err = io.ErrUnexpectedEOF 697 } 698 return err 699 } 700 f.roffset++ 701 f.b |= uint32(c) << f.nb 702 f.nb += 8 703 return nil 704 } 705 706 // Read the next Huffman-encoded symbol from f according to h. 707 func (f *decompressor) huffSym(h *huffmanDecoder) (int, error) { 708 // Since a huffmanDecoder can be empty or be composed of a degenerate tree 709 // with single element, huffSym must error on these two edge cases. In both 710 // cases, the chunks slice will be 0 for the invalid sequence, leading it 711 // satisfy the n == 0 check below. 712 n := uint(h.min) 713 for { 714 for f.nb < n { 715 if err := f.moreBits(); err != nil { 716 return 0, err 717 } 718 } 719 chunk := h.chunks[f.b&(huffmanNumChunks-1)] 720 n = uint(chunk & huffmanCountMask) 721 if n > huffmanChunkBits { 722 chunk = h.links[chunk>>huffmanValueShift][(f.b>>huffmanChunkBits)&h.linkMask] 723 n = uint(chunk & huffmanCountMask) 724 } 725 if n <= f.nb { 726 if n == 0 { 727 f.err = CorruptInputError(f.roffset) 728 return 0, f.err 729 } 730 f.b >>= n 731 f.nb -= n 732 return int(chunk >> huffmanValueShift), nil 733 } 734 } 735 } 736 737 func makeReader(r io.Reader) Reader { 738 if rr, ok := r.(Reader); ok { 739 return rr 740 } 741 return bufio.NewReader(r) 742 } 743 744 func fixedHuffmanDecoderInit() { 745 fixedOnce.Do(func() { 746 // These come from the RFC section 3.2.6. 747 var bits [288]int 748 for i := 0; i < 144; i++ { 749 bits[i] = 8 750 } 751 for i := 144; i < 256; i++ { 752 bits[i] = 9 753 } 754 for i := 256; i < 280; i++ { 755 bits[i] = 7 756 } 757 for i := 280; i < 288; i++ { 758 bits[i] = 8 759 } 760 fixedHuffmanDecoder.init(bits[:]) 761 }) 762 } 763 764 func (f *decompressor) Reset(r io.Reader, dict []byte) error { 765 *f = decompressor{ 766 r: makeReader(r), 767 bits: f.bits, 768 codebits: f.codebits, 769 dict: f.dict, 770 step: (*decompressor).nextBlock, 771 } 772 f.dict.init(maxMatchOffset, dict) 773 return nil 774 } 775 776 // NewReader returns a new ReadCloser that can be used 777 // to read the uncompressed version of r. 778 // If r does not also implement io.ByteReader, 779 // the decompressor may read more data than necessary from r. 780 // It is the caller's responsibility to call Close on the ReadCloser 781 // when finished reading. 782 // 783 // The ReadCloser returned by NewReader also implements Resetter. 784 func NewReader(r io.Reader) io.ReadCloser { 785 fixedHuffmanDecoderInit() 786 787 var f decompressor 788 f.r = makeReader(r) 789 f.bits = new([maxNumLit + maxNumDist]int) 790 f.codebits = new([numCodes]int) 791 f.step = (*decompressor).nextBlock 792 f.dict.init(maxMatchOffset, nil) 793 return &f 794 } 795 796 // NewReaderDict is like NewReader but initializes the reader 797 // with a preset dictionary. The returned Reader behaves as if 798 // the uncompressed data stream started with the given dictionary, 799 // which has already been read. NewReaderDict is typically used 800 // to read data compressed by NewWriterDict. 801 // 802 // The ReadCloser returned by NewReader also implements Resetter. 803 func NewReaderDict(r io.Reader, dict []byte) io.ReadCloser { 804 fixedHuffmanDecoderInit() 805 806 var f decompressor 807 f.r = makeReader(r) 808 f.bits = new([maxNumLit + maxNumDist]int) 809 f.codebits = new([numCodes]int) 810 f.step = (*decompressor).nextBlock 811 f.dict.init(maxMatchOffset, dict) 812 return &f 813 } 814