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 nbits
= kBlockLengthPrefixCode
[code
].nbits
; /* nbits == 2..24 */
862 return kBlockLengthPrefixCode
[code
].offset
+ BrotliReadBits(br
, nbits
);
865 /* WARNING: if state is not BROTLI_STATE_READ_BLOCK_LENGTH_NONE, then
866 reading can't be continued with ReadBlockLength. */
867 static BROTLI_INLINE BROTLI_BOOL
SafeReadBlockLength(
868 BrotliDecoderState
* s
, uint32_t* result
, const HuffmanCode
* table
,
869 BrotliBitReader
* br
) {
871 if (s
->substate_read_block_length
== BROTLI_STATE_READ_BLOCK_LENGTH_NONE
) {
872 if (!SafeReadSymbol(table
, br
, &index
)) {
876 index
= s
->block_length_index
;
880 uint32_t nbits
= kBlockLengthPrefixCode
[index
].nbits
; /* nbits == 2..24 */
881 if (!BrotliSafeReadBits(br
, nbits
, &bits
)) {
882 s
->block_length_index
= index
;
883 s
->substate_read_block_length
= BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
;
886 *result
= kBlockLengthPrefixCode
[index
].offset
+ bits
;
887 s
->substate_read_block_length
= BROTLI_STATE_READ_BLOCK_LENGTH_NONE
;
893 1) initialize list L with values 0, 1,... 255
894 2) For each input element X:
896 2.2) remove X-th element from L
898 2.4) append Y to output
900 In most cases max(Y) <= 7, so most of L remains intact.
901 To reduce the cost of initialization, we reuse L, remember the upper bound
902 of Y values, and reinitialize only first elements in L.
904 Most of input values are 0 and 1. To reduce number of branches, we replace
905 inner for loop with do-while. */
906 static BROTLI_NOINLINE
void InverseMoveToFrontTransform(
907 uint8_t* v
, uint32_t v_len
, BrotliDecoderState
* state
) {
908 /* Reinitialize elements that could have been changed. */
910 uint32_t upper_bound
= state
->mtf_upper_bound
;
911 uint32_t* mtf
= &state
->mtf
[1]; /* Make mtf[-1] addressable. */
912 uint8_t* mtf_u8
= (uint8_t*)mtf
;
913 /* Load endian-aware constant. */
914 const uint8_t b0123
[4] = {0, 1, 2, 3};
916 memcpy(&pattern
, &b0123
, 4);
918 /* Initialize list using 4 consequent values pattern. */
921 pattern
+= 0x04040404; /* Advance all 4 values by 4. */
924 } while (i
<= upper_bound
);
926 /* Transform the input. */
928 for (i
= 0; i
< v_len
; ++i
) {
930 uint8_t value
= mtf_u8
[index
];
936 mtf_u8
[index
+ 1] = mtf_u8
[index
];
937 } while (index
>= 0);
939 /* Remember amount of elements to be reinitialized. */
940 state
->mtf_upper_bound
= upper_bound
>> 2;
943 /* Decodes a series of Huffman table using ReadHuffmanCode function. */
944 static BrotliDecoderErrorCode
HuffmanTreeGroupDecode(
945 HuffmanTreeGroup
* group
, BrotliDecoderState
* s
) {
946 if (s
->substate_tree_group
!= BROTLI_STATE_TREE_GROUP_LOOP
) {
947 s
->next
= group
->codes
;
949 s
->substate_tree_group
= BROTLI_STATE_TREE_GROUP_LOOP
;
951 while (s
->htree_index
< group
->num_htrees
) {
953 BrotliDecoderErrorCode result
=
954 ReadHuffmanCode(group
->alphabet_size
, group
->max_symbol
,
955 s
->next
, &table_size
, s
);
956 if (result
!= BROTLI_DECODER_SUCCESS
) return result
;
957 group
->htrees
[s
->htree_index
] = s
->next
;
958 s
->next
+= table_size
;
961 s
->substate_tree_group
= BROTLI_STATE_TREE_GROUP_NONE
;
962 return BROTLI_DECODER_SUCCESS
;
965 /* Decodes a context map.
966 Decoding is done in 4 phases:
967 1) Read auxiliary information (6..16 bits) and allocate memory.
968 In case of trivial context map, decoding is finished at this phase.
969 2) Decode Huffman table using ReadHuffmanCode function.
970 This table will be used for reading context map items.
971 3) Read context map items; "0" values could be run-length encoded.
972 4) Optionally, apply InverseMoveToFront transform to the resulting map. */
973 static BrotliDecoderErrorCode
DecodeContextMap(uint32_t context_map_size
,
974 uint32_t* num_htrees
,
975 uint8_t** context_map_arg
,
976 BrotliDecoderState
* s
) {
977 BrotliBitReader
* br
= &s
->br
;
978 BrotliDecoderErrorCode result
= BROTLI_DECODER_SUCCESS
;
980 switch ((int)s
->substate_context_map
) {
981 case BROTLI_STATE_CONTEXT_MAP_NONE
:
982 result
= DecodeVarLenUint8(s
, br
, num_htrees
);
983 if (result
!= BROTLI_DECODER_SUCCESS
) {
987 s
->context_index
= 0;
988 BROTLI_LOG_UINT(context_map_size
);
989 BROTLI_LOG_UINT(*num_htrees
);
991 (uint8_t*)BROTLI_DECODER_ALLOC(s
, (size_t)context_map_size
);
992 if (*context_map_arg
== 0) {
993 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP
);
995 if (*num_htrees
<= 1) {
996 memset(*context_map_arg
, 0, (size_t)context_map_size
);
997 return BROTLI_DECODER_SUCCESS
;
999 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_READ_PREFIX
;
1002 case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX
: {
1004 /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe
1005 to peek 4 bits ahead. */
1006 if (!BrotliSafeGetBits(br
, 5, &bits
)) {
1007 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1009 if ((bits
& 1) != 0) { /* Use RLE for zeros. */
1010 s
->max_run_length_prefix
= (bits
>> 1) + 1;
1011 BrotliDropBits(br
, 5);
1013 s
->max_run_length_prefix
= 0;
1014 BrotliDropBits(br
, 1);
1016 BROTLI_LOG_UINT(s
->max_run_length_prefix
);
1017 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_HUFFMAN
;
1021 case BROTLI_STATE_CONTEXT_MAP_HUFFMAN
: {
1022 uint32_t alphabet_size
= *num_htrees
+ s
->max_run_length_prefix
;
1023 result
= ReadHuffmanCode(alphabet_size
, alphabet_size
,
1024 s
->context_map_table
, NULL
, s
);
1025 if (result
!= BROTLI_DECODER_SUCCESS
) return result
;
1027 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_DECODE
;
1031 case BROTLI_STATE_CONTEXT_MAP_DECODE
: {
1032 uint32_t context_index
= s
->context_index
;
1033 uint32_t max_run_length_prefix
= s
->max_run_length_prefix
;
1034 uint8_t* context_map
= *context_map_arg
;
1035 uint32_t code
= s
->code
;
1036 BROTLI_BOOL skip_preamble
= (code
!= 0xFFFF);
1037 while (context_index
< context_map_size
|| skip_preamble
) {
1038 if (!skip_preamble
) {
1039 if (!SafeReadSymbol(s
->context_map_table
, br
, &code
)) {
1041 s
->context_index
= context_index
;
1042 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1044 BROTLI_LOG_UINT(code
);
1047 context_map
[context_index
++] = 0;
1050 if (code
> max_run_length_prefix
) {
1051 context_map
[context_index
++] =
1052 (uint8_t)(code
- max_run_length_prefix
);
1056 skip_preamble
= BROTLI_FALSE
;
1058 /* RLE sub-stage. */
1061 if (!BrotliSafeReadBits(br
, code
, &reps
)) {
1063 s
->context_index
= context_index
;
1064 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1067 BROTLI_LOG_UINT(reps
);
1068 if (context_index
+ reps
> context_map_size
) {
1070 BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT
);
1073 context_map
[context_index
++] = 0;
1080 case BROTLI_STATE_CONTEXT_MAP_TRANSFORM
: {
1082 if (!BrotliSafeReadBits(br
, 1, &bits
)) {
1083 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_TRANSFORM
;
1084 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1087 InverseMoveToFrontTransform(*context_map_arg
, context_map_size
, s
);
1089 s
->substate_context_map
= BROTLI_STATE_CONTEXT_MAP_NONE
;
1090 return BROTLI_DECODER_SUCCESS
;
1095 BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
1099 /* Decodes a command or literal and updates block type ring-buffer.
1100 Reads 3..54 bits. */
1101 static BROTLI_INLINE BROTLI_BOOL
DecodeBlockTypeAndLength(
1102 int safe
, BrotliDecoderState
* s
, int tree_type
) {
1103 uint32_t max_block_type
= s
->num_block_types
[tree_type
];
1104 const HuffmanCode
* type_tree
= &s
->block_type_trees
[
1105 tree_type
* BROTLI_HUFFMAN_MAX_SIZE_258
];
1106 const HuffmanCode
* len_tree
= &s
->block_len_trees
[
1107 tree_type
* BROTLI_HUFFMAN_MAX_SIZE_26
];
1108 BrotliBitReader
* br
= &s
->br
;
1109 uint32_t* ringbuffer
= &s
->block_type_rb
[tree_type
* 2];
1110 uint32_t block_type
;
1111 if (max_block_type
<= 1) {
1112 return BROTLI_FALSE
;
1115 /* Read 0..15 + 3..39 bits. */
1117 block_type
= ReadSymbol(type_tree
, br
);
1118 s
->block_length
[tree_type
] = ReadBlockLength(len_tree
, br
);
1120 BrotliBitReaderState memento
;
1121 BrotliBitReaderSaveState(br
, &memento
);
1122 if (!SafeReadSymbol(type_tree
, br
, &block_type
)) return BROTLI_FALSE
;
1123 if (!SafeReadBlockLength(s
, &s
->block_length
[tree_type
], len_tree
, br
)) {
1124 s
->substate_read_block_length
= BROTLI_STATE_READ_BLOCK_LENGTH_NONE
;
1125 BrotliBitReaderRestoreState(br
, &memento
);
1126 return BROTLI_FALSE
;
1130 if (block_type
== 1) {
1131 block_type
= ringbuffer
[1] + 1;
1132 } else if (block_type
== 0) {
1133 block_type
= ringbuffer
[0];
1137 if (block_type
>= max_block_type
) {
1138 block_type
-= max_block_type
;
1140 ringbuffer
[0] = ringbuffer
[1];
1141 ringbuffer
[1] = block_type
;
1145 static BROTLI_INLINE
void DetectTrivialLiteralBlockTypes(
1146 BrotliDecoderState
* s
) {
1148 for (i
= 0; i
< 8; ++i
) s
->trivial_literal_contexts
[i
] = 0;
1149 for (i
= 0; i
< s
->num_block_types
[0]; i
++) {
1150 size_t offset
= i
<< BROTLI_LITERAL_CONTEXT_BITS
;
1152 size_t sample
= s
->context_map
[offset
];
1154 for (j
= 0; j
< (1u << BROTLI_LITERAL_CONTEXT_BITS
);) {
1155 BROTLI_REPEAT(4, error
|= s
->context_map
[offset
+ j
++] ^ sample
;)
1158 s
->trivial_literal_contexts
[i
>> 5] |= 1u << (i
& 31);
1163 static BROTLI_INLINE
void PrepareLiteralDecoding(BrotliDecoderState
* s
) {
1164 uint8_t context_mode
;
1166 uint32_t block_type
= s
->block_type_rb
[1];
1167 uint32_t context_offset
= block_type
<< BROTLI_LITERAL_CONTEXT_BITS
;
1168 s
->context_map_slice
= s
->context_map
+ context_offset
;
1169 trivial
= s
->trivial_literal_contexts
[block_type
>> 5];
1170 s
->trivial_literal_context
= (trivial
>> (block_type
& 31)) & 1;
1171 s
->literal_htree
= s
->literal_hgroup
.htrees
[s
->context_map_slice
[0]];
1172 context_mode
= s
->context_modes
[block_type
] & 3;
1173 s
->context_lookup
= BROTLI_CONTEXT_LUT(context_mode
);
1176 /* Decodes the block type and updates the state for literal context.
1177 Reads 3..54 bits. */
1178 static BROTLI_INLINE BROTLI_BOOL
DecodeLiteralBlockSwitchInternal(
1179 int safe
, BrotliDecoderState
* s
) {
1180 if (!DecodeBlockTypeAndLength(safe
, s
, 0)) {
1181 return BROTLI_FALSE
;
1183 PrepareLiteralDecoding(s
);
1187 static void BROTLI_NOINLINE
DecodeLiteralBlockSwitch(BrotliDecoderState
* s
) {
1188 DecodeLiteralBlockSwitchInternal(0, s
);
1191 static BROTLI_BOOL BROTLI_NOINLINE
SafeDecodeLiteralBlockSwitch(
1192 BrotliDecoderState
* s
) {
1193 return DecodeLiteralBlockSwitchInternal(1, s
);
1196 /* Block switch for insert/copy length.
1197 Reads 3..54 bits. */
1198 static BROTLI_INLINE BROTLI_BOOL
DecodeCommandBlockSwitchInternal(
1199 int safe
, BrotliDecoderState
* s
) {
1200 if (!DecodeBlockTypeAndLength(safe
, s
, 1)) {
1201 return BROTLI_FALSE
;
1203 s
->htree_command
= s
->insert_copy_hgroup
.htrees
[s
->block_type_rb
[3]];
1207 static void BROTLI_NOINLINE
DecodeCommandBlockSwitch(BrotliDecoderState
* s
) {
1208 DecodeCommandBlockSwitchInternal(0, s
);
1211 static BROTLI_BOOL BROTLI_NOINLINE
SafeDecodeCommandBlockSwitch(
1212 BrotliDecoderState
* s
) {
1213 return DecodeCommandBlockSwitchInternal(1, s
);
1216 /* Block switch for distance codes.
1217 Reads 3..54 bits. */
1218 static BROTLI_INLINE BROTLI_BOOL
DecodeDistanceBlockSwitchInternal(
1219 int safe
, BrotliDecoderState
* s
) {
1220 if (!DecodeBlockTypeAndLength(safe
, s
, 2)) {
1221 return BROTLI_FALSE
;
1223 s
->dist_context_map_slice
= s
->dist_context_map
+
1224 (s
->block_type_rb
[5] << BROTLI_DISTANCE_CONTEXT_BITS
);
1225 s
->dist_htree_index
= s
->dist_context_map_slice
[s
->distance_context
];
1229 static void BROTLI_NOINLINE
DecodeDistanceBlockSwitch(BrotliDecoderState
* s
) {
1230 DecodeDistanceBlockSwitchInternal(0, s
);
1233 static BROTLI_BOOL BROTLI_NOINLINE
SafeDecodeDistanceBlockSwitch(
1234 BrotliDecoderState
* s
) {
1235 return DecodeDistanceBlockSwitchInternal(1, s
);
1238 static size_t UnwrittenBytes(const BrotliDecoderState
* s
, BROTLI_BOOL wrap
) {
1239 size_t pos
= wrap
&& s
->pos
> s
->ringbuffer_size
?
1240 (size_t)s
->ringbuffer_size
: (size_t)(s
->pos
);
1241 size_t partial_pos_rb
= (s
->rb_roundtrips
* (size_t)s
->ringbuffer_size
) + pos
;
1242 return partial_pos_rb
- s
->partial_pos_out
;
1246 Returns BROTLI_DECODER_NEEDS_MORE_OUTPUT only if there is more output to push
1247 and either ring-buffer is as big as window size, or |force| is true. */
1248 static BrotliDecoderErrorCode BROTLI_NOINLINE
WriteRingBuffer(
1249 BrotliDecoderState
* s
, size_t* available_out
, uint8_t** next_out
,
1250 size_t* total_out
, BROTLI_BOOL force
) {
1252 s
->ringbuffer
+ (s
->partial_pos_out
& (size_t)s
->ringbuffer_mask
);
1253 size_t to_write
= UnwrittenBytes(s
, BROTLI_TRUE
);
1254 size_t num_written
= *available_out
;
1255 if (num_written
> to_write
) {
1256 num_written
= to_write
;
1258 if (s
->meta_block_remaining_len
< 0) {
1259 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1
);
1261 if (next_out
&& !*next_out
) {
1265 memcpy(*next_out
, start
, num_written
);
1266 *next_out
+= num_written
;
1269 *available_out
-= num_written
;
1270 BROTLI_LOG_UINT(to_write
);
1271 BROTLI_LOG_UINT(num_written
);
1272 s
->partial_pos_out
+= num_written
;
1274 *total_out
= s
->partial_pos_out
;
1276 if (num_written
< to_write
) {
1277 if (s
->ringbuffer_size
== (1 << s
->window_bits
) || force
) {
1278 return BROTLI_DECODER_NEEDS_MORE_OUTPUT
;
1280 return BROTLI_DECODER_SUCCESS
;
1283 /* Wrap ring buffer only if it has reached its maximal size. */
1284 if (s
->ringbuffer_size
== (1 << s
->window_bits
) &&
1285 s
->pos
>= s
->ringbuffer_size
) {
1286 s
->pos
-= s
->ringbuffer_size
;
1288 s
->should_wrap_ringbuffer
= (size_t)s
->pos
!= 0 ? 1 : 0;
1290 return BROTLI_DECODER_SUCCESS
;
1293 static void BROTLI_NOINLINE
WrapRingBuffer(BrotliDecoderState
* s
) {
1294 if (s
->should_wrap_ringbuffer
) {
1295 memcpy(s
->ringbuffer
, s
->ringbuffer_end
, (size_t)s
->pos
);
1296 s
->should_wrap_ringbuffer
= 0;
1300 /* Allocates ring-buffer.
1302 s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before
1303 this function is called.
1305 Last two bytes of ring-buffer are initialized to 0, so context calculation
1306 could be done uniformly for the first two and all other positions. */
1307 static BROTLI_BOOL BROTLI_NOINLINE
BrotliEnsureRingBuffer(
1308 BrotliDecoderState
* s
) {
1309 uint8_t* old_ringbuffer
= s
->ringbuffer
;
1310 if (s
->ringbuffer_size
== s
->new_ringbuffer_size
) {
1314 s
->ringbuffer
= (uint8_t*)BROTLI_DECODER_ALLOC(s
,
1315 (size_t)(s
->new_ringbuffer_size
) + kRingBufferWriteAheadSlack
);
1316 if (s
->ringbuffer
== 0) {
1317 /* Restore previous value. */
1318 s
->ringbuffer
= old_ringbuffer
;
1319 return BROTLI_FALSE
;
1321 s
->ringbuffer
[s
->new_ringbuffer_size
- 2] = 0;
1322 s
->ringbuffer
[s
->new_ringbuffer_size
- 1] = 0;
1324 if (!!old_ringbuffer
) {
1325 memcpy(s
->ringbuffer
, old_ringbuffer
, (size_t)s
->pos
);
1326 BROTLI_DECODER_FREE(s
, old_ringbuffer
);
1329 s
->ringbuffer_size
= s
->new_ringbuffer_size
;
1330 s
->ringbuffer_mask
= s
->new_ringbuffer_size
- 1;
1331 s
->ringbuffer_end
= s
->ringbuffer
+ s
->ringbuffer_size
;
1336 static BrotliDecoderErrorCode BROTLI_NOINLINE
CopyUncompressedBlockToOutput(
1337 size_t* available_out
, uint8_t** next_out
, size_t* total_out
,
1338 BrotliDecoderState
* s
) {
1339 /* TODO: avoid allocation for single uncompressed block. */
1340 if (!BrotliEnsureRingBuffer(s
)) {
1341 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1
);
1346 switch (s
->substate_uncompressed
) {
1347 case BROTLI_STATE_UNCOMPRESSED_NONE
: {
1348 int nbytes
= (int)BrotliGetRemainingBytes(&s
->br
);
1349 if (nbytes
> s
->meta_block_remaining_len
) {
1350 nbytes
= s
->meta_block_remaining_len
;
1352 if (s
->pos
+ nbytes
> s
->ringbuffer_size
) {
1353 nbytes
= s
->ringbuffer_size
- s
->pos
;
1355 /* Copy remaining bytes from s->br.buf_ to ring-buffer. */
1356 BrotliCopyBytes(&s
->ringbuffer
[s
->pos
], &s
->br
, (size_t)nbytes
);
1358 s
->meta_block_remaining_len
-= nbytes
;
1359 if (s
->pos
< 1 << s
->window_bits
) {
1360 if (s
->meta_block_remaining_len
== 0) {
1361 return BROTLI_DECODER_SUCCESS
;
1363 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1365 s
->substate_uncompressed
= BROTLI_STATE_UNCOMPRESSED_WRITE
;
1369 case BROTLI_STATE_UNCOMPRESSED_WRITE
: {
1370 BrotliDecoderErrorCode result
;
1371 result
= WriteRingBuffer(
1372 s
, available_out
, next_out
, total_out
, BROTLI_FALSE
);
1373 if (result
!= BROTLI_DECODER_SUCCESS
) {
1376 if (s
->ringbuffer_size
== 1 << s
->window_bits
) {
1377 s
->max_distance
= s
->max_backward_distance
;
1379 s
->substate_uncompressed
= BROTLI_STATE_UNCOMPRESSED_NONE
;
1384 BROTLI_DCHECK(0); /* Unreachable */
1387 /* Calculates the smallest feasible ring buffer.
1389 If we know the data size is small, do not allocate more ring buffer
1390 size than needed to reduce memory usage.
1392 When this method is called, metablock size and flags MUST be decoded. */
1393 static void BROTLI_NOINLINE
BrotliCalculateRingBufferSize(
1394 BrotliDecoderState
* s
) {
1395 int window_size
= 1 << s
->window_bits
;
1396 int new_ringbuffer_size
= window_size
;
1397 /* We need at least 2 bytes of ring buffer size to get the last two
1398 bytes for context from there */
1399 int min_size
= s
->ringbuffer_size
? s
->ringbuffer_size
: 1024;
1402 /* If maximum is already reached, no further extension is retired. */
1403 if (s
->ringbuffer_size
== window_size
) {
1407 /* Metadata blocks does not touch ring buffer. */
1408 if (s
->is_metadata
) {
1412 if (!s
->ringbuffer
) {
1415 output_size
= s
->pos
;
1417 output_size
+= s
->meta_block_remaining_len
;
1418 min_size
= min_size
< output_size
? output_size
: min_size
;
1420 if (!!s
->canny_ringbuffer_allocation
) {
1421 /* Reduce ring buffer size to save memory when server is unscrupulous.
1422 In worst case memory usage might be 1.5x bigger for a short period of
1423 ring buffer reallocation. */
1424 while ((new_ringbuffer_size
>> 1) >= min_size
) {
1425 new_ringbuffer_size
>>= 1;
1429 s
->new_ringbuffer_size
= new_ringbuffer_size
;
1432 /* Reads 1..256 2-bit context modes. */
1433 static BrotliDecoderErrorCode
ReadContextModes(BrotliDecoderState
* s
) {
1434 BrotliBitReader
* br
= &s
->br
;
1435 int i
= s
->loop_counter
;
1437 while (i
< (int)s
->num_block_types
[0]) {
1439 if (!BrotliSafeReadBits(br
, 2, &bits
)) {
1440 s
->loop_counter
= i
;
1441 return BROTLI_DECODER_NEEDS_MORE_INPUT
;
1443 s
->context_modes
[i
] = (uint8_t)bits
;
1444 BROTLI_LOG_ARRAY_INDEX(s
->context_modes
, i
);
1447 return BROTLI_DECODER_SUCCESS
;
1450 static BROTLI_INLINE
void TakeDistanceFromRingBuffer(BrotliDecoderState
* s
) {
1451 if (s
->distance_code
== 0) {
1453 s
->distance_code
= s
->dist_rb
[s
->dist_rb_idx
& 3];
1454 /* Compensate double distance-ring-buffer roll for dictionary items. */
1455 s
->distance_context
= 1;
1457 int distance_code
= s
->distance_code
<< 1;
1458 /* kDistanceShortCodeIndexOffset has 2-bit values from LSB:
1459 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */
1460 const uint32_t kDistanceShortCodeIndexOffset
= 0xAAAFFF1B;
1461 /* kDistanceShortCodeValueOffset has 2-bit values from LSB:
1462 -0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */
1463 const uint32_t kDistanceShortCodeValueOffset
= 0xFA5FA500;
1464 int v
= (s
->dist_rb_idx
+
1465 (int)(kDistanceShortCodeIndexOffset
>> distance_code
)) & 0x3;
1466 s
->distance_code
= s
->dist_rb
[v
];
1467 v
= (int)(kDistanceShortCodeValueOffset
>> distance_code
) & 0x3;
1468 if ((distance_code
& 0x3) != 0) {
1469 s
->distance_code
+= v
;
1471 s
->distance_code
-= v
;
1472 if (s
->distance_code
<= 0) {
1473 /* A huge distance will cause a BROTLI_FAILURE() soon.
1474 This is a little faster than failing here. */
1475 s
->distance_code
= 0x7FFFFFFF;
1481 static BROTLI_INLINE BROTLI_BOOL
SafeReadBits(
1482 BrotliBitReader
* const br
, uint32_t n_bits
, uint32_t* val
) {
1484 return BrotliSafeReadBits(br
, n_bits
, val
);
1491 /* Precondition: s->distance_code < 0. */
1492 static BROTLI_INLINE BROTLI_BOOL
ReadDistanceInternal(
1493 int safe
, BrotliDecoderState
* s
, BrotliBitReader
* br
) {
1495 BrotliBitReaderState memento
;
1496 HuffmanCode
* distance_tree
= s
->distance_hgroup
.htrees
[s
->dist_htree_index
];
1498 s
->distance_code
= (int)ReadSymbol(distance_tree
, br
);
1501 BrotliBitReaderSaveState(br
, &memento
);
1502 if (!SafeReadSymbol(distance_tree
, br
, &code
)) {
1503 return BROTLI_FALSE
;
1505 s
->distance_code
= (int)code
;
1507 /* Convert the distance code to the actual distance by possibly
1508 looking up past distances from the s->ringbuffer. */
1509 s
->distance_context
= 0;
1510 if ((s
->distance_code
& ~0xF) == 0) {
1511 TakeDistanceFromRingBuffer(s
);
1512 --s
->block_length
[2];
1515 distval
= s
->distance_code
- (int)s
->num_direct_distance_codes
;
1520 if (!safe
&& (s
->distance_postfix_bits
== 0)) {
1521 nbits
= ((uint32_t)distval
>> 1) + 1;
1522 offset
= ((2 + (distval
& 1)) << nbits
) - 4;
1523 s
->distance_code
= (int)s
->num_direct_distance_codes
+ offset
+
1524 (int)BrotliReadBits(br
, nbits
);
1526 /* This branch also works well when s->distance_postfix_bits == 0. */
1528 postfix
= distval
& s
->distance_postfix_mask
;
1529 distval
>>= s
->distance_postfix_bits
;
1530 nbits
= ((uint32_t)distval
>> 1) + 1;
1532 if (!SafeReadBits(br
, nbits
, &bits
)) {
1533 s
->distance_code
= -1; /* Restore precondition. */
1534 BrotliBitReaderRestoreState(br
, &memento
);
1535 return BROTLI_FALSE
;
1538 bits
= BrotliReadBits(br
, nbits
);
1540 offset
= ((2 + (distval
& 1)) << nbits
) - 4;
1541 s
->distance_code
= (int)s
->num_direct_distance_codes
+
1542 ((offset
+ (int)bits
) << s
->distance_postfix_bits
) + postfix
;
1545 s
->distance_code
= s
->distance_code
- BROTLI_NUM_DISTANCE_SHORT_CODES
+ 1;
1546 --s
->block_length
[2];
1550 static BROTLI_INLINE
void ReadDistance(
1551 BrotliDecoderState
* s
, BrotliBitReader
* br
) {
1552 ReadDistanceInternal(0, s
, br
);
1555 static BROTLI_INLINE BROTLI_BOOL
SafeReadDistance(
1556 BrotliDecoderState
* s
, BrotliBitReader
* br
) {
1557 return ReadDistanceInternal(1, s
, br
);
1560 static BROTLI_INLINE BROTLI_BOOL
ReadCommandInternal(
1561 int safe
, BrotliDecoderState
* s
, BrotliBitReader
* br
, int* insert_length
) {
1563 uint32_t insert_len_extra
= 0;
1564 uint32_t copy_length
;
1566 BrotliBitReaderState memento
;
1568 cmd_code
= ReadSymbol(s
->htree_command
, br
);
1570 BrotliBitReaderSaveState(br
, &memento
);
1571 if (!SafeReadSymbol(s
->htree_command
, br
, &cmd_code
)) {
1572 return BROTLI_FALSE
;
1575 v
= kCmdLut
[cmd_code
];
1576 s
->distance_code
= v
.distance_code
;
1577 s
->distance_context
= v
.context
;
1578 s
->dist_htree_index
= s
->dist_context_map_slice
[s
->distance_context
];
1579 *insert_length
= v
.insert_len_offset
;
1581 if (BROTLI_PREDICT_FALSE(v
.insert_len_extra_bits
!= 0)) {
1582 insert_len_extra
= BrotliReadBits(br
, v
.insert_len_extra_bits
);
1584 copy_length
= BrotliReadBits(br
, v
.copy_len_extra_bits
);
1586 if (!SafeReadBits(br
, v
.insert_len_extra_bits
, &insert_len_extra
) ||
1587 !SafeReadBits(br
, v
.copy_len_extra_bits
, ©_length
)) {
1588 BrotliBitReaderRestoreState(br
, &memento
);
1589 return BROTLI_FALSE
;
1592 s
->copy_length
= (int)copy_length
+ v
.copy_len_offset
;
1593 --s
->block_length
[1];
1594 *insert_length
+= (int)insert_len_extra
;
1598 static BROTLI_INLINE
void ReadCommand(
1599 BrotliDecoderState
* s
, BrotliBitReader
* br
, int* insert_length
) {
1600 ReadCommandInternal(0, s
, br
, insert_length
);
1603 static BROTLI_INLINE BROTLI_BOOL
SafeReadCommand(
1604 BrotliDecoderState
* s
, BrotliBitReader
* br
, int* insert_length
) {
1605 return ReadCommandInternal(1, s
, br
, insert_length
);
1608 static BROTLI_INLINE BROTLI_BOOL
CheckInputAmount(
1609 int safe
, BrotliBitReader
* const br
, size_t num
) {
1613 return BrotliCheckInputAmount(br
, num
);
1616 #define BROTLI_SAFE(METHOD) \
1619 if (!Safe##METHOD) { \
1620 result = BROTLI_DECODER_NEEDS_MORE_INPUT; \
1621 goto saveStateAndReturn; \
1628 static BROTLI_INLINE BrotliDecoderErrorCode
ProcessCommandsInternal(
1629 int safe
, BrotliDecoderState
* s
) {
1631 int i
= s
->loop_counter
;
1632 BrotliDecoderErrorCode result
= BROTLI_DECODER_SUCCESS
;
1633 BrotliBitReader
* br
= &s
->br
;
1635 if (!CheckInputAmount(safe
, br
, 28)) {
1636 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1637 goto saveStateAndReturn
;
1640 BROTLI_UNUSED(BrotliWarmupBitReader(br
));
1643 /* Jump into state machine. */
1644 if (s
->state
== BROTLI_STATE_COMMAND_BEGIN
) {
1646 } else if (s
->state
== BROTLI_STATE_COMMAND_INNER
) {
1648 } else if (s
->state
== BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
) {
1649 goto CommandPostDecodeLiterals
;
1650 } else if (s
->state
== BROTLI_STATE_COMMAND_POST_WRAP_COPY
) {
1651 goto CommandPostWrapCopy
;
1653 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE
);
1658 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
1660 if (!CheckInputAmount(safe
, br
, 28)) { /* 156 bits + 7 bytes */
1661 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
1662 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1663 goto saveStateAndReturn
;
1665 if (BROTLI_PREDICT_FALSE(s
->block_length
[1] == 0)) {
1666 BROTLI_SAFE(DecodeCommandBlockSwitch(s
));
1669 /* Read the insert/copy length in the command. */
1670 BROTLI_SAFE(ReadCommand(s
, br
, &i
));
1671 BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",
1672 pos
, i
, s
->copy_length
));
1674 goto CommandPostDecodeLiterals
;
1676 s
->meta_block_remaining_len
-= i
;
1680 s
->state
= BROTLI_STATE_COMMAND_INNER
;
1682 /* Read the literals in the command. */
1683 if (s
->trivial_literal_context
) {
1686 PreloadSymbol(safe
, s
->literal_htree
, br
, &bits
, &value
);
1688 if (!CheckInputAmount(safe
, br
, 28)) { /* 162 bits + 7 bytes */
1689 s
->state
= BROTLI_STATE_COMMAND_INNER
;
1690 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1691 goto saveStateAndReturn
;
1693 if (BROTLI_PREDICT_FALSE(s
->block_length
[0] == 0)) {
1694 BROTLI_SAFE(DecodeLiteralBlockSwitch(s
));
1695 PreloadSymbol(safe
, s
->literal_htree
, br
, &bits
, &value
);
1696 if (!s
->trivial_literal_context
) goto CommandInner
;
1699 s
->ringbuffer
[pos
] =
1700 (uint8_t)ReadPreloadedSymbol(s
->literal_htree
, br
, &bits
, &value
);
1703 if (!SafeReadSymbol(s
->literal_htree
, br
, &literal
)) {
1704 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1705 goto saveStateAndReturn
;
1707 s
->ringbuffer
[pos
] = (uint8_t)literal
;
1709 --s
->block_length
[0];
1710 BROTLI_LOG_ARRAY_INDEX(s
->ringbuffer
, pos
);
1712 if (BROTLI_PREDICT_FALSE(pos
== s
->ringbuffer_size
)) {
1713 s
->state
= BROTLI_STATE_COMMAND_INNER_WRITE
;
1715 goto saveStateAndReturn
;
1719 uint8_t p1
= s
->ringbuffer
[(pos
- 1) & s
->ringbuffer_mask
];
1720 uint8_t p2
= s
->ringbuffer
[(pos
- 2) & s
->ringbuffer_mask
];
1722 const HuffmanCode
* hc
;
1724 if (!CheckInputAmount(safe
, br
, 28)) { /* 162 bits + 7 bytes */
1725 s
->state
= BROTLI_STATE_COMMAND_INNER
;
1726 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1727 goto saveStateAndReturn
;
1729 if (BROTLI_PREDICT_FALSE(s
->block_length
[0] == 0)) {
1730 BROTLI_SAFE(DecodeLiteralBlockSwitch(s
));
1731 if (s
->trivial_literal_context
) goto CommandInner
;
1733 context
= BROTLI_CONTEXT(p1
, p2
, s
->context_lookup
);
1734 BROTLI_LOG_UINT(context
);
1735 hc
= s
->literal_hgroup
.htrees
[s
->context_map_slice
[context
]];
1738 p1
= (uint8_t)ReadSymbol(hc
, br
);
1741 if (!SafeReadSymbol(hc
, br
, &literal
)) {
1742 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
1743 goto saveStateAndReturn
;
1745 p1
= (uint8_t)literal
;
1747 s
->ringbuffer
[pos
] = p1
;
1748 --s
->block_length
[0];
1749 BROTLI_LOG_UINT(s
->context_map_slice
[context
]);
1750 BROTLI_LOG_ARRAY_INDEX(s
->ringbuffer
, pos
& s
->ringbuffer_mask
);
1752 if (BROTLI_PREDICT_FALSE(pos
== s
->ringbuffer_size
)) {
1753 s
->state
= BROTLI_STATE_COMMAND_INNER_WRITE
;
1755 goto saveStateAndReturn
;
1759 BROTLI_LOG_UINT(s
->meta_block_remaining_len
);
1760 if (BROTLI_PREDICT_FALSE(s
->meta_block_remaining_len
<= 0)) {
1761 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
1762 goto saveStateAndReturn
;
1765 CommandPostDecodeLiterals
:
1767 s
->state
= BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
;
1769 if (s
->distance_code
>= 0) {
1770 /* Implicit distance case. */
1771 s
->distance_context
= s
->distance_code
? 0 : 1;
1773 s
->distance_code
= s
->dist_rb
[s
->dist_rb_idx
& 3];
1775 /* Read distance code in the command, unless it was implicitly zero. */
1776 if (BROTLI_PREDICT_FALSE(s
->block_length
[2] == 0)) {
1777 BROTLI_SAFE(DecodeDistanceBlockSwitch(s
));
1779 BROTLI_SAFE(ReadDistance(s
, br
));
1781 BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",
1782 pos
, s
->distance_code
));
1783 if (s
->max_distance
!= s
->max_backward_distance
) {
1785 (pos
< s
->max_backward_distance
) ? pos
: s
->max_backward_distance
;
1788 /* Apply copy of LZ77 back-reference, or static dictionary reference if
1789 the distance is larger than the max LZ77 distance */
1790 if (s
->distance_code
> s
->max_distance
) {
1791 /* The maximum allowed distance is BROTLI_MAX_ALLOWED_DISTANCE = 0x7FFFFFFC.
1792 With this choice, no signed overflow can occur after decoding
1793 a special distance code (e.g., after adding 3 to the last distance). */
1794 if (s
->distance_code
> BROTLI_MAX_ALLOWED_DISTANCE
) {
1795 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1796 "len: %d bytes left: %d\n",
1797 pos
, s
->distance_code
, i
, s
->meta_block_remaining_len
));
1798 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DISTANCE
);
1800 if (i
>= BROTLI_MIN_DICTIONARY_WORD_LENGTH
&&
1801 i
<= BROTLI_MAX_DICTIONARY_WORD_LENGTH
) {
1802 int address
= s
->distance_code
- s
->max_distance
- 1;
1803 const BrotliDictionary
* words
= s
->dictionary
;
1804 const BrotliTransforms
* transforms
= s
->transforms
;
1805 int offset
= (int)s
->dictionary
->offsets_by_length
[i
];
1806 uint32_t shift
= s
->dictionary
->size_bits_by_length
[i
];
1808 int mask
= (int)BitMask(shift
);
1809 int word_idx
= address
& mask
;
1810 int transform_idx
= address
>> shift
;
1811 /* Compensate double distance-ring-buffer roll. */
1812 s
->dist_rb_idx
+= s
->distance_context
;
1813 offset
+= word_idx
* i
;
1814 if (BROTLI_PREDICT_FALSE(!words
->data
)) {
1815 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_DICTIONARY_NOT_SET
);
1817 if (transform_idx
< (int)transforms
->num_transforms
) {
1818 const uint8_t* word
= &words
->data
[offset
];
1820 if (transform_idx
== transforms
->cutOffTransforms
[0]) {
1821 memcpy(&s
->ringbuffer
[pos
], word
, (size_t)len
);
1822 BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s]\n",
1825 len
= BrotliTransformDictionaryWord(&s
->ringbuffer
[pos
], word
, len
,
1826 transforms
, transform_idx
);
1827 BROTLI_LOG(("[ProcessCommandsInternal] dictionary word: [%.*s],"
1828 " transform_idx = %d, transformed: [%.*s]\n",
1829 i
, word
, transform_idx
, len
, &s
->ringbuffer
[pos
]));
1832 s
->meta_block_remaining_len
-= len
;
1833 if (pos
>= s
->ringbuffer_size
) {
1834 s
->state
= BROTLI_STATE_COMMAND_POST_WRITE_1
;
1835 goto saveStateAndReturn
;
1838 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1839 "len: %d bytes left: %d\n",
1840 pos
, s
->distance_code
, i
, s
->meta_block_remaining_len
));
1841 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM
);
1844 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
1845 "len: %d bytes left: %d\n",
1846 pos
, s
->distance_code
, i
, s
->meta_block_remaining_len
));
1847 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY
);
1850 int src_start
= (pos
- s
->distance_code
) & s
->ringbuffer_mask
;
1851 uint8_t* copy_dst
= &s
->ringbuffer
[pos
];
1852 uint8_t* copy_src
= &s
->ringbuffer
[src_start
];
1853 int dst_end
= pos
+ i
;
1854 int src_end
= src_start
+ i
;
1855 /* Update the recent distances cache. */
1856 s
->dist_rb
[s
->dist_rb_idx
& 3] = s
->distance_code
;
1858 s
->meta_block_remaining_len
-= i
;
1859 /* There are 32+ bytes of slack in the ring-buffer allocation.
1860 Also, we have 16 short codes, that make these 16 bytes irrelevant
1861 in the ring-buffer. Let's copy over them as a first guess. */
1862 memmove16(copy_dst
, copy_src
);
1863 if (src_end
> pos
&& dst_end
> src_start
) {
1864 /* Regions intersect. */
1865 goto CommandPostWrapCopy
;
1867 if (dst_end
>= s
->ringbuffer_size
|| src_end
>= s
->ringbuffer_size
) {
1868 /* At least one region wraps. */
1869 goto CommandPostWrapCopy
;
1874 memcpy(copy_dst
+ 16, copy_src
+ 16, (size_t)(i
- 16));
1876 /* This branch covers about 45% cases.
1877 Fixed size short copy allows more compiler optimizations. */
1878 memmove16(copy_dst
+ 16, copy_src
+ 16);
1882 BROTLI_LOG_UINT(s
->meta_block_remaining_len
);
1883 if (s
->meta_block_remaining_len
<= 0) {
1884 /* Next metablock, if any. */
1885 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
1886 goto saveStateAndReturn
;
1890 CommandPostWrapCopy
:
1892 int wrap_guard
= s
->ringbuffer_size
- pos
;
1894 s
->ringbuffer
[pos
] =
1895 s
->ringbuffer
[(pos
- s
->distance_code
) & s
->ringbuffer_mask
];
1897 if (BROTLI_PREDICT_FALSE(--wrap_guard
== 0)) {
1898 s
->state
= BROTLI_STATE_COMMAND_POST_WRITE_2
;
1899 goto saveStateAndReturn
;
1903 if (s
->meta_block_remaining_len
<= 0) {
1904 /* Next metablock, if any. */
1905 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
1906 goto saveStateAndReturn
;
1913 s
->loop_counter
= i
;
1919 static BROTLI_NOINLINE BrotliDecoderErrorCode
ProcessCommands(
1920 BrotliDecoderState
* s
) {
1921 return ProcessCommandsInternal(0, s
);
1924 static BROTLI_NOINLINE BrotliDecoderErrorCode
SafeProcessCommands(
1925 BrotliDecoderState
* s
) {
1926 return ProcessCommandsInternal(1, s
);
1929 /* Returns the maximum number of distance symbols which can only represent
1930 distances not exceeding BROTLI_MAX_ALLOWED_DISTANCE. */
1931 static uint32_t BrotliMaxDistanceSymbol(uint32_t ndirect
, uint32_t npostfix
) {
1932 static const uint32_t bound
[BROTLI_MAX_NPOSTFIX
+ 1] = {0, 4, 12, 28};
1933 static const uint32_t diff
[BROTLI_MAX_NPOSTFIX
+ 1] = {73, 126, 228, 424};
1934 uint32_t postfix
= 1U << npostfix
;
1935 if (ndirect
< bound
[npostfix
]) {
1936 return ndirect
+ diff
[npostfix
] + postfix
;
1937 } else if (ndirect
> bound
[npostfix
] + postfix
) {
1938 return ndirect
+ diff
[npostfix
];
1940 return bound
[npostfix
] + diff
[npostfix
] + postfix
;
1944 BrotliDecoderResult
BrotliDecoderDecompress(
1945 size_t encoded_size
, const uint8_t* encoded_buffer
, size_t* decoded_size
,
1946 uint8_t* decoded_buffer
) {
1947 BrotliDecoderState s
;
1948 BrotliDecoderResult result
;
1949 size_t total_out
= 0;
1950 size_t available_in
= encoded_size
;
1951 const uint8_t* next_in
= encoded_buffer
;
1952 size_t available_out
= *decoded_size
;
1953 uint8_t* next_out
= decoded_buffer
;
1954 if (!BrotliDecoderStateInit(&s
, 0, 0, 0)) {
1955 return BROTLI_DECODER_RESULT_ERROR
;
1957 result
= BrotliDecoderDecompressStream(
1958 &s
, &available_in
, &next_in
, &available_out
, &next_out
, &total_out
);
1959 *decoded_size
= total_out
;
1960 BrotliDecoderStateCleanup(&s
);
1961 if (result
!= BROTLI_DECODER_RESULT_SUCCESS
) {
1962 result
= BROTLI_DECODER_RESULT_ERROR
;
1967 /* Invariant: input stream is never overconsumed:
1968 - invalid input implies that the whole stream is invalid -> any amount of
1969 input could be read and discarded
1970 - when result is "needs more input", then at least one more byte is REQUIRED
1971 to complete decoding; all input data MUST be consumed by decoder, so
1972 client could swap the input buffer
1973 - when result is "needs more output" decoder MUST ensure that it doesn't
1974 hold more than 7 bits in bit reader; this saves client from swapping input
1975 buffer ahead of time
1976 - when result is "success" decoder MUST return all unused data back to input
1977 buffer; this is possible because the invariant is held on enter */
1978 BrotliDecoderResult
BrotliDecoderDecompressStream(
1979 BrotliDecoderState
* s
, size_t* available_in
, const uint8_t** next_in
,
1980 size_t* available_out
, uint8_t** next_out
, size_t* total_out
) {
1981 BrotliDecoderErrorCode result
= BROTLI_DECODER_SUCCESS
;
1982 BrotliBitReader
* br
= &s
->br
;
1983 /* Ensure that |total_out| is set, even if no data will ever be pushed out. */
1985 *total_out
= s
->partial_pos_out
;
1987 /* Do not try to process further in a case of unrecoverable error. */
1988 if ((int)s
->error_code
< 0) {
1989 return BROTLI_DECODER_RESULT_ERROR
;
1991 if (*available_out
&& (!next_out
|| !*next_out
)) {
1992 return SaveErrorCode(
1993 s
, BROTLI_FAILURE(BROTLI_DECODER_ERROR_INVALID_ARGUMENTS
));
1995 if (!*available_out
) next_out
= 0;
1996 if (s
->buffer_length
== 0) { /* Just connect bit reader to input stream. */
1997 br
->avail_in
= *available_in
;
1998 br
->next_in
= *next_in
;
2000 /* At least one byte of input is required. More than one byte of input may
2001 be required to complete the transaction -> reading more data must be
2002 done in a loop -> do it in a main loop. */
2003 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2004 br
->next_in
= &s
->buffer
.u8
[0];
2008 if (result
!= BROTLI_DECODER_SUCCESS
) {
2009 /* Error, needs more input/output. */
2010 if (result
== BROTLI_DECODER_NEEDS_MORE_INPUT
) {
2011 if (s
->ringbuffer
!= 0) { /* Pro-actively push output. */
2012 BrotliDecoderErrorCode intermediate_result
= WriteRingBuffer(s
,
2013 available_out
, next_out
, total_out
, BROTLI_TRUE
);
2014 /* WriteRingBuffer checks s->meta_block_remaining_len validity. */
2015 if ((int)intermediate_result
< 0) {
2016 result
= intermediate_result
;
2020 if (s
->buffer_length
!= 0) { /* Used with internal buffer. */
2021 if (br
->avail_in
== 0) {
2022 /* Successfully finished read transaction.
2023 Accumulator contains less than 8 bits, because internal buffer
2024 is expanded byte-by-byte until it is enough to complete read. */
2025 s
->buffer_length
= 0;
2026 /* Switch to input stream and restart. */
2027 result
= BROTLI_DECODER_SUCCESS
;
2028 br
->avail_in
= *available_in
;
2029 br
->next_in
= *next_in
;
2031 } else if (*available_in
!= 0) {
2032 /* Not enough data in buffer, but can take one more byte from
2034 result
= BROTLI_DECODER_SUCCESS
;
2035 s
->buffer
.u8
[s
->buffer_length
] = **next_in
;
2037 br
->avail_in
= s
->buffer_length
;
2040 /* Retry with more data in buffer. */
2043 /* Can't finish reading and no more input. */
2045 } else { /* Input stream doesn't contain enough input. */
2046 /* Copy tail to internal buffer and return. */
2047 *next_in
= br
->next_in
;
2048 *available_in
= br
->avail_in
;
2049 while (*available_in
) {
2050 s
->buffer
.u8
[s
->buffer_length
] = **next_in
;
2060 /* Fail or needs more output. */
2062 if (s
->buffer_length
!= 0) {
2063 /* Just consumed the buffered input and produced some output. Otherwise
2064 it would result in "needs more input". Reset internal buffer. */
2065 s
->buffer_length
= 0;
2067 /* Using input stream in last iteration. When decoder switches to input
2068 stream it has less than 8 bits in accumulator, so it is safe to
2069 return unused accumulator bits there. */
2070 BrotliBitReaderUnload(br
);
2071 *available_in
= br
->avail_in
;
2072 *next_in
= br
->next_in
;
2077 case BROTLI_STATE_UNINITED
:
2078 /* Prepare to the first read. */
2079 if (!BrotliWarmupBitReader(br
)) {
2080 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2083 /* Decode window size. */
2084 result
= DecodeWindowBits(s
, br
); /* Reads 1..8 bits. */
2085 if (result
!= BROTLI_DECODER_SUCCESS
) {
2088 if (s
->large_window
) {
2089 s
->state
= BROTLI_STATE_LARGE_WINDOW_BITS
;
2092 s
->state
= BROTLI_STATE_INITIALIZE
;
2095 case BROTLI_STATE_LARGE_WINDOW_BITS
:
2096 if (!BrotliSafeReadBits(br
, 6, &s
->window_bits
)) {
2097 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2100 if (s
->window_bits
< BROTLI_LARGE_MIN_WBITS
||
2101 s
->window_bits
> BROTLI_LARGE_MAX_WBITS
) {
2102 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS
);
2105 s
->state
= BROTLI_STATE_INITIALIZE
;
2108 case BROTLI_STATE_INITIALIZE
:
2109 BROTLI_LOG_UINT(s
->window_bits
);
2110 /* Maximum distance, see section 9.1. of the spec. */
2111 s
->max_backward_distance
= (1 << s
->window_bits
) - BROTLI_WINDOW_GAP
;
2113 /* Allocate memory for both block_type_trees and block_len_trees. */
2114 s
->block_type_trees
= (HuffmanCode
*)BROTLI_DECODER_ALLOC(s
,
2115 sizeof(HuffmanCode
) * 3 *
2116 (BROTLI_HUFFMAN_MAX_SIZE_258
+ BROTLI_HUFFMAN_MAX_SIZE_26
));
2117 if (s
->block_type_trees
== 0) {
2118 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES
);
2121 s
->block_len_trees
=
2122 s
->block_type_trees
+ 3 * BROTLI_HUFFMAN_MAX_SIZE_258
;
2124 s
->state
= BROTLI_STATE_METABLOCK_BEGIN
;
2127 case BROTLI_STATE_METABLOCK_BEGIN
:
2128 BrotliDecoderStateMetablockBegin(s
);
2129 BROTLI_LOG_UINT(s
->pos
);
2130 s
->state
= BROTLI_STATE_METABLOCK_HEADER
;
2133 case BROTLI_STATE_METABLOCK_HEADER
:
2134 result
= DecodeMetaBlockLength(s
, br
); /* Reads 2 - 31 bits. */
2135 if (result
!= BROTLI_DECODER_SUCCESS
) {
2138 BROTLI_LOG_UINT(s
->is_last_metablock
);
2139 BROTLI_LOG_UINT(s
->meta_block_remaining_len
);
2140 BROTLI_LOG_UINT(s
->is_metadata
);
2141 BROTLI_LOG_UINT(s
->is_uncompressed
);
2142 if (s
->is_metadata
|| s
->is_uncompressed
) {
2143 if (!BrotliJumpToByteBoundary(br
)) {
2144 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1
);
2148 if (s
->is_metadata
) {
2149 s
->state
= BROTLI_STATE_METADATA
;
2152 if (s
->meta_block_remaining_len
== 0) {
2153 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2156 BrotliCalculateRingBufferSize(s
);
2157 if (s
->is_uncompressed
) {
2158 s
->state
= BROTLI_STATE_UNCOMPRESSED
;
2161 s
->loop_counter
= 0;
2162 s
->state
= BROTLI_STATE_HUFFMAN_CODE_0
;
2165 case BROTLI_STATE_UNCOMPRESSED
: {
2166 result
= CopyUncompressedBlockToOutput(
2167 available_out
, next_out
, total_out
, s
);
2168 if (result
!= BROTLI_DECODER_SUCCESS
) {
2171 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2175 case BROTLI_STATE_METADATA
:
2176 for (; s
->meta_block_remaining_len
> 0; --s
->meta_block_remaining_len
) {
2178 /* Read one byte and ignore it. */
2179 if (!BrotliSafeReadBits(br
, 8, &bits
)) {
2180 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2184 if (result
== BROTLI_DECODER_SUCCESS
) {
2185 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2189 case BROTLI_STATE_HUFFMAN_CODE_0
:
2190 if (s
->loop_counter
>= 3) {
2191 s
->state
= BROTLI_STATE_METABLOCK_HEADER_2
;
2194 /* Reads 1..11 bits. */
2195 result
= DecodeVarLenUint8(s
, br
, &s
->num_block_types
[s
->loop_counter
]);
2196 if (result
!= BROTLI_DECODER_SUCCESS
) {
2199 s
->num_block_types
[s
->loop_counter
]++;
2200 BROTLI_LOG_UINT(s
->num_block_types
[s
->loop_counter
]);
2201 if (s
->num_block_types
[s
->loop_counter
] < 2) {
2205 s
->state
= BROTLI_STATE_HUFFMAN_CODE_1
;
2208 case BROTLI_STATE_HUFFMAN_CODE_1
: {
2209 uint32_t alphabet_size
= s
->num_block_types
[s
->loop_counter
] + 2;
2210 int tree_offset
= s
->loop_counter
* BROTLI_HUFFMAN_MAX_SIZE_258
;
2211 result
= ReadHuffmanCode(alphabet_size
, alphabet_size
,
2212 &s
->block_type_trees
[tree_offset
], NULL
, s
);
2213 if (result
!= BROTLI_DECODER_SUCCESS
) break;
2214 s
->state
= BROTLI_STATE_HUFFMAN_CODE_2
;
2218 case BROTLI_STATE_HUFFMAN_CODE_2
: {
2219 uint32_t alphabet_size
= BROTLI_NUM_BLOCK_LEN_SYMBOLS
;
2220 int tree_offset
= s
->loop_counter
* BROTLI_HUFFMAN_MAX_SIZE_26
;
2221 result
= ReadHuffmanCode(alphabet_size
, alphabet_size
,
2222 &s
->block_len_trees
[tree_offset
], NULL
, s
);
2223 if (result
!= BROTLI_DECODER_SUCCESS
) break;
2224 s
->state
= BROTLI_STATE_HUFFMAN_CODE_3
;
2228 case BROTLI_STATE_HUFFMAN_CODE_3
: {
2229 int tree_offset
= s
->loop_counter
* BROTLI_HUFFMAN_MAX_SIZE_26
;
2230 if (!SafeReadBlockLength(s
, &s
->block_length
[s
->loop_counter
],
2231 &s
->block_len_trees
[tree_offset
], br
)) {
2232 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2235 BROTLI_LOG_UINT(s
->block_length
[s
->loop_counter
]);
2237 s
->state
= BROTLI_STATE_HUFFMAN_CODE_0
;
2241 case BROTLI_STATE_METABLOCK_HEADER_2
: {
2243 if (!BrotliSafeReadBits(br
, 6, &bits
)) {
2244 result
= BROTLI_DECODER_NEEDS_MORE_INPUT
;
2247 s
->distance_postfix_bits
= bits
& BitMask(2);
2249 s
->num_direct_distance_codes
= BROTLI_NUM_DISTANCE_SHORT_CODES
+
2250 (bits
<< s
->distance_postfix_bits
);
2251 BROTLI_LOG_UINT(s
->num_direct_distance_codes
);
2252 BROTLI_LOG_UINT(s
->distance_postfix_bits
);
2253 s
->distance_postfix_mask
= (int)BitMask(s
->distance_postfix_bits
);
2255 (uint8_t*)BROTLI_DECODER_ALLOC(s
, (size_t)s
->num_block_types
[0]);
2256 if (s
->context_modes
== 0) {
2257 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES
);
2260 s
->loop_counter
= 0;
2261 s
->state
= BROTLI_STATE_CONTEXT_MODES
;
2265 case BROTLI_STATE_CONTEXT_MODES
:
2266 result
= ReadContextModes(s
);
2267 if (result
!= BROTLI_DECODER_SUCCESS
) {
2270 s
->state
= BROTLI_STATE_CONTEXT_MAP_1
;
2273 case BROTLI_STATE_CONTEXT_MAP_1
:
2274 result
= DecodeContextMap(
2275 s
->num_block_types
[0] << BROTLI_LITERAL_CONTEXT_BITS
,
2276 &s
->num_literal_htrees
, &s
->context_map
, s
);
2277 if (result
!= BROTLI_DECODER_SUCCESS
) {
2280 DetectTrivialLiteralBlockTypes(s
);
2281 s
->state
= BROTLI_STATE_CONTEXT_MAP_2
;
2284 case BROTLI_STATE_CONTEXT_MAP_2
: {
2285 uint32_t num_direct_codes
=
2286 s
->num_direct_distance_codes
- BROTLI_NUM_DISTANCE_SHORT_CODES
;
2287 uint32_t num_distance_codes
= BROTLI_DISTANCE_ALPHABET_SIZE(
2288 s
->distance_postfix_bits
, num_direct_codes
,
2289 (s
->large_window
? BROTLI_LARGE_MAX_DISTANCE_BITS
:
2290 BROTLI_MAX_DISTANCE_BITS
));
2291 uint32_t max_distance_symbol
= (s
->large_window
?
2292 BrotliMaxDistanceSymbol(
2293 num_direct_codes
, s
->distance_postfix_bits
) :
2294 num_distance_codes
);
2295 BROTLI_BOOL allocation_success
= BROTLI_TRUE
;
2296 result
= DecodeContextMap(
2297 s
->num_block_types
[2] << BROTLI_DISTANCE_CONTEXT_BITS
,
2298 &s
->num_dist_htrees
, &s
->dist_context_map
, s
);
2299 if (result
!= BROTLI_DECODER_SUCCESS
) {
2302 allocation_success
&= BrotliDecoderHuffmanTreeGroupInit(
2303 s
, &s
->literal_hgroup
, BROTLI_NUM_LITERAL_SYMBOLS
,
2304 BROTLI_NUM_LITERAL_SYMBOLS
, s
->num_literal_htrees
);
2305 allocation_success
&= BrotliDecoderHuffmanTreeGroupInit(
2306 s
, &s
->insert_copy_hgroup
, BROTLI_NUM_COMMAND_SYMBOLS
,
2307 BROTLI_NUM_COMMAND_SYMBOLS
, s
->num_block_types
[1]);
2308 allocation_success
&= BrotliDecoderHuffmanTreeGroupInit(
2309 s
, &s
->distance_hgroup
, num_distance_codes
,
2310 max_distance_symbol
, s
->num_dist_htrees
);
2311 if (!allocation_success
) {
2312 return SaveErrorCode(s
,
2313 BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS
));
2315 s
->loop_counter
= 0;
2316 s
->state
= BROTLI_STATE_TREE_GROUP
;
2320 case BROTLI_STATE_TREE_GROUP
: {
2321 HuffmanTreeGroup
* hgroup
= NULL
;
2322 switch (s
->loop_counter
) {
2323 case 0: hgroup
= &s
->literal_hgroup
; break;
2324 case 1: hgroup
= &s
->insert_copy_hgroup
; break;
2325 case 2: hgroup
= &s
->distance_hgroup
; break;
2326 default: return SaveErrorCode(s
, BROTLI_FAILURE(
2327 BROTLI_DECODER_ERROR_UNREACHABLE
));
2329 result
= HuffmanTreeGroupDecode(hgroup
, s
);
2330 if (result
!= BROTLI_DECODER_SUCCESS
) break;
2332 if (s
->loop_counter
>= 3) {
2333 PrepareLiteralDecoding(s
);
2334 s
->dist_context_map_slice
= s
->dist_context_map
;
2335 s
->htree_command
= s
->insert_copy_hgroup
.htrees
[0];
2336 if (!BrotliEnsureRingBuffer(s
)) {
2337 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2
);
2340 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
2345 case BROTLI_STATE_COMMAND_BEGIN
:
2347 case BROTLI_STATE_COMMAND_INNER
:
2349 case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
:
2351 case BROTLI_STATE_COMMAND_POST_WRAP_COPY
:
2352 result
= ProcessCommands(s
);
2353 if (result
== BROTLI_DECODER_NEEDS_MORE_INPUT
) {
2354 result
= SafeProcessCommands(s
);
2358 case BROTLI_STATE_COMMAND_INNER_WRITE
:
2360 case BROTLI_STATE_COMMAND_POST_WRITE_1
:
2362 case BROTLI_STATE_COMMAND_POST_WRITE_2
:
2363 result
= WriteRingBuffer(
2364 s
, available_out
, next_out
, total_out
, BROTLI_FALSE
);
2365 if (result
!= BROTLI_DECODER_SUCCESS
) {
2369 if (s
->ringbuffer_size
== 1 << s
->window_bits
) {
2370 s
->max_distance
= s
->max_backward_distance
;
2372 if (s
->state
== BROTLI_STATE_COMMAND_POST_WRITE_1
) {
2373 if (s
->meta_block_remaining_len
== 0) {
2374 /* Next metablock, if any. */
2375 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2377 s
->state
= BROTLI_STATE_COMMAND_BEGIN
;
2380 } else if (s
->state
== BROTLI_STATE_COMMAND_POST_WRITE_2
) {
2381 s
->state
= BROTLI_STATE_COMMAND_POST_WRAP_COPY
;
2382 } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */
2383 if (s
->loop_counter
== 0) {
2384 if (s
->meta_block_remaining_len
== 0) {
2385 s
->state
= BROTLI_STATE_METABLOCK_DONE
;
2387 s
->state
= BROTLI_STATE_COMMAND_POST_DECODE_LITERALS
;
2391 s
->state
= BROTLI_STATE_COMMAND_INNER
;
2395 case BROTLI_STATE_METABLOCK_DONE
:
2396 if (s
->meta_block_remaining_len
< 0) {
2397 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2
);
2400 BrotliDecoderStateCleanupAfterMetablock(s
);
2401 if (!s
->is_last_metablock
) {
2402 s
->state
= BROTLI_STATE_METABLOCK_BEGIN
;
2405 if (!BrotliJumpToByteBoundary(br
)) {
2406 result
= BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2
);
2409 if (s
->buffer_length
== 0) {
2410 BrotliBitReaderUnload(br
);
2411 *available_in
= br
->avail_in
;
2412 *next_in
= br
->next_in
;
2414 s
->state
= BROTLI_STATE_DONE
;
2417 case BROTLI_STATE_DONE
:
2418 if (s
->ringbuffer
!= 0) {
2419 result
= WriteRingBuffer(
2420 s
, available_out
, next_out
, total_out
, BROTLI_TRUE
);
2421 if (result
!= BROTLI_DECODER_SUCCESS
) {
2425 return SaveErrorCode(s
, result
);
2428 return SaveErrorCode(s
, result
);
2431 BROTLI_BOOL
BrotliDecoderHasMoreOutput(const BrotliDecoderState
* s
) {
2432 /* After unrecoverable error remaining output is considered nonsensical. */
2433 if ((int)s
->error_code
< 0) {
2434 return BROTLI_FALSE
;
2436 return TO_BROTLI_BOOL(
2437 s
->ringbuffer
!= 0 && UnwrittenBytes(s
, BROTLI_FALSE
) != 0);
2440 const uint8_t* BrotliDecoderTakeOutput(BrotliDecoderState
* s
, size_t* size
) {
2441 uint8_t* result
= 0;
2442 size_t available_out
= *size
? *size
: 1u << 24;
2443 size_t requested_out
= available_out
;
2444 BrotliDecoderErrorCode status
;
2445 if ((s
->ringbuffer
== 0) || ((int)s
->error_code
< 0)) {
2450 status
= WriteRingBuffer(s
, &available_out
, &result
, 0, BROTLI_TRUE
);
2451 /* Either WriteRingBuffer returns those "success" codes... */
2452 if (status
== BROTLI_DECODER_SUCCESS
||
2453 status
== BROTLI_DECODER_NEEDS_MORE_OUTPUT
) {
2454 *size
= requested_out
- available_out
;
2456 /* ... or stream is broken. Normally this should be caught by
2457 BrotliDecoderDecompressStream, this is just a safeguard. */
2458 if ((int)status
< 0) SaveErrorCode(s
, status
);
2465 BROTLI_BOOL
BrotliDecoderIsUsed(const BrotliDecoderState
* s
) {
2466 return TO_BROTLI_BOOL(s
->state
!= BROTLI_STATE_UNINITED
||
2467 BrotliGetAvailableBits(&s
->br
) != 0);
2470 BROTLI_BOOL
BrotliDecoderIsFinished(const BrotliDecoderState
* s
) {
2471 return TO_BROTLI_BOOL(s
->state
== BROTLI_STATE_DONE
) &&
2472 !BrotliDecoderHasMoreOutput(s
);
2475 BrotliDecoderErrorCode
BrotliDecoderGetErrorCode(const BrotliDecoderState
* s
) {
2476 return (BrotliDecoderErrorCode
)s
->error_code
;
2479 const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c
) {
2481 #define BROTLI_ERROR_CODE_CASE_(PREFIX, NAME, CODE) \
2482 case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;
2483 #define BROTLI_NOTHING_
2484 BROTLI_DECODER_ERROR_CODES_LIST(BROTLI_ERROR_CODE_CASE_
, BROTLI_NOTHING_
)
2485 #undef BROTLI_ERROR_CODE_CASE_
2486 #undef BROTLI_NOTHING_
2487 default: return "INVALID";
2491 uint32_t BrotliDecoderVersion() {
2492 return BROTLI_VERSION
;
2495 #if defined(__cplusplus) || defined(c_plusplus)