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) {
    BrotliWriteBits(4, 1, storage_ix, storage);
    BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
    depth[symbols[0]] = 0;
    bits[symbols[0]] = 0;
    return;
  }

  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) || BROTLI_IS_NULL(tree)) 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;
        }
      }
      {
        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;
        }
      }
    }
    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 */

    /* Sort */
    for (i = 0; i < count; i++) {
      size_t j;
      for (j = i + 1; j < count; j++) {
        if (depth[symbols[j]] < depth[symbols[i]]) {
          BROTLI_SWAP(size_t, symbols, j, i);
        }
      }
    }

    if (count == 2) {
      BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
      BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
    } else if (count == 3) {
      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 {
      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 {
    uint8_t previous_value = 8;
    size_t i;
    /* Complex Huffman Tree */
    StoreStaticCodeLengthCode(storage_ix, storage);

    /* Actual RLE coding. */
    for (i = 0; i < length;) {
      const uint8_t value = depth[i];
      size_t reps = 1;
      size_t k;
      for (k = i + 1; k < length && depth[k] == value; ++k) {
        ++reps;
      }
      i += reps;
      if (value == 0) {
        BrotliWriteBits(kZeroRepsDepth[reps], kZeroRepsBits[reps],
                        storage_ix, storage);
      } else {
        if (previous_value != value) {
          BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
                          storage_ix, storage);
          --reps;
        }
        if (reps < 3) {
          while (reps != 0) {
            reps--;
            BrotliWriteBits(kCodeLengthDepth[value], kCodeLengthBits[value],
                            storage_ix, storage);
          }
        } else {
          reps -= 3;
          BrotliWriteBits(kNonZeroRepsDepth[reps], kNonZeroRepsBits[reps],
                          storage_ix, storage);
        }
        previous_value = value;
      }
    }
  }
}