diff options
Diffstat (limited to 'libgo/go/compress/flate/deflate.go')
-rw-r--r-- | libgo/go/compress/flate/deflate.go | 478 |
1 files changed, 202 insertions, 276 deletions
diff --git a/libgo/go/compress/flate/deflate.go b/libgo/go/compress/flate/deflate.go index a02a5e8d94b..b1cee0b2f0f 100644 --- a/libgo/go/compress/flate/deflate.go +++ b/libgo/go/compress/flate/deflate.go @@ -11,16 +11,18 @@ import ( ) const ( - NoCompression = 0 - BestSpeed = 1 - fastCompression = 3 - BestCompression = 9 - DefaultCompression = -1 - logMaxOffsetSize = 15 // Standard DEFLATE - wideLogMaxOffsetSize = 22 // Wide 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 + 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. @@ -32,22 +34,6 @@ const ( hashShift = (hashBits + minMatchLength - 1) / minMatchLength ) -type syncPipeReader struct { - *io.PipeReader - closeChan chan bool -} - -func (sr *syncPipeReader) CloseWithError(err os.Error) os.Error { - retErr := sr.PipeReader.CloseWithError(err) - sr.closeChan <- true // finish writer close - return retErr -} - -type syncPipeWriter struct { - *io.PipeWriter - closeChan chan bool -} - type compressionLevel struct { good, lazy, nice, chain, fastSkipHashing int } @@ -68,105 +54,73 @@ var levels = []compressionLevel{ {32, 258, 258, 4096, math.MaxInt32}, } -func (sw *syncPipeWriter) Close() os.Error { - err := sw.PipeWriter.Close() - <-sw.closeChan // wait for reader close - return err -} - -func syncPipe() (*syncPipeReader, *syncPipeWriter) { - r, w := io.Pipe() - sr := &syncPipeReader{r, make(chan bool, 1)} - sw := &syncPipeWriter{w, sr.closeChan} - return sr, sw -} - type compressor struct { - level int - logWindowSize uint - w *huffmanBitWriter - r io.Reader - // (1 << logWindowSize) - 1. - windowMask int + compressionLevel - eof bool // has eof been reached on input? - sync bool // writer wants to flush - syncChan chan os.Error + w *huffmanBitWriter - // hashHead[hashValue] contains the largest inputIndex with the specified hash value - hashHead []int + // 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. - hashPrev []int - - // If we find a match of length >= niceMatch, then we don't bother searching - // any further. - niceMatch int - - // If we find a match of length >= goodMatch, we only do a half-hearted - // effort at doing lazy matching starting at the next character - goodMatch int - - // The maximum number of chains we look at when finding a match - maxChainLength int - - // The sliding window we use for matching - window []byte - - // The index just past the last valid character - windowEnd int - - // index in "window" at which current block starts - blockStart int -} - -func (d *compressor) flush() os.Error { - d.w.flush() - return d.w.err + chainHead int + hashHead []int + hashPrev []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[:ti] + tokens []token + ti int + + // deflate state + length int + offset int + hash int + maxInsertIndex int + err os.Error } -func (d *compressor) fillWindow(index int) (int, os.Error) { - if d.sync { - return index, nil - } - wSize := d.windowMask + 1 - if index >= wSize+wSize-(minMatchLength+maxMatchLength) { - // shift the window by wSize - copy(d.window, d.window[wSize:2*wSize]) - index -= wSize - d.windowEnd -= wSize - if d.blockStart >= wSize { - d.blockStart -= wSize +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 } for i, h := range d.hashHead { - v := h - wSize + v := h - windowSize if v < -1 { v = -1 } d.hashHead[i] = v } for i, h := range d.hashPrev { - v := -h - wSize + v := -h - windowSize if v < -1 { v = -1 } d.hashPrev[i] = v } } - count, err := d.r.Read(d.window[d.windowEnd:]) - d.windowEnd += count - if count == 0 && err == nil { - d.sync = true - } - if err == os.EOF { - d.eof = true - err = nil - } - return index, err + n := copy(d.window[d.windowEnd:], b) + d.windowEnd += n + return n } func (d *compressor) writeBlock(tokens []token, index int, eof bool) os.Error { @@ -194,21 +148,21 @@ func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead // We quit when we get a match that's at least nice long nice := len(win) - pos - if d.niceMatch < nice { - nice = d.niceMatch + 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.maxChainLength + tries := d.chain length = prevLength - if length >= d.goodMatch { + if length >= d.good { tries >>= 2 } w0 := win[pos] w1 := win[pos+1] wEnd := win[pos+length] - minIndex := pos - (d.windowMask + 1) + minIndex := pos - windowSize for i := prevHead; tries > 0; tries-- { if w0 == win[i] && w1 == win[i+1] && wEnd == win[i+length] { @@ -233,7 +187,7 @@ func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead // hashPrev[i & windowMask] has already been overwritten, so stop now. break } - if i = d.hashPrev[i&d.windowMask]; i < minIndex || i < 0 { + if i = d.hashPrev[i&windowMask]; i < minIndex || i < 0 { break } } @@ -248,234 +202,224 @@ func (d *compressor) writeStoredBlock(buf []byte) os.Error { return d.w.err } -func (d *compressor) storedDeflate() os.Error { - buf := make([]byte, maxStoreBlockSize) - for { - n, err := d.r.Read(buf) - if n == 0 && err == nil { - d.sync = true - } - if n > 0 || d.sync { - if err := d.writeStoredBlock(buf[0:n]); err != nil { - return err - } - if d.sync { - d.syncChan <- nil - d.sync = false - } - } - if err != nil { - if err == os.EOF { - break - } - return err - } - } - return nil -} - -func (d *compressor) doDeflate() (err os.Error) { - // init - d.windowMask = 1<<d.logWindowSize - 1 +func (d *compressor) initDeflate() { d.hashHead = make([]int, hashSize) - d.hashPrev = make([]int, 1<<d.logWindowSize) - d.window = make([]byte, 2<<d.logWindowSize) + d.hashPrev = make([]int, windowSize) + d.window = make([]byte, 2*windowSize) fillInts(d.hashHead, -1) - tokens := make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1) - l := levels[d.level] - d.goodMatch = l.good - d.niceMatch = l.nice - d.maxChainLength = l.chain - lazyMatch := l.lazy - length := minMatchLength - 1 - offset := 0 - byteAvailable := false - isFastDeflate := l.fastSkipHashing != 0 - index := 0 - // run - if index, err = d.fillWindow(index); err != nil { + d.tokens = make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1) + d.length = minMatchLength - 1 + d.offset = 0 + d.byteAvailable = false + d.index = 0 + d.ti = 0 + d.hash = 0 + d.chainHead = -1 +} + +func (d *compressor) deflate() { + if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync { return } - maxOffset := d.windowMask + 1 // (1 << logWindowSize); - // only need to change when you refill the window - windowEnd := d.windowEnd - maxInsertIndex := windowEnd - (minMatchLength - 1) - ti := 0 - - hash := int(0) - if index < maxInsertIndex { - hash = int(d.window[index])<<hashShift + int(d.window[index+1]) + + d.maxInsertIndex = d.windowEnd - (minMatchLength - 1) + if d.index < d.maxInsertIndex { + d.hash = int(d.window[d.index])<<hashShift + int(d.window[d.index+1]) } - chainHead := -1 + Loop: for { - if index > windowEnd { + if d.index > d.windowEnd { panic("index > windowEnd") } - lookahead := windowEnd - index + lookahead := d.windowEnd - d.index if lookahead < minMatchLength+maxMatchLength { - if index, err = d.fillWindow(index); err != nil { - return + if !d.sync { + break Loop } - windowEnd = d.windowEnd - if index > windowEnd { + if d.index > d.windowEnd { panic("index > windowEnd") } - maxInsertIndex = windowEnd - (minMatchLength - 1) - lookahead = windowEnd - index if lookahead == 0 { // Flush current output block if any. - if byteAvailable { + if d.byteAvailable { // There is still one pending token that needs to be flushed - tokens[ti] = literalToken(uint32(d.window[index-1]) & 0xFF) - ti++ - byteAvailable = false + d.tokens[d.ti] = literalToken(uint32(d.window[d.index-1])) + d.ti++ + d.byteAvailable = false } - if ti > 0 { - if err = d.writeBlock(tokens[0:ti], index, false); err != nil { + if d.ti > 0 { + if d.err = d.writeBlock(d.tokens[0:d.ti], d.index, false); d.err != nil { return } - ti = 0 - } - if d.sync { - d.w.writeStoredHeader(0, false) - d.w.flush() - d.syncChan <- d.w.err - d.sync = false - } - - // If this was only a sync (not at EOF) keep going. - if !d.eof { - continue + d.ti = 0 } break Loop } } - if index < maxInsertIndex { + if d.index < d.maxInsertIndex { // Update the hash - hash = (hash<<hashShift + int(d.window[index+2])) & hashMask - chainHead = d.hashHead[hash] - d.hashPrev[index&d.windowMask] = chainHead - d.hashHead[hash] = index + d.hash = (d.hash<<hashShift + int(d.window[d.index+2])) & hashMask + d.chainHead = d.hashHead[d.hash] + d.hashPrev[d.index&windowMask] = d.chainHead + d.hashHead[d.hash] = d.index } - prevLength := length - prevOffset := offset - length = minMatchLength - 1 - offset = 0 - minIndex := index - maxOffset + prevLength := d.length + prevOffset := d.offset + d.length = minMatchLength - 1 + d.offset = 0 + minIndex := d.index - windowSize if minIndex < 0 { minIndex = 0 } - if chainHead >= minIndex && - (isFastDeflate && lookahead > minMatchLength-1 || - !isFastDeflate && lookahead > prevLength && prevLength < lazyMatch) { - if newLength, newOffset, ok := d.findMatch(index, chainHead, minMatchLength-1, lookahead); ok { - length = newLength - offset = newOffset + if d.chainHead >= minIndex && + (d.fastSkipHashing != 0 && lookahead > minMatchLength-1 || + d.fastSkipHashing == 0 && lookahead > prevLength && prevLength < d.lazy) { + if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead, minMatchLength-1, lookahead); ok { + d.length = newLength + d.offset = newOffset } } - if isFastDeflate && length >= minMatchLength || - !isFastDeflate && prevLength >= minMatchLength && length <= prevLength { + if d.fastSkipHashing != 0 && d.length >= minMatchLength || + d.fastSkipHashing == 0 && 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 isFastDeflate { - tokens[ti] = matchToken(uint32(length-minMatchLength), uint32(offset-minOffsetSize)) + if d.fastSkipHashing != 0 { + d.tokens[d.ti] = matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize)) } else { - tokens[ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)) + d.tokens[d.ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)) } - ti++ + d.ti++ // 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 length <= l.fastSkipHashing { + if d.length <= d.fastSkipHashing { var newIndex int - if isFastDeflate { - newIndex = index + length + if d.fastSkipHashing != 0 { + newIndex = d.index + d.length } else { newIndex = prevLength - 1 } - for index++; index < newIndex; index++ { - if index < maxInsertIndex { - hash = (hash<<hashShift + int(d.window[index+2])) & hashMask + for d.index++; d.index < newIndex; d.index++ { + if d.index < d.maxInsertIndex { + d.hash = (d.hash<<hashShift + int(d.window[d.index+2])) & hashMask // Get previous value with the same hash. // Our chain should point to the previous value. - d.hashPrev[index&d.windowMask] = d.hashHead[hash] + d.hashPrev[d.index&windowMask] = d.hashHead[d.hash] // Set the head of the hash chain to us. - d.hashHead[hash] = index + d.hashHead[d.hash] = d.index } } - if !isFastDeflate { - byteAvailable = false - length = minMatchLength - 1 + if d.fastSkipHashing == 0 { + d.byteAvailable = false + d.length = minMatchLength - 1 } } else { // For matches this long, we don't bother inserting each individual // item into the table. - index += length - hash = (int(d.window[index])<<hashShift + int(d.window[index+1])) + d.index += d.length + d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1])) } - if ti == maxFlateBlockTokens { + if d.ti == maxFlateBlockTokens { // The block includes the current character - if err = d.writeBlock(tokens, index, false); err != nil { + if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil { return } - ti = 0 + d.ti = 0 } } else { - if isFastDeflate || byteAvailable { - i := index - 1 - if isFastDeflate { - i = index + if d.fastSkipHashing != 0 || d.byteAvailable { + i := d.index - 1 + if d.fastSkipHashing != 0 { + i = d.index } - tokens[ti] = literalToken(uint32(d.window[i]) & 0xFF) - ti++ - if ti == maxFlateBlockTokens { - if err = d.writeBlock(tokens, i+1, false); err != nil { + d.tokens[d.ti] = literalToken(uint32(d.window[i])) + d.ti++ + if d.ti == maxFlateBlockTokens { + if d.err = d.writeBlock(d.tokens, i+1, false); d.err != nil { return } - ti = 0 + d.ti = 0 } } - index++ - if !isFastDeflate { - byteAvailable = true + d.index++ + if d.fastSkipHashing == 0 { + d.byteAvailable = true } } } - return } -func (d *compressor) compress(r io.Reader, w io.Writer, level int, logWindowSize uint) (err os.Error) { - d.r = r +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 os.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() os.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 os.Error) { d.w = newHuffmanBitWriter(w) - d.level = level - d.logWindowSize = logWindowSize switch { case level == NoCompression: - err = d.storedDeflate() + d.window = make([]byte, maxStoreBlockSize) + d.fill = (*compressor).fillStore + d.step = (*compressor).store case level == DefaultCompression: - d.level = 6 + level = 6 fallthrough case 1 <= level && level <= 9: - err = d.doDeflate() + d.compressionLevel = levels[level] + d.initDeflate() + d.fill = (*compressor).fillDeflate + d.step = (*compressor).deflate default: return WrongValueError{"level", 0, 9, int32(level)} } + return nil +} - if d.sync { - d.syncChan <- err - d.sync = false - } - if err != nil { - return err +func (d *compressor) close() os.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 } - return d.flush() + d.w.flush() + return d.w.err } // NewWriter returns a new Writer compressing @@ -486,14 +430,9 @@ func (d *compressor) compress(r io.Reader, w io.Writer, level int, logWindowSize // compression; it only adds the necessary DEFLATE framing. func NewWriter(w io.Writer, level int) *Writer { const logWindowSize = logMaxOffsetSize - var d compressor - d.syncChan = make(chan os.Error, 1) - pr, pw := syncPipe() - go func() { - err := d.compress(pr, w, level, logWindowSize) - pr.CloseWithError(err) - }() - return &Writer{pw, &d} + var dw Writer + dw.d.init(w, level) + return &dw } // NewWriterDict is like NewWriter but initializes the new @@ -526,18 +465,13 @@ func (w *dictWriter) Write(b []byte) (n int, err os.Error) { // A Writer takes data written to it and writes the compressed // form of that data to an underlying writer (see NewWriter). type Writer struct { - w *syncPipeWriter - d *compressor + 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 os.Error) { - if len(data) == 0 { - // no point, and nil interferes with sync - return - } - return w.w.Write(data) + return w.d.write(data) } // Flush flushes any pending compressed data to the underlying writer. @@ -550,18 +484,10 @@ func (w *Writer) Write(data []byte) (n int, err os.Error) { func (w *Writer) Flush() os.Error { // For more about flushing: // http://www.bolet.org/~pornin/deflate-flush.html - if w.d.sync { - panic("compress/flate: double Flush") - } - _, err := w.w.Write(nil) - err1 := <-w.d.syncChan - if err == nil { - err = err1 - } - return err + return w.d.syncFlush() } // Close flushes and closes the writer. func (w *Writer) Close() os.Error { - return w.w.Close() + return w.d.close() } |