dec/decode.c

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