tests/test.sh exit code (0 → resolved); the classification below is post-hoc and cannot change it.pwd && rg -n "deflateLazy|choose|dynamic|stored|fixed|Block" flate/deflate.go flate -S
Chunk ID: b2ddcc
Wall time: 0.0001 seconds
Process exited with code 0
Original token count: 5673
Output:
/app
flate/deflate.go:47: maxFlateBlockTokens = 1 << 15
flate/deflate.go:48: maxStoreBlockSize = 65535
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:187:// to determine if the block should be stored on no matches, or
flate/deflate.go:189:func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
flate/deflate.go:196: d.w.writeBlockHuff(eof, window, d.sync)
flate/deflate.go: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:354:func (d *compressor) writeStoredBlock(buf []byte) error {
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:421: d.h = newHuffmanEncoder(maxFlateBlockTokens)
flate/deflate.go:452: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:511: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:513: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:552: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:554: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:612: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:614: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:629: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:630: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:646: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:647: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:666: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:667: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:682: if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
flate/deflate.go:683: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
flate/deflate.go:690:func (d *compressor) fillBlock(b []byte) int {
flate/deflate.go:703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:712: // We only compress if we have maxStoreBlockSize.
flate/deflate.go:723: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
flate/deflate.go:725: d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
flate/deflate.go:738: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
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:790: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:791: d.fill = (*compressor).fillBlock
flate/deflate.go:796: d.fill = (*compressor).fillBlock
flate/deflate.go:804: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:805: d.fill = (*compressor).fillBlock
flate/deflate.go:813: d.step = (*compressor).deflateLazy
flate/deflate.go:816: d.fast = &fastEncL5Window{maxOffset: int32(-level), cur: maxStoreBlockSize}
flate/deflate.go:817: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:818: d.fill = (*compressor).fillBlock
flate/level1.go:21: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level1.go:51: s := e.addBlock(src)
flate/level1.go:55: if len(src) < minNonLiteralBlockSize {
flate/huffman_code.go:89:// Generates a HuffmanCode corresponding to the fixed literal table
flate/huffman_code.go:129:var fixedLiteralEncoding = generateFixedLiteralEncoding()
flate/huffman_code.go:130:var fixedOffsetEncoding = generateFixedOffsetEncoding()
flate/level6.go:14: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level6.go:62: s := e.addBlock(src)
flate/level6.go:66: if len(src) < minNonLiteralBlockSize {
flate/level4.go:14: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level4.go:55: s := e.addBlock(src)
flate/level4.go:59: if len(src) < minNonLiteralBlockSize {
flate/token_test.go:35: wr.writeBlockDynamic(tok, true, nil, true)
flate/flate_test.go:322: "fixed block, use reserved symbol 287",
flate/deflate.go:47: maxFlateBlockTokens = 1 << 15
flate/deflate.go:48: maxStoreBlockSize = 65535
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:187:// to determine if the block should be stored on no matches, or
flate/deflate.go:189:func (d *compressor) writeBlockSkip(tok *tokens, index int, eof bool) error {
flate/deflate.go:196: d.w.writeBlockHuff(eof, window, d.sync)
flate/deflate.go: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:354:func (d *compressor) writeStoredBlock(buf []byte) error {
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:421: d.h = newHuffmanEncoder(maxFlateBlockTokens)
flate/deflate.go:452: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:511: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:513: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:552: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:554: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:612: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:614: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:629: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:630: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:646: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:647: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:666: if d.tokens.n == maxFlateBlockTokens {
flate/deflate.go:667: if d.err = d.writeBlock(&d.tokens, s.index, false); d.err != nil {
flate/deflate.go:682: if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
flate/deflate.go:683: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
flate/deflate.go:690:func (d *compressor) fillBlock(b []byte) int {
flate/deflate.go:703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
flate/deflate.go:712: // We only compress if we have maxStoreBlockSize.
flate/deflate.go:723: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
flate/deflate.go:725: d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
flate/deflate.go:738: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
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:790: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:791: d.fill = (*compressor).fillBlock
flate/deflate.go:796: d.fill = (*compressor).fillBlock
flate/deflate.go:804: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:805: d.fill = (*compressor).fillBlock
flate/deflate.go:813: d.step = (*compressor).deflateLazy
flate/deflate.go:816: d.fast = &fastEncL5Window{maxOffset: int32(-level), cur: maxStoreBlockSize}
flate/deflate.go:817: d.window = make([]byte, maxStoreBlockSize)
flate/deflate.go:818: d.fill = (*compressor).fillBlock
flate/token.go:135: n uint16 // Must be able to contain maxStoreBlockSize
flate/token.go:136: tokens [maxStoreBlockSize + 1]token
flate/token.go:312: t.tokens[t.n] = token(endBlockMarker)
flate/level3.go:15: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level3.go:53: s := e.addBlock(src)
flate/level3.go:56: if len(src) < minNonLiteralBlockSize {
flate/huffman_bit_writer.go:20: endBlockMarker = 256
flate/huffman_bit_writer.go:30: // where we check if fixed size is smaller.
flate/huffman_bit_writer.go:199: w.writeCode(w.literalEncoding.codes[endBlockMarker])
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: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: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:408:// storedSize calculates the stored size, including header.
flate/huffman_bit_writer.go:411:func (w *huffmanBitWriter) storedSize(in []byte) (int, bool) {
flate/huffman_bit_writer.go:415: if len(in) <= maxStoreBlockSize {
flate/huffman_bit_writer.go:453:// Write the header of a dynamic Huffman block to the output stream.
flate/huffman_bit_writer.go:499:// writeStoredHeader will write a stored header.
flate/huffman_bit_writer.go:500:// If the stored block is only used for EOF,
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:552:// stored block.
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:568: storedSize, storable := w.storedSize(input)
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: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:598: if storable && storedSize <= size {
flate/huffman_bit_writer.go:605: if literalEncoding == fixedLiteralEncoding {
flate/huffman_bit_writer.go:615:// writeBlockDynamic encodes a block using a dynamic Huffman table.
flate/huffman_bit_writer.go:619:// input size the block is stored.
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:651: ssize, storable := w.storedSize(input)
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: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:808: // We haven't found a single match. If we want to go with the dynamic encoding,
flate/huffman_bit_writer.go:831: // Only last token should be endBlockMarker.
flate/huffman_bit_writer.go:833: if tokens[len(tokens)-1] == endBlockMarker {
flate/huffman_bit_writer.go:968: w.writeCode(leCodes[endBlockMarker])
flate/huffman_bit_writer.go:983:// writeBlockHuff encodes a block of bytes as either
flate/huffman_bit_writer.go:986:func (w *huffmanBitWriter) writeBlockHuff(eof bool, input []byte, sync bool) {
flate/huffman_bit_writer.go:1001: const numLiterals = endBlockMarker + 1
flate/huffman_bit_writer.go:1010: ssize, storable := w.storedSize(input)
flate/huffman_bit_writer.go:1025: fmt.Println("stored", abs, "<", max)
flate/huffman_bit_writer.go:1033: w.literalFreq[endBlockMarker] = 1
flate/huffman_bit_writer.go:1047: fmt.Println("stored,", ssize, "<=", estBits)
flate/huffman_bit_writer.go:1062: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/huffman_bit_writer.go:1169: w.writeCode(w.literalEncoding.codes[endBlockMarker])
flate/inflate_test.go:110: {"0 0 0 0 0", "invalid stored block lengths", 1},
flate/inflate_test.go:111: {"3 0", "fixed", 0},
flate/inflate_test.go:113: {"1 1 0 fe ff 0", "stored", 0},
flate/inflate_test.go:229: {"3 0", "use fixed blocks", 0, -15, 1, false},
flate/inflate_test.go:284:func TestReaderPartialBlock(t *testing.T) {
flate/inflate_test.go:290: r := NewReaderOpts(bytes.NewReader(data), WithPartialBlock())
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: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:81:func (e *fastGen) addBlock(src []byte) int32 {
flate/level2.go:18: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level2.go:49: s := e.addBlock(src)
flate/level2.go:53: if len(src) < minNonLiteralBlockSize {
flate/_gen/gen_inflate.go:40:// fixed distance encoding associated with fixed Huffman blocks.
flate/_gen/gen_inflate.go:120: f.finishBlock()
flate/_gen/gen_inflate.go:294: f.WriteString("func (f *decompressor) huffmanBlockDecoder() {\n")
flate/writer_test.go:409: var length = maxStoreBlockSize*30 + 500
flate/writer_test.go:436: // We choose a different buffer size,
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:293: nextBlock
flate/inflate.go:347:func (f *decompressor) nextBlock() {
flate/inflate.go:360: f.dataBlock()
flate/inflate.go:362: fmt.Println("stored block")
flate/inflate.go:365: // compressed, fixed Huffman tables
flate/inflate.go:366: f.hl = &fixedHuffmanDecoder
flate/inflate.go:368: f.huffmanBlockDecoder()
flate/inflate.go:373: // compressed, dynamic Huffman tables
flate/inflate.go:379: f.huffmanBlockDecoder()
flate/inflate.go:381: fmt.Println("dynamic huffman block")
flate/inflate.go:455:// Compression with dynamic Huffman codes
flate/inflate.go:581: if f.h1.maxRead < f.bits[endBlockMarker] {
flate/inflate.go:582: f.h1.maxRead = f.bits[endBlockMarker]
flate/inflate.go:595:func (f *decompressor) dataBlock() {
flate/inflate.go:635: f.finishBlock()
flate/inflate.go:665: f.finishBlock()
flate/inflate.go:668:func (f *decompressor) finishBlock() {
flate/inflate.go:679: f.step = nextBlock
flate/inflate.go:686: case nextBlock:
flate/inflate.go:687: f.nextBlock()
flate/inflate.go:775:func fixedHuffmanDecoderInit() {
flate/inflate.go:776: fixedOnce.Do(func() {
flate/inflate.go:791: fixedHuffmanDecoder.init(bits[:])
flate/inflate.go:803: step: nextBlock,
flate/inflate.go:811:// WithPartialBlock tells decompressor to return after each block,
flate/inflate.go:813:func WithPartialBlock() ReaderOpt {
flate/inflate.go:828: fixedHuffmanDecoderInit()
flate/inflate.go:834: f.step = nextBlock
flate/level5.go:14: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level5.go:62: s := e.addBlock(src)
flate/level5.go:66: if len(src) < minNonLiteralBlockSize {
flate/level5.go:325: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/level5.go:374: s := e.addBlock(src)
flate/level5.go:378: if len(src) < minNonLiteralBlockSize {
flate/level5.go:639:func (e *fastEncL5Window) addBlock(src []byte) int32 {
flate/deflate_test.go:594:// compressor.encSpeed method (0, 16, 128), as well as near maxStoreBlockSize
flate/huffman_bit_writer_test.go:19:// TestBlockHuff tests huffman encoding against reference files
flate/huffman_bit_writer_test.go:23:func TestBlockHuff(t *testing.T) {
flate/huffman_bit_writer_test.go:36: testBlockHuff(t, in, out)
flate/huffman_bit_writer_test.go:41:func testBlockHuff(t *testing.T, in, out string) {
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:167:func TestWriteBlock(t *testing.T) {
flate/huffman_bit_writer_test.go:168: for _, test := range writeBlockTests {
flate/huffman_bit_writer_test.go:169: testBlock(t, test, "wb")
flate/huffman_bit_writer_test.go:173:// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
flate/huffman_bit_writer_test.go:175:func TestWriteBlockDynamic(t *testing.T) {
flate/huffman_bit_writer_test.go:176: for _, test := range writeBlockTests {
flate/huffman_bit_writer_test.go:177: testBlock(t, test, "dyn")
flate/huffman_bit_writer_test.go:181:// TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
flate/huffman_bit_writer_test.go:183:func TestWriteBlockDynamicSync(t *testing.T) {
flate/huffman_bit_writer_test.go:184: for _, test := range writeBlockTests {
flate/huffman_bit_writer_test.go:185: testBlock(t, test, "sync")
flate/huffman_bit_writer_test.go:189:// testBlock tests a block against its references,
flate/huffman_bit_writer_test.go:191:func testBlock(t *testing.T, test huffTest, ttype string) {
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/stateless.go:12: maxStatelessBlock = math.MaxInt16
flate/stateless.go:13: // dictionary will be taken from maxStatelessBlock, so limit it.
flate/stateless.go:109: if len(todo) > maxStatelessBlock-maxStatelessDict {
flate/stateless.go:110: todo = todo[:maxStatelessBlock-maxStatelessDict]
flate/stateless.go:112: } else if len(todo) > maxStatelessBlock-len(dict) {
flate/stateless.go:113: todo = todo[:maxStatelessBlock-len(dict)]
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:157: // Align, only a stored block can do that.
flate/stateless.go:179: minNonLiteralBlockSize = 1 + 1 + inputMargin
flate/stateless.go:190: if len(src)-int(startAt) < minNonLiteralBlockSize {
flate/inflate_gen.go:16:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:96: f.finishBlock()
flate/inflate_gen.go:267:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:347: f.finishBlock()
flate/inflate_gen.go:518:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:598: f.finishBlock()
flate/inflate_gen.go:769:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:849: f.finishBlock()
flate/inflate_gen.go:1020:// fixed distance encoding associated with fixed Huffman blocks.
flate/inflate_gen.go:1100: f.finishBlock()
flate/inflate_gen.go:1268:func (f *decompressor) huffmanBlockDecoder() {
go test ./flate -run 'Test|Regression|Round|Deflate|Inflate' -count=1
Chunk ID: 6a0be1 Wall time: 1.0019 seconds Process running with session ID 19852 Original token count: 0 Output:
git status --short
Chunk ID: c1e871 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
nl -ba flate/deflate.go | sed -n '160,230p'
Chunk ID: 19baa3
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 593
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
211 // dictionary and calculate all hashes.
212 // This is much faster than doing a full encode.
213 // Should only be used after a start/reset.
214 func (d *compressor) fillWindow(b []byte) {
215 // Do not fill window if we are in store-only or huffman mode.
216 if d.level <= 0 && d.level > -MinCustomWindowSize {
217 return
218 }
219 if d.fast != nil {
220 // encode the last data, but discard the result
221 if len(b) > maxMatchOffset {
222 b = b[len(b)-maxMatchOffset:]
223 }
224 d.fast.Encode(&d.tokens, b)
225 d.tokens.Reset()
226 return
227 }
228 s := d.state
229 // If we are given too much, cut it.
230 if len(b) > windowSize {
nl -ba flate/deflate.go | sed -n '408,690p'
Chunk ID: fe8ede
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 2680
Output:
408 func (d *compressor) deflateLazy() {
409 s := d.state
410 // Sanity enables additional runtime tests.
411 // It's intended to be used during development
412 // to supplement the currently ad-hoc unit tests.
413 const sanity = debugDeflate
414
415 if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
416 return
417 }
418 if d.windowEnd != s.index && d.chain > 100 {
419 // Get literal huffman coder.
420 if d.h == nil {
421 d.h = newHuffmanEncoder(maxFlateBlockTokens)
422 }
423 var tmp [256]uint16
424 for _, v := range d.window[s.index:d.windowEnd] {
425 tmp[v]++
426 }
427 d.h.generate(tmp[:], 15)
428 }
429
430 s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
431
432 for {
433 if sanity && s.index > d.windowEnd {
434 panic("index > windowEnd")
435 }
436 lookahead := d.windowEnd - s.index
437 if lookahead < minMatchLength+maxMatchLength {
438 if !d.sync {
439 return
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
676 }
677 }
678 }
679 }
680
681 func (d *compressor) store() {
682 if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
683 d.err = d.writeStoredBlock(d.window[:d.windowEnd])
684 d.windowEnd = 0
685 }
686 }
687
688 // fillWindow will fill the buffer with data for huffman-only compression.
689 // The number of bytes copied is returned.
690 func (d *compressor) fillBlock(b []byte) int {
nl -ba flate/huffman_bit_writer.go | sed -n '615,760p'
Chunk ID: da7b08
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1308
Output:
615 // writeBlockDynamic encodes a block using a dynamic Huffman table.
616 // This should be used if the symbols used have a disproportionate
617 // histogram distribution.
618 // If input is supplied and the compression savings are below 1/16th of the
619 // input size the block is stored.
620 func (w *huffmanBitWriter) writeBlockDynamic(tokens *tokens, eof bool, input []byte, sync bool) {
621 if w.err != nil {
622 return
623 }
624
625 sync = sync || eof
626 if sync {
627 tokens.AddEOB()
628 }
629
630 // We cannot reuse pure huffman table, and must mark as EOF.
631 if (w.lastHuffMan || eof) && w.lastHeader > 0 {
632 // We will not try to reuse.
633 w.writeCode(w.literalEncoding.codes[endBlockMarker])
634 w.lastHeader = 0
635 w.lastHuffMan = false
636 }
637
638 // fillReuse enables filling of empty values.
639 // This will make encodings always reusable without testing.
640 // However, this does not appear to benefit on most cases.
641 const fillReuse = false
642
643 // Check if we can reuse...
644 if !fillReuse && w.lastHeader > 0 && !w.canReuse(tokens) {
645 w.writeCode(w.literalEncoding.codes[endBlockMarker])
646 w.lastHeader = 0
647 }
648
649 numLiterals, numOffsets := w.indexTokens(tokens, fillReuse && !sync)
650 extraBits := 0
651 ssize, storable := w.storedSize(input)
652
653 const usePrefs = true
654 if storable || w.lastHeader > 0 {
655 extraBits = w.extraBitSize()
656 }
657
658 var size int
659
660 // Check if we should reuse.
661 if w.lastHeader > 0 {
662 // Estimate size for using a new table.
663 // Use the previous header size as the best estimate.
664 newSize := w.lastHeader + tokens.EstimatedBits()
665 newSize += int(w.literalEncoding.codes[endBlockMarker].len()) + newSize>>w.logNewTablePenalty
666
667 // The estimated size is calculated as an optimal table.
668 // We add a penalty to make it more realistic and re-use a bit more.
669 reuseSize := w.dynamicReuseSize(w.literalEncoding, w.offsetEncoding) + extraBits
670
671 // Check if a new table is better.
672 if newSize < reuseSize {
673 // Write the EOB we owe.
674 w.writeCode(w.literalEncoding.codes[endBlockMarker])
675 size = newSize
676 w.lastHeader = 0
677 } else {
678 size = reuseSize
679 }
680
681 if tokens.n < maxPredefinedTokens {
682 if preSize := w.fixedSize(extraBits) + 7; usePrefs && preSize < size {
683 // Check if we get a reasonable size decrease.
684 if storable && ssize <= size {
685 w.writeStoredHeader(len(input), eof)
686 w.writeBytes(input)
687 return
688 }
689 w.writeFixedHeader(eof)
690 if !sync {
691 tokens.AddEOB()
692 }
693 w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
694 return
695 }
696 }
697 // Check if we get a reasonable size decrease.
698 if storable && ssize <= size {
699 w.writeStoredHeader(len(input), eof)
700 w.writeBytes(input)
701 return
702 }
703 }
704
705 // We want a new block/table
706 if w.lastHeader == 0 {
707 if fillReuse && !sync {
708 w.fillTokens()
709 numLiterals, numOffsets = maxNumLit, maxNumDist
710 } else {
711 w.literalFreq[endBlockMarker] = 1
712 }
713
714 w.generate()
715 // Generate codegen and codegenFrequencies, which indicates how to encode
716 // the literalEncoding and the offsetEncoding.
717 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
718 w.codegenEncoding.generate(w.codegenFreq[:], 7)
719
720 var numCodegens int
721 if fillReuse && !sync {
722 // Reindex for accurate size...
723 w.indexTokens(tokens, true)
724 }
725 size, numCodegens = w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
726
727 // Store predefined, if we don't get a reasonable improvement.
728 if tokens.n < maxPredefinedTokens {
729 if preSize := w.fixedSize(extraBits); usePrefs && preSize <= size {
730 // Store bytes, if we don't get an improvement.
731 if storable && ssize <= preSize {
732 w.writeStoredHeader(len(input), eof)
733 w.writeBytes(input)
734 return
735 }
736 w.writeFixedHeader(eof)
737 if !sync {
738 tokens.AddEOB()
739 }
740 w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
741 return
742 }
743 }
744
745 if storable && ssize <= size {
746 // Store bytes, if we don't get an improvement.
747 w.writeStoredHeader(len(input), eof)
748 w.writeBytes(input)
749 return
750 }
751
752 // Write Huffman table.
753 w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
754 if !sync {
755 w.lastHeader, _ = w.headerSize()
756 }
757 w.lastHuffMan = false
758 }
759
760 if sync {
find flate -maxdepth 3 -type f | sort | sed -n '1,200p'
Chunk ID: 284cbf 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
nl -ba flate/large_low_entropy_test.go | sed -n '1,240p'
Chunk ID: 6b1f70
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 353
Output:
1 package flate
2
3 import (
4 "bytes"
5 stdflate "compress/flate"
6 "io"
7 "testing"
8 )
9
10 func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
11 input := make([]byte, 1<<20)
12
13 var compressed bytes.Buffer
14 w, err := NewWriter(&compressed, BestCompression)
15 if err != nil {
16 t.Fatalf("NewWriter: %v", err)
17 }
18 if _, err := w.Write(input); err != nil {
19 t.Fatalf("Write: %v", err)
20 }
21 if err := w.Close(); err != nil {
22 t.Fatalf("Close: %v", err)
23 }
24
25 stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
26 stdOut, err := io.ReadAll(stdReader)
27 _ = stdReader.Close()
28 if err != nil {
29 t.Fatalf("standard reader rejected stream: %v", err)
30 }
31 if !bytes.Equal(stdOut, input) {
32 t.Fatalf("standard reader mismatch: got %d bytes, want %d", len(stdOut), len(input))
33 }
34
35 localReader := NewReader(bytes.NewReader(compressed.Bytes()))
36 localOut, err := io.ReadAll(localReader)
37 _ = localReader.Close()
38 if err != nil {
39 t.Fatalf("local reader rejected stream: %v", err)
40 }
41 if !bytes.Equal(localOut, input) {
42 t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
43 }
44 }
nl -ba flate/token.go | sed -n '120,340p'
Chunk ID: 5f14fc
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1706
Output:
120 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
121 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
122 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
123 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
124 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
125 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
126 }
127
128 type token uint32
129
130 type tokens struct {
131 extraHist [32]uint16 // codes 256->maxnumlit
132 offHist [32]uint16 // offset codes
133 litHist [256]uint16 // codes 0->255
134 nFilled int
135 n uint16 // Must be able to contain maxStoreBlockSize
136 tokens [maxStoreBlockSize + 1]token
137 }
138
139 func (t *tokens) Reset() {
140 if t.n == 0 {
141 return
142 }
143 t.n = 0
144 t.nFilled = 0
145 for i := range t.litHist[:] {
146 t.litHist[i] = 0
147 }
148 for i := range t.extraHist[:] {
149 t.extraHist[i] = 0
150 }
151 for i := range t.offHist[:] {
152 t.offHist[i] = 0
153 }
154 }
155
156 func (t *tokens) Fill() {
157 if t.n == 0 {
158 return
159 }
160 for i, v := range t.litHist[:] {
161 if v == 0 {
162 t.litHist[i] = 1
163 t.nFilled++
164 }
165 }
166 for i, v := range t.extraHist[:literalCount-256] {
167 if v == 0 {
168 t.nFilled++
169 t.extraHist[i] = 1
170 }
171 }
172 for i, v := range t.offHist[:offsetCodeCount] {
173 if v == 0 {
174 t.offHist[i] = 1
175 }
176 }
177 }
178
179 func indexTokens(in []token) tokens {
180 var t tokens
181 t.indexTokens(in)
182 return t
183 }
184
185 func (t *tokens) indexTokens(in []token) {
186 t.Reset()
187 for _, tok := range in {
188 if tok < matchType {
189 t.AddLiteral(tok.literal())
190 continue
191 }
192 t.AddMatch(uint32(tok.length()), tok.offset()&matchOffsetOnlyMask)
193 }
194 }
195
196 // emitLiteral writes a literal chunk and returns the number of bytes written.
197 func emitLiteral(dst *tokens, lit []byte) {
198 for _, v := range lit {
199 dst.tokens[dst.n] = token(v)
200 dst.litHist[v]++
201 dst.n++
202 }
203 }
204
205 func (t *tokens) AddLiteral(lit byte) {
206 t.tokens[t.n] = token(lit)
207 t.litHist[lit]++
208 t.n++
209 }
210
211 // from https://stackoverflow.com/a/28730362
212 func mFastLog2(val float32) float32 {
213 ux := int32(math.Float32bits(val))
214 log2 := (float32)(((ux >> 23) & 255) - 128)
215 ux &= -0x7f800001
216 ux += 127 << 23
217 uval := math.Float32frombits(uint32(ux))
218 log2 += ((-0.34484843)*uval+2.02466578)*uval - 0.67487759
219 return log2
220 }
221
222 // EstimatedBits will return an minimum size estimated by an *optimal*
223 // compression of the block.
224 // The size of the block
225 func (t *tokens) EstimatedBits() int {
226 shannon := float32(0)
227 bits := int(0)
228 nMatches := 0
229 total := int(t.n) + t.nFilled
230 if total > 0 {
231 invTotal := 1.0 / float32(total)
232 for _, v := range t.litHist[:] {
233 if v > 0 {
234 n := float32(v)
235 shannon += atLeastOne(-mFastLog2(n*invTotal)) * n
236 }
237 }
238 // Just add 15 for EOB
239 shannon += 15
240 for i, v := range t.extraHist[1 : literalCount-256] {
241 if v > 0 {
242 n := float32(v)
243 shannon += atLeastOne(-mFastLog2(n*invTotal)) * n
244 bits += int(lengthExtraBits[i&31]) * int(v)
245 nMatches += int(v)
246 }
247 }
248 }
249 if nMatches > 0 {
250 invTotal := 1.0 / float32(nMatches)
251 for i, v := range t.offHist[:offsetCodeCount] {
252 if v > 0 {
253 n := float32(v)
254 shannon += atLeastOne(-mFastLog2(n*invTotal)) * n
255 bits += int(offsetExtraBits[i&31]) * int(v)
256 }
257 }
258 }
259 return int(shannon) + bits
260 }
261
262 // AddMatch adds a match to the tokens.
263 // This function is very sensitive to inlining and right on the border.
264 func (t *tokens) AddMatch(xlength uint32, xoffset uint32) {
265 if debugDeflate {
266 if xlength >= maxMatchLength+baseMatchLength {
267 panic(fmt.Errorf("invalid length: %v", xlength))
268 }
269 if xoffset >= maxMatchOffset+baseMatchOffset {
270 panic(fmt.Errorf("invalid offset: %v", xoffset))
271 }
272 }
273 oCode := offsetCode(xoffset)
274 xoffset |= oCode << 16
275
276 t.extraHist[lengthCodes1[uint8(xlength)]]++
277 t.offHist[oCode&31]++
278 t.tokens[t.n] = token(matchType | xlength<<lengthShift | xoffset)
279 t.n++
280 }
281
282 // AddMatchLong adds a match to the tokens, potentially longer than max match length.
283 // Length should NOT have the base subtracted, only offset should.
284 func (t *tokens) AddMatchLong(xlength int32, xoffset uint32) {
285 if debugDeflate {
286 if xoffset >= maxMatchOffset+baseMatchOffset {
287 panic(fmt.Errorf("invalid offset: %v", xoffset))
288 }
289 }
290 oc := offsetCode(xoffset)
291 xoffset |= oc << 16
292 for xlength > 0 {
293 xl := xlength
294 if xl > 258 {
295 // We need to have at least baseMatchLength left over for next loop.
296 if xl > 258+baseMatchLength {
297 xl = 258
298 } else {
299 xl = 258 - baseMatchLength
300 }
301 }
302 xlength -= xl
303 xl -= baseMatchLength
304 t.extraHist[lengthCodes1[uint8(xl)]]++
305 t.offHist[oc&31]++
306 t.tokens[t.n] = token(matchType | uint32(xl)<<lengthShift | xoffset)
307 t.n++
308 }
309 }
310
311 func (t *tokens) AddEOB() {
312 t.tokens[t.n] = token(endBlockMarker)
313 t.extraHist[0]++
314 t.n++
315 }
316
317 func (t *tokens) Slice() []token {
318 return t.tokens[:t.n]
319 }
320
321 // VarInt returns the tokens as varint encoded bytes.
322 func (t *tokens) VarInt() []byte {
323 var b = make([]byte, binary.MaxVarintLen32*int(t.n))
324 var off int
325 for _, v := range t.tokens[:t.n] {
326 off += binary.PutUvarint(b[off:], uint64(v))
327 }
328 return b[:off]
329 }
330
331 // FromVarInt restores t to the varint encoded tokens provided.
332 // Any data in t is removed.
333 func (t *tokens) FromVarInt(b []byte) error {
334 var buf = bytes.NewReader(b)
335 var toks []token
336 for {
337 r, err := binary.ReadUvarint(buf)
338 if err == io.EOF {
339 break
340 }
nl -ba flate/huffman_bit_writer.go | sed -n '760,850p'
Chunk ID: 769e41
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 767
Output:
760 if sync {
761 w.lastHeader = 0
762 }
763 // Write the tokens.
764 w.writeTokens(tokens.Slice(), w.literalEncoding.codes, w.offsetEncoding.codes)
765 }
766
767 func (w *huffmanBitWriter) fillTokens() {
768 for i, v := range w.literalFreq[:literalCount] {
769 if v == 0 {
770 w.literalFreq[i] = 1
771 }
772 }
773 for i, v := range w.offsetFreq[:offsetCodeCount] {
774 if v == 0 {
775 w.offsetFreq[i] = 1
776 }
777 }
778 }
779
780 // indexTokens indexes a slice of tokens, and updates
781 // literalFreq and offsetFreq, and generates literalEncoding
782 // and offsetEncoding.
783 // The number of literal and offset tokens is returned.
784 func (w *huffmanBitWriter) indexTokens(t *tokens, filled bool) (numLiterals, numOffsets int) {
785 //copy(w.literalFreq[:], t.litHist[:])
786 *(*[256]uint16)(w.literalFreq[:]) = t.litHist
787 //copy(w.literalFreq[256:], t.extraHist[:])
788 *(*[32]uint16)(w.literalFreq[256:]) = t.extraHist
789 w.offsetFreq = t.offHist
790
791 if t.n == 0 {
792 return
793 }
794 if filled {
795 return maxNumLit, maxNumDist
796 }
797 // get the number of literals
798 numLiterals = len(w.literalFreq)
799 for w.literalFreq[numLiterals-1] == 0 {
800 numLiterals--
801 }
802 // get the number of offsets
803 numOffsets = len(w.offsetFreq)
804 for numOffsets > 0 && w.offsetFreq[numOffsets-1] == 0 {
805 numOffsets--
806 }
807 if numOffsets == 0 {
808 // We haven't found a single match. If we want to go with the dynamic encoding,
809 // we should count at least one offset to be sure that the offset huffman tree could be encoded.
810 w.offsetFreq[0] = 1
811 numOffsets = 1
812 }
813 return
814 }
815
816 func (w *huffmanBitWriter) generate() {
817 w.literalEncoding.generate(w.literalFreq[:literalCount], 15)
818 w.offsetEncoding.generate(w.offsetFreq[:offsetCodeCount], 15)
819 }
820
821 // writeTokens writes a slice of tokens to the output.
822 // codes for literal and offset encoding must be supplied.
823 func (w *huffmanBitWriter) writeTokens(tokens []token, leCodes, oeCodes []hcode) {
824 if w.err != nil {
825 return
826 }
827 if len(tokens) == 0 {
828 return
829 }
830
831 // Only last token should be endBlockMarker.
832 var deferEOB bool
833 if tokens[len(tokens)-1] == endBlockMarker {
834 tokens = tokens[:len(tokens)-1]
835 deferEOB = true
836 }
837
838 // Create slices up to the next power of two to avoid bounds checks.
839 lits := leCodes[:256]
840 offs := oeCodes[:32]
841 lengths := leCodes[lengthCodesStart:]
842 lengths = lengths[:32]
843
844 // Go 1.16 LOVES having these on stack.
845 bits, nbits, nbytes := w.bits, w.nbits, w.nbytes
846
847 for _, t := range tokens {
848 if t < 256 {
849 //w.writeCode(lits[t.literal()])
850 c := lits[t]
{
"session_id": 19852,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 20000
}
, output,
Chunk ID: 9eb233
Wall time: 0.0000 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.56s)
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
FAIL
FAIL [code-host]/klauspost/compress/flate 6.240s
FAIL
nl -ba flate/deflate.go | sed -n '1,170p'
Chunk ID: 5de068
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1570
Output:
1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Copyright (c) 2015 Klaus Post
3 // Use of this source code is governed by a BSD-style
4 // license that can be found in the LICENSE file.
5
6 package flate
7
8 import (
9 "errors"
10 "fmt"
11 "io"
12 "math"
13
14 "[code-host]/klauspost/compress/internal/le"
15 )
16
17 const (
18 NoCompression = 0
19 BestSpeed = 1
20 BestCompression = 9
21 DefaultCompression = -1
22
23 // HuffmanOnly disables Lempel-Ziv match searching and only performs Huffman
24 // entropy encoding. This mode is useful in compressing data that has
25 // already been compressed with an LZ style algorithm (e.g. Snappy or LZ4)
26 // that lacks an entropy encoder. Compression gains are achieved when
27 // certain bytes in the input stream occur more frequently than others.
28 //
29 // Note that HuffmanOnly produces a compressed output that is
30 // RFC 1951 compliant. That is, any valid DEFLATE decompressor will
31 // continue to be able to decompress this output.
32 HuffmanOnly = -2
33 ConstantCompression = HuffmanOnly // compatibility alias.
34
35 logWindowSize = 15
36 windowSize = 1 << logWindowSize
37 windowMask = windowSize - 1
38 logMaxOffsetSize = 15 // Standard DEFLATE
39 minMatchLength = 4 // The smallest match that the compressor looks for
40 maxMatchLength = 258 // The longest match for the compressor
41 minOffsetSize = 1 // The shortest offset that makes any sense
42
43 // The maximum number of tokens we will encode at the time.
44 // Smaller sizes usually creates less optimal blocks.
45 // Bigger can make context switching slow.
46 // We use this for levels 7-9, so we make it big.
47 maxFlateBlockTokens = 1 << 15
48 maxStoreBlockSize = 65535
49 hashBits = 17 // After 17 performance degrades
50 hashSize = 1 << hashBits
51 hashMask = (1 << hashBits) - 1
52 hashShift = (hashBits + minMatchLength - 1) / minMatchLength
53 maxHashOffset = 1 << 28
54
55 skipNever = math.MaxInt32
56
57 debugDeflate = false
58 )
59
60 type compressionLevel struct {
61 good, lazy, nice, chain, fastSkipHashing, level int
62 }
63
64 // Compression levels have been rebalanced from zlib deflate defaults
65 // to give a bigger spread in speed and compression.
66 // See https://blog.klauspost.com/rebalancing-deflate-compression-levels/
67 var levels = []compressionLevel{
68 {}, // 0
69 // Level 1-6 uses specialized algorithm - values not used
70 {0, 0, 0, 0, 0, 1},
71 {0, 0, 0, 0, 0, 2},
72 {0, 0, 0, 0, 0, 3},
73 {0, 0, 0, 0, 0, 4},
74 {0, 0, 0, 0, 0, 5},
75 {0, 0, 0, 0, 0, 6},
76 // Levels 7-9 use increasingly more lazy matching
77 // and increasingly stringent conditions for "good enough".
78 {8, 12, 16, 24, skipNever, 7},
79 {16, 30, 40, 64, skipNever, 8},
80 {32, 258, 258, 1024, skipNever, 9},
81 }
82
83 // advancedState contains state for the advanced levels, with bigger hash tables, etc.
84 type advancedState struct {
85 // deflate state
86 length int
87 offset int
88 maxInsertIndex int
89 chainHead int
90 hashOffset int
91
92 ii uint16 // position of last match, intended to overflow to reset.
93
94 // input window: unprocessed data is window[index:windowEnd]
95 index int
96 hashMatch [maxMatchLength + minMatchLength]uint32
97
98 // Input hash chains
99 // hashHead[hashValue] contains the largest inputIndex with the specified hash value
100 // If hashHead[hashValue] is within the current window, then
101 // hashPrev[hashHead[hashValue] & windowMask] contains the previous index
102 // with the same hash value.
103 hashHead [hashSize]uint32
104 hashPrev [windowSize]uint32
105 }
106
107 type compressor struct {
108 compressionLevel
109
110 h *huffmanEncoder
111 w *huffmanBitWriter
112
113 // compression algorithm
114 fill func(*compressor, []byte) int // copy data to window
115 step func(*compressor) // process window
116
117 window []byte
118 windowEnd int
119 blockStart int // window index where current tokens start
120 err error
121
122 // queued output tokens
123 tokens tokens
124 fast fastEnc
125 state *advancedState
126
127 sync bool // requesting flush
128 byteAvailable bool // if true, still need to process window[index-1].
129 }
130
131 func (d *compressor) fillDeflate(b []byte) int {
132 s := d.state
133 if s.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
134 // shift the window by windowSize
135 //copy(d.window[:], d.window[windowSize:2*windowSize])
136 *(*[windowSize]byte)(d.window) = *(*[windowSize]byte)(d.window[windowSize:])
137 s.index -= windowSize
138 d.windowEnd -= windowSize
139 if d.blockStart >= windowSize {
140 d.blockStart -= windowSize
141 } else {
142 d.blockStart = math.MaxInt32
143 }
144 s.hashOffset += windowSize
145 if s.hashOffset > maxHashOffset {
146 delta := s.hashOffset - 1
147 s.hashOffset -= delta
148 s.chainHead -= delta
149 // Iterate over slices instead of arrays to avoid copying
150 // the entire table onto the stack (Issue #18625).
151 for i, v := range s.hashPrev[:] {
152 if int(v) > delta {
153 s.hashPrev[i] = uint32(int(v) - delta)
154 } else {
155 s.hashPrev[i] = 0
156 }
157 }
158 for i, v := range s.hashHead[:] {
159 if int(v) > delta {
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 }
nl -ba flate/writer_test.go | sed -n '380,470p'
Chunk ID: 5572e2
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 730
Output:
380 }
381
382 _, err = w.Write(in)
383 if err != nil {
384 t.Fatal(err)
385 }
386 err = w.Close()
387 if err != nil {
388 t.Fatal(err)
389 }
390 }
391 })
392 }
393 }
394
395 func TestDeterministicL1(t *testing.T) { testDeterministic(1, t) }
396 func TestDeterministicL2(t *testing.T) { testDeterministic(2, t) }
397 func TestDeterministicL3(t *testing.T) { testDeterministic(3, t) }
398 func TestDeterministicL4(t *testing.T) { testDeterministic(4, t) }
399 func TestDeterministicL5(t *testing.T) { testDeterministic(5, t) }
400 func TestDeterministicL6(t *testing.T) { testDeterministic(6, t) }
401 func TestDeterministicL7(t *testing.T) { testDeterministic(7, t) }
402 func TestDeterministicL8(t *testing.T) { testDeterministic(8, t) }
403 func TestDeterministicL9(t *testing.T) { testDeterministic(9, t) }
404 func TestDeterministicL0(t *testing.T) { testDeterministic(0, t) }
405 func TestDeterministicLM2(t *testing.T) { testDeterministic(-2, t) }
406
407 func testDeterministic(i int, t *testing.T) {
408 // Test so much we cross a good number of block boundaries.
409 var length = maxStoreBlockSize*30 + 500
410 if testing.Short() {
411 length /= 10
412 }
413
414 // Create a random, but compressible stream.
415 rng := rand.New(rand.NewSource(1))
416 t1 := make([]byte, length)
417 for i := range t1 {
418 t1[i] = byte(rng.Int63() & 7)
419 }
420
421 // Do our first encode.
422 var b1 bytes.Buffer
423 br := bytes.NewBuffer(t1)
424 w, err := NewWriter(&b1, i)
425 if err != nil {
426 t.Fatal(err)
427 }
428 // Use a very small prime sized buffer.
429 cbuf := make([]byte, 787)
430 _, err = copyBuffer(w, br, cbuf)
431 if err != nil {
432 t.Fatal(err)
433 }
434 w.Close()
435
436 // We choose a different buffer size,
437 // bigger than a maximum block, and also a prime.
438 var b2 bytes.Buffer
439 cbuf = make([]byte, 81761)
440 br2 := bytes.NewBuffer(t1)
441 w2, err := NewWriter(&b2, i)
442 if err != nil {
443 t.Fatal(err)
444 }
445 _, err = copyBuffer(w2, br2, cbuf)
446 if err != nil {
447 t.Fatal(err)
448 }
449 w2.Close()
450
451 b1b := b1.Bytes()
452 b2b := b2.Bytes()
453
454 if !bytes.Equal(b1b, b2b) {
455 t.Errorf("level %d did not produce deterministic result, result mismatch, len(a) = %d, len(b) = %d", i, len(b1b), len(b2b))
456 }
457
458 // Test using io.WriterTo interface.
459 var b3 bytes.Buffer
460 br = bytes.NewBuffer(t1)
461 w, err = NewWriter(&b3, i)
462 if err != nil {
463 t.Fatal(err)
464 }
465 _, err = br.WriteTo(w)
466 if err != nil {
467 t.Fatal(err)
468 }
469 w.Close()
470
go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 440110
Wall time: 0.4890 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.54s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.539s
FAIL
nl -ba flate/huffman_bit_writer.go | sed -n '1,220p'
Chunk ID: c41e76
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1842
Output:
1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package flate
6
7 import (
8 "fmt"
9 "io"
10 "math"
11
12 "[code-host]/klauspost/compress/internal/le"
13 )
14
15 const (
16 // The largest offset code.
17 offsetCodeCount = 30
18
19 // The special code used to mark the end of a block.
20 endBlockMarker = 256
21
22 // The first length code.
23 lengthCodesStart = 257
24
25 // The number of codegen codes.
26 codegenCodeCount = 19
27 badCode = 255
28
29 // maxPredefinedTokens is the maximum number of tokens
30 // where we check if fixed size is smaller.
31 maxPredefinedTokens = 250
32
33 // bufferFlushSize indicates the buffer size
34 // after which bytes are flushed to the writer.
35 // Should preferably be a multiple of 6, since
36 // we accumulate 6 bytes between writes to the buffer.
37 bufferFlushSize = 246
38 )
39
40 // Minimum length code that emits bits.
41 const lengthExtraBitsMinCode = 8
42
43 // The number of extra bits needed by length code X - LENGTH_CODES_START.
44 var lengthExtraBits = [32]uint8{
45 /* 257 */ 0, 0, 0,
46 /* 260 */ 0, 0, 0, 0, 0, 1, 1, 1, 1, 2,
47 /* 270 */ 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
48 /* 280 */ 4, 5, 5, 5, 5, 0,
49 }
50
51 // The length indicated by length code X - LENGTH_CODES_START.
52 var lengthBase = [32]uint8{
53 0, 1, 2, 3, 4, 5, 6, 7, 8, 10,
54 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
55 64, 80, 96, 112, 128, 160, 192, 224, 255,
56 }
57
58 // Minimum offset code that emits bits.
59 const offsetExtraBitsMinCode = 4
60
61 // offset code word extra bits.
62 var offsetExtraBits = [32]int8{
63 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
64 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
65 9, 9, 10, 10, 11, 11, 12, 12, 13, 13,
66 /* extended window */
67 14, 14,
68 }
69
70 var offsetCombined = [32]uint32{}
71
72 func init() {
73 var offsetBase = [32]uint32{
74 /* normal deflate */
75 0x000000, 0x000001, 0x000002, 0x000003, 0x000004,
76 0x000006, 0x000008, 0x00000c, 0x000010, 0x000018,
77 0x000020, 0x000030, 0x000040, 0x000060, 0x000080,
78 0x0000c0, 0x000100, 0x000180, 0x000200, 0x000300,
79 0x000400, 0x000600, 0x000800, 0x000c00, 0x001000,
80 0x001800, 0x002000, 0x003000, 0x004000, 0x006000,
81
82 /* extended window */
83 0x008000, 0x00c000,
84 }
85
86 for i := range offsetCombined[:] {
87 // Don't use extended window values...
88 if offsetExtraBits[i] == 0 || offsetBase[i] > 0x006000 {
89 continue
90 }
91 offsetCombined[i] = uint32(offsetExtraBits[i]) | (offsetBase[i] << 8)
92 }
93 }
94
95 // The odd order in which the codegen code sizes are written.
96 var codegenOrder = []uint32{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}
97
98 type huffmanBitWriter struct {
99 // writer is the underlying writer.
100 // Do not use it directly; use the write method, which ensures
101 // that Write errors are sticky.
102 writer io.Writer
103
104 // Data waiting to be written is bytes[0:nbytes]
105 // and then the low nbits of bits.
106 bits uint64
107 nbits uint8
108 nbytes uint8
109 lastHuffMan bool
110 literalEncoding *huffmanEncoder
111 tmpLitEncoding *huffmanEncoder
112 offsetEncoding *huffmanEncoder
113 codegenEncoding *huffmanEncoder
114 err error
115 lastHeader int
116 // Set between 0 (reused block can be up to 2x the size)
117 logNewTablePenalty uint
118 bytes [256 + 8]byte
119 literalFreq [lengthCodesStart + 32]uint16
120 offsetFreq [32]uint16
121 codegenFreq [codegenCodeCount]uint16
122
123 // codegen must have an extra space for the final symbol.
124 codegen [literalCount + offsetCodeCount + 1]uint8
125 }
126
127 // Huffman reuse.
128 //
129 // The huffmanBitWriter supports reusing huffman tables and thereby combining block sections.
130 //
131 // This is controlled by several variables:
132 //
133 // If lastHeader is non-zero the Huffman table can be reused.
134 // This also indicates that a Huffman table has been generated that can output all
135 // possible symbols.
136 // It also indicates that an EOB has not yet been emitted, so if a new tabel is generated
137 // an EOB with the previous table must be written.
138 //
139 // If lastHuffMan is set, a table for outputting literals has been generated and offsets are invalid.
140 //
141 // An incoming block estimates the output size of a new table using a 'fresh' by calculating the
142 // optimal size and adding a penalty in 'logNewTablePenalty'.
143 // A Huffman table is not optimal, which is why we add a penalty, and generating a new table
144 // is slower both for compression and decompression.
145
146 func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
147 return &huffmanBitWriter{
148 writer: w,
149 literalEncoding: newHuffmanEncoder(literalCount),
150 tmpLitEncoding: newHuffmanEncoder(literalCount),
151 codegenEncoding: newHuffmanEncoder(codegenCodeCount),
152 offsetEncoding: newHuffmanEncoder(offsetCodeCount),
153 }
154 }
155
156 func (w *huffmanBitWriter) reset(writer io.Writer) {
157 w.writer = writer
158 w.bits, w.nbits, w.nbytes, w.err = 0, 0, 0, nil
159 w.lastHeader = 0
160 w.lastHuffMan = false
161 }
162
163 func (w *huffmanBitWriter) canReuse(t *tokens) (ok bool) {
164 a := t.offHist[:offsetCodeCount]
165 b := w.offsetEncoding.codes
166 b = b[:len(a)]
167 for i, v := range a {
168 if v != 0 && b[i].zero() {
169 return false
170 }
171 }
172
173 a = t.extraHist[:literalCount-256]
174 b = w.literalEncoding.codes[256:literalCount]
175 b = b[:len(a)]
176 for i, v := range a {
177 if v != 0 && b[i].zero() {
178 return false
179 }
180 }
181
182 a = t.litHist[:256]
183 b = w.literalEncoding.codes[:len(a)]
184 for i, v := range a {
185 if v != 0 && b[i].zero() {
186 return false
187 }
188 }
189 return true
190 }
191
192 func (w *huffmanBitWriter) flush() {
193 if w.err != nil {
194 w.nbits = 0
195 return
196 }
197 if w.lastHeader > 0 {
198 // We owe an EOB
199 w.writeCode(w.literalEncoding.codes[endBlockMarker])
200 w.lastHeader = 0
201 }
202 n := w.nbytes
203 for w.nbits != 0 {
204 w.bytes[n] = byte(w.bits)
205 w.bits >>= 8
206 if w.nbits > 8 { // Avoid underflow
207 w.nbits -= 8
208 } else {
209 w.nbits = 0
210 }
211 n++
212 }
213 w.bits = 0
214 if n > 0 {
215 w.write(w.bytes[:n])
216 }
217 w.nbytes = 0
218 }
219
220 func (w *huffmanBitWriter) write(b []byte) {
nl -ba flate/huffman_bit_writer.go | sed -n '360,620p'
Chunk ID: 6d1c5e
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 2157
Output:
360 for numCodegens > 4 && w.codegenFreq[codegenOrder[numCodegens-1]] == 0 {
361 numCodegens--
362 }
363 return 3 + 5 + 5 + 4 + (3 * numCodegens) +
364 w.codegenEncoding.bitLength(w.codegenFreq[:]) +
365 int(w.codegenFreq[16])*2 +
366 int(w.codegenFreq[17])*3 +
367 int(w.codegenFreq[18])*7, numCodegens
368 }
369
370 // dynamicSize returns the size of dynamically encoded data in bits.
371 func (w *huffmanBitWriter) dynamicReuseSize(litEnc, offEnc *huffmanEncoder) (size int) {
372 size = litEnc.bitLength(w.literalFreq[:]) +
373 offEnc.bitLength(w.offsetFreq[:])
374 return size
375 }
376
377 // dynamicSize returns the size of dynamically encoded data in bits.
378 func (w *huffmanBitWriter) dynamicSize(litEnc, offEnc *huffmanEncoder, extraBits int) (size, numCodegens int) {
379 header, numCodegens := w.headerSize()
380 size = header +
381 litEnc.bitLength(w.literalFreq[:]) +
382 offEnc.bitLength(w.offsetFreq[:]) +
383 extraBits
384 return size, numCodegens
385 }
386
387 // extraBitSize will return the number of bits that will be written
388 // as "extra" bits on matches.
389 func (w *huffmanBitWriter) extraBitSize() int {
390 total := 0
391 for i, n := range w.literalFreq[257:literalCount] {
392 total += int(n) * int(lengthExtraBits[i&31])
393 }
394 for i, n := range w.offsetFreq[:offsetCodeCount] {
395 total += int(n) * int(offsetExtraBits[i&31])
396 }
397 return total
398 }
399
400 // fixedSize returns the size of dynamically encoded data in bits.
401 func (w *huffmanBitWriter) fixedSize(extraBits int) int {
402 return 3 +
403 fixedLiteralEncoding.bitLength(w.literalFreq[:]) +
404 fixedOffsetEncoding.bitLength(w.offsetFreq[:]) +
405 extraBits
406 }
407
408 // storedSize calculates the stored size, including header.
409 // The function returns the size in bits and whether the block
410 // fits inside a single block.
411 func (w *huffmanBitWriter) storedSize(in []byte) (int, bool) {
412 if in == nil {
413 return 0, false
414 }
415 if len(in) <= maxStoreBlockSize {
416 return (len(in) + 5) * 8, true
417 }
418 return 0, false
419 }
420
421 func (w *huffmanBitWriter) writeCode(c hcode) {
422 // The function does not get inlined if we "& 63" the shift.
423 w.bits |= c.code64() << (w.nbits & 63)
424 w.nbits += c.len()
425 if w.nbits >= 48 {
426 w.writeOutBits()
427 }
428 }
429
430 // writeOutBits will write bits to the buffer.
431 func (w *huffmanBitWriter) writeOutBits() {
432 bits := w.bits
433 w.bits >>= 48
434 w.nbits -= 48
435 n := w.nbytes
436
437 // We overwrite, but faster...
438 le.Store64(w.bytes[:], n, bits)
439 n += 6
440
441 if n >= bufferFlushSize {
442 if w.err != nil {
443 n = 0
444 return
445 }
446 w.write(w.bytes[:n])
447 n = 0
448 }
449
450 w.nbytes = n
451 }
452
453 // Write the header of a dynamic Huffman block to the output stream.
454 //
455 // numLiterals The number of literals specified in codegen
456 // numOffsets The number of offsets specified in codegen
457 // numCodegens The number of codegens used in codegen
458 func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) {
459 if w.err != nil {
460 return
461 }
462 var firstBits int32 = 4
463 if isEof {
464 firstBits = 5
465 }
466 w.writeBits(firstBits, 3)
467 w.writeBits(int32(numLiterals-257), 5)
468 w.writeBits(int32(numOffsets-1), 5)
469 w.writeBits(int32(numCodegens-4), 4)
470
471 for i := range numCodegens {
472 value := uint(w.codegenEncoding.codes[codegenOrder[i]].len())
473 w.writeBits(int32(value), 3)
474 }
475
476 i := 0
477 for {
478 var codeWord = uint32(w.codegen[i])
479 i++
480 if codeWord == badCode {
481 break
482 }
483 w.writeCode(w.codegenEncoding.codes[codeWord])
484
485 switch codeWord {
486 case 16:
487 w.writeBits(int32(w.codegen[i]), 2)
488 i++
489 case 17:
490 w.writeBits(int32(w.codegen[i]), 3)
491 i++
492 case 18:
493 w.writeBits(int32(w.codegen[i]), 7)
494 i++
495 }
496 }
497 }
498
499 // writeStoredHeader will write a stored header.
500 // If the stored block is only used for EOF,
501 // it is replaced with a fixed huffman block.
502 func (w *huffmanBitWriter) writeStoredHeader(length int, isEof bool) {
503 if w.err != nil {
504 return
505 }
506 if w.lastHeader > 0 {
507 // We owe an EOB
508 w.writeCode(w.literalEncoding.codes[endBlockMarker])
509 w.lastHeader = 0
510 }
511
512 // To write EOF, use a fixed encoding block. 10 bits instead of 5 bytes.
513 if length == 0 && isEof {
514 w.writeFixedHeader(isEof)
515 // EOB: 7 bits, value: 0
516 w.writeBits(0, 7)
517 w.flush()
518 return
519 }
520
521 var flag int32
522 if isEof {
523 flag = 1
524 }
525 w.writeBits(flag, 3)
526 w.flush()
527 w.writeBits(int32(length), 16)
528 w.writeBits(int32(^uint16(length)), 16)
529 }
530
531 func (w *huffmanBitWriter) writeFixedHeader(isEof bool) {
532 if w.err != nil {
533 return
534 }
535 if w.lastHeader > 0 {
536 // We owe an EOB
537 w.writeCode(w.literalEncoding.codes[endBlockMarker])
538 w.lastHeader = 0
539 }
540
541 // Indicate that we are a fixed Huffman block
542 var value int32 = 2
543 if isEof {
544 value = 3
545 }
546 w.writeBits(value, 3)
547 }
548
549 // writeBlock will write a block of tokens with the smallest encoding.
550 // The original input can be supplied, and if the huffman encoded data
551 // is larger than the original bytes, the data will be written as a
552 // stored block.
553 // If the input is nil, the tokens will always be Huffman encoded.
554 func (w *huffmanBitWriter) writeBlock(tokens *tokens, eof bool, input []byte) {
555 if w.err != nil {
556 return
557 }
558
559 tokens.AddEOB()
560 if w.lastHeader > 0 {
561 // We owe an EOB
562 w.writeCode(w.literalEncoding.codes[endBlockMarker])
563 w.lastHeader = 0
564 }
565 numLiterals, numOffsets := w.indexTokens(tokens, false)
566 w.generate()
567 var extraBits int
568 storedSize, storable := w.storedSize(input)
569 if storable {
570 extraBits = w.extraBitSize()
571 }
572
573 // Figure out smallest code.
574 // Fixed Huffman baseline.
575 var literalEncoding = fixedLiteralEncoding
576 var offsetEncoding = fixedOffsetEncoding
577 var size = math.MaxInt32
578 if tokens.n < maxPredefinedTokens {
579 size = w.fixedSize(extraBits)
580 }
581
582 // Dynamic Huffman?
583 var numCodegens int
584
585 // Generate codegen and codegenFrequencies, which indicates how to encode
586 // the literalEncoding and the offsetEncoding.
587 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
588 w.codegenEncoding.generate(w.codegenFreq[:], 7)
589 dynamicSize, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
590
591 if dynamicSize < size {
592 size = dynamicSize
593 literalEncoding = w.literalEncoding
594 offsetEncoding = w.offsetEncoding
595 }
596
597 // Stored bytes?
598 if storable && storedSize <= size {
599 w.writeStoredHeader(len(input), eof)
600 w.writeBytes(input)
601 return
602 }
603
604 // Huffman.
605 if literalEncoding == fixedLiteralEncoding {
606 w.writeFixedHeader(eof)
607 } else {
608 w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
609 }
610
611 // Write the tokens.
612 w.writeTokens(tokens.Slice(), literalEncoding.codes, offsetEncoding.codes)
613 }
614
615 // writeBlockDynamic encodes a block using a dynamic Huffman table.
616 // This should be used if the symbols used have a disproportionate
617 // histogram distribution.
618 // If input is supplied and the compression savings are below 1/16th of the
619 // input size the block is stored.
620 func (w *huffmanBitWriter) writeBlockDynamic(tokens *tokens, eof bool, input []byte, sync bool) {
nl -ba flate/huffman_bit_writer.go | sed -n '850,980p'
Chunk ID: f4bda7
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 974
Output:
850 c := lits[t]
851 bits |= c.code64() << (nbits & 63)
852 nbits += c.len()
853 if nbits >= 48 {
854 le.Store64(w.bytes[:], nbytes, bits)
855 bits >>= 48
856 nbits -= 48
857 nbytes += 6
858 if nbytes >= bufferFlushSize {
859 if w.err != nil {
860 nbytes = 0
861 return
862 }
863 _, w.err = w.writer.Write(w.bytes[:nbytes])
864 nbytes = 0
865 }
866 }
867 continue
868 }
869
870 // Write the length
871 length := t.length()
872 lengthCode := lengthCode(length) & 31
873 if false {
874 w.writeCode(lengths[lengthCode])
875 } else {
876 // inlined
877 c := lengths[lengthCode]
878 bits |= c.code64() << (nbits & 63)
879 nbits += c.len()
880 if nbits >= 48 {
881 le.Store64(w.bytes[:], nbytes, bits)
882 bits >>= 48
883 nbits -= 48
884 nbytes += 6
885 if nbytes >= bufferFlushSize {
886 if w.err != nil {
887 nbytes = 0
888 return
889 }
890 _, w.err = w.writer.Write(w.bytes[:nbytes])
891 nbytes = 0
892 }
893 }
894 }
895
896 if lengthCode >= lengthExtraBitsMinCode {
897 extraLengthBits := lengthExtraBits[lengthCode]
898 //w.writeBits(extraLength, extraLengthBits)
899 extraLength := int32(length - lengthBase[lengthCode])
900 bits |= uint64(extraLength) << (nbits & 63)
901 nbits += extraLengthBits
902 if nbits >= 48 {
903 le.Store64(w.bytes[:], nbytes, bits)
904 bits >>= 48
905 nbits -= 48
906 nbytes += 6
907 if nbytes >= bufferFlushSize {
908 if w.err != nil {
909 nbytes = 0
910 return
911 }
912 _, w.err = w.writer.Write(w.bytes[:nbytes])
913 nbytes = 0
914 }
915 }
916 }
917 // Write the offset
918 offset := t.offset()
919 offsetCode := (offset >> 16) & 31
920 if false {
921 w.writeCode(offs[offsetCode])
922 } else {
923 // inlined
924 c := offs[offsetCode]
925 bits |= c.code64() << (nbits & 63)
926 nbits += c.len()
927 if nbits >= 48 {
928 le.Store64(w.bytes[:], nbytes, bits)
929 bits >>= 48
930 nbits -= 48
931 nbytes += 6
932 if nbytes >= bufferFlushSize {
933 if w.err != nil {
934 nbytes = 0
935 return
936 }
937 _, w.err = w.writer.Write(w.bytes[:nbytes])
938 nbytes = 0
939 }
940 }
941 }
942
943 if offsetCode >= offsetExtraBitsMinCode {
944 offsetComb := offsetCombined[offsetCode]
945 //w.writeBits(extraOffset, extraOffsetBits)
946 bits |= uint64((offset-(offsetComb>>8))&matchOffsetOnlyMask) << (nbits & 63)
947 nbits += uint8(offsetComb)
948 if nbits >= 48 {
949 le.Store64(w.bytes[:], nbytes, bits)
950 bits >>= 48
951 nbits -= 48
952 nbytes += 6
953 if nbytes >= bufferFlushSize {
954 if w.err != nil {
955 nbytes = 0
956 return
957 }
958 _, w.err = w.writer.Write(w.bytes[:nbytes])
959 nbytes = 0
960 }
961 }
962 }
963 }
964 // Restore...
965 w.bits, w.nbits, w.nbytes = bits, nbits, nbytes
966
967 if deferEOB {
968 w.writeCode(leCodes[endBlockMarker])
969 }
970 }
971
972 // huffOffset is a static offset encoder used for huffman only encoding.
973 // It can be reused since we will not be encoding offset values.
974 var huffOffset *huffmanEncoder
975
976 func init() {
977 w := newHuffmanBitWriter(nil)
978 w.offsetFreq[0] = 1
979 huffOffset = newHuffmanEncoder(offsetCodeCount)
980 huffOffset.generate(w.offsetFreq[:offsetCodeCount], 15)
rg -n "type Writer|func \(.*\) Write|Close\(|Flush\(|d.step|fillDeflate|windowEnd" flate/deflate.go
Chunk ID: 649706
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 599
Output:
94: // input window: unprocessed data is window[index:windowEnd]
118: windowEnd int
131:func (d *compressor) fillDeflate(b []byte) int {
138: d.windowEnd -= windowSize
167: n := copy(d.window[d.windowEnd:], b)
168: d.windowEnd += n
234: n := copy(d.window[d.windowEnd:], b)
262: d.windowEnd += n
415: if d.windowEnd-s.index < minMatchLength+maxMatchLength && !d.sync {
418: if d.windowEnd != s.index && d.chain > 100 {
424: for _, v := range d.window[s.index:d.windowEnd] {
430: s.maxInsertIndex = d.windowEnd - (minMatchLength - 1)
433: if sanity && s.index > d.windowEnd {
434: panic("index > windowEnd")
436: lookahead := d.windowEnd - s.index
441: if sanity && s.index > d.windowEnd {
442: panic("index > windowEnd")
642: if s.index >= d.windowEnd-1 {
682: if d.windowEnd > 0 && (d.windowEnd == maxStoreBlockSize || d.sync) {
683: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
684: d.windowEnd = 0
691: n := copy(d.window[d.windowEnd:], b)
692: d.windowEnd += n
700: if d.windowEnd < len(d.window) && !d.sync || d.windowEnd == 0 {
703: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
705: d.windowEnd = 0
713: if d.windowEnd < len(d.window) {
718: if d.windowEnd < 128 {
719: if d.windowEnd == 0 {
722: if d.windowEnd <= 32 {
723: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
725: d.w.writeBlockHuff(false, d.window[:d.windowEnd], true)
729: d.windowEnd = 0
735: d.fast.Encode(&d.tokens, d.window[:d.windowEnd])
738: d.err = d.writeStoredBlock(d.window[:d.windowEnd])
740: } else if int(d.tokens.n) > d.windowEnd-(d.windowEnd>>4) {
741: d.w.writeBlockHuff(false, d.window[:d.windowEnd], d.sync)
744: d.w.writeBlockDynamic(&d.tokens, false, d.window[:d.windowEnd], d.sync)
748: d.windowEnd = 0
759: if d.windowEnd == len(d.window) || d.sync {
760: d.step(d)
770:func (d *compressor) syncFlush() error {
775: d.step(d)
792: d.step = (*compressor).store
797: d.step = (*compressor).storeHuff
806: d.step = (*compressor).storeFast
812: d.fill = (*compressor).fillDeflate
813: d.step = (*compressor).deflateLazy
819: d.step = (*compressor).storeFast
835: d.windowEnd = 0
842: d.windowEnd = 0
853: s.index, d.windowEnd = 0, 0
868: d.step(d)
940:type Writer struct {
947:func (w *Writer) Write(data []byte) (n int, err error) {
960:func (w *Writer) Flush() error {
963: return w.d.syncFlush()
967:func (w *Writer) Close() error {
nl -ba flate/deflate.go | sed -n '748,880p'
Chunk ID: 09b702
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 986
Output:
748 d.windowEnd = 0
749 }
750
751 // write will add input byte to the stream.
752 // Unless an error occurs all bytes will be consumed.
753 func (d *compressor) write(b []byte) (n int, err error) {
754 if d.err != nil {
755 return 0, d.err
756 }
757 n = len(b)
758 for len(b) > 0 {
759 if d.windowEnd == len(d.window) || d.sync {
760 d.step(d)
761 }
762 b = b[d.fill(d, b):]
763 if d.err != nil {
764 return 0, d.err
765 }
766 }
767 return n, d.err
768 }
769
770 func (d *compressor) syncFlush() error {
771 d.sync = true
772 if d.err != nil {
773 return d.err
774 }
775 d.step(d)
776 if d.err == nil {
777 d.w.writeStoredHeader(0, false)
778 d.w.flush()
779 d.err = d.w.err
780 }
781 d.sync = false
782 return d.err
783 }
784
785 func (d *compressor) init(w io.Writer, level int) (err error) {
786 d.w = newHuffmanBitWriter(w)
787
788 switch {
789 case level == NoCompression:
790 d.window = make([]byte, maxStoreBlockSize)
791 d.fill = (*compressor).fillBlock
792 d.step = (*compressor).store
793 case level == ConstantCompression:
794 d.w.logNewTablePenalty = 10
795 d.window = make([]byte, 32<<10)
796 d.fill = (*compressor).fillBlock
797 d.step = (*compressor).storeHuff
798 case level == DefaultCompression:
799 level = 5
800 fallthrough
801 case level >= 1 && level <= 6:
802 d.w.logNewTablePenalty = 7
803 d.fast = newFastEnc(level)
804 d.window = make([]byte, maxStoreBlockSize)
805 d.fill = (*compressor).fillBlock
806 d.step = (*compressor).storeFast
807 case 7 <= level && level <= 9:
808 d.w.logNewTablePenalty = 8
809 d.state = &advancedState{}
810 d.compressionLevel = levels[level]
811 d.initDeflate()
812 d.fill = (*compressor).fillDeflate
813 d.step = (*compressor).deflateLazy
814 case -level >= MinCustomWindowSize && -level <= MaxCustomWindowSize:
815 d.w.logNewTablePenalty = 7
816 d.fast = &fastEncL5Window{maxOffset: int32(-level), cur: maxStoreBlockSize}
817 d.window = make([]byte, maxStoreBlockSize)
818 d.fill = (*compressor).fillBlock
819 d.step = (*compressor).storeFast
820 default:
821 return fmt.Errorf("flate: invalid compression level %d: want value in range [-2, 9]", level)
822 }
823 d.level = level
824 return nil
825 }
826
827 // reset the state of the compressor.
828 func (d *compressor) reset(w io.Writer) {
829 d.w.reset(w)
830 d.sync = false
831 d.err = nil
832 // We only need to reset a few things for Snappy.
833 if d.fast != nil {
834 d.fast.Reset()
835 d.windowEnd = 0
836 d.tokens.Reset()
837 return
838 }
839 switch d.compressionLevel.chain {
840 case 0:
841 // level was NoCompression or ConstantCompression.
842 d.windowEnd = 0
843 default:
844 s := d.state
845 s.chainHead = -1
846 for i := range s.hashHead {
847 s.hashHead[i] = 0
848 }
849 for i := range s.hashPrev {
850 s.hashPrev[i] = 0
851 }
852 s.hashOffset = 1
853 s.index, d.windowEnd = 0, 0
854 d.blockStart, d.byteAvailable = 0, false
855 d.tokens.Reset()
856 s.length = minMatchLength - 1
857 s.offset = 0
858 s.ii = 0
859 s.maxInsertIndex = 0
860 }
861 }
862
863 func (d *compressor) close() error {
864 if d.err != nil {
865 return d.err
866 }
867 d.sync = true
868 d.step(d)
869 if d.err != nil {
870 return d.err
871 }
872 if d.w.writeStoredHeader(0, true); d.w.err != nil {
873 return d.w.err
874 }
875 d.w.flush()
876 d.w.reset(nil)
877 return d.w.err
878 }
879
880 // NewWriter returns a new Writer compressing data at the given level.
nl -ba flate/deflate.go | sed -n '920,990p'
Chunk ID: 35498a
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 720
Output:
920 const MaxCustomWindowSize = windowSize
921
922 // NewWriterWindow returns a new Writer compressing data with a custom window size.
923 // windowSize must be from MinCustomWindowSize to MaxCustomWindowSize.
924 func NewWriterWindow(w io.Writer, windowSize int) (*Writer, error) {
925 if windowSize < MinCustomWindowSize {
926 return nil, errors.New("flate: requested window size less than MinWindowSize")
927 }
928 if windowSize > MaxCustomWindowSize {
929 return nil, errors.New("flate: requested window size bigger than MaxCustomWindowSize")
930 }
931 var dw Writer
932 if err := dw.d.init(w, -windowSize); err != nil {
933 return nil, err
934 }
935 return &dw, nil
936 }
937
938 // A Writer takes data written to it and writes the compressed
939 // form of that data to an underlying writer (see NewWriter).
940 type Writer struct {
941 d compressor
942 dict []byte
943 }
944
945 // Write writes data to w, which will eventually write the
946 // compressed form of data to its underlying writer.
947 func (w *Writer) Write(data []byte) (n int, err error) {
948 return w.d.write(data)
949 }
950
951 // Flush flushes any pending data to the underlying writer.
952 // It is useful mainly in compressed network protocols, to ensure that
953 // a remote reader has enough data to reconstruct a packet.
954 // Flush does not return until the data has been written.
955 // Calling Flush when there is no pending data still causes the Writer
956 // to emit a sync marker of at least 4 bytes.
957 // If the underlying writer returns an error, Flush returns that error.
958 //
959 // In the terminology of the zlib library, Flush is equivalent to Z_SYNC_FLUSH.
960 func (w *Writer) Flush() error {
961 // For more about flushing:
962 // http://www.bolet.org/~pornin/deflate-flush.html
963 return w.d.syncFlush()
964 }
965
966 // Close flushes and closes the writer.
967 func (w *Writer) Close() error {
968 return w.d.close()
969 }
970
971 // Reset discards the writer's state and makes it equivalent to
972 // the result of NewWriter or NewWriterDict called with dst
973 // and w's level and dictionary.
974 func (w *Writer) Reset(dst io.Writer) {
975 if len(w.dict) > 0 {
976 // w was created with NewWriterDict
977 w.d.reset(dst)
978 if dst != nil {
979 w.d.fillWindow(w.dict)
980 }
981 } else {
982 // w was created with NewWriter
983 w.d.reset(dst)
984 }
985 }
986
987 // ResetDict discards the writer's state and makes it equivalent to
988 // the result of NewWriter or NewWriterDict called with dst
989 // and w's level, but sets a specific dictionary.
990 func (w *Writer) ResetDict(dst io.Writer, dict []byte) {
rg -n "func \(.*\) writeBytes|func \(.*\) writeBits" flate/huffman_bit_writer.go && nl -ba flate/huffman_bit_writer.go | sed -n '220,340p'
Chunk ID: 512e94
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1028
Output:
227:func (w *huffmanBitWriter) writeBits(b int32, nb uint8) {
235:func (w *huffmanBitWriter) writeBytes(bytes []byte) {
220 func (w *huffmanBitWriter) write(b []byte) {
221 if w.err != nil {
222 return
223 }
224 _, w.err = w.writer.Write(b)
225 }
226
227 func (w *huffmanBitWriter) writeBits(b int32, nb uint8) {
228 w.bits |= uint64(b) << (w.nbits & 63)
229 w.nbits += nb
230 if w.nbits >= 48 {
231 w.writeOutBits()
232 }
233 }
234
235 func (w *huffmanBitWriter) writeBytes(bytes []byte) {
236 if w.err != nil {
237 return
238 }
239 n := w.nbytes
240 if w.nbits&7 != 0 {
241 w.err = InternalError("writeBytes with unfinished bits")
242 return
243 }
244 for w.nbits != 0 {
245 w.bytes[n] = byte(w.bits)
246 w.bits >>= 8
247 w.nbits -= 8
248 n++
249 }
250 if n != 0 {
251 w.write(w.bytes[:n])
252 }
253 w.nbytes = 0
254 w.write(bytes)
255 }
256
257 // RFC 1951 3.2.7 specifies a special run-length encoding for specifying
258 // the literal and offset lengths arrays (which are concatenated into a single
259 // array). This method generates that run-length encoding.
260 //
261 // The result is written into the codegen array, and the frequencies
262 // of each code is written into the codegenFreq array.
263 // Codes 0-15 are single byte codes. Codes 16-18 are followed by additional
264 // information. Code badCode is an end marker
265 //
266 // numLiterals The number of literals in literalEncoding
267 // numOffsets The number of offsets in offsetEncoding
268 // litenc, offenc The literal and offset encoder to use
269 func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int, litEnc, offEnc *huffmanEncoder) {
270 for i := range w.codegenFreq {
271 w.codegenFreq[i] = 0
272 }
273 // Note that we are using codegen both as a temporary variable for holding
274 // a copy of the frequencies, and as the place where we put the result.
275 // This is fine because the output is always shorter than the input used
276 // so far.
277 codegen := w.codegen[:] // cache
278 // Copy the concatenated code sizes to codegen. Put a marker at the end.
279 cgnl := codegen[:numLiterals]
280 for i := range cgnl {
281 cgnl[i] = litEnc.codes[i].len()
282 }
283
284 cgnl = codegen[numLiterals : numLiterals+numOffsets]
285 for i := range cgnl {
286 cgnl[i] = offEnc.codes[i].len()
287 }
288 codegen[numLiterals+numOffsets] = badCode
289
290 size := codegen[0]
291 count := 1
292 outIndex := 0
293 for inIndex := 1; size != badCode; inIndex++ {
294 // INVARIANT: We have seen "count" copies of size that have not yet
295 // had output generated for them.
296 nextSize := codegen[inIndex]
297 if nextSize == size {
298 count++
299 continue
300 }
301 // We need to generate codegen indicating "count" of size.
302 if size != 0 {
303 codegen[outIndex] = size
304 outIndex++
305 w.codegenFreq[size]++
306 count--
307 for count >= 3 {
308 n := min(6, count)
309 codegen[outIndex] = 16
310 outIndex++
311 codegen[outIndex] = uint8(n - 3)
312 outIndex++
313 w.codegenFreq[16]++
314 count -= n
315 }
316 } else {
317 for count >= 11 {
318 n := min(138, count)
319 codegen[outIndex] = 18
320 outIndex++
321 codegen[outIndex] = uint8(n - 11)
322 outIndex++
323 w.codegenFreq[18]++
324 count -= n
325 }
326 if count >= 3 {
327 // count >= 3 && count <= 10
328 codegen[outIndex] = 17
329 outIndex++
330 codegen[outIndex] = uint8(count - 3)
331 outIndex++
332 w.codegenFreq[17]++
333 count = 0
334 }
335 }
336 count--
337 for ; count >= 0; count-- {
338 codegen[outIndex] = size
339 outIndex++
340 w.codegenFreq[size]++
go list -m
Chunk ID: 5caec4 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 8 Output: [code-host]/klauspost/compress
go test ./flate -run 'TestWriteBlock|TestBlockHuff|TestDeterministicL[789]|TestLargeLowEntropyRoundTripVisible' -count=1 -v
Chunk ID: 1bd0db
Wall time: 1.0029 seconds
Process running with session ID 19745
Original token count: 3679
Output:
=== RUN TestBlockHuff
=== RUN TestBlockHuff/testdata/huffman-null-max.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-null-max.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-pi.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-pi.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-rand-1k.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-rand-1k.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-rand-limit.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-rand-limit.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-rand-max.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-rand-max.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-shifts.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-shifts.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-text-shift.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-text-shift.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-text.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-text.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
=== RUN TestBlockHuff/testdata/huffman-zero.in
huffman_bit_writer_test.go:60: Testing "testdata/huffman-zero.in"
huffman_bit_writer_test.go:80: Output ok
huffman_bit_writer_test.go:95: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestBlockHuff (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-null-max.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-pi.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-rand-1k.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-rand-limit.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-rand-max.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-shifts.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-text-shift.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-text.in (0.00s)
--- PASS: TestBlockHuff/testdata/huffman-zero.in (0.00s)
=== RUN TestWriteBlock
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.wb.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.wb.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestWriteBlock (0.01s)
=== RUN TestWriteBlockDynamic
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.dyn.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.dyn.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestWriteBlockDynamic (0.01s)
=== RUN TestWriteBlockDynamicSync
huffman_bit_writer_test.go:230: Testing "testdata/huffman-null-max.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-null-max.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-pi.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-pi.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-1k.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-1k.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-rand-limit.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-rand-limit.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-shifts.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-shifts.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text-shift.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text-shift.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-text.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-text.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:230: Testing "testdata/huffman-zero.sync.expect"
huffman_bit_writer_test.go:252: Output ok
huffman_bit_writer_test.go:267: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/huffman-zero.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
huffman_bit_writer_test.go:270: Testing "testdata/null-long-match.sync.expect-noinput"
huffman_bit_writer_test.go:291: Output ok
huffman_bit_writer_test.go:306: Reset ok
huffman_bit_writer_test.go:380: EOF ok
--- PASS: TestWriteBlockDynamicSync (0.01s)
=== RUN TestLargeLowEntropyRoundTripVisible
large_low_entropy_test.go:29: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.54s)
=== RUN TestDeterministicL7
--- PASS: TestDeterministicL7 (0.13s)
=== RUN TestDeterministicL8
--- PASS: TestDeterministicL8 (0.13s)
=== RUN TestDeterministicL9
rg -n "InternalError|type InternalError|CorruptInputError|invalid distance" -S
Chunk ID: b875f9
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 872
Output:
flate/huffman_bit_writer.go:241: w.err = InternalError("writeBytes with unfinished bits")
flate/inflate_test.go:120: {"4 80 49 92 24 49 92 24 f b4 ff ff c3 84", "invalid distances set", 1},
flate/inflate_test.go:122: {"2 7e ff ff", "invalid distance code", 1},
flate/inflate_test.go:123: {"c c0 81 0 0 0 0 0 90 ff 6b 4 0", "invalid distance too far back", 1},
flate/inflate_test.go:214: {"3 7e 0 0 0 0 0", "fast invalid distance code", 0, -8, 258, true},
flate/_gen/gen_inflate.go:95: f.err = CorruptInputError(f.roffset)
flate/_gen/gen_inflate.go:150: f.err = CorruptInputError(f.roffset)
flate/_gen/gen_inflate.go:207: f.err = CorruptInputError(f.roffset)
flate/_gen/gen_inflate.go:249: f.err = CorruptInputError(f.roffset)
flate/_gen/gen_inflate.go:259: f.err = CorruptInputError(f.roffset)
flate/inflate.go:50:// A CorruptInputError reports the presence of corrupt input at a given offset.
flate/inflate.go:51:type CorruptInputError = flate.CorruptInputError
flate/inflate.go:53:// An InternalError reports an error in the flate code itself.
flate/inflate.go:54:type InternalError string
flate/inflate.go:56:func (e InternalError) Error() string { return "flate: internal error: " + string(e) }
flate/inflate.go:388: f.err = CorruptInputError(f.roffset)
flate/inflate.go:471: return CorruptInputError(f.roffset)
flate/inflate.go:479: return CorruptInputError(f.roffset)
flate/inflate.go:505: return CorruptInputError(f.roffset)
flate/inflate.go:527: return InternalError("unexpected length code")
flate/inflate.go:535: return CorruptInputError(f.roffset)
flate/inflate.go:562: return CorruptInputError(f.roffset)
flate/inflate.go:574: return CorruptInputError(f.roffset)
flate/inflate.go:626: f.err = CorruptInputError(f.roffset)
flate/inflate.go:758: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:71: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:126: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:183: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:225: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:235: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:322: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:377: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:434: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:476: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:486: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:573: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:628: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:685: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:727: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:737: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:824: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:879: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:936: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:978: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:988: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:1075: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:1130: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:1187: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:1229: f.err = CorruptInputError(f.roffset)
flate/inflate_gen.go:1239: f.err = CorruptInputError(f.roffset)
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
- extraBits := 0
+ extraBits := w.extraBitSize()
ssize, storable := w.storedSize(input)
@@
- if storable || w.lastHeader > 0 {
- extraBits = w.extraBitSize()
- }
-
var size int
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
gofmt -w flate/huffman_bit_writer.go && go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 0941e1
Wall time: 0.7394 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.55s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.554s
FAIL
{
"session_id": 19745,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 10000
}
, output,
Chunk ID: 2966c8
Wall time: 0.0000 seconds
Process exited with code 1
Original token count: 24
Output:
--- PASS: TestDeterministicL9 (0.34s)
FAIL
FAIL [code-host]/klauspost/compress/flate 1.161s
FAIL
*** Begin Patch
*** Update File: /app/flate/large_low_entropy_test.go
@@
if err := w.Close(); err != nil {
t.Fatalf("Close: %v", err)
}
+ t.Logf("compressed len=%d first=%x", compressed.Len(), compressed.Bytes()[:min(compressed.Len(), 64)])
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/large_low_entropy_test.go
gofmt -w flate/large_low_entropy_test.go && go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 7ed88f
Wall time: 0.7129 seconds
Process exited with code 1
Original token count: 113
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
large_low_entropy_test.go:24: compressed len=9184 first=04f8ffffffffffff1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
large_low_entropy_test.go:30: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.53s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.533s
FAIL
rg -n "func \(d \*compressor\) findMatch|d\.h|good|nice|chain" flate/deflate.go
Chunk ID: 2662fd
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 503
Output:
61: good, lazy, nice, chain, fastSkipHashing, level int
77: // and increasingly stringent conditions for "good enough".
89: chainHead int
98: // Input hash chains
148: s.chainHead -= delta
255: // Our chain should point to the previous value.
257: // Set the head of the hash chain to us.
267:// We only look at chainCount possibilities before giving up.
268:// pos = s.index, prevHead = s.chainHead-s.hashOffset, prevLength=minMatchLength-1, lookahead
269:func (d *compressor) findMatch(pos int, prevHead int, lookahead int) (length, offset int, ok bool) {
274: // We quit when we get a match that's at least nice long
275: nice := min(d.nice, len(win)-pos)
277: // If we've got a match that's good enough, only look in 1/4 the chain.
278: tries := d.chain
286: if d.chain < 100 {
294: if n >= nice {
295: // The match is good enough that we don't try to find a better one.
326: newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
328: //fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
334: if n >= nice {
335: // The match is good enough that we don't try to find a better one.
403: s.chainHead = -1
418: if d.windowEnd != s.index && d.chain > 100 {
420: if d.h == nil {
421: d.h = newHuffmanEncoder(maxFlateBlockTokens)
427: d.h.generate(tmp[:], 15)
464: s.chainHead = int(ch)
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 {
522: s.chainHead = int(ch)
563: s.chainHead = int(ch)
602: // Our chain should point to the previous value.
604: // Set the head of the hash chain to us.
639: if n := int(s.ii) - d.chain; n > 0 {
656: s.chainHead = int(ch)
839: switch d.compressionLevel.chain {
845: s.chainHead = -1
nl -ba flate/deflate.go | sed -n '250,407p'
Chunk ID: 0048a0
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1314
Output:
250 var newH uint32
251 for i, val := range dst {
252 di := i + startindex
253 newH = val & hashMask
254 // Get previous value with the same hash.
255 // Our chain should point to the previous value.
256 s.hashPrev[di&windowMask] = s.hashHead[newH]
257 // Set the head of the hash chain to us.
258 s.hashHead[newH] = uint32(di + s.hashOffset)
259 }
260 }
261 // Update window information.
262 d.windowEnd += n
263 s.index = n
264 }
265
266 // Try to find a match starting at index whose length is greater than prevSize.
267 // We only look at chainCount possibilities before giving up.
268 // pos = s.index, prevHead = s.chainHead-s.hashOffset, prevLength=minMatchLength-1, lookahead
269 func (d *compressor) findMatch(pos int, prevHead int, lookahead int) (length, offset int, ok bool) {
270 minMatchLook := min(lookahead, maxMatchLength)
271
272 win := d.window[0 : pos+minMatchLook]
273
274 // We quit when we get a match that's at least nice long
275 nice := min(d.nice, len(win)-pos)
276
277 // If we've got a match that's good enough, only look in 1/4 the chain.
278 tries := d.chain
279 length = minMatchLength - 1
280
281 wEnd := win[pos+length]
282 wPos := win[pos:]
283 minIndex := max(pos-windowSize, 0)
284 offset = 0
285
286 if d.chain < 100 {
287 for i := prevHead; tries > 0; tries-- {
288 if wEnd == win[i+length] {
289 n := matchLen(win[i:i+minMatchLook], wPos)
290 if n > length {
291 length = n
292 offset = pos - i
293 ok = true
294 if n >= nice {
295 // The match is good enough that we don't try to find a better one.
296 break
297 }
298 wEnd = win[pos+n]
299 }
300 }
301 if i <= minIndex {
302 // hashPrev[i & windowMask] has already been overwritten, so stop now.
303 break
304 }
305 i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
306 if i < minIndex {
307 break
308 }
309 }
310 return
311 }
312
313 // Minimum gain to accept a match.
314 cGain := 4
315
316 // Some like it higher (CSV), some like it lower (JSON)
317 const baseCost = 3
318 // Base is 4 bytes at with an additional cost.
319 // Matches must be better than this.
320
321 for i := prevHead; tries > 0; tries-- {
322 if wEnd == win[i+length] {
323 n := matchLen(win[i:i+minMatchLook], wPos)
324 if n > length {
325 // Calculate gain. Estimate
326 newGain := d.h.bitLengthRaw(wPos[:n]) - int(offsetExtraBits[offsetCode(uint32(pos-i))]) - baseCost - int(lengthExtraBits[lengthCodes[(n-3)&255]])
327
328 //fmt.Println("gain:", newGain, "prev:", cGain, "raw:", d.h.bitLengthRaw(wPos[:n]), "this-len:", n, "prev-len:", length)
329 if newGain > cGain {
330 length = n
331 offset = pos - i
332 cGain = newGain
333 ok = true
334 if n >= nice {
335 // The match is good enough that we don't try to find a better one.
336 break
337 }
338 wEnd = win[pos+n]
339 }
340 }
341 }
342 if i <= minIndex {
343 // hashPrev[i & windowMask] has already been overwritten, so stop now.
344 break
345 }
346 i = int(d.state.hashPrev[i&windowMask]) - d.state.hashOffset
347 if i < minIndex {
348 break
349 }
350 }
351 return
352 }
353
354 func (d *compressor) writeStoredBlock(buf []byte) error {
355 if d.w.writeStoredHeader(len(buf), false); d.w.err != nil {
356 return d.w.err
357 }
358 d.w.writeBytes(buf)
359 return d.w.err
360 }
361
362 // hash4 returns a hash representation of the first 4 bytes
363 // of the supplied slice.
364 // The caller must ensure that len(b) >= 4.
365 func hash4(b []byte) uint32 {
366 return hash4u(le.Load32(b, 0), hashBits)
367 }
368
369 // hash4 returns the hash of u to fit in a hash table with h bits.
370 // Preferably h should be a constant and should always be <32.
371 func hash4u(u uint32, h uint8) uint32 {
372 return (u * prime4bytes) >> (32 - h)
373 }
374
375 // bulkHash4 will compute hashes using the same
376 // algorithm as hash4
377 func bulkHash4(b []byte, dst []uint32) {
378 if len(b) < 4 {
379 return
380 }
381 hb := le.Load32(b, 0)
382
383 dst[0] = hash4u(hb, hashBits)
384 end := len(b) - 4 + 1
385 for i := 1; i < end; i++ {
386 hb = (hb >> 8) | uint32(b[i+3])<<24
387 dst[i] = hash4u(hb, hashBits)
388 }
389 }
390
391 func (d *compressor) initDeflate() {
392 d.window = make([]byte, 2*windowSize)
393 d.byteAvailable = false
394 d.err = nil
395 if d.state == nil {
396 return
397 }
398 s := d.state
399 s.index = 0
400 s.hashOffset = 1
401 s.length = minMatchLength - 1
402 s.offset = 0
403 s.chainHead = -1
404 }
405
406 // deflateLazy is the same as deflate, but with d.fastSkipHashing == skipNever,
407 // meaning it always has lazy matching on.
rg -n "type hcode|func \(.*hcode|func \(.*\) generate" flate/huffman_code.go flate/huffman_bit_writer.go
Chunk ID: 1f415a
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 196
Output:
flate/huffman_code.go:19:type hcode uint32
flate/huffman_code.go:21:func (h hcode) len() uint8 {
flate/huffman_code.go:25:func (h hcode) code64() uint64 {
flate/huffman_code.go:29:func (h hcode) zero() bool {
flate/huffman_code.go:69:func (h *hcode) set(code uint16, length uint8) {
flate/huffman_code.go:339:func (h *huffmanEncoder) generate(freq []uint16, maxBits int32) {
flate/huffman_bit_writer.go:269:func (w *huffmanBitWriter) generateCodegen(numLiterals int, numOffsets int, litEnc, offEnc *huffmanEncoder) {
flate/huffman_bit_writer.go:421:func (w *huffmanBitWriter) writeCode(c hcode) {
flate/huffman_bit_writer.go:812:func (w *huffmanBitWriter) generate() {
flate/huffman_bit_writer.go:819:func (w *huffmanBitWriter) writeTokens(tokens []token, leCodes, oeCodes []hcode) {
python3 - <<'PY'
data=bytes.fromhex('04f8ffffffffffff100000000000000000000000000000000000000000000000')
bits=[]
for b in data:
for i in range(8): bits.append((b>>i)&1)
pos=0
def take(n):
global pos
v=sum(bits[pos+i]<<i for i in range(n)); pos+=n; return v
print('bfinal', take(1), 'btype', take(2))
print('hlit', take(5)+257, 'hdist', take(5)+1, 'hclen', take(4)+4, 'pos', pos)
order=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15]
for i in range(19):
if i < 19:
pass
PYChunk ID: a10509 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 13 Output: bfinal 0 btype 2 hlit 257 hdist 25 hclen 19 pos 17
python3 - <<'PY'
hexstr='04f8ffffffffffff1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
data=bytes.fromhex(hexstr)
bits=[(b>>i)&1 for b in data for i in range(8)]
pos=0
def take(n):
global pos
v=sum(bits[pos+i]<<i for i in range(n)); pos+=n; return v
print('bfinal', take(1), 'btype', take(2))
hlit=take(5)+257; hdist=take(5)+1; hclen=take(4)+4
print(hlit, hdist, hclen, 'pos', pos)
order=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15]
cl=[0]*19
for i in range(hclen): cl[order[i]]=take(3)
print('cl', cl, 'pos', pos)
PYChunk ID: 3191bc Wall time: 0.0000 seconds Process exited with code 0 Original token count: 26 Output: bfinal 0 btype 2 257 25 19 pos 17 cl [7, 1, 3, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 0, 7, 7, 7] pos 74
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
// Write Huffman table.
+ if numLiterals == endBlockMarker+1 && numOffsets > 1 {
+ fmt.Println("debug dynamic", "tokens", tokens.n, "lit0", tokens.litHist[0], "extra", tokens.extraHist, "off", tokens.offHist, "input", len(input), "sync", sync)
+ }
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
gofmt -w flate/huffman_bit_writer.go && go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: f40bcb
Wall time: 0.7014 seconds
Process exited with code 1
Original token count: 113
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
large_low_entropy_test.go:24: compressed len=9184 first=04f8ffffffffffff1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
large_low_entropy_test.go:30: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.53s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.531s
FAIL
rg -n "writeDynamicHeader" flate/huffman_bit_writer.go
Chunk ID: e7965a
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 82
Output:
458:func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) {
608: w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
752: w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
1079: w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) {
if w.err != nil {
return
}
+ fmt.Println("debug header", numLiterals, numOffsets, numCodegens, isEof)
var firstBits int32 = 4
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
gofmt -w flate/huffman_bit_writer.go && go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: 67cdf0
Wall time: 0.7105 seconds
Process exited with code 1
Original token count: 134
Output:
=== RUN TestLargeLowEntropyRoundTripVisible
debug header 1 1 18 false
debug header 286 1 18 false
debug header 286 1 18 false
large_low_entropy_test.go:24: compressed len=9184 first=04f8ffffffffffff1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
large_low_entropy_test.go:30: standard reader rejected stream: flate: corrupt input before offset 10
--- FAIL: TestLargeLowEntropyRoundTripVisible (0.53s)
FAIL
FAIL [code-host]/klauspost/compress/flate 0.532s
FAIL
nl -ba flate/huffman_bit_writer.go | sed -n '1000,1095p'
Chunk ID: 727ee1
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 863
Output:
1000
1001 const numLiterals = endBlockMarker + 1
1002 const numOffsets = 1
1003
1004 // Add everything as literals
1005 // We have to estimate the header size.
1006 // Assume header is around 70 bytes:
1007 // https://stackoverflow.com/a/25454430
1008 const guessHeaderSizeBits = 70 * 8
1009 histogram(input, w.literalFreq[:numLiterals])
1010 ssize, storable := w.storedSize(input)
1011 if storable && len(input) > 1024 {
1012 // Quick check for incompressible content.
1013 abs := float64(0)
1014 avg := float64(len(input)) / 256
1015 max := float64(len(input) * 2)
1016 for _, v := range w.literalFreq[:256] {
1017 diff := float64(v) - avg
1018 abs += diff * diff
1019 if abs > max {
1020 break
1021 }
1022 }
1023 if abs < max {
1024 if debugDeflate {
1025 fmt.Println("stored", abs, "<", max)
1026 }
1027 // No chance we can compress this...
1028 w.writeStoredHeader(len(input), eof)
1029 w.writeBytes(input)
1030 return
1031 }
1032 }
1033 w.literalFreq[endBlockMarker] = 1
1034 w.tmpLitEncoding.generate(w.literalFreq[:numLiterals], 15)
1035 estBits := w.tmpLitEncoding.canReuseBits(w.literalFreq[:numLiterals])
1036 if estBits < math.MaxInt32 {
1037 estBits += w.lastHeader
1038 if w.lastHeader == 0 {
1039 estBits += guessHeaderSizeBits
1040 }
1041 estBits += estBits >> w.logNewTablePenalty
1042 }
1043
1044 // Store bytes, if we don't get a reasonable improvement.
1045 if storable && ssize <= estBits {
1046 if debugDeflate {
1047 fmt.Println("stored,", ssize, "<=", estBits)
1048 }
1049 w.writeStoredHeader(len(input), eof)
1050 w.writeBytes(input)
1051 return
1052 }
1053
1054 if w.lastHeader > 0 {
1055 reuseSize := w.literalEncoding.canReuseBits(w.literalFreq[:256])
1056
1057 if estBits < reuseSize {
1058 if debugDeflate {
1059 fmt.Println("NOT reusing, reuse:", reuseSize/8, "> new:", estBits/8, "header est:", w.lastHeader/8, "bytes")
1060 }
1061 // We owe an EOB
1062 w.writeCode(w.literalEncoding.codes[endBlockMarker])
1063 w.lastHeader = 0
1064 } else if debugDeflate {
1065 fmt.Println("reusing, reuse:", reuseSize/8, "> new:", estBits/8, "- header est:", w.lastHeader/8)
1066 }
1067 }
1068
1069 count := 0
1070 if w.lastHeader == 0 {
1071 // Use the temp encoding, so swap.
1072 w.literalEncoding, w.tmpLitEncoding = w.tmpLitEncoding, w.literalEncoding
1073 // Generate codegen and codegenFrequencies, which indicates how to encode
1074 // the literalEncoding and the offsetEncoding.
1075 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, huffOffset)
1076 w.codegenEncoding.generate(w.codegenFreq[:], 7)
1077 numCodegens := w.codegens()
1078
1079 // Huffman.
1080 w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
1081 w.lastHuffMan = true
1082 w.lastHeader, _ = w.headerSize()
1083 if debugDeflate {
1084 count += w.lastHeader
1085 fmt.Println("header:", count/8)
1086 }
1087 }
1088
1089 encoding := w.literalEncoding.codes[:256]
1090 // Go 1.16 LOVES having these on stack. At least 1.5x the speed.
1091 bits, nbits, nbytes := w.bits, w.nbits, w.nbytes
1092
1093 if debugDeflate {
1094 count -= int(nbytes)*8 + int(nbits)
1095 }
nl -ba flate/huffman_bit_writer.go | sed -n '690,730p'
Chunk ID: 3f4f51
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 392
Output:
690 w.writeTokens(tokens.Slice(), fixedLiteralEncoding.codes, fixedOffsetEncoding.codes)
691 return
692 }
693 }
694 // Check if we get a reasonable size decrease.
695 if storable && ssize <= size {
696 w.writeStoredHeader(len(input), eof)
697 w.writeBytes(input)
698 return
699 }
700 }
701
702 // We want a new block/table
703 if w.lastHeader == 0 {
704 if fillReuse && !sync {
705 w.fillTokens()
706 numLiterals, numOffsets = maxNumLit, maxNumDist
707 } else {
708 w.literalFreq[endBlockMarker] = 1
709 }
710
711 w.generate()
712 // Generate codegen and codegenFrequencies, which indicates how to encode
713 // the literalEncoding and the offsetEncoding.
714 w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
715 w.codegenEncoding.generate(w.codegenFreq[:], 7)
716
717 var numCodegens int
718 if fillReuse && !sync {
719 // Reindex for accurate size...
720 w.indexTokens(tokens, true)
721 }
722 size, numCodegens = w.dynamicSize(w.literalEncoding, w.offsetEncoding, extraBits)
723
724 // Store predefined, if we don't get a reasonable improvement.
725 if tokens.n < maxPredefinedTokens {
726 if preSize := w.fixedSize(extraBits); usePrefs && preSize <= size {
727 // Store bytes, if we don't get an improvement.
728 if storable && ssize <= preSize {
729 w.writeStoredHeader(len(input), eof)
730 w.writeBytes(input)
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
func (w *huffmanBitWriter) writeDynamicHeader(numLiterals int, numOffsets int, numCodegens int, isEof bool) {
if w.err != nil {
return
}
- fmt.Println("debug header", numLiterals, numOffsets, numCodegens, isEof)
var firstBits int32 = 4
@@
- extraBits := w.extraBitSize()
+ extraBits := 0
ssize, storable := w.storedSize(input)
@@
const usePrefs = true
+ if storable || w.lastHeader > 0 {
+ extraBits = w.extraBitSize()
+ }
+
var size int
@@
} else {
w.literalFreq[endBlockMarker] = 1
+ if numLiterals < endBlockMarker+1 {
+ numLiterals = endBlockMarker + 1
+ }
}
@@
- if numLiterals == endBlockMarker+1 && numOffsets > 1 {
- fmt.Println("debug dynamic", "tokens", tokens.n, "lit0", tokens.litHist[0], "extra", tokens.extraHist, "off", tokens.offHist, "input", len(input), "sync", sync)
- }
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
*** Begin Patch
*** Update File: /app/flate/large_low_entropy_test.go
@@
if err := w.Close(); err != nil {
t.Fatalf("Close: %v", err)
}
- t.Logf("compressed len=%d first=%x", compressed.Len(), compressed.Bytes()[:min(compressed.Len(), 64)])
stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/large_low_entropy_test.go
gofmt -w flate/huffman_bit_writer.go flate/large_low_entropy_test.go && go test ./flate -run TestLargeLowEntropyRoundTripVisible -count=1 -v
Chunk ID: de7ae1 Wall time: 0.9820 seconds Process exited with code 0 Original token count: 39 Output: === RUN TestLargeLowEntropyRoundTripVisible --- PASS: TestLargeLowEntropyRoundTripVisible (0.59s) PASS ok [code-host]/klauspost/compress/flate 0.594s
go test ./flate -run 'TestWriteBlock|TestBlockHuff|TestDeterministicL[0-9]|TestDeterministicLM2' -count=1
Chunk ID: 5ecd1a Wall time: 1.0016 seconds Process running with session ID 93521 Original token count: 0 Output:
*** Begin Patch
*** Update File: /app/flate/large_low_entropy_test.go
@@
import (
"bytes"
stdflate "compress/flate"
+ "fmt"
"io"
+ "math/rand"
"testing"
)
-func TestLargeLowEntropyRoundTripVisible(t *testing.T) {
- input := make([]byte, 1<<20)
-
+func testRoundTripWithReaders(t *testing.T, input []byte, level int, chunked bool) {
+ t.Helper()
var compressed bytes.Buffer
- w, err := NewWriter(&compressed, BestCompression)
+ w, err := NewWriter(&compressed, level)
if err != nil {
t.Fatalf("NewWriter: %v", err)
}
- if _, err := w.Write(input); err != nil {
- t.Fatalf("Write: %v", err)
+ if chunked {
+ for off := 0; off < len(input); {
+ n := 787
+ if off+n > len(input) {
+ n = len(input) - off
+ }
+ if _, err := w.Write(input[off : off+n]); err != nil {
+ t.Fatalf("Write: %v", err)
+ }
+ off += n
+ }
+ } else {
+ if _, err := w.Write(input); err != nil {
+ t.Fatalf("Write: %v", err)
+ }
}
if err := w.Close(); err != nil {
t.Fatalf("Close: %v", err)
}
@@
if !bytes.Equal(localOut, input) {
t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
}
}
+
+func TestLargeGeneratedRoundTrips(t *testing.T) {
+ lowEntropy := make([]byte, 1<<20)
+
+ rng := rand.New(rand.NewSource(1))
+ mediumEntropy := make([]byte, 192<<10)
+ for i := range mediumEntropy {
+ mediumEntropy[i] = byte(rng.Intn(8))
+ }
+
+ highEntropy := make([]byte, 192<<10)
+ if _, err := rand.New(rand.NewSource(2)).Read(highEntropy); err != nil {
+ t.Fatalf("rand.Read: %v", err)
+ }
+
+ inputs := []struct {
+ name string
+ data []byte
+ }{
+ {"low", lowEntropy},
+ {"medium", mediumEntropy},
+ {"high", highEntropy},
+ }
+ levels := []int{
+ NoCompression,
+ BestSpeed,
+ DefaultCompression,
+ HuffmanOnly,
+ 5,
+ 6,
+ 7,
+ 8,
+ BestCompression,
+ }
+ for _, input := range inputs {
+ for _, level := range levels {
+ for _, chunked := range []bool{false, true} {
+ name := fmt.Sprintf("%s/level_%d", input.name, level)
+ if chunked {
+ name += "/chunked"
+ } else {
+ name += "/single"
+ }
+ t.Run(name, func(t *testing.T) {
+ testRoundTripWithReaders(t, input.data, level, chunked)
+ })
+ }
+ }
+ }
+}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/large_low_entropy_test.go
gofmt -w flate/large_low_entropy_test.go && go test ./flate -run TestLargeGeneratedRoundTrips -count=1 -v
Chunk ID: 77d4fd Wall time: 1.0067 seconds Process running with session ID 76190 Original token count: 274 Output: === RUN TestLargeGeneratedRoundTrips === RUN TestLargeGeneratedRoundTrips/low/level_0/single === RUN TestLargeGeneratedRoundTrips/low/level_0/chunked === RUN TestLargeGeneratedRoundTrips/low/level_1/single === RUN TestLargeGeneratedRoundTrips/low/level_1/chunked === RUN TestLargeGeneratedRoundTrips/low/level_-1/single === RUN TestLargeGeneratedRoundTrips/low/level_-1/chunked === RUN TestLargeGeneratedRoundTrips/low/level_-2/single === RUN TestLargeGeneratedRoundTrips/low/level_-2/chunked === RUN TestLargeGeneratedRoundTrips/low/level_5/single === RUN TestLargeGeneratedRoundTrips/low/level_5/chunked === RUN TestLargeGeneratedRoundTrips/low/level_6/single === RUN TestLargeGeneratedRoundTrips/low/level_6/chunked === RUN TestLargeGeneratedRoundTrips/low/level_7/single === RUN TestLargeGeneratedRoundTrips/low/level_7/chunked === RUN TestLargeGeneratedRoundTrips/low/level_8/single === RUN TestLargeGeneratedRoundTrips/low/level_8/chunked === RUN TestLargeGeneratedRoundTrips/low/level_9/single === RUN TestLargeGeneratedRoundTrips/low/level_9/chunked
{
"session_id": 93521,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: 16283b
Wall time: 0.0000 seconds
Process exited with code 1
Original token count: 1039
Output:
--- FAIL: TestWriteBlockDynamic (0.02s)
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.915s
FAIL
nl -ba flate/huffman_bit_writer_test.go | sed -n '100,210p'
Chunk ID: b9c093
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 9080
Output:
100 tokens []token
101 input string // File name of input data matching the tokens.
102 want string // File name of data with the expected output with input available.
103 wantNoInput string // File name of the expected output when no input is available.
104 }
105
106 const ml = 0x7fc00000 // Maximum length token. Used to reduce the size of writeBlockTests
107
108 var writeBlockTests = []huffTest{
109 {
110 input: "testdata/huffman-null-max.in",
111 want: "testdata/huffman-null-max.%s.expect",
112 wantNoInput: "testdata/huffman-null-max.%s.expect-noinput",
113 tokens: []token{0x0, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, 0x0, 0x0},
114 },
115 {
116 input: "testdata/huffman-pi.in",
117 want: "testdata/huffman-pi.%s.expect",
118 wantNoInput: "testdata/huffman-pi.%s.expect-noinput",
119 tokens: []token{0x33, 0x2e, 0x31, 0x34, 0x31, 0x35, 0x39, 0x32, 0x36, 0x35, 0x33, 0x35, 0x38, 0x39, 0x37, 0x39, 0x33, 0x32, 0x33, 0x38, 0x34, 0x36, 0x32, 0x36, 0x34, 0x33, 0x33, 0x38, 0x33, 0x32, 0x37, 0x39, 0x35, 0x30, 0x32, 0x38, 0x38, 0x34, 0x31, 0x39, 0x37, 0x31, 0x36, 0x39, 0x33, 0x39, 0x39, 0x33, 0x37, 0x35, 0x31, 0x30, 0x35, 0x38, 0x32, 0x30, 0x39, 0x37, 0x34, 0x39, 0x34, 0x34, 0x35, 0x39, 0x32, 0x33, 0x30, 0x37, 0x38, 0x31, 0x36, 0x34, 0x30, 0x36, 0x32, 0x38, 0x36, 0x32, 0x30, 0x38, 0x39, 0x39, 0x38, 0x36, 0x32, 0x38, 0x30, 0x33, 0x34, 0x38, 0x32, 0x35, 0x33, 0x34, 0x32, 0x31, 0x31, 0x37, 0x30, 0x36, 0x37, 0x39, 0x38, 0x32, 0x31, 0x34, 0x38, 0x30, 0x38, 0x36, 0x35, 0x31, 0x33, 0x32, 0x38, 0x32, 0x33, 0x30, 0x36, 0x36, 0x34, 0x37, 0x30, 0x39, 0x33, 0x38, 0x34, 0x34, 0x36, 0x30, 0x39, 0x35, 0x35, 0x30, 0x35, 0x38, 0x32, 0x32, 0x33, 0x31, 0x37, 0x32, 0x35, 0x33, 0x35, 0x39, 0x34, 0x30, 0x38, 0x31, 0x32, 0x38, 0x34, 0x38, 0x31, 0x31, 0x31, 0x37, 0x34, 0x4040007e, 0x34, 0x31, 0x30, 0x32, 0x37, 0x30, 0x31, 0x39, 0x33, 0x38, 0x35, 0x32, 0x31, 0x31, 0x30, 0x35, 0x35, 0x35, 0x39, 0x36, 0x34, 0x34, 0x36, 0x32, 0x32, 0x39, 0x34, 0x38, 0x39, 0x35, 0x34, 0x39, 0x33, 0x30, 0x33, 0x38, 0x31, 0x40400012, 0x32, 0x38, 0x38, 0x31, 0x30, 0x39, 0x37, 0x35, 0x36, 0x36, 0x35, 0x39, 0x33, 0x33, 0x34, 0x34, 0x36, 0x40400047, 0x37, 0x35, 0x36, 0x34, 0x38, 0x32, 0x33, 0x33, 0x37, 0x38, 0x36, 0x37, 0x38, 0x33, 0x31, 0x36, 0x35, 0x32, 0x37, 0x31, 0x32, 0x30, 0x31, 0x39, 0x30, 0x39, 0x31, 0x34, 0x4040001a, 0x35, 0x36, 0x36, 0x39, 0x32, 0x33, 0x34, 0x36, 0x404000b2, 0x36, 0x31, 0x30, 0x34, 0x35, 0x34, 0x33, 0x32, 0x36, 0x40400032, 0x31, 0x33, 0x33, 0x39, 0x33, 0x36, 0x30, 0x37, 0x32, 0x36, 0x30, 0x32, 0x34, 0x39, 0x31, 0x34, 0x31, 0x32, 0x37, 0x33, 0x37, 0x32, 0x34, 0x35, 0x38, 0x37, 0x30, 0x30, 0x36, 0x36, 0x30, 0x36, 0x33, 0x31, 0x35, 0x35, 0x38, 0x38, 0x31, 0x37, 0x34, 0x38, 0x38, 0x31, 0x35, 0x32, 0x30, 0x39, 0x32, 0x30, 0x39, 0x36, 0x32, 0x38, 0x32, 0x39, 0x32, 0x35, 0x34, 0x30, 0x39, 0x31, 0x37, 0x31, 0x35, 0x33, 0x36, 0x34, 0x33, 0x36, 0x37, 0x38, 0x39, 0x32, 0x35, 0x39, 0x30, 0x33, 0x36, 0x30, 0x30, 0x31, 0x31, 0x33, 0x33, 0x30, 0x35, 0x33, 0x30, 0x35, 0x34, 0x38, 0x38, 0x32, 0x30, 0x34, 0x36, 0x36, 0x35, 0x32, 0x31, 0x33, 0x38, 0x34, 0x31, 0x34, 0x36, 0x39, 0x35, 0x31, 0x39, 0x34, 0x31, 0x35, 0x31, 0x31, 0x36, 0x30, 0x39, 0x34, 0x33, 0x33, 0x30, 0x35, 0x37, 0x32, 0x37, 0x30, 0x33, 0x36, 0x35, 0x37, 0x35, 0x39, 0x35, 0x39, 0x31, 0x39, 0x35, 0x33, 0x30, 0x39, 0x32, 0x31, 0x38, 0x36, 0x31, 0x31, 0x37, 0x404000e9, 0x33, 0x32, 0x40400009, 0x39, 0x33, 0x31, 0x30, 0x35, 0x31, 0x31, 0x38, 0x35, 0x34, 0x38, 0x30, 0x37, 0x4040010e, 0x33, 0x37, 0x39, 0x39, 0x36, 0x32, 0x37, 0x34, 0x39, 0x35, 0x36, 0x37, 0x33, 0x35, 0x31, 0x38, 0x38, 0x35, 0x37, 0x35, 0x32, 0x37, 0x32, 0x34, 0x38, 0x39, 0x31, 0x32, 0x32, 0x37, 0x39, 0x33, 0x38, 0x31, 0x38, 0x33, 0x30, 0x31, 0x31, 0x39, 0x34, 0x39, 0x31, 0x32, 0x39, 0x38, 0x33, 0x33, 0x36, 0x37, 0x33, 0x33, 0x36, 0x32, 0x34, 0x34, 0x30, 0x36, 0x35, 0x36, 0x36, 0x34, 0x33, 0x30, 0x38, 0x36, 0x30, 0x32, 0x31, 0x33, 0x39, 0x34, 0x39, 0x34, 0x36, 0x33, 0x39, 0x35, 0x32, 0x32, 0x34, 0x37, 0x33, 0x37, 0x31, 0x39, 0x30, 0x37, 0x30, 0x32, 0x31, 0x37, 0x39, 0x38, 0x40800099, 0x37, 0x30, 0x32, 0x37, 0x37, 0x30, 0x35, 0x33, 0x39, 0x32, 0x31, 0x37, 0x31, 0x37, 0x36, 0x32, 0x39, 0x33, 0x31, 0x37, 0x36, 0x37, 0x35, 0x40800232, 0x37, 0x34, 0x38, 0x31, 0x40400006, 0x36, 0x36, 0x39, 0x34, 0x30, 0x404001e7, 0x30, 0x30, 0x30, 0x35, 0x36, 0x38, 0x31, 0x32, 0x37, 0x31, 0x34, 0x35, 0x32, 0x36, 0x33, 0x35, 0x36, 0x30, 0x38, 0x32, 0x37, 0x37, 0x38, 0x35, 0x37, 0x37, 0x31, 0x33, 0x34, 0x32, 0x37, 0x35, 0x37, 0x37, 0x38, 0x39, 0x36, 0x40400129, 0x33, 0x36, 0x33, 0x37, 0x31, 0x37, 0x38, 0x37, 0x32, 0x31, 0x34, 0x36, 0x38, 0x34, 0x34, 0x30, 0x39, 0x30, 0x31, 0x32, 0x32, 0x34, 0x39, 0x35, 0x33, 0x34, 0x33, 0x30, 0x31, 0x34, 0x36, 0x35, 0x34, 0x39, 0x35, 0x38, 0x35, 0x33, 0x37, 0x31, 0x30, 0x35, 0x30, 0x37, 0x39, 0x404000ca, 0x36, 0x40400153, 0x38, 0x39, 0x32, 0x33, 0x35, 0x34, 0x404001c9, 0x39, 0x35, 0x36, 0x31, 0x31, 0x32, 0x31, 0x32, 0x39, 0x30, 0x32, 0x31, 0x39, 0x36, 0x30, 0x38, 0x36, 0x34, 0x30, 0x33, 0x34, 0x34, 0x31, 0x38, 0x31, 0x35, 0x39, 0x38, 0x31, 0x33, 0x36, 0x32, 0x39, 0x37, 0x37, 0x34, 0x40400074, 0x30, 0x39, 0x39, 0x36, 0x30, 0x35, 0x31, 0x38, 0x37, 0x30, 0x37, 0x32, 0x31, 0x31, 0x33, 0x34, 0x39, 0x40800000, 0x38, 0x33, 0x37, 0x32, 0x39, 0x37, 0x38, 0x30, 0x34, 0x39, 0x39, 0x404002da, 0x39, 0x37, 0x33, 0x31, 0x37, 0x33, 0x32, 0x38, 0x4040018a, 0x36, 0x33, 0x31, 0x38, 0x35, 0x40400301, 0x404002e8, 0x34, 0x35, 0x35, 0x33, 0x34, 0x36, 0x39, 0x30, 0x38, 0x33, 0x30, 0x32, 0x36, 0x34, 0x32, 0x35, 0x32, 0x32, 0x33, 0x30, 0x404002e3, 0x40400267, 0x38, 0x35, 0x30, 0x33, 0x35, 0x32, 0x36, 0x31, 0x39, 0x33, 0x31, 0x31, 0x40400212, 0x31, 0x30, 0x31, 0x30, 0x30, 0x30, 0x33, 0x31, 0x33, 0x37, 0x38, 0x33, 0x38, 0x37, 0x35, 0x32, 0x38, 0x38, 0x36, 0x35, 0x38, 0x37, 0x35, 0x33, 0x33, 0x32, 0x30, 0x38, 0x33, 0x38, 0x31, 0x34, 0x32, 0x30, 0x36, 0x40400140, 0x4040012b, 0x31, 0x34, 0x37, 0x33, 0x30, 0x33, 0x35, 0x39, 0x4080032e, 0x39, 0x30, 0x34, 0x32, 0x38, 0x37, 0x35, 0x35, 0x34, 0x36, 0x38, 0x37, 0x33, 0x31, 0x31, 0x35, 0x39, 0x35, 0x40400355, 0x33, 0x38, 0x38, 0x32, 0x33, 0x35, 0x33, 0x37, 0x38, 0x37, 0x35, 0x4080037f, 0x39, 0x4040013a, 0x31, 0x40400148, 0x38, 0x30, 0x35, 0x33, 0x4040018a, 0x32, 0x32, 0x36, 0x38, 0x30, 0x36, 0x36, 0x31, 0x33, 0x30, 0x30, 0x31, 0x39, 0x32, 0x37, 0x38, 0x37, 0x36, 0x36, 0x31, 0x31, 0x31, 0x39, 0x35, 0x39, 0x40400237, 0x36, 0x40800124, 0x38, 0x39, 0x33, 0x38, 0x30, 0x39, 0x35, 0x32, 0x35, 0x37, 0x32, 0x30, 0x31, 0x30, 0x36, 0x35, 0x34, 0x38, 0x35, 0x38, 0x36, 0x33, 0x32, 0x37, 0x4040009a, 0x39, 0x33, 0x36, 0x31, 0x35, 0x33, 0x40400220, 0x4080015c, 0x32, 0x33, 0x30, 0x33, 0x30, 0x31, 0x39, 0x35, 0x32, 0x30, 0x33, 0x35, 0x33, 0x30, 0x31, 0x38, 0x35, 0x32, 0x40400171, 0x40400075, 0x33, 0x36, 0x32, 0x32, 0x35, 0x39, 0x39, 0x34, 0x31, 0x33, 0x40400254, 0x34, 0x39, 0x37, 0x32, 0x31, 0x37, 0x404000de, 0x33, 0x34, 0x37, 0x39, 0x31, 0x33, 0x31, 0x35, 0x31, 0x35, 0x35, 0x37, 0x34, 0x38, 0x35, 0x37, 0x32, 0x34, 0x32, 0x34, 0x35, 0x34, 0x31, 0x35, 0x30, 0x36, 0x39, 0x4040013f, 0x38, 0x32, 0x39, 0x35, 0x33, 0x33, 0x31, 0x31, 0x36, 0x38, 0x36, 0x31, 0x37, 0x32, 0x37, 0x38, 0x40400337, 0x39, 0x30, 0x37, 0x35, 0x30, 0x39, 0x4040010d, 0x37, 0x35, 0x34, 0x36, 0x33, 0x37, 0x34, 0x36, 0x34, 0x39, 0x33, 0x39, 0x33, 0x31, 0x39, 0x32, 0x35, 0x35, 0x30, 0x36, 0x30, 0x34, 0x30, 0x30, 0x39, 0x4040026b, 0x31, 0x36, 0x37, 0x31, 0x31, 0x33, 0x39, 0x30, 0x30, 0x39, 0x38, 0x40400335, 0x34, 0x30, 0x31, 0x32, 0x38, 0x35, 0x38, 0x33, 0x36, 0x31, 0x36, 0x30, 0x33, 0x35, 0x36, 0x33, 0x37, 0x30, 0x37, 0x36, 0x36, 0x30, 0x31, 0x30, 0x34, 0x40400172, 0x38, 0x31, 0x39, 0x34, 0x32, 0x39, 0x4080041e, 0x404000ef, 0x4040028b, 0x37, 0x38, 0x33, 0x37, 0x34, 0x404004a8, 0x38, 0x32, 0x35, 0x35, 0x33, 0x37, 0x40800209, 0x32, 0x36, 0x38, 0x4040002e, 0x34, 0x30, 0x34, 0x37, 0x404001d1, 0x34, 0x404004b5, 0x4040038d, 0x38, 0x34, 0x404003a8, 0x36, 0x40c0031f, 0x33, 0x33, 0x31, 0x33, 0x36, 0x37, 0x37, 0x30, 0x32, 0x38, 0x39, 0x38, 0x39, 0x31, 0x35, 0x32, 0x40400062, 0x35, 0x32, 0x31, 0x36, 0x32, 0x30, 0x35, 0x36, 0x39, 0x36, 0x40400411, 0x30, 0x35, 0x38, 0x40400477, 0x35, 0x40400498, 0x35, 0x31, 0x31, 0x40400209, 0x38, 0x32, 0x34, 0x33, 0x30, 0x30, 0x33, 0x35, 0x35, 0x38, 0x37, 0x36, 0x34, 0x30, 0x32, 0x34, 0x37, 0x34, 0x39, 0x36, 0x34, 0x37, 0x33, 0x32, 0x36, 0x33, 0x4040043e, 0x39, 0x39, 0x32, 0x4040044b, 0x34, 0x32, 0x36, 0x39, 0x40c002c5, 0x37, 0x404001d6, 0x34, 0x4040053d, 0x4040041d, 0x39, 0x33, 0x34, 0x31, 0x37, 0x404001ad, 0x31, 0x32, 0x4040002a, 0x34, 0x4040019e, 0x31, 0x35, 0x30, 0x33, 0x30, 0x32, 0x38, 0x36, 0x31, 0x38, 0x32, 0x39, 0x37, 0x34, 0x35, 0x35, 0x35, 0x37, 0x30, 0x36, 0x37, 0x34, 0x40400135, 0x35, 0x30, 0x35, 0x34, 0x39, 0x34, 0x35, 0x38, 0x404001c5, 0x39, 0x40400051, 0x35, 0x36, 0x404001ec, 0x37, 0x32, 0x31, 0x30, 0x37, 0x39, 0x40400159, 0x33, 0x30, 0x4040010a, 0x33, 0x32, 0x31, 0x31, 0x36, 0x35, 0x33, 0x34, 0x34, 0x39, 0x38, 0x37, 0x32, 0x30, 0x32, 0x37, 0x4040011b, 0x30, 0x32, 0x33, 0x36, 0x34, 0x4040022e, 0x35, 0x34, 0x39, 0x39, 0x31, 0x31, 0x39, 0x38, 0x40400418, 0x34, 0x4040011b, 0x35, 0x33, 0x35, 0x36, 0x36, 0x33, 0x36, 0x39, 0x40400450, 0x32, 0x36, 0x35, 0x404002e4, 0x37, 0x38, 0x36, 0x32, 0x35, 0x35, 0x31, 0x404003da, 0x31, 0x37, 0x35, 0x37, 0x34, 0x36, 0x37, 0x32, 0x38, 0x39, 0x30, 0x39, 0x37, 0x37, 0x37, 0x37, 0x40800453, 0x30, 0x30, 0x30, 0x404005fd, 0x37, 0x30, 0x404004df, 0x36, 0x404003e9, 0x34, 0x39, 0x31, 0x4040041e, 0x40400297, 0x32, 0x31, 0x34, 0x37, 0x37, 0x32, 0x33, 0x35, 0x30, 0x31, 0x34, 0x31, 0x34, 0x40400643, 0x33, 0x35, 0x36, 0x404004af, 0x31, 0x36, 0x31, 0x33, 0x36, 0x31, 0x31, 0x35, 0x37, 0x33, 0x35, 0x32, 0x35, 0x40400504, 0x33, 0x34, 0x4040005b, 0x31, 0x38, 0x4040047b, 0x38, 0x34, 0x404005e7, 0x33, 0x33, 0x32, 0x33, 0x39, 0x30, 0x37, 0x33, 0x39, 0x34, 0x31, 0x34, 0x33, 0x33, 0x33, 0x34, 0x35, 0x34, 0x37, 0x37, 0x36, 0x32, 0x34, 0x40400242, 0x32, 0x35, 0x31, 0x38, 0x39, 0x38, 0x33, 0x35, 0x36, 0x39, 0x34, 0x38, 0x35, 0x35, 0x36, 0x32, 0x30, 0x39, 0x39, 0x32, 0x31, 0x39, 0x32, 0x32, 0x32, 0x31, 0x38, 0x34, 0x32, 0x37, 0x4040023e, 0x32, 0x404000ba, 0x36, 0x38, 0x38, 0x37, 0x36, 0x37, 0x31, 0x37, 0x39, 0x30, 0x40400055, 0x30, 0x40800106, 0x36, 0x36, 0x404003e7, 0x38, 0x38, 0x36, 0x32, 0x37, 0x32, 0x404006dc, 0x31, 0x37, 0x38, 0x36, 0x30, 0x38, 0x35, 0x37, 0x40400073, 0x33, 0x408002fc, 0x37, 0x39, 0x37, 0x36, 0x36, 0x38, 0x31, 0x404002bd, 0x30, 0x30, 0x39, 0x35, 0x33, 0x38, 0x38, 0x40400638, 0x33, 0x404006a5, 0x30, 0x36, 0x38, 0x30, 0x30, 0x36, 0x34, 0x32, 0x32, 0x35, 0x31, 0x32, 0x35, 0x32, 0x4040057b, 0x37, 0x33, 0x39, 0x32, 0x40400297, 0x40400474, 0x34, 0x408006b3, 0x38, 0x36, 0x32, 0x36, 0x39, 0x34, 0x35, 0x404001e5, 0x34, 0x31, 0x39, 0x36, 0x35, 0x32, 0x38, 0x35, 0x30, 0x40400099, 0x4040039c, 0x31, 0x38, 0x36, 0x33, 0x404001be, 0x34, 0x40800154, 0x32, 0x30, 0x33, 0x39, 0x4040058b, 0x34, 0x35, 0x404002bc, 0x32, 0x33, 0x37, 0x4040042c, 0x36, 0x40400510, 0x35, 0x36, 0x40400638, 0x37, 0x31, 0x39, 0x31, 0x37, 0x32, 0x38, 0x40400171, 0x37, 0x36, 0x34, 0x36, 0x35, 0x37, 0x35, 0x37, 0x33, 0x39, 0x40400101, 0x33, 0x38, 0x39, 0x40400748, 0x38, 0x33, 0x32, 0x36, 0x34, 0x35, 0x39, 0x39, 0x35, 0x38, 0x404006a7, 0x30, 0x34, 0x37, 0x38, 0x404001de, 0x40400328, 0x39, 0x4040002d, 0x36, 0x34, 0x30, 0x37, 0x38, 0x39, 0x35, 0x31, 0x4040008e, 0x36, 0x38, 0x33, 0x4040012f, 0x32, 0x35, 0x39, 0x35, 0x37, 0x30, 0x40400468, 0x38, 0x32, 0x32, 0x404002c8, 0x32, 0x4040061b, 0x34, 0x30, 0x37, 0x37, 0x32, 0x36, 0x37, 0x31, 0x39, 0x34, 0x37, 0x38, 0x40400319, 0x38, 0x32, 0x36, 0x30, 0x31, 0x34, 0x37, 0x36, 0x39, 0x39, 0x30, 0x39, 0x404004e8, 0x30, 0x31, 0x33, 0x36, 0x33, 0x39, 0x34, 0x34, 0x33, 0x4040027f, 0x33, 0x30, 0x40400105, 0x32, 0x30, 0x33, 0x34, 0x39, 0x36, 0x32, 0x35, 0x32, 0x34, 0x35, 0x31, 0x37, 0x404003b5, 0x39, 0x36, 0x35, 0x31, 0x34, 0x33, 0x31, 0x34, 0x32, 0x39, 0x38, 0x30, 0x39, 0x31, 0x39, 0x30, 0x36, 0x35, 0x39, 0x32, 0x40400282, 0x37, 0x32, 0x32, 0x31, 0x36, 0x39, 0x36, 0x34, 0x36, 0x40400419, 0x4040007a, 0x35, 0x4040050e, 0x34, 0x40800565, 0x38, 0x40400559, 0x39, 0x37, 0x4040057b, 0x35, 0x34, 0x4040049d, 0x4040023e, 0x37, 0x4040065a, 0x38, 0x34, 0x36, 0x38, 0x31, 0x33, 0x4040008c, 0x36, 0x38, 0x33, 0x38, 0x36, 0x38, 0x39, 0x34, 0x32, 0x37, 0x37, 0x34, 0x31, 0x35, 0x35, 0x39, 0x39, 0x31, 0x38, 0x35, 0x4040005a, 0x32, 0x34, 0x35, 0x39, 0x35, 0x33, 0x39, 0x35, 0x39, 0x34, 0x33, 0x31, 0x404005b7, 0x37, 0x40400012, 0x36, 0x38, 0x30, 0x38, 0x34, 0x35, 0x404002e7, 0x37, 0x33, 0x4040081e, 0x39, 0x35, 0x38, 0x34, 0x38, 0x36, 0x35, 0x33, 0x38, 0x404006e8, 0x36, 0x32, 0x404000f2, 0x36, 0x30, 0x39, 0x404004b6, 0x36, 0x30, 0x38, 0x30, 0x35, 0x31, 0x32, 0x34, 0x33, 0x38, 0x38, 0x34, 0x4040013a, 0x4040000b, 0x34, 0x31, 0x33, 0x4040030f, 0x37, 0x36, 0x32, 0x37, 0x38, 0x40400341, 0x37, 0x31, 0x35, 0x4040059b, 0x33, 0x35, 0x39, 0x39, 0x37, 0x37, 0x30, 0x30, 0x31, 0x32, 0x39, 0x40400472, 0x38, 0x39, 0x34, 0x34, 0x31, 0x40400277, 0x36, 0x38, 0x35, 0x35, 0x4040005f, 0x34, 0x30, 0x36, 0x33, 0x404008e6, 0x32, 0x30, 0x37, 0x32, 0x32, 0x40400158, 0x40800203, 0x34, 0x38, 0x31, 0x35, 0x38, 0x40400205, 0x404001fe, 0x4040027a, 0x40400298, 0x33, 0x39, 0x34, 0x35, 0x32, 0x32, 0x36, 0x37, 0x40c00496, 0x38, 0x4040058a, 0x32, 0x31, 0x404002ea, 0x32, 0x40400387, 0x35, 0x34, 0x36, 0x36, 0x36, 0x4040051b, 0x32, 0x33, 0x39, 0x38, 0x36, 0x34, 0x35, 0x36, 0x404004c4, 0x31, 0x36, 0x33, 0x35, 0x40800253, 0x40400811, 0x37, 0x404008ad, 0x39, 0x38, 0x4040045e, 0x39, 0x33, 0x36, 0x33, 0x34, 0x4040075b, 0x37, 0x34, 0x33, 0x32, 0x34, 0x4040047b, 0x31, 0x35, 0x30, 0x37, 0x36, 0x404004bb, 0x37, 0x39, 0x34, 0x35, 0x31, 0x30, 0x39, 0x4040003e, 0x30, 0x39, 0x34, 0x30, 0x404006a6, 0x38, 0x38, 0x37, 0x39, 0x37, 0x31, 0x30, 0x38, 0x39, 0x33, 0x404008f0, 0x36, 0x39, 0x31, 0x33, 0x36, 0x38, 0x36, 0x37, 0x32, 0x4040025b, 0x404001fe, 0x35, 0x4040053f, 0x40400468, 0x40400801, 0x31, 0x37, 0x39, 0x32, 0x38, 0x36, 0x38, 0x404008cc, 0x38, 0x37, 0x34, 0x37, 0x4080079e, 0x38, 0x32, 0x34, 0x4040097a, 0x38, 0x4040025b, 0x37, 0x31, 0x34, 0x39, 0x30, 0x39, 0x36, 0x37, 0x35, 0x39, 0x38, 0x404006ef, 0x33, 0x36, 0x35, 0x40400134, 0x38, 0x31, 0x4040005c, 0x40400745, 0x40400936, 0x36, 0x38, 0x32, 0x39, 0x4040057e, 0x38, 0x37, 0x32, 0x32, 0x36, 0x35, 0x38, 0x38, 0x30, 0x40400611, 0x35, 0x40400249, 0x34, 0x32, 0x37, 0x30, 0x34, 0x37, 0x37, 0x35, 0x35, 0x4040081e, 0x33, 0x37, 0x39, 0x36, 0x34, 0x31, 0x34, 0x35, 0x31, 0x35, 0x32, 0x404005fd, 0x32, 0x33, 0x34, 0x33, 0x36, 0x34, 0x35, 0x34, 0x404005de, 0x34, 0x34, 0x34, 0x37, 0x39, 0x35, 0x4040003c, 0x40400523, 0x408008e6, 0x34, 0x31, 0x4040052a, 0x33, 0x40400304, 0x35, 0x32, 0x33, 0x31, 0x40800841, 0x31, 0x36, 0x36, 0x31, 0x404008b2, 0x35, 0x39, 0x36, 0x39, 0x35, 0x33, 0x36, 0x32, 0x33, 0x31, 0x34, 0x404005ff, 0x32, 0x34, 0x38, 0x34, 0x39, 0x33, 0x37, 0x31, 0x38, 0x37, 0x31, 0x31, 0x30, 0x31, 0x34, 0x35, 0x37, 0x36, 0x35, 0x34, 0x40400761, 0x30, 0x32, 0x37, 0x39, 0x39, 0x33, 0x34, 0x34, 0x30, 0x33, 0x37, 0x34, 0x32, 0x30, 0x30, 0x37, 0x4040093f, 0x37, 0x38, 0x35, 0x33, 0x39, 0x30, 0x36, 0x32, 0x31, 0x39, 0x40800299, 0x40400345, 0x38, 0x34, 0x37, 0x408003d2, 0x38, 0x33, 0x33, 0x32, 0x31, 0x34, 0x34, 0x35, 0x37, 0x31, 0x40400284, 0x40400776, 0x34, 0x33, 0x35, 0x30, 0x40400928, 0x40400468, 0x35, 0x33, 0x31, 0x39, 0x31, 0x30, 0x34, 0x38, 0x34, 0x38, 0x31, 0x30, 0x30, 0x35, 0x33, 0x37, 0x30, 0x36, 0x404008bc, 0x4080059d, 0x40800781, 0x31, 0x40400559, 0x37, 0x4040031b, 0x35, 0x404007ec, 0x4040040c, 0x36, 0x33, 0x408007dc, 0x34, 0x40400971, 0x4080034e, 0x408003f5, 0x38, 0x4080052d, 0x40800887, 0x39, 0x40400187, 0x39, 0x31, 0x404008ce, 0x38, 0x31, 0x34, 0x36, 0x37, 0x35, 0x31, 0x4040062b, 0x31, 0x32, 0x33, 0x39, 0x40c001a9, 0x39, 0x30, 0x37, 0x31, 0x38, 0x36, 0x34, 0x39, 0x34, 0x32, 0x33, 0x31, 0x39, 0x36, 0x31, 0x35, 0x36, 0x404001ec, 0x404006bc, 0x39, 0x35, 0x40400926, 0x40400469, 0x4040011b, 0x36, 0x30, 0x33, 0x38, 0x40400a25, 0x4040016f, 0x40400384, 0x36, 0x32, 0x4040045a, 0x35, 0x4040084c, 0x36, 0x33, 0x38, 0x39, 0x33, 0x37, 0x37, 0x38, 0x37, 0x404008c5, 0x404000f8, 0x39, 0x37, 0x39, 0x32, 0x30, 0x37, 0x37, 0x33, 0x404005d7, 0x32, 0x31, 0x38, 0x32, 0x35, 0x36, 0x404007df, 0x36, 0x36, 0x404006d6, 0x34, 0x32, 0x4080067e, 0x36, 0x404006e6, 0x34, 0x34, 0x40400024, 0x35, 0x34, 0x39, 0x32, 0x30, 0x32, 0x36, 0x30, 0x35, 0x40400ab3, 0x408003e4, 0x32, 0x30, 0x31, 0x34, 0x39, 0x404004d2, 0x38, 0x35, 0x30, 0x37, 0x33, 0x40400599, 0x36, 0x36, 0x36, 0x30, 0x40400194, 0x32, 0x34, 0x33, 0x34, 0x30, 0x40400087, 0x30, 0x4040076b, 0x38, 0x36, 0x33, 0x40400956, 0x404007e4, 0x4040042b, 0x40400174, 0x35, 0x37, 0x39, 0x36, 0x32, 0x36, 0x38, 0x35, 0x36, 0x40400140, 0x35, 0x30, 0x38, 0x40400523, 0x35, 0x38, 0x37, 0x39, 0x36, 0x39, 0x39, 0x40400711, 0x35, 0x37, 0x34, 0x40400a18, 0x38, 0x34, 0x30, 0x404008b3, 0x31, 0x34, 0x35, 0x39, 0x31, 0x4040078c, 0x37, 0x30, 0x40400234, 0x30, 0x31, 0x40400be7, 0x31, 0x32, 0x40400c74, 0x30, 0x404003c3, 0x33, 0x39, 0x40400b2a, 0x40400112, 0x37, 0x31, 0x35, 0x404003b0, 0x34, 0x32, 0x30, 0x40800bf2, 0x39, 0x40400bc2, 0x30, 0x37, 0x40400341, 0x40400795, 0x40400aaf, 0x40400c62, 0x32, 0x31, 0x40400960, 0x32, 0x35, 0x31, 0x4040057b, 0x40400944, 0x39, 0x32, 0x404001b2, 0x38, 0x32, 0x36, 0x40400b66, 0x32, 0x40400278, 0x33, 0x32, 0x31, 0x35, 0x37, 0x39, 0x31, 0x39, 0x38, 0x34, 0x31, 0x34, 0x4080087b, 0x39, 0x31, 0x36, 0x34, 0x408006e8, 0x39, 0x40800b58, 0x404008db, 0x37, 0x32, 0x32, 0x40400321, 0x35, 0x404008a4, 0x40400141, 0x39, 0x31, 0x30, 0x404000bc, 0x40400c5b, 0x35, 0x32, 0x38, 0x30, 0x31, 0x37, 0x40400231, 0x37, 0x31, 0x32, 0x40400914, 0x38, 0x33, 0x32, 0x40400373, 0x31, 0x40400589, 0x30, 0x39, 0x33, 0x35, 0x33, 0x39, 0x36, 0x35, 0x37, 0x4040064b, 0x31, 0x30, 0x38, 0x33, 0x40400069, 0x35, 0x31, 0x4040077a, 0x40400d5a, 0x31, 0x34, 0x34, 0x34, 0x32, 0x31, 0x30, 0x30, 0x40400202, 0x30, 0x33, 0x4040019c, 0x31, 0x31, 0x30, 0x33, 0x40400c81, 0x40400009, 0x40400026, 0x40c00602, 0x35, 0x31, 0x36, 0x404005d9, 0x40800883, 0x4040092a, 0x35, 0x40800c42, 0x38, 0x35, 0x31, 0x37, 0x31, 0x34, 0x33, 0x37, 0x40400605, 0x4040006d, 0x31, 0x35, 0x35, 0x36, 0x35, 0x30, 0x38, 0x38, 0x404003b9, 0x39, 0x38, 0x39, 0x38, 0x35, 0x39, 0x39, 0x38, 0x32, 0x33, 0x38, 0x404001cf, 0x404009ba, 0x33, 0x4040016c, 0x4040043e, 0x404009c3, 0x38, 0x40800e05, 0x33, 0x32, 0x40400107, 0x35, 0x40400305, 0x33, 0x404001ca, 0x39, 0x4040041b, 0x39, 0x38, 0x4040087d, 0x34, 0x40400cb8, 0x37, 0x4040064b, 0x30, 0x37, 0x404000e5, 0x34, 0x38, 0x31, 0x34, 0x31, 0x40400539, 0x38, 0x35, 0x39, 0x34, 0x36, 0x31, 0x40400bc9, 0x38, 0x30},
120 },
121 {
122 input: "testdata/huffman-rand-1k.in",
123 want: "testdata/huffman-rand-1k.%s.expect",
124 wantNoInput: "testdata/huffman-rand-1k.%s.expect-noinput",
125 tokens: []token{0xf8, 0x8b, 0x96, 0x76, 0x48, 0xd, 0x85, 0x94, 0x25, 0x80, 0xaf, 0xc2, 0xfe, 0x8d, 0xe8, 0x20, 0xeb, 0x17, 0x86, 0xc9, 0xb7, 0xc5, 0xde, 0x6, 0xea, 0x7d, 0x18, 0x8b, 0xe7, 0x3e, 0x7, 0xda, 0xdf, 0xff, 0x6c, 0x73, 0xde, 0xcc, 0xe7, 0x6d, 0x8d, 0x4, 0x19, 0x49, 0x7f, 0x47, 0x1f, 0x48, 0x15, 0xb0, 0xe8, 0x9e, 0xf2, 0x31, 0x59, 0xde, 0x34, 0xb4, 0x5b, 0xe5, 0xe0, 0x9, 0x11, 0x30, 0xc2, 0x88, 0x5b, 0x7c, 0x5d, 0x14, 0x13, 0x6f, 0x23, 0xa9, 0xd, 0xbc, 0x2d, 0x23, 0xbe, 0xd9, 0xed, 0x75, 0x4, 0x6c, 0x99, 0xdf, 0xfd, 0x70, 0x66, 0xe6, 0xee, 0xd9, 0xb1, 0x9e, 0x6e, 0x83, 0x59, 0xd5, 0xd4, 0x80, 0x59, 0x98, 0x77, 0x89, 0x43, 0x38, 0xc9, 0xaf, 0x30, 0x32, 0x9a, 0x20, 0x1b, 0x46, 0x3d, 0x67, 0x6e, 0xd7, 0x72, 0x9e, 0x4e, 0x21, 0x4f, 0xc6, 0xe0, 0xd4, 0x7b, 0x4, 0x8d, 0xa5, 0x3, 0xf6, 0x5, 0x9b, 0x6b, 0xdc, 0x2a, 0x93, 0x77, 0x28, 0xfd, 0xb4, 0x62, 0xda, 0x20, 0xe7, 0x1f, 0xab, 0x6b, 0x51, 0x43, 0x39, 0x2f, 0xa0, 0x92, 0x1, 0x6c, 0x75, 0x3e, 0xf4, 0x35, 0xfd, 0x43, 0x2e, 0xf7, 0xa4, 0x75, 0xda, 0xea, 0x9b, 0xa, 0x64, 0xb, 0xe0, 0x23, 0x29, 0xbd, 0xf7, 0xe7, 0x83, 0x3c, 0xfb, 0xdf, 0xb3, 0xae, 0x4f, 0xa4, 0x47, 0x55, 0x99, 0xde, 0x2f, 0x96, 0x6e, 0x1c, 0x43, 0x4c, 0x87, 0xe2, 0x7c, 0xd9, 0x5f, 0x4c, 0x7c, 0xe8, 0x90, 0x3, 0xdb, 0x30, 0x95, 0xd6, 0x22, 0xc, 0x47, 0xb8, 0x4d, 0x6b, 0xbd, 0x24, 0x11, 0xab, 0x2c, 0xd7, 0xbe, 0x6e, 0x7a, 0xd6, 0x8, 0xa3, 0x98, 0xd8, 0xdd, 0x15, 0x6a, 0xfa, 0x93, 0x30, 0x1, 0x25, 0x1d, 0xa2, 0x74, 0x86, 0x4b, 0x6a, 0x95, 0xe8, 0xe1, 0x4e, 0xe, 0x76, 0xb9, 0x49, 0xa9, 0x5f, 0xa0, 0xa6, 0x63, 0x3c, 0x7e, 0x7e, 0x20, 0x13, 0x4f, 0xbb, 0x66, 0x92, 0xb8, 0x2e, 0xa4, 0xfa, 0x48, 0xcb, 0xae, 0xb9, 0x3c, 0xaf, 0xd3, 0x1f, 0xe1, 0xd5, 0x8d, 0x42, 0x6d, 0xf0, 0xfc, 0x8c, 0xc, 0x0, 0xde, 0x40, 0xab, 0x8b, 0x47, 0x97, 0x4e, 0xa8, 0xcf, 0x8e, 0xdb, 0xa6, 0x8b, 0x20, 0x9, 0x84, 0x7a, 0x66, 0xe5, 0x98, 0x29, 0x2, 0x95, 0xe6, 0x38, 0x32, 0x60, 0x3, 0xe3, 0x9a, 0x1e, 0x54, 0xe8, 0x63, 0x80, 0x48, 0x9c, 0xe7, 0x63, 0x33, 0x6e, 0xa0, 0x65, 0x83, 0xfa, 0xc6, 0xba, 0x7a, 0x43, 0x71, 0x5, 0xf5, 0x68, 0x69, 0x85, 0x9c, 0xba, 0x45, 0xcd, 0x6b, 0xb, 0x19, 0xd1, 0xbb, 0x7f, 0x70, 0x85, 0x92, 0xd1, 0xb4, 0x64, 0x82, 0xb1, 0xe4, 0x62, 0xc5, 0x3c, 0x46, 0x1f, 0x92, 0x31, 0x1c, 0x4e, 0x41, 0x77, 0xf7, 0xe7, 0x87, 0xa2, 0xf, 0x6e, 0xe8, 0x92, 0x3, 0x6b, 0xa, 0xe7, 0xa9, 0x3b, 0x11, 0xda, 0x66, 0x8a, 0x29, 0xda, 0x79, 0xe1, 0x64, 0x8d, 0xe3, 0x54, 0xd4, 0xf5, 0xef, 0x64, 0x87, 0x3b, 0xf4, 0xc2, 0xf4, 0x71, 0x13, 0xa9, 0xe9, 0xe0, 0xa2, 0x6, 0x14, 0xab, 0x5d, 0xa7, 0x96, 0x0, 0xd6, 0xc3, 0xcc, 0x57, 0xed, 0x39, 0x6a, 0x25, 0xcd, 0x76, 0xea, 0xba, 0x3a, 0xf2, 0xa1, 0x95, 0x5d, 0xe5, 0x71, 0xcf, 0x9c, 0x62, 0x9e, 0x6a, 0xfa, 0xd5, 0x31, 0xd1, 0xa8, 0x66, 0x30, 0x33, 0xaa, 0x51, 0x17, 0x13, 0x82, 0x99, 0xc8, 0x14, 0x60, 0x9f, 0x4d, 0x32, 0x6d, 0xda, 0x19, 0x26, 0x21, 0xdc, 0x7e, 0x2e, 0x25, 0x67, 0x72, 0xca, 0xf, 0x92, 0xcd, 0xf6, 0xd6, 0xcb, 0x97, 0x8a, 0x33, 0x58, 0x73, 0x70, 0x91, 0x1d, 0xbf, 0x28, 0x23, 0xa3, 0xc, 0xf1, 0x83, 0xc3, 0xc8, 0x56, 0x77, 0x68, 0xe3, 0x82, 0xba, 0xb9, 0x57, 0x56, 0x57, 0x9c, 0xc3, 0xd6, 0x14, 0x5, 0x3c, 0xb1, 0xaf, 0x93, 0xc8, 0x8a, 0x57, 0x7f, 0x53, 0xfa, 0x2f, 0xaa, 0x6e, 0x66, 0x83, 0xfa, 0x33, 0xd1, 0x21, 0xab, 0x1b, 0x71, 0xb4, 0x7c, 0xda, 0xfd, 0xfb, 0x7f, 0x20, 0xab, 0x5e, 0xd5, 0xca, 0xfd, 0xdd, 0xe0, 0xee, 0xda, 0xba, 0xa8, 0x27, 0x99, 0x97, 0x69, 0xc1, 0x3c, 0x82, 0x8c, 0xa, 0x5c, 0x2d, 0x5b, 0x88, 0x3e, 0x34, 0x35, 0x86, 0x37, 0x46, 0x79, 0xe1, 0xaa, 0x19, 0xfb, 0xaa, 0xde, 0x15, 0x9, 0xd, 0x1a, 0x57, 0xff, 0xb5, 0xf, 0xf3, 0x2b, 0x5a, 0x6a, 0x4d, 0x19, 0x77, 0x71, 0x45, 0xdf, 0x4f, 0xb3, 0xec, 0xf1, 0xeb, 0x18, 0x53, 0x3e, 0x3b, 0x47, 0x8, 0x9a, 0x73, 0xa0, 0x5c, 0x8c, 0x5f, 0xeb, 0xf, 0x3a, 0xc2, 0x43, 0x67, 0xb4, 0x66, 0x67, 0x80, 0x58, 0xe, 0xc1, 0xec, 0x40, 0xd4, 0x22, 0x94, 0xca, 0xf9, 0xe8, 0x92, 0xe4, 0x69, 0x38, 0xbe, 0x67, 0x64, 0xca, 0x50, 0xc7, 0x6, 0x67, 0x42, 0x6e, 0xa3, 0xf0, 0xb7, 0x6c, 0xf2, 0xe8, 0x5f, 0xb1, 0xaf, 0xe7, 0xdb, 0xbb, 0x77, 0xb5, 0xf8, 0xcb, 0x8, 0xc4, 0x75, 0x7e, 0xc0, 0xf9, 0x1c, 0x7f, 0x3c, 0x89, 0x2f, 0xd2, 0x58, 0x3a, 0xe2, 0xf8, 0x91, 0xb6, 0x7b, 0x24, 0x27, 0xe9, 0xae, 0x84, 0x8b, 0xde, 0x74, 0xac, 0xfd, 0xd9, 0xb7, 0x69, 0x2a, 0xec, 0x32, 0x6f, 0xf0, 0x92, 0x84, 0xf1, 0x40, 0xc, 0x8a, 0xbc, 0x39, 0x6e, 0x2e, 0x73, 0xd4, 0x6e, 0x8a, 0x74, 0x2a, 0xdc, 0x60, 0x1f, 0xa3, 0x7, 0xde, 0x75, 0x8b, 0x74, 0xc8, 0xfe, 0x63, 0x75, 0xf6, 0x3d, 0x63, 0xac, 0x33, 0x89, 0xc3, 0xf0, 0xf8, 0x2d, 0x6b, 0xb4, 0x9e, 0x74, 0x8b, 0x5c, 0x33, 0xb4, 0xca, 0xa8, 0xe4, 0x99, 0xb6, 0x90, 0xa1, 0xef, 0xf, 0xd3, 0x61, 0xb2, 0xc6, 0x1a, 0x94, 0x7c, 0x44, 0x55, 0xf4, 0x45, 0xff, 0x9e, 0xa5, 0x5a, 0xc6, 0xa0, 0xe8, 0x2a, 0xc1, 0x8d, 0x6f, 0x34, 0x11, 0xb9, 0xbe, 0x4e, 0xd9, 0x87, 0x97, 0x73, 0xcf, 0x3d, 0x23, 0xae, 0xd5, 0x1a, 0x5e, 0xae, 0x5d, 0x6a, 0x3, 0xf9, 0x22, 0xd, 0x10, 0xd9, 0x47, 0x69, 0x15, 0x3f, 0xee, 0x52, 0xa3, 0x8, 0xd2, 0x3c, 0x51, 0xf4, 0xf8, 0x9d, 0xe4, 0x98, 0x89, 0xc8, 0x67, 0x39, 0xd5, 0x5e, 0x35, 0x78, 0x27, 0xe8, 0x3c, 0x80, 0xae, 0x79, 0x71, 0xd2, 0x93, 0xf4, 0xaa, 0x51, 0x12, 0x1c, 0x4b, 0x1b, 0xe5, 0x6e, 0x15, 0x6f, 0xe4, 0xbb, 0x51, 0x9b, 0x45, 0x9f, 0xf9, 0xc4, 0x8c, 0x2a, 0xfb, 0x1a, 0xdf, 0x55, 0xd3, 0x48, 0x93, 0x27, 0x1, 0x26, 0xc2, 0x6b, 0x55, 0x6d, 0xa2, 0xfb, 0x84, 0x8b, 0xc9, 0x9e, 0x28, 0xc2, 0xef, 0x1a, 0x24, 0xec, 0x9b, 0xae, 0xbd, 0x60, 0xe9, 0x15, 0x35, 0xee, 0x42, 0xa4, 0x33, 0x5b, 0xfa, 0xf, 0xb6, 0xf7, 0x1, 0xa6, 0x2, 0x4c, 0xca, 0x90, 0x58, 0x3a, 0x96, 0x41, 0xe7, 0xcb, 0x9, 0x8c, 0xdb, 0x85, 0x4d, 0xa8, 0x89, 0xf3, 0xb5, 0x8e, 0xfd, 0x75, 0x5b, 0x4f, 0xed, 0xde, 0x3f, 0xeb, 0x38, 0xa3, 0xbe, 0xb0, 0x73, 0xfc, 0xb8, 0x54, 0xf7, 0x4c, 0x30, 0x67, 0x2e, 0x38, 0xa2, 0x54, 0x18, 0xba, 0x8, 0xbf, 0xf2, 0x39, 0xd5, 0xfe, 0xa5, 0x41, 0xc6, 0x66, 0x66, 0xba, 0x81, 0xef, 0x67, 0xe4, 0xe6, 0x3c, 0xc, 0xca, 0xa4, 0xa, 0x79, 0xb3, 0x57, 0x8b, 0x8a, 0x75, 0x98, 0x18, 0x42, 0x2f, 0x29, 0xa3, 0x82, 0xef, 0x9f, 0x86, 0x6, 0x23, 0xe1, 0x75, 0xfa, 0x8, 0xb1, 0xde, 0x17, 0x4a},
126 },
127 {
128 input: "testdata/huffman-rand-limit.in",
129 want: "testdata/huffman-rand-limit.%s.expect",
130 wantNoInput: "testdata/huffman-rand-limit.%s.expect-noinput",
131 tokens: []token{0x61, 0x51c00000, 0xa, 0xf8, 0x8b, 0x96, 0x76, 0x48, 0xa, 0x85, 0x94, 0x25, 0x80, 0xaf, 0xc2, 0xfe, 0x8d, 0xe8, 0x20, 0xeb, 0x17, 0x86, 0xc9, 0xb7, 0xc5, 0xde, 0x6, 0xea, 0x7d, 0x18, 0x8b, 0xe7, 0x3e, 0x7, 0xda, 0xdf, 0xff, 0x6c, 0x73, 0xde, 0xcc, 0xe7, 0x6d, 0x8d, 0x4, 0x19, 0x49, 0x7f, 0x47, 0x1f, 0x48, 0x15, 0xb0, 0xe8, 0x9e, 0xf2, 0x31, 0x59, 0xde, 0x34, 0xb4, 0x5b, 0xe5, 0xe0, 0x9, 0x11, 0x30, 0xc2, 0x88, 0x5b, 0x7c, 0x5d, 0x14, 0x13, 0x6f, 0x23, 0xa9, 0xa, 0xbc, 0x2d, 0x23, 0xbe, 0xd9, 0xed, 0x75, 0x4, 0x6c, 0x99, 0xdf, 0xfd, 0x70, 0x66, 0xe6, 0xee, 0xd9, 0xb1, 0x9e, 0x6e, 0x83, 0x59, 0xd5, 0xd4, 0x80, 0x59, 0x98, 0x77, 0x89, 0x43, 0x38, 0xc9, 0xaf, 0x30, 0x32, 0x9a, 0x20, 0x1b, 0x46, 0x3d, 0x67, 0x6e, 0xd7, 0x72, 0x9e, 0x4e, 0x21, 0x4f, 0xc6, 0xe0, 0xd4, 0x7b, 0x4, 0x8d, 0xa5, 0x3, 0xf6, 0x5, 0x9b, 0x6b, 0xdc, 0x2a, 0x93, 0x77, 0x28, 0xfd, 0xb4, 0x62, 0xda, 0x20, 0xe7, 0x1f, 0xab, 0x6b, 0x51, 0x43, 0x39, 0x2f, 0xa0, 0x92, 0x1, 0x6c, 0x75, 0x3e, 0xf4, 0x35, 0xfd, 0x43, 0x2e, 0xf7, 0xa4, 0x75, 0xda, 0xea, 0x9b, 0xa},
132 },
133 {
134 input: "testdata/huffman-shifts.in",
135 want: "testdata/huffman-shifts.%s.expect",
136 wantNoInput: "testdata/huffman-shifts.%s.expect-noinput",
137 tokens: []token{0x31, 0x30, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x52400001, 0xd, 0xa, 0x32, 0x33, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7fc00001, 0x7f400001},
138 },
139 {
140 input: "testdata/huffman-text-shift.in",
141 want: "testdata/huffman-text-shift.%s.expect",
142 wantNoInput: "testdata/huffman-text-shift.%s.expect-noinput",
143 tokens: []token{0x2f, 0x2f, 0x43, 0x6f, 0x70, 0x79, 0x72, 0x69, 0x67, 0x68, 0x74, 0x32, 0x30, 0x30, 0x39, 0x54, 0x68, 0x47, 0x6f, 0x41, 0x75, 0x74, 0x68, 0x6f, 0x72, 0x2e, 0x41, 0x6c, 0x6c, 0x40800016, 0x72, 0x72, 0x76, 0x64, 0x2e, 0xd, 0xa, 0x2f, 0x2f, 0x55, 0x6f, 0x66, 0x74, 0x68, 0x69, 0x6f, 0x75, 0x72, 0x63, 0x63, 0x6f, 0x64, 0x69, 0x67, 0x6f, 0x76, 0x72, 0x6e, 0x64, 0x62, 0x79, 0x42, 0x53, 0x44, 0x2d, 0x74, 0x79, 0x6c, 0x40400020, 0x6c, 0x69, 0x63, 0x6e, 0x74, 0x68, 0x74, 0x63, 0x6e, 0x62, 0x66, 0x6f, 0x75, 0x6e, 0x64, 0x69, 0x6e, 0x74, 0x68, 0x4c, 0x49, 0x43, 0x45, 0x4e, 0x53, 0x45, 0x66, 0x69, 0x6c, 0x2e, 0xd, 0xa, 0xd, 0xa, 0x70, 0x63, 0x6b, 0x67, 0x6d, 0x69, 0x6e, 0x4040000a, 0x69, 0x6d, 0x70, 0x6f, 0x72, 0x74, 0x22, 0x6f, 0x22, 0x4040000c, 0x66, 0x75, 0x6e, 0x63, 0x6d, 0x69, 0x6e, 0x28, 0x29, 0x7b, 0xd, 0xa, 0x9, 0x76, 0x72, 0x62, 0x3d, 0x6d, 0x6b, 0x28, 0x5b, 0x5d, 0x62, 0x79, 0x74, 0x2c, 0x36, 0x35, 0x35, 0x33, 0x35, 0x29, 0xd, 0xa, 0x9, 0x66, 0x2c, 0x5f, 0x3a, 0x3d, 0x6f, 0x2e, 0x43, 0x72, 0x74, 0x28, 0x22, 0x68, 0x75, 0x66, 0x66, 0x6d, 0x6e, 0x2d, 0x6e, 0x75, 0x6c, 0x6c, 0x2d, 0x6d, 0x78, 0x2e, 0x69, 0x6e, 0x22, 0x40800021, 0x2e, 0x57, 0x72, 0x69, 0x74, 0x28, 0x62, 0x29, 0xd, 0xa, 0x7d, 0xd, 0xa, 0x41, 0x42, 0x43, 0x44, 0x45, 0x46, 0x47, 0x48, 0x49, 0x4a, 0x4b, 0x4c, 0x4d, 0x4e, 0x4f, 0x50, 0x51, 0x52, 0x53, 0x54, 0x55, 0x56, 0x58, 0x78, 0x79, 0x7a, 0x21, 0x22, 0x23, 0xc2, 0xa4, 0x25, 0x26, 0x2f, 0x3f, 0x22},
144 },
145 {
146 input: "testdata/huffman-text.in",
147 want: "testdata/huffman-text.%s.expect",
148 wantNoInput: "testdata/huffman-text.%s.expect-noinput",
149 tokens: []token{0x2f, 0x2f, 0x20, 0x43, 0x6f, 0x70, 0x79, 0x72, 0x69, 0x67, 0x68, 0x74, 0x20, 0x32, 0x30, 0x30, 0x39, 0x20, 0x54, 0x68, 0x65, 0x20, 0x47, 0x6f, 0x20, 0x41, 0x75, 0x74, 0x68, 0x6f, 0x72, 0x73, 0x2e, 0x20, 0x41, 0x6c, 0x6c, 0x20, 0x4080001e, 0x73, 0x20, 0x72, 0x65, 0x73, 0x65, 0x72, 0x76, 0x65, 0x64, 0x2e, 0xd, 0xa, 0x2f, 0x2f, 0x20, 0x55, 0x73, 0x65, 0x20, 0x6f, 0x66, 0x20, 0x74, 0x68, 0x69, 0x73, 0x20, 0x73, 0x6f, 0x75, 0x72, 0x63, 0x65, 0x20, 0x63, 0x6f, 0x64, 0x65, 0x20, 0x69, 0x73, 0x20, 0x67, 0x6f, 0x76, 0x65, 0x72, 0x6e, 0x65, 0x64, 0x20, 0x62, 0x79, 0x20, 0x61, 0x20, 0x42, 0x53, 0x44, 0x2d, 0x73, 0x74, 0x79, 0x6c, 0x65, 0x40800036, 0x6c, 0x69, 0x63, 0x65, 0x6e, 0x73, 0x65, 0x20, 0x74, 0x68, 0x61, 0x74, 0x20, 0x63, 0x61, 0x6e, 0x20, 0x62, 0x65, 0x20, 0x66, 0x6f, 0x75, 0x6e, 0x64, 0x20, 0x69, 0x6e, 0x20, 0x74, 0x68, 0x65, 0x20, 0x4c, 0x49, 0x43, 0x45, 0x4e, 0x53, 0x45, 0x20, 0x66, 0x69, 0x6c, 0x65, 0x2e, 0xd, 0xa, 0xd, 0xa, 0x70, 0x61, 0x63, 0x6b, 0x61, 0x67, 0x65, 0x20, 0x6d, 0x61, 0x69, 0x6e, 0x4040000f, 0x69, 0x6d, 0x70, 0x6f, 0x72, 0x74, 0x20, 0x22, 0x6f, 0x73, 0x22, 0x4040000e, 0x66, 0x75, 0x6e, 0x63, 0x4080001b, 0x28, 0x29, 0x20, 0x7b, 0xd, 0xa, 0x9, 0x76, 0x61, 0x72, 0x20, 0x62, 0x20, 0x3d, 0x20, 0x6d, 0x61, 0x6b, 0x65, 0x28, 0x5b, 0x5d, 0x62, 0x79, 0x74, 0x65, 0x2c, 0x20, 0x36, 0x35, 0x35, 0x33, 0x35, 0x29, 0xd, 0xa, 0x9, 0x66, 0x2c, 0x20, 0x5f, 0x20, 0x3a, 0x3d, 0x20, 0x6f, 0x73, 0x2e, 0x43, 0x72, 0x65, 0x61, 0x74, 0x65, 0x28, 0x22, 0x68, 0x75, 0x66, 0x66, 0x6d, 0x61, 0x6e, 0x2d, 0x6e, 0x75, 0x6c, 0x6c, 0x2d, 0x6d, 0x61, 0x78, 0x2e, 0x69, 0x6e, 0x22, 0x4080002a, 0x2e, 0x57, 0x72, 0x69, 0x74, 0x65, 0x28, 0x62, 0x29, 0xd, 0xa, 0x7d, 0xd, 0xa},
150 },
151 {
152 input: "testdata/huffman-zero.in",
153 want: "testdata/huffman-zero.%s.expect",
154 wantNoInput: "testdata/huffman-zero.%s.expect-noinput",
155 tokens: []token{0x30, ml, 0x4b800000},
156 },
157 {
158 input: "",
159 want: "",
160 wantNoInput: "testdata/null-long-match.%s.expect-noinput",
161 tokens: []token{0x0, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, ml, 0x41400000},
162 },
163 }
164
165 // TestWriteBlock tests if the writeBlock encoding has changed.
166 // To update the reference files use the "-update" flag on the test.
167 func TestWriteBlock(t *testing.T) {
168 for _, test := range writeBlockTests {
169 testBlock(t, test, "wb")
170 }
171 }
172
173 // TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
174 // To update the reference files use the "-update" flag on the test.
175 func TestWriteBlockDynamic(t *testing.T) {
176 for _, test := range writeBlockTests {
177 testBlock(t, test, "dyn")
178 }
179 }
180
181 // TestWriteBlockDynamic tests if the writeBlockDynamic encoding has changed.
182 // To update the reference files use the "-update" flag on the test.
183 func TestWriteBlockDynamicSync(t *testing.T) {
184 for _, test := range writeBlockTests {
185 testBlock(t, test, "sync")
186 }
187 }
188
189 // testBlock tests a block against its references,
190 // or regenerate the references, if "-update" flag is set.
191 func testBlock(t *testing.T, test huffTest, ttype string) {
192 if test.want != "" {
193 test.want = fmt.Sprintf(test.want, ttype)
194 }
195 const gotSuffix = ".got"
196 test.wantNoInput = fmt.Sprintf(test.wantNoInput, ttype)
197 tokens := indexTokens(test.tokens)
198 if *update {
199 if test.input != "" {
200 t.Logf("Updating %q", test.want)
201 input, err := os.ReadFile(test.input)
202 if err != nil {
203 t.Error(err)
204 return
205 }
206
207 f, err := os.Create(test.want)
208 if err != nil {
209 t.Error(err)
210 return
nl -ba flate/huffman_bit_writer_test.go | sed -n '210,330p'
Chunk ID: f4c418
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 973
Output:
210 return
211 }
212 defer f.Close()
213 bw := newHuffmanBitWriter(f)
214 writeToType(t, ttype, bw, tokens, input)
215 }
216
217 t.Logf("Updating %q", test.wantNoInput)
218 f, err := os.Create(test.wantNoInput)
219 if err != nil {
220 t.Error(err)
221 return
222 }
223 defer f.Close()
224 bw := newHuffmanBitWriter(f)
225 writeToType(t, ttype, bw, tokens, nil)
226 return
227 }
228
229 if test.input != "" {
230 t.Logf("Testing %q", test.want)
231 input, err := os.ReadFile(test.input)
232 if err != nil {
233 t.Error(err)
234 return
235 }
236 want, err := os.ReadFile(test.want)
237 if err != nil {
238 t.Error(err)
239 return
240 }
241 var buf bytes.Buffer
242 bw := newHuffmanBitWriter(&buf)
243 writeToType(t, ttype, bw, tokens, input)
244
245 got := buf.Bytes()
246 if !bytes.Equal(got, want) {
247 t.Errorf("writeBlock did not yield expected result for file %q with input. See %q", test.want, test.want+gotSuffix)
248 if err := os.WriteFile(test.want+gotSuffix, got, 0666); err != nil {
249 t.Error(err)
250 }
251 }
252 t.Log("Output ok")
253
254 // Test if the writer produces the same output after reset.
255 buf.Reset()
256 bw.reset(&buf)
257 writeToType(t, ttype, bw, tokens, input)
258 bw.flush()
259 got = buf.Bytes()
260 if !bytes.Equal(got, want) {
261 t.Errorf("reset: writeBlock did not yield expected result for file %q with input. See %q", test.want, test.want+".reset"+gotSuffix)
262 if err := os.WriteFile(test.want+".reset"+gotSuffix, got, 0666); err != nil {
263 t.Error(err)
264 }
265 return
266 }
267 t.Log("Reset ok")
268 testWriterEOF(t, "wb", test, true)
269 }
270 t.Logf("Testing %q", test.wantNoInput)
271 wantNI, err := os.ReadFile(test.wantNoInput)
272 if err != nil {
273 t.Error(err)
274 return
275 }
276 var buf bytes.Buffer
277 bw := newHuffmanBitWriter(&buf)
278 writeToType(t, ttype, bw, tokens, nil)
279
280 got := buf.Bytes()
281 if !bytes.Equal(got, wantNI) {
282 t.Errorf("writeBlock did not yield expected result for file %q with input. See %q", test.wantNoInput, test.wantNoInput+gotSuffix)
283 if err := os.WriteFile(test.wantNoInput+gotSuffix, got, 0666); err != nil {
284 t.Error(err)
285 }
286 } else if got[0]&1 == 1 {
287 t.Error("got unexpected EOF")
288 return
289 }
290
291 t.Log("Output ok")
292
293 // Test if the writer produces the same output after reset.
294 buf.Reset()
295 bw.reset(&buf)
296 writeToType(t, ttype, bw, tokens, nil)
297 bw.flush()
298 got = buf.Bytes()
299 if !bytes.Equal(got, wantNI) {
300 t.Errorf("reset: writeBlock did not yield expected result for file %q without input. See %q", test.wantNoInput, test.wantNoInput+".reset"+gotSuffix)
301 if err := os.WriteFile(test.wantNoInput+".reset"+gotSuffix, got, 0666); err != nil {
302 t.Error(err)
303 }
304 return
305 }
306 t.Log("Reset ok")
307 testWriterEOF(t, "wb", test, false)
308 }
309
310 func writeToType(t *testing.T, ttype string, bw *huffmanBitWriter, tok tokens, input []byte) {
311 switch ttype {
312 case "wb":
313 bw.writeBlock(&tok, false, input)
314 case "dyn":
315 bw.writeBlockDynamic(&tok, false, input, false)
316 case "sync":
317 bw.writeBlockDynamic(&tok, false, input, true)
318 default:
319 panic("unknown test type")
320 }
321
322 if bw.err != nil {
323 t.Error(bw.err)
324 return
325 }
326
327 bw.flush()
328 if bw.err != nil {
329 t.Error(bw.err)
330 return
cmp -l flate/testdata/huffman-rand-1k.dyn.expect-noinput flate/testdata/huffman-rand-1k.dyn.expect-noinput.got | sed -n '1,40p'; ls -l flate/testdata/huffman-rand-1k.dyn.expect-noinput*
Chunk ID: f4b3f7 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 202 Output: 1 374 4 2 377 300 3 377 13 4 377 70 5 377 32 6 377 10 7 377 0 8 377 0 73 376 356 74 103 77 75 152 244 76 151 226 77 222 46 78 247 171 79 126 152 80 116 345 81 261 24 82 161 33 83 106 147 84 53 264 85 357 362 86 204 116 87 46 150 88 3 62 89 257 360 90 137 372 91 316 345 92 35 334 93 351 221 94 172 256 95 53 267 96 126 142 97 133 265 98 373 265 99 135 337 100 217 365 101 52 250 102 165 122 103 276 347 104 40 13 -rw-r--r-- 1 root root 1054 Jun 11 22:43 flate/testdata/huffman-rand-1k.dyn.expect-noinput -rw-r--r-- 1 root root 1054 Jun 21 18:15 flate/testdata/huffman-rand-1k.dyn.expect-noinput.got -rw-r--r-- 1 root root 1054 Jun 21 18:15 flate/testdata/huffman-rand-1k.dyn.expect-noinput.reset.got
{
"session_id": 76190,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: f396f2
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1545
Output:
=== RUN TestLargeGeneratedRoundTrips/medium/level_0/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_0/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_1/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_1/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_-1/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_-1/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_-2/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_-2/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_5/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_5/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_6/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_6/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_7/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_7/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_8/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_8/chunked
=== RUN TestLargeGeneratedRoundTrips/medium/level_9/single
=== RUN TestLargeGeneratedRoundTrips/medium/level_9/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_0/single
=== RUN TestLargeGeneratedRoundTrips/high/level_0/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_1/single
=== RUN TestLargeGeneratedRoundTrips/high/level_1/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_-1/single
=== RUN TestLargeGeneratedRoundTrips/high/level_-1/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_-2/single
=== RUN TestLargeGeneratedRoundTrips/high/level_-2/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_5/single
=== RUN TestLargeGeneratedRoundTrips/high/level_5/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_6/single
=== RUN TestLargeGeneratedRoundTrips/high/level_6/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_7/single
=== RUN TestLargeGeneratedRoundTrips/high/level_7/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_8/single
=== RUN TestLargeGeneratedRoundTrips/high/level_8/chunked
=== RUN TestLargeGeneratedRoundTrips/high/level_9/single
=== RUN TestLargeGeneratedRoundTrips/high/level_9/chunked
--- PASS: TestLargeGeneratedRoundTrips (1.23s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_0/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_0/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_1/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_1/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_-1/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_-1/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_-2/single (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_-2/chunked (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_5/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_5/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_6/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_6/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_7/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_7/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_8/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_8/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_9/single (0.53s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_9/chunked (0.55s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_0/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_0/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_1/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_1/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_-1/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_-1/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_-2/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_-2/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_5/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_5/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_6/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_6/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_7/single (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_7/chunked (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_8/single (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_8/chunked (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_9/single (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/medium/level_9/chunked (0.01s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_0/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_0/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_1/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_1/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_-1/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_-1/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_-2/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_-2/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_5/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_5/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_6/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_6/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_7/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_7/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_8/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_8/chunked (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_9/single (0.00s)
--- PASS: TestLargeGeneratedRoundTrips/high/level_9/chunked (0.00s)
PASS
ok [code-host]/klauspost/compress/flate 1.233s
nl -ba flate/huffman_bit_writer_test.go | sed -n '330,390p'
Chunk ID: eb0b08
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 334
Output:
330 return
331 }
332 }
333
334 // testWriterEOF tests if the written block contains an EOF marker.
335 func testWriterEOF(t *testing.T, ttype string, test huffTest, useInput bool) {
336 if useInput && test.input == "" {
337 return
338 }
339 var input []byte
340 if useInput {
341 var err error
342 input, err = os.ReadFile(test.input)
343 if err != nil {
344 t.Error(err)
345 return
346 }
347 }
348 var buf bytes.Buffer
349 bw := newHuffmanBitWriter(&buf)
350 tokens := indexTokens(test.tokens)
351 switch ttype {
352 case "wb":
353 bw.writeBlock(&tokens, true, input)
354 case "dyn":
355 bw.writeBlockDynamic(&tokens, true, input, true)
356 case "huff":
357 bw.writeBlockHuff(true, input, true)
358 default:
359 panic("unknown test type")
360 }
361 if bw.err != nil {
362 t.Error(bw.err)
363 return
364 }
365
366 bw.flush()
367 if bw.err != nil {
368 t.Error(bw.err)
369 return
370 }
371 b := buf.Bytes()
372 if len(b) == 0 {
373 t.Error("no output received")
374 return
375 }
376 if b[0]&1 != 1 {
377 t.Errorf("block not marked with EOF for input %q", test.input)
378 return
379 }
380 t.Log("EOF ok")
381 }
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
} else {
w.literalFreq[endBlockMarker] = 1
- if numLiterals < endBlockMarker+1 {
+ if numLiterals < endBlockMarker {
numLiterals = endBlockMarker + 1
}
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
rm -f flate/testdata/*.got flate/testdata/*.reset.got && gofmt -w flate/huffman_bit_writer.go && go test ./flate -run 'TestLargeGeneratedRoundTrips|TestWriteBlock|TestBlockHuff|TestDeterministicL[0-9]|TestDeterministicLM2' -count=1
Chunk ID: 974abd Wall time: 1.0022 seconds Process running with session ID 72196 Original token count: 0 Output:
go test ./flate -run TestLargeGeneratedRoundTrips/low/level_9 -count=1 -v
Chunk ID: a964d1 Wall time: 1.0022 seconds Process running with session ID 96777 Original token count: 25 Output: === RUN TestLargeGeneratedRoundTrips === RUN TestLargeGeneratedRoundTrips/low/level_9/single
{
"session_id": 96777,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 12000
}
, output,
Chunk ID: 20f853
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 75
Output:
=== RUN TestLargeGeneratedRoundTrips/low/level_9/chunked
--- PASS: TestLargeGeneratedRoundTrips (1.18s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_9/single (0.56s)
--- PASS: TestLargeGeneratedRoundTrips/low/level_9/chunked (0.62s)
PASS
ok [code-host]/klauspost/compress/flate 1.182s
{
"session_id": 72196,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: 06a271
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 12
Output:
ok [code-host]/klauspost/compress/flate 2.305s
*** Begin Patch
*** Update File: /app/flate/large_low_entropy_test.go
@@
lowEntropy := make([]byte, 1<<20)
+ highByteLowEntropy := bytes.Repeat([]byte{0xff}, 1<<20)
@@
inputs := []struct {
name string
data []byte
}{
- {"low", lowEntropy},
+ {"low_zero", lowEntropy},
+ {"low_ff", highByteLowEntropy},
{"medium", mediumEntropy},
{"high", highEntropy},
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/large_low_entropy_test.go
gofmt -w flate/large_low_entropy_test.go && go test ./flate -run 'TestLargeGeneratedRoundTrips/low_(zero|ff)/level_9' -count=1 -v
Chunk ID: b5dc6b Wall time: 1.0018 seconds Process running with session ID 51702 Original token count: 42 Output: === RUN TestLargeGeneratedRoundTrips === RUN TestLargeGeneratedRoundTrips/low_zero/level_9/single === RUN TestLargeGeneratedRoundTrips/low_zero/level_9/chunked
{
"session_id": 51702,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 16000
}
, output,
Chunk ID: 84c352
Wall time: 0.0000 seconds
Process exited with code 1
Original token count: 184
Output:
=== RUN TestLargeGeneratedRoundTrips/low_ff/level_9/single
large_low_entropy_test.go:105: standard reader rejected stream: flate: corrupt input before offset 3
=== RUN TestLargeGeneratedRoundTrips/low_ff/level_9/chunked
large_low_entropy_test.go:105: standard reader rejected stream: flate: corrupt input before offset 3
--- FAIL: TestLargeGeneratedRoundTrips (2.26s)
--- PASS: TestLargeGeneratedRoundTrips/low_zero/level_9/single (0.59s)
--- PASS: TestLargeGeneratedRoundTrips/low_zero/level_9/chunked (0.57s)
--- FAIL: TestLargeGeneratedRoundTrips/low_ff/level_9/single (0.56s)
--- FAIL: TestLargeGeneratedRoundTrips/low_ff/level_9/chunked (0.55s)
FAIL
FAIL [code-host]/klauspost/compress/flate 2.265s
FAIL
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
} else {
w.literalFreq[endBlockMarker] = 1
- if numLiterals < endBlockMarker {
- numLiterals = endBlockMarker + 1
+ if numLiterals < endBlockMarker+1 {
+ includeEOB := numLiterals < endBlockMarker
+ for i := 0; !includeEOB && i < endBlockMarker; i++ {
+ includeEOB = w.literalFreq[i] == 0
+ }
+ if includeEOB {
+ numLiterals = endBlockMarker + 1
+ }
}
}
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
gofmt -w flate/huffman_bit_writer.go && go test ./flate -run 'TestLargeGeneratedRoundTrips/low_(zero|ff)/level_9' -count=1 -v
Chunk ID: 7e734f Wall time: 1.0019 seconds Process running with session ID 37611 Original token count: 42 Output: === RUN TestLargeGeneratedRoundTrips === RUN TestLargeGeneratedRoundTrips/low_zero/level_9/single === RUN TestLargeGeneratedRoundTrips/low_zero/level_9/chunked
rm -f flate/testdata/*.got flate/testdata/*.reset.got && go test ./flate -run 'TestWriteBlock|TestBlockHuff|TestDeterministicL[0-9]|TestDeterministicLM2' -count=1
Chunk ID: b4bb29 Wall time: 1.0015 seconds Process running with session ID 41530 Original token count: 0 Output:
{
"session_id": 37611,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 16000
}
, output,
Chunk ID: b836ec
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 131
Output:
=== RUN TestLargeGeneratedRoundTrips/low_ff/level_9/single
=== RUN TestLargeGeneratedRoundTrips/low_ff/level_9/chunked
--- PASS: TestLargeGeneratedRoundTrips (2.30s)
--- PASS: TestLargeGeneratedRoundTrips/low_zero/level_9/single (0.61s)
--- PASS: TestLargeGeneratedRoundTrips/low_zero/level_9/chunked (0.61s)
--- PASS: TestLargeGeneratedRoundTrips/low_ff/level_9/single (0.54s)
--- PASS: TestLargeGeneratedRoundTrips/low_ff/level_9/chunked (0.54s)
PASS
ok [code-host]/klauspost/compress/flate 2.299s
{
"session_id": 41530,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 20000
}
, output,
Chunk ID: 2d4827
Wall time: 0.0000 seconds
Process exited with code 1
Original token count: 1039
Output:
--- FAIL: TestWriteBlockDynamic (0.00s)
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 1.024s
FAIL
rg -n "newHuffmanBitWriter" -S
Chunk ID: cfcc5f
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 184
Output:
flate/token_test.go:34: wr := newHuffmanBitWriter(&buf)
flate/deflate.go:786: d.w = newHuffmanBitWriter(w)
flate/huffman_bit_writer.go:146:func newHuffmanBitWriter(w io.Writer) *huffmanBitWriter {
flate/huffman_bit_writer.go:986: w := newHuffmanBitWriter(nil)
flate/huffman_bit_writer_test.go:48: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer_test.go:213: bw := newHuffmanBitWriter(f)
flate/huffman_bit_writer_test.go:224: bw := newHuffmanBitWriter(f)
flate/huffman_bit_writer_test.go:242: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer_test.go:277: bw := newHuffmanBitWriter(&buf)
flate/huffman_bit_writer_test.go:349: bw := newHuffmanBitWriter(&buf)
flate/stateless.go:60: return newHuffmanBitWriter(nil)
*** Begin Patch
*** Update File: /app/flate/huffman_bit_writer.go
@@
err error
lastHeader int
+ requireDynamicEOB bool
// Set between 0 (reused block can be up to 2x the size)
logNewTablePenalty uint
@@
w.literalFreq[endBlockMarker] = 1
- if numLiterals < endBlockMarker+1 {
+ if w.requireDynamicEOB && numLiterals < endBlockMarker+1 {
includeEOB := numLiterals < endBlockMarker
for i := 0; !includeEOB && i < endBlockMarker; i++ {
includeEOB = w.literalFreq[i] == 0
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/huffman_bit_writer.go
*** Begin Patch
*** Update File: /app/flate/deflate.go
@@
func (d *compressor) init(w io.Writer, level int) (err error) {
d.w = newHuffmanBitWriter(w)
+ d.w.requireDynamicEOB = true
switch {
*** End Patch
Exit code: 0
Wall time: 0 seconds
Output:
Success. Updated the following files:
M /app/flate/deflate.go
rm -f flate/testdata/*.got flate/testdata/*.reset.got && gofmt -w flate/deflate.go flate/huffman_bit_writer.go flate/large_low_entropy_test.go && go test ./flate -run 'TestLargeGeneratedRoundTrips|TestWriteBlock|TestBlockHuff|TestDeterministicL[0-9]|TestDeterministicLM2' -count=1
Chunk ID: 7d58fb Wall time: 1.0013 seconds Process running with session ID 97978 Original token count: 0 Output:
go test ./flate -run 'TestLargeGeneratedRoundTrips/low_(zero|ff)/level_9' -count=1 -v
Chunk ID: 1f2003 Wall time: 1.0009 seconds Process running with session ID 87373 Original token count: 42 Output: === RUN TestLargeGeneratedRoundTrips === RUN TestLargeGeneratedRoundTrips/low_zero/level_9/single === RUN TestLargeGeneratedRoundTrips/low_zero/level_9/chunked
{
"session_id": 87373,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 16000
}
, output,
Chunk ID: 805dba
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 131
Output:
=== RUN TestLargeGeneratedRoundTrips/low_ff/level_9/single
=== RUN TestLargeGeneratedRoundTrips/low_ff/level_9/chunked
--- PASS: TestLargeGeneratedRoundTrips (2.40s)
--- PASS: TestLargeGeneratedRoundTrips/low_zero/level_9/single (0.58s)
--- PASS: TestLargeGeneratedRoundTrips/low_zero/level_9/chunked (0.65s)
--- PASS: TestLargeGeneratedRoundTrips/low_ff/level_9/single (0.59s)
--- PASS: TestLargeGeneratedRoundTrips/low_ff/level_9/chunked (0.57s)
PASS
ok [code-host]/klauspost/compress/flate 2.399s
{
"session_id": 97978,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: 3fdf5b
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 12
Output:
ok [code-host]/klauspost/compress/flate 3.410s
go build ./...
Chunk ID: b674ec Wall time: 0.0214 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -list .
Chunk ID: b325b1 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 680 Output: TestBulkHash4 TestDeflate TestVeryLongSparseChunk TestDeflateInflate TestReverseBits TestDeflateInflateString TestReaderDict TestWriterDict TestRegression2508 TestWriterReset TestBestSpeed TestDictDecoder TestIssue5915 TestIssue5962 TestIssue6255 TestInvalidEncoding TestRegressions TestInvalidBits TestStreams TestBlockHuff TestWriteBlock TestWriteBlockDynamic TestWriteBlockDynamicSync TestReset TestReaderTruncated TestResetDict TestInflate TestWriteTo TestReaderPartialBlock TestLargeGeneratedRoundTrips TestNlitOutOfRange Test_tokens_EstimatedBits TestWriterMemUsage TestWriterRegression TestWriteError TestWriter_Reset TestDeterministicL1 TestDeterministicL2 TestDeterministicL3 TestDeterministicL4 TestDeterministicL5 TestDeterministicL6 TestDeterministicL7 TestDeterministicL8 TestDeterministicL9 TestDeterministicL0 TestDeterministicLM2 BenchmarkDecodeDigitsSpeed1e4 BenchmarkDecodeDigitsSpeed1e5 BenchmarkDecodeDigitsSpeed1e6 BenchmarkDecodeDigitsDefault1e4 BenchmarkDecodeDigitsDefault1e5 BenchmarkDecodeDigitsDefault1e6 BenchmarkDecodeDigitsCompress1e4 BenchmarkDecodeDigitsCompress1e5 BenchmarkDecodeDigitsCompress1e6 BenchmarkDecodeTwainSpeed1e4 BenchmarkDecodeTwainSpeed1e5 BenchmarkDecodeTwainSpeed1e6 BenchmarkDecodeTwainDefault1e4 BenchmarkDecodeTwainDefault1e5 BenchmarkDecodeTwainDefault1e6 BenchmarkDecodeTwainCompress1e4 BenchmarkDecodeTwainCompress1e5 BenchmarkDecodeTwainCompress1e6 BenchmarkDecodeRandomSpeed1e4 BenchmarkDecodeRandomSpeed1e5 BenchmarkDecodeRandomSpeed1e6 Benchmark_tokens_EstimatedBits BenchmarkEncodeDigitsConstant1e4 BenchmarkEncodeDigitsConstant1e5 BenchmarkEncodeDigitsConstant1e6 BenchmarkEncodeDigitsSpeed1e4 BenchmarkEncodeDigitsSpeed1e5 BenchmarkEncodeDigitsSpeed1e6 BenchmarkEncodeDigitsDefault1e4 BenchmarkEncodeDigitsDefault1e5 BenchmarkEncodeDigitsDefault1e6 BenchmarkEncodeDigitsCompress1e4 BenchmarkEncodeDigitsCompress1e5 BenchmarkEncodeDigitsCompress1e6 BenchmarkEncodeDigitsSL1e4 BenchmarkEncodeDigitsSL1e5 BenchmarkEncodeDigitsSL1e6 BenchmarkEncodeTwainConstant1e4 BenchmarkEncodeTwainConstant1e5 BenchmarkEncodeTwainConstant1e6 BenchmarkEncodeTwainSpeed1e4 BenchmarkEncodeTwainSpeed1e5 BenchmarkEncodeTwainSpeed1e6 BenchmarkEncodeTwainDefault1e4 BenchmarkEncodeTwainDefault1e5 BenchmarkEncodeTwainDefault1e6 BenchmarkEncodeTwainCompress1e4 BenchmarkEncodeTwainCompress1e5 BenchmarkEncodeTwainCompress1e6 BenchmarkEncodeTwainSL1e4 BenchmarkEncodeTwainSL1e5 BenchmarkEncodeTwainSL1e6 BenchmarkEncodeTwain1024Win1e4 BenchmarkEncodeTwain1024Win1e5 BenchmarkEncodeTwain1024Win1e6 BenchmarkCompressAllocations BenchmarkCompressAllocationsSingle FuzzEncoding Example_reset Example_dictionary Example_synchronization ok [code-host]/klauspost/compress/flate 0.002s
find flate/testdata -maxdepth 2 -name '*.got' -o -name '*.reset.got'
Chunk ID: 069d3c Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'Test(Deflate|DeflateInflate|Regression2508|Regressions|WriterRegression|NlitOutOfRange|InvalidEncoding|InvalidBits|Streams|Inflate|ReaderPartialBlock|ReaderTruncated|WriteError|Writer_Reset|WriterReset|WriterDict|ReaderDict|BestSpeed|VeryLongSparseChunk|Issue5915|Issue5962|Issue6255)$' -count=1
Chunk ID: b9f748 Wall time: 1.0033 seconds Process running with session ID 11223 Original token count: 0 Output:
{
"session_id": 11223,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: ec6f1d
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 12
Output:
ok [code-host]/klauspost/compress/flate 4.221s
nl -ba flate/huffman_bit_writer.go | sed -n '98,125p;700,720p' && nl -ba flate/deflate.go | sed -n '785,790p' && nl -ba flate/large_low_entropy_test.go | sed -n '1,180p'
Chunk ID: c0579c
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 1325
Output:
98 type huffmanBitWriter struct {
99 // writer is the underlying writer.
100 // Do not use it directly; use the write method, which ensures
101 // that Write errors are sticky.
102 writer io.Writer
103
104 // Data waiting to be written is bytes[0:nbytes]
105 // and then the low nbits of bits.
106 bits uint64
107 nbits uint8
108 nbytes uint8
109 lastHuffMan bool
110 literalEncoding *huffmanEncoder
111 tmpLitEncoding *huffmanEncoder
112 offsetEncoding *huffmanEncoder
113 codegenEncoding *huffmanEncoder
114 err error
115 lastHeader int
116 requireDynamicEOB bool
117 // Set between 0 (reused block can be up to 2x the size)
118 logNewTablePenalty uint
119 bytes [256 + 8]byte
120 literalFreq [lengthCodesStart + 32]uint16
121 offsetFreq [32]uint16
122 codegenFreq [codegenCodeCount]uint16
123
124 // codegen must have an extra space for the final symbol.
125 codegen [literalCount + offsetCodeCount + 1]uint8
700 w.writeStoredHeader(len(input), eof)
701 w.writeBytes(input)
702 return
703 }
704 }
705
706 // We want a new block/table
707 if w.lastHeader == 0 {
708 if fillReuse && !sync {
709 w.fillTokens()
710 numLiterals, numOffsets = maxNumLit, maxNumDist
711 } else {
712 w.literalFreq[endBlockMarker] = 1
713 if w.requireDynamicEOB && numLiterals < endBlockMarker+1 {
714 includeEOB := numLiterals < endBlockMarker
715 for i := 0; !includeEOB && i < endBlockMarker; i++ {
716 includeEOB = w.literalFreq[i] == 0
717 }
718 if includeEOB {
719 numLiterals = endBlockMarker + 1
720 }
785 func (d *compressor) init(w io.Writer, level int) (err error) {
786 d.w = newHuffmanBitWriter(w)
787 d.w.requireDynamicEOB = true
788
789 switch {
790 case level == NoCompression:
1 package flate
2
3 import (
4 "bytes"
5 stdflate "compress/flate"
6 "fmt"
7 "io"
8 "math/rand"
9 "testing"
10 )
11
12 func testRoundTripWithReaders(t *testing.T, input []byte, level int, chunked bool) {
13 t.Helper()
14 var compressed bytes.Buffer
15 w, err := NewWriter(&compressed, level)
16 if err != nil {
17 t.Fatalf("NewWriter: %v", err)
18 }
19 if chunked {
20 for off := 0; off < len(input); {
21 n := 787
22 if off+n > len(input) {
23 n = len(input) - off
24 }
25 if _, err := w.Write(input[off : off+n]); err != nil {
26 t.Fatalf("Write: %v", err)
27 }
28 off += n
29 }
30 } else {
31 if _, err := w.Write(input); err != nil {
32 t.Fatalf("Write: %v", err)
33 }
34 }
35 if err := w.Close(); err != nil {
36 t.Fatalf("Close: %v", err)
37 }
38
39 stdReader := stdflate.NewReader(bytes.NewReader(compressed.Bytes()))
40 stdOut, err := io.ReadAll(stdReader)
41 _ = stdReader.Close()
42 if err != nil {
43 t.Fatalf("standard reader rejected stream: %v", err)
44 }
45 if !bytes.Equal(stdOut, input) {
46 t.Fatalf("standard reader mismatch: got %d bytes, want %d", len(stdOut), len(input))
47 }
48
49 localReader := NewReader(bytes.NewReader(compressed.Bytes()))
50 localOut, err := io.ReadAll(localReader)
51 _ = localReader.Close()
52 if err != nil {
53 t.Fatalf("local reader rejected stream: %v", err)
54 }
55 if !bytes.Equal(localOut, input) {
56 t.Fatalf("local reader mismatch: got %d bytes, want %d", len(localOut), len(input))
57 }
58 }
59
60 func TestLargeGeneratedRoundTrips(t *testing.T) {
61 lowEntropy := make([]byte, 1<<20)
62 highByteLowEntropy := bytes.Repeat([]byte{0xff}, 1<<20)
63
64 rng := rand.New(rand.NewSource(1))
65 mediumEntropy := make([]byte, 192<<10)
66 for i := range mediumEntropy {
67 mediumEntropy[i] = byte(rng.Intn(8))
68 }
69
70 highEntropy := make([]byte, 192<<10)
71 if _, err := rand.New(rand.NewSource(2)).Read(highEntropy); err != nil {
72 t.Fatalf("rand.Read: %v", err)
73 }
74
75 inputs := []struct {
76 name string
77 data []byte
78 }{
79 {"low_zero", lowEntropy},
80 {"low_ff", highByteLowEntropy},
81 {"medium", mediumEntropy},
82 {"high", highEntropy},
83 }
84 levels := []int{
85 NoCompression,
86 BestSpeed,
87 DefaultCompression,
88 HuffmanOnly,
89 5,
90 6,
91 7,
92 8,
93 BestCompression,
94 }
95 for _, input := range inputs {
96 for _, level := range levels {
97 for _, chunked := range []bool{false, true} {
98 name := fmt.Sprintf("%s/level_%d", input.name, level)
99 if chunked {
100 name += "/chunked"
101 } else {
102 name += "/single"
103 }
104 t.Run(name, func(t *testing.T) {
105 testRoundTripWithReaders(t, input.data, level, chunked)
106 })
107 }
108 }
109 }
110 }
go build ./...
Chunk ID: 0cbd4a Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
find flate/testdata -maxdepth 2 \( -name '*.got' -o -name '*.reset.got' \) -print
Chunk ID: 42ea03 Wall time: 0.0000 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'TestLargeGeneratedRoundTrips|TestWriteBlock|TestBlockHuff|TestDeterministicL[0-9]|TestDeterministicLM2' -count=1
Chunk ID: 302541 Wall time: 1.0035 seconds Process running with session ID 52116 Original token count: 0 Output:
{
"session_id": 52116,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: 8ca000
Wall time: 0.0000 seconds
Process exited with code 0
Original token count: 12
Output:
ok [code-host]/klauspost/compress/flate 3.287s
*** Begin Patch *** Update File: /app/flate/huffman_bit_writer.go @@ codegenEncoding *huffmanEncoder err error lastHeader int + // requireDynamicEOB makes public compressor streams advertise the + // implicit end-block code in new dynamic Huffman headers. requireDynamicEOB bool // Set between 0 (reused block can be up to 2x the size) logNewTablePenalty uint *** End Patch Exit code: 0 Wall time: 0 seconds Output: Success. Updated the following files: M /app/flate/huffman_bit_writer.go
gofmt -w flate/huffman_bit_writer.go && go build ./...
Chunk ID: 56ad12 Wall time: 0.1883 seconds Process exited with code 0 Original token count: 0 Output:
go test ./flate -run 'TestLargeGeneratedRoundTrips|TestWriteBlock|TestBlockHuff|TestDeterministicL[0-9]|TestDeterministicLM2' -count=1
Chunk ID: ceedfb Wall time: 1.0038 seconds Process running with session ID 71018 Original token count: 0 Output:
go test ./flate -run 'Test(Deflate|DeflateInflate|Regression2508|Regressions|WriterRegression|NlitOutOfRange|InvalidEncoding|InvalidBits|Streams|Inflate|ReaderPartialBlock|ReaderTruncated|WriteError|Writer_Reset|WriterReset|WriterDict|ReaderDict|BestSpeed|VeryLongSparseChunk|Issue5915|Issue5962|Issue6255)$' -count=1
Chunk ID: cd195f Wall time: 1.0011 seconds Process running with session ID 31896 Original token count: 0 Output:
{
"session_id": 71018,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: e92f29
Wall time: 0.1218 seconds
Process exited with code 0
Original token count: 12
Output:
ok [code-host]/klauspost/compress/flate 4.396s
{
"session_id": 31896,
"chars": "",
"yield_time_ms": 1000,
"max_output_tokens": 22000
}
, output,
Chunk ID: f5a8b5
Wall time: 0.4516 seconds
Process exited with code 0
Original token count: 12
Output:
ok [code-host]/klauspost/compress/flate 4.850s
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 12.04s ==============================
Reproduce this trial: git checkout 2f94510 && PYTHONPATH=src python3 scripts/build_site.py , then open trial/trial_37693344e204459a. Re-running the agent live requires EVAL_PLATFORM_ENABLE_OAUTH_SMOKE=1 and is non-deterministic.
Trial trial_37693344e204459a · verifier authoritative; classifier explanatory.