diff options
author | Ian Lance Taylor <ian@gcc.gnu.org> | 2012-02-01 19:26:59 +0000 |
---|---|---|
committer | Ian Lance Taylor <ian@gcc.gnu.org> | 2012-02-01 19:26:59 +0000 |
commit | 9af4cb9545ce481b8d9d4a13acfe26512032e21b (patch) | |
tree | 7e7e6083ebe59999943a211a17f8ef6f07f17c2f /libgo/go/compress/flate/deflate.go | |
parent | 6b6cd722f329a168f98d1f421834cf40bb33a77d (diff) | |
download | gcc-9af4cb9545ce481b8d9d4a13acfe26512032e21b.zip gcc-9af4cb9545ce481b8d9d4a13acfe26512032e21b.tar.gz gcc-9af4cb9545ce481b8d9d4a13acfe26512032e21b.tar.bz2 |
libgo: Update to weekly.2012-01-27.
From-SVN: r183810
Diffstat (limited to 'libgo/go/compress/flate/deflate.go')
-rw-r--r-- | libgo/go/compress/flate/deflate.go | 105 |
1 files changed, 45 insertions, 60 deletions
diff --git a/libgo/go/compress/flate/deflate.go b/libgo/go/compress/flate/deflate.go index 4f74445..1e72589 100644 --- a/libgo/go/compress/flate/deflate.go +++ b/libgo/go/compress/flate/deflate.go @@ -27,10 +27,12 @@ const ( // stop things from getting too large. maxFlateBlockTokens = 1 << 14 maxStoreBlockSize = 65535 - hashBits = 15 + hashBits = 17 hashSize = 1 << hashBits hashMask = (1 << hashBits) - 1 hashShift = (hashBits + minMatchLength - 1) / minMatchLength + + skipNever = math.MaxInt32 ) type compressionLevel struct { @@ -45,12 +47,12 @@ var levels = []compressionLevel{ {3, 0, 32, 32, 6}, // Levels 4-9 use increasingly more lazy matching // and increasingly stringent conditions for "good enough". - {4, 4, 16, 16, math.MaxInt32}, - {8, 16, 32, 32, math.MaxInt32}, - {8, 16, 128, 128, math.MaxInt32}, - {8, 32, 128, 256, math.MaxInt32}, - {32, 128, 258, 1024, math.MaxInt32}, - {32, 258, 258, 4096, math.MaxInt32}, + {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 { @@ -68,9 +70,10 @@ type compressor struct { // 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 + chainHead int + hashHead []int + hashPrev []int + hashOffset int // input window: unprocessed data is window[index:windowEnd] index int @@ -79,9 +82,8 @@ type compressor struct { blockStart int // window index where current tokens start byteAvailable bool // if true, still need to process window[index-1]. - // queued output tokens: tokens[:ti] + // queued output tokens tokens []token - ti int // deflate state length int @@ -100,22 +102,9 @@ func (d *compressor) fillDeflate(b []byte) int { if d.blockStart >= windowSize { d.blockStart -= windowSize } else { - d.blockStart = math.MaxInt32 - } - for i, h := range d.hashHead { - v := h - windowSize - if v < -1 { - v = -1 - } - d.hashHead[i] = v - } - for i, h := range d.hashPrev { - v := -h - windowSize - if v < -1 { - v = -1 - } - d.hashPrev[i] = v + d.blockStart = skipNever } + d.hashOffset += windowSize } n := copy(d.window[d.windowEnd:], b) d.windowEnd += n @@ -186,7 +175,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&windowMask]; i < minIndex || i < 0 { + if i = d.hashPrev[i&windowMask] - d.hashOffset; i < minIndex || i < 0 { break } } @@ -205,13 +194,12 @@ func (d *compressor) initDeflate() { d.hashHead = make([]int, hashSize) d.hashPrev = make([]int, windowSize) d.window = make([]byte, 2*windowSize) - fillInts(d.hashHead, -1) - d.tokens = make([]token, maxFlateBlockTokens, maxFlateBlockTokens+1) + d.hashOffset = 1 + d.tokens = make([]token, 0, maxFlateBlockTokens+1) d.length = minMatchLength - 1 d.offset = 0 d.byteAvailable = false d.index = 0 - d.ti = 0 d.hash = 0 d.chainHead = -1 } @@ -243,15 +231,14 @@ Loop: // Flush current output block if any. if d.byteAvailable { // There is still one pending token that needs to be flushed - d.tokens[d.ti] = literalToken(uint32(d.window[d.index-1])) - d.ti++ + d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index-1]))) d.byteAvailable = false } - if d.ti > 0 { - if d.err = d.writeBlock(d.tokens[0:d.ti], d.index, false); d.err != nil { + if len(d.tokens) > 0 { + if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil { return } - d.ti = 0 + d.tokens = d.tokens[:0] } break Loop } @@ -261,7 +248,7 @@ Loop: 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 + d.hashHead[d.hash] = d.index + d.hashOffset } prevLength := d.length prevOffset := d.offset @@ -272,34 +259,33 @@ Loop: minIndex = 0 } - 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 { + 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 != 0 && d.length >= minMatchLength || - d.fastSkipHashing == 0 && prevLength >= minMatchLength && d.length <= prevLength { + 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 != 0 { - d.tokens[d.ti] = matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize)) + if d.fastSkipHashing != skipNever { + d.tokens = append(d.tokens, matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize))) } else { - d.tokens[d.ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize)) + d.tokens = append(d.tokens, matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))) } - 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 d.length <= d.fastSkipHashing { var newIndex int - if d.fastSkipHashing != 0 { + if d.fastSkipHashing != skipNever { newIndex = d.index + d.length } else { - newIndex = prevLength - 1 + newIndex = d.index + prevLength - 1 } for d.index++; d.index < newIndex; d.index++ { if d.index < d.maxInsertIndex { @@ -308,10 +294,10 @@ Loop: // 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.hashHead[d.hash] = d.index + d.hashOffset } } - if d.fastSkipHashing == 0 { + if d.fastSkipHashing == skipNever { d.byteAvailable = false d.length = minMatchLength - 1 } @@ -323,30 +309,29 @@ Loop: d.hash = (int(d.window[d.index])<<hashShift + int(d.window[d.index+1])) } } - if d.ti == maxFlateBlockTokens { + 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.ti = 0 + d.tokens = d.tokens[:0] } } else { - if d.fastSkipHashing != 0 || d.byteAvailable { + if d.fastSkipHashing != skipNever || d.byteAvailable { i := d.index - 1 - if d.fastSkipHashing != 0 { + if d.fastSkipHashing != skipNever { i = d.index } - d.tokens[d.ti] = literalToken(uint32(d.window[i])) - d.ti++ - if d.ti == maxFlateBlockTokens { + 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.ti = 0 + d.tokens = d.tokens[:0] } } d.index++ - if d.fastSkipHashing == 0 { + if d.fastSkipHashing == skipNever { d.byteAvailable = true } } |