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
5package zstd
6
7import (
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.
14var 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.
22var 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.
29var 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.
40func 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		test := test
72		t.Run(test.name, func(t *testing.T) {
73			var r Reader
74			table := make([]fseEntry, 1<<test.tableBits)
75			if err := r.buildFSE(0, test.distribution, table, test.tableBits); err != nil {
76				t.Fatal(err)
77			}
78
79			baselineTable := make([]fseBaselineEntry, len(table))
80			if err := test.toBaseline(&r, 0, table, baselineTable); err != nil {
81				t.Fatal(err)
82			}
83
84			if !slices.Equal(baselineTable, test.predef) {
85				t.Errorf("got %v, want %v", baselineTable, test.predef)
86			}
87		})
88	}
89}
90