fse_test.go

     1  // Copyright 2023 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  package zstd
     6  
     7  import (
     8  	"slices"
     9  	"testing"
    10  )
    11  
    12  // literalPredefinedDistribution is the predefined distribution table
    13  // for literal lengths. RFC 3.1.1.3.2.2.1.
    14  var literalPredefinedDistribution = []int16{
    15  	4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
    16  	2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
    17  	-1, -1, -1, -1,
    18  }
    19  
    20  // offsetPredefinedDistribution is the predefined distribution table
    21  // for offsets. RFC 3.1.1.3.2.2.3.
    22  var offsetPredefinedDistribution = []int16{
    23  	1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
    24  	1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1,
    25  }
    26  
    27  // matchPredefinedDistribution is the predefined distribution table
    28  // for match lengths. RFC 3.1.1.3.2.2.2.
    29  var matchPredefinedDistribution = []int16{
    30  	1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
    31  	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    32  	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1,
    33  	-1, -1, -1, -1, -1,
    34  }
    35  
    36  // TestPredefinedTables verifies that we can generate the predefined
    37  // literal/offset/match tables from the input data in RFC 8878.
    38  // This serves as a test of the predefined tables, and also of buildFSE
    39  // and the functions that make baseline FSE tables.
    40  func TestPredefinedTables(t *testing.T) {
    41  	tests := []struct {
    42  		name         string
    43  		distribution []int16
    44  		tableBits    int
    45  		toBaseline   func(*Reader, int, []fseEntry, []fseBaselineEntry) error
    46  		predef       []fseBaselineEntry
    47  	}{
    48  		{
    49  			name:         "literal",
    50  			distribution: literalPredefinedDistribution,
    51  			tableBits:    6,
    52  			toBaseline:   (*Reader).makeLiteralBaselineFSE,
    53  			predef:       predefinedLiteralTable[:],
    54  		},
    55  		{
    56  			name:         "offset",
    57  			distribution: offsetPredefinedDistribution,
    58  			tableBits:    5,
    59  			toBaseline:   (*Reader).makeOffsetBaselineFSE,
    60  			predef:       predefinedOffsetTable[:],
    61  		},
    62  		{
    63  			name:         "match",
    64  			distribution: matchPredefinedDistribution,
    65  			tableBits:    6,
    66  			toBaseline:   (*Reader).makeMatchBaselineFSE,
    67  			predef:       predefinedMatchTable[:],
    68  		},
    69  	}
    70  	for _, test := range tests {
    71  		t.Run(test.name, func(t *testing.T) {
    72  			var r Reader
    73  			table := make([]fseEntry, 1<<test.tableBits)
    74  			if err := r.buildFSE(0, test.distribution, table, test.tableBits); err != nil {
    75  				t.Fatal(err)
    76  			}
    77  
    78  			baselineTable := make([]fseBaselineEntry, len(table))
    79  			if err := test.toBaseline(&r, 0, table, baselineTable); err != nil {
    80  				t.Fatal(err)
    81  			}
    82  
    83  			if !slices.Equal(baselineTable, test.predef) {
    84  				t.Errorf("got %v, want %v", baselineTable, test.predef)
    85  			}
    86  		})
    87  	}
    88  }
    89
View as plain text