1 /* Copyright 2013 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 #include <brotli/decode.h>
9 #if defined(__ARM_NEON__)
13 //#include <stdlib.h> /* free, malloc */
14 //#include <string.h> /* memcpy, memset */
16 #include "../common/constants.h"
17 #include "../common/context.h"
18 #include "../common/dictionary.h"
19 #include "../common/platform.h"
20 #include "../common/transform.h"
21 #include "../common/version.h"
22 #include "./bit_reader.h"
23 #include "./huffman.h"
27 #if defined(__cplusplus) || defined(c_plusplus)
31 #define BROTLI_FAILURE(CODE) (BROTLI_DUMP(), CODE)
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]))
39 #define HUFFMAN_TABLE_BITS 8U
40 #define HUFFMAN_TABLE_MASK 0xFF
42 /* We need the slack region for the following reasons:
43 - doing up to two 16-byte copies for fast backward copying
44 - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */
45 static const uint32_t kRingBufferWriteAheadSlack
= 42;
47 static const uint8_t kCodeLengthCodeOrder
[BROTLI_CODE_LENGTH_CODES
] = {
48 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
51 /* Static prefix code for the complex code length code lengths. */
52 static const uint8_t kCodeLengthPrefixLength
[16] = {
53 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4,
56 static const uint8_t kCodeLengthPrefixValue
[16] = {
57 0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,
60 BROTLI_BOOL
BrotliDecoderSetParameter(
61 BrotliDecoderState
* state
, BrotliDecoderParameter p
, uint32_t value
) {
62 if (state
->state
!= BROTLI_STATE_UNINITED
) return BROTLI_FALSE
;
64 case BROTLI_DECODER_PARAM_DISABLE_RING_BUFFER_REALLOCATION
:
65 state
->canny_ringbuffer_allocation
= !!value
? 0 : 1;
68 case BROTLI_DECODER_PARAM_LARGE_WINDOW
:
69 state
->large_window
= TO_BROTLI_BOOL(!!value
);
72 default: return BROTLI_FALSE
;
76 BrotliDecoderState
* BrotliDecoderCreateInstance(
77 brotli_alloc_func alloc_func
, brotli_free_func free_func
, void* opaque
) {
78 BrotliDecoderState
* state
= 0;
79 if (!alloc_func
&& !free_func
) {
80 state
= (BrotliDecoderState
*)BrDummyMalloc(sizeof(BrotliDecoderState
));
81 } else if (alloc_func
&& free_func
) {
82 state
= (BrotliDecoderState
*)alloc_func(opaque
, sizeof(BrotliDecoderState
));
88 if (!BrotliDecoderStateInit(state
, alloc_func
, free_func
, opaque
)) {
90 if (!alloc_func
&& !free_func
) {
92 } else if (alloc_func
&& free_func
) {
93 free_func(opaque
, state
);
100 /* Deinitializes and frees BrotliDecoderState instance. */
101 void BrotliDecoderDestroyInstance(BrotliDecoderState
* state
) {
105 brotli_free_func free_func
= state
->free_func
;
106 void* opaque
= state
->memory_manager_opaque
;
107 BrotliDecoderStateCleanup(state
);
108 free_func(opaque
, state
);
112 /* Saves error code and converts it to BrotliDecoderResult. */
113 static BROTLI_NOINLINE BrotliDecoderResult
SaveErrorCode(
114 BrotliDecoderState
* s
, BrotliDecoderErrorCode e
) {
115 s
->error_code
= (int)e
;
117 case BROTLI_DECODER_SUCCESS
:
118 return BROTLI_DECODER_RESULT_SUCCESS
;
120 case BROTLI_DECODER_NEEDS_MORE_INPUT
:
121 return BROTLI_DECODER_RESULT_NEEDS_MORE_INPUT
;
123 case BROTLI_DECODER_NEEDS_MORE_OUTPUT
:
124 return BROTLI_DECODER_RESULT_NEEDS_MORE_OUTPUT
;
127 return BROTLI_DECODER_RESULT_ERROR
;
131 /* Decodes WBITS by reading 1 - 7 bits, or 0x11 for "Large Window Brotli".
132 Precondition: bit-reader accumulator has at least 8 bits. */
133 static BrotliDecoderErrorCode
DecodeWindowBits(BrotliDecoderState
* s
,
134 BrotliBitReader
* br
) {
136 BROTLI_BOOL large_window
= s
->large_window
;
137 s
->large_window
= BROTLI_FALSE
;
138 BrotliTakeBits(br
, 1, &n
);
141 return BROTLI_DECODER_SUCCESS
;
143 BrotliTakeBits(br
, 3, &n
);
145 s
->window_bits
= 17 + n
;
146 return BROTLI_DECODER_SUCCESS
;
148 BrotliTakeBits(br
, 3, &n
);
151 BrotliTakeBits(br
, 1, &n
);
153 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS
);
155 s
->large_window
= BROTLI_TRUE
;
156 return BROTLI_DECODER_SUCCESS
;
158 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS
);
162 s
->window_bits
= 8 + n
;
163 return BROTLI_DECODER_SUCCESS
;
166 return BROTLI_DECODER_SUCCESS
;
169 static BROTLI_INLINE
void memmove16(uint8_t* dst
, uint8_t* src
) {
170 #if defined(__ARM_NEON__)
171 vst1q_u8(dst
, vld1q_u8(src
));
174 memcpy(buffer
, src
, 16);
175 memcpy(dst
, buffer
, 16);
179 /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
180 static BROTLI_NOINLINE BrotliDecoderErrorCode
DecodeVarLenUint8(
181 BrotliDecoderState
* s
, BrotliBitReader
* br
, uint32_t* value
) {
183 switch (s
->substate_decode_uint8
) {
184 case BROTLI_STATE_DECODE_UINT8_NONE
:
185 if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br
, 1, &bits
))) {
186 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
190 return BROTLI_DECODER_SUCCESS
;
194 case BROTLI_STATE_DECODE_UINT8_SHORT
:
195 if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br
, 3, &bits
))) {
196 s
->substate_decode_uint8
= BROTLI_STATE_DECODE_UINT8_SHORT
;
197 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
201 s
->substate_decode_uint8
= BROTLI_STATE_DECODE_UINT8_NONE
;
202 return BROTLI_DECODER_SUCCESS
;
204 /* Use output value as a temporary storage. It MUST be persisted. */
208 case BROTLI_STATE_DECODE_UINT8_LONG
:
209 if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br
, *value
, &bits
))) {
210 s
->substate_decode_uint8
= BROTLI_STATE_DECODE_UINT8_LONG
;
211 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
213 *value
= (1U << *value
) + bits
;
214 s
->substate_decode_uint8
= BROTLI_STATE_DECODE_UINT8_NONE
;
215 return BROTLI_DECODER_SUCCESS
;
219 BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
223 /* Decodes a metablock length and flags by reading 2 - 31 bits. */
224 static BrotliDecoderErrorCode BROTLI_NOINLINE
DecodeMetaBlockLength(
225 BrotliDecoderState
* s
, BrotliBitReader
* br
) {
229 switch (s
->substate_metablock_header
) {
230 case BROTLI_STATE_METABLOCK_HEADER_NONE
:
231 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
232 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
234 s
->is_last_metablock
= bits
? 1 : 0;
235 s
->meta_block_remaining_len
= 0;
236 s
->is_uncompressed
= 0;
238 if (!s
->is_last_metablock
) {
239 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_NIBBLES
;
242 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_EMPTY
;
245 case BROTLI_STATE_METABLOCK_HEADER_EMPTY
:
246 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
247 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
250 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_NONE
;
251 return BROTLI_DECODER_SUCCESS
;
253 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_NIBBLES
;
256 case BROTLI_STATE_METABLOCK_HEADER_NIBBLES
:
257 if (!BrotliSafeReadBits(br
, 2, &bits
)) {
258 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
260 s
->size_nibbles
= (uint8_t)(bits
+ 4);
264 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_RESERVED
;
267 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_SIZE
;
270 case BROTLI_STATE_METABLOCK_HEADER_SIZE
:
272 for (; i
< (int)s
->size_nibbles
; ++i
) {
273 if (!BrotliSafeReadBits(br
, 4, &bits
)) {
275 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
277 if (i
+ 1 == s
->size_nibbles
&& s
->size_nibbles
> 4 && bits
== 0) {
278 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_NIBBLE
);
280 s
->meta_block_remaining_len
|= (int)(bits
<< (i
* 4));
282 s
->substate_metablock_header
=
283 BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED
;
286 case BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED
:
287 if (!s
->is_last_metablock
) {
288 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
289 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
291 s
->is_uncompressed
= bits
? 1 : 0;
293 ++s
->meta_block_remaining_len
;
294 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_NONE
;
295 return BROTLI_DECODER_SUCCESS
;
297 case BROTLI_STATE_METABLOCK_HEADER_RESERVED
:
298 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
299 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
302 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_RESERVED
);
304 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_BYTES
;
307 case BROTLI_STATE_METABLOCK_HEADER_BYTES
:
308 if (!BrotliSafeReadBits(br
, 2, &bits
)) {
309 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
312 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_NONE
;
313 return BROTLI_DECODER_SUCCESS
;
315 s
->size_nibbles
= (uint8_t)bits
;
316 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_METADATA
;
319 case BROTLI_STATE_METABLOCK_HEADER_METADATA
:
321 for (; i
< (int)s
->size_nibbles
; ++i
) {
322 if (!BrotliSafeReadBits(br
, 8, &bits
)) {
324 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
326 if (i
+ 1 == s
->size_nibbles
&& s
->size_nibbles
> 1 && bits
== 0) {
327 return BROTLI_FAILURE(
328 BROTLI_DECODER_ERROR_FORMAT_EXUBERANT_META_NIBBLE
);
330 s
->meta_block_remaining_len
|= (int)(bits
<< (i
* 8));
332 ++s
->meta_block_remaining_len
;
333 s
->substate_metablock_header
= BROTLI_STATE_METABLOCK_HEADER_NONE
;
334 return BROTLI_DECODER_SUCCESS
;
338 BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
343 /* Decodes the Huffman code.
344 This method doesn't read data from the bit reader, BUT drops the amount of
345 bits that correspond to the decoded symbol.
346 bits MUST contain at least 15 (BROTLI_HUFFMAN_MAX_CODE_LENGTH) valid bits. */
347 static BROTLI_INLINE
uint32_t DecodeSymbol(uint32_t bits
,
348 const HuffmanCode
* table
,
349 BrotliBitReader
* br
) {
350 table
+= bits
& HUFFMAN_TABLE_MASK
;
351 if (table
->bits
> HUFFMAN_TABLE_BITS
) {
352 uint32_t nbits
= table
->bits
- HUFFMAN_TABLE_BITS
;
353 BrotliDropBits(br
, HUFFMAN_TABLE_BITS
);
354 table
+= table
->value
;
355 table
+= (bits
>> HUFFMAN_TABLE_BITS
) & BitMask(nbits
);
357 BrotliDropBits(br
, table
->bits
);
361 /* Reads and decodes the next Huffman code from bit-stream.
362 This method peeks 16 bits of input and drops 0 - 15 of them. */
363 static BROTLI_INLINE
uint32_t ReadSymbol(const HuffmanCode
* table
,
364 BrotliBitReader
* br
) {
365 return DecodeSymbol(BrotliGet16BitsUnmasked(br
), table
, br
);
368 /* Same as DecodeSymbol, but it is known that there is less than 15 bits of
369 input are currently available. */
370 static BROTLI_NOINLINE BROTLI_BOOL
SafeDecodeSymbol(
371 const HuffmanCode
* table
, BrotliBitReader
* br
, uint32_t* result
) {
373 uint32_t available_bits
= BrotliGetAvailableBits(br
);
374 if (available_bits
== 0) {
375 if (table
->bits
== 0) {
376 *result
= table
->value
;
379 return BROTLI_FALSE
; /* No valid bits at all. */
381 val
= (uint32_t)BrotliGetBitsUnmasked(br
);
382 table
+= val
& HUFFMAN_TABLE_MASK
;
383 if (table
->bits
<= HUFFMAN_TABLE_BITS
) {
384 if (table
->bits
<= available_bits
) {
385 BrotliDropBits(br
, table
->bits
);
386 *result
= table
->value
;
389 return BROTLI_FALSE
; /* Not enough bits for the first level. */
392 if (available_bits
<= HUFFMAN_TABLE_BITS
) {
393 return BROTLI_FALSE
; /* Not enough bits to move to the second level. */
396 /* Speculatively drop HUFFMAN_TABLE_BITS. */
397 val
= (val
& BitMask(table
->bits
)) >> HUFFMAN_TABLE_BITS
;
398 available_bits
-= HUFFMAN_TABLE_BITS
;
399 table
+= table
->value
+ val
;
400 if (available_bits
< table
->bits
) {
401 return BROTLI_FALSE
; /* Not enough bits for the second level. */
404 BrotliDropBits(br
, HUFFMAN_TABLE_BITS
+ table
->bits
);
405 *result
= table
->value
;
409 static BROTLI_INLINE BROTLI_BOOL
SafeReadSymbol(
410 const HuffmanCode
* table
, BrotliBitReader
* br
, uint32_t* result
) {
412 if (BROTLI_PREDICT_TRUE(BrotliSafeGetBits(br
, 15, &val
))) {
413 *result
= DecodeSymbol(val
, table
, br
);
416 return SafeDecodeSymbol(table
, br
, result
);
419 /* Makes a look-up in first level Huffman table. Peeks 8 bits. */
420 static BROTLI_INLINE
void PreloadSymbol(int safe
,
421 const HuffmanCode
* table
,
428 table
+= BrotliGetBits(br
, HUFFMAN_TABLE_BITS
);
430 *value
= table
->value
;
433 /* Decodes the next Huffman code using data prepared by PreloadSymbol.
434 Reads 0 - 15 bits. Also peeks 8 following bits. */
435 static BROTLI_INLINE
uint32_t ReadPreloadedSymbol(const HuffmanCode
* table
,
439 uint32_t result
= *value
;
440 if (BROTLI_PREDICT_FALSE(*bits
> HUFFMAN_TABLE_BITS
)) {
441 uint32_t val
= BrotliGet16BitsUnmasked(br
);
442 const HuffmanCode
* ext
= table
+ (val
& HUFFMAN_TABLE_MASK
) + *value
;
443 uint32_t mask
= BitMask((*bits
- HUFFMAN_TABLE_BITS
));
444 BrotliDropBits(br
, HUFFMAN_TABLE_BITS
);
445 ext
+= (val
>> HUFFMAN_TABLE_BITS
) & mask
;
446 BrotliDropBits(br
, ext
->bits
);
449 BrotliDropBits(br
, *bits
);
451 PreloadSymbol(0, table
, br
, bits
, value
);
455 static BROTLI_INLINE
uint32_t Log2Floor(uint32_t x
) {
464 /* Reads (s->symbol + 1) symbols.
465 Totally 1..4 symbols are read, 1..11 bits each.
466 The list of symbols MUST NOT contain duplicates. */
467 static BrotliDecoderErrorCode
ReadSimpleHuffmanSymbols(
468 uint32_t alphabet_size
, uint32_t max_symbol
, BrotliDecoderState
* s
) {
469 /* max_bits == 1..11; symbol == 0..3; 1..44 bits will be read. */
470 BrotliBitReader
* br
= &s
->br
;
471 uint32_t max_bits
= Log2Floor(alphabet_size
- 1);
472 uint32_t i
= s
->sub_loop_counter
;
473 uint32_t num_symbols
= s
->symbol
;
474 while (i
<= num_symbols
) {
476 if (BROTLI_PREDICT_FALSE(!BrotliSafeReadBits(br
, max_bits
, &v
))) {
477 s
->sub_loop_counter
= i
;
478 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_SIMPLE_READ
;
479 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
481 if (v
>= max_symbol
) {
483 BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_ALPHABET
);
485 s
->symbols_lists_array
[i
] = (uint16_t)v
;
486 BROTLI_LOG_UINT(s
->symbols_lists_array
[i
]);
490 for (i
= 0; i
< num_symbols
; ++i
) {
492 for (; k
<= num_symbols
; ++k
) {
493 if (s
->symbols_lists_array
[i
] == s
->symbols_lists_array
[k
]) {
494 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_SIMPLE_HUFFMAN_SAME
);
499 return BROTLI_DECODER_SUCCESS
;
502 /* Process single decoded symbol code length:
503 A) reset the repeat variable
504 B) remember code length (if it is not 0)
505 C) extend corresponding index-chain
506 D) reduce the Huffman space
507 E) update the histogram */
508 static BROTLI_INLINE
void ProcessSingleCodeLength(uint32_t code_len
,
509 uint32_t* symbol
, uint32_t* repeat
, uint32_t* space
,
510 uint32_t* prev_code_len
, uint16_t* symbol_lists
,
511 uint16_t* code_length_histo
, int* next_symbol
) {
513 if (code_len
!= 0) { /* code_len == 1..15 */
514 symbol_lists
[next_symbol
[code_len
]] = (uint16_t)(*symbol
);
515 next_symbol
[code_len
] = (int)(*symbol
);
516 *prev_code_len
= code_len
;
517 *space
-= 32768U >> code_len
;
518 code_length_histo
[code_len
]++;
519 BROTLI_LOG(("[ReadHuffmanCode] code_length[%d] = %d\n",
520 (int)*symbol
, (int)code_len
));
525 /* Process repeated symbol code length.
526 A) Check if it is the extension of previous repeat sequence; if the decoded
527 value is not BROTLI_REPEAT_PREVIOUS_CODE_LENGTH, then it is a new
529 B) Update repeat variable
530 C) Check if operation is feasible (fits alphabet)
531 D) For each symbol do the same operations as in ProcessSingleCodeLength
533 PRECONDITION: code_len == BROTLI_REPEAT_PREVIOUS_CODE_LENGTH or
534 code_len == BROTLI_REPEAT_ZERO_CODE_LENGTH */
535 static BROTLI_INLINE
void ProcessRepeatedCodeLength(uint32_t code_len
,
536 uint32_t repeat_delta
, uint32_t alphabet_size
, uint32_t* symbol
,
537 uint32_t* repeat
, uint32_t* space
, uint32_t* prev_code_len
,
538 uint32_t* repeat_code_len
, uint16_t* symbol_lists
,
539 uint16_t* code_length_histo
, int* next_symbol
) {
541 uint32_t extra_bits
= 3; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */
542 uint32_t new_len
= 0; /* for BROTLI_REPEAT_ZERO_CODE_LENGTH */
543 if (code_len
== BROTLI_REPEAT_PREVIOUS_CODE_LENGTH
) {
544 new_len
= *prev_code_len
;
547 if (*repeat_code_len
!= new_len
) {
549 *repeat_code_len
= new_len
;
551 old_repeat
= *repeat
;
554 *repeat
<<= extra_bits
;
556 *repeat
+= repeat_delta
+ 3U;
557 repeat_delta
= *repeat
- old_repeat
;
558 if (*symbol
+ repeat_delta
> alphabet_size
) {
560 *symbol
= alphabet_size
;
564 BROTLI_LOG(("[ReadHuffmanCode] code_length[%d..%d] = %d\n",
565 (int)*symbol
, (int)(*symbol
+ repeat_delta
- 1), (int)*repeat_code_len
));
566 if (*repeat_code_len
!= 0) {
567 unsigned last
= *symbol
+ repeat_delta
;
568 int next
= next_symbol
[*repeat_code_len
];
570 symbol_lists
[next
] = (uint16_t)*symbol
;
572 } while (++(*symbol
) != last
);
573 next_symbol
[*repeat_code_len
] = next
;
574 *space
-= repeat_delta
<< (15 - *repeat_code_len
);
575 code_length_histo
[*repeat_code_len
] =
576 (uint16_t)(code_length_histo
[*repeat_code_len
] + repeat_delta
);
578 *symbol
+= repeat_delta
;
582 /* Reads and decodes symbol codelengths. */
583 static BrotliDecoderErrorCode
ReadSymbolCodeLengths(
584 uint32_t alphabet_size
, BrotliDecoderState
* s
) {
585 BrotliBitReader
* br
= &s
->br
;
586 uint32_t symbol
= s
->symbol
;
587 uint32_t repeat
= s
->repeat
;
588 uint32_t space
= s
->space
;
589 uint32_t prev_code_len
= s
->prev_code_len
;
590 uint32_t repeat_code_len
= s
->repeat_code_len
;
591 uint16_t* symbol_lists
= s
->symbol_lists
;
592 uint16_t* code_length_histo
= s
->code_length_histo
;
593 int* next_symbol
= s
->next_symbol
;
594 if (!BrotliWarmupBitReader(br
)) {
595 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
597 while (symbol
< alphabet_size
&& space
> 0) {
598 const HuffmanCode
* p
= s
->table
;
600 if (!BrotliCheckInputAmount(br
, BROTLI_SHORT_FILL_BIT_WINDOW_READ
)) {
603 s
->prev_code_len
= prev_code_len
;
604 s
->repeat_code_len
= repeat_code_len
;
606 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
608 BrotliFillBitWindow16(br
);
609 p
+= BrotliGetBitsUnmasked(br
) &
610 BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
);
611 BrotliDropBits(br
, p
->bits
); /* Use 1..5 bits. */
612 code_len
= p
->value
; /* code_len == 0..17 */
613 if (code_len
< BROTLI_REPEAT_PREVIOUS_CODE_LENGTH
) {
614 ProcessSingleCodeLength(code_len
, &symbol
, &repeat
, &space
,
615 &prev_code_len
, symbol_lists
, code_length_histo
, next_symbol
);
616 } else { /* code_len == 16..17, extra_bits == 2..3 */
617 uint32_t extra_bits
=
618 (code_len
== BROTLI_REPEAT_PREVIOUS_CODE_LENGTH
) ? 2 : 3;
619 uint32_t repeat_delta
=
620 (uint32_t)BrotliGetBitsUnmasked(br
) & BitMask(extra_bits
);
621 BrotliDropBits(br
, extra_bits
);
622 ProcessRepeatedCodeLength(code_len
, repeat_delta
, alphabet_size
,
623 &symbol
, &repeat
, &space
, &prev_code_len
, &repeat_code_len
,
624 symbol_lists
, code_length_histo
, next_symbol
);
628 return BROTLI_DECODER_SUCCESS
;
631 static BrotliDecoderErrorCode
SafeReadSymbolCodeLengths(
632 uint32_t alphabet_size
, BrotliDecoderState
* s
) {
633 BrotliBitReader
* br
= &s
->br
;
634 BROTLI_BOOL get_byte
= BROTLI_FALSE
;
635 while (s
->symbol
< alphabet_size
&& s
->space
> 0) {
636 const HuffmanCode
* p
= s
->table
;
638 uint32_t available_bits
;
640 if (get_byte
&& !BrotliPullByte(br
)) return BROTLI_DECODER_NEEDS_MORE_INPUT
;
641 get_byte
= BROTLI_FALSE
;
642 available_bits
= BrotliGetAvailableBits(br
);
643 if (available_bits
!= 0) {
644 bits
= (uint32_t)BrotliGetBitsUnmasked(br
);
646 p
+= bits
& BitMask(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
);
647 if (p
->bits
> available_bits
) {
648 get_byte
= BROTLI_TRUE
;
651 code_len
= p
->value
; /* code_len == 0..17 */
652 if (code_len
< BROTLI_REPEAT_PREVIOUS_CODE_LENGTH
) {
653 BrotliDropBits(br
, p
->bits
);
654 ProcessSingleCodeLength(code_len
, &s
->symbol
, &s
->repeat
, &s
->space
,
655 &s
->prev_code_len
, s
->symbol_lists
, s
->code_length_histo
,
657 } else { /* code_len == 16..17, extra_bits == 2..3 */
658 uint32_t extra_bits
= code_len
- 14U;
659 uint32_t repeat_delta
= (bits
>> p
->bits
) & BitMask(extra_bits
);
660 if (available_bits
< p
->bits
+ extra_bits
) {
661 get_byte
= BROTLI_TRUE
;
664 BrotliDropBits(br
, p
->bits
+ extra_bits
);
665 ProcessRepeatedCodeLength(code_len
, repeat_delta
, alphabet_size
,
666 &s
->symbol
, &s
->repeat
, &s
->space
, &s
->prev_code_len
,
667 &s
->repeat_code_len
, s
->symbol_lists
, s
->code_length_histo
,
671 return BROTLI_DECODER_SUCCESS
;
674 /* Reads and decodes 15..18 codes using static prefix code.
675 Each code is 2..4 bits long. In total 30..72 bits are used. */
676 static BrotliDecoderErrorCode
ReadCodeLengthCodeLengths(BrotliDecoderState
* s
) {
677 BrotliBitReader
* br
= &s
->br
;
678 uint32_t num_codes
= s
->repeat
;
679 unsigned space
= s
->space
;
680 uint32_t i
= s
->sub_loop_counter
;
681 for (; i
< BROTLI_CODE_LENGTH_CODES
; ++i
) {
682 const uint8_t code_len_idx
= kCodeLengthCodeOrder
[i
];
685 if (BROTLI_PREDICT_FALSE(!BrotliSafeGetBits(br
, 4, &ix
))) {
686 uint32_t available_bits
= BrotliGetAvailableBits(br
);
687 if (available_bits
!= 0) {
688 ix
= BrotliGetBitsUnmasked(br
) & 0xF;
692 if (kCodeLengthPrefixLength
[ix
] > available_bits
) {
693 s
->sub_loop_counter
= i
;
694 s
->repeat
= num_codes
;
696 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_COMPLEX
;
697 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
700 v
= kCodeLengthPrefixValue
[ix
];
701 BrotliDropBits(br
, kCodeLengthPrefixLength
[ix
]);
702 s
->code_length_code_lengths
[code_len_idx
] = (uint8_t)v
;
703 BROTLI_LOG_ARRAY_INDEX(s
->code_length_code_lengths
, code_len_idx
);
705 space
= space
- (32U >> v
);
707 ++s
->code_length_histo
[v
];
708 if (space
- 1U >= 32U) {
709 /* space is 0 or wrapped around. */
714 if (!(num_codes
== 1 || space
== 0)) {
715 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CL_SPACE
);
717 return BROTLI_DECODER_SUCCESS
;
720 /* Decodes the Huffman tables.
721 There are 2 scenarios:
722 A) Huffman code contains only few symbols (1..4). Those symbols are read
723 directly; their code lengths are defined by the number of symbols.
724 For this scenario 4 - 49 bits will be read.
727 B.1) Small Huffman table is decoded; it is specified with code lengths
728 encoded with predefined entropy code. 32 - 74 bits are used.
729 B.2) Decoded table is used to decode code lengths of symbols in resulting
730 Huffman table. In worst case 3520 bits are read. */
731 static BrotliDecoderErrorCode
ReadHuffmanCode(uint32_t alphabet_size
,
734 uint32_t* opt_table_size
,
735 BrotliDecoderState
* s
) {
736 BrotliBitReader
* br
= &s
->br
;
737 /* Unnecessary masking, but might be good for safety. */
738 alphabet_size
&= 0x7FF;
741 switch (s
->substate_huffman
) {
742 case BROTLI_STATE_HUFFMAN_NONE
:
743 if (!BrotliSafeReadBits(br
, 2, &s
->sub_loop_counter
)) {
744 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
746 BROTLI_LOG_UINT(s
->sub_loop_counter
);
747 /* The value is used as follows:
749 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
750 if (s
->sub_loop_counter
!= 1) {
752 s
->repeat
= 0; /* num_codes */
753 memset(&s
->code_length_histo
[0], 0, sizeof(s
->code_length_histo
[0]) *
754 (BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
+ 1));
755 memset(&s
->code_length_code_lengths
[0], 0,
756 sizeof(s
->code_length_code_lengths
));
757 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_COMPLEX
;
762 case BROTLI_STATE_HUFFMAN_SIMPLE_SIZE
:
763 /* Read symbols, codes & code lengths directly. */
764 if (!BrotliSafeReadBits(br
, 2, &s
->symbol
)) { /* num_symbols */
765 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_SIMPLE_SIZE
;
766 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
768 s
->sub_loop_counter
= 0;
771 case BROTLI_STATE_HUFFMAN_SIMPLE_READ
: {
772 BrotliDecoderErrorCode result
=
773 ReadSimpleHuffmanSymbols(alphabet_size
, max_symbol
, s
);
774 if (result
!= BROTLI_DECODER_SUCCESS
) {
780 case BROTLI_STATE_HUFFMAN_SIMPLE_BUILD
: {
782 if (s
->symbol
== 3) {
784 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
785 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_SIMPLE_BUILD
;
786 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
790 BROTLI_LOG_UINT(s
->symbol
);
791 table_size
= BrotliBuildSimpleHuffmanTable(
792 table
, HUFFMAN_TABLE_BITS
, s
->symbols_lists_array
, s
->symbol
);
793 if (opt_table_size
) {
794 *opt_table_size
= table_size
;
796 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_NONE
;
797 return BROTLI_DECODER_SUCCESS
;
800 /* Decode Huffman-coded code lengths. */
801 case BROTLI_STATE_HUFFMAN_COMPLEX
: {
803 BrotliDecoderErrorCode result
= ReadCodeLengthCodeLengths(s
);
804 if (result
!= BROTLI_DECODER_SUCCESS
) {
807 BrotliBuildCodeLengthsHuffmanTable(s
->table
,
808 s
->code_length_code_lengths
,
809 s
->code_length_histo
);
810 memset(&s
->code_length_histo
[0], 0, sizeof(s
->code_length_histo
));
811 for (i
= 0; i
<= BROTLI_HUFFMAN_MAX_CODE_LENGTH
; ++i
) {
812 s
->next_symbol
[i
] = (int)i
- (BROTLI_HUFFMAN_MAX_CODE_LENGTH
+ 1);
813 s
->symbol_lists
[s
->next_symbol
[i
]] = 0xFFFF;
817 s
->prev_code_len
= BROTLI_INITIAL_REPEATED_CODE_LENGTH
;
819 s
->repeat_code_len
= 0;
821 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS
;
825 case BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS
: {
827 BrotliDecoderErrorCode result
= ReadSymbolCodeLengths(max_symbol
, s
);
828 if (result
== BROTLI_DECODER_NEEDS_MORE_INPUT
) {
829 result
= SafeReadSymbolCodeLengths(max_symbol
, s
);
831 if (result
!= BROTLI_DECODER_SUCCESS
) {
836 BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", (int)s
->space
));
837 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_HUFFMAN_SPACE
);
839 table_size
= BrotliBuildHuffmanTable(
840 table
, HUFFMAN_TABLE_BITS
, s
->symbol_lists
, s
->code_length_histo
);
841 if (opt_table_size
) {
842 *opt_table_size
= table_size
;
844 s
->substate_huffman
= BROTLI_STATE_HUFFMAN_NONE
;
845 return BROTLI_DECODER_SUCCESS
;
850 BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
855 /* Decodes a block length by reading 3..39 bits. */
856 static BROTLI_INLINE
uint32_t ReadBlockLength(const HuffmanCode
* table
,
857 BrotliBitReader
* br
) {
860 code
= ReadSymbol(table
, br
);
861 ASSERT (code
< BROTLI_NUM_BLOCK_LEN_SYMBOLS
);
862 nbits
= kBlockLengthPrefixCode
[code
].nbits
; /* nbits == 2..24 */
863 return kBlockLengthPrefixCode
[code
].offset
+ BrotliReadBits(br
, nbits
);
866 /* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then
867 reading can't be continued with ReadBlockLength. */
868 static BROTLI_INLINE BROTLI_BOOL
SafeReadBlockLength(
869 BrotliDecoderState
* s
, uint32_t* result
, const HuffmanCode
* table
,
870 BrotliBitReader
* br
) {
872 if (s
->substate_read_block_length
== BROTLI_STATE_READ_BLOCK_LENGTH_NONE
) {
873 if (!SafeReadSymbol(table
, br
, &index
)) {
877 index
= s
->block_length_index
;
881 uint32_t nbits
= kBlockLengthPrefixCode
[index
].nbits
; /* nbits == 2..24 */
882 if (!BrotliSafeReadBits(br
, nbits
, &bits
)) {
883 s
->block_length_index
= index
;
884 s
->substate_read_block_length
= BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
;
887 *result
= kBlockLengthPrefixCode
[index
].offset
+ bits
;
888 s
->substate_read_block_length
= BROTLI_STATE_READ_BLOCK_LENGTH_NONE
;
894 1) initialize list L with values 0, 1,... 255
895 2) For each input element X:
897 2.2) remove X-th element from L
899 2.4) append Y to output
901 In most cases max(Y) <= 7, so most of L remains intact.
902 To reduce the cost of initialization, we reuse L, remember the upper bound
903 of Y values, and reinitialize only first elements in L.
905 Most of input values are 0 and 1. To reduce number of branches, we replace
906 inner for loop with do-while. */
907 static BROTLI_NOINLINE
void InverseMoveToFrontTransform(
908 uint8_t* v
, uint32_t v_len
, BrotliDecoderState
* state
) {
909 /* Reinitialize elements that could have been changed. */
911 uint32_t upper_bound
= state
->mtf_upper_bound
;
912 uint32_t* mtf
= &state
->mtf
[1]; /* Make mtf[-1] addressable. */
913 uint8_t* mtf_u8
= (uint8_t*)mtf
;
914 uint8_t* mtf_u8t
= mtf_u8
- 1;
915 /* Load endian-aware constant. */
916 const uint8_t b0123
[4] = {0, 1, 2, 3};
918 memcpy(&pattern
, &b0123
, 4);
920 /* Initialize list using 4 consequent values pattern. */
923 pattern
+= 0x04040404; /* Advance all 4 values by 4. */
926 } while (i
<= upper_bound
);
928 /* Transform the input. */
930 for (i
= 0; i
< v_len
; ++i
) {
932 uint8_t value
= mtf_u8
[index
];
933 upper_bound
|= (uint32_t) v
[i
];
937 mtf_u8t
[index
+ 1] = mtf_u8t
[index
];
941 /* Remember amount of elements to be reinitialized. */
942 state
->mtf_upper_bound
= upper_bound
>> 2;
945 /* Decodes a series of Huffman table using ReadHuffmanCode function. */
946 static BrotliDecoderErrorCode
HuffmanTreeGroupDecode(
947 HuffmanTreeGroup
* group
, BrotliDecoderState
* s
) {
948 if (s
->substate_tree_group
!= BROTLI_STATE_TREE_GROUP_LOOP
) {
949 s
->next
= group
->codes
;
951 s
->substate_tree_group
= BROTLI_STATE_TREE_GROUP_LOOP
;
953 while (s
->htree_index
< group
->num_htrees
) {
955 BrotliDecoderErrorCode result
=
956 ReadHuffmanCode(group
->alphabet_size
, group
->max_symbol
,
957 s
->next
, &table_size
, s
);
958 if (result
!= BROTLI_DECODER_SUCCESS
) return result
;
959 group
->htrees
[s
->htree_index
] = s
->next
;
960 s
->next
+= table_size
;
963 s
->substate_tree_group
= BROTLI_STATE_TREE_GROUP_NONE
;
964 return BROTLI_DECODER_SUCCESS
;
967 /* Decodes a context map.
968 Decoding is done in 4 phases:
969 1) Read auxiliary information (6..16 bits) and allocate memory.
970 In case of trivial context map, decoding is finished at this phase.
971 2) Decode Huffman table using ReadHuffmanCode function.
972 This table will be used for reading context map items.
973 3) Read context map items; "0" values could be run-length encoded.
974 4) Optionally, apply InverseMoveToFront transform to the resulting map. */
975 static BrotliDecoderErrorCode
DecodeContextMap(uint32_t context_map_size
,
976 uint32_t* num_htrees
,
977 uint8_t** context_map_arg
,
978 BrotliDecoderState
* s
) {
979 BrotliBitReader
* br
= &s
->br
;
980 BrotliDecoderErrorCode result
= BROTLI_DECODER_SUCCESS
;
982 switch ((int)s
->substate_context_map
) {
983 case BROTLI_STATE_CONTEXT_MAP_NONE
:
984 result
= DecodeVarLenUint8(s
, br
, num_htrees
);
985 if (result
!= BROTLI_DECODER_SUCCESS
) {
989 s
->context_index
= 0;
990 BROTLI_LOG_UINT(context_map_size
);
991 BROTLI_LOG_UINT(*num_htrees
);
993 (uint8_t*)BROTLI_DECODER_ALLOC(s
, (size_t)context_map_size
);
994 if (*context_map_arg
== 0) {
995 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP
);
997 if (*num_htrees
<= 1) {
998 memset(*context_map_arg
, 0, (size_t)context_map_size
);
999 return BROTLI_DECODER_SUCCESS
;
1001 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_READ_PREFIX
;
1004 case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX
: {
1006 /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe
1007 to peek 4 bits ahead. */
1008 if (!BrotliSafeGetBits(br
, 5, &bits
)) {
1009 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1011 if ((bits
& 1) != 0) { /* Use RLE for zeros. */
1012 s
->max_run_length_prefix
= (bits
>> 1) + 1;
1013 BrotliDropBits(br
, 5);
1015 s
->max_run_length_prefix
= 0;
1016 BrotliDropBits(br
, 1);
1018 BROTLI_LOG_UINT(s
->max_run_length_prefix
);
1019 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_HUFFMAN
;
1023 case BROTLI_STATE_CONTEXT_MAP_HUFFMAN
: {
1024 uint32_t alphabet_size
= *num_htrees
+ s
->max_run_length_prefix
;
1025 result
= ReadHuffmanCode(alphabet_size
, alphabet_size
,
1026 s
->context_map_table
, NULL
, s
);
1027 if (result
!= BROTLI_DECODER_SUCCESS
) return result
;
1029 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_DECODE
;
1033 case BROTLI_STATE_CONTEXT_MAP_DECODE
: {
1034 uint32_t context_index
= s
->context_index
;
1035 uint32_t max_run_length_prefix
= s
->max_run_length_prefix
;
1036 uint8_t* context_map
= *context_map_arg
;
1037 uint32_t code
= s
->code
;
1038 BROTLI_BOOL skip_preamble
= (code
!= 0xFFFF);
1039 while (context_index
< context_map_size
|| skip_preamble
) {
1040 if (!skip_preamble
) {
1041 if (!SafeReadSymbol(s
->context_map_table
, br
, &code
)) {
1043 s
->context_index
= context_index
;
1044 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1046 BROTLI_LOG_UINT(code
);
1049 context_map
[context_index
++] = 0;
1052 if (code
> max_run_length_prefix
) {
1053 context_map
[context_index
++] =
1054 (uint8_t)(code
- max_run_length_prefix
);
1058 skip_preamble
= BROTLI_FALSE
;
1060 /* RLE sub-stage. */
1063 if (!BrotliSafeReadBits(br
, code
, &reps
)) {
1065 s
->context_index
= context_index
;
1066 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1069 BROTLI_LOG_UINT(reps
);
1070 if (context_index
+ reps
> context_map_size
) {
1072 BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT
);
1075 context_map
[context_index
++] = 0;
1082 case BROTLI_STATE_CONTEXT_MAP_TRANSFORM
: {
1084 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
1085 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_TRANSFORM
;
1086 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1089 InverseMoveToFrontTransform(*context_map_arg
, context_map_size
, s
);
1091 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_NONE
;
1092 return BROTLI_DECODER_SUCCESS
;
1097 BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
1101 /* Decodes a command or literal and updates block type ring-buffer.
1102 Reads 3..54 bits. */
1103 static BROTLI_INLINE BROTLI_BOOL
DecodeBlockTypeAndLength(
1104 int safe
, BrotliDecoderState
* s
, int tree_type
) {
1105 uint32_t max_block_type
= s
->num_block_types
[tree_type
];
1106 const HuffmanCode
* type_tree
= &s
->block_type_trees
[
1107 tree_type
* BROTLI_HUFFMAN_MAX_SIZE_258
];
1108 const HuffmanCode
* len_tree
= &s
->block_len_trees
[
1109 tree_type
* BROTLI_HUFFMAN_MAX_SIZE_26
];
1110 BrotliBitReader
* br
= &s
->br
;
1111 uint32_t* ringbuffer
= &s
->block_type_rb
[tree_type
* 2];
1112 uint32_t block_type
;
1113 if (max_block_type
<= 1) {
1114 return BROTLI_FALSE
;
1117 /* Read 0..15 + 3..39 bits. */
1119 block_type
= ReadSymbol(type_tree
, br
);
1120 s
->block_length
[tree_type
] = ReadBlockLength(len_tree
, br
);
1122 BrotliBitReaderState memento
;
1123 BrotliBitReaderSaveState(br
, &memento
);
1124 if (!SafeReadSymbol(type_tree
, br
, &block_type
)) return BROTLI_FALSE
;
1125 if (!SafeReadBlockLength(s
, &s
->block_length
[tree_type
], len_tree
, br
)) {
1126 s
->substate_read_block_length
= BROTLI_STATE_READ_BLOCK_LENGTH_NONE
;
1127 BrotliBitReaderRestoreState(br
, &memento
);
1128 return BROTLI_FALSE
;
1132 if (block_type
== 1) {
1133 block_type
= ringbuffer
[1] + 1;
1134 } else if (block_type
== 0) {
1135 block_type
= ringbuffer
[0];
1139 if (block_type
>= max_block_type
) {
1140 block_type
-= max_block_type
;
1142 ringbuffer
[0] = ringbuffer
[1];
1143 ringbuffer
[1] = block_type
;
1147 static BROTLI_INLINE
void DetectTrivialLiteralBlockTypes(
1148 BrotliDecoderState
* s
) {
1150 for (i
= 0; i
< 8; ++i
) s
->trivial_literal_contexts
[i
] = 0;
1151 for (i
= 0; i
< s
->num_block_types
[0]; i
++) {
1152 size_t offset
= i
<< BROTLI_LITERAL_CONTEXT_BITS
;
1154 size_t sample
= s
->context_map
[offset
];
1156 for (j
= 0; j
< (1u << BROTLI_LITERAL_CONTEXT_BITS
);) {
1157 BROTLI_REPEAT(4, error
|= s
->context_map
[offset
+ j
++] ^ sample
;)
1160 s
->trivial_literal_contexts
[i
>> 5] |= 1u << (i
& 31);
1165 static BROTLI_INLINE
void PrepareLiteralDecoding(BrotliDecoderState
* s
) {
1166 uint8_t context_mode
;
1168 uint32_t block_type
= s
->block_type_rb
[1];
1169 uint32_t context_offset
= block_type
<< BROTLI_LITERAL_CONTEXT_BITS
;
1170 s
->context_map_slice
= s
->context_map
+ context_offset
;
1171 trivial
= s
->trivial_literal_contexts
[block_type
>> 5];
1172 s
->trivial_literal_context
= (trivial
>> (block_type
& 31)) & 1;
1173 s
->literal_htree
= s
->literal_hgroup
.htrees
[s
->context_map_slice
[0]];
1174 context_mode
= s
->context_modes
[block_type
] & 3;
1175 s
->context_lookup
= BROTLI_CONTEXT_LUT(context_mode
);
1178 /* Decodes the block type and updates the state for literal context.
1179 Reads 3..54 bits. */
1180 static BROTLI_INLINE BROTLI_BOOL
DecodeLiteralBlockSwitchInternal(
1181 int safe
, BrotliDecoderState
* s
) {
1182 if (!DecodeBlockTypeAndLength(safe
, s
, 0)) {
1183 return BROTLI_FALSE
;
1185 PrepareLiteralDecoding(s
);
1189 static void BROTLI_NOINLINE
DecodeLiteralBlockSwitch(BrotliDecoderState
* s
) {
1190 DecodeLiteralBlockSwitchInternal(0, s
);
1193 static BROTLI_BOOL BROTLI_NOINLINE
SafeDecodeLiteralBlockSwitch(
1194 BrotliDecoderState
* s
) {
1195 return DecodeLiteralBlockSwitchInternal(1, s
);
1198 /* Block switch for insert/copy length.
1199 Reads 3..54 bits. */
1200 static BROTLI_INLINE BROTLI_BOOL
DecodeCommandBlockSwitchInternal(
1201 int safe
, BrotliDecoderState
* s
) {
1202 if (!DecodeBlockTypeAndLength(safe
, s
, 1)) {
1203 return BROTLI_FALSE
;
1205 s
->htree_command
= s
->insert_copy_hgroup
.htrees
[s
->block_type_rb
[3]];
1209 static void BROTLI_NOINLINE
DecodeCommandBlockSwitch(BrotliDecoderState
* s
) {
1210 DecodeCommandBlockSwitchInternal(0, s
);
1213 static BROTLI_BOOL BROTLI_NOINLINE
SafeDecodeCommandBlockSwitch(
1214 BrotliDecoderState
* s
) {
1215 return DecodeCommandBlockSwitchInternal(1, s
);
1218 /* Block switch for distance codes.
1219 Reads 3..54 bits. */
1220 static BROTLI_INLINE BROTLI_BOOL
DecodeDistanceBlockSwitchInternal(
1221 int safe
, BrotliDecoderState
* s
) {
1222 if (!DecodeBlockTypeAndLength(safe
, s
, 2)) {
1223 return BROTLI_FALSE
;
1225 s
->dist_context_map_slice
= s
->dist_context_map
+
1226 (s
->block_type_rb
[5] << BROTLI_DISTANCE_CONTEXT_BITS
);
1227 s
->dist_htree_index
= s
->dist_context_map_slice
[s
->distance_context
];
1231 static void BROTLI_NOINLINE
DecodeDistanceBlockSwitch(BrotliDecoderState
* s
) {
1232 DecodeDistanceBlockSwitchInternal(0, s
);
1235 static BROTLI_BOOL BROTLI_NOINLINE
SafeDecodeDistanceBlockSwitch(
1236 BrotliDecoderState
* s
) {
1237 return DecodeDistanceBlockSwitchInternal(1, s
);
1240 static size_t UnwrittenBytes(const BrotliDecoderState
* s
, BROTLI_BOOL wrap
) {
1241 size_t pos
= wrap
&& s
->pos
> s
->ringbuffer_size
?
1242 (size_t)s
->ringbuffer_size
: (size_t)(s
->pos
);
1243 size_t partial_pos_rb
= (s
->rb_roundtrips
* (size_t)s
->ringbuffer_size
) + pos
;
1244 return partial_pos_rb
- s
->partial_pos_out
;
1248 Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push
1249 and either ring-buffer is as big as window size, or |force| is true. */
1250 static BrotliDecoderErrorCode BROTLI_NOINLINE
WriteRingBuffer(
1251 BrotliDecoderState
* s
, size_t* available_out
, uint8_t** next_out
,
1252 size_t* total_out
, BROTLI_BOOL force
) {
1254 s
->ringbuffer
+ (s
->partial_pos_out
& (size_t)s
->ringbuffer_mask
);
1255 size_t to_write
= UnwrittenBytes(s
, BROTLI_TRUE
);
1256 size_t num_written
= *available_out
;
1257 if (num_written
> to_write
) {
1258 num_written
= to_write
;
1260 if (s
->meta_block_remaining_len
< 0) {
1261 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1
);
1263 if (next_out
&& !*next_out
) {
1267 memcpy(*next_out
, start
, num_written
);
1268 *next_out
+= num_written
;
1271 *available_out
-= num_written
;
1272 BROTLI_LOG_UINT(to_write
);
1273 BROTLI_LOG_UINT(num_written
);
1274 s
->partial_pos_out
+= num_written
;
1276 *total_out
= s
->partial_pos_out
;
1278 if (num_written
< to_write
) {
1279 if (s
->ringbuffer_size
== (1 << s
->window_bits
) || force
) {
1280 return BROTLI_DECODER_NEEDS_MORE_OUTPUT
;
1282 return BROTLI_DECODER_SUCCESS
;
1285 /* Wrap ring buffer only if it has reached its maximal size. */
1286 if (s
->ringbuffer_size
== (1 << s
->window_bits
) &&
1287 s
->pos
>= s
->ringbuffer_size
) {
1288 s
->pos
-= s
->ringbuffer_size
;
1290 s
->should_wrap_ringbuffer
= (size_t)s
->pos
!= 0 ? 1 : 0;
1292 return BROTLI_DECODER_SUCCESS
;
1295 static void BROTLI_NOINLINE
WrapRingBuffer(BrotliDecoderState
* s
) {
1296 if (s
->should_wrap_ringbuffer
) {
1297 memcpy(s
->ringbuffer
, s
->ringbuffer_end
, (size_t)s
->pos
);
1298 s
->should_wrap_ringbuffer
= 0;
1302 /* Allocates ring-buffer.
1304 s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
1305 this function is called.
1307 Last two bytes of ring-buffer are initialized to 0, so context calculation
1308 could be done uniformly for the first two and all other positions. */
1309 static BROTLI_BOOL BROTLI_NOINLINE
BrotliEnsureRingBuffer(
1310 BrotliDecoderState
* s
) {
1311 uint8_t* old_ringbuffer
= s
->ringbuffer
;
1312 if (s
->ringbuffer_size
== s
->new_ringbuffer_size
) {
1316 s
->ringbuffer
= (uint8_t*)BROTLI_DECODER_ALLOC(s
,
1317 (size_t)(s
->new_ringbuffer_size
) + kRingBufferWriteAheadSlack
);
1318 if (s
->ringbuffer
== 0) {
1319 /* Restore previous value. */
1320 s
->ringbuffer
= old_ringbuffer
;
1321 return BROTLI_FALSE
;
1323 s
->ringbuffer
[s
->new_ringbuffer_size
- 2] = 0;
1324 s
->ringbuffer
[s
->new_ringbuffer_size
- 1] = 0;
1326 if (!!old_ringbuffer
) {
1327 memcpy(s
->ringbuffer
, old_ringbuffer
, (size_t)s
->pos
);
1328 BROTLI_DECODER_FREE(s
, old_ringbuffer
);
1331 s
->ringbuffer_size
= s
->new_ringbuffer_size
;
1332 s
->ringbuffer_mask
= s
->new_ringbuffer_size
- 1;
1333 s
->ringbuffer_end
= s
->ringbuffer
+ s
->ringbuffer_size
;
1338 static BrotliDecoderErrorCode BROTLI_NOINLINE
CopyUncompressedBlockToOutput(
1339 size_t* available_out
, uint8_t** next_out
, size_t* total_out
,
1340 BrotliDecoderState
* s
) {
1341 /* TODO: avoid allocation for single uncompressed block. */
1342 if (!BrotliEnsureRingBuffer(s
)) {
1343 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1
);
1348 switch (s
->substate_uncompressed
) {
1349 case BROTLI_STATE_UNCOMPRESSED_NONE
: {
1350 int nbytes
= (int)BrotliGetRemainingBytes(&s
->br
);
1351 if (nbytes
> s
->meta_block_remaining_len
) {
1352 nbytes
= s
->meta_block_remaining_len
;
1354 if (s
->pos
+ nbytes
> s
->ringbuffer_size
) {
1355 nbytes
= s
->ringbuffer_size
- s
->pos
;
1357 /* Copy remaining bytes from s->br.buf_ to ring-buffer. */
1358 BrotliCopyBytes(&s
->ringbuffer
[s
->pos
], &s
->br
, (size_t)nbytes
);
1360 s
->meta_block_remaining_len
-= nbytes
;
1361 if (s
->pos
< 1 << s
->window_bits
) {
1362 if (s
->meta_block_remaining_len
== 0) {
1363 return BROTLI_DECODER_SUCCESS
;
1365 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1367 s
->substate_uncompressed
= BROTLI_STATE_UNCOMPRESSED_WRITE
;
1371 case BROTLI_STATE_UNCOMPRESSED_WRITE
: {
1372 BrotliDecoderErrorCode result
;
1373 result
= WriteRingBuffer(
1374 s
, available_out
, next_out
, total_out
, BROTLI_FALSE
);
1375 if (result
!= BROTLI_DECODER_SUCCESS
) {
1378 if (s
->ringbuffer_size
== 1 << s
->window_bits
) {
1379 s
->max_distance
= s
->max_backward_distance
;
1381 s
->substate_uncompressed
= BROTLI_STATE_UNCOMPRESSED_NONE
;
1386 BROTLI_DCHECK(0); /* Unreachable */
1389 /* Calculates the smallest feasible ring buffer.
1391 If we know the data size is small, do not allocate more ring buffer
1392 size than needed to reduce memory usage.
1394 When this method is called, metablock size and flags MUST be decoded. */
1395 static void BROTLI_NOINLINE
BrotliCalculateRingBufferSize(
1396 BrotliDecoderState
* s
) {
1397 int window_size
= 1 << s
->window_bits
;
1398 int new_ringbuffer_size
= window_size
;
1399 /* We need at least 2 bytes of ring buffer size to get the last two
1400 bytes for context from there */
1401 int min_size
= s
->ringbuffer_size
? s
->ringbuffer_size
: 1024;
1404 /* If maximum is already reached, no further extension is retired. */
1405 if (s
->ringbuffer_size
== window_size
) {
1409 /* Metadata blocks does not touch ring buffer. */
1410 if (s
->is_metadata
) {
1414 if (!s
->ringbuffer
) {
1417 output_size
= s
->pos
;
1419 output_size
+= s
->meta_block_remaining_len
;
1420 min_size
= min_size
< output_size
? output_size
: min_size
;
1422 if (!!s
->canny_ringbuffer_allocation
) {
1423 /* Reduce ring buffer size to save memory when server is unscrupulous.
1424 In worst case memory usage might be 1.5x bigger for a short period of
1425 ring buffer reallocation. */
1426 while ((new_ringbuffer_size
>> 1) >= min_size
) {
1427 new_ringbuffer_size
>>= 1;
1431 s
->new_ringbuffer_size
= new_ringbuffer_size
;
1434 /* Reads 1..256 2-bit context modes. */
1435 static BrotliDecoderErrorCode
ReadContextModes(BrotliDecoderState
* s
) {
1436 BrotliBitReader
* br
= &s
->br
;
1437 int i
= s
->loop_counter
;
1439 while (i
< (int)s
->num_block_types
[0]) {
1441 if (!BrotliSafeReadBits(br
, 2, &bits
)) {
1442 s
->loop_counter
= i
;
1443 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1445 s
->context_modes
[i
] = (uint8_t)bits
;
1446 BROTLI_LOG_ARRAY_INDEX(s
->context_modes
, i
);
1449 return BROTLI_DECODER_SUCCESS
;
1452 static BROTLI_INLINE
void TakeDistanceFromRingBuffer(BrotliDecoderState
* s
) {
1453 if (s
->distance_code
== 0) {
1455 s
->distance_code
= s
->dist_rb
[s
->dist_rb_idx
& 3];
1456 /* Compensate double distance-ring-buffer roll for dictionary items. */
1457 s
->distance_context
= 1;
1459 int distance_code
= s
->distance_code
<< 1;
1460 /* kDistanceShortCodeIndexOffset has 2-bit values from LSB:
1461 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */
1462 const uint32_t kDistanceShortCodeIndexOffset
= 0xAAAFFF1B;
1463 /* kDistanceShortCodeValueOffset has 2-bit values from LSB:
1464 -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */
1465 const uint32_t kDistanceShortCodeValueOffset
= 0xFA5FA500;
1466 int v
= (s
->dist_rb_idx
+
1467 (int)(kDistanceShortCodeIndexOffset
>> distance_code
)) & 0x3;
1468 s
->distance_code
= s
->dist_rb
[v
];
1469 v
= (int)(kDistanceShortCodeValueOffset
>> distance_code
) & 0x3;
1470 if ((distance_code
& 0x3) != 0) {
1471 s
->distance_code
+= v
;
1473 s
->distance_code
-= v
;
1474 if (s
->distance_code
<= 0) {
1475 /* A huge distance will cause a BROTLI_FAILURE() soon.
1476 This is a little faster than failing here. */
1477 s
->distance_code
= 0x7FFFFFFF;
1483 static BROTLI_INLINE BROTLI_BOOL
SafeReadBits(
1484 BrotliBitReader
* const br
, uint32_t n_bits
, uint32_t* val
) {
1486 return BrotliSafeReadBits(br
, n_bits
, val
);
1493 /* Precondition: s->distance_code < 0. */
1494 static BROTLI_INLINE BROTLI_BOOL
ReadDistanceInternal(
1495 int safe
, BrotliDecoderState
* s
, BrotliBitReader
* br
) {
1497 BrotliBitReaderState memento
;
1498 HuffmanCode
* distance_tree
= s
->distance_hgroup
.htrees
[s
->dist_htree_index
];
1500 s
->distance_code
= (int)ReadSymbol(distance_tree
, br
);
1503 BrotliBitReaderSaveState(br
, &memento
);
1504 if (!SafeReadSymbol(distance_tree
, br
, &code
)) {
1505 return BROTLI_FALSE
;
1507 s
->distance_code
= (int)code
;
1509 /* Convert the distance code to the actual distance by possibly
1510 looking up past distances from the s->ringbuffer. */
1511 s
->distance_context
= 0;
1512 if ((s
->distance_code
& ~0xF) == 0) {
1513 TakeDistanceFromRingBuffer(s
);
1514 --s
->block_length
[2];
1517 distval
= s
->distance_code
- (int)s
->num_direct_distance_codes
;
1522 if (!safe
&& (s
->distance_postfix_bits
== 0)) {
1523 nbits
= ((uint32_t)distval
>> 1) + 1;
1524 offset
= ((2 + (distval
& 1)) << nbits
) - 4;
1525 s
->distance_code
= (int)s
->num_direct_distance_codes
+ offset
+
1526 (int)BrotliReadBits(br
, nbits
);
1528 /* This branch also works well when s->distance_postfix_bits == 0. */
1530 postfix
= distval
& s
->distance_postfix_mask
;
1531 distval
>>= s
->distance_postfix_bits
;
1532 nbits
= ((uint32_t)distval
>> 1) + 1;
1534 if (!SafeReadBits(br
, nbits
, &bits
)) {
1535 s
->distance_code
= -1; /* Restore precondition. */
1536 BrotliBitReaderRestoreState(br
, &memento
);
1537 return BROTLI_FALSE
;
1540 bits
= BrotliReadBits(br
, nbits
);
1542 offset
= ((2 + (distval
& 1)) << nbits
) - 4;
1543 s
->distance_code
= (int)s
->num_direct_distance_codes
+
1544 ((offset
+ (int)bits
) << s
->distance_postfix_bits
) + postfix
;
1547 s
->distance_code
= s
->distance_code
- BROTLI_NUM_DISTANCE_SHORT_CODES
+ 1;
1548 --s
->block_length
[2];
1552 static BROTLI_INLINE
void ReadDistance(
1553 BrotliDecoderState
* s
, BrotliBitReader
* br
) {
1554 ReadDistanceInternal(0, s
, br
);
1557 static BROTLI_INLINE BROTLI_BOOL
SafeReadDistance(
1558 BrotliDecoderState
* s
, BrotliBitReader
* br
) {
1559 return ReadDistanceInternal(1, s
, br
);
1562 static BROTLI_INLINE BROTLI_BOOL
ReadCommandInternal(
1563 int safe
, BrotliDecoderState
* s
, BrotliBitReader
* br
, int* insert_length
) {
1565 uint32_t insert_len_extra
= 0;
1566 uint32_t copy_length
;
1568 BrotliBitReaderState memento
;
1570 cmd_code
= ReadSymbol(s
->htree_command
, br
);
1571 ASSERT (cmd_code
< BROTLI_NUM_COMMAND_SYMBOLS
);
1573 BrotliBitReaderSaveState(br
, &memento
);
1574 if (!SafeReadSymbol(s
->htree_command
, br
, &cmd_code
)) {
1575 return BROTLI_FALSE
;
1578 v
= kCmdLut
[cmd_code
];
1579 s
->distance_code
= v
.distance_code
;
1580 s
->distance_context
= v
.context
;
1581 s
->dist_htree_index
= s
->dist_context_map_slice
[s
->distance_context
];
1582 *insert_length
= v
.insert_len_offset
;
1584 if (BROTLI_PREDICT_FALSE(v
.insert_len_extra_bits
!= 0)) {
1585 insert_len_extra
= BrotliReadBits(br
, v
.insert_len_extra_bits
);
1587 copy_length
= BrotliReadBits(br
, v
.copy_len_extra_bits
);
1589 if (!SafeReadBits(br
, v
.insert_len_extra_bits
, &insert_len_extra
) ||
1590 !SafeReadBits(br
, v
.copy_len_extra_bits
, ©_length
)) {
1591 BrotliBitReaderRestoreState(br
, &memento
);
1592 return BROTLI_FALSE
;
1595 s
->copy_length
= (int)copy_length
+ v
.copy_len_offset
;
1596 --s
->block_length
[1];
1597 *insert_length
+= (int)insert_len_extra
;
1601 static BROTLI_INLINE
void ReadCommand(
1602 BrotliDecoderState
* s
, BrotliBitReader
* br
, int* insert_length
) {
1603 ReadCommandInternal(0, s
, br
, insert_length
);
1606 static BROTLI_INLINE BROTLI_BOOL
SafeReadCommand(
1607 BrotliDecoderState
* s
, BrotliBitReader
* br
, int* insert_length
) {
1608 return ReadCommandInternal(1, s
, br
, insert_length
);
1611 static BROTLI_INLINE BROTLI_BOOL
CheckInputAmount(
1612 int safe
, BrotliBitReader
* const br
, size_t num
) {
1616 return BrotliCheckInputAmount(br
, num
);
1619 #define BROTLI_SAFE(METHOD) \
1622 if (!Safe##METHOD) { \
1623 result = BROTLI_DECODER_NEEDS_MORE_INPUT; \
1624 goto saveStateAndReturn; \
1631 static BROTLI_INLINE BrotliDecoderErrorCode
ProcessCommandsInternal(
1632 int safe
, BrotliDecoderState
* s
) {
1634 int i
= s
->loop_counter
;
1635 BrotliDecoderErrorCode result
= BROTLI_DECODER_SUCCESS
;
1636 BrotliBitReader
* br
= &s
->br
;
1638 if (!CheckInputAmount(safe
, br
, 28)) {
1639 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1640 goto saveStateAndReturn
;
1643 BROTLI_UNUSED(BrotliWarmupBitReader(br
));
1646 /* Jump into state machine. */
1647 if (s
->state
== BROTLI_STATE_COMMAND_BEGIN
) {
1649 } else if (s
->state
== BROTLI_STATE_COMMAND_INNER
) {
1651 } else if (s
->state
== BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
) {
1652 goto CommandPostDecodeLiterals
;
1653 } else if (s
->state
== BROTLI_STATE_COMMAND_POST_WRAP_COPY
) {
1654 goto CommandPostWrapCopy
;
1656 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
1661 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
1663 if (!CheckInputAmount(safe
, br
, 28)) { /* 156 bits + 7 bytes */
1664 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
1665 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1666 goto saveStateAndReturn
;
1668 if (BROTLI_PREDICT_FALSE(s
->block_length
[1] == 0)) {
1669 BROTLI_SAFE(DecodeCommandBlockSwitch(s
));
1672 /* Read the insert/copy length in the command. */
1673 BROTLI_SAFE(ReadCommand(s
, br
, &i
));
1674 BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",
1675 pos
, i
, s
->copy_length
));
1677 goto CommandPostDecodeLiterals
;
1679 s
->meta_block_remaining_len
-= i
;
1683 s
->state
= BROTLI_STATE_COMMAND_INNER
;
1685 /* Read the literals in the command. */
1686 if (s
->trivial_literal_context
) {
1689 PreloadSymbol(safe
, s
->literal_htree
, br
, &bits
, &value
);
1691 if (!CheckInputAmount(safe
, br
, 28)) { /* 162 bits + 7 bytes */
1692 s
->state
= BROTLI_STATE_COMMAND_INNER
;
1693 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1694 goto saveStateAndReturn
;
1696 if (BROTLI_PREDICT_FALSE(s
->block_length
[0] == 0)) {
1697 BROTLI_SAFE(DecodeLiteralBlockSwitch(s
));
1698 PreloadSymbol(safe
, s
->literal_htree
, br
, &bits
, &value
);
1699 if (!s
->trivial_literal_context
) goto CommandInner
;
1702 s
->ringbuffer
[pos
] =
1703 (uint8_t)ReadPreloadedSymbol(s
->literal_htree
, br
, &bits
, &value
);
1706 if (!SafeReadSymbol(s
->literal_htree
, br
, &literal
)) {
1707 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1708 goto saveStateAndReturn
;
1710 s
->ringbuffer
[pos
] = (uint8_t)literal
;
1712 --s
->block_length
[0];
1713 BROTLI_LOG_ARRAY_INDEX(s
->ringbuffer
, pos
);
1715 if (BROTLI_PREDICT_FALSE(pos
== s
->ringbuffer_size
)) {
1716 s
->state
= BROTLI_STATE_COMMAND_INNER_WRITE
;
1718 goto saveStateAndReturn
;
1722 uint8_t p1
= s
->ringbuffer
[(pos
- 1) & s
->ringbuffer_mask
];
1723 uint8_t p2
= s
->ringbuffer
[(pos
- 2) & s
->ringbuffer_mask
];
1725 const HuffmanCode
* hc
;
1727 if (!CheckInputAmount(safe
, br
, 28)) { /* 162 bits + 7 bytes */
1728 s
->state
= BROTLI_STATE_COMMAND_INNER
;
1729 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1730 goto saveStateAndReturn
;
1732 if (BROTLI_PREDICT_FALSE(s
->block_length
[0] == 0)) {
1733 BROTLI_SAFE(DecodeLiteralBlockSwitch(s
));
1734 if (s
->trivial_literal_context
) goto CommandInner
;
1736 context
= BROTLI_CONTEXT(p1
, p2
, s
->context_lookup
);
1737 BROTLI_LOG_UINT(context
);
1738 hc
= s
->literal_hgroup
.htrees
[s
->context_map_slice
[context
]];
1741 p1
= (uint8_t)ReadSymbol(hc
, br
);
1744 if (!SafeReadSymbol(hc
, br
, &literal
)) {
1745 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1746 goto saveStateAndReturn
;
1748 p1
= (uint8_t)literal
;
1750 s
->ringbuffer
[pos
] = p1
;
1751 --s
->block_length
[0];
1752 BROTLI_LOG_UINT(s
->context_map_slice
[context
]);
1753 BROTLI_LOG_ARRAY_INDEX(s
->ringbuffer
, pos
& s
->ringbuffer_mask
);
1755 if (BROTLI_PREDICT_FALSE(pos
== s
->ringbuffer_size
)) {
1756 s
->state
= BROTLI_STATE_COMMAND_INNER_WRITE
;
1758 goto saveStateAndReturn
;
1762 BROTLI_LOG_UINT(s
->meta_block_remaining_len
);
1763 if (BROTLI_PREDICT_FALSE(s
->meta_block_remaining_len
<= 0)) {
1764 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
1765 goto saveStateAndReturn
;
1768 CommandPostDecodeLiterals
:
1770 s
->state
= BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
;
1772 if (s
->distance_code
>= 0) {
1773 /* Implicit distance case. */
1774 s
->distance_context
= s
->distance_code
? 0 : 1;
1776 s
->distance_code
= s
->dist_rb
[s
->dist_rb_idx
& 3];
1778 /* Read distance code in the command, unless it was implicitly zero. */
1779 if (BROTLI_PREDICT_FALSE(s
->block_length
[2] == 0)) {
1780 BROTLI_SAFE(DecodeDistanceBlockSwitch(s
));
1782 BROTLI_SAFE(ReadDistance(s
, br
));
1784 BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",
1785 pos
, s
->distance_code
));
1786 if (s
->max_distance
!= s
->max_backward_distance
) {
1788 (pos
< s
->max_backward_distance
) ? pos
: s
->max_backward_distance
;
1791 /* Apply copy of LZ77 back-reference, or static dictionary reference if
1792 the distance is larger than the max LZ77 distance */
1793 if (s
->distance_code
> s
->max_distance
) {
1794 /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC.
1795 With this choice, no signed overflow can occur after decoding
1796 a special distance code (e.g., after adding 3 to the last distance). */
1797 if (s
->distance_code
> BROTLI_MAX_ALLOWED_DISTANCE
) {
1798 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1799 "len: %d bytes left: %d\n",
1800 pos
, s
->distance_code
, i
, s
->meta_block_remaining_len
));
1801 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE
);
1803 if (i
>= BROTLI_MIN_DICTIONARY_WORD_LENGTH
&&
1804 i
<= BROTLI_MAX_DICTIONARY_WORD_LENGTH
) {
1805 int address
= s
->distance_code
- s
->max_distance
- 1;
1806 const BrotliDictionary
* words
= s
->dictionary
;
1807 const BrotliTransforms
* transforms
= s
->transforms
;
1808 int offset
= (int)s
->dictionary
->offsets_by_length
[i
];
1809 uint32_t shift
= s
->dictionary
->size_bits_by_length
[i
];
1811 int mask
= (int)BitMask(shift
);
1812 int word_idx
= address
& mask
;
1813 int transform_idx
= address
>> shift
;
1814 /* Compensate double distance-ring-buffer roll. */
1815 s
->dist_rb_idx
+= s
->distance_context
;
1816 offset
+= word_idx
* i
;
1817 if (BROTLI_PREDICT_FALSE(!words
->data
)) {
1818 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET
);
1820 if (transform_idx
< (int)transforms
->num_transforms
) {
1821 const uint8_t* word
= &words
->data
[offset
];
1823 if (transform_idx
== transforms
->cutOffTransforms
[0]) {
1824 memcpy(&s
->ringbuffer
[pos
], word
, (size_t)len
);
1825 BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n",
1828 len
= BrotliTransformDictionaryWord(&s
->ringbuffer
[pos
], word
, len
,
1829 transforms
, transform_idx
);
1830 BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s],"
1831 " transform_idx = %d, transformed: [%.*s]\n",
1832 i
, word
, transform_idx
, len
, &s
->ringbuffer
[pos
]));
1835 s
->meta_block_remaining_len
-= len
;
1836 if (pos
>= s
->ringbuffer_size
) {
1837 s
->state
= BROTLI_STATE_COMMAND_POST_WRITE_1
;
1838 goto saveStateAndReturn
;
1841 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1842 "len: %d bytes left: %d\n",
1843 pos
, s
->distance_code
, i
, s
->meta_block_remaining_len
));
1844 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM
);
1847 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1848 "len: %d bytes left: %d\n",
1849 pos
, s
->distance_code
, i
, s
->meta_block_remaining_len
));
1850 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY
);
1853 int src_start
= (pos
- s
->distance_code
) & s
->ringbuffer_mask
;
1854 uint8_t* copy_dst
= &s
->ringbuffer
[pos
];
1855 uint8_t* copy_src
= &s
->ringbuffer
[src_start
];
1856 int dst_end
= pos
+ i
;
1857 int src_end
= src_start
+ i
;
1858 /* Update the recent distances cache. */
1859 s
->dist_rb
[s
->dist_rb_idx
& 3] = s
->distance_code
;
1861 s
->meta_block_remaining_len
-= i
;
1862 /* There are 32+ bytes of slack in the ring-buffer allocation.
1863 Also, we have 16 short codes, that make these 16 bytes irrelevant
1864 in the ring-buffer. Let's copy over them as a first guess. */
1865 memmove16(copy_dst
, copy_src
);
1866 if (src_end
> pos
&& dst_end
> src_start
) {
1867 /* Regions intersect. */
1868 goto CommandPostWrapCopy
;
1870 if (dst_end
>= s
->ringbuffer_size
|| src_end
>= s
->ringbuffer_size
) {
1871 /* At least one region wraps. */
1872 goto CommandPostWrapCopy
;
1877 memcpy(copy_dst
+ 16, copy_src
+ 16, (size_t)(i
- 16));
1879 /* This branch covers about 45% cases.
1880 Fixed size short copy allows more compiler optimizations. */
1881 memmove16(copy_dst
+ 16, copy_src
+ 16);
1885 BROTLI_LOG_UINT(s
->meta_block_remaining_len
);
1886 if (s
->meta_block_remaining_len
<= 0) {
1887 /* Next metablock, if any. */
1888 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
1889 goto saveStateAndReturn
;
1893 CommandPostWrapCopy
:
1895 int wrap_guard
= s
->ringbuffer_size
- pos
;
1897 s
->ringbuffer
[pos
] =
1898 s
->ringbuffer
[(pos
- s
->distance_code
) & s
->ringbuffer_mask
];
1900 if (BROTLI_PREDICT_FALSE(--wrap_guard
== 0)) {
1901 s
->state
= BROTLI_STATE_COMMAND_POST_WRITE_2
;
1902 goto saveStateAndReturn
;
1906 if (s
->meta_block_remaining_len
<= 0) {
1907 /* Next metablock, if any. */
1908 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
1909 goto saveStateAndReturn
;
1916 s
->loop_counter
= i
;
1922 static BROTLI_NOINLINE BrotliDecoderErrorCode
ProcessCommands(
1923 BrotliDecoderState
* s
) {
1924 return ProcessCommandsInternal(0, s
);
1927 static BROTLI_NOINLINE BrotliDecoderErrorCode
SafeProcessCommands(
1928 BrotliDecoderState
* s
) {
1929 return ProcessCommandsInternal(1, s
);
1932 /* Returns the maximum number of distance symbols which can only represent
1933 distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */
1934 static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect
, uint32_t npostfix
) {
1935 static const uint32_t bound
[BROTLI_MAX_NPOSTFIX
+ 1] = {0, 4, 12, 28};
1936 static const uint32_t diff
[BROTLI_MAX_NPOSTFIX
+ 1] = {73, 126, 228, 424};
1937 uint32_t postfix
= 1U << npostfix
;
1938 if (ndirect
< bound
[npostfix
]) {
1939 return ndirect
+ diff
[npostfix
] + postfix
;
1940 } else if (ndirect
> bound
[npostfix
] + postfix
) {
1941 return ndirect
+ diff
[npostfix
];
1943 return bound
[npostfix
] + diff
[npostfix
] + postfix
;
1947 BrotliDecoderResult
BrotliDecoderDecompress(
1948 size_t encoded_size
, const uint8_t* encoded_buffer
, size_t* decoded_size
,
1949 uint8_t* decoded_buffer
) {
1950 BrotliDecoderState s
;
1951 BrotliDecoderResult result
;
1952 size_t total_out
= 0;
1953 size_t available_in
= encoded_size
;
1954 const uint8_t* next_in
= encoded_buffer
;
1955 size_t available_out
= *decoded_size
;
1956 uint8_t* next_out
= decoded_buffer
;
1957 if (!BrotliDecoderStateInit(&s
, 0, 0, 0)) {
1958 return BROTLI_DECODER_RESULT_ERROR
;
1960 result
= BrotliDecoderDecompressStream(
1961 &s
, &available_in
, &next_in
, &available_out
, &next_out
, &total_out
);
1962 *decoded_size
= total_out
;
1963 BrotliDecoderStateCleanup(&s
);
1964 if (result
!= BROTLI_DECODER_RESULT_SUCCESS
) {
1965 result
= BROTLI_DECODER_RESULT_ERROR
;
1970 /* Invariant: input stream is never overconsumed:
1971 - invalid input implies that the whole stream is invalid -> any amount of
1972 input could be read and discarded
1973 - when result is "needs more input", then at least one more byte is REQUIRED
1974 to complete decoding; all input data MUST be consumed by decoder, so
1975 client could swap the input buffer
1976 - when result is "needs more output" decoder MUST ensure that it doesn't
1977 hold more than 7 bits in bit reader; this saves client from swapping input
1978 buffer ahead of time
1979 - when result is "success" decoder MUST return all unused data back to input
1980 buffer; this is possible because the invariant is held on enter */
1981 BrotliDecoderResult
BrotliDecoderDecompressStream(
1982 BrotliDecoderState
* s
, size_t* available_in
, const uint8_t** next_in
,
1983 size_t* available_out
, uint8_t** next_out
, size_t* total_out
) {
1984 BrotliDecoderErrorCode result
= BROTLI_DECODER_SUCCESS
;
1985 BrotliBitReader
* br
= &s
->br
;
1986 /* Ensure that |total_out| is set, even if no data will ever be pushed out. */
1988 *total_out
= s
->partial_pos_out
;
1990 /* Do not try to process further in a case of unrecoverable error. */
1991 if ((int)s
->error_code
< 0) {
1992 return BROTLI_DECODER_RESULT_ERROR
;
1994 if (*available_out
&& (!next_out
|| !*next_out
)) {
1995 return SaveErrorCode(
1996 s
, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS
));
1998 if (!*available_out
) next_out
= 0;
1999 if (s
->buffer_length
== 0) { /* Just connect bit reader to input stream. */
2000 br
->avail_in
= *available_in
;
2001 br
->next_in
= *next_in
;
2003 /* At least one byte of input is required. More than one byte of input may
2004 be required to complete the transaction -> reading more data must be
2005 done in a loop -> do it in a main loop. */
2006 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2007 br
->next_in
= &s
->buffer
.u8
[0];
2011 if (result
!= BROTLI_DECODER_SUCCESS
) {
2012 /* Error, needs more input/output. */
2013 if (result
== BROTLI_DECODER_NEEDS_MORE_INPUT
) {
2014 if (s
->ringbuffer
!= 0) { /* Pro-actively push output. */
2015 BrotliDecoderErrorCode intermediate_result
= WriteRingBuffer(s
,
2016 available_out
, next_out
, total_out
, BROTLI_TRUE
);
2017 /* WriteRingBuffer checks s->meta_block_remaining_len validity. */
2018 if ((int)intermediate_result
< 0) {
2019 result
= intermediate_result
;
2023 if (s
->buffer_length
!= 0) { /* Used with internal buffer. */
2024 if (br
->avail_in
== 0) {
2025 /* Successfully finished read transaction.
2026 Accumulator contains less than 8 bits, because internal buffer
2027 is expanded byte-by-byte until it is enough to complete read. */
2028 s
->buffer_length
= 0;
2029 /* Switch to input stream and restart. */
2030 result
= BROTLI_DECODER_SUCCESS
;
2031 br
->avail_in
= *available_in
;
2032 br
->next_in
= *next_in
;
2034 } else if (*available_in
!= 0) {
2035 /* Not enough data in buffer, but can take one more byte from
2037 result
= BROTLI_DECODER_SUCCESS
;
2038 s
->buffer
.u8
[s
->buffer_length
] = **next_in
;
2040 br
->avail_in
= s
->buffer_length
;
2043 /* Retry with more data in buffer. */
2046 /* Can't finish reading and no more input. */
2048 } else { /* Input stream doesn't contain enough input. */
2049 /* Copy tail to internal buffer and return. */
2050 *next_in
= br
->next_in
;
2051 *available_in
= br
->avail_in
;
2052 while (*available_in
) {
2053 s
->buffer
.u8
[s
->buffer_length
] = **next_in
;
2063 /* Fail or needs more output. */
2065 if (s
->buffer_length
!= 0) {
2066 /* Just consumed the buffered input and produced some output. Otherwise
2067 it would result in "needs more input". Reset internal buffer. */
2068 s
->buffer_length
= 0;
2070 /* Using input stream in last iteration. When decoder switches to input
2071 stream it has less than 8 bits in accumulator, so it is safe to
2072 return unused accumulator bits there. */
2073 BrotliBitReaderUnload(br
);
2074 *available_in
= br
->avail_in
;
2075 *next_in
= br
->next_in
;
2080 case BROTLI_STATE_UNINITED
:
2081 /* Prepare to the first read. */
2082 if (!BrotliWarmupBitReader(br
)) {
2083 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2086 /* Decode window size. */
2087 result
= DecodeWindowBits(s
, br
); /* Reads 1..8 bits. */
2088 if (result
!= BROTLI_DECODER_SUCCESS
) {
2091 if (s
->large_window
) {
2092 s
->state
= BROTLI_STATE_LARGE_WINDOW_BITS
;
2095 s
->state
= BROTLI_STATE_INITIALIZE
;
2098 case BROTLI_STATE_LARGE_WINDOW_BITS
:
2099 if (!BrotliSafeReadBits(br
, 6, &s
->window_bits
)) {
2100 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2103 if (s
->window_bits
< BROTLI_LARGE_MIN_WBITS
||
2104 s
->window_bits
> BROTLI_LARGE_MAX_WBITS
) {
2105 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS
);
2108 s
->state
= BROTLI_STATE_INITIALIZE
;
2111 case BROTLI_STATE_INITIALIZE
:
2112 BROTLI_LOG_UINT(s
->window_bits
);
2113 /* Maximum distance, see section 9.1. of the spec. */
2114 s
->max_backward_distance
= (1 << s
->window_bits
) - BROTLI_WINDOW_GAP
;
2116 /* Allocate memory for both block_type_trees and block_len_trees. */
2117 s
->block_type_trees
= (HuffmanCode
*)BROTLI_DECODER_ALLOC(s
,
2118 sizeof(HuffmanCode
) * 3 *
2119 (BROTLI_HUFFMAN_MAX_SIZE_258
+ BROTLI_HUFFMAN_MAX_SIZE_26
));
2120 if (s
->block_type_trees
== 0) {
2121 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES
);
2124 s
->block_len_trees
=
2125 s
->block_type_trees
+ 3 * BROTLI_HUFFMAN_MAX_SIZE_258
;
2127 s
->state
= BROTLI_STATE_METABLOCK_BEGIN
;
2130 case BROTLI_STATE_METABLOCK_BEGIN
:
2131 BrotliDecoderStateMetablockBegin(s
);
2132 BROTLI_LOG_UINT(s
->pos
);
2133 s
->state
= BROTLI_STATE_METABLOCK_HEADER
;
2136 case BROTLI_STATE_METABLOCK_HEADER
:
2137 result
= DecodeMetaBlockLength(s
, br
); /* Reads 2 - 31 bits. */
2138 if (result
!= BROTLI_DECODER_SUCCESS
) {
2141 BROTLI_LOG_UINT(s
->is_last_metablock
);
2142 BROTLI_LOG_UINT(s
->meta_block_remaining_len
);
2143 BROTLI_LOG_UINT(s
->is_metadata
);
2144 BROTLI_LOG_UINT(s
->is_uncompressed
);
2145 if (s
->is_metadata
|| s
->is_uncompressed
) {
2146 if (!BrotliJumpToByteBoundary(br
)) {
2147 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1
);
2151 if (s
->is_metadata
) {
2152 s
->state
= BROTLI_STATE_METADATA
;
2155 if (s
->meta_block_remaining_len
== 0) {
2156 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2159 BrotliCalculateRingBufferSize(s
);
2160 if (s
->is_uncompressed
) {
2161 s
->state
= BROTLI_STATE_UNCOMPRESSED
;
2164 s
->loop_counter
= 0;
2165 s
->state
= BROTLI_STATE_HUFFMAN_CODE_0
;
2168 case BROTLI_STATE_UNCOMPRESSED
: {
2169 result
= CopyUncompressedBlockToOutput(
2170 available_out
, next_out
, total_out
, s
);
2171 if (result
!= BROTLI_DECODER_SUCCESS
) {
2174 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2178 case BROTLI_STATE_METADATA
:
2179 for (; s
->meta_block_remaining_len
> 0; --s
->meta_block_remaining_len
) {
2181 /* Read one byte and ignore it. */
2182 if (!BrotliSafeReadBits(br
, 8, &bits
)) {
2183 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2187 if (result
== BROTLI_DECODER_SUCCESS
) {
2188 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2192 case BROTLI_STATE_HUFFMAN_CODE_0
:
2193 if (s
->loop_counter
>= 3) {
2194 s
->state
= BROTLI_STATE_METABLOCK_HEADER_2
;
2197 /* Reads 1..11 bits. */
2198 result
= DecodeVarLenUint8(s
, br
, &s
->num_block_types
[s
->loop_counter
]);
2199 if (result
!= BROTLI_DECODER_SUCCESS
) {
2202 s
->num_block_types
[s
->loop_counter
]++;
2203 BROTLI_LOG_UINT(s
->num_block_types
[s
->loop_counter
]);
2204 if (s
->num_block_types
[s
->loop_counter
] < 2) {
2208 s
->state
= BROTLI_STATE_HUFFMAN_CODE_1
;
2211 case BROTLI_STATE_HUFFMAN_CODE_1
: {
2212 uint32_t alphabet_size
= s
->num_block_types
[s
->loop_counter
] + 2;
2213 int tree_offset
= s
->loop_counter
* BROTLI_HUFFMAN_MAX_SIZE_258
;
2214 result
= ReadHuffmanCode(alphabet_size
, alphabet_size
,
2215 &s
->block_type_trees
[tree_offset
], NULL
, s
);
2216 if (result
!= BROTLI_DECODER_SUCCESS
) break;
2217 s
->state
= BROTLI_STATE_HUFFMAN_CODE_2
;
2221 case BROTLI_STATE_HUFFMAN_CODE_2
: {
2222 uint32_t alphabet_size
= BROTLI_NUM_BLOCK_LEN_SYMBOLS
;
2223 int tree_offset
= s
->loop_counter
* BROTLI_HUFFMAN_MAX_SIZE_26
;
2224 result
= ReadHuffmanCode(alphabet_size
, alphabet_size
,
2225 &s
->block_len_trees
[tree_offset
], NULL
, s
);
2226 if (result
!= BROTLI_DECODER_SUCCESS
) break;
2227 s
->state
= BROTLI_STATE_HUFFMAN_CODE_3
;
2231 case BROTLI_STATE_HUFFMAN_CODE_3
: {
2232 int tree_offset
= s
->loop_counter
* BROTLI_HUFFMAN_MAX_SIZE_26
;
2233 if (!SafeReadBlockLength(s
, &s
->block_length
[s
->loop_counter
],
2234 &s
->block_len_trees
[tree_offset
], br
)) {
2235 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2238 BROTLI_LOG_UINT(s
->block_length
[s
->loop_counter
]);
2240 s
->state
= BROTLI_STATE_HUFFMAN_CODE_0
;
2244 case BROTLI_STATE_METABLOCK_HEADER_2
: {
2246 if (!BrotliSafeReadBits(br
, 6, &bits
)) {
2247 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2250 s
->distance_postfix_bits
= bits
& BitMask(2);
2252 s
->num_direct_distance_codes
= BROTLI_NUM_DISTANCE_SHORT_CODES
+
2253 (bits
<< s
->distance_postfix_bits
);
2254 BROTLI_LOG_UINT(s
->num_direct_distance_codes
);
2255 BROTLI_LOG_UINT(s
->distance_postfix_bits
);
2256 s
->distance_postfix_mask
= (int)BitMask(s
->distance_postfix_bits
);
2258 (uint8_t*)BROTLI_DECODER_ALLOC(s
, (size_t)s
->num_block_types
[0]);
2259 if (s
->context_modes
== 0) {
2260 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES
);
2263 s
->loop_counter
= 0;
2264 s
->state
= BROTLI_STATE_CONTEXT_MODES
;
2268 case BROTLI_STATE_CONTEXT_MODES
:
2269 result
= ReadContextModes(s
);
2270 if (result
!= BROTLI_DECODER_SUCCESS
) {
2273 s
->state
= BROTLI_STATE_CONTEXT_MAP_1
;
2276 case BROTLI_STATE_CONTEXT_MAP_1
:
2277 result
= DecodeContextMap(
2278 s
->num_block_types
[0] << BROTLI_LITERAL_CONTEXT_BITS
,
2279 &s
->num_literal_htrees
, &s
->context_map
, s
);
2280 if (result
!= BROTLI_DECODER_SUCCESS
) {
2283 DetectTrivialLiteralBlockTypes(s
);
2284 s
->state
= BROTLI_STATE_CONTEXT_MAP_2
;
2287 case BROTLI_STATE_CONTEXT_MAP_2
: {
2288 uint32_t num_direct_codes
=
2289 s
->num_direct_distance_codes
- BROTLI_NUM_DISTANCE_SHORT_CODES
;
2290 uint32_t num_distance_codes
= BROTLI_DISTANCE_ALPHABET_SIZE(
2291 s
->distance_postfix_bits
, num_direct_codes
,
2292 (s
->large_window
? BROTLI_LARGE_MAX_DISTANCE_BITS
:
2293 BROTLI_MAX_DISTANCE_BITS
));
2294 uint32_t max_distance_symbol
= (s
->large_window
?
2295 BrotliMaxDistanceSymbol(
2296 num_direct_codes
, s
->distance_postfix_bits
) :
2297 num_distance_codes
);
2298 BROTLI_BOOL allocation_success
= BROTLI_TRUE
;
2299 result
= DecodeContextMap(
2300 s
->num_block_types
[2] << BROTLI_DISTANCE_CONTEXT_BITS
,
2301 &s
->num_dist_htrees
, &s
->dist_context_map
, s
);
2302 if (result
!= BROTLI_DECODER_SUCCESS
) {
2305 allocation_success
&= BrotliDecoderHuffmanTreeGroupInit(
2306 s
, &s
->literal_hgroup
, BROTLI_NUM_LITERAL_SYMBOLS
,
2307 BROTLI_NUM_LITERAL_SYMBOLS
, s
->num_literal_htrees
);
2308 allocation_success
&= BrotliDecoderHuffmanTreeGroupInit(
2309 s
, &s
->insert_copy_hgroup
, BROTLI_NUM_COMMAND_SYMBOLS
,
2310 BROTLI_NUM_COMMAND_SYMBOLS
, s
->num_block_types
[1]);
2311 allocation_success
&= BrotliDecoderHuffmanTreeGroupInit(
2312 s
, &s
->distance_hgroup
, num_distance_codes
,
2313 max_distance_symbol
, s
->num_dist_htrees
);
2314 if (!allocation_success
) {
2315 return SaveErrorCode(s
,
2316 BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS
));
2318 s
->loop_counter
= 0;
2319 s
->state
= BROTLI_STATE_TREE_GROUP
;
2323 case BROTLI_STATE_TREE_GROUP
: {
2324 HuffmanTreeGroup
* hgroup
= NULL
;
2325 switch (s
->loop_counter
) {
2326 case 0: hgroup
= &s
->literal_hgroup
; break;
2327 case 1: hgroup
= &s
->insert_copy_hgroup
; break;
2328 case 2: hgroup
= &s
->distance_hgroup
; break;
2329 default: return SaveErrorCode(s
, BROTLI_FAILURE(
2330 BROTLI_DECODER_ERROR_UNREACHABLE
));
2332 result
= HuffmanTreeGroupDecode(hgroup
, s
);
2333 if (result
!= BROTLI_DECODER_SUCCESS
) break;
2335 if (s
->loop_counter
>= 3) {
2336 PrepareLiteralDecoding(s
);
2337 s
->dist_context_map_slice
= s
->dist_context_map
;
2338 s
->htree_command
= s
->insert_copy_hgroup
.htrees
[0];
2339 if (!BrotliEnsureRingBuffer(s
)) {
2340 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2
);
2343 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
2348 case BROTLI_STATE_COMMAND_BEGIN
:
2350 case BROTLI_STATE_COMMAND_INNER
:
2352 case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
:
2354 case BROTLI_STATE_COMMAND_POST_WRAP_COPY
:
2355 result
= ProcessCommands(s
);
2356 if (result
== BROTLI_DECODER_NEEDS_MORE_INPUT
) {
2357 result
= SafeProcessCommands(s
);
2361 case BROTLI_STATE_COMMAND_INNER_WRITE
:
2363 case BROTLI_STATE_COMMAND_POST_WRITE_1
:
2365 case BROTLI_STATE_COMMAND_POST_WRITE_2
:
2366 result
= WriteRingBuffer(
2367 s
, available_out
, next_out
, total_out
, BROTLI_FALSE
);
2368 if (result
!= BROTLI_DECODER_SUCCESS
) {
2372 if (s
->ringbuffer_size
== 1 << s
->window_bits
) {
2373 s
->max_distance
= s
->max_backward_distance
;
2375 if (s
->state
== BROTLI_STATE_COMMAND_POST_WRITE_1
) {
2376 if (s
->meta_block_remaining_len
== 0) {
2377 /* Next metablock, if any. */
2378 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2380 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
2383 } else if (s
->state
== BROTLI_STATE_COMMAND_POST_WRITE_2
) {
2384 s
->state
= BROTLI_STATE_COMMAND_POST_WRAP_COPY
;
2385 } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */
2386 if (s
->loop_counter
== 0) {
2387 if (s
->meta_block_remaining_len
== 0) {
2388 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2390 s
->state
= BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
;
2394 s
->state
= BROTLI_STATE_COMMAND_INNER
;
2398 case BROTLI_STATE_METABLOCK_DONE
:
2399 if (s
->meta_block_remaining_len
< 0) {
2400 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2
);
2403 BrotliDecoderStateCleanupAfterMetablock(s
);
2404 if (!s
->is_last_metablock
) {
2405 s
->state
= BROTLI_STATE_METABLOCK_BEGIN
;
2408 if (!BrotliJumpToByteBoundary(br
)) {
2409 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2
);
2412 if (s
->buffer_length
== 0) {
2413 BrotliBitReaderUnload(br
);
2414 *available_in
= br
->avail_in
;
2415 *next_in
= br
->next_in
;
2417 s
->state
= BROTLI_STATE_DONE
;
2420 case BROTLI_STATE_DONE
:
2421 if (s
->ringbuffer
!= 0) {
2422 result
= WriteRingBuffer(
2423 s
, available_out
, next_out
, total_out
, BROTLI_TRUE
);
2424 if (result
!= BROTLI_DECODER_SUCCESS
) {
2428 return SaveErrorCode(s
, result
);
2431 return SaveErrorCode(s
, result
);
2434 BROTLI_BOOL
BrotliDecoderHasMoreOutput(const BrotliDecoderState
* s
) {
2435 /* After unrecoverable error remaining output is considered nonsensical. */
2436 if ((int)s
->error_code
< 0) {
2437 return BROTLI_FALSE
;
2439 return TO_BROTLI_BOOL(
2440 s
->ringbuffer
!= 0 && UnwrittenBytes(s
, BROTLI_FALSE
) != 0);
2443 const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState
* s
, size_t* size
) {
2444 uint8_t* result
= 0;
2445 size_t available_out
= *size
? *size
: 1u << 24;
2446 size_t requested_out
= available_out
;
2447 BrotliDecoderErrorCode status
;
2448 if ((s
->ringbuffer
== 0) || ((int)s
->error_code
< 0)) {
2453 status
= WriteRingBuffer(s
, &available_out
, &result
, 0, BROTLI_TRUE
);
2454 /* Either WriteRingBuffer returns those "success" codes... */
2455 if (status
== BROTLI_DECODER_SUCCESS
||
2456 status
== BROTLI_DECODER_NEEDS_MORE_OUTPUT
) {
2457 *size
= requested_out
- available_out
;
2459 /* ... or stream is broken. Normally this should be caught by
2460 BrotliDecoderDecompressStream, this is just a safeguard. */
2461 if ((int)status
< 0) SaveErrorCode(s
, status
);
2468 BROTLI_BOOL
BrotliDecoderIsUsed(const BrotliDecoderState
* s
) {
2469 return TO_BROTLI_BOOL(s
->state
!= BROTLI_STATE_UNINITED
||
2470 BrotliGetAvailableBits(&s
->br
) != 0);
2473 BROTLI_BOOL
BrotliDecoderIsFinished(const BrotliDecoderState
* s
) {
2474 return TO_BROTLI_BOOL(s
->state
== BROTLI_STATE_DONE
) &&
2475 !BrotliDecoderHasMoreOutput(s
);
2478 BrotliDecoderErrorCode
BrotliDecoderGetErrorCode(const BrotliDecoderState
* s
) {
2479 return (BrotliDecoderErrorCode
)s
->error_code
;
2482 const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c
) {
2484 #define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \
2485 case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;
2486 #define BROTLI_NOTHING_
2487 BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_
, BROTLI_NOTHING_
)
2488 #undef BROTLI_ERROR_CODE_CASE_
2489 #undef BROTLI_NOTHING_
2490 default: return "INVALID";
2494 uint32_t BrotliDecoderVersion() {
2495 return BROTLI_VERSION
;
2498 #if defined(__cplusplus) || defined(c_plusplus)