• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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)) 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)) 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;
960   uint32_t num_effective_distance_symbols = num_distance_symbols;
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 = &params->dist;
967   if (params->large_window &&
968       num_effective_distance_symbols > BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS) {
969     num_effective_distance_symbols = BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS;
970   }
971 
972   StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
973 
974   tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE);
975   if (BROTLI_IS_OOM(m)) return;
976   InitBlockEncoder(&literal_enc, BROTLI_NUM_LITERAL_SYMBOLS,
977       mb->literal_split.num_types, mb->literal_split.types,
978       mb->literal_split.lengths, mb->literal_split.num_blocks);
979   InitBlockEncoder(&command_enc, BROTLI_NUM_COMMAND_SYMBOLS,
980       mb->command_split.num_types, mb->command_split.types,
981       mb->command_split.lengths, mb->command_split.num_blocks);
982   InitBlockEncoder(&distance_enc, num_effective_distance_symbols,
983       mb->distance_split.num_types, mb->distance_split.types,
984       mb->distance_split.lengths, mb->distance_split.num_blocks);
985 
986   BuildAndStoreBlockSwitchEntropyCodes(&literal_enc, tree, storage_ix, storage);
987   BuildAndStoreBlockSwitchEntropyCodes(&command_enc, tree, storage_ix, storage);
988   BuildAndStoreBlockSwitchEntropyCodes(
989       &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(mb->literal_histograms_size,
1001         BROTLI_LITERAL_CONTEXT_BITS, tree, storage_ix, storage);
1002   } else {
1003     EncodeContextMap(m,
1004         mb->literal_context_map, mb->literal_context_map_size,
1005         mb->literal_histograms_size, tree, storage_ix, storage);
1006     if (BROTLI_IS_OOM(m)) return;
1007   }
1008 
1009   if (mb->distance_context_map_size == 0) {
1010     StoreTrivialContextMap(mb->distance_histograms_size,
1011         BROTLI_DISTANCE_CONTEXT_BITS, tree, storage_ix, storage);
1012   } else {
1013     EncodeContextMap(m,
1014         mb->distance_context_map, mb->distance_context_map_size,
1015         mb->distance_histograms_size, tree, storage_ix, storage);
1016     if (BROTLI_IS_OOM(m)) return;
1017   }
1018 
1019   BuildAndStoreEntropyCodesLiteral(m, &literal_enc, mb->literal_histograms,
1020       mb->literal_histograms_size, BROTLI_NUM_LITERAL_SYMBOLS, tree,
1021       storage_ix, storage);
1022   if (BROTLI_IS_OOM(m)) return;
1023   BuildAndStoreEntropyCodesCommand(m, &command_enc, mb->command_histograms,
1024       mb->command_histograms_size, BROTLI_NUM_COMMAND_SYMBOLS, tree,
1025       storage_ix, storage);
1026   if (BROTLI_IS_OOM(m)) return;
1027   BuildAndStoreEntropyCodesDistance(m, &distance_enc, mb->distance_histograms,
1028       mb->distance_histograms_size, num_distance_symbols, tree,
1029       storage_ix, storage);
1030   if (BROTLI_IS_OOM(m)) return;
1031   BROTLI_FREE(m, tree);
1032 
1033   for (i = 0; i < n_commands; ++i) {
1034     const Command cmd = commands[i];
1035     size_t cmd_code = cmd.cmd_prefix_;
1036     StoreSymbol(&command_enc, cmd_code, storage_ix, storage);
1037     StoreCommandExtra(&cmd, storage_ix, storage);
1038     if (mb->literal_context_map_size == 0) {
1039       size_t j;
1040       for (j = cmd.insert_len_; j != 0; --j) {
1041         StoreSymbol(&literal_enc, input[pos & mask], storage_ix, storage);
1042         ++pos;
1043       }
1044     } else {
1045       size_t j;
1046       for (j = cmd.insert_len_; j != 0; --j) {
1047         size_t context =
1048             BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut);
1049         uint8_t literal = input[pos & mask];
1050         StoreSymbolWithContext(&literal_enc, literal, context,
1051             mb->literal_context_map, storage_ix, storage,
1052             BROTLI_LITERAL_CONTEXT_BITS);
1053         prev_byte2 = prev_byte;
1054         prev_byte = literal;
1055         ++pos;
1056       }
1057     }
1058     pos += CommandCopyLen(&cmd);
1059     if (CommandCopyLen(&cmd)) {
1060       prev_byte2 = input[(pos - 2) & mask];
1061       prev_byte = input[(pos - 1) & mask];
1062       if (cmd.cmd_prefix_ >= 128) {
1063         size_t dist_code = cmd.dist_prefix_ & 0x3FF;
1064         uint32_t distnumextra = cmd.dist_prefix_ >> 10;
1065         uint64_t distextra = cmd.dist_extra_;
1066         if (mb->distance_context_map_size == 0) {
1067           StoreSymbol(&distance_enc, dist_code, storage_ix, storage);
1068         } else {
1069           size_t context = CommandDistanceContext(&cmd);
1070           StoreSymbolWithContext(&distance_enc, dist_code, context,
1071               mb->distance_context_map, storage_ix, storage,
1072               BROTLI_DISTANCE_CONTEXT_BITS);
1073         }
1074         BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
1075       }
1076     }
1077   }
1078   CleanupBlockEncoder(m, &distance_enc);
1079   CleanupBlockEncoder(m, &command_enc);
1080   CleanupBlockEncoder(m, &literal_enc);
1081   if (is_last) {
1082     JumpToByteBoundary(storage_ix, storage);
1083   }
1084 }
1085 
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)1086 static void BuildHistograms(const uint8_t* input,
1087                             size_t start_pos,
1088                             size_t mask,
1089                             const Command* commands,
1090                             size_t n_commands,
1091                             HistogramLiteral* lit_histo,
1092                             HistogramCommand* cmd_histo,
1093                             HistogramDistance* dist_histo) {
1094   size_t pos = start_pos;
1095   size_t i;
1096   for (i = 0; i < n_commands; ++i) {
1097     const Command cmd = commands[i];
1098     size_t j;
1099     HistogramAddCommand(cmd_histo, cmd.cmd_prefix_);
1100     for (j = cmd.insert_len_; j != 0; --j) {
1101       HistogramAddLiteral(lit_histo, input[pos & mask]);
1102       ++pos;
1103     }
1104     pos += CommandCopyLen(&cmd);
1105     if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
1106       HistogramAddDistance(dist_histo, cmd.dist_prefix_ & 0x3FF);
1107     }
1108   }
1109 }
1110 
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)1111 static void StoreDataWithHuffmanCodes(const uint8_t* input,
1112                                       size_t start_pos,
1113                                       size_t mask,
1114                                       const Command* commands,
1115                                       size_t n_commands,
1116                                       const uint8_t* lit_depth,
1117                                       const uint16_t* lit_bits,
1118                                       const uint8_t* cmd_depth,
1119                                       const uint16_t* cmd_bits,
1120                                       const uint8_t* dist_depth,
1121                                       const uint16_t* dist_bits,
1122                                       size_t* storage_ix,
1123                                       uint8_t* storage) {
1124   size_t pos = start_pos;
1125   size_t i;
1126   for (i = 0; i < n_commands; ++i) {
1127     const Command cmd = commands[i];
1128     const size_t cmd_code = cmd.cmd_prefix_;
1129     size_t j;
1130     BrotliWriteBits(
1131         cmd_depth[cmd_code], cmd_bits[cmd_code], storage_ix, storage);
1132     StoreCommandExtra(&cmd, storage_ix, storage);
1133     for (j = cmd.insert_len_; j != 0; --j) {
1134       const uint8_t literal = input[pos & mask];
1135       BrotliWriteBits(
1136           lit_depth[literal], lit_bits[literal], storage_ix, storage);
1137       ++pos;
1138     }
1139     pos += CommandCopyLen(&cmd);
1140     if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
1141       const size_t dist_code = cmd.dist_prefix_ & 0x3FF;
1142       const uint32_t distnumextra = cmd.dist_prefix_ >> 10;
1143       const uint32_t distextra = cmd.dist_extra_;
1144       BrotliWriteBits(dist_depth[dist_code], dist_bits[dist_code],
1145                       storage_ix, storage);
1146       BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
1147     }
1148   }
1149 }
1150 
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)1151 void BrotliStoreMetaBlockTrivial(MemoryManager* m,
1152     const uint8_t* input, size_t start_pos, size_t length, size_t mask,
1153     BROTLI_BOOL is_last, const BrotliEncoderParams* params,
1154     const Command* commands, size_t n_commands,
1155     size_t* storage_ix, uint8_t* storage) {
1156   HistogramLiteral lit_histo;
1157   HistogramCommand cmd_histo;
1158   HistogramDistance dist_histo;
1159   uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
1160   uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
1161   uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS];
1162   uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS];
1163   uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE];
1164   uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE];
1165   HuffmanTree* tree;
1166   uint32_t num_distance_symbols = params->dist.alphabet_size;
1167 
1168   StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
1169 
1170   HistogramClearLiteral(&lit_histo);
1171   HistogramClearCommand(&cmd_histo);
1172   HistogramClearDistance(&dist_histo);
1173 
1174   BuildHistograms(input, start_pos, mask, commands, n_commands,
1175                   &lit_histo, &cmd_histo, &dist_histo);
1176 
1177   BrotliWriteBits(13, 0, storage_ix, storage);
1178 
1179   tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE);
1180   if (BROTLI_IS_OOM(m)) return;
1181   BuildAndStoreHuffmanTree(lit_histo.data_, BROTLI_NUM_LITERAL_SYMBOLS,
1182                            BROTLI_NUM_LITERAL_SYMBOLS, tree,
1183                            lit_depth, lit_bits,
1184                            storage_ix, storage);
1185   BuildAndStoreHuffmanTree(cmd_histo.data_, BROTLI_NUM_COMMAND_SYMBOLS,
1186                            BROTLI_NUM_COMMAND_SYMBOLS, tree,
1187                            cmd_depth, cmd_bits,
1188                            storage_ix, storage);
1189   BuildAndStoreHuffmanTree(dist_histo.data_, MAX_SIMPLE_DISTANCE_ALPHABET_SIZE,
1190                            num_distance_symbols, tree,
1191                            dist_depth, dist_bits,
1192                            storage_ix, storage);
1193   BROTLI_FREE(m, tree);
1194   StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
1195                             n_commands, lit_depth, lit_bits,
1196                             cmd_depth, cmd_bits,
1197                             dist_depth, dist_bits,
1198                             storage_ix, storage);
1199   if (is_last) {
1200     JumpToByteBoundary(storage_ix, storage);
1201   }
1202 }
1203 
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)1204 void BrotliStoreMetaBlockFast(MemoryManager* m,
1205     const uint8_t* input, size_t start_pos, size_t length, size_t mask,
1206     BROTLI_BOOL is_last, const BrotliEncoderParams* params,
1207     const Command* commands, size_t n_commands,
1208     size_t* storage_ix, uint8_t* storage) {
1209   uint32_t num_distance_symbols = params->dist.alphabet_size;
1210   uint32_t distance_alphabet_bits =
1211       Log2FloorNonZero(num_distance_symbols - 1) + 1;
1212 
1213   StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
1214 
1215   BrotliWriteBits(13, 0, storage_ix, storage);
1216 
1217   if (n_commands <= 128) {
1218     uint32_t histogram[BROTLI_NUM_LITERAL_SYMBOLS] = { 0 };
1219     size_t pos = start_pos;
1220     size_t num_literals = 0;
1221     size_t i;
1222     uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
1223     uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
1224     for (i = 0; i < n_commands; ++i) {
1225       const Command cmd = commands[i];
1226       size_t j;
1227       for (j = cmd.insert_len_; j != 0; --j) {
1228         ++histogram[input[pos & mask]];
1229         ++pos;
1230       }
1231       num_literals += cmd.insert_len_;
1232       pos += CommandCopyLen(&cmd);
1233     }
1234     BrotliBuildAndStoreHuffmanTreeFast(m, histogram, num_literals,
1235                                        /* max_bits = */ 8,
1236                                        lit_depth, lit_bits,
1237                                        storage_ix, storage);
1238     if (BROTLI_IS_OOM(m)) return;
1239     StoreStaticCommandHuffmanTree(storage_ix, storage);
1240     StoreStaticDistanceHuffmanTree(storage_ix, storage);
1241     StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
1242                               n_commands, lit_depth, lit_bits,
1243                               kStaticCommandCodeDepth,
1244                               kStaticCommandCodeBits,
1245                               kStaticDistanceCodeDepth,
1246                               kStaticDistanceCodeBits,
1247                               storage_ix, storage);
1248   } else {
1249     HistogramLiteral lit_histo;
1250     HistogramCommand cmd_histo;
1251     HistogramDistance dist_histo;
1252     uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
1253     uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
1254     uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS];
1255     uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS];
1256     uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE];
1257     uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE];
1258     HistogramClearLiteral(&lit_histo);
1259     HistogramClearCommand(&cmd_histo);
1260     HistogramClearDistance(&dist_histo);
1261     BuildHistograms(input, start_pos, mask, commands, n_commands,
1262                     &lit_histo, &cmd_histo, &dist_histo);
1263     BrotliBuildAndStoreHuffmanTreeFast(m, lit_histo.data_,
1264                                        lit_histo.total_count_,
1265                                        /* max_bits = */ 8,
1266                                        lit_depth, lit_bits,
1267                                        storage_ix, storage);
1268     if (BROTLI_IS_OOM(m)) return;
1269     BrotliBuildAndStoreHuffmanTreeFast(m, cmd_histo.data_,
1270                                        cmd_histo.total_count_,
1271                                        /* max_bits = */ 10,
1272                                        cmd_depth, cmd_bits,
1273                                        storage_ix, storage);
1274     if (BROTLI_IS_OOM(m)) return;
1275     BrotliBuildAndStoreHuffmanTreeFast(m, dist_histo.data_,
1276                                        dist_histo.total_count_,
1277                                        /* max_bits = */
1278                                        distance_alphabet_bits,
1279                                        dist_depth, dist_bits,
1280                                        storage_ix, storage);
1281     if (BROTLI_IS_OOM(m)) return;
1282     StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
1283                               n_commands, lit_depth, lit_bits,
1284                               cmd_depth, cmd_bits,
1285                               dist_depth, dist_bits,
1286                               storage_ix, storage);
1287   }
1288 
1289   if (is_last) {
1290     JumpToByteBoundary(storage_ix, storage);
1291   }
1292 }
1293 
1294 /* This is for storing uncompressed blocks (simple raw storage of
1295    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)1296 void BrotliStoreUncompressedMetaBlock(BROTLI_BOOL is_final_block,
1297                                       const uint8_t* BROTLI_RESTRICT input,
1298                                       size_t position, size_t mask,
1299                                       size_t len,
1300                                       size_t* BROTLI_RESTRICT storage_ix,
1301                                       uint8_t* BROTLI_RESTRICT storage) {
1302   size_t masked_pos = position & mask;
1303   BrotliStoreUncompressedMetaBlockHeader(len, storage_ix, storage);
1304   JumpToByteBoundary(storage_ix, storage);
1305 
1306   if (masked_pos + len > mask + 1) {
1307     size_t len1 = mask + 1 - masked_pos;
1308     memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len1);
1309     *storage_ix += len1 << 3;
1310     len -= len1;
1311     masked_pos = 0;
1312   }
1313   memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len);
1314   *storage_ix += len << 3;
1315 
1316   /* We need to clear the next 4 bytes to continue to be
1317      compatible with BrotliWriteBits. */
1318   BrotliWriteBitsPrepareStorage(*storage_ix, storage);
1319 
1320   /* Since the uncompressed block itself may not be the final block, add an
1321      empty one after this. */
1322   if (is_final_block) {
1323     BrotliWriteBits(1, 1, storage_ix, storage);  /* islast */
1324     BrotliWriteBits(1, 1, storage_ix, storage);  /* isempty */
1325     JumpToByteBoundary(storage_ix, storage);
1326   }
1327 }
1328 
1329 #if defined(__cplusplus) || defined(c_plusplus)
1330 }  /* extern "C" */
1331 #endif
1332