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