diff options
Diffstat (limited to 'brotli/dec/decode.c')
| -rw-r--r-- | brotli/dec/decode.c | 719 |
1 files changed, 435 insertions, 284 deletions
diff --git a/brotli/dec/decode.c b/brotli/dec/decode.c index 0e61640..a8b4ba3 100644 --- a/brotli/dec/decode.c +++ b/brotli/dec/decode.c @@ -14,7 +14,6 @@ #include <stdlib.h> #include <stdio.h> -#include <string.h> #include "./bit_reader.h" #include "./context.h" #include "./decode.h" @@ -28,10 +27,10 @@ extern "C" { #ifdef BROTLI_DECODE_DEBUG #define BROTLI_LOG_UINT(name) \ - printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)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]) + (unsigned long)(idx), (unsigned long)array_name[idx]) #else #define BROTLI_LOG_UINT(name) #define BROTLI_LOG_ARRAY_INDEX(array_name, idx) @@ -46,10 +45,12 @@ static const int kCodeLengthRepeatOffsets[3] = { 3, 3, 11 }; static const int kNumLiteralCodes = 256; static const int kNumInsertAndCopyCodes = 704; static const int kNumBlockLengthCodes = 26; +static const int kLiteralContextBits = 6; +static const int kDistanceContextBits = 2; #define CODE_LENGTH_CODES 19 static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = { - 17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 + 1, 2, 3, 4, 0, 17, 18, 5, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15 }; #define NUM_DISTANCE_SHORT_CODES 16 @@ -61,81 +62,92 @@ static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = { 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 }; -static int DecodeSize(BrotliBitReader* br, size_t* len) { +static int64_t DecodeSize(BrotliBitReader* br) { int size_bytes = BrotliReadBits(br, 3); int i = 0; - *len = 0; + int64_t len = 0; + if (size_bytes == 0) { + return -1; + } for (; i < size_bytes; ++i) { - *len |= BrotliReadBits(br, 8) << (i * 8); + len |= BrotliReadBits(br, 8) << (i * 8); } - return !br->error_; + return len; } -static int DecodeMetaBlockLength(int input_size_bits, - size_t remaining_length, - BrotliBitReader* br, - size_t* meta_block_length) { - if (BrotliReadBits(br, 1)) { - *meta_block_length = remaining_length; - return 1; - } else { - int shift = 0; +static void DecodeMetaBlockLength(int input_size_bits, + size_t pos, + int64_t input_size, + BrotliBitReader* br, + size_t* meta_block_length, + int* input_end) { + *input_end = BrotliReadBits(br, 1); + if (input_size < 0) { *meta_block_length = 0; - while (input_size_bits > 0) { - *meta_block_length |= BrotliReadBits(br, 8) << shift; - input_size_bits -= 8; - shift += 8; + if (!*input_end) { + int size_nibbles = BrotliReadBits(br, 3); + int i; + for (i = 0; i < size_nibbles; ++i) { + *meta_block_length |= BrotliReadBits(br, 4) << (i * 4); + } + ++(*meta_block_length); } - if (input_size_bits > 0) { - *meta_block_length |= BrotliReadBits(br, input_size_bits) << shift; + } else { + if (*input_end) { + *meta_block_length = (size_t)input_size - pos; + } else { + int shift = 0; + *meta_block_length = 0; + while (input_size_bits > 0) { + *meta_block_length |= BrotliReadBits(br, 8) << shift; + input_size_bits -= 8; + shift += 8; + } + if (input_size_bits > 0) { + *meta_block_length |= BrotliReadBits(br, input_size_bits) << shift; + } + ++(*meta_block_length); } - ++(*meta_block_length); - return !br->error_; } } // Decodes the next Huffman code from bit-stream. -// FillBitWindow(br) needs to be called at minimum every second call -// to ReadSymbol, in order to pre-fetch enough bits. static BROTLI_INLINE int ReadSymbol(const HuffmanTree* tree, BrotliBitReader* br) { - if (tree->fixed_bit_length_ > 0) { - return BrotliReadBits(br, tree->fixed_bit_length_); - } else { - const HuffmanTreeNode* node = tree->root_; - uint32_t bits = BrotliPrefetchBits(br); - int bitpos = br->bit_pos_; - // Check if we find the bit combination from the Huffman lookup table. - const int lut_ix = bits & (HUFF_LUT - 1); - const int lut_bits = tree->lut_bits_[lut_ix]; - if (lut_bits <= HUFF_LUT_BITS) { - BrotliSetBitPos(br, bitpos + lut_bits); - return tree->lut_symbol_[lut_ix]; - } - node += tree->lut_jump_[lut_ix]; - bitpos += HUFF_LUT_BITS; - bits >>= HUFF_LUT_BITS; - - // Decode the value from a binary tree. - assert(node != NULL); - do { - node = HuffmanTreeNextNode(node, bits & 1); - bits >>= 1; - ++bitpos; - } while (HuffmanTreeNodeIsNotLeaf(node)); - BrotliSetBitPos(br, bitpos); - return node->symbol_; + const HuffmanTreeNode* node = tree->root_; + BrotliFillBitWindow(br); + uint32_t bits = BrotliPrefetchBits(br); + int bitpos = br->bit_pos_; + // Check if we find the bit combination from the Huffman lookup table. + const int lut_ix = bits & (HUFF_LUT - 1); + const int lut_bits = tree->lut_bits_[lut_ix]; + if (lut_bits <= HUFF_LUT_BITS) { + BrotliSetBitPos(br, bitpos + lut_bits); + return tree->lut_symbol_[lut_ix]; } + node += tree->lut_jump_[lut_ix]; + bitpos += HUFF_LUT_BITS; + bits >>= HUFF_LUT_BITS; + + // Decode the value from a binary tree. + assert(node != NULL); + do { + node = HuffmanTreeNextNode(node, bits & 1); + bits >>= 1; + ++bitpos; + } while (HuffmanTreeNodeIsNotLeaf(node)); + BrotliSetBitPos(br, bitpos); + return node->symbol_; } -static void PrintIntVector(const int* v, int len) { +static void PrintUcharVector(const uint8_t* v, int len) { while (len-- > 0) printf(" %d", *v++); printf("\n"); } static int ReadHuffmanCodeLengths( - const int* code_length_code_lengths, - int num_symbols, int* code_lengths, + const uint8_t* code_length_code_lengths, + int num_symbols, uint8_t* code_lengths, BrotliBitReader* br) { int ok = 0; int symbol; @@ -147,10 +159,14 @@ static int ReadHuffmanCodeLengths( if (!BrotliHuffmanTreeBuildImplicit(&tree, code_length_code_lengths, CODE_LENGTH_CODES)) { printf("[ReadHuffmanCodeLengths] Building code length tree failed: "); - PrintIntVector(code_length_code_lengths, CODE_LENGTH_CODES); + PrintUcharVector(code_length_code_lengths, CODE_LENGTH_CODES); return 0; } + if (!BrotliReadMoreInput(br)) { + printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n"); + return 0; + } decode_number_of_code_length_codes = BrotliReadBits(br, 1); BROTLI_LOG_UINT(decode_number_of_code_length_codes); if (decode_number_of_code_length_codes) { @@ -171,7 +187,10 @@ static int ReadHuffmanCodeLengths( while (symbol < num_symbols) { int code_len; if (max_symbol-- == 0) break; - BrotliFillBitWindow(br); + if (!BrotliReadMoreInput(br)) { + printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n"); + goto End; + } code_len = ReadSymbol(&tree, br); BROTLI_LOG_UINT(symbol); BROTLI_LOG_UINT(code_len); @@ -206,128 +225,101 @@ static int ReadHuffmanCodeLengths( return ok; } -static const int64_t kUnitInterval = 1LL<<30; - -static int RepairHuffmanCodeLengths(int num_symbols, int* code_lengths) { - int i; - int64_t space = kUnitInterval; - int max_length = 0; - for(i = 0; i < num_symbols; i++) - if (code_lengths[i] != 0) { - if (code_lengths[i] > max_length) - max_length = code_lengths[i]; - space -= kUnitInterval >> code_lengths[i]; - } - // The code which contains one symbol of length one cannot be made optimal. - if (max_length == 1) - return 1; - if (space < 0) { - int count_longest = 0; - int new_length = max_length; - for(i = 0; i < num_symbols; i++) { - if (code_lengths[i] == max_length) - count_longest++; - } - // Substitute all longest codes with sufficiently longer ones, so that all - // code words fit into the unit interval. Leftover space will be - // redistributed later. - space += count_longest * (kUnitInterval >> max_length); - if (space < 0) - return 0; - while (space < count_longest * (kUnitInterval >> new_length)) - new_length++; - space -= count_longest * (kUnitInterval >> new_length); - for(i = 0; i < num_symbols; i++) { - if (code_lengths[i] == max_length) - code_lengths[i] = new_length; - } - } - - while (space > 0) { - // Redistribute leftover space in an approximation of a uniform fashion. - for(i = 0; i < num_symbols; i++) { - if (code_lengths[i] > 1 && space >= (kUnitInterval >> code_lengths[i])) { - space -= kUnitInterval >> code_lengths[i]; - code_lengths[i]--; - } - if (space == 0) - break; - } - } - return 1; -} - static int ReadHuffmanCode(int alphabet_size, HuffmanTree* tree, BrotliBitReader* br) { - int ok = 0; - const int simple_code = BrotliReadBits(br, 1); - BROTLI_LOG_UINT(simple_code); + int ok = 1; + int simple_code; + uint8_t* code_lengths = NULL; + code_lengths = + (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size, + sizeof(*code_lengths)); + if (code_lengths == NULL) { + return 0; + } + if (!BrotliReadMoreInput(br)) { + printf("[ReadHuffmanCode] Unexpected end of input.\n"); + return 0; + } + simple_code = BrotliReadBits(br, 1); + BROTLI_LOG_UINT(simple_code); if (simple_code) { // Read symbols, codes & code lengths directly. - int symbols[2] = { 0 }; - int codes[2]; - int code_lengths[2]; - const int num_symbols = BrotliReadBits(br, 1) + 1; - const int first_symbol_len_code = BrotliReadBits(br, 1); - // The first code is either 1 bit or 8 bit code. - symbols[0] = BrotliReadBits(br, (first_symbol_len_code == 0) ? 1 : 8); - codes[0] = 0; - code_lengths[0] = num_symbols - 1; - // The second code (if present), is always 8 bit long. - if (num_symbols == 2) { - symbols[1] = BrotliReadBits(br, 8); - codes[1] = 1; - code_lengths[1] = num_symbols - 1; + int i; + int max_bits_counter = alphabet_size - 1; + int max_bits = 0; + int symbols[4] = { 0 }; + const int num_symbols = BrotliReadBits(br, 2) + 1; + while (max_bits_counter) { + max_bits_counter >>= 1; + ++max_bits; } - BROTLI_LOG_UINT(num_symbols); - BROTLI_LOG_UINT(first_symbol_len_code); - BROTLI_LOG_UINT(symbols[0]); - BROTLI_LOG_UINT(symbols[1]); - ok = BrotliHuffmanTreeBuildExplicit(tree, code_lengths, codes, symbols, - alphabet_size, num_symbols); - if (!ok) { - printf("[ReadHuffmanCode] HuffmanTreeBuildExplicit failed: "); - PrintIntVector(code_lengths, num_symbols); + memset(code_lengths, 0, alphabet_size); + for (i = 0; i < num_symbols; ++i) { + symbols[i] = BrotliReadBits(br, max_bits); + code_lengths[symbols[i]] = 2; } + code_lengths[symbols[0]] = 1; + switch (num_symbols) { + case 1: + case 3: + break; + case 2: + code_lengths[symbols[1]] = 1; + break; + case 4: + if (BrotliReadBits(br, 1)) { + code_lengths[symbols[2]] = 3; + code_lengths[symbols[3]] = 3; + } else { + code_lengths[symbols[0]] = 2; + } + break; + } + BROTLI_LOG_UINT(num_symbols); } else { // Decode Huffman-coded code lengths. - int* code_lengths = NULL; int i; - int code_length_code_lengths[CODE_LENGTH_CODES] = { 0 }; + uint8_t code_length_code_lengths[CODE_LENGTH_CODES] = { 0 }; const int num_codes = BrotliReadBits(br, 4) + 4; BROTLI_LOG_UINT(num_codes); if (num_codes > CODE_LENGTH_CODES) { return 0; } - - code_lengths = - (int*)BrotliSafeMalloc((uint64_t)alphabet_size, sizeof(*code_lengths)); - if (code_lengths == NULL) { - return 0; - } - - for (i = 0; i < num_codes; ++i) { + for (i = BrotliReadBits(br, 1) * 2; i < num_codes; ++i) { int code_len_idx = kCodeLengthCodeOrder[i]; - code_length_code_lengths[code_len_idx] = BrotliReadBits(br, 3); + int v = BrotliReadBits(br, 2); + if (v == 3) { + v = BrotliReadBits(br, 1); + if (v == 0) { + v = 2; + } else { + v = BrotliReadBits(br, 1); + if (v == 0) { + v = 1; + } else { + v = 5; + } + } + } else if (v == 1) { + v = 3; + } else if (v == 2) { + v = 4; + } + code_length_code_lengths[code_len_idx] = v; BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx); } ok = ReadHuffmanCodeLengths(code_length_code_lengths, alphabet_size, - code_lengths, br) && - RepairHuffmanCodeLengths(alphabet_size, code_lengths); - if (ok) { - ok = BrotliHuffmanTreeBuildImplicit(tree, code_lengths, alphabet_size); - if (!ok) { - printf("[ReadHuffmanCode] HuffmanTreeBuildImplicit failed: "); - PrintIntVector(code_lengths, alphabet_size); - } - } - free(code_lengths); + code_lengths, br); } - ok = ok && !br->error_; - if (!ok) { - return 0; + if (ok) { + ok = BrotliHuffmanTreeBuildImplicit(tree, code_lengths, alphabet_size); + if (!ok) { + printf("[ReadHuffmanCode] HuffmanTreeBuildImplicit failed: "); + PrintUcharVector(code_lengths, alphabet_size); + } } - return 1; + free(code_lengths); + return ok; } static int ReadCopyDistance(const HuffmanTree* tree, @@ -339,7 +331,6 @@ static int ReadCopyDistance(const HuffmanTree* tree, int nbits; int postfix; int offset; - BrotliFillBitWindow(br); code = ReadSymbol(tree, br); if (code < num_direct_codes) { return code; @@ -357,7 +348,6 @@ static int ReadCopyDistance(const HuffmanTree* tree, static int ReadBlockLength(const HuffmanTree* tree, BrotliBitReader* br) { int code; int nbits; - BrotliFillBitWindow(br); code = ReadSymbol(tree, br); nbits = kBlockLengthPrefixCode[code].nbits; return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits); @@ -371,8 +361,9 @@ static void ReadInsertAndCopy(const HuffmanTree* tree, int code; int range_idx; int insert_code; + int insert_extra_bits; int copy_code; - BrotliFillBitWindow(br); + int copy_extra_bits; code = ReadSymbol(tree, br); range_idx = code >> 6; if (range_idx >= 2) { @@ -383,27 +374,27 @@ static void ReadInsertAndCopy(const HuffmanTree* tree, } insert_code = (kInsertRangeLut[range_idx] << 3) + ((code >> 3) & 7); copy_code = (kCopyRangeLut[range_idx] << 3) + (code & 7); - *insert_len = - kInsertLengthPrefixCode[insert_code].offset + - BrotliReadBits(br, kInsertLengthPrefixCode[insert_code].nbits); - *copy_len = - kCopyLengthPrefixCode[copy_code].offset + - BrotliReadBits(br, kCopyLengthPrefixCode[copy_code].nbits); + *insert_len = kInsertLengthPrefixCode[insert_code].offset; + insert_extra_bits = kInsertLengthPrefixCode[insert_code].nbits; + if (insert_extra_bits > 0) { + *insert_len += BrotliReadBits(br, insert_extra_bits); + } + *copy_len = kCopyLengthPrefixCode[copy_code].offset; + copy_extra_bits = kCopyLengthPrefixCode[copy_code].nbits; + if (copy_extra_bits > 0) { + *copy_len += BrotliReadBits(br, copy_extra_bits); + } } -static int TranslateShortCodes(int code, int* ringbuffer, size_t* index) { +static int TranslateShortCodes(int code, int* ringbuffer, size_t index) { int val; if (code < NUM_DISTANCE_SHORT_CODES) { - int index_offset = kDistanceShortCodeIndexOffset[code]; - int value_offset = kDistanceShortCodeValueOffset[code]; - val = ringbuffer[(*index + index_offset) & 3] + value_offset; + index += kDistanceShortCodeIndexOffset[code]; + index &= 3; + val = ringbuffer[index] + kDistanceShortCodeValueOffset[code]; } else { val = code - NUM_DISTANCE_SHORT_CODES + 1; } - if (code > 0) { - ringbuffer[*index & 3] = val; - ++(*index); - } return val; } @@ -453,41 +444,24 @@ static int HuffmanTreeGroupDecode(HuffmanTreeGroup* group, BrotliBitReader* br) { int i; for (i = 0; i < group->num_htrees; ++i) { - ReadHuffmanCode(group->alphabet_size, &group->htrees[i], br); + if (!ReadHuffmanCode(group->alphabet_size, &group->htrees[i], br)) { + return 0; + } } return 1; } -static int DecodeContextMap(int num_block_types, - int stream_type, - int* context_mode, - int* contexts_per_block, +static int DecodeContextMap(int context_map_size, int* num_htrees, uint8_t** context_map, BrotliBitReader* br) { - int context_map_size; - int use_context = BrotliReadBits(br, 1); - if (!use_context) { - *context_mode = 0; - *contexts_per_block = 1; - *context_map = NULL; - *num_htrees = num_block_types; - return 1; + int ok = 1; + if (!BrotliReadMoreInput(br)) { + printf("[DecodeContextMap] Unexpected end of input.\n"); + return 0; } - switch (stream_type) { - case 0: - *context_mode = BrotliReadBits(br, 4); - *contexts_per_block = NumContexts(*context_mode); - break; - case 2: - *context_mode = 1; - *contexts_per_block = 4; - break; - } - context_map_size = *contexts_per_block * num_block_types; *num_htrees = BrotliReadBits(br, 8) + 1; - BROTLI_LOG_UINT(*context_mode); BROTLI_LOG_UINT(context_map_size); BROTLI_LOG_UINT(*num_htrees); @@ -511,13 +485,19 @@ static int DecodeContextMap(int num_block_types, if (use_rle_for_zeros) { max_run_length_prefix = BrotliReadBits(br, 4) + 1; } - ReadHuffmanCode(*num_htrees + max_run_length_prefix, - &tree_index_htree, br); + if (!ReadHuffmanCode(*num_htrees + max_run_length_prefix, + &tree_index_htree, br)) { + return 0; + } if (use_rle_for_zeros) { int i; for (i = 0; i < context_map_size;) { int code; - BrotliFillBitWindow(br); + if (!BrotliReadMoreInput(br)) { + printf("[DecodeContextMap] Unexpected end of input.\n"); + ok = 0; + goto End; + } code = ReadSymbol(&tree_index_htree, br); if (code == 0) { (*context_map)[i] = 0; @@ -536,16 +516,21 @@ static int DecodeContextMap(int num_block_types, } else { int i; for (i = 0; i < context_map_size; ++i) { - BrotliFillBitWindow(br); + if (!BrotliReadMoreInput(br)) { + printf("[DecodeContextMap] Unexpected end of input.\n"); + ok = 0; + goto End; + } (*context_map)[i] = ReadSymbol(&tree_index_htree, br); } } + End: BrotliHuffmanTreeRelease(&tree_index_htree); } if (BrotliReadBits(br, 1)) { InverseMoveToFrontTransform(*context_map, context_map_size); } - return 1; + return ok; } static BROTLI_INLINE void DecodeBlockType(const HuffmanTree* trees, @@ -570,39 +555,116 @@ static BROTLI_INLINE void DecodeBlockType(const HuffmanTree* trees, ++(*index); } +// Copy len bytes from src to dst. It can write up to ten extra bytes +// after the end of the copy. +// +// The main part of this loop is a simple copy of eight bytes at a time until +// we've copied (at least) the requested amount of bytes. However, if dst and +// src are less than eight bytes apart (indicating a repeating pattern of +// length < 8), we first need to expand the pattern in order to get the correct +// results. For instance, if the buffer looks like this, with the eight-byte +// <src> and <dst> patterns marked as intervals: +// +// abxxxxxxxxxxxx +// [------] src +// [------] dst +// +// a single eight-byte copy from <src> to <dst> will repeat the pattern once, +// after which we can move <dst> two bytes without moving <src>: +// +// ababxxxxxxxxxx +// [------] src +// [------] dst +// +// and repeat the exercise until the two no longer overlap. +// +// This allows us to do very well in the special case of one single byte +// repeated many times, without taking a big hit for more general cases. +// +// The worst case of extra writing past the end of the match occurs when +// dst - src == 1 and len == 1; the last copy will read from byte positions +// [0..7] and write to [4..11], whereas it was only supposed to write to +// position 1. Thus, ten excess bytes. +static BROTLI_INLINE void IncrementalCopyFastPath( + uint8_t* dst, const uint8_t* src, int len) { + if (src < dst) { + while (dst - src < 8) { + UNALIGNED_COPY64(dst, src); + len -= dst - src; + dst += dst - src; + } + } + while (len > 0) { + UNALIGNED_COPY64(dst, src); + src += 8; + dst += 8; + len -= 8; + } +} + int BrotliDecompressedSize(size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size) { + BrotliMemInput memin; + BrotliInput input = BrotliInitMemInput(encoded_buffer, encoded_size, &memin); BrotliBitReader br; - BrotliInitBitReader(&br, encoded_buffer, encoded_size); - return DecodeSize(&br, decoded_size); + if (!BrotliInitBitReader(&br, input)) { + return 0; + } + int64_t size = DecodeSize(&br); + if (size < 0) { + return 0; + } + *decoded_size = (size_t)size; + return 1; } int BrotliDecompressBuffer(size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size, uint8_t* decoded_buffer) { + BrotliMemInput memin; + BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin); + BrotliMemOutput mout; + BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout); + int success = BrotliDecompress(in, out); + *decoded_size = mout.pos; + return success; +} + +int BrotliDecompress(BrotliInput input, BrotliOutput output) { int ok = 1; int i; size_t pos = 0; - uint8_t* data = decoded_buffer; - int input_size_bits; + int64_t decoded_size; + int input_size_bits = 0; + int input_end = 0; + int window_bits = 0; + size_t ringbuffer_size; + size_t ringbuffer_mask; + uint8_t* ringbuffer; + uint8_t* ringbuffer_end; // This ring buffer holds a few past copy distances that will be used by // some special distance codes. int dist_rb[4] = { 4, 11, 15, 16 }; size_t dist_rb_idx = 0; + // The previous 2 bytes used for context. + uint8_t prev_byte1 = 0; + uint8_t prev_byte2 = 0; HuffmanTreeGroup hgroup[3]; BrotliBitReader br; - BrotliInitBitReader(&br, encoded_buffer, encoded_size); - ok = DecodeSize(&br, decoded_size); - if (!ok) return 0; + if (!BrotliInitBitReader(&br, input)) { + return 0; + } - if (*decoded_size == 0) { + decoded_size = DecodeSize(&br); + if (decoded_size == 0) { return 1; } - { - size_t n = *decoded_size; + + if (decoded_size > 0) { + size_t n = (size_t)decoded_size; input_size_bits = (n == (n &~ (n - 1))) ? -1 : 0; while (n) { ++input_size_bits; @@ -610,12 +672,24 @@ int BrotliDecompressBuffer(size_t encoded_size, } } - BROTLI_LOG_UINT(*decoded_size); + // Decode window size. + if ((decoded_size < 0 || input_size_bits > 16) && BrotliReadBits(&br, 1)) { + window_bits = 17 + BrotliReadBits(&br, 3); + } else { + window_bits = 16; + } + + ringbuffer_size = 1 << window_bits; + ringbuffer_mask = ringbuffer_size - 1; + ringbuffer = (uint8_t*)malloc(ringbuffer_size + 16); + ringbuffer_end = ringbuffer + ringbuffer_size; + + BROTLI_LOG_UINT(decoded_size); BROTLI_LOG_UINT(input_size_bits); - while (pos < *decoded_size && ok) { + while (!input_end && ok) { size_t meta_block_len = 0; - size_t meta_block_end; + size_t meta_block_end_pos; size_t block_length[3] = { 0 }; int block_type[3] = { 0 }; int num_block_types[3] = { 0 }; @@ -628,12 +702,9 @@ int BrotliDecompressBuffer(size_t encoded_size, uint32_t distance_postfix_mask; int num_distance_codes; uint8_t* context_map = NULL; - int context_mode; - int contexts_per_block; + uint8_t* context_modes = NULL; int num_literal_htrees; uint8_t* dist_context_map = NULL; - int dist_context_mode; - int dist_contexts_per_block; int num_dist_htrees; int context_offset = 0; uint8_t* context_map_slice = NULL; @@ -641,23 +712,41 @@ int BrotliDecompressBuffer(size_t encoded_size, int dist_context_offset = 0; uint8_t* dist_context_map_slice = NULL; uint8_t dist_htree_index = 0; + int context_lookup_offset1 = 0; + int context_lookup_offset2 = 0; + uint8_t context_mode; - BROTLI_LOG_UINT(pos); - if (!DecodeMetaBlockLength(input_size_bits, *decoded_size - pos, - &br, &meta_block_len)) { - printf("Could not decode meta-block length.\n"); + for (i = 0; i < 3; ++i) { + hgroup[i].num_htrees = 0; + hgroup[i].htrees = NULL; + block_type_trees[i].root_ = NULL; + block_len_trees[i].root_ = NULL; + } + + if (!BrotliReadMoreInput(&br)) { + printf("[BrotliDecompress] Unexpected end of input.\n"); ok = 0; goto End; } + BROTLI_LOG_UINT(pos); + DecodeMetaBlockLength(input_size_bits, pos, decoded_size, + &br, &meta_block_len, &input_end); BROTLI_LOG_UINT(meta_block_len); - meta_block_end = pos + meta_block_len; + if (meta_block_len == 0) { + goto End; + } + meta_block_end_pos = pos + meta_block_len; for (i = 0; i < 3; ++i) { block_type_trees[i].root_ = NULL; block_len_trees[i].root_ = NULL; if (BrotliReadBits(&br, 1)) { num_block_types[i] = BrotliReadBits(&br, 8) + 1; - ReadHuffmanCode(num_block_types[i] + 2, &block_type_trees[i], &br); - ReadHuffmanCode(kNumBlockLengthCodes, &block_len_trees[i], &br); + if (!ReadHuffmanCode( + num_block_types[i] + 2, &block_type_trees[i], &br) || + !ReadHuffmanCode(kNumBlockLengthCodes, &block_len_trees[i], &br)) { + ok = 0; + goto End; + } block_length[i] = ReadBlockLength(&block_len_trees[i], &br); block_type_rb_index[i] = 1; } else { @@ -673,21 +762,32 @@ int BrotliDecompressBuffer(size_t encoded_size, BROTLI_LOG_UINT(block_length[1]); BROTLI_LOG_UINT(block_length[2]); + if (!BrotliReadMoreInput(&br)) { + printf("[BrotliDecompress] Unexpected end of input.\n"); + ok = 0; + goto End; + } distance_postfix_bits = BrotliReadBits(&br, 2); num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES + (BrotliReadBits(&br, 4) << distance_postfix_bits); distance_postfix_mask = (1 << distance_postfix_bits) - 1; num_distance_codes = (num_direct_distance_codes + (48 << distance_postfix_bits)); + context_modes = (uint8_t*)malloc(num_block_types[0]); + for (i = 0; i < num_block_types[0]; ++i) { + context_modes[i] = BrotliReadBits(&br, 2) << 1; + BROTLI_LOG_ARRAY_INDEX(context_modes, i); + } BROTLI_LOG_UINT(num_direct_distance_codes); BROTLI_LOG_UINT(distance_postfix_bits); - DecodeContextMap(num_block_types[0], 0, &context_mode, &contexts_per_block, - &num_literal_htrees, &context_map, &br); - - DecodeContextMap(num_block_types[2], 2, &dist_context_mode, - &dist_contexts_per_block, - &num_dist_htrees, &dist_context_map, &br); + if (!DecodeContextMap(num_block_types[0] << kLiteralContextBits, + &num_literal_htrees, &context_map, &br) || + !DecodeContextMap(num_block_types[2] << kDistanceContextBits, + &num_dist_htrees, &dist_context_map, &br)) { + ok = 0; + goto End; + } HuffmanTreeGroupInit(&hgroup[0], kNumLiteralCodes, num_literal_htrees); HuffmanTreeGroupInit(&hgroup[1], kNumInsertAndCopyCodes, @@ -695,18 +795,32 @@ int BrotliDecompressBuffer(size_t encoded_size, HuffmanTreeGroupInit(&hgroup[2], num_distance_codes, num_dist_htrees); for (i = 0; i < 3; ++i) { - HuffmanTreeGroupDecode(&hgroup[i], &br); + if (!HuffmanTreeGroupDecode(&hgroup[i], &br)) { + ok = 0; + goto End; + } } context_map_slice = context_map; dist_context_map_slice = dist_context_map; + context_mode = context_modes[block_type[0]]; + context_lookup_offset1 = kContextLookupOffsets[context_mode]; + context_lookup_offset2 = kContextLookupOffsets[context_mode + 1]; - while (pos < meta_block_end) { + while (pos < meta_block_end_pos) { int insert_length; int copy_length; int distance_code; int distance; + uint8_t context; int j; + const uint8_t* copy_src; + uint8_t* copy_dst; + if (!BrotliReadMoreInput(&br)) { + printf("[BrotliDecompress] Unexpected end of input.\n"); + ok = 0; + goto End; + } if (block_length[1] == 0) { DecodeBlockType(block_type_trees, 1, block_type, block_type_rb, block_type_rb_index, &br); @@ -719,87 +833,120 @@ int BrotliDecompressBuffer(size_t encoded_size, BROTLI_LOG_UINT(copy_length); BROTLI_LOG_UINT(distance_code); for (j = 0; j < insert_length; ++j) { + if (!BrotliReadMoreInput(&br)) { + printf("[BrotliDecompress] Unexpected end of input.\n"); + ok = 0; + goto End; + } if (block_length[0] == 0) { DecodeBlockType(block_type_trees, 0, block_type, block_type_rb, block_type_rb_index, &br); block_length[0] = ReadBlockLength(&block_len_trees[0], &br); - literal_htree_index = block_type[0]; - context_offset = block_type[0] * contexts_per_block; + context_offset = block_type[0] << kLiteralContextBits; context_map_slice = context_map + context_offset; + context_mode = context_modes[block_type[0]]; + context_lookup_offset1 = kContextLookupOffsets[context_mode]; + context_lookup_offset2 = kContextLookupOffsets[context_mode + 1]; } + context = (kContextLookup[context_lookup_offset1 + prev_byte1] | + kContextLookup[context_lookup_offset2 + prev_byte2]); + BROTLI_LOG_UINT(context); + literal_htree_index = context_map_slice[context]; --block_length[0]; - BrotliFillBitWindow(&br); - // Figure out htree - if (contexts_per_block > 1) { - uint8_t prev_byte = pos > 0 ? data[pos - 1] : 0; - uint8_t prev_byte2 = pos > 1 ? data[pos - 2] : 0; - uint8_t prev_byte3 = pos > 2 ? data[pos - 3] : 0; - uint8_t context = Context(prev_byte, prev_byte2, prev_byte3, - context_mode); - BROTLI_LOG_UINT(context); - literal_htree_index = context_map_slice[context]; - } - data[pos] = ReadSymbol(&hgroup[0].htrees[literal_htree_index], &br); + prev_byte2 = prev_byte1; + prev_byte1 = ReadSymbol(&hgroup[0].htrees[literal_htree_index], &br); + ringbuffer[pos & ringbuffer_mask] = prev_byte1; BROTLI_LOG_UINT(literal_htree_index); - BROTLI_LOG_ARRAY_INDEX(data, pos); + BROTLI_LOG_ARRAY_INDEX(ringbuffer, pos & ringbuffer_mask); + if ((pos & ringbuffer_mask) == ringbuffer_mask) { + if (BrotliWrite(output, ringbuffer, ringbuffer_size) < 0) { + ok = 0; + goto End; + } + } ++pos; } - if (br.error_) { - printf("Read error after decoding literal sequence.\n"); - ok = 0; - goto End; - } - - if (pos == meta_block_end) break; + if (pos == meta_block_end_pos) break; if (distance_code < 0) { + if (!BrotliReadMoreInput(&br)) { + printf("[BrotliDecompress] Unexpected end of input.\n"); + ok = 0; + goto End; + } if (block_length[2] == 0) { DecodeBlockType(block_type_trees, 2, block_type, block_type_rb, block_type_rb_index, &br); block_length[2] = ReadBlockLength(&block_len_trees[2], &br); dist_htree_index = block_type[2]; - dist_context_offset = block_type[2] * dist_contexts_per_block; + dist_context_offset = block_type[2] << kDistanceContextBits; dist_context_map_slice = dist_context_map + dist_context_offset; } --block_length[2]; - if (dist_contexts_per_block > 1) { - uint8_t context = copy_length > 4 ? 3 : copy_length - 2; - dist_htree_index = dist_context_map_slice[context]; - } + uint8_t context = copy_length > 4 ? 3 : copy_length - 2; + dist_htree_index = dist_context_map_slice[context]; distance_code = ReadCopyDistance(&hgroup[2].htrees[dist_htree_index], num_direct_distance_codes, distance_postfix_bits, distance_postfix_mask, &br); - if (br.error_) { - printf("Could not read copy distance.\n"); - ok = 0; - goto End; - } } // Convert the distance code to the actual distance by possibly looking // up past distnaces from the ringbuffer. - distance = TranslateShortCodes(distance_code, dist_rb, &dist_rb_idx); + distance = TranslateShortCodes(distance_code, dist_rb, dist_rb_idx); + if (distance_code > 0) { + dist_rb[dist_rb_idx & 3] = distance; + ++dist_rb_idx; + } + BROTLI_LOG_UINT(distance); - // Do the actual copy if it is valid. - if (distance > 0 && pos >= (size_t)distance && - pos + copy_length <= *decoded_size) { - int j; - for (j = 0; j < copy_length; ++j) { - data[pos + j] = data[pos + j - distance]; - } - pos += copy_length; - } else { - printf("Invalid backward reference. pos: %lu distance: %d " - "len: %d end: %lu\n", (unsigned long)pos, distance, copy_length, - (unsigned long)*decoded_size); + if (pos < (size_t)distance || pos + copy_length > meta_block_end_pos) { + printf("Invalid backward reference. pos: %ld distance: %d " + "len: %d end: %lu\n", pos, distance, copy_length, + (unsigned long)meta_block_end_pos); ok = 0; goto End; } + + copy_src = &ringbuffer[(pos - distance) & ringbuffer_mask]; + copy_dst = &ringbuffer[pos & ringbuffer_mask]; + +#if (defined(__x86_64__) || defined(_M_X64)) + if (copy_src + copy_length <= ringbuffer_end && + copy_dst + copy_length < ringbuffer_end) { + if (copy_length <= 16 && distance >= 8) { + UNALIGNED_COPY64(copy_dst, copy_src); + UNALIGNED_COPY64(copy_dst + 8, copy_src + 8); + } else { + IncrementalCopyFastPath(copy_dst, copy_src, copy_length); + } + pos += copy_length; + copy_length = 0; + } +#endif + + for (j = 0; j < copy_length; ++j) { + ringbuffer[pos & ringbuffer_mask] = + ringbuffer[(pos - distance) & ringbuffer_mask]; + if ((pos & ringbuffer_mask) == ringbuffer_mask) { + if (BrotliWrite(output, ringbuffer, ringbuffer_size) < 0) { + ok = 0; + goto End; + } + } + ++pos; + } + + // When we get here, we must have inserted at least one literal and made + // a copy of at least length two, therefore accessing the last 2 bytes is + // valid. + prev_byte1 = ringbuffer[(pos - 1) & ringbuffer_mask]; + prev_byte2 = ringbuffer[(pos - 2) & ringbuffer_mask]; } End: + free(context_modes); free(context_map); free(dist_context_map); for (i = 0; i < 3; ++i) { @@ -809,6 +956,10 @@ int BrotliDecompressBuffer(size_t encoded_size, } } + if (BrotliWrite(output, ringbuffer, pos & ringbuffer_mask) < 0) { + ok = 0; + } + free(ringbuffer); return ok; } |