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