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