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