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
  54 #define CODE_LENGTH_CODES 18
  55 static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = {
  56   1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
  57 };
  58
  59 #define NUM_DISTANCE_SHORT_CODES 16
  60 static const int kDistanceShortCodeIndexOffset[NUM_DISTANCE_SHORT_CODES] = {
  61   3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2
  62 };
  63
  64 static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = {
  65   0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
  66 };
  67
  68 static BROTLI_INLINE int DecodeWindowBits(BrotliBitReader* br) {
  69   if (BrotliReadBits(br, 1)) {
  70     return 17 + (int)BrotliReadBits(br, 3);
  71   } else {
  72     return 16;
  73   }
  74 }
  75
  76 /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
  77 static BROTLI_INLINE int DecodeVarLenUint8(BrotliBitReader* br) {
  78   if (BrotliReadBits(br, 1)) {
  79     int nbits = (int)BrotliReadBits(br, 3);
  80     if (nbits == 0) {
  81       return 1;
  82     } else {
  83       return (int)BrotliReadBits(br, nbits) + (1 << nbits);
  84     }
  85   }
  86   return 0;
  87 }
  88
  89 static void DecodeMetaBlockLength(BrotliBitReader* br,
  90                                   int* meta_block_length,
  91                                   int* input_end,
  92                                   int* is_uncompressed) {
  93   int size_nibbles;
  94   int i;
  95   *input_end = (int)BrotliReadBits(br, 1);
  96   *meta_block_length = 0;
  97   *is_uncompressed = 0;
  98   if (*input_end && BrotliReadBits(br, 1)) {
  99     return;
 100   }
 101   size_nibbles = (int)BrotliReadBits(br, 2) + 4;
 102   for (i = 0; i < size_nibbles; ++i) {
 103     *meta_block_length |= (int)BrotliReadBits(br, 4) << (i * 4);
 104   }
 105   ++(*meta_block_length);
 106   if (!*input_end) {
 107     *is_uncompressed = (int)BrotliReadBits(br, 1);
 108   }
 109 }
 110
 111 /* Decodes the next Huffman code from bit-stream. */
 112 static BROTLI_INLINE int ReadSymbol(const HuffmanCode* table,
 113                                     BrotliBitReader* br) {
 114   int nbits;
 115   BrotliFillBitWindow(br);
 116   table += (int)(br->val_ >> br->bit_pos_) & HUFFMAN_TABLE_MASK;
 117   nbits = table->bits - HUFFMAN_TABLE_BITS;
 118   if (nbits > 0) {
 119     br->bit_pos_ += HUFFMAN_TABLE_BITS;
 120     table += table->value;
 121     table += (int)(br->val_ >> br->bit_pos_) & ((1 << nbits) - 1);
 122   }
 123   br->bit_pos_ += table->bits;
 124   return table->value;
 125 }
 126
 127 static void PrintUcharVector(const uint8_t* v, int len) {
 128   while (len-- > 0) printf(" %d", *v++);
 129   printf("\n");
 130 }
 131
 132 static BrotliResult ReadHuffmanCodeLengths(
 133     const uint8_t* code_length_code_lengths,
 134     int num_symbols, uint8_t* code_lengths,
 135     BrotliState* s) {
 136   BrotliBitReader* br = &s->br;
 137   switch (s->sub_state[1]) {
 138     case BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN:
 139       s->symbol = 0;
 140       s->prev_code_len = kDefaultCodeLength;
 141       s->repeat = 0;
 142       s->repeat_code_len = 0;
 143       s->space = 32768;
 144
 145       if (!BrotliBuildHuffmanTable(s->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 BROTLI_RESULT_ERROR;
 151       }
 152       s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS;
 153       /* No break, continue to next state. */
 154     case BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS:
 155       while (s->symbol < num_symbols && s->space > 0) {
 156         const HuffmanCode* p = s->table;
 157         uint8_t code_len;
 158         if (!BrotliReadMoreInput(br)) {
 159           return BROTLI_RESULT_PARTIAL;
 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           s->repeat = 0;
 167           code_lengths[s->symbol++] = code_len;
 168           if (code_len != 0) {
 169             s->prev_code_len = code_len;
 170             s->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 =  s->prev_code_len;
 179           }
 180           if (s->repeat_code_len != new_len) {
 181             s->repeat = 0;
 182             s->repeat_code_len = new_len;
 183           }
 184           old_repeat = s->repeat;
 185           if (s->repeat > 0) {
 186             s->repeat -= 2;
 187             s->repeat <<= extra_bits;
 188           }
 189           s->repeat += (int)BrotliReadBits(br, extra_bits) + 3;
 190           repeat_delta = s->repeat - old_repeat;
 191           if (s->symbol + repeat_delta > num_symbols) {
 192             return BROTLI_RESULT_ERROR;
 193           }
 194           memset(&code_lengths[s->symbol], s->repeat_code_len,
 195                  (size_t)repeat_delta);
 196           s->symbol += repeat_delta;
 197           if (s->repeat_code_len != 0) {
 198             s->space -= repeat_delta << (15 - s->repeat_code_len);
 199           }
 200         }
 201       }
 202       if (s->space != 0) {
 203         printf("[ReadHuffmanCodeLengths] s->space = %d\n", s->space);
 204         return BROTLI_RESULT_ERROR;
 205       }
 206       memset(&code_lengths[s->symbol], 0, (size_t)(num_symbols - s->symbol));
 207       s->sub_state[1] = BROTLI_STATE_SUB_NONE;
 208       return BROTLI_RESULT_SUCCESS;
 209     default:
 210       return BROTLI_RESULT_ERROR;
 211   }
 212   return BROTLI_RESULT_ERROR;
 213 }
 214
 215 static BrotliResult ReadHuffmanCode(int alphabet_size,
 216                                     HuffmanCode* table,
 217                                     int* opt_table_size,
 218                                     BrotliState* s) {
 219   BrotliBitReader* br = &s->br;
 220   BrotliResult result = BROTLI_RESULT_SUCCESS;
 221   int table_size = 0;
 222   /* State machine */
 223   for (;;) {
 224     switch(s->sub_state[1]) {
 225       case BROTLI_STATE_SUB_NONE:
 226         if (!BrotliReadMoreInput(br)) {
 227           return BROTLI_RESULT_PARTIAL;
 228         }
 229         s->code_lengths =
 230             (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size,
 231                                        sizeof(*s->code_lengths));
 232         if (s->code_lengths == NULL) {
 233           return BROTLI_RESULT_ERROR;
 234         }
 235         /* simple_code_or_skip is used as follows:
 236            1 for simple code;
 237            0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
 238         s->simple_code_or_skip = (int)BrotliReadBits(br, 2);
 239         BROTLI_LOG_UINT(s->simple_code_or_skip);
 240         if (s->simple_code_or_skip == 1) {
 241           /* Read symbols, codes & code lengths directly. */
 242           int i;
 243           int max_bits_counter = alphabet_size - 1;
 244           int max_bits = 0;
 245           int symbols[4] = { 0 };
 246           const int num_symbols = (int)BrotliReadBits(br, 2) + 1;
 247           while (max_bits_counter) {
 248             max_bits_counter >>= 1;
 249             ++max_bits;
 250           }
 251           memset(s->code_lengths, 0, (size_t)alphabet_size);
 252           for (i = 0; i < num_symbols; ++i) {
 253             symbols[i] = (int)BrotliReadBits(br, max_bits) % alphabet_size;
 254             s->code_lengths[symbols[i]] = 2;
 255           }
 256           s->code_lengths[symbols[0]] = 1;
 257           switch (num_symbols) {
 258             case 1:
 259               break;
 260             case 3:
 261               if ((symbols[0] == symbols[1]) ||
 262                   (symbols[0] == symbols[2]) ||
 263                   (symbols[1] == symbols[2])) {
 264                 return BROTLI_RESULT_ERROR;
 265               }
 266               break;
 267             case 2:
 268               if (symbols[0] == symbols[1]) {
 269                 return BROTLI_RESULT_ERROR;
 270               }
 271               s->code_lengths[symbols[1]] = 1;
 272               break;
 273             case 4:
 274               if ((symbols[0] == symbols[1]) ||
 275                   (symbols[0] == symbols[2]) ||
 276                   (symbols[0] == symbols[3]) ||
 277                   (symbols[1] == symbols[2]) ||
 278                   (symbols[1] == symbols[3]) ||
 279                   (symbols[2] == symbols[3])) {
 280                 return BROTLI_RESULT_ERROR;
 281               }
 282               if (BrotliReadBits(br, 1)) {
 283                 s->code_lengths[symbols[2]] = 3;
 284                 s->code_lengths[symbols[3]] = 3;
 285               } else {
 286                 s->code_lengths[symbols[0]] = 2;
 287               }
 288               break;
 289           }
 290           BROTLI_LOG_UINT(num_symbols);
 291           s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_DONE;
 292           break;
 293         } else {  /* Decode Huffman-coded code lengths. */
 294           int i;
 295           int space = 32;
 296           int num_codes = 0;
 297           /* Static Huffman code for the code length code lengths */
 298           static const HuffmanCode huff[16] = {
 299             {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1},
 300             {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5},
 301           };
 302           for (i = 0; i < CODE_LENGTH_CODES; i++) {
 303             s->code_length_code_lengths[i] = 0;
 304           }
 305           for (i = s->simple_code_or_skip;
 306               i < CODE_LENGTH_CODES && space > 0; ++i) {
 307             const int code_len_idx = kCodeLengthCodeOrder[i];
 308             const HuffmanCode* p = huff;
 309             uint8_t v;
 310             BrotliFillBitWindow(br);
 311             p += (br->val_ >> br->bit_pos_) & 15;
 312             br->bit_pos_ += p->bits;
 313             v = (uint8_t)p->value;
 314             s->code_length_code_lengths[code_len_idx] = v;
 315             BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx);
 316             if (v != 0) {
 317               space -= (32 >> v);
 318               ++num_codes;
 319             }
 320           }
 321           if (!(num_codes == 1 || space == 0)) {
 322             return BROTLI_RESULT_ERROR;
 323           }
 324           s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN;
 325         }
 326         /* No break, go to next state */
 327       case BROTLI_STATE_SUB_HUFFMAN_LENGTH_BEGIN:
 328       case BROTLI_STATE_SUB_HUFFMAN_LENGTH_SYMBOLS:
 329         result = ReadHuffmanCodeLengths(s->code_length_code_lengths,
 330                                         alphabet_size, s->code_lengths, s);
 331         if (result != BROTLI_RESULT_SUCCESS) return result;
 332         s->sub_state[1] = BROTLI_STATE_SUB_HUFFMAN_DONE;
 333         /* No break, go to next state */
 334       case BROTLI_STATE_SUB_HUFFMAN_DONE:
 335         table_size = BrotliBuildHuffmanTable(table, HUFFMAN_TABLE_BITS,
 336                                              s->code_lengths, alphabet_size);
 337         if (table_size == 0) {
 338           printf("[ReadHuffmanCode] BuildHuffmanTable failed: ");
 339           PrintUcharVector(s->code_lengths, alphabet_size);
 340           return BROTLI_RESULT_ERROR;
 341         }
 342         free(s->code_lengths);
 343         s->code_lengths = NULL;
 344         if (opt_table_size) {
 345           *opt_table_size = table_size;
 346         }
 347         s->sub_state[1] = BROTLI_STATE_SUB_NONE;
 348         return result;
 349       default:
 350         return BROTLI_RESULT_ERROR;  /* unknown state */
 351     }
 352   }
 353
 354   return BROTLI_RESULT_ERROR;
 355 }
 356
 357 static BROTLI_INLINE int ReadBlockLength(const HuffmanCode* table,
 358                                          BrotliBitReader* br) {
 359   int code;
 360   int nbits;
 361   code = ReadSymbol(table, br);
 362   nbits = kBlockLengthPrefixCode[code].nbits;
 363   return kBlockLengthPrefixCode[code].offset + (int)BrotliReadBits(br, nbits);
 364 }
 365
 366 static int TranslateShortCodes(int code, int* ringbuffer, int index) {
 367   int val;
 368   if (code < NUM_DISTANCE_SHORT_CODES) {
 369     index += kDistanceShortCodeIndexOffset[code];
 370     index &= 3;
 371     val = ringbuffer[index] + kDistanceShortCodeValueOffset[code];
 372   } else {
 373     val = code - NUM_DISTANCE_SHORT_CODES + 1;
 374   }
 375   return val;
 376 }
 377
 378 static void MoveToFront(uint8_t* v, uint8_t index) {
 379   uint8_t value = v[index];
 380   uint8_t i = index;
 381   for (; i; --i) v[i] = v[i - 1];
 382   v[0] = value;
 383 }
 384
 385 static void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
 386   uint8_t mtf[256];
 387   int i;
 388   for (i = 0; i < 256; ++i) {
 389     mtf[i] = (uint8_t)i;
 390   }
 391   for (i = 0; i < v_len; ++i) {
 392     uint8_t index = v[i];
 393     v[i] = mtf[index];
 394     if (index) MoveToFront(mtf, index);
 395   }
 396 }
 397
 398 static BrotliResult HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
 399                                            BrotliState* s) {
 400   switch (s->sub_state[0]) {
 401     case BROTLI_STATE_SUB_NONE:
 402       s->next = group->codes;
 403       s->htree_index = 0;
 404       s->sub_state[0] = BROTLI_STATE_SUB_TREE_GROUP;
 405       /* No break, continue to next state. */
 406     case BROTLI_STATE_SUB_TREE_GROUP:
 407       while (s->htree_index < group->num_htrees) {
 408         int table_size;
 409         BrotliResult result =
 410             ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
 411         if (result != BROTLI_RESULT_SUCCESS) return result;
 412         group->htrees[s->htree_index] = s->next;
 413         s->next += table_size;
 414         if (table_size == 0) {
 415           return BROTLI_RESULT_ERROR;
 416         }
 417         ++s->htree_index;
 418       }
 419       s->sub_state[0] = BROTLI_STATE_SUB_NONE;
 420       return BROTLI_RESULT_SUCCESS;
 421     default:
 422       return BROTLI_RESULT_ERROR;  /* unknown state */
 423   }
 424
 425   return BROTLI_RESULT_ERROR;
 426 }
 427
 428 static BrotliResult DecodeContextMap(int context_map_size,
 429                                      int* num_htrees,
 430                                      uint8_t** context_map,
 431                                      BrotliState* s) {
 432   BrotliBitReader* br = &s->br;
 433   BrotliResult result = BROTLI_RESULT_SUCCESS;
 434   int use_rle_for_zeros;
 435
 436   switch(s->sub_state[0]) {
 437     case BROTLI_STATE_SUB_NONE:
 438       if (!BrotliReadMoreInput(br)) {
 439         return BROTLI_RESULT_PARTIAL;
 440       }
 441       *num_htrees = DecodeVarLenUint8(br) + 1;
 442
 443       s->context_index = 0;
 444
 445       BROTLI_LOG_UINT(context_map_size);
 446       BROTLI_LOG_UINT(*num_htrees);
 447
 448       *context_map = (uint8_t*)malloc((size_t)context_map_size);
 449       if (*context_map == 0) {
 450         return BROTLI_RESULT_ERROR;
 451       }
 452       if (*num_htrees <= 1) {
 453         memset(*context_map, 0, (size_t)context_map_size);
 454         return BROTLI_RESULT_SUCCESS;
 455       }
 456
 457       use_rle_for_zeros = (int)BrotliReadBits(br, 1);
 458       if (use_rle_for_zeros) {
 459         s->max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1;
 460       } else {
 461         s->max_run_length_prefix = 0;
 462       }
 463       s->context_map_table = (HuffmanCode*)malloc(
 464           BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(*s->context_map_table));
 465       if (s->context_map_table == NULL) {
 466         return BROTLI_RESULT_ERROR;
 467       }
 468       s->sub_state[0] = BROTLI_STATE_SUB_CONTEXT_MAP_HUFFMAN;
 469       /* No break, continue to next state. */
 470     case BROTLI_STATE_SUB_CONTEXT_MAP_HUFFMAN:
 471       result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,
 472                                s->context_map_table, NULL, s);
 473       if (result != BROTLI_RESULT_SUCCESS) return result;
 474       s->sub_state[0] = BROTLI_STATE_SUB_CONTEXT_MAPS;
 475       /* No break, continue to next state. */
 476     case BROTLI_STATE_SUB_CONTEXT_MAPS:
 477       while (s->context_index < context_map_size) {
 478         int code;
 479         if (!BrotliReadMoreInput(br)) {
 480           return BROTLI_RESULT_PARTIAL;
 481         }
 482         code = ReadSymbol(s->context_map_table, br);
 483         if (code == 0) {
 484           (*context_map)[s->context_index] = 0;
 485           ++s->context_index;
 486         } else if (code <= s->max_run_length_prefix) {
 487           int reps = 1 + (1 << code) + (int)BrotliReadBits(br, code);
 488           while (--reps) {
 489             if (s->context_index >= context_map_size) {
 490               return BROTLI_RESULT_ERROR;
 491             }
 492             (*context_map)[s->context_index] = 0;
 493             ++s->context_index;
 494           }
 495         } else {
 496           (*context_map)[s->context_index] =
 497               (uint8_t)(code - s->max_run_length_prefix);
 498           ++s->context_index;
 499         }
 500       }
 501       if (BrotliReadBits(br, 1)) {
 502         InverseMoveToFrontTransform(*context_map, context_map_size);
 503       }
 504       free(s->context_map_table);
 505       s->context_map_table = NULL;
 506       s->sub_state[0] = BROTLI_STATE_SUB_NONE;
 507       return BROTLI_RESULT_SUCCESS;
 508     default:
 509       return BROTLI_RESULT_ERROR;  /* unknown state */
 510   }
 511
 512   return BROTLI_RESULT_ERROR;
 513 }
 514
 515 static BROTLI_INLINE void DecodeBlockType(const int max_block_type,
 516                                           const HuffmanCode* trees,
 517                                           int tree_type,
 518                                           int* block_types,
 519                                           int* ringbuffers,
 520                                           int* indexes,
 521                                           BrotliBitReader* br) {
 522   int* ringbuffer = ringbuffers + tree_type * 2;
 523   int* index = indexes + tree_type;
 524   int type_code =
 525       ReadSymbol(&trees[tree_type * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
 526   int block_type;
 527   if (type_code == 0) {
 528     block_type = ringbuffer[*index & 1];
 529   } else if (type_code == 1) {
 530     block_type = ringbuffer[(*index - 1) & 1] + 1;
 531   } else {
 532     block_type = type_code - 2;
 533   }
 534   if (block_type >= max_block_type) {
 535     block_type -= max_block_type;
 536   }
 537   block_types[tree_type] = block_type;
 538   ringbuffer[(*index) & 1] = block_type;
 539   ++(*index);
 540 }
 541
 542 /* Decodes the block type and updates the state for literal context. */
 543 static BROTLI_INLINE void DecodeBlockTypeWithContext(BrotliState* s,
 544                                                      BrotliBitReader* br) {
 545   DecodeBlockType(s->num_block_types[0],
 546                   s->block_type_trees, 0,
 547                   s->block_type, s->block_type_rb,
 548                   s->block_type_rb_index, br);
 549   s->block_length[0] = ReadBlockLength(s->block_len_trees, br);
 550   s->context_offset = s->block_type[0] << kLiteralContextBits;
 551   s->context_map_slice = s->context_map + s->context_offset;
 552   s->literal_htree_index = s->context_map_slice[0];
 553   s->context_mode = s->context_modes[s->block_type[0]];
 554   s->context_lookup_offset1 = kContextLookupOffsets[s->context_mode];
 555   s->context_lookup_offset2 = kContextLookupOffsets[s->context_mode + 1];
 556 }
 557
 558 /* Copy len bytes from src to dst. It can write up to ten extra bytes
 559    after the end of the copy.
 560
 561    The main part of this loop is a simple copy of eight bytes at a time until
 562    we've copied (at least) the requested amount of bytes.  However, if dst and
 563    src are less than eight bytes apart (indicating a repeating pattern of
 564    length < 8), we first need to expand the pattern in order to get the correct
 565    results. For instance, if the buffer looks like this, with the eight-byte
 566    <src> and <dst> patterns marked as intervals:
 567
 568       abxxxxxxxxxxxx
 569       [------]           src
 570         [------]         dst
 571
 572    a single eight-byte copy from <src> to <dst> will repeat the pattern once,
 573    after which we can move <dst> two bytes without moving <src>:
 574
 575       ababxxxxxxxxxx
 576       [------]           src
 577           [------]       dst
 578
 579    and repeat the exercise until the two no longer overlap.
 580
 581    This allows us to do very well in the special case of one single byte
 582    repeated many times, without taking a big hit for more general cases.
 583
 584    The worst case of extra writing past the end of the match occurs when
 585    dst - src == 1 and len == 1; the last copy will read from byte positions
 586    [0..7] and write to [4..11], whereas it was only supposed to write to
 587    position 1. Thus, ten excess bytes.
 588 */
 589 static BROTLI_INLINE void IncrementalCopyFastPath(
 590     uint8_t* dst, const uint8_t* src, int len) {
 591   if (src < dst) {
 592     while (dst - src < 8) {
 593       UNALIGNED_MOVE64(dst, src);
 594       len -= (int)(dst - src);
 595       dst += dst - src;
 596     }
 597   }
 598   while (len > 0) {
 599     UNALIGNED_COPY64(dst, src);
 600     src += 8;
 601     dst += 8;
 602     len -= 8;
 603   }
 604 }
 605
 606 BrotliResult CopyUncompressedBlockToOutput(BrotliOutput output,
 607                                            int pos,
 608                                            BrotliState* s) {
 609   const int rb_size = s->ringbuffer_mask + 1;
 610   uint8_t* ringbuffer_end = s->ringbuffer + rb_size;
 611   int rb_pos = pos & s->ringbuffer_mask;
 612   int br_pos = s->br.pos_ & BROTLI_IBUF_MASK;
 613   uint32_t remaining_bits;
 614   int num_read;
 615
 616   /* State machine */
 617   for (;;) {
 618     switch (s->sub_state[0]) {
 619       case BROTLI_STATE_SUB_NONE:
 620         /* For short lengths copy byte-by-byte */
 621         if (s->meta_block_remaining_len < 8 || s->br.bit_pos_ +
 622             (uint32_t)(s->meta_block_remaining_len << 3) < s->br.bit_end_pos_) {
 623           s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_SHORT;
 624           break;
 625         }
 626         if (s->br.bit_end_pos_ < 64) {
 627           return BROTLI_RESULT_ERROR;
 628         }
 629         /*
 630          * Copy remaining 0-4 in 32-bit case or 0-8 bytes in the 64-bit case
 631          * from s->br.val_ to ringbuffer.
 632          */
 633 #if (BROTLI_USE_64_BITS)
 634         remaining_bits = 64;
 635 #else
 636         remaining_bits = 32;
 637 #endif
 638         while (s->br.bit_pos_ < remaining_bits) {
 639           s->ringbuffer[rb_pos] = (uint8_t)(s->br.val_ >> s->br.bit_pos_);
 640           s->br.bit_pos_ += 8;
 641           ++rb_pos;
 642           --s->meta_block_remaining_len;
 643         }
 644
 645         /* Copy remaining bytes from s->br.buf_ to ringbuffer. */
 646         s->nbytes = (int)(s->br.bit_end_pos_ - s->br.bit_pos_) >> 3;
 647         if (br_pos + s->nbytes > BROTLI_IBUF_MASK) {
 648           int tail = BROTLI_IBUF_MASK + 1 - br_pos;
 649           memcpy(&s->ringbuffer[rb_pos], &s->br.buf_[br_pos], (size_t)tail);
 650           s->nbytes -= tail;
 651           rb_pos += tail;
 652           s->meta_block_remaining_len -= tail;
 653           br_pos = 0;
 654         }
 655         memcpy(&s->ringbuffer[rb_pos], &s->br.buf_[br_pos], (size_t)s->nbytes);
 656         rb_pos += s->nbytes;
 657         s->meta_block_remaining_len -= s->nbytes;
 658
 659         /* If we wrote past the logical end of the ringbuffer, copy the tail of
 660            the ringbuffer to its beginning and flush the ringbuffer to the
 661            output. */
 662         if (rb_pos >= rb_size) {
 663           if (BrotliWrite(output, s->ringbuffer, (size_t)rb_size) < rb_size) {
 664             return BROTLI_RESULT_ERROR;
 665           }
 666           rb_pos -= rb_size;
 667           s->meta_block_remaining_len += rb_size;
 668           memcpy(s->ringbuffer, ringbuffer_end, (size_t)rb_pos);
 669         }
 670         s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_FILL;
 671         break;
 672       case BROTLI_STATE_SUB_UNCOMPRESSED_SHORT:
 673         while (s->meta_block_remaining_len > 0) {
 674           if (!BrotliReadMoreInput(&s->br)) {
 675             return BROTLI_RESULT_PARTIAL;
 676           }
 677           s->ringbuffer[rb_pos++] = (uint8_t)BrotliReadBits(&s->br, 8);
 678           if (rb_pos == rb_size) {
 679             if (BrotliWrite(output, s->ringbuffer, (size_t)rb_size) < rb_size) {
 680               return BROTLI_RESULT_ERROR;
 681             }
 682             rb_pos = 0;
 683           }
 684           s->meta_block_remaining_len--;
 685         }
 686         s->sub_state[0] = BROTLI_STATE_SUB_NONE;
 687         return BROTLI_RESULT_SUCCESS;
 688       case BROTLI_STATE_SUB_UNCOMPRESSED_FILL:
 689         /* If we have more to copy than the remaining size of the ringbuffer,
 690            then we first fill the ringbuffer from the input and then flush the
 691            ringbuffer to the output */
 692         while (rb_pos + s->meta_block_remaining_len >= rb_size) {
 693           s->nbytes = rb_size - rb_pos;
 694           if (BrotliRead(s->br.input_, &s->ringbuffer[rb_pos],
 695                          (size_t)s->nbytes) < s->nbytes) {
 696             return BROTLI_RESULT_PARTIAL;
 697           }
 698           if (BrotliWrite(output, s->ringbuffer, (size_t)rb_size) < s->nbytes) {
 699             return BROTLI_RESULT_ERROR;
 700           }
 701           s->meta_block_remaining_len -= s->nbytes;
 702           rb_pos = 0;
 703         }
 704         s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_COPY;
 705         /* No break, continue to next state */
 706       case BROTLI_STATE_SUB_UNCOMPRESSED_COPY:
 707         /* Copy straight from the input onto the ringbuffer. The ringbuffer will
 708            be flushed to the output at a later time. */
 709         num_read = BrotliRead(s->br.input_, &s->ringbuffer[rb_pos],
 710                               (size_t)s->meta_block_remaining_len);
 711         s->meta_block_remaining_len -= num_read;
 712         if (s->meta_block_remaining_len > 0) {
 713           return BROTLI_RESULT_PARTIAL;
 714         }
 715
 716         /* Restore the state of the bit reader. */
 717         BrotliInitBitReader(&s->br, s->br.input_, s->br.finish_);
 718         s->sub_state[0] = BROTLI_STATE_SUB_UNCOMPRESSED_WARMUP;
 719         /* No break, continue to next state */
 720       case BROTLI_STATE_SUB_UNCOMPRESSED_WARMUP:
 721         if (!BrotliWarmupBitReader(&s->br)) {
 722           return BROTLI_RESULT_PARTIAL;
 723         }
 724         s->sub_state[0] = BROTLI_STATE_SUB_NONE;
 725         return BROTLI_RESULT_SUCCESS;
 726         break;
 727       default:
 728         return BROTLI_RESULT_ERROR;  /* Unknown state */
 729     }
 730   }
 731   return BROTLI_RESULT_ERROR;
 732 }
 733
 734 BrotliResult BrotliDecompressedSize(size_t encoded_size,
 735                                     const uint8_t* encoded_buffer,
 736                                     size_t* decoded_size) {
 737   int i;
 738   uint64_t val = 0;
 739   int bit_pos = 0;
 740   int is_last;
 741   int is_uncompressed = 0;
 742   int size_nibbles;
 743   int meta_block_len = 0;
 744   if (encoded_size == 0) {
 745     return BROTLI_RESULT_ERROR;
 746   }
 747   /* Look at the first 8 bytes, it is enough to decode the length of the first
 748      meta-block. */
 749   for (i = 0; (size_t)i < encoded_size && i < 8; ++i) {
 750     val |= (uint64_t)encoded_buffer[i] << (8 * i);
 751   }
 752   /* Skip the window bits. */
 753   bit_pos += (val & 1) ? 4 : 1;
 754   /* Decode the ISLAST bit. */
 755   is_last = (val >> bit_pos) & 1;
 756   ++bit_pos;
 757   if (is_last) {
 758     /* Decode the ISEMPTY bit, if it is set to 1, we are done. */
 759     if ((val >> bit_pos) & 1) {
 760       *decoded_size = 0;
 761       return BROTLI_RESULT_SUCCESS;
 762     }
 763     ++bit_pos;
 764   }
 765   /* Decode the length of the first meta-block. */
 766   size_nibbles = (int)((val >> bit_pos) & 3) + 4;
 767   bit_pos += 2;
 768   for (i = 0; i < size_nibbles; ++i) {
 769     meta_block_len |= (int)((val >> bit_pos) & 0xf) << (4 * i);
 770     bit_pos += 4;
 771   }
 772   ++meta_block_len;
 773   if (is_last) {
 774     /* If this meta-block is the only one, we are done. */
 775     *decoded_size = (size_t)meta_block_len;
 776     return BROTLI_RESULT_SUCCESS;
 777   }
 778   is_uncompressed = (val >> bit_pos) & 1;
 779   ++bit_pos;
 780   if (is_uncompressed) {
 781     /* If the first meta-block is uncompressed, we skip it and look at the
 782        first two bits (ISLAST and ISEMPTY) of the next meta-block, and if
 783        both are set to 1, we have a stream with an uncompressed meta-block
 784        followed by an empty one, so the decompressed size is the size of the
 785        first meta-block. */
 786     size_t offset = (size_t)((bit_pos + 7) >> 3) + (size_t)meta_block_len;
 787     if (offset < encoded_size && ((encoded_buffer[offset] & 3) == 3)) {
 788       *decoded_size = (size_t)meta_block_len;
 789       return BROTLI_RESULT_SUCCESS;
 790     }
 791   }
 792   return BROTLI_RESULT_ERROR;
 793 }
 794
 795 BrotliResult BrotliDecompressBuffer(size_t encoded_size,
 796                                     const uint8_t* encoded_buffer,
 797                                     size_t* decoded_size,
 798                                     uint8_t* decoded_buffer) {
 799   BrotliMemInput memin;
 800   BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin);
 801   BrotliMemOutput mout;
 802   BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout);
 803   BrotliResult success = BrotliDecompress(in, out);
 804   *decoded_size = mout.pos;
 805   return success;
 806 }
 807
 808 BrotliResult BrotliDecompress(BrotliInput input, BrotliOutput output) {
 809   BrotliState s;
 810   BrotliResult result;
 811   BrotliStateInit(&s);
 812   result = BrotliDecompressStreaming(input, output, 1, &s);
 813   if (result == BROTLI_RESULT_PARTIAL) {
 814     /* Not ok: it didn't finish even though this is a non-streaming function. */
 815     result = BROTLI_RESULT_ERROR;
 816   }
 817   BrotliStateCleanup(&s);
 818   return result;
 819 }
 820
 821 BrotliResult BrotliDecompressBufferStreaming(size_t* available_in,
 822                                              const uint8_t** next_in,
 823                                              int finish,
 824                                              size_t* available_out,
 825                                              uint8_t** next_out,
 826                                              size_t* total_out,
 827                                              BrotliState* s) {
 828   BrotliResult result;
 829   BrotliMemInput memin;
 830   BrotliInput in = BrotliInitMemInput(*next_in, *available_in, &memin);
 831   BrotliMemOutput memout;
 832   BrotliOutput out = BrotliInitMemOutput(*next_out, *available_out, &memout);
 833
 834   result = BrotliDecompressStreaming(in, out, finish, s);
 835
 836   /* The current implementation reads everything, so 0 bytes are available. */
 837   *next_in += memin.pos;
 838   *available_in -= memin.pos;
 839
 840   /* Update the output position to where we write next. */
 841   *next_out += memout.pos;
 842   *available_out -= memout.pos;
 843   *total_out += memout.pos;
 844
 845   return result;
 846 }
 847
 848 BrotliResult BrotliDecompressStreaming(BrotliInput input, BrotliOutput output,
 849                                        int finish, BrotliState* s) {
 850   uint8_t context;
 851   int pos = s->pos;
 852   int i = s->loop_counter;
 853   BrotliResult result = BROTLI_RESULT_SUCCESS;
 854   BrotliBitReader* br = &s->br;
 855   int initial_remaining_len;
 856   int bytes_copied;
 857
 858   /* We need the slack region for the following reasons:
 859        - always doing two 8-byte copies for fast backward copying
 860        - transforms
 861        - flushing the input s->ringbuffer when decoding uncompressed blocks */
 862   static const int kRingBufferWriteAheadSlack = 128 + BROTLI_READ_SIZE;
 863
 864   s->br.finish_ = finish;
 865
 866   /* State machine */
 867   for (;;) {
 868     if (result != BROTLI_RESULT_SUCCESS) {
 869       if (result == BROTLI_RESULT_PARTIAL && finish) {
 870         printf("Unexpected end of input. State: %d\n", s->state);
 871         result = BROTLI_RESULT_ERROR;
 872       }
 873       break;  /* Fail, or partial data. */
 874     }
 875
 876     switch (s->state) {
 877       case BROTLI_STATE_UNINITED:
 878         pos = 0;
 879         s->input_end = 0;
 880         s->window_bits = 0;
 881         s->max_distance = 0;
 882         s->dist_rb[0] = 16;
 883         s->dist_rb[1] = 15;
 884         s->dist_rb[2] = 11;
 885         s->dist_rb[3] = 4;
 886         s->dist_rb_idx = 0;
 887         s->prev_byte1 = 0;
 888         s->prev_byte2 = 0;
 889         s->block_type_trees = NULL;
 890         s->block_len_trees = NULL;
 891
 892         BrotliInitBitReader(br, input, finish);
 893
 894         s->state = BROTLI_STATE_BITREADER_WARMUP;
 895         /* No break, continue to next state */
 896       case BROTLI_STATE_BITREADER_WARMUP:
 897         if (!BrotliWarmupBitReader(br)) {
 898           result = BROTLI_RESULT_PARTIAL;
 899           break;
 900         }
 901         /* Decode window size. */
 902         s->window_bits = DecodeWindowBits(br);
 903         s->max_backward_distance = (1 << s->window_bits) - 16;
 904
 905         s->ringbuffer_size = 1 << s->window_bits;
 906         s->ringbuffer_mask = s->ringbuffer_size - 1;
 907         s->ringbuffer = (uint8_t*)malloc((size_t)(s->ringbuffer_size +
 908                                                kRingBufferWriteAheadSlack +
 909                                                kMaxDictionaryWordLength));
 910         if (!s->ringbuffer) {
 911           result = BROTLI_RESULT_ERROR;
 912           break;
 913         }
 914         s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
 915
 916         s->block_type_trees = (HuffmanCode*)malloc(
 917             3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
 918         s->block_len_trees = (HuffmanCode*)malloc(
 919             3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
 920         if (s->block_type_trees == NULL || s->block_len_trees == NULL) {
 921           result = BROTLI_RESULT_ERROR;
 922           break;
 923         }
 924
 925         s->state = BROTLI_STATE_METABLOCK_BEGIN;
 926         /* No break, continue to next state */
 927       case BROTLI_STATE_METABLOCK_BEGIN:
 928         if (!BrotliReadMoreInput(br)) {
 929           result = BROTLI_RESULT_PARTIAL;
 930           break;
 931         }
 932         if (s->input_end) {
 933           s->state = BROTLI_STATE_DONE;
 934           break;
 935         }
 936         s->meta_block_remaining_len = 0;
 937         s->block_length[0] = 1 << 28;
 938         s->block_length[1] = 1 << 28;
 939         s->block_length[2] = 1 << 28;
 940         s->block_type[0] = 0;
 941         s->num_block_types[0] = 1;
 942         s->num_block_types[1] = 1;
 943         s->num_block_types[2] = 1;
 944         s->block_type_rb[0] = 0;
 945         s->block_type_rb[1] = 1;
 946         s->block_type_rb[2] = 0;
 947         s->block_type_rb[3] = 1;
 948         s->block_type_rb[4] = 0;
 949         s->block_type_rb[5] = 1;
 950         s->block_type_rb_index[0] = 0;
 951         s->context_map = NULL;
 952         s->context_modes = NULL;
 953         s->dist_context_map = NULL;
 954         s->context_offset = 0;
 955         s->context_map_slice = NULL;
 956         s->literal_htree_index = 0;
 957         s->dist_context_offset = 0;
 958         s->dist_context_map_slice = NULL;
 959         s->dist_htree_index = 0;
 960         s->context_lookup_offset1 = 0;
 961         s->context_lookup_offset2 = 0;
 962         for (i = 0; i < 3; ++i) {
 963           s->hgroup[i].codes = NULL;
 964           s->hgroup[i].htrees = NULL;
 965         }
 966         s->state = BROTLI_STATE_METABLOCK_HEADER_1;
 967         /* No break, continue to next state */
 968       case BROTLI_STATE_METABLOCK_HEADER_1:
 969         if (!BrotliReadMoreInput(br)) {
 970           result = BROTLI_RESULT_PARTIAL;
 971           break;
 972         }
 973         BROTLI_LOG_UINT(pos);
 974         DecodeMetaBlockLength(br, &s->meta_block_remaining_len,
 975                               &s->input_end, &s->is_uncompressed);
 976         BROTLI_LOG_UINT(s->meta_block_remaining_len);
 977         if (s->meta_block_remaining_len == 0) {
 978           s->state = BROTLI_STATE_METABLOCK_DONE;
 979           break;
 980         }
 981         if (s->is_uncompressed) {
 982           BrotliSetBitPos(br, (s->br.bit_pos_ + 7) & (uint32_t)(~7UL));
 983           s->state = BROTLI_STATE_UNCOMPRESSED;
 984           break;
 985         }
 986         i = 0;
 987         s->state = BROTLI_STATE_HUFFMAN_CODE_0;
 988         break;
 989       case BROTLI_STATE_UNCOMPRESSED:
 990         initial_remaining_len = s->meta_block_remaining_len;
 991         /* pos is given as argument since s->pos is only updated at the end. */
 992         result = CopyUncompressedBlockToOutput(output, pos, s);
 993         bytes_copied = initial_remaining_len - s->meta_block_remaining_len;
 994         pos += bytes_copied;
 995         if (bytes_copied > 0) {
 996           s->prev_byte2 = bytes_copied == 1 ? s->prev_byte1 :
 997               s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
 998           s->prev_byte1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
 999         }
1000         if (result != BROTLI_RESULT_SUCCESS) break;
1001         s->state = BROTLI_STATE_METABLOCK_DONE;
1002         break;
1003       case BROTLI_STATE_HUFFMAN_CODE_0:
1004         if (i >= 3) {
1005           BROTLI_LOG_UINT(s->num_block_types[0]);
1006           BROTLI_LOG_UINT(s->num_block_types[1]);
1007           BROTLI_LOG_UINT(s->num_block_types[2]);
1008           BROTLI_LOG_UINT(s->block_length[0]);
1009           BROTLI_LOG_UINT(s->block_length[1]);
1010           BROTLI_LOG_UINT(s->block_length[2]);
1011
1012           s->state = BROTLI_STATE_METABLOCK_HEADER_2;
1013           break;
1014         }
1015         s->num_block_types[i] = DecodeVarLenUint8(br) + 1;
1016         s->state = BROTLI_STATE_HUFFMAN_CODE_1;
1017         /* No break, continue to next state */
1018       case BROTLI_STATE_HUFFMAN_CODE_1:
1019         if (s->num_block_types[i] >= 2) {
1020           result = ReadHuffmanCode(s->num_block_types[i] + 2,
1021               &s->block_type_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
1022               NULL, s);
1023           if (result != BROTLI_RESULT_SUCCESS) break;
1024           s->state = BROTLI_STATE_HUFFMAN_CODE_2;
1025         } else {
1026           i++;
1027           s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1028           break;
1029         }
1030         /* No break, continue to next state */
1031       case BROTLI_STATE_HUFFMAN_CODE_2:
1032         result = ReadHuffmanCode(kNumBlockLengthCodes,
1033             &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
1034             NULL, s);
1035         if (result != BROTLI_RESULT_SUCCESS) break;
1036         s->block_length[i] = ReadBlockLength(
1037             &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1038         s->block_type_rb_index[i] = 1;
1039         i++;
1040         s->state = BROTLI_STATE_HUFFMAN_CODE_0;
1041         break;
1042       case BROTLI_STATE_METABLOCK_HEADER_2:
1043         if (!BrotliReadMoreInput(br)) {
1044           result = BROTLI_RESULT_PARTIAL;
1045           break;
1046         }
1047         s->distance_postfix_bits = (int)BrotliReadBits(br, 2);
1048         s->num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES +
1049             ((int)BrotliReadBits(br, 4) << s->distance_postfix_bits);
1050         s->distance_postfix_mask = (1 << s->distance_postfix_bits) - 1;
1051         s->num_distance_codes = (s->num_direct_distance_codes +
1052                               (48 << s->distance_postfix_bits));
1053         s->context_modes = (uint8_t*)malloc((size_t)s->num_block_types[0]);
1054         if (s->context_modes == 0) {
1055           result = BROTLI_RESULT_ERROR;
1056           break;
1057         }
1058         for (i = 0; i < s->num_block_types[0]; ++i) {
1059           s->context_modes[i] = (uint8_t)(BrotliReadBits(br, 2) << 1);
1060           BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
1061         }
1062         BROTLI_LOG_UINT(s->num_direct_distance_codes);
1063         BROTLI_LOG_UINT(s->distance_postfix_bits);
1064         s->state = BROTLI_STATE_CONTEXT_MAP_1;
1065         /* No break, continue to next state */
1066       case BROTLI_STATE_CONTEXT_MAP_1:
1067         result = DecodeContextMap(s->num_block_types[0] << kLiteralContextBits,
1068                                   &s->num_literal_htrees, &s->context_map, s);
1069
1070         s->trivial_literal_context = 1;
1071         for (i = 0; i < s->num_block_types[0] << kLiteralContextBits; i++) {
1072           if (s->context_map[i] != i >> kLiteralContextBits) {
1073             s->trivial_literal_context = 0;
1074             break;
1075           }
1076         }
1077
1078         if (result != BROTLI_RESULT_SUCCESS) break;
1079         s->state = BROTLI_STATE_CONTEXT_MAP_2;
1080         /* No break, continue to next state */
1081       case BROTLI_STATE_CONTEXT_MAP_2:
1082         result = DecodeContextMap(s->num_block_types[2] << kDistanceContextBits,
1083                                   &s->num_dist_htrees, &s->dist_context_map, s);
1084         if (result != BROTLI_RESULT_SUCCESS) break;
1085
1086         BrotliHuffmanTreeGroupInit(&s->hgroup[0], kNumLiteralCodes,
1087                                    s->num_literal_htrees);
1088         BrotliHuffmanTreeGroupInit(&s->hgroup[1], kNumInsertAndCopyCodes,
1089                                    s->num_block_types[1]);
1090         BrotliHuffmanTreeGroupInit(&s->hgroup[2], s->num_distance_codes,
1091                                    s->num_dist_htrees);
1092         i = 0;
1093         s->state = BROTLI_STATE_TREE_GROUP;
1094         /* No break, continue to next state */
1095       case BROTLI_STATE_TREE_GROUP:
1096         result = HuffmanTreeGroupDecode(&s->hgroup[i], s);
1097         if (result != BROTLI_RESULT_SUCCESS) break;
1098         i++;
1099
1100         if (i >= 3) {
1101           s->context_map_slice = s->context_map;
1102           s->dist_context_map_slice = s->dist_context_map;
1103           s->context_mode = s->context_modes[s->block_type[0]];
1104           s->context_lookup_offset1 = kContextLookupOffsets[s->context_mode];
1105           s->context_lookup_offset2 =
1106               kContextLookupOffsets[s->context_mode + 1];
1107           s->htree_command = s->hgroup[1].htrees[0];
1108
1109           s->state = BROTLI_STATE_BLOCK_BEGIN;
1110           break;
1111         }
1112
1113         break;
1114       case BROTLI_STATE_BLOCK_BEGIN:
1115  /* Block decoding is the inner loop, jumping with goto makes it 3% faster */
1116  BlockBegin:
1117         if (!BrotliReadMoreInput(br)) {
1118           result = BROTLI_RESULT_PARTIAL;
1119           break;
1120         }
1121         if (s->meta_block_remaining_len <= 0) {
1122           /* Protect pos from overflow, wrap it around at every GB of input. */
1123           pos &= 0x3fffffff;
1124
1125           /* Next metablock, if any */
1126           s->state = BROTLI_STATE_METABLOCK_DONE;
1127           break;
1128         }
1129
1130         if (s->block_length[1] == 0) {
1131           DecodeBlockType(s->num_block_types[1],
1132                           s->block_type_trees, 1,
1133                           s->block_type, s->block_type_rb,
1134                           s->block_type_rb_index, br);
1135           s->block_length[1] = ReadBlockLength(
1136               &s->block_len_trees[BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1137           s->htree_command = s->hgroup[1].htrees[s->block_type[1]];
1138         }
1139         --s->block_length[1];
1140         s->cmd_code = ReadSymbol(s->htree_command, br);
1141         s->range_idx = s->cmd_code >> 6;
1142         if (s->range_idx >= 2) {
1143           s->range_idx -= 2;
1144           s->distance_code = -1;
1145         } else {
1146           s->distance_code = 0;
1147         }
1148         s->insert_code =
1149             kInsertRangeLut[s->range_idx] + ((s->cmd_code >> 3) & 7);
1150         s->copy_code = kCopyRangeLut[s->range_idx] + (s->cmd_code & 7);
1151         s->insert_length = kInsertLengthPrefixCode[s->insert_code].offset +
1152             (int)BrotliReadBits(br,
1153                                 kInsertLengthPrefixCode[s->insert_code].nbits);
1154         s->copy_length = kCopyLengthPrefixCode[s->copy_code].offset +
1155             (int)BrotliReadBits(br, kCopyLengthPrefixCode[s->copy_code].nbits);
1156         BROTLI_LOG_UINT(s->insert_length);
1157         BROTLI_LOG_UINT(s->copy_length);
1158         BROTLI_LOG_UINT(s->distance_code);
1159
1160         i = 0;
1161         s->state = BROTLI_STATE_BLOCK_INNER;
1162         /* No break, go to next state */
1163       case BROTLI_STATE_BLOCK_INNER:
1164         if (s->trivial_literal_context) {
1165           while (i < s->insert_length) {
1166             if (!BrotliReadMoreInput(br)) {
1167               result = BROTLI_RESULT_PARTIAL;
1168               break;
1169             }
1170             if (s->block_length[0] == 0) {
1171               DecodeBlockTypeWithContext(s, br);
1172             }
1173
1174             s->ringbuffer[pos & s->ringbuffer_mask] = (uint8_t)ReadSymbol(
1175                 s->hgroup[0].htrees[s->literal_htree_index], br);
1176
1177             --s->block_length[0];
1178             BROTLI_LOG_UINT(s->literal_htree_index);
1179             BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1180             if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1181               if (BrotliWrite(output, s->ringbuffer,
1182                               (size_t)s->ringbuffer_size) < 0) {
1183                 result = BROTLI_RESULT_ERROR;
1184                 break;
1185               }
1186             }
1187             ++pos;
1188             ++i;
1189           }
1190         } else {
1191           while (i < s->insert_length) {
1192             if (!BrotliReadMoreInput(br)) {
1193               result = BROTLI_RESULT_PARTIAL;
1194               break;
1195             }
1196             if (s->block_length[0] == 0) {
1197               DecodeBlockTypeWithContext(s, br);
1198             }
1199
1200             context =
1201                 (kContextLookup[s->context_lookup_offset1 + s->prev_byte1] |
1202                  kContextLookup[s->context_lookup_offset2 + s->prev_byte2]);
1203             BROTLI_LOG_UINT(context);
1204             s->literal_htree_index = s->context_map_slice[context];
1205             --s->block_length[0];
1206             s->prev_byte2 = s->prev_byte1;
1207             s->prev_byte1 = (uint8_t)ReadSymbol(
1208                 s->hgroup[0].htrees[s->literal_htree_index], br);
1209             s->ringbuffer[pos & s->ringbuffer_mask] = s->prev_byte1;
1210             BROTLI_LOG_UINT(s->literal_htree_index);
1211             BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
1212             if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1213               if (BrotliWrite(output, s->ringbuffer,
1214                               (size_t)s->ringbuffer_size) < 0) {
1215                 result = BROTLI_RESULT_ERROR;
1216                 break;
1217               }
1218             }
1219             ++pos;
1220             ++i;
1221           }
1222         }
1223
1224         if (result != BROTLI_RESULT_SUCCESS) break;
1225
1226         s->meta_block_remaining_len -= s->insert_length;
1227         if (s->meta_block_remaining_len <= 0) {
1228           s->state = BROTLI_STATE_METABLOCK_DONE;
1229           break;
1230         } else if (s->distance_code < 0) {
1231           s->state = BROTLI_STATE_BLOCK_DISTANCE;
1232         } else {
1233           s->state = BROTLI_STATE_BLOCK_POST;
1234           break;
1235         }
1236         /* No break, go to next state */
1237       case BROTLI_STATE_BLOCK_DISTANCE:
1238         if (!BrotliReadMoreInput(br)) {
1239           result = BROTLI_RESULT_PARTIAL;
1240           break;
1241         }
1242         assert(s->distance_code < 0);
1243
1244         if (s->block_length[2] == 0) {
1245           DecodeBlockType(s->num_block_types[2],
1246                           s->block_type_trees, 2,
1247                           s->block_type, s->block_type_rb,
1248                           s->block_type_rb_index, br);
1249           s->block_length[2] = ReadBlockLength(
1250               &s->block_len_trees[2 * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
1251           s->dist_context_offset = s->block_type[2] << kDistanceContextBits;
1252           s->dist_context_map_slice =
1253               s->dist_context_map + s->dist_context_offset;
1254         }
1255         --s->block_length[2];
1256         context = (uint8_t)(s->copy_length > 4 ? 3 : s->copy_length - 2);
1257         s->dist_htree_index = s->dist_context_map_slice[context];
1258         s->distance_code =
1259             ReadSymbol(s->hgroup[2].htrees[s->dist_htree_index], br);
1260         if (s->distance_code >= s->num_direct_distance_codes) {
1261           int nbits;
1262           int postfix;
1263           int offset;
1264           s->distance_code -= s->num_direct_distance_codes;
1265           postfix = s->distance_code & s->distance_postfix_mask;
1266           s->distance_code >>= s->distance_postfix_bits;
1267           nbits = (s->distance_code >> 1) + 1;
1268           offset = ((2 + (s->distance_code & 1)) << nbits) - 4;
1269           s->distance_code = s->num_direct_distance_codes +
1270               ((offset + (int)BrotliReadBits(br, nbits)) <<
1271                s->distance_postfix_bits) + postfix;
1272         }
1273         s->state = BROTLI_STATE_BLOCK_POST;
1274         /* No break, go to next state */
1275       case BROTLI_STATE_BLOCK_POST:
1276         if (!BrotliReadMoreInput(br)) {
1277           result = BROTLI_RESULT_PARTIAL;
1278           break;
1279         }
1280         /* Convert the distance code to the actual distance by possibly */
1281         /* looking up past distnaces from the s->ringbuffer. */
1282         s->distance =
1283             TranslateShortCodes(s->distance_code, s->dist_rb, s->dist_rb_idx);
1284         if (s->distance < 0) {
1285           result = BROTLI_RESULT_ERROR;
1286           break;
1287         }
1288         BROTLI_LOG_UINT(s->distance);
1289
1290         if (pos < s->max_backward_distance &&
1291             s->max_distance != s->max_backward_distance) {
1292           s->max_distance = pos;
1293         } else {
1294           s->max_distance = s->max_backward_distance;
1295         }
1296
1297         s->copy_dst = &s->ringbuffer[pos & s->ringbuffer_mask];
1298
1299         if (s->distance > s->max_distance) {
1300           if (s->copy_length >= kMinDictionaryWordLength &&
1301               s->copy_length <= kMaxDictionaryWordLength) {
1302             int offset = kBrotliDictionaryOffsetsByLength[s->copy_length];
1303             int word_id = s->distance - s->max_distance - 1;
1304             int shift = kBrotliDictionarySizeBitsByLength[s->copy_length];
1305             int mask = (1 << shift) - 1;
1306             int word_idx = word_id & mask;
1307             int transform_idx = word_id >> shift;
1308             offset += word_idx * s->copy_length;
1309             if (transform_idx < kNumTransforms) {
1310               const uint8_t* word = &kBrotliDictionary[offset];
1311               int len = TransformDictionaryWord(
1312                   s->copy_dst, word, s->copy_length, transform_idx);
1313               s->copy_dst += len;
1314               pos += len;
1315               s->meta_block_remaining_len -= len;
1316               if (s->copy_dst >= s->ringbuffer_end) {
1317                 if (BrotliWrite(output, s->ringbuffer,
1318                                 (size_t)s->ringbuffer_size) < 0) {
1319                   result = BROTLI_RESULT_ERROR;
1320                   break;
1321                 }
1322                 memcpy(s->ringbuffer, s->ringbuffer_end,
1323                        (size_t)(s->copy_dst - s->ringbuffer_end));
1324               }
1325             } else {
1326               printf("Invalid backward reference. pos: %d distance: %d "
1327                      "len: %d bytes left: %d\n",
1328                      pos, s->distance, s->copy_length,
1329                      s->meta_block_remaining_len);
1330               result = BROTLI_RESULT_ERROR;
1331               break;
1332             }
1333           } else {
1334             printf("Invalid backward reference. pos: %d distance: %d "
1335                    "len: %d bytes left: %d\n", pos, s->distance, s->copy_length,
1336                    s->meta_block_remaining_len);
1337             result = BROTLI_RESULT_ERROR;
1338             break;
1339           }
1340         } else {
1341           if (s->distance_code > 0) {
1342             s->dist_rb[s->dist_rb_idx & 3] = s->distance;
1343             ++s->dist_rb_idx;
1344           }
1345
1346           if (s->copy_length > s->meta_block_remaining_len) {
1347             printf("Invalid backward reference. pos: %d distance: %d "
1348                    "len: %d bytes left: %d\n", pos, s->distance, s->copy_length,
1349                    s->meta_block_remaining_len);
1350             result = BROTLI_RESULT_ERROR;
1351             break;
1352           }
1353
1354           s->copy_src =
1355               &s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1356
1357 #if (defined(__x86_64__) || defined(_M_X64))
1358           if (s->copy_src + s->copy_length <= s->ringbuffer_end &&
1359               s->copy_dst + s->copy_length < s->ringbuffer_end) {
1360             if (s->copy_length <= 16 && s->distance >= 8) {
1361               UNALIGNED_COPY64(s->copy_dst, s->copy_src);
1362               UNALIGNED_COPY64(s->copy_dst + 8, s->copy_src + 8);
1363             } else {
1364               IncrementalCopyFastPath(s->copy_dst, s->copy_src, s->copy_length);
1365             }
1366             pos += s->copy_length;
1367             s->meta_block_remaining_len -= s->copy_length;
1368             s->copy_length = 0;
1369           }
1370 #endif
1371
1372           for (i = 0; i < s->copy_length; ++i) {
1373             s->ringbuffer[pos & s->ringbuffer_mask] =
1374                 s->ringbuffer[(pos - s->distance) & s->ringbuffer_mask];
1375             if ((pos & s->ringbuffer_mask) == s->ringbuffer_mask) {
1376               if (BrotliWrite(output, s->ringbuffer,
1377                               (size_t)s->ringbuffer_size) < 0) {
1378                 result = BROTLI_RESULT_ERROR;
1379                 break;
1380               }
1381             }
1382             ++pos;
1383             --s->meta_block_remaining_len;
1384           }
1385         }
1386
1387         /* When we get here, we must have inserted at least one literal and */
1388         /* made a copy of at least length two, therefore accessing the last 2 */
1389         /* bytes is valid. */
1390         s->prev_byte1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
1391         s->prev_byte2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
1392         s->state = BROTLI_STATE_BLOCK_BEGIN;
1393         goto BlockBegin;
1394       case BROTLI_STATE_METABLOCK_DONE:
1395         if (s->context_modes != 0) {
1396           free(s->context_modes);
1397           s->context_modes = NULL;
1398         }
1399         if (s->context_map != 0) {
1400           free(s->context_map);
1401           s->context_map = NULL;
1402         }
1403         if (s->dist_context_map != 0) {
1404           free(s->dist_context_map);
1405           s->dist_context_map = NULL;
1406         }
1407         for (i = 0; i < 3; ++i) {
1408           BrotliHuffmanTreeGroupRelease(&s->hgroup[i]);
1409           s->hgroup[i].codes = NULL;
1410           s->hgroup[i].htrees = NULL;
1411         }
1412         s->state = BROTLI_STATE_METABLOCK_BEGIN;
1413         break;
1414       case BROTLI_STATE_DONE:
1415         if (s->ringbuffer != 0) {
1416           if (BrotliWrite(output, s->ringbuffer,
1417                           (size_t)(pos & s->ringbuffer_mask)) < 0) {
1418             result = BROTLI_RESULT_ERROR;
1419           }
1420         }
1421         return result;
1422       default:
1423         printf("Unknown state %d\n", s->state);
1424         result = BROTLI_RESULT_ERROR;
1425     }
1426   }
1427
1428   s->pos = pos;
1429   s->loop_counter = i;
1430   return result;
1431 }
1432
1433 #if defined(__cplusplus) || defined(c_plusplus)
1434 }    /* extern "C" */
1435 #endif