summaryrefslogtreecommitdiffstats
path: root/modules/brotli/dec/decode.c
diff options
context:
space:
mode:
Diffstat (limited to 'modules/brotli/dec/decode.c')
-rw-r--r--modules/brotli/dec/decode.c1802
1 files changed, 1023 insertions, 779 deletions
diff --git a/modules/brotli/dec/decode.c b/modules/brotli/dec/decode.c
index d184f24cb..08bd76ca1 100644
--- a/modules/brotli/dec/decode.c
+++ b/modules/brotli/dec/decode.c
@@ -4,23 +4,25 @@
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 <brotli/decode.h>
#include <stdlib.h> /* free, malloc */
#include <string.h> /* memcpy, memset */
+#include "../common/constants.h"
+#include "../common/context.h"
+#include "../common/dictionary.h"
+#include "../common/platform.h"
+#include "../common/transform.h"
+#include "../common/version.h"
#include "./bit_reader.h"
-#include "./context.h"
-#include "./dictionary.h"
#include "./huffman.h"
-#include "./port.h"
#include "./prefix.h"
#include "./state.h"
-#include "./transform.h"
+
+#if defined(BROTLI_TARGET_NEON)
+#include <arm_neon.h>
+#endif
#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
@@ -34,19 +36,15 @@ extern "C" {
BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \
(unsigned long)(idx), (unsigned long)array_name[idx]))
-static const uint32_t kDefaultCodeLength = 8;
-static const uint32_t kCodeLengthRepeatCode = 16;
-static const uint32_t kNumLiteralCodes = 256;
-static const uint32_t kNumInsertAndCopyCodes = 704;
-static const uint32_t kNumBlockLengthCodes = 26;
-static const int kLiteralContextBits = 6;
-static const int kDistanceContextBits = 2;
-
#define HUFFMAN_TABLE_BITS 8U
-#define HUFFMAN_TABLE_MASK 0xff
+#define HUFFMAN_TABLE_MASK 0xFF
+
+/* We need the slack region for the following reasons:
+ - doing up to two 16-byte copies for fast backward copying
+ - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */
+static const uint32_t kRingBufferWriteAheadSlack = 42;
-#define CODE_LENGTH_CODES 18
-static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = {
+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,
};
@@ -59,70 +57,117 @@ static const uint8_t kCodeLengthPrefixValue[16] = {
0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,
};
-#define NUM_DISTANCE_SHORT_CODES 16
+BROTLI_BOOL BrotliDecoderSetParameter(
+ BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) {
+ if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE;
+ switch (p) {
+ case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION:
+ state->canny_ringbuffer_allocation = !!value ? 0 : 1;
+ return BROTLI_TRUE;
-BrotliState* BrotliCreateState(
+ case BROTLI_DECODER_PARAM_LARGE_WINDOW:
+ state->large_window = TO_BROTLI_BOOL(!!value);
+ return BROTLI_TRUE;
+
+ default: return BROTLI_FALSE;
+ }
+}
+
+BrotliDecoderState* BrotliDecoderCreateInstance(
brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
- BrotliState* state = 0;
+ BrotliDecoderState* state = 0;
if (!alloc_func && !free_func) {
- state = (BrotliState*)malloc(sizeof(BrotliState));
+ state = (BrotliDecoderState*)malloc(sizeof(BrotliDecoderState));
} else if (alloc_func && free_func) {
- state = (BrotliState*)alloc_func(opaque, sizeof(BrotliState));
+ state = (BrotliDecoderState*)alloc_func(opaque, sizeof(BrotliDecoderState));
}
if (state == 0) {
BROTLI_DUMP();
return 0;
}
- BrotliStateInitWithCustomAllocators(state, alloc_func, free_func, opaque);
- state->error_code = BROTLI_NO_ERROR;
+ if (!BrotliDecoderStateInit(state, alloc_func, free_func, opaque)) {
+ BROTLI_DUMP();
+ if (!alloc_func && !free_func) {
+ free(state);
+ } else if (alloc_func && free_func) {
+ free_func(opaque, state);
+ }
+ return 0;
+ }
return state;
}
-/* Deinitializes and frees BrotliState instance. */
-void BrotliDestroyState(BrotliState* 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;
- BrotliStateCleanup(state);
+ BrotliDecoderStateCleanup(state);
free_func(opaque, state);
}
}
-/* Saves error code and converts it to BrotliResult */
-static BROTLI_NOINLINE BrotliResult SaveErrorCode(
- BrotliState* s, BrotliErrorCode e) {
+/* 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_SUCCESS: return BROTLI_RESULT_SUCCESS;
- case BROTLI_NEEDS_MORE_INPUT: return BROTLI_RESULT_NEEDS_MORE_INPUT;
- case BROTLI_NEEDS_MORE_OUTPUT: return BROTLI_RESULT_NEEDS_MORE_OUTPUT;
- default: return BROTLI_RESULT_ERROR;
+ 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) {
+/* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli".
+ Precondition: bit-reader accumulator has at least 8 bits. */
+static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s,
+ BrotliBitReader* br) {
uint32_t n;
+ BROTLI_BOOL large_window = s->large_window;
+ s->large_window = BROTLI_FALSE;
BrotliTakeBits(br, 1, &n);
if (n == 0) {
- return 16;
+ s->window_bits = 16;
+ return BROTLI_DECODER_SUCCESS;
}
BrotliTakeBits(br, 3, &n);
if (n != 0) {
- return 17 + n;
+ s->window_bits = 17 + n;
+ return BROTLI_DECODER_SUCCESS;
}
BrotliTakeBits(br, 3, &n);
+ if (n == 1) {
+ if (large_window) {
+ BrotliTakeBits(br, 1, &n);
+ if (n == 1) {
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
+ }
+ s->large_window = BROTLI_TRUE;
+ return BROTLI_DECODER_SUCCESS;
+ } else {
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
+ }
+ }
if (n != 0) {
- return 8 + n;
+ s->window_bits = 8 + n;
+ return BROTLI_DECODER_SUCCESS;
}
- return 17;
+ s->window_bits = 17;
+ return BROTLI_DECODER_SUCCESS;
}
static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) {
-#if defined(__ARM_NEON__)
+#if defined(BROTLI_TARGET_NEON)
vst1q_u8(dst, vld1q_u8(src));
#else
uint32_t buffer[4];
@@ -132,60 +177,61 @@ static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) {
}
/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
-static BROTLI_NOINLINE BrotliErrorCode DecodeVarLenUint8(BrotliState* s,
- BrotliBitReader* br, uint32_t* value) {
+static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8(
+ BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) {
uint32_t bits;
switch (s->substate_decode_uint8) {
case BROTLI_STATE_DECODE_UINT8_NONE:
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) {
- return BROTLI_NEEDS_MORE_INPUT;
+ if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) {
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (bits == 0) {
*value = 0;
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
- /* No break, transit to the next state. */
+ /* Fall through. */
case BROTLI_STATE_DECODE_UINT8_SHORT:
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) {
+ if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) {
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (bits == 0) {
*value = 1;
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
/* Use output value as a temporary storage. It MUST be persisted. */
*value = bits;
- /* No break, transit to the next state. */
+ /* Fall through. */
case BROTLI_STATE_DECODE_UINT8_LONG:
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) {
+ if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) {
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
*value = (1U << *value) + bits;
s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
default:
- return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE);
+ return
+ BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
}
}
/* Decodes a metablock length and flags by reading 2 - 31 bits. */
-static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
- BrotliState* s, BrotliBitReader* br) {
+static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
+ BrotliDecoderState* s, BrotliBitReader* br) {
uint32_t bits;
int i;
for (;;) {
switch (s->substate_metablock_header) {
case BROTLI_STATE_METABLOCK_HEADER_NONE:
if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
- s->is_last_metablock = (uint8_t)bits;
+ s->is_last_metablock = bits ? 1 : 0;
s->meta_block_remaining_len = 0;
s->is_uncompressed = 0;
s->is_metadata = 0;
@@ -194,22 +240,22 @@ static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
break;
}
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY;
- /* No break, transit to the next state. */
+ /* Fall through. */
case BROTLI_STATE_METABLOCK_HEADER_EMPTY:
if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (bits) {
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
- /* No break, transit to the next state. */
+ /* Fall through. */
case BROTLI_STATE_METABLOCK_HEADER_NIBBLES:
if (!BrotliSafeReadBits(br, 2, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
s->size_nibbles = (uint8_t)(bits + 4);
s->loop_counter = 0;
@@ -219,75 +265,77 @@ static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
break;
}
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE;
- /* No break, transit to the next state. */
+ /* Fall through. */
case BROTLI_STATE_METABLOCK_HEADER_SIZE:
i = s->loop_counter;
- for (; i < s->size_nibbles; ++i) {
+ for (; i < (int)s->size_nibbles; ++i) {
if (!BrotliSafeReadBits(br, 4, &bits)) {
s->loop_counter = i;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (i + 1 == s->size_nibbles && s->size_nibbles > 4 && bits == 0) {
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_EXUBERANT_NIBBLE);
+ 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. */
+ /* Fall through. */
case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED:
if (!s->is_last_metablock) {
if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
- s->is_uncompressed = (uint8_t)bits;
+ s->is_uncompressed = bits ? 1 : 0;
}
++s->meta_block_remaining_len;
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
case BROTLI_STATE_METABLOCK_HEADER_RESERVED:
if (!BrotliSafeReadBits(br, 1, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (bits != 0) {
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_RESERVED);
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED);
}
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES;
- /* No break, transit to the next state. */
+ /* Fall through. */
case BROTLI_STATE_METABLOCK_HEADER_BYTES:
if (!BrotliSafeReadBits(br, 2, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (bits == 0) {
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_SUCCESS;
+ 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. */
+ /* Fall through. */
case BROTLI_STATE_METABLOCK_HEADER_METADATA:
i = s->loop_counter;
- for (; i < s->size_nibbles; ++i) {
+ for (; i < (int)s->size_nibbles; ++i) {
if (!BrotliSafeReadBits(br, 8, &bits)) {
s->loop_counter = i;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
if (i + 1 == s->size_nibbles && s->size_nibbles > 1 && bits == 0) {
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_EXUBERANT_META_NIBBLE);
+ return BROTLI_FAILURE(
+ BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE);
}
s->meta_block_remaining_len |= (int)(bits << (i * 8));
}
++s->meta_block_remaining_len;
s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
default:
- return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE);
+ return
+ BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
}
}
}
@@ -299,15 +347,17 @@ static BrotliErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits,
const HuffmanCode* table,
BrotliBitReader* br) {
- table += bits & HUFFMAN_TABLE_MASK;
- if (table->bits > HUFFMAN_TABLE_BITS) {
- uint32_t nbits = table->bits - HUFFMAN_TABLE_BITS;
+ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
+ BROTLI_HC_ADJUST_TABLE_INDEX(table, bits & HUFFMAN_TABLE_MASK);
+ if (BROTLI_HC_FAST_LOAD_BITS(table) > HUFFMAN_TABLE_BITS) {
+ uint32_t nbits = BROTLI_HC_FAST_LOAD_BITS(table) - HUFFMAN_TABLE_BITS;
BrotliDropBits(br, HUFFMAN_TABLE_BITS);
- table += table->value;
- table += (bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits);
+ BROTLI_HC_ADJUST_TABLE_INDEX(table,
+ BROTLI_HC_FAST_LOAD_VALUE(table) +
+ ((bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits)));
}
- BrotliDropBits(br, table->bits);
- return table->value;
+ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table));
+ return BROTLI_HC_FAST_LOAD_VALUE(table);
}
/* Reads and decodes the next Huffman code from bit-stream.
@@ -319,53 +369,52 @@ static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table,
/* Same as DecodeSymbol, but it is known that there is less than 15 bits of
input are currently available. */
-static BROTLI_NOINLINE int SafeDecodeSymbol(const HuffmanCode* table,
- BrotliBitReader* br,
- uint32_t* result) {
+static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol(
+ const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
uint32_t val;
uint32_t available_bits = BrotliGetAvailableBits(br);
+ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
if (available_bits == 0) {
- if (table->bits == 0) {
- *result = table->value;
- return 1;
+ if (BROTLI_HC_FAST_LOAD_BITS(table) == 0) {
+ *result = BROTLI_HC_FAST_LOAD_VALUE(table);
+ return BROTLI_TRUE;
}
- return 0; /* No valid bits at all. */
+ 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 1;
+ BROTLI_HC_ADJUST_TABLE_INDEX(table, val & HUFFMAN_TABLE_MASK);
+ if (BROTLI_HC_FAST_LOAD_BITS(table) <= HUFFMAN_TABLE_BITS) {
+ if (BROTLI_HC_FAST_LOAD_BITS(table) <= available_bits) {
+ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table));
+ *result = BROTLI_HC_FAST_LOAD_VALUE(table);
+ return BROTLI_TRUE;
} else {
- return 0; /* Not enough bits for the first level. */
+ return BROTLI_FALSE; /* Not enough bits for the first level. */
}
}
if (available_bits <= HUFFMAN_TABLE_BITS) {
- return 0; /* Not enough bits to move to the second level. */
+ 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;
+ val = (val & BitMask(BROTLI_HC_FAST_LOAD_BITS(table))) >> HUFFMAN_TABLE_BITS;
available_bits -= HUFFMAN_TABLE_BITS;
- table += table->value + val;
- if (available_bits < table->bits) {
- return 0; /* Not enough bits for the second level. */
+ BROTLI_HC_ADJUST_TABLE_INDEX(table, BROTLI_HC_FAST_LOAD_VALUE(table) + val);
+ if (available_bits < BROTLI_HC_FAST_LOAD_BITS(table)) {
+ return BROTLI_FALSE; /* Not enough bits for the second level. */
}
- BrotliDropBits(br, HUFFMAN_TABLE_BITS + table->bits);
- *result = table->value;
- return 1;
+ BrotliDropBits(br, HUFFMAN_TABLE_BITS + BROTLI_HC_FAST_LOAD_BITS(table));
+ *result = BROTLI_HC_FAST_LOAD_VALUE(table);
+ return BROTLI_TRUE;
}
-static BROTLI_INLINE int SafeReadSymbol(const HuffmanCode* table,
- BrotliBitReader* br,
- uint32_t* result) {
+static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol(
+ const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
uint32_t val;
- if (PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {
+ if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {
*result = DecodeSymbol(val, table, br);
- return 1;
+ return BROTLI_TRUE;
}
return SafeDecodeSymbol(table, br, result);
}
@@ -379,9 +428,10 @@ static BROTLI_INLINE void PreloadSymbol(int safe,
if (safe) {
return;
}
- table += BrotliGetBits(br, HUFFMAN_TABLE_BITS);
- *bits = table->bits;
- *value = table->value;
+ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
+ BROTLI_HC_ADJUST_TABLE_INDEX(table, BrotliGetBits(br, HUFFMAN_TABLE_BITS));
+ *bits = BROTLI_HC_FAST_LOAD_BITS(table);
+ *value = BROTLI_HC_FAST_LOAD_VALUE(table);
}
/* Decodes the next Huffman code using data prepared by PreloadSymbol.
@@ -391,14 +441,15 @@ static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table,
uint32_t* bits,
uint32_t* value) {
uint32_t result = *value;
- if (PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {
+ if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {
uint32_t val = BrotliGet16BitsUnmasked(br);
const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value;
uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS));
+ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(ext);
BrotliDropBits(br, HUFFMAN_TABLE_BITS);
- ext += (val >> HUFFMAN_TABLE_BITS) & mask;
- BrotliDropBits(br, ext->bits);
- result = ext->value;
+ BROTLI_HC_ADJUST_TABLE_INDEX(ext, (val >> HUFFMAN_TABLE_BITS) & mask);
+ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(ext));
+ result = BROTLI_HC_FAST_LOAD_VALUE(ext);
} else {
BrotliDropBits(br, *bits);
}
@@ -416,25 +467,25 @@ static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) {
}
/* Reads (s->symbol + 1) symbols.
- Totally 1..4 symbols are read, 1..10 bits each.
- The list of symbols MUST NOT contain duplicates.
- */
-static BrotliErrorCode ReadSimpleHuffmanSymbols(uint32_t alphabet_size,
- BrotliState* s) {
- /* max_bits == 1..10; symbol == 0..3; 1..40 bits will be read. */
+ Totally 1..4 symbols are read, 1..11 bits each.
+ The list of symbols MUST NOT contain duplicates. */
+static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols(
+ uint32_t alphabet_size, uint32_t max_symbol, BrotliDecoderState* s) {
+ /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */
BrotliBitReader* br = &s->br;
uint32_t max_bits = Log2Floor(alphabet_size - 1);
uint32_t i = s->sub_loop_counter;
uint32_t num_symbols = s->symbol;
while (i <= num_symbols) {
uint32_t v;
- if (PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) {
+ if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) {
s->sub_loop_counter = i;
s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
- if (v >= alphabet_size) {
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET);
+ if (v >= max_symbol) {
+ return
+ BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET);
}
s->symbols_lists_array[i] = (uint16_t)v;
BROTLI_LOG_UINT(s->symbols_lists_array[i]);
@@ -445,55 +496,58 @@ static BrotliErrorCode ReadSimpleHuffmanSymbols(uint32_t alphabet_size,
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_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME);
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME);
}
}
}
- return BROTLI_SUCCESS;
+ 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
- */
+ C) extend corresponding index-chain
+ D) reduce the Huffman space
+ E) update the histogram */
static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len,
uint32_t* symbol, uint32_t* repeat, uint32_t* space,
uint32_t* prev_code_len, uint16_t* symbol_lists,
uint16_t* code_length_histo, int* next_symbol) {
*repeat = 0;
- if (code_len != 0) { /* code_len == 1..15 */
+ 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));
+ BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n",
+ (int)*symbol, (int)code_len));
}
(*symbol)++;
}
/* Process repeated symbol code length.
A) Check if it is the extension of previous repeat sequence; if the decoded
- value is not kCodeLengthRepeatCode, then it is a new symbol-skip
+ 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)
+ C) Check if operation is feasible (fits alphabet)
D) For each symbol do the same operations as in ProcessSingleCodeLength
- PRECONDITION: code_len == kCodeLengthRepeatCode or kCodeLengthRepeatCode + 1
- */
+ 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 new_len = 0;
- if (code_len == kCodeLengthRepeatCode) {
+ 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;
@@ -502,7 +556,7 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len,
old_repeat = *repeat;
if (*repeat > 0) {
*repeat -= 2;
- *repeat <<= code_len - 14U;
+ *repeat <<= extra_bits;
}
*repeat += repeat_delta + 3U;
repeat_delta = *repeat - old_repeat;
@@ -513,7 +567,7 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len,
return;
}
BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n",
- *symbol, *symbol + repeat_delta - 1, *repeat_code_len));
+ (int)*symbol, (int)(*symbol + repeat_delta - 1), (int)*repeat_code_len));
if (*repeat_code_len != 0) {
unsigned last = *symbol + repeat_delta;
int next = next_symbol[*repeat_code_len];
@@ -531,8 +585,8 @@ static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len,
}
/* Reads and decodes symbol codelengths. */
-static BrotliErrorCode ReadSymbolCodeLengths(
- uint32_t alphabet_size, BrotliState* s) {
+static BrotliDecoderErrorCode ReadSymbolCodeLengths(
+ uint32_t alphabet_size, BrotliDecoderState* s) {
BrotliBitReader* br = &s->br;
uint32_t symbol = s->symbol;
uint32_t repeat = s->repeat;
@@ -543,91 +597,101 @@ static BrotliErrorCode ReadSymbolCodeLengths(
uint16_t* code_length_histo = s->code_length_histo;
int* next_symbol = s->next_symbol;
if (!BrotliWarmupBitReader(br)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
while (symbol < alphabet_size && space > 0) {
const HuffmanCode* p = s->table;
uint32_t code_len;
+ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p);
if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) {
s->symbol = symbol;
s->repeat = repeat;
s->prev_code_len = prev_code_len;
s->repeat_code_len = repeat_code_len;
s->space = space;
- return BROTLI_NEEDS_MORE_INPUT;
+ 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 < kCodeLengthRepeatCode) {
+ BROTLI_HC_ADJUST_TABLE_INDEX(p, BrotliGetBitsUnmasked(br) &
+ BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH));
+ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); /* Use 1..5 bits. */
+ code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */
+ if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
ProcessSingleCodeLength(code_len, &symbol, &repeat, &space,
&prev_code_len, symbol_lists, code_length_histo, next_symbol);
- } else { /* code_len == 16..17, extra_bits == 2..3 */
+ } 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(code_len - 14U);
- BrotliDropBits(br, code_len - 14U);
+ (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_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
-static BrotliErrorCode SafeReadSymbolCodeLengths(
- uint32_t alphabet_size, BrotliState* s) {
+static BrotliDecoderErrorCode SafeReadSymbolCodeLengths(
+ uint32_t alphabet_size, BrotliDecoderState* s) {
BrotliBitReader* br = &s->br;
+ BROTLI_BOOL get_byte = BROTLI_FALSE;
while (s->symbol < alphabet_size && s->space > 0) {
const HuffmanCode* p = s->table;
uint32_t code_len;
+ uint32_t available_bits;
uint32_t bits = 0;
- uint32_t available_bits = BrotliGetAvailableBits(br);
+ BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p);
+ if (get_byte && !BrotliPullByte(br)) return BROTLI_DECODER_NEEDS_MORE_INPUT;
+ get_byte = BROTLI_FALSE;
+ available_bits = BrotliGetAvailableBits(br);
if (available_bits != 0) {
bits = (uint32_t)BrotliGetBitsUnmasked(br);
}
- p += bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
- if (p->bits > available_bits) goto pullMoreInput;
- code_len = p->value; /* code_len == 0..17 */
- if (code_len < kCodeLengthRepeatCode) {
- BrotliDropBits(br, p->bits);
+ BROTLI_HC_ADJUST_TABLE_INDEX(p,
+ bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH));
+ if (BROTLI_HC_FAST_LOAD_BITS(p) > available_bits) {
+ get_byte = BROTLI_TRUE;
+ continue;
+ }
+ code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */
+ if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
+ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p));
ProcessSingleCodeLength(code_len, &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 */
+ } 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);
+ uint32_t repeat_delta = (bits >> BROTLI_HC_FAST_LOAD_BITS(p)) &
+ BitMask(extra_bits);
+ if (available_bits < BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits) {
+ get_byte = BROTLI_TRUE;
+ continue;
+ }
+ BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits);
ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,
&s->symbol, &s->repeat, &s->space, &s->prev_code_len,
&s->repeat_code_len, s->symbol_lists, s->code_length_histo,
s->next_symbol);
}
- continue;
-
-pullMoreInput:
- if (!BrotliPullByte(br)) {
- return BROTLI_NEEDS_MORE_INPUT;
- }
}
- return BROTLI_SUCCESS;
+ 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 BrotliErrorCode ReadCodeLengthCodeLengths(BrotliState* s) {
+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 < CODE_LENGTH_CODES; ++i) {
+ 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))) {
+ if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) {
uint32_t available_bits = BrotliGetAvailableBits(br);
if (available_bits != 0) {
ix = BrotliGetBitsUnmasked(br) & 0xF;
@@ -639,7 +703,7 @@ static BrotliErrorCode ReadCodeLengthCodeLengths(BrotliState* s) {
s->repeat = num_codes;
s->space = space;
s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
}
v = kCodeLengthPrefixValue[ix];
@@ -651,142 +715,149 @@ static BrotliErrorCode ReadCodeLengthCodeLengths(BrotliState* s) {
++num_codes;
++s->code_length_histo[v];
if (space - 1U >= 32U) {
- /* space is 0 or wrapped around */
+ /* space is 0 or wrapped around. */
break;
}
}
}
if (!(num_codes == 1 || space == 0)) {
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_CL_SPACE);
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE);
}
- return BROTLI_SUCCESS;
+ 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.
+ For this scenario 4 - 49 bits will be read.
B) 2-phase decoding:
B.1) Small Huffman table is decoded; it is specified with code lengths
encoded with predefined entropy code. 32 - 74 bits are used.
B.2) Decoded table is used to decode code lengths of symbols in resulting
- Huffman table. In worst case 3520 bits are read.
-*/
-static BrotliErrorCode ReadHuffmanCode(uint32_t alphabet_size,
- HuffmanCode* table,
- uint32_t* opt_table_size,
- BrotliState* s) {
+ Huffman table. In worst case 3520 bits are read. */
+static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size,
+ uint32_t max_symbol,
+ 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_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. */
+ alphabet_size &= 0x7FF;
+ /* State machine. */
+ for (;;) {
+ switch (s->substate_huffman) {
+ case BROTLI_STATE_HUFFMAN_NONE:
+ if (!BrotliSafeReadBits(br, 2, &s->sub_loop_counter)) {
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
+ }
+ BROTLI_LOG_UINT(s->sub_loop_counter);
+ /* The value is used as follows:
+ 1 for simple code;
+ 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
+ if (s->sub_loop_counter != 1) {
+ s->space = 32;
+ s->repeat = 0; /* num_codes */
+ memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo[0]) *
+ (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1));
+ memset(&s->code_length_code_lengths[0], 0,
+ sizeof(s->code_length_code_lengths));
+ s->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;
+ continue;
+ }
+ /* Fall through. */
- case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE:
- /* Read symbols, codes & code lengths directly. */
- if (!BrotliSafeReadBits(br, 2, &s->symbol)) { /* num_symbols */
- s->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE;
- return BROTLI_NEEDS_MORE_INPUT;
- }
- s->sub_loop_counter = 0;
- /* No break, transit to the next state. */
- case BROTLI_STATE_HUFFMAN_SIMPLE_READ: {
- BrotliErrorCode result = ReadSimpleHuffmanSymbols(alphabet_size, s);
- if (result != BROTLI_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_NEEDS_MORE_INPUT;
+ 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->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_SUCCESS;
- }
+ s->sub_loop_counter = 0;
+ /* Fall through. */
-Complex: /* Decode Huffman-coded code lengths. */
- case BROTLI_STATE_HUFFMAN_COMPLEX: {
- uint32_t i;
- BrotliErrorCode result = ReadCodeLengthCodeLengths(s);
- if (result != BROTLI_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;
+ case BROTLI_STATE_HUFFMAN_SIMPLE_READ: {
+ BrotliDecoderErrorCode result =
+ ReadSimpleHuffmanSymbols(alphabet_size, max_symbol, s);
+ if (result != BROTLI_DECODER_SUCCESS) {
+ return result;
+ }
}
+ /* Fall through. */
- s->symbol = 0;
- s->prev_code_len = kDefaultCodeLength;
- 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;
- BrotliErrorCode result = ReadSymbolCodeLengths(alphabet_size, s);
- if (result == BROTLI_NEEDS_MORE_INPUT) {
- result = SafeReadSymbolCodeLengths(alphabet_size, s);
- }
- if (result != BROTLI_SUCCESS) {
- return result;
+ 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;
}
- if (s->space != 0) {
- BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", s->space));
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_HUFFMAN_SPACE);
+ /* Decode Huffman-coded code lengths. */
+ case BROTLI_STATE_HUFFMAN_COMPLEX: {
+ uint32_t i;
+ BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s);
+ if (result != BROTLI_DECODER_SUCCESS) {
+ return result;
+ }
+ BrotliBuildCodeLengthsHuffmanTable(s->table,
+ s->code_length_code_lengths,
+ s->code_length_histo);
+ memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo));
+ for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) {
+ s->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
+ s->symbol_lists[s->next_symbol[i]] = 0xFFFF;
+ }
+
+ s->symbol = 0;
+ s->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH;
+ s->repeat = 0;
+ s->repeat_code_len = 0;
+ s->space = 32768;
+ s->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS;
}
- table_size = BrotliBuildHuffmanTable(
- table, HUFFMAN_TABLE_BITS, s->symbol_lists, s->code_length_histo);
- if (opt_table_size) {
- *opt_table_size = table_size;
+ /* Fall through. */
+
+ case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: {
+ uint32_t table_size;
+ BrotliDecoderErrorCode result = ReadSymbolCodeLengths(max_symbol, s);
+ if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
+ result = SafeReadSymbolCodeLengths(max_symbol, s);
+ }
+ if (result != BROTLI_DECODER_SUCCESS) {
+ return result;
+ }
+
+ if (s->space != 0) {
+ BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)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;
}
- s->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
- return BROTLI_SUCCESS;
- }
- default:
- return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE);
+ default:
+ return
+ BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
+ }
}
}
@@ -796,35 +867,34 @@ static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table,
uint32_t code;
uint32_t nbits;
code = ReadSymbol(table, br);
- nbits = kBlockLengthPrefixCode[code].nbits; /* nbits == 2..24 */
+ 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 int SafeReadBlockLength(BrotliState* s,
- uint32_t* result,
- const HuffmanCode* table,
- BrotliBitReader* br) {
+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 0;
+ return BROTLI_FALSE;
}
} else {
index = s->block_length_index;
}
{
uint32_t bits;
- uint32_t nbits = kBlockLengthPrefixCode[index].nbits; /* nbits == 2..24 */
+ 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 0;
+ return BROTLI_FALSE;
}
*result = kBlockLengthPrefixCode[index].offset + bits;
s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
- return 1;
+ return BROTLI_TRUE;
}
}
@@ -841,47 +911,47 @@ static BROTLI_INLINE int SafeReadBlockLength(BrotliState* s,
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, BrotliState* state) {
+ 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 i = 1;
uint32_t upper_bound = state->mtf_upper_bound;
- uint8_t* mtf = &state->mtf[4]; /* Make mtf[-1] addressable. */
+ uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */
+ uint8_t* mtf_u8 = (uint8_t*)mtf;
/* Load endian-aware constant. */
const uint8_t b0123[4] = {0, 1, 2, 3};
uint32_t pattern;
memcpy(&pattern, &b0123, 4);
/* Initialize list using 4 consequent values pattern. */
- *(uint32_t*)mtf = pattern;
+ mtf[0] = pattern;
do {
- pattern += 0x04040404; /* Advance all 4 values by 4. */
- *(uint32_t*)(mtf + i) = pattern;
- i += 4;
+ pattern += 0x04040404; /* Advance all 4 values by 4. */
+ mtf[i] = pattern;
+ i++;
} while (i <= upper_bound);
/* Transform the input. */
upper_bound = 0;
for (i = 0; i < v_len; ++i) {
int index = v[i];
- uint8_t value = mtf[index];
+ uint8_t value = mtf_u8[index];
upper_bound |= v[i];
v[i] = value;
- mtf[-1] = value;
+ mtf_u8[-1] = value;
do {
index--;
- mtf[index + 1] = mtf[index];
+ mtf_u8[index + 1] = mtf_u8[index];
} while (index >= 0);
}
/* Remember amount of elements to be reinitialized. */
- state->mtf_upper_bound = upper_bound;
+ state->mtf_upper_bound = upper_bound >> 2;
}
/* Decodes a series of Huffman table using ReadHuffmanCode function. */
-static BrotliErrorCode HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
- BrotliState* s) {
+static BrotliDecoderErrorCode HuffmanTreeGroupDecode(
+ HuffmanTreeGroup* group, BrotliDecoderState* s) {
if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {
s->next = group->codes;
s->htree_index = 0;
@@ -889,15 +959,16 @@ static BrotliErrorCode HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
}
while (s->htree_index < group->num_htrees) {
uint32_t table_size;
- BrotliErrorCode result =
- ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
- if (result != BROTLI_SUCCESS) return result;
+ BrotliDecoderErrorCode result =
+ ReadHuffmanCode(group->alphabet_size, group->max_symbol,
+ 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_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
/* Decodes a context map.
@@ -907,43 +978,44 @@ static BrotliErrorCode HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
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 BrotliErrorCode DecodeContextMap(uint32_t context_map_size,
- uint32_t* num_htrees,
- uint8_t** context_map_arg,
- BrotliState* s) {
+ 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;
- BrotliErrorCode result = BROTLI_SUCCESS;
+ 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_SUCCESS) {
+ 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);
+ *context_map_arg =
+ (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)context_map_size);
if (*context_map_arg == 0) {
- return BROTLI_FAILURE(BROTLI_ERROR_ALLOC_CONTEXT_MAP);
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP);
}
if (*num_htrees <= 1) {
memset(*context_map_arg, 0, (size_t)context_map_size);
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX;
- /* No break, continue to next state. */
+ /* Fall through. */
+
case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: {
uint32_t bits;
/* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe
to peek 4 bits ahead. */
if (!BrotliSafeGetBits(br, 5, &bits)) {
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
- if ((bits & 1) != 0) { /* Use RLE for zeroes. */
+ if ((bits & 1) != 0) { /* Use RLE for zeros. */
s->max_run_length_prefix = (bits >> 1) + 1;
BrotliDropBits(br, 5);
} else {
@@ -952,81 +1024,91 @@ static BrotliErrorCode DecodeContextMap(uint32_t context_map_size,
}
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,
+ /* Fall through. */
+
+ case BROTLI_STATE_CONTEXT_MAP_HUFFMAN: {
+ uint32_t alphabet_size = *num_htrees + s->max_run_length_prefix;
+ result = ReadHuffmanCode(alphabet_size, alphabet_size,
s->context_map_table, NULL, s);
- if (result != BROTLI_SUCCESS) return result;
+ 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. */
+ }
+ /* Fall through. */
+
case BROTLI_STATE_CONTEXT_MAP_DECODE: {
uint32_t context_index = s->context_index;
uint32_t max_run_length_prefix = s->max_run_length_prefix;
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_NEEDS_MORE_INPUT;
- }
- BROTLI_LOG_UINT(code);
+ BROTLI_BOOL skip_preamble = (code != 0xFFFF);
+ while (context_index < context_map_size || skip_preamble) {
+ if (!skip_preamble) {
+ if (!SafeReadSymbol(s->context_map_table, br, &code)) {
+ s->code = 0xFFFF;
+ s->context_index = context_index;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
+ }
+ BROTLI_LOG_UINT(code);
- if (code == 0) {
- context_map[context_index++] = 0;
- continue;
- }
- if (code > max_run_length_prefix) {
- context_map[context_index++] =
- (uint8_t)(code - max_run_length_prefix);
- continue;
+ if (code == 0) {
+ context_map[context_index++] = 0;
+ continue;
+ }
+ if (code > max_run_length_prefix) {
+ context_map[context_index++] =
+ (uint8_t)(code - max_run_length_prefix);
+ continue;
+ }
+ } else {
+ skip_preamble = BROTLI_FALSE;
}
-rleCode:
+ /* RLE sub-stage. */
{
uint32_t reps;
if (!BrotliSafeReadBits(br, code, &reps)) {
s->code = code;
s->context_index = context_index;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
reps += 1U << code;
BROTLI_LOG_UINT(reps);
if (context_index + reps > context_map_size) {
- return BROTLI_FAILURE(BROTLI_ERROR_FORMAT_CONTEXT_MAP_REPEAT);
+ return
+ BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT);
}
do {
context_map[context_index++] = 0;
} while (--reps);
}
}
- /* No break, continue to next state. */
}
+ /* Fall through. */
+
case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: {
uint32_t bits;
if (!BrotliSafeReadBits(br, 1, &bits)) {
s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM;
- return BROTLI_NEEDS_MORE_INPUT;
+ 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_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
+
default:
- return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE);
+ return
+ BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
}
}
-/* Decodes a command or literal and updates block type ringbuffer.
+/* Decodes a command or literal and updates block type ring-buffer.
Reads 3..54 bits. */
-static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe,
- BrotliState* s, int tree_type) {
+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];
@@ -1035,19 +1117,22 @@ static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe,
BrotliBitReader* br = &s->br;
uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2];
uint32_t block_type;
+ if (max_block_type <= 1) {
+ return BROTLI_FALSE;
+ }
- /* Read 0..15 + 3..39 bits */
+ /* 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 0;
+ 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 0;
+ return BROTLI_FALSE;
}
}
@@ -1063,18 +1148,19 @@ static BROTLI_INLINE int DecodeBlockTypeAndLength(int safe,
}
ringbuffer[0] = ringbuffer[1];
ringbuffer[1] = block_type;
- return 1;
+ return BROTLI_TRUE;
}
-static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(BrotliState* s) {
+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 << kLiteralContextBits;
+ 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 << kLiteralContextBits);) {
+ for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) {
BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;)
}
if (error == 0) {
@@ -1083,151 +1169,185 @@ static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(BrotliState* s) {
}
}
-static BROTLI_INLINE void PrepareLiteralDecoding(BrotliState* s) {
+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 << kLiteralContextBits;
+ 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]];
+ context_mode = s->context_modes[block_type] & 3;
+ s->context_lookup = BROTLI_CONTEXT_LUT(context_mode);
}
/* Decodes the block type and updates the state for literal context.
Reads 3..54 bits. */
-static BROTLI_INLINE int DecodeLiteralBlockSwitchInternal(int safe,
- BrotliState* s) {
+static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal(
+ int safe, BrotliDecoderState* s) {
if (!DecodeBlockTypeAndLength(safe, s, 0)) {
- return 0;
+ return BROTLI_FALSE;
}
PrepareLiteralDecoding(s);
- return 1;
+ return BROTLI_TRUE;
}
-static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliState* s) {
+static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) {
DecodeLiteralBlockSwitchInternal(0, s);
}
-static int BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(BrotliState* 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 int DecodeCommandBlockSwitchInternal(int safe,
- BrotliState* s) {
+static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal(
+ int safe, BrotliDecoderState* s) {
if (!DecodeBlockTypeAndLength(safe, s, 1)) {
- return 0;
+ return BROTLI_FALSE;
}
s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]];
- return 1;
+ return BROTLI_TRUE;
}
-static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliState* s) {
+static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) {
DecodeCommandBlockSwitchInternal(0, s);
}
-static int BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(BrotliState* 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 int DecodeDistanceBlockSwitchInternal(int safe,
- BrotliState* s) {
+static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal(
+ int safe, BrotliDecoderState* s) {
if (!DecodeBlockTypeAndLength(safe, s, 2)) {
- return 0;
+ return BROTLI_FALSE;
}
- s->dist_context_map_slice =
- s->dist_context_map + (s->block_type_rb[5] << kDistanceContextBits);
+ 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 1;
+ return BROTLI_TRUE;
}
-static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliState* s) {
+static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) {
DecodeDistanceBlockSwitchInternal(0, s);
}
-static int BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(BrotliState* s) {
+static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(
+ BrotliDecoderState* s) {
return DecodeDistanceBlockSwitchInternal(1, s);
}
-static BrotliErrorCode BROTLI_NOINLINE WriteRingBuffer(size_t* available_out,
- uint8_t** next_out, size_t* total_out, BrotliState* s) {
- size_t pos = (s->pos > s->ringbuffer_size) ? (size_t)s->ringbuffer_size
- : (size_t)(s->pos);
+static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) {
+ size_t pos = wrap && s->pos > s->ringbuffer_size ?
+ (size_t)s->ringbuffer_size : (size_t)(s->pos);
+ size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos;
+ return partial_pos_rb - s->partial_pos_out;
+}
+
+/* Dumps output.
+ Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push
+ and either ring-buffer is as big as window size, or |force| is true. */
+static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer(
+ BrotliDecoderState* s, size_t* available_out, uint8_t** next_out,
+ size_t* total_out, BROTLI_BOOL force) {
uint8_t* start =
s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask);
- size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos;
- size_t to_write = (partial_pos_rb - s->partial_pos_out);
+ 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_ERROR_FORMAT_BLOCK_LENGTH_1);
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1);
+ }
+ if (next_out && !*next_out) {
+ *next_out = start;
+ } else {
+ if (next_out) {
+ memcpy(*next_out, start, num_written);
+ *next_out += num_written;
+ }
}
- 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 (total_out) {
+ *total_out = s->partial_pos_out;
+ }
if (num_written < to_write) {
- return BROTLI_NEEDS_MORE_OUTPUT;
+ if (s->ringbuffer_size == (1 << s->window_bits) || force) {
+ return BROTLI_DECODER_NEEDS_MORE_OUTPUT;
+ } else {
+ return BROTLI_DECODER_SUCCESS;
+ }
}
-
- if (s->pos >= s->ringbuffer_size) {
+ /* Wrap ring buffer only if it has reached its maximal size. */
+ if (s->ringbuffer_size == (1 << s->window_bits) &&
+ s->pos >= s->ringbuffer_size) {
s->pos -= s->ringbuffer_size;
s->rb_roundtrips++;
+ s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0;
+ }
+ return BROTLI_DECODER_SUCCESS;
+}
+
+static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) {
+ if (s->should_wrap_ringbuffer) {
+ memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);
+ s->should_wrap_ringbuffer = 0;
}
- return BROTLI_SUCCESS;
}
-/* Allocates ringbuffer.
+/* Allocates ring-buffer.
- s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
- this function is called.
+ 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.
+ Last two bytes of ring-buffer are initialized to 0, so context calculation
+ could be done uniformly for the first two and all other positions. */
+static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer(
+ BrotliDecoderState* s) {
+ uint8_t* old_ringbuffer = s->ringbuffer;
+ if (s->ringbuffer_size == s->new_ringbuffer_size) {
+ return BROTLI_TRUE;
+ }
- Custom dictionary, if any, is copied to the end of ringbuffer.
-*/
-static int BROTLI_NOINLINE BrotliAllocateRingBuffer(BrotliState* 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));
+ s->ringbuffer = (uint8_t*)BROTLI_DECODER_ALLOC(s,
+ (size_t)(s->new_ringbuffer_size) + kRingBufferWriteAheadSlack);
if (s->ringbuffer == 0) {
- return 0;
+ /* Restore previous value. */
+ s->ringbuffer = old_ringbuffer;
+ return BROTLI_FALSE;
}
+ s->ringbuffer[s->new_ringbuffer_size - 2] = 0;
+ s->ringbuffer[s->new_ringbuffer_size - 1] = 0;
- 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);
+ if (!!old_ringbuffer) {
+ memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos);
+ BROTLI_DECODER_FREE(s, old_ringbuffer);
}
- return 1;
+ s->ringbuffer_size = s->new_ringbuffer_size;
+ s->ringbuffer_mask = s->new_ringbuffer_size - 1;
+ s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
+
+ return BROTLI_TRUE;
}
-static BrotliErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(
+static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(
size_t* available_out, uint8_t** next_out, size_t* total_out,
- BrotliState* s) {
+ BrotliDecoderState* s) {
/* TODO: avoid allocation for single uncompressed block. */
- if (!s->ringbuffer && !BrotliAllocateRingBuffer(s)) {
- return BROTLI_FAILURE(BROTLI_ERROR_ALLOC_RING_BUFFER_1);
+ if (!BrotliEnsureRingBuffer(s)) {
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1);
}
/* State machine */
@@ -1241,26 +1361,30 @@ static BrotliErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(
if (s->pos + nbytes > s->ringbuffer_size) {
nbytes = s->ringbuffer_size - s->pos;
}
- /* Copy remaining bytes from s->br.buf_ to ringbuffer. */
+ /* Copy remaining bytes from s->br.buf_ to ring-buffer. */
BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes);
s->pos += nbytes;
s->meta_block_remaining_len -= nbytes;
- if (s->pos < s->ringbuffer_size) {
+ if (s->pos < 1 << s->window_bits) {
if (s->meta_block_remaining_len == 0) {
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE;
- /* No break, continue to next state */
}
+ /* Fall through. */
+
case BROTLI_STATE_UNCOMPRESSED_WRITE: {
- BrotliErrorCode result =
- WriteRingBuffer(available_out, next_out, total_out, s);
- if (result != BROTLI_SUCCESS) {
+ BrotliDecoderErrorCode result;
+ result = WriteRingBuffer(
+ s, available_out, next_out, total_out, BROTLI_FALSE);
+ if (result != BROTLI_DECODER_SUCCESS) {
return result;
}
- s->max_distance = s->max_backward_distance;
+ if (s->ringbuffer_size == 1 << s->window_bits) {
+ s->max_distance = s->max_backward_distance;
+ }
s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;
break;
}
@@ -1269,69 +1393,53 @@ static BrotliErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(
BROTLI_DCHECK(0); /* Unreachable */
}
-int BrotliDecompressedSize(size_t encoded_size,
- const uint8_t* encoded_buffer,
- size_t* decoded_size) {
- BrotliState s;
- int next_block_header;
- BrotliStateInit(&s);
- s.br.next_in = encoded_buffer;
- s.br.avail_in = encoded_size;
- if (!BrotliWarmupBitReader(&s.br)) {
- return 0;
- }
- DecodeWindowBits(&s.br);
- if (DecodeMetaBlockLength(&s, &s.br) != BROTLI_SUCCESS) {
- return 0;
- }
- *decoded_size = (size_t)s.meta_block_remaining_len;
- if (s.is_last_metablock) {
- return 1;
- }
- if (!s.is_uncompressed || !BrotliJumpToByteBoundary(&s.br)) {
- return 0;
- }
- next_block_header = BrotliPeekByte(&s.br, (size_t)s.meta_block_remaining_len);
- return (next_block_header != -1) && ((next_block_header & 3) == 3);
-}
-
/* Calculates the smallest feasible ring buffer.
- If we know the data size is small, do not allocate more ringbuffer
+ If we know the data size is small, do not allocate more ring buffer
size than needed to reduce memory usage.
- When this method is called, metablock size and flags MUST be decoded.
-*/
-static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(BrotliState* s,
- BrotliBitReader* br) {
- int is_last = s->is_last_metablock;
+ When this method is called, metablock size and flags MUST be decoded. */
+static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(
+ BrotliDecoderState* s) {
int window_size = 1 << s->window_bits;
- 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 = 1;
- }
- }
- }
-
+ int new_ringbuffer_size = window_size;
/* We need at least 2 bytes of ring buffer size to get the last two
bytes for context from there */
- 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;
+ int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024;
+ int output_size;
+
+ /* If maximum is already reached, no further extension is retired. */
+ if (s->ringbuffer_size == window_size) {
+ return;
+ }
+
+ /* Metadata blocks does not touch ring buffer. */
+ if (s->is_metadata) {
+ return;
+ }
+
+ if (!s->ringbuffer) {
+ output_size = 0;
+ } else {
+ output_size = s->pos;
+ }
+ output_size += s->meta_block_remaining_len;
+ min_size = min_size < output_size ? output_size : min_size;
+
+ if (!!s->canny_ringbuffer_allocation) {
+ /* Reduce ring buffer size to save memory when server is unscrupulous.
+ In worst case memory usage might be 1.5x bigger for a short period of
+ ring buffer reallocation. */
+ while ((new_ringbuffer_size >> 1) >= min_size) {
+ new_ringbuffer_size >>= 1;
}
}
- s->ringbuffer_mask = s->ringbuffer_size - 1;
+ s->new_ringbuffer_size = new_ringbuffer_size;
}
/* Reads 1..256 2-bit context modes. */
-static BrotliErrorCode ReadContextModes(BrotliState* s) {
+static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) {
BrotliBitReader* br = &s->br;
int i = s->loop_counter;
@@ -1339,27 +1447,29 @@ static BrotliErrorCode ReadContextModes(BrotliState* s) {
uint32_t bits;
if (!BrotliSafeReadBits(br, 2, &bits)) {
s->loop_counter = i;
- return BROTLI_NEEDS_MORE_INPUT;
+ return BROTLI_DECODER_NEEDS_MORE_INPUT;
}
- s->context_modes[i] = (uint8_t)(bits << 1);
+ s->context_modes[i] = (uint8_t)bits;
BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
i++;
}
- return BROTLI_SUCCESS;
+ return BROTLI_DECODER_SUCCESS;
}
-static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliState* s) {
+static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) {
if (s->distance_code == 0) {
--s->dist_rb_idx;
s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
+ /* Compensate double distance-ring-buffer roll for dictionary items. */
+ s->distance_context = 1;
} else {
int distance_code = s->distance_code << 1;
- /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: */
- /* 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */
- const uint32_t kDistanceShortCodeIndexOffset = 0xaaafff1b;
- /* kDistanceShortCodeValueOffset has 2-bit values from LSB: */
- /*-0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */
- const uint32_t kDistanceShortCodeValueOffset = 0xfa5fa500;
+ /* 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];
@@ -1369,27 +1479,27 @@ static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliState* s) {
} 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;
+ /* A huge distance will cause a BROTLI_FAILURE() soon.
+ This is a little faster than failing here. */
+ s->distance_code = 0x7FFFFFFF;
}
}
}
}
-static BROTLI_INLINE int SafeReadBits(
+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 1;
+ return BROTLI_TRUE;
}
}
-/* Precondition: s->distance_code < 0 */
-static BROTLI_INLINE int ReadDistanceInternal(int safe,
- BrotliState* s, BrotliBitReader* br) {
+/* 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];
@@ -1399,16 +1509,17 @@ static BROTLI_INLINE int ReadDistanceInternal(int safe,
uint32_t code;
BrotliBitReaderSaveState(br, &memento);
if (!SafeReadSymbol(distance_tree, br, &code)) {
- return 0;
+ 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) {
+ /* Convert the distance code to the actual distance by possibly
+ looking up past distances from the s->ringbuffer. */
+ s->distance_context = 0;
+ if ((s->distance_code & ~0xF) == 0) {
TakeDistanceFromRingBuffer(s);
--s->block_length[2];
- return 1;
+ return BROTLI_TRUE;
}
distval = s->distance_code - (int)s->num_direct_distance_codes;
if (distval >= 0) {
@@ -1421,16 +1532,16 @@ static BROTLI_INLINE int ReadDistanceInternal(int safe,
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 */
+ /* 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. */
+ s->distance_code = -1; /* Restore precondition. */
BrotliBitReaderRestoreState(br, &memento);
- return 0;
+ return BROTLI_FALSE;
}
} else {
bits = BrotliReadBits(br, nbits);
@@ -1440,21 +1551,23 @@ static BROTLI_INLINE int ReadDistanceInternal(int safe,
((offset + (int)bits) << s->distance_postfix_bits) + postfix;
}
}
- s->distance_code = s->distance_code - NUM_DISTANCE_SHORT_CODES + 1;
+ s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1;
--s->block_length[2];
- return 1;
+ return BROTLI_TRUE;
}
-static BROTLI_INLINE void ReadDistance(BrotliState* s, BrotliBitReader* br) {
+static BROTLI_INLINE void ReadDistance(
+ BrotliDecoderState* s, BrotliBitReader* br) {
ReadDistanceInternal(0, s, br);
}
-static BROTLI_INLINE int SafeReadDistance(BrotliState* s, BrotliBitReader* br) {
+static BROTLI_INLINE BROTLI_BOOL SafeReadDistance(
+ BrotliDecoderState* s, BrotliBitReader* br) {
return ReadDistanceInternal(1, s, br);
}
-static BROTLI_INLINE int ReadCommandInternal(int safe,
- BrotliState* s, BrotliBitReader* br, int* insert_length) {
+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;
@@ -1465,7 +1578,7 @@ static BROTLI_INLINE int ReadCommandInternal(int safe,
} else {
BrotliBitReaderSaveState(br, &memento);
if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) {
- return 0;
+ return BROTLI_FALSE;
}
}
v = kCmdLut[cmd_code];
@@ -1474,7 +1587,7 @@ static BROTLI_INLINE int ReadCommandInternal(int safe,
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)) {
+ if (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) {
insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits);
}
copy_length = BrotliReadBits(br, v.copy_len_extra_bits);
@@ -1482,54 +1595,54 @@ static BROTLI_INLINE int ReadCommandInternal(int safe,
if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) ||
!SafeReadBits(br, v.copy_len_extra_bits, &copy_length)) {
BrotliBitReaderRestoreState(br, &memento);
- return 0;
+ return BROTLI_FALSE;
}
}
s->copy_length = (int)copy_length + v.copy_len_offset;
--s->block_length[1];
*insert_length += (int)insert_len_extra;
- return 1;
+ return BROTLI_TRUE;
}
-static BROTLI_INLINE void ReadCommand(BrotliState* s, BrotliBitReader* br,
- int* insert_length) {
+static BROTLI_INLINE void ReadCommand(
+ BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
ReadCommandInternal(0, s, br, insert_length);
}
-static BROTLI_INLINE int SafeReadCommand(BrotliState* s, BrotliBitReader* br,
- int* 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 int CheckInputAmount(int safe,
- BrotliBitReader* const br, size_t num) {
+static BROTLI_INLINE BROTLI_BOOL CheckInputAmount(
+ int safe, BrotliBitReader* const br, size_t num) {
if (safe) {
- return 1;
+ return BROTLI_TRUE;
}
return BrotliCheckInputAmount(br, num);
}
-#define BROTLI_SAFE(METHOD) \
- { \
- if (safe) { \
- if (!Safe##METHOD) { \
- result = BROTLI_NEEDS_MORE_INPUT; \
- goto saveStateAndReturn; \
- } \
- } else { \
- METHOD; \
- } \
+#define BROTLI_SAFE(METHOD) \
+ { \
+ if (safe) { \
+ if (!Safe##METHOD) { \
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT; \
+ goto saveStateAndReturn; \
+ } \
+ } else { \
+ METHOD; \
+ } \
}
-static BROTLI_INLINE BrotliErrorCode ProcessCommandsInternal(int safe,
- BrotliState* s) {
+static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal(
+ int safe, BrotliDecoderState* s) {
int pos = s->pos;
int i = s->loop_counter;
- BrotliErrorCode result = BROTLI_SUCCESS;
+ BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
BrotliBitReader* br = &s->br;
if (!CheckInputAmount(safe, br, 28)) {
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
goto saveStateAndReturn;
}
if (!safe) {
@@ -1546,23 +1659,23 @@ static BROTLI_INLINE BrotliErrorCode ProcessCommandsInternal(int safe,
} else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) {
goto CommandPostWrapCopy;
} else {
- return BROTLI_FAILURE(BROTLI_ERROR_UNREACHABLE);
+ 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 */
+ if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */
s->state = BROTLI_STATE_COMMAND_BEGIN;
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
goto saveStateAndReturn;
}
- if (PREDICT_FALSE(s->block_length[1] == 0)) {
+ if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) {
BROTLI_SAFE(DecodeCommandBlockSwitch(s));
goto CommandBegin;
}
- /* Read the insert/copy length in the command */
+ /* 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));
@@ -1575,18 +1688,18 @@ CommandInner:
if (safe) {
s->state = BROTLI_STATE_COMMAND_INNER;
}
- /* Read the literals in the command */
+ /* 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 */
+ if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
s->state = BROTLI_STATE_COMMAND_INNER;
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
goto saveStateAndReturn;
}
- if (PREDICT_FALSE(s->block_length[0] == 0)) {
+ if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {
BROTLI_SAFE(DecodeLiteralBlockSwitch(s));
PreloadSymbol(safe, s->literal_htree, br, &bits, &value);
if (!s->trivial_literal_context) goto CommandInner;
@@ -1597,7 +1710,7 @@ CommandInner:
} else {
uint32_t literal;
if (!SafeReadSymbol(s->literal_htree, br, &literal)) {
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
goto saveStateAndReturn;
}
s->ringbuffer[pos] = (uint8_t)literal;
@@ -1605,7 +1718,7 @@ CommandInner:
--s->block_length[0];
BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos);
++pos;
- if (PREDICT_FALSE(pos == s->ringbuffer_size)) {
+ if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {
s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
--i;
goto saveStateAndReturn;
@@ -1617,16 +1730,16 @@ CommandInner:
do {
const HuffmanCode* hc;
uint8_t context;
- if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
+ if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
s->state = BROTLI_STATE_COMMAND_INNER;
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
goto saveStateAndReturn;
}
- if (PREDICT_FALSE(s->block_length[0] == 0)) {
+ if (BROTLI_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];
+ context = BROTLI_CONTEXT(p1, p2, s->context_lookup);
BROTLI_LOG_UINT(context);
hc = s->literal_hgroup.htrees[s->context_map_slice[context]];
p2 = p1;
@@ -1635,7 +1748,7 @@ CommandInner:
} else {
uint32_t literal;
if (!SafeReadSymbol(hc, br, &literal)) {
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
goto saveStateAndReturn;
}
p1 = (uint8_t)literal;
@@ -1645,7 +1758,7 @@ CommandInner:
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)) {
+ if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {
s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
--i;
goto saveStateAndReturn;
@@ -1653,7 +1766,7 @@ CommandInner:
} while (--i != 0);
}
BROTLI_LOG_UINT(s->meta_block_remaining_len);
- if (PREDICT_FALSE(s->meta_block_remaining_len <= 0)) {
+ if (BROTLI_PREDICT_FALSE(s->meta_block_remaining_len <= 0)) {
s->state = BROTLI_STATE_METABLOCK_DONE;
goto saveStateAndReturn;
}
@@ -1663,51 +1776,70 @@ CommandPostDecodeLiterals:
s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;
}
if (s->distance_code >= 0) {
+ /* Implicit distance case. */
+ s->distance_context = s->distance_code ? 0 : 1;
--s->dist_rb_idx;
s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
- 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));
+ } else {
+ /* Read distance code in the command, unless it was implicitly zero. */
+ if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) {
+ BROTLI_SAFE(DecodeDistanceBlockSwitch(s));
+ }
+ BROTLI_SAFE(ReadDistance(s, br));
}
- BROTLI_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;
- }
+ s->max_distance =
+ (pos < s->max_backward_distance) ? pos : s->max_backward_distance;
}
i = s->copy_length;
/* Apply copy of LZ77 back-reference, or static dictionary reference if
- the distance is larger than the max LZ77 distance */
+ 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];
+ /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC.
+ With this choice, no signed overflow can occur after decoding
+ a special distance code (e.g., after adding 3 to the last distance). */
+ if (s->distance_code > BROTLI_MAX_ALLOWED_DISTANCE) {
+ BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
+ "len: %d bytes left: %d\n",
+ pos, s->distance_code, i, s->meta_block_remaining_len));
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE);
+ }
+ if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH &&
+ i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) {
+ int address = s->distance_code - s->max_distance - 1;
+ const BrotliDictionary* words = s->dictionary;
+ const BrotliTransforms* transforms = s->transforms;
+ int offset = (int)s->dictionary->offsets_by_length[i];
+ uint32_t shift = s->dictionary->size_bits_by_length[i];
+
int mask = (int)BitMask(shift);
- int word_idx = word_id & mask;
- int transform_idx = word_id >> shift;
+ int word_idx = address & mask;
+ int transform_idx = address >> shift;
+ /* Compensate double distance-ring-buffer roll. */
+ s->dist_rb_idx += s->distance_context;
offset += word_idx * i;
- if (transform_idx < kNumTransforms) {
- const uint8_t* word = &kBrotliDictionary[offset];
+ if (BROTLI_PREDICT_FALSE(!words->data)) {
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET);
+ }
+ if (transform_idx < (int)transforms->num_transforms) {
+ const uint8_t* word = &words->data[offset];
int len = i;
- if (transform_idx == 0) {
+ if (transform_idx == transforms->cutOffTransforms[0]) {
memcpy(&s->ringbuffer[pos], word, (size_t)len);
+ BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n",
+ len, word));
} else {
- len = TransformDictionaryWord(
- &s->ringbuffer[pos], word, len, transform_idx);
+ len = BrotliTransformDictionaryWord(&s->ringbuffer[pos], word, len,
+ transforms, transform_idx);
+ BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s],"
+ " transform_idx = %d, transformed: [%.*s]\n",
+ i, word, transform_idx, len, &s->ringbuffer[pos]));
}
pos += len;
s->meta_block_remaining_len -= len;
if (pos >= s->ringbuffer_size) {
- /*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/
s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;
goto saveStateAndReturn;
}
@@ -1715,13 +1847,13 @@ postReadDistance:
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_ERROR_FORMAT_TRANSFORM);
+ 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_ERROR_FORMAT_DICTIONARY);
+ return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY);
}
} else {
int src_start = (pos - s->distance_code) & s->ringbuffer_mask;
@@ -1729,14 +1861,13 @@ postReadDistance:
uint8_t* copy_src = &s->ringbuffer[src_start];
int dst_end = pos + i;
int src_end = src_start + i;
- /* update the recent distances cache */
+ /* 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.
+ /* There are 32+ bytes of slack in the ring-buffer allocation.
Also, we have 16 short codes, that make these 16 bytes irrelevant
- in the ringbuffer. Let's copy over them as a first guess.
- */
+ in the ring-buffer. Let's copy over them as a first guess. */
memmove16(copy_dst, copy_src);
if (src_end > pos && dst_end > src_start) {
/* Regions intersect. */
@@ -1759,7 +1890,7 @@ postReadDistance:
}
BROTLI_LOG_UINT(s->meta_block_remaining_len);
if (s->meta_block_remaining_len <= 0) {
- /* Next metablock, if any */
+ /* Next metablock, if any. */
s->state = BROTLI_STATE_METABLOCK_DONE;
goto saveStateAndReturn;
} else {
@@ -1772,14 +1903,14 @@ CommandPostWrapCopy:
s->ringbuffer[pos] =
s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];
++pos;
- if (PREDICT_FALSE(--wrap_guard == 0)) {
+ if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) {
s->state = BROTLI_STATE_COMMAND_POST_WRITE_2;
goto saveStateAndReturn;
}
}
}
if (s->meta_block_remaining_len <= 0) {
- /* Next metablock, if any */
+ /* Next metablock, if any. */
s->state = BROTLI_STATE_METABLOCK_DONE;
goto saveStateAndReturn;
} else {
@@ -1794,84 +1925,122 @@ saveStateAndReturn:
#undef BROTLI_SAFE
-static BROTLI_NOINLINE BrotliErrorCode ProcessCommands(BrotliState* s) {
+static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands(
+ BrotliDecoderState* s) {
return ProcessCommandsInternal(0, s);
}
-static BROTLI_NOINLINE BrotliErrorCode SafeProcessCommands(BrotliState* s) {
+static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands(
+ BrotliDecoderState* s) {
return ProcessCommandsInternal(1, s);
}
-BrotliResult BrotliDecompressBuffer(size_t encoded_size,
- const uint8_t* encoded_buffer,
- size_t* decoded_size,
- uint8_t* decoded_buffer) {
- BrotliState s;
- BrotliResult result;
+/* Returns the maximum number of distance symbols which can only represent
+ distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */
+static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect, uint32_t npostfix) {
+ static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28};
+ static const uint32_t diff[BROTLI_MAX_NPOSTFIX + 1] = {73, 126, 228, 424};
+ uint32_t postfix = 1U << npostfix;
+ if (ndirect < bound[npostfix]) {
+ return ndirect + diff[npostfix] + postfix;
+ } else if (ndirect > bound[npostfix] + postfix) {
+ return ndirect + diff[npostfix];
+ } else {
+ return bound[npostfix] + diff[npostfix] + postfix;
+ }
+}
+
+BrotliDecoderResult BrotliDecoderDecompress(
+ size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,
+ uint8_t* decoded_buffer) {
+ 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;
- BrotliStateInit(&s);
- result = BrotliDecompressStream(&available_in, &next_in, &available_out,
- &next_out, &total_out, &s);
+ if (!BrotliDecoderStateInit(&s, 0, 0, 0)) {
+ return BROTLI_DECODER_RESULT_ERROR;
+ }
+ result = BrotliDecoderDecompressStream(
+ &s, &available_in, &next_in, &available_out, &next_out, &total_out);
*decoded_size = total_out;
- BrotliStateCleanup(&s);
- if (result != BROTLI_RESULT_SUCCESS) {
- result = BROTLI_RESULT_ERROR;
+ 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
+ - 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
+ - when result is "needs more input", then at least one more byte is REQUIRED
to complete decoding; all input data MUST be consumed by decoder, so
client could swap the input buffer
- * when result is "needs more output" decoder MUST ensure that it doesn't
+ - 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
-*/
-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) {
- BrotliErrorCode result = BROTLI_SUCCESS;
+ - when result is "success" decoder MUST return all unused data back to input
+ buffer; this is possible because the invariant is held on enter */
+BrotliDecoderResult BrotliDecoderDecompressStream(
+ BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in,
+ size_t* available_out, uint8_t** next_out, size_t* total_out) {
+ BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
BrotliBitReader* br = &s->br;
- if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */
+ /* Ensure that |total_out| is set, even if no data will ever be pushed out. */
+ if (total_out) {
+ *total_out = s->partial_pos_out;
+ }
+ /* Do not try to process further in a case of unrecoverable error. */
+ if ((int)s->error_code < 0) {
+ return BROTLI_DECODER_RESULT_ERROR;
+ }
+ if (*available_out && (!next_out || !*next_out)) {
+ return SaveErrorCode(
+ s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS));
+ }
+ if (!*available_out) next_out = 0;
+ 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_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
br->next_in = &s->buffer.u8[0];
}
/* State machine */
for (;;) {
- if (result != BROTLI_SUCCESS) { /* Error | needs more input/output */
- if (result == BROTLI_NEEDS_MORE_INPUT) {
- if (s->ringbuffer != 0) { /* Proactively push output. */
- WriteRingBuffer(available_out, next_out, total_out, s);
- }
- 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
+ if (result != BROTLI_DECODER_SUCCESS) {
+ /* Error, needs more input/output. */
+ if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
+ if (s->ringbuffer != 0) { /* Pro-actively push output. */
+ BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s,
+ available_out, next_out, total_out, BROTLI_TRUE);
+ /* WriteRingBuffer checks s->meta_block_remaining_len validity. */
+ if ((int)intermediate_result < 0) {
+ result = intermediate_result;
+ break;
+ }
+ }
+ if (s->buffer_length != 0) { /* Used with internal buffer. */
+ if (br->avail_in == 0) {
+ /* Successfully finished read transaction.
+ Accumulator contains less than 8 bits, because internal buffer
is expanded byte-by-byte until it is enough to complete read. */
s->buffer_length = 0;
/* Switch to input stream and restart. */
- result = BROTLI_SUCCESS;
+ 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_SUCCESS;
+ result = BROTLI_DECODER_SUCCESS;
s->buffer.u8[s->buffer_length] = **next_in;
s->buffer_length++;
br->avail_in = s->buffer_length;
@@ -1880,9 +2049,9 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
/* Retry with more data in buffer. */
continue;
}
- /* Can't finish reading and no more input.*/
+ /* Can't finish reading and no more input. */
break;
- } else { /* Input stream doesn't contain enough input. */
+ } 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;
@@ -1901,12 +2070,12 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
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.*/
+ 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. */
+ stream it has less than 8 bits in accumulator, so it is safe to
+ return unused accumulator bits there. */
BrotliBitReaderUnload(br);
*available_in = br->avail_in;
*next_in = br->next_in;
@@ -1917,48 +2086,62 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
case BROTLI_STATE_UNINITED:
/* Prepare to the first read. */
if (!BrotliWarmupBitReader(br)) {
- result = BROTLI_NEEDS_MORE_INPUT;
+ 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_ERROR_FORMAT_WINDOW_BITS);
+ result = DecodeWindowBits(s, br); /* Reads 1..8 bits. */
+ if (result != BROTLI_DECODER_SUCCESS) {
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;
+ if (s->large_window) {
+ s->state = BROTLI_STATE_LARGE_WINDOW_BITS;
+ break;
+ }
+ s->state = BROTLI_STATE_INITIALIZE;
+ break;
+
+ case BROTLI_STATE_LARGE_WINDOW_BITS:
+ if (!BrotliSafeReadBits(br, 6, &s->window_bits)) {
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
+ break;
+ }
+ if (s->window_bits < BROTLI_LARGE_MIN_WBITS ||
+ s->window_bits > BROTLI_LARGE_MAX_WBITS) {
+ result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
+ break;
}
- s->max_backward_distance_minus_custom_dict_size =
- s->max_backward_distance - s->custom_dict_size;
+ s->state = BROTLI_STATE_INITIALIZE;
+ /* Fall through. */
+
+ case BROTLI_STATE_INITIALIZE:
+ BROTLI_LOG_UINT(s->window_bits);
+ /* Maximum distance, see section 9.1. of the spec. */
+ s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP;
/* Allocate memory for both block_type_trees and block_len_trees. */
- s->block_type_trees = (HuffmanCode*)BROTLI_ALLOC(s,
+ s->block_type_trees = (HuffmanCode*)BROTLI_DECODER_ALLOC(s,
sizeof(HuffmanCode) * 3 *
(BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26));
if (s->block_type_trees == 0) {
- result = BROTLI_FAILURE(BROTLI_ERROR_ALLOC_BLOCK_TYPE_TREES);
+ 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 */
+ /* Fall through. */
+
case BROTLI_STATE_METABLOCK_BEGIN:
- BrotliStateMetablockBegin(s);
+ BrotliDecoderStateMetablockBegin(s);
BROTLI_LOG_UINT(s->pos);
s->state = BROTLI_STATE_METABLOCK_HEADER;
- /* No break, continue to next state */
+ /* Fall through. */
+
case BROTLI_STATE_METABLOCK_HEADER:
- result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */
- if (result != BROTLI_SUCCESS) {
+ result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */
+ if (result != BROTLI_DECODER_SUCCESS) {
break;
}
BROTLI_LOG_UINT(s->is_last_metablock);
@@ -1967,7 +2150,7 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
BROTLI_LOG_UINT(s->is_uncompressed);
if (s->is_metadata || s->is_uncompressed) {
if (!BrotliJumpToByteBoundary(br)) {
- result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_PADDING_1);
+ result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1);
break;
}
}
@@ -1979,9 +2162,7 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
s->state = BROTLI_STATE_METABLOCK_DONE;
break;
}
- if (!s->ringbuffer) {
- BrotliCalculateRingBufferSize(s, br);
- }
+ BrotliCalculateRingBufferSize(s);
if (s->is_uncompressed) {
s->state = BROTLI_STATE_UNCOMPRESSED;
break;
@@ -1989,30 +2170,31 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
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_SUCCESS) {
+ 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_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
break;
}
}
- if (result == BROTLI_SUCCESS) {
+ if (result == BROTLI_DECODER_SUCCESS) {
s->state = BROTLI_STATE_METABLOCK_DONE;
}
break;
+
case BROTLI_STATE_HUFFMAN_CODE_0:
if (s->loop_counter >= 3) {
s->state = BROTLI_STATE_METABLOCK_HEADER_2;
@@ -2020,7 +2202,7 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
}
/* Reads 1..11 bits. */
result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]);
- if (result != BROTLI_SUCCESS) {
+ if (result != BROTLI_DECODER_SUCCESS) {
break;
}
s->num_block_types[s->loop_counter]++;
@@ -2030,28 +2212,33 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
break;
}
s->state = BROTLI_STATE_HUFFMAN_CODE_1;
- /* No break, continue to next state */
+ /* Fall through. */
+
case BROTLI_STATE_HUFFMAN_CODE_1: {
+ uint32_t alphabet_size = s->num_block_types[s->loop_counter] + 2;
int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258;
- result = ReadHuffmanCode(s->num_block_types[s->loop_counter] + 2,
+ result = ReadHuffmanCode(alphabet_size, alphabet_size,
&s->block_type_trees[tree_offset], NULL, s);
- if (result != BROTLI_SUCCESS) break;
+ if (result != BROTLI_DECODER_SUCCESS) break;
s->state = BROTLI_STATE_HUFFMAN_CODE_2;
- /* No break, continue to next state */
}
+ /* Fall through. */
+
case BROTLI_STATE_HUFFMAN_CODE_2: {
+ uint32_t alphabet_size = BROTLI_NUM_BLOCK_LEN_SYMBOLS;
int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
- result = ReadHuffmanCode(kNumBlockLengthCodes,
+ result = ReadHuffmanCode(alphabet_size, alphabet_size,
&s->block_len_trees[tree_offset], NULL, s);
- if (result != BROTLI_SUCCESS) break;
+ if (result != BROTLI_DECODER_SUCCESS) break;
s->state = BROTLI_STATE_HUFFMAN_CODE_3;
- /* No break, continue to next state */
}
+ /* Fall through. */
+
case BROTLI_STATE_HUFFMAN_CODE_3: {
int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter],
&s->block_len_trees[tree_offset], br)) {
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
break;
}
BROTLI_LOG_UINT(s->block_length[s->loop_counter]);
@@ -2059,126 +2246,141 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
s->state = BROTLI_STATE_HUFFMAN_CODE_0;
break;
}
+
case BROTLI_STATE_METABLOCK_HEADER_2: {
uint32_t bits;
if (!BrotliSafeReadBits(br, 6, &bits)) {
- result = BROTLI_NEEDS_MORE_INPUT;
+ result = BROTLI_DECODER_NEEDS_MORE_INPUT;
break;
}
s->distance_postfix_bits = bits & BitMask(2);
bits >>= 2;
- s->num_direct_distance_codes =
- NUM_DISTANCE_SHORT_CODES + (bits << s->distance_postfix_bits);
+ 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]);
+ (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)s->num_block_types[0]);
if (s->context_modes == 0) {
- result = BROTLI_FAILURE(BROTLI_ERROR_ALLOC_CONTEXT_MODES);
+ 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 */
}
+ /* Fall through. */
+
case BROTLI_STATE_CONTEXT_MODES:
result = ReadContextModes(s);
- if (result != BROTLI_SUCCESS) {
+ if (result != BROTLI_DECODER_SUCCESS) {
break;
}
s->state = BROTLI_STATE_CONTEXT_MAP_1;
- /* No break, continue to next state */
+ /* Fall through. */
+
case BROTLI_STATE_CONTEXT_MAP_1:
result = DecodeContextMap(
- s->num_block_types[0] << kLiteralContextBits,
+ s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS,
&s->num_literal_htrees, &s->context_map, s);
- if (result != BROTLI_SUCCESS) {
+ 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] << kDistanceContextBits,
- &s->num_dist_htrees, &s->dist_context_map, s);
- if (result != BROTLI_SUCCESS) {
- break;
- }
- BrotliHuffmanTreeGroupInit(s, &s->literal_hgroup, kNumLiteralCodes,
- s->num_literal_htrees);
- BrotliHuffmanTreeGroupInit(s, &s->insert_copy_hgroup,
- kNumInsertAndCopyCodes,
- s->num_block_types[1]);
- BrotliHuffmanTreeGroupInit(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_ERROR_ALLOC_TREE_GROUPS));
- }
+ /* Fall through. */
+
+ case BROTLI_STATE_CONTEXT_MAP_2: {
+ uint32_t num_direct_codes =
+ s->num_direct_distance_codes - BROTLI_NUM_DISTANCE_SHORT_CODES;
+ uint32_t num_distance_codes = BROTLI_DISTANCE_ALPHABET_SIZE(
+ s->distance_postfix_bits, num_direct_codes,
+ (s->large_window ? BROTLI_LARGE_MAX_DISTANCE_BITS :
+ BROTLI_MAX_DISTANCE_BITS));
+ uint32_t max_distance_symbol = (s->large_window ?
+ BrotliMaxDistanceSymbol(
+ num_direct_codes, s->distance_postfix_bits) :
+ num_distance_codes);
+ BROTLI_BOOL allocation_success = BROTLI_TRUE;
+ result = DecodeContextMap(
+ s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS,
+ &s->num_dist_htrees, &s->dist_context_map, s);
+ if (result != BROTLI_DECODER_SUCCESS) {
+ break;
+ }
+ allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
+ s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS,
+ BROTLI_NUM_LITERAL_SYMBOLS, s->num_literal_htrees);
+ allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
+ s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS,
+ BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]);
+ allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
+ s, &s->distance_hgroup, num_distance_codes,
+ max_distance_symbol, s->num_dist_htrees);
+ if (!allocation_success) {
+ 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_ERROR_UNREACHABLE));
- }
- result = HuffmanTreeGroupDecode(hgroup, s);
+ }
+ /* Fall through. */
+
+ case BROTLI_STATE_TREE_GROUP: {
+ HuffmanTreeGroup* hgroup = NULL;
+ switch (s->loop_counter) {
+ case 0: hgroup = &s->literal_hgroup; break;
+ case 1: hgroup = &s->insert_copy_hgroup; break;
+ case 2: hgroup = &s->distance_hgroup; break;
+ default: return SaveErrorCode(s, BROTLI_FAILURE(
+ BROTLI_DECODER_ERROR_UNREACHABLE));
}
- if (result != BROTLI_SUCCESS) break;
+ 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_ERROR_ALLOC_RING_BUFFER_2);
+ if (!BrotliEnsureRingBuffer(s)) {
+ result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2);
break;
}
s->state = BROTLI_STATE_COMMAND_BEGIN;
}
break;
+ }
+
case BROTLI_STATE_COMMAND_BEGIN:
+ /* Fall through. */
case BROTLI_STATE_COMMAND_INNER:
+ /* Fall through. */
case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS:
+ /* Fall through. */
case BROTLI_STATE_COMMAND_POST_WRAP_COPY:
result = ProcessCommands(s);
- if (result == BROTLI_NEEDS_MORE_INPUT) {
+ if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
result = SafeProcessCommands(s);
}
break;
+
case BROTLI_STATE_COMMAND_INNER_WRITE:
+ /* Fall through. */
case BROTLI_STATE_COMMAND_POST_WRITE_1:
+ /* Fall through. */
case BROTLI_STATE_COMMAND_POST_WRITE_2:
- result = WriteRingBuffer(available_out, next_out, total_out, s);
- if (result != BROTLI_SUCCESS) {
+ result = WriteRingBuffer(
+ s, available_out, next_out, total_out, BROTLI_FALSE);
+ if (result != BROTLI_DECODER_SUCCESS) {
break;
}
- s->max_distance = s->max_backward_distance;
+ WrapRingBuffer(s);
+ if (s->ringbuffer_size == 1 << s->window_bits) {
+ s->max_distance = s->max_backward_distance;
+ }
if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {
- memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);
if (s->meta_block_remaining_len == 0) {
- /* Next metablock, if any */
+ /* Next metablock, if any. */
s->state = BROTLI_STATE_METABLOCK_DONE;
} else {
s->state = BROTLI_STATE_COMMAND_BEGIN;
@@ -2198,18 +2400,19 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
s->state = BROTLI_STATE_COMMAND_INNER;
}
break;
+
case BROTLI_STATE_METABLOCK_DONE:
if (s->meta_block_remaining_len < 0) {
- result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_BLOCK_LENGTH_2);
+ result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2);
break;
}
- BrotliStateCleanupAfterMetablock(s);
+ BrotliDecoderStateCleanupAfterMetablock(s);
if (!s->is_last_metablock) {
s->state = BROTLI_STATE_METABLOCK_BEGIN;
break;
}
if (!BrotliJumpToByteBoundary(br)) {
- result = BROTLI_FAILURE(BROTLI_ERROR_FORMAT_PADDING_2);
+ result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2);
break;
}
if (s->buffer_length == 0) {
@@ -2218,11 +2421,13 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
*next_in = br->next_in;
}
s->state = BROTLI_STATE_DONE;
- /* No break, continue to next state */
+ /* Fall through. */
+
case BROTLI_STATE_DONE:
if (s->ringbuffer != 0) {
- result = WriteRingBuffer(available_out, next_out, total_out, s);
- if (result != BROTLI_SUCCESS) {
+ result = WriteRingBuffer(
+ s, available_out, next_out, total_out, BROTLI_TRUE);
+ if (result != BROTLI_DECODER_SUCCESS) {
break;
}
}
@@ -2232,31 +2437,70 @@ BrotliResult BrotliDecompressStream(size_t* available_in,
return SaveErrorCode(s, result);
}
-void BrotliSetCustomDictionary(
- size_t size, const uint8_t* dict, BrotliState* s) {
- if (size > (1u << 24)) {
- return;
+BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) {
+ /* After unrecoverable error remaining output is considered nonsensical. */
+ if ((int)s->error_code < 0) {
+ return BROTLI_FALSE;
+ }
+ return TO_BROTLI_BOOL(
+ s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0);
+}
+
+const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) {
+ uint8_t* result = 0;
+ size_t available_out = *size ? *size : 1u << 24;
+ size_t requested_out = available_out;
+ BrotliDecoderErrorCode status;
+ if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) {
+ *size = 0;
+ return 0;
+ }
+ WrapRingBuffer(s);
+ status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE);
+ /* Either WriteRingBuffer returns those "success" codes... */
+ if (status == BROTLI_DECODER_SUCCESS ||
+ status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) {
+ *size = requested_out - available_out;
+ } else {
+ /* ... or stream is broken. Normally this should be caught by
+ BrotliDecoderDecompressStream, this is just a safeguard. */
+ if ((int)status < 0) SaveErrorCode(s, status);
+ *size = 0;
+ result = 0;
}
- s->custom_dict = dict;
- s->custom_dict_size = (int)size;
+ return result;
+}
+
+BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) {
+ return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED ||
+ BrotliGetAvailableBits(&s->br) != 0);
}
-BrotliErrorCode BrotliGetErrorCode(const BrotliState* s) {
- return (BrotliErrorCode)s->error_code;
+BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) {
+ return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) &&
+ !BrotliDecoderHasMoreOutput(s);
}
-const char* BrotliErrorString(BrotliErrorCode c) {
+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 ## PREFIX ## NAME: return #NAME;
-#define _BROTLI_NOTHING
- BROTLI_ERROR_CODES_LIST(_BROTLI_ERROR_CODE_CASE, _BROTLI_NOTHING)
-#undef _BROTLI_ERROR_CODE_CASE
-#undef _BROTLI_NOTHING
+#define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \
+ case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;
+#define BROTLI_NOTHING_
+ BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_)
+#undef BROTLI_ERROR_CODE_CASE_
+#undef BROTLI_NOTHING_
default: return "INVALID";
}
}
+uint32_t BrotliDecoderVersion() {
+ return BROTLI_VERSION;
+}
+
#if defined(__cplusplus) || defined(c_plusplus)
} /* extern "C" */
#endif