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