Source file src/compress/flate/deflate.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
		 6  
		 7  import (
		 8  	"fmt"
		 9  	"io"
		10  	"math"
		11  )
		12  
		13  const (
		14  	NoCompression			= 0
		15  	BestSpeed					= 1
		16  	BestCompression		= 9
		17  	DefaultCompression = -1
		18  
		19  	// HuffmanOnly disables Lempel-Ziv match searching and only performs Huffman
		20  	// entropy encoding. This mode is useful in compressing data that has
		21  	// already been compressed with an LZ style algorithm (e.g. Snappy or LZ4)
		22  	// that lacks an entropy encoder. Compression gains are achieved when
		23  	// certain bytes in the input stream occur more frequently than others.
		24  	//
		25  	// Note that HuffmanOnly produces a compressed output that is
		26  	// RFC 1951 compliant. That is, any valid DEFLATE decompressor will
		27  	// continue to be able to decompress this output.
		28  	HuffmanOnly = -2
		29  )
		30  
		31  const (
		32  	logWindowSize = 15
		33  	windowSize		= 1 << logWindowSize
		34  	windowMask		= windowSize - 1
		35  
		36  	// The LZ77 step produces a sequence of literal tokens and <length, offset>
		37  	// pair tokens. The offset is also known as distance. The underlying wire
		38  	// format limits the range of lengths and offsets. For example, there are
		39  	// 256 legitimate lengths: those in the range [3, 258]. This package's
		40  	// compressor uses a higher minimum match length, enabling optimizations
		41  	// such as finding matches via 32-bit loads and compares.
		42  	baseMatchLength = 3			 // The smallest match length per the RFC section 3.2.5
		43  	minMatchLength	= 4			 // The smallest match length that the compressor actually emits
		44  	maxMatchLength	= 258		 // The largest match length
		45  	baseMatchOffset = 1			 // The smallest match offset
		46  	maxMatchOffset	= 1 << 15 // The largest match offset
		47  
		48  	// The maximum number of tokens we put into a single flate block, just to
		49  	// stop things from getting too large.
		50  	maxFlateBlockTokens = 1 << 14
		51  	maxStoreBlockSize	 = 65535
		52  	hashBits						= 17 // After 17 performance degrades
		53  	hashSize						= 1 << hashBits
		54  	hashMask						= (1 << hashBits) - 1
		55  	maxHashOffset			 = 1 << 24
		56  
		57  	skipNever = math.MaxInt32
		58  )
		59  
		60  type compressionLevel struct {
		61  	level, good, lazy, nice, chain, fastSkipHashing int
		62  }
		63  
		64  var levels = []compressionLevel{
		65  	{0, 0, 0, 0, 0, 0}, // NoCompression.
		66  	{1, 0, 0, 0, 0, 0}, // BestSpeed uses a custom algorithm; see deflatefast.go.
		67  	// For levels 2-3 we don't bother trying with lazy matches.
		68  	{2, 4, 0, 16, 8, 5},
		69  	{3, 4, 0, 32, 32, 6},
		70  	// Levels 4-9 use increasingly more lazy matching
		71  	// and increasingly stringent conditions for "good enough".
		72  	{4, 4, 4, 16, 16, skipNever},
		73  	{5, 8, 16, 32, 32, skipNever},
		74  	{6, 8, 16, 128, 128, skipNever},
		75  	{7, 8, 32, 128, 256, skipNever},
		76  	{8, 32, 128, 258, 1024, skipNever},
		77  	{9, 32, 258, 258, 4096, skipNever},
		78  }
		79  
		80  type compressor struct {
		81  	compressionLevel
		82  
		83  	w					*huffmanBitWriter
		84  	bulkHasher func([]byte, []uint32)
		85  
		86  	// compression algorithm
		87  	fill			func(*compressor, []byte) int // copy data to window
		88  	step			func(*compressor)						 // process window
		89  	sync			bool													// requesting flush
		90  	bestSpeed *deflateFast									// Encoder for BestSpeed
		91  
		92  	// Input hash chains
		93  	// hashHead[hashValue] contains the largest inputIndex with the specified hash value
		94  	// If hashHead[hashValue] is within the current window, then
		95  	// hashPrev[hashHead[hashValue] & windowMask] contains the previous index
		96  	// with the same hash value.
		97  	chainHead	int
		98  	hashHead	 [hashSize]uint32
		99  	hashPrev	 [windowSize]uint32
	 100  	hashOffset int
	 101  
	 102  	// input window: unprocessed data is window[index:windowEnd]
	 103  	index				 int
	 104  	window				[]byte
	 105  	windowEnd		 int
	 106  	blockStart		int	// window index where current tokens start
	 107  	byteAvailable bool // if true, still need to process window[index-1].
	 108  
	 109  	// queued output tokens
	 110  	tokens []token
	 111  
	 112  	// deflate state
	 113  	length				 int
	 114  	offset				 int
	 115  	hash					 uint32
	 116  	maxInsertIndex int
	 117  	err						error
	 118  
	 119  	// hashMatch must be able to contain hashes for the maximum match length.
	 120  	hashMatch [maxMatchLength - 1]uint32
	 121  }
	 122  
	 123  func (d *compressor) fillDeflate(b []byte) int {
	 124  	if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
	 125  		// shift the window by windowSize
	 126  		copy(d.window, d.window[windowSize:2*windowSize])
	 127  		d.index -= windowSize
	 128  		d.windowEnd -= windowSize
	 129  		if d.blockStart >= windowSize {
	 130  			d.blockStart -= windowSize
	 131  		} else {
	 132  			d.blockStart = math.MaxInt32
	 133  		}
	 134  		d.hashOffset += windowSize
	 135  		if d.hashOffset > maxHashOffset {
	 136  			delta := d.hashOffset - 1
	 137  			d.hashOffset -= delta
	 138  			d.chainHead -= delta
	 139  
	 140  			// Iterate over slices instead of arrays to avoid copying
	 141  			// the entire table onto the stack (Issue #18625).
	 142  			for i, v := range d.hashPrev[:] {
	 143  				if int(v) > delta {
	 144  					d.hashPrev[i] = uint32(int(v) - delta)
	 145  				} else {
	 146  					d.hashPrev[i] = 0
	 147  				}
	 148  			}
	 149  			for i, v := range d.hashHead[:] {
	 150  				if int(v) > delta {
	 151  					d.hashHead[i] = uint32(int(v) - delta)
	 152  				} else {
	 153  					d.hashHead[i] = 0
	 154  				}
	 155  			}
	 156  		}
	 157  	}
	 158  	n := copy(d.window[d.windowEnd:], b)
	 159  	d.windowEnd += n
	 160  	return n
	 161  }
	 162  
	 163  func (d *compressor) writeBlock(tokens []token, index int) error {
	 164  	if index > 0 {
	 165  		var window []byte
	 166  		if d.blockStart <= index {
	 167  			window = d.window[d.blockStart:index]
	 168  		}
	 169  		d.blockStart = index
	 170  		d.w.writeBlock(tokens, false, window)
	 171  		return d.w.err
	 172  	}
	 173  	return nil
	 174  }
	 175  
	 176  // fillWindow will fill the current window with the supplied
	 177  // dictionary and calculate all hashes.
	 178  // This is much faster than doing a full encode.
	 179  // Should only be used after a reset.
	 180  func (d *compressor) fillWindow(b []byte) {
	 181  	// Do not fill window if we are in store-only mode.
	 182  	if d.compressionLevel.level < 2 {
	 183  		return
	 184  	}
	 185  	if d.index != 0 || d.windowEnd != 0 {
	 186  		panic("internal error: fillWindow called with stale data")
	 187  	}
	 188  
	 189  	// If we are given too much, cut it.
	 190  	if len(b) > windowSize {
	 191  		b = b[len(b)-windowSize:]
	 192  	}
	 193  	// Add all to window.
	 194  	n := copy(d.window, b)
	 195  
	 196  	// Calculate 256 hashes at the time (more L1 cache hits)
	 197  	loops := (n + 256 - minMatchLength) / 256
	 198  	for j := 0; j < loops; j++ {
	 199  		index := j * 256
	 200  		end := index + 256 + minMatchLength - 1
	 201  		if end > n {
	 202  			end = n
	 203  		}
	 204  		toCheck := d.window[index:end]
	 205  		dstSize := len(toCheck) - minMatchLength + 1
	 206  
	 207  		if dstSize <= 0 {
	 208  			continue
	 209  		}
	 210  
	 211  		dst := d.hashMatch[:dstSize]
	 212  		d.bulkHasher(toCheck, dst)
	 213  		var newH uint32
	 214  		for i, val := range dst {
	 215  			di := i + index
	 216  			newH = val
	 217  			hh := &d.hashHead[newH&hashMask]
	 218  			// Get previous value with the same hash.
	 219  			// Our chain should point to the previous value.
	 220  			d.hashPrev[di&windowMask] = *hh
	 221  			// Set the head of the hash chain to us.
	 222  			*hh = uint32(di + d.hashOffset)
	 223  		}
	 224  		d.hash = newH
	 225  	}
	 226  	// Update window information.
	 227  	d.windowEnd = n
	 228  	d.index = n
	 229  }
	 230  
	 231  // Try to find a match starting at index whose length is greater than prevSize.
	 232  // We only look at chainCount possibilities before giving up.
	 233  func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
	 234  	minMatchLook := maxMatchLength
	 235  	if lookahead < minMatchLook {
	 236  		minMatchLook = lookahead
	 237  	}
	 238  
	 239  	win := d.window[0 : pos+minMatchLook]
	 240  
	 241  	// We quit when we get a match that's at least nice long
	 242  	nice := len(win) - pos
	 243  	if d.nice < nice {
	 244  		nice = d.nice
	 245  	}
	 246  
	 247  	// If we've got a match that's good enough, only look in 1/4 the chain.
	 248  	tries := d.chain
	 249  	length = prevLength
	 250  	if length >= d.good {
	 251  		tries >>= 2
	 252  	}
	 253  
	 254  	wEnd := win[pos+length]
	 255  	wPos := win[pos:]
	 256  	minIndex := pos - windowSize
	 257  
	 258  	for i := prevHead; tries > 0; tries-- {
	 259  		if wEnd == win[i+length] {
	 260  			n := matchLen(win[i:], wPos, minMatchLook)
	 261  
	 262  			if n > length && (n > minMatchLength || pos-i <= 4096) {
	 263  				length = n
	 264  				offset = pos - i
	 265  				ok = true
	 266  				if n >= nice {
	 267  					// The match is good enough that we don't try to find a better one.
	 268  					break
	 269  				}
	 270  				wEnd = win[pos+n]
	 271  			}
	 272  		}
	 273  		if i == minIndex {
	 274  			// hashPrev[i & windowMask] has already been overwritten, so stop now.
	 275  			break
	 276  		}
	 277  		i = int(d.hashPrev[i&windowMask]) - d.hashOffset
	 278  		if i < minIndex || i < 0 {
	 279  			break
	 280  		}
	 281  	}
	 282  	return
	 283  }
	 284  
	 285  func (d *compressor) writeStoredBlock(buf []byte) error {
	 286  	if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
	 287  		return d.w.err
	 288  	}
	 289  	d.w.writeBytes(buf)
	 290  	return d.w.err
	 291  }
	 292  
	 293  const hashmul = 0x1e35a7bd
	 294  
	 295  // hash4 returns a hash representation of the first 4 bytes
	 296  // of the supplied slice.
	 297  // The caller must ensure that len(b) >= 4.
	 298  func hash4(b []byte) uint32 {
	 299  	return ((uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24) * hashmul) >> (32 - hashBits)
	 300  }
	 301  
	 302  // bulkHash4 will compute hashes using the same
	 303  // algorithm as hash4
	 304  func bulkHash4(b []byte, dst []uint32) {
	 305  	if len(b) < minMatchLength {
	 306  		return
	 307  	}
	 308  	hb := uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24
	 309  	dst[0] = (hb * hashmul) >> (32 - hashBits)
	 310  	end := len(b) - minMatchLength + 1
	 311  	for i := 1; i < end; i++ {
	 312  		hb = (hb << 8) | uint32(b[i+3])
	 313  		dst[i] = (hb * hashmul) >> (32 - hashBits)
	 314  	}
	 315  }
	 316  
	 317  // matchLen returns the number of matching bytes in a and b
	 318  // up to length 'max'. Both slices must be at least 'max'
	 319  // bytes in size.
	 320  func matchLen(a, b []byte, max int) int {
	 321  	a = a[:max]
	 322  	b = b[:len(a)]
	 323  	for i, av := range a {
	 324  		if b[i] != av {
	 325  			return i
	 326  		}
	 327  	}
	 328  	return max
	 329  }
	 330  
	 331  // encSpeed will compress and store the currently added data,
	 332  // if enough has been accumulated or we at the end of the stream.
	 333  // Any error that occurred will be in d.err
	 334  func (d *compressor) encSpeed() {
	 335  	// We only compress if we have maxStoreBlockSize.
	 336  	if d.windowEnd < maxStoreBlockSize {
	 337  		if !d.sync {
	 338  			return
	 339  		}
	 340  
	 341  		// Handle small sizes.
	 342  		if d.windowEnd < 128 {
	 343  			switch {
	 344  			case d.windowEnd == 0:
	 345  				return
	 346  			case d.windowEnd <= 16:
	 347  				d.err = d.writeStoredBlock(d.window[:d.windowEnd])
	 348  			default:
	 349  				d.w.writeBlockHuff(false, d.window[:d.windowEnd])
	 350  				d.err = d.w.err
	 351  			}
	 352  			d.windowEnd = 0
	 353  			d.bestSpeed.reset()
	 354  			return
	 355  		}
	 356  
	 357  	}
	 358  	// Encode the block.
	 359  	d.tokens = d.bestSpeed.encode(d.tokens[:0], d.window[:d.windowEnd])
	 360  
	 361  	// If we removed less than 1/16th, Huffman compress the block.
	 362  	if len(d.tokens) > d.windowEnd-(d.windowEnd>>4) {
	 363  		d.w.writeBlockHuff(false, d.window[:d.windowEnd])
	 364  	} else {
	 365  		d.w.writeBlockDynamic(d.tokens, false, d.window[:d.windowEnd])
	 366  	}
	 367  	d.err = d.w.err
	 368  	d.windowEnd = 0
	 369  }
	 370  
	 371  func (d *compressor) initDeflate() {
	 372  	d.window = make([]byte, 2*windowSize)
	 373  	d.hashOffset = 1
	 374  	d.tokens = make([]token, 0, maxFlateBlockTokens+1)
	 375  	d.length = minMatchLength - 1
	 376  	d.offset = 0
	 377  	d.byteAvailable = false
	 378  	d.index = 0
	 379  	d.hash = 0
	 380  	d.chainHead = -1
	 381  	d.bulkHasher = bulkHash4
	 382  }
	 383  
	 384  func (d *compressor) deflate() {
	 385  	if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
	 386  		return
	 387  	}
	 388  
	 389  	d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
	 390  	if d.index < d.maxInsertIndex {
	 391  		d.hash = hash4(d.window[d.index : d.index+minMatchLength])
	 392  	}
	 393  
	 394  Loop:
	 395  	for {
	 396  		if d.index > d.windowEnd {
	 397  			panic("index > windowEnd")
	 398  		}
	 399  		lookahead := d.windowEnd - d.index
	 400  		if lookahead < minMatchLength+maxMatchLength {
	 401  			if !d.sync {
	 402  				break Loop
	 403  			}
	 404  			if d.index > d.windowEnd {
	 405  				panic("index > windowEnd")
	 406  			}
	 407  			if lookahead == 0 {
	 408  				// Flush current output block if any.
	 409  				if d.byteAvailable {
	 410  					// There is still one pending token that needs to be flushed
	 411  					d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1])))
	 412  					d.byteAvailable = false
	 413  				}
	 414  				if len(d.tokens) > 0 {
	 415  					if d.err = d.writeBlock(d.tokens, d.index); d.err != nil {
	 416  						return
	 417  					}
	 418  					d.tokens = d.tokens[:0]
	 419  				}
	 420  				break Loop
	 421  			}
	 422  		}
	 423  		if d.index < d.maxInsertIndex {
	 424  			// Update the hash
	 425  			d.hash = hash4(d.window[d.index : d.index+minMatchLength])
	 426  			hh := &d.hashHead[d.hash&hashMask]
	 427  			d.chainHead = int(*hh)
	 428  			d.hashPrev[d.index&windowMask] = uint32(d.chainHead)
	 429  			*hh = uint32(d.index + d.hashOffset)
	 430  		}
	 431  		prevLength := d.length
	 432  		prevOffset := d.offset
	 433  		d.length = minMatchLength - 1
	 434  		d.offset = 0
	 435  		minIndex := d.index - windowSize
	 436  		if minIndex < 0 {
	 437  			minIndex = 0
	 438  		}
	 439  
	 440  		if d.chainHead-d.hashOffset >= minIndex &&
	 441  			(d.fastSkipHashing != skipNever && lookahead > minMatchLength-1 ||
	 442  				d.fastSkipHashing == skipNever && lookahead > prevLength && prevLength < d.lazy) {
	 443  			if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
	 444  				d.length = newLength
	 445  				d.offset = newOffset
	 446  			}
	 447  		}
	 448  		if d.fastSkipHashing != skipNever && d.length >= minMatchLength ||
	 449  			d.fastSkipHashing == skipNever && prevLength >= minMatchLength && d.length <= prevLength {
	 450  			// There was a match at the previous step, and the current match is
	 451  			// not better. Output the previous match.
	 452  			if d.fastSkipHashing != skipNever {
	 453  				d.tokens = append(d.tokens, matchToken(uint32(d.length-baseMatchLength), uint32(d.offset-baseMatchOffset)))
	 454  			} else {
	 455  				d.tokens = append(d.tokens, matchToken(uint32(prevLength-baseMatchLength), uint32(prevOffset-baseMatchOffset)))
	 456  			}
	 457  			// Insert in the hash table all strings up to the end of the match.
	 458  			// index and index-1 are already inserted. If there is not enough
	 459  			// lookahead, the last two strings are not inserted into the hash
	 460  			// table.
	 461  			if d.length <= d.fastSkipHashing {
	 462  				var newIndex int
	 463  				if d.fastSkipHashing != skipNever {
	 464  					newIndex = d.index + d.length
	 465  				} else {
	 466  					newIndex = d.index + prevLength - 1
	 467  				}
	 468  				index := d.index
	 469  				for index++; index < newIndex; index++ {
	 470  					if index < d.maxInsertIndex {
	 471  						d.hash = hash4(d.window[index : index+minMatchLength])
	 472  						// Get previous value with the same hash.
	 473  						// Our chain should point to the previous value.
	 474  						hh := &d.hashHead[d.hash&hashMask]
	 475  						d.hashPrev[index&windowMask] = *hh
	 476  						// Set the head of the hash chain to us.
	 477  						*hh = uint32(index + d.hashOffset)
	 478  					}
	 479  				}
	 480  				d.index = index
	 481  
	 482  				if d.fastSkipHashing == skipNever {
	 483  					d.byteAvailable = false
	 484  					d.length = minMatchLength - 1
	 485  				}
	 486  			} else {
	 487  				// For matches this long, we don't bother inserting each individual
	 488  				// item into the table.
	 489  				d.index += d.length
	 490  				if d.index < d.maxInsertIndex {
	 491  					d.hash = hash4(d.window[d.index : d.index+minMatchLength])
	 492  				}
	 493  			}
	 494  			if len(d.tokens) == maxFlateBlockTokens {
	 495  				// The block includes the current character
	 496  				if d.err = d.writeBlock(d.tokens, d.index); d.err != nil {
	 497  					return
	 498  				}
	 499  				d.tokens = d.tokens[:0]
	 500  			}
	 501  		} else {
	 502  			if d.fastSkipHashing != skipNever || d.byteAvailable {
	 503  				i := d.index - 1
	 504  				if d.fastSkipHashing != skipNever {
	 505  					i = d.index
	 506  				}
	 507  				d.tokens = append(d.tokens, literalToken(uint32(d.window[i])))
	 508  				if len(d.tokens) == maxFlateBlockTokens {
	 509  					if d.err = d.writeBlock(d.tokens, i+1); d.err != nil {
	 510  						return
	 511  					}
	 512  					d.tokens = d.tokens[:0]
	 513  				}
	 514  			}
	 515  			d.index++
	 516  			if d.fastSkipHashing == skipNever {
	 517  				d.byteAvailable = true
	 518  			}
	 519  		}
	 520  	}
	 521  }
	 522  
	 523  func (d *compressor) fillStore(b []byte) int {
	 524  	n := copy(d.window[d.windowEnd:], b)
	 525  	d.windowEnd += n
	 526  	return n
	 527  }
	 528  
	 529  func (d *compressor) store() {
	 530  	if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
	 531  		d.err = d.writeStoredBlock(d.window[:d.windowEnd])
	 532  		d.windowEnd = 0
	 533  	}
	 534  }
	 535  
	 536  // storeHuff compresses and stores the currently added data
	 537  // when the d.window is full or we are at the end of the stream.
	 538  // Any error that occurred will be in d.err
	 539  func (d *compressor) storeHuff() {
	 540  	if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
	 541  		return
	 542  	}
	 543  	d.w.writeBlockHuff(false, d.window[:d.windowEnd])
	 544  	d.err = d.w.err
	 545  	d.windowEnd = 0
	 546  }
	 547  
	 548  func (d *compressor) write(b []byte) (n int, err error) {
	 549  	if d.err != nil {
	 550  		return 0, d.err
	 551  	}
	 552  	n = len(b)
	 553  	for len(b) > 0 {
	 554  		d.step(d)
	 555  		b = b[d.fill(d, b):]
	 556  		if d.err != nil {
	 557  			return 0, d.err
	 558  		}
	 559  	}
	 560  	return n, nil
	 561  }
	 562  
	 563  func (d *compressor) syncFlush() error {
	 564  	if d.err != nil {
	 565  		return d.err
	 566  	}
	 567  	d.sync = true
	 568  	d.step(d)
	 569  	if d.err == nil {
	 570  		d.w.writeStoredHeader(0, false)
	 571  		d.w.flush()
	 572  		d.err = d.w.err
	 573  	}
	 574  	d.sync = false
	 575  	return d.err
	 576  }
	 577  
	 578  func (d *compressor) init(w io.Writer, level int) (err error) {
	 579  	d.w = newHuffmanBitWriter(w)
	 580  
	 581  	switch {
	 582  	case level == NoCompression:
	 583  		d.window = make([]byte, maxStoreBlockSize)
	 584  		d.fill = (*compressor).fillStore
	 585  		d.step = (*compressor).store
	 586  	case level == HuffmanOnly:
	 587  		d.window = make([]byte, maxStoreBlockSize)
	 588  		d.fill = (*compressor).fillStore
	 589  		d.step = (*compressor).storeHuff
	 590  	case level == BestSpeed:
	 591  		d.compressionLevel = levels[level]
	 592  		d.window = make([]byte, maxStoreBlockSize)
	 593  		d.fill = (*compressor).fillStore
	 594  		d.step = (*compressor).encSpeed
	 595  		d.bestSpeed = newDeflateFast()
	 596  		d.tokens = make([]token, maxStoreBlockSize)
	 597  	case level == DefaultCompression:
	 598  		level = 6
	 599  		fallthrough
	 600  	case 2 <= level && level <= 9:
	 601  		d.compressionLevel = levels[level]
	 602  		d.initDeflate()
	 603  		d.fill = (*compressor).fillDeflate
	 604  		d.step = (*compressor).deflate
	 605  	default:
	 606  		return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
	 607  	}
	 608  	return nil
	 609  }
	 610  
	 611  func (d *compressor) reset(w io.Writer) {
	 612  	d.w.reset(w)
	 613  	d.sync = false
	 614  	d.err = nil
	 615  	switch d.compressionLevel.level {
	 616  	case NoCompression:
	 617  		d.windowEnd = 0
	 618  	case BestSpeed:
	 619  		d.windowEnd = 0
	 620  		d.tokens = d.tokens[:0]
	 621  		d.bestSpeed.reset()
	 622  	default:
	 623  		d.chainHead = -1
	 624  		for i := range d.hashHead {
	 625  			d.hashHead[i] = 0
	 626  		}
	 627  		for i := range d.hashPrev {
	 628  			d.hashPrev[i] = 0
	 629  		}
	 630  		d.hashOffset = 1
	 631  		d.index, d.windowEnd = 0, 0
	 632  		d.blockStart, d.byteAvailable = 0, false
	 633  		d.tokens = d.tokens[:0]
	 634  		d.length = minMatchLength - 1
	 635  		d.offset = 0
	 636  		d.hash = 0
	 637  		d.maxInsertIndex = 0
	 638  	}
	 639  }
	 640  
	 641  func (d *compressor) close() error {
	 642  	if d.err != nil {
	 643  		return d.err
	 644  	}
	 645  	d.sync = true
	 646  	d.step(d)
	 647  	if d.err != nil {
	 648  		return d.err
	 649  	}
	 650  	if d.w.writeStoredHeader(0, true); d.w.err != nil {
	 651  		return d.w.err
	 652  	}
	 653  	d.w.flush()
	 654  	return d.w.err
	 655  }
	 656  
	 657  // NewWriter returns a new Writer compressing data at the given level.
	 658  // Following zlib, levels range from 1 (BestSpeed) to 9 (BestCompression);
	 659  // higher levels typically run slower but compress more. Level 0
	 660  // (NoCompression) does not attempt any compression; it only adds the
	 661  // necessary DEFLATE framing.
	 662  // Level -1 (DefaultCompression) uses the default compression level.
	 663  // Level -2 (HuffmanOnly) will use Huffman compression only, giving
	 664  // a very fast compression for all types of input, but sacrificing considerable
	 665  // compression efficiency.
	 666  //
	 667  // If level is in the range [-2, 9] then the error returned will be nil.
	 668  // Otherwise the error returned will be non-nil.
	 669  func NewWriter(w io.Writer, level int) (*Writer, error) {
	 670  	var dw Writer
	 671  	if err := dw.d.init(w, level); err != nil {
	 672  		return nil, err
	 673  	}
	 674  	return &dw, nil
	 675  }
	 676  
	 677  // NewWriterDict is like NewWriter but initializes the new
	 678  // Writer with a preset dictionary. The returned Writer behaves
	 679  // as if the dictionary had been written to it without producing
	 680  // any compressed output. The compressed data written to w
	 681  // can only be decompressed by a Reader initialized with the
	 682  // same dictionary.
	 683  func NewWriterDict(w io.Writer, level int, dict []byte) (*Writer, error) {
	 684  	dw := &dictWriter{w}
	 685  	zw, err := NewWriter(dw, level)
	 686  	if err != nil {
	 687  		return nil, err
	 688  	}
	 689  	zw.d.fillWindow(dict)
	 690  	zw.dict = append(zw.dict, dict...) // duplicate dictionary for Reset method.
	 691  	return zw, err
	 692  }
	 693  
	 694  type dictWriter struct {
	 695  	w io.Writer
	 696  }
	 697  
	 698  func (w *dictWriter) Write(b []byte) (n int, err error) {
	 699  	return w.w.Write(b)
	 700  }
	 701  
	 702  // A Writer takes data written to it and writes the compressed
	 703  // form of that data to an underlying writer (see NewWriter).
	 704  type Writer struct {
	 705  	d		compressor
	 706  	dict []byte
	 707  }
	 708  
	 709  // Write writes data to w, which will eventually write the
	 710  // compressed form of data to its underlying writer.
	 711  func (w *Writer) Write(data []byte) (n int, err error) {
	 712  	return w.d.write(data)
	 713  }
	 714  
	 715  // Flush flushes any pending data to the underlying writer.
	 716  // It is useful mainly in compressed network protocols, to ensure that
	 717  // a remote reader has enough data to reconstruct a packet.
	 718  // Flush does not return until the data has been written.
	 719  // Calling Flush when there is no pending data still causes the Writer
	 720  // to emit a sync marker of at least 4 bytes.
	 721  // If the underlying writer returns an error, Flush returns that error.
	 722  //
	 723  // In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
	 724  func (w *Writer) Flush() error {
	 725  	// For more about flushing:
	 726  	// https://www.bolet.org/~pornin/deflate-flush.html
	 727  	return w.d.syncFlush()
	 728  }
	 729  
	 730  // Close flushes and closes the writer.
	 731  func (w *Writer) Close() error {
	 732  	return w.d.close()
	 733  }
	 734  
	 735  // Reset discards the writer's state and makes it equivalent to
	 736  // the result of NewWriter or NewWriterDict called with dst
	 737  // and w's level and dictionary.
	 738  func (w *Writer) Reset(dst io.Writer) {
	 739  	if dw, ok := w.d.w.writer.(*dictWriter); ok {
	 740  		// w was created with NewWriterDict
	 741  		dw.w = dst
	 742  		w.d.reset(dw)
	 743  		w.d.fillWindow(w.dict)
	 744  	} else {
	 745  		// w was created with NewWriter
	 746  		w.d.reset(dst)
	 747  	}
	 748  }
	 749  

View as plain text