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