/* 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 … /* The maximum size of Huffman dictionary for distances assuming that NPOSTFIX = 0 and NDIRECT = 0. */ #define MAX_SIMPLE_DISTANCE_ALPHABET_SIZE … /* MAX_SIMPLE_DISTANCE_ALPHABET_SIZE == 140 */ static BROTLI_INLINE uint32_t BlockLengthPrefixCode(uint32_t len) { … } static BROTLI_INLINE void GetBlockLengthPrefixCode(uint32_t len, size_t* code, uint32_t* n_extra, uint32_t* extra) { … } BlockTypeCodeCalculator; static void InitBlockTypeCodeCalculator(BlockTypeCodeCalculator* self) { … } static BROTLI_INLINE size_t NextBlockTypeCode( BlockTypeCodeCalculator* calculator, uint8_t type) { … } /* |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) { … } static BROTLI_INLINE void StoreCommandExtra( const Command* cmd, size_t* storage_ix, uint8_t* storage) { … } /* Data structure that stores almost everything that is needed to encode each block switch command. */ BlockSplitCode; /* Stores a number between 0 and 255. */ static void StoreVarLenUint8(size_t n, size_t* storage_ix, uint8_t* 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) { … } /* 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) { … } static void BrotliStoreHuffmanTreeOfHuffmanTreeToBitMask( const int num_codes, const uint8_t* code_length_bitdepth, size_t* storage_ix, uint8_t* 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) { … } 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) { … } /* num = alphabet size depths = symbol depths */ void BrotliStoreHuffmanTree(const uint8_t* depths, size_t num, HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) { … } /* Builds a Huffman tree from histogram[0:length] into depth[0:length] and bits[0:length] and stores the encoded tree to the bit stream. */ static void BuildAndStoreHuffmanTree(const uint32_t* histogram, const size_t histogram_length, const size_t alphabet_size, HuffmanTree* tree, uint8_t* depth, uint16_t* bits, size_t* storage_ix, uint8_t* storage) { … } static BROTLI_INLINE BROTLI_BOOL SortHuffmanTree( const HuffmanTree* v0, const HuffmanTree* v1) { … } void BrotliBuildAndStoreHuffmanTreeFast(HuffmanTree* tree, 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) { … } static size_t IndexOf(const uint8_t* v, size_t v_size, uint8_t value) { … } static void MoveToFront(uint8_t* v, size_t index) { … } static void MoveToFrontTransform(const uint32_t* BROTLI_RESTRICT v_in, const size_t v_size, uint32_t* v_out) { … } /* 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) { … } #define SYMBOL_BITS … EncodeContextMapArena; static void EncodeContextMap(MemoryManager* m, EncodeContextMapArena* arena, const uint32_t* context_map, size_t context_map_size, size_t num_clusters, HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) { … } /* 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) { … } /* 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) { … } /* Stores a context map where the histogram type is always the block type. */ static void StoreTrivialContextMap(EncodeContextMapArena* arena, size_t num_types, size_t context_bits, HuffmanTree* tree, size_t* storage_ix, uint8_t* storage) { … } /* Manages the encoding of one block category (literal, command or distance). */ 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) { … } static void CleanupBlockEncoder(MemoryManager* m, BlockEncoder* self) { … } /* 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) { … } /* 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) { … } /* 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) { … } #define FN … /* NOLINTNEXTLINE(build/include) */ #include "block_encoder_inc.h" #undef FN #define FN … /* NOLINTNEXTLINE(build/include) */ #include "block_encoder_inc.h" #undef FN #define FN … /* NOLINTNEXTLINE(build/include) */ #include "block_encoder_inc.h" #undef FN static void JumpToByteBoundary(size_t* storage_ix, uint8_t* storage) { … } StoreMetablockArena; 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) { … } 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) { … } 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) { … } /* TODO(eustas): pull alloc/dealloc to caller? */ MetablockArena; 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) { … } 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) { … } /* 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) { … } #if defined(BROTLI_TEST) void GetBlockLengthPrefixCodeForTest(uint32_t len, size_t* code, uint32_t* n_extra, uint32_t* extra) { GetBlockLengthPrefixCode(len, code, n_extra, extra); } #endif #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ #endif
Codebase Browser
chromium