diff options
Diffstat (limited to 'BaseTools/Source/C/BrotliCompress/dec')
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/bit_reader.c | 48 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/bit_reader.h | 383 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/context.h | 251 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/decode.c | 2347 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/decode.h | 188 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/huffman.c | 357 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/huffman.h | 68 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/port.h | 159 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/prefix.h | 751 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/state.c | 168 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/state.h | 246 | ||||
| -rw-r--r-- | BaseTools/Source/C/BrotliCompress/dec/transform.h | 300 |
12 files changed, 0 insertions, 5266 deletions
diff --git a/BaseTools/Source/C/BrotliCompress/dec/bit_reader.c b/BaseTools/Source/C/BrotliCompress/dec/bit_reader.c deleted file mode 100644 index 83dcc36b46..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/bit_reader.c +++ /dev/null @@ -1,48 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Bit reading helpers */
-
-#include "./bit_reader.h"
-
-#include "../common/types.h"
-#include "./port.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-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 aligment. */
- 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;
- }
- }
- return BROTLI_TRUE;
-}
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
diff --git a/BaseTools/Source/C/BrotliCompress/dec/bit_reader.h b/BaseTools/Source/C/BrotliCompress/dec/bit_reader.h deleted file mode 100644 index c0f6d1bf6e..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/bit_reader.h +++ /dev/null @@ -1,383 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Bit reading helpers */
-
-#ifndef BROTLI_DEC_BIT_READER_H_
-#define BROTLI_DEC_BIT_READER_H_
-
-#include <string.h> /* memcpy */
-
-#include "../common/types.h"
-#include "./port.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-#if (BROTLI_64_BITS)
-#define BROTLI_SHORT_FILL_BIT_WINDOW_READ 4
-typedef uint64_t reg_t;
-#else
-#define BROTLI_SHORT_FILL_BIT_WINDOW_READ 2
-typedef uint32_t reg_t;
-#endif
-
-static const uint32_t kBitMask[33] = { 0x0000,
- 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 (IS_CONSTANT(n) || BROTLI_HAS_UBFX) {
- /* Masking with this expression turns to a single
- "Unsigned Bit Field Extract" UBFX instruction on ARM. */
- return ~((0xffffffffU) << n);
- } else {
- return kBitMask[n];
- }
-}
-
-typedef struct {
- 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;
-} BrotliBitReader;
-
-typedef struct {
- reg_t val_;
- uint32_t bit_pos_;
- const uint8_t* next_in;
- size_t avail_in;
-} BrotliBitReaderState;
-
-/* Initializes the bitreader fields. */
-BROTLI_INTERNAL void BrotliInitBitReader(BrotliBitReader* const br);
-
-/* Ensures that accumulator is not empty. May consume one byte of input.
- Returns 0 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_;
-}
-
-/* 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 ringbuffer (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);
-}
-
-static BROTLI_INLINE uint16_t BrotliLoad16LE(const uint8_t* in) {
- if (BROTLI_LITTLE_ENDIAN) {
- return *((const uint16_t*)in);
- } else if (BROTLI_BIG_ENDIAN) {
- uint16_t value = *((const uint16_t*)in);
- return (uint16_t)(((value & 0xFFU) << 8) | ((value & 0xFF00U) >> 8));
- } else {
- return (uint16_t)(in[0] | (in[1] << 8));
- }
-}
-
-static BROTLI_INLINE uint32_t BrotliLoad32LE(const uint8_t* in) {
- if (BROTLI_LITTLE_ENDIAN) {
- return *((const uint32_t*)in);
- } else if (BROTLI_BIG_ENDIAN) {
- uint32_t value = *((const uint32_t*)in);
- return ((value & 0xFFU) << 24) | ((value & 0xFF00U) << 8) |
- ((value & 0xFF0000U) >> 8) | ((value & 0xFF000000U) >> 24);
- } else {
- uint32_t value = (uint32_t)(*(in++));
- value |= (uint32_t)(*(in++)) << 8;
- value |= (uint32_t)(*(in++)) << 16;
- value |= (uint32_t)(*(in++)) << 24;
- return value;
- }
-}
-
-#if (BROTLI_64_BITS)
-static BROTLI_INLINE uint64_t BrotliLoad64LE(const uint8_t* in) {
- if (BROTLI_LITTLE_ENDIAN) {
- return *((const uint64_t*)in);
- } else if (BROTLI_BIG_ENDIAN) {
- uint64_t value = *((const uint64_t*)in);
- return
- ((value & 0xFFU) << 56) |
- ((value & 0xFF00U) << 40) |
- ((value & 0xFF0000U) << 24) |
- ((value & 0xFF000000U) << 8) |
- ((value & 0xFF00000000U) >> 8) |
- ((value & 0xFF0000000000U) >> 24) |
- ((value & 0xFF000000000000U) >> 40) |
- ((value & 0xFF00000000000000U) >> 56);
- } else {
- uint64_t value = (uint64_t)(*(in++));
- value |= (uint64_t)(*(in++)) << 8;
- value |= (uint64_t)(*(in++)) << 16;
- value |= (uint64_t)(*(in++)) << 24;
- value |= (uint64_t)(*(in++)) << 32;
- value |= (uint64_t)(*(in++)) << 40;
- value |= (uint64_t)(*(in++)) << 48;
- value |= (uint64_t)(*(in++)) << 56;
- return value;
- }
-}
-#endif
-
-/* Guarantees that there are at least n_bits + 1 bits in accumulator.
- Precondition: accumulator contains at least 1 bit.
- n_bits should be in the range [1..24] for regular build. For portable
- non-64-bit little endian build only 16 bits are safe to request. */
-static BROTLI_INLINE void BrotliFillBitWindow(
- BrotliBitReader* const br, uint32_t n_bits) {
-#if (BROTLI_64_BITS)
- if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
- if (br->bit_pos_ >= 56) {
- br->val_ >>= 56;
- br->bit_pos_ ^= 56; /* here same as -= 56 because of the if condition */
- br->val_ |= BrotliLoad64LE(br->next_in) << 8;
- br->avail_in -= 7;
- br->next_in += 7;
- }
- } else if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 16)) {
- if (br->bit_pos_ >= 48) {
- br->val_ >>= 48;
- br->bit_pos_ ^= 48; /* here same as -= 48 because of the if condition */
- br->val_ |= BrotliLoad64LE(br->next_in) << 16;
- br->avail_in -= 6;
- br->next_in += 6;
- }
- } else {
- if (br->bit_pos_ >= 32) {
- br->val_ >>= 32;
- br->bit_pos_ ^= 32; /* here same as -= 32 because of the if condition */
- br->val_ |= ((uint64_t)BrotliLoad32LE(br->next_in)) << 32;
- br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
- br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
- }
- }
-#else
- if (!BROTLI_ALIGNED_READ && IS_CONSTANT(n_bits) && (n_bits <= 8)) {
- if (br->bit_pos_ >= 24) {
- br->val_ >>= 24;
- br->bit_pos_ ^= 24; /* here same as -= 24 because of the if condition */
- br->val_ |= BrotliLoad32LE(br->next_in) << 8;
- br->avail_in -= 3;
- br->next_in += 3;
- }
- } else {
- if (br->bit_pos_ >= 16) {
- br->val_ >>= 16;
- br->bit_pos_ ^= 16; /* here same as -= 16 because of the if condition */
- br->val_ |= ((uint32_t)BrotliLoad16LE(br->next_in)) << 16;
- br->avail_in -= BROTLI_SHORT_FILL_BIT_WINDOW_READ;
- br->next_in += BROTLI_SHORT_FILL_BIT_WINDOW_READ;
- }
- }
-#endif
-}
-
-/* Mosltly 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);
-}
-
-/* Pulls one byte of input to accumulator. */
-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;
-#else
- br->val_ |= ((uint32_t)*br->next_in) << 24;
-#endif
- br->bit_pos_ -= 8;
- --br->avail_in;
- ++br->next_in;
- return BROTLI_TRUE;
-}
-
-/* Returns currently available bits.
- The number of valid bits could be calclulated by BrotliGetAvailableBits. */
-static BROTLI_INLINE reg_t BrotliGetBitsUnmasked(BrotliBitReader* const br) {
- 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);
-}
-
-/* Returns the specified number of bits from br without advancing bit pos. */
-static BROTLI_INLINE uint32_t BrotliGetBits(
- BrotliBitReader* const br, uint32_t n_bits) {
- BrotliFillBitWindow(br, n_bits);
- return (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(n_bits);
-}
-
-/* Tries to peek the specified amount of bits. Returns 0, 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;
-}
-
-/* Advances the bit pos by n_bits. */
-static BROTLI_INLINE void BrotliDropBits(
- 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;
-}
-
-/* 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",
- (int)br->avail_in, (int)br->bit_pos_, n_bits, (int)*val));
- BrotliDropBits(br, n_bits);
-}
-
-/* Reads the specified number of bits from br and advances the bit pos.
- Assumes that there is enough input to perform BrotliFillBitWindow. */
-static BROTLI_INLINE uint32_t BrotliReadBits(
- 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 0, 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;
- }
- }
- BrotliTakeBits(br, n_bits, val);
- 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;
- uint32_t pad_bits = 0;
- if (pad_bits_count != 0) {
- BrotliTakeBits(br, pad_bits_count, &pad_bits);
- }
- return TO_BROTLI_BOOL(pad_bits == 0);
-}
-
-/* Peeks a byte at specified offset.
- Precondition: bit reader is parked to a byte boundary.
- Returns -1 if operation is not feasible. */
-static BROTLI_INLINE int BrotliPeekByte(BrotliBitReader* br, size_t offset) {
- uint32_t available_bits = BrotliGetAvailableBits(br);
- size_t bytes_left = available_bits >> 3;
- BROTLI_DCHECK((available_bits & 7) == 0);
- if (offset < bytes_left) {
- return (BrotliGetBitsUnmasked(br) >> (unsigned)(offset << 3)) & 0xFF;
- }
- offset -= bytes_left;
- if (offset < br->avail_in) {
- return br->next_in[offset];
- }
- return -1;
-}
-
-/* Copies remaining input bytes stored in the bit reader to the output. Value
- num may not be larger than BrotliGetRemainingBytes. The bit reader must be
- warmed up again after this. */
-static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
- BrotliBitReader* br, size_t num) {
- while (BrotliGetAvailableBits(br) >= 8 && num > 0) {
- *dest = (uint8_t)BrotliGetBitsUnmasked(br);
- BrotliDropBits(br, 8);
- ++dest;
- --num;
- }
- memcpy(dest, br->next_in, num);
- br->avail_in -= num;
- br->next_in += num;
-}
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
-
-#endif /* BROTLI_DEC_BIT_READER_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/context.h b/BaseTools/Source/C/BrotliCompress/dec/context.h deleted file mode 100644 index d4e7d866a6..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/context.h +++ /dev/null @@ -1,251 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Lookup table to map the previous two bytes to a context id.
-
- There are four different context modeling modes defined here:
- CONTEXT_LSB6: context id is the least significant 6 bits of the last byte,
- CONTEXT_MSB6: context id is the most significant 6 bits of the last byte,
- CONTEXT_UTF8: second-order context model tuned for UTF8-encoded text,
- CONTEXT_SIGNED: second-order context model tuned for signed integers.
-
- The context id for the UTF8 context model is calculated as follows. If p1
- and p2 are the previous two bytes, we calculate the context as
-
- context = kContextLookup[p1] | kContextLookup[p2 + 256].
-
- If the previous two bytes are ASCII characters (i.e. < 128), this will be
- equivalent to
-
- context = 4 * context1(p1) + context2(p2),
-
- where context1 is based on the previous byte in the following way:
-
- 0 : non-ASCII control
- 1 : \t, \n, \r
- 2 : space
- 3 : other punctuation
- 4 : " '
- 5 : %
- 6 : ( < [ {
- 7 : ) > ] }
- 8 : , ; :
- 9 : .
- 10 : =
- 11 : number
- 12 : upper-case vowel
- 13 : upper-case consonant
- 14 : lower-case vowel
- 15 : lower-case consonant
-
- and context2 is based on the second last byte:
-
- 0 : control, space
- 1 : punctuation
- 2 : upper-case letter, number
- 3 : lower-case letter
-
- If the last byte is ASCII, and the second last byte is not (in a valid UTF8
- stream it will be a continuation byte, value between 128 and 191), the
- context is the same as if the second last byte was an ASCII control or space.
-
- If the last byte is a UTF8 lead byte (value >= 192), then the next byte will
- be a continuation byte and the context id is 2 or 3 depending on the LSB of
- the last byte and to a lesser extent on the second last byte if it is ASCII.
-
- If the last byte is a UTF8 continuation byte, the second last byte can be:
- - continuation byte: the next byte is probably ASCII or lead byte (assuming
- 4-byte UTF8 characters are rare) and the context id is 0 or 1.
- - lead byte (192 - 207): next byte is ASCII or lead byte, context is 0 or 1
- - lead byte (208 - 255): next byte is continuation byte, context is 2 or 3
-
- The possible value combinations of the previous two bytes, the range of
- context ids and the type of the next byte is summarized in the table below:
-
- |--------\-----------------------------------------------------------------|
- | \ Last byte |
- | Second \---------------------------------------------------------------|
- | last byte \ ASCII | cont. byte | lead byte |
- | \ (0-127) | (128-191) | (192-) |
- |=============|===================|=====================|==================|
- | ASCII | next: ASCII/lead | not valid | next: cont. |
- | (0-127) | context: 4 - 63 | | context: 2 - 3 |
- |-------------|-------------------|---------------------|------------------|
- | cont. byte | next: ASCII/lead | next: ASCII/lead | next: cont. |
- | (128-191) | context: 4 - 63 | context: 0 - 1 | context: 2 - 3 |
- |-------------|-------------------|---------------------|------------------|
- | lead byte | not valid | next: ASCII/lead | not valid |
- | (192-207) | | context: 0 - 1 | |
- |-------------|-------------------|---------------------|------------------|
- | lead byte | not valid | next: cont. | not valid |
- | (208-) | | context: 2 - 3 | |
- |-------------|-------------------|---------------------|------------------|
-
- The context id for the signed context mode is calculated as:
-
- context = (kContextLookup[512 + p1] << 3) | kContextLookup[512 + p2].
-
- For any context modeling modes, the context ids can be calculated by |-ing
- together two lookups from one table using context model dependent offsets:
-
- context = kContextLookup[offset1 + p1] | kContextLookup[offset2 + p2].
-
- where offset1 and offset2 are dependent on the context mode.
-*/
-
-#ifndef BROTLI_DEC_CONTEXT_H_
-#define BROTLI_DEC_CONTEXT_H_
-
-#include "../common/types.h"
-
-enum ContextType {
- CONTEXT_LSB6 = 0,
- CONTEXT_MSB6 = 1,
- CONTEXT_UTF8 = 2,
- CONTEXT_SIGNED = 3
-};
-
-/* Common context lookup table for all context modes. */
-static const uint8_t kContextLookup[1792] = {
- /* CONTEXT_UTF8, last byte. */
- /* ASCII range. */
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 0, 4, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
- 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
- 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
- 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
- 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
- 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12, 0,
- /* UTF8 continuation byte range. */
- 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
- 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
- 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
- 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
- /* UTF8 lead byte range. */
- 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
- 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
- 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
- 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
- /* CONTEXT_UTF8 second last byte. */
- /* ASCII range. */
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
- 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
- 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,
- /* UTF8 continuation byte range. */
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- /* UTF8 lead byte range. */
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- /* CONTEXT_SIGNED, second last byte. */
- 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
- 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
- 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
- 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
- 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7,
- /* CONTEXT_SIGNED, last byte, same as the above values shifted by 3 bits. */
- 0, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
- 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
- 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
- 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
- 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
- 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
- 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
- 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
- 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
- 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
- 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
- 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 56,
- /* CONTEXT_LSB6, last byte. */
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
- 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
- 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
- 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
- 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
- 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
- 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
- 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
- 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
- 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
- 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
- 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
- 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
- /* CONTEXT_MSB6, last byte. */
- 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
- 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7,
- 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 11, 11,
- 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15,
- 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19,
- 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23,
- 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27,
- 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 31, 31, 31, 31,
- 32, 32, 32, 32, 33, 33, 33, 33, 34, 34, 34, 34, 35, 35, 35, 35,
- 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 38, 38, 39, 39, 39, 39,
- 40, 40, 40, 40, 41, 41, 41, 41, 42, 42, 42, 42, 43, 43, 43, 43,
- 44, 44, 44, 44, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47,
- 48, 48, 48, 48, 49, 49, 49, 49, 50, 50, 50, 50, 51, 51, 51, 51,
- 52, 52, 52, 52, 53, 53, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55,
- 56, 56, 56, 56, 57, 57, 57, 57, 58, 58, 58, 58, 59, 59, 59, 59,
- 60, 60, 60, 60, 61, 61, 61, 61, 62, 62, 62, 62, 63, 63, 63, 63,
- /* CONTEXT_{M,L}SB6, second last byte, */
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
-};
-
-static const int kContextLookupOffsets[8] = {
- /* CONTEXT_LSB6 */
- 1024, 1536,
- /* CONTEXT_MSB6 */
- 1280, 1536,
- /* CONTEXT_UTF8 */
- 0, 256,
- /* CONTEXT_SIGNED */
- 768, 512,
-};
-
-#endif /* BROTLI_DEC_CONTEXT_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/decode.c b/BaseTools/Source/C/BrotliCompress/dec/decode.c deleted file mode 100644 index 0b3eca3644..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/decode.c +++ /dev/null @@ -1,2347 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-#include "./decode.h"
-
-#ifdef __ARM_NEON__
-#include <arm_neon.h>
-#endif
-
-#include <stdlib.h> /* free, malloc */
-#include <string.h> /* memcpy, memset */
-
-#include "../common/constants.h"
-#include "../common/dictionary.h"
-#include "./bit_reader.h"
-#include "./context.h"
-#include "./huffman.h"
-#include "./port.h"
-#include "./prefix.h"
-#include "./state.h"
-#include "./transform.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-#define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE)
-
-#define BROTLI_LOG_UINT(name) \
- BROTLI_LOG(("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)))
-#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \
- BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \
- (unsigned long)(idx), (unsigned long)array_name[idx]))
-
-#define HUFFMAN_TABLE_BITS 8U
-#define HUFFMAN_TABLE_MASK 0xff
-
-static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = {
- 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
-};
-
-/* Static prefix code for the complex code length code lengths. */
-static const uint8_t kCodeLengthPrefixLength[16] = {
- 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4,
-};
-
-static const uint8_t kCodeLengthPrefixValue[16] = {
- 0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,
-};
-
-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;
- }
- BrotliDecoderStateInitWithCustomAllocators(
- state, alloc_func, free_func, opaque);
- state->error_code = BROTLI_DECODER_NO_ERROR;
- 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;
- }
-}
-
-/* Decodes a number in the range [9..24], by reading 1 - 7 bits.
- Precondition: bit-reader accumulator has at least 7 bits. */
-static uint32_t DecodeWindowBits(BrotliBitReader* br) {
- uint32_t n;
- BrotliTakeBits(br, 1, &n);
- if (n == 0) {
- return 16;
- }
- BrotliTakeBits(br, 3, &n);
- if (n != 0) {
- return 17 + n;
- }
- BrotliTakeBits(br, 3, &n);
- if (n != 0) {
- return 8 + n;
- }
- return 17;
-}
-
-static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) {
-#if defined(__ARM_NEON__)
- vst1q_u8(dst, vld1q_u8(src));
-#else
- uint32_t buffer[4];
- memcpy(buffer, src, 16);
- memcpy(dst, buffer, 16);
-#endif
-}
-
-/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
-static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8(
- BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) {
- uint32_t bits;
- switch (s->substate_decode_uint8) {
- case BROTLI_STATE_DECODE_UINT8_NONE:
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (bits == 0) {
- *value = 0;
- return BROTLI_DECODER_SUCCESS;
- }
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_DECODE_UINT8_SHORT:
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) {
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT;
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (bits == 0) {
- *value = 1;
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
- return BROTLI_DECODER_SUCCESS;
- }
- /* Use output value as a temporary storage. It MUST be persisted. */
- *value = bits;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_DECODE_UINT8_LONG:
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) {
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG;
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- *value = (1U << *value) + bits;
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
- return BROTLI_DECODER_SUCCESS;
-
- default:
- return
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
- }
-}
-
-/* Decodes a metablock length and flags by reading 2 - 31 bits. */
-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;
- }
- s->is_last_metablock = (uint8_t)bits;
- s->meta_block_remaining_len = 0;
- s->is_uncompressed = 0;
- s->is_metadata = 0;
- if (!s->is_last_metablock) {
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
- break;
- }
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_METABLOCK_HEADER_EMPTY:
- if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (bits) {
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_DECODER_SUCCESS;
- }
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_METABLOCK_HEADER_NIBBLES:
- if (!BrotliSafeReadBits(br, 2, &bits)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- s->size_nibbles = (uint8_t)(bits + 4);
- s->loop_counter = 0;
- if (bits == 3) {
- s->is_metadata = 1;
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_RESERVED;
- break;
- }
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_METABLOCK_HEADER_SIZE:
- i = s->loop_counter;
- for (; i < s->size_nibbles; ++i) {
- if (!BrotliSafeReadBits(br, 4, &bits)) {
- s->loop_counter = i;
- return BROTLI_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);
- }
- s->meta_block_remaining_len |= (int)(bits << (i * 4));
- }
- s->substate_metablock_header =
- BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED:
- if (!s->is_last_metablock) {
- if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- s->is_uncompressed = (uint8_t)bits;
- }
- ++s->meta_block_remaining_len;
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_DECODER_SUCCESS;
-
- case BROTLI_STATE_METABLOCK_HEADER_RESERVED:
- if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (bits != 0) {
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED);
- }
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_METABLOCK_HEADER_BYTES:
- if (!BrotliSafeReadBits(br, 2, &bits)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (bits == 0) {
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_DECODER_SUCCESS;
- }
- s->size_nibbles = (uint8_t)bits;
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA;
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_METABLOCK_HEADER_METADATA:
- i = s->loop_counter;
- for (; i < s->size_nibbles; ++i) {
- if (!BrotliSafeReadBits(br, 8, &bits)) {
- s->loop_counter = i;
- return BROTLI_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);
- }
- s->meta_block_remaining_len |= (int)(bits << (i * 8));
- }
- ++s->meta_block_remaining_len;
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_DECODER_SUCCESS;
-
- default:
- return
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
- }
- }
-}
-
-/* Decodes the Huffman code.
- This method doesn't read data from the bit reader, BUT drops the amount of
- bits that correspond to the decoded symbol.
- bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */
-static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits,
- const HuffmanCode* table,
- BrotliBitReader* br) {
- table += bits & HUFFMAN_TABLE_MASK;
- if (table->bits > HUFFMAN_TABLE_BITS) {
- uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS;
- BrotliDropBits(br, HUFFMAN_TABLE_BITS);
- table += table->value;
- table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits);
- }
- BrotliDropBits(br, table->bits);
- return table->value;
-}
-
-/* Reads and decodes the next Huffman code from bit-stream.
- This method peeks 16 bits of input and drops 0 - 15 of them. */
-static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table,
- BrotliBitReader* br) {
- return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br);
-}
-
-/* Same as DecodeSymbol, but it is known that there is less than 15 bits of
- input are currently available. */
-static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol(
- const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
- uint32_t val;
- uint32_t available_bits = BrotliGetAvailableBits(br);
- if (available_bits == 0) {
- if (table->bits == 0) {
- *result = table->value;
- return BROTLI_TRUE;
- }
- return BROTLI_FALSE; /* No valid bits at all. */
- }
- val = (uint32_t)BrotliGetBitsUnmasked(br);
- table += val & HUFFMAN_TABLE_MASK;
- if (table->bits <= HUFFMAN_TABLE_BITS) {
- if (table->bits <= available_bits) {
- BrotliDropBits(br, table->bits);
- *result = table->value;
- return BROTLI_TRUE;
- } else {
- return BROTLI_FALSE; /* Not enough bits for the first level. */
- }
- }
- if (available_bits <= HUFFMAN_TABLE_BITS) {
- return BROTLI_FALSE; /* Not enough bits to move to the second level. */
- }
-
- /* Speculatively drop HUFFMAN_TABLE_BITS. */
- val = (val & BitMask(table->bits)) >> HUFFMAN_TABLE_BITS;
- available_bits -= HUFFMAN_TABLE_BITS;
- table += table->value + val;
- if (available_bits < table->bits) {
- return BROTLI_FALSE; /* Not enough bits for the second level. */
- }
-
- BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits);
- *result = table->value;
- return BROTLI_TRUE;
-}
-
-static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol(
- const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
- uint32_t val;
- if (PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {
- *result = DecodeSymbol(val, table, br);
- return BROTLI_TRUE;
- }
- return SafeDecodeSymbol(table, br, result);
-}
-
-/* Makes a look-up in first level Huffman table. Peeks 8 bits. */
-static BROTLI_INLINE void PreloadSymbol(int safe,
- const HuffmanCode* table,
- BrotliBitReader* br,
- uint32_t* bits,
- uint32_t* value) {
- if (safe) {
- return;
- }
- table += BrotliGetBits(br, HUFFMAN_TABLE_BITS);
- *bits = table->bits;
- *value = table->value;
-}
-
-/* Decodes the next Huffman code using data prepared by PreloadSymbol.
- Reads 0 - 15 bits. Also peeks 8 following bits. */
-static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table,
- BrotliBitReader* br,
- uint32_t* bits,
- uint32_t* value) {
- uint32_t result = *value;
- if (PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {
- uint32_t val = BrotliGet16BitsUnmasked(br);
- const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value;
- uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS));
- BrotliDropBits(br, HUFFMAN_TABLE_BITS);
- ext += (val >> HUFFMAN_TABLE_BITS) & mask;
- BrotliDropBits(br, ext->bits);
- result = ext->value;
- } else {
- BrotliDropBits(br, *bits);
- }
- PreloadSymbol(0, table, br, bits, value);
- return result;
-}
-
-static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) {
- uint32_t result = 0;
- while (x) {
- x >>= 1;
- ++result;
- }
- return result;
-}
-
-/* Reads (s->symbol + 1) symbols.
- Totally 1..4 symbols are read, 1..10 bits each.
- The list of symbols MUST NOT contain duplicates.
- */
-static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols(
- uint32_t alphabet_size, BrotliDecoderState* s) {
- /* max_bits == 1..10; symbol == 0..3; 1..40 bits will be read. */
- BrotliBitReader* br = &s->br;
- uint32_t max_bits = Log2Floor(alphabet_size - 1);
- uint32_t i = s->sub_loop_counter;
- uint32_t num_symbols = s->symbol;
- while (i <= num_symbols) {
- uint32_t v;
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) {
- s->sub_loop_counter = i;
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ;
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (v >= alphabet_size) {
- 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 corredponding index-chain
- D) reduce the huffman space
- E) update the histogram
- */
-static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len,
- uint32_t* symbol, uint32_t* repeat, uint32_t* space,
- uint32_t* prev_code_len, uint16_t* symbol_lists,
- uint16_t* code_length_histo, int* next_symbol) {
- *repeat = 0;
- if (code_len != 0) { /* code_len == 1..15 */
- symbol_lists[next_symbol[code_len]] = (uint16_t)(*symbol);
- next_symbol[code_len] = (int)(*symbol);
- *prev_code_len = code_len;
- *space -= 32768U >> code_len;
- code_length_histo[code_len]++;
- BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n", *symbol, 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 alphapet)
- 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",
- *symbol, *symbol + repeat_delta - 1, *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 (!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);
- p += BrotliGetBitsUnmasked(br) &
- BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
- BrotliDropBits(br, p->bits); /* Use 1..5 bits */
- code_len = p->value; /* code_len == 0..17 */
- if (code_len < 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;
- while (s->symbol < alphabet_size && s->space > 0) {
- const HuffmanCode* p = s->table;
- uint32_t code_len;
- uint32_t bits = 0;
- uint32_t available_bits = BrotliGetAvailableBits(br);
- if (available_bits != 0) {
- bits = (uint32_t)BrotliGetBitsUnmasked(br);
- }
- p += bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
- if (p->bits > available_bits) goto pullMoreInput;
- code_len = p->value; /* code_len == 0..17 */
- if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
- BrotliDropBits(br, p->bits);
- ProcessSingleCodeLength(code_len, &s->symbol, &s->repeat, &s->space,
- &s->prev_code_len, s->symbol_lists, s->code_length_histo,
- s->next_symbol);
- } else { /* code_len == 16..17, extra_bits == 2..3 */
- uint32_t extra_bits = code_len - 14U;
- uint32_t repeat_delta = (bits >> p->bits) & BitMask(extra_bits);
- if (available_bits < p->bits + extra_bits) goto pullMoreInput;
- BrotliDropBits(br, p->bits + extra_bits);
- ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,
- &s->symbol, &s->repeat, &s->space, &s->prev_code_len,
- &s->repeat_code_len, s->symbol_lists, s->code_length_histo,
- s->next_symbol);
- }
- continue;
-
-pullMoreInput:
- if (!BrotliPullByte(br)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- }
- 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 (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;
-}
-
-/* Decodes the Huffman tables.
- There are 2 scenarios:
- A) Huffman code contains only few symbols (1..4). Those symbols are read
- directly; their code lengths are defined by the number of symbols.
- For this scenario 4 - 45 bits will be read.
-
- B) 2-phase decoding:
- B.1) Small Huffman table is decoded; it is specified with code lengths
- encoded with predefined entropy code. 32 - 74 bits are used.
- B.2) Decoded table is used to decode code lengths of symbols in resulting
- Huffman table. In worst case 3520 bits are read.
-*/
-static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size,
- HuffmanCode* table,
- uint32_t* opt_table_size,
- BrotliDecoderState* s) {
- BrotliBitReader* br = &s->br;
- /* Unnecessary masking, but might be good for safety. */
- alphabet_size &= 0x3ff;
- /* State machine */
- switch (s->substate_huffman) {
- case BROTLI_STATE_HUFFMAN_NONE:
- if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) {
- return BROTLI_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;
- goto Complex;
- }
- /* No break, transit to the next state. */
-
- case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE:
- /* Read symbols, codes & code lengths directly. */
- if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE;
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- s->sub_loop_counter = 0;
- /* No break, transit to the next state. */
- case BROTLI_STATE_HUFFMAN_SIMPLE_READ: {
- BrotliDecoderErrorCode result =
- ReadSimpleHuffmanSymbols(alphabet_size, s);
- if (result != BROTLI_DECODER_SUCCESS) {
- return result;
- }
- /* No break, transit to the next state. */
- }
- case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: {
- uint32_t table_size;
- if (s->symbol == 3) {
- uint32_t bits;
- if (!BrotliSafeReadBits(br, 1, &bits)) {
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD;
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- s->symbol += bits;
- }
- BROTLI_LOG_UINT(s->symbol);
- table_size = BrotliBuildSimpleHuffmanTable(
- table, HUFFMAN_TABLE_BITS, s->symbols_lists_array, s->symbol);
- if (opt_table_size) {
- *opt_table_size = table_size;
- }
- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
- return BROTLI_DECODER_SUCCESS;
- }
-
-Complex: /* 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[(int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1)] = 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;
- /* No break, transit to the next state. */
- }
- case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: {
- uint32_t table_size;
- BrotliDecoderErrorCode result = ReadSymbolCodeLengths(alphabet_size, s);
- if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
- result = SafeReadSymbolCodeLengths(alphabet_size, s);
- }
- if (result != BROTLI_DECODER_SUCCESS) {
- return result;
- }
-
- if (s->space != 0) {
- BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", s->space));
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE);
- }
- 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;
- }
-
- 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;
- 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;
- 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;
- }
-}
-
-/* Transform:
- 1) initialize list L with values 0, 1,... 255
- 2) For each input element X:
- 2.1) let Y = L[X]
- 2.2) remove X-th element from L
- 2.3) prepend Y to L
- 2.4) append Y to output
-
- In most cases max(Y) <= 7, so most of L remains intact.
- To reduce the cost of initialization, we reuse L, remember the upper bound
- of Y values, and reinitialize only first elements in L.
-
- Most of input values are 0 and 1. To reduce number of branches, we replace
- inner for loop with do-while.
- */
-static BROTLI_NOINLINE void InverseMoveToFrontTransform(
- uint8_t* v, uint32_t v_len, BrotliDecoderState* state) {
- /* Reinitialize elements that could have been changed. */
- uint32_t i = 4;
- uint32_t upper_bound = state->mtf_upper_bound;
- uint8_t* mtf = &state->mtf[4]; /* Make mtf[-1] addressable. */
- /* Load endian-aware constant. */
- const uint8_t b0123[4] = {0, 1, 2, 3};
- uint32_t pattern;
- memcpy(&pattern, &b0123, 4);
-
- /* Initialize list using 4 consequent values pattern. */
- *(uint32_t*)mtf = pattern;
- do {
- pattern += 0x04040404; /* Advance all 4 values by 4. */
- *(uint32_t*)(mtf + i) = pattern;
- i += 4;
- } while (i <= upper_bound);
-
- /* Transform the input. */
- upper_bound = 0;
- for (i = 0; i < v_len; ++i) {
- int index = v[i];
- uint8_t value = mtf[index];
- upper_bound |= v[i];
- v[i] = value;
- mtf[-1] = value;
- do {
- index--;
- mtf[index + 1] = mtf[index];
- } while (index >= 0);
- }
- /* Remember amount of elements to be reinitialized. */
- state->mtf_upper_bound = upper_bound;
-}
-
-/* Decodes a series of Huffman table using ReadHuffmanCode function. */
-static BrotliDecoderErrorCode HuffmanTreeGroupDecode(
- HuffmanTreeGroup* group, BrotliDecoderState* s) {
- if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {
- s->next = group->codes;
- s->htree_index = 0;
- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP;
- }
- while (s->htree_index < group->num_htrees) {
- uint32_t table_size;
- BrotliDecoderErrorCode result =
- ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
- if (result != BROTLI_DECODER_SUCCESS) return result;
- group->htrees[s->htree_index] = s->next;
- s->next += table_size;
- ++s->htree_index;
- }
- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;
- return BROTLI_DECODER_SUCCESS;
-}
-
-/* Decodes a context map.
- Decoding is done in 4 phases:
- 1) Read auxiliary information (6..16 bits) and allocate memory.
- In case of trivial context map, decoding is finished at this phase.
- 2) Decode Huffman table using ReadHuffmanCode function.
- This table will be used for reading context map items.
- 3) Read context map items; "0" values could be run-length encoded.
- 4) Optionally, apply InverseMoveToFront transform to the resulting map.
- */
-static BrotliDecoderErrorCode DecodeContextMap(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;
-
- switch ((int)s->substate_context_map) {
- case BROTLI_STATE_CONTEXT_MAP_NONE:
- result = DecodeVarLenUint8(s, br, num_htrees);
- if (result != BROTLI_DECODER_SUCCESS) {
- return result;
- }
- (*num_htrees)++;
- s->context_index = 0;
- BROTLI_LOG_UINT(context_map_size);
- BROTLI_LOG_UINT(*num_htrees);
- *context_map_arg = (uint8_t*)BROTLI_ALLOC(s, (size_t)context_map_size);
- if (*context_map_arg == 0) {
- return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP);
- }
- if (*num_htrees <= 1) {
- memset(*context_map_arg, 0, (size_t)context_map_size);
- return BROTLI_DECODER_SUCCESS;
- }
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX;
- /* No break, continue to next state. */
- case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: {
- uint32_t bits;
- /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe
- to peek 4 bits ahead. */
- if (!BrotliSafeGetBits(br, 5, &bits)) {
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if ((bits & 1) != 0) { /* Use RLE for zeroes. */
- s->max_run_length_prefix = (bits >> 1) + 1;
- BrotliDropBits(br, 5);
- } else {
- s->max_run_length_prefix = 0;
- BrotliDropBits(br, 1);
- }
- BROTLI_LOG_UINT(s->max_run_length_prefix);
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN;
- /* No break, continue to next state. */
- }
- case BROTLI_STATE_CONTEXT_MAP_HUFFMAN:
- result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,
- s->context_map_table, NULL, s);
- if (result != BROTLI_DECODER_SUCCESS) return result;
- s->code = 0xFFFF;
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE;
- /* No break, continue to next state. */
- case BROTLI_STATE_CONTEXT_MAP_DECODE: {
- uint32_t context_index = s->context_index;
- uint32_t max_run_length_prefix = s->max_run_length_prefix;
- uint8_t* context_map = *context_map_arg;
- uint32_t code = s->code;
- if (code != 0xFFFF) {
- goto rleCode;
- }
- while (context_index < context_map_size) {
- if (!SafeReadSymbol(s->context_map_table, br, &code)) {
- s->code = 0xFFFF;
- s->context_index = context_index;
- return BROTLI_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;
- }
-rleCode:
- {
- 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);
- }
- do {
- context_map[context_index++] = 0;
- } while (--reps);
- }
- }
- /* No break, continue to next state. */
- }
- case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: {
- uint32_t bits;
- if (!BrotliSafeReadBits(br, 1, &bits)) {
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM;
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- if (bits != 0) {
- InverseMoveToFrontTransform(*context_map_arg, context_map_size, s);
- }
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;
- return BROTLI_DECODER_SUCCESS;
- }
- default:
- return
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
- }
-}
-
-/* Decodes a command or literal and updates block type ringbuffer.
- 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;
-
- /* Read 0..15 + 3..39 bits */
- if (!safe) {
- block_type = ReadSymbol(type_tree, br);
- s->block_length[tree_type] = ReadBlockLength(len_tree, br);
- } else {
- BrotliBitReaderState memento;
- BrotliBitReaderSaveState(br, &memento);
- if (!SafeReadSymbol(type_tree, br, &block_type)) return BROTLI_FALSE;
- if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) {
- s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
- BrotliBitReaderRestoreState(br, &memento);
- return BROTLI_FALSE;
- }
- }
-
- if (block_type == 1) {
- block_type = ringbuffer[1] + 1;
- } else if (block_type == 0) {
- block_type = ringbuffer[0];
- } else {
- block_type -= 2;
- }
- if (block_type >= max_block_type) {
- block_type -= max_block_type;
- }
- ringbuffer[0] = ringbuffer[1];
- ringbuffer[1] = block_type;
- return BROTLI_TRUE;
-}
-
-static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(
- BrotliDecoderState* s) {
- size_t i;
- for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0;
- for (i = 0; i < s->num_block_types[0]; i++) {
- size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS;
- size_t error = 0;
- size_t sample = s->context_map[offset];
- size_t j;
- for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) {
- 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;
- s->context_map_slice = s->context_map + context_offset;
- trivial = s->trivial_literal_contexts[block_type >> 5];
- s->trivial_literal_context = (trivial >> (block_type & 31)) & 1;
- s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]];
- context_mode = s->context_modes[block_type];
- s->context_lookup1 = &kContextLookup[kContextLookupOffsets[context_mode]];
- s->context_lookup2 = &kContextLookup[kContextLookupOffsets[context_mode + 1]];
-}
-
-/* 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;
-}
-
-static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer(
- BrotliDecoderState* s, size_t* available_out, uint8_t** next_out,
- size_t* total_out) {
- 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);
- }
- 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) {
- return BROTLI_DECODER_NEEDS_MORE_OUTPUT;
- }
-
- if (s->pos >= s->ringbuffer_size) {
- s->pos -= s->ringbuffer_size;
- s->rb_roundtrips++;
- }
- return BROTLI_DECODER_SUCCESS;
-}
-
-/* Allocates ringbuffer.
-
- s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
- this function is called.
-
- Last two bytes of ringbuffer are initialized to 0, so context calculation
- could be done uniformly for the first two and all other positions.
-
- Custom dictionary, if any, is copied to the end of ringbuffer.
-*/
-static BROTLI_BOOL BROTLI_NOINLINE BrotliAllocateRingBuffer(
- BrotliDecoderState* s) {
- /* We need the slack region for the following reasons:
- - doing up to two 16-byte copies for fast backward copying
- - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */
- static const int kRingBufferWriteAheadSlack = 42;
- s->ringbuffer = (uint8_t*)BROTLI_ALLOC(s, (size_t)(s->ringbuffer_size +
- kRingBufferWriteAheadSlack));
- if (s->ringbuffer == 0) {
- return BROTLI_FALSE;
- }
-
- s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
-
- s->ringbuffer[s->ringbuffer_size - 2] = 0;
- s->ringbuffer[s->ringbuffer_size - 1] = 0;
-
- if (s->custom_dict) {
- memcpy(&s->ringbuffer[(-s->custom_dict_size) & s->ringbuffer_mask],
- s->custom_dict, (size_t)s->custom_dict_size);
- }
-
- return 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 (!s->ringbuffer && !BrotliAllocateRingBuffer(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 ringbuffer. */
- BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes);
- s->pos += nbytes;
- s->meta_block_remaining_len -= nbytes;
- if (s->pos < s->ringbuffer_size) {
- if (s->meta_block_remaining_len == 0) {
- return BROTLI_DECODER_SUCCESS;
- }
- return BROTLI_DECODER_NEEDS_MORE_INPUT;
- }
- s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE;
- /* No break, continue to next state */
- }
- case BROTLI_STATE_UNCOMPRESSED_WRITE: {
- BrotliDecoderErrorCode result =
- WriteRingBuffer(s, available_out, next_out, total_out);
- if (result != BROTLI_DECODER_SUCCESS) {
- return result;
- }
- s->max_distance = s->max_backward_distance;
- s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;
- break;
- }
- }
- }
- BROTLI_DCHECK(0); /* Unreachable */
-}
-
-BROTLI_BOOL BrotliDecompressedSize(size_t encoded_size,
- const uint8_t* encoded_buffer,
- size_t* decoded_size) {
- size_t total_size = 0;
- BrotliDecoderState s;
- BrotliBitReader* br;
- BrotliDecoderStateInit(&s);
- br = &s.br;
- *decoded_size = 0;
- br->next_in = encoded_buffer;
- br->avail_in = encoded_size;
- if (!BrotliWarmupBitReader(br)) return BROTLI_FALSE;
- DecodeWindowBits(br);
- while (1) {
- size_t block_size;
- if (DecodeMetaBlockLength(&s, br) != BROTLI_DECODER_SUCCESS) {
- return BROTLI_FALSE;
- }
- block_size = (size_t)s.meta_block_remaining_len;
- if (!s.is_metadata) {
- if ((block_size + total_size) < total_size) return BROTLI_FALSE;
- total_size += block_size;
- }
- if (s.is_last_metablock) {
- *decoded_size = total_size;
- return BROTLI_TRUE;
- }
- if (!s.is_uncompressed && !s.is_metadata) return BROTLI_FALSE;
- if (!BrotliJumpToByteBoundary(br)) return BROTLI_FALSE;
- BrotliBitReaderUnload(br);
- if (br->avail_in < block_size) return BROTLI_FALSE;
- br->avail_in -= block_size;
- br->next_in += block_size;
- if (!BrotliWarmupBitReader(br)) return BROTLI_FALSE;
- }
-}
-
-/* Calculates the smallest feasible ring buffer.
-
- If we know the data size is small, do not allocate more ringbuffer
- size than needed to reduce memory usage.
-
- When this method is called, metablock size and flags MUST be decoded.
-*/
-static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(
- BrotliDecoderState* s, BrotliBitReader* br) {
- BROTLI_BOOL is_last = TO_BROTLI_BOOL(s->is_last_metablock);
- int window_size = 1 << s->window_bits;
- s->ringbuffer_size = window_size;
-
- if (s->is_uncompressed) {
- int next_block_header =
- BrotliPeekByte(br, (size_t)s->meta_block_remaining_len);
- if (next_block_header != -1) { /* Peek succeeded */
- if ((next_block_header & 3) == 3) { /* ISLAST and ISEMPTY */
- is_last = BROTLI_TRUE;
- }
- }
- }
-
- /* We need at least 2 bytes of ring buffer size to get the last two
- bytes for context from there */
- if (is_last) {
- int min_size_x2 = (s->meta_block_remaining_len + s->custom_dict_size) * 2;
- while (s->ringbuffer_size >= min_size_x2 && s->ringbuffer_size > 32) {
- s->ringbuffer_size >>= 1;
- }
- }
-
- s->ringbuffer_mask = s->ringbuffer_size - 1;
-}
-
-/* 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;
- }
- s->context_modes[i] = (uint8_t)(bits << 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];
- } else {
- int distance_code = s->distance_code << 1;
- /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: */
- /* 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */
- const uint32_t kDistanceShortCodeIndexOffset = 0xaaafff1b;
- /* kDistanceShortCodeValueOffset has 2-bit values from LSB: */
- /*-0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */
- const uint32_t kDistanceShortCodeValueOffset = 0xfa5fa500;
- int v = (s->dist_rb_idx +
- (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3;
- s->distance_code = s->dist_rb[v];
- v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3;
- if ((distance_code & 0x3) != 0) {
- s->distance_code += v;
- } else {
- s->distance_code -= v;
- if (s->distance_code <= 0) {
- /* A huge distance will cause a BROTLI_FAILURE() soon. */
- /* This is a little faster than failing here. */
- s->distance_code = 0x0fffffff;
- }
- }
- }
-}
-
-static BROTLI_INLINE 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;
- }
- /* Convert the distance code to the actual distance by possibly */
- /* looking up past distances from the s->ringbuffer. */
- if ((s->distance_code & ~0xf) == 0) {
- TakeDistanceFromRingBuffer(s);
- --s->block_length[2];
- return BROTLI_TRUE;
- }
- distval = s->distance_code - (int)s->num_direct_distance_codes;
- if (distval >= 0) {
- uint32_t nbits;
- int postfix;
- int offset;
- if (!safe && (s->distance_postfix_bits == 0)) {
- nbits = ((uint32_t)distval >> 1) + 1;
- offset = ((2 + (distval & 1)) << nbits) - 4;
- s->distance_code = (int)s->num_direct_distance_codes + offset +
- (int)BrotliReadBits(br, nbits);
- } else {
- /* This branch also works well when s->distance_postfix_bits == 0 */
- uint32_t bits;
- postfix = distval & s->distance_postfix_mask;
- distval >>= s->distance_postfix_bits;
- nbits = ((uint32_t)distval >> 1) + 1;
- if (safe) {
- if (!SafeReadBits(br, nbits, &bits)) {
- s->distance_code = -1; /* Restore precondition. */
- BrotliBitReaderRestoreState(br, &memento);
- return BROTLI_FALSE;
- }
- } else {
- bits = BrotliReadBits(br, nbits);
- }
- offset = ((2 + (distval & 1)) << nbits) - 4;
- s->distance_code = (int)s->num_direct_distance_codes +
- ((offset + (int)bits) << s->distance_postfix_bits) + postfix;
- }
- }
- 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 (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 (PREDICT_FALSE(s->block_length[1] == 0)) {
- BROTLI_SAFE(DecodeCommandBlockSwitch(s));
- goto CommandBegin;
- }
- /* Read the insert/copy length in the command */
- BROTLI_SAFE(ReadCommand(s, br, &i));
- BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",
- pos, i, s->copy_length));
- if (i == 0) {
- goto CommandPostDecodeLiterals;
- }
- s->meta_block_remaining_len -= i;
-
-CommandInner:
- if (safe) {
- s->state = BROTLI_STATE_COMMAND_INNER;
- }
- /* Read the literals in the command */
- if (s->trivial_literal_context) {
- 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 (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 (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 (PREDICT_FALSE(s->block_length[0] == 0)) {
- BROTLI_SAFE(DecodeLiteralBlockSwitch(s));
- if (s->trivial_literal_context) goto CommandInner;
- }
- context = s->context_lookup1[p1] | s->context_lookup2[p2];
- BROTLI_LOG_UINT(context);
- hc = s->literal_hgroup.htrees[s->context_map_slice[context]];
- p2 = p1;
- if (!safe) {
- p1 = (uint8_t)ReadSymbol(hc, br);
- } else {
- uint32_t literal;
- if (!SafeReadSymbol(hc, br, &literal)) {
- result = BROTLI_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 (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 (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) {
- --s->dist_rb_idx;
- s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
- goto postReadDistance; /* We already have the implicit distance */
- }
- /* Read distance code in the command, unless it was implicitly zero. */
- if (PREDICT_FALSE(s->block_length[2] == 0)) {
- BROTLI_SAFE(DecodeDistanceBlockSwitch(s));
- }
- BROTLI_SAFE(ReadDistance(s, br));
-postReadDistance:
- BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",
- pos, s->distance_code));
- if (s->max_distance != s->max_backward_distance) {
- if (pos < s->max_backward_distance_minus_custom_dict_size) {
- s->max_distance = pos + s->custom_dict_size;
- } else {
- s->max_distance = s->max_backward_distance;
- }
- }
- i = s->copy_length;
- /* Apply copy of LZ77 back-reference, or static dictionary reference if
- the distance is larger than the max LZ77 distance */
- if (s->distance_code > s->max_distance) {
- if (i >= kBrotliMinDictionaryWordLength &&
- i <= kBrotliMaxDictionaryWordLength) {
- int offset = (int)kBrotliDictionaryOffsetsByLength[i];
- int word_id = s->distance_code - s->max_distance - 1;
- uint32_t shift = kBrotliDictionarySizeBitsByLength[i];
- int mask = (int)BitMask(shift);
- int word_idx = word_id & mask;
- int transform_idx = word_id >> shift;
- offset += word_idx * i;
- if (transform_idx < kNumTransforms) {
- const uint8_t* word = &kBrotliDictionary[offset];
- int len = i;
- if (transform_idx == 0) {
- memcpy(&s->ringbuffer[pos], word, (size_t)len);
- } else {
- len = TransformDictionaryWord(
- &s->ringbuffer[pos], word, len, transform_idx);
- }
- pos += len;
- s->meta_block_remaining_len -= len;
- if (pos >= s->ringbuffer_size) {
- /*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/
- s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;
- goto saveStateAndReturn;
- }
- } else {
- BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
- "len: %d bytes left: %d\n",
- pos, s->distance_code, i, s->meta_block_remaining_len));
- return BROTLI_FAILURE(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 ringbuffer allocation.
- Also, we have 16 short codes, that make these 16 bytes irrelevant
- in the ringbuffer. Let's copy over them as a first guess.
- */
- memmove16(copy_dst, copy_src);
- 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 (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;
- return result;
-}
-
-#undef BROTLI_SAFE
-
-static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands(
- BrotliDecoderState* s) {
- return ProcessCommandsInternal(0, s);
-}
-
-static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands(
- BrotliDecoderState* s) {
- return ProcessCommandsInternal(1, s);
-}
-
-BrotliDecoderResult BrotliDecoderDecompress(
- size_t encoded_size, const uint8_t* encoded_buffer, 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;
- BrotliDecoderStateInit(&s);
- result = BrotliDecoderDecompressStream(
- &s, &available_in, &next_in, &available_out, &next_out, &total_out);
- *decoded_size = total_out;
- BrotliDecoderStateCleanup(&s);
- if (result != BROTLI_DECODER_RESULT_SUCCESS) {
- result = BROTLI_DECODER_RESULT_ERROR;
- }
- return result;
-}
-
-/* Invariant: input stream is never overconsumed:
- * invalid input implies that the whole stream is invalid -> any amount of
- input could be read and discarded
- * when result is "needs more input", then at leat one more byte is REQUIRED
- to complete decoding; all input data MUST be consumed by decoder, so
- client could swap the input buffer
- * when result is "needs more output" decoder MUST ensure that it doesn't
- hold more than 7 bits in bit reader; this saves client from swapping input
- buffer ahead of time
- * when result is "success" decoder MUST return all unused data back to input
- buffer; this is possible because the invariant is hold on enter
-*/
-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;
- 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];
- }
- /* State machine */
- for (;;) {
- if (result != BROTLI_DECODER_SUCCESS) { /* Error, needs more input/output */
- if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
- if (s->ringbuffer != 0) { /* Proactively push output. */
- WriteRingBuffer(s, available_out, next_out, total_out);
- }
- if (s->buffer_length != 0) { /* Used with internal buffer. */
- if (br->avail_in == 0) { /* Successfully finished read transaction. */
- /* Accamulator contains less than 8 bits, because internal buffer
- is expanded byte-by-byte until it is enough to complete read. */
- s->buffer_length = 0;
- /* Switch to input stream and restart. */
- result = BROTLI_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;
- } else { /* Input stream doesn't contain enough input. */
- /* Copy tail to internal buffer and return. */
- *next_in = br->next_in;
- *available_in = br->avail_in;
- while (*available_in) {
- s->buffer.u8[s->buffer_length] = **next_in;
- s->buffer_length++;
- (*next_in)++;
- (*available_in)--;
- }
- break;
- }
- /* Unreachable. */
- }
-
- /* Fail or needs more output. */
-
- if (s->buffer_length != 0) {
- /* Just consumed the buffered input and produced some output. Otherwise
- it would result in "needs more input". Reset internal buffer.*/
- s->buffer_length = 0;
- } else {
- /* Using input stream in last iteration. When decoder switches to input
- stream it has less than 8 bits in accamulator, so it is safe to
- return unused accamulator bits there. */
- BrotliBitReaderUnload(br);
- *available_in = br->avail_in;
- *next_in = br->next_in;
- }
- break;
- }
- switch (s->state) {
- case BROTLI_STATE_UNINITED:
- /* Prepare to the first read. */
- if (!BrotliWarmupBitReader(br)) {
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;
- break;
- }
- /* Decode window size. */
- s->window_bits = DecodeWindowBits(br); /* Reads 1..7 bits. */
- BROTLI_LOG_UINT(s->window_bits);
- if (s->window_bits == 9) {
- /* Value 9 is reserved for future use. */
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
- break;
- }
- /* Maximum distance, see section 9.1. of the spec. */
- s->max_backward_distance = (1 << s->window_bits) - 16;
- /* Limit custom dictionary size. */
- if (s->custom_dict_size >= s->max_backward_distance) {
- s->custom_dict += s->custom_dict_size - s->max_backward_distance;
- s->custom_dict_size = s->max_backward_distance;
- }
- s->max_backward_distance_minus_custom_dict_size =
- s->max_backward_distance - s->custom_dict_size;
-
- /* Allocate memory for both block_type_trees and block_len_trees. */
- s->block_type_trees = (HuffmanCode*)BROTLI_ALLOC(s,
- sizeof(HuffmanCode) * 3 *
- (BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26));
- if (s->block_type_trees == 0) {
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES);
- break;
- }
- s->block_len_trees =
- s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258;
-
- s->state = BROTLI_STATE_METABLOCK_BEGIN;
- /* No break, continue to next state */
- case BROTLI_STATE_METABLOCK_BEGIN:
- BrotliDecoderStateMetablockBegin(s);
- BROTLI_LOG_UINT(s->pos);
- s->state = BROTLI_STATE_METABLOCK_HEADER;
- /* No break, continue to next state */
- case BROTLI_STATE_METABLOCK_HEADER:
- result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- BROTLI_LOG_UINT(s->is_last_metablock);
- BROTLI_LOG_UINT(s->meta_block_remaining_len);
- BROTLI_LOG_UINT(s->is_metadata);
- BROTLI_LOG_UINT(s->is_uncompressed);
- if (s->is_metadata || s->is_uncompressed) {
- if (!BrotliJumpToByteBoundary(br)) {
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1);
- break;
- }
- }
- if (s->is_metadata) {
- s->state = BROTLI_STATE_METADATA;
- break;
- }
- if (s->meta_block_remaining_len == 0) {
- s->state = BROTLI_STATE_METABLOCK_DONE;
- break;
- }
- if (!s->ringbuffer) {
- BrotliCalculateRingBufferSize(s, br);
- }
- if (s->is_uncompressed) {
- s->state = BROTLI_STATE_UNCOMPRESSED;
- break;
- }
- s->loop_counter = 0;
- s->state = BROTLI_STATE_HUFFMAN_CODE_0;
- break;
- case BROTLI_STATE_UNCOMPRESSED: {
- int bytes_copied = s->meta_block_remaining_len;
- result = CopyUncompressedBlockToOutput(
- available_out, next_out, total_out, s);
- bytes_copied -= s->meta_block_remaining_len;
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- s->state = BROTLI_STATE_METABLOCK_DONE;
- break;
- }
- case BROTLI_STATE_METADATA:
- for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {
- uint32_t bits;
- /* Read one byte and ignore it. */
- if (!BrotliSafeReadBits(br, 8, &bits)) {
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;
- break;
- }
- }
- if (result == BROTLI_DECODER_SUCCESS) {
- s->state = BROTLI_STATE_METABLOCK_DONE;
- }
- break;
- case BROTLI_STATE_HUFFMAN_CODE_0:
- if (s->loop_counter >= 3) {
- s->state = BROTLI_STATE_METABLOCK_HEADER_2;
- break;
- }
- /* Reads 1..11 bits. */
- result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]);
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- s->num_block_types[s->loop_counter]++;
- BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]);
- if (s->num_block_types[s->loop_counter] < 2) {
- s->loop_counter++;
- break;
- }
- s->state = BROTLI_STATE_HUFFMAN_CODE_1;
- /* No break, continue to next state */
- case BROTLI_STATE_HUFFMAN_CODE_1: {
- int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258;
- result = ReadHuffmanCode(s->num_block_types[s->loop_counter] + 2,
- &s->block_type_trees[tree_offset], NULL, s);
- if (result != BROTLI_DECODER_SUCCESS) break;
- s->state = BROTLI_STATE_HUFFMAN_CODE_2;
- /* No break, continue to next state */
- }
- case BROTLI_STATE_HUFFMAN_CODE_2: {
- int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
- result = ReadHuffmanCode(BROTLI_NUM_BLOCK_LEN_SYMBOLS,
- &s->block_len_trees[tree_offset], NULL, s);
- if (result != BROTLI_DECODER_SUCCESS) break;
- s->state = BROTLI_STATE_HUFFMAN_CODE_3;
- /* No break, continue to next state */
- }
- case BROTLI_STATE_HUFFMAN_CODE_3: {
- int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
- if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter],
- &s->block_len_trees[tree_offset], br)) {
- result = BROTLI_DECODER_NEEDS_MORE_INPUT;
- break;
- }
- BROTLI_LOG_UINT(s->block_length[s->loop_counter]);
- s->loop_counter++;
- s->state = BROTLI_STATE_HUFFMAN_CODE_0;
- break;
- }
- case BROTLI_STATE_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);
- BROTLI_LOG_UINT(s->num_direct_distance_codes);
- BROTLI_LOG_UINT(s->distance_postfix_bits);
- s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits);
- s->context_modes =
- (uint8_t*)BROTLI_ALLOC(s, (size_t)s->num_block_types[0]);
- if (s->context_modes == 0) {
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES);
- break;
- }
- s->loop_counter = 0;
- s->state = BROTLI_STATE_CONTEXT_MODES;
- /* No break, continue to next state */
- }
- case BROTLI_STATE_CONTEXT_MODES:
- result = ReadContextModes(s);
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- s->state = BROTLI_STATE_CONTEXT_MAP_1;
- /* No break, continue to next state */
- case BROTLI_STATE_CONTEXT_MAP_1:
- result = DecodeContextMap(
- s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS,
- &s->num_literal_htrees, &s->context_map, s);
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- DetectTrivialLiteralBlockTypes(s);
- s->state = BROTLI_STATE_CONTEXT_MAP_2;
- /* No break, continue to next state */
- case BROTLI_STATE_CONTEXT_MAP_2:
- {
- uint32_t num_distance_codes =
- s->num_direct_distance_codes + (48U << s->distance_postfix_bits);
- result = DecodeContextMap(
- s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS,
- &s->num_dist_htrees, &s->dist_context_map, s);
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- BrotliDecoderHuffmanTreeGroupInit(
- s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS,
- s->num_literal_htrees);
- BrotliDecoderHuffmanTreeGroupInit(
- s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS,
- s->num_block_types[1]);
- BrotliDecoderHuffmanTreeGroupInit(
- s, &s->distance_hgroup, num_distance_codes,
- s->num_dist_htrees);
- if (s->literal_hgroup.codes == 0 ||
- s->insert_copy_hgroup.codes == 0 ||
- s->distance_hgroup.codes == 0) {
- return SaveErrorCode(s,
- BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS));
- }
- }
- s->loop_counter = 0;
- s->state = BROTLI_STATE_TREE_GROUP;
- /* No break, continue to next state */
- case BROTLI_STATE_TREE_GROUP:
- {
- HuffmanTreeGroup* hgroup = NULL;
- switch (s->loop_counter) {
- case 0:
- hgroup = &s->literal_hgroup;
- break;
- case 1:
- hgroup = &s->insert_copy_hgroup;
- break;
- case 2:
- hgroup = &s->distance_hgroup;
- break;
- default:
- return SaveErrorCode(s, BROTLI_FAILURE(
- BROTLI_DECODER_ERROR_UNREACHABLE));
- }
- result = HuffmanTreeGroupDecode(hgroup, s);
- }
- if (result != BROTLI_DECODER_SUCCESS) break;
- s->loop_counter++;
- if (s->loop_counter >= 3) {
- PrepareLiteralDecoding(s);
- s->dist_context_map_slice = s->dist_context_map;
- s->htree_command = s->insert_copy_hgroup.htrees[0];
- if (!s->ringbuffer && !BrotliAllocateRingBuffer(s)) {
- result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2);
- break;
- }
- s->state = BROTLI_STATE_COMMAND_BEGIN;
- }
- break;
- case BROTLI_STATE_COMMAND_BEGIN:
- case BROTLI_STATE_COMMAND_INNER:
- case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS:
- case BROTLI_STATE_COMMAND_POST_WRAP_COPY:
- result = ProcessCommands(s);
- if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
- result = SafeProcessCommands(s);
- }
- break;
- case BROTLI_STATE_COMMAND_INNER_WRITE:
- case BROTLI_STATE_COMMAND_POST_WRITE_1:
- case BROTLI_STATE_COMMAND_POST_WRITE_2:
- result = WriteRingBuffer(s, available_out, next_out, total_out);
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- s->max_distance = s->max_backward_distance;
- if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {
- memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);
- if (s->meta_block_remaining_len == 0) {
- /* Next metablock, if any */
- s->state = BROTLI_STATE_METABLOCK_DONE;
- } else {
- s->state = BROTLI_STATE_COMMAND_BEGIN;
- }
- break;
- } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) {
- s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;
- } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */
- if (s->loop_counter == 0) {
- if (s->meta_block_remaining_len == 0) {
- s->state = BROTLI_STATE_METABLOCK_DONE;
- } else {
- s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;
- }
- break;
- }
- s->state = BROTLI_STATE_COMMAND_INNER;
- }
- break;
- case BROTLI_STATE_METABLOCK_DONE:
- 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;
- }
- s->state = BROTLI_STATE_DONE;
- /* No break, continue to next state */
- case BROTLI_STATE_DONE:
- if (s->ringbuffer != 0) {
- result = WriteRingBuffer(s, available_out, next_out, total_out);
- if (result != BROTLI_DECODER_SUCCESS) {
- break;
- }
- }
- return SaveErrorCode(s, result);
- }
- }
- return SaveErrorCode(s, result);
-}
-
-void BrotliDecoderSetCustomDictionary(
- BrotliDecoderState* s, size_t size, const uint8_t* dict) {
- if (size > (1u << 24)) {
- return;
- }
- s->custom_dict = dict;
- s->custom_dict_size = (int)size;
-}
-
-BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) {
- return TO_BROTLI_BOOL(
- s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0);
-}
-
-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);
-}
-
-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";
- }
-}
-
-/* DEPRECATED >>> */
-BrotliState* BrotliCreateState(
- brotli_alloc_func alloc, brotli_free_func free, void* opaque) {
- return (BrotliState*)BrotliDecoderCreateInstance(alloc, free, opaque);
-}
-void BrotliDestroyState(BrotliState* state) {
- BrotliDecoderDestroyInstance((BrotliDecoderState*)state);
-}
-BrotliResult BrotliDecompressBuffer(
- size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,
- uint8_t* decoded_buffer) {
- return (BrotliResult)BrotliDecoderDecompress(
- encoded_size, encoded_buffer, decoded_size, decoded_buffer);
-}
-BrotliResult BrotliDecompressStream(
- size_t* available_in, const uint8_t** next_in, size_t* available_out,
- uint8_t** next_out, size_t* total_out, BrotliState* s) {
- return (BrotliResult)BrotliDecoderDecompressStream((BrotliDecoderState*)s,
- available_in, next_in, available_out, next_out, total_out);
-}
-void BrotliSetCustomDictionary(
- size_t size, const uint8_t* dict, BrotliState* s) {
- BrotliDecoderSetCustomDictionary((BrotliDecoderState*)s, size, dict);
-}
-BROTLI_BOOL BrotliStateIsStreamStart(const BrotliState* s) {
- return !BrotliDecoderIsUsed((const BrotliDecoderState*)s);
-}
-BROTLI_BOOL BrotliStateIsStreamEnd(const BrotliState* s) {
- return BrotliDecoderIsFinished((const BrotliDecoderState*)s);
-}
-BrotliErrorCode BrotliGetErrorCode(const BrotliState* s) {
- return (BrotliErrorCode)BrotliDecoderGetErrorCode(
- (const BrotliDecoderState*)s);
-}
-const char* BrotliErrorString(BrotliErrorCode c) {
- return BrotliDecoderErrorString((BrotliDecoderErrorCode)c);
-}
-/* <<< DEPRECATED */
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
diff --git a/BaseTools/Source/C/BrotliCompress/dec/decode.h b/BaseTools/Source/C/BrotliCompress/dec/decode.h deleted file mode 100644 index 4a2fa2ec9b..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/decode.h +++ /dev/null @@ -1,188 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* API for Brotli decompression */
-
-#ifndef BROTLI_DEC_DECODE_H_
-#define BROTLI_DEC_DECODE_H_
-
-#include "../common/types.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-typedef struct BrotliDecoderStateStruct BrotliDecoderState;
-
-typedef enum {
- /* Decoding error, e.g. corrupt input or memory allocation problem */
- BROTLI_DECODER_RESULT_ERROR = 0,
- /* Decoding successfully completed */
- BROTLI_DECODER_RESULT_SUCCESS = 1,
- /* Partially done; should be called again with more input */
- BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT = 2,
- /* Partially done; should be called again with more output */
- BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT = 3
-} BrotliDecoderResult;
-
-#define BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE, SEPARATOR) \
- BROTLI_ERROR_CODE(_, NO_ERROR, 0) SEPARATOR \
- /* Same as BrotliDecoderResult values */ \
- BROTLI_ERROR_CODE(_, SUCCESS, 1) SEPARATOR \
- BROTLI_ERROR_CODE(_, NEEDS_MORE_INPUT, 2) SEPARATOR \
- BROTLI_ERROR_CODE(_, NEEDS_MORE_OUTPUT, 3) SEPARATOR \
- \
- /* Errors caused by invalid input */ \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, EXUBERANT_NIBBLE, -1) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, RESERVED, -2) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, EXUBERANT_META_NIBBLE, -3) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, SIMPLE_HUFFMAN_ALPHABET, -4) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, SIMPLE_HUFFMAN_SAME, -5) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, CL_SPACE, -6) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, HUFFMAN_SPACE, -7) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, CONTEXT_MAP_REPEAT, -8) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, BLOCK_LENGTH_1, -9) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, BLOCK_LENGTH_2, -10) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, TRANSFORM, -11) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, DICTIONARY, -12) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, WINDOW_BITS, -13) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, PADDING_1, -14) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_FORMAT_, PADDING_2, -15) SEPARATOR \
- \
- /* -16..-20 codes are reserved */ \
- \
- /* Memory allocation problems */ \
- BROTLI_ERROR_CODE(_ERROR_ALLOC_, CONTEXT_MODES, -21) SEPARATOR \
- /* Literal, insert and distance trees together */ \
- BROTLI_ERROR_CODE(_ERROR_ALLOC_, TREE_GROUPS, -22) SEPARATOR \
- /* -23..-24 codes are reserved for distinct tree groups */ \
- BROTLI_ERROR_CODE(_ERROR_ALLOC_, CONTEXT_MAP, -25) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_ALLOC_, RING_BUFFER_1, -26) SEPARATOR \
- BROTLI_ERROR_CODE(_ERROR_ALLOC_, RING_BUFFER_2, -27) SEPARATOR \
- /* -28..-29 codes are reserved for dynamic ringbuffer allocation */ \
- BROTLI_ERROR_CODE(_ERROR_ALLOC_, BLOCK_TYPE_TREES, -30) SEPARATOR \
- \
- /* "Impossible" states */ \
- BROTLI_ERROR_CODE(_ERROR_, UNREACHABLE, -31)
-
-typedef enum {
-#define _BROTLI_COMMA ,
-#define _BROTLI_ERROR_CODE_ENUM_ITEM(PREFIX, NAME, CODE) \
- BROTLI_DECODER ## PREFIX ## NAME = CODE
- BROTLI_DECODER_ERROR_CODES_LIST(_BROTLI_ERROR_CODE_ENUM_ITEM, _BROTLI_COMMA)
-#undef _BROTLI_ERROR_CODE_ENUM_ITEM
-#undef _BROTLI_COMMA
-} BrotliDecoderErrorCode;
-
-#define BROTLI_LAST_ERROR_CODE BROTLI_DECODER_ERROR_UNREACHABLE
-
-/* Creates the instance of BrotliDecoderState and initializes it. |alloc_func|
- and |free_func| MUST be both zero or both non-zero. In the case they are both
- zero, default memory allocators are used. |opaque| is passed to |alloc_func|
- and |free_func| when they are called. */
-BrotliDecoderState* BrotliDecoderCreateInstance(
- brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque);
-
-/* Deinitializes and frees BrotliDecoderState instance. */
-void BrotliDecoderDestroyInstance(BrotliDecoderState* state);
-
-/* Decompresses the data in |encoded_buffer| into |decoded_buffer|, and sets
- |*decoded_size| to the decompressed length. */
-BrotliDecoderResult BrotliDecoderDecompress(
- size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,
- uint8_t* decoded_buffer);
-
-/* Decompresses the data. Supports partial input and output.
-
- Must be called with an allocated input buffer in |*next_in| and an allocated
- output buffer in |*next_out|. The values |*available_in| and |*available_out|
- must specify the allocated size in |*next_in| and |*next_out| respectively.
-
- After each call, |*available_in| will be decremented by the amount of input
- bytes consumed, and the |*next_in| pointer will be incremented by that
- amount. Similarly, |*available_out| will be decremented by the amount of
- output bytes written, and the |*next_out| pointer will be incremented by that
- amount. |total_out|, if it is not a null-pointer, will be set to the number
- of bytes decompressed since the last state initialization.
-
- Input is never overconsumed, so |next_in| and |available_in| could be passed
- to the next consumer after decoding is complete. */
-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);
-
-/* Fills the new state with a dictionary for LZ77, warming up the ringbuffer,
- e.g. for custom static dictionaries for data formats.
- Not to be confused with the built-in transformable dictionary of Brotli.
- |size| should be less or equal to 2^24 (16MiB), otherwise the dictionary will
- be ignored. The dictionary must exist in memory until decoding is done and
- is owned by the caller. To use:
- 1) Allocate and initialize state with BrotliCreateInstance
- 2) Use BrotliSetCustomDictionary
- 3) Use BrotliDecompressStream
- 4) Clean up and free state with BrotliDestroyState
-*/
-void BrotliDecoderSetCustomDictionary(
- BrotliDecoderState* s, size_t size, const uint8_t* dict);
-
-/* Returns true, if decoder has some unconsumed output.
- Otherwise returns false. */
-BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s);
-
-/* Returns true, if decoder has already received some input bytes.
- Otherwise returns false. */
-BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s);
-
-/* Returns true, if decoder is in a state where we reached the end of the input
- and produced all of the output; returns false otherwise. */
-BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s);
-
-/* Returns detailed error code after BrotliDecompressStream returns
- BROTLI_DECODER_RESULT_ERROR. */
-BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s);
-
-const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c);
-
-/* DEPRECATED >>> */
-typedef enum {
- BROTLI_RESULT_ERROR = 0,
- BROTLI_RESULT_SUCCESS = 1,
- BROTLI_RESULT_NEEDS_MORE_INPUT = 2,
- BROTLI_RESULT_NEEDS_MORE_OUTPUT = 3
-} BrotliResult;
-typedef enum {
-#define _BROTLI_COMMA ,
-#define _BROTLI_ERROR_CODE_ENUM_ITEM(PREFIX, NAME, CODE) \
- BROTLI ## PREFIX ## NAME = CODE
- BROTLI_DECODER_ERROR_CODES_LIST(_BROTLI_ERROR_CODE_ENUM_ITEM, _BROTLI_COMMA)
-#undef _BROTLI_ERROR_CODE_ENUM_ITEM
-#undef _BROTLI_COMMA
-} BrotliErrorCode;
-typedef struct BrotliStateStruct BrotliState;
-BrotliState* BrotliCreateState(
- brotli_alloc_func alloc, brotli_free_func free, void* opaque);
-void BrotliDestroyState(BrotliState* state);
-BROTLI_BOOL BrotliDecompressedSize(
- size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size);
-BrotliResult BrotliDecompressBuffer(
- size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,
- uint8_t* decoded_buffer);
-BrotliResult BrotliDecompressStream(
- size_t* available_in, const uint8_t** next_in, size_t* available_out,
- uint8_t** next_out, size_t* total_out, BrotliState* s);
-void BrotliSetCustomDictionary(
- size_t size, const uint8_t* dict, BrotliState* s);
-BROTLI_BOOL BrotliStateIsStreamStart(const BrotliState* s);
-BROTLI_BOOL BrotliStateIsStreamEnd(const BrotliState* s);
-BrotliErrorCode BrotliGetErrorCode(const BrotliState* s);
-const char* BrotliErrorString(BrotliErrorCode c);
-/* <<< DEPRECATED */
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
-
-#endif /* BROTLI_DEC_DECODE_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/huffman.c b/BaseTools/Source/C/BrotliCompress/dec/huffman.c deleted file mode 100644 index 09a3c30d95..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/huffman.c +++ /dev/null @@ -1,357 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Utilities for building Huffman decoding tables. */
-
-#include "./huffman.h"
-
-#include <string.h> /* memcpy, memset */
-
-#include "../common/constants.h"
-#include "../common/types.h"
-#include "./port.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-#define BROTLI_REVERSE_BITS_MAX 8
-
-#ifdef BROTLI_RBIT
-#define BROTLI_REVERSE_BITS_BASE (32 - 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 \
- (1U << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
-
-/* Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
- where reverse(value, len) is the bit-wise reversal of the len least
- significant bits of value. */
-static BROTLI_INLINE uint32_t BrotliReverseBits(uint32_t num) {
-#ifdef BROTLI_RBIT
- return BROTLI_RBIT(num);
-#else
- return kReverseBits[num];
-#endif
-}
-
-/* Stores code in table[0], table[step], table[2*step], ..., table[end] */
-/* Assumes that end is an integer multiple of step */
-static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
- int step, int end,
- HuffmanCode code) {
- do {
- end -= step;
- table[end] = code;
- } while (end > 0);
-}
-
-/* Returns the table width of the next 2nd level table. count is the histogram
- of bit lengths for the remaining symbols, len is the code length of the next
- processed symbol */
-static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count,
- int len, int root_bits) {
- int left = 1 << (len - root_bits);
- while (len < BROTLI_HUFFMAN_MAX_CODE_LENGTH) {
- left -= count[len];
- if (left <= 0) break;
- ++len;
- left <<= 1;
- }
- return len - root_bits;
-}
-
-void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
- const uint8_t* const code_lengths,
- uint16_t* count) {
- HuffmanCode code; /* current table entry */
- int symbol; /* symbol index in original or sorted table */
- uint32_t key; /* prefix code */
- uint32_t key_step; /* prefix code addend */
- int step; /* step size to replicate values in current table */
- int table_size; /* size of current table */
- int sorted[BROTLI_CODE_LENGTH_CODES]; /* symbols sorted by code length */
- /* offsets in sorted table for each length */
- int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1];
- int bits;
- int bits_count;
- BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <=
- BROTLI_REVERSE_BITS_MAX);
-
- /* generate offsets into sorted symbol table by code length */
- symbol = -1;
- bits = 1;
- BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
- symbol += count[bits];
- offset[bits] = symbol;
- bits++;
- });
- /* Symbols with code length 0 are placed after all other symbols. */
- offset[0] = BROTLI_CODE_LENGTH_CODES - 1;
-
- /* sort symbols by length, by symbol order within each length */
- symbol = BROTLI_CODE_LENGTH_CODES;
- do {
- BROTLI_REPEAT(6, {
- symbol--;
- sorted[offset[code_lengths[symbol]]--] = symbol;
- });
- } while (symbol != 0);
-
- table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
-
- /* Special case: all symbols but one have 0 code length. */
- if (offset[0] == 0) {
- code.bits = 0;
- code.value = (uint16_t)sorted[0];
- for (key = 0; key < (uint32_t)table_size; ++key) {
- table[key] = code;
- }
- return;
- }
-
- /* fill in table */
- key = 0;
- key_step = BROTLI_REVERSE_BITS_LOWEST;
- symbol = 0;
- bits = 1;
- step = 2;
- do {
- code.bits = (uint8_t)bits;
- for (bits_count = count[bits]; bits_count != 0; --bits_count) {
- code.value = (uint16_t)sorted[symbol++];
- ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
- key += key_step;
- }
- step <<= 1;
- key_step >>= 1;
- } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
-}
-
-uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
- int root_bits,
- const uint16_t* const symbol_lists,
- uint16_t* count) {
- HuffmanCode code; /* current table entry */
- HuffmanCode* table; /* next available space in table */
- int len; /* current code length */
- int symbol; /* symbol index in original or sorted table */
- uint32_t key; /* prefix code */
- uint32_t key_step; /* prefix code addend */
- uint32_t sub_key; /* 2nd level table prefix code */
- uint32_t sub_key_step; /* 2nd level table prefix code addend */
- int step; /* step size to replicate values in current table */
- int table_bits; /* key length of current table */
- int table_size; /* size of current table */
- int total_size; /* sum of root table size and 2nd level table sizes */
- int max_length = -1;
- int bits;
- int bits_count;
-
- BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
- BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
- BROTLI_REVERSE_BITS_MAX);
-
- while (symbol_lists[max_length] == 0xFFFF) max_length--;
- max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
-
- table = root_table;
- table_bits = root_bits;
- table_size = 1 << table_bits;
- total_size = table_size;
-
- /* fill in root table */
- /* let's reduce the table size to a smaller size if possible, and */
- /* create the repetitions by memcpy if possible in the coming loop */
- if (table_bits > max_length) {
- table_bits = max_length;
- table_size = 1 << table_bits;
- }
- key = 0;
- key_step = BROTLI_REVERSE_BITS_LOWEST;
- bits = 1;
- step = 2;
- do {
- code.bits = (uint8_t)bits;
- symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
- for (bits_count = count[bits]; bits_count != 0; --bits_count) {
- symbol = symbol_lists[symbol];
- code.value = (uint16_t)symbol;
- ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
- key += key_step;
- }
- step <<= 1;
- key_step >>= 1;
- } while (++bits <= table_bits);
-
- /* if root_bits != table_bits we only created one fraction of the */
- /* table, and we need to replicate it now. */
- while (total_size != table_size) {
- memcpy(&table[table_size], &table[0],
- (size_t)table_size * sizeof(table[0]));
- table_size <<= 1;
- }
-
- /* fill in 2nd level tables and add pointers to root table */
- key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
- sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1);
- sub_key_step = BROTLI_REVERSE_BITS_LOWEST;
- for (len = root_bits + 1, step = 2; len <= max_length; ++len) {
- symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
- for (; count[len] != 0; --count[len]) {
- if (sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1U)) {
- table += table_size;
- table_bits = NextTableBitSize(count, len, root_bits);
- table_size = 1 << table_bits;
- total_size += table_size;
- sub_key = BrotliReverseBits(key);
- key += key_step;
- root_table[sub_key].bits = (uint8_t)(table_bits + root_bits);
- root_table[sub_key].value =
- (uint16_t)(((size_t)(table - root_table)) - sub_key);
- sub_key = 0;
- }
- code.bits = (uint8_t)(len - root_bits);
- symbol = symbol_lists[symbol];
- code.value = (uint16_t)symbol;
- ReplicateValue(
- &table[BrotliReverseBits(sub_key)], step, table_size, code);
- sub_key += sub_key_step;
- }
- step <<= 1;
- sub_key_step >>= 1;
- }
- return (uint32_t)total_size;
-}
-
-uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
- int root_bits,
- uint16_t* val,
- uint32_t num_symbols) {
- uint32_t table_size = 1;
- const uint32_t goal_size = 1U << root_bits;
- switch (num_symbols) {
- case 0:
- table[0].bits = 0;
- table[0].value = val[0];
- break;
- case 1:
- table[0].bits = 1;
- table[1].bits = 1;
- if (val[1] > val[0]) {
- table[0].value = val[0];
- table[1].value = val[1];
- } else {
- table[0].value = val[1];
- table[1].value = val[0];
- }
- table_size = 2;
- break;
- case 2:
- table[0].bits = 1;
- table[0].value = val[0];
- table[2].bits = 1;
- table[2].value = val[0];
- if (val[2] > val[1]) {
- table[1].value = val[1];
- table[3].value = val[2];
- } else {
- table[1].value = val[2];
- table[3].value = val[1];
- }
- table[1].bits = 2;
- table[3].bits = 2;
- 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;
- }
- }
- }
- for (i = 0; i < 4; ++i) {
- table[i].bits = 2;
- }
- table[0].value = val[0];
- table[2].value = val[1];
- table[1].value = val[2];
- table[3].value = val[3];
- table_size = 4;
- break;
- }
- case 4: {
- int i;
- if (val[3] < val[2]) {
- uint16_t t = val[3];
- val[3] = val[2];
- val[2] = t;
- }
- for (i = 0; i < 7; ++i) {
- table[i].value = val[0];
- table[i].bits = (uint8_t)(1 + (i & 1));
- }
- table[1].value = val[1];
- table[3].value = val[2];
- table[5].value = val[1];
- table[7].value = val[3];
- table[3].bits = 3;
- table[7].bits = 3;
- table_size = 8;
- break;
- }
- }
- while (table_size != goal_size) {
- memcpy(&table[table_size], &table[0],
- (size_t)table_size * sizeof(table[0]));
- table_size <<= 1;
- }
- return goal_size;
-}
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
diff --git a/BaseTools/Source/C/BrotliCompress/dec/huffman.h b/BaseTools/Source/C/BrotliCompress/dec/huffman.h deleted file mode 100644 index ead502dd7f..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/huffman.h +++ /dev/null @@ -1,68 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Utilities for building Huffman decoding tables. */
-
-#ifndef BROTLI_DEC_HUFFMAN_H_
-#define BROTLI_DEC_HUFFMAN_H_
-
-#include "../common/types.h"
-#include "./port.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-#define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15
-
-/* Maximum possible Huffman table size for an alphabet size of (index * 32),
- * max code length 15 and root table bits 8. */
-static const uint16_t kMaxHuffmanTableSize[] = {
- 256, 402, 436, 468, 500, 534, 566, 598, 630, 662, 694, 726, 758, 790, 822,
- 854, 886, 920, 952, 984, 1016, 1048, 1080};
-/* 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
-
-typedef struct {
- uint8_t bits; /* number of bits used for this symbol */
- uint16_t value; /* symbol value or table offset */
-} HuffmanCode;
-
-/* Builds Huffman lookup table assuming code lengths are in symbol order. */
-BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,
- const uint8_t* const code_lengths, uint16_t* count);
-
-/* Builds Huffman lookup table assuming code lengths are in symbol order. */
-/* Returns size of resulting table. */
-BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
- int root_bits, const uint16_t* const symbol_lists, uint16_t* count_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);
-
-/* Contains a collection of Huffman trees with the same alphabet size. */
-typedef struct {
- HuffmanCode** htrees;
- HuffmanCode* codes;
- uint16_t alphabet_size;
- uint16_t num_htrees;
-} HuffmanTreeGroup;
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
-
-#endif /* BROTLI_DEC_HUFFMAN_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/port.h b/BaseTools/Source/C/BrotliCompress/dec/port.h deleted file mode 100644 index 866965b1ef..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/port.h +++ /dev/null @@ -1,159 +0,0 @@ -/* Copyright 2015 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Macros for compiler / platform specific features and build options.
-
- Build options are:
- * BROTLI_BUILD_32_BIT disables 64-bit optimizations
- * BROTLI_BUILD_64_BIT forces to use 64-bit optimizations
- * BROTLI_BUILD_BIG_ENDIAN forces to use big-endian optimizations
- * BROTLI_BUILD_ENDIAN_NEUTRAL disables endian-aware optimizations
- * BROTLI_BUILD_LITTLE_ENDIAN forces to use little-endian optimizations
- * BROTLI_BUILD_MODERN_COMPILER forces to use modern compilers built-ins,
- features and attributes
- * BROTLI_BUILD_PORTABLE disables dangerous optimizations, like unaligned
- read and overlapping memcpy; this reduces decompression speed by 5%
- * BROTLI_DEBUG dumps file name and line number when decoder detects stream
- or memory error
- * BROTLI_ENABLE_LOG enables asserts and dumps various state information
- */
-
-#ifndef BROTLI_DEC_PORT_H_
-#define BROTLI_DEC_PORT_H_
-
-#if defined(BROTLI_ENABLE_LOG) || defined(BROTLI_DEBUG)
-#include <assert.h>
-#include <stdio.h>
-#endif
-
-#include "../common/port.h"
-
-#if defined(__arm__) || defined(__thumb__) || \
- defined(_M_ARM) || defined(_M_ARMT)
-#define BROTLI_TARGET_ARM
-#if (defined(__ARM_ARCH) && (__ARM_ARCH >= 7)) || \
- (defined(M_ARM) && (M_ARM >= 7))
-#define BROTLI_TARGET_ARMV7
-#endif /* ARMv7 */
-#if defined(__aarch64__)
-#define BROTLI_TARGET_ARMV8
-#endif /* ARMv8 */
-#endif /* ARM */
-
-#if defined(__i386) || defined(_M_IX86)
-#define BROTLI_TARGET_X86
-#endif
-
-#if defined(__x86_64__) || defined(_M_X64)
-#define BROTLI_TARGET_X64
-#endif
-
-#if defined(__PPC64__)
-#define BROTLI_TARGET_POWERPC64
-#endif
-
-#ifdef BROTLI_BUILD_PORTABLE
-#define BROTLI_ALIGNED_READ (!!1)
-#elif defined(BROTLI_TARGET_X86) || defined(BROTLI_TARGET_X64) || \
- defined(BROTLI_TARGET_ARMV7) || defined(BROTLI_TARGET_ARMV8)
-/* Allow unaligned read only for whitelisted CPUs. */
-#define BROTLI_ALIGNED_READ (!!0)
-#else
-#define BROTLI_ALIGNED_READ (!!1)
-#endif
-
-/* IS_CONSTANT macros returns true for compile-time constant expressions. */
-#if BROTLI_MODERN_COMPILER || __has_builtin(__builtin_constant_p)
-#define IS_CONSTANT(x) (!!__builtin_constant_p(x))
-#else
-#define IS_CONSTANT(x) (!!0)
-#endif
-
-#ifdef BROTLI_ENABLE_LOG
-#define BROTLI_DCHECK(x) assert(x)
-#define BROTLI_LOG(x) printf x
-#else
-#define BROTLI_DCHECK(x)
-#define BROTLI_LOG(x)
-#endif
-
-#if defined(BROTLI_DEBUG) || defined(BROTLI_ENABLE_LOG)
-static BROTLI_INLINE void BrotliDump(const char* f, int l, const char* fn) {
- fprintf(stderr, "%s:%d (%s)\n", f, l, fn);
- fflush(stderr);
-}
-#define BROTLI_DUMP() BrotliDump(__FILE__, __LINE__, __FUNCTION__)
-#else
-#define BROTLI_DUMP() (void)(0)
-#endif
-
-#if defined(BROTLI_BUILD_64_BIT)
-#define BROTLI_64_BITS 1
-#elif defined(BROTLI_BUILD_32_BIT)
-#define BROTLI_64_BITS 0
-#elif defined(BROTLI_TARGET_X64) || defined(BROTLI_TARGET_ARMV8) || \
- defined(BROTLI_TARGET_POWERPC64)
-#define BROTLI_64_BITS 1
-#else
-#define BROTLI_64_BITS 0
-#endif
-
-#if defined(BROTLI_BUILD_BIG_ENDIAN)
-#define BROTLI_LITTLE_ENDIAN 0
-#define BROTLI_BIG_ENDIAN 1
-#elif defined(BROTLI_BUILD_LITTLE_ENDIAN)
-#define BROTLI_LITTLE_ENDIAN 1
-#define BROTLI_BIG_ENDIAN 0
-#elif defined(BROTLI_BUILD_ENDIAN_NEUTRAL)
-#define BROTLI_LITTLE_ENDIAN 0
-#define BROTLI_BIG_ENDIAN 0
-#elif defined(__BYTE_ORDER__) && (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
-#define BROTLI_LITTLE_ENDIAN 1
-#define BROTLI_BIG_ENDIAN 0
-#elif defined(_WIN32)
-/* Win32 can currently always be assumed to be little endian */
-#define BROTLI_LITTLE_ENDIAN 1
-#define BROTLI_BIG_ENDIAN 0
-#else
-#if (defined(__BYTE_ORDER__) && (__BYTE_ORDER__ == __ORDER_BIG_ENDIAN__))
-#define BROTLI_BIG_ENDIAN 1
-#else
-#define BROTLI_BIG_ENDIAN 0
-#endif
-#define BROTLI_LITTLE_ENDIAN 0
-#endif
-
-#define BROTLI_REPEAT(N, X) { \
- if ((N & 1) != 0) {X;} \
- if ((N & 2) != 0) {X; X;} \
- if ((N & 4) != 0) {X; X; X; X;} \
-}
-
-#if BROTLI_MODERN_COMPILER || defined(__llvm__)
-#if defined(BROTLI_TARGET_ARMV7)
-static BROTLI_INLINE unsigned BrotliRBit(unsigned input) {
- unsigned output;
- __asm__("rbit %0, %1\n" : "=r"(output) : "r"(input));
- return output;
-}
-#define BROTLI_RBIT(x) BrotliRBit(x)
-#endif /* armv7 */
-#endif /* gcc || clang */
-
-#if defined(BROTLI_TARGET_ARM)
-#define BROTLI_HAS_UBFX (!!1)
-#else
-#define BROTLI_HAS_UBFX (!!0)
-#endif
-
-#define BROTLI_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L)
-
-#define BROTLI_FREE(S, X) { \
- S->free_func(S->memory_manager_opaque, X); \
- X = NULL; \
-}
-
-#endif /* BROTLI_DEC_PORT_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/prefix.h b/BaseTools/Source/C/BrotliCompress/dec/prefix.h deleted file mode 100644 index 6006496433..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/prefix.h +++ /dev/null @@ -1,751 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Lookup tables to map prefix codes to value ranges. This is used during
- decoding of the block lengths, literal insertion lengths and copy lengths.
-*/
-
-#ifndef BROTLI_DEC_PREFIX_H_
-#define BROTLI_DEC_PREFIX_H_
-
-#include "../common/constants.h"
-#include "../common/types.h"
-
-/* Represents the range of values belonging to a prefix code: */
-/* [offset, offset + 2^nbits) */
-struct PrefixCodeRange {
- uint16_t offset;
- uint8_t nbits;
-};
-
-static const struct PrefixCodeRange
- kBlockLengthPrefixCode[BROTLI_NUM_BLOCK_LEN_SYMBOLS] = {
- { 1, 2}, { 5, 2}, { 9, 2}, { 13, 2},
- { 17, 3}, { 25, 3}, { 33, 3}, { 41, 3},
- { 49, 4}, { 65, 4}, { 81, 4}, { 97, 4},
- { 113, 5}, { 145, 5}, { 177, 5}, { 209, 5},
- { 241, 6}, { 305, 6}, { 369, 7}, { 497, 8},
- { 753, 9}, { 1265, 10}, {2289, 11}, {4337, 12},
- {8433, 13}, {16625, 24}
-};
-
-typedef struct CmdLutElement {
- uint8_t insert_len_extra_bits;
- uint8_t copy_len_extra_bits;
- int8_t distance_code;
- uint8_t context;
- uint16_t insert_len_offset;
- uint16_t copy_len_offset;
-} CmdLutElement;
-
-static const CmdLutElement kCmdLut[BROTLI_NUM_COMMAND_SYMBOLS] = {
- { 0x00, 0x00, 0, 0x00, 0x0000, 0x0002 },
- { 0x00, 0x00, 0, 0x01, 0x0000, 0x0003 },
- { 0x00, 0x00, 0, 0x02, 0x0000, 0x0004 },
- { 0x00, 0x00, 0, 0x03, 0x0000, 0x0005 },
- { 0x00, 0x00, 0, 0x03, 0x0000, 0x0006 },
- { 0x00, 0x00, 0, 0x03, 0x0000, 0x0007 },
- { 0x00, 0x00, 0, 0x03, 0x0000, 0x0008 },
- { 0x00, 0x00, 0, 0x03, 0x0000, 0x0009 },
- { 0x00, 0x00, 0, 0x00, 0x0001, 0x0002 },
- { 0x00, 0x00, 0, 0x01, 0x0001, 0x0003 },
- { 0x00, 0x00, 0, 0x02, 0x0001, 0x0004 },
- { 0x00, 0x00, 0, 0x03, 0x0001, 0x0005 },
- { 0x00, 0x00, 0, 0x03, 0x0001, 0x0006 },
- { 0x00, 0x00, 0, 0x03, 0x0001, 0x0007 },
- { 0x00, 0x00, 0, 0x03, 0x0001, 0x0008 },
- { 0x00, 0x00, 0, 0x03, 0x0001, 0x0009 },
- { 0x00, 0x00, 0, 0x00, 0x0002, 0x0002 },
- { 0x00, 0x00, 0, 0x01, 0x0002, 0x0003 },
- { 0x00, 0x00, 0, 0x02, 0x0002, 0x0004 },
- { 0x00, 0x00, 0, 0x03, 0x0002, 0x0005 },
- { 0x00, 0x00, 0, 0x03, 0x0002, 0x0006 },
- { 0x00, 0x00, 0, 0x03, 0x0002, 0x0007 },
- { 0x00, 0x00, 0, 0x03, 0x0002, 0x0008 },
- { 0x00, 0x00, 0, 0x03, 0x0002, 0x0009 },
- { 0x00, 0x00, 0, 0x00, 0x0003, 0x0002 },
- { 0x00, 0x00, 0, 0x01, 0x0003, 0x0003 },
- { 0x00, 0x00, 0, 0x02, 0x0003, 0x0004 },
- { 0x00, 0x00, 0, 0x03, 0x0003, 0x0005 },
- { 0x00, 0x00, 0, 0x03, 0x0003, 0x0006 },
- { 0x00, 0x00, 0, 0x03, 0x0003, 0x0007 },
- { 0x00, 0x00, 0, 0x03, 0x0003, 0x0008 },
- { 0x00, 0x00, 0, 0x03, 0x0003, 0x0009 },
- { 0x00, 0x00, 0, 0x00, 0x0004, 0x0002 },
- { 0x00, 0x00, 0, 0x01, 0x0004, 0x0003 },
- { 0x00, 0x00, 0, 0x02, 0x0004, 0x0004 },
- { 0x00, 0x00, 0, 0x03, 0x0004, 0x0005 },
- { 0x00, 0x00, 0, 0x03, 0x0004, 0x0006 },
- { 0x00, 0x00, 0, 0x03, 0x0004, 0x0007 },
- { 0x00, 0x00, 0, 0x03, 0x0004, 0x0008 },
- { 0x00, 0x00, 0, 0x03, 0x0004, 0x0009 },
- { 0x00, 0x00, 0, 0x00, 0x0005, 0x0002 },
- { 0x00, 0x00, 0, 0x01, 0x0005, 0x0003 },
- { 0x00, 0x00, 0, 0x02, 0x0005, 0x0004 },
- { 0x00, 0x00, 0, 0x03, 0x0005, 0x0005 },
- { 0x00, 0x00, 0, 0x03, 0x0005, 0x0006 },
- { 0x00, 0x00, 0, 0x03, 0x0005, 0x0007 },
- { 0x00, 0x00, 0, 0x03, 0x0005, 0x0008 },
- { 0x00, 0x00, 0, 0x03, 0x0005, 0x0009 },
- { 0x01, 0x00, 0, 0x00, 0x0006, 0x0002 },
- { 0x01, 0x00, 0, 0x01, 0x0006, 0x0003 },
- { 0x01, 0x00, 0, 0x02, 0x0006, 0x0004 },
- { 0x01, 0x00, 0, 0x03, 0x0006, 0x0005 },
- { 0x01, 0x00, 0, 0x03, 0x0006, 0x0006 },
- { 0x01, 0x00, 0, 0x03, 0x0006, 0x0007 },
- { 0x01, 0x00, 0, 0x03, 0x0006, 0x0008 },
- { 0x01, 0x00, 0, 0x03, 0x0006, 0x0009 },
- { 0x01, 0x00, 0, 0x00, 0x0008, 0x0002 },
- { 0x01, 0x00, 0, 0x01, 0x0008, 0x0003 },
- { 0x01, 0x00, 0, 0x02, 0x0008, 0x0004 },
- { 0x01, 0x00, 0, 0x03, 0x0008, 0x0005 },
- { 0x01, 0x00, 0, 0x03, 0x0008, 0x0006 },
- { 0x01, 0x00, 0, 0x03, 0x0008, 0x0007 },
- { 0x01, 0x00, 0, 0x03, 0x0008, 0x0008 },
- { 0x01, 0x00, 0, 0x03, 0x0008, 0x0009 },
- { 0x00, 0x01, 0, 0x03, 0x0000, 0x000a },
- { 0x00, 0x01, 0, 0x03, 0x0000, 0x000c },
- { 0x00, 0x02, 0, 0x03, 0x0000, 0x000e },
- { 0x00, 0x02, 0, 0x03, 0x0000, 0x0012 },
- { 0x00, 0x03, 0, 0x03, 0x0000, 0x0016 },
- { 0x00, 0x03, 0, 0x03, 0x0000, 0x001e },
- { 0x00, 0x04, 0, 0x03, 0x0000, 0x0026 },
- { 0x00, 0x04, 0, 0x03, 0x0000, 0x0036 },
- { 0x00, 0x01, 0, 0x03, 0x0001, 0x000a },
- { 0x00, 0x01, 0, 0x03, 0x0001, 0x000c },
- { 0x00, 0x02, 0, 0x03, 0x0001, 0x000e },
- { 0x00, 0x02, 0, 0x03, 0x0001, 0x0012 },
- { 0x00, 0x03, 0, 0x03, 0x0001, 0x0016 },
- { 0x00, 0x03, 0, 0x03, 0x0001, 0x001e },
- { 0x00, 0x04, 0, 0x03, 0x0001, 0x0026 },
- { 0x00, 0x04, 0, 0x03, 0x0001, 0x0036 },
- { 0x00, 0x01, 0, 0x03, 0x0002, 0x000a },
- { 0x00, 0x01, 0, 0x03, 0x0002, 0x000c },
- { 0x00, 0x02, 0, 0x03, 0x0002, 0x000e },
- { 0x00, 0x02, 0, 0x03, 0x0002, 0x0012 },
- { 0x00, 0x03, 0, 0x03, 0x0002, 0x0016 },
- { 0x00, 0x03, 0, 0x03, 0x0002, 0x001e },
- { 0x00, 0x04, 0, 0x03, 0x0002, 0x0026 },
- { 0x00, 0x04, 0, 0x03, 0x0002, 0x0036 },
- { 0x00, 0x01, 0, 0x03, 0x0003, 0x000a },
- { 0x00, 0x01, 0, 0x03, 0x0003, 0x000c },
- { 0x00, 0x02, 0, 0x03, 0x0003, 0x000e },
- { 0x00, 0x02, 0, 0x03, 0x0003, 0x0012 },
- { 0x00, 0x03, 0, 0x03, 0x0003, 0x0016 },
- { 0x00, 0x03, 0, 0x03, 0x0003, 0x001e },
- { 0x00, 0x04, 0, 0x03, 0x0003, 0x0026 },
- { 0x00, 0x04, 0, 0x03, 0x0003, 0x0036 },
- { 0x00, 0x01, 0, 0x03, 0x0004, 0x000a },
- { 0x00, 0x01, 0, 0x03, 0x0004, 0x000c },
- { 0x00, 0x02, 0, 0x03, 0x0004, 0x000e },
- { 0x00, 0x02, 0, 0x03, 0x0004, 0x0012 },
- { 0x00, 0x03, 0, 0x03, 0x0004, 0x0016 },
- { 0x00, 0x03, 0, 0x03, 0x0004, 0x001e },
- { 0x00, 0x04, 0, 0x03, 0x0004, 0x0026 },
- { 0x00, 0x04, 0, 0x03, 0x0004, 0x0036 },
- { 0x00, 0x01, 0, 0x03, 0x0005, 0x000a },
- { 0x00, 0x01, 0, 0x03, 0x0005, 0x000c },
- { 0x00, 0x02, 0, 0x03, 0x0005, 0x000e },
- { 0x00, 0x02, 0, 0x03, 0x0005, 0x0012 },
- { 0x00, 0x03, 0, 0x03, 0x0005, 0x0016 },
- { 0x00, 0x03, 0, 0x03, 0x0005, 0x001e },
- { 0x00, 0x04, 0, 0x03, 0x0005, 0x0026 },
- { 0x00, 0x04, 0, 0x03, 0x0005, 0x0036 },
- { 0x01, 0x01, 0, 0x03, 0x0006, 0x000a },
- { 0x01, 0x01, 0, 0x03, 0x0006, 0x000c },
- { 0x01, 0x02, 0, 0x03, 0x0006, 0x000e },
- { 0x01, 0x02, 0, 0x03, 0x0006, 0x0012 },
- { 0x01, 0x03, 0, 0x03, 0x0006, 0x0016 },
- { 0x01, 0x03, 0, 0x03, 0x0006, 0x001e },
- { 0x01, 0x04, 0, 0x03, 0x0006, 0x0026 },
- { 0x01, 0x04, 0, 0x03, 0x0006, 0x0036 },
- { 0x01, 0x01, 0, 0x03, 0x0008, 0x000a },
- { 0x01, 0x01, 0, 0x03, 0x0008, 0x000c },
- { 0x01, 0x02, 0, 0x03, 0x0008, 0x000e },
- { 0x01, 0x02, 0, 0x03, 0x0008, 0x0012 },
- { 0x01, 0x03, 0, 0x03, 0x0008, 0x0016 },
- { 0x01, 0x03, 0, 0x03, 0x0008, 0x001e },
- { 0x01, 0x04, 0, 0x03, 0x0008, 0x0026 },
- { 0x01, 0x04, 0, 0x03, 0x0008, 0x0036 },
- { 0x00, 0x00, -1, 0x00, 0x0000, 0x0002 },
- { 0x00, 0x00, -1, 0x01, 0x0000, 0x0003 },
- { 0x00, 0x00, -1, 0x02, 0x0000, 0x0004 },
- { 0x00, 0x00, -1, 0x03, 0x0000, 0x0005 },
- { 0x00, 0x00, -1, 0x03, 0x0000, 0x0006 },
- { 0x00, 0x00, -1, 0x03, 0x0000, 0x0007 },
- { 0x00, 0x00, -1, 0x03, 0x0000, 0x0008 },
- { 0x00, 0x00, -1, 0x03, 0x0000, 0x0009 },
- { 0x00, 0x00, -1, 0x00, 0x0001, 0x0002 },
- { 0x00, 0x00, -1, 0x01, 0x0001, 0x0003 },
- { 0x00, 0x00, -1, 0x02, 0x0001, 0x0004 },
- { 0x00, 0x00, -1, 0x03, 0x0001, 0x0005 },
- { 0x00, 0x00, -1, 0x03, 0x0001, 0x0006 },
- { 0x00, 0x00, -1, 0x03, 0x0001, 0x0007 },
- { 0x00, 0x00, -1, 0x03, 0x0001, 0x0008 },
- { 0x00, 0x00, -1, 0x03, 0x0001, 0x0009 },
- { 0x00, 0x00, -1, 0x00, 0x0002, 0x0002 },
- { 0x00, 0x00, -1, 0x01, 0x0002, 0x0003 },
- { 0x00, 0x00, -1, 0x02, 0x0002, 0x0004 },
- { 0x00, 0x00, -1, 0x03, 0x0002, 0x0005 },
- { 0x00, 0x00, -1, 0x03, 0x0002, 0x0006 },
- { 0x00, 0x00, -1, 0x03, 0x0002, 0x0007 },
- { 0x00, 0x00, -1, 0x03, 0x0002, 0x0008 },
- { 0x00, 0x00, -1, 0x03, 0x0002, 0x0009 },
- { 0x00, 0x00, -1, 0x00, 0x0003, 0x0002 },
- { 0x00, 0x00, -1, 0x01, 0x0003, 0x0003 },
- { 0x00, 0x00, -1, 0x02, 0x0003, 0x0004 },
- { 0x00, 0x00, -1, 0x03, 0x0003, 0x0005 },
- { 0x00, 0x00, -1, 0x03, 0x0003, 0x0006 },
- { 0x00, 0x00, -1, 0x03, 0x0003, 0x0007 },
- { 0x00, 0x00, -1, 0x03, 0x0003, 0x0008 },
- { 0x00, 0x00, -1, 0x03, 0x0003, 0x0009 },
- { 0x00, 0x00, -1, 0x00, 0x0004, 0x0002 },
- { 0x00, 0x00, -1, 0x01, 0x0004, 0x0003 },
- { 0x00, 0x00, -1, 0x02, 0x0004, 0x0004 },
- { 0x00, 0x00, -1, 0x03, 0x0004, 0x0005 },
- { 0x00, 0x00, -1, 0x03, 0x0004, 0x0006 },
- { 0x00, 0x00, -1, 0x03, 0x0004, 0x0007 },
- { 0x00, 0x00, -1, 0x03, 0x0004, 0x0008 },
- { 0x00, 0x00, -1, 0x03, 0x0004, 0x0009 },
- { 0x00, 0x00, -1, 0x00, 0x0005, 0x0002 },
- { 0x00, 0x00, -1, 0x01, 0x0005, 0x0003 },
- { 0x00, 0x00, -1, 0x02, 0x0005, 0x0004 },
- { 0x00, 0x00, -1, 0x03, 0x0005, 0x0005 },
- { 0x00, 0x00, -1, 0x03, 0x0005, 0x0006 },
- { 0x00, 0x00, -1, 0x03, 0x0005, 0x0007 },
- { 0x00, 0x00, -1, 0x03, 0x0005, 0x0008 },
- { 0x00, 0x00, -1, 0x03, 0x0005, 0x0009 },
- { 0x01, 0x00, -1, 0x00, 0x0006, 0x0002 },
- { 0x01, 0x00, -1, 0x01, 0x0006, 0x0003 },
- { 0x01, 0x00, -1, 0x02, 0x0006, 0x0004 },
- { 0x01, 0x00, -1, 0x03, 0x0006, 0x0005 },
- { 0x01, 0x00, -1, 0x03, 0x0006, 0x0006 },
- { 0x01, 0x00, -1, 0x03, 0x0006, 0x0007 },
- { 0x01, 0x00, -1, 0x03, 0x0006, 0x0008 },
- { 0x01, 0x00, -1, 0x03, 0x0006, 0x0009 },
- { 0x01, 0x00, -1, 0x00, 0x0008, 0x0002 },
- { 0x01, 0x00, -1, 0x01, 0x0008, 0x0003 },
- { 0x01, 0x00, -1, 0x02, 0x0008, 0x0004 },
- { 0x01, 0x00, -1, 0x03, 0x0008, 0x0005 },
- { 0x01, 0x00, -1, 0x03, 0x0008, 0x0006 },
- { 0x01, 0x00, -1, 0x03, 0x0008, 0x0007 },
- { 0x01, 0x00, -1, 0x03, 0x0008, 0x0008 },
- { 0x01, 0x00, -1, 0x03, 0x0008, 0x0009 },
- { 0x00, 0x01, -1, 0x03, 0x0000, 0x000a },
- { 0x00, 0x01, -1, 0x03, 0x0000, 0x000c },
- { 0x00, 0x02, -1, 0x03, 0x0000, 0x000e },
- { 0x00, 0x02, -1, 0x03, 0x0000, 0x0012 },
- { 0x00, 0x03, -1, 0x03, 0x0000, 0x0016 },
- { 0x00, 0x03, -1, 0x03, 0x0000, 0x001e },
- { 0x00, 0x04, -1, 0x03, 0x0000, 0x0026 },
- { 0x00, 0x04, -1, 0x03, 0x0000, 0x0036 },
- { 0x00, 0x01, -1, 0x03, 0x0001, 0x000a },
- { 0x00, 0x01, -1, 0x03, 0x0001, 0x000c },
- { 0x00, 0x02, -1, 0x03, 0x0001, 0x000e },
- { 0x00, 0x02, -1, 0x03, 0x0001, 0x0012 },
- { 0x00, 0x03, -1, 0x03, 0x0001, 0x0016 },
- { 0x00, 0x03, -1, 0x03, 0x0001, 0x001e },
- { 0x00, 0x04, -1, 0x03, 0x0001, 0x0026 },
- { 0x00, 0x04, -1, 0x03, 0x0001, 0x0036 },
- { 0x00, 0x01, -1, 0x03, 0x0002, 0x000a },
- { 0x00, 0x01, -1, 0x03, 0x0002, 0x000c },
- { 0x00, 0x02, -1, 0x03, 0x0002, 0x000e },
- { 0x00, 0x02, -1, 0x03, 0x0002, 0x0012 },
- { 0x00, 0x03, -1, 0x03, 0x0002, 0x0016 },
- { 0x00, 0x03, -1, 0x03, 0x0002, 0x001e },
- { 0x00, 0x04, -1, 0x03, 0x0002, 0x0026 },
- { 0x00, 0x04, -1, 0x03, 0x0002, 0x0036 },
- { 0x00, 0x01, -1, 0x03, 0x0003, 0x000a },
- { 0x00, 0x01, -1, 0x03, 0x0003, 0x000c },
- { 0x00, 0x02, -1, 0x03, 0x0003, 0x000e },
- { 0x00, 0x02, -1, 0x03, 0x0003, 0x0012 },
- { 0x00, 0x03, -1, 0x03, 0x0003, 0x0016 },
- { 0x00, 0x03, -1, 0x03, 0x0003, 0x001e },
- { 0x00, 0x04, -1, 0x03, 0x0003, 0x0026 },
- { 0x00, 0x04, -1, 0x03, 0x0003, 0x0036 },
- { 0x00, 0x01, -1, 0x03, 0x0004, 0x000a },
- { 0x00, 0x01, -1, 0x03, 0x0004, 0x000c },
- { 0x00, 0x02, -1, 0x03, 0x0004, 0x000e },
- { 0x00, 0x02, -1, 0x03, 0x0004, 0x0012 },
- { 0x00, 0x03, -1, 0x03, 0x0004, 0x0016 },
- { 0x00, 0x03, -1, 0x03, 0x0004, 0x001e },
- { 0x00, 0x04, -1, 0x03, 0x0004, 0x0026 },
- { 0x00, 0x04, -1, 0x03, 0x0004, 0x0036 },
- { 0x00, 0x01, -1, 0x03, 0x0005, 0x000a },
- { 0x00, 0x01, -1, 0x03, 0x0005, 0x000c },
- { 0x00, 0x02, -1, 0x03, 0x0005, 0x000e },
- { 0x00, 0x02, -1, 0x03, 0x0005, 0x0012 },
- { 0x00, 0x03, -1, 0x03, 0x0005, 0x0016 },
- { 0x00, 0x03, -1, 0x03, 0x0005, 0x001e },
- { 0x00, 0x04, -1, 0x03, 0x0005, 0x0026 },
- { 0x00, 0x04, -1, 0x03, 0x0005, 0x0036 },
- { 0x01, 0x01, -1, 0x03, 0x0006, 0x000a },
- { 0x01, 0x01, -1, 0x03, 0x0006, 0x000c },
- { 0x01, 0x02, -1, 0x03, 0x0006, 0x000e },
- { 0x01, 0x02, -1, 0x03, 0x0006, 0x0012 },
- { 0x01, 0x03, -1, 0x03, 0x0006, 0x0016 },
- { 0x01, 0x03, -1, 0x03, 0x0006, 0x001e },
- { 0x01, 0x04, -1, 0x03, 0x0006, 0x0026 },
- { 0x01, 0x04, -1, 0x03, 0x0006, 0x0036 },
- { 0x01, 0x01, -1, 0x03, 0x0008, 0x000a },
- { 0x01, 0x01, -1, 0x03, 0x0008, 0x000c },
- { 0x01, 0x02, -1, 0x03, 0x0008, 0x000e },
- { 0x01, 0x02, -1, 0x03, 0x0008, 0x0012 },
- { 0x01, 0x03, -1, 0x03, 0x0008, 0x0016 },
- { 0x01, 0x03, -1, 0x03, 0x0008, 0x001e },
- { 0x01, 0x04, -1, 0x03, 0x0008, 0x0026 },
- { 0x01, 0x04, -1, 0x03, 0x0008, 0x0036 },
- { 0x02, 0x00, -1, 0x00, 0x000a, 0x0002 },
- { 0x02, 0x00, -1, 0x01, 0x000a, 0x0003 },
- { 0x02, 0x00, -1, 0x02, 0x000a, 0x0004 },
- { 0x02, 0x00, -1, 0x03, 0x000a, 0x0005 },
- { 0x02, 0x00, -1, 0x03, 0x000a, 0x0006 },
- { 0x02, 0x00, -1, 0x03, 0x000a, 0x0007 },
- { 0x02, 0x00, -1, 0x03, 0x000a, 0x0008 },
- { 0x02, 0x00, -1, 0x03, 0x000a, 0x0009 },
- { 0x02, 0x00, -1, 0x00, 0x000e, 0x0002 },
- { 0x02, 0x00, -1, 0x01, 0x000e, 0x0003 },
- { 0x02, 0x00, -1, 0x02, 0x000e, 0x0004 },
- { 0x02, 0x00, -1, 0x03, 0x000e, 0x0005 },
- { 0x02, 0x00, -1, 0x03, 0x000e, 0x0006 },
- { 0x02, 0x00, -1, 0x03, 0x000e, 0x0007 },
- { 0x02, 0x00, -1, 0x03, 0x000e, 0x0008 },
- { 0x02, 0x00, -1, 0x03, 0x000e, 0x0009 },
- { 0x03, 0x00, -1, 0x00, 0x0012, 0x0002 },
- { 0x03, 0x00, -1, 0x01, 0x0012, 0x0003 },
- { 0x03, 0x00, -1, 0x02, 0x0012, 0x0004 },
- { 0x03, 0x00, -1, 0x03, 0x0012, 0x0005 },
- { 0x03, 0x00, -1, 0x03, 0x0012, 0x0006 },
- { 0x03, 0x00, -1, 0x03, 0x0012, 0x0007 },
- { 0x03, 0x00, -1, 0x03, 0x0012, 0x0008 },
- { 0x03, 0x00, -1, 0x03, 0x0012, 0x0009 },
- { 0x03, 0x00, -1, 0x00, 0x001a, 0x0002 },
- { 0x03, 0x00, -1, 0x01, 0x001a, 0x0003 },
- { 0x03, 0x00, -1, 0x02, 0x001a, 0x0004 },
- { 0x03, 0x00, -1, 0x03, 0x001a, 0x0005 },
- { 0x03, 0x00, -1, 0x03, 0x001a, 0x0006 },
- { 0x03, 0x00, -1, 0x03, 0x001a, 0x0007 },
- { 0x03, 0x00, -1, 0x03, 0x001a, 0x0008 },
- { 0x03, 0x00, -1, 0x03, 0x001a, 0x0009 },
- { 0x04, 0x00, -1, 0x00, 0x0022, 0x0002 },
- { 0x04, 0x00, -1, 0x01, 0x0022, 0x0003 },
- { 0x04, 0x00, -1, 0x02, 0x0022, 0x0004 },
- { 0x04, 0x00, -1, 0x03, 0x0022, 0x0005 },
- { 0x04, 0x00, -1, 0x03, 0x0022, 0x0006 },
- { 0x04, 0x00, -1, 0x03, 0x0022, 0x0007 },
- { 0x04, 0x00, -1, 0x03, 0x0022, 0x0008 },
- { 0x04, 0x00, -1, 0x03, 0x0022, 0x0009 },
- { 0x04, 0x00, -1, 0x00, 0x0032, 0x0002 },
- { 0x04, 0x00, -1, 0x01, 0x0032, 0x0003 },
- { 0x04, 0x00, -1, 0x02, 0x0032, 0x0004 },
- { 0x04, 0x00, -1, 0x03, 0x0032, 0x0005 },
- { 0x04, 0x00, -1, 0x03, 0x0032, 0x0006 },
- { 0x04, 0x00, -1, 0x03, 0x0032, 0x0007 },
- { 0x04, 0x00, -1, 0x03, 0x0032, 0x0008 },
- { 0x04, 0x00, -1, 0x03, 0x0032, 0x0009 },
- { 0x05, 0x00, -1, 0x00, 0x0042, 0x0002 },
- { 0x05, 0x00, -1, 0x01, 0x0042, 0x0003 },
- { 0x05, 0x00, -1, 0x02, 0x0042, 0x0004 },
- { 0x05, 0x00, -1, 0x03, 0x0042, 0x0005 },
- { 0x05, 0x00, -1, 0x03, 0x0042, 0x0006 },
- { 0x05, 0x00, -1, 0x03, 0x0042, 0x0007 },
- { 0x05, 0x00, -1, 0x03, 0x0042, 0x0008 },
- { 0x05, 0x00, -1, 0x03, 0x0042, 0x0009 },
- { 0x05, 0x00, -1, 0x00, 0x0062, 0x0002 },
- { 0x05, 0x00, -1, 0x01, 0x0062, 0x0003 },
- { 0x05, 0x00, -1, 0x02, 0x0062, 0x0004 },
- { 0x05, 0x00, -1, 0x03, 0x0062, 0x0005 },
- { 0x05, 0x00, -1, 0x03, 0x0062, 0x0006 },
- { 0x05, 0x00, -1, 0x03, 0x0062, 0x0007 },
- { 0x05, 0x00, -1, 0x03, 0x0062, 0x0008 },
- { 0x05, 0x00, -1, 0x03, 0x0062, 0x0009 },
- { 0x02, 0x01, -1, 0x03, 0x000a, 0x000a },
- { 0x02, 0x01, -1, 0x03, 0x000a, 0x000c },
- { 0x02, 0x02, -1, 0x03, 0x000a, 0x000e },
- { 0x02, 0x02, -1, 0x03, 0x000a, 0x0012 },
- { 0x02, 0x03, -1, 0x03, 0x000a, 0x0016 },
- { 0x02, 0x03, -1, 0x03, 0x000a, 0x001e },
- { 0x02, 0x04, -1, 0x03, 0x000a, 0x0026 },
- { 0x02, 0x04, -1, 0x03, 0x000a, 0x0036 },
- { 0x02, 0x01, -1, 0x03, 0x000e, 0x000a },
- { 0x02, 0x01, -1, 0x03, 0x000e, 0x000c },
- { 0x02, 0x02, -1, 0x03, 0x000e, 0x000e },
- { 0x02, 0x02, -1, 0x03, 0x000e, 0x0012 },
- { 0x02, 0x03, -1, 0x03, 0x000e, 0x0016 },
- { 0x02, 0x03, -1, 0x03, 0x000e, 0x001e },
- { 0x02, 0x04, -1, 0x03, 0x000e, 0x0026 },
- { 0x02, 0x04, -1, 0x03, 0x000e, 0x0036 },
- { 0x03, 0x01, -1, 0x03, 0x0012, 0x000a },
- { 0x03, 0x01, -1, 0x03, 0x0012, 0x000c },
- { 0x03, 0x02, -1, 0x03, 0x0012, 0x000e },
- { 0x03, 0x02, -1, 0x03, 0x0012, 0x0012 },
- { 0x03, 0x03, -1, 0x03, 0x0012, 0x0016 },
- { 0x03, 0x03, -1, 0x03, 0x0012, 0x001e },
- { 0x03, 0x04, -1, 0x03, 0x0012, 0x0026 },
- { 0x03, 0x04, -1, 0x03, 0x0012, 0x0036 },
- { 0x03, 0x01, -1, 0x03, 0x001a, 0x000a },
- { 0x03, 0x01, -1, 0x03, 0x001a, 0x000c },
- { 0x03, 0x02, -1, 0x03, 0x001a, 0x000e },
- { 0x03, 0x02, -1, 0x03, 0x001a, 0x0012 },
- { 0x03, 0x03, -1, 0x03, 0x001a, 0x0016 },
- { 0x03, 0x03, -1, 0x03, 0x001a, 0x001e },
- { 0x03, 0x04, -1, 0x03, 0x001a, 0x0026 },
- { 0x03, 0x04, -1, 0x03, 0x001a, 0x0036 },
- { 0x04, 0x01, -1, 0x03, 0x0022, 0x000a },
- { 0x04, 0x01, -1, 0x03, 0x0022, 0x000c },
- { 0x04, 0x02, -1, 0x03, 0x0022, 0x000e },
- { 0x04, 0x02, -1, 0x03, 0x0022, 0x0012 },
- { 0x04, 0x03, -1, 0x03, 0x0022, 0x0016 },
- { 0x04, 0x03, -1, 0x03, 0x0022, 0x001e },
- { 0x04, 0x04, -1, 0x03, 0x0022, 0x0026 },
- { 0x04, 0x04, -1, 0x03, 0x0022, 0x0036 },
- { 0x04, 0x01, -1, 0x03, 0x0032, 0x000a },
- { 0x04, 0x01, -1, 0x03, 0x0032, 0x000c },
- { 0x04, 0x02, -1, 0x03, 0x0032, 0x000e },
- { 0x04, 0x02, -1, 0x03, 0x0032, 0x0012 },
- { 0x04, 0x03, -1, 0x03, 0x0032, 0x0016 },
- { 0x04, 0x03, -1, 0x03, 0x0032, 0x001e },
- { 0x04, 0x04, -1, 0x03, 0x0032, 0x0026 },
- { 0x04, 0x04, -1, 0x03, 0x0032, 0x0036 },
- { 0x05, 0x01, -1, 0x03, 0x0042, 0x000a },
- { 0x05, 0x01, -1, 0x03, 0x0042, 0x000c },
- { 0x05, 0x02, -1, 0x03, 0x0042, 0x000e },
- { 0x05, 0x02, -1, 0x03, 0x0042, 0x0012 },
- { 0x05, 0x03, -1, 0x03, 0x0042, 0x0016 },
- { 0x05, 0x03, -1, 0x03, 0x0042, 0x001e },
- { 0x05, 0x04, -1, 0x03, 0x0042, 0x0026 },
- { 0x05, 0x04, -1, 0x03, 0x0042, 0x0036 },
- { 0x05, 0x01, -1, 0x03, 0x0062, 0x000a },
- { 0x05, 0x01, -1, 0x03, 0x0062, 0x000c },
- { 0x05, 0x02, -1, 0x03, 0x0062, 0x000e },
- { 0x05, 0x02, -1, 0x03, 0x0062, 0x0012 },
- { 0x05, 0x03, -1, 0x03, 0x0062, 0x0016 },
- { 0x05, 0x03, -1, 0x03, 0x0062, 0x001e },
- { 0x05, 0x04, -1, 0x03, 0x0062, 0x0026 },
- { 0x05, 0x04, -1, 0x03, 0x0062, 0x0036 },
- { 0x00, 0x05, -1, 0x03, 0x0000, 0x0046 },
- { 0x00, 0x05, -1, 0x03, 0x0000, 0x0066 },
- { 0x00, 0x06, -1, 0x03, 0x0000, 0x0086 },
- { 0x00, 0x07, -1, 0x03, 0x0000, 0x00c6 },
- { 0x00, 0x08, -1, 0x03, 0x0000, 0x0146 },
- { 0x00, 0x09, -1, 0x03, 0x0000, 0x0246 },
- { 0x00, 0x0a, -1, 0x03, 0x0000, 0x0446 },
- { 0x00, 0x18, -1, 0x03, 0x0000, 0x0846 },
- { 0x00, 0x05, -1, 0x03, 0x0001, 0x0046 },
- { 0x00, 0x05, -1, 0x03, 0x0001, 0x0066 },
- { 0x00, 0x06, -1, 0x03, 0x0001, 0x0086 },
- { 0x00, 0x07, -1, 0x03, 0x0001, 0x00c6 },
- { 0x00, 0x08, -1, 0x03, 0x0001, 0x0146 },
- { 0x00, 0x09, -1, 0x03, 0x0001, 0x0246 },
- { 0x00, 0x0a, -1, 0x03, 0x0001, 0x0446 },
- { 0x00, 0x18, -1, 0x03, 0x0001, 0x0846 },
- { 0x00, 0x05, -1, 0x03, 0x0002, 0x0046 },
- { 0x00, 0x05, -1, 0x03, 0x0002, 0x0066 },
- { 0x00, 0x06, -1, 0x03, 0x0002, 0x0086 },
- { 0x00, 0x07, -1, 0x03, 0x0002, 0x00c6 },
- { 0x00, 0x08, -1, 0x03, 0x0002, 0x0146 },
- { 0x00, 0x09, -1, 0x03, 0x0002, 0x0246 },
- { 0x00, 0x0a, -1, 0x03, 0x0002, 0x0446 },
- { 0x00, 0x18, -1, 0x03, 0x0002, 0x0846 },
- { 0x00, 0x05, -1, 0x03, 0x0003, 0x0046 },
- { 0x00, 0x05, -1, 0x03, 0x0003, 0x0066 },
- { 0x00, 0x06, -1, 0x03, 0x0003, 0x0086 },
- { 0x00, 0x07, -1, 0x03, 0x0003, 0x00c6 },
- { 0x00, 0x08, -1, 0x03, 0x0003, 0x0146 },
- { 0x00, 0x09, -1, 0x03, 0x0003, 0x0246 },
- { 0x00, 0x0a, -1, 0x03, 0x0003, 0x0446 },
- { 0x00, 0x18, -1, 0x03, 0x0003, 0x0846 },
- { 0x00, 0x05, -1, 0x03, 0x0004, 0x0046 },
- { 0x00, 0x05, -1, 0x03, 0x0004, 0x0066 },
- { 0x00, 0x06, -1, 0x03, 0x0004, 0x0086 },
- { 0x00, 0x07, -1, 0x03, 0x0004, 0x00c6 },
- { 0x00, 0x08, -1, 0x03, 0x0004, 0x0146 },
- { 0x00, 0x09, -1, 0x03, 0x0004, 0x0246 },
- { 0x00, 0x0a, -1, 0x03, 0x0004, 0x0446 },
- { 0x00, 0x18, -1, 0x03, 0x0004, 0x0846 },
- { 0x00, 0x05, -1, 0x03, 0x0005, 0x0046 },
- { 0x00, 0x05, -1, 0x03, 0x0005, 0x0066 },
- { 0x00, 0x06, -1, 0x03, 0x0005, 0x0086 },
- { 0x00, 0x07, -1, 0x03, 0x0005, 0x00c6 },
- { 0x00, 0x08, -1, 0x03, 0x0005, 0x0146 },
- { 0x00, 0x09, -1, 0x03, 0x0005, 0x0246 },
- { 0x00, 0x0a, -1, 0x03, 0x0005, 0x0446 },
- { 0x00, 0x18, -1, 0x03, 0x0005, 0x0846 },
- { 0x01, 0x05, -1, 0x03, 0x0006, 0x0046 },
- { 0x01, 0x05, -1, 0x03, 0x0006, 0x0066 },
- { 0x01, 0x06, -1, 0x03, 0x0006, 0x0086 },
- { 0x01, 0x07, -1, 0x03, 0x0006, 0x00c6 },
- { 0x01, 0x08, -1, 0x03, 0x0006, 0x0146 },
- { 0x01, 0x09, -1, 0x03, 0x0006, 0x0246 },
- { 0x01, 0x0a, -1, 0x03, 0x0006, 0x0446 },
- { 0x01, 0x18, -1, 0x03, 0x0006, 0x0846 },
- { 0x01, 0x05, -1, 0x03, 0x0008, 0x0046 },
- { 0x01, 0x05, -1, 0x03, 0x0008, 0x0066 },
- { 0x01, 0x06, -1, 0x03, 0x0008, 0x0086 },
- { 0x01, 0x07, -1, 0x03, 0x0008, 0x00c6 },
- { 0x01, 0x08, -1, 0x03, 0x0008, 0x0146 },
- { 0x01, 0x09, -1, 0x03, 0x0008, 0x0246 },
- { 0x01, 0x0a, -1, 0x03, 0x0008, 0x0446 },
- { 0x01, 0x18, -1, 0x03, 0x0008, 0x0846 },
- { 0x06, 0x00, -1, 0x00, 0x0082, 0x0002 },
- { 0x06, 0x00, -1, 0x01, 0x0082, 0x0003 },
- { 0x06, 0x00, -1, 0x02, 0x0082, 0x0004 },
- { 0x06, 0x00, -1, 0x03, 0x0082, 0x0005 },
- { 0x06, 0x00, -1, 0x03, 0x0082, 0x0006 },
- { 0x06, 0x00, -1, 0x03, 0x0082, 0x0007 },
- { 0x06, 0x00, -1, 0x03, 0x0082, 0x0008 },
- { 0x06, 0x00, -1, 0x03, 0x0082, 0x0009 },
- { 0x07, 0x00, -1, 0x00, 0x00c2, 0x0002 },
- { 0x07, 0x00, -1, 0x01, 0x00c2, 0x0003 },
- { 0x07, 0x00, -1, 0x02, 0x00c2, 0x0004 },
- { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0005 },
- { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0006 },
- { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0007 },
- { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0008 },
- { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0009 },
- { 0x08, 0x00, -1, 0x00, 0x0142, 0x0002 },
- { 0x08, 0x00, -1, 0x01, 0x0142, 0x0003 },
- { 0x08, 0x00, -1, 0x02, 0x0142, 0x0004 },
- { 0x08, 0x00, -1, 0x03, 0x0142, 0x0005 },
- { 0x08, 0x00, -1, 0x03, 0x0142, 0x0006 },
- { 0x08, 0x00, -1, 0x03, 0x0142, 0x0007 },
- { 0x08, 0x00, -1, 0x03, 0x0142, 0x0008 },
- { 0x08, 0x00, -1, 0x03, 0x0142, 0x0009 },
- { 0x09, 0x00, -1, 0x00, 0x0242, 0x0002 },
- { 0x09, 0x00, -1, 0x01, 0x0242, 0x0003 },
- { 0x09, 0x00, -1, 0x02, 0x0242, 0x0004 },
- { 0x09, 0x00, -1, 0x03, 0x0242, 0x0005 },
- { 0x09, 0x00, -1, 0x03, 0x0242, 0x0006 },
- { 0x09, 0x00, -1, 0x03, 0x0242, 0x0007 },
- { 0x09, 0x00, -1, 0x03, 0x0242, 0x0008 },
- { 0x09, 0x00, -1, 0x03, 0x0242, 0x0009 },
- { 0x0a, 0x00, -1, 0x00, 0x0442, 0x0002 },
- { 0x0a, 0x00, -1, 0x01, 0x0442, 0x0003 },
- { 0x0a, 0x00, -1, 0x02, 0x0442, 0x0004 },
- { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0005 },
- { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0006 },
- { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0007 },
- { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0008 },
- { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0009 },
- { 0x0c, 0x00, -1, 0x00, 0x0842, 0x0002 },
- { 0x0c, 0x00, -1, 0x01, 0x0842, 0x0003 },
- { 0x0c, 0x00, -1, 0x02, 0x0842, 0x0004 },
- { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0005 },
- { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0006 },
- { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0007 },
- { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0008 },
- { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0009 },
- { 0x0e, 0x00, -1, 0x00, 0x1842, 0x0002 },
- { 0x0e, 0x00, -1, 0x01, 0x1842, 0x0003 },
- { 0x0e, 0x00, -1, 0x02, 0x1842, 0x0004 },
- { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0005 },
- { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0006 },
- { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0007 },
- { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0008 },
- { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0009 },
- { 0x18, 0x00, -1, 0x00, 0x5842, 0x0002 },
- { 0x18, 0x00, -1, 0x01, 0x5842, 0x0003 },
- { 0x18, 0x00, -1, 0x02, 0x5842, 0x0004 },
- { 0x18, 0x00, -1, 0x03, 0x5842, 0x0005 },
- { 0x18, 0x00, -1, 0x03, 0x5842, 0x0006 },
- { 0x18, 0x00, -1, 0x03, 0x5842, 0x0007 },
- { 0x18, 0x00, -1, 0x03, 0x5842, 0x0008 },
- { 0x18, 0x00, -1, 0x03, 0x5842, 0x0009 },
- { 0x02, 0x05, -1, 0x03, 0x000a, 0x0046 },
- { 0x02, 0x05, -1, 0x03, 0x000a, 0x0066 },
- { 0x02, 0x06, -1, 0x03, 0x000a, 0x0086 },
- { 0x02, 0x07, -1, 0x03, 0x000a, 0x00c6 },
- { 0x02, 0x08, -1, 0x03, 0x000a, 0x0146 },
- { 0x02, 0x09, -1, 0x03, 0x000a, 0x0246 },
- { 0x02, 0x0a, -1, 0x03, 0x000a, 0x0446 },
- { 0x02, 0x18, -1, 0x03, 0x000a, 0x0846 },
- { 0x02, 0x05, -1, 0x03, 0x000e, 0x0046 },
- { 0x02, 0x05, -1, 0x03, 0x000e, 0x0066 },
- { 0x02, 0x06, -1, 0x03, 0x000e, 0x0086 },
- { 0x02, 0x07, -1, 0x03, 0x000e, 0x00c6 },
- { 0x02, 0x08, -1, 0x03, 0x000e, 0x0146 },
- { 0x02, 0x09, -1, 0x03, 0x000e, 0x0246 },
- { 0x02, 0x0a, -1, 0x03, 0x000e, 0x0446 },
- { 0x02, 0x18, -1, 0x03, 0x000e, 0x0846 },
- { 0x03, 0x05, -1, 0x03, 0x0012, 0x0046 },
- { 0x03, 0x05, -1, 0x03, 0x0012, 0x0066 },
- { 0x03, 0x06, -1, 0x03, 0x0012, 0x0086 },
- { 0x03, 0x07, -1, 0x03, 0x0012, 0x00c6 },
- { 0x03, 0x08, -1, 0x03, 0x0012, 0x0146 },
- { 0x03, 0x09, -1, 0x03, 0x0012, 0x0246 },
- { 0x03, 0x0a, -1, 0x03, 0x0012, 0x0446 },
- { 0x03, 0x18, -1, 0x03, 0x0012, 0x0846 },
- { 0x03, 0x05, -1, 0x03, 0x001a, 0x0046 },
- { 0x03, 0x05, -1, 0x03, 0x001a, 0x0066 },
- { 0x03, 0x06, -1, 0x03, 0x001a, 0x0086 },
- { 0x03, 0x07, -1, 0x03, 0x001a, 0x00c6 },
- { 0x03, 0x08, -1, 0x03, 0x001a, 0x0146 },
- { 0x03, 0x09, -1, 0x03, 0x001a, 0x0246 },
- { 0x03, 0x0a, -1, 0x03, 0x001a, 0x0446 },
- { 0x03, 0x18, -1, 0x03, 0x001a, 0x0846 },
- { 0x04, 0x05, -1, 0x03, 0x0022, 0x0046 },
- { 0x04, 0x05, -1, 0x03, 0x0022, 0x0066 },
- { 0x04, 0x06, -1, 0x03, 0x0022, 0x0086 },
- { 0x04, 0x07, -1, 0x03, 0x0022, 0x00c6 },
- { 0x04, 0x08, -1, 0x03, 0x0022, 0x0146 },
- { 0x04, 0x09, -1, 0x03, 0x0022, 0x0246 },
- { 0x04, 0x0a, -1, 0x03, 0x0022, 0x0446 },
- { 0x04, 0x18, -1, 0x03, 0x0022, 0x0846 },
- { 0x04, 0x05, -1, 0x03, 0x0032, 0x0046 },
- { 0x04, 0x05, -1, 0x03, 0x0032, 0x0066 },
- { 0x04, 0x06, -1, 0x03, 0x0032, 0x0086 },
- { 0x04, 0x07, -1, 0x03, 0x0032, 0x00c6 },
- { 0x04, 0x08, -1, 0x03, 0x0032, 0x0146 },
- { 0x04, 0x09, -1, 0x03, 0x0032, 0x0246 },
- { 0x04, 0x0a, -1, 0x03, 0x0032, 0x0446 },
- { 0x04, 0x18, -1, 0x03, 0x0032, 0x0846 },
- { 0x05, 0x05, -1, 0x03, 0x0042, 0x0046 },
- { 0x05, 0x05, -1, 0x03, 0x0042, 0x0066 },
- { 0x05, 0x06, -1, 0x03, 0x0042, 0x0086 },
- { 0x05, 0x07, -1, 0x03, 0x0042, 0x00c6 },
- { 0x05, 0x08, -1, 0x03, 0x0042, 0x0146 },
- { 0x05, 0x09, -1, 0x03, 0x0042, 0x0246 },
- { 0x05, 0x0a, -1, 0x03, 0x0042, 0x0446 },
- { 0x05, 0x18, -1, 0x03, 0x0042, 0x0846 },
- { 0x05, 0x05, -1, 0x03, 0x0062, 0x0046 },
- { 0x05, 0x05, -1, 0x03, 0x0062, 0x0066 },
- { 0x05, 0x06, -1, 0x03, 0x0062, 0x0086 },
- { 0x05, 0x07, -1, 0x03, 0x0062, 0x00c6 },
- { 0x05, 0x08, -1, 0x03, 0x0062, 0x0146 },
- { 0x05, 0x09, -1, 0x03, 0x0062, 0x0246 },
- { 0x05, 0x0a, -1, 0x03, 0x0062, 0x0446 },
- { 0x05, 0x18, -1, 0x03, 0x0062, 0x0846 },
- { 0x06, 0x01, -1, 0x03, 0x0082, 0x000a },
- { 0x06, 0x01, -1, 0x03, 0x0082, 0x000c },
- { 0x06, 0x02, -1, 0x03, 0x0082, 0x000e },
- { 0x06, 0x02, -1, 0x03, 0x0082, 0x0012 },
- { 0x06, 0x03, -1, 0x03, 0x0082, 0x0016 },
- { 0x06, 0x03, -1, 0x03, 0x0082, 0x001e },
- { 0x06, 0x04, -1, 0x03, 0x0082, 0x0026 },
- { 0x06, 0x04, -1, 0x03, 0x0082, 0x0036 },
- { 0x07, 0x01, -1, 0x03, 0x00c2, 0x000a },
- { 0x07, 0x01, -1, 0x03, 0x00c2, 0x000c },
- { 0x07, 0x02, -1, 0x03, 0x00c2, 0x000e },
- { 0x07, 0x02, -1, 0x03, 0x00c2, 0x0012 },
- { 0x07, 0x03, -1, 0x03, 0x00c2, 0x0016 },
- { 0x07, 0x03, -1, 0x03, 0x00c2, 0x001e },
- { 0x07, 0x04, -1, 0x03, 0x00c2, 0x0026 },
- { 0x07, 0x04, -1, 0x03, 0x00c2, 0x0036 },
- { 0x08, 0x01, -1, 0x03, 0x0142, 0x000a },
- { 0x08, 0x01, -1, 0x03, 0x0142, 0x000c },
- { 0x08, 0x02, -1, 0x03, 0x0142, 0x000e },
- { 0x08, 0x02, -1, 0x03, 0x0142, 0x0012 },
- { 0x08, 0x03, -1, 0x03, 0x0142, 0x0016 },
- { 0x08, 0x03, -1, 0x03, 0x0142, 0x001e },
- { 0x08, 0x04, -1, 0x03, 0x0142, 0x0026 },
- { 0x08, 0x04, -1, 0x03, 0x0142, 0x0036 },
- { 0x09, 0x01, -1, 0x03, 0x0242, 0x000a },
- { 0x09, 0x01, -1, 0x03, 0x0242, 0x000c },
- { 0x09, 0x02, -1, 0x03, 0x0242, 0x000e },
- { 0x09, 0x02, -1, 0x03, 0x0242, 0x0012 },
- { 0x09, 0x03, -1, 0x03, 0x0242, 0x0016 },
- { 0x09, 0x03, -1, 0x03, 0x0242, 0x001e },
- { 0x09, 0x04, -1, 0x03, 0x0242, 0x0026 },
- { 0x09, 0x04, -1, 0x03, 0x0242, 0x0036 },
- { 0x0a, 0x01, -1, 0x03, 0x0442, 0x000a },
- { 0x0a, 0x01, -1, 0x03, 0x0442, 0x000c },
- { 0x0a, 0x02, -1, 0x03, 0x0442, 0x000e },
- { 0x0a, 0x02, -1, 0x03, 0x0442, 0x0012 },
- { 0x0a, 0x03, -1, 0x03, 0x0442, 0x0016 },
- { 0x0a, 0x03, -1, 0x03, 0x0442, 0x001e },
- { 0x0a, 0x04, -1, 0x03, 0x0442, 0x0026 },
- { 0x0a, 0x04, -1, 0x03, 0x0442, 0x0036 },
- { 0x0c, 0x01, -1, 0x03, 0x0842, 0x000a },
- { 0x0c, 0x01, -1, 0x03, 0x0842, 0x000c },
- { 0x0c, 0x02, -1, 0x03, 0x0842, 0x000e },
- { 0x0c, 0x02, -1, 0x03, 0x0842, 0x0012 },
- { 0x0c, 0x03, -1, 0x03, 0x0842, 0x0016 },
- { 0x0c, 0x03, -1, 0x03, 0x0842, 0x001e },
- { 0x0c, 0x04, -1, 0x03, 0x0842, 0x0026 },
- { 0x0c, 0x04, -1, 0x03, 0x0842, 0x0036 },
- { 0x0e, 0x01, -1, 0x03, 0x1842, 0x000a },
- { 0x0e, 0x01, -1, 0x03, 0x1842, 0x000c },
- { 0x0e, 0x02, -1, 0x03, 0x1842, 0x000e },
- { 0x0e, 0x02, -1, 0x03, 0x1842, 0x0012 },
- { 0x0e, 0x03, -1, 0x03, 0x1842, 0x0016 },
- { 0x0e, 0x03, -1, 0x03, 0x1842, 0x001e },
- { 0x0e, 0x04, -1, 0x03, 0x1842, 0x0026 },
- { 0x0e, 0x04, -1, 0x03, 0x1842, 0x0036 },
- { 0x18, 0x01, -1, 0x03, 0x5842, 0x000a },
- { 0x18, 0x01, -1, 0x03, 0x5842, 0x000c },
- { 0x18, 0x02, -1, 0x03, 0x5842, 0x000e },
- { 0x18, 0x02, -1, 0x03, 0x5842, 0x0012 },
- { 0x18, 0x03, -1, 0x03, 0x5842, 0x0016 },
- { 0x18, 0x03, -1, 0x03, 0x5842, 0x001e },
- { 0x18, 0x04, -1, 0x03, 0x5842, 0x0026 },
- { 0x18, 0x04, -1, 0x03, 0x5842, 0x0036 },
- { 0x06, 0x05, -1, 0x03, 0x0082, 0x0046 },
- { 0x06, 0x05, -1, 0x03, 0x0082, 0x0066 },
- { 0x06, 0x06, -1, 0x03, 0x0082, 0x0086 },
- { 0x06, 0x07, -1, 0x03, 0x0082, 0x00c6 },
- { 0x06, 0x08, -1, 0x03, 0x0082, 0x0146 },
- { 0x06, 0x09, -1, 0x03, 0x0082, 0x0246 },
- { 0x06, 0x0a, -1, 0x03, 0x0082, 0x0446 },
- { 0x06, 0x18, -1, 0x03, 0x0082, 0x0846 },
- { 0x07, 0x05, -1, 0x03, 0x00c2, 0x0046 },
- { 0x07, 0x05, -1, 0x03, 0x00c2, 0x0066 },
- { 0x07, 0x06, -1, 0x03, 0x00c2, 0x0086 },
- { 0x07, 0x07, -1, 0x03, 0x00c2, 0x00c6 },
- { 0x07, 0x08, -1, 0x03, 0x00c2, 0x0146 },
- { 0x07, 0x09, -1, 0x03, 0x00c2, 0x0246 },
- { 0x07, 0x0a, -1, 0x03, 0x00c2, 0x0446 },
- { 0x07, 0x18, -1, 0x03, 0x00c2, 0x0846 },
- { 0x08, 0x05, -1, 0x03, 0x0142, 0x0046 },
- { 0x08, 0x05, -1, 0x03, 0x0142, 0x0066 },
- { 0x08, 0x06, -1, 0x03, 0x0142, 0x0086 },
- { 0x08, 0x07, -1, 0x03, 0x0142, 0x00c6 },
- { 0x08, 0x08, -1, 0x03, 0x0142, 0x0146 },
- { 0x08, 0x09, -1, 0x03, 0x0142, 0x0246 },
- { 0x08, 0x0a, -1, 0x03, 0x0142, 0x0446 },
- { 0x08, 0x18, -1, 0x03, 0x0142, 0x0846 },
- { 0x09, 0x05, -1, 0x03, 0x0242, 0x0046 },
- { 0x09, 0x05, -1, 0x03, 0x0242, 0x0066 },
- { 0x09, 0x06, -1, 0x03, 0x0242, 0x0086 },
- { 0x09, 0x07, -1, 0x03, 0x0242, 0x00c6 },
- { 0x09, 0x08, -1, 0x03, 0x0242, 0x0146 },
- { 0x09, 0x09, -1, 0x03, 0x0242, 0x0246 },
- { 0x09, 0x0a, -1, 0x03, 0x0242, 0x0446 },
- { 0x09, 0x18, -1, 0x03, 0x0242, 0x0846 },
- { 0x0a, 0x05, -1, 0x03, 0x0442, 0x0046 },
- { 0x0a, 0x05, -1, 0x03, 0x0442, 0x0066 },
- { 0x0a, 0x06, -1, 0x03, 0x0442, 0x0086 },
- { 0x0a, 0x07, -1, 0x03, 0x0442, 0x00c6 },
- { 0x0a, 0x08, -1, 0x03, 0x0442, 0x0146 },
- { 0x0a, 0x09, -1, 0x03, 0x0442, 0x0246 },
- { 0x0a, 0x0a, -1, 0x03, 0x0442, 0x0446 },
- { 0x0a, 0x18, -1, 0x03, 0x0442, 0x0846 },
- { 0x0c, 0x05, -1, 0x03, 0x0842, 0x0046 },
- { 0x0c, 0x05, -1, 0x03, 0x0842, 0x0066 },
- { 0x0c, 0x06, -1, 0x03, 0x0842, 0x0086 },
- { 0x0c, 0x07, -1, 0x03, 0x0842, 0x00c6 },
- { 0x0c, 0x08, -1, 0x03, 0x0842, 0x0146 },
- { 0x0c, 0x09, -1, 0x03, 0x0842, 0x0246 },
- { 0x0c, 0x0a, -1, 0x03, 0x0842, 0x0446 },
- { 0x0c, 0x18, -1, 0x03, 0x0842, 0x0846 },
- { 0x0e, 0x05, -1, 0x03, 0x1842, 0x0046 },
- { 0x0e, 0x05, -1, 0x03, 0x1842, 0x0066 },
- { 0x0e, 0x06, -1, 0x03, 0x1842, 0x0086 },
- { 0x0e, 0x07, -1, 0x03, 0x1842, 0x00c6 },
- { 0x0e, 0x08, -1, 0x03, 0x1842, 0x0146 },
- { 0x0e, 0x09, -1, 0x03, 0x1842, 0x0246 },
- { 0x0e, 0x0a, -1, 0x03, 0x1842, 0x0446 },
- { 0x0e, 0x18, -1, 0x03, 0x1842, 0x0846 },
- { 0x18, 0x05, -1, 0x03, 0x5842, 0x0046 },
- { 0x18, 0x05, -1, 0x03, 0x5842, 0x0066 },
- { 0x18, 0x06, -1, 0x03, 0x5842, 0x0086 },
- { 0x18, 0x07, -1, 0x03, 0x5842, 0x00c6 },
- { 0x18, 0x08, -1, 0x03, 0x5842, 0x0146 },
- { 0x18, 0x09, -1, 0x03, 0x5842, 0x0246 },
- { 0x18, 0x0a, -1, 0x03, 0x5842, 0x0446 },
- { 0x18, 0x18, -1, 0x03, 0x5842, 0x0846 },
-};
-
-#endif /* BROTLI_DEC_PREFIX_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/state.c b/BaseTools/Source/C/BrotliCompress/dec/state.c deleted file mode 100644 index 940abaaddb..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/state.c +++ /dev/null @@ -1,168 +0,0 @@ -/* Copyright 2015 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-#include "./state.h"
-
-#include <stdlib.h> /* free, malloc */
-
-#include "../common/types.h"
-#include "./huffman.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-static void* DefaultAllocFunc(void* opaque, size_t size) {
- BROTLI_UNUSED(opaque);
- return malloc(size);
-}
-
-static void DefaultFreeFunc(void* opaque, void* address) {
- BROTLI_UNUSED(opaque);
- free(address);
-}
-
-void BrotliDecoderStateInit(BrotliDecoderState* s) {
- BrotliDecoderStateInitWithCustomAllocators(s, 0, 0, 0);
-}
-
-void BrotliDecoderStateInitWithCustomAllocators(BrotliDecoderState* s,
- brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
- if (!alloc_func) {
- s->alloc_func = DefaultAllocFunc;
- s->free_func = DefaultFreeFunc;
- s->memory_manager_opaque = 0;
- } else {
- s->alloc_func = alloc_func;
- s->free_func = free_func;
- s->memory_manager_opaque = opaque;
- }
-
- BrotliInitBitReader(&s->br);
- s->state = BROTLI_STATE_UNINITED;
- s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;
- s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;
- s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;
- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
- s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
- s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
-
- 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->context_map = NULL;
- s->context_modes = NULL;
- s->dist_context_map = NULL;
- s->context_map_slice = NULL;
- s->dist_context_map_slice = NULL;
-
- s->sub_loop_counter = 0;
-
- s->literal_hgroup.codes = NULL;
- s->literal_hgroup.htrees = NULL;
- s->insert_copy_hgroup.codes = NULL;
- s->insert_copy_hgroup.htrees = NULL;
- s->distance_hgroup.codes = NULL;
- s->distance_hgroup.htrees = NULL;
-
- s->custom_dict = NULL;
- s->custom_dict_size = 0;
-
- s->is_last_metablock = 0;
- s->window_bits = 0;
- s->max_distance = 0;
- s->dist_rb[0] = 16;
- s->dist_rb[1] = 15;
- s->dist_rb[2] = 11;
- s->dist_rb[3] = 4;
- s->dist_rb_idx = 0;
- s->block_type_trees = NULL;
- s->block_len_trees = NULL;
-
- /* Make small negative indexes addressable. */
- s->symbol_lists = &s->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1];
-
- s->mtf_upper_bound = 255;
-}
-
-void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s) {
- s->meta_block_remaining_len = 0;
- s->block_length[0] = 1U << 28;
- s->block_length[1] = 1U << 28;
- s->block_length[2] = 1U << 28;
- s->num_block_types[0] = 1;
- s->num_block_types[1] = 1;
- s->num_block_types[2] = 1;
- s->block_type_rb[0] = 1;
- s->block_type_rb[1] = 0;
- s->block_type_rb[2] = 1;
- s->block_type_rb[3] = 0;
- s->block_type_rb[4] = 1;
- s->block_type_rb[5] = 0;
- s->context_map = NULL;
- s->context_modes = NULL;
- s->dist_context_map = NULL;
- s->context_map_slice = NULL;
- s->literal_htree = NULL;
- s->dist_context_map_slice = NULL;
- s->dist_htree_index = 0;
- s->context_lookup1 = NULL;
- s->context_lookup2 = NULL;
- s->literal_hgroup.codes = NULL;
- s->literal_hgroup.htrees = NULL;
- s->insert_copy_hgroup.codes = NULL;
- s->insert_copy_hgroup.htrees = NULL;
- s->distance_hgroup.codes = NULL;
- s->distance_hgroup.htrees = NULL;
-}
-
-void BrotliDecoderStateCleanupAfterMetablock(BrotliDecoderState* s) {
- BROTLI_FREE(s, s->context_modes);
- BROTLI_FREE(s, s->context_map);
- BROTLI_FREE(s, s->dist_context_map);
-
- BrotliDecoderHuffmanTreeGroupRelease(s, &s->literal_hgroup);
- BrotliDecoderHuffmanTreeGroupRelease(s, &s->insert_copy_hgroup);
- BrotliDecoderHuffmanTreeGroupRelease(s, &s->distance_hgroup);
-}
-
-void BrotliDecoderStateCleanup(BrotliDecoderState* s) {
- BrotliDecoderStateCleanupAfterMetablock(s);
-
- BROTLI_FREE(s, s->ringbuffer);
- BROTLI_FREE(s, s->block_type_trees);
-}
-
-void BrotliDecoderHuffmanTreeGroupInit(BrotliDecoderState* s,
- HuffmanTreeGroup* group, uint32_t alphabet_size, 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;
- char* p = (char*)BROTLI_ALLOC(s, code_size + htree_size);
- group->alphabet_size = (uint16_t)alphabet_size;
- group->num_htrees = (uint16_t)ntrees;
- group->codes = (HuffmanCode*)p;
- group->htrees = (HuffmanCode**)(p + code_size);
-}
-
-void BrotliDecoderHuffmanTreeGroupRelease(
- BrotliDecoderState* s, HuffmanTreeGroup* group) {
- BROTLI_FREE(s, group->codes);
- group->htrees = NULL;
-}
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
diff --git a/BaseTools/Source/C/BrotliCompress/dec/state.h b/BaseTools/Source/C/BrotliCompress/dec/state.h deleted file mode 100644 index 22681cbb97..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/state.h +++ /dev/null @@ -1,246 +0,0 @@ -/* Copyright 2015 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Brotli state for partial streaming decoding. */
-
-#ifndef BROTLI_DEC_STATE_H_
-#define BROTLI_DEC_STATE_H_
-
-#include "../common/constants.h"
-#include "../common/types.h"
-#include "./bit_reader.h"
-#include "./huffman.h"
-#include "./port.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-typedef enum {
- BROTLI_STATE_UNINITED,
- BROTLI_STATE_METABLOCK_BEGIN,
- BROTLI_STATE_METABLOCK_HEADER,
- BROTLI_STATE_METABLOCK_HEADER_2,
- BROTLI_STATE_CONTEXT_MODES,
- BROTLI_STATE_COMMAND_BEGIN,
- BROTLI_STATE_COMMAND_INNER,
- BROTLI_STATE_COMMAND_POST_DECODE_LITERALS,
- BROTLI_STATE_COMMAND_POST_WRAP_COPY,
- BROTLI_STATE_UNCOMPRESSED,
- BROTLI_STATE_METADATA,
- BROTLI_STATE_COMMAND_INNER_WRITE,
- BROTLI_STATE_METABLOCK_DONE,
- BROTLI_STATE_COMMAND_POST_WRITE_1,
- BROTLI_STATE_COMMAND_POST_WRITE_2,
- BROTLI_STATE_HUFFMAN_CODE_0,
- BROTLI_STATE_HUFFMAN_CODE_1,
- BROTLI_STATE_HUFFMAN_CODE_2,
- BROTLI_STATE_HUFFMAN_CODE_3,
- BROTLI_STATE_CONTEXT_MAP_1,
- BROTLI_STATE_CONTEXT_MAP_2,
- BROTLI_STATE_TREE_GROUP,
- BROTLI_STATE_DONE
-} BrotliRunningState;
-
-typedef enum {
- BROTLI_STATE_METABLOCK_HEADER_NONE,
- BROTLI_STATE_METABLOCK_HEADER_EMPTY,
- BROTLI_STATE_METABLOCK_HEADER_NIBBLES,
- BROTLI_STATE_METABLOCK_HEADER_SIZE,
- BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED,
- BROTLI_STATE_METABLOCK_HEADER_RESERVED,
- BROTLI_STATE_METABLOCK_HEADER_BYTES,
- BROTLI_STATE_METABLOCK_HEADER_METADATA
-} BrotliRunningMetablockHeaderState;
-
-typedef enum {
- BROTLI_STATE_UNCOMPRESSED_NONE,
- BROTLI_STATE_UNCOMPRESSED_WRITE
-} BrotliRunningUncompressedState;
-
-typedef enum {
- BROTLI_STATE_TREE_GROUP_NONE,
- BROTLI_STATE_TREE_GROUP_LOOP
-} BrotliRunningTreeGroupState;
-
-typedef enum {
- BROTLI_STATE_CONTEXT_MAP_NONE,
- BROTLI_STATE_CONTEXT_MAP_READ_PREFIX,
- BROTLI_STATE_CONTEXT_MAP_HUFFMAN,
- BROTLI_STATE_CONTEXT_MAP_DECODE,
- BROTLI_STATE_CONTEXT_MAP_TRANSFORM
-} BrotliRunningContextMapState;
-
-typedef enum {
- BROTLI_STATE_HUFFMAN_NONE,
- BROTLI_STATE_HUFFMAN_SIMPLE_SIZE,
- BROTLI_STATE_HUFFMAN_SIMPLE_READ,
- BROTLI_STATE_HUFFMAN_SIMPLE_BUILD,
- BROTLI_STATE_HUFFMAN_COMPLEX,
- BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS
-} BrotliRunningHuffmanState;
-
-typedef enum {
- BROTLI_STATE_DECODE_UINT8_NONE,
- BROTLI_STATE_DECODE_UINT8_SHORT,
- BROTLI_STATE_DECODE_UINT8_LONG
-} BrotliRunningDecodeUint8State;
-
-typedef enum {
- BROTLI_STATE_READ_BLOCK_LENGTH_NONE,
- BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
-} BrotliRunningReadBlockLengthState;
-
-struct BrotliDecoderStateStruct {
- BrotliRunningState state;
-
- /* This counter is reused for several disjoint loops. */
- int loop_counter;
-
- BrotliBitReader br;
-
- brotli_alloc_func alloc_func;
- brotli_free_func free_func;
- void* memory_manager_opaque;
-
- /* Temporary storage for remaining input. */
- union {
- uint64_t u64;
- uint8_t u8[8];
- } buffer;
- uint32_t buffer_length;
-
- int pos;
- int max_backward_distance;
- int max_backward_distance_minus_custom_dict_size;
- int max_distance;
- int ringbuffer_size;
- int ringbuffer_mask;
- int dist_rb_idx;
- int dist_rb[4];
- int error_code;
- uint32_t sub_loop_counter;
- uint8_t* ringbuffer;
- uint8_t* ringbuffer_end;
- HuffmanCode* htree_command;
- const uint8_t* context_lookup1;
- const uint8_t* context_lookup2;
- uint8_t* context_map_slice;
- uint8_t* dist_context_map_slice;
-
- /* This ring buffer holds a few past copy distances that will be used by */
- /* some special distance codes. */
- HuffmanTreeGroup literal_hgroup;
- HuffmanTreeGroup insert_copy_hgroup;
- HuffmanTreeGroup distance_hgroup;
- HuffmanCode* block_type_trees;
- HuffmanCode* block_len_trees;
- /* This is true if the literal context map histogram type always matches the
- block type. It is then not needed to keep the context (faster decoding). */
- int trivial_literal_context;
- 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;
- int distance_postfix_mask;
- uint32_t num_dist_htrees;
- uint8_t* dist_context_map;
- HuffmanCode* literal_htree;
- uint8_t dist_htree_index;
- uint32_t repeat_code_len;
- uint32_t prev_code_len;
-
- int copy_length;
- int distance_code;
-
- /* For partial write operations */
- size_t rb_roundtrips; /* How many times we went around the ringbuffer */
- size_t partial_pos_out; /* How much output to the user in total (<= rb) */
-
- /* For ReadHuffmanCode */
- uint32_t symbol;
- uint32_t repeat;
- uint32_t space;
-
- HuffmanCode table[32];
- /* List of of symbol chains. */
- uint16_t* symbol_lists;
- /* Storage from symbol_lists. */
- uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 +
- BROTLI_NUM_COMMAND_SYMBOLS];
- /* Tails of symbol chains. */
- int next_symbol[32];
- uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES];
- /* Population counts for the code lengths */
- uint16_t code_length_histo[16];
-
- /* For HuffmanTreeGroupDecode */
- int htree_index;
- HuffmanCode* next;
-
- /* For DecodeContextMap */
- uint32_t context_index;
- uint32_t max_run_length_prefix;
- uint32_t code;
- HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272];
-
- /* For InverseMoveToFrontTransform */
- uint32_t mtf_upper_bound;
- uint8_t mtf[256 + 4];
-
- /* For custom dictionaries */
- const uint8_t* custom_dict;
- int custom_dict_size;
-
- /* less used attributes are in the end of this struct */
- /* States inside function calls */
- BrotliRunningMetablockHeaderState substate_metablock_header;
- BrotliRunningTreeGroupState substate_tree_group;
- BrotliRunningContextMapState substate_context_map;
- BrotliRunningUncompressedState substate_uncompressed;
- BrotliRunningHuffmanState substate_huffman;
- BrotliRunningDecodeUint8State substate_decode_uint8;
- BrotliRunningReadBlockLengthState substate_read_block_length;
-
- uint8_t is_last_metablock;
- uint8_t is_uncompressed;
- uint8_t is_metadata;
- uint8_t size_nibbles;
- uint32_t window_bits;
-
- uint32_t num_literal_htrees;
- uint8_t* context_map;
- uint8_t* context_modes;
-
- uint32_t trivial_literal_contexts[8]; /* 256 bits */
-};
-
-typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal;
-#define BrotliDecoderState BrotliDecoderStateInternal
-
-BROTLI_INTERNAL void BrotliDecoderStateInit(BrotliDecoderState* s);
-BROTLI_INTERNAL void BrotliDecoderStateInitWithCustomAllocators(
- 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 void BrotliDecoderHuffmanTreeGroupInit(
- BrotliDecoderState* s, HuffmanTreeGroup* group, uint32_t alphabet_size,
- uint32_t ntrees);
-BROTLI_INTERNAL void BrotliDecoderHuffmanTreeGroupRelease(
- BrotliDecoderState* s, HuffmanTreeGroup* group);
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
-
-#endif /* BROTLI_DEC_STATE_H_ */
diff --git a/BaseTools/Source/C/BrotliCompress/dec/transform.h b/BaseTools/Source/C/BrotliCompress/dec/transform.h deleted file mode 100644 index 9d6501a452..0000000000 --- a/BaseTools/Source/C/BrotliCompress/dec/transform.h +++ /dev/null @@ -1,300 +0,0 @@ -/* Copyright 2013 Google Inc. All Rights Reserved.
-
- Distributed under MIT license.
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
-*/
-
-/* Transformations on dictionary words. */
-
-#ifndef BROTLI_DEC_TRANSFORM_H_
-#define BROTLI_DEC_TRANSFORM_H_
-
-#include "../common/types.h"
-#include "./port.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-enum WordTransformType {
- kIdentity = 0,
- kOmitLast1 = 1,
- kOmitLast2 = 2,
- kOmitLast3 = 3,
- kOmitLast4 = 4,
- kOmitLast5 = 5,
- kOmitLast6 = 6,
- kOmitLast7 = 7,
- kOmitLast8 = 8,
- kOmitLast9 = 9,
- kUppercaseFirst = 10,
- kUppercaseAll = 11,
- kOmitFirst1 = 12,
- kOmitFirst2 = 13,
- kOmitFirst3 = 14,
- kOmitFirst4 = 15,
- kOmitFirst5 = 16,
- kOmitFirst6 = 17,
- kOmitFirst7 = 18,
- kOmitFirst8 = 19,
- kOmitFirst9 = 20
-};
-
-typedef struct {
- const uint8_t prefix_id;
- const uint8_t transform;
- const uint8_t suffix_id;
-} Transform;
-
-static const char kPrefixSuffix[208] =
- "\0 \0, \0 of the \0 of \0s \0.\0 and \0 in \0\"\0 to \0\">\0\n\0. \0]\0"
- " for \0 a \0 that \0\'\0 with \0 from \0 by \0(\0. The \0 on \0 as \0"
- " is \0ing \0\n\t\0:\0ed \0=\"\0 at \0ly \0,\0=\'\0.com/\0. This \0"
- " not \0er \0al \0ful \0ive \0less \0est \0ize \0\xc2\xa0\0ous ";
-
-enum {
- /* EMPTY = ""
- SP = " "
- DQUOT = "\""
- SQUOT = "'"
- CLOSEBR = "]"
- OPEN = "("
- SLASH = "/"
- NBSP = non-breaking space "\0xc2\xa0"
- */
- kPFix_EMPTY = 0,
- kPFix_SP = 1,
- kPFix_COMMASP = 3,
- kPFix_SPofSPtheSP = 6,
- kPFix_SPtheSP = 9,
- kPFix_eSP = 12,
- kPFix_SPofSP = 15,
- kPFix_sSP = 20,
- kPFix_DOT = 23,
- kPFix_SPandSP = 25,
- kPFix_SPinSP = 31,
- kPFix_DQUOT = 36,
- kPFix_SPtoSP = 38,
- kPFix_DQUOTGT = 43,
- kPFix_NEWLINE = 46,
- kPFix_DOTSP = 48,
- kPFix_CLOSEBR = 51,
- kPFix_SPforSP = 53,
- kPFix_SPaSP = 59,
- kPFix_SPthatSP = 63,
- kPFix_SQUOT = 70,
- kPFix_SPwithSP = 72,
- kPFix_SPfromSP = 79,
- kPFix_SPbySP = 86,
- kPFix_OPEN = 91,
- kPFix_DOTSPTheSP = 93,
- kPFix_SPonSP = 100,
- kPFix_SPasSP = 105,
- kPFix_SPisSP = 110,
- kPFix_ingSP = 115,
- kPFix_NEWLINETAB = 120,
- kPFix_COLON = 123,
- kPFix_edSP = 125,
- kPFix_EQDQUOT = 129,
- kPFix_SPatSP = 132,
- kPFix_lySP = 137,
- kPFix_COMMA = 141,
- kPFix_EQSQUOT = 143,
- kPFix_DOTcomSLASH = 146,
- kPFix_DOTSPThisSP = 152,
- kPFix_SPnotSP = 160,
- kPFix_erSP = 166,
- kPFix_alSP = 170,
- kPFix_fulSP = 174,
- kPFix_iveSP = 179,
- kPFix_lessSP = 184,
- kPFix_estSP = 190,
- kPFix_izeSP = 195,
- kPFix_NBSP = 200,
- kPFix_ousSP = 203
-};
-
-static const Transform kTransforms[] = {
- { kPFix_EMPTY, kIdentity, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_SP },
- { kPFix_SP, kIdentity, kPFix_SP },
- { kPFix_EMPTY, kOmitFirst1, kPFix_EMPTY },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_SP },
- { kPFix_EMPTY, kIdentity, kPFix_SPtheSP },
- { kPFix_SP, kIdentity, kPFix_EMPTY },
- { kPFix_sSP, kIdentity, kPFix_SP },
- { kPFix_EMPTY, kIdentity, kPFix_SPofSP },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_SPandSP },
- { kPFix_EMPTY, kOmitFirst2, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitLast1, kPFix_EMPTY },
- { kPFix_COMMASP, kIdentity, kPFix_SP },
- { kPFix_EMPTY, kIdentity, kPFix_COMMASP },
- { kPFix_SP, kUppercaseFirst, kPFix_SP },
- { kPFix_EMPTY, kIdentity, kPFix_SPinSP },
- { kPFix_EMPTY, kIdentity, kPFix_SPtoSP },
- { kPFix_eSP, kIdentity, kPFix_SP },
- { kPFix_EMPTY, kIdentity, kPFix_DQUOT },
- { kPFix_EMPTY, kIdentity, kPFix_DOT },
- { kPFix_EMPTY, kIdentity, kPFix_DQUOTGT },
- { kPFix_EMPTY, kIdentity, kPFix_NEWLINE },
- { kPFix_EMPTY, kOmitLast3, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_CLOSEBR },
- { kPFix_EMPTY, kIdentity, kPFix_SPforSP },
- { kPFix_EMPTY, kOmitFirst3, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitLast2, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_SPaSP },
- { kPFix_EMPTY, kIdentity, kPFix_SPthatSP },
- { kPFix_SP, kUppercaseFirst, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_DOTSP },
- { kPFix_DOT, kIdentity, kPFix_EMPTY },
- { kPFix_SP, kIdentity, kPFix_COMMASP },
- { kPFix_EMPTY, kOmitFirst4, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_SPwithSP },
- { kPFix_EMPTY, kIdentity, kPFix_SQUOT },
- { kPFix_EMPTY, kIdentity, kPFix_SPfromSP },
- { kPFix_EMPTY, kIdentity, kPFix_SPbySP },
- { kPFix_EMPTY, kOmitFirst5, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitFirst6, kPFix_EMPTY },
- { kPFix_SPtheSP, kIdentity, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitLast4, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_DOTSPTheSP },
- { kPFix_EMPTY, kUppercaseAll, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_SPonSP },
- { kPFix_EMPTY, kIdentity, kPFix_SPasSP },
- { kPFix_EMPTY, kIdentity, kPFix_SPisSP },
- { kPFix_EMPTY, kOmitLast7, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitLast1, kPFix_ingSP },
- { kPFix_EMPTY, kIdentity, kPFix_NEWLINETAB },
- { kPFix_EMPTY, kIdentity, kPFix_COLON },
- { kPFix_SP, kIdentity, kPFix_DOTSP },
- { kPFix_EMPTY, kIdentity, kPFix_edSP },
- { kPFix_EMPTY, kOmitFirst9, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitFirst7, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitLast6, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_OPEN },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_COMMASP },
- { kPFix_EMPTY, kOmitLast8, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_SPatSP },
- { kPFix_EMPTY, kIdentity, kPFix_lySP },
- { kPFix_SPtheSP, kIdentity, kPFix_SPofSP },
- { kPFix_EMPTY, kOmitLast5, kPFix_EMPTY },
- { kPFix_EMPTY, kOmitLast9, kPFix_EMPTY },
- { kPFix_SP, kUppercaseFirst, kPFix_COMMASP },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_DQUOT },
- { kPFix_DOT, kIdentity, kPFix_OPEN },
- { kPFix_EMPTY, kUppercaseAll, kPFix_SP },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_DQUOTGT },
- { kPFix_EMPTY, kIdentity, kPFix_EQDQUOT },
- { kPFix_SP, kIdentity, kPFix_DOT },
- { kPFix_DOTcomSLASH, kIdentity, kPFix_EMPTY },
- { kPFix_SPtheSP, kIdentity, kPFix_SPofSPtheSP },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_SQUOT },
- { kPFix_EMPTY, kIdentity, kPFix_DOTSPThisSP },
- { kPFix_EMPTY, kIdentity, kPFix_COMMA },
- { kPFix_DOT, kIdentity, kPFix_SP },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_OPEN },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_DOT },
- { kPFix_EMPTY, kIdentity, kPFix_SPnotSP },
- { kPFix_SP, kIdentity, kPFix_EQDQUOT },
- { kPFix_EMPTY, kIdentity, kPFix_erSP },
- { kPFix_SP, kUppercaseAll, kPFix_SP },
- { kPFix_EMPTY, kIdentity, kPFix_alSP },
- { kPFix_SP, kUppercaseAll, kPFix_EMPTY },
- { kPFix_EMPTY, kIdentity, kPFix_EQSQUOT },
- { kPFix_EMPTY, kUppercaseAll, kPFix_DQUOT },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_DOTSP },
- { kPFix_SP, kIdentity, kPFix_OPEN },
- { kPFix_EMPTY, kIdentity, kPFix_fulSP },
- { kPFix_SP, kUppercaseFirst, kPFix_DOTSP },
- { kPFix_EMPTY, kIdentity, kPFix_iveSP },
- { kPFix_EMPTY, kIdentity, kPFix_lessSP },
- { kPFix_EMPTY, kUppercaseAll, kPFix_SQUOT },
- { kPFix_EMPTY, kIdentity, kPFix_estSP },
- { kPFix_SP, kUppercaseFirst, kPFix_DOT },
- { kPFix_EMPTY, kUppercaseAll, kPFix_DQUOTGT },
- { kPFix_SP, kIdentity, kPFix_EQSQUOT },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_COMMA },
- { kPFix_EMPTY, kIdentity, kPFix_izeSP },
- { kPFix_EMPTY, kUppercaseAll, kPFix_DOT },
- { kPFix_NBSP, kIdentity, kPFix_EMPTY },
- { kPFix_SP, kIdentity, kPFix_COMMA },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_EQDQUOT },
- { kPFix_EMPTY, kUppercaseAll, kPFix_EQDQUOT },
- { kPFix_EMPTY, kIdentity, kPFix_ousSP },
- { kPFix_EMPTY, kUppercaseAll, kPFix_COMMASP },
- { kPFix_EMPTY, kUppercaseFirst, kPFix_EQSQUOT },
- { kPFix_SP, kUppercaseFirst, kPFix_COMMA },
- { kPFix_SP, kUppercaseAll, kPFix_EQDQUOT },
- { kPFix_SP, kUppercaseAll, kPFix_COMMASP },
- { kPFix_EMPTY, kUppercaseAll, kPFix_COMMA },
- { kPFix_EMPTY, kUppercaseAll, kPFix_OPEN },
- { kPFix_EMPTY, kUppercaseAll, kPFix_DOTSP },
- { kPFix_SP, kUppercaseAll, kPFix_DOT },
- { kPFix_EMPTY, kUppercaseAll, kPFix_EQSQUOT },
- { kPFix_SP, kUppercaseAll, kPFix_DOTSP },
- { kPFix_SP, kUppercaseFirst, kPFix_EQDQUOT },
- { kPFix_SP, kUppercaseAll, kPFix_EQSQUOT },
- { kPFix_SP, kUppercaseFirst, kPFix_EQSQUOT },
-};
-
-static const int kNumTransforms = sizeof(kTransforms) / sizeof(kTransforms[0]);
-
-static int ToUpperCase(uint8_t* p) {
- if (p[0] < 0xc0) {
- if (p[0] >= 'a' && p[0] <= 'z') {
- p[0] ^= 32;
- }
- return 1;
- }
- /* An overly simplified uppercasing model for utf-8. */
- if (p[0] < 0xe0) {
- p[1] ^= 32;
- return 2;
- }
- /* An arbitrary transform for three byte characters. */
- p[2] ^= 5;
- return 3;
-}
-
-static BROTLI_NOINLINE int TransformDictionaryWord(
- uint8_t* dst, const uint8_t* word, int len, int transform) {
- int idx = 0;
- {
- const char* prefix = &kPrefixSuffix[kTransforms[transform].prefix_id];
- while (*prefix) { dst[idx++] = (uint8_t)*prefix++; }
- }
- {
- const int t = kTransforms[transform].transform;
- int i = 0;
- int skip = t - (kOmitFirst1 - 1);
- if (skip > 0) {
- word += skip;
- len -= skip;
- } else if (t <= kOmitLast9) {
- len -= t;
- }
- while (i < len) { dst[idx++] = word[i++]; }
- if (t == kUppercaseFirst) {
- ToUpperCase(&dst[idx - len]);
- } else if (t == kUppercaseAll) {
- uint8_t* uppercase = &dst[idx - len];
- while (len > 0) {
- int step = ToUpperCase(uppercase);
- uppercase += step;
- len -= step;
- }
- }
- }
- {
- const char* suffix = &kPrefixSuffix[kTransforms[transform].suffix_id];
- while (*suffix) { dst[idx++] = (uint8_t)*suffix++; }
- return idx;
- }
-}
-
-#if defined(__cplusplus) || defined(c_plusplus)
-} /* extern "C" */
-#endif
-
-#endif /* BROTLI_DEC_TRANSFORM_H_ */
|