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