...
Run Format

Source file src/compress/flate/flate_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  // This test tests some internals of the flate package.
     6  // The tests in package compress/gzip serve as the
     7  // end-to-end test of the decompressor.
     8  
     9  package flate
    10  
    11  import (
    12  	"bytes"
    13  	"encoding/hex"
    14  	"io"
    15  	"io/ioutil"
    16  	"strings"
    17  	"testing"
    18  )
    19  
    20  // The following test should not panic.
    21  func TestIssue5915(t *testing.T) {
    22  	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0, 5, 5, 6,
    23  		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    24  		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 6, 0, 11, 0, 8, 0, 6, 6, 10, 8}
    25  	var h huffmanDecoder
    26  	if h.init(bits) {
    27  		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
    28  	}
    29  }
    30  
    31  // The following test should not panic.
    32  func TestIssue5962(t *testing.T) {
    33  	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0,
    34  		5, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11}
    35  	var h huffmanDecoder
    36  	if h.init(bits) {
    37  		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
    38  	}
    39  }
    40  
    41  // The following test should not panic.
    42  func TestIssue6255(t *testing.T) {
    43  	bits1 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 11}
    44  	bits2 := []int{11, 13}
    45  	var h huffmanDecoder
    46  	if !h.init(bits1) {
    47  		t.Fatalf("Given sequence of bits is good and should succeed.")
    48  	}
    49  	if h.init(bits2) {
    50  		t.Fatalf("Given sequence of bits is bad and should not succeed.")
    51  	}
    52  }
    53  
    54  func TestInvalidEncoding(t *testing.T) {
    55  	// Initialize Huffman decoder to recognize "0".
    56  	var h huffmanDecoder
    57  	if !h.init([]int{1}) {
    58  		t.Fatal("Failed to initialize Huffman decoder")
    59  	}
    60  
    61  	// Initialize decompressor with invalid Huffman coding.
    62  	var f decompressor
    63  	f.r = bytes.NewReader([]byte{0xff})
    64  
    65  	_, err := f.huffSym(&h)
    66  	if err == nil {
    67  		t.Fatal("Should have rejected invalid bit sequence")
    68  	}
    69  }
    70  
    71  func TestInvalidBits(t *testing.T) {
    72  	oversubscribed := []int{1, 2, 3, 4, 4, 5}
    73  	incomplete := []int{1, 2, 4, 4}
    74  	var h huffmanDecoder
    75  	if h.init(oversubscribed) {
    76  		t.Fatal("Should reject oversubscribed bit-length set")
    77  	}
    78  	if h.init(incomplete) {
    79  		t.Fatal("Should reject incomplete bit-length set")
    80  	}
    81  }
    82  
    83  func TestStreams(t *testing.T) {
    84  	// To verify any of these hexstrings as valid or invalid flate streams
    85  	// according to the C zlib library, you can use the Python wrapper library:
    86  	// >>> hex_string = "010100feff11"
    87  	// >>> import zlib
    88  	// >>> zlib.decompress(hex_string.decode("hex"), -15) # Negative means raw DEFLATE
    89  	// '\x11'
    90  
    91  	testCases := []struct {
    92  		desc   string // Description of the stream
    93  		stream string // Hexstring of the input DEFLATE stream
    94  		want   string // Expected result. Use "fail" to expect failure
    95  	}{{
    96  		"degenerate HCLenTree",
    97  		"05e0010000000000100000000000000000000000000000000000000000000000" +
    98  			"00000000000000000004",
    99  		"fail",
   100  	}, {
   101  		"complete HCLenTree, empty HLitTree, empty HDistTree",
   102  		"05e0010400000000000000000000000000000000000000000000000000000000" +
   103  			"00000000000000000010",
   104  		"fail",
   105  	}, {
   106  		"empty HCLenTree",
   107  		"05e0010000000000000000000000000000000000000000000000000000000000" +
   108  			"00000000000000000010",
   109  		"fail",
   110  	}, {
   111  		"complete HCLenTree, complete HLitTree, empty HDistTree, use missing HDist symbol",
   112  		"000100feff000de0010400000000100000000000000000000000000000000000" +
   113  			"0000000000000000000000000000002c",
   114  		"fail",
   115  	}, {
   116  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use missing HDist symbol",
   117  		"000100feff000de0010000000000000000000000000000000000000000000000" +
   118  			"00000000000000000610000000004070",
   119  		"fail",
   120  	}, {
   121  		"complete HCLenTree, empty HLitTree, empty HDistTree",
   122  		"05e0010400000000100400000000000000000000000000000000000000000000" +
   123  			"0000000000000000000000000008",
   124  		"fail",
   125  	}, {
   126  		"complete HCLenTree, empty HLitTree, degenerate HDistTree",
   127  		"05e0010400000000100400000000000000000000000000000000000000000000" +
   128  			"0000000000000000000800000008",
   129  		"fail",
   130  	}, {
   131  		"complete HCLenTree, degenerate HLitTree, degenerate HDistTree, use missing HLit symbol",
   132  		"05e0010400000000100000000000000000000000000000000000000000000000" +
   133  			"0000000000000000001c",
   134  		"fail",
   135  	}, {
   136  		"complete HCLenTree, complete HLitTree, too large HDistTree",
   137  		"edff870500000000200400000000000000000000000000000000000000000000" +
   138  			"000000000000000000080000000000000004",
   139  		"fail",
   140  	}, {
   141  		"complete HCLenTree, complete HLitTree, empty HDistTree, excessive repeater code",
   142  		"edfd870500000000200400000000000000000000000000000000000000000000" +
   143  			"000000000000000000e8b100",
   144  		"fail",
   145  	}, {
   146  		"complete HCLenTree, complete HLitTree, empty HDistTree of normal length 30",
   147  		"05fd01240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   148  			"ffffffffffffffffff07000000fe01",
   149  		"",
   150  	}, {
   151  		"complete HCLenTree, complete HLitTree, empty HDistTree of excessive length 31",
   152  		"05fe01240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   153  			"ffffffffffffffffff07000000fc03",
   154  		"fail",
   155  	}, {
   156  		"complete HCLenTree, over-subscribed HLitTree, empty HDistTree",
   157  		"05e001240000000000fcffffffffffffffffffffffffffffffffffffffffffff" +
   158  			"ffffffffffffffffff07f00f",
   159  		"fail",
   160  	}, {
   161  		"complete HCLenTree, under-subscribed HLitTree, empty HDistTree",
   162  		"05e001240000000000fcffffffffffffffffffffffffffffffffffffffffffff" +
   163  			"fffffffffcffffffff07f00f",
   164  		"fail",
   165  	}, {
   166  		"complete HCLenTree, complete HLitTree with single code, empty HDistTree",
   167  		"05e001240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   168  			"ffffffffffffffffff07f00f",
   169  		"01",
   170  	}, {
   171  		"complete HCLenTree, complete HLitTree with multiple codes, empty HDistTree",
   172  		"05e301240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   173  			"ffffffffffffffffff07807f",
   174  		"01",
   175  	}, {
   176  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HDist symbol",
   177  		"000100feff000de0010400000000100000000000000000000000000000000000" +
   178  			"0000000000000000000000000000003c",
   179  		"00000000",
   180  	}, {
   181  		"complete HCLenTree, degenerate HLitTree, degenerate HDistTree",
   182  		"05e0010400000000100000000000000000000000000000000000000000000000" +
   183  			"0000000000000000000c",
   184  		"",
   185  	}, {
   186  		"complete HCLenTree, degenerate HLitTree, empty HDistTree",
   187  		"05e0010400000000100000000000000000000000000000000000000000000000" +
   188  			"00000000000000000004",
   189  		"",
   190  	}, {
   191  		"complete HCLenTree, complete HLitTree, empty HDistTree, spanning repeater code",
   192  		"edfd870500000000200400000000000000000000000000000000000000000000" +
   193  			"000000000000000000e8b000",
   194  		"",
   195  	}, {
   196  		"complete HCLenTree with length codes, complete HLitTree, empty HDistTree",
   197  		"ede0010400000000100000000000000000000000000000000000000000000000" +
   198  			"0000000000000000000400004000",
   199  		"",
   200  	}, {
   201  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HLit symbol 284 with count 31",
   202  		"000100feff00ede0010400000000100000000000000000000000000000000000" +
   203  			"000000000000000000000000000000040000407f00",
   204  		"0000000000000000000000000000000000000000000000000000000000000000" +
   205  			"0000000000000000000000000000000000000000000000000000000000000000" +
   206  			"0000000000000000000000000000000000000000000000000000000000000000" +
   207  			"0000000000000000000000000000000000000000000000000000000000000000" +
   208  			"0000000000000000000000000000000000000000000000000000000000000000" +
   209  			"0000000000000000000000000000000000000000000000000000000000000000" +
   210  			"0000000000000000000000000000000000000000000000000000000000000000" +
   211  			"0000000000000000000000000000000000000000000000000000000000000000" +
   212  			"000000",
   213  	}, {
   214  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HLit and HDist symbols",
   215  		"0cc2010d00000082b0ac4aff0eb07d27060000ffff",
   216  		"616263616263",
   217  	}, {
   218  		"fixed block, use reserved symbol 287",
   219  		"33180700",
   220  		"fail",
   221  	}, {
   222  		"raw block",
   223  		"010100feff11",
   224  		"11",
   225  	}, {
   226  		"issue 10426 - over-subscribed HCLenTree causes a hang",
   227  		"344c4a4e494d4b070000ff2e2eff2e2e2e2e2eff",
   228  		"fail",
   229  	}, {
   230  		"issue 11030 - empty HDistTree unexpectedly leads to error",
   231  		"05c0070600000080400fff37a0ca",
   232  		"",
   233  	}, {
   234  		"issue 11033 - empty HDistTree unexpectedly leads to error",
   235  		"050fb109c020cca5d017dcbca044881ee1034ec149c8980bbc413c2ab35be9dc" +
   236  			"b1473449922449922411202306ee97b0383a521b4ffdcf3217f9f7d3adb701",
   237  		"3130303634342068652e706870005d05355f7ed957ff084a90925d19e3ebc6d0" +
   238  			"c6d7",
   239  	}}
   240  
   241  	for i, tc := range testCases {
   242  		data, err := hex.DecodeString(tc.stream)
   243  		if err != nil {
   244  			t.Fatal(err)
   245  		}
   246  		data, err = ioutil.ReadAll(NewReader(bytes.NewReader(data)))
   247  		if tc.want == "fail" {
   248  			if err == nil {
   249  				t.Errorf("#%d (%s): got nil error, want non-nil", i, tc.desc)
   250  			}
   251  		} else {
   252  			if err != nil {
   253  				t.Errorf("#%d (%s): %v", i, tc.desc, err)
   254  				continue
   255  			}
   256  			if got := hex.EncodeToString(data); got != tc.want {
   257  				t.Errorf("#%d (%s):\ngot  %q\nwant %q", i, tc.desc, got, tc.want)
   258  			}
   259  
   260  		}
   261  	}
   262  }
   263  
   264  func TestTruncatedStreams(t *testing.T) {
   265  	const data = "\x00\f\x00\xf3\xffhello, world\x01\x00\x00\xff\xff"
   266  
   267  	for i := 0; i < len(data)-1; i++ {
   268  		r := NewReader(strings.NewReader(data[:i]))
   269  		_, err := io.Copy(ioutil.Discard, r)
   270  		if err != io.ErrUnexpectedEOF {
   271  			t.Errorf("io.Copy(%d) on truncated stream: got %v, want %v", i, err, io.ErrUnexpectedEOF)
   272  		}
   273  	}
   274  }
   275  
   276  // Verify that flate.Reader.Read returns (n, io.EOF) instead
   277  // of (n, nil) + (0, io.EOF) when possible.
   278  //
   279  // This helps net/http.Transport reuse HTTP/1 connections more
   280  // aggressively.
   281  //
   282  // See https://github.com/google/go-github/pull/317 for background.
   283  func TestReaderEarlyEOF(t *testing.T) {
   284  	t.Parallel()
   285  	testSizes := []int{
   286  		1, 2, 3, 4, 5, 6, 7, 8,
   287  		100, 1000, 10000, 100000,
   288  		128, 1024, 16384, 131072,
   289  
   290  		// Testing multiples of windowSize triggers the case
   291  		// where Read will fail to return an early io.EOF.
   292  		windowSize * 1, windowSize * 2, windowSize * 3,
   293  	}
   294  
   295  	var maxSize int
   296  	for _, n := range testSizes {
   297  		if maxSize < n {
   298  			maxSize = n
   299  		}
   300  	}
   301  
   302  	readBuf := make([]byte, 40)
   303  	data := make([]byte, maxSize)
   304  	for i := range data {
   305  		data[i] = byte(i)
   306  	}
   307  
   308  	for _, sz := range testSizes {
   309  		if testing.Short() && sz > windowSize {
   310  			continue
   311  		}
   312  		for _, flush := range []bool{true, false} {
   313  			earlyEOF := true // Do we expect early io.EOF?
   314  
   315  			var buf bytes.Buffer
   316  			w, _ := NewWriter(&buf, 5)
   317  			w.Write(data[:sz])
   318  			if flush {
   319  				// If a Flush occurs after all the actual data, the flushing
   320  				// semantics dictate that we will observe a (0, io.EOF) since
   321  				// Read must return data before it knows that the stream ended.
   322  				w.Flush()
   323  				earlyEOF = false
   324  			}
   325  			w.Close()
   326  
   327  			r := NewReader(&buf)
   328  			for {
   329  				n, err := r.Read(readBuf)
   330  				if err == io.EOF {
   331  					// If the availWrite == windowSize, then that means that the
   332  					// previous Read returned because the write buffer was full
   333  					// and it just so happened that the stream had no more data.
   334  					// This situation is rare, but unavoidable.
   335  					if r.(*decompressor).dict.availWrite() == windowSize {
   336  						earlyEOF = false
   337  					}
   338  
   339  					if n == 0 && earlyEOF {
   340  						t.Errorf("On size:%d flush:%v, Read() = (0, io.EOF), want (n, io.EOF)", sz, flush)
   341  					}
   342  					if n != 0 && !earlyEOF {
   343  						t.Errorf("On size:%d flush:%v, Read() = (%d, io.EOF), want (0, io.EOF)", sz, flush, n)
   344  					}
   345  					break
   346  				}
   347  				if err != nil {
   348  					t.Fatal(err)
   349  				}
   350  			}
   351  		}
   352  	}
   353  }
   354  

View as plain text