Source file src/compress/flate/deflate_test.go

Documentation: compress/flate

     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  	"bytes"
     9  	"errors"
    10  	"fmt"
    11  	"internal/testenv"
    12  	"io"
    13  	"math/rand"
    14  	"os"
    15  	"reflect"
    16  	"runtime/debug"
    17  	"sync"
    18  	"testing"
    19  )
    20  
    21  type deflateTest struct {
    22  	in    []byte
    23  	level int
    24  	out   []byte
    25  }
    26  
    27  type deflateInflateTest struct {
    28  	in []byte
    29  }
    30  
    31  type reverseBitsTest struct {
    32  	in       uint16
    33  	bitCount uint8
    34  	out      uint16
    35  }
    36  
    37  var deflateTests = []*deflateTest{
    38  	{[]byte{}, 0, []byte{1, 0, 0, 255, 255}},
    39  	{[]byte{0x11}, -1, []byte{18, 4, 4, 0, 0, 255, 255}},
    40  	{[]byte{0x11}, DefaultCompression, []byte{18, 4, 4, 0, 0, 255, 255}},
    41  	{[]byte{0x11}, 4, []byte{18, 4, 4, 0, 0, 255, 255}},
    42  
    43  	{[]byte{0x11}, 0, []byte{0, 1, 0, 254, 255, 17, 1, 0, 0, 255, 255}},
    44  	{[]byte{0x11, 0x12}, 0, []byte{0, 2, 0, 253, 255, 17, 18, 1, 0, 0, 255, 255}},
    45  	{[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 0,
    46  		[]byte{0, 8, 0, 247, 255, 17, 17, 17, 17, 17, 17, 17, 17, 1, 0, 0, 255, 255},
    47  	},
    48  	{[]byte{}, 2, []byte{1, 0, 0, 255, 255}},
    49  	{[]byte{0x11}, 2, []byte{18, 4, 4, 0, 0, 255, 255}},
    50  	{[]byte{0x11, 0x12}, 2, []byte{18, 20, 2, 4, 0, 0, 255, 255}},
    51  	{[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 2, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}},
    52  	{[]byte{}, 9, []byte{1, 0, 0, 255, 255}},
    53  	{[]byte{0x11}, 9, []byte{18, 4, 4, 0, 0, 255, 255}},
    54  	{[]byte{0x11, 0x12}, 9, []byte{18, 20, 2, 4, 0, 0, 255, 255}},
    55  	{[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 9, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}},
    56  }
    57  
    58  var deflateInflateTests = []*deflateInflateTest{
    59  	{[]byte{}},
    60  	{[]byte{0x11}},
    61  	{[]byte{0x11, 0x12}},
    62  	{[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}},
    63  	{[]byte{0x11, 0x10, 0x13, 0x41, 0x21, 0x21, 0x41, 0x13, 0x87, 0x78, 0x13}},
    64  	{largeDataChunk()},
    65  }
    66  
    67  var reverseBitsTests = []*reverseBitsTest{
    68  	{1, 1, 1},
    69  	{1, 2, 2},
    70  	{1, 3, 4},
    71  	{1, 4, 8},
    72  	{1, 5, 16},
    73  	{17, 5, 17},
    74  	{257, 9, 257},
    75  	{29, 5, 23},
    76  }
    77  
    78  func largeDataChunk() []byte {
    79  	result := make([]byte, 100000)
    80  	for i := range result {
    81  		result[i] = byte(i * i & 0xFF)
    82  	}
    83  	return result
    84  }
    85  
    86  func TestBulkHash4(t *testing.T) {
    87  	for _, x := range deflateTests {
    88  		y := x.out
    89  		if len(y) < minMatchLength {
    90  			continue
    91  		}
    92  		y = append(y, y...)
    93  		for j := 4; j < len(y); j++ {
    94  			y := y[:j]
    95  			dst := make([]uint32, len(y)-minMatchLength+1)
    96  			for i := range dst {
    97  				dst[i] = uint32(i + 100)
    98  			}
    99  			bulkHash4(y, dst)
   100  			for i, got := range dst {
   101  				want := hash4(y[i:])
   102  				if got != want && got == uint32(i)+100 {
   103  					t.Errorf("Len:%d Index:%d, want 0x%08x but not modified", len(y), i, want)
   104  				} else if got != want {
   105  					t.Errorf("Len:%d Index:%d, got 0x%08x want:0x%08x", len(y), i, got, want)
   106  				}
   107  			}
   108  		}
   109  	}
   110  }
   111  
   112  func TestDeflate(t *testing.T) {
   113  	for _, h := range deflateTests {
   114  		var buf bytes.Buffer
   115  		w, err := NewWriter(&buf, h.level)
   116  		if err != nil {
   117  			t.Errorf("NewWriter: %v", err)
   118  			continue
   119  		}
   120  		w.Write(h.in)
   121  		w.Close()
   122  		if !bytes.Equal(buf.Bytes(), h.out) {
   123  			t.Errorf("Deflate(%d, %x) = \n%#v, want \n%#v", h.level, h.in, buf.Bytes(), h.out)
   124  		}
   125  	}
   126  }
   127  
   128  // A sparseReader returns a stream consisting of 0s followed by 1<<16 1s.
   129  // This tests missing hash references in a very large input.
   130  type sparseReader struct {
   131  	l   int64
   132  	cur int64
   133  }
   134  
   135  func (r *sparseReader) Read(b []byte) (n int, err error) {
   136  	if r.cur >= r.l {
   137  		return 0, io.EOF
   138  	}
   139  	n = len(b)
   140  	cur := r.cur + int64(n)
   141  	if cur > r.l {
   142  		n -= int(cur - r.l)
   143  		cur = r.l
   144  	}
   145  	for i := range b[0:n] {
   146  		if r.cur+int64(i) >= r.l-1<<16 {
   147  			b[i] = 1
   148  		} else {
   149  			b[i] = 0
   150  		}
   151  	}
   152  	r.cur = cur
   153  	return
   154  }
   155  
   156  func TestVeryLongSparseChunk(t *testing.T) {
   157  	if testing.Short() {
   158  		t.Skip("skipping sparse chunk during short test")
   159  	}
   160  	w, err := NewWriter(io.Discard, 1)
   161  	if err != nil {
   162  		t.Errorf("NewWriter: %v", err)
   163  		return
   164  	}
   165  	if _, err = io.Copy(w, &sparseReader{l: 23e8}); err != nil {
   166  		t.Errorf("Compress failed: %v", err)
   167  		return
   168  	}
   169  }
   170  
   171  type syncBuffer struct {
   172  	buf    bytes.Buffer
   173  	mu     sync.RWMutex
   174  	closed bool
   175  	ready  chan bool
   176  }
   177  
   178  func newSyncBuffer() *syncBuffer {
   179  	return &syncBuffer{ready: make(chan bool, 1)}
   180  }
   181  
   182  func (b *syncBuffer) Read(p []byte) (n int, err error) {
   183  	for {
   184  		b.mu.RLock()
   185  		n, err = b.buf.Read(p)
   186  		b.mu.RUnlock()
   187  		if n > 0 || b.closed {
   188  			return
   189  		}
   190  		<-b.ready
   191  	}
   192  }
   193  
   194  func (b *syncBuffer) signal() {
   195  	select {
   196  	case b.ready <- true:
   197  	default:
   198  	}
   199  }
   200  
   201  func (b *syncBuffer) Write(p []byte) (n int, err error) {
   202  	n, err = b.buf.Write(p)
   203  	b.signal()
   204  	return
   205  }
   206  
   207  func (b *syncBuffer) WriteMode() {
   208  	b.mu.Lock()
   209  }
   210  
   211  func (b *syncBuffer) ReadMode() {
   212  	b.mu.Unlock()
   213  	b.signal()
   214  }
   215  
   216  func (b *syncBuffer) Close() error {
   217  	b.closed = true
   218  	b.signal()
   219  	return nil
   220  }
   221  
   222  func testSync(t *testing.T, level int, input []byte, name string) {
   223  	if len(input) == 0 {
   224  		return
   225  	}
   226  
   227  	t.Logf("--testSync %d, %d, %s", level, len(input), name)
   228  	buf := newSyncBuffer()
   229  	buf1 := new(bytes.Buffer)
   230  	buf.WriteMode()
   231  	w, err := NewWriter(io.MultiWriter(buf, buf1), level)
   232  	if err != nil {
   233  		t.Errorf("NewWriter: %v", err)
   234  		return
   235  	}
   236  	r := NewReader(buf)
   237  
   238  	// Write half the input and read back.
   239  	for i := 0; i < 2; i++ {
   240  		var lo, hi int
   241  		if i == 0 {
   242  			lo, hi = 0, (len(input)+1)/2
   243  		} else {
   244  			lo, hi = (len(input)+1)/2, len(input)
   245  		}
   246  		t.Logf("#%d: write %d-%d", i, lo, hi)
   247  		if _, err := w.Write(input[lo:hi]); err != nil {
   248  			t.Errorf("testSync: write: %v", err)
   249  			return
   250  		}
   251  		if i == 0 {
   252  			if err := w.Flush(); err != nil {
   253  				t.Errorf("testSync: flush: %v", err)
   254  				return
   255  			}
   256  		} else {
   257  			if err := w.Close(); err != nil {
   258  				t.Errorf("testSync: close: %v", err)
   259  			}
   260  		}
   261  		buf.ReadMode()
   262  		out := make([]byte, hi-lo+1)
   263  		m, err := io.ReadAtLeast(r, out, hi-lo)
   264  		t.Logf("#%d: read %d", i, m)
   265  		if m != hi-lo || err != nil {
   266  			t.Errorf("testSync/%d (%d, %d, %s): read %d: %d, %v (%d left)", i, level, len(input), name, hi-lo, m, err, buf.buf.Len())
   267  			return
   268  		}
   269  		if !bytes.Equal(input[lo:hi], out[:hi-lo]) {
   270  			t.Errorf("testSync/%d: read wrong bytes: %x vs %x", i, input[lo:hi], out[:hi-lo])
   271  			return
   272  		}
   273  		// This test originally checked that after reading
   274  		// the first half of the input, there was nothing left
   275  		// in the read buffer (buf.buf.Len() != 0) but that is
   276  		// not necessarily the case: the write Flush may emit
   277  		// some extra framing bits that are not necessary
   278  		// to process to obtain the first half of the uncompressed
   279  		// data. The test ran correctly most of the time, because
   280  		// the background goroutine had usually read even
   281  		// those extra bits by now, but it's not a useful thing to
   282  		// check.
   283  		buf.WriteMode()
   284  	}
   285  	buf.ReadMode()
   286  	out := make([]byte, 10)
   287  	if n, err := r.Read(out); n > 0 || err != io.EOF {
   288  		t.Errorf("testSync (%d, %d, %s): final Read: %d, %v (hex: %x)", level, len(input), name, n, err, out[0:n])
   289  	}
   290  	if buf.buf.Len() != 0 {
   291  		t.Errorf("testSync (%d, %d, %s): extra data at end", level, len(input), name)
   292  	}
   293  	r.Close()
   294  
   295  	// stream should work for ordinary reader too
   296  	r = NewReader(buf1)
   297  	out, err = io.ReadAll(r)
   298  	if err != nil {
   299  		t.Errorf("testSync: read: %s", err)
   300  		return
   301  	}
   302  	r.Close()
   303  	if !bytes.Equal(input, out) {
   304  		t.Errorf("testSync: decompress(compress(data)) != data: level=%d input=%s", level, name)
   305  	}
   306  }
   307  
   308  func testToFromWithLevelAndLimit(t *testing.T, level int, input []byte, name string, limit int) {
   309  	var buffer bytes.Buffer
   310  	w, err := NewWriter(&buffer, level)
   311  	if err != nil {
   312  		t.Errorf("NewWriter: %v", err)
   313  		return
   314  	}
   315  	w.Write(input)
   316  	w.Close()
   317  	if limit > 0 && buffer.Len() > limit {
   318  		t.Errorf("level: %d, len(compress(data)) = %d > limit = %d", level, buffer.Len(), limit)
   319  		return
   320  	}
   321  	if limit > 0 {
   322  		t.Logf("level: %d, size:%.2f%%, %d b\n", level, float64(buffer.Len()*100)/float64(limit), buffer.Len())
   323  	}
   324  	r := NewReader(&buffer)
   325  	out, err := io.ReadAll(r)
   326  	if err != nil {
   327  		t.Errorf("read: %s", err)
   328  		return
   329  	}
   330  	r.Close()
   331  	if !bytes.Equal(input, out) {
   332  		t.Errorf("decompress(compress(data)) != data: level=%d input=%s", level, name)
   333  		return
   334  	}
   335  	testSync(t, level, input, name)
   336  }
   337  
   338  func testToFromWithLimit(t *testing.T, input []byte, name string, limit [11]int) {
   339  	for i := 0; i < 10; i++ {
   340  		testToFromWithLevelAndLimit(t, i, input, name, limit[i])
   341  	}
   342  	// Test HuffmanCompression
   343  	testToFromWithLevelAndLimit(t, -2, input, name, limit[10])
   344  }
   345  
   346  func TestDeflateInflate(t *testing.T) {
   347  	t.Parallel()
   348  	for i, h := range deflateInflateTests {
   349  		if testing.Short() && len(h.in) > 10000 {
   350  			continue
   351  		}
   352  		testToFromWithLimit(t, h.in, fmt.Sprintf("#%d", i), [11]int{})
   353  	}
   354  }
   355  
   356  func TestReverseBits(t *testing.T) {
   357  	for _, h := range reverseBitsTests {
   358  		if v := reverseBits(h.in, h.bitCount); v != h.out {
   359  			t.Errorf("reverseBits(%v,%v) = %v, want %v",
   360  				h.in, h.bitCount, v, h.out)
   361  		}
   362  	}
   363  }
   364  
   365  type deflateInflateStringTest struct {
   366  	filename string
   367  	label    string
   368  	limit    [11]int
   369  }
   370  
   371  var deflateInflateStringTests = []deflateInflateStringTest{
   372  	{
   373  		"../testdata/e.txt",
   374  		"2.718281828...",
   375  		[...]int{100018, 50650, 50960, 51150, 50930, 50790, 50790, 50790, 50790, 50790, 43683},
   376  	},
   377  	{
   378  		"../../testdata/Isaac.Newton-Opticks.txt",
   379  		"Isaac.Newton-Opticks",
   380  		[...]int{567248, 218338, 198211, 193152, 181100, 175427, 175427, 173597, 173422, 173422, 325240},
   381  	},
   382  }
   383  
   384  func TestDeflateInflateString(t *testing.T) {
   385  	t.Parallel()
   386  	if testing.Short() && testenv.Builder() == "" {
   387  		t.Skip("skipping in short mode")
   388  	}
   389  	for _, test := range deflateInflateStringTests {
   390  		gold, err := os.ReadFile(test.filename)
   391  		if err != nil {
   392  			t.Error(err)
   393  		}
   394  		testToFromWithLimit(t, gold, test.label, test.limit)
   395  		if testing.Short() {
   396  			break
   397  		}
   398  	}
   399  }
   400  
   401  func TestReaderDict(t *testing.T) {
   402  	const (
   403  		dict = "hello world"
   404  		text = "hello again world"
   405  	)
   406  	var b bytes.Buffer
   407  	w, err := NewWriter(&b, 5)
   408  	if err != nil {
   409  		t.Fatalf("NewWriter: %v", err)
   410  	}
   411  	w.Write([]byte(dict))
   412  	w.Flush()
   413  	b.Reset()
   414  	w.Write([]byte(text))
   415  	w.Close()
   416  
   417  	r := NewReaderDict(&b, []byte(dict))
   418  	data, err := io.ReadAll(r)
   419  	if err != nil {
   420  		t.Fatal(err)
   421  	}
   422  	if string(data) != "hello again world" {
   423  		t.Fatalf("read returned %q want %q", string(data), text)
   424  	}
   425  }
   426  
   427  func TestWriterDict(t *testing.T) {
   428  	const (
   429  		dict = "hello world"
   430  		text = "hello again world"
   431  	)
   432  	var b bytes.Buffer
   433  	w, err := NewWriter(&b, 5)
   434  	if err != nil {
   435  		t.Fatalf("NewWriter: %v", err)
   436  	}
   437  	w.Write([]byte(dict))
   438  	w.Flush()
   439  	b.Reset()
   440  	w.Write([]byte(text))
   441  	w.Close()
   442  
   443  	var b1 bytes.Buffer
   444  	w, _ = NewWriterDict(&b1, 5, []byte(dict))
   445  	w.Write([]byte(text))
   446  	w.Close()
   447  
   448  	if !bytes.Equal(b1.Bytes(), b.Bytes()) {
   449  		t.Fatalf("writer wrote %q want %q", b1.Bytes(), b.Bytes())
   450  	}
   451  }
   452  
   453  // See https://golang.org/issue/2508
   454  func TestRegression2508(t *testing.T) {
   455  	if testing.Short() {
   456  		t.Logf("test disabled with -short")
   457  		return
   458  	}
   459  	w, err := NewWriter(io.Discard, 1)
   460  	if err != nil {
   461  		t.Fatalf("NewWriter: %v", err)
   462  	}
   463  	buf := make([]byte, 1024)
   464  	for i := 0; i < 131072; i++ {
   465  		if _, err := w.Write(buf); err != nil {
   466  			t.Fatalf("writer failed: %v", err)
   467  		}
   468  	}
   469  	w.Close()
   470  }
   471  
   472  func TestWriterReset(t *testing.T) {
   473  	t.Parallel()
   474  	for level := 0; level <= 9; level++ {
   475  		if testing.Short() && level > 1 {
   476  			break
   477  		}
   478  		w, err := NewWriter(io.Discard, level)
   479  		if err != nil {
   480  			t.Fatalf("NewWriter: %v", err)
   481  		}
   482  		buf := []byte("hello world")
   483  		n := 1024
   484  		if testing.Short() {
   485  			n = 10
   486  		}
   487  		for i := 0; i < n; i++ {
   488  			w.Write(buf)
   489  		}
   490  		w.Reset(io.Discard)
   491  
   492  		wref, err := NewWriter(io.Discard, level)
   493  		if err != nil {
   494  			t.Fatalf("NewWriter: %v", err)
   495  		}
   496  
   497  		// DeepEqual doesn't compare functions.
   498  		w.d.fill, wref.d.fill = nil, nil
   499  		w.d.step, wref.d.step = nil, nil
   500  		w.d.bulkHasher, wref.d.bulkHasher = nil, nil
   501  		w.d.bestSpeed, wref.d.bestSpeed = nil, nil
   502  		// hashMatch is always overwritten when used.
   503  		copy(w.d.hashMatch[:], wref.d.hashMatch[:])
   504  		if len(w.d.tokens) != 0 {
   505  			t.Errorf("level %d Writer not reset after Reset. %d tokens were present", level, len(w.d.tokens))
   506  		}
   507  		// As long as the length is 0, we don't care about the content.
   508  		w.d.tokens = wref.d.tokens
   509  
   510  		// We don't care if there are values in the window, as long as it is at d.index is 0
   511  		w.d.window = wref.d.window
   512  		if !reflect.DeepEqual(w, wref) {
   513  			t.Errorf("level %d Writer not reset after Reset", level)
   514  		}
   515  	}
   516  
   517  	levels := []int{0, 1, 2, 5, 9}
   518  	for _, level := range levels {
   519  		t.Run(fmt.Sprint(level), func(t *testing.T) {
   520  			testResetOutput(t, level, nil)
   521  		})
   522  	}
   523  
   524  	t.Run("dict", func(t *testing.T) {
   525  		for _, level := range levels {
   526  			t.Run(fmt.Sprint(level), func(t *testing.T) {
   527  				testResetOutput(t, level, nil)
   528  			})
   529  		}
   530  	})
   531  }
   532  
   533  func testResetOutput(t *testing.T, level int, dict []byte) {
   534  	writeData := func(w *Writer) {
   535  		msg := []byte("now is the time for all good gophers")
   536  		w.Write(msg)
   537  		w.Flush()
   538  
   539  		hello := []byte("hello world")
   540  		for i := 0; i < 1024; i++ {
   541  			w.Write(hello)
   542  		}
   543  
   544  		fill := bytes.Repeat([]byte("x"), 65000)
   545  		w.Write(fill)
   546  	}
   547  
   548  	buf := new(bytes.Buffer)
   549  	var w *Writer
   550  	var err error
   551  	if dict == nil {
   552  		w, err = NewWriter(buf, level)
   553  	} else {
   554  		w, err = NewWriterDict(buf, level, dict)
   555  	}
   556  	if err != nil {
   557  		t.Fatalf("NewWriter: %v", err)
   558  	}
   559  
   560  	writeData(w)
   561  	w.Close()
   562  	out1 := buf.Bytes()
   563  
   564  	buf2 := new(bytes.Buffer)
   565  	w.Reset(buf2)
   566  	writeData(w)
   567  	w.Close()
   568  	out2 := buf2.Bytes()
   569  
   570  	if len(out1) != len(out2) {
   571  		t.Errorf("got %d, expected %d bytes", len(out2), len(out1))
   572  		return
   573  	}
   574  	if !bytes.Equal(out1, out2) {
   575  		mm := 0
   576  		for i, b := range out1[:len(out2)] {
   577  			if b != out2[i] {
   578  				t.Errorf("mismatch index %d: %#02x, expected %#02x", i, out2[i], b)
   579  			}
   580  			mm++
   581  			if mm == 10 {
   582  				t.Fatal("Stopping")
   583  			}
   584  		}
   585  	}
   586  	t.Logf("got %d bytes", len(out1))
   587  }
   588  
   589  // TestBestSpeed tests that round-tripping through deflate and then inflate
   590  // recovers the original input. The Write sizes are near the thresholds in the
   591  // compressor.encSpeed method (0, 16, 128), as well as near maxStoreBlockSize
   592  // (65535).
   593  func TestBestSpeed(t *testing.T) {
   594  	t.Parallel()
   595  	abc := make([]byte, 128)
   596  	for i := range abc {
   597  		abc[i] = byte(i)
   598  	}
   599  	abcabc := bytes.Repeat(abc, 131072/len(abc))
   600  	var want []byte
   601  
   602  	testCases := [][]int{
   603  		{65536, 0},
   604  		{65536, 1},
   605  		{65536, 1, 256},
   606  		{65536, 1, 65536},
   607  		{65536, 14},
   608  		{65536, 15},
   609  		{65536, 16},
   610  		{65536, 16, 256},
   611  		{65536, 16, 65536},
   612  		{65536, 127},
   613  		{65536, 128},
   614  		{65536, 128, 256},
   615  		{65536, 128, 65536},
   616  		{65536, 129},
   617  		{65536, 65536, 256},
   618  		{65536, 65536, 65536},
   619  	}
   620  
   621  	for i, tc := range testCases {
   622  		if i >= 3 && testing.Short() {
   623  			break
   624  		}
   625  		for _, firstN := range []int{1, 65534, 65535, 65536, 65537, 131072} {
   626  			tc[0] = firstN
   627  		outer:
   628  			for _, flush := range []bool{false, true} {
   629  				buf := new(bytes.Buffer)
   630  				want = want[:0]
   631  
   632  				w, err := NewWriter(buf, BestSpeed)
   633  				if err != nil {
   634  					t.Errorf("i=%d, firstN=%d, flush=%t: NewWriter: %v", i, firstN, flush, err)
   635  					continue
   636  				}
   637  				for _, n := range tc {
   638  					want = append(want, abcabc[:n]...)
   639  					if _, err := w.Write(abcabc[:n]); err != nil {
   640  						t.Errorf("i=%d, firstN=%d, flush=%t: Write: %v", i, firstN, flush, err)
   641  						continue outer
   642  					}
   643  					if !flush {
   644  						continue
   645  					}
   646  					if err := w.Flush(); err != nil {
   647  						t.Errorf("i=%d, firstN=%d, flush=%t: Flush: %v", i, firstN, flush, err)
   648  						continue outer
   649  					}
   650  				}
   651  				if err := w.Close(); err != nil {
   652  					t.Errorf("i=%d, firstN=%d, flush=%t: Close: %v", i, firstN, flush, err)
   653  					continue
   654  				}
   655  
   656  				r := NewReader(buf)
   657  				got, err := io.ReadAll(r)
   658  				if err != nil {
   659  					t.Errorf("i=%d, firstN=%d, flush=%t: ReadAll: %v", i, firstN, flush, err)
   660  					continue
   661  				}
   662  				r.Close()
   663  
   664  				if !bytes.Equal(got, want) {
   665  					t.Errorf("i=%d, firstN=%d, flush=%t: corruption during deflate-then-inflate", i, firstN, flush)
   666  					continue
   667  				}
   668  			}
   669  		}
   670  	}
   671  }
   672  
   673  var errIO = errors.New("IO error")
   674  
   675  // failWriter fails with errIO exactly at the nth call to Write.
   676  type failWriter struct{ n int }
   677  
   678  func (w *failWriter) Write(b []byte) (int, error) {
   679  	w.n--
   680  	if w.n == -1 {
   681  		return 0, errIO
   682  	}
   683  	return len(b), nil
   684  }
   685  
   686  func TestWriterPersistentError(t *testing.T) {
   687  	t.Parallel()
   688  	d, err := os.ReadFile("../../testdata/Isaac.Newton-Opticks.txt")
   689  	if err != nil {
   690  		t.Fatalf("ReadFile: %v", err)
   691  	}
   692  	d = d[:10000] // Keep this test short
   693  
   694  	zw, err := NewWriter(nil, DefaultCompression)
   695  	if err != nil {
   696  		t.Fatalf("NewWriter: %v", err)
   697  	}
   698  
   699  	// Sweep over the threshold at which an error is returned.
   700  	// The variable i makes it such that the ith call to failWriter.Write will
   701  	// return errIO. Since failWriter errors are not persistent, we must ensure
   702  	// that flate.Writer errors are persistent.
   703  	for i := 0; i < 1000; i++ {
   704  		fw := &failWriter{i}
   705  		zw.Reset(fw)
   706  
   707  		_, werr := zw.Write(d)
   708  		cerr := zw.Close()
   709  		if werr != errIO && werr != nil {
   710  			t.Errorf("test %d, mismatching Write error: got %v, want %v", i, werr, errIO)
   711  		}
   712  		if cerr != errIO && fw.n < 0 {
   713  			t.Errorf("test %d, mismatching Close error: got %v, want %v", i, cerr, errIO)
   714  		}
   715  		if fw.n >= 0 {
   716  			// At this point, the failure threshold was sufficiently high enough
   717  			// that we wrote the whole stream without any errors.
   718  			return
   719  		}
   720  	}
   721  }
   722  
   723  func TestBestSpeedMatch(t *testing.T) {
   724  	t.Parallel()
   725  	cases := []struct {
   726  		previous, current []byte
   727  		t, s, want        int32
   728  	}{{
   729  		previous: []byte{0, 0, 0, 1, 2},
   730  		current:  []byte{3, 4, 5, 0, 1, 2, 3, 4, 5},
   731  		t:        -3,
   732  		s:        3,
   733  		want:     6,
   734  	}, {
   735  		previous: []byte{0, 0, 0, 1, 2},
   736  		current:  []byte{2, 4, 5, 0, 1, 2, 3, 4, 5},
   737  		t:        -3,
   738  		s:        3,
   739  		want:     3,
   740  	}, {
   741  		previous: []byte{0, 0, 0, 1, 1},
   742  		current:  []byte{3, 4, 5, 0, 1, 2, 3, 4, 5},
   743  		t:        -3,
   744  		s:        3,
   745  		want:     2,
   746  	}, {
   747  		previous: []byte{0, 0, 0, 1, 2},
   748  		current:  []byte{2, 2, 2, 2, 1, 2, 3, 4, 5},
   749  		t:        -1,
   750  		s:        0,
   751  		want:     4,
   752  	}, {
   753  		previous: []byte{0, 0, 0, 1, 2, 3, 4, 5, 2, 2},
   754  		current:  []byte{2, 2, 2, 2, 1, 2, 3, 4, 5},
   755  		t:        -7,
   756  		s:        4,
   757  		want:     5,
   758  	}, {
   759  		previous: []byte{9, 9, 9, 9, 9},
   760  		current:  []byte{2, 2, 2, 2, 1, 2, 3, 4, 5},
   761  		t:        -1,
   762  		s:        0,
   763  		want:     0,
   764  	}, {
   765  		previous: []byte{9, 9, 9, 9, 9},
   766  		current:  []byte{9, 2, 2, 2, 1, 2, 3, 4, 5},
   767  		t:        0,
   768  		s:        1,
   769  		want:     0,
   770  	}, {
   771  		previous: []byte{},
   772  		current:  []byte{9, 2, 2, 2, 1, 2, 3, 4, 5},
   773  		t:        -5,
   774  		s:        1,
   775  		want:     0,
   776  	}, {
   777  		previous: []byte{},
   778  		current:  []byte{9, 2, 2, 2, 1, 2, 3, 4, 5},
   779  		t:        -1,
   780  		s:        1,
   781  		want:     0,
   782  	}, {
   783  		previous: []byte{},
   784  		current:  []byte{2, 2, 2, 2, 1, 2, 3, 4, 5},
   785  		t:        0,
   786  		s:        1,
   787  		want:     3,
   788  	}, {
   789  		previous: []byte{3, 4, 5},
   790  		current:  []byte{3, 4, 5},
   791  		t:        -3,
   792  		s:        0,
   793  		want:     3,
   794  	}, {
   795  		previous: make([]byte, 1000),
   796  		current:  make([]byte, 1000),
   797  		t:        -1000,
   798  		s:        0,
   799  		want:     maxMatchLength - 4,
   800  	}, {
   801  		previous: make([]byte, 200),
   802  		current:  make([]byte, 500),
   803  		t:        -200,
   804  		s:        0,
   805  		want:     maxMatchLength - 4,
   806  	}, {
   807  		previous: make([]byte, 200),
   808  		current:  make([]byte, 500),
   809  		t:        0,
   810  		s:        1,
   811  		want:     maxMatchLength - 4,
   812  	}, {
   813  		previous: make([]byte, maxMatchLength-4),
   814  		current:  make([]byte, 500),
   815  		t:        -(maxMatchLength - 4),
   816  		s:        0,
   817  		want:     maxMatchLength - 4,
   818  	}, {
   819  		previous: make([]byte, 200),
   820  		current:  make([]byte, 500),
   821  		t:        -200,
   822  		s:        400,
   823  		want:     100,
   824  	}, {
   825  		previous: make([]byte, 10),
   826  		current:  make([]byte, 500),
   827  		t:        200,
   828  		s:        400,
   829  		want:     100,
   830  	}}
   831  	for i, c := range cases {
   832  		e := deflateFast{prev: c.previous}
   833  		got := e.matchLen(c.s, c.t, c.current)
   834  		if got != c.want {
   835  			t.Errorf("Test %d: match length, want %d, got %d", i, c.want, got)
   836  		}
   837  	}
   838  }
   839  
   840  func TestBestSpeedMaxMatchOffset(t *testing.T) {
   841  	t.Parallel()
   842  	const abc, xyz = "abcdefgh", "stuvwxyz"
   843  	for _, matchBefore := range []bool{false, true} {
   844  		for _, extra := range []int{0, inputMargin - 1, inputMargin, inputMargin + 1, 2 * inputMargin} {
   845  			for offsetAdj := -5; offsetAdj <= +5; offsetAdj++ {
   846  				report := func(desc string, err error) {
   847  					t.Errorf("matchBefore=%t, extra=%d, offsetAdj=%d: %s%v",
   848  						matchBefore, extra, offsetAdj, desc, err)
   849  				}
   850  
   851  				offset := maxMatchOffset + offsetAdj
   852  
   853  				// Make src to be a []byte of the form
   854  				//	"%s%s%s%s%s" % (abc, zeros0, xyzMaybe, abc, zeros1)
   855  				// where:
   856  				//	zeros0 is approximately maxMatchOffset zeros.
   857  				//	xyzMaybe is either xyz or the empty string.
   858  				//	zeros1 is between 0 and 30 zeros.
   859  				// The difference between the two abc's will be offset, which
   860  				// is maxMatchOffset plus or minus a small adjustment.
   861  				src := make([]byte, offset+len(abc)+extra)
   862  				copy(src, abc)
   863  				if !matchBefore {
   864  					copy(src[offset-len(xyz):], xyz)
   865  				}
   866  				copy(src[offset:], abc)
   867  
   868  				buf := new(bytes.Buffer)
   869  				w, err := NewWriter(buf, BestSpeed)
   870  				if err != nil {
   871  					report("NewWriter: ", err)
   872  					continue
   873  				}
   874  				if _, err := w.Write(src); err != nil {
   875  					report("Write: ", err)
   876  					continue
   877  				}
   878  				if err := w.Close(); err != nil {
   879  					report("Writer.Close: ", err)
   880  					continue
   881  				}
   882  
   883  				r := NewReader(buf)
   884  				dst, err := io.ReadAll(r)
   885  				r.Close()
   886  				if err != nil {
   887  					report("ReadAll: ", err)
   888  					continue
   889  				}
   890  
   891  				if !bytes.Equal(dst, src) {
   892  					report("", fmt.Errorf("bytes differ after round-tripping"))
   893  					continue
   894  				}
   895  			}
   896  		}
   897  	}
   898  }
   899  
   900  func TestBestSpeedShiftOffsets(t *testing.T) {
   901  	// Test if shiftoffsets properly preserves matches and resets out-of-range matches
   902  	// seen in https://github.com/golang/go/issues/4142
   903  	enc := newDeflateFast()
   904  
   905  	// testData may not generate internal matches.
   906  	testData := make([]byte, 32)
   907  	rng := rand.New(rand.NewSource(0))
   908  	for i := range testData {
   909  		testData[i] = byte(rng.Uint32())
   910  	}
   911  
   912  	// Encode the testdata with clean state.
   913  	// Second part should pick up matches from the first block.
   914  	wantFirstTokens := len(enc.encode(nil, testData))
   915  	wantSecondTokens := len(enc.encode(nil, testData))
   916  
   917  	if wantFirstTokens <= wantSecondTokens {
   918  		t.Fatalf("test needs matches between inputs to be generated")
   919  	}
   920  	// Forward the current indicator to before wraparound.
   921  	enc.cur = bufferReset - int32(len(testData))
   922  
   923  	// Part 1 before wrap, should match clean state.
   924  	got := len(enc.encode(nil, testData))
   925  	if wantFirstTokens != got {
   926  		t.Errorf("got %d, want %d tokens", got, wantFirstTokens)
   927  	}
   928  
   929  	// Verify we are about to wrap.
   930  	if enc.cur != bufferReset {
   931  		t.Errorf("got %d, want e.cur to be at bufferReset (%d)", enc.cur, bufferReset)
   932  	}
   933  
   934  	// Part 2 should match clean state as well even if wrapped.
   935  	got = len(enc.encode(nil, testData))
   936  	if wantSecondTokens != got {
   937  		t.Errorf("got %d, want %d token", got, wantSecondTokens)
   938  	}
   939  
   940  	// Verify that we wrapped.
   941  	if enc.cur >= bufferReset {
   942  		t.Errorf("want e.cur to be < bufferReset (%d), got %d", bufferReset, enc.cur)
   943  	}
   944  
   945  	// Forward the current buffer, leaving the matches at the bottom.
   946  	enc.cur = bufferReset
   947  	enc.shiftOffsets()
   948  
   949  	// Ensure that no matches were picked up.
   950  	got = len(enc.encode(nil, testData))
   951  	if wantFirstTokens != got {
   952  		t.Errorf("got %d, want %d tokens", got, wantFirstTokens)
   953  	}
   954  }
   955  
   956  func TestMaxStackSize(t *testing.T) {
   957  	// This test must not run in parallel with other tests as debug.SetMaxStack
   958  	// affects all goroutines.
   959  	n := debug.SetMaxStack(1 << 16)
   960  	defer debug.SetMaxStack(n)
   961  
   962  	var wg sync.WaitGroup
   963  	defer wg.Wait()
   964  
   965  	b := make([]byte, 1<<20)
   966  	for level := HuffmanOnly; level <= BestCompression; level++ {
   967  		// Run in separate goroutine to increase probability of stack regrowth.
   968  		wg.Add(1)
   969  		go func(level int) {
   970  			defer wg.Done()
   971  			zw, err := NewWriter(io.Discard, level)
   972  			if err != nil {
   973  				t.Errorf("level %d, NewWriter() = %v, want nil", level, err)
   974  			}
   975  			if n, err := zw.Write(b); n != len(b) || err != nil {
   976  				t.Errorf("level %d, Write() = (%d, %v), want (%d, nil)", level, n, err, len(b))
   977  			}
   978  			if err := zw.Close(); err != nil {
   979  				t.Errorf("level %d, Close() = %v, want nil", level, err)
   980  			}
   981  			zw.Reset(io.Discard)
   982  		}(level)
   983  	}
   984  }
   985  

View as plain text