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