// 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";
"os";
)
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 deflater looks for
maxMatchLength = 258; // The longest match for the deflater
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 = 15;
hashSize = 1 << hashBits;
hashMask = (1 << hashBits) - 1;
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;
}
var levels = []compressionLevel{
compressionLevel{}, // 0
// For levels 1-3 we don't bother trying with lazy matches
compressionLevel{3, 0, 8, 4, 4},
compressionLevel{3, 0, 16, 8, 5},
compressionLevel{3, 0, 32, 32, 6},
// Levels 4-9 use increasingly more lazy matching
// and increasingly stringent conditions for "good enough".
compressionLevel{4, 4, 16, 16, math.MaxInt32},
compressionLevel{8, 16, 32, 32, math.MaxInt32},
compressionLevel{8, 16, 128, 128, math.MaxInt32},
compressionLevel{8, 32, 128, 256, math.MaxInt32},
compressionLevel{32, 128, 258, 1024, math.MaxInt32},
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 deflater struct {
level int;
logWindowSize uint;
w *huffmanBitWriter;
r io.Reader;
// (1 << logWindowSize) - 1.
windowMask int;
// hashHead[hashValue] contains the largest inputIndex with the specified hash value
hashHead []int;
// 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 *deflater) flush() os.Error {
d.w.flush();
return d.w.err;
}
func (d *deflater) fillWindow(index int) (int, os.Error) {
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
} else {
d.blockStart = math.MaxInt32
}
for i, h := range d.hashHead {
d.hashHead[i] = max(h-wSize, -1)
}
for i, h := range d.hashPrev {
d.hashPrev[i] = max(h-wSize, -1)
}
}
var count int;
var err os.Error;
count, err = io.ReadAtLeast(d.r, d.window[d.windowEnd:], 1);
d.windowEnd += count;
if err == os.EOF {
return index, nil
}
return index, err;
}
func (d *deflater) writeBlock(tokens []token, index int, eof bool) os.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 *deflater) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
win := d.window[0 : pos+min(maxMatchLength, lookahead)];
// We quit when we get a match that's at least nice long
nice := min(d.niceMatch, len(win)-pos);
// If we've got a match that's good enough, only look in 1/4 the chain.
tries := d.maxChainLength;
length = prevLength;
if length >= d.goodMatch {
tries >>= 2
}
w0 := win[pos];
w1 := win[pos+1];
wEnd := win[pos+length];
minIndex := pos - (d.windowMask + 1);
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&d.windowMask]; i < minIndex || i < 0 {
break
}
}
return;
}
func (d *deflater) writeStoredBlock(buf []byte) os.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 *deflater) storedDeflate() os.Error {
buf := make([]byte, maxStoreBlockSize);
for {
n, err := d.r.Read(buf);
if n > 0 {
if err := d.writeStoredBlock(buf[0:n]); err != nil {
return err
}
}
if err != nil {
if err == os.EOF {
break
}
return err;
}
}
return nil;
}
func (d *deflater) doDeflate() (err os.Error) {
// init
d.windowMask = 1<<d.logWindowSize - 1;
d.hashHead = make([]int, hashSize);
d.hashPrev = make([]int, 1<<d.logWindowSize);
d.window = make([]byte, 2<<d.logWindowSize);
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 {
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])
}
chainHead := -1;
for {
if index > windowEnd {
panic("index > windowEnd")
}
lookahead := windowEnd - index;
if lookahead < minMatchLength+maxMatchLength {
if index, err = d.fillWindow(index); err != nil {
return
}
windowEnd = d.windowEnd;
if index > windowEnd {
panic("index > windowEnd")
}
maxInsertIndex = windowEnd - (minMatchLength - 1);
lookahead = windowEnd - index;
if lookahead == 0 {
break
}
}
if index < 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;
}
prevLength := length;
prevOffset := offset;
minIndex := max(index-maxOffset, 0);
length = minMatchLength - 1;
offset = 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 isFastDeflate && length >= minMatchLength ||
!isFastDeflate && prevLength >= minMatchLength && 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))
} else {
tokens[ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))
}
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 {
var newIndex int;
if isFastDeflate {
newIndex = index + length
} else {
newIndex = prevLength - 1
}
for index++; index < newIndex; index++ {
if index < maxInsertIndex {
hash = (hash<<hashShift + int(d.window[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];
// Set the head of the hash chain to us.
d.hashHead[hash] = index;
}
}
if !isFastDeflate {
byteAvailable = false;
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]));
}
if ti == maxFlateBlockTokens {
// The block includes the current character
if err = d.writeBlock(tokens, index, false); err != nil {
return
}
ti = 0;
}
} else {
if isFastDeflate || byteAvailable {
i := index - 1;
if isFastDeflate {
i = index
}
tokens[ti] = literalToken(uint32(d.window[i]) & 0xFF);
ti++;
if ti == maxFlateBlockTokens {
if err = d.writeBlock(tokens, i+1, false); err != nil {
return
}
ti = 0;
}
}
index++;
if !isFastDeflate {
byteAvailable = true
}
}
}
if byteAvailable {
// There is still one pending token that needs to be flushed
tokens[ti] = literalToken(uint32(d.window[index-1]) & 0xFF);
ti++;
}
if ti > 0 {
if err = d.writeBlock(tokens[0:ti], index, false); err != nil {
return
}
}
return;
}
func (d *deflater) deflater(r io.Reader, w io.Writer, level int, logWindowSize uint) (err os.Error) {
d.r = r;
d.w = newHuffmanBitWriter(w);
d.level = level;
d.logWindowSize = logWindowSize;
switch {
case level == NoCompression:
err = d.storedDeflate()
case level == DefaultCompression:
d.level = 6;
fallthrough;
case 1 <= level && level <= 9:
err = d.doDeflate()
default:
return WrongValueError{"level", 0, 9, int32(level)}
}
if err != nil {
return err
}
if d.w.writeStoredHeader(0, true); d.w.err != nil {
return d.w.err
}
return d.flush();
}
func newDeflater(w io.Writer, level int, logWindowSize uint) io.WriteCloser {
var d deflater;
pr, pw := syncPipe();
go func() {
err := d.deflater(pr, w, level, logWindowSize);
pr.CloseWithError(err);
}();
return pw;
}
func NewDeflater(w io.Writer, level int) io.WriteCloser {
return newDeflater(w, level, logMaxOffsetSize)
}
|
