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