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