+++ /dev/null
-/* Copyright 2013 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
-#include <brotli/decode.h>\r
-\r
-#if defined(__ARM_NEON__)\r
-#include <arm_neon.h>\r
-#endif\r
-\r
-//#include <stdlib.h> /* free, malloc */\r
-//#include <string.h> /* memcpy, memset */\r
-\r
-#include "../common/constants.h"\r
-#include "../common/context.h"\r
-#include "../common/dictionary.h"\r
-#include "../common/platform.h"\r
-#include "../common/transform.h"\r
-#include "../common/version.h"\r
-#include "./bit_reader.h"\r
-#include "./huffman.h"\r
-#include "./prefix.h"\r
-#include "./state.h"\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-extern "C" {\r
-#endif\r
-\r
-#define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE)\r
-\r
-#define BROTLI_LOG_UINT(name) \\r
- BROTLI_LOG(("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)))\r
-#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \\r
- BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \\r
- (unsigned long)(idx), (unsigned long)array_name[idx]))\r
-\r
-#define HUFFMAN_TABLE_BITS 8U\r
-#define HUFFMAN_TABLE_MASK 0xFF\r
-\r
-/* We need the slack region for the following reasons:\r
- - doing up to two 16-byte copies for fast backward copying\r
- - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */\r
-static const uint32_t kRingBufferWriteAheadSlack = 42;\r
-\r
-static const uint8_t kCodeLengthCodeOrder[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
-\r
-/* Static prefix code for the complex code length code lengths. */\r
-static const uint8_t kCodeLengthPrefixLength[16] = {\r
- 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4,\r
-};\r
-\r
-static const uint8_t kCodeLengthPrefixValue[16] = {\r
- 0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,\r
-};\r
-\r
-BROTLI_BOOL BrotliDecoderSetParameter(\r
- BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) {\r
- if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE;\r
- switch (p) {\r
- case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION:\r
- state->canny_ringbuffer_allocation = !!value ? 0 : 1;\r
- return BROTLI_TRUE;\r
-\r
- case BROTLI_DECODER_PARAM_LARGE_WINDOW:\r
- state->large_window = TO_BROTLI_BOOL(!!value);\r
- return BROTLI_TRUE;\r
-\r
- default: return BROTLI_FALSE;\r
- }\r
-}\r
-\r
-BrotliDecoderState* BrotliDecoderCreateInstance(\r
- brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {\r
- BrotliDecoderState* state = 0;\r
- if (!alloc_func && !free_func) {\r
- state = (BrotliDecoderState*)BrDummyMalloc(sizeof(BrotliDecoderState));\r
- } else if (alloc_func && free_func) {\r
- state = (BrotliDecoderState*)alloc_func(opaque, sizeof(BrotliDecoderState));\r
- }\r
- if (state == 0) {\r
- BROTLI_DUMP();\r
- return 0;\r
- }\r
- if (!BrotliDecoderStateInit(state, alloc_func, free_func, opaque)) {\r
- BROTLI_DUMP();\r
- if (!alloc_func && !free_func) {\r
- BrDummyFree(state);\r
- } else if (alloc_func && free_func) {\r
- free_func(opaque, state);\r
- }\r
- return 0;\r
- }\r
- return state;\r
-}\r
-\r
-/* Deinitializes and frees BrotliDecoderState instance. */\r
-void BrotliDecoderDestroyInstance(BrotliDecoderState* state) {\r
- if (!state) {\r
- return;\r
- } else {\r
- brotli_free_func free_func = state->free_func;\r
- void* opaque = state->memory_manager_opaque;\r
- BrotliDecoderStateCleanup(state);\r
- free_func(opaque, state);\r
- }\r
-}\r
-\r
-/* Saves error code and converts it to BrotliDecoderResult. */\r
-static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode(\r
- BrotliDecoderState* s, BrotliDecoderErrorCode e) {\r
- s->error_code = (int)e;\r
- switch (e) {\r
- case BROTLI_DECODER_SUCCESS:\r
- return BROTLI_DECODER_RESULT_SUCCESS;\r
-\r
- case BROTLI_DECODER_NEEDS_MORE_INPUT:\r
- return BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT;\r
-\r
- case BROTLI_DECODER_NEEDS_MORE_OUTPUT:\r
- return BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT;\r
-\r
- default:\r
- return BROTLI_DECODER_RESULT_ERROR;\r
- }\r
-}\r
-\r
-/* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli".\r
- Precondition: bit-reader accumulator has at least 8 bits. */\r
-static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s,\r
- BrotliBitReader* br) {\r
- uint32_t n;\r
- BROTLI_BOOL large_window = s->large_window;\r
- s->large_window = BROTLI_FALSE;\r
- BrotliTakeBits(br, 1, &n);\r
- if (n == 0) {\r
- s->window_bits = 16;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- BrotliTakeBits(br, 3, &n);\r
- if (n != 0) {\r
- s->window_bits = 17 + n;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- BrotliTakeBits(br, 3, &n);\r
- if (n == 1) {\r
- if (large_window) {\r
- BrotliTakeBits(br, 1, &n);\r
- if (n == 1) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);\r
- }\r
- s->large_window = BROTLI_TRUE;\r
- return BROTLI_DECODER_SUCCESS;\r
- } else {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);\r
- }\r
- }\r
- if (n != 0) {\r
- s->window_bits = 8 + n;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- s->window_bits = 17;\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) {\r
-#if defined(__ARM_NEON__)\r
- vst1q_u8(dst, vld1q_u8(src));\r
-#else\r
- uint32_t buffer[4];\r
- memcpy(buffer, src, 16);\r
- memcpy(dst, buffer, 16);\r
-#endif\r
-}\r
-\r
-/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */\r
-static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8(\r
- BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) {\r
- uint32_t bits;\r
- switch (s->substate_decode_uint8) {\r
- case BROTLI_STATE_DECODE_UINT8_NONE:\r
- if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (bits == 0) {\r
- *value = 0;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_DECODE_UINT8_SHORT:\r
- if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) {\r
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (bits == 0) {\r
- *value = 1;\r
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- /* Use output value as a temporary storage. It MUST be persisted. */\r
- *value = bits;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_DECODE_UINT8_LONG:\r
- if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) {\r
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- *value = (1U << *value) + bits;\r
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
-\r
- default:\r
- return\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
- }\r
-}\r
-\r
-/* Decodes a metablock length and flags by reading 2 - 31 bits. */\r
-static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(\r
- BrotliDecoderState* s, BrotliBitReader* br) {\r
- uint32_t bits;\r
- unsigned int i;\r
- for (;;) {\r
- switch (s->substate_metablock_header) {\r
- case BROTLI_STATE_METABLOCK_HEADER_NONE:\r
- if (!BrotliSafeReadBits(br, 1, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->is_last_metablock = bits ? 1 : 0;\r
- s->meta_block_remaining_len = 0;\r
- s->is_uncompressed = 0;\r
- s->is_metadata = 0;\r
- if (!s->is_last_metablock) {\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;\r
- break;\r
- }\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_EMPTY:\r
- if (!BrotliSafeReadBits(br, 1, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (bits) {\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_NIBBLES:\r
- if (!BrotliSafeReadBits(br, 2, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->size_nibbles = (uint8_t)(bits + 4);\r
- s->loop_counter = 0;\r
- if (bits == 3) {\r
- s->is_metadata = 1;\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_RESERVED;\r
- break;\r
- }\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_SIZE:\r
- i = s->loop_counter;\r
- for (; i < (int)s->size_nibbles; ++i) {\r
- if (!BrotliSafeReadBits(br, 4, &bits)) {\r
- s->loop_counter = i;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE);\r
- }\r
- s->meta_block_remaining_len |= (int)(bits << (i * 4));\r
- }\r
- s->substate_metablock_header =\r
- BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED:\r
- if (!s->is_last_metablock) {\r
- if (!BrotliSafeReadBits(br, 1, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->is_uncompressed = bits ? 1 : 0;\r
- }\r
- ++s->meta_block_remaining_len;\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_RESERVED:\r
- if (!BrotliSafeReadBits(br, 1, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (bits != 0) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED);\r
- }\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_BYTES:\r
- if (!BrotliSafeReadBits(br, 2, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (bits == 0) {\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- s->size_nibbles = (uint8_t)bits;\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_METADATA:\r
- i = s->loop_counter;\r
- for (; i < (int)s->size_nibbles; ++i) {\r
- if (!BrotliSafeReadBits(br, 8, &bits)) {\r
- s->loop_counter = i;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) {\r
- return BROTLI_FAILURE(\r
- BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE);\r
- }\r
- s->meta_block_remaining_len |= (int)(bits << (i * 8));\r
- }\r
- ++s->meta_block_remaining_len;\r
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
-\r
- default:\r
- return\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
- }\r
- }\r
-}\r
-\r
-/* Decodes the Huffman code.\r
- This method doesn't read data from the bit reader, BUT drops the amount of\r
- bits that correspond to the decoded symbol.\r
- bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */\r
-static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits,\r
- const HuffmanCode* table,\r
- BrotliBitReader* br) {\r
- table += bits & HUFFMAN_TABLE_MASK;\r
- if (table->bits > HUFFMAN_TABLE_BITS) {\r
- uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS;\r
- BrotliDropBits(br, HUFFMAN_TABLE_BITS);\r
- table += table->value;\r
- table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits);\r
- }\r
- BrotliDropBits(br, table->bits);\r
- return table->value;\r
-}\r
-\r
-/* Reads and decodes the next Huffman code from bit-stream.\r
- This method peeks 16 bits of input and drops 0 - 15 of them. */\r
-static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table,\r
- BrotliBitReader* br) {\r
- return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br);\r
-}\r
-\r
-/* Same as DecodeSymbol, but it is known that there is less than 15 bits of\r
- input are currently available. */\r
-static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol(\r
- const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {\r
- uint32_t val;\r
- uint32_t available_bits = BrotliGetAvailableBits(br);\r
- if (available_bits == 0) {\r
- if (table->bits == 0) {\r
- *result = table->value;\r
- return BROTLI_TRUE;\r
- }\r
- return BROTLI_FALSE; /* No valid bits at all. */\r
- }\r
- val = (uint32_t)BrotliGetBitsUnmasked(br);\r
- table += val & HUFFMAN_TABLE_MASK;\r
- if (table->bits <= HUFFMAN_TABLE_BITS) {\r
- if (table->bits <= available_bits) {\r
- BrotliDropBits(br, table->bits);\r
- *result = table->value;\r
- return BROTLI_TRUE;\r
- } else {\r
- return BROTLI_FALSE; /* Not enough bits for the first level. */\r
- }\r
- }\r
- if (available_bits <= HUFFMAN_TABLE_BITS) {\r
- return BROTLI_FALSE; /* Not enough bits to move to the second level. */\r
- }\r
-\r
- /* Speculatively drop HUFFMAN_TABLE_BITS. */\r
- val = (val & BitMask(table->bits)) >> HUFFMAN_TABLE_BITS;\r
- available_bits -= HUFFMAN_TABLE_BITS;\r
- table += table->value + val;\r
- if (available_bits < table->bits) {\r
- return BROTLI_FALSE; /* Not enough bits for the second level. */\r
- }\r
-\r
- BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits);\r
- *result = table->value;\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol(\r
- const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {\r
- uint32_t val;\r
- if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {\r
- *result = DecodeSymbol(val, table, br);\r
- return BROTLI_TRUE;\r
- }\r
- return SafeDecodeSymbol(table, br, result);\r
-}\r
-\r
-/* Makes a look-up in first level Huffman table. Peeks 8 bits. */\r
-static BROTLI_INLINE void PreloadSymbol(int safe,\r
- const HuffmanCode* table,\r
- BrotliBitReader* br,\r
- uint32_t* bits,\r
- uint32_t* value) {\r
- if (safe) {\r
- return;\r
- }\r
- table += BrotliGetBits(br, HUFFMAN_TABLE_BITS);\r
- *bits = table->bits;\r
- *value = table->value;\r
-}\r
-\r
-/* Decodes the next Huffman code using data prepared by PreloadSymbol.\r
- Reads 0 - 15 bits. Also peeks 8 following bits. */\r
-static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table,\r
- BrotliBitReader* br,\r
- uint32_t* bits,\r
- uint32_t* value) {\r
- uint32_t result = *value;\r
- if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {\r
- uint32_t val = BrotliGet16BitsUnmasked(br);\r
- const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value;\r
- uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS));\r
- BrotliDropBits(br, HUFFMAN_TABLE_BITS);\r
- ext += (val >> HUFFMAN_TABLE_BITS) & mask;\r
- BrotliDropBits(br, ext->bits);\r
- result = ext->value;\r
- } else {\r
- BrotliDropBits(br, *bits);\r
- }\r
- PreloadSymbol(0, table, br, bits, value);\r
- return result;\r
-}\r
-\r
-static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) {\r
- uint32_t result = 0;\r
- while (x) {\r
- x >>= 1;\r
- ++result;\r
- }\r
- return result;\r
-}\r
-\r
-/* Reads (s->symbol + 1) symbols.\r
- Totally 1..4 symbols are read, 1..11 bits each.\r
- The list of symbols MUST NOT contain duplicates. */\r
-static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols(\r
- uint32_t alphabet_size, uint32_t max_symbol, BrotliDecoderState* s) {\r
- /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */\r
- BrotliBitReader* br = &s->br;\r
- uint32_t max_bits = Log2Floor(alphabet_size - 1);\r
- uint32_t i = s->sub_loop_counter;\r
- uint32_t num_symbols = s->symbol;\r
- while (i <= num_symbols) {\r
- uint32_t v;\r
- if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) {\r
- s->sub_loop_counter = i;\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (v >= max_symbol) {\r
- return\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET);\r
- }\r
- s->symbols_lists_array[i] = (uint16_t)v;\r
- BROTLI_LOG_UINT(s->symbols_lists_array[i]);\r
- ++i;\r
- }\r
-\r
- for (i = 0; i < num_symbols; ++i) {\r
- uint32_t k = i + 1;\r
- for (; k <= num_symbols; ++k) {\r
- if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME);\r
- }\r
- }\r
- }\r
-\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-/* Process single decoded symbol code length:\r
- A) reset the repeat variable\r
- B) remember code length (if it is not 0)\r
- C) extend corresponding index-chain\r
- D) reduce the Huffman space\r
- E) update the histogram */\r
-static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len,\r
- uint32_t* symbol, uint32_t* repeat, uint32_t* space,\r
- uint32_t* prev_code_len, uint16_t* symbol_lists,\r
- uint16_t* code_length_histo, int* next_symbol) {\r
- *repeat = 0;\r
- if (code_len != 0) { /* code_len == 1..15 */\r
- symbol_lists[next_symbol[code_len]] = (uint16_t)(*symbol);\r
- next_symbol[code_len] = (int)(*symbol);\r
- *prev_code_len = code_len;\r
- *space -= 32768U >> code_len;\r
- code_length_histo[code_len]++;\r
- BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n",\r
- (int)*symbol, (int)code_len));\r
- }\r
- (*symbol)++;\r
-}\r
-\r
-/* Process repeated symbol code length.\r
- A) Check if it is the extension of previous repeat sequence; if the decoded\r
- value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new\r
- symbol-skip\r
- B) Update repeat variable\r
- C) Check if operation is feasible (fits alphabet)\r
- D) For each symbol do the same operations as in ProcessSingleCodeLength\r
-\r
- PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or\r
- code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH */\r
-static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len,\r
- uint32_t repeat_delta, uint32_t alphabet_size, uint32_t* symbol,\r
- uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len,\r
- uint32_t* repeat_code_len, uint16_t* symbol_lists,\r
- uint16_t* code_length_histo, int* next_symbol) {\r
- uint32_t old_repeat;\r
- uint32_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */\r
- uint32_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */\r
- if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {\r
- new_len = *prev_code_len;\r
- extra_bits = 2;\r
- }\r
- if (*repeat_code_len != new_len) {\r
- *repeat = 0;\r
- *repeat_code_len = new_len;\r
- }\r
- old_repeat = *repeat;\r
- if (*repeat > 0) {\r
- *repeat -= 2;\r
- *repeat <<= extra_bits;\r
- }\r
- *repeat += repeat_delta + 3U;\r
- repeat_delta = *repeat - old_repeat;\r
- if (*symbol + repeat_delta > alphabet_size) {\r
- BROTLI_DUMP();\r
- *symbol = alphabet_size;\r
- *space = 0xFFFFF;\r
- return;\r
- }\r
- BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n",\r
- (int)*symbol, (int)(*symbol + repeat_delta - 1), (int)*repeat_code_len));\r
- if (*repeat_code_len != 0) {\r
- unsigned last = *symbol + repeat_delta;\r
- int next = next_symbol[*repeat_code_len];\r
- do {\r
- symbol_lists[next] = (uint16_t)*symbol;\r
- next = (int)*symbol;\r
- } while (++(*symbol) != last);\r
- next_symbol[*repeat_code_len] = next;\r
- *space -= repeat_delta << (15 - *repeat_code_len);\r
- code_length_histo[*repeat_code_len] =\r
- (uint16_t)(code_length_histo[*repeat_code_len] + repeat_delta);\r
- } else {\r
- *symbol += repeat_delta;\r
- }\r
-}\r
-\r
-/* Reads and decodes symbol codelengths. */\r
-static BrotliDecoderErrorCode ReadSymbolCodeLengths(\r
- uint32_t alphabet_size, BrotliDecoderState* s) {\r
- BrotliBitReader* br = &s->br;\r
- uint32_t symbol = s->symbol;\r
- uint32_t repeat = s->repeat;\r
- uint32_t space = s->space;\r
- uint32_t prev_code_len = s->prev_code_len;\r
- uint32_t repeat_code_len = s->repeat_code_len;\r
- uint16_t* symbol_lists = s->symbol_lists;\r
- uint16_t* code_length_histo = s->code_length_histo;\r
- int* next_symbol = s->next_symbol;\r
- if (!BrotliWarmupBitReader(br)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- while (symbol < alphabet_size && space > 0) {\r
- const HuffmanCode* p = s->table;\r
- uint32_t code_len;\r
- if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) {\r
- s->symbol = symbol;\r
- s->repeat = repeat;\r
- s->prev_code_len = prev_code_len;\r
- s->repeat_code_len = repeat_code_len;\r
- s->space = space;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- BrotliFillBitWindow16(br);\r
- p += BrotliGetBitsUnmasked(br) &\r
- BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);\r
- BrotliDropBits(br, p->bits); /* Use 1..5 bits. */\r
- code_len = p->value; /* code_len == 0..17 */\r
- if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {\r
- ProcessSingleCodeLength(code_len, &symbol, &repeat, &space,\r
- &prev_code_len, symbol_lists, code_length_histo, next_symbol);\r
- } else { /* code_len == 16..17, extra_bits == 2..3 */\r
- uint32_t extra_bits =\r
- (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3;\r
- uint32_t repeat_delta =\r
- (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(extra_bits);\r
- BrotliDropBits(br, extra_bits);\r
- ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,\r
- &symbol, &repeat, &space, &prev_code_len, &repeat_code_len,\r
- symbol_lists, code_length_histo, next_symbol);\r
- }\r
- }\r
- s->space = space;\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-static BrotliDecoderErrorCode SafeReadSymbolCodeLengths(\r
- uint32_t alphabet_size, BrotliDecoderState* s) {\r
- BrotliBitReader* br = &s->br;\r
- BROTLI_BOOL get_byte = BROTLI_FALSE;\r
- while (s->symbol < alphabet_size && s->space > 0) {\r
- const HuffmanCode* p = s->table;\r
- uint32_t code_len;\r
- uint32_t available_bits;\r
- uint32_t bits = 0;\r
- if (get_byte && !BrotliPullByte(br)) return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- get_byte = BROTLI_FALSE;\r
- available_bits = BrotliGetAvailableBits(br);\r
- if (available_bits != 0) {\r
- bits = (uint32_t)BrotliGetBitsUnmasked(br);\r
- }\r
- p += bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);\r
- if (p->bits > available_bits) {\r
- get_byte = BROTLI_TRUE;\r
- continue;\r
- }\r
- code_len = p->value; /* code_len == 0..17 */\r
- if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {\r
- BrotliDropBits(br, p->bits);\r
- ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space,\r
- &s->prev_code_len, s->symbol_lists, s->code_length_histo,\r
- s->next_symbol);\r
- } else { /* code_len == 16..17, extra_bits == 2..3 */\r
- uint32_t extra_bits = code_len - 14U;\r
- uint32_t repeat_delta = (bits >> p->bits) & BitMask(extra_bits);\r
- if (available_bits < p->bits + extra_bits) {\r
- get_byte = BROTLI_TRUE;\r
- continue;\r
- }\r
- BrotliDropBits(br, p->bits + extra_bits);\r
- ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,\r
- &s->symbol, &s->repeat, &s->space, &s->prev_code_len,\r
- &s->repeat_code_len, s->symbol_lists, s->code_length_histo,\r
- s->next_symbol);\r
- }\r
- }\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-/* Reads and decodes 15..18 codes using static prefix code.\r
- Each code is 2..4 bits long. In total 30..72 bits are used. */\r
-static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) {\r
- BrotliBitReader* br = &s->br;\r
- uint32_t num_codes = s->repeat;\r
- unsigned space = s->space;\r
- uint32_t i = s->sub_loop_counter;\r
- for (; i < BROTLI_CODE_LENGTH_CODES; ++i) {\r
- const uint8_t code_len_idx = kCodeLengthCodeOrder[i];\r
- uint32_t ix;\r
- uint32_t v;\r
- if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) {\r
- uint32_t available_bits = BrotliGetAvailableBits(br);\r
- if (available_bits != 0) {\r
- ix = BrotliGetBitsUnmasked(br) & 0xF;\r
- } else {\r
- ix = 0;\r
- }\r
- if (kCodeLengthPrefixLength[ix] > available_bits) {\r
- s->sub_loop_counter = i;\r
- s->repeat = num_codes;\r
- s->space = space;\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- }\r
- v = kCodeLengthPrefixValue[ix];\r
- BrotliDropBits(br, kCodeLengthPrefixLength[ix]);\r
- s->code_length_code_lengths[code_len_idx] = (uint8_t)v;\r
- BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx);\r
- if (v != 0) {\r
- space = space - (32U >> v);\r
- ++num_codes;\r
- ++s->code_length_histo[v];\r
- if (space - 1U >= 32U) {\r
- /* space is 0 or wrapped around. */\r
- break;\r
- }\r
- }\r
- }\r
- if (!(num_codes == 1 || space == 0)) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE);\r
- }\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-/* Decodes the Huffman tables.\r
- There are 2 scenarios:\r
- A) Huffman code contains only few symbols (1..4). Those symbols are read\r
- directly; their code lengths are defined by the number of symbols.\r
- For this scenario 4 - 49 bits will be read.\r
-\r
- B) 2-phase decoding:\r
- B.1) Small Huffman table is decoded; it is specified with code lengths\r
- encoded with predefined entropy code. 32 - 74 bits are used.\r
- B.2) Decoded table is used to decode code lengths of symbols in resulting\r
- Huffman table. In worst case 3520 bits are read. */\r
-static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size,\r
- uint32_t max_symbol,\r
- HuffmanCode* table,\r
- uint32_t* opt_table_size,\r
- BrotliDecoderState* s) {\r
- BrotliBitReader* br = &s->br;\r
- /* Unnecessary masking, but might be good for safety. */\r
- alphabet_size &= 0x7FF;\r
- /* State machine. */\r
- for (;;) {\r
- switch (s->substate_huffman) {\r
- case BROTLI_STATE_HUFFMAN_NONE:\r
- if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- BROTLI_LOG_UINT(s->sub_loop_counter);\r
- /* The value is used as follows:\r
- 1 for simple code;\r
- 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */\r
- if (s->sub_loop_counter != 1) {\r
- s->space = 32;\r
- s->repeat = 0; /* num_codes */\r
- memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) *\r
- (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1));\r
- memset(&s->code_length_code_lengths[0], 0,\r
- sizeof(s->code_length_code_lengths));\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;\r
- continue;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE:\r
- /* Read symbols, codes & code lengths directly. */\r
- if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->sub_loop_counter = 0;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_SIMPLE_READ: {\r
- BrotliDecoderErrorCode result =\r
- ReadSimpleHuffmanSymbols(alphabet_size, max_symbol, s);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- return result;\r
- }\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: {\r
- uint32_t table_size;\r
- if (s->symbol == 3) {\r
- uint32_t bits;\r
- if (!BrotliSafeReadBits(br, 1, &bits)) {\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->symbol += bits;\r
- }\r
- BROTLI_LOG_UINT(s->symbol);\r
- table_size = BrotliBuildSimpleHuffmanTable(\r
- table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol);\r
- if (opt_table_size) {\r
- *opt_table_size = table_size;\r
- }\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
-\r
- /* Decode Huffman-coded code lengths. */\r
- case BROTLI_STATE_HUFFMAN_COMPLEX: {\r
- uint32_t i;\r
- BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- return result;\r
- }\r
- BrotliBuildCodeLengthsHuffmanTable(s->table,\r
- s->code_length_code_lengths,\r
- s->code_length_histo);\r
- memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo));\r
- for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) {\r
- s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);\r
- s->symbol_lists[s->next_symbol[i]] = 0xFFFF;\r
- }\r
-\r
- s->symbol = 0;\r
- s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH;\r
- s->repeat = 0;\r
- s->repeat_code_len = 0;\r
- s->space = 32768;\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: {\r
- uint32_t table_size;\r
- BrotliDecoderErrorCode result = ReadSymbolCodeLengths(max_symbol, s);\r
- if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {\r
- result = SafeReadSymbolCodeLengths(max_symbol, s);\r
- }\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- return result;\r
- }\r
-\r
- if (s->space != 0) {\r
- BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)s->space));\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE);\r
- }\r
- table_size = BrotliBuildHuffmanTable(\r
- table, HUFFMAN_TABLE_BITS, s->symbol_lists, s->code_length_histo);\r
- if (opt_table_size) {\r
- *opt_table_size = table_size;\r
- }\r
- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
-\r
- default:\r
- return\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
- }\r
- }\r
-}\r
-\r
-/* Decodes a block length by reading 3..39 bits. */\r
-static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table,\r
- BrotliBitReader* br) {\r
- uint32_t code;\r
- uint32_t nbits;\r
- code = ReadSymbol(table, br);\r
- ASSERT (code < BROTLI_NUM_BLOCK_LEN_SYMBOLS);\r
- nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */\r
- return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits);\r
-}\r
-\r
-/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then\r
- reading can't be continued with ReadBlockLength. */\r
-static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength(\r
- BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table,\r
- BrotliBitReader* br) {\r
- uint32_t index;\r
- if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) {\r
- if (!SafeReadSymbol(table, br, &index)) {\r
- return BROTLI_FALSE;\r
- }\r
- } else {\r
- index = s->block_length_index;\r
- }\r
- {\r
- uint32_t bits;\r
- uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */\r
- if (!BrotliSafeReadBits(br, nbits, &bits)) {\r
- s->block_length_index = index;\r
- s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX;\r
- return BROTLI_FALSE;\r
- }\r
- *result = kBlockLengthPrefixCode[index].offset + bits;\r
- s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;\r
- return BROTLI_TRUE;\r
- }\r
-}\r
-\r
-/* Transform:\r
- 1) initialize list L with values 0, 1,... 255\r
- 2) For each input element X:\r
- 2.1) let Y = L[X]\r
- 2.2) remove X-th element from L\r
- 2.3) prepend Y to L\r
- 2.4) append Y to output\r
-\r
- In most cases max(Y) <= 7, so most of L remains intact.\r
- To reduce the cost of initialization, we reuse L, remember the upper bound\r
- of Y values, and reinitialize only first elements in L.\r
-\r
- Most of input values are 0 and 1. To reduce number of branches, we replace\r
- inner for loop with do-while. */\r
-static BROTLI_NOINLINE void InverseMoveToFrontTransform(\r
- uint8_t* v, uint32_t v_len, BrotliDecoderState* state) {\r
- /* Reinitialize elements that could have been changed. */\r
- uint32_t i = 1;\r
- uint32_t upper_bound = state->mtf_upper_bound;\r
- uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */\r
- uint8_t* mtf_u8 = (uint8_t*)mtf;\r
- uint8_t* mtf_u8t = mtf_u8 - 1;\r
- /* Load endian-aware constant. */\r
- const uint8_t b0123[4] = {0, 1, 2, 3};\r
- uint32_t pattern;\r
- memcpy(&pattern, &b0123, 4);\r
-\r
- /* Initialize list using 4 consequent values pattern. */\r
- mtf[0] = pattern;\r
- do {\r
- pattern += 0x04040404; /* Advance all 4 values by 4. */\r
- mtf[i] = pattern;\r
- i++;\r
- } while (i <= upper_bound);\r
-\r
- /* Transform the input. */\r
- upper_bound = 0;\r
- for (i = 0; i < v_len; ++i) {\r
- int index = v[i];\r
- uint8_t value = mtf_u8[index];\r
- upper_bound |= (uint32_t) v[i];\r
- v[i] = value;\r
- mtf_u8t[0] = value;\r
- while (index >= 0) {\r
- mtf_u8t[index + 1] = mtf_u8t[index];\r
- index--;\r
- }\r
- }\r
- /* Remember amount of elements to be reinitialized. */\r
- state->mtf_upper_bound = upper_bound >> 2;\r
-}\r
-\r
-/* Decodes a series of Huffman table using ReadHuffmanCode function. */\r
-static BrotliDecoderErrorCode HuffmanTreeGroupDecode(\r
- HuffmanTreeGroup* group, BrotliDecoderState* s) {\r
- if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {\r
- s->next = group->codes;\r
- s->htree_index = 0;\r
- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP;\r
- }\r
- while (s->htree_index < group->num_htrees) {\r
- uint32_t table_size;\r
- BrotliDecoderErrorCode result =\r
- ReadHuffmanCode(group->alphabet_size, group->max_symbol,\r
- s->next, &table_size, s);\r
- if (result != BROTLI_DECODER_SUCCESS) return result;\r
- group->htrees[s->htree_index] = s->next;\r
- s->next += table_size;\r
- ++s->htree_index;\r
- }\r
- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-/* Decodes a context map.\r
- Decoding is done in 4 phases:\r
- 1) Read auxiliary information (6..16 bits) and allocate memory.\r
- In case of trivial context map, decoding is finished at this phase.\r
- 2) Decode Huffman table using ReadHuffmanCode function.\r
- This table will be used for reading context map items.\r
- 3) Read context map items; "0" values could be run-length encoded.\r
- 4) Optionally, apply InverseMoveToFront transform to the resulting map. */\r
-static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size,\r
- uint32_t* num_htrees,\r
- uint8_t** context_map_arg,\r
- BrotliDecoderState* s) {\r
- BrotliBitReader* br = &s->br;\r
- BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;\r
-\r
- switch ((int)s->substate_context_map) {\r
- case BROTLI_STATE_CONTEXT_MAP_NONE:\r
- result = DecodeVarLenUint8(s, br, num_htrees);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- return result;\r
- }\r
- (*num_htrees)++;\r
- s->context_index = 0;\r
- BROTLI_LOG_UINT(context_map_size);\r
- BROTLI_LOG_UINT(*num_htrees);\r
- *context_map_arg =\r
- (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)context_map_size);\r
- if (*context_map_arg == 0) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP);\r
- }\r
- if (*num_htrees <= 1) {\r
- memset(*context_map_arg, 0, (size_t)context_map_size);\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: {\r
- uint32_t bits;\r
- /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe\r
- to peek 4 bits ahead. */\r
- if (!BrotliSafeGetBits(br, 5, &bits)) {\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if ((bits & 1) != 0) { /* Use RLE for zeros. */\r
- s->max_run_length_prefix = (bits >> 1) + 1;\r
- BrotliDropBits(br, 5);\r
- } else {\r
- s->max_run_length_prefix = 0;\r
- BrotliDropBits(br, 1);\r
- }\r
- BROTLI_LOG_UINT(s->max_run_length_prefix);\r
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MAP_HUFFMAN: {\r
- uint32_t alphabet_size = *num_htrees + s->max_run_length_prefix;\r
- result = ReadHuffmanCode(alphabet_size, alphabet_size,\r
- s->context_map_table, NULL, s);\r
- if (result != BROTLI_DECODER_SUCCESS) return result;\r
- s->code = 0xFFFF;\r
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MAP_DECODE: {\r
- uint32_t context_index = s->context_index;\r
- uint32_t max_run_length_prefix = s->max_run_length_prefix;\r
- uint8_t* context_map = *context_map_arg;\r
- uint32_t code = s->code;\r
- BROTLI_BOOL skip_preamble = (code != 0xFFFF);\r
- while (context_index < context_map_size || skip_preamble) {\r
- if (!skip_preamble) {\r
- if (!SafeReadSymbol(s->context_map_table, br, &code)) {\r
- s->code = 0xFFFF;\r
- s->context_index = context_index;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- BROTLI_LOG_UINT(code);\r
-\r
- if (code == 0) {\r
- context_map[context_index++] = 0;\r
- continue;\r
- }\r
- if (code > max_run_length_prefix) {\r
- context_map[context_index++] =\r
- (uint8_t)(code - max_run_length_prefix);\r
- continue;\r
- }\r
- } else {\r
- skip_preamble = BROTLI_FALSE;\r
- }\r
- /* RLE sub-stage. */\r
- {\r
- uint32_t reps;\r
- if (!BrotliSafeReadBits(br, code, &reps)) {\r
- s->code = code;\r
- s->context_index = context_index;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- reps += 1U << code;\r
- BROTLI_LOG_UINT(reps);\r
- if (context_index + reps > context_map_size) {\r
- return\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT);\r
- }\r
- do {\r
- context_map[context_index++] = 0;\r
- } while (--reps);\r
- }\r
- }\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: {\r
- uint32_t bits;\r
- if (!BrotliSafeReadBits(br, 1, &bits)) {\r
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- if (bits != 0) {\r
- InverseMoveToFrontTransform(*context_map_arg, context_map_size, s);\r
- }\r
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
-\r
- default:\r
- return\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
- }\r
-}\r
-\r
-/* Decodes a command or literal and updates block type ring-buffer.\r
- Reads 3..54 bits. */\r
-static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength(\r
- int safe, BrotliDecoderState* s, int tree_type) {\r
- uint32_t max_block_type = s->num_block_types[tree_type];\r
- const HuffmanCode* type_tree = &s->block_type_trees[\r
- tree_type * BROTLI_HUFFMAN_MAX_SIZE_258];\r
- const HuffmanCode* len_tree = &s->block_len_trees[\r
- tree_type * BROTLI_HUFFMAN_MAX_SIZE_26];\r
- BrotliBitReader* br = &s->br;\r
- uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2];\r
- uint32_t block_type;\r
- if (max_block_type <= 1) {\r
- return BROTLI_FALSE;\r
- }\r
-\r
- /* Read 0..15 + 3..39 bits. */\r
- if (!safe) {\r
- block_type = ReadSymbol(type_tree, br);\r
- s->block_length[tree_type] = ReadBlockLength(len_tree, br);\r
- } else {\r
- BrotliBitReaderState memento;\r
- BrotliBitReaderSaveState(br, &memento);\r
- if (!SafeReadSymbol(type_tree, br, &block_type)) return BROTLI_FALSE;\r
- if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) {\r
- s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;\r
- BrotliBitReaderRestoreState(br, &memento);\r
- return BROTLI_FALSE;\r
- }\r
- }\r
-\r
- if (block_type == 1) {\r
- block_type = ringbuffer[1] + 1;\r
- } else if (block_type == 0) {\r
- block_type = ringbuffer[0];\r
- } else {\r
- block_type -= 2;\r
- }\r
- if (block_type >= max_block_type) {\r
- block_type -= max_block_type;\r
- }\r
- ringbuffer[0] = ringbuffer[1];\r
- ringbuffer[1] = block_type;\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(\r
- BrotliDecoderState* s) {\r
- size_t i;\r
- for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0;\r
- for (i = 0; i < s->num_block_types[0]; i++) {\r
- size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS;\r
- size_t error = 0;\r
- size_t sample = s->context_map[offset];\r
- size_t j;\r
- for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) {\r
- BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;)\r
- }\r
- if (error == 0) {\r
- s->trivial_literal_contexts[i >> 5] |= 1u << (i & 31);\r
- }\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) {\r
- uint8_t context_mode;\r
- size_t trivial;\r
- uint32_t block_type = s->block_type_rb[1];\r
- uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS;\r
- s->context_map_slice = s->context_map + context_offset;\r
- trivial = s->trivial_literal_contexts[block_type >> 5];\r
- s->trivial_literal_context = (trivial >> (block_type & 31)) & 1;\r
- s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]];\r
- context_mode = s->context_modes[block_type] & 3;\r
- s->context_lookup = BROTLI_CONTEXT_LUT(context_mode);\r
-}\r
-\r
-/* Decodes the block type and updates the state for literal context.\r
- Reads 3..54 bits. */\r
-static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal(\r
- int safe, BrotliDecoderState* s) {\r
- if (!DecodeBlockTypeAndLength(safe, s, 0)) {\r
- return BROTLI_FALSE;\r
- }\r
- PrepareLiteralDecoding(s);\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) {\r
- DecodeLiteralBlockSwitchInternal(0, s);\r
-}\r
-\r
-static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(\r
- BrotliDecoderState* s) {\r
- return DecodeLiteralBlockSwitchInternal(1, s);\r
-}\r
-\r
-/* Block switch for insert/copy length.\r
- Reads 3..54 bits. */\r
-static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal(\r
- int safe, BrotliDecoderState* s) {\r
- if (!DecodeBlockTypeAndLength(safe, s, 1)) {\r
- return BROTLI_FALSE;\r
- }\r
- s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]];\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) {\r
- DecodeCommandBlockSwitchInternal(0, s);\r
-}\r
-\r
-static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(\r
- BrotliDecoderState* s) {\r
- return DecodeCommandBlockSwitchInternal(1, s);\r
-}\r
-\r
-/* Block switch for distance codes.\r
- Reads 3..54 bits. */\r
-static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal(\r
- int safe, BrotliDecoderState* s) {\r
- if (!DecodeBlockTypeAndLength(safe, s, 2)) {\r
- return BROTLI_FALSE;\r
- }\r
- s->dist_context_map_slice = s->dist_context_map +\r
- (s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS);\r
- s->dist_htree_index = s->dist_context_map_slice[s->distance_context];\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) {\r
- DecodeDistanceBlockSwitchInternal(0, s);\r
-}\r
-\r
-static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(\r
- BrotliDecoderState* s) {\r
- return DecodeDistanceBlockSwitchInternal(1, s);\r
-}\r
-\r
-static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) {\r
- size_t pos = wrap && s->pos > s->ringbuffer_size ?\r
- (size_t)s->ringbuffer_size : (size_t)(s->pos);\r
- size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos;\r
- return partial_pos_rb - s->partial_pos_out;\r
-}\r
-\r
-/* Dumps output.\r
- Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push\r
- and either ring-buffer is as big as window size, or |force| is true. */\r
-static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer(\r
- BrotliDecoderState* s, size_t* available_out, uint8_t** next_out,\r
- size_t* total_out, BROTLI_BOOL force) {\r
- uint8_t* start =\r
- s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask);\r
- size_t to_write = UnwrittenBytes(s, BROTLI_TRUE);\r
- size_t num_written = *available_out;\r
- if (num_written > to_write) {\r
- num_written = to_write;\r
- }\r
- if (s->meta_block_remaining_len < 0) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1);\r
- }\r
- if (next_out && !*next_out) {\r
- *next_out = start;\r
- } else {\r
- if (next_out) {\r
- memcpy(*next_out, start, num_written);\r
- *next_out += num_written;\r
- }\r
- }\r
- *available_out -= num_written;\r
- BROTLI_LOG_UINT(to_write);\r
- BROTLI_LOG_UINT(num_written);\r
- s->partial_pos_out += num_written;\r
- if (total_out) {\r
- *total_out = s->partial_pos_out;\r
- }\r
- if (num_written < to_write) {\r
- if (s->ringbuffer_size == (1 << s->window_bits) || force) {\r
- return BROTLI_DECODER_NEEDS_MORE_OUTPUT;\r
- } else {\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- }\r
- /* Wrap ring buffer only if it has reached its maximal size. */\r
- if (s->ringbuffer_size == (1 << s->window_bits) &&\r
- s->pos >= s->ringbuffer_size) {\r
- s->pos -= s->ringbuffer_size;\r
- s->rb_roundtrips++;\r
- s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0;\r
- }\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) {\r
- if (s->should_wrap_ringbuffer) {\r
- memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);\r
- s->should_wrap_ringbuffer = 0;\r
- }\r
-}\r
-\r
-/* Allocates ring-buffer.\r
-\r
- s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before\r
- this function is called.\r
-\r
- Last two bytes of ring-buffer are initialized to 0, so context calculation\r
- could be done uniformly for the first two and all other positions. */\r
-static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer(\r
- BrotliDecoderState* s) {\r
- uint8_t* old_ringbuffer = s->ringbuffer;\r
- if (s->ringbuffer_size == s->new_ringbuffer_size) {\r
- return BROTLI_TRUE;\r
- }\r
-\r
- s->ringbuffer = (uint8_t*)BROTLI_DECODER_ALLOC(s,\r
- (size_t)(s->new_ringbuffer_size) + kRingBufferWriteAheadSlack);\r
- if (s->ringbuffer == 0) {\r
- /* Restore previous value. */\r
- s->ringbuffer = old_ringbuffer;\r
- return BROTLI_FALSE;\r
- }\r
- s->ringbuffer[s->new_ringbuffer_size - 2] = 0;\r
- s->ringbuffer[s->new_ringbuffer_size - 1] = 0;\r
-\r
- if (!!old_ringbuffer) {\r
- memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos);\r
- BROTLI_DECODER_FREE(s, old_ringbuffer);\r
- }\r
-\r
- s->ringbuffer_size = s->new_ringbuffer_size;\r
- s->ringbuffer_mask = s->new_ringbuffer_size - 1;\r
- s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;\r
-\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(\r
- size_t* available_out, uint8_t** next_out, size_t* total_out,\r
- BrotliDecoderState* s) {\r
- /* TODO: avoid allocation for single uncompressed block. */\r
- if (!BrotliEnsureRingBuffer(s)) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1);\r
- }\r
-\r
- /* State machine */\r
- for (;;) {\r
- switch (s->substate_uncompressed) {\r
- case BROTLI_STATE_UNCOMPRESSED_NONE: {\r
- int nbytes = (int)BrotliGetRemainingBytes(&s->br);\r
- if (nbytes > s->meta_block_remaining_len) {\r
- nbytes = s->meta_block_remaining_len;\r
- }\r
- if (s->pos + nbytes > s->ringbuffer_size) {\r
- nbytes = s->ringbuffer_size - s->pos;\r
- }\r
- /* Copy remaining bytes from s->br.buf_ to ring-buffer. */\r
- BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes);\r
- s->pos += nbytes;\r
- s->meta_block_remaining_len -= nbytes;\r
- if (s->pos < 1 << s->window_bits) {\r
- if (s->meta_block_remaining_len == 0) {\r
- return BROTLI_DECODER_SUCCESS;\r
- }\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_UNCOMPRESSED_WRITE: {\r
- BrotliDecoderErrorCode result;\r
- result = WriteRingBuffer(\r
- s, available_out, next_out, total_out, BROTLI_FALSE);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- return result;\r
- }\r
- if (s->ringbuffer_size == 1 << s->window_bits) {\r
- s->max_distance = s->max_backward_distance;\r
- }\r
- s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;\r
- break;\r
- }\r
- }\r
- }\r
- BROTLI_DCHECK(0); /* Unreachable */\r
-}\r
-\r
-/* Calculates the smallest feasible ring buffer.\r
-\r
- If we know the data size is small, do not allocate more ring buffer\r
- size than needed to reduce memory usage.\r
-\r
- When this method is called, metablock size and flags MUST be decoded. */\r
-static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(\r
- BrotliDecoderState* s) {\r
- int window_size = 1 << s->window_bits;\r
- int new_ringbuffer_size = window_size;\r
- /* We need at least 2 bytes of ring buffer size to get the last two\r
- bytes for context from there */\r
- int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024;\r
- int output_size;\r
-\r
- /* If maximum is already reached, no further extension is retired. */\r
- if (s->ringbuffer_size == window_size) {\r
- return;\r
- }\r
-\r
- /* Metadata blocks does not touch ring buffer. */\r
- if (s->is_metadata) {\r
- return;\r
- }\r
-\r
- if (!s->ringbuffer) {\r
- output_size = 0;\r
- } else {\r
- output_size = s->pos;\r
- }\r
- output_size += s->meta_block_remaining_len;\r
- min_size = min_size < output_size ? output_size : min_size;\r
-\r
- if (!!s->canny_ringbuffer_allocation) {\r
- /* Reduce ring buffer size to save memory when server is unscrupulous.\r
- In worst case memory usage might be 1.5x bigger for a short period of\r
- ring buffer reallocation. */\r
- while ((new_ringbuffer_size >> 1) >= min_size) {\r
- new_ringbuffer_size >>= 1;\r
- }\r
- }\r
-\r
- s->new_ringbuffer_size = new_ringbuffer_size;\r
-}\r
-\r
-/* Reads 1..256 2-bit context modes. */\r
-static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) {\r
- BrotliBitReader* br = &s->br;\r
- int i = s->loop_counter;\r
-\r
- while (i < (int)s->num_block_types[0]) {\r
- uint32_t bits;\r
- if (!BrotliSafeReadBits(br, 2, &bits)) {\r
- s->loop_counter = i;\r
- return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- }\r
- s->context_modes[i] = (uint8_t)bits;\r
- BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);\r
- i++;\r
- }\r
- return BROTLI_DECODER_SUCCESS;\r
-}\r
-\r
-static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) {\r
- if (s->distance_code == 0) {\r
- --s->dist_rb_idx;\r
- s->distance_code = s->dist_rb[s->dist_rb_idx & 3];\r
- /* Compensate double distance-ring-buffer roll for dictionary items. */\r
- s->distance_context = 1;\r
- } else {\r
- int distance_code = s->distance_code << 1;\r
- /* kDistanceShortCodeIndexOffset has 2-bit values from LSB:\r
- 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */\r
- const uint32_t kDistanceShortCodeIndexOffset = 0xAAAFFF1B;\r
- /* kDistanceShortCodeValueOffset has 2-bit values from LSB:\r
- -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */\r
- const uint32_t kDistanceShortCodeValueOffset = 0xFA5FA500;\r
- int v = (s->dist_rb_idx +\r
- (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3;\r
- s->distance_code = s->dist_rb[v];\r
- v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3;\r
- if ((distance_code & 0x3) != 0) {\r
- s->distance_code += v;\r
- } else {\r
- s->distance_code -= v;\r
- if (s->distance_code <= 0) {\r
- /* A huge distance will cause a BROTLI_FAILURE() soon.\r
- This is a little faster than failing here. */\r
- s->distance_code = 0x7FFFFFFF;\r
- }\r
- }\r
- }\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL SafeReadBits(\r
- BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r
- if (n_bits != 0) {\r
- return BrotliSafeReadBits(br, n_bits, val);\r
- } else {\r
- *val = 0;\r
- return BROTLI_TRUE;\r
- }\r
-}\r
-\r
-/* Precondition: s->distance_code < 0. */\r
-static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal(\r
- int safe, BrotliDecoderState* s, BrotliBitReader* br) {\r
- int distval;\r
- BrotliBitReaderState memento;\r
- HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index];\r
- if (!safe) {\r
- s->distance_code = (int)ReadSymbol(distance_tree, br);\r
- } else {\r
- uint32_t code;\r
- BrotliBitReaderSaveState(br, &memento);\r
- if (!SafeReadSymbol(distance_tree, br, &code)) {\r
- return BROTLI_FALSE;\r
- }\r
- s->distance_code = (int)code;\r
- }\r
- /* Convert the distance code to the actual distance by possibly\r
- looking up past distances from the s->ringbuffer. */\r
- s->distance_context = 0;\r
- if ((s->distance_code & ~0xF) == 0) {\r
- TakeDistanceFromRingBuffer(s);\r
- --s->block_length[2];\r
- return BROTLI_TRUE;\r
- }\r
- distval = s->distance_code - (int)s->num_direct_distance_codes;\r
- if (distval >= 0) {\r
- uint32_t nbits;\r
- int postfix;\r
- int offset;\r
- if (!safe && (s->distance_postfix_bits == 0)) {\r
- nbits = ((uint32_t)distval >> 1) + 1;\r
- offset = ((2 + (distval & 1)) << nbits) - 4;\r
- s->distance_code = (int)s->num_direct_distance_codes + offset +\r
- (int)BrotliReadBits(br, nbits);\r
- } else {\r
- /* This branch also works well when s->distance_postfix_bits == 0. */\r
- uint32_t bits;\r
- postfix = distval & s->distance_postfix_mask;\r
- distval >>= s->distance_postfix_bits;\r
- nbits = ((uint32_t)distval >> 1) + 1;\r
- if (safe) {\r
- if (!SafeReadBits(br, nbits, &bits)) {\r
- s->distance_code = -1; /* Restore precondition. */\r
- BrotliBitReaderRestoreState(br, &memento);\r
- return BROTLI_FALSE;\r
- }\r
- } else {\r
- bits = BrotliReadBits(br, nbits);\r
- }\r
- offset = ((2 + (distval & 1)) << nbits) - 4;\r
- s->distance_code = (int)s->num_direct_distance_codes +\r
- ((offset + (int)bits) << s->distance_postfix_bits) + postfix;\r
- }\r
- }\r
- s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1;\r
- --s->block_length[2];\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static BROTLI_INLINE void ReadDistance(\r
- BrotliDecoderState* s, BrotliBitReader* br) {\r
- ReadDistanceInternal(0, s, br);\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL SafeReadDistance(\r
- BrotliDecoderState* s, BrotliBitReader* br) {\r
- return ReadDistanceInternal(1, s, br);\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal(\r
- int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {\r
- uint32_t cmd_code;\r
- uint32_t insert_len_extra = 0;\r
- uint32_t copy_length;\r
- CmdLutElement v;\r
- BrotliBitReaderState memento;\r
- if (!safe) {\r
- cmd_code = ReadSymbol(s->htree_command, br);\r
- ASSERT (cmd_code < BROTLI_NUM_COMMAND_SYMBOLS);\r
- } else {\r
- BrotliBitReaderSaveState(br, &memento);\r
- if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) {\r
- return BROTLI_FALSE;\r
- }\r
- }\r
- v = kCmdLut[cmd_code];\r
- s->distance_code = v.distance_code;\r
- s->distance_context = v.context;\r
- s->dist_htree_index = s->dist_context_map_slice[s->distance_context];\r
- *insert_length = v.insert_len_offset;\r
- if (!safe) {\r
- if (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) {\r
- insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits);\r
- }\r
- copy_length = BrotliReadBits(br, v.copy_len_extra_bits);\r
- } else {\r
- if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) ||\r
- !SafeReadBits(br, v.copy_len_extra_bits, ©_length)) {\r
- BrotliBitReaderRestoreState(br, &memento);\r
- return BROTLI_FALSE;\r
- }\r
- }\r
- s->copy_length = (int)copy_length + v.copy_len_offset;\r
- --s->block_length[1];\r
- *insert_length += (int)insert_len_extra;\r
- return BROTLI_TRUE;\r
-}\r
-\r
-static BROTLI_INLINE void ReadCommand(\r
- BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {\r
- ReadCommandInternal(0, s, br, insert_length);\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL SafeReadCommand(\r
- BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {\r
- return ReadCommandInternal(1, s, br, insert_length);\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL CheckInputAmount(\r
- int safe, BrotliBitReader* const br, size_t num) {\r
- if (safe) {\r
- return BROTLI_TRUE;\r
- }\r
- return BrotliCheckInputAmount(br, num);\r
-}\r
-\r
-#define BROTLI_SAFE(METHOD) \\r
- { \\r
- if (safe) { \\r
- if (!Safe##METHOD) { \\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT; \\r
- goto saveStateAndReturn; \\r
- } \\r
- } else { \\r
- METHOD; \\r
- } \\r
- }\r
-\r
-static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal(\r
- int safe, BrotliDecoderState* s) {\r
- int pos = s->pos;\r
- int i = s->loop_counter;\r
- BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;\r
- BrotliBitReader* br = &s->br;\r
-\r
- if (!CheckInputAmount(safe, br, 28)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- goto saveStateAndReturn;\r
- }\r
- if (!safe) {\r
- BROTLI_UNUSED(BrotliWarmupBitReader(br));\r
- }\r
-\r
- /* Jump into state machine. */\r
- if (s->state == BROTLI_STATE_COMMAND_BEGIN) {\r
- goto CommandBegin;\r
- } else if (s->state == BROTLI_STATE_COMMAND_INNER) {\r
- goto CommandInner;\r
- } else if (s->state == BROTLI_STATE_COMMAND_POST_DECODE_LITERALS) {\r
- goto CommandPostDecodeLiterals;\r
- } else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) {\r
- goto CommandPostWrapCopy;\r
- } else {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
- }\r
-\r
-CommandBegin:\r
- if (safe) {\r
- s->state = BROTLI_STATE_COMMAND_BEGIN;\r
- }\r
- if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */\r
- s->state = BROTLI_STATE_COMMAND_BEGIN;\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- goto saveStateAndReturn;\r
- }\r
- if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) {\r
- BROTLI_SAFE(DecodeCommandBlockSwitch(s));\r
- goto CommandBegin;\r
- }\r
- /* Read the insert/copy length in the command. */\r
- BROTLI_SAFE(ReadCommand(s, br, &i));\r
- BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",\r
- pos, i, s->copy_length));\r
- if (i == 0) {\r
- goto CommandPostDecodeLiterals;\r
- }\r
- s->meta_block_remaining_len -= i;\r
-\r
-CommandInner:\r
- if (safe) {\r
- s->state = BROTLI_STATE_COMMAND_INNER;\r
- }\r
- /* Read the literals in the command. */\r
- if (s->trivial_literal_context) {\r
- uint32_t bits;\r
- uint32_t value;\r
- PreloadSymbol(safe, s->literal_htree, br, &bits, &value);\r
- do {\r
- if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */\r
- s->state = BROTLI_STATE_COMMAND_INNER;\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- goto saveStateAndReturn;\r
- }\r
- if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {\r
- BROTLI_SAFE(DecodeLiteralBlockSwitch(s));\r
- PreloadSymbol(safe, s->literal_htree, br, &bits, &value);\r
- if (!s->trivial_literal_context) goto CommandInner;\r
- }\r
- if (!safe) {\r
- s->ringbuffer[pos] =\r
- (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value);\r
- } else {\r
- uint32_t literal;\r
- if (!SafeReadSymbol(s->literal_htree, br, &literal)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- goto saveStateAndReturn;\r
- }\r
- s->ringbuffer[pos] = (uint8_t)literal;\r
- }\r
- --s->block_length[0];\r
- BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos);\r
- ++pos;\r
- if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {\r
- s->state = BROTLI_STATE_COMMAND_INNER_WRITE;\r
- --i;\r
- goto saveStateAndReturn;\r
- }\r
- } while (--i != 0);\r
- } else {\r
- uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];\r
- uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];\r
- do {\r
- const HuffmanCode* hc;\r
- uint8_t context;\r
- if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */\r
- s->state = BROTLI_STATE_COMMAND_INNER;\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- goto saveStateAndReturn;\r
- }\r
- if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {\r
- BROTLI_SAFE(DecodeLiteralBlockSwitch(s));\r
- if (s->trivial_literal_context) goto CommandInner;\r
- }\r
- context = BROTLI_CONTEXT(p1, p2, s->context_lookup);\r
- BROTLI_LOG_UINT(context);\r
- hc = s->literal_hgroup.htrees[s->context_map_slice[context]];\r
- p2 = p1;\r
- if (!safe) {\r
- p1 = (uint8_t)ReadSymbol(hc, br);\r
- } else {\r
- uint32_t literal;\r
- if (!SafeReadSymbol(hc, br, &literal)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- goto saveStateAndReturn;\r
- }\r
- p1 = (uint8_t)literal;\r
- }\r
- s->ringbuffer[pos] = p1;\r
- --s->block_length[0];\r
- BROTLI_LOG_UINT(s->context_map_slice[context]);\r
- BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);\r
- ++pos;\r
- if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {\r
- s->state = BROTLI_STATE_COMMAND_INNER_WRITE;\r
- --i;\r
- goto saveStateAndReturn;\r
- }\r
- } while (--i != 0);\r
- }\r
- BROTLI_LOG_UINT(s->meta_block_remaining_len);\r
- if (BROTLI_PREDICT_FALSE(s->meta_block_remaining_len <= 0)) {\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- goto saveStateAndReturn;\r
- }\r
-\r
-CommandPostDecodeLiterals:\r
- if (safe) {\r
- s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;\r
- }\r
- if (s->distance_code >= 0) {\r
- /* Implicit distance case. */\r
- s->distance_context = s->distance_code ? 0 : 1;\r
- --s->dist_rb_idx;\r
- s->distance_code = s->dist_rb[s->dist_rb_idx & 3];\r
- } else {\r
- /* Read distance code in the command, unless it was implicitly zero. */\r
- if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) {\r
- BROTLI_SAFE(DecodeDistanceBlockSwitch(s));\r
- }\r
- BROTLI_SAFE(ReadDistance(s, br));\r
- }\r
- BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",\r
- pos, s->distance_code));\r
- if (s->max_distance != s->max_backward_distance) {\r
- s->max_distance =\r
- (pos < s->max_backward_distance) ? pos : s->max_backward_distance;\r
- }\r
- i = s->copy_length;\r
- /* Apply copy of LZ77 back-reference, or static dictionary reference if\r
- the distance is larger than the max LZ77 distance */\r
- if (s->distance_code > s->max_distance) {\r
- /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC.\r
- With this choice, no signed overflow can occur after decoding\r
- a special distance code (e.g., after adding 3 to the last distance). */\r
- if (s->distance_code > BROTLI_MAX_ALLOWED_DISTANCE) {\r
- BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "\r
- "len: %d bytes left: %d\n",\r
- pos, s->distance_code, i, s->meta_block_remaining_len));\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE);\r
- }\r
- if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH &&\r
- i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) {\r
- int address = s->distance_code - s->max_distance - 1;\r
- const BrotliDictionary* words = s->dictionary;\r
- const BrotliTransforms* transforms = s->transforms;\r
- int offset = (int)s->dictionary->offsets_by_length[i];\r
- uint32_t shift = s->dictionary->size_bits_by_length[i];\r
-\r
- int mask = (int)BitMask(shift);\r
- int word_idx = address & mask;\r
- int transform_idx = address >> shift;\r
- /* Compensate double distance-ring-buffer roll. */\r
- s->dist_rb_idx += s->distance_context;\r
- offset += word_idx * i;\r
- if (BROTLI_PREDICT_FALSE(!words->data)) {\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET);\r
- }\r
- if (transform_idx < (int)transforms->num_transforms) {\r
- const uint8_t* word = &words->data[offset];\r
- int len = i;\r
- if (transform_idx == transforms->cutOffTransforms[0]) {\r
- memcpy(&s->ringbuffer[pos], word, (size_t)len);\r
- BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n",\r
- len, word));\r
- } else {\r
- len = BrotliTransformDictionaryWord(&s->ringbuffer[pos], word, len,\r
- transforms, transform_idx);\r
- BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s],"\r
- " transform_idx = %d, transformed: [%.*s]\n",\r
- i, word, transform_idx, len, &s->ringbuffer[pos]));\r
- }\r
- pos += len;\r
- s->meta_block_remaining_len -= len;\r
- if (pos >= s->ringbuffer_size) {\r
- s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;\r
- goto saveStateAndReturn;\r
- }\r
- } else {\r
- BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "\r
- "len: %d bytes left: %d\n",\r
- pos, s->distance_code, i, s->meta_block_remaining_len));\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM);\r
- }\r
- } else {\r
- BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "\r
- "len: %d bytes left: %d\n",\r
- pos, s->distance_code, i, s->meta_block_remaining_len));\r
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY);\r
- }\r
- } else {\r
- int src_start = (pos - s->distance_code) & s->ringbuffer_mask;\r
- uint8_t* copy_dst = &s->ringbuffer[pos];\r
- uint8_t* copy_src = &s->ringbuffer[src_start];\r
- int dst_end = pos + i;\r
- int src_end = src_start + i;\r
- /* Update the recent distances cache. */\r
- s->dist_rb[s->dist_rb_idx & 3] = s->distance_code;\r
- ++s->dist_rb_idx;\r
- s->meta_block_remaining_len -= i;\r
- /* There are 32+ bytes of slack in the ring-buffer allocation.\r
- Also, we have 16 short codes, that make these 16 bytes irrelevant\r
- in the ring-buffer. Let's copy over them as a first guess. */\r
- memmove16(copy_dst, copy_src);\r
- if (src_end > pos && dst_end > src_start) {\r
- /* Regions intersect. */\r
- goto CommandPostWrapCopy;\r
- }\r
- if (dst_end >= s->ringbuffer_size || src_end >= s->ringbuffer_size) {\r
- /* At least one region wraps. */\r
- goto CommandPostWrapCopy;\r
- }\r
- pos += i;\r
- if (i > 16) {\r
- if (i > 32) {\r
- memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16));\r
- } else {\r
- /* This branch covers about 45% cases.\r
- Fixed size short copy allows more compiler optimizations. */\r
- memmove16(copy_dst + 16, copy_src + 16);\r
- }\r
- }\r
- }\r
- BROTLI_LOG_UINT(s->meta_block_remaining_len);\r
- if (s->meta_block_remaining_len <= 0) {\r
- /* Next metablock, if any. */\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- goto saveStateAndReturn;\r
- } else {\r
- goto CommandBegin;\r
- }\r
-CommandPostWrapCopy:\r
- {\r
- int wrap_guard = s->ringbuffer_size - pos;\r
- while (--i >= 0) {\r
- s->ringbuffer[pos] =\r
- s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];\r
- ++pos;\r
- if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) {\r
- s->state = BROTLI_STATE_COMMAND_POST_WRITE_2;\r
- goto saveStateAndReturn;\r
- }\r
- }\r
- }\r
- if (s->meta_block_remaining_len <= 0) {\r
- /* Next metablock, if any. */\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- goto saveStateAndReturn;\r
- } else {\r
- goto CommandBegin;\r
- }\r
-\r
-saveStateAndReturn:\r
- s->pos = pos;\r
- s->loop_counter = i;\r
- return result;\r
-}\r
-\r
-#undef BROTLI_SAFE\r
-\r
-static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands(\r
- BrotliDecoderState* s) {\r
- return ProcessCommandsInternal(0, s);\r
-}\r
-\r
-static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands(\r
- BrotliDecoderState* s) {\r
- return ProcessCommandsInternal(1, s);\r
-}\r
-\r
-/* Returns the maximum number of distance symbols which can only represent\r
- distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */\r
-static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect, uint32_t npostfix) {\r
- static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28};\r
- static const uint32_t diff[BROTLI_MAX_NPOSTFIX + 1] = {73, 126, 228, 424};\r
- uint32_t postfix = 1U << npostfix;\r
- if (ndirect < bound[npostfix]) {\r
- return ndirect + diff[npostfix] + postfix;\r
- } else if (ndirect > bound[npostfix] + postfix) {\r
- return ndirect + diff[npostfix];\r
- } else {\r
- return bound[npostfix] + diff[npostfix] + postfix;\r
- }\r
-}\r
-\r
-BrotliDecoderResult BrotliDecoderDecompress(\r
- size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,\r
- uint8_t* decoded_buffer) {\r
- BrotliDecoderState s;\r
- BrotliDecoderResult result;\r
- size_t total_out = 0;\r
- size_t available_in = encoded_size;\r
- const uint8_t* next_in = encoded_buffer;\r
- size_t available_out = *decoded_size;\r
- uint8_t* next_out = decoded_buffer;\r
- if (!BrotliDecoderStateInit(&s, 0, 0, 0)) {\r
- return BROTLI_DECODER_RESULT_ERROR;\r
- }\r
- result = BrotliDecoderDecompressStream(\r
- &s, &available_in, &next_in, &available_out, &next_out, &total_out);\r
- *decoded_size = total_out;\r
- BrotliDecoderStateCleanup(&s);\r
- if (result != BROTLI_DECODER_RESULT_SUCCESS) {\r
- result = BROTLI_DECODER_RESULT_ERROR;\r
- }\r
- return result;\r
-}\r
-\r
-/* Invariant: input stream is never overconsumed:\r
- - invalid input implies that the whole stream is invalid -> any amount of\r
- input could be read and discarded\r
- - when result is "needs more input", then at least one more byte is REQUIRED\r
- to complete decoding; all input data MUST be consumed by decoder, so\r
- client could swap the input buffer\r
- - when result is "needs more output" decoder MUST ensure that it doesn't\r
- hold more than 7 bits in bit reader; this saves client from swapping input\r
- buffer ahead of time\r
- - when result is "success" decoder MUST return all unused data back to input\r
- buffer; this is possible because the invariant is held on enter */\r
-BrotliDecoderResult BrotliDecoderDecompressStream(\r
- BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in,\r
- size_t* available_out, uint8_t** next_out, size_t* total_out) {\r
- BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;\r
- BrotliBitReader* br = &s->br;\r
- /* Ensure that |total_out| is set, even if no data will ever be pushed out. */\r
- if (total_out) {\r
- *total_out = s->partial_pos_out;\r
- }\r
- /* Do not try to process further in a case of unrecoverable error. */\r
- if ((int)s->error_code < 0) {\r
- return BROTLI_DECODER_RESULT_ERROR;\r
- }\r
- if (*available_out && (!next_out || !*next_out)) {\r
- return SaveErrorCode(\r
- s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS));\r
- }\r
- if (!*available_out) next_out = 0;\r
- if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */\r
- br->avail_in = *available_in;\r
- br->next_in = *next_in;\r
- } else {\r
- /* At least one byte of input is required. More than one byte of input may\r
- be required to complete the transaction -> reading more data must be\r
- done in a loop -> do it in a main loop. */\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- br->next_in = &s->buffer.u8[0];\r
- }\r
- /* State machine */\r
- for (;;) {\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- /* Error, needs more input/output. */\r
- if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {\r
- if (s->ringbuffer != 0) { /* Pro-actively push output. */\r
- BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s,\r
- available_out, next_out, total_out, BROTLI_TRUE);\r
- /* WriteRingBuffer checks s->meta_block_remaining_len validity. */\r
- if ((int)intermediate_result < 0) {\r
- result = intermediate_result;\r
- break;\r
- }\r
- }\r
- if (s->buffer_length != 0) { /* Used with internal buffer. */\r
- if (br->avail_in == 0) {\r
- /* Successfully finished read transaction.\r
- Accumulator contains less than 8 bits, because internal buffer\r
- is expanded byte-by-byte until it is enough to complete read. */\r
- s->buffer_length = 0;\r
- /* Switch to input stream and restart. */\r
- result = BROTLI_DECODER_SUCCESS;\r
- br->avail_in = *available_in;\r
- br->next_in = *next_in;\r
- continue;\r
- } else if (*available_in != 0) {\r
- /* Not enough data in buffer, but can take one more byte from\r
- input stream. */\r
- result = BROTLI_DECODER_SUCCESS;\r
- s->buffer.u8[s->buffer_length] = **next_in;\r
- s->buffer_length++;\r
- br->avail_in = s->buffer_length;\r
- (*next_in)++;\r
- (*available_in)--;\r
- /* Retry with more data in buffer. */\r
- continue;\r
- }\r
- /* Can't finish reading and no more input. */\r
- break;\r
- } else { /* Input stream doesn't contain enough input. */\r
- /* Copy tail to internal buffer and return. */\r
- *next_in = br->next_in;\r
- *available_in = br->avail_in;\r
- while (*available_in) {\r
- s->buffer.u8[s->buffer_length] = **next_in;\r
- s->buffer_length++;\r
- (*next_in)++;\r
- (*available_in)--;\r
- }\r
- break;\r
- }\r
- /* Unreachable. */\r
- }\r
-\r
- /* Fail or needs more output. */\r
-\r
- if (s->buffer_length != 0) {\r
- /* Just consumed the buffered input and produced some output. Otherwise\r
- it would result in "needs more input". Reset internal buffer. */\r
- s->buffer_length = 0;\r
- } else {\r
- /* Using input stream in last iteration. When decoder switches to input\r
- stream it has less than 8 bits in accumulator, so it is safe to\r
- return unused accumulator bits there. */\r
- BrotliBitReaderUnload(br);\r
- *available_in = br->avail_in;\r
- *next_in = br->next_in;\r
- }\r
- break;\r
- }\r
- switch (s->state) {\r
- case BROTLI_STATE_UNINITED:\r
- /* Prepare to the first read. */\r
- if (!BrotliWarmupBitReader(br)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- break;\r
- }\r
- /* Decode window size. */\r
- result = DecodeWindowBits(s, br); /* Reads 1..8 bits. */\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- if (s->large_window) {\r
- s->state = BROTLI_STATE_LARGE_WINDOW_BITS;\r
- break;\r
- }\r
- s->state = BROTLI_STATE_INITIALIZE;\r
- break;\r
-\r
- case BROTLI_STATE_LARGE_WINDOW_BITS:\r
- if (!BrotliSafeReadBits(br, 6, &s->window_bits)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- break;\r
- }\r
- if (s->window_bits < BROTLI_LARGE_MIN_WBITS ||\r
- s->window_bits > BROTLI_LARGE_MAX_WBITS) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);\r
- break;\r
- }\r
- s->state = BROTLI_STATE_INITIALIZE;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_INITIALIZE:\r
- BROTLI_LOG_UINT(s->window_bits);\r
- /* Maximum distance, see section 9.1. of the spec. */\r
- s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP;\r
-\r
- /* Allocate memory for both block_type_trees and block_len_trees. */\r
- s->block_type_trees = (HuffmanCode*)BROTLI_DECODER_ALLOC(s,\r
- sizeof(HuffmanCode) * 3 *\r
- (BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26));\r
- if (s->block_type_trees == 0) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES);\r
- break;\r
- }\r
- s->block_len_trees =\r
- s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258;\r
-\r
- s->state = BROTLI_STATE_METABLOCK_BEGIN;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_BEGIN:\r
- BrotliDecoderStateMetablockBegin(s);\r
- BROTLI_LOG_UINT(s->pos);\r
- s->state = BROTLI_STATE_METABLOCK_HEADER;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER:\r
- result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- BROTLI_LOG_UINT(s->is_last_metablock);\r
- BROTLI_LOG_UINT(s->meta_block_remaining_len);\r
- BROTLI_LOG_UINT(s->is_metadata);\r
- BROTLI_LOG_UINT(s->is_uncompressed);\r
- if (s->is_metadata || s->is_uncompressed) {\r
- if (!BrotliJumpToByteBoundary(br)) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1);\r
- break;\r
- }\r
- }\r
- if (s->is_metadata) {\r
- s->state = BROTLI_STATE_METADATA;\r
- break;\r
- }\r
- if (s->meta_block_remaining_len == 0) {\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- break;\r
- }\r
- BrotliCalculateRingBufferSize(s);\r
- if (s->is_uncompressed) {\r
- s->state = BROTLI_STATE_UNCOMPRESSED;\r
- break;\r
- }\r
- s->loop_counter = 0;\r
- s->state = BROTLI_STATE_HUFFMAN_CODE_0;\r
- break;\r
-\r
- case BROTLI_STATE_UNCOMPRESSED: {\r
- result = CopyUncompressedBlockToOutput(\r
- available_out, next_out, total_out, s);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- break;\r
- }\r
-\r
- case BROTLI_STATE_METADATA:\r
- for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {\r
- uint32_t bits;\r
- /* Read one byte and ignore it. */\r
- if (!BrotliSafeReadBits(br, 8, &bits)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- break;\r
- }\r
- }\r
- if (result == BROTLI_DECODER_SUCCESS) {\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- }\r
- break;\r
-\r
- case BROTLI_STATE_HUFFMAN_CODE_0:\r
- if (s->loop_counter >= 3) {\r
- s->state = BROTLI_STATE_METABLOCK_HEADER_2;\r
- break;\r
- }\r
- /* Reads 1..11 bits. */\r
- result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- s->num_block_types[s->loop_counter]++;\r
- BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]);\r
- if (s->num_block_types[s->loop_counter] < 2) {\r
- s->loop_counter++;\r
- break;\r
- }\r
- s->state = BROTLI_STATE_HUFFMAN_CODE_1;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_CODE_1: {\r
- uint32_t alphabet_size = s->num_block_types[s->loop_counter] + 2;\r
- int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258;\r
- result = ReadHuffmanCode(alphabet_size, alphabet_size,\r
- &s->block_type_trees[tree_offset], NULL, s);\r
- if (result != BROTLI_DECODER_SUCCESS) break;\r
- s->state = BROTLI_STATE_HUFFMAN_CODE_2;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_CODE_2: {\r
- uint32_t alphabet_size = BROTLI_NUM_BLOCK_LEN_SYMBOLS;\r
- int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;\r
- result = ReadHuffmanCode(alphabet_size, alphabet_size,\r
- &s->block_len_trees[tree_offset], NULL, s);\r
- if (result != BROTLI_DECODER_SUCCESS) break;\r
- s->state = BROTLI_STATE_HUFFMAN_CODE_3;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_HUFFMAN_CODE_3: {\r
- int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;\r
- if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter],\r
- &s->block_len_trees[tree_offset], br)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- break;\r
- }\r
- BROTLI_LOG_UINT(s->block_length[s->loop_counter]);\r
- s->loop_counter++;\r
- s->state = BROTLI_STATE_HUFFMAN_CODE_0;\r
- break;\r
- }\r
-\r
- case BROTLI_STATE_METABLOCK_HEADER_2: {\r
- uint32_t bits;\r
- if (!BrotliSafeReadBits(br, 6, &bits)) {\r
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
- break;\r
- }\r
- s->distance_postfix_bits = bits & BitMask(2);\r
- bits >>= 2;\r
- s->num_direct_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES +\r
- (bits << s->distance_postfix_bits);\r
- BROTLI_LOG_UINT(s->num_direct_distance_codes);\r
- BROTLI_LOG_UINT(s->distance_postfix_bits);\r
- s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits);\r
- s->context_modes =\r
- (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)s->num_block_types[0]);\r
- if (s->context_modes == 0) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES);\r
- break;\r
- }\r
- s->loop_counter = 0;\r
- s->state = BROTLI_STATE_CONTEXT_MODES;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MODES:\r
- result = ReadContextModes(s);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- s->state = BROTLI_STATE_CONTEXT_MAP_1;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MAP_1:\r
- result = DecodeContextMap(\r
- s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS,\r
- &s->num_literal_htrees, &s->context_map, s);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- DetectTrivialLiteralBlockTypes(s);\r
- s->state = BROTLI_STATE_CONTEXT_MAP_2;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_CONTEXT_MAP_2: {\r
- uint32_t num_direct_codes =\r
- s->num_direct_distance_codes - BROTLI_NUM_DISTANCE_SHORT_CODES;\r
- uint32_t num_distance_codes = BROTLI_DISTANCE_ALPHABET_SIZE(\r
- s->distance_postfix_bits, num_direct_codes,\r
- (s->large_window ? BROTLI_LARGE_MAX_DISTANCE_BITS :\r
- BROTLI_MAX_DISTANCE_BITS));\r
- uint32_t max_distance_symbol = (s->large_window ?\r
- BrotliMaxDistanceSymbol(\r
- num_direct_codes, s->distance_postfix_bits) :\r
- num_distance_codes);\r
- BROTLI_BOOL allocation_success = BROTLI_TRUE;\r
- result = DecodeContextMap(\r
- s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS,\r
- &s->num_dist_htrees, &s->dist_context_map, s);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- allocation_success &= BrotliDecoderHuffmanTreeGroupInit(\r
- s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS,\r
- BROTLI_NUM_LITERAL_SYMBOLS, s->num_literal_htrees);\r
- allocation_success &= BrotliDecoderHuffmanTreeGroupInit(\r
- s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS,\r
- BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]);\r
- allocation_success &= BrotliDecoderHuffmanTreeGroupInit(\r
- s, &s->distance_hgroup, num_distance_codes,\r
- max_distance_symbol, s->num_dist_htrees);\r
- if (!allocation_success) {\r
- return SaveErrorCode(s,\r
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS));\r
- }\r
- s->loop_counter = 0;\r
- s->state = BROTLI_STATE_TREE_GROUP;\r
- }\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_TREE_GROUP: {\r
- HuffmanTreeGroup* hgroup = NULL;\r
- switch (s->loop_counter) {\r
- case 0: hgroup = &s->literal_hgroup; break;\r
- case 1: hgroup = &s->insert_copy_hgroup; break;\r
- case 2: hgroup = &s->distance_hgroup; break;\r
- default: return SaveErrorCode(s, BROTLI_FAILURE(\r
- BROTLI_DECODER_ERROR_UNREACHABLE));\r
- }\r
- result = HuffmanTreeGroupDecode(hgroup, s);\r
- if (result != BROTLI_DECODER_SUCCESS) break;\r
- s->loop_counter++;\r
- if (s->loop_counter >= 3) {\r
- PrepareLiteralDecoding(s);\r
- s->dist_context_map_slice = s->dist_context_map;\r
- s->htree_command = s->insert_copy_hgroup.htrees[0];\r
- if (!BrotliEnsureRingBuffer(s)) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2);\r
- break;\r
- }\r
- s->state = BROTLI_STATE_COMMAND_BEGIN;\r
- }\r
- break;\r
- }\r
-\r
- case BROTLI_STATE_COMMAND_BEGIN:\r
- /* Fall through. */\r
- case BROTLI_STATE_COMMAND_INNER:\r
- /* Fall through. */\r
- case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS:\r
- /* Fall through. */\r
- case BROTLI_STATE_COMMAND_POST_WRAP_COPY:\r
- result = ProcessCommands(s);\r
- if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {\r
- result = SafeProcessCommands(s);\r
- }\r
- break;\r
-\r
- case BROTLI_STATE_COMMAND_INNER_WRITE:\r
- /* Fall through. */\r
- case BROTLI_STATE_COMMAND_POST_WRITE_1:\r
- /* Fall through. */\r
- case BROTLI_STATE_COMMAND_POST_WRITE_2:\r
- result = WriteRingBuffer(\r
- s, available_out, next_out, total_out, BROTLI_FALSE);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- WrapRingBuffer(s);\r
- if (s->ringbuffer_size == 1 << s->window_bits) {\r
- s->max_distance = s->max_backward_distance;\r
- }\r
- if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {\r
- if (s->meta_block_remaining_len == 0) {\r
- /* Next metablock, if any. */\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- } else {\r
- s->state = BROTLI_STATE_COMMAND_BEGIN;\r
- }\r
- break;\r
- } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) {\r
- s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;\r
- } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */\r
- if (s->loop_counter == 0) {\r
- if (s->meta_block_remaining_len == 0) {\r
- s->state = BROTLI_STATE_METABLOCK_DONE;\r
- } else {\r
- s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;\r
- }\r
- break;\r
- }\r
- s->state = BROTLI_STATE_COMMAND_INNER;\r
- }\r
- break;\r
-\r
- case BROTLI_STATE_METABLOCK_DONE:\r
- if (s->meta_block_remaining_len < 0) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2);\r
- break;\r
- }\r
- BrotliDecoderStateCleanupAfterMetablock(s);\r
- if (!s->is_last_metablock) {\r
- s->state = BROTLI_STATE_METABLOCK_BEGIN;\r
- break;\r
- }\r
- if (!BrotliJumpToByteBoundary(br)) {\r
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2);\r
- break;\r
- }\r
- if (s->buffer_length == 0) {\r
- BrotliBitReaderUnload(br);\r
- *available_in = br->avail_in;\r
- *next_in = br->next_in;\r
- }\r
- s->state = BROTLI_STATE_DONE;\r
- /* Fall through. */\r
-\r
- case BROTLI_STATE_DONE:\r
- if (s->ringbuffer != 0) {\r
- result = WriteRingBuffer(\r
- s, available_out, next_out, total_out, BROTLI_TRUE);\r
- if (result != BROTLI_DECODER_SUCCESS) {\r
- break;\r
- }\r
- }\r
- return SaveErrorCode(s, result);\r
- }\r
- }\r
- return SaveErrorCode(s, result);\r
-}\r
-\r
-BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) {\r
- /* After unrecoverable error remaining output is considered nonsensical. */\r
- if ((int)s->error_code < 0) {\r
- return BROTLI_FALSE;\r
- }\r
- return TO_BROTLI_BOOL(\r
- s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0);\r
-}\r
-\r
-const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) {\r
- uint8_t* result = 0;\r
- size_t available_out = *size ? *size : 1u << 24;\r
- size_t requested_out = available_out;\r
- BrotliDecoderErrorCode status;\r
- if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) {\r
- *size = 0;\r
- return 0;\r
- }\r
- WrapRingBuffer(s);\r
- status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE);\r
- /* Either WriteRingBuffer returns those "success" codes... */\r
- if (status == BROTLI_DECODER_SUCCESS ||\r
- status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) {\r
- *size = requested_out - available_out;\r
- } else {\r
- /* ... or stream is broken. Normally this should be caught by\r
- BrotliDecoderDecompressStream, this is just a safeguard. */\r
- if ((int)status < 0) SaveErrorCode(s, status);\r
- *size = 0;\r
- result = 0;\r
- }\r
- return result;\r
-}\r
-\r
-BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) {\r
- return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED ||\r
- BrotliGetAvailableBits(&s->br) != 0);\r
-}\r
-\r
-BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) {\r
- return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) &&\r
- !BrotliDecoderHasMoreOutput(s);\r
-}\r
-\r
-BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) {\r
- return (BrotliDecoderErrorCode)s->error_code;\r
-}\r
-\r
-const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) {\r
- switch (c) {\r
-#define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \\r
- case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;\r
-#define BROTLI_NOTHING_\r
- BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_)\r
-#undef BROTLI_ERROR_CODE_CASE_\r
-#undef BROTLI_NOTHING_\r
- default: return "INVALID";\r
- }\r
-}\r
-\r
-uint32_t BrotliDecoderVersion() {\r
- return BROTLI_VERSION;\r
-}\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-} /* extern "C" */\r
-#endif\r
projects / mirror_edk2.git / blobdiff