diff options
Diffstat (limited to 'deps/node/deps/brotli/c/enc/brotli_bit_stream.c')
| -rw-r--r-- | deps/node/deps/brotli/c/enc/brotli_bit_stream.c | 1331 |
1 files changed, 0 insertions, 1331 deletions
diff --git a/deps/node/deps/brotli/c/enc/brotli_bit_stream.c b/deps/node/deps/brotli/c/enc/brotli_bit_stream.c deleted file mode 100644 index aaf2dad7..00000000 --- a/deps/node/deps/brotli/c/enc/brotli_bit_stream.c +++ /dev/null @@ -1,1331 +0,0 @@ -/* 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. */ - -#include "./brotli_bit_stream.h" - -#include <string.h> /* memcpy, memset */ - -#include "../common/constants.h" -#include "../common/context.h" -#include "../common/platform.h" -#include <brotli/types.h> -#include "./entropy_encode.h" -#include "./entropy_encode_static.h" -#include "./fast_log.h" -#include "./histogram.h" -#include "./memory.h" -#include "./write_bits.h" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#define MAX_HUFFMAN_TREE_SIZE (2 * BROTLI_NUM_COMMAND_SYMBOLS + 1) -/* The maximum size of Huffman dictionary for distances assuming that - NPOSTFIX = 0 and NDIRECT = 0. */ -#define MAX_SIMPLE_DISTANCE_ALPHABET_SIZE \ - BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_LARGE_MAX_DISTANCE_BITS) -/* MAX_SIMPLE_DISTANCE_ALPHABET_SIZE == 140 */ - -/* Represents the range of values belonging to a prefix code: - [offset, offset + 2^nbits) */ -typedef struct PrefixCodeRange { - uint32_t offset; - uint32_t nbits; -} PrefixCodeRange; - -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; - BROTLI_DCHECK(length > 0); - BROTLI_DCHECK(length <= (1 << 24)); - BROTLI_DCHECK(lg <= 24); - *nibblesbits = mnibbles - 4; - *numbits = mnibbles * 4; - *bits = length - 1; -} - -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 copyextraval = copylen_code - GetCopyBase(copycode); - uint64_t bits = (copyextraval << insnumextra) | insextraval; - BrotliWriteBits( - insnumextra + GetCopyExtra(copycode), bits, storage_ix, storage); -} - -/* 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; - -/* Stores a number between 0 and 255. */ -static 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); - } -} - -/* 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; - - /* 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); - } -} - -/* 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; - - /* 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); -} - -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 */ - 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; - 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); - } - } -} - -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* 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]; - BrotliWriteBits(code_length_bitdepth[ix], code_length_bitdepth_symbols[ix], - storage_ix, storage); - /* Extra bits */ - switch (ix) { - case BROTLI_REPEAT_PREVIOUS_CODE_LENGTH: - BrotliWriteBits(2, huffman_tree_extra_bits[i], storage_ix, storage); - break; - 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 */ - 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); - } - } - } - } - - 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); - } -} - -/* 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; - 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; - - 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; ++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, - 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 */ - 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); -} - -/* 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 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); - } -} - -static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree( - const HuffmanTree* v0, const HuffmanTree* v1) { - return TO_BROTLI_BOOL(v0->total_count_ < v1->total_count_); -} - -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)) 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; - } - } - } -} - -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]; - size_t i; - for (i = index; i != 0; --i) { - v[i] = v[i - 1]; - } - v[0] = value; -} - -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; - } - 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); - } - } -} - -/* 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* BROTLI_RESTRICT v, size_t* BROTLI_RESTRICT out_size, - uint32_t* BROTLI_RESTRICT 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); - } - 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 (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); - } - } - } - } -} - -#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; - } - - 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); - memset(histogram, 0, sizeof(histogram)); - for (i = 0; i < num_rle_symbols; ++i) { - ++histogram[rle_symbols[i] & kSymbolMask]; - } - { - 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, - 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_BITS; - 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); -} - -/* 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) { - 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)); - 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]; - ++length_histo[BlockLengthPrefixCode(lengths[i])]; - } - StoreVarLenUint8(num_types - 1, storage_ix, storage); - if (num_types > 1) { /* TODO: else? could StoreBlockSwitch occur? */ - 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_SYMBOLS, - 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[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])); - /* 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); - } -} - -/* Manages the encoding of one block category (literal, command or distance). */ -typedef 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_; -} BlockEncoder; - -static 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]; - 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->histogram_length_; - 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->histogram_length_ + 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 BrotliStoreMetaBlock(MemoryManager* m, - const uint8_t* input, size_t start_pos, size_t length, size_t mask, - uint8_t prev_byte, uint8_t prev_byte2, BROTLI_BOOL is_last, - const BrotliEncoderParams* params, ContextType literal_context_mode, - const Command* commands, size_t n_commands, const MetaBlockSplit* mb, - size_t* storage_ix, uint8_t* storage) { - - size_t pos = start_pos; - size_t i; - uint32_t num_distance_symbols = params->dist.alphabet_size; - uint32_t num_effective_distance_symbols = num_distance_symbols; - HuffmanTree* tree; - ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode); - BlockEncoder literal_enc; - BlockEncoder command_enc; - BlockEncoder distance_enc; - const BrotliDistanceParams* dist = ¶ms->dist; - if (params->large_window && - num_effective_distance_symbols > BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS) { - 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); - if (BROTLI_IS_OOM(m)) return; - InitBlockEncoder(&literal_enc, BROTLI_NUM_LITERAL_SYMBOLS, - 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_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); - 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) { - 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(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(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, BROTLI_NUM_LITERAL_SYMBOLS, tree, - storage_ix, storage); - if (BROTLI_IS_OOM(m)) return; - BuildAndStoreEntropyCodesCommand(m, &command_enc, mb->command_histograms, - mb->command_histograms_size, BROTLI_NUM_COMMAND_SYMBOLS, tree, - storage_ix, storage); - if (BROTLI_IS_OOM(m)) return; - BuildAndStoreEntropyCodesDistance(m, &distance_enc, mb->distance_histograms, - mb->distance_histograms_size, num_distance_symbols, 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_; - 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 { - size_t j; - for (j = cmd.insert_len_; j != 0; --j) { - size_t context = - BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut); - uint8_t literal = input[pos & mask]; - 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 += 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_BITS); - } - 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 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); - } - } -} - -static 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); - } - } -} - -void BrotliStoreMetaBlockTrivial(MemoryManager* m, - const uint8_t* input, size_t start_pos, size_t length, size_t mask, - BROTLI_BOOL is_last, const BrotliEncoderParams* params, - const Command* commands, size_t n_commands, - size_t* storage_ix, uint8_t* storage) { - 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[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; - uint16_t dist_bits[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; - HuffmanTree* tree; - uint32_t num_distance_symbols = params->dist.alphabet_size; - - 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); - if (BROTLI_IS_OOM(m)) return; - BuildAndStoreHuffmanTree(lit_histo.data_, BROTLI_NUM_LITERAL_SYMBOLS, - BROTLI_NUM_LITERAL_SYMBOLS, tree, - lit_depth, lit_bits, - storage_ix, storage); - BuildAndStoreHuffmanTree(cmd_histo.data_, BROTLI_NUM_COMMAND_SYMBOLS, - BROTLI_NUM_COMMAND_SYMBOLS, tree, - cmd_depth, cmd_bits, - storage_ix, storage); - BuildAndStoreHuffmanTree(dist_histo.data_, MAX_SIMPLE_DISTANCE_ALPHABET_SIZE, - num_distance_symbols, tree, - dist_depth, dist_bits, - storage_ix, storage); - BROTLI_FREE(m, tree); - 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); - } -} - -void BrotliStoreMetaBlockFast(MemoryManager* m, - const uint8_t* input, size_t start_pos, size_t length, size_t mask, - BROTLI_BOOL is_last, const BrotliEncoderParams* params, - const Command* commands, size_t n_commands, - size_t* storage_ix, uint8_t* storage) { - uint32_t num_distance_symbols = params->dist.alphabet_size; - 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_SYMBOLS] = { 0 }; - size_t pos = start_pos; - size_t num_literals = 0; - 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]; - 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)) 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_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[MAX_SIMPLE_DISTANCE_ALPHABET_SIZE]; - uint16_t dist_bits[MAX_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); - 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 = */ - 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, 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 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); - - 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); - } -} - -#if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ -#endif |