tests/test.sh exit code (0 → resolved); the classification below is post-hoc and cannot change it.pwd && rg -n "func \(d \*compressor\) deflateLazy|deflateLazy|storedDeflate|writeBlock|dynamic|fixed" /app/flate/deflate.go
Chunk ID: 430c8b
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 376
Output:
/app
172:func (d *compressor) writeBlock(tok *tokens, index int, eof bool) error {
179: //d.w.writeBlock(tok, eof, window)
180: d.w.writeBlockDynamic(tok, eof, window, d.sync)
186:// writeBlockSkip writes the current block and uses the number of tokens
189:func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
196: d.w.writeBlockHuff(eof, window, d.sync)
198: // Write a dynamic huffman block.
199: d.w.writeBlockDynamic(tok, eof, window, d.sync)
202: d.w.writeBlock(tok, eof, nil)
406:// deflateLazy is the same as deflate, but with d.fastSkipHashing == skipNever,
408:func (d *compressor) deflateLazy() {
452: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
513: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
554: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
614: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
630: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
647: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
667: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
725: d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
741: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
744: d.w.writeBlockDynamic(&d.tokens, false, d.window[:d.windowEnd], d.sync)
813: d.step = (*compressor).deflateLazy
rg --files /app | sed 's#^/app/##' | head -200
Chunk ID: 08f9d9 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 987 Output: go.mod flate/fuzz_test.go flate/level1.go flate/huffman_code.go flate/level6.go flate/matchlen_generic.go flate/level4.go flate/token_test.go flate/huffman_sortByLiteral.go flate/flate_test.go flate/deflate.go flate/large_low_entropy_test.go flate/regmask_other.go flate/token.go flate/testdata/huffman-pi.sync.expect-noinput flate/testdata/huffman-rand-max.golden flate/testdata/huffman-zero.sync.expect flate/testdata/huffman-null-max.dyn.expect flate/testdata/huffman-shifts.wb.expect flate/testdata/huffman-rand-limit.dyn.expect flate/testdata/huffman-pi.wb.expect flate/testdata/tokens.bin flate/testdata/partial-block flate/testdata/huffman-null-max.sync.expect flate/testdata/huffman-rand-limit.wb.expect flate/testdata/huffman-text-shift.dyn.expect flate/testdata/huffman-shifts.sync.expect flate/testdata/huffman-null-max.in flate/testdata/huffman-rand-limit.wb.expect-noinput flate/testdata/huffman-text-shift.sync.expect flate/testdata/huffman-shifts.golden flate/testdata/huffman-zero.in flate/testdata/null-long-match.dyn.expect-noinput flate/testdata/regression.zip flate/testdata/huffman-text.wb.expect flate/testdata/huffman-text.dyn.expect flate/testdata/huffman-rand-max.in flate/testdata/huffman-text-shift.golden flate/testdata/huffman-rand-1k.wb.expect flate/testdata/huffman-text.dyn.expect-noinput flate/testdata/huffman-null-max.dyn.expect-noinput flate/testdata/huffman-pi.wb.expect-noinput flate/testdata/huffman-rand-1k.wb.expect-noinput flate/testdata/huffman-text.sync.expect flate/testdata/huffman-shifts.in flate/testdata/huffman-null-max.sync.expect-noinput flate/testdata/huffman-text.in flate/testdata/huffman-rand-1k.dyn.expect-noinput flate/testdata/huffman-zero.wb.expect-noinput flate/testdata/huffman-text.sync.expect-noinput flate/testdata/huffman-text-shift.wb.expect-noinput flate/testdata/huffman-zero.dyn.expect-noinput flate/testdata/huffman-shifts.sync.expect-noinput flate/testdata/huffman-zero.wb.expect flate/testdata/huffman-text-shift.dyn.expect-noinput flate/testdata/huffman-pi.golden flate/testdata/huffman-rand-1k.dyn.expect flate/testdata/null-long-match.sync.expect-noinput flate/testdata/huffman-rand-limit.golden flate/testdata/huffman-rand-1k.sync.expect flate/testdata/huffman-rand-limit.sync.expect flate/testdata/huffman-rand-1k.golden flate/testdata/huffman-rand-1k.in flate/testdata/huffman-pi.sync.expect flate/testdata/huffman-shifts.wb.expect-noinput flate/testdata/huffman-zero.golden flate/testdata/huffman-zero.sync.expect-noinput flate/testdata/huffman-pi.in flate/testdata/huffman-text-shift.sync.expect-noinput flate/testdata/huffman-null-max.golden flate/testdata/huffman-shifts.dyn.expect flate/testdata/null-long-match.wb.expect-noinput flate/testdata/huffman-zero.dyn.expect flate/testdata/huffman-text.golden flate/testdata/huffman-text-shift.in flate/testdata/huffman-null-max.wb.expect-noinput flate/testdata/huffman-rand-1k.sync.expect-noinput flate/testdata/huffman-shifts.dyn.expect-noinput flate/testdata/huffman-text.wb.expect-noinput flate/testdata/huffman-null-max.wb.expect flate/testdata/huffman-rand-limit.dyn.expect-noinput flate/testdata/huffman-rand-limit.sync.expect-noinput flate/testdata/huffman-rand-limit.in flate/testdata/fuzz/encode-raw-corpus.zip flate/testdata/fuzz/FuzzEncoding.zip flate/testdata/huffman-pi.dyn.expect flate/testdata/huffman-text-shift.wb.expect flate/testdata/huffman-pi.dyn.expect-noinput flate/level3.go flate/huffman_bit_writer.go flate/inflate_test.go flate/regmask_amd64.go flate/fast_encoder.go flate/level2.go flate/dict_decoder.go flate/_gen/gen_inflate.go flate/writer_test.go flate/inflate.go flate/dict_decoder_test.go flate/level5.go flate/deflate_test.go flate/huffman_bit_writer_test.go flate/stateless.go flate/example_test.go flate/huffman_sortByFreq.go flate/inflate_gen.go flate/reader_test.go internal/le/le.go internal/le/unsafe_disabled.go internal/le/unsafe_enabled.go internal/fuzz/helpers.go go.sum
go test ./flate -run 'Test|Round|Regression|Local' -count=1
Chunk ID: 6294f7
Wall time: 6.1853 seconds
Process exited with code 1
Original token count: 394
Output:
--- FAIL: TestDeflateInflateString (0.01s)
deflate_test.go:387: open ../testdata/e.txt: no such file or directory
deflate_test.go:320: level: 0 - Size:0.00%, 2 b
deflate_test.go:320: level: 1 - Size:0.00%, 2 b
deflate_test.go:320: level: 2 - Size:0.00%, 2 b
deflate_test.go:320: level: 3 - Size:0.00%, 2 b
deflate_test.go:320: level: 4 - Size:0.00%, 2 b
deflate_test.go:320: level: 5 - Size:0.00%, 2 b
deflate_test.go:320: level: 6 - Size:0.00%, 2 b
deflate_test.go:320: level: 7 - Size:0.00%, 2 b
deflate_test.go:320: level: 8 - Size:0.00%, 2 b
deflate_test.go:320: level: 9 - Size:0.00%, 2 b
deflate_test.go:320: level: -2 - Size:0.00%, 2 b
deflate_test.go:387: open ../testdata/Mark.Twain-Tom.Sawyer.txt: no such file or directory
deflate_test.go:320: level: 0 - Size:0.00%, 2 b
deflate_test.go:320: level: 1 - Size:0.00%, 2 b
deflate_test.go:320: level: 2 - Size:0.00%, 2 b
deflate_test.go:320: level: 3 - Size:0.00%, 2 b
deflate_test.go:320: level: 4 - Size:0.00%, 2 b
deflate_test.go:320: level: 5 - Size:0.00%, 2 b
deflate_test.go:320: level: 6 - Size:0.00%, 2 b
deflate_test.go:320: level: 7 - Size:0.00%, 2 b
deflate_test.go:320: level: 8 - Size:0.00%, 2 b
deflate_test.go:320: level: 9 - Size:0.00%, 2 b
deflate_test.go:320: level: -2 - Size:0.00%, 2 b
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.56s)
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
FAIL
FAIL [code-host]/klauspost/compress/flate 6.194s
FAIL
sed -n '130,230p' flate/deflate.go
Chunk ID: 41f234
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 702
Output:
func (d *compressor) fillDeflate(b []byte) int {
s := d.state
if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
// shift the window by windowSize
//copy(d.window[:], d.window[windowSize:2*windowSize])
*(*[windowSize]byte)(d.window) = *(*[windowSize]byte)(d.window[windowSize:])
s.index -= windowSize
d.windowEnd -= windowSize
if d.blockStart >= windowSize {
d.blockStart -= windowSize
} else {
d.blockStart = math.MaxInt32
}
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 s.hashPrev[:] {
if int(v) > delta {
s.hashPrev[i] = uint32(int(v) - delta)
} else {
s.hashPrev[i] = 0
}
}
for i, v := range s.hashHead[:] {
if int(v) > delta {
s.hashHead[i] = uint32(int(v) - delta)
} else {
s.hashHead[i] = 0
}
}
}
}
n := copy(d.window[d.windowEnd:], b)
d.windowEnd += n
return n
}
func (d *compressor) writeBlock(tok *tokens, 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(tok, eof, window)
d.w.writeBlockDynamic(tok, eof, window, d.sync)
return d.w.err
}
return nil
}
// writeBlockSkip writes the current block and uses the number of tokens
// to determine if the block should be stored on no matches, or
// only huffman encoded.
func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
if index > 0 || eof {
if d.blockStart <= index {
window := d.window[d.blockStart:index]
// If we removed less than a 64th of all literals
// we huffman compress the block.
if int(tok.n) > len(window)-int(tok.n>>6) {
d.w.writeBlockHuff(eof, window, d.sync)
} else {
// Write a dynamic huffman block.
d.w.writeBlockDynamic(tok, eof, window, d.sync)
}
} else {
d.w.writeBlock(tok, eof, nil)
}
d.blockStart = index
return d.w.err
}
return nil
}
// fillWindow will fill the current window with the supplied
// dictionary and calculate all hashes.
// This is much faster than doing a full encode.
// Should only be used after a start/reset.
func (d *compressor) fillWindow(b []byte) {
// Do not fill window if we are in store-only or huffman mode.
if d.level <= 0 && d.level > -MinCustomWindowSize {
return
}
if d.fast != nil {
// encode the last data, but discard the result
if len(b) > maxMatchOffset {
b = b[len(b)-maxMatchOffset:]
}
d.fast.Encode(&d.tokens, b)
d.tokens.Reset()
return
}
s := d.state
// If we are given too much, cut it.
if len(b) > windowSize {
sed -n '380,700p' flate/deflate.go
Chunk ID: a2bb90
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 2412
Output:
}
hb := le.Load32(b, 0)
dst[0] = hash4u(hb, hashBits)
end := len(b) - 4 + 1
for i := 1; i < end; i++ {
hb = (hb >> 8) | uint32(b[i+3])<<24
dst[i] = hash4u(hb, hashBits)
}
}
func (d *compressor) initDeflate() {
d.window = make([]byte, 2*windowSize)
d.byteAvailable = false
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.chainHead = -1
}
// 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 = debugDeflate
if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
return
}
if d.windowEnd != s.index && d.chain > 100 {
// Get literal huffman coder.
if d.h == nil {
d.h = newHuffmanEncoder(maxFlateBlockTokens)
}
var tmp [256]uint16
for _, v := range d.window[s.index:d.windowEnd] {
tmp[v]++
}
d.h.generate(tmp[:], 15)
}
s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
for {
if sanity && s.index > d.windowEnd {
panic("index > windowEnd")
}
lookahead := d.windowEnd - s.index
if lookahead < minMatchLength+maxMatchLength {
if !d.sync {
return
}
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.AddLiteral(d.window[s.index-1])
d.byteAvailable = false
}
if d.tokens.n > 0 {
if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
return
}
}
if s.index < s.maxInsertIndex {
// Update the hash
hash := hash4(d.window[s.index:])
ch := s.hashHead[hash]
s.chainHead = int(ch)
s.hashPrev[s.index&windowMask] = ch
s.hashHead[hash] = uint32(s.index + s.hashOffset)
}
prevLength := s.length
prevOffset := s.offset
s.length = minMatchLength - 1
s.offset = 0
minIndex := max(s.index-windowSize, 0)
if s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, lookahead); ok {
s.length = newLength
s.offset = newOffset
}
}
if prevLength >= minMatchLength && s.length <= prevLength {
// No better match, but check for better match at end...
//
// Skip forward a number of bytes.
// Offset of 2 seems to yield best results. 3 is sometimes better.
const checkOff = 2
// Check all, except full length
if prevLength < maxMatchLength-checkOff {
prevIndex := s.index - 1
if prevIndex+prevLength < s.maxInsertIndex {
end := min(lookahead, maxMatchLength+checkOff)
end += prevIndex
// Hash at match end.
h := hash4(d.window[prevIndex+prevLength:])
ch2 := int(s.hashHead[h]) - s.hashOffset - prevLength
if prevIndex-ch2 != prevOffset && ch2 > minIndex+checkOff {
length := matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:])
// It seems like a pure length metric is best.
if length > prevLength {
prevLength = length
prevOffset = prevIndex - ch2
// Extend back...
for i := checkOff - 1; i >= 0; i-- {
if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i] {
// Emit tokens we "owe"
for j := 0; j <= i; j++ {
d.tokens.AddLiteral(d.window[prevIndex+j])
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
s.index++
if s.index < s.maxInsertIndex {
h := hash4(d.window[s.index:])
ch := s.hashHead[h]
s.chainHead = int(ch)
s.hashPrev[s.index&windowMask] = ch
s.hashHead[h] = uint32(s.index + s.hashOffset)
}
}
break
} else {
prevLength++
}
}
} else if false {
// Check one further ahead.
// Only rarely better, disabled for now.
prevIndex++
h := hash4(d.window[prevIndex+prevLength:])
ch2 := int(s.hashHead[h]) - s.hashOffset - prevLength
if prevIndex-ch2 != prevOffset && ch2 > minIndex+checkOff {
length := matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:])
// It seems like a pure length metric is best.
if length > prevLength+checkOff {
prevLength = length
prevOffset = prevIndex - ch2
prevIndex--
// Extend back...
for i := checkOff; i >= 0; i-- {
if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i-1] {
// Emit tokens we "owe"
for j := 0; j <= i; j++ {
d.tokens.AddLiteral(d.window[prevIndex+j])
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
s.index++
if s.index < s.maxInsertIndex {
h := hash4(d.window[s.index:])
ch := s.hashHead[h]
s.chainHead = int(ch)
s.hashPrev[s.index&windowMask] = ch
s.hashHead[h] = uint32(s.index + s.hashOffset)
}
}
break
} else {
prevLength++
}
}
}
}
}
}
}
}
// There was a match at the previous step, and the current match is
// not better. Output the previous match.
d.tokens.AddMatch(uint32(prevLength-3), 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.
newIndex := s.index + prevLength - 1
// Calculate missing hashes
end := min(newIndex, s.maxInsertIndex)
end += minMatchLength - 1
startindex := min(s.index+1, s.maxInsertIndex)
tocheck := d.window[startindex:end]
dstSize := len(tocheck) - minMatchLength + 1
if dstSize > 0 {
dst := s.hashMatch[:dstSize]
bulkHash4(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.
s.hashPrev[di&windowMask] = s.hashHead[newH]
// Set the head of the hash chain to us.
s.hashHead[newH] = uint32(di + s.hashOffset)
}
}
s.index = newIndex
d.byteAvailable = false
s.length = minMatchLength - 1
if d.tokens.n == maxFlateBlockTokens {
// The block includes the current character
if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
s.ii = 0
} else {
// Reset, if we got a match this run.
if s.length >= minMatchLength {
s.ii = 0
}
// We have a byte waiting. Emit it.
if d.byteAvailable {
s.ii++
d.tokens.AddLiteral(d.window[s.index-1])
if d.tokens.n == maxFlateBlockTokens {
if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
s.index++
// If we have a long run of no matches, skip additional bytes
// Resets when s.ii overflows after 64KB.
if n := int(s.ii) - d.chain; n > 0 {
n = 1 + int(n>>6)
for j := 0; j < n; j++ {
if s.index >= d.windowEnd-1 {
break
}
d.tokens.AddLiteral(d.window[s.index-1])
if d.tokens.n == maxFlateBlockTokens {
if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
// Index...
if s.index < s.maxInsertIndex {
h := hash4(d.window[s.index:])
ch := s.hashHead[h]
s.chainHead = int(ch)
s.hashPrev[s.index&windowMask] = ch
s.hashHead[h] = uint32(s.index + s.hashOffset)
}
s.index++
}
// Flush last byte
d.tokens.AddLiteral(d.window[s.index-1])
d.byteAvailable = false
// 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, s.index, false); d.err != nil {
return
}
d.tokens.Reset()
}
}
} else {
s.index++
d.byteAvailable = true
}
}
}
}
func (d *compressor) store() {
if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
d.err = d.writeStoredBlock(d.window[:d.windowEnd])
d.windowEnd = 0
}
}
// fillWindow will fill the buffer with data for huffman-only compression.
// The number of bytes copied is returned.
func (d *compressor) fillBlock(b []byte) int {
n := copy(d.window[d.windowEnd:], b)
d.windowEnd += n
return n
}
// storeHuff will compress and store the currently added data,
// if enough has been accumulated or we at the end of the stream.
// Any error that occurred will be in d.err
func (d *compressor) storeHuff() {
if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
sed -n '1,220p' flate/large_low_entropy_test.go
Chunk ID: 4890b6
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 276
Output:
package flate
import (
"bytes"
stdflate "compress/flate"
"io"
"testing"
)
func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
input := make([]byte, 1<<20)
var compressed bytes.Buffer
w, err := NewWriter(&compressed, BestCompression)
if err != nil {
t.Fatalf("NewWriter: %v", err)
}
if _, err := w.Write(input); err != nil {
t.Fatalf("Write: %v", err)
}
if err := w.Close(); err != nil {
t.Fatalf("Close: %v", err)
}
stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
stdOut, err := io.ReadAll(stdReader)
_ = stdReader.Close()
if err != nil {
t.Fatalf("standard reader rejected stream: %v", err)
}
if !bytes.Equal(stdOut, input) {
t.Fatalf("standard reader mismatch: got %d bytes, want %d", len(stdOut), len(input))
}
localReader := NewReader(bytes.NewReader(compressed.Bytes()))
localOut, err := io.ReadAll(localReader)
_ = localReader.Close()
if err != nil {
t.Fatalf("local reader rejected stream: %v", err)
}
if !bytes.Equal(localOut, input) {
t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
}
}
rg -n "func \(w \*huffmanBitWriter\) writeBlock|writeBlockDynamic|writeBlockHuff|storedSize|indexTokens|tokens" flate -g'*.go'
Chunk ID: ccc764
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 11418
Output:
Total output lines: 190
flate/level1.go:18:func (e *fastEncL1) Encode(dst *tokens, src []byte) {
flate/level1.go:136: dst.tokens[dst.n] = token(v)
flate/level1.go:165: dst.tokens[dst.n] = token(matchType | uint32(xl)<<lengthShift | xoffset)
flate/level6.go:11:func (e *fastEncL6) Encode(dst *tokens, src []byte) {
flate/level6.go:260: dst.tokens[dst.n] = token(v)
flate/level4.go:11:func (e *fastEncL4) Encode(dst *tokens, src []byte) {
flate/level4.go:143: dst.tokens[dst.n] = token(v)
flate/token_test.go:13:// loadTestTokens will load test tokens.
flate/token_test.go:15:func loadTestTokens(t testFatal) *tokens {
flate/token_test.go:16: b, err := os.ReadFile("testdata/tokens.bin")
flate/token_test.go:20: var tokens tokens
flate/token_test.go:21: err = tokens.FromVarInt(b)
flate/token_test.go:25: return &tokens
flate/token_test.go:28:func Test_tokens_EstimatedBits(t *testing.T) {
flate/token_test.go:35: wr.writeBlockDynamic(tok, true, nil, true)
flate/token_test.go:46:func Benchmark_tokens_EstimatedBits(b *testing.B) {
flate/deflate.go:43: // The maximum number of tokens we will encode at the time.
flate/deflate.go:119: blockStart int // window index where current tokens start
flate/deflate.go:122: // queued output tokens
flate/deflate.go:123: tokens tokens
flate/deflate.go:172:func (d *compressor) writeBlock(tok *tokens, index int, eof bool) error {
flate/deflate.go:180: d.w.writeBlockDynamic(tok, eof, window, d.sync)
flate/deflate.go:186:// writeBlockSkip writes the current block and uses the number of tokens
flate/deflate.go:189:func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
flate/deflate.go:196: d.w.writeBlockHuff(eof, window, d.sync)
flate/deflate.go:199: d.w.writeBlockDynamic(tok, eof, window, d.sync)
flate/deflate.go:224: d.fast.Encode(&d.tokens, b)
flate/deflate.go:225: d.tokens.Reset()
flate/deflate.go:448: d.tokens.AddLiteral(d.window[s.index-1])
flate/deflate.go:451: if d.tokens.n > 0 {
flate/deflate.go:452: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:455: d.tokens.Reset()
flate/deflate.go:508: // Emit tokens we "owe"
flate/deflate.go:510: d.tokens.AddLiteral(d.window[prevIndex+j])
flate/deflate.go:511: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:513: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:516: d.tokens.Reset()
flate/deflate.go:549: // Emit tokens we "owe"
flate/deflate.go:551: d.tokens.AddLiteral(d.window[prevIndex+j])
flate/deflate.go:552: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:554: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:557: d.tokens.Reset()
flate/deflate.go:581: d.tokens.AddMatch(uint32(prevLength-3), uint32(prevOffset-minOffsetSize))
flate/deflate.go:612: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:614: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:617: d.tokens.Reset()
flate/deflate.go:628: d.tokens.AddLiteral(d.window[s.index-1])
flate/deflate.go:629: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:630: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:633: d.tokens.Reset()
flate/deflate.go:645: d.tokens.AddLiteral(d.window[s.index-1])
flate/deflate.go:646: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:647: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:650: d.tokens.Reset()
flate/deflate.go:663: d.tokens.AddLiteral(d.window[s.index-1])
flate/deflate.go:666: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:667: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:670: d.tokens.Reset()
flate/deflate.go:703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:725: d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
flate/deflate.go:728: d.tokens.Reset()
flate/deflate.go:735: d.fast.Encode(&d.tokens, d.window[:d.windowEnd])
flate/deflate.go:737: if d.tokens.n == 0 {
flate/deflate.go:740: } else if int(d.tokens.n) > d.windowEnd-(d.windowEnd>>4) {
flate/deflate.go:741: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:744: d.w.writeBlockDynamic(&d.tokens, false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:747: d.tokens.Reset()
flate/deflate.go:836: d.tokens.Reset()
flate/deflate.go:855: d.tokens.Reset()
flate/token.go:130:type tokens struct {
flate/token.go:136: tokens [maxStoreBlockSize + 1]token
flate/token.go:139:func (t *tokens) Reset() {
flate/token.go:156:func (t *tokens) Fill() {
flate/token.go:179:func indexTokens(in []token) tokens {
flate/token.go:180: var t tokens
flate/token.go:181: t.indexTokens(in)
flate/token.go:185:func (t *tokens) indexTokens(in []token) {
flate/token.go:197:func emitLiteral(dst *tokens, lit []byte) {
flate/token.go:199: dst.tokens[dst.n] = token(v)
flate/token.go:205:func (t *tokens) AddLiteral(lit byte) {
flate/token.go:206: t.tokens[t.n] = token(lit)
flate/token.go:225:func (t *tokens) EstimatedBits() int {
flate/token.go:262:// AddMatch adds a match to the tokens.
flate/token.go:264:func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
flate/token.go:278: t.tokens[t.n] = token(matchType | xlength<<lengthShift | xoffset)
flate/token.go:282:// AddMatchLong adds a match to the tokens, potentially longer than max match length.
flate/token.go:284:func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
flate/token.go:306: t.tokens[t.n] = token(matchType | uint32(xl)<<lengthShift | xoffset)
flate/token.go:311:func (t *tokens) AddEOB() {
flate/token.go:312: t.tokens[t.n] = token(endBlockMarker)
flate/token.go:317:func (t *tokens) Slice() []token {
flate/token.go:318: return t.tokens[:t.n]
flate/token.go:321:// VarInt returns the tokens as varint encoded bytes.
flate/token.go:322:func (t *tokens) VarInt() []byte {
flate/token.go:325: for _, v := range t.tokens[:t.n] {
flate/token.go:331:// FromVarInt restores t to the varint encoded tokens provided.
flate/token.go:333:func (t *tokens) FromVarInt(b []byte) error {
flate/token.go:346: t.indexTokens(toks)
flate/level3.go:12:func (e *fastEncL3) Encode(dst *tokens, src []byte) {
flate/level3.go:151: dst.tokens[dst.n] = token(v)
flate/huffman_bit_writer.go:29: // maxPredefinedTokens is the maximum number of tokens
flate/huffman_bit_writer.go:163:func (w *huffmanBitWriter) canReuse(t *tokens) (ok bool) {
flate/huffman_bit_writer.go:408:// storedSize calculates the stored size, including header.
flate/huffman_bit_writer.go:411:func (w *huffmanBitWriter) storedSize(in []byte) (int, bool) {
flate/huffman_bit_writer.go:549:// writeBlock will write a block of tokens with the smallest encoding.
flate/huffman_bit_writer.go:553:// If the input is nil, the tokens will always be Huffman encoded.
flate/huffman_bit_writer.go:554:func (w *huffmanBitWriter) writeBlock(tokens *tokens, eof bool, input []byte) {
flate/huffman_bit_writer.go:559: tokens.AddEOB()
flate/huffman_bit_writer.go:565: numLiterals, numOffsets := w.indexTokens(tokens, false)
flate/huffman_bit_writer.go:568: storedSize, storable := w.storedSize(input)
flate/huffman_bit_writer.go:578: if tokens.n < maxPredefinedTokens {
flate/huffman_bit_writer.go:598: if storable && storedSize <= size {
flate/huffman_bit_writer.go:611: // Write the tokens.
flate/huffman_bit_writer.go:612: w.writeTokens(tokens.Slice(), literalEncoding.codes, offsetEncoding.codes)
flate/huffman_bit_writer.go:615:// writeBlockDynamic encodes a block using a dynamic Huffman table.
flate/huffman_bit_writer.go:620:func (w *huffmanBitWriter) writeBlockDynamic(tokens *tokens, eof bool, input []byte, sync bool) {
flate/huffman_bit_writer.go:627: tokens.AddEOB()
flate/huffman_bit_writer.go:644: if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
flate/huffman_bit_writer.go:649: numLiterals, numOffsets := w.indexTokens(tokens, fillReuse && !sync)
flate/huffman_bit_writer.go:651: ssize, storable := w.storedSize(input)
flate/huffman_bit_writer.go:664: newSize := w.lastHeader + tokens.EstimatedBits()
flate/huffman_bit_writer.go:681: if tokens.n < maxPredefinedTokens {
flate/huffman_bit_writer.go:691: tokens.AddEOB()
flate/huffman_bit_writer.go:693: w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
flate/huffman_bit_writer.go:723: w.indexTokens(tokens, true)
flate/huffman_bit_writer.go:728: if tokens.n < maxPredefinedTokens {
flate/huffman_bit_writer.go:738: tokens.AddEOB()
flate/huffman_bit_writer.go:740: w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
flate/huffman_bit_writer.go:763: // Write the tokens.
flate/huffman_bit_writer.go:764: w.writeTokens(tokens.Slice(), w.literalEncoding.codes, w.offsetEncoding.codes)
flate/huffman_bit_writer.go:780:// indexTokens indexes a slice of tokens, and updates
flate/huffman_bit_writer.go:783:// The number of literal and offset tokens is returned.
flate/huffman_bit_writer.go:784:func (w *huffmanBitWriter) indexTokens(t *tokens, filled bool) (numLiterals, numOffsets int) {
flate/huffman_bit_writer.go:821:// writeTokens writes a slice of tokens to the output.
flate/huffman_bit_writer.go:823:func (w *huffmanBitWriter) writeTokens(tokens []token, leCodes, oeCodes []hcode) {
flate/huffman_bit_writer.go:827: if len(tokens) == 0 {
flate/huffman_bit_writer.go:833: if tokens[len(tokens)-1] == endBlockMarker {
flate/huffman_bit_writer.go:834: tokens = tokens[:len(tokens)-1]
flate/huffman_bit_writer.go:847: for _, t := range tokens {
flate/huffman_bit_writer.go:983:// writeBlockHuff encodes a block of bytes as either
flate/huffman_bit_writer.go:986:func (w *huffmanBitWriter) writeBlockHuff(eof bool, input []byte, sync bool) {
flate/huffman_bit_writer.go:1010: ssize, storable := w.storedSize(input)
flate/fast_encoder.go:15: Encode(dst *tokens, src []byte)
flate/level2.go:15:func (e *fastEncL2) Encode(dst *tokens, src []byte) {
flate/level2.go:142: dst.tokens[dst.n] = token(v)
flate/level5.go:11:func (e *fastEncL5) Encode(dst *tokens, src []byte) {
flate/level5.go:225: dst.tokens[dst.n] = token(v)
flate/level5.go:322:func (e *fastEncL5Window) Encode(dst *tokens, src []byte) {
flate/level5.go:537: dst.tokens[dst.n] = token(v)
flate/deflate_test.go:511: if w.d.tokens.n != 0 {
flate/deflate_test.go:512: t.Errorf("level %d Writer not reset after Reset. %d tokens were present", level, w.d.tokens.n)
flate/deflate_test.go:515: w.d.tokens = wref.d.tokens
flate/huffman_bit_writer_test.go:50: bw.writeBlockHuff(false, all, false)
flate/huffman_bit_writer_test.go:85: bw.writeBlockHuff(false, all, false)
flate/huffman_bit_writer_test.go:100: tokens []token
flate/huffman_bit_writer_test.go:101: input string // File name of input data matching the tokens.
flate/huffman_bit_writer_test.go:113: tokens: []token{0x0, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, 0x0, 0x0},
flate/huffman_bit_writer_test.go:119: tokens: []token{0x33, 0x2e, 0x31, 0x34, 0x31, 0x35, 0x39, 0x32, 0x36, 0x35, 0x33, 0x35, 0x38, 0x39, 0x37, 0x39, 0x33, 0x32, 0x33, 0x38, 0x34, 0x36, 0x32, 0x36, 0x34, 0x33, 0x33, 0x38, 0x33, 0x32, 0x37, 0x39, 0x35, 0x30, 0x32, 0x38, 0x38, 0x34, 0x31, 0x39, 0x37, 0x31, 0x36, 0x39, 0x33, 0x39, 0x39, 0x33, 0x37, 0x35, 0x31, 0x30, 0x35, 0x38, 0x32, 0x30, 0x39, 0x37, 0x34, 0x39, 0x34, 0x34, 0x35, 0x39, 0x32, 0x33, 0x30, 0x37, 0x38, 0x31, 0x36, 0x34, 0x30, 0x36, 0x32, 0x38, 0x36, 0x32, 0x30, 0x38, 0x39, 0x39, 0x38, 0x36, 0x32, 0x38, 0x30, 0x33, 0x34, 0x38, 0x32, 0x35, 0x33, 0x34, 0x32, 0x31, 0x31, 0x37, 0x30, 0x36, 0x37, 0x39, 0x38, 0x32, 0x31, 0x34, 0x38, 0x30, 0x38, 0x36, 0x35, 0x31, 0x33, 0x32, 0x38, 0x32, 0x33, 0x30, 0x36, 0x36, 0x34, 0x37, 0x30, 0x39, 0x33, 0x38, 0x34, 0x34, 0x36, 0x30, 0x39, 0x35, 0x35, 0x30, 0x35, 0x38, 0x32, 0x32, 0x33, 0x31, 0x37, 0x32, 0x35, 0x33, 0x35, 0x39, 0x34, 0x30, 0x38, 0x31, 0x32, 0x38, 0x34, 0x38, 0x31, 0x31, 0x31, 0x37, 0x34, 0x4040007e, 0x34, 0x31, 0x30, 0x32, 0x37, 0x30, 0x31, 0x39, 0x33, 0x38, 0x35, 0x32, 0x31, 0x31, 0x30, 0x35, 0x35, 0x35, 0x39, 0x36, 0x34, 0x34, 0x36, 0x32, 0x32, 0x39, 0x34, 0x38, 0x39, 0x35, 0x34, 0x39, 0x33, 0x30, 0x33, 0x38, 0x31, 0x40400012, 0x32, 0x38, 0x38, 0x31, 0x30, 0x39, 0x37, 0x35, 0x36, 0x36, 0x35, 0x39, 0x33, 0x33, 0x34, 0x34, 0x36, 0x40400047, 0x37, 0x35, 0x36, 0x34, 0x38, 0x32, 0x33, 0x33, 0x37, 0x38, 0x36, 0x37, 0x38, 0x33, 0x31, 0x36, 0x35, 0x32, 0x37, 0x31, 0x32, 0x30, 0x31, 0x39, 0x30, 0x39, 0x31, 0x34, 0x4040001a, 0x35, 0x36, 0x36, 0x39, 0x32, 0x33, 0x34, 0x36, 0x404000b2, 0x36, 0x31, 0x30, 0x34, 0x35, 0x34, 0x33, 0x32, 0x36, 0x40400032, 0x31, 0x33, 0x33, 0x39, 0x33, 0x36, 0x30, 0x37, 0x32, 0x36, 0x30, 0x32, 0x34, 0x39, 0x31, 0x34, 0x31, 0x32, 0x37, 0x33, 0x37, 0x32, 0x34, 0x35, 0x38, 0x37, 0x30, 0x30, 0x36, 0x36, 0x30, 0x36, 0x33, 0x31, 0x35, 0x35, 0x38, 0x38, 0x31, 0x37, 0x34, 0x38, 0x38, 0x31, 0x35, 0x32, 0x30, 0x39, 0x32, 0x30, 0x39, 0x36, 0x32, 0x38, 0x32, 0x39, 0x32, 0x35, 0x34, 0x30, 0x39, 0x31, 0x37, 0x31, 0x35, 0x33, 0x36, 0x34, 0x33, 0x36, 0x37, 0x38, 0x39, 0x32, 0x35, 0x39, 0x30, 0x33, 0x36, 0x30, 0x30, 0x31, 0x31, 0x33, 0x33, 0x30, 0x35, 0x33, 0x30, 0x35, 0x34, 0x38, 0x38, 0x32, 0x30, 0x34, 0x36, 0x36, 0x35, 0x32, 0x31, 0x33, 0x38, 0x34, 0x31, 0x34, 0x36, 0x39, 0x35, 0x31, 0x39, 0x34, 0x31, 0x35, 0x31, 0x31, 0x36, 0x30, 0x39, 0x34, 0x33, 0x33, 0x30, 0x35, 0x37, 0x32, 0x37, 0x30, 0x33, 0x36, 0x35, 0x37, 0x35, 0x39, 0x35, 0x39, 0x31, 0x39, 0x35, 0x33, 0x30, 0x39, 0x32, 0x31, 0x38, 0x36, 0x31, 0x31, 0x37, 0x404000e9, 0x33, 0x32, 0x40400009, 0x39, 0x33, 0x31, 0x30, 0x35, 0x31, 0x31, 0x38, 0x35, 0x34, 0x38, 0x30, 0x37, 0x4040010e, 0x33, 0x37, 0x39, 0x39, 0x36, 0x32, 0x37, 0x34, 0x39, 0x35, 0x36, 0x37, 0x33, 0x35, 0x31, 0x38, 0x38, 0x35, 0x37, 0x35, 0x32, 0x37, 0x32, 0x34, 0x38, 0x39, 0x31, 0x32, 0x32, 0x37, 0x39, 0x33, 0x38, 0x31, 0x38, 0x33, 0x30, 0x31, 0x31, 0x39, 0x34, 0x39, 0x31, 0x32, 0x39, 0x38, 0x33, 0x33, 0x36, 0x37, 0x33, 0x33, 0x36, 0x32, 0x34, 0x34, 0x30, 0x36, 0x35, 0x36, 0x36, 0x34, 0x33, 0x30, 0x38, 0x36, 0x30, 0x32, 0x31, 0x33, 0x39, 0x34, 0x39, 0x34, 0x36, 0x33, 0x39, 0x35, 0x32, 0x32, 0x34, 0x37, 0x33, 0x37, 0x31, 0x39, 0x30, 0x37, 0x30, 0x32, 0x31, 0x37, 0x39, 0x38, 0x40800099, 0x37, 0x30, 0x32, 0x37, 0x37, 0x30, 0x35, 0x33, 0x39, 0x32, 0x31, 0x37, 0x31, 0x37, 0x36, 0x32, 0x39, 0x33, 0x31, 0x37, 0x36, 0x37, 0x35, 0x40800232, 0x37, 0x34, 0x38, 0x31, 0x40400006, 0x36, 0x36, 0x39, 0x34, 0x30, 0x404001e7, 0x30, 0x30, 0x30, 0x35, 0x36, 0x38, 0x31, 0x32, 0x37, 0x31, 0x34, 0x35, 0x32, 0x36, 0x33, 0x35, 0x36, 0x30, 0x38, 0x32, 0x37, 0x37, 0x38, 0x35, 0x37, 0x37, 0x31, 0x33, 0x34, 0x32, 0x37, 0x35, 0x37, 0x37, 0x38, 0x39, 0x36, 0x40400129, 0x33, 0x36, 0x33, 0x37, 0x31, 0x37, 0x38, 0x37, 0x32, 0x31, 0x34, 0x36, 0x38, 0x34, 0x34, 0x30, 0x39, 0x30, 0x31, 0x32, 0x32, 0x34, 0x39, 0x35, 0x33, 0x34, 0x33, 0x30, 0x31, 0x34, 0x36, 0x35, 0x34, 0x39, 0x35, 0x38, 0x35, 0x33, 0x37, 0x31, 0x30, 0x35, 0x30, 0x37, 0x39, 0x404000ca, 0x36, 0x40400153, 0x38, 0x39, 0x32, 0x33, 0x35, 0x34, 0x404001c9, 0x39, 0x35, 0x36, 0x31, 0x31, 0x32, 0x31, 0x32, 0x39, 0x30, 0x32, 0x31, 0x39, 0x36, 0x30, 0x38, 0x36, 0x34, 0x30, 0x33, 0x34, 0x34, 0x31, 0x38, 0x31, 0x35, 0x39, 0x38, 0x31, 0x33, 0x36, 0x32, 0x39, 0x37, 0x37, 0x34, 0x40400074, 0x30, 0x39, 0x39, 0x36, 0x30, 0x35, 0x31, 0x38, 0x37, 0x30, 0x37, 0x32, 0x31, 0x31, 0x33, 0x34, 0x39, 0x40800000, 0x38, 0x33, 0x37, 0x32, 0x39, 0x37, 0x38, 0x30, 0x34, 0x39, 0x39, 0x404002da, 0x39, 0x37, 0x33, 0x31, 0x37, 0x33, 0x32, 0x38, 0x4040018a, 0x36, 0x33, 0x31, 0x38, 0x35, 0x40400301, 0x404002e8, 0x34, 0x35, 0x35, 0x33, 0x34, 0x36, 0x39, 0x30, 0x38, 0x33, 0x30, 0x32, 0x36, 0x34, 0x32, 0x35, 0x32, 0x32, 0x33, 0x30, 0x404002e3, 0x40400267, 0x38, 0x35, 0x30, 0x33, 0x35, 0x32, 0x36, 0x31, 0x39, 0x33, 0x31, 0x31, 0x40400212, 0x31, 0x30, 0x31, 0x30, 0x30, 0x30, 0x33, 0x31, 0x33, 0x37, 0x38, 0x33, 0x38, 0x37, 0x35, 0x32, 0x38, 0x38, 0x36, 0x35, 0x38, 0x37, 0x35, 0x33, 0x33, 0x32, 0x30, 0x38, 0x33, 0x38, 0x31, 0x34, 0x32, 0x30, 0x36, 0x40400140, 0x4040012b, 0x31, 0x34, 0x37, 0x33, 0x30, 0x33, 0x35, 0x39, 0x4080032e, 0x39, 0x30, 0x34, 0x32, 0x38, 0x37, 0x35, 0x35, 0x34, 0x36, 0x38, 0x37, 0x33, 0x31, 0x31, 0x35, 0x39, 0x35, 0x40400355, 0x33, 0x38, 0x38, 0x32, 0x33, 0x35, 0x33, 0x37, 0x38, 0x37, 0x35, 0x4080037f, 0x39, 0x4040013a, 0x31, 0x40400148, 0x38, 0x30, 0x35, 0x33, 0x4040018a, 0x32, 0x32, 0x36, 0x38, 0x30, 0x36, 0x36, 0x31, 0x33, 0x30, 0x30, 0x31, 0x39, 0x32, 0x37, 0x38, 0x37, 0x36, 0x36, 0x31, 0x31, 0x31, 0x39, 0x35, 0x39, 0x40400237, 0x36, 0x40800124, 0x38, 0x39, 0x33, 0x38, 0x30, 0x39, 0x35, 0x32, 0x35, 0x37, 0x32, 0x30, 0x31, 0x30, 0x36, 0x35, 0x34, 0x38, 0x35, 0x38, 0x36, 0x33, 0x32, 0x37, 0x4040009a, 0x39, 0x33, 0x36, 0x31, 0x35, 0x33, 0x40400220, 0x4080015c, 0x32, 0x33, 0x30, 0x33, 0x30, 0x31, 0x39, 0x35, 0x32, 0x30, 0x33, 0x35, 0x33, 0x30, 0x31, 0x38, 0x35, 0x32, 0x40400171, 0x40400075, 0x33, 0x36, 0x32, 0x32, 0x35, 0x39, 0x39, 0x34, 0x31, 0x33, 0x40400254, 0x34, 0x39, 0x37, 0x32, 0x31, 0x37, 0x404000de, 0x33, 0x34, 0x37, 0x39, 0x31, 0x33, 0x31, 0x35, 0x31, 0x35, 0x35, 0x37, 0x34, 0x38, 0x35, 0x37, 0x32, 0x34, 0x32, 0x34, 0x35, 0x34, 0x31, 0x35, 0x30, 0x36, 0x39, 0x4040013f, 0x38, 0x32, 0x39, 0x35, 0x33, 0x33, 0x31, 0x31, 0x36, 0x38, 0x36, 0x31, 0x37, 0x32, 0x37, 0x38, 0x40400337, 0x39, 0x30, 0x37, 0x35, 0x30, 0x39, 0x4040010d, 0x37, 0x35, 0x34, 0x36, 0x33, 0x37, 0x34, 0x36, 0x34, 0x39, 0x33, 0x39, 0x33, 0x31, 0x39, 0x32, 0x35, 0x35, 0x30, 0x36, 0x30, 0x34, 0x30, 0x30, 0x39, 0x4040026b, 0x31, 0x36, 0x37, 0x31, 0x31, 0x33, 0x39, 0x30, 0x30, 0x39, 0x38, 0x40400335, 0x34, 0x30, 0x31, 0x32, 0x38, 0x35, 0x38, 0x33, 0x36, 0x31, 0x36, 0x30, 0x33, 0x35, 0x36, 0x33, 0x37, 0x30, 0x37, 0x36, 0x36, 0x30, 0x31, 0x30, 0x34, 0x40400172, 0x38, 0x31, 0x39, 0x34, 0x32, 0x39, 0x4080041e, 0x404000ef, 0x4040028b, 0x37, 0x38, 0x33, 0x37, 0x34, 0x404004a8, 0x38, 0x32, 0x35, 0x35, 0x33, 0x37, 0x40800209, 0x32, 0x36, 0x38, 0x4040002e, 0x34, 0x30, 0x34, 0x37, 0x404001d1, 0x34, 0x404004b5, 0x4040038d, 0x38, 0x34, 0x404003a8, 0x36, 0x40c0031f, 0x33, 0x33, 0x31, 0x33, 0x36, 0x37, 0x37, 0x30, 0x32, 0x38, 0x39, 0x38, 0x39, 0x31, 0x35, 0x32, 0x40400062, 0x35, 0x32, 0x31, 0x36, 0x32, 0x30, 0x35, 0x36, 0x39, 0x36, 0x40400411, 0x30, 0x35, 0x38, 0x40400477, 0x35, 0x40400498, 0x35, 0x31, 0x31, 0x40400209, 0x38, 0x32, 0x34, 0x33, 0x30, 0x30, 0x33, 0x35, 0x35, 0x38, 0x37, 0x36, 0x34, 0x30, 0x32, 0x34, 0x37, 0x34, 0x39, 0x36, 0x34, 0x37, 0x33, 0x32, 0x36, 0x33, 0x4040043e, 0x39, 0x39, 0x32, 0x4040044b, 0x34, 0x32, 0x36, 0x39, 0x40c002c5, 0x37, 0x404001d6, 0x34, 0x4040053d, 0x4040041d, 0x39, 0x33, 0x34, 0x31, 0x37, 0x404001ad, 0x31, 0x32, 0x4040002a, 0x34, 0x4040019e, 0x31, 0x35, 0x30, 0x33, 0x30, 0x32, 0x38, 0x36, 0x31, 0x38, 0x32, 0x39, 0x37, 0x34, 0x35, 0x35, 0x35, 0x37, 0x30, 0x36, 0x37, 0x34, 0x40400135, 0x35, 0x30, 0x35, 0x34, 0x39, 0…1418 tokens truncated…0x32, 0x33, 0x34, 0x33, 0x36, 0x34, 0x35, 0x34, 0x404005de, 0x34, 0x34, 0x34, 0x37, 0x39, 0x35, 0x4040003c, 0x40400523, 0x408008e6, 0x34, 0x31, 0x4040052a, 0x33, 0x40400304, 0x35, 0x32, 0x33, 0x31, 0x40800841, 0x31, 0x36, 0x36, 0x31, 0x404008b2, 0x35, 0x39, 0x36, 0x39, 0x35, 0x33, 0x36, 0x32, 0x33, 0x31, 0x34, 0x404005ff, 0x32, 0x34, 0x38, 0x34, 0x39, 0x33, 0x37, 0x31, 0x38, 0x37, 0x31, 0x31, 0x30, 0x31, 0x34, 0x35, 0x37, 0x36, 0x35, 0x34, 0x40400761, 0x30, 0x32, 0x37, 0x39, 0x39, 0x33, 0x34, 0x34, 0x30, 0x33, 0x37, 0x34, 0x32, 0x30, 0x30, 0x37, 0x4040093f, 0x37, 0x38, 0x35, 0x33, 0x39, 0x30, 0x36, 0x32, 0x31, 0x39, 0x40800299, 0x40400345, 0x38, 0x34, 0x37, 0x408003d2, 0x38, 0x33, 0x33, 0x32, 0x31, 0x34, 0x34, 0x35, 0x37, 0x31, 0x40400284, 0x40400776, 0x34, 0x33, 0x35, 0x30, 0x40400928, 0x40400468, 0x35, 0x33, 0x31, 0x39, 0x31, 0x30, 0x34, 0x38, 0x34, 0x38, 0x31, 0x30, 0x30, 0x35, 0x33, 0x37, 0x30, 0x36, 0x404008bc, 0x4080059d, 0x40800781, 0x31, 0x40400559, 0x37, 0x4040031b, 0x35, 0x404007ec, 0x4040040c, 0x36, 0x33, 0x408007dc, 0x34, 0x40400971, 0x4080034e, 0x408003f5, 0x38, 0x4080052d, 0x40800887, 0x39, 0x40400187, 0x39, 0x31, 0x404008ce, 0x38, 0x31, 0x34, 0x36, 0x37, 0x35, 0x31, 0x4040062b, 0x31, 0x32, 0x33, 0x39, 0x40c001a9, 0x39, 0x30, 0x37, 0x31, 0x38, 0x36, 0x34, 0x39, 0x34, 0x32, 0x33, 0x31, 0x39, 0x36, 0x31, 0x35, 0x36, 0x404001ec, 0x404006bc, 0x39, 0x35, 0x40400926, 0x40400469, 0x4040011b, 0x36, 0x30, 0x33, 0x38, 0x40400a25, 0x4040016f, 0x40400384, 0x36, 0x32, 0x4040045a, 0x35, 0x4040084c, 0x36, 0x33, 0x38, 0x39, 0x33, 0x37, 0x37, 0x38, 0x37, 0x404008c5, 0x404000f8, 0x39, 0x37, 0x39, 0x32, 0x30, 0x37, 0x37, 0x33, 0x404005d7, 0x32, 0x31, 0x38, 0x32, 0x35, 0x36, 0x404007df, 0x36, 0x36, 0x404006d6, 0x34, 0x32, 0x4080067e, 0x36, 0x404006e6, 0x34, 0x34, 0x40400024, 0x35, 0x34, 0x39, 0x32, 0x30, 0x32, 0x36, 0x30, 0x35, 0x40400ab3, 0x408003e4, 0x32, 0x30, 0x31, 0x34, 0x39, 0x404004d2, 0x38, 0x35, 0x30, 0x37, 0x33, 0x40400599, 0x36, 0x36, 0x36, 0x30, 0x40400194, 0x32, 0x34, 0x33, 0x34, 0x30, 0x40400087, 0x30, 0x4040076b, 0x38, 0x36, 0x33, 0x40400956, 0x404007e4, 0x4040042b, 0x40400174, 0x35, 0x37, 0x39, 0x36, 0x32, 0x36, 0x38, 0x35, 0x36, 0x40400140, 0x35, 0x30, 0x38, 0x40400523, 0x35, 0x38, 0x37, 0x39, 0x36, 0x39, 0x39, 0x40400711, 0x35, 0x37, 0x34, 0x40400a18, 0x38, 0x34, 0x30, 0x404008b3, 0x31, 0x34, 0x35, 0x39, 0x31, 0x4040078c, 0x37, 0x30, 0x40400234, 0x30, 0x31, 0x40400be7, 0x31, 0x32, 0x40400c74, 0x30, 0x404003c3, 0x33, 0x39, 0x40400b2a, 0x40400112, 0x37, 0x31, 0x35, 0x404003b0, 0x34, 0x32, 0x30, 0x40800bf2, 0x39, 0x40400bc2, 0x30, 0x37, 0x40400341, 0x40400795, 0x40400aaf, 0x40400c62, 0x32, 0x31, 0x40400960, 0x32, 0x35, 0x31, 0x4040057b, 0x40400944, 0x39, 0x32, 0x404001b2, 0x38, 0x32, 0x36, 0x40400b66, 0x32, 0x40400278, 0x33, 0x32, 0x31, 0x35, 0x37, 0x39, 0x31, 0x39, 0x38, 0x34, 0x31, 0x34, 0x4080087b, 0x39, 0x31, 0x36, 0x34, 0x408006e8, 0x39, 0x40800b58, 0x404008db, 0x37, 0x32, 0x32, 0x40400321, 0x35, 0x404008a4, 0x40400141, 0x39, 0x31, 0x30, 0x404000bc, 0x40400c5b, 0x35, 0x32, 0x38, 0x30, 0x31, 0x37, 0x40400231, 0x37, 0x31, 0x32, 0x40400914, 0x38, 0x33, 0x32, 0x40400373, 0x31, 0x40400589, 0x30, 0x39, 0x33, 0x35, 0x33, 0x39, 0x36, 0x35, 0x37, 0x4040064b, 0x31, 0x30, 0x38, 0x33, 0x40400069, 0x35, 0x31, 0x4040077a, 0x40400d5a, 0x31, 0x34, 0x34, 0x34, 0x32, 0x31, 0x30, 0x30, 0x40400202, 0x30, 0x33, 0x4040019c, 0x31, 0x31, 0x30, 0x33, 0x40400c81, 0x40400009, 0x40400026, 0x40c00602, 0x35, 0x31, 0x36, 0x404005d9, 0x40800883, 0x4040092a, 0x35, 0x40800c42, 0x38, 0x35, 0x31, 0x37, 0x31, 0x34, 0x33, 0x37, 0x40400605, 0x4040006d, 0x31, 0x35, 0x35, 0x36, 0x35, 0x30, 0x38, 0x38, 0x404003b9, 0x39, 0x38, 0x39, 0x38, 0x35, 0x39, 0x39, 0x38, 0x32, 0x33, 0x38, 0x404001cf, 0x404009ba, 0x33, 0x4040016c, 0x4040043e, 0x404009c3, 0x38, 0x40800e05, 0x33, 0x32, 0x40400107, 0x35, 0x40400305, 0x33, 0x404001ca, 0x39, 0x4040041b, 0x39, 0x38, 0x4040087d, 0x34, 0x40400cb8, 0x37, 0x4040064b, 0x30, 0x37, 0x404000e5, 0x34, 0x38, 0x31, 0x34, 0x31, 0x40400539, 0x38, 0x35, 0x39, 0x34, 0x36, 0x31, 0x40400bc9, 0x38, 0x30},
flate/huffman_bit_writer_test.go:125: tokens: []token{0xf8, 0x8b, 0x96, 0x76, 0x48, 0xd, 0x85, 0x94, 0x25, 0x80, 0xaf, 0xc2, 0xfe, 0x8d, 0xe8, 0x20, 0xeb, 0x17, 0x86, 0xc9, 0xb7, 0xc5, 0xde, 0x6, 0xea, 0x7d, 0x18, 0x8b, 0xe7, 0x3e, 0x7, 0xda, 0xdf, 0xff, 0x6c, 0x73, 0xde, 0xcc, 0xe7, 0x6d, 0x8d, 0x4, 0x19, 0x49, 0x7f, 0x47, 0x1f, 0x48, 0x15, 0xb0, 0xe8, 0x9e, 0xf2, 0x31, 0x59, 0xde, 0x34, 0xb4, 0x5b, 0xe5, 0xe0, 0x9, 0x11, 0x30, 0xc2, 0x88, 0x5b, 0x7c, 0x5d, 0x14, 0x13, 0x6f, 0x23, 0xa9, 0xd, 0xbc, 0x2d, 0x23, 0xbe, 0xd9, 0xed, 0x75, 0x4, 0x6c, 0x99, 0xdf, 0xfd, 0x70, 0x66, 0xe6, 0xee, 0xd9, 0xb1, 0x9e, 0x6e, 0x83, 0x59, 0xd5, 0xd4, 0x80, 0x59, 0x98, 0x77, 0x89, 0x43, 0x38, 0xc9, 0xaf, 0x30, 0x32, 0x9a, 0x20, 0x1b, 0x46, 0x3d, 0x67, 0x6e, 0xd7, 0x72, 0x9e, 0x4e, 0x21, 0x4f, 0xc6, 0xe0, 0xd4, 0x7b, 0x4, 0x8d, 0xa5, 0x3, 0xf6, 0x5, 0x9b, 0x6b, 0xdc, 0x2a, 0x93, 0x77, 0x28, 0xfd, 0xb4, 0x62, 0xda, 0x20, 0xe7, 0x1f, 0xab, 0x6b, 0x51, 0x43, 0x39, 0x2f, 0xa0, 0x92, 0x1, 0x6c, 0x75, 0x3e, 0xf4, 0x35, 0xfd, 0x43, 0x2e, 0xf7, 0xa4, 0x75, 0xda, 0xea, 0x9b, 0xa, 0x64, 0xb, 0xe0, 0x23, 0x29, 0xbd, 0xf7, 0xe7, 0x83, 0x3c, 0xfb, 0xdf, 0xb3, 0xae, 0x4f, 0xa4, 0x47, 0x55, 0x99, 0xde, 0x2f, 0x96, 0x6e, 0x1c, 0x43, 0x4c, 0x87, 0xe2, 0x7c, 0xd9, 0x5f, 0x4c, 0x7c, 0xe8, 0x90, 0x3, 0xdb, 0x30, 0x95, 0xd6, 0x22, 0xc, 0x47, 0xb8, 0x4d, 0x6b, 0xbd, 0x24, 0x11, 0xab, 0x2c, 0xd7, 0xbe, 0x6e, 0x7a, 0xd6, 0x8, 0xa3, 0x98, 0xd8, 0xdd, 0x15, 0x6a, 0xfa, 0x93, 0x30, 0x1, 0x25, 0x1d, 0xa2, 0x74, 0x86, 0x4b, 0x6a, 0x95, 0xe8, 0xe1, 0x4e, 0xe, 0x76, 0xb9, 0x49, 0xa9, 0x5f, 0xa0, 0xa6, 0x63, 0x3c, 0x7e, 0x7e, 0x20, 0x13, 0x4f, 0xbb, 0x66, 0x92, 0xb8, 0x2e, 0xa4, 0xfa, 0x48, 0xcb, 0xae, 0xb9, 0x3c, 0xaf, 0xd3, 0x1f, 0xe1, 0xd5, 0x8d, 0x42, 0x6d, 0xf0, 0xfc, 0x8c, 0xc, 0x0, 0xde, 0x40, 0xab, 0x8b, 0x47, 0x97, 0x4e, 0xa8, 0xcf, 0x8e, 0xdb, 0xa6, 0x8b, 0x20, 0x9, 0x84, 0x7a, 0x66, 0xe5, 0x98, 0x29, 0x2, 0x95, 0xe6, 0x38, 0x32, 0x60, 0x3, 0xe3, 0x9a, 0x1e, 0x54, 0xe8, 0x63, 0x80, 0x48, 0x9c, 0xe7, 0x63, 0x33, 0x6e, 0xa0, 0x65, 0x83, 0xfa, 0xc6, 0xba, 0x7a, 0x43, 0x71, 0x5, 0xf5, 0x68, 0x69, 0x85, 0x9c, 0xba, 0x45, 0xcd, 0x6b, 0xb, 0x19, 0xd1, 0xbb, 0x7f, 0x70, 0x85, 0x92, 0xd1, 0xb4, 0x64, 0x82, 0xb1, 0xe4, 0x62, 0xc5, 0x3c, 0x46, 0x1f, 0x92, 0x31, 0x1c, 0x4e, 0x41, 0x77, 0xf7, 0xe7, 0x87, 0xa2, 0xf, 0x6e, 0xe8, 0x92, 0x3, 0x6b, 0xa, 0xe7, 0xa9, 0x3b, 0x11, 0xda, 0x66, 0x8a, 0x29, 0xda, 0x79, 0xe1, 0x64, 0x8d, 0xe3, 0x54, 0xd4, 0xf5, 0xef, 0x64, 0x87, 0x3b, 0xf4, 0xc2, 0xf4, 0x71, 0x13, 0xa9, 0xe9, 0xe0, 0xa2, 0x6, 0x14, 0xab, 0x5d, 0xa7, 0x96, 0x0, 0xd6, 0xc3, 0xcc, 0x57, 0xed, 0x39, 0x6a, 0x25, 0xcd, 0x76, 0xea, 0xba, 0x3a, 0xf2, 0xa1, 0x95, 0x5d, 0xe5, 0x71, 0xcf, 0x9c, 0x62, 0x9e, 0x6a, 0xfa, 0xd5, 0x31, 0xd1, 0xa8, 0x66, 0x30, 0x33, 0xaa, 0x51, 0x17, 0x13, 0x82, 0x99, 0xc8, 0x14, 0x60, 0x9f, 0x4d, 0x32, 0x6d, 0xda, 0x19, 0x26, 0x21, 0xdc, 0x7e, 0x2e, 0x25, 0x67, 0x72, 0xca, 0xf, 0x92, 0xcd, 0xf6, 0xd6, 0xcb, 0x97, 0x8a, 0x33, 0x58, 0x73, 0x70, 0x91, 0x1d, 0xbf, 0x28, 0x23, 0xa3, 0xc, 0xf1, 0x83, 0xc3, 0xc8, 0x56, 0x77, 0x68, 0xe3, 0x82, 0xba, 0xb9, 0x57, 0x56, 0x57, 0x9c, 0xc3, 0xd6, 0x14, 0x5, 0x3c, 0xb1, 0xaf, 0x93, 0xc8, 0x8a, 0x57, 0x7f, 0x53, 0xfa, 0x2f, 0xaa, 0x6e, 0x66, 0x83, 0xfa, 0x33, 0xd1, 0x21, 0xab, 0x1b, 0x71, 0xb4, 0x7c, 0xda, 0xfd, 0xfb, 0x7f, 0x20, 0xab, 0x5e, 0xd5, 0xca, 0xfd, 0xdd, 0xe0, 0xee, 0xda, 0xba, 0xa8, 0x27, 0x99, 0x97, 0x69, 0xc1, 0x3c, 0x82, 0x8c, 0xa, 0x5c, 0x2d, 0x5b, 0x88, 0x3e, 0x34, 0x35, 0x86, 0x37, 0x46, 0x79, 0xe1, 0xaa, 0x19, 0xfb, 0xaa, 0xde, 0x15, 0x9, 0xd, 0x1a, 0x57, 0xff, 0xb5, 0xf, 0xf3, 0x2b, 0x5a, 0x6a, 0x4d, 0x19, 0x77, 0x71, 0x45, 0xdf, 0x4f, 0xb3, 0xec, 0xf1, 0xeb, 0x18, 0x53, 0x3e, 0x3b, 0x47, 0x8, 0x9a, 0x73, 0xa0, 0x5c, 0x8c, 0x5f, 0xeb, 0xf, 0x3a, 0xc2, 0x43, 0x67, 0xb4, 0x66, 0x67, 0x80, 0x58, 0xe, 0xc1, 0xec, 0x40, 0xd4, 0x22, 0x94, 0xca, 0xf9, 0xe8, 0x92, 0xe4, 0x69, 0x38, 0xbe, 0x67, 0x64, 0xca, 0x50, 0xc7, 0x6, 0x67, 0x42, 0x6e, 0xa3, 0xf0, 0xb7, 0x6c, 0xf2, 0xe8, 0x5f, 0xb1, 0xaf, 0xe7, 0xdb, 0xbb, 0x77, 0xb5, 0xf8, 0xcb, 0x8, 0xc4, 0x75, 0x7e, 0xc0, 0xf9, 0x1c, 0x7f, 0x3c, 0x89, 0x2f, 0xd2, 0x58, 0x3a, 0xe2, 0xf8, 0x91, 0xb6, 0x7b, 0x24, 0x27, 0xe9, 0xae, 0x84, 0x8b, 0xde, 0x74, 0xac, 0xfd, 0xd9, 0xb7, 0x69, 0x2a, 0xec, 0x32, 0x6f, 0xf0, 0x92, 0x84, 0xf1, 0x40, 0xc, 0x8a, 0xbc, 0x39, 0x6e, 0x2e, 0x73, 0xd4, 0x6e, 0x8a, 0x74, 0x2a, 0xdc, 0x60, 0x1f, 0xa3, 0x7, 0xde, 0x75, 0x8b, 0x74, 0xc8, 0xfe, 0x63, 0x75, 0xf6, 0x3d, 0x63, 0xac, 0x33, 0x89, 0xc3, 0xf0, 0xf8, 0x2d, 0x6b, 0xb4, 0x9e, 0x74, 0x8b, 0x5c, 0x33, 0xb4, 0xca, 0xa8, 0xe4, 0x99, 0xb6, 0x90, 0xa1, 0xef, 0xf, 0xd3, 0x61, 0xb2, 0xc6, 0x1a, 0x94, 0x7c, 0x44, 0x55, 0xf4, 0x45, 0xff, 0x9e, 0xa5, 0x5a, 0xc6, 0xa0, 0xe8, 0x2a, 0xc1, 0x8d, 0x6f, 0x34, 0x11, 0xb9, 0xbe, 0x4e, 0xd9, 0x87, 0x97, 0x73, 0xcf, 0x3d, 0x23, 0xae, 0xd5, 0x1a, 0x5e, 0xae, 0x5d, 0x6a, 0x3, 0xf9, 0x22, 0xd, 0x10, 0xd9, 0x47, 0x69, 0x15, 0x3f, 0xee, 0x52, 0xa3, 0x8, 0xd2, 0x3c, 0x51, 0xf4, 0xf8, 0x9d, 0xe4, 0x98, 0x89, 0xc8, 0x67, 0x39, 0xd5, 0x5e, 0x35, 0x78, 0x27, 0xe8, 0x3c, 0x80, 0xae, 0x79, 0x71, 0xd2, 0x93, 0xf4, 0xaa, 0x51, 0x12, 0x1c, 0x4b, 0x1b, 0xe5, 0x6e, 0x15, 0x6f, 0xe4, 0xbb, 0x51, 0x9b, 0x45, 0x9f, 0xf9, 0xc4, 0x8c, 0x2a, 0xfb, 0x1a, 0xdf, 0x55, 0xd3, 0x48, 0x93, 0x27, 0x1, 0x26, 0xc2, 0x6b, 0x55, 0x6d, 0xa2, 0xfb, 0x84, 0x8b, 0xc9, 0x9e, 0x28, 0xc2, 0xef, 0x1a, 0x24, 0xec, 0x9b, 0xae, 0xbd, 0x60, 0xe9, 0x15, 0x35, 0xee, 0x42, 0xa4, 0x33, 0x5b, 0xfa, 0xf, 0xb6, 0xf7, 0x1, 0xa6, 0x2, 0x4c, 0xca, 0x90, 0x58, 0x3a, 0x96, 0x41, 0xe7, 0xcb, 0x9, 0x8c, 0xdb, 0x85, 0x4d, 0xa8, 0x89, 0xf3, 0xb5, 0x8e, 0xfd, 0x75, 0x5b, 0x4f, 0xed, 0xde, 0x3f, 0xeb, 0x38, 0xa3, 0xbe, 0xb0, 0x73, 0xfc, 0xb8, 0x54, 0xf7, 0x4c, 0x30, 0x67, 0x2e, 0x38, 0xa2, 0x54, 0x18, 0xba, 0x8, 0xbf, 0xf2, 0x39, 0xd5, 0xfe, 0xa5, 0x41, 0xc6, 0x66, 0x66, 0xba, 0x81, 0xef, 0x67, 0xe4, 0xe6, 0x3c, 0xc, 0xca, 0xa4, 0xa, 0x79, 0xb3, 0x57, 0x8b, 0x8a, 0x75, 0x98, 0x18, 0x42, 0x2f, 0x29, 0xa3, 0x82, 0xef, 0x9f, 0x86, 0x6, 0x23, 0xe1, 0x75, 0xfa, 0x8, 0xb1, 0xde, 0x17, 0x4a},
flate/huffman_bit_writer_test.go:131: tokens: []token{0x61, 0x51c00000, 0xa, 0xf8, 0x8b, 0x96, 0x76, 0x48, 0xa, 0x85, 0x94, 0x25, 0x80, 0xaf, 0xc2, 0xfe, 0x8d, 0xe8, 0x20, 0xeb, 0x17, 0x86, 0xc9, 0xb7, 0xc5, 0xde, 0x6, 0xea, 0x7d, 0x18, 0x8b, 0xe7, 0x3e, 0x7, 0xda, 0xdf, 0xff, 0x6c, 0x73, 0xde, 0xcc, 0xe7, 0x6d, 0x8d, 0x4, 0x19, 0x49, 0x7f, 0x47, 0x1f, 0x48, 0x15, 0xb0, 0xe8, 0x9e, 0xf2, 0x31, 0x59, 0xde, 0x34, 0xb4, 0x5b, 0xe5, 0xe0, 0x9, 0x11, 0x30, 0xc2, 0x88, 0x5b, 0x7c, 0x5d, 0x14, 0x13, 0x6f, 0x23, 0xa9, 0xa, 0xbc, 0x2d, 0x23, 0xbe, 0xd9, 0xed, 0x75, 0x4, 0x6c, 0x99, 0xdf, 0xfd, 0x70, 0x66, 0xe6, 0xee, 0xd9, 0xb1, 0x9e, 0x6e, 0x83, 0x59, 0xd5, 0xd4, 0x80, 0x59, 0x98, 0x77, 0x89, 0x43, 0x38, 0xc9, 0xaf, 0x30, 0x32, 0x9a, 0x20, 0x1b, 0x46, 0x3d, 0x67, 0x6e, 0xd7, 0x72, 0x9e, 0x4e, 0x21, 0x4f, 0xc6, 0xe0, 0xd4, 0x7b, 0x4, 0x8d, 0xa5, 0x3, 0xf6, 0x5, 0x9b, 0x6b, 0xdc, 0x2a, 0x93, 0x77, 0x28, 0xfd, 0xb4, 0x62, 0xda, 0x20, 0xe7, 0x1f, 0xab, 0x6b, 0x51, 0x43, 0x39, 0x2f, 0xa0, 0x92, 0x1, 0x6c, 0x75, 0x3e, 0xf4, 0x35, 0xfd, 0x43, 0x2e, 0xf7, 0xa4, 0x75, 0xda, 0xea, 0x9b, 0xa},
flate/huffman_bit_writer_test.go:137: tokens: []token{0x31, 0x30, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x52400001, 0xd, 0xa, 0x32, 0x33, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7f400001},
flate/huffman_bit_writer_test.go:143: tokens: []token{0x2f, 0x2f, 0x43, 0x6f, 0x70, 0x79, 0x72, 0x69, 0x67, 0x68, 0x74, 0x32, 0x30, 0x30, 0x39, 0x54, 0x68, 0x47, 0x6f, 0x41, 0x75, 0x74, 0x68, 0x6f, 0x72, 0x2e, 0x41, 0x6c, 0x6c, 0x40800016, 0x72, 0x72, 0x76, 0x64, 0x2e, 0xd, 0xa, 0x2f, 0x2f, 0x55, 0x6f, 0x66, 0x74, 0x68, 0x69, 0x6f, 0x75, 0x72, 0x63, 0x63, 0x6f, 0x64, 0x69, 0x67, 0x6f, 0x76, 0x72, 0x6e, 0x64, 0x62, 0x79, 0x42, 0x53, 0x44, 0x2d, 0x74, 0x79, 0x6c, 0x40400020, 0x6c, 0x69, 0x63, 0x6e, 0x74, 0x68, 0x74, 0x63, 0x6e, 0x62, 0x66, 0x6f, 0x75, 0x6e, 0x64, 0x69, 0x6e, 0x74, 0x68, 0x4c, 0x49, 0x43, 0x45, 0x4e, 0x53, 0x45, 0x66, 0x69, 0x6c, 0x2e, 0xd, 0xa, 0xd, 0xa, 0x70, 0x63, 0x6b, 0x67, 0x6d, 0x69, 0x6e, 0x4040000a, 0x69, 0x6d, 0x70, 0x6f, 0x72, 0x74, 0x22, 0x6f, 0x22, 0x4040000c, 0x66, 0x75, 0x6e, 0x63, 0x6d, 0x69, 0x6e, 0x28, 0x29, 0x7b, 0xd, 0xa, 0x9, 0x76, 0x72, 0x62, 0x3d, 0x6d, 0x6b, 0x28, 0x5b, 0x5d, 0x62, 0x79, 0x74, 0x2c, 0x36, 0x35, 0x35, 0x33, 0x35, 0x29, 0xd, 0xa, 0x9, 0x66, 0x2c, 0x5f, 0x3a, 0x3d, 0x6f, 0x2e, 0x43, 0x72, 0x74, 0x28, 0x22, 0x68, 0x75, 0x66, 0x66, 0x6d, 0x6e, 0x2d, 0x6e, 0x75, 0x6c, 0x6c, 0x2d, 0x6d, 0x78, 0x2e, 0x69, 0x6e, 0x22, 0x40800021, 0x2e, 0x57, 0x72, 0x69, 0x74, 0x28, 0x62, 0x29, 0xd, 0xa, 0x7d, 0xd, 0xa, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x58, 0x78, 0x79, 0x7a, 0x21, 0x22, 0x23, 0xc2, 0xa4, 0x25, 0x26, 0x2f, 0x3f, 0x22},
flate/huffman_bit_writer_test.go:149: tokens: []token{0x2f, 0x2f, 0x20, 0x43, 0x6f, 0x70, 0x79, 0x72, 0x69, 0x67, 0x68, 0x74, 0x20, 0x32, 0x30, 0x30, 0x39, 0x20, 0x54, 0x68, 0x65, 0x20, 0x47, 0x6f, 0x20, 0x41, 0x75, 0x74, 0x68, 0x6f, 0x72, 0x73, 0x2e, 0x20, 0x41, 0x6c, 0x6c, 0x20, 0x4080001e, 0x73, 0x20, 0x72, 0x65, 0x73, 0x65, 0x72, 0x76, 0x65, 0x64, 0x2e, 0xd, 0xa, 0x2f, 0x2f, 0x20, 0x55, 0x73, 0x65, 0x20, 0x6f, 0x66, 0x20, 0x74, 0x68, 0x69, 0x73, 0x20, 0x73, 0x6f, 0x75, 0x72, 0x63, 0x65, 0x20, 0x63, 0x6f, 0x64, 0x65, 0x20, 0x69, 0x73, 0x20, 0x67, 0x6f, 0x76, 0x65, 0x72, 0x6e, 0x65, 0x64, 0x20, 0x62, 0x79, 0x20, 0x61, 0x20, 0x42, 0x53, 0x44, 0x2d, 0x73, 0x74, 0x79, 0x6c, 0x65, 0x40800036, 0x6c, 0x69, 0x63, 0x65, 0x6e, 0x73, 0x65, 0x20, 0x74, 0x68, 0x61, 0x74, 0x20, 0x63, 0x61, 0x6e, 0x20, 0x62, 0x65, 0x20, 0x66, 0x6f, 0x75, 0x6e, 0x64, 0x20, 0x69, 0x6e, 0x20, 0x74, 0x68, 0x65, 0x20, 0x4c, 0x49, 0x43, 0x45, 0x4e, 0x53, 0x45, 0x20, 0x66, 0x69, 0x6c, 0x65, 0x2e, 0xd, 0xa, 0xd, 0xa, 0x70, 0x61, 0x63, 0x6b, 0x61, 0x67, 0x65, 0x20, 0x6d, 0x61, 0x69, 0x6e, 0x4040000f, 0x69, 0x6d, 0x70, 0x6f, 0x72, 0x74, 0x20, 0x22, 0x6f, 0x73, 0x22, 0x4040000e, 0x66, 0x75, 0x6e, 0x63, 0x4080001b, 0x28, 0x29, 0x20, 0x7b, 0xd, 0xa, 0x9, 0x76, 0x61, 0x72, 0x20, 0x62, 0x20, 0x3d, 0x20, 0x6d, 0x61, 0x6b, 0x65, 0x28, 0x5b, 0x5d, 0x62, 0x79, 0x74, 0x65, 0x2c, 0x20, 0x36, 0x35, 0x35, 0x33, 0x35, 0x29, 0xd, 0xa, 0x9, 0x66, 0x2c, 0x20, 0x5f, 0x20, 0x3a, 0x3d, 0x20, 0x6f, 0x73, 0x2e, 0x43, 0x72, 0x65, 0x61, 0x74, 0x65, 0x28, 0x22, 0x68, 0x75, 0x66, 0x66, 0x6d, 0x61, 0x6e, 0x2d, 0x6e, 0x75, 0x6c, 0x6c, 0x2d, 0x6d, 0x61, 0x78, 0x2e, 0x69, 0x6e, 0x22, 0x4080002a, 0x2e, 0x57, 0x72, 0x69, 0x74, 0x65, 0x28, 0x62, 0x29, 0xd, 0xa, 0x7d, 0xd, 0xa},
flate/huffman_bit_writer_test.go:155: tokens: []token{0x30, ml, 0x4b800000},
flate/huffman_bit_writer_test.go:161: tokens: []token{0x0, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, 0x41400000},
flate/huffman_bit_writer_test.go:173:// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
flate/huffman_bit_writer_test.go:181:// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
flate/huffman_bit_writer_test.go:197: tokens := indexTokens(test.tokens)
flate/huffman_bit_writer_test.go:214: writeToType(t, ttype, bw, tokens, input)
flate/huffman_bit_writer_test.go:225: writeToType(t, ttype, bw, tokens, nil)
flate/huffman_bit_writer_test.go:243: writeToType(t, ttype, bw, tokens, input)
flate/huffman_bit_writer_test.go:257: writeToType(t, ttype, bw, tokens, input)
flate/huffman_bit_writer_test.go:278: writeToType(t, ttype, bw, tokens, nil)
flate/huffman_bit_writer_test.go:296: writeToType(t, ttype, bw, tokens, nil)
flate/huffman_bit_writer_test.go:310:func writeToType(t *testing.T, ttype string, bw *huffmanBitWriter, tok tokens, input []byte) {
flate/huffman_bit_writer_test.go:315: bw.writeBlockDynamic(&tok, false, input, false)
flate/huffman_bit_writer_test.go:317: bw.writeBlockDynamic(&tok, false, input, true)
flate/huffman_bit_writer_test.go:350: tokens := indexTokens(test.tokens)
flate/huffman_bit_writer_test.go:353: bw.writeBlock(&tokens, true, input)
flate/huffman_bit_writer_test.go:355: bw.writeBlockDynamic(&tokens, true, input, true)
flate/huffman_bit_writer_test.go:357: bw.writeBlockHuff(true, input, true)
flate/stateless.go:64:// tokensPool contains tokens struct objects that can be reused
flate/stateless.go:65:var tokensPool = sync.Pool{
flate/stateless.go:67: return &tokens{}
flate/stateless.go:100: dst := tokensPool.Get().(*tokens)
flate/stateless.go:103: tokensPool.Put(dst)
flate/stateless.go:142: bw.writeBlockHuff(isEof, uncompressed, len(in) == 0)
flate/stateless.go:144: bw.writeBlockDynamic(dst, isEof, uncompressed, len(in) == 0)
flate/stateless.go:176:func statelessEnc(dst *tokens, src []byte, startAt int16) {
flate/stateless.go:276: dst.tokens[dst.n] = token(v)
sed -n '540,775p' flate/huffman_bit_writer.go
Chunk ID: fc5592
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1641
Output:
// Indicate that we are a fixed Huffman block
var value int32 = 2
if isEof {
value = 3
}
w.writeBits(value, 3)
}
// writeBlock will write a block of tokens with the smallest encoding.
// The original input can be supplied, and if the huffman encoded data
// is larger than the original bytes, the data will be written as a
// stored block.
// If the input is nil, the tokens will always be Huffman encoded.
func (w *huffmanBitWriter) writeBlock(tokens *tokens, eof bool, input []byte) {
if w.err != nil {
return
}
tokens.AddEOB()
if w.lastHeader > 0 {
// We owe an EOB
w.writeCode(w.literalEncoding.codes[endBlockMarker])
w.lastHeader = 0
}
numLiterals, numOffsets := w.indexTokens(tokens, false)
w.generate()
var extraBits int
storedSize, storable := w.storedSize(input)
if storable {
extraBits = w.extraBitSize()
}
// Figure out smallest code.
// Fixed Huffman baseline.
var literalEncoding = fixedLiteralEncoding
var offsetEncoding = fixedOffsetEncoding
var size = math.MaxInt32
if tokens.n < maxPredefinedTokens {
size = w.fixedSize(extraBits)
}
// Dynamic Huffman?
var numCodegens int
// Generate codegen and codegenFrequencies, which indicates how to encode
// the literalEncoding and the offsetEncoding.
w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
w.codegenEncoding.generate(w.codegenFreq[:], 7)
dynamicSize, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
if dynamicSize < size {
size = dynamicSize
literalEncoding = w.literalEncoding
offsetEncoding = w.offsetEncoding
}
// Stored bytes?
if storable && storedSize <= size {
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
// Huffman.
if literalEncoding == fixedLiteralEncoding {
w.writeFixedHeader(eof)
} else {
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
}
// Write the tokens.
w.writeTokens(tokens.Slice(), literalEncoding.codes, offsetEncoding.codes)
}
// writeBlockDynamic encodes a block using a dynamic Huffman table.
// This should be used if the symbols used have a disproportionate
// histogram distribution.
// If input is supplied and the compression savings are below 1/16th of the
// input size the block is stored.
func (w *huffmanBitWriter) writeBlockDynamic(tokens *tokens, eof bool, input []byte, sync bool) {
if w.err != nil {
return
}
sync = sync || eof
if sync {
tokens.AddEOB()
}
// We cannot reuse pure huffman table, and must mark as EOF.
if (w.lastHuffMan || eof) && w.lastHeader > 0 {
// We will not try to reuse.
w.writeCode(w.literalEncoding.codes[endBlockMarker])
w.lastHeader = 0
w.lastHuffMan = false
}
// fillReuse enables filling of empty values.
// This will make encodings always reusable without testing.
// However, this does not appear to benefit on most cases.
const fillReuse = false
// Check if we can reuse...
if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
w.writeCode(w.literalEncoding.codes[endBlockMarker])
w.lastHeader = 0
}
numLiterals, numOffsets := w.indexTokens(tokens, fillReuse && !sync)
extraBits := 0
ssize, storable := w.storedSize(input)
const usePrefs = true
if storable || w.lastHeader > 0 {
extraBits = w.extraBitSize()
}
var size int
// Check if we should reuse.
if w.lastHeader > 0 {
// Estimate size for using a new table.
// Use the previous header size as the best estimate.
newSize := w.lastHeader + tokens.EstimatedBits()
newSize += int(w.literalEncoding.codes[endBlockMarker].len()) + newSize>>w.logNewTablePenalty
// The estimated size is calculated as an optimal table.
// We add a penalty to make it more realistic and re-use a bit more.
reuseSize := w.dynamicReuseSize(w.literalEncoding, w.offsetEncoding) + extraBits
// Check if a new table is better.
if newSize < reuseSize {
// Write the EOB we owe.
w.writeCode(w.literalEncoding.codes[endBlockMarker])
size = newSize
w.lastHeader = 0
} else {
size = reuseSize
}
if tokens.n < maxPredefinedTokens {
if preSize := w.fixedSize(extraBits) + 7; usePrefs && preSize < size {
// Check if we get a reasonable size decrease.
if storable && ssize <= size {
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
w.writeFixedHeader(eof)
if !sync {
tokens.AddEOB()
}
w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
return
}
}
// Check if we get a reasonable size decrease.
if storable && ssize <= size {
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
}
// We want a new block/table
if w.lastHeader == 0 {
if fillReuse && !sync {
w.fillTokens()
numLiterals, numOffsets = maxNumLit, maxNumDist
} else {
w.literalFreq[endBlockMarker] = 1
}
w.generate()
// Generate codegen and codegenFrequencies, which indicates how to encode
// the literalEncoding and the offsetEncoding.
w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
w.codegenEncoding.generate(w.codegenFreq[:], 7)
var numCodegens int
if fillReuse && !sync {
// Reindex for accurate size...
w.indexTokens(tokens, true)
}
size, numCodegens = w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
// Store predefined, if we don't get a reasonable improvement.
if tokens.n < maxPredefinedTokens {
if preSize := w.fixedSize(extraBits); usePrefs && preSize <= size {
// Store bytes, if we don't get an improvement.
if storable && ssize <= preSize {
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
w.writeFixedHeader(eof)
if !sync {
tokens.AddEOB()
}
w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
return
}
}
if storable && ssize <= size {
// Store bytes, if we don't get an improvement.
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
// Write Huffman table.
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
if !sync {
w.lastHeader, _ = w.headerSize()
}
w.lastHuffMan = false
}
if sync {
w.lastHeader = 0
}
// Write the tokens.
w.writeTokens(tokens.Slice(), w.literalEncoding.codes, w.offsetEncoding.codes)
}
func (w *huffmanBitWriter) fillTokens() {
for i, v := range w.literalFreq[:literalCount] {
if v == 0 {
w.literalFreq[i] = 1
}
}
for i, v := range w.offsetFreq[:offsetCodeCount] {
if v == 0 {
w.offsetFreq[i] = 1
sed -n '775,880p' flate/huffman_bit_writer.go
Chunk ID: e9b063
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 678
Output:
w.offsetFreq[i] = 1
}
}
}
// indexTokens indexes a slice of tokens, and updates
// literalFreq and offsetFreq, and generates literalEncoding
// and offsetEncoding.
// The number of literal and offset tokens is returned.
func (w *huffmanBitWriter) indexTokens(t *tokens, filled bool) (numLiterals, numOffsets int) {
//copy(w.literalFreq[:], t.litHist[:])
*(*[256]uint16)(w.literalFreq[:]) = t.litHist
//copy(w.literalFreq[256:], t.extraHist[:])
*(*[32]uint16)(w.literalFreq[256:]) = t.extraHist
w.offsetFreq = t.offHist
if t.n == 0 {
return
}
if filled {
return maxNumLit, maxNumDist
}
// get the number of literals
numLiterals = len(w.literalFreq)
for w.literalFreq[numLiterals-1] == 0 {
numLiterals--
}
// get the number of offsets
numOffsets = len(w.offsetFreq)
for numOffsets > 0 && w.offsetFreq[numOffsets-1] == 0 {
numOffsets--
}
if numOffsets == 0 {
// We haven't found a single match. If we want to go with the dynamic encoding,
// we should count at least one offset to be sure that the offset huffman tree could be encoded.
w.offsetFreq[0] = 1
numOffsets = 1
}
return
}
func (w *huffmanBitWriter) generate() {
w.literalEncoding.generate(w.literalFreq[:literalCount], 15)
w.offsetEncoding.generate(w.offsetFreq[:offsetCodeCount], 15)
}
// writeTokens writes a slice of tokens to the output.
// codes for literal and offset encoding must be supplied.
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]
// Go 1.16 LOVES having these on stack.
bits, nbits, nbytes := w.bits, w.nbits, w.nbytes
for _, t := range tokens {
if t < 256 {
//w.writeCode(lits[t.literal()])
c := lits[t]
bits |= c.code64() << (nbits & 63)
nbits += c.len()
if nbits >= 48 {
le.Store64(w.bytes[:], nbytes, bits)
bits >>= 48
nbits -= 48
nbytes += 6
if nbytes >= bufferFlushSize {
if w.err != nil {
nbytes = 0
return
}
_, w.err = w.writer.Write(w.bytes[:nbytes])
nbytes = 0
}
}
continue
}
// Write the length
length := t.length()
lengthCode := lengthCode(length) & 31
if false {
w.writeCode(lengths[lengthCode])
} else {
// inlined
c := lengths[lengthCode]
bits |= c.code64() << (nbits & 63)
nbits += c.len()
if nbits >= 48 {
sed -n '1,180p' flate/token.go
Chunk ID: f31d5d
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1525
Output:
// 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 (
"bytes"
"encoding/binary"
"fmt"
"io"
"math"
)
const (
// bits 0-16 xoffset = offset - MIN_OFFSET_SIZE, or literal - 16 bits
// bits 16-22 offsetcode - 5 bits
// bits 22-30 xlength = length - MIN_MATCH_LENGTH - 8 bits
// bits 30-32 type 0 = literal 1=EOF 2=Match 3=Unused - 2 bits
lengthShift = 22
offsetMask = 1<<lengthShift - 1
typeMask = 3 << 30
literalType = 0 << 30
matchType = 1 << 30
matchOffsetOnlyMask = 0xffff
)
// The length code for length X (MIN_MATCH_LENGTH <= X <= MAX_MATCH_LENGTH)
// is lengthCodes[length - MIN_MATCH_LENGTH]
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,
15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
17, 17, 17, 17, 17, 17, 17, 17, 18, 18,
18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
19, 19, 19, 19, 20, 20, 20, 20, 20, 20,
20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 28,
}
// lengthCodes1 is length codes, but starting at 1.
var lengthCodes1 = [256]uint8{
1, 2, 3, 4, 5, 6, 7, 8, 9, 9,
10, 10, 11, 11, 12, 12, 13, 13, 13, 13,
14, 14, 14, 14, 15, 15, 15, 15, 16, 16,
16, 16, 17, 17, 17, 17, 17, 17, 17, 17,
18, 18, 18, 18, 18, 18, 18, 18, 19, 19,
19, 19, 19, 19, 19, 19, 20, 20, 20, 20,
20, 20, 20, 20, 21, 21, 21, 21, 21, 21,
21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
22, 22, 22, 22, 22, 22, 23, 23, 23, 23,
23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
24, 24, 24, 24, 24, 24, 24, 24, 25, 25,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 29,
}
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,
11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
}
// offsetCodes14 are offsetCodes, but with 14 added.
var offsetCodes14 = [256]uint32{
14, 15, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
}
type token uint32
type tokens struct {
extraHist [32]uint16 // codes 256->maxnumlit
offHist [32]uint16 // offset codes
litHist [256]uint16 // codes 0->255
nFilled int
n uint16 // Must be able to contain maxStoreBlockSize
tokens [maxStoreBlockSize + 1]token
}
func (t *tokens) Reset() {
if t.n == 0 {
return
}
t.n = 0
t.nFilled = 0
for i := range t.litHist[:] {
t.litHist[i] = 0
}
for i := range t.extraHist[:] {
t.extraHist[i] = 0
}
for i := range t.offHist[:] {
t.offHist[i] = 0
}
}
func (t *tokens) Fill() {
if t.n == 0 {
return
}
for i, v := range t.litHist[:] {
if v == 0 {
t.litHist[i] = 1
t.nFilled++
}
}
for i, v := range t.extraHist[:literalCount-256] {
if v == 0 {
t.nFilled++
t.extraHist[i] = 1
}
}
for i, v := range t.offHist[:offsetCodeCount] {
if v == 0 {
t.offHist[i] = 1
}
}
}
func indexTokens(in []token) tokens {
var t tokens
sed -n '760,875p' flate/deflate.go
Chunk ID: 1c10f3
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 654
Output:
d.step(d)
}
b = b[d.fill(d, b):]
if d.err != nil {
return 0, d.err
}
}
return n, d.err
}
func (d *compressor) syncFlush() error {
d.sync = true
if d.err != nil {
return d.err
}
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).fillBlock
d.step = (*compressor).store
case level == ConstantCompression:
d.w.logNewTablePenalty = 10
d.window = make([]byte, 32<<10)
d.fill = (*compressor).fillBlock
d.step = (*compressor).storeHuff
case level == DefaultCompression:
level = 5
fallthrough
case level >= 1 && level <= 6:
d.w.logNewTablePenalty = 7
d.fast = newFastEnc(level)
d.window = make([]byte, maxStoreBlockSize)
d.fill = (*compressor).fillBlock
d.step = (*compressor).storeFast
case 7 <= level && level <= 9:
d.w.logNewTablePenalty = 8
d.state = &advancedState{}
d.compressionLevel = levels[level]
d.initDeflate()
d.fill = (*compressor).fillDeflate
d.step = (*compressor).deflateLazy
case -level >= MinCustomWindowSize && -level <= MaxCustomWindowSize:
d.w.logNewTablePenalty = 7
d.fast = &fastEncL5Window{maxOffset: int32(-level), cur: maxStoreBlockSize}
d.window = make([]byte, maxStoreBlockSize)
d.fill = (*compressor).fillBlock
d.step = (*compressor).storeFast
default:
return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
}
d.level = level
return nil
}
// reset the state of the compressor.
func (d *compressor) reset(w io.Writer) {
d.w.reset(w)
d.sync = false
d.err = nil
// We only need to reset a few things for Snappy.
if d.fast != nil {
d.fast.Reset()
d.windowEnd = 0
d.tokens.Reset()
return
}
switch d.compressionLevel.chain {
case 0:
// level was NoCompression or ConstantCompression.
d.windowEnd = 0
default:
s := d.state
s.chainHead = -1
for i := range s.hashHead {
s.hashHead[i] = 0
}
for i := range s.hashPrev {
s.hashPrev[i] = 0
}
s.hashOffset = 1
s.index, d.windowEnd = 0, 0
d.blockStart, d.byteAvailable = 0, false
d.tokens.Reset()
s.length = minMatchLength - 1
s.offset = 0
s.ii = 0
s.maxInsertIndex = 0
}
}
func (d *compressor) close() error {
if d.err != nil {
return d.err
}
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()
GOROOT=$(go env GOROOT); rg -n "func \(d \*compressor\) deflateLazy|writeBlock\(&d.tokens" "$GOROOT/src/compress/flate/deflate.go"
Chunk ID: 0c403e Wall time: 0.0000 seconds Process exited with code 1 Original token count: 0 Output:
GOROOT=$(go env GOROOT); sed -n '330,560p' "$GOROOT/src/compress/flate/deflate.go"
Chunk ID: 035865
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1594
Output:
// encSpeed will compress and store the currently added data,
// if enough has been accumulated or we at the end of the stream.
// Any error that occurred will be in d.err
func (d *compressor) encSpeed() {
// We only compress if we have maxStoreBlockSize.
if d.windowEnd < maxStoreBlockSize {
if !d.sync {
return
}
// Handle small sizes.
if d.windowEnd < 128 {
switch {
case d.windowEnd == 0:
return
case d.windowEnd <= 16:
d.err = d.writeStoredBlock(d.window[:d.windowEnd])
default:
d.w.writeBlockHuff(false, d.window[:d.windowEnd])
d.err = d.w.err
}
d.windowEnd = 0
d.bestSpeed.reset()
return
}
}
// Encode the block.
d.tokens = d.bestSpeed.encode(d.tokens[:0], d.window[:d.windowEnd])
// If we removed less than 1/16th, Huffman compress the block.
if len(d.tokens) > d.windowEnd-(d.windowEnd>>4) {
d.w.writeBlockHuff(false, d.window[:d.windowEnd])
} else {
d.w.writeBlockDynamic(d.tokens, false, d.window[:d.windowEnd])
}
d.err = d.w.err
d.windowEnd = 0
}
func (d *compressor) initDeflate() {
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.chainHead = -1
d.bulkHasher = bulkHash4
}
func (d *compressor) deflate() {
if d.windowEnd-d.index < minMatchLength+maxMatchLength && !d.sync {
return
}
d.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
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); d.err != nil {
return
}
d.tokens = d.tokens[:0]
}
break Loop
}
}
if d.index < d.maxInsertIndex {
// Update the hash
hash := hash4(d.window[d.index : d.index+minMatchLength])
hh := &d.hashHead[hash&hashMask]
d.chainHead = int(*hh)
d.hashPrev[d.index&windowMask] = uint32(d.chainHead)
*hh = uint32(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-baseMatchLength), uint32(d.offset-baseMatchOffset)))
} else {
d.tokens = append(d.tokens, matchToken(uint32(prevLength-baseMatchLength), uint32(prevOffset-baseMatchOffset)))
}
// 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
}
index := d.index
for index++; index < newIndex; index++ {
if index < d.maxInsertIndex {
hash := hash4(d.window[index : index+minMatchLength])
// Get previous value with the same hash.
// Our chain should point to the previous value.
hh := &d.hashHead[hash&hashMask]
d.hashPrev[index&windowMask] = *hh
// Set the head of the hash chain to us.
*hh = uint32(index + d.hashOffset)
}
}
d.index = index
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 len(d.tokens) == maxFlateBlockTokens {
// The block includes the current character
if d.err = d.writeBlock(d.tokens, d.index); 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); 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.windowEnd == maxStoreBlockSize || d.sync) {
d.err = d.writeStoredBlock(d.window[:d.windowEnd])
d.windowEnd = 0
}
}
// storeHuff compresses and stores the currently added data
// when the d.window is full or we are at the end of the stream.
// Any error that occurred will be in d.err
func (d *compressor) storeHuff() {
if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
return
}
d.w.writeBlockHuff(false, d.window[:d.windowEnd])
d.err = d.w.err
d.windowEnd = 0
}
func (d *compressor) write(b []byte) (n int, err error) {
if d.err != nil {
return 0, d.err
}
n = len(b)
for len(b) > 0 {
d.step(d)
b = b[d.fill(d, b):]
if d.err != nil {
return 0, d.err
}
}
return n, nil
}
func (d *compressor) syncFlush() error {
if d.err != nil {
return d.err
}
d.sync = true
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: b16788
Wall time: 0.6060 seconds
Process exited with code 1
Original token count: 66
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.59s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.593s
FAIL
rg -n "d\.h|huffmanEncoder|maxFlateBlockTokens|writeBlockSkip\(" flate/deflate.go flate/*.goChunk ID: 2ba966
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1325
Output:
flate/deflate.go:47: maxFlateBlockTokens = 1 << 15
flate/deflate.go:110: h *huffmanEncoder
flate/deflate.go:189:func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
flate/deflate.go:326: newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
flate/deflate.go:328: //fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
flate/deflate.go:420: if d.h == nil {
flate/deflate.go:421: d.h = newHuffmanEncoder(maxFlateBlockTokens)
flate/deflate.go:427: d.h.generate(tmp[:], 15)
flate/deflate.go:511: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:552: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:612: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:629: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:646: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:666: if d.tokens.n == maxFlateBlockTokens {
flate/dict_decoder_test.go:113: writeCopy(dd.histSize(), 33)
flate/dict_decoder_test.go:132: writeCopy(dd.histSize(), 10)
flate/dict_decoder_test.go:133: want.Write(want.Bytes()[want.Len()-dd.histSize():][:10])
flate/deflate.go:47: maxFlateBlockTokens = 1 << 15
flate/deflate.go:110: h *huffmanEncoder
flate/deflate.go:189:func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
flate/deflate.go:326: newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
flate/deflate.go:328: //fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
flate/deflate.go:420: if d.h == nil {
flate/deflate.go:421: d.h = newHuffmanEncoder(maxFlateBlockTokens)
flate/deflate.go:427: d.h.generate(tmp[:], 15)
flate/deflate.go:511: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:552: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:612: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:629: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:646: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:666: if d.tokens.n == maxFlateBlockTokens {
flate/dict_decoder.go:40: *dd = dictDecoder{hist: dd.hist}
flate/dict_decoder.go:42: if cap(dd.hist) < size {
flate/dict_decoder.go:43: dd.hist = make([]byte, size)
flate/dict_decoder.go:45: dd.hist = dd.hist[:size]
flate/dict_decoder.go:47: if len(dict) > len(dd.hist) {
flate/dict_decoder.go:48: dict = dict[len(dict)-len(dd.hist):]
flate/dict_decoder.go:50: dd.wrPos = copy(dd.hist, dict)
flate/dict_decoder.go:51: if dd.wrPos == len(dd.hist) {
flate/dict_decoder.go:61: return len(dd.hist)
flate/dict_decoder.go:73: return len(dd.hist) - dd.wrPos
flate/dict_decoder.go:80: return dd.hist[dd.wrPos:]
flate/dict_decoder.go:94: dd.hist[dd.wrPos] = c
flate/dict_decoder.go:107: endPos := min(dstPos+length, len(dd.hist))
flate/dict_decoder.go:117: srcPos += len(dd.hist)
flate/dict_decoder.go:118: dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:])
flate/dict_decoder.go:132: // dd.hist[dstPos+i] = dd.hist[srcPos+i]
flate/dict_decoder.go:137: dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
flate/dict_decoder.go:153: if dstPos < dist || endPos > len(dd.hist) {
flate/dict_decoder.go:161: dstPos += copy(dd.hist[dstPos:endPos], dd.hist[srcPos:dstPos])
flate/dict_decoder.go:174: toRead := dd.hist[dd.rdPos:dd.wrPos]
flate/dict_decoder.go:176: if dd.wrPos == len(dd.hist) {
flate/huffman_bit_writer.go:110: literalEncoding *huffmanEncoder
flate/huffman_bit_writer.go:111: tmpLitEncoding *huffmanEncoder
flate/huffman_bit_writer.go:112: offsetEncoding *huffmanEncoder
flate/huffman_bit_writer.go:113: codegenEncoding *huffmanEncoder
flate/huffman_bit_writer.go:269:func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int, litEnc, offEnc *huffmanEncoder) {
flate/huffman_bit_writer.go:371:func (w *huffmanBitWriter) dynamicReuseSize(litEnc, offEnc *huffmanEncoder) (size int) {
flate/huffman_bit_writer.go:378:func (w *huffmanBitWriter) dynamicSize(litEnc, offEnc *huffmanEncoder, extraBits int) (size, numCodegens int) {
flate/huffman_bit_writer.go:974:var huffOffset *huffmanEncoder
flate/huffman_code.go:33:type huffmanEncoder struct {
flate/huffman_code.go:83:func newHuffmanEncoder(size int) *huffmanEncoder {
flate/huffman_code.go:86: return &huffmanEncoder{codes: make([]hcode, size, 1<<c)}
flate/huffman_code.go:90:func generateFixedLiteralEncoding() *huffmanEncoder {
flate/huffman_code.go:120:func generateFixedOffsetEncoding() *huffmanEncoder {
flate/huffman_code.go:132:func (h *huffmanEncoder) bitLength(freq []uint16) int {
flate/huffman_code.go:142:func (h *huffmanEncoder) bitLengthRaw(b []byte) int {
flate/huffman_code.go:151:func (h *huffmanEncoder) canReuseBits(freq []uint16) int {
flate/huffman_code.go:183:func (h *huffmanEncoder) bitCounts(list []literalNode, maxBits int32) []int32 {
flate/huffman_code.go:313:func (h *huffmanEncoder) assignEncodingAndSize(bitCount []int32, list []literalNode) {
flate/huffman_code.go:339:func (h *huffmanEncoder) generate(freq []uint16, maxBits int32) {
sed -n '1,135p' flate/deflate.go
Chunk ID: 8ae912
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1052
Output:
// Copyright 2009 The Go Authors. All rights reserved.
// Copyright (c) 2015 Klaus Post
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package flate
import (
"errors"
"fmt"
"io"
"math"
"[code-host]/klauspost/compress/internal/le"
)
const (
NoCompression = 0
BestSpeed = 1
BestCompression = 9
DefaultCompression = -1
// HuffmanOnly disables Lempel-Ziv match searching and only performs Huffman
// entropy encoding. This mode is useful in compressing data that has
// already been compressed with an LZ style algorithm (e.g. Snappy or LZ4)
// that lacks an entropy encoder. Compression gains are achieved when
// certain bytes in the input stream occur more frequently than others.
//
// Note that HuffmanOnly produces a compressed output that is
// RFC 1951 compliant. That is, any valid DEFLATE decompressor will
// continue to be able to decompress this output.
HuffmanOnly = -2
ConstantCompression = HuffmanOnly // compatibility alias.
logWindowSize = 15
windowSize = 1 << logWindowSize
windowMask = windowSize - 1
logMaxOffsetSize = 15 // Standard DEFLATE
minMatchLength = 4 // The smallest match that the compressor looks for
maxMatchLength = 258 // The longest match for the compressor
minOffsetSize = 1 // The shortest offset that makes any sense
// The maximum number of tokens we will encode at the time.
// Smaller sizes usually creates less optimal blocks.
// Bigger can make context switching slow.
// We use this for levels 7-9, so we make it big.
maxFlateBlockTokens = 1 << 15
maxStoreBlockSize = 65535
hashBits = 17 // After 17 performance degrades
hashSize = 1 << hashBits
hashMask = (1 << hashBits) - 1
hashShift = (hashBits + minMatchLength - 1) / minMatchLength
maxHashOffset = 1 << 28
skipNever = math.MaxInt32
debugDeflate = false
)
type compressionLevel struct {
good, lazy, nice, chain, fastSkipHashing, level int
}
// Compression levels have been rebalanced from zlib deflate defaults
// to give a bigger spread in speed and compression.
// See https://blog.klauspost.com/rebalancing-deflate-compression-levels/
var levels = []compressionLevel{
{}, // 0
// Level 1-6 uses specialized algorithm - values not used
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 2},
{0, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 0, 4},
{0, 0, 0, 0, 0, 5},
{0, 0, 0, 0, 0, 6},
// Levels 7-9 use increasingly more lazy matching
// and increasingly stringent conditions for "good enough".
{8, 12, 16, 24, skipNever, 7},
{16, 30, 40, 64, skipNever, 8},
{32, 258, 258, 1024, skipNever, 9},
}
// advancedState contains state for the advanced levels, with bigger hash tables, etc.
type advancedState struct {
// deflate state
length int
offset int
maxInsertIndex int
chainHead int
hashOffset int
ii uint16 // position of last match, intended to overflow to reset.
// input window: unprocessed data is window[index:windowEnd]
index int
hashMatch [maxMatchLength + minMatchLength]uint32
// 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.
hashHead [hashSize]uint32
hashPrev [windowSize]uint32
}
type compressor struct {
compressionLevel
h *huffmanEncoder
w *huffmanBitWriter
// compression algorithm
fill func(*compressor, []byte) int // copy data to window
step func(*compressor) // process window
window []byte
windowEnd int
blockStart int // window index where current tokens start
err error
// queued output tokens
tokens tokens
fast fastEnc
state *advancedState
sync bool // requesting flush
byteAvailable bool // if true, still need to process window[index-1].
}
func (d *compressor) fillDeflate(b []byte) int {
s := d.state
if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
// shift the window by windowSize
//copy(d.window[:], d.window[windowSize:2*windowSize])
git diff -- flate/deflate.go flate/large_low_entropy_test.go
Chunk ID: fee334
Wall time: 0.0000 seconds
Process exited with code 1
Original token count: 7759
Output:
diff --git a/flate/deflate.go b/flate/large_low_entropy_test.go
index 4e92f59..d040289 100644
--- a/flate/deflate.go
+++ b/flate/large_low_entropy_test.go
@@ -1,994 +1,44 @@
-// Copyright 2009 The Go Authors. All rights reserved.
-// Copyright (c) 2015 Klaus Post
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
package flate
import (
- "errors"
- "fmt"
+ "bytes"
+ stdflate "compress/flate"
"io"
- "math"
-
- "[code-host]/klauspost/compress/internal/le"
-)
-
-const (
- NoCompression = 0
- BestSpeed = 1
- BestCompression = 9
- DefaultCompression = -1
-
- // HuffmanOnly disables Lempel-Ziv match searching and only performs Huffman
- // entropy encoding. This mode is useful in compressing data that has
- // already been compressed with an LZ style algorithm (e.g. Snappy or LZ4)
- // that lacks an entropy encoder. Compression gains are achieved when
- // certain bytes in the input stream occur more frequently than others.
- //
- // Note that HuffmanOnly produces a compressed output that is
- // RFC 1951 compliant. That is, any valid DEFLATE decompressor will
- // continue to be able to decompress this output.
- HuffmanOnly = -2
- ConstantCompression = HuffmanOnly // compatibility alias.
-
- logWindowSize = 15
- windowSize = 1 << logWindowSize
- windowMask = windowSize - 1
- logMaxOffsetSize = 15 // Standard DEFLATE
- minMatchLength = 4 // The smallest match that the compressor looks for
- maxMatchLength = 258 // The longest match for the compressor
- minOffsetSize = 1 // The shortest offset that makes any sense
-
- // The maximum number of tokens we will encode at the time.
- // Smaller sizes usually creates less optimal blocks.
- // Bigger can make context switching slow.
- // We use this for levels 7-9, so we make it big.
- maxFlateBlockTokens = 1 << 15
- maxStoreBlockSize = 65535
- hashBits = 17 // After 17 performance degrades
- hashSize = 1 << hashBits
- hashMask = (1 << hashBits) - 1
- hashShift = (hashBits + minMatchLength - 1) / minMatchLength
- maxHashOffset = 1 << 28
-
- skipNever = math.MaxInt32
-
- debugDeflate = false
+ "testing"
)
-type compressionLevel struct {
- good, lazy, nice, chain, fastSkipHashing, level int
-}
-
-// Compression levels have been rebalanced from zlib deflate defaults
-// to give a bigger spread in speed and compression.
-// See https://blog.klauspost.com/rebalancing-deflate-compression-levels/
-var levels = []compressionLevel{
- {}, // 0
- // Level 1-6 uses specialized algorithm - values not used
- {0, 0, 0, 0, 0, 1},
- {0, 0, 0, 0, 0, 2},
- {0, 0, 0, 0, 0, 3},
- {0, 0, 0, 0, 0, 4},
- {0, 0, 0, 0, 0, 5},
- {0, 0, 0, 0, 0, 6},
- // Levels 7-9 use increasingly more lazy matching
- // and increasingly stringent conditions for "good enough".
- {8, 12, 16, 24, skipNever, 7},
- {16, 30, 40, 64, skipNever, 8},
- {32, 258, 258, 1024, skipNever, 9},
-}
-
-// advancedState contains state for the advanced levels, with bigger hash tables, etc.
-type advancedState struct {
- // deflate state
- length int
- offset int
- maxInsertIndex int
- chainHead int
- hashOffset int
-
- ii uint16 // position of last match, intended to overflow to reset.
-
- // input window: unprocessed data is window[index:windowEnd]
- index int
- hashMatch [maxMatchLength + minMatchLength]uint32
-
- // 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.
- hashHead [hashSize]uint32
- hashPrev [windowSize]uint32
-}
-
-type compressor struct {
- compressionLevel
-
- h *huffmanEncoder
- w *huffmanBitWriter
-
- // compression algorithm
- fill func(*compressor, []byte) int // copy data to window
- step func(*compressor) // process window
-
- window []byte
- windowEnd int
- blockStart int // window index where current tokens start
- err error
-
- // queued output tokens
- tokens tokens
- fast fastEnc
- state *advancedState
-
- sync bool // requesting flush
- byteAvailable bool // if true, still need to process window[index-1].
-}
-
-func (d *compressor) fillDeflate(b []byte) int {
- s := d.state
- if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
- // shift the window by windowSize
- //copy(d.window[:], d.window[windowSize:2*windowSize])
- *(*[windowSize]byte)(d.window) = *(*[windowSize]byte)(d.window[windowSize:])
- s.index -= windowSize
- d.windowEnd -= windowSize
- if d.blockStart >= windowSize {
- d.blockStart -= windowSize
- } else {
- d.blockStart = math.MaxInt32
- }
- 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 s.hashPrev[:] {
- if int(v) > delta {
- s.hashPrev[i] = uint32(int(v) - delta)
- } else {
- s.hashPrev[i] = 0
- }
- }
- for i, v := range s.hashHead[:] {
- if int(v) > delta {
- s.hashHead[i] = uint32(int(v) - delta)
- } else {
- s.hashHead[i] = 0
- }
- }
- }
- }
- n := copy(d.window[d.windowEnd:], b)
- d.windowEnd += n
- return n
-}
-
-func (d *compressor) writeBlock(tok *tokens, 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(tok, eof, window)
- d.w.writeBlockDynamic(tok, eof, window, d.sync)
- return d.w.err
- }
- return nil
-}
-
-// writeBlockSkip writes the current block and uses the number of tokens
-// to determine if the block should be stored on no matches, or
-// only huffman encoded.
-func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
- if index > 0 || eof {
- if d.blockStart <= index {
- window := d.window[d.blockStart:index]
- // If we removed less than a 64th of all literals
- // we huffman compress the block.
- if int(tok.n) > len(window)-int(tok.n>>6) {
- d.w.writeBlockHuff(eof, window, d.sync)
- } else {
- // Write a dynamic huffman block.
- d.w.writeBlockDynamic(tok, eof, window, d.sync)
- }
- } else {
- d.w.writeBlock(tok, eof, nil)
- }
- d.blockStart = index
- return d.w.err
- }
- return nil
-}
-
-// fillWindow will fill the current window with the supplied
-// dictionary and calculate all hashes.
-// This is much faster than doing a full encode.
-// Should only be used after a start/reset.
-func (d *compressor) fillWindow(b []byte) {
- // Do not fill window if we are in store-only or huffman mode.
- if d.level <= 0 && d.level > -MinCustomWindowSize {
- return
- }
- if d.fast != nil {
- // encode the last data, but discard the result
- if len(b) > maxMatchOffset {
- b = b[len(b)-maxMatchOffset:]
- }
- d.fast.Encode(&d.tokens, b)
- d.tokens.Reset()
- return
- }
- s := d.state
- // If we are given too much, cut it.
- if len(b) > windowSize {
- b = b[len(b)-windowSize:]
- }
- // Add all to window.
- n := copy(d.window[d.windowEnd:], b)
-
- // Calculate 256 hashes at the time (more L1 cache hits)
- loops := (n + 256 - minMatchLength) / 256
- for j := range loops {
- startindex := j * 256
- end := min(startindex+256+minMatchLength-1, n)
- tocheck := d.window[startindex:end]
- dstSize := len(tocheck) - minMatchLength + 1
-
- if dstSize <= 0 {
- continue
- }
-
- dst := s.hashMatch[:dstSize]
- bulkHash4(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.
- s.hashPrev[di&windowMask] = s.hashHead[newH]
- // Set the head of the hash chain to us.
- s.hashHead[newH] = uint32(di + s.hashOffset)
- }
- }
- // Update window information.
- d.windowEnd += 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 = s.index, prevHead = s.chainHead-s.hashOffset, prevLength=minMatchLength-1, lookahead
-func (d *compressor) findMatch(pos int, prevHead int, lookahead int) (length, offset int, ok bool) {
- minMatchLook := min(lookahead, maxMatchLength)
-
- win := d.window[0 : pos+minMatchLook]
-
- // We quit when we get a match that's at least nice long
- nice := min(d.nice, len(win)-pos)
-
- // If we've got a match that's good enough, only look in 1/4 the chain.
- tries := d.chain
- length = minMatchLength - 1
-
- wEnd := win[pos+length]
- wPos := win[pos:]
- minIndex := max(pos-windowSize, 0)
- offset = 0
-
- if d.chain < 100 {
- for i := prevHead; tries > 0; tries-- {
- if wEnd == win[i+length] {
- n := matchLen(win[i:i+minMatchLook], wPos)
- if n > length {
- 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
- }
- i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
- if i < minIndex {
- break
- }
- }
- return
- }
-
- // Minimum gain to accept a match.
- cGain := 4
-
- // Some like it higher (CSV), some like it lower (JSON)
- const baseCost = 3
- // Base is 4 bytes at with an additional cost.
- // Matches must be better than this.
-
- for i := prevHead; tries > 0; tries-- {
- if wEnd == win[i+length] {
- n := matchLen(win[i:i+minMatchLook], wPos)
- if n > length {
- // Calculate gain. Estimate
- newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
-
- //fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
- if newGain > cGain {
- length = n
- offset = pos - i
- cGain = newGain
- 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
- }
- i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
- if i < minIndex {
- 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
-}
-
-// hash4 returns a hash representation of the first 4 bytes
-// of the supplied slice.
-// The caller must ensure that len(b) >= 4.
-func hash4(b []byte) uint32 {
- return hash4u(le.Load32(b, 0), hashBits)
-}
-
-// hash4 returns the hash of u to fit in a hash table with h bits.
-// Preferably h should be a constant and should always be <32.
-func hash4u(u uint32, h uint8) uint32 {
- return (u * prime4bytes) >> (32 - h)
-}
-
-// bulkHash4 will compute hashes using the same
-// algorithm as hash4
-func bulkHash4(b []byte, dst []uint32) {
- if len(b) < 4 {
- return
- }
- hb := le.Load32(b, 0)
-
- dst[0] = hash4u(hb, hashBits)
- end := len(b) - 4 + 1
- for i := 1; i < end; i++ {
- hb = (hb >> 8) | uint32(b[i+3])<<24
- dst[i] = hash4u(hb, hashBits)
- }
-}
-
-func (d *compressor) initDeflate() {
- d.window = make([]byte, 2*windowSize)
- d.byteAvailable = false
- 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.chainHead = -1
-}
-
-// 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 = debugDeflate
-
- if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
- return
- }
- if d.windowEnd != s.index && d.chain > 100 {
- // Get literal huffman coder.
- if d.h == nil {
- d.h = newHuffmanEncoder(maxFlateBlockTokens)
- }
- var tmp [256]uint16
- for _, v := range d.window[s.index:d.windowEnd] {
- tmp[v]++
- }
- d.h.generate(tmp[:], 15)
- }
-
- s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
-
- for {
- if sanity && s.index > d.windowEnd {
- panic("index > windowEnd")
- }
- lookahead := d.windowEnd - s.index
- if lookahead < minMatchLength+maxMatchLength {
- if !d.sync {
- return
- }
- 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.AddLiteral(d.window[s.index-1])
- d.byteAvailable = false
- }
- if d.tokens.n > 0 {
- if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- return
- }
- }
- if s.index < s.maxInsertIndex {
- // Update the hash
- hash := hash4(d.window[s.index:])
- ch := s.hashHead[hash]
- s.chainHead = int(ch)
- s.hashPrev[s.index&windowMask] = ch
- s.hashHead[hash] = uint32(s.index + s.hashOffset)
- }
- prevLength := s.length
- prevOffset := s.offset
- s.length = minMatchLength - 1
- s.offset = 0
- minIndex := max(s.index-windowSize, 0)
-
- if s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
- if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, lookahead); ok {
- s.length = newLength
- s.offset = newOffset
- }
- }
-
- if prevLength >= minMatchLength && s.length <= prevLength {
- // No better match, but check for better match at end...
- //
- // Skip forward a number of bytes.
- // Offset of 2 seems to yield best results. 3 is sometimes better.
- const checkOff = 2
-
- // Check all, except full length
- if prevLength < maxMatchLength-checkOff {
- prevIndex := s.index - 1
- if prevIndex+prevLength < s.maxInsertIndex {
- end := min(lookahead, maxMatchLength+checkOff)
- end += prevIndex
-
- // Hash at match end.
- h := hash4(d.window[prevIndex+prevLength:])
- ch2 := int(s.hashHead[h]) - s.hashOffset - prevLength
- if prevIndex-ch2 != prevOffset && ch2 > minIndex+checkOff {
- length := matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:])
- // It seems like a pure length metric is best.
- if length > prevLength {
- prevLength = length
- prevOffset = prevIndex - ch2
-
- // Extend back...
- for i := checkOff - 1; i >= 0; i-- {
- if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i] {
- // Emit tokens we "owe"
- for j := 0; j <= i; j++ {
- d.tokens.AddLiteral(d.window[prevIndex+j])
- if d.tokens.n == maxFlateBlockTokens {
- // The block includes the current character
- if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- s.index++
- if s.index < s.maxInsertIndex {
- h := hash4(d.window[s.index:])
- ch := s.hashHead[h]
- s.chainHead = int(ch)
- s.hashPrev[s.index&windowMask] = ch
- s.hashHead[h] = uint32(s.index + s.hashOffset)
- }
- }
- break
- } else {
- prevLength++
- }
- }
- } else if false {
- // Check one further ahead.
- // Only rarely better, disabled for now.
- prevIndex++
- h := hash4(d.window[prevIndex+prevLength:])
- ch2 := int(s.hashHead[h]) - s.hashOffset - prevLength
- if prevIndex-ch2 != prevOffset && ch2 > minIndex+checkOff {
- length := matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:])
- // It seems like a pure length metric is best.
- if length > prevLength+checkOff {
- prevLength = length
- prevOffset = prevIndex - ch2
- prevIndex--
-
- // Extend back...
- for i := checkOff; i >= 0; i-- {
- if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i-1] {
- // Emit tokens we "owe"
- for j := 0; j <= i; j++ {
- d.tokens.AddLiteral(d.window[prevIndex+j])
- if d.tokens.n == maxFlateBlockTokens {
- // The block includes the current character
- if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- s.index++
- if s.index < s.maxInsertIndex {
- h := hash4(d.window[s.index:])
- ch := s.hashHead[h]
- s.chainHead = int(ch)
- s.hashPrev[s.index&windowMask] = ch
- s.hashHead[h] = uint32(s.index + s.hashOffset)
- }
- }
- break
- } else {
- prevLength++
- }
- }
- }
- }
- }
- }
- }
- }
- // There was a match at the previous step, and the current match is
- // not better. Output the previous match.
- d.tokens.AddMatch(uint32(prevLength-3), 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.
- newIndex := s.index + prevLength - 1
- // Calculate missing hashes
- end := min(newIndex, s.maxInsertIndex)
- end += minMatchLength - 1
- startindex := min(s.index+1, s.maxInsertIndex)
- tocheck := d.window[startindex:end]
- dstSize := len(tocheck) - minMatchLength + 1
- if dstSize > 0 {
- dst := s.hashMatch[:dstSize]
- bulkHash4(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.
- s.hashPrev[di&windowMask] = s.hashHead[newH]
- // Set the head of the hash chain to us.
- s.hashHead[newH] = uint32(di + s.hashOffset)
- }
- }
-
- s.index = newIndex
- d.byteAvailable = false
- s.length = minMatchLength - 1
- if d.tokens.n == maxFlateBlockTokens {
- // The block includes the current character
- if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- s.ii = 0
- } else {
- // Reset, if we got a match this run.
- if s.length >= minMatchLength {
- s.ii = 0
- }
- // We have a byte waiting. Emit it.
- if d.byteAvailable {
- s.ii++
- d.tokens.AddLiteral(d.window[s.index-1])
- if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- s.index++
-
- // If we have a long run of no matches, skip additional bytes
- // Resets when s.ii overflows after 64KB.
- if n := int(s.ii) - d.chain; n > 0 {
- n = 1 + int(n>>6)
- for j := 0; j < n; j++ {
- if s.index >= d.windowEnd-1 {
- break
- }
- d.tokens.AddLiteral(d.window[s.index-1])
- if d.tokens.n == maxFlateBlockTokens {
- if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- // Index...
- if s.index < s.maxInsertIndex {
- h := hash4(d.window[s.index:])
- ch := s.hashHead[h]
- s.chainHead = int(ch)
- s.hashPrev[s.index&windowMask] = ch
- s.hashHead[h] = uint32(s.index + s.hashOffset)
- }
- s.index++
- }
- // Flush last byte
- d.tokens.AddLiteral(d.window[s.index-1])
- d.byteAvailable = false
- // 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, s.index, false); d.err != nil {
- return
- }
- d.tokens.Reset()
- }
- }
- } else {
- s.index++
- d.byteAvailable = true
- }
- }
- }
-}
-
-func (d *compressor) store() {
- if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
- d.err = d.writeStoredBlock(d.window[:d.windowEnd])
- d.windowEnd = 0
- }
-}
-
-// fillWindow will fill the buffer with data for huffman-only compression.
-// The number of bytes copied is returned.
-func (d *compressor) fillBlock(b []byte) int {
- n := copy(d.window[d.windowEnd:], b)
- d.windowEnd += n
- return n
-}
-
-// storeHuff will compress and store the currently added data,
-// if enough has been accumulated or we at the end of the stream.
-// Any error that occurred will be in d.err
-func (d *compressor) storeHuff() {
- if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
- return
- }
- d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
- d.err = d.w.err
- d.windowEnd = 0
-}
-
-// storeFast will compress and store the currently added data,
-// if enough has been accumulated or we at the end of the stream.
-// Any error that occurred will be in d.err
-func (d *compressor) storeFast() {
- // We only compress if we have maxStoreBlockSize.
- if d.windowEnd < len(d.window) {
- if !d.sync {
- return
- }
- // Handle extremely small sizes.
- if d.windowEnd < 128 {
- if d.windowEnd == 0 {
- return
- }
- if d.windowEnd <= 32 {
- d.err = d.writeStoredBlock(d.window[:d.windowEnd])
- } else {
- d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
- d.err = d.w.err
- }
- d.tokens.Reset()
- d.windowEnd = 0
- d.fast.Reset()
- return
- }
- }
-
- d.fast.Encode(&d.tokens, d.window[:d.windowEnd])
- // If we made zero matches, store the block as is.
- if d.tokens.n == 0 {
- d.err = d.writeStoredBlock(d.window[:d.windowEnd])
- // If we removed less than 1/16th, huffman compress the block.
- } else if int(d.tokens.n) > d.windowEnd-(d.windowEnd>>4) {
- d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
- d.err = d.w.err
- } else {
- d.w.writeBlockDynamic(&d.tokens, false, d.window[:d.windowEnd], d.sync)
- d.err = d.w.err
- }
- d.tokens.Reset()
- d.windowEnd = 0
-}
-
-// write will add input byte to the stream.
-// Unless an error occurs all bytes will be consumed.
-func (d *compressor) write(b []byte) (n int, err error) {
- if d.err != nil {
- return 0, d.err
- }
- n = len(b)
- for len(b) > 0 {
- if d.windowEnd == len(d.window) || d.sync {
- d.step(d)
- }
- b = b[d.fill(d, b):]
- if d.err != nil {
- return 0, d.err
- }
- }
- return n, d.err
-}
+func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
+ input := make([]byte, 1<<20)
-func (d *compressor) syncFlush() error {
- d.sync = true
- if d.err != nil {
- return d.err
- }
- 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).fillBlock
- d.step = (*compressor).store
- case level == ConstantCompression:
- d.w.logNewTablePenalty = 10
- d.window = make([]byte, 32<<10)
- d.fill = (*compressor).fillBlock
- d.step = (*compressor).storeHuff
- case level == DefaultCompression:
- level = 5
- fallthrough
- case level >= 1 && level <= 6:
- d.w.logNewTablePenalty = 7
- d.fast = newFastEnc(level)
- d.window = make([]byte, maxStoreBlockSize)
- d.fill = (*compressor).fillBlock
- d.step = (*compressor).storeFast
- case 7 <= level && level <= 9:
- d.w.logNewTablePenalty = 8
- d.state = &advancedState{}
- d.compressionLevel = levels[level]
- d.initDeflate()
- d.fill = (*compressor).fillDeflate
- d.step = (*compressor).deflateLazy
- case -level >= MinCustomWindowSize && -level <= MaxCustomWindowSize:
- d.w.logNewTablePenalty = 7
- d.fast = &fastEncL5Window{maxOffset: int32(-level), cur: maxStoreBlockSize}
- d.window = make([]byte, maxStoreBlockSize)
- d.fill = (*compressor).fillBlock
- d.step = (*compressor).storeFast
- default:
- return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
+ var compressed bytes.Buffer
+ w, err := NewWriter(&compressed, BestCompression)
+ if err != nil {
+ t.Fatalf("NewWriter: %v", err)
}
- d.level = level
- return nil
-}
-
-// reset the state of the compressor.
-func (d *compressor) reset(w io.Writer) {
- d.w.reset(w)
- d.sync = false
- d.err = nil
- // We only need to reset a few things for Snappy.
- if d.fast != nil {
- d.fast.Reset()
- d.windowEnd = 0
- d.tokens.Reset()
- return
+ if _, err := w.Write(input); err != nil {
+ t.Fatalf("Write: %v", err)
}
- switch d.compressionLevel.chain {
- case 0:
- // level was NoCompression or ConstantCompression.
- d.windowEnd = 0
- default:
- s := d.state
- s.chainHead = -1
- for i := range s.hashHead {
- s.hashHead[i] = 0
- }
- for i := range s.hashPrev {
- s.hashPrev[i] = 0
- }
- s.hashOffset = 1
- s.index, d.windowEnd = 0, 0
- d.blockStart, d.byteAvailable = 0, false
- d.tokens.Reset()
- s.length = minMatchLength - 1
- s.offset = 0
- s.ii = 0
- s.maxInsertIndex = 0
+ if err := w.Close(); err != nil {
+ t.Fatalf("Close: %v", err)
}
-}
-func (d *compressor) close() error {
- if d.err != nil {
- return d.err
- }
- 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
+ stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
+ stdOut, err := io.ReadAll(stdReader)
+ _ = stdReader.Close()
+ if err != nil {
+ t.Fatalf("standard reader rejected stream: %v", err)
}
- d.w.flush()
- d.w.reset(nil)
- 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.
-// Level -1 (DefaultCompression) uses the default compression level.
-// Level -2 (ConstantCompression) will use Huffman compression only, giving
-// a very fast compression for all types of input, but sacrificing considerable
-// compression efficiency.
-//
-// If level is in the range [-2, 9] then the error returned will be nil.
-// Otherwise the error returned will be non-nil.
-func NewWriter(w io.Writer, level int) (*Writer, error) {
- var dw Writer
- if err := dw.d.init(w, level); err != nil {
- return nil, err
+ if !bytes.Equal(stdOut, input) {
+ t.Fatalf("standard reader mismatch: got %d bytes, want %d", len(stdOut), len(input))
}
- return &dw, nil
-}
-// 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, error) {
- zw, err := NewWriter(w, level)
+ localReader := NewReader(bytes.NewReader(compressed.Bytes()))
+ localOut, err := io.ReadAll(localReader)
+ _ = localReader.Close()
if err != nil {
- return nil, err
- }
- zw.d.fillWindow(dict)
- zw.dict = append(zw.dict, dict...) // duplicate dictionary for Reset method.
- return zw, err
-}
-
-// MinCustomWindowSize is the minimum window size that can be sent to NewWriterWindow.
-const MinCustomWindowSize = 32
-
-// MaxCustomWindowSize is the maximum custom window that can be sent to NewWriterWindow.
-const MaxCustomWindowSize = windowSize
-
-// NewWriterWindow returns a new Writer compressing data with a custom window size.
-// windowSize must be from MinCustomWindowSize to MaxCustomWindowSize.
-func NewWriterWindow(w io.Writer, windowSize int) (*Writer, error) {
- if windowSize < MinCustomWindowSize {
- return nil, errors.New("flate: requested window size less than MinWindowSize")
+ t.Fatalf("local reader rejected stream: %v", err)
}
- if windowSize > MaxCustomWindowSize {
- return nil, errors.New("flate: requested window size bigger than MaxCustomWindowSize")
+ if !bytes.Equal(localOut, input) {
+ t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
}
- var dw Writer
- if err := dw.d.init(w, -windowSize); err != nil {
- return nil, err
- }
- return &dw, 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
- dict []byte
-}
-
-// 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 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.
-// Calling Flush when there is no pending data still causes the Writer
-// to emit a sync marker of at least 4 bytes.
-// 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()
-}
-
-// Reset discards the writer's state and makes it equivalent to
-// the result of NewWriter or NewWriterDict called with dst
-// and w's level and dictionary.
-func (w *Writer) Reset(dst io.Writer) {
- if len(w.dict) > 0 {
- // w was created with NewWriterDict
- w.d.reset(dst)
- if dst != nil {
- w.d.fillWindow(w.dict)
- }
- } else {
- // w was created with NewWriter
- w.d.reset(dst)
- }
-}
-
-// ResetDict discards the writer's state and makes it equivalent to
-// the result of NewWriter or NewWriterDict called with dst
-// and w's level, but sets a specific dictionary.
-func (w *Writer) ResetDict(dst io.Writer, dict []byte) {
- w.dict = dict
- w.d.reset(dst)
- w.d.fillWindow(w.dict)
}
git status --short
Chunk ID: eeef87 Wall time: 0.0000 seconds Process exited with code 128 Original token count: 18 Output: fatal: not a git repository (or any of the parent directories): .git
sed -n '300,345p' flate/deflate.go
Chunk ID: dc43e6
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 312
Output:
}
if i <= minIndex {
// hashPrev[i & windowMask] has already been overwritten, so stop now.
break
}
i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
if i < minIndex {
break
}
}
return
}
// Minimum gain to accept a match.
cGain := 4
// Some like it higher (CSV), some like it lower (JSON)
const baseCost = 3
// Base is 4 bytes at with an additional cost.
// Matches must be better than this.
for i := prevHead; tries > 0; tries-- {
if wEnd == win[i+length] {
n := matchLen(win[i:i+minMatchLook], wPos)
if n > length {
// Calculate gain. Estimate
newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
//fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
if newGain > cGain {
length = n
offset = pos - i
cGain = newGain
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
}
go test ./flate -run 'TestWriteBlockDynamic|TestLargeLowEntropyRoundTripVisible' -count=1
Chunk ID: 524783
Wall time: 0.5093 seconds
Process exited with code 1
Original token count: 55
Output:
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.55s)
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
FAIL
FAIL [code-host]/klauspost/compress/flate 0.561s
FAIL
cat > /tmp/repro.go <<'EOF'
package main
import (
"bytes"
"fmt"
"io"
stdflate "compress/flate"
kflate "[code-host]/klauspost/compress/flate"
)
func main(){
input:=make([]byte,1<<20)
var b bytes.Buffer
w,_:=kflate.NewWriter(&b,kflate.BestCompression)
w.Write(input); err:=w.Close(); fmt.Println("close",err,"clen",b.Len())
out:=b.Bytes(); if len(out)>64 { out=out[:64] }
fmt.Printf("first % x\n", out)
r:=stdflate.NewReader(bytes.NewReader(b.Bytes()))
dec,err:=io.ReadAll(r); fmt.Println("read",len(dec),err); r.Close()
}
EOF
go run /tmp/repro.goChunk ID: 4ef47f Wall time: 0.6426 seconds Process exited with code 0 Original token count: 67 Output: close <nil> clen 9184 first 04 f8 ff ff ff ff ff ff 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 read 0 flate: corrupt input before offset 10
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 40eb97
Wall time: 0.5635 seconds
Process exited with code 1
Original token count: 66
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.58s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.577s
FAIL
cat > /tmp/repro.go <<'EOF'
package main
import (
"bytes"
"fmt"
"io"
stdflate "compress/flate"
kflate "[code-host]/klauspost/compress/flate"
)
func main(){
input:=make([]byte,1<<20)
var b bytes.Buffer
w,_:=kflate.NewWriter(&b,kflate.BestCompression)
w.Write(input); err:=w.Close(); fmt.Println("close",err,"clen",b.Len())
fmt.Printf("first % x\n", b.Bytes()[:min(64,b.Len())])
r:=stdflate.NewReader(bytes.NewReader(b.Bytes()))
dec,err:=io.ReadAll(r); fmt.Println("std",len(dec),err); r.Close()
kr:=kflate.NewReader(bytes.NewReader(b.Bytes()))
kdec,kerr:=io.ReadAll(kr); fmt.Println("local",len(kdec),kerr); kr.Close()
}
func min(a,b int)int{if a<b{return a};return b}
EOF
go run /tmp/repro.goChunk ID: 600864 Wall time: 0.4959 seconds Process exited with code 0 Original token count: 78 Output: close <nil> clen 9184 first 04 f8 ff ff ff ff ff ff 10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 std 0 flate: corrupt input before offset 10 local 0 flate: corrupt input before offset 10
sed -n '200,430p' flate/huffman_bit_writer.go
Chunk ID: 4fbd5e
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1502
Output:
w.lastHeader = 0
}
n := w.nbytes
for w.nbits != 0 {
w.bytes[n] = byte(w.bits)
w.bits >>= 8
if w.nbits > 8 { // Avoid underflow
w.nbits -= 8
} else {
w.nbits = 0
}
n++
}
w.bits = 0
if n > 0 {
w.write(w.bytes[:n])
}
w.nbytes = 0
}
func (w *huffmanBitWriter) write(b []byte) {
if w.err != nil {
return
}
_, w.err = w.writer.Write(b)
}
func (w *huffmanBitWriter) writeBits(b int32, nb uint8) {
w.bits |= uint64(b) << (w.nbits & 63)
w.nbits += nb
if w.nbits >= 48 {
w.writeOutBits()
}
}
func (w *huffmanBitWriter) writeBytes(bytes []byte) {
if w.err != nil {
return
}
n := w.nbytes
if w.nbits&7 != 0 {
w.err = InternalError("writeBytes with unfinished bits")
return
}
for w.nbits != 0 {
w.bytes[n] = byte(w.bits)
w.bits >>= 8
w.nbits -= 8
n++
}
if n != 0 {
w.write(w.bytes[:n])
}
w.nbytes = 0
w.write(bytes)
}
// RFC 1951 3.2.7 specifies a special run-length encoding for specifying
// the literal and offset lengths arrays (which are concatenated into a single
// array). This method generates that run-length encoding.
//
// The result is written into the codegen array, and the frequencies
// of each code is written into the codegenFreq array.
// Codes 0-15 are single byte codes. Codes 16-18 are followed by additional
// information. Code badCode is an end marker
//
// numLiterals The number of literals in literalEncoding
// numOffsets The number of offsets in offsetEncoding
// litenc, offenc The literal and offset encoder to use
func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int, litEnc, offEnc *huffmanEncoder) {
for i := range w.codegenFreq {
w.codegenFreq[i] = 0
}
// Note that we are using codegen both as a temporary variable for holding
// a copy of the frequencies, and as the place where we put the result.
// This is fine because the output is always shorter than the input used
// so far.
codegen := w.codegen[:] // cache
// Copy the concatenated code sizes to codegen. Put a marker at the end.
cgnl := codegen[:numLiterals]
for i := range cgnl {
cgnl[i] = litEnc.codes[i].len()
}
cgnl = codegen[numLiterals : numLiterals+numOffsets]
for i := range cgnl {
cgnl[i] = offEnc.codes[i].len()
}
codegen[numLiterals+numOffsets] = badCode
size := codegen[0]
count := 1
outIndex := 0
for inIndex := 1; size != badCode; inIndex++ {
// INVARIANT: We have seen "count" copies of size that have not yet
// had output generated for them.
nextSize := codegen[inIndex]
if nextSize == size {
count++
continue
}
// We need to generate codegen indicating "count" of size.
if size != 0 {
codegen[outIndex] = size
outIndex++
w.codegenFreq[size]++
count--
for count >= 3 {
n := min(6, count)
codegen[outIndex] = 16
outIndex++
codegen[outIndex] = uint8(n - 3)
outIndex++
w.codegenFreq[16]++
count -= n
}
} else {
for count >= 11 {
n := min(138, count)
codegen[outIndex] = 18
outIndex++
codegen[outIndex] = uint8(n - 11)
outIndex++
w.codegenFreq[18]++
count -= n
}
if count >= 3 {
// count >= 3 && count <= 10
codegen[outIndex] = 17
outIndex++
codegen[outIndex] = uint8(count - 3)
outIndex++
w.codegenFreq[17]++
count = 0
}
}
count--
for ; count >= 0; count-- {
codegen[outIndex] = size
outIndex++
w.codegenFreq[size]++
}
// Set up invariant for next time through the loop.
size = nextSize
count = 1
}
// Marker indicating the end of the codegen.
codegen[outIndex] = badCode
}
func (w *huffmanBitWriter) codegens() int {
numCodegens := len(w.codegenFreq)
for numCodegens > 4 && w.codegenFreq[codegenOrder[numCodegens-1]] == 0 {
numCodegens--
}
return numCodegens
}
func (w *huffmanBitWriter) headerSize() (size, numCodegens int) {
numCodegens = len(w.codegenFreq)
for numCodegens > 4 && w.codegenFreq[codegenOrder[numCodegens-1]] == 0 {
numCodegens--
}
return 3 + 5 + 5 + 4 + (3 * numCodegens) +
w.codegenEncoding.bitLength(w.codegenFreq[:]) +
int(w.codegenFreq[16])*2 +
int(w.codegenFreq[17])*3 +
int(w.codegenFreq[18])*7, numCodegens
}
// dynamicSize returns the size of dynamically encoded data in bits.
func (w *huffmanBitWriter) dynamicReuseSize(litEnc, offEnc *huffmanEncoder) (size int) {
size = litEnc.bitLength(w.literalFreq[:]) +
offEnc.bitLength(w.offsetFreq[:])
return size
}
// dynamicSize returns the size of dynamically encoded data in bits.
func (w *huffmanBitWriter) dynamicSize(litEnc, offEnc *huffmanEncoder, extraBits int) (size, numCodegens int) {
header, numCodegens := w.headerSize()
size = header +
litEnc.bitLength(w.literalFreq[:]) +
offEnc.bitLength(w.offsetFreq[:]) +
extraBits
return size, numCodegens
}
// extraBitSize will return the number of bits that will be written
// as "extra" bits on matches.
func (w *huffmanBitWriter) extraBitSize() int {
total := 0
for i, n := range w.literalFreq[257:literalCount] {
total += int(n) * int(lengthExtraBits[i&31])
}
for i, n := range w.offsetFreq[:offsetCodeCount] {
total += int(n) * int(offsetExtraBits[i&31])
}
return total
}
// fixedSize returns the size of dynamically encoded data in bits.
func (w *huffmanBitWriter) fixedSize(extraBits int) int {
return 3 +
fixedLiteralEncoding.bitLength(w.literalFreq[:]) +
fixedOffsetEncoding.bitLength(w.offsetFreq[:]) +
extraBits
}
// storedSize calculates the stored size, including header.
// The function returns the size in bits and whether the block
// fits inside a single block.
func (w *huffmanBitWriter) storedSize(in []byte) (int, bool) {
if in == nil {
return 0, false
}
if len(in) <= maxStoreBlockSize {
return (len(in) + 5) * 8, true
}
return 0, false
}
func (w *huffmanBitWriter) writeCode(c hcode) {
// The function does not get inlined if we "& 63" the shift.
w.bits |= c.code64() << (w.nbits & 63)
w.nbits += c.len()
if w.nbits >= 48 {
w.writeOutBits()
}
}
// writeOutBits will write bits to the buffer.
sed -n '430,545p' flate/huffman_bit_writer.go
Chunk ID: e5a8f8
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 608
Output:
// writeOutBits will write bits to the buffer.
func (w *huffmanBitWriter) writeOutBits() {
bits := w.bits
w.bits >>= 48
w.nbits -= 48
n := w.nbytes
// We overwrite, but faster...
le.Store64(w.bytes[:], n, bits)
n += 6
if n >= bufferFlushSize {
if w.err != nil {
n = 0
return
}
w.write(w.bytes[:n])
n = 0
}
w.nbytes = n
}
// Write the header of a dynamic Huffman block to the output stream.
//
// numLiterals The number of literals specified in codegen
// numOffsets The number of offsets specified in codegen
// numCodegens The number of codegens used in codegen
func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) {
if w.err != nil {
return
}
var firstBits int32 = 4
if isEof {
firstBits = 5
}
w.writeBits(firstBits, 3)
w.writeBits(int32(numLiterals-257), 5)
w.writeBits(int32(numOffsets-1), 5)
w.writeBits(int32(numCodegens-4), 4)
for i := range numCodegens {
value := uint(w.codegenEncoding.codes[codegenOrder[i]].len())
w.writeBits(int32(value), 3)
}
i := 0
for {
var codeWord = uint32(w.codegen[i])
i++
if codeWord == badCode {
break
}
w.writeCode(w.codegenEncoding.codes[codeWord])
switch codeWord {
case 16:
w.writeBits(int32(w.codegen[i]), 2)
i++
case 17:
w.writeBits(int32(w.codegen[i]), 3)
i++
case 18:
w.writeBits(int32(w.codegen[i]), 7)
i++
}
}
}
// writeStoredHeader will write a stored header.
// If the stored block is only used for EOF,
// it is replaced with a fixed huffman block.
func (w *huffmanBitWriter) writeStoredHeader(length int, isEof bool) {
if w.err != nil {
return
}
if w.lastHeader > 0 {
// We owe an EOB
w.writeCode(w.literalEncoding.codes[endBlockMarker])
w.lastHeader = 0
}
// To write EOF, use a fixed encoding block. 10 bits instead of 5 bytes.
if length == 0 && isEof {
w.writeFixedHeader(isEof)
// EOB: 7 bits, value: 0
w.writeBits(0, 7)
w.flush()
return
}
var flag int32
if isEof {
flag = 1
}
w.writeBits(flag, 3)
w.flush()
w.writeBits(int32(length), 16)
w.writeBits(int32(^uint16(length)), 16)
}
func (w *huffmanBitWriter) writeFixedHeader(isEof bool) {
if w.err != nil {
return
}
if w.lastHeader > 0 {
// We owe an EOB
w.writeCode(w.literalEncoding.codes[endBlockMarker])
w.lastHeader = 0
}
// Indicate that we are a fixed Huffman block
var value int32 = 2
if isEof {
value = 3
}
rg -n "offsetCode|lengthCode\(|func \(t \*tokens\) AddMatch|extraHist|offHist" flate/token.go flate/huffman_bit_writer.go
Chunk ID: 07c6f0
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 839
Output:
flate/huffman_bit_writer.go:17: offsetCodeCount = 30
flate/huffman_bit_writer.go:124: codegen [literalCount + offsetCodeCount + 1]uint8
flate/huffman_bit_writer.go:152: offsetEncoding: newHuffmanEncoder(offsetCodeCount),
flate/huffman_bit_writer.go:164: a := t.offHist[:offsetCodeCount]
flate/huffman_bit_writer.go:173: a = t.extraHist[:literalCount-256]
flate/huffman_bit_writer.go:394: for i, n := range w.offsetFreq[:offsetCodeCount] {
flate/huffman_bit_writer.go:773: for i, v := range w.offsetFreq[:offsetCodeCount] {
flate/huffman_bit_writer.go:787: //copy(w.literalFreq[256:], t.extraHist[:])
flate/huffman_bit_writer.go:788: *(*[32]uint16)(w.literalFreq[256:]) = t.extraHist
flate/huffman_bit_writer.go:789: w.offsetFreq = t.offHist
flate/huffman_bit_writer.go:818: w.offsetEncoding.generate(w.offsetFreq[:offsetCodeCount], 15)
flate/huffman_bit_writer.go:872: lengthCode := lengthCode(length) & 31
flate/huffman_bit_writer.go:919: offsetCode := (offset >> 16) & 31
flate/huffman_bit_writer.go:921: w.writeCode(offs[offsetCode])
flate/huffman_bit_writer.go:924: c := offs[offsetCode]
flate/huffman_bit_writer.go:943: if offsetCode >= offsetExtraBitsMinCode {
flate/huffman_bit_writer.go:944: offsetComb := offsetCombined[offsetCode]
flate/huffman_bit_writer.go:979: huffOffset = newHuffmanEncoder(offsetCodeCount)
flate/huffman_bit_writer.go:980: huffOffset.generate(w.offsetFreq[:offsetCodeCount], 15)
flate/token.go:89:var offsetCodes = [256]uint32{
flate/token.go:108:// offsetCodes14 are offsetCodes, but with 14 added.
flate/token.go:109:var offsetCodes14 = [256]uint32{
flate/token.go:131: extraHist [32]uint16 // codes 256->maxnumlit
flate/token.go:132: offHist [32]uint16 // offset codes
flate/token.go:148: for i := range t.extraHist[:] {
flate/token.go:149: t.extraHist[i] = 0
flate/token.go:151: for i := range t.offHist[:] {
flate/token.go:152: t.offHist[i] = 0
flate/token.go:166: for i, v := range t.extraHist[:literalCount-256] {
flate/token.go:169: t.extraHist[i] = 1
flate/token.go:172: for i, v := range t.offHist[:offsetCodeCount] {
flate/token.go:174: t.offHist[i] = 1
flate/token.go:240: for i, v := range t.extraHist[1 : literalCount-256] {
flate/token.go:251: for i, v := range t.offHist[:offsetCodeCount] {
flate/token.go:264:func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
flate/token.go:273: oCode := offsetCode(xoffset)
flate/token.go:276: t.extraHist[lengthCodes1[uint8(xlength)]]++
flate/token.go:277: t.offHist[oCode&31]++
flate/token.go:284:func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
flate/token.go:290: oc := offsetCode(xoffset)
flate/token.go:304: t.extraHist[lengthCodes1[uint8(xl)]]++
flate/token.go:305: t.offHist[oc&31]++
flate/token.go:313: t.extraHist[0]++
flate/token.go:362:func lengthCode(len uint8) uint8 { return lengthCodes[len] }
flate/token.go:365:func offsetCode(off uint32) uint32 {
flate/token.go:367: if off < uint32(len(offsetCodes)) {
flate/token.go:368: return offsetCodes[off&255]
flate/token.go:369: } else if off>>7 < uint32(len(offsetCodes)) {
flate/token.go:370: return offsetCodes[(off>>7)&255] + 14
flate/token.go:372: return offsetCodes[(off>>14)&255] + 28
flate/token.go:375: if off < uint32(len(offsetCodes)) {
flate/token.go:376: return offsetCodes[uint8(off)]
flate/token.go:378: return offsetCodes14[uint8(off>>7)]
sed -n '220,285p' flate/token.go
Chunk ID: 22fe8e
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 457
Output:
}
// EstimatedBits will return an minimum size estimated by an *optimal*
// compression of the block.
// The size of the block
func (t *tokens) EstimatedBits() int {
shannon := float32(0)
bits := int(0)
nMatches := 0
total := int(t.n) + t.nFilled
if total > 0 {
invTotal := 1.0 / float32(total)
for _, v := range t.litHist[:] {
if v > 0 {
n := float32(v)
shannon += atLeastOne(-mFastLog2(n*invTotal)) * n
}
}
// Just add 15 for EOB
shannon += 15
for i, v := range t.extraHist[1 : literalCount-256] {
if v > 0 {
n := float32(v)
shannon += atLeastOne(-mFastLog2(n*invTotal)) * n
bits += int(lengthExtraBits[i&31]) * int(v)
nMatches += int(v)
}
}
}
if nMatches > 0 {
invTotal := 1.0 / float32(nMatches)
for i, v := range t.offHist[:offsetCodeCount] {
if v > 0 {
n := float32(v)
shannon += atLeastOne(-mFastLog2(n*invTotal)) * n
bits += int(offsetExtraBits[i&31]) * int(v)
}
}
}
return int(shannon) + bits
}
// AddMatch adds a match to the tokens.
// This function is very sensitive to inlining and right on the border.
func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
if debugDeflate {
if xlength >= maxMatchLength+baseMatchLength {
panic(fmt.Errorf("invalid length: %v", xlength))
}
if xoffset >= maxMatchOffset+baseMatchOffset {
panic(fmt.Errorf("invalid offset: %v", xoffset))
}
}
oCode := offsetCode(xoffset)
xoffset |= oCode << 16
t.extraHist[lengthCodes1[uint8(xlength)]]++
t.offHist[oCode&31]++
t.tokens[t.n] = token(matchType | xlength<<lengthShift | xoffset)
t.n++
}
// AddMatchLong adds a match to the tokens, potentially longer than max match length.
// Length should NOT have the base subtracted, only offset should.
func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
if debugDeflate {
sed -n '285,385p' flate/token.go
Chunk ID: 314ee7
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 566
Output:
if debugDeflate {
if xoffset >= maxMatchOffset+baseMatchOffset {
panic(fmt.Errorf("invalid offset: %v", xoffset))
}
}
oc := offsetCode(xoffset)
xoffset |= oc << 16
for xlength > 0 {
xl := xlength
if xl > 258 {
// We need to have at least baseMatchLength left over for next loop.
if xl > 258+baseMatchLength {
xl = 258
} else {
xl = 258 - baseMatchLength
}
}
xlength -= xl
xl -= baseMatchLength
t.extraHist[lengthCodes1[uint8(xl)]]++
t.offHist[oc&31]++
t.tokens[t.n] = token(matchType | uint32(xl)<<lengthShift | xoffset)
t.n++
}
}
func (t *tokens) AddEOB() {
t.tokens[t.n] = token(endBlockMarker)
t.extraHist[0]++
t.n++
}
func (t *tokens) Slice() []token {
return t.tokens[:t.n]
}
// VarInt returns the tokens as varint encoded bytes.
func (t *tokens) VarInt() []byte {
var b = make([]byte, binary.MaxVarintLen32*int(t.n))
var off int
for _, v := range t.tokens[:t.n] {
off += binary.PutUvarint(b[off:], uint64(v))
}
return b[:off]
}
// FromVarInt restores t to the varint encoded tokens provided.
// Any data in t is removed.
func (t *tokens) FromVarInt(b []byte) error {
var buf = bytes.NewReader(b)
var toks []token
for {
r, err := binary.ReadUvarint(buf)
if err == io.EOF {
break
}
if err != nil {
return err
}
toks = append(toks, token(r))
}
t.indexTokens(toks)
return nil
}
// 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() 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() uint8 { return uint8(t >> lengthShift) }
// Convert length to code.
func lengthCode(len uint8) uint8 { return lengthCodes[len] }
// Returns the offset code corresponding to a specific offset
func offsetCode(off uint32) uint32 {
if false {
if off < uint32(len(offsetCodes)) {
return offsetCodes[off&255]
} else if off>>7 < uint32(len(offsetCodes)) {
return offsetCodes[(off>>7)&255] + 14
} else {
return offsetCodes[(off>>14)&255] + 28
}
}
if off < uint32(len(offsetCodes)) {
return offsetCodes[uint8(off)]
}
return offsetCodes14[uint8(off>>7)]
}
cat > /tmp/headerbits.go <<'EOF'
package main
import "fmt"
func main(){b:=[]byte{0x04,0xf8,0xff,0xff,0xff,0xff,0xff,0xff,0x10,0}; bit:=0; read:=func(n int)int{v:=0; for i:=0;i<n;i++{if b[bit/8]&(1<<(bit%8))!=0{v|=1<<i}; bit++}; return v}; fmt.Println(read(1), read(2), read(5), read(5), read(4)); for i:=0;i<19;i++{fmt.Print(read(3)," ")}; fmt.Println("bit",bit)}
EOF
go run /tmp/headerbits.goChunk ID: 4171bc Wall time: 0.0000 seconds Process exited with code 0 Original token count: 15 Output: 0 2 0 24 15 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 3 0 1 0 bit 74
sed -n '1,190p' flate/huffman_bit_writer.go
Chunk ID: 59c9d0
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1336
Output:
// 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 (
"fmt"
"io"
"math"
"[code-host]/klauspost/compress/internal/le"
)
const (
// The largest offset code.
offsetCodeCount = 30
// The special code used to mark the end of a block.
endBlockMarker = 256
// The first length code.
lengthCodesStart = 257
// The number of codegen codes.
codegenCodeCount = 19
badCode = 255
// maxPredefinedTokens is the maximum number of tokens
// where we check if fixed size is smaller.
maxPredefinedTokens = 250
// bufferFlushSize indicates the buffer size
// after which bytes are flushed to the writer.
// Should preferably be a multiple of 6, since
// we accumulate 6 bytes between writes to the buffer.
bufferFlushSize = 246
)
// Minimum length code that emits bits.
const lengthExtraBitsMinCode = 8
// The number of extra bits needed by length code X - LENGTH_CODES_START.
var lengthExtraBits = [32]uint8{
/* 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,
/* 280 */ 4, 5, 5, 5, 5, 0,
}
// The length indicated by length code X - LENGTH_CODES_START.
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,
}
// Minimum offset code that emits bits.
const offsetExtraBitsMinCode = 4
// offset code word extra bits.
var offsetExtraBits = [32]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,
/* extended window */
14, 14,
}
var offsetCombined = [32]uint32{}
func init() {
var offsetBase = [32]uint32{
/* normal deflate */
0x000000, 0x000001, 0x000002, 0x000003, 0x000004,
0x000006, 0x000008, 0x00000c, 0x000010, 0x000018,
0x000020, 0x000030, 0x000040, 0x000060, 0x000080,
0x0000c0, 0x000100, 0x000180, 0x000200, 0x000300,
0x000400, 0x000600, 0x000800, 0x000c00, 0x001000,
0x001800, 0x002000, 0x003000, 0x004000, 0x006000,
/* extended window */
0x008000, 0x00c000,
}
for i := range offsetCombined[:] {
// Don't use extended window values...
if offsetExtraBits[i] == 0 || offsetBase[i] > 0x006000 {
continue
}
offsetCombined[i] = uint32(offsetExtraBits[i]) | (offsetBase[i] << 8)
}
}
// The odd order in which the codegen code sizes are written.
var codegenOrder = []uint32{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}
type huffmanBitWriter struct {
// writer is the underlying writer.
// Do not use it directly; use the write method, which ensures
// that Write errors are sticky.
writer io.Writer
// Data waiting to be written is bytes[0:nbytes]
// and then the low nbits of bits.
bits uint64
nbits uint8
nbytes uint8
lastHuffMan bool
literalEncoding *huffmanEncoder
tmpLitEncoding *huffmanEncoder
offsetEncoding *huffmanEncoder
codegenEncoding *huffmanEncoder
err error
lastHeader int
// Set between 0 (reused block can be up to 2x the size)
logNewTablePenalty uint
bytes [256 + 8]byte
literalFreq [lengthCodesStart + 32]uint16
offsetFreq [32]uint16
codegenFreq [codegenCodeCount]uint16
// codegen must have an extra space for the final symbol.
codegen [literalCount + offsetCodeCount + 1]uint8
}
// Huffman reuse.
//
// The huffmanBitWriter supports reusing huffman tables and thereby combining block sections.
//
// This is controlled by several variables:
//
// If lastHeader is non-zero the Huffman table can be reused.
// This also indicates that a Huffman table has been generated that can output all
// possible symbols.
// It also indicates that an EOB has not yet been emitted, so if a new tabel is generated
// an EOB with the previous table must be written.
//
// If lastHuffMan is set, a table for outputting literals has been generated and offsets are invalid.
//
// An incoming block estimates the output size of a new table using a 'fresh' by calculating the
// optimal size and adding a penalty in 'logNewTablePenalty'.
// A Huffman table is not optimal, which is why we add a penalty, and generating a new table
// is slower both for compression and decompression.
func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
return &huffmanBitWriter{
writer: w,
literalEncoding: newHuffmanEncoder(literalCount),
tmpLitEncoding: newHuffmanEncoder(literalCount),
codegenEncoding: newHuffmanEncoder(codegenCodeCount),
offsetEncoding: newHuffmanEncoder(offsetCodeCount),
}
}
func (w *huffmanBitWriter) reset(writer io.Writer) {
w.writer = writer
w.bits, w.nbits, w.nbytes, w.err = 0, 0, 0, nil
w.lastHeader = 0
w.lastHuffMan = false
}
func (w *huffmanBitWriter) canReuse(t *tokens) (ok bool) {
a := t.offHist[:offsetCodeCount]
b := w.offsetEncoding.codes
b = b[:len(a)]
for i, v := range a {
if v != 0 && b[i].zero() {
return false
}
}
a = t.extraHist[:literalCount-256]
b = w.literalEncoding.codes[256:literalCount]
b = b[:len(a)]
for i, v := range a {
if v != 0 && b[i].zero() {
return false
}
}
a = t.litHist[:256]
b = w.literalEncoding.codes[:len(a)]
for i, v := range a {
if v != 0 && b[i].zero() {
return false
}
}
return true
}
sed -n '330,385p' flate/huffman_code.go
Chunk ID: 91238c
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 359
Output:
}
list = list[0 : len(list)-int(bits)]
}
}
// Update this Huffman Code object to be the minimum code for the specified frequency count.
//
// freq An array of frequencies, in which frequency[i] gives the frequency of literal i.
// maxBits The maximum number of bits to use for any literal.
func (h *huffmanEncoder) generate(freq []uint16, maxBits int32) {
list := h.freqcache[:len(freq)+1]
codes := h.codes[:len(freq)]
// Number of non-zero literals
count := 0
// Set list to be the set of all non-zero literals and their frequencies
for i, f := range freq {
if f != 0 {
list[count] = literalNode{uint16(i), f}
count++
} else {
codes[i] = 0
}
}
list[count] = literalNode{}
list = list[:count]
if count <= 2 {
// Handle the small cases here, because they are awkward for the general case code. With
// two or fewer literals, everything has bit length 1.
for i, node := range list {
// "list" is in order of increasing literal value.
h.codes[node.literal].set(uint16(i), 1)
}
return
}
sortByFreq(list)
// Get the number of literals for each bit count
bitCount := h.bitCounts(list, maxBits)
// And do the assignment
h.assignEncodingAndSize(bitCount, list)
}
// atLeastOne clamps the result between 1 and 15.
func atLeastOne(v float32) float32 {
if v < 1 {
return 1
}
if v > 15 {
return 15
}
return v
}
func histogram(b []byte, h []uint16) {
if true && len(b) >= 8<<10 {
sed -n '70,145p' flate/huffman_code.go
Chunk ID: d9f3c1
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 459
Output:
*h = hcode(length) | (hcode(code) << 8)
}
func newhcode(code uint16, length uint8) hcode {
return hcode(length) | (hcode(code) << 8)
}
func reverseBits(number uint16, bitLength byte) uint16 {
return bits.Reverse16(number << ((16 - bitLength) & 15))
}
func maxNode() literalNode { return literalNode{math.MaxUint16, math.MaxUint16} }
func newHuffmanEncoder(size int) *huffmanEncoder {
// 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
func generateFixedLiteralEncoding() *huffmanEncoder {
h := newHuffmanEncoder(literalCount)
codes := h.codes
var ch uint16
for ch = range uint16(literalCount) {
var bits uint16
var size uint8
switch {
case ch < 144:
// size 8, 000110000 .. 10111111
bits = ch + 48
size = 8
case ch < 256:
// size 9, 110010000 .. 111111111
bits = ch + 400 - 144
size = 9
case ch < 280:
// size 7, 0000000 .. 0010111
bits = ch - 256
size = 7
default:
// size 8, 11000000 .. 11000111
bits = ch + 192 - 280
size = 8
}
codes[ch] = newhcode(reverseBits(bits, size), size)
}
return h
}
func generateFixedOffsetEncoding() *huffmanEncoder {
h := newHuffmanEncoder(30)
codes := h.codes
for ch := range codes {
codes[ch] = newhcode(reverseBits(uint16(ch), 5), 5)
}
return h
}
var fixedLiteralEncoding = generateFixedLiteralEncoding()
var fixedOffsetEncoding = generateFixedOffsetEncoding()
func (h *huffmanEncoder) bitLength(freq []uint16) int {
var total int
for i, f := range freq {
if f != 0 {
total += int(f) * int(h.codes[i].len())
}
}
return total
}
func (h *huffmanEncoder) bitLengthRaw(b []byte) int {
var total int
for _, f := range b {
total += int(h.codes[f].len())
rg -n "func \(w \*huffmanBitWriter\) reset|newHuffmanBitWriter|codegenEncoding" flate/huffman_bit_writer.go flate/*.go
Chunk ID: f1602b
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 593
Output:
flate/deflate.go:786: d.w = newHuffmanBitWriter(w)
flate/huffman_bit_writer.go:113: codegenEncoding *huffmanEncoder
flate/huffman_bit_writer.go:146:func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
flate/huffman_bit_writer.go:151: codegenEncoding: newHuffmanEncoder(codegenCodeCount),
flate/huffman_bit_writer.go:156:func (w *huffmanBitWriter) reset(writer io.Writer) {
flate/huffman_bit_writer.go:364: w.codegenEncoding.bitLength(w.codegenFreq[:]) +
flate/huffman_bit_writer.go:472: value := uint(w.codegenEncoding.codes[codegenOrder[i]].len())
flate/huffman_bit_writer.go:483: w.writeCode(w.codegenEncoding.codes[codeWord])
flate/huffman_bit_writer.go:588: w.codegenEncoding.generate(w.codegenFreq[:], 7)
flate/huffman_bit_writer.go:718: w.codegenEncoding.generate(w.codegenFreq[:], 7)
flate/huffman_bit_writer.go:977: w := newHuffmanBitWriter(nil)
flate/huffman_bit_writer.go:1076: w.codegenEncoding.generate(w.codegenFreq[:], 7)
flate/huffman_bit_writer_test.go:48: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer_test.go:213: bw := newHuffmanBitWriter(f)
flate/huffman_bit_writer_test.go:224: bw := newHuffmanBitWriter(f)
flate/huffman_bit_writer_test.go:242: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer_test.go:277: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer_test.go:349: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer.go:113: codegenEncoding *huffmanEncoder
flate/huffman_bit_writer.go:146:func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
flate/huffman_bit_writer.go:151: codegenEncoding: newHuffmanEncoder(codegenCodeCount),
flate/huffman_bit_writer.go:156:func (w *huffmanBitWriter) reset(writer io.Writer) {
flate/huffman_bit_writer.go:364: w.codegenEncoding.bitLength(w.codegenFreq[:]) +
flate/huffman_bit_writer.go:472: value := uint(w.codegenEncoding.codes[codegenOrder[i]].len())
flate/huffman_bit_writer.go:483: w.writeCode(w.codegenEncoding.codes[codeWord])
flate/huffman_bit_writer.go:588: w.codegenEncoding.generate(w.codegenFreq[:], 7)
flate/huffman_bit_writer.go:718: w.codegenEncoding.generate(w.codegenFreq[:], 7)
flate/huffman_bit_writer.go:977: w := newHuffmanBitWriter(nil)
flate/huffman_bit_writer.go:1076: w.codegenEncoding.generate(w.codegenFreq[:], 7)
flate/stateless.go:60: return newHuffmanBitWriter(nil)
flate/token_test.go:34: wr := newHuffmanBitWriter(&buf)
cat > /tmp/levels.go <<'EOF'
package main
import (
"bytes"; "fmt"; "io"; std "compress/flate"; k "[code-host]/klauspost/compress/flate"
)
func main(){ input:=make([]byte,1<<20); for _, lvl:= range []int{k.NoCompression,k.HuffmanOnly,k.BestSpeed,5,7,8,9,k.DefaultCompression}{ var b bytes.Buffer; w,_:=k.NewWriter(&b,lvl); w.Write(input); cerr:=w.Close(); r:=std.NewReader(bytes.NewReader(b.Bytes())); out,err:=io.ReadAll(r); r.Close(); fmt.Println("lvl",lvl,"close",cerr,"clen",b.Len(),"out",len(out),"err",err,"first",fmt.Sprintf("% x", b.Bytes()[:min(10,b.Len())])) }}
func min(a,b int)int{if a<b{return a};return b}
EOF
go run /tmp/levels.goChunk ID: c2eaa4 Wall time: 0.5088 seconds Process exited with code 0 Original token count: 181 Output: lvl 0 close <nil> clen 1048663 out 1048576 err <nil> first 00 ff ff 00 00 00 00 00 00 00 lvl -2 close <nil> clen 131085 out 1048576 err <nil> first 04 c0 81 00 00 00 00 00 10 ff lvl 1 close <nil> clen 1090 out 1048576 err <nil> first ec c1 01 0d 00 00 08 04 a1 eb lvl 5 close <nil> clen 1089 out 1048576 err <nil> first ec c0 01 0d 00 00 00 01 30 fd lvl 7 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl 8 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl 9 close <nil> clen 9184 out 0 err flate: corrupt input before offset 10 first 04 f8 ff ff ff ff ff ff 10 00 lvl -1 close <nil> clen 1089 out 1048576 err <nil> first ec c0 01 0d 00 00 00 01 30 fd
go test ./flate -run 'TestWriteBlockDynamic|TestWriteBlock|TestLargeLowEntropyRoundTripVisible' -count=1 -v
Chunk ID: f1098c
Wall time: 0.5264 seconds
Process exited with code 1
Original token count: 2919
Output:
=== RUN TestWriteBlock
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestWriteBlock (0.01s)
=== RUN TestWriteBlockDynamic
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestWriteBlockDynamic (0.01s)
=== RUN TestWriteBlockDynamicSync
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestWriteBlockDynamicSync (0.01s)
=== RUN TestLargeLowEntropyRoundTripVisible
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.56s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.582s
FAIL
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) {
if w.err != nil {
return
}
+ println("dynhdr", numLiterals, numOffsets, numCodegens, isEof, "freq256", w.literalFreq[256], "freq285", w.literalFreq[285], "off0", w.offsetFreq[0])
var firstBits int32 = 4
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 69ab45
Wall time: 0.7785 seconds
Process exited with code 1
Original token count: 105
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
dynhdr 1 1 18 false freq256 1 freq285 0 off0 1
dynhdr 286 1 18 false freq256 1 freq285 222 off0 222
dynhdr 286 1 18 false freq256 1 freq285 3589 off0 3590
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.55s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.552s
FAIL
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
- println("dynhdr", numLiterals, numOffsets, numCodegens, isEof, "freq256", w.literalFreq[256], "freq285", w.literalFreq[285], "off0", w.offsetFreq[0])
var firstBits int32 = 4
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
if fillReuse && !sync {
w.fillTokens()
numLiterals, numOffsets = maxNumLit, maxNumDist
} else {
w.literalFreq[endBlockMarker] = 1
+ if numLiterals <= endBlockMarker {
+ numLiterals = endBlockMarker + 1
+ }
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 9246c8 Wall time: 1.0556 seconds Process exited with code 0 Original token count: 39 Output: === RUN TestLargeLowEntropyRoundTripVisible --- PASS: TestLargeLowEntropyRoundTripVisible (0.61s) PASS ok [code-host]/klauspost/compress/flate 0.609s
go test ./flate -run 'TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: 55b4ce
Wall time: 0.4962 seconds
Process exited with code 1
Original token count: 1039
Output:
--- FAIL: TestWriteBlockDynamic (0.01s)
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.dyn.expect-noinput"
huffman_bit_writer_test.go:282: writeBlock did not yield expected result for file "testdata/huffman-rand-1k.dyn.expect-noinput" with input. See "testdata/huffman-rand-1k.dyn.expect-noinput.got"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:300: reset: writeBlock did not yield expected result for file "testdata/huffman-rand-1k.dyn.expect-noinput" without input. See "testdata/huffman-rand-1k.dyn.expect-noinput.reset.got"
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
FAIL
FAIL [code-host]/klauspost/compress/flate 0.053s
FAIL
go run /tmp/levels.go
Chunk ID: 57a512 Wall time: 1.0144 seconds Process exited with code 0 Original token count: 174 Output: lvl 0 close <nil> clen 1048663 out 1048576 err <nil> first 00 ff ff 00 00 00 00 00 00 00 lvl -2 close <nil> clen 131085 out 1048576 err <nil> first 04 c0 81 00 00 00 00 00 10 ff lvl 1 close <nil> clen 1090 out 1048576 err <nil> first ec c1 01 0d 00 00 08 04 a1 eb lvl 5 close <nil> clen 1089 out 1048576 err <nil> first ec c0 01 0d 00 00 00 01 30 fd lvl 7 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl 8 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl 9 close <nil> clen 9186 out 1048576 err <nil> first 04 c0 81 00 00 00 00 00 10 ff lvl -1 close <nil> clen 1089 out 1048576 err <nil> first ec c0 01 0d 00 00 00 01 30 fd
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
if fillReuse && !sync {
w.fillTokens()
numLiterals, numOffsets = maxNumLit, maxNumDist
} else {
w.literalFreq[endBlockMarker] = 1
- if numLiterals <= endBlockMarker {
- numLiterals = endBlockMarker + 1
- }
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
*** Begin Patch
*** Update File: /app/flate/deflate.go
@@
func (d *compressor) writeBlock(tok *tokens, index int, eof bool) error {
if index > 0 || eof {
var window []byte
if d.blockStart <= index {
window = d.window[d.blockStart:index]
}
+ println("writeBlock", "tok", tok.n, "idx", index, "bs", d.blockStart, "win", len(window), "eof", eof, "sync", d.sync, "lit0", tok.litHist[0], "extra1", tok.extraHist[1], "extra29", tok.extraHist[29], "off0", tok.offHist[0])
d.blockStart = index
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/deflate.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: ec824d
Wall time: 0.7693 seconds
Process exited with code 1
Original token count: 148
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
writeBlock tok 32768 idx 32768 bs 0 win 32768 eof false sync false lit0 32768 extra1 0 extra29 0 off0 0
writeBlock tok 32768 idx 57054 bs 2147483647 win 0 eof false sync false lit0 32546 extra1 0 extra29 222 off0 222
writeBlock tok 3590 idx 65536 bs 2146631679 win 0 eof false sync true lit0 0 extra1 0 extra29 3589 off0 3590
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.56s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.561s
FAIL
*** Begin Patch
*** Update File: /app/flate/deflate.go
@@
- println("writeBlock", "tok", tok.n, "idx", index, "bs", d.blockStart, "win", len(window), "eof", eof, "sync", d.sync, "lit0", tok.litHist[0], "extra1", tok.extraHist[1], "extra29", tok.extraHist[29], "off0", tok.offHist[0])
d.blockStart = index
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/deflate.go
*** Begin Patch
*** Update File: /app/flate/deflate.go
@@
}
var tmp [256]uint16
for _, v := range d.window[s.index:d.windowEnd] {
- tmp[v]++
+ if tmp[v] < math.MaxUint16 {
+ tmp[v]++
+ }
}
d.h.generate(tmp[:], 15)
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/deflate.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 38c0dd Wall time: 0.5342 seconds Process exited with code 0 Original token count: 39 Output: === RUN TestLargeLowEntropyRoundTripVisible --- PASS: TestLargeLowEntropyRoundTripVisible (0.00s) PASS ok [code-host]/klauspost/compress/flate 0.005s
go test ./flate -run 'TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: c8caa6 Wall time: 0.5422 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 0.014s
go run /tmp/levels.go
Chunk ID: 81cef7 Wall time: 0.4083 seconds Process exited with code 0 Original token count: 174 Output: lvl 0 close <nil> clen 1048663 out 1048576 err <nil> first 00 ff ff 00 00 00 00 00 00 00 lvl -2 close <nil> clen 131085 out 1048576 err <nil> first 04 c0 81 00 00 00 00 00 10 ff lvl 1 close <nil> clen 1090 out 1048576 err <nil> first ec c1 01 0d 00 00 08 04 a1 eb lvl 5 close <nil> clen 1089 out 1048576 err <nil> first ec c0 01 0d 00 00 00 01 30 fd lvl 7 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl 8 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl 9 close <nil> clen 1034 out 1048576 err <nil> first ec c0 31 01 00 00 00 c2 20 fb lvl -1 close <nil> clen 1089 out 1048576 err <nil> first ec c0 01 0d 00 00 00 01 30 fd
*** Begin Patch
*** Update File: /app/flate/large_low_entropy_test.go
@@
import (
"bytes"
stdflate "compress/flate"
+ "fmt"
"io"
"testing"
)
func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
input := make([]byte, 1<<20)
+ for _, level := range []int{NoCompression, HuffmanOnly, BestSpeed, DefaultCompression, 7, 8, BestCompression} {
+ t.Run(fmt.Sprintf("level=%d/single", level), func(t *testing.T) {
+ roundTripGenerated(t, input, level, nil)
+ })
+ t.Run(fmt.Sprintf("level=%d/chunked", level), func(t *testing.T) {
+ roundTripGenerated(t, input, level, []int{1, 257, 8191, 65537})
+ })
+ }
+}
+
+func TestGeneratedEntropyRoundTrips(t *testing.T) {
+ inputs := map[string][]byte{
+ "low": bytes.Repeat([]byte{0}, 128<<10),
+ "medium": generatedPattern(128 << 10),
+ "high": generatedRandom(128 << 10),
+ }
+ levels := []int{NoCompression, HuffmanOnly, BestSpeed, DefaultCompression, 7, 8, BestCompression}
+
+ for name, input := range inputs {
+ for _, level := range levels {
+ t.Run(fmt.Sprintf("%s/level=%d/single", name, level), func(t *testing.T) {
+ roundTripGenerated(t, input, level, nil)
+ })
+ t.Run(fmt.Sprintf("%s/level=%d/chunked", name, level), func(t *testing.T) {
+ roundTripGenerated(t, input, level, []int{3, 511, 4096, 16383})
+ })
+ }
+ }
+}
+
+func roundTripGenerated(t *testing.T, input []byte, level int, chunks []int) {
+ t.Helper()
+
var compressed bytes.Buffer
- w, err := NewWriter(&compressed, BestCompression)
+ w, err := NewWriter(&compressed, level)
if err != nil {
t.Fatalf("NewWriter: %v", err)
}
- if _, err := w.Write(input); err != nil {
- t.Fatalf("Write: %v", err)
+ if len(chunks) == 0 {
+ if _, err := w.Write(input); err != nil {
+ t.Fatalf("Write: %v", err)
+ }
+ } else {
+ for pos, chunk := 0, 0; pos < len(input); chunk++ {
+ n := chunks[chunk%len(chunks)]
+ if n > len(input)-pos {
+ n = len(input) - pos
+ }
+ if _, err := w.Write(input[pos : pos+n]); err != nil {
+ t.Fatalf("Write chunk at %d: %v", pos, err)
+ }
+ pos += n
+ }
}
if err := w.Close(); err != nil {
t.Fatalf("Close: %v", err)
@@
if !bytes.Equal(localOut, input) {
t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
}
}
+
+func generatedPattern(size int) []byte {
+ out := make([]byte, size)
+ pattern := []byte("DEFLATE block-boundary pattern 0123456789\n")
+ for i := range out {
+ out[i] = pattern[i%len(pattern)]
+ if i%1021 == 0 {
+ out[i] = byte(i)
+ }
+ }
+ return out
+}
+
+func generatedRandom(size int) []byte {
+ out := make([]byte, size)
+ var x uint32 = 0x12345678
+ for i := range out {
+ x ^= x << 13
+ x ^= x >> 17
+ x ^= x << 5
+ out[i] = byte(x)
+ }
+ return out
+}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/large_low_entropy_test.go
gofmt -w flate/large_low_entropy_test.go flate/deflate.go
Chunk ID: f1429b Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'TestLargeLowEntropyRoundTripVisible|TestGeneratedEntropyRoundTrips' -count=1
Chunk ID: 093b23 Wall time: 0.2903 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 0.110s
rg -n "regression|testdata/fuzz|\.golden|huffman|large" flate/*_test.go
Chunk ID: 1cec91
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 912
Output:
flate/flate_test.go:27: var h huffmanDecoder
flate/flate_test.go:37: var h huffmanDecoder
flate/flate_test.go:47: var h huffmanDecoder
flate/flate_test.go:58: var h huffmanDecoder
flate/flate_test.go:74: // Test fuzzer regressions
flate/flate_test.go:75: data, err := os.ReadFile("testdata/regression.zip")
flate/flate_test.go:178: var h huffmanDecoder
flate/flate_test.go:240: "complete HCLenTree, complete HLitTree, too large HDistTree",
flate/deflate_test.go:62: {largeDataChunk()},
flate/deflate_test.go:76:func largeDataChunk() []byte {
flate/deflate_test.go:129:// This tests missing hash references in a very large input.
flate/huffman_bit_writer_test.go:19:// TestBlockHuff tests huffman encoding against reference files
flate/huffman_bit_writer_test.go:20:// to detect possible regressions.
flate/huffman_bit_writer_test.go:25: match, err := filepath.Glob("testdata/huffman-*.in")
flate/huffman_bit_writer_test.go:33: out = in[:len(in)-len(".in")] + ".golden"
flate/huffman_bit_writer_test.go:110: input: "testdata/huffman-null-max.in",
flate/huffman_bit_writer_test.go:111: want: "testdata/huffman-null-max.%s.expect",
flate/huffman_bit_writer_test.go:112: wantNoInput: "testdata/huffman-null-max.%s.expect-noinput",
flate/huffman_bit_writer_test.go:116: input: "testdata/huffman-pi.in",
flate/huffman_bit_writer_test.go:117: want: "testdata/huffman-pi.%s.expect",
flate/huffman_bit_writer_test.go:118: wantNoInput: "testdata/huffman-pi.%s.expect-noinput",
flate/huffman_bit_writer_test.go:122: input: "testdata/huffman-rand-1k.in",
flate/huffman_bit_writer_test.go:123: want: "testdata/huffman-rand-1k.%s.expect",
flate/huffman_bit_writer_test.go:124: wantNoInput: "testdata/huffman-rand-1k.%s.expect-noinput",
flate/huffman_bit_writer_test.go:128: input: "testdata/huffman-rand-limit.in",
flate/huffman_bit_writer_test.go:129: want: "testdata/huffman-rand-limit.%s.expect",
flate/huffman_bit_writer_test.go:130: wantNoInput: "testdata/huffman-rand-limit.%s.expect-noinput",
flate/huffman_bit_writer_test.go:134: input: "testdata/huffman-shifts.in",
flate/huffman_bit_writer_test.go:135: want: "testdata/huffman-shifts.%s.expect",
flate/huffman_bit_writer_test.go:136: wantNoInput: "testdata/huffman-shifts.%s.expect-noinput",
flate/huffman_bit_writer_test.go:140: input: "testdata/huffman-text-shift.in",
flate/huffman_bit_writer_test.go:141: want: "testdata/huffman-text-shift.%s.expect",
flate/huffman_bit_writer_test.go:142: wantNoInput: "testdata/huffman-text-shift.%s.expect-noinput",
flate/huffman_bit_writer_test.go:146: input: "testdata/huffman-text.in",
flate/huffman_bit_writer_test.go:147: want: "testdata/huffman-text.%s.expect",
flate/huffman_bit_writer_test.go:148: wantNoInput: "testdata/huffman-text.%s.expect-noinput",
flate/huffman_bit_writer_test.go:152: input: "testdata/huffman-zero.in",
flate/huffman_bit_writer_test.go:153: want: "testdata/huffman-zero.%s.expect",
flate/huffman_bit_writer_test.go:154: wantNoInput: "testdata/huffman-zero.%s.expect-noinput",
flate/huffman_bit_writer_test.go:310:func writeToType(t *testing.T, ttype string, bw *huffmanBitWriter, tok tokens, input []byte) {
flate/fuzz_test.go:29: fuzz.AddFromZip(f, "testdata/regression.zip", fuzz.TypeRaw, false)
flate/fuzz_test.go:30: fuzz.AddFromZip(f, "testdata/fuzz/encode-raw-corpus.zip", fuzz.TypeRaw, testing.Short())
flate/fuzz_test.go:31: fuzz.AddFromZip(f, "testdata/fuzz/FuzzEncoding.zip", fuzz.TypeGoFuzz, testing.Short())
flate/writer_test.go:69: data, err := os.ReadFile("testdata/regression.zip")
go test ./flate -run 'TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync|TestLargeLowEntropyRoundTripVisible|TestGeneratedEntropyRoundTrips|TestRegression|Regression|Golden|Fuzz' -count=1
Chunk ID: 4a1eca Wall time: 2.6510 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 2.703s
go build ./...
Chunk ID: 02314e Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'TestBlockHuff|TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: cdb5b7 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 0.021s
go test ./flate -run 'TestBestSpeed|TestBestSpeedMatch|TestVeryLongSparseChunk|TestWriter|TestReader|TestInflate|TestDeflate|TestGeneratedEntropyRoundTrips|TestLargeLowEntropyRoundTripVisible' -count=1
Chunk ID: eee341
Wall time: 3.8380 seconds
Process exited with code 1
Original token count: 355
Output:
--- FAIL: TestDeflateInflateString (0.00s)
deflate_test.go:387: open ../testdata/e.txt: no such file or directory
deflate_test.go:320: level: 0 - Size:0.00%, 2 b
deflate_test.go:320: level: 1 - Size:0.00%, 2 b
deflate_test.go:320: level: 2 - Size:0.00%, 2 b
deflate_test.go:320: level: 3 - Size:0.00%, 2 b
deflate_test.go:320: level: 4 - Size:0.00%, 2 b
deflate_test.go:320: level: 5 - Size:0.00%, 2 b
deflate_test.go:320: level: 6 - Size:0.00%, 2 b
deflate_test.go:320: level: 7 - Size:0.00%, 2 b
deflate_test.go:320: level: 8 - Size:0.00%, 2 b
deflate_test.go:320: level: 9 - Size:0.00%, 2 b
deflate_test.go:320: level: -2 - Size:0.00%, 2 b
deflate_test.go:387: open ../testdata/Mark.Twain-Tom.Sawyer.txt: no such file or directory
deflate_test.go:320: level: 0 - Size:0.00%, 2 b
deflate_test.go:320: level: 1 - Size:0.00%, 2 b
deflate_test.go:320: level: 2 - Size:0.00%, 2 b
deflate_test.go:320: level: 3 - Size:0.00%, 2 b
deflate_test.go:320: level: 4 - Size:0.00%, 2 b
deflate_test.go:320: level: 5 - Size:0.00%, 2 b
deflate_test.go:320: level: 6 - Size:0.00%, 2 b
deflate_test.go:320: level: 7 - Size:0.00%, 2 b
deflate_test.go:320: level: 8 - Size:0.00%, 2 b
deflate_test.go:320: level: 9 - Size:0.00%, 2 b
deflate_test.go:320: level: -2 - Size:0.00%, 2 b
FAIL
FAIL [code-host]/klauspost/compress/flate 3.870s
FAIL
sed -n '414,432p' flate/deflate.go
Chunk ID: 2f8ebb
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 111
Output:
if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
return
}
if d.windowEnd != s.index && d.chain > 100 {
// Get literal huffman coder.
if d.h == nil {
d.h = newHuffmanEncoder(maxFlateBlockTokens)
}
var tmp [256]uint16
for _, v := range d.window[s.index:d.windowEnd] {
if tmp[v] < math.MaxUint16 {
tmp[v]++
}
}
d.h.generate(tmp[:], 15)
}
s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
sed -n '1,180p' flate/large_low_entropy_test.go
Chunk ID: 624f07
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 751
Output:
package flate
import (
"bytes"
stdflate "compress/flate"
"fmt"
"io"
"testing"
)
func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
input := make([]byte, 1<<20)
for _, level := range []int{NoCompression, HuffmanOnly, BestSpeed, DefaultCompression, 7, 8, BestCompression} {
t.Run(fmt.Sprintf("level=%d/single", level), func(t *testing.T) {
roundTripGenerated(t, input, level, nil)
})
t.Run(fmt.Sprintf("level=%d/chunked", level), func(t *testing.T) {
roundTripGenerated(t, input, level, []int{1, 257, 8191, 65537})
})
}
}
func TestGeneratedEntropyRoundTrips(t *testing.T) {
inputs := map[string][]byte{
"low": bytes.Repeat([]byte{0}, 128<<10),
"medium": generatedPattern(128 << 10),
"high": generatedRandom(128 << 10),
}
levels := []int{NoCompression, HuffmanOnly, BestSpeed, DefaultCompression, 7, 8, BestCompression}
for name, input := range inputs {
for _, level := range levels {
t.Run(fmt.Sprintf("%s/level=%d/single", name, level), func(t *testing.T) {
roundTripGenerated(t, input, level, nil)
})
t.Run(fmt.Sprintf("%s/level=%d/chunked", name, level), func(t *testing.T) {
roundTripGenerated(t, input, level, []int{3, 511, 4096, 16383})
})
}
}
}
func roundTripGenerated(t *testing.T, input []byte, level int, chunks []int) {
t.Helper()
var compressed bytes.Buffer
w, err := NewWriter(&compressed, level)
if err != nil {
t.Fatalf("NewWriter: %v", err)
}
if len(chunks) == 0 {
if _, err := w.Write(input); err != nil {
t.Fatalf("Write: %v", err)
}
} else {
for pos, chunk := 0, 0; pos < len(input); chunk++ {
n := chunks[chunk%len(chunks)]
if n > len(input)-pos {
n = len(input) - pos
}
if _, err := w.Write(input[pos : pos+n]); err != nil {
t.Fatalf("Write chunk at %d: %v", pos, err)
}
pos += n
}
}
if err := w.Close(); err != nil {
t.Fatalf("Close: %v", err)
}
stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
stdOut, err := io.ReadAll(stdReader)
_ = stdReader.Close()
if err != nil {
t.Fatalf("standard reader rejected stream: %v", err)
}
if !bytes.Equal(stdOut, input) {
t.Fatalf("standard reader mismatch: got %d bytes, want %d", len(stdOut), len(input))
}
localReader := NewReader(bytes.NewReader(compressed.Bytes()))
localOut, err := io.ReadAll(localReader)
_ = localReader.Close()
if err != nil {
t.Fatalf("local reader rejected stream: %v", err)
}
if !bytes.Equal(localOut, input) {
t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
}
}
func generatedPattern(size int) []byte {
out := make([]byte, size)
pattern := []byte("DEFLATE block-boundary pattern 0123456789\n")
for i := range out {
out[i] = pattern[i%len(pattern)]
if i%1021 == 0 {
out[i] = byte(i)
}
}
return out
}
func generatedRandom(size int) []byte {
out := make([]byte, size)
var x uint32 = 0x12345678
for i := range out {
x ^= x << 13
x ^= x >> 17
x ^= x << 5
out[i] = byte(x)
}
return out
}
go test ./flate -run 'TestLargeLowEntropyRoundTripVisible|TestGeneratedEntropyRoundTrips|TestBlockHuff|TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync|TestBadHuffman|TestInvalid|TestReaderTruncated|TestRegression|FuzzEncoding' -count=1
Chunk ID: 56c4ae Wall time: 2.2677 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 2.325s
go build ./...
Chunk ID: 987885 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
nl -ba flate/deflate.go | sed -n '418,429p'
Chunk ID: 164645
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 97
Output:
418 if d.windowEnd != s.index && d.chain > 100 {
419 // Get literal huffman coder.
420 if d.h == nil {
421 d.h = newHuffmanEncoder(maxFlateBlockTokens)
422 }
423 var tmp [256]uint16
424 for _, v := range d.window[s.index:d.windowEnd] {
425 if tmp[v] < math.MaxUint16 {
426 tmp[v]++
427 }
428 }
429 d.h.generate(tmp[:], 15)
nl -ba flate/large_low_entropy_test.go | sed -n '1,150p'
Chunk ID: b48f7d
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 952
Output:
1 package flate
2
3 import (
4 "bytes"
5 stdflate "compress/flate"
6 "fmt"
7 "io"
8 "testing"
9 )
10
11 func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
12 input := make([]byte, 1<<20)
13
14 for _, level := range []int{NoCompression, HuffmanOnly, BestSpeed, DefaultCompression, 7, 8, BestCompression} {
15 t.Run(fmt.Sprintf("level=%d/single", level), func(t *testing.T) {
16 roundTripGenerated(t, input, level, nil)
17 })
18 t.Run(fmt.Sprintf("level=%d/chunked", level), func(t *testing.T) {
19 roundTripGenerated(t, input, level, []int{1, 257, 8191, 65537})
20 })
21 }
22 }
23
24 func TestGeneratedEntropyRoundTrips(t *testing.T) {
25 inputs := map[string][]byte{
26 "low": bytes.Repeat([]byte{0}, 128<<10),
27 "medium": generatedPattern(128 << 10),
28 "high": generatedRandom(128 << 10),
29 }
30 levels := []int{NoCompression, HuffmanOnly, BestSpeed, DefaultCompression, 7, 8, BestCompression}
31
32 for name, input := range inputs {
33 for _, level := range levels {
34 t.Run(fmt.Sprintf("%s/level=%d/single", name, level), func(t *testing.T) {
35 roundTripGenerated(t, input, level, nil)
36 })
37 t.Run(fmt.Sprintf("%s/level=%d/chunked", name, level), func(t *testing.T) {
38 roundTripGenerated(t, input, level, []int{3, 511, 4096, 16383})
39 })
40 }
41 }
42 }
43
44 func roundTripGenerated(t *testing.T, input []byte, level int, chunks []int) {
45 t.Helper()
46
47 var compressed bytes.Buffer
48 w, err := NewWriter(&compressed, level)
49 if err != nil {
50 t.Fatalf("NewWriter: %v", err)
51 }
52 if len(chunks) == 0 {
53 if _, err := w.Write(input); err != nil {
54 t.Fatalf("Write: %v", err)
55 }
56 } else {
57 for pos, chunk := 0, 0; pos < len(input); chunk++ {
58 n := chunks[chunk%len(chunks)]
59 if n > len(input)-pos {
60 n = len(input) - pos
61 }
62 if _, err := w.Write(input[pos : pos+n]); err != nil {
63 t.Fatalf("Write chunk at %d: %v", pos, err)
64 }
65 pos += n
66 }
67 }
68 if err := w.Close(); err != nil {
69 t.Fatalf("Close: %v", err)
70 }
71
72 stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
73 stdOut, err := io.ReadAll(stdReader)
74 _ = stdReader.Close()
75 if err != nil {
76 t.Fatalf("standard reader rejected stream: %v", err)
77 }
78 if !bytes.Equal(stdOut, input) {
79 t.Fatalf("standard reader mismatch: got %d bytes, want %d", len(stdOut), len(input))
80 }
81
82 localReader := NewReader(bytes.NewReader(compressed.Bytes()))
83 localOut, err := io.ReadAll(localReader)
84 _ = localReader.Close()
85 if err != nil {
86 t.Fatalf("local reader rejected stream: %v", err)
87 }
88 if !bytes.Equal(localOut, input) {
89 t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
90 }
91 }
92
93 func generatedPattern(size int) []byte {
94 out := make([]byte, size)
95 pattern := []byte("DEFLATE block-boundary pattern 0123456789\n")
96 for i := range out {
97 out[i] = pattern[i%len(pattern)]
98 if i%1021 == 0 {
99 out[i] = byte(i)
100 }
101 }
102 return out
103 }
104
105 func generatedRandom(size int) []byte {
106 out := make([]byte, size)
107 var x uint32 = 0x12345678
108 for i := range out {
109 x ^= x << 13
110 x ^= x >> 17
111 x ^= x << 5
112 out[i] = byte(x)
113 }
114 return out
115 }
No file changes, the agent left the workspace untouched.
============================= test session starts ============================== platform linux -- Python 3.11.2, pytest-8.3.3, pluggy-1.6.0 -- /opt/test-venv/bin/python3 cachedir: .pytest_cache rootdir: /tests collecting ... collected 5 items ../tests/test_outputs.py::test_package_builds PASSED [ 20%] ../tests/test_outputs.py::test_flate_streams_roundtrip PASSED [ 40%] ../tests/test_outputs.py::test_held_back_actually_ran PASSED [ 60%] ../tests/test_outputs.py::test_existing_flate_package_tests_pass PASSED [ 80%] ../tests/test_outputs.py::test_no_hardcoded_hidden_literals PASSED [100%] ==================================== PASSES ==================================== =========================== short test summary info ============================ PASSED ../tests/test_outputs.py::test_package_builds PASSED ../tests/test_outputs.py::test_flate_streams_roundtrip PASSED ../tests/test_outputs.py::test_held_back_actually_ran PASSED ../tests/test_outputs.py::test_existing_flate_package_tests_pass PASSED ../tests/test_outputs.py::test_no_hardcoded_hidden_literals ============================== 5 passed in 7.85s ===============================
Reproduce this trial: git checkout 2f94510 && PYTHONPATH=src python3 scripts/build_site.py , then open trial/trial_c415a367fef24542. Re-running the agent live requires EVAL_PLATFORM_ENABLE_OAUTH_SMOKE=1 and is non-deterministic.
Trial trial_c415a367fef24542 · verifier authoritative; classifier explanatory.