source: code/trunk/vendor/github.com/andybalholm/brotli/entropy_encode.go@ 145

Last change on this file since 145 was 145, checked in by Izuru Yakumo, 22 months ago

Updated the Makefile and vendored depedencies

Signed-off-by: Izuru Yakumo <yakumo.izuru@…>
File size: 13.7 KB
Line 
1package brotli
2
3import "math"
4
5/* Copyright 2010 Google Inc. All Rights Reserved.
6
7 Distributed under MIT license.
8 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
9*/
10
11/* Entropy encoding (Huffman) utilities. */
12
13/* A node of a Huffman tree. */
14type huffmanTree struct {
15 total_count_ uint32
16 index_left_ int16
17 index_right_or_value_ int16
18}
19
20func initHuffmanTree(self *huffmanTree, count uint32, left int16, right int16) {
21 self.total_count_ = count
22 self.index_left_ = left
23 self.index_right_or_value_ = right
24}
25
26/* Input size optimized Shell sort. */
27type huffmanTreeComparator func(huffmanTree, huffmanTree) bool
28
29var sortHuffmanTreeItems_gaps = []uint{132, 57, 23, 10, 4, 1}
30
31func sortHuffmanTreeItems(items []huffmanTree, n uint, comparator huffmanTreeComparator) {
32 if n < 13 {
33 /* Insertion sort. */
34 var i uint
35 for i = 1; i < n; i++ {
36 var tmp huffmanTree = items[i]
37 var k uint = i
38 var j uint = i - 1
39 for comparator(tmp, items[j]) {
40 items[k] = items[j]
41 k = j
42 if j == 0 {
43 break
44 }
45 j--
46 }
47
48 items[k] = tmp
49 }
50
51 return
52 } else {
53 var g int
54 if n < 57 {
55 g = 2
56 } else {
57 g = 0
58 }
59 for ; g < 6; g++ {
60 var gap uint = sortHuffmanTreeItems_gaps[g]
61 var i uint
62 for i = gap; i < n; i++ {
63 var j uint = i
64 var tmp huffmanTree = items[i]
65 for ; j >= gap && comparator(tmp, items[j-gap]); j -= gap {
66 items[j] = items[j-gap]
67 }
68
69 items[j] = tmp
70 }
71 }
72 }
73}
74
75/* Returns 1 if assignment of depths succeeded, otherwise 0. */
76func setDepth(p0 int, pool []huffmanTree, depth []byte, max_depth int) bool {
77 var stack [16]int
78 var level int = 0
79 var p int = p0
80 assert(max_depth <= 15)
81 stack[0] = -1
82 for {
83 if pool[p].index_left_ >= 0 {
84 level++
85 if level > max_depth {
86 return false
87 }
88 stack[level] = int(pool[p].index_right_or_value_)
89 p = int(pool[p].index_left_)
90 continue
91 } else {
92 depth[pool[p].index_right_or_value_] = byte(level)
93 }
94
95 for level >= 0 && stack[level] == -1 {
96 level--
97 }
98 if level < 0 {
99 return true
100 }
101 p = stack[level]
102 stack[level] = -1
103 }
104}
105
106/* Sort the root nodes, least popular first. */
107func sortHuffmanTree(v0 huffmanTree, v1 huffmanTree) bool {
108 if v0.total_count_ != v1.total_count_ {
109 return v0.total_count_ < v1.total_count_
110 }
111
112 return v0.index_right_or_value_ > v1.index_right_or_value_
113}
114
115/* This function will create a Huffman tree.
116
117 The catch here is that the tree cannot be arbitrarily deep.
118 Brotli specifies a maximum depth of 15 bits for "code trees"
119 and 7 bits for "code length code trees."
120
121 count_limit is the value that is to be faked as the minimum value
122 and this minimum value is raised until the tree matches the
123 maximum length requirement.
124
125 This algorithm is not of excellent performance for very long data blocks,
126 especially when population counts are longer than 2**tree_limit, but
127 we are not planning to use this with extremely long blocks.
128
129 See http://en.wikipedia.org/wiki/Huffman_coding */
130func createHuffmanTree(data []uint32, length uint, tree_limit int, tree []huffmanTree, depth []byte) {
131 var count_limit uint32
132 var sentinel huffmanTree
133 initHuffmanTree(&sentinel, math.MaxUint32, -1, -1)
134
135 /* For block sizes below 64 kB, we never need to do a second iteration
136 of this loop. Probably all of our block sizes will be smaller than
137 that, so this loop is mostly of academic interest. If we actually
138 would need this, we would be better off with the Katajainen algorithm. */
139 for count_limit = 1; ; count_limit *= 2 {
140 var n uint = 0
141 var i uint
142 var j uint
143 var k uint
144 for i = length; i != 0; {
145 i--
146 if data[i] != 0 {
147 var count uint32 = brotli_max_uint32_t(data[i], count_limit)
148 initHuffmanTree(&tree[n], count, -1, int16(i))
149 n++
150 }
151 }
152
153 if n == 1 {
154 depth[tree[0].index_right_or_value_] = 1 /* Only one element. */
155 break
156 }
157
158 sortHuffmanTreeItems(tree, n, huffmanTreeComparator(sortHuffmanTree))
159
160 /* The nodes are:
161 [0, n): the sorted leaf nodes that we start with.
162 [n]: we add a sentinel here.
163 [n + 1, 2n): new parent nodes are added here, starting from
164 (n+1). These are naturally in ascending order.
165 [2n]: we add a sentinel at the end as well.
166 There will be (2n+1) elements at the end. */
167 tree[n] = sentinel
168
169 tree[n+1] = sentinel
170
171 i = 0 /* Points to the next leaf node. */
172 j = n + 1 /* Points to the next non-leaf node. */
173 for k = n - 1; k != 0; k-- {
174 var left uint
175 var right uint
176 if tree[i].total_count_ <= tree[j].total_count_ {
177 left = i
178 i++
179 } else {
180 left = j
181 j++
182 }
183
184 if tree[i].total_count_ <= tree[j].total_count_ {
185 right = i
186 i++
187 } else {
188 right = j
189 j++
190 }
191 {
192 /* The sentinel node becomes the parent node. */
193 var j_end uint = 2*n - k
194 tree[j_end].total_count_ = tree[left].total_count_ + tree[right].total_count_
195 tree[j_end].index_left_ = int16(left)
196 tree[j_end].index_right_or_value_ = int16(right)
197
198 /* Add back the last sentinel node. */
199 tree[j_end+1] = sentinel
200 }
201 }
202
203 if setDepth(int(2*n-1), tree[0:], depth, tree_limit) {
204 /* We need to pack the Huffman tree in tree_limit bits. If this was not
205 successful, add fake entities to the lowest values and retry. */
206 break
207 }
208 }
209}
210
211func reverse(v []byte, start uint, end uint) {
212 end--
213 for start < end {
214 var tmp byte = v[start]
215 v[start] = v[end]
216 v[end] = tmp
217 start++
218 end--
219 }
220}
221
222func writeHuffmanTreeRepetitions(previous_value byte, value byte, repetitions uint, tree_size *uint, tree []byte, extra_bits_data []byte) {
223 assert(repetitions > 0)
224 if previous_value != value {
225 tree[*tree_size] = value
226 extra_bits_data[*tree_size] = 0
227 (*tree_size)++
228 repetitions--
229 }
230
231 if repetitions == 7 {
232 tree[*tree_size] = value
233 extra_bits_data[*tree_size] = 0
234 (*tree_size)++
235 repetitions--
236 }
237
238 if repetitions < 3 {
239 var i uint
240 for i = 0; i < repetitions; i++ {
241 tree[*tree_size] = value
242 extra_bits_data[*tree_size] = 0
243 (*tree_size)++
244 }
245 } else {
246 var start uint = *tree_size
247 repetitions -= 3
248 for {
249 tree[*tree_size] = repeatPreviousCodeLength
250 extra_bits_data[*tree_size] = byte(repetitions & 0x3)
251 (*tree_size)++
252 repetitions >>= 2
253 if repetitions == 0 {
254 break
255 }
256
257 repetitions--
258 }
259
260 reverse(tree, start, *tree_size)
261 reverse(extra_bits_data, start, *tree_size)
262 }
263}
264
265func writeHuffmanTreeRepetitionsZeros(repetitions uint, tree_size *uint, tree []byte, extra_bits_data []byte) {
266 if repetitions == 11 {
267 tree[*tree_size] = 0
268 extra_bits_data[*tree_size] = 0
269 (*tree_size)++
270 repetitions--
271 }
272
273 if repetitions < 3 {
274 var i uint
275 for i = 0; i < repetitions; i++ {
276 tree[*tree_size] = 0
277 extra_bits_data[*tree_size] = 0
278 (*tree_size)++
279 }
280 } else {
281 var start uint = *tree_size
282 repetitions -= 3
283 for {
284 tree[*tree_size] = repeatZeroCodeLength
285 extra_bits_data[*tree_size] = byte(repetitions & 0x7)
286 (*tree_size)++
287 repetitions >>= 3
288 if repetitions == 0 {
289 break
290 }
291
292 repetitions--
293 }
294
295 reverse(tree, start, *tree_size)
296 reverse(extra_bits_data, start, *tree_size)
297 }
298}
299
300/* Change the population counts in a way that the consequent
301 Huffman tree compression, especially its RLE-part will be more
302 likely to compress this data more efficiently.
303
304 length contains the size of the histogram.
305 counts contains the population counts.
306 good_for_rle is a buffer of at least length size */
307func optimizeHuffmanCountsForRLE(length uint, counts []uint32, good_for_rle []byte) {
308 var nonzero_count uint = 0
309 var stride uint
310 var limit uint
311 var sum uint
312 var streak_limit uint = 1240
313 var i uint
314 /* Let's make the Huffman code more compatible with RLE encoding. */
315 for i = 0; i < length; i++ {
316 if counts[i] != 0 {
317 nonzero_count++
318 }
319 }
320
321 if nonzero_count < 16 {
322 return
323 }
324
325 for length != 0 && counts[length-1] == 0 {
326 length--
327 }
328
329 if length == 0 {
330 return /* All zeros. */
331 }
332
333 /* Now counts[0..length - 1] does not have trailing zeros. */
334 {
335 var nonzeros uint = 0
336 var smallest_nonzero uint32 = 1 << 30
337 for i = 0; i < length; i++ {
338 if counts[i] != 0 {
339 nonzeros++
340 if smallest_nonzero > counts[i] {
341 smallest_nonzero = counts[i]
342 }
343 }
344 }
345
346 if nonzeros < 5 {
347 /* Small histogram will model it well. */
348 return
349 }
350
351 if smallest_nonzero < 4 {
352 var zeros uint = length - nonzeros
353 if zeros < 6 {
354 for i = 1; i < length-1; i++ {
355 if counts[i-1] != 0 && counts[i] == 0 && counts[i+1] != 0 {
356 counts[i] = 1
357 }
358 }
359 }
360 }
361
362 if nonzeros < 28 {
363 return
364 }
365 }
366
367 /* 2) Let's mark all population counts that already can be encoded
368 with an RLE code. */
369 for i := 0; i < int(length); i++ {
370 good_for_rle[i] = 0
371 }
372 {
373 var symbol uint32 = counts[0]
374 /* Let's not spoil any of the existing good RLE codes.
375 Mark any seq of 0's that is longer as 5 as a good_for_rle.
376 Mark any seq of non-0's that is longer as 7 as a good_for_rle. */
377
378 var step uint = 0
379 for i = 0; i <= length; i++ {
380 if i == length || counts[i] != symbol {
381 if (symbol == 0 && step >= 5) || (symbol != 0 && step >= 7) {
382 var k uint
383 for k = 0; k < step; k++ {
384 good_for_rle[i-k-1] = 1
385 }
386 }
387
388 step = 1
389 if i != length {
390 symbol = counts[i]
391 }
392 } else {
393 step++
394 }
395 }
396 }
397
398 /* 3) Let's replace those population counts that lead to more RLE codes.
399 Math here is in 24.8 fixed point representation. */
400 stride = 0
401
402 limit = uint(256*(counts[0]+counts[1]+counts[2])/3 + 420)
403 sum = 0
404 for i = 0; i <= length; i++ {
405 if i == length || good_for_rle[i] != 0 || (i != 0 && good_for_rle[i-1] != 0) || (256*counts[i]-uint32(limit)+uint32(streak_limit)) >= uint32(2*streak_limit) {
406 if stride >= 4 || (stride >= 3 && sum == 0) {
407 var k uint
408 var count uint = (sum + stride/2) / stride
409 /* The stride must end, collapse what we have, if we have enough (4). */
410 if count == 0 {
411 count = 1
412 }
413
414 if sum == 0 {
415 /* Don't make an all zeros stride to be upgraded to ones. */
416 count = 0
417 }
418
419 for k = 0; k < stride; k++ {
420 /* We don't want to change value at counts[i],
421 that is already belonging to the next stride. Thus - 1. */
422 counts[i-k-1] = uint32(count)
423 }
424 }
425
426 stride = 0
427 sum = 0
428 if i < length-2 {
429 /* All interesting strides have a count of at least 4, */
430 /* at least when non-zeros. */
431 limit = uint(256*(counts[i]+counts[i+1]+counts[i+2])/3 + 420)
432 } else if i < length {
433 limit = uint(256 * counts[i])
434 } else {
435 limit = 0
436 }
437 }
438
439 stride++
440 if i != length {
441 sum += uint(counts[i])
442 if stride >= 4 {
443 limit = (256*sum + stride/2) / stride
444 }
445
446 if stride == 4 {
447 limit += 120
448 }
449 }
450 }
451}
452
453func decideOverRLEUse(depth []byte, length uint, use_rle_for_non_zero *bool, use_rle_for_zero *bool) {
454 var total_reps_zero uint = 0
455 var total_reps_non_zero uint = 0
456 var count_reps_zero uint = 1
457 var count_reps_non_zero uint = 1
458 var i uint
459 for i = 0; i < length; {
460 var value byte = depth[i]
461 var reps uint = 1
462 var k uint
463 for k = i + 1; k < length && depth[k] == value; k++ {
464 reps++
465 }
466
467 if reps >= 3 && value == 0 {
468 total_reps_zero += reps
469 count_reps_zero++
470 }
471
472 if reps >= 4 && value != 0 {
473 total_reps_non_zero += reps
474 count_reps_non_zero++
475 }
476
477 i += reps
478 }
479
480 *use_rle_for_non_zero = total_reps_non_zero > count_reps_non_zero*2
481 *use_rle_for_zero = total_reps_zero > count_reps_zero*2
482}
483
484/* Write a Huffman tree from bit depths into the bit-stream representation
485 of a Huffman tree. The generated Huffman tree is to be compressed once
486 more using a Huffman tree */
487func writeHuffmanTree(depth []byte, length uint, tree_size *uint, tree []byte, extra_bits_data []byte) {
488 var previous_value byte = initialRepeatedCodeLength
489 var i uint
490 var use_rle_for_non_zero bool = false
491 var use_rle_for_zero bool = false
492 var new_length uint = length
493 /* Throw away trailing zeros. */
494 for i = 0; i < length; i++ {
495 if depth[length-i-1] == 0 {
496 new_length--
497 } else {
498 break
499 }
500 }
501
502 /* First gather statistics on if it is a good idea to do RLE. */
503 if length > 50 {
504 /* Find RLE coding for longer codes.
505 Shorter codes seem not to benefit from RLE. */
506 decideOverRLEUse(depth, new_length, &use_rle_for_non_zero, &use_rle_for_zero)
507 }
508
509 /* Actual RLE coding. */
510 for i = 0; i < new_length; {
511 var value byte = depth[i]
512 var reps uint = 1
513 if (value != 0 && use_rle_for_non_zero) || (value == 0 && use_rle_for_zero) {
514 var k uint
515 for k = i + 1; k < new_length && depth[k] == value; k++ {
516 reps++
517 }
518 }
519
520 if value == 0 {
521 writeHuffmanTreeRepetitionsZeros(reps, tree_size, tree, extra_bits_data)
522 } else {
523 writeHuffmanTreeRepetitions(previous_value, value, reps, tree_size, tree, extra_bits_data)
524 previous_value = value
525 }
526
527 i += reps
528 }
529}
530
531var reverseBits_kLut = [16]uint{
532 0x00,
533 0x08,
534 0x04,
535 0x0C,
536 0x02,
537 0x0A,
538 0x06,
539 0x0E,
540 0x01,
541 0x09,
542 0x05,
543 0x0D,
544 0x03,
545 0x0B,
546 0x07,
547 0x0F,
548}
549
550func reverseBits(num_bits uint, bits uint16) uint16 {
551 var retval uint = reverseBits_kLut[bits&0x0F]
552 var i uint
553 for i = 4; i < num_bits; i += 4 {
554 retval <<= 4
555 bits = uint16(bits >> 4)
556 retval |= reverseBits_kLut[bits&0x0F]
557 }
558
559 retval >>= ((0 - num_bits) & 0x03)
560 return uint16(retval)
561}
562
563/* 0..15 are values for bits */
564const maxHuffmanBits = 16
565
566/* Get the actual bit values for a tree of bit depths. */
567func convertBitDepthsToSymbols(depth []byte, len uint, bits []uint16) {
568 var bl_count = [maxHuffmanBits]uint16{0}
569 var next_code [maxHuffmanBits]uint16
570 var i uint
571 /* In Brotli, all bit depths are [1..15]
572 0 bit depth means that the symbol does not exist. */
573
574 var code int = 0
575 for i = 0; i < len; i++ {
576 bl_count[depth[i]]++
577 }
578
579 bl_count[0] = 0
580 next_code[0] = 0
581 for i = 1; i < maxHuffmanBits; i++ {
582 code = (code + int(bl_count[i-1])) << 1
583 next_code[i] = uint16(code)
584 }
585
586 for i = 0; i < len; i++ {
587 if depth[i] != 0 {
588 bits[i] = reverseBits(uint(depth[i]), next_code[depth[i]])
589 next_code[depth[i]]++
590 }
591 }
592}
Note: See TracBrowser for help on using the repository browser.