diff --git a/SOURCES/rhbz1881156.patch b/SOURCES/rhbz1881156.patch new file mode 100644 index 0000000..faf58f4 --- /dev/null +++ b/SOURCES/rhbz1881156.patch @@ -0,0 +1,2152 @@ +From ce3b0936620b9abb2d6d21d3e608f37f3c7302d9 Mon Sep 17 00:00:00 2001 +From: rpm-build +Date: Thu, 1 Oct 2020 10:34:27 +0200 +Subject: [PATCH] rhbz1881156.patch + +--- + c/common/constants.c | 15 + + c/common/constants.h | 136 ++++++++ + c/common/platform.h | 8 +- + c/dec/bit_reader.c | 28 ++ + c/dec/bit_reader.h | 74 +++- + c/dec/decode.c | 695 ++++++++++++++++++++++---------------- + c/dec/huffman.h | 71 +++- + c/dec/prefix.h | 18 - + c/dec/state.c | 23 +- + c/dec/state.h | 181 ++++++++-- + c/enc/brotli_bit_stream.c | 21 +- + research/brotli_decoder.c | 1 + + scripts/sources.lst | 1 + + setup.py | 1 + + 14 files changed, 865 insertions(+), 408 deletions(-) + create mode 100644 c/common/constants.c + +diff --git a/c/common/constants.c b/c/common/constants.c +new file mode 100644 +index 0000000..6bad9f6 +--- /dev/null ++++ b/c/common/constants.c +@@ -0,0 +1,15 @@ ++/* 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 "./constants.h" ++ ++const BrotliPrefixCodeRange ++ _kBrotliPrefixCodeRanges[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = { ++ {1, 2}, {5, 2}, {9, 2}, {13, 2}, {17, 3}, {25, 3}, ++ {33, 3}, {41, 3}, {49, 4}, {65, 4}, {81, 4}, {97, 4}, ++ {113, 5}, {145, 5}, {177, 5}, {209, 5}, {241, 6}, {305, 6}, ++ {369, 7}, {497, 8}, {753, 9}, {1265, 10}, {2289, 11}, {4337, 12}, ++ {8433, 13}, {16625, 24}}; +diff --git a/c/common/constants.h b/c/common/constants.h +index d1b88d1..e848195 100644 +--- a/c/common/constants.h ++++ b/c/common/constants.h +@@ -4,9 +4,18 @@ + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + */ + ++/** ++ * @file ++ * Common constants used in decoder and encoder API. ++ */ ++ + #ifndef BROTLI_COMMON_CONSTANTS_H_ + #define BROTLI_COMMON_CONSTANTS_H_ + ++#include "./platform.h" ++#include ++#include ++ + /* Specification: 7.3. Encoding of the context map */ + #define BROTLI_CONTEXT_MAP_MAX_RLE 16 + +@@ -29,12 +38,31 @@ + #define BROTLI_INITIAL_REPEATED_CODE_LENGTH 8 + + /* "Large Window Brotli" */ ++ ++/** ++ * The theoretical maximum number of distance bits specified for large window ++ * brotli, for 64-bit encoders and decoders. Even when in practice 32-bit ++ * encoders and decoders only support up to 30 max distance bits, the value is ++ * set to 62 because it affects the large window brotli file format. ++ * Specifically, it affects the encoding of simple huffman tree for distances, ++ * see Specification RFC 7932 chapter 3.4. ++ */ + #define BROTLI_LARGE_MAX_DISTANCE_BITS 62U + #define BROTLI_LARGE_MIN_WBITS 10 ++/** ++ * The maximum supported large brotli window bits by the encoder and decoder. ++ * Large window brotli allows up to 62 bits, however the current encoder and ++ * decoder, designed for 32-bit integers, only support up to 30 bits maximum. ++ */ + #define BROTLI_LARGE_MAX_WBITS 30 + + /* Specification: 4. Encoding of distances */ + #define BROTLI_NUM_DISTANCE_SHORT_CODES 16 ++/** ++ * Maximal number of "postfix" bits. ++ * ++ * Number of "postfix" bits is stored as 2 bits in meta-block header. ++ */ + #define BROTLI_MAX_NPOSTFIX 3 + #define BROTLI_MAX_NDIRECT 120 + #define BROTLI_MAX_DISTANCE_BITS 24U +@@ -45,9 +73,22 @@ + #define BROTLI_NUM_DISTANCE_SYMBOLS \ + BROTLI_DISTANCE_ALPHABET_SIZE( \ + BROTLI_MAX_NDIRECT, BROTLI_MAX_NPOSTFIX, BROTLI_LARGE_MAX_DISTANCE_BITS) ++ ++/* ((1 << 26) - 4) is the maximal distance that can be expressed in RFC 7932 ++ brotli stream using NPOSTFIX = 0 and NDIRECT = 0. With other NPOSTFIX and ++ NDIRECT values distances up to ((1 << 29) + 88) could be expressed. */ + #define BROTLI_MAX_DISTANCE 0x3FFFFFC ++ ++/* ((1 << 31) - 4) is the safe distance limit. Using this number as a limit ++ allows safe distance calculation without overflows, given the distance ++ alphabet size is limited to corresponding size ++ (see kLargeWindowDistanceCodeLimits). */ + #define BROTLI_MAX_ALLOWED_DISTANCE 0x7FFFFFFC + ++ ++/* Specification: 4. Encoding of Literal Insertion Lengths and Copy Lengths */ ++#define BROTLI_NUM_INS_COPY_CODES 24 ++ + /* 7.1. Context modes and context ID lookup for literals */ + /* "context IDs for literals are in the range of 0..63" */ + #define BROTLI_LITERAL_CONTEXT_BITS 6 +@@ -61,4 +102,99 @@ + #define BROTLI_WINDOW_GAP 16 + #define BROTLI_MAX_BACKWARD_LIMIT(W) (((size_t)1 << (W)) - BROTLI_WINDOW_GAP) + ++typedef struct BrotliDistanceCodeLimit { ++ uint32_t max_alphabet_size; ++ uint32_t max_distance; ++} BrotliDistanceCodeLimit; ++ ++/* This function calculates maximal size of distance alphabet, such that the ++ distances greater than the given values can not be represented. ++ ++ This limits are designed to support fast and safe 32-bit decoders. ++ "32-bit" means that signed integer values up to ((1 << 31) - 1) could be ++ safely expressed. ++ ++ Brotli distance alphabet symbols do not represent consecutive distance ++ ranges. Each distance alphabet symbol (excluding direct distances and short ++ codes), represent interleaved (for NPOSTFIX > 0) range of distances. ++ A "group" of consecutive (1 << NPOSTFIX) symbols represent non-interleaved ++ range. Two consecutive groups require the same amount of "extra bits". ++ ++ It is important that distance alphabet represents complete "groups". ++ To avoid complex logic on encoder side about interleaved ranges ++ it was decided to restrict both sides to complete distance code "groups". ++ */ ++BROTLI_UNUSED_FUNCTION BrotliDistanceCodeLimit BrotliCalculateDistanceCodeLimit( ++ uint32_t max_distance, uint32_t npostfix, uint32_t ndirect) { ++ BrotliDistanceCodeLimit result; ++ /* Marking this function as unused, because not all files ++ including "constants.h" use it -> compiler warns about that. */ ++ BROTLI_UNUSED(&BrotliCalculateDistanceCodeLimit); ++ if (max_distance <= ndirect) { ++ /* This case never happens / exists only for the sake of completeness. */ ++ result.max_alphabet_size = max_distance + BROTLI_NUM_DISTANCE_SHORT_CODES; ++ result.max_distance = max_distance; ++ return result; ++ } else { ++ /* The first prohibited value. */ ++ uint32_t forbidden_distance = max_distance + 1; ++ /* Subtract "directly" encoded region. */ ++ uint32_t offset = forbidden_distance - ndirect - 1; ++ uint32_t ndistbits = 0; ++ uint32_t tmp; ++ uint32_t half; ++ uint32_t group; ++ /* Postfix for the last dcode in the group. */ ++ uint32_t postfix = (1u << npostfix) - 1; ++ uint32_t extra; ++ uint32_t start; ++ /* Remove postfix and "head-start". */ ++ offset = (offset >> npostfix) + 4; ++ /* Calculate the number of distance bits. */ ++ tmp = offset / 2; ++ /* Poor-man's log2floor, to avoid extra dependencies. */ ++ while (tmp != 0) {ndistbits++; tmp = tmp >> 1;} ++ /* One bit is covered with subrange addressing ("half"). */ ++ ndistbits--; ++ /* Find subrange. */ ++ half = (offset >> ndistbits) & 1; ++ /* Calculate the "group" part of dcode. */ ++ group = ((ndistbits - 1) << 1) | half; ++ /* Calculated "group" covers the prohibited distance value. */ ++ if (group == 0) { ++ /* This case is added for correctness; does not occur for limit > 128. */ ++ result.max_alphabet_size = ndirect + BROTLI_NUM_DISTANCE_SHORT_CODES; ++ result.max_distance = ndirect; ++ return result; ++ } ++ /* Decrement "group", so it is the last permitted "group". */ ++ group--; ++ /* After group was decremented, ndistbits and half must be recalculated. */ ++ ndistbits = (group >> 1) + 1; ++ /* The last available distance in the subrange has all extra bits set. */ ++ extra = (1u << ndistbits) - 1; ++ /* Calculate region start. NB: ndistbits >= 1. */ ++ start = (1u << (ndistbits + 1)) - 4; ++ /* Move to subregion. */ ++ start += (group & 1) << ndistbits; ++ /* Calculate the alphabet size. */ ++ result.max_alphabet_size = ((group << npostfix) | postfix) + ndirect + ++ BROTLI_NUM_DISTANCE_SHORT_CODES + 1; ++ /* Calculate the maximal distance representable by alphabet. */ ++ result.max_distance = ((start + extra) << npostfix) + postfix + ndirect + 1; ++ return result; ++ } ++} ++ ++/* Represents the range of values belonging to a prefix code: ++ [offset, offset + 2^nbits) */ ++typedef struct { ++ uint16_t offset; ++ uint8_t nbits; ++} BrotliPrefixCodeRange; ++ ++/* "Soft-private", it is exported, but not "advertised" as API. */ ++BROTLI_COMMON_API extern const BrotliPrefixCodeRange ++ _kBrotliPrefixCodeRanges[BROTLI_NUM_BLOCK_LEN_SYMBOLS]; ++ + #endif /* BROTLI_COMMON_CONSTANTS_H_ */ +diff --git a/c/common/platform.h b/c/common/platform.h +index 0d84b19..94bf773 100755 +--- a/c/common/platform.h ++++ b/c/common/platform.h +@@ -197,6 +197,10 @@ OR: + + #endif /* ARMv8 */ + ++#if defined(__ARM_NEON__) || defined(__ARM_NEON) ++#define BROTLI_TARGET_NEON ++#endif ++ + #if defined(__i386) || defined(_M_IX86) + #define BROTLI_TARGET_X86 + #endif +@@ -456,20 +460,20 @@ static BROTLI_INLINE void BROTLI_UNALIGNED_STORE64LE(void* p, uint64_t v) { + #endif + + #if defined(BROTLI_ENABLE_LOG) +-#define BROTLI_DCHECK(x) assert(x) + #define BROTLI_LOG(x) printf x + #else +-#define BROTLI_DCHECK(x) + #define BROTLI_LOG(x) + #endif + + #if defined(BROTLI_DEBUG) || defined(BROTLI_ENABLE_LOG) ++#define BROTLI_DCHECK(x) assert(x) + static BROTLI_INLINE void BrotliDump(const char* f, int l, const char* fn) { + fprintf(stderr, "%s:%d (%s)\n", f, l, fn); + fflush(stderr); + } + #define BROTLI_DUMP() BrotliDump(__FILE__, __LINE__, __FUNCTION__) + #else ++#define BROTLI_DCHECK(x) + #define BROTLI_DUMP() (void)(0) + #endif + +diff --git a/c/dec/bit_reader.c b/c/dec/bit_reader.c +index 722fd90..7f7b256 100644 +--- a/c/dec/bit_reader.c ++++ b/c/dec/bit_reader.c +@@ -15,6 +15,17 @@ + extern "C" { + #endif + ++const uint32_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_ = sizeof(br->val_) << 3; +@@ -43,6 +54,23 @@ BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br) { + return BROTLI_TRUE; + } + ++BROTLI_BOOL BrotliSafeReadBits32Slow(BrotliBitReader* const br, ++ uint32_t n_bits, uint32_t* val) { ++ uint32_t low_val; ++ uint32_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/c/dec/bit_reader.h b/c/dec/bit_reader.h +index c06e914..22bc060 100644 +--- a/c/dec/bit_reader.h ++++ b/c/dec/bit_reader.h +@@ -11,6 +11,7 @@ + + #include /* memcpy */ + ++#include "../common/constants.h" + #include "../common/platform.h" + #include + +@@ -20,16 +21,7 @@ extern "C" { + + #define BROTLI_SHORT_FILL_BIT_WINDOW_READ (sizeof(brotli_reg_t) >> 1) + +-static const uint32_t kBitMask[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 +-}; ++BROTLI_INTERNAL extern const uint32_t kBrotliBitMask[33]; + + static BROTLI_INLINE uint32_t BitMask(uint32_t n) { + if (BROTLI_IS_CONSTANT(n) || BROTLI_HAS_UBFX) { +@@ -37,7 +29,7 @@ static BROTLI_INLINE uint32_t BitMask(uint32_t n) { + "Unsigned Bit Field Extract" UBFX instruction on ARM. */ + return ~((0xFFFFFFFFu) << n); + } else { +- return kBitMask[n]; ++ return kBrotliBitMask[n]; + } + } + +@@ -65,6 +57,12 @@ BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br); + reading. */ + BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const 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* const br, uint32_t n_bits, uint32_t* val); ++ + static BROTLI_INLINE void BrotliBitReaderSaveState( + BrotliBitReader* const from, BrotliBitReaderState* to) { + to->val_ = from->val_; +@@ -87,8 +85,11 @@ static BROTLI_INLINE uint32_t BrotliGetAvailableBits( + } + + /* Returns amount of unread bytes the bit reader still has buffered from the +- BrotliInput, including whole bytes in br->val_. */ ++ 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; ++ if (br->avail_in > kCap) return kCap; + return br->avail_in + (BrotliGetAvailableBits(br) >> 3); + } + +@@ -237,15 +238,17 @@ static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) { + static BROTLI_INLINE void BrotliTakeBits( + BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { + *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); +- BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n", ++ BROTLI_LOG(("[BrotliTakeBits] %d %d %d val: %6x\n", + (int)br->avail_in, (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. */ +-static BROTLI_INLINE uint32_t BrotliReadBits( ++ Assumes that there is enough input to perform BrotliFillBitWindow. ++ Up to 24 bits are allowed to be requested from this method. */ ++static BROTLI_INLINE uint32_t BrotliReadBits24( + BrotliBitReader* const br, uint32_t n_bits) { ++ BROTLI_DCHECK(n_bits <= 24); + if (BROTLI_64_BITS || (n_bits <= 16)) { + uint32_t val; + BrotliFillBitWindow(br, n_bits); +@@ -262,10 +265,32 @@ static BROTLI_INLINE uint32_t BrotliReadBits( + } + } + ++/* Same as BrotliReadBits24, but allows reading up to 32 bits. */ ++static BROTLI_INLINE uint32_t BrotliReadBits32( ++ BrotliBitReader* const br, uint32_t n_bits) { ++ BROTLI_DCHECK(n_bits <= 32); ++ if (BROTLI_64_BITS || (n_bits <= 16)) { ++ uint32_t val; ++ BrotliFillBitWindow(br, n_bits); ++ BrotliTakeBits(br, n_bits, &val); ++ return val; ++ } else { ++ uint32_t low_val; ++ uint32_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. */ ++ 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, uint32_t n_bits, uint32_t* val) { ++ BROTLI_DCHECK(n_bits <= 24); + while (BrotliGetAvailableBits(br) < n_bits) { + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; +@@ -275,6 +300,23 @@ static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits( + return BROTLI_TRUE; + } + ++/* Same as BrotliSafeReadBits, but allows reading up to 32 bits. */ ++static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits32( ++ BrotliBitReader* const br, uint32_t n_bits, uint32_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) { +diff --git a/c/dec/decode.c b/c/dec/decode.c +index 674b829..ae5a3d3 100644 +--- a/c/dec/decode.c ++++ b/c/dec/decode.c +@@ -6,10 +6,6 @@ + + #include + +-#if defined(__ARM_NEON__) +-#include +-#endif +- + #include /* free, malloc */ + #include /* memcpy, memset */ + +@@ -24,6 +20,10 @@ + #include "./prefix.h" + #include "./state.h" + ++#if defined(BROTLI_TARGET_NEON) ++#include ++#endif ++ + #if defined(__cplusplus) || defined(c_plusplus) + extern "C" { + #endif +@@ -41,7 +41,8 @@ extern "C" { + + /* We need the slack region for the following reasons: + - doing up to two 16-byte copies for fast backward copying +- - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */ ++ - inserting transformed dictionary word: ++ 5 prefix + 24 base + 8 suffix */ + static const uint32_t kRingBufferWriteAheadSlack = 42; + + static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = { +@@ -167,7 +168,7 @@ static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s, + } + + static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) { +-#if defined(__ARM_NEON__) ++#if defined(BROTLI_TARGET_NEON) + vst1q_u8(dst, vld1q_u8(src)); + #else + uint32_t buffer[4]; +@@ -274,7 +275,8 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( + s->loop_counter = i; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } +- if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) { ++ 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)); +@@ -323,7 +325,8 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( + s->loop_counter = i; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } +- if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) { ++ if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 1 && ++ bits == 0) { + return BROTLI_FAILURE( + BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE); + } +@@ -347,15 +350,17 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( + static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, + const HuffmanCode* table, + BrotliBitReader* br) { +- table += bits & HUFFMAN_TABLE_MASK; +- if (table->bits > HUFFMAN_TABLE_BITS) { +- uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS; ++ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); ++ BROTLI_HC_ADJUST_TABLE_INDEX(table, bits & HUFFMAN_TABLE_MASK); ++ if (BROTLI_HC_FAST_LOAD_BITS(table) > HUFFMAN_TABLE_BITS) { ++ uint32_t nbits = BROTLI_HC_FAST_LOAD_BITS(table) - HUFFMAN_TABLE_BITS; + BrotliDropBits(br, HUFFMAN_TABLE_BITS); +- table += table->value; +- table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits); ++ BROTLI_HC_ADJUST_TABLE_INDEX(table, ++ BROTLI_HC_FAST_LOAD_VALUE(table) + ++ ((bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits))); + } +- BrotliDropBits(br, table->bits); +- return table->value; ++ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table)); ++ return BROTLI_HC_FAST_LOAD_VALUE(table); + } + + /* Reads and decodes the next Huffman code from bit-stream. +@@ -371,19 +376,20 @@ static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol( + const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { + uint32_t val; + uint32_t available_bits = BrotliGetAvailableBits(br); ++ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); + if (available_bits == 0) { +- if (table->bits == 0) { +- *result = table->value; ++ 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 = (uint32_t)BrotliGetBitsUnmasked(br); +- table += val & HUFFMAN_TABLE_MASK; +- if (table->bits <= HUFFMAN_TABLE_BITS) { +- if (table->bits <= available_bits) { +- BrotliDropBits(br, table->bits); +- *result = table->value; ++ 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. */ +@@ -394,15 +400,15 @@ static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol( + } + + /* Speculatively drop HUFFMAN_TABLE_BITS. */ +- val = (val & BitMask(table->bits)) >> HUFFMAN_TABLE_BITS; ++ val = (val & BitMask(BROTLI_HC_FAST_LOAD_BITS(table))) >> HUFFMAN_TABLE_BITS; + available_bits -= HUFFMAN_TABLE_BITS; +- table += table->value + val; +- if (available_bits < table->bits) { ++ BROTLI_HC_ADJUST_TABLE_INDEX(table, BROTLI_HC_FAST_LOAD_VALUE(table) + val); ++ if (available_bits < BROTLI_HC_FAST_LOAD_BITS(table)) { + return BROTLI_FALSE; /* Not enough bits for the second level. */ + } + +- BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits); +- *result = table->value; ++ BrotliDropBits(br, HUFFMAN_TABLE_BITS + BROTLI_HC_FAST_LOAD_BITS(table)); ++ *result = BROTLI_HC_FAST_LOAD_VALUE(table); + return BROTLI_TRUE; + } + +@@ -425,9 +431,10 @@ static BROTLI_INLINE void PreloadSymbol(int safe, + if (safe) { + return; + } +- table += BrotliGetBits(br, HUFFMAN_TABLE_BITS); +- *bits = table->bits; +- *value = table->value; ++ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table); ++ BROTLI_HC_ADJUST_TABLE_INDEX(table, BrotliGetBits(br, HUFFMAN_TABLE_BITS)); ++ *bits = BROTLI_HC_FAST_LOAD_BITS(table); ++ *value = BROTLI_HC_FAST_LOAD_VALUE(table); + } + + /* Decodes the next Huffman code using data prepared by PreloadSymbol. +@@ -441,10 +448,11 @@ static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table, + uint32_t val = BrotliGet16BitsUnmasked(br); + const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value; + uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS)); ++ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(ext); + BrotliDropBits(br, HUFFMAN_TABLE_BITS); +- ext += (val >> HUFFMAN_TABLE_BITS) & mask; +- BrotliDropBits(br, ext->bits); +- result = ext->value; ++ BROTLI_HC_ADJUST_TABLE_INDEX(ext, (val >> HUFFMAN_TABLE_BITS) & mask); ++ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(ext)); ++ result = BROTLI_HC_FAST_LOAD_VALUE(ext); + } else { + BrotliDropBits(br, *bits); + } +@@ -465,32 +473,34 @@ static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { + Totally 1..4 symbols are read, 1..11 bits each. + The list of symbols MUST NOT contain duplicates. */ + static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols( +- uint32_t alphabet_size, uint32_t max_symbol, BrotliDecoderState* s) { ++ uint32_t alphabet_size_max, uint32_t alphabet_size_limit, ++ BrotliDecoderState* s) { + /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */ + BrotliBitReader* br = &s->br; +- uint32_t max_bits = Log2Floor(alphabet_size - 1); +- uint32_t i = s->sub_loop_counter; +- uint32_t num_symbols = s->symbol; ++ BrotliMetablockHeaderArena* h = &s->arena.header; ++ uint32_t max_bits = Log2Floor(alphabet_size_max - 1); ++ uint32_t i = h->sub_loop_counter; ++ uint32_t num_symbols = h->symbol; + while (i <= num_symbols) { + uint32_t v; + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) { +- s->sub_loop_counter = i; +- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; ++ h->sub_loop_counter = i; ++ h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } +- if (v >= max_symbol) { ++ if (v >= alphabet_size_limit) { + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET); + } +- s->symbols_lists_array[i] = (uint16_t)v; +- BROTLI_LOG_UINT(s->symbols_lists_array[i]); ++ h->symbols_lists_array[i] = (uint16_t)v; ++ BROTLI_LOG_UINT(h->symbols_lists_array[i]); + ++i; + } + + for (i = 0; i < num_symbols; ++i) { + uint32_t k = i + 1; + for (; k <= num_symbols; ++k) { +- if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) { ++ if (h->symbols_lists_array[i] == h->symbols_lists_array[k]) { + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME); + } + } +@@ -583,33 +593,35 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len, + static BrotliDecoderErrorCode ReadSymbolCodeLengths( + uint32_t alphabet_size, BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; +- uint32_t symbol = s->symbol; +- uint32_t repeat = s->repeat; +- uint32_t space = s->space; +- uint32_t prev_code_len = s->prev_code_len; +- uint32_t repeat_code_len = s->repeat_code_len; +- uint16_t* symbol_lists = s->symbol_lists; +- uint16_t* code_length_histo = s->code_length_histo; +- int* next_symbol = s->next_symbol; ++ BrotliMetablockHeaderArena* h = &s->arena.header; ++ uint32_t symbol = h->symbol; ++ uint32_t repeat = h->repeat; ++ uint32_t space = h->space; ++ uint32_t prev_code_len = h->prev_code_len; ++ uint32_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 = s->table; ++ const HuffmanCode* p = h->table; + uint32_t code_len; ++ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p); + if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) { +- s->symbol = symbol; +- s->repeat = repeat; +- s->prev_code_len = prev_code_len; +- s->repeat_code_len = repeat_code_len; +- s->space = space; ++ 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); +- p += BrotliGetBitsUnmasked(br) & +- BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH); +- BrotliDropBits(br, p->bits); /* Use 1..5 bits. */ +- code_len = p->value; /* code_len == 0..17 */ ++ 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); +@@ -624,48 +636,52 @@ static BrotliDecoderErrorCode ReadSymbolCodeLengths( + symbol_lists, code_length_histo, next_symbol); + } + } +- s->space = space; ++ h->space = space; + return BROTLI_DECODER_SUCCESS; + } + + static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( + uint32_t alphabet_size, BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; ++ BrotliMetablockHeaderArena* h = &s->arena.header; + BROTLI_BOOL get_byte = BROTLI_FALSE; +- while (s->symbol < alphabet_size && s->space > 0) { +- const HuffmanCode* p = s->table; ++ while (h->symbol < alphabet_size && h->space > 0) { ++ const HuffmanCode* p = h->table; + uint32_t code_len; + uint32_t available_bits; + uint32_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); + } +- p += bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH); +- if (p->bits > available_bits) { ++ BROTLI_HC_ADJUST_TABLE_INDEX(p, ++ bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH)); ++ if (BROTLI_HC_FAST_LOAD_BITS(p) > available_bits) { + get_byte = BROTLI_TRUE; + continue; + } +- code_len = p->value; /* code_len == 0..17 */ ++ code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */ + if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { +- BrotliDropBits(br, p->bits); +- ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space, +- &s->prev_code_len, s->symbol_lists, s->code_length_histo, +- s->next_symbol); ++ 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 */ + uint32_t extra_bits = code_len - 14U; +- uint32_t repeat_delta = (bits >> p->bits) & BitMask(extra_bits); +- if (available_bits < p->bits + extra_bits) { ++ uint32_t repeat_delta = (bits >> BROTLI_HC_FAST_LOAD_BITS(p)) & ++ BitMask(extra_bits); ++ if (available_bits < BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits) { + get_byte = BROTLI_TRUE; + continue; + } +- BrotliDropBits(br, p->bits + extra_bits); ++ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits); + ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, +- &s->symbol, &s->repeat, &s->space, &s->prev_code_len, +- &s->repeat_code_len, s->symbol_lists, s->code_length_histo, +- s->next_symbol); ++ &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; +@@ -675,9 +691,10 @@ static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( + Each code is 2..4 bits long. In total 30..72 bits are used. */ + static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; +- uint32_t num_codes = s->repeat; +- unsigned space = s->space; +- uint32_t i = s->sub_loop_counter; ++ BrotliMetablockHeaderArena* h = &s->arena.header; ++ uint32_t num_codes = h->repeat; ++ unsigned space = h->space; ++ uint32_t i = h->sub_loop_counter; + for (; i < BROTLI_CODE_LENGTH_CODES; ++i) { + const uint8_t code_len_idx = kCodeLengthCodeOrder[i]; + uint32_t ix; +@@ -690,21 +707,21 @@ static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) { + ix = 0; + } + if (kCodeLengthPrefixLength[ix] > available_bits) { +- s->sub_loop_counter = i; +- s->repeat = num_codes; +- s->space = space; +- s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; ++ 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]); +- s->code_length_code_lengths[code_len_idx] = (uint8_t)v; +- BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx); ++ 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; +- ++s->code_length_histo[v]; ++ ++h->code_length_histo[v]; + if (space - 1U >= 32U) { + /* space is 0 or wrapped around. */ + break; +@@ -728,49 +745,48 @@ static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) { + 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(uint32_t alphabet_size, +- uint32_t max_symbol, ++static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size_max, ++ uint32_t alphabet_size_limit, + HuffmanCode* table, + uint32_t* opt_table_size, + BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; +- /* Unnecessary masking, but might be good for safety. */ +- alphabet_size &= 0x7FF; ++ BrotliMetablockHeaderArena* h = &s->arena.header; + /* State machine. */ + for (;;) { +- switch (s->substate_huffman) { ++ switch (h->substate_huffman) { + case BROTLI_STATE_HUFFMAN_NONE: +- if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) { ++ if (!BrotliSafeReadBits(br, 2, &h->sub_loop_counter)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } +- BROTLI_LOG_UINT(s->sub_loop_counter); ++ 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 (s->sub_loop_counter != 1) { +- s->space = 32; +- s->repeat = 0; /* num_codes */ +- memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) * ++ 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(&s->code_length_code_lengths[0], 0, +- sizeof(s->code_length_code_lengths)); +- s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; ++ 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, &s->symbol)) { /* num_symbols */ +- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; ++ if (!BrotliSafeReadBits(br, 2, &h->symbol)) { /* num_symbols */ ++ h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } +- s->sub_loop_counter = 0; ++ h->sub_loop_counter = 0; + /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { + BrotliDecoderErrorCode result = +- ReadSimpleHuffmanSymbols(alphabet_size, max_symbol, s); ++ ReadSimpleHuffmanSymbols(alphabet_size_max, alphabet_size_limit, s); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } +@@ -779,21 +795,21 @@ static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size, + + case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: { + uint32_t table_size; +- if (s->symbol == 3) { ++ if (h->symbol == 3) { + uint32_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { +- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; ++ h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } +- s->symbol += bits; ++ h->symbol += bits; + } +- BROTLI_LOG_UINT(s->symbol); ++ BROTLI_LOG_UINT(h->symbol); + table_size = BrotliBuildSimpleHuffmanTable( +- table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol); ++ table, HUFFMAN_TABLE_BITS, h->symbols_lists_array, h->symbol); + if (opt_table_size) { + *opt_table_size = table_size; + } +- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; ++ h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; + } + +@@ -804,44 +820,45 @@ static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size, + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } +- BrotliBuildCodeLengthsHuffmanTable(s->table, +- s->code_length_code_lengths, +- s->code_length_histo); +- memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo)); ++ 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) { +- s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); +- s->symbol_lists[s->next_symbol[i]] = 0xFFFF; ++ h->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); ++ h->symbol_lists[h->next_symbol[i]] = 0xFFFF; + } + +- s->symbol = 0; +- s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH; +- s->repeat = 0; +- s->repeat_code_len = 0; +- s->space = 32768; +- s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; ++ 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: { + uint32_t table_size; +- BrotliDecoderErrorCode result = ReadSymbolCodeLengths(max_symbol, s); ++ BrotliDecoderErrorCode result = ReadSymbolCodeLengths( ++ alphabet_size_limit, s); + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { +- result = SafeReadSymbolCodeLengths(max_symbol, s); ++ result = SafeReadSymbolCodeLengths(alphabet_size_limit, s); + } + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + +- if (s->space != 0) { +- BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)s->space)); ++ 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, s->symbol_lists, s->code_length_histo); ++ table, HUFFMAN_TABLE_BITS, h->symbol_lists, h->code_length_histo); + if (opt_table_size) { + *opt_table_size = table_size; + } +- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; ++ h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; + } + +@@ -858,8 +875,8 @@ static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table, + uint32_t code; + uint32_t nbits; + code = ReadSymbol(table, br); +- nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */ +- return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits); ++ 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 +@@ -877,13 +894,14 @@ static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( + } + { + uint32_t bits; +- uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */ ++ uint32_t nbits = _kBrotliPrefixCodeRanges[index].nbits; ++ uint32_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 = kBlockLengthPrefixCode[index].offset + bits; ++ *result = offset + bits; + s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; + return BROTLI_TRUE; + } +@@ -943,22 +961,22 @@ static BROTLI_NOINLINE void InverseMoveToFrontTransform( + /* Decodes a series of Huffman table using ReadHuffmanCode function. */ + static BrotliDecoderErrorCode HuffmanTreeGroupDecode( + HuffmanTreeGroup* group, BrotliDecoderState* s) { +- if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) { +- s->next = group->codes; +- s->htree_index = 0; +- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP; ++ 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 (s->htree_index < group->num_htrees) { ++ while (h->htree_index < group->num_htrees) { + uint32_t table_size; +- BrotliDecoderErrorCode result = +- ReadHuffmanCode(group->alphabet_size, group->max_symbol, +- s->next, &table_size, s); ++ 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[s->htree_index] = s->next; +- s->next += table_size; +- ++s->htree_index; ++ group->htrees[h->htree_index] = h->next; ++ h->next += table_size; ++ ++h->htree_index; + } +- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; ++ h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; + return BROTLI_DECODER_SUCCESS; + } + +@@ -976,15 +994,16 @@ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, + BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; ++ BrotliMetablockHeaderArena* h = &s->arena.header; + +- switch ((int)s->substate_context_map) { ++ 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)++; +- s->context_index = 0; ++ h->context_index = 0; + BROTLI_LOG_UINT(context_map_size); + BROTLI_LOG_UINT(*num_htrees); + *context_map_arg = +@@ -996,7 +1015,7 @@ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, + memset(*context_map_arg, 0, (size_t)context_map_size); + return BROTLI_DECODER_SUCCESS; + } +- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; ++ h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: { +@@ -1007,38 +1026,38 @@ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if ((bits & 1) != 0) { /* Use RLE for zeros. */ +- s->max_run_length_prefix = (bits >> 1) + 1; ++ h->max_run_length_prefix = (bits >> 1) + 1; + BrotliDropBits(br, 5); + } else { +- s->max_run_length_prefix = 0; ++ h->max_run_length_prefix = 0; + BrotliDropBits(br, 1); + } +- BROTLI_LOG_UINT(s->max_run_length_prefix); +- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN; ++ 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: { +- uint32_t alphabet_size = *num_htrees + s->max_run_length_prefix; ++ uint32_t alphabet_size = *num_htrees + h->max_run_length_prefix; + result = ReadHuffmanCode(alphabet_size, alphabet_size, +- s->context_map_table, NULL, s); ++ h->context_map_table, NULL, s); + if (result != BROTLI_DECODER_SUCCESS) return result; +- s->code = 0xFFFF; +- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE; ++ h->code = 0xFFFF; ++ h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE; + } + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_DECODE: { +- uint32_t context_index = s->context_index; +- uint32_t max_run_length_prefix = s->max_run_length_prefix; ++ uint32_t context_index = h->context_index; ++ uint32_t max_run_length_prefix = h->max_run_length_prefix; + uint8_t* context_map = *context_map_arg; +- uint32_t code = s->code; ++ uint32_t code = h->code; + BROTLI_BOOL skip_preamble = (code != 0xFFFF); + while (context_index < context_map_size || skip_preamble) { + if (!skip_preamble) { +- if (!SafeReadSymbol(s->context_map_table, br, &code)) { +- s->code = 0xFFFF; +- s->context_index = context_index; ++ 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); +@@ -1059,8 +1078,8 @@ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, + { + uint32_t reps; + if (!BrotliSafeReadBits(br, code, &reps)) { +- s->code = code; +- s->context_index = context_index; ++ h->code = code; ++ h->context_index = context_index; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + reps += 1U << code; +@@ -1080,13 +1099,13 @@ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, + case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: { + uint32_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { +- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM; ++ 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); + } +- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; ++ h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; + return BROTLI_DECODER_SUCCESS; + } + +@@ -1448,32 +1467,28 @@ static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) { + } + + static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) { +- if (s->distance_code == 0) { +- --s->dist_rb_idx; +- s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; ++ 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_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 distance_code = s->distance_code << 1; +- /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: +- 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */ +- const uint32_t kDistanceShortCodeIndexOffset = 0xAAAFFF1B; +- /* kDistanceShortCodeValueOffset has 2-bit values from LSB: +- -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */ +- const uint32_t kDistanceShortCodeValueOffset = 0xFA5FA500; +- int v = (s->dist_rb_idx + +- (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3; +- s->distance_code = s->dist_rb[v]; +- v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3; +- if ((distance_code & 0x3) != 0) { +- s->distance_code += v; ++ int index_delta = 3; ++ int delta; ++ int base = s->distance_code - 10; ++ if (s->distance_code < 10) { ++ base = s->distance_code - 4; + } else { +- s->distance_code -= v; +- if (s->distance_code <= 0) { +- /* A huge distance will cause a BROTLI_FAILURE() soon. +- This is a little faster than failing here. */ +- s->distance_code = 0x7FFFFFFF; +- } ++ 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; + } + } + } +@@ -1488,62 +1503,153 @@ static BROTLI_INLINE BROTLI_BOOL SafeReadBits( + } + } + ++static BROTLI_INLINE BROTLI_BOOL SafeReadBits32( ++ BrotliBitReader* const br, uint32_t n_bits, uint32_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; ++ uint32_t npostfix = s->distance_postfix_bits; ++ uint32_t ndirect = s->num_direct_distance_codes; ++ uint32_t alphabet_size_limit = s->distance_hgroup.alphabet_size_limit; ++ uint32_t postfix = 1u << npostfix; ++ uint32_t j; ++ uint32_t bits = 1; ++ uint32_t half = 0; ++ ++ /* Skip short codes. */ ++ uint32_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) { ++ uint32_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) { +- int distval; ++ BrotliMetablockBodyArena* b = &s->arena.body; ++ uint32_t code; ++ uint32_t bits; + BrotliBitReaderState memento; + HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; + if (!safe) { +- s->distance_code = (int)ReadSymbol(distance_tree, br); ++ code = ReadSymbol(distance_tree, br); + } else { +- uint32_t code; + BrotliBitReaderSaveState(br, &memento); + if (!SafeReadSymbol(distance_tree, br, &code)) { + return BROTLI_FALSE; + } +- s->distance_code = (int)code; + } ++ --s->block_length[2]; + /* Convert the distance code to the actual distance by possibly +- looking up past distances from the s->ringbuffer. */ ++ looking up past distances from the s->dist_rb. */ + s->distance_context = 0; +- if ((s->distance_code & ~0xF) == 0) { ++ if ((code & ~0xFu) == 0) { ++ s->distance_code = (int)code; + TakeDistanceFromRingBuffer(s); +- --s->block_length[2]; + return BROTLI_TRUE; + } +- distval = s->distance_code - (int)s->num_direct_distance_codes; +- if (distval >= 0) { +- uint32_t nbits; +- int postfix; +- int offset; +- if (!safe && (s->distance_postfix_bits == 0)) { +- nbits = ((uint32_t)distval >> 1) + 1; +- offset = ((2 + (distval & 1)) << nbits) - 4; +- s->distance_code = (int)s->num_direct_distance_codes + offset + +- (int)BrotliReadBits(br, nbits); +- } else { +- /* This branch also works well when s->distance_postfix_bits == 0. */ +- uint32_t bits; +- postfix = distval & s->distance_postfix_mask; +- distval >>= s->distance_postfix_bits; +- nbits = ((uint32_t)distval >> 1) + 1; +- if (safe) { +- if (!SafeReadBits(br, nbits, &bits)) { +- s->distance_code = -1; /* Restore precondition. */ +- BrotliBitReaderRestoreState(br, &memento); +- return BROTLI_FALSE; +- } +- } else { +- bits = BrotliReadBits(br, nbits); +- } +- offset = ((2 + (distval & 1)) << nbits) - 4; +- s->distance_code = (int)s->num_direct_distance_codes + +- ((offset + (int)bits) << s->distance_postfix_bits) + postfix; ++ 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 = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1; +- --s->block_length[2]; ++ s->distance_code = ++ (int)(b->dist_offset[code] + (bits << s->distance_postfix_bits)); + return BROTLI_TRUE; + } + +@@ -1579,9 +1685,9 @@ static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal( + *insert_length = v.insert_len_offset; + if (!safe) { + if (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) { +- insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits); ++ insert_len_extra = BrotliReadBits24(br, v.insert_len_extra_bits); + } +- copy_length = BrotliReadBits(br, v.copy_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)) { +@@ -1926,21 +2032,6 @@ static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands( + return ProcessCommandsInternal(1, s); + } + +-/* Returns the maximum number of distance symbols which can only represent +- distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */ +-static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect, uint32_t npostfix) { +- static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28}; +- static const uint32_t diff[BROTLI_MAX_NPOSTFIX + 1] = {73, 126, 228, 424}; +- uint32_t postfix = 1U << npostfix; +- if (ndirect < bound[npostfix]) { +- return ndirect + diff[npostfix] + postfix; +- } else if (ndirect > bound[npostfix] + postfix) { +- return ndirect + diff[npostfix]; +- } else { +- return bound[npostfix] + diff[npostfix] + postfix; +- } +-} +- + BrotliDecoderResult BrotliDecoderDecompress( + size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size, + uint8_t* decoded_buffer) { +@@ -2158,33 +2249,23 @@ BrotliDecoderResult BrotliDecoderDecompressStream( + 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; +- 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: +- for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) { +- uint32_t bits; +- /* Read one byte and ignore it. */ +- if (!BrotliSafeReadBits(br, 8, &bits)) { +- result = BROTLI_DECODER_NEEDS_MORE_INPUT; +- break; +- } +- } +- if (result == BROTLI_DECODER_SUCCESS) { +- s->state = BROTLI_STATE_METABLOCK_DONE; +- } +- break; ++ /* Fall through. */ + + case BROTLI_STATE_HUFFMAN_CODE_0: + if (s->loop_counter >= 3) { +@@ -2238,6 +2319,30 @@ BrotliDecoderResult BrotliDecoderDecompressStream( + 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: ++ for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) { ++ uint32_t bits; ++ /* Read one byte and ignore it. */ ++ if (!BrotliSafeReadBits(br, 8, &bits)) { ++ result = BROTLI_DECODER_NEEDS_MORE_INPUT; ++ break; ++ } ++ } ++ if (result == BROTLI_DECODER_SUCCESS) { ++ s->state = BROTLI_STATE_METABLOCK_DONE; ++ } ++ break; ++ + case BROTLI_STATE_METABLOCK_HEADER_2: { + uint32_t bits; + if (!BrotliSafeReadBits(br, 6, &bits)) { +@@ -2246,11 +2351,9 @@ BrotliDecoderResult BrotliDecoderDecompressStream( + } + s->distance_postfix_bits = bits & BitMask(2); + bits >>= 2; +- s->num_direct_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES + +- (bits << s->distance_postfix_bits); ++ 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->distance_postfix_mask = (int)BitMask(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) { +@@ -2282,17 +2385,19 @@ BrotliDecoderResult BrotliDecoderDecompressStream( + /* Fall through. */ + + case BROTLI_STATE_CONTEXT_MAP_2: { +- uint32_t num_direct_codes = +- s->num_direct_distance_codes - BROTLI_NUM_DISTANCE_SHORT_CODES; +- uint32_t num_distance_codes = BROTLI_DISTANCE_ALPHABET_SIZE( +- s->distance_postfix_bits, num_direct_codes, +- (s->large_window ? BROTLI_LARGE_MAX_DISTANCE_BITS : +- BROTLI_MAX_DISTANCE_BITS)); +- uint32_t max_distance_symbol = (s->large_window ? +- BrotliMaxDistanceSymbol( +- num_direct_codes, s->distance_postfix_bits) : +- num_distance_codes); ++ uint32_t npostfix = s->distance_postfix_bits; ++ uint32_t ndirect = s->num_direct_distance_codes; ++ uint32_t distance_alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE( ++ npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS); ++ uint32_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, npostfix, 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); +@@ -2306,8 +2411,8 @@ BrotliDecoderResult BrotliDecoderDecompressStream( + s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS, + BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]); + allocation_success &= BrotliDecoderHuffmanTreeGroupInit( +- s, &s->distance_hgroup, num_distance_codes, +- max_distance_symbol, s->num_dist_htrees); ++ s, &s->distance_hgroup, distance_alphabet_size_max, ++ distance_alphabet_size_limit, s->num_dist_htrees); + if (!allocation_success) { + return SaveErrorCode(s, + BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS)); +@@ -2329,18 +2434,24 @@ BrotliDecoderResult BrotliDecoderDecompressStream( + result = HuffmanTreeGroupDecode(hgroup, s); + if (result != BROTLI_DECODER_SUCCESS) break; + s->loop_counter++; +- if (s->loop_counter >= 3) { +- PrepareLiteralDecoding(s); +- s->dist_context_map_slice = s->dist_context_map; +- s->htree_command = s->insert_copy_hgroup.htrees[0]; +- if (!BrotliEnsureRingBuffer(s)) { +- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2); +- break; +- } +- s->state = BROTLI_STATE_COMMAND_BEGIN; ++ if (s->loop_counter < 3) { ++ break; + } +- 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. */ +diff --git a/c/dec/huffman.h b/c/dec/huffman.h +index 521ec6e..a8fbc45 100644 +--- a/c/dec/huffman.h ++++ b/c/dec/huffman.h +@@ -18,12 +18,6 @@ extern "C" { + + #define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15 + +-/* Maximum possible Huffman table size for an alphabet size of (index * 32), +- max code length 15 and root table bits 8. */ +-static const uint16_t kMaxHuffmanTableSize[] = { +- 256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822, +- 854, 886, 920, 952, 984, 1016, 1048, 1080, 1112, 1144, 1176, 1208, 1240, 1272, +- 1304, 1336, 1368, 1400, 1432, 1464, 1496, 1528}; + /* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */ + #define BROTLI_HUFFMAN_MAX_SIZE_26 396 + /* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */ +@@ -33,11 +27,66 @@ static const uint16_t kMaxHuffmanTableSize[] = { + + #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); +@@ -45,7 +94,7 @@ BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table, + /* 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_arg); ++ 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, +@@ -55,13 +104,13 @@ 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. */ +-/* max_symbol is needed due to simple codes since log2(alphabet_size) could be +- greater than log2(max_symbol). */ ++/* 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; +- uint16_t max_symbol; ++ uint16_t alphabet_size_max; ++ uint16_t alphabet_size_limit; + uint16_t num_htrees; + } HuffmanTreeGroup; + +diff --git a/c/dec/prefix.h b/c/dec/prefix.h +index 3ea062d..481a2c7 100644 +--- a/c/dec/prefix.h ++++ b/c/dec/prefix.h +@@ -13,24 +13,6 @@ + #include "../common/constants.h" + #include + +-/* Represents the range of values belonging to a prefix code: +- [offset, offset + 2^nbits) */ +-struct PrefixCodeRange { +- uint16_t offset; +- uint8_t nbits; +-}; +- +-static const struct PrefixCodeRange +- kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = { +- { 1, 2}, { 5, 2}, { 9, 2}, { 13, 2}, +- { 17, 3}, { 25, 3}, { 33, 3}, { 41, 3}, +- { 49, 4}, { 65, 4}, { 81, 4}, { 97, 4}, +- { 113, 5}, { 145, 5}, { 177, 5}, { 209, 5}, +- { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8}, +- { 753, 9}, { 1265, 10}, {2289, 11}, {4337, 12}, +- {8433, 13}, {16625, 24} +-}; +- + typedef struct CmdLutElement { + uint8_t insert_len_extra_bits; + uint8_t copy_len_extra_bits; +diff --git a/c/dec/state.c b/c/dec/state.c +index e0b37c2..f847836 100644 +--- a/c/dec/state.c ++++ b/c/dec/state.c +@@ -33,10 +33,7 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, + s->state = BROTLI_STATE_UNINITED; + s->large_window = 0; + s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; +- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; +- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; + s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; +- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; + s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; + +@@ -59,8 +56,6 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, + s->context_map_slice = NULL; + s->dist_context_map_slice = NULL; + +- s->sub_loop_counter = 0; +- + s->literal_hgroup.codes = NULL; + s->literal_hgroup.htrees = NULL; + s->insert_copy_hgroup.codes = NULL; +@@ -84,9 +79,6 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, + s->block_type_trees = NULL; + s->block_len_trees = NULL; + +- /* Make small negative indexes addressable. */ +- s->symbol_lists = &s->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1]; +- + s->mtf_upper_bound = 63; + + s->dictionary = BrotliGetDictionary(); +@@ -142,17 +134,20 @@ void BrotliDecoderStateCleanup(BrotliDecoderState* s) { + } + + BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit(BrotliDecoderState* s, +- HuffmanTreeGroup* group, uint32_t alphabet_size, uint32_t max_symbol, +- uint32_t ntrees) { +- /* Pack two allocations into one */ +- const size_t max_table_size = kMaxHuffmanTableSize[(alphabet_size + 31) >> 5]; ++ HuffmanTreeGroup* group, uint32_t alphabet_size_max, ++ uint32_t alphabet_size_limit, uint32_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 = (uint16_t)alphabet_size; +- group->max_symbol = (uint16_t)max_symbol; ++ 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]); +diff --git a/c/dec/state.h b/c/dec/state.h +index d28b639..54dab69 100644 +--- a/c/dec/state.h ++++ b/c/dec/state.h +@@ -21,6 +21,95 @@ + 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, +@@ -39,6 +128,7 @@ typedef enum { + 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, +@@ -46,6 +136,7 @@ typedef enum { + BROTLI_STATE_CONTEXT_MAP_1, + BROTLI_STATE_CONTEXT_MAP_2, + BROTLI_STATE_TREE_GROUP, ++ BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY, + BROTLI_STATE_DONE + } BrotliRunningState; + +@@ -98,6 +189,50 @@ typedef enum { + BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX + } BrotliRunningReadBlockLengthState; + ++typedef struct BrotliMetablockHeaderArena { ++ BrotliRunningTreeGroupState substate_tree_group; ++ BrotliRunningContextMapState substate_context_map; ++ BrotliRunningHuffmanState substate_huffman; ++ ++ uint32_t sub_loop_counter; ++ ++ uint32_t repeat_code_len; ++ uint32_t prev_code_len; ++ ++ /* For ReadHuffmanCode. */ ++ uint32_t symbol; ++ uint32_t repeat; ++ uint32_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]; ++ ++ /* For HuffmanTreeGroupDecode. */ ++ int htree_index; ++ HuffmanCode* next; ++ ++ /* For DecodeContextMap. */ ++ uint32_t context_index; ++ uint32_t max_run_length_prefix; ++ uint32_t code; ++ HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272]; ++} BrotliMetablockHeaderArena; ++ ++typedef struct BrotliMetablockBodyArena { ++ uint8_t dist_extra_bits[544]; ++ uint32_t dist_offset[544]; ++} BrotliMetablockBodyArena; ++ + struct BrotliDecoderStateStruct { + BrotliRunningState state; + +@@ -110,7 +245,8 @@ struct BrotliDecoderStateStruct { + brotli_free_func free_func; + void* memory_manager_opaque; + +- /* Temporary storage for remaining input. */ ++ /* 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]; +@@ -125,7 +261,6 @@ struct BrotliDecoderStateStruct { + int dist_rb_idx; + int dist_rb[4]; + int error_code; +- uint32_t sub_loop_counter; + uint8_t* ringbuffer; + uint8_t* ringbuffer_end; + HuffmanCode* htree_command; +@@ -153,13 +288,10 @@ struct BrotliDecoderStateStruct { + uint32_t block_type_rb[6]; + uint32_t distance_postfix_bits; + uint32_t num_direct_distance_codes; +- int distance_postfix_mask; + uint32_t num_dist_htrees; + uint8_t* dist_context_map; + HuffmanCode* literal_htree; + uint8_t dist_htree_index; +- uint32_t repeat_code_len; +- uint32_t prev_code_len; + + int copy_length; + int distance_code; +@@ -168,33 +300,6 @@ struct BrotliDecoderStateStruct { + 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 ReadHuffmanCode. */ +- uint32_t symbol; +- uint32_t repeat; +- uint32_t space; +- +- 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]; +- +- /* For HuffmanTreeGroupDecode. */ +- int htree_index; +- HuffmanCode* next; +- +- /* For DecodeContextMap. */ +- uint32_t context_index; +- uint32_t max_run_length_prefix; +- uint32_t code; +- HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272]; +- + /* For InverseMoveToFrontTransform. */ + uint32_t mtf_upper_bound; + uint32_t mtf[64 + 1]; +@@ -203,10 +308,7 @@ struct BrotliDecoderStateStruct { + + /* States inside function calls. */ + BrotliRunningMetablockHeaderState substate_metablock_header; +- BrotliRunningTreeGroupState substate_tree_group; +- BrotliRunningContextMapState substate_context_map; + BrotliRunningUncompressedState substate_uncompressed; +- BrotliRunningHuffmanState substate_huffman; + BrotliRunningDecodeUint8State substate_decode_uint8; + BrotliRunningReadBlockLengthState substate_read_block_length; + +@@ -229,6 +331,11 @@ struct BrotliDecoderStateStruct { + const BrotliTransforms* transforms; + + uint32_t trivial_literal_contexts[8]; /* 256 bits */ ++ ++ union { ++ BrotliMetablockHeaderArena header; ++ BrotliMetablockBodyArena body; ++ } arena; + }; + + typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal; +@@ -241,8 +348,8 @@ BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s); + BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock( + BrotliDecoderState* s); + BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit( +- BrotliDecoderState* s, HuffmanTreeGroup* group, uint32_t alphabet_size, +- uint32_t max_symbol, uint32_t ntrees); ++ BrotliDecoderState* s, HuffmanTreeGroup* group, uint32_t alphabet_size_max, ++ uint32_t alphabet_size_limit, uint32_t ntrees); + + #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L) + +diff --git a/c/enc/brotli_bit_stream.c b/c/enc/brotli_bit_stream.c +index aaf2dad..8e68059 100644 +--- a/c/enc/brotli_bit_stream.c ++++ b/c/enc/brotli_bit_stream.c +@@ -34,33 +34,18 @@ extern "C" { + BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_LARGE_MAX_DISTANCE_BITS) + /* MAX_SIMPLE_DISTANCE_ALPHABET_SIZE == 140 */ + +-/* Represents the range of values belonging to a prefix code: +- [offset, offset + 2^nbits) */ +-typedef struct PrefixCodeRange { +- uint32_t offset; +- uint32_t nbits; +-} PrefixCodeRange; +- +-static const PrefixCodeRange +- kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = { +- { 1, 2}, { 5, 2}, { 9, 2}, {13, 2}, {17, 3}, { 25, 3}, { 33, 3}, +- {41, 3}, {49, 4}, {65, 4}, {81, 4}, {97, 4}, {113, 5}, {145, 5}, +- {177, 5}, { 209, 5}, { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8}, +- {753, 9}, {1265, 10}, {2289, 11}, {4337, 12}, {8433, 13}, {16625, 24} +-}; +- + static BROTLI_INLINE uint32_t BlockLengthPrefixCode(uint32_t len) { + uint32_t code = (len >= 177) ? (len >= 753 ? 20 : 14) : (len >= 41 ? 7 : 0); + while (code < (BROTLI_NUM_BLOCK_LEN_SYMBOLS - 1) && +- len >= kBlockLengthPrefixCode[code + 1].offset) ++code; ++ len >= _kBrotliPrefixCodeRanges[code + 1].offset) ++code; + return code; + } + + static BROTLI_INLINE void GetBlockLengthPrefixCode(uint32_t len, size_t* code, + uint32_t* n_extra, uint32_t* extra) { + *code = BlockLengthPrefixCode(len); +- *n_extra = kBlockLengthPrefixCode[*code].nbits; +- *extra = len - kBlockLengthPrefixCode[*code].offset; ++ *n_extra = _kBrotliPrefixCodeRanges[*code].nbits; ++ *extra = len - _kBrotliPrefixCodeRanges[*code].offset; + } + + typedef struct BlockTypeCodeCalculator { +diff --git a/research/brotli_decoder.c b/research/brotli_decoder.c +index b1d556d..4b0bc4a 100644 +--- a/research/brotli_decoder.c ++++ b/research/brotli_decoder.c +@@ -38,6 +38,7 @@ void cleanup(Context* ctx) { + + void fail(Context* ctx, const char* message) { + fprintf(stderr, "%s\n", message); ++ cleanup(ctx); + exit(1); + } + +diff --git a/scripts/sources.lst b/scripts/sources.lst +index 5e8e817..cd0b343 100644 +--- a/scripts/sources.lst ++++ b/scripts/sources.lst +@@ -5,6 +5,7 @@ BROTLI_CLI_C = \ + c/tools/brotli.c + + BROTLI_COMMON_C = \ ++ c/common/constants.c \ + c/common/dictionary.c \ + c/common/transform.c + +diff --git a/setup.py b/setup.py +index 1491db3..7bd6314 100644 +--- a/setup.py ++++ b/setup.py +@@ -181,6 +181,7 @@ EXT_MODULES = [ + '_brotli', + sources=[ + 'python/_brotli.cc', ++ 'c/common/constants.c', + 'c/common/dictionary.c', + 'c/common/transform.c', + 'c/dec/bit_reader.c', +-- +2.25.4 + diff --git a/SPECS/brotli.spec b/SPECS/brotli.spec index d86929c..e201b9c 100644 --- a/SPECS/brotli.spec +++ b/SPECS/brotli.spec @@ -7,13 +7,15 @@ Name: brotli Version: 1.0.6 -Release: 2%{?dist} +Release: 3%{?dist} Summary: Lossless compression algorithm License: MIT URL: https://github.com/google/brotli Source0: https://github.com/google/brotli/archive/v%{version}.tar.gz +Patch1: rhbz1881156.patch + %if %{with python2} BuildRequires: python2-devel %endif @@ -69,13 +71,14 @@ It is similar in speed with deflate but offers more dense compression. This package installs the development files %prep -%autosetup +%autosetup -p1 -S git # fix permissions for -debuginfo # rpmlint will complain if I create an extra %%files section for # -debuginfo for this so we'll put it here instead %{__chmod} 644 c/enc/*.[ch] %{__chmod} 644 c/include/brotli/*.h %{__chmod} 644 c/tools/brotli.c + %build mkdir -p build @@ -148,6 +151,9 @@ cd .. %changelog +* Thu Oct 01 2020 Eike Rathke - 1.0.6-3 +- Resolves: CVE-2020-8927 + * Wed Jun 17 2020 Eike Rathke - 1.0.6-2 - Resolves: rhbz#1737412 bump NRV for build to compose