X-Git-Url: http://git.ieval.ro/?a=blobdiff_plain;f=dec%2Fdecode.c;fp=dec%2Fdecode.c;h=0000000000000000000000000000000000000000;hb=c6145b6a4d86aead1b94bb5becd50d483a9210df;hp=6e3f9e1515be58beef75bb06a8752c1a9d3d287e;hpb=fd0f6b130ce1fb819de157da52d543bcf366bcd4;p=io-compress-brotli.git diff --git a/dec/decode.c b/dec/decode.c deleted file mode 100644 index 6e3f9e1..0000000 --- a/dec/decode.c +++ /dev/null @@ -1,2338 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved. - - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT -*/ - -#include -#include -#include -#include "./bit_reader.h" -#include "./context.h" -#include "./decode.h" -#include "./dictionary.h" -#include "./port.h" -#include "./transform.h" -#include "./huffman.h" -#include "./prefix.h" - -#ifdef __ARM_NEON__ -#include -#endif - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -#ifdef BROTLI_DECODE_DEBUG -#define BROTLI_LOG_UINT(name) \ - printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)) -#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \ - printf("[%s] %s[%lu] = %lu\n", __func__, #array_name, \ - (unsigned long)(idx), (unsigned long)array_name[idx]) -#define BROTLI_LOG(x) printf x -#else -#define BROTLI_LOG_UINT(name) -#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) -#define BROTLI_LOG(x) -#endif - -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 CODE_LENGTH_CODES 18 -static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = { - 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, -}; - -/* Static prefix code for the complex code length code lengths. */ -static const uint8_t kCodeLengthPrefixLength[16] = { - 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4, -}; - -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 - -BrotliState* BrotliCreateState( - brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { - BrotliState* state = 0; - if (!alloc_func && !free_func) { - state = (BrotliState*)malloc(sizeof(BrotliState)); - } else if (alloc_func && free_func) { - state = (BrotliState*)alloc_func(opaque, sizeof(BrotliState)); - } - if (state == 0) { - (void)BROTLI_FAILURE(); - return 0; - } - BrotliStateInitWithCustomAllocators(state, alloc_func, free_func, opaque); - return state; -} - -/* Deinitializes and frees BrotliState instance. */ -void BrotliDestroyState(BrotliState* state) { - if (!state) { - return; - } else { - brotli_free_func free_func = state->free_func; - void* opaque = state->memory_manager_opaque; - BrotliStateCleanup(state); - free_func(opaque, state); - } -} - -/* 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) { - uint32_t n; - BrotliTakeBits(br, 1, &n); - if (n == 0) { - return 16; - } - BrotliTakeBits(br, 3, &n); - if (n != 0) { - return 17 + n; - } - BrotliTakeBits(br, 3, &n); - if (n != 0) { - return 8 + n; - } - return 17; -} - -static BROTLI_INLINE BROTLI_NO_ASAN void memmove16( - uint8_t* dst, uint8_t* src) { -#if BROTLI_SAFE_MEMMOVE - /* For x86 this compiles to the same binary as signle memcpy. - On ARM memcpy is not inlined, so it works slower. - This implementation makes decompression 1% slower than regular one, - and 2% slower than NEON implementation. - */ - uint32_t buffer[4]; - memcpy(buffer, src, 16); - memcpy(dst, buffer, 16); -#elif defined(__ARM_NEON__) - vst1q_u8(dst, vld1q_u8(src)); -#else - /* memcpy is unsafe for overlapping regions and ASAN detects this. - But, because of optimizations, it works exactly as memmove: - copies data to registers first, and then stores them to dst. */ - memcpy(dst, src, 16); -#endif -} - -/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */ -static BROTLI_NOINLINE BrotliResult DecodeVarLenUint8(BrotliState* 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_RESULT_NEEDS_MORE_INPUT; - } - if (bits == 0) { - *value = 0; - return BROTLI_RESULT_SUCCESS; - } - /* No break, transit to the next state. */ - - case BROTLI_STATE_DECODE_UINT8_SHORT: - if (PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) { - s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (bits == 0) { - *value = 1; - s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; - return BROTLI_RESULT_SUCCESS; - } - /* Use output value as a temporary storage. It MUST be persisted. */ - *value = bits; - /* No break, transit to the next state. */ - - case BROTLI_STATE_DECODE_UINT8_LONG: - if (PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) { - s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - *value = (1U << *value) + bits; - s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; - return BROTLI_RESULT_SUCCESS; - - default: - return BROTLI_FAILURE(); - } -} - -/* Decodes a metablock length and flags by reading 2 - 31 bits. */ -static BrotliResult BROTLI_NOINLINE DecodeMetaBlockLength(BrotliState* 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_RESULT_NEEDS_MORE_INPUT; - } - s->is_last_metablock = (uint8_t)bits; - s->meta_block_remaining_len = 0; - s->is_uncompressed = 0; - s->is_metadata = 0; - if (!s->is_last_metablock) { - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES; - break; - } - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY; - /* No break, transit to the next state. */ - - case BROTLI_STATE_METABLOCK_HEADER_EMPTY: - if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (bits) { - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_RESULT_SUCCESS; - } - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES; - /* No break, transit to the next state. */ - - case BROTLI_STATE_METABLOCK_HEADER_NIBBLES: - if (!BrotliSafeReadBits(br, 2, &bits)) { - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - s->size_nibbles = (uint8_t)(bits + 4); - s->loop_counter = 0; - if (bits == 3) { - s->is_metadata = 1; - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_RESERVED; - break; - } - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE; - /* No break, transit to the next state. */ - - case BROTLI_STATE_METABLOCK_HEADER_SIZE: - i = s->loop_counter; - for (; i < s->size_nibbles; ++i) { - if (!BrotliSafeReadBits(br, 4, &bits)) { - s->loop_counter = i; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) { - return BROTLI_FAILURE(); - } - 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. */ - - case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED: - if (!s->is_last_metablock && !s->is_metadata) { - if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - s->is_uncompressed = (uint8_t)bits; - } - ++s->meta_block_remaining_len; - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_RESULT_SUCCESS; - - case BROTLI_STATE_METABLOCK_HEADER_RESERVED: - if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (bits != 0) { - return BROTLI_FAILURE(); - } - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES; - /* No break, transit to the next state. */ - - case BROTLI_STATE_METABLOCK_HEADER_BYTES: - if (!BrotliSafeReadBits(br, 2, &bits)) { - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (bits == 0) { - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_RESULT_SUCCESS; - } - s->size_nibbles = (uint8_t)bits; - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA; - /* No break, transit to the next state. */ - - case BROTLI_STATE_METABLOCK_HEADER_METADATA: - i = s->loop_counter; - for (; i < s->size_nibbles; ++i) { - if (!BrotliSafeReadBits(br, 8, &bits)) { - s->loop_counter = i; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) { - return BROTLI_FAILURE(); - } - s->meta_block_remaining_len |= (int)(bits << (i * 8)); - } - s->substate_metablock_header = - BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED; - break; - - default: - return BROTLI_FAILURE(); - } - } -} - -/* Decodes the Huffman code. - This method doesn't read data from the bit reader, BUT drops the amount of - bits that correspond to the decoded symbol. - bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */ -static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, - const HuffmanCode* table, - BrotliBitReader* br) { - table += bits & HUFFMAN_TABLE_MASK; - if (table->bits > HUFFMAN_TABLE_BITS) { - uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS; - BrotliDropBits(br, HUFFMAN_TABLE_BITS); - table += table->value; - table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits); - } - BrotliDropBits(br, table->bits); - return table->value; -} - -/* Reads and decodes the next Huffman code from bit-stream. - This method peeks 16 bits of input and drops 0 - 15 of them. */ -static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table, - BrotliBitReader* br) { - return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br); -} - -/* 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) { - uint32_t val; - uint32_t available_bits = BrotliGetAvailableBits(br); - if (available_bits == 0) { - if (table->bits == 0) { - *result = table->value; - return 1; - } - return 0; /* 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; - } else { - return 0; /* Not enough bits for the first level. */ - } - } - if (available_bits <= HUFFMAN_TABLE_BITS) { - return 0; /* Not enough bits to move to the second level. */ - } - - /* Speculatively drop HUFFMAN_TABLE_BITS. */ - val = (val & BitMask(table->bits)) >> 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. */ - } - - BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits); - *result = table->value; - return 1; -} - -static BROTLI_INLINE int SafeReadSymbol(const HuffmanCode* table, - BrotliBitReader* br, - uint32_t* result) { - uint32_t val; - if (PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) { - *result = DecodeSymbol(val, table, br); - return 1; - } - return SafeDecodeSymbol(table, br, result); -} - - -/* Makes a look-up in first level Huffman table. Peeks 8 bits. */ -static BROTLI_INLINE void PreloadSymbol(int safe, - const HuffmanCode* table, - BrotliBitReader* br, - uint32_t* bits, - uint32_t* value) { - if (safe) { - return; - } - table += BrotliGetBits(br, HUFFMAN_TABLE_BITS); - *bits = table->bits; - *value = table->value; -} - -/* Decodes the next Huffman code using data prepared by PreloadSymbol. - Reads 0 - 15 bits. Also peeks 8 following bits. */ -static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table, - BrotliBitReader* br, - uint32_t* bits, - uint32_t* value) { - uint32_t result = *value; - if (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)); - BrotliDropBits(br, HUFFMAN_TABLE_BITS); - ext += (val >> HUFFMAN_TABLE_BITS) & mask; - BrotliDropBits(br, ext->bits); - result = ext->value; - } else { - BrotliDropBits(br, *bits); - } - PreloadSymbol(0, table, br, bits, value); - return result; -} - -static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { - uint32_t result = 0; - while (x) { - x >>= 1; - ++result; - } - return result; -} - -/* Reads (s->symbol + 1) symbols. - Totally 1..4 symbols are read, 1..10 bits each. - The list of symbols MUST NOT contain duplicates. - */ -static BrotliResult ReadSimpleHuffmanSymbols(uint32_t alphabet_size, - BrotliState* s) { - /* max_bits == 1..10; symbol == 0..3; 1..40 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))) { - s->sub_loop_counter = i; - s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - if (v >= alphabet_size) { - return BROTLI_FAILURE(); - } - s->symbols_lists_array[i] = (uint16_t)v; - BROTLI_LOG_UINT(s->symbols_lists_array[i]); - ++i; - } - - for (i = 0; i < num_symbols; ++i) { - uint32_t k = i + 1; - for (; k <= num_symbols; ++k) { - if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) { - return BROTLI_FAILURE(); - } - } - } - - return BROTLI_RESULT_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 - */ -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 */ - 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]++; - } - (*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 - B) Update repeat variable - C) Check if operation is feasible (fits alphapet) - D) For each symbol do the same operations as in ProcessSingleCodeLength - - PRECONDITION: code_len == kCodeLengthRepeatCode or kCodeLengthRepeatCode + 1 - */ -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) { - new_len = *prev_code_len; - } - if (*repeat_code_len != new_len) { - *repeat = 0; - *repeat_code_len = new_len; - } - old_repeat = *repeat; - if (*repeat > 0) { - *repeat -= 2; - *repeat <<= code_len - 14U; - } - *repeat += repeat_delta + 3U; - repeat_delta = *repeat - old_repeat; - if (*symbol + repeat_delta > alphabet_size) { - (void)BROTLI_FAILURE(); - *symbol = alphabet_size; - *space = 0xFFFFF; - return; - } - if (*repeat_code_len != 0) { - unsigned last = *symbol + repeat_delta; - int next = next_symbol[*repeat_code_len]; - do { - symbol_lists[next] = (uint16_t)*symbol; - next = (int)*symbol; - } while (++(*symbol) != last); - next_symbol[*repeat_code_len] = next; - *space -= repeat_delta << (15 - *repeat_code_len); - code_length_histo[*repeat_code_len] = (uint16_t) - (code_length_histo[*repeat_code_len] + repeat_delta); - } else { - *symbol += repeat_delta; - } -} - -/* Reads and decodes symbol codelengths. */ -static BrotliResult ReadSymbolCodeLengths( - uint32_t alphabet_size, BrotliState* s) { - BrotliBitReader* br = &s->br; - uint32_t symbol = s->symbol; - uint32_t repeat = s->repeat; - uint32_t space = s->space; - uint32_t prev_code_len = s->prev_code_len; - uint32_t repeat_code_len = s->repeat_code_len; - uint16_t* symbol_lists = s->symbol_lists; - uint16_t* code_length_histo = s->code_length_histo; - int* next_symbol = s->next_symbol; - if (!BrotliWarmupBitReader(br)) { - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - while (symbol < alphabet_size && space > 0) { - const HuffmanCode* p = s->table; - uint32_t code_len; - 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_RESULT_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) { - 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 */ - uint32_t repeat_delta = - (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(code_len - 14U); - BrotliDropBits(br, code_len - 14U); - 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_RESULT_SUCCESS; -} - -static BrotliResult SafeReadSymbolCodeLengths( - uint32_t alphabet_size, BrotliState* s) { - BrotliBitReader* br = &s->br; - while (s->symbol < alphabet_size && s->space > 0) { - const HuffmanCode* p = s->table; - uint32_t code_len; - uint32_t bits = 0; - uint32_t 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); - 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 */ - 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); - 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_RESULT_NEEDS_MORE_INPUT; - } - } - return BROTLI_RESULT_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 BrotliResult ReadCodeLengthCodeLengths(BrotliState* 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) { - const uint8_t code_len_idx = kCodeLengthCodeOrder[i]; - uint32_t ix; - uint32_t v; - if (PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) { - uint32_t available_bits = BrotliGetAvailableBits(br); - if (available_bits != 0) { - ix = BrotliGetBitsUnmasked(br) & 0xF; - } else { - ix = 0; - } - if (kCodeLengthPrefixLength[ix] > available_bits) { - s->sub_loop_counter = i; - s->repeat = num_codes; - s->space = space; - s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - } - v = kCodeLengthPrefixValue[ix]; - BrotliDropBits(br, kCodeLengthPrefixLength[ix]); - s->code_length_code_lengths[code_len_idx] = (uint8_t)v; - BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx); - if (v != 0) { - space = space - (32U >> v); - ++num_codes; - ++s->code_length_histo[v]; - if (space - 1U >= 32U) { - /* space is 0 or wrapped around */ - break; - } - } - } - if (!(num_codes == 1 || space == 0)) { - return BROTLI_FAILURE(); - } - return BROTLI_RESULT_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. - - 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 BrotliResult ReadHuffmanCode(uint32_t alphabet_size, - HuffmanCode* table, - uint32_t* opt_table_size, - BrotliState* 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_RESULT_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. */ - - 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_RESULT_NEEDS_MORE_INPUT; - } - s->sub_loop_counter = 0; - /* No break, transit to the next state. */ - case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { - BrotliResult result = ReadSimpleHuffmanSymbols(alphabet_size, s); - if (result != BROTLI_RESULT_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_RESULT_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_RESULT_SUCCESS; - } - -Complex: /* Decode Huffman-coded code lengths. */ - case BROTLI_STATE_HUFFMAN_COMPLEX: { - uint32_t i; - BrotliResult result = ReadCodeLengthCodeLengths(s); - if (result != BROTLI_RESULT_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; - } - - 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; - BrotliResult result = ReadSymbolCodeLengths(alphabet_size, s); - if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) { - result = SafeReadSymbolCodeLengths(alphabet_size, s); - } - if (result != BROTLI_RESULT_SUCCESS) { - return result; - } - - if (s->space != 0) { - BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", s->space)); - return BROTLI_FAILURE(); - } - 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_RESULT_SUCCESS; - } - - default: - return BROTLI_FAILURE(); - } -} - -/* Decodes a block length by reading 3..39 bits. */ -static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table, - BrotliBitReader* br) { - uint32_t code; - uint32_t nbits; - code = ReadSymbol(table, br); - 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) { - uint32_t index; - if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) { - if (!SafeReadSymbol(table, br, &index)) { - return 0; - } - } else { - index = s->block_length_index; - } - { - uint32_t bits; - 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; - } - *result = kBlockLengthPrefixCode[index].offset + bits; - s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; - return 1; - } -} - -/* Transform: - 1) initialize list L with values 0, 1,... 255 - 2) For each input element X: - 2.1) let Y = L[X] - 2.2) remove X-th element from L - 2.3) prepend Y to L - 2.4) append Y to output - - In most cases max(Y) <= 7, so most of L remains intact. - To reduce the cost of initialization, we reuse L, remember the upper bound - of Y values, and reinitialize only first elements in L. - - Most of input values are 0 and 1. To reduce number of branches, we replace - inner for loop with do-while. - */ -static BROTLI_NOINLINE void InverseMoveToFrontTransform(uint8_t* v, - uint32_t v_len, BrotliState* state) { - /* Reinitialize elements that could have been changed. */ - uint32_t i = 4; - uint32_t upper_bound = state->mtf_upper_bound; - uint8_t* mtf = state->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; - do { - pattern += 0x04040404; /* Advance all 4 values by 4. */ - *(uint32_t*)(mtf + i) = pattern; - i += 4; - } 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]; - upper_bound |= v[i]; - v[i] = value; - do { - index--; - mtf[index + 1] = mtf[index]; - } while (index > 0); - mtf[0] = value; - } - /* Remember amount of elements to be reinitialized. */ - state->mtf_upper_bound = upper_bound; -} - - -/* Decodes a series of Huffman table using ReadHuffmanCode function. */ -static BrotliResult HuffmanTreeGroupDecode(HuffmanTreeGroup* group, - BrotliState* s) { - if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) { - s->next = group->codes; - s->htree_index = 0; - s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP; - } - while (s->htree_index < group->num_htrees) { - uint32_t table_size; - BrotliResult result = - ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s); - if (result != BROTLI_RESULT_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_RESULT_SUCCESS; -} - -/* Decodes a context map. - Decoding is done in 4 phases: - 1) Read auxiliary information (6..16 bits) and allocate memory. - In case of trivial context map, decoding is finished at this phase. - 2) Decode Huffman table using ReadHuffmanCode function. - This table will be used for reading context map items. - 3) Read context map items; "0" values could be run-length encoded. - 4) Optionally, apply InverseMoveToFront transform to the resulting map. - */ -static BrotliResult DecodeContextMap(uint32_t context_map_size, - uint32_t* num_htrees, - uint8_t** context_map_arg, - BrotliState* s) { - BrotliBitReader* br = &s->br; - BrotliResult result = BROTLI_RESULT_SUCCESS; - - switch((int)s->substate_context_map) { - case BROTLI_STATE_CONTEXT_MAP_NONE: - result = DecodeVarLenUint8(s, br, num_htrees); - if (result != BROTLI_RESULT_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); - if (*context_map_arg == 0) { - return BROTLI_FAILURE(); - } - if (*num_htrees <= 1) { - memset(*context_map_arg, 0, (size_t)context_map_size); - return BROTLI_RESULT_SUCCESS; - } - s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; - /* No break, continue to next state. */ - 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_RESULT_NEEDS_MORE_INPUT; - } - if ((bits & 1) != 0) { /* Use RLE for zeroes. */ - s->max_run_length_prefix = (bits >> 1) + 1; - BrotliDropBits(br, 5); - } else { - s->max_run_length_prefix = 0; - BrotliDropBits(br, 1); - } - 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, - s->context_map_table, NULL, s); - if (result != BROTLI_RESULT_SUCCESS) return result; - s->code = 0xFFFF; - s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE; - /* No break, continue to next state. */ - 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_RESULT_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; - } -rleCode: - { - uint32_t reps; - if (!BrotliSafeReadBits(br, code, &reps)) { - s->code = code; - s->context_index = context_index; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - reps += 1U << code; - BROTLI_LOG_UINT(reps); - if (context_index + reps > context_map_size) { - return BROTLI_FAILURE(); - } - do { - context_map[context_index++] = 0; - } while (--reps); - } - } - /* No break, continue to next state. */ - } - 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_RESULT_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_RESULT_SUCCESS; - } - } - - return BROTLI_FAILURE(); -} - -/* Decodes a command or literal and updates block type ringbuffer. - Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe, - BrotliState* s, int tree_type) { - uint32_t max_block_type = s->num_block_types[tree_type]; - int tree_offset = tree_type * BROTLI_HUFFMAN_MAX_TABLE_SIZE; - const HuffmanCode* type_tree = &s->block_type_trees[tree_offset]; - const HuffmanCode* len_tree = &s->block_len_trees[tree_offset]; - BrotliBitReader* br = &s->br; - uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2]; - uint32_t block_type; - - /* 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 (!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; - } - } - - if (block_type == 1) { - block_type = ringbuffer[1] + 1; - } else if (block_type == 0) { - block_type = ringbuffer[0]; - } else { - block_type -= 2; - } - if (block_type >= max_block_type) { - block_type -= max_block_type; - } - ringbuffer[0] = ringbuffer[1]; - ringbuffer[1] = block_type; - return 1; -} - -/* Decodes the block type and updates the state for literal context. - Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeLiteralBlockSwitchInternal(int safe, - BrotliState* s) { - uint8_t context_mode; - uint32_t context_offset; - if (!DecodeBlockTypeAndLength(safe, s, 0)) { - return 0; - } - context_offset = s->block_type_rb[1] << kLiteralContextBits; - s->context_map_slice = s->context_map + context_offset; - s->literal_htree_index = s->context_map_slice[0]; - s->literal_htree = s->literal_hgroup.htrees[s->literal_htree_index]; - context_mode = s->context_modes[s->block_type_rb[1]]; - s->context_lookup1 = &kContextLookup[kContextLookupOffsets[context_mode]]; - s->context_lookup2 = &kContextLookup[kContextLookupOffsets[context_mode + 1]]; - return 1; -} - -static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliState* s) { - DecodeLiteralBlockSwitchInternal(0, s); -} - -static int BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(BrotliState* s) { - return DecodeLiteralBlockSwitchInternal(1, s); -} - -/* Block switch for insert/copy length. - Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeCommandBlockSwitchInternal(int safe, - BrotliState* s) { - if (!DecodeBlockTypeAndLength(safe, s, 1)) { - return 0; - } - s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]]; - return 1; -} - -static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliState* s) { - DecodeCommandBlockSwitchInternal(0, s); -} -static int BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(BrotliState* s) { - return DecodeCommandBlockSwitchInternal(1, s); -} - -/* Block switch for distance codes. - Reads 3..54 bits. */ -static BROTLI_INLINE int DecodeDistanceBlockSwitchInternal(int safe, - BrotliState* s) { - if (!DecodeBlockTypeAndLength(safe, s, 2)) { - return 0; - } - s->dist_context_map_slice = - s->dist_context_map + (s->block_type_rb[5] << kDistanceContextBits); - s->dist_htree_index = s->dist_context_map_slice[s->distance_context]; - return 1; -} - -static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliState* s) { - DecodeDistanceBlockSwitchInternal(0, s); -} - -static int BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(BrotliState* s) { - return DecodeDistanceBlockSwitchInternal(1, s); -} - -static BrotliResult 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); - 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 num_written = *available_out; - if (num_written > to_write) { - num_written = to_write; - } - if (s->meta_block_remaining_len < 0) { - return BROTLI_FAILURE(); - } - 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 += (size_t)num_written; - *total_out = s->partial_pos_out; - if (num_written < to_write) { - return BROTLI_RESULT_NEEDS_MORE_OUTPUT; - } - return BROTLI_RESULT_SUCCESS; -} - -static BrotliResult BROTLI_NOINLINE CopyUncompressedBlockToOutput( - size_t* available_out, uint8_t** next_out, size_t* total_out, - BrotliState* s) { - /* State machine */ - for (;;) { - switch (s->substate_uncompressed) { - case BROTLI_STATE_UNCOMPRESSED_NONE: { - int nbytes = (int)BrotliGetRemainingBytes(&s->br); - if (nbytes > s->meta_block_remaining_len) { - nbytes = s->meta_block_remaining_len; - } - if (s->pos + nbytes > s->ringbuffer_size) { - nbytes = s->ringbuffer_size - s->pos; - } - /* Copy remaining bytes from s->br.buf_ to ringbuffer. */ - 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->meta_block_remaining_len == 0) { - return BROTLI_RESULT_SUCCESS; - } - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE; - /*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/ - /* No break, continue to next state */ - } - case BROTLI_STATE_UNCOMPRESSED_WRITE: { - BrotliResult result = WriteRingBuffer( - available_out, next_out, total_out, s); - if (result != BROTLI_RESULT_SUCCESS) { - return result; - } - s->pos = 0; - s->rb_roundtrips++; - s->max_distance = s->max_backward_distance; - s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; - break; - } - } - } - return BROTLI_FAILURE(); -} - -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_RESULT_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); -} - -/* Allocates the smallest feasible ring buffer. - - If we know the data size is small, do not allocate more ringbuffer - size than needed to reduce memory usage. - - This method is called before the first non-empty non-metadata block is - processed. When this method is called, metablock size and flags MUST be - decoded. -*/ -static int BROTLI_NOINLINE BrotliAllocateRingBuffer(BrotliState* s, - BrotliBitReader* br) { - /* 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; - int is_last = s->is_last_metablock; - s->ringbuffer_size = 1 << s->window_bits; - - 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; - } - } - } - - /* We need at least 2 bytes of ring buffer size to get the last two - bytes for context from there */ - if (is_last) { - while (s->ringbuffer_size >= s->meta_block_remaining_len * 2 - && s->ringbuffer_size > 32) { - s->ringbuffer_size >>= 1; - } - } - - /* But make it fit the custom dictionary if there is one. */ - while (s->ringbuffer_size < s->custom_dict_size) { - s->ringbuffer_size <<= 1; - } - - s->ringbuffer_mask = s->ringbuffer_size - 1; - s->ringbuffer = (uint8_t*)BROTLI_ALLOC(s, (size_t)(s->ringbuffer_size + - kRingBufferWriteAheadSlack + kBrotliMaxDictionaryWordLength)); - if (s->ringbuffer == 0) { - return 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); - } - - return 1; -} - -/* Reads 1..256 2-bit context modes. */ -static BrotliResult ReadContextModes(BrotliState* s) { - BrotliBitReader* br = &s->br; - int i = s->loop_counter; - - while (i < (int)s->num_block_types[0]) { - uint32_t bits; - if (!BrotliSafeReadBits(br, 2, &bits)) { - s->loop_counter = i; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - s->context_modes[i] = (uint8_t)(bits << 1); - BROTLI_LOG_ARRAY_INDEX(s->context_modes, i); - i++; - } - return BROTLI_RESULT_SUCCESS; -} - -static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliState* s) { - if (s->distance_code == 0) { - --s->dist_rb_idx; - s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; - } 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; - int v = (s->dist_rb_idx + - (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3; - s->distance_code = s->dist_rb[v]; - v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3; - if ((distance_code & 0x3) != 0) { - s->distance_code += v; - } 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; - } - } - } -} - -static BROTLI_INLINE int 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; - } -} - -/* Precondition: s->distance_code < 0 */ -static BROTLI_INLINE int ReadDistanceInternal(int safe, - BrotliState* s, BrotliBitReader* br) { - int distval; - BrotliBitReaderState memento; - HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; - if (!safe) { - s->distance_code = (int)ReadSymbol(distance_tree, br); - } else { - uint32_t code; - BrotliBitReaderSaveState(br, &memento); - if (!SafeReadSymbol(distance_tree, br, &code)) { - return 0; - } - 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) { - TakeDistanceFromRingBuffer(s); - --s->block_length[2]; - return 1; - } - distval = s->distance_code - (int)s->num_direct_distance_codes; - if (distval >= 0) { - uint32_t nbits; - int postfix; - int offset; - if (!safe && (s->distance_postfix_bits == 0)) { - nbits = ((uint32_t)distval >> 1) + 1; - offset = ((2 + (distval & 1)) << nbits) - 4; - 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 */ - 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. */ - BrotliBitReaderRestoreState(br, &memento); - return 0; - } - } else { - bits = BrotliReadBits(br, nbits); - } - offset = ((2 + (distval & 1)) << nbits) - 4; - s->distance_code = (int)s->num_direct_distance_codes + - ((offset + (int)bits) << s->distance_postfix_bits) + postfix; - } - } - s->distance_code = s->distance_code - NUM_DISTANCE_SHORT_CODES + 1; - --s->block_length[2]; - return 1; -} - -static BROTLI_INLINE void ReadDistance(BrotliState* s, BrotliBitReader* br) { - ReadDistanceInternal(0, s, br); -} - -static BROTLI_INLINE int SafeReadDistance(BrotliState* s, BrotliBitReader* br) { - return ReadDistanceInternal(1, s, br); -} - -static BROTLI_INLINE int ReadCommandInternal(int safe, - BrotliState* s, BrotliBitReader* br, int* insert_length) { - uint32_t cmd_code; - uint32_t insert_len_extra = 0; - uint32_t copy_length; - CmdLutElement v; - BrotliBitReaderState memento; - if (!safe) { - cmd_code = ReadSymbol(s->htree_command, br); - } else { - BrotliBitReaderSaveState(br, &memento); - if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) { - return 0; - } - } - v = kCmdLut[cmd_code]; - s->distance_code = v.distance_code; - s->distance_context = v.context; - 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)) { - insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits); - } - copy_length = BrotliReadBits(br, v.copy_len_extra_bits); - } else { - if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) || - !SafeReadBits(br, v.copy_len_extra_bits, ©_length)) { - BrotliBitReaderRestoreState(br, &memento); - return 0; - } - } - s->copy_length = (int)copy_length + v.copy_len_offset; - --s->block_length[1]; - *insert_length += (int)insert_len_extra; - return 1; -} - -static BROTLI_INLINE void ReadCommand(BrotliState* s, BrotliBitReader* br, - int* insert_length) { - ReadCommandInternal(0, s, br, insert_length); -} - -static BROTLI_INLINE int SafeReadCommand(BrotliState* s, BrotliBitReader* br, - int* insert_length) { - return ReadCommandInternal(1, s, br, insert_length); -} - -static BROTLI_INLINE int WarmupBitReader(int safe, BrotliBitReader* const br) { - if (safe) { - return 1; - } - return BrotliWarmupBitReader(br); -} - -static BROTLI_INLINE int CheckInputAmount(int safe, - BrotliBitReader* const br, size_t num) { - if (safe) { - return 1; - } - return BrotliCheckInputAmount(br, num); -} - -#define BROTLI_SAFE(METHOD) { \ - if (safe) { \ - if (! Safe ## METHOD ) { \ - result = BROTLI_RESULT_NEEDS_MORE_INPUT; \ - goto saveStateAndReturn; \ - } \ - } else { \ - METHOD ; \ - } \ -} - -static BROTLI_INLINE BrotliResult ProcessCommandsInternal(int safe, - BrotliState* s) { - int pos = s->pos; - int i = s->loop_counter; - BrotliResult result = BROTLI_RESULT_SUCCESS; - BrotliBitReader* br = &s->br; - - if (!CheckInputAmount(safe, br, 28) || !WarmupBitReader(safe, br)) { - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - - /* Jump into state machine. */ - if (s->state == BROTLI_STATE_COMMAND_BEGIN) { - goto CommandBegin; - } else if (s->state == BROTLI_STATE_COMMAND_INNER) { - goto CommandInner; - } else if (s->state == BROTLI_STATE_COMMAND_POST_DECODE_LITERALS) { - goto CommandPostDecodeLiterals; - } else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) { - goto CommandPostWrapCopy; - } else { - return BROTLI_FAILURE(); - } - -CommandBegin: - if (safe) { - s->state = BROTLI_STATE_COMMAND_BEGIN; - } - if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */ - s->state = BROTLI_STATE_COMMAND_BEGIN; - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - if (PREDICT_FALSE(s->block_length[1] == 0)) { - BROTLI_SAFE(DecodeCommandBlockSwitch(s)); - goto CommandBegin; - } - /* Read the insert/copy length in the command */ - BROTLI_SAFE(ReadCommand(s, br, &i)); - BROTLI_LOG_UINT(i); - BROTLI_LOG_UINT(s->copy_length); - BROTLI_LOG_UINT(s->distance_code); - if (i == 0) { - goto CommandPostDecodeLiterals; - } - s->meta_block_remaining_len -= i; - -CommandInner: - if (safe) { - s->state = BROTLI_STATE_COMMAND_INNER; - } - /* 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 */ - s->state = BROTLI_STATE_COMMAND_INNER; - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - if (PREDICT_FALSE(s->block_length[0] == 0)) { - BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); - PreloadSymbol(safe, s->literal_htree, br, &bits, &value); - } - if (!safe) { - s->ringbuffer[pos] = (uint8_t)ReadPreloadedSymbol( - s->literal_htree, br, &bits, &value); - } else { - uint32_t literal; - if (!SafeReadSymbol(s->literal_htree, br, &literal)) { - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - s->ringbuffer[pos] = (uint8_t)literal; - } - --s->block_length[0]; - BROTLI_LOG_UINT(s->literal_htree_index); - BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos); - ++pos; - if (PREDICT_FALSE(pos == s->ringbuffer_size)) { - s->state = BROTLI_STATE_COMMAND_INNER_WRITE; - --i; - goto saveStateAndReturn; - } - } while (--i != 0); - } else { - uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask]; - uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask]; - do { - const HuffmanCode* hc; - uint8_t context; - if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */ - s->state = BROTLI_STATE_COMMAND_INNER; - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - if (PREDICT_FALSE(s->block_length[0] == 0)) { - BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); - } - context = s->context_lookup1[p1] | s->context_lookup2[p2]; - BROTLI_LOG_UINT(context); - hc = s->literal_hgroup.htrees[s->context_map_slice[context]]; - p2 = p1; - if (!safe) { - p1 = (uint8_t)ReadSymbol(hc, br); - } else { - uint32_t literal; - if (!SafeReadSymbol(hc, br, &literal)) { - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - p1 = (uint8_t)literal; - } - s->ringbuffer[pos] = p1; - --s->block_length[0]; - 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)) { - s->state = BROTLI_STATE_COMMAND_INNER_WRITE; - --i; - goto saveStateAndReturn; - } - } while (--i != 0); - } - if (s->meta_block_remaining_len <= 0) { - s->state = BROTLI_STATE_METABLOCK_DONE; - goto saveStateAndReturn; - } - -CommandPostDecodeLiterals: - if (safe) { - s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS; - } - if (s->distance_code >= 0) { - --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)); - } - BROTLI_SAFE(ReadDistance(s, br)); -postReadDistance: - BROTLI_LOG_UINT(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; - } - } - i = s->copy_length; - /* Apply copy of LZ77 back-reference, or static dictionary reference if - the distance is larger than the max LZ77 distance */ - if (s->distance_code > s->max_distance) { - if (i >= kBrotliMinDictionaryWordLength && - i <= kBrotliMaxDictionaryWordLength) { - int offset = kBrotliDictionaryOffsetsByLength[i]; - int word_id = s->distance_code - s->max_distance - 1; - uint32_t shift = kBrotliDictionarySizeBitsByLength[i]; - int mask = (int)BitMask(shift); - int word_idx = word_id & mask; - int transform_idx = word_id >> shift; - offset += word_idx * i; - if (transform_idx < kNumTransforms) { - const uint8_t* word = &kBrotliDictionary[offset]; - int len = i; - if (transform_idx == 0) { - memcpy(&s->ringbuffer[pos], word, (size_t)len); - } else { - len = TransformDictionaryWord( - &s->ringbuffer[pos], word, len, transform_idx); - } - 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; - } - } 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(); - } - } 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(); - } - } else { - const uint8_t *ringbuffer_end_minus_copy_length = - s->ringbuffer_end - i; - uint8_t* copy_src = &s->ringbuffer[ - (pos - s->distance_code) & s->ringbuffer_mask]; - uint8_t* copy_dst = &s->ringbuffer[pos]; - /* 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; - if (PREDICT_FALSE(s->meta_block_remaining_len < 0)) { - 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(); - } - /* There is 128+ bytes of slack in the ringbuffer 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. - */ - memmove16(copy_dst, copy_src); - /* Now check if the copy extends over the ringbuffer end, - or if the copy overlaps with itself, if yes, do wrap-copy. */ - if (copy_src < copy_dst) { - if (copy_dst >= ringbuffer_end_minus_copy_length) { - goto CommandPostWrapCopy; - } - if (copy_src + i > copy_dst) { - goto postSelfintersecting; - } - } else { - if (copy_src >= ringbuffer_end_minus_copy_length) { - goto CommandPostWrapCopy; - } - if (copy_dst + i > copy_src) { - goto postSelfintersecting; - } - } - pos += i; - if (i > 16) { - if (i > 32) { - memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16)); - } else { - /* This branch covers about 45% cases. - Fixed size short copy allows more compiler optimizations. */ - memmove16(copy_dst + 16, copy_src + 16); - } - } - } - if (s->meta_block_remaining_len <= 0) { - /* Next metablock, if any */ - s->state = BROTLI_STATE_METABLOCK_DONE; - goto saveStateAndReturn; - } else { - goto CommandBegin; - } -postSelfintersecting: - while (--i >= 0) { - s->ringbuffer[pos] = - s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask]; - ++pos; - } - if (s->meta_block_remaining_len <= 0) { - /* Next metablock, if any */ - s->state = BROTLI_STATE_METABLOCK_DONE; - goto saveStateAndReturn; - } else { - goto CommandBegin; - } - -CommandPostWrapCopy: - s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY; - while (--i >= 0) { - s->ringbuffer[pos] = - s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask]; - ++pos; - if (pos == s->ringbuffer_size) { - /*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/ - s->state = BROTLI_STATE_COMMAND_POST_WRITE_2; - goto saveStateAndReturn; - } - } - if (s->meta_block_remaining_len <= 0) { - /* Next metablock, if any */ - s->state = BROTLI_STATE_METABLOCK_DONE; - goto saveStateAndReturn; - } else { - goto CommandBegin; - } - -saveStateAndReturn: - s->pos = pos; - s->loop_counter = i; - return result; -} - -#undef BROTLI_SAFE - -static BROTLI_NOINLINE BrotliResult ProcessCommands(BrotliState* s) { - return ProcessCommandsInternal(0, s); -} - -static BROTLI_NOINLINE BrotliResult SafeProcessCommands(BrotliState* 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; - 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); - *decoded_size = total_out; - BrotliStateCleanup(&s); - if (result != BROTLI_RESULT_SUCCESS) { - result = BROTLI_RESULT_ERROR; - } - return result; -} - -BrotliResult BrotliDecompress(BrotliInput input, BrotliOutput output) { - BrotliState s; - BrotliResult result; - BrotliStateInit(&s); - result = BrotliDecompressStreaming(input, output, 1, &s); - if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) { - /* Not ok: it didn't finish even though this is a non-streaming function. */ - result = BROTLI_FAILURE(); - } - BrotliStateCleanup(&s); - return result; -} - -BrotliResult BrotliDecompressBufferStreaming(size_t* available_in, - const uint8_t** next_in, - int finish, - size_t* available_out, - uint8_t** next_out, - size_t* total_out, - BrotliState* s) { - BrotliResult result = BrotliDecompressStream(available_in, next_in, - available_out, next_out, total_out, s); - if (finish && result == BROTLI_RESULT_NEEDS_MORE_INPUT) { - result = BROTLI_FAILURE(); - } - return result; -} - -BrotliResult BrotliDecompressStreaming(BrotliInput input, BrotliOutput output, - int finish, BrotliState* s) { - const size_t kBufferSize = 65536; - BrotliResult result; - uint8_t* input_buffer; - uint8_t* output_buffer; - size_t avail_in; - const uint8_t* next_in; - size_t total_out; - - if (s->legacy_input_buffer == 0) { - s->legacy_input_buffer = (uint8_t*)BROTLI_ALLOC(s, kBufferSize); - } - if (s->legacy_output_buffer == 0) { - s->legacy_output_buffer = (uint8_t*)BROTLI_ALLOC(s, kBufferSize); - } - if (s->legacy_input_buffer == 0 || s->legacy_output_buffer == 0) { - return BROTLI_FAILURE(); - } - input_buffer = s->legacy_input_buffer; - output_buffer = s->legacy_output_buffer; - - /* Push remaining output. */ - if (s->legacy_output_len > s->legacy_output_pos) { - size_t to_write = s->legacy_output_len - s->legacy_output_pos; - int num_written = BrotliWrite( - output, output_buffer + s->legacy_output_pos, to_write); - if (num_written < 0) { - return BROTLI_FAILURE(); - } - s->legacy_output_pos += (size_t)num_written; - if ((size_t)num_written < to_write) { - return BROTLI_RESULT_NEEDS_MORE_OUTPUT; - } - } - s->legacy_output_pos = 0; - - avail_in = s->legacy_input_len - s->legacy_input_pos; - next_in = input_buffer + s->legacy_input_pos; - - while (1) { - size_t to_write; - int num_written; - size_t avail_out = kBufferSize; - uint8_t* next_out = output_buffer; - result = BrotliDecompressStream(&avail_in, &next_in, - &avail_out, &next_out, &total_out, s); - s->legacy_input_pos = (size_t)(next_out - input_buffer); - to_write = (size_t)(next_out - output_buffer); - num_written = BrotliWrite(output, output_buffer, to_write); - if (num_written < 0) { - return BROTLI_FAILURE(); - } - if ((size_t)num_written < to_write) { - s->legacy_output_len = to_write; - s->legacy_output_pos = (size_t)num_written; - return BROTLI_RESULT_NEEDS_MORE_OUTPUT; - } - if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) { - int num_read = BrotliRead(input, input_buffer, kBufferSize); - if (num_read < 0 || (num_read == 0 && finish)) { - return BROTLI_FAILURE(); - } - if (num_read == 0) { - s->legacy_input_len = 0; - s->legacy_input_pos = 0; - return BROTLI_RESULT_NEEDS_MORE_INPUT; - } - avail_in = (size_t)num_read; - next_in = input_buffer; - s->legacy_input_len = avail_in; - s->legacy_input_pos = 0; - } else if (result != BROTLI_RESULT_NEEDS_MORE_OUTPUT) { - /* Success or failure. */ - return result; - } - } -} - -/* Invariant: input stream is never overconsumed: - * invalid input implies that the whole stream is invalid -> any amount of - input could be read and discarded - * when result is "needs more input", then at leat one more byte is REQUIRED - to complete decoding; all input data MUST be consumed by decoder, so - client could swap the input buffer - * when result is "needs more output" decoder MUST ensure that it doesn't - hold more than 7 bits in bit reader; this saves client from swapping input - buffer ahead of time - * when result is "success" decoder MUST return all unused data back to input - buffer; this is possible because the invariant is 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) { - BrotliResult result = BROTLI_RESULT_SUCCESS; - BrotliBitReader* br = &s->br; - 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_RESULT_NEEDS_MORE_INPUT; - br->next_in = &s->buffer.u8[0]; - } - /* State machine */ - for (;;) { - if (result != BROTLI_RESULT_SUCCESS) { /* Error | needs more input/output */ - if (result == BROTLI_RESULT_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 - is expanded byte-by-byte until it is enough to complete read. */ - s->buffer_length = 0; - /* Switch to input stream and restart. */ - result = BROTLI_RESULT_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_RESULT_SUCCESS; - s->buffer.u8[s->buffer_length] = **next_in; - s->buffer_length++; - br->avail_in = s->buffer_length; - (*next_in)++; - (*available_in)--; - /* Retry with more data in buffer. */ - continue; - } - /* Can't finish reading and no more input.*/ - break; - } 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; - while (*available_in) { - s->buffer.u8[s->buffer_length] = **next_in; - s->buffer_length++; - (*next_in)++; - (*available_in)--; - } - break; - } - /* Unreachable. */ - } - - /* Fail or needs more output. */ - - 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.*/ - 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. */ - BrotliBitReaderUnload(br); - *available_in = br->avail_in; - *next_in = br->next_in; - } - break; - } - switch (s->state) { - case BROTLI_STATE_UNINITED: - /* Prepare to the first read. */ - if (!BrotliWarmupBitReader(br)) { - result = BROTLI_RESULT_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(); - break; - } - s->max_backward_distance = (1 << s->window_bits) - 16; - s->max_backward_distance_minus_custom_dict_size = - s->max_backward_distance - s->custom_dict_size; - - /* Allocate memory for both block_type_trees and block_len_trees. */ - s->block_type_trees = (HuffmanCode*)BROTLI_ALLOC(s, - 6 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode)); - if (s->block_type_trees == 0) { - result = BROTLI_FAILURE(); - break; - } - s->block_len_trees = s->block_type_trees + - 3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE; - - s->state = BROTLI_STATE_METABLOCK_BEGIN; - /* No break, continue to next state */ - case BROTLI_STATE_METABLOCK_BEGIN: - BrotliStateMetablockBegin(s); - BROTLI_LOG_UINT(s->pos); - s->state = BROTLI_STATE_METABLOCK_HEADER; - /* No break, continue to next state */ - case BROTLI_STATE_METABLOCK_HEADER: - result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */ - if (result != BROTLI_RESULT_SUCCESS) { - break; - } - BROTLI_LOG_UINT(s->is_last_metablock); - BROTLI_LOG_UINT(s->meta_block_remaining_len); - BROTLI_LOG_UINT(s->is_metadata); - BROTLI_LOG_UINT(s->is_uncompressed); - if (s->is_metadata || s->is_uncompressed) { - if (!BrotliJumpToByteBoundary(br)) { - result = BROTLI_FAILURE(); - break; - } - } - if (s->is_metadata) { - s->state = BROTLI_STATE_METADATA; - break; - } - if (s->meta_block_remaining_len == 0) { - s->state = BROTLI_STATE_METABLOCK_DONE; - break; - } - if (!s->ringbuffer) { - if (!BrotliAllocateRingBuffer(s, br)) { - result = BROTLI_FAILURE(); - break; - } - } - if (s->is_uncompressed) { - s->state = BROTLI_STATE_UNCOMPRESSED; - break; - } - 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_RESULT_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_RESULT_NEEDS_MORE_INPUT; - break; - } - } - if (result == BROTLI_RESULT_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; - break; - } - /* Reads 1..11 bits. */ - result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]); - if (result != BROTLI_RESULT_SUCCESS) { - break; - } - s->num_block_types[s->loop_counter]++; - BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]); - if (s->num_block_types[s->loop_counter] < 2) { - s->loop_counter++; - break; - } - s->state = BROTLI_STATE_HUFFMAN_CODE_1; - /* No break, continue to next state */ - case BROTLI_STATE_HUFFMAN_CODE_1: { - int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_TABLE_SIZE; - result = ReadHuffmanCode(s->num_block_types[s->loop_counter] + 2, - &s->block_type_trees[tree_offset], NULL, s); - if (result != BROTLI_RESULT_SUCCESS) break; - s->state = BROTLI_STATE_HUFFMAN_CODE_2; - /* No break, continue to next state */ - } - case BROTLI_STATE_HUFFMAN_CODE_2: { - int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_TABLE_SIZE; - result = ReadHuffmanCode(kNumBlockLengthCodes, - &s->block_len_trees[tree_offset], NULL, s); - if (result != BROTLI_RESULT_SUCCESS) break; - s->state = BROTLI_STATE_HUFFMAN_CODE_3; - /* No break, continue to next state */ - } - case BROTLI_STATE_HUFFMAN_CODE_3: { - int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_TABLE_SIZE; - if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter], - &s->block_len_trees[tree_offset], br)) { - result = BROTLI_RESULT_NEEDS_MORE_INPUT; - break; - } - BROTLI_LOG_UINT(s->block_length[s->loop_counter]); - s->loop_counter++; - s->state = BROTLI_STATE_HUFFMAN_CODE_0; - break; - } - case BROTLI_STATE_METABLOCK_HEADER_2: { - uint32_t bits; - if (!BrotliSafeReadBits(br, 6, &bits)) { - result = BROTLI_RESULT_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); - 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]); - if (s->context_modes == 0) { - result = BROTLI_FAILURE(); - break; - } - s->loop_counter = 0; - s->state = BROTLI_STATE_CONTEXT_MODES; - /* No break, continue to next state */ - } - case BROTLI_STATE_CONTEXT_MODES: - result = ReadContextModes(s); - if (result != BROTLI_RESULT_SUCCESS) { - break; - } - s->state = BROTLI_STATE_CONTEXT_MAP_1; - /* No break, continue to next state */ - case BROTLI_STATE_CONTEXT_MAP_1: { - uint32_t j; - result = DecodeContextMap(s->num_block_types[0] << kLiteralContextBits, - &s->num_literal_htrees, &s->context_map, s); - if (result != BROTLI_RESULT_SUCCESS) { - break; - } - s->trivial_literal_context = 1; - for (j = 0; j < s->num_block_types[0] << kLiteralContextBits; j++) { - if (s->context_map[j] != j >> kLiteralContextBits) { - s->trivial_literal_context = 0; - break; - } - } - 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_RESULT_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 BROTLI_FAILURE(); - } - } - 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; - } - result = HuffmanTreeGroupDecode(hgroup, s); - } - if (result != BROTLI_RESULT_SUCCESS) break; - s->loop_counter++; - if (s->loop_counter >= 3) { - uint8_t context_mode = s->context_modes[s->block_type_rb[1]]; - s->context_map_slice = s->context_map; - s->dist_context_map_slice = s->dist_context_map; - s->context_lookup1 = - &kContextLookup[kContextLookupOffsets[context_mode]]; - s->context_lookup2 = - &kContextLookup[kContextLookupOffsets[context_mode + 1]]; - s->htree_command = s->insert_copy_hgroup.htrees[0]; - s->literal_htree = s->literal_hgroup.htrees[s->literal_htree_index]; - s->state = BROTLI_STATE_COMMAND_BEGIN; - } - break; - case BROTLI_STATE_COMMAND_BEGIN: - case BROTLI_STATE_COMMAND_INNER: - case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS: - case BROTLI_STATE_COMMAND_POST_WRAP_COPY: - result = ProcessCommands(s); - if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) { - result = SafeProcessCommands(s); - } - break; - case BROTLI_STATE_COMMAND_INNER_WRITE: - case BROTLI_STATE_COMMAND_POST_WRITE_1: - case BROTLI_STATE_COMMAND_POST_WRITE_2: - result = WriteRingBuffer(available_out, next_out, total_out, s); - if (result != BROTLI_RESULT_SUCCESS) { - break; - } - s->pos -= s->ringbuffer_size; - s->rb_roundtrips++; - 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 */ - s->state = BROTLI_STATE_METABLOCK_DONE; - } else { - s->state = BROTLI_STATE_COMMAND_BEGIN; - } - break; - } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) { - s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY; - } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */ - if (s->loop_counter == 0) { - if (s->meta_block_remaining_len <= 0) { - s->state = BROTLI_STATE_METABLOCK_DONE; - } else { - s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS; - } - break; - } - s->state = BROTLI_STATE_COMMAND_INNER; - } - break; - case BROTLI_STATE_METABLOCK_DONE: - BrotliStateCleanupAfterMetablock(s); - if (!s->is_last_metablock) { - s->state = BROTLI_STATE_METABLOCK_BEGIN; - break; - } - if (!BrotliJumpToByteBoundary(br)) { - result = BROTLI_FAILURE(); - } - if (s->buffer_length == 0) { - BrotliBitReaderUnload(br); - *available_in = br->avail_in; - *next_in = br->next_in; - } - s->state = BROTLI_STATE_DONE; - /* No break, continue to next state */ - case BROTLI_STATE_DONE: - if (s->ringbuffer != 0) { - result = WriteRingBuffer(available_out, next_out, total_out, s); - if (result != BROTLI_RESULT_SUCCESS) { - break; - } - } - return result; - } - } - return result; -} - -void BrotliSetCustomDictionary( - size_t size, const uint8_t* dict, BrotliState* s) { - s->custom_dict = dict; - s->custom_dict_size = (int) size; -} - - -#if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ -#endif