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