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
9package flate
10
11import (
12	"bytes"
13	"encoding/hex"
14	"io"
15	"io/ioutil"
16	"strings"
17	"testing"
18)
19
20// The following test should not panic.
21func 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.
32func 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.
42func 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
54func 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
71func 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
83func 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
264func 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.
283func 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