URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [compress/] [flate/] [deflate.go] - Blame information for rev 801

Go to most recent revision | Details | Compare with Previous | View Log


// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
package flate
 
import (
        "io"
        "math"
)
 
const (
        NoCompression      = 0
        BestSpeed          = 1
        fastCompression    = 3
        BestCompression    = 9
        DefaultCompression = -1
        logWindowSize      = 15
        windowSize         = 1 << logWindowSize
        windowMask         = windowSize - 1
        logMaxOffsetSize   = 15  // Standard DEFLATE
        minMatchLength     = 3   // The smallest match that the compressor looks for
        maxMatchLength     = 258 // The longest match for the compressor
        minOffsetSize      = 1   // The shortest offset that makes any sence
 
        // The maximum number of tokens we put into a single flat block, just too
        // stop things from getting too large.
        maxFlateBlockTokens = 1 << 14
        maxStoreBlockSize   = 65535
        hashBits            = 17
        hashSize            = 1 << hashBits
        hashMask            = (1 << hashBits) - 1
        hashShift           = (hashBits + minMatchLength - 1) / minMatchLength
 
        skipNever = math.MaxInt32
)
 
type compressionLevel struct {
        good, lazy, nice, chain, fastSkipHashing int
}
 
var levels = []compressionLevel{
        {}, // 0
        // For levels 1-3 we don't bother trying with lazy matches
        {3, 0, 8, 4, 4},
        {3, 0, 16, 8, 5},
        {3, 0, 32, 32, 6},
        // Levels 4-9 use increasingly more lazy matching
        // and increasingly stringent conditions for "good enough".
        {4, 4, 16, 16, skipNever},
        {8, 16, 32, 32, skipNever},
        {8, 16, 128, 128, skipNever},
        {8, 32, 128, 256, skipNever},
        {32, 128, 258, 1024, skipNever},
        {32, 258, 258, 4096, skipNever},
}
 
type compressor struct {
        compressionLevel
 
        w *huffmanBitWriter
 
        // compression algorithm
        fill func(*compressor, []byte) int // copy data to window
        step func(*compressor)             // process window
        sync bool                          // requesting flush
 
        // Input hash chains
        // hashHead[hashValue] contains the largest inputIndex with the specified hash value
        // If hashHead[hashValue] is within the current window, then
        // hashPrev[hashHead[hashValue] & windowMask] contains the previous index
        // with the same hash value.
        chainHead  int
        hashHead   []int
        hashPrev   []int
        hashOffset int
 
        // input window: unprocessed data is window[index:windowEnd]
        index         int
        window        []byte
        windowEnd     int
        blockStart    int  // window index where current tokens start
        byteAvailable bool // if true, still need to process window[index-1].
 
        // queued output tokens
        tokens []token
 
        // deflate state
        length         int
        offset         int
        hash           int
        maxInsertIndex int
        err            error
}
 
func (d *compressor) fillDeflate(b []byte) int {
        if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
                // shift the window by windowSize
                copy(d.window, d.window[windowSize:2*windowSize])
                d.index -= windowSize
                d.windowEnd -= windowSize
                if d.blockStart >= windowSize {
                        d.blockStart -= windowSize
                } else {
                        d.blockStart = math.MaxInt32
                }
                d.hashOffset += windowSize
        }
        n := copy(d.window[d.windowEnd:], b)
        d.windowEnd += n
        return n
}
 
func (d *compressor) writeBlock(tokens []token, index int, eof bool) error {
        if index > 0 || eof {
                var window []byte
                if d.blockStart <= index {
                        window = d.window[d.blockStart:index]
                }
                d.blockStart = index
                d.w.writeBlock(tokens, eof, window)
                return d.w.err
        }
        return nil
}
 
// Try to find a match starting at index whose length is greater than prevSize.
// We only look at chainCount possibilities before giving up.
func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
        minMatchLook := maxMatchLength
        if lookahead < minMatchLook {
                minMatchLook = lookahead
        }
 
        win := d.window[0 : pos+minMatchLook]
 
        // We quit when we get a match that's at least nice long
        nice := len(win) - pos
        if d.nice < nice {
                nice = d.nice
        }
 
        // If we've got a match that's good enough, only look in 1/4 the chain.
        tries := d.chain
        length = prevLength
        if length >= d.good {
                tries >>= 2
        }
 
        w0 := win[pos]
        w1 := win[pos+1]
        wEnd := win[pos+length]
        minIndex := pos - windowSize
 
        for i := prevHead; tries > 0; tries-- {
                if w0 == win[i] && w1 == win[i+1] && wEnd == win[i+length] {
                        // The hash function ensures that if win[i] and win[i+1] match, win[i+2] matches
 
                        n := 3
                        for pos+n < len(win) && win[i+n] == win[pos+n] {
                                n++
                        }
                        if n > length && (n > 3 || pos-i <= 4096) {
                                length = n
                                offset = pos - i
                                ok = true
                                if n >= nice {
                                        // The match is good enough that we don't try to find a better one.
                                        break
                                }
                                wEnd = win[pos+n]
                        }
                }
                if i == minIndex {
                        // hashPrev[i & windowMask] has already been overwritten, so stop now.
                        break
                }
                if i = d.hashPrev[i&windowMask] - d.hashOffset; i < minIndex || i < 0 {
                        break
                }
        }
        return
}
 
func (d *compressor) writeStoredBlock(buf []byte) error {
        if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
                return d.w.err
        }
        d.w.writeBytes(buf)
        return d.w.err
}
 
func (d *compressor) initDeflate() {
        d.hashHead = make([]int, hashSize)
        d.hashPrev = make([]int, windowSize)
        d.window = make([]byte, 2*windowSize)
        d.hashOffset = 1
        d.tokens = make([]token, 0, maxFlateBlockTokens+1)
        d.length = minMatchLength - 1
        d.offset = 0
        d.byteAvailable = false
        d.index = 0
        d.hash = 0
        d.chainHead = -1
}
 
func (d *compressor) deflate() {
        if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
                return
        }
 
        d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
        if d.index < d.maxInsertIndex {
                d.hash = int(d.window[d.index])<
        }
 
Loop:
        for {
                if d.index > d.windowEnd {
                        panic("index > windowEnd")
                }
                lookahead := d.windowEnd - d.index
                if lookahead < minMatchLength+maxMatchLength {
                        if !d.sync {
                                break Loop
                        }
                        if d.index > d.windowEnd {
                                panic("index > windowEnd")
                        }
                        if lookahead == 0 {
                                // Flush current output block if any.
                                if d.byteAvailable {
                                        // There is still one pending token that needs to be flushed
                                        d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1])))
                                        d.byteAvailable = false
                                }
                                if len(d.tokens) > 0 {
                                        if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
                                                return
                                        }
                                        d.tokens = d.tokens[:0]
                                }
                                break Loop
                        }
                }
                if d.index < d.maxInsertIndex {
                        // Update the hash
                        d.hash = (d.hash<
                        d.chainHead = d.hashHead[d.hash]
                        d.hashPrev[d.index&windowMask] = d.chainHead
                        d.hashHead[d.hash] = d.index + d.hashOffset
                }
                prevLength := d.length
                prevOffset := d.offset
                d.length = minMatchLength - 1
                d.offset = 0
                minIndex := d.index - windowSize
                if minIndex < 0 {
                        minIndex = 0
                }
 
                if d.chainHead-d.hashOffset >= minIndex &&
                        (d.fastSkipHashing != skipNever && lookahead > minMatchLength-1 ||
                                d.fastSkipHashing == skipNever && lookahead > prevLength && prevLength < d.lazy) {
                        if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
                                d.length = newLength
                                d.offset = newOffset
                        }
                }
                if d.fastSkipHashing != skipNever && d.length >= minMatchLength ||
                        d.fastSkipHashing == skipNever && prevLength >= minMatchLength && d.length <= prevLength {
                        // There was a match at the previous step, and the current match is
                        // not better. Output the previous match.
                        if d.fastSkipHashing != skipNever {
                                d.tokens = append(d.tokens, matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize)))
                        } else {
                                d.tokens = append(d.tokens, matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)))
                        }
                        // Insert in the hash table all strings up to the end of the match.
                        // index and index-1 are already inserted. If there is not enough
                        // lookahead, the last two strings are not inserted into the hash
                        // table.
                        if d.length <= d.fastSkipHashing {
                                var newIndex int
                                if d.fastSkipHashing != skipNever {
                                        newIndex = d.index + d.length
                                } else {
                                        newIndex = d.index + prevLength - 1
                                }
                                for d.index++; d.index < newIndex; d.index++ {
                                        if d.index < d.maxInsertIndex {
                                                d.hash = (d.hash<
                                                // Get previous value with the same hash.
                                                // Our chain should point to the previous value.
                                                d.hashPrev[d.index&windowMask] = d.hashHead[d.hash]
                                                // Set the head of the hash chain to us.
                                                d.hashHead[d.hash] = d.index + d.hashOffset
                                        }
                                }
                                if d.fastSkipHashing == skipNever {
                                        d.byteAvailable = false
                                        d.length = minMatchLength - 1
                                }
                        } else {
                                // For matches this long, we don't bother inserting each individual
                                // item into the table.
                                d.index += d.length
                                if d.index < d.maxInsertIndex {
                                        d.hash = (int(d.window[d.index])<
                                }
                        }
                        if len(d.tokens) == maxFlateBlockTokens {
                                // The block includes the current character
                                if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
                                        return
                                }
                                d.tokens = d.tokens[:0]
                        }
                } else {
                        if d.fastSkipHashing != skipNever || d.byteAvailable {
                                i := d.index - 1
                                if d.fastSkipHashing != skipNever {
                                        i = d.index
                                }
                                d.tokens = append(d.tokens, literalToken(uint32(d.window[i])))
                                if len(d.tokens) == maxFlateBlockTokens {
                                        if d.err = d.writeBlock(d.tokens, i+1, false); d.err != nil {
                                                return
                                        }
                                        d.tokens = d.tokens[:0]
                                }
                        }
                        d.index++
                        if d.fastSkipHashing == skipNever {
                                d.byteAvailable = true
                        }
                }
        }
}
 
func (d *compressor) fillStore(b []byte) int {
        n := copy(d.window[d.windowEnd:], b)
        d.windowEnd += n
        return n
}
 
func (d *compressor) store() {
        if d.windowEnd > 0 {
                d.err = d.writeStoredBlock(d.window[:d.windowEnd])
        }
        d.windowEnd = 0
}
 
func (d *compressor) write(b []byte) (n int, err error) {
        n = len(b)
        b = b[d.fill(d, b):]
        for len(b) > 0 {
                d.step(d)
                b = b[d.fill(d, b):]
        }
        return n, d.err
}
 
func (d *compressor) syncFlush() error {
        d.sync = true
        d.step(d)
        if d.err == nil {
                d.w.writeStoredHeader(0, false)
                d.w.flush()
                d.err = d.w.err
        }
        d.sync = false
        return d.err
}
 
func (d *compressor) init(w io.Writer, level int) (err error) {
        d.w = newHuffmanBitWriter(w)
 
        switch {
        case level == NoCompression:
                d.window = make([]byte, maxStoreBlockSize)
                d.fill = (*compressor).fillStore
                d.step = (*compressor).store
        case level == DefaultCompression:
                level = 6
                fallthrough
        case 1 <= level && level <= 9:
                d.compressionLevel = levels[level]
                d.initDeflate()
                d.fill = (*compressor).fillDeflate
                d.step = (*compressor).deflate
        default:
                return WrongValueError{"level", 0, 9, int32(level)}
        }
        return nil
}
 
func (d *compressor) close() error {
        d.sync = true
        d.step(d)
        if d.err != nil {
                return d.err
        }
        if d.w.writeStoredHeader(0, true); d.w.err != nil {
                return d.w.err
        }
        d.w.flush()
        return d.w.err
}
 
// NewWriter returns a new Writer compressing
// data at the given level.  Following zlib, levels
// range from 1 (BestSpeed) to 9 (BestCompression);
// higher levels typically run slower but compress more.
// Level 0 (NoCompression) does not attempt any
// compression; it only adds the necessary DEFLATE framing.
func NewWriter(w io.Writer, level int) *Writer {
        const logWindowSize = logMaxOffsetSize
        var dw Writer
        dw.d.init(w, level)
        return &dw
}
 
// NewWriterDict is like NewWriter but initializes the new
// Writer with a preset dictionary.  The returned Writer behaves
// as if the dictionary had been written to it without producing
// any compressed output.  The compressed data written to w
// can only be decompressed by a Reader initialized with the
// same dictionary.
func NewWriterDict(w io.Writer, level int, dict []byte) *Writer {
        dw := &dictWriter{w, false}
        zw := NewWriter(dw, level)
        zw.Write(dict)
        zw.Flush()
        dw.enabled = true
        return zw
}
 
type dictWriter struct {
        w       io.Writer
        enabled bool
}
 
func (w *dictWriter) Write(b []byte) (n int, err error) {
        if w.enabled {
                return w.w.Write(b)
        }
        return len(b), nil
}
 
// A Writer takes data written to it and writes the compressed
// form of that data to an underlying writer (see NewWriter).
type Writer struct {
        d compressor
}
 
// Write writes data to w, which will eventually write the
// compressed form of data to its underlying writer.
func (w *Writer) Write(data []byte) (n int, err error) {
        return w.d.write(data)
}
 
// Flush flushes any pending compressed data to the underlying writer.
// It is useful mainly in compressed network protocols, to ensure that
// a remote reader has enough data to reconstruct a packet.
// Flush does not return until the data has been written.
// If the underlying writer returns an error, Flush returns that error.
//
// In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
func (w *Writer) Flush() error {
        // For more about flushing:
        // http://www.bolet.org/~pornin/deflate-flush.html
        return w.d.syncFlush()
}
 
// Close flushes and closes the writer.
func (w *Writer) Close() error {
        return w.d.close()
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [compress/] [flate/] [deflate.go] - Blame information for rev 801

Line No.	Rev	Author	Line
1	747	jeremybenn	`// 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			`"io"`
9			`"math"`
10			`)`
11
12			`const (`
13			`NoCompression = 0`
14			`BestSpeed = 1`
15			`fastCompression = 3`
16			`BestCompression = 9`
17			`DefaultCompression = -1`
18			`logWindowSize = 15`
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`
25
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`
30			`hashBits = 17`
31			`hashSize = 1 << hashBits`
32			`hashMask = (1 << hashBits) - 1`
33			`hashShift = (hashBits + minMatchLength - 1) / minMatchLength`
34
35			`skipNever = math.MaxInt32`
36			`)`
37
38			`type compressionLevel struct {`
39			`good, lazy, nice, chain, fastSkipHashing int`
40			`}`
41
42			`var levels = []compressionLevel{`
43			`{}, // 0`
44			`// For levels 1-3 we don't bother trying with lazy matches`
45			`{3, 0, 8, 4, 4},`
46			`{3, 0, 16, 8, 5},`
47			`{3, 0, 32, 32, 6},`
48			`// Levels 4-9 use increasingly more lazy matching`
49			`// and increasingly stringent conditions for "good enough".`
50			`{4, 4, 16, 16, skipNever},`
51			`{8, 16, 32, 32, skipNever},`
52			`{8, 16, 128, 128, skipNever},`
53			`{8, 32, 128, 256, skipNever},`
54			`{32, 128, 258, 1024, skipNever},`
55			`{32, 258, 258, 4096, skipNever},`
56			`}`
57
58			`type compressor struct {`
59			`compressionLevel`
60
61			`w *huffmanBitWriter`
62
63			`// compression algorithm`
64			`fill func(*compressor, []byte) int // copy data to window`
65			`step func(*compressor) // process window`
66			`sync bool // requesting flush`
67
68			`// Input hash chains`
69			`// hashHead[hashValue] contains the largest inputIndex with the specified hash value`
70			`// If hashHead[hashValue] is within the current window, then`
71			`// hashPrev[hashHead[hashValue] & windowMask] contains the previous index`
72			`// with the same hash value.`
73			`chainHead int`
74			`hashHead []int`
75			`hashPrev []int`
76			`hashOffset int`
77
78			`// input window: unprocessed data is window[index:windowEnd]`
79			`index int`
80			`window []byte`
81			`windowEnd int`
82			`blockStart int // window index where current tokens start`
83			`byteAvailable bool // if true, still need to process window[index-1].`
84
85			`// queued output tokens`
86			`tokens []token`
87
88			`// deflate state`
89			`length int`
90			`offset int`
91			`hash int`
92			`maxInsertIndex int`
93			`err error`
94			`}`
95
96			`func (d *compressor) fillDeflate(b []byte) int {`
97			`if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {`
98			`// shift the window by windowSize`
99			`copy(d.window, d.window[windowSize:2*windowSize])`
100			`d.index -= windowSize`
101			`d.windowEnd -= windowSize`
102			`if d.blockStart >= windowSize {`
103			`d.blockStart -= windowSize`
104			`} else {`
105			`d.blockStart = math.MaxInt32`
106			`}`
107			`d.hashOffset += windowSize`
108			`}`
109			`n := copy(d.window[d.windowEnd:], b)`
110			`d.windowEnd += n`
111			`return n`
112			`}`
113
114			`func (d *compressor) writeBlock(tokens []token, index int, eof bool) error {`
115			`if index > 0 \|\| eof {`
116			`var window []byte`
117			`if d.blockStart <= index {`
118			`window = d.window[d.blockStart:index]`
119			`}`
120			`d.blockStart = index`
121			`d.w.writeBlock(tokens, eof, window)`
122			`return d.w.err`
123			`}`
124			`return nil`
125			`}`
126
127			`// Try to find a match starting at index whose length is greater than prevSize.`
128			`// We only look at chainCount possibilities before giving up.`
129			`func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {`
130			`minMatchLook := maxMatchLength`
131			`if lookahead < minMatchLook {`
132			`minMatchLook = lookahead`
133			`}`
134
135			`win := d.window[0 : pos+minMatchLook]`
136
137			`// We quit when we get a match that's at least nice long`
138			`nice := len(win) - pos`
139			`if d.nice < nice {`
140			`nice = d.nice`
141			`}`
142
143			`// If we've got a match that's good enough, only look in 1/4 the chain.`
144			`tries := d.chain`
145			`length = prevLength`
146			`if length >= d.good {`
147			`tries >>= 2`
148			`}`
149
150			`w0 := win[pos]`
151			`w1 := win[pos+1]`
152			`wEnd := win[pos+length]`
153			`minIndex := pos - windowSize`
154
155			`for i := prevHead; tries > 0; tries-- {`
156			`if w0 == win[i] && w1 == win[i+1] && wEnd == win[i+length] {`
157			`// The hash function ensures that if win[i] and win[i+1] match, win[i+2] matches`
158
159			`n := 3`
160			`for pos+n < len(win) && win[i+n] == win[pos+n] {`
161			`n++`
162			`}`
163			`if n > length && (n > 3 \|\| pos-i <= 4096) {`
164			`length = n`
165			`offset = pos - i`
166			`ok = true`
167			`if n >= nice {`
168			`// The match is good enough that we don't try to find a better one.`
169			`break`
170			`}`
171			`wEnd = win[pos+n]`
172			`}`
173			`}`
174			`if i == minIndex {`
175			`// hashPrev[i & windowMask] has already been overwritten, so stop now.`
176			`break`
177			`}`
178			`if i = d.hashPrev[i&windowMask] - d.hashOffset; i < minIndex \|\| i < 0 {`
179			`break`
180			`}`
181			`}`
182			`return`
183			`}`
184
185			`func (d *compressor) writeStoredBlock(buf []byte) error {`
186			`if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {`
187			`return d.w.err`
188			`}`
189			`d.w.writeBytes(buf)`
190			`return d.w.err`
191			`}`
192
193			`func (d *compressor) initDeflate() {`
194			`d.hashHead = make([]int, hashSize)`
195			`d.hashPrev = make([]int, windowSize)`
196			`d.window = make([]byte, 2*windowSize)`
197			`d.hashOffset = 1`
198			`d.tokens = make([]token, 0, maxFlateBlockTokens+1)`
199			`d.length = minMatchLength - 1`
200			`d.offset = 0`
201			`d.byteAvailable = false`
202			`d.index = 0`
203			`d.hash = 0`
204			`d.chainHead = -1`
205			`}`
206
207			`func (d *compressor) deflate() {`
208			`if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {`
209			`return`
210			`}`
211
212			`d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)`
213			`if d.index < d.maxInsertIndex {`
214			`d.hash = int(d.window[d.index])<`
215			`}`
216
217			`Loop:`
218			`for {`
219			`if d.index > d.windowEnd {`
220			`panic("index > windowEnd")`
221			`}`
222			`lookahead := d.windowEnd - d.index`
223			`if lookahead < minMatchLength+maxMatchLength {`
224			`if !d.sync {`
225			`break Loop`
226			`}`
227			`if d.index > d.windowEnd {`
228			`panic("index > windowEnd")`
229			`}`
230			`if lookahead == 0 {`
231			`// Flush current output block if any.`
232			`if d.byteAvailable {`
233			`// There is still one pending token that needs to be flushed`
234			`d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1])))`
235			`d.byteAvailable = false`
236			`}`
237			`if len(d.tokens) > 0 {`
238			`if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {`
239			`return`
240			`}`
241			`d.tokens = d.tokens[:0]`
242			`}`
243			`break Loop`
244			`}`
245			`}`
246			`if d.index < d.maxInsertIndex {`
247			`// Update the hash`
248			`d.hash = (d.hash<`
249			`d.chainHead = d.hashHead[d.hash]`
250			`d.hashPrev[d.index&windowMask] = d.chainHead`
251			`d.hashHead[d.hash] = d.index + d.hashOffset`
252			`}`
253			`prevLength := d.length`
254			`prevOffset := d.offset`
255			`d.length = minMatchLength - 1`
256			`d.offset = 0`
257			`minIndex := d.index - windowSize`
258			`if minIndex < 0 {`
259			`minIndex = 0`
260			`}`
261
262			`if d.chainHead-d.hashOffset >= minIndex &&`
263			`(d.fastSkipHashing != skipNever && lookahead > minMatchLength-1 \|\|`
264			`d.fastSkipHashing == skipNever && lookahead > prevLength && prevLength < d.lazy) {`
265			`if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {`
266			`d.length = newLength`
267			`d.offset = newOffset`
268			`}`
269			`}`
270			`if d.fastSkipHashing != skipNever && d.length >= minMatchLength \|\|`
271			`d.fastSkipHashing == skipNever && prevLength >= minMatchLength && d.length <= prevLength {`
272			`// There was a match at the previous step, and the current match is`
273			`// not better. Output the previous match.`
274			`if d.fastSkipHashing != skipNever {`
275			`d.tokens = append(d.tokens, matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize)))`
276			`} else {`
277			`d.tokens = append(d.tokens, matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)))`
278			`}`
279			`// Insert in the hash table all strings up to the end of the match.`
280			`// index and index-1 are already inserted. If there is not enough`
281			`// lookahead, the last two strings are not inserted into the hash`
282			`// table.`
283			`if d.length <= d.fastSkipHashing {`
284			`var newIndex int`
285			`if d.fastSkipHashing != skipNever {`
286			`newIndex = d.index + d.length`
287			`} else {`
288			`newIndex = d.index + prevLength - 1`
289			`}`
290			`for d.index++; d.index < newIndex; d.index++ {`
291			`if d.index < d.maxInsertIndex {`
292			`d.hash = (d.hash<`
293			`// Get previous value with the same hash.`
294			`// Our chain should point to the previous value.`
295			`d.hashPrev[d.index&windowMask] = d.hashHead[d.hash]`
296			`// Set the head of the hash chain to us.`
297			`d.hashHead[d.hash] = d.index + d.hashOffset`
298			`}`
299			`}`
300			`if d.fastSkipHashing == skipNever {`
301			`d.byteAvailable = false`
302			`d.length = minMatchLength - 1`
303			`}`
304			`} else {`
305			`// For matches this long, we don't bother inserting each individual`
306			`// item into the table.`
307			`d.index += d.length`
308			`if d.index < d.maxInsertIndex {`
309			`d.hash = (int(d.window[d.index])<`
310			`}`
311			`}`
312			`if len(d.tokens) == maxFlateBlockTokens {`
313			`// The block includes the current character`
314			`if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {`
315			`return`
316			`}`
317			`d.tokens = d.tokens[:0]`
318			`}`
319			`} else {`
320			`if d.fastSkipHashing != skipNever \|\| d.byteAvailable {`
321			`i := d.index - 1`
322			`if d.fastSkipHashing != skipNever {`
323			`i = d.index`
324			`}`
325			`d.tokens = append(d.tokens, literalToken(uint32(d.window[i])))`
326			`if len(d.tokens) == maxFlateBlockTokens {`
327			`if d.err = d.writeBlock(d.tokens, i+1, false); d.err != nil {`
328			`return`
329			`}`
330			`d.tokens = d.tokens[:0]`
331			`}`
332			`}`
333			`d.index++`
334			`if d.fastSkipHashing == skipNever {`
335			`d.byteAvailable = true`
336			`}`
337			`}`
338			`}`
339			`}`
340
341			`func (d *compressor) fillStore(b []byte) int {`
342			`n := copy(d.window[d.windowEnd:], b)`
343			`d.windowEnd += n`
344			`return n`
345			`}`
346
347			`func (d *compressor) store() {`
348			`if d.windowEnd > 0 {`
349			`d.err = d.writeStoredBlock(d.window[:d.windowEnd])`
350			`}`
351			`d.windowEnd = 0`
352			`}`
353
354			`func (d *compressor) write(b []byte) (n int, err error) {`
355			`n = len(b)`
356			`b = b[d.fill(d, b):]`
357			`for len(b) > 0 {`
358			`d.step(d)`
359			`b = b[d.fill(d, b):]`
360			`}`
361			`return n, d.err`
362			`}`
363
364			`func (d *compressor) syncFlush() error {`
365			`d.sync = true`
366			`d.step(d)`
367			`if d.err == nil {`
368			`d.w.writeStoredHeader(0, false)`
369			`d.w.flush()`
370			`d.err = d.w.err`
371			`}`
372			`d.sync = false`
373			`return d.err`
374			`}`
375
376			`func (d *compressor) init(w io.Writer, level int) (err error) {`
377			`d.w = newHuffmanBitWriter(w)`
378
379			`switch {`
380			`case level == NoCompression:`
381			`d.window = make([]byte, maxStoreBlockSize)`
382			`d.fill = (*compressor).fillStore`
383			`d.step = (*compressor).store`
384			`case level == DefaultCompression:`
385			`level = 6`
386			`fallthrough`
387			`case 1 <= level && level <= 9:`
388			`d.compressionLevel = levels[level]`
389			`d.initDeflate()`
390			`d.fill = (*compressor).fillDeflate`
391			`d.step = (*compressor).deflate`
392			`default:`
393			`return WrongValueError{"level", 0, 9, int32(level)}`
394			`}`
395			`return nil`
396			`}`
397
398			`func (d *compressor) close() error {`
399			`d.sync = true`
400			`d.step(d)`
401			`if d.err != nil {`
402			`return d.err`
403			`}`
404			`if d.w.writeStoredHeader(0, true); d.w.err != nil {`
405			`return d.w.err`
406			`}`
407			`d.w.flush()`
408			`return d.w.err`
409			`}`
410
411			`// NewWriter returns a new Writer compressing`
412			`// data at the given level. Following zlib, levels`
413			`// range from 1 (BestSpeed) to 9 (BestCompression);`
414			`// higher levels typically run slower but compress more.`
415			`// Level 0 (NoCompression) does not attempt any`
416			`// compression; it only adds the necessary DEFLATE framing.`
417			`func NewWriter(w io.Writer, level int) *Writer {`
418			`const logWindowSize = logMaxOffsetSize`
419			`var dw Writer`
420			`dw.d.init(w, level)`
421			`return &dw`
422			`}`
423
424			`// NewWriterDict is like NewWriter but initializes the new`
425			`// Writer with a preset dictionary. The returned Writer behaves`
426			`// as if the dictionary had been written to it without producing`
427			`// any compressed output. The compressed data written to w`
428			`// can only be decompressed by a Reader initialized with the`
429			`// same dictionary.`
430			`func NewWriterDict(w io.Writer, level int, dict []byte) *Writer {`
431			`dw := &dictWriter{w, false}`
432			`zw := NewWriter(dw, level)`
433			`zw.Write(dict)`
434			`zw.Flush()`
435			`dw.enabled = true`
436			`return zw`
437			`}`
438
439			`type dictWriter struct {`
440			`w io.Writer`
441			`enabled bool`
442			`}`
443
444			`func (w *dictWriter) Write(b []byte) (n int, err error) {`
445			`if w.enabled {`
446			`return w.w.Write(b)`
447			`}`
448			`return len(b), nil`
449			`}`
450
451			`// A Writer takes data written to it and writes the compressed`
452			`// form of that data to an underlying writer (see NewWriter).`
453			`type Writer struct {`
454			`d compressor`
455			`}`
456
457			`// Write writes data to w, which will eventually write the`
458			`// compressed form of data to its underlying writer.`
459			`func (w *Writer) Write(data []byte) (n int, err error) {`
460			`return w.d.write(data)`
461			`}`
462
463			`// Flush flushes any pending compressed data to the underlying writer.`
464			`// It is useful mainly in compressed network protocols, to ensure that`
465			`// a remote reader has enough data to reconstruct a packet.`
466			`// Flush does not return until the data has been written.`
467			`// If the underlying writer returns an error, Flush returns that error.`
468			`//`
469			`// In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.`
470			`func (w *Writer) Flush() error {`
471			`// For more about flushing:`
472			`// http://www.bolet.org/~pornin/deflate-flush.html`
473			`return w.d.syncFlush()`
474			`}`
475
476			`// Close flushes and closes the writer.`
477			`func (w *Writer) Close() error {`
478			`return w.d.close()`
479			`}`