tests/test.sh exit code (0 → resolved); the classification below is post-hoc and cannot change it.pwd && rg -n "func \(.*deflateLazy|deflateLazy|writeBlock|storedBlock|dynamic|fixed|literal" flate/deflate.go flate -g'*.go'
Chunk ID: 3af466
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 6810
Output:
/app
flate/deflate.go:172:func (d *compressor) writeBlock(tok *tokens, index int, eof bool) error {
flate/deflate.go:179: //d.w.writeBlock(tok, eof, window)
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:193: // If we removed less than a 64th of all literals
flate/deflate.go:196: d.w.writeBlockHuff(eof, window, d.sync)
flate/deflate.go:198: // Write a dynamic huffman block.
flate/deflate.go:199: d.w.writeBlockDynamic(tok, eof, window, d.sync)
flate/deflate.go:202: d.w.writeBlock(tok, eof, nil)
flate/deflate.go:406:// deflateLazy is the same as deflate, but with d.fastSkipHashing == skipNever,
flate/deflate.go:408:func (d *compressor) deflateLazy() {
flate/deflate.go:419: // Get literal huffman coder.
flate/deflate.go:452: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:513: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:554: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:614: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:630: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:647: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:667: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
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: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:813: d.step = (*compressor).deflateLazy
flate/level1.go:117: // them as literal bytes.
flate/level1.go:120: // literal bytes prior to s.
flate/level1.go:209: // If nothing was added, don't encode literals.
flate/level2.go:113: // them as literal bytes.
flate/level2.go:120: // though we don't yet know how big the literal will be. We handle that
flate/level2.go:125: // literal bytes prior to s.
flate/level2.go:207: // If nothing was added, don't encode literals.
flate/huffman_code.go:14: // number of valid literals
flate/huffman_code.go:15: literalCount = 286
flate/huffman_code.go:38: // Possible lengths are codegenCodeCount, offsetCodeCount and literalCount.
flate/huffman_code.go:39: // The largest of these is literalCount, so we allocate for that case.
flate/huffman_code.go:40: freqcache [literalCount + 1]literalNode
flate/huffman_code.go:43:type literalNode struct {
flate/huffman_code.go:44: literal uint16
flate/huffman_code.go:81:func maxNode() literalNode { return literalNode{math.MaxUint16, math.MaxUint16} }
flate/huffman_code.go:89:// Generates a HuffmanCode corresponding to the fixed literal table
flate/huffman_code.go:91: h := newHuffmanEncoder(literalCount)
flate/huffman_code.go:94: for ch = range uint16(literalCount) {
flate/huffman_code.go:129:var fixedLiteralEncoding = generateFixedLiteralEncoding()
flate/huffman_code.go:130:var fixedOffsetEncoding = generateFixedOffsetEncoding()
flate/huffman_code.go:165:// Return the number of literals assigned to each bit size in the Huffman encoding
flate/huffman_code.go:168:// The cases of 0, 1, and 2 literals are handled by special case code.
flate/huffman_code.go:170:// list An array of the literals with non-zero frequencies
flate/huffman_code.go:176:// maxBits The maximum number of bits that should be used to encode any literal.
flate/huffman_code.go:180:// return An integer array in which array[i] indicates the number of literals
flate/huffman_code.go:183:func (h *huffmanEncoder) bitCounts(list []literalNode, maxBits int32) []int32 {
flate/huffman_code.go:202: // leafCounts[i] counts the number of literals at the left
flate/huffman_code.go:204: // leafCounts[i][j] is the number of literals at the left
flate/huffman_code.go:253: if e.literal < math.MaxUint16 {
flate/huffman_code.go:303: // chain.leafCount gives the number of literals requiring at least "bits"
flate/huffman_code.go:313:func (h *huffmanEncoder) assignEncodingAndSize(bitCount []int32, list []literalNode) {
flate/huffman_code.go:320: // The literals list[len(list)-bits] .. list[len(list)-bits]
flate/huffman_code.go:323: // assigned in literal order (not frequency order).
flate/huffman_code.go:328: h.codes[node.literal] = newhcode(reverseBits(code, uint8(n)), uint8(n))
flate/huffman_code.go:337:// freq An array of frequencies, in which frequency[i] gives the frequency of literal i.
flate/huffman_code.go:338:// maxBits The maximum number of bits to use for any literal.
flate/huffman_code.go:342: // Number of non-zero literals
flate/huffman_code.go:344: // Set list to be the set of all non-zero literals and their frequencies
flate/huffman_code.go:347: list[count] = literalNode{uint16(i), f}
flate/huffman_code.go:353: list[count] = literalNode{}
flate/huffman_code.go:358: // two or fewer literals, everything has bit length 1.
flate/huffman_code.go:360: // "list" is in order of increasing literal value.
flate/huffman_code.go:361: h.codes[node.literal].set(uint16(i), 1)
flate/huffman_code.go:367: // Get the number of literals for each bit count
flate/dict_decoder.go:13:// Any valid stream must start with a literal insertion if no preset dictionary
flate/level6.go:206: // them as literal bytes.
flate/level6.go:318: // If nothing was added, don't encode literals.
flate/level4.go:127: // them as literal bytes.
flate/level4.go:214: // If nothing was added, don't encode literals.
flate/_gen/gen_inflate.go:40:// fixed distance encoding associated with fixed Huffman blocks.
flate/_gen/gen_inflate.go:61: // Read literal and/or (length, distance) according to RFC section 3.2.3.
flate/token_test.go:35: wr.writeBlockDynamic(tok, true, nil, true)
flate/huffman_sortByLiteral.go:10:func sortByLiteral(data []literalNode) {
flate/huffman_sortByLiteral.go:15:func quickSort(data []literalNode, a, b, maxDepth int) {
flate/huffman_sortByLiteral.go:37: if data[i].literal < data[i-6].literal {
flate/huffman_sortByLiteral.go:44:func heapSort(data []literalNode, a, b int) {
flate/huffman_sortByLiteral.go:63:func siftDown(data []literalNode, lo, hi, first int) {
flate/huffman_sortByLiteral.go:70: if child+1 < hi && data[first+child].literal < data[first+child+1].literal {
flate/huffman_sortByLiteral.go:73: if data[first+root].literal > data[first+child].literal {
flate/huffman_sortByLiteral.go:80:func doPivot(data []literalNode, lo, hi int) (midlo, midhi int) {
flate/huffman_sortByLiteral.go:101: for ; a < c && data[a].literal < data[pivot].literal; a++ {
flate/huffman_sortByLiteral.go:105: for ; b < c && data[pivot].literal > data[b].literal; b++ { // data[b] <= pivot
flate/huffman_sortByLiteral.go:107: for ; b < c && data[pivot].literal < data[c-1].literal; c-- { // data[c-1] > pivot
flate/huffman_sortByLiteral.go:123: if data[pivot].literal > data[hi-1].literal { // data[hi-1] = pivot
flate/huffman_sortByLiteral.go:128: if data[b-1].literal > data[pivot].literal { // data[b-1] = pivot
flate/huffman_sortByLiteral.go:135: if data[m].literal > data[pivot].literal { // data[m] = pivot
flate/huffman_sortByLiteral.go:149: for ; a < b && data[b-1].literal > data[pivot].literal; b-- { // data[b] == pivot
flate/huffman_sortByLiteral.go:151: for ; a < b && data[a].literal < data[pivot].literal; a++ { // data[a] < pivot
flate/huffman_sortByLiteral.go:168:func insertionSort(data []literalNode, a, b int) {
flate/huffman_sortByLiteral.go:170: for j := i; j > a && data[j].literal < data[j-1].literal; j-- {
flate/huffman_sortByLiteral.go:187:func medianOfThree(data []literalNode, m1, m0, m2 int) {
flate/huffman_sortByLiteral.go:189: if data[m1].literal < data[m0].literal {
flate/huffman_sortByLiteral.go:193: if data[m2].literal < data[m1].literal {
flate/huffman_sortByLiteral.go:196: if data[m1].literal < data[m0].literal {
flate/flate_test.go:322: "fixed block, use reserved symbol 287",
flate/deflate.go:172:func (d *compressor) writeBlock(tok *tokens, index int, eof bool) error {
flate/deflate.go:179: //d.w.writeBlock(tok, eof, window)
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:193: // If we removed less than a 64th of all literals
flate/deflate.go:196: d.w.writeBlockHuff(eof, window, d.sync)
flate/deflate.go:198: // Write a dynamic huffman block.
flate/deflate.go:199: d.w.writeBlockDynamic(tok, eof, window, d.sync)
flate/deflate.go:202: d.w.writeBlock(tok, eof, nil)
flate/deflate.go:406:// deflateLazy is the same as deflate, but with d.fastSkipHashing == skipNever,
flate/deflate.go:408:func (d *compressor) deflateLazy() {
flate/deflate.go:419: // Get literal huffman coder.
flate/deflate.go:452: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:513: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:554: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:614: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:630: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:647: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:667: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
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: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:813: d.step = (*compressor).deflateLazy
flate/inflate.go:46:// Initialize the fixedHuffmanDecoder only once upon first use.
flate/inflate.go:47:var fixedOnce sync.Once
flate/inflate.go:48:var fixedHuffmanDecoder huffmanDecoder
flate/inflate.go:78:// zlib. There is a lookup table of a fixed bit width (huffmanChunkBits),
flate/inflate.go:315: // Huffman decoders for literal/length, distance.
flate/inflate.go:365: // compressed, fixed Huffman tables
flate/inflate.go:366: f.hl = &fixedHuffmanDecoder
flate/inflate.go:373: // compressed, dynamic Huffman tables
flate/inflate.go:381: fmt.Println("dynamic huffman block")
flate/inflate.go:455:// Compression with dynamic Huffman codes
flate/inflate.go:775:func fixedHuffmanDecoderInit() {
flate/inflate.go:776: fixedOnce.Do(func() {
flate/inflate.go:791: fixedHuffmanDecoder.init(bits[:])
flate/inflate.go:828: fixedHuffmanDecoderInit()
flate/token.go:16: // bits 0-16 xoffset = offset - MIN_OFFSET_SIZE, or literal - 16 bits
flate/token.go:19: // bits 30-32 type 0 = literal 1=EOF 2=Match 3=Unused - 2 bits
flate/token.go:23: literalType = 0 << 30
flate/token.go:166: for i, v := range t.extraHist[:literalCount-256] {
flate/token.go:189: t.AddLiteral(tok.literal())
flate/token.go:196:// emitLiteral writes a literal chunk and returns the number of bytes written.
flate/token.go:240: for i, v := range t.extraHist[1 : literalCount-256] {
flate/token.go:353:// Returns the literal of a literal token
flate/token.go:354:func (t token) literal() uint8 { return uint8(t) }
flate/level5.go:184: // them as literal bytes.
flate/level5.go:303: // If nothing was added, don't encode literals.
flate/level5.go:496: // them as literal bytes.
flate/level5.go:615: // If nothing was added, don't encode literals.
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:106:const ml = 0x7fc00000 // Maximum length token. Used to reduce the size of writeBlockTests
flate/huffman_bit_writer_test.go:108:var writeBlockTests = []huffTest{
flate/huffman_bit_writer_test.go:165:// TestWriteBlock tests if the writeBlock encoding has changed.
flate/huffman_bit_writer_test.go:168: for _, test := range writeBlockTests {
flate/huffman_bit_writer_test.go:173:// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
flate/huffman_bit_writer_test.go:176: for _, test := range writeBlockTests {
flate/huffman_bit_writer_test.go:181:// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
flate/huffman_bit_writer_test.go:184: for _, test := range writeBlockTests {
flate/huffman_bit_writer_test.go:247: t.Errorf("writeBlock did not yield expected result for file %q with input. See %q", test.want, test.want+gotSuffix)
flate/huffman_bit_writer_test.go:261: t.Errorf("reset: writeBlock did not yield expected result for file %q with input. See %q", test.want, test.want+".reset"+gotSuffix)
flate/huffman_bit_writer_test.go:282: t.Errorf("writeBlock did not yield expected result for file %q with input. See %q", test.wantNoInput, test.wantNoInput+gotSuffix)
flate/huffman_bit_writer_test.go:300: t.Errorf("reset: writeBlock did not yield expected result for file %q without input. See %q", test.wantNoInput, test.wantNoInput+".reset"+gotSuffix)
flate/huffman_bit_writer_test.go:313: bw.writeBlock(&tok, false, input)
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: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/level3.go:128: // though we don't yet know how big the literal will be. We handle that
flate/level3.go:133: // literal bytes prior to s.
flate/level3.go:234: // If nothing was added, don't encode literals.
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:256: // them as literal bytes.
flate/stateless.go:259: // literal bytes prior to s.
flate/stateless.go:319: // If nothing was added, don't encode literals.
flate/huffman_sortByFreq.go:10:func sortByFreq(data []literalNode) {
flate/huffman_sortByFreq.go:15:func quickSortByFreq(data []literalNode, a, b, maxDepth int) {
flate/huffman_sortByFreq.go:37: if data[i].freq == data[i-6].freq && data[i].literal < data[i-6].literal || data[i].freq < data[i-6].freq {
flate/huffman_sortByFreq.go:45:func doPivotByFreq(data []literalNode, lo, hi int) (midlo, midhi int) {
flate/huffman_sortByFreq.go:66: for ; a < c && (data[a].freq == data[pivot].freq && data[a].literal < data[pivot].literal || data[a].freq < data[pivot].freq); a++ {
flate/huffman_sortByFreq.go:70: for ; b < c && (data[pivot].freq == data[b].freq && data[pivot].literal > data[b].literal || data[pivot].freq > data[b].freq); b++ { // data[b] <= pivot
flate/huffman_sortByFreq.go:72: for ; b < c && (data[pivot].freq == data[c-1].freq && data[pivot].literal < data[c-1].literal || data[pivot].freq < data[c-1].freq); c-- { // data[c-1] > pivot
flate/huffman_sortByFreq.go:88: if data[pivot].freq == data[hi-1].freq && data[pivot].literal > data[hi-1].literal || data[pivot].freq > data[hi-1].freq { // data[hi-1] = pivot
flate/huffman_sortByFreq.go:93: if data[b-1].freq == data[pivot].freq && data[b-1].literal > data[pivot].literal || data[b-1].freq > data[pivot].freq { // data[b-1] = pivot
flate/huffman_sortByFreq.go:100: if data[m].freq == data[pivot].freq && data[m].literal > data[pivot].literal || data[m].freq > data[pivot].freq { // data[m] = pivot
flate/huffman_sortByFreq.go:114: for ; a < b && (data[b-1].freq == data[pivot].freq && data[b-1].literal > data[pivot].literal || data[b-1].freq > data[pivot].freq); b-- { // data[b] == pivot
flate/huffman_sortByFreq.go:116: for ; a < b && (data[a].freq == data[pivot].freq && data[a].literal < data[pivot].literal || data[a].freq < data[pivot].freq); a++ { // data[a] < pivot
flate/huffman_sortByFreq.go:133:func insertionSortByFreq(data []literalNode, a, b int) {
flate/huffman_sortByFreq.go:135: for j := i; j > a && (data[j].freq == data[j-1].freq && data[j].literal < data[j-1].literal || data[j].freq < data[j-1].freq); j-- {
flate/huffman_sortByFreq.go:145:func medianOfThreeSortByFreq(data []literalNode, m1, m0, m2 int) {
flate/huffman_sortByFreq.go:147: if data[m1].freq == data[m0].freq && data[m1].literal < data[m0].literal || data[m1].freq < data[m0].freq {
flate/huffman_sortByFreq.go:151: if data[m2].freq == data[m1].freq && data[m2].literal < data[m1].literal || data[m2].freq < data[m1].freq {
flate/huffman_sortByFreq.go:154: if data[m1].freq == data[m0].freq && data[m1].literal < data[m0].literal || data[m1].freq < data[m0].freq {
flate/huffman_bit_writer.go:30: // where we check if fixed size is smaller.
flate/huffman_bit_writer.go:110: literalEncoding *huffmanEncoder
flate/huffman_bit_writer.go:119: literalFreq [lengthCodesStart + 32]uint16
flate/huffman_bit_writer.go:124: codegen [literalCount + offsetCodeCount + 1]uint8
flate/huffman_bit_writer.go:139:// If lastHuffMan is set, a table for outputting literals has been generated and offsets are invalid.
flate/huffman_bit_writer.go:149: literalEncoding: newHuffmanEncoder(literalCount),
flate/huffman_bit_writer.go:150: tmpLitEncoding: newHuffmanEncoder(literalCount),
flate/huffman_bit_writer.go:173: a = t.extraHist[:literalCount-256]
flate/huffman_bit_writer.go:174: b = w.literalEncoding.codes[256:literalCount]
flate/huffman_bit_writer.go:183: b = w.literalEncoding.codes[:len(a)]
flate/huffman_bit_writer.go:199: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:258:// the literal and offset lengths arrays (which are concatenated into a single
flate/huffman_bit_writer.go:266:// numLiterals The number of literals in literalEncoding
flate/huffman_bit_writer.go:268:// litenc, offenc The literal and offset encoder to use
flate/huffman_bit_writer.go:370:// dynamicSize returns the size of dynamically encoded data in bits.
flate/huffman_bit_writer.go:371:func (w *huffmanBitWriter) dynamicReuseSize(litEnc, offEnc *huffmanEncoder) (size int) {
flate/huffman_bit_writer.go:372: size = litEnc.bitLength(w.literalFreq[:]) +
flate/huffman_bit_writer.go:377:// dynamicSize returns the size of dynamically encoded data in bits.
flate/huffman_bit_writer.go:378:func (w *huffmanBitWriter) dynamicSize(litEnc, offEnc *huffmanEncoder, extraBits int) (size, numCodegens int) {
flate/huffman_bit_writer.go:381: litEnc.bitLength(w.literalFreq[:]) +
flate/huffman_bit_writer.go:391: for i, n := range w.literalFreq[257:literalCount] {
flate/huffman_bit_writer.go:400:// fixedSize returns the size of dynamically encoded data in bits.
flate/huffman_bit_writer.go:401:func (w *huffmanBitWriter) fixedSize(extraBits int) int {
flate/huffman_bit_writer.go:403: fixedLiteralEncoding.bitLength(w.literalFreq[:]) +
flate/huffman_bit_writer.go:404: fixedOffsetEncoding.bitLength(w.offsetFreq[:]) +
flate/huffman_bit_writer.go:453:// Write the header of a dynamic Huffman block to the output stream.
flate/huffman_bit_writer.go:455:// numLiterals The number of literals specified in codegen
flate/huffman_bit_writer.go:501:// it is replaced with a fixed huffman block.
flate/huffman_bit_writer.go:508: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:512: // To write EOF, use a fixed encoding block. 10 bits instead of 5 bytes.
flate/huffman_bit_writer.go:537: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:541: // Indicate that we are a fixed Huffman block
flate/huffman_bit_writer.go:549:// writeBlock will write a block of tokens with the smallest encoding.
flate/huffman_bit_writer.go:554:func (w *huffmanBitWriter) writeBlock(tokens *tokens, eof bool, input []byte) {
flate/huffman_bit_writer.go:562: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:575: var literalEncoding = fixedLiteralEncoding
flate/huffman_bit_writer.go:576: var offsetEncoding = fixedOffsetEncoding
flate/huffman_bit_writer.go:579: size = w.fixedSize(extraBits)
flate/huffman_bit_writer.go:586: // the literalEncoding and the offsetEncoding.
flate/huffman_bit_writer.go:587: w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
flate/huffman_bit_writer.go:589: dynamicSize, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
flate/huffman_bit_writer.go:591: if dynamicSize < size {
flate/huffman_bit_writer.go:592: size = dynamicSize
flate/huffman_bit_writer.go:593: literalEncoding = w.literalEncoding
flate/huffman_bit_writer.go:605: if literalEncoding == fixedLiteralEncoding {
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:633: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:645: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:665: newSize += int(w.literalEncoding.codes[endBlockMarker].len()) + newSize>>w.logNewTablePenalty
flate/huffman_bit_writer.go:669: reuseSize := w.dynamicReuseSize(w.literalEncoding, w.offsetEncoding) + extraBits
flate/huffman_bit_writer.go:674: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:682: if preSize := w.fixedSize(extraBits) + 7; usePrefs && preSize < size {
flate/huffman_bit_writer.go:693: w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
flate/huffman_bit_writer.go:711: w.literalFreq[endBlockMarker] = 1
flate/huffman_bit_writer.go:716: // the literalEncoding and the offsetEncoding.
flate/huffman_bit_writer.go:717: w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
flate/huffman_bit_writer.go:725: size, numCodegens = w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
flate/huffman_bit_writer.go:729: if preSize := w.fixedSize(extraBits); usePrefs && preSize <= size {
flate/huffman_bit_writer.go:740: w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
flate/huffman_bit_writer.go:764: w.writeTokens(tokens.Slice(), w.literalEncoding.codes, w.offsetEncoding.codes)
flate/huffman_bit_writer.go:768: for i, v := range w.literalFreq[:literalCount] {
flate/huffman_bit_writer.go:770: w.literalFreq[i] = 1
flate/huffman_bit_writer.go:781:// literalFreq and offsetFreq, and generates literalEncoding
flate/huffman_bit_writer.go:783:// The number of literal and offset tokens is returned.
flate/huffman_bit_writer.go:785: //copy(w.literalFreq[:], t.litHist[:])
flate/huffman_bit_writer.go:786: *(*[256]uint16)(w.literalFreq[:]) = t.litHist
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:797: // get the number of literals
flate/huffman_bit_writer.go:798: numLiterals = len(w.literalFreq)
flate/huffman_bit_writer.go:799: for w.literalFreq[numLiterals-1] == 0 {
flate/huffman_bit_writer.go:808: // We haven't found a single match. If we want to go with the dynamic encoding,
flate/huffman_bit_writer.go:817: w.literalEncoding.generate(w.literalFreq[:literalCount], 15)
flate/huffman_bit_writer.go:822:// codes for literal and offset encoding must be supplied.
flate/huffman_bit_writer.go:849: //w.writeCode(lits[t.literal()])
flate/huffman_bit_writer.go:983:// writeBlockHuff encodes a block of bytes as either
flate/huffman_bit_writer.go:984:// Huffman encoded literals or uncompressed bytes if the
flate/huffman_bit_writer.go:986:func (w *huffmanBitWriter) writeBlockHuff(eof bool, input []byte, sync bool) {
flate/huffman_bit_writer.go:992: for i := range w.literalFreq[:] {
flate/huffman_bit_writer.go:993: w.literalFreq[i] = 0
flate/huffman_bit_writer.go:1004: // Add everything as literals
flate/huffman_bit_writer.go:1009: histogram(input, w.literalFreq[:numLiterals])
flate/huffman_bit_writer.go:1016: for _, v := range w.literalFreq[:256] {
flate/huffman_bit_writer.go:1033: w.literalFreq[endBlockMarker] = 1
flate/huffman_bit_writer.go:1034: w.tmpLitEncoding.generate(w.literalFreq[:numLiterals], 15)
flate/huffman_bit_writer.go:1035: estBits := w.tmpLitEncoding.canReuseBits(w.literalFreq[:numLiterals])
flate/huffman_bit_writer.go:1055: reuseSize := w.literalEncoding.canReuseBits(w.literalFreq[:256])
flate/huffman_bit_writer.go:1062: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:1072: w.literalEncoding, w.tmpLitEncoding = w.tmpLitEncoding, w.literalEncoding
flate/huffman_bit_writer.go:1074: // the literalEncoding and the offsetEncoding.
flate/huffman_bit_writer.go:1075: w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, huffOffset)
flate/huffman_bit_writer.go:1089: encoding := w.literalEncoding.codes[:256]
flate/huffman_bit_writer.go:1169: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/inflate_gen.go:16:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:37: // Read literal and/or (length, distance) according to RFC section 3.2.3.
flate/inflate_gen.go:267:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:288: // Read literal and/or (length, distance) according to RFC section 3.2.3.
flate/inflate_gen.go:518:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:539: // Read literal and/or (length, distance) according to RFC section 3.2.3.
flate/inflate_gen.go:769:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:790: // Read literal and/or (length, distance) according to RFC section 3.2.3.
flate/inflate_gen.go:1020:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:1041: // Read literal and/or (length, distance) according to RFC section 3.2.3.
flate/inflate_test.go:111: {"3 0", "fixed", 0},
flate/inflate_test.go:119: {"4 80 49 92 24 49 92 24 71 ff ff 93 11 0", "invalid literal/lengths set", 1},
flate/inflate_test.go:121: {"4 c0 81 8 0 0 0 0 20 7f eb b 0 0", "invalid literal/length code", 1},
flate/inflate_test.go:215: {"1b 7 0 0 0 0 0", "fast invalid literal/length code", 0, -8, 258, true},
flate/inflate_test.go:229: {"3 0", "use fixed blocks", 0, -15, 1, false},
go test ./flate -run 'Test.*Local|Regression|Round|Deflate|Inflate' -count=1
Chunk ID: 27ee3f
Wall time: 1.4528 seconds
Process exited with code 1
Original token count: 394
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: TestLargeLowEntropyRoundTripVisible (0.58s)
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
FAIL
FAIL [code-host]/klauspost/compress/flate 1.461s
FAIL
rg --files flate | sort
Chunk ID: 9825de Wall time: 0.0000 seconds Process exited with code 0 Original token count: 957 Output: flate/_gen/gen_inflate.go flate/deflate.go flate/deflate_test.go flate/dict_decoder.go flate/dict_decoder_test.go flate/example_test.go flate/fast_encoder.go flate/flate_test.go flate/fuzz_test.go flate/huffman_bit_writer.go flate/huffman_bit_writer_test.go flate/huffman_code.go flate/huffman_sortByFreq.go flate/huffman_sortByLiteral.go flate/inflate.go flate/inflate_gen.go flate/inflate_test.go flate/large_low_entropy_test.go flate/level1.go flate/level2.go flate/level3.go flate/level4.go flate/level5.go flate/level6.go flate/matchlen_generic.go flate/reader_test.go flate/regmask_amd64.go flate/regmask_other.go flate/stateless.go flate/testdata/fuzz/FuzzEncoding.zip flate/testdata/fuzz/encode-raw-corpus.zip flate/testdata/huffman-null-max.dyn.expect flate/testdata/huffman-null-max.dyn.expect-noinput flate/testdata/huffman-null-max.golden flate/testdata/huffman-null-max.in flate/testdata/huffman-null-max.sync.expect flate/testdata/huffman-null-max.sync.expect-noinput flate/testdata/huffman-null-max.wb.expect flate/testdata/huffman-null-max.wb.expect-noinput flate/testdata/huffman-pi.dyn.expect flate/testdata/huffman-pi.dyn.expect-noinput flate/testdata/huffman-pi.golden flate/testdata/huffman-pi.in flate/testdata/huffman-pi.sync.expect flate/testdata/huffman-pi.sync.expect-noinput flate/testdata/huffman-pi.wb.expect flate/testdata/huffman-pi.wb.expect-noinput flate/testdata/huffman-rand-1k.dyn.expect flate/testdata/huffman-rand-1k.dyn.expect-noinput flate/testdata/huffman-rand-1k.golden flate/testdata/huffman-rand-1k.in flate/testdata/huffman-rand-1k.sync.expect flate/testdata/huffman-rand-1k.sync.expect-noinput flate/testdata/huffman-rand-1k.wb.expect flate/testdata/huffman-rand-1k.wb.expect-noinput flate/testdata/huffman-rand-limit.dyn.expect flate/testdata/huffman-rand-limit.dyn.expect-noinput flate/testdata/huffman-rand-limit.golden flate/testdata/huffman-rand-limit.in flate/testdata/huffman-rand-limit.sync.expect flate/testdata/huffman-rand-limit.sync.expect-noinput flate/testdata/huffman-rand-limit.wb.expect flate/testdata/huffman-rand-limit.wb.expect-noinput flate/testdata/huffman-rand-max.golden flate/testdata/huffman-rand-max.in flate/testdata/huffman-shifts.dyn.expect flate/testdata/huffman-shifts.dyn.expect-noinput flate/testdata/huffman-shifts.golden flate/testdata/huffman-shifts.in flate/testdata/huffman-shifts.sync.expect flate/testdata/huffman-shifts.sync.expect-noinput flate/testdata/huffman-shifts.wb.expect flate/testdata/huffman-shifts.wb.expect-noinput flate/testdata/huffman-text-shift.dyn.expect flate/testdata/huffman-text-shift.dyn.expect-noinput flate/testdata/huffman-text-shift.golden flate/testdata/huffman-text-shift.in flate/testdata/huffman-text-shift.sync.expect flate/testdata/huffman-text-shift.sync.expect-noinput flate/testdata/huffman-text-shift.wb.expect flate/testdata/huffman-text-shift.wb.expect-noinput flate/testdata/huffman-text.dyn.expect flate/testdata/huffman-text.dyn.expect-noinput flate/testdata/huffman-text.golden flate/testdata/huffman-text.in flate/testdata/huffman-text.sync.expect flate/testdata/huffman-text.sync.expect-noinput flate/testdata/huffman-text.wb.expect flate/testdata/huffman-text.wb.expect-noinput flate/testdata/huffman-zero.dyn.expect flate/testdata/huffman-zero.dyn.expect-noinput flate/testdata/huffman-zero.golden flate/testdata/huffman-zero.in flate/testdata/huffman-zero.sync.expect flate/testdata/huffman-zero.sync.expect-noinput flate/testdata/huffman-zero.wb.expect flate/testdata/huffman-zero.wb.expect-noinput flate/testdata/null-long-match.dyn.expect-noinput flate/testdata/null-long-match.sync.expect-noinput flate/testdata/null-long-match.wb.expect-noinput flate/testdata/partial-block flate/testdata/regression.zip flate/testdata/tokens.bin flate/token.go flate/token_test.go flate/writer_test.go
sed -n '130,230p' flate/deflate.go
Chunk ID: 1decd3
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 '400,680p' flate/deflate.go
Chunk ID: 26fa00
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 2151
Output:
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
}
}
}
}
sed -n '680,770p' flate/deflate.go
Chunk ID: 2b3109
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 603
Output:
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 (d *compressor) syncFlush() error {
sed -n '1,160p' flate/large_low_entropy_test.go
Chunk ID: cd604e
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))
}
}
nl -ba flate/deflate.go | sed -n '160,210p'
Chunk ID: 531e07
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 413
Output:
160 s.hashHead[i] = uint32(int(v) - delta)
161 } else {
162 s.hashHead[i] = 0
163 }
164 }
165 }
166 }
167 n := copy(d.window[d.windowEnd:], b)
168 d.windowEnd += n
169 return n
170 }
171
172 func (d *compressor) writeBlock(tok *tokens, index int, eof bool) error {
173 if index > 0 || eof {
174 var window []byte
175 if d.blockStart <= index {
176 window = d.window[d.blockStart:index]
177 }
178 d.blockStart = index
179 //d.w.writeBlock(tok, eof, window)
180 d.w.writeBlockDynamic(tok, eof, window, d.sync)
181 return d.w.err
182 }
183 return nil
184 }
185
186 // writeBlockSkip writes the current block and uses the number of tokens
187 // to determine if the block should be stored on no matches, or
188 // only huffman encoded.
189 func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
190 if index > 0 || eof {
191 if d.blockStart <= index {
192 window := d.window[d.blockStart:index]
193 // If we removed less than a 64th of all literals
194 // we huffman compress the block.
195 if int(tok.n) > len(window)-int(tok.n>>6) {
196 d.w.writeBlockHuff(eof, window, d.sync)
197 } else {
198 // Write a dynamic huffman block.
199 d.w.writeBlockDynamic(tok, eof, window, d.sync)
200 }
201 } else {
202 d.w.writeBlock(tok, eof, nil)
203 }
204 d.blockStart = index
205 return d.w.err
206 }
207 return nil
208 }
209
210 // fillWindow will fill the current window with the supplied
nl -ba flate/deflate.go | sed -n '440,675p'
Chunk ID: 9303eb
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 2303
Output:
440 }
441 if sanity && s.index > d.windowEnd {
442 panic("index > windowEnd")
443 }
444 if lookahead == 0 {
445 // Flush current output block if any.
446 if d.byteAvailable {
447 // There is still one pending token that needs to be flushed
448 d.tokens.AddLiteral(d.window[s.index-1])
449 d.byteAvailable = false
450 }
451 if d.tokens.n > 0 {
452 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
453 return
454 }
455 d.tokens.Reset()
456 }
457 return
458 }
459 }
460 if s.index < s.maxInsertIndex {
461 // Update the hash
462 hash := hash4(d.window[s.index:])
463 ch := s.hashHead[hash]
464 s.chainHead = int(ch)
465 s.hashPrev[s.index&windowMask] = ch
466 s.hashHead[hash] = uint32(s.index + s.hashOffset)
467 }
468 prevLength := s.length
469 prevOffset := s.offset
470 s.length = minMatchLength - 1
471 s.offset = 0
472 minIndex := max(s.index-windowSize, 0)
473
474 if s.chainHead-s.hashOffset >= minIndex && lookahead > prevLength && prevLength < d.lazy {
475 if newLength, newOffset, ok := d.findMatch(s.index, s.chainHead-s.hashOffset, lookahead); ok {
476 s.length = newLength
477 s.offset = newOffset
478 }
479 }
480
481 if prevLength >= minMatchLength && s.length <= prevLength {
482 // No better match, but check for better match at end...
483 //
484 // Skip forward a number of bytes.
485 // Offset of 2 seems to yield best results. 3 is sometimes better.
486 const checkOff = 2
487
488 // Check all, except full length
489 if prevLength < maxMatchLength-checkOff {
490 prevIndex := s.index - 1
491 if prevIndex+prevLength < s.maxInsertIndex {
492 end := min(lookahead, maxMatchLength+checkOff)
493 end += prevIndex
494
495 // Hash at match end.
496 h := hash4(d.window[prevIndex+prevLength:])
497 ch2 := int(s.hashHead[h]) - s.hashOffset - prevLength
498 if prevIndex-ch2 != prevOffset && ch2 > minIndex+checkOff {
499 length := matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:])
500 // It seems like a pure length metric is best.
501 if length > prevLength {
502 prevLength = length
503 prevOffset = prevIndex - ch2
504
505 // Extend back...
506 for i := checkOff - 1; i >= 0; i-- {
507 if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i] {
508 // Emit tokens we "owe"
509 for j := 0; j <= i; j++ {
510 d.tokens.AddLiteral(d.window[prevIndex+j])
511 if d.tokens.n == maxFlateBlockTokens {
512 // The block includes the current character
513 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
514 return
515 }
516 d.tokens.Reset()
517 }
518 s.index++
519 if s.index < s.maxInsertIndex {
520 h := hash4(d.window[s.index:])
521 ch := s.hashHead[h]
522 s.chainHead = int(ch)
523 s.hashPrev[s.index&windowMask] = ch
524 s.hashHead[h] = uint32(s.index + s.hashOffset)
525 }
526 }
527 break
528 } else {
529 prevLength++
530 }
531 }
532 } else if false {
533 // Check one further ahead.
534 // Only rarely better, disabled for now.
535 prevIndex++
536 h := hash4(d.window[prevIndex+prevLength:])
537 ch2 := int(s.hashHead[h]) - s.hashOffset - prevLength
538 if prevIndex-ch2 != prevOffset && ch2 > minIndex+checkOff {
539 length := matchLen(d.window[prevIndex+checkOff:end], d.window[ch2+checkOff:])
540 // It seems like a pure length metric is best.
541 if length > prevLength+checkOff {
542 prevLength = length
543 prevOffset = prevIndex - ch2
544 prevIndex--
545
546 // Extend back...
547 for i := checkOff; i >= 0; i-- {
548 if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i-1] {
549 // Emit tokens we "owe"
550 for j := 0; j <= i; j++ {
551 d.tokens.AddLiteral(d.window[prevIndex+j])
552 if d.tokens.n == maxFlateBlockTokens {
553 // The block includes the current character
554 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
555 return
556 }
557 d.tokens.Reset()
558 }
559 s.index++
560 if s.index < s.maxInsertIndex {
561 h := hash4(d.window[s.index:])
562 ch := s.hashHead[h]
563 s.chainHead = int(ch)
564 s.hashPrev[s.index&windowMask] = ch
565 s.hashHead[h] = uint32(s.index + s.hashOffset)
566 }
567 }
568 break
569 } else {
570 prevLength++
571 }
572 }
573 }
574 }
575 }
576 }
577 }
578 }
579 // There was a match at the previous step, and the current match is
580 // not better. Output the previous match.
581 d.tokens.AddMatch(uint32(prevLength-3), uint32(prevOffset-minOffsetSize))
582
583 // Insert in the hash table all strings up to the end of the match.
584 // index and index-1 are already inserted. If there is not enough
585 // lookahead, the last two strings are not inserted into the hash
586 // table.
587 newIndex := s.index + prevLength - 1
588 // Calculate missing hashes
589 end := min(newIndex, s.maxInsertIndex)
590 end += minMatchLength - 1
591 startindex := min(s.index+1, s.maxInsertIndex)
592 tocheck := d.window[startindex:end]
593 dstSize := len(tocheck) - minMatchLength + 1
594 if dstSize > 0 {
595 dst := s.hashMatch[:dstSize]
596 bulkHash4(tocheck, dst)
597 var newH uint32
598 for i, val := range dst {
599 di := i + startindex
600 newH = val & hashMask
601 // Get previous value with the same hash.
602 // Our chain should point to the previous value.
603 s.hashPrev[di&windowMask] = s.hashHead[newH]
604 // Set the head of the hash chain to us.
605 s.hashHead[newH] = uint32(di + s.hashOffset)
606 }
607 }
608
609 s.index = newIndex
610 d.byteAvailable = false
611 s.length = minMatchLength - 1
612 if d.tokens.n == maxFlateBlockTokens {
613 // The block includes the current character
614 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
615 return
616 }
617 d.tokens.Reset()
618 }
619 s.ii = 0
620 } else {
621 // Reset, if we got a match this run.
622 if s.length >= minMatchLength {
623 s.ii = 0
624 }
625 // We have a byte waiting. Emit it.
626 if d.byteAvailable {
627 s.ii++
628 d.tokens.AddLiteral(d.window[s.index-1])
629 if d.tokens.n == maxFlateBlockTokens {
630 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
631 return
632 }
633 d.tokens.Reset()
634 }
635 s.index++
636
637 // If we have a long run of no matches, skip additional bytes
638 // Resets when s.ii overflows after 64KB.
639 if n := int(s.ii) - d.chain; n > 0 {
640 n = 1 + int(n>>6)
641 for j := 0; j < n; j++ {
642 if s.index >= d.windowEnd-1 {
643 break
644 }
645 d.tokens.AddLiteral(d.window[s.index-1])
646 if d.tokens.n == maxFlateBlockTokens {
647 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
648 return
649 }
650 d.tokens.Reset()
651 }
652 // Index...
653 if s.index < s.maxInsertIndex {
654 h := hash4(d.window[s.index:])
655 ch := s.hashHead[h]
656 s.chainHead = int(ch)
657 s.hashPrev[s.index&windowMask] = ch
658 s.hashHead[h] = uint32(s.index + s.hashOffset)
659 }
660 s.index++
661 }
662 // Flush last byte
663 d.tokens.AddLiteral(d.window[s.index-1])
664 d.byteAvailable = false
665 // s.length = minMatchLength - 1 // not needed, since s.ii is reset above, so it should never be > minMatchLength
666 if d.tokens.n == maxFlateBlockTokens {
667 if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
668 return
669 }
670 d.tokens.Reset()
671 }
672 }
673 } else {
674 s.index++
675 d.byteAvailable = true
sed -n '1,220p' flate/token.go
Chunk ID: 243a0e
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1745
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
t.indexTokens(in)
return t
}
func (t *tokens) indexTokens(in []token) {
t.Reset()
for _, tok := range in {
if tok < matchType {
t.AddLiteral(tok.literal())
continue
}
t.AddMatch(uint32(tok.length()), tok.offset()&matchOffsetOnlyMask)
}
}
// emitLiteral writes a literal chunk and returns the number of bytes written.
func emitLiteral(dst *tokens, lit []byte) {
for _, v := range lit {
dst.tokens[dst.n] = token(v)
dst.litHist[v]++
dst.n++
}
}
func (t *tokens) AddLiteral(lit byte) {
t.tokens[t.n] = token(lit)
t.litHist[lit]++
t.n++
}
// from https://stackoverflow.com/a/28730362
func mFastLog2(val float32) float32 {
ux := int32(math.Float32bits(val))
log2 := (float32)(((ux >> 23) & 255) - 128)
ux &= -0x7f800001
ux += 127 << 23
uval := math.Float32frombits(uint32(ux))
log2 += ((-0.34484843)*uval+2.02466578)*uval - 0.67487759
return log2
}
sed -n '615,770p' flate/huffman_bit_writer.go
Chunk ID: 611113
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1117
Output:
// 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
rg -n "func \(t \*tokens\) AddMatch|func \(t token\) length|func \(t token\) offset|EstimatedBits|AddEOB|Slice" flate/token.go flate/huffman_bit_writer.go
Chunk ID: 0ef73e
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 332
Output:
flate/huffman_bit_writer.go:559: tokens.AddEOB()
flate/huffman_bit_writer.go:612: w.writeTokens(tokens.Slice(), literalEncoding.codes, offsetEncoding.codes)
flate/huffman_bit_writer.go:627: tokens.AddEOB()
flate/huffman_bit_writer.go:664: newSize := w.lastHeader + tokens.EstimatedBits()
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:738: tokens.AddEOB()
flate/huffman_bit_writer.go:740: w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
flate/huffman_bit_writer.go:764: w.writeTokens(tokens.Slice(), w.literalEncoding.codes, w.offsetEncoding.codes)
flate/token.go:222:// EstimatedBits will return an minimum size estimated by an *optimal*
flate/token.go:225:func (t *tokens) EstimatedBits() int {
flate/token.go:264:func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
flate/token.go:284:func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
flate/token.go:311:func (t *tokens) AddEOB() {
flate/token.go:317:func (t *tokens) Slice() []token {
flate/token.go:357:func (t token) offset() uint32 { return uint32(t) & offsetMask }
flate/token.go:359:func (t token) length() uint8 { return uint8(t >> lengthShift) }
sed -n '220,390p' flate/token.go
Chunk ID: 3ba509
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1019
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 {
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)]
}
sed -n '770,870p' flate/huffman_bit_writer.go
Chunk ID: 4366b0
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 641
Output:
w.literalFreq[i] = 1
}
}
for i, v := range w.offsetFreq[:offsetCodeCount] {
if v == 0 {
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
sed -n '330,430p' flate/huffman_bit_writer.go
Chunk ID: 1b8d6f
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 704
Output:
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.
rg -n "canReuse|canReuseBits|lastHeader|lastHuffMan" flate/huffman_bit_writer.go flate/*.go
Chunk ID: 1b9197
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1494
Output:
flate/huffman_bit_writer.go:109: lastHuffMan bool
flate/huffman_bit_writer.go:115: lastHeader int
flate/huffman_bit_writer.go:133:// If lastHeader is non-zero the Huffman table can be reused.
flate/huffman_bit_writer.go:139:// If lastHuffMan is set, a table for outputting literals has been generated and offsets are invalid.
flate/huffman_bit_writer.go:159: w.lastHeader = 0
flate/huffman_bit_writer.go:160: w.lastHuffMan = false
flate/huffman_bit_writer.go:163:func (w *huffmanBitWriter) canReuse(t *tokens) (ok bool) {
flate/huffman_bit_writer.go:197: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:200: w.lastHeader = 0
flate/huffman_bit_writer.go:506: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:509: w.lastHeader = 0
flate/huffman_bit_writer.go:535: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:538: w.lastHeader = 0
flate/huffman_bit_writer.go:560: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:563: w.lastHeader = 0
flate/huffman_bit_writer.go:631: if (w.lastHuffMan || eof) && w.lastHeader > 0 {
flate/huffman_bit_writer.go:634: w.lastHeader = 0
flate/huffman_bit_writer.go:635: w.lastHuffMan = false
flate/huffman_bit_writer.go:644: if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
flate/huffman_bit_writer.go:646: w.lastHeader = 0
flate/huffman_bit_writer.go:654: if storable || w.lastHeader > 0 {
flate/huffman_bit_writer.go:661: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:664: newSize := w.lastHeader + tokens.EstimatedBits()
flate/huffman_bit_writer.go:676: w.lastHeader = 0
flate/huffman_bit_writer.go:706: if w.lastHeader == 0 {
flate/huffman_bit_writer.go:755: w.lastHeader, _ = w.headerSize()
flate/huffman_bit_writer.go:757: w.lastHuffMan = false
flate/huffman_bit_writer.go:761: w.lastHeader = 0
flate/huffman_bit_writer.go:995: if !w.lastHuffMan {
flate/huffman_bit_writer.go:1035: estBits := w.tmpLitEncoding.canReuseBits(w.literalFreq[:numLiterals])
flate/huffman_bit_writer.go:1037: estBits += w.lastHeader
flate/huffman_bit_writer.go:1038: if w.lastHeader == 0 {
flate/huffman_bit_writer.go:1054: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:1055: reuseSize := w.literalEncoding.canReuseBits(w.literalFreq[:256])
flate/huffman_bit_writer.go:1059: fmt.Println("NOT reusing, reuse:", reuseSize/8, "> new:", estBits/8, "header est:", w.lastHeader/8, "bytes")
flate/huffman_bit_writer.go:1063: w.lastHeader = 0
flate/huffman_bit_writer.go:1065: fmt.Println("reusing, reuse:", reuseSize/8, "> new:", estBits/8, "- header est:", w.lastHeader/8)
flate/huffman_bit_writer.go:1070: if w.lastHeader == 0 {
flate/huffman_bit_writer.go:1081: w.lastHuffMan = true
flate/huffman_bit_writer.go:1082: w.lastHeader, _ = w.headerSize()
flate/huffman_bit_writer.go:1084: count += w.lastHeader
flate/huffman_bit_writer.go:1170: w.lastHeader = 0
flate/huffman_bit_writer.go:1171: w.lastHuffMan = false
flate/huffman_bit_writer.go:109: lastHuffMan bool
flate/huffman_bit_writer.go:115: lastHeader int
flate/huffman_bit_writer.go:133:// If lastHeader is non-zero the Huffman table can be reused.
flate/huffman_bit_writer.go:139:// If lastHuffMan is set, a table for outputting literals has been generated and offsets are invalid.
flate/huffman_bit_writer.go:159: w.lastHeader = 0
flate/huffman_bit_writer.go:160: w.lastHuffMan = false
flate/huffman_bit_writer.go:163:func (w *huffmanBitWriter) canReuse(t *tokens) (ok bool) {
flate/huffman_bit_writer.go:197: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:200: w.lastHeader = 0
flate/huffman_bit_writer.go:506: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:509: w.lastHeader = 0
flate/huffman_bit_writer.go:535: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:538: w.lastHeader = 0
flate/huffman_bit_writer.go:560: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:563: w.lastHeader = 0
flate/huffman_bit_writer.go:631: if (w.lastHuffMan || eof) && w.lastHeader > 0 {
flate/huffman_bit_writer.go:634: w.lastHeader = 0
flate/huffman_bit_writer.go:635: w.lastHuffMan = false
flate/huffman_bit_writer.go:644: if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
flate/huffman_bit_writer.go:646: w.lastHeader = 0
flate/huffman_bit_writer.go:654: if storable || w.lastHeader > 0 {
flate/huffman_bit_writer.go:661: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:664: newSize := w.lastHeader + tokens.EstimatedBits()
flate/huffman_bit_writer.go:676: w.lastHeader = 0
flate/huffman_bit_writer.go:706: if w.lastHeader == 0 {
flate/huffman_bit_writer.go:755: w.lastHeader, _ = w.headerSize()
flate/huffman_bit_writer.go:757: w.lastHuffMan = false
flate/huffman_bit_writer.go:761: w.lastHeader = 0
flate/huffman_bit_writer.go:995: if !w.lastHuffMan {
flate/huffman_bit_writer.go:1035: estBits := w.tmpLitEncoding.canReuseBits(w.literalFreq[:numLiterals])
flate/huffman_bit_writer.go:1037: estBits += w.lastHeader
flate/huffman_bit_writer.go:1038: if w.lastHeader == 0 {
flate/huffman_bit_writer.go:1054: if w.lastHeader > 0 {
flate/huffman_bit_writer.go:1055: reuseSize := w.literalEncoding.canReuseBits(w.literalFreq[:256])
flate/huffman_bit_writer.go:1059: fmt.Println("NOT reusing, reuse:", reuseSize/8, "> new:", estBits/8, "header est:", w.lastHeader/8, "bytes")
flate/huffman_bit_writer.go:1063: w.lastHeader = 0
flate/huffman_bit_writer.go:1065: fmt.Println("reusing, reuse:", reuseSize/8, "> new:", estBits/8, "- header est:", w.lastHeader/8)
flate/huffman_bit_writer.go:1070: if w.lastHeader == 0 {
flate/huffman_bit_writer.go:1081: w.lastHuffMan = true
flate/huffman_bit_writer.go:1082: w.lastHeader, _ = w.headerSize()
flate/huffman_bit_writer.go:1084: count += w.lastHeader
flate/huffman_bit_writer.go:1170: w.lastHeader = 0
flate/huffman_bit_writer.go:1171: w.lastHuffMan = false
flate/huffman_code.go:150:// canReuseBits returns the number of bits or math.MaxInt32 if the encoder cannot be reused.
flate/huffman_code.go:151:func (h *huffmanEncoder) canReuseBits(freq []uint16) int {
sed -n '130,210p' flate/huffman_bit_writer.go
Chunk ID: d4f896
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 542
Output:
//
// 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
}
func (w *huffmanBitWriter) flush() {
if w.err != nil {
w.nbits = 0
return
}
if w.lastHeader > 0 {
// We owe an EOB
w.writeCode(w.literalEncoding.codes[endBlockMarker])
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
}
sed -n '870,960p' flate/huffman_bit_writer.go
Chunk ID: 172d76
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 532
Output:
// 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 {
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
}
}
}
if lengthCode >= lengthExtraBitsMinCode {
extraLengthBits := lengthExtraBits[lengthCode]
//w.writeBits(extraLength, extraLengthBits)
extraLength := int32(length - lengthBase[lengthCode])
bits |= uint64(extraLength) << (nbits & 63)
nbits += extraLengthBits
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
}
}
}
// Write the offset
offset := t.offset()
offsetCode := (offset >> 16) & 31
if false {
w.writeCode(offs[offsetCode])
} else {
// inlined
c := offs[offsetCode]
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
}
}
}
if offsetCode >= offsetExtraBitsMinCode {
offsetComb := offsetCombined[offsetCode]
//w.writeBits(extraOffset, extraOffsetBits)
bits |= uint64((offset-(offsetComb>>8))&matchOffsetOnlyMask) << (nbits & 63)
nbits += uint8(offsetComb)
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
}
cat <<'EOF' >/tmp/repro.go
package main
import (
"bytes"
stdflate "compress/flate"
"fmt"
"io"
kflate "[code-host]/klauspost/compress/flate"
)
func main(){
levels:=[]int{kflate.NoCompression,kflate.BestSpeed,2,3,4,5,kflate.DefaultCompression,7,8,kflate.BestCompression,kflate.HuffmanOnly}
sizes:=[]int{1,100,1024,32768,65536,131072,1048576}
for _, level:= range levels{
for _, size:= range sizes{
input:=make([]byte,size)
var b bytes.Buffer
w,err:=kflate.NewWriter(&b,level); if err!=nil{panic(err)}
if _,err:=w.Write(input);err!=nil{panic(err)}
cerr:=w.Close()
r:=stdflate.NewReader(bytes.NewReader(b.Bytes()))
out,err:=io.ReadAll(r); r.Close()
if cerr!=nil||err!=nil||!bytes.Equal(out,input){fmt.Printf("FAIL level=%d size=%d clen=%d cerr=%v rerr=%v out=%d first=% x\n",level,size,b.Len(),cerr,err,len(out),b.Bytes()[:min(40,b.Len())]); break}
}
}
}
func min(a,b int)int{if a<b{return a};return b}
EOF
go run /tmp/repro.goChunk ID: 1debe2 Wall time: 1.2430 seconds Process exited with code 0 Original token count: 56 Output: FAIL level=9 size=131072 clen=8294 cerr=<nil> rerr=flate: corrupt input before offset 10 out=0 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
rg -n "const \(|maxFlateBlockTokens|maxStoreBlockSize|windowSize|maxMatchLength|baseMatchLength|minOffsetSize|baseMatchOffset" flate/*.go
Chunk ID: e5eb4e
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 2018
Output:
flate/deflate_test.go:406: const (
flate/deflate_test.go:432: const (
flate/deflate_test.go:594:// compressor.encSpeed method (0, 16, 128), as well as near maxStoreBlockSize
flate/deflate.go:17:const (
flate/deflate.go:36: windowSize = 1 << logWindowSize
flate/deflate.go:37: windowMask = windowSize - 1
flate/deflate.go:40: maxMatchLength = 258 // The longest match for the compressor
flate/deflate.go:41: minOffsetSize = 1 // The shortest offset that makes any sense
flate/deflate.go:47: maxFlateBlockTokens = 1 << 15
flate/deflate.go:48: maxStoreBlockSize = 65535
flate/deflate.go:96: hashMatch [maxMatchLength + minMatchLength]uint32
flate/deflate.go:104: hashPrev [windowSize]uint32
flate/deflate.go:133: if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
flate/deflate.go:134: // shift the window by windowSize
flate/deflate.go:135: //copy(d.window[:], d.window[windowSize:2*windowSize])
flate/deflate.go:136: *(*[windowSize]byte)(d.window) = *(*[windowSize]byte)(d.window[windowSize:])
flate/deflate.go:137: s.index -= windowSize
flate/deflate.go:138: d.windowEnd -= windowSize
flate/deflate.go:139: if d.blockStart >= windowSize {
flate/deflate.go:140: d.blockStart -= windowSize
flate/deflate.go:144: s.hashOffset += windowSize
flate/deflate.go:230: if len(b) > windowSize {
flate/deflate.go:231: b = b[len(b)-windowSize:]
flate/deflate.go:270: minMatchLook := min(lookahead, maxMatchLength)
flate/deflate.go:283: minIndex := max(pos-windowSize, 0)
flate/deflate.go:392: d.window = make([]byte, 2*windowSize)
flate/deflate.go:415: if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
flate/deflate.go:421: d.h = newHuffmanEncoder(maxFlateBlockTokens)
flate/deflate.go:437: if lookahead < minMatchLength+maxMatchLength {
flate/deflate.go:472: minIndex := max(s.index-windowSize, 0)
flate/deflate.go:489: if prevLength < maxMatchLength-checkOff {
flate/deflate.go:492: end := min(lookahead, maxMatchLength+checkOff)
flate/deflate.go:507: if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i] {
flate/deflate.go:511: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:548: if prevLength >= maxMatchLength || d.window[prevIndex+i] != d.window[ch2+i-1] {
flate/deflate.go:552: if d.tokens.n == maxFlateBlockTokens {
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: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/deflate.go:682: if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
flate/deflate.go:712: // We only compress if we have maxStoreBlockSize.
flate/deflate.go:790: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:804: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:816: d.fast = &fastEncL5Window{maxOffset: int32(-level), cur: maxStoreBlockSize}
flate/deflate.go:817: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:920:const MaxCustomWindowSize = windowSize
flate/deflate.go:923:// windowSize must be from MinCustomWindowSize to MaxCustomWindowSize.
flate/deflate.go:924:func NewWriterWindow(w io.Writer, windowSize int) (*Writer, error) {
flate/deflate.go:925: if windowSize < MinCustomWindowSize {
flate/deflate.go:928: if windowSize > MaxCustomWindowSize {
flate/deflate.go:932: if err := dw.d.init(w, -windowSize); err != nil {
flate/dict_decoder_test.go:14: const (
flate/fast_encoder.go:22: return &fastEncL1{fastGen: fastGen{cur: maxStoreBlockSize}}
flate/fast_encoder.go:24: return &fastEncL2{fastGen: fastGen{cur: maxStoreBlockSize}}
flate/fast_encoder.go:26: return &fastEncL3{fastGen: fastGen{cur: maxStoreBlockSize}}
flate/fast_encoder.go:28: return &fastEncL4{fastGen: fastGen{cur: maxStoreBlockSize}}
flate/fast_encoder.go:30: return &fastEncL5{fastGen: fastGen{cur: maxStoreBlockSize}}
flate/fast_encoder.go:32: return &fastEncL6{fastGen: fastGen{cur: maxStoreBlockSize}}
flate/fast_encoder.go:38:const (
flate/fast_encoder.go:42: baseMatchOffset = 1 // The smallest match offset
flate/fast_encoder.go:43: baseMatchLength = 3 // The smallest match length per the RFC section 3.2.5
flate/fast_encoder.go:48: allocHistory = maxStoreBlockSize * 5 // Size to preallocate for history.
flate/fast_encoder.go:49: bufferReset = (1 << 31) - allocHistory - maxStoreBlockSize - 1 // Reset the buffer offset when reaching this.
flate/fast_encoder.go:52:const (
flate/fast_encoder.go:136:// The maximum length returned is maxMatchLength - 4.
flate/fast_encoder.go:150: panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
flate/fast_encoder.go:153: a := src[s:min(s+maxMatchLength-4, len(src))]
flate/fast_encoder.go:172: panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
flate/huffman_bit_writer.go:15:const (
flate/huffman_bit_writer.go:415: if len(in) <= maxStoreBlockSize {
flate/huffman_code.go:12:const (
flate/inflate.go:19:const (
flate/inflate.go:97:const (
flate/inflate.go:291:const (
flate/inflate.go:304:const (
flate/level1.go:19: const (
flate/level1.go:145: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/level1.go:148: xoffset := uint32(s - t - baseMatchOffset)
flate/level1.go:155: if xl > 258+baseMatchLength {
flate/level1.go:158: xl = 258 - baseMatchLength
flate/level1.go:162: xl -= baseMatchLength
flate/inflate_gen.go:18: const (
flate/inflate_gen.go:269: const (
flate/inflate_gen.go:520: const (
flate/inflate_gen.go:771: const (
flate/inflate_gen.go:1022: const (
flate/level3.go:13: const (
flate/level3.go:158: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/level2.go:16: const (
flate/level2.go:149: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/level5.go:12: const (
flate/level5.go:189: } else if l == maxMatchLength {
flate/level5.go:238: if l < baseMatchLength {
flate/level5.go:243: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/level5.go:323: const (
flate/level5.go:501: } else if l == maxMatchLength {
flate/level5.go:550: if l < baseMatchLength {
flate/level5.go:555: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/level5.go:663:// The maximum length returned is maxMatchLength - 4.
flate/level5.go:677: panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
flate/level5.go:680: s1 := min(int(s)+maxMatchLength-4, len(src))
flate/level5.go:700: panic(fmt.Sprint(s, "-", t, "(", s-t, ") > maxMatchLength (", maxMatchOffset, ")"))
flate/level4.go:12: const (
flate/level4.go:156: if l < baseMatchLength {
flate/level4.go:161: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/regmask_amd64.go:3:const (
flate/level6.go:12: const (
flate/level6.go:211: } else if l == maxMatchLength {
flate/level6.go:273: if l < baseMatchLength {
flate/level6.go:278: dst.AddMatchLong(l, uint32(s-t-baseMatchOffset))
flate/stateless.go:11:const (
flate/stateless.go:177: const (
flate/stateless.go:284: dst.AddMatchLong(int32(l), uint32(s-t-baseMatchOffset))
flate/reader_test.go:25:const (
flate/reader_test.go:80:const (
flate/regmask_other.go:6:const (
flate/writer_test.go:409: var length = maxStoreBlockSize*30 + 500
flate/token.go:15:const (
flate/token.go:135: n uint16 // Must be able to contain maxStoreBlockSize
flate/token.go:136: tokens [maxStoreBlockSize + 1]token
flate/token.go:266: if xlength >= maxMatchLength+baseMatchLength {
flate/token.go:269: if xoffset >= maxMatchOffset+baseMatchOffset {
flate/token.go:286: if xoffset >= maxMatchOffset+baseMatchOffset {
flate/token.go:295: // We need to have at least baseMatchLength left over for next loop.
flate/token.go:296: if xl > 258+baseMatchLength {
flate/token.go:299: xl = 258 - baseMatchLength
flate/token.go:303: xl -= baseMatchLength
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: bcaf91
Wall time: 0.5163 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.57s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.573s
FAIL
git status --short && git diff -- flate/deflate.go flate/huffman_bit_writer.go flate/large_low_entropy_test.go
Chunk ID: 19f31e 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 '1,70p' flate/deflate.go
Chunk ID: 0d5b55
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 593
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},
sed -n '760,880p' flate/deflate.go
Chunk ID: e136b8
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 680
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()
d.w.reset(nil)
return d.w.err
}
// NewWriter returns a new Writer compressing data at the given level.
sed -n '880,990p' flate/deflate.go
Chunk ID: 0b5c85
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1008
Output:
// 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
}
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)
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")
}
if windowSize > MaxCustomWindowSize {
return nil, errors.New("flate: requested window size bigger than MaxCustomWindowSize")
}
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) {
rg -n "func \(.*Close|close\(|syncFlush|finish|Flush|d.sync" flate/deflate.go flate/*.go
Chunk ID: 70c483
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1932
Output:
flate/deflate.go:180: d.w.writeBlockDynamic(tok, eof, window, d.sync)
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:415: if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
flate/deflate.go:438: if !d.sync {
flate/deflate.go:445: // Flush current output block if any.
flate/deflate.go:662: // Flush last byte
flate/deflate.go:682: if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
flate/deflate.go:700: if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
flate/deflate.go:703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:714: if !d.sync {
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:759: if d.windowEnd == len(d.window) || d.sync {
flate/deflate.go:770:func (d *compressor) syncFlush() error {
flate/deflate.go:771: d.sync = true
flate/deflate.go:781: d.sync = false
flate/deflate.go:830: d.sync = false
flate/deflate.go:863:func (d *compressor) close() error {
flate/deflate.go:867: d.sync = true
flate/deflate.go:951:// Flush flushes any pending data to the underlying writer.
flate/deflate.go:954:// Flush does not return until the data has been written.
flate/deflate.go:955:// Calling Flush when there is no pending data still causes the Writer
flate/deflate.go:957:// If the underlying writer returns an error, Flush returns that error.
flate/deflate.go:959:// In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
flate/deflate.go:960:func (w *Writer) Flush() error {
flate/deflate.go:963: return w.d.syncFlush()
flate/deflate.go:967:func (w *Writer) Close() error {
flate/deflate.go:968: return w.d.close()
flate/dict_decoder.go:66:// availRead reports the number of bytes that can be flushed by readFlush.
flate/dict_decoder.go:170:// readFlush returns a slice of the historical buffer that is ready to be
flate/dict_decoder.go:171:// emitted to the user. The data returned by readFlush must be fully consumed
flate/dict_decoder.go:173:func (dd *dictDecoder) readFlush() []byte {
flate/deflate.go:180: d.w.writeBlockDynamic(tok, eof, window, d.sync)
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:415: if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
flate/deflate.go:438: if !d.sync {
flate/deflate.go:445: // Flush current output block if any.
flate/deflate.go:662: // Flush last byte
flate/deflate.go:682: if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
flate/deflate.go:700: if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
flate/deflate.go:703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:714: if !d.sync {
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:759: if d.windowEnd == len(d.window) || d.sync {
flate/deflate.go:770:func (d *compressor) syncFlush() error {
flate/deflate.go:771: d.sync = true
flate/deflate.go:781: d.sync = false
flate/deflate.go:830: d.sync = false
flate/deflate.go:863:func (d *compressor) close() error {
flate/deflate.go:867: d.sync = true
flate/deflate.go:951:// Flush flushes any pending data to the underlying writer.
flate/deflate.go:954:// Flush does not return until the data has been written.
flate/deflate.go:955:// Calling Flush when there is no pending data still causes the Writer
flate/deflate.go:957:// If the underlying writer returns an error, Flush returns that error.
flate/deflate.go:959:// In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
flate/deflate.go:960:func (w *Writer) Flush() error {
flate/deflate.go:963: return w.d.syncFlush()
flate/deflate.go:967:func (w *Writer) Close() error {
flate/deflate.go:968: return w.d.close()
flate/example_test.go:189: // Flush ensures that the receiver can read all data sent so far.
flate/example_test.go:190: if err := zw.Flush(); err != nil {
flate/example_test.go:211: // Flush and Close on the transmitter side.
flate/deflate_test.go:218:func (b *syncBuffer) Close() error {
flate/deflate_test.go:254: if err := w.Flush(); err != nil {
flate/deflate_test.go:278: // not necessarily the case: the write Flush may emit
flate/deflate_test.go:416: w.Flush()
flate/deflate_test.go:446: w.Flush()
flate/deflate_test.go:648: if err := w.Flush(); err != nil {
flate/deflate_test.go:649: t.Errorf("i=%d, firstN=%d, flush=%t: Flush: %v", i, firstN, flush, err)
flate/huffman_bit_writer.go:33: // bufferFlushSize indicates the buffer size
flate/huffman_bit_writer.go:37: bufferFlushSize = 246
flate/huffman_bit_writer.go:241: w.err = InternalError("writeBytes with unfinished bits")
flate/huffman_bit_writer.go:441: if n >= bufferFlushSize {
flate/huffman_bit_writer.go:858: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:885: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:907: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:932: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:953: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:1107: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:1135: if nbytes >= bufferFlushSize {
flate/huffman_bit_writer.go:1163: // Flush if needed to have space.
flate/dict_decoder_test.go:84: got.Write(dd.readFlush())
flate/dict_decoder_test.go:94: got.Write(dd.readFlush())
flate/dict_decoder_test.go:135: got.Write(dd.readFlush())
flate/inflate_gen.go:87: f.toRead = dict.readFlush()
flate/inflate_gen.go:96: f.finishBlock()
flate/inflate_gen.go:253: f.toRead = dict.readFlush()
flate/inflate_gen.go:338: f.toRead = dict.readFlush()
flate/inflate_gen.go:347: f.finishBlock()
flate/inflate_gen.go:504: f.toRead = dict.readFlush()
flate/inflate_gen.go:589: f.toRead = dict.readFlush()
flate/inflate_gen.go:598: f.finishBlock()
flate/inflate_gen.go:755: f.toRead = dict.readFlush()
flate/inflate_gen.go:840: f.toRead = dict.readFlush()
flate/inflate_gen.go:849: f.finishBlock()
flate/inflate_gen.go:1006: f.toRead = dict.readFlush()
flate/inflate_gen.go:1091: f.toRead = dict.readFlush()
flate/inflate_gen.go:1100: f.finishBlock()
flate/inflate_gen.go:1257: f.toRead = dict.readFlush()
flate/inflate.go:305: syncFlush flushMode = iota // return data after sync flush block
flate/inflate.go:306: partialFlush // return data after each block
flate/inflate.go:409: f.toRead = f.dict.readFlush() // Flush what's left in case of error
flate/inflate.go:441: f.toRead = f.dict.readFlush() // Flush what's left in case of error
flate/inflate.go:447:func (f *decompressor) Close() error {
flate/inflate.go:631: if f.flushMode == syncFlush {
flate/inflate.go:632: f.toRead = f.dict.readFlush()
flate/inflate.go:635: f.finishBlock()
flate/inflate.go:661: f.toRead = f.dict.readFlush()
flate/inflate.go:665: f.finishBlock()
flate/inflate.go:668:func (f *decompressor) finishBlock() {
flate/inflate.go:671: f.toRead = f.dict.readFlush()
flate/inflate.go:675: } else if f.flushMode == partialFlush && f.dict.availRead() > 0 {
flate/inflate.go:676: f.toRead = f.dict.readFlush()
flate/inflate.go:815: f.flushMode = partialFlush
flate/inflate.go:849:// when finished reading.
flate/writer_test.go:302: err = w.Flush()
flate/stateless.go:26:func (s *statelessWriter) Close() error {
go list -m all | sed -n '1,80p'
Chunk ID: 7fdfb0 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 8 Output: [code-host]/klauspost/compress
find /root/go/pkg/mod -path '*klauspost*compress*' -name deflate.go 2>/dev/null | head -20
Chunk ID: e51fdf Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
sed -n '1,80p' go.mod
Chunk ID: 62c4dc Wall time: 0.0000 seconds Process exited with code 0 Original token count: 35 Output: module [code-host]/klauspost/compress go 1.23 retract ( // https://[code-host]/klauspost/compress/pull/503 v1.14.3 v1.14.2 v1.14.1 )
sed -n '1,30p' flate/huffman_bit_writer.go
Chunk ID: 610bd5 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 157 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.
*** Begin Patch
*** Update File: flate/huffman_bit_writer.go
@@
func (w *huffmanBitWriter) writeBlockDynamic(tokens *tokens, eof bool, input []byte, sync bool) {
if w.err != nil {
return
}
+ fmt.Println("DBG enter", "tokens", tokens.n, "input", len(input), "sync", sync, "eof", eof, "last", w.lastHeader)
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/huffman_bit_writer.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 75c62a
Wall time: 0.7400 seconds
Process exited with code 1
Original token count: 112
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
DBG enter tokens 32768 input 32768 sync false eof false last 0
DBG enter tokens 32768 input 0 sync false eof false last 73
DBG enter tokens 3590 input 0 sync true eof false last 103
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.57s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.570s
FAIL
*** Begin Patch
*** Update File: flate/huffman_bit_writer.go
@@
- fmt.Println("DBG enter", "tokens", tokens.n, "input", len(input), "sync", sync, "eof", eof, "last", w.lastHeader)
+ var decLen int
+ for _, t := range tokens.Slice() {
+ if t < 256 {
+ decLen++
+ } else if t > 256 {
+ decLen += int(t.length()) + baseMatchLength
+ }
+ }
+ fmt.Println("DBG enter", "tokens", tokens.n, "dec", decLen, "input", len(input), "sync", sync, "eof", eof, "last", w.lastHeader)
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/huffman_bit_writer.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: e2853d
Wall time: 0.7567 seconds
Process exited with code 1
Original token count: 119
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
DBG enter tokens 32768 dec 32768 input 32768 sync false eof false last 0
DBG enter tokens 32768 dec 89822 input 0 sync false eof false last 73
DBG enter tokens 3590 dec 925986 input 0 sync true eof false last 103
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.57s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.573s
FAIL
*** Begin Patch
*** Update File: 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]
}
+ fmt.Println("DBG writeBlock", "blockStart", d.blockStart, "index", index, "window", len(window), "tokens", tok.n)
d.blockStart = index
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/deflate.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 0a590d
Wall time: 0.7852 seconds
Process exited with code 1
Original token count: 171
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
DBG writeBlock blockStart 0 index 32768 window 32768 tokens 32768
DBG enter tokens 32768 dec 32768 input 32768 sync false eof false last 0
DBG writeBlock blockStart 2147483647 index 57054 window 0 tokens 32768
DBG enter tokens 32768 dec 89822 input 0 sync false eof false last 73
DBG writeBlock blockStart 2146631679 index 65536 window 0 tokens 3590
DBG enter tokens 3590 dec 925986 input 0 sync true eof false last 103
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.61s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.608s
FAIL
*** Begin Patch
*** Update File: flate/huffman_bit_writer.go
@@
- if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
- w.writeCode(w.literalEncoding.codes[endBlockMarker])
- w.lastHeader = 0
+ if !fillReuse && w.lastHeader > 0 {
+ canReuse := w.canReuse(tokens)
+ fmt.Println("DBG reuse", canReuse, "last", w.lastHeader)
+ if !canReuse {
+ w.writeCode(w.literalEncoding.codes[endBlockMarker])
+ w.lastHeader = 0
+ }
}
@@
- w.writeStoredHeader(len(input), eof)
+ fmt.Println("DBG choose stored reuse", len(input))
+ w.writeStoredHeader(len(input), eof)
@@
- w.writeFixedHeader(eof)
+ fmt.Println("DBG choose fixed reuse")
+ w.writeFixedHeader(eof)
@@
- w.writeStoredHeader(len(input), eof)
+ fmt.Println("DBG choose stored reuse2", len(input))
+ w.writeStoredHeader(len(input), eof)
@@
- w.writeStoredHeader(len(input), eof)
+ fmt.Println("DBG choose stored newpref", len(input))
+ w.writeStoredHeader(len(input), eof)
@@
- w.writeFixedHeader(eof)
+ fmt.Println("DBG choose fixed new")
+ w.writeFixedHeader(eof)
@@
- w.writeStoredHeader(len(input), eof)
+ fmt.Println("DBG choose stored new", len(input))
+ w.writeStoredHeader(len(input), eof)
@@
- w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
+ fmt.Println("DBG choose dynamic", "lits", numLiterals, "offs", numOffsets, "codes", numCodegens)
+ w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/huffman_bit_writer.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 62bc52
Wall time: 0.7468 seconds
Process exited with code 1
Original token count: 216
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
DBG writeBlock blockStart 0 index 32768 window 32768 tokens 32768
DBG enter tokens 32768 dec 32768 input 32768 sync false eof false last 0
DBG choose dynamic lits 1 offs 1 codes 18
DBG writeBlock blockStart 2147483647 index 57054 window 0 tokens 32768
DBG enter tokens 32768 dec 89822 input 0 sync false eof false last 73
DBG reuse false last 73
DBG choose dynamic lits 286 offs 1 codes 18
DBG writeBlock blockStart 2146631679 index 65536 window 0 tokens 3590
DBG enter tokens 3590 dec 925986 input 0 sync true eof false last 103
DBG reuse false last 103
DBG choose dynamic lits 286 offs 1 codes 18
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.57s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.575s
FAIL
sed -n '150,220p' flate/huffman_bit_writer_test.go
Chunk ID: 6fd65f
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1253
Output:
},
{
input: "testdata/huffman-zero.in",
want: "testdata/huffman-zero.%s.expect",
wantNoInput: "testdata/huffman-zero.%s.expect-noinput",
tokens: []token{0x30, ml, 0x4b800000},
},
{
input: "",
want: "",
wantNoInput: "testdata/null-long-match.%s.expect-noinput",
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},
},
}
// TestWriteBlock tests if the writeBlock encoding has changed.
// To update the reference files use the "-update" flag on the test.
func TestWriteBlock(t *testing.T) {
for _, test := range writeBlockTests {
testBlock(t, test, "wb")
}
}
// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
// To update the reference files use the "-update" flag on the test.
func TestWriteBlockDynamic(t *testing.T) {
for _, test := range writeBlockTests {
testBlock(t, test, "dyn")
}
}
// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
// To update the reference files use the "-update" flag on the test.
func TestWriteBlockDynamicSync(t *testing.T) {
for _, test := range writeBlockTests {
testBlock(t, test, "sync")
}
}
// testBlock tests a block against its references,
// or regenerate the references, if "-update" flag is set.
func testBlock(t *testing.T, test huffTest, ttype string) {
if test.want != "" {
test.want = fmt.Sprintf(test.want, ttype)
}
const gotSuffix = ".got"
test.wantNoInput = fmt.Sprintf(test.wantNoInput, ttype)
tokens := indexTokens(test.tokens)
if *update {
if test.input != "" {
t.Logf("Updating %q", test.want)
input, err := os.ReadFile(test.input)
if err != nil {
t.Error(err)
return
}
f, err := os.Create(test.want)
if err != nil {
t.Error(err)
return
}
defer f.Close()
bw := newHuffmanBitWriter(f)
writeToType(t, ttype, bw, tokens, input)
}
t.Logf("Updating %q", test.wantNoInput)
f, err := os.Create(test.wantNoInput)
if err != nil {
t.Error(err)
sed -n '220,330p' flate/huffman_bit_writer_test.go
Chunk ID: ec735a
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 708
Output:
t.Error(err)
return
}
defer f.Close()
bw := newHuffmanBitWriter(f)
writeToType(t, ttype, bw, tokens, nil)
return
}
if test.input != "" {
t.Logf("Testing %q", test.want)
input, err := os.ReadFile(test.input)
if err != nil {
t.Error(err)
return
}
want, err := os.ReadFile(test.want)
if err != nil {
t.Error(err)
return
}
var buf bytes.Buffer
bw := newHuffmanBitWriter(&buf)
writeToType(t, ttype, bw, tokens, input)
got := buf.Bytes()
if !bytes.Equal(got, want) {
t.Errorf("writeBlock did not yield expected result for file %q with input. See %q", test.want, test.want+gotSuffix)
if err := os.WriteFile(test.want+gotSuffix, got, 0666); err != nil {
t.Error(err)
}
}
t.Log("Output ok")
// Test if the writer produces the same output after reset.
buf.Reset()
bw.reset(&buf)
writeToType(t, ttype, bw, tokens, input)
bw.flush()
got = buf.Bytes()
if !bytes.Equal(got, want) {
t.Errorf("reset: writeBlock did not yield expected result for file %q with input. See %q", test.want, test.want+".reset"+gotSuffix)
if err := os.WriteFile(test.want+".reset"+gotSuffix, got, 0666); err != nil {
t.Error(err)
}
return
}
t.Log("Reset ok")
testWriterEOF(t, "wb", test, true)
}
t.Logf("Testing %q", test.wantNoInput)
wantNI, err := os.ReadFile(test.wantNoInput)
if err != nil {
t.Error(err)
return
}
var buf bytes.Buffer
bw := newHuffmanBitWriter(&buf)
writeToType(t, ttype, bw, tokens, nil)
got := buf.Bytes()
if !bytes.Equal(got, wantNI) {
t.Errorf("writeBlock did not yield expected result for file %q with input. See %q", test.wantNoInput, test.wantNoInput+gotSuffix)
if err := os.WriteFile(test.wantNoInput+gotSuffix, got, 0666); err != nil {
t.Error(err)
}
} else if got[0]&1 == 1 {
t.Error("got unexpected EOF")
return
}
t.Log("Output ok")
// Test if the writer produces the same output after reset.
buf.Reset()
bw.reset(&buf)
writeToType(t, ttype, bw, tokens, nil)
bw.flush()
got = buf.Bytes()
if !bytes.Equal(got, wantNI) {
t.Errorf("reset: writeBlock did not yield expected result for file %q without input. See %q", test.wantNoInput, test.wantNoInput+".reset"+gotSuffix)
if err := os.WriteFile(test.wantNoInput+".reset"+gotSuffix, got, 0666); err != nil {
t.Error(err)
}
return
}
t.Log("Reset ok")
testWriterEOF(t, "wb", test, false)
}
func writeToType(t *testing.T, ttype string, bw *huffmanBitWriter, tok tokens, input []byte) {
switch ttype {
case "wb":
bw.writeBlock(&tok, false, input)
case "dyn":
bw.writeBlockDynamic(&tok, false, input, false)
case "sync":
bw.writeBlockDynamic(&tok, false, input, true)
default:
panic("unknown test type")
}
if bw.err != nil {
t.Error(bw.err)
return
}
bw.flush()
if bw.err != nil {
t.Error(bw.err)
return
sed -n '330,370p' flate/huffman_bit_writer_test.go
Chunk ID: 99a547
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 195
Output:
return
}
}
// testWriterEOF tests if the written block contains an EOF marker.
func testWriterEOF(t *testing.T, ttype string, test huffTest, useInput bool) {
if useInput && test.input == "" {
return
}
var input []byte
if useInput {
var err error
input, err = os.ReadFile(test.input)
if err != nil {
t.Error(err)
return
}
}
var buf bytes.Buffer
bw := newHuffmanBitWriter(&buf)
tokens := indexTokens(test.tokens)
switch ttype {
case "wb":
bw.writeBlock(&tokens, true, input)
case "dyn":
bw.writeBlockDynamic(&tokens, true, input, true)
case "huff":
bw.writeBlockHuff(true, input, true)
default:
panic("unknown test type")
}
if bw.err != nil {
t.Error(bw.err)
return
}
bw.flush()
if bw.err != nil {
t.Error(bw.err)
return
}
wc -c flate/testdata/huffman-zero.dyn.expect flate/testdata/huffman-zero.sync.expect flate/testdata/huffman-null-max.dyn.expect
Chunk ID: 99727d Wall time: 0.0000 seconds Process exited with code 0 Original token count: 35 Output: 6 flate/testdata/huffman-zero.dyn.expect 6 flate/testdata/huffman-zero.sync.expect 78 flate/testdata/huffman-null-max.dyn.expect 90 total
*** Begin Patch
*** Update File: flate/deflate.go
@@
if d.blockStart <= index {
window = d.window[d.blockStart:index]
}
- fmt.Println("DBG writeBlock", "blockStart", d.blockStart, "index", index, "window", len(window), "tokens", tok.n)
d.blockStart = index
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/deflate.go
*** Begin Patch
*** Update File: flate/huffman_bit_writer.go
@@
- var decLen int
- for _, t := range tokens.Slice() {
- if t < 256 {
- decLen++
- } else if t > 256 {
- decLen += int(t.length()) + baseMatchLength
- }
- }
- fmt.Println("DBG enter", "tokens", tokens.n, "dec", decLen, "input", len(input), "sync", sync, "eof", eof, "last", w.lastHeader)
-
sync = sync || eof
if sync {
tokens.AddEOB()
}
@@
- if !fillReuse && w.lastHeader > 0 {
- canReuse := w.canReuse(tokens)
- fmt.Println("DBG reuse", canReuse, "last", w.lastHeader)
- if !canReuse {
- w.writeCode(w.literalEncoding.codes[endBlockMarker])
- w.lastHeader = 0
- }
+ if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
+ w.writeCode(w.literalEncoding.codes[endBlockMarker])
+ w.lastHeader = 0
}
@@
- fmt.Println("DBG choose stored reuse", len(input))
w.writeStoredHeader(len(input), eof)
@@
- fmt.Println("DBG choose fixed reuse")
w.writeFixedHeader(eof)
@@
- fmt.Println("DBG choose stored reuse2", len(input))
w.writeStoredHeader(len(input), eof)
@@
if fillReuse && !sync {
w.fillTokens()
numLiterals, numOffsets = maxNumLit, maxNumDist
} else {
w.literalFreq[endBlockMarker] = 1
+ if numLiterals <= endBlockMarker {
+ numLiterals = endBlockMarker + 1
+ }
}
@@
- fmt.Println("DBG choose stored newpref", len(input))
w.writeStoredHeader(len(input), eof)
@@
- fmt.Println("DBG choose fixed new")
w.writeFixedHeader(eof)
@@
- fmt.Println("DBG choose stored new", len(input))
w.writeStoredHeader(len(input), eof)
@@
- fmt.Println("DBG choose dynamic", "lits", numLiterals, "offs", numOffsets, "codes", numCodegens)
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/huffman_bit_writer.go
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: da9729 Wall time: 1.2727 seconds Process exited with code 0 Original token count: 39 Output: === RUN TestLargeLowEntropyRoundTripVisible --- PASS: TestLargeLowEntropyRoundTripVisible (0.62s) PASS ok [code-host]/klauspost/compress/flate 0.620s
go test ./flate -run 'TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: 70bbdd
Wall time: 0.7286 seconds
Process exited with code 1
Original token count: 1039
Output:
--- FAIL: TestWriteBlockDynamic (0.05s)
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.074s
FAIL
go test ./flate -run 'TestWriter|TestDeflate|TestInflate|TestLargeLowEntropyRoundTripVisible' -count=1
Chunk ID: 4ab79b
Wall time: 4.5420 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.919s
FAIL
*** Begin Patch
*** Update File: flate/huffman_bit_writer.go
@@
} else {
w.literalFreq[endBlockMarker] = 1
- if numLiterals <= endBlockMarker {
+ if input != nil && numLiterals <= endBlockMarker {
numLiterals = endBlockMarker + 1
}
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/huffman_bit_writer.go
go test ./flate -run 'TestLargeLowEntropyRoundTripVisible|TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: ea1270 Wall time: 0.9131 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 0.585s
go run /tmp/repro.go
Chunk ID: de7f40 Wall time: 1.9782 seconds Process exited with code 0 Original token count: 0 Output:
*** Begin Patch
*** Update File: flate/large_low_entropy_test.go
@@
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))
+ inputs := map[string][]byte{
+ "low": make([]byte, 1<<20),
+ "medium": makeMediumEntropy(384 << 10),
+ "high": makeHighEntropy(256 << 10),
+ }
+ levels := []int{
+ HuffmanOnly,
+ DefaultCompression,
+ NoCompression,
+ BestSpeed,
+ 2, 3, 4, 5, 6, 7, 8,
+ BestCompression,
+ }
+ chunks := map[string][]int{
+ "single": nil,
+ "chunked": {1, 3, 257, 8191, 65536},
+ }
+
+ for name, input := range inputs {
+ for _, level := range levels {
+ for mode, chunkPattern := range chunks {
+ t.Run(name+"/"+mode, func(t *testing.T) {
+ compressed := compressForRoundTrip(t, input, level, chunkPattern)
+ checkRoundTrip(t, "standard", func() io.ReadCloser {
+ return stdflate.NewReader(bytes.NewReader(compressed))
+ }, input)
+ checkRoundTrip(t, "local", func() io.ReadCloser {
+ return NewReader(bytes.NewReader(compressed))
+ }, input)
+ })
+ }
+ }
+ }
+}
+
+func compressForRoundTrip(t *testing.T, input []byte, level int, chunks []int) []byte {
+ t.Helper()
+
+ var compressed bytes.Buffer
+ w, err := NewWriter(&compressed, level)
+ if err != nil {
+ t.Fatalf("NewWriter(%d): %v", level, err)
+ }
+ if len(chunks) == 0 {
+ if _, err := w.Write(input); err != nil {
+ t.Fatalf("Write: %v", err)
+ }
+ } else {
+ for pos, i := 0, 0; pos < len(input); i++ {
+ n := chunks[i%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)
+ }
+ return compressed.Bytes()
+}
+
+func checkRoundTrip(t *testing.T, name string, newReader func() io.ReadCloser, input []byte) {
+ t.Helper()
+
+ r := newReader()
+ out, err := io.ReadAll(r)
+ _ = r.Close()
+ if err != nil {
+ t.Fatalf("%s reader rejected stream: %v", name, err)
+ }
+ if !bytes.Equal(out, input) {
+ t.Fatalf("%s reader mismatch: got %d bytes, want %d", name, len(out), len(input))
}
}
+
+func makeMediumEntropy(n int) []byte {
+ out := make([]byte, n)
+ for i := range out {
+ out[i] = byte((i/7 + i/251) & 15)
+ }
+ return out
+}
+
+func makeHighEntropy(n int) []byte {
+ out := make([]byte, n)
+ var x uint32 = 1
+ for i := range out {
+ x = x*1664525 + 1013904223
+ out[i] = byte(x >> 24)
+ }
+ return out
+}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/large_low_entropy_test.go
*** Begin Patch
*** Update File: flate/large_low_entropy_test.go
@@
import (
"bytes"
stdflate "compress/flate"
+ "fmt"
"io"
"testing"
)
@@
for _, level := range levels {
for mode, chunkPattern := range chunks {
- t.Run(name+"/"+mode, func(t *testing.T) {
+ t.Run(fmt.Sprintf("%s/%s/level_%d", name, mode, level), func(t *testing.T) {
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/large_low_entropy_test.go
gofmt -w flate/huffman_bit_writer.go flate/large_low_entropy_test.go
Chunk ID: 264952 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'TestLargeLowEntropyRoundTripVisible|TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: f6e7d5 Wall time: 1.4662 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 1.303s
rg -n "func Test.*Regression|regression|flate-local|testdata/regression" flate/*_test.go
Chunk ID: 1d8428
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 140
Output:
flate/deflate_test.go:463:func TestRegression2508(t *testing.T) {
flate/fuzz_test.go:29: fuzz.AddFromZip(f, "testdata/regression.zip", fuzz.TypeRaw, false)
flate/writer_test.go:68:func TestWriterRegression(t *testing.T) {
flate/writer_test.go:69: data, err := os.ReadFile("testdata/regression.zip")
flate/huffman_bit_writer_test.go:20:// to detect possible regressions.
flate/flate_test.go:73:func TestRegressions(t *testing.T) {
flate/flate_test.go:74: // Test fuzzer regressions
flate/flate_test.go:75: data, err := os.ReadFile("testdata/regression.zip")
go build ./...
Chunk ID: c37b45 Wall time: 0.0108 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'Regression|TestWriter|TestReader|TestDict|TestLargeLowEntropyRoundTripVisible' -count=1
Chunk ID: 4980a4 Wall time: 4.2452 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 4.311s
go run /tmp/repro.go
Chunk ID: 86fbcb Wall time: 1.5279 seconds Process exited with code 0 Original token count: 0 Output:
sed -n '700,735p' flate/huffman_bit_writer.go
Chunk ID: a2585a
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 281
Output:
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
if input != nil && numLiterals <= endBlockMarker {
numLiterals = 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)
sed -n '1,180p' flate/large_low_entropy_test.go
Chunk ID: 464ec5
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 609
Output:
package flate
import (
"bytes"
stdflate "compress/flate"
"fmt"
"io"
"testing"
)
func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
inputs := map[string][]byte{
"low": make([]byte, 1<<20),
"medium": makeMediumEntropy(384 << 10),
"high": makeHighEntropy(256 << 10),
}
levels := []int{
HuffmanOnly,
DefaultCompression,
NoCompression,
BestSpeed,
2, 3, 4, 5, 6, 7, 8,
BestCompression,
}
chunks := map[string][]int{
"single": nil,
"chunked": {1, 3, 257, 8191, 65536},
}
for name, input := range inputs {
for _, level := range levels {
for mode, chunkPattern := range chunks {
t.Run(fmt.Sprintf("%s/%s/level_%d", name, mode, level), func(t *testing.T) {
compressed := compressForRoundTrip(t, input, level, chunkPattern)
checkRoundTrip(t, "standard", func() io.ReadCloser {
return stdflate.NewReader(bytes.NewReader(compressed))
}, input)
checkRoundTrip(t, "local", func() io.ReadCloser {
return NewReader(bytes.NewReader(compressed))
}, input)
})
}
}
}
}
func compressForRoundTrip(t *testing.T, input []byte, level int, chunks []int) []byte {
t.Helper()
var compressed bytes.Buffer
w, err := NewWriter(&compressed, level)
if err != nil {
t.Fatalf("NewWriter(%d): %v", level, err)
}
if len(chunks) == 0 {
if _, err := w.Write(input); err != nil {
t.Fatalf("Write: %v", err)
}
} else {
for pos, i := 0, 0; pos < len(input); i++ {
n := chunks[i%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)
}
return compressed.Bytes()
}
func checkRoundTrip(t *testing.T, name string, newReader func() io.ReadCloser, input []byte) {
t.Helper()
r := newReader()
out, err := io.ReadAll(r)
_ = r.Close()
if err != nil {
t.Fatalf("%s reader rejected stream: %v", name, err)
}
if !bytes.Equal(out, input) {
t.Fatalf("%s reader mismatch: got %d bytes, want %d", name, len(out), len(input))
}
}
func makeMediumEntropy(n int) []byte {
out := make([]byte, n)
for i := range out {
out[i] = byte((i/7 + i/251) & 15)
}
return out
}
func makeHighEntropy(n int) []byte {
out := make([]byte, n)
var x uint32 = 1
for i := range out {
x = x*1664525 + 1013904223
out[i] = byte(x >> 24)
}
return out
}
find flate/testdata -name '*.got' -o -name '*.reset.got'
Chunk ID: b4f31a Wall time: 0.0000 seconds Process exited with code 0 Original token count: 29 Output: flate/testdata/huffman-rand-1k.dyn.expect-noinput.got flate/testdata/huffman-rand-1k.dyn.expect-noinput.reset.got
rm -f flate/testdata/huffman-rand-1k.dyn.expect-noinput.got flate/testdata/huffman-rand-1k.dyn.expect-noinput.reset.got
Chunk ID: dd1917 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
*** Begin Patch
*** Update File: flate/large_low_entropy_test.go
@@
func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
- inputs := map[string][]byte{
- "low": make([]byte, 1<<20),
- "medium": makeMediumEntropy(384 << 10),
- "high": makeHighEntropy(256 << 10),
+ inputs := []struct {
+ name string
+ data []byte
+ }{
+ {"low", make([]byte, 1<<20)},
+ {"medium", makeMediumEntropy(384 << 10)},
+ {"high", makeHighEntropy(256 << 10)},
}
@@
- chunks := map[string][]int{
- "single": nil,
- "chunked": {1, 3, 257, 8191, 65536},
+ chunks := []struct {
+ name string
+ pattern []int
+ }{
+ {"single", nil},
+ {"chunked", []int{1, 3, 257, 8191, 65536}},
}
- for name, input := range inputs {
+ for _, input := range inputs {
for _, level := range levels {
- for mode, chunkPattern := range chunks {
- t.Run(fmt.Sprintf("%s/%s/level_%d", name, mode, level), func(t *testing.T) {
- compressed := compressForRoundTrip(t, input, level, chunkPattern)
+ for _, chunk := range chunks {
+ t.Run(fmt.Sprintf("%s/%s/level_%d", input.name, chunk.name, level), func(t *testing.T) {
+ compressed := compressForRoundTrip(t, input.data, level, chunk.pattern)
checkRoundTrip(t, "standard", func() io.ReadCloser {
return stdflate.NewReader(bytes.NewReader(compressed))
- }, input)
+ }, input.data)
checkRoundTrip(t, "local", func() io.ReadCloser {
return NewReader(bytes.NewReader(compressed))
- }, input)
+ }, input.data)
})
}
}
}
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M flate/large_low_entropy_test.go
gofmt -w flate/large_low_entropy_test.go flate/huffman_bit_writer.go
Chunk ID: 1a4b4e Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'TestLargeLowEntropyRoundTripVisible|TestWriteBlock|TestWriteBlockDynamic|TestWriteBlockDynamicSync' -count=1
Chunk ID: ee59fb Wall time: 1.6456 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 1.303s
go test ./flate -run 'Regression|TestWriter|TestReader|TestDict|TestLargeLowEntropyRoundTripVisible' -count=1
Chunk ID: 296931 Wall time: 4.7115 seconds Process exited with code 0 Original token count: 12 Output: ok [code-host]/klauspost/compress/flate 4.367s
find flate/testdata -name '*.got' -o -name '*.reset.got'
Chunk ID: cffa22 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go build ./...
Chunk ID: cf901f Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
rg -n "DBG|fmt\.Println|\.got" flate/huffman_bit_writer.go flate/deflate.go flate/large_low_entropy_test.go flate/testdata
Chunk ID: d4fa5f
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 184
Output:
flate/deflate.go:328: //fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
flate/huffman_bit_writer.go:1027: fmt.Println("stored", abs, "<", max)
flate/huffman_bit_writer.go:1049: fmt.Println("stored,", ssize, "<=", estBits)
flate/huffman_bit_writer.go:1061: fmt.Println("NOT reusing, reuse:", reuseSize/8, "> new:", estBits/8, "header est:", w.lastHeader/8, "bytes")
flate/huffman_bit_writer.go:1067: fmt.Println("reusing, reuse:", reuseSize/8, "> new:", estBits/8, "- header est:", w.lastHeader/8)
flate/huffman_bit_writer.go:1087: fmt.Println("header:", count/8)
flate/huffman_bit_writer.go:1163: fmt.Println("wrote", nb, "bits,", nb/8, "bytes.")
nl -ba flate/huffman_bit_writer.go | sed -n '704,716p'
Chunk ID: f3a22d
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 101
Output:
704 // We want a new block/table
705 if w.lastHeader == 0 {
706 if fillReuse && !sync {
707 w.fillTokens()
708 numLiterals, numOffsets = maxNumLit, maxNumDist
709 } else {
710 w.literalFreq[endBlockMarker] = 1
711 if input != nil && numLiterals <= endBlockMarker {
712 numLiterals = endBlockMarker + 1
713 }
714 }
715
716 w.generate()
nl -ba flate/large_low_entropy_test.go | sed -n '1,130p'
Chunk ID: f988aa
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 826
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 inputs := []struct {
13 name string
14 data []byte
15 }{
16 {"low", make([]byte, 1<<20)},
17 {"medium", makeMediumEntropy(384 << 10)},
18 {"high", makeHighEntropy(256 << 10)},
19 }
20 levels := []int{
21 HuffmanOnly,
22 DefaultCompression,
23 NoCompression,
24 BestSpeed,
25 2, 3, 4, 5, 6, 7, 8,
26 BestCompression,
27 }
28 chunks := []struct {
29 name string
30 pattern []int
31 }{
32 {"single", nil},
33 {"chunked", []int{1, 3, 257, 8191, 65536}},
34 }
35
36 for _, input := range inputs {
37 for _, level := range levels {
38 for _, chunk := range chunks {
39 t.Run(fmt.Sprintf("%s/%s/level_%d", input.name, chunk.name, level), func(t *testing.T) {
40 compressed := compressForRoundTrip(t, input.data, level, chunk.pattern)
41 checkRoundTrip(t, "standard", func() io.ReadCloser {
42 return stdflate.NewReader(bytes.NewReader(compressed))
43 }, input.data)
44 checkRoundTrip(t, "local", func() io.ReadCloser {
45 return NewReader(bytes.NewReader(compressed))
46 }, input.data)
47 })
48 }
49 }
50 }
51 }
52
53 func compressForRoundTrip(t *testing.T, input []byte, level int, chunks []int) []byte {
54 t.Helper()
55
56 var compressed bytes.Buffer
57 w, err := NewWriter(&compressed, level)
58 if err != nil {
59 t.Fatalf("NewWriter(%d): %v", level, err)
60 }
61 if len(chunks) == 0 {
62 if _, err := w.Write(input); err != nil {
63 t.Fatalf("Write: %v", err)
64 }
65 } else {
66 for pos, i := 0, 0; pos < len(input); i++ {
67 n := chunks[i%len(chunks)]
68 if n > len(input)-pos {
69 n = len(input) - pos
70 }
71 if _, err := w.Write(input[pos : pos+n]); err != nil {
72 t.Fatalf("Write chunk at %d: %v", pos, err)
73 }
74 pos += n
75 }
76 }
77 if err := w.Close(); err != nil {
78 t.Fatalf("Close: %v", err)
79 }
80 return compressed.Bytes()
81 }
82
83 func checkRoundTrip(t *testing.T, name string, newReader func() io.ReadCloser, input []byte) {
84 t.Helper()
85
86 r := newReader()
87 out, err := io.ReadAll(r)
88 _ = r.Close()
89 if err != nil {
90 t.Fatalf("%s reader rejected stream: %v", name, err)
91 }
92 if !bytes.Equal(out, input) {
93 t.Fatalf("%s reader mismatch: got %d bytes, want %d", name, len(out), len(input))
94 }
95 }
96
97 func makeMediumEntropy(n int) []byte {
98 out := make([]byte, n)
99 for i := range out {
100 out[i] = byte((i/7 + i/251) & 15)
101 }
102 return out
103 }
104
105 func makeHighEntropy(n int) []byte {
106 out := make([]byte, n)
107 var x uint32 = 1
108 for i := range out {
109 x = x*1664525 + 1013904223
110 out[i] = byte(x >> 24)
111 }
112 return out
113 }
cat <<'EOF' >/tmp/repro2.go
package main
import (
"bytes"
stdflate "compress/flate"
"fmt"
"io"
kflate "[code-host]/klauspost/compress/flate"
)
func data(n int, kind string) []byte { b:=make([]byte,n); var x uint32=1; for i:=range b { switch kind { case "low": b[i]=0; case "medium": b[i]=byte((i/7+i/251)&15); default: x=x*1664525+1013904223; b[i]=byte(x>>24) } }; return b }
func main(){
levels:=[]int{kflate.HuffmanOnly,kflate.DefaultCompression,kflate.NoCompression,1,2,3,4,5,6,7,8,9}
for _, kind:= range []string{"low","medium","high"}{
input:=data(1<<20, kind)
for _, level:= range levels{
for _, chunked := range []bool{false,true}{
var b bytes.Buffer
w,_:=kflate.NewWriter(&b, level)
if chunked { chunks:=[]int{1,3,257,8191,65536}; for pos,i:=0,0; pos<len(input); i++ { n:=chunks[i%len(chunks)]; if n>len(input)-pos { n=len(input)-pos }; if _,err:=w.Write(input[pos:pos+n]); err!=nil { panic(err) }; pos+=n } } else { if _,err:=w.Write(input); err!=nil { panic(err) } }
if err:=w.Close(); err!=nil { panic(err) }
r:=stdflate.NewReader(bytes.NewReader(b.Bytes()))
out,err:=io.ReadAll(r); r.Close()
if err!=nil || !bytes.Equal(out,input) { fmt.Printf("FAIL kind=%s level=%d chunk=%v clen=%d err=%v out=%d\n",kind,level,chunked,b.Len(),err,len(out)); return }
}
}
}
}
EOF
go run /tmp/repro2.goChunk ID: 22fe5b Wall time: 1.2795 seconds Process exited with code 0 Original token count: 0 Output:
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 11.91s ==============================
Reproduce this trial: git checkout 2f94510 && PYTHONPATH=src python3 scripts/build_site.py , then open trial/trial_80a395a110eb4f34. Re-running the agent live requires EVAL_PLATFORM_ENABLE_OAUTH_SMOKE=1 and is non-deterministic.
Trial trial_80a395a110eb4f34 · verifier authoritative; classifier explanatory.