diff options
Diffstat (limited to 'modules/brotli/dec/decode.c')
| -rw-r--r-- | modules/brotli/dec/decode.c | 1802 |
1 files changed, 1023 insertions, 779 deletions
diff --git a/modules/brotli/dec/decode.c b/modules/brotli/dec/decode.c index d184f24cb..08bd76ca1 100644 --- a/modules/brotli/dec/decode.c +++ b/modules/brotli/dec/decode.c @@ -4,23 +4,25 @@ See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ -#include "./decode.h" - -#ifdef __ARM_NEON__ -#include <arm_neon.h> -#endif +#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/transform.h" +#include "../common/version.h" #include "./bit_reader.h" -#include "./context.h" -#include "./dictionary.h" #include "./huffman.h" -#include "./port.h" #include "./prefix.h" #include "./state.h" -#include "./transform.h" + +#if defined(BROTLI_TARGET_NEON) +#include <arm_neon.h> +#endif #if defined(__cplusplus) || defined(c_plusplus) extern "C" { @@ -34,19 +36,15 @@ extern "C" { BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \ (unsigned long)(idx), (unsigned long)array_name[idx])) -static const uint32_t kDefaultCodeLength = 8; -static const uint32_t kCodeLengthRepeatCode = 16; -static const uint32_t kNumLiteralCodes = 256; -static const uint32_t kNumInsertAndCopyCodes = 704; -static const uint32_t kNumBlockLengthCodes = 26; -static const int kLiteralContextBits = 6; -static const int kDistanceContextBits = 2; - #define HUFFMAN_TABLE_BITS 8U -#define HUFFMAN_TABLE_MASK 0xff +#define HUFFMAN_TABLE_MASK 0xFF + +/* We need the slack region for the following reasons: + - doing up to two 16-byte copies for fast backward copying + - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */ +static const uint32_t kRingBufferWriteAheadSlack = 42; -#define CODE_LENGTH_CODES 18 -static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = { +static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = { 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, }; @@ -59,70 +57,117 @@ static const uint8_t kCodeLengthPrefixValue[16] = { 0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5, }; -#define NUM_DISTANCE_SHORT_CODES 16 +BROTLI_BOOL BrotliDecoderSetParameter( + BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) { + if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE; + switch (p) { + case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION: + state->canny_ringbuffer_allocation = !!value ? 0 : 1; + return BROTLI_TRUE; -BrotliState* BrotliCreateState( + case BROTLI_DECODER_PARAM_LARGE_WINDOW: + state->large_window = TO_BROTLI_BOOL(!!value); + return BROTLI_TRUE; + + default: return BROTLI_FALSE; + } +} + +BrotliDecoderState* BrotliDecoderCreateInstance( brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { - BrotliState* state = 0; + BrotliDecoderState* state = 0; if (!alloc_func && !free_func) { - state = (BrotliState*)malloc(sizeof(BrotliState)); + state = (BrotliDecoderState*)malloc(sizeof(BrotliDecoderState)); } else if (alloc_func && free_func) { - state = (BrotliState*)alloc_func(opaque, sizeof(BrotliState)); + state = (BrotliDecoderState*)alloc_func(opaque, sizeof(BrotliDecoderState)); } if (state == 0) { BROTLI_DUMP(); return 0; } - BrotliStateInitWithCustomAllocators(state, alloc_func, free_func, opaque); - state->error_code = BROTLI_NO_ERROR; + if (!BrotliDecoderStateInit(state, alloc_func, free_func, opaque)) { + BROTLI_DUMP(); + if (!alloc_func && !free_func) { + free(state); + } else if (alloc_func && free_func) { + free_func(opaque, state); + } + return 0; + } return state; } -/* Deinitializes and frees BrotliState instance. */ -void BrotliDestroyState(BrotliState* state) { +/* Deinitializes and frees BrotliDecoderState instance. */ +void BrotliDecoderDestroyInstance(BrotliDecoderState* state) { if (!state) { return; } else { brotli_free_func free_func = state->free_func; void* opaque = state->memory_manager_opaque; - BrotliStateCleanup(state); + BrotliDecoderStateCleanup(state); free_func(opaque, state); } } -/* Saves error code and converts it to BrotliResult */ -static BROTLI_NOINLINE BrotliResult SaveErrorCode( - BrotliState* s, BrotliErrorCode e) { +/* Saves error code and converts it to BrotliDecoderResult. */ +static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode( + BrotliDecoderState* s, BrotliDecoderErrorCode e) { s->error_code = (int)e; switch (e) { - case BROTLI_SUCCESS: return BROTLI_RESULT_SUCCESS; - case BROTLI_NEEDS_MORE_INPUT: return BROTLI_RESULT_NEEDS_MORE_INPUT; - case BROTLI_NEEDS_MORE_OUTPUT: return BROTLI_RESULT_NEEDS_MORE_OUTPUT; - default: return BROTLI_RESULT_ERROR; + case BROTLI_DECODER_SUCCESS: + return BROTLI_DECODER_RESULT_SUCCESS; + + case BROTLI_DECODER_NEEDS_MORE_INPUT: + return BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT; + + case BROTLI_DECODER_NEEDS_MORE_OUTPUT: + return BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT; + + default: + return BROTLI_DECODER_RESULT_ERROR; } } -/* Decodes a number in the range [9..24], by reading 1 - 7 bits. - Precondition: bit-reader accumulator has at least 7 bits. */ -static uint32_t DecodeWindowBits(BrotliBitReader* br) { +/* 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) { uint32_t n; + BROTLI_BOOL large_window = s->large_window; + s->large_window = BROTLI_FALSE; BrotliTakeBits(br, 1, &n); if (n == 0) { - return 16; + s->window_bits = 16; + return BROTLI_DECODER_SUCCESS; } BrotliTakeBits(br, 3, &n); if (n != 0) { - return 17 + n; + s->window_bits = 17 + n; + return BROTLI_DECODER_SUCCESS; } BrotliTakeBits(br, 3, &n); + if (n == 1) { + if (large_window) { + BrotliTakeBits(br, 1, &n); + if (n == 1) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + } + s->large_window = BROTLI_TRUE; + return BROTLI_DECODER_SUCCESS; + } else { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + } + } if (n != 0) { - return 8 + n; + s->window_bits = 8 + n; + return BROTLI_DECODER_SUCCESS; } - return 17; + s->window_bits = 17; + return BROTLI_DECODER_SUCCESS; } static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) { -#if defined(__ARM_NEON__) +#if defined(BROTLI_TARGET_NEON) vst1q_u8(dst, vld1q_u8(src)); #else uint32_t buffer[4]; @@ -132,60 +177,61 @@ 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 BrotliErrorCode DecodeVarLenUint8(BrotliState* s, - BrotliBitReader* br, uint32_t* value) { +static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8( + BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) { uint32_t bits; switch (s->substate_decode_uint8) { case BROTLI_STATE_DECODE_UINT8_NONE: - if (PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) { - return BROTLI_NEEDS_MORE_INPUT; + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits == 0) { *value = 0; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_DECODE_UINT8_SHORT: - if (PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) { + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) { s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits == 0) { *value = 1; s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* Use output value as a temporary storage. It MUST be persisted. */ *value = bits; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_DECODE_UINT8_LONG: - if (PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) { + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) { s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } *value = (1U << *value) + bits; s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; default: - return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE); + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } /* Decodes a metablock length and flags by reading 2 - 31 bits. */ -static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( - BrotliState* s, BrotliBitReader* br) { +static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( + BrotliDecoderState* s, BrotliBitReader* br) { uint32_t bits; int i; for (;;) { switch (s->substate_metablock_header) { case BROTLI_STATE_METABLOCK_HEADER_NONE: if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->is_last_metablock = (uint8_t)bits; + s->is_last_metablock = bits ? 1 : 0; s->meta_block_remaining_len = 0; s->is_uncompressed = 0; s->is_metadata = 0; @@ -194,22 +240,22 @@ static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( break; } s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_EMPTY: if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits) { s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_NIBBLES: if (!BrotliSafeReadBits(br, 2, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } s->size_nibbles = (uint8_t)(bits + 4); s->loop_counter = 0; @@ -219,75 +265,77 @@ static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( break; } s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_SIZE: i = s->loop_counter; - for (; i < s->size_nibbles; ++i) { + for (; i < (int)s->size_nibbles; ++i) { if (!BrotliSafeReadBits(br, 4, &bits)) { s->loop_counter = i; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_EXUBERANT_NIBBLE); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE); } s->meta_block_remaining_len |= (int)(bits << (i * 4)); } s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED: if (!s->is_last_metablock) { if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->is_uncompressed = (uint8_t)bits; + s->is_uncompressed = bits ? 1 : 0; } ++s->meta_block_remaining_len; s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; case BROTLI_STATE_METABLOCK_HEADER_RESERVED: if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits != 0) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_RESERVED); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED); } s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_BYTES: if (!BrotliSafeReadBits(br, 2, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits == 0) { s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } s->size_nibbles = (uint8_t)bits; s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA; - /* No break, transit to the next state. */ + /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_METADATA: i = s->loop_counter; - for (; i < s->size_nibbles; ++i) { + for (; i < (int)s->size_nibbles; ++i) { if (!BrotliSafeReadBits(br, 8, &bits)) { s->loop_counter = i; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_EXUBERANT_META_NIBBLE); + return BROTLI_FAILURE( + BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE); } s->meta_block_remaining_len |= (int)(bits << (i * 8)); } ++s->meta_block_remaining_len; s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; default: - return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE); + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } } @@ -299,15 +347,17 @@ static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, const HuffmanCode* table, BrotliBitReader* br) { - table += bits & HUFFMAN_TABLE_MASK; - if (table->bits > HUFFMAN_TABLE_BITS) { - uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS; + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + BROTLI_HC_ADJUST_TABLE_INDEX(table, bits & HUFFMAN_TABLE_MASK); + if (BROTLI_HC_FAST_LOAD_BITS(table) > HUFFMAN_TABLE_BITS) { + uint32_t nbits = BROTLI_HC_FAST_LOAD_BITS(table) - HUFFMAN_TABLE_BITS; BrotliDropBits(br, HUFFMAN_TABLE_BITS); - table += table->value; - table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits); + BROTLI_HC_ADJUST_TABLE_INDEX(table, + BROTLI_HC_FAST_LOAD_VALUE(table) + + ((bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits))); } - BrotliDropBits(br, table->bits); - return table->value; + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table)); + return BROTLI_HC_FAST_LOAD_VALUE(table); } /* Reads and decodes the next Huffman code from bit-stream. @@ -319,53 +369,52 @@ static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table, /* Same as DecodeSymbol, but it is known that there is less than 15 bits of input are currently available. */ -static BROTLI_NOINLINE int SafeDecodeSymbol(const HuffmanCode* table, - BrotliBitReader* br, - uint32_t* result) { +static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol( + const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { uint32_t val; uint32_t available_bits = BrotliGetAvailableBits(br); + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); if (available_bits == 0) { - if (table->bits == 0) { - *result = table->value; - return 1; + if (BROTLI_HC_FAST_LOAD_BITS(table) == 0) { + *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; } - return 0; /* No valid bits at all. */ + return BROTLI_FALSE; /* No valid bits at all. */ } val = (uint32_t)BrotliGetBitsUnmasked(br); - table += val & HUFFMAN_TABLE_MASK; - if (table->bits <= HUFFMAN_TABLE_BITS) { - if (table->bits <= available_bits) { - BrotliDropBits(br, table->bits); - *result = table->value; - return 1; + BROTLI_HC_ADJUST_TABLE_INDEX(table, val & HUFFMAN_TABLE_MASK); + if (BROTLI_HC_FAST_LOAD_BITS(table) <= HUFFMAN_TABLE_BITS) { + if (BROTLI_HC_FAST_LOAD_BITS(table) <= available_bits) { + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table)); + *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; } else { - return 0; /* Not enough bits for the first level. */ + return BROTLI_FALSE; /* Not enough bits for the first level. */ } } if (available_bits <= HUFFMAN_TABLE_BITS) { - return 0; /* Not enough bits to move to the second level. */ + return BROTLI_FALSE; /* Not enough bits to move to the second level. */ } /* Speculatively drop HUFFMAN_TABLE_BITS. */ - val = (val & BitMask(table->bits)) >> HUFFMAN_TABLE_BITS; + val = (val & BitMask(BROTLI_HC_FAST_LOAD_BITS(table))) >> HUFFMAN_TABLE_BITS; available_bits -= HUFFMAN_TABLE_BITS; - table += table->value + val; - if (available_bits < table->bits) { - return 0; /* Not enough bits for the second level. */ + BROTLI_HC_ADJUST_TABLE_INDEX(table, BROTLI_HC_FAST_LOAD_VALUE(table) + val); + if (available_bits < BROTLI_HC_FAST_LOAD_BITS(table)) { + return BROTLI_FALSE; /* Not enough bits for the second level. */ } - BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits); - *result = table->value; - return 1; + BrotliDropBits(br, HUFFMAN_TABLE_BITS + BROTLI_HC_FAST_LOAD_BITS(table)); + *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; } -static BROTLI_INLINE int SafeReadSymbol(const HuffmanCode* table, - BrotliBitReader* br, - uint32_t* result) { +static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol( + const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { uint32_t val; - if (PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) { + if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) { *result = DecodeSymbol(val, table, br); - return 1; + return BROTLI_TRUE; } return SafeDecodeSymbol(table, br, result); } @@ -379,9 +428,10 @@ static BROTLI_INLINE void PreloadSymbol(int safe, if (safe) { return; } - table += BrotliGetBits(br, HUFFMAN_TABLE_BITS); - *bits = table->bits; - *value = table->value; + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + BROTLI_HC_ADJUST_TABLE_INDEX(table, BrotliGetBits(br, HUFFMAN_TABLE_BITS)); + *bits = BROTLI_HC_FAST_LOAD_BITS(table); + *value = BROTLI_HC_FAST_LOAD_VALUE(table); } /* Decodes the next Huffman code using data prepared by PreloadSymbol. @@ -391,14 +441,15 @@ static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table, uint32_t* bits, uint32_t* value) { uint32_t result = *value; - if (PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) { + if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) { uint32_t val = BrotliGet16BitsUnmasked(br); const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value; uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS)); + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(ext); BrotliDropBits(br, HUFFMAN_TABLE_BITS); - ext += (val >> HUFFMAN_TABLE_BITS) & mask; - BrotliDropBits(br, ext->bits); - result = ext->value; + BROTLI_HC_ADJUST_TABLE_INDEX(ext, (val >> HUFFMAN_TABLE_BITS) & mask); + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(ext)); + result = BROTLI_HC_FAST_LOAD_VALUE(ext); } else { BrotliDropBits(br, *bits); } @@ -416,25 +467,25 @@ static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { } /* Reads (s->symbol + 1) symbols. - Totally 1..4 symbols are read, 1..10 bits each. - The list of symbols MUST NOT contain duplicates. - */ -static BrotliErrorCode ReadSimpleHuffmanSymbols(uint32_t alphabet_size, - BrotliState* s) { - /* max_bits == 1..10; symbol == 0..3; 1..40 bits will be read. */ + 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, uint32_t max_symbol, BrotliDecoderState* s) { + /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */ BrotliBitReader* br = &s->br; uint32_t max_bits = Log2Floor(alphabet_size - 1); uint32_t i = s->sub_loop_counter; uint32_t num_symbols = s->symbol; while (i <= num_symbols) { uint32_t v; - if (PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) { + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) { s->sub_loop_counter = i; s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - if (v >= alphabet_size) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET); + if (v >= max_symbol) { + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET); } s->symbols_lists_array[i] = (uint16_t)v; BROTLI_LOG_UINT(s->symbols_lists_array[i]); @@ -445,55 +496,58 @@ static BrotliErrorCode ReadSimpleHuffmanSymbols(uint32_t alphabet_size, uint32_t k = i + 1; for (; k <= num_symbols; ++k) { if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME); } } } - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* Process single decoded symbol code length: A) reset the repeat variable B) remember code length (if it is not 0) - C) extend corredponding index-chain - D) reduce the huffman space - E) update the histogram - */ + 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) { *repeat = 0; - if (code_len != 0) { /* code_len == 1..15 */ + if (code_len != 0) { /* code_len == 1..15 */ symbol_lists[next_symbol[code_len]] = (uint16_t)(*symbol); next_symbol[code_len] = (int)(*symbol); *prev_code_len = code_len; *space -= 32768U >> code_len; code_length_histo[code_len]++; - BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n", *symbol, code_len)); + BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n", + (int)*symbol, (int)code_len)); } (*symbol)++; } /* Process repeated symbol code length. A) Check if it is the extension of previous repeat sequence; if the decoded - value is not kCodeLengthRepeatCode, then it is a new symbol-skip + 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 alphapet) + C) Check if operation is feasible (fits alphabet) D) For each symbol do the same operations as in ProcessSingleCodeLength - PRECONDITION: code_len == kCodeLengthRepeatCode or kCodeLengthRepeatCode + 1 - */ + 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) { uint32_t old_repeat; - uint32_t new_len = 0; - if (code_len == kCodeLengthRepeatCode) { + uint32_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ + uint32_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ + if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { new_len = *prev_code_len; + extra_bits = 2; } if (*repeat_code_len != new_len) { *repeat = 0; @@ -502,7 +556,7 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len, old_repeat = *repeat; if (*repeat > 0) { *repeat -= 2; - *repeat <<= code_len - 14U; + *repeat <<= extra_bits; } *repeat += repeat_delta + 3U; repeat_delta = *repeat - old_repeat; @@ -513,7 +567,7 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len, return; } BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n", - *symbol, *symbol + repeat_delta - 1, *repeat_code_len)); + (int)*symbol, (int)(*symbol + repeat_delta - 1), (int)*repeat_code_len)); if (*repeat_code_len != 0) { unsigned last = *symbol + repeat_delta; int next = next_symbol[*repeat_code_len]; @@ -531,8 +585,8 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len, } /* Reads and decodes symbol codelengths. */ -static BrotliErrorCode ReadSymbolCodeLengths( - uint32_t alphabet_size, BrotliState* s) { +static BrotliDecoderErrorCode ReadSymbolCodeLengths( + uint32_t alphabet_size, BrotliDecoderState* s) { BrotliBitReader* br = &s->br; uint32_t symbol = s->symbol; uint32_t repeat = s->repeat; @@ -543,91 +597,101 @@ static BrotliErrorCode ReadSymbolCodeLengths( uint16_t* code_length_histo = s->code_length_histo; int* next_symbol = s->next_symbol; if (!BrotliWarmupBitReader(br)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } while (symbol < alphabet_size && space > 0) { const HuffmanCode* p = s->table; uint32_t code_len; + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p); if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) { s->symbol = symbol; s->repeat = repeat; s->prev_code_len = prev_code_len; s->repeat_code_len = repeat_code_len; s->space = space; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } BrotliFillBitWindow16(br); - p += BrotliGetBitsUnmasked(br) & - BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH); - BrotliDropBits(br, p->bits); /* Use 1..5 bits */ - code_len = p->value; /* code_len == 0..17 */ - if (code_len < kCodeLengthRepeatCode) { + BROTLI_HC_ADJUST_TABLE_INDEX(p, BrotliGetBitsUnmasked(br) & + BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH)); + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); /* Use 1..5 bits. */ + code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */ + if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { ProcessSingleCodeLength(code_len, &symbol, &repeat, &space, &prev_code_len, symbol_lists, code_length_histo, next_symbol); - } else { /* code_len == 16..17, extra_bits == 2..3 */ + } else { /* code_len == 16..17, extra_bits == 2..3 */ + uint32_t extra_bits = + (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3; uint32_t repeat_delta = - (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(code_len - 14U); - BrotliDropBits(br, code_len - 14U); + (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(extra_bits); + BrotliDropBits(br, extra_bits); ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, &symbol, &repeat, &space, &prev_code_len, &repeat_code_len, symbol_lists, code_length_histo, next_symbol); } } s->space = space; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } -static BrotliErrorCode SafeReadSymbolCodeLengths( - uint32_t alphabet_size, BrotliState* s) { +static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( + uint32_t alphabet_size, BrotliDecoderState* s) { BrotliBitReader* br = &s->br; + BROTLI_BOOL get_byte = BROTLI_FALSE; while (s->symbol < alphabet_size && s->space > 0) { const HuffmanCode* p = s->table; uint32_t code_len; + uint32_t available_bits; uint32_t bits = 0; - uint32_t available_bits = BrotliGetAvailableBits(br); + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p); + if (get_byte && !BrotliPullByte(br)) return BROTLI_DECODER_NEEDS_MORE_INPUT; + get_byte = BROTLI_FALSE; + available_bits = BrotliGetAvailableBits(br); if (available_bits != 0) { bits = (uint32_t)BrotliGetBitsUnmasked(br); } - p += bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH); - if (p->bits > available_bits) goto pullMoreInput; - code_len = p->value; /* code_len == 0..17 */ - if (code_len < kCodeLengthRepeatCode) { - BrotliDropBits(br, p->bits); + BROTLI_HC_ADJUST_TABLE_INDEX(p, + bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH)); + if (BROTLI_HC_FAST_LOAD_BITS(p) > available_bits) { + get_byte = BROTLI_TRUE; + continue; + } + code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */ + if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space, &s->prev_code_len, s->symbol_lists, s->code_length_histo, s->next_symbol); - } else { /* code_len == 16..17, extra_bits == 2..3 */ + } else { /* code_len == 16..17, extra_bits == 2..3 */ uint32_t extra_bits = code_len - 14U; - uint32_t repeat_delta = (bits >> p->bits) & BitMask(extra_bits); - if (available_bits < p->bits + extra_bits) goto pullMoreInput; - BrotliDropBits(br, p->bits + extra_bits); + uint32_t repeat_delta = (bits >> BROTLI_HC_FAST_LOAD_BITS(p)) & + BitMask(extra_bits); + if (available_bits < BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits) { + get_byte = BROTLI_TRUE; + continue; + } + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits); ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, &s->symbol, &s->repeat, &s->space, &s->prev_code_len, &s->repeat_code_len, s->symbol_lists, s->code_length_histo, s->next_symbol); } - continue; - -pullMoreInput: - if (!BrotliPullByte(br)) { - return BROTLI_NEEDS_MORE_INPUT; - } } - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* 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 BrotliErrorCode ReadCodeLengthCodeLengths(BrotliState* s) { +static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) { BrotliBitReader* br = &s->br; uint32_t num_codes = s->repeat; unsigned space = s->space; uint32_t i = s->sub_loop_counter; - for (; i < CODE_LENGTH_CODES; ++i) { + for (; i < BROTLI_CODE_LENGTH_CODES; ++i) { const uint8_t code_len_idx = kCodeLengthCodeOrder[i]; uint32_t ix; uint32_t v; - if (PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) { + if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) { uint32_t available_bits = BrotliGetAvailableBits(br); if (available_bits != 0) { ix = BrotliGetBitsUnmasked(br) & 0xF; @@ -639,7 +703,7 @@ static BrotliErrorCode ReadCodeLengthCodeLengths(BrotliState* s) { s->repeat = num_codes; s->space = space; s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } } v = kCodeLengthPrefixValue[ix]; @@ -651,142 +715,149 @@ static BrotliErrorCode ReadCodeLengthCodeLengths(BrotliState* s) { ++num_codes; ++s->code_length_histo[v]; if (space - 1U >= 32U) { - /* space is 0 or wrapped around */ + /* space is 0 or wrapped around. */ break; } } } if (!(num_codes == 1 || space == 0)) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_CL_SPACE); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE); } - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* 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 - 45 bits will be read. + 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 BrotliErrorCode ReadHuffmanCode(uint32_t alphabet_size, - HuffmanCode* table, - uint32_t* opt_table_size, - BrotliState* s) { + Huffman table. In worst case 3520 bits are read. */ +static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size, + uint32_t max_symbol, + HuffmanCode* table, + uint32_t* opt_table_size, + BrotliDecoderState* s) { BrotliBitReader* br = &s->br; /* Unnecessary masking, but might be good for safety. */ - alphabet_size &= 0x3ff; - /* State machine */ - switch (s->substate_huffman) { - case BROTLI_STATE_HUFFMAN_NONE: - if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) { - return BROTLI_NEEDS_MORE_INPUT; - } - BROTLI_LOG_UINT(s->sub_loop_counter); - /* The value is used as follows: - 1 for simple code; - 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ - if (s->sub_loop_counter != 1) { - s->space = 32; - s->repeat = 0; /* num_codes */ - memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) * - (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1)); - memset(&s->code_length_code_lengths[0], 0, - sizeof(s->code_length_code_lengths)); - s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; - goto Complex; - } - /* No break, transit to the next state. */ + alphabet_size &= 0x7FF; + /* State machine. */ + for (;;) { + switch (s->substate_huffman) { + case BROTLI_STATE_HUFFMAN_NONE: + if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BROTLI_LOG_UINT(s->sub_loop_counter); + /* The value is used as follows: + 1 for simple code; + 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ + if (s->sub_loop_counter != 1) { + s->space = 32; + s->repeat = 0; /* num_codes */ + memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) * + (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1)); + memset(&s->code_length_code_lengths[0], 0, + sizeof(s->code_length_code_lengths)); + s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; + continue; + } + /* Fall through. */ - case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE: - /* Read symbols, codes & code lengths directly. */ - if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */ - s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; - return BROTLI_NEEDS_MORE_INPUT; - } - s->sub_loop_counter = 0; - /* No break, transit to the next state. */ - case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { - BrotliErrorCode result = ReadSimpleHuffmanSymbols(alphabet_size, s); - if (result != BROTLI_SUCCESS) { - return result; - } - /* No break, transit to the next state. */ - } - case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: { - uint32_t table_size; - if (s->symbol == 3) { - uint32_t bits; - if (!BrotliSafeReadBits(br, 1, &bits)) { - s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; - return BROTLI_NEEDS_MORE_INPUT; + case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE: + /* Read symbols, codes & code lengths directly. */ + if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */ + s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->symbol += bits; - } - BROTLI_LOG_UINT(s->symbol); - table_size = BrotliBuildSimpleHuffmanTable( - table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol); - if (opt_table_size) { - *opt_table_size = table_size; - } - s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; - return BROTLI_SUCCESS; - } + s->sub_loop_counter = 0; + /* Fall through. */ -Complex: /* Decode Huffman-coded code lengths. */ - case BROTLI_STATE_HUFFMAN_COMPLEX: { - uint32_t i; - BrotliErrorCode result = ReadCodeLengthCodeLengths(s); - if (result != BROTLI_SUCCESS) { - return result; - } - BrotliBuildCodeLengthsHuffmanTable(s->table, - s->code_length_code_lengths, - s->code_length_histo); - memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo)); - for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) { - s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); - s->symbol_lists[(int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1)] = 0xFFFF; + case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { + BrotliDecoderErrorCode result = + ReadSimpleHuffmanSymbols(alphabet_size, max_symbol, s); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } } + /* Fall through. */ - s->symbol = 0; - s->prev_code_len = kDefaultCodeLength; - s->repeat = 0; - s->repeat_code_len = 0; - s->space = 32768; - s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; - /* No break, transit to the next state. */ - } - case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: { - uint32_t table_size; - BrotliErrorCode result = ReadSymbolCodeLengths(alphabet_size, s); - if (result == BROTLI_NEEDS_MORE_INPUT) { - result = SafeReadSymbolCodeLengths(alphabet_size, s); - } - if (result != BROTLI_SUCCESS) { - return result; + case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: { + uint32_t table_size; + if (s->symbol == 3) { + uint32_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { + s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + s->symbol += bits; + } + BROTLI_LOG_UINT(s->symbol); + table_size = BrotliBuildSimpleHuffmanTable( + table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol); + if (opt_table_size) { + *opt_table_size = table_size; + } + s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; } - if (s->space != 0) { - BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", s->space)); - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_HUFFMAN_SPACE); + /* Decode Huffman-coded code lengths. */ + case BROTLI_STATE_HUFFMAN_COMPLEX: { + uint32_t i; + BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + BrotliBuildCodeLengthsHuffmanTable(s->table, + s->code_length_code_lengths, + s->code_length_histo); + memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo)); + for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) { + s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); + s->symbol_lists[s->next_symbol[i]] = 0xFFFF; + } + + s->symbol = 0; + s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH; + s->repeat = 0; + s->repeat_code_len = 0; + s->space = 32768; + s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; } - table_size = BrotliBuildHuffmanTable( - table, HUFFMAN_TABLE_BITS, s->symbol_lists, s->code_length_histo); - if (opt_table_size) { - *opt_table_size = table_size; + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: { + uint32_t table_size; + BrotliDecoderErrorCode result = ReadSymbolCodeLengths(max_symbol, s); + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + result = SafeReadSymbolCodeLengths(max_symbol, s); + } + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + + if (s->space != 0) { + BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)s->space)); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE); + } + table_size = BrotliBuildHuffmanTable( + table, HUFFMAN_TABLE_BITS, s->symbol_lists, s->code_length_histo); + if (opt_table_size) { + *opt_table_size = table_size; + } + s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; } - s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; - return BROTLI_SUCCESS; - } - default: - return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE); + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); + } } } @@ -796,35 +867,34 @@ static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table, uint32_t code; uint32_t nbits; code = ReadSymbol(table, br); - nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */ + nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */ return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits); } /* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then reading can't be continued with ReadBlockLength. */ -static BROTLI_INLINE int SafeReadBlockLength(BrotliState* s, - uint32_t* result, - const HuffmanCode* table, - BrotliBitReader* br) { +static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( + BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table, + BrotliBitReader* br) { uint32_t index; if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) { if (!SafeReadSymbol(table, br, &index)) { - return 0; + return BROTLI_FALSE; } } else { index = s->block_length_index; } { uint32_t bits; - uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */ + uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */ if (!BrotliSafeReadBits(br, nbits, &bits)) { s->block_length_index = index; s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX; - return 0; + return BROTLI_FALSE; } *result = kBlockLengthPrefixCode[index].offset + bits; s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; - return 1; + return BROTLI_TRUE; } } @@ -841,47 +911,47 @@ static BROTLI_INLINE int SafeReadBlockLength(BrotliState* s, 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, BrotliState* state) { + inner for loop with do-while. */ +static BROTLI_NOINLINE void InverseMoveToFrontTransform( + uint8_t* v, uint32_t v_len, BrotliDecoderState* state) { /* Reinitialize elements that could have been changed. */ - uint32_t i = 4; + uint32_t i = 1; uint32_t upper_bound = state->mtf_upper_bound; - uint8_t* mtf = &state->mtf[4]; /* Make mtf[-1] addressable. */ + uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */ + uint8_t* mtf_u8 = (uint8_t*)mtf; /* Load endian-aware constant. */ const uint8_t b0123[4] = {0, 1, 2, 3}; uint32_t pattern; memcpy(&pattern, &b0123, 4); /* Initialize list using 4 consequent values pattern. */ - *(uint32_t*)mtf = pattern; + mtf[0] = pattern; do { - pattern += 0x04040404; /* Advance all 4 values by 4. */ - *(uint32_t*)(mtf + i) = pattern; - i += 4; + pattern += 0x04040404; /* Advance all 4 values by 4. */ + mtf[i] = pattern; + i++; } while (i <= upper_bound); /* Transform the input. */ upper_bound = 0; for (i = 0; i < v_len; ++i) { int index = v[i]; - uint8_t value = mtf[index]; + uint8_t value = mtf_u8[index]; upper_bound |= v[i]; v[i] = value; - mtf[-1] = value; + mtf_u8[-1] = value; do { index--; - mtf[index + 1] = mtf[index]; + mtf_u8[index + 1] = mtf_u8[index]; } while (index >= 0); } /* Remember amount of elements to be reinitialized. */ - state->mtf_upper_bound = upper_bound; + state->mtf_upper_bound = upper_bound >> 2; } /* Decodes a series of Huffman table using ReadHuffmanCode function. */ -static BrotliErrorCode HuffmanTreeGroupDecode(HuffmanTreeGroup* group, - BrotliState* s) { +static BrotliDecoderErrorCode HuffmanTreeGroupDecode( + HuffmanTreeGroup* group, BrotliDecoderState* s) { if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) { s->next = group->codes; s->htree_index = 0; @@ -889,15 +959,16 @@ static BrotliErrorCode HuffmanTreeGroupDecode(HuffmanTreeGroup* group, } while (s->htree_index < group->num_htrees) { uint32_t table_size; - BrotliErrorCode result = - ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s); - if (result != BROTLI_SUCCESS) return result; + BrotliDecoderErrorCode result = + ReadHuffmanCode(group->alphabet_size, group->max_symbol, + s->next, &table_size, s); + if (result != BROTLI_DECODER_SUCCESS) return result; group->htrees[s->htree_index] = s->next; s->next += table_size; ++s->htree_index; } s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* Decodes a context map. @@ -907,43 +978,44 @@ static BrotliErrorCode HuffmanTreeGroupDecode(HuffmanTreeGroup* group, 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 BrotliErrorCode DecodeContextMap(uint32_t context_map_size, - uint32_t* num_htrees, - uint8_t** context_map_arg, - BrotliState* s) { + 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) { BrotliBitReader* br = &s->br; - BrotliErrorCode result = BROTLI_SUCCESS; + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; switch ((int)s->substate_context_map) { case BROTLI_STATE_CONTEXT_MAP_NONE: result = DecodeVarLenUint8(s, br, num_htrees); - if (result != BROTLI_SUCCESS) { + if (result != BROTLI_DECODER_SUCCESS) { return result; } (*num_htrees)++; s->context_index = 0; BROTLI_LOG_UINT(context_map_size); BROTLI_LOG_UINT(*num_htrees); - *context_map_arg = (uint8_t*)BROTLI_ALLOC(s, (size_t)context_map_size); + *context_map_arg = + (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)context_map_size); if (*context_map_arg == 0) { - return BROTLI_FAILURE(BROTLI_ERROR_ALLOC_CONTEXT_MAP); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP); } if (*num_htrees <= 1) { memset(*context_map_arg, 0, (size_t)context_map_size); - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; - /* No break, continue to next state. */ + /* Fall through. */ + case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: { uint32_t bits; /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe to peek 4 bits ahead. */ if (!BrotliSafeGetBits(br, 5, &bits)) { - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - if ((bits & 1) != 0) { /* Use RLE for zeroes. */ + if ((bits & 1) != 0) { /* Use RLE for zeros. */ s->max_run_length_prefix = (bits >> 1) + 1; BrotliDropBits(br, 5); } else { @@ -952,81 +1024,91 @@ static BrotliErrorCode DecodeContextMap(uint32_t context_map_size, } BROTLI_LOG_UINT(s->max_run_length_prefix); s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN; - /* No break, continue to next state. */ } - case BROTLI_STATE_CONTEXT_MAP_HUFFMAN: - result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix, + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_HUFFMAN: { + uint32_t alphabet_size = *num_htrees + s->max_run_length_prefix; + result = ReadHuffmanCode(alphabet_size, alphabet_size, s->context_map_table, NULL, s); - if (result != BROTLI_SUCCESS) return result; + if (result != BROTLI_DECODER_SUCCESS) return result; s->code = 0xFFFF; s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE; - /* No break, continue to next state. */ + } + /* Fall through. */ + case BROTLI_STATE_CONTEXT_MAP_DECODE: { uint32_t context_index = s->context_index; uint32_t max_run_length_prefix = s->max_run_length_prefix; uint8_t* context_map = *context_map_arg; uint32_t code = s->code; - if (code != 0xFFFF) { - goto rleCode; - } - while (context_index < context_map_size) { - if (!SafeReadSymbol(s->context_map_table, br, &code)) { - s->code = 0xFFFF; - s->context_index = context_index; - return BROTLI_NEEDS_MORE_INPUT; - } - BROTLI_LOG_UINT(code); + BROTLI_BOOL skip_preamble = (code != 0xFFFF); + while (context_index < context_map_size || skip_preamble) { + if (!skip_preamble) { + if (!SafeReadSymbol(s->context_map_table, br, &code)) { + s->code = 0xFFFF; + s->context_index = context_index; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BROTLI_LOG_UINT(code); - if (code == 0) { - context_map[context_index++] = 0; - continue; - } - if (code > max_run_length_prefix) { - context_map[context_index++] = - (uint8_t)(code - max_run_length_prefix); - continue; + if (code == 0) { + context_map[context_index++] = 0; + continue; + } + if (code > max_run_length_prefix) { + context_map[context_index++] = + (uint8_t)(code - max_run_length_prefix); + continue; + } + } else { + skip_preamble = BROTLI_FALSE; } -rleCode: + /* RLE sub-stage. */ { uint32_t reps; if (!BrotliSafeReadBits(br, code, &reps)) { s->code = code; s->context_index = context_index; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } reps += 1U << code; BROTLI_LOG_UINT(reps); if (context_index + reps > context_map_size) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_CONTEXT_MAP_REPEAT); + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT); } do { context_map[context_index++] = 0; } while (--reps); } } - /* No break, continue to next state. */ } + /* Fall through. */ + case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: { uint32_t bits; if (!BrotliSafeReadBits(br, 1, &bits)) { s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits != 0) { InverseMoveToFrontTransform(*context_map_arg, context_map_size, s); } s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } + default: - return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE); + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } -/* Decodes a command or literal and updates block type ringbuffer. +/* Decodes a command or literal and updates block type ring-buffer. Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe, - BrotliState* s, int tree_type) { +static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength( + int safe, BrotliDecoderState* s, int tree_type) { uint32_t max_block_type = s->num_block_types[tree_type]; const HuffmanCode* type_tree = &s->block_type_trees[ tree_type * BROTLI_HUFFMAN_MAX_SIZE_258]; @@ -1035,19 +1117,22 @@ static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe, BrotliBitReader* br = &s->br; uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2]; uint32_t block_type; + if (max_block_type <= 1) { + return BROTLI_FALSE; + } - /* Read 0..15 + 3..39 bits */ + /* Read 0..15 + 3..39 bits. */ if (!safe) { block_type = ReadSymbol(type_tree, br); s->block_length[tree_type] = ReadBlockLength(len_tree, br); } else { BrotliBitReaderState memento; BrotliBitReaderSaveState(br, &memento); - if (!SafeReadSymbol(type_tree, br, &block_type)) return 0; + if (!SafeReadSymbol(type_tree, br, &block_type)) return BROTLI_FALSE; if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) { s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; BrotliBitReaderRestoreState(br, &memento); - return 0; + return BROTLI_FALSE; } } @@ -1063,18 +1148,19 @@ static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe, } ringbuffer[0] = ringbuffer[1]; ringbuffer[1] = block_type; - return 1; + return BROTLI_TRUE; } -static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(BrotliState* s) { +static BROTLI_INLINE void DetectTrivialLiteralBlockTypes( + BrotliDecoderState* s) { size_t i; for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0; for (i = 0; i < s->num_block_types[0]; i++) { - size_t offset = i << kLiteralContextBits; + size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS; size_t error = 0; size_t sample = s->context_map[offset]; size_t j; - for (j = 0; j < (1u << kLiteralContextBits);) { + for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) { BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;) } if (error == 0) { @@ -1083,151 +1169,185 @@ static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(BrotliState* s) { } } -static BROTLI_INLINE void PrepareLiteralDecoding(BrotliState* s) { +static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) { uint8_t context_mode; size_t trivial; uint32_t block_type = s->block_type_rb[1]; - uint32_t context_offset = block_type << kLiteralContextBits; + uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS; s->context_map_slice = s->context_map + context_offset; trivial = s->trivial_literal_contexts[block_type >> 5]; s->trivial_literal_context = (trivial >> (block_type & 31)) & 1; s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]]; - context_mode = s->context_modes[block_type]; - s->context_lookup1 = &kContextLookup[kContextLookupOffsets[context_mode]]; - s->context_lookup2 = &kContextLookup[kContextLookupOffsets[context_mode + 1]]; + context_mode = s->context_modes[block_type] & 3; + s->context_lookup = BROTLI_CONTEXT_LUT(context_mode); } /* Decodes the block type and updates the state for literal context. Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeLiteralBlockSwitchInternal(int safe, - BrotliState* s) { +static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal( + int safe, BrotliDecoderState* s) { if (!DecodeBlockTypeAndLength(safe, s, 0)) { - return 0; + return BROTLI_FALSE; } PrepareLiteralDecoding(s); - return 1; + return BROTLI_TRUE; } -static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliState* s) { +static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) { DecodeLiteralBlockSwitchInternal(0, s); } -static int BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(BrotliState* s) { +static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch( + BrotliDecoderState* s) { return DecodeLiteralBlockSwitchInternal(1, s); } /* Block switch for insert/copy length. Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeCommandBlockSwitchInternal(int safe, - BrotliState* s) { +static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal( + int safe, BrotliDecoderState* s) { if (!DecodeBlockTypeAndLength(safe, s, 1)) { - return 0; + return BROTLI_FALSE; } s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]]; - return 1; + return BROTLI_TRUE; } -static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliState* s) { +static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) { DecodeCommandBlockSwitchInternal(0, s); } -static int BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(BrotliState* s) { + +static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch( + BrotliDecoderState* s) { return DecodeCommandBlockSwitchInternal(1, s); } /* Block switch for distance codes. Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeDistanceBlockSwitchInternal(int safe, - BrotliState* s) { +static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal( + int safe, BrotliDecoderState* s) { if (!DecodeBlockTypeAndLength(safe, s, 2)) { - return 0; + return BROTLI_FALSE; } - s->dist_context_map_slice = - s->dist_context_map + (s->block_type_rb[5] << kDistanceContextBits); + s->dist_context_map_slice = s->dist_context_map + + (s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS); s->dist_htree_index = s->dist_context_map_slice[s->distance_context]; - return 1; + return BROTLI_TRUE; } -static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliState* s) { +static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) { DecodeDistanceBlockSwitchInternal(0, s); } -static int BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(BrotliState* s) { +static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch( + BrotliDecoderState* s) { return DecodeDistanceBlockSwitchInternal(1, s); } -static BrotliErrorCode BROTLI_NOINLINE WriteRingBuffer(size_t* available_out, - uint8_t** next_out, size_t* total_out, BrotliState* s) { - size_t pos = (s->pos > s->ringbuffer_size) ? (size_t)s->ringbuffer_size - : (size_t)(s->pos); +static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) { + size_t pos = wrap && s->pos > s->ringbuffer_size ? + (size_t)s->ringbuffer_size : (size_t)(s->pos); + size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos; + return partial_pos_rb - s->partial_pos_out; +} + +/* 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) { uint8_t* start = s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask); - size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos; - size_t to_write = (partial_pos_rb - s->partial_pos_out); + size_t to_write = UnwrittenBytes(s, BROTLI_TRUE); size_t num_written = *available_out; if (num_written > to_write) { num_written = to_write; } if (s->meta_block_remaining_len < 0) { - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_BLOCK_LENGTH_1); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1); + } + if (next_out && !*next_out) { + *next_out = start; + } else { + if (next_out) { + memcpy(*next_out, start, num_written); + *next_out += num_written; + } } - memcpy(*next_out, start, num_written); - *next_out += num_written; *available_out -= num_written; BROTLI_LOG_UINT(to_write); BROTLI_LOG_UINT(num_written); s->partial_pos_out += num_written; - if (total_out) *total_out = s->partial_pos_out; + if (total_out) { + *total_out = s->partial_pos_out; + } if (num_written < to_write) { - return BROTLI_NEEDS_MORE_OUTPUT; + if (s->ringbuffer_size == (1 << s->window_bits) || force) { + return BROTLI_DECODER_NEEDS_MORE_OUTPUT; + } else { + return BROTLI_DECODER_SUCCESS; + } } - - if (s->pos >= s->ringbuffer_size) { + /* Wrap ring buffer only if it has reached its maximal size. */ + if (s->ringbuffer_size == (1 << s->window_bits) && + s->pos >= s->ringbuffer_size) { s->pos -= s->ringbuffer_size; s->rb_roundtrips++; + s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0; + } + return BROTLI_DECODER_SUCCESS; +} + +static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) { + if (s->should_wrap_ringbuffer) { + memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos); + s->should_wrap_ringbuffer = 0; } - return BROTLI_SUCCESS; } -/* Allocates ringbuffer. +/* Allocates ring-buffer. - s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before - this function is called. + s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before + this function is called. - Last two bytes of ringbuffer are initialized to 0, so context calculation - could be done uniformly for the first two and all other positions. + 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) { + uint8_t* old_ringbuffer = s->ringbuffer; + if (s->ringbuffer_size == s->new_ringbuffer_size) { + return BROTLI_TRUE; + } - Custom dictionary, if any, is copied to the end of ringbuffer. -*/ -static int BROTLI_NOINLINE BrotliAllocateRingBuffer(BrotliState* s) { - /* We need the slack region for the following reasons: - - doing up to two 16-byte copies for fast backward copying - - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */ - static const int kRingBufferWriteAheadSlack = 42; - s->ringbuffer = (uint8_t*)BROTLI_ALLOC(s, (size_t)(s->ringbuffer_size + - kRingBufferWriteAheadSlack)); + s->ringbuffer = (uint8_t*)BROTLI_DECODER_ALLOC(s, + (size_t)(s->new_ringbuffer_size) + kRingBufferWriteAheadSlack); if (s->ringbuffer == 0) { - return 0; + /* Restore previous value. */ + s->ringbuffer = old_ringbuffer; + return BROTLI_FALSE; } + s->ringbuffer[s->new_ringbuffer_size - 2] = 0; + s->ringbuffer[s->new_ringbuffer_size - 1] = 0; - s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size; - - s->ringbuffer[s->ringbuffer_size - 2] = 0; - s->ringbuffer[s->ringbuffer_size - 1] = 0; - - if (s->custom_dict) { - memcpy(&s->ringbuffer[(-s->custom_dict_size) & s->ringbuffer_mask], - s->custom_dict, (size_t)s->custom_dict_size); + if (!!old_ringbuffer) { + memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos); + BROTLI_DECODER_FREE(s, old_ringbuffer); } - return 1; + s->ringbuffer_size = s->new_ringbuffer_size; + s->ringbuffer_mask = s->new_ringbuffer_size - 1; + s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size; + + return BROTLI_TRUE; } -static BrotliErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( +static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( size_t* available_out, uint8_t** next_out, size_t* total_out, - BrotliState* s) { + BrotliDecoderState* s) { /* TODO: avoid allocation for single uncompressed block. */ - if (!s->ringbuffer && !BrotliAllocateRingBuffer(s)) { - return BROTLI_FAILURE(BROTLI_ERROR_ALLOC_RING_BUFFER_1); + if (!BrotliEnsureRingBuffer(s)) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1); } /* State machine */ @@ -1241,26 +1361,30 @@ static BrotliErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( if (s->pos + nbytes > s->ringbuffer_size) { nbytes = s->ringbuffer_size - s->pos; } - /* Copy remaining bytes from s->br.buf_ to ringbuffer. */ + /* Copy remaining bytes from s->br.buf_ to ring-buffer. */ BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes); s->pos += nbytes; s->meta_block_remaining_len -= nbytes; - if (s->pos < s->ringbuffer_size) { + if (s->pos < 1 << s->window_bits) { if (s->meta_block_remaining_len == 0) { - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE; - /* No break, continue to next state */ } + /* Fall through. */ + case BROTLI_STATE_UNCOMPRESSED_WRITE: { - BrotliErrorCode result = - WriteRingBuffer(available_out, next_out, total_out, s); - if (result != BROTLI_SUCCESS) { + BrotliDecoderErrorCode result; + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_FALSE); + if (result != BROTLI_DECODER_SUCCESS) { return result; } - s->max_distance = s->max_backward_distance; + if (s->ringbuffer_size == 1 << s->window_bits) { + s->max_distance = s->max_backward_distance; + } s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; break; } @@ -1269,69 +1393,53 @@ static BrotliErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( BROTLI_DCHECK(0); /* Unreachable */ } -int BrotliDecompressedSize(size_t encoded_size, - const uint8_t* encoded_buffer, - size_t* decoded_size) { - BrotliState s; - int next_block_header; - BrotliStateInit(&s); - s.br.next_in = encoded_buffer; - s.br.avail_in = encoded_size; - if (!BrotliWarmupBitReader(&s.br)) { - return 0; - } - DecodeWindowBits(&s.br); - if (DecodeMetaBlockLength(&s, &s.br) != BROTLI_SUCCESS) { - return 0; - } - *decoded_size = (size_t)s.meta_block_remaining_len; - if (s.is_last_metablock) { - return 1; - } - if (!s.is_uncompressed || !BrotliJumpToByteBoundary(&s.br)) { - return 0; - } - next_block_header = BrotliPeekByte(&s.br, (size_t)s.meta_block_remaining_len); - return (next_block_header != -1) && ((next_block_header & 3) == 3); -} - /* Calculates the smallest feasible ring buffer. - If we know the data size is small, do not allocate more ringbuffer + 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(BrotliState* s, - BrotliBitReader* br) { - int is_last = s->is_last_metablock; + When this method is called, metablock size and flags MUST be decoded. */ +static void BROTLI_NOINLINE BrotliCalculateRingBufferSize( + BrotliDecoderState* s) { int window_size = 1 << s->window_bits; - s->ringbuffer_size = window_size; - - if (s->is_uncompressed) { - int next_block_header = - BrotliPeekByte(br, (size_t)s->meta_block_remaining_len); - if (next_block_header != -1) { /* Peek succeeded */ - if ((next_block_header & 3) == 3) { /* ISLAST and ISEMPTY */ - is_last = 1; - } - } - } - + int new_ringbuffer_size = window_size; /* We need at least 2 bytes of ring buffer size to get the last two bytes for context from there */ - if (is_last) { - int min_size_x2 = (s->meta_block_remaining_len + s->custom_dict_size) * 2; - while (s->ringbuffer_size >= min_size_x2 && s->ringbuffer_size > 32) { - s->ringbuffer_size >>= 1; + int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024; + int output_size; + + /* If maximum is already reached, no further extension is retired. */ + if (s->ringbuffer_size == window_size) { + return; + } + + /* Metadata blocks does not touch ring buffer. */ + if (s->is_metadata) { + return; + } + + if (!s->ringbuffer) { + output_size = 0; + } else { + output_size = s->pos; + } + output_size += s->meta_block_remaining_len; + min_size = min_size < output_size ? output_size : min_size; + + if (!!s->canny_ringbuffer_allocation) { + /* Reduce ring buffer size to save memory when server is unscrupulous. + In worst case memory usage might be 1.5x bigger for a short period of + ring buffer reallocation. */ + while ((new_ringbuffer_size >> 1) >= min_size) { + new_ringbuffer_size >>= 1; } } - s->ringbuffer_mask = s->ringbuffer_size - 1; + s->new_ringbuffer_size = new_ringbuffer_size; } /* Reads 1..256 2-bit context modes. */ -static BrotliErrorCode ReadContextModes(BrotliState* s) { +static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) { BrotliBitReader* br = &s->br; int i = s->loop_counter; @@ -1339,27 +1447,29 @@ static BrotliErrorCode ReadContextModes(BrotliState* s) { uint32_t bits; if (!BrotliSafeReadBits(br, 2, &bits)) { s->loop_counter = i; - return BROTLI_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->context_modes[i] = (uint8_t)(bits << 1); + s->context_modes[i] = (uint8_t)bits; BROTLI_LOG_ARRAY_INDEX(s->context_modes, i); i++; } - return BROTLI_SUCCESS; + return BROTLI_DECODER_SUCCESS; } -static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliState* s) { +static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) { if (s->distance_code == 0) { --s->dist_rb_idx; s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; + /* Compensate double distance-ring-buffer roll for dictionary items. */ + s->distance_context = 1; } else { int distance_code = s->distance_code << 1; - /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: */ - /* 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */ - const uint32_t kDistanceShortCodeIndexOffset = 0xaaafff1b; - /* kDistanceShortCodeValueOffset has 2-bit values from LSB: */ - /*-0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */ - const uint32_t kDistanceShortCodeValueOffset = 0xfa5fa500; + /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: + 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */ + const uint32_t kDistanceShortCodeIndexOffset = 0xAAAFFF1B; + /* kDistanceShortCodeValueOffset has 2-bit values from LSB: + -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */ + const uint32_t kDistanceShortCodeValueOffset = 0xFA5FA500; int v = (s->dist_rb_idx + (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3; s->distance_code = s->dist_rb[v]; @@ -1369,27 +1479,27 @@ static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliState* s) { } else { s->distance_code -= v; if (s->distance_code <= 0) { - /* A huge distance will cause a BROTLI_FAILURE() soon. */ - /* This is a little faster than failing here. */ - s->distance_code = 0x0fffffff; + /* A huge distance will cause a BROTLI_FAILURE() soon. + This is a little faster than failing here. */ + s->distance_code = 0x7FFFFFFF; } } } } -static BROTLI_INLINE int SafeReadBits( +static BROTLI_INLINE BROTLI_BOOL SafeReadBits( BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { if (n_bits != 0) { return BrotliSafeReadBits(br, n_bits, val); } else { *val = 0; - return 1; + return BROTLI_TRUE; } } -/* Precondition: s->distance_code < 0 */ -static BROTLI_INLINE int ReadDistanceInternal(int safe, - BrotliState* s, BrotliBitReader* br) { +/* Precondition: s->distance_code < 0. */ +static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal( + int safe, BrotliDecoderState* s, BrotliBitReader* br) { int distval; BrotliBitReaderState memento; HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; @@ -1399,16 +1509,17 @@ static BROTLI_INLINE int ReadDistanceInternal(int safe, uint32_t code; BrotliBitReaderSaveState(br, &memento); if (!SafeReadSymbol(distance_tree, br, &code)) { - return 0; + return BROTLI_FALSE; } s->distance_code = (int)code; } - /* Convert the distance code to the actual distance by possibly */ - /* looking up past distances from the s->ringbuffer. */ - if ((s->distance_code & ~0xf) == 0) { + /* Convert the distance code to the actual distance by possibly + looking up past distances from the s->ringbuffer. */ + s->distance_context = 0; + if ((s->distance_code & ~0xF) == 0) { TakeDistanceFromRingBuffer(s); --s->block_length[2]; - return 1; + return BROTLI_TRUE; } distval = s->distance_code - (int)s->num_direct_distance_codes; if (distval >= 0) { @@ -1421,16 +1532,16 @@ static BROTLI_INLINE int ReadDistanceInternal(int safe, s->distance_code = (int)s->num_direct_distance_codes + offset + (int)BrotliReadBits(br, nbits); } else { - /* This branch also works well when s->distance_postfix_bits == 0 */ + /* This branch also works well when s->distance_postfix_bits == 0. */ uint32_t bits; postfix = distval & s->distance_postfix_mask; distval >>= s->distance_postfix_bits; nbits = ((uint32_t)distval >> 1) + 1; if (safe) { if (!SafeReadBits(br, nbits, &bits)) { - s->distance_code = -1; /* Restore precondition. */ + s->distance_code = -1; /* Restore precondition. */ BrotliBitReaderRestoreState(br, &memento); - return 0; + return BROTLI_FALSE; } } else { bits = BrotliReadBits(br, nbits); @@ -1440,21 +1551,23 @@ static BROTLI_INLINE int ReadDistanceInternal(int safe, ((offset + (int)bits) << s->distance_postfix_bits) + postfix; } } - s->distance_code = s->distance_code - NUM_DISTANCE_SHORT_CODES + 1; + s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1; --s->block_length[2]; - return 1; + return BROTLI_TRUE; } -static BROTLI_INLINE void ReadDistance(BrotliState* s, BrotliBitReader* br) { +static BROTLI_INLINE void ReadDistance( + BrotliDecoderState* s, BrotliBitReader* br) { ReadDistanceInternal(0, s, br); } -static BROTLI_INLINE int SafeReadDistance(BrotliState* s, BrotliBitReader* br) { +static BROTLI_INLINE BROTLI_BOOL SafeReadDistance( + BrotliDecoderState* s, BrotliBitReader* br) { return ReadDistanceInternal(1, s, br); } -static BROTLI_INLINE int ReadCommandInternal(int safe, - BrotliState* s, BrotliBitReader* br, int* insert_length) { +static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal( + int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { uint32_t cmd_code; uint32_t insert_len_extra = 0; uint32_t copy_length; @@ -1465,7 +1578,7 @@ static BROTLI_INLINE int ReadCommandInternal(int safe, } else { BrotliBitReaderSaveState(br, &memento); if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) { - return 0; + return BROTLI_FALSE; } } v = kCmdLut[cmd_code]; @@ -1474,7 +1587,7 @@ static BROTLI_INLINE int ReadCommandInternal(int safe, s->dist_htree_index = s->dist_context_map_slice[s->distance_context]; *insert_length = v.insert_len_offset; if (!safe) { - if (PREDICT_FALSE(v.insert_len_extra_bits != 0)) { + if (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) { insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits); } copy_length = BrotliReadBits(br, v.copy_len_extra_bits); @@ -1482,54 +1595,54 @@ static BROTLI_INLINE int ReadCommandInternal(int safe, if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) || !SafeReadBits(br, v.copy_len_extra_bits, ©_length)) { BrotliBitReaderRestoreState(br, &memento); - return 0; + return BROTLI_FALSE; } } s->copy_length = (int)copy_length + v.copy_len_offset; --s->block_length[1]; *insert_length += (int)insert_len_extra; - return 1; + return BROTLI_TRUE; } -static BROTLI_INLINE void ReadCommand(BrotliState* s, BrotliBitReader* br, - int* insert_length) { +static BROTLI_INLINE void ReadCommand( + BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { ReadCommandInternal(0, s, br, insert_length); } -static BROTLI_INLINE int SafeReadCommand(BrotliState* s, BrotliBitReader* br, - int* insert_length) { +static BROTLI_INLINE BROTLI_BOOL SafeReadCommand( + BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { return ReadCommandInternal(1, s, br, insert_length); } -static BROTLI_INLINE int CheckInputAmount(int safe, - BrotliBitReader* const br, size_t num) { +static BROTLI_INLINE BROTLI_BOOL CheckInputAmount( + int safe, BrotliBitReader* const br, size_t num) { if (safe) { - return 1; + return BROTLI_TRUE; } return BrotliCheckInputAmount(br, num); } -#define BROTLI_SAFE(METHOD) \ - { \ - if (safe) { \ - if (!Safe##METHOD) { \ - result = BROTLI_NEEDS_MORE_INPUT; \ - goto saveStateAndReturn; \ - } \ - } else { \ - METHOD; \ - } \ +#define BROTLI_SAFE(METHOD) \ + { \ + if (safe) { \ + if (!Safe##METHOD) { \ + result = BROTLI_DECODER_NEEDS_MORE_INPUT; \ + goto saveStateAndReturn; \ + } \ + } else { \ + METHOD; \ + } \ } -static BROTLI_INLINE BrotliErrorCode ProcessCommandsInternal(int safe, - BrotliState* s) { +static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal( + int safe, BrotliDecoderState* s) { int pos = s->pos; int i = s->loop_counter; - BrotliErrorCode result = BROTLI_SUCCESS; + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; BrotliBitReader* br = &s->br; if (!CheckInputAmount(safe, br, 28)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; goto saveStateAndReturn; } if (!safe) { @@ -1546,23 +1659,23 @@ static BROTLI_INLINE BrotliErrorCode ProcessCommandsInternal(int safe, } else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) { goto CommandPostWrapCopy; } else { - return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } CommandBegin: if (safe) { s->state = BROTLI_STATE_COMMAND_BEGIN; } - if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */ + if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */ s->state = BROTLI_STATE_COMMAND_BEGIN; - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; goto saveStateAndReturn; } - if (PREDICT_FALSE(s->block_length[1] == 0)) { + if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) { BROTLI_SAFE(DecodeCommandBlockSwitch(s)); goto CommandBegin; } - /* Read the insert/copy length in the command */ + /* Read the insert/copy length in the command. */ BROTLI_SAFE(ReadCommand(s, br, &i)); BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n", pos, i, s->copy_length)); @@ -1575,18 +1688,18 @@ CommandInner: if (safe) { s->state = BROTLI_STATE_COMMAND_INNER; } - /* Read the literals in the command */ + /* Read the literals in the command. */ if (s->trivial_literal_context) { uint32_t bits; uint32_t value; PreloadSymbol(safe, s->literal_htree, br, &bits, &value); do { - if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */ + if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */ s->state = BROTLI_STATE_COMMAND_INNER; - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; goto saveStateAndReturn; } - if (PREDICT_FALSE(s->block_length[0] == 0)) { + if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); PreloadSymbol(safe, s->literal_htree, br, &bits, &value); if (!s->trivial_literal_context) goto CommandInner; @@ -1597,7 +1710,7 @@ CommandInner: } else { uint32_t literal; if (!SafeReadSymbol(s->literal_htree, br, &literal)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; goto saveStateAndReturn; } s->ringbuffer[pos] = (uint8_t)literal; @@ -1605,7 +1718,7 @@ CommandInner: --s->block_length[0]; BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos); ++pos; - if (PREDICT_FALSE(pos == s->ringbuffer_size)) { + if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) { s->state = BROTLI_STATE_COMMAND_INNER_WRITE; --i; goto saveStateAndReturn; @@ -1617,16 +1730,16 @@ CommandInner: do { const HuffmanCode* hc; uint8_t context; - if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */ + if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */ s->state = BROTLI_STATE_COMMAND_INNER; - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; goto saveStateAndReturn; } - if (PREDICT_FALSE(s->block_length[0] == 0)) { + if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); if (s->trivial_literal_context) goto CommandInner; } - context = s->context_lookup1[p1] | s->context_lookup2[p2]; + context = BROTLI_CONTEXT(p1, p2, s->context_lookup); BROTLI_LOG_UINT(context); hc = s->literal_hgroup.htrees[s->context_map_slice[context]]; p2 = p1; @@ -1635,7 +1748,7 @@ CommandInner: } else { uint32_t literal; if (!SafeReadSymbol(hc, br, &literal)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; goto saveStateAndReturn; } p1 = (uint8_t)literal; @@ -1645,7 +1758,7 @@ CommandInner: BROTLI_LOG_UINT(s->context_map_slice[context]); BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask); ++pos; - if (PREDICT_FALSE(pos == s->ringbuffer_size)) { + if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) { s->state = BROTLI_STATE_COMMAND_INNER_WRITE; --i; goto saveStateAndReturn; @@ -1653,7 +1766,7 @@ CommandInner: } while (--i != 0); } BROTLI_LOG_UINT(s->meta_block_remaining_len); - if (PREDICT_FALSE(s->meta_block_remaining_len <= 0)) { + if (BROTLI_PREDICT_FALSE(s->meta_block_remaining_len <= 0)) { s->state = BROTLI_STATE_METABLOCK_DONE; goto saveStateAndReturn; } @@ -1663,51 +1776,70 @@ CommandPostDecodeLiterals: s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS; } if (s->distance_code >= 0) { + /* Implicit distance case. */ + s->distance_context = s->distance_code ? 0 : 1; --s->dist_rb_idx; s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; - goto postReadDistance; /* We already have the implicit distance */ - } - /* Read distance code in the command, unless it was implicitly zero. */ - if (PREDICT_FALSE(s->block_length[2] == 0)) { - BROTLI_SAFE(DecodeDistanceBlockSwitch(s)); + } else { + /* Read distance code in the command, unless it was implicitly zero. */ + if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) { + BROTLI_SAFE(DecodeDistanceBlockSwitch(s)); + } + BROTLI_SAFE(ReadDistance(s, br)); } - BROTLI_SAFE(ReadDistance(s, br)); -postReadDistance: BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n", pos, s->distance_code)); if (s->max_distance != s->max_backward_distance) { - if (pos < s->max_backward_distance_minus_custom_dict_size) { - s->max_distance = pos + s->custom_dict_size; - } else { - s->max_distance = s->max_backward_distance; - } + s->max_distance = + (pos < s->max_backward_distance) ? pos : s->max_backward_distance; } i = s->copy_length; /* Apply copy of LZ77 back-reference, or static dictionary reference if - the distance is larger than the max LZ77 distance */ + the distance is larger than the max LZ77 distance */ if (s->distance_code > s->max_distance) { - if (i >= kBrotliMinDictionaryWordLength && - i <= kBrotliMaxDictionaryWordLength) { - int offset = (int)kBrotliDictionaryOffsetsByLength[i]; - int word_id = s->distance_code - s->max_distance - 1; - uint32_t shift = kBrotliDictionarySizeBitsByLength[i]; + /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC. + With this choice, no signed overflow can occur after decoding + a special distance code (e.g., after adding 3 to the last distance). */ + if (s->distance_code > BROTLI_MAX_ALLOWED_DISTANCE) { + BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d " + "len: %d bytes left: %d\n", + pos, s->distance_code, i, s->meta_block_remaining_len)); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE); + } + if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH && + i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) { + int address = s->distance_code - s->max_distance - 1; + const BrotliDictionary* words = s->dictionary; + const BrotliTransforms* transforms = s->transforms; + int offset = (int)s->dictionary->offsets_by_length[i]; + uint32_t shift = s->dictionary->size_bits_by_length[i]; + int mask = (int)BitMask(shift); - int word_idx = word_id & mask; - int transform_idx = word_id >> shift; + int word_idx = address & mask; + int transform_idx = address >> shift; + /* Compensate double distance-ring-buffer roll. */ + s->dist_rb_idx += s->distance_context; offset += word_idx * i; - if (transform_idx < kNumTransforms) { - const uint8_t* word = &kBrotliDictionary[offset]; + if (BROTLI_PREDICT_FALSE(!words->data)) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET); + } + if (transform_idx < (int)transforms->num_transforms) { + const uint8_t* word = &words->data[offset]; int len = i; - if (transform_idx == 0) { + if (transform_idx == transforms->cutOffTransforms[0]) { memcpy(&s->ringbuffer[pos], word, (size_t)len); + BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n", + len, word)); } else { - len = TransformDictionaryWord( - &s->ringbuffer[pos], word, len, transform_idx); + len = BrotliTransformDictionaryWord(&s->ringbuffer[pos], word, len, + transforms, transform_idx); + BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]," + " transform_idx = %d, transformed: [%.*s]\n", + i, word, transform_idx, len, &s->ringbuffer[pos])); } pos += len; s->meta_block_remaining_len -= len; if (pos >= s->ringbuffer_size) { - /*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/ s->state = BROTLI_STATE_COMMAND_POST_WRITE_1; goto saveStateAndReturn; } @@ -1715,13 +1847,13 @@ postReadDistance: BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d " "len: %d bytes left: %d\n", pos, s->distance_code, i, s->meta_block_remaining_len)); - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_TRANSFORM); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM); } } else { BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d " "len: %d bytes left: %d\n", pos, s->distance_code, i, s->meta_block_remaining_len)); - return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_DICTIONARY); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY); } } else { int src_start = (pos - s->distance_code) & s->ringbuffer_mask; @@ -1729,14 +1861,13 @@ postReadDistance: uint8_t* copy_src = &s->ringbuffer[src_start]; int dst_end = pos + i; int src_end = src_start + i; - /* update the recent distances cache */ + /* Update the recent distances cache. */ s->dist_rb[s->dist_rb_idx & 3] = s->distance_code; ++s->dist_rb_idx; s->meta_block_remaining_len -= i; - /* There are 32+ bytes of slack in the ringbuffer allocation. + /* There are 32+ bytes of slack in the ring-buffer allocation. Also, we have 16 short codes, that make these 16 bytes irrelevant - in the ringbuffer. Let's copy over them as a first guess. - */ + in the ring-buffer. Let's copy over them as a first guess. */ memmove16(copy_dst, copy_src); if (src_end > pos && dst_end > src_start) { /* Regions intersect. */ @@ -1759,7 +1890,7 @@ postReadDistance: } BROTLI_LOG_UINT(s->meta_block_remaining_len); if (s->meta_block_remaining_len <= 0) { - /* Next metablock, if any */ + /* Next metablock, if any. */ s->state = BROTLI_STATE_METABLOCK_DONE; goto saveStateAndReturn; } else { @@ -1772,14 +1903,14 @@ CommandPostWrapCopy: s->ringbuffer[pos] = s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask]; ++pos; - if (PREDICT_FALSE(--wrap_guard == 0)) { + if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) { s->state = BROTLI_STATE_COMMAND_POST_WRITE_2; goto saveStateAndReturn; } } } if (s->meta_block_remaining_len <= 0) { - /* Next metablock, if any */ + /* Next metablock, if any. */ s->state = BROTLI_STATE_METABLOCK_DONE; goto saveStateAndReturn; } else { @@ -1794,84 +1925,122 @@ saveStateAndReturn: #undef BROTLI_SAFE -static BROTLI_NOINLINE BrotliErrorCode ProcessCommands(BrotliState* s) { +static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands( + BrotliDecoderState* s) { return ProcessCommandsInternal(0, s); } -static BROTLI_NOINLINE BrotliErrorCode SafeProcessCommands(BrotliState* s) { +static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands( + BrotliDecoderState* s) { return ProcessCommandsInternal(1, s); } -BrotliResult BrotliDecompressBuffer(size_t encoded_size, - const uint8_t* encoded_buffer, - size_t* decoded_size, - uint8_t* decoded_buffer) { - BrotliState s; - BrotliResult result; +/* Returns the maximum number of distance symbols which can only represent + distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */ +static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect, uint32_t npostfix) { + static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28}; + static const uint32_t diff[BROTLI_MAX_NPOSTFIX + 1] = {73, 126, 228, 424}; + uint32_t postfix = 1U << npostfix; + if (ndirect < bound[npostfix]) { + return ndirect + diff[npostfix] + postfix; + } else if (ndirect > bound[npostfix] + postfix) { + return ndirect + diff[npostfix]; + } else { + return bound[npostfix] + diff[npostfix] + postfix; + } +} + +BrotliDecoderResult BrotliDecoderDecompress( + size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size, + uint8_t* decoded_buffer) { + BrotliDecoderState s; + BrotliDecoderResult result; size_t total_out = 0; size_t available_in = encoded_size; const uint8_t* next_in = encoded_buffer; size_t available_out = *decoded_size; uint8_t* next_out = decoded_buffer; - BrotliStateInit(&s); - result = BrotliDecompressStream(&available_in, &next_in, &available_out, - &next_out, &total_out, &s); + if (!BrotliDecoderStateInit(&s, 0, 0, 0)) { + return BROTLI_DECODER_RESULT_ERROR; + } + result = BrotliDecoderDecompressStream( + &s, &available_in, &next_in, &available_out, &next_out, &total_out); *decoded_size = total_out; - BrotliStateCleanup(&s); - if (result != BROTLI_RESULT_SUCCESS) { - result = BROTLI_RESULT_ERROR; + BrotliDecoderStateCleanup(&s); + if (result != BROTLI_DECODER_RESULT_SUCCESS) { + result = BROTLI_DECODER_RESULT_ERROR; } return result; } /* Invariant: input stream is never overconsumed: - * invalid input implies that the whole stream is invalid -> any amount of + - 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 leat one more byte is REQUIRED + - 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 + - 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 hold on enter -*/ -BrotliResult BrotliDecompressStream(size_t* available_in, - const uint8_t** next_in, size_t* available_out, uint8_t** next_out, - size_t* total_out, BrotliState* s) { - BrotliErrorCode result = BROTLI_SUCCESS; + - 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) { + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; BrotliBitReader* br = &s->br; - if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */ + /* Ensure that |total_out| is set, even if no data will ever be pushed out. */ + if (total_out) { + *total_out = s->partial_pos_out; + } + /* Do not try to process further in a case of unrecoverable error. */ + if ((int)s->error_code < 0) { + return BROTLI_DECODER_RESULT_ERROR; + } + if (*available_out && (!next_out || !*next_out)) { + return SaveErrorCode( + s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS)); + } + if (!*available_out) next_out = 0; + if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */ br->avail_in = *available_in; br->next_in = *next_in; } else { /* At least one byte of input is required. More than one byte of input may be required to complete the transaction -> reading more data must be done in a loop -> do it in a main loop. */ - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; br->next_in = &s->buffer.u8[0]; } /* State machine */ for (;;) { - if (result != BROTLI_SUCCESS) { /* Error | needs more input/output */ - if (result == BROTLI_NEEDS_MORE_INPUT) { - if (s->ringbuffer != 0) { /* Proactively push output. */ - WriteRingBuffer(available_out, next_out, total_out, s); - } - if (s->buffer_length != 0) { /* Used with internal buffer. */ - if (br->avail_in == 0) { /* Successfully finished read transaction. */ - /* Accamulator contains less than 8 bits, because internal buffer + if (result != BROTLI_DECODER_SUCCESS) { + /* Error, needs more input/output. */ + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + if (s->ringbuffer != 0) { /* Pro-actively push output. */ + BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s, + available_out, next_out, total_out, BROTLI_TRUE); + /* WriteRingBuffer checks s->meta_block_remaining_len validity. */ + if ((int)intermediate_result < 0) { + result = intermediate_result; + break; + } + } + if (s->buffer_length != 0) { /* Used with internal buffer. */ + if (br->avail_in == 0) { + /* Successfully finished read transaction. + Accumulator contains less than 8 bits, because internal buffer is expanded byte-by-byte until it is enough to complete read. */ s->buffer_length = 0; /* Switch to input stream and restart. */ - result = BROTLI_SUCCESS; + result = BROTLI_DECODER_SUCCESS; br->avail_in = *available_in; br->next_in = *next_in; continue; } else if (*available_in != 0) { /* Not enough data in buffer, but can take one more byte from input stream. */ - result = BROTLI_SUCCESS; + result = BROTLI_DECODER_SUCCESS; s->buffer.u8[s->buffer_length] = **next_in; s->buffer_length++; br->avail_in = s->buffer_length; @@ -1880,9 +2049,9 @@ BrotliResult BrotliDecompressStream(size_t* available_in, /* Retry with more data in buffer. */ continue; } - /* Can't finish reading and no more input.*/ + /* Can't finish reading and no more input. */ break; - } else { /* Input stream doesn't contain enough input. */ + } else { /* Input stream doesn't contain enough input. */ /* Copy tail to internal buffer and return. */ *next_in = br->next_in; *available_in = br->avail_in; @@ -1901,12 +2070,12 @@ BrotliResult BrotliDecompressStream(size_t* available_in, if (s->buffer_length != 0) { /* Just consumed the buffered input and produced some output. Otherwise - it would result in "needs more input". Reset internal buffer.*/ + it would result in "needs more input". Reset internal buffer. */ s->buffer_length = 0; } else { /* Using input stream in last iteration. When decoder switches to input - stream it has less than 8 bits in accamulator, so it is safe to - return unused accamulator bits there. */ + stream it has less than 8 bits in accumulator, so it is safe to + return unused accumulator bits there. */ BrotliBitReaderUnload(br); *available_in = br->avail_in; *next_in = br->next_in; @@ -1917,48 +2086,62 @@ BrotliResult BrotliDecompressStream(size_t* available_in, case BROTLI_STATE_UNINITED: /* Prepare to the first read. */ if (!BrotliWarmupBitReader(br)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; break; } /* Decode window size. */ - s->window_bits = DecodeWindowBits(br); /* Reads 1..7 bits. */ - BROTLI_LOG_UINT(s->window_bits); - if (s->window_bits == 9) { - /* Value 9 is reserved for future use. */ - result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_WINDOW_BITS); + result = DecodeWindowBits(s, br); /* Reads 1..8 bits. */ + if (result != BROTLI_DECODER_SUCCESS) { break; } - /* Maximum distance, see section 9.1. of the spec. */ - s->max_backward_distance = (1 << s->window_bits) - 16; - /* Limit custom dictionary size. */ - if (s->custom_dict_size >= s->max_backward_distance) { - s->custom_dict += s->custom_dict_size - s->max_backward_distance; - s->custom_dict_size = s->max_backward_distance; + if (s->large_window) { + s->state = BROTLI_STATE_LARGE_WINDOW_BITS; + break; + } + s->state = BROTLI_STATE_INITIALIZE; + break; + + case BROTLI_STATE_LARGE_WINDOW_BITS: + if (!BrotliSafeReadBits(br, 6, &s->window_bits)) { + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + break; + } + if (s->window_bits < BROTLI_LARGE_MIN_WBITS || + s->window_bits > BROTLI_LARGE_MAX_WBITS) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + break; } - s->max_backward_distance_minus_custom_dict_size = - s->max_backward_distance - s->custom_dict_size; + s->state = BROTLI_STATE_INITIALIZE; + /* Fall through. */ + + case BROTLI_STATE_INITIALIZE: + BROTLI_LOG_UINT(s->window_bits); + /* Maximum distance, see section 9.1. of the spec. */ + s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP; /* Allocate memory for both block_type_trees and block_len_trees. */ - s->block_type_trees = (HuffmanCode*)BROTLI_ALLOC(s, + s->block_type_trees = (HuffmanCode*)BROTLI_DECODER_ALLOC(s, sizeof(HuffmanCode) * 3 * (BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26)); if (s->block_type_trees == 0) { - result = BROTLI_FAILURE(BROTLI_ERROR_ALLOC_BLOCK_TYPE_TREES); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES); break; } s->block_len_trees = s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258; s->state = BROTLI_STATE_METABLOCK_BEGIN; - /* No break, continue to next state */ + /* Fall through. */ + case BROTLI_STATE_METABLOCK_BEGIN: - BrotliStateMetablockBegin(s); + BrotliDecoderStateMetablockBegin(s); BROTLI_LOG_UINT(s->pos); s->state = BROTLI_STATE_METABLOCK_HEADER; - /* No break, continue to next state */ + /* Fall through. */ + case BROTLI_STATE_METABLOCK_HEADER: - result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */ - if (result != BROTLI_SUCCESS) { + result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */ + if (result != BROTLI_DECODER_SUCCESS) { break; } BROTLI_LOG_UINT(s->is_last_metablock); @@ -1967,7 +2150,7 @@ BrotliResult BrotliDecompressStream(size_t* available_in, BROTLI_LOG_UINT(s->is_uncompressed); if (s->is_metadata || s->is_uncompressed) { if (!BrotliJumpToByteBoundary(br)) { - result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_PADDING_1); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1); break; } } @@ -1979,9 +2162,7 @@ BrotliResult BrotliDecompressStream(size_t* available_in, s->state = BROTLI_STATE_METABLOCK_DONE; break; } - if (!s->ringbuffer) { - BrotliCalculateRingBufferSize(s, br); - } + BrotliCalculateRingBufferSize(s); if (s->is_uncompressed) { s->state = BROTLI_STATE_UNCOMPRESSED; break; @@ -1989,30 +2170,31 @@ BrotliResult BrotliDecompressStream(size_t* available_in, s->loop_counter = 0; s->state = BROTLI_STATE_HUFFMAN_CODE_0; break; + case BROTLI_STATE_UNCOMPRESSED: { - int bytes_copied = s->meta_block_remaining_len; result = CopyUncompressedBlockToOutput( available_out, next_out, total_out, s); - bytes_copied -= s->meta_block_remaining_len; - if (result != BROTLI_SUCCESS) { + if (result != BROTLI_DECODER_SUCCESS) { break; } s->state = BROTLI_STATE_METABLOCK_DONE; break; } + case BROTLI_STATE_METADATA: for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) { uint32_t bits; /* Read one byte and ignore it. */ if (!BrotliSafeReadBits(br, 8, &bits)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; break; } } - if (result == BROTLI_SUCCESS) { + if (result == BROTLI_DECODER_SUCCESS) { s->state = BROTLI_STATE_METABLOCK_DONE; } break; + case BROTLI_STATE_HUFFMAN_CODE_0: if (s->loop_counter >= 3) { s->state = BROTLI_STATE_METABLOCK_HEADER_2; @@ -2020,7 +2202,7 @@ BrotliResult BrotliDecompressStream(size_t* available_in, } /* Reads 1..11 bits. */ result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]); - if (result != BROTLI_SUCCESS) { + if (result != BROTLI_DECODER_SUCCESS) { break; } s->num_block_types[s->loop_counter]++; @@ -2030,28 +2212,33 @@ BrotliResult BrotliDecompressStream(size_t* available_in, break; } s->state = BROTLI_STATE_HUFFMAN_CODE_1; - /* No break, continue to next state */ + /* Fall through. */ + case BROTLI_STATE_HUFFMAN_CODE_1: { + uint32_t alphabet_size = s->num_block_types[s->loop_counter] + 2; int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258; - result = ReadHuffmanCode(s->num_block_types[s->loop_counter] + 2, + result = ReadHuffmanCode(alphabet_size, alphabet_size, &s->block_type_trees[tree_offset], NULL, s); - if (result != BROTLI_SUCCESS) break; + if (result != BROTLI_DECODER_SUCCESS) break; s->state = BROTLI_STATE_HUFFMAN_CODE_2; - /* No break, continue to next state */ } + /* Fall through. */ + case BROTLI_STATE_HUFFMAN_CODE_2: { + uint32_t alphabet_size = BROTLI_NUM_BLOCK_LEN_SYMBOLS; int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; - result = ReadHuffmanCode(kNumBlockLengthCodes, + result = ReadHuffmanCode(alphabet_size, alphabet_size, &s->block_len_trees[tree_offset], NULL, s); - if (result != BROTLI_SUCCESS) break; + if (result != BROTLI_DECODER_SUCCESS) break; s->state = BROTLI_STATE_HUFFMAN_CODE_3; - /* No break, continue to next state */ } + /* Fall through. */ + case BROTLI_STATE_HUFFMAN_CODE_3: { int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter], &s->block_len_trees[tree_offset], br)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; break; } BROTLI_LOG_UINT(s->block_length[s->loop_counter]); @@ -2059,126 +2246,141 @@ BrotliResult BrotliDecompressStream(size_t* available_in, s->state = BROTLI_STATE_HUFFMAN_CODE_0; break; } + case BROTLI_STATE_METABLOCK_HEADER_2: { uint32_t bits; if (!BrotliSafeReadBits(br, 6, &bits)) { - result = BROTLI_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; break; } s->distance_postfix_bits = bits & BitMask(2); bits >>= 2; - s->num_direct_distance_codes = - NUM_DISTANCE_SHORT_CODES + (bits << s->distance_postfix_bits); + s->num_direct_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES + + (bits << s->distance_postfix_bits); BROTLI_LOG_UINT(s->num_direct_distance_codes); BROTLI_LOG_UINT(s->distance_postfix_bits); s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits); s->context_modes = - (uint8_t*)BROTLI_ALLOC(s, (size_t)s->num_block_types[0]); + (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)s->num_block_types[0]); if (s->context_modes == 0) { - result = BROTLI_FAILURE(BROTLI_ERROR_ALLOC_CONTEXT_MODES); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES); break; } s->loop_counter = 0; s->state = BROTLI_STATE_CONTEXT_MODES; - /* No break, continue to next state */ } + /* Fall through. */ + case BROTLI_STATE_CONTEXT_MODES: result = ReadContextModes(s); - if (result != BROTLI_SUCCESS) { + if (result != BROTLI_DECODER_SUCCESS) { break; } s->state = BROTLI_STATE_CONTEXT_MAP_1; - /* No break, continue to next state */ + /* Fall through. */ + case BROTLI_STATE_CONTEXT_MAP_1: result = DecodeContextMap( - s->num_block_types[0] << kLiteralContextBits, + s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS, &s->num_literal_htrees, &s->context_map, s); - if (result != BROTLI_SUCCESS) { + if (result != BROTLI_DECODER_SUCCESS) { break; } DetectTrivialLiteralBlockTypes(s); s->state = BROTLI_STATE_CONTEXT_MAP_2; - /* No break, continue to next state */ - case BROTLI_STATE_CONTEXT_MAP_2: - { - uint32_t num_distance_codes = - s->num_direct_distance_codes + (48U << s->distance_postfix_bits); - result = DecodeContextMap( - s->num_block_types[2] << kDistanceContextBits, - &s->num_dist_htrees, &s->dist_context_map, s); - if (result != BROTLI_SUCCESS) { - break; - } - BrotliHuffmanTreeGroupInit(s, &s->literal_hgroup, kNumLiteralCodes, - s->num_literal_htrees); - BrotliHuffmanTreeGroupInit(s, &s->insert_copy_hgroup, - kNumInsertAndCopyCodes, - s->num_block_types[1]); - BrotliHuffmanTreeGroupInit(s, &s->distance_hgroup, num_distance_codes, - s->num_dist_htrees); - if (s->literal_hgroup.codes == 0 || - s->insert_copy_hgroup.codes == 0 || - s->distance_hgroup.codes == 0) { - return SaveErrorCode(s, - BROTLI_FAILURE(BROTLI_ERROR_ALLOC_TREE_GROUPS)); - } + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_2: { + uint32_t num_direct_codes = + s->num_direct_distance_codes - BROTLI_NUM_DISTANCE_SHORT_CODES; + uint32_t num_distance_codes = BROTLI_DISTANCE_ALPHABET_SIZE( + s->distance_postfix_bits, num_direct_codes, + (s->large_window ? BROTLI_LARGE_MAX_DISTANCE_BITS : + BROTLI_MAX_DISTANCE_BITS)); + uint32_t max_distance_symbol = (s->large_window ? + BrotliMaxDistanceSymbol( + num_direct_codes, s->distance_postfix_bits) : + num_distance_codes); + BROTLI_BOOL allocation_success = BROTLI_TRUE; + result = DecodeContextMap( + s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS, + &s->num_dist_htrees, &s->dist_context_map, s); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( + s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS, + BROTLI_NUM_LITERAL_SYMBOLS, s->num_literal_htrees); + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( + s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS, + BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]); + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( + s, &s->distance_hgroup, num_distance_codes, + max_distance_symbol, s->num_dist_htrees); + if (!allocation_success) { + return SaveErrorCode(s, + BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS)); } s->loop_counter = 0; s->state = BROTLI_STATE_TREE_GROUP; - /* No break, continue to next state */ - case BROTLI_STATE_TREE_GROUP: - { - HuffmanTreeGroup* hgroup = NULL; - switch (s->loop_counter) { - case 0: - hgroup = &s->literal_hgroup; - break; - case 1: - hgroup = &s->insert_copy_hgroup; - break; - case 2: - hgroup = &s->distance_hgroup; - break; - default: - return SaveErrorCode(s, - BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE)); - } - result = HuffmanTreeGroupDecode(hgroup, s); + } + /* Fall through. */ + + case BROTLI_STATE_TREE_GROUP: { + HuffmanTreeGroup* hgroup = NULL; + switch (s->loop_counter) { + case 0: hgroup = &s->literal_hgroup; break; + case 1: hgroup = &s->insert_copy_hgroup; break; + case 2: hgroup = &s->distance_hgroup; break; + default: return SaveErrorCode(s, BROTLI_FAILURE( + BROTLI_DECODER_ERROR_UNREACHABLE)); } - if (result != BROTLI_SUCCESS) break; + result = HuffmanTreeGroupDecode(hgroup, s); + if (result != BROTLI_DECODER_SUCCESS) break; s->loop_counter++; if (s->loop_counter >= 3) { PrepareLiteralDecoding(s); s->dist_context_map_slice = s->dist_context_map; s->htree_command = s->insert_copy_hgroup.htrees[0]; - if (!s->ringbuffer && !BrotliAllocateRingBuffer(s)) { - result = BROTLI_FAILURE(BROTLI_ERROR_ALLOC_RING_BUFFER_2); + if (!BrotliEnsureRingBuffer(s)) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2); break; } s->state = BROTLI_STATE_COMMAND_BEGIN; } break; + } + case BROTLI_STATE_COMMAND_BEGIN: + /* Fall through. */ case BROTLI_STATE_COMMAND_INNER: + /* Fall through. */ case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS: + /* Fall through. */ case BROTLI_STATE_COMMAND_POST_WRAP_COPY: result = ProcessCommands(s); - if (result == BROTLI_NEEDS_MORE_INPUT) { + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { result = SafeProcessCommands(s); } break; + case BROTLI_STATE_COMMAND_INNER_WRITE: + /* Fall through. */ case BROTLI_STATE_COMMAND_POST_WRITE_1: + /* Fall through. */ case BROTLI_STATE_COMMAND_POST_WRITE_2: - result = WriteRingBuffer(available_out, next_out, total_out, s); - if (result != BROTLI_SUCCESS) { + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_FALSE); + if (result != BROTLI_DECODER_SUCCESS) { break; } - s->max_distance = s->max_backward_distance; + WrapRingBuffer(s); + if (s->ringbuffer_size == 1 << s->window_bits) { + s->max_distance = s->max_backward_distance; + } if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) { - memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos); if (s->meta_block_remaining_len == 0) { - /* Next metablock, if any */ + /* Next metablock, if any. */ s->state = BROTLI_STATE_METABLOCK_DONE; } else { s->state = BROTLI_STATE_COMMAND_BEGIN; @@ -2198,18 +2400,19 @@ BrotliResult BrotliDecompressStream(size_t* available_in, s->state = BROTLI_STATE_COMMAND_INNER; } break; + case BROTLI_STATE_METABLOCK_DONE: if (s->meta_block_remaining_len < 0) { - result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_BLOCK_LENGTH_2); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2); break; } - BrotliStateCleanupAfterMetablock(s); + BrotliDecoderStateCleanupAfterMetablock(s); if (!s->is_last_metablock) { s->state = BROTLI_STATE_METABLOCK_BEGIN; break; } if (!BrotliJumpToByteBoundary(br)) { - result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_PADDING_2); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2); break; } if (s->buffer_length == 0) { @@ -2218,11 +2421,13 @@ BrotliResult BrotliDecompressStream(size_t* available_in, *next_in = br->next_in; } s->state = BROTLI_STATE_DONE; - /* No break, continue to next state */ + /* Fall through. */ + case BROTLI_STATE_DONE: if (s->ringbuffer != 0) { - result = WriteRingBuffer(available_out, next_out, total_out, s); - if (result != BROTLI_SUCCESS) { + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_TRUE); + if (result != BROTLI_DECODER_SUCCESS) { break; } } @@ -2232,31 +2437,70 @@ BrotliResult BrotliDecompressStream(size_t* available_in, return SaveErrorCode(s, result); } -void BrotliSetCustomDictionary( - size_t size, const uint8_t* dict, BrotliState* s) { - if (size > (1u << 24)) { - return; +BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) { + /* After unrecoverable error remaining output is considered nonsensical. */ + if ((int)s->error_code < 0) { + return BROTLI_FALSE; + } + return TO_BROTLI_BOOL( + s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0); +} + +const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) { + uint8_t* result = 0; + size_t available_out = *size ? *size : 1u << 24; + size_t requested_out = available_out; + BrotliDecoderErrorCode status; + if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) { + *size = 0; + return 0; + } + WrapRingBuffer(s); + status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE); + /* Either WriteRingBuffer returns those "success" codes... */ + if (status == BROTLI_DECODER_SUCCESS || + status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) { + *size = requested_out - available_out; + } else { + /* ... or stream is broken. Normally this should be caught by + BrotliDecoderDecompressStream, this is just a safeguard. */ + if ((int)status < 0) SaveErrorCode(s, status); + *size = 0; + result = 0; } - s->custom_dict = dict; - s->custom_dict_size = (int)size; + return result; +} + +BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) { + return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED || + BrotliGetAvailableBits(&s->br) != 0); } -BrotliErrorCode BrotliGetErrorCode(const BrotliState* s) { - return (BrotliErrorCode)s->error_code; +BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) { + return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) && + !BrotliDecoderHasMoreOutput(s); } -const char* BrotliErrorString(BrotliErrorCode c) { +BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) { + return (BrotliDecoderErrorCode)s->error_code; +} + +const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) { switch (c) { -#define _BROTLI_ERROR_CODE_CASE(PREFIX, NAME, CODE) \ - case BROTLI ## PREFIX ## NAME: return #NAME; -#define _BROTLI_NOTHING - BROTLI_ERROR_CODES_LIST(_BROTLI_ERROR_CODE_CASE, _BROTLI_NOTHING) -#undef _BROTLI_ERROR_CODE_CASE -#undef _BROTLI_NOTHING +#define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \ + case BROTLI_DECODER ## PREFIX ## NAME: return #NAME; +#define BROTLI_NOTHING_ + BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_) +#undef BROTLI_ERROR_CODE_CASE_ +#undef BROTLI_NOTHING_ default: return "INVALID"; } } +uint32_t BrotliDecoderVersion() { + return BROTLI_VERSION; +} + #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ #endif |