...
1
2
3
4
5 package flate
6
7 import (
8 "math"
9 "math/bits"
10 "sort"
11 )
12
13
14 type hcode struct {
15 code, len uint16
16 }
17
18 type huffmanEncoder struct {
19 codes []hcode
20 freqcache []literalNode
21 bitCount [17]int32
22 lns byLiteral
23 lfs byFreq
24 }
25
26 type literalNode struct {
27 literal uint16
28 freq int32
29 }
30
31
32 type levelInfo struct {
33
34 level int32
35
36
37 lastFreq int32
38
39
40 nextCharFreq int32
41
42
43
44 nextPairFreq int32
45
46
47
48 needed int32
49 }
50
51
52 func (h *hcode) set(code uint16, length uint16) {
53 h.len = length
54 h.code = code
55 }
56
57 func maxNode() literalNode { return literalNode{math.MaxUint16, math.MaxInt32} }
58
59 func newHuffmanEncoder(size int) *huffmanEncoder {
60 return &huffmanEncoder{codes: make([]hcode, size)}
61 }
62
63
64 func generateFixedLiteralEncoding() *huffmanEncoder {
65 h := newHuffmanEncoder(maxNumLit)
66 codes := h.codes
67 var ch uint16
68 for ch = 0; ch < maxNumLit; ch++ {
69 var bits uint16
70 var size uint16
71 switch {
72 case ch < 144:
73
74 bits = ch + 48
75 size = 8
76 break
77 case ch < 256:
78
79 bits = ch + 400 - 144
80 size = 9
81 break
82 case ch < 280:
83
84 bits = ch - 256
85 size = 7
86 break
87 default:
88
89 bits = ch + 192 - 280
90 size = 8
91 }
92 codes[ch] = hcode{code: reverseBits(bits, byte(size)), len: size}
93 }
94 return h
95 }
96
97 func generateFixedOffsetEncoding() *huffmanEncoder {
98 h := newHuffmanEncoder(30)
99 codes := h.codes
100 for ch := range codes {
101 codes[ch] = hcode{code: reverseBits(uint16(ch), 5), len: 5}
102 }
103 return h
104 }
105
106 var fixedLiteralEncoding *huffmanEncoder = generateFixedLiteralEncoding()
107 var fixedOffsetEncoding *huffmanEncoder = generateFixedOffsetEncoding()
108
109 func (h *huffmanEncoder) bitLength(freq []int32) int {
110 var total int
111 for i, f := range freq {
112 if f != 0 {
113 total += int(f) * int(h.codes[i].len)
114 }
115 }
116 return total
117 }
118
119 const maxBitsLimit = 16
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135 func (h *huffmanEncoder) bitCounts(list []literalNode, maxBits int32) []int32 {
136 if maxBits >= maxBitsLimit {
137 panic("flate: maxBits too large")
138 }
139 n := int32(len(list))
140 list = list[0 : n+1]
141 list[n] = maxNode()
142
143
144
145 if maxBits > n-1 {
146 maxBits = n - 1
147 }
148
149
150
151
152
153 var levels [maxBitsLimit]levelInfo
154
155
156
157
158 var leafCounts [maxBitsLimit][maxBitsLimit]int32
159
160 for level := int32(1); level <= maxBits; level++ {
161
162
163 levels[level] = levelInfo{
164 level: level,
165 lastFreq: list[1].freq,
166 nextCharFreq: list[2].freq,
167 nextPairFreq: list[0].freq + list[1].freq,
168 }
169 leafCounts[level][level] = 2
170 if level == 1 {
171 levels[level].nextPairFreq = math.MaxInt32
172 }
173 }
174
175
176 levels[maxBits].needed = 2*n - 4
177
178 level := maxBits
179 for {
180 l := &levels[level]
181 if l.nextPairFreq == math.MaxInt32 && l.nextCharFreq == math.MaxInt32 {
182
183
184
185
186 l.needed = 0
187 levels[level+1].nextPairFreq = math.MaxInt32
188 level++
189 continue
190 }
191
192 prevFreq := l.lastFreq
193 if l.nextCharFreq < l.nextPairFreq {
194
195 n := leafCounts[level][level] + 1
196 l.lastFreq = l.nextCharFreq
197
198 leafCounts[level][level] = n
199 l.nextCharFreq = list[n].freq
200 } else {
201
202
203
204 l.lastFreq = l.nextPairFreq
205
206 copy(leafCounts[level][:level], leafCounts[level-1][:level])
207 levels[l.level-1].needed = 2
208 }
209
210 if l.needed--; l.needed == 0 {
211
212
213
214
215 if l.level == maxBits {
216
217 break
218 }
219 levels[l.level+1].nextPairFreq = prevFreq + l.lastFreq
220 level++
221 } else {
222
223 for levels[level-1].needed > 0 {
224 level--
225 }
226 }
227 }
228
229
230
231 if leafCounts[maxBits][maxBits] != n {
232 panic("leafCounts[maxBits][maxBits] != n")
233 }
234
235 bitCount := h.bitCount[:maxBits+1]
236 bits := 1
237 counts := &leafCounts[maxBits]
238 for level := maxBits; level > 0; level-- {
239
240
241 bitCount[bits] = counts[level] - counts[level-1]
242 bits++
243 }
244 return bitCount
245 }
246
247
248
249 func (h *huffmanEncoder) assignEncodingAndSize(bitCount []int32, list []literalNode) {
250 code := uint16(0)
251 for n, bits := range bitCount {
252 code <<= 1
253 if n == 0 || bits == 0 {
254 continue
255 }
256
257
258
259
260 chunk := list[len(list)-int(bits):]
261
262 h.lns.sort(chunk)
263 for _, node := range chunk {
264 h.codes[node.literal] = hcode{code: reverseBits(code, uint8(n)), len: uint16(n)}
265 code++
266 }
267 list = list[0 : len(list)-int(bits)]
268 }
269 }
270
271
272
273
274
275 func (h *huffmanEncoder) generate(freq []int32, maxBits int32) {
276 if h.freqcache == nil {
277
278
279
280 h.freqcache = make([]literalNode, maxNumLit+1)
281 }
282 list := h.freqcache[:len(freq)+1]
283
284 count := 0
285
286 for i, f := range freq {
287 if f != 0 {
288 list[count] = literalNode{uint16(i), f}
289 count++
290 } else {
291 h.codes[i].len = 0
292 }
293 }
294
295 list = list[:count]
296 if count <= 2 {
297
298
299 for i, node := range list {
300
301 h.codes[node.literal].set(uint16(i), 1)
302 }
303 return
304 }
305 h.lfs.sort(list)
306
307
308 bitCount := h.bitCounts(list, maxBits)
309
310 h.assignEncodingAndSize(bitCount, list)
311 }
312
313 type byLiteral []literalNode
314
315 func (s *byLiteral) sort(a []literalNode) {
316 *s = byLiteral(a)
317 sort.Sort(s)
318 }
319
320 func (s byLiteral) Len() int { return len(s) }
321
322 func (s byLiteral) Less(i, j int) bool {
323 return s[i].literal < s[j].literal
324 }
325
326 func (s byLiteral) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
327
328 type byFreq []literalNode
329
330 func (s *byFreq) sort(a []literalNode) {
331 *s = byFreq(a)
332 sort.Sort(s)
333 }
334
335 func (s byFreq) Len() int { return len(s) }
336
337 func (s byFreq) Less(i, j int) bool {
338 if s[i].freq == s[j].freq {
339 return s[i].literal < s[j].literal
340 }
341 return s[i].freq < s[j].freq
342 }
343
344 func (s byFreq) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
345
346 func reverseBits(number uint16, bitLength byte) uint16 {
347 return bits.Reverse16(number << (16 - bitLength))
348 }
349
View as plain text