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