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