xref: /aosp_15_r20/external/brotli/c/dec/decode.c (revision f4ee7fba7774faf2a30f13154332c0a06550dbc4)
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, &copy_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