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