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