../deps/brotli/c/enc/brotli_bit

Bug Summary

File:	out/../deps/brotli/c/enc/brotli_bit_stream.c
Warning:	line 749, column 3 1st function call argument is an uninitialized value

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name brotli_bit_stream.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D V8_DEPRECATION_WARNINGS -D V8_IMMINENT_DEPRECATION_WARNINGS -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D OS_LINUX -I ../deps/brotli/c/include -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c ../deps/brotli/c/enc/brotli_bit_stream.c

../deps/brotli/c/enc/brotli_bit_stream.c

→

1/* Copyright 2014 Google Inc. All Rights Reserved.

 Distributed under MIT license.
 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5*/

7/* 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. */

11#include "./brotli_bit_stream.h"

13#include <string.h>  /* memcpy, memset */

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"

26#if defined(__cplusplus) || defined(c_plusplus)
27extern "C" {
28#endif

30#define MAX_HUFFMAN_TREE_SIZE(2 * 704 + 1) (2 * BROTLI_NUM_COMMAND_SYMBOLS704 + 1)
31/* The maximum size of Huffman dictionary for distances assuming that
 NPOSTFIX = 0 and NDIRECT = 0. */
33#define MAX_SIMPLE_DISTANCE_ALPHABET_SIZE( 16 + (0) + ((62U) << ((0) + 1))) \
BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_LARGE_MAX_DISTANCE_BITS)( 16 + (0) + ((62U) << ((0) + 1)))
35/* MAX_SIMPLE_DISTANCE_ALPHABET_SIZE == 140 */

37static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t BlockLengthPrefixCode(uint32_t len) {
uint32_t code = (len >= 177) ? (len >= 753 ? 20 : 14) : (len >= 41 ? 7 : 0);
44
←
Assuming 'len' is < 177→
45
←
'?' condition is false→
46
←
Assuming 'len' is >= 41→
47
←
'?' condition is true→
48
←
'code' initialized to 7→
while (code < (BROTLI_NUM_BLOCK_LEN_SYMBOLS26 - 1) &&
50
←
Loop condition is false. Execution continues on line 41→
    len >= _kBrotliPrefixCodeRanges[code + 1].offset) ++code;
49
←
Assuming 'len' is < field 'offset'→
return code;
51
←
Returning the value 7 (loaded from 'code')→
42}

44static BROTLI_INLINEinline __attribute__((__always_inline__)) void GetBlockLengthPrefixCode(uint32_t len, size_t* code,
  uint32_t* n_extra, uint32_t* extra) {
*code = BlockLengthPrefixCode(len);
43
←
Calling 'BlockLengthPrefixCode'→
52
←
Returning from 'BlockLengthPrefixCode'→
53
←
The value 7 is assigned to 'lencode'→
*n_extra = _kBrotliPrefixCodeRanges[*code].nbits;
*extra = len - _kBrotliPrefixCodeRanges[*code].offset;
49}

51typedef struct BlockTypeCodeCalculator {
size_t last_type;
size_t second_last_type;
54} BlockTypeCodeCalculator;

56static void InitBlockTypeCodeCalculator(BlockTypeCodeCalculator* self) {
self->last_type = 1;
self->second_last_type = 0;
59}

61static BROTLI_INLINEinline __attribute__((__always_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;
68}

70/* |nibblesbits| represents the 2 bits to encode MNIBBLES (0-3)
 REQUIRES: length > 0
 REQUIRES: length <= (1 << 24) */
73static 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;
BROTLI_DCHECK(length > 0);
BROTLI_DCHECK(length <= (1 << 24));
BROTLI_DCHECK(lg <= 24);
*nibblesbits = mnibbles - 4;
*numbits = mnibbles * 4;
*bits = length - 1;
83}

85static BROTLI_INLINEinline __attribute__((__always_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 copyextraval = copylen_code - GetCopyBase(copycode);
uint64_t bits = (copyextraval << insnumextra) | insextraval;
BrotliWriteBits(
    insnumextra + GetCopyExtra(copycode), bits, storage_ix, storage);
96}

98/* Data structure that stores almost everything that is needed to encode each
 block switch command. */
100typedef struct BlockSplitCode {
BlockTypeCodeCalculator type_code_calculator;
uint8_t type_depths[BROTLI_MAX_BLOCK_TYPE_SYMBOLS(256 + 2)];
uint16_t type_bits[BROTLI_MAX_BLOCK_TYPE_SYMBOLS(256 + 2)];
uint8_t length_depths[BROTLI_NUM_BLOCK_LEN_SYMBOLS26];
uint16_t length_bits[BROTLI_NUM_BLOCK_LEN_SYMBOLS26];
106} BlockSplitCode;

108/* Stores a number between 0 and 255. */
109static void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* storage) {
if (n == 0) {
  BrotliWriteBits(1, 0, storage_ix, storage);
} else {
  size_t nbits = Log2FloorNonZero(n);
  BrotliWriteBits(1, 1, storage_ix, storage);
  BrotliWriteBits(3, nbits, storage_ix, storage);
  BrotliWriteBits(nbits, n - ((size_t)1 << nbits), storage_ix, storage);
}
118}

120/* Stores the compressed meta-block header.
 REQUIRES: length > 0
 REQUIRES: length <= (1 << 24) */
123static void StoreCompressedMetaBlockHeader(BROTLI_BOOLint is_final_block,
                                         size_t length,
                                         size_t* storage_ix,
                                         uint8_t* storage) {
uint64_t lenbits;
size_t nlenbits;
uint64_t nibblesbits;

/* 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);
}
146}

148/* Stores the uncompressed meta-block header.
 REQUIRES: length > 0
 REQUIRES: length <= (1 << 24) */
151static void BrotliStoreUncompressedMetaBlockHeader(size_t length,
                                                 size_t* storage_ix,
                                                 uint8_t* storage) {
uint64_t lenbits;
size_t nlenbits;
uint64_t nibblesbits;

/* 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);
166}

168static 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(17 + 1)] = {
  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 */
static const uint8_t kHuffmanBitLengthHuffmanCodeSymbols[6] = {
   0, 7, 3, 2, 1, 15
};
static const uint8_t kHuffmanBitLengthHuffmanCodeBitLengths[6] = {
  2, 4, 3, 2, 2, 4
};

size_t skip_some = 0;  /* skips none. */

/* Throw away trailing zeros: */
size_t codes_to_store = BROTLI_CODE_LENGTH_CODES(17 + 1);
if (num_codes > 1) {
  for (; codes_to_store > 0; --codes_to_store) {
    if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
      break;
    }
  }
}
if (code_length_bitdepth[kStorageOrder[0]] == 0 &&
    code_length_bitdepth[kStorageOrder[1]] == 0) {
  skip_some = 2;  /* skips two. */
  if (code_length_bitdepth[kStorageOrder[2]] == 0) {
    skip_some = 3;  /* skips three. */
  }
}
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);
  }
}
218}

220static 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* BROTLI_RESTRICTrestrict storage_ix, uint8_t* BROTLI_RESTRICTrestrict storage) {
size_t i;
for (i = 0; i < huffman_tree_size; ++i) {
  size_t ix = huffman_tree[i];
  BrotliWriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix],
                  storage_ix, storage);
  /* Extra bits */
  switch (ix) {
    case BROTLI_REPEAT_PREVIOUS_CODE_LENGTH16:
      BrotliWriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage);
      break;
    case BROTLI_REPEAT_ZERO_CODE_LENGTH17:
      BrotliWriteBits(3, huffman_tree_extra_bits[i], storage_ix, storage);
      break;
  }
}
240}

242static 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 */
BrotliWriteBits(2, 1, storage_ix, storage);
BrotliWriteBits(2, num_symbols - 1, storage_ix, storage);  /* NSYM - 1 */

{
  /* 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){ size_t __brotli_swap_tmp = (symbols)[(j)]; (symbols)[(j)] =
 (symbols)[(i)]; (symbols)[(i)] = __brotli_swap_tmp; };
      }
    }
  }
}

if (num_symbols == 2) {
  BrotliWriteBits(max_bits, symbols[0], storage_ix, storage);
  BrotliWriteBits(max_bits, symbols[1], storage_ix, storage);
} else if (num_symbols == 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, depths[symbols[0]] == 1 ? 1 : 0, storage_ix, storage);
}
279}

281/* num = alphabet size
 depths = symbol depths */
283void 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_SYMBOLS704];
uint8_t huffman_tree_extra_bits[BROTLI_NUM_COMMAND_SYMBOLS704];
size_t huffman_tree_size = 0;
uint8_t code_length_bitdepth[BROTLI_CODE_LENGTH_CODES(17 + 1)] = { 0 };
uint16_t code_length_bitdepth_symbols[BROTLI_CODE_LENGTH_CODES(17 + 1)];
uint32_t huffman_tree_histogram[BROTLI_CODE_LENGTH_CODES(17 + 1)] = { 0 };
size_t i;
int num_codes = 0;
size_t code = 0;

BROTLI_DCHECK(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]];
}

for (i = 0; i < BROTLI_CODE_LENGTH_CODES(17 + 1); ++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. */
BrotliCreateHuffmanTree(huffman_tree_histogram, BROTLI_CODE_LENGTH_CODES(17 + 1),
                        5, tree, code_length_bitdepth);
BrotliConvertBitDepthsToSymbols(code_length_bitdepth,
                                BROTLI_CODE_LENGTH_CODES(17 + 1),
                                code_length_bitdepth_symbols);

/* 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. */
BrotliStoreHuffmanTreeToBitMask(huffman_tree_size,
                                huffman_tree,
                                huffman_tree_extra_bits,
                                code_length_bitdepth,
                                code_length_bitdepth_symbols,
                                storage_ix, storage);
344}

346/* 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. */
348static void BuildAndStoreHuffmanTree(const uint32_t* histogram,
                                   const size_t histogram_length,
                                   const size_t alphabet_size,
                                   HuffmanTree* tree,
                                   uint8_t* depth,
                                   uint16_t* bits,
                                   size_t* storage_ix,
                                   uint8_t* storage) {
size_t count = 0;
size_t s4[4] = { 0 };
size_t i;
size_t max_bits = 0;
for (i = 0; i < histogram_length; i++) {
  if (histogram[i]) {
    if (count < 4) {
      s4[count] = i;
    } else if (count > 4) {
      break;
    }
    count++;
  }
}

{
  size_t max_bits_counter = alphabet_size - 1;
  while (max_bits_counter) {
    max_bits_counter >>= 1;
    ++max_bits;
  }
}

if (count <= 1) {
  BrotliWriteBits(4, 1, storage_ix, storage);
  BrotliWriteBits(max_bits, s4[0], storage_ix, storage);
  depth[s4[0]] = 0;
  bits[s4[0]] = 0;
  return;
}

memset(depth, 0, histogram_length * sizeof(depth[0]));
BrotliCreateHuffmanTree(histogram, histogram_length, 15, tree, depth);
BrotliConvertBitDepthsToSymbols(depth, histogram_length, bits);

if (count <= 4) {
  StoreSimpleHuffmanTree(depth, s4, count, max_bits, storage_ix, storage);
} else {
  BrotliStoreHuffmanTree(depth, histogram_length, tree, storage_ix, storage);
}
396}

398static BROTLI_INLINEinline __attribute__((__always_inline__)) BROTLI_BOOLint SortHuffmanTree(
  const HuffmanTree* v0, const HuffmanTree* v1) {
return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_)(!!(v0->total_count_ < v1->total_count_) ? 1 : 0);
401}

403void 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)((max_tree_size) > 0 ? ((HuffmanTree*)BrotliAllocate((m), (
max_tree_size) * sizeof(HuffmanTree))) : ((void*)0));
  uint32_t count_limit;
  if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(tree)(!!0)) 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)(__builtin_expect(!!(histogram[l] >= count_limit), 1))) {
          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(~((uint32_t)0)), -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){ BrotliFree((m), (tree)); tree = ((void*)0); };
}
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){ size_t __brotli_swap_tmp = (symbols)[(j)]; (symbols)[(j)] =
 (symbols)[(i)]; (symbols)[(i)] = __brotli_swap_tmp; };
      }
    }
  }

  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;
    }
  }
}
576}

578static 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;
584}

586static void MoveToFront(uint8_t* v, size_t index) {
uint8_t value = v[index];
size_t i;
for (i = index; i != 0; --i) {
  v[i] = v[i - 1];
}
v[0] = value;
593}

595static void MoveToFrontTransform(const uint32_t* BROTLI_RESTRICTrestrict 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;
}
max_value = v_in[0];
for (i = 1; i < v_size; ++i) {
  if (v_in[i] > max_value) max_value = v_in[i];
}
BROTLI_DCHECK(max_value < 256u);
for (i = 0; i <= max_value; ++i) {
  mtf[i] = (uint8_t)i;
}
{
  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]);
    BROTLI_DCHECK(index < mtf_size);
    v_out[i] = (uint32_t)index;
    MoveToFront(mtf, index);
  }
}
621}

623/* 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. */
629static void RunLengthCodeZeros(const size_t in_size,
  uint32_t* BROTLI_RESTRICTrestrict v, size_t* BROTLI_RESTRICTrestrict out_size,
  uint32_t* BROTLI_RESTRICTrestrict max_run_length_prefix) {
uint32_t max_reps = 0;
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) ;
  for (; i < in_size && v[i] == 0; ++i) {
    ++reps;
  }
  max_reps = BROTLI_MAX(uint32_t, reps, max_reps)(brotli_max_uint32_t((reps), (max_reps)));
}
max_prefix = max_reps > 0 ? Log2FloorNonZero(max_reps) : 0;
max_prefix = BROTLI_MIN(uint32_t, max_prefix, *max_run_length_prefix)(brotli_min_uint32_t((max_prefix), (*max_run_length_prefix)));
*max_run_length_prefix = max_prefix;
*out_size = 0;
for (i = 0; i < in_size;) {
  BROTLI_DCHECK(*out_size <= i);
  if (v[i] != 0) {
    v[*out_size] = v[i] + *max_run_length_prefix;
    ++i;
    ++(*out_size);
  } else {
    uint32_t reps = 1;
    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);
      }
    }
  }
}
676}

678#define SYMBOL_BITS9 9

680static 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(256 + 16)];
static const uint32_t kSymbolMask = (1u << SYMBOL_BITS9) - 1u;
uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS(256 + 16)];
uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS(256 + 16)];

StoreVarLenUint8(num_clusters - 1, storage_ix, storage);

if (num_clusters == 1) {
  return;
}

rle_symbols = BROTLI_ALLOC(m, uint32_t, context_map_size)((context_map_size) > 0 ? ((uint32_t*)BrotliAllocate((m), (
context_map_size) * sizeof(uint32_t))) : ((void*)0));
if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(rle_symbols)(!!0)) return;
MoveToFrontTransform(context_map, context_map_size, rle_symbols);
RunLengthCodeZeros(context_map_size, rle_symbols,
                   &num_rle_symbols, &max_run_length_prefix);
memset(histogram, 0, sizeof(histogram));
for (i = 0; i < num_rle_symbols; ++i) {
  ++histogram[rle_symbols[i] & kSymbolMask];
}
{
  BROTLI_BOOLint use_rle = TO_BROTLI_BOOL(max_run_length_prefix > 0)(!!(max_run_length_prefix > 0) ? 1 : 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,
                         num_clusters + max_run_length_prefix,
                         tree, depths, bits, storage_ix, storage);
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] >> SYMBOL_BITS9;
  BrotliWriteBits(depths[rle_symbol], bits[rle_symbol], storage_ix, storage);
  if (rle_symbol > 0 && rle_symbol <= max_run_length_prefix) {
    BrotliWriteBits(rle_symbol, extra_bits_val, storage_ix, storage);
  }
}
BrotliWriteBits(1, 1, storage_ix, storage);  /* use move-to-front */
BROTLI_FREE(m, rle_symbols){ BrotliFree((m), (rle_symbols)); rle_symbols = ((void*)0); };
730}

732/* Stores the block switch command with index block_ix to the bit stream. */
733static BROTLI_INLINEinline __attribute__((__always_inline__)) void StoreBlockSwitch(BlockSplitCode* code,
                                         const uint32_t block_len,
                                         const uint8_t block_type,
                                         BROTLI_BOOLint 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_block40.1
'is_first_block' is 0
1
'is_first_block' is 0
) {
41
←
Taking true branch→
  BrotliWriteBits(code->type_depths[typecode], code->type_bits[typecode],
                  storage_ix, storage);
}
GetBlockLengthPrefixCode(block_len, &lencode, &len_nextra, &len_extra);
42
←
Calling 'GetBlockLengthPrefixCode'→
54
←
Returning from 'GetBlockLengthPrefixCode'→

BrotliWriteBits(code->length_depths[lencode], code->length_bits[lencode],
55
←
1st function call argument is an uninitialized value
                storage_ix, storage);
BrotliWriteBits(len_nextra, len_extra, storage_ix, storage);
752}

754/* 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. */
756static 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) {
uint32_t type_histo[BROTLI_MAX_BLOCK_TYPE_SYMBOLS(256 + 2)];
uint32_t length_histo[BROTLI_NUM_BLOCK_LEN_SYMBOLS26];
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));
InitBlockTypeCodeCalculator(&type_code_calculator);
for (i = 0; i8.1
'i' is < 'num_blocks'
1
'i' is < 'num_blocks'
 < num_blocks; ++i) {
9
←
Loop condition is true.  Entering loop body→
11
←
Assuming 'i' is >= 'num_blocks'→
12
←
Loop condition is false. Execution continues on line 776→
  size_t type_code = NextBlockTypeCode(&type_code_calculator, types[i]);
  if (i9.1
'i' is equal to 0
1
'i' is equal to 0
 != 0) ++type_histo[type_code];
10
←
Taking false branch→
  ++length_histo[BlockLengthPrefixCode(lengths[i])];
}
StoreVarLenUint8(num_types - 1, storage_ix, storage);
if (num_types > 1) {  /* TODO: else? could StoreBlockSwitch occur? */
13
←
Assuming 'num_types' is <= 1→
14
←
Taking false branch→
  BuildAndStoreHuffmanTree(&type_histo[0], num_types + 2, num_types + 2, tree,
                           &code->type_depths[0], &code->type_bits[0],
                           storage_ix, storage);
  BuildAndStoreHuffmanTree(&length_histo[0], BROTLI_NUM_BLOCK_LEN_SYMBOLS26,
                           BROTLI_NUM_BLOCK_LEN_SYMBOLS26,
                           tree, &code->length_depths[0],
                           &code->length_bits[0], storage_ix, storage);
  StoreBlockSwitch(code, lengths[0], types[0], 1, storage_ix, storage);
}
787}

789/* Stores a context map where the histogram type is always the block type. */
790static 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[BROTLI_MAX_CONTEXT_MAP_SYMBOLS(256 + 16)];
  uint8_t depths[BROTLI_MAX_CONTEXT_MAP_SYMBOLS(256 + 16)];
  uint16_t bits[BROTLI_MAX_CONTEXT_MAP_SYMBOLS(256 + 16)];
  size_t i;
  memset(histogram, 0, alphabet_size * sizeof(histogram[0]));
  /* 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 (i = context_bits; i < alphabet_size; ++i) {
    histogram[i] = 1;
  }
  BuildAndStoreHuffmanTree(histogram, alphabet_size, 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);
    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);
}
825}

827/* Manages the encoding of one block category (literal, command or distance). */
828typedef struct BlockEncoder {
size_t histogram_length_;
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_;
uint8_t* depths_;
uint16_t* bits_;
840} BlockEncoder;

842static void InitBlockEncoder(BlockEncoder* self, size_t histogram_length,
  size_t num_block_types, const uint8_t* block_types,
  const uint32_t* block_lengths, const size_t num_blocks) {
self->histogram_length_ = histogram_length;
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];
4
←
Assuming 'num_blocks' is not equal to 0→
5
←
'?' condition is false→
self->entropy_ix_ = 0;
self->depths_ = 0;
self->bits_ = 0;
856}

858static void CleanupBlockEncoder(MemoryManager* m, BlockEncoder* self) {
BROTLI_FREE(m, self->depths_){ BrotliFree((m), (self->depths_)); self->depths_ = ((void
*)0); };
BROTLI_FREE(m, self->bits_){ BrotliFree((m), (self->bits_)); self->bits_ = ((void*
)0); };
861}

863/* Creates entropy codes of block lengths and block types and stores them
 to the bit stream. */
865static void BuildAndStoreBlockSwitchEntropyCodes(BlockEncoder* self,
  HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) {
BuildAndStoreBlockSplitCode(self->block_types_, self->block_lengths_,
8
←
Calling 'BuildAndStoreBlockSplitCode'→
15
←
Returning from 'BuildAndStoreBlockSplitCode'→
    self->num_blocks_, self->num_block_types_, tree, &self->block_split_code_,
    storage_ix, storage);
870}

872/* Stores the next symbol with the entropy code of the current block type.
 Updates the block type and block length at block boundaries. */
874static void StoreSymbol(BlockEncoder* self, size_t symbol, size_t* storage_ix,
  uint8_t* storage) {
if (self->block_len_ == 0) {
38
←
Assuming field 'block_len_' is equal to 0→
39
←
Taking true branch→
  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->histogram_length_;
  StoreBlockSwitch(&self->block_split_code_, block_len, block_type, 0,
40
←
Calling 'StoreBlockSwitch'→
      storage_ix, storage);
}
--self->block_len_;
{
  size_t ix = self->entropy_ix_ + symbol;
  BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage);
}
890}

892/* 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. */
895static 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->histogram_length_ + symbol;
  BrotliWriteBits(self->depths_[ix], self->bits_[ix], storage_ix, storage);
}
913}

915#define FN(X) X ## Literal
916/* NOLINTNEXTLINE(build/include) */
917#include "./block_encoder_inc.h"
918#undef FN

920#define FN(X) X ## Command
921/* NOLINTNEXTLINE(build/include) */
922#include "./block_encoder_inc.h"
923#undef FN

925#define FN(X) X ## Distance
926/* NOLINTNEXTLINE(build/include) */
927#include "./block_encoder_inc.h"
928#undef FN

930static void JumpToByteBoundary(size_t* storage_ix, uint8_t* storage) {
*storage_ix = (*storage_ix + 7u) & ~7u;
storage[*storage_ix >> 3] = 0;
933}

935void 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_BOOLint is_last,
  const BrotliEncoderParams* params, ContextType literal_context_mode,
  const Command* commands, size_t n_commands, const MetaBlockSplit* mb,
  size_t* storage_ix, uint8_t* storage) {

size_t pos = start_pos;
size_t i;
uint32_t num_distance_symbols = params->dist.alphabet_size_max;
uint32_t num_effective_distance_symbols = params->dist.alphabet_size_limit;
HuffmanTree* tree;
ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode)(&_kBrotliContextLookupTable[(literal_context_mode) <<
 9]);
BlockEncoder literal_enc;
BlockEncoder command_enc;
BlockEncoder distance_enc;
const BrotliDistanceParams* dist = &params->dist;
BROTLI_DCHECK(
    num_effective_distance_symbols <= BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS);

StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);

tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE)(((2 * 704 + 1)) > 0 ? ((HuffmanTree*)BrotliAllocate((m), (
(2 * 704 + 1)) * sizeof(HuffmanTree))) : ((void*)0));
1
'?' condition is true→
if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(tree)(!!0)) return;
2
←
Taking false branch→
InitBlockEncoder(&literal_enc, BROTLI_NUM_LITERAL_SYMBOLS256,
    mb->literal_split.num_types, mb->literal_split.types,
    mb->literal_split.lengths, mb->literal_split.num_blocks);
InitBlockEncoder(&command_enc, BROTLI_NUM_COMMAND_SYMBOLS704,
3
←
Calling 'InitBlockEncoder'→
6
←
Returning from 'InitBlockEncoder'→
    mb->command_split.num_types, mb->command_split.types,
    mb->command_split.lengths, mb->command_split.num_blocks);
InitBlockEncoder(&distance_enc, num_effective_distance_symbols,
    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);
7
←
Calling 'BuildAndStoreBlockSwitchEntropyCodes'→
16
←
Returning from 'BuildAndStoreBlockSwitchEntropyCodes'→
BuildAndStoreBlockSwitchEntropyCodes(
    &distance_enc, tree, storage_ix, storage);

BrotliWriteBits(2, dist->distance_postfix_bits, storage_ix, storage);
BrotliWriteBits(
    4, dist->num_direct_distance_codes >> dist->distance_postfix_bits,
    storage_ix, storage);
for (i = 0; i < mb->literal_split.num_types; ++i) {
17
←
Loop condition is false. Execution continues on line 982→
  BrotliWriteBits(2, literal_context_mode, storage_ix, storage);
}

if (mb->literal_context_map_size == 0) {
18
←
Assuming field 'literal_context_map_size' is not equal to 0→
19
←
Taking false branch→
  StoreTrivialContextMap(mb->literal_histograms_size,
      BROTLI_LITERAL_CONTEXT_BITS6, tree, storage_ix, storage);
} else {
  EncodeContextMap(m,
      mb->literal_context_map, mb->literal_context_map_size,
      mb->literal_histograms_size, tree, storage_ix, storage);
  if (BROTLI_IS_OOM(m)(!!0)) return;
20
←
Taking false branch→
}

if (mb->distance_context_map_size == 0) {
21
←
Assuming field 'distance_context_map_size' is not equal to 0→
22
←
Taking false branch→
  StoreTrivialContextMap(mb->distance_histograms_size,
      BROTLI_DISTANCE_CONTEXT_BITS2, tree, storage_ix, storage);
} else {
  EncodeContextMap(m,
      mb->distance_context_map, mb->distance_context_map_size,
      mb->distance_histograms_size, tree, storage_ix, storage);
  if (BROTLI_IS_OOM(m)(!!0)) return;
23
←
Taking false branch→
}

BuildAndStoreEntropyCodesLiteral(m, &literal_enc, mb->literal_histograms,
    mb->literal_histograms_size, BROTLI_NUM_LITERAL_SYMBOLS256, tree,
    storage_ix, storage);
if (BROTLI_IS_OOM(m)(!!0)) return;
24
←
Taking false branch→
BuildAndStoreEntropyCodesCommand(m, &command_enc, mb->command_histograms,
25
←
Calling 'BuildAndStoreEntropyCodesCommand'→
32
←
Returning from 'BuildAndStoreEntropyCodesCommand'→
    mb->command_histograms_size, BROTLI_NUM_COMMAND_SYMBOLS704, tree,
    storage_ix, storage);
if (BROTLI_IS_OOM(m)(!!0)) return;
33
←
Taking false branch→
BuildAndStoreEntropyCodesDistance(m, &distance_enc, mb->distance_histograms,
    mb->distance_histograms_size, num_distance_symbols, tree,
    storage_ix, storage);
if (BROTLI_IS_OOM(m)(!!0)) return;
34
←
Taking false branch→
BROTLI_FREE(m, tree){ BrotliFree((m), (tree)); tree = ((void*)0); };

for (i = 0; i < n_commands; ++i) {
35
←
Assuming 'i' is < 'n_commands'→
36
←
Loop condition is true.  Entering loop body→
  const Command cmd = commands[i];
  size_t cmd_code = cmd.cmd_prefix_;
  StoreSymbol(&command_enc, cmd_code, storage_ix, storage);
37
←
Calling 'StoreSymbol'→
  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 {
    size_t j;
    for (j = cmd.insert_len_; j != 0; --j) {
      size_t context =
          BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut)((literal_context_lut)[prev_byte] | ((literal_context_lut) + 256
)[prev_byte2]);
      uint8_t literal = input[pos & mask];
      StoreSymbolWithContext(&literal_enc, literal, context,
          mb->literal_context_map, storage_ix, storage,
          BROTLI_LITERAL_CONTEXT_BITS6);
      prev_byte2 = prev_byte;
      prev_byte = literal;
      ++pos;
    }
  }
  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_ & 0x3FF;
      uint32_t distnumextra = cmd.dist_prefix_ >> 10;
      uint64_t distextra = cmd.dist_extra_;
      if (mb->distance_context_map_size == 0) {
        StoreSymbol(&distance_enc, dist_code, storage_ix, storage);
      } else {
        size_t context = CommandDistanceContext(&cmd);
        StoreSymbolWithContext(&distance_enc, dist_code, context,
            mb->distance_context_map, storage_ix, storage,
            BROTLI_DISTANCE_CONTEXT_BITS2);
      }
      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);
}
1067}

1069static void BuildHistograms(const uint8_t* input,
                          size_t start_pos,
                          size_t mask,
                          const Command* commands,
                          size_t n_commands,
                          HistogramLiteral* lit_histo,
                          HistogramCommand* cmd_histo,
                          HistogramDistance* dist_histo) {
size_t pos = start_pos;
size_t i;
for (i = 0; i < n_commands; ++i) {
  const Command cmd = commands[i];
  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 += CommandCopyLen(&cmd);
  if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
    HistogramAddDistance(dist_histo, cmd.dist_prefix_ & 0x3FF);
  }
}
1092}

1094static void StoreDataWithHuffmanCodes(const uint8_t* input,
                                    size_t start_pos,
                                    size_t mask,
                                    const Command* commands,
                                    size_t n_commands,
                                    const uint8_t* lit_depth,
                                    const uint16_t* lit_bits,
                                    const uint8_t* cmd_depth,
                                    const uint16_t* cmd_bits,
                                    const uint8_t* dist_depth,
                                    const uint16_t* dist_bits,
                                    size_t* storage_ix,
                                    uint8_t* storage) {
size_t pos = start_pos;
size_t i;
for (i = 0; i < n_commands; ++i) {
  const Command cmd = commands[i];
  const size_t cmd_code = cmd.cmd_prefix_;
  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];
    BrotliWriteBits(
        lit_depth[literal], lit_bits[literal], storage_ix, storage);
    ++pos;
  }
  pos += CommandCopyLen(&cmd);
  if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {
    const size_t dist_code = cmd.dist_prefix_ & 0x3FF;
    const uint32_t distnumextra = cmd.dist_prefix_ >> 10;
    const uint32_t distextra = cmd.dist_extra_;
    BrotliWriteBits(dist_depth[dist_code], dist_bits[dist_code],
                    storage_ix, storage);
    BrotliWriteBits(distnumextra, distextra, storage_ix, storage);
  }
}
1132}

1134void BrotliStoreMetaBlockTrivial(MemoryManager* m,
  const uint8_t* input, size_t start_pos, size_t length, size_t mask,
  BROTLI_BOOLint is_last, const BrotliEncoderParams* params,
  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_SYMBOLS256];
uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS256];
uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS704];
uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS704];
uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE( 16 + (0) + ((62U) << ((0) + 1)))];
uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE( 16 + (0) + ((62U) << ((0) + 1)))];
HuffmanTree* tree;
uint32_t num_distance_symbols = params->dist.alphabet_size_max;

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);

BrotliWriteBits(13, 0, storage_ix, storage);

tree = BROTLI_ALLOC(m, HuffmanTree, MAX_HUFFMAN_TREE_SIZE)(((2 * 704 + 1)) > 0 ? ((HuffmanTree*)BrotliAllocate((m), (
(2 * 704 + 1)) * sizeof(HuffmanTree))) : ((void*)0));
if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(tree)(!!0)) return;
BuildAndStoreHuffmanTree(lit_histo.data_, BROTLI_NUM_LITERAL_SYMBOLS256,
                         BROTLI_NUM_LITERAL_SYMBOLS256, tree,
                         lit_depth, lit_bits,
                         storage_ix, storage);
BuildAndStoreHuffmanTree(cmd_histo.data_, BROTLI_NUM_COMMAND_SYMBOLS704,
                         BROTLI_NUM_COMMAND_SYMBOLS704, tree,
                         cmd_depth, cmd_bits,
                         storage_ix, storage);
BuildAndStoreHuffmanTree(dist_histo.data_, MAX_SIMPLE_DISTANCE_ALPHABET_SIZE( 16 + (0) + ((62U) << ((0) + 1))),
                         num_distance_symbols, tree,
                         dist_depth, dist_bits,
                         storage_ix, storage);
BROTLI_FREE(m, tree){ BrotliFree((m), (tree)); tree = ((void*)0); };
StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
                          n_commands, lit_depth, lit_bits,
                          cmd_depth, cmd_bits,
                          dist_depth, dist_bits,
                          storage_ix, storage);
if (is_last) {
  JumpToByteBoundary(storage_ix, storage);
}
1185}

1187void BrotliStoreMetaBlockFast(MemoryManager* m,
  const uint8_t* input, size_t start_pos, size_t length, size_t mask,
  BROTLI_BOOLint is_last, const BrotliEncoderParams* params,
  const Command* commands, size_t n_commands,
  size_t* storage_ix, uint8_t* storage) {
uint32_t num_distance_symbols = params->dist.alphabet_size_max;
uint32_t distance_alphabet_bits =
    Log2FloorNonZero(num_distance_symbols - 1) + 1;

StoreCompressedMetaBlockHeader(is_last, length, storage_ix, storage);

BrotliWriteBits(13, 0, storage_ix, storage);

if (n_commands <= 128) {
  uint32_t histogram[BROTLI_NUM_LITERAL_SYMBOLS256] = { 0 };
  size_t pos = start_pos;
  size_t num_literals = 0;
  size_t i;
  uint8_t lit_depth[BROTLI_NUM_LITERAL_SYMBOLS256];
  uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS256];
  for (i = 0; i < n_commands; ++i) {
    const Command cmd = commands[i];
    size_t j;
    for (j = cmd.insert_len_; j != 0; --j) {
      ++histogram[input[pos & mask]];
      ++pos;
    }
    num_literals += cmd.insert_len_;
    pos += CommandCopyLen(&cmd);
  }
  BrotliBuildAndStoreHuffmanTreeFast(m, histogram, num_literals,
                                     /* max_bits = */ 8,
                                     lit_depth, lit_bits,
                                     storage_ix, storage);
  if (BROTLI_IS_OOM(m)(!!0)) return;
  StoreStaticCommandHuffmanTree(storage_ix, storage);
  StoreStaticDistanceHuffmanTree(storage_ix, storage);
  StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
                            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_SYMBOLS256];
  uint16_t lit_bits[BROTLI_NUM_LITERAL_SYMBOLS256];
  uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS704];
  uint16_t cmd_bits[BROTLI_NUM_COMMAND_SYMBOLS704];
  uint8_t dist_depth[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE( 16 + (0) + ((62U) << ((0) + 1)))];
  uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE( 16 + (0) + ((62U) << ((0) + 1)))];
  HistogramClearLiteral(&lit_histo);
  HistogramClearCommand(&cmd_histo);
  HistogramClearDistance(&dist_histo);
  BuildHistograms(input, start_pos, mask, commands, n_commands,
                  &lit_histo, &cmd_histo, &dist_histo);
  BrotliBuildAndStoreHuffmanTreeFast(m, lit_histo.data_,
                                     lit_histo.total_count_,
                                     /* max_bits = */ 8,
                                     lit_depth, lit_bits,
                                     storage_ix, storage);
  if (BROTLI_IS_OOM(m)(!!0)) 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)(!!0)) return;
  BrotliBuildAndStoreHuffmanTreeFast(m, dist_histo.data_,
                                     dist_histo.total_count_,
                                     /* max_bits = */
                                     distance_alphabet_bits,
                                     dist_depth, dist_bits,
                                     storage_ix, storage);
  if (BROTLI_IS_OOM(m)(!!0)) return;
  StoreDataWithHuffmanCodes(input, start_pos, mask, commands,
                            n_commands, lit_depth, lit_bits,
                            cmd_depth, cmd_bits,
                            dist_depth, dist_bits,
                            storage_ix, storage);
}

if (is_last) {
  JumpToByteBoundary(storage_ix, storage);
}
1275}

1277/* This is for storing uncompressed blocks (simple raw storage of
 bytes-as-bytes). */
1279void BrotliStoreUncompressedMetaBlock(BROTLI_BOOLint is_final_block,
                                    const uint8_t* BROTLI_RESTRICTrestrict input,
                                    size_t position, size_t mask,
                                    size_t len,
                                    size_t* BROTLI_RESTRICTrestrict storage_ix,
                                    uint8_t* BROTLI_RESTRICTrestrict storage) {
size_t masked_pos = position & mask;
BrotliStoreUncompressedMetaBlockHeader(len, storage_ix, storage);
JumpToByteBoundary(storage_ix, storage);

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 BrotliWriteBits. */
BrotliWriteBitsPrepareStorage(*storage_ix, storage);

/* 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);
}
1310}

1312#if defined(__cplusplus) || defined(c_plusplus)
1313}  /* extern "C" */
1314#endif

←

../deps/brotli/c/enc/./block_encoder_inc.h

1/* NOLINT(build/header_guard) */
2/* Copyright 2014 Google Inc. All Rights Reserved.
3 
4   Distributed under MIT license.
5   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6*/
7 
8/* template parameters: FN */
9 
10#define HistogramType FN(Histogram)
11 
12/* Creates entropy codes for all block types and stores them to the bit
13   stream. */
14static void FN(BuildAndStoreEntropyCodes)(MemoryManager* m, BlockEncoder* self,
15    const HistogramType* histograms, const size_t histograms_size,
16    const size_t alphabet_size, HuffmanTree* tree,
17    size_t* storage_ix, uint8_t* storage) {
18  const size_t table_size = histograms_size * self->histogram_length_;
19  self->depths_ = BROTLI_ALLOC(m, uint8_t, table_size)((table_size) > 0 ? ((uint8_t*)BrotliAllocate((m), (table_size
) * sizeof(uint8_t))) : ((void*)0));
26
←
Assuming 'table_size' is <= 0→
27
←
'?' condition is false→
20  self->bits_ = BROTLI_ALLOC(m, uint16_t, table_size)((table_size) > 0 ? ((uint16_t*)BrotliAllocate((m), (table_size
) * sizeof(uint16_t))) : ((void*)0));
28
←
'?' condition is false→
21  if (BROTLI_IS_OOM(m)(!!0)) return;
29
←
Taking false branch→
22 
23  {
24    size_t i;
25    for (i = 0; i < histograms_size; ++i) {
30
←
Assuming 'i' is >= 'histograms_size'→
31
←
Loop condition is false. Execution continues on line 25→
26      size_t ix = i * self->histogram_length_;
27      BuildAndStoreHuffmanTree(&histograms[i].data_[0], self->histogram_length_,
28          alphabet_size, tree, &self->depths_[ix], &self->bits_[ix],
29          storage_ix, storage);
30    }
31  }
32}
33 
34#undef HistogramType