1*f4ee7fbaSAndroid Build Coastguard Worker /* Copyright 2013 Google Inc. All Rights Reserved.
2*f4ee7fbaSAndroid Build Coastguard Worker
3*f4ee7fbaSAndroid Build Coastguard Worker Distributed under MIT license.
4*f4ee7fbaSAndroid Build Coastguard Worker See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5*f4ee7fbaSAndroid Build Coastguard Worker */
6*f4ee7fbaSAndroid Build Coastguard Worker
7*f4ee7fbaSAndroid Build Coastguard Worker #include <brotli/decode.h>
8*f4ee7fbaSAndroid Build Coastguard Worker
9*f4ee7fbaSAndroid Build Coastguard Worker #include <stdlib.h> /* free, malloc */
10*f4ee7fbaSAndroid Build Coastguard Worker #include <string.h> /* memcpy, memset */
11*f4ee7fbaSAndroid Build Coastguard Worker
12*f4ee7fbaSAndroid Build Coastguard Worker #include "../common/constants.h"
13*f4ee7fbaSAndroid Build Coastguard Worker #include "../common/context.h"
14*f4ee7fbaSAndroid Build Coastguard Worker #include "../common/dictionary.h"
15*f4ee7fbaSAndroid Build Coastguard Worker #include "../common/platform.h"
16*f4ee7fbaSAndroid Build Coastguard Worker #include "../common/transform.h"
17*f4ee7fbaSAndroid Build Coastguard Worker #include "../common/version.h"
18*f4ee7fbaSAndroid Build Coastguard Worker #include "./bit_reader.h"
19*f4ee7fbaSAndroid Build Coastguard Worker #include "./huffman.h"
20*f4ee7fbaSAndroid Build Coastguard Worker #include "./prefix.h"
21*f4ee7fbaSAndroid Build Coastguard Worker #include "./state.h"
22*f4ee7fbaSAndroid Build Coastguard Worker
23*f4ee7fbaSAndroid Build Coastguard Worker #if defined(BROTLI_TARGET_NEON)
24*f4ee7fbaSAndroid Build Coastguard Worker #include <arm_neon.h>
25*f4ee7fbaSAndroid Build Coastguard Worker #endif
26*f4ee7fbaSAndroid Build Coastguard Worker
27*f4ee7fbaSAndroid Build Coastguard Worker #if defined(__cplusplus) || defined(c_plusplus)
28*f4ee7fbaSAndroid Build Coastguard Worker extern "C" {
29*f4ee7fbaSAndroid Build Coastguard Worker #endif
30*f4ee7fbaSAndroid Build Coastguard Worker
31*f4ee7fbaSAndroid Build Coastguard Worker #define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE)
32*f4ee7fbaSAndroid Build Coastguard Worker
33*f4ee7fbaSAndroid Build Coastguard Worker #define BROTLI_LOG_UINT(name) \
34*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)))
35*f4ee7fbaSAndroid Build Coastguard Worker #define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \
36*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[%s] %s[%lu] = %lu\n", __func__, #array_name, \
37*f4ee7fbaSAndroid Build Coastguard Worker (unsigned long)(idx), (unsigned long)array_name[idx]))
38*f4ee7fbaSAndroid Build Coastguard Worker
39*f4ee7fbaSAndroid Build Coastguard Worker #define HUFFMAN_TABLE_BITS 8U
40*f4ee7fbaSAndroid Build Coastguard Worker #define HUFFMAN_TABLE_MASK 0xFF
41*f4ee7fbaSAndroid Build Coastguard Worker
42*f4ee7fbaSAndroid Build Coastguard Worker /* We need the slack region for the following reasons:
43*f4ee7fbaSAndroid Build Coastguard Worker - doing up to two 16-byte copies for fast backward copying
44*f4ee7fbaSAndroid Build Coastguard Worker - inserting transformed dictionary word:
45*f4ee7fbaSAndroid Build Coastguard Worker 5 prefix + 24 base + 8 suffix */
46*f4ee7fbaSAndroid Build Coastguard Worker static const uint32_t kRingBufferWriteAheadSlack = 42;
47*f4ee7fbaSAndroid Build Coastguard Worker
48*f4ee7fbaSAndroid Build Coastguard Worker static const uint8_t kCodeLengthCodeOrder[BROTLI_CODE_LENGTH_CODES] = {
49*f4ee7fbaSAndroid Build Coastguard Worker 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
50*f4ee7fbaSAndroid Build Coastguard Worker };
51*f4ee7fbaSAndroid Build Coastguard Worker
52*f4ee7fbaSAndroid Build Coastguard Worker /* Static prefix code for the complex code length code lengths. */
53*f4ee7fbaSAndroid Build Coastguard Worker static const uint8_t kCodeLengthPrefixLength[16] = {
54*f4ee7fbaSAndroid Build Coastguard Worker 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4,
55*f4ee7fbaSAndroid Build Coastguard Worker };
56*f4ee7fbaSAndroid Build Coastguard Worker
57*f4ee7fbaSAndroid Build Coastguard Worker static const uint8_t kCodeLengthPrefixValue[16] = {
58*f4ee7fbaSAndroid Build Coastguard Worker 0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,
59*f4ee7fbaSAndroid Build Coastguard Worker };
60*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderSetParameter(BrotliDecoderState * state,BrotliDecoderParameter p,uint32_t value)61*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL BrotliDecoderSetParameter(
62*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* state, BrotliDecoderParameter p, uint32_t value) {
63*f4ee7fbaSAndroid Build Coastguard Worker if (state->state != BROTLI_STATE_UNINITED) return BROTLI_FALSE;
64*f4ee7fbaSAndroid Build Coastguard Worker switch (p) {
65*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION:
66*f4ee7fbaSAndroid Build Coastguard Worker state->canny_ringbuffer_allocation = !!value ? 0 : 1;
67*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
68*f4ee7fbaSAndroid Build Coastguard Worker
69*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_DECODER_PARAM_LARGE_WINDOW:
70*f4ee7fbaSAndroid Build Coastguard Worker state->large_window = TO_BROTLI_BOOL(!!value);
71*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
72*f4ee7fbaSAndroid Build Coastguard Worker
73*f4ee7fbaSAndroid Build Coastguard Worker default: return BROTLI_FALSE;
74*f4ee7fbaSAndroid Build Coastguard Worker }
75*f4ee7fbaSAndroid Build Coastguard Worker }
76*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderCreateInstance(brotli_alloc_func alloc_func,brotli_free_func free_func,void * opaque)77*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* BrotliDecoderCreateInstance(
78*f4ee7fbaSAndroid Build Coastguard Worker brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) {
79*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* state = 0;
80*f4ee7fbaSAndroid Build Coastguard Worker if (!alloc_func && !free_func) {
81*f4ee7fbaSAndroid Build Coastguard Worker state = (BrotliDecoderState*)malloc(sizeof(BrotliDecoderState));
82*f4ee7fbaSAndroid Build Coastguard Worker } else if (alloc_func && free_func) {
83*f4ee7fbaSAndroid Build Coastguard Worker state = (BrotliDecoderState*)alloc_func(opaque, sizeof(BrotliDecoderState));
84*f4ee7fbaSAndroid Build Coastguard Worker }
85*f4ee7fbaSAndroid Build Coastguard Worker if (state == 0) {
86*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DUMP();
87*f4ee7fbaSAndroid Build Coastguard Worker return 0;
88*f4ee7fbaSAndroid Build Coastguard Worker }
89*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliDecoderStateInit(state, alloc_func, free_func, opaque)) {
90*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DUMP();
91*f4ee7fbaSAndroid Build Coastguard Worker if (!alloc_func && !free_func) {
92*f4ee7fbaSAndroid Build Coastguard Worker free(state);
93*f4ee7fbaSAndroid Build Coastguard Worker } else if (alloc_func && free_func) {
94*f4ee7fbaSAndroid Build Coastguard Worker free_func(opaque, state);
95*f4ee7fbaSAndroid Build Coastguard Worker }
96*f4ee7fbaSAndroid Build Coastguard Worker return 0;
97*f4ee7fbaSAndroid Build Coastguard Worker }
98*f4ee7fbaSAndroid Build Coastguard Worker return state;
99*f4ee7fbaSAndroid Build Coastguard Worker }
100*f4ee7fbaSAndroid Build Coastguard Worker
101*f4ee7fbaSAndroid Build Coastguard Worker /* Deinitializes and frees BrotliDecoderState instance. */
BrotliDecoderDestroyInstance(BrotliDecoderState * state)102*f4ee7fbaSAndroid Build Coastguard Worker void BrotliDecoderDestroyInstance(BrotliDecoderState* state) {
103*f4ee7fbaSAndroid Build Coastguard Worker if (!state) {
104*f4ee7fbaSAndroid Build Coastguard Worker return;
105*f4ee7fbaSAndroid Build Coastguard Worker } else {
106*f4ee7fbaSAndroid Build Coastguard Worker brotli_free_func free_func = state->free_func;
107*f4ee7fbaSAndroid Build Coastguard Worker void* opaque = state->memory_manager_opaque;
108*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderStateCleanup(state);
109*f4ee7fbaSAndroid Build Coastguard Worker free_func(opaque, state);
110*f4ee7fbaSAndroid Build Coastguard Worker }
111*f4ee7fbaSAndroid Build Coastguard Worker }
112*f4ee7fbaSAndroid Build Coastguard Worker
113*f4ee7fbaSAndroid Build Coastguard Worker /* Saves error code and converts it to BrotliDecoderResult. */
SaveErrorCode(BrotliDecoderState * s,BrotliDecoderErrorCode e)114*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_NOINLINE BrotliDecoderResult SaveErrorCode(
115*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliDecoderErrorCode e) {
116*f4ee7fbaSAndroid Build Coastguard Worker s->error_code = (int)e;
117*f4ee7fbaSAndroid Build Coastguard Worker switch (e) {
118*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_DECODER_SUCCESS:
119*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_RESULT_SUCCESS;
120*f4ee7fbaSAndroid Build Coastguard Worker
121*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_DECODER_NEEDS_MORE_INPUT:
122*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT;
123*f4ee7fbaSAndroid Build Coastguard Worker
124*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_DECODER_NEEDS_MORE_OUTPUT:
125*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT;
126*f4ee7fbaSAndroid Build Coastguard Worker
127*f4ee7fbaSAndroid Build Coastguard Worker default:
128*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_RESULT_ERROR;
129*f4ee7fbaSAndroid Build Coastguard Worker }
130*f4ee7fbaSAndroid Build Coastguard Worker }
131*f4ee7fbaSAndroid Build Coastguard Worker
132*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli".
133*f4ee7fbaSAndroid Build Coastguard Worker Precondition: bit-reader accumulator has at least 8 bits. */
DecodeWindowBits(BrotliDecoderState * s,BrotliBitReader * br)134*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode DecodeWindowBits(BrotliDecoderState* s,
135*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br) {
136*f4ee7fbaSAndroid Build Coastguard Worker uint32_t n;
137*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL large_window = s->large_window;
138*f4ee7fbaSAndroid Build Coastguard Worker s->large_window = BROTLI_FALSE;
139*f4ee7fbaSAndroid Build Coastguard Worker BrotliTakeBits(br, 1, &n);
140*f4ee7fbaSAndroid Build Coastguard Worker if (n == 0) {
141*f4ee7fbaSAndroid Build Coastguard Worker s->window_bits = 16;
142*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
143*f4ee7fbaSAndroid Build Coastguard Worker }
144*f4ee7fbaSAndroid Build Coastguard Worker BrotliTakeBits(br, 3, &n);
145*f4ee7fbaSAndroid Build Coastguard Worker if (n != 0) {
146*f4ee7fbaSAndroid Build Coastguard Worker s->window_bits = 17 + n;
147*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
148*f4ee7fbaSAndroid Build Coastguard Worker }
149*f4ee7fbaSAndroid Build Coastguard Worker BrotliTakeBits(br, 3, &n);
150*f4ee7fbaSAndroid Build Coastguard Worker if (n == 1) {
151*f4ee7fbaSAndroid Build Coastguard Worker if (large_window) {
152*f4ee7fbaSAndroid Build Coastguard Worker BrotliTakeBits(br, 1, &n);
153*f4ee7fbaSAndroid Build Coastguard Worker if (n == 1) {
154*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
155*f4ee7fbaSAndroid Build Coastguard Worker }
156*f4ee7fbaSAndroid Build Coastguard Worker s->large_window = BROTLI_TRUE;
157*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
158*f4ee7fbaSAndroid Build Coastguard Worker } else {
159*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
160*f4ee7fbaSAndroid Build Coastguard Worker }
161*f4ee7fbaSAndroid Build Coastguard Worker }
162*f4ee7fbaSAndroid Build Coastguard Worker if (n != 0) {
163*f4ee7fbaSAndroid Build Coastguard Worker s->window_bits = 8 + n;
164*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
165*f4ee7fbaSAndroid Build Coastguard Worker }
166*f4ee7fbaSAndroid Build Coastguard Worker s->window_bits = 17;
167*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
168*f4ee7fbaSAndroid Build Coastguard Worker }
169*f4ee7fbaSAndroid Build Coastguard Worker
memmove16(uint8_t * dst,uint8_t * src)170*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void memmove16(uint8_t* dst, uint8_t* src) {
171*f4ee7fbaSAndroid Build Coastguard Worker #if defined(BROTLI_TARGET_NEON)
172*f4ee7fbaSAndroid Build Coastguard Worker vst1q_u8(dst, vld1q_u8(src));
173*f4ee7fbaSAndroid Build Coastguard Worker #else
174*f4ee7fbaSAndroid Build Coastguard Worker uint32_t buffer[4];
175*f4ee7fbaSAndroid Build Coastguard Worker memcpy(buffer, src, 16);
176*f4ee7fbaSAndroid Build Coastguard Worker memcpy(dst, buffer, 16);
177*f4ee7fbaSAndroid Build Coastguard Worker #endif
178*f4ee7fbaSAndroid Build Coastguard Worker }
179*f4ee7fbaSAndroid Build Coastguard Worker
180*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
DecodeVarLenUint8(BrotliDecoderState * s,BrotliBitReader * br,uint32_t * value)181*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_NOINLINE BrotliDecoderErrorCode DecodeVarLenUint8(
182*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliBitReader* br, uint32_t* value) {
183*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
184*f4ee7fbaSAndroid Build Coastguard Worker switch (s->substate_decode_uint8) {
185*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_DECODE_UINT8_NONE:
186*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 1, &bits))) {
187*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
188*f4ee7fbaSAndroid Build Coastguard Worker }
189*f4ee7fbaSAndroid Build Coastguard Worker if (bits == 0) {
190*f4ee7fbaSAndroid Build Coastguard Worker *value = 0;
191*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
192*f4ee7fbaSAndroid Build Coastguard Worker }
193*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
194*f4ee7fbaSAndroid Build Coastguard Worker
195*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_DECODE_UINT8_SHORT:
196*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, 3, &bits))) {
197*f4ee7fbaSAndroid Build Coastguard Worker s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_SHORT;
198*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
199*f4ee7fbaSAndroid Build Coastguard Worker }
200*f4ee7fbaSAndroid Build Coastguard Worker if (bits == 0) {
201*f4ee7fbaSAndroid Build Coastguard Worker *value = 1;
202*f4ee7fbaSAndroid Build Coastguard Worker s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
203*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
204*f4ee7fbaSAndroid Build Coastguard Worker }
205*f4ee7fbaSAndroid Build Coastguard Worker /* Use output value as a temporary storage. It MUST be persisted. */
206*f4ee7fbaSAndroid Build Coastguard Worker *value = bits;
207*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
208*f4ee7fbaSAndroid Build Coastguard Worker
209*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_DECODE_UINT8_LONG:
210*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, *value, &bits))) {
211*f4ee7fbaSAndroid Build Coastguard Worker s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_LONG;
212*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
213*f4ee7fbaSAndroid Build Coastguard Worker }
214*f4ee7fbaSAndroid Build Coastguard Worker *value = (1U << *value) + bits;
215*f4ee7fbaSAndroid Build Coastguard Worker s->substate_decode_uint8 = BROTLI_STATE_DECODE_UINT8_NONE;
216*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
217*f4ee7fbaSAndroid Build Coastguard Worker
218*f4ee7fbaSAndroid Build Coastguard Worker default:
219*f4ee7fbaSAndroid Build Coastguard Worker return
220*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
221*f4ee7fbaSAndroid Build Coastguard Worker }
222*f4ee7fbaSAndroid Build Coastguard Worker }
223*f4ee7fbaSAndroid Build Coastguard Worker
224*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes a metablock length and flags by reading 2 - 31 bits. */
DecodeMetaBlockLength(BrotliDecoderState * s,BrotliBitReader * br)225*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode BROTLI_NOINLINE DecodeMetaBlockLength(
226*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliBitReader* br) {
227*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
228*f4ee7fbaSAndroid Build Coastguard Worker int i;
229*f4ee7fbaSAndroid Build Coastguard Worker for (;;) {
230*f4ee7fbaSAndroid Build Coastguard Worker switch (s->substate_metablock_header) {
231*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_NONE:
232*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 1, &bits)) {
233*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
234*f4ee7fbaSAndroid Build Coastguard Worker }
235*f4ee7fbaSAndroid Build Coastguard Worker s->is_last_metablock = bits ? 1 : 0;
236*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len = 0;
237*f4ee7fbaSAndroid Build Coastguard Worker s->is_uncompressed = 0;
238*f4ee7fbaSAndroid Build Coastguard Worker s->is_metadata = 0;
239*f4ee7fbaSAndroid Build Coastguard Worker if (!s->is_last_metablock) {
240*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
241*f4ee7fbaSAndroid Build Coastguard Worker break;
242*f4ee7fbaSAndroid Build Coastguard Worker }
243*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_EMPTY;
244*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
245*f4ee7fbaSAndroid Build Coastguard Worker
246*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_EMPTY:
247*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 1, &bits)) {
248*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
249*f4ee7fbaSAndroid Build Coastguard Worker }
250*f4ee7fbaSAndroid Build Coastguard Worker if (bits) {
251*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
252*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
253*f4ee7fbaSAndroid Build Coastguard Worker }
254*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NIBBLES;
255*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
256*f4ee7fbaSAndroid Build Coastguard Worker
257*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_NIBBLES:
258*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 2, &bits)) {
259*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
260*f4ee7fbaSAndroid Build Coastguard Worker }
261*f4ee7fbaSAndroid Build Coastguard Worker s->size_nibbles = (uint8_t)(bits + 4);
262*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = 0;
263*f4ee7fbaSAndroid Build Coastguard Worker if (bits == 3) {
264*f4ee7fbaSAndroid Build Coastguard Worker s->is_metadata = 1;
265*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_RESERVED;
266*f4ee7fbaSAndroid Build Coastguard Worker break;
267*f4ee7fbaSAndroid Build Coastguard Worker }
268*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_SIZE;
269*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
270*f4ee7fbaSAndroid Build Coastguard Worker
271*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_SIZE:
272*f4ee7fbaSAndroid Build Coastguard Worker i = s->loop_counter;
273*f4ee7fbaSAndroid Build Coastguard Worker for (; i < (int)s->size_nibbles; ++i) {
274*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 4, &bits)) {
275*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = i;
276*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
277*f4ee7fbaSAndroid Build Coastguard Worker }
278*f4ee7fbaSAndroid Build Coastguard Worker if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 4 &&
279*f4ee7fbaSAndroid Build Coastguard Worker bits == 0) {
280*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE);
281*f4ee7fbaSAndroid Build Coastguard Worker }
282*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len |= (int)(bits << (i * 4));
283*f4ee7fbaSAndroid Build Coastguard Worker }
284*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header =
285*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED;
286*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
287*f4ee7fbaSAndroid Build Coastguard Worker
288*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED:
289*f4ee7fbaSAndroid Build Coastguard Worker if (!s->is_last_metablock) {
290*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 1, &bits)) {
291*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
292*f4ee7fbaSAndroid Build Coastguard Worker }
293*f4ee7fbaSAndroid Build Coastguard Worker s->is_uncompressed = bits ? 1 : 0;
294*f4ee7fbaSAndroid Build Coastguard Worker }
295*f4ee7fbaSAndroid Build Coastguard Worker ++s->meta_block_remaining_len;
296*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
297*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
298*f4ee7fbaSAndroid Build Coastguard Worker
299*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_RESERVED:
300*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 1, &bits)) {
301*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
302*f4ee7fbaSAndroid Build Coastguard Worker }
303*f4ee7fbaSAndroid Build Coastguard Worker if (bits != 0) {
304*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED);
305*f4ee7fbaSAndroid Build Coastguard Worker }
306*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_BYTES;
307*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
308*f4ee7fbaSAndroid Build Coastguard Worker
309*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_BYTES:
310*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 2, &bits)) {
311*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
312*f4ee7fbaSAndroid Build Coastguard Worker }
313*f4ee7fbaSAndroid Build Coastguard Worker if (bits == 0) {
314*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
315*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
316*f4ee7fbaSAndroid Build Coastguard Worker }
317*f4ee7fbaSAndroid Build Coastguard Worker s->size_nibbles = (uint8_t)bits;
318*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_METADATA;
319*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
320*f4ee7fbaSAndroid Build Coastguard Worker
321*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_METADATA:
322*f4ee7fbaSAndroid Build Coastguard Worker i = s->loop_counter;
323*f4ee7fbaSAndroid Build Coastguard Worker for (; i < (int)s->size_nibbles; ++i) {
324*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 8, &bits)) {
325*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = i;
326*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
327*f4ee7fbaSAndroid Build Coastguard Worker }
328*f4ee7fbaSAndroid Build Coastguard Worker if (i + 1 == (int)s->size_nibbles && s->size_nibbles > 1 &&
329*f4ee7fbaSAndroid Build Coastguard Worker bits == 0) {
330*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(
331*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE);
332*f4ee7fbaSAndroid Build Coastguard Worker }
333*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len |= (int)(bits << (i * 8));
334*f4ee7fbaSAndroid Build Coastguard Worker }
335*f4ee7fbaSAndroid Build Coastguard Worker ++s->meta_block_remaining_len;
336*f4ee7fbaSAndroid Build Coastguard Worker s->substate_metablock_header = BROTLI_STATE_METABLOCK_HEADER_NONE;
337*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
338*f4ee7fbaSAndroid Build Coastguard Worker
339*f4ee7fbaSAndroid Build Coastguard Worker default:
340*f4ee7fbaSAndroid Build Coastguard Worker return
341*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
342*f4ee7fbaSAndroid Build Coastguard Worker }
343*f4ee7fbaSAndroid Build Coastguard Worker }
344*f4ee7fbaSAndroid Build Coastguard Worker }
345*f4ee7fbaSAndroid Build Coastguard Worker
346*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes the Huffman code.
347*f4ee7fbaSAndroid Build Coastguard Worker This method doesn't read data from the bit reader, BUT drops the amount of
348*f4ee7fbaSAndroid Build Coastguard Worker bits that correspond to the decoded symbol.
349*f4ee7fbaSAndroid Build Coastguard Worker bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */
DecodeSymbol(uint32_t bits,const HuffmanCode * table,BrotliBitReader * br)350*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE uint32_t DecodeSymbol(uint32_t bits,
351*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* table,
352*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br) {
353*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
354*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(table, bits & HUFFMAN_TABLE_MASK);
355*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_HC_FAST_LOAD_BITS(table) > HUFFMAN_TABLE_BITS) {
356*f4ee7fbaSAndroid Build Coastguard Worker uint32_t nbits = BROTLI_HC_FAST_LOAD_BITS(table) - HUFFMAN_TABLE_BITS;
357*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, HUFFMAN_TABLE_BITS);
358*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(table,
359*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_FAST_LOAD_VALUE(table) +
360*f4ee7fbaSAndroid Build Coastguard Worker ((bits >> HUFFMAN_TABLE_BITS) & BitMask(nbits)));
361*f4ee7fbaSAndroid Build Coastguard Worker }
362*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table));
363*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_HC_FAST_LOAD_VALUE(table);
364*f4ee7fbaSAndroid Build Coastguard Worker }
365*f4ee7fbaSAndroid Build Coastguard Worker
366*f4ee7fbaSAndroid Build Coastguard Worker /* Reads and decodes the next Huffman code from bit-stream.
367*f4ee7fbaSAndroid Build Coastguard Worker This method peeks 16 bits of input and drops 0 - 15 of them. */
ReadSymbol(const HuffmanCode * table,BrotliBitReader * br)368*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE uint32_t ReadSymbol(const HuffmanCode* table,
369*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br) {
370*f4ee7fbaSAndroid Build Coastguard Worker return DecodeSymbol(BrotliGet16BitsUnmasked(br), table, br);
371*f4ee7fbaSAndroid Build Coastguard Worker }
372*f4ee7fbaSAndroid Build Coastguard Worker
373*f4ee7fbaSAndroid Build Coastguard Worker /* Same as DecodeSymbol, but it is known that there is less than 15 bits of
374*f4ee7fbaSAndroid Build Coastguard Worker input are currently available. */
SafeDecodeSymbol(const HuffmanCode * table,BrotliBitReader * br,uint32_t * result)375*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_NOINLINE BROTLI_BOOL SafeDecodeSymbol(
376*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
377*f4ee7fbaSAndroid Build Coastguard Worker uint32_t val;
378*f4ee7fbaSAndroid Build Coastguard Worker uint32_t available_bits = BrotliGetAvailableBits(br);
379*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
380*f4ee7fbaSAndroid Build Coastguard Worker if (available_bits == 0) {
381*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_HC_FAST_LOAD_BITS(table) == 0) {
382*f4ee7fbaSAndroid Build Coastguard Worker *result = BROTLI_HC_FAST_LOAD_VALUE(table);
383*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
384*f4ee7fbaSAndroid Build Coastguard Worker }
385*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE; /* No valid bits at all. */
386*f4ee7fbaSAndroid Build Coastguard Worker }
387*f4ee7fbaSAndroid Build Coastguard Worker val = (uint32_t)BrotliGetBitsUnmasked(br);
388*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(table, val & HUFFMAN_TABLE_MASK);
389*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_HC_FAST_LOAD_BITS(table) <= HUFFMAN_TABLE_BITS) {
390*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_HC_FAST_LOAD_BITS(table) <= available_bits) {
391*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(table));
392*f4ee7fbaSAndroid Build Coastguard Worker *result = BROTLI_HC_FAST_LOAD_VALUE(table);
393*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
394*f4ee7fbaSAndroid Build Coastguard Worker } else {
395*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE; /* Not enough bits for the first level. */
396*f4ee7fbaSAndroid Build Coastguard Worker }
397*f4ee7fbaSAndroid Build Coastguard Worker }
398*f4ee7fbaSAndroid Build Coastguard Worker if (available_bits <= HUFFMAN_TABLE_BITS) {
399*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE; /* Not enough bits to move to the second level. */
400*f4ee7fbaSAndroid Build Coastguard Worker }
401*f4ee7fbaSAndroid Build Coastguard Worker
402*f4ee7fbaSAndroid Build Coastguard Worker /* Speculatively drop HUFFMAN_TABLE_BITS. */
403*f4ee7fbaSAndroid Build Coastguard Worker val = (val & BitMask(BROTLI_HC_FAST_LOAD_BITS(table))) >> HUFFMAN_TABLE_BITS;
404*f4ee7fbaSAndroid Build Coastguard Worker available_bits -= HUFFMAN_TABLE_BITS;
405*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(table, BROTLI_HC_FAST_LOAD_VALUE(table) + val);
406*f4ee7fbaSAndroid Build Coastguard Worker if (available_bits < BROTLI_HC_FAST_LOAD_BITS(table)) {
407*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE; /* Not enough bits for the second level. */
408*f4ee7fbaSAndroid Build Coastguard Worker }
409*f4ee7fbaSAndroid Build Coastguard Worker
410*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, HUFFMAN_TABLE_BITS + BROTLI_HC_FAST_LOAD_BITS(table));
411*f4ee7fbaSAndroid Build Coastguard Worker *result = BROTLI_HC_FAST_LOAD_VALUE(table);
412*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
413*f4ee7fbaSAndroid Build Coastguard Worker }
414*f4ee7fbaSAndroid Build Coastguard Worker
SafeReadSymbol(const HuffmanCode * table,BrotliBitReader * br,uint32_t * result)415*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL SafeReadSymbol(
416*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* table, BrotliBitReader* br, uint32_t* result) {
417*f4ee7fbaSAndroid Build Coastguard Worker uint32_t val;
418*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br, 15, &val))) {
419*f4ee7fbaSAndroid Build Coastguard Worker *result = DecodeSymbol(val, table, br);
420*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
421*f4ee7fbaSAndroid Build Coastguard Worker }
422*f4ee7fbaSAndroid Build Coastguard Worker return SafeDecodeSymbol(table, br, result);
423*f4ee7fbaSAndroid Build Coastguard Worker }
424*f4ee7fbaSAndroid Build Coastguard Worker
425*f4ee7fbaSAndroid Build Coastguard Worker /* Makes a look-up in first level Huffman table. Peeks 8 bits. */
PreloadSymbol(int safe,const HuffmanCode * table,BrotliBitReader * br,uint32_t * bits,uint32_t * value)426*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void PreloadSymbol(int safe,
427*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* table,
428*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br,
429*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* bits,
430*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* value) {
431*f4ee7fbaSAndroid Build Coastguard Worker if (safe) {
432*f4ee7fbaSAndroid Build Coastguard Worker return;
433*f4ee7fbaSAndroid Build Coastguard Worker }
434*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
435*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(table, BrotliGetBits(br, HUFFMAN_TABLE_BITS));
436*f4ee7fbaSAndroid Build Coastguard Worker *bits = BROTLI_HC_FAST_LOAD_BITS(table);
437*f4ee7fbaSAndroid Build Coastguard Worker *value = BROTLI_HC_FAST_LOAD_VALUE(table);
438*f4ee7fbaSAndroid Build Coastguard Worker }
439*f4ee7fbaSAndroid Build Coastguard Worker
440*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes the next Huffman code using data prepared by PreloadSymbol.
441*f4ee7fbaSAndroid Build Coastguard Worker Reads 0 - 15 bits. Also peeks 8 following bits. */
ReadPreloadedSymbol(const HuffmanCode * table,BrotliBitReader * br,uint32_t * bits,uint32_t * value)442*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE uint32_t ReadPreloadedSymbol(const HuffmanCode* table,
443*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br,
444*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* bits,
445*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* value) {
446*f4ee7fbaSAndroid Build Coastguard Worker uint32_t result = *value;
447*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {
448*f4ee7fbaSAndroid Build Coastguard Worker uint32_t val = BrotliGet16BitsUnmasked(br);
449*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value;
450*f4ee7fbaSAndroid Build Coastguard Worker uint32_t mask = BitMask((*bits - HUFFMAN_TABLE_BITS));
451*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(ext);
452*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, HUFFMAN_TABLE_BITS);
453*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(ext, (val >> HUFFMAN_TABLE_BITS) & mask);
454*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(ext));
455*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_HC_FAST_LOAD_VALUE(ext);
456*f4ee7fbaSAndroid Build Coastguard Worker } else {
457*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, *bits);
458*f4ee7fbaSAndroid Build Coastguard Worker }
459*f4ee7fbaSAndroid Build Coastguard Worker PreloadSymbol(0, table, br, bits, value);
460*f4ee7fbaSAndroid Build Coastguard Worker return result;
461*f4ee7fbaSAndroid Build Coastguard Worker }
462*f4ee7fbaSAndroid Build Coastguard Worker
Log2Floor(uint32_t x)463*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE uint32_t Log2Floor(uint32_t x) {
464*f4ee7fbaSAndroid Build Coastguard Worker uint32_t result = 0;
465*f4ee7fbaSAndroid Build Coastguard Worker while (x) {
466*f4ee7fbaSAndroid Build Coastguard Worker x >>= 1;
467*f4ee7fbaSAndroid Build Coastguard Worker ++result;
468*f4ee7fbaSAndroid Build Coastguard Worker }
469*f4ee7fbaSAndroid Build Coastguard Worker return result;
470*f4ee7fbaSAndroid Build Coastguard Worker }
471*f4ee7fbaSAndroid Build Coastguard Worker
472*f4ee7fbaSAndroid Build Coastguard Worker /* Reads (s->symbol + 1) symbols.
473*f4ee7fbaSAndroid Build Coastguard Worker Totally 1..4 symbols are read, 1..11 bits each.
474*f4ee7fbaSAndroid Build Coastguard Worker The list of symbols MUST NOT contain duplicates. */
ReadSimpleHuffmanSymbols(uint32_t alphabet_size_max,uint32_t alphabet_size_limit,BrotliDecoderState * s)475*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode ReadSimpleHuffmanSymbols(
476*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size_max, uint32_t alphabet_size_limit,
477*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
478*f4ee7fbaSAndroid Build Coastguard Worker /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */
479*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
480*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
481*f4ee7fbaSAndroid Build Coastguard Worker uint32_t max_bits = Log2Floor(alphabet_size_max - 1);
482*f4ee7fbaSAndroid Build Coastguard Worker uint32_t i = h->sub_loop_counter;
483*f4ee7fbaSAndroid Build Coastguard Worker uint32_t num_symbols = h->symbol;
484*f4ee7fbaSAndroid Build Coastguard Worker while (i <= num_symbols) {
485*f4ee7fbaSAndroid Build Coastguard Worker uint32_t v;
486*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br, max_bits, &v))) {
487*f4ee7fbaSAndroid Build Coastguard Worker h->sub_loop_counter = i;
488*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_READ;
489*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
490*f4ee7fbaSAndroid Build Coastguard Worker }
491*f4ee7fbaSAndroid Build Coastguard Worker if (v >= alphabet_size_limit) {
492*f4ee7fbaSAndroid Build Coastguard Worker return
493*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET);
494*f4ee7fbaSAndroid Build Coastguard Worker }
495*f4ee7fbaSAndroid Build Coastguard Worker h->symbols_lists_array[i] = (uint16_t)v;
496*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(h->symbols_lists_array[i]);
497*f4ee7fbaSAndroid Build Coastguard Worker ++i;
498*f4ee7fbaSAndroid Build Coastguard Worker }
499*f4ee7fbaSAndroid Build Coastguard Worker
500*f4ee7fbaSAndroid Build Coastguard Worker for (i = 0; i < num_symbols; ++i) {
501*f4ee7fbaSAndroid Build Coastguard Worker uint32_t k = i + 1;
502*f4ee7fbaSAndroid Build Coastguard Worker for (; k <= num_symbols; ++k) {
503*f4ee7fbaSAndroid Build Coastguard Worker if (h->symbols_lists_array[i] == h->symbols_lists_array[k]) {
504*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME);
505*f4ee7fbaSAndroid Build Coastguard Worker }
506*f4ee7fbaSAndroid Build Coastguard Worker }
507*f4ee7fbaSAndroid Build Coastguard Worker }
508*f4ee7fbaSAndroid Build Coastguard Worker
509*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
510*f4ee7fbaSAndroid Build Coastguard Worker }
511*f4ee7fbaSAndroid Build Coastguard Worker
512*f4ee7fbaSAndroid Build Coastguard Worker /* Process single decoded symbol code length:
513*f4ee7fbaSAndroid Build Coastguard Worker A) reset the repeat variable
514*f4ee7fbaSAndroid Build Coastguard Worker B) remember code length (if it is not 0)
515*f4ee7fbaSAndroid Build Coastguard Worker C) extend corresponding index-chain
516*f4ee7fbaSAndroid Build Coastguard Worker D) reduce the Huffman space
517*f4ee7fbaSAndroid Build Coastguard Worker E) update the histogram */
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)518*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void ProcessSingleCodeLength(uint32_t code_len,
519*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* symbol, uint32_t* repeat, uint32_t* space,
520*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* prev_code_len, uint16_t* symbol_lists,
521*f4ee7fbaSAndroid Build Coastguard Worker uint16_t* code_length_histo, int* next_symbol) {
522*f4ee7fbaSAndroid Build Coastguard Worker *repeat = 0;
523*f4ee7fbaSAndroid Build Coastguard Worker if (code_len != 0) { /* code_len == 1..15 */
524*f4ee7fbaSAndroid Build Coastguard Worker symbol_lists[next_symbol[code_len]] = (uint16_t)(*symbol);
525*f4ee7fbaSAndroid Build Coastguard Worker next_symbol[code_len] = (int)(*symbol);
526*f4ee7fbaSAndroid Build Coastguard Worker *prev_code_len = code_len;
527*f4ee7fbaSAndroid Build Coastguard Worker *space -= 32768U >> code_len;
528*f4ee7fbaSAndroid Build Coastguard Worker code_length_histo[code_len]++;
529*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n",
530*f4ee7fbaSAndroid Build Coastguard Worker (int)*symbol, (int)code_len));
531*f4ee7fbaSAndroid Build Coastguard Worker }
532*f4ee7fbaSAndroid Build Coastguard Worker (*symbol)++;
533*f4ee7fbaSAndroid Build Coastguard Worker }
534*f4ee7fbaSAndroid Build Coastguard Worker
535*f4ee7fbaSAndroid Build Coastguard Worker /* Process repeated symbol code length.
536*f4ee7fbaSAndroid Build Coastguard Worker A) Check if it is the extension of previous repeat sequence; if the decoded
537*f4ee7fbaSAndroid Build Coastguard Worker value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new
538*f4ee7fbaSAndroid Build Coastguard Worker symbol-skip
539*f4ee7fbaSAndroid Build Coastguard Worker B) Update repeat variable
540*f4ee7fbaSAndroid Build Coastguard Worker C) Check if operation is feasible (fits alphabet)
541*f4ee7fbaSAndroid Build Coastguard Worker D) For each symbol do the same operations as in ProcessSingleCodeLength
542*f4ee7fbaSAndroid Build Coastguard Worker
543*f4ee7fbaSAndroid Build Coastguard Worker PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or
544*f4ee7fbaSAndroid Build Coastguard Worker code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH */
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)545*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void ProcessRepeatedCodeLength(uint32_t code_len,
546*f4ee7fbaSAndroid Build Coastguard Worker uint32_t repeat_delta, uint32_t alphabet_size, uint32_t* symbol,
547*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* repeat, uint32_t* space, uint32_t* prev_code_len,
548*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* repeat_code_len, uint16_t* symbol_lists,
549*f4ee7fbaSAndroid Build Coastguard Worker uint16_t* code_length_histo, int* next_symbol) {
550*f4ee7fbaSAndroid Build Coastguard Worker uint32_t old_repeat;
551*f4ee7fbaSAndroid Build Coastguard Worker uint32_t extra_bits = 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */
552*f4ee7fbaSAndroid Build Coastguard Worker uint32_t new_len = 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */
553*f4ee7fbaSAndroid Build Coastguard Worker if (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
554*f4ee7fbaSAndroid Build Coastguard Worker new_len = *prev_code_len;
555*f4ee7fbaSAndroid Build Coastguard Worker extra_bits = 2;
556*f4ee7fbaSAndroid Build Coastguard Worker }
557*f4ee7fbaSAndroid Build Coastguard Worker if (*repeat_code_len != new_len) {
558*f4ee7fbaSAndroid Build Coastguard Worker *repeat = 0;
559*f4ee7fbaSAndroid Build Coastguard Worker *repeat_code_len = new_len;
560*f4ee7fbaSAndroid Build Coastguard Worker }
561*f4ee7fbaSAndroid Build Coastguard Worker old_repeat = *repeat;
562*f4ee7fbaSAndroid Build Coastguard Worker if (*repeat > 0) {
563*f4ee7fbaSAndroid Build Coastguard Worker *repeat -= 2;
564*f4ee7fbaSAndroid Build Coastguard Worker *repeat <<= extra_bits;
565*f4ee7fbaSAndroid Build Coastguard Worker }
566*f4ee7fbaSAndroid Build Coastguard Worker *repeat += repeat_delta + 3U;
567*f4ee7fbaSAndroid Build Coastguard Worker repeat_delta = *repeat - old_repeat;
568*f4ee7fbaSAndroid Build Coastguard Worker if (*symbol + repeat_delta > alphabet_size) {
569*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DUMP();
570*f4ee7fbaSAndroid Build Coastguard Worker *symbol = alphabet_size;
571*f4ee7fbaSAndroid Build Coastguard Worker *space = 0xFFFFF;
572*f4ee7fbaSAndroid Build Coastguard Worker return;
573*f4ee7fbaSAndroid Build Coastguard Worker }
574*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n",
575*f4ee7fbaSAndroid Build Coastguard Worker (int)*symbol, (int)(*symbol + repeat_delta - 1), (int)*repeat_code_len));
576*f4ee7fbaSAndroid Build Coastguard Worker if (*repeat_code_len != 0) {
577*f4ee7fbaSAndroid Build Coastguard Worker unsigned last = *symbol + repeat_delta;
578*f4ee7fbaSAndroid Build Coastguard Worker int next = next_symbol[*repeat_code_len];
579*f4ee7fbaSAndroid Build Coastguard Worker do {
580*f4ee7fbaSAndroid Build Coastguard Worker symbol_lists[next] = (uint16_t)*symbol;
581*f4ee7fbaSAndroid Build Coastguard Worker next = (int)*symbol;
582*f4ee7fbaSAndroid Build Coastguard Worker } while (++(*symbol) != last);
583*f4ee7fbaSAndroid Build Coastguard Worker next_symbol[*repeat_code_len] = next;
584*f4ee7fbaSAndroid Build Coastguard Worker *space -= repeat_delta << (15 - *repeat_code_len);
585*f4ee7fbaSAndroid Build Coastguard Worker code_length_histo[*repeat_code_len] =
586*f4ee7fbaSAndroid Build Coastguard Worker (uint16_t)(code_length_histo[*repeat_code_len] + repeat_delta);
587*f4ee7fbaSAndroid Build Coastguard Worker } else {
588*f4ee7fbaSAndroid Build Coastguard Worker *symbol += repeat_delta;
589*f4ee7fbaSAndroid Build Coastguard Worker }
590*f4ee7fbaSAndroid Build Coastguard Worker }
591*f4ee7fbaSAndroid Build Coastguard Worker
592*f4ee7fbaSAndroid Build Coastguard Worker /* Reads and decodes symbol codelengths. */
ReadSymbolCodeLengths(uint32_t alphabet_size,BrotliDecoderState * s)593*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode ReadSymbolCodeLengths(
594*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size, BrotliDecoderState* s) {
595*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
596*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
597*f4ee7fbaSAndroid Build Coastguard Worker uint32_t symbol = h->symbol;
598*f4ee7fbaSAndroid Build Coastguard Worker uint32_t repeat = h->repeat;
599*f4ee7fbaSAndroid Build Coastguard Worker uint32_t space = h->space;
600*f4ee7fbaSAndroid Build Coastguard Worker uint32_t prev_code_len = h->prev_code_len;
601*f4ee7fbaSAndroid Build Coastguard Worker uint32_t repeat_code_len = h->repeat_code_len;
602*f4ee7fbaSAndroid Build Coastguard Worker uint16_t* symbol_lists = h->symbol_lists;
603*f4ee7fbaSAndroid Build Coastguard Worker uint16_t* code_length_histo = h->code_length_histo;
604*f4ee7fbaSAndroid Build Coastguard Worker int* next_symbol = h->next_symbol;
605*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliWarmupBitReader(br)) {
606*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
607*f4ee7fbaSAndroid Build Coastguard Worker }
608*f4ee7fbaSAndroid Build Coastguard Worker while (symbol < alphabet_size && space > 0) {
609*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* p = h->table;
610*f4ee7fbaSAndroid Build Coastguard Worker uint32_t code_len;
611*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p);
612*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliCheckInputAmount(br, BROTLI_SHORT_FILL_BIT_WINDOW_READ)) {
613*f4ee7fbaSAndroid Build Coastguard Worker h->symbol = symbol;
614*f4ee7fbaSAndroid Build Coastguard Worker h->repeat = repeat;
615*f4ee7fbaSAndroid Build Coastguard Worker h->prev_code_len = prev_code_len;
616*f4ee7fbaSAndroid Build Coastguard Worker h->repeat_code_len = repeat_code_len;
617*f4ee7fbaSAndroid Build Coastguard Worker h->space = space;
618*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
619*f4ee7fbaSAndroid Build Coastguard Worker }
620*f4ee7fbaSAndroid Build Coastguard Worker BrotliFillBitWindow16(br);
621*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(p, BrotliGetBitsUnmasked(br) &
622*f4ee7fbaSAndroid Build Coastguard Worker BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH));
623*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p)); /* Use 1..5 bits. */
624*f4ee7fbaSAndroid Build Coastguard Worker code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */
625*f4ee7fbaSAndroid Build Coastguard Worker if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
626*f4ee7fbaSAndroid Build Coastguard Worker ProcessSingleCodeLength(code_len, &symbol, &repeat, &space,
627*f4ee7fbaSAndroid Build Coastguard Worker &prev_code_len, symbol_lists, code_length_histo, next_symbol);
628*f4ee7fbaSAndroid Build Coastguard Worker } else { /* code_len == 16..17, extra_bits == 2..3 */
629*f4ee7fbaSAndroid Build Coastguard Worker uint32_t extra_bits =
630*f4ee7fbaSAndroid Build Coastguard Worker (code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) ? 2 : 3;
631*f4ee7fbaSAndroid Build Coastguard Worker uint32_t repeat_delta =
632*f4ee7fbaSAndroid Build Coastguard Worker (uint32_t)BrotliGetBitsUnmasked(br) & BitMask(extra_bits);
633*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, extra_bits);
634*f4ee7fbaSAndroid Build Coastguard Worker ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,
635*f4ee7fbaSAndroid Build Coastguard Worker &symbol, &repeat, &space, &prev_code_len, &repeat_code_len,
636*f4ee7fbaSAndroid Build Coastguard Worker symbol_lists, code_length_histo, next_symbol);
637*f4ee7fbaSAndroid Build Coastguard Worker }
638*f4ee7fbaSAndroid Build Coastguard Worker }
639*f4ee7fbaSAndroid Build Coastguard Worker h->space = space;
640*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
641*f4ee7fbaSAndroid Build Coastguard Worker }
642*f4ee7fbaSAndroid Build Coastguard Worker
SafeReadSymbolCodeLengths(uint32_t alphabet_size,BrotliDecoderState * s)643*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode SafeReadSymbolCodeLengths(
644*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size, BrotliDecoderState* s) {
645*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
646*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
647*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL get_byte = BROTLI_FALSE;
648*f4ee7fbaSAndroid Build Coastguard Worker while (h->symbol < alphabet_size && h->space > 0) {
649*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* p = h->table;
650*f4ee7fbaSAndroid Build Coastguard Worker uint32_t code_len;
651*f4ee7fbaSAndroid Build Coastguard Worker uint32_t available_bits;
652*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits = 0;
653*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(p);
654*f4ee7fbaSAndroid Build Coastguard Worker if (get_byte && !BrotliPullByte(br)) return BROTLI_DECODER_NEEDS_MORE_INPUT;
655*f4ee7fbaSAndroid Build Coastguard Worker get_byte = BROTLI_FALSE;
656*f4ee7fbaSAndroid Build Coastguard Worker available_bits = BrotliGetAvailableBits(br);
657*f4ee7fbaSAndroid Build Coastguard Worker if (available_bits != 0) {
658*f4ee7fbaSAndroid Build Coastguard Worker bits = (uint32_t)BrotliGetBitsUnmasked(br);
659*f4ee7fbaSAndroid Build Coastguard Worker }
660*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_HC_ADJUST_TABLE_INDEX(p,
661*f4ee7fbaSAndroid Build Coastguard Worker bits & BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH));
662*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_HC_FAST_LOAD_BITS(p) > available_bits) {
663*f4ee7fbaSAndroid Build Coastguard Worker get_byte = BROTLI_TRUE;
664*f4ee7fbaSAndroid Build Coastguard Worker continue;
665*f4ee7fbaSAndroid Build Coastguard Worker }
666*f4ee7fbaSAndroid Build Coastguard Worker code_len = BROTLI_HC_FAST_LOAD_VALUE(p); /* code_len == 0..17 */
667*f4ee7fbaSAndroid Build Coastguard Worker if (code_len < BROTLI_REPEAT_PREVIOUS_CODE_LENGTH) {
668*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p));
669*f4ee7fbaSAndroid Build Coastguard Worker ProcessSingleCodeLength(code_len, &h->symbol, &h->repeat, &h->space,
670*f4ee7fbaSAndroid Build Coastguard Worker &h->prev_code_len, h->symbol_lists, h->code_length_histo,
671*f4ee7fbaSAndroid Build Coastguard Worker h->next_symbol);
672*f4ee7fbaSAndroid Build Coastguard Worker } else { /* code_len == 16..17, extra_bits == 2..3 */
673*f4ee7fbaSAndroid Build Coastguard Worker uint32_t extra_bits = code_len - 14U;
674*f4ee7fbaSAndroid Build Coastguard Worker uint32_t repeat_delta = (bits >> BROTLI_HC_FAST_LOAD_BITS(p)) &
675*f4ee7fbaSAndroid Build Coastguard Worker BitMask(extra_bits);
676*f4ee7fbaSAndroid Build Coastguard Worker if (available_bits < BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits) {
677*f4ee7fbaSAndroid Build Coastguard Worker get_byte = BROTLI_TRUE;
678*f4ee7fbaSAndroid Build Coastguard Worker continue;
679*f4ee7fbaSAndroid Build Coastguard Worker }
680*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, BROTLI_HC_FAST_LOAD_BITS(p) + extra_bits);
681*f4ee7fbaSAndroid Build Coastguard Worker ProcessRepeatedCodeLength(code_len, repeat_delta, alphabet_size,
682*f4ee7fbaSAndroid Build Coastguard Worker &h->symbol, &h->repeat, &h->space, &h->prev_code_len,
683*f4ee7fbaSAndroid Build Coastguard Worker &h->repeat_code_len, h->symbol_lists, h->code_length_histo,
684*f4ee7fbaSAndroid Build Coastguard Worker h->next_symbol);
685*f4ee7fbaSAndroid Build Coastguard Worker }
686*f4ee7fbaSAndroid Build Coastguard Worker }
687*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
688*f4ee7fbaSAndroid Build Coastguard Worker }
689*f4ee7fbaSAndroid Build Coastguard Worker
690*f4ee7fbaSAndroid Build Coastguard Worker /* Reads and decodes 15..18 codes using static prefix code.
691*f4ee7fbaSAndroid Build Coastguard Worker Each code is 2..4 bits long. In total 30..72 bits are used. */
ReadCodeLengthCodeLengths(BrotliDecoderState * s)692*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode ReadCodeLengthCodeLengths(BrotliDecoderState* s) {
693*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
694*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
695*f4ee7fbaSAndroid Build Coastguard Worker uint32_t num_codes = h->repeat;
696*f4ee7fbaSAndroid Build Coastguard Worker unsigned space = h->space;
697*f4ee7fbaSAndroid Build Coastguard Worker uint32_t i = h->sub_loop_counter;
698*f4ee7fbaSAndroid Build Coastguard Worker for (; i < BROTLI_CODE_LENGTH_CODES; ++i) {
699*f4ee7fbaSAndroid Build Coastguard Worker const uint8_t code_len_idx = kCodeLengthCodeOrder[i];
700*f4ee7fbaSAndroid Build Coastguard Worker uint32_t ix;
701*f4ee7fbaSAndroid Build Coastguard Worker uint32_t v;
702*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br, 4, &ix))) {
703*f4ee7fbaSAndroid Build Coastguard Worker uint32_t available_bits = BrotliGetAvailableBits(br);
704*f4ee7fbaSAndroid Build Coastguard Worker if (available_bits != 0) {
705*f4ee7fbaSAndroid Build Coastguard Worker ix = BrotliGetBitsUnmasked(br) & 0xF;
706*f4ee7fbaSAndroid Build Coastguard Worker } else {
707*f4ee7fbaSAndroid Build Coastguard Worker ix = 0;
708*f4ee7fbaSAndroid Build Coastguard Worker }
709*f4ee7fbaSAndroid Build Coastguard Worker if (kCodeLengthPrefixLength[ix] > available_bits) {
710*f4ee7fbaSAndroid Build Coastguard Worker h->sub_loop_counter = i;
711*f4ee7fbaSAndroid Build Coastguard Worker h->repeat = num_codes;
712*f4ee7fbaSAndroid Build Coastguard Worker h->space = space;
713*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;
714*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
715*f4ee7fbaSAndroid Build Coastguard Worker }
716*f4ee7fbaSAndroid Build Coastguard Worker }
717*f4ee7fbaSAndroid Build Coastguard Worker v = kCodeLengthPrefixValue[ix];
718*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, kCodeLengthPrefixLength[ix]);
719*f4ee7fbaSAndroid Build Coastguard Worker h->code_length_code_lengths[code_len_idx] = (uint8_t)v;
720*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_ARRAY_INDEX(h->code_length_code_lengths, code_len_idx);
721*f4ee7fbaSAndroid Build Coastguard Worker if (v != 0) {
722*f4ee7fbaSAndroid Build Coastguard Worker space = space - (32U >> v);
723*f4ee7fbaSAndroid Build Coastguard Worker ++num_codes;
724*f4ee7fbaSAndroid Build Coastguard Worker ++h->code_length_histo[v];
725*f4ee7fbaSAndroid Build Coastguard Worker if (space - 1U >= 32U) {
726*f4ee7fbaSAndroid Build Coastguard Worker /* space is 0 or wrapped around. */
727*f4ee7fbaSAndroid Build Coastguard Worker break;
728*f4ee7fbaSAndroid Build Coastguard Worker }
729*f4ee7fbaSAndroid Build Coastguard Worker }
730*f4ee7fbaSAndroid Build Coastguard Worker }
731*f4ee7fbaSAndroid Build Coastguard Worker if (!(num_codes == 1 || space == 0)) {
732*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE);
733*f4ee7fbaSAndroid Build Coastguard Worker }
734*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
735*f4ee7fbaSAndroid Build Coastguard Worker }
736*f4ee7fbaSAndroid Build Coastguard Worker
737*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes the Huffman tables.
738*f4ee7fbaSAndroid Build Coastguard Worker There are 2 scenarios:
739*f4ee7fbaSAndroid Build Coastguard Worker A) Huffman code contains only few symbols (1..4). Those symbols are read
740*f4ee7fbaSAndroid Build Coastguard Worker directly; their code lengths are defined by the number of symbols.
741*f4ee7fbaSAndroid Build Coastguard Worker For this scenario 4 - 49 bits will be read.
742*f4ee7fbaSAndroid Build Coastguard Worker
743*f4ee7fbaSAndroid Build Coastguard Worker B) 2-phase decoding:
744*f4ee7fbaSAndroid Build Coastguard Worker B.1) Small Huffman table is decoded; it is specified with code lengths
745*f4ee7fbaSAndroid Build Coastguard Worker encoded with predefined entropy code. 32 - 74 bits are used.
746*f4ee7fbaSAndroid Build Coastguard Worker B.2) Decoded table is used to decode code lengths of symbols in resulting
747*f4ee7fbaSAndroid Build Coastguard Worker Huffman table. In worst case 3520 bits are read. */
ReadHuffmanCode(uint32_t alphabet_size_max,uint32_t alphabet_size_limit,HuffmanCode * table,uint32_t * opt_table_size,BrotliDecoderState * s)748*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode ReadHuffmanCode(uint32_t alphabet_size_max,
749*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size_limit,
750*f4ee7fbaSAndroid Build Coastguard Worker HuffmanCode* table,
751*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* opt_table_size,
752*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
753*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
754*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
755*f4ee7fbaSAndroid Build Coastguard Worker /* State machine. */
756*f4ee7fbaSAndroid Build Coastguard Worker for (;;) {
757*f4ee7fbaSAndroid Build Coastguard Worker switch (h->substate_huffman) {
758*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_NONE:
759*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 2, &h->sub_loop_counter)) {
760*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
761*f4ee7fbaSAndroid Build Coastguard Worker }
762*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(h->sub_loop_counter);
763*f4ee7fbaSAndroid Build Coastguard Worker /* The value is used as follows:
764*f4ee7fbaSAndroid Build Coastguard Worker 1 for simple code;
765*f4ee7fbaSAndroid Build Coastguard Worker 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
766*f4ee7fbaSAndroid Build Coastguard Worker if (h->sub_loop_counter != 1) {
767*f4ee7fbaSAndroid Build Coastguard Worker h->space = 32;
768*f4ee7fbaSAndroid Build Coastguard Worker h->repeat = 0; /* num_codes */
769*f4ee7fbaSAndroid Build Coastguard Worker memset(&h->code_length_histo[0], 0, sizeof(h->code_length_histo[0]) *
770*f4ee7fbaSAndroid Build Coastguard Worker (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1));
771*f4ee7fbaSAndroid Build Coastguard Worker memset(&h->code_length_code_lengths[0], 0,
772*f4ee7fbaSAndroid Build Coastguard Worker sizeof(h->code_length_code_lengths));
773*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_COMPLEX;
774*f4ee7fbaSAndroid Build Coastguard Worker continue;
775*f4ee7fbaSAndroid Build Coastguard Worker }
776*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
777*f4ee7fbaSAndroid Build Coastguard Worker
778*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE:
779*f4ee7fbaSAndroid Build Coastguard Worker /* Read symbols, codes & code lengths directly. */
780*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 2, &h->symbol)) { /* num_symbols */
781*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_SIZE;
782*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
783*f4ee7fbaSAndroid Build Coastguard Worker }
784*f4ee7fbaSAndroid Build Coastguard Worker h->sub_loop_counter = 0;
785*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
786*f4ee7fbaSAndroid Build Coastguard Worker
787*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_SIMPLE_READ: {
788*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result =
789*f4ee7fbaSAndroid Build Coastguard Worker ReadSimpleHuffmanSymbols(alphabet_size_max, alphabet_size_limit, s);
790*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
791*f4ee7fbaSAndroid Build Coastguard Worker return result;
792*f4ee7fbaSAndroid Build Coastguard Worker }
793*f4ee7fbaSAndroid Build Coastguard Worker }
794*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
795*f4ee7fbaSAndroid Build Coastguard Worker
796*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD: {
797*f4ee7fbaSAndroid Build Coastguard Worker uint32_t table_size;
798*f4ee7fbaSAndroid Build Coastguard Worker if (h->symbol == 3) {
799*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
800*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 1, &bits)) {
801*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_SIMPLE_BUILD;
802*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
803*f4ee7fbaSAndroid Build Coastguard Worker }
804*f4ee7fbaSAndroid Build Coastguard Worker h->symbol += bits;
805*f4ee7fbaSAndroid Build Coastguard Worker }
806*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(h->symbol);
807*f4ee7fbaSAndroid Build Coastguard Worker table_size = BrotliBuildSimpleHuffmanTable(
808*f4ee7fbaSAndroid Build Coastguard Worker table, HUFFMAN_TABLE_BITS, h->symbols_lists_array, h->symbol);
809*f4ee7fbaSAndroid Build Coastguard Worker if (opt_table_size) {
810*f4ee7fbaSAndroid Build Coastguard Worker *opt_table_size = table_size;
811*f4ee7fbaSAndroid Build Coastguard Worker }
812*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
813*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
814*f4ee7fbaSAndroid Build Coastguard Worker }
815*f4ee7fbaSAndroid Build Coastguard Worker
816*f4ee7fbaSAndroid Build Coastguard Worker /* Decode Huffman-coded code lengths. */
817*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_COMPLEX: {
818*f4ee7fbaSAndroid Build Coastguard Worker uint32_t i;
819*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result = ReadCodeLengthCodeLengths(s);
820*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
821*f4ee7fbaSAndroid Build Coastguard Worker return result;
822*f4ee7fbaSAndroid Build Coastguard Worker }
823*f4ee7fbaSAndroid Build Coastguard Worker BrotliBuildCodeLengthsHuffmanTable(h->table,
824*f4ee7fbaSAndroid Build Coastguard Worker h->code_length_code_lengths,
825*f4ee7fbaSAndroid Build Coastguard Worker h->code_length_histo);
826*f4ee7fbaSAndroid Build Coastguard Worker memset(&h->code_length_histo[0], 0, sizeof(h->code_length_histo));
827*f4ee7fbaSAndroid Build Coastguard Worker for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) {
828*f4ee7fbaSAndroid Build Coastguard Worker h->next_symbol[i] = (int)i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
829*f4ee7fbaSAndroid Build Coastguard Worker h->symbol_lists[h->next_symbol[i]] = 0xFFFF;
830*f4ee7fbaSAndroid Build Coastguard Worker }
831*f4ee7fbaSAndroid Build Coastguard Worker
832*f4ee7fbaSAndroid Build Coastguard Worker h->symbol = 0;
833*f4ee7fbaSAndroid Build Coastguard Worker h->prev_code_len = BROTLI_INITIAL_REPEATED_CODE_LENGTH;
834*f4ee7fbaSAndroid Build Coastguard Worker h->repeat = 0;
835*f4ee7fbaSAndroid Build Coastguard Worker h->repeat_code_len = 0;
836*f4ee7fbaSAndroid Build Coastguard Worker h->space = 32768;
837*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS;
838*f4ee7fbaSAndroid Build Coastguard Worker }
839*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
840*f4ee7fbaSAndroid Build Coastguard Worker
841*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS: {
842*f4ee7fbaSAndroid Build Coastguard Worker uint32_t table_size;
843*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result = ReadSymbolCodeLengths(
844*f4ee7fbaSAndroid Build Coastguard Worker alphabet_size_limit, s);
845*f4ee7fbaSAndroid Build Coastguard Worker if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
846*f4ee7fbaSAndroid Build Coastguard Worker result = SafeReadSymbolCodeLengths(alphabet_size_limit, s);
847*f4ee7fbaSAndroid Build Coastguard Worker }
848*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
849*f4ee7fbaSAndroid Build Coastguard Worker return result;
850*f4ee7fbaSAndroid Build Coastguard Worker }
851*f4ee7fbaSAndroid Build Coastguard Worker
852*f4ee7fbaSAndroid Build Coastguard Worker if (h->space != 0) {
853*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)h->space));
854*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE);
855*f4ee7fbaSAndroid Build Coastguard Worker }
856*f4ee7fbaSAndroid Build Coastguard Worker table_size = BrotliBuildHuffmanTable(
857*f4ee7fbaSAndroid Build Coastguard Worker table, HUFFMAN_TABLE_BITS, h->symbol_lists, h->code_length_histo);
858*f4ee7fbaSAndroid Build Coastguard Worker if (opt_table_size) {
859*f4ee7fbaSAndroid Build Coastguard Worker *opt_table_size = table_size;
860*f4ee7fbaSAndroid Build Coastguard Worker }
861*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
862*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
863*f4ee7fbaSAndroid Build Coastguard Worker }
864*f4ee7fbaSAndroid Build Coastguard Worker
865*f4ee7fbaSAndroid Build Coastguard Worker default:
866*f4ee7fbaSAndroid Build Coastguard Worker return
867*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
868*f4ee7fbaSAndroid Build Coastguard Worker }
869*f4ee7fbaSAndroid Build Coastguard Worker }
870*f4ee7fbaSAndroid Build Coastguard Worker }
871*f4ee7fbaSAndroid Build Coastguard Worker
872*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes a block length by reading 3..39 bits. */
ReadBlockLength(const HuffmanCode * table,BrotliBitReader * br)873*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE uint32_t ReadBlockLength(const HuffmanCode* table,
874*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br) {
875*f4ee7fbaSAndroid Build Coastguard Worker uint32_t code;
876*f4ee7fbaSAndroid Build Coastguard Worker uint32_t nbits;
877*f4ee7fbaSAndroid Build Coastguard Worker code = ReadSymbol(table, br);
878*f4ee7fbaSAndroid Build Coastguard Worker nbits = _kBrotliPrefixCodeRanges[code].nbits; /* nbits == 2..24 */
879*f4ee7fbaSAndroid Build Coastguard Worker return _kBrotliPrefixCodeRanges[code].offset + BrotliReadBits24(br, nbits);
880*f4ee7fbaSAndroid Build Coastguard Worker }
881*f4ee7fbaSAndroid Build Coastguard Worker
882*f4ee7fbaSAndroid Build Coastguard Worker /* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then
883*f4ee7fbaSAndroid Build Coastguard Worker reading can't be continued with ReadBlockLength. */
SafeReadBlockLength(BrotliDecoderState * s,uint32_t * result,const HuffmanCode * table,BrotliBitReader * br)884*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL SafeReadBlockLength(
885*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, uint32_t* result, const HuffmanCode* table,
886*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br) {
887*f4ee7fbaSAndroid Build Coastguard Worker uint32_t index;
888*f4ee7fbaSAndroid Build Coastguard Worker if (s->substate_read_block_length == BROTLI_STATE_READ_BLOCK_LENGTH_NONE) {
889*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(table, br, &index)) {
890*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
891*f4ee7fbaSAndroid Build Coastguard Worker }
892*f4ee7fbaSAndroid Build Coastguard Worker } else {
893*f4ee7fbaSAndroid Build Coastguard Worker index = s->block_length_index;
894*f4ee7fbaSAndroid Build Coastguard Worker }
895*f4ee7fbaSAndroid Build Coastguard Worker {
896*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
897*f4ee7fbaSAndroid Build Coastguard Worker uint32_t nbits = _kBrotliPrefixCodeRanges[index].nbits;
898*f4ee7fbaSAndroid Build Coastguard Worker uint32_t offset = _kBrotliPrefixCodeRanges[index].offset;
899*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, nbits, &bits)) {
900*f4ee7fbaSAndroid Build Coastguard Worker s->block_length_index = index;
901*f4ee7fbaSAndroid Build Coastguard Worker s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX;
902*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
903*f4ee7fbaSAndroid Build Coastguard Worker }
904*f4ee7fbaSAndroid Build Coastguard Worker *result = offset + bits;
905*f4ee7fbaSAndroid Build Coastguard Worker s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
906*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
907*f4ee7fbaSAndroid Build Coastguard Worker }
908*f4ee7fbaSAndroid Build Coastguard Worker }
909*f4ee7fbaSAndroid Build Coastguard Worker
910*f4ee7fbaSAndroid Build Coastguard Worker /* Transform:
911*f4ee7fbaSAndroid Build Coastguard Worker 1) initialize list L with values 0, 1,... 255
912*f4ee7fbaSAndroid Build Coastguard Worker 2) For each input element X:
913*f4ee7fbaSAndroid Build Coastguard Worker 2.1) let Y = L[X]
914*f4ee7fbaSAndroid Build Coastguard Worker 2.2) remove X-th element from L
915*f4ee7fbaSAndroid Build Coastguard Worker 2.3) prepend Y to L
916*f4ee7fbaSAndroid Build Coastguard Worker 2.4) append Y to output
917*f4ee7fbaSAndroid Build Coastguard Worker
918*f4ee7fbaSAndroid Build Coastguard Worker In most cases max(Y) <= 7, so most of L remains intact.
919*f4ee7fbaSAndroid Build Coastguard Worker To reduce the cost of initialization, we reuse L, remember the upper bound
920*f4ee7fbaSAndroid Build Coastguard Worker of Y values, and reinitialize only first elements in L.
921*f4ee7fbaSAndroid Build Coastguard Worker
922*f4ee7fbaSAndroid Build Coastguard Worker Most of input values are 0 and 1. To reduce number of branches, we replace
923*f4ee7fbaSAndroid Build Coastguard Worker inner for loop with do-while. */
InverseMoveToFrontTransform(uint8_t * v,uint32_t v_len,BrotliDecoderState * state)924*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_NOINLINE void InverseMoveToFrontTransform(
925*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* v, uint32_t v_len, BrotliDecoderState* state) {
926*f4ee7fbaSAndroid Build Coastguard Worker /* Reinitialize elements that could have been changed. */
927*f4ee7fbaSAndroid Build Coastguard Worker uint32_t i = 1;
928*f4ee7fbaSAndroid Build Coastguard Worker uint32_t upper_bound = state->mtf_upper_bound;
929*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* mtf = &state->mtf[1]; /* Make mtf[-1] addressable. */
930*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* mtf_u8 = (uint8_t*)mtf;
931*f4ee7fbaSAndroid Build Coastguard Worker /* Load endian-aware constant. */
932*f4ee7fbaSAndroid Build Coastguard Worker const uint8_t b0123[4] = {0, 1, 2, 3};
933*f4ee7fbaSAndroid Build Coastguard Worker uint32_t pattern;
934*f4ee7fbaSAndroid Build Coastguard Worker memcpy(&pattern, &b0123, 4);
935*f4ee7fbaSAndroid Build Coastguard Worker
936*f4ee7fbaSAndroid Build Coastguard Worker /* Initialize list using 4 consequent values pattern. */
937*f4ee7fbaSAndroid Build Coastguard Worker mtf[0] = pattern;
938*f4ee7fbaSAndroid Build Coastguard Worker do {
939*f4ee7fbaSAndroid Build Coastguard Worker pattern += 0x04040404; /* Advance all 4 values by 4. */
940*f4ee7fbaSAndroid Build Coastguard Worker mtf[i] = pattern;
941*f4ee7fbaSAndroid Build Coastguard Worker i++;
942*f4ee7fbaSAndroid Build Coastguard Worker } while (i <= upper_bound);
943*f4ee7fbaSAndroid Build Coastguard Worker
944*f4ee7fbaSAndroid Build Coastguard Worker /* Transform the input. */
945*f4ee7fbaSAndroid Build Coastguard Worker upper_bound = 0;
946*f4ee7fbaSAndroid Build Coastguard Worker for (i = 0; i < v_len; ++i) {
947*f4ee7fbaSAndroid Build Coastguard Worker int index = v[i];
948*f4ee7fbaSAndroid Build Coastguard Worker uint8_t value = mtf_u8[index];
949*f4ee7fbaSAndroid Build Coastguard Worker upper_bound |= v[i];
950*f4ee7fbaSAndroid Build Coastguard Worker v[i] = value;
951*f4ee7fbaSAndroid Build Coastguard Worker mtf_u8[-1] = value;
952*f4ee7fbaSAndroid Build Coastguard Worker do {
953*f4ee7fbaSAndroid Build Coastguard Worker index--;
954*f4ee7fbaSAndroid Build Coastguard Worker mtf_u8[index + 1] = mtf_u8[index];
955*f4ee7fbaSAndroid Build Coastguard Worker } while (index >= 0);
956*f4ee7fbaSAndroid Build Coastguard Worker }
957*f4ee7fbaSAndroid Build Coastguard Worker /* Remember amount of elements to be reinitialized. */
958*f4ee7fbaSAndroid Build Coastguard Worker state->mtf_upper_bound = upper_bound >> 2;
959*f4ee7fbaSAndroid Build Coastguard Worker }
960*f4ee7fbaSAndroid Build Coastguard Worker
961*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes a series of Huffman table using ReadHuffmanCode function. */
HuffmanTreeGroupDecode(HuffmanTreeGroup * group,BrotliDecoderState * s)962*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode HuffmanTreeGroupDecode(
963*f4ee7fbaSAndroid Build Coastguard Worker HuffmanTreeGroup* group, BrotliDecoderState* s) {
964*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
965*f4ee7fbaSAndroid Build Coastguard Worker if (h->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {
966*f4ee7fbaSAndroid Build Coastguard Worker h->next = group->codes;
967*f4ee7fbaSAndroid Build Coastguard Worker h->htree_index = 0;
968*f4ee7fbaSAndroid Build Coastguard Worker h->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP;
969*f4ee7fbaSAndroid Build Coastguard Worker }
970*f4ee7fbaSAndroid Build Coastguard Worker while (h->htree_index < group->num_htrees) {
971*f4ee7fbaSAndroid Build Coastguard Worker uint32_t table_size;
972*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result = ReadHuffmanCode(group->alphabet_size_max,
973*f4ee7fbaSAndroid Build Coastguard Worker group->alphabet_size_limit, h->next, &table_size, s);
974*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) return result;
975*f4ee7fbaSAndroid Build Coastguard Worker group->htrees[h->htree_index] = h->next;
976*f4ee7fbaSAndroid Build Coastguard Worker h->next += table_size;
977*f4ee7fbaSAndroid Build Coastguard Worker ++h->htree_index;
978*f4ee7fbaSAndroid Build Coastguard Worker }
979*f4ee7fbaSAndroid Build Coastguard Worker h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;
980*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
981*f4ee7fbaSAndroid Build Coastguard Worker }
982*f4ee7fbaSAndroid Build Coastguard Worker
983*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes a context map.
984*f4ee7fbaSAndroid Build Coastguard Worker Decoding is done in 4 phases:
985*f4ee7fbaSAndroid Build Coastguard Worker 1) Read auxiliary information (6..16 bits) and allocate memory.
986*f4ee7fbaSAndroid Build Coastguard Worker In case of trivial context map, decoding is finished at this phase.
987*f4ee7fbaSAndroid Build Coastguard Worker 2) Decode Huffman table using ReadHuffmanCode function.
988*f4ee7fbaSAndroid Build Coastguard Worker This table will be used for reading context map items.
989*f4ee7fbaSAndroid Build Coastguard Worker 3) Read context map items; "0" values could be run-length encoded.
990*f4ee7fbaSAndroid Build Coastguard Worker 4) Optionally, apply InverseMoveToFront transform to the resulting map. */
DecodeContextMap(uint32_t context_map_size,uint32_t * num_htrees,uint8_t ** context_map_arg,BrotliDecoderState * s)991*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size,
992*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* num_htrees,
993*f4ee7fbaSAndroid Build Coastguard Worker uint8_t** context_map_arg,
994*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
995*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
996*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
997*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
998*f4ee7fbaSAndroid Build Coastguard Worker
999*f4ee7fbaSAndroid Build Coastguard Worker switch ((int)h->substate_context_map) {
1000*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_NONE:
1001*f4ee7fbaSAndroid Build Coastguard Worker result = DecodeVarLenUint8(s, br, num_htrees);
1002*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
1003*f4ee7fbaSAndroid Build Coastguard Worker return result;
1004*f4ee7fbaSAndroid Build Coastguard Worker }
1005*f4ee7fbaSAndroid Build Coastguard Worker (*num_htrees)++;
1006*f4ee7fbaSAndroid Build Coastguard Worker h->context_index = 0;
1007*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(context_map_size);
1008*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(*num_htrees);
1009*f4ee7fbaSAndroid Build Coastguard Worker *context_map_arg =
1010*f4ee7fbaSAndroid Build Coastguard Worker (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)context_map_size);
1011*f4ee7fbaSAndroid Build Coastguard Worker if (*context_map_arg == 0) {
1012*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP);
1013*f4ee7fbaSAndroid Build Coastguard Worker }
1014*f4ee7fbaSAndroid Build Coastguard Worker if (*num_htrees <= 1) {
1015*f4ee7fbaSAndroid Build Coastguard Worker memset(*context_map_arg, 0, (size_t)context_map_size);
1016*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
1017*f4ee7fbaSAndroid Build Coastguard Worker }
1018*f4ee7fbaSAndroid Build Coastguard Worker h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX;
1019*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
1020*f4ee7fbaSAndroid Build Coastguard Worker
1021*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: {
1022*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
1023*f4ee7fbaSAndroid Build Coastguard Worker /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe
1024*f4ee7fbaSAndroid Build Coastguard Worker to peek 4 bits ahead. */
1025*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeGetBits(br, 5, &bits)) {
1026*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
1027*f4ee7fbaSAndroid Build Coastguard Worker }
1028*f4ee7fbaSAndroid Build Coastguard Worker if ((bits & 1) != 0) { /* Use RLE for zeros. */
1029*f4ee7fbaSAndroid Build Coastguard Worker h->max_run_length_prefix = (bits >> 1) + 1;
1030*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, 5);
1031*f4ee7fbaSAndroid Build Coastguard Worker } else {
1032*f4ee7fbaSAndroid Build Coastguard Worker h->max_run_length_prefix = 0;
1033*f4ee7fbaSAndroid Build Coastguard Worker BrotliDropBits(br, 1);
1034*f4ee7fbaSAndroid Build Coastguard Worker }
1035*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(h->max_run_length_prefix);
1036*f4ee7fbaSAndroid Build Coastguard Worker h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN;
1037*f4ee7fbaSAndroid Build Coastguard Worker }
1038*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
1039*f4ee7fbaSAndroid Build Coastguard Worker
1040*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_HUFFMAN: {
1041*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size = *num_htrees + h->max_run_length_prefix;
1042*f4ee7fbaSAndroid Build Coastguard Worker result = ReadHuffmanCode(alphabet_size, alphabet_size,
1043*f4ee7fbaSAndroid Build Coastguard Worker h->context_map_table, NULL, s);
1044*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) return result;
1045*f4ee7fbaSAndroid Build Coastguard Worker h->code = 0xFFFF;
1046*f4ee7fbaSAndroid Build Coastguard Worker h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE;
1047*f4ee7fbaSAndroid Build Coastguard Worker }
1048*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
1049*f4ee7fbaSAndroid Build Coastguard Worker
1050*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_DECODE: {
1051*f4ee7fbaSAndroid Build Coastguard Worker uint32_t context_index = h->context_index;
1052*f4ee7fbaSAndroid Build Coastguard Worker uint32_t max_run_length_prefix = h->max_run_length_prefix;
1053*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* context_map = *context_map_arg;
1054*f4ee7fbaSAndroid Build Coastguard Worker uint32_t code = h->code;
1055*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL skip_preamble = (code != 0xFFFF);
1056*f4ee7fbaSAndroid Build Coastguard Worker while (context_index < context_map_size || skip_preamble) {
1057*f4ee7fbaSAndroid Build Coastguard Worker if (!skip_preamble) {
1058*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(h->context_map_table, br, &code)) {
1059*f4ee7fbaSAndroid Build Coastguard Worker h->code = 0xFFFF;
1060*f4ee7fbaSAndroid Build Coastguard Worker h->context_index = context_index;
1061*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
1062*f4ee7fbaSAndroid Build Coastguard Worker }
1063*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(code);
1064*f4ee7fbaSAndroid Build Coastguard Worker
1065*f4ee7fbaSAndroid Build Coastguard Worker if (code == 0) {
1066*f4ee7fbaSAndroid Build Coastguard Worker context_map[context_index++] = 0;
1067*f4ee7fbaSAndroid Build Coastguard Worker continue;
1068*f4ee7fbaSAndroid Build Coastguard Worker }
1069*f4ee7fbaSAndroid Build Coastguard Worker if (code > max_run_length_prefix) {
1070*f4ee7fbaSAndroid Build Coastguard Worker context_map[context_index++] =
1071*f4ee7fbaSAndroid Build Coastguard Worker (uint8_t)(code - max_run_length_prefix);
1072*f4ee7fbaSAndroid Build Coastguard Worker continue;
1073*f4ee7fbaSAndroid Build Coastguard Worker }
1074*f4ee7fbaSAndroid Build Coastguard Worker } else {
1075*f4ee7fbaSAndroid Build Coastguard Worker skip_preamble = BROTLI_FALSE;
1076*f4ee7fbaSAndroid Build Coastguard Worker }
1077*f4ee7fbaSAndroid Build Coastguard Worker /* RLE sub-stage. */
1078*f4ee7fbaSAndroid Build Coastguard Worker {
1079*f4ee7fbaSAndroid Build Coastguard Worker uint32_t reps;
1080*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, code, &reps)) {
1081*f4ee7fbaSAndroid Build Coastguard Worker h->code = code;
1082*f4ee7fbaSAndroid Build Coastguard Worker h->context_index = context_index;
1083*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
1084*f4ee7fbaSAndroid Build Coastguard Worker }
1085*f4ee7fbaSAndroid Build Coastguard Worker reps += 1U << code;
1086*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(reps);
1087*f4ee7fbaSAndroid Build Coastguard Worker if (context_index + reps > context_map_size) {
1088*f4ee7fbaSAndroid Build Coastguard Worker return
1089*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT);
1090*f4ee7fbaSAndroid Build Coastguard Worker }
1091*f4ee7fbaSAndroid Build Coastguard Worker do {
1092*f4ee7fbaSAndroid Build Coastguard Worker context_map[context_index++] = 0;
1093*f4ee7fbaSAndroid Build Coastguard Worker } while (--reps);
1094*f4ee7fbaSAndroid Build Coastguard Worker }
1095*f4ee7fbaSAndroid Build Coastguard Worker }
1096*f4ee7fbaSAndroid Build Coastguard Worker }
1097*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
1098*f4ee7fbaSAndroid Build Coastguard Worker
1099*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: {
1100*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
1101*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 1, &bits)) {
1102*f4ee7fbaSAndroid Build Coastguard Worker h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM;
1103*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
1104*f4ee7fbaSAndroid Build Coastguard Worker }
1105*f4ee7fbaSAndroid Build Coastguard Worker if (bits != 0) {
1106*f4ee7fbaSAndroid Build Coastguard Worker InverseMoveToFrontTransform(*context_map_arg, context_map_size, s);
1107*f4ee7fbaSAndroid Build Coastguard Worker }
1108*f4ee7fbaSAndroid Build Coastguard Worker h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;
1109*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
1110*f4ee7fbaSAndroid Build Coastguard Worker }
1111*f4ee7fbaSAndroid Build Coastguard Worker
1112*f4ee7fbaSAndroid Build Coastguard Worker default:
1113*f4ee7fbaSAndroid Build Coastguard Worker return
1114*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
1115*f4ee7fbaSAndroid Build Coastguard Worker }
1116*f4ee7fbaSAndroid Build Coastguard Worker }
1117*f4ee7fbaSAndroid Build Coastguard Worker
1118*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes a command or literal and updates block type ring-buffer.
1119*f4ee7fbaSAndroid Build Coastguard Worker Reads 3..54 bits. */
DecodeBlockTypeAndLength(int safe,BrotliDecoderState * s,int tree_type)1120*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength(
1121*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s, int tree_type) {
1122*f4ee7fbaSAndroid Build Coastguard Worker uint32_t max_block_type = s->num_block_types[tree_type];
1123*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* type_tree = &s->block_type_trees[
1124*f4ee7fbaSAndroid Build Coastguard Worker tree_type * BROTLI_HUFFMAN_MAX_SIZE_258];
1125*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* len_tree = &s->block_len_trees[
1126*f4ee7fbaSAndroid Build Coastguard Worker tree_type * BROTLI_HUFFMAN_MAX_SIZE_26];
1127*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
1128*f4ee7fbaSAndroid Build Coastguard Worker uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2];
1129*f4ee7fbaSAndroid Build Coastguard Worker uint32_t block_type;
1130*f4ee7fbaSAndroid Build Coastguard Worker if (max_block_type <= 1) {
1131*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1132*f4ee7fbaSAndroid Build Coastguard Worker }
1133*f4ee7fbaSAndroid Build Coastguard Worker
1134*f4ee7fbaSAndroid Build Coastguard Worker /* Read 0..15 + 3..39 bits. */
1135*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1136*f4ee7fbaSAndroid Build Coastguard Worker block_type = ReadSymbol(type_tree, br);
1137*f4ee7fbaSAndroid Build Coastguard Worker s->block_length[tree_type] = ReadBlockLength(len_tree, br);
1138*f4ee7fbaSAndroid Build Coastguard Worker } else {
1139*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderState memento;
1140*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderSaveState(br, &memento);
1141*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(type_tree, br, &block_type)) return BROTLI_FALSE;
1142*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) {
1143*f4ee7fbaSAndroid Build Coastguard Worker s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;
1144*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderRestoreState(br, &memento);
1145*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1146*f4ee7fbaSAndroid Build Coastguard Worker }
1147*f4ee7fbaSAndroid Build Coastguard Worker }
1148*f4ee7fbaSAndroid Build Coastguard Worker
1149*f4ee7fbaSAndroid Build Coastguard Worker if (block_type == 1) {
1150*f4ee7fbaSAndroid Build Coastguard Worker block_type = ringbuffer[1] + 1;
1151*f4ee7fbaSAndroid Build Coastguard Worker } else if (block_type == 0) {
1152*f4ee7fbaSAndroid Build Coastguard Worker block_type = ringbuffer[0];
1153*f4ee7fbaSAndroid Build Coastguard Worker } else {
1154*f4ee7fbaSAndroid Build Coastguard Worker block_type -= 2;
1155*f4ee7fbaSAndroid Build Coastguard Worker }
1156*f4ee7fbaSAndroid Build Coastguard Worker if (block_type >= max_block_type) {
1157*f4ee7fbaSAndroid Build Coastguard Worker block_type -= max_block_type;
1158*f4ee7fbaSAndroid Build Coastguard Worker }
1159*f4ee7fbaSAndroid Build Coastguard Worker ringbuffer[0] = ringbuffer[1];
1160*f4ee7fbaSAndroid Build Coastguard Worker ringbuffer[1] = block_type;
1161*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1162*f4ee7fbaSAndroid Build Coastguard Worker }
1163*f4ee7fbaSAndroid Build Coastguard Worker
DetectTrivialLiteralBlockTypes(BrotliDecoderState * s)1164*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(
1165*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1166*f4ee7fbaSAndroid Build Coastguard Worker size_t i;
1167*f4ee7fbaSAndroid Build Coastguard Worker for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0;
1168*f4ee7fbaSAndroid Build Coastguard Worker for (i = 0; i < s->num_block_types[0]; i++) {
1169*f4ee7fbaSAndroid Build Coastguard Worker size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS;
1170*f4ee7fbaSAndroid Build Coastguard Worker size_t error = 0;
1171*f4ee7fbaSAndroid Build Coastguard Worker size_t sample = s->context_map[offset];
1172*f4ee7fbaSAndroid Build Coastguard Worker size_t j;
1173*f4ee7fbaSAndroid Build Coastguard Worker for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) {
1174*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;)
1175*f4ee7fbaSAndroid Build Coastguard Worker }
1176*f4ee7fbaSAndroid Build Coastguard Worker if (error == 0) {
1177*f4ee7fbaSAndroid Build Coastguard Worker s->trivial_literal_contexts[i >> 5] |= 1u << (i & 31);
1178*f4ee7fbaSAndroid Build Coastguard Worker }
1179*f4ee7fbaSAndroid Build Coastguard Worker }
1180*f4ee7fbaSAndroid Build Coastguard Worker }
1181*f4ee7fbaSAndroid Build Coastguard Worker
PrepareLiteralDecoding(BrotliDecoderState * s)1182*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) {
1183*f4ee7fbaSAndroid Build Coastguard Worker uint8_t context_mode;
1184*f4ee7fbaSAndroid Build Coastguard Worker size_t trivial;
1185*f4ee7fbaSAndroid Build Coastguard Worker uint32_t block_type = s->block_type_rb[1];
1186*f4ee7fbaSAndroid Build Coastguard Worker uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS;
1187*f4ee7fbaSAndroid Build Coastguard Worker s->context_map_slice = s->context_map + context_offset;
1188*f4ee7fbaSAndroid Build Coastguard Worker trivial = s->trivial_literal_contexts[block_type >> 5];
1189*f4ee7fbaSAndroid Build Coastguard Worker s->trivial_literal_context = (trivial >> (block_type & 31)) & 1;
1190*f4ee7fbaSAndroid Build Coastguard Worker s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]];
1191*f4ee7fbaSAndroid Build Coastguard Worker context_mode = s->context_modes[block_type] & 3;
1192*f4ee7fbaSAndroid Build Coastguard Worker s->context_lookup = BROTLI_CONTEXT_LUT(context_mode);
1193*f4ee7fbaSAndroid Build Coastguard Worker }
1194*f4ee7fbaSAndroid Build Coastguard Worker
1195*f4ee7fbaSAndroid Build Coastguard Worker /* Decodes the block type and updates the state for literal context.
1196*f4ee7fbaSAndroid Build Coastguard Worker Reads 3..54 bits. */
DecodeLiteralBlockSwitchInternal(int safe,BrotliDecoderState * s)1197*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal(
1198*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s) {
1199*f4ee7fbaSAndroid Build Coastguard Worker if (!DecodeBlockTypeAndLength(safe, s, 0)) {
1200*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1201*f4ee7fbaSAndroid Build Coastguard Worker }
1202*f4ee7fbaSAndroid Build Coastguard Worker PrepareLiteralDecoding(s);
1203*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1204*f4ee7fbaSAndroid Build Coastguard Worker }
1205*f4ee7fbaSAndroid Build Coastguard Worker
DecodeLiteralBlockSwitch(BrotliDecoderState * s)1206*f4ee7fbaSAndroid Build Coastguard Worker static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) {
1207*f4ee7fbaSAndroid Build Coastguard Worker DecodeLiteralBlockSwitchInternal(0, s);
1208*f4ee7fbaSAndroid Build Coastguard Worker }
1209*f4ee7fbaSAndroid Build Coastguard Worker
SafeDecodeLiteralBlockSwitch(BrotliDecoderState * s)1210*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(
1211*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1212*f4ee7fbaSAndroid Build Coastguard Worker return DecodeLiteralBlockSwitchInternal(1, s);
1213*f4ee7fbaSAndroid Build Coastguard Worker }
1214*f4ee7fbaSAndroid Build Coastguard Worker
1215*f4ee7fbaSAndroid Build Coastguard Worker /* Block switch for insert/copy length.
1216*f4ee7fbaSAndroid Build Coastguard Worker Reads 3..54 bits. */
DecodeCommandBlockSwitchInternal(int safe,BrotliDecoderState * s)1217*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal(
1218*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s) {
1219*f4ee7fbaSAndroid Build Coastguard Worker if (!DecodeBlockTypeAndLength(safe, s, 1)) {
1220*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1221*f4ee7fbaSAndroid Build Coastguard Worker }
1222*f4ee7fbaSAndroid Build Coastguard Worker s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]];
1223*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1224*f4ee7fbaSAndroid Build Coastguard Worker }
1225*f4ee7fbaSAndroid Build Coastguard Worker
DecodeCommandBlockSwitch(BrotliDecoderState * s)1226*f4ee7fbaSAndroid Build Coastguard Worker static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) {
1227*f4ee7fbaSAndroid Build Coastguard Worker DecodeCommandBlockSwitchInternal(0, s);
1228*f4ee7fbaSAndroid Build Coastguard Worker }
1229*f4ee7fbaSAndroid Build Coastguard Worker
SafeDecodeCommandBlockSwitch(BrotliDecoderState * s)1230*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(
1231*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1232*f4ee7fbaSAndroid Build Coastguard Worker return DecodeCommandBlockSwitchInternal(1, s);
1233*f4ee7fbaSAndroid Build Coastguard Worker }
1234*f4ee7fbaSAndroid Build Coastguard Worker
1235*f4ee7fbaSAndroid Build Coastguard Worker /* Block switch for distance codes.
1236*f4ee7fbaSAndroid Build Coastguard Worker Reads 3..54 bits. */
DecodeDistanceBlockSwitchInternal(int safe,BrotliDecoderState * s)1237*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal(
1238*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s) {
1239*f4ee7fbaSAndroid Build Coastguard Worker if (!DecodeBlockTypeAndLength(safe, s, 2)) {
1240*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1241*f4ee7fbaSAndroid Build Coastguard Worker }
1242*f4ee7fbaSAndroid Build Coastguard Worker s->dist_context_map_slice = s->dist_context_map +
1243*f4ee7fbaSAndroid Build Coastguard Worker (s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS);
1244*f4ee7fbaSAndroid Build Coastguard Worker s->dist_htree_index = s->dist_context_map_slice[s->distance_context];
1245*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1246*f4ee7fbaSAndroid Build Coastguard Worker }
1247*f4ee7fbaSAndroid Build Coastguard Worker
DecodeDistanceBlockSwitch(BrotliDecoderState * s)1248*f4ee7fbaSAndroid Build Coastguard Worker static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) {
1249*f4ee7fbaSAndroid Build Coastguard Worker DecodeDistanceBlockSwitchInternal(0, s);
1250*f4ee7fbaSAndroid Build Coastguard Worker }
1251*f4ee7fbaSAndroid Build Coastguard Worker
SafeDecodeDistanceBlockSwitch(BrotliDecoderState * s)1252*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(
1253*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1254*f4ee7fbaSAndroid Build Coastguard Worker return DecodeDistanceBlockSwitchInternal(1, s);
1255*f4ee7fbaSAndroid Build Coastguard Worker }
1256*f4ee7fbaSAndroid Build Coastguard Worker
UnwrittenBytes(const BrotliDecoderState * s,BROTLI_BOOL wrap)1257*f4ee7fbaSAndroid Build Coastguard Worker static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) {
1258*f4ee7fbaSAndroid Build Coastguard Worker size_t pos = wrap && s->pos > s->ringbuffer_size ?
1259*f4ee7fbaSAndroid Build Coastguard Worker (size_t)s->ringbuffer_size : (size_t)(s->pos);
1260*f4ee7fbaSAndroid Build Coastguard Worker size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos;
1261*f4ee7fbaSAndroid Build Coastguard Worker return partial_pos_rb - s->partial_pos_out;
1262*f4ee7fbaSAndroid Build Coastguard Worker }
1263*f4ee7fbaSAndroid Build Coastguard Worker
1264*f4ee7fbaSAndroid Build Coastguard Worker /* Dumps output.
1265*f4ee7fbaSAndroid Build Coastguard Worker Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push
1266*f4ee7fbaSAndroid Build Coastguard Worker and either ring-buffer is as big as window size, or |force| is true. */
WriteRingBuffer(BrotliDecoderState * s,size_t * available_out,uint8_t ** next_out,size_t * total_out,BROTLI_BOOL force)1267*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer(
1268*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, size_t* available_out, uint8_t** next_out,
1269*f4ee7fbaSAndroid Build Coastguard Worker size_t* total_out, BROTLI_BOOL force) {
1270*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* start =
1271*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask);
1272*f4ee7fbaSAndroid Build Coastguard Worker size_t to_write = UnwrittenBytes(s, BROTLI_TRUE);
1273*f4ee7fbaSAndroid Build Coastguard Worker size_t num_written = *available_out;
1274*f4ee7fbaSAndroid Build Coastguard Worker if (num_written > to_write) {
1275*f4ee7fbaSAndroid Build Coastguard Worker num_written = to_write;
1276*f4ee7fbaSAndroid Build Coastguard Worker }
1277*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len < 0) {
1278*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1);
1279*f4ee7fbaSAndroid Build Coastguard Worker }
1280*f4ee7fbaSAndroid Build Coastguard Worker if (next_out && !*next_out) {
1281*f4ee7fbaSAndroid Build Coastguard Worker *next_out = start;
1282*f4ee7fbaSAndroid Build Coastguard Worker } else {
1283*f4ee7fbaSAndroid Build Coastguard Worker if (next_out) {
1284*f4ee7fbaSAndroid Build Coastguard Worker memcpy(*next_out, start, num_written);
1285*f4ee7fbaSAndroid Build Coastguard Worker *next_out += num_written;
1286*f4ee7fbaSAndroid Build Coastguard Worker }
1287*f4ee7fbaSAndroid Build Coastguard Worker }
1288*f4ee7fbaSAndroid Build Coastguard Worker *available_out -= num_written;
1289*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(to_write);
1290*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(num_written);
1291*f4ee7fbaSAndroid Build Coastguard Worker s->partial_pos_out += num_written;
1292*f4ee7fbaSAndroid Build Coastguard Worker if (total_out) {
1293*f4ee7fbaSAndroid Build Coastguard Worker *total_out = s->partial_pos_out;
1294*f4ee7fbaSAndroid Build Coastguard Worker }
1295*f4ee7fbaSAndroid Build Coastguard Worker if (num_written < to_write) {
1296*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer_size == (1 << s->window_bits) || force) {
1297*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_OUTPUT;
1298*f4ee7fbaSAndroid Build Coastguard Worker } else {
1299*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
1300*f4ee7fbaSAndroid Build Coastguard Worker }
1301*f4ee7fbaSAndroid Build Coastguard Worker }
1302*f4ee7fbaSAndroid Build Coastguard Worker /* Wrap ring buffer only if it has reached its maximal size. */
1303*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer_size == (1 << s->window_bits) &&
1304*f4ee7fbaSAndroid Build Coastguard Worker s->pos >= s->ringbuffer_size) {
1305*f4ee7fbaSAndroid Build Coastguard Worker s->pos -= s->ringbuffer_size;
1306*f4ee7fbaSAndroid Build Coastguard Worker s->rb_roundtrips++;
1307*f4ee7fbaSAndroid Build Coastguard Worker s->should_wrap_ringbuffer = (size_t)s->pos != 0 ? 1 : 0;
1308*f4ee7fbaSAndroid Build Coastguard Worker }
1309*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
1310*f4ee7fbaSAndroid Build Coastguard Worker }
1311*f4ee7fbaSAndroid Build Coastguard Worker
WrapRingBuffer(BrotliDecoderState * s)1312*f4ee7fbaSAndroid Build Coastguard Worker static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) {
1313*f4ee7fbaSAndroid Build Coastguard Worker if (s->should_wrap_ringbuffer) {
1314*f4ee7fbaSAndroid Build Coastguard Worker memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);
1315*f4ee7fbaSAndroid Build Coastguard Worker s->should_wrap_ringbuffer = 0;
1316*f4ee7fbaSAndroid Build Coastguard Worker }
1317*f4ee7fbaSAndroid Build Coastguard Worker }
1318*f4ee7fbaSAndroid Build Coastguard Worker
1319*f4ee7fbaSAndroid Build Coastguard Worker /* Allocates ring-buffer.
1320*f4ee7fbaSAndroid Build Coastguard Worker
1321*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
1322*f4ee7fbaSAndroid Build Coastguard Worker this function is called.
1323*f4ee7fbaSAndroid Build Coastguard Worker
1324*f4ee7fbaSAndroid Build Coastguard Worker Last two bytes of ring-buffer are initialized to 0, so context calculation
1325*f4ee7fbaSAndroid Build Coastguard Worker could be done uniformly for the first two and all other positions. */
BrotliEnsureRingBuffer(BrotliDecoderState * s)1326*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer(
1327*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1328*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* old_ringbuffer = s->ringbuffer;
1329*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer_size == s->new_ringbuffer_size) {
1330*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1331*f4ee7fbaSAndroid Build Coastguard Worker }
1332*f4ee7fbaSAndroid Build Coastguard Worker
1333*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer = (uint8_t*)BROTLI_DECODER_ALLOC(s,
1334*f4ee7fbaSAndroid Build Coastguard Worker (size_t)(s->new_ringbuffer_size) + kRingBufferWriteAheadSlack);
1335*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer == 0) {
1336*f4ee7fbaSAndroid Build Coastguard Worker /* Restore previous value. */
1337*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer = old_ringbuffer;
1338*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1339*f4ee7fbaSAndroid Build Coastguard Worker }
1340*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[s->new_ringbuffer_size - 2] = 0;
1341*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[s->new_ringbuffer_size - 1] = 0;
1342*f4ee7fbaSAndroid Build Coastguard Worker
1343*f4ee7fbaSAndroid Build Coastguard Worker if (!!old_ringbuffer) {
1344*f4ee7fbaSAndroid Build Coastguard Worker memcpy(s->ringbuffer, old_ringbuffer, (size_t)s->pos);
1345*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DECODER_FREE(s, old_ringbuffer);
1346*f4ee7fbaSAndroid Build Coastguard Worker }
1347*f4ee7fbaSAndroid Build Coastguard Worker
1348*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer_size = s->new_ringbuffer_size;
1349*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer_mask = s->new_ringbuffer_size - 1;
1350*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
1351*f4ee7fbaSAndroid Build Coastguard Worker
1352*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1353*f4ee7fbaSAndroid Build Coastguard Worker }
1354*f4ee7fbaSAndroid Build Coastguard Worker
CopyUncompressedBlockToOutput(size_t * available_out,uint8_t ** next_out,size_t * total_out,BrotliDecoderState * s)1355*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(
1356*f4ee7fbaSAndroid Build Coastguard Worker size_t* available_out, uint8_t** next_out, size_t* total_out,
1357*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1358*f4ee7fbaSAndroid Build Coastguard Worker /* TODO: avoid allocation for single uncompressed block. */
1359*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliEnsureRingBuffer(s)) {
1360*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1);
1361*f4ee7fbaSAndroid Build Coastguard Worker }
1362*f4ee7fbaSAndroid Build Coastguard Worker
1363*f4ee7fbaSAndroid Build Coastguard Worker /* State machine */
1364*f4ee7fbaSAndroid Build Coastguard Worker for (;;) {
1365*f4ee7fbaSAndroid Build Coastguard Worker switch (s->substate_uncompressed) {
1366*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_UNCOMPRESSED_NONE: {
1367*f4ee7fbaSAndroid Build Coastguard Worker int nbytes = (int)BrotliGetRemainingBytes(&s->br);
1368*f4ee7fbaSAndroid Build Coastguard Worker if (nbytes > s->meta_block_remaining_len) {
1369*f4ee7fbaSAndroid Build Coastguard Worker nbytes = s->meta_block_remaining_len;
1370*f4ee7fbaSAndroid Build Coastguard Worker }
1371*f4ee7fbaSAndroid Build Coastguard Worker if (s->pos + nbytes > s->ringbuffer_size) {
1372*f4ee7fbaSAndroid Build Coastguard Worker nbytes = s->ringbuffer_size - s->pos;
1373*f4ee7fbaSAndroid Build Coastguard Worker }
1374*f4ee7fbaSAndroid Build Coastguard Worker /* Copy remaining bytes from s->br.buf_ to ring-buffer. */
1375*f4ee7fbaSAndroid Build Coastguard Worker BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes);
1376*f4ee7fbaSAndroid Build Coastguard Worker s->pos += nbytes;
1377*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len -= nbytes;
1378*f4ee7fbaSAndroid Build Coastguard Worker if (s->pos < 1 << s->window_bits) {
1379*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len == 0) {
1380*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
1381*f4ee7fbaSAndroid Build Coastguard Worker }
1382*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
1383*f4ee7fbaSAndroid Build Coastguard Worker }
1384*f4ee7fbaSAndroid Build Coastguard Worker s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE;
1385*f4ee7fbaSAndroid Build Coastguard Worker }
1386*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
1387*f4ee7fbaSAndroid Build Coastguard Worker
1388*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_UNCOMPRESSED_WRITE: {
1389*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result;
1390*f4ee7fbaSAndroid Build Coastguard Worker result = WriteRingBuffer(
1391*f4ee7fbaSAndroid Build Coastguard Worker s, available_out, next_out, total_out, BROTLI_FALSE);
1392*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
1393*f4ee7fbaSAndroid Build Coastguard Worker return result;
1394*f4ee7fbaSAndroid Build Coastguard Worker }
1395*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer_size == 1 << s->window_bits) {
1396*f4ee7fbaSAndroid Build Coastguard Worker s->max_distance = s->max_backward_distance;
1397*f4ee7fbaSAndroid Build Coastguard Worker }
1398*f4ee7fbaSAndroid Build Coastguard Worker s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;
1399*f4ee7fbaSAndroid Build Coastguard Worker break;
1400*f4ee7fbaSAndroid Build Coastguard Worker }
1401*f4ee7fbaSAndroid Build Coastguard Worker }
1402*f4ee7fbaSAndroid Build Coastguard Worker }
1403*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DCHECK(0); /* Unreachable */
1404*f4ee7fbaSAndroid Build Coastguard Worker }
1405*f4ee7fbaSAndroid Build Coastguard Worker
1406*f4ee7fbaSAndroid Build Coastguard Worker /* Calculates the smallest feasible ring buffer.
1407*f4ee7fbaSAndroid Build Coastguard Worker
1408*f4ee7fbaSAndroid Build Coastguard Worker If we know the data size is small, do not allocate more ring buffer
1409*f4ee7fbaSAndroid Build Coastguard Worker size than needed to reduce memory usage.
1410*f4ee7fbaSAndroid Build Coastguard Worker
1411*f4ee7fbaSAndroid Build Coastguard Worker When this method is called, metablock size and flags MUST be decoded. */
BrotliCalculateRingBufferSize(BrotliDecoderState * s)1412*f4ee7fbaSAndroid Build Coastguard Worker static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(
1413*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
1414*f4ee7fbaSAndroid Build Coastguard Worker int window_size = 1 << s->window_bits;
1415*f4ee7fbaSAndroid Build Coastguard Worker int new_ringbuffer_size = window_size;
1416*f4ee7fbaSAndroid Build Coastguard Worker /* We need at least 2 bytes of ring buffer size to get the last two
1417*f4ee7fbaSAndroid Build Coastguard Worker bytes for context from there */
1418*f4ee7fbaSAndroid Build Coastguard Worker int min_size = s->ringbuffer_size ? s->ringbuffer_size : 1024;
1419*f4ee7fbaSAndroid Build Coastguard Worker int output_size;
1420*f4ee7fbaSAndroid Build Coastguard Worker
1421*f4ee7fbaSAndroid Build Coastguard Worker /* If maximum is already reached, no further extension is retired. */
1422*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer_size == window_size) {
1423*f4ee7fbaSAndroid Build Coastguard Worker return;
1424*f4ee7fbaSAndroid Build Coastguard Worker }
1425*f4ee7fbaSAndroid Build Coastguard Worker
1426*f4ee7fbaSAndroid Build Coastguard Worker /* Metadata blocks does not touch ring buffer. */
1427*f4ee7fbaSAndroid Build Coastguard Worker if (s->is_metadata) {
1428*f4ee7fbaSAndroid Build Coastguard Worker return;
1429*f4ee7fbaSAndroid Build Coastguard Worker }
1430*f4ee7fbaSAndroid Build Coastguard Worker
1431*f4ee7fbaSAndroid Build Coastguard Worker if (!s->ringbuffer) {
1432*f4ee7fbaSAndroid Build Coastguard Worker output_size = 0;
1433*f4ee7fbaSAndroid Build Coastguard Worker } else {
1434*f4ee7fbaSAndroid Build Coastguard Worker output_size = s->pos;
1435*f4ee7fbaSAndroid Build Coastguard Worker }
1436*f4ee7fbaSAndroid Build Coastguard Worker output_size += s->meta_block_remaining_len;
1437*f4ee7fbaSAndroid Build Coastguard Worker min_size = min_size < output_size ? output_size : min_size;
1438*f4ee7fbaSAndroid Build Coastguard Worker
1439*f4ee7fbaSAndroid Build Coastguard Worker if (!!s->canny_ringbuffer_allocation) {
1440*f4ee7fbaSAndroid Build Coastguard Worker /* Reduce ring buffer size to save memory when server is unscrupulous.
1441*f4ee7fbaSAndroid Build Coastguard Worker In worst case memory usage might be 1.5x bigger for a short period of
1442*f4ee7fbaSAndroid Build Coastguard Worker ring buffer reallocation. */
1443*f4ee7fbaSAndroid Build Coastguard Worker while ((new_ringbuffer_size >> 1) >= min_size) {
1444*f4ee7fbaSAndroid Build Coastguard Worker new_ringbuffer_size >>= 1;
1445*f4ee7fbaSAndroid Build Coastguard Worker }
1446*f4ee7fbaSAndroid Build Coastguard Worker }
1447*f4ee7fbaSAndroid Build Coastguard Worker
1448*f4ee7fbaSAndroid Build Coastguard Worker s->new_ringbuffer_size = new_ringbuffer_size;
1449*f4ee7fbaSAndroid Build Coastguard Worker }
1450*f4ee7fbaSAndroid Build Coastguard Worker
1451*f4ee7fbaSAndroid Build Coastguard Worker /* Reads 1..256 2-bit context modes. */
ReadContextModes(BrotliDecoderState * s)1452*f4ee7fbaSAndroid Build Coastguard Worker static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) {
1453*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
1454*f4ee7fbaSAndroid Build Coastguard Worker int i = s->loop_counter;
1455*f4ee7fbaSAndroid Build Coastguard Worker
1456*f4ee7fbaSAndroid Build Coastguard Worker while (i < (int)s->num_block_types[0]) {
1457*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
1458*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 2, &bits)) {
1459*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = i;
1460*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_NEEDS_MORE_INPUT;
1461*f4ee7fbaSAndroid Build Coastguard Worker }
1462*f4ee7fbaSAndroid Build Coastguard Worker s->context_modes[i] = (uint8_t)bits;
1463*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
1464*f4ee7fbaSAndroid Build Coastguard Worker i++;
1465*f4ee7fbaSAndroid Build Coastguard Worker }
1466*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_SUCCESS;
1467*f4ee7fbaSAndroid Build Coastguard Worker }
1468*f4ee7fbaSAndroid Build Coastguard Worker
TakeDistanceFromRingBuffer(BrotliDecoderState * s)1469*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) {
1470*f4ee7fbaSAndroid Build Coastguard Worker int offset = s->distance_code - 3;
1471*f4ee7fbaSAndroid Build Coastguard Worker if (s->distance_code <= 3) {
1472*f4ee7fbaSAndroid Build Coastguard Worker /* Compensate double distance-ring-buffer roll for dictionary items. */
1473*f4ee7fbaSAndroid Build Coastguard Worker s->distance_context = 1 >> s->distance_code;
1474*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code = s->dist_rb[(s->dist_rb_idx - offset) & 3];
1475*f4ee7fbaSAndroid Build Coastguard Worker s->dist_rb_idx -= s->distance_context;
1476*f4ee7fbaSAndroid Build Coastguard Worker } else {
1477*f4ee7fbaSAndroid Build Coastguard Worker int index_delta = 3;
1478*f4ee7fbaSAndroid Build Coastguard Worker int delta;
1479*f4ee7fbaSAndroid Build Coastguard Worker int base = s->distance_code - 10;
1480*f4ee7fbaSAndroid Build Coastguard Worker if (s->distance_code < 10) {
1481*f4ee7fbaSAndroid Build Coastguard Worker base = s->distance_code - 4;
1482*f4ee7fbaSAndroid Build Coastguard Worker } else {
1483*f4ee7fbaSAndroid Build Coastguard Worker index_delta = 2;
1484*f4ee7fbaSAndroid Build Coastguard Worker }
1485*f4ee7fbaSAndroid Build Coastguard Worker /* Unpack one of six 4-bit values. */
1486*f4ee7fbaSAndroid Build Coastguard Worker delta = ((0x605142 >> (4 * base)) & 0xF) - 3;
1487*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code = s->dist_rb[(s->dist_rb_idx + index_delta) & 0x3] + delta;
1488*f4ee7fbaSAndroid Build Coastguard Worker if (s->distance_code <= 0) {
1489*f4ee7fbaSAndroid Build Coastguard Worker /* A huge distance will cause a BROTLI_FAILURE() soon.
1490*f4ee7fbaSAndroid Build Coastguard Worker This is a little faster than failing here. */
1491*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code = 0x7FFFFFFF;
1492*f4ee7fbaSAndroid Build Coastguard Worker }
1493*f4ee7fbaSAndroid Build Coastguard Worker }
1494*f4ee7fbaSAndroid Build Coastguard Worker }
1495*f4ee7fbaSAndroid Build Coastguard Worker
SafeReadBits(BrotliBitReader * const br,uint32_t n_bits,uint32_t * val)1496*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL SafeReadBits(
1497*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
1498*f4ee7fbaSAndroid Build Coastguard Worker if (n_bits != 0) {
1499*f4ee7fbaSAndroid Build Coastguard Worker return BrotliSafeReadBits(br, n_bits, val);
1500*f4ee7fbaSAndroid Build Coastguard Worker } else {
1501*f4ee7fbaSAndroid Build Coastguard Worker *val = 0;
1502*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1503*f4ee7fbaSAndroid Build Coastguard Worker }
1504*f4ee7fbaSAndroid Build Coastguard Worker }
1505*f4ee7fbaSAndroid Build Coastguard Worker
SafeReadBits32(BrotliBitReader * const br,uint32_t n_bits,uint32_t * val)1506*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL SafeReadBits32(
1507*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {
1508*f4ee7fbaSAndroid Build Coastguard Worker if (n_bits != 0) {
1509*f4ee7fbaSAndroid Build Coastguard Worker return BrotliSafeReadBits32(br, n_bits, val);
1510*f4ee7fbaSAndroid Build Coastguard Worker } else {
1511*f4ee7fbaSAndroid Build Coastguard Worker *val = 0;
1512*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1513*f4ee7fbaSAndroid Build Coastguard Worker }
1514*f4ee7fbaSAndroid Build Coastguard Worker }
1515*f4ee7fbaSAndroid Build Coastguard Worker
1516*f4ee7fbaSAndroid Build Coastguard Worker /*
1517*f4ee7fbaSAndroid Build Coastguard Worker RFC 7932 Section 4 with "..." shortenings and "[]" emendations.
1518*f4ee7fbaSAndroid Build Coastguard Worker
1519*f4ee7fbaSAndroid Build Coastguard Worker Each distance ... is represented with a pair <distance code, extra bits>...
1520*f4ee7fbaSAndroid Build Coastguard Worker The distance code is encoded using a prefix code... The number of extra bits
1521*f4ee7fbaSAndroid Build Coastguard Worker can be 0..24... Two additional parameters: NPOSTFIX (0..3), and ...
1522*f4ee7fbaSAndroid Build Coastguard Worker NDIRECT (0..120) ... are encoded in the meta-block header...
1523*f4ee7fbaSAndroid Build Coastguard Worker
1524*f4ee7fbaSAndroid Build Coastguard Worker The first 16 distance symbols ... reference past distances... ring buffer ...
1525*f4ee7fbaSAndroid Build Coastguard Worker Next NDIRECT distance symbols ... represent distances from 1 to NDIRECT...
1526*f4ee7fbaSAndroid Build Coastguard Worker [For] distance symbols 16 + NDIRECT and greater ... the number of extra bits
1527*f4ee7fbaSAndroid Build Coastguard Worker ... is given by the following formula:
1528*f4ee7fbaSAndroid Build Coastguard Worker
1529*f4ee7fbaSAndroid Build Coastguard Worker [ xcode = dcode - NDIRECT - 16 ]
1530*f4ee7fbaSAndroid Build Coastguard Worker ndistbits = 1 + [ xcode ] >> (NPOSTFIX + 1)
1531*f4ee7fbaSAndroid Build Coastguard Worker
1532*f4ee7fbaSAndroid Build Coastguard Worker ...
1533*f4ee7fbaSAndroid Build Coastguard Worker */
1534*f4ee7fbaSAndroid Build Coastguard Worker
1535*f4ee7fbaSAndroid Build Coastguard Worker /*
1536*f4ee7fbaSAndroid Build Coastguard Worker RFC 7932 Section 9.2 with "..." shortenings and "[]" emendations.
1537*f4ee7fbaSAndroid Build Coastguard Worker
1538*f4ee7fbaSAndroid Build Coastguard Worker ... to get the actual value of the parameter NDIRECT, left-shift this
1539*f4ee7fbaSAndroid Build Coastguard Worker four-bit number by NPOSTFIX bits ...
1540*f4ee7fbaSAndroid Build Coastguard Worker */
1541*f4ee7fbaSAndroid Build Coastguard Worker
1542*f4ee7fbaSAndroid Build Coastguard Worker /* Remaining formulas from RFC 7932 Section 4 could be rewritten as following:
1543*f4ee7fbaSAndroid Build Coastguard Worker
1544*f4ee7fbaSAndroid Build Coastguard Worker alphabet_size = 16 + NDIRECT + (max_distbits << (NPOSTFIX + 1))
1545*f4ee7fbaSAndroid Build Coastguard Worker
1546*f4ee7fbaSAndroid Build Coastguard Worker half = ((xcode >> NPOSTFIX) & 1) << ndistbits
1547*f4ee7fbaSAndroid Build Coastguard Worker postfix = xcode & ((1 << NPOSTFIX) - 1)
1548*f4ee7fbaSAndroid Build Coastguard Worker range_start = 2 * (1 << ndistbits - 1 - 1)
1549*f4ee7fbaSAndroid Build Coastguard Worker
1550*f4ee7fbaSAndroid Build Coastguard Worker distance = (range_start + half + extra) << NPOSTFIX + postfix + NDIRECT + 1
1551*f4ee7fbaSAndroid Build Coastguard Worker
1552*f4ee7fbaSAndroid Build Coastguard Worker NB: ndistbits >= 1 -> range_start >= 0
1553*f4ee7fbaSAndroid Build Coastguard Worker NB: range_start has factor 2, as the range is covered by 2 "halves"
1554*f4ee7fbaSAndroid Build Coastguard Worker NB: extra -1 offset in range_start formula covers the absence of
1555*f4ee7fbaSAndroid Build Coastguard Worker ndistbits = 0 case
1556*f4ee7fbaSAndroid Build Coastguard Worker NB: when NPOSTFIX = 0, NDIRECT is not greater than 15
1557*f4ee7fbaSAndroid Build Coastguard Worker
1558*f4ee7fbaSAndroid Build Coastguard Worker In other words, xcode has the following binary structure - XXXHPPP:
1559*f4ee7fbaSAndroid Build Coastguard Worker - XXX represent the number of extra distance bits
1560*f4ee7fbaSAndroid Build Coastguard Worker - H selects upper / lower range of distances
1561*f4ee7fbaSAndroid Build Coastguard Worker - PPP represent "postfix"
1562*f4ee7fbaSAndroid Build Coastguard Worker
1563*f4ee7fbaSAndroid Build Coastguard Worker "Regular" distance encoding has NPOSTFIX = 0; omitting the postfix part
1564*f4ee7fbaSAndroid Build Coastguard Worker simplifies distance calculation.
1565*f4ee7fbaSAndroid Build Coastguard Worker
1566*f4ee7fbaSAndroid Build Coastguard Worker Using NPOSTFIX > 0 allows cheaper encoding of regular structures, e.g. where
1567*f4ee7fbaSAndroid Build Coastguard Worker most of distances have the same reminder of division by 2/4/8. For example,
1568*f4ee7fbaSAndroid Build Coastguard Worker the table of int32_t values that come from different sources; if it is likely
1569*f4ee7fbaSAndroid Build Coastguard Worker that 3 highest bytes of values from the same source are the same, then
1570*f4ee7fbaSAndroid Build Coastguard Worker copy distance often looks like 4x + y.
1571*f4ee7fbaSAndroid Build Coastguard Worker
1572*f4ee7fbaSAndroid Build Coastguard Worker Distance calculation could be rewritten to:
1573*f4ee7fbaSAndroid Build Coastguard Worker
1574*f4ee7fbaSAndroid Build Coastguard Worker ndistbits = NDISTBITS(NDIRECT, NPOSTFIX)[dcode]
1575*f4ee7fbaSAndroid Build Coastguard Worker distance = OFFSET(NDIRECT, NPOSTFIX)[dcode] + extra << NPOSTFIX
1576*f4ee7fbaSAndroid Build Coastguard Worker
1577*f4ee7fbaSAndroid Build Coastguard Worker NDISTBITS and OFFSET could be pre-calculated, as NDIRECT and NPOSTFIX could
1578*f4ee7fbaSAndroid Build Coastguard Worker change only once per meta-block.
1579*f4ee7fbaSAndroid Build Coastguard Worker */
1580*f4ee7fbaSAndroid Build Coastguard Worker
1581*f4ee7fbaSAndroid Build Coastguard Worker /* Calculates distance lookup table.
1582*f4ee7fbaSAndroid Build Coastguard Worker NB: it is possible to have all 64 tables precalculated. */
CalculateDistanceLut(BrotliDecoderState * s)1583*f4ee7fbaSAndroid Build Coastguard Worker static void CalculateDistanceLut(BrotliDecoderState* s) {
1584*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockBodyArena* b = &s->arena.body;
1585*f4ee7fbaSAndroid Build Coastguard Worker uint32_t npostfix = s->distance_postfix_bits;
1586*f4ee7fbaSAndroid Build Coastguard Worker uint32_t ndirect = s->num_direct_distance_codes;
1587*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size_limit = s->distance_hgroup.alphabet_size_limit;
1588*f4ee7fbaSAndroid Build Coastguard Worker uint32_t postfix = 1u << npostfix;
1589*f4ee7fbaSAndroid Build Coastguard Worker uint32_t j;
1590*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits = 1;
1591*f4ee7fbaSAndroid Build Coastguard Worker uint32_t half = 0;
1592*f4ee7fbaSAndroid Build Coastguard Worker
1593*f4ee7fbaSAndroid Build Coastguard Worker /* Skip short codes. */
1594*f4ee7fbaSAndroid Build Coastguard Worker uint32_t i = BROTLI_NUM_DISTANCE_SHORT_CODES;
1595*f4ee7fbaSAndroid Build Coastguard Worker
1596*f4ee7fbaSAndroid Build Coastguard Worker /* Fill direct codes. */
1597*f4ee7fbaSAndroid Build Coastguard Worker for (j = 0; j < ndirect; ++j) {
1598*f4ee7fbaSAndroid Build Coastguard Worker b->dist_extra_bits[i] = 0;
1599*f4ee7fbaSAndroid Build Coastguard Worker b->dist_offset[i] = j + 1;
1600*f4ee7fbaSAndroid Build Coastguard Worker ++i;
1601*f4ee7fbaSAndroid Build Coastguard Worker }
1602*f4ee7fbaSAndroid Build Coastguard Worker
1603*f4ee7fbaSAndroid Build Coastguard Worker /* Fill regular distance codes. */
1604*f4ee7fbaSAndroid Build Coastguard Worker while (i < alphabet_size_limit) {
1605*f4ee7fbaSAndroid Build Coastguard Worker uint32_t base = ndirect + ((((2 + half) << bits) - 4) << npostfix) + 1;
1606*f4ee7fbaSAndroid Build Coastguard Worker /* Always fill the complete group. */
1607*f4ee7fbaSAndroid Build Coastguard Worker for (j = 0; j < postfix; ++j) {
1608*f4ee7fbaSAndroid Build Coastguard Worker b->dist_extra_bits[i] = (uint8_t)bits;
1609*f4ee7fbaSAndroid Build Coastguard Worker b->dist_offset[i] = base + j;
1610*f4ee7fbaSAndroid Build Coastguard Worker ++i;
1611*f4ee7fbaSAndroid Build Coastguard Worker }
1612*f4ee7fbaSAndroid Build Coastguard Worker bits = bits + half;
1613*f4ee7fbaSAndroid Build Coastguard Worker half = half ^ 1;
1614*f4ee7fbaSAndroid Build Coastguard Worker }
1615*f4ee7fbaSAndroid Build Coastguard Worker }
1616*f4ee7fbaSAndroid Build Coastguard Worker
1617*f4ee7fbaSAndroid Build Coastguard Worker /* Precondition: s->distance_code < 0. */
ReadDistanceInternal(int safe,BrotliDecoderState * s,BrotliBitReader * br)1618*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal(
1619*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s, BrotliBitReader* br) {
1620*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockBodyArena* b = &s->arena.body;
1621*f4ee7fbaSAndroid Build Coastguard Worker uint32_t code;
1622*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
1623*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderState memento;
1624*f4ee7fbaSAndroid Build Coastguard Worker HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index];
1625*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1626*f4ee7fbaSAndroid Build Coastguard Worker code = ReadSymbol(distance_tree, br);
1627*f4ee7fbaSAndroid Build Coastguard Worker } else {
1628*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderSaveState(br, &memento);
1629*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(distance_tree, br, &code)) {
1630*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1631*f4ee7fbaSAndroid Build Coastguard Worker }
1632*f4ee7fbaSAndroid Build Coastguard Worker }
1633*f4ee7fbaSAndroid Build Coastguard Worker --s->block_length[2];
1634*f4ee7fbaSAndroid Build Coastguard Worker /* Convert the distance code to the actual distance by possibly
1635*f4ee7fbaSAndroid Build Coastguard Worker looking up past distances from the s->dist_rb. */
1636*f4ee7fbaSAndroid Build Coastguard Worker s->distance_context = 0;
1637*f4ee7fbaSAndroid Build Coastguard Worker if ((code & ~0xFu) == 0) {
1638*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code = (int)code;
1639*f4ee7fbaSAndroid Build Coastguard Worker TakeDistanceFromRingBuffer(s);
1640*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1641*f4ee7fbaSAndroid Build Coastguard Worker }
1642*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1643*f4ee7fbaSAndroid Build Coastguard Worker bits = BrotliReadBits32(br, b->dist_extra_bits[code]);
1644*f4ee7fbaSAndroid Build Coastguard Worker } else {
1645*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadBits32(br, b->dist_extra_bits[code], &bits)) {
1646*f4ee7fbaSAndroid Build Coastguard Worker ++s->block_length[2];
1647*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderRestoreState(br, &memento);
1648*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1649*f4ee7fbaSAndroid Build Coastguard Worker }
1650*f4ee7fbaSAndroid Build Coastguard Worker }
1651*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code =
1652*f4ee7fbaSAndroid Build Coastguard Worker (int)(b->dist_offset[code] + (bits << s->distance_postfix_bits));
1653*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1654*f4ee7fbaSAndroid Build Coastguard Worker }
1655*f4ee7fbaSAndroid Build Coastguard Worker
ReadDistance(BrotliDecoderState * s,BrotliBitReader * br)1656*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void ReadDistance(
1657*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliBitReader* br) {
1658*f4ee7fbaSAndroid Build Coastguard Worker ReadDistanceInternal(0, s, br);
1659*f4ee7fbaSAndroid Build Coastguard Worker }
1660*f4ee7fbaSAndroid Build Coastguard Worker
SafeReadDistance(BrotliDecoderState * s,BrotliBitReader * br)1661*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL SafeReadDistance(
1662*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliBitReader* br) {
1663*f4ee7fbaSAndroid Build Coastguard Worker return ReadDistanceInternal(1, s, br);
1664*f4ee7fbaSAndroid Build Coastguard Worker }
1665*f4ee7fbaSAndroid Build Coastguard Worker
ReadCommandInternal(int safe,BrotliDecoderState * s,BrotliBitReader * br,int * insert_length)1666*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal(
1667*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
1668*f4ee7fbaSAndroid Build Coastguard Worker uint32_t cmd_code;
1669*f4ee7fbaSAndroid Build Coastguard Worker uint32_t insert_len_extra = 0;
1670*f4ee7fbaSAndroid Build Coastguard Worker uint32_t copy_length;
1671*f4ee7fbaSAndroid Build Coastguard Worker CmdLutElement v;
1672*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderState memento;
1673*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1674*f4ee7fbaSAndroid Build Coastguard Worker cmd_code = ReadSymbol(s->htree_command, br);
1675*f4ee7fbaSAndroid Build Coastguard Worker } else {
1676*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderSaveState(br, &memento);
1677*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) {
1678*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1679*f4ee7fbaSAndroid Build Coastguard Worker }
1680*f4ee7fbaSAndroid Build Coastguard Worker }
1681*f4ee7fbaSAndroid Build Coastguard Worker v = kCmdLut[cmd_code];
1682*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code = v.distance_code;
1683*f4ee7fbaSAndroid Build Coastguard Worker s->distance_context = v.context;
1684*f4ee7fbaSAndroid Build Coastguard Worker s->dist_htree_index = s->dist_context_map_slice[s->distance_context];
1685*f4ee7fbaSAndroid Build Coastguard Worker *insert_length = v.insert_len_offset;
1686*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1687*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(v.insert_len_extra_bits != 0)) {
1688*f4ee7fbaSAndroid Build Coastguard Worker insert_len_extra = BrotliReadBits24(br, v.insert_len_extra_bits);
1689*f4ee7fbaSAndroid Build Coastguard Worker }
1690*f4ee7fbaSAndroid Build Coastguard Worker copy_length = BrotliReadBits24(br, v.copy_len_extra_bits);
1691*f4ee7fbaSAndroid Build Coastguard Worker } else {
1692*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) ||
1693*f4ee7fbaSAndroid Build Coastguard Worker !SafeReadBits(br, v.copy_len_extra_bits, ©_length)) {
1694*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderRestoreState(br, &memento);
1695*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
1696*f4ee7fbaSAndroid Build Coastguard Worker }
1697*f4ee7fbaSAndroid Build Coastguard Worker }
1698*f4ee7fbaSAndroid Build Coastguard Worker s->copy_length = (int)copy_length + v.copy_len_offset;
1699*f4ee7fbaSAndroid Build Coastguard Worker --s->block_length[1];
1700*f4ee7fbaSAndroid Build Coastguard Worker *insert_length += (int)insert_len_extra;
1701*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1702*f4ee7fbaSAndroid Build Coastguard Worker }
1703*f4ee7fbaSAndroid Build Coastguard Worker
ReadCommand(BrotliDecoderState * s,BrotliBitReader * br,int * insert_length)1704*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE void ReadCommand(
1705*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
1706*f4ee7fbaSAndroid Build Coastguard Worker ReadCommandInternal(0, s, br, insert_length);
1707*f4ee7fbaSAndroid Build Coastguard Worker }
1708*f4ee7fbaSAndroid Build Coastguard Worker
SafeReadCommand(BrotliDecoderState * s,BrotliBitReader * br,int * insert_length)1709*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL SafeReadCommand(
1710*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {
1711*f4ee7fbaSAndroid Build Coastguard Worker return ReadCommandInternal(1, s, br, insert_length);
1712*f4ee7fbaSAndroid Build Coastguard Worker }
1713*f4ee7fbaSAndroid Build Coastguard Worker
CheckInputAmount(int safe,BrotliBitReader * const br,size_t num)1714*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BROTLI_BOOL CheckInputAmount(
1715*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliBitReader* const br, size_t num) {
1716*f4ee7fbaSAndroid Build Coastguard Worker if (safe) {
1717*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_TRUE;
1718*f4ee7fbaSAndroid Build Coastguard Worker }
1719*f4ee7fbaSAndroid Build Coastguard Worker return BrotliCheckInputAmount(br, num);
1720*f4ee7fbaSAndroid Build Coastguard Worker }
1721*f4ee7fbaSAndroid Build Coastguard Worker
1722*f4ee7fbaSAndroid Build Coastguard Worker #define BROTLI_SAFE(METHOD) \
1723*f4ee7fbaSAndroid Build Coastguard Worker { \
1724*f4ee7fbaSAndroid Build Coastguard Worker if (safe) { \
1725*f4ee7fbaSAndroid Build Coastguard Worker if (!Safe##METHOD) { \
1726*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT; \
1727*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn; \
1728*f4ee7fbaSAndroid Build Coastguard Worker } \
1729*f4ee7fbaSAndroid Build Coastguard Worker } else { \
1730*f4ee7fbaSAndroid Build Coastguard Worker METHOD; \
1731*f4ee7fbaSAndroid Build Coastguard Worker } \
1732*f4ee7fbaSAndroid Build Coastguard Worker }
1733*f4ee7fbaSAndroid Build Coastguard Worker
ProcessCommandsInternal(int safe,BrotliDecoderState * s)1734*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal(
1735*f4ee7fbaSAndroid Build Coastguard Worker int safe, BrotliDecoderState* s) {
1736*f4ee7fbaSAndroid Build Coastguard Worker int pos = s->pos;
1737*f4ee7fbaSAndroid Build Coastguard Worker int i = s->loop_counter;
1738*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
1739*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
1740*f4ee7fbaSAndroid Build Coastguard Worker
1741*f4ee7fbaSAndroid Build Coastguard Worker if (!CheckInputAmount(safe, br, 28)) {
1742*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1743*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1744*f4ee7fbaSAndroid Build Coastguard Worker }
1745*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1746*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_UNUSED(BrotliWarmupBitReader(br));
1747*f4ee7fbaSAndroid Build Coastguard Worker }
1748*f4ee7fbaSAndroid Build Coastguard Worker
1749*f4ee7fbaSAndroid Build Coastguard Worker /* Jump into state machine. */
1750*f4ee7fbaSAndroid Build Coastguard Worker if (s->state == BROTLI_STATE_COMMAND_BEGIN) {
1751*f4ee7fbaSAndroid Build Coastguard Worker goto CommandBegin;
1752*f4ee7fbaSAndroid Build Coastguard Worker } else if (s->state == BROTLI_STATE_COMMAND_INNER) {
1753*f4ee7fbaSAndroid Build Coastguard Worker goto CommandInner;
1754*f4ee7fbaSAndroid Build Coastguard Worker } else if (s->state == BROTLI_STATE_COMMAND_POST_DECODE_LITERALS) {
1755*f4ee7fbaSAndroid Build Coastguard Worker goto CommandPostDecodeLiterals;
1756*f4ee7fbaSAndroid Build Coastguard Worker } else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) {
1757*f4ee7fbaSAndroid Build Coastguard Worker goto CommandPostWrapCopy;
1758*f4ee7fbaSAndroid Build Coastguard Worker } else {
1759*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);
1760*f4ee7fbaSAndroid Build Coastguard Worker }
1761*f4ee7fbaSAndroid Build Coastguard Worker
1762*f4ee7fbaSAndroid Build Coastguard Worker CommandBegin:
1763*f4ee7fbaSAndroid Build Coastguard Worker if (safe) {
1764*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_BEGIN;
1765*f4ee7fbaSAndroid Build Coastguard Worker }
1766*f4ee7fbaSAndroid Build Coastguard Worker if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */
1767*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_BEGIN;
1768*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1769*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1770*f4ee7fbaSAndroid Build Coastguard Worker }
1771*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(s->block_length[1] == 0)) {
1772*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_SAFE(DecodeCommandBlockSwitch(s));
1773*f4ee7fbaSAndroid Build Coastguard Worker goto CommandBegin;
1774*f4ee7fbaSAndroid Build Coastguard Worker }
1775*f4ee7fbaSAndroid Build Coastguard Worker /* Read the insert/copy length in the command. */
1776*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_SAFE(ReadCommand(s, br, &i));
1777*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",
1778*f4ee7fbaSAndroid Build Coastguard Worker pos, i, s->copy_length));
1779*f4ee7fbaSAndroid Build Coastguard Worker if (i == 0) {
1780*f4ee7fbaSAndroid Build Coastguard Worker goto CommandPostDecodeLiterals;
1781*f4ee7fbaSAndroid Build Coastguard Worker }
1782*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len -= i;
1783*f4ee7fbaSAndroid Build Coastguard Worker
1784*f4ee7fbaSAndroid Build Coastguard Worker CommandInner:
1785*f4ee7fbaSAndroid Build Coastguard Worker if (safe) {
1786*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_INNER;
1787*f4ee7fbaSAndroid Build Coastguard Worker }
1788*f4ee7fbaSAndroid Build Coastguard Worker /* Read the literals in the command. */
1789*f4ee7fbaSAndroid Build Coastguard Worker if (s->trivial_literal_context) {
1790*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
1791*f4ee7fbaSAndroid Build Coastguard Worker uint32_t value;
1792*f4ee7fbaSAndroid Build Coastguard Worker PreloadSymbol(safe, s->literal_htree, br, &bits, &value);
1793*f4ee7fbaSAndroid Build Coastguard Worker do {
1794*f4ee7fbaSAndroid Build Coastguard Worker if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
1795*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_INNER;
1796*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1797*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1798*f4ee7fbaSAndroid Build Coastguard Worker }
1799*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {
1800*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_SAFE(DecodeLiteralBlockSwitch(s));
1801*f4ee7fbaSAndroid Build Coastguard Worker PreloadSymbol(safe, s->literal_htree, br, &bits, &value);
1802*f4ee7fbaSAndroid Build Coastguard Worker if (!s->trivial_literal_context) goto CommandInner;
1803*f4ee7fbaSAndroid Build Coastguard Worker }
1804*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1805*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[pos] =
1806*f4ee7fbaSAndroid Build Coastguard Worker (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value);
1807*f4ee7fbaSAndroid Build Coastguard Worker } else {
1808*f4ee7fbaSAndroid Build Coastguard Worker uint32_t literal;
1809*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(s->literal_htree, br, &literal)) {
1810*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1811*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1812*f4ee7fbaSAndroid Build Coastguard Worker }
1813*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[pos] = (uint8_t)literal;
1814*f4ee7fbaSAndroid Build Coastguard Worker }
1815*f4ee7fbaSAndroid Build Coastguard Worker --s->block_length[0];
1816*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos);
1817*f4ee7fbaSAndroid Build Coastguard Worker ++pos;
1818*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {
1819*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
1820*f4ee7fbaSAndroid Build Coastguard Worker --i;
1821*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1822*f4ee7fbaSAndroid Build Coastguard Worker }
1823*f4ee7fbaSAndroid Build Coastguard Worker } while (--i != 0);
1824*f4ee7fbaSAndroid Build Coastguard Worker } else {
1825*f4ee7fbaSAndroid Build Coastguard Worker uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1826*f4ee7fbaSAndroid Build Coastguard Worker uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
1827*f4ee7fbaSAndroid Build Coastguard Worker do {
1828*f4ee7fbaSAndroid Build Coastguard Worker const HuffmanCode* hc;
1829*f4ee7fbaSAndroid Build Coastguard Worker uint8_t context;
1830*f4ee7fbaSAndroid Build Coastguard Worker if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */
1831*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_INNER;
1832*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1833*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1834*f4ee7fbaSAndroid Build Coastguard Worker }
1835*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(s->block_length[0] == 0)) {
1836*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_SAFE(DecodeLiteralBlockSwitch(s));
1837*f4ee7fbaSAndroid Build Coastguard Worker if (s->trivial_literal_context) goto CommandInner;
1838*f4ee7fbaSAndroid Build Coastguard Worker }
1839*f4ee7fbaSAndroid Build Coastguard Worker context = BROTLI_CONTEXT(p1, p2, s->context_lookup);
1840*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(context);
1841*f4ee7fbaSAndroid Build Coastguard Worker hc = s->literal_hgroup.htrees[s->context_map_slice[context]];
1842*f4ee7fbaSAndroid Build Coastguard Worker p2 = p1;
1843*f4ee7fbaSAndroid Build Coastguard Worker if (!safe) {
1844*f4ee7fbaSAndroid Build Coastguard Worker p1 = (uint8_t)ReadSymbol(hc, br);
1845*f4ee7fbaSAndroid Build Coastguard Worker } else {
1846*f4ee7fbaSAndroid Build Coastguard Worker uint32_t literal;
1847*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadSymbol(hc, br, &literal)) {
1848*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
1849*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1850*f4ee7fbaSAndroid Build Coastguard Worker }
1851*f4ee7fbaSAndroid Build Coastguard Worker p1 = (uint8_t)literal;
1852*f4ee7fbaSAndroid Build Coastguard Worker }
1853*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[pos] = p1;
1854*f4ee7fbaSAndroid Build Coastguard Worker --s->block_length[0];
1855*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->context_map_slice[context]);
1856*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1857*f4ee7fbaSAndroid Build Coastguard Worker ++pos;
1858*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(pos == s->ringbuffer_size)) {
1859*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
1860*f4ee7fbaSAndroid Build Coastguard Worker --i;
1861*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1862*f4ee7fbaSAndroid Build Coastguard Worker }
1863*f4ee7fbaSAndroid Build Coastguard Worker } while (--i != 0);
1864*f4ee7fbaSAndroid Build Coastguard Worker }
1865*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->meta_block_remaining_len);
1866*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(s->meta_block_remaining_len <= 0)) {
1867*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
1868*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1869*f4ee7fbaSAndroid Build Coastguard Worker }
1870*f4ee7fbaSAndroid Build Coastguard Worker
1871*f4ee7fbaSAndroid Build Coastguard Worker CommandPostDecodeLiterals:
1872*f4ee7fbaSAndroid Build Coastguard Worker if (safe) {
1873*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;
1874*f4ee7fbaSAndroid Build Coastguard Worker }
1875*f4ee7fbaSAndroid Build Coastguard Worker if (s->distance_code >= 0) {
1876*f4ee7fbaSAndroid Build Coastguard Worker /* Implicit distance case. */
1877*f4ee7fbaSAndroid Build Coastguard Worker s->distance_context = s->distance_code ? 0 : 1;
1878*f4ee7fbaSAndroid Build Coastguard Worker --s->dist_rb_idx;
1879*f4ee7fbaSAndroid Build Coastguard Worker s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
1880*f4ee7fbaSAndroid Build Coastguard Worker } else {
1881*f4ee7fbaSAndroid Build Coastguard Worker /* Read distance code in the command, unless it was implicitly zero. */
1882*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(s->block_length[2] == 0)) {
1883*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_SAFE(DecodeDistanceBlockSwitch(s));
1884*f4ee7fbaSAndroid Build Coastguard Worker }
1885*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_SAFE(ReadDistance(s, br));
1886*f4ee7fbaSAndroid Build Coastguard Worker }
1887*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",
1888*f4ee7fbaSAndroid Build Coastguard Worker pos, s->distance_code));
1889*f4ee7fbaSAndroid Build Coastguard Worker if (s->max_distance != s->max_backward_distance) {
1890*f4ee7fbaSAndroid Build Coastguard Worker s->max_distance =
1891*f4ee7fbaSAndroid Build Coastguard Worker (pos < s->max_backward_distance) ? pos : s->max_backward_distance;
1892*f4ee7fbaSAndroid Build Coastguard Worker }
1893*f4ee7fbaSAndroid Build Coastguard Worker i = s->copy_length;
1894*f4ee7fbaSAndroid Build Coastguard Worker /* Apply copy of LZ77 back-reference, or static dictionary reference if
1895*f4ee7fbaSAndroid Build Coastguard Worker the distance is larger than the max LZ77 distance */
1896*f4ee7fbaSAndroid Build Coastguard Worker if (s->distance_code > s->max_distance) {
1897*f4ee7fbaSAndroid Build Coastguard Worker /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC.
1898*f4ee7fbaSAndroid Build Coastguard Worker With this choice, no signed overflow can occur after decoding
1899*f4ee7fbaSAndroid Build Coastguard Worker a special distance code (e.g., after adding 3 to the last distance). */
1900*f4ee7fbaSAndroid Build Coastguard Worker if (s->distance_code > BROTLI_MAX_ALLOWED_DISTANCE) {
1901*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1902*f4ee7fbaSAndroid Build Coastguard Worker "len: %d bytes left: %d\n",
1903*f4ee7fbaSAndroid Build Coastguard Worker pos, s->distance_code, i, s->meta_block_remaining_len));
1904*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE);
1905*f4ee7fbaSAndroid Build Coastguard Worker }
1906*f4ee7fbaSAndroid Build Coastguard Worker if (i >= BROTLI_MIN_DICTIONARY_WORD_LENGTH &&
1907*f4ee7fbaSAndroid Build Coastguard Worker i <= BROTLI_MAX_DICTIONARY_WORD_LENGTH) {
1908*f4ee7fbaSAndroid Build Coastguard Worker int address = s->distance_code - s->max_distance - 1;
1909*f4ee7fbaSAndroid Build Coastguard Worker const BrotliDictionary* words = s->dictionary;
1910*f4ee7fbaSAndroid Build Coastguard Worker const BrotliTransforms* transforms = s->transforms;
1911*f4ee7fbaSAndroid Build Coastguard Worker int offset = (int)s->dictionary->offsets_by_length[i];
1912*f4ee7fbaSAndroid Build Coastguard Worker uint32_t shift = s->dictionary->size_bits_by_length[i];
1913*f4ee7fbaSAndroid Build Coastguard Worker
1914*f4ee7fbaSAndroid Build Coastguard Worker int mask = (int)BitMask(shift);
1915*f4ee7fbaSAndroid Build Coastguard Worker int word_idx = address & mask;
1916*f4ee7fbaSAndroid Build Coastguard Worker int transform_idx = address >> shift;
1917*f4ee7fbaSAndroid Build Coastguard Worker /* Compensate double distance-ring-buffer roll. */
1918*f4ee7fbaSAndroid Build Coastguard Worker s->dist_rb_idx += s->distance_context;
1919*f4ee7fbaSAndroid Build Coastguard Worker offset += word_idx * i;
1920*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(!words->data)) {
1921*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET);
1922*f4ee7fbaSAndroid Build Coastguard Worker }
1923*f4ee7fbaSAndroid Build Coastguard Worker if (transform_idx < (int)transforms->num_transforms) {
1924*f4ee7fbaSAndroid Build Coastguard Worker const uint8_t* word = &words->data[offset];
1925*f4ee7fbaSAndroid Build Coastguard Worker int len = i;
1926*f4ee7fbaSAndroid Build Coastguard Worker if (transform_idx == transforms->cutOffTransforms[0]) {
1927*f4ee7fbaSAndroid Build Coastguard Worker memcpy(&s->ringbuffer[pos], word, (size_t)len);
1928*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n",
1929*f4ee7fbaSAndroid Build Coastguard Worker len, word));
1930*f4ee7fbaSAndroid Build Coastguard Worker } else {
1931*f4ee7fbaSAndroid Build Coastguard Worker len = BrotliTransformDictionaryWord(&s->ringbuffer[pos], word, len,
1932*f4ee7fbaSAndroid Build Coastguard Worker transforms, transform_idx);
1933*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s],"
1934*f4ee7fbaSAndroid Build Coastguard Worker " transform_idx = %d, transformed: [%.*s]\n",
1935*f4ee7fbaSAndroid Build Coastguard Worker i, word, transform_idx, len, &s->ringbuffer[pos]));
1936*f4ee7fbaSAndroid Build Coastguard Worker }
1937*f4ee7fbaSAndroid Build Coastguard Worker pos += len;
1938*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len -= len;
1939*f4ee7fbaSAndroid Build Coastguard Worker if (pos >= s->ringbuffer_size) {
1940*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;
1941*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1942*f4ee7fbaSAndroid Build Coastguard Worker }
1943*f4ee7fbaSAndroid Build Coastguard Worker } else {
1944*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1945*f4ee7fbaSAndroid Build Coastguard Worker "len: %d bytes left: %d\n",
1946*f4ee7fbaSAndroid Build Coastguard Worker pos, s->distance_code, i, s->meta_block_remaining_len));
1947*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM);
1948*f4ee7fbaSAndroid Build Coastguard Worker }
1949*f4ee7fbaSAndroid Build Coastguard Worker } else {
1950*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1951*f4ee7fbaSAndroid Build Coastguard Worker "len: %d bytes left: %d\n",
1952*f4ee7fbaSAndroid Build Coastguard Worker pos, s->distance_code, i, s->meta_block_remaining_len));
1953*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY);
1954*f4ee7fbaSAndroid Build Coastguard Worker }
1955*f4ee7fbaSAndroid Build Coastguard Worker } else {
1956*f4ee7fbaSAndroid Build Coastguard Worker int src_start = (pos - s->distance_code) & s->ringbuffer_mask;
1957*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* copy_dst = &s->ringbuffer[pos];
1958*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* copy_src = &s->ringbuffer[src_start];
1959*f4ee7fbaSAndroid Build Coastguard Worker int dst_end = pos + i;
1960*f4ee7fbaSAndroid Build Coastguard Worker int src_end = src_start + i;
1961*f4ee7fbaSAndroid Build Coastguard Worker /* Update the recent distances cache. */
1962*f4ee7fbaSAndroid Build Coastguard Worker s->dist_rb[s->dist_rb_idx & 3] = s->distance_code;
1963*f4ee7fbaSAndroid Build Coastguard Worker ++s->dist_rb_idx;
1964*f4ee7fbaSAndroid Build Coastguard Worker s->meta_block_remaining_len -= i;
1965*f4ee7fbaSAndroid Build Coastguard Worker /* There are 32+ bytes of slack in the ring-buffer allocation.
1966*f4ee7fbaSAndroid Build Coastguard Worker Also, we have 16 short codes, that make these 16 bytes irrelevant
1967*f4ee7fbaSAndroid Build Coastguard Worker in the ring-buffer. Let's copy over them as a first guess. */
1968*f4ee7fbaSAndroid Build Coastguard Worker memmove16(copy_dst, copy_src);
1969*f4ee7fbaSAndroid Build Coastguard Worker if (src_end > pos && dst_end > src_start) {
1970*f4ee7fbaSAndroid Build Coastguard Worker /* Regions intersect. */
1971*f4ee7fbaSAndroid Build Coastguard Worker goto CommandPostWrapCopy;
1972*f4ee7fbaSAndroid Build Coastguard Worker }
1973*f4ee7fbaSAndroid Build Coastguard Worker if (dst_end >= s->ringbuffer_size || src_end >= s->ringbuffer_size) {
1974*f4ee7fbaSAndroid Build Coastguard Worker /* At least one region wraps. */
1975*f4ee7fbaSAndroid Build Coastguard Worker goto CommandPostWrapCopy;
1976*f4ee7fbaSAndroid Build Coastguard Worker }
1977*f4ee7fbaSAndroid Build Coastguard Worker pos += i;
1978*f4ee7fbaSAndroid Build Coastguard Worker if (i > 16) {
1979*f4ee7fbaSAndroid Build Coastguard Worker if (i > 32) {
1980*f4ee7fbaSAndroid Build Coastguard Worker memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16));
1981*f4ee7fbaSAndroid Build Coastguard Worker } else {
1982*f4ee7fbaSAndroid Build Coastguard Worker /* This branch covers about 45% cases.
1983*f4ee7fbaSAndroid Build Coastguard Worker Fixed size short copy allows more compiler optimizations. */
1984*f4ee7fbaSAndroid Build Coastguard Worker memmove16(copy_dst + 16, copy_src + 16);
1985*f4ee7fbaSAndroid Build Coastguard Worker }
1986*f4ee7fbaSAndroid Build Coastguard Worker }
1987*f4ee7fbaSAndroid Build Coastguard Worker }
1988*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->meta_block_remaining_len);
1989*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len <= 0) {
1990*f4ee7fbaSAndroid Build Coastguard Worker /* Next metablock, if any. */
1991*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
1992*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
1993*f4ee7fbaSAndroid Build Coastguard Worker } else {
1994*f4ee7fbaSAndroid Build Coastguard Worker goto CommandBegin;
1995*f4ee7fbaSAndroid Build Coastguard Worker }
1996*f4ee7fbaSAndroid Build Coastguard Worker CommandPostWrapCopy:
1997*f4ee7fbaSAndroid Build Coastguard Worker {
1998*f4ee7fbaSAndroid Build Coastguard Worker int wrap_guard = s->ringbuffer_size - pos;
1999*f4ee7fbaSAndroid Build Coastguard Worker while (--i >= 0) {
2000*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[pos] =
2001*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];
2002*f4ee7fbaSAndroid Build Coastguard Worker ++pos;
2003*f4ee7fbaSAndroid Build Coastguard Worker if (BROTLI_PREDICT_FALSE(--wrap_guard == 0)) {
2004*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_POST_WRITE_2;
2005*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
2006*f4ee7fbaSAndroid Build Coastguard Worker }
2007*f4ee7fbaSAndroid Build Coastguard Worker }
2008*f4ee7fbaSAndroid Build Coastguard Worker }
2009*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len <= 0) {
2010*f4ee7fbaSAndroid Build Coastguard Worker /* Next metablock, if any. */
2011*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
2012*f4ee7fbaSAndroid Build Coastguard Worker goto saveStateAndReturn;
2013*f4ee7fbaSAndroid Build Coastguard Worker } else {
2014*f4ee7fbaSAndroid Build Coastguard Worker goto CommandBegin;
2015*f4ee7fbaSAndroid Build Coastguard Worker }
2016*f4ee7fbaSAndroid Build Coastguard Worker
2017*f4ee7fbaSAndroid Build Coastguard Worker saveStateAndReturn:
2018*f4ee7fbaSAndroid Build Coastguard Worker s->pos = pos;
2019*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = i;
2020*f4ee7fbaSAndroid Build Coastguard Worker return result;
2021*f4ee7fbaSAndroid Build Coastguard Worker }
2022*f4ee7fbaSAndroid Build Coastguard Worker
2023*f4ee7fbaSAndroid Build Coastguard Worker #undef BROTLI_SAFE
2024*f4ee7fbaSAndroid Build Coastguard Worker
ProcessCommands(BrotliDecoderState * s)2025*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands(
2026*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
2027*f4ee7fbaSAndroid Build Coastguard Worker return ProcessCommandsInternal(0, s);
2028*f4ee7fbaSAndroid Build Coastguard Worker }
2029*f4ee7fbaSAndroid Build Coastguard Worker
SafeProcessCommands(BrotliDecoderState * s)2030*f4ee7fbaSAndroid Build Coastguard Worker static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands(
2031*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s) {
2032*f4ee7fbaSAndroid Build Coastguard Worker return ProcessCommandsInternal(1, s);
2033*f4ee7fbaSAndroid Build Coastguard Worker }
2034*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderDecompress(size_t encoded_size,const uint8_t * encoded_buffer,size_t * decoded_size,uint8_t * decoded_buffer)2035*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderResult BrotliDecoderDecompress(
2036*f4ee7fbaSAndroid Build Coastguard Worker size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,
2037*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* decoded_buffer) {
2038*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState s;
2039*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderResult result;
2040*f4ee7fbaSAndroid Build Coastguard Worker size_t total_out = 0;
2041*f4ee7fbaSAndroid Build Coastguard Worker size_t available_in = encoded_size;
2042*f4ee7fbaSAndroid Build Coastguard Worker const uint8_t* next_in = encoded_buffer;
2043*f4ee7fbaSAndroid Build Coastguard Worker size_t available_out = *decoded_size;
2044*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* next_out = decoded_buffer;
2045*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliDecoderStateInit(&s, 0, 0, 0)) {
2046*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_RESULT_ERROR;
2047*f4ee7fbaSAndroid Build Coastguard Worker }
2048*f4ee7fbaSAndroid Build Coastguard Worker result = BrotliDecoderDecompressStream(
2049*f4ee7fbaSAndroid Build Coastguard Worker &s, &available_in, &next_in, &available_out, &next_out, &total_out);
2050*f4ee7fbaSAndroid Build Coastguard Worker *decoded_size = total_out;
2051*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderStateCleanup(&s);
2052*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_RESULT_SUCCESS) {
2053*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_RESULT_ERROR;
2054*f4ee7fbaSAndroid Build Coastguard Worker }
2055*f4ee7fbaSAndroid Build Coastguard Worker return result;
2056*f4ee7fbaSAndroid Build Coastguard Worker }
2057*f4ee7fbaSAndroid Build Coastguard Worker
2058*f4ee7fbaSAndroid Build Coastguard Worker /* Invariant: input stream is never overconsumed:
2059*f4ee7fbaSAndroid Build Coastguard Worker - invalid input implies that the whole stream is invalid -> any amount of
2060*f4ee7fbaSAndroid Build Coastguard Worker input could be read and discarded
2061*f4ee7fbaSAndroid Build Coastguard Worker - when result is "needs more input", then at least one more byte is REQUIRED
2062*f4ee7fbaSAndroid Build Coastguard Worker to complete decoding; all input data MUST be consumed by decoder, so
2063*f4ee7fbaSAndroid Build Coastguard Worker client could swap the input buffer
2064*f4ee7fbaSAndroid Build Coastguard Worker - when result is "needs more output" decoder MUST ensure that it doesn't
2065*f4ee7fbaSAndroid Build Coastguard Worker hold more than 7 bits in bit reader; this saves client from swapping input
2066*f4ee7fbaSAndroid Build Coastguard Worker buffer ahead of time
2067*f4ee7fbaSAndroid Build Coastguard Worker - when result is "success" decoder MUST return all unused data back to input
2068*f4ee7fbaSAndroid Build Coastguard Worker buffer; this is possible because the invariant is held on enter */
BrotliDecoderDecompressStream(BrotliDecoderState * s,size_t * available_in,const uint8_t ** next_in,size_t * available_out,uint8_t ** next_out,size_t * total_out)2069*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderResult BrotliDecoderDecompressStream(
2070*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in,
2071*f4ee7fbaSAndroid Build Coastguard Worker size_t* available_out, uint8_t** next_out, size_t* total_out) {
2072*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;
2073*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReader* br = &s->br;
2074*f4ee7fbaSAndroid Build Coastguard Worker /* Ensure that |total_out| is set, even if no data will ever be pushed out. */
2075*f4ee7fbaSAndroid Build Coastguard Worker if (total_out) {
2076*f4ee7fbaSAndroid Build Coastguard Worker *total_out = s->partial_pos_out;
2077*f4ee7fbaSAndroid Build Coastguard Worker }
2078*f4ee7fbaSAndroid Build Coastguard Worker /* Do not try to process further in a case of unrecoverable error. */
2079*f4ee7fbaSAndroid Build Coastguard Worker if ((int)s->error_code < 0) {
2080*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_DECODER_RESULT_ERROR;
2081*f4ee7fbaSAndroid Build Coastguard Worker }
2082*f4ee7fbaSAndroid Build Coastguard Worker if (*available_out && (!next_out || !*next_out)) {
2083*f4ee7fbaSAndroid Build Coastguard Worker return SaveErrorCode(
2084*f4ee7fbaSAndroid Build Coastguard Worker s, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS));
2085*f4ee7fbaSAndroid Build Coastguard Worker }
2086*f4ee7fbaSAndroid Build Coastguard Worker if (!*available_out) next_out = 0;
2087*f4ee7fbaSAndroid Build Coastguard Worker if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */
2088*f4ee7fbaSAndroid Build Coastguard Worker br->avail_in = *available_in;
2089*f4ee7fbaSAndroid Build Coastguard Worker br->next_in = *next_in;
2090*f4ee7fbaSAndroid Build Coastguard Worker } else {
2091*f4ee7fbaSAndroid Build Coastguard Worker /* At least one byte of input is required. More than one byte of input may
2092*f4ee7fbaSAndroid Build Coastguard Worker be required to complete the transaction -> reading more data must be
2093*f4ee7fbaSAndroid Build Coastguard Worker done in a loop -> do it in a main loop. */
2094*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2095*f4ee7fbaSAndroid Build Coastguard Worker br->next_in = &s->buffer.u8[0];
2096*f4ee7fbaSAndroid Build Coastguard Worker }
2097*f4ee7fbaSAndroid Build Coastguard Worker /* State machine */
2098*f4ee7fbaSAndroid Build Coastguard Worker for (;;) {
2099*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2100*f4ee7fbaSAndroid Build Coastguard Worker /* Error, needs more input/output. */
2101*f4ee7fbaSAndroid Build Coastguard Worker if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
2102*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer != 0) { /* Pro-actively push output. */
2103*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode intermediate_result = WriteRingBuffer(s,
2104*f4ee7fbaSAndroid Build Coastguard Worker available_out, next_out, total_out, BROTLI_TRUE);
2105*f4ee7fbaSAndroid Build Coastguard Worker /* WriteRingBuffer checks s->meta_block_remaining_len validity. */
2106*f4ee7fbaSAndroid Build Coastguard Worker if ((int)intermediate_result < 0) {
2107*f4ee7fbaSAndroid Build Coastguard Worker result = intermediate_result;
2108*f4ee7fbaSAndroid Build Coastguard Worker break;
2109*f4ee7fbaSAndroid Build Coastguard Worker }
2110*f4ee7fbaSAndroid Build Coastguard Worker }
2111*f4ee7fbaSAndroid Build Coastguard Worker if (s->buffer_length != 0) { /* Used with internal buffer. */
2112*f4ee7fbaSAndroid Build Coastguard Worker if (br->avail_in == 0) {
2113*f4ee7fbaSAndroid Build Coastguard Worker /* Successfully finished read transaction.
2114*f4ee7fbaSAndroid Build Coastguard Worker Accumulator contains less than 8 bits, because internal buffer
2115*f4ee7fbaSAndroid Build Coastguard Worker is expanded byte-by-byte until it is enough to complete read. */
2116*f4ee7fbaSAndroid Build Coastguard Worker s->buffer_length = 0;
2117*f4ee7fbaSAndroid Build Coastguard Worker /* Switch to input stream and restart. */
2118*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_SUCCESS;
2119*f4ee7fbaSAndroid Build Coastguard Worker br->avail_in = *available_in;
2120*f4ee7fbaSAndroid Build Coastguard Worker br->next_in = *next_in;
2121*f4ee7fbaSAndroid Build Coastguard Worker continue;
2122*f4ee7fbaSAndroid Build Coastguard Worker } else if (*available_in != 0) {
2123*f4ee7fbaSAndroid Build Coastguard Worker /* Not enough data in buffer, but can take one more byte from
2124*f4ee7fbaSAndroid Build Coastguard Worker input stream. */
2125*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_SUCCESS;
2126*f4ee7fbaSAndroid Build Coastguard Worker s->buffer.u8[s->buffer_length] = **next_in;
2127*f4ee7fbaSAndroid Build Coastguard Worker s->buffer_length++;
2128*f4ee7fbaSAndroid Build Coastguard Worker br->avail_in = s->buffer_length;
2129*f4ee7fbaSAndroid Build Coastguard Worker (*next_in)++;
2130*f4ee7fbaSAndroid Build Coastguard Worker (*available_in)--;
2131*f4ee7fbaSAndroid Build Coastguard Worker /* Retry with more data in buffer. */
2132*f4ee7fbaSAndroid Build Coastguard Worker continue;
2133*f4ee7fbaSAndroid Build Coastguard Worker }
2134*f4ee7fbaSAndroid Build Coastguard Worker /* Can't finish reading and no more input. */
2135*f4ee7fbaSAndroid Build Coastguard Worker break;
2136*f4ee7fbaSAndroid Build Coastguard Worker } else { /* Input stream doesn't contain enough input. */
2137*f4ee7fbaSAndroid Build Coastguard Worker /* Copy tail to internal buffer and return. */
2138*f4ee7fbaSAndroid Build Coastguard Worker *next_in = br->next_in;
2139*f4ee7fbaSAndroid Build Coastguard Worker *available_in = br->avail_in;
2140*f4ee7fbaSAndroid Build Coastguard Worker while (*available_in) {
2141*f4ee7fbaSAndroid Build Coastguard Worker s->buffer.u8[s->buffer_length] = **next_in;
2142*f4ee7fbaSAndroid Build Coastguard Worker s->buffer_length++;
2143*f4ee7fbaSAndroid Build Coastguard Worker (*next_in)++;
2144*f4ee7fbaSAndroid Build Coastguard Worker (*available_in)--;
2145*f4ee7fbaSAndroid Build Coastguard Worker }
2146*f4ee7fbaSAndroid Build Coastguard Worker break;
2147*f4ee7fbaSAndroid Build Coastguard Worker }
2148*f4ee7fbaSAndroid Build Coastguard Worker /* Unreachable. */
2149*f4ee7fbaSAndroid Build Coastguard Worker }
2150*f4ee7fbaSAndroid Build Coastguard Worker
2151*f4ee7fbaSAndroid Build Coastguard Worker /* Fail or needs more output. */
2152*f4ee7fbaSAndroid Build Coastguard Worker
2153*f4ee7fbaSAndroid Build Coastguard Worker if (s->buffer_length != 0) {
2154*f4ee7fbaSAndroid Build Coastguard Worker /* Just consumed the buffered input and produced some output. Otherwise
2155*f4ee7fbaSAndroid Build Coastguard Worker it would result in "needs more input". Reset internal buffer. */
2156*f4ee7fbaSAndroid Build Coastguard Worker s->buffer_length = 0;
2157*f4ee7fbaSAndroid Build Coastguard Worker } else {
2158*f4ee7fbaSAndroid Build Coastguard Worker /* Using input stream in last iteration. When decoder switches to input
2159*f4ee7fbaSAndroid Build Coastguard Worker stream it has less than 8 bits in accumulator, so it is safe to
2160*f4ee7fbaSAndroid Build Coastguard Worker return unused accumulator bits there. */
2161*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderUnload(br);
2162*f4ee7fbaSAndroid Build Coastguard Worker *available_in = br->avail_in;
2163*f4ee7fbaSAndroid Build Coastguard Worker *next_in = br->next_in;
2164*f4ee7fbaSAndroid Build Coastguard Worker }
2165*f4ee7fbaSAndroid Build Coastguard Worker break;
2166*f4ee7fbaSAndroid Build Coastguard Worker }
2167*f4ee7fbaSAndroid Build Coastguard Worker switch (s->state) {
2168*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_UNINITED:
2169*f4ee7fbaSAndroid Build Coastguard Worker /* Prepare to the first read. */
2170*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliWarmupBitReader(br)) {
2171*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2172*f4ee7fbaSAndroid Build Coastguard Worker break;
2173*f4ee7fbaSAndroid Build Coastguard Worker }
2174*f4ee7fbaSAndroid Build Coastguard Worker /* Decode window size. */
2175*f4ee7fbaSAndroid Build Coastguard Worker result = DecodeWindowBits(s, br); /* Reads 1..8 bits. */
2176*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2177*f4ee7fbaSAndroid Build Coastguard Worker break;
2178*f4ee7fbaSAndroid Build Coastguard Worker }
2179*f4ee7fbaSAndroid Build Coastguard Worker if (s->large_window) {
2180*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_LARGE_WINDOW_BITS;
2181*f4ee7fbaSAndroid Build Coastguard Worker break;
2182*f4ee7fbaSAndroid Build Coastguard Worker }
2183*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_INITIALIZE;
2184*f4ee7fbaSAndroid Build Coastguard Worker break;
2185*f4ee7fbaSAndroid Build Coastguard Worker
2186*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_LARGE_WINDOW_BITS:
2187*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 6, &s->window_bits)) {
2188*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2189*f4ee7fbaSAndroid Build Coastguard Worker break;
2190*f4ee7fbaSAndroid Build Coastguard Worker }
2191*f4ee7fbaSAndroid Build Coastguard Worker if (s->window_bits < BROTLI_LARGE_MIN_WBITS ||
2192*f4ee7fbaSAndroid Build Coastguard Worker s->window_bits > BROTLI_LARGE_MAX_WBITS) {
2193*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);
2194*f4ee7fbaSAndroid Build Coastguard Worker break;
2195*f4ee7fbaSAndroid Build Coastguard Worker }
2196*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_INITIALIZE;
2197*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2198*f4ee7fbaSAndroid Build Coastguard Worker
2199*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_INITIALIZE:
2200*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->window_bits);
2201*f4ee7fbaSAndroid Build Coastguard Worker /* Maximum distance, see section 9.1. of the spec. */
2202*f4ee7fbaSAndroid Build Coastguard Worker s->max_backward_distance = (1 << s->window_bits) - BROTLI_WINDOW_GAP;
2203*f4ee7fbaSAndroid Build Coastguard Worker
2204*f4ee7fbaSAndroid Build Coastguard Worker /* Allocate memory for both block_type_trees and block_len_trees. */
2205*f4ee7fbaSAndroid Build Coastguard Worker s->block_type_trees = (HuffmanCode*)BROTLI_DECODER_ALLOC(s,
2206*f4ee7fbaSAndroid Build Coastguard Worker sizeof(HuffmanCode) * 3 *
2207*f4ee7fbaSAndroid Build Coastguard Worker (BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26));
2208*f4ee7fbaSAndroid Build Coastguard Worker if (s->block_type_trees == 0) {
2209*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES);
2210*f4ee7fbaSAndroid Build Coastguard Worker break;
2211*f4ee7fbaSAndroid Build Coastguard Worker }
2212*f4ee7fbaSAndroid Build Coastguard Worker s->block_len_trees =
2213*f4ee7fbaSAndroid Build Coastguard Worker s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258;
2214*f4ee7fbaSAndroid Build Coastguard Worker
2215*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_BEGIN;
2216*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2217*f4ee7fbaSAndroid Build Coastguard Worker
2218*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_BEGIN:
2219*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderStateMetablockBegin(s);
2220*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->pos);
2221*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_HEADER;
2222*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2223*f4ee7fbaSAndroid Build Coastguard Worker
2224*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER:
2225*f4ee7fbaSAndroid Build Coastguard Worker result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */
2226*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2227*f4ee7fbaSAndroid Build Coastguard Worker break;
2228*f4ee7fbaSAndroid Build Coastguard Worker }
2229*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->is_last_metablock);
2230*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->meta_block_remaining_len);
2231*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->is_metadata);
2232*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->is_uncompressed);
2233*f4ee7fbaSAndroid Build Coastguard Worker if (s->is_metadata || s->is_uncompressed) {
2234*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliJumpToByteBoundary(br)) {
2235*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1);
2236*f4ee7fbaSAndroid Build Coastguard Worker break;
2237*f4ee7fbaSAndroid Build Coastguard Worker }
2238*f4ee7fbaSAndroid Build Coastguard Worker }
2239*f4ee7fbaSAndroid Build Coastguard Worker if (s->is_metadata) {
2240*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METADATA;
2241*f4ee7fbaSAndroid Build Coastguard Worker break;
2242*f4ee7fbaSAndroid Build Coastguard Worker }
2243*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len == 0) {
2244*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
2245*f4ee7fbaSAndroid Build Coastguard Worker break;
2246*f4ee7fbaSAndroid Build Coastguard Worker }
2247*f4ee7fbaSAndroid Build Coastguard Worker BrotliCalculateRingBufferSize(s);
2248*f4ee7fbaSAndroid Build Coastguard Worker if (s->is_uncompressed) {
2249*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_UNCOMPRESSED;
2250*f4ee7fbaSAndroid Build Coastguard Worker break;
2251*f4ee7fbaSAndroid Build Coastguard Worker }
2252*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER;
2253*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2254*f4ee7fbaSAndroid Build Coastguard Worker
2255*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_HEADER: {
2256*f4ee7fbaSAndroid Build Coastguard Worker BrotliMetablockHeaderArena* h = &s->arena.header;
2257*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = 0;
2258*f4ee7fbaSAndroid Build Coastguard Worker /* Initialize compressed metablock header arena. */
2259*f4ee7fbaSAndroid Build Coastguard Worker h->sub_loop_counter = 0;
2260*f4ee7fbaSAndroid Build Coastguard Worker /* Make small negative indexes addressable. */
2261*f4ee7fbaSAndroid Build Coastguard Worker h->symbol_lists =
2262*f4ee7fbaSAndroid Build Coastguard Worker &h->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1];
2263*f4ee7fbaSAndroid Build Coastguard Worker h->substate_huffman = BROTLI_STATE_HUFFMAN_NONE;
2264*f4ee7fbaSAndroid Build Coastguard Worker h->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;
2265*f4ee7fbaSAndroid Build Coastguard Worker h->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;
2266*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_HUFFMAN_CODE_0;
2267*f4ee7fbaSAndroid Build Coastguard Worker }
2268*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2269*f4ee7fbaSAndroid Build Coastguard Worker
2270*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_CODE_0:
2271*f4ee7fbaSAndroid Build Coastguard Worker if (s->loop_counter >= 3) {
2272*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_HEADER_2;
2273*f4ee7fbaSAndroid Build Coastguard Worker break;
2274*f4ee7fbaSAndroid Build Coastguard Worker }
2275*f4ee7fbaSAndroid Build Coastguard Worker /* Reads 1..11 bits. */
2276*f4ee7fbaSAndroid Build Coastguard Worker result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]);
2277*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2278*f4ee7fbaSAndroid Build Coastguard Worker break;
2279*f4ee7fbaSAndroid Build Coastguard Worker }
2280*f4ee7fbaSAndroid Build Coastguard Worker s->num_block_types[s->loop_counter]++;
2281*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]);
2282*f4ee7fbaSAndroid Build Coastguard Worker if (s->num_block_types[s->loop_counter] < 2) {
2283*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter++;
2284*f4ee7fbaSAndroid Build Coastguard Worker break;
2285*f4ee7fbaSAndroid Build Coastguard Worker }
2286*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_HUFFMAN_CODE_1;
2287*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2288*f4ee7fbaSAndroid Build Coastguard Worker
2289*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_CODE_1: {
2290*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size = s->num_block_types[s->loop_counter] + 2;
2291*f4ee7fbaSAndroid Build Coastguard Worker int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258;
2292*f4ee7fbaSAndroid Build Coastguard Worker result = ReadHuffmanCode(alphabet_size, alphabet_size,
2293*f4ee7fbaSAndroid Build Coastguard Worker &s->block_type_trees[tree_offset], NULL, s);
2294*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) break;
2295*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_HUFFMAN_CODE_2;
2296*f4ee7fbaSAndroid Build Coastguard Worker }
2297*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2298*f4ee7fbaSAndroid Build Coastguard Worker
2299*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_CODE_2: {
2300*f4ee7fbaSAndroid Build Coastguard Worker uint32_t alphabet_size = BROTLI_NUM_BLOCK_LEN_SYMBOLS;
2301*f4ee7fbaSAndroid Build Coastguard Worker int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
2302*f4ee7fbaSAndroid Build Coastguard Worker result = ReadHuffmanCode(alphabet_size, alphabet_size,
2303*f4ee7fbaSAndroid Build Coastguard Worker &s->block_len_trees[tree_offset], NULL, s);
2304*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) break;
2305*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_HUFFMAN_CODE_3;
2306*f4ee7fbaSAndroid Build Coastguard Worker }
2307*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2308*f4ee7fbaSAndroid Build Coastguard Worker
2309*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_HUFFMAN_CODE_3: {
2310*f4ee7fbaSAndroid Build Coastguard Worker int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;
2311*f4ee7fbaSAndroid Build Coastguard Worker if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter],
2312*f4ee7fbaSAndroid Build Coastguard Worker &s->block_len_trees[tree_offset], br)) {
2313*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2314*f4ee7fbaSAndroid Build Coastguard Worker break;
2315*f4ee7fbaSAndroid Build Coastguard Worker }
2316*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->block_length[s->loop_counter]);
2317*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter++;
2318*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_HUFFMAN_CODE_0;
2319*f4ee7fbaSAndroid Build Coastguard Worker break;
2320*f4ee7fbaSAndroid Build Coastguard Worker }
2321*f4ee7fbaSAndroid Build Coastguard Worker
2322*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_UNCOMPRESSED: {
2323*f4ee7fbaSAndroid Build Coastguard Worker result = CopyUncompressedBlockToOutput(
2324*f4ee7fbaSAndroid Build Coastguard Worker available_out, next_out, total_out, s);
2325*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2326*f4ee7fbaSAndroid Build Coastguard Worker break;
2327*f4ee7fbaSAndroid Build Coastguard Worker }
2328*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
2329*f4ee7fbaSAndroid Build Coastguard Worker break;
2330*f4ee7fbaSAndroid Build Coastguard Worker }
2331*f4ee7fbaSAndroid Build Coastguard Worker
2332*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METADATA:
2333*f4ee7fbaSAndroid Build Coastguard Worker for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {
2334*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
2335*f4ee7fbaSAndroid Build Coastguard Worker /* Read one byte and ignore it. */
2336*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 8, &bits)) {
2337*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2338*f4ee7fbaSAndroid Build Coastguard Worker break;
2339*f4ee7fbaSAndroid Build Coastguard Worker }
2340*f4ee7fbaSAndroid Build Coastguard Worker }
2341*f4ee7fbaSAndroid Build Coastguard Worker if (result == BROTLI_DECODER_SUCCESS) {
2342*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
2343*f4ee7fbaSAndroid Build Coastguard Worker }
2344*f4ee7fbaSAndroid Build Coastguard Worker break;
2345*f4ee7fbaSAndroid Build Coastguard Worker
2346*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_HEADER_2: {
2347*f4ee7fbaSAndroid Build Coastguard Worker uint32_t bits;
2348*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliSafeReadBits(br, 6, &bits)) {
2349*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_DECODER_NEEDS_MORE_INPUT;
2350*f4ee7fbaSAndroid Build Coastguard Worker break;
2351*f4ee7fbaSAndroid Build Coastguard Worker }
2352*f4ee7fbaSAndroid Build Coastguard Worker s->distance_postfix_bits = bits & BitMask(2);
2353*f4ee7fbaSAndroid Build Coastguard Worker bits >>= 2;
2354*f4ee7fbaSAndroid Build Coastguard Worker s->num_direct_distance_codes = bits << s->distance_postfix_bits;
2355*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->num_direct_distance_codes);
2356*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_LOG_UINT(s->distance_postfix_bits);
2357*f4ee7fbaSAndroid Build Coastguard Worker s->context_modes =
2358*f4ee7fbaSAndroid Build Coastguard Worker (uint8_t*)BROTLI_DECODER_ALLOC(s, (size_t)s->num_block_types[0]);
2359*f4ee7fbaSAndroid Build Coastguard Worker if (s->context_modes == 0) {
2360*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES);
2361*f4ee7fbaSAndroid Build Coastguard Worker break;
2362*f4ee7fbaSAndroid Build Coastguard Worker }
2363*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = 0;
2364*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_CONTEXT_MODES;
2365*f4ee7fbaSAndroid Build Coastguard Worker }
2366*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2367*f4ee7fbaSAndroid Build Coastguard Worker
2368*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MODES:
2369*f4ee7fbaSAndroid Build Coastguard Worker result = ReadContextModes(s);
2370*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2371*f4ee7fbaSAndroid Build Coastguard Worker break;
2372*f4ee7fbaSAndroid Build Coastguard Worker }
2373*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_CONTEXT_MAP_1;
2374*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2375*f4ee7fbaSAndroid Build Coastguard Worker
2376*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_1:
2377*f4ee7fbaSAndroid Build Coastguard Worker result = DecodeContextMap(
2378*f4ee7fbaSAndroid Build Coastguard Worker s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS,
2379*f4ee7fbaSAndroid Build Coastguard Worker &s->num_literal_htrees, &s->context_map, s);
2380*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2381*f4ee7fbaSAndroid Build Coastguard Worker break;
2382*f4ee7fbaSAndroid Build Coastguard Worker }
2383*f4ee7fbaSAndroid Build Coastguard Worker DetectTrivialLiteralBlockTypes(s);
2384*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_CONTEXT_MAP_2;
2385*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2386*f4ee7fbaSAndroid Build Coastguard Worker
2387*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_CONTEXT_MAP_2: {
2388*f4ee7fbaSAndroid Build Coastguard Worker uint32_t npostfix = s->distance_postfix_bits;
2389*f4ee7fbaSAndroid Build Coastguard Worker uint32_t ndirect = s->num_direct_distance_codes;
2390*f4ee7fbaSAndroid Build Coastguard Worker uint32_t distance_alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE(
2391*f4ee7fbaSAndroid Build Coastguard Worker npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS);
2392*f4ee7fbaSAndroid Build Coastguard Worker uint32_t distance_alphabet_size_limit = distance_alphabet_size_max;
2393*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL allocation_success = BROTLI_TRUE;
2394*f4ee7fbaSAndroid Build Coastguard Worker if (s->large_window) {
2395*f4ee7fbaSAndroid Build Coastguard Worker BrotliDistanceCodeLimit limit = BrotliCalculateDistanceCodeLimit(
2396*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_MAX_ALLOWED_DISTANCE, npostfix, ndirect);
2397*f4ee7fbaSAndroid Build Coastguard Worker distance_alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE(
2398*f4ee7fbaSAndroid Build Coastguard Worker npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS);
2399*f4ee7fbaSAndroid Build Coastguard Worker distance_alphabet_size_limit = limit.max_alphabet_size;
2400*f4ee7fbaSAndroid Build Coastguard Worker }
2401*f4ee7fbaSAndroid Build Coastguard Worker result = DecodeContextMap(
2402*f4ee7fbaSAndroid Build Coastguard Worker s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS,
2403*f4ee7fbaSAndroid Build Coastguard Worker &s->num_dist_htrees, &s->dist_context_map, s);
2404*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2405*f4ee7fbaSAndroid Build Coastguard Worker break;
2406*f4ee7fbaSAndroid Build Coastguard Worker }
2407*f4ee7fbaSAndroid Build Coastguard Worker allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
2408*f4ee7fbaSAndroid Build Coastguard Worker s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS,
2409*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_NUM_LITERAL_SYMBOLS, s->num_literal_htrees);
2410*f4ee7fbaSAndroid Build Coastguard Worker allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
2411*f4ee7fbaSAndroid Build Coastguard Worker s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS,
2412*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_NUM_COMMAND_SYMBOLS, s->num_block_types[1]);
2413*f4ee7fbaSAndroid Build Coastguard Worker allocation_success &= BrotliDecoderHuffmanTreeGroupInit(
2414*f4ee7fbaSAndroid Build Coastguard Worker s, &s->distance_hgroup, distance_alphabet_size_max,
2415*f4ee7fbaSAndroid Build Coastguard Worker distance_alphabet_size_limit, s->num_dist_htrees);
2416*f4ee7fbaSAndroid Build Coastguard Worker if (!allocation_success) {
2417*f4ee7fbaSAndroid Build Coastguard Worker return SaveErrorCode(s,
2418*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS));
2419*f4ee7fbaSAndroid Build Coastguard Worker }
2420*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter = 0;
2421*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_TREE_GROUP;
2422*f4ee7fbaSAndroid Build Coastguard Worker }
2423*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2424*f4ee7fbaSAndroid Build Coastguard Worker
2425*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_TREE_GROUP: {
2426*f4ee7fbaSAndroid Build Coastguard Worker HuffmanTreeGroup* hgroup = NULL;
2427*f4ee7fbaSAndroid Build Coastguard Worker switch (s->loop_counter) {
2428*f4ee7fbaSAndroid Build Coastguard Worker case 0: hgroup = &s->literal_hgroup; break;
2429*f4ee7fbaSAndroid Build Coastguard Worker case 1: hgroup = &s->insert_copy_hgroup; break;
2430*f4ee7fbaSAndroid Build Coastguard Worker case 2: hgroup = &s->distance_hgroup; break;
2431*f4ee7fbaSAndroid Build Coastguard Worker default: return SaveErrorCode(s, BROTLI_FAILURE(
2432*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DECODER_ERROR_UNREACHABLE));
2433*f4ee7fbaSAndroid Build Coastguard Worker }
2434*f4ee7fbaSAndroid Build Coastguard Worker result = HuffmanTreeGroupDecode(hgroup, s);
2435*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) break;
2436*f4ee7fbaSAndroid Build Coastguard Worker s->loop_counter++;
2437*f4ee7fbaSAndroid Build Coastguard Worker if (s->loop_counter < 3) {
2438*f4ee7fbaSAndroid Build Coastguard Worker break;
2439*f4ee7fbaSAndroid Build Coastguard Worker }
2440*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY;
2441*f4ee7fbaSAndroid Build Coastguard Worker }
2442*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2443*f4ee7fbaSAndroid Build Coastguard Worker
2444*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_BEFORE_COMPRESSED_METABLOCK_BODY:
2445*f4ee7fbaSAndroid Build Coastguard Worker PrepareLiteralDecoding(s);
2446*f4ee7fbaSAndroid Build Coastguard Worker s->dist_context_map_slice = s->dist_context_map;
2447*f4ee7fbaSAndroid Build Coastguard Worker s->htree_command = s->insert_copy_hgroup.htrees[0];
2448*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliEnsureRingBuffer(s)) {
2449*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2);
2450*f4ee7fbaSAndroid Build Coastguard Worker break;
2451*f4ee7fbaSAndroid Build Coastguard Worker }
2452*f4ee7fbaSAndroid Build Coastguard Worker CalculateDistanceLut(s);
2453*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_BEGIN;
2454*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2455*f4ee7fbaSAndroid Build Coastguard Worker
2456*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_BEGIN:
2457*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2458*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_INNER:
2459*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2460*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS:
2461*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2462*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_POST_WRAP_COPY:
2463*f4ee7fbaSAndroid Build Coastguard Worker result = ProcessCommands(s);
2464*f4ee7fbaSAndroid Build Coastguard Worker if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {
2465*f4ee7fbaSAndroid Build Coastguard Worker result = SafeProcessCommands(s);
2466*f4ee7fbaSAndroid Build Coastguard Worker }
2467*f4ee7fbaSAndroid Build Coastguard Worker break;
2468*f4ee7fbaSAndroid Build Coastguard Worker
2469*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_INNER_WRITE:
2470*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2471*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_POST_WRITE_1:
2472*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2473*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_COMMAND_POST_WRITE_2:
2474*f4ee7fbaSAndroid Build Coastguard Worker result = WriteRingBuffer(
2475*f4ee7fbaSAndroid Build Coastguard Worker s, available_out, next_out, total_out, BROTLI_FALSE);
2476*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2477*f4ee7fbaSAndroid Build Coastguard Worker break;
2478*f4ee7fbaSAndroid Build Coastguard Worker }
2479*f4ee7fbaSAndroid Build Coastguard Worker WrapRingBuffer(s);
2480*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer_size == 1 << s->window_bits) {
2481*f4ee7fbaSAndroid Build Coastguard Worker s->max_distance = s->max_backward_distance;
2482*f4ee7fbaSAndroid Build Coastguard Worker }
2483*f4ee7fbaSAndroid Build Coastguard Worker if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {
2484*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len == 0) {
2485*f4ee7fbaSAndroid Build Coastguard Worker /* Next metablock, if any. */
2486*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
2487*f4ee7fbaSAndroid Build Coastguard Worker } else {
2488*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_BEGIN;
2489*f4ee7fbaSAndroid Build Coastguard Worker }
2490*f4ee7fbaSAndroid Build Coastguard Worker break;
2491*f4ee7fbaSAndroid Build Coastguard Worker } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) {
2492*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;
2493*f4ee7fbaSAndroid Build Coastguard Worker } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */
2494*f4ee7fbaSAndroid Build Coastguard Worker if (s->loop_counter == 0) {
2495*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len == 0) {
2496*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_DONE;
2497*f4ee7fbaSAndroid Build Coastguard Worker } else {
2498*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;
2499*f4ee7fbaSAndroid Build Coastguard Worker }
2500*f4ee7fbaSAndroid Build Coastguard Worker break;
2501*f4ee7fbaSAndroid Build Coastguard Worker }
2502*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_COMMAND_INNER;
2503*f4ee7fbaSAndroid Build Coastguard Worker }
2504*f4ee7fbaSAndroid Build Coastguard Worker break;
2505*f4ee7fbaSAndroid Build Coastguard Worker
2506*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_METABLOCK_DONE:
2507*f4ee7fbaSAndroid Build Coastguard Worker if (s->meta_block_remaining_len < 0) {
2508*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2);
2509*f4ee7fbaSAndroid Build Coastguard Worker break;
2510*f4ee7fbaSAndroid Build Coastguard Worker }
2511*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderStateCleanupAfterMetablock(s);
2512*f4ee7fbaSAndroid Build Coastguard Worker if (!s->is_last_metablock) {
2513*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_METABLOCK_BEGIN;
2514*f4ee7fbaSAndroid Build Coastguard Worker break;
2515*f4ee7fbaSAndroid Build Coastguard Worker }
2516*f4ee7fbaSAndroid Build Coastguard Worker if (!BrotliJumpToByteBoundary(br)) {
2517*f4ee7fbaSAndroid Build Coastguard Worker result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2);
2518*f4ee7fbaSAndroid Build Coastguard Worker break;
2519*f4ee7fbaSAndroid Build Coastguard Worker }
2520*f4ee7fbaSAndroid Build Coastguard Worker if (s->buffer_length == 0) {
2521*f4ee7fbaSAndroid Build Coastguard Worker BrotliBitReaderUnload(br);
2522*f4ee7fbaSAndroid Build Coastguard Worker *available_in = br->avail_in;
2523*f4ee7fbaSAndroid Build Coastguard Worker *next_in = br->next_in;
2524*f4ee7fbaSAndroid Build Coastguard Worker }
2525*f4ee7fbaSAndroid Build Coastguard Worker s->state = BROTLI_STATE_DONE;
2526*f4ee7fbaSAndroid Build Coastguard Worker /* Fall through. */
2527*f4ee7fbaSAndroid Build Coastguard Worker
2528*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_STATE_DONE:
2529*f4ee7fbaSAndroid Build Coastguard Worker if (s->ringbuffer != 0) {
2530*f4ee7fbaSAndroid Build Coastguard Worker result = WriteRingBuffer(
2531*f4ee7fbaSAndroid Build Coastguard Worker s, available_out, next_out, total_out, BROTLI_TRUE);
2532*f4ee7fbaSAndroid Build Coastguard Worker if (result != BROTLI_DECODER_SUCCESS) {
2533*f4ee7fbaSAndroid Build Coastguard Worker break;
2534*f4ee7fbaSAndroid Build Coastguard Worker }
2535*f4ee7fbaSAndroid Build Coastguard Worker }
2536*f4ee7fbaSAndroid Build Coastguard Worker return SaveErrorCode(s, result);
2537*f4ee7fbaSAndroid Build Coastguard Worker }
2538*f4ee7fbaSAndroid Build Coastguard Worker }
2539*f4ee7fbaSAndroid Build Coastguard Worker return SaveErrorCode(s, result);
2540*f4ee7fbaSAndroid Build Coastguard Worker }
2541*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderHasMoreOutput(const BrotliDecoderState * s)2542*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) {
2543*f4ee7fbaSAndroid Build Coastguard Worker /* After unrecoverable error remaining output is considered nonsensical. */
2544*f4ee7fbaSAndroid Build Coastguard Worker if ((int)s->error_code < 0) {
2545*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_FALSE;
2546*f4ee7fbaSAndroid Build Coastguard Worker }
2547*f4ee7fbaSAndroid Build Coastguard Worker return TO_BROTLI_BOOL(
2548*f4ee7fbaSAndroid Build Coastguard Worker s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0);
2549*f4ee7fbaSAndroid Build Coastguard Worker }
2550*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderTakeOutput(BrotliDecoderState * s,size_t * size)2551*f4ee7fbaSAndroid Build Coastguard Worker const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState* s, size_t* size) {
2552*f4ee7fbaSAndroid Build Coastguard Worker uint8_t* result = 0;
2553*f4ee7fbaSAndroid Build Coastguard Worker size_t available_out = *size ? *size : 1u << 24;
2554*f4ee7fbaSAndroid Build Coastguard Worker size_t requested_out = available_out;
2555*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode status;
2556*f4ee7fbaSAndroid Build Coastguard Worker if ((s->ringbuffer == 0) || ((int)s->error_code < 0)) {
2557*f4ee7fbaSAndroid Build Coastguard Worker *size = 0;
2558*f4ee7fbaSAndroid Build Coastguard Worker return 0;
2559*f4ee7fbaSAndroid Build Coastguard Worker }
2560*f4ee7fbaSAndroid Build Coastguard Worker WrapRingBuffer(s);
2561*f4ee7fbaSAndroid Build Coastguard Worker status = WriteRingBuffer(s, &available_out, &result, 0, BROTLI_TRUE);
2562*f4ee7fbaSAndroid Build Coastguard Worker /* Either WriteRingBuffer returns those "success" codes... */
2563*f4ee7fbaSAndroid Build Coastguard Worker if (status == BROTLI_DECODER_SUCCESS ||
2564*f4ee7fbaSAndroid Build Coastguard Worker status == BROTLI_DECODER_NEEDS_MORE_OUTPUT) {
2565*f4ee7fbaSAndroid Build Coastguard Worker *size = requested_out - available_out;
2566*f4ee7fbaSAndroid Build Coastguard Worker } else {
2567*f4ee7fbaSAndroid Build Coastguard Worker /* ... or stream is broken. Normally this should be caught by
2568*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderDecompressStream, this is just a safeguard. */
2569*f4ee7fbaSAndroid Build Coastguard Worker if ((int)status < 0) SaveErrorCode(s, status);
2570*f4ee7fbaSAndroid Build Coastguard Worker *size = 0;
2571*f4ee7fbaSAndroid Build Coastguard Worker result = 0;
2572*f4ee7fbaSAndroid Build Coastguard Worker }
2573*f4ee7fbaSAndroid Build Coastguard Worker return result;
2574*f4ee7fbaSAndroid Build Coastguard Worker }
2575*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderIsUsed(const BrotliDecoderState * s)2576*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) {
2577*f4ee7fbaSAndroid Build Coastguard Worker return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED ||
2578*f4ee7fbaSAndroid Build Coastguard Worker BrotliGetAvailableBits(&s->br) != 0);
2579*f4ee7fbaSAndroid Build Coastguard Worker }
2580*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderIsFinished(const BrotliDecoderState * s)2581*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) {
2582*f4ee7fbaSAndroid Build Coastguard Worker return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE) &&
2583*f4ee7fbaSAndroid Build Coastguard Worker !BrotliDecoderHasMoreOutput(s);
2584*f4ee7fbaSAndroid Build Coastguard Worker }
2585*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderGetErrorCode(const BrotliDecoderState * s)2586*f4ee7fbaSAndroid Build Coastguard Worker BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) {
2587*f4ee7fbaSAndroid Build Coastguard Worker return (BrotliDecoderErrorCode)s->error_code;
2588*f4ee7fbaSAndroid Build Coastguard Worker }
2589*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderErrorString(BrotliDecoderErrorCode c)2590*f4ee7fbaSAndroid Build Coastguard Worker const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) {
2591*f4ee7fbaSAndroid Build Coastguard Worker switch (c) {
2592*f4ee7fbaSAndroid Build Coastguard Worker #define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \
2593*f4ee7fbaSAndroid Build Coastguard Worker case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;
2594*f4ee7fbaSAndroid Build Coastguard Worker #define BROTLI_NOTHING_
2595*f4ee7fbaSAndroid Build Coastguard Worker BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_, BROTLI_NOTHING_)
2596*f4ee7fbaSAndroid Build Coastguard Worker #undef BROTLI_ERROR_CODE_CASE_
2597*f4ee7fbaSAndroid Build Coastguard Worker #undef BROTLI_NOTHING_
2598*f4ee7fbaSAndroid Build Coastguard Worker default: return "INVALID";
2599*f4ee7fbaSAndroid Build Coastguard Worker }
2600*f4ee7fbaSAndroid Build Coastguard Worker }
2601*f4ee7fbaSAndroid Build Coastguard Worker
BrotliDecoderVersion()2602*f4ee7fbaSAndroid Build Coastguard Worker uint32_t BrotliDecoderVersion() {
2603*f4ee7fbaSAndroid Build Coastguard Worker return BROTLI_VERSION;
2604*f4ee7fbaSAndroid Build Coastguard Worker }
2605*f4ee7fbaSAndroid Build Coastguard Worker
2606*f4ee7fbaSAndroid Build Coastguard Worker #if defined(__cplusplus) || defined(c_plusplus)
2607*f4ee7fbaSAndroid Build Coastguard Worker } /* extern "C" */
2608*f4ee7fbaSAndroid Build Coastguard Worker #endif
2609