Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/brotli/c/enc/brotli_bit_stream.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 2014 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 /* Brotli bit stream functions to support the low level format. There are no
8 compression algorithms here, just the right ordering of bits to match the
9 specs. */
10
11 #include "brotli_bit_stream.h"
12
13 #include <string.h> /* memcpy, memset */
14
15 #include <brotli/types.h>
16
17 #include "../common/constants.h"
18 #include "../common/context.h"
19 #include "../common/platform.h"
20 #include "entropy_encode.h"
21 #include "entropy_encode_static.h"
22 #include "fast_log.h"
23 #include "histogram.h"
24 #include "memory.h"
25 #include "write_bits.h"
26
27 #if defined(__cplusplus) || defined(c_plusplus)
28 extern "C" {
29 #endif
30
31 #define MAX_HUFFMAN_TREE_SIZE (2 * BROTLI_NUM_COMMAND_SYMBOLS + 1)
32 /* The maximum size of Huffman dictionary for distances assuming that
33 NPOSTFIX = 0 and NDIRECT = 0. */
34 #define MAX_SIMPLE_DISTANCE_ALPHABET_SIZE \
35 BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_LARGE_MAX_DISTANCE_BITS)
36 /* MAX_SIMPLE_DISTANCE_ALPHABET_SIZE == 140 */
37
38 static BROTLI_INLINE uint32_t BlockLengthPrefixCode(uint32_t len) {
39 uint32_t code = (len >= 177) ? (len >= 753 ? 20 : 14) : (len >= 41 ? 7 : 0);
40 while (code < (BROTLI_NUM_BLOCK_LEN_SYMBOLS - 1) &&
41 len >= _kBrotliPrefixCodeRanges[code + 1].offset) ++code;
42 return code;
43 }
44
45 static BROTLI_INLINE void GetBlockLengthPrefixCode(uint32_t len, size_t* code,
46 uint32_t* n_extra, uint32_t* extra) {
47 *code = BlockLengthPrefixCode(len);
48 *n_extra = _kBrotliPrefixCodeRanges[*code].nbits;
49 *extra = len - _kBrotliPrefixCodeRanges[*code].offset;
50 }
51
52 typedef struct BlockTypeCodeCalculator {
53 size_t last_type;
54 size_t second_last_type;
55 } BlockTypeCodeCalculator;
56
57 static void InitBlockTypeCodeCalculator(BlockTypeCodeCalculator* self) {
58 self->last_type = 1;
59 self->second_last_type = 0;
60 }
61
62 static BROTLI_INLINE size_t NextBlockTypeCode(
63 BlockTypeCodeCalculator* calculator, uint8_t type) {
64 size_t type_code = (type == calculator->last_type + 1) ? 1u :
65 (type == calculator->second_last_type) ? 0u : type + 2u;
66 calculator->second_last_type = calculator->last_type;
67 calculator->last_type = type;
68 return type_code;
69 }
70
71 /* |nibblesbits| represents the 2 bits to encode MNIBBLES (0-3)
72 REQUIRES: length > 0
73 REQUIRES: length <= (1 << 24) */
74 static void BrotliEncodeMlen(size_t length, uint64_t* bits,
75 size_t* numbits, uint64_t* nibblesbits) {
76 size_t lg = (length == 1) ? 1 : Log2FloorNonZero((uint32_t)(length - 1)) + 1;
77 size_t mnibbles = (lg < 16 ? 16 : (lg + 3)) / 4;
78 BROTLI_DCHECK(length > 0);
79 BROTLI_DCHECK(length <= (1 << 24));
80 BROTLI_DCHECK(lg <= 24);
81 *nibblesbits = mnibbles - 4;
82 *numbits = mnibbles * 4;
83 *bits = length - 1;
84 }
85
86 static BROTLI_INLINE void StoreCommandExtra(
87 const Command* cmd, size_t* storage_ix, uint8_t* storage) {
88 uint32_t copylen_code = CommandCopyLenCode(cmd);
89 uint16_t inscode = GetInsertLengthCode(cmd->insert_len_);
90 uint16_t copycode = GetCopyLengthCode(copylen_code);
91 uint32_t insnumextra = GetInsertExtra(inscode);
92 uint64_t insextraval = cmd->insert_len_ - GetInsertBase(inscode);
93 uint64_t copyextraval = copylen_code - GetCopyBase(copycode);
94 uint64_t bits = (copyextraval << insnumextra) | insextraval;
95 BrotliWriteBits(
96 insnumextra + GetCopyExtra(copycode), bits, storage_ix, storage);
97 }
98
99 /* Data structure that stores almost everything that is needed to encode each
100 block switch command. */
101 typedef struct BlockSplitCode {
102 BlockTypeCodeCalculator type_code_calculator;
103 uint8_t type_depths[BROTLI_MAX_BLOCK_TYPE_SYMBOLS];
104 uint16_t type_bits[BROTLI_MAX_BLOCK_TYPE_SYMBOLS];
105 uint8_t length_depths[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
106 uint16_t length_bits[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
107 } BlockSplitCode;
108
109 /* Stores a number between 0 and 255. */
110 static void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage) {
111 if (n == 0) {
112 BrotliWriteBits(1, 0, storage_ix, storage);
113 } else {
114 size_t nbits = Log2FloorNonZero(n);
115 BrotliWriteBits(1, 1, storage_ix, storage);
116 BrotliWriteBits(3, nbits, storage_ix, storage);
117 BrotliWriteBits(nbits, n - ((size_t)1 << nbits), storage_ix, storage);
118 }
119 }
120
121 /* Stores the compressed meta-block header.
122 REQUIRES: length > 0
123 REQUIRES: length <= (1 << 24) */
124 static void StoreCompressedMetaBlockHeader(BROTLI_BOOL is_final_block,
125 size_t length,
126 size_t* storage_ix,
127 uint8_t* storage) {
128 uint64_t lenbits;
129 size_t nlenbits;
130 uint64_t nibblesbits;
131
132 /* Write ISLAST bit. */
133 BrotliWriteBits(1, (uint64_t)is_final_block, storage_ix, storage);
134 /* Write ISEMPTY bit. */
135 if (is_final_block) {
136 BrotliWriteBits(1, 0, storage_ix, storage);
137 }
138
139 BrotliEncodeMlen(length, &lenbits, &nlenbits, &nibblesbits);
140 BrotliWriteBits(2, nibblesbits, storage_ix, storage);
141 BrotliWriteBits(nlenbits, lenbits, storage_ix, storage);
142
143 if (!is_final_block) {
144 /* Write ISUNCOMPRESSED bit. */
145 BrotliWriteBits(1, 0, storage_ix, storage);
146 }
147 }
148
149 /* Stores the uncompressed meta-block header.
150 REQUIRES: length > 0
151 REQUIRES: length <= (1 << 24) */
152 static void BrotliStoreUncompressedMetaBlockHeader(size_t length,
153 size_t* storage_ix,
154 uint8_t* storage) {
155 uint64_t lenbits;
156 size_t nlenbits;
157 uint64_t nibblesbits;
158
159 /* Write ISLAST bit.
160 Uncompressed block cannot be the last one, so set to 0. */
161 BrotliWriteBits(1, 0, storage_ix, storage);
162 BrotliEncodeMlen(length, &lenbits, &nlenbits, &nibblesbits);
163 BrotliWriteBits(2, nibblesbits, storage_ix, storage);
164 BrotliWriteBits(nlenbits, lenbits, storage_ix, storage);
165 /* Write ISUNCOMPRESSED bit. */
166 BrotliWriteBits(1, 1, storage_ix, storage);
167 }
168
169 static void BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(
170 const int num_codes, const uint8_t* code_length_bitdepth,
171 size_t* storage_ix, uint8_t* storage) {
172 static const uint8_t kStorageOrder[BROTLI_CODE_LENGTH_CODES] = {
173 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15
174 };
175 /* The bit lengths of the Huffman code over the code length alphabet
176 are compressed with the following static Huffman code:
177 Symbol Code
178 ------ ----
179 0 00
180 1 1110
181 2 110
182 3 01
183 4 10
184 5 1111 */
185 static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = {
186 0, 7, 3, 2, 1, 15
187 };
188 static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = {
189 2, 4, 3, 2, 2, 4
190 };
191
192 size_t skip_some = 0; /* skips none. */
193
194 /* Throw away trailing zeros: */
195 size_t codes_to_store = BROTLI_CODE_LENGTH_CODES;
196 if (num_codes > 1) {
197 for (; codes_to_store > 0; --codes_to_store) {
198 if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
199 break;
200 }
201 }
202 }
203 if (code_length_bitdepth[kStorageOrder[0]] == 0 &&
204 code_length_bitdepth[kStorageOrder[1]] == 0) {
205 skip_some = 2; /* skips two. */
206 if (code_length_bitdepth[kStorageOrder[2]] == 0) {
207 skip_some = 3; /* skips three. */
208 }
209 }
210 BrotliWriteBits(2, skip_some, storage_ix, storage);
211 {
212 size_t i;
213 for (i = skip_some; i < codes_to_store; ++i) {
214 size_t l = code_length_bitdepth[kStorageOrder[i]];
215 BrotliWriteBits(kHuffmanBitLengthHuffmanCodeBitLengths[l],
216 kHuffmanBitLengthHuffmanCodeSymbols[l], storage_ix, storage);
217 }
218 }
219 }
220
221 static void BrotliStoreHuffmanTreeToBitMask(
222 const size_t huffman_tree_size, const uint8_t* huffman_tree,
223 const uint8_t* huffman_tree_extra_bits, const uint8_t* code_length_bitdepth,
224 const uint16_t* code_length_bitdepth_symbols,
225 size_t* BROTLI_RESTRICT storage_ix, uint8_t* BROTLI_RESTRICT storage) {
226 size_t i;
227 for (i = 0; i < huffman_tree_size; ++i) {
228 size_t ix = huffman_tree[i];
229 BrotliWriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix],
230 storage_ix, storage);
231 /* Extra bits */
232 switch (ix) {
233 case BROTLI_REPEAT_PREVIOUS_CODE_LENGTH:
234 BrotliWriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage);
235 break;
236 case BROTLI_REPEAT_ZERO_CODE_LENGTH:
237 BrotliWriteBits(3, huffman_tree_extra_bits[i], storage_ix, storage);
238 break;
239 }
240 }
241 }
242
243 static void StoreSimpleHuffmanTree(const uint8_t* depths,
244 size_t symbols[4],
245 size_t num_symbols,
246 size_t max_bits,
247 size_t* storage_ix, uint8_t* storage) {
248 /* value of 1 indicates a simple Huffman code */
249 BrotliWriteBits(2, 1, storage_ix, storage);
250 BrotliWriteBits(2, num_symbols - 1, storage_ix, storage); /* NSYM - 1 */
251
252 {
253 /* Sort */
254 size_t i;
255 for (i = 0; i < num_symbols; i++) {
256 size_t j;
257 for (j = i + 1; j < num_symbols; j++) {
258 if (depths[symbols[j]] < depths[symbols[i]]) {
259 BROTLI_SWAP(size_t, symbols, j, i);
260 }
261 }
262 }
263 }
264
265 if (num_symbols == 2) {
266 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
267 BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
268 } else if (num_symbols == 3) {
269 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
270 BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
271 BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
272 } else {
273 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
274 BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
275 BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
276 BrotliWriteBits(max_bits, symbols[3], storage_ix, storage);
277 /* tree-select */
278 BrotliWriteBits(1, depths[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
279 }
280 }
281
282 /* num = alphabet size
283 depths = symbol depths */
284 void BrotliStoreHuffmanTree(const uint8_t* depths, size_t num,
285 HuffmanTree* tree,
286 size_t* storage_ix, uint8_t* storage) {
287 /* Write the Huffman tree into the brotli-representation.
288 The command alphabet is the largest, so this allocation will fit all
289 alphabets. */
290 /* TODO(eustas): fix me */
291 uint8_t huffman_tree[BROTLI_NUM_COMMAND_SYMBOLS];
292 uint8_t huffman_tree_extra_bits[BROTLI_NUM_COMMAND_SYMBOLS];
293 size_t huffman_tree_size = 0;
294 uint8_t code_length_bitdepth[BROTLI_CODE_LENGTH_CODES] = { 0 };
295 uint16_t code_length_bitdepth_symbols[BROTLI_CODE_LENGTH_CODES];
296 uint32_t huffman_tree_histogram[BROTLI_CODE_LENGTH_CODES] = { 0 };
297 size_t i;
298 int num_codes = 0;
299 size_t code = 0;
300
301 BROTLI_DCHECK(num <= BROTLI_NUM_COMMAND_SYMBOLS);
302
303 BrotliWriteHuffmanTree(depths, num, &huffman_tree_size, huffman_tree,
304 huffman_tree_extra_bits);
305
306 /* Calculate the statistics of the Huffman tree in brotli-representation. */
307 for (i = 0; i < huffman_tree_size; ++i) {
308 ++huffman_tree_histogram[huffman_tree[i]];
309 }
310
311 for (i = 0; i < BROTLI_CODE_LENGTH_CODES; ++i) {
312 if (huffman_tree_histogram[i]) {
313 if (num_codes == 0) {
314 code = i;
315 num_codes = 1;
316 } else if (num_codes == 1) {
317 num_codes = 2;
318 break;
319 }
320 }
321 }
322
323 /* Calculate another Huffman tree to use for compressing both the
324 earlier Huffman tree with. */
325 BrotliCreateHuffmanTree(huffman_tree_histogram, BROTLI_CODE_LENGTH_CODES,
326 5, tree, code_length_bitdepth);
327 BrotliConvertBitDepthsToSymbols(code_length_bitdepth,
328 BROTLI_CODE_LENGTH_CODES,
329 code_length_bitdepth_symbols);
330
331 /* Now, we have all the data, let's start storing it */
332 BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth,
333 storage_ix, storage);
334
335 if (num_codes == 1) {
336 code_length_bitdepth[code] = 0;
337 }
338
339 /* Store the real Huffman tree now. */
340 BrotliStoreHuffmanTreeToBitMask(huffman_tree_size,
341 huffman_tree,
342 huffman_tree_extra_bits,
343 code_length_bitdepth,
344 code_length_bitdepth_symbols,
345 storage_ix, storage);
346 }
347
348 /* Builds a Huffman tree from histogram[0:length] into depth[0:length] and
349 bits[0:length] and stores the encoded tree to the bit stream. */
350 static void BuildAndStoreHuffmanTree(const uint32_t* histogram,
351 const size_t histogram_length,
352 const size_t alphabet_size,
353 HuffmanTree* tree,
354 uint8_t* depth,
355 uint16_t* bits,
356 size_t* storage_ix,
357 uint8_t* storage) {
358 size_t count = 0;
359 size_t s4[4] = { 0 };
360 size_t i;
361 size_t max_bits = 0;
362 for (i = 0; i < histogram_length; i++) {
363 if (histogram[i]) {
364 if (count < 4) {
365 s4[count] = i;
366 } else if (count > 4) {
367 break;
368 }
369 count++;
370 }
371 }
372
373 {
374 size_t max_bits_counter = alphabet_size - 1;
375 while (max_bits_counter) {
376 max_bits_counter >>= 1;
377 ++max_bits;
378 }
379 }
380
381 if (count <= 1) {
382 BrotliWriteBits(4, 1, storage_ix, storage);
383 BrotliWriteBits(max_bits, s4[0], storage_ix, storage);
384 depth[s4[0]] = 0;
385 bits[s4[0]] = 0;
386 return;
387 }
388
389 memset(depth, 0, histogram_length * sizeof(depth[0]));
390 BrotliCreateHuffmanTree(histogram, histogram_length, 15, tree, depth);
391 BrotliConvertBitDepthsToSymbols(depth, histogram_length, bits);
392
393 if (count <= 4) {
394 StoreSimpleHuffmanTree(depth, s4, count, max_bits, storage_ix, storage);
395 } else {
396 BrotliStoreHuffmanTree(depth, histogram_length, tree, storage_ix, storage);
397 }
398 }
399
400 static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree(
401 const HuffmanTree* v0, const HuffmanTree* v1) {
402 return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_);
403 }
404
405 void BrotliBuildAndStoreHuffmanTreeFast(HuffmanTree* tree,
406 const uint32_t* histogram,
407 const size_t histogram_total,
408 const size_t max_bits,
409 uint8_t* depth, uint16_t* bits,
410 size_t* storage_ix,
411 uint8_t* storage) {
412 size_t count = 0;
413 size_t symbols[4] = { 0 };
414 size_t length = 0;
415 size_t total = histogram_total;
416 while (total != 0) {
417 if (histogram[length]) {
418 if (count < 4) {
419 symbols[count] = length;
420 }
421 ++count;
422 total -= histogram[length];
423 }
424 ++length;
425 }
426
427 if (count <= 1) {
428 BrotliWriteBits(4, 1, storage_ix, storage);
429 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
430 depth[symbols[0]] = 0;
431 bits[symbols[0]] = 0;
432 return;
433 }
434
435 memset(depth, 0, length * sizeof(depth[0]));
436 {
437 uint32_t count_limit;
438 for (count_limit = 1; ; count_limit *= 2) {
439 HuffmanTree* node = tree;
440 size_t l;
441 for (l = length; l != 0;) {
442 --l;
443 if (histogram[l]) {
444 if (BROTLI_PREDICT_TRUE(histogram[l] >= count_limit)) {
445 InitHuffmanTree(node, histogram[l], -1, (int16_t)l);
446 } else {
447 InitHuffmanTree(node, count_limit, -1, (int16_t)l);
448 }
449 ++node;
450 }
451 }
452 {
453 const int n = (int)(node - tree);
454 HuffmanTree sentinel;
455 int i = 0; /* Points to the next leaf node. */
456 int j = n + 1; /* Points to the next non-leaf node. */
457 int k;
458
459 SortHuffmanTreeItems(tree, (size_t)n, SortHuffmanTree);
460 /* The nodes are:
461 [0, n): the sorted leaf nodes that we start with.
462 [n]: we add a sentinel here.
463 [n + 1, 2n): new parent nodes are added here, starting from
464 (n+1). These are naturally in ascending order.
465 [2n]: we add a sentinel at the end as well.
466 There will be (2n+1) elements at the end. */
467 InitHuffmanTree(&sentinel, BROTLI_UINT32_MAX, -1, -1);
468 *node++ = sentinel;
469 *node++ = sentinel;
470
471 for (k = n - 1; k > 0; --k) {
472 int left, right;
473 if (tree[i].total_count_ <= tree[j].total_count_) {
474 left = i;
475 ++i;
476 } else {
477 left = j;
478 ++j;
479 }
480 if (tree[i].total_count_ <= tree[j].total_count_) {
481 right = i;
482 ++i;
483 } else {
484 right = j;
485 ++j;
486 }
487 /* The sentinel node becomes the parent node. */
488 node[-1].total_count_ =
489 tree[left].total_count_ + tree[right].total_count_;
490 node[-1].index_left_ = (int16_t)left;
491 node[-1].index_right_or_value_ = (int16_t)right;
492 /* Add back the last sentinel node. */
493 *node++ = sentinel;
494 }
495 if (BrotliSetDepth(2 * n - 1, tree, depth, 14)) {
496 /* We need to pack the Huffman tree in 14 bits. If this was not
497 successful, add fake entities to the lowest values and retry. */
498 break;
499 }
500 }
501 }
502 }
503 BrotliConvertBitDepthsToSymbols(depth, length, bits);
504 if (count <= 4) {
505 size_t i;
506 /* value of 1 indicates a simple Huffman code */
507 BrotliWriteBits(2, 1, storage_ix, storage);
508 BrotliWriteBits(2, count - 1, storage_ix, storage); /* NSYM - 1 */
509
510 /* Sort */
511 for (i = 0; i < count; i++) {
512 size_t j;
513 for (j = i + 1; j < count; j++) {
514 if (depth[symbols[j]] < depth[symbols[i]]) {
515 BROTLI_SWAP(size_t, symbols, j, i);
516 }
517 }
518 }
519
520 if (count == 2) {
521 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
522 BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
523 } else if (count == 3) {
524 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
525 BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
526 BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
527 } else {
528 BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
529 BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
530 BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
531 BrotliWriteBits(max_bits, symbols[3], storage_ix, storage);
532 /* tree-select */
533 BrotliWriteBits(1, depth[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
534 }
535 } else {
536 uint8_t previous_value = 8;
537 size_t i;
538 /* Complex Huffman Tree */
539 StoreStaticCodeLengthCode(storage_ix, storage);
540
541 /* Actual RLE coding. */
542 for (i = 0; i < length;) {
543 const uint8_t value = depth[i];
544 size_t reps = 1;
545 size_t k;
546 for (k = i + 1; k < length && depth[k] == value; ++k) {
547 ++reps;
548 }
549 i += reps;
550 if (value == 0) {
551 BrotliWriteBits(kZeroRepsDepth[reps], kZeroRepsBits[reps],
552 storage_ix, storage);
553 } else {
554 if (previous_value != value) {
555 BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
556 storage_ix, storage);
557 --reps;
558 }
559 if (reps < 3) {
560 while (reps != 0) {
561 reps--;
562 BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
563 storage_ix, storage);
564 }
565 } else {
566 reps -= 3;
567 BrotliWriteBits(kNonZeroRepsDepth[reps], kNonZeroRepsBits[reps],
568 storage_ix, storage);
569 }
570 previous_value = value;
571 }
572 }
573 }
574 }
575
576 static size_t IndexOf(const uint8_t* v, size_t v_size, uint8_t value) {
577 size_t i = 0;
578 for (; i < v_size; ++i) {
579 if (v[i] == value) return i;
580 }
581 return i;
582 }
583
584 static void MoveToFront(uint8_t* v, size_t index) {
585 uint8_t value = v[index];
586 size_t i;
587 for (i = index; i != 0; --i) {
588 v[i] = v[i - 1];
589 }
590 v[0] = value;
591 }
592
593 static void MoveToFrontTransform(const uint32_t* BROTLI_RESTRICT v_in,
594 const size_t v_size,
595 uint32_t* v_out) {
596 size_t i;
597 uint8_t mtf[256];
598 uint32_t max_value;
599 if (v_size == 0) {
600 return;
601 }
602 max_value = v_in[0];
603 for (i = 1; i < v_size; ++i) {
604 if (v_in[i] > max_value) max_value = v_in[i];
605 }
606 BROTLI_DCHECK(max_value < 256u);
607 for (i = 0; i <= max_value; ++i) {
608 mtf[i] = (uint8_t)i;
609 }
610 {
611 size_t mtf_size = max_value + 1;
612 for (i = 0; i < v_size; ++i) {
613 size_t index = IndexOf(mtf, mtf_size, (uint8_t)v_in[i]);
614 BROTLI_DCHECK(index < mtf_size);
615 v_out[i] = (uint32_t)index;
616 MoveToFront(mtf, index);
617 }
618 }
619 }
620
621 /* Finds runs of zeros in v[0..in_size) and replaces them with a prefix code of
622 the run length plus extra bits (lower 9 bits is the prefix code and the rest
623 are the extra bits). Non-zero values in v[] are shifted by
624 *max_length_prefix. Will not create prefix codes bigger than the initial
625 value of *max_run_length_prefix. The prefix code of run length L is simply
626 Log2Floor(L) and the number of extra bits is the same as the prefix code. */
627 static void RunLengthCodeZeros(const size_t in_size,
628 uint32_t* BROTLI_RESTRICT v, size_t* BROTLI_RESTRICT out_size,
629 uint32_t* BROTLI_RESTRICT max_run_length_prefix) {
630 uint32_t max_reps = 0;
631 size_t i;
632 uint32_t max_prefix;
633 for (i = 0; i < in_size;) {
634 uint32_t reps = 0;
635 for (; i < in_size && v[i] != 0; ++i) ;
636 for (; i < in_size && v[i] == 0; ++i) {
637 ++reps;
638 }
639 max_reps = BROTLI_MAX(uint32_t, reps, max_reps);
640 }
641 max_prefix = max_reps > 0 ? Log2FloorNonZero(max_reps) : 0;
642 max_prefix = BROTLI_MIN(uint32_t, max_prefix, *max_run_length_prefix);
643 *max_run_length_prefix = max_prefix;
644 *out_size = 0;
645 for (i = 0; i < in_size;) {
646 BROTLI_DCHECK(*out_size <= i);
647 if (v[i] != 0) {
648 v[*out_size] = v[i] + *max_run_length_prefix;
649 ++i;
650 ++(*out_size);
651 } else {
652 uint32_t reps = 1;
653 size_t k;
654 for (k = i + 1; k < in_size && v[k] == 0; ++k) {
655 ++reps;
656 }
657 i += reps;
658 while (reps != 0) {
659 if (reps < (2u << max_prefix)) {
660 uint32_t run_length_prefix = Log2FloorNonZero(reps);
661 const uint32_t extra_bits = reps - (1u << run_length_prefix);
662 v[*out_size] = run_length_prefix + (extra_bits << 9);
663 ++(*out_size);
664 break;
665 } else {
666 const uint32_t extra_bits = (1u << max_prefix) - 1u;
667 v[*out_size] = max_prefix + (extra_bits << 9);
668 reps -= (2u << max_prefix) - 1u;
669 ++(*out_size);
670 }
671 }
672 }
673 }
674 }
675
676 #define SYMBOL_BITS 9
677
678 typedef struct EncodeContextMapArena {
679 uint32_t histogram[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
680 uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
681 uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
682 } EncodeContextMapArena;
683
684 static void EncodeContextMap(MemoryManager* m,
685 EncodeContextMapArena* arena,
686 const uint32_t* context_map,
687 size_t context_map_size,
688 size_t num_clusters,
689 HuffmanTree* tree,
690 size_t* storage_ix, uint8_t* storage) {
691 size_t i;
692 uint32_t* rle_symbols;
693 uint32_t max_run_length_prefix = 6;
694 size_t num_rle_symbols = 0;
695 uint32_t* BROTLI_RESTRICT const histogram = arena->histogram;
696 static const uint32_t kSymbolMask = (1u << SYMBOL_BITS) - 1u;
697 uint8_t* BROTLI_RESTRICT const depths = arena->depths;
698 uint16_t* BROTLI_RESTRICT const bits = arena->bits;
699
700 StoreVarLenUint8(num_clusters - 1, storage_ix, storage);
701
702 if (num_clusters == 1) {
703 return;
704 }
705
706 rle_symbols = BROTLI_ALLOC(m, uint32_t, context_map_size);
707 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(rle_symbols)) return;
708 MoveToFrontTransform(context_map, context_map_size, rle_symbols);
709 RunLengthCodeZeros(context_map_size, rle_symbols,
710 &num_rle_symbols, &max_run_length_prefix);
711 memset(histogram, 0, sizeof(arena->histogram));
712 for (i = 0; i < num_rle_symbols; ++i) {
713 ++histogram[rle_symbols[i] & kSymbolMask];
714 }
715 {
716 BROTLI_BOOL use_rle = TO_BROTLI_BOOL(max_run_length_prefix > 0);
717 BrotliWriteBits(1, (uint64_t)use_rle, storage_ix, storage);
718 if (use_rle) {
719 BrotliWriteBits(4, max_run_length_prefix - 1, storage_ix, storage);
720 }
721 }
722 BuildAndStoreHuffmanTree(histogram, num_clusters + max_run_length_prefix,
723 num_clusters + max_run_length_prefix,
724 tree, depths, bits, storage_ix, storage);
725 for (i = 0; i < num_rle_symbols; ++i) {
726 const uint32_t rle_symbol = rle_symbols[i] & kSymbolMask;
727 const uint32_t extra_bits_val = rle_symbols[i] >> SYMBOL_BITS;
728 BrotliWriteBits(depths[rle_symbol], bits[rle_symbol], storage_ix, storage);
729 if (rle_symbol > 0 && rle_symbol <= max_run_length_prefix) {
730 BrotliWriteBits(rle_symbol, extra_bits_val, storage_ix, storage);
731 }
732 }
733 BrotliWriteBits(1, 1, storage_ix, storage); /* use move-to-front */
734 BROTLI_FREE(m, rle_symbols);
735 }
736
737 /* Stores the block switch command with index block_ix to the bit stream. */
738 static BROTLI_INLINE void StoreBlockSwitch(BlockSplitCode* code,
739 const uint32_t block_len,
740 const uint8_t block_type,
741 BROTLI_BOOL is_first_block,
742 size_t* storage_ix,
743 uint8_t* storage) {
744 size_t typecode = NextBlockTypeCode(&code->type_code_calculator, block_type);
745 size_t lencode;
746 uint32_t len_nextra;
747 uint32_t len_extra;
748 if (!is_first_block) {
749 BrotliWriteBits(code->type_depths[typecode], code->type_bits[typecode],
750 storage_ix, storage);
751 }
752 GetBlockLengthPrefixCode(block_len, &lencode, &len_nextra, &len_extra);
753
754 BrotliWriteBits(code->length_depths[lencode], code->length_bits[lencode],
755 storage_ix, storage);
756 BrotliWriteBits(len_nextra, len_extra, storage_ix, storage);
757 }
758
759 /* Builds a BlockSplitCode data structure from the block split given by the
760 vector of block types and block lengths and stores it to the bit stream. */
761 static void BuildAndStoreBlockSplitCode(const uint8_t* types,
762 const uint32_t* lengths,
763 const size_t num_blocks,
764 const size_t num_types,
765 HuffmanTree* tree,
766 BlockSplitCode* code,
767 size_t* storage_ix,
768 uint8_t* storage) {
769 uint32_t type_histo[BROTLI_MAX_BLOCK_TYPE_SYMBOLS];
770 uint32_t length_histo[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
771 size_t i;
772 BlockTypeCodeCalculator type_code_calculator;
773 memset(type_histo, 0, (num_types + 2) * sizeof(type_histo[0]));
774 memset(length_histo, 0, sizeof(length_histo));
775 InitBlockTypeCodeCalculator(&type_code_calculator);
776 for (i = 0; i < num_blocks; ++i) {
777 size_t type_code = NextBlockTypeCode(&type_code_calculator, types[i]);
778 if (i != 0) ++type_histo[type_code];
779 ++length_histo[BlockLengthPrefixCode(lengths[i])];
780 }
781 StoreVarLenUint8(num_types - 1, storage_ix, storage);
782 if (num_types > 1) { /* TODO(eustas): else? could StoreBlockSwitch occur? */
783 BuildAndStoreHuffmanTree(&type_histo[0], num_types + 2, num_types + 2, tree,
784 &code->type_depths[0], &code->type_bits[0],
785 storage_ix, storage);
786 BuildAndStoreHuffmanTree(&length_histo[0], BROTLI_NUM_BLOCK_LEN_SYMBOLS,
787 BROTLI_NUM_BLOCK_LEN_SYMBOLS,
788 tree, &code->length_depths[0],
789 &code->length_bits[0], storage_ix, storage);
790 StoreBlockSwitch(code, lengths[0], types[0], 1, storage_ix, storage);
791 }
792 }
793
794 /* Stores a context map where the histogram type is always the block type. */
795 static void StoreTrivialContextMap(EncodeContextMapArena* arena,
796 size_t num_types,
797 size_t context_bits,
798 HuffmanTree* tree,
799 size_t* storage_ix,
800 uint8_t* storage) {
801 StoreVarLenUint8(num_types - 1, storage_ix, storage);
802 if (num_types > 1) {
803 size_t repeat_code = context_bits - 1u;
804 size_t repeat_bits = (1u << repeat_code) - 1u;
805 size_t alphabet_size = num_types + repeat_code;
806 uint32_t* BROTLI_RESTRICT const histogram = arena->histogram;
807 uint8_t* BROTLI_RESTRICT const depths = arena->depths;
808 uint16_t* BROTLI_RESTRICT const bits = arena->bits;
809 size_t i;
810 memset(histogram, 0, alphabet_size * sizeof(histogram[0]));
811 /* Write RLEMAX. */
812 BrotliWriteBits(1, 1, storage_ix, storage);
813 BrotliWriteBits(4, repeat_code - 1, storage_ix, storage);
814 histogram[repeat_code] = (uint32_t)num_types;
815 histogram[0] = 1;
816 for (i = context_bits; i < alphabet_size; ++i) {
817 histogram[i] = 1;
818 }
819 BuildAndStoreHuffmanTree(histogram, alphabet_size, alphabet_size,
820 tree, depths, bits, storage_ix, storage);
821 for (i = 0; i < num_types; ++i) {
822 size_t code = (i == 0 ? 0 : i + context_bits - 1);
823 BrotliWriteBits(depths[code], bits[code], storage_ix, storage);
824 BrotliWriteBits(
825 depths[repeat_code], bits[repeat_code], storage_ix, storage);
826 BrotliWriteBits(repeat_code, repeat_bits, storage_ix, storage);
827 }
828 /* Write IMTF (inverse-move-to-front) bit. */
829 BrotliWriteBits(1, 1, storage_ix, storage);
830 }
831 }
832
833 /* Manages the encoding of one block category (literal, command or distance). */
834 typedef struct BlockEncoder {
835 size_t histogram_length_;
836 size_t num_block_types_;
837 const uint8_t* block_types_; /* Not owned. */
838 const uint32_t* block_lengths_; /* Not owned. */
839 size_t num_blocks_;
840 BlockSplitCode block_split_code_;
841 size_t block_ix_;
842 size_t block_len_;
843 size_t entropy_ix_;
844 uint8_t* depths_;
845 uint16_t* bits_;
846 } BlockEncoder;
847
848 static void InitBlockEncoder(BlockEncoder* self, size_t histogram_length,
849 size_t num_block_types, const uint8_t* block_types,
850 const uint32_t* block_lengths, const size_t num_blocks) {
851 self->histogram_length_ = histogram_length;
852 self->num_block_types_ = num_block_types;
853 self->block_types_ = block_types;
854 self->block_lengths_ = block_lengths;
855 self->num_blocks_ = num_blocks;
856 InitBlockTypeCodeCalculator(&self->block_split_code_.type_code_calculator);
857 self->block_ix_ = 0;
858 self->block_len_ = num_blocks == 0 ? 0 : block_lengths[0];
859 self->entropy_ix_ = 0;
860 self->depths_ = 0;
861 self->bits_ = 0;
862 }
863
864 static void CleanupBlockEncoder(MemoryManager* m, BlockEncoder* self) {
865 BROTLI_FREE(m, self->depths_);
866 BROTLI_FREE(m, self->bits_);
867 }
868
869 /* Creates entropy codes of block lengths and block types and stores them
870 to the bit stream. */
871 static void BuildAndStoreBlockSwitchEntropyCodes(BlockEncoder* self,
872 HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) {
873 BuildAndStoreBlockSplitCode(self->block_types_, self->block_lengths_,
874 self->num_blocks_, self->num_block_types_, tree, &self->block_split_code_,
875 storage_ix, storage);
876 }
877
878 /* Stores the next symbol with the entropy code of the current block type.
879 Updates the block type and block length at block boundaries. */
880 static void StoreSymbol(BlockEncoder* self, size_t symbol, size_t* storage_ix,
881 uint8_t* storage) {
882 if (self->block_len_ == 0) {
883 size_t block_ix = ++self->block_ix_;
884 uint32_t block_len = self->block_lengths_[block_ix];
885 uint8_t block_type = self->block_types_[block_ix];
886 self->block_len_ = block_len;
887 self->entropy_ix_ = block_type * self->histogram_length_;
888 StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0,
889 storage_ix, storage);
890 }
891 --self->block_len_;
892 {
893 size_t ix = self->entropy_ix_ + symbol;
894 BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage);
895 }
896 }
897
898 /* Stores the next symbol with the entropy code of the current block type and
899 context value.
900 Updates the block type and block length at block boundaries. */
901 static void StoreSymbolWithContext(BlockEncoder* self, size_t symbol,
902 size_t context, const uint32_t* context_map, size_t* storage_ix,
903 uint8_t* storage, const size_t context_bits) {
904 if (self->block_len_ == 0) {
905 size_t block_ix = ++self->block_ix_;
906 uint32_t block_len = self->block_lengths_[block_ix];
907 uint8_t block_type = self->block_types_[block_ix];
908 self->block_len_ = block_len;
909 self->entropy_ix_ = (size_t)block_type << context_bits;
910 StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0,
911 storage_ix, storage);
912 }
913 --self->block_len_;
914 {
915 size_t histo_ix = context_map[self->entropy_ix_ + context];
916 size_t ix = histo_ix * self->histogram_length_ + symbol;
917 BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage);
918 }
919 }
920
921 #define FN(X) X ## Literal
922 /* NOLINTNEXTLINE(build/include) */
923 #include "block_encoder_inc.h"
924 #undef FN
925
926 #define FN(X) X ## Command
927 /* NOLINTNEXTLINE(build/include) */
928 #include "block_encoder_inc.h"
929 #undef FN
930
931 #define FN(X) X ## Distance
932 /* NOLINTNEXTLINE(build/include) */
933 #include "block_encoder_inc.h"
934 #undef FN
935
936 static void JumpToByteBoundary(size_t* storage_ix, uint8_t* storage) {
937 *storage_ix = (*storage_ix + 7u) & ~7u;
938 storage[*storage_ix >> 3] = 0;
939 }
940
941 typedef struct StoreMetablockArena {
942 BlockEncoder literal_enc;
943 BlockEncoder command_enc;
944 BlockEncoder distance_enc;
945 EncodeContextMapArena context_map_arena;
946 } StoreMetablockArena;
947
948 void BrotliStoreMetaBlock(MemoryManager* m,
949 const uint8_t* input, size_t start_pos, size_t length, size_t mask,
950 uint8_t prev_byte, uint8_t prev_byte2, BROTLI_BOOL is_last,
951 const BrotliEncoderParams* params, ContextType literal_context_mode,
952 const Command* commands, size_t n_commands, const MetaBlockSplit* mb,
953 size_t* storage_ix, uint8_t* storage) {
954
955 size_t pos = start_pos;
956 size_t i;
957 uint32_t num_distance_symbols = params->dist.alphabet_size_max;
958 uint32_t num_effective_distance_symbols = params->dist.alphabet_size_limit;
959 HuffmanTree* tree;
960 ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode);
961 StoreMetablockArena* arena = NULL;
962 BlockEncoder* literal_enc = NULL;
963 BlockEncoder* command_enc = NULL;
964 BlockEncoder* distance_enc = NULL;
965 const BrotliDistanceParams* dist = &params->dist;
966 BROTLI_DCHECK(
967 num_effective_distance_symbols <= BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS);
968
969 StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
970
971 tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE);
972 arena = BROTLI_ALLOC(m, StoreMetablockArena, 1);
973 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(tree) || BROTLI_IS_NULL(arena)) return;
974 literal_enc = &arena->literal_enc;
975 command_enc = &arena->command_enc;
976 distance_enc = &arena->distance_enc;
977 InitBlockEncoder(literal_enc, BROTLI_NUM_LITERAL_SYMBOLS,
978 mb->literal_split.num_types, mb->literal_split.types,
979 mb->literal_split.lengths, mb->literal_split.num_blocks);
980 InitBlockEncoder(command_enc, BROTLI_NUM_COMMAND_SYMBOLS,
981 mb->command_split.num_types, mb->command_split.types,
982 mb->command_split.lengths, mb->command_split.num_blocks);
983 InitBlockEncoder(distance_enc, num_effective_distance_symbols,
984 mb->distance_split.num_types, mb->distance_split.types,
985 mb->distance_split.lengths, mb->distance_split.num_blocks);
986
987 BuildAndStoreBlockSwitchEntropyCodes(literal_enc, tree, storage_ix, storage);
988 BuildAndStoreBlockSwitchEntropyCodes(command_enc, tree, storage_ix, storage);
989 BuildAndStoreBlockSwitchEntropyCodes(distance_enc, tree, storage_ix, storage);
990
991 BrotliWriteBits(2, dist->distance_postfix_bits, storage_ix, storage);
992 BrotliWriteBits(
993 4, dist->num_direct_distance_codes >> dist->distance_postfix_bits,
994 storage_ix, storage);
995 for (i = 0; i < mb->literal_split.num_types; ++i) {
996 BrotliWriteBits(2, literal_context_mode, storage_ix, storage);
997 }
998
999 if (mb->literal_context_map_size == 0) {
1000 StoreTrivialContextMap(
1001 &arena->context_map_arena, mb->literal_histograms_size,
1002 BROTLI_LITERAL_CONTEXT_BITS, tree, storage_ix, storage);
1003 } else {
1004 EncodeContextMap(m, &arena->context_map_arena,
1005 mb->literal_context_map, mb->literal_context_map_size,
1006 mb->literal_histograms_size, tree, storage_ix, storage);
1007 if (BROTLI_IS_OOM(m)) return;
1008 }
1009
1010 if (mb->distance_context_map_size == 0) {
1011 StoreTrivialContextMap(
1012 &arena->context_map_arena, mb->distance_histograms_size,
1013 BROTLI_DISTANCE_CONTEXT_BITS, tree, storage_ix, storage);
1014 } else {
1015 EncodeContextMap(m, &arena->context_map_arena,
1016 mb->distance_context_map, mb->distance_context_map_size,
1017 mb->distance_histograms_size, tree, storage_ix, storage);
1018 if (BROTLI_IS_OOM(m)) return;
1019 }
1020
1021 BuildAndStoreEntropyCodesLiteral(m, literal_enc, mb->literal_histograms,
1022 mb->literal_histograms_size, BROTLI_NUM_LITERAL_SYMBOLS, tree,
1023 storage_ix, storage);
1024 if (BROTLI_IS_OOM(m)) return;
1025 BuildAndStoreEntropyCodesCommand(m, command_enc, mb->command_histograms,
1026 mb->command_histograms_size, BROTLI_NUM_COMMAND_SYMBOLS, tree,
1027 storage_ix, storage);
1028 if (BROTLI_IS_OOM(m)) return;
1029 BuildAndStoreEntropyCodesDistance(m, distance_enc, mb->distance_histograms,
1030 mb->distance_histograms_size, num_distance_symbols, tree,
1031 storage_ix, storage);
1032 if (BROTLI_IS_OOM(m)) return;
1033 BROTLI_FREE(m, tree);
1034
1035 for (i = 0; i < n_commands; ++i) {
1036 const Command cmd = commands[i];
1037 size_t cmd_code = cmd.cmd_prefix_;
1038 StoreSymbol(command_enc, cmd_code, storage_ix, storage);
1039 StoreCommandExtra(&cmd, storage_ix, storage);
1040 if (mb->literal_context_map_size == 0) {
1041 size_t j;
1042 for (j = cmd.insert_len_; j != 0; --j) {
1043 StoreSymbol(literal_enc, input[pos & mask], storage_ix, storage);
1044 ++pos;
1045 }
1046 } else {
1047 size_t j;
1048 for (j = cmd.insert_len_; j != 0; --j) {
1049 size_t context =
1050 BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut);
1051 uint8_t literal = input[pos & mask];
1052 StoreSymbolWithContext(literal_enc, literal, context,
1053 mb->literal_context_map, storage_ix, storage,
1054 BROTLI_LITERAL_CONTEXT_BITS);
1055 prev_byte2 = prev_byte;
1056 prev_byte = literal;
1057 ++pos;
1058 }
1059 }
1060 pos += CommandCopyLen(&cmd);
1061 if (CommandCopyLen(&cmd)) {
1062 prev_byte2 = input[(pos - 2) & mask];
1063 prev_byte = input[(pos - 1) & mask];
1064 if (cmd.cmd_prefix_ >= 128) {
1065 size_t dist_code = cmd.dist_prefix_ & 0x3FF;
1066 uint32_t distnumextra = cmd.dist_prefix_ >> 10;
1067 uint64_t distextra = cmd.dist_extra_;
1068 if (mb->distance_context_map_size == 0) {
1069 StoreSymbol(distance_enc, dist_code, storage_ix, storage);
1070 } else {
1071 size_t context = CommandDistanceContext(&cmd);
1072 StoreSymbolWithContext(distance_enc, dist_code, context,
1073 mb->distance_context_map, storage_ix, storage,
1074 BROTLI_DISTANCE_CONTEXT_BITS);
1075 }
1076 BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
1077 }
1078 }
1079 }
1080 CleanupBlockEncoder(m, distance_enc);
1081 CleanupBlockEncoder(m, command_enc);
1082 CleanupBlockEncoder(m, literal_enc);
1083 BROTLI_FREE(m, arena);
1084 if (is_last) {
1085 JumpToByteBoundary(storage_ix, storage);
1086 }
1087 }
1088
1089 static void BuildHistograms(const uint8_t* input,
1090 size_t start_pos,
1091 size_t mask,
1092 const Command* commands,
1093 size_t n_commands,
1094 HistogramLiteral* lit_histo,
1095 HistogramCommand* cmd_histo,
1096 HistogramDistance* dist_histo) {
1097 size_t pos = start_pos;
1098 size_t i;
1099 for (i = 0; i < n_commands; ++i) {
1100 const Command cmd = commands[i];
1101 size_t j;
1102 HistogramAddCommand(cmd_histo, cmd.cmd_prefix_);
1103 for (j = cmd.insert_len_; j != 0; --j) {
1104 HistogramAddLiteral(lit_histo, input[pos & mask]);
1105 ++pos;
1106 }
1107 pos += CommandCopyLen(&cmd);
1108 if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
1109 HistogramAddDistance(dist_histo, cmd.dist_prefix_ & 0x3FF);
1110 }
1111 }
1112 }
1113
1114 static void StoreDataWithHuffmanCodes(const uint8_t* input,
1115 size_t start_pos,
1116 size_t mask,
1117 const Command* commands,
1118 size_t n_commands,
1119 const uint8_t* lit_depth,
1120 const uint16_t* lit_bits,
1121 const uint8_t* cmd_depth,
1122 const uint16_t* cmd_bits,
1123 const uint8_t* dist_depth,
1124 const uint16_t* dist_bits,
1125 size_t* storage_ix,
1126 uint8_t* storage) {
1127 size_t pos = start_pos;
1128 size_t i;
1129 for (i = 0; i < n_commands; ++i) {
1130 const Command cmd = commands[i];
1131 const size_t cmd_code = cmd.cmd_prefix_;
1132 size_t j;
1133 BrotliWriteBits(
1134 cmd_depth[cmd_code], cmd_bits[cmd_code], storage_ix, storage);
1135 StoreCommandExtra(&cmd, storage_ix, storage);
1136 for (j = cmd.insert_len_; j != 0; --j) {
1137 const uint8_t literal = input[pos & mask];
1138 BrotliWriteBits(
1139 lit_depth[literal], lit_bits[literal], storage_ix, storage);
1140 ++pos;
1141 }
1142 pos += CommandCopyLen(&cmd);
1143 if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
1144 const size_t dist_code = cmd.dist_prefix_ & 0x3FF;
1145 const uint32_t distnumextra = cmd.dist_prefix_ >> 10;
1146 const uint32_t distextra = cmd.dist_extra_;
1147 BrotliWriteBits(dist_depth[dist_code], dist_bits[dist_code],
1148 storage_ix, storage);
1149 BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
1150 }
1151 }
1152 }
1153
1154 /* TODO(eustas): pull alloc/dealloc to caller? */
1155 typedef struct MetablockArena {
1156 HistogramLiteral lit_histo;
1157 HistogramCommand cmd_histo;
1158 HistogramDistance dist_histo;
1159 /* TODO(eustas): merge bits and depth? */
1160 uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
1161 uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
1162 uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS];
1163 uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS];
1164 uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE];
1165 uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE];
1166 HuffmanTree tree[MAX_HUFFMAN_TREE_SIZE];
1167 } MetablockArena;
1168
1169 void BrotliStoreMetaBlockTrivial(MemoryManager* m,
1170 const uint8_t* input, size_t start_pos, size_t length, size_t mask,
1171 BROTLI_BOOL is_last, const BrotliEncoderParams* params,
1172 const Command* commands, size_t n_commands,
1173 size_t* storage_ix, uint8_t* storage) {
1174 MetablockArena* arena = BROTLI_ALLOC(m, MetablockArena, 1);
1175 uint32_t num_distance_symbols = params->dist.alphabet_size_max;
1176 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return;
1177
1178 StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
1179
1180 HistogramClearLiteral(&arena->lit_histo);
1181 HistogramClearCommand(&arena->cmd_histo);
1182 HistogramClearDistance(&arena->dist_histo);
1183
1184 BuildHistograms(input, start_pos, mask, commands, n_commands,
1185 &arena->lit_histo, &arena->cmd_histo, &arena->dist_histo);
1186
1187 BrotliWriteBits(13, 0, storage_ix, storage);
1188
1189 BuildAndStoreHuffmanTree(arena->lit_histo.data_, BROTLI_NUM_LITERAL_SYMBOLS,
1190 BROTLI_NUM_LITERAL_SYMBOLS, arena->tree,
1191 arena->lit_depth, arena->lit_bits,
1192 storage_ix, storage);
1193 BuildAndStoreHuffmanTree(arena->cmd_histo.data_, BROTLI_NUM_COMMAND_SYMBOLS,
1194 BROTLI_NUM_COMMAND_SYMBOLS, arena->tree,
1195 arena->cmd_depth, arena->cmd_bits,
1196 storage_ix, storage);
1197 BuildAndStoreHuffmanTree(arena->dist_histo.data_,
1198 MAX_SIMPLE_DISTANCE_ALPHABET_SIZE,
1199 num_distance_symbols, arena->tree,
1200 arena->dist_depth, arena->dist_bits,
1201 storage_ix, storage);
1202 StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
1203 n_commands, arena->lit_depth, arena->lit_bits,
1204 arena->cmd_depth, arena->cmd_bits,
1205 arena->dist_depth, arena->dist_bits,
1206 storage_ix, storage);
1207 BROTLI_FREE(m, arena);
1208 if (is_last) {
1209 JumpToByteBoundary(storage_ix, storage);
1210 }
1211 }
1212
1213 void BrotliStoreMetaBlockFast(MemoryManager* m,
1214 const uint8_t* input, size_t start_pos, size_t length, size_t mask,
1215 BROTLI_BOOL is_last, const BrotliEncoderParams* params,
1216 const Command* commands, size_t n_commands,
1217 size_t* storage_ix, uint8_t* storage) {
1218 MetablockArena* arena = BROTLI_ALLOC(m, MetablockArena, 1);
1219 uint32_t num_distance_symbols = params->dist.alphabet_size_max;
1220 uint32_t distance_alphabet_bits =
1221 Log2FloorNonZero(num_distance_symbols - 1) + 1;
1222 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return;
1223
1224 StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
1225
1226 BrotliWriteBits(13, 0, storage_ix, storage);
1227
1228 if (n_commands <= 128) {
1229 uint32_t histogram[BROTLI_NUM_LITERAL_SYMBOLS] = { 0 };
1230 size_t pos = start_pos;
1231 size_t num_literals = 0;
1232 size_t i;
1233 for (i = 0; i < n_commands; ++i) {
1234 const Command cmd = commands[i];
1235 size_t j;
1236 for (j = cmd.insert_len_; j != 0; --j) {
1237 ++histogram[input[pos & mask]];
1238 ++pos;
1239 }
1240 num_literals += cmd.insert_len_;
1241 pos += CommandCopyLen(&cmd);
1242 }
1243 BrotliBuildAndStoreHuffmanTreeFast(arena->tree, histogram, num_literals,
1244 /* max_bits = */ 8,
1245 arena->lit_depth, arena->lit_bits,
1246 storage_ix, storage);
1247 StoreStaticCommandHuffmanTree(storage_ix, storage);
1248 StoreStaticDistanceHuffmanTree(storage_ix, storage);
1249 StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
1250 n_commands, arena->lit_depth, arena->lit_bits,
1251 kStaticCommandCodeDepth,
1252 kStaticCommandCodeBits,
1253 kStaticDistanceCodeDepth,
1254 kStaticDistanceCodeBits,
1255 storage_ix, storage);
1256 } else {
1257 HistogramClearLiteral(&arena->lit_histo);
1258 HistogramClearCommand(&arena->cmd_histo);
1259 HistogramClearDistance(&arena->dist_histo);
1260 BuildHistograms(input, start_pos, mask, commands, n_commands,
1261 &arena->lit_histo, &arena->cmd_histo, &arena->dist_histo);
1262 BrotliBuildAndStoreHuffmanTreeFast(arena->tree, arena->lit_histo.data_,
1263 arena->lit_histo.total_count_,
1264 /* max_bits = */ 8,
1265 arena->lit_depth, arena->lit_bits,
1266 storage_ix, storage);
1267 BrotliBuildAndStoreHuffmanTreeFast(arena->tree, arena->cmd_histo.data_,
1268 arena->cmd_histo.total_count_,
1269 /* max_bits = */ 10,
1270 arena->cmd_depth, arena->cmd_bits,
1271 storage_ix, storage);
1272 BrotliBuildAndStoreHuffmanTreeFast(arena->tree, arena->dist_histo.data_,
1273 arena->dist_histo.total_count_,
1274 /* max_bits = */
1275 distance_alphabet_bits,
1276 arena->dist_depth, arena->dist_bits,
1277 storage_ix, storage);
1278 StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
1279 n_commands, arena->lit_depth, arena->lit_bits,
1280 arena->cmd_depth, arena->cmd_bits,
1281 arena->dist_depth, arena->dist_bits,
1282 storage_ix, storage);
1283 }
1284
1285 BROTLI_FREE(m, arena);
1286
1287 if (is_last) {
1288 JumpToByteBoundary(storage_ix, storage);
1289 }
1290 }
1291
1292 /* This is for storing uncompressed blocks (simple raw storage of
1293 bytes-as-bytes). */
1294 void BrotliStoreUncompressedMetaBlock(BROTLI_BOOL is_final_block,
1295 const uint8_t* BROTLI_RESTRICT input,
1296 size_t position, size_t mask,
1297 size_t len,
1298 size_t* BROTLI_RESTRICT storage_ix,
1299 uint8_t* BROTLI_RESTRICT storage) {
1300 size_t masked_pos = position & mask;
1301 BrotliStoreUncompressedMetaBlockHeader(len, storage_ix, storage);
1302 JumpToByteBoundary(storage_ix, storage);
1303
1304 if (masked_pos + len > mask + 1) {
1305 size_t len1 = mask + 1 - masked_pos;
1306 memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len1);
1307 *storage_ix += len1 << 3;
1308 len -= len1;
1309 masked_pos = 0;
1310 }
1311 memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len);
1312 *storage_ix += len << 3;
1313
1314 /* We need to clear the next 4 bytes to continue to be
1315 compatible with BrotliWriteBits. */
1316 BrotliWriteBitsPrepareStorage(*storage_ix, storage);
1317
1318 /* Since the uncompressed block itself may not be the final block, add an
1319 empty one after this. */
1320 if (is_final_block) {
1321 BrotliWriteBits(1, 1, storage_ix, storage); /* islast */
1322 BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */
1323 JumpToByteBoundary(storage_ix, storage);
1324 }
1325 }
1326
1327 #if defined(BROTLI_TEST)
1328 void GetBlockLengthPrefixCodeForTest(uint32_t len, size_t* code,
1329 uint32_t* n_extra, uint32_t* extra) {
1330 GetBlockLengthPrefixCode(len, code, n_extra, extra);
1331 }
1332 #endif
1333
1334 #if defined(__cplusplus) || defined(c_plusplus)
1335 } /* extern "C" */
1336 #endif