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