Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/brotli/c/enc/entropy_encode.c @ 2:b50eed0cc0ef upstream

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