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	"strings"
16	"testing"
17)
18
19// The following test should not panic.
20func 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.
31func 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.
41func 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
53func 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
70func 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
82func 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
263func 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.
282func 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