/* Copyright 2013 Google Inc. All Rights Reserved. Distributed under MIT license. See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ #include <brotli/decode.h> #include <stdlib.h> /* free, malloc */ #include <string.h> /* memcpy, memset */ #include "../common/constants.h" #include "../common/context.h" #include "../common/dictionary.h" #include "../common/platform.h" #include "../common/shared_dictionary_internal.h" #include "../common/transform.h" #include "../common/version.h" #include "bit_reader.h" #include "huffman.h" #include "prefix.h" #include "state.h" #if defined(BROTLI_TARGET_NEON) #include <arm_neon.h> #endif #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif #define BROTLI_FAILURE(CODE) … #define BROTLI_LOG_UINT(name) … #define BROTLI_LOG_ARRAY_INDEX(array_name, idx) … #define HUFFMAN_TABLE_BITS … #define HUFFMAN_TABLE_MASK … /* We need the slack region for the following reasons: - doing up to two 16-byte copies for fast backward copying - inserting transformed dictionary word: 255 prefix + 32 base + 255 suffix */ static const uint32_t kRingBufferWriteAheadSlack = …; static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = …; /* Static prefix code for the complex code length code lengths. */ static const uint8_t kCodeLengthPrefixLength[16] = …; static const uint8_t kCodeLengthPrefixValue[16] = …; BROTLI_BOOL BrotliDecoderSetParameter( BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) { … } BrotliDecoderState* BrotliDecoderCreateInstance( brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { … } /* Deinitializes and frees BrotliDecoderState instance. */ void BrotliDecoderDestroyInstance(BrotliDecoderState* state) { … } /* Saves error code and converts it to BrotliDecoderResult. */ static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode( BrotliDecoderState* s, BrotliDecoderErrorCode e) { … } /* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli". Precondition: bit-reader accumulator has at least 8 bits. */ static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s, BrotliBitReader* br) { … } static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) { … } /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */ static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8( BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) { … } /* Decodes a metablock length and flags by reading 2 - 31 bits. */ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( BrotliDecoderState* s, BrotliBitReader* br) { … } /* Decodes the Huffman code. This method doesn't read data from the bit reader, BUT drops the amount of bits that correspond to the decoded symbol. bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */ static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, const HuffmanCode* table, BrotliBitReader* br) { … } /* Reads and decodes the next Huffman code from bit-stream. This method peeks 16 bits of input and drops 0 - 15 of them. */ static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table, BrotliBitReader* br) { … } /* Same as DecodeSymbol, but it is known that there is less than 15 bits of input are currently available. */ static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol( const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { … } static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol( const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { … } /* Makes a look-up in first level Huffman table. Peeks 8 bits. */ static BROTLI_INLINE void PreloadSymbol(int safe, const HuffmanCode* table, BrotliBitReader* br, uint32_t* bits, uint32_t* value) { … } /* Decodes the next Huffman code using data prepared by PreloadSymbol. Reads 0 - 15 bits. Also peeks 8 following bits. */ static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table, BrotliBitReader* br, uint32_t* bits, uint32_t* value) { … } static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { … } /* Reads (s->symbol + 1) symbols. Totally 1..4 symbols are read, 1..11 bits each. The list of symbols MUST NOT contain duplicates. */ static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols( uint32_t alphabet_size_max, uint32_t alphabet_size_limit, BrotliDecoderState* s) { … } /* Process single decoded symbol code length: A) reset the repeat variable B) remember code length (if it is not 0) C) extend corresponding index-chain D) reduce the Huffman space E) update the histogram */ static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len, uint32_t* symbol, uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len, uint16_t* symbol_lists, uint16_t* code_length_histo, int* next_symbol) { … } /* Process repeated symbol code length. A) Check if it is the extension of previous repeat sequence; if the decoded value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new symbol-skip B) Update repeat variable C) Check if operation is feasible (fits alphabet) D) For each symbol do the same operations as in ProcessSingleCodeLength PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH */ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len, uint32_t repeat_delta, uint32_t alphabet_size, uint32_t* symbol, uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len, uint32_t* repeat_code_len, uint16_t* symbol_lists, uint16_t* code_length_histo, int* next_symbol) { … } /* Reads and decodes symbol codelengths. */ static BrotliDecoderErrorCode ReadSymbolCodeLengths( uint32_t alphabet_size, BrotliDecoderState* s) { … } static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( uint32_t alphabet_size, BrotliDecoderState* s) { … } /* Reads and decodes 15..18 codes using static prefix code. Each code is 2..4 bits long. In total 30..72 bits are used. */ static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) { … } /* Decodes the Huffman tables. There are 2 scenarios: A) Huffman code contains only few symbols (1..4). Those symbols are read directly; their code lengths are defined by the number of symbols. For this scenario 4 - 49 bits will be read. B) 2-phase decoding: B.1) Small Huffman table is decoded; it is specified with code lengths encoded with predefined entropy code. 32 - 74 bits are used. B.2) Decoded table is used to decode code lengths of symbols in resulting Huffman table. In worst case 3520 bits are read. */ static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size_max, uint32_t alphabet_size_limit, HuffmanCode* table, uint32_t* opt_table_size, BrotliDecoderState* s) { … } /* Decodes a block length by reading 3..39 bits. */ static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table, BrotliBitReader* br) { … } /* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then reading can't be continued with ReadBlockLength. */ static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table, BrotliBitReader* br) { … } /* Transform: 1) initialize list L with values 0, 1,... 255 2) For each input element X: 2.1) let Y = L[X] 2.2) remove X-th element from L 2.3) prepend Y to L 2.4) append Y to output In most cases max(Y) <= 7, so most of L remains intact. To reduce the cost of initialization, we reuse L, remember the upper bound of Y values, and reinitialize only first elements in L. Most of input values are 0 and 1. To reduce number of branches, we replace inner for loop with do-while. */ static BROTLI_NOINLINE void InverseMoveToFrontTransform( uint8_t* v, uint32_t v_len, BrotliDecoderState* state) { … } /* Decodes a series of Huffman table using ReadHuffmanCode function. */ static BrotliDecoderErrorCode HuffmanTreeGroupDecode( HuffmanTreeGroup* group, BrotliDecoderState* s) { … } /* Decodes a context map. Decoding is done in 4 phases: 1) Read auxiliary information (6..16 bits) and allocate memory. In case of trivial context map, decoding is finished at this phase. 2) Decode Huffman table using ReadHuffmanCode function. This table will be used for reading context map items. 3) Read context map items; "0" values could be run-length encoded. 4) Optionally, apply InverseMoveToFront transform to the resulting map. */ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, uint32_t* num_htrees, uint8_t** context_map_arg, BrotliDecoderState* s) { … } /* Decodes a command or literal and updates block type ring-buffer. Reads 3..54 bits. */ static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength( int safe, BrotliDecoderState* s, int tree_type) { … } static BROTLI_INLINE void DetectTrivialLiteralBlockTypes( BrotliDecoderState* s) { … } static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) { … } /* Decodes the block type and updates the state for literal context. Reads 3..54 bits. */ static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal( int safe, BrotliDecoderState* s) { … } static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) { … } static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch( BrotliDecoderState* s) { … } /* Block switch for insert/copy length. Reads 3..54 bits. */ static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal( int safe, BrotliDecoderState* s) { … } static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) { … } static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch( BrotliDecoderState* s) { … } /* Block switch for distance codes. Reads 3..54 bits. */ static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal( int safe, BrotliDecoderState* s) { … } static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) { … } static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch( BrotliDecoderState* s) { … } static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) { … } /* Dumps output. Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push and either ring-buffer is as big as window size, or |force| is true. */ static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer( BrotliDecoderState* s, size_t* available_out, uint8_t** next_out, size_t* total_out, BROTLI_BOOL force) { … } static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) { … } /* Allocates ring-buffer. s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before this function is called. Last two bytes of ring-buffer are initialized to 0, so context calculation could be done uniformly for the first two and all other positions. */ static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer( BrotliDecoderState* s) { … } static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( size_t* available_out, uint8_t** next_out, size_t* total_out, BrotliDecoderState* s) { … } static BROTLI_BOOL AttachCompoundDictionary( BrotliDecoderState* state, const uint8_t* data, size_t size) { … } static void EnsureCoumpoundDictionaryInitialized(BrotliDecoderState* state) { … } static BROTLI_BOOL InitializeCompoundDictionaryCopy(BrotliDecoderState* s, int address, int length) { … } static int GetCompoundDictionarySize(BrotliDecoderState* s) { … } static int CopyFromCompoundDictionary(BrotliDecoderState* s, int pos) { … } BROTLI_BOOL BrotliDecoderAttachDictionary( BrotliDecoderState* state, BrotliSharedDictionaryType type, size_t data_size, const uint8_t data[BROTLI_ARRAY_PARAM(data_size)]) { … } /* Calculates the smallest feasible ring buffer. If we know the data size is small, do not allocate more ring buffer size than needed to reduce memory usage. When this method is called, metablock size and flags MUST be decoded. */ static void BROTLI_NOINLINE BrotliCalculateRingBufferSize( BrotliDecoderState* s) { … } /* Reads 1..256 2-bit context modes. */ static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) { … } static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) { … } static BROTLI_INLINE BROTLI_BOOL SafeReadBits( BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { … } static BROTLI_INLINE BROTLI_BOOL SafeReadBits32( BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { … } /* RFC 7932 Section 4 with "..." shortenings and "[]" emendations. Each distance ... is represented with a pair <distance code, extra bits>... The distance code is encoded using a prefix code... The number of extra bits can be 0..24... Two additional parameters: NPOSTFIX (0..3), and ... NDIRECT (0..120) ... are encoded in the meta-block header... The first 16 distance symbols ... reference past distances... ring buffer ... Next NDIRECT distance symbols ... represent distances from 1 to NDIRECT... [For] distance symbols 16 + NDIRECT and greater ... the number of extra bits ... is given by the following formula: [ xcode = dcode - NDIRECT - 16 ] ndistbits = 1 + [ xcode ] >> (NPOSTFIX + 1) ... */ /* RFC 7932 Section 9.2 with "..." shortenings and "[]" emendations. ... to get the actual value of the parameter NDIRECT, left-shift this four-bit number by NPOSTFIX bits ... */ /* Remaining formulas from RFC 7932 Section 4 could be rewritten as following: alphabet_size = 16 + NDIRECT + (max_distbits << (NPOSTFIX + 1)) half = ((xcode >> NPOSTFIX) & 1) << ndistbits postfix = xcode & ((1 << NPOSTFIX) - 1) range_start = 2 * (1 << ndistbits - 1 - 1) distance = (range_start + half + extra) << NPOSTFIX + postfix + NDIRECT + 1 NB: ndistbits >= 1 -> range_start >= 0 NB: range_start has factor 2, as the range is covered by 2 "halves" NB: extra -1 offset in range_start formula covers the absence of ndistbits = 0 case NB: when NPOSTFIX = 0, NDIRECT is not greater than 15 In other words, xcode has the following binary structure - XXXHPPP: - XXX represent the number of extra distance bits - H selects upper / lower range of distances - PPP represent "postfix" "Regular" distance encoding has NPOSTFIX = 0; omitting the postfix part simplifies distance calculation. Using NPOSTFIX > 0 allows cheaper encoding of regular structures, e.g. where most of distances have the same reminder of division by 2/4/8. For example, the table of int32_t values that come from different sources; if it is likely that 3 highest bytes of values from the same source are the same, then copy distance often looks like 4x + y. Distance calculation could be rewritten to: ndistbits = NDISTBITS(NDIRECT, NPOSTFIX)[dcode] distance = OFFSET(NDIRECT, NPOSTFIX)[dcode] + extra << NPOSTFIX NDISTBITS and OFFSET could be pre-calculated, as NDIRECT and NPOSTFIX could change only once per meta-block. */ /* Calculates distance lookup table. NB: it is possible to have all 64 tables precalculated. */ static void CalculateDistanceLut(BrotliDecoderState* s) { … } /* Precondition: s->distance_code < 0. */ static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal( int safe, BrotliDecoderState* s, BrotliBitReader* br) { … } static BROTLI_INLINE void ReadDistance( BrotliDecoderState* s, BrotliBitReader* br) { … } static BROTLI_INLINE BROTLI_BOOL SafeReadDistance( BrotliDecoderState* s, BrotliBitReader* br) { … } static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal( int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { … } static BROTLI_INLINE void ReadCommand( BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { … } static BROTLI_INLINE BROTLI_BOOL SafeReadCommand( BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { … } static BROTLI_INLINE BROTLI_BOOL CheckInputAmount( int safe, BrotliBitReader* const br, size_t num) { … } #define BROTLI_SAFE … static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal( int safe, BrotliDecoderState* s) { … } #undef BROTLI_SAFE static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands( BrotliDecoderState* s) { … } static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands( BrotliDecoderState* s) { … } BrotliDecoderResult BrotliDecoderDecompress( size_t encoded_size, const uint8_t encoded_buffer[BROTLI_ARRAY_PARAM(encoded_size)], size_t* decoded_size, uint8_t decoded_buffer[BROTLI_ARRAY_PARAM(*decoded_size)]) { … } /* Invariant: input stream is never overconsumed: - invalid input implies that the whole stream is invalid -> any amount of input could be read and discarded - when result is "needs more input", then at least one more byte is REQUIRED to complete decoding; all input data MUST be consumed by decoder, so client could swap the input buffer - when result is "needs more output" decoder MUST ensure that it doesn't hold more than 7 bits in bit reader; this saves client from swapping input buffer ahead of time - when result is "success" decoder MUST return all unused data back to input buffer; this is possible because the invariant is held on enter */ BrotliDecoderResult BrotliDecoderDecompressStream( BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in, size_t* available_out, uint8_t** next_out, size_t* total_out) { … } BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) { … } const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) { … } BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) { … } BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) { … } BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) { … } const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) { … } uint32_t BrotliDecoderVersion() { … } /* Escalate internal functions visibility; for testing purposes only. */ #if defined(BROTLI_TEST) BROTLI_BOOL SafeReadSymbolForTest( const HuffmanCode*, BrotliBitReader*, uint32_t*); BROTLI_BOOL SafeReadSymbolForTest( const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { return SafeReadSymbol(table, br, result); } void InverseMoveToFrontTransformForTest( uint8_t*, uint32_t, BrotliDecoderState*); void InverseMoveToFrontTransformForTest( uint8_t* v, uint32_t l, BrotliDecoderState* s) { InverseMoveToFrontTransform(v, l, s); } #endif #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ #endif
Codebase Browser
chromium