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