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