fse_predefined.go raw
1 // Copyright 2019+ Klaus Post. All rights reserved.
2 // License information can be found in the LICENSE file.
3 // Based on work by Yann Collet, released under BSD License.
4
5 package zstd
6
7 import (
8 "fmt"
9 "math"
10 "sync"
11 )
12
13 var (
14 // fsePredef are the predefined fse tables as defined here:
15 // https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#default-distributions
16 // These values are already transformed.
17 fsePredef [3]fseDecoder
18
19 // fsePredefEnc are the predefined encoder based on fse tables as defined here:
20 // https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#default-distributions
21 // These values are already transformed.
22 fsePredefEnc [3]fseEncoder
23
24 // symbolTableX contain the transformations needed for each type as defined in
25 // https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#the-codes-for-literals-lengths-match-lengths-and-offsets
26 symbolTableX [3][]baseOffset
27
28 // maxTableSymbol is the biggest supported symbol for each table type
29 // https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#the-codes-for-literals-lengths-match-lengths-and-offsets
30 maxTableSymbol = [3]uint8{tableLiteralLengths: maxLiteralLengthSymbol, tableOffsets: maxOffsetLengthSymbol, tableMatchLengths: maxMatchLengthSymbol}
31
32 // bitTables is the bits table for each table.
33 bitTables = [3][]byte{tableLiteralLengths: llBitsTable[:], tableOffsets: nil, tableMatchLengths: mlBitsTable[:]}
34 )
35
36 type tableIndex uint8
37
38 const (
39 // indexes for fsePredef and symbolTableX
40 tableLiteralLengths tableIndex = 0
41 tableOffsets tableIndex = 1
42 tableMatchLengths tableIndex = 2
43
44 maxLiteralLengthSymbol = 35
45 maxOffsetLengthSymbol = 30
46 maxMatchLengthSymbol = 52
47 )
48
49 // baseOffset is used for calculating transformations.
50 type baseOffset struct {
51 baseLine uint32
52 addBits uint8
53 }
54
55 // fillBase will precalculate base offsets with the given bit distributions.
56 func fillBase(dst []baseOffset, base uint32, bits ...uint8) {
57 if len(bits) != len(dst) {
58 panic(fmt.Sprintf("len(dst) (%d) != len(bits) (%d)", len(dst), len(bits)))
59 }
60 for i, bit := range bits {
61 if base > math.MaxInt32 {
62 panic("invalid decoding table, base overflows int32")
63 }
64
65 dst[i] = baseOffset{
66 baseLine: base,
67 addBits: bit,
68 }
69 base += 1 << bit
70 }
71 }
72
73 var predef sync.Once
74
75 func initPredefined() {
76 predef.Do(func() {
77 // Literals length codes
78 tmp := make([]baseOffset, 36)
79 for i := range tmp[:16] {
80 tmp[i] = baseOffset{
81 baseLine: uint32(i),
82 addBits: 0,
83 }
84 }
85 fillBase(tmp[16:], 16, 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
86 symbolTableX[tableLiteralLengths] = tmp
87
88 // Match length codes
89 tmp = make([]baseOffset, 53)
90 for i := range tmp[:32] {
91 tmp[i] = baseOffset{
92 // The transformation adds the 3 length.
93 baseLine: uint32(i) + 3,
94 addBits: 0,
95 }
96 }
97 fillBase(tmp[32:], 35, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
98 symbolTableX[tableMatchLengths] = tmp
99
100 // Offset codes
101 tmp = make([]baseOffset, maxOffsetBits+1)
102 tmp[1] = baseOffset{
103 baseLine: 1,
104 addBits: 1,
105 }
106 fillBase(tmp[2:], 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
107 symbolTableX[tableOffsets] = tmp
108
109 // Fill predefined tables and transform them.
110 // https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#default-distributions
111 for i := range fsePredef[:] {
112 f := &fsePredef[i]
113 switch tableIndex(i) {
114 case tableLiteralLengths:
115 // https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L243
116 f.actualTableLog = 6
117 copy(f.norm[:], []int16{4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
118 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
119 -1, -1, -1, -1})
120 f.symbolLen = 36
121 case tableOffsets:
122 // https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L281
123 f.actualTableLog = 5
124 copy(f.norm[:], []int16{
125 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
126 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1})
127 f.symbolLen = 29
128 case tableMatchLengths:
129 //https://github.com/facebook/zstd/blob/ededcfca57366461021c922720878c81a5854a0a/lib/decompress/zstd_decompress_block.c#L304
130 f.actualTableLog = 6
131 copy(f.norm[:], []int16{
132 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
133 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
134 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1,
135 -1, -1, -1, -1, -1})
136 f.symbolLen = 53
137 }
138 if err := f.buildDtable(); err != nil {
139 panic(fmt.Errorf("building table %v: %v", tableIndex(i), err))
140 }
141 if err := f.transform(symbolTableX[i]); err != nil {
142 panic(fmt.Errorf("building table %v: %v", tableIndex(i), err))
143 }
144 f.preDefined = true
145
146 // Create encoder as well
147 enc := &fsePredefEnc[i]
148 copy(enc.norm[:], f.norm[:])
149 enc.symbolLen = f.symbolLen
150 enc.actualTableLog = f.actualTableLog
151 if err := enc.buildCTable(); err != nil {
152 panic(fmt.Errorf("building encoding table %v: %v", tableIndex(i), err))
153 }
154 enc.setBits(bitTables[i])
155 enc.preDefined = true
156 }
157 })
158 }
159