1/* Copyright 2010 Google Inc. All Rights Reserved.
2
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5*/
6
7/* Entropy encoding (Huffman) utilities. */
8
9#include "./entropy_encode.h"
10
11#include <string.h> /* memset */
12
13#include "../common/constants.h"
14#include "../common/platform.h"
15#include <brotli/types.h>
16
17#if defined(__cplusplus) || defined(c_plusplus)
18extern "C" {
19#endif
20
21BROTLI_BOOL BrotliSetDepth(
22 int p0, HuffmanTree* pool, uint8_t* depth, int max_depth) {
23 int stack[16];
24 int level = 0;
25 int p = p0;
26 BROTLI_DCHECK(max_depth <= 15);
27 stack[0] = -1;
28 while (BROTLI_TRUE) {
29 if (pool[p].index_left_ >= 0) {
30 level++;
31 if (level > max_depth) return BROTLI_FALSE;
32 stack[level] = pool[p].index_right_or_value_;
33 p = pool[p].index_left_;
34 continue;
35 } else {
36 depth[pool[p].index_right_or_value_] = (uint8_t)level;
37 }
38 while (level >= 0 && stack[level] == -1) level--;
39 if (level < 0) return BROTLI_TRUE;
40 p = stack[level];
41 stack[level] = -1;
42 }
43}
44
45/* Sort the root nodes, least popular first. */
46static 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_);
50 }
51 return TO_BROTLI_BOOL(v0->index_right_or_value_ > v1->index_right_or_value_);
52}
53
54/* This function will create a Huffman tree.
55
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."
59
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.
63
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.
67
68 See http://en.wikipedia.org/wiki/Huffman_coding */
69void BrotliCreateHuffmanTree(const uint32_t* data,
70 const size_t length,
71 const int tree_limit,
72 HuffmanTree* tree,
73 uint8_t* depth) {
74 uint32_t count_limit;
75 HuffmanTree sentinel;
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) {
82 size_t n = 0;
83 size_t i;
84 size_t j;
85 size_t k;
86 for (i = length; i != 0;) {
87 --i;
88 if (data[i]) {
89 const uint32_t count = BROTLI_MAX(uint32_t, data[i], count_limit);
90 InitHuffmanTree(&tree[n++], count, -1, (int16_t)i);
91 }
92 }
93
94 if (n == 1) {
95 depth[tree[0].index_right_or_value_] = 1; /* Only one element. */
96 break;
97 }
98
99 SortHuffmanTreeItems(tree, n, SortHuffmanTree);
100
101 /* The nodes are:
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. */
108 tree[n] = sentinel;
109 tree[n + 1] = sentinel;
110
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) {
114 size_t left, right;
115 if (tree[i].total_count_ <= tree[j].total_count_) {
116 left = i;
117 ++i;
118 } else {
119 left = j;
120 ++j;
121 }
122 if (tree[i].total_count_ <= tree[j].total_count_) {
123 right = i;
124 ++i;
125 } else {
126 right = j;
127 ++j;
128 }
129
130 {
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;
137
138 /* Add back the last sentinel node. */
139 tree[j_end + 1] = sentinel;
140 }
141 }
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. */
145 break;
146 }
147 }
148}
149
150static void Reverse(uint8_t* v, size_t start, size_t end) {
151 --end;
152 while (start < end) {
153 uint8_t tmp = v[start];
154 v[start] = v[end];
155 v[end] = tmp;
156 ++start;
157 --end;
158 }
159}
160
161static void BrotliWriteHuffmanTreeRepetitions(
162 const uint8_t previous_value,
163 const uint8_t value,
164 size_t repetitions,
165 size_t* tree_size,
166 uint8_t* tree,
167 uint8_t* extra_bits_data) {
168 BROTLI_DCHECK(repetitions > 0);
169 if (previous_value != value) {
170 tree[*tree_size] = value;
171 extra_bits_data[*tree_size] = 0;
172 ++(*tree_size);
173 --repetitions;
174 }
175 if (repetitions == 7) {
176 tree[*tree_size] = value;
177 extra_bits_data[*tree_size] = 0;
178 ++(*tree_size);
179 --repetitions;
180 }
181 if (repetitions < 3) {
182 size_t i;
183 for (i = 0; i < repetitions; ++i) {
184 tree[*tree_size] = value;
185 extra_bits_data[*tree_size] = 0;
186 ++(*tree_size);
187 }
188 } else {
189 size_t start = *tree_size;
190 repetitions -= 3;
191 while (BROTLI_TRUE) {
192 tree[*tree_size] = BROTLI_REPEAT_PREVIOUS_CODE_LENGTH;
193 extra_bits_data[*tree_size] = repetitions & 0x3;
194 ++(*tree_size);
195 repetitions >>= 2;
196 if (repetitions == 0) {
197 break;
198 }
199 --repetitions;
200 }
201 Reverse(tree, start, *tree_size);
202 Reverse(extra_bits_data, start, *tree_size);
203 }
204}
205
206static void BrotliWriteHuffmanTreeRepetitionsZeros(
207 size_t repetitions,
208 size_t* tree_size,
209 uint8_t* tree,
210 uint8_t* extra_bits_data) {
211 if (repetitions == 11) {
212 tree[*tree_size] = 0;
213 extra_bits_data[*tree_size] = 0;
214 ++(*tree_size);
215 --repetitions;
216 }
217 if (repetitions < 3) {
218 size_t i;
219 for (i = 0; i < repetitions; ++i) {
220 tree[*tree_size] = 0;
221 extra_bits_data[*tree_size] = 0;
222 ++(*tree_size);
223 }
224 } else {
225 size_t start = *tree_size;
226 repetitions -= 3;
227 while (BROTLI_TRUE) {
228 tree[*tree_size] = BROTLI_REPEAT_ZERO_CODE_LENGTH;
229 extra_bits_data[*tree_size] = repetitions & 0x7;
230 ++(*tree_size);
231 repetitions >>= 3;
232 if (repetitions == 0) {
233 break;
234 }
235 --repetitions;
236 }
237 Reverse(tree, start, *tree_size);
238 Reverse(extra_bits_data, start, *tree_size);
239 }
240}
241
242void BrotliOptimizeHuffmanCountsForRle(size_t length, uint32_t* counts,
243 uint8_t* good_for_rle) {
244 size_t nonzero_count = 0;
245 size_t stride;
246 size_t limit;
247 size_t sum;
248 const size_t streak_limit = 1240;
249 /* Let's make the Huffman code more compatible with RLE encoding. */
250 size_t i;
251 for (i = 0; i < length; i++) {
252 if (counts[i]) {
253 ++nonzero_count;
254 }
255 }
256 if (nonzero_count < 16) {
257 return;
258 }
259 while (length != 0 && counts[length - 1] == 0) {
260 --length;
261 }
262 if (length == 0) {
263 return; /* All zeros. */
264 }
265 /* Now counts[0..length - 1] does not have trailing zeros. */
266 {
267 size_t nonzeros = 0;
268 uint32_t smallest_nonzero = 1 << 30;
269 for (i = 0; i < length; ++i) {
270 if (counts[i] != 0) {
271 ++nonzeros;
272 if (smallest_nonzero > counts[i]) {
273 smallest_nonzero = counts[i];
274 }
275 }
276 }
277 if (nonzeros < 5) {
278 /* Small histogram will model it well. */
279 return;
280 }
281 if (smallest_nonzero < 4) {
282 size_t zeros = length - nonzeros;
283 if (zeros < 6) {
284 for (i = 1; i < length - 1; ++i) {
285 if (counts[i - 1] != 0 && counts[i] == 0 && counts[i + 1] != 0) {
286 counts[i] = 1;
287 }
288 }
289 }
290 }
291 if (nonzeros < 28) {
292 return;
293 }
294 }
295 /* 2) Let's mark all population counts that already can be encoded
296 with an RLE code. */
297 memset(good_for_rle, 0, length);
298 {
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];
303 size_t step = 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)) {
308 size_t k;
309 for (k = 0; k < step; ++k) {
310 good_for_rle[i - k - 1] = 1;
311 }
312 }
313 step = 1;
314 if (i != length) {
315 symbol = counts[i];
316 }
317 } else {
318 ++step;
319 }
320 }
321 }
322 /* 3) Let's replace those population counts that lead to more RLE codes.
323 Math here is in 24.8 fixed point representation. */
324 stride = 0;
325 limit = 256 * (counts[0] + counts[1] + counts[2]) / 3 + 420;
326 sum = 0;
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)) {
332 size_t k;
333 /* The stride must end, collapse what we have, if we have enough (4). */
334 size_t count = (sum + stride / 2) / stride;
335 if (count == 0) {
336 count = 1;
337 }
338 if (sum == 0) {
339 /* Don't make an all zeros stride to be upgraded to ones. */
340 count = 0;
341 }
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;
346 }
347 }
348 stride = 0;
349 sum = 0;
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];
356 } else {
357 limit = 0;
358 }
359 }
360 ++stride;
361 if (i != length) {
362 sum += counts[i];
363 if (stride >= 4) {
364 limit = (256 * sum + stride / 2) / stride;
365 }
366 if (stride == 4) {
367 limit += 120;
368 }
369 }
370 }
371}
372
373static 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;
380 size_t i;
381 for (i = 0; i < length;) {
382 const uint8_t value = depth[i];
383 size_t reps = 1;
384 size_t k;
385 for (k = i + 1; k < length && depth[k] == value; ++k) {
386 ++reps;
387 }
388 if (reps >= 3 && value == 0) {
389 total_reps_zero += reps;
390 ++count_reps_zero;
391 }
392 if (reps >= 4 && value != 0) {
393 total_reps_non_zero += reps;
394 ++count_reps_non_zero;
395 }
396 i += reps;
397 }
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);
401}
402
403void BrotliWriteHuffmanTree(const uint8_t* depth,
404 size_t length,
405 size_t* tree_size,
406 uint8_t* tree,
407 uint8_t* extra_bits_data) {
408 uint8_t previous_value = BROTLI_INITIAL_REPEATED_CODE_LENGTH;
409 size_t i;
410 BROTLI_BOOL use_rle_for_non_zero = BROTLI_FALSE;
411 BROTLI_BOOL use_rle_for_zero = BROTLI_FALSE;
412
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) {
417 --new_length;
418 } else {
419 break;
420 }
421 }
422
423 /* First gather statistics on if it is a good idea to do RLE. */
424 if (length > 50) {
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);
429 }
430
431 /* Actual RLE coding. */
432 for (i = 0; i < new_length;) {
433 const uint8_t value = depth[i];
434 size_t reps = 1;
435 if ((value != 0 && use_rle_for_non_zero) ||
436 (value == 0 && use_rle_for_zero)) {
437 size_t k;
438 for (k = i + 1; k < new_length && depth[k] == value; ++k) {
439 ++reps;
440 }
441 }
442 if (value == 0) {
443 BrotliWriteHuffmanTreeRepetitionsZeros(
444 reps, tree_size, tree, extra_bits_data);
445 } else {
446 BrotliWriteHuffmanTreeRepetitions(previous_value,
447 value, reps, tree_size,
448 tree, extra_bits_data);
449 previous_value = value;
450 }
451 i += reps;
452 }
453}
454
455static uint16_t BrotliReverseBits(size_t num_bits, uint16_t bits) {
456 static const size_t kLut[16] = { /* Pre-reversed 4-bit values. */
457 0x00, 0x08, 0x04, 0x0C, 0x02, 0x0A, 0x06, 0x0E,
458 0x01, 0x09, 0x05, 0x0D, 0x03, 0x0B, 0x07, 0x0F
459 };
460 size_t retval = kLut[bits & 0x0F];
461 size_t i;
462 for (i = 4; i < num_bits; i += 4) {
463 retval <<= 4;
464 bits = (uint16_t)(bits >> 4);
465 retval |= kLut[bits & 0x0F];
466 }
467 retval >>= ((0 - num_bits) & 0x03);
468 return (uint16_t)retval;
469}
470
471/* 0..15 are values for bits */
472#define MAX_HUFFMAN_BITS 16
473
474void BrotliConvertBitDepthsToSymbols(const uint8_t* depth,
475 size_t len,
476 uint16_t* bits) {
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];
481 size_t i;
482 int code = 0;
483 for (i = 0; i < len; ++i) {
484 ++bl_count[depth[i]];
485 }
486 bl_count[0] = 0;
487 next_code[0] = 0;
488 for (i = 1; i < MAX_HUFFMAN_BITS; ++i) {
489 code = (code + bl_count[i - 1]) << 1;
490 next_code[i] = (uint16_t)code;
491 }
492 for (i = 0; i < len; ++i) {
493 if (depth[i]) {
494 bits[i] = BrotliReverseBits(depth[i], next_code[depth[i]]++);
495 }
496 }
497}
498
499#if defined(__cplusplus) || defined(c_plusplus)
500} /* extern "C" */
501#endif
502