1/* Copyright 2013 Google Inc. All Rights Reserved. 2 3 Licensed under the Apache License, Version 2.0 (the "License"); 4 you may not use this file except in compliance with the License. 5 You may obtain a copy of the License at 6 7 http://www.apache.org/licenses/LICENSE-2.0 8 9 Unless required by applicable law or agreed to in writing, software 10 distributed under the License is distributed on an "AS IS" BASIS, 11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 See the License for the specific language governing permissions and 13 limitations under the License. 14*/ 15 16#include <stdlib.h> 17#include <stdio.h> 18#include <string.h> 19#include "./bit_reader.h" 20#include "./context.h" 21#include "./decode.h" 22#include "./dictionary.h" 23#include "./transform.h" 24#include "./huffman.h" 25#include "./prefix.h" 26#include "./safe_malloc.h" 27 28#if defined(__cplusplus) || defined(c_plusplus) 29extern "C" { 30#endif 31 32#ifdef BROTLI_DECODE_DEBUG 33#define BROTLI_LOG_UINT(name) \ 34 printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name)) 35#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) \ 36 printf("[%s] %s[%lu] = %lu\n", __func__, #array_name, \ 37 (unsigned long)(idx), (unsigned long)array_name[idx]) 38#else 39#define BROTLI_LOG_UINT(name) 40#define BROTLI_LOG_ARRAY_INDEX(array_name, idx) 41#endif 42 43static const uint8_t kDefaultCodeLength = 8; 44static const uint8_t kCodeLengthRepeatCode = 16; 45static const int kNumLiteralCodes = 256; 46static const int kNumInsertAndCopyCodes = 704; 47static const int kNumBlockLengthCodes = 26; 48static const int kLiteralContextBits = 6; 49static const int kDistanceContextBits = 2; 50 51#define HUFFMAN_TABLE_BITS 8 52#define HUFFMAN_TABLE_MASK 0xff 53/* This is a rough estimate, not an exact bound. */ 54#define HUFFMAN_MAX_TABLE_SIZE 2048 55 56#define CODE_LENGTH_CODES 18 57static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = { 58 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15, 59}; 60 61#define NUM_DISTANCE_SHORT_CODES 16 62static const int kDistanceShortCodeIndexOffset[NUM_DISTANCE_SHORT_CODES] = { 63 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 64}; 65 66static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = { 67 0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3 68}; 69 70static BROTLI_INLINE int DecodeWindowBits(BrotliBitReader* br) { 71 if (BrotliReadBits(br, 1)) { 72 return 17 + (int)BrotliReadBits(br, 3); 73 } else { 74 return 16; 75 } 76} 77 78/* Decodes a number in the range [0..255], by reading 1 - 11 bits. */ 79static BROTLI_INLINE int DecodeVarLenUint8(BrotliBitReader* br) { 80 if (BrotliReadBits(br, 1)) { 81 int nbits = (int)BrotliReadBits(br, 3); 82 if (nbits == 0) { 83 return 1; 84 } else { 85 return (int)BrotliReadBits(br, nbits) + (1 << nbits); 86 } 87 } 88 return 0; 89} 90 91static void DecodeMetaBlockLength(BrotliBitReader* br, 92 int* meta_block_length, 93 int* input_end, 94 int* is_uncompressed) { 95 int size_nibbles; 96 int i; 97 *input_end = (int)BrotliReadBits(br, 1); 98 *meta_block_length = 0; 99 *is_uncompressed = 0; 100 if (*input_end && BrotliReadBits(br, 1)) { 101 return; 102 } 103 size_nibbles = (int)BrotliReadBits(br, 2) + 4; 104 for (i = 0; i < size_nibbles; ++i) { 105 *meta_block_length |= (int)BrotliReadBits(br, 4) << (i * 4); 106 } 107 ++(*meta_block_length); 108 if (!*input_end) { 109 *is_uncompressed = (int)BrotliReadBits(br, 1); 110 } 111} 112 113/* Decodes the next Huffman code from bit-stream. */ 114static BROTLI_INLINE int ReadSymbol(const HuffmanCode* table, 115 BrotliBitReader* br) { 116 int nbits; 117 BrotliFillBitWindow(br); 118 table += (int)(br->val_ >> br->bit_pos_) & HUFFMAN_TABLE_MASK; 119 nbits = table->bits - HUFFMAN_TABLE_BITS; 120 if (nbits > 0) { 121 br->bit_pos_ += HUFFMAN_TABLE_BITS; 122 table += table->value; 123 table += (int)(br->val_ >> br->bit_pos_) & ((1 << nbits) - 1); 124 } 125 br->bit_pos_ += table->bits; 126 return table->value; 127} 128 129static void PrintUcharVector(const uint8_t* v, int len) { 130 while (len-- > 0) printf(" %d", *v++); 131 printf("\n"); 132} 133 134static int ReadHuffmanCodeLengths( 135 const uint8_t* code_length_code_lengths, 136 int num_symbols, uint8_t* code_lengths, 137 BrotliBitReader* br) { 138 int symbol = 0; 139 uint8_t prev_code_len = kDefaultCodeLength; 140 int repeat = 0; 141 uint8_t repeat_code_len = 0; 142 int space = 32768; 143 HuffmanCode table[32]; 144 145 if (!BrotliBuildHuffmanTable(table, 5, 146 code_length_code_lengths, 147 CODE_LENGTH_CODES)) { 148 printf("[ReadHuffmanCodeLengths] Building code length tree failed: "); 149 PrintUcharVector(code_length_code_lengths, CODE_LENGTH_CODES); 150 return 0; 151 } 152 153 while (symbol < num_symbols && space > 0) { 154 const HuffmanCode* p = table; 155 uint8_t code_len; 156 if (!BrotliReadMoreInput(br)) { 157 printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n"); 158 return 0; 159 } 160 BrotliFillBitWindow(br); 161 p += (br->val_ >> br->bit_pos_) & 31; 162 br->bit_pos_ += p->bits; 163 code_len = (uint8_t)p->value; 164 if (code_len < kCodeLengthRepeatCode) { 165 repeat = 0; 166 code_lengths[symbol++] = code_len; 167 if (code_len != 0) { 168 prev_code_len = code_len; 169 space -= 32768 >> code_len; 170 } 171 } else { 172 const int extra_bits = code_len - 14; 173 int old_repeat; 174 int repeat_delta; 175 uint8_t new_len = 0; 176 if (code_len == kCodeLengthRepeatCode) { 177 new_len = prev_code_len; 178 } 179 if (repeat_code_len != new_len) { 180 repeat = 0; 181 repeat_code_len = new_len; 182 } 183 old_repeat = repeat; 184 if (repeat > 0) { 185 repeat -= 2; 186 repeat <<= extra_bits; 187 } 188 repeat += (int)BrotliReadBits(br, extra_bits) + 3; 189 repeat_delta = repeat - old_repeat; 190 if (symbol + repeat_delta > num_symbols) { 191 return 0; 192 } 193 memset(&code_lengths[symbol], repeat_code_len, (size_t)repeat_delta); 194 symbol += repeat_delta; 195 if (repeat_code_len != 0) { 196 space -= repeat_delta << (15 - repeat_code_len); 197 } 198 } 199 } 200 if (space != 0) { 201 printf("[ReadHuffmanCodeLengths] space = %d\n", space); 202 return 0; 203 } 204 memset(&code_lengths[symbol], 0, (size_t)(num_symbols - symbol)); 205 return 1; 206} 207 208static int ReadHuffmanCode(int alphabet_size, 209 HuffmanCode* table, 210 BrotliBitReader* br) { 211 int ok = 1; 212 int table_size = 0; 213 int simple_code_or_skip; 214 uint8_t* code_lengths = NULL; 215 216 code_lengths = 217 (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size, 218 sizeof(*code_lengths)); 219 if (code_lengths == NULL) { 220 return 0; 221 } 222 if (!BrotliReadMoreInput(br)) { 223 printf("[ReadHuffmanCode] Unexpected end of input.\n"); 224 return 0; 225 } 226 /* simple_code_or_skip is used as follows: 227 1 for simple code; 228 0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */ 229 simple_code_or_skip = (int)BrotliReadBits(br, 2); 230 BROTLI_LOG_UINT(simple_code_or_skip); 231 if (simple_code_or_skip == 1) { 232 /* Read symbols, codes & code lengths directly. */ 233 int i; 234 int max_bits_counter = alphabet_size - 1; 235 int max_bits = 0; 236 int symbols[4] = { 0 }; 237 const int num_symbols = (int)BrotliReadBits(br, 2) + 1; 238 while (max_bits_counter) { 239 max_bits_counter >>= 1; 240 ++max_bits; 241 } 242 memset(code_lengths, 0, (size_t)alphabet_size); 243 for (i = 0; i < num_symbols; ++i) { 244 symbols[i] = (int)BrotliReadBits(br, max_bits) % alphabet_size; 245 code_lengths[symbols[i]] = 2; 246 } 247 code_lengths[symbols[0]] = 1; 248 switch (num_symbols) { 249 case 1: 250 break; 251 case 3: 252 ok = ((symbols[0] != symbols[1]) && 253 (symbols[0] != symbols[2]) && 254 (symbols[1] != symbols[2])); 255 break; 256 case 2: 257 ok = (symbols[0] != symbols[1]); 258 code_lengths[symbols[1]] = 1; 259 break; 260 case 4: 261 ok = ((symbols[0] != symbols[1]) && 262 (symbols[0] != symbols[2]) && 263 (symbols[0] != symbols[3]) && 264 (symbols[1] != symbols[2]) && 265 (symbols[1] != symbols[3]) && 266 (symbols[2] != symbols[3])); 267 if (BrotliReadBits(br, 1)) { 268 code_lengths[symbols[2]] = 3; 269 code_lengths[symbols[3]] = 3; 270 } else { 271 code_lengths[symbols[0]] = 2; 272 } 273 break; 274 } 275 BROTLI_LOG_UINT(num_symbols); 276 } else { /* Decode Huffman-coded code lengths. */ 277 int i; 278 uint8_t code_length_code_lengths[CODE_LENGTH_CODES] = { 0 }; 279 int space = 32; 280 int num_codes = 0; 281 /* Static Huffman code for the code length code lengths */ 282 static const HuffmanCode huff[16] = { 283 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1}, 284 {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5}, 285 }; 286 for (i = simple_code_or_skip; i < CODE_LENGTH_CODES && space > 0; ++i) { 287 const int code_len_idx = kCodeLengthCodeOrder[i]; 288 const HuffmanCode* p = huff; 289 uint8_t v; 290 BrotliFillBitWindow(br); 291 p += (br->val_ >> br->bit_pos_) & 15; 292 br->bit_pos_ += p->bits; 293 v = (uint8_t)p->value; 294 code_length_code_lengths[code_len_idx] = v; 295 BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx); 296 if (v != 0) { 297 space -= (32 >> v); 298 ++num_codes; 299 } 300 } 301 ok = (num_codes == 1 || space == 0) && 302 ReadHuffmanCodeLengths(code_length_code_lengths, 303 alphabet_size, code_lengths, br); 304 } 305 if (ok) { 306 table_size = BrotliBuildHuffmanTable(table, HUFFMAN_TABLE_BITS, 307 code_lengths, alphabet_size); 308 if (table_size == 0) { 309 printf("[ReadHuffmanCode] BuildHuffmanTable failed: "); 310 PrintUcharVector(code_lengths, alphabet_size); 311 } 312 } 313 free(code_lengths); 314 return table_size; 315} 316 317static BROTLI_INLINE int ReadBlockLength(const HuffmanCode* table, 318 BrotliBitReader* br) { 319 int code; 320 int nbits; 321 code = ReadSymbol(table, br); 322 nbits = kBlockLengthPrefixCode[code].nbits; 323 return kBlockLengthPrefixCode[code].offset + (int)BrotliReadBits(br, nbits); 324} 325 326static int TranslateShortCodes(int code, int* ringbuffer, int index) { 327 int val; 328 if (code < NUM_DISTANCE_SHORT_CODES) { 329 index += kDistanceShortCodeIndexOffset[code]; 330 index &= 3; 331 val = ringbuffer[index] + kDistanceShortCodeValueOffset[code]; 332 } else { 333 val = code - NUM_DISTANCE_SHORT_CODES + 1; 334 } 335 return val; 336} 337 338static void MoveToFront(uint8_t* v, uint8_t index) { 339 uint8_t value = v[index]; 340 uint8_t i = index; 341 for (; i; --i) v[i] = v[i - 1]; 342 v[0] = value; 343} 344 345static void InverseMoveToFrontTransform(uint8_t* v, int v_len) { 346 uint8_t mtf[256]; 347 int i; 348 for (i = 0; i < 256; ++i) { 349 mtf[i] = (uint8_t)i; 350 } 351 for (i = 0; i < v_len; ++i) { 352 uint8_t index = v[i]; 353 v[i] = mtf[index]; 354 if (index) MoveToFront(mtf, index); 355 } 356} 357 358/* Contains a collection of huffman trees with the same alphabet size. */ 359typedef struct { 360 int alphabet_size; 361 int num_htrees; 362 HuffmanCode* codes; 363 HuffmanCode** htrees; 364} HuffmanTreeGroup; 365 366static void HuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size, 367 int ntrees) { 368 group->alphabet_size = alphabet_size; 369 group->num_htrees = ntrees; 370 group->codes = (HuffmanCode*)malloc( 371 sizeof(HuffmanCode) * (size_t)(ntrees * HUFFMAN_MAX_TABLE_SIZE)); 372 group->htrees = (HuffmanCode**)malloc(sizeof(HuffmanCode*) * (size_t)ntrees); 373} 374 375static void HuffmanTreeGroupRelease(HuffmanTreeGroup* group) { 376 if (group->codes) { 377 free(group->codes); 378 } 379 if (group->htrees) { 380 free(group->htrees); 381 } 382} 383 384static int HuffmanTreeGroupDecode(HuffmanTreeGroup* group, 385 BrotliBitReader* br) { 386 int i; 387 int table_size; 388 HuffmanCode* next = group->codes; 389 for (i = 0; i < group->num_htrees; ++i) { 390 group->htrees[i] = next; 391 table_size = ReadHuffmanCode(group->alphabet_size, next, br); 392 next += table_size; 393 if (table_size == 0) { 394 return 0; 395 } 396 } 397 return 1; 398} 399 400static int DecodeContextMap(int context_map_size, 401 int* num_htrees, 402 uint8_t** context_map, 403 BrotliBitReader* br) { 404 int ok = 1; 405 int use_rle_for_zeros; 406 int max_run_length_prefix = 0; 407 HuffmanCode* table; 408 int i; 409 if (!BrotliReadMoreInput(br)) { 410 printf("[DecodeContextMap] Unexpected end of input.\n"); 411 return 0; 412 } 413 *num_htrees = DecodeVarLenUint8(br) + 1; 414 415 BROTLI_LOG_UINT(context_map_size); 416 BROTLI_LOG_UINT(*num_htrees); 417 418 *context_map = (uint8_t*)malloc((size_t)context_map_size); 419 if (*context_map == 0) { 420 return 0; 421 } 422 if (*num_htrees <= 1) { 423 memset(*context_map, 0, (size_t)context_map_size); 424 return 1; 425 } 426 427 use_rle_for_zeros = (int)BrotliReadBits(br, 1); 428 if (use_rle_for_zeros) { 429 max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1; 430 } 431 table = (HuffmanCode*)malloc(HUFFMAN_MAX_TABLE_SIZE * sizeof(*table)); 432 if (table == NULL) { 433 return 0; 434 } 435 if (!ReadHuffmanCode(*num_htrees + max_run_length_prefix, table, br)) { 436 ok = 0; 437 goto End; 438 } 439 for (i = 0; i < context_map_size;) { 440 int code; 441 if (!BrotliReadMoreInput(br)) { 442 printf("[DecodeContextMap] Unexpected end of input.\n"); 443 ok = 0; 444 goto End; 445 } 446 code = ReadSymbol(table, br); 447 if (code == 0) { 448 (*context_map)[i] = 0; 449 ++i; 450 } else if (code <= max_run_length_prefix) { 451 int reps = 1 + (1 << code) + (int)BrotliReadBits(br, code); 452 while (--reps) { 453 if (i >= context_map_size) { 454 ok = 0; 455 goto End; 456 } 457 (*context_map)[i] = 0; 458 ++i; 459 } 460 } else { 461 (*context_map)[i] = (uint8_t)(code - max_run_length_prefix); 462 ++i; 463 } 464 } 465 if (BrotliReadBits(br, 1)) { 466 InverseMoveToFrontTransform(*context_map, context_map_size); 467 } 468End: 469 free(table); 470 return ok; 471} 472 473static BROTLI_INLINE void DecodeBlockType(const int max_block_type, 474 const HuffmanCode* trees, 475 int tree_type, 476 int* block_types, 477 int* ringbuffers, 478 int* indexes, 479 BrotliBitReader* br) { 480 int* ringbuffer = ringbuffers + tree_type * 2; 481 int* index = indexes + tree_type; 482 int type_code = ReadSymbol(&trees[tree_type * HUFFMAN_MAX_TABLE_SIZE], br); 483 int block_type; 484 if (type_code == 0) { 485 block_type = ringbuffer[*index & 1]; 486 } else if (type_code == 1) { 487 block_type = ringbuffer[(*index - 1) & 1] + 1; 488 } else { 489 block_type = type_code - 2; 490 } 491 if (block_type >= max_block_type) { 492 block_type -= max_block_type; 493 } 494 block_types[tree_type] = block_type; 495 ringbuffer[(*index) & 1] = block_type; 496 ++(*index); 497} 498 499/* Copy len bytes from src to dst. It can write up to ten extra bytes 500 after the end of the copy. 501 502 The main part of this loop is a simple copy of eight bytes at a time until 503 we've copied (at least) the requested amount of bytes. However, if dst and 504 src are less than eight bytes apart (indicating a repeating pattern of 505 length < 8), we first need to expand the pattern in order to get the correct 506 results. For instance, if the buffer looks like this, with the eight-byte 507 <src> and <dst> patterns marked as intervals: 508 509 abxxxxxxxxxxxx 510 [------] src 511 [------] dst 512 513 a single eight-byte copy from <src> to <dst> will repeat the pattern once, 514 after which we can move <dst> two bytes without moving <src>: 515 516 ababxxxxxxxxxx 517 [------] src 518 [------] dst 519 520 and repeat the exercise until the two no longer overlap. 521 522 This allows us to do very well in the special case of one single byte 523 repeated many times, without taking a big hit for more general cases. 524 525 The worst case of extra writing past the end of the match occurs when 526 dst - src == 1 and len == 1; the last copy will read from byte positions 527 [0..7] and write to [4..11], whereas it was only supposed to write to 528 position 1. Thus, ten excess bytes. 529*/ 530static BROTLI_INLINE void IncrementalCopyFastPath( 531 uint8_t* dst, const uint8_t* src, int len) { 532 if (src < dst) { 533 while (dst - src < 8) { 534 UNALIGNED_COPY64(dst, src); 535 len -= (int)(dst - src); 536 dst += dst - src; 537 } 538 } 539 while (len > 0) { 540 UNALIGNED_COPY64(dst, src); 541 src += 8; 542 dst += 8; 543 len -= 8; 544 } 545} 546 547int CopyUncompressedBlockToOutput(BrotliOutput output, int len, int pos, 548 uint8_t* ringbuffer, int ringbuffer_mask, 549 BrotliBitReader* br) { 550 const int rb_size = ringbuffer_mask + 1; 551 uint8_t* ringbuffer_end = ringbuffer + rb_size; 552 int rb_pos = pos & ringbuffer_mask; 553 int br_pos = br->pos_ & BROTLI_IBUF_MASK; 554 int nbytes; 555 556 /* For short lengths copy byte-by-byte */ 557 if (len < 8 || br->bit_pos_ + (uint32_t)(len << 3) < br->bit_end_pos_) { 558 while (len-- > 0) { 559 if (!BrotliReadMoreInput(br)) { 560 return 0; 561 } 562 ringbuffer[rb_pos++]= (uint8_t)BrotliReadBits(br, 8); 563 if (rb_pos == rb_size) { 564 if (BrotliWrite(output, ringbuffer, (size_t)rb_size) < rb_size) { 565 return 0; 566 } 567 rb_pos = 0; 568 } 569 } 570 return 1; 571 } 572 573 if (br->bit_end_pos_ < 64) { 574 return 0; 575 } 576 577 /* Copy remaining 0-8 bytes from br->val_ to ringbuffer. */ 578 while (br->bit_pos_ < 64) { 579 ringbuffer[rb_pos] = (uint8_t)(br->val_ >> br->bit_pos_); 580 br->bit_pos_ += 8; 581 ++rb_pos; 582 --len; 583 } 584 585 /* Copy remaining bytes from br->buf_ to ringbuffer. */ 586 nbytes = (int)(br->bit_end_pos_ - br->bit_pos_) >> 3; 587 if (br_pos + nbytes > BROTLI_IBUF_MASK) { 588 int tail = BROTLI_IBUF_MASK + 1 - br_pos; 589 memcpy(&ringbuffer[rb_pos], &br->buf_[br_pos], (size_t)tail); 590 nbytes -= tail; 591 rb_pos += tail; 592 len -= tail; 593 br_pos = 0; 594 } 595 memcpy(&ringbuffer[rb_pos], &br->buf_[br_pos], (size_t)nbytes); 596 rb_pos += nbytes; 597 len -= nbytes; 598 599 /* If we wrote past the logical end of the ringbuffer, copy the tail of the 600 ringbuffer to its beginning and flush the ringbuffer to the output. */ 601 if (rb_pos >= rb_size) { 602 if (BrotliWrite(output, ringbuffer, (size_t)rb_size) < rb_size) { 603 return 0; 604 } 605 rb_pos -= rb_size; 606 memcpy(ringbuffer, ringbuffer_end, (size_t)rb_pos); 607 } 608 609 /* If we have more to copy than the remaining size of the ringbuffer, then we 610 first fill the ringbuffer from the input and then flush the ringbuffer to 611 the output */ 612 while (rb_pos + len >= rb_size) { 613 nbytes = rb_size - rb_pos; 614 if (BrotliRead(br->input_, &ringbuffer[rb_pos], (size_t)nbytes) < nbytes || 615 BrotliWrite(output, ringbuffer, (size_t)rb_size) < nbytes) { 616 return 0; 617 } 618 len -= nbytes; 619 rb_pos = 0; 620 } 621 622 /* Copy straight from the input onto the ringbuffer. The ringbuffer will be 623 flushed to the output at a later time. */ 624 if (BrotliRead(br->input_, &ringbuffer[rb_pos], (size_t)len) < len) { 625 return 0; 626 } 627 628 /* Restore the state of the bit reader. */ 629 BrotliInitBitReader(br, br->input_); 630 return 1; 631} 632 633int BrotliDecompressedSize(size_t encoded_size, 634 const uint8_t* encoded_buffer, 635 size_t* decoded_size) { 636 BrotliMemInput memin; 637 BrotliInput input = BrotliInitMemInput(encoded_buffer, encoded_size, &memin); 638 BrotliBitReader br; 639 int meta_block_len; 640 int input_end; 641 int is_uncompressed; 642 if (!BrotliInitBitReader(&br, input)) { 643 return 0; 644 } 645 DecodeWindowBits(&br); 646 DecodeMetaBlockLength(&br, &meta_block_len, &input_end, &is_uncompressed); 647 if (!input_end) { 648 return 0; 649 } 650 *decoded_size = (size_t)meta_block_len; 651 return 1; 652} 653 654int BrotliDecompressBuffer(size_t encoded_size, 655 const uint8_t* encoded_buffer, 656 size_t* decoded_size, 657 uint8_t* decoded_buffer) { 658 BrotliMemInput memin; 659 BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin); 660 BrotliMemOutput mout; 661 BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout); 662 int success = BrotliDecompress(in, out); 663 *decoded_size = mout.pos; 664 return success; 665} 666 667int BrotliDecompress(BrotliInput input, BrotliOutput output) { 668 int ok = 1; 669 int i; 670 int pos = 0; 671 int input_end = 0; 672 int window_bits = 0; 673 int max_backward_distance; 674 int max_distance = 0; 675 int ringbuffer_size; 676 int ringbuffer_mask; 677 uint8_t* ringbuffer; 678 uint8_t* ringbuffer_end; 679 /* This ring buffer holds a few past copy distances that will be used by */ 680 /* some special distance codes. */ 681 int dist_rb[4] = { 16, 15, 11, 4 }; 682 int dist_rb_idx = 0; 683 /* The previous 2 bytes used for context. */ 684 uint8_t prev_byte1 = 0; 685 uint8_t prev_byte2 = 0; 686 HuffmanTreeGroup hgroup[3]; 687 HuffmanCode* block_type_trees = NULL; 688 HuffmanCode* block_len_trees = NULL; 689 BrotliBitReader br; 690 691 /* We need the slack region for the following reasons: 692 - always doing two 8-byte copies for fast backward copying 693 - transforms 694 - flushing the input ringbuffer when decoding uncompressed blocks */ 695 static const int kRingBufferWriteAheadSlack = 128 + BROTLI_READ_SIZE; 696 697 if (!BrotliInitBitReader(&br, input)) { 698 return 0; 699 } 700 701 /* Decode window size. */ 702 window_bits = DecodeWindowBits(&br); 703 max_backward_distance = (1 << window_bits) - 16; 704 705 ringbuffer_size = 1 << window_bits; 706 ringbuffer_mask = ringbuffer_size - 1; 707 ringbuffer = (uint8_t*)malloc((size_t)(ringbuffer_size + 708 kRingBufferWriteAheadSlack + 709 kMaxDictionaryWordLength)); 710 if (!ringbuffer) { 711 ok = 0; 712 } 713 ringbuffer_end = ringbuffer + ringbuffer_size; 714 715 if (ok) { 716 block_type_trees = (HuffmanCode*)malloc( 717 3 * HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode)); 718 block_len_trees = (HuffmanCode*)malloc( 719 3 * HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode)); 720 if (block_type_trees == NULL || block_len_trees == NULL) { 721 ok = 0; 722 } 723 } 724 725 while (!input_end && ok) { 726 int meta_block_remaining_len = 0; 727 int is_uncompressed; 728 int block_length[3] = { 1 << 28, 1 << 28, 1 << 28 }; 729 int block_type[3] = { 0 }; 730 int num_block_types[3] = { 1, 1, 1 }; 731 int block_type_rb[6] = { 0, 1, 0, 1, 0, 1 }; 732 int block_type_rb_index[3] = { 0 }; 733 int distance_postfix_bits; 734 int num_direct_distance_codes; 735 int distance_postfix_mask; 736 int num_distance_codes; 737 uint8_t* context_map = NULL; 738 uint8_t* context_modes = NULL; 739 int num_literal_htrees; 740 uint8_t* dist_context_map = NULL; 741 int num_dist_htrees; 742 int context_offset = 0; 743 uint8_t* context_map_slice = NULL; 744 uint8_t literal_htree_index = 0; 745 int dist_context_offset = 0; 746 uint8_t* dist_context_map_slice = NULL; 747 uint8_t dist_htree_index = 0; 748 int context_lookup_offset1 = 0; 749 int context_lookup_offset2 = 0; 750 uint8_t context_mode; 751 HuffmanCode* htree_command; 752 753 for (i = 0; i < 3; ++i) { 754 hgroup[i].codes = NULL; 755 hgroup[i].htrees = NULL; 756 } 757 758 if (!BrotliReadMoreInput(&br)) { 759 printf("[BrotliDecompress] Unexpected end of input.\n"); 760 ok = 0; 761 goto End; 762 } 763 BROTLI_LOG_UINT(pos); 764 DecodeMetaBlockLength(&br, &meta_block_remaining_len, 765 &input_end, &is_uncompressed); 766 BROTLI_LOG_UINT(meta_block_remaining_len); 767 if (meta_block_remaining_len == 0) { 768 goto End; 769 } 770 if (is_uncompressed) { 771 BrotliSetBitPos(&br, (br.bit_pos_ + 7) & (uint32_t)(~7UL)); 772 ok = CopyUncompressedBlockToOutput(output, meta_block_remaining_len, pos, 773 ringbuffer, ringbuffer_mask, &br); 774 pos += meta_block_remaining_len; 775 goto End; 776 } 777 for (i = 0; i < 3; ++i) { 778 num_block_types[i] = DecodeVarLenUint8(&br) + 1; 779 if (num_block_types[i] >= 2) { 780 if (!ReadHuffmanCode(num_block_types[i] + 2, 781 &block_type_trees[i * HUFFMAN_MAX_TABLE_SIZE], 782 &br) || 783 !ReadHuffmanCode(kNumBlockLengthCodes, 784 &block_len_trees[i * HUFFMAN_MAX_TABLE_SIZE], 785 &br)) { 786 ok = 0; 787 goto End; 788 } 789 block_length[i] = ReadBlockLength( 790 &block_len_trees[i * HUFFMAN_MAX_TABLE_SIZE], &br); 791 block_type_rb_index[i] = 1; 792 } 793 } 794 795 BROTLI_LOG_UINT(num_block_types[0]); 796 BROTLI_LOG_UINT(num_block_types[1]); 797 BROTLI_LOG_UINT(num_block_types[2]); 798 BROTLI_LOG_UINT(block_length[0]); 799 BROTLI_LOG_UINT(block_length[1]); 800 BROTLI_LOG_UINT(block_length[2]); 801 802 if (!BrotliReadMoreInput(&br)) { 803 printf("[BrotliDecompress] Unexpected end of input.\n"); 804 ok = 0; 805 goto End; 806 } 807 distance_postfix_bits = (int)BrotliReadBits(&br, 2); 808 num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES + 809 ((int)BrotliReadBits(&br, 4) << distance_postfix_bits); 810 distance_postfix_mask = (1 << distance_postfix_bits) - 1; 811 num_distance_codes = (num_direct_distance_codes + 812 (48 << distance_postfix_bits)); 813 context_modes = (uint8_t*)malloc((size_t)num_block_types[0]); 814 if (context_modes == 0) { 815 ok = 0; 816 goto End; 817 } 818 for (i = 0; i < num_block_types[0]; ++i) { 819 context_modes[i] = (uint8_t)(BrotliReadBits(&br, 2) << 1); 820 BROTLI_LOG_ARRAY_INDEX(context_modes, i); 821 } 822 BROTLI_LOG_UINT(num_direct_distance_codes); 823 BROTLI_LOG_UINT(distance_postfix_bits); 824 825 if (!DecodeContextMap(num_block_types[0] << kLiteralContextBits, 826 &num_literal_htrees, &context_map, &br) || 827 !DecodeContextMap(num_block_types[2] << kDistanceContextBits, 828 &num_dist_htrees, &dist_context_map, &br)) { 829 ok = 0; 830 goto End; 831 } 832 833 HuffmanTreeGroupInit(&hgroup[0], kNumLiteralCodes, num_literal_htrees); 834 HuffmanTreeGroupInit(&hgroup[1], kNumInsertAndCopyCodes, 835 num_block_types[1]); 836 HuffmanTreeGroupInit(&hgroup[2], num_distance_codes, num_dist_htrees); 837 838 for (i = 0; i < 3; ++i) { 839 if (!HuffmanTreeGroupDecode(&hgroup[i], &br)) { 840 ok = 0; 841 goto End; 842 } 843 } 844 845 context_map_slice = context_map; 846 dist_context_map_slice = dist_context_map; 847 context_mode = context_modes[block_type[0]]; 848 context_lookup_offset1 = kContextLookupOffsets[context_mode]; 849 context_lookup_offset2 = kContextLookupOffsets[context_mode + 1]; 850 htree_command = hgroup[1].htrees[0]; 851 852 while (meta_block_remaining_len > 0) { 853 int cmd_code; 854 int range_idx; 855 int insert_code; 856 int copy_code; 857 int insert_length; 858 int copy_length; 859 int distance_code; 860 int distance; 861 uint8_t context; 862 int j; 863 const uint8_t* copy_src; 864 uint8_t* copy_dst; 865 if (!BrotliReadMoreInput(&br)) { 866 printf("[BrotliDecompress] Unexpected end of input.\n"); 867 ok = 0; 868 goto End; 869 } 870 if (block_length[1] == 0) { 871 DecodeBlockType(num_block_types[1], 872 block_type_trees, 1, block_type, block_type_rb, 873 block_type_rb_index, &br); 874 block_length[1] = ReadBlockLength( 875 &block_len_trees[HUFFMAN_MAX_TABLE_SIZE], &br); 876 htree_command = hgroup[1].htrees[block_type[1]]; 877 } 878 --block_length[1]; 879 cmd_code = ReadSymbol(htree_command, &br); 880 range_idx = cmd_code >> 6; 881 if (range_idx >= 2) { 882 range_idx -= 2; 883 distance_code = -1; 884 } else { 885 distance_code = 0; 886 } 887 insert_code = kInsertRangeLut[range_idx] + ((cmd_code >> 3) & 7); 888 copy_code = kCopyRangeLut[range_idx] + (cmd_code & 7); 889 insert_length = kInsertLengthPrefixCode[insert_code].offset + 890 (int)BrotliReadBits(&br, kInsertLengthPrefixCode[insert_code].nbits); 891 copy_length = kCopyLengthPrefixCode[copy_code].offset + 892 (int)BrotliReadBits(&br, kCopyLengthPrefixCode[copy_code].nbits); 893 BROTLI_LOG_UINT(insert_length); 894 BROTLI_LOG_UINT(copy_length); 895 BROTLI_LOG_UINT(distance_code); 896 for (j = 0; j < insert_length; ++j) { 897 if (!BrotliReadMoreInput(&br)) { 898 printf("[BrotliDecompress] Unexpected end of input.\n"); 899 ok = 0; 900 goto End; 901 } 902 if (block_length[0] == 0) { 903 DecodeBlockType(num_block_types[0], 904 block_type_trees, 0, block_type, block_type_rb, 905 block_type_rb_index, &br); 906 block_length[0] = ReadBlockLength(block_len_trees, &br); 907 context_offset = block_type[0] << kLiteralContextBits; 908 context_map_slice = context_map + context_offset; 909 context_mode = context_modes[block_type[0]]; 910 context_lookup_offset1 = kContextLookupOffsets[context_mode]; 911 context_lookup_offset2 = kContextLookupOffsets[context_mode + 1]; 912 } 913 context = (kContextLookup[context_lookup_offset1 + prev_byte1] | 914 kContextLookup[context_lookup_offset2 + prev_byte2]); 915 BROTLI_LOG_UINT(context); 916 literal_htree_index = context_map_slice[context]; 917 --block_length[0]; 918 prev_byte2 = prev_byte1; 919 prev_byte1 = (uint8_t)ReadSymbol(hgroup[0].htrees[literal_htree_index], 920 &br); 921 ringbuffer[pos & ringbuffer_mask] = prev_byte1; 922 BROTLI_LOG_UINT(literal_htree_index); 923 BROTLI_LOG_ARRAY_INDEX(ringbuffer, pos & ringbuffer_mask); 924 if ((pos & ringbuffer_mask) == ringbuffer_mask) { 925 if (BrotliWrite(output, ringbuffer, (size_t)ringbuffer_size) < 0) { 926 ok = 0; 927 goto End; 928 } 929 } 930 ++pos; 931 } 932 meta_block_remaining_len -= insert_length; 933 if (meta_block_remaining_len <= 0) break; 934 935 if (distance_code < 0) { 936 uint8_t context; 937 if (!BrotliReadMoreInput(&br)) { 938 printf("[BrotliDecompress] Unexpected end of input.\n"); 939 ok = 0; 940 goto End; 941 } 942 if (block_length[2] == 0) { 943 DecodeBlockType(num_block_types[2], 944 block_type_trees, 2, block_type, block_type_rb, 945 block_type_rb_index, &br); 946 block_length[2] = ReadBlockLength( 947 &block_len_trees[2 * HUFFMAN_MAX_TABLE_SIZE], &br); 948 dist_htree_index = (uint8_t)block_type[2]; 949 dist_context_offset = block_type[2] << kDistanceContextBits; 950 dist_context_map_slice = dist_context_map + dist_context_offset; 951 } 952 --block_length[2]; 953 context = (uint8_t)(copy_length > 4 ? 3 : copy_length - 2); 954 dist_htree_index = dist_context_map_slice[context]; 955 distance_code = ReadSymbol(hgroup[2].htrees[dist_htree_index], &br); 956 if (distance_code >= num_direct_distance_codes) { 957 int nbits; 958 int postfix; 959 int offset; 960 distance_code -= num_direct_distance_codes; 961 postfix = distance_code & distance_postfix_mask; 962 distance_code >>= distance_postfix_bits; 963 nbits = (distance_code >> 1) + 1; 964 offset = ((2 + (distance_code & 1)) << nbits) - 4; 965 distance_code = num_direct_distance_codes + 966 ((offset + (int)BrotliReadBits(&br, nbits)) << 967 distance_postfix_bits) + postfix; 968 } 969 } 970 971 /* Convert the distance code to the actual distance by possibly looking */ 972 /* up past distnaces from the ringbuffer. */ 973 distance = TranslateShortCodes(distance_code, dist_rb, dist_rb_idx); 974 if (distance < 0) { 975 ok = 0; 976 goto End; 977 } 978 BROTLI_LOG_UINT(distance); 979 980 if (pos < max_backward_distance && 981 max_distance != max_backward_distance) { 982 max_distance = pos; 983 } else { 984 max_distance = max_backward_distance; 985 } 986 987 copy_dst = &ringbuffer[pos & ringbuffer_mask]; 988 989 if (distance > max_distance) { 990 if (copy_length >= kMinDictionaryWordLength && 991 copy_length <= kMaxDictionaryWordLength) { 992 int offset = kBrotliDictionaryOffsetsByLength[copy_length]; 993 int word_id = distance - max_distance - 1; 994 int shift = kBrotliDictionarySizeBitsByLength[copy_length]; 995 int mask = (1 << shift) - 1; 996 int word_idx = word_id & mask; 997 int transform_idx = word_id >> shift; 998 offset += word_idx * copy_length; 999 if (transform_idx < kNumTransforms) { 1000 const uint8_t* word = &kBrotliDictionary[offset]; 1001 int len = TransformDictionaryWord( 1002 copy_dst, word, copy_length, transform_idx); 1003 copy_dst += len; 1004 pos += len; 1005 meta_block_remaining_len -= len; 1006 if (copy_dst >= ringbuffer_end) { 1007 if (BrotliWrite(output, ringbuffer, 1008 (size_t)ringbuffer_size) < 0) { 1009 ok = 0; 1010 goto End; 1011 } 1012 memcpy(ringbuffer, ringbuffer_end, 1013 (size_t)(copy_dst - ringbuffer_end)); 1014 } 1015 } else { 1016 printf("Invalid backward reference. pos: %d distance: %d " 1017 "len: %d bytes left: %d\n", pos, distance, copy_length, 1018 meta_block_remaining_len); 1019 ok = 0; 1020 goto End; 1021 } 1022 } else { 1023 printf("Invalid backward reference. pos: %d distance: %d " 1024 "len: %d bytes left: %d\n", pos, distance, copy_length, 1025 meta_block_remaining_len); 1026 ok = 0; 1027 goto End; 1028 } 1029 } else { 1030 if (distance_code > 0) { 1031 dist_rb[dist_rb_idx & 3] = distance; 1032 ++dist_rb_idx; 1033 } 1034 1035 if (copy_length > meta_block_remaining_len) { 1036 printf("Invalid backward reference. pos: %d distance: %d " 1037 "len: %d bytes left: %d\n", pos, distance, copy_length, 1038 meta_block_remaining_len); 1039 ok = 0; 1040 goto End; 1041 } 1042 1043 copy_src = &ringbuffer[(pos - distance) & ringbuffer_mask]; 1044 1045#if (defined(__x86_64__) || defined(_M_X64)) 1046 if (copy_src + copy_length <= ringbuffer_end && 1047 copy_dst + copy_length < ringbuffer_end) { 1048 if (copy_length <= 16 && distance >= 8) { 1049 UNALIGNED_COPY64(copy_dst, copy_src); 1050 UNALIGNED_COPY64(copy_dst + 8, copy_src + 8); 1051 } else { 1052 IncrementalCopyFastPath(copy_dst, copy_src, copy_length); 1053 } 1054 pos += copy_length; 1055 meta_block_remaining_len -= copy_length; 1056 copy_length = 0; 1057 } 1058#endif 1059 1060 for (j = 0; j < copy_length; ++j) { 1061 ringbuffer[pos & ringbuffer_mask] = 1062 ringbuffer[(pos - distance) & ringbuffer_mask]; 1063 if ((pos & ringbuffer_mask) == ringbuffer_mask) { 1064 if (BrotliWrite(output, ringbuffer, (size_t)ringbuffer_size) < 0) { 1065 ok = 0; 1066 goto End; 1067 } 1068 } 1069 ++pos; 1070 --meta_block_remaining_len; 1071 } 1072 } 1073 1074 /* When we get here, we must have inserted at least one literal and */ 1075 /* made a copy of at least length two, therefore accessing the last 2 */ 1076 /* bytes is valid. */ 1077 prev_byte1 = ringbuffer[(pos - 1) & ringbuffer_mask]; 1078 prev_byte2 = ringbuffer[(pos - 2) & ringbuffer_mask]; 1079 } 1080 1081 /* Protect pos from overflow, wrap it around at every GB of input data */ 1082 pos &= 0x3fffffff; 1083 1084 End: 1085 if (context_modes != 0) { 1086 free(context_modes); 1087 } 1088 if (context_map != 0) { 1089 free(context_map); 1090 } 1091 if (dist_context_map != 0) { 1092 free(dist_context_map); 1093 } 1094 for (i = 0; i < 3; ++i) { 1095 HuffmanTreeGroupRelease(&hgroup[i]); 1096 } 1097 } 1098 1099 if (ringbuffer != 0) { 1100 if (BrotliWrite(output, ringbuffer, (size_t)(pos & ringbuffer_mask)) < 0) { 1101 ok = 0; 1102 } 1103 free(ringbuffer); 1104 } 1105 if (block_type_trees != 0) { 1106 free(block_type_trees); 1107 } 1108 if (block_len_trees != 0) { 1109 free(block_len_trees); 1110 } 1111 return ok; 1112} 1113 1114#if defined(__cplusplus) || defined(c_plusplus) 1115} /* extern "C" */ 1116#endif 1117