summaryrefslogtreecommitdiff
path: root/vendor/github.com/klauspost/compress/flate
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/klauspost/compress/flate')
-rw-r--r--vendor/github.com/klauspost/compress/flate/copy.go32
-rw-r--r--vendor/github.com/klauspost/compress/flate/deflate.go551
-rw-r--r--vendor/github.com/klauspost/compress/flate/huffman_bit_writer.go138
-rw-r--r--vendor/github.com/klauspost/compress/flate/huffman_code.go5
-rw-r--r--vendor/github.com/klauspost/compress/flate/snappy.go4
-rw-r--r--vendor/github.com/klauspost/compress/flate/token.go27
6 files changed, 384 insertions, 373 deletions
diff --git a/vendor/github.com/klauspost/compress/flate/copy.go b/vendor/github.com/klauspost/compress/flate/copy.go
deleted file mode 100644
index a3200a8f4..000000000
--- a/vendor/github.com/klauspost/compress/flate/copy.go
+++ /dev/null
@@ -1,32 +0,0 @@
-// Copyright 2012 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
-
-// forwardCopy is like the built-in copy function except that it always goes
-// forward from the start, even if the dst and src overlap.
-// It is equivalent to:
-// for i := 0; i < n; i++ {
-// mem[dst+i] = mem[src+i]
-// }
-func forwardCopy(mem []byte, dst, src, n int) {
- if dst <= src {
- copy(mem[dst:dst+n], mem[src:src+n])
- return
- }
- for {
- if dst >= src+n {
- copy(mem[dst:dst+n], mem[src:src+n])
- return
- }
- // There is some forward overlap. The destination
- // will be filled with a repeated pattern of mem[src:src+k].
- // We copy one instance of the pattern here, then repeat.
- // Each time around this loop k will double.
- k := dst - src
- copy(mem[dst:dst+k], mem[src:src+k])
- n -= k
- dst += k
- }
-}
diff --git a/vendor/github.com/klauspost/compress/flate/deflate.go b/vendor/github.com/klauspost/compress/flate/deflate.go
index 9e6e7ff0c..628795120 100644
--- a/vendor/github.com/klauspost/compress/flate/deflate.go
+++ b/vendor/github.com/klauspost/compress/flate/deflate.go
@@ -77,16 +77,14 @@ var levels = []compressionLevel{
{32, 258, 258, 4096, skipNever, 9},
}
-type compressor struct {
- compressionLevel
-
- w *huffmanBitWriter
- bulkHasher func([]byte, []uint32)
-
- // compression algorithm
- fill func(*compressor, []byte) int // copy data to window
- step func(*compressor) // process window
- sync bool // requesting flush
+// advancedState contains state for the advanced levels, with bigger hash tables, etc.
+type advancedState struct {
+ // deflate state
+ length int
+ offset int
+ hash uint32
+ maxInsertIndex int
+ ii uint16 // position of last match, intended to overflow to reset.
// Input hash chains
// hashHead[hashValue] contains the largest inputIndex with the specified hash value
@@ -99,57 +97,64 @@ type compressor struct {
hashOffset int
// input window: unprocessed data is window[index:windowEnd]
- index int
+ index int
+ bulkHasher func([]byte, []uint32)
+ hashMatch [maxMatchLength + minMatchLength]uint32
+}
+
+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
+
window []byte
windowEnd int
blockStart int // window index where current tokens start
byteAvailable bool // if true, still need to process window[index-1].
+ err error
// queued output tokens
tokens tokens
-
- // deflate state
- length int
- offset int
- hash uint32
- maxInsertIndex int
- err error
- ii uint16 // position of last match, intended to overflow to reset.
-
- snap snappyEnc
- hashMatch [maxMatchLength + minMatchLength]uint32
+ snap fastEnc
+ state *advancedState
}
func (d *compressor) fillDeflate(b []byte) int {
- if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
+ s := d.state
+ if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
// shift the window by windowSize
copy(d.window[:], d.window[windowSize:2*windowSize])
- d.index -= windowSize
+ s.index -= windowSize
d.windowEnd -= windowSize
if d.blockStart >= windowSize {
d.blockStart -= windowSize
} else {
d.blockStart = math.MaxInt32
}
- d.hashOffset += windowSize
- if d.hashOffset > maxHashOffset {
- delta := d.hashOffset - 1
- d.hashOffset -= delta
- d.chainHead -= delta
+ s.hashOffset += windowSize
+ if s.hashOffset > maxHashOffset {
+ delta := s.hashOffset - 1
+ s.hashOffset -= delta
+ s.chainHead -= delta
// Iterate over slices instead of arrays to avoid copying
// the entire table onto the stack (Issue #18625).
- for i, v := range d.hashPrev[:] {
+ for i, v := range s.hashPrev[:] {
if int(v) > delta {
- d.hashPrev[i] = uint32(int(v) - delta)
+ s.hashPrev[i] = uint32(int(v) - delta)
} else {
- d.hashPrev[i] = 0
+ s.hashPrev[i] = 0
}
}
- for i, v := range d.hashHead[:] {
+ for i, v := range s.hashHead[:] {
if int(v) > delta {
- d.hashHead[i] = uint32(int(v) - delta)
+ s.hashHead[i] = uint32(int(v) - delta)
} else {
- d.hashHead[i] = 0
+ s.hashHead[i] = 0
}
}
}
@@ -207,6 +212,7 @@ func (d *compressor) fillWindow(b []byte) {
case 0, 1, 2:
return
}
+ s := d.state
// If we are given too much, cut it.
if len(b) > windowSize {
b = b[len(b)-windowSize:]
@@ -229,28 +235,28 @@ func (d *compressor) fillWindow(b []byte) {
continue
}
- dst := d.hashMatch[:dstSize]
- d.bulkHasher(tocheck, dst)
+ dst := s.hashMatch[:dstSize]
+ s.bulkHasher(tocheck, dst)
var newH uint32
for i, val := range dst {
di := i + startindex
newH = val & hashMask
// Get previous value with the same hash.
// Our chain should point to the previous value.
- d.hashPrev[di&windowMask] = d.hashHead[newH]
+ s.hashPrev[di&windowMask] = s.hashHead[newH]
// Set the head of the hash chain to us.
- d.hashHead[newH] = uint32(di + d.hashOffset)
+ s.hashHead[newH] = uint32(di + s.hashOffset)
}
- d.hash = newH
+ s.hash = newH
}
// Update window information.
d.windowEnd += n
- d.index = n
+ s.index = n
}
// Try to find a match starting at index whose length is greater than prevSize.
// We only look at chainCount possibilities before giving up.
-// pos = d.index, prevHead = d.chainHead-d.hashOffset, prevLength=minMatchLength-1, lookahead
+// pos = s.index, prevHead = s.chainHead-s.hashOffset, prevLength=minMatchLength-1, lookahead
func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
minMatchLook := maxMatchLength
if lookahead < minMatchLook {
@@ -295,7 +301,7 @@ func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead
// hashPrev[i & windowMask] has already been overwritten, so stop now.
break
}
- i = int(d.hashPrev[i&windowMask]) - d.hashOffset
+ i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
if i < minIndex || i < 0 {
break
}
@@ -305,7 +311,7 @@ func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead
// Try to find a match starting at index whose length is greater than prevSize.
// We only look at chainCount possibilities before giving up.
-// pos = d.index, prevHead = d.chainHead-d.hashOffset, prevLength=minMatchLength-1, lookahead
+// pos = s.index, prevHead = s.chainHead-s.hashOffset, prevLength=minMatchLength-1, lookahead
func (d *compressor) findMatchSSE(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
minMatchLook := maxMatchLength
if lookahead < minMatchLook {
@@ -350,7 +356,7 @@ func (d *compressor) findMatchSSE(pos int, prevHead int, prevLength int, lookahe
// hashPrev[i & windowMask] has already been overwritten, so stop now.
break
}
- i = int(d.hashPrev[i&windowMask]) - d.hashOffset
+ i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
if i < minIndex || i < 0 {
break
}
@@ -406,52 +412,57 @@ func matchLen(a, b []byte, max int) int {
func (d *compressor) initDeflate() {
d.window = make([]byte, 2*windowSize)
- d.hashOffset = 1
- d.length = minMatchLength - 1
- d.offset = 0
d.byteAvailable = false
- d.index = 0
- d.hash = 0
- d.chainHead = -1
- d.bulkHasher = bulkHash4
+ d.err = nil
+ if d.state == nil {
+ return
+ }
+ s := d.state
+ s.index = 0
+ s.hashOffset = 1
+ s.length = minMatchLength - 1
+ s.offset = 0
+ s.hash = 0
+ s.chainHead = -1
+ s.bulkHasher = bulkHash4
if useSSE42 {
- d.bulkHasher = crc32sseAll
+ s.bulkHasher = crc32sseAll
}
}
// Assumes that d.fastSkipHashing != skipNever,
// otherwise use deflateLazy
func (d *compressor) deflate() {
-
+ s := d.state
// Sanity enables additional runtime tests.
// It's intended to be used during development
// to supplement the currently ad-hoc unit tests.
const sanity = false
- if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
+ if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
return
}
- d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
- if d.index < d.maxInsertIndex {
- d.hash = hash4(d.window[d.index : d.index+minMatchLength])
+ s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
+ if s.index < s.maxInsertIndex {
+ s.hash = hash4(d.window[s.index : s.index+minMatchLength])
}
for {
- if sanity && d.index > d.windowEnd {
+ if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
- lookahead := d.windowEnd - d.index
+ lookahead := d.windowEnd - s.index
if lookahead < minMatchLength+maxMatchLength {
if !d.sync {
return
}
- if sanity && d.index > d.windowEnd {
+ if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
if lookahead == 0 {
if d.tokens.n > 0 {
- if d.err = d.writeBlockSkip(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlockSkip(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
@@ -459,55 +470,55 @@ func (d *compressor) deflate() {
return
}
}
- if d.index < d.maxInsertIndex {
+ if s.index < s.maxInsertIndex {
// Update the hash
- d.hash = hash4(d.window[d.index : d.index+minMatchLength])
- ch := d.hashHead[d.hash&hashMask]
- d.chainHead = int(ch)
- d.hashPrev[d.index&windowMask] = ch
- d.hashHead[d.hash&hashMask] = uint32(d.index + d.hashOffset)
+ s.hash = hash4(d.window[s.index : s.index+minMatchLength])
+ ch := s.hashHead[s.hash&hashMask]
+ s.chainHead = int(ch)
+ s.hashPrev[s.index&windowMask] = ch
+ s.hashHead[s.hash&hashMask] = uint32(s.index + s.hashOffset)
}
- d.length = minMatchLength - 1
- d.offset = 0
- minIndex := d.index - windowSize
+ s.length = minMatchLength - 1
+ s.offset = 0
+ minIndex := s.index - windowSize
if minIndex < 0 {
minIndex = 0
}
- if d.chainHead-d.hashOffset >= minIndex && lookahead > minMatchLength-1 {
- if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
- d.length = newLength
- d.offset = newOffset
+ if s.chainHead-s.hashOffset >= minIndex && lookahead > minMatchLength-1 {
+ if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, minMatchLength-1, lookahead); ok {
+ s.length = newLength
+ s.offset = newOffset
}
}
- if d.length >= minMatchLength {
- d.ii = 0
+ if s.length >= minMatchLength {
+ s.ii = 0
// There was a match at the previous step, and the current match is
// not better. Output the previous match.
- // "d.length-3" should NOT be "d.length-minMatchLength", since the format always assume 3
- d.tokens.tokens[d.tokens.n] = matchToken(uint32(d.length-3), uint32(d.offset-minOffsetSize))
+ // "s.length-3" should NOT be "s.length-minMatchLength", since the format always assume 3
+ d.tokens.tokens[d.tokens.n] = matchToken(uint32(s.length-3), uint32(s.offset-minOffsetSize))
d.tokens.n++
// 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 {
+ if s.length <= d.fastSkipHashing {
var newIndex int
- newIndex = d.index + d.length
+ newIndex = s.index + s.length
// Calculate missing hashes
end := newIndex
- if end > d.maxInsertIndex {
- end = d.maxInsertIndex
+ if end > s.maxInsertIndex {
+ end = s.maxInsertIndex
}
end += minMatchLength - 1
- startindex := d.index + 1
- if startindex > d.maxInsertIndex {
- startindex = d.maxInsertIndex
+ startindex := s.index + 1
+ if startindex > s.maxInsertIndex {
+ startindex = s.maxInsertIndex
}
tocheck := d.window[startindex:end]
dstSize := len(tocheck) - minMatchLength + 1
if dstSize > 0 {
- dst := d.hashMatch[:dstSize]
+ dst := s.hashMatch[:dstSize]
bulkHash4(tocheck, dst)
var newH uint32
for i, val := range dst {
@@ -515,35 +526,35 @@ func (d *compressor) deflate() {
newH = val & hashMask
// Get previous value with the same hash.
// Our chain should point to the previous value.
- d.hashPrev[di&windowMask] = d.hashHead[newH]
+ s.hashPrev[di&windowMask] = s.hashHead[newH]
// Set the head of the hash chain to us.
- d.hashHead[newH] = uint32(di + d.hashOffset)
+ s.hashHead[newH] = uint32(di + s.hashOffset)
}
- d.hash = newH
+ s.hash = newH
}
- d.index = newIndex
+ s.index = newIndex
} 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 = hash4(d.window[d.index : d.index+minMatchLength])
+ s.index += s.length
+ if s.index < s.maxInsertIndex {
+ s.hash = hash4(d.window[s.index : s.index+minMatchLength])
}
}
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
- if d.err = d.writeBlockSkip(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlockSkip(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
} else {
- d.ii++
- end := d.index + int(d.ii>>uint(d.fastSkipHashing)) + 1
+ s.ii++
+ end := s.index + int(s.ii>>uint(d.fastSkipHashing)) + 1
if end > d.windowEnd {
end = d.windowEnd
}
- for i := d.index; i < end; i++ {
+ for i := s.index; i < end; i++ {
d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[i]))
d.tokens.n++
if d.tokens.n == maxFlateBlockTokens {
@@ -553,7 +564,7 @@ func (d *compressor) deflate() {
d.tokens.n = 0
}
}
- d.index = end
+ s.index = end
}
}
}
@@ -561,42 +572,43 @@ func (d *compressor) deflate() {
// deflateLazy is the same as deflate, but with d.fastSkipHashing == skipNever,
// meaning it always has lazy matching on.
func (d *compressor) deflateLazy() {
+ s := d.state
// Sanity enables additional runtime tests.
// It's intended to be used during development
// to supplement the currently ad-hoc unit tests.
const sanity = false
- if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
+ if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
return
}
- d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
- if d.index < d.maxInsertIndex {
- d.hash = hash4(d.window[d.index : d.index+minMatchLength])
+ s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
+ if s.index < s.maxInsertIndex {
+ s.hash = hash4(d.window[s.index : s.index+minMatchLength])
}
for {
- if sanity && d.index > d.windowEnd {
+ if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
- lookahead := d.windowEnd - d.index
+ lookahead := d.windowEnd - s.index
if lookahead < minMatchLength+maxMatchLength {
if !d.sync {
return
}
- if sanity && d.index > d.windowEnd {
+ if sanity && s.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.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
d.byteAvailable = false
}
if d.tokens.n > 0 {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
@@ -604,30 +616,30 @@ func (d *compressor) deflateLazy() {
return
}
}
- if d.index < d.maxInsertIndex {
+ if s.index < s.maxInsertIndex {
// Update the hash
- d.hash = hash4(d.window[d.index : d.index+minMatchLength])
- ch := d.hashHead[d.hash&hashMask]
- d.chainHead = int(ch)
- d.hashPrev[d.index&windowMask] = ch
- d.hashHead[d.hash&hashMask] = uint32(d.index + d.hashOffset)
+ s.hash = hash4(d.window[s.index : s.index+minMatchLength])
+ ch := s.hashHead[s.hash&hashMask]
+ s.chainHead = int(ch)
+ s.hashPrev[s.index&windowMask] = ch
+ s.hashHead[s.hash&hashMask] = uint32(s.index + s.hashOffset)
}
- prevLength := d.length
- prevOffset := d.offset
- d.length = minMatchLength - 1
- d.offset = 0
- minIndex := d.index - windowSize
+ prevLength := s.length
+ prevOffset := s.offset
+ s.length = minMatchLength - 1
+ s.offset = 0
+ minIndex := s.index - windowSize
if minIndex < 0 {
minIndex = 0
}
- if d.chainHead-d.hashOffset >= minIndex && 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 s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
+ if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, minMatchLength-1, lookahead); ok {
+ s.length = newLength
+ s.offset = newOffset
}
}
- if prevLength >= minMatchLength && d.length <= prevLength {
+ if prevLength >= minMatchLength && s.length <= prevLength {
// There was a match at the previous step, and the current match is
// not better. Output the previous match.
d.tokens.tokens[d.tokens.n] = matchToken(uint32(prevLength-3), uint32(prevOffset-minOffsetSize))
@@ -638,21 +650,21 @@ func (d *compressor) deflateLazy() {
// lookahead, the last two strings are not inserted into the hash
// table.
var newIndex int
- newIndex = d.index + prevLength - 1
+ newIndex = s.index + prevLength - 1
// Calculate missing hashes
end := newIndex
- if end > d.maxInsertIndex {
- end = d.maxInsertIndex
+ if end > s.maxInsertIndex {
+ end = s.maxInsertIndex
}
end += minMatchLength - 1
- startindex := d.index + 1
- if startindex > d.maxInsertIndex {
- startindex = d.maxInsertIndex
+ startindex := s.index + 1
+ if startindex > s.maxInsertIndex {
+ startindex = s.maxInsertIndex
}
tocheck := d.window[startindex:end]
dstSize := len(tocheck) - minMatchLength + 1
if dstSize > 0 {
- dst := d.hashMatch[:dstSize]
+ dst := s.hashMatch[:dstSize]
bulkHash4(tocheck, dst)
var newH uint32
for i, val := range dst {
@@ -660,74 +672,74 @@ func (d *compressor) deflateLazy() {
newH = val & hashMask
// Get previous value with the same hash.
// Our chain should point to the previous value.
- d.hashPrev[di&windowMask] = d.hashHead[newH]
+ s.hashPrev[di&windowMask] = s.hashHead[newH]
// Set the head of the hash chain to us.
- d.hashHead[newH] = uint32(di + d.hashOffset)
+ s.hashHead[newH] = uint32(di + s.hashOffset)
}
- d.hash = newH
+ s.hash = newH
}
- d.index = newIndex
+ s.index = newIndex
d.byteAvailable = false
- d.length = minMatchLength - 1
+ s.length = minMatchLength - 1
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
} else {
// Reset, if we got a match this run.
- if d.length >= minMatchLength {
- d.ii = 0
+ if s.length >= minMatchLength {
+ s.ii = 0
}
// We have a byte waiting. Emit it.
if d.byteAvailable {
- d.ii++
- d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ s.ii++
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
- d.index++
+ s.index++
// If we have a long run of no matches, skip additional bytes
- // Resets when d.ii overflows after 64KB.
- if d.ii > 31 {
- n := int(d.ii >> 5)
+ // Resets when s.ii overflows after 64KB.
+ if s.ii > 31 {
+ n := int(s.ii >> 5)
for j := 0; j < n; j++ {
- if d.index >= d.windowEnd-1 {
+ if s.index >= d.windowEnd-1 {
break
}
- d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
- d.index++
+ s.index++
}
// Flush last byte
- d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
d.byteAvailable = false
- // d.length = minMatchLength - 1 // not needed, since d.ii is reset above, so it should never be > minMatchLength
+ // s.length = minMatchLength - 1 // not needed, since s.ii is reset above, so it should never be > minMatchLength
if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
}
} else {
- d.index++
+ s.index++
d.byteAvailable = true
}
}
@@ -737,36 +749,36 @@ func (d *compressor) deflateLazy() {
// Assumes that d.fastSkipHashing != skipNever,
// otherwise use deflateLazySSE
func (d *compressor) deflateSSE() {
-
+ s := d.state
// Sanity enables additional runtime tests.
// It's intended to be used during development
// to supplement the currently ad-hoc unit tests.
const sanity = false
- if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
+ if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
return
}
- d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
- if d.index < d.maxInsertIndex {
- d.hash = crc32sse(d.window[d.index:d.index+minMatchLength]) & hashMask
+ s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
+ if s.index < s.maxInsertIndex {
+ s.hash = crc32sse(d.window[s.index:s.index+minMatchLength]) & hashMask
}
for {
- if sanity && d.index > d.windowEnd {
+ if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
- lookahead := d.windowEnd - d.index
+ lookahead := d.windowEnd - s.index
if lookahead < minMatchLength+maxMatchLength {
if !d.sync {
return
}
- if sanity && d.index > d.windowEnd {
+ if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
if lookahead == 0 {
if d.tokens.n > 0 {
- if d.err = d.writeBlockSkip(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlockSkip(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
@@ -774,55 +786,55 @@ func (d *compressor) deflateSSE() {
return
}
}
- if d.index < d.maxInsertIndex {
+ if s.index < s.maxInsertIndex {
// Update the hash
- d.hash = crc32sse(d.window[d.index:d.index+minMatchLength]) & hashMask
- ch := d.hashHead[d.hash]
- d.chainHead = int(ch)
- d.hashPrev[d.index&windowMask] = ch
- d.hashHead[d.hash] = uint32(d.index + d.hashOffset)
+ s.hash = crc32sse(d.window[s.index:s.index+minMatchLength]) & hashMask
+ ch := s.hashHead[s.hash]
+ s.chainHead = int(ch)
+ s.hashPrev[s.index&windowMask] = ch
+ s.hashHead[s.hash] = uint32(s.index + s.hashOffset)
}
- d.length = minMatchLength - 1
- d.offset = 0
- minIndex := d.index - windowSize
+ s.length = minMatchLength - 1
+ s.offset = 0
+ minIndex := s.index - windowSize
if minIndex < 0 {
minIndex = 0
}
- if d.chainHead-d.hashOffset >= minIndex && lookahead > minMatchLength-1 {
- if newLength, newOffset, ok := d.findMatchSSE(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
- d.length = newLength
- d.offset = newOffset
+ if s.chainHead-s.hashOffset >= minIndex && lookahead > minMatchLength-1 {
+ if newLength, newOffset, ok := d.findMatchSSE(s.index, s.chainHead-s.hashOffset, minMatchLength-1, lookahead); ok {
+ s.length = newLength
+ s.offset = newOffset
}
}
- if d.length >= minMatchLength {
- d.ii = 0
+ if s.length >= minMatchLength {
+ s.ii = 0
// There was a match at the previous step, and the current match is
// not better. Output the previous match.
- // "d.length-3" should NOT be "d.length-minMatchLength", since the format always assume 3
- d.tokens.tokens[d.tokens.n] = matchToken(uint32(d.length-3), uint32(d.offset-minOffsetSize))
+ // "s.length-3" should NOT be "s.length-minMatchLength", since the format always assume 3
+ d.tokens.tokens[d.tokens.n] = matchToken(uint32(s.length-3), uint32(s.offset-minOffsetSize))
d.tokens.n++
// 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 {
+ if s.length <= d.fastSkipHashing {
var newIndex int
- newIndex = d.index + d.length
+ newIndex = s.index + s.length
// Calculate missing hashes
end := newIndex
- if end > d.maxInsertIndex {
- end = d.maxInsertIndex
+ if end > s.maxInsertIndex {
+ end = s.maxInsertIndex
}
end += minMatchLength - 1
- startindex := d.index + 1
- if startindex > d.maxInsertIndex {
- startindex = d.maxInsertIndex
+ startindex := s.index + 1
+ if startindex > s.maxInsertIndex {
+ startindex = s.maxInsertIndex
}
tocheck := d.window[startindex:end]
dstSize := len(tocheck) - minMatchLength + 1
if dstSize > 0 {
- dst := d.hashMatch[:dstSize]
+ dst := s.hashMatch[:dstSize]
crc32sseAll(tocheck, dst)
var newH uint32
@@ -831,35 +843,35 @@ func (d *compressor) deflateSSE() {
newH = val & hashMask
// Get previous value with the same hash.
// Our chain should point to the previous value.
- d.hashPrev[di&windowMask] = d.hashHead[newH]
+ s.hashPrev[di&windowMask] = s.hashHead[newH]
// Set the head of the hash chain to us.
- d.hashHead[newH] = uint32(di + d.hashOffset)
+ s.hashHead[newH] = uint32(di + s.hashOffset)
}
- d.hash = newH
+ s.hash = newH
}
- d.index = newIndex
+ s.index = newIndex
} 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 = crc32sse(d.window[d.index:d.index+minMatchLength]) & hashMask
+ s.index += s.length
+ if s.index < s.maxInsertIndex {
+ s.hash = crc32sse(d.window[s.index:s.index+minMatchLength]) & hashMask
}
}
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
- if d.err = d.writeBlockSkip(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlockSkip(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
} else {
- d.ii++
- end := d.index + int(d.ii>>5) + 1
+ s.ii++
+ end := s.index + int(s.ii>>5) + 1
if end > d.windowEnd {
end = d.windowEnd
}
- for i := d.index; i < end; i++ {
+ for i := s.index; i < end; i++ {
d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[i]))
d.tokens.n++
if d.tokens.n == maxFlateBlockTokens {
@@ -869,7 +881,7 @@ func (d *compressor) deflateSSE() {
d.tokens.n = 0
}
}
- d.index = end
+ s.index = end
}
}
}
@@ -877,42 +889,43 @@ func (d *compressor) deflateSSE() {
// deflateLazy is the same as deflate, but with d.fastSkipHashing == skipNever,
// meaning it always has lazy matching on.
func (d *compressor) deflateLazySSE() {
+ s := d.state
// Sanity enables additional runtime tests.
// It's intended to be used during development
// to supplement the currently ad-hoc unit tests.
const sanity = false
- if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
+ if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
return
}
- d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
- if d.index < d.maxInsertIndex {
- d.hash = crc32sse(d.window[d.index:d.index+minMatchLength]) & hashMask
+ s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
+ if s.index < s.maxInsertIndex {
+ s.hash = crc32sse(d.window[s.index:s.index+minMatchLength]) & hashMask
}
for {
- if sanity && d.index > d.windowEnd {
+ if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
- lookahead := d.windowEnd - d.index
+ lookahead := d.windowEnd - s.index
if lookahead < minMatchLength+maxMatchLength {
if !d.sync {
return
}
- if sanity && d.index > d.windowEnd {
+ if sanity && s.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.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
d.byteAvailable = false
}
if d.tokens.n > 0 {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
@@ -920,30 +933,30 @@ func (d *compressor) deflateLazySSE() {
return
}
}
- if d.index < d.maxInsertIndex {
+ if s.index < s.maxInsertIndex {
// Update the hash
- d.hash = crc32sse(d.window[d.index:d.index+minMatchLength]) & hashMask
- ch := d.hashHead[d.hash]
- d.chainHead = int(ch)
- d.hashPrev[d.index&windowMask] = ch
- d.hashHead[d.hash] = uint32(d.index + d.hashOffset)
+ s.hash = crc32sse(d.window[s.index:s.index+minMatchLength]) & hashMask
+ ch := s.hashHead[s.hash]
+ s.chainHead = int(ch)
+ s.hashPrev[s.index&windowMask] = ch
+ s.hashHead[s.hash] = uint32(s.index + s.hashOffset)
}
- prevLength := d.length
- prevOffset := d.offset
- d.length = minMatchLength - 1
- d.offset = 0
- minIndex := d.index - windowSize
+ prevLength := s.length
+ prevOffset := s.offset
+ s.length = minMatchLength - 1
+ s.offset = 0
+ minIndex := s.index - windowSize
if minIndex < 0 {
minIndex = 0
}
- if d.chainHead-d.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
- if newLength, newOffset, ok := d.findMatchSSE(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
- d.length = newLength
- d.offset = newOffset
+ if s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
+ if newLength, newOffset, ok := d.findMatchSSE(s.index, s.chainHead-s.hashOffset, minMatchLength-1, lookahead); ok {
+ s.length = newLength
+ s.offset = newOffset
}
}
- if prevLength >= minMatchLength && d.length <= prevLength {
+ if prevLength >= minMatchLength && s.length <= prevLength {
// There was a match at the previous step, and the current match is
// not better. Output the previous match.
d.tokens.tokens[d.tokens.n] = matchToken(uint32(prevLength-3), uint32(prevOffset-minOffsetSize))
@@ -954,21 +967,21 @@ func (d *compressor) deflateLazySSE() {
// lookahead, the last two strings are not inserted into the hash
// table.
var newIndex int
- newIndex = d.index + prevLength - 1
+ newIndex = s.index + prevLength - 1
// Calculate missing hashes
end := newIndex
- if end > d.maxInsertIndex {
- end = d.maxInsertIndex
+ if end > s.maxInsertIndex {
+ end = s.maxInsertIndex
}
end += minMatchLength - 1
- startindex := d.index + 1
- if startindex > d.maxInsertIndex {
- startindex = d.maxInsertIndex
+ startindex := s.index + 1
+ if startindex > s.maxInsertIndex {
+ startindex = s.maxInsertIndex
}
tocheck := d.window[startindex:end]
dstSize := len(tocheck) - minMatchLength + 1
if dstSize > 0 {
- dst := d.hashMatch[:dstSize]
+ dst := s.hashMatch[:dstSize]
crc32sseAll(tocheck, dst)
var newH uint32
for i, val := range dst {
@@ -976,74 +989,74 @@ func (d *compressor) deflateLazySSE() {
newH = val & hashMask
// Get previous value with the same hash.
// Our chain should point to the previous value.
- d.hashPrev[di&windowMask] = d.hashHead[newH]
+ s.hashPrev[di&windowMask] = s.hashHead[newH]
// Set the head of the hash chain to us.
- d.hashHead[newH] = uint32(di + d.hashOffset)
+ s.hashHead[newH] = uint32(di + s.hashOffset)
}
- d.hash = newH
+ s.hash = newH
}
- d.index = newIndex
+ s.index = newIndex
d.byteAvailable = false
- d.length = minMatchLength - 1
+ s.length = minMatchLength - 1
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
} else {
// Reset, if we got a match this run.
- if d.length >= minMatchLength {
- d.ii = 0
+ if s.length >= minMatchLength {
+ s.ii = 0
}
// We have a byte waiting. Emit it.
if d.byteAvailable {
- d.ii++
- d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ s.ii++
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
- d.index++
+ s.index++
// If we have a long run of no matches, skip additional bytes
- // Resets when d.ii overflows after 64KB.
- if d.ii > 31 {
- n := int(d.ii >> 6)
+ // Resets when s.ii overflows after 64KB.
+ if s.ii > 31 {
+ n := int(s.ii >> 6)
for j := 0; j < n; j++ {
- if d.index >= d.windowEnd-1 {
+ if s.index >= d.windowEnd-1 {
break
}
- d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
- d.index++
+ s.index++
}
// Flush last byte
- d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[d.index-1]))
+ d.tokens.tokens[d.tokens.n] = literalToken(uint32(d.window[s.index-1]))
d.tokens.n++
d.byteAvailable = false
- // d.length = minMatchLength - 1 // not needed, since d.ii is reset above, so it should never be > minMatchLength
+ // s.length = minMatchLength - 1 // not needed, since s.ii is reset above, so it should never be > minMatchLength
if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(d.tokens, d.index, false); d.err != nil {
+ if d.err = d.writeBlock(d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.n = 0
}
}
} else {
- d.index++
+ s.index++
d.byteAvailable = true
}
}
@@ -1167,7 +1180,7 @@ func (d *compressor) init(w io.Writer, level int) (err error) {
d.fill = (*compressor).fillBlock
d.step = (*compressor).storeHuff
case level >= 1 && level <= 4:
- d.snap = newSnappy(level)
+ d.snap = newFastEnc(level)
d.window = make([]byte, maxStoreBlockSize)
d.fill = (*compressor).fillBlock
d.step = (*compressor).storeSnappy
@@ -1175,6 +1188,7 @@ func (d *compressor) init(w io.Writer, level int) (err error) {
level = 5
fallthrough
case 5 <= level && level <= 9:
+ d.state = &advancedState{}
d.compressionLevel = levels[level]
d.initDeflate()
d.fill = (*compressor).fillDeflate
@@ -1215,22 +1229,23 @@ func (d *compressor) reset(w io.Writer) {
// level was NoCompression or ConstantCompresssion.
d.windowEnd = 0
default:
- d.chainHead = -1
- for i := range d.hashHead {
- d.hashHead[i] = 0
+ s := d.state
+ s.chainHead = -1
+ for i := range s.hashHead {
+ s.hashHead[i] = 0
}
- for i := range d.hashPrev {
- d.hashPrev[i] = 0
+ for i := range s.hashPrev {
+ s.hashPrev[i] = 0
}
- d.hashOffset = 1
- d.index, d.windowEnd = 0, 0
+ s.hashOffset = 1
+ s.index, d.windowEnd = 0, 0
d.blockStart, d.byteAvailable = 0, false
d.tokens.n = 0
- d.length = minMatchLength - 1
- d.offset = 0
- d.hash = 0
- d.ii = 0
- d.maxInsertIndex = 0
+ s.length = minMatchLength - 1
+ s.offset = 0
+ s.hash = 0
+ s.ii = 0
+ s.maxInsertIndex = 0
}
}
diff --git a/vendor/github.com/klauspost/compress/flate/huffman_bit_writer.go b/vendor/github.com/klauspost/compress/flate/huffman_bit_writer.go
index f9b2a699a..f46c65418 100644
--- a/vendor/github.com/klauspost/compress/flate/huffman_bit_writer.go
+++ b/vendor/github.com/klauspost/compress/flate/huffman_bit_writer.go
@@ -35,7 +35,7 @@ const (
)
// The number of extra bits needed by length code X - LENGTH_CODES_START.
-var lengthExtraBits = []int8{
+var lengthExtraBits = [32]int8{
/* 257 */ 0, 0, 0,
/* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
/* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
@@ -43,14 +43,14 @@ var lengthExtraBits = []int8{
}
// The length indicated by length code X - LENGTH_CODES_START.
-var lengthBase = []uint32{
+var lengthBase = [32]uint8{
0, 1, 2, 3, 4, 5, 6, 7, 8, 10,
12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
64, 80, 96, 112, 128, 160, 192, 224, 255,
}
// offset code word extra bits.
-var offsetExtraBits = []int8{
+var offsetExtraBits = [64]int8{
0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
@@ -58,7 +58,7 @@ var offsetExtraBits = []int8{
14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20,
}
-var offsetBase = []uint32{
+var offsetBase = [64]uint32{
/* normal deflate */
0x000000, 0x000001, 0x000002, 0x000003, 0x000004,
0x000006, 0x000008, 0x00000c, 0x000010, 0x000018,
@@ -86,9 +86,9 @@ type huffmanBitWriter struct {
// and then the low nbits of bits.
bits uint64
nbits uint
- bytes [bufferSize]byte
+ bytes [256]byte
codegenFreq [codegenCodeCount]int32
- nbytes int
+ nbytes uint8
literalFreq []int32
offsetFreq []int32
codegen []uint8
@@ -101,8 +101,8 @@ type huffmanBitWriter struct {
func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
return &huffmanBitWriter{
writer: w,
- literalFreq: make([]int32, maxNumLit),
- offsetFreq: make([]int32, offsetCodeCount),
+ literalFreq: make([]int32, lengthCodesStart+32),
+ offsetFreq: make([]int32, 32),
codegen: make([]uint8, maxNumLit+offsetCodeCount+1),
literalEncoding: newHuffmanEncoder(maxNumLit),
codegenEncoding: newHuffmanEncoder(codegenCodeCount),
@@ -113,7 +113,7 @@ func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
func (w *huffmanBitWriter) reset(writer io.Writer) {
w.writer = writer
w.bits, w.nbits, w.nbytes, w.err = 0, 0, 0, nil
- w.bytes = [bufferSize]byte{}
+ w.bytes = [256]byte{}
}
func (w *huffmanBitWriter) flush() {
@@ -145,9 +145,6 @@ func (w *huffmanBitWriter) write(b []byte) {
}
func (w *huffmanBitWriter) writeBits(b int32, nb uint) {
- if w.err != nil {
- return
- }
w.bits |= uint64(b) << w.nbits
w.nbits += nb
if w.nbits >= 48 {
@@ -155,15 +152,18 @@ func (w *huffmanBitWriter) writeBits(b int32, nb uint) {
w.bits >>= 48
w.nbits -= 48
n := w.nbytes
- bytes := w.bytes[n : n+6]
- bytes[0] = byte(bits)
- bytes[1] = byte(bits >> 8)
- bytes[2] = byte(bits >> 16)
- bytes[3] = byte(bits >> 24)
- bytes[4] = byte(bits >> 32)
- bytes[5] = byte(bits >> 40)
+ w.bytes[n] = byte(bits)
+ w.bytes[n+1] = byte(bits >> 8)
+ w.bytes[n+2] = byte(bits >> 16)
+ w.bytes[n+3] = byte(bits >> 24)
+ w.bytes[n+4] = byte(bits >> 32)
+ w.bytes[n+5] = byte(bits >> 40)
n += 6
if n >= bufferFlushSize {
+ if w.err != nil {
+ n = 0
+ return
+ }
w.write(w.bytes[:n])
n = 0
}
@@ -333,9 +333,6 @@ func (w *huffmanBitWriter) storedSize(in []byte) (int, bool) {
}
func (w *huffmanBitWriter) writeCode(c hcode) {
- if w.err != nil {
- return
- }
w.bits |= uint64(c.code) << w.nbits
w.nbits += uint(c.len)
if w.nbits >= 48 {
@@ -343,15 +340,18 @@ func (w *huffmanBitWriter) writeCode(c hcode) {
w.bits >>= 48
w.nbits -= 48
n := w.nbytes
- bytes := w.bytes[n : n+6]
- bytes[0] = byte(bits)
- bytes[1] = byte(bits >> 8)
- bytes[2] = byte(bits >> 16)
- bytes[3] = byte(bits >> 24)
- bytes[4] = byte(bits >> 32)
- bytes[5] = byte(bits >> 40)
+ w.bytes[n] = byte(bits)
+ w.bytes[n+1] = byte(bits >> 8)
+ w.bytes[n+2] = byte(bits >> 16)
+ w.bytes[n+3] = byte(bits >> 24)
+ w.bytes[n+4] = byte(bits >> 32)
+ w.bytes[n+5] = byte(bits >> 40)
n += 6
if n >= bufferFlushSize {
+ if w.err != nil {
+ n = 0
+ return
+ }
w.write(w.bytes[:n])
n = 0
}
@@ -460,7 +460,7 @@ func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
}
for offsetCode := 4; offsetCode < numOffsets; offsetCode++ {
// First four offset codes have extra size = 0.
- extraBits += int(w.offsetFreq[offsetCode]) * int(offsetExtraBits[offsetCode])
+ extraBits += int(w.offsetFreq[offsetCode]) * int(offsetExtraBits[offsetCode&63])
}
}
@@ -548,15 +548,30 @@ func (w *huffmanBitWriter) indexTokens(tokens []token) (numLiterals, numOffsets
w.offsetFreq[i] = 0
}
+ if len(tokens) == 0 {
+ return
+ }
+
+ // Only last token should be endBlockMarker.
+ if tokens[len(tokens)-1] == endBlockMarker {
+ w.literalFreq[endBlockMarker]++
+ tokens = tokens[:len(tokens)-1]
+ }
+
+ // Create slices up to the next power of two to avoid bounds checks.
+ lits := w.literalFreq[:256]
+ offs := w.offsetFreq[:32]
+ lengths := w.literalFreq[lengthCodesStart:]
+ lengths = lengths[:32]
for _, t := range tokens {
- if t < matchType {
- w.literalFreq[t.literal()]++
+ if t < endBlockMarker {
+ lits[t.literal()]++
continue
}
length := t.length()
offset := t.offset()
- w.literalFreq[lengthCodesStart+lengthCode(length)]++
- w.offsetFreq[offsetCode(offset)]++
+ lengths[lengthCode(length)&31]++
+ offs[offsetCode(offset)&31]++
}
// get the number of literals
@@ -575,8 +590,8 @@ func (w *huffmanBitWriter) indexTokens(tokens []token) (numLiterals, numOffsets
w.offsetFreq[0] = 1
numOffsets = 1
}
- w.literalEncoding.generate(w.literalFreq, 15)
- w.offsetEncoding.generate(w.offsetFreq, 15)
+ w.literalEncoding.generate(w.literalFreq[:maxNumLit], 15)
+ w.offsetEncoding.generate(w.offsetFreq[:offsetCodeCount], 15)
return
}
@@ -586,30 +601,50 @@ func (w *huffmanBitWriter) writeTokens(tokens []token, leCodes, oeCodes []hcode)
if w.err != nil {
return
}
+ if len(tokens) == 0 {
+ return
+ }
+
+ // Only last token should be endBlockMarker.
+ var deferEOB bool
+ if tokens[len(tokens)-1] == endBlockMarker {
+ tokens = tokens[:len(tokens)-1]
+ deferEOB = true
+ }
+
+ // Create slices up to the next power of two to avoid bounds checks.
+ lits := leCodes[:256]
+ offs := oeCodes[:32]
+ lengths := leCodes[lengthCodesStart:]
+ lengths = lengths[:32]
for _, t := range tokens {
if t < matchType {
- w.writeCode(leCodes[t.literal()])
+ w.writeCode(lits[t.literal()])
continue
}
+
// Write the length
length := t.length()
lengthCode := lengthCode(length)
- w.writeCode(leCodes[lengthCode+lengthCodesStart])
- extraLengthBits := uint(lengthExtraBits[lengthCode])
+ w.writeCode(lengths[lengthCode&31])
+ extraLengthBits := uint(lengthExtraBits[lengthCode&31])
if extraLengthBits > 0 {
- extraLength := int32(length - lengthBase[lengthCode])
+ extraLength := int32(length - lengthBase[lengthCode&31])
w.writeBits(extraLength, extraLengthBits)
}
// Write the offset
offset := t.offset()
offsetCode := offsetCode(offset)
- w.writeCode(oeCodes[offsetCode])
- extraOffsetBits := uint(offsetExtraBits[offsetCode])
+ w.writeCode(offs[offsetCode&31])
+ extraOffsetBits := uint(offsetExtraBits[offsetCode&63])
if extraOffsetBits > 0 {
- extraOffset := int32(offset - offsetBase[offsetCode])
+ extraOffset := int32(offset - offsetBase[offsetCode&63])
w.writeBits(extraOffset, extraOffsetBits)
}
}
+ if deferEOB {
+ w.writeCode(leCodes[endBlockMarker])
+ }
}
// huffOffset is a static offset encoder used for huffman only encoding.
@@ -620,7 +655,7 @@ func init() {
w := newHuffmanBitWriter(nil)
w.offsetFreq[0] = 1
huffOffset = newHuffmanEncoder(offsetCodeCount)
- huffOffset.generate(w.offsetFreq, 15)
+ huffOffset.generate(w.offsetFreq[:offsetCodeCount], 15)
}
// writeBlockHuff encodes a block of bytes as either
@@ -644,7 +679,7 @@ func (w *huffmanBitWriter) writeBlockHuff(eof bool, input []byte) {
const numLiterals = endBlockMarker + 1
const numOffsets = 1
- w.literalEncoding.generate(w.literalFreq, 15)
+ w.literalEncoding.generate(w.literalFreq[:maxNumLit], 15)
// Figure out smallest code.
// Always use dynamic Huffman or Store
@@ -679,13 +714,12 @@ func (w *huffmanBitWriter) writeBlockHuff(eof bool, input []byte) {
bits := w.bits
w.bits >>= 48
w.nbits -= 48
- bytes := w.bytes[n : n+6]
- bytes[0] = byte(bits)
- bytes[1] = byte(bits >> 8)
- bytes[2] = byte(bits >> 16)
- bytes[3] = byte(bits >> 24)
- bytes[4] = byte(bits >> 32)
- bytes[5] = byte(bits >> 40)
+ w.bytes[n] = byte(bits)
+ w.bytes[n+1] = byte(bits >> 8)
+ w.bytes[n+2] = byte(bits >> 16)
+ w.bytes[n+3] = byte(bits >> 24)
+ w.bytes[n+4] = byte(bits >> 32)
+ w.bytes[n+5] = byte(bits >> 40)
n += 6
if n < bufferFlushSize {
continue
diff --git a/vendor/github.com/klauspost/compress/flate/huffman_code.go b/vendor/github.com/klauspost/compress/flate/huffman_code.go
index bdcbd823b..f65f79336 100644
--- a/vendor/github.com/klauspost/compress/flate/huffman_code.go
+++ b/vendor/github.com/klauspost/compress/flate/huffman_code.go
@@ -6,6 +6,7 @@ package flate
import (
"math"
+ "math/bits"
"sort"
)
@@ -56,7 +57,9 @@ func (h *hcode) set(code uint16, length uint16) {
func maxNode() literalNode { return literalNode{math.MaxUint16, math.MaxInt32} }
func newHuffmanEncoder(size int) *huffmanEncoder {
- return &huffmanEncoder{codes: make([]hcode, size)}
+ // Make capacity to next power of two.
+ c := uint(bits.Len32(uint32(size - 1)))
+ return &huffmanEncoder{codes: make([]hcode, size, 1<<c)}
}
// Generates a HuffmanCode corresponding to the fixed literal table
diff --git a/vendor/github.com/klauspost/compress/flate/snappy.go b/vendor/github.com/klauspost/compress/flate/snappy.go
index d853320a7..aebebd524 100644
--- a/vendor/github.com/klauspost/compress/flate/snappy.go
+++ b/vendor/github.com/klauspost/compress/flate/snappy.go
@@ -20,12 +20,12 @@ func emitCopy(dst *tokens, offset, length int) {
dst.n++
}
-type snappyEnc interface {
+type fastEnc interface {
Encode(dst *tokens, src []byte)
Reset()
}
-func newSnappy(level int) snappyEnc {
+func newFastEnc(level int) fastEnc {
switch level {
case 1:
return &snappyL1{}
diff --git a/vendor/github.com/klauspost/compress/flate/token.go b/vendor/github.com/klauspost/compress/flate/token.go
index 4f275ea61..141299b97 100644
--- a/vendor/github.com/klauspost/compress/flate/token.go
+++ b/vendor/github.com/klauspost/compress/flate/token.go
@@ -4,8 +4,6 @@
package flate
-import "fmt"
-
const (
// 2 bits: type 0 = literal 1=EOF 2=Match 3=Unused
// 8 bits: xlength = length - MIN_MATCH_LENGTH
@@ -19,7 +17,7 @@ const (
// The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
// is lengthCodes[length - MIN_MATCH_LENGTH]
-var lengthCodes = [...]uint32{
+var lengthCodes = [256]uint8{
0, 1, 2, 3, 4, 5, 6, 7, 8, 8,
9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
13, 13, 13, 13, 14, 14, 14, 14, 15, 15,
@@ -48,7 +46,7 @@ var lengthCodes = [...]uint32{
27, 27, 27, 27, 27, 28,
}
-var offsetCodes = [...]uint32{
+var offsetCodes = [256]uint32{
0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
@@ -82,34 +80,27 @@ func matchToken(xlength uint32, xoffset uint32) token {
return token(matchType + xlength<<lengthShift + xoffset)
}
-func matchTokend(xlength uint32, xoffset uint32) token {
- if xlength > maxMatchLength || xoffset > maxMatchOffset {
- panic(fmt.Sprintf("Invalid match: len: %d, offset: %d\n", xlength, xoffset))
- return token(matchType)
- }
- return token(matchType + xlength<<lengthShift + xoffset)
-}
-
// Returns the type of a token
func (t token) typ() uint32 { return uint32(t) & typeMask }
// Returns the literal of a literal token
-func (t token) literal() uint32 { return uint32(t - literalType) }
+func (t token) literal() uint8 { return uint8(t) }
// Returns the extra offset of a match token
func (t token) offset() uint32 { return uint32(t) & offsetMask }
-func (t token) length() uint32 { return uint32((t - matchType) >> lengthShift) }
+func (t token) length() uint8 { return uint8(t >> lengthShift) }
-func lengthCode(len uint32) uint32 { return lengthCodes[len] }
+// The code is never more than 8 bits, but is returned as uint32 for convenience.
+func lengthCode(len uint8) uint32 { return uint32(lengthCodes[len]) }
// Returns the offset code corresponding to a specific offset
func offsetCode(off uint32) uint32 {
if off < uint32(len(offsetCodes)) {
- return offsetCodes[off]
+ return offsetCodes[off&255]
} else if off>>7 < uint32(len(offsetCodes)) {
- return offsetCodes[off>>7] + 14
+ return offsetCodes[(off>>7)&255] + 14
} else {
- return offsetCodes[off>>14] + 28
+ return offsetCodes[(off>>14)&255] + 28
}
}