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, &copy_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