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