flate_test.go

Documentation: github.com/klauspost/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  	"archive/zip"
    13  	"bytes"
    14  	"compress/flate"
    15  	"encoding/hex"
    16  	"fmt"
    17  	"io"
    18  	"os"
    19  	"testing"
    20  )
    21  
    22  // The following test should not panic.
    23  func TestIssue5915(t *testing.T) {
    24  	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0, 5, 5, 6,
    25  		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    26  		0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 8, 6, 0, 11, 0, 8, 0, 6, 6, 10, 8}
    27  	var h huffmanDecoder
    28  	if h.init(bits) {
    29  		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
    30  	}
    31  }
    32  
    33  // The following test should not panic.
    34  func TestIssue5962(t *testing.T) {
    35  	bits := []int{4, 0, 0, 6, 4, 3, 2, 3, 3, 4, 4, 5, 0, 0, 0, 0,
    36  		5, 5, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11}
    37  	var h huffmanDecoder
    38  	if h.init(bits) {
    39  		t.Fatalf("Given sequence of bits is bad, and should not succeed.")
    40  	}
    41  }
    42  
    43  // The following test should not panic.
    44  func TestIssue6255(t *testing.T) {
    45  	bits1 := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 11}
    46  	bits2 := []int{11, 13}
    47  	var h huffmanDecoder
    48  	if !h.init(bits1) {
    49  		t.Fatalf("Given sequence of bits is good and should succeed.")
    50  	}
    51  	if h.init(bits2) {
    52  		t.Fatalf("Given sequence of bits is bad and should not succeed.")
    53  	}
    54  }
    55  
    56  func TestInvalidEncoding(t *testing.T) {
    57  	// Initialize Huffman decoder to recognize "0".
    58  	var h huffmanDecoder
    59  	if !h.init([]int{1}) {
    60  		t.Fatal("Failed to initialize Huffman decoder")
    61  	}
    62  
    63  	// Initialize decompressor with invalid Huffman coding.
    64  	var f decompressor
    65  	f.r = bytes.NewReader([]byte{0xff})
    66  
    67  	_, err := f.huffSym(&h)
    68  	if err == nil {
    69  		t.Fatal("Should have rejected invalid bit sequence")
    70  	}
    71  }
    72  
    73  func TestRegressions(t *testing.T) {
    74  	// Test fuzzer regressions
    75  	data, err := os.ReadFile("testdata/regression.zip")
    76  	if err != nil {
    77  		t.Fatal(err)
    78  	}
    79  	zr, err := zip.NewReader(bytes.NewReader(data), int64(len(data)))
    80  	if err != nil {
    81  		t.Fatal(err)
    82  	}
    83  	for _, tt := range zr.File {
    84  		data, err := tt.Open()
    85  		if err != nil {
    86  			t.Fatal(err)
    87  		}
    88  		data1, err := io.ReadAll(data)
    89  		if err != nil {
    90  			t.Fatal(err)
    91  		}
    92  		t.Run(tt.Name, func(t *testing.T) {
    93  			if testing.Short() && len(data1) > 10000 {
    94  				t.SkipNow()
    95  			}
    96  			for level := 0; level <= 9; level++ {
    97  				t.Run(fmt.Sprint(tt.Name+"-level", 1), func(t *testing.T) {
    98  					buf := new(bytes.Buffer)
    99  					fw, err := NewWriter(buf, level)
   100  					if err != nil {
   101  						t.Error(err)
   102  					}
   103  					n, err := fw.Write(data1)
   104  					if n != len(data1) {
   105  						t.Error("short write")
   106  					}
   107  					if err != nil {
   108  						t.Error(err)
   109  					}
   110  					err = fw.Close()
   111  					if err != nil {
   112  						t.Error(err)
   113  					}
   114  					fr1 := NewReader(buf)
   115  					data2, err := io.ReadAll(fr1)
   116  					if err != nil {
   117  						t.Error(err)
   118  					}
   119  					if !bytes.Equal(data1, data2) {
   120  						t.Error("not equal")
   121  					}
   122  					// Do it again...
   123  					buf.Reset()
   124  					fw.Reset(buf)
   125  					n, err = fw.Write(data1)
   126  					if n != len(data1) {
   127  						t.Error("short write")
   128  					}
   129  					if err != nil {
   130  						t.Error(err)
   131  					}
   132  					err = fw.Close()
   133  					if err != nil {
   134  						t.Error(err)
   135  					}
   136  					fr1 = flate.NewReader(buf)
   137  					data2, err = io.ReadAll(fr1)
   138  					if err != nil {
   139  						t.Error(err)
   140  					}
   141  					if !bytes.Equal(data1, data2) {
   142  						t.Error("not equal")
   143  					}
   144  				})
   145  			}
   146  			t.Run(tt.Name+"stateless", func(t *testing.T) {
   147  				// Split into two and use history...
   148  				buf := new(bytes.Buffer)
   149  				err = StatelessDeflate(buf, data1[:len(data1)/2], false, nil)
   150  				if err != nil {
   151  					t.Error(err)
   152  				}
   153  
   154  				// Use top half as dictionary...
   155  				dict := data1[:len(data1)/2]
   156  				err = StatelessDeflate(buf, data1[len(data1)/2:], true, dict)
   157  				if err != nil {
   158  					t.Error(err)
   159  				}
   160  				t.Log(buf.Len())
   161  				fr1 := NewReader(buf)
   162  				data2, err := io.ReadAll(fr1)
   163  				if err != nil {
   164  					t.Error(err)
   165  				}
   166  				if !bytes.Equal(data1, data2) {
   167  					//fmt.Printf("want:%x\ngot: %x\n", data1, data2)
   168  					t.Error("not equal")
   169  				}
   170  			})
   171  		})
   172  	}
   173  }
   174  
   175  func TestInvalidBits(t *testing.T) {
   176  	oversubscribed := []int{1, 2, 3, 4, 4, 5}
   177  	incomplete := []int{1, 2, 4, 4}
   178  	var h huffmanDecoder
   179  	if h.init(oversubscribed) {
   180  		t.Fatal("Should reject oversubscribed bit-length set")
   181  	}
   182  	if h.init(incomplete) {
   183  		t.Fatal("Should reject incomplete bit-length set")
   184  	}
   185  }
   186  
   187  func TestStreams(t *testing.T) {
   188  	// To verify any of these hexstrings as valid or invalid flate streams
   189  	// according to the C zlib library, you can use the Python wrapper library:
   190  	// >>> hex_string = "010100feff11"
   191  	// >>> import zlib
   192  	// >>> zlib.decompress(hex_string.decode("hex"), -15) # Negative means raw DEFLATE
   193  	// '\x11'
   194  
   195  	testCases := []struct {
   196  		desc   string // Description of the stream
   197  		stream string // Hexstring of the input DEFLATE stream
   198  		want   string // Expected result. Use "fail" to expect failure
   199  	}{{
   200  		"degenerate HCLenTree",
   201  		"05e0010000000000100000000000000000000000000000000000000000000000" +
   202  			"00000000000000000004",
   203  		"fail",
   204  	}, {
   205  		"complete HCLenTree, empty HLitTree, empty HDistTree",
   206  		"05e0010400000000000000000000000000000000000000000000000000000000" +
   207  			"00000000000000000010",
   208  		"fail",
   209  	}, {
   210  		"empty HCLenTree",
   211  		"05e0010000000000000000000000000000000000000000000000000000000000" +
   212  			"00000000000000000010",
   213  		"fail",
   214  	}, {
   215  		"complete HCLenTree, complete HLitTree, empty HDistTree, use missing HDist symbol",
   216  		"000100feff000de0010400000000100000000000000000000000000000000000" +
   217  			"0000000000000000000000000000002c",
   218  		"fail",
   219  	}, {
   220  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use missing HDist symbol",
   221  		"000100feff000de0010000000000000000000000000000000000000000000000" +
   222  			"00000000000000000610000000004070",
   223  		"fail",
   224  	}, {
   225  		"complete HCLenTree, empty HLitTree, empty HDistTree",
   226  		"05e0010400000000100400000000000000000000000000000000000000000000" +
   227  			"0000000000000000000000000008",
   228  		"fail",
   229  	}, {
   230  		"complete HCLenTree, empty HLitTree, degenerate HDistTree",
   231  		"05e0010400000000100400000000000000000000000000000000000000000000" +
   232  			"0000000000000000000800000008",
   233  		"fail",
   234  	}, {
   235  		"complete HCLenTree, degenerate HLitTree, degenerate HDistTree, use missing HLit symbol",
   236  		"05e0010400000000100000000000000000000000000000000000000000000000" +
   237  			"0000000000000000001c",
   238  		"fail",
   239  	}, {
   240  		"complete HCLenTree, complete HLitTree, too large HDistTree",
   241  		"edff870500000000200400000000000000000000000000000000000000000000" +
   242  			"000000000000000000080000000000000004",
   243  		"fail",
   244  	}, {
   245  		"complete HCLenTree, complete HLitTree, empty HDistTree, excessive repeater code",
   246  		"edfd870500000000200400000000000000000000000000000000000000000000" +
   247  			"000000000000000000e8b100",
   248  		"fail",
   249  	}, {
   250  		"complete HCLenTree, complete HLitTree, empty HDistTree of normal length 30",
   251  		"05fd01240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   252  			"ffffffffffffffffff07000000fe01",
   253  		"",
   254  	}, {
   255  		"complete HCLenTree, complete HLitTree, empty HDistTree of excessive length 31",
   256  		"05fe01240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   257  			"ffffffffffffffffff07000000fc03",
   258  		"fail",
   259  	}, {
   260  		"complete HCLenTree, over-subscribed HLitTree, empty HDistTree",
   261  		"05e001240000000000fcffffffffffffffffffffffffffffffffffffffffffff" +
   262  			"ffffffffffffffffff07f00f",
   263  		"fail",
   264  	}, {
   265  		"complete HCLenTree, under-subscribed HLitTree, empty HDistTree",
   266  		"05e001240000000000fcffffffffffffffffffffffffffffffffffffffffffff" +
   267  			"fffffffffcffffffff07f00f",
   268  		"fail",
   269  	}, {
   270  		"complete HCLenTree, complete HLitTree with single code, empty HDistTree",
   271  		"05e001240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   272  			"ffffffffffffffffff07f00f",
   273  		"01",
   274  	}, {
   275  		"complete HCLenTree, complete HLitTree with multiple codes, empty HDistTree",
   276  		"05e301240000000000f8ffffffffffffffffffffffffffffffffffffffffffff" +
   277  			"ffffffffffffffffff07807f",
   278  		"01",
   279  	}, {
   280  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HDist symbol",
   281  		"000100feff000de0010400000000100000000000000000000000000000000000" +
   282  			"0000000000000000000000000000003c",
   283  		"00000000",
   284  	}, {
   285  		"complete HCLenTree, degenerate HLitTree, degenerate HDistTree",
   286  		"05e0010400000000100000000000000000000000000000000000000000000000" +
   287  			"0000000000000000000c",
   288  		"",
   289  	}, {
   290  		"complete HCLenTree, degenerate HLitTree, empty HDistTree",
   291  		"05e0010400000000100000000000000000000000000000000000000000000000" +
   292  			"00000000000000000004",
   293  		"",
   294  	}, {
   295  		"complete HCLenTree, complete HLitTree, empty HDistTree, spanning repeater code",
   296  		"edfd870500000000200400000000000000000000000000000000000000000000" +
   297  			"000000000000000000e8b000",
   298  		"",
   299  	}, {
   300  		"complete HCLenTree with length codes, complete HLitTree, empty HDistTree",
   301  		"ede0010400000000100000000000000000000000000000000000000000000000" +
   302  			"0000000000000000000400004000",
   303  		"",
   304  	}, {
   305  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HLit symbol 284 with count 31",
   306  		"000100feff00ede0010400000000100000000000000000000000000000000000" +
   307  			"000000000000000000000000000000040000407f00",
   308  		"0000000000000000000000000000000000000000000000000000000000000000" +
   309  			"0000000000000000000000000000000000000000000000000000000000000000" +
   310  			"0000000000000000000000000000000000000000000000000000000000000000" +
   311  			"0000000000000000000000000000000000000000000000000000000000000000" +
   312  			"0000000000000000000000000000000000000000000000000000000000000000" +
   313  			"0000000000000000000000000000000000000000000000000000000000000000" +
   314  			"0000000000000000000000000000000000000000000000000000000000000000" +
   315  			"0000000000000000000000000000000000000000000000000000000000000000" +
   316  			"000000",
   317  	}, {
   318  		"complete HCLenTree, complete HLitTree, degenerate HDistTree, use valid HLit and HDist symbols",
   319  		"0cc2010d00000082b0ac4aff0eb07d27060000ffff",
   320  		"616263616263",
   321  	}, {
   322  		"fixed block, use reserved symbol 287",
   323  		"33180700",
   324  		"fail",
   325  	}, {
   326  		"raw block",
   327  		"010100feff11",
   328  		"11",
   329  	}, {
   330  		"issue 10426 - over-subscribed HCLenTree causes a hang",
   331  		"344c4a4e494d4b070000ff2e2eff2e2e2e2e2eff",
   332  		"fail",
   333  	}, {
   334  		"issue 11030 - empty HDistTree unexpectedly leads to error",
   335  		"05c0070600000080400fff37a0ca",
   336  		"",
   337  	}, {
   338  		"issue 11033 - empty HDistTree unexpectedly leads to error",
   339  		"050fb109c020cca5d017dcbca044881ee1034ec149c8980bbc413c2ab35be9dc" +
   340  			"b1473449922449922411202306ee97b0383a521b4ffdcf3217f9f7d3adb701",
   341  		"3130303634342068652e706870005d05355f7ed957ff084a90925d19e3ebc6d0" +
   342  			"c6d7",
   343  	}}
   344  
   345  	for i, tc := range testCases {
   346  		data, err := hex.DecodeString(tc.stream)
   347  		if err != nil {
   348  			t.Fatal(err)
   349  		}
   350  		data, err = io.ReadAll(NewReader(bytes.NewReader(data)))
   351  		if tc.want == "fail" {
   352  			if err == nil {
   353  				t.Errorf("#%d (%s): got nil error, want non-nil", i, tc.desc)
   354  			}
   355  		} else {
   356  			if err != nil {
   357  				t.Errorf("#%d (%s): %v", i, tc.desc, err)
   358  				continue
   359  			}
   360  			if got := hex.EncodeToString(data); got != tc.want {
   361  				t.Errorf("#%d (%s):\ngot  %q\nwant %q", i, tc.desc, got, tc.want)
   362  			}
   363  
   364  		}
   365  	}
   366  }
   367
View as plain text