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/ioutil"
15	"testing"
16)
17
18// The following test should not panic.
19func TestIssue5915(t *testing.T) {
20	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0, 5, 5, 6,
21		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
22		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 6, 0, 11, 0, 8, 0, 6, 6, 10, 8}
23	var h huffmanDecoder
24	if h.init(bits) {
25		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
26	}
27}
28
29// The following test should not panic.
30func TestIssue5962(t *testing.T) {
31	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0,
32		5, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11}
33	var h huffmanDecoder
34	if h.init(bits) {
35		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
36	}
37}
38
39// The following test should not panic.
40func TestIssue6255(t *testing.T) {
41	bits1 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 11}
42	bits2 := []int{11, 13}
43	var h huffmanDecoder
44	if !h.init(bits1) {
45		t.Fatalf("Given sequence of bits is good and should succeed.")
46	}
47	if h.init(bits2) {
48		t.Fatalf("Given sequence of bits is bad and should not succeed.")
49	}
50}
51
52func TestInvalidEncoding(t *testing.T) {
53	// Initialize Huffman decoder to recognize "0".
54	var h huffmanDecoder
55	if !h.init([]int{1}) {
56		t.Fatal("Failed to initialize Huffman decoder")
57	}
58
59	// Initialize decompressor with invalid Huffman coding.
60	var f decompressor
61	f.r = bytes.NewReader([]byte{0xff})
62
63	_, err := f.huffSym(&h)
64	if err == nil {
65		t.Fatal("Should have rejected invalid bit sequence")
66	}
67}
68
69func TestInvalidBits(t *testing.T) {
70	oversubscribed := []int{1, 2, 3, 4, 4, 5}
71	incomplete := []int{1, 2, 4, 4}
72	var h huffmanDecoder
73	if h.init(oversubscribed) {
74		t.Fatal("Should reject oversubscribed bit-length set")
75	}
76	if h.init(incomplete) {
77		t.Fatal("Should reject incomplete bit-length set")
78	}
79}
80
81func TestStreams(t *testing.T) {
82	// To verify any of these hexstrings as valid or invalid flate streams
83	// according to the C zlib library, you can use the Python wrapper library:
84	// >>> hex_string = "010100feff11"
85	// >>> import zlib
86	// >>> zlib.decompress(hex_string.decode("hex"), -15) # Negative means raw DEFLATE
87	// '\x11'
88
89	testCases := []struct {
90		desc   string // Description of the stream
91		stream string // Hexstring of the input DEFLATE stream
92		want   string // Expected result. Use "fail" to expect failure
93	}{{
94		"degenerate HCLenTree",
95		"05e0010000000000100000000000000000000000000000000000000000000000" +
96			"00000000000000000004",
97		"fail",
98	}, {
99		"complete HCLenTree, empty HLitTree, empty HDistTree",
100		"05e0010400000000000000000000000000000000000000000000000000000000" +
101			"00000000000000000010",
102		"fail",
103	}, {
104		"empty HCLenTree",
105		"05e0010000000000000000000000000000000000000000000000000000000000" +
106			"00000000000000000010",
107		"fail",
108	}, {
109		"complete HCLenTree, complete HLitTree, empty HDistTree, use missing HDist symbol",
110		"000100feff000de0010400000000100000000000000000000000000000000000" +
111			"0000000000000000000000000000002c",
112		"fail",
113	}, {
114		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use missing HDist symbol",
115		"000100feff000de0010000000000000000000000000000000000000000000000" +
116			"00000000000000000610000000004070",
117		"fail",
118	}, {
119		"complete HCLenTree, empty HLitTree, empty HDistTree",
120		"05e0010400000000100400000000000000000000000000000000000000000000" +
121			"0000000000000000000000000008",
122		"fail",
123	}, {
124		"complete HCLenTree, empty HLitTree, degenerate HDistTree",
125		"05e0010400000000100400000000000000000000000000000000000000000000" +
126			"0000000000000000000800000008",
127		"fail",
128	}, {
129		"complete HCLenTree, degenerate HLitTree, degenerate HDistTree, use missing HLit symbol",
130		"05e0010400000000100000000000000000000000000000000000000000000000" +
131			"0000000000000000001c",
132		"fail",
133	}, {
134		"complete HCLenTree, complete HLitTree, too large HDistTree",
135		"edff870500000000200400000000000000000000000000000000000000000000" +
136			"000000000000000000080000000000000004",
137		"fail",
138	}, {
139		"complete HCLenTree, complete HLitTree, empty HDistTree, excessive repeater code",
140		"edfd870500000000200400000000000000000000000000000000000000000000" +
141			"000000000000000000e8b100",
142		"fail",
143	}, {
144		"complete HCLenTree, complete HLitTree, empty HDistTree of normal length 30",
145		"05fd01240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
146			"ffffffffffffffffff07000000fe01",
147		"",
148	}, {
149		"complete HCLenTree, complete HLitTree, empty HDistTree of excessive length 31",
150		"05fe01240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
151			"ffffffffffffffffff07000000fc03",
152		"fail",
153	}, {
154		"complete HCLenTree, over-subscribed HLitTree, empty HDistTree",
155		"05e001240000000000fcffffffffffffffffffffffffffffffffffffffffffff" +
156			"ffffffffffffffffff07f00f",
157		"fail",
158	}, {
159		"complete HCLenTree, under-subscribed HLitTree, empty HDistTree",
160		"05e001240000000000fcffffffffffffffffffffffffffffffffffffffffffff" +
161			"fffffffffcffffffff07f00f",
162		"fail",
163	}, {
164		"complete HCLenTree, complete HLitTree with single code, empty HDistTree",
165		"05e001240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
166			"ffffffffffffffffff07f00f",
167		"01",
168	}, {
169		"complete HCLenTree, complete HLitTree with multiple codes, empty HDistTree",
170		"05e301240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
171			"ffffffffffffffffff07807f",
172		"01",
173	}, {
174		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HDist symbol",
175		"000100feff000de0010400000000100000000000000000000000000000000000" +
176			"0000000000000000000000000000003c",
177		"00000000",
178	}, {
179		"complete HCLenTree, degenerate HLitTree, degenerate HDistTree",
180		"05e0010400000000100000000000000000000000000000000000000000000000" +
181			"0000000000000000000c",
182		"",
183	}, {
184		"complete HCLenTree, degenerate HLitTree, empty HDistTree",
185		"05e0010400000000100000000000000000000000000000000000000000000000" +
186			"00000000000000000004",
187		"",
188	}, {
189		"complete HCLenTree, complete HLitTree, empty HDistTree, spanning repeater code",
190		"edfd870500000000200400000000000000000000000000000000000000000000" +
191			"000000000000000000e8b000",
192		"",
193	}, {
194		"complete HCLenTree with length codes, complete HLitTree, empty HDistTree",
195		"ede0010400000000100000000000000000000000000000000000000000000000" +
196			"0000000000000000000400004000",
197		"",
198	}, {
199		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HLit symbol 284 with count 31",
200		"000100feff00ede0010400000000100000000000000000000000000000000000" +
201			"000000000000000000000000000000040000407f00",
202		"0000000000000000000000000000000000000000000000000000000000000000" +
203			"0000000000000000000000000000000000000000000000000000000000000000" +
204			"0000000000000000000000000000000000000000000000000000000000000000" +
205			"0000000000000000000000000000000000000000000000000000000000000000" +
206			"0000000000000000000000000000000000000000000000000000000000000000" +
207			"0000000000000000000000000000000000000000000000000000000000000000" +
208			"0000000000000000000000000000000000000000000000000000000000000000" +
209			"0000000000000000000000000000000000000000000000000000000000000000" +
210			"000000",
211	}, {
212		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HLit and HDist symbols",
213		"0cc2010d00000082b0ac4aff0eb07d27060000ffff",
214		"616263616263",
215	}, {
216		"fixed block, use reserved symbol 287",
217		"33180700",
218		"fail",
219	}, {
220		"raw block",
221		"010100feff11",
222		"11",
223	}, {
224		"issue 10426 - over-subscribed HCLenTree causes a hang",
225		"344c4a4e494d4b070000ff2e2eff2e2e2e2e2eff",
226		"fail",
227	}, {
228		"issue 11030 - empty HDistTree unexpectedly leads to error",
229		"05c0070600000080400fff37a0ca",
230		"",
231	}, {
232		"issue 11033 - empty HDistTree unexpectedly leads to error",
233		"050fb109c020cca5d017dcbca044881ee1034ec149c8980bbc413c2ab35be9dc" +
234			"b1473449922449922411202306ee97b0383a521b4ffdcf3217f9f7d3adb701",
235		"3130303634342068652e706870005d05355f7ed957ff084a90925d19e3ebc6d0" +
236			"c6d7",
237	}}
238
239	for i, tc := range testCases {
240		data, err := hex.DecodeString(tc.stream)
241		if err != nil {
242			t.Fatal(err)
243		}
244		data, err = ioutil.ReadAll(NewReader(bytes.NewReader(data)))
245		if tc.want == "fail" {
246			if err == nil {
247				t.Errorf("#%d (%s): got nil error, want non-nil", i, tc.desc)
248			}
249		} else {
250			if err != nil {
251				t.Errorf("#%d (%s): %v", i, tc.desc, err)
252				continue
253			}
254			if got := hex.EncodeToString(data); got != tc.want {
255				t.Errorf("#%d (%s):\ngot  %q\nwant %q", i, tc.desc, got, tc.want)
256			}
257
258		}
259	}
260}
261