diff options
author | asaitgalin <asaitgalin@yandex-team.ru> | 2022-02-10 16:47:28 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:28 +0300 |
commit | cb85b6b6ed9608dfa24ee0362fd286dd27fd40ae (patch) | |
tree | 9814fbd1c3effac9b8377c5d604b367b14e2db55 /contrib/libs/brotli/dec | |
parent | c0780d05ad256f75dc8e0fa36aee5dbce402e8f6 (diff) | |
download | ydb-cb85b6b6ed9608dfa24ee0362fd286dd27fd40ae.tar.gz |
Restoring authorship annotation for <asaitgalin@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/brotli/dec')
-rw-r--r-- | contrib/libs/brotli/dec/bit_reader.c | 50 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/bit_reader.h | 326 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/decode.c | 3304 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/huffman.c | 236 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/huffman.h | 46 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/prefix.h | 20 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/state.c | 110 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/state.h | 160 | ||||
-rw-r--r-- | contrib/libs/brotli/dec/ya.make | 10 |
9 files changed, 2131 insertions, 2131 deletions
diff --git a/contrib/libs/brotli/dec/bit_reader.c b/contrib/libs/brotli/dec/bit_reader.c index 805684aefc..722fd906dd 100644 --- a/contrib/libs/brotli/dec/bit_reader.c +++ b/contrib/libs/brotli/dec/bit_reader.c @@ -1,48 +1,48 @@ /* Copyright 2013 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + 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 "./bit_reader.h" #include "../common/platform.h" -#include <brotli/types.h> +#include <brotli/types.h> #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif -void BrotliInitBitReader(BrotliBitReader* const br) { +void BrotliInitBitReader(BrotliBitReader* const br) { br->val_ = 0; br->bit_pos_ = sizeof(br->val_) << 3; } -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_ALIGNED_READ) { - aligned_read_mask = 0; - } - if (BrotliGetAvailableBits(br) == 0) { - if (!BrotliPullByte(br)) { - return BROTLI_FALSE; +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_ALIGNED_READ) { + aligned_read_mask = 0; + } + if (BrotliGetAvailableBits(br) == 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; } } - - 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; + return BROTLI_TRUE; } #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif diff --git a/contrib/libs/brotli/dec/bit_reader.h b/contrib/libs/brotli/dec/bit_reader.h index 33bd0ee275..c06e91419f 100644 --- a/contrib/libs/brotli/dec/bit_reader.h +++ b/contrib/libs/brotli/dec/bit_reader.h @@ -1,7 +1,7 @@ /* Copyright 2013 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ /* Bit reading helpers */ @@ -9,10 +9,10 @@ #ifndef BROTLI_DEC_BIT_READER_H_ #define BROTLI_DEC_BIT_READER_H_ -#include <string.h> /* memcpy */ +#include <string.h> /* memcpy */ #include "../common/platform.h" -#include <brotli/types.h> +#include <brotli/types.h> #if defined(__cplusplus) || defined(c_plusplus) extern "C" { @@ -21,91 +21,91 @@ 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 -}; - -static BROTLI_INLINE uint32_t BitMask(uint32_t n) { + 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 +}; + +static BROTLI_INLINE uint32_t BitMask(uint32_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. */ + /* Masking with this expression turns to a single + "Unsigned Bit Field Extract" UBFX instruction on ARM. */ return ~((0xFFFFFFFFu) << n); - } else { - return kBitMask[n]; - } -} - + } else { + return kBitMask[n]; + } +} + typedef struct { brotli_reg_t val_; /* pre-fetched bits */ - uint32_t bit_pos_; /* current bit-reading position in val_ */ - const uint8_t* next_in; /* the byte we're reading from */ - size_t avail_in; + uint32_t bit_pos_; /* current bit-reading position in val_ */ + const uint8_t* next_in; /* the byte we're reading from */ + size_t avail_in; } BrotliBitReader; -typedef struct { +typedef struct { brotli_reg_t val_; - uint32_t bit_pos_; - const uint8_t* next_in; - size_t avail_in; -} BrotliBitReaderState; - -/* Initializes the BrotliBitReader fields. */ -BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br); - + uint32_t bit_pos_; + const uint8_t* next_in; + size_t avail_in; +} BrotliBitReaderState; + +/* Initializes the BrotliBitReader fields. */ +BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const 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_ALIGNED_READ this function also prepares bit reader for aligned - reading. */ -BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br); - -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 = from->avail_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; - to->avail_in = from->avail_in; -} - -static BROTLI_INLINE uint32_t BrotliGetAvailableBits( - const BrotliBitReader* br) { - return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_; + For BROTLI_ALIGNED_READ this function also prepares bit reader for aligned + reading. */ +BROTLI_INTERNAL BROTLI_BOOL BrotliWarmupBitReader(BrotliBitReader* const br); + +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 = from->avail_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; + to->avail_in = from->avail_in; +} + +static BROTLI_INLINE uint32_t BrotliGetAvailableBits( + const BrotliBitReader* br) { + return (BROTLI_64_BITS ? 64 : 32) - br->bit_pos_; } /* Returns amount of unread bytes the bit reader still has buffered from the BrotliInput, including whole bytes in br->val_. */ static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) { - return br->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, size_t num) { - return TO_BROTLI_BOOL(br->avail_in >= num); -} - + return br->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, size_t num) { + return TO_BROTLI_BOOL(br->avail_in >= num); +} + /* 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. */ + non-64-bit little-endian build only 16 bits are safe to request. */ static BROTLI_INLINE void BrotliFillBitWindow( - BrotliBitReader* const br, uint32_t n_bits) { -#if (BROTLI_64_BITS) + BrotliBitReader* const br, uint32_t n_bits) { +#if (BROTLI_64_BITS) if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) { if (br->bit_pos_ >= 56) { br->val_ >>= 56; @@ -128,11 +128,11 @@ static BROTLI_INLINE void BrotliFillBitWindow( br->val_ >>= 32; br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */ br->val_ |= ((uint64_t)BROTLI_UNALIGNED_LOAD32LE(br->next_in)) << 32; - br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; - br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; + br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; + br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; } } -#else +#else if (!BROTLI_ALIGNED_READ && BROTLI_IS_CONSTANT(n_bits) && (n_bits <= 8)) { if (br->bit_pos_ >= 24) { br->val_ >>= 24; @@ -146,144 +146,144 @@ static BROTLI_INLINE void BrotliFillBitWindow( br->val_ >>= 16; br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */ br->val_ |= ((uint32_t)BROTLI_UNALIGNED_LOAD16LE(br->next_in)) << 16; - br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; - br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ; + br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ; + 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); -} - +/* 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->avail_in == 0) { - return BROTLI_FALSE; - } +static BROTLI_INLINE BROTLI_BOOL BrotliPullByte(BrotliBitReader* const br) { + if (br->avail_in == 0) { + return BROTLI_FALSE; + } br->val_ >>= 8; -#if (BROTLI_64_BITS) - br->val_ |= ((uint64_t)*br->next_in) << 56; +#if (BROTLI_64_BITS) + br->val_ |= ((uint64_t)*br->next_in) << 56; #else - br->val_ |= ((uint32_t)*br->next_in) << 24; + br->val_ |= ((uint32_t)*br->next_in) << 24; #endif br->bit_pos_ -= 8; --br->avail_in; ++br->next_in; - return BROTLI_TRUE; + return BROTLI_TRUE; } -/* Returns currently available bits. - The number of valid bits could be calculated by BrotliGetAvailableBits. */ +/* 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_ >> br->bit_pos_; + return br->val_ >> br->bit_pos_; +} + +/* Like BrotliGetBits, but does not mask the result. + The result contains at least 16 valid bits. */ +static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked( + BrotliBitReader* const br) { + BrotliFillBitWindow(br, 16); + return (uint32_t)BrotliGetBitsUnmasked(br); } -/* Like BrotliGetBits, but does not mask the result. - The result contains at least 16 valid bits. */ -static BROTLI_INLINE uint32_t BrotliGet16BitsUnmasked( - BrotliBitReader* const br) { - BrotliFillBitWindow(br, 16); - return (uint32_t)BrotliGetBitsUnmasked(br); -} - /* Returns the specified number of bits from |br| without advancing bit position. */ static BROTLI_INLINE uint32_t BrotliGetBits( - BrotliBitReader* const br, uint32_t n_bits) { + BrotliBitReader* const br, uint32_t n_bits) { BrotliFillBitWindow(br, n_bits); - return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); + return (uint32_t)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, uint32_t n_bits, uint32_t* val) { - while (BrotliGetAvailableBits(br) < n_bits) { - if (!BrotliPullByte(br)) { - return BROTLI_FALSE; - } - } - *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); - return BROTLI_TRUE; -} - +static BROTLI_INLINE BROTLI_BOOL BrotliSafeGetBits( + BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { + while (BrotliGetAvailableBits(br) < n_bits) { + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; + } + } + *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); + return BROTLI_TRUE; +} + /* Advances the bit pos by |n_bits|. */ static BROTLI_INLINE void BrotliDropBits( - BrotliBitReader* const br, uint32_t n_bits) { - br->bit_pos_ += n_bits; + BrotliBitReader* const br, uint32_t n_bits) { + br->bit_pos_ += n_bits; +} + +static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) { + uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3; + uint32_t unused_bits = unused_bytes << 3; + br->avail_in += unused_bytes; + br->next_in -= unused_bytes; + if (unused_bits == sizeof(br->val_) << 3) { + br->val_ = 0; + } else { + br->val_ <<= unused_bits; + } + br->bit_pos_ += unused_bits; } -static BROTLI_INLINE void BrotliBitReaderUnload(BrotliBitReader* br) { - uint32_t unused_bytes = BrotliGetAvailableBits(br) >> 3; - uint32_t unused_bits = unused_bytes << 3; - br->avail_in += unused_bytes; - br->next_in -= unused_bytes; - if (unused_bits == sizeof(br->val_) << 3) { - br->val_ = 0; - } else { - br->val_ <<= unused_bits; - } - br->bit_pos_ += unused_bits; -} - -/* Reads the specified number of bits from |br| and advances the bit pos. +/* 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, uint32_t n_bits, uint32_t* val) { - *val = (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits); - BROTLI_LOG(("[BrotliReadBits] %d %d %d val: %6x\n", + 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", (int)br->avail_in, (int)br->bit_pos_, (int)n_bits, (int)*val)); - BrotliDropBits(br, n_bits); + BrotliDropBits(br, n_bits); } -/* Reads the specified number of bits from |br| and advances the bit pos. +/* 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( - BrotliBitReader* const br, uint32_t n_bits) { - 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, 8); - BrotliTakeBits(br, n_bits - 16, &high_val); - return low_val | (high_val << 16); - } + BrotliBitReader* const br, uint32_t n_bits) { + 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, 8); + 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. */ -static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits( - BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { - while (BrotliGetAvailableBits(br) < n_bits) { - if (!BrotliPullByte(br)) { - return BROTLI_FALSE; +static BROTLI_INLINE BROTLI_BOOL BrotliSafeReadBits( + BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { + while (BrotliGetAvailableBits(br) < n_bits) { + if (!BrotliPullByte(br)) { + return BROTLI_FALSE; } } BrotliTakeBits(br, n_bits, val); - return BROTLI_TRUE; + return BROTLI_TRUE; } /* 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) { - uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7; +static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) { + uint32_t pad_bits_count = BrotliGetAvailableBits(br) & 0x7; uint32_t pad_bits = 0; if (pad_bits_count != 0) { BrotliTakeBits(br, pad_bits_count, &pad_bits); } - return TO_BROTLI_BOOL(pad_bits == 0); + return TO_BROTLI_BOOL(pad_bits == 0); } /* Copies remaining input bytes stored in the bit reader to the output. Value @@ -291,19 +291,19 @@ static BROTLI_INLINE BROTLI_BOOL BrotliJumpToByteBoundary(BrotliBitReader* br) { 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); + while (BrotliGetAvailableBits(br) >= 8 && num > 0) { + *dest = (uint8_t)BrotliGetBitsUnmasked(br); + BrotliDropBits(br, 8); ++dest; --num; } memcpy(dest, br->next_in, num); - br->avail_in -= num; + br->avail_in -= num; br->next_in += num; } #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif #endif /* BROTLI_DEC_BIT_READER_H_ */ diff --git a/contrib/libs/brotli/dec/decode.c b/contrib/libs/brotli/dec/decode.c index e244a9f1ec..08bd76ca16 100644 --- a/contrib/libs/brotli/dec/decode.c +++ b/contrib/libs/brotli/dec/decode.c @@ -1,24 +1,24 @@ /* Copyright 2013 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT -*/ + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ -#include <brotli/decode.h> +#include <brotli/decode.h> -#include <stdlib.h> /* free, malloc */ -#include <string.h> /* memcpy, memset */ - -#include "../common/constants.h" +#include <stdlib.h> /* free, malloc */ +#include <string.h> /* memcpy, memset */ + +#include "../common/constants.h" #include "../common/context.h" -#include "../common/dictionary.h" +#include "../common/dictionary.h" #include "../common/platform.h" #include "../common/transform.h" -#include "../common/version.h" +#include "../common/version.h" #include "./bit_reader.h" -#include "./huffman.h" -#include "./prefix.h" -#include "./state.h" +#include "./huffman.h" +#include "./prefix.h" +#include "./state.h" #if defined(BROTLI_TARGET_NEON) #include <arm_neon.h> @@ -28,23 +28,23 @@ extern "C" { #endif -#define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE) +#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 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_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 (5 prefix + 24 base + 8 suffix) */ -static const uint32_t kRingBufferWriteAheadSlack = 42; - -static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = { +/* We need the slack region for the following reasons: + - doing up to two 16-byte copies for fast backward copying + - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */ +static const uint32_t kRingBufferWriteAheadSlack = 42; + +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, }; @@ -57,34 +57,34 @@ 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) { +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; + 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; - } + 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) { @@ -94,40 +94,40 @@ BrotliDecoderState* BrotliDecoderCreateInstance( } 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); - } -} - + 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) { - s->error_code = (int)e; - 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; - } -} - +static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode( + BrotliDecoderState* s, BrotliDecoderErrorCode e) { + s->error_code = (int)e; + 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, @@ -166,72 +166,72 @@ static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s, return BROTLI_DECODER_SUCCESS; } -static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) { +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); + 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, uint32_t* value) { +static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8( + BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) { uint32_t bits; switch (s->substate_decode_uint8) { case BROTLI_STATE_DECODE_UINT8_NONE: - if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits == 0) { *value = 0; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* Fall through. */ case BROTLI_STATE_DECODE_UINT8_SHORT: - if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) { + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) { s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits == 0) { *value = 1; s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* Use output value as a temporary storage. It MUST be persisted. */ - *value = bits; + *value = bits; /* Fall through. */ case BROTLI_STATE_DECODE_UINT8_LONG: - if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) { + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) { s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - *value = (1U << *value) + bits; + *value = (1U << *value) + bits; s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; default: - return - BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } /* Decodes a metablock length and flags by reading 2 - 31 bits. */ -static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( - BrotliDecoderState* s, BrotliBitReader* br) { +static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( + BrotliDecoderState* s, BrotliBitReader* br) { uint32_t bits; int i; for (;;) { switch (s->substate_metablock_header) { case BROTLI_STATE_METABLOCK_HEADER_NONE: if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->is_last_metablock = bits ? 1 : 0; + s->is_last_metablock = bits ? 1 : 0; s->meta_block_remaining_len = 0; s->is_uncompressed = 0; s->is_metadata = 0; @@ -244,18 +244,18 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( case BROTLI_STATE_METABLOCK_HEADER_EMPTY: if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits) { s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_DECODER_SUCCESS; + 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; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } s->size_nibbles = (uint8_t)(bits + 4); s->loop_counter = 0; @@ -269,13 +269,13 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( case BROTLI_STATE_METABLOCK_HEADER_SIZE: i = s->loop_counter; - for (; i < (int)s->size_nibbles; ++i) { + for (; i < (int)s->size_nibbles; ++i) { if (!BrotliSafeReadBits(br, 4, &bits)) { s->loop_counter = i; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) { - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE); } s->meta_block_remaining_len |= (int)(bits << (i * 4)); } @@ -284,33 +284,33 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( /* Fall through. */ case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED: - if (!s->is_last_metablock) { + if (!s->is_last_metablock) { if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->is_uncompressed = bits ? 1 : 0; + s->is_uncompressed = bits ? 1 : 0; } ++s->meta_block_remaining_len; s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; case BROTLI_STATE_METABLOCK_HEADER_RESERVED: if (!BrotliSafeReadBits(br, 1, &bits)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits != 0) { - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED); + 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; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (bits == 0) { s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; } s->size_nibbles = (uint8_t)bits; s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA; @@ -318,35 +318,35 @@ static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength( case BROTLI_STATE_METABLOCK_HEADER_METADATA: i = s->loop_counter; - for (; i < (int)s->size_nibbles; ++i) { + for (; i < (int)s->size_nibbles; ++i) { if (!BrotliSafeReadBits(br, 8, &bits)) { s->loop_counter = i; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) { - return BROTLI_FAILURE( - BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE); + return BROTLI_FAILURE( + BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE); } s->meta_block_remaining_len |= (int)(bits << (i * 8)); } - ++s->meta_block_remaining_len; - s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE; - return BROTLI_DECODER_SUCCESS; + ++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); + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } } -/* Decodes the Huffman code. - This method doesn't read data from the bit reader, BUT drops the amount of - bits that correspond to the decoded symbol. - bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */ -static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, - const HuffmanCode* table, - BrotliBitReader* br) { +/* Decodes the Huffman code. + This method doesn't read data from the bit reader, BUT drops the amount of + bits that correspond to the decoded symbol. + bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */ +static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, + const HuffmanCode* table, + BrotliBitReader* br) { 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) { @@ -360,74 +360,74 @@ static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits, 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 uint32_t ReadSymbol(const HuffmanCode* table, - BrotliBitReader* br) { - return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br); -} - -/* Same as DecodeSymbol, but it is known that there is less than 15 bits of - input are currently available. */ -static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol( - const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { - uint32_t val; - uint32_t available_bits = BrotliGetAvailableBits(br); +/* Reads and decodes the next Huffman code from bit-stream. + This method peeks 16 bits of input and drops 0 - 15 of them. */ +static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table, + BrotliBitReader* br) { + return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br); +} + +/* Same as DecodeSymbol, but it is known that there is less than 15 bits of + input are currently available. */ +static BROTLI_NOINLINE 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 (available_bits == 0) { if (BROTLI_HC_FAST_LOAD_BITS(table) == 0) { *result = BROTLI_HC_FAST_LOAD_VALUE(table); - return BROTLI_TRUE; - } + return BROTLI_TRUE; + } return BROTLI_FALSE; /* No valid bits at all. */ - } - val = (uint32_t)BrotliGetBitsUnmasked(br); + } + val = (uint32_t)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_TRUE; + } else { return BROTLI_FALSE; /* Not enough bits for the first level. */ - } - } - if (available_bits <= HUFFMAN_TABLE_BITS) { + } + } + if (available_bits <= HUFFMAN_TABLE_BITS) { return BROTLI_FALSE; /* Not enough bits to move to the second level. */ - } - - /* Speculatively drop HUFFMAN_TABLE_BITS. */ + } + + /* Speculatively drop HUFFMAN_TABLE_BITS. */ val = (val & BitMask(BROTLI_HC_FAST_LOAD_BITS(table))) >> HUFFMAN_TABLE_BITS; - available_bits -= 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, uint32_t* result) { - uint32_t val; - if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) { - *result = DecodeSymbol(val, table, br); - return BROTLI_TRUE; - } - return SafeDecodeSymbol(table, br, result); -} - + return BROTLI_TRUE; +} + +static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol( + const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) { + uint32_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, +static BROTLI_INLINE void PreloadSymbol(int safe, + const HuffmanCode* table, BrotliBitReader* br, - uint32_t* bits, - uint32_t* value) { - if (safe) { - return; - } + uint32_t* bits, + uint32_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); @@ -436,29 +436,29 @@ static BROTLI_INLINE void PreloadSymbol(int safe, /* Decodes the next Huffman code using data prepared by PreloadSymbol. Reads 0 - 15 bits. Also peeks 8 following bits. */ -static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table, +static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table, BrotliBitReader* br, - uint32_t* bits, - uint32_t* value) { - uint32_t result = *value; - if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) { - uint32_t val = BrotliGet16BitsUnmasked(br); + uint32_t* bits, + uint32_t* value) { + uint32_t result = *value; + if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) { + uint32_t val = BrotliGet16BitsUnmasked(br); const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value; - uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS)); + uint32_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); + BrotliDropBits(br, *bits); } - PreloadSymbol(0, table, br, bits, value); + PreloadSymbol(0, table, br, bits, value); return result; } -static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { - uint32_t result = 0; +static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { + uint32_t result = 0; while (x) { x >>= 1; ++result; @@ -466,266 +466,266 @@ static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) { return result; } -/* Reads (s->symbol + 1) symbols. +/* 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( +static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols( uint32_t alphabet_size, uint32_t max_symbol, BrotliDecoderState* s) { /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */ - BrotliBitReader* br = &s->br; - uint32_t max_bits = Log2Floor(alphabet_size - 1); - uint32_t i = s->sub_loop_counter; - uint32_t num_symbols = s->symbol; - while (i <= num_symbols) { - uint32_t v; - if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) { - s->sub_loop_counter = i; - s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } + BrotliBitReader* br = &s->br; + uint32_t max_bits = Log2Floor(alphabet_size - 1); + uint32_t i = s->sub_loop_counter; + uint32_t num_symbols = s->symbol; + while (i <= num_symbols) { + uint32_t v; + if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) { + s->sub_loop_counter = i; + s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } if (v >= max_symbol) { - return - BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET); - } - s->symbols_lists_array[i] = (uint16_t)v; - BROTLI_LOG_UINT(s->symbols_lists_array[i]); - ++i; - } - - for (i = 0; i < num_symbols; ++i) { - uint32_t k = i + 1; - for (; k <= num_symbols; ++k) { - if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) { - return BROTLI_FAILURE(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 + 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]); + ++i; + } + + for (i = 0; i < num_symbols; ++i) { + uint32_t k = i + 1; + for (; k <= num_symbols; ++k) { + if (s->symbols_lists_array[i] == s->symbols_lists_array[k]) { + return BROTLI_FAILURE(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(uint32_t code_len, - uint32_t* symbol, uint32_t* repeat, uint32_t* space, - uint32_t* prev_code_len, uint16_t* symbol_lists, - uint16_t* code_length_histo, int* next_symbol) { - *repeat = 0; +static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len, + uint32_t* symbol, uint32_t* repeat, uint32_t* space, + uint32_t* prev_code_len, uint16_t* symbol_lists, + uint16_t* code_length_histo, int* next_symbol) { + *repeat = 0; if (code_len != 0) { /* code_len == 1..15 */ - symbol_lists[next_symbol[code_len]] = (uint16_t)(*symbol); - next_symbol[code_len] = (int)(*symbol); - *prev_code_len = code_len; - *space -= 32768U >> code_len; - code_length_histo[code_len]++; + symbol_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 + } + (*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(uint32_t code_len, - uint32_t repeat_delta, uint32_t alphabet_size, uint32_t* symbol, - uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len, - uint32_t* repeat_code_len, uint16_t* symbol_lists, - uint16_t* code_length_histo, int* next_symbol) { - uint32_t old_repeat; - uint32_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ - uint32_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ - if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { - new_len = *prev_code_len; - extra_bits = 2; - } - if (*repeat_code_len != new_len) { - *repeat = 0; - *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", +static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len, + uint32_t repeat_delta, uint32_t alphabet_size, uint32_t* symbol, + uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len, + uint32_t* repeat_code_len, uint16_t* symbol_lists, + uint16_t* code_length_histo, int* next_symbol) { + uint32_t old_repeat; + uint32_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ + uint32_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */ + if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { + new_len = *prev_code_len; + extra_bits = 2; + } + if (*repeat_code_len != new_len) { + *repeat = 0; + *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) { - unsigned last = *symbol + repeat_delta; - int next = next_symbol[*repeat_code_len]; - do { - symbol_lists[next] = (uint16_t)*symbol; - next = (int)*symbol; - } while (++(*symbol) != last); - next_symbol[*repeat_code_len] = next; - *space -= repeat_delta << (15 - *repeat_code_len); - code_length_histo[*repeat_code_len] = - (uint16_t)(code_length_histo[*repeat_code_len] + repeat_delta); - } else { - *symbol += repeat_delta; - } -} - -/* Reads and decodes symbol codelengths. */ -static 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; - if (!BrotliWarmupBitReader(br)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } - while (symbol < alphabet_size && space > 0) { - const HuffmanCode* p = s->table; - uint32_t code_len; + if (*repeat_code_len != 0) { + unsigned last = *symbol + repeat_delta; + int next = next_symbol[*repeat_code_len]; + do { + symbol_lists[next] = (uint16_t)*symbol; + next = (int)*symbol; + } while (++(*symbol) != last); + next_symbol[*repeat_code_len] = next; + *space -= repeat_delta << (15 - *repeat_code_len); + code_length_histo[*repeat_code_len] = + (uint16_t)(code_length_histo[*repeat_code_len] + repeat_delta); + } else { + *symbol += repeat_delta; + } +} + +/* Reads and decodes symbol codelengths. */ +static 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; + if (!BrotliWarmupBitReader(br)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + while (symbol < alphabet_size && space > 0) { + const HuffmanCode* p = s->table; + uint32_t code_len; BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p); - if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) { - s->symbol = symbol; - s->repeat = repeat; - s->prev_code_len = prev_code_len; - s->repeat_code_len = repeat_code_len; - s->space = space; - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } - BrotliFillBitWindow16(br); + if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) { + s->symbol = symbol; + s->repeat = repeat; + s->prev_code_len = prev_code_len; + s->repeat_code_len = repeat_code_len; + s->space = space; + return BROTLI_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); + 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 */ - uint32_t extra_bits = - (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3; - uint32_t repeat_delta = - (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(extra_bits); - BrotliDropBits(br, extra_bits); - ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, - &symbol, &repeat, &space, &prev_code_len, &repeat_code_len, - symbol_lists, code_length_histo, next_symbol); - } - } - s->space = space; - return BROTLI_DECODER_SUCCESS; -} - -static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( - uint32_t alphabet_size, BrotliDecoderState* s) { - BrotliBitReader* br = &s->br; - BROTLI_BOOL get_byte = BROTLI_FALSE; - while (s->symbol < alphabet_size && s->space > 0) { - const HuffmanCode* p = s->table; - uint32_t code_len; - uint32_t available_bits; - uint32_t bits = 0; + uint32_t extra_bits = + (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3; + uint32_t repeat_delta = + (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(extra_bits); + BrotliDropBits(br, extra_bits); + ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, + &symbol, &repeat, &space, &prev_code_len, &repeat_code_len, + symbol_lists, code_length_histo, next_symbol); + } + } + s->space = space; + return BROTLI_DECODER_SUCCESS; +} + +static BrotliDecoderErrorCode SafeReadSymbolCodeLengths( + uint32_t alphabet_size, BrotliDecoderState* s) { + BrotliBitReader* br = &s->br; + BROTLI_BOOL get_byte = BROTLI_FALSE; + while (s->symbol < alphabet_size && s->space > 0) { + const HuffmanCode* p = s->table; + uint32_t code_len; + uint32_t available_bits; + uint32_t bits = 0; 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); - } + 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; - } + 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) { + if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) { BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); - ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space, - &s->prev_code_len, s->symbol_lists, s->code_length_histo, - s->next_symbol); + ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space, + &s->prev_code_len, s->symbol_lists, s->code_length_histo, + s->next_symbol); } else { /* code_len == 16..17, extra_bits == 2..3 */ - uint32_t extra_bits = code_len - 14U; + uint32_t extra_bits = code_len - 14U; 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; - } + get_byte = BROTLI_TRUE; + continue; + } BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits); - ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size, - &s->symbol, &s->repeat, &s->space, &s->prev_code_len, - &s->repeat_code_len, s->symbol_lists, s->code_length_histo, - s->next_symbol); - } - } - 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; - uint32_t num_codes = s->repeat; - unsigned space = s->space; - uint32_t i = s->sub_loop_counter; - for (; i < BROTLI_CODE_LENGTH_CODES; ++i) { - const uint8_t code_len_idx = kCodeLengthCodeOrder[i]; - uint32_t ix; - uint32_t v; - if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) { - uint32_t available_bits = BrotliGetAvailableBits(br); - if (available_bits != 0) { - ix = BrotliGetBitsUnmasked(br) & 0xF; - } else { - ix = 0; - } - if (kCodeLengthPrefixLength[ix] > available_bits) { - s->sub_loop_counter = i; - s->repeat = num_codes; - s->space = space; - s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; - return BROTLI_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); - if (v != 0) { - space = space - (32U >> v); - ++num_codes; - ++s->code_length_histo[v]; - if (space - 1U >= 32U) { + 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); + } + } + 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; + uint32_t num_codes = s->repeat; + unsigned space = s->space; + uint32_t i = s->sub_loop_counter; + for (; i < BROTLI_CODE_LENGTH_CODES; ++i) { + const uint8_t code_len_idx = kCodeLengthCodeOrder[i]; + uint32_t ix; + uint32_t v; + if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) { + uint32_t available_bits = BrotliGetAvailableBits(br); + if (available_bits != 0) { + ix = BrotliGetBitsUnmasked(br) & 0xF; + } else { + ix = 0; + } + if (kCodeLengthPrefixLength[ix] > available_bits) { + s->sub_loop_counter = i; + s->repeat = num_codes; + s->space = space; + s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; + return BROTLI_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); + if (v != 0) { + space = space - (32U >> v); + ++num_codes; + ++s->code_length_histo[v]; + if (space - 1U >= 32U) { /* space is 0 or wrapped around. */ - break; - } - } - } - if (!(num_codes == 1 || space == 0)) { - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE); - } - return BROTLI_DECODER_SUCCESS; -} - + 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 @@ -737,167 +737,167 @@ 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, +static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size, uint32_t max_symbol, - HuffmanCode* table, - uint32_t* opt_table_size, - BrotliDecoderState* s) { + HuffmanCode* table, + uint32_t* opt_table_size, + BrotliDecoderState* s) { BrotliBitReader* br = &s->br; /* Unnecessary masking, but might be good for safety. */ alphabet_size &= 0x7FF; /* State machine. */ - for (;;) { - switch (s->substate_huffman) { - case BROTLI_STATE_HUFFMAN_NONE: - if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } - BROTLI_LOG_UINT(s->sub_loop_counter); - /* The value is used as follows: - 1 for simple code; - 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ - if (s->sub_loop_counter != 1) { - s->space = 32; + for (;;) { + switch (s->substate_huffman) { + case BROTLI_STATE_HUFFMAN_NONE: + if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BROTLI_LOG_UINT(s->sub_loop_counter); + /* The value is used as follows: + 1 for simple code; + 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ + if (s->sub_loop_counter != 1) { + s->space = 32; s->repeat = 0; /* num_codes */ - memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) * - (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1)); - memset(&s->code_length_code_lengths[0], 0, - sizeof(s->code_length_code_lengths)); - s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; - continue; - } + memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) * + (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1)); + memset(&s->code_length_code_lengths[0], 0, + sizeof(s->code_length_code_lengths)); + s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX; + continue; + } /* Fall through. */ - - case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE: + + case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE: /* Read symbols, codes & code lengths directly. */ if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */ - s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->sub_loop_counter = 0; + s->sub_loop_counter = 0; /* Fall through. */ - case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { - BrotliDecoderErrorCode result = + case BROTLI_STATE_HUFFMAN_SIMPLE_READ: { + BrotliDecoderErrorCode result = ReadSimpleHuffmanSymbols(alphabet_size, max_symbol, s); - if (result != BROTLI_DECODER_SUCCESS) { - return result; - } - } + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + } /* Fall through. */ - case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: { - uint32_t table_size; - if (s->symbol == 3) { - uint32_t bits; - if (!BrotliSafeReadBits(br, 1, &bits)) { - s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: { + uint32_t table_size; + if (s->symbol == 3) { + uint32_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { + s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->symbol += bits; + s->symbol += bits; } - BROTLI_LOG_UINT(s->symbol); - table_size = BrotliBuildSimpleHuffmanTable( - table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol); + BROTLI_LOG_UINT(s->symbol); + table_size = BrotliBuildSimpleHuffmanTable( + table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol); if (opt_table_size) { - *opt_table_size = table_size; + *opt_table_size = table_size; } s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; - return BROTLI_DECODER_SUCCESS; - } - - /* Decode Huffman-coded code lengths. */ - case BROTLI_STATE_HUFFMAN_COMPLEX: { - uint32_t i; - BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s); - if (result != BROTLI_DECODER_SUCCESS) { - return result; - } - BrotliBuildCodeLengthsHuffmanTable(s->table, - s->code_length_code_lengths, - s->code_length_histo); - memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo)); - for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) { - s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); - s->symbol_lists[s->next_symbol[i]] = 0xFFFF; - } - - s->symbol = 0; - s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH; - s->repeat = 0; - s->repeat_code_len = 0; - s->space = 32768; - s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; + return BROTLI_DECODER_SUCCESS; + } + + /* Decode Huffman-coded code lengths. */ + case BROTLI_STATE_HUFFMAN_COMPLEX: { + uint32_t i; + BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s); + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } + BrotliBuildCodeLengthsHuffmanTable(s->table, + s->code_length_code_lengths, + s->code_length_histo); + memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo)); + for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) { + s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1); + s->symbol_lists[s->next_symbol[i]] = 0xFFFF; + } + + s->symbol = 0; + s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH; + s->repeat = 0; + s->repeat_code_len = 0; + s->space = 32768; + s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS; } /* Fall through. */ - case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: { - uint32_t table_size; + case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: { + uint32_t table_size; BrotliDecoderErrorCode result = ReadSymbolCodeLengths(max_symbol, s); - if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { result = SafeReadSymbolCodeLengths(max_symbol, s); - } - if (result != BROTLI_DECODER_SUCCESS) { - return result; - } + } + if (result != BROTLI_DECODER_SUCCESS) { + return result; + } - if (s->space != 0) { + if (s->space != 0) { BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)s->space)); - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_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_size = BrotliBuildHuffmanTable( + table, HUFFMAN_TABLE_BITS, s->symbol_lists, s->code_length_histo); if (opt_table_size) { *opt_table_size = table_size; } - s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; - return BROTLI_DECODER_SUCCESS; + s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE; + return BROTLI_DECODER_SUCCESS; } - - default: - return - BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); + + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } } /* Decodes a block length by reading 3..39 bits. */ -static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table, - BrotliBitReader* br) { - uint32_t code; - uint32_t nbits; +static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table, + BrotliBitReader* br) { + uint32_t code; + uint32_t nbits; code = ReadSymbol(table, br); nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */ - return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits); -} - -/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then - reading can't be continued with ReadBlockLength. */ -static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( - BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table, - BrotliBitReader* br) { - uint32_t index; - if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) { - if (!SafeReadSymbol(table, br, &index)) { - return BROTLI_FALSE; - } - } else { - index = s->block_length_index; - } - { - uint32_t bits; + return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits); +} + +/* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then + reading can't be continued with ReadBlockLength. */ +static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( + BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table, + BrotliBitReader* br) { + uint32_t index; + if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) { + if (!SafeReadSymbol(table, br, &index)) { + return BROTLI_FALSE; + } + } else { + index = s->block_length_index; + } + { + uint32_t bits; uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */ - if (!BrotliSafeReadBits(br, nbits, &bits)) { - s->block_length_index = index; - s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX; - return BROTLI_FALSE; - } - *result = kBlockLengthPrefixCode[index].offset + bits; - s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE; - return BROTLI_TRUE; - } -} - + 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; + 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: @@ -912,63 +912,63 @@ static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength( Most of input values are 0 and 1. To reduce number of branches, we replace inner for loop with do-while. */ -static BROTLI_NOINLINE void InverseMoveToFrontTransform( - uint8_t* v, uint32_t v_len, BrotliDecoderState* state) { +static BROTLI_NOINLINE void InverseMoveToFrontTransform( + uint8_t* v, uint32_t v_len, BrotliDecoderState* state) { /* Reinitialize elements that could have been changed. */ - uint32_t i = 1; - uint32_t upper_bound = state->mtf_upper_bound; - uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */ - uint8_t* mtf_u8 = (uint8_t*)mtf; + uint32_t i = 1; + uint32_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; + mtf[0] = pattern; do { pattern += 0x04040404; /* Advance all 4 values by 4. */ - mtf[i] = pattern; - i++; + 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]; + uint8_t value = mtf_u8[index]; + upper_bound |= v[i]; v[i] = value; - mtf_u8[-1] = value; + mtf_u8[-1] = value; do { index--; - mtf_u8[index + 1] = mtf_u8[index]; - } while (index >= 0); + mtf_u8[index + 1] = mtf_u8[index]; + } while (index >= 0); } /* Remember amount of elements to be reinitialized. */ - state->mtf_upper_bound = upper_bound >> 2; + state->mtf_upper_bound = upper_bound >> 2; } /* Decodes a series of Huffman table using ReadHuffmanCode function. */ -static BrotliDecoderErrorCode HuffmanTreeGroupDecode( - HuffmanTreeGroup* group, BrotliDecoderState* s) { +static BrotliDecoderErrorCode HuffmanTreeGroupDecode( + HuffmanTreeGroup* group, BrotliDecoderState* s) { if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) { s->next = group->codes; s->htree_index = 0; s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP; } while (s->htree_index < group->num_htrees) { - uint32_t table_size; - BrotliDecoderErrorCode result = + uint32_t table_size; + BrotliDecoderErrorCode result = ReadHuffmanCode(group->alphabet_size, group->max_symbol, s->next, &table_size, s); - if (result != BROTLI_DECODER_SUCCESS) return result; + if (result != BROTLI_DECODER_SUCCESS) return result; group->htrees[s->htree_index] = s->next; s->next += table_size; ++s->htree_index; } s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; } /* Decodes a context map. @@ -979,17 +979,17 @@ static BrotliDecoderErrorCode HuffmanTreeGroupDecode( 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(uint32_t context_map_size, - uint32_t* num_htrees, - uint8_t** context_map_arg, - BrotliDecoderState* s) { +static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, + uint32_t* num_htrees, + uint8_t** context_map_arg, + BrotliDecoderState* s) { BrotliBitReader* br = &s->br; - BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; + BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS; - switch ((int)s->substate_context_map) { + switch ((int)s->substate_context_map) { case BROTLI_STATE_CONTEXT_MAP_NONE: result = DecodeVarLenUint8(s, br, num_htrees); - if (result != BROTLI_DECODER_SUCCESS) { + if (result != BROTLI_DECODER_SUCCESS) { return result; } (*num_htrees)++; @@ -999,804 +999,804 @@ static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size, *context_map_arg = (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)context_map_size); if (*context_map_arg == 0) { - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP); + return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP); } if (*num_htrees <= 1) { memset(*context_map_arg, 0, (size_t)context_map_size); - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; } s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX; /* Fall through. */ - case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: { - uint32_t bits; - /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe - to peek 4 bits ahead. */ - if (!BrotliSafeGetBits(br, 5, &bits)) { - return BROTLI_DECODER_NEEDS_MORE_INPUT; + case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: { + uint32_t bits; + /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe + to peek 4 bits ahead. */ + if (!BrotliSafeGetBits(br, 5, &bits)) { + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - if ((bits & 1) != 0) { /* Use RLE for zeros. */ - s->max_run_length_prefix = (bits >> 1) + 1; - BrotliDropBits(br, 5); + if ((bits & 1) != 0) { /* Use RLE for zeros. */ + s->max_run_length_prefix = (bits >> 1) + 1; + BrotliDropBits(br, 5); } else { s->max_run_length_prefix = 0; - BrotliDropBits(br, 1); + BrotliDropBits(br, 1); } BROTLI_LOG_UINT(s->max_run_length_prefix); s->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; result = ReadHuffmanCode(alphabet_size, alphabet_size, s->context_map_table, NULL, s); - if (result != BROTLI_DECODER_SUCCESS) return result; - s->code = 0xFFFF; + if (result != BROTLI_DECODER_SUCCESS) return result; + s->code = 0xFFFF; s->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 = s->context_index; + uint32_t max_run_length_prefix = s->max_run_length_prefix; uint8_t* context_map = *context_map_arg; - uint32_t code = s->code; - BROTLI_BOOL skip_preamble = (code != 0xFFFF); - while (context_index < context_map_size || skip_preamble) { - if (!skip_preamble) { - if (!SafeReadSymbol(s->context_map_table, br, &code)) { - s->code = 0xFFFF; - s->context_index = context_index; - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } - BROTLI_LOG_UINT(code); - - if (code == 0) { - context_map[context_index++] = 0; - continue; - } - if (code > max_run_length_prefix) { - context_map[context_index++] = - (uint8_t)(code - max_run_length_prefix); - continue; - } - } else { - skip_preamble = BROTLI_FALSE; - } - /* RLE sub-stage. */ - { - uint32_t reps; - if (!BrotliSafeReadBits(br, code, &reps)) { - s->code = code; - s->context_index = context_index; - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } - reps += 1U << code; + uint32_t code = s->code; + BROTLI_BOOL skip_preamble = (code != 0xFFFF); + while (context_index < context_map_size || skip_preamble) { + if (!skip_preamble) { + if (!SafeReadSymbol(s->context_map_table, br, &code)) { + s->code = 0xFFFF; + s->context_index = context_index; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + BROTLI_LOG_UINT(code); + + if (code == 0) { + context_map[context_index++] = 0; + continue; + } + if (code > max_run_length_prefix) { + context_map[context_index++] = + (uint8_t)(code - max_run_length_prefix); + continue; + } + } else { + skip_preamble = BROTLI_FALSE; + } + /* RLE sub-stage. */ + { + uint32_t reps; + if (!BrotliSafeReadBits(br, code, &reps)) { + s->code = code; + s->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); + 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: { - uint32_t bits; - if (!BrotliSafeReadBits(br, 1, &bits)) { - s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM; - return BROTLI_DECODER_NEEDS_MORE_INPUT; + case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: { + uint32_t bits; + if (!BrotliSafeReadBits(br, 1, &bits)) { + s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM; + return BROTLI_DECODER_NEEDS_MORE_INPUT; + } + if (bits != 0) { + InverseMoveToFrontTransform(*context_map_arg, context_map_size, s); } - if (bits != 0) { - InverseMoveToFrontTransform(*context_map_arg, context_map_size, s); - } s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE; - return BROTLI_DECODER_SUCCESS; + return BROTLI_DECODER_SUCCESS; } - default: - return - BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); + default: + return + BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE); } } -/* 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) { - uint32_t max_block_type = s->num_block_types[tree_type]; - const HuffmanCode* type_tree = &s->block_type_trees[ - tree_type * BROTLI_HUFFMAN_MAX_SIZE_258]; - const HuffmanCode* len_tree = &s->block_len_trees[ - tree_type * BROTLI_HUFFMAN_MAX_SIZE_26]; - BrotliBitReader* br = &s->br; - uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2]; - uint32_t block_type; +/* 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) { + uint32_t max_block_type = s->num_block_types[tree_type]; + const HuffmanCode* type_tree = &s->block_type_trees[ + tree_type * BROTLI_HUFFMAN_MAX_SIZE_258]; + const HuffmanCode* len_tree = &s->block_len_trees[ + tree_type * BROTLI_HUFFMAN_MAX_SIZE_26]; + BrotliBitReader* br = &s->br; + uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2]; + uint32_t block_type; if (max_block_type <= 1) { return BROTLI_FALSE; } - + /* Read 0..15 + 3..39 bits. */ - 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) { + 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) { + } else if (block_type == 0) { block_type = ringbuffer[0]; - } else { - block_type -= 2; + } 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);) { - 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) { + 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);) { + 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; - uint32_t block_type = s->block_type_rb[1]; - uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS; + size_t trivial; + uint32_t block_type = s->block_type_rb[1]; + uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS; s->context_map_slice = s->context_map + context_offset; - trivial = s->trivial_literal_contexts[block_type >> 5]; - s->trivial_literal_context = (trivial >> (block_type & 31)) & 1; - s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]]; + 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 +/* 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; - } +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); + 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 + 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; - } - +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); + 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 CopyUncompressedBlockToOutput( - size_t* available_out, uint8_t** next_out, size_t* total_out, - BrotliDecoderState* s) { - /* TODO: avoid allocation for single uncompressed block. */ - if (!BrotliEnsureRingBuffer(s)) { - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1); - } - + } + + s->ringbuffer_size = s->new_ringbuffer_size; + s->ringbuffer_mask = s->new_ringbuffer_size - 1; + s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size; + + return BROTLI_TRUE; +} + +static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput( + size_t* available_out, uint8_t** next_out, size_t* total_out, + BrotliDecoderState* s) { + /* TODO: 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; + 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; + return BROTLI_DECODER_NEEDS_MORE_INPUT; } - s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE; - } + 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) { + 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; + if (s->ringbuffer_size == 1 << s->window_bits) { + s->max_distance = s->max_backward_distance; } - s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; + s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE; break; - } + } } } - BROTLI_DCHECK(0); /* Unreachable */ + BROTLI_DCHECK(0); /* Unreachable */ } -/* 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. - +/* 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 +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; - } + while ((new_ringbuffer_size >> 1) >= min_size) { + new_ringbuffer_size >>= 1; + } } - - s->new_ringbuffer_size = new_ringbuffer_size; + + 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; +/* 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]) { - uint32_t bits; - if (!BrotliSafeReadBits(br, 2, &bits)) { - s->loop_counter = i; - return BROTLI_DECODER_NEEDS_MORE_INPUT; - } + while (i < (int)s->num_block_types[0]) { + uint32_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) { - if (s->distance_code == 0) { - --s->dist_rb_idx; - s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; - /* Compensate double distance-ring-buffer roll for dictionary items. */ - s->distance_context = 1; - } else { - int distance_code = s->distance_code << 1; + BROTLI_LOG_ARRAY_INDEX(s->context_modes, i); + i++; + } + return BROTLI_DECODER_SUCCESS; +} + +static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) { + if (s->distance_code == 0) { + --s->dist_rb_idx; + s->distance_code = s->dist_rb[s->dist_rb_idx & 3]; + /* Compensate double distance-ring-buffer roll for dictionary items. */ + s->distance_context = 1; + } else { + int distance_code = s->distance_code << 1; /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */ const uint32_t kDistanceShortCodeIndexOffset = 0xAAAFFF1B; /* kDistanceShortCodeValueOffset has 2-bit values from LSB: -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */ const uint32_t kDistanceShortCodeValueOffset = 0xFA5FA500; - int v = (s->dist_rb_idx + - (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3; - s->distance_code = s->dist_rb[v]; - v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3; - if ((distance_code & 0x3) != 0) { - s->distance_code += v; - } else { - s->distance_code -= v; - if (s->distance_code <= 0) { + int v = (s->dist_rb_idx + + (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3; + s->distance_code = s->dist_rb[v]; + v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3; + if ((distance_code & 0x3) != 0) { + s->distance_code += v; + } else { + s->distance_code -= v; + if (s->distance_code <= 0) { /* A huge distance will cause a BROTLI_FAILURE() soon. This is a little faster than failing here. */ s->distance_code = 0x7FFFFFFF; } } } -} +} -static BROTLI_INLINE BROTLI_BOOL SafeReadBits( - BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { - if (n_bits != 0) { - return BrotliSafeReadBits(br, n_bits, val); - } else { - *val = 0; - return BROTLI_TRUE; +static BROTLI_INLINE BROTLI_BOOL SafeReadBits( + BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) { + if (n_bits != 0) { + return BrotliSafeReadBits(br, n_bits, val); + } else { + *val = 0; + return BROTLI_TRUE; } -} +} /* Precondition: s->distance_code < 0. */ -static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal( - int safe, BrotliDecoderState* s, BrotliBitReader* br) { - int distval; - BrotliBitReaderState memento; - HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; - if (!safe) { - s->distance_code = (int)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; +static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal( + int safe, BrotliDecoderState* s, BrotliBitReader* br) { + int distval; + BrotliBitReaderState memento; + HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index]; + if (!safe) { + s->distance_code = (int)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; } /* Convert the distance code to the actual distance by possibly looking up past distances from the s->ringbuffer. */ - s->distance_context = 0; + s->distance_context = 0; if ((s->distance_code & ~0xF) == 0) { - 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 { + 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)) { + 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; - } - } - s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1; - --s->block_length[2]; - 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) { - uint32_t cmd_code; - uint32_t insert_len_extra = 0; - uint32_t copy_length; - CmdLutElement v; - BrotliBitReaderState memento; - if (!safe) { - cmd_code = ReadSymbol(s->htree_command, br); - } else { - BrotliBitReaderSaveState(br, &memento); - if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) { - return 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 = BrotliReadBits(br, v.insert_len_extra_bits); - } - copy_length = BrotliReadBits(br, v.copy_len_extra_bits); - } else { - if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) || - !SafeReadBits(br, v.copy_len_extra_bits, ©_length)) { - BrotliBitReaderRestoreState(br, &memento); - return 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, size_t num) { - if (safe) { - return BROTLI_TRUE; - } - return BrotliCheckInputAmount(br, num); -} - -#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; - - if (!CheckInputAmount(safe, br, 28)) { - 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); - } - -CommandBegin: - if (safe) { - s->state = BROTLI_STATE_COMMAND_BEGIN; - } + 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; + } + } + s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1; + --s->block_length[2]; + 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) { + uint32_t cmd_code; + uint32_t insert_len_extra = 0; + uint32_t copy_length; + CmdLutElement v; + BrotliBitReaderState memento; + if (!safe) { + cmd_code = ReadSymbol(s->htree_command, br); + } else { + BrotliBitReaderSaveState(br, &memento); + if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) { + return 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 = BrotliReadBits(br, v.insert_len_extra_bits); + } + copy_length = BrotliReadBits(br, v.copy_len_extra_bits); + } else { + if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) || + !SafeReadBits(br, v.copy_len_extra_bits, ©_length)) { + BrotliBitReaderRestoreState(br, &memento); + return 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, size_t num) { + if (safe) { + return BROTLI_TRUE; + } + return BrotliCheckInputAmount(br, num); +} + +#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; + + if (!CheckInputAmount(safe, br, 28)) { + 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); + } + +CommandBegin: + if (safe) { + s->state = BROTLI_STATE_COMMAND_BEGIN; + } if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */ - s->state = BROTLI_STATE_COMMAND_BEGIN; - result = BROTLI_DECODER_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) { - BROTLI_SAFE(DecodeCommandBlockSwitch(s)); - goto CommandBegin; - } + 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; - } + 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) { - uint32_t bits; - uint32_t value; - PreloadSymbol(safe, s->literal_htree, br, &bits, &value); - do { + if (s->trivial_literal_context) { + uint32_t bits; + uint32_t value; + PreloadSymbol(safe, s->literal_htree, br, &bits, &value); + do { if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */ - s->state = BROTLI_STATE_COMMAND_INNER; - result = BROTLI_DECODER_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { - BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); - PreloadSymbol(safe, s->literal_htree, br, &bits, &value); - if (!s->trivial_literal_context) goto CommandInner; - } - if (!safe) { - s->ringbuffer[pos] = - (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value); - } else { - uint32_t literal; - if (!SafeReadSymbol(s->literal_htree, br, &literal)) { - result = BROTLI_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; + s->state = BROTLI_STATE_COMMAND_INNER; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { + BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); + PreloadSymbol(safe, s->literal_htree, br, &bits, &value); + if (!s->trivial_literal_context) goto CommandInner; + } + if (!safe) { + s->ringbuffer[pos] = + (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value); + } else { + uint32_t literal; + if (!SafeReadSymbol(s->literal_htree, br, &literal)) { + result = BROTLI_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, 28)) { /* 162 bits + 7 bytes */ - s->state = BROTLI_STATE_COMMAND_INNER; - result = BROTLI_DECODER_NEEDS_MORE_INPUT; - goto saveStateAndReturn; - } - if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { - BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); - if (s->trivial_literal_context) goto CommandInner; - } + s->state = BROTLI_STATE_COMMAND_INNER; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + goto saveStateAndReturn; + } + if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) { + BROTLI_SAFE(DecodeLiteralBlockSwitch(s)); + if (s->trivial_literal_context) goto CommandInner; + } 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 { - uint32_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 + BROTLI_LOG_UINT(context); + hc = s->literal_hgroup.htrees[s->context_map_slice[context]]; + p2 = p1; + if (!safe) { + p1 = (uint8_t)ReadSymbol(hc, br); + } else { + uint32_t literal; + if (!SafeReadSymbol(hc, br, &literal)) { + result = BROTLI_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) { + 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). */ @@ -1806,135 +1806,135 @@ CommandPostDecodeLiterals: pos, s->distance_code, i, s->meta_block_remaining_len)); return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE); } - if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH && - i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) { + if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH && + i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) { int address = s->distance_code - s->max_distance - 1; const BrotliDictionary* words = s->dictionary; const BrotliTransforms* transforms = s->transforms; - int offset = (int)s->dictionary->offsets_by_length[i]; - uint32_t shift = s->dictionary->size_bits_by_length[i]; - - int mask = (int)BitMask(shift); - int word_idx = address & mask; - int transform_idx = address >> shift; - /* Compensate double distance-ring-buffer roll. */ - s->dist_rb_idx += s->distance_context; - offset += word_idx * i; + int offset = (int)s->dictionary->offsets_by_length[i]; + uint32_t shift = s->dictionary->size_bits_by_length[i]; + + int mask = (int)BitMask(shift); + int word_idx = 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 (BROTLI_PREDICT_FALSE(!words->data)) { - return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET); - } + 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; + 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 { + 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])); - } - 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; + BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]," + " transform_idx = %d, transformed: [%.*s]\n", + i, word, transform_idx, len, &s->ringbuffer[pos])); + } + pos += len; + s->meta_block_remaining_len -= len; + if (pos >= s->ringbuffer_size) { + s->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 + 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) { + 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) { + 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; - } - -saveStateAndReturn: - s->pos = pos; - s->loop_counter = i; + s->state = BROTLI_STATE_METABLOCK_DONE; + goto saveStateAndReturn; + } else { + goto CommandBegin; + } + +saveStateAndReturn: + s->pos = pos; + s->loop_counter = i; return result; } -#undef BROTLI_SAFE - -static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands( - BrotliDecoderState* s) { - return ProcessCommandsInternal(0, s); -} - -static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands( - BrotliDecoderState* s) { - return ProcessCommandsInternal(1, s); -} - +#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); +} + /* 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) { @@ -1950,143 +1950,143 @@ static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect, uint32_t npostfix) { } } -BrotliDecoderResult BrotliDecoderDecompress( - size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size, - uint8_t* decoded_buffer) { - BrotliDecoderState s; - BrotliDecoderResult result; - size_t total_out = 0; - size_t available_in = encoded_size; - const uint8_t* next_in = encoded_buffer; - size_t available_out = *decoded_size; - uint8_t* next_out = decoded_buffer; +BrotliDecoderResult BrotliDecoderDecompress( + size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size, + uint8_t* decoded_buffer) { + BrotliDecoderState s; + BrotliDecoderResult result; + size_t total_out = 0; + size_t available_in = encoded_size; + const uint8_t* next_in = encoded_buffer; + size_t available_out = *decoded_size; + uint8_t* next_out = decoded_buffer; 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; - } + 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: +/* Invariant: input stream is never overconsumed: - invalid input implies that the whole stream is invalid -> any amount of - input could be read and discarded + 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 + 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 + 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; +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; /* Ensure that |total_out| is set, even if no data will ever be pushed out. */ if (total_out) { *total_out = s->partial_pos_out; } - /* Do not try to process further in a case of unrecoverable error. */ - if ((int)s->error_code < 0) { - return BROTLI_DECODER_RESULT_ERROR; - } - if (*available_out && (!next_out || !*next_out)) { - return SaveErrorCode( - s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS)); - } - if (!*available_out) next_out = 0; + /* Do not try to process further in a case of unrecoverable error. */ + if ((int)s->error_code < 0) { + return BROTLI_DECODER_RESULT_ERROR; + } + if (*available_out && (!next_out || !*next_out)) { + return SaveErrorCode( + s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS)); + } + if (!*available_out) next_out = 0; if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */ - br->avail_in = *available_in; - br->next_in = *next_in; - } else { - /* At least one byte of input is required. More than one byte of input may - be required to complete the transaction -> reading more data must be - done in a loop -> do it in a main loop. */ - result = BROTLI_DECODER_NEEDS_MORE_INPUT; - br->next_in = &s->buffer.u8[0]; - } + br->avail_in = *available_in; + br->next_in = *next_in; + } else { + /* At least one byte of input is required. More than one byte of input may + be required to complete the transaction -> reading more data must be + done in a loop -> do it in a main loop. */ + result = BROTLI_DECODER_NEEDS_MORE_INPUT; + br->next_in = &s->buffer.u8[0]; + } /* State machine */ for (;;) { if (result != BROTLI_DECODER_SUCCESS) { /* Error, needs more input/output. */ - if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + 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; - } + BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s, + available_out, next_out, total_out, BROTLI_TRUE); + /* WriteRingBuffer checks s->meta_block_remaining_len validity. */ + if ((int)intermediate_result < 0) { + result = intermediate_result; + break; + } } if (s->buffer_length != 0) { /* Used with internal buffer. */ if (br->avail_in == 0) { /* Successfully finished read transaction. Accumulator contains less than 8 bits, because internal buffer - is expanded byte-by-byte until it is enough to complete read. */ - s->buffer_length = 0; - /* Switch to input stream and restart. */ - result = BROTLI_DECODER_SUCCESS; - br->avail_in = *available_in; - br->next_in = *next_in; - continue; - } else if (*available_in != 0) { - /* Not enough data in buffer, but can take one more byte from - input stream. */ - result = BROTLI_DECODER_SUCCESS; - s->buffer.u8[s->buffer_length] = **next_in; - s->buffer_length++; - br->avail_in = s->buffer_length; - (*next_in)++; - (*available_in)--; - /* Retry with more data in buffer. */ - continue; - } + 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; + br->avail_in = *available_in; + br->next_in = *next_in; + continue; + } else if (*available_in != 0) { + /* Not enough data in buffer, but can take one more byte from + input stream. */ + result = BROTLI_DECODER_SUCCESS; + s->buffer.u8[s->buffer_length] = **next_in; + s->buffer_length++; + br->avail_in = s->buffer_length; + (*next_in)++; + (*available_in)--; + /* Retry with more data in buffer. */ + continue; + } /* Can't finish reading and no more input. */ - break; + break; } else { /* Input stream doesn't contain enough input. */ - /* Copy tail to internal buffer and return. */ - *next_in = br->next_in; - *available_in = br->avail_in; - while (*available_in) { - s->buffer.u8[s->buffer_length] = **next_in; - s->buffer_length++; - (*next_in)++; - (*available_in)--; - } - break; - } - /* Unreachable. */ + /* Copy tail to internal buffer and return. */ + *next_in = br->next_in; + *available_in = br->avail_in; + while (*available_in) { + s->buffer.u8[s->buffer_length] = **next_in; + s->buffer_length++; + (*next_in)++; + (*available_in)--; + } + break; + } + /* Unreachable. */ } - - /* Fail or needs more output. */ - - if (s->buffer_length != 0) { - /* Just consumed the buffered input and produced some output. Otherwise + + /* 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 = br->avail_in; - *next_in = br->next_in; - } - break; + 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 = br->avail_in; + *next_in = br->next_in; + } + break; } switch (s->state) { case BROTLI_STATE_UNINITED: /* Prepare to the first read. */ if (!BrotliWarmupBitReader(br)) { - result = BROTLI_DECODER_NEEDS_MORE_INPUT; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; break; } /* Decode window size. */ @@ -2108,7 +2108,7 @@ BrotliDecoderResult BrotliDecoderDecompressStream( } if (s->window_bits < BROTLI_LARGE_MIN_WBITS || s->window_bits > BROTLI_LARGE_MAX_WBITS) { - result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS); break; } s->state = BROTLI_STATE_INITIALIZE; @@ -2116,32 +2116,32 @@ BrotliDecoderResult BrotliDecoderDecompressStream( 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; + /* 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); + 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->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); + 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) { + if (result != BROTLI_DECODER_SUCCESS) { break; } BROTLI_LOG_UINT(s->is_last_metablock); @@ -2150,7 +2150,7 @@ BrotliDecoderResult BrotliDecoderDecompressStream( 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); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1); break; } } @@ -2162,131 +2162,131 @@ BrotliDecoderResult BrotliDecoderDecompressStream( s->state = BROTLI_STATE_METABLOCK_DONE; break; } - BrotliCalculateRingBufferSize(s); + BrotliCalculateRingBufferSize(s); if (s->is_uncompressed) { s->state = BROTLI_STATE_UNCOMPRESSED; break; } - s->loop_counter = 0; + s->loop_counter = 0; 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) { + 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; + result = BROTLI_DECODER_NEEDS_MORE_INPUT; break; } } - if (result == BROTLI_DECODER_SUCCESS) { + if (result == BROTLI_DECODER_SUCCESS) { s->state = BROTLI_STATE_METABLOCK_DONE; } break; case BROTLI_STATE_HUFFMAN_CODE_0: - if (s->loop_counter >= 3) { - s->state = BROTLI_STATE_METABLOCK_HEADER_2; + 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) { + 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++; + 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; + s->state = BROTLI_STATE_HUFFMAN_CODE_1; /* Fall through. */ - case BROTLI_STATE_HUFFMAN_CODE_1: { + case BROTLI_STATE_HUFFMAN_CODE_1: { uint32_t alphabet_size = s->num_block_types[s->loop_counter] + 2; - int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258; + 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; - } + &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: { + case BROTLI_STATE_HUFFMAN_CODE_2: { uint32_t alphabet_size = BROTLI_NUM_BLOCK_LEN_SYMBOLS; - int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26; + 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->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; + 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++; + BROTLI_LOG_UINT(s->block_length[s->loop_counter]); + s->loop_counter++; s->state = BROTLI_STATE_HUFFMAN_CODE_0; break; - } + } - case BROTLI_STATE_METABLOCK_HEADER_2: { - uint32_t bits; - if (!BrotliSafeReadBits(br, 6, &bits)) { - result = BROTLI_DECODER_NEEDS_MORE_INPUT; + case BROTLI_STATE_METABLOCK_HEADER_2: { + uint32_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 = BROTLI_NUM_DISTANCE_SHORT_CODES + - (bits << s->distance_postfix_bits); + s->distance_postfix_bits = bits & BitMask(2); + bits >>= 2; + s->num_direct_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES + + (bits << s->distance_postfix_bits); BROTLI_LOG_UINT(s->num_direct_distance_codes); BROTLI_LOG_UINT(s->distance_postfix_bits); s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits); - s->context_modes = + 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); + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES); break; } - s->loop_counter = 0; - s->state = BROTLI_STATE_CONTEXT_MODES; - } + 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; + 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) { + 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); + DetectTrivialLiteralBlockTypes(s); s->state = BROTLI_STATE_CONTEXT_MAP_2; /* Fall through. */ @@ -2321,7 +2321,7 @@ BrotliDecoderResult BrotliDecoderDecompressStream( return SaveErrorCode(s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS)); } - s->loop_counter = 0; + s->loop_counter = 0; s->state = BROTLI_STATE_TREE_GROUP; } /* Fall through. */ @@ -2336,16 +2336,16 @@ BrotliDecoderResult BrotliDecoderDecompressStream( BROTLI_DECODER_ERROR_UNREACHABLE)); } result = HuffmanTreeGroupDecode(hgroup, s); - if (result != BROTLI_DECODER_SUCCESS) break; - s->loop_counter++; - if (s->loop_counter >= 3) { - PrepareLiteralDecoding(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; - } + if (!BrotliEnsureRingBuffer(s)) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2); + break; + } s->state = BROTLI_STATE_COMMAND_BEGIN; } break; @@ -2355,12 +2355,12 @@ BrotliDecoderResult BrotliDecoderDecompressStream( /* Fall through. */ case BROTLI_STATE_COMMAND_INNER: /* Fall through. */ - case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS: + 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); + result = ProcessCommands(s); + if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) { + result = SafeProcessCommands(s); } break; @@ -2369,138 +2369,138 @@ BrotliDecoderResult BrotliDecoderDecompressStream( 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) { + 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; - } + 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) { - if (s->meta_block_remaining_len == 0) { + if (s->meta_block_remaining_len == 0) { /* Next metablock, if any. */ s->state = BROTLI_STATE_METABLOCK_DONE; } else { - s->state = BROTLI_STATE_COMMAND_BEGIN; + s->state = BROTLI_STATE_COMMAND_BEGIN; } - break; + 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) { + 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; + } else { + s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS; } - break; + 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->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 = br->avail_in; - *next_in = br->next_in; - } + if (!BrotliJumpToByteBoundary(br)) { + result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2); + break; + } + if (s->buffer_length == 0) { + BrotliBitReaderUnload(br); + *available_in = br->avail_in; + *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) { + result = WriteRingBuffer( + s, available_out, next_out, total_out, BROTLI_TRUE); + if (result != BROTLI_DECODER_SUCCESS) { break; } } - return SaveErrorCode(s, result); + return SaveErrorCode(s, result); } } - return SaveErrorCode(s, result); -} - -BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) { - /* After unrecoverable error remaining output is considered nonsensical. */ - if ((int)s->error_code < 0) { - return BROTLI_FALSE; - } - return TO_BROTLI_BOOL( - s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0); -} - -const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) { - uint8_t* result = 0; - size_t available_out = *size ? *size : 1u << 24; - size_t requested_out = available_out; - BrotliDecoderErrorCode status; - if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) { - *size = 0; - return 0; - } - WrapRingBuffer(s); - status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE); - /* Either WriteRingBuffer returns those "success" codes... */ - if (status == BROTLI_DECODER_SUCCESS || - status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) { - *size = requested_out - available_out; - } else { - /* ... or stream is broken. Normally this should be caught by - BrotliDecoderDecompressStream, this is just a safeguard. */ - if ((int)status < 0) SaveErrorCode(s, status); - *size = 0; - result = 0; - } + return SaveErrorCode(s, result); +} + +BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) { + /* After unrecoverable error remaining output is considered nonsensical. */ + if ((int)s->error_code < 0) { + return BROTLI_FALSE; + } + return TO_BROTLI_BOOL( + s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0); +} + +const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) { + uint8_t* result = 0; + size_t available_out = *size ? *size : 1u << 24; + size_t requested_out = available_out; + BrotliDecoderErrorCode status; + if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) { + *size = 0; + return 0; + } + WrapRingBuffer(s); + status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE); + /* Either WriteRingBuffer returns those "success" codes... */ + if (status == BROTLI_DECODER_SUCCESS || + status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) { + *size = requested_out - available_out; + } else { + /* ... or stream is broken. Normally this should be caught by + BrotliDecoderDecompressStream, this is just a safeguard. */ + if ((int)status < 0) SaveErrorCode(s, status); + *size = 0; + result = 0; + } 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 #NAME; -#define BROTLI_NOTHING_ - BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_) -#undef BROTLI_ERROR_CODE_CASE_ -#undef BROTLI_NOTHING_ - default: return "INVALID"; - } -} - -uint32_t BrotliDecoderVersion() { - return BROTLI_VERSION; -} - +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 #NAME; +#define BROTLI_NOTHING_ + BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_) +#undef BROTLI_ERROR_CODE_CASE_ +#undef BROTLI_NOTHING_ + default: return "INVALID"; + } +} + +uint32_t BrotliDecoderVersion() { + return BROTLI_VERSION; +} + #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif diff --git a/contrib/libs/brotli/dec/huffman.c b/contrib/libs/brotli/dec/huffman.c index 14f41f7adc..30c40d33f2 100644 --- a/contrib/libs/brotli/dec/huffman.c +++ b/contrib/libs/brotli/dec/huffman.c @@ -1,77 +1,77 @@ /* Copyright 2013 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + 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 <string.h> /* memcpy, memset */ - -#include "../common/constants.h" + +#include <string.h> /* memcpy, memset */ + +#include "../common/constants.h" #include "../common/platform.h" -#include <brotli/types.h> +#include <brotli/types.h> #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif -#define BROTLI_REVERSE_BITS_MAX 8 - +#define BROTLI_REVERSE_BITS_MAX 8 + #if defined(BROTLI_RBIT) -#define BROTLI_REVERSE_BITS_BASE \ +#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 \ +#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. */ + +/* 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]; + return BROTLI_RBIT(num); +#else + return kReverseBits[num]; #endif } @@ -103,20 +103,20 @@ static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count, void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, const uint8_t* const code_lengths, - uint16_t* count) { + 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 */ + 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 <= + BROTLI_REVERSE_BITS_MAX); /* Generate offsets into sorted symbol table by code length. */ symbol = -1; @@ -126,11 +126,11 @@ void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, offset[bits] = symbol; bits++; }); - /* Symbols with code length 0 are placed after all other symbols. */ - offset[0] = BROTLI_CODE_LENGTH_CODES - 1; + /* 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; + symbol = BROTLI_CODE_LENGTH_CODES; do { BROTLI_REPEAT(6, { symbol--; @@ -140,8 +140,8 @@ void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH; - /* Special case: all symbols but one have 0 code length. */ - if (offset[0] == 0) { + /* 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; @@ -151,25 +151,25 @@ void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table, /* Fill in table. */ key = 0; - key_step = BROTLI_REVERSE_BITS_LOWEST; + 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; + ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code); + key += key_step; } step <<= 1; - key_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) { +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 */ @@ -186,10 +186,10 @@ uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, 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); - + 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; @@ -205,7 +205,7 @@ uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, table_size = 1 << table_bits; } key = 0; - key_step = BROTLI_REVERSE_BITS_LOWEST; + key_step = BROTLI_REVERSE_BITS_LOWEST; bits = 1; step = 2; do { @@ -213,11 +213,11 @@ uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, 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; + ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code); + key += key_step; } step <<= 1; - key_step >>= 1; + key_step >>= 1; } while (++bits <= table_bits); /* If root_bits != table_bits then replicate to fill the remaining slots. */ @@ -228,42 +228,42 @@ uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, } /* 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) { + 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)) { + 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; + 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; + 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; + ReplicateValue( + &table[BrotliReverseBits(sub_key)], step, table_size, code); + sub_key += sub_key_step; } - step <<= 1; - sub_key_step >>= 1; + step <<= 1; + sub_key_step >>= 1; } - return (uint32_t)total_size; + 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; +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]); @@ -290,14 +290,14 @@ uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, } 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; + 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; } } } @@ -305,14 +305,14 @@ uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, table[2] = ConstructHuffmanCode(2, val[1]); table[1] = ConstructHuffmanCode(2, val[2]); table[3] = ConstructHuffmanCode(2, val[3]); - table_size = 4; + table_size = 4; break; - } - case 4: { - if (val[3] < val[2]) { - uint16_t t = val[3]; - val[3] = val[2]; - val[2] = t; + } + 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]); @@ -322,9 +322,9 @@ uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, table[5] = ConstructHuffmanCode(2, val[1]); table[6] = ConstructHuffmanCode(1, val[0]); table[7] = ConstructHuffmanCode(3, val[3]); - table_size = 8; + table_size = 8; break; - } + } } while (table_size != goal_size) { memcpy(&table[table_size], &table[0], @@ -335,5 +335,5 @@ uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, } #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif diff --git a/contrib/libs/brotli/dec/huffman.h b/contrib/libs/brotli/dec/huffman.h index fa446f0175..b9f0716c16 100644 --- a/contrib/libs/brotli/dec/huffman.h +++ b/contrib/libs/brotli/dec/huffman.h @@ -1,7 +1,7 @@ /* Copyright 2013 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ /* Utilities for building Huffman decoding tables. */ @@ -10,7 +10,7 @@ #define BROTLI_DEC_HUFFMAN_H_ #include "../common/platform.h" -#include <brotli/types.h> +#include <brotli/types.h> #if defined(__cplusplus) || defined(c_plusplus) extern "C" { @@ -18,18 +18,18 @@ extern "C" { #define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15 -/* Maximum possible Huffman table size for an alphabet size of (index * 32), +/* 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, +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 */ -#define BROTLI_HUFFMAN_MAX_SIZE_258 632 -/* BROTLI_MAX_CONTEXT_MAP_SYMBOLS == 272 */ -#define BROTLI_HUFFMAN_MAX_SIZE_272 646 +/* 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 @@ -42,8 +42,8 @@ static const uint16_t kMaxHuffmanTableSize[] = { /* 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 */ + 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, @@ -94,20 +94,20 @@ static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits, #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); +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_arg); +BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table, + int root_bits, const uint16_t* const symbol_lists, uint16_t* count_arg); /* 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); +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 @@ -115,13 +115,13 @@ BROTLI_INTERNAL uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table, typedef struct { HuffmanCode** htrees; HuffmanCode* codes; - uint16_t alphabet_size; + uint16_t alphabet_size; uint16_t max_symbol; - uint16_t num_htrees; + uint16_t num_htrees; } HuffmanTreeGroup; #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif #endif /* BROTLI_DEC_HUFFMAN_H_ */ diff --git a/contrib/libs/brotli/dec/prefix.h b/contrib/libs/brotli/dec/prefix.h index 17bf3a4729..3ea062d84a 100644 --- a/contrib/libs/brotli/dec/prefix.h +++ b/contrib/libs/brotli/dec/prefix.h @@ -1,7 +1,7 @@ /* Copyright 2013 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + 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 @@ -10,18 +10,18 @@ #ifndef BROTLI_DEC_PREFIX_H_ #define BROTLI_DEC_PREFIX_H_ -#include "../common/constants.h" -#include <brotli/types.h> - +#include "../common/constants.h" +#include <brotli/types.h> + /* Represents the range of values belonging to a prefix code: [offset, offset + 2^nbits) */ struct PrefixCodeRange { - uint16_t offset; - uint8_t nbits; + uint16_t offset; + uint8_t nbits; }; -static const struct PrefixCodeRange - kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = { +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}, @@ -40,7 +40,7 @@ typedef struct CmdLutElement { uint16_t copy_len_offset; } CmdLutElement; -static const CmdLutElement kCmdLut[BROTLI_NUM_COMMAND_SYMBOLS] = { +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 }, diff --git a/contrib/libs/brotli/dec/state.c b/contrib/libs/brotli/dec/state.c index af4f115885..e0b37c2dcd 100644 --- a/contrib/libs/brotli/dec/state.c +++ b/contrib/libs/brotli/dec/state.c @@ -1,14 +1,14 @@ /* Copyright 2015 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT -*/ + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT +*/ -#include "./state.h" +#include "./state.h" -#include <stdlib.h> /* free, malloc */ +#include <stdlib.h> /* free, malloc */ -#include <brotli/types.h> +#include <brotli/types.h> #include "./huffman.h" #if defined(__cplusplus) || defined(c_plusplus) @@ -16,20 +16,20 @@ extern "C" { #endif BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, - brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { - if (!alloc_func) { + 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->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; @@ -38,20 +38,20 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, 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; - - s->buffer_length = 0; - s->loop_counter = 0; - s->pos = 0; - s->rb_roundtrips = 0; - s->partial_pos_out = 0; - + 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->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->ringbuffer_size = 0; + s->new_ringbuffer_size = 0; + s->ringbuffer_mask = 0; s->context_map = NULL; s->context_modes = NULL; @@ -59,8 +59,8 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, s->context_map_slice = NULL; s->dist_context_map_slice = NULL; - s->sub_loop_counter = 0; - + s->sub_loop_counter = 0; + s->literal_hgroup.codes = NULL; s->literal_hgroup.htrees = NULL; s->insert_copy_hgroup.codes = NULL; @@ -68,11 +68,11 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, 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->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; @@ -87,7 +87,7 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, /* Make small negative indexes addressable. */ s->symbol_lists = &s->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1]; - s->mtf_upper_bound = 63; + s->mtf_upper_bound = 63; s->dictionary = BrotliGetDictionary(); s->transforms = BrotliGetTransforms(); @@ -95,7 +95,7 @@ BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s, return BROTLI_TRUE; } -void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s) { +void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s) { s->meta_block_remaining_len = 0; s->block_length[0] = 1U << 24; s->block_length[1] = 1U << 24; @@ -125,7 +125,7 @@ void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s) { s->distance_hgroup.htrees = NULL; } -void BrotliDecoderStateCleanupAfterMetablock(BrotliDecoderState* s) { +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); @@ -134,31 +134,31 @@ void BrotliDecoderStateCleanupAfterMetablock(BrotliDecoderState* s) { BROTLI_DECODER_FREE(s, s->distance_hgroup.htrees); } -void BrotliDecoderStateCleanup(BrotliDecoderState* s) { - BrotliDecoderStateCleanupAfterMetablock(s); +void BrotliDecoderStateCleanup(BrotliDecoderState* s) { + BrotliDecoderStateCleanupAfterMetablock(s); BROTLI_DECODER_FREE(s, s->ringbuffer); BROTLI_DECODER_FREE(s, s->block_type_trees); } -BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit(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]; - 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). */ + /* Pack two allocations into one */ + const size_t max_table_size = kMaxHuffmanTableSize[(alphabet_size + 31) >> 5]; + 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->alphabet_size = (uint16_t)alphabet_size; group->max_symbol = (uint16_t)max_symbol; - group->num_htrees = (uint16_t)ntrees; - group->htrees = p; - group->codes = (HuffmanCode*)(&p[ntrees]); - return !!p; -} - + group->num_htrees = (uint16_t)ntrees; + group->htrees = p; + group->codes = (HuffmanCode*)(&p[ntrees]); + return !!p; +} + #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif diff --git a/contrib/libs/brotli/dec/state.h b/contrib/libs/brotli/dec/state.h index 4eb1c8aadd..d28b63920e 100644 --- a/contrib/libs/brotli/dec/state.h +++ b/contrib/libs/brotli/dec/state.h @@ -1,7 +1,7 @@ /* Copyright 2015 Google Inc. All Rights Reserved. - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT + Distributed under MIT license. + See file LICENSE for detail or copy at https://opensource.org/licenses/MIT */ /* Brotli state for partial streaming decoding. */ @@ -9,11 +9,11 @@ #ifndef BROTLI_DEC_STATE_H_ #define BROTLI_DEC_STATE_H_ -#include "../common/constants.h" -#include "../common/dictionary.h" +#include "../common/constants.h" +#include "../common/dictionary.h" #include "../common/platform.h" #include "../common/transform.h" -#include <brotli/types.h> +#include <brotli/types.h> #include "./bit_reader.h" #include "./huffman.h" @@ -27,12 +27,12 @@ typedef enum { BROTLI_STATE_INITIALIZE, BROTLI_STATE_METABLOCK_BEGIN, BROTLI_STATE_METABLOCK_HEADER, - BROTLI_STATE_METABLOCK_HEADER_2, + 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_COMMAND_POST_DECODE_LITERALS, + BROTLI_STATE_COMMAND_POST_WRAP_COPY, BROTLI_STATE_UNCOMPRESSED, BROTLI_STATE_METADATA, BROTLI_STATE_COMMAND_INNER_WRITE, @@ -62,7 +62,7 @@ typedef enum { typedef enum { BROTLI_STATE_UNCOMPRESSED_NONE, - BROTLI_STATE_UNCOMPRESSED_WRITE + BROTLI_STATE_UNCOMPRESSED_WRITE } BrotliRunningUncompressedState; typedef enum { @@ -74,16 +74,16 @@ 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 + 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_SIMPLE_SIZE, + BROTLI_STATE_HUFFMAN_SIMPLE_READ, + BROTLI_STATE_HUFFMAN_SIMPLE_BUILD, + BROTLI_STATE_HUFFMAN_COMPLEX, BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS } BrotliRunningHuffmanState; @@ -93,30 +93,30 @@ typedef enum { BROTLI_STATE_DECODE_UINT8_LONG } BrotliRunningDecodeUint8State; -typedef enum { - BROTLI_STATE_READ_BLOCK_LENGTH_NONE, - BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX -} BrotliRunningReadBlockLengthState; - -struct BrotliDecoderStateStruct { +typedef enum { + BROTLI_STATE_READ_BLOCK_LENGTH_NONE, + BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX +} BrotliRunningReadBlockLengthState; + +struct BrotliDecoderStateStruct { BrotliRunningState state; - + /* This counter is reused for several disjoint loops. */ - int loop_counter; - + int loop_counter; + BrotliBitReader br; - - brotli_alloc_func alloc_func; - brotli_free_func free_func; - void* memory_manager_opaque; - - /* Temporary storage for remaining input. */ - union { - uint64_t u64; - uint8_t u8[8]; - } buffer; - uint32_t buffer_length; - + + brotli_alloc_func alloc_func; + brotli_free_func free_func; + void* memory_manager_opaque; + + /* Temporary storage for remaining input. */ + union { + uint64_t u64; + uint8_t u8[8]; + } buffer; + uint32_t buffer_length; + int pos; int max_backward_distance; int max_distance; @@ -124,8 +124,8 @@ struct BrotliDecoderStateStruct { int ringbuffer_mask; int dist_rb_idx; int dist_rb[4]; - int error_code; - uint32_t sub_loop_counter; + int error_code; + uint32_t sub_loop_counter; uint8_t* ringbuffer; uint8_t* ringbuffer_end; HuffmanCode* htree_command; @@ -147,19 +147,19 @@ struct BrotliDecoderStateStruct { computed. After distance computation it is used as a temporary variable. */ int distance_context; int meta_block_remaining_len; - uint32_t block_length_index; - uint32_t block_length[3]; - uint32_t num_block_types[3]; - uint32_t block_type_rb[6]; - uint32_t distance_postfix_bits; - uint32_t num_direct_distance_codes; + uint32_t block_length_index; + uint32_t block_length[3]; + uint32_t num_block_types[3]; + 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; + uint32_t num_dist_htrees; uint8_t* dist_context_map; - HuffmanCode* literal_htree; + HuffmanCode* literal_htree; uint8_t dist_htree_index; - uint32_t repeat_code_len; - uint32_t prev_code_len; + uint32_t repeat_code_len; + uint32_t prev_code_len; int copy_length; int distance_code; @@ -174,14 +174,14 @@ struct BrotliDecoderStateStruct { uint32_t space; HuffmanCode table[32]; - /* List of heads of symbol chains. */ + /* 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]; + BROTLI_NUM_COMMAND_SYMBOLS]; /* Tails of symbol chains. */ int next_symbol[32]; - uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES]; + uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES]; /* Population counts for the code lengths. */ uint16_t code_length_histo[16]; @@ -190,14 +190,14 @@ struct BrotliDecoderStateStruct { 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]; + 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]; + uint32_t mtf_upper_bound; + uint32_t mtf[64 + 1]; /* Less used attributes are at the end of this struct. */ @@ -208,42 +208,42 @@ struct BrotliDecoderStateStruct { BrotliRunningUncompressedState substate_uncompressed; BrotliRunningHuffmanState substate_huffman; BrotliRunningDecodeUint8State substate_decode_uint8; - BrotliRunningReadBlockLengthState substate_read_block_length; + BrotliRunningReadBlockLengthState substate_read_block_length; - 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 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 size_nibbles : 8; + unsigned int size_nibbles : 8; uint32_t window_bits; - int new_ringbuffer_size; + int new_ringbuffer_size; - uint32_t num_literal_htrees; + uint32_t num_literal_htrees; uint8_t* context_map; uint8_t* context_modes; - const BrotliDictionary* dictionary; + const BrotliDictionary* dictionary; const BrotliTransforms* transforms; - uint32_t trivial_literal_contexts[8]; /* 256 bits */ -}; + uint32_t trivial_literal_contexts[8]; /* 256 bits */ +}; + +typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal; +#define BrotliDecoderState BrotliDecoderStateInternal -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, uint32_t alphabet_size, +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, uint32_t alphabet_size, uint32_t max_symbol, uint32_t ntrees); - + #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L) #define BROTLI_DECODER_FREE(S, X) { \ @@ -252,7 +252,7 @@ BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit( } #if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ +} /* extern "C" */ #endif #endif /* BROTLI_DEC_STATE_H_ */ diff --git a/contrib/libs/brotli/dec/ya.make b/contrib/libs/brotli/dec/ya.make index 9e16df657f..0f482f36ed 100644 --- a/contrib/libs/brotli/dec/ya.make +++ b/contrib/libs/brotli/dec/ya.make @@ -15,11 +15,11 @@ NO_UTIL() NO_COMPILER_WARNINGS() ADDINCL(GLOBAL contrib/libs/brotli/include) - -PEERDIR( - contrib/libs/brotli/common -) - + +PEERDIR( + contrib/libs/brotli/common +) + SRCS( bit_reader.c decode.c |