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