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