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.
17 DefaultCompression = -1
19 windowSize = 1 << logWindowSize
20 windowMask = windowSize - 1
21 logMaxOffsetSize = 15 // Standard DEFLATE
22 minMatchLength = 3 // The smallest match that the compressor looks for
23 maxMatchLength = 258 // The longest match for the compressor
24 minOffsetSize = 1 // The shortest offset that makes any sence
26 // The maximum number of tokens we put into a single flat block, just too
27 // stop things from getting too large.
28 maxFlateBlockTokens = 1 << 14
29 maxStoreBlockSize = 65535
31 hashSize = 1 << hashBits
32 hashMask = (1 << hashBits) - 1
33 hashShift = (hashBits + minMatchLength - 1) / minMatchLength
36 type compressionLevel struct {
37 good, lazy, nice, chain, fastSkipHashing int
40 var levels = []compressionLevel{
42 // For levels 1-3 we don't bother trying with lazy matches
46 // Levels 4-9 use increasingly more lazy matching
47 // and increasingly stringent conditions for "good enough".
48 {4, 4, 16, 16, math.MaxInt32},
49 {8, 16, 32, 32, math.MaxInt32},
50 {8, 16, 128, 128, math.MaxInt32},
51 {8, 32, 128, 256, math.MaxInt32},
52 {32, 128, 258, 1024, math.MaxInt32},
53 {32, 258, 258, 4096, math.MaxInt32},
56 type compressor struct {
61 // compression algorithm
62 fill func(*compressor, []byte) int // copy data to window
63 step func(*compressor) // process window
64 sync bool // requesting flush
67 // hashHead[hashValue] contains the largest inputIndex with the specified hash value
68 // If hashHead[hashValue] is within the current window, then
69 // hashPrev[hashHead[hashValue] & windowMask] contains the previous index
70 // with the same hash value.
75 // input window: unprocessed data is window[index:windowEnd]
79 blockStart int // window index where current tokens start
80 byteAvailable bool // if true, still need to process window[index-1].
82 // queued output tokens: tokens[:ti]
94 func (d *compressor) fillDeflate(b []byte) int {
95 if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
96 // shift the window by windowSize
97 copy(d.window, d.window[windowSize:2*windowSize])
99 d.windowEnd -= windowSize
100 if d.blockStart >= windowSize {
101 d.blockStart -= windowSize
103 d.blockStart = math.MaxInt32
105 for i, h := range d.hashHead {
112 for i, h := range d.hashPrev {
120 n := copy(d.window[d.windowEnd:], b)
125 func (d *compressor) writeBlock(tokens []token, index int, eof bool) error {
126 if index > 0 || eof {
128 if d.blockStart <= index {
129 window = d.window[d.blockStart:index]
132 d.w.writeBlock(tokens, eof, window)
138 // Try to find a match starting at index whose length is greater than prevSize.
139 // We only look at chainCount possibilities before giving up.
140 func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
141 minMatchLook := maxMatchLength
142 if lookahead < minMatchLook {
143 minMatchLook = lookahead
146 win := d.window[0 : pos+minMatchLook]
148 // We quit when we get a match that's at least nice long
149 nice := len(win) - pos
154 // If we've got a match that's good enough, only look in 1/4 the chain.
157 if length >= d.good {
163 wEnd := win[pos+length]
164 minIndex := pos - windowSize
166 for i := prevHead; tries > 0; tries-- {
167 if w0 == win[i] && w1 == win[i+1] && wEnd == win[i+length] {
168 // The hash function ensures that if win[i] and win[i+1] match, win[i+2] matches
171 for pos+n < len(win) && win[i+n] == win[pos+n] {
174 if n > length && (n > 3 || pos-i <= 4096) {
179 // The match is good enough that we don't try to find a better one.
186 // hashPrev[i & windowMask] has already been overwritten, so stop now.
189 if i = d.hashPrev[i&windowMask]; i < minIndex || i < 0 {
196 func (d *compressor) writeStoredBlock(buf []byte) error {
197 if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
204 func (d *compressor) initDeflate() {
205 d.hashHead = make([]int, hashSize)
206 d.hashPrev = make([]int, windowSize)
207 d.window = make([]byte, 2*windowSize)
208 fillInts(d.hashHead, -1)
209 d.tokens = make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1)
210 d.length = minMatchLength - 1
212 d.byteAvailable = false
219 func (d *compressor) deflate() {
220 if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
224 d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
225 if d.index < d.maxInsertIndex {
226 d.hash = int(d.window[d.index])<<hashShift + int(d.window[d.index+1])
231 if d.index > d.windowEnd {
232 panic("index > windowEnd")
234 lookahead := d.windowEnd - d.index
235 if lookahead < minMatchLength+maxMatchLength {
239 if d.index > d.windowEnd {
240 panic("index > windowEnd")
243 // Flush current output block if any.
245 // There is still one pending token that needs to be flushed
246 d.tokens[d.ti] = literalToken(uint32(d.window[d.index-1]))
248 d.byteAvailable = false
251 if d.err = d.writeBlock(d.tokens[0:d.ti], d.index, false); d.err != nil {
259 if d.index < d.maxInsertIndex {
261 d.hash = (d.hash<<hashShift + int(d.window[d.index+2])) & hashMask
262 d.chainHead = d.hashHead[d.hash]
263 d.hashPrev[d.index&windowMask] = d.chainHead
264 d.hashHead[d.hash] = d.index
266 prevLength := d.length
267 prevOffset := d.offset
268 d.length = minMatchLength - 1
270 minIndex := d.index - windowSize
275 if d.chainHead >= minIndex &&
276 (d.fastSkipHashing != 0 && lookahead > minMatchLength-1 ||
277 d.fastSkipHashing == 0 && lookahead > prevLength && prevLength < d.lazy) {
278 if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead, minMatchLength-1, lookahead); ok {
283 if d.fastSkipHashing != 0 && d.length >= minMatchLength ||
284 d.fastSkipHashing == 0 && prevLength >= minMatchLength && d.length <= prevLength {
285 // There was a match at the previous step, and the current match is
286 // not better. Output the previous match.
287 if d.fastSkipHashing != 0 {
288 d.tokens[d.ti] = matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize))
290 d.tokens[d.ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))
293 // Insert in the hash table all strings up to the end of the match.
294 // index and index-1 are already inserted. If there is not enough
295 // lookahead, the last two strings are not inserted into the hash
297 if d.length <= d.fastSkipHashing {
299 if d.fastSkipHashing != 0 {
300 newIndex = d.index + d.length
302 newIndex = prevLength - 1
304 for d.index++; d.index < newIndex; d.index++ {
305 if d.index < d.maxInsertIndex {
306 d.hash = (d.hash<<hashShift + int(d.window[d.index+2])) & hashMask
307 // Get previous value with the same hash.
308 // Our chain should point to the previous value.
309 d.hashPrev[d.index&windowMask] = d.hashHead[d.hash]
310 // Set the head of the hash chain to us.
311 d.hashHead[d.hash] = d.index
314 if d.fastSkipHashing == 0 {
315 d.byteAvailable = false
316 d.length = minMatchLength - 1
319 // For matches this long, we don't bother inserting each individual
320 // item into the table.
322 d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1]))
324 if d.ti == maxFlateBlockTokens {
325 // The block includes the current character
326 if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
332 if d.fastSkipHashing != 0 || d.byteAvailable {
334 if d.fastSkipHashing != 0 {
337 d.tokens[d.ti] = literalToken(uint32(d.window[i]))
339 if d.ti == maxFlateBlockTokens {
340 if d.err = d.writeBlock(d.tokens, i+1, false); d.err != nil {
347 if d.fastSkipHashing == 0 {
348 d.byteAvailable = true
354 func (d *compressor) fillStore(b []byte) int {
355 n := copy(d.window[d.windowEnd:], b)
360 func (d *compressor) store() {
362 d.err = d.writeStoredBlock(d.window[:d.windowEnd])
367 func (d *compressor) write(b []byte) (n int, err error) {
377 func (d *compressor) syncFlush() error {
381 d.w.writeStoredHeader(0, false)
389 func (d *compressor) init(w io.Writer, level int) (err error) {
390 d.w = newHuffmanBitWriter(w)
393 case level == NoCompression:
394 d.window = make([]byte, maxStoreBlockSize)
395 d.fill = (*compressor).fillStore
396 d.step = (*compressor).store
397 case level == DefaultCompression:
400 case 1 <= level && level <= 9:
401 d.compressionLevel = levels[level]
403 d.fill = (*compressor).fillDeflate
404 d.step = (*compressor).deflate
406 return WrongValueError{"level", 0, 9, int32(level)}
411 func (d *compressor) close() error {
417 if d.w.writeStoredHeader(0, true); d.w.err != nil {
424 // NewWriter returns a new Writer compressing
425 // data at the given level. Following zlib, levels
426 // range from 1 (BestSpeed) to 9 (BestCompression);
427 // higher levels typically run slower but compress more.
428 // Level 0 (NoCompression) does not attempt any
429 // compression; it only adds the necessary DEFLATE framing.
430 func NewWriter(w io.Writer, level int) *Writer {
431 const logWindowSize = logMaxOffsetSize
437 // NewWriterDict is like NewWriter but initializes the new
438 // Writer with a preset dictionary. The returned Writer behaves
439 // as if the dictionary had been written to it without producing
440 // any compressed output. The compressed data written to w
441 // can only be decompressed by a Reader initialized with the
443 func NewWriterDict(w io.Writer, level int, dict []byte) *Writer {
444 dw := &dictWriter{w, false}
445 zw := NewWriter(dw, level)
452 type dictWriter struct {
457 func (w *dictWriter) Write(b []byte) (n int, err error) {
464 // A Writer takes data written to it and writes the compressed
465 // form of that data to an underlying writer (see NewWriter).
470 // Write writes data to w, which will eventually write the
471 // compressed form of data to its underlying writer.
472 func (w *Writer) Write(data []byte) (n int, err error) {
473 return w.d.write(data)
476 // Flush flushes any pending compressed data to the underlying writer.
477 // It is useful mainly in compressed network protocols, to ensure that
478 // a remote reader has enough data to reconstruct a packet.
479 // Flush does not return until the data has been written.
480 // If the underlying writer returns an error, Flush returns that error.
482 // In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
483 func (w *Writer) Flush() error {
484 // For more about flushing:
485 // http://www.bolet.org/~pornin/deflate-flush.html
486 return w.d.syncFlush()
489 // Close flushes and closes the writer.
490 func (w *Writer) Close() error {