Source file src/compress/flate/inflate.go

Documentation: compress/flate

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

View as plain text