]>
Commit | Line | Data |
---|---|---|
11b7501a SB |
1 | /* Copyright 2010 Google Inc. All Rights Reserved.\r |
2 | \r | |
3 | Distributed under MIT license.\r | |
4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r | |
5 | */\r | |
6 | \r | |
7 | /* Entropy encoding (Huffman) utilities. */\r | |
8 | \r | |
9 | #include "./entropy_encode.h"\r | |
10 | \r | |
11 | #include <string.h> /* memset */\r | |
12 | \r | |
13 | #include "../common/constants.h"\r | |
14 | #include "../common/types.h"\r | |
15 | #include "./port.h"\r | |
16 | \r | |
17 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
18 | extern "C" {\r | |
19 | #endif\r | |
20 | \r | |
21 | BROTLI_BOOL BrotliSetDepth(\r | |
22 | int p0, HuffmanTree* pool, uint8_t* depth, int max_depth) {\r | |
23 | int stack[16];\r | |
24 | int level = 0;\r | |
25 | int p = p0;\r | |
26 | assert(max_depth <= 15);\r | |
27 | stack[0] = -1;\r | |
28 | while (BROTLI_TRUE) {\r | |
29 | if (pool[p].index_left_ >= 0) {\r | |
30 | level++;\r | |
31 | if (level > max_depth) return BROTLI_FALSE;\r | |
32 | stack[level] = pool[p].index_right_or_value_;\r | |
33 | p = pool[p].index_left_;\r | |
34 | continue;\r | |
35 | } else {\r | |
36 | depth[pool[p].index_right_or_value_] = (uint8_t)level;\r | |
37 | }\r | |
38 | while (level >= 0 && stack[level] == -1) level--;\r | |
39 | if (level < 0) return BROTLI_TRUE;\r | |
40 | p = stack[level];\r | |
41 | stack[level] = -1;\r | |
42 | }\r | |
43 | }\r | |
44 | \r | |
45 | /* Sort the root nodes, least popular first. */\r | |
46 | static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree(\r | |
47 | const HuffmanTree* v0, const HuffmanTree* v1) {\r | |
48 | if (v0->total_count_ != v1->total_count_) {\r | |
49 | return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_);\r | |
50 | }\r | |
51 | return TO_BROTLI_BOOL(v0->index_right_or_value_ > v1->index_right_or_value_);\r | |
52 | }\r | |
53 | \r | |
54 | /* This function will create a Huffman tree.\r | |
55 | \r | |
56 | The catch here is that the tree cannot be arbitrarily deep.\r | |
57 | Brotli specifies a maximum depth of 15 bits for "code trees"\r | |
58 | and 7 bits for "code length code trees."\r | |
59 | \r | |
60 | count_limit is the value that is to be faked as the minimum value\r | |
61 | and this minimum value is raised until the tree matches the\r | |
62 | maximum length requirement.\r | |
63 | \r | |
64 | This algorithm is not of excellent performance for very long data blocks,\r | |
65 | especially when population counts are longer than 2**tree_limit, but\r | |
66 | we are not planning to use this with extremely long blocks.\r | |
67 | \r | |
68 | See http://en.wikipedia.org/wiki/Huffman_coding */\r | |
69 | void BrotliCreateHuffmanTree(const uint32_t *data,\r | |
70 | const size_t length,\r | |
71 | const int tree_limit,\r | |
72 | HuffmanTree* tree,\r | |
73 | uint8_t *depth) {\r | |
74 | uint32_t count_limit;\r | |
75 | HuffmanTree sentinel;\r | |
76 | InitHuffmanTree(&sentinel, BROTLI_UINT32_MAX, -1, -1);\r | |
77 | /* For block sizes below 64 kB, we never need to do a second iteration\r | |
78 | of this loop. Probably all of our block sizes will be smaller than\r | |
79 | that, so this loop is mostly of academic interest. If we actually\r | |
80 | would need this, we would be better off with the Katajainen algorithm. */\r | |
81 | for (count_limit = 1; ; count_limit *= 2) {\r | |
82 | size_t n = 0;\r | |
83 | size_t i;\r | |
84 | size_t j;\r | |
85 | size_t k;\r | |
86 | for (i = length; i != 0;) {\r | |
87 | --i;\r | |
88 | if (data[i]) {\r | |
89 | const uint32_t count = BROTLI_MAX(uint32_t, data[i], count_limit);\r | |
90 | InitHuffmanTree(&tree[n++], count, -1, (int16_t)i);\r | |
91 | }\r | |
92 | }\r | |
93 | \r | |
94 | if (n == 1) {\r | |
95 | depth[tree[0].index_right_or_value_] = 1; /* Only one element. */\r | |
96 | break;\r | |
97 | }\r | |
98 | \r | |
99 | SortHuffmanTreeItems(tree, n, SortHuffmanTree);\r | |
100 | \r | |
101 | /* The nodes are:\r | |
102 | [0, n): the sorted leaf nodes that we start with.\r | |
103 | [n]: we add a sentinel here.\r | |
104 | [n + 1, 2n): new parent nodes are added here, starting from\r | |
105 | (n+1). These are naturally in ascending order.\r | |
106 | [2n]: we add a sentinel at the end as well.\r | |
107 | There will be (2n+1) elements at the end. */\r | |
108 | tree[n] = sentinel;\r | |
109 | tree[n + 1] = sentinel;\r | |
110 | \r | |
111 | i = 0; /* Points to the next leaf node. */\r | |
112 | j = n + 1; /* Points to the next non-leaf node. */\r | |
113 | for (k = n - 1; k != 0; --k) {\r | |
114 | size_t left, right;\r | |
115 | if (tree[i].total_count_ <= tree[j].total_count_) {\r | |
116 | left = i;\r | |
117 | ++i;\r | |
118 | } else {\r | |
119 | left = j;\r | |
120 | ++j;\r | |
121 | }\r | |
122 | if (tree[i].total_count_ <= tree[j].total_count_) {\r | |
123 | right = i;\r | |
124 | ++i;\r | |
125 | } else {\r | |
126 | right = j;\r | |
127 | ++j;\r | |
128 | }\r | |
129 | \r | |
130 | {\r | |
131 | /* The sentinel node becomes the parent node. */\r | |
132 | size_t j_end = 2 * n - k;\r | |
133 | tree[j_end].total_count_ =\r | |
134 | tree[left].total_count_ + tree[right].total_count_;\r | |
135 | tree[j_end].index_left_ = (int16_t)left;\r | |
136 | tree[j_end].index_right_or_value_ = (int16_t)right;\r | |
137 | \r | |
138 | /* Add back the last sentinel node. */\r | |
139 | tree[j_end + 1] = sentinel;\r | |
140 | }\r | |
141 | }\r | |
142 | if (BrotliSetDepth((int)(2 * n - 1), &tree[0], depth, tree_limit)) {\r | |
143 | /* We need to pack the Huffman tree in tree_limit bits. If this was not\r | |
144 | successful, add fake entities to the lowest values and retry. */\r | |
145 | break;\r | |
146 | }\r | |
147 | }\r | |
148 | }\r | |
149 | \r | |
150 | static void Reverse(uint8_t* v, size_t start, size_t end) {\r | |
151 | --end;\r | |
152 | while (start < end) {\r | |
153 | uint8_t tmp = v[start];\r | |
154 | v[start] = v[end];\r | |
155 | v[end] = tmp;\r | |
156 | ++start;\r | |
157 | --end;\r | |
158 | }\r | |
159 | }\r | |
160 | \r | |
161 | static void BrotliWriteHuffmanTreeRepetitions(\r | |
162 | const uint8_t previous_value,\r | |
163 | const uint8_t value,\r | |
164 | size_t repetitions,\r | |
165 | size_t* tree_size,\r | |
166 | uint8_t* tree,\r | |
167 | uint8_t* extra_bits_data) {\r | |
168 | assert(repetitions > 0);\r | |
169 | if (previous_value != value) {\r | |
170 | tree[*tree_size] = value;\r | |
171 | extra_bits_data[*tree_size] = 0;\r | |
172 | ++(*tree_size);\r | |
173 | --repetitions;\r | |
174 | }\r | |
175 | if (repetitions == 7) {\r | |
176 | tree[*tree_size] = value;\r | |
177 | extra_bits_data[*tree_size] = 0;\r | |
178 | ++(*tree_size);\r | |
179 | --repetitions;\r | |
180 | }\r | |
181 | if (repetitions < 3) {\r | |
182 | size_t i;\r | |
183 | for (i = 0; i < repetitions; ++i) {\r | |
184 | tree[*tree_size] = value;\r | |
185 | extra_bits_data[*tree_size] = 0;\r | |
186 | ++(*tree_size);\r | |
187 | }\r | |
188 | } else {\r | |
189 | size_t start = *tree_size;\r | |
190 | repetitions -= 3;\r | |
191 | while (BROTLI_TRUE) {\r | |
192 | tree[*tree_size] = BROTLI_REPEAT_PREVIOUS_CODE_LENGTH;\r | |
193 | extra_bits_data[*tree_size] = repetitions & 0x3;\r | |
194 | ++(*tree_size);\r | |
195 | repetitions >>= 2;\r | |
196 | if (repetitions == 0) {\r | |
197 | break;\r | |
198 | }\r | |
199 | --repetitions;\r | |
200 | }\r | |
201 | Reverse(tree, start, *tree_size);\r | |
202 | Reverse(extra_bits_data, start, *tree_size);\r | |
203 | }\r | |
204 | }\r | |
205 | \r | |
206 | static void BrotliWriteHuffmanTreeRepetitionsZeros(\r | |
207 | size_t repetitions,\r | |
208 | size_t* tree_size,\r | |
209 | uint8_t* tree,\r | |
210 | uint8_t* extra_bits_data) {\r | |
211 | if (repetitions == 11) {\r | |
212 | tree[*tree_size] = 0;\r | |
213 | extra_bits_data[*tree_size] = 0;\r | |
214 | ++(*tree_size);\r | |
215 | --repetitions;\r | |
216 | }\r | |
217 | if (repetitions < 3) {\r | |
218 | size_t i;\r | |
219 | for (i = 0; i < repetitions; ++i) {\r | |
220 | tree[*tree_size] = 0;\r | |
221 | extra_bits_data[*tree_size] = 0;\r | |
222 | ++(*tree_size);\r | |
223 | }\r | |
224 | } else {\r | |
225 | size_t start = *tree_size;\r | |
226 | repetitions -= 3;\r | |
227 | while (BROTLI_TRUE) {\r | |
228 | tree[*tree_size] = BROTLI_REPEAT_ZERO_CODE_LENGTH;\r | |
229 | extra_bits_data[*tree_size] = repetitions & 0x7;\r | |
230 | ++(*tree_size);\r | |
231 | repetitions >>= 3;\r | |
232 | if (repetitions == 0) {\r | |
233 | break;\r | |
234 | }\r | |
235 | --repetitions;\r | |
236 | }\r | |
237 | Reverse(tree, start, *tree_size);\r | |
238 | Reverse(extra_bits_data, start, *tree_size);\r | |
239 | }\r | |
240 | }\r | |
241 | \r | |
242 | void BrotliOptimizeHuffmanCountsForRle(size_t length, uint32_t* counts,\r | |
243 | uint8_t* good_for_rle) {\r | |
244 | size_t nonzero_count = 0;\r | |
245 | size_t stride;\r | |
246 | size_t limit;\r | |
247 | size_t sum;\r | |
248 | const size_t streak_limit = 1240;\r | |
249 | /* Let's make the Huffman code more compatible with rle encoding. */\r | |
250 | size_t i;\r | |
251 | for (i = 0; i < length; i++) {\r | |
252 | if (counts[i]) {\r | |
253 | ++nonzero_count;\r | |
254 | }\r | |
255 | }\r | |
256 | if (nonzero_count < 16) {\r | |
257 | return;\r | |
258 | }\r | |
259 | while (length != 0 && counts[length - 1] == 0) {\r | |
260 | --length;\r | |
261 | }\r | |
262 | if (length == 0) {\r | |
263 | return; /* All zeros. */\r | |
264 | }\r | |
265 | /* Now counts[0..length - 1] does not have trailing zeros. */\r | |
266 | {\r | |
267 | size_t nonzeros = 0;\r | |
268 | uint32_t smallest_nonzero = 1 << 30;\r | |
269 | for (i = 0; i < length; ++i) {\r | |
270 | if (counts[i] != 0) {\r | |
271 | ++nonzeros;\r | |
272 | if (smallest_nonzero > counts[i]) {\r | |
273 | smallest_nonzero = counts[i];\r | |
274 | }\r | |
275 | }\r | |
276 | }\r | |
277 | if (nonzeros < 5) {\r | |
278 | /* Small histogram will model it well. */\r | |
279 | return;\r | |
280 | }\r | |
281 | if (smallest_nonzero < 4) {\r | |
282 | size_t zeros = length - nonzeros;\r | |
283 | if (zeros < 6) {\r | |
284 | for (i = 1; i < length - 1; ++i) {\r | |
285 | if (counts[i - 1] != 0 && counts[i] == 0 && counts[i + 1] != 0) {\r | |
286 | counts[i] = 1;\r | |
287 | }\r | |
288 | }\r | |
289 | }\r | |
290 | }\r | |
291 | if (nonzeros < 28) {\r | |
292 | return;\r | |
293 | }\r | |
294 | }\r | |
295 | /* 2) Let's mark all population counts that already can be encoded\r | |
296 | with an rle code. */\r | |
297 | memset(good_for_rle, 0, length);\r | |
298 | {\r | |
299 | /* Let's not spoil any of the existing good rle codes.\r | |
300 | Mark any seq of 0's that is longer as 5 as a good_for_rle.\r | |
301 | Mark any seq of non-0's that is longer as 7 as a good_for_rle. */\r | |
302 | uint32_t symbol = counts[0];\r | |
303 | size_t step = 0;\r | |
304 | for (i = 0; i <= length; ++i) {\r | |
305 | if (i == length || counts[i] != symbol) {\r | |
306 | if ((symbol == 0 && step >= 5) ||\r | |
307 | (symbol != 0 && step >= 7)) {\r | |
308 | size_t k;\r | |
309 | for (k = 0; k < step; ++k) {\r | |
310 | good_for_rle[i - k - 1] = 1;\r | |
311 | }\r | |
312 | }\r | |
313 | step = 1;\r | |
314 | if (i != length) {\r | |
315 | symbol = counts[i];\r | |
316 | }\r | |
317 | } else {\r | |
318 | ++step;\r | |
319 | }\r | |
320 | }\r | |
321 | }\r | |
322 | /* 3) Let's replace those population counts that lead to more rle codes.\r | |
323 | Math here is in 24.8 fixed point representation. */\r | |
324 | stride = 0;\r | |
325 | limit = 256 * (counts[0] + counts[1] + counts[2]) / 3 + 420;\r | |
326 | sum = 0;\r | |
327 | for (i = 0; i <= length; ++i) {\r | |
328 | if (i == length || good_for_rle[i] ||\r | |
329 | (i != 0 && good_for_rle[i - 1]) ||\r | |
330 | (256 * counts[i] - limit + streak_limit) >= 2 * streak_limit) {\r | |
331 | if (stride >= 4 || (stride >= 3 && sum == 0)) {\r | |
332 | size_t k;\r | |
333 | /* The stride must end, collapse what we have, if we have enough (4). */\r | |
334 | size_t count = (sum + stride / 2) / stride;\r | |
335 | if (count == 0) {\r | |
336 | count = 1;\r | |
337 | }\r | |
338 | if (sum == 0) {\r | |
339 | /* Don't make an all zeros stride to be upgraded to ones. */\r | |
340 | count = 0;\r | |
341 | }\r | |
342 | for (k = 0; k < stride; ++k) {\r | |
343 | /* We don't want to change value at counts[i],\r | |
344 | that is already belonging to the next stride. Thus - 1. */\r | |
345 | counts[i - k - 1] = (uint32_t)count;\r | |
346 | }\r | |
347 | }\r | |
348 | stride = 0;\r | |
349 | sum = 0;\r | |
350 | if (i < length - 2) {\r | |
351 | /* All interesting strides have a count of at least 4, */\r | |
352 | /* at least when non-zeros. */\r | |
353 | limit = 256 * (counts[i] + counts[i + 1] + counts[i + 2]) / 3 + 420;\r | |
354 | } else if (i < length) {\r | |
355 | limit = 256 * counts[i];\r | |
356 | } else {\r | |
357 | limit = 0;\r | |
358 | }\r | |
359 | }\r | |
360 | ++stride;\r | |
361 | if (i != length) {\r | |
362 | sum += counts[i];\r | |
363 | if (stride >= 4) {\r | |
364 | limit = (256 * sum + stride / 2) / stride;\r | |
365 | }\r | |
366 | if (stride == 4) {\r | |
367 | limit += 120;\r | |
368 | }\r | |
369 | }\r | |
370 | }\r | |
371 | }\r | |
372 | \r | |
373 | static void DecideOverRleUse(const uint8_t* depth, const size_t length,\r | |
374 | BROTLI_BOOL *use_rle_for_non_zero,\r | |
375 | BROTLI_BOOL *use_rle_for_zero) {\r | |
376 | size_t total_reps_zero = 0;\r | |
377 | size_t total_reps_non_zero = 0;\r | |
378 | size_t count_reps_zero = 1;\r | |
379 | size_t count_reps_non_zero = 1;\r | |
380 | size_t i;\r | |
381 | for (i = 0; i < length;) {\r | |
382 | const uint8_t value = depth[i];\r | |
383 | size_t reps = 1;\r | |
384 | size_t k;\r | |
385 | for (k = i + 1; k < length && depth[k] == value; ++k) {\r | |
386 | ++reps;\r | |
387 | }\r | |
388 | if (reps >= 3 && value == 0) {\r | |
389 | total_reps_zero += reps;\r | |
390 | ++count_reps_zero;\r | |
391 | }\r | |
392 | if (reps >= 4 && value != 0) {\r | |
393 | total_reps_non_zero += reps;\r | |
394 | ++count_reps_non_zero;\r | |
395 | }\r | |
396 | i += reps;\r | |
397 | }\r | |
398 | *use_rle_for_non_zero =\r | |
399 | TO_BROTLI_BOOL(total_reps_non_zero > count_reps_non_zero * 2);\r | |
400 | *use_rle_for_zero = TO_BROTLI_BOOL(total_reps_zero > count_reps_zero * 2);\r | |
401 | }\r | |
402 | \r | |
403 | void BrotliWriteHuffmanTree(const uint8_t* depth,\r | |
404 | size_t length,\r | |
405 | size_t* tree_size,\r | |
406 | uint8_t* tree,\r | |
407 | uint8_t* extra_bits_data) {\r | |
408 | uint8_t previous_value = BROTLI_INITIAL_REPEATED_CODE_LENGTH;\r | |
409 | size_t i;\r | |
410 | BROTLI_BOOL use_rle_for_non_zero = BROTLI_FALSE;\r | |
411 | BROTLI_BOOL use_rle_for_zero = BROTLI_FALSE;\r | |
412 | \r | |
413 | /* Throw away trailing zeros. */\r | |
414 | size_t new_length = length;\r | |
415 | for (i = 0; i < length; ++i) {\r | |
416 | if (depth[length - i - 1] == 0) {\r | |
417 | --new_length;\r | |
418 | } else {\r | |
419 | break;\r | |
420 | }\r | |
421 | }\r | |
422 | \r | |
423 | /* First gather statistics on if it is a good idea to do rle. */\r | |
424 | if (length > 50) {\r | |
425 | /* Find rle coding for longer codes.\r | |
426 | Shorter codes seem not to benefit from rle. */\r | |
427 | DecideOverRleUse(depth, new_length,\r | |
428 | &use_rle_for_non_zero, &use_rle_for_zero);\r | |
429 | }\r | |
430 | \r | |
431 | /* Actual rle coding. */\r | |
432 | for (i = 0; i < new_length;) {\r | |
433 | const uint8_t value = depth[i];\r | |
434 | size_t reps = 1;\r | |
435 | if ((value != 0 && use_rle_for_non_zero) ||\r | |
436 | (value == 0 && use_rle_for_zero)) {\r | |
437 | size_t k;\r | |
438 | for (k = i + 1; k < new_length && depth[k] == value; ++k) {\r | |
439 | ++reps;\r | |
440 | }\r | |
441 | }\r | |
442 | if (value == 0) {\r | |
443 | BrotliWriteHuffmanTreeRepetitionsZeros(\r | |
444 | reps, tree_size, tree, extra_bits_data);\r | |
445 | } else {\r | |
446 | BrotliWriteHuffmanTreeRepetitions(previous_value,\r | |
447 | value, reps, tree_size,\r | |
448 | tree, extra_bits_data);\r | |
449 | previous_value = value;\r | |
450 | }\r | |
451 | i += reps;\r | |
452 | }\r | |
453 | }\r | |
454 | \r | |
455 | static uint16_t BrotliReverseBits(size_t num_bits, uint16_t bits) {\r | |
456 | static const size_t kLut[16] = { /* Pre-reversed 4-bit values. */\r | |
457 | 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,\r | |
458 | 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf\r | |
459 | };\r | |
460 | size_t retval = kLut[bits & 0xf];\r | |
461 | size_t i;\r | |
462 | for (i = 4; i < num_bits; i += 4) {\r | |
463 | retval <<= 4;\r | |
464 | bits = (uint16_t)(bits >> 4);\r | |
465 | retval |= kLut[bits & 0xf];\r | |
466 | }\r | |
467 | retval >>= ((0 - num_bits) & 0x3);\r | |
468 | return (uint16_t)retval;\r | |
469 | }\r | |
470 | \r | |
471 | /* 0..15 are values for bits */\r | |
472 | #define MAX_HUFFMAN_BITS 16\r | |
473 | \r | |
474 | void BrotliConvertBitDepthsToSymbols(const uint8_t *depth,\r | |
475 | size_t len,\r | |
476 | uint16_t *bits) {\r | |
477 | /* In Brotli, all bit depths are [1..15]\r | |
478 | 0 bit depth means that the symbol does not exist. */\r | |
479 | uint16_t bl_count[MAX_HUFFMAN_BITS] = { 0 };\r | |
480 | uint16_t next_code[MAX_HUFFMAN_BITS];\r | |
481 | size_t i;\r | |
482 | int code = 0;\r | |
483 | for (i = 0; i < len; ++i) {\r | |
484 | ++bl_count[depth[i]];\r | |
485 | }\r | |
486 | bl_count[0] = 0;\r | |
487 | next_code[0] = 0;\r | |
488 | for (i = 1; i < MAX_HUFFMAN_BITS; ++i) {\r | |
489 | code = (code + bl_count[i - 1]) << 1;\r | |
490 | next_code[i] = (uint16_t)code;\r | |
491 | }\r | |
492 | for (i = 0; i < len; ++i) {\r | |
493 | if (depth[i]) {\r | |
494 | bits[i] = BrotliReverseBits(depth[i], next_code[depth[i]]++);\r | |
495 | }\r | |
496 | }\r | |
497 | }\r | |
498 | \r | |
499 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
500 | } /* extern "C" */\r | |
501 | #endif\r |