1 /* Copyright 2010 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 /* Entropy encoding (Huffman) utilities. */
9 #include "./entropy_encode.h"
11 #include <string.h> /* memset */
13 #include "../common/constants.h"
14 #include "../common/types.h"
17 #if defined(__cplusplus) || defined(c_plusplus)
21 BROTLI_BOOL
BrotliSetDepth(
22 int p0
, HuffmanTree
* pool
, uint8_t* depth
, int max_depth
) {
26 assert(max_depth
<= 15);
29 if (pool
[p
].index_left_
>= 0) {
31 if (level
> max_depth
) return BROTLI_FALSE
;
32 stack
[level
] = pool
[p
].index_right_or_value_
;
33 p
= pool
[p
].index_left_
;
36 depth
[pool
[p
].index_right_or_value_
] = (uint8_t)level
;
38 while (level
>= 0 && stack
[level
] == -1) level
--;
39 if (level
< 0) return BROTLI_TRUE
;
45 /* Sort the root nodes, least popular first. */
46 static BROTLI_INLINE BROTLI_BOOL
SortHuffmanTree(
47 const HuffmanTree
* v0
, const HuffmanTree
* v1
) {
48 if (v0
->total_count_
!= v1
->total_count_
) {
49 return TO_BROTLI_BOOL(v0
->total_count_
< v1
->total_count_
);
51 return TO_BROTLI_BOOL(v0
->index_right_or_value_
> v1
->index_right_or_value_
);
54 /* This function will create a Huffman tree.
56 The catch here is that the tree cannot be arbitrarily deep.
57 Brotli specifies a maximum depth of 15 bits for "code trees"
58 and 7 bits for "code length code trees."
60 count_limit is the value that is to be faked as the minimum value
61 and this minimum value is raised until the tree matches the
62 maximum length requirement.
64 This algorithm is not of excellent performance for very long data blocks,
65 especially when population counts are longer than 2**tree_limit, but
66 we are not planning to use this with extremely long blocks.
68 See http://en.wikipedia.org/wiki/Huffman_coding */
69 void BrotliCreateHuffmanTree(const uint32_t *data
,
76 InitHuffmanTree(&sentinel
, BROTLI_UINT32_MAX
, -1, -1);
77 /* For block sizes below 64 kB, we never need to do a second iteration
78 of this loop. Probably all of our block sizes will be smaller than
79 that, so this loop is mostly of academic interest. If we actually
80 would need this, we would be better off with the Katajainen algorithm. */
81 for (count_limit
= 1; ; count_limit
*= 2) {
86 for (i
= length
; i
!= 0;) {
89 const uint32_t count
= BROTLI_MAX(uint32_t, data
[i
], count_limit
);
90 InitHuffmanTree(&tree
[n
++], count
, -1, (int16_t)i
);
95 depth
[tree
[0].index_right_or_value_
] = 1; /* Only one element. */
99 SortHuffmanTreeItems(tree
, n
, SortHuffmanTree
);
102 [0, n): the sorted leaf nodes that we start with.
103 [n]: we add a sentinel here.
104 [n + 1, 2n): new parent nodes are added here, starting from
105 (n+1). These are naturally in ascending order.
106 [2n]: we add a sentinel at the end as well.
107 There will be (2n+1) elements at the end. */
109 tree
[n
+ 1] = sentinel
;
111 i
= 0; /* Points to the next leaf node. */
112 j
= n
+ 1; /* Points to the next non-leaf node. */
113 for (k
= n
- 1; k
!= 0; --k
) {
115 if (tree
[i
].total_count_
<= tree
[j
].total_count_
) {
122 if (tree
[i
].total_count_
<= tree
[j
].total_count_
) {
131 /* The sentinel node becomes the parent node. */
132 size_t j_end
= 2 * n
- k
;
133 tree
[j_end
].total_count_
=
134 tree
[left
].total_count_
+ tree
[right
].total_count_
;
135 tree
[j_end
].index_left_
= (int16_t)left
;
136 tree
[j_end
].index_right_or_value_
= (int16_t)right
;
138 /* Add back the last sentinel node. */
139 tree
[j_end
+ 1] = sentinel
;
142 if (BrotliSetDepth((int)(2 * n
- 1), &tree
[0], depth
, tree_limit
)) {
143 /* We need to pack the Huffman tree in tree_limit bits. If this was not
144 successful, add fake entities to the lowest values and retry. */
150 static void Reverse(uint8_t* v
, size_t start
, size_t end
) {
152 while (start
< end
) {
153 uint8_t tmp
= v
[start
];
161 static void BrotliWriteHuffmanTreeRepetitions(
162 const uint8_t previous_value
,
167 uint8_t* extra_bits_data
) {
168 assert(repetitions
> 0);
169 if (previous_value
!= value
) {
170 tree
[*tree_size
] = value
;
171 extra_bits_data
[*tree_size
] = 0;
175 if (repetitions
== 7) {
176 tree
[*tree_size
] = value
;
177 extra_bits_data
[*tree_size
] = 0;
181 if (repetitions
< 3) {
183 for (i
= 0; i
< repetitions
; ++i
) {
184 tree
[*tree_size
] = value
;
185 extra_bits_data
[*tree_size
] = 0;
189 size_t start
= *tree_size
;
191 while (BROTLI_TRUE
) {
192 tree
[*tree_size
] = BROTLI_REPEAT_PREVIOUS_CODE_LENGTH
;
193 extra_bits_data
[*tree_size
] = repetitions
& 0x3;
196 if (repetitions
== 0) {
201 Reverse(tree
, start
, *tree_size
);
202 Reverse(extra_bits_data
, start
, *tree_size
);
206 static void BrotliWriteHuffmanTreeRepetitionsZeros(
210 uint8_t* extra_bits_data
) {
211 if (repetitions
== 11) {
212 tree
[*tree_size
] = 0;
213 extra_bits_data
[*tree_size
] = 0;
217 if (repetitions
< 3) {
219 for (i
= 0; i
< repetitions
; ++i
) {
220 tree
[*tree_size
] = 0;
221 extra_bits_data
[*tree_size
] = 0;
225 size_t start
= *tree_size
;
227 while (BROTLI_TRUE
) {
228 tree
[*tree_size
] = BROTLI_REPEAT_ZERO_CODE_LENGTH
;
229 extra_bits_data
[*tree_size
] = repetitions
& 0x7;
232 if (repetitions
== 0) {
237 Reverse(tree
, start
, *tree_size
);
238 Reverse(extra_bits_data
, start
, *tree_size
);
242 void BrotliOptimizeHuffmanCountsForRle(size_t length
, uint32_t* counts
,
243 uint8_t* good_for_rle
) {
244 size_t nonzero_count
= 0;
248 const size_t streak_limit
= 1240;
249 /* Let's make the Huffman code more compatible with rle encoding. */
251 for (i
= 0; i
< length
; i
++) {
256 if (nonzero_count
< 16) {
259 while (length
!= 0 && counts
[length
- 1] == 0) {
263 return; /* All zeros. */
265 /* Now counts[0..length - 1] does not have trailing zeros. */
268 uint32_t smallest_nonzero
= 1 << 30;
269 for (i
= 0; i
< length
; ++i
) {
270 if (counts
[i
] != 0) {
272 if (smallest_nonzero
> counts
[i
]) {
273 smallest_nonzero
= counts
[i
];
278 /* Small histogram will model it well. */
281 if (smallest_nonzero
< 4) {
282 size_t zeros
= length
- nonzeros
;
284 for (i
= 1; i
< length
- 1; ++i
) {
285 if (counts
[i
- 1] != 0 && counts
[i
] == 0 && counts
[i
+ 1] != 0) {
295 /* 2) Let's mark all population counts that already can be encoded
297 memset(good_for_rle
, 0, length
);
299 /* Let's not spoil any of the existing good rle codes.
300 Mark any seq of 0's that is longer as 5 as a good_for_rle.
301 Mark any seq of non-0's that is longer as 7 as a good_for_rle. */
302 uint32_t symbol
= counts
[0];
304 for (i
= 0; i
<= length
; ++i
) {
305 if (i
== length
|| counts
[i
] != symbol
) {
306 if ((symbol
== 0 && step
>= 5) ||
307 (symbol
!= 0 && step
>= 7)) {
309 for (k
= 0; k
< step
; ++k
) {
310 good_for_rle
[i
- k
- 1] = 1;
322 /* 3) Let's replace those population counts that lead to more rle codes.
323 Math here is in 24.8 fixed point representation. */
325 limit
= 256 * (counts
[0] + counts
[1] + counts
[2]) / 3 + 420;
327 for (i
= 0; i
<= length
; ++i
) {
328 if (i
== length
|| good_for_rle
[i
] ||
329 (i
!= 0 && good_for_rle
[i
- 1]) ||
330 (256 * counts
[i
] - limit
+ streak_limit
) >= 2 * streak_limit
) {
331 if (stride
>= 4 || (stride
>= 3 && sum
== 0)) {
333 /* The stride must end, collapse what we have, if we have enough (4). */
334 size_t count
= (sum
+ stride
/ 2) / stride
;
339 /* Don't make an all zeros stride to be upgraded to ones. */
342 for (k
= 0; k
< stride
; ++k
) {
343 /* We don't want to change value at counts[i],
344 that is already belonging to the next stride. Thus - 1. */
345 counts
[i
- k
- 1] = (uint32_t)count
;
350 if (i
< length
- 2) {
351 /* All interesting strides have a count of at least 4, */
352 /* at least when non-zeros. */
353 limit
= 256 * (counts
[i
] + counts
[i
+ 1] + counts
[i
+ 2]) / 3 + 420;
354 } else if (i
< length
) {
355 limit
= 256 * counts
[i
];
364 limit
= (256 * sum
+ stride
/ 2) / stride
;
373 static void DecideOverRleUse(const uint8_t* depth
, const size_t length
,
374 BROTLI_BOOL
*use_rle_for_non_zero
,
375 BROTLI_BOOL
*use_rle_for_zero
) {
376 size_t total_reps_zero
= 0;
377 size_t total_reps_non_zero
= 0;
378 size_t count_reps_zero
= 1;
379 size_t count_reps_non_zero
= 1;
381 for (i
= 0; i
< length
;) {
382 const uint8_t value
= depth
[i
];
385 for (k
= i
+ 1; k
< length
&& depth
[k
] == value
; ++k
) {
388 if (reps
>= 3 && value
== 0) {
389 total_reps_zero
+= reps
;
392 if (reps
>= 4 && value
!= 0) {
393 total_reps_non_zero
+= reps
;
394 ++count_reps_non_zero
;
398 *use_rle_for_non_zero
=
399 TO_BROTLI_BOOL(total_reps_non_zero
> count_reps_non_zero
* 2);
400 *use_rle_for_zero
= TO_BROTLI_BOOL(total_reps_zero
> count_reps_zero
* 2);
403 void BrotliWriteHuffmanTree(const uint8_t* depth
,
407 uint8_t* extra_bits_data
) {
408 uint8_t previous_value
= BROTLI_INITIAL_REPEATED_CODE_LENGTH
;
410 BROTLI_BOOL use_rle_for_non_zero
= BROTLI_FALSE
;
411 BROTLI_BOOL use_rle_for_zero
= BROTLI_FALSE
;
413 /* Throw away trailing zeros. */
414 size_t new_length
= length
;
415 for (i
= 0; i
< length
; ++i
) {
416 if (depth
[length
- i
- 1] == 0) {
423 /* First gather statistics on if it is a good idea to do rle. */
425 /* Find rle coding for longer codes.
426 Shorter codes seem not to benefit from rle. */
427 DecideOverRleUse(depth
, new_length
,
428 &use_rle_for_non_zero
, &use_rle_for_zero
);
431 /* Actual rle coding. */
432 for (i
= 0; i
< new_length
;) {
433 const uint8_t value
= depth
[i
];
435 if ((value
!= 0 && use_rle_for_non_zero
) ||
436 (value
== 0 && use_rle_for_zero
)) {
438 for (k
= i
+ 1; k
< new_length
&& depth
[k
] == value
; ++k
) {
443 BrotliWriteHuffmanTreeRepetitionsZeros(
444 reps
, tree_size
, tree
, extra_bits_data
);
446 BrotliWriteHuffmanTreeRepetitions(previous_value
,
447 value
, reps
, tree_size
,
448 tree
, extra_bits_data
);
449 previous_value
= value
;
455 static uint16_t BrotliReverseBits(size_t num_bits
, uint16_t bits
) {
456 static const size_t kLut
[16] = { /* Pre-reversed 4-bit values. */
457 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
458 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
460 size_t retval
= kLut
[bits
& 0xf];
462 for (i
= 4; i
< num_bits
; i
+= 4) {
464 bits
= (uint16_t)(bits
>> 4);
465 retval
|= kLut
[bits
& 0xf];
467 retval
>>= ((0 - num_bits
) & 0x3);
468 return (uint16_t)retval
;
471 /* 0..15 are values for bits */
472 #define MAX_HUFFMAN_BITS 16
474 void BrotliConvertBitDepthsToSymbols(const uint8_t *depth
,
477 /* In Brotli, all bit depths are [1..15]
478 0 bit depth means that the symbol does not exist. */
479 uint16_t bl_count
[MAX_HUFFMAN_BITS
] = { 0 };
480 uint16_t next_code
[MAX_HUFFMAN_BITS
];
483 for (i
= 0; i
< len
; ++i
) {
484 ++bl_count
[depth
[i
]];
488 for (i
= 1; i
< MAX_HUFFMAN_BITS
; ++i
) {
489 code
= (code
+ bl_count
[i
- 1]) << 1;
490 next_code
[i
] = (uint16_t)code
;
492 for (i
= 0; i
< len
; ++i
) {
494 bits
[i
] = BrotliReverseBits(depth
[i
], next_code
[depth
[i
]]++);
499 #if defined(__cplusplus) || defined(c_plusplus)