third_party/brotli/dec/decode.c

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