Update brotli to v1.0.0-snapshot.

third_party/brotli/enc/brotli_bit_stream.c

 /* Copyright 2014 Google Inc. All Rights Reserved.
 
    Distributed under MIT license.
    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
 */
 
-// Brotli bit stream functions to support the low level format. There are no
-// compression algorithms here, just the right ordering of bits to match the
-// specs.
+/* Brotli bit stream functions to support the low level format. There are no
+   compression algorithms here, just the right ordering of bits to match the
+   specs. */
 
 #include "./brotli_bit_stream.h"
 
-#include <algorithm>
-#include <cstdlib>  /* free, malloc */
-#include <cstring>
-#include <limits>
-#include <vector>
+#include <string.h>  /* memcpy, memset */
 
-#include "./bit_cost.h"
+#include "../common/constants.h"
+#include <brotli/types.h>
 #include "./context.h"
 #include "./entropy_encode.h"
 #include "./entropy_encode_static.h"
 #include "./fast_log.h"
-#include "./prefix.h"
+#include "./memory.h"
+#include "./port.h"
 #include "./write_bits.h"
 
-namespace brotli {
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
 
-namespace {
+#define MAX_HUFFMAN_TREE_SIZE (2 * BROTLI_NUM_COMMAND_SYMBOLS + 1)
+/* The size of Huffman dictionary for distances assuming that NPOSTFIX = 0 and
+ NDIRECT = 0. */
+#define SIMPLE_DISTANCE_ALPHABET_SIZE (BROTLI_NUM_DISTANCE_SHORT_CODES + \
+                                       (2 * BROTLI_MAX_DISTANCE_BITS))
+/* SIMPLE_DISTANCE_ALPHABET_SIZE == 64 */
+#define SIMPLE_DISTANCE_ALPHABET_BITS 6
 
-static const size_t kMaxHuffmanTreeSize = 2 * kNumCommandPrefixes + 1;
-// Context map alphabet has 256 context id symbols plus max 16 rle symbols.
-static const size_t kContextMapAlphabetSize = 256 + 16;
-// Block type alphabet has 256 block id symbols plus 2 special symbols.
-static const size_t kBlockTypeAlphabetSize = 256 + 2;
+/* Represents the range of values belonging to a prefix code:
+   [offset, offset + 2^nbits) */
+typedef struct PrefixCodeRange {
+  uint32_t offset;
+  uint32_t nbits;
+} PrefixCodeRange;
 
-// nibblesbits represents the 2 bits to encode MNIBBLES (0-3)
-// REQUIRES: length > 0
-// REQUIRES: length <= (1 << 24)
-void EncodeMlen(size_t length, uint64_t* bits,
-                size_t* numbits, uint64_t* nibblesbits) {
+static const PrefixCodeRange
+    kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = {
+  { 1, 2}, { 5, 2}, { 9, 2}, {13, 2}, {17, 3}, { 25, 3}, { 33, 3},
+  {41, 3}, {49, 4}, {65, 4}, {81, 4}, {97, 4}, {113, 5}, {145, 5},
+  {177, 5}, { 209,  5}, { 241,  6}, { 305,  6}, { 369,  7}, {  497,  8},
+  {753, 9}, {1265, 10}, {2289, 11}, {4337, 12}, {8433, 13}, {16625, 24}
+};
+
+static BROTLI_INLINE uint32_t BlockLengthPrefixCode(uint32_t len) {
+  uint32_t code = (len >= 177) ? (len >= 753 ? 20 : 14) : (len >= 41 ? 7 : 0);
+  while (code < (BROTLI_NUM_BLOCK_LEN_SYMBOLS - 1) &&
+      len >= kBlockLengthPrefixCode[code + 1].offset) ++code;
+  return code;
+}
+
+static BROTLI_INLINE void GetBlockLengthPrefixCode(uint32_t len, size_t* code,
+    uint32_t* n_extra, uint32_t* extra) {
+  *code = BlockLengthPrefixCode(len);
+  *n_extra = kBlockLengthPrefixCode[*code].nbits;
+  *extra = len - kBlockLengthPrefixCode[*code].offset;
+}
+
+typedef struct BlockTypeCodeCalculator {
+  size_t last_type;
+  size_t second_last_type;
+} BlockTypeCodeCalculator;
+
+static void InitBlockTypeCodeCalculator(BlockTypeCodeCalculator* self) {
+  self->last_type = 1;
+  self->second_last_type = 0;
+}
+
+static BROTLI_INLINE size_t NextBlockTypeCode(
+    BlockTypeCodeCalculator* calculator, uint8_t type) {
+  size_t type_code = (type == calculator->last_type + 1) ? 1u :
+      (type == calculator->second_last_type) ? 0u : type + 2u;
+  calculator->second_last_type = calculator->last_type;
+  calculator->last_type = type;
+  return type_code;
+}
+
+/* |nibblesbits| represents the 2 bits to encode MNIBBLES (0-3)
+   REQUIRES: length > 0
+   REQUIRES: length <= (1 << 24) */
+static void BrotliEncodeMlen(size_t length, uint64_t* bits,
+                             size_t* numbits, uint64_t* nibblesbits) {
+  size_t lg = (length == 1) ? 1 : Log2FloorNonZero((uint32_t)(length - 1)) + 1;
+  size_t mnibbles = (lg < 16 ? 16 : (lg + 3)) / 4;
   assert(length > 0);
   assert(length <= (1 << 24));
-  length--;  // MLEN - 1 is encoded
-  size_t lg = length == 0 ? 1 : Log2FloorNonZero(
-      static_cast<uint32_t>(length)) + 1;
   assert(lg <= 24);
-  size_t mnibbles = (lg < 16 ? 16 : (lg + 3)) / 4;
   *nibblesbits = mnibbles - 4;
   *numbits = mnibbles * 4;
-  *bits = length;
+  *bits = length - 1;
 }
 
-static inline void StoreCommandExtra(
-    const Command& cmd, size_t* storage_ix, uint8_t* storage) {
-  uint32_t copylen_code = cmd.copy_len_code();
-  uint16_t inscode = GetInsertLengthCode(cmd.insert_len_);
+static BROTLI_INLINE void StoreCommandExtra(
+    const Command* cmd, size_t* storage_ix, uint8_t* storage) {
+  uint32_t copylen_code = CommandCopyLenCode(cmd);
+  uint16_t inscode = GetInsertLengthCode(cmd->insert_len_);
   uint16_t copycode = GetCopyLengthCode(copylen_code);
   uint32_t insnumextra = GetInsertExtra(inscode);
-  uint64_t insextraval = cmd.insert_len_ - GetInsertBase(inscode);
+  uint64_t insextraval = cmd->insert_len_ - GetInsertBase(inscode);
   uint64_t copyextraval = copylen_code - GetCopyBase(copycode);
   uint64_t bits = (copyextraval << insnumextra) | insextraval;
-  WriteBits(insnumextra + GetCopyExtra(copycode), bits, storage_ix, storage);
+  BrotliWriteBits(
+      insnumextra + GetCopyExtra(copycode), bits, storage_ix, storage);
 }
 
-}  // namespace
+/* Data structure that stores almost everything that is needed to encode each
+   block switch command. */
+typedef struct BlockSplitCode {
+  BlockTypeCodeCalculator type_code_calculator;
+  uint8_t type_depths[BROTLI_MAX_BLOCK_TYPE_SYMBOLS];
+  uint16_t type_bits[BROTLI_MAX_BLOCK_TYPE_SYMBOLS];
+  uint8_t length_depths[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
+  uint16_t length_bits[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
+} BlockSplitCode;
 
-void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage) {
+/* Stores a number between 0 and 255. */
+static void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage) {
   if (n == 0) {
-    WriteBits(1, 0, storage_ix, storage);
+    BrotliWriteBits(1, 0, storage_ix, storage);
   } else {
-    WriteBits(1, 1, storage_ix, storage);
     size_t nbits = Log2FloorNonZero(n);
-    WriteBits(3, nbits, storage_ix, storage);
-    WriteBits(nbits, n - (1 << nbits), storage_ix, storage);
+    BrotliWriteBits(1, 1, storage_ix, storage);
+    BrotliWriteBits(3, nbits, storage_ix, storage);
+    BrotliWriteBits(nbits, n - ((size_t)1 << nbits), storage_ix, storage);
   }
 }
 
-void StoreCompressedMetaBlockHeader(bool final_block,
-                                    size_t length,
-                                    size_t* storage_ix,
-                                    uint8_t* storage) {
-  // Write ISLAST bit.
-  WriteBits(1, final_block, storage_ix, storage);
-  // Write ISEMPTY bit.
-  if (final_block) {
-    WriteBits(1, 0, storage_ix, storage);
-  }
-
+/* Stores the compressed meta-block header.
+   REQUIRES: length > 0
+   REQUIRES: length <= (1 << 24) */
+static void StoreCompressedMetaBlockHeader(BROTLI_BOOL is_final_block,
+                                           size_t length,
+                                           size_t* storage_ix,
+                                           uint8_t* storage) {
   uint64_t lenbits;
   size_t nlenbits;
   uint64_t nibblesbits;
-  EncodeMlen(length, &lenbits, &nlenbits, &nibblesbits);
-  WriteBits(2, nibblesbits, storage_ix, storage);
-  WriteBits(nlenbits, lenbits, storage_ix, storage);
 
-  if (!final_block) {
-    // Write ISUNCOMPRESSED bit.
-    WriteBits(1, 0, storage_ix, storage);
+  /* Write ISLAST bit. */
+  BrotliWriteBits(1, (uint64_t)is_final_block, storage_ix, storage);
+  /* Write ISEMPTY bit. */
+  if (is_final_block) {
+    BrotliWriteBits(1, 0, storage_ix, storage);
+  }
+
+  BrotliEncodeMlen(length, &lenbits, &nlenbits, &nibblesbits);
+  BrotliWriteBits(2, nibblesbits, storage_ix, storage);
+  BrotliWriteBits(nlenbits, lenbits, storage_ix, storage);
+
+  if (!is_final_block) {
+    /* Write ISUNCOMPRESSED bit. */
+    BrotliWriteBits(1, 0, storage_ix, storage);
   }
 }
 
-void StoreUncompressedMetaBlockHeader(size_t length,
-                                      size_t* storage_ix,
-                                      uint8_t* storage) {
-  // Write ISLAST bit. Uncompressed block cannot be the last one, so set to 0.
-  WriteBits(1, 0, storage_ix, storage);
+/* Stores the uncompressed meta-block header.
+   REQUIRES: length > 0
+   REQUIRES: length <= (1 << 24) */
+static void BrotliStoreUncompressedMetaBlockHeader(size_t length,
+                                                   size_t* storage_ix,
+                                                   uint8_t* storage) {
   uint64_t lenbits;
   size_t nlenbits;
   uint64_t nibblesbits;
-  EncodeMlen(length, &lenbits, &nlenbits, &nibblesbits);
-  WriteBits(2, nibblesbits, storage_ix, storage);
-  WriteBits(nlenbits, lenbits, storage_ix, storage);
-  // Write ISUNCOMPRESSED bit.
-  WriteBits(1, 1, storage_ix, storage);
+
+  /* Write ISLAST bit.
+     Uncompressed block cannot be the last one, so set to 0. */
+  BrotliWriteBits(1, 0, storage_ix, storage);
+  BrotliEncodeMlen(length, &lenbits, &nlenbits, &nibblesbits);
+  BrotliWriteBits(2, nibblesbits, storage_ix, storage);
+  BrotliWriteBits(nlenbits, lenbits, storage_ix, storage);
+  /* Write ISUNCOMPRESSED bit. */
+  BrotliWriteBits(1, 1, storage_ix, storage);
 }
 
-void StoreHuffmanTreeOfHuffmanTreeToBitMask(
-    const int num_codes,
-    const uint8_t *code_length_bitdepth,
-    size_t *storage_ix,
-    uint8_t *storage) {
-  static const uint8_t kStorageOrder[kCodeLengthCodes] = {
+static void BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(
+    const int num_codes, const uint8_t* code_length_bitdepth,
+    size_t* storage_ix, uint8_t* storage) {
+  static const uint8_t kStorageOrder[BROTLI_CODE_LENGTH_CODES] = {
     1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15
   };
-  // The bit lengths of the Huffman code over the code length alphabet
-  // are compressed with the following static Huffman code:
-  //   Symbol   Code
-  //   ------   ----
-  //   0          00
-  //   1        1110
-  //   2         110
-  //   3          01
-  //   4          10
-  //   5        1111
+  /* The bit lengths of the Huffman code over the code length alphabet
+     are compressed with the following static Huffman code:
+       Symbol   Code
+       ------   ----
+       0          00
+       1        1110
+       2         110
+       3          01
+       4          10
+       5        1111 */
   static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = {
      0, 7, 3, 2, 1, 15
   };
   static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = {
     2, 4, 3, 2, 2, 4
   };
 
-  // Throw away trailing zeros:
-  size_t codes_to_store = kCodeLengthCodes;
+  size_t skip_some = 0;  /* skips none. */
+
+  /* Throw away trailing zeros: */
+  size_t codes_to_store = BROTLI_CODE_LENGTH_CODES;
   if (num_codes > 1) {
     for (; codes_to_store > 0; --codes_to_store) {
       if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
         break;
       }
     }
   }
-  size_t skip_some = 0;  // skips none.
   if (code_length_bitdepth[kStorageOrder[0]] == 0 &&
       code_length_bitdepth[kStorageOrder[1]] == 0) {
-    skip_some = 2;  // skips two.
+    skip_some = 2;  /* skips two. */
     if (code_length_bitdepth[kStorageOrder[2]] == 0) {
-      skip_some = 3;  // skips three.
+      skip_some = 3;  /* skips three. */
     }
   }
-  WriteBits(2, skip_some, storage_ix, storage);
-  for (size_t i = skip_some; i < codes_to_store; ++i) {
-    size_t l = code_length_bitdepth[kStorageOrder[i]];
-    WriteBits(kHuffmanBitLengthHuffmanCodeBitLengths[l],
-              kHuffmanBitLengthHuffmanCodeSymbols[l], storage_ix, storage);
+  BrotliWriteBits(2, skip_some, storage_ix, storage);
+  {
+    size_t i;
+    for (i = skip_some; i < codes_to_store; ++i) {
+      size_t l = code_length_bitdepth[kStorageOrder[i]];
+      BrotliWriteBits(kHuffmanBitLengthHuffmanCodeBitLengths[l],
+          kHuffmanBitLengthHuffmanCodeSymbols[l], storage_ix, storage);
+    }
   }
 }
 
-static void StoreHuffmanTreeToBitMask(
-    const size_t huffman_tree_size,
-    const uint8_t* huffman_tree,
-    const uint8_t* huffman_tree_extra_bits,
-    const uint8_t* code_length_bitdepth,
+static void 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 * __restrict storage_ix,
-    uint8_t * __restrict storage) {
-  for (size_t i = 0; i < huffman_tree_size; ++i) {
+    size_t* BROTLI_RESTRICT storage_ix, uint8_t* BROTLI_RESTRICT storage) {
+  size_t i;
+  for (i = 0; i < huffman_tree_size; ++i) {
     size_t ix = huffman_tree[i];
-    WriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix],
-              storage_ix, storage);
-    // Extra bits
+    BrotliWriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix],
+                    storage_ix, storage);
+    /* Extra bits */
     switch (ix) {
-      case 16:
-        WriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage);
+      case BROTLI_REPEAT_PREVIOUS_CODE_LENGTH:
+        BrotliWriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage);
         break;
-      case 17:
-        WriteBits(3, huffman_tree_extra_bits[i], storage_ix, storage);
+      case BROTLI_REPEAT_ZERO_CODE_LENGTH:
+        BrotliWriteBits(3, huffman_tree_extra_bits[i], storage_ix, storage);
         break;
     }
   }
 }
 
 static void StoreSimpleHuffmanTree(const uint8_t* depths,
                                    size_t symbols[4],
                                    size_t num_symbols,
                                    size_t max_bits,
                                    size_t *storage_ix, uint8_t *storage) {
-  // value of 1 indicates a simple Huffman code
-  WriteBits(2, 1, storage_ix, storage);
-  WriteBits(2, num_symbols - 1, storage_ix, storage);  // NSYM - 1
+  /* value of 1 indicates a simple Huffman code */
+  BrotliWriteBits(2, 1, storage_ix, storage);
+  BrotliWriteBits(2, num_symbols - 1, storage_ix, storage);  /* NSYM - 1 */
 
-  // Sort
-  for (size_t i = 0; i < num_symbols; i++) {
-    for (size_t j = i + 1; j < num_symbols; j++) {
-      if (depths[symbols[j]] < depths[symbols[i]]) {
-        std::swap(symbols[j], symbols[i]);
+  {
+    /* Sort */
+    size_t i;
+    for (i = 0; i < num_symbols; i++) {
+      size_t j;
+      for (j = i + 1; j < num_symbols; j++) {
+        if (depths[symbols[j]] < depths[symbols[i]]) {
+          BROTLI_SWAP(size_t, symbols, j, i);
+        }
       }
     }
   }
 
   if (num_symbols == 2) {
-    WriteBits(max_bits, symbols[0], storage_ix, storage);
-    WriteBits(max_bits, symbols[1], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
   } else if (num_symbols == 3) {
-    WriteBits(max_bits, symbols[0], storage_ix, storage);
-    WriteBits(max_bits, symbols[1], storage_ix, storage);
-    WriteBits(max_bits, symbols[2], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
   } else {
-    WriteBits(max_bits, symbols[0], storage_ix, storage);
-    WriteBits(max_bits, symbols[1], storage_ix, storage);
-    WriteBits(max_bits, symbols[2], storage_ix, storage);
-    WriteBits(max_bits, symbols[3], storage_ix, storage);
-    // tree-select
-    WriteBits(1, depths[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[3], storage_ix, storage);
+    /* tree-select */
+    BrotliWriteBits(1, depths[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
   }
 }
 
-// num = alphabet size
-// depths = symbol depths
-void StoreHuffmanTree(const uint8_t* depths, size_t num,
-                      HuffmanTree* tree,
-                      size_t *storage_ix, uint8_t *storage) {
-  // Write the Huffman tree into the brotli-representation.
-  // The command alphabet is the largest, so this allocation will fit all
-  // alphabets.
-  assert(num <= kNumCommandPrefixes);
-  uint8_t huffman_tree[kNumCommandPrefixes];
-  uint8_t huffman_tree_extra_bits[kNumCommandPrefixes];
+/* num = alphabet size
+   depths = symbol depths */
+void BrotliStoreHuffmanTree(const uint8_t* depths, size_t num,
+                            HuffmanTree* tree,
+                            size_t *storage_ix, uint8_t *storage) {
+  /* Write the Huffman tree into the brotli-representation.
+     The command alphabet is the largest, so this allocation will fit all
+     alphabets. */
+  uint8_t huffman_tree[BROTLI_NUM_COMMAND_SYMBOLS];
+  uint8_t huffman_tree_extra_bits[BROTLI_NUM_COMMAND_SYMBOLS];
   size_t huffman_tree_size = 0;
-  WriteHuffmanTree(depths, num, &huffman_tree_size, huffman_tree,
-                   huffman_tree_extra_bits);
+  uint8_t code_length_bitdepth[BROTLI_CODE_LENGTH_CODES] = { 0 };
+  uint16_t code_length_bitdepth_symbols[BROTLI_CODE_LENGTH_CODES];
+  uint32_t huffman_tree_histogram[BROTLI_CODE_LENGTH_CODES] = { 0 };
+  size_t i;
+  int num_codes = 0;
+  size_t code = 0;
 
-  // Calculate the statistics of the Huffman tree in brotli-representation.
-  uint32_t huffman_tree_histogram[kCodeLengthCodes] = { 0 };
-  for (size_t i = 0; i < huffman_tree_size; ++i) {
+  assert(num <= BROTLI_NUM_COMMAND_SYMBOLS);
+
+  BrotliWriteHuffmanTree(depths, num, &huffman_tree_size, huffman_tree,
+                         huffman_tree_extra_bits);
+
+  /* Calculate the statistics of the Huffman tree in brotli-representation. */
+  for (i = 0; i < huffman_tree_size; ++i) {
     ++huffman_tree_histogram[huffman_tree[i]];
   }
 
-  int num_codes = 0;
-  int code = 0;
-  for (int i = 0; i < kCodeLengthCodes; ++i) {
+  for (i = 0; i < BROTLI_CODE_LENGTH_CODES; ++i) {
     if (huffman_tree_histogram[i]) {
       if (num_codes == 0) {
         code = i;
         num_codes = 1;
       } else if (num_codes == 1) {
         num_codes = 2;
         break;
       }
     }
   }
 
-  // Calculate another Huffman tree to use for compressing both the
-  // earlier Huffman tree with.
-  uint8_t code_length_bitdepth[kCodeLengthCodes] = { 0 };
-  uint16_t code_length_bitdepth_symbols[kCodeLengthCodes] = { 0 };
-  CreateHuffmanTree(&huffman_tree_histogram[0], kCodeLengthCodes,
-                    5, tree, &code_length_bitdepth[0]);
-  ConvertBitDepthsToSymbols(code_length_bitdepth, kCodeLengthCodes,
-                            &code_length_bitdepth_symbols[0]);
+  /* Calculate another Huffman tree to use for compressing both the
+     earlier Huffman tree with. */
+  BrotliCreateHuffmanTree(huffman_tree_histogram, BROTLI_CODE_LENGTH_CODES,
+                          5, tree, code_length_bitdepth);
+  BrotliConvertBitDepthsToSymbols(code_length_bitdepth,
+                                  BROTLI_CODE_LENGTH_CODES,
+                                  code_length_bitdepth_symbols);
 
-  // Now, we have all the data, let's start storing it
-  StoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth,
-                                         storage_ix, storage);
+  /* Now, we have all the data, let's start storing it */
+  BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask(num_codes, code_length_bitdepth,
+                                               storage_ix, storage);
 
   if (num_codes == 1) {
     code_length_bitdepth[code] = 0;
   }
 
-  // Store the real huffman tree now.
-  StoreHuffmanTreeToBitMask(huffman_tree_size,
-                            huffman_tree,
-                            huffman_tree_extra_bits,
-                            &code_length_bitdepth[0],
-                            code_length_bitdepth_symbols,
-                            storage_ix, storage);
+  /* Store the real Huffman tree now. */
+  BrotliStoreHuffmanTreeToBitMask(huffman_tree_size,
+                                  huffman_tree,
+                                  huffman_tree_extra_bits,
+                                  code_length_bitdepth,
+                                  code_length_bitdepth_symbols,
+                                  storage_ix, storage);
 }
 
-void BuildAndStoreHuffmanTree(const uint32_t *histogram,
-                              const size_t length,
-                              HuffmanTree* tree,
-                              uint8_t* depth,
-                              uint16_t* bits,
-                              size_t* storage_ix,
-                              uint8_t* storage) {
+/* Builds a Huffman tree from histogram[0:length] into depth[0:length] and
+   bits[0:length] and stores the encoded tree to the bit stream. */
+static void BuildAndStoreHuffmanTree(const uint32_t *histogram,
+                                     const size_t length,
+                                     HuffmanTree* tree,
+                                     uint8_t* depth,
+                                     uint16_t* bits,
+                                     size_t* storage_ix,
+                                     uint8_t* storage) {
   size_t count = 0;
   size_t s4[4] = { 0 };
-  for (size_t i = 0; i < length; i++) {
+  size_t i;
+  size_t max_bits = 0;
+  for (i = 0; i < length; i++) {
     if (histogram[i]) {
       if (count < 4) {
         s4[count] = i;
       } else if (count > 4) {
         break;
       }
       count++;
     }
   }
 
-  size_t max_bits_counter = length - 1;
-  size_t max_bits = 0;
-  while (max_bits_counter) {
-    max_bits_counter >>= 1;
-    ++max_bits;
+  {
+    size_t max_bits_counter = length - 1;
+    while (max_bits_counter) {
+      max_bits_counter >>= 1;
+      ++max_bits;
+    }
   }
 
   if (count <= 1) {
-    WriteBits(4, 1, storage_ix, storage);
-    WriteBits(max_bits, s4[0], storage_ix, storage);
+    BrotliWriteBits(4, 1, storage_ix, storage);
+    BrotliWriteBits(max_bits, s4[0], storage_ix, storage);
+    depth[s4[0]] = 0;
+    bits[s4[0]] = 0;
     return;
   }
 
-  CreateHuffmanTree(histogram, length, 15, tree, depth);
-  ConvertBitDepthsToSymbols(depth, length, bits);
+  memset(depth, 0, length * sizeof(depth[0]));
+  BrotliCreateHuffmanTree(histogram, length, 15, tree, depth);
+  BrotliConvertBitDepthsToSymbols(depth, length, bits);
 
   if (count <= 4) {
     StoreSimpleHuffmanTree(depth, s4, count, max_bits, storage_ix, storage);
   } else {
-    StoreHuffmanTree(depth, length, tree, storage_ix, storage);
+    BrotliStoreHuffmanTree(depth, length, tree, storage_ix, storage);
   }
 }
 
-static inline bool SortHuffmanTree(const HuffmanTree& v0,
-                                   const HuffmanTree& v1) {
-  return v0.total_count_ < v1.total_count_;
+static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree(
+    const HuffmanTree* v0, const HuffmanTree* v1) {
+  return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_);
 }
 
-void BuildAndStoreHuffmanTreeFast(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) {
+void 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) {
   size_t count = 0;
   size_t symbols[4] = { 0 };
   size_t length = 0;
   size_t total = histogram_total;
   while (total != 0) {
     if (histogram[length]) {
       if (count < 4) {
         symbols[count] = length;
       }
       ++count;
       total -= histogram[length];
     }
     ++length;
   }
 
   if (count <= 1) {
-    WriteBits(4, 1, storage_ix, storage);
-    WriteBits(max_bits, symbols[0], storage_ix, storage);
+    BrotliWriteBits(4, 1, storage_ix, storage);
+    BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+    depth[symbols[0]] = 0;
+    bits[symbols[0]] = 0;
     return;
   }
 
-  const size_t max_tree_size = 2 * length + 1;
-  HuffmanTree* const tree =
-      static_cast<HuffmanTree*>(malloc(max_tree_size * sizeof(HuffmanTree)));
-  for (uint32_t count_limit = 1; ; count_limit *= 2) {
-    HuffmanTree* node = tree;
-    for (size_t i = length; i != 0;) {
-      --i;
-      if (histogram[i]) {
-        if (PREDICT_TRUE(histogram[i] >= count_limit)) {
-          *node = HuffmanTree(histogram[i], -1, static_cast<int16_t>(i));
-        } else {
-          *node = HuffmanTree(count_limit, -1, static_cast<int16_t>(i));
+  memset(depth, 0, length * sizeof(depth[0]));
+  {
+    const size_t max_tree_size = 2 * length + 1;
+    HuffmanTree* tree = BROTLI_ALLOC(m, HuffmanTree, max_tree_size);
+    uint32_t count_limit;
+    if (BROTLI_IS_OOM(m)) return;
+    for (count_limit = 1; ; count_limit *= 2) {
+      HuffmanTree* node = tree;
+      size_t l;
+      for (l = length; l != 0;) {
+        --l;
+        if (histogram[l]) {
+          if (BROTLI_PREDICT_TRUE(histogram[l] >= count_limit)) {
+            InitHuffmanTree(node, histogram[l], -1, (int16_t)l);
+          } else {
+            InitHuffmanTree(node, count_limit, -1, (int16_t)l);
+          }
+          ++node;
         }
-        ++node;
+      }
+      {
+        const int n = (int)(node - tree);
+        HuffmanTree sentinel;
+        int i = 0;      /* Points to the next leaf node. */
+        int j = n + 1;  /* Points to the next non-leaf node. */
+        int k;
+
+        SortHuffmanTreeItems(tree, (size_t)n, SortHuffmanTree);
+        /* The nodes are:
+           [0, n): the sorted leaf nodes that we start with.
+           [n]: we add a sentinel here.
+           [n + 1, 2n): new parent nodes are added here, starting from
+                        (n+1). These are naturally in ascending order.
+           [2n]: we add a sentinel at the end as well.
+           There will be (2n+1) elements at the end. */
+        InitHuffmanTree(&sentinel, BROTLI_UINT32_MAX, -1, -1);
+        *node++ = sentinel;
+        *node++ = sentinel;
+
+        for (k = n - 1; k > 0; --k) {
+          int left, right;
+          if (tree[i].total_count_ <= tree[j].total_count_) {
+            left = i;
+            ++i;
+          } else {
+            left = j;
+            ++j;
+          }
+          if (tree[i].total_count_ <= tree[j].total_count_) {
+            right = i;
+            ++i;
+          } else {
+            right = j;
+            ++j;
+          }
+          /* The sentinel node becomes the parent node. */
+          node[-1].total_count_ =
+              tree[left].total_count_ + tree[right].total_count_;
+          node[-1].index_left_ = (int16_t)left;
+          node[-1].index_right_or_value_ = (int16_t)right;
+          /* Add back the last sentinel node. */
+          *node++ = sentinel;
+        }
+        if (BrotliSetDepth(2 * n - 1, tree, depth, 14)) {
+          /* We need to pack the Huffman tree in 14 bits. If this was not
+             successful, add fake entities to the lowest values and retry. */
+          break;
+        }
       }
     }
-    const int n = static_cast<int>(node - tree);
-    std::sort(tree, node, SortHuffmanTree);
-    // The nodes are:
-    // [0, n): the sorted leaf nodes that we start with.
-    // [n]: we add a sentinel here.
-    // [n + 1, 2n): new parent nodes are added here, starting from
-    //              (n+1). These are naturally in ascending order.
-    // [2n]: we add a sentinel at the end as well.
-    // There will be (2n+1) elements at the end.
-    const HuffmanTree sentinel(std::numeric_limits<int>::max(), -1, -1);
-    *node++ = sentinel;
-    *node++ = sentinel;
+    BROTLI_FREE(m, tree);
+  }
+  BrotliConvertBitDepthsToSymbols(depth, length, bits);
+  if (count <= 4) {
+    size_t i;
+    /* value of 1 indicates a simple Huffman code */
+    BrotliWriteBits(2, 1, storage_ix, storage);
+    BrotliWriteBits(2, count - 1, storage_ix, storage);  /* NSYM - 1 */
 
-    int i = 0;      // Points to the next leaf node.
-    int j = n + 1;  // Points to the next non-leaf node.
-    for (int k = n - 1; k > 0; --k) {
-      int left, right;
-      if (tree[i].total_count_ <= tree[j].total_count_) {
-        left = i;
-        ++i;
-      } else {
-        left = j;
-        ++j;
-      }
-      if (tree[i].total_count_ <= tree[j].total_count_) {
-        right = i;
-        ++i;
-      } else {
-        right = j;
-        ++j;
-      }
-      // The sentinel node becomes the parent node.
-      node[-1].total_count_ =
-          tree[left].total_count_ + tree[right].total_count_;
-      node[-1].index_left_ = static_cast<int16_t>(left);
-      node[-1].index_right_or_value_ = static_cast<int16_t>(right);
-      // Add back the last sentinel node.
-      *node++ = sentinel;
-    }
-    SetDepth(tree[2 * n - 1], &tree[0], depth, 0);
-    // We need to pack the Huffman tree in 14 bits.
-    // If this was not successful, add fake entities to the lowest values
-    // and retry.
-    if (PREDICT_TRUE(*std::max_element(&depth[0], &depth[length]) <= 14)) {
-      break;
-    }
-  }
-  free(tree);
-  ConvertBitDepthsToSymbols(depth, length, bits);
-  if (count <= 4) {
-    // value of 1 indicates a simple Huffman code
-    WriteBits(2, 1, storage_ix, storage);
-    WriteBits(2, count - 1, storage_ix, storage);  // NSYM - 1
-
-    // Sort
-    for (size_t i = 0; i < count; i++) {
-      for (size_t j = i + 1; j < count; j++) {
+    /* Sort */
+    for (i = 0; i < count; i++) {
+      size_t j;
+      for (j = i + 1; j < count; j++) {
         if (depth[symbols[j]] < depth[symbols[i]]) {
-          std::swap(symbols[j], symbols[i]);
+          BROTLI_SWAP(size_t, symbols, j, i);
         }
       }
     }
 
     if (count == 2) {
-      WriteBits(max_bits, symbols[0], storage_ix, storage);
-      WriteBits(max_bits, symbols[1], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
     } else if (count == 3) {
-      WriteBits(max_bits, symbols[0], storage_ix, storage);
-      WriteBits(max_bits, symbols[1], storage_ix, storage);
-      WriteBits(max_bits, symbols[2], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
     } else {
-      WriteBits(max_bits, symbols[0], storage_ix, storage);
-      WriteBits(max_bits, symbols[1], storage_ix, storage);
-      WriteBits(max_bits, symbols[2], storage_ix, storage);
-      WriteBits(max_bits, symbols[3], storage_ix, storage);
-      // tree-select
-      WriteBits(1, depth[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[2], storage_ix, storage);
+      BrotliWriteBits(max_bits, symbols[3], storage_ix, storage);
+      /* tree-select */
+      BrotliWriteBits(1, depth[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
     }
   } else {
-    // Complex Huffman Tree
+    uint8_t previous_value = 8;
+    size_t i;
+    /* Complex Huffman Tree */
     StoreStaticCodeLengthCode(storage_ix, storage);
 
-    // Actual rle coding.
-    uint8_t previous_value = 8;
-    for (size_t i = 0; i < length;) {
+    /* Actual RLE coding. */
+    for (i = 0; i < length;) {
       const uint8_t value = depth[i];
       size_t reps = 1;
-      for (size_t k = i + 1; k < length && depth[k] == value; ++k) {
+      size_t k;
+      for (k = i + 1; k < length && depth[k] == value; ++k) {
         ++reps;
       }
       i += reps;
       if (value == 0) {
-        WriteBits(kZeroRepsDepth[reps], kZeroRepsBits[reps],
-                  storage_ix, storage);
+        BrotliWriteBits(kZeroRepsDepth[reps], kZeroRepsBits[reps],
+                        storage_ix, storage);
       } else {
         if (previous_value != value) {
-          WriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
-                    storage_ix, storage);
+          BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
+                          storage_ix, storage);
           --reps;
         }
         if (reps < 3) {
           while (reps != 0) {
             reps--;
-            WriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
-                      storage_ix, storage);
+            BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
+                            storage_ix, storage);
           }
         } else {
           reps -= 3;
-          WriteBits(kNonZeroRepsDepth[reps], kNonZeroRepsBits[reps],
-                    storage_ix, storage);
+          BrotliWriteBits(kNonZeroRepsDepth[reps], kNonZeroRepsBits[reps],
+                          storage_ix, storage);
         }
         previous_value = value;
       }
     }
   }
 }
 
 static size_t IndexOf(const uint8_t* v, size_t v_size, uint8_t value) {
   size_t i = 0;
   for (; i < v_size; ++i) {
     if (v[i] == value) return i;
   }
   return i;
 }
 
 static void MoveToFront(uint8_t* v, size_t index) {
   uint8_t value = v[index];
-  for (size_t i = index; i != 0; --i) {
+  size_t i;
+  for (i = index; i != 0; --i) {
     v[i] = v[i - 1];
   }
   v[0] = value;
 }
 
-static void MoveToFrontTransform(const uint32_t* __restrict v_in,
+static void MoveToFrontTransform(const uint32_t* BROTLI_RESTRICT v_in,
                                  const size_t v_size,
                                  uint32_t* v_out) {
+  size_t i;
+  uint8_t mtf[256];
+  uint32_t max_value;
   if (v_size == 0) {
     return;
   }
-  uint32_t max_value = *std::max_element(v_in, v_in + v_size);
+  max_value = v_in[0];
+  for (i = 1; i < v_size; ++i) {
+    if (v_in[i] > max_value) max_value = v_in[i];
+  }
   assert(max_value < 256u);
-  uint8_t mtf[256];
-  size_t mtf_size = max_value + 1;
-  for (uint32_t i = 0; i <= max_value; ++i) {
-    mtf[i] = static_cast<uint8_t>(i);
+  for (i = 0; i <= max_value; ++i) {
+    mtf[i] = (uint8_t)i;
   }
-  for (size_t i = 0; i < v_size; ++i) {
-    size_t index = IndexOf(mtf, mtf_size, static_cast<uint8_t>(v_in[i]));
-    assert(index < mtf_size);
-    v_out[i] = static_cast<uint32_t>(index);
-    MoveToFront(mtf, index);
+  {
+    size_t mtf_size = max_value + 1;
+    for (i = 0; i < v_size; ++i) {
+      size_t index = IndexOf(mtf, mtf_size, (uint8_t)v_in[i]);
+      assert(index < mtf_size);
+      v_out[i] = (uint32_t)index;
+      MoveToFront(mtf, index);
+    }
   }
 }
 
-// Finds runs of zeros in v[0..in_size) and replaces them with a prefix code of
-// the run length plus extra bits (lower 9 bits is the prefix code and the rest
-// are the extra bits). Non-zero values in v[] are shifted by
-// *max_length_prefix. Will not create prefix codes bigger than the initial
-// value of *max_run_length_prefix. The prefix code of run length L is simply
-// Log2Floor(L) and the number of extra bits is the same as the prefix code.
+/* Finds runs of zeros in v[0..in_size) and replaces them with a prefix code of
+   the run length plus extra bits (lower 9 bits is the prefix code and the rest
+   are the extra bits). Non-zero values in v[] are shifted by
+   *max_length_prefix. Will not create prefix codes bigger than the initial
+   value of *max_run_length_prefix. The prefix code of run length L is simply
+   Log2Floor(L) and the number of extra bits is the same as the prefix code. */
 static void RunLengthCodeZeros(const size_t in_size,
-                               uint32_t* __restrict v,
-                               size_t* __restrict out_size,
-                               uint32_t* __restrict max_run_length_prefix) {
+    uint32_t* BROTLI_RESTRICT v, size_t* BROTLI_RESTRICT out_size,
+    uint32_t* BROTLI_RESTRICT max_run_length_prefix) {
   uint32_t max_reps = 0;
-  for (size_t i = 0; i < in_size;) {
+  size_t i;
+  uint32_t max_prefix;
+  for (i = 0; i < in_size;) {
+    uint32_t reps = 0;
     for (; i < in_size && v[i] != 0; ++i) ;
-    uint32_t reps = 0;
     for (; i < in_size && v[i] == 0; ++i) {
       ++reps;
     }
-    max_reps = std::max(reps, max_reps);
+    max_reps = BROTLI_MAX(uint32_t, reps, max_reps);
   }
-  uint32_t max_prefix = max_reps > 0 ? Log2FloorNonZero(max_reps) : 0;
-  max_prefix = std::min(max_prefix, *max_run_length_prefix);
+  max_prefix = max_reps > 0 ? Log2FloorNonZero(max_reps) : 0;
+  max_prefix = BROTLI_MIN(uint32_t, max_prefix, *max_run_length_prefix);
   *max_run_length_prefix = max_prefix;
   *out_size = 0;
-  for (size_t i = 0; i < in_size;) {
+  for (i = 0; i < in_size;) {
     assert(*out_size <= i);
     if (v[i] != 0) {
       v[*out_size] = v[i] + *max_run_length_prefix;
       ++i;
       ++(*out_size);
     } else {
       uint32_t reps = 1;
-      for (size_t k = i + 1; k < in_size && v[k] == 0; ++k) {
+      size_t k;
+      for (k = i + 1; k < in_size && v[k] == 0; ++k) {
         ++reps;
       }
       i += reps;
       while (reps != 0) {
         if (reps < (2u << max_prefix)) {
           uint32_t run_length_prefix = Log2FloorNonZero(reps);
           const uint32_t extra_bits = reps - (1u << run_length_prefix);
           v[*out_size] = run_length_prefix + (extra_bits << 9);
           ++(*out_size);
           break;
         } else {
           const uint32_t extra_bits = (1u << max_prefix) - 1u;
           v[*out_size] = max_prefix + (extra_bits << 9);
           reps -= (2u << max_prefix) - 1u;
           ++(*out_size);
         }
       }
     }
   }
 }
 
-void EncodeContextMap(const std::vector<uint32_t>& context_map,
-                      size_t num_clusters,
-                      HuffmanTree* tree,
-                      size_t* storage_ix, uint8_t* storage) {
+#define SYMBOL_BITS 9
+
+static void 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) {
+  size_t i;
+  uint32_t* rle_symbols;
+  uint32_t max_run_length_prefix = 6;
+  size_t num_rle_symbols = 0;
+  uint32_t histogram[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
+  static const uint32_t kSymbolMask = (1u << SYMBOL_BITS) - 1u;
+  uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
+  uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
+
   StoreVarLenUint8(num_clusters - 1, storage_ix, storage);
 
   if (num_clusters == 1) {
     return;
   }
 
-  uint32_t* rle_symbols = new uint32_t[context_map.size()];
-  MoveToFrontTransform(&context_map[0], context_map.size(), rle_symbols);
-  uint32_t max_run_length_prefix = 6;
-  size_t num_rle_symbols = 0;
-  RunLengthCodeZeros(context_map.size(), rle_symbols,
+  rle_symbols = BROTLI_ALLOC(m, uint32_t, context_map_size);
+  if (BROTLI_IS_OOM(m)) return;
+  MoveToFrontTransform(context_map, context_map_size, rle_symbols);
+  RunLengthCodeZeros(context_map_size, rle_symbols,
                      &num_rle_symbols, &max_run_length_prefix);
-  uint32_t histogram[kContextMapAlphabetSize];
   memset(histogram, 0, sizeof(histogram));
-  static const int kSymbolBits = 9;
-  static const uint32_t kSymbolMask = (1u << kSymbolBits) - 1u;
-  for (size_t i = 0; i < num_rle_symbols; ++i) {
+  for (i = 0; i < num_rle_symbols; ++i) {
     ++histogram[rle_symbols[i] & kSymbolMask];
   }
-  bool use_rle = max_run_length_prefix > 0;
-  WriteBits(1, use_rle, storage_ix, storage);
-  if (use_rle) {
-    WriteBits(4, max_run_length_prefix - 1, storage_ix, storage);
-  }
-  uint8_t depths[kContextMapAlphabetSize];
-  uint16_t bits[kContextMapAlphabetSize];
-  memset(depths, 0, sizeof(depths));
-  memset(bits, 0, sizeof(bits));
+  {
+    BROTLI_BOOL use_rle = TO_BROTLI_BOOL(max_run_length_prefix > 0);
+    BrotliWriteBits(1, (uint64_t)use_rle, storage_ix, storage);
+    if (use_rle) {
+      BrotliWriteBits(4, max_run_length_prefix - 1, storage_ix, storage);
+    }
+  }
   BuildAndStoreHuffmanTree(histogram, num_clusters + max_run_length_prefix,
                            tree, depths, bits, storage_ix, storage);
-  for (size_t i = 0; i < num_rle_symbols; ++i) {
+  for (i = 0; i < num_rle_symbols; ++i) {
     const uint32_t rle_symbol = rle_symbols[i] & kSymbolMask;
-    const uint32_t extra_bits_val = rle_symbols[i] >> kSymbolBits;
-    WriteBits(depths[rle_symbol], bits[rle_symbol], storage_ix, storage);
+    const uint32_t extra_bits_val = rle_symbols[i] >> SYMBOL_BITS;
+    BrotliWriteBits(depths[rle_symbol], bits[rle_symbol], storage_ix, storage);
     if (rle_symbol > 0 && rle_symbol <= max_run_length_prefix) {
-      WriteBits(rle_symbol, extra_bits_val, storage_ix, storage);
-    }
-  }
-  WriteBits(1, 1, storage_ix, storage);  // use move-to-front
-  delete[] rle_symbols;
-}
-
-void StoreBlockSwitch(const BlockSplitCode& code,
-                      const size_t block_ix,
-                      size_t* storage_ix,
-                      uint8_t* storage) {
-  if (block_ix > 0) {
-    size_t typecode = code.type_code[block_ix];
-    WriteBits(code.type_depths[typecode], code.type_bits[typecode],
-              storage_ix, storage);
-  }
-  size_t lencode = code.length_prefix[block_ix];
-  WriteBits(code.length_depths[lencode], code.length_bits[lencode],
-            storage_ix, storage);
-  WriteBits(code.length_nextra[block_ix], code.length_extra[block_ix],
-            storage_ix, storage);
-}
-
-static void BuildAndStoreBlockSplitCode(const std::vector<uint8_t>& types,
-                                        const std::vector<uint32_t>& lengths,
+      BrotliWriteBits(rle_symbol, extra_bits_val, storage_ix, storage);
+    }
+  }
+  BrotliWriteBits(1, 1, storage_ix, storage);  /* use move-to-front */
+  BROTLI_FREE(m, rle_symbols);
+}
+
+/* Stores the block switch command with index block_ix to the bit stream. */
+static BROTLI_INLINE void 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) {
+  size_t typecode = NextBlockTypeCode(&code->type_code_calculator, block_type);
+  size_t lencode;
+  uint32_t len_nextra;
+  uint32_t len_extra;
+  if (!is_first_block) {
+    BrotliWriteBits(code->type_depths[typecode], code->type_bits[typecode],
+                    storage_ix, storage);
+  }
+  GetBlockLengthPrefixCode(block_len, &lencode, &len_nextra, &len_extra);
+
+  BrotliWriteBits(code->length_depths[lencode], code->length_bits[lencode],
+                  storage_ix, storage);
+  BrotliWriteBits(len_nextra, len_extra, storage_ix, storage);
+}
+
+/* Builds a BlockSplitCode data structure from the block split given by the
+   vector of block types and block lengths and stores it to the bit stream. */
+static void 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) {
-  const size_t num_blocks = types.size();
-  uint32_t type_histo[kBlockTypeAlphabetSize];
-  uint32_t length_histo[kNumBlockLenPrefixes];
+  uint32_t type_histo[BROTLI_MAX_BLOCK_TYPE_SYMBOLS];
+  uint32_t length_histo[BROTLI_NUM_BLOCK_LEN_SYMBOLS];
+  size_t i;
+  BlockTypeCodeCalculator type_code_calculator;
   memset(type_histo, 0, (num_types + 2) * sizeof(type_histo[0]));
   memset(length_histo, 0, sizeof(length_histo));
-  size_t last_type = 1;
-  size_t second_last_type = 0;
-  code->type_code.resize(num_blocks);
-  code->length_prefix.resize(num_blocks);
-  code->length_nextra.resize(num_blocks);
-  code->length_extra.resize(num_blocks);
-  code->type_depths.resize(num_types + 2);
-  code->type_bits.resize(num_types + 2);
-  memset(code->length_depths, 0, sizeof(code->length_depths));
-  memset(code->length_bits, 0, sizeof(code->length_bits));
-  for (size_t i = 0; i < num_blocks; ++i) {
-    size_t type = types[i];
-    size_t type_code = (type == last_type + 1 ? 1 :
-                     type == second_last_type ? 0 :
-                     type + 2);
-    second_last_type = last_type;
-    last_type = type;
-    code->type_code[i] = static_cast<uint32_t>(type_code);
+  InitBlockTypeCodeCalculator(&type_code_calculator);
+  for (i = 0; i < num_blocks; ++i) {
+    size_t type_code = NextBlockTypeCode(&type_code_calculator, types[i]);
     if (i != 0) ++type_histo[type_code];
-    GetBlockLengthPrefixCode(lengths[i],
-                             &code->length_prefix[i],
-                             &code->length_nextra[i],
-                             &code->length_extra[i]);
-    ++length_histo[code->length_prefix[i]];
+    ++length_histo[BlockLengthPrefixCode(lengths[i])];
   }
   StoreVarLenUint8(num_types - 1, storage_ix, storage);
-  if (num_types > 1) {
+  if (num_types > 1) {  /* TODO: else? could StoreBlockSwitch occur? */
     BuildAndStoreHuffmanTree(&type_histo[0], num_types + 2, tree,
                              &code->type_depths[0], &code->type_bits[0],
                              storage_ix, storage);
-    BuildAndStoreHuffmanTree(&length_histo[0], kNumBlockLenPrefixes, tree,
-                             &code->length_depths[0], &code->length_bits[0],
-                             storage_ix, storage);
-    StoreBlockSwitch(*code, 0, storage_ix, storage);
-  }
-}
-
-void StoreTrivialContextMap(size_t num_types,
-                            size_t context_bits,
-                            HuffmanTree* tree,
-                            size_t* storage_ix,
-                            uint8_t* storage) {
+    BuildAndStoreHuffmanTree(&length_histo[0], BROTLI_NUM_BLOCK_LEN_SYMBOLS,
+                             tree, &code->length_depths[0],
+                             &code->length_bits[0], storage_ix, storage);
+    StoreBlockSwitch(code, lengths[0], types[0], 1, storage_ix, storage);
+  }
+}
+
+/* Stores a context map where the histogram type is always the block type. */
+static void StoreTrivialContextMap(size_t num_types,
+                                   size_t context_bits,
+                                   HuffmanTree* tree,
+                                   size_t* storage_ix,
+                                   uint8_t* storage) {
   StoreVarLenUint8(num_types - 1, storage_ix, storage);
   if (num_types > 1) {
     size_t repeat_code = context_bits - 1u;
     size_t repeat_bits = (1u << repeat_code) - 1u;
     size_t alphabet_size = num_types + repeat_code;
-    uint32_t histogram[kContextMapAlphabetSize];
-    uint8_t depths[kContextMapAlphabetSize];
-    uint16_t bits[kContextMapAlphabetSize];
+    uint32_t histogram[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
+    uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
+    uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS];
+    size_t i;
     memset(histogram, 0, alphabet_size * sizeof(histogram[0]));
-    memset(depths, 0, alphabet_size * sizeof(depths[0]));
-    memset(bits, 0, alphabet_size * sizeof(bits[0]));
-    // Write RLEMAX.
-    WriteBits(1, 1, storage_ix, storage);
-    WriteBits(4, repeat_code - 1, storage_ix, storage);
-    histogram[repeat_code] = static_cast<uint32_t>(num_types);
+    /* Write RLEMAX. */
+    BrotliWriteBits(1, 1, storage_ix, storage);
+    BrotliWriteBits(4, repeat_code - 1, storage_ix, storage);
+    histogram[repeat_code] = (uint32_t)num_types;
     histogram[0] = 1;
-    for (size_t i = context_bits; i < alphabet_size; ++i) {
+    for (i = context_bits; i < alphabet_size; ++i) {
       histogram[i] = 1;
     }
-    BuildAndStoreHuffmanTree(&histogram[0], alphabet_size, tree,
-                             &depths[0], &bits[0],
-                             storage_ix, storage);
-    for (size_t i = 0; i < num_types; ++i) {
+    BuildAndStoreHuffmanTree(histogram, alphabet_size, tree,
+                             depths, bits, storage_ix, storage);
+    for (i = 0; i < num_types; ++i) {
       size_t code = (i == 0 ? 0 : i + context_bits - 1);
-      WriteBits(depths[code], bits[code], storage_ix, storage);
-      WriteBits(depths[repeat_code], bits[repeat_code], storage_ix, storage);
-      WriteBits(repeat_code, repeat_bits, storage_ix, storage);
-    }
-    // Write IMTF (inverse-move-to-front) bit.
-    WriteBits(1, 1, storage_ix, storage);
-  }
-}
-
-// Manages the encoding of one block category (literal, command or distance).
-class BlockEncoder {
- public:
-  BlockEncoder(size_t alphabet_size,
-               size_t num_block_types,
-               const std::vector<uint8_t>& block_types,
-               const std::vector<uint32_t>& block_lengths)
-      : alphabet_size_(alphabet_size),
-        num_block_types_(num_block_types),
-        block_types_(block_types),
-        block_lengths_(block_lengths),
-        block_ix_(0),
-        block_len_(block_lengths.empty() ? 0 : block_lengths[0]),
-        entropy_ix_(0) {}
-
-  // Creates entropy codes of block lengths and block types and stores them
-  // to the bit stream.
-  void BuildAndStoreBlockSwitchEntropyCodes(HuffmanTree* tree,
-                                            size_t* storage_ix,
-                                            uint8_t* storage) {
-    BuildAndStoreBlockSplitCode(
-        block_types_, block_lengths_, num_block_types_,
-        tree, &block_split_code_, storage_ix, storage);
-  }
-
-  // Creates entropy codes for all block types and stores them to the bit
-  // stream.
-  template<int kSize>
-  void BuildAndStoreEntropyCodes(
-      const std::vector<Histogram<kSize> >& histograms,
-      HuffmanTree* tree,
-      size_t* storage_ix, uint8_t* storage) {
-    depths_.resize(histograms.size() * alphabet_size_);
-    bits_.resize(histograms.size() * alphabet_size_);
-    for (size_t i = 0; i < histograms.size(); ++i) {
-      size_t ix = i * alphabet_size_;
-      BuildAndStoreHuffmanTree(&histograms[i].data_[0], alphabet_size_,
-                               tree,
-                               &depths_[ix], &bits_[ix],
-                               storage_ix, storage);
-    }
-  }
-
-  // Stores the next symbol with the entropy code of the current block type.
-  // Updates the block type and block length at block boundaries.
-  void StoreSymbol(size_t symbol, size_t* storage_ix, uint8_t* storage) {
-    if (block_len_ == 0) {
-      ++block_ix_;
-      block_len_ = block_lengths_[block_ix_];
-      entropy_ix_ = block_types_[block_ix_] * alphabet_size_;
-      StoreBlockSwitch(block_split_code_, block_ix_, storage_ix, storage);
-    }
-    --block_len_;
-    size_t ix = entropy_ix_ + symbol;
-    WriteBits(depths_[ix], bits_[ix], storage_ix, storage);
-  }
-
-  // Stores the next symbol with the entropy code of the current block type and
-  // context value.
-  // Updates the block type and block length at block boundaries.
-  template<int kContextBits>
-  void StoreSymbolWithContext(size_t symbol, size_t context,
-                              const std::vector<uint32_t>& context_map,
-                              size_t* storage_ix, uint8_t* storage) {
-    if (block_len_ == 0) {
-      ++block_ix_;
-      block_len_ = block_lengths_[block_ix_];
-      size_t block_type = block_types_[block_ix_];
-      entropy_ix_ = block_type << kContextBits;
-      StoreBlockSwitch(block_split_code_, block_ix_, storage_ix, storage);
-    }
-    --block_len_;
-    size_t histo_ix = context_map[entropy_ix_ + context];
-    size_t ix = histo_ix * alphabet_size_ + symbol;
-    WriteBits(depths_[ix], bits_[ix], storage_ix, storage);
-  }
-
- private:
-  const size_t alphabet_size_;
-  const size_t num_block_types_;
-  const std::vector<uint8_t>& block_types_;
-  const std::vector<uint32_t>& block_lengths_;
+      BrotliWriteBits(depths[code], bits[code], storage_ix, storage);
+      BrotliWriteBits(
+          depths[repeat_code], bits[repeat_code], storage_ix, storage);
+      BrotliWriteBits(repeat_code, repeat_bits, storage_ix, storage);
+    }
+    /* Write IMTF (inverse-move-to-front) bit. */
+    BrotliWriteBits(1, 1, storage_ix, storage);
+  }
+}
+
+/* Manages the encoding of one block category (literal, command or distance). */
+typedef struct BlockEncoder {
+  size_t alphabet_size_;
+  size_t num_block_types_;
+  const uint8_t* block_types_;  /* Not owned. */
+  const uint32_t* block_lengths_;  /* Not owned. */
+  size_t num_blocks_;
   BlockSplitCode block_split_code_;
   size_t block_ix_;
   size_t block_len_;
   size_t entropy_ix_;
-  std::vector<uint8_t> depths_;
-  std::vector<uint16_t> bits_;
-};
+  uint8_t* depths_;
+  uint16_t* bits_;
+} BlockEncoder;
+
+static void InitBlockEncoder(BlockEncoder* self, size_t alphabet_size,
+    size_t num_block_types, const uint8_t* block_types,
+    const uint32_t* block_lengths, const size_t num_blocks) {
+  self->alphabet_size_ = alphabet_size;
+  self->num_block_types_ = num_block_types;
+  self->block_types_ = block_types;
+  self->block_lengths_ = block_lengths;
+  self->num_blocks_ = num_blocks;
+  InitBlockTypeCodeCalculator(&self->block_split_code_.type_code_calculator);
+  self->block_ix_ = 0;
+  self->block_len_ = num_blocks == 0 ? 0 : block_lengths[0];
+  self->entropy_ix_ = 0;
+  self->depths_ = 0;
+  self->bits_ = 0;
+}
+
+static void CleanupBlockEncoder(MemoryManager* m, BlockEncoder* self) {
+  BROTLI_FREE(m, self->depths_);
+  BROTLI_FREE(m, self->bits_);
+}
+
+/* Creates entropy codes of block lengths and block types and stores them
+   to the bit stream. */
+static void BuildAndStoreBlockSwitchEntropyCodes(BlockEncoder* self,
+    HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) {
+  BuildAndStoreBlockSplitCode(self->block_types_, self->block_lengths_,
+      self->num_blocks_, self->num_block_types_, tree, &self->block_split_code_,
+      storage_ix, storage);
+}
+
+/* Stores the next symbol with the entropy code of the current block type.
+   Updates the block type and block length at block boundaries. */
+static void StoreSymbol(BlockEncoder* self, size_t symbol, size_t* storage_ix,
+    uint8_t* storage) {
+  if (self->block_len_ == 0) {
+    size_t block_ix = ++self->block_ix_;
+    uint32_t block_len = self->block_lengths_[block_ix];
+    uint8_t block_type = self->block_types_[block_ix];
+    self->block_len_ = block_len;
+    self->entropy_ix_ = block_type * self->alphabet_size_;
+    StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0,
+        storage_ix, storage);
+  }
+  --self->block_len_;
+  {
+    size_t ix = self->entropy_ix_ + symbol;
+    BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage);
+  }
+}
+
+/* Stores the next symbol with the entropy code of the current block type and
+   context value.
+   Updates the block type and block length at block boundaries. */
+static void 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) {
+  if (self->block_len_ == 0) {
+    size_t block_ix = ++self->block_ix_;
+    uint32_t block_len = self->block_lengths_[block_ix];
+    uint8_t block_type = self->block_types_[block_ix];
+    self->block_len_ = block_len;
+    self->entropy_ix_ = (size_t)block_type << context_bits;
+    StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0,
+        storage_ix, storage);
+  }
+  --self->block_len_;
+  {
+    size_t histo_ix = context_map[self->entropy_ix_ + context];
+    size_t ix = histo_ix * self->alphabet_size_ + symbol;
+    BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage);
+  }
+}
+
+#define FN(X) X ## Literal
+/* NOLINTNEXTLINE(build/include) */
+#include "./block_encoder_inc.h"
+#undef FN
+
+#define FN(X) X ## Command
+/* NOLINTNEXTLINE(build/include) */
+#include "./block_encoder_inc.h"
+#undef FN
+
+#define FN(X) X ## Distance
+/* NOLINTNEXTLINE(build/include) */
+#include "./block_encoder_inc.h"
+#undef FN
 
 static void JumpToByteBoundary(size_t* storage_ix, uint8_t* storage) {
   *storage_ix = (*storage_ix + 7u) & ~7u;
   storage[*storage_ix >> 3] = 0;
 }
 
-void StoreMetaBlock(const uint8_t* input,
-                    size_t start_pos,
-                    size_t length,
-                    size_t mask,
-                    uint8_t prev_byte,
-                    uint8_t prev_byte2,
-                    bool is_last,
-                    uint32_t num_direct_distance_codes,
-                    uint32_t distance_postfix_bits,
-                    ContextType literal_context_mode,
-                    const brotli::Command *commands,
-                    size_t n_commands,
-                    const MetaBlockSplit& mb,
-                    size_t *storage_ix,
-                    uint8_t *storage) {
+void 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,
+                          uint32_t num_direct_distance_codes,
+                          uint32_t distance_postfix_bits,
+                          ContextType literal_context_mode,
+                          const Command *commands,
+                          size_t n_commands,
+                          const MetaBlockSplit* mb,
+                          size_t *storage_ix,
+                          uint8_t *storage) {
+  size_t pos = start_pos;
+  size_t i;
+  size_t num_distance_codes =
+      BROTLI_NUM_DISTANCE_SHORT_CODES + num_direct_distance_codes +
+      (48u << distance_postfix_bits);
+  HuffmanTree* tree;
+  BlockEncoder literal_enc;
+  BlockEncoder command_enc;
+  BlockEncoder distance_enc;
+
   StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
 
-  size_t num_distance_codes =
-      kNumDistanceShortCodes + num_direct_distance_codes +
-      (48u << distance_postfix_bits);
-
-  HuffmanTree* tree = static_cast<HuffmanTree*>(
-      malloc(kMaxHuffmanTreeSize * sizeof(HuffmanTree)));
-  BlockEncoder literal_enc(256,
-                           mb.literal_split.num_types,
-                           mb.literal_split.types,
-                           mb.literal_split.lengths);
-  BlockEncoder command_enc(kNumCommandPrefixes,
-                           mb.command_split.num_types,
-                           mb.command_split.types,
-                           mb.command_split.lengths);
-  BlockEncoder distance_enc(num_distance_codes,
-                            mb.distance_split.num_types,
-                            mb.distance_split.types,
-                            mb.distance_split.lengths);
-
-  literal_enc.BuildAndStoreBlockSwitchEntropyCodes(tree, storage_ix, storage);
-  command_enc.BuildAndStoreBlockSwitchEntropyCodes(tree, storage_ix, storage);
-  distance_enc.BuildAndStoreBlockSwitchEntropyCodes(tree, storage_ix, storage);
-
-  WriteBits(2, distance_postfix_bits, storage_ix, storage);
-  WriteBits(4, num_direct_distance_codes >> distance_postfix_bits,
-            storage_ix, storage);
-  for (size_t i = 0; i < mb.literal_split.num_types; ++i) {
-    WriteBits(2, literal_context_mode, storage_ix, storage);
-  }
-
-  size_t num_literal_histograms = mb.literal_histograms.size();
-  if (mb.literal_context_map.empty()) {
-    StoreTrivialContextMap(num_literal_histograms, kLiteralContextBits, tree,
-                           storage_ix, storage);
+  tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE);
+  if (BROTLI_IS_OOM(m)) return;
+  InitBlockEncoder(&literal_enc, 256, mb->literal_split.num_types,
+      mb->literal_split.types, mb->literal_split.lengths,
+      mb->literal_split.num_blocks);
+  InitBlockEncoder(&command_enc, BROTLI_NUM_COMMAND_SYMBOLS,
+      mb->command_split.num_types, mb->command_split.types,
+      mb->command_split.lengths, mb->command_split.num_blocks);
+  InitBlockEncoder(&distance_enc, num_distance_codes,
+      mb->distance_split.num_types, mb->distance_split.types,
+      mb->distance_split.lengths, mb->distance_split.num_blocks);
+
+  BuildAndStoreBlockSwitchEntropyCodes(&literal_enc, tree, storage_ix, storage);
+  BuildAndStoreBlockSwitchEntropyCodes(&command_enc, tree, storage_ix, storage);
+  BuildAndStoreBlockSwitchEntropyCodes(
+      &distance_enc, tree, storage_ix, storage);
+
+  BrotliWriteBits(2, distance_postfix_bits, storage_ix, storage);
+  BrotliWriteBits(4, num_direct_distance_codes >> distance_postfix_bits,
+                  storage_ix, storage);
+  for (i = 0; i < mb->literal_split.num_types; ++i) {
+    BrotliWriteBits(2, literal_context_mode, storage_ix, storage);
+  }
+
+  if (mb->literal_context_map_size == 0) {
+    StoreTrivialContextMap(mb->literal_histograms_size,
+        BROTLI_LITERAL_CONTEXT_BITS, tree, storage_ix, storage);
   } else {
-    EncodeContextMap(mb.literal_context_map, num_literal_histograms, tree,
-                     storage_ix, storage);
-  }
-
-  size_t num_dist_histograms = mb.distance_histograms.size();
-  if (mb.distance_context_map.empty()) {
-    StoreTrivialContextMap(num_dist_histograms, kDistanceContextBits, tree,
-                           storage_ix, storage);
+    EncodeContextMap(m,
+        mb->literal_context_map, mb->literal_context_map_size,
+        mb->literal_histograms_size, tree, storage_ix, storage);
+    if (BROTLI_IS_OOM(m)) return;
+  }
+
+  if (mb->distance_context_map_size == 0) {
+    StoreTrivialContextMap(mb->distance_histograms_size,
+        BROTLI_DISTANCE_CONTEXT_BITS, tree, storage_ix, storage);
   } else {
-    EncodeContextMap(mb.distance_context_map, num_dist_histograms, tree,
-                     storage_ix, storage);
-  }
-
-  literal_enc.BuildAndStoreEntropyCodes(mb.literal_histograms, tree,
-                                        storage_ix, storage);
-  command_enc.BuildAndStoreEntropyCodes(mb.command_histograms, tree,
-                                        storage_ix, storage);
-  distance_enc.BuildAndStoreEntropyCodes(mb.distance_histograms, tree,
-                                         storage_ix, storage);
-  free(tree);
-
-  size_t pos = start_pos;
-  for (size_t i = 0; i < n_commands; ++i) {
+    EncodeContextMap(m,
+        mb->distance_context_map, mb->distance_context_map_size,
+        mb->distance_histograms_size, tree, storage_ix, storage);
+    if (BROTLI_IS_OOM(m)) return;
+  }
+
+  BuildAndStoreEntropyCodesLiteral(m, &literal_enc, mb->literal_histograms,
+      mb->literal_histograms_size, tree, storage_ix, storage);
+  if (BROTLI_IS_OOM(m)) return;
+  BuildAndStoreEntropyCodesCommand(m, &command_enc, mb->command_histograms,
+      mb->command_histograms_size, tree, storage_ix, storage);
+  if (BROTLI_IS_OOM(m)) return;
+  BuildAndStoreEntropyCodesDistance(m, &distance_enc, mb->distance_histograms,
+      mb->distance_histograms_size, tree, storage_ix, storage);
+  if (BROTLI_IS_OOM(m)) return;
+  BROTLI_FREE(m, tree);
+
+  for (i = 0; i < n_commands; ++i) {
     const Command cmd = commands[i];
     size_t cmd_code = cmd.cmd_prefix_;
-    command_enc.StoreSymbol(cmd_code, storage_ix, storage);
-    StoreCommandExtra(cmd, storage_ix, storage);
-    if (mb.literal_context_map.empty()) {
-      for (size_t j = cmd.insert_len_; j != 0; --j) {
-        literal_enc.StoreSymbol(input[pos & mask], storage_ix, storage);
+    StoreSymbol(&command_enc, cmd_code, storage_ix, storage);
+    StoreCommandExtra(&cmd, storage_ix, storage);
+    if (mb->literal_context_map_size == 0) {
+      size_t j;
+      for (j = cmd.insert_len_; j != 0; --j) {
+        StoreSymbol(&literal_enc, input[pos & mask], storage_ix, storage);
         ++pos;
       }
     } else {
-      for (size_t j = cmd.insert_len_; j != 0; --j) {
+      size_t j;
+      for (j = cmd.insert_len_; j != 0; --j) {
         size_t context = Context(prev_byte, prev_byte2, literal_context_mode);
         uint8_t literal = input[pos & mask];
-        literal_enc.StoreSymbolWithContext<kLiteralContextBits>(
-            literal, context, mb.literal_context_map, storage_ix, storage);
+        StoreSymbolWithContext(&literal_enc, literal, context,
+            mb->literal_context_map, storage_ix, storage,
+            BROTLI_LITERAL_CONTEXT_BITS);
         prev_byte2 = prev_byte;
         prev_byte = literal;
         ++pos;
       }
     }
-    pos += cmd.copy_len();
-    if (cmd.copy_len()) {
+    pos += CommandCopyLen(&cmd);
+    if (CommandCopyLen(&cmd)) {
       prev_byte2 = input[(pos - 2) & mask];
       prev_byte = input[(pos - 1) & mask];
       if (cmd.cmd_prefix_ >= 128) {
         size_t dist_code = cmd.dist_prefix_;
         uint32_t distnumextra = cmd.dist_extra_ >> 24;
         uint64_t distextra = cmd.dist_extra_ & 0xffffff;
-        if (mb.distance_context_map.empty()) {
-          distance_enc.StoreSymbol(dist_code, storage_ix, storage);
+        if (mb->distance_context_map_size == 0) {
+          StoreSymbol(&distance_enc, dist_code, storage_ix, storage);
         } else {
-          size_t context = cmd.DistanceContext();
-          distance_enc.StoreSymbolWithContext<kDistanceContextBits>(
-              dist_code, context, mb.distance_context_map, storage_ix, storage);
+          size_t context = CommandDistanceContext(&cmd);
+          StoreSymbolWithContext(&distance_enc, dist_code, context,
+              mb->distance_context_map, storage_ix, storage,
+              BROTLI_DISTANCE_CONTEXT_BITS);
         }
-        brotli::WriteBits(distnumextra, distextra, storage_ix, storage);
+        BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
       }
     }
   }
+  CleanupBlockEncoder(m, &distance_enc);
+  CleanupBlockEncoder(m, &command_enc);
+  CleanupBlockEncoder(m, &literal_enc);
   if (is_last) {
     JumpToByteBoundary(storage_ix, storage);
   }
 }
 
 static void BuildHistograms(const uint8_t* input,
                             size_t start_pos,
                             size_t mask,
-                            const brotli::Command *commands,
+                            const Command *commands,
                             size_t n_commands,
                             HistogramLiteral* lit_histo,
                             HistogramCommand* cmd_histo,
                             HistogramDistance* dist_histo) {
   size_t pos = start_pos;
-  for (size_t i = 0; i < n_commands; ++i) {
+  size_t i;
+  for (i = 0; i < n_commands; ++i) {
     const Command cmd = commands[i];
-    cmd_histo->Add(cmd.cmd_prefix_);
-    for (size_t j = cmd.insert_len_; j != 0; --j) {
-      lit_histo->Add(input[pos & mask]);
+    size_t j;
+    HistogramAddCommand(cmd_histo, cmd.cmd_prefix_);
+    for (j = cmd.insert_len_; j != 0; --j) {
+      HistogramAddLiteral(lit_histo, input[pos & mask]);
       ++pos;
     }
-    pos += cmd.copy_len();
-    if (cmd.copy_len() && cmd.cmd_prefix_ >= 128) {
-      dist_histo->Add(cmd.dist_prefix_);
+    pos += CommandCopyLen(&cmd);
+    if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
+      HistogramAddDistance(dist_histo, cmd.dist_prefix_);
     }
   }
 }
 
 static void StoreDataWithHuffmanCodes(const uint8_t* input,
                                       size_t start_pos,
                                       size_t mask,
-                                      const brotli::Command *commands,
+                                      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) {
   size_t pos = start_pos;
-  for (size_t i = 0; i < n_commands; ++i) {
+  size_t i;
+  for (i = 0; i < n_commands; ++i) {
     const Command cmd = commands[i];
     const size_t cmd_code = cmd.cmd_prefix_;
-    WriteBits(cmd_depth[cmd_code], cmd_bits[cmd_code], storage_ix, storage);
-    StoreCommandExtra(cmd, storage_ix, storage);
-    for (size_t j = cmd.insert_len_; j != 0; --j) {
+    size_t j;
+    BrotliWriteBits(
+        cmd_depth[cmd_code], cmd_bits[cmd_code], storage_ix, storage);
+    StoreCommandExtra(&cmd, storage_ix, storage);
+    for (j = cmd.insert_len_; j != 0; --j) {
       const uint8_t literal = input[pos & mask];
-      WriteBits(lit_depth[literal], lit_bits[literal], storage_ix, storage);
+      BrotliWriteBits(
+          lit_depth[literal], lit_bits[literal], storage_ix, storage);
       ++pos;
     }
-    pos += cmd.copy_len();
-    if (cmd.copy_len() && cmd.cmd_prefix_ >= 128) {
+    pos += CommandCopyLen(&cmd);
+    if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
       const size_t dist_code = cmd.dist_prefix_;
       const uint32_t distnumextra = cmd.dist_extra_ >> 24;
       const uint32_t distextra = cmd.dist_extra_ & 0xffffff;
-      WriteBits(dist_depth[dist_code], dist_bits[dist_code],
-                storage_ix, storage);
-      WriteBits(distnumextra, distextra, storage_ix, storage);
+      BrotliWriteBits(dist_depth[dist_code], dist_bits[dist_code],
+                      storage_ix, storage);
+      BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
     }
   }
 }
 
-void StoreMetaBlockTrivial(const uint8_t* input,
-                           size_t start_pos,
-                           size_t length,
-                           size_t mask,
-                           bool is_last,
-                           const brotli::Command *commands,
-                           size_t n_commands,
-                           size_t *storage_ix,
-                           uint8_t *storage) {
-  StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
-
+void BrotliStoreMetaBlockTrivial(MemoryManager* m,
+                                 const uint8_t* input,
+                                 size_t start_pos,
+                                 size_t length,
+                                 size_t mask,
+                                 BROTLI_BOOL is_last,
+                                 const Command *commands,
+                                 size_t n_commands,
+                                 size_t *storage_ix,
+                                 uint8_t *storage) {
   HistogramLiteral lit_histo;
   HistogramCommand cmd_histo;
   HistogramDistance dist_histo;
+  uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
+  uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
+  uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS];
+  uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS];
+  uint8_t dist_depth[SIMPLE_DISTANCE_ALPHABET_SIZE];
+  uint16_t dist_bits[SIMPLE_DISTANCE_ALPHABET_SIZE];
+  HuffmanTree* tree;
+
+  StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
+
+  HistogramClearLiteral(&lit_histo);
+  HistogramClearCommand(&cmd_histo);
+  HistogramClearDistance(&dist_histo);
 
   BuildHistograms(input, start_pos, mask, commands, n_commands,
                   &lit_histo, &cmd_histo, &dist_histo);
 
-  WriteBits(13, 0, storage_ix, storage);
+  BrotliWriteBits(13, 0, storage_ix, storage);
 
-  std::vector<uint8_t> lit_depth(256);
-  std::vector<uint16_t> lit_bits(256);
-  std::vector<uint8_t> cmd_depth(kNumCommandPrefixes);
-  std::vector<uint16_t> cmd_bits(kNumCommandPrefixes);
-  std::vector<uint8_t> dist_depth(64);
-  std::vector<uint16_t> dist_bits(64);
-
-  HuffmanTree* tree = static_cast<HuffmanTree*>(
-      malloc(kMaxHuffmanTreeSize * sizeof(HuffmanTree)));
-  BuildAndStoreHuffmanTree(&lit_histo.data_[0], 256, tree,
-                           &lit_depth[0], &lit_bits[0],
+  tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE);
+  if (BROTLI_IS_OOM(m)) return;
+  BuildAndStoreHuffmanTree(lit_histo.data_, BROTLI_NUM_LITERAL_SYMBOLS, tree,
+                           lit_depth, lit_bits,
                            storage_ix, storage);
-  BuildAndStoreHuffmanTree(&cmd_histo.data_[0], kNumCommandPrefixes, tree,
-                           &cmd_depth[0], &cmd_bits[0],
+  BuildAndStoreHuffmanTree(cmd_histo.data_, BROTLI_NUM_COMMAND_SYMBOLS, tree,
+                           cmd_depth, cmd_bits,
                            storage_ix, storage);
-  BuildAndStoreHuffmanTree(&dist_histo.data_[0], 64, tree,
-                           &dist_depth[0], &dist_bits[0],
+  BuildAndStoreHuffmanTree(dist_histo.data_, SIMPLE_DISTANCE_ALPHABET_SIZE,
+                           tree,
+                           dist_depth, dist_bits,
                            storage_ix, storage);
-  free(tree);
+  BROTLI_FREE(m, tree);
   StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
-                            n_commands, &lit_depth[0], &lit_bits[0],
-                            &cmd_depth[0], &cmd_bits[0],
-                            &dist_depth[0], &dist_bits[0],
+                            n_commands, lit_depth, lit_bits,
+                            cmd_depth, cmd_bits,
+                            dist_depth, dist_bits,
                             storage_ix, storage);
   if (is_last) {
     JumpToByteBoundary(storage_ix, storage);
   }
 }
 
-void StoreMetaBlockFast(const uint8_t* input,
-                        size_t start_pos,
-                        size_t length,
-                        size_t mask,
-                        bool is_last,
-                        const brotli::Command *commands,
-                        size_t n_commands,
-                        size_t *storage_ix,
-                        uint8_t *storage) {
+void BrotliStoreMetaBlockFast(MemoryManager* m,
+                              const uint8_t* input,
+                              size_t start_pos,
+                              size_t length,
+                              size_t mask,
+                              BROTLI_BOOL is_last,
+                              const Command *commands,
+                              size_t n_commands,
+                              size_t *storage_ix,
+                              uint8_t *storage) {
   StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);
 
-  WriteBits(13, 0, storage_ix, storage);
+  BrotliWriteBits(13, 0, storage_ix, storage);
 
   if (n_commands <= 128) {
-    uint32_t histogram[256] = { 0 };
+    uint32_t histogram[BROTLI_NUM_LITERAL_SYMBOLS] = { 0 };
     size_t pos = start_pos;
     size_t num_literals = 0;
-    for (size_t i = 0; i < n_commands; ++i) {
+    size_t i;
+    uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
+    uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
+    for (i = 0; i < n_commands; ++i) {
       const Command cmd = commands[i];
-      for (size_t j = cmd.insert_len_; j != 0; --j) {
+      size_t j;
+      for (j = cmd.insert_len_; j != 0; --j) {
         ++histogram[input[pos & mask]];
         ++pos;
       }
       num_literals += cmd.insert_len_;
-      pos += cmd.copy_len();
+      pos += CommandCopyLen(&cmd);
     }
-    uint8_t lit_depth[256] = { 0 };
-    uint16_t lit_bits[256] = { 0 };
-    BuildAndStoreHuffmanTreeFast(histogram, num_literals,
-                                 /* max_bits = */ 8,
-                                 lit_depth, lit_bits,
-                                 storage_ix, storage);
+    BrotliBuildAndStoreHuffmanTreeFast(m, histogram, num_literals,
+                                       /* max_bits = */ 8,
+                                       lit_depth, lit_bits,
+                                       storage_ix, storage);
+    if (BROTLI_IS_OOM(m)) return;
     StoreStaticCommandHuffmanTree(storage_ix, storage);
     StoreStaticDistanceHuffmanTree(storage_ix, storage);
     StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
-                              n_commands, &lit_depth[0], &lit_bits[0],
+                              n_commands, lit_depth, lit_bits,
                               kStaticCommandCodeDepth,
                               kStaticCommandCodeBits,
                               kStaticDistanceCodeDepth,
                               kStaticDistanceCodeBits,
                               storage_ix, storage);
   } else {
     HistogramLiteral lit_histo;
     HistogramCommand cmd_histo;
     HistogramDistance dist_histo;
+    uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS];
+    uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS];
+    uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS];
+    uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS];
+    uint8_t dist_depth[SIMPLE_DISTANCE_ALPHABET_SIZE];
+    uint16_t dist_bits[SIMPLE_DISTANCE_ALPHABET_SIZE];
+    HistogramClearLiteral(&lit_histo);
+    HistogramClearCommand(&cmd_histo);
+    HistogramClearDistance(&dist_histo);
     BuildHistograms(input, start_pos, mask, commands, n_commands,
                     &lit_histo, &cmd_histo, &dist_histo);
-    std::vector<uint8_t> lit_depth(256);
-    std::vector<uint16_t> lit_bits(256);
-    std::vector<uint8_t> cmd_depth(kNumCommandPrefixes);
-    std::vector<uint16_t> cmd_bits(kNumCommandPrefixes);
-    std::vector<uint8_t> dist_depth(64);
-    std::vector<uint16_t> dist_bits(64);
-    BuildAndStoreHuffmanTreeFast(&lit_histo.data_[0], lit_histo.total_count_,
-                                 /* max_bits = */ 8,
-                                 &lit_depth[0], &lit_bits[0],
-                                 storage_ix, storage);
-    BuildAndStoreHuffmanTreeFast(&cmd_histo.data_[0], cmd_histo.total_count_,
-                                 /* max_bits = */ 10,
-                                 &cmd_depth[0], &cmd_bits[0],
-                                 storage_ix, storage);
-    BuildAndStoreHuffmanTreeFast(&dist_histo.data_[0], dist_histo.total_count_,
-                                 /* max_bits = */ 6,
-                                 &dist_depth[0], &dist_bits[0],
-                                 storage_ix, storage);
+    BrotliBuildAndStoreHuffmanTreeFast(m, lit_histo.data_,
+                                       lit_histo.total_count_,
+                                       /* max_bits = */ 8,
+                                       lit_depth, lit_bits,
+                                       storage_ix, storage);
+    if (BROTLI_IS_OOM(m)) return;
+    BrotliBuildAndStoreHuffmanTreeFast(m, cmd_histo.data_,
+                                       cmd_histo.total_count_,
+                                       /* max_bits = */ 10,
+                                       cmd_depth, cmd_bits,
+                                       storage_ix, storage);
+    if (BROTLI_IS_OOM(m)) return;
+    BrotliBuildAndStoreHuffmanTreeFast(m, dist_histo.data_,
+                                       dist_histo.total_count_,
+                                       /* max_bits = */
+                                       SIMPLE_DISTANCE_ALPHABET_BITS,
+                                       dist_depth, dist_bits,
+                                       storage_ix, storage);
+    if (BROTLI_IS_OOM(m)) return;
     StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
-                              n_commands, &lit_depth[0], &lit_bits[0],
-                              &cmd_depth[0], &cmd_bits[0],
-                              &dist_depth[0], &dist_bits[0],
+                              n_commands, lit_depth, lit_bits,
+                              cmd_depth, cmd_bits,
+                              dist_depth, dist_bits,
                               storage_ix, storage);
   }
 
   if (is_last) {
     JumpToByteBoundary(storage_ix, storage);
   }
 }
 
-// This is for storing uncompressed blocks (simple raw storage of
-// bytes-as-bytes).
-void StoreUncompressedMetaBlock(bool final_block,
-                                const uint8_t * __restrict input,
-                                size_t position, size_t mask,
-                                size_t len,
-                                size_t * __restrict storage_ix,
-                                uint8_t * __restrict storage) {
-  StoreUncompressedMetaBlockHeader(len, storage_ix, storage);
+/* This is for storing uncompressed blocks (simple raw storage of
+   bytes-as-bytes). */
+void 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) {
+  size_t masked_pos = position & mask;
+  BrotliStoreUncompressedMetaBlockHeader(len, storage_ix, storage);
   JumpToByteBoundary(storage_ix, storage);
 
-  size_t masked_pos = position & mask;
   if (masked_pos + len > mask + 1) {
     size_t len1 = mask + 1 - masked_pos;
     memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len1);
     *storage_ix += len1 << 3;
     len -= len1;
     masked_pos = 0;
   }
   memcpy(&storage[*storage_ix >> 3], &input[masked_pos], len);
   *storage_ix += len << 3;
 
-  // We need to clear the next 4 bytes to continue to be
-  // compatible with WriteBits.
-  brotli::WriteBitsPrepareStorage(*storage_ix, storage);
+  /* We need to clear the next 4 bytes to continue to be
+     compatible with BrotliWriteBits. */
+  BrotliWriteBitsPrepareStorage(*storage_ix, storage);
 
-  // Since the uncompressed block itself may not be the final block, add an
-  // empty one after this.
-  if (final_block) {
-    brotli::WriteBits(1, 1, storage_ix, storage);  // islast
-    brotli::WriteBits(1, 1, storage_ix, storage);  // isempty
+  /* Since the uncompressed block itself may not be the final block, add an
+     empty one after this. */
+  if (is_final_block) {
+    BrotliWriteBits(1, 1, storage_ix, storage);  /* islast */
+    BrotliWriteBits(1, 1, storage_ix, storage);  /* isempty */
     JumpToByteBoundary(storage_ix, storage);
   }
 }
 
-void StoreSyncMetaBlock(size_t * __restrict storage_ix,
-                        uint8_t * __restrict storage) {
-  // Empty metadata meta-block bit pattern:
-  //   1 bit:  is_last (0)
-  //   2 bits: num nibbles (3)
-  //   1 bit:  reserved (0)
-  //   2 bits: metadata length bytes (0)
-  WriteBits(6, 6, storage_ix, storage);
+void BrotliStoreSyncMetaBlock(size_t* BROTLI_RESTRICT storage_ix,
+                              uint8_t* BROTLI_RESTRICT storage) {
+  /* Empty metadata meta-block bit pattern:
+       1 bit:  is_last (0)
+       2 bits: num nibbles (3)
+       1 bit:  reserved (0)
+       2 bits: metadata length bytes (0) */
+  BrotliWriteBits(6, 6, storage_ix, storage);
   JumpToByteBoundary(storage_ix, storage);
 }
 
-}  // namespace brotli
+#if defined(__cplusplus) || defined(c_plusplus)
+}  /* extern "C" */
+#endif