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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
// Copyright 2023 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package zstd
import (
"io"
"math/bits"
)
// maxHuffmanBits is the largest possible Huffman table bits.
const maxHuffmanBits = 11
// readHuff reads Huffman table from data starting at off into table.
// Each entry in a Huffman table is a pair of bytes.
// The high byte is the encoded value. The low byte is the number
// of bits used to encode that value. We index into the table
// with a value of size tableBits. A value that requires fewer bits
// appear in the table multiple times.
// This returns the number of bits in the Huffman table and the new offset.
// RFC 4.2.1.
func (r *Reader) readHuff(data block, off int, table []uint16) (tableBits, roff int, err error) {
if off >= len(data) {
return 0, 0, r.makeEOFError(off)
}
hdr := data[off]
off++
var weights [256]uint8
var count int
if hdr < 128 {
// The table is compressed using an FSE. RFC 4.2.1.2.
if len(r.fseScratch) < 1<<6 {
r.fseScratch = make([]fseEntry, 1<<6)
}
fseBits, noff, err := r.readFSE(data, off, 255, 6, r.fseScratch)
if err != nil {
return 0, 0, err
}
fseTable := r.fseScratch
if off+int(hdr) > len(data) {
return 0, 0, r.makeEOFError(off)
}
rbr, err := r.makeReverseBitReader(data, off+int(hdr)-1, noff)
if err != nil {
return 0, 0, err
}
state1, err := rbr.val(uint8(fseBits))
if err != nil {
return 0, 0, err
}
state2, err := rbr.val(uint8(fseBits))
if err != nil {
return 0, 0, err
}
// There are two independent FSE streams, tracked by
// state1 and state2. We decode them alternately.
for {
pt := &fseTable[state1]
if !rbr.fetch(pt.bits) {
if count >= 254 {
return 0, 0, rbr.makeError("Huffman count overflow")
}
weights[count] = pt.sym
weights[count+1] = fseTable[state2].sym
count += 2
break
}
v, err := rbr.val(pt.bits)
if err != nil {
return 0, 0, err
}
state1 = uint32(pt.base) + v
if count >= 255 {
return 0, 0, rbr.makeError("Huffman count overflow")
}
weights[count] = pt.sym
count++
pt = &fseTable[state2]
if !rbr.fetch(pt.bits) {
if count >= 254 {
return 0, 0, rbr.makeError("Huffman count overflow")
}
weights[count] = pt.sym
weights[count+1] = fseTable[state1].sym
count += 2
break
}
v, err = rbr.val(pt.bits)
if err != nil {
return 0, 0, err
}
state2 = uint32(pt.base) + v
if count >= 255 {
return 0, 0, rbr.makeError("Huffman count overflow")
}
weights[count] = pt.sym
count++
}
off += int(hdr)
} else {
// The table is not compressed. Each weight is 4 bits.
count = int(hdr) - 127
if off+((count+1)/2) >= len(data) {
return 0, 0, io.ErrUnexpectedEOF
}
for i := 0; i < count; i += 2 {
b := data[off]
off++
weights[i] = b >> 4
weights[i+1] = b & 0xf
}
}
// RFC 4.2.1.3.
var weightMark [13]uint32
weightMask := uint32(0)
for _, w := range weights[:count] {
if w > 12 {
return 0, 0, r.makeError(off, "Huffman weight overflow")
}
weightMark[w]++
if w > 0 {
weightMask += 1 << (w - 1)
}
}
if weightMask == 0 {
return 0, 0, r.makeError(off, "bad Huffman weights")
}
tableBits = 32 - bits.LeadingZeros32(weightMask)
if tableBits > maxHuffmanBits {
return 0, 0, r.makeError(off, "bad Huffman weights")
}
if len(table) < 1<<tableBits {
return 0, 0, r.makeError(off, "Huffman table too small")
}
// Work out the last weight value, which is omitted because
// the weights must sum to a power of two.
left := (uint32(1) << tableBits) - weightMask
if left == 0 {
return 0, 0, r.makeError(off, "bad Huffman weights")
}
highBit := 31 - bits.LeadingZeros32(left)
if uint32(1)<<highBit != left {
return 0, 0, r.makeError(off, "bad Huffman weights")
}
if count >= 256 {
return 0, 0, r.makeError(off, "Huffman weight overflow")
}
weights[count] = uint8(highBit + 1)
count++
weightMark[highBit+1]++
if weightMark[1] < 2 || weightMark[1]&1 != 0 {
return 0, 0, r.makeError(off, "bad Huffman weights")
}
// Change weightMark from a count of weights to the index of
// the first symbol for that weight. We shift the indexes to
// also store how many we have seen so far,
next := uint32(0)
for i := 0; i < tableBits; i++ {
cur := next
next += weightMark[i+1] << i
weightMark[i+1] = cur
}
for i, w := range weights[:count] {
if w == 0 {
continue
}
length := uint32(1) << (w - 1)
tval := uint16(i)<<8 | (uint16(tableBits) + 1 - uint16(w))
start := weightMark[w]
for j := uint32(0); j < length; j++ {
table[start+j] = tval
}
weightMark[w] += length
}
return tableBits, off, nil
}
|
