]> git.proxmox.com Git - mirror_edk2.git/blame - MdeModulePkg/Library/BrotliCustomDecompressLib/dec/decode.c
projects / mirror_edk2.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
MdeModulePkg: Fix BrotliCustomDecompressLib potential issue
[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / decode.c
CommitLineData
36ff6d80
SB		 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
841b2590
SB		 13//#include <stdlib.h> /* free, malloc */\r
14//#include <string.h> /* memcpy, memset */\r
15#include <BrotliDecompressLibInternal.h>\r
36ff6d80
SB		 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
36a0d5ca 805 if (code >= BROTLI_NUM_BLOCK_LEN_SYMBOLS) code = BROTLI_NUM_BLOCK_LEN_SYMBOLS - 1;\r
36ff6d80
SB		 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 /* Load endian-aware constant. */\r
859 const uint8_t b0123[4] = {0, 1, 2, 3};\r
860 uint32_t pattern;\r
861 memcpy(&pattern, &b0123, 4);\r
862\r
863 /* Initialize list using 4 consequent values pattern. */\r
864 *(uint32_t*)mtf = pattern;\r
865 do {\r
866 pattern += 0x04040404; /* Advance all 4 values by 4. */\r
867 *(uint32_t*)(mtf + i) = pattern;\r
868 i += 4;\r
869 } while (i <= upper_bound);\r
870\r
871 /* Transform the input. */\r
872 upper_bound = 0;\r
873 for (i = 0; i < v_len; ++i) {\r
874 int index = v[i];\r
875 uint8_t value = mtf[index];\r
36a0d5ca 876 upper_bound |= (uint32_t)v[i];\r
36ff6d80
SB		 877 v[i] = value;\r
878 mtf[-1] = value;\r
36a0d5ca 879 while (index > 0) {\r
36ff6d80
SB		 880 index--;\r
881 mtf[index + 1] = mtf[index];\r
36a0d5ca 882 }\r
36ff6d80
SB		 883 }\r
884 /* Remember amount of elements to be reinitialized. */\r
885 state->mtf_upper_bound = upper_bound;\r
886}\r
887\r
888/* Decodes a series of Huffman table using ReadHuffmanCode function. */\r
889static BrotliDecoderErrorCode HuffmanTreeGroupDecode(\r
890 HuffmanTreeGroup* group, BrotliDecoderState* s) {\r
891 if (s->substate_tree_group != BROTLI_STATE_TREE_GROUP_LOOP) {\r
892 s->next = group->codes;\r
893 s->htree_index = 0;\r
894 s->substate_tree_group = BROTLI_STATE_TREE_GROUP_LOOP;\r
895 }\r
896 while (s->htree_index < group->num_htrees) {\r
897 uint32_t table_size;\r
898 BrotliDecoderErrorCode result =\r
899 ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);\r
900 if (result != BROTLI_DECODER_SUCCESS) return result;\r
901 group->htrees[s->htree_index] = s->next;\r
902 s->next += table_size;\r
903 ++s->htree_index;\r
904 }\r
905 s->substate_tree_group = BROTLI_STATE_TREE_GROUP_NONE;\r
906 return BROTLI_DECODER_SUCCESS;\r
907}\r
908\r
909/* Decodes a context map.\r
910 Decoding is done in 4 phases:\r
911 1) Read auxiliary information (6..16 bits) and allocate memory.\r
912 In case of trivial context map, decoding is finished at this phase.\r
913 2) Decode Huffman table using ReadHuffmanCode function.\r
914 This table will be used for reading context map items.\r
915 3) Read context map items; "0" values could be run-length encoded.\r
916 4) Optionally, apply InverseMoveToFront transform to the resulting map.\r
917 */\r
918static BrotliDecoderErrorCode DecodeContextMap(uint32_t context_map_size,\r
919 uint32_t* num_htrees,\r
920 uint8_t** context_map_arg,\r
921 BrotliDecoderState* s) {\r
922 BrotliBitReader* br = &s->br;\r
923 BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;\r
924\r
925 switch ((int)s->substate_context_map) {\r
926 case BROTLI_STATE_CONTEXT_MAP_NONE:\r
927 result = DecodeVarLenUint8(s, br, num_htrees);\r
928 if (result != BROTLI_DECODER_SUCCESS) {\r
929 return result;\r
930 }\r
931 (*num_htrees)++;\r
932 s->context_index = 0;\r
933 BROTLI_LOG_UINT(context_map_size);\r
934 BROTLI_LOG_UINT(*num_htrees);\r
935 *context_map_arg = (uint8_t*)BROTLI_ALLOC(s, (size_t)context_map_size);\r
936 if (*context_map_arg == 0) {\r
937 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MAP);\r
938 }\r
939 if (*num_htrees <= 1) {\r
940 memset(*context_map_arg, 0, (size_t)context_map_size);\r
941 return BROTLI_DECODER_SUCCESS;\r
942 }\r
943 s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_READ_PREFIX;\r
944 /* No break, continue to next state. */\r
945 case BROTLI_STATE_CONTEXT_MAP_READ_PREFIX: {\r
946 uint32_t bits;\r
947 /* In next stage ReadHuffmanCode uses at least 4 bits, so it is safe\r
948 to peek 4 bits ahead. */\r
949 if (!BrotliSafeGetBits(br, 5, &bits)) {\r
950 return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
951 }\r
952 if ((bits & 1) != 0) { /* Use RLE for zeroes. */\r
953 s->max_run_length_prefix = (bits >> 1) + 1;\r
954 BrotliDropBits(br, 5);\r
955 } else {\r
956 s->max_run_length_prefix = 0;\r
957 BrotliDropBits(br, 1);\r
958 }\r
959 BROTLI_LOG_UINT(s->max_run_length_prefix);\r
960 s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_HUFFMAN;\r
961 /* No break, continue to next state. */\r
962 }\r
963 case BROTLI_STATE_CONTEXT_MAP_HUFFMAN:\r
964 result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,\r
965 s->context_map_table, NULL, s);\r
966 if (result != BROTLI_DECODER_SUCCESS) return result;\r
967 s->code = 0xFFFF;\r
968 s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_DECODE;\r
969 /* No break, continue to next state. */\r
970 case BROTLI_STATE_CONTEXT_MAP_DECODE: {\r
971 uint32_t context_index = s->context_index;\r
972 uint32_t max_run_length_prefix = s->max_run_length_prefix;\r
973 uint8_t* context_map = *context_map_arg;\r
974 uint32_t code = s->code;\r
975 if (code != 0xFFFF) {\r
976 goto rleCode;\r
977 }\r
978 while (context_index < context_map_size) {\r
979 if (!SafeReadSymbol(s->context_map_table, br, &code)) {\r
980 s->code = 0xFFFF;\r
981 s->context_index = context_index;\r
982 return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
983 }\r
984 BROTLI_LOG_UINT(code);\r
985\r
986 if (code == 0) {\r
987 context_map[context_index++] = 0;\r
988 continue;\r
989 }\r
990 if (code > max_run_length_prefix) {\r
991 context_map[context_index++] =\r
992 (uint8_t)(code - max_run_length_prefix);\r
993 continue;\r
994 }\r
995rleCode:\r
996 {\r
997 uint32_t reps;\r
998 if (!BrotliSafeReadBits(br, code, &reps)) {\r
999 s->code = code;\r
1000 s->context_index = context_index;\r
1001 return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1002 }\r
1003 reps += 1U << code;\r
1004 BROTLI_LOG_UINT(reps);\r
1005 if (context_index + reps > context_map_size) {\r
1006 return\r
1007 BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_CONTEXT_MAP_REPEAT);\r
1008 }\r
1009 do {\r
1010 context_map[context_index++] = 0;\r
1011 } while (--reps);\r
1012 }\r
1013 }\r
1014 /* No break, continue to next state. */\r
1015 }\r
1016 case BROTLI_STATE_CONTEXT_MAP_TRANSFORM: {\r
1017 uint32_t bits;\r
1018 if (!BrotliSafeReadBits(br, 1, &bits)) {\r
1019 s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_TRANSFORM;\r
1020 return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1021 }\r
1022 if (bits != 0) {\r
1023 InverseMoveToFrontTransform(*context_map_arg, context_map_size, s);\r
1024 }\r
1025 s->substate_context_map = BROTLI_STATE_CONTEXT_MAP_NONE;\r
1026 return BROTLI_DECODER_SUCCESS;\r
1027 }\r
1028 default:\r
1029 return\r
1030 BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
1031 }\r
1032}\r
1033\r
1034/* Decodes a command or literal and updates block type ringbuffer.\r
1035 Reads 3..54 bits. */\r
1036static BROTLI_INLINE BROTLI_BOOL DecodeBlockTypeAndLength(\r
1037 int safe, BrotliDecoderState* s, int tree_type) {\r
1038 uint32_t max_block_type = s->num_block_types[tree_type];\r
1039 const HuffmanCode* type_tree = &s->block_type_trees[\r
1040 tree_type * BROTLI_HUFFMAN_MAX_SIZE_258];\r
1041 const HuffmanCode* len_tree = &s->block_len_trees[\r
1042 tree_type * BROTLI_HUFFMAN_MAX_SIZE_26];\r
1043 BrotliBitReader* br = &s->br;\r
1044 uint32_t* ringbuffer = &s->block_type_rb[tree_type * 2];\r
1045 uint32_t block_type;\r
1046\r
1047 /* Read 0..15 + 3..39 bits */\r
1048 if (!safe) {\r
1049 block_type = ReadSymbol(type_tree, br);\r
1050 s->block_length[tree_type] = ReadBlockLength(len_tree, br);\r
1051 } else {\r
1052 BrotliBitReaderState memento;\r
1053 BrotliBitReaderSaveState(br, &memento);\r
1054 if (!SafeReadSymbol(type_tree, br, &block_type)) return BROTLI_FALSE;\r
1055 if (!SafeReadBlockLength(s, &s->block_length[tree_type], len_tree, br)) {\r
1056 s->substate_read_block_length = BROTLI_STATE_READ_BLOCK_LENGTH_NONE;\r
1057 BrotliBitReaderRestoreState(br, &memento);\r
1058 return BROTLI_FALSE;\r
1059 }\r
1060 }\r
1061\r
1062 if (block_type == 1) {\r
1063 block_type = ringbuffer[1] + 1;\r
1064 } else if (block_type == 0) {\r
1065 block_type = ringbuffer[0];\r
1066 } else {\r
1067 block_type -= 2;\r
1068 }\r
1069 if (block_type >= max_block_type) {\r
1070 block_type -= max_block_type;\r
1071 }\r
1072 ringbuffer[0] = ringbuffer[1];\r
1073 ringbuffer[1] = block_type;\r
1074 return BROTLI_TRUE;\r
1075}\r
1076\r
1077static BROTLI_INLINE void DetectTrivialLiteralBlockTypes(\r
1078 BrotliDecoderState* s) {\r
1079 size_t i;\r
1080 for (i = 0; i < 8; ++i) s->trivial_literal_contexts[i] = 0;\r
1081 for (i = 0; i < s->num_block_types[0]; i++) {\r
1082 size_t offset = i << BROTLI_LITERAL_CONTEXT_BITS;\r
1083 size_t error = 0;\r
1084 size_t sample = s->context_map[offset];\r
1085 size_t j;\r
1086 for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS);) {\r
1087 BROTLI_REPEAT(4, error |= s->context_map[offset + j++] ^ sample;)\r
1088 }\r
1089 if (error == 0) {\r
1090 s->trivial_literal_contexts[i >> 5] |= 1u << (i & 31);\r
1091 }\r
1092 }\r
1093}\r
1094\r
1095static BROTLI_INLINE void PrepareLiteralDecoding(BrotliDecoderState* s) {\r
1096 uint8_t context_mode;\r
1097 size_t trivial;\r
1098 uint32_t block_type = s->block_type_rb[1];\r
1099 uint32_t context_offset = block_type << BROTLI_LITERAL_CONTEXT_BITS;\r
1100 s->context_map_slice = s->context_map + context_offset;\r
1101 trivial = s->trivial_literal_contexts[block_type >> 5];\r
1102 s->trivial_literal_context = (trivial >> (block_type & 31)) & 1;\r
1103 s->literal_htree = s->literal_hgroup.htrees[s->context_map_slice[0]];\r
1104 context_mode = s->context_modes[block_type];\r
1105 s->context_lookup1 = &kContextLookup[kContextLookupOffsets[context_mode]];\r
1106 s->context_lookup2 = &kContextLookup[kContextLookupOffsets[context_mode + 1]];\r
1107}\r
1108\r
1109/* Decodes the block type and updates the state for literal context.\r
1110 Reads 3..54 bits. */\r
1111static BROTLI_INLINE BROTLI_BOOL DecodeLiteralBlockSwitchInternal(\r
1112 int safe, BrotliDecoderState* s) {\r
1113 if (!DecodeBlockTypeAndLength(safe, s, 0)) {\r
1114 return BROTLI_FALSE;\r
1115 }\r
1116 PrepareLiteralDecoding(s);\r
1117 return BROTLI_TRUE;\r
1118}\r
1119\r
1120static void BROTLI_NOINLINE DecodeLiteralBlockSwitch(BrotliDecoderState* s) {\r
1121 DecodeLiteralBlockSwitchInternal(0, s);\r
1122}\r
1123\r
1124static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeLiteralBlockSwitch(\r
1125 BrotliDecoderState* s) {\r
1126 return DecodeLiteralBlockSwitchInternal(1, s);\r
1127}\r
1128\r
1129/* Block switch for insert/copy length.\r
1130 Reads 3..54 bits. */\r
1131static BROTLI_INLINE BROTLI_BOOL DecodeCommandBlockSwitchInternal(\r
1132 int safe, BrotliDecoderState* s) {\r
1133 if (!DecodeBlockTypeAndLength(safe, s, 1)) {\r
1134 return BROTLI_FALSE;\r
1135 }\r
1136 s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]];\r
1137 return BROTLI_TRUE;\r
1138}\r
1139\r
1140static void BROTLI_NOINLINE DecodeCommandBlockSwitch(BrotliDecoderState* s) {\r
1141 DecodeCommandBlockSwitchInternal(0, s);\r
1142}\r
1143static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeCommandBlockSwitch(\r
1144 BrotliDecoderState* s) {\r
1145 return DecodeCommandBlockSwitchInternal(1, s);\r
1146}\r
1147\r
1148/* Block switch for distance codes.\r
1149 Reads 3..54 bits. */\r
1150static BROTLI_INLINE BROTLI_BOOL DecodeDistanceBlockSwitchInternal(\r
1151 int safe, BrotliDecoderState* s) {\r
1152 if (!DecodeBlockTypeAndLength(safe, s, 2)) {\r
1153 return BROTLI_FALSE;\r
1154 }\r
1155 s->dist_context_map_slice = s->dist_context_map +\r
1156 (s->block_type_rb[5] << BROTLI_DISTANCE_CONTEXT_BITS);\r
1157 s->dist_htree_index = s->dist_context_map_slice[s->distance_context];\r
1158 return BROTLI_TRUE;\r
1159}\r
1160\r
1161static void BROTLI_NOINLINE DecodeDistanceBlockSwitch(BrotliDecoderState* s) {\r
1162 DecodeDistanceBlockSwitchInternal(0, s);\r
1163}\r
1164\r
1165static BROTLI_BOOL BROTLI_NOINLINE SafeDecodeDistanceBlockSwitch(\r
1166 BrotliDecoderState* s) {\r
1167 return DecodeDistanceBlockSwitchInternal(1, s);\r
1168}\r
1169\r
1170static size_t UnwrittenBytes(const BrotliDecoderState* s, BROTLI_BOOL wrap) {\r
1171 size_t pos = wrap && s->pos > s->ringbuffer_size ?\r
1172 (size_t)s->ringbuffer_size : (size_t)(s->pos);\r
1173 size_t partial_pos_rb = (s->rb_roundtrips * (size_t)s->ringbuffer_size) + pos;\r
1174 return partial_pos_rb - s->partial_pos_out;\r
1175}\r
1176\r
1177static BrotliDecoderErrorCode BROTLI_NOINLINE WriteRingBuffer(\r
1178 BrotliDecoderState* s, size_t* available_out, uint8_t** next_out,\r
1179 size_t* total_out) {\r
1180 uint8_t* start =\r
1181 s->ringbuffer + (s->partial_pos_out & (size_t)s->ringbuffer_mask);\r
1182 size_t to_write = UnwrittenBytes(s, BROTLI_TRUE);\r
1183 size_t num_written = *available_out;\r
1184 if (num_written > to_write) {\r
1185 num_written = to_write;\r
1186 }\r
1187 if (s->meta_block_remaining_len < 0) {\r
1188 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_1);\r
1189 }\r
1190 memcpy(*next_out, start, num_written);\r
1191 *next_out += num_written;\r
1192 *available_out -= num_written;\r
1193 BROTLI_LOG_UINT(to_write);\r
1194 BROTLI_LOG_UINT(num_written);\r
1195 s->partial_pos_out += num_written;\r
1196 if (total_out) *total_out = s->partial_pos_out;\r
1197 if (num_written < to_write) {\r
1198 return BROTLI_DECODER_NEEDS_MORE_OUTPUT;\r
1199 }\r
1200\r
1201 if (s->pos >= s->ringbuffer_size) {\r
1202 s->pos -= s->ringbuffer_size;\r
1203 s->rb_roundtrips++;\r
1204 }\r
1205 return BROTLI_DECODER_SUCCESS;\r
1206}\r
1207\r
1208/* Allocates ringbuffer.\r
1209\r
1210 s->ringbuffer_size MUST be updated by BrotliCalculateRingBufferSize before\r
1211 this function is called.\r
1212\r
1213 Last two bytes of ringbuffer are initialized to 0, so context calculation\r
1214 could be done uniformly for the first two and all other positions.\r
1215\r
1216 Custom dictionary, if any, is copied to the end of ringbuffer.\r
1217*/\r
1218static BROTLI_BOOL BROTLI_NOINLINE BrotliAllocateRingBuffer(\r
1219 BrotliDecoderState* s) {\r
1220 /* We need the slack region for the following reasons:\r
1221 - doing up to two 16-byte copies for fast backward copying\r
1222 - inserting transformed dictionary word (5 prefix + 24 base + 8 suffix) */\r
1223 static const int kRingBufferWriteAheadSlack = 42;\r
1224 s->ringbuffer = (uint8_t*)BROTLI_ALLOC(s, (size_t)(s->ringbuffer_size +\r
1225 kRingBufferWriteAheadSlack));\r
1226 if (s->ringbuffer == 0) {\r
1227 return BROTLI_FALSE;\r
1228 }\r
1229\r
1230 s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;\r
1231\r
1232 s->ringbuffer[s->ringbuffer_size - 2] = 0;\r
1233 s->ringbuffer[s->ringbuffer_size - 1] = 0;\r
1234\r
1235 if (s->custom_dict) {\r
1236 memcpy(&s->ringbuffer[(-s->custom_dict_size) & s->ringbuffer_mask],\r
1237 s->custom_dict, (size_t)s->custom_dict_size);\r
1238 }\r
1239\r
1240 return BROTLI_TRUE;\r
1241}\r
1242\r
1243static BrotliDecoderErrorCode BROTLI_NOINLINE CopyUncompressedBlockToOutput(\r
1244 size_t* available_out, uint8_t** next_out, size_t* total_out,\r
1245 BrotliDecoderState* s) {\r
1246 /* TODO: avoid allocation for single uncompressed block. */\r
1247 if (!s->ringbuffer && !BrotliAllocateRingBuffer(s)) {\r
1248 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_1);\r
1249 }\r
1250\r
1251 /* State machine */\r
1252 for (;;) {\r
1253 switch (s->substate_uncompressed) {\r
1254 case BROTLI_STATE_UNCOMPRESSED_NONE: {\r
1255 int nbytes = (int)BrotliGetRemainingBytes(&s->br);\r
1256 if (nbytes > s->meta_block_remaining_len) {\r
1257 nbytes = s->meta_block_remaining_len;\r
1258 }\r
1259 if (s->pos + nbytes > s->ringbuffer_size) {\r
1260 nbytes = s->ringbuffer_size - s->pos;\r
1261 }\r
1262 /* Copy remaining bytes from s->br.buf_ to ringbuffer. */\r
1263 BrotliCopyBytes(&s->ringbuffer[s->pos], &s->br, (size_t)nbytes);\r
1264 s->pos += nbytes;\r
1265 s->meta_block_remaining_len -= nbytes;\r
1266 if (s->pos < s->ringbuffer_size) {\r
1267 if (s->meta_block_remaining_len == 0) {\r
1268 return BROTLI_DECODER_SUCCESS;\r
1269 }\r
1270 return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1271 }\r
1272 s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_WRITE;\r
1273 /* No break, continue to next state */\r
1274 }\r
1275 case BROTLI_STATE_UNCOMPRESSED_WRITE: {\r
1276 BrotliDecoderErrorCode result =\r
1277 WriteRingBuffer(s, available_out, next_out, total_out);\r
1278 if (result != BROTLI_DECODER_SUCCESS) {\r
1279 return result;\r
1280 }\r
1281 s->max_distance = s->max_backward_distance;\r
1282 s->substate_uncompressed = BROTLI_STATE_UNCOMPRESSED_NONE;\r
1283 break;\r
1284 }\r
1285 }\r
1286 }\r
1287 BROTLI_DCHECK(0); /* Unreachable */\r
1288}\r
1289\r
1290BROTLI_BOOL BrotliDecompressedSize(size_t encoded_size,\r
1291 const uint8_t* encoded_buffer,\r
1292 size_t* decoded_size) {\r
1293 size_t total_size = 0;\r
1294 BrotliDecoderState s;\r
1295 BrotliBitReader* br;\r
1296 BrotliDecoderStateInit(&s);\r
1297 br = &s.br;\r
1298 *decoded_size = 0;\r
1299 br->next_in = encoded_buffer;\r
1300 br->avail_in = encoded_size;\r
1301 if (!BrotliWarmupBitReader(br)) return BROTLI_FALSE;\r
1302 DecodeWindowBits(br);\r
1303 while (1) {\r
1304 size_t block_size;\r
1305 if (DecodeMetaBlockLength(&s, br) != BROTLI_DECODER_SUCCESS) {\r
1306 return BROTLI_FALSE;\r
1307 }\r
1308 block_size = (size_t)s.meta_block_remaining_len;\r
1309 if (!s.is_metadata) {\r
1310 if ((block_size + total_size) < total_size) return BROTLI_FALSE;\r
1311 total_size += block_size;\r
1312 }\r
1313 if (s.is_last_metablock) {\r
1314 *decoded_size = total_size;\r
1315 return BROTLI_TRUE;\r
1316 }\r
1317 if (!s.is_uncompressed && !s.is_metadata) return BROTLI_FALSE;\r
1318 if (!BrotliJumpToByteBoundary(br)) return BROTLI_FALSE;\r
1319 BrotliBitReaderUnload(br);\r
1320 if (br->avail_in < block_size) return BROTLI_FALSE;\r
1321 br->avail_in -= block_size;\r
1322 br->next_in += block_size;\r
1323 if (!BrotliWarmupBitReader(br)) return BROTLI_FALSE;\r
1324 }\r
1325}\r
1326\r
1327/* Calculates the smallest feasible ring buffer.\r
1328\r
1329 If we know the data size is small, do not allocate more ringbuffer\r
1330 size than needed to reduce memory usage.\r
1331\r
1332 When this method is called, metablock size and flags MUST be decoded.\r
1333*/\r
1334static void BROTLI_NOINLINE BrotliCalculateRingBufferSize(\r
1335 BrotliDecoderState* s, BrotliBitReader* br) {\r
1336 BROTLI_BOOL is_last = TO_BROTLI_BOOL(s->is_last_metablock);\r
1337 int window_size = 1 << s->window_bits;\r
1338 s->ringbuffer_size = window_size;\r
1339\r
1340 if (s->is_uncompressed) {\r
1341 int next_block_header =\r
1342 BrotliPeekByte(br, (size_t)s->meta_block_remaining_len);\r
1343 if (next_block_header != -1) { /* Peek succeeded */\r
1344 if ((next_block_header & 3) == 3) { /* ISLAST and ISEMPTY */\r
1345 is_last = BROTLI_TRUE;\r
1346 }\r
1347 }\r
1348 }\r
1349\r
1350 /* We need at least 2 bytes of ring buffer size to get the last two\r
1351 bytes for context from there */\r
1352 if (is_last) {\r
1353 int min_size_x2 = (s->meta_block_remaining_len + s->custom_dict_size) * 2;\r
1354 while (s->ringbuffer_size >= min_size_x2 && s->ringbuffer_size > 32) {\r
1355 s->ringbuffer_size >>= 1;\r
1356 }\r
1357 }\r
1358\r
1359 s->ringbuffer_mask = s->ringbuffer_size - 1;\r
1360}\r
1361\r
1362/* Reads 1..256 2-bit context modes. */\r
1363static BrotliDecoderErrorCode ReadContextModes(BrotliDecoderState* s) {\r
1364 BrotliBitReader* br = &s->br;\r
1365 int i = s->loop_counter;\r
1366\r
1367 while (i < (int)s->num_block_types[0]) {\r
1368 uint32_t bits;\r
1369 if (!BrotliSafeReadBits(br, 2, &bits)) {\r
1370 s->loop_counter = i;\r
1371 return BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1372 }\r
1373 s->context_modes[i] = (uint8_t)(bits << 1);\r
1374 BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);\r
1375 i++;\r
1376 }\r
1377 return BROTLI_DECODER_SUCCESS;\r
1378}\r
1379\r
1380static BROTLI_INLINE void TakeDistanceFromRingBuffer(BrotliDecoderState* s) {\r
1381 if (s->distance_code == 0) {\r
1382 --s->dist_rb_idx;\r
1383 s->distance_code = s->dist_rb[s->dist_rb_idx & 3];\r
1384 } else {\r
1385 int distance_code = s->distance_code << 1;\r
1386 /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: */\r
1387 /* 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */\r
1388 const uint32_t kDistanceShortCodeIndexOffset = 0xaaafff1b;\r
1389 /* kDistanceShortCodeValueOffset has 2-bit values from LSB: */\r
1390 /*-0, 0,-0, 0,-1, 1,-2, 2,-3, 3,-1, 1,-2, 2,-3, 3 */\r
1391 const uint32_t kDistanceShortCodeValueOffset = 0xfa5fa500;\r
1392 int v = (s->dist_rb_idx +\r
1393 (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3;\r
1394 s->distance_code = s->dist_rb[v];\r
1395 v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3;\r
1396 if ((distance_code & 0x3) != 0) {\r
1397 s->distance_code += v;\r
1398 } else {\r
1399 s->distance_code -= v;\r
1400 if (s->distance_code <= 0) {\r
1401 /* A huge distance will cause a BROTLI_FAILURE() soon. */\r
1402 /* This is a little faster than failing here. */\r
1403 s->distance_code = 0x0fffffff;\r
1404 }\r
1405 }\r
1406 }\r
1407}\r
1408\r
1409static BROTLI_INLINE BROTLI_BOOL SafeReadBits(\r
1410 BrotliBitReader* const br, uint32_t n_bits, uint32_t* val) {\r
1411 if (n_bits != 0) {\r
1412 return BrotliSafeReadBits(br, n_bits, val);\r
1413 } else {\r
1414 *val = 0;\r
1415 return BROTLI_TRUE;\r
1416 }\r
1417}\r
1418\r
1419/* Precondition: s->distance_code < 0 */\r
1420static BROTLI_INLINE BROTLI_BOOL ReadDistanceInternal(\r
1421 int safe, BrotliDecoderState* s, BrotliBitReader* br) {\r
1422 int distval;\r
1423 BrotliBitReaderState memento;\r
1424 HuffmanCode* distance_tree = s->distance_hgroup.htrees[s->dist_htree_index];\r
1425 if (!safe) {\r
1426 s->distance_code = (int)ReadSymbol(distance_tree, br);\r
1427 } else {\r
1428 uint32_t code;\r
1429 BrotliBitReaderSaveState(br, &memento);\r
1430 if (!SafeReadSymbol(distance_tree, br, &code)) {\r
1431 return BROTLI_FALSE;\r
1432 }\r
1433 s->distance_code = (int)code;\r
1434 }\r
1435 /* Convert the distance code to the actual distance by possibly */\r
1436 /* looking up past distances from the s->ringbuffer. */\r
1437 if ((s->distance_code & ~0xf) == 0) {\r
1438 TakeDistanceFromRingBuffer(s);\r
1439 --s->block_length[2];\r
1440 return BROTLI_TRUE;\r
1441 }\r
1442 distval = s->distance_code - (int)s->num_direct_distance_codes;\r
1443 if (distval >= 0) {\r
1444 uint32_t nbits;\r
1445 int postfix;\r
1446 int offset;\r
1447 if (!safe && (s->distance_postfix_bits == 0)) {\r
1448 nbits = ((uint32_t)distval >> 1) + 1;\r
1449 offset = ((2 + (distval & 1)) << nbits) - 4;\r
1450 s->distance_code = (int)s->num_direct_distance_codes + offset +\r
1451 (int)BrotliReadBits(br, nbits);\r
1452 } else {\r
1453 /* This branch also works well when s->distance_postfix_bits == 0 */\r
1454 uint32_t bits;\r
1455 postfix = distval & s->distance_postfix_mask;\r
1456 distval >>= s->distance_postfix_bits;\r
1457 nbits = ((uint32_t)distval >> 1) + 1;\r
1458 if (safe) {\r
1459 if (!SafeReadBits(br, nbits, &bits)) {\r
1460 s->distance_code = -1; /* Restore precondition. */\r
1461 BrotliBitReaderRestoreState(br, &memento);\r
1462 return BROTLI_FALSE;\r
1463 }\r
1464 } else {\r
1465 bits = BrotliReadBits(br, nbits);\r
1466 }\r
1467 offset = ((2 + (distval & 1)) << nbits) - 4;\r
1468 s->distance_code = (int)s->num_direct_distance_codes +\r
1469 ((offset + (int)bits) << s->distance_postfix_bits) + postfix;\r
1470 }\r
1471 }\r
1472 s->distance_code = s->distance_code - BROTLI_NUM_DISTANCE_SHORT_CODES + 1;\r
1473 --s->block_length[2];\r
1474 return BROTLI_TRUE;\r
1475}\r
1476\r
1477static BROTLI_INLINE void ReadDistance(\r
1478 BrotliDecoderState* s, BrotliBitReader* br) {\r
1479 ReadDistanceInternal(0, s, br);\r
1480}\r
1481\r
1482static BROTLI_INLINE BROTLI_BOOL SafeReadDistance(\r
1483 BrotliDecoderState* s, BrotliBitReader* br) {\r
1484 return ReadDistanceInternal(1, s, br);\r
1485}\r
1486\r
1487static BROTLI_INLINE BROTLI_BOOL ReadCommandInternal(\r
1488 int safe, BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {\r
1489 uint32_t cmd_code;\r
1490 uint32_t insert_len_extra = 0;\r
1491 uint32_t copy_length;\r
1492 CmdLutElement v;\r
1493 BrotliBitReaderState memento;\r
1494 if (!safe) {\r
1495 cmd_code = ReadSymbol(s->htree_command, br);\r
1496 } else {\r
1497 BrotliBitReaderSaveState(br, &memento);\r
1498 if (!SafeReadSymbol(s->htree_command, br, &cmd_code)) {\r
1499 return BROTLI_FALSE;\r
1500 }\r
1501 }\r
36a0d5ca 1502 if (cmd_code >= BROTLI_NUM_COMMAND_SYMBOLS) cmd_code = BROTLI_NUM_COMMAND_SYMBOLS - 1;\r
36ff6d80
SB		 1503 v = kCmdLut[cmd_code];\r
1504 s->distance_code = v.distance_code;\r
1505 s->distance_context = v.context;\r
1506 s->dist_htree_index = s->dist_context_map_slice[s->distance_context];\r
1507 *insert_length = v.insert_len_offset;\r
1508 if (!safe) {\r
1509 if (PREDICT_FALSE(v.insert_len_extra_bits != 0)) {\r
1510 insert_len_extra = BrotliReadBits(br, v.insert_len_extra_bits);\r
1511 }\r
1512 copy_length = BrotliReadBits(br, v.copy_len_extra_bits);\r
1513 } else {\r
1514 if (!SafeReadBits(br, v.insert_len_extra_bits, &insert_len_extra) ||\r
1515 !SafeReadBits(br, v.copy_len_extra_bits, &copy_length)) {\r
1516 BrotliBitReaderRestoreState(br, &memento);\r
1517 return BROTLI_FALSE;\r
1518 }\r
1519 }\r
1520 s->copy_length = (int)copy_length + v.copy_len_offset;\r
1521 --s->block_length[1];\r
1522 *insert_length += (int)insert_len_extra;\r
1523 return BROTLI_TRUE;\r
1524}\r
1525\r
1526static BROTLI_INLINE void ReadCommand(\r
1527 BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {\r
1528 ReadCommandInternal(0, s, br, insert_length);\r
1529}\r
1530\r
1531static BROTLI_INLINE BROTLI_BOOL SafeReadCommand(\r
1532 BrotliDecoderState* s, BrotliBitReader* br, int* insert_length) {\r
1533 return ReadCommandInternal(1, s, br, insert_length);\r
1534}\r
1535\r
1536static BROTLI_INLINE BROTLI_BOOL CheckInputAmount(\r
1537 int safe, BrotliBitReader* const br, size_t num) {\r
1538 if (safe) {\r
1539 return BROTLI_TRUE;\r
1540 }\r
1541 return BrotliCheckInputAmount(br, num);\r
1542}\r
1543\r
1544#define BROTLI_SAFE(METHOD) \\r
1545 { \\r
1546 if (safe) { \\r
1547 if (!Safe##METHOD) { \\r
1548 result = BROTLI_DECODER_NEEDS_MORE_INPUT; \\r
1549 goto saveStateAndReturn; \\r
1550 } \\r
1551 } else { \\r
1552 METHOD; \\r
1553 } \\r
1554 }\r
1555\r
1556static BROTLI_INLINE BrotliDecoderErrorCode ProcessCommandsInternal(\r
1557 int safe, BrotliDecoderState* s) {\r
1558 int pos = s->pos;\r
1559 int i = s->loop_counter;\r
1560 BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;\r
1561 BrotliBitReader* br = &s->br;\r
1562\r
1563 if (!CheckInputAmount(safe, br, 28)) {\r
1564 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1565 goto saveStateAndReturn;\r
1566 }\r
1567 if (!safe) {\r
1568 BROTLI_UNUSED(BrotliWarmupBitReader(br));\r
1569 }\r
1570\r
1571 /* Jump into state machine. */\r
1572 if (s->state == BROTLI_STATE_COMMAND_BEGIN) {\r
1573 goto CommandBegin;\r
1574 } else if (s->state == BROTLI_STATE_COMMAND_INNER) {\r
1575 goto CommandInner;\r
1576 } else if (s->state == BROTLI_STATE_COMMAND_POST_DECODE_LITERALS) {\r
1577 goto CommandPostDecodeLiterals;\r
1578 } else if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) {\r
1579 goto CommandPostWrapCopy;\r
1580 } else {\r
1581 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_UNREACHABLE);\r
1582 }\r
1583\r
1584CommandBegin:\r
1585 if (safe) {\r
1586 s->state = BROTLI_STATE_COMMAND_BEGIN;\r
1587 }\r
1588 if (!CheckInputAmount(safe, br, 28)) { /* 156 bits + 7 bytes */\r
1589 s->state = BROTLI_STATE_COMMAND_BEGIN;\r
1590 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1591 goto saveStateAndReturn;\r
1592 }\r
1593 if (PREDICT_FALSE(s->block_length[1] == 0)) {\r
1594 BROTLI_SAFE(DecodeCommandBlockSwitch(s));\r
1595 goto CommandBegin;\r
1596 }\r
1597 /* Read the insert/copy length in the command */\r
1598 BROTLI_SAFE(ReadCommand(s, br, &i));\r
1599 BROTLI_LOG(("[ProcessCommandsInternal] pos = %d insert = %d copy = %d\n",\r
1600 pos, i, s->copy_length));\r
1601 if (i == 0) {\r
1602 goto CommandPostDecodeLiterals;\r
1603 }\r
1604 s->meta_block_remaining_len -= i;\r
1605\r
1606CommandInner:\r
1607 if (safe) {\r
1608 s->state = BROTLI_STATE_COMMAND_INNER;\r
1609 }\r
1610 /* Read the literals in the command */\r
1611 if (s->trivial_literal_context) {\r
1612 uint32_t bits;\r
1613 uint32_t value;\r
1614 PreloadSymbol(safe, s->literal_htree, br, &bits, &value);\r
1615 do {\r
1616 if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */\r
1617 s->state = BROTLI_STATE_COMMAND_INNER;\r
1618 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1619 goto saveStateAndReturn;\r
1620 }\r
1621 if (PREDICT_FALSE(s->block_length[0] == 0)) {\r
1622 BROTLI_SAFE(DecodeLiteralBlockSwitch(s));\r
1623 PreloadSymbol(safe, s->literal_htree, br, &bits, &value);\r
1624 if (!s->trivial_literal_context) goto CommandInner;\r
1625 }\r
1626 if (!safe) {\r
1627 s->ringbuffer[pos] =\r
1628 (uint8_t)ReadPreloadedSymbol(s->literal_htree, br, &bits, &value);\r
1629 } else {\r
1630 uint32_t literal;\r
1631 if (!SafeReadSymbol(s->literal_htree, br, &literal)) {\r
1632 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1633 goto saveStateAndReturn;\r
1634 }\r
1635 s->ringbuffer[pos] = (uint8_t)literal;\r
1636 }\r
1637 --s->block_length[0];\r
1638 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos);\r
1639 ++pos;\r
1640 if (PREDICT_FALSE(pos == s->ringbuffer_size)) {\r
1641 s->state = BROTLI_STATE_COMMAND_INNER_WRITE;\r
1642 --i;\r
1643 goto saveStateAndReturn;\r
1644 }\r
1645 } while (--i != 0);\r
1646 } else {\r
1647 uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];\r
1648 uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];\r
1649 do {\r
1650 const HuffmanCode* hc;\r
1651 uint8_t context;\r
1652 if (!CheckInputAmount(safe, br, 28)) { /* 162 bits + 7 bytes */\r
1653 s->state = BROTLI_STATE_COMMAND_INNER;\r
1654 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1655 goto saveStateAndReturn;\r
1656 }\r
1657 if (PREDICT_FALSE(s->block_length[0] == 0)) {\r
1658 BROTLI_SAFE(DecodeLiteralBlockSwitch(s));\r
1659 if (s->trivial_literal_context) goto CommandInner;\r
1660 }\r
1661 context = s->context_lookup1[p1] | s->context_lookup2[p2];\r
1662 BROTLI_LOG_UINT(context);\r
1663 hc = s->literal_hgroup.htrees[s->context_map_slice[context]];\r
1664 p2 = p1;\r
1665 if (!safe) {\r
1666 p1 = (uint8_t)ReadSymbol(hc, br);\r
1667 } else {\r
1668 uint32_t literal;\r
1669 if (!SafeReadSymbol(hc, br, &literal)) {\r
1670 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1671 goto saveStateAndReturn;\r
1672 }\r
1673 p1 = (uint8_t)literal;\r
1674 }\r
1675 s->ringbuffer[pos] = p1;\r
1676 --s->block_length[0];\r
1677 BROTLI_LOG_UINT(s->context_map_slice[context]);\r
1678 BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);\r
1679 ++pos;\r
1680 if (PREDICT_FALSE(pos == s->ringbuffer_size)) {\r
1681 s->state = BROTLI_STATE_COMMAND_INNER_WRITE;\r
1682 --i;\r
1683 goto saveStateAndReturn;\r
1684 }\r
1685 } while (--i != 0);\r
1686 }\r
1687 BROTLI_LOG_UINT(s->meta_block_remaining_len);\r
1688 if (PREDICT_FALSE(s->meta_block_remaining_len <= 0)) {\r
1689 s->state = BROTLI_STATE_METABLOCK_DONE;\r
1690 goto saveStateAndReturn;\r
1691 }\r
1692\r
1693CommandPostDecodeLiterals:\r
1694 if (safe) {\r
1695 s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;\r
1696 }\r
1697 if (s->distance_code >= 0) {\r
1698 --s->dist_rb_idx;\r
1699 s->distance_code = s->dist_rb[s->dist_rb_idx & 3];\r
1700 goto postReadDistance; /* We already have the implicit distance */\r
1701 }\r
1702 /* Read distance code in the command, unless it was implicitly zero. */\r
1703 if (PREDICT_FALSE(s->block_length[2] == 0)) {\r
1704 BROTLI_SAFE(DecodeDistanceBlockSwitch(s));\r
1705 }\r
1706 BROTLI_SAFE(ReadDistance(s, br));\r
1707postReadDistance:\r
1708 BROTLI_LOG(("[ProcessCommandsInternal] pos = %d distance = %d\n",\r
1709 pos, s->distance_code));\r
1710 if (s->max_distance != s->max_backward_distance) {\r
1711 if (pos < s->max_backward_distance_minus_custom_dict_size) {\r
1712 s->max_distance = pos + s->custom_dict_size;\r
1713 } else {\r
1714 s->max_distance = s->max_backward_distance;\r
1715 }\r
1716 }\r
1717 i = s->copy_length;\r
1718 /* Apply copy of LZ77 back-reference, or static dictionary reference if\r
1719 the distance is larger than the max LZ77 distance */\r
1720 if (s->distance_code > s->max_distance) {\r
1721 if (i >= kBrotliMinDictionaryWordLength &&\r
1722 i <= kBrotliMaxDictionaryWordLength) {\r
1723 int offset = (int)kBrotliDictionaryOffsetsByLength[i];\r
1724 int word_id = s->distance_code - s->max_distance - 1;\r
1725 uint32_t shift = kBrotliDictionarySizeBitsByLength[i];\r
1726 int mask = (int)BitMask(shift);\r
1727 int word_idx = word_id & mask;\r
1728 int transform_idx = word_id >> shift;\r
1729 offset += word_idx * i;\r
1730 if (transform_idx < kNumTransforms) {\r
1731 const uint8_t* word = &kBrotliDictionary[offset];\r
1732 int len = i;\r
1733 if (transform_idx == 0) {\r
1734 memcpy(&s->ringbuffer[pos], word, (size_t)len);\r
1735 } else {\r
1736 len = TransformDictionaryWord(\r
1737 &s->ringbuffer[pos], word, len, transform_idx);\r
1738 }\r
1739 pos += len;\r
1740 s->meta_block_remaining_len -= len;\r
1741 if (pos >= s->ringbuffer_size) {\r
1742 /*s->partial_pos_rb += (size_t)s->ringbuffer_size;*/\r
1743 s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;\r
1744 goto saveStateAndReturn;\r
1745 }\r
1746 } else {\r
1747 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "\r
1748 "len: %d bytes left: %d\n",\r
1749 pos, s->distance_code, i, s->meta_block_remaining_len));\r
1750 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_TRANSFORM);\r
1751 }\r
1752 } else {\r
1753 BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "\r
1754 "len: %d bytes left: %d\n",\r
1755 pos, s->distance_code, i, s->meta_block_remaining_len));\r
1756 return BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_DICTIONARY);\r
1757 }\r
1758 } else {\r
1759 int src_start = (pos - s->distance_code) & s->ringbuffer_mask;\r
1760 uint8_t* copy_dst = &s->ringbuffer[pos];\r
1761 uint8_t* copy_src = &s->ringbuffer[src_start];\r
1762 int dst_end = pos + i;\r
1763 int src_end = src_start + i;\r
1764 /* update the recent distances cache */\r
1765 s->dist_rb[s->dist_rb_idx & 3] = s->distance_code;\r
1766 ++s->dist_rb_idx;\r
1767 s->meta_block_remaining_len -= i;\r
1768 /* There are 32+ bytes of slack in the ringbuffer allocation.\r
1769 Also, we have 16 short codes, that make these 16 bytes irrelevant\r
1770 in the ringbuffer. Let's copy over them as a first guess.\r
1771 */\r
1772 memmove16(copy_dst, copy_src);\r
1773 if (src_end > pos && dst_end > src_start) {\r
1774 /* Regions intersect. */\r
1775 goto CommandPostWrapCopy;\r
1776 }\r
1777 if (dst_end >= s->ringbuffer_size || src_end >= s->ringbuffer_size) {\r
1778 /* At least one region wraps. */\r
1779 goto CommandPostWrapCopy;\r
1780 }\r
1781 pos += i;\r
1782 if (i > 16) {\r
1783 if (i > 32) {\r
1784 memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16));\r
1785 } else {\r
1786 /* This branch covers about 45% cases.\r
1787 Fixed size short copy allows more compiler optimizations. */\r
1788 memmove16(copy_dst + 16, copy_src + 16);\r
1789 }\r
1790 }\r
1791 }\r
1792 BROTLI_LOG_UINT(s->meta_block_remaining_len);\r
1793 if (s->meta_block_remaining_len <= 0) {\r
1794 /* Next metablock, if any */\r
1795 s->state = BROTLI_STATE_METABLOCK_DONE;\r
1796 goto saveStateAndReturn;\r
1797 } else {\r
1798 goto CommandBegin;\r
1799 }\r
1800CommandPostWrapCopy:\r
1801 {\r
1802 int wrap_guard = s->ringbuffer_size - pos;\r
1803 while (--i >= 0) {\r
1804 s->ringbuffer[pos] =\r
1805 s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];\r
1806 ++pos;\r
1807 if (PREDICT_FALSE(--wrap_guard == 0)) {\r
1808 s->state = BROTLI_STATE_COMMAND_POST_WRITE_2;\r
1809 goto saveStateAndReturn;\r
1810 }\r
1811 }\r
1812 }\r
1813 if (s->meta_block_remaining_len <= 0) {\r
1814 /* Next metablock, if any */\r
1815 s->state = BROTLI_STATE_METABLOCK_DONE;\r
1816 goto saveStateAndReturn;\r
1817 } else {\r
1818 goto CommandBegin;\r
1819 }\r
1820\r
1821saveStateAndReturn:\r
1822 s->pos = pos;\r
1823 s->loop_counter = i;\r
1824 return result;\r
1825}\r
1826\r
1827#undef BROTLI_SAFE\r
1828\r
1829static BROTLI_NOINLINE BrotliDecoderErrorCode ProcessCommands(\r
1830 BrotliDecoderState* s) {\r
1831 return ProcessCommandsInternal(0, s);\r
1832}\r
1833\r
1834static BROTLI_NOINLINE BrotliDecoderErrorCode SafeProcessCommands(\r
1835 BrotliDecoderState* s) {\r
1836 return ProcessCommandsInternal(1, s);\r
1837}\r
1838\r
1839BrotliDecoderResult BrotliDecoderDecompress(\r
1840 size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,\r
1841 uint8_t* decoded_buffer) {\r
1842 BrotliDecoderState s;\r
1843 BrotliDecoderResult result;\r
1844 size_t total_out = 0;\r
1845 size_t available_in = encoded_size;\r
1846 const uint8_t* next_in = encoded_buffer;\r
1847 size_t available_out = *decoded_size;\r
1848 uint8_t* next_out = decoded_buffer;\r
1849 BrotliDecoderStateInit(&s);\r
1850 result = BrotliDecoderDecompressStream(\r
1851 &s, &available_in, &next_in, &available_out, &next_out, &total_out);\r
1852 *decoded_size = total_out;\r
1853 BrotliDecoderStateCleanup(&s);\r
1854 if (result != BROTLI_DECODER_RESULT_SUCCESS) {\r
1855 result = BROTLI_DECODER_RESULT_ERROR;\r
1856 }\r
1857 return result;\r
1858}\r
1859\r
1860/* Invariant: input stream is never overconsumed:\r
1861 * invalid input implies that the whole stream is invalid -> any amount of\r
1862 input could be read and discarded\r
1863 * when result is "needs more input", then at leat one more byte is REQUIRED\r
1864 to complete decoding; all input data MUST be consumed by decoder, so\r
1865 client could swap the input buffer\r
1866 * when result is "needs more output" decoder MUST ensure that it doesn't\r
1867 hold more than 7 bits in bit reader; this saves client from swapping input\r
1868 buffer ahead of time\r
1869 * when result is "success" decoder MUST return all unused data back to input\r
1870 buffer; this is possible because the invariant is hold on enter\r
1871*/\r
1872BrotliDecoderResult BrotliDecoderDecompressStream(\r
1873 BrotliDecoderState* s, size_t* available_in, const uint8_t** next_in,\r
1874 size_t* available_out, uint8_t** next_out, size_t* total_out) {\r
1875 BrotliDecoderErrorCode result = BROTLI_DECODER_SUCCESS;\r
1876 BrotliBitReader* br = &s->br;\r
1877 if (s->buffer_length == 0) { /* Just connect bit reader to input stream. */\r
1878 br->avail_in = *available_in;\r
1879 br->next_in = *next_in;\r
1880 } else {\r
1881 /* At least one byte of input is required. More than one byte of input may\r
1882 be required to complete the transaction -> reading more data must be\r
1883 done in a loop -> do it in a main loop. */\r
1884 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1885 br->next_in = &s->buffer.u8[0];\r
1886 }\r
1887 /* State machine */\r
1888 for (;;) {\r
1889 if (result != BROTLI_DECODER_SUCCESS) { /* Error, needs more input/output */\r
1890 if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {\r
1891 if (s->ringbuffer != 0) { /* Proactively push output. */\r
1892 WriteRingBuffer(s, available_out, next_out, total_out);\r
1893 }\r
1894 if (s->buffer_length != 0) { /* Used with internal buffer. */\r
1895 if (br->avail_in == 0) { /* Successfully finished read transaction. */\r
1896 /* Accamulator contains less than 8 bits, because internal buffer\r
1897 is expanded byte-by-byte until it is enough to complete read. */\r
1898 s->buffer_length = 0;\r
1899 /* Switch to input stream and restart. */\r
1900 result = BROTLI_DECODER_SUCCESS;\r
1901 br->avail_in = *available_in;\r
1902 br->next_in = *next_in;\r
1903 continue;\r
1904 } else if (*available_in != 0) {\r
1905 /* Not enough data in buffer, but can take one more byte from\r
1906 input stream. */\r
1907 result = BROTLI_DECODER_SUCCESS;\r
1908 s->buffer.u8[s->buffer_length] = **next_in;\r
1909 s->buffer_length++;\r
1910 br->avail_in = s->buffer_length;\r
1911 (*next_in)++;\r
1912 (*available_in)--;\r
1913 /* Retry with more data in buffer. */\r
1914 continue;\r
1915 }\r
1916 /* Can't finish reading and no more input.*/\r
1917 break;\r
1918 } else { /* Input stream doesn't contain enough input. */\r
1919 /* Copy tail to internal buffer and return. */\r
1920 *next_in = br->next_in;\r
1921 *available_in = br->avail_in;\r
1922 while (*available_in) {\r
1923 s->buffer.u8[s->buffer_length] = **next_in;\r
1924 s->buffer_length++;\r
1925 (*next_in)++;\r
1926 (*available_in)--;\r
1927 }\r
1928 break;\r
1929 }\r
1930 /* Unreachable. */\r
1931 }\r
1932\r
1933 /* Fail or needs more output. */\r
1934\r
1935 if (s->buffer_length != 0) {\r
1936 /* Just consumed the buffered input and produced some output. Otherwise\r
1937 it would result in "needs more input". Reset internal buffer.*/\r
1938 s->buffer_length = 0;\r
1939 } else {\r
1940 /* Using input stream in last iteration. When decoder switches to input\r
1941 stream it has less than 8 bits in accamulator, so it is safe to\r
1942 return unused accamulator bits there. */\r
1943 BrotliBitReaderUnload(br);\r
1944 *available_in = br->avail_in;\r
1945 *next_in = br->next_in;\r
1946 }\r
1947 break;\r
1948 }\r
1949 switch (s->state) {\r
1950 case BROTLI_STATE_UNINITED:\r
1951 /* Prepare to the first read. */\r
1952 if (!BrotliWarmupBitReader(br)) {\r
1953 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
1954 break;\r
1955 }\r
1956 /* Decode window size. */\r
1957 s->window_bits = DecodeWindowBits(br); /* Reads 1..7 bits. */\r
1958 BROTLI_LOG_UINT(s->window_bits);\r
1959 if (s->window_bits == 9) {\r
1960 /* Value 9 is reserved for future use. */\r
1961 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_WINDOW_BITS);\r
1962 break;\r
1963 }\r
1964 /* Maximum distance, see section 9.1. of the spec. */\r
1965 s->max_backward_distance = (1 << s->window_bits) - 16;\r
1966 /* Limit custom dictionary size. */\r
1967 if (s->custom_dict_size >= s->max_backward_distance) {\r
1968 s->custom_dict += s->custom_dict_size - s->max_backward_distance;\r
1969 s->custom_dict_size = s->max_backward_distance;\r
1970 }\r
1971 s->max_backward_distance_minus_custom_dict_size =\r
1972 s->max_backward_distance - s->custom_dict_size;\r
1973\r
1974 /* Allocate memory for both block_type_trees and block_len_trees. */\r
1975 s->block_type_trees = (HuffmanCode*)BROTLI_ALLOC(s,\r
1976 sizeof(HuffmanCode) * 3 *\r
1977 (BROTLI_HUFFMAN_MAX_SIZE_258 + BROTLI_HUFFMAN_MAX_SIZE_26));\r
1978 if (s->block_type_trees == 0) {\r
1979 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_BLOCK_TYPE_TREES);\r
1980 break;\r
1981 }\r
1982 s->block_len_trees =\r
1983 s->block_type_trees + 3 * BROTLI_HUFFMAN_MAX_SIZE_258;\r
1984\r
1985 s->state = BROTLI_STATE_METABLOCK_BEGIN;\r
1986 /* No break, continue to next state */\r
1987 case BROTLI_STATE_METABLOCK_BEGIN:\r
1988 BrotliDecoderStateMetablockBegin(s);\r
1989 BROTLI_LOG_UINT(s->pos);\r
1990 s->state = BROTLI_STATE_METABLOCK_HEADER;\r
1991 /* No break, continue to next state */\r
1992 case BROTLI_STATE_METABLOCK_HEADER:\r
1993 result = DecodeMetaBlockLength(s, br); /* Reads 2 - 31 bits. */\r
1994 if (result != BROTLI_DECODER_SUCCESS) {\r
1995 break;\r
1996 }\r
1997 BROTLI_LOG_UINT(s->is_last_metablock);\r
1998 BROTLI_LOG_UINT(s->meta_block_remaining_len);\r
1999 BROTLI_LOG_UINT(s->is_metadata);\r
2000 BROTLI_LOG_UINT(s->is_uncompressed);\r
2001 if (s->is_metadata || s->is_uncompressed) {\r
2002 if (!BrotliJumpToByteBoundary(br)) {\r
2003 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_1);\r
2004 break;\r
2005 }\r
2006 }\r
2007 if (s->is_metadata) {\r
2008 s->state = BROTLI_STATE_METADATA;\r
2009 break;\r
2010 }\r
2011 if (s->meta_block_remaining_len == 0) {\r
2012 s->state = BROTLI_STATE_METABLOCK_DONE;\r
2013 break;\r
2014 }\r
2015 if (!s->ringbuffer) {\r
2016 BrotliCalculateRingBufferSize(s, br);\r
2017 }\r
2018 if (s->is_uncompressed) {\r
2019 s->state = BROTLI_STATE_UNCOMPRESSED;\r
2020 break;\r
2021 }\r
2022 s->loop_counter = 0;\r
2023 s->state = BROTLI_STATE_HUFFMAN_CODE_0;\r
2024 break;\r
2025 case BROTLI_STATE_UNCOMPRESSED: {\r
2026 int bytes_copied = s->meta_block_remaining_len;\r
2027 result = CopyUncompressedBlockToOutput(\r
2028 available_out, next_out, total_out, s);\r
2029 bytes_copied -= s->meta_block_remaining_len;\r
2030 if (result != BROTLI_DECODER_SUCCESS) {\r
2031 break;\r
2032 }\r
2033 s->state = BROTLI_STATE_METABLOCK_DONE;\r
2034 break;\r
2035 }\r
2036 case BROTLI_STATE_METADATA:\r
2037 for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {\r
2038 uint32_t bits;\r
2039 /* Read one byte and ignore it. */\r
2040 if (!BrotliSafeReadBits(br, 8, &bits)) {\r
2041 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
2042 break;\r
2043 }\r
2044 }\r
2045 if (result == BROTLI_DECODER_SUCCESS) {\r
2046 s->state = BROTLI_STATE_METABLOCK_DONE;\r
2047 }\r
2048 break;\r
2049 case BROTLI_STATE_HUFFMAN_CODE_0:\r
2050 if (s->loop_counter >= 3) {\r
2051 s->state = BROTLI_STATE_METABLOCK_HEADER_2;\r
2052 break;\r
2053 }\r
2054 /* Reads 1..11 bits. */\r
2055 result = DecodeVarLenUint8(s, br, &s->num_block_types[s->loop_counter]);\r
2056 if (result != BROTLI_DECODER_SUCCESS) {\r
2057 break;\r
2058 }\r
2059 s->num_block_types[s->loop_counter]++;\r
2060 BROTLI_LOG_UINT(s->num_block_types[s->loop_counter]);\r
2061 if (s->num_block_types[s->loop_counter] < 2) {\r
2062 s->loop_counter++;\r
2063 break;\r
2064 }\r
2065 s->state = BROTLI_STATE_HUFFMAN_CODE_1;\r
2066 /* No break, continue to next state */\r
2067 case BROTLI_STATE_HUFFMAN_CODE_1: {\r
2068 int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_258;\r
2069 result = ReadHuffmanCode(s->num_block_types[s->loop_counter] + 2,\r
2070 &s->block_type_trees[tree_offset], NULL, s);\r
2071 if (result != BROTLI_DECODER_SUCCESS) break;\r
2072 s->state = BROTLI_STATE_HUFFMAN_CODE_2;\r
2073 /* No break, continue to next state */\r
2074 }\r
2075 case BROTLI_STATE_HUFFMAN_CODE_2: {\r
2076 int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;\r
2077 result = ReadHuffmanCode(BROTLI_NUM_BLOCK_LEN_SYMBOLS,\r
2078 &s->block_len_trees[tree_offset], NULL, s);\r
2079 if (result != BROTLI_DECODER_SUCCESS) break;\r
2080 s->state = BROTLI_STATE_HUFFMAN_CODE_3;\r
2081 /* No break, continue to next state */\r
2082 }\r
2083 case BROTLI_STATE_HUFFMAN_CODE_3: {\r
2084 int tree_offset = s->loop_counter * BROTLI_HUFFMAN_MAX_SIZE_26;\r
2085 if (!SafeReadBlockLength(s, &s->block_length[s->loop_counter],\r
2086 &s->block_len_trees[tree_offset], br)) {\r
2087 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
2088 break;\r
2089 }\r
2090 BROTLI_LOG_UINT(s->block_length[s->loop_counter]);\r
2091 s->loop_counter++;\r
2092 s->state = BROTLI_STATE_HUFFMAN_CODE_0;\r
2093 break;\r
2094 }\r
2095 case BROTLI_STATE_METABLOCK_HEADER_2: {\r
2096 uint32_t bits;\r
2097 if (!BrotliSafeReadBits(br, 6, &bits)) {\r
2098 result = BROTLI_DECODER_NEEDS_MORE_INPUT;\r
2099 break;\r
2100 }\r
2101 s->distance_postfix_bits = bits & BitMask(2);\r
2102 bits >>= 2;\r
2103 s->num_direct_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES +\r
2104 (bits << s->distance_postfix_bits);\r
2105 BROTLI_LOG_UINT(s->num_direct_distance_codes);\r
2106 BROTLI_LOG_UINT(s->distance_postfix_bits);\r
2107 s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits);\r
2108 s->context_modes =\r
2109 (uint8_t*)BROTLI_ALLOC(s, (size_t)s->num_block_types[0]);\r
2110 if (s->context_modes == 0) {\r
2111 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_CONTEXT_MODES);\r
2112 break;\r
2113 }\r
2114 s->loop_counter = 0;\r
2115 s->state = BROTLI_STATE_CONTEXT_MODES;\r
2116 /* No break, continue to next state */\r
2117 }\r
2118 case BROTLI_STATE_CONTEXT_MODES:\r
2119 result = ReadContextModes(s);\r
2120 if (result != BROTLI_DECODER_SUCCESS) {\r
2121 break;\r
2122 }\r
2123 s->state = BROTLI_STATE_CONTEXT_MAP_1;\r
2124 /* No break, continue to next state */\r
2125 case BROTLI_STATE_CONTEXT_MAP_1:\r
2126 result = DecodeContextMap(\r
2127 s->num_block_types[0] << BROTLI_LITERAL_CONTEXT_BITS,\r
2128 &s->num_literal_htrees, &s->context_map, s);\r
2129 if (result != BROTLI_DECODER_SUCCESS) {\r
2130 break;\r
2131 }\r
2132 DetectTrivialLiteralBlockTypes(s);\r
2133 s->state = BROTLI_STATE_CONTEXT_MAP_2;\r
2134 /* No break, continue to next state */\r
2135 case BROTLI_STATE_CONTEXT_MAP_2:\r
2136 {\r
2137 uint32_t num_distance_codes =\r
2138 s->num_direct_distance_codes + (48U << s->distance_postfix_bits);\r
2139 result = DecodeContextMap(\r
2140 s->num_block_types[2] << BROTLI_DISTANCE_CONTEXT_BITS,\r
2141 &s->num_dist_htrees, &s->dist_context_map, s);\r
2142 if (result != BROTLI_DECODER_SUCCESS) {\r
2143 break;\r
2144 }\r
2145 BrotliDecoderHuffmanTreeGroupInit(\r
2146 s, &s->literal_hgroup, BROTLI_NUM_LITERAL_SYMBOLS,\r
2147 s->num_literal_htrees);\r
2148 BrotliDecoderHuffmanTreeGroupInit(\r
2149 s, &s->insert_copy_hgroup, BROTLI_NUM_COMMAND_SYMBOLS,\r
2150 s->num_block_types[1]);\r
2151 BrotliDecoderHuffmanTreeGroupInit(\r
2152 s, &s->distance_hgroup, num_distance_codes,\r
2153 s->num_dist_htrees);\r
2154 if (s->literal_hgroup.codes == 0 ||\r
2155 s->insert_copy_hgroup.codes == 0 ||\r
2156 s->distance_hgroup.codes == 0) {\r
2157 return SaveErrorCode(s,\r
2158 BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_TREE_GROUPS));\r
2159 }\r
2160 }\r
2161 s->loop_counter = 0;\r
2162 s->state = BROTLI_STATE_TREE_GROUP;\r
2163 /* No break, continue to next state */\r
2164 case BROTLI_STATE_TREE_GROUP:\r
2165 {\r
2166 HuffmanTreeGroup* hgroup = NULL;\r
2167 switch (s->loop_counter) {\r
2168 case 0:\r
2169 hgroup = &s->literal_hgroup;\r
2170 break;\r
2171 case 1:\r
2172 hgroup = &s->insert_copy_hgroup;\r
2173 break;\r
2174 case 2:\r
2175 hgroup = &s->distance_hgroup;\r
2176 break;\r
2177 default:\r
2178 return SaveErrorCode(s, BROTLI_FAILURE(\r
2179 BROTLI_DECODER_ERROR_UNREACHABLE));\r
2180 }\r
2181 result = HuffmanTreeGroupDecode(hgroup, s);\r
2182 }\r
2183 if (result != BROTLI_DECODER_SUCCESS) break;\r
2184 s->loop_counter++;\r
2185 if (s->loop_counter >= 3) {\r
2186 PrepareLiteralDecoding(s);\r
2187 s->dist_context_map_slice = s->dist_context_map;\r
2188 s->htree_command = s->insert_copy_hgroup.htrees[0];\r
2189 if (!s->ringbuffer && !BrotliAllocateRingBuffer(s)) {\r
2190 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_ALLOC_RING_BUFFER_2);\r
2191 break;\r
2192 }\r
2193 s->state = BROTLI_STATE_COMMAND_BEGIN;\r
2194 }\r
2195 break;\r
2196 case BROTLI_STATE_COMMAND_BEGIN:\r
2197 case BROTLI_STATE_COMMAND_INNER:\r
2198 case BROTLI_STATE_COMMAND_POST_DECODE_LITERALS:\r
2199 case BROTLI_STATE_COMMAND_POST_WRAP_COPY:\r
2200 result = ProcessCommands(s);\r
2201 if (result == BROTLI_DECODER_NEEDS_MORE_INPUT) {\r
2202 result = SafeProcessCommands(s);\r
2203 }\r
2204 break;\r
2205 case BROTLI_STATE_COMMAND_INNER_WRITE:\r
2206 case BROTLI_STATE_COMMAND_POST_WRITE_1:\r
2207 case BROTLI_STATE_COMMAND_POST_WRITE_2:\r
2208 result = WriteRingBuffer(s, available_out, next_out, total_out);\r
2209 if (result != BROTLI_DECODER_SUCCESS) {\r
2210 break;\r
2211 }\r
2212 s->max_distance = s->max_backward_distance;\r
2213 if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {\r
36a0d5ca
SB		 2214 if (s->ringbuffer != 0) {\r
2215 memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)s->pos);\r
2216 }\r
36ff6d80
SB		 2217 if (s->meta_block_remaining_len == 0) {\r
2218 /* Next metablock, if any */\r
2219 s->state = BROTLI_STATE_METABLOCK_DONE;\r
2220 } else {\r
2221 s->state = BROTLI_STATE_COMMAND_BEGIN;\r
2222 }\r
2223 break;\r
2224 } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) {\r
2225 s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;\r
2226 } else { /* BROTLI_STATE_COMMAND_INNER_WRITE */\r
2227 if (s->loop_counter == 0) {\r
2228 if (s->meta_block_remaining_len == 0) {\r
2229 s->state = BROTLI_STATE_METABLOCK_DONE;\r
2230 } else {\r
2231 s->state = BROTLI_STATE_COMMAND_POST_DECODE_LITERALS;\r
2232 }\r
2233 break;\r
2234 }\r
2235 s->state = BROTLI_STATE_COMMAND_INNER;\r
2236 }\r
2237 break;\r
2238 case BROTLI_STATE_METABLOCK_DONE:\r
2239 if (s->meta_block_remaining_len < 0) {\r
2240 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_BLOCK_LENGTH_2);\r
2241 break;\r
2242 }\r
2243 BrotliDecoderStateCleanupAfterMetablock(s);\r
2244 if (!s->is_last_metablock) {\r
2245 s->state = BROTLI_STATE_METABLOCK_BEGIN;\r
2246 break;\r
2247 }\r
2248 if (!BrotliJumpToByteBoundary(br)) {\r
2249 result = BROTLI_FAILURE(BROTLI_DECODER_ERROR_FORMAT_PADDING_2);\r
2250 break;\r
2251 }\r
2252 if (s->buffer_length == 0) {\r
2253 BrotliBitReaderUnload(br);\r
2254 *available_in = br->avail_in;\r
2255 *next_in = br->next_in;\r
2256 }\r
2257 s->state = BROTLI_STATE_DONE;\r
2258 /* No break, continue to next state */\r
2259 case BROTLI_STATE_DONE:\r
2260 if (s->ringbuffer != 0) {\r
2261 result = WriteRingBuffer(s, available_out, next_out, total_out);\r
2262 if (result != BROTLI_DECODER_SUCCESS) {\r
2263 break;\r
2264 }\r
2265 }\r
2266 return SaveErrorCode(s, result);\r
2267 }\r
2268 }\r
2269 return SaveErrorCode(s, result);\r
2270}\r
2271\r
2272void BrotliDecoderSetCustomDictionary(\r
2273 BrotliDecoderState* s, size_t size, const uint8_t* dict) {\r
2274 if (size > (1u << 24)) {\r
2275 return;\r
2276 }\r
2277 s->custom_dict = dict;\r
2278 s->custom_dict_size = (int)size;\r
2279}\r
2280\r
2281BROTLI_BOOL BrotliDecoderHasMoreOutput(const BrotliDecoderState* s) {\r
2282 return TO_BROTLI_BOOL(\r
2283 s->ringbuffer != 0 && UnwrittenBytes(s, BROTLI_FALSE) != 0);\r
2284}\r
2285\r
2286BROTLI_BOOL BrotliDecoderIsUsed(const BrotliDecoderState* s) {\r
2287 return TO_BROTLI_BOOL(s->state != BROTLI_STATE_UNINITED ||\r
2288 BrotliGetAvailableBits(&s->br) != 0);\r
2289}\r
2290\r
2291BROTLI_BOOL BrotliDecoderIsFinished(const BrotliDecoderState* s) {\r
2292 return TO_BROTLI_BOOL(s->state == BROTLI_STATE_DONE);\r
2293}\r
2294\r
2295BrotliDecoderErrorCode BrotliDecoderGetErrorCode(const BrotliDecoderState* s) {\r
2296 return (BrotliDecoderErrorCode)s->error_code;\r
2297}\r
2298\r
2299const char* BrotliDecoderErrorString(BrotliDecoderErrorCode c) {\r
2300 switch (c) {\r
2301#define _BROTLI_ERROR_CODE_CASE(PREFIX, NAME, CODE) \\r
2302 case BROTLI_DECODER ## PREFIX ## NAME: return #NAME;\r
2303#define _BROTLI_NOTHING\r
2304 BROTLI_DECODER_ERROR_CODES_LIST(_BROTLI_ERROR_CODE_CASE, _BROTLI_NOTHING)\r
2305#undef _BROTLI_ERROR_CODE_CASE\r
2306#undef _BROTLI_NOTHING\r
2307 default: return "INVALID";\r
2308 }\r
2309}\r
2310\r
2311/* DEPRECATED >>> */\r
2312BrotliState* BrotliCreateState(\r
2313 brotli_alloc_func alloc, brotli_free_func free, void* opaque) {\r
2314 return (BrotliState*)BrotliDecoderCreateInstance(alloc, free, opaque);\r
2315}\r
2316void BrotliDestroyState(BrotliState* state) {\r
2317 BrotliDecoderDestroyInstance((BrotliDecoderState*)state);\r
2318}\r
2319BrotliResult BrotliDecompressBuffer(\r
2320 size_t encoded_size, const uint8_t* encoded_buffer, size_t* decoded_size,\r
2321 uint8_t* decoded_buffer) {\r
2322 return (BrotliResult)BrotliDecoderDecompress(\r
2323 encoded_size, encoded_buffer, decoded_size, decoded_buffer);\r
2324}\r
2325BrotliResult BrotliDecompressStream(\r
2326 size_t* available_in, const uint8_t** next_in, size_t* available_out,\r
2327 uint8_t** next_out, size_t* total_out, BrotliState* s) {\r
2328 return (BrotliResult)BrotliDecoderDecompressStream((BrotliDecoderState*)s,\r
2329 available_in, next_in, available_out, next_out, total_out);\r
2330}\r
2331void BrotliSetCustomDictionary(\r
2332 size_t size, const uint8_t* dict, BrotliState* s) {\r
2333 BrotliDecoderSetCustomDictionary((BrotliDecoderState*)s, size, dict);\r
2334}\r
2335BROTLI_BOOL BrotliStateIsStreamStart(const BrotliState* s) {\r
2336 return !BrotliDecoderIsUsed((const BrotliDecoderState*)s);\r
2337}\r
2338BROTLI_BOOL BrotliStateIsStreamEnd(const BrotliState* s) {\r
2339 return BrotliDecoderIsFinished((const BrotliDecoderState*)s);\r
2340}\r
2341BrotliErrorCode BrotliGetErrorCode(const BrotliState* s) {\r
2342 return (BrotliErrorCode)BrotliDecoderGetErrorCode(\r
2343 (const BrotliDecoderState*)s);\r
2344}\r
2345const char* BrotliErrorString(BrotliErrorCode c) {\r
2346 return BrotliDecoderErrorString((BrotliDecoderErrorCode)c);\r
2347}\r
2348/* <<< DEPRECATED */\r
2349\r
2350#if defined(__cplusplus) || defined(c_plusplus)\r
2351} /* extern "C" */\r
2352#endif\r
EFI Development Kit II mirror for PVE