From 26a029d407be480d791972afb5975cf62c9360a6 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 02:47:55 +0200 Subject: Adding upstream version 124.0.1. Signed-off-by: Daniel Baumann --- modules/brotli/dec/bit_reader.c | 78 ++ modules/brotli/dec/bit_reader.h | 423 ++++++ modules/brotli/dec/decode.c | 2875 +++++++++++++++++++++++++++++++++++++++ modules/brotli/dec/huffman.c | 342 +++++ modules/brotli/dec/huffman.h | 122 ++ modules/brotli/dec/prefix.h | 733 ++++++++++ modules/brotli/dec/state.c | 183 +++ modules/brotli/dec/state.h | 400 ++++++ 8 files changed, 5156 insertions(+) create mode 100644 modules/brotli/dec/bit_reader.c create mode 100644 modules/brotli/dec/bit_reader.h create mode 100644 modules/brotli/dec/decode.c create mode 100644 modules/brotli/dec/huffman.c create mode 100644 modules/brotli/dec/huffman.h create mode 100644 modules/brotli/dec/prefix.h create mode 100644 modules/brotli/dec/state.c create mode 100644 modules/brotli/dec/state.h (limited to 'modules/brotli/dec') diff --git a/modules/brotli/dec/bit_reader.c b/modules/brotli/dec/bit_reader.c new file mode 100644 index 0000000000..35101ddc1a --- /dev/null +++ b/modules/brotli/dec/bit_reader.c @@ -0,0 +1,78 @@ +/* Copyright 2013 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* Bit reading helpers */ + +#include "bit_reader.h" + +#include + +#include "../common/platform.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +const brotli_reg_t kBrotliBitMask[33] = { 0x00000000, + 0x00000001, 0x00000003, 0x00000007, 0x0000000F, + 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF, + 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF, + 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF, + 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF, + 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF, + 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF, + 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF, 0xFFFFFFFF +}; + +void BrotliInitBitReader(BrotliBitReader* const br) { + br->val_ = 0; + br->bit_pos_ = 0; +} + +BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br) { + size_t aligned_read_mask = (sizeof(br->val_) >> 1) - 1; + /* Fixing alignment after unaligned BrotliFillWindow would result accumulator + overflow. If unalignment is caused by BrotliSafeReadBits, then there is + enough space in accumulator to fix alignment. */ + if (BROTLI_UNALIGNED_READ_FAST) { + aligned_read_mask = 0; + } + if (BrotliGetAvailableBits(br) == 0) { + br->val_ = 0; + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; + } + } + + while ((((size_t)br->next_in) & aligned_read_mask) != 0) { + if (!BrotliPullByte(br)) { + /* If we consumed all the input, we don't care about the alignment. */ + return BROTLI_TRUE; + } + } + return BROTLI_TRUE; +} + +BROTLI_BOOL BrotliSafeReadBits32Slow(BrotliBitReader* const br, + brotli_reg_t n_bits, brotli_reg_t* val) { + brotli_reg_t low_val; + brotli_reg_t high_val; + BrotliBitReaderState memento; + BROTLI_DCHECK(n_bits <= 32); + BROTLI_DCHECK(n_bits > 24); + BrotliBitReaderSaveState(br, &memento); + if (!BrotliSafeReadBits(br, 16, &low_val) || + !BrotliSafeReadBits(br, n_bits - 16, &high_val)) { + BrotliBitReaderRestoreState(br, &memento); + return BROTLI_FALSE; + } + *val = low_val | (high_val << 16); + return BROTLI_TRUE; +} + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif diff --git a/modules/brotli/dec/bit_reader.h b/modules/brotli/dec/bit_reader.h new file mode 100644 index 0000000000..930dc60f1d --- /dev/null +++ b/modules/brotli/dec/bit_reader.h @@ -0,0 +1,423 @@ +/* Copyright 2013 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* Bit reading helpers */ + +#ifndef BROTLI_DEC_BIT_READER_H_ +#define BROTLI_DEC_BIT_READER_H_ + +#include /* memcpy */ + +#include + +#include "../common/constants.h" +#include "../common/platform.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1) + +/* 162 bits + 7 bytes */ +#define BROTLI_FAST_INPUT_SLACK 28 + +BROTLI_INTERNAL extern const brotli_reg_t kBrotliBitMask[33]; + +static BROTLI_INLINE brotli_reg_t BitMask(brotli_reg_t n) { + if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) { + /* Masking with this expression turns to a single + "Unsigned Bit Field Extract" UBFX instruction on ARM. */ + return ~(~((brotli_reg_t)0) << n); + } else { + return kBrotliBitMask[n]; + } +} + +typedef struct { + brotli_reg_t val_; /* pre-fetched bits */ + brotli_reg_t bit_pos_; /* current bit-reading position in val_ */ + const uint8_t* next_in; /* the byte we're reading from */ + const uint8_t* guard_in; /* position from which "fast-path" is prohibited */ + const uint8_t* last_in; /* == next_in + avail_in */ +} BrotliBitReader; + +typedef struct { + brotli_reg_t val_; + brotli_reg_t bit_pos_; + const uint8_t* next_in; + size_t avail_in; +} BrotliBitReaderState; + +/* Initializes the BrotliBitReader fields. */ +BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* br); + +/* Ensures that accumulator is not empty. + May consume up to sizeof(brotli_reg_t) - 1 bytes of input. + Returns BROTLI_FALSE if data is required but there is no input available. + For !BROTLI_UNALIGNED_READ_FAST this function also prepares bit reader for + aligned reading. */ +BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* br); + +/* Fallback for BrotliSafeReadBits32. Extracted as noninlined method to unburden + the main code-path. Never called for RFC brotli streams, required only for + "large-window" mode and other extensions. */ +BROTLI_INTERNAL BROTLI_NOINLINE BROTLI_BOOL BrotliSafeReadBits32Slow( + BrotliBitReader* br, brotli_reg_t n_bits, brotli_reg_t* val); + +static BROTLI_INLINE size_t +BrotliBitReaderGetAvailIn(BrotliBitReader* const br) { + return (size_t)(br->last_in - br->next_in); +} + +static BROTLI_INLINE void BrotliBitReaderSaveState( + BrotliBitReader* const from, BrotliBitReaderState* to) { + to->val_ = from->val_; + to->bit_pos_ = from->bit_pos_; + to->next_in = from->next_in; + to->avail_in = BrotliBitReaderGetAvailIn(from); +} + +static BROTLI_INLINE void BrotliBitReaderSetInput( + BrotliBitReader* const br, const uint8_t* next_in, size_t avail_in) { + br->next_in = next_in; + br->last_in = (avail_in == 0) ? next_in : (next_in + avail_in); + if (avail_in + 1 > BROTLI_FAST_INPUT_SLACK) { + br->guard_in = next_in + (avail_in + 1 - BROTLI_FAST_INPUT_SLACK); + } else { + br->guard_in = next_in; + } +} + +static BROTLI_INLINE void BrotliBitReaderRestoreState( + BrotliBitReader* const to, BrotliBitReaderState* from) { + to->val_ = from->val_; + to->bit_pos_ = from->bit_pos_; + to->next_in = from->next_in; + BrotliBitReaderSetInput(to, from->next_in, from->avail_in); +} + +static BROTLI_INLINE brotli_reg_t BrotliGetAvailableBits( + const BrotliBitReader* br) { + return br->bit_pos_; +} + +/* Returns amount of unread bytes the bit reader still has buffered from the + BrotliInput, including whole bytes in br->val_. Result is capped with + maximal ring-buffer size (larger number won't be utilized anyway). */ +static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) { + static const size_t kCap = (size_t)1 << BROTLI_LARGE_MAX_WBITS; + size_t avail_in = BrotliBitReaderGetAvailIn(br); + if (avail_in > kCap) return kCap; + return avail_in + (BrotliGetAvailableBits(br) >> 3); +} + +/* Checks if there is at least |num| bytes left in the input ring-buffer + (excluding the bits remaining in br->val_). */ +static BROTLI_INLINE BROTLI_BOOL BrotliCheckInputAmount( + BrotliBitReader* const br) { + return TO_BROTLI_BOOL(br->next_in < br->guard_in); +} + +/* Load more bits into accumulator. */ +static BROTLI_INLINE brotli_reg_t BrotliBitReaderLoadBits(brotli_reg_t val, + brotli_reg_t new_bits, + brotli_reg_t count, + brotli_reg_t offset) { + BROTLI_DCHECK( + !((val >> offset) & ~new_bits & ~(~((brotli_reg_t)0) << count))); + (void)count; + return val | (new_bits << offset); +} + +/* Guarantees that there are at least |n_bits| + 1 bits in accumulator. + Precondition: accumulator contains at least 1 bit. + |n_bits| should be in the range [1..24] for regular build. For portable + non-64-bit little-endian build only 16 bits are safe to request. */ +static BROTLI_INLINE void BrotliFillBitWindow( + BrotliBitReader* const br, brotli_reg_t n_bits) { +#if (BROTLI_64_BITS) + if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) && + (n_bits <= 8)) { + brotli_reg_t bit_pos = br->bit_pos_; + if (bit_pos <= 8) { + br->val_ = BrotliBitReaderLoadBits(br->val_, + BROTLI_UNALIGNED_LOAD64LE(br->next_in), 56, bit_pos); + br->bit_pos_ = bit_pos + 56; + br->next_in += 7; + } + } else if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) && + (n_bits <= 16)) { + brotli_reg_t bit_pos = br->bit_pos_; + if (bit_pos <= 16) { + br->val_ = BrotliBitReaderLoadBits(br->val_, + BROTLI_UNALIGNED_LOAD64LE(br->next_in), 48, bit_pos); + br->bit_pos_ = bit_pos + 48; + br->next_in += 6; + } + } else { + brotli_reg_t bit_pos = br->bit_pos_; + if (bit_pos <= 32) { + br->val_ = BrotliBitReaderLoadBits(br->val_, + (uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in), 32, bit_pos); + br->bit_pos_ = bit_pos + 32; + br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; + } + } +#else + if (BROTLI_UNALIGNED_READ_FAST && BROTLI_IS_CONSTANT(n_bits) && + (n_bits <= 8)) { + brotli_reg_t bit_pos = br->bit_pos_; + if (bit_pos <= 8) { + br->val_ = BrotliBitReaderLoadBits(br->val_, + BROTLI_UNALIGNED_LOAD32LE(br->next_in), 24, bit_pos); + br->bit_pos_ = bit_pos + 24; + br->next_in += 3; + } + } else { + brotli_reg_t bit_pos = br->bit_pos_; + if (bit_pos <= 16) { + br->val_ = BrotliBitReaderLoadBits(br->val_, + (uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in), 16, bit_pos); + br->bit_pos_ = bit_pos + 16; + br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; + } + } +#endif +} + +/* Mostly like BrotliFillBitWindow, but guarantees only 16 bits and reads no + more than BROTLI_SHORT_FILL_BIT_WINDOW_READ bytes of input. */ +static BROTLI_INLINE void BrotliFillBitWindow16(BrotliBitReader* const br) { + BrotliFillBitWindow(br, 17); +} + +/* Tries to pull one byte of input to accumulator. + Returns BROTLI_FALSE if there is no input available. */ +static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) { + if (br->next_in == br->last_in) { + return BROTLI_FALSE; + } + br->val_ = BrotliBitReaderLoadBits(br->val_, + (brotli_reg_t)*br->next_in, 8, br->bit_pos_); + br->bit_pos_ += 8; + ++br->next_in; + return BROTLI_TRUE; +} + +/* Returns currently available bits. + The number of valid bits could be calculated by BrotliGetAvailableBits. */ +static BROTLI_INLINE brotli_reg_t BrotliGetBitsUnmasked( + BrotliBitReader* const br) { + return br->val_; +} + +/* Like BrotliGetBits, but does not mask the result. + The result contains at least 16 valid bits. */ +static BROTLI_INLINE brotli_reg_t BrotliGet16BitsUnmasked( + BrotliBitReader* const br) { + BrotliFillBitWindow(br, 16); + return (brotli_reg_t)BrotliGetBitsUnmasked(br); +} + +/* Returns the specified number of bits from |br| without advancing bit + position. */ +static BROTLI_INLINE brotli_reg_t BrotliGetBits( + BrotliBitReader* const br, brotli_reg_t n_bits) { + BrotliFillBitWindow(br, n_bits); + return BrotliGetBitsUnmasked(br) & BitMask(n_bits); +} + +/* Tries to peek the specified amount of bits. Returns BROTLI_FALSE, if there + is not enough input. */ +static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits( + BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) { + while (BrotliGetAvailableBits(br) < n_bits) { + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; + } + } + *val = BrotliGetBitsUnmasked(br) & BitMask(n_bits); + return BROTLI_TRUE; +} + +/* Advances the bit pos by |n_bits|. */ +static BROTLI_INLINE void BrotliDropBits( + BrotliBitReader* const br, brotli_reg_t n_bits) { + br->bit_pos_ -= n_bits; + br->val_ >>= n_bits; +} + +/* Make sure that there are no spectre bits in accumulator. + This is important for the cases when some bytes are skipped + (i.e. never placed into accumulator). */ +static BROTLI_INLINE void BrotliBitReaderNormalize(BrotliBitReader* br) { + /* Actually, it is enough to normalize when br->bit_pos_ == 0 */ + if (br->bit_pos_ < (sizeof(brotli_reg_t) << 3u)) { + br->val_ &= (((brotli_reg_t)1) << br->bit_pos_) - 1; + } +} + +static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) { + brotli_reg_t unused_bytes = BrotliGetAvailableBits(br) >> 3; + brotli_reg_t unused_bits = unused_bytes << 3; + br->next_in = + (unused_bytes == 0) ? br->next_in : (br->next_in - unused_bytes); + br->bit_pos_ -= unused_bits; + BrotliBitReaderNormalize(br); +} + +/* Reads the specified number of bits from |br| and advances the bit pos. + Precondition: accumulator MUST contain at least |n_bits|. */ +static BROTLI_INLINE void BrotliTakeBits(BrotliBitReader* const br, + brotli_reg_t n_bits, + brotli_reg_t* val) { + *val = BrotliGetBitsUnmasked(br) & BitMask(n_bits); + BROTLI_LOG(("[BrotliTakeBits] %d %d %d val: %6x\n", + (int)BrotliBitReaderGetAvailIn(br), (int)br->bit_pos_, + (int)n_bits, (int)*val)); + BrotliDropBits(br, n_bits); +} + +/* Reads the specified number of bits from |br| and advances the bit pos. + Assumes that there is enough input to perform BrotliFillBitWindow. + Up to 24 bits are allowed to be requested from this method. */ +static BROTLI_INLINE brotli_reg_t BrotliReadBits24( + BrotliBitReader* const br, brotli_reg_t n_bits) { + BROTLI_DCHECK(n_bits <= 24); + if (BROTLI_64_BITS || (n_bits <= 16)) { + brotli_reg_t val; + BrotliFillBitWindow(br, n_bits); + BrotliTakeBits(br, n_bits, &val); + return val; + } else { + brotli_reg_t low_val; + brotli_reg_t high_val; + BrotliFillBitWindow(br, 16); + BrotliTakeBits(br, 16, &low_val); + BrotliFillBitWindow(br, 8); + BrotliTakeBits(br, n_bits - 16, &high_val); + return low_val | (high_val << 16); + } +} + +/* Same as BrotliReadBits24, but allows reading up to 32 bits. */ +static BROTLI_INLINE brotli_reg_t BrotliReadBits32( + BrotliBitReader* const br, brotli_reg_t n_bits) { + BROTLI_DCHECK(n_bits <= 32); + if (BROTLI_64_BITS || (n_bits <= 16)) { + brotli_reg_t val; + BrotliFillBitWindow(br, n_bits); + BrotliTakeBits(br, n_bits, &val); + return val; + } else { + brotli_reg_t low_val; + brotli_reg_t high_val; + BrotliFillBitWindow(br, 16); + BrotliTakeBits(br, 16, &low_val); + BrotliFillBitWindow(br, 16); + BrotliTakeBits(br, n_bits - 16, &high_val); + return low_val | (high_val << 16); + } +} + +/* Tries to read the specified amount of bits. Returns BROTLI_FALSE, if there + is not enough input. |n_bits| MUST be positive. + Up to 24 bits are allowed to be requested from this method. */ +static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits( + BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) { + BROTLI_DCHECK(n_bits <= 24); + while (BrotliGetAvailableBits(br) < n_bits) { + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; + } + } + BrotliTakeBits(br, n_bits, val); + return BROTLI_TRUE; +} + +/* Same as BrotliSafeReadBits, but allows reading up to 32 bits. */ +static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits32( + BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) { + BROTLI_DCHECK(n_bits <= 32); + if (BROTLI_64_BITS || (n_bits <= 24)) { + while (BrotliGetAvailableBits(br) < n_bits) { + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; + } + } + BrotliTakeBits(br, n_bits, val); + return BROTLI_TRUE; + } else { + return BrotliSafeReadBits32Slow(br, n_bits, val); + } +} + +/* Advances the bit reader position to the next byte boundary and verifies + that any skipped bits are set to zero. */ +static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) { + brotli_reg_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7; + brotli_reg_t pad_bits = 0; + if (pad_bits_count != 0) { + BrotliTakeBits(br, pad_bits_count, &pad_bits); + } + BrotliBitReaderNormalize(br); + return TO_BROTLI_BOOL(pad_bits == 0); +} + +static BROTLI_INLINE void BrotliDropBytes(BrotliBitReader* br, size_t num) { + /* Check detour is legal: accumulator must to be empty. */ + BROTLI_DCHECK(br->bit_pos_ == 0); + BROTLI_DCHECK(br->val_ == 0); + br->next_in += num; +} + +/* Copies remaining input bytes stored in the bit reader to the output. Value + |num| may not be larger than BrotliGetRemainingBytes. The bit reader must be + warmed up again after this. */ +static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest, + BrotliBitReader* br, size_t num) { + while (BrotliGetAvailableBits(br) >= 8 && num > 0) { + *dest = (uint8_t)BrotliGetBitsUnmasked(br); + BrotliDropBits(br, 8); + ++dest; + --num; + } + BrotliBitReaderNormalize(br); + if (num > 0) { + memcpy(dest, br->next_in, num); + BrotliDropBytes(br, num); + } +} + +BROTLI_UNUSED_FUNCTION void BrotliBitReaderSuppressUnusedFunctions(void) { + BROTLI_UNUSED(&BrotliBitReaderSuppressUnusedFunctions); + + BROTLI_UNUSED(&BrotliBitReaderGetAvailIn); + BROTLI_UNUSED(&BrotliBitReaderLoadBits); + BROTLI_UNUSED(&BrotliBitReaderRestoreState); + BROTLI_UNUSED(&BrotliBitReaderSaveState); + BROTLI_UNUSED(&BrotliBitReaderSetInput); + BROTLI_UNUSED(&BrotliBitReaderUnload); + BROTLI_UNUSED(&BrotliCheckInputAmount); + BROTLI_UNUSED(&BrotliCopyBytes); + BROTLI_UNUSED(&BrotliFillBitWindow16); + BROTLI_UNUSED(&BrotliGet16BitsUnmasked); + BROTLI_UNUSED(&BrotliGetBits); + BROTLI_UNUSED(&BrotliGetRemainingBytes); + BROTLI_UNUSED(&BrotliJumpToByteBoundary); + BROTLI_UNUSED(&BrotliReadBits24); + BROTLI_UNUSED(&BrotliReadBits32); + BROTLI_UNUSED(&BrotliSafeGetBits); + BROTLI_UNUSED(&BrotliSafeReadBits); + BROTLI_UNUSED(&BrotliSafeReadBits32); +} + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif + +#endif /* BROTLI_DEC_BIT_READER_H_ */ diff --git a/modules/brotli/dec/decode.c b/modules/brotli/dec/decode.c new file mode 100644 index 0000000000..220c7e85c6 --- /dev/null +++ b/modules/brotli/dec/decode.c @@ -0,0 +1,2875 @@ +/* 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 /* free, malloc */ +#include /* memcpy, memset */ + +#include "../common/constants.h" +#include "../common/context.h" +#include "../common/dictionary.h" +#include "../common/platform.h" +#include "../common/shared_dictionary_internal.h" +#include "../common/transform.h" +#include "../common/version.h" +#include "bit_reader.h" +#include "huffman.h" +#include "prefix.h" +#include "state.h" + +#if defined(BROTLI_TARGET_NEON) +#include +#endif + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE) + +#define BROTLI_LOG_UINT(name) \ + BROTLI_LOG(("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name))) +#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \ + BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \ + (unsigned long)(idx), (unsigned long)array_name[idx])) + +#define HUFFMAN_TABLE_BITS 8U +#define HUFFMAN_TABLE_MASK 0xFF + +/* We need the slack region for the following reasons: + - doing up to two 16-byte copies for fast backward copying + - inserting transformed dictionary word: + 255 prefix + 32 base + 255 suffix */ +static const brotli_reg_t kRingBufferWriteAheadSlack = 542; + +static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = { + 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, +}; + +/* 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, +}; + +BROTLI_BOOL BrotliDecoderSetParameter( + BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) { + if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE; + switch (p) { + case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION: + state->canny_ringbuffer_allocation = !!value ? 0 : 1; + return BROTLI_TRUE; + + case BROTLI_DECODER_PARAM_LARGE_WINDOW: + state->large_window = TO_BROTLI_BOOL(!!value); + return BROTLI_TRUE; + + default: return BROTLI_FALSE; + } +} + +BrotliDecoderState* BrotliDecoderCreateInstance( + brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { + BrotliDecoderState* state = 0; + if (!alloc_func && !free_func) { + state = (BrotliDecoderState*)malloc(sizeof(BrotliDecoderState)); + } else if (alloc_func && free_func) { + state = (BrotliDecoderState*)alloc_func(opaque, sizeof(BrotliDecoderState)); + } + if (state == 0) { + BROTLI_DUMP(); + return 0; + } + if (!BrotliDecoderStateInit(state, alloc_func, free_func, opaque)) { + BROTLI_DUMP(); + if (!alloc_func && !free_func) { + free(state); + } else if (alloc_func && free_func) { + free_func(opaque, state); + } + return 0; + } + return state; +} + +/* Deinitializes and frees BrotliDecoderState instance. */ +void BrotliDecoderDestroyInstance(BrotliDecoderState* state) { + if (!state) { + return; + } else { + brotli_free_func free_func = state->free_func; + void* opaque = state->memory_manager_opaque; + BrotliDecoderStateCleanup(state); + free_func(opaque, state); + } +} + +/* Saves error code and converts it to BrotliDecoderResult. */ +static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode( + BrotliDecoderState* s, BrotliDecoderErrorCode e, size_t consumed_input) { + s->error_code = (int)e; + s->used_input += consumed_input; + if ((s->buffer_length != 0) && (s->br.next_in == s->br.last_in)) { + /* If internal buffer is depleted at last, reset it. */ + s->buffer_length = 0; + } + switch (e) { + case BROTLI_DECODER_SUCCESS: + return BROTLI_DECODER_RESULT_SUCCESS; + + case BROTLI_DECODER_NEEDS_MORE_INPUT: + return BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT; + + case BROTLI_DECODER_NEEDS_MORE_OUTPUT: + return BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT; + + default: + return BROTLI_DECODER_RESULT_ERROR; + } +} + +/* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli". + Precondition: bit-reader accumulator has at least 8 bits. */ +static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s, + BrotliBitReader* br) { + brotli_reg_t n; + BROTLI_BOOL large_window = s->large_window; + s->large_window = BROTLI_FALSE; + BrotliTakeBits(br, 1, &n); + if (n == 0) { + s->window_bits = 16; + return BROTLI_DECODER_SUCCESS; + } + BrotliTakeBits(br, 3, &n); + if (n != 0) { + s->window_bits = (17u + n) & 63u; + return BROTLI_DECODER_SUCCESS; + } + BrotliTakeBits(br, 3, &n); + if (n == 1) { + if (large_window) { + BrotliTakeBits(br, 1, &n); + if (n == 1) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + } + s->large_window = BROTLI_TRUE; + return BROTLI_DECODER_SUCCESS; + } else { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + } + } + if (n != 0) { + s->window_bits = (8u + n) & 63u; + return BROTLI_DECODER_SUCCESS; + } + s->window_bits = 17; + return BROTLI_DECODER_SUCCESS; +} + +static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) { +#if defined(BROTLI_TARGET_NEON) + vst1q_u8(dst, vld1q_u8(src)); +#else + uint32_t buffer[4]; + memcpy(buffer, src, 16); + memcpy(dst, buffer, 16); +#endif +} + +/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */ +static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8( + BrotliDecoderState* s, BrotliBitReader* br, brotli_reg_t* value) { + brotli_reg_t bits; + switch (s->substate_decode_uint8) { + case BROTLI_STATE_DECODE_UINT8_NONE: + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits == 0) { + *value = 0; + return BROTLI_DECODER_SUCCESS; + } + /* Fall through. */ + + case BROTLI_STATE_DECODE_UINT8_SHORT: + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) { + s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits == 0) { + *value = 1; + s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; + return BROTLI_DECODER_SUCCESS; + } + /* Use output value as a temporary storage. It MUST be persisted. */ + *value = bits; + /* Fall through. */ + + case BROTLI_STATE_DECODE_UINT8_LONG: + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) { + s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + *value = (1U << *value) + bits; + s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; + return BROTLI_DECODER_SUCCESS; + + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); /* COV_NF_LINE */ + } +} + +/* Decodes a metablock length and flags by reading 2 - 31 bits. */ +static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( + BrotliDecoderState* s, BrotliBitReader* br) { + brotli_reg_t bits; + int i; + for (;;) { + switch (s->substate_metablock_header) { + case BROTLI_STATE_METABLOCK_HEADER_NONE: + if (!BrotliSafeReadBits(br, 1, &bits)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + s->is_last_metablock = bits ? 1 : 0; + 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; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER_EMPTY: + if (!BrotliSafeReadBits(br, 1, &bits)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits) { + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; + return BROTLI_DECODER_SUCCESS; + } + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER_NIBBLES: + if (!BrotliSafeReadBits(br, 2, &bits)) { + return BROTLI_DECODER_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; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER_SIZE: + i = s->loop_counter; + for (; i < (int)s->size_nibbles; ++i) { + if (!BrotliSafeReadBits(br, 4, &bits)) { + s->loop_counter = i; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 4 && + bits == 0) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE); + } + s->meta_block_remaining_len |= (int)(bits << (i * 4)); + } + s->substate_metablock_header = + BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED: + if (!s->is_last_metablock) { + if (!BrotliSafeReadBits(br, 1, &bits)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + s->is_uncompressed = bits ? 1 : 0; + } + ++s->meta_block_remaining_len; + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; + return BROTLI_DECODER_SUCCESS; + + case BROTLI_STATE_METABLOCK_HEADER_RESERVED: + if (!BrotliSafeReadBits(br, 1, &bits)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits != 0) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED); + } + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER_BYTES: + if (!BrotliSafeReadBits(br, 2, &bits)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits == 0) { + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; + return BROTLI_DECODER_SUCCESS; + } + s->size_nibbles = (uint8_t)bits; + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER_METADATA: + i = s->loop_counter; + for (; i < (int)s->size_nibbles; ++i) { + if (!BrotliSafeReadBits(br, 8, &bits)) { + s->loop_counter = i; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 1 && + bits == 0) { + return BROTLI_FAILURE( + BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE); + } + s->meta_block_remaining_len |= (int)(bits << (i * 8)); + } + ++s->meta_block_remaining_len; + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; + return BROTLI_DECODER_SUCCESS; + + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); /* COV_NF_LINE */ + } + } +} + +/* 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 brotli_reg_t DecodeSymbol(brotli_reg_t bits, + const HuffmanCode* table, + BrotliBitReader* br) { + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + BROTLI_HC_ADJUST_TABLE_INDEX(table, bits & HUFFMAN_TABLE_MASK); + if (BROTLI_HC_FAST_LOAD_BITS(table) > HUFFMAN_TABLE_BITS) { + brotli_reg_t nbits = BROTLI_HC_FAST_LOAD_BITS(table) - HUFFMAN_TABLE_BITS; + BrotliDropBits(br, HUFFMAN_TABLE_BITS); + BROTLI_HC_ADJUST_TABLE_INDEX(table, + BROTLI_HC_FAST_LOAD_VALUE(table) + + ((bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits))); + } + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table)); + return BROTLI_HC_FAST_LOAD_VALUE(table); +} + +/* Reads and decodes the next Huffman code from bit-stream. + This method peeks 16 bits of input and drops 0 - 15 of them. */ +static BROTLI_INLINE brotli_reg_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 BROTLI_BOOL SafeDecodeSymbol( + const HuffmanCode* table, BrotliBitReader* br, brotli_reg_t* result) { + brotli_reg_t val; + brotli_reg_t available_bits = BrotliGetAvailableBits(br); + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + if (available_bits == 0) { + if (BROTLI_HC_FAST_LOAD_BITS(table) == 0) { + *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; + } + return BROTLI_FALSE; /* No valid bits at all. */ + } + val = BrotliGetBitsUnmasked(br); + BROTLI_HC_ADJUST_TABLE_INDEX(table, val & HUFFMAN_TABLE_MASK); + if (BROTLI_HC_FAST_LOAD_BITS(table) <= HUFFMAN_TABLE_BITS) { + if (BROTLI_HC_FAST_LOAD_BITS(table) <= available_bits) { + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table)); + *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; + } else { + return BROTLI_FALSE; /* Not enough bits for the first level. */ + } + } + if (available_bits <= HUFFMAN_TABLE_BITS) { + return BROTLI_FALSE; /* Not enough bits to move to the second level. */ + } + + /* Speculatively drop HUFFMAN_TABLE_BITS. */ + val = (val & BitMask(BROTLI_HC_FAST_LOAD_BITS(table))) >> HUFFMAN_TABLE_BITS; + available_bits -= HUFFMAN_TABLE_BITS; + BROTLI_HC_ADJUST_TABLE_INDEX(table, BROTLI_HC_FAST_LOAD_VALUE(table) + val); + if (available_bits < BROTLI_HC_FAST_LOAD_BITS(table)) { + return BROTLI_FALSE; /* Not enough bits for the second level. */ + } + + BrotliDropBits(br, HUFFMAN_TABLE_BITS + BROTLI_HC_FAST_LOAD_BITS(table)); + *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; +} + +static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol( + const HuffmanCode* table, BrotliBitReader* br, brotli_reg_t* result) { + brotli_reg_t val; + if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) { + *result = DecodeSymbol(val, table, br); + return BROTLI_TRUE; + } + 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, + brotli_reg_t* bits, + brotli_reg_t* value) { + if (safe) { + return; + } + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + BROTLI_HC_ADJUST_TABLE_INDEX(table, BrotliGetBits(br, HUFFMAN_TABLE_BITS)); + *bits = BROTLI_HC_FAST_LOAD_BITS(table); + *value = BROTLI_HC_FAST_LOAD_VALUE(table); +} + +/* Decodes the next Huffman code using data prepared by PreloadSymbol. + Reads 0 - 15 bits. Also peeks 8 following bits. */ +static BROTLI_INLINE brotli_reg_t ReadPreloadedSymbol(const HuffmanCode* table, + BrotliBitReader* br, + brotli_reg_t* bits, + brotli_reg_t* value) { + brotli_reg_t result = *value; + if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) { + brotli_reg_t val = BrotliGet16BitsUnmasked(br); + const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value; + brotli_reg_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS)); + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(ext); + BrotliDropBits(br, HUFFMAN_TABLE_BITS); + BROTLI_HC_ADJUST_TABLE_INDEX(ext, (val >> HUFFMAN_TABLE_BITS) & mask); + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(ext)); + result = BROTLI_HC_FAST_LOAD_VALUE(ext); + } else { + BrotliDropBits(br, *bits); + } + PreloadSymbol(0, table, br, bits, value); + return result; +} + +static BROTLI_INLINE brotli_reg_t Log2Floor(brotli_reg_t x) { + brotli_reg_t result = 0; + while (x) { + x >>= 1; + ++result; + } + return result; +} + +/* Reads (s->symbol + 1) symbols. + Totally 1..4 symbols are read, 1..11 bits each. + The list of symbols MUST NOT contain duplicates. */ +static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols( + brotli_reg_t alphabet_size_max, brotli_reg_t alphabet_size_limit, + BrotliDecoderState* s) { + /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */ + BrotliBitReader* br = &s->br; + BrotliMetablockHeaderArena* h = &s->arena.header; + brotli_reg_t max_bits = Log2Floor(alphabet_size_max - 1); + brotli_reg_t i = h->sub_loop_counter; + brotli_reg_t num_symbols = h->symbol; + while (i <= num_symbols) { + brotli_reg_t v; + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) { + h->sub_loop_counter = i; + h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (v >= alphabet_size_limit) { + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET); + } + h->symbols_lists_array[i] = (uint16_t)v; + BROTLI_LOG_UINT(h->symbols_lists_array[i]); + ++i; + } + + for (i = 0; i < num_symbols; ++i) { + brotli_reg_t k = i + 1; + for (; k <= num_symbols; ++k) { + if (h->symbols_lists_array[i] == h->symbols_lists_array[k]) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME); + } + } + } + + return BROTLI_DECODER_SUCCESS; +} + +/* Process single decoded symbol code length: + A) reset the repeat variable + B) remember code length (if it is not 0) + C) extend corresponding index-chain + D) reduce the Huffman space + E) update the histogram */ +static BROTLI_INLINE void ProcessSingleCodeLength(brotli_reg_t code_len, + brotli_reg_t* symbol, brotli_reg_t* repeat, brotli_reg_t* space, + brotli_reg_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]++; + BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n", + (int)*symbol, (int)code_len)); + } + (*symbol)++; +} + +/* Process repeated symbol code length. + A) Check if it is the extension of previous repeat sequence; if the decoded + value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new + symbol-skip + B) Update repeat variable + C) Check if operation is feasible (fits alphabet) + D) For each symbol do the same operations as in ProcessSingleCodeLength + + PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or + code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH */ +static BROTLI_INLINE void ProcessRepeatedCodeLength(brotli_reg_t code_len, + brotli_reg_t repeat_delta, brotli_reg_t alphabet_size, brotli_reg_t* symbol, + brotli_reg_t* repeat, brotli_reg_t* space, brotli_reg_t* prev_code_len, + brotli_reg_t* repeat_code_len, uint16_t* symbol_lists, + uint16_t* code_length_histo, int* next_symbol) { + brotli_reg_t old_repeat; + brotli_reg_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ + brotli_reg_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ + if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { + new_len = *prev_code_len; + extra_bits = 2; + } + if (*repeat_code_len != new_len) { + *repeat = 0; + *repeat_code_len = new_len; + } + old_repeat = *repeat; + if (*repeat > 0) { + *repeat -= 2; + *repeat <<= extra_bits; + } + *repeat += repeat_delta + 3U; + repeat_delta = *repeat - old_repeat; + if (*symbol + repeat_delta > alphabet_size) { + BROTLI_DUMP(); + *symbol = alphabet_size; + *space = 0xFFFFF; + return; + } + BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n", + (int)*symbol, (int)(*symbol + repeat_delta - 1), (int)*repeat_code_len)); + if (*repeat_code_len != 0) { + brotli_reg_t 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 BrotliDecoderErrorCode ReadSymbolCodeLengths( + brotli_reg_t alphabet_size, BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BrotliMetablockHeaderArena* h = &s->arena.header; + brotli_reg_t symbol = h->symbol; + brotli_reg_t repeat = h->repeat; + brotli_reg_t space = h->space; + brotli_reg_t prev_code_len = h->prev_code_len; + brotli_reg_t repeat_code_len = h->repeat_code_len; + uint16_t* symbol_lists = h->symbol_lists; + uint16_t* code_length_histo = h->code_length_histo; + int* next_symbol = h->next_symbol; + if (!BrotliWarmupBitReader(br)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + while (symbol < alphabet_size && space > 0) { + const HuffmanCode* p = h->table; + brotli_reg_t code_len; + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p); + if (!BrotliCheckInputAmount(br)) { + h->symbol = symbol; + h->repeat = repeat; + h->prev_code_len = prev_code_len; + h->repeat_code_len = repeat_code_len; + h->space = space; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BrotliFillBitWindow16(br); + BROTLI_HC_ADJUST_TABLE_INDEX(p, BrotliGetBitsUnmasked(br) & + BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH)); + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); /* Use 1..5 bits. */ + code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */ + if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { + ProcessSingleCodeLength(code_len, &symbol, &repeat, &space, + &prev_code_len, symbol_lists, code_length_histo, next_symbol); + } else { /* code_len == 16..17, extra_bits == 2..3 */ + brotli_reg_t extra_bits = + (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3; + brotli_reg_t repeat_delta = + BrotliGetBitsUnmasked(br) & BitMask(extra_bits); + BrotliDropBits(br, extra_bits); + ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, + &symbol, &repeat, &space, &prev_code_len, &repeat_code_len, + symbol_lists, code_length_histo, next_symbol); + } + } + h->space = space; + return BROTLI_DECODER_SUCCESS; +} + +static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( + brotli_reg_t alphabet_size, BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BrotliMetablockHeaderArena* h = &s->arena.header; + BROTLI_BOOL get_byte = BROTLI_FALSE; + while (h->symbol < alphabet_size && h->space > 0) { + const HuffmanCode* p = h->table; + brotli_reg_t code_len; + brotli_reg_t available_bits; + brotli_reg_t bits = 0; + BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p); + if (get_byte && !BrotliPullByte(br)) return BROTLI_DECODER_NEEDS_MORE_INPUT; + get_byte = BROTLI_FALSE; + available_bits = BrotliGetAvailableBits(br); + if (available_bits != 0) { + bits = (uint32_t)BrotliGetBitsUnmasked(br); + } + BROTLI_HC_ADJUST_TABLE_INDEX(p, + bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH)); + if (BROTLI_HC_FAST_LOAD_BITS(p) > available_bits) { + get_byte = BROTLI_TRUE; + continue; + } + code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */ + if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); + ProcessSingleCodeLength(code_len, &h->symbol, &h->repeat, &h->space, + &h->prev_code_len, h->symbol_lists, h->code_length_histo, + h->next_symbol); + } else { /* code_len == 16..17, extra_bits == 2..3 */ + brotli_reg_t extra_bits = code_len - 14U; + brotli_reg_t repeat_delta = (bits >> BROTLI_HC_FAST_LOAD_BITS(p)) & + BitMask(extra_bits); + if (available_bits < BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits) { + get_byte = BROTLI_TRUE; + continue; + } + BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits); + ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, + &h->symbol, &h->repeat, &h->space, &h->prev_code_len, + &h->repeat_code_len, h->symbol_lists, h->code_length_histo, + h->next_symbol); + } + } + return BROTLI_DECODER_SUCCESS; +} + +/* Reads and decodes 15..18 codes using static prefix code. + Each code is 2..4 bits long. In total 30..72 bits are used. */ +static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BrotliMetablockHeaderArena* h = &s->arena.header; + brotli_reg_t num_codes = h->repeat; + brotli_reg_t space = h->space; + brotli_reg_t i = h->sub_loop_counter; + for (; i < BROTLI_CODE_LENGTH_CODES; ++i) { + const uint8_t code_len_idx = kCodeLengthCodeOrder[i]; + brotli_reg_t ix; + brotli_reg_t v; + if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) { + brotli_reg_t available_bits = BrotliGetAvailableBits(br); + if (available_bits != 0) { + ix = BrotliGetBitsUnmasked(br) & 0xF; + } else { + ix = 0; + } + if (kCodeLengthPrefixLength[ix] > available_bits) { + h->sub_loop_counter = i; + h->repeat = num_codes; + h->space = space; + h->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + } + v = kCodeLengthPrefixValue[ix]; + BrotliDropBits(br, kCodeLengthPrefixLength[ix]); + h->code_length_code_lengths[code_len_idx] = (uint8_t)v; + BROTLI_LOG_ARRAY_INDEX(h->code_length_code_lengths, code_len_idx); + if (v != 0) { + space = space - (32U >> v); + ++num_codes; + ++h->code_length_histo[v]; + if (space - 1U >= 32U) { + /* space is 0 or wrapped around. */ + break; + } + } + } + if (!(num_codes == 1 || space == 0)) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE); + } + return BROTLI_DECODER_SUCCESS; +} + +/* Decodes the Huffman tables. + There are 2 scenarios: + A) Huffman code contains only few symbols (1..4). Those symbols are read + directly; their code lengths are defined by the number of symbols. + For this scenario 4 - 49 bits will be read. + + B) 2-phase decoding: + B.1) Small Huffman table is decoded; it is specified with code lengths + encoded with predefined entropy code. 32 - 74 bits are used. + B.2) Decoded table is used to decode code lengths of symbols in resulting + Huffman table. In worst case 3520 bits are read. */ +static BrotliDecoderErrorCode ReadHuffmanCode(brotli_reg_t alphabet_size_max, + brotli_reg_t alphabet_size_limit, + HuffmanCode* table, + brotli_reg_t* opt_table_size, + BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BrotliMetablockHeaderArena* h = &s->arena.header; + /* State machine. */ + for (;;) { + switch (h->substate_huffman) { + case BROTLI_STATE_HUFFMAN_NONE: + if (!BrotliSafeReadBits(br, 2, &h->sub_loop_counter)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BROTLI_LOG_UINT(h->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 (h->sub_loop_counter != 1) { + h->space = 32; + h->repeat = 0; /* num_codes */ + memset(&h->code_length_histo[0], 0, sizeof(h->code_length_histo[0]) * + (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1)); + memset(&h->code_length_code_lengths[0], 0, + sizeof(h->code_length_code_lengths)); + h->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; + continue; + } + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE: + /* Read symbols, codes & code lengths directly. */ + if (!BrotliSafeReadBits(br, 2, &h->symbol)) { /* num_symbols */ + h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + h->sub_loop_counter = 0; + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { + BrotliDecoderErrorCode result = + ReadSimpleHuffmanSymbols(alphabet_size_max, alphabet_size_limit, s); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + } + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: { + brotli_reg_t table_size; + if (h->symbol == 3) { + brotli_reg_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { + h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + h->symbol += bits; + } + BROTLI_LOG_UINT(h->symbol); + table_size = BrotliBuildSimpleHuffmanTable(table, HUFFMAN_TABLE_BITS, + h->symbols_lists_array, + (uint32_t)h->symbol); + if (opt_table_size) { + *opt_table_size = table_size; + } + h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; + } + + /* Decode Huffman-coded code lengths. */ + case BROTLI_STATE_HUFFMAN_COMPLEX: { + brotli_reg_t i; + BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + BrotliBuildCodeLengthsHuffmanTable(h->table, + h->code_length_code_lengths, + h->code_length_histo); + memset(&h->code_length_histo[0], 0, sizeof(h->code_length_histo)); + for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) { + h->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); + h->symbol_lists[h->next_symbol[i]] = 0xFFFF; + } + + h->symbol = 0; + h->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH; + h->repeat = 0; + h->repeat_code_len = 0; + h->space = 32768; + h->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; + } + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: { + brotli_reg_t table_size; + BrotliDecoderErrorCode result = ReadSymbolCodeLengths( + alphabet_size_limit, s); + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + result = SafeReadSymbolCodeLengths(alphabet_size_limit, s); + } + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + + if (h->space != 0) { + BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)h->space)); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE); + } + table_size = BrotliBuildHuffmanTable( + table, HUFFMAN_TABLE_BITS, h->symbol_lists, h->code_length_histo); + if (opt_table_size) { + *opt_table_size = table_size; + } + h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; + } + + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); /* COV_NF_LINE */ + } + } +} + +/* Decodes a block length by reading 3..39 bits. */ +static BROTLI_INLINE brotli_reg_t ReadBlockLength(const HuffmanCode* table, + BrotliBitReader* br) { + brotli_reg_t code; + brotli_reg_t nbits; + code = ReadSymbol(table, br); + nbits = _kBrotliPrefixCodeRanges[code].nbits; /* nbits == 2..24 */ + return _kBrotliPrefixCodeRanges[code].offset + BrotliReadBits24(br, nbits); +} + +/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then + reading can't be continued with ReadBlockLength. */ +static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( + BrotliDecoderState* s, brotli_reg_t* result, const HuffmanCode* table, + BrotliBitReader* br) { + brotli_reg_t index; + if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) { + if (!SafeReadSymbol(table, br, &index)) { + return BROTLI_FALSE; + } + } else { + index = s->block_length_index; + } + { + brotli_reg_t bits; + brotli_reg_t nbits = _kBrotliPrefixCodeRanges[index].nbits; + brotli_reg_t offset = _kBrotliPrefixCodeRanges[index].offset; + if (!BrotliSafeReadBits(br, nbits, &bits)) { + s->block_length_index = index; + s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX; + return BROTLI_FALSE; + } + *result = offset + bits; + s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; + return BROTLI_TRUE; + } +} + +/* 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, brotli_reg_t v_len, BrotliDecoderState* state) { + /* Reinitialize elements that could have been changed. */ + brotli_reg_t i = 1; + brotli_reg_t upper_bound = state->mtf_upper_bound; + uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */ + uint8_t* mtf_u8 = (uint8_t*)mtf; + /* Load endian-aware constant. */ + const uint8_t b0123[4] = {0, 1, 2, 3}; + uint32_t pattern; + memcpy(&pattern, &b0123, 4); + + /* Initialize list using 4 consequent values pattern. */ + mtf[0] = pattern; + do { + pattern += 0x04040404; /* Advance all 4 values by 4. */ + mtf[i] = pattern; + i++; + } while (i <= upper_bound); + + /* Transform the input. */ + upper_bound = 0; + for (i = 0; i < v_len; ++i) { + int index = v[i]; + uint8_t value = mtf_u8[index]; + upper_bound |= v[i]; + v[i] = value; + mtf_u8[-1] = value; + do { + index--; + mtf_u8[index + 1] = mtf_u8[index]; + } while (index >= 0); + } + /* Remember amount of elements to be reinitialized. */ + state->mtf_upper_bound = upper_bound >> 2; +} + +/* Decodes a series of Huffman table using ReadHuffmanCode function. */ +static BrotliDecoderErrorCode HuffmanTreeGroupDecode( + HuffmanTreeGroup* group, BrotliDecoderState* s) { + BrotliMetablockHeaderArena* h = &s->arena.header; + if (h->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) { + h->next = group->codes; + h->htree_index = 0; + h->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP; + } + while (h->htree_index < group->num_htrees) { + brotli_reg_t table_size; + BrotliDecoderErrorCode result = ReadHuffmanCode(group->alphabet_size_max, + group->alphabet_size_limit, h->next, &table_size, s); + if (result != BROTLI_DECODER_SUCCESS) return result; + group->htrees[h->htree_index] = h->next; + h->next += table_size; + ++h->htree_index; + } + h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; + return BROTLI_DECODER_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 BrotliDecoderErrorCode DecodeContextMap(brotli_reg_t context_map_size, + brotli_reg_t* num_htrees, + uint8_t** context_map_arg, + BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; + BrotliMetablockHeaderArena* h = &s->arena.header; + + switch ((int)h->substate_context_map) { + case BROTLI_STATE_CONTEXT_MAP_NONE: + result = DecodeVarLenUint8(s, br, num_htrees); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + (*num_htrees)++; + h->context_index = 0; + BROTLI_LOG_UINT(context_map_size); + BROTLI_LOG_UINT(*num_htrees); + *context_map_arg = + (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)context_map_size); + if (*context_map_arg == 0) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP); + } + if (*num_htrees <= 1) { + memset(*context_map_arg, 0, (size_t)context_map_size); + return BROTLI_DECODER_SUCCESS; + } + h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: { + brotli_reg_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_DECODER_NEEDS_MORE_INPUT; + } + if ((bits & 1) != 0) { /* Use RLE for zeros. */ + h->max_run_length_prefix = (bits >> 1) + 1; + BrotliDropBits(br, 5); + } else { + h->max_run_length_prefix = 0; + BrotliDropBits(br, 1); + } + BROTLI_LOG_UINT(h->max_run_length_prefix); + h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN; + } + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_HUFFMAN: { + brotli_reg_t alphabet_size = *num_htrees + h->max_run_length_prefix; + result = ReadHuffmanCode(alphabet_size, alphabet_size, + h->context_map_table, NULL, s); + if (result != BROTLI_DECODER_SUCCESS) return result; + h->code = 0xFFFF; + h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE; + } + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_DECODE: { + brotli_reg_t context_index = h->context_index; + brotli_reg_t max_run_length_prefix = h->max_run_length_prefix; + uint8_t* context_map = *context_map_arg; + brotli_reg_t code = h->code; + BROTLI_BOOL skip_preamble = (code != 0xFFFF); + while (context_index < context_map_size || skip_preamble) { + if (!skip_preamble) { + if (!SafeReadSymbol(h->context_map_table, br, &code)) { + h->code = 0xFFFF; + h->context_index = context_index; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BROTLI_LOG_UINT(code); + + if (code == 0) { + context_map[context_index++] = 0; + continue; + } + if (code > max_run_length_prefix) { + context_map[context_index++] = + (uint8_t)(code - max_run_length_prefix); + continue; + } + } else { + skip_preamble = BROTLI_FALSE; + } + /* RLE sub-stage. */ + { + brotli_reg_t reps; + if (!BrotliSafeReadBits(br, code, &reps)) { + h->code = code; + h->context_index = context_index; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + reps += 1U << code; + BROTLI_LOG_UINT(reps); + if (context_index + reps > context_map_size) { + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT); + } + do { + context_map[context_index++] = 0; + } while (--reps); + } + } + } + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: { + brotli_reg_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { + h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits != 0) { + InverseMoveToFrontTransform(*context_map_arg, context_map_size, s); + } + h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; + return BROTLI_DECODER_SUCCESS; + } + + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); /* COV_NF_LINE */ + } +} + +/* Decodes a command or literal and updates block type ring-buffer. + Reads 3..54 bits. */ +static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength( + int safe, BrotliDecoderState* s, int tree_type) { + brotli_reg_t max_block_type = s->num_block_types[tree_type]; + const HuffmanCode* type_tree = &s->block_type_trees[ + tree_type * BROTLI_HUFFMAN_MAX_SIZE_258]; + const HuffmanCode* len_tree = &s->block_len_trees[ + tree_type * BROTLI_HUFFMAN_MAX_SIZE_26]; + BrotliBitReader* br = &s->br; + brotli_reg_t* ringbuffer = &s->block_type_rb[tree_type * 2]; + brotli_reg_t block_type; + if (max_block_type <= 1) { + return BROTLI_FALSE; + } + + /* 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 BROTLI_FALSE; + if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) { + s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; + BrotliBitReaderRestoreState(br, &memento); + return BROTLI_FALSE; + } + } + + 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 BROTLI_TRUE; +} + +static BROTLI_INLINE void DetectTrivialLiteralBlockTypes( + BrotliDecoderState* s) { + size_t i; + for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0; + for (i = 0; i < s->num_block_types[0]; i++) { + size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS; + size_t error = 0; + size_t sample = s->context_map[offset]; + size_t j; + for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) { + /* NOLINTNEXTLINE(bugprone-macro-repeated-side-effects) */ + BROTLI_REPEAT_4({ error |= s->context_map[offset + j++] ^ sample; }) + } + if (error == 0) { + s->trivial_literal_contexts[i >> 5] |= 1u << (i & 31); + } + } +} + +static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) { + uint8_t context_mode; + size_t trivial; + brotli_reg_t block_type = s->block_type_rb[1]; + brotli_reg_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS; + s->context_map_slice = s->context_map + context_offset; + trivial = s->trivial_literal_contexts[block_type >> 5]; + s->trivial_literal_context = (trivial >> (block_type & 31)) & 1; + s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]]; + context_mode = s->context_modes[block_type] & 3; + s->context_lookup = BROTLI_CONTEXT_LUT(context_mode); +} + +/* Decodes the block type and updates the state for literal context. + Reads 3..54 bits. */ +static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal( + int safe, BrotliDecoderState* s) { + if (!DecodeBlockTypeAndLength(safe, s, 0)) { + return BROTLI_FALSE; + } + PrepareLiteralDecoding(s); + return BROTLI_TRUE; +} + +static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) { + DecodeLiteralBlockSwitchInternal(0, s); +} + +static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch( + BrotliDecoderState* s) { + return DecodeLiteralBlockSwitchInternal(1, s); +} + +/* Block switch for insert/copy length. + Reads 3..54 bits. */ +static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal( + int safe, BrotliDecoderState* s) { + if (!DecodeBlockTypeAndLength(safe, s, 1)) { + return BROTLI_FALSE; + } + s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]]; + return BROTLI_TRUE; +} + +static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) { + DecodeCommandBlockSwitchInternal(0, s); +} + +static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch( + BrotliDecoderState* s) { + return DecodeCommandBlockSwitchInternal(1, s); +} + +/* Block switch for distance codes. + Reads 3..54 bits. */ +static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal( + int safe, BrotliDecoderState* s) { + if (!DecodeBlockTypeAndLength(safe, s, 2)) { + return BROTLI_FALSE; + } + s->dist_context_map_slice = s->dist_context_map + + (s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS); + s->dist_htree_index = s->dist_context_map_slice[s->distance_context]; + return BROTLI_TRUE; +} + +static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) { + DecodeDistanceBlockSwitchInternal(0, s); +} + +static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch( + BrotliDecoderState* s) { + return DecodeDistanceBlockSwitchInternal(1, s); +} + +static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) { + size_t pos = wrap && s->pos > s->ringbuffer_size ? + (size_t)s->ringbuffer_size : (size_t)(s->pos); + size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos; + return partial_pos_rb - s->partial_pos_out; +} + +/* Dumps output. + Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push + and either ring-buffer is as big as window size, or |force| is true. */ +static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer( + BrotliDecoderState* s, size_t* available_out, uint8_t** next_out, + size_t* total_out, BROTLI_BOOL force) { + uint8_t* start = + s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask); + size_t to_write = UnwrittenBytes(s, BROTLI_TRUE); + size_t num_written = *available_out; + if (num_written > to_write) { + num_written = to_write; + } + if (s->meta_block_remaining_len < 0) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1); + } + if (next_out && !*next_out) { + *next_out = start; + } else { + if (next_out) { + memcpy(*next_out, start, num_written); + *next_out += num_written; + } + } + *available_out -= num_written; + BROTLI_LOG_UINT(to_write); + BROTLI_LOG_UINT(num_written); + s->partial_pos_out += num_written; + if (total_out) { + *total_out = s->partial_pos_out; + } + if (num_written < to_write) { + if (s->ringbuffer_size == (1 << s->window_bits) || force) { + return BROTLI_DECODER_NEEDS_MORE_OUTPUT; + } else { + return BROTLI_DECODER_SUCCESS; + } + } + /* Wrap ring buffer only if it has reached its maximal size. */ + if (s->ringbuffer_size == (1 << s->window_bits) && + s->pos >= s->ringbuffer_size) { + s->pos -= s->ringbuffer_size; + s->rb_roundtrips++; + s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0; + } + return BROTLI_DECODER_SUCCESS; +} + +static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) { + if (s->should_wrap_ringbuffer) { + memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos); + s->should_wrap_ringbuffer = 0; + } +} + +/* Allocates ring-buffer. + + s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before + this function is called. + + Last two bytes of ring-buffer are initialized to 0, so context calculation + could be done uniformly for the first two and all other positions. */ +static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer( + BrotliDecoderState* s) { + uint8_t* old_ringbuffer = s->ringbuffer; + if (s->ringbuffer_size == s->new_ringbuffer_size) { + return BROTLI_TRUE; + } + + s->ringbuffer = (uint8_t*)BROTLI_DECODER_ALLOC(s, + (size_t)(s->new_ringbuffer_size) + kRingBufferWriteAheadSlack); + if (s->ringbuffer == 0) { + /* Restore previous value. */ + s->ringbuffer = old_ringbuffer; + return BROTLI_FALSE; + } + s->ringbuffer[s->new_ringbuffer_size - 2] = 0; + s->ringbuffer[s->new_ringbuffer_size - 1] = 0; + + if (!!old_ringbuffer) { + memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos); + BROTLI_DECODER_FREE(s, old_ringbuffer); + } + + s->ringbuffer_size = s->new_ringbuffer_size; + s->ringbuffer_mask = s->new_ringbuffer_size - 1; + s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size; + + return BROTLI_TRUE; +} + +static BrotliDecoderErrorCode BROTLI_NOINLINE +SkipMetadataBlock(BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + + if (s->meta_block_remaining_len == 0) { + return BROTLI_DECODER_SUCCESS; + } + + BROTLI_DCHECK((BrotliGetAvailableBits(br) & 7) == 0); + + /* Drain accumulator. */ + if (BrotliGetAvailableBits(br) >= 8) { + uint8_t buffer[8]; + int nbytes = (int)(BrotliGetAvailableBits(br)) >> 3; + BROTLI_DCHECK(nbytes <= 8); + if (nbytes > s->meta_block_remaining_len) { + nbytes = s->meta_block_remaining_len; + } + BrotliCopyBytes(buffer, br, (size_t)nbytes); + if (s->metadata_chunk_func) { + s->metadata_chunk_func(s->metadata_callback_opaque, buffer, + (size_t)nbytes); + } + s->meta_block_remaining_len -= nbytes; + if (s->meta_block_remaining_len == 0) { + return BROTLI_DECODER_SUCCESS; + } + } + + /* Direct access to metadata is possible. */ + int nbytes = (int)BrotliGetRemainingBytes(br); + if (nbytes > s->meta_block_remaining_len) { + nbytes = s->meta_block_remaining_len; + } + if (nbytes > 0) { + if (s->metadata_chunk_func) { + s->metadata_chunk_func(s->metadata_callback_opaque, br->next_in, + (size_t)nbytes); + } + BrotliDropBytes(br, (size_t)nbytes); + s->meta_block_remaining_len -= nbytes; + if (s->meta_block_remaining_len == 0) { + return BROTLI_DECODER_SUCCESS; + } + } + + BROTLI_DCHECK(BrotliGetRemainingBytes(br) == 0); + + return BROTLI_DECODER_NEEDS_MORE_INPUT; +} + +static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( + size_t* available_out, uint8_t** next_out, size_t* total_out, + BrotliDecoderState* s) { + /* TODO(eustas): avoid allocation for single uncompressed block. */ + if (!BrotliEnsureRingBuffer(s)) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1); + } + + /* 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 ring-buffer. */ + BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes); + s->pos += nbytes; + s->meta_block_remaining_len -= nbytes; + if (s->pos < 1 << s->window_bits) { + if (s->meta_block_remaining_len == 0) { + return BROTLI_DECODER_SUCCESS; + } + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE; + } + /* Fall through. */ + + case BROTLI_STATE_UNCOMPRESSED_WRITE: { + BrotliDecoderErrorCode result; + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_FALSE); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + if (s->ringbuffer_size == 1 << s->window_bits) { + s->max_distance = s->max_backward_distance; + } + s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; + break; + } + } + } + BROTLI_DCHECK(0); /* Unreachable */ +} + +static BROTLI_BOOL AttachCompoundDictionary( + BrotliDecoderState* state, const uint8_t* data, size_t size) { + BrotliDecoderCompoundDictionary* addon = state->compound_dictionary; + if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE; + if (!addon) { + addon = (BrotliDecoderCompoundDictionary*)BROTLI_DECODER_ALLOC( + state, sizeof(BrotliDecoderCompoundDictionary)); + if (!addon) return BROTLI_FALSE; + addon->num_chunks = 0; + addon->total_size = 0; + addon->br_length = 0; + addon->br_copied = 0; + addon->block_bits = -1; + addon->chunk_offsets[0] = 0; + state->compound_dictionary = addon; + } + if (addon->num_chunks == 15) return BROTLI_FALSE; + addon->chunks[addon->num_chunks] = data; + addon->num_chunks++; + addon->total_size += (int)size; + addon->chunk_offsets[addon->num_chunks] = addon->total_size; + return BROTLI_TRUE; +} + +static void EnsureCoumpoundDictionaryInitialized(BrotliDecoderState* state) { + BrotliDecoderCompoundDictionary* addon = state->compound_dictionary; + /* 256 = (1 << 8) slots in block map. */ + int block_bits = 8; + int cursor = 0; + int index = 0; + if (addon->block_bits != -1) return; + while (((addon->total_size - 1) >> block_bits) != 0) block_bits++; + block_bits -= 8; + addon->block_bits = block_bits; + while (cursor < addon->total_size) { + while (addon->chunk_offsets[index + 1] < cursor) index++; + addon->block_map[cursor >> block_bits] = (uint8_t)index; + cursor += 1 << block_bits; + } +} + +static BROTLI_BOOL InitializeCompoundDictionaryCopy(BrotliDecoderState* s, + int address, int length) { + BrotliDecoderCompoundDictionary* addon = s->compound_dictionary; + int index; + EnsureCoumpoundDictionaryInitialized(s); + index = addon->block_map[address >> addon->block_bits]; + while (address >= addon->chunk_offsets[index + 1]) index++; + if (addon->total_size < address + length) return BROTLI_FALSE; + /* 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 -= length; + addon->br_index = index; + addon->br_offset = address - addon->chunk_offsets[index]; + addon->br_length = length; + addon->br_copied = 0; + return BROTLI_TRUE; +} + +static int GetCompoundDictionarySize(BrotliDecoderState* s) { + return s->compound_dictionary ? s->compound_dictionary->total_size : 0; +} + +static int CopyFromCompoundDictionary(BrotliDecoderState* s, int pos) { + BrotliDecoderCompoundDictionary* addon = s->compound_dictionary; + int orig_pos = pos; + while (addon->br_length != addon->br_copied) { + uint8_t* copy_dst = &s->ringbuffer[pos]; + const uint8_t* copy_src = + addon->chunks[addon->br_index] + addon->br_offset; + int space = s->ringbuffer_size - pos; + int rem_chunk_length = (addon->chunk_offsets[addon->br_index + 1] - + addon->chunk_offsets[addon->br_index]) - addon->br_offset; + int length = addon->br_length - addon->br_copied; + if (length > rem_chunk_length) length = rem_chunk_length; + if (length > space) length = space; + memcpy(copy_dst, copy_src, (size_t)length); + pos += length; + addon->br_offset += length; + addon->br_copied += length; + if (length == rem_chunk_length) { + addon->br_index++; + addon->br_offset = 0; + } + if (pos == s->ringbuffer_size) break; + } + return pos - orig_pos; +} + +BROTLI_BOOL BrotliDecoderAttachDictionary( + BrotliDecoderState* state, BrotliSharedDictionaryType type, + size_t data_size, const uint8_t data[BROTLI_ARRAY_PARAM(data_size)]) { + brotli_reg_t i; + brotli_reg_t num_prefix_before = state->dictionary->num_prefix; + if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE; + if (!BrotliSharedDictionaryAttach(state->dictionary, type, data_size, data)) { + return BROTLI_FALSE; + } + for (i = num_prefix_before; i < state->dictionary->num_prefix; i++) { + if (!AttachCompoundDictionary( + state, state->dictionary->prefix[i], + state->dictionary->prefix_size[i])) { + return BROTLI_FALSE; + } + } + return BROTLI_TRUE; +} + +/* Calculates the smallest feasible ring buffer. + + If we know the data size is small, do not allocate more ring buffer + size than needed to reduce memory usage. + + When this method is called, metablock size and flags MUST be decoded. */ +static void BROTLI_NOINLINE BrotliCalculateRingBufferSize( + BrotliDecoderState* s) { + int window_size = 1 << s->window_bits; + int new_ringbuffer_size = window_size; + /* We need at least 2 bytes of ring buffer size to get the last two + bytes for context from there */ + int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024; + int output_size; + + /* If maximum is already reached, no further extension is retired. */ + if (s->ringbuffer_size == window_size) { + return; + } + + /* Metadata blocks does not touch ring buffer. */ + if (s->is_metadata) { + return; + } + + if (!s->ringbuffer) { + output_size = 0; + } else { + output_size = s->pos; + } + output_size += s->meta_block_remaining_len; + min_size = min_size < output_size ? output_size : min_size; + + if (!!s->canny_ringbuffer_allocation) { + /* Reduce ring buffer size to save memory when server is unscrupulous. + In worst case memory usage might be 1.5x bigger for a short period of + ring buffer reallocation. */ + while ((new_ringbuffer_size >> 1) >= min_size) { + new_ringbuffer_size >>= 1; + } + } + + s->new_ringbuffer_size = new_ringbuffer_size; +} + +/* Reads 1..256 2-bit context modes. */ +static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + int i = s->loop_counter; + + while (i < (int)s->num_block_types[0]) { + brotli_reg_t bits; + if (!BrotliSafeReadBits(br, 2, &bits)) { + s->loop_counter = i; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + s->context_modes[i] = (uint8_t)bits; + BROTLI_LOG_ARRAY_INDEX(s->context_modes, i); + i++; + } + return BROTLI_DECODER_SUCCESS; +} + +static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) { + int offset = s->distance_code - 3; + if (s->distance_code <= 3) { + /* Compensate double distance-ring-buffer roll for dictionary items. */ + s->distance_context = 1 >> s->distance_code; + s->distance_code = s->dist_rb[(s->dist_rb_idx - offset) & 3]; + s->dist_rb_idx -= s->distance_context; + } else { + int index_delta = 3; + int delta; + int base = s->distance_code - 10; + if (s->distance_code < 10) { + base = s->distance_code - 4; + } else { + index_delta = 2; + } + /* Unpack one of six 4-bit values. */ + delta = ((0x605142 >> (4 * base)) & 0xF) - 3; + s->distance_code = s->dist_rb[(s->dist_rb_idx + index_delta) & 0x3] + delta; + 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 = 0x7FFFFFFF; + } + } +} + +static BROTLI_INLINE BROTLI_BOOL SafeReadBits( + BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) { + if (n_bits != 0) { + return BrotliSafeReadBits(br, n_bits, val); + } else { + *val = 0; + return BROTLI_TRUE; + } +} + +static BROTLI_INLINE BROTLI_BOOL SafeReadBits32( + BrotliBitReader* const br, brotli_reg_t n_bits, brotli_reg_t* val) { + if (n_bits != 0) { + return BrotliSafeReadBits32(br, n_bits, val); + } else { + *val = 0; + return BROTLI_TRUE; + } +} + +/* + RFC 7932 Section 4 with "..." shortenings and "[]" emendations. + + Each distance ... is represented with a pair ... + The distance code is encoded using a prefix code... The number of extra bits + can be 0..24... Two additional parameters: NPOSTFIX (0..3), and ... + NDIRECT (0..120) ... are encoded in the meta-block header... + + The first 16 distance symbols ... reference past distances... ring buffer ... + Next NDIRECT distance symbols ... represent distances from 1 to NDIRECT... + [For] distance symbols 16 + NDIRECT and greater ... the number of extra bits + ... is given by the following formula: + + [ xcode = dcode - NDIRECT - 16 ] + ndistbits = 1 + [ xcode ] >> (NPOSTFIX + 1) + + ... +*/ + +/* + RFC 7932 Section 9.2 with "..." shortenings and "[]" emendations. + + ... to get the actual value of the parameter NDIRECT, left-shift this + four-bit number by NPOSTFIX bits ... +*/ + +/* Remaining formulas from RFC 7932 Section 4 could be rewritten as following: + + alphabet_size = 16 + NDIRECT + (max_distbits << (NPOSTFIX + 1)) + + half = ((xcode >> NPOSTFIX) & 1) << ndistbits + postfix = xcode & ((1 << NPOSTFIX) - 1) + range_start = 2 * (1 << ndistbits - 1 - 1) + + distance = (range_start + half + extra) << NPOSTFIX + postfix + NDIRECT + 1 + + NB: ndistbits >= 1 -> range_start >= 0 + NB: range_start has factor 2, as the range is covered by 2 "halves" + NB: extra -1 offset in range_start formula covers the absence of + ndistbits = 0 case + NB: when NPOSTFIX = 0, NDIRECT is not greater than 15 + + In other words, xcode has the following binary structure - XXXHPPP: + - XXX represent the number of extra distance bits + - H selects upper / lower range of distances + - PPP represent "postfix" + + "Regular" distance encoding has NPOSTFIX = 0; omitting the postfix part + simplifies distance calculation. + + Using NPOSTFIX > 0 allows cheaper encoding of regular structures, e.g. where + most of distances have the same reminder of division by 2/4/8. For example, + the table of int32_t values that come from different sources; if it is likely + that 3 highest bytes of values from the same source are the same, then + copy distance often looks like 4x + y. + + Distance calculation could be rewritten to: + + ndistbits = NDISTBITS(NDIRECT, NPOSTFIX)[dcode] + distance = OFFSET(NDIRECT, NPOSTFIX)[dcode] + extra << NPOSTFIX + + NDISTBITS and OFFSET could be pre-calculated, as NDIRECT and NPOSTFIX could + change only once per meta-block. +*/ + +/* Calculates distance lookup table. + NB: it is possible to have all 64 tables precalculated. */ +static void CalculateDistanceLut(BrotliDecoderState* s) { + BrotliMetablockBodyArena* b = &s->arena.body; + brotli_reg_t npostfix = s->distance_postfix_bits; + brotli_reg_t ndirect = s->num_direct_distance_codes; + brotli_reg_t alphabet_size_limit = s->distance_hgroup.alphabet_size_limit; + brotli_reg_t postfix = 1u << npostfix; + brotli_reg_t j; + brotli_reg_t bits = 1; + brotli_reg_t half = 0; + + /* Skip short codes. */ + brotli_reg_t i = BROTLI_NUM_DISTANCE_SHORT_CODES; + + /* Fill direct codes. */ + for (j = 0; j < ndirect; ++j) { + b->dist_extra_bits[i] = 0; + b->dist_offset[i] = j + 1; + ++i; + } + + /* Fill regular distance codes. */ + while (i < alphabet_size_limit) { + brotli_reg_t base = ndirect + ((((2 + half) << bits) - 4) << npostfix) + 1; + /* Always fill the complete group. */ + for (j = 0; j < postfix; ++j) { + b->dist_extra_bits[i] = (uint8_t)bits; + b->dist_offset[i] = base + j; + ++i; + } + bits = bits + half; + half = half ^ 1; + } +} + +/* Precondition: s->distance_code < 0. */ +static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal( + int safe, BrotliDecoderState* s, BrotliBitReader* br) { + BrotliMetablockBodyArena* b = &s->arena.body; + brotli_reg_t code; + brotli_reg_t bits; + BrotliBitReaderState memento; + HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; + if (!safe) { + code = ReadSymbol(distance_tree, br); + } else { + BrotliBitReaderSaveState(br, &memento); + if (!SafeReadSymbol(distance_tree, br, &code)) { + return BROTLI_FALSE; + } + } + --s->block_length[2]; + /* Convert the distance code to the actual distance by possibly + looking up past distances from the s->dist_rb. */ + s->distance_context = 0; + if ((code & ~0xFu) == 0) { + s->distance_code = (int)code; + TakeDistanceFromRingBuffer(s); + return BROTLI_TRUE; + } + if (!safe) { + bits = BrotliReadBits32(br, b->dist_extra_bits[code]); + } else { + if (!SafeReadBits32(br, b->dist_extra_bits[code], &bits)) { + ++s->block_length[2]; + BrotliBitReaderRestoreState(br, &memento); + return BROTLI_FALSE; + } + } + s->distance_code = + (int)(b->dist_offset[code] + (bits << s->distance_postfix_bits)); + return BROTLI_TRUE; +} + +static BROTLI_INLINE void ReadDistance( + BrotliDecoderState* s, BrotliBitReader* br) { + ReadDistanceInternal(0, s, br); +} + +static BROTLI_INLINE BROTLI_BOOL SafeReadDistance( + BrotliDecoderState* s, BrotliBitReader* br) { + return ReadDistanceInternal(1, s, br); +} + +static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal( + int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { + brotli_reg_t cmd_code; + brotli_reg_t insert_len_extra = 0; + brotli_reg_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 BROTLI_FALSE; + } + } + 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 (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) { + insert_len_extra = BrotliReadBits24(br, v.insert_len_extra_bits); + } + copy_length = BrotliReadBits24(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 BROTLI_FALSE; + } + } + s->copy_length = (int)copy_length + v.copy_len_offset; + --s->block_length[1]; + *insert_length += (int)insert_len_extra; + return BROTLI_TRUE; +} + +static BROTLI_INLINE void ReadCommand( + BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { + ReadCommandInternal(0, s, br, insert_length); +} + +static BROTLI_INLINE BROTLI_BOOL SafeReadCommand( + BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) { + return ReadCommandInternal(1, s, br, insert_length); +} + +static BROTLI_INLINE BROTLI_BOOL CheckInputAmount( + int safe, BrotliBitReader* const br) { + if (safe) { + return BROTLI_TRUE; + } + return BrotliCheckInputAmount(br); +} + +#define BROTLI_SAFE(METHOD) \ + { \ + if (safe) { \ + if (!Safe##METHOD) { \ + result = BROTLI_DECODER_NEEDS_MORE_INPUT; \ + goto saveStateAndReturn; \ + } \ + } else { \ + METHOD; \ + } \ + } + +static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal( + int safe, BrotliDecoderState* s) { + int pos = s->pos; + int i = s->loop_counter; + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; + BrotliBitReader* br = &s->br; + int compound_dictionary_size = GetCompoundDictionarySize(s); + + if (!CheckInputAmount(safe, br)) { + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + if (!safe) { + BROTLI_UNUSED(BrotliWarmupBitReader(br)); + } + + /* 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(BROTLI_DECODER_ERROR_UNREACHABLE); /* COV_NF_LINE */ + } + +CommandBegin: + if (safe) { + s->state = BROTLI_STATE_COMMAND_BEGIN; + } + if (!CheckInputAmount(safe, br)) { + s->state = BROTLI_STATE_COMMAND_BEGIN; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + if (BROTLI_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(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n", + pos, i, s->copy_length)); + 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) { + brotli_reg_t bits; + brotli_reg_t value; + PreloadSymbol(safe, s->literal_htree, br, &bits, &value); + do { + if (!CheckInputAmount(safe, br)) { + s->state = BROTLI_STATE_COMMAND_INNER; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { + goto NextLiteralBlock; + } + if (!safe) { + s->ringbuffer[pos] = + (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value); + } else { + brotli_reg_t literal; + if (!SafeReadSymbol(s->literal_htree, br, &literal)) { + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + s->ringbuffer[pos] = (uint8_t)literal; + } + --s->block_length[0]; + BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos); + ++pos; + if (BROTLI_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)) { + s->state = BROTLI_STATE_COMMAND_INNER; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { + goto NextLiteralBlock; + } + context = BROTLI_CONTEXT(p1, p2, s->context_lookup); + 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 { + brotli_reg_t literal; + if (!SafeReadSymbol(hc, br, &literal)) { + result = BROTLI_DECODER_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 (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) { + s->state = BROTLI_STATE_COMMAND_INNER_WRITE; + --i; + goto saveStateAndReturn; + } + } while (--i != 0); + } + BROTLI_LOG_UINT(s->meta_block_remaining_len); + if (BROTLI_PREDICT_FALSE(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) { + /* Implicit distance case. */ + s->distance_context = s->distance_code ? 0 : 1; + --s->dist_rb_idx; + s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; + } else { + /* Read distance code in the command, unless it was implicitly zero. */ + if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) { + BROTLI_SAFE(DecodeDistanceBlockSwitch(s)); + } + BROTLI_SAFE(ReadDistance(s, br)); + } + BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n", + pos, s->distance_code)); + if (s->max_distance != s->max_backward_distance) { + s->max_distance = + (pos < s->max_backward_distance) ? pos : s->max_backward_distance; + } + i = s->copy_length; + /* Apply copy of LZ77 back-reference, or static dictionary reference if + the distance is larger than the max LZ77 distance */ + if (s->distance_code > s->max_distance) { + /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC. + With this choice, no signed overflow can occur after decoding + a special distance code (e.g., after adding 3 to the last distance). */ + if (s->distance_code > BROTLI_MAX_ALLOWED_DISTANCE) { + BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d " + "len: %d bytes left: %d\n", + pos, s->distance_code, i, s->meta_block_remaining_len)); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE); + } + if (s->distance_code - s->max_distance - 1 < compound_dictionary_size) { + int address = compound_dictionary_size - + (s->distance_code - s->max_distance); + if (!InitializeCompoundDictionaryCopy(s, address, i)) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_COMPOUND_DICTIONARY); + } + pos += CopyFromCompoundDictionary(s, pos); + if (pos >= s->ringbuffer_size) { + s->state = BROTLI_STATE_COMMAND_POST_WRITE_1; + goto saveStateAndReturn; + } + } else if (i >= SHARED_BROTLI_MIN_DICTIONARY_WORD_LENGTH && + i <= SHARED_BROTLI_MAX_DICTIONARY_WORD_LENGTH) { + uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask]; + uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask]; + uint8_t dict_id = s->dictionary->context_based ? + s->dictionary->context_map[BROTLI_CONTEXT(p1, p2, s->context_lookup)] + : 0; + const BrotliDictionary* words = s->dictionary->words[dict_id]; + const BrotliTransforms* transforms = s->dictionary->transforms[dict_id]; + int offset = (int)words->offsets_by_length[i]; + brotli_reg_t shift = words->size_bits_by_length[i]; + int address = + s->distance_code - s->max_distance - 1 - compound_dictionary_size; + int mask = (int)BitMask(shift); + int word_idx = address & mask; + int transform_idx = address >> shift; + /* Compensate double distance-ring-buffer roll. */ + s->dist_rb_idx += s->distance_context; + offset += word_idx * i; + /* If the distance is out of bound, select a next static dictionary if + there exist multiple. */ + if ((transform_idx >= (int)transforms->num_transforms || + words->size_bits_by_length[i] == 0) && + s->dictionary->num_dictionaries > 1) { + uint8_t dict_id2; + int dist_remaining = address - + (int)(((1u << shift) & ~1u)) * (int)transforms->num_transforms; + for (dict_id2 = 0; dict_id2 < s->dictionary->num_dictionaries; + dict_id2++) { + const BrotliDictionary* words2 = s->dictionary->words[dict_id2]; + if (dict_id2 != dict_id && words2->size_bits_by_length[i] != 0) { + const BrotliTransforms* transforms2 = + s->dictionary->transforms[dict_id2]; + brotli_reg_t shift2 = words2->size_bits_by_length[i]; + int num = (int)((1u << shift2) & ~1u) * + (int)transforms2->num_transforms; + if (dist_remaining < num) { + dict_id = dict_id2; + words = words2; + transforms = transforms2; + address = dist_remaining; + shift = shift2; + mask = (int)BitMask(shift); + word_idx = address & mask; + transform_idx = address >> shift; + offset = (int)words->offsets_by_length[i] + word_idx * i; + break; + } + dist_remaining -= num; + } + } + } + if (BROTLI_PREDICT_FALSE(words->size_bits_by_length[i] == 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(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY); + } + if (BROTLI_PREDICT_FALSE(!words->data)) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET); + } + if (transform_idx < (int)transforms->num_transforms) { + const uint8_t* word = &words->data[offset]; + int len = i; + if (transform_idx == transforms->cutOffTransforms[0]) { + memcpy(&s->ringbuffer[pos], word, (size_t)len); + BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n", + len, word)); + } else { + len = BrotliTransformDictionaryWord(&s->ringbuffer[pos], word, len, + transforms, transform_idx); + BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]," + " transform_idx = %d, transformed: [%.*s]\n", + i, word, transform_idx, len, &s->ringbuffer[pos])); + if (len == 0 && s->distance_code <= 120) { + BROTLI_LOG(("Invalid length-0 dictionary word after transform\n")); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM); + } + } + pos += len; + s->meta_block_remaining_len -= len; + if (pos >= 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(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM); + } + } else { + BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d " + "len: %d bytes left: %d\n", + pos, s->distance_code, i, s->meta_block_remaining_len)); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY); + } + } else { + int src_start = (pos - s->distance_code) & s->ringbuffer_mask; + uint8_t* copy_dst = &s->ringbuffer[pos]; + uint8_t* copy_src = &s->ringbuffer[src_start]; + int dst_end = pos + i; + int src_end = src_start + i; + /* Update the recent distances cache. */ + s->dist_rb[s->dist_rb_idx & 3] = s->distance_code; + ++s->dist_rb_idx; + s->meta_block_remaining_len -= i; + /* There are 32+ bytes of slack in the ring-buffer allocation. + Also, we have 16 short codes, that make these 16 bytes irrelevant + in the ring-buffer. Let's copy over them as a first guess. */ + memmove16(copy_dst, copy_src); + if (src_end > pos && dst_end > src_start) { + /* Regions intersect. */ + goto CommandPostWrapCopy; + } + if (dst_end >= s->ringbuffer_size || src_end >= s->ringbuffer_size) { + /* At least one region wraps. */ + goto CommandPostWrapCopy; + } + 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); + } + } + } + BROTLI_LOG_UINT(s->meta_block_remaining_len); + if (s->meta_block_remaining_len <= 0) { + /* Next metablock, if any. */ + s->state = BROTLI_STATE_METABLOCK_DONE; + goto saveStateAndReturn; + } else { + goto CommandBegin; + } +CommandPostWrapCopy: + { + int wrap_guard = s->ringbuffer_size - pos; + while (--i >= 0) { + s->ringbuffer[pos] = + s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask]; + ++pos; + if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) { + s->state = BROTLI_STATE_COMMAND_POST_WRITE_2; + goto saveStateAndReturn; + } + } + } + if (s->meta_block_remaining_len <= 0) { + /* Next metablock, if any. */ + s->state = BROTLI_STATE_METABLOCK_DONE; + goto saveStateAndReturn; + } else { + goto CommandBegin; + } + +NextLiteralBlock: + BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); + goto CommandInner; + +saveStateAndReturn: + s->pos = pos; + s->loop_counter = i; + return result; +} + +#undef BROTLI_SAFE + +static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands( + BrotliDecoderState* s) { + return ProcessCommandsInternal(0, s); +} + +static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands( + BrotliDecoderState* s) { + return ProcessCommandsInternal(1, s); +} + +BrotliDecoderResult BrotliDecoderDecompress( + size_t encoded_size, + const uint8_t encoded_buffer[BROTLI_ARRAY_PARAM(encoded_size)], + size_t* decoded_size, + uint8_t decoded_buffer[BROTLI_ARRAY_PARAM(*decoded_size)]) { + BrotliDecoderState s; + BrotliDecoderResult result; + size_t total_out = 0; + size_t available_in = encoded_size; + const uint8_t* next_in = encoded_buffer; + size_t available_out = *decoded_size; + uint8_t* next_out = decoded_buffer; + if (!BrotliDecoderStateInit(&s, 0, 0, 0)) { + return BROTLI_DECODER_RESULT_ERROR; + } + result = BrotliDecoderDecompressStream( + &s, &available_in, &next_in, &available_out, &next_out, &total_out); + *decoded_size = total_out; + BrotliDecoderStateCleanup(&s); + if (result != BROTLI_DECODER_RESULT_SUCCESS) { + result = BROTLI_DECODER_RESULT_ERROR; + } + return result; +} + +/* Invariant: input stream is never overconsumed: + - invalid input implies that the whole stream is invalid -> any amount of + input could be read and discarded + - when result is "needs more input", then at least one more byte is REQUIRED + to complete decoding; all input data MUST be consumed by decoder, so + client could swap the input buffer + - when result is "needs more output" decoder MUST ensure that it doesn't + hold more than 7 bits in bit reader; this saves client from swapping input + buffer ahead of time + - when result is "success" decoder MUST return all unused data back to input + buffer; this is possible because the invariant is held on enter */ +BrotliDecoderResult BrotliDecoderDecompressStream( + BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in, + size_t* available_out, uint8_t** next_out, size_t* total_out) { + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; + BrotliBitReader* br = &s->br; + size_t input_size = *available_in; +#define BROTLI_SAVE_ERROR_CODE(code) \ + SaveErrorCode(s, (code), input_size - *available_in) + /* Ensure that |total_out| is set, even if no data will ever be pushed out. */ + if (total_out) { + *total_out = s->partial_pos_out; + } + /* Do not try to process further in a case of unrecoverable error. */ + if ((int)s->error_code < 0) { + return BROTLI_DECODER_RESULT_ERROR; + } + if (*available_out && (!next_out || !*next_out)) { + return BROTLI_SAVE_ERROR_CODE( + BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS)); + } + if (!*available_out) next_out = 0; + if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */ + BrotliBitReaderSetInput(br, *next_in, *available_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_DECODER_NEEDS_MORE_INPUT; + BrotliBitReaderSetInput(br, &s->buffer.u8[0], s->buffer_length); + } + /* State machine */ + for (;;) { + if (result != BROTLI_DECODER_SUCCESS) { + /* Error, needs more input/output. */ + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + if (s->ringbuffer != 0) { /* Pro-actively push output. */ + BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s, + available_out, next_out, total_out, BROTLI_TRUE); + /* WriteRingBuffer checks s->meta_block_remaining_len validity. */ + if ((int)intermediate_result < 0) { + result = intermediate_result; + break; + } + } + if (s->buffer_length != 0) { /* Used with internal buffer. */ + if (br->next_in == br->last_in) { + /* Successfully finished read transaction. + Accumulator contains less than 8 bits, because internal buffer + is expanded byte-by-byte until it is enough to complete read. */ + s->buffer_length = 0; + /* Switch to input stream and restart. */ + result = BROTLI_DECODER_SUCCESS; + BrotliBitReaderSetInput(br, *next_in, *available_in); + continue; + } else if (*available_in != 0) { + /* Not enough data in buffer, but can take one more byte from + input stream. */ + result = BROTLI_DECODER_SUCCESS; + BROTLI_DCHECK(s->buffer_length < 8); + s->buffer.u8[s->buffer_length] = **next_in; + s->buffer_length++; + BrotliBitReaderSetInput(br, &s->buffer.u8[0], 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 = BrotliBitReaderGetAvailIn(br); + 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 accumulator, so it is safe to + return unused accumulator bits there. */ + BrotliBitReaderUnload(br); + *available_in = BrotliBitReaderGetAvailIn(br); + *next_in = br->next_in; + } + break; + } + switch (s->state) { + case BROTLI_STATE_UNINITED: + /* Prepare to the first read. */ + if (!BrotliWarmupBitReader(br)) { + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + break; + } + /* Decode window size. */ + result = DecodeWindowBits(s, br); /* Reads 1..8 bits. */ + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + if (s->large_window) { + s->state = BROTLI_STATE_LARGE_WINDOW_BITS; + break; + } + s->state = BROTLI_STATE_INITIALIZE; + break; + + case BROTLI_STATE_LARGE_WINDOW_BITS: { + brotli_reg_t bits; + if (!BrotliSafeReadBits(br, 6, &bits)) { + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + break; + } + s->window_bits = bits & 63u; + if (s->window_bits < BROTLI_LARGE_MIN_WBITS || + s->window_bits > BROTLI_LARGE_MAX_WBITS) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + break; + } + s->state = BROTLI_STATE_INITIALIZE; + } + /* Fall through. */ + + case BROTLI_STATE_INITIALIZE: + BROTLI_LOG_UINT(s->window_bits); + /* Maximum distance, see section 9.1. of the spec. */ + s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP; + + /* Allocate memory for both block_type_trees and block_len_trees. */ + s->block_type_trees = (HuffmanCode*)BROTLI_DECODER_ALLOC(s, + sizeof(HuffmanCode) * 3 * + (BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26)); + if (s->block_type_trees == 0) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES); + break; + } + s->block_len_trees = + s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258; + + s->state = BROTLI_STATE_METABLOCK_BEGIN; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_BEGIN: + BrotliDecoderStateMetablockBegin(s); + BROTLI_LOG_UINT(s->pos); + s->state = BROTLI_STATE_METABLOCK_HEADER; + /* Fall through. */ + + case BROTLI_STATE_METABLOCK_HEADER: + result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */ + if (result != BROTLI_DECODER_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(BROTLI_DECODER_ERROR_FORMAT_PADDING_1); + break; + } + } + if (s->is_metadata) { + s->state = BROTLI_STATE_METADATA; + if (s->metadata_start_func) { + s->metadata_start_func(s->metadata_callback_opaque, + (size_t)s->meta_block_remaining_len); + } + break; + } + if (s->meta_block_remaining_len == 0) { + s->state = BROTLI_STATE_METABLOCK_DONE; + break; + } + BrotliCalculateRingBufferSize(s); + if (s->is_uncompressed) { + s->state = BROTLI_STATE_UNCOMPRESSED; + break; + } + s->state = BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER; + /* Fall through. */ + + case BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER: { + BrotliMetablockHeaderArena* h = &s->arena.header; + s->loop_counter = 0; + /* Initialize compressed metablock header arena. */ + h->sub_loop_counter = 0; + /* Make small negative indexes addressable. */ + h->symbol_lists = + &h->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1]; + h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; + h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; + s->state = BROTLI_STATE_HUFFMAN_CODE_0; + } + /* Fall through. */ + + 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_DECODER_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; + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_CODE_1: { + brotli_reg_t alphabet_size = s->num_block_types[s->loop_counter] + 2; + int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258; + result = ReadHuffmanCode(alphabet_size, alphabet_size, + &s->block_type_trees[tree_offset], NULL, s); + if (result != BROTLI_DECODER_SUCCESS) break; + s->state = BROTLI_STATE_HUFFMAN_CODE_2; + } + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_CODE_2: { + brotli_reg_t alphabet_size = BROTLI_NUM_BLOCK_LEN_SYMBOLS; + int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; + result = ReadHuffmanCode(alphabet_size, alphabet_size, + &s->block_len_trees[tree_offset], NULL, s); + if (result != BROTLI_DECODER_SUCCESS) break; + s->state = BROTLI_STATE_HUFFMAN_CODE_3; + } + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_CODE_3: { + int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; + if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter], + &s->block_len_trees[tree_offset], br)) { + result = BROTLI_DECODER_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_UNCOMPRESSED: { + result = CopyUncompressedBlockToOutput( + available_out, next_out, total_out, s); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + s->state = BROTLI_STATE_METABLOCK_DONE; + break; + } + + case BROTLI_STATE_METADATA: + result = SkipMetadataBlock(s); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + s->state = BROTLI_STATE_METABLOCK_DONE; + break; + + case BROTLI_STATE_METABLOCK_HEADER_2: { + brotli_reg_t bits; + if (!BrotliSafeReadBits(br, 6, &bits)) { + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + break; + } + s->distance_postfix_bits = bits & BitMask(2); + bits >>= 2; + s->num_direct_distance_codes = bits << s->distance_postfix_bits; + BROTLI_LOG_UINT(s->num_direct_distance_codes); + BROTLI_LOG_UINT(s->distance_postfix_bits); + s->context_modes = + (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)s->num_block_types[0]); + if (s->context_modes == 0) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES); + break; + } + s->loop_counter = 0; + s->state = BROTLI_STATE_CONTEXT_MODES; + } + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MODES: + result = ReadContextModes(s); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + s->state = BROTLI_STATE_CONTEXT_MAP_1; + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_1: + result = DecodeContextMap( + s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS, + &s->num_literal_htrees, &s->context_map, s); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + DetectTrivialLiteralBlockTypes(s); + s->state = BROTLI_STATE_CONTEXT_MAP_2; + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_2: { + brotli_reg_t npostfix = s->distance_postfix_bits; + brotli_reg_t ndirect = s->num_direct_distance_codes; + brotli_reg_t distance_alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE( + npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS); + brotli_reg_t distance_alphabet_size_limit = distance_alphabet_size_max; + BROTLI_BOOL allocation_success = BROTLI_TRUE; + if (s->large_window) { + BrotliDistanceCodeLimit limit = BrotliCalculateDistanceCodeLimit( + BROTLI_MAX_ALLOWED_DISTANCE, (uint32_t)npostfix, + (uint32_t)ndirect); + distance_alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE( + npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS); + distance_alphabet_size_limit = limit.max_alphabet_size; + } + result = DecodeContextMap( + s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS, + &s->num_dist_htrees, &s->dist_context_map, s); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( + s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS, + BROTLI_NUM_LITERAL_SYMBOLS, s->num_literal_htrees); + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( + s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS, + BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]); + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( + s, &s->distance_hgroup, distance_alphabet_size_max, + distance_alphabet_size_limit, s->num_dist_htrees); + if (!allocation_success) { + return BROTLI_SAVE_ERROR_CODE( + BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS)); + } + s->loop_counter = 0; + s->state = BROTLI_STATE_TREE_GROUP; + } + /* Fall through. */ + + case BROTLI_STATE_TREE_GROUP: { + HuffmanTreeGroup* hgroup = NULL; + switch (s->loop_counter) { + case 0: hgroup = &s->literal_hgroup; break; + case 1: hgroup = &s->insert_copy_hgroup; break; + case 2: hgroup = &s->distance_hgroup; break; + default: return BROTLI_SAVE_ERROR_CODE(BROTLI_FAILURE( + BROTLI_DECODER_ERROR_UNREACHABLE)); /* COV_NF_LINE */ + } + result = HuffmanTreeGroupDecode(hgroup, s); + if (result != BROTLI_DECODER_SUCCESS) break; + s->loop_counter++; + if (s->loop_counter < 3) { + break; + } + s->state = BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY; + } + /* Fall through. */ + + case BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY: + PrepareLiteralDecoding(s); + s->dist_context_map_slice = s->dist_context_map; + s->htree_command = s->insert_copy_hgroup.htrees[0]; + if (!BrotliEnsureRingBuffer(s)) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2); + break; + } + CalculateDistanceLut(s); + s->state = BROTLI_STATE_COMMAND_BEGIN; + /* Fall through. */ + + case BROTLI_STATE_COMMAND_BEGIN: + /* Fall through. */ + case BROTLI_STATE_COMMAND_INNER: + /* Fall through. */ + case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS: + /* Fall through. */ + case BROTLI_STATE_COMMAND_POST_WRAP_COPY: + result = ProcessCommands(s); + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + result = SafeProcessCommands(s); + } + break; + + case BROTLI_STATE_COMMAND_INNER_WRITE: + /* Fall through. */ + case BROTLI_STATE_COMMAND_POST_WRITE_1: + /* Fall through. */ + case BROTLI_STATE_COMMAND_POST_WRITE_2: + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_FALSE); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + WrapRingBuffer(s); + if (s->ringbuffer_size == 1 << s->window_bits) { + s->max_distance = s->max_backward_distance; + } + if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) { + BrotliDecoderCompoundDictionary* addon = s->compound_dictionary; + if (addon && (addon->br_length != addon->br_copied)) { + s->pos += CopyFromCompoundDictionary(s, s->pos); + if (s->pos >= s->ringbuffer_size) continue; + } + 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: + if (s->meta_block_remaining_len < 0) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2); + break; + } + BrotliDecoderStateCleanupAfterMetablock(s); + if (!s->is_last_metablock) { + s->state = BROTLI_STATE_METABLOCK_BEGIN; + break; + } + if (!BrotliJumpToByteBoundary(br)) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2); + break; + } + if (s->buffer_length == 0) { + BrotliBitReaderUnload(br); + *available_in = BrotliBitReaderGetAvailIn(br); + *next_in = br->next_in; + } + s->state = BROTLI_STATE_DONE; + /* Fall through. */ + + case BROTLI_STATE_DONE: + if (s->ringbuffer != 0) { + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_TRUE); + if (result != BROTLI_DECODER_SUCCESS) { + break; + } + } + return BROTLI_SAVE_ERROR_CODE(result); + } + } + return BROTLI_SAVE_ERROR_CODE(result); +#undef BROTLI_SAVE_ERROR_CODE +} + +BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) { + /* After unrecoverable error remaining output is considered nonsensical. */ + if ((int)s->error_code < 0) { + return BROTLI_FALSE; + } + return TO_BROTLI_BOOL( + s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0); +} + +const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) { + uint8_t* result = 0; + size_t available_out = *size ? *size : 1u << 24; + size_t requested_out = available_out; + BrotliDecoderErrorCode status; + if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) { + *size = 0; + return 0; + } + WrapRingBuffer(s); + status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE); + /* Either WriteRingBuffer returns those "success" codes... */ + if (status == BROTLI_DECODER_SUCCESS || + status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) { + *size = requested_out - available_out; + } else { + /* ... or stream is broken. Normally this should be caught by + BrotliDecoderDecompressStream, this is just a safeguard. */ + if ((int)status < 0) SaveErrorCode(s, status, 0); + *size = 0; + result = 0; + } + return result; +} + +BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) { + return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED || + BrotliGetAvailableBits(&s->br) != 0); +} + +BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) { + return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) && + !BrotliDecoderHasMoreOutput(s); +} + +BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) { + return (BrotliDecoderErrorCode)s->error_code; +} + +const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) { + switch (c) { +#define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \ + case BROTLI_DECODER ## PREFIX ## NAME: return #PREFIX #NAME; +#define BROTLI_NOTHING_ + BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_) +#undef BROTLI_ERROR_CODE_CASE_ +#undef BROTLI_NOTHING_ + default: return "INVALID"; + } +} + +uint32_t BrotliDecoderVersion(void) { + return BROTLI_VERSION; +} + +void BrotliDecoderSetMetadataCallbacks( + BrotliDecoderState* state, + brotli_decoder_metadata_start_func start_func, + brotli_decoder_metadata_chunk_func chunk_func, void* opaque) { + state->metadata_start_func = start_func; + state->metadata_chunk_func = chunk_func; + state->metadata_callback_opaque = opaque; +} + +/* Escalate internal functions visibility; for testing purposes only. */ +#if defined(BROTLI_TEST) +BROTLI_BOOL SafeReadSymbolForTest( + const HuffmanCode*, BrotliBitReader*, brotli_reg_t*); +BROTLI_BOOL SafeReadSymbolForTest( + const HuffmanCode* table, BrotliBitReader* br, brotli_reg_t* result) { + return SafeReadSymbol(table, br, result); +} + +void InverseMoveToFrontTransformForTest( + uint8_t*, brotli_reg_t, BrotliDecoderState*); +void InverseMoveToFrontTransformForTest( + uint8_t* v, brotli_reg_t l, BrotliDecoderState* s) { + InverseMoveToFrontTransform(v, l, s); +} +#endif + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif diff --git a/modules/brotli/dec/huffman.c b/modules/brotli/dec/huffman.c new file mode 100644 index 0000000000..3806454864 --- /dev/null +++ b/modules/brotli/dec/huffman.c @@ -0,0 +1,342 @@ +/* Copyright 2013 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* Utilities for building Huffman decoding tables. */ + +#include "huffman.h" + +#include /* memcpy, memset */ + +#include + +#include "../common/constants.h" +#include "../common/platform.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#define BROTLI_REVERSE_BITS_MAX 8 + +#if defined(BROTLI_RBIT) +#define BROTLI_REVERSE_BITS_BASE \ + ((sizeof(brotli_reg_t) << 3) - BROTLI_REVERSE_BITS_MAX) +#else +#define BROTLI_REVERSE_BITS_BASE 0 +static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = { + 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, + 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0, + 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, + 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8, + 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, + 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4, + 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, + 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC, + 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, + 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2, + 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, + 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA, + 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, + 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6, + 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, + 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE, + 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, + 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1, + 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, + 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9, + 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, + 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5, + 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, + 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD, + 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, + 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3, + 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, + 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB, + 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, + 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7, + 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, + 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF +}; +#endif /* BROTLI_RBIT */ + +#define BROTLI_REVERSE_BITS_LOWEST \ + ((brotli_reg_t)1 << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE)) + +/* Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX), + where reverse(value, len) is the bit-wise reversal of the len least + significant bits of value. */ +static BROTLI_INLINE brotli_reg_t BrotliReverseBits(brotli_reg_t num) { +#if defined(BROTLI_RBIT) + return BROTLI_RBIT(num); +#else + return kReverseBits[num]; +#endif +} + +/* Stores code in table[0], table[step], table[2*step], ..., table[end] */ +/* Assumes that end is an integer multiple of step */ +static BROTLI_INLINE void ReplicateValue(HuffmanCode* table, + int step, int end, + HuffmanCode code) { + do { + end -= step; + table[end] = code; + } while (end > 0); +} + +/* Returns the table width of the next 2nd level table. |count| is the histogram + of bit lengths for the remaining symbols, |len| is the code length of the + next processed symbol. */ +static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count, + int len, int root_bits) { + int left = 1 << (len - root_bits); + while (len < BROTLI_HUFFMAN_MAX_CODE_LENGTH) { + left -= count[len]; + if (left <= 0) break; + ++len; + left <<= 1; + } + return len - root_bits; +} + +void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, + const uint8_t* const code_lengths, + uint16_t* count) { + HuffmanCode code; /* current table entry */ + int symbol; /* symbol index in original or sorted table */ + brotli_reg_t key; /* prefix code */ + brotli_reg_t key_step; /* prefix code addend */ + int step; /* step size to replicate values in current table */ + int table_size; /* size of current table */ + int sorted[BROTLI_CODE_LENGTH_CODES]; /* symbols sorted by code length */ + /* offsets in sorted table for each length */ + int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1]; + int bits; + int bits_count; + BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <= + BROTLI_REVERSE_BITS_MAX); + BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH == 5); + + /* Generate offsets into sorted symbol table by code length. */ + symbol = -1; + bits = 1; + /* BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH == 5 */ + BROTLI_REPEAT_5({ + symbol += count[bits]; + offset[bits] = symbol; + bits++; + }); + /* Symbols with code length 0 are placed after all other symbols. */ + offset[0] = BROTLI_CODE_LENGTH_CODES - 1; + + /* Sort symbols by length, by symbol order within each length. */ + symbol = BROTLI_CODE_LENGTH_CODES; + do { + BROTLI_REPEAT_6({ + symbol--; + sorted[offset[code_lengths[symbol]]--] = symbol; + }); + } while (symbol != 0); + + table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH; + + /* Special case: all symbols but one have 0 code length. */ + if (offset[0] == 0) { + code = ConstructHuffmanCode(0, (uint16_t)sorted[0]); + for (key = 0; key < (brotli_reg_t)table_size; ++key) { + table[key] = code; + } + return; + } + + /* Fill in table. */ + key = 0; + key_step = BROTLI_REVERSE_BITS_LOWEST; + symbol = 0; + bits = 1; + step = 2; + do { + for (bits_count = count[bits]; bits_count != 0; --bits_count) { + code = ConstructHuffmanCode((uint8_t)bits, (uint16_t)sorted[symbol++]); + ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code); + key += key_step; + } + step <<= 1; + key_step >>= 1; + } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH); +} + +uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, + int root_bits, + const uint16_t* const symbol_lists, + uint16_t* count) { + HuffmanCode code; /* current table entry */ + HuffmanCode* table; /* next available space in table */ + int len; /* current code length */ + int symbol; /* symbol index in original or sorted table */ + brotli_reg_t key; /* prefix code */ + brotli_reg_t key_step; /* prefix code addend */ + brotli_reg_t sub_key; /* 2nd level table prefix code */ + brotli_reg_t sub_key_step; /* 2nd level table prefix code addend */ + int step; /* step size to replicate values in current table */ + int table_bits; /* key length of current table */ + int table_size; /* size of current table */ + int total_size; /* sum of root table size and 2nd level table sizes */ + int max_length = -1; + int bits; + int bits_count; + + BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX); + BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <= + BROTLI_REVERSE_BITS_MAX); + + while (symbol_lists[max_length] == 0xFFFF) max_length--; + max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1; + + table = root_table; + table_bits = root_bits; + table_size = 1 << table_bits; + total_size = table_size; + + /* Fill in the root table. Reduce the table size to if possible, + and create the repetitions by memcpy. */ + if (table_bits > max_length) { + table_bits = max_length; + table_size = 1 << table_bits; + } + key = 0; + key_step = BROTLI_REVERSE_BITS_LOWEST; + bits = 1; + step = 2; + do { + symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); + for (bits_count = count[bits]; bits_count != 0; --bits_count) { + symbol = symbol_lists[symbol]; + code = ConstructHuffmanCode((uint8_t)bits, (uint16_t)symbol); + ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code); + key += key_step; + } + step <<= 1; + key_step >>= 1; + } while (++bits <= table_bits); + + /* If root_bits != table_bits then replicate to fill the remaining slots. */ + while (total_size != table_size) { + memcpy(&table[table_size], &table[0], + (size_t)table_size * sizeof(table[0])); + table_size <<= 1; + } + + /* Fill in 2nd level tables and add pointers to root table. */ + key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1); + sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1); + sub_key_step = BROTLI_REVERSE_BITS_LOWEST; + for (len = root_bits + 1, step = 2; len <= max_length; ++len) { + symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); + for (; count[len] != 0; --count[len]) { + if (sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1U)) { + table += table_size; + table_bits = NextTableBitSize(count, len, root_bits); + table_size = 1 << table_bits; + total_size += table_size; + sub_key = BrotliReverseBits(key); + key += key_step; + root_table[sub_key] = ConstructHuffmanCode( + (uint8_t)(table_bits + root_bits), + (uint16_t)(((size_t)(table - root_table)) - sub_key)); + sub_key = 0; + } + symbol = symbol_lists[symbol]; + code = ConstructHuffmanCode((uint8_t)(len - root_bits), (uint16_t)symbol); + ReplicateValue( + &table[BrotliReverseBits(sub_key)], step, table_size, code); + sub_key += sub_key_step; + } + step <<= 1; + sub_key_step >>= 1; + } + return (uint32_t)total_size; +} + +uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, + int root_bits, + uint16_t* val, + uint32_t num_symbols) { + uint32_t table_size = 1; + const uint32_t goal_size = 1U << root_bits; + switch (num_symbols) { + case 0: + table[0] = ConstructHuffmanCode(0, val[0]); + break; + case 1: + if (val[1] > val[0]) { + table[0] = ConstructHuffmanCode(1, val[0]); + table[1] = ConstructHuffmanCode(1, val[1]); + } else { + table[0] = ConstructHuffmanCode(1, val[1]); + table[1] = ConstructHuffmanCode(1, val[0]); + } + table_size = 2; + break; + case 2: + table[0] = ConstructHuffmanCode(1, val[0]); + table[2] = ConstructHuffmanCode(1, val[0]); + if (val[2] > val[1]) { + table[1] = ConstructHuffmanCode(2, val[1]); + table[3] = ConstructHuffmanCode(2, val[2]); + } else { + table[1] = ConstructHuffmanCode(2, val[2]); + table[3] = ConstructHuffmanCode(2, val[1]); + } + table_size = 4; + break; + case 3: { + int i, k; + for (i = 0; i < 3; ++i) { + for (k = i + 1; k < 4; ++k) { + if (val[k] < val[i]) { + uint16_t t = val[k]; + val[k] = val[i]; + val[i] = t; + } + } + } + table[0] = ConstructHuffmanCode(2, val[0]); + table[2] = ConstructHuffmanCode(2, val[1]); + table[1] = ConstructHuffmanCode(2, val[2]); + table[3] = ConstructHuffmanCode(2, val[3]); + table_size = 4; + break; + } + case 4: { + if (val[3] < val[2]) { + uint16_t t = val[3]; + val[3] = val[2]; + val[2] = t; + } + table[0] = ConstructHuffmanCode(1, val[0]); + table[1] = ConstructHuffmanCode(2, val[1]); + table[2] = ConstructHuffmanCode(1, val[0]); + table[3] = ConstructHuffmanCode(3, val[2]); + table[4] = ConstructHuffmanCode(1, val[0]); + table[5] = ConstructHuffmanCode(2, val[1]); + table[6] = ConstructHuffmanCode(1, val[0]); + table[7] = ConstructHuffmanCode(3, val[3]); + table_size = 8; + break; + } + } + while (table_size != goal_size) { + memcpy(&table[table_size], &table[0], + (size_t)table_size * sizeof(table[0])); + table_size <<= 1; + } + return goal_size; +} + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif diff --git a/modules/brotli/dec/huffman.h b/modules/brotli/dec/huffman.h new file mode 100644 index 0000000000..50360962c7 --- /dev/null +++ b/modules/brotli/dec/huffman.h @@ -0,0 +1,122 @@ +/* Copyright 2013 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* Utilities for building Huffman decoding tables. */ + +#ifndef BROTLI_DEC_HUFFMAN_H_ +#define BROTLI_DEC_HUFFMAN_H_ + +#include + +#include "../common/platform.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +#define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15 + +/* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */ +#define BROTLI_HUFFMAN_MAX_SIZE_26 396 +/* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */ +#define BROTLI_HUFFMAN_MAX_SIZE_258 632 +/* BROTLI_MAX_CONTEXT_MAP_SYMBOLS == 272 */ +#define BROTLI_HUFFMAN_MAX_SIZE_272 646 + +#define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5 + +#if ((defined(BROTLI_TARGET_ARMV7) || defined(BROTLI_TARGET_ARMV8_32)) && \ + BROTLI_GNUC_HAS_ATTRIBUTE(aligned, 2, 7, 0)) +#define BROTLI_HUFFMAN_CODE_FAST_LOAD +#endif + +#if !defined(BROTLI_HUFFMAN_CODE_FAST_LOAD) +/* Do not create this struct directly - use the ConstructHuffmanCode + * constructor below! */ +typedef struct { + uint8_t bits; /* number of bits used for this symbol */ + uint16_t value; /* symbol value or table offset */ +} HuffmanCode; + +static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits, + const uint16_t value) { + HuffmanCode h; + h.bits = bits; + h.value = value; + return h; +} + +/* Please use the following macros to optimize HuffmanCode accesses in hot + * paths. + * + * For example, assuming |table| contains a HuffmanCode pointer: + * + * BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + * BROTLI_HC_ADJUST_TABLE_INDEX(table, index_into_table); + * *bits = BROTLI_HC_GET_BITS(table); + * *value = BROTLI_HC_GET_VALUE(table); + * BROTLI_HC_ADJUST_TABLE_INDEX(table, offset); + * *bits2 = BROTLI_HC_GET_BITS(table); + * *value2 = BROTLI_HC_GET_VALUE(table); + * + */ + +#define BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(H) +#define BROTLI_HC_ADJUST_TABLE_INDEX(H, V) H += (V) + +/* These must be given a HuffmanCode pointer! */ +#define BROTLI_HC_FAST_LOAD_BITS(H) (H->bits) +#define BROTLI_HC_FAST_LOAD_VALUE(H) (H->value) + +#else /* BROTLI_HUFFMAN_CODE_FAST_LOAD */ + +typedef BROTLI_ALIGNED(4) uint32_t HuffmanCode; + +static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits, + const uint16_t value) { + return (HuffmanCode) ((value & 0xFFFF) << 16) | (bits & 0xFF); +} + +#define BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(H) uint32_t __fastload_##H = (*H) +#define BROTLI_HC_ADJUST_TABLE_INDEX(H, V) H += (V); __fastload_##H = (*H) + +/* These must be given a HuffmanCode pointer! */ +#define BROTLI_HC_FAST_LOAD_BITS(H) ((__fastload_##H) & 0xFF) +#define BROTLI_HC_FAST_LOAD_VALUE(H) ((__fastload_##H) >> 16) +#endif /* BROTLI_HUFFMAN_CODE_FAST_LOAD */ + +/* Builds Huffman lookup table assuming code lengths are in symbol order. */ +BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table, + const uint8_t* const code_lengths, uint16_t* count); + +/* Builds Huffman lookup table assuming code lengths are in symbol order. + Returns size of resulting table. */ +BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, + int root_bits, const uint16_t* const symbol_lists, uint16_t* count); + +/* Builds a simple Huffman table. The |num_symbols| parameter is to be + interpreted as follows: 0 means 1 symbol, 1 means 2 symbols, + 2 means 3 symbols, 3 means 4 symbols with lengths [2, 2, 2, 2], + 4 means 4 symbols with lengths [1, 2, 3, 3]. */ +BROTLI_INTERNAL uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, + int root_bits, uint16_t* symbols, uint32_t num_symbols); + +/* Contains a collection of Huffman trees with the same alphabet size. */ +/* alphabet_size_limit is needed due to simple codes, since + log2(alphabet_size_max) could be greater than log2(alphabet_size_limit). */ +typedef struct { + HuffmanCode** htrees; + HuffmanCode* codes; + uint16_t alphabet_size_max; + uint16_t alphabet_size_limit; + uint16_t num_htrees; +} HuffmanTreeGroup; + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif + +#endif /* BROTLI_DEC_HUFFMAN_H_ */ diff --git a/modules/brotli/dec/prefix.h b/modules/brotli/dec/prefix.h new file mode 100644 index 0000000000..e8acf07740 --- /dev/null +++ b/modules/brotli/dec/prefix.h @@ -0,0 +1,733 @@ +/* Copyright 2013 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* Lookup tables to map prefix codes to value ranges. This is used during + decoding of the block lengths, literal insertion lengths and copy lengths. */ + +#ifndef BROTLI_DEC_PREFIX_H_ +#define BROTLI_DEC_PREFIX_H_ + +#include + +#include "../common/constants.h" + +typedef struct CmdLutElement { + uint8_t insert_len_extra_bits; + uint8_t copy_len_extra_bits; + int8_t distance_code; + uint8_t context; + uint16_t insert_len_offset; + uint16_t copy_len_offset; +} CmdLutElement; + +static const CmdLutElement kCmdLut[BROTLI_NUM_COMMAND_SYMBOLS] = { + { 0x00, 0x00, 0, 0x00, 0x0000, 0x0002 }, + { 0x00, 0x00, 0, 0x01, 0x0000, 0x0003 }, + { 0x00, 0x00, 0, 0x02, 0x0000, 0x0004 }, + { 0x00, 0x00, 0, 0x03, 0x0000, 0x0005 }, + { 0x00, 0x00, 0, 0x03, 0x0000, 0x0006 }, + { 0x00, 0x00, 0, 0x03, 0x0000, 0x0007 }, + { 0x00, 0x00, 0, 0x03, 0x0000, 0x0008 }, + { 0x00, 0x00, 0, 0x03, 0x0000, 0x0009 }, + { 0x00, 0x00, 0, 0x00, 0x0001, 0x0002 }, + { 0x00, 0x00, 0, 0x01, 0x0001, 0x0003 }, + { 0x00, 0x00, 0, 0x02, 0x0001, 0x0004 }, + { 0x00, 0x00, 0, 0x03, 0x0001, 0x0005 }, + { 0x00, 0x00, 0, 0x03, 0x0001, 0x0006 }, + { 0x00, 0x00, 0, 0x03, 0x0001, 0x0007 }, + { 0x00, 0x00, 0, 0x03, 0x0001, 0x0008 }, + { 0x00, 0x00, 0, 0x03, 0x0001, 0x0009 }, + { 0x00, 0x00, 0, 0x00, 0x0002, 0x0002 }, + { 0x00, 0x00, 0, 0x01, 0x0002, 0x0003 }, + { 0x00, 0x00, 0, 0x02, 0x0002, 0x0004 }, + { 0x00, 0x00, 0, 0x03, 0x0002, 0x0005 }, + { 0x00, 0x00, 0, 0x03, 0x0002, 0x0006 }, + { 0x00, 0x00, 0, 0x03, 0x0002, 0x0007 }, + { 0x00, 0x00, 0, 0x03, 0x0002, 0x0008 }, + { 0x00, 0x00, 0, 0x03, 0x0002, 0x0009 }, + { 0x00, 0x00, 0, 0x00, 0x0003, 0x0002 }, + { 0x00, 0x00, 0, 0x01, 0x0003, 0x0003 }, + { 0x00, 0x00, 0, 0x02, 0x0003, 0x0004 }, + { 0x00, 0x00, 0, 0x03, 0x0003, 0x0005 }, + { 0x00, 0x00, 0, 0x03, 0x0003, 0x0006 }, + { 0x00, 0x00, 0, 0x03, 0x0003, 0x0007 }, + { 0x00, 0x00, 0, 0x03, 0x0003, 0x0008 }, + { 0x00, 0x00, 0, 0x03, 0x0003, 0x0009 }, + { 0x00, 0x00, 0, 0x00, 0x0004, 0x0002 }, + { 0x00, 0x00, 0, 0x01, 0x0004, 0x0003 }, + { 0x00, 0x00, 0, 0x02, 0x0004, 0x0004 }, + { 0x00, 0x00, 0, 0x03, 0x0004, 0x0005 }, + { 0x00, 0x00, 0, 0x03, 0x0004, 0x0006 }, + { 0x00, 0x00, 0, 0x03, 0x0004, 0x0007 }, + { 0x00, 0x00, 0, 0x03, 0x0004, 0x0008 }, + { 0x00, 0x00, 0, 0x03, 0x0004, 0x0009 }, + { 0x00, 0x00, 0, 0x00, 0x0005, 0x0002 }, + { 0x00, 0x00, 0, 0x01, 0x0005, 0x0003 }, + { 0x00, 0x00, 0, 0x02, 0x0005, 0x0004 }, + { 0x00, 0x00, 0, 0x03, 0x0005, 0x0005 }, + { 0x00, 0x00, 0, 0x03, 0x0005, 0x0006 }, + { 0x00, 0x00, 0, 0x03, 0x0005, 0x0007 }, + { 0x00, 0x00, 0, 0x03, 0x0005, 0x0008 }, + { 0x00, 0x00, 0, 0x03, 0x0005, 0x0009 }, + { 0x01, 0x00, 0, 0x00, 0x0006, 0x0002 }, + { 0x01, 0x00, 0, 0x01, 0x0006, 0x0003 }, + { 0x01, 0x00, 0, 0x02, 0x0006, 0x0004 }, + { 0x01, 0x00, 0, 0x03, 0x0006, 0x0005 }, + { 0x01, 0x00, 0, 0x03, 0x0006, 0x0006 }, + { 0x01, 0x00, 0, 0x03, 0x0006, 0x0007 }, + { 0x01, 0x00, 0, 0x03, 0x0006, 0x0008 }, + { 0x01, 0x00, 0, 0x03, 0x0006, 0x0009 }, + { 0x01, 0x00, 0, 0x00, 0x0008, 0x0002 }, + { 0x01, 0x00, 0, 0x01, 0x0008, 0x0003 }, + { 0x01, 0x00, 0, 0x02, 0x0008, 0x0004 }, + { 0x01, 0x00, 0, 0x03, 0x0008, 0x0005 }, + { 0x01, 0x00, 0, 0x03, 0x0008, 0x0006 }, + { 0x01, 0x00, 0, 0x03, 0x0008, 0x0007 }, + { 0x01, 0x00, 0, 0x03, 0x0008, 0x0008 }, + { 0x01, 0x00, 0, 0x03, 0x0008, 0x0009 }, + { 0x00, 0x01, 0, 0x03, 0x0000, 0x000a }, + { 0x00, 0x01, 0, 0x03, 0x0000, 0x000c }, + { 0x00, 0x02, 0, 0x03, 0x0000, 0x000e }, + { 0x00, 0x02, 0, 0x03, 0x0000, 0x0012 }, + { 0x00, 0x03, 0, 0x03, 0x0000, 0x0016 }, + { 0x00, 0x03, 0, 0x03, 0x0000, 0x001e }, + { 0x00, 0x04, 0, 0x03, 0x0000, 0x0026 }, + { 0x00, 0x04, 0, 0x03, 0x0000, 0x0036 }, + { 0x00, 0x01, 0, 0x03, 0x0001, 0x000a }, + { 0x00, 0x01, 0, 0x03, 0x0001, 0x000c }, + { 0x00, 0x02, 0, 0x03, 0x0001, 0x000e }, + { 0x00, 0x02, 0, 0x03, 0x0001, 0x0012 }, + { 0x00, 0x03, 0, 0x03, 0x0001, 0x0016 }, + { 0x00, 0x03, 0, 0x03, 0x0001, 0x001e }, + { 0x00, 0x04, 0, 0x03, 0x0001, 0x0026 }, + { 0x00, 0x04, 0, 0x03, 0x0001, 0x0036 }, + { 0x00, 0x01, 0, 0x03, 0x0002, 0x000a }, + { 0x00, 0x01, 0, 0x03, 0x0002, 0x000c }, + { 0x00, 0x02, 0, 0x03, 0x0002, 0x000e }, + { 0x00, 0x02, 0, 0x03, 0x0002, 0x0012 }, + { 0x00, 0x03, 0, 0x03, 0x0002, 0x0016 }, + { 0x00, 0x03, 0, 0x03, 0x0002, 0x001e }, + { 0x00, 0x04, 0, 0x03, 0x0002, 0x0026 }, + { 0x00, 0x04, 0, 0x03, 0x0002, 0x0036 }, + { 0x00, 0x01, 0, 0x03, 0x0003, 0x000a }, + { 0x00, 0x01, 0, 0x03, 0x0003, 0x000c }, + { 0x00, 0x02, 0, 0x03, 0x0003, 0x000e }, + { 0x00, 0x02, 0, 0x03, 0x0003, 0x0012 }, + { 0x00, 0x03, 0, 0x03, 0x0003, 0x0016 }, + { 0x00, 0x03, 0, 0x03, 0x0003, 0x001e }, + { 0x00, 0x04, 0, 0x03, 0x0003, 0x0026 }, + { 0x00, 0x04, 0, 0x03, 0x0003, 0x0036 }, + { 0x00, 0x01, 0, 0x03, 0x0004, 0x000a }, + { 0x00, 0x01, 0, 0x03, 0x0004, 0x000c }, + { 0x00, 0x02, 0, 0x03, 0x0004, 0x000e }, + { 0x00, 0x02, 0, 0x03, 0x0004, 0x0012 }, + { 0x00, 0x03, 0, 0x03, 0x0004, 0x0016 }, + { 0x00, 0x03, 0, 0x03, 0x0004, 0x001e }, + { 0x00, 0x04, 0, 0x03, 0x0004, 0x0026 }, + { 0x00, 0x04, 0, 0x03, 0x0004, 0x0036 }, + { 0x00, 0x01, 0, 0x03, 0x0005, 0x000a }, + { 0x00, 0x01, 0, 0x03, 0x0005, 0x000c }, + { 0x00, 0x02, 0, 0x03, 0x0005, 0x000e }, + { 0x00, 0x02, 0, 0x03, 0x0005, 0x0012 }, + { 0x00, 0x03, 0, 0x03, 0x0005, 0x0016 }, + { 0x00, 0x03, 0, 0x03, 0x0005, 0x001e }, + { 0x00, 0x04, 0, 0x03, 0x0005, 0x0026 }, + { 0x00, 0x04, 0, 0x03, 0x0005, 0x0036 }, + { 0x01, 0x01, 0, 0x03, 0x0006, 0x000a }, + { 0x01, 0x01, 0, 0x03, 0x0006, 0x000c }, + { 0x01, 0x02, 0, 0x03, 0x0006, 0x000e }, + { 0x01, 0x02, 0, 0x03, 0x0006, 0x0012 }, + { 0x01, 0x03, 0, 0x03, 0x0006, 0x0016 }, + { 0x01, 0x03, 0, 0x03, 0x0006, 0x001e }, + { 0x01, 0x04, 0, 0x03, 0x0006, 0x0026 }, + { 0x01, 0x04, 0, 0x03, 0x0006, 0x0036 }, + { 0x01, 0x01, 0, 0x03, 0x0008, 0x000a }, + { 0x01, 0x01, 0, 0x03, 0x0008, 0x000c }, + { 0x01, 0x02, 0, 0x03, 0x0008, 0x000e }, + { 0x01, 0x02, 0, 0x03, 0x0008, 0x0012 }, + { 0x01, 0x03, 0, 0x03, 0x0008, 0x0016 }, + { 0x01, 0x03, 0, 0x03, 0x0008, 0x001e }, + { 0x01, 0x04, 0, 0x03, 0x0008, 0x0026 }, + { 0x01, 0x04, 0, 0x03, 0x0008, 0x0036 }, + { 0x00, 0x00, -1, 0x00, 0x0000, 0x0002 }, + { 0x00, 0x00, -1, 0x01, 0x0000, 0x0003 }, + { 0x00, 0x00, -1, 0x02, 0x0000, 0x0004 }, + { 0x00, 0x00, -1, 0x03, 0x0000, 0x0005 }, + { 0x00, 0x00, -1, 0x03, 0x0000, 0x0006 }, + { 0x00, 0x00, -1, 0x03, 0x0000, 0x0007 }, + { 0x00, 0x00, -1, 0x03, 0x0000, 0x0008 }, + { 0x00, 0x00, -1, 0x03, 0x0000, 0x0009 }, + { 0x00, 0x00, -1, 0x00, 0x0001, 0x0002 }, + { 0x00, 0x00, -1, 0x01, 0x0001, 0x0003 }, + { 0x00, 0x00, -1, 0x02, 0x0001, 0x0004 }, + { 0x00, 0x00, -1, 0x03, 0x0001, 0x0005 }, + { 0x00, 0x00, -1, 0x03, 0x0001, 0x0006 }, + { 0x00, 0x00, -1, 0x03, 0x0001, 0x0007 }, + { 0x00, 0x00, -1, 0x03, 0x0001, 0x0008 }, + { 0x00, 0x00, -1, 0x03, 0x0001, 0x0009 }, + { 0x00, 0x00, -1, 0x00, 0x0002, 0x0002 }, + { 0x00, 0x00, -1, 0x01, 0x0002, 0x0003 }, + { 0x00, 0x00, -1, 0x02, 0x0002, 0x0004 }, + { 0x00, 0x00, -1, 0x03, 0x0002, 0x0005 }, + { 0x00, 0x00, -1, 0x03, 0x0002, 0x0006 }, + { 0x00, 0x00, -1, 0x03, 0x0002, 0x0007 }, + { 0x00, 0x00, -1, 0x03, 0x0002, 0x0008 }, + { 0x00, 0x00, -1, 0x03, 0x0002, 0x0009 }, + { 0x00, 0x00, -1, 0x00, 0x0003, 0x0002 }, + { 0x00, 0x00, -1, 0x01, 0x0003, 0x0003 }, + { 0x00, 0x00, -1, 0x02, 0x0003, 0x0004 }, + { 0x00, 0x00, -1, 0x03, 0x0003, 0x0005 }, + { 0x00, 0x00, -1, 0x03, 0x0003, 0x0006 }, + { 0x00, 0x00, -1, 0x03, 0x0003, 0x0007 }, + { 0x00, 0x00, -1, 0x03, 0x0003, 0x0008 }, + { 0x00, 0x00, -1, 0x03, 0x0003, 0x0009 }, + { 0x00, 0x00, -1, 0x00, 0x0004, 0x0002 }, + { 0x00, 0x00, -1, 0x01, 0x0004, 0x0003 }, + { 0x00, 0x00, -1, 0x02, 0x0004, 0x0004 }, + { 0x00, 0x00, -1, 0x03, 0x0004, 0x0005 }, + { 0x00, 0x00, -1, 0x03, 0x0004, 0x0006 }, + { 0x00, 0x00, -1, 0x03, 0x0004, 0x0007 }, + { 0x00, 0x00, -1, 0x03, 0x0004, 0x0008 }, + { 0x00, 0x00, -1, 0x03, 0x0004, 0x0009 }, + { 0x00, 0x00, -1, 0x00, 0x0005, 0x0002 }, + { 0x00, 0x00, -1, 0x01, 0x0005, 0x0003 }, + { 0x00, 0x00, -1, 0x02, 0x0005, 0x0004 }, + { 0x00, 0x00, -1, 0x03, 0x0005, 0x0005 }, + { 0x00, 0x00, -1, 0x03, 0x0005, 0x0006 }, + { 0x00, 0x00, -1, 0x03, 0x0005, 0x0007 }, + { 0x00, 0x00, -1, 0x03, 0x0005, 0x0008 }, + { 0x00, 0x00, -1, 0x03, 0x0005, 0x0009 }, + { 0x01, 0x00, -1, 0x00, 0x0006, 0x0002 }, + { 0x01, 0x00, -1, 0x01, 0x0006, 0x0003 }, + { 0x01, 0x00, -1, 0x02, 0x0006, 0x0004 }, + { 0x01, 0x00, -1, 0x03, 0x0006, 0x0005 }, + { 0x01, 0x00, -1, 0x03, 0x0006, 0x0006 }, + { 0x01, 0x00, -1, 0x03, 0x0006, 0x0007 }, + { 0x01, 0x00, -1, 0x03, 0x0006, 0x0008 }, + { 0x01, 0x00, -1, 0x03, 0x0006, 0x0009 }, + { 0x01, 0x00, -1, 0x00, 0x0008, 0x0002 }, + { 0x01, 0x00, -1, 0x01, 0x0008, 0x0003 }, + { 0x01, 0x00, -1, 0x02, 0x0008, 0x0004 }, + { 0x01, 0x00, -1, 0x03, 0x0008, 0x0005 }, + { 0x01, 0x00, -1, 0x03, 0x0008, 0x0006 }, + { 0x01, 0x00, -1, 0x03, 0x0008, 0x0007 }, + { 0x01, 0x00, -1, 0x03, 0x0008, 0x0008 }, + { 0x01, 0x00, -1, 0x03, 0x0008, 0x0009 }, + { 0x00, 0x01, -1, 0x03, 0x0000, 0x000a }, + { 0x00, 0x01, -1, 0x03, 0x0000, 0x000c }, + { 0x00, 0x02, -1, 0x03, 0x0000, 0x000e }, + { 0x00, 0x02, -1, 0x03, 0x0000, 0x0012 }, + { 0x00, 0x03, -1, 0x03, 0x0000, 0x0016 }, + { 0x00, 0x03, -1, 0x03, 0x0000, 0x001e }, + { 0x00, 0x04, -1, 0x03, 0x0000, 0x0026 }, + { 0x00, 0x04, -1, 0x03, 0x0000, 0x0036 }, + { 0x00, 0x01, -1, 0x03, 0x0001, 0x000a }, + { 0x00, 0x01, -1, 0x03, 0x0001, 0x000c }, + { 0x00, 0x02, -1, 0x03, 0x0001, 0x000e }, + { 0x00, 0x02, -1, 0x03, 0x0001, 0x0012 }, + { 0x00, 0x03, -1, 0x03, 0x0001, 0x0016 }, + { 0x00, 0x03, -1, 0x03, 0x0001, 0x001e }, + { 0x00, 0x04, -1, 0x03, 0x0001, 0x0026 }, + { 0x00, 0x04, -1, 0x03, 0x0001, 0x0036 }, + { 0x00, 0x01, -1, 0x03, 0x0002, 0x000a }, + { 0x00, 0x01, -1, 0x03, 0x0002, 0x000c }, + { 0x00, 0x02, -1, 0x03, 0x0002, 0x000e }, + { 0x00, 0x02, -1, 0x03, 0x0002, 0x0012 }, + { 0x00, 0x03, -1, 0x03, 0x0002, 0x0016 }, + { 0x00, 0x03, -1, 0x03, 0x0002, 0x001e }, + { 0x00, 0x04, -1, 0x03, 0x0002, 0x0026 }, + { 0x00, 0x04, -1, 0x03, 0x0002, 0x0036 }, + { 0x00, 0x01, -1, 0x03, 0x0003, 0x000a }, + { 0x00, 0x01, -1, 0x03, 0x0003, 0x000c }, + { 0x00, 0x02, -1, 0x03, 0x0003, 0x000e }, + { 0x00, 0x02, -1, 0x03, 0x0003, 0x0012 }, + { 0x00, 0x03, -1, 0x03, 0x0003, 0x0016 }, + { 0x00, 0x03, -1, 0x03, 0x0003, 0x001e }, + { 0x00, 0x04, -1, 0x03, 0x0003, 0x0026 }, + { 0x00, 0x04, -1, 0x03, 0x0003, 0x0036 }, + { 0x00, 0x01, -1, 0x03, 0x0004, 0x000a }, + { 0x00, 0x01, -1, 0x03, 0x0004, 0x000c }, + { 0x00, 0x02, -1, 0x03, 0x0004, 0x000e }, + { 0x00, 0x02, -1, 0x03, 0x0004, 0x0012 }, + { 0x00, 0x03, -1, 0x03, 0x0004, 0x0016 }, + { 0x00, 0x03, -1, 0x03, 0x0004, 0x001e }, + { 0x00, 0x04, -1, 0x03, 0x0004, 0x0026 }, + { 0x00, 0x04, -1, 0x03, 0x0004, 0x0036 }, + { 0x00, 0x01, -1, 0x03, 0x0005, 0x000a }, + { 0x00, 0x01, -1, 0x03, 0x0005, 0x000c }, + { 0x00, 0x02, -1, 0x03, 0x0005, 0x000e }, + { 0x00, 0x02, -1, 0x03, 0x0005, 0x0012 }, + { 0x00, 0x03, -1, 0x03, 0x0005, 0x0016 }, + { 0x00, 0x03, -1, 0x03, 0x0005, 0x001e }, + { 0x00, 0x04, -1, 0x03, 0x0005, 0x0026 }, + { 0x00, 0x04, -1, 0x03, 0x0005, 0x0036 }, + { 0x01, 0x01, -1, 0x03, 0x0006, 0x000a }, + { 0x01, 0x01, -1, 0x03, 0x0006, 0x000c }, + { 0x01, 0x02, -1, 0x03, 0x0006, 0x000e }, + { 0x01, 0x02, -1, 0x03, 0x0006, 0x0012 }, + { 0x01, 0x03, -1, 0x03, 0x0006, 0x0016 }, + { 0x01, 0x03, -1, 0x03, 0x0006, 0x001e }, + { 0x01, 0x04, -1, 0x03, 0x0006, 0x0026 }, + { 0x01, 0x04, -1, 0x03, 0x0006, 0x0036 }, + { 0x01, 0x01, -1, 0x03, 0x0008, 0x000a }, + { 0x01, 0x01, -1, 0x03, 0x0008, 0x000c }, + { 0x01, 0x02, -1, 0x03, 0x0008, 0x000e }, + { 0x01, 0x02, -1, 0x03, 0x0008, 0x0012 }, + { 0x01, 0x03, -1, 0x03, 0x0008, 0x0016 }, + { 0x01, 0x03, -1, 0x03, 0x0008, 0x001e }, + { 0x01, 0x04, -1, 0x03, 0x0008, 0x0026 }, + { 0x01, 0x04, -1, 0x03, 0x0008, 0x0036 }, + { 0x02, 0x00, -1, 0x00, 0x000a, 0x0002 }, + { 0x02, 0x00, -1, 0x01, 0x000a, 0x0003 }, + { 0x02, 0x00, -1, 0x02, 0x000a, 0x0004 }, + { 0x02, 0x00, -1, 0x03, 0x000a, 0x0005 }, + { 0x02, 0x00, -1, 0x03, 0x000a, 0x0006 }, + { 0x02, 0x00, -1, 0x03, 0x000a, 0x0007 }, + { 0x02, 0x00, -1, 0x03, 0x000a, 0x0008 }, + { 0x02, 0x00, -1, 0x03, 0x000a, 0x0009 }, + { 0x02, 0x00, -1, 0x00, 0x000e, 0x0002 }, + { 0x02, 0x00, -1, 0x01, 0x000e, 0x0003 }, + { 0x02, 0x00, -1, 0x02, 0x000e, 0x0004 }, + { 0x02, 0x00, -1, 0x03, 0x000e, 0x0005 }, + { 0x02, 0x00, -1, 0x03, 0x000e, 0x0006 }, + { 0x02, 0x00, -1, 0x03, 0x000e, 0x0007 }, + { 0x02, 0x00, -1, 0x03, 0x000e, 0x0008 }, + { 0x02, 0x00, -1, 0x03, 0x000e, 0x0009 }, + { 0x03, 0x00, -1, 0x00, 0x0012, 0x0002 }, + { 0x03, 0x00, -1, 0x01, 0x0012, 0x0003 }, + { 0x03, 0x00, -1, 0x02, 0x0012, 0x0004 }, + { 0x03, 0x00, -1, 0x03, 0x0012, 0x0005 }, + { 0x03, 0x00, -1, 0x03, 0x0012, 0x0006 }, + { 0x03, 0x00, -1, 0x03, 0x0012, 0x0007 }, + { 0x03, 0x00, -1, 0x03, 0x0012, 0x0008 }, + { 0x03, 0x00, -1, 0x03, 0x0012, 0x0009 }, + { 0x03, 0x00, -1, 0x00, 0x001a, 0x0002 }, + { 0x03, 0x00, -1, 0x01, 0x001a, 0x0003 }, + { 0x03, 0x00, -1, 0x02, 0x001a, 0x0004 }, + { 0x03, 0x00, -1, 0x03, 0x001a, 0x0005 }, + { 0x03, 0x00, -1, 0x03, 0x001a, 0x0006 }, + { 0x03, 0x00, -1, 0x03, 0x001a, 0x0007 }, + { 0x03, 0x00, -1, 0x03, 0x001a, 0x0008 }, + { 0x03, 0x00, -1, 0x03, 0x001a, 0x0009 }, + { 0x04, 0x00, -1, 0x00, 0x0022, 0x0002 }, + { 0x04, 0x00, -1, 0x01, 0x0022, 0x0003 }, + { 0x04, 0x00, -1, 0x02, 0x0022, 0x0004 }, + { 0x04, 0x00, -1, 0x03, 0x0022, 0x0005 }, + { 0x04, 0x00, -1, 0x03, 0x0022, 0x0006 }, + { 0x04, 0x00, -1, 0x03, 0x0022, 0x0007 }, + { 0x04, 0x00, -1, 0x03, 0x0022, 0x0008 }, + { 0x04, 0x00, -1, 0x03, 0x0022, 0x0009 }, + { 0x04, 0x00, -1, 0x00, 0x0032, 0x0002 }, + { 0x04, 0x00, -1, 0x01, 0x0032, 0x0003 }, + { 0x04, 0x00, -1, 0x02, 0x0032, 0x0004 }, + { 0x04, 0x00, -1, 0x03, 0x0032, 0x0005 }, + { 0x04, 0x00, -1, 0x03, 0x0032, 0x0006 }, + { 0x04, 0x00, -1, 0x03, 0x0032, 0x0007 }, + { 0x04, 0x00, -1, 0x03, 0x0032, 0x0008 }, + { 0x04, 0x00, -1, 0x03, 0x0032, 0x0009 }, + { 0x05, 0x00, -1, 0x00, 0x0042, 0x0002 }, + { 0x05, 0x00, -1, 0x01, 0x0042, 0x0003 }, + { 0x05, 0x00, -1, 0x02, 0x0042, 0x0004 }, + { 0x05, 0x00, -1, 0x03, 0x0042, 0x0005 }, + { 0x05, 0x00, -1, 0x03, 0x0042, 0x0006 }, + { 0x05, 0x00, -1, 0x03, 0x0042, 0x0007 }, + { 0x05, 0x00, -1, 0x03, 0x0042, 0x0008 }, + { 0x05, 0x00, -1, 0x03, 0x0042, 0x0009 }, + { 0x05, 0x00, -1, 0x00, 0x0062, 0x0002 }, + { 0x05, 0x00, -1, 0x01, 0x0062, 0x0003 }, + { 0x05, 0x00, -1, 0x02, 0x0062, 0x0004 }, + { 0x05, 0x00, -1, 0x03, 0x0062, 0x0005 }, + { 0x05, 0x00, -1, 0x03, 0x0062, 0x0006 }, + { 0x05, 0x00, -1, 0x03, 0x0062, 0x0007 }, + { 0x05, 0x00, -1, 0x03, 0x0062, 0x0008 }, + { 0x05, 0x00, -1, 0x03, 0x0062, 0x0009 }, + { 0x02, 0x01, -1, 0x03, 0x000a, 0x000a }, + { 0x02, 0x01, -1, 0x03, 0x000a, 0x000c }, + { 0x02, 0x02, -1, 0x03, 0x000a, 0x000e }, + { 0x02, 0x02, -1, 0x03, 0x000a, 0x0012 }, + { 0x02, 0x03, -1, 0x03, 0x000a, 0x0016 }, + { 0x02, 0x03, -1, 0x03, 0x000a, 0x001e }, + { 0x02, 0x04, -1, 0x03, 0x000a, 0x0026 }, + { 0x02, 0x04, -1, 0x03, 0x000a, 0x0036 }, + { 0x02, 0x01, -1, 0x03, 0x000e, 0x000a }, + { 0x02, 0x01, -1, 0x03, 0x000e, 0x000c }, + { 0x02, 0x02, -1, 0x03, 0x000e, 0x000e }, + { 0x02, 0x02, -1, 0x03, 0x000e, 0x0012 }, + { 0x02, 0x03, -1, 0x03, 0x000e, 0x0016 }, + { 0x02, 0x03, -1, 0x03, 0x000e, 0x001e }, + { 0x02, 0x04, -1, 0x03, 0x000e, 0x0026 }, + { 0x02, 0x04, -1, 0x03, 0x000e, 0x0036 }, + { 0x03, 0x01, -1, 0x03, 0x0012, 0x000a }, + { 0x03, 0x01, -1, 0x03, 0x0012, 0x000c }, + { 0x03, 0x02, -1, 0x03, 0x0012, 0x000e }, + { 0x03, 0x02, -1, 0x03, 0x0012, 0x0012 }, + { 0x03, 0x03, -1, 0x03, 0x0012, 0x0016 }, + { 0x03, 0x03, -1, 0x03, 0x0012, 0x001e }, + { 0x03, 0x04, -1, 0x03, 0x0012, 0x0026 }, + { 0x03, 0x04, -1, 0x03, 0x0012, 0x0036 }, + { 0x03, 0x01, -1, 0x03, 0x001a, 0x000a }, + { 0x03, 0x01, -1, 0x03, 0x001a, 0x000c }, + { 0x03, 0x02, -1, 0x03, 0x001a, 0x000e }, + { 0x03, 0x02, -1, 0x03, 0x001a, 0x0012 }, + { 0x03, 0x03, -1, 0x03, 0x001a, 0x0016 }, + { 0x03, 0x03, -1, 0x03, 0x001a, 0x001e }, + { 0x03, 0x04, -1, 0x03, 0x001a, 0x0026 }, + { 0x03, 0x04, -1, 0x03, 0x001a, 0x0036 }, + { 0x04, 0x01, -1, 0x03, 0x0022, 0x000a }, + { 0x04, 0x01, -1, 0x03, 0x0022, 0x000c }, + { 0x04, 0x02, -1, 0x03, 0x0022, 0x000e }, + { 0x04, 0x02, -1, 0x03, 0x0022, 0x0012 }, + { 0x04, 0x03, -1, 0x03, 0x0022, 0x0016 }, + { 0x04, 0x03, -1, 0x03, 0x0022, 0x001e }, + { 0x04, 0x04, -1, 0x03, 0x0022, 0x0026 }, + { 0x04, 0x04, -1, 0x03, 0x0022, 0x0036 }, + { 0x04, 0x01, -1, 0x03, 0x0032, 0x000a }, + { 0x04, 0x01, -1, 0x03, 0x0032, 0x000c }, + { 0x04, 0x02, -1, 0x03, 0x0032, 0x000e }, + { 0x04, 0x02, -1, 0x03, 0x0032, 0x0012 }, + { 0x04, 0x03, -1, 0x03, 0x0032, 0x0016 }, + { 0x04, 0x03, -1, 0x03, 0x0032, 0x001e }, + { 0x04, 0x04, -1, 0x03, 0x0032, 0x0026 }, + { 0x04, 0x04, -1, 0x03, 0x0032, 0x0036 }, + { 0x05, 0x01, -1, 0x03, 0x0042, 0x000a }, + { 0x05, 0x01, -1, 0x03, 0x0042, 0x000c }, + { 0x05, 0x02, -1, 0x03, 0x0042, 0x000e }, + { 0x05, 0x02, -1, 0x03, 0x0042, 0x0012 }, + { 0x05, 0x03, -1, 0x03, 0x0042, 0x0016 }, + { 0x05, 0x03, -1, 0x03, 0x0042, 0x001e }, + { 0x05, 0x04, -1, 0x03, 0x0042, 0x0026 }, + { 0x05, 0x04, -1, 0x03, 0x0042, 0x0036 }, + { 0x05, 0x01, -1, 0x03, 0x0062, 0x000a }, + { 0x05, 0x01, -1, 0x03, 0x0062, 0x000c }, + { 0x05, 0x02, -1, 0x03, 0x0062, 0x000e }, + { 0x05, 0x02, -1, 0x03, 0x0062, 0x0012 }, + { 0x05, 0x03, -1, 0x03, 0x0062, 0x0016 }, + { 0x05, 0x03, -1, 0x03, 0x0062, 0x001e }, + { 0x05, 0x04, -1, 0x03, 0x0062, 0x0026 }, + { 0x05, 0x04, -1, 0x03, 0x0062, 0x0036 }, + { 0x00, 0x05, -1, 0x03, 0x0000, 0x0046 }, + { 0x00, 0x05, -1, 0x03, 0x0000, 0x0066 }, + { 0x00, 0x06, -1, 0x03, 0x0000, 0x0086 }, + { 0x00, 0x07, -1, 0x03, 0x0000, 0x00c6 }, + { 0x00, 0x08, -1, 0x03, 0x0000, 0x0146 }, + { 0x00, 0x09, -1, 0x03, 0x0000, 0x0246 }, + { 0x00, 0x0a, -1, 0x03, 0x0000, 0x0446 }, + { 0x00, 0x18, -1, 0x03, 0x0000, 0x0846 }, + { 0x00, 0x05, -1, 0x03, 0x0001, 0x0046 }, + { 0x00, 0x05, -1, 0x03, 0x0001, 0x0066 }, + { 0x00, 0x06, -1, 0x03, 0x0001, 0x0086 }, + { 0x00, 0x07, -1, 0x03, 0x0001, 0x00c6 }, + { 0x00, 0x08, -1, 0x03, 0x0001, 0x0146 }, + { 0x00, 0x09, -1, 0x03, 0x0001, 0x0246 }, + { 0x00, 0x0a, -1, 0x03, 0x0001, 0x0446 }, + { 0x00, 0x18, -1, 0x03, 0x0001, 0x0846 }, + { 0x00, 0x05, -1, 0x03, 0x0002, 0x0046 }, + { 0x00, 0x05, -1, 0x03, 0x0002, 0x0066 }, + { 0x00, 0x06, -1, 0x03, 0x0002, 0x0086 }, + { 0x00, 0x07, -1, 0x03, 0x0002, 0x00c6 }, + { 0x00, 0x08, -1, 0x03, 0x0002, 0x0146 }, + { 0x00, 0x09, -1, 0x03, 0x0002, 0x0246 }, + { 0x00, 0x0a, -1, 0x03, 0x0002, 0x0446 }, + { 0x00, 0x18, -1, 0x03, 0x0002, 0x0846 }, + { 0x00, 0x05, -1, 0x03, 0x0003, 0x0046 }, + { 0x00, 0x05, -1, 0x03, 0x0003, 0x0066 }, + { 0x00, 0x06, -1, 0x03, 0x0003, 0x0086 }, + { 0x00, 0x07, -1, 0x03, 0x0003, 0x00c6 }, + { 0x00, 0x08, -1, 0x03, 0x0003, 0x0146 }, + { 0x00, 0x09, -1, 0x03, 0x0003, 0x0246 }, + { 0x00, 0x0a, -1, 0x03, 0x0003, 0x0446 }, + { 0x00, 0x18, -1, 0x03, 0x0003, 0x0846 }, + { 0x00, 0x05, -1, 0x03, 0x0004, 0x0046 }, + { 0x00, 0x05, -1, 0x03, 0x0004, 0x0066 }, + { 0x00, 0x06, -1, 0x03, 0x0004, 0x0086 }, + { 0x00, 0x07, -1, 0x03, 0x0004, 0x00c6 }, + { 0x00, 0x08, -1, 0x03, 0x0004, 0x0146 }, + { 0x00, 0x09, -1, 0x03, 0x0004, 0x0246 }, + { 0x00, 0x0a, -1, 0x03, 0x0004, 0x0446 }, + { 0x00, 0x18, -1, 0x03, 0x0004, 0x0846 }, + { 0x00, 0x05, -1, 0x03, 0x0005, 0x0046 }, + { 0x00, 0x05, -1, 0x03, 0x0005, 0x0066 }, + { 0x00, 0x06, -1, 0x03, 0x0005, 0x0086 }, + { 0x00, 0x07, -1, 0x03, 0x0005, 0x00c6 }, + { 0x00, 0x08, -1, 0x03, 0x0005, 0x0146 }, + { 0x00, 0x09, -1, 0x03, 0x0005, 0x0246 }, + { 0x00, 0x0a, -1, 0x03, 0x0005, 0x0446 }, + { 0x00, 0x18, -1, 0x03, 0x0005, 0x0846 }, + { 0x01, 0x05, -1, 0x03, 0x0006, 0x0046 }, + { 0x01, 0x05, -1, 0x03, 0x0006, 0x0066 }, + { 0x01, 0x06, -1, 0x03, 0x0006, 0x0086 }, + { 0x01, 0x07, -1, 0x03, 0x0006, 0x00c6 }, + { 0x01, 0x08, -1, 0x03, 0x0006, 0x0146 }, + { 0x01, 0x09, -1, 0x03, 0x0006, 0x0246 }, + { 0x01, 0x0a, -1, 0x03, 0x0006, 0x0446 }, + { 0x01, 0x18, -1, 0x03, 0x0006, 0x0846 }, + { 0x01, 0x05, -1, 0x03, 0x0008, 0x0046 }, + { 0x01, 0x05, -1, 0x03, 0x0008, 0x0066 }, + { 0x01, 0x06, -1, 0x03, 0x0008, 0x0086 }, + { 0x01, 0x07, -1, 0x03, 0x0008, 0x00c6 }, + { 0x01, 0x08, -1, 0x03, 0x0008, 0x0146 }, + { 0x01, 0x09, -1, 0x03, 0x0008, 0x0246 }, + { 0x01, 0x0a, -1, 0x03, 0x0008, 0x0446 }, + { 0x01, 0x18, -1, 0x03, 0x0008, 0x0846 }, + { 0x06, 0x00, -1, 0x00, 0x0082, 0x0002 }, + { 0x06, 0x00, -1, 0x01, 0x0082, 0x0003 }, + { 0x06, 0x00, -1, 0x02, 0x0082, 0x0004 }, + { 0x06, 0x00, -1, 0x03, 0x0082, 0x0005 }, + { 0x06, 0x00, -1, 0x03, 0x0082, 0x0006 }, + { 0x06, 0x00, -1, 0x03, 0x0082, 0x0007 }, + { 0x06, 0x00, -1, 0x03, 0x0082, 0x0008 }, + { 0x06, 0x00, -1, 0x03, 0x0082, 0x0009 }, + { 0x07, 0x00, -1, 0x00, 0x00c2, 0x0002 }, + { 0x07, 0x00, -1, 0x01, 0x00c2, 0x0003 }, + { 0x07, 0x00, -1, 0x02, 0x00c2, 0x0004 }, + { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0005 }, + { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0006 }, + { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0007 }, + { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0008 }, + { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0009 }, + { 0x08, 0x00, -1, 0x00, 0x0142, 0x0002 }, + { 0x08, 0x00, -1, 0x01, 0x0142, 0x0003 }, + { 0x08, 0x00, -1, 0x02, 0x0142, 0x0004 }, + { 0x08, 0x00, -1, 0x03, 0x0142, 0x0005 }, + { 0x08, 0x00, -1, 0x03, 0x0142, 0x0006 }, + { 0x08, 0x00, -1, 0x03, 0x0142, 0x0007 }, + { 0x08, 0x00, -1, 0x03, 0x0142, 0x0008 }, + { 0x08, 0x00, -1, 0x03, 0x0142, 0x0009 }, + { 0x09, 0x00, -1, 0x00, 0x0242, 0x0002 }, + { 0x09, 0x00, -1, 0x01, 0x0242, 0x0003 }, + { 0x09, 0x00, -1, 0x02, 0x0242, 0x0004 }, + { 0x09, 0x00, -1, 0x03, 0x0242, 0x0005 }, + { 0x09, 0x00, -1, 0x03, 0x0242, 0x0006 }, + { 0x09, 0x00, -1, 0x03, 0x0242, 0x0007 }, + { 0x09, 0x00, -1, 0x03, 0x0242, 0x0008 }, + { 0x09, 0x00, -1, 0x03, 0x0242, 0x0009 }, + { 0x0a, 0x00, -1, 0x00, 0x0442, 0x0002 }, + { 0x0a, 0x00, -1, 0x01, 0x0442, 0x0003 }, + { 0x0a, 0x00, -1, 0x02, 0x0442, 0x0004 }, + { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0005 }, + { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0006 }, + { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0007 }, + { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0008 }, + { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0009 }, + { 0x0c, 0x00, -1, 0x00, 0x0842, 0x0002 }, + { 0x0c, 0x00, -1, 0x01, 0x0842, 0x0003 }, + { 0x0c, 0x00, -1, 0x02, 0x0842, 0x0004 }, + { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0005 }, + { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0006 }, + { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0007 }, + { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0008 }, + { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0009 }, + { 0x0e, 0x00, -1, 0x00, 0x1842, 0x0002 }, + { 0x0e, 0x00, -1, 0x01, 0x1842, 0x0003 }, + { 0x0e, 0x00, -1, 0x02, 0x1842, 0x0004 }, + { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0005 }, + { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0006 }, + { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0007 }, + { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0008 }, + { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0009 }, + { 0x18, 0x00, -1, 0x00, 0x5842, 0x0002 }, + { 0x18, 0x00, -1, 0x01, 0x5842, 0x0003 }, + { 0x18, 0x00, -1, 0x02, 0x5842, 0x0004 }, + { 0x18, 0x00, -1, 0x03, 0x5842, 0x0005 }, + { 0x18, 0x00, -1, 0x03, 0x5842, 0x0006 }, + { 0x18, 0x00, -1, 0x03, 0x5842, 0x0007 }, + { 0x18, 0x00, -1, 0x03, 0x5842, 0x0008 }, + { 0x18, 0x00, -1, 0x03, 0x5842, 0x0009 }, + { 0x02, 0x05, -1, 0x03, 0x000a, 0x0046 }, + { 0x02, 0x05, -1, 0x03, 0x000a, 0x0066 }, + { 0x02, 0x06, -1, 0x03, 0x000a, 0x0086 }, + { 0x02, 0x07, -1, 0x03, 0x000a, 0x00c6 }, + { 0x02, 0x08, -1, 0x03, 0x000a, 0x0146 }, + { 0x02, 0x09, -1, 0x03, 0x000a, 0x0246 }, + { 0x02, 0x0a, -1, 0x03, 0x000a, 0x0446 }, + { 0x02, 0x18, -1, 0x03, 0x000a, 0x0846 }, + { 0x02, 0x05, -1, 0x03, 0x000e, 0x0046 }, + { 0x02, 0x05, -1, 0x03, 0x000e, 0x0066 }, + { 0x02, 0x06, -1, 0x03, 0x000e, 0x0086 }, + { 0x02, 0x07, -1, 0x03, 0x000e, 0x00c6 }, + { 0x02, 0x08, -1, 0x03, 0x000e, 0x0146 }, + { 0x02, 0x09, -1, 0x03, 0x000e, 0x0246 }, + { 0x02, 0x0a, -1, 0x03, 0x000e, 0x0446 }, + { 0x02, 0x18, -1, 0x03, 0x000e, 0x0846 }, + { 0x03, 0x05, -1, 0x03, 0x0012, 0x0046 }, + { 0x03, 0x05, -1, 0x03, 0x0012, 0x0066 }, + { 0x03, 0x06, -1, 0x03, 0x0012, 0x0086 }, + { 0x03, 0x07, -1, 0x03, 0x0012, 0x00c6 }, + { 0x03, 0x08, -1, 0x03, 0x0012, 0x0146 }, + { 0x03, 0x09, -1, 0x03, 0x0012, 0x0246 }, + { 0x03, 0x0a, -1, 0x03, 0x0012, 0x0446 }, + { 0x03, 0x18, -1, 0x03, 0x0012, 0x0846 }, + { 0x03, 0x05, -1, 0x03, 0x001a, 0x0046 }, + { 0x03, 0x05, -1, 0x03, 0x001a, 0x0066 }, + { 0x03, 0x06, -1, 0x03, 0x001a, 0x0086 }, + { 0x03, 0x07, -1, 0x03, 0x001a, 0x00c6 }, + { 0x03, 0x08, -1, 0x03, 0x001a, 0x0146 }, + { 0x03, 0x09, -1, 0x03, 0x001a, 0x0246 }, + { 0x03, 0x0a, -1, 0x03, 0x001a, 0x0446 }, + { 0x03, 0x18, -1, 0x03, 0x001a, 0x0846 }, + { 0x04, 0x05, -1, 0x03, 0x0022, 0x0046 }, + { 0x04, 0x05, -1, 0x03, 0x0022, 0x0066 }, + { 0x04, 0x06, -1, 0x03, 0x0022, 0x0086 }, + { 0x04, 0x07, -1, 0x03, 0x0022, 0x00c6 }, + { 0x04, 0x08, -1, 0x03, 0x0022, 0x0146 }, + { 0x04, 0x09, -1, 0x03, 0x0022, 0x0246 }, + { 0x04, 0x0a, -1, 0x03, 0x0022, 0x0446 }, + { 0x04, 0x18, -1, 0x03, 0x0022, 0x0846 }, + { 0x04, 0x05, -1, 0x03, 0x0032, 0x0046 }, + { 0x04, 0x05, -1, 0x03, 0x0032, 0x0066 }, + { 0x04, 0x06, -1, 0x03, 0x0032, 0x0086 }, + { 0x04, 0x07, -1, 0x03, 0x0032, 0x00c6 }, + { 0x04, 0x08, -1, 0x03, 0x0032, 0x0146 }, + { 0x04, 0x09, -1, 0x03, 0x0032, 0x0246 }, + { 0x04, 0x0a, -1, 0x03, 0x0032, 0x0446 }, + { 0x04, 0x18, -1, 0x03, 0x0032, 0x0846 }, + { 0x05, 0x05, -1, 0x03, 0x0042, 0x0046 }, + { 0x05, 0x05, -1, 0x03, 0x0042, 0x0066 }, + { 0x05, 0x06, -1, 0x03, 0x0042, 0x0086 }, + { 0x05, 0x07, -1, 0x03, 0x0042, 0x00c6 }, + { 0x05, 0x08, -1, 0x03, 0x0042, 0x0146 }, + { 0x05, 0x09, -1, 0x03, 0x0042, 0x0246 }, + { 0x05, 0x0a, -1, 0x03, 0x0042, 0x0446 }, + { 0x05, 0x18, -1, 0x03, 0x0042, 0x0846 }, + { 0x05, 0x05, -1, 0x03, 0x0062, 0x0046 }, + { 0x05, 0x05, -1, 0x03, 0x0062, 0x0066 }, + { 0x05, 0x06, -1, 0x03, 0x0062, 0x0086 }, + { 0x05, 0x07, -1, 0x03, 0x0062, 0x00c6 }, + { 0x05, 0x08, -1, 0x03, 0x0062, 0x0146 }, + { 0x05, 0x09, -1, 0x03, 0x0062, 0x0246 }, + { 0x05, 0x0a, -1, 0x03, 0x0062, 0x0446 }, + { 0x05, 0x18, -1, 0x03, 0x0062, 0x0846 }, + { 0x06, 0x01, -1, 0x03, 0x0082, 0x000a }, + { 0x06, 0x01, -1, 0x03, 0x0082, 0x000c }, + { 0x06, 0x02, -1, 0x03, 0x0082, 0x000e }, + { 0x06, 0x02, -1, 0x03, 0x0082, 0x0012 }, + { 0x06, 0x03, -1, 0x03, 0x0082, 0x0016 }, + { 0x06, 0x03, -1, 0x03, 0x0082, 0x001e }, + { 0x06, 0x04, -1, 0x03, 0x0082, 0x0026 }, + { 0x06, 0x04, -1, 0x03, 0x0082, 0x0036 }, + { 0x07, 0x01, -1, 0x03, 0x00c2, 0x000a }, + { 0x07, 0x01, -1, 0x03, 0x00c2, 0x000c }, + { 0x07, 0x02, -1, 0x03, 0x00c2, 0x000e }, + { 0x07, 0x02, -1, 0x03, 0x00c2, 0x0012 }, + { 0x07, 0x03, -1, 0x03, 0x00c2, 0x0016 }, + { 0x07, 0x03, -1, 0x03, 0x00c2, 0x001e }, + { 0x07, 0x04, -1, 0x03, 0x00c2, 0x0026 }, + { 0x07, 0x04, -1, 0x03, 0x00c2, 0x0036 }, + { 0x08, 0x01, -1, 0x03, 0x0142, 0x000a }, + { 0x08, 0x01, -1, 0x03, 0x0142, 0x000c }, + { 0x08, 0x02, -1, 0x03, 0x0142, 0x000e }, + { 0x08, 0x02, -1, 0x03, 0x0142, 0x0012 }, + { 0x08, 0x03, -1, 0x03, 0x0142, 0x0016 }, + { 0x08, 0x03, -1, 0x03, 0x0142, 0x001e }, + { 0x08, 0x04, -1, 0x03, 0x0142, 0x0026 }, + { 0x08, 0x04, -1, 0x03, 0x0142, 0x0036 }, + { 0x09, 0x01, -1, 0x03, 0x0242, 0x000a }, + { 0x09, 0x01, -1, 0x03, 0x0242, 0x000c }, + { 0x09, 0x02, -1, 0x03, 0x0242, 0x000e }, + { 0x09, 0x02, -1, 0x03, 0x0242, 0x0012 }, + { 0x09, 0x03, -1, 0x03, 0x0242, 0x0016 }, + { 0x09, 0x03, -1, 0x03, 0x0242, 0x001e }, + { 0x09, 0x04, -1, 0x03, 0x0242, 0x0026 }, + { 0x09, 0x04, -1, 0x03, 0x0242, 0x0036 }, + { 0x0a, 0x01, -1, 0x03, 0x0442, 0x000a }, + { 0x0a, 0x01, -1, 0x03, 0x0442, 0x000c }, + { 0x0a, 0x02, -1, 0x03, 0x0442, 0x000e }, + { 0x0a, 0x02, -1, 0x03, 0x0442, 0x0012 }, + { 0x0a, 0x03, -1, 0x03, 0x0442, 0x0016 }, + { 0x0a, 0x03, -1, 0x03, 0x0442, 0x001e }, + { 0x0a, 0x04, -1, 0x03, 0x0442, 0x0026 }, + { 0x0a, 0x04, -1, 0x03, 0x0442, 0x0036 }, + { 0x0c, 0x01, -1, 0x03, 0x0842, 0x000a }, + { 0x0c, 0x01, -1, 0x03, 0x0842, 0x000c }, + { 0x0c, 0x02, -1, 0x03, 0x0842, 0x000e }, + { 0x0c, 0x02, -1, 0x03, 0x0842, 0x0012 }, + { 0x0c, 0x03, -1, 0x03, 0x0842, 0x0016 }, + { 0x0c, 0x03, -1, 0x03, 0x0842, 0x001e }, + { 0x0c, 0x04, -1, 0x03, 0x0842, 0x0026 }, + { 0x0c, 0x04, -1, 0x03, 0x0842, 0x0036 }, + { 0x0e, 0x01, -1, 0x03, 0x1842, 0x000a }, + { 0x0e, 0x01, -1, 0x03, 0x1842, 0x000c }, + { 0x0e, 0x02, -1, 0x03, 0x1842, 0x000e }, + { 0x0e, 0x02, -1, 0x03, 0x1842, 0x0012 }, + { 0x0e, 0x03, -1, 0x03, 0x1842, 0x0016 }, + { 0x0e, 0x03, -1, 0x03, 0x1842, 0x001e }, + { 0x0e, 0x04, -1, 0x03, 0x1842, 0x0026 }, + { 0x0e, 0x04, -1, 0x03, 0x1842, 0x0036 }, + { 0x18, 0x01, -1, 0x03, 0x5842, 0x000a }, + { 0x18, 0x01, -1, 0x03, 0x5842, 0x000c }, + { 0x18, 0x02, -1, 0x03, 0x5842, 0x000e }, + { 0x18, 0x02, -1, 0x03, 0x5842, 0x0012 }, + { 0x18, 0x03, -1, 0x03, 0x5842, 0x0016 }, + { 0x18, 0x03, -1, 0x03, 0x5842, 0x001e }, + { 0x18, 0x04, -1, 0x03, 0x5842, 0x0026 }, + { 0x18, 0x04, -1, 0x03, 0x5842, 0x0036 }, + { 0x06, 0x05, -1, 0x03, 0x0082, 0x0046 }, + { 0x06, 0x05, -1, 0x03, 0x0082, 0x0066 }, + { 0x06, 0x06, -1, 0x03, 0x0082, 0x0086 }, + { 0x06, 0x07, -1, 0x03, 0x0082, 0x00c6 }, + { 0x06, 0x08, -1, 0x03, 0x0082, 0x0146 }, + { 0x06, 0x09, -1, 0x03, 0x0082, 0x0246 }, + { 0x06, 0x0a, -1, 0x03, 0x0082, 0x0446 }, + { 0x06, 0x18, -1, 0x03, 0x0082, 0x0846 }, + { 0x07, 0x05, -1, 0x03, 0x00c2, 0x0046 }, + { 0x07, 0x05, -1, 0x03, 0x00c2, 0x0066 }, + { 0x07, 0x06, -1, 0x03, 0x00c2, 0x0086 }, + { 0x07, 0x07, -1, 0x03, 0x00c2, 0x00c6 }, + { 0x07, 0x08, -1, 0x03, 0x00c2, 0x0146 }, + { 0x07, 0x09, -1, 0x03, 0x00c2, 0x0246 }, + { 0x07, 0x0a, -1, 0x03, 0x00c2, 0x0446 }, + { 0x07, 0x18, -1, 0x03, 0x00c2, 0x0846 }, + { 0x08, 0x05, -1, 0x03, 0x0142, 0x0046 }, + { 0x08, 0x05, -1, 0x03, 0x0142, 0x0066 }, + { 0x08, 0x06, -1, 0x03, 0x0142, 0x0086 }, + { 0x08, 0x07, -1, 0x03, 0x0142, 0x00c6 }, + { 0x08, 0x08, -1, 0x03, 0x0142, 0x0146 }, + { 0x08, 0x09, -1, 0x03, 0x0142, 0x0246 }, + { 0x08, 0x0a, -1, 0x03, 0x0142, 0x0446 }, + { 0x08, 0x18, -1, 0x03, 0x0142, 0x0846 }, + { 0x09, 0x05, -1, 0x03, 0x0242, 0x0046 }, + { 0x09, 0x05, -1, 0x03, 0x0242, 0x0066 }, + { 0x09, 0x06, -1, 0x03, 0x0242, 0x0086 }, + { 0x09, 0x07, -1, 0x03, 0x0242, 0x00c6 }, + { 0x09, 0x08, -1, 0x03, 0x0242, 0x0146 }, + { 0x09, 0x09, -1, 0x03, 0x0242, 0x0246 }, + { 0x09, 0x0a, -1, 0x03, 0x0242, 0x0446 }, + { 0x09, 0x18, -1, 0x03, 0x0242, 0x0846 }, + { 0x0a, 0x05, -1, 0x03, 0x0442, 0x0046 }, + { 0x0a, 0x05, -1, 0x03, 0x0442, 0x0066 }, + { 0x0a, 0x06, -1, 0x03, 0x0442, 0x0086 }, + { 0x0a, 0x07, -1, 0x03, 0x0442, 0x00c6 }, + { 0x0a, 0x08, -1, 0x03, 0x0442, 0x0146 }, + { 0x0a, 0x09, -1, 0x03, 0x0442, 0x0246 }, + { 0x0a, 0x0a, -1, 0x03, 0x0442, 0x0446 }, + { 0x0a, 0x18, -1, 0x03, 0x0442, 0x0846 }, + { 0x0c, 0x05, -1, 0x03, 0x0842, 0x0046 }, + { 0x0c, 0x05, -1, 0x03, 0x0842, 0x0066 }, + { 0x0c, 0x06, -1, 0x03, 0x0842, 0x0086 }, + { 0x0c, 0x07, -1, 0x03, 0x0842, 0x00c6 }, + { 0x0c, 0x08, -1, 0x03, 0x0842, 0x0146 }, + { 0x0c, 0x09, -1, 0x03, 0x0842, 0x0246 }, + { 0x0c, 0x0a, -1, 0x03, 0x0842, 0x0446 }, + { 0x0c, 0x18, -1, 0x03, 0x0842, 0x0846 }, + { 0x0e, 0x05, -1, 0x03, 0x1842, 0x0046 }, + { 0x0e, 0x05, -1, 0x03, 0x1842, 0x0066 }, + { 0x0e, 0x06, -1, 0x03, 0x1842, 0x0086 }, + { 0x0e, 0x07, -1, 0x03, 0x1842, 0x00c6 }, + { 0x0e, 0x08, -1, 0x03, 0x1842, 0x0146 }, + { 0x0e, 0x09, -1, 0x03, 0x1842, 0x0246 }, + { 0x0e, 0x0a, -1, 0x03, 0x1842, 0x0446 }, + { 0x0e, 0x18, -1, 0x03, 0x1842, 0x0846 }, + { 0x18, 0x05, -1, 0x03, 0x5842, 0x0046 }, + { 0x18, 0x05, -1, 0x03, 0x5842, 0x0066 }, + { 0x18, 0x06, -1, 0x03, 0x5842, 0x0086 }, + { 0x18, 0x07, -1, 0x03, 0x5842, 0x00c6 }, + { 0x18, 0x08, -1, 0x03, 0x5842, 0x0146 }, + { 0x18, 0x09, -1, 0x03, 0x5842, 0x0246 }, + { 0x18, 0x0a, -1, 0x03, 0x5842, 0x0446 }, + { 0x18, 0x18, -1, 0x03, 0x5842, 0x0846 }, +}; + +#endif /* BROTLI_DEC_PREFIX_H_ */ diff --git a/modules/brotli/dec/state.c b/modules/brotli/dec/state.c new file mode 100644 index 0000000000..be6a26680b --- /dev/null +++ b/modules/brotli/dec/state.c @@ -0,0 +1,183 @@ +/* Copyright 2015 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +#include "state.h" + +#include /* free, malloc */ + +#include + +#include "../common/dictionary.h" +#include "huffman.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, + brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { + if (!alloc_func) { + s->alloc_func = BrotliDefaultAllocFunc; + s->free_func = BrotliDefaultFreeFunc; + s->memory_manager_opaque = 0; + } else { + s->alloc_func = alloc_func; + s->free_func = free_func; + s->memory_manager_opaque = opaque; + } + + s->error_code = 0; /* BROTLI_DECODER_NO_ERROR */ + + BrotliInitBitReader(&s->br); + s->state = BROTLI_STATE_UNINITED; + s->large_window = 0; + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; + s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; + s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; + s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; + + s->buffer_length = 0; + s->loop_counter = 0; + s->pos = 0; + s->rb_roundtrips = 0; + s->partial_pos_out = 0; + s->used_input = 0; + + s->block_type_trees = NULL; + s->block_len_trees = NULL; + s->ringbuffer = NULL; + s->ringbuffer_size = 0; + s->new_ringbuffer_size = 0; + s->ringbuffer_mask = 0; + + s->context_map = NULL; + s->context_modes = NULL; + s->dist_context_map = NULL; + s->context_map_slice = NULL; + s->dist_context_map_slice = NULL; + + s->literal_hgroup.codes = NULL; + s->literal_hgroup.htrees = NULL; + s->insert_copy_hgroup.codes = NULL; + s->insert_copy_hgroup.htrees = NULL; + s->distance_hgroup.codes = NULL; + s->distance_hgroup.htrees = NULL; + + s->is_last_metablock = 0; + s->is_uncompressed = 0; + s->is_metadata = 0; + s->should_wrap_ringbuffer = 0; + s->canny_ringbuffer_allocation = 1; + + s->window_bits = 0; + s->max_distance = 0; + s->dist_rb[0] = 16; + s->dist_rb[1] = 15; + s->dist_rb[2] = 11; + s->dist_rb[3] = 4; + s->dist_rb_idx = 0; + s->block_type_trees = NULL; + s->block_len_trees = NULL; + + s->mtf_upper_bound = 63; + + s->compound_dictionary = NULL; + s->dictionary = + BrotliSharedDictionaryCreateInstance(alloc_func, free_func, opaque); + if (!s->dictionary) return BROTLI_FALSE; + + s->metadata_start_func = NULL; + s->metadata_chunk_func = NULL; + s->metadata_callback_opaque = 0; + + return BROTLI_TRUE; +} + +void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s) { + s->meta_block_remaining_len = 0; + s->block_length[0] = BROTLI_BLOCK_SIZE_CAP; + s->block_length[1] = BROTLI_BLOCK_SIZE_CAP; + s->block_length[2] = BROTLI_BLOCK_SIZE_CAP; + s->num_block_types[0] = 1; + s->num_block_types[1] = 1; + s->num_block_types[2] = 1; + s->block_type_rb[0] = 1; + s->block_type_rb[1] = 0; + s->block_type_rb[2] = 1; + s->block_type_rb[3] = 0; + s->block_type_rb[4] = 1; + s->block_type_rb[5] = 0; + s->context_map = NULL; + s->context_modes = NULL; + s->dist_context_map = NULL; + s->context_map_slice = NULL; + s->literal_htree = NULL; + s->dist_context_map_slice = NULL; + s->dist_htree_index = 0; + s->context_lookup = NULL; + s->literal_hgroup.codes = NULL; + s->literal_hgroup.htrees = NULL; + s->insert_copy_hgroup.codes = NULL; + s->insert_copy_hgroup.htrees = NULL; + s->distance_hgroup.codes = NULL; + s->distance_hgroup.htrees = NULL; +} + +void BrotliDecoderStateCleanupAfterMetablock(BrotliDecoderState* s) { + BROTLI_DECODER_FREE(s, s->context_modes); + BROTLI_DECODER_FREE(s, s->context_map); + BROTLI_DECODER_FREE(s, s->dist_context_map); + BROTLI_DECODER_FREE(s, s->literal_hgroup.htrees); + BROTLI_DECODER_FREE(s, s->insert_copy_hgroup.htrees); + BROTLI_DECODER_FREE(s, s->distance_hgroup.htrees); +} + +#ifdef BROTLI_REPORTING +/* When BROTLI_REPORTING is defined extra reporting module have to be linked. */ +void BrotliDecoderOnFinish(const BrotliDecoderState* s); +#define BROTLI_DECODER_ON_FINISH(s) BrotliDecoderOnFinish(s); +#else +#if !defined(BROTLI_DECODER_ON_FINISH) +#define BROTLI_DECODER_ON_FINISH(s) (void)(s); +#endif +#endif + +void BrotliDecoderStateCleanup(BrotliDecoderState* s) { + BrotliDecoderStateCleanupAfterMetablock(s); + + BROTLI_DECODER_ON_FINISH(s); + + BROTLI_DECODER_FREE(s, s->compound_dictionary); + BrotliSharedDictionaryDestroyInstance(s->dictionary); + s->dictionary = NULL; + BROTLI_DECODER_FREE(s, s->ringbuffer); + BROTLI_DECODER_FREE(s, s->block_type_trees); +} + +BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit(BrotliDecoderState* s, + HuffmanTreeGroup* group, brotli_reg_t alphabet_size_max, + brotli_reg_t alphabet_size_limit, brotli_reg_t ntrees) { + /* 376 = 256 (1-st level table) + 4 + 7 + 15 + 31 + 63 (2-nd level mix-tables) + This number is discovered "unlimited" "enough" calculator; it is actually + a wee bigger than required in several cases (especially for alphabets with + less than 16 symbols). */ + const size_t max_table_size = alphabet_size_limit + 376; + const size_t code_size = sizeof(HuffmanCode) * ntrees * max_table_size; + const size_t htree_size = sizeof(HuffmanCode*) * ntrees; + /* Pointer alignment is, hopefully, wider than sizeof(HuffmanCode). */ + HuffmanCode** p = (HuffmanCode**)BROTLI_DECODER_ALLOC(s, + code_size + htree_size); + group->alphabet_size_max = (uint16_t)alphabet_size_max; + group->alphabet_size_limit = (uint16_t)alphabet_size_limit; + group->num_htrees = (uint16_t)ntrees; + group->htrees = p; + group->codes = (HuffmanCode*)(&p[ntrees]); + return !!p; +} + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif diff --git a/modules/brotli/dec/state.h b/modules/brotli/dec/state.h new file mode 100644 index 0000000000..fd250b6842 --- /dev/null +++ b/modules/brotli/dec/state.h @@ -0,0 +1,400 @@ +/* Copyright 2015 Google Inc. All Rights Reserved. + + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ + +/* Brotli state for partial streaming decoding. */ + +#ifndef BROTLI_DEC_STATE_H_ +#define BROTLI_DEC_STATE_H_ + +#include +#include +#include + +#include "../common/constants.h" +#include "../common/dictionary.h" +#include "../common/platform.h" +#include "../common/transform.h" +#include "bit_reader.h" +#include "huffman.h" + +#if defined(__cplusplus) || defined(c_plusplus) +extern "C" { +#endif + +/* Graphviz diagram that describes state transitions: + +digraph States { + graph [compound=true] + concentrate=true + node [shape="box"] + + UNINITED -> {LARGE_WINDOW_BITS -> INITIALIZE} + subgraph cluster_metablock_workflow { + style="rounded" + label=< METABLOCK CYCLE > + METABLOCK_BEGIN -> METABLOCK_HEADER + METABLOCK_HEADER:sw -> METADATA + METABLOCK_HEADER:s -> UNCOMPRESSED + METABLOCK_HEADER:se -> METABLOCK_DONE:ne + METADATA:s -> METABLOCK_DONE:w + UNCOMPRESSED:s -> METABLOCK_DONE:n + METABLOCK_DONE:e -> METABLOCK_BEGIN:e [constraint="false"] + } + INITIALIZE -> METABLOCK_BEGIN + METABLOCK_DONE -> DONE + + subgraph cluster_compressed_metablock { + style="rounded" + label=< COMPRESSED METABLOCK > + + subgraph cluster_command { + style="rounded" + label=< HOT LOOP > + + _METABLOCK_DONE_PORT_ [shape=point style=invis] + + { + // Set different shape for nodes returning from "compressed metablock". + node [shape=invhouse]; CMD_INNER CMD_POST_DECODE_LITERALS; + CMD_POST_WRAP_COPY; CMD_INNER_WRITE; CMD_POST_WRITE_1; + } + + CMD_BEGIN -> CMD_INNER -> CMD_POST_DECODE_LITERALS -> CMD_POST_WRAP_COPY + + // IO ("write") nodes are not in the hot loop! + CMD_INNER_WRITE [style=dashed] + CMD_INNER -> CMD_INNER_WRITE + CMD_POST_WRITE_1 [style=dashed] + CMD_POST_DECODE_LITERALS -> CMD_POST_WRITE_1 + CMD_POST_WRITE_2 [style=dashed] + CMD_POST_WRAP_COPY -> CMD_POST_WRITE_2 + + CMD_POST_WRITE_1 -> CMD_BEGIN:s [constraint="false"] + CMD_INNER_WRITE -> {CMD_INNER CMD_POST_DECODE_LITERALS} + [constraint="false"] + CMD_BEGIN:ne -> CMD_POST_DECODE_LITERALS [constraint="false"] + CMD_POST_WRAP_COPY -> CMD_BEGIN [constraint="false"] + CMD_POST_DECODE_LITERALS -> CMD_BEGIN:ne [constraint="false"] + CMD_POST_WRITE_2 -> CMD_POST_WRAP_COPY [constraint="false"] + {rank=same; CMD_BEGIN; CMD_INNER; CMD_POST_DECODE_LITERALS; + CMD_POST_WRAP_COPY} + {rank=same; CMD_INNER_WRITE; CMD_POST_WRITE_1; CMD_POST_WRITE_2} + + {CMD_INNER CMD_POST_DECODE_LITERALS CMD_POST_WRAP_COPY} -> + _METABLOCK_DONE_PORT_ [style=invis] + {CMD_INNER_WRITE CMD_POST_WRITE_1} -> _METABLOCK_DONE_PORT_ + [constraint="false" style=invis] + } + + BEFORE_COMPRESSED_METABLOCK_HEADER:s -> HUFFMAN_CODE_0:n + HUFFMAN_CODE_0 -> HUFFMAN_CODE_1 -> HUFFMAN_CODE_2 -> HUFFMAN_CODE_3 + HUFFMAN_CODE_0 -> METABLOCK_HEADER_2 -> CONTEXT_MODES -> CONTEXT_MAP_1 + CONTEXT_MAP_1 -> CONTEXT_MAP_2 -> TREE_GROUP + TREE_GROUP -> BEFORE_COMPRESSED_METABLOCK_BODY:e + BEFORE_COMPRESSED_METABLOCK_BODY:s -> CMD_BEGIN:n + + HUFFMAN_CODE_3:e -> HUFFMAN_CODE_0:ne [constraint="false"] + {rank=same; HUFFMAN_CODE_0; HUFFMAN_CODE_1; HUFFMAN_CODE_2; HUFFMAN_CODE_3} + {rank=same; METABLOCK_HEADER_2; CONTEXT_MODES; CONTEXT_MAP_1; CONTEXT_MAP_2; + TREE_GROUP} + } + METABLOCK_HEADER:e -> BEFORE_COMPRESSED_METABLOCK_HEADER:n + + _METABLOCK_DONE_PORT_ -> METABLOCK_DONE:se + [constraint="false" ltail=cluster_command] + + UNINITED [shape=Mdiamond]; + DONE [shape=Msquare]; +} + + + */ + +typedef enum { + BROTLI_STATE_UNINITED, + BROTLI_STATE_LARGE_WINDOW_BITS, + BROTLI_STATE_INITIALIZE, + BROTLI_STATE_METABLOCK_BEGIN, + BROTLI_STATE_METABLOCK_HEADER, + BROTLI_STATE_METABLOCK_HEADER_2, + BROTLI_STATE_CONTEXT_MODES, + BROTLI_STATE_COMMAND_BEGIN, + BROTLI_STATE_COMMAND_INNER, + BROTLI_STATE_COMMAND_POST_DECODE_LITERALS, + BROTLI_STATE_COMMAND_POST_WRAP_COPY, + BROTLI_STATE_UNCOMPRESSED, + BROTLI_STATE_METADATA, + BROTLI_STATE_COMMAND_INNER_WRITE, + BROTLI_STATE_METABLOCK_DONE, + BROTLI_STATE_COMMAND_POST_WRITE_1, + BROTLI_STATE_COMMAND_POST_WRITE_2, + BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER, + BROTLI_STATE_HUFFMAN_CODE_0, + BROTLI_STATE_HUFFMAN_CODE_1, + BROTLI_STATE_HUFFMAN_CODE_2, + BROTLI_STATE_HUFFMAN_CODE_3, + BROTLI_STATE_CONTEXT_MAP_1, + BROTLI_STATE_CONTEXT_MAP_2, + BROTLI_STATE_TREE_GROUP, + BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY, + BROTLI_STATE_DONE +} BrotliRunningState; + +typedef enum { + BROTLI_STATE_METABLOCK_HEADER_NONE, + BROTLI_STATE_METABLOCK_HEADER_EMPTY, + BROTLI_STATE_METABLOCK_HEADER_NIBBLES, + BROTLI_STATE_METABLOCK_HEADER_SIZE, + BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED, + BROTLI_STATE_METABLOCK_HEADER_RESERVED, + BROTLI_STATE_METABLOCK_HEADER_BYTES, + BROTLI_STATE_METABLOCK_HEADER_METADATA +} BrotliRunningMetablockHeaderState; + +typedef enum { + BROTLI_STATE_UNCOMPRESSED_NONE, + BROTLI_STATE_UNCOMPRESSED_WRITE +} BrotliRunningUncompressedState; + +typedef enum { + BROTLI_STATE_TREE_GROUP_NONE, + BROTLI_STATE_TREE_GROUP_LOOP +} BrotliRunningTreeGroupState; + +typedef enum { + BROTLI_STATE_CONTEXT_MAP_NONE, + BROTLI_STATE_CONTEXT_MAP_READ_PREFIX, + BROTLI_STATE_CONTEXT_MAP_HUFFMAN, + BROTLI_STATE_CONTEXT_MAP_DECODE, + BROTLI_STATE_CONTEXT_MAP_TRANSFORM +} BrotliRunningContextMapState; + +typedef enum { + BROTLI_STATE_HUFFMAN_NONE, + BROTLI_STATE_HUFFMAN_SIMPLE_SIZE, + BROTLI_STATE_HUFFMAN_SIMPLE_READ, + BROTLI_STATE_HUFFMAN_SIMPLE_BUILD, + BROTLI_STATE_HUFFMAN_COMPLEX, + BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS +} BrotliRunningHuffmanState; + +typedef enum { + BROTLI_STATE_DECODE_UINT8_NONE, + BROTLI_STATE_DECODE_UINT8_SHORT, + BROTLI_STATE_DECODE_UINT8_LONG +} BrotliRunningDecodeUint8State; + +typedef enum { + BROTLI_STATE_READ_BLOCK_LENGTH_NONE, + BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX +} BrotliRunningReadBlockLengthState; + +/* BrotliDecoderState addon, used for Compound Dictionary functionality. */ +typedef struct BrotliDecoderCompoundDictionary { + int num_chunks; + int total_size; + int br_index; + int br_offset; + int br_length; + int br_copied; + const uint8_t* chunks[16]; + int chunk_offsets[16]; + int block_bits; + uint8_t block_map[256]; +} BrotliDecoderCompoundDictionary; + +typedef struct BrotliMetablockHeaderArena { + BrotliRunningTreeGroupState substate_tree_group; + BrotliRunningContextMapState substate_context_map; + BrotliRunningHuffmanState substate_huffman; + + brotli_reg_t sub_loop_counter; + + brotli_reg_t repeat_code_len; + brotli_reg_t prev_code_len; + + /* For ReadHuffmanCode. */ + brotli_reg_t symbol; + brotli_reg_t repeat; + brotli_reg_t space; + + /* Huffman table for "histograms". */ + HuffmanCode table[32]; + /* List of heads of symbol chains. */ + uint16_t* symbol_lists; + /* Storage from symbol_lists. */ + uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 + + BROTLI_NUM_COMMAND_SYMBOLS]; + /* Tails of symbol chains. */ + int next_symbol[32]; + uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES]; + /* Population counts for the code lengths. */ + uint16_t code_length_histo[16]; + /* TODO(eustas): +2 bytes padding */ + + /* For HuffmanTreeGroupDecode. */ + int htree_index; + HuffmanCode* next; + + /* For DecodeContextMap. */ + brotli_reg_t context_index; + brotli_reg_t max_run_length_prefix; + brotli_reg_t code; + HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272]; +} BrotliMetablockHeaderArena; + +typedef struct BrotliMetablockBodyArena { + uint8_t dist_extra_bits[544]; + brotli_reg_t dist_offset[544]; +} BrotliMetablockBodyArena; + +struct BrotliDecoderStateStruct { + BrotliRunningState state; + + /* This counter is reused for several disjoint loops. */ + int loop_counter; + + BrotliBitReader br; + + brotli_alloc_func alloc_func; + brotli_free_func free_func; + void* memory_manager_opaque; + + /* Temporary storage for remaining input. Brotli stream format is designed in + a way, that 64 bits are enough to make progress in decoding. */ + union { + uint64_t u64; + uint8_t u8[8]; + } buffer; + brotli_reg_t buffer_length; + + int pos; + int max_backward_distance; + int max_distance; + int ringbuffer_size; + int ringbuffer_mask; + int dist_rb_idx; + int dist_rb[4]; + int error_code; + int meta_block_remaining_len; + + uint8_t* ringbuffer; + uint8_t* ringbuffer_end; + HuffmanCode* htree_command; + const uint8_t* context_lookup; + uint8_t* context_map_slice; + uint8_t* dist_context_map_slice; + + /* This ring buffer holds a few past copy distances that will be used by + some special distance codes. */ + HuffmanTreeGroup literal_hgroup; + HuffmanTreeGroup insert_copy_hgroup; + HuffmanTreeGroup distance_hgroup; + HuffmanCode* block_type_trees; + HuffmanCode* block_len_trees; + /* This is true if the literal context map histogram type always matches the + block type. It is then not needed to keep the context (faster decoding). */ + int trivial_literal_context; + /* Distance context is actual after command is decoded and before distance is + computed. After distance computation it is used as a temporary variable. */ + int distance_context; + brotli_reg_t block_length[3]; + brotli_reg_t block_length_index; + brotli_reg_t num_block_types[3]; + brotli_reg_t block_type_rb[6]; + brotli_reg_t distance_postfix_bits; + brotli_reg_t num_direct_distance_codes; + brotli_reg_t num_dist_htrees; + uint8_t* dist_context_map; + HuffmanCode* literal_htree; + + /* For partial write operations. */ + size_t rb_roundtrips; /* how many times we went around the ring-buffer */ + size_t partial_pos_out; /* how much output to the user in total */ + + /* For InverseMoveToFrontTransform. */ + brotli_reg_t mtf_upper_bound; + uint32_t mtf[64 + 1]; + + int copy_length; + int distance_code; + + uint8_t dist_htree_index; + /* TODO(eustas): +3 bytes padding */ + + /* Less used attributes are at the end of this struct. */ + + brotli_decoder_metadata_start_func metadata_start_func; + brotli_decoder_metadata_chunk_func metadata_chunk_func; + void* metadata_callback_opaque; + + /* For reporting. */ + uint64_t used_input; /* how many bytes of input are consumed */ + + /* States inside function calls. */ + BrotliRunningMetablockHeaderState substate_metablock_header; + BrotliRunningUncompressedState substate_uncompressed; + BrotliRunningDecodeUint8State substate_decode_uint8; + BrotliRunningReadBlockLengthState substate_read_block_length; + + int new_ringbuffer_size; + /* TODO(eustas): +4 bytes padding */ + + unsigned int is_last_metablock : 1; + unsigned int is_uncompressed : 1; + unsigned int is_metadata : 1; + unsigned int should_wrap_ringbuffer : 1; + unsigned int canny_ringbuffer_allocation : 1; + unsigned int large_window : 1; + unsigned int window_bits : 6; + unsigned int size_nibbles : 8; + /* TODO(eustas): +12 bits padding */ + + brotli_reg_t num_literal_htrees; + uint8_t* context_map; + uint8_t* context_modes; + + BrotliSharedDictionary* dictionary; + BrotliDecoderCompoundDictionary* compound_dictionary; + + uint32_t trivial_literal_contexts[8]; /* 256 bits */ + + union { + BrotliMetablockHeaderArena header; + BrotliMetablockBodyArena body; + } arena; +}; + +typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal; +#define BrotliDecoderState BrotliDecoderStateInternal + +BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, + brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque); +BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s); +BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s); +BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock( + BrotliDecoderState* s); +BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit( + BrotliDecoderState* s, HuffmanTreeGroup* group, + brotli_reg_t alphabet_size_max, brotli_reg_t alphabet_size_limit, + brotli_reg_t ntrees); + +#define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L) + +#define BROTLI_DECODER_FREE(S, X) { \ + S->free_func(S->memory_manager_opaque, X); \ + X = NULL; \ +} + +/* Literal/Command/Distance block size maximum; same as maximum metablock size; + used as block size when there is no block switching. */ +#define BROTLI_BLOCK_SIZE_CAP (1U << 24) + +#if defined(__cplusplus) || defined(c_plusplus) +} /* extern "C" */ +#endif + +#endif /* BROTLI_DEC_STATE_H_ */ -- cgit v1.2.3