bug 366559 - patch 1, update brotli snapshot r=jfkthame
authorPatrick McManus <mcmanus@ducksong.com>
Fri, 18 Sep 2015 18:40:05 -0400
changeset 263808 c4b11255892f
parent 263807 64821648efdd
child 263809 2a30f1edd862
push id29418
push userkwierso@gmail.com
push date2015-09-22 23:42 +0000
treeherdermozilla-central@05a7ee49d40a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjfkthame
bugs366559
milestone44.0a1
bug 366559 - patch 1, update brotli snapshot r=jfkthame
modules/brotli/README.mozilla
modules/brotli/dec/Makefile
modules/brotli/dec/bit_reader.c
modules/brotli/dec/bit_reader.h
modules/brotli/dec/context.h
modules/brotli/dec/decode.c
modules/brotli/dec/decode.h
modules/brotli/dec/dictionary.h
modules/brotli/dec/huffman.c
modules/brotli/dec/huffman.h
modules/brotli/dec/port.h
modules/brotli/dec/prefix.h
modules/brotli/dec/safe_malloc.c
modules/brotli/dec/safe_malloc.h
modules/brotli/dec/state.c
modules/brotli/dec/state.h
modules/brotli/dec/streams.c
modules/brotli/dec/streams.h
modules/brotli/dec/transform.h
modules/brotli/dec/types.h
modules/brotli/moz.build
--- a/modules/brotli/README.mozilla
+++ b/modules/brotli/README.mozilla
@@ -9,9 +9,9 @@ Upstream code can be viewed at
 
 and cloned by
   git clone https://github.com/google/brotli
 
 The in-tree copy is updated by running
   sh update.sh
 from within the modules/brotli directory.
 
-Current version: [commit ca29aa22c295daac15baf5d85427ecc7808b515c].
+Current version: [commit 1dd66ef114fd244778d9dcb5da09c28b49a0df33].
--- a/modules/brotli/dec/Makefile
+++ b/modules/brotli/dec/Makefile
@@ -1,12 +1,12 @@
 #brotli/dec
 
 include ../shared.mk
 
-CPPFLAGS += -Wall
+CFLAGS += -Wall
 
-OBJS = bit_reader.o decode.o huffman.o safe_malloc.o streams.o
+OBJS = bit_reader.o decode.o huffman.o state.o streams.o
 
 all : $(OBJS)
 
 clean :
 	rm -f $(OBJS)
--- a/modules/brotli/dec/bit_reader.c
+++ b/modules/brotli/dec/bit_reader.c
@@ -6,45 +6,50 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
-
-   Bit reading helpers
 */
 
-#include <assert.h>
+/* Bit reading helpers */
+
 #include <stdlib.h>
 
 #include "./bit_reader.h"
+#include "./port.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
-int BrotliInitBitReader(BrotliBitReader* const br, BrotliInput input) {
-  size_t i;
-  assert(br != NULL);
+void BrotliInitBitReader(BrotliBitReader* const br, BrotliInput input) {
+  BROTLI_DCHECK(br != NULL);
 
-  br->buf_ptr_ = br->buf_;
   br->input_ = input;
   br->val_ = 0;
-  br->pos_ = 0;
   br->bit_pos_ = 0;
-  br->bit_end_pos_ = 0;
+  br->avail_in = 0;
   br->eos_ = 0;
-  if (!BrotliReadMoreInput(br)) {
-    return 0;
-  }
+  br->next_in = br->buf_;
+}
+
+
+void BrotliWarmupBitReader(BrotliBitReader* const br) {
+  size_t i;
+  br->val_ = 0;
   for (i = 0; i < sizeof(br->val_); ++i) {
-    br->val_ |= ((uint64_t)br->buf_[br->pos_]) << (8 * i);
-    ++br->pos_;
+#if (BROTLI_64_BITS_LITTLE_ENDIAN)
+    br->val_ |= ((uint64_t)*br->next_in) << (8 * i);
+#else
+    br->val_ |= ((uint32_t)*br->next_in) << (8 * i);
+#endif
+    ++br->next_in;
+    --br->avail_in;
   }
-  return (br->bit_end_pos_ > 0);
 }
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    /* extern "C" */
 #endif
--- a/modules/brotli/dec/bit_reader.h
+++ b/modules/brotli/dec/bit_reader.h
@@ -6,199 +6,251 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Bit reading helpers
-*/
+/* Bit reading helpers */
 
 #ifndef BROTLI_DEC_BIT_READER_H_
 #define BROTLI_DEC_BIT_READER_H_
 
 #include <string.h>
+#include "./port.h"
 #include "./streams.h"
 #include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
-#if (defined(__x86_64__) || defined(_M_X64))
-/* This should be set to 1 only on little-endian machines. */
-#define BROTLI_USE_64_BITS 1
-#else
-#define BROTLI_USE_64_BITS 0
-#endif
 #define BROTLI_MAX_NUM_BIT_READ   25
-#define BROTLI_READ_SIZE          4096
-#define BROTLI_IBUF_SIZE          (2 * BROTLI_READ_SIZE + 32)
-#define BROTLI_IBUF_MASK          (2 * BROTLI_READ_SIZE - 1)
+#define BROTLI_READ_SIZE          1024
+#define BROTLI_IMPLICIT_ZEROES    128
+#define BROTLI_IBUF_SIZE          (BROTLI_READ_SIZE + BROTLI_IMPLICIT_ZEROES)
+#define BROTLI_IBUF_MASK          (BROTLI_READ_SIZE - 1)
 
-#define UNALIGNED_COPY64(dst, src) memcpy(dst, src, 8)
-#define UNALIGNED_MOVE64(dst, src) memmove(dst, src, 8)
-
-static const uint32_t kBitMask[BROTLI_MAX_NUM_BIT_READ] = {
-  0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
-  65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215
-};
+/* Masking with this expression turns to a single "Unsigned Bit Field Extract"
+   UBFX instruction on ARM. */
+static BROTLI_INLINE uint32_t BitMask(int n) { return ~((0xffffffff) << n); }
 
 typedef struct {
-  /* Input byte buffer, consist of a ringbuffer and a "slack" region where */
-  /* bytes from the start of the ringbuffer are copied. */
-  uint8_t buf_[BROTLI_IBUF_SIZE];
-  uint8_t*    buf_ptr_;      /* next input will write here */
-  BrotliInput input_;        /* input callback */
-#if (BROTLI_USE_64_BITS)
+#if (BROTLI_64_BITS_LITTLE_ENDIAN)
   uint64_t    val_;          /* pre-fetched bits */
 #else
   uint32_t    val_;          /* pre-fetched bits */
 #endif
-  uint32_t    pos_;          /* byte position in stream */
   uint32_t    bit_pos_;      /* current bit-reading position in val_ */
-  uint32_t    bit_end_pos_;  /* bit-reading end position from LSB of val_ */
+  uint8_t*    next_in;       /* the byte we're reading from */
+  uint32_t    avail_in;
   int         eos_;          /* input stream is finished */
+  BrotliInput input_;        /* input callback */
+
+  /* Input byte buffer, consist of a ringbuffer and a "slack" region where */
+  /* bytes from the start of the ringbuffer are copied. */
+  uint8_t buf_[BROTLI_IBUF_SIZE];
 } BrotliBitReader;
 
-int BrotliInitBitReader(BrotliBitReader* const br, BrotliInput input);
-
-/* Return the prefetched bits, so they can be looked up. */
-static BROTLI_INLINE uint32_t BrotliPrefetchBits(BrotliBitReader* const br) {
-  return (uint32_t)(br->val_ >> br->bit_pos_);
-}
-
-/* For jumping over a number of bits in the bit stream when accessed with */
-/* BrotliPrefetchBits and BrotliFillBitWindow. */
-static BROTLI_INLINE void BrotliSetBitPos(BrotliBitReader* const br,
-                                          uint32_t val) {
-#ifdef BROTLI_DECODE_DEBUG
-  uint32_t n_bits = val - br->bit_pos_;
-  const uint32_t bval = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
-  printf("[BrotliReadBits]  %010d %2d  val: %6x\n",
-         (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, bval);
-#endif
-  br->bit_pos_ = val;
-}
+/* Initializes the bitreader fields. After this, BrotliReadInput then
+   BrotliWarmupBitReader must be used. */
+void BrotliInitBitReader(BrotliBitReader* const br, BrotliInput input);
 
-/*
- * Reload up to 32 bits byte-by-byte.
- * This function works on both little and big endian.
- */
-static BROTLI_INLINE void ShiftBytes32(BrotliBitReader* const br) {
-  while (br->bit_pos_ >= 8) {
-    br->val_ >>= 8;
-    br->val_ |= ((uint32_t)br->buf_[br->pos_ & BROTLI_IBUF_MASK]) << 24;
-    ++br->pos_;
-    br->bit_pos_ -= 8;
-    br->bit_end_pos_ -= 8;
-  }
-}
+/* Initializes bit reading and bit position with the first input data available.
+   Requires that there is enough input available (BrotliCheckInputAmount). */
+void BrotliWarmupBitReader(BrotliBitReader* const br);
 
-/* Fills up the input ringbuffer by calling the input callback.
+/* Pulls data from the input to the the read buffer.
 
-   Does nothing if there are at least 32 bytes present after current position.
-
-   Returns 0 if either:
+   Returns 0 if one of:
     - the input callback returned an error, or
     - there is no more input and the position is past the end of the stream.
+    - finish is false and less than BROTLI_READ_SIZE are available - a next call
+      when more data is available makes it continue including the partially read
+      data
 
-   After encountering the end of the input stream, 32 additional zero bytes are
-   copied to the ringbuffer, therefore it is safe to call this function after
-   every 32 bytes of input is read.
+   If finish is true and the end of the stream is reached,
+   BROTLI_IMPLICIT_ZEROES additional zero bytes are copied to the ringbuffer.
 */
-static BROTLI_INLINE int BrotliReadMoreInput(BrotliBitReader* const br) {
-  if (br->bit_end_pos_ > 256) {
-    return 1;
-  } else if (br->eos_) {
-    return br->bit_pos_ <= br->bit_end_pos_;
+static BROTLI_INLINE int BrotliReadInput(
+    BrotliBitReader* const br, int finish) {
+  if (PREDICT_FALSE(br->eos_)) {
+    return 0;
   } else {
-    uint8_t* dst = br->buf_ptr_;
-    int bytes_read = BrotliRead(br->input_, dst, BROTLI_READ_SIZE);
+    size_t i;
+    int bytes_read;
+    if (br->next_in != br->buf_) {
+      for (i = 0; i < br->avail_in; i++) {
+        br->buf_[i] = br->next_in[i];
+      }
+      br->next_in = br->buf_;
+    }
+    bytes_read = BrotliRead(br->input_, br->next_in + br->avail_in,
+        (size_t)(BROTLI_READ_SIZE - br->avail_in));
     if (bytes_read < 0) {
       return 0;
     }
-    if (bytes_read < BROTLI_READ_SIZE) {
+    br->avail_in += (uint32_t)bytes_read;
+    if (br->avail_in < BROTLI_READ_SIZE) {
+      if (!finish) {
+        return 0;
+      }
       br->eos_ = 1;
-      /* Store 32 bytes of zero after the stream end. */
-#if (BROTLI_USE_64_BITS)
-      *(uint64_t*)(dst + bytes_read) = 0;
-      *(uint64_t*)(dst + bytes_read + 8) = 0;
-      *(uint64_t*)(dst + bytes_read + 16) = 0;
-      *(uint64_t*)(dst + bytes_read + 24) = 0;
-#else
-      memset(dst + bytes_read, 0, 32);
-#endif
+      /* Store BROTLI_IMPLICIT_ZEROES bytes of zero after the stream end. */
+      memset(br->next_in + br->avail_in, 0, BROTLI_IMPLICIT_ZEROES);
+      br->avail_in += BROTLI_IMPLICIT_ZEROES;
     }
-    if (dst == br->buf_) {
-      /* Copy the head of the ringbuffer to the slack region. */
-#if (BROTLI_USE_64_BITS)
-      UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 32, br->buf_);
-      UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 24, br->buf_ + 8);
-      UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 16, br->buf_ + 16);
-      UNALIGNED_COPY64(br->buf_ + BROTLI_IBUF_SIZE - 8, br->buf_ + 24);
-#else
-      memcpy(br->buf_ + (BROTLI_READ_SIZE << 1), br->buf_, 32);
-#endif
-      br->buf_ptr_ = br->buf_ + BROTLI_READ_SIZE;
-    } else {
-      br->buf_ptr_ = br->buf_;
-    }
-    br->bit_end_pos_ += ((uint32_t)bytes_read << 3);
     return 1;
   }
 }
 
-/* Guarantees that there are at least 24 bits in the buffer. */
-static BROTLI_INLINE void BrotliFillBitWindow(BrotliBitReader* const br) {
-#if (BROTLI_USE_64_BITS)
-  if (br->bit_pos_ >= 40) {
-    /*
-     * Advances the Read buffer by 5 bytes to make room for reading next
-     * 24 bits.
-     * The expression below needs a little-endian arch to work correctly.
-     * This gives a large speedup for decoding speed.
-     */
-    br->val_ >>= 40;
-    br->val_ |= *(const uint64_t*)(
-        br->buf_ + (br->pos_ & BROTLI_IBUF_MASK)) << 24;
-    br->pos_ += 5;
-    br->bit_pos_ -= 40;
-    br->bit_end_pos_ -= 40;
+/* Returns amount of unread bytes the bit reader still has buffered from the
+   BrotliInput, including whole bytes in br->val_. */
+static BROTLI_INLINE size_t BrotliGetRemainingBytes(BrotliBitReader* br) {
+  return br->avail_in + sizeof(br->val_) - (br->bit_pos_ >> 3);
+}
+
+/* Checks if there is at least num bytes left in the input ringbuffer (excluding
+   the bits remaining in br->val_). The maximum value for num is
+   BROTLI_IMPLICIT_ZEROES bytes. */
+static BROTLI_INLINE int BrotliCheckInputAmount(
+    BrotliBitReader* const br, size_t num) {
+  return br->avail_in >= num;
+}
+
+/* Guarantees that there are at least n_bits in the buffer.
+   n_bits should be in the range [1..24] */
+static BROTLI_INLINE void BrotliFillBitWindow(
+    BrotliBitReader* const br, int n_bits) {
+#if (BROTLI_64_BITS_LITTLE_ENDIAN)
+  if (IS_CONSTANT(n_bits) && n_bits <= 8) {
+    if (br->bit_pos_ >= 56) {
+      br->val_ >>= 56;
+      br->bit_pos_ ^= 56;  /* here same as -= 56 because of the if condition */
+      br->val_ |= (*(const uint64_t*)(br->next_in)) << 8;
+      br->avail_in -= 7;
+      br->next_in += 7;
+    }
+  } else if (IS_CONSTANT(n_bits) && n_bits <= 16) {
+    if (br->bit_pos_ >= 48) {
+      br->val_ >>= 48;
+      br->bit_pos_ ^= 48;  /* here same as -= 48 because of the if condition */
+      br->val_ |= (*(const uint64_t*)(br->next_in)) << 16;
+      br->avail_in -= 6;
+      br->next_in += 6;
+    }
+  } else {
+    if (br->bit_pos_ >= 32) {
+      br->val_ >>= 32;
+      br->bit_pos_ ^= 32;  /* here same as -= 32 because of the if condition */
+      br->val_ |= ((uint64_t)(*(const uint32_t*)(br->next_in))) << 32;
+      br->avail_in -= 4;
+      br->next_in += 4;
+    }
+  }
+#elif (BROTLI_LITTLE_ENDIAN)
+  if (IS_CONSTANT(n_bits) && n_bits <= 8) {
+    if (br->bit_pos_ >= 24) {
+      br->val_ >>= 24;
+      br->bit_pos_ ^= 24;  /* here same as -= 24 because of the if condition */
+      br->val_ |= (*(const uint32_t*)(br->next_in)) << 8;
+      br->avail_in -= 3;
+      br->next_in += 3;
+    }
+  } else {
+    if (br->bit_pos_ >= 16) {
+      br->val_ >>= 16;
+      br->bit_pos_ ^= 16;  /* here same as -= 16 because of the if condition */
+      br->val_ |= ((uint32_t)(*(const uint16_t*)(br->next_in))) << 16;
+      br->avail_in -= 2;
+      br->next_in += 2;
+    }
+    if (!IS_CONSTANT(n_bits) || (n_bits > 16)) {
+      if (br->bit_pos_ >= 8) {
+        br->val_ >>= 8;
+        br->bit_pos_ ^= 8;  /* here same as -= 8 because of the if condition */
+        br->val_ |= ((uint32_t)*br->next_in) << 24;
+        --br->avail_in;
+        ++br->next_in;
+      }
+    }
   }
 #else
-  ShiftBytes32(br);
+  while (br->bit_pos_ >= 8) {
+    br->val_ >>= 8;
+    br->val_ |= ((uint32_t)*br->next_in) << 24;
+    br->bit_pos_ -= 8;
+    --br->avail_in;
+    ++br->next_in;
+  }
 #endif
 }
 
-/* Reads the specified number of bits from Read Buffer. */
+/* Like BrotliGetBits, but does not mask the result, it is only guaranteed
+that it has minimum n_bits. */
+static BROTLI_INLINE uint32_t BrotliGetBitsUnmasked(
+    BrotliBitReader* const br, int n_bits) {
+  BrotliFillBitWindow(br, n_bits);
+  return (uint32_t)(br->val_ >> br->bit_pos_);
+}
+
+/* Returns the specified number of bits from br without advancing bit pos. */
+static BROTLI_INLINE uint32_t BrotliGetBits(
+    BrotliBitReader* const br, int n_bits) {
+  BrotliFillBitWindow(br, n_bits);
+  return (uint32_t)(br->val_ >> br->bit_pos_) & BitMask(n_bits);
+}
+
+/* Advances the bit pos by n_bits. */
+static BROTLI_INLINE void BrotliDropBits(
+    BrotliBitReader* const br, int n_bits) {
+  br->bit_pos_ += (uint32_t)n_bits;
+}
+
+/* Reads the specified number of bits from br and advances the bit pos. */
 static BROTLI_INLINE uint32_t BrotliReadBits(
     BrotliBitReader* const br, int n_bits) {
   uint32_t val;
-#if (BROTLI_USE_64_BITS)
-  BrotliFillBitWindow(br);
-  val = (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
-#else
-  /*
-   * The if statement gives 2-4% speed boost on Canterbury data set with
-   * asm.js/firefox/x86-64.
-   */
-  if ((32 - br->bit_pos_) < ((uint32_t) n_bits)) {
-    BrotliFillBitWindow(br);
-  }
-  val = (br->val_ >> br->bit_pos_) & kBitMask[n_bits];
-#endif
+  BrotliFillBitWindow(br, n_bits);
+  val = (uint32_t)(br->val_ >> br->bit_pos_) & BitMask(n_bits);
 #ifdef BROTLI_DECODE_DEBUG
-  printf("[BrotliReadBits]  %010d %2d  val: %6x\n",
-         (br->pos_ << 3) + br->bit_pos_ - 64, n_bits, val);
+  printf("[BrotliReadBits]  %d %d %d val: %6x\n",
+         (int)br->avail_in, (int)br->bit_pos_, n_bits, val);
 #endif
   br->bit_pos_ += (uint32_t)n_bits;
   return val;
 }
 
+/* Advances the bit reader position to the next byte boundary and verifies
+   that any skipped bits are set to zero. */
+static BROTLI_INLINE int BrotliJumpToByteBoundary(BrotliBitReader* br) {
+  uint32_t new_bit_pos = (br->bit_pos_ + 7) & (uint32_t)(~7UL);
+  uint32_t pad_bits = BrotliReadBits(br, (int)(new_bit_pos - br->bit_pos_));
+  return pad_bits == 0;
+}
+
+/* Copies remaining input bytes stored in the bit reader to the output. Value
+   num may not be larger than BrotliGetRemainingBytes. The bit reader must be
+   warmed up again after this. */
+static BROTLI_INLINE void BrotliCopyBytes(uint8_t* dest,
+                                          BrotliBitReader* br, size_t num) {
+  while (br->bit_pos_ + 8 <= (BROTLI_64_BITS_LITTLE_ENDIAN ? 64 : 32)
+      && num > 0) {
+    *dest = (uint8_t)(br->val_ >> br->bit_pos_);
+    br->bit_pos_ += 8;
+    ++dest;
+    --num;
+  }
+  memcpy(dest, br->next_in, num);
+  br->avail_in -= (uint32_t)num;
+  br->next_in += num;
+  br->bit_pos_ = 0;
+}
+
 #if defined(__cplusplus) || defined(c_plusplus)
 }    /* extern "C" */
 #endif
 
 #endif  /* BROTLI_DEC_BIT_READER_H_ */
--- a/modules/brotli/dec/context.h
+++ b/modules/brotli/dec/context.h
@@ -6,18 +6,19 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Lookup table to map the previous two bytes to a context id.
+/* Lookup table to map the previous two bytes to a context id.
 
    There are four different context modeling modes defined here:
      CONTEXT_LSB6: context id is the least significant 6 bits of the last byte,
      CONTEXT_MSB6: context id is the most significant 6 bits of the last byte,
      CONTEXT_UTF8: second-order context model tuned for UTF8-encoded text,
      CONTEXT_SIGNED: second-order context model tuned for signed integers.
 
    The context id for the UTF8 context model is calculated as follows. If p1
--- a/modules/brotli/dec/decode.c
+++ b/modules/brotli/dec/decode.c
@@ -15,634 +15,729 @@
 
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
 #include "./bit_reader.h"
 #include "./context.h"
 #include "./decode.h"
 #include "./dictionary.h"
+#include "./port.h"
 #include "./transform.h"
 #include "./huffman.h"
 #include "./prefix.h"
-#include "./safe_malloc.h"
+
+#ifdef __ARM_NEON__
+#include <arm_neon.h>
+#endif
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
 #ifdef BROTLI_DECODE_DEBUG
 #define BROTLI_LOG_UINT(name)                                    \
   printf("[%s] %s = %lu\n", __func__, #name, (unsigned long)(name))
 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx)                  \
   printf("[%s] %s[%lu] = %lu\n", __func__, #array_name, \
          (unsigned long)(idx), (unsigned long)array_name[idx])
+#define BROTLI_LOG(x) printf x
 #else
 #define BROTLI_LOG_UINT(name)
 #define BROTLI_LOG_ARRAY_INDEX(array_name, idx)
+#define BROTLI_LOG(x)
 #endif
 
 static const uint8_t kDefaultCodeLength = 8;
 static const uint8_t kCodeLengthRepeatCode = 16;
 static const int kNumLiteralCodes = 256;
 static const int kNumInsertAndCopyCodes = 704;
 static const int kNumBlockLengthCodes = 26;
 static const int kLiteralContextBits = 6;
 static const int kDistanceContextBits = 2;
 
 #define HUFFMAN_TABLE_BITS      8
 #define HUFFMAN_TABLE_MASK      0xff
-/* Maximum possible Huffman table size for an alphabet size of 704, max code
- * length 15 and root table bits 8. */
-#define HUFFMAN_MAX_TABLE_SIZE  1080
 
 #define CODE_LENGTH_CODES 18
 static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = {
   1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15,
 };
 
 #define NUM_DISTANCE_SHORT_CODES 16
-static const int kDistanceShortCodeIndexOffset[NUM_DISTANCE_SHORT_CODES] = {
-  3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2
-};
+
 
-static const int kDistanceShortCodeValueOffset[NUM_DISTANCE_SHORT_CODES] = {
-  0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
-};
-
-static BROTLI_INLINE int DecodeWindowBits(BrotliBitReader* br) {
-  if (BrotliReadBits(br, 1)) {
-    return 17 + (int)BrotliReadBits(br, 3);
-  } else {
+static uint32_t DecodeWindowBits(BrotliBitReader* br) {
+  uint32_t n;
+  if (BrotliReadBits(br, 1) == 0) {
     return 16;
   }
+  n = BrotliReadBits(br, 3);
+  if (n != 0) {
+    return 17 + n;
+  }
+  n = BrotliReadBits(br, 3);
+  if (n != 0) {
+    return 8 + n;
+  }
+  return 17;
+}
+
+static BROTLI_INLINE BROTLI_NO_ASAN void memmove16(
+    uint8_t* dst, uint8_t* src) {
+#ifdef __ARM_NEON__
+  vst1q_u8(dst, vld1q_u8(src));
+#else
+  /* memcpy is unsafe for overlapping regions and ASAN detects this.
+     But, because of optimizations, it works exactly as memmove:
+     copies data to registers first, and then stores them to dst. */
+  memcpy(dst, src, 16);
+#endif
 }
 
 /* Decodes a number in the range [0..255], by reading 1 - 11 bits. */
 static BROTLI_INLINE int DecodeVarLenUint8(BrotliBitReader* br) {
   if (BrotliReadBits(br, 1)) {
     int nbits = (int)BrotliReadBits(br, 3);
     if (nbits == 0) {
       return 1;
     } else {
       return (int)BrotliReadBits(br, nbits) + (1 << nbits);
     }
   }
   return 0;
 }
 
-static void DecodeMetaBlockLength(BrotliBitReader* br,
-                                  int* meta_block_length,
-                                  int* input_end,
-                                  int* is_uncompressed) {
+static BrotliResult DecodeMetaBlockLength(BrotliBitReader* br,
+                                          int* meta_block_length,
+                                          int* input_end,
+                                          int* is_metadata,
+                                          int* is_uncompressed) {
   int size_nibbles;
+  int size_bytes;
   int i;
   *input_end = (int)BrotliReadBits(br, 1);
   *meta_block_length = 0;
   *is_uncompressed = 0;
+  *is_metadata = 0;
   if (*input_end && BrotliReadBits(br, 1)) {
-    return;
+    return BROTLI_RESULT_SUCCESS;
   }
   size_nibbles = (int)BrotliReadBits(br, 2) + 4;
-  for (i = 0; i < size_nibbles; ++i) {
-    *meta_block_length |= (int)BrotliReadBits(br, 4) << (i * 4);
+  if (size_nibbles == 7) {
+    *is_metadata = 1;
+    /* Verify reserved bit. */
+    if (BrotliReadBits(br, 1) != 0) {
+      return BROTLI_FAILURE();
+    }
+    size_bytes = (int)BrotliReadBits(br, 2);
+    if (size_bytes == 0) {
+      return BROTLI_RESULT_SUCCESS;
+    }
+    for (i = 0; i < size_bytes; ++i) {
+      int next_byte = (int)BrotliReadBits(br, 8);
+      if (i + 1 == size_bytes && size_bytes > 1 && next_byte == 0) {
+        return BROTLI_FAILURE();
+      }
+      *meta_block_length |= next_byte << (i * 8);
+    }
+  } else {
+    for (i = 0; i < size_nibbles; ++i) {
+      int next_nibble = (int)BrotliReadBits(br, 4);
+      if (i + 1 == size_nibbles && size_nibbles > 4 && next_nibble == 0) {
+        return BROTLI_FAILURE();
+      }
+      *meta_block_length |= next_nibble << (i * 4);
+    }
   }
   ++(*meta_block_length);
-  if (!*input_end) {
+  if (!*input_end && !*is_metadata) {
     *is_uncompressed = (int)BrotliReadBits(br, 1);
   }
+  return BROTLI_RESULT_SUCCESS;
 }
 
 /* Decodes the next Huffman code from bit-stream. */
 static BROTLI_INLINE int ReadSymbol(const HuffmanCode* table,
                                     BrotliBitReader* br) {
-  int nbits;
-  BrotliFillBitWindow(br);
-  table += (int)(br->val_ >> br->bit_pos_) & HUFFMAN_TABLE_MASK;
-  nbits = table->bits - HUFFMAN_TABLE_BITS;
-  if (nbits > 0) {
-    br->bit_pos_ += HUFFMAN_TABLE_BITS;
+  /* Read the bits for two reads at once. */
+  uint32_t val = BrotliGetBitsUnmasked(br, 15);
+  table += val & HUFFMAN_TABLE_MASK;
+  if (table->bits > HUFFMAN_TABLE_BITS) {
+    int nbits = table->bits - HUFFMAN_TABLE_BITS;
+    BrotliDropBits(br, HUFFMAN_TABLE_BITS);
     table += table->value;
-    table += (int)(br->val_ >> br->bit_pos_) & ((1 << nbits) - 1);
+    table += (int)(val >> HUFFMAN_TABLE_BITS) & (int)BitMask(nbits);
   }
-  br->bit_pos_ += table->bits;
+  BrotliDropBits(br, table->bits);
   return table->value;
 }
 
-static void PrintUcharVector(const uint8_t* v, int len) {
-  while (len-- > 0) printf(" %d", *v++);
-  printf("\n");
+static BROTLI_INLINE void PreloadSymbol(const HuffmanCode* table,
+                                        BrotliBitReader* br,
+                                        unsigned* bits,
+                                        unsigned* value) {
+  table += BrotliGetBits(br, HUFFMAN_TABLE_BITS);
+  *bits = table->bits;
+  *value = table->value;
+}
+
+static BROTLI_INLINE unsigned ReadPreloadedSymbol(const HuffmanCode* table,
+                                                  BrotliBitReader* br,
+                                                  unsigned* bits,
+                                                  unsigned* value) {
+  unsigned result = *value;
+  if (PREDICT_FALSE(*bits > HUFFMAN_TABLE_BITS)) {
+    uint32_t val = BrotliGetBitsUnmasked(br, 15);
+    const HuffmanCode* ext = table + (val & HUFFMAN_TABLE_MASK) + *value;
+    int mask = (int)BitMask((int)(*bits - HUFFMAN_TABLE_BITS));
+    BrotliDropBits(br, HUFFMAN_TABLE_BITS);
+    ext += (int)(val >> HUFFMAN_TABLE_BITS) & mask;
+    BrotliDropBits(br, ext->bits);
+    result = ext->value;
+  } else {
+    BrotliDropBits(br, (int)*bits);
+  }
+  PreloadSymbol(table, br, bits, value);
+  return result;
 }
 
-static int ReadHuffmanCodeLengths(
-    const uint8_t* code_length_code_lengths,
-    int num_symbols, uint8_t* code_lengths,
-    BrotliBitReader* br) {
-  int symbol = 0;
-  uint8_t prev_code_len = kDefaultCodeLength;
-  int repeat = 0;
-  uint8_t repeat_code_len = 0;
-  int space = 32768;
-  HuffmanCode table[32];
+static BrotliResult ReadHuffmanCode(int alphabet_size,
+                                    HuffmanCode* table,
+                                    int* opt_table_size,
+                                    BrotliState* s) {
+  BrotliBitReader* br = &s->br;
+  /* simple_code_or_skip is used as follows:
+     1 for simple code;
+     0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
+  int simple_code_or_skip;
+  unsigned symbol = s->symbol;
+  uint32_t repeat = s->repeat;
+  uint8_t prev_code_len = s->prev_code_len;
+  uint8_t repeat_code_len = s->repeat_code_len;
+  uint32_t space = s->space;
+  uint16_t* symbol_lists = s->symbol_lists;
+  int* next_symbol = s->next_symbol;
+  int i = 0;
+  /* Unnecessary masking, but might be good for safety. */
+  alphabet_size &= 0x3ff;
+  /* State machine */
+  if (s->sub1_state == BROTLI_STATE_SUB1_NONE) {
+    if (!BrotliCheckInputAmount(br, 32)) {
+      return BROTLI_RESULT_NEEDS_MORE_INPUT;
+    }
+    simple_code_or_skip = (int)BrotliReadBits(br, 2);
+    BROTLI_LOG_UINT(simple_code_or_skip);
+    if (simple_code_or_skip == 1) {
+      /* Read symbols, codes & code lengths directly. */
+      int table_size;
+      int max_bits_counter = alphabet_size - 1;
+      int max_bits = 0;
+      uint16_t symbols[4] = { 0 };
+      uint32_t num_symbols = BrotliReadBits(br, 2);
+      i = 0;
+      while (max_bits_counter) {
+        max_bits_counter >>= 1;
+        ++max_bits;
+      }
+      do {
+        int k;
+        uint32_t v = BrotliReadBits(br, max_bits);
+        if (v >= alphabet_size) {
+          return BROTLI_FAILURE();
+        }
+        symbols[i] = (uint16_t)v;
+        for (k = 0; k < i; k++) {
+          if (symbols[k] == (uint16_t)v) {
+            return BROTLI_FAILURE();
+          }
+        }
+      } while (++i <= num_symbols);
+      if (num_symbols == 3) {
+        num_symbols += BrotliReadBits(br, 1);
+      }
+      BROTLI_LOG_UINT(num_symbols);
+      table_size = BrotliBuildSimpleHuffmanTable(
+          table, HUFFMAN_TABLE_BITS, symbols, num_symbols);
+      if (opt_table_size) {
+        *opt_table_size = table_size;
+      }
+      s->sub1_state = BROTLI_STATE_SUB1_NONE;
+      return BROTLI_RESULT_SUCCESS;
+    } else {  /* Decode Huffman-coded code lengths. */
+      int i;
+      int8_t num_codes = 0;
+      /* Static Huffman code for the code length code lengths. */
+      static const uint8_t huff_len[16] = {
+        2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 4,
+      };
+      static const uint8_t huff_val[16] = {
+        0, 4, 3, 2, 0, 4, 3, 1, 0, 4, 3, 2, 0, 4, 3, 5,
+      };
+      space = 32;
+      memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo));
+      memset(&s->code_length_code_lengths[0], 0,
+             sizeof(s->code_length_code_lengths));
+      for (i = simple_code_or_skip;
+           i < CODE_LENGTH_CODES; ++i) {
+        const uint8_t code_len_idx = kCodeLengthCodeOrder[i];
+        uint8_t ix = (uint8_t)BrotliGetBits(br, 4);
+        uint8_t v = huff_val[ix];
+        BrotliDropBits(br, huff_len[ix]);
+        s->code_length_code_lengths[code_len_idx] = v;
+        BROTLI_LOG_ARRAY_INDEX(s->code_length_code_lengths, code_len_idx);
+        if (v != 0) {
+          space = space - (32U >> v);
+          ++num_codes;
+          ++s->code_length_histo[v];
+          if (space - 1U >= 32U) {
+            /* space is 0 or wrapped around */
+            break;
+          }
+        }
+      }
+      if (!(num_codes == 1 || space == 0)) {
+        return BROTLI_FAILURE();
+      }
+    }
+    BrotliBuildCodeLengthsHuffmanTable(s->table,
+                                       s->code_length_code_lengths,
+                                       s->code_length_histo);
+    memset(&s->code_length_histo[0], 0, sizeof(s->code_length_histo));
+    for (i = 0; i <= BROTLI_HUFFMAN_MAX_CODE_LENGTH; ++i) {
+      next_symbol[i] = i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
+      symbol_lists[i - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1)] = 0xFFFF;
+    }
 
-  if (!BrotliBuildHuffmanTable(table, 5,
-                               code_length_code_lengths,
-                               CODE_LENGTH_CODES)) {
-    printf("[ReadHuffmanCodeLengths] Building code length tree failed: ");
-    PrintUcharVector(code_length_code_lengths, CODE_LENGTH_CODES);
-    return 0;
+    symbol = 0;
+    prev_code_len = kDefaultCodeLength;
+    repeat = 0;
+    repeat_code_len = 0;
+    space = 32768;
+    s->sub1_state = BROTLI_STATE_SUB1_HUFFMAN_LENGTH_SYMBOLS;
   }
 
-  while (symbol < num_symbols && space > 0) {
-    const HuffmanCode* p = table;
-    uint8_t code_len;
-    if (!BrotliReadMoreInput(br)) {
-      printf("[ReadHuffmanCodeLengths] Unexpected end of input.\n");
-      return 0;
+  while (symbol < alphabet_size && space > 0) {
+    uint32_t milestone;
+    if (!BrotliCheckInputAmount(br, 128)) {
+      s->symbol = (uint32_t)symbol;
+      s->repeat = repeat;
+      s->prev_code_len = prev_code_len;
+      s->repeat_code_len = repeat_code_len;
+      s->space = space;
+      return BROTLI_RESULT_NEEDS_MORE_INPUT;
+    }
+    /* We use at most 5 bits per symbol. 128 * 8 / 5 = 204.8 */
+    milestone = symbol + 204;
+    if (milestone > alphabet_size) {
+      milestone = (uint32_t)alphabet_size;
     }
-    BrotliFillBitWindow(br);
-    p += (br->val_ >> br->bit_pos_) & 31;
-    br->bit_pos_ += p->bits;
-    code_len = (uint8_t)p->value;
-    if (code_len < kCodeLengthRepeatCode) {
-      repeat = 0;
-      code_lengths[symbol++] = code_len;
-      if (code_len != 0) {
-        prev_code_len = code_len;
-        space -= 32768 >> code_len;
-      }
-    } else {
-      const int extra_bits = code_len - 14;
-      int old_repeat;
-      int repeat_delta;
-      uint8_t new_len = 0;
-      if (code_len == kCodeLengthRepeatCode) {
-        new_len =  prev_code_len;
-      }
-      if (repeat_code_len != new_len) {
+    while (symbol < milestone && space > 0) {
+      const HuffmanCode* p = s->table;
+      uint8_t code_len;
+      p += BrotliGetBits(br, BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
+      BrotliDropBits(br, p->bits);
+      code_len = (uint8_t)p->value;
+      if (code_len < kCodeLengthRepeatCode) {
         repeat = 0;
-        repeat_code_len = new_len;
-      }
-      old_repeat = repeat;
-      if (repeat > 0) {
-        repeat -= 2;
-        repeat <<= extra_bits;
-      }
-      repeat += (int)BrotliReadBits(br, extra_bits) + 3;
-      repeat_delta = repeat - old_repeat;
-      if (symbol + repeat_delta > num_symbols) {
-        return 0;
-      }
-      memset(&code_lengths[symbol], repeat_code_len, (size_t)repeat_delta);
-      symbol += repeat_delta;
-      if (repeat_code_len != 0) {
-        space -= repeat_delta << (15 - repeat_code_len);
+        if (code_len != 0) {
+          symbol_lists[next_symbol[code_len]] = (uint16_t)symbol;
+          next_symbol[code_len] = (int)symbol;
+          prev_code_len = code_len;
+          space -= 32768U >> code_len;
+          s->code_length_histo[code_len]++;
+        }
+        symbol++;
+      } else {
+        const int extra_bits = code_len - 14;
+        uint32_t old_repeat;
+        uint32_t repeat_delta;
+        uint8_t new_len = 0;
+        if (code_len == kCodeLengthRepeatCode) {
+          new_len = prev_code_len;
+        }
+        if (repeat_code_len != new_len) {
+          repeat = 0;
+          repeat_code_len = new_len;
+        }
+        old_repeat = repeat;
+        if (repeat > 0) {
+          repeat -= 2;
+          repeat <<= extra_bits;
+        }
+        repeat += BrotliReadBits(br, extra_bits) + 3;
+        repeat_delta = repeat - old_repeat;
+        if (symbol + repeat_delta > alphabet_size) {
+          return BROTLI_FAILURE();
+        }
+        if (repeat_code_len != 0) {
+          unsigned last = symbol + repeat_delta;
+          i = next_symbol[repeat_code_len];
+          do {
+            symbol_lists[i] = (uint16_t)symbol;
+            i = (int)symbol;
+          } while (++symbol != last);
+          next_symbol[repeat_code_len] = i;
+          space -= repeat_delta << (15 - repeat_code_len);
+          s->code_length_histo[repeat_code_len] = (uint16_t)
+              (s->code_length_histo[repeat_code_len] + repeat_delta);
+        } else {
+          symbol += repeat_delta;
+        }
       }
     }
   }
   if (space != 0) {
-    printf("[ReadHuffmanCodeLengths] space = %d\n", space);
-    return 0;
-  }
-  memset(&code_lengths[symbol], 0, (size_t)(num_symbols - symbol));
-  return 1;
-}
-
-static int ReadHuffmanCode(int alphabet_size,
-                           HuffmanCode* table,
-                           BrotliBitReader* br) {
-  int ok = 1;
-  int table_size = 0;
-  int simple_code_or_skip;
-  uint8_t* code_lengths = NULL;
-
-  code_lengths =
-      (uint8_t*)BrotliSafeMalloc((uint64_t)alphabet_size,
-                                 sizeof(*code_lengths));
-  if (code_lengths == NULL) {
-    return 0;
-  }
-  if (!BrotliReadMoreInput(br)) {
-    printf("[ReadHuffmanCode] Unexpected end of input.\n");
-    return 0;
+    BROTLI_LOG(("[ReadHuffmanCode] space = %d\n", space));
+    return BROTLI_FAILURE();
   }
-  /* simple_code_or_skip is used as follows:
-     1 for simple code;
-     0 for no skipping, 2 skips 2 code lengths, 3 skips 3 code lengths */
-  simple_code_or_skip = (int)BrotliReadBits(br, 2);
-  BROTLI_LOG_UINT(simple_code_or_skip);
-  if (simple_code_or_skip == 1) {
-    /* Read symbols, codes & code lengths directly. */
-    int i;
-    int max_bits_counter = alphabet_size - 1;
-    int max_bits = 0;
-    int symbols[4] = { 0 };
-    const int num_symbols = (int)BrotliReadBits(br, 2) + 1;
-    while (max_bits_counter) {
-      max_bits_counter >>= 1;
-      ++max_bits;
-    }
-    memset(code_lengths, 0, (size_t)alphabet_size);
-    for (i = 0; i < num_symbols; ++i) {
-      symbols[i] = (int)BrotliReadBits(br, max_bits) % alphabet_size;
-      code_lengths[symbols[i]] = 2;
-    }
-    code_lengths[symbols[0]] = 1;
-    switch (num_symbols) {
-      case 1:
-        break;
-      case 3:
-        ok = ((symbols[0] != symbols[1]) &&
-              (symbols[0] != symbols[2]) &&
-              (symbols[1] != symbols[2]));
-        break;
-      case 2:
-        ok = (symbols[0] != symbols[1]);
-        code_lengths[symbols[1]] = 1;
-        break;
-      case 4:
-        ok = ((symbols[0] != symbols[1]) &&
-              (symbols[0] != symbols[2]) &&
-              (symbols[0] != symbols[3]) &&
-              (symbols[1] != symbols[2]) &&
-              (symbols[1] != symbols[3]) &&
-              (symbols[2] != symbols[3]));
-        if (BrotliReadBits(br, 1)) {
-          code_lengths[symbols[2]] = 3;
-          code_lengths[symbols[3]] = 3;
-        } else {
-          code_lengths[symbols[0]] = 2;
-        }
-        break;
-    }
-    BROTLI_LOG_UINT(num_symbols);
-  } else {  /* Decode Huffman-coded code lengths. */
-    int i;
-    uint8_t code_length_code_lengths[CODE_LENGTH_CODES] = { 0 };
-    int space = 32;
-    int num_codes = 0;
-    /* Static Huffman code for the code length code lengths */
-    static const HuffmanCode huff[16] = {
-      {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 1},
-      {2, 0}, {2, 4}, {2, 3}, {3, 2}, {2, 0}, {2, 4}, {2, 3}, {4, 5},
-    };
-    for (i = simple_code_or_skip; i < CODE_LENGTH_CODES && space > 0; ++i) {
-      const int code_len_idx = kCodeLengthCodeOrder[i];
-      const HuffmanCode* p = huff;
-      uint8_t v;
-      BrotliFillBitWindow(br);
-      p += (br->val_ >> br->bit_pos_) & 15;
-      br->bit_pos_ += p->bits;
-      v = (uint8_t)p->value;
-      code_length_code_lengths[code_len_idx] = v;
-      BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx);
-      if (v != 0) {
-        space -= (32 >> v);
-        ++num_codes;
-      }
-    }
-    ok = (num_codes == 1 || space == 0) &&
-        ReadHuffmanCodeLengths(code_length_code_lengths,
-                               alphabet_size, code_lengths, br);
-  }
-  if (ok) {
-    table_size = BrotliBuildHuffmanTable(table, HUFFMAN_TABLE_BITS,
-                                         code_lengths, alphabet_size);
-    if (table_size == 0) {
-      printf("[ReadHuffmanCode] BuildHuffmanTable failed: ");
-      PrintUcharVector(code_lengths, alphabet_size);
+  {
+    int table_size = BrotliBuildHuffmanTable(
+        table, HUFFMAN_TABLE_BITS, symbol_lists,
+        s->code_length_histo);
+    if (opt_table_size) {
+      *opt_table_size = table_size;
     }
   }
-  free(code_lengths);
-  return table_size;
+  s->sub1_state = BROTLI_STATE_SUB1_NONE;
+  return BROTLI_RESULT_SUCCESS;
 }
 
 static BROTLI_INLINE int ReadBlockLength(const HuffmanCode* table,
                                          BrotliBitReader* br) {
   int code;
   int nbits;
   code = ReadSymbol(table, br);
   nbits = kBlockLengthPrefixCode[code].nbits;
   return kBlockLengthPrefixCode[code].offset + (int)BrotliReadBits(br, nbits);
 }
 
-static int TranslateShortCodes(int code, int* ringbuffer, int index) {
-  int val;
-  if (code < NUM_DISTANCE_SHORT_CODES) {
-    index += kDistanceShortCodeIndexOffset[code];
-    index &= 3;
-    val = ringbuffer[index] + kDistanceShortCodeValueOffset[code];
-  } else {
-    val = code - NUM_DISTANCE_SHORT_CODES + 1;
-  }
-  return val;
-}
+/* Transform:
+    1) initialize list L with values 0, 1,... 255
+    2) For each input element X:
+    2.1) let Y = L[X]
+    2.2) remove X-th element from L
+    2.3) prepend Y to L
+    2.4) append Y to output
+
+   In most cases max(Y) <= 7, so most of L remains intact.
+   To reduce the cost of initialization, we reuse L, remember the upper bound
+   of Y values, and reinitialize only first elements in L.
 
-static void MoveToFront(uint8_t* v, uint8_t index) {
-  uint8_t value = v[index];
-  uint8_t i = index;
-  for (; i; --i) v[i] = v[i - 1];
-  v[0] = value;
-}
+   Most of input values are 0 and 1. To reduce number of brances, we replace
+   inner for loop with do-while.
+ */
+static BROTLI_NOINLINE void InverseMoveToFrontTransform(uint8_t* v, int v_len,
+    BrotliState* state) {
+  /* Reinitialize elements that could have been changed. */
+  int i = 4;
+  int upper_bound = state->mtf_upper_bound;
+  uint8_t* mtf = state->mtf;
+  /* Load endian-aware constant. */
+  const uint8_t b0123[4] = {0, 1, 2, 3};
+  uint32_t pattern;
+  memcpy(&pattern, &b0123, 4);
 
-static void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
-  uint8_t mtf[256];
-  int i;
-  for (i = 0; i < 256; ++i) {
-    mtf[i] = (uint8_t)i;
+  /* Initialize list using 4 consequent values pattern. */
+  *(uint32_t*)mtf = pattern;
+  do {
+    pattern += 0x04040404; /* Advance all 4 values by 4. */
+    *(uint32_t*)(mtf + i) = pattern;
+    i += 4;
+  } while (i <= upper_bound);
+
+  /* Transform the input. */
+  upper_bound = 0;
+  for (i = 0; i < v_len; ++i) {
+    int index = v[i];
+    uint8_t value = mtf[index];
+    v[i] = value;
+    upper_bound |= index;
+    do {
+      index--;
+      mtf[index + 1] = mtf[index];
+    } while (index > 0);
+    mtf[0] = value;
   }
-  for (i = 0; i < v_len; ++i) {
-    uint8_t index = v[i];
-    v[i] = mtf[index];
-    if (index) MoveToFront(mtf, index);
-  }
+  /* Remember amount of elements to be reinitialized. */
+  state->mtf_upper_bound = upper_bound;
 }
 
-/* Contains a collection of huffman trees with the same alphabet size. */
-typedef struct {
-  int alphabet_size;
-  int num_htrees;
-  HuffmanCode* codes;
-  HuffmanCode** htrees;
-} HuffmanTreeGroup;
-
-static void HuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size,
-                                 int ntrees) {
-  group->alphabet_size = alphabet_size;
-  group->num_htrees = ntrees;
-  group->codes = (HuffmanCode*)malloc(
-      sizeof(HuffmanCode) * (size_t)(ntrees * HUFFMAN_MAX_TABLE_SIZE));
-  group->htrees = (HuffmanCode**)malloc(sizeof(HuffmanCode*) * (size_t)ntrees);
+/* Expose function for testing. Will be removed by linker as unused. */
+void InverseMoveToFrontTransformForTesting(uint8_t* v, int l, BrotliState* s) {
+  InverseMoveToFrontTransform(v, l, s);
 }
 
-static void HuffmanTreeGroupRelease(HuffmanTreeGroup* group) {
-  if (group->codes) {
-    free(group->codes);
-  }
-  if (group->htrees) {
-    free(group->htrees);
+
+static BrotliResult HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
+                                           BrotliState* s) {
+  if (s->sub0_state != BROTLI_STATE_SUB0_TREE_GROUP) {
+    s->next = group->codes;
+    s->htree_index = 0;
+    s->sub0_state = BROTLI_STATE_SUB0_TREE_GROUP;
   }
-}
-
-static int HuffmanTreeGroupDecode(HuffmanTreeGroup* group,
-                                  BrotliBitReader* br) {
-  int i;
-  int table_size;
-  HuffmanCode* next = group->codes;
-  for (i = 0; i < group->num_htrees; ++i) {
-    group->htrees[i] = next;
-    table_size = ReadHuffmanCode(group->alphabet_size, next, br);
-    next += table_size;
+  while (s->htree_index < group->num_htrees) {
+    int table_size;
+    BrotliResult result =
+        ReadHuffmanCode(group->alphabet_size, s->next, &table_size, s);
+    if (result != BROTLI_RESULT_SUCCESS) return result;
+    group->htrees[s->htree_index] = s->next;
+    s->next += table_size;
     if (table_size == 0) {
-      return 0;
+      return BROTLI_FAILURE();
     }
+    ++s->htree_index;
   }
-  return 1;
+  s->sub0_state = BROTLI_STATE_SUB0_NONE;
+  return BROTLI_RESULT_SUCCESS;
 }
 
-static int DecodeContextMap(int context_map_size,
-                            int* num_htrees,
-                            uint8_t** context_map,
-                            BrotliBitReader* br) {
-  int ok = 1;
+static BrotliResult DecodeContextMap(int context_map_size,
+                                     int* num_htrees,
+                                     uint8_t** context_map_arg,
+                                     BrotliState* s) {
+  BrotliBitReader* br = &s->br;
+  BrotliResult result = BROTLI_RESULT_SUCCESS;
   int use_rle_for_zeros;
-  int max_run_length_prefix = 0;
-  HuffmanCode* table;
-  int i;
-  if (!BrotliReadMoreInput(br)) {
-    printf("[DecodeContextMap] Unexpected end of input.\n");
-    return 0;
-  }
-  *num_htrees = DecodeVarLenUint8(br) + 1;
 
-  BROTLI_LOG_UINT(context_map_size);
-  BROTLI_LOG_UINT(*num_htrees);
-
-  *context_map = (uint8_t*)malloc((size_t)context_map_size);
-  if (*context_map == 0) {
-    return 0;
-  }
-  if (*num_htrees <= 1) {
-    memset(*context_map, 0, (size_t)context_map_size);
-    return 1;
+  switch((int)s->sub0_state) {
+    case BROTLI_STATE_SUB0_NONE:
+      if (!BrotliCheckInputAmount(br, 32)) {
+        return BROTLI_RESULT_NEEDS_MORE_INPUT;
+      }
+      *num_htrees = DecodeVarLenUint8(br) + 1;
+      s->context_index = 0;
+      BROTLI_LOG_UINT(context_map_size);
+      BROTLI_LOG_UINT(*num_htrees);
+      *context_map_arg = (uint8_t*)malloc((size_t)context_map_size);
+      if (*context_map_arg == 0) {
+        return BROTLI_FAILURE();
+      }
+      if (*num_htrees <= 1) {
+        memset(*context_map_arg, 0, (size_t)context_map_size);
+        return BROTLI_RESULT_SUCCESS;
+      }
+      use_rle_for_zeros = (int)BrotliReadBits(br, 1);
+      if (use_rle_for_zeros) {
+        s->max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1;
+      } else {
+        s->max_run_length_prefix = 0;
+      }
+      s->sub0_state = BROTLI_STATE_SUB0_CONTEXT_MAP_HUFFMAN;
+      /* No break, continue to next state. */
+    case BROTLI_STATE_SUB0_CONTEXT_MAP_HUFFMAN:
+      result = ReadHuffmanCode(*num_htrees + s->max_run_length_prefix,
+                               s->context_map_table, NULL, s);
+      if (result != BROTLI_RESULT_SUCCESS) return result;
+      s->sub0_state = BROTLI_STATE_SUB0_CONTEXT_MAPS;
+      /* No break, continue to next state. */
+    case BROTLI_STATE_SUB0_CONTEXT_MAPS: {
+      int context_index = s->context_index;
+      int max_run_length_prefix = s->max_run_length_prefix;
+      uint8_t* context_map = *context_map_arg;
+      int code;
+      while (context_index < context_map_size) {
+        if (!BrotliCheckInputAmount(br, 32)) {
+          s->context_index = context_index;
+          return BROTLI_RESULT_NEEDS_MORE_INPUT;
+        }
+        code = ReadSymbol(s->context_map_table, br);
+        if (code == 0) {
+          context_map[context_index++] = 0;
+        } else if (code - max_run_length_prefix <= 0) {
+          int reps = (1 << code) + (int)BrotliReadBits(br, code);
+          if (context_index + reps > context_map_size) {
+            return BROTLI_FAILURE();
+          }
+          do {
+            context_map[context_index++] = 0;
+          } while (--reps);
+        } else {
+          context_map[context_index++] =
+              (uint8_t)(code - max_run_length_prefix);
+        }
+      }
+      if (BrotliReadBits(br, 1)) {
+        InverseMoveToFrontTransform(context_map, context_map_size, s);
+      }
+      s->sub0_state = BROTLI_STATE_SUB0_NONE;
+      return BROTLI_RESULT_SUCCESS;
+    }
   }
 
-  use_rle_for_zeros = (int)BrotliReadBits(br, 1);
-  if (use_rle_for_zeros) {
-    max_run_length_prefix = (int)BrotliReadBits(br, 4) + 1;
-  }
-  table = (HuffmanCode*)malloc(HUFFMAN_MAX_TABLE_SIZE * sizeof(*table));
-  if (table == NULL) {
-    return 0;
-  }
-  if (!ReadHuffmanCode(*num_htrees + max_run_length_prefix, table, br)) {
-    ok = 0;
-    goto End;
-  }
-  for (i = 0; i < context_map_size;) {
-    int code;
-    if (!BrotliReadMoreInput(br)) {
-      printf("[DecodeContextMap] Unexpected end of input.\n");
-      ok = 0;
-      goto End;
-    }
-    code = ReadSymbol(table, br);
-    if (code == 0) {
-      (*context_map)[i] = 0;
-      ++i;
-    } else if (code <= max_run_length_prefix) {
-      int reps = 1 + (1 << code) + (int)BrotliReadBits(br, code);
-      while (--reps) {
-        if (i >= context_map_size) {
-          ok = 0;
-          goto End;
-        }
-        (*context_map)[i] = 0;
-        ++i;
-      }
-    } else {
-      (*context_map)[i] = (uint8_t)(code - max_run_length_prefix);
-      ++i;
-    }
-  }
-  if (BrotliReadBits(br, 1)) {
-    InverseMoveToFrontTransform(*context_map, context_map_size);
-  }
-End:
-  free(table);
-  return ok;
+  return BROTLI_FAILURE();
 }
 
-static BROTLI_INLINE void DecodeBlockType(const int max_block_type,
-                                          const HuffmanCode* trees,
-                                          int tree_type,
-                                          int* block_types,
-                                          int* ringbuffers,
-                                          int* indexes,
-                                          BrotliBitReader* br) {
+static void DecodeBlockType(const int max_block_type,
+                            const HuffmanCode* trees,
+                            int tree_type,
+                            int* ringbuffers,
+                            BrotliBitReader* br) {
   int* ringbuffer = ringbuffers + tree_type * 2;
-  int* index = indexes + tree_type;
-  int type_code = ReadSymbol(&trees[tree_type * HUFFMAN_MAX_TABLE_SIZE], br);
-  int block_type;
-  if (type_code == 0) {
-    block_type = ringbuffer[*index & 1];
-  } else if (type_code == 1) {
-    block_type = ringbuffer[(*index - 1) & 1] + 1;
-  } else {
-    block_type = type_code - 2;
+  int block_type =
+      ReadSymbol(&trees[tree_type * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br) - 2;
+  if (block_type == -1) {
+    block_type = ringbuffer[1] + 1;
+  } else if (block_type == -2) {
+    block_type = ringbuffer[0];
   }
   if (block_type >= max_block_type) {
     block_type -= max_block_type;
   }
-  block_types[tree_type] = block_type;
-  ringbuffer[(*index) & 1] = block_type;
-  ++(*index);
+  ringbuffer[0] = ringbuffer[1];
+  ringbuffer[1] = block_type;
 }
 
-/* Copy len bytes from src to dst. It can write up to ten extra bytes
-   after the end of the copy.
-
-   The main part of this loop is a simple copy of eight bytes at a time until
-   we've copied (at least) the requested amount of bytes.  However, if dst and
-   src are less than eight bytes apart (indicating a repeating pattern of
-   length < 8), we first need to expand the pattern in order to get the correct
-   results. For instance, if the buffer looks like this, with the eight-byte
-   <src> and <dst> patterns marked as intervals:
-
-      abxxxxxxxxxxxx
-      [------]           src
-        [------]         dst
-
-   a single eight-byte copy from <src> to <dst> will repeat the pattern once,
-   after which we can move <dst> two bytes without moving <src>:
-
-      ababxxxxxxxxxx
-      [------]           src
-          [------]       dst
-
-   and repeat the exercise until the two no longer overlap.
+/* Decodes the block type and updates the state for literal context. */
+static void DecodeBlockTypeWithContext(BrotliState* s,
+                                       BrotliBitReader* br) {
+  uint8_t context_mode;
+  int context_offset;
+  DecodeBlockType(s->num_block_types[0], s->block_type_trees, 0,
+                  s->block_type_rb, br);
+  s->block_length[0] = ReadBlockLength(s->block_len_trees, br);
+  context_offset = s->block_type_rb[1] << kLiteralContextBits;
+  s->context_map_slice = s->context_map + context_offset;
+  s->literal_htree_index = s->context_map_slice[0];
+  s->literal_htree = s->literal_hgroup.htrees[s->literal_htree_index];
+  context_mode = s->context_modes[s->block_type_rb[1]];
+  s->context_lookup1 = &kContextLookup[kContextLookupOffsets[context_mode]];
+  s->context_lookup2 = &kContextLookup[kContextLookupOffsets[context_mode + 1]];
+}
 
-   This allows us to do very well in the special case of one single byte
-   repeated many times, without taking a big hit for more general cases.
-
-   The worst case of extra writing past the end of the match occurs when
-   dst - src == 1 and len == 1; the last copy will read from byte positions
-   [0..7] and write to [4..11], whereas it was only supposed to write to
-   position 1. Thus, ten excess bytes.
-*/
-static BROTLI_INLINE void IncrementalCopyFastPath(
-    uint8_t* dst, const uint8_t* src, int len) {
-  if (src < dst) {
-    while (dst - src < 8) {
-      UNALIGNED_MOVE64(dst, src);
-      len -= (int)(dst - src);
-      dst += dst - src;
-    }
+BrotliResult WriteRingBuffer(BrotliOutput output,
+                             BrotliState* s) {
+  int num_written = BrotliWrite(
+      output, s->ringbuffer + s->partially_written,
+      (size_t)(s->to_write - s->partially_written));
+  if (num_written < 0) {
+    return BROTLI_FAILURE();
   }
-  while (len > 0) {
-    UNALIGNED_COPY64(dst, src);
-    src += 8;
-    dst += 8;
-    len -= 8;
+  s->partially_written += num_written;
+  if (s->partially_written < s->to_write) {
+    return BROTLI_RESULT_NEEDS_MORE_OUTPUT;
   }
+  return BROTLI_RESULT_SUCCESS;
 }
 
-int CopyUncompressedBlockToOutput(BrotliOutput output, int len, int pos,
-                                  uint8_t* ringbuffer, int ringbuffer_mask,
-                                  BrotliBitReader* br) {
-  const int rb_size = ringbuffer_mask + 1;
-  uint8_t* ringbuffer_end = ringbuffer + rb_size;
-  int rb_pos = pos & ringbuffer_mask;
-  int br_pos = br->pos_ & BROTLI_IBUF_MASK;
-  int nbytes;
-  uint32_t remaining_bits;
-
-  /* For short lengths copy byte-by-byte */
-  if (len < 8 || br->bit_pos_ + (uint32_t)(len << 3) < br->bit_end_pos_) {
-    while (len-- > 0) {
-      if (!BrotliReadMoreInput(br)) {
-        return 0;
-      }
-      ringbuffer[rb_pos++]= (uint8_t)BrotliReadBits(br, 8);
-      if (rb_pos == rb_size) {
-        if (BrotliWrite(output, ringbuffer, (size_t)rb_size) < rb_size) {
-          return 0;
+BrotliResult BROTLI_NOINLINE CopyUncompressedBlockToOutput(BrotliOutput output,
+                                                           int pos,
+                                                           BrotliState* s) {
+  BrotliResult result;
+  int num_read;
+  /* State machine */
+  for (;;) {
+    switch ((int)s->sub0_state) {
+      case BROTLI_STATE_SUB0_NONE:
+        /* For short lengths copy byte-by-byte */
+        if (s->meta_block_remaining_len < 8 ||
+            s->meta_block_remaining_len < BrotliGetRemainingBytes(&s->br)) {
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_SHORT;
+          break;
+        }
+        /* Copy remaining bytes from s->br.buf_ to ringbuffer. */
+        s->nbytes = (int)BrotliGetRemainingBytes(&s->br);
+        BrotliCopyBytes(&s->ringbuffer[pos], &s->br, (size_t)s->nbytes);
+        pos += s->nbytes;
+        s->meta_block_remaining_len -= s->nbytes;
+        if (pos >= s->ringbuffer_size) {
+          s->to_write = s->ringbuffer_size;
+          s->partially_written = 0;
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_1;
+          break;
+        }
+        if (pos + s->meta_block_remaining_len >= s->ringbuffer_size) {
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_FILL;
+        } else {
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_COPY;
+        }
+        break;
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_SHORT:
+        while (s->meta_block_remaining_len > 0) {
+          if (!BrotliCheckInputAmount(&s->br, 32)) {
+            return BROTLI_RESULT_NEEDS_MORE_INPUT;
+          }
+          s->ringbuffer[pos++] = (uint8_t)BrotliReadBits(&s->br, 8);
+          s->meta_block_remaining_len--;
+        }
+        if (pos >= s->ringbuffer_size) {
+          s->to_write = s->ringbuffer_size;
+          s->partially_written = 0;
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_2;
+        } else {
+          s->sub0_state = BROTLI_STATE_SUB0_NONE;
+          return BROTLI_RESULT_SUCCESS;
+        }
+        /* No break, if state is updated, continue to next state */
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_1:
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_2:
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_3:
+        result = WriteRingBuffer(output, s);
+        if (result != BROTLI_RESULT_SUCCESS) {
+          return result;
         }
-        rb_pos = 0;
-      }
+        pos &= s->ringbuffer_mask;
+        s->max_distance = s->max_backward_distance;
+        if (s->sub0_state == BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_2) {
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_SHORT;
+          break;
+        }
+        if (s->sub0_state == BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_1) {
+          s->meta_block_remaining_len -= s->ringbuffer_size;
+          /* If we wrote past the logical end of the ringbuffer, copy the tail
+             of the ringbuffer to its beginning and flush the ringbuffer to the
+             output. */
+          memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)pos);
+        }
+        if (pos + s->meta_block_remaining_len >= s->ringbuffer_size) {
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_FILL;
+        } else {
+          s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_COPY;
+          break;
+        }
+        /* No break, continue to next state */
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_FILL:
+        /* If we have more to copy than the remaining size of the ringbuffer,
+           then we first fill the ringbuffer from the input and then flush the
+           ringbuffer to the output */
+        s->nbytes = s->ringbuffer_size - pos;
+        num_read = BrotliRead(s->br.input_, &s->ringbuffer[pos],
+                              (size_t)s->nbytes);
+        s->meta_block_remaining_len -= num_read;
+        if (num_read < s->nbytes) {
+          if (num_read < 0) return BROTLI_FAILURE();
+          return BROTLI_RESULT_NEEDS_MORE_INPUT;
+        }
+        s->to_write = s->ringbuffer_size;
+        s->partially_written = 0;
+        s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_3;
+        break;
+        /* No break, continue to next state */
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_COPY:
+        /* Copy straight from the input onto the ringbuffer. The ringbuffer will
+           be flushed to the output at a later time. */
+        num_read = BrotliRead(s->br.input_, &s->ringbuffer[pos],
+                              (size_t)s->meta_block_remaining_len);
+        s->meta_block_remaining_len -= num_read;
+        if (s->meta_block_remaining_len > 0) {
+          if (num_read < 0) return BROTLI_FAILURE();
+          return BROTLI_RESULT_NEEDS_MORE_INPUT;
+        }
+        s->sub0_state = BROTLI_STATE_SUB0_UNCOMPRESSED_WARMUP;
+        /* No break, continue to next state */
+      case BROTLI_STATE_SUB0_UNCOMPRESSED_WARMUP:
+        if (!BrotliCheckInputAmount(&s->br, 32)) {
+          return BROTLI_RESULT_NEEDS_MORE_INPUT;
+        }
+        BrotliWarmupBitReader(&s->br);
+        s->sub0_state = BROTLI_STATE_SUB0_NONE;
+        return BROTLI_RESULT_SUCCESS;
     }
-    return 1;
-  }
-
-  if (br->bit_end_pos_ < 64) {
-    return 0;
-  }
-
-  /*
-   * Copy remaining 0-4 in 32-bit case or 0-8 bytes in the 64-bit case
-   * from br->val_ to ringbuffer.
-   */
-#if (BROTLI_USE_64_BITS)
-  remaining_bits = 64;
-#else
-  remaining_bits = 32;
-#endif
-  while (br->bit_pos_ < remaining_bits) {
-    ringbuffer[rb_pos] = (uint8_t)(br->val_ >> br->bit_pos_);
-    br->bit_pos_ += 8;
-    ++rb_pos;
-    --len;
   }
-
-  /* Copy remaining bytes from br->buf_ to ringbuffer. */
-  nbytes = (int)(br->bit_end_pos_ - br->bit_pos_) >> 3;
-  if (br_pos + nbytes > BROTLI_IBUF_MASK) {
-    int tail = BROTLI_IBUF_MASK + 1 - br_pos;
-    memcpy(&ringbuffer[rb_pos], &br->buf_[br_pos], (size_t)tail);
-    nbytes -= tail;
-    rb_pos += tail;
-    len -= tail;
-    br_pos = 0;
-  }
-  memcpy(&ringbuffer[rb_pos], &br->buf_[br_pos], (size_t)nbytes);
-  rb_pos += nbytes;
-  len -= nbytes;
-
-  /* If we wrote past the logical end of the ringbuffer, copy the tail of the
-     ringbuffer to its beginning and flush the ringbuffer to the output. */
-  if (rb_pos >= rb_size) {
-    if (BrotliWrite(output, ringbuffer, (size_t)rb_size) < rb_size) {
-      return 0;
-    }
-    rb_pos -= rb_size;
-    memcpy(ringbuffer, ringbuffer_end, (size_t)rb_pos);
-  }
-
-  /* If we have more to copy than the remaining size of the ringbuffer, then we
-     first fill the ringbuffer from the input and then flush the ringbuffer to
-     the output */
-  while (rb_pos + len >= rb_size) {
-    nbytes = rb_size - rb_pos;
-    if (BrotliRead(br->input_, &ringbuffer[rb_pos], (size_t)nbytes) < nbytes ||
-        BrotliWrite(output, ringbuffer, (size_t)rb_size) < nbytes) {
-      return 0;
-    }
-    len -= nbytes;
-    rb_pos = 0;
-  }
-
-  /* Copy straight from the input onto the ringbuffer. The ringbuffer will be
-     flushed to the output at a later time. */
-  if (BrotliRead(br->input_, &ringbuffer[rb_pos], (size_t)len) < len) {
-    return 0;
-  }
-
-  /* Restore the state of the bit reader. */
-  BrotliInitBitReader(br, br->input_);
-  return 1;
+  return BROTLI_FAILURE();
 }
 
 int BrotliDecompressedSize(size_t encoded_size,
                            const uint8_t* encoded_buffer,
                            size_t* decoded_size) {
   int i;
   uint64_t val = 0;
   int bit_pos = 0;
@@ -654,30 +749,40 @@ int BrotliDecompressedSize(size_t encode
     return 0;
   }
   /* Look at the first 8 bytes, it is enough to decode the length of the first
      meta-block. */
   for (i = 0; (size_t)i < encoded_size && i < 8; ++i) {
     val |= (uint64_t)encoded_buffer[i] << (8 * i);
   }
   /* Skip the window bits. */
-  bit_pos += (val & 1) ? 4 : 1;
+  ++bit_pos;
+  if (val & 1) {
+    bit_pos += 3;
+    if (((val >> 1) & 7) == 0) {
+      bit_pos += 3;
+    }
+  }
   /* Decode the ISLAST bit. */
   is_last = (val >> bit_pos) & 1;
   ++bit_pos;
   if (is_last) {
     /* Decode the ISEMPTY bit, if it is set to 1, we are done. */
     if ((val >> bit_pos) & 1) {
       *decoded_size = 0;
       return 1;
     }
     ++bit_pos;
   }
   /* Decode the length of the first meta-block. */
   size_nibbles = (int)((val >> bit_pos) & 3) + 4;
+  if (size_nibbles == 7) {
+    /* First meta-block contains metadata, this case is not supported here. */
+    return 0;
+  }
   bit_pos += 2;
   for (i = 0; i < size_nibbles; ++i) {
     meta_block_len |= (int)((val >> bit_pos) & 0xf) << (4 * i);
     bit_pos += 4;
   }
   ++meta_block_len;
   if (is_last) {
     /* If this meta-block is the only one, we are done. */
@@ -693,473 +798,776 @@ int BrotliDecompressedSize(size_t encode
        followed by an empty one, so the decompressed size is the size of the
        first meta-block. */
     size_t offset = (size_t)((bit_pos + 7) >> 3) + (size_t)meta_block_len;
     if (offset < encoded_size && ((encoded_buffer[offset] & 3) == 3)) {
       *decoded_size = (size_t)meta_block_len;
       return 1;
     }
   }
+  /* Could not get the size because the file has multiple meta-blocks */
   return 0;
 }
 
-int BrotliDecompressBuffer(size_t encoded_size,
-                           const uint8_t* encoded_buffer,
-                           size_t* decoded_size,
-                           uint8_t* decoded_buffer) {
+BrotliResult BrotliDecompressBuffer(size_t encoded_size,
+                                    const uint8_t* encoded_buffer,
+                                    size_t* decoded_size,
+                                    uint8_t* decoded_buffer) {
   BrotliMemInput memin;
   BrotliInput in = BrotliInitMemInput(encoded_buffer, encoded_size, &memin);
   BrotliMemOutput mout;
   BrotliOutput out = BrotliInitMemOutput(decoded_buffer, *decoded_size, &mout);
-  int success = BrotliDecompress(in, out);
+  BrotliResult success = BrotliDecompress(in, out);
   *decoded_size = mout.pos;
   return success;
 }
 
-int BrotliDecompress(BrotliInput input, BrotliOutput output) {
-  int ok = 1;
-  int i;
-  int pos = 0;
-  int input_end = 0;
-  int window_bits = 0;
-  int max_backward_distance;
-  int max_distance = 0;
-  int ringbuffer_size;
-  int ringbuffer_mask;
-  uint8_t* ringbuffer;
-  uint8_t* ringbuffer_end;
-  /* This ring buffer holds a few past copy distances that will be used by */
-  /* some special distance codes. */
-  int dist_rb[4] = { 16, 15, 11, 4 };
-  int dist_rb_idx = 0;
-  /* The previous 2 bytes used for context. */
-  uint8_t prev_byte1 = 0;
-  uint8_t prev_byte2 = 0;
-  HuffmanTreeGroup hgroup[3];
-  HuffmanCode* block_type_trees = NULL;
-  HuffmanCode* block_len_trees = NULL;
-  BrotliBitReader br;
+BrotliResult BrotliDecompress(BrotliInput input, BrotliOutput output) {
+  BrotliState s;
+  BrotliResult result;
+  BrotliStateInit(&s);
+  result = BrotliDecompressStreaming(input, output, 1, &s);
+  if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) {
+    /* Not ok: it didn't finish even though this is a non-streaming function. */
+    result = BROTLI_FAILURE();
+  }
+  BrotliStateCleanup(&s);
+  return result;
+}
 
+BrotliResult BrotliDecompressBufferStreaming(size_t* available_in,
+                                             const uint8_t** next_in,
+                                             int finish,
+                                             size_t* available_out,
+                                             uint8_t** next_out,
+                                             size_t* total_out,
+                                             BrotliState* s) {
+  BrotliMemInput memin;
+  BrotliInput in = BrotliInitMemInput(*next_in, *available_in, &memin);
+  BrotliMemOutput memout;
+  BrotliOutput out = BrotliInitMemOutput(*next_out, *available_out, &memout);
+  BrotliResult result = BrotliDecompressStreaming(in, out, finish, s);
+  /* The current implementation reads everything, so 0 bytes are available. */
+  *next_in += memin.pos;
+  *available_in -= memin.pos;
+  /* Update the output position to where we write next. */
+  *next_out += memout.pos;
+  *available_out -= memout.pos;
+  *total_out += memout.pos;
+  return result;
+}
+
+BrotliResult BrotliDecompressStreaming(BrotliInput input, BrotliOutput output,
+                                       int finish, BrotliState* s) {
+  uint8_t context;
+  int pos = s->pos;
+  int i = s->loop_counter;
+  BrotliResult result = BROTLI_RESULT_SUCCESS;
+  BrotliBitReader* br = &s->br;
+  int initial_remaining_len;
+  int bytes_copied;
+  int is_metadata;
+  int is_uncompressed;
+  uint8_t *copy_src;
+  uint8_t *copy_dst;
   /* We need the slack region for the following reasons:
-       - always doing two 8-byte copies for fast backward copying
+       - doing up to two 16-byte copies for fast backward copying
        - transforms
-       - flushing the input ringbuffer when decoding uncompressed blocks */
-  static const int kRingBufferWriteAheadSlack = 128 + BROTLI_READ_SIZE;
+       - flushing the input s->ringbuffer when decoding uncompressed blocks */
+  static const int kRingBufferWriteAheadSlack =
+      BROTLI_IMPLICIT_ZEROES + BROTLI_READ_SIZE;
+  s->br.input_ = input;
+  /* State machine */
+  for (;;) {
+    if (result != BROTLI_RESULT_SUCCESS) {
+      if (result == BROTLI_RESULT_NEEDS_MORE_INPUT) {
+        if (BrotliReadInput(br, finish)) {
+          result = BROTLI_RESULT_SUCCESS;
+          continue;
+        }
+        if (finish) {
+          BROTLI_LOG(("Unexpected end of input. State: %d\n", s->state));
+          result = BROTLI_FAILURE();
+        }
+      }
+      break;  /* Fail, or partial data. */
+    }
+    switch (s->state) {
+      case BROTLI_STATE_UNINITED:
+        pos = 0;
+        BrotliInitBitReader(br, input);
+
+        s->state = BROTLI_STATE_BITREADER_WARMUP;
+        /* No break, continue to next state */
+      case BROTLI_STATE_BITREADER_WARMUP:
+        if (!BrotliCheckInputAmount(br, 32)) {
+          result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+          break;
+        }
+        BrotliWarmupBitReader(br);
+        /* Decode window size. */
+        s->window_bits = DecodeWindowBits(br);
+        if (s->window_bits == 9) {
+          /* Value 9 is reserved for future use. */
+          result = BROTLI_FAILURE();
+          break;
+        }
+        /* Allocate the ringbuffer */
+        {
+          size_t known_size = 0;
+          s->ringbuffer_size = 1 << s->window_bits;
 
-  if (!BrotliInitBitReader(&br, input)) {
-    return 0;
-  }
+          /* If we know the data size is small, do not allocate more ringbuffer
+             size than needed to reduce memory usage. Since this happens after
+             the first BrotliCheckInputAmount call, we can read the bitreader
+             buffer at position 0.
+             We need at least 2 bytes of ring buffer size to get the last two
+             bytes for context from there */
+          if (BrotliDecompressedSize(BROTLI_READ_SIZE, br->buf_, &known_size)) {
+            while (s->ringbuffer_size >= known_size * 2
+                && s->ringbuffer_size > 32) {
+              s->ringbuffer_size >>= 1;
+            }
+          }
+
+          /* But make it fit the custom dictionary if there is one. */
+          while (s->ringbuffer_size < s->custom_dict_size) {
+            s->ringbuffer_size <<= 1;
+          }
 
-  /* Decode window size. */
-  window_bits = DecodeWindowBits(&br);
-  max_backward_distance = (1 << window_bits) - 16;
+          s->ringbuffer_mask = s->ringbuffer_size - 1;
+          s->ringbuffer = (uint8_t*)malloc((size_t)(s->ringbuffer_size +
+                                                 kRingBufferWriteAheadSlack +
+                                                 kMaxDictionaryWordLength));
+          if (!s->ringbuffer) {
+            result = BROTLI_FAILURE();
+            break;
+          }
+          s->ringbuffer_end = s->ringbuffer + s->ringbuffer_size;
+          s->ringbuffer[s->ringbuffer_size - 2] = 0;
+          s->ringbuffer[s->ringbuffer_size - 1] = 0;
+          if (s->custom_dict) {
+            memcpy(&s->ringbuffer[(-s->custom_dict_size) & s->ringbuffer_mask],
+                                  s->custom_dict, (size_t)s->custom_dict_size);
+          }
+        }
+        s->max_backward_distance = (1 << s->window_bits) - 16;
+        s->max_backward_distance_minus_custom_dict_size =
+            s->max_backward_distance - s->custom_dict_size;
+
+        /* Allocate memory for both block_type_trees and block_len_trees. */
+        s->block_type_trees = (HuffmanCode*)malloc(
+            6 * BROTLI_HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
+
+        if (s->block_type_trees == NULL) {
+          result = BROTLI_FAILURE();
+          break;
+        }
+        s->block_len_trees = s->block_type_trees +
+            3 * BROTLI_HUFFMAN_MAX_TABLE_SIZE;
 
-  ringbuffer_size = 1 << window_bits;
-  ringbuffer_mask = ringbuffer_size - 1;
-  ringbuffer = (uint8_t*)malloc((size_t)(ringbuffer_size +
-                                         kRingBufferWriteAheadSlack +
-                                         kMaxDictionaryWordLength));
-  if (!ringbuffer) {
-    ok = 0;
-  }
-  ringbuffer_end = ringbuffer + ringbuffer_size;
-
-  if (ok) {
-    block_type_trees = (HuffmanCode*)malloc(
-        3 * HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
-    block_len_trees = (HuffmanCode*)malloc(
-        3 * HUFFMAN_MAX_TABLE_SIZE * sizeof(HuffmanCode));
-    if (block_type_trees == NULL || block_len_trees == NULL) {
-      ok = 0;
+        s->state = BROTLI_STATE_METABLOCK_BEGIN;
+        /* No break, continue to next state */
+      case BROTLI_STATE_METABLOCK_BEGIN:
+        if (s->input_end) {
+          s->to_write = pos;
+          s->partially_written = 0;
+          s->state = BROTLI_STATE_DONE;
+          break;
+        }
+        BrotliStateMetablockBegin(s);
+        s->state = BROTLI_STATE_METABLOCK_HEADER_1;
+        /* No break, continue to next state */
+      case BROTLI_STATE_METABLOCK_HEADER_1:
+        if (!BrotliCheckInputAmount(br, 32)) {
+          result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+          break;
+        }
+        BROTLI_LOG_UINT(pos);
+        if (!DecodeMetaBlockLength(br,
+                                   &s->meta_block_remaining_len,
+                                   &s->input_end,
+                                   &is_metadata,
+                                   &is_uncompressed)) {
+          result = BROTLI_FAILURE();
+          break;
+        }
+        BROTLI_LOG_UINT(s->meta_block_remaining_len);
+        if (is_metadata) {
+          if (!BrotliJumpToByteBoundary(br)) {
+            result = BROTLI_FAILURE();
+            break;
+          }
+          s->state = BROTLI_STATE_METADATA;
+          break;
+        }
+        if (s->meta_block_remaining_len == 0) {
+          s->state = BROTLI_STATE_METABLOCK_DONE;
+          break;
+        }
+        if (is_uncompressed) {
+          if (!BrotliJumpToByteBoundary(br)) {
+            result = BROTLI_FAILURE();
+            break;
+          }
+          s->state = BROTLI_STATE_UNCOMPRESSED;
+          break;
+        }
+        i = 0;
+        s->state = BROTLI_STATE_HUFFMAN_CODE_0;
+        break;
+      case BROTLI_STATE_UNCOMPRESSED:
+        initial_remaining_len = s->meta_block_remaining_len;
+        /* pos is given as argument since s->pos is only updated at the end. */
+        result = CopyUncompressedBlockToOutput(output, pos, s);
+        bytes_copied = initial_remaining_len - s->meta_block_remaining_len;
+        pos = (pos + bytes_copied) & s->ringbuffer_mask;
+        if (result != BROTLI_RESULT_SUCCESS) {
+          break;
+        }
+        s->state = BROTLI_STATE_METABLOCK_DONE;
+        break;
+      case BROTLI_STATE_METADATA:
+        for (; s->meta_block_remaining_len > 0; --s->meta_block_remaining_len) {
+          if (!BrotliCheckInputAmount(br, 32)) {
+            result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+            break;
+          }
+          /* Read one byte and ignore it. */
+          BrotliReadBits(br, 8);
+        }
+        if (result == BROTLI_RESULT_SUCCESS) {
+          s->state = BROTLI_STATE_METABLOCK_DONE;
+        }
+        break;
+      case BROTLI_STATE_HUFFMAN_CODE_0:
+        if (i >= 3) {
+          BROTLI_LOG_UINT(s->num_block_type_rb[0]);
+          BROTLI_LOG_UINT(s->num_block_type_rb[2]);
+          BROTLI_LOG_UINT(s->num_block_type_rb[4]);
+          BROTLI_LOG_UINT(s->block_length[0]);
+          BROTLI_LOG_UINT(s->block_length[1]);
+          BROTLI_LOG_UINT(s->block_length[2]);
+          s->state = BROTLI_STATE_METABLOCK_HEADER_2;
+          break;
+        }
+        s->num_block_types[i] = DecodeVarLenUint8(br) + 1;
+        s->state = BROTLI_STATE_HUFFMAN_CODE_1;
+        /* No break, continue to next state */
+      case BROTLI_STATE_HUFFMAN_CODE_1:
+        if (s->num_block_types[i] >= 2) {
+          result = ReadHuffmanCode(s->num_block_types[i] + 2,
+              &s->block_type_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
+              NULL, s);
+          if (result != BROTLI_RESULT_SUCCESS) break;
+          s->state = BROTLI_STATE_HUFFMAN_CODE_2;
+        } else {
+          i++;
+          s->state = BROTLI_STATE_HUFFMAN_CODE_0;
+          break;
+        }
+        /* No break, continue to next state */
+      case BROTLI_STATE_HUFFMAN_CODE_2:
+        result = ReadHuffmanCode(kNumBlockLengthCodes,
+            &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE],
+            NULL, s);
+        if (result != BROTLI_RESULT_SUCCESS) break;
+        s->block_length[i] = ReadBlockLength(
+            &s->block_len_trees[i * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
+        i++;
+        s->state = BROTLI_STATE_HUFFMAN_CODE_0;
+        break;
+      case BROTLI_STATE_METABLOCK_HEADER_2:
+        /* We need up to 256 * 2 + 6 bits, this fits in 128 bytes. */
+        if (!BrotliCheckInputAmount(br, 128)) {
+          result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+          break;
+        }
+        s->distance_postfix_bits = (int)BrotliReadBits(br, 2);
+        s->num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES +
+            ((int)BrotliReadBits(br, 4) << s->distance_postfix_bits);
+        s->distance_postfix_mask = (int)BitMask(s->distance_postfix_bits);
+        s->context_modes = (uint8_t*)malloc((size_t)s->num_block_types[0]);
+        if (s->context_modes == 0) {
+          result = BROTLI_FAILURE();
+          break;
+        }
+        for (i = 0; i < s->num_block_types[0]; ++i) {
+          s->context_modes[i] = (uint8_t)(BrotliReadBits(br, 2) << 1);
+          BROTLI_LOG_ARRAY_INDEX(s->context_modes, i);
+        }
+        BROTLI_LOG_UINT(s->num_direct_distance_codes);
+        BROTLI_LOG_UINT(s->distance_postfix_bits);
+        s->state = BROTLI_STATE_CONTEXT_MAP_1;
+        /* No break, continue to next state */
+      case BROTLI_STATE_CONTEXT_MAP_1:
+        result = DecodeContextMap(s->num_block_types[0] << kLiteralContextBits,
+                                  &s->num_literal_htrees, &s->context_map, s);
+        if (result != BROTLI_RESULT_SUCCESS) {
+          break;
+        }
+        s->trivial_literal_context = 1;
+        for (i = 0; i < s->num_block_types[0] << kLiteralContextBits; i++) {
+          if (s->context_map[i] != i >> kLiteralContextBits) {
+            s->trivial_literal_context = 0;
+            break;
+          }
+        }
+        s->state = BROTLI_STATE_CONTEXT_MAP_2;
+        /* No break, continue to next state */
+      case BROTLI_STATE_CONTEXT_MAP_2:
+        {
+          int num_dist_htrees;
+          int num_distance_codes =
+              s->num_direct_distance_codes + (48 << s->distance_postfix_bits);
+          result = DecodeContextMap(
+              s->num_block_types[2] << kDistanceContextBits,
+              &num_dist_htrees, &s->dist_context_map, s);
+          if (result != BROTLI_RESULT_SUCCESS) {
+            break;
+          }
+          BrotliHuffmanTreeGroupInit(
+              &s->literal_hgroup, kNumLiteralCodes, s->num_literal_htrees);
+          BrotliHuffmanTreeGroupInit(
+              &s->insert_copy_hgroup, kNumInsertAndCopyCodes,
+              s->num_block_types[1]);
+          BrotliHuffmanTreeGroupInit(
+              &s->distance_hgroup, num_distance_codes, num_dist_htrees);
+        }
+        i = 0;
+        s->state = BROTLI_STATE_TREE_GROUP;
+        /* No break, continue to next state */
+      case BROTLI_STATE_TREE_GROUP:
+        switch (i) {
+          case 0:
+            result = HuffmanTreeGroupDecode(&s->literal_hgroup, s);
+            break;
+          case 1:
+            result = HuffmanTreeGroupDecode(&s->insert_copy_hgroup, s);
+            break;
+          case 2:
+            result = HuffmanTreeGroupDecode(&s->distance_hgroup, s);
+            break;
+        }
+        if (result != BROTLI_RESULT_SUCCESS) break;
+        i++;
+        if (i >= 3) {
+          uint8_t context_mode = s->context_modes[s->block_type_rb[1]];
+          s->context_map_slice = s->context_map;
+          s->dist_context_map_slice = s->dist_context_map;
+          s->context_lookup1 =
+              &kContextLookup[kContextLookupOffsets[context_mode]];
+          s->context_lookup2 =
+              &kContextLookup[kContextLookupOffsets[context_mode + 1]];
+          s->htree_command = s->insert_copy_hgroup.htrees[0];
+          s->literal_htree = s->literal_hgroup.htrees[s->literal_htree_index];
+          s->state = BROTLI_STATE_COMMAND_BEGIN;
+        }
+        break;
+      case BROTLI_STATE_COMMAND_BEGIN:
+        if (s->meta_block_remaining_len <= 0) {
+          /* Next metablock, if any */
+          s->state = BROTLI_STATE_METABLOCK_DONE;
+          break;
+        }
+ /* Decoding of Brotli commands is the inner loop, jumping with goto makes it
+    3% faster */
+ CommandBegin:
+        if (!BrotliCheckInputAmount(br, 32)) {
+          s->state = BROTLI_STATE_COMMAND_BEGIN;
+          result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+          break;
+        }
+          /* Read the insert/copy length in the command */
+        if (s->block_length[1] == 0) {
+          /* Block switch for insert/copy length */
+          DecodeBlockType(s->num_block_types[1],
+                          s->block_type_trees, 1,
+                          s->block_type_rb, br);
+          s->htree_command = s->insert_copy_hgroup.htrees[s->block_type_rb[3]];
+          s->block_length[1] = ReadBlockLength(
+              &s->block_len_trees[BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
+        }
+        {
+          int cmd_code = ReadSymbol(s->htree_command, br);
+          CmdLutElement v;
+          --s->block_length[1];
+          v = kCmdLut[cmd_code];
+          s->distance_code = v.distance_code;
+          s->distance_context = v.context;
+          s->dist_htree_index = s->dist_context_map_slice[s->distance_context];
+          i = (int)BrotliReadBits(br, v.insert_len_extra_bits) +
+              v.insert_len_offset;
+          s->copy_length = (int)BrotliReadBits(br, v.copy_len_extra_bits) +
+              v.copy_len_offset;
+        }
+        BROTLI_LOG_UINT(i);
+        BROTLI_LOG_UINT(s->copy_length);
+        BROTLI_LOG_UINT(s->distance_code);
+        if (i == 0) {
+          goto postDecodeLiterals;
+        }
+        s->meta_block_remaining_len -= i;
+        /* No break, go to next state */
+      case BROTLI_STATE_COMMAND_INNER:
+        /* Read the literals in the command */
+        if (s->trivial_literal_context) {
+          unsigned bits;
+          unsigned value;
+          PreloadSymbol(s->literal_htree, br, &bits, &value);
+          do {
+            if (!BrotliCheckInputAmount(br, 64)) {
+              s->state = BROTLI_STATE_COMMAND_INNER;
+              result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+              break;
+            }
+            if (PREDICT_FALSE(s->block_length[0] == 0)) {
+              /* Block switch for literals */
+              DecodeBlockTypeWithContext(s, br);
+              PreloadSymbol(s->literal_htree, br, &bits, &value);
+            }
+            s->ringbuffer[pos] =
+                (uint8_t)ReadPreloadedSymbol(s->literal_htree,
+                                             br, &bits, &value);
+            --s->block_length[0];
+            BROTLI_LOG_UINT(s->literal_htree_index);
+            BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos);
+            ++pos;
+            if (PREDICT_FALSE(pos == s->ringbuffer_size)) {
+              s->to_write = s->ringbuffer_size;
+              s->partially_written = 0;
+              s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
+              --i;
+              goto innerWrite;
+            }
+          } while (--i != 0);
+        } else {
+          uint8_t p1 = s->ringbuffer[(pos - 1) & s->ringbuffer_mask];
+          uint8_t p2 = s->ringbuffer[(pos - 2) & s->ringbuffer_mask];
+          do {
+            const HuffmanCode* hc;
+            if (!BrotliCheckInputAmount(br, 64)) {
+              s->state = BROTLI_STATE_COMMAND_INNER;
+              result = BROTLI_RESULT_NEEDS_MORE_INPUT;
+              break;
+            }
+            if (PREDICT_FALSE(s->block_length[0] == 0)) {
+              /* Block switch for literals */
+              DecodeBlockTypeWithContext(s, br);
+            }
+            context = s->context_lookup1[p1] | s->context_lookup2[p2];
+            BROTLI_LOG_UINT(context);
+            hc = s->literal_hgroup.htrees[s->context_map_slice[context]];
+            --s->block_length[0];
+            p2 = p1;
+            p1 = (uint8_t)ReadSymbol(hc, br);
+            s->ringbuffer[pos] = p1;
+            BROTLI_LOG_UINT(s->context_map_slice[context]);
+            BROTLI_LOG_ARRAY_INDEX(s->ringbuffer, pos & s->ringbuffer_mask);
+            ++pos;
+            if (PREDICT_FALSE(pos == s->ringbuffer_size)) {
+              s->to_write = s->ringbuffer_size;
+              s->partially_written = 0;
+              s->state = BROTLI_STATE_COMMAND_INNER_WRITE;
+              --i;
+              goto innerWrite;
+            }
+          } while (--i != 0);
+        }
+        if (result != BROTLI_RESULT_SUCCESS) break;
+        if (s->meta_block_remaining_len <= 0) {
+          s->state = BROTLI_STATE_METABLOCK_DONE;
+          break;
+        }
+postDecodeLiterals:
+        if (s->distance_code >= 0) {
+          --s->dist_rb_idx;
+          s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
+          goto postReadDistance;  /* We already have the implicit distance */
+        }
+        /* Read distance code in the command, unless it was implicitely zero. */
+        BROTLI_DCHECK(s->distance_code < 0);
+        if (s->block_length[2] == 0) {
+          /* Block switch for distance codes */
+          int dist_context_offset;
+          DecodeBlockType(s->num_block_types[2],
+                          s->block_type_trees, 2,
+                          s->block_type_rb, br);
+          s->block_length[2] = ReadBlockLength(
+              &s->block_len_trees[2 * BROTLI_HUFFMAN_MAX_TABLE_SIZE], br);
+          dist_context_offset = s->block_type_rb[5] << kDistanceContextBits;
+          s->dist_context_map_slice =
+              s->dist_context_map + dist_context_offset;
+          s->dist_htree_index = s->dist_context_map_slice[s->distance_context];
+        }
+        --s->block_length[2];
+        s->distance_code =
+            ReadSymbol(s->distance_hgroup.htrees[s->dist_htree_index], br);
+        /* Convert the distance code to the actual distance by possibly */
+        /* looking up past distances from the s->ringbuffer. */
+        if ((s->distance_code & ~0xf) == 0) {
+          if (s->distance_code == 0) {
+            --s->dist_rb_idx;
+            s->distance_code = s->dist_rb[s->dist_rb_idx & 3];
+          } else {
+            int distance_code = s->distance_code << 1;
+            /* kDistanceShortCodeIndexOffset has 2-bit values from LSB: */
+            /* 3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2 */
+            const uint32_t kDistanceShortCodeIndexOffset = 0xaaafff1b;
+            /* kDistanceShortCodeValueOffset has 2-bit values from LSB: */
+            /* 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 1, 1, 2, 2, 3, 3 */
+            const uint32_t kDistanceShortCodeValueOffset = 0xfa5fa500;
+            int v = (s->dist_rb_idx +
+                (int)(kDistanceShortCodeIndexOffset >> distance_code)) & 0x3;
+            s->distance_code = s->dist_rb[v];
+            v = (int)(kDistanceShortCodeValueOffset >> distance_code) & 0x3;
+            if ((distance_code & 0x3) != 0) {
+              s->distance_code += v;
+            } else {
+              s->distance_code -= v;
+              if (s->distance_code <= 0) {
+                /* A huge distance will cause a BROTLI_FAILURE() soon. */
+                /* This is a little faster than failing here. */
+                s->distance_code = 0x0fffffff;
+              }
+            }
+          }
+        } else {
+          int distval = s->distance_code - s->num_direct_distance_codes;
+          if (distval >= 0) {
+            int nbits;
+            int postfix;
+            int offset;
+            if (s->distance_postfix_bits == 0) {
+              nbits = (distval >> 1) + 1;
+              offset = ((2 + (distval & 1)) << nbits) - 4;
+              s->distance_code = s->num_direct_distance_codes +
+                  offset + (int)BrotliReadBits(br, nbits);
+            } else {
+              postfix = distval & s->distance_postfix_mask;
+              distval >>= s->distance_postfix_bits;
+              nbits = (distval >> 1) + 1;
+              offset = ((2 + (distval & 1)) << nbits) - 4;
+              s->distance_code = s->num_direct_distance_codes +
+                  ((offset + (int)BrotliReadBits(br, nbits)) <<
+                   s->distance_postfix_bits) + postfix;
+            }
+          }
+          s->distance_code = s->distance_code - NUM_DISTANCE_SHORT_CODES + 1;
+        }
+postReadDistance:
+        BROTLI_LOG_UINT(s->distance_code);
+        if (s->max_distance != s->max_backward_distance) {
+          if (pos < s->max_backward_distance_minus_custom_dict_size) {
+            s->max_distance = pos + s->custom_dict_size;
+          } else {
+            s->max_distance = s->max_backward_distance;
+          }
+        }
+        i = s->copy_length;
+        /* Apply copy of LZ77 back-reference, or static dictionary reference if
+        the distance is larger than the max LZ77 distance */
+        if (s->distance_code > s->max_distance) {
+          if (i >= kMinDictionaryWordLength &&
+              i <= kMaxDictionaryWordLength) {
+            int offset = kBrotliDictionaryOffsetsByLength[i];
+            int word_id = s->distance_code - s->max_distance - 1;
+            int shift = kBrotliDictionarySizeBitsByLength[i];
+            int mask = (int)BitMask(shift);
+            int word_idx = word_id & mask;
+            int transform_idx = word_id >> shift;
+            offset += word_idx * i;
+            if (transform_idx < kNumTransforms) {
+              const uint8_t* word = &kBrotliDictionary[offset];
+              int len = i;
+              if (transform_idx == 0) {
+                memcpy(&s->ringbuffer[pos], word, (size_t)len);
+              } else {
+                len = TransformDictionaryWord(
+                    &s->ringbuffer[pos], word, len, transform_idx);
+              }
+              pos += len;
+              s->meta_block_remaining_len -= len;
+              if (pos >= s->ringbuffer_size) {
+                s->to_write = s->ringbuffer_size;
+                s->partially_written = 0;
+                s->state = BROTLI_STATE_COMMAND_POST_WRITE_1;
+                break;
+              }
+            } else {
+              BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
+                     "len: %d bytes left: %d\n",
+                  pos, s->distance_code, i,
+                  s->meta_block_remaining_len));
+              result = BROTLI_FAILURE();
+              break;
+            }
+          } else {
+            BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
+                   "len: %d bytes left: %d\n", pos, s->distance_code, i,
+                   s->meta_block_remaining_len));
+            result = BROTLI_FAILURE();
+            break;
+          }
+        } else {
+          const uint8_t *ringbuffer_end_minus_copy_length =
+              s->ringbuffer_end - i;
+          copy_src = &s->ringbuffer[(pos - s->distance_code) &
+                                    s->ringbuffer_mask];
+          copy_dst = &s->ringbuffer[pos];
+          /* update the recent distances cache */
+          s->dist_rb[s->dist_rb_idx & 3] = s->distance_code;
+          ++s->dist_rb_idx;
+          s->meta_block_remaining_len -= i;
+          if (PREDICT_FALSE(s->meta_block_remaining_len < 0)) {
+            BROTLI_LOG(("Invalid backward reference. pos: %d distance: %d "
+                   "len: %d bytes left: %d\n", pos, s->distance_code, i,
+                   s->meta_block_remaining_len));
+            result = BROTLI_FAILURE();
+            break;
+          }
+          /* There is 128+ bytes of slack in the ringbuffer allocation.
+             Also, we have 16 short codes, that make these 16 bytes irrelevant
+             in the ringbuffer. Let's copy over them as a first guess.
+           */
+          memmove16(copy_dst, copy_src);
+          /* Now check if the copy extends over the ringbuffer end,
+             or if the copy overlaps with itself, if yes, do wrap-copy. */
+          if (copy_src < copy_dst) {
+            if (copy_dst >= ringbuffer_end_minus_copy_length) {
+              goto postWrapCopy;
+            }
+            if (copy_src + i > copy_dst) {
+              goto postSelfintersecting;
+            }
+          } else {
+            if (copy_src >= ringbuffer_end_minus_copy_length) {
+              goto postWrapCopy;
+            }
+            if (copy_dst + i > copy_src) {
+              goto postSelfintersecting;
+            }
+          }
+          pos += i;
+          if (i > 16) {
+            if (i > 32) {
+              memcpy(copy_dst + 16, copy_src + 16, (size_t)(i - 16));
+            } else {
+              /* This branch covers about 45% cases.
+                 Fixed size short copy allows more compiler optimizations. */
+              memmove16(copy_dst + 16, copy_src + 16);
+            }
+          }
+        }
+        if (s->meta_block_remaining_len <= 0) {
+          /* Next metablock, if any */
+          s->state = BROTLI_STATE_METABLOCK_DONE;
+          break;
+        } else {
+          goto CommandBegin;
+        }
+      postSelfintersecting:
+        while (--i >= 0) {
+          s->ringbuffer[pos] =
+              s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];
+          ++pos;
+        }
+        if (s->meta_block_remaining_len <= 0) {
+          /* Next metablock, if any */
+          s->state = BROTLI_STATE_METABLOCK_DONE;
+          break;
+        } else {
+          goto CommandBegin;
+        }
+      postWrapCopy:
+        s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;
+        /* No break, go to next state */
+      case BROTLI_STATE_COMMAND_POST_WRAP_COPY:
+        while (--i >= 0) {
+          s->ringbuffer[pos] =
+              s->ringbuffer[(pos - s->distance_code) & s->ringbuffer_mask];
+          ++pos;
+          if (pos == s->ringbuffer_size) {
+            s->to_write = s->ringbuffer_size;
+            s->partially_written = 0;
+            s->state = BROTLI_STATE_COMMAND_POST_WRITE_2;
+            break;
+          }
+        }
+        if (s->state == BROTLI_STATE_COMMAND_POST_WRAP_COPY) {
+          if (s->meta_block_remaining_len <= 0) {
+            /* Next metablock, if any */
+            s->state = BROTLI_STATE_METABLOCK_DONE;
+            break;
+          } else {
+            goto CommandBegin;
+          }
+        }
+        break;
+      case BROTLI_STATE_COMMAND_INNER_WRITE:
+      case BROTLI_STATE_COMMAND_POST_WRITE_1:
+      case BROTLI_STATE_COMMAND_POST_WRITE_2:
+innerWrite:
+        result = WriteRingBuffer(output, s);
+        if (result != BROTLI_RESULT_SUCCESS) {
+          break;
+        }
+        pos -= s->ringbuffer_size;
+        s->max_distance = s->max_backward_distance;
+        if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_1) {
+          memcpy(s->ringbuffer, s->ringbuffer_end, (size_t)pos);
+          if (s->meta_block_remaining_len <= 0) {
+            /* Next metablock, if any */
+            s->state = BROTLI_STATE_METABLOCK_DONE;
+            break;
+          } else {
+            goto CommandBegin;
+          }
+        } else if (s->state == BROTLI_STATE_COMMAND_POST_WRITE_2) {
+          s->state = BROTLI_STATE_COMMAND_POST_WRAP_COPY;
+        } else {  /* BROTLI_STATE_COMMAND_INNER_WRITE */
+          if (i == 0) {
+            if (s->meta_block_remaining_len <= 0) {
+              s->state = BROTLI_STATE_METABLOCK_DONE;
+              break;
+            }
+            goto postDecodeLiterals;
+          }
+          s->state = BROTLI_STATE_COMMAND_INNER;
+        }
+        break;
+      case BROTLI_STATE_METABLOCK_DONE:
+        BrotliStateCleanupAfterMetablock(s);
+        s->state = BROTLI_STATE_METABLOCK_BEGIN;
+        break;
+      case BROTLI_STATE_DONE:
+        if (s->ringbuffer != 0) {
+          result = WriteRingBuffer(output, s);
+          if (result != BROTLI_RESULT_SUCCESS) {
+            break;
+          }
+        }
+        if (!BrotliJumpToByteBoundary(br)) {
+          result = BROTLI_FAILURE();
+        }
+        if (BrotliGetRemainingBytes(br) < BROTLI_IMPLICIT_ZEROES) {
+          /* The brotli input stream was too small, does not follow the spec. It
+          might have decompressed fine because of the implicit 128 zeroes added.
+          NOTE: larger input is allowed, smaller not. */
+          result = BROTLI_FAILURE();
+        }
+        return result;
     }
   }
-
-  while (!input_end && ok) {
-    int meta_block_remaining_len = 0;
-    int is_uncompressed;
-    int block_length[3] = { 1 << 28, 1 << 28, 1 << 28 };
-    int block_type[3] = { 0 };
-    int num_block_types[3] = { 1, 1, 1 };
-    int block_type_rb[6] = { 0, 1, 0, 1, 0, 1 };
-    int block_type_rb_index[3] = { 0 };
-    int distance_postfix_bits;
-    int num_direct_distance_codes;
-    int distance_postfix_mask;
-    int num_distance_codes;
-    uint8_t* context_map = NULL;
-    uint8_t* context_modes = NULL;
-    int num_literal_htrees;
-    uint8_t* dist_context_map = NULL;
-    int num_dist_htrees;
-    int context_offset = 0;
-    uint8_t* context_map_slice = NULL;
-    uint8_t literal_htree_index = 0;
-    int dist_context_offset = 0;
-    uint8_t* dist_context_map_slice = NULL;
-    uint8_t dist_htree_index = 0;
-    int context_lookup_offset1 = 0;
-    int context_lookup_offset2 = 0;
-    uint8_t context_mode;
-    HuffmanCode* htree_command;
-
-    for (i = 0; i < 3; ++i) {
-      hgroup[i].codes = NULL;
-      hgroup[i].htrees = NULL;
-    }
-
-    if (!BrotliReadMoreInput(&br)) {
-      printf("[BrotliDecompress] Unexpected end of input.\n");
-      ok = 0;
-      goto End;
-    }
-    BROTLI_LOG_UINT(pos);
-    DecodeMetaBlockLength(&br, &meta_block_remaining_len,
-                          &input_end, &is_uncompressed);
-    BROTLI_LOG_UINT(meta_block_remaining_len);
-    if (meta_block_remaining_len == 0) {
-      goto End;
-    }
-    if (is_uncompressed) {
-      BrotliSetBitPos(&br, (br.bit_pos_ + 7) & (uint32_t)(~7UL));
-      ok = CopyUncompressedBlockToOutput(output, meta_block_remaining_len, pos,
-                                         ringbuffer, ringbuffer_mask, &br);
-      pos += meta_block_remaining_len;
-      goto End;
-    }
-    for (i = 0; i < 3; ++i) {
-      num_block_types[i] = DecodeVarLenUint8(&br) + 1;
-      if (num_block_types[i] >= 2) {
-        if (!ReadHuffmanCode(num_block_types[i] + 2,
-                             &block_type_trees[i * HUFFMAN_MAX_TABLE_SIZE],
-                             &br) ||
-            !ReadHuffmanCode(kNumBlockLengthCodes,
-                             &block_len_trees[i * HUFFMAN_MAX_TABLE_SIZE],
-                             &br)) {
-          ok = 0;
-          goto End;
-        }
-        block_length[i] = ReadBlockLength(
-            &block_len_trees[i * HUFFMAN_MAX_TABLE_SIZE], &br);
-        block_type_rb_index[i] = 1;
-      }
-    }
-
-    BROTLI_LOG_UINT(num_block_types[0]);
-    BROTLI_LOG_UINT(num_block_types[1]);
-    BROTLI_LOG_UINT(num_block_types[2]);
-    BROTLI_LOG_UINT(block_length[0]);
-    BROTLI_LOG_UINT(block_length[1]);
-    BROTLI_LOG_UINT(block_length[2]);
-
-    if (!BrotliReadMoreInput(&br)) {
-      printf("[BrotliDecompress] Unexpected end of input.\n");
-      ok = 0;
-      goto End;
-    }
-    distance_postfix_bits = (int)BrotliReadBits(&br, 2);
-    num_direct_distance_codes = NUM_DISTANCE_SHORT_CODES +
-        ((int)BrotliReadBits(&br, 4) << distance_postfix_bits);
-    distance_postfix_mask = (1 << distance_postfix_bits) - 1;
-    num_distance_codes = (num_direct_distance_codes +
-                          (48 << distance_postfix_bits));
-    context_modes = (uint8_t*)malloc((size_t)num_block_types[0]);
-    if (context_modes == 0) {
-      ok = 0;
-      goto End;
-    }
-    for (i = 0; i < num_block_types[0]; ++i) {
-      context_modes[i] = (uint8_t)(BrotliReadBits(&br, 2) << 1);
-      BROTLI_LOG_ARRAY_INDEX(context_modes, i);
-    }
-    BROTLI_LOG_UINT(num_direct_distance_codes);
-    BROTLI_LOG_UINT(distance_postfix_bits);
-
-    if (!DecodeContextMap(num_block_types[0] << kLiteralContextBits,
-                          &num_literal_htrees, &context_map, &br) ||
-        !DecodeContextMap(num_block_types[2] << kDistanceContextBits,
-                          &num_dist_htrees, &dist_context_map, &br)) {
-      ok = 0;
-      goto End;
-    }
-
-    HuffmanTreeGroupInit(&hgroup[0], kNumLiteralCodes, num_literal_htrees);
-    HuffmanTreeGroupInit(&hgroup[1], kNumInsertAndCopyCodes,
-                         num_block_types[1]);
-    HuffmanTreeGroupInit(&hgroup[2], num_distance_codes, num_dist_htrees);
-
-    for (i = 0; i < 3; ++i) {
-      if (!HuffmanTreeGroupDecode(&hgroup[i], &br)) {
-        ok = 0;
-        goto End;
-      }
-    }
-
-    context_map_slice = context_map;
-    dist_context_map_slice = dist_context_map;
-    context_mode = context_modes[block_type[0]];
-    context_lookup_offset1 = kContextLookupOffsets[context_mode];
-    context_lookup_offset2 = kContextLookupOffsets[context_mode + 1];
-    htree_command = hgroup[1].htrees[0];
+  s->pos = pos;
+  s->loop_counter = i;
+  return result;
+}
 
-    while (meta_block_remaining_len > 0) {
-      int cmd_code;
-      int range_idx;
-      int insert_code;
-      int copy_code;
-      int insert_length;
-      int copy_length;
-      int distance_code;
-      int distance;
-      uint8_t context;
-      int j;
-      const uint8_t* copy_src;
-      uint8_t* copy_dst;
-      if (!BrotliReadMoreInput(&br)) {
-        printf("[BrotliDecompress] Unexpected end of input.\n");
-        ok = 0;
-        goto End;
-      }
-      if (block_length[1] == 0) {
-        DecodeBlockType(num_block_types[1],
-                        block_type_trees, 1, block_type, block_type_rb,
-                        block_type_rb_index, &br);
-        block_length[1] = ReadBlockLength(
-            &block_len_trees[HUFFMAN_MAX_TABLE_SIZE], &br);
-        htree_command = hgroup[1].htrees[block_type[1]];
-      }
-      --block_length[1];
-      cmd_code = ReadSymbol(htree_command, &br);
-      range_idx = cmd_code >> 6;
-      if (range_idx >= 2) {
-        range_idx -= 2;
-        distance_code = -1;
-      } else {
-        distance_code = 0;
-      }
-      insert_code = kInsertRangeLut[range_idx] + ((cmd_code >> 3) & 7);
-      copy_code = kCopyRangeLut[range_idx] + (cmd_code & 7);
-      insert_length = kInsertLengthPrefixCode[insert_code].offset +
-          (int)BrotliReadBits(&br, kInsertLengthPrefixCode[insert_code].nbits);
-      copy_length = kCopyLengthPrefixCode[copy_code].offset +
-          (int)BrotliReadBits(&br, kCopyLengthPrefixCode[copy_code].nbits);
-      BROTLI_LOG_UINT(insert_length);
-      BROTLI_LOG_UINT(copy_length);
-      BROTLI_LOG_UINT(distance_code);
-      for (j = 0; j < insert_length; ++j) {
-        if (!BrotliReadMoreInput(&br)) {
-          printf("[BrotliDecompress] Unexpected end of input.\n");
-          ok = 0;
-          goto End;
-        }
-        if (block_length[0] == 0) {
-          DecodeBlockType(num_block_types[0],
-                          block_type_trees, 0, block_type, block_type_rb,
-                          block_type_rb_index, &br);
-          block_length[0] = ReadBlockLength(block_len_trees, &br);
-          context_offset = block_type[0] << kLiteralContextBits;
-          context_map_slice = context_map + context_offset;
-          context_mode = context_modes[block_type[0]];
-          context_lookup_offset1 = kContextLookupOffsets[context_mode];
-          context_lookup_offset2 = kContextLookupOffsets[context_mode + 1];
-        }
-        context = (kContextLookup[context_lookup_offset1 + prev_byte1] |
-                   kContextLookup[context_lookup_offset2 + prev_byte2]);
-        BROTLI_LOG_UINT(context);
-        literal_htree_index = context_map_slice[context];
-        --block_length[0];
-        prev_byte2 = prev_byte1;
-        prev_byte1 = (uint8_t)ReadSymbol(hgroup[0].htrees[literal_htree_index],
-                                         &br);
-        ringbuffer[pos & ringbuffer_mask] = prev_byte1;
-        BROTLI_LOG_UINT(literal_htree_index);
-        BROTLI_LOG_ARRAY_INDEX(ringbuffer, pos & ringbuffer_mask);
-        if ((pos & ringbuffer_mask) == ringbuffer_mask) {
-          if (BrotliWrite(output, ringbuffer, (size_t)ringbuffer_size) < 0) {
-            ok = 0;
-            goto End;
-          }
-        }
-        ++pos;
-      }
-      meta_block_remaining_len -= insert_length;
-      if (meta_block_remaining_len <= 0) break;
-
-      if (distance_code < 0) {
-        uint8_t context;
-        if (!BrotliReadMoreInput(&br)) {
-          printf("[BrotliDecompress] Unexpected end of input.\n");
-          ok = 0;
-          goto End;
-        }
-        if (block_length[2] == 0) {
-          DecodeBlockType(num_block_types[2],
-                          block_type_trees, 2, block_type, block_type_rb,
-                          block_type_rb_index, &br);
-          block_length[2] = ReadBlockLength(
-              &block_len_trees[2 * HUFFMAN_MAX_TABLE_SIZE], &br);
-          dist_context_offset = block_type[2] << kDistanceContextBits;
-          dist_context_map_slice = dist_context_map + dist_context_offset;
-        }
-        --block_length[2];
-        context = (uint8_t)(copy_length > 4 ? 3 : copy_length - 2);
-        dist_htree_index = dist_context_map_slice[context];
-        distance_code = ReadSymbol(hgroup[2].htrees[dist_htree_index], &br);
-        if (distance_code >= num_direct_distance_codes) {
-          int nbits;
-          int postfix;
-          int offset;
-          distance_code -= num_direct_distance_codes;
-          postfix = distance_code & distance_postfix_mask;
-          distance_code >>= distance_postfix_bits;
-          nbits = (distance_code >> 1) + 1;
-          offset = ((2 + (distance_code & 1)) << nbits) - 4;
-          distance_code = num_direct_distance_codes +
-              ((offset + (int)BrotliReadBits(&br, nbits)) <<
-               distance_postfix_bits) + postfix;
-        }
-      }
-
-      /* Convert the distance code to the actual distance by possibly looking */
-      /* up past distnaces from the ringbuffer. */
-      distance = TranslateShortCodes(distance_code, dist_rb, dist_rb_idx);
-      if (distance < 0) {
-        ok = 0;
-        goto End;
-      }
-      BROTLI_LOG_UINT(distance);
-
-      if (pos < max_backward_distance &&
-          max_distance != max_backward_distance) {
-        max_distance = pos;
-      } else {
-        max_distance = max_backward_distance;
-      }
-
-      copy_dst = &ringbuffer[pos & ringbuffer_mask];
-
-      if (distance > max_distance) {
-        if (copy_length >= kMinDictionaryWordLength &&
-            copy_length <= kMaxDictionaryWordLength) {
-          int offset = kBrotliDictionaryOffsetsByLength[copy_length];
-          int word_id = distance - max_distance - 1;
-          int shift = kBrotliDictionarySizeBitsByLength[copy_length];
-          int mask = (1 << shift) - 1;
-          int word_idx = word_id & mask;
-          int transform_idx = word_id >> shift;
-          offset += word_idx * copy_length;
-          if (transform_idx < kNumTransforms) {
-            const uint8_t* word = &kBrotliDictionary[offset];
-            int len = TransformDictionaryWord(
-                copy_dst, word, copy_length, transform_idx);
-            copy_dst += len;
-            pos += len;
-            meta_block_remaining_len -= len;
-            if (copy_dst >= ringbuffer_end) {
-              if (BrotliWrite(output, ringbuffer,
-                              (size_t)ringbuffer_size) < 0) {
-                ok = 0;
-                goto End;
-              }
-              memcpy(ringbuffer, ringbuffer_end,
-                     (size_t)(copy_dst - ringbuffer_end));
-            }
-          } else {
-            printf("Invalid backward reference. pos: %d distance: %d "
-                   "len: %d bytes left: %d\n", pos, distance, copy_length,
-                   meta_block_remaining_len);
-            ok = 0;
-            goto End;
-          }
-        } else {
-          printf("Invalid backward reference. pos: %d distance: %d "
-                 "len: %d bytes left: %d\n", pos, distance, copy_length,
-                 meta_block_remaining_len);
-          ok = 0;
-          goto End;
-        }
-      } else {
-        if (distance_code > 0) {
-          dist_rb[dist_rb_idx & 3] = distance;
-          ++dist_rb_idx;
-        }
-
-        if (copy_length > meta_block_remaining_len) {
-          printf("Invalid backward reference. pos: %d distance: %d "
-                 "len: %d bytes left: %d\n", pos, distance, copy_length,
-                 meta_block_remaining_len);
-          ok = 0;
-          goto End;
-        }
-
-        copy_src = &ringbuffer[(pos - distance) & ringbuffer_mask];
-
-#if (defined(__x86_64__) || defined(_M_X64))
-        if (copy_src + copy_length <= ringbuffer_end &&
-            copy_dst + copy_length < ringbuffer_end) {
-          if (copy_length <= 16 && distance >= 8) {
-            UNALIGNED_COPY64(copy_dst, copy_src);
-            UNALIGNED_COPY64(copy_dst + 8, copy_src + 8);
-          } else {
-            IncrementalCopyFastPath(copy_dst, copy_src, copy_length);
-          }
-          pos += copy_length;
-          meta_block_remaining_len -= copy_length;
-          copy_length = 0;
-        }
-#endif
-
-        for (j = 0; j < copy_length; ++j) {
-          ringbuffer[pos & ringbuffer_mask] =
-              ringbuffer[(pos - distance) & ringbuffer_mask];
-          if ((pos & ringbuffer_mask) == ringbuffer_mask) {
-            if (BrotliWrite(output, ringbuffer, (size_t)ringbuffer_size) < 0) {
-              ok = 0;
-              goto End;
-            }
-          }
-          ++pos;
-          --meta_block_remaining_len;
-        }
-      }
-
-      /* When we get here, we must have inserted at least one literal and */
-      /* made a copy of at least length two, therefore accessing the last 2 */
-      /* bytes is valid. */
-      prev_byte1 = ringbuffer[(pos - 1) & ringbuffer_mask];
-      prev_byte2 = ringbuffer[(pos - 2) & ringbuffer_mask];
-    }
-
-    /* Protect pos from overflow, wrap it around at every GB of input data */
-    pos &= 0x3fffffff;
-
- End:
-    if (context_modes != 0) {
-      free(context_modes);
-    }
-    if (context_map != 0) {
-      free(context_map);
-    }
-    if (dist_context_map != 0) {
-      free(dist_context_map);
-    }
-    for (i = 0; i < 3; ++i) {
-      HuffmanTreeGroupRelease(&hgroup[i]);
-    }
-  }
-
-  if (ringbuffer != 0) {
-    if (BrotliWrite(output, ringbuffer, (size_t)(pos & ringbuffer_mask)) < 0) {
-      ok = 0;
-    }
-    free(ringbuffer);
-  }
-  if (block_type_trees != 0) {
-    free(block_type_trees);
-  }
-  if (block_len_trees != 0) {
-    free(block_len_trees);
-  }
-  return ok;
+void BrotliSetCustomDictionary(
+    size_t size, const uint8_t* dict, BrotliState* s) {
+  s->custom_dict = dict;
+  s->custom_dict_size = (int) size;
 }
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    /* extern "C" */
 #endif
--- a/modules/brotli/dec/decode.h
+++ b/modules/brotli/dec/decode.h
@@ -6,50 +6,155 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   API for Brotli decompression
-*/
+/* API for Brotli decompression */
 
 #ifndef BROTLI_DEC_DECODE_H_
 #define BROTLI_DEC_DECODE_H_
 
+#include "./state.h"
 #include "./streams.h"
 #include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
+typedef enum {
+  /* Decoding error, e.g. corrupt input or no memory */
+  BROTLI_RESULT_ERROR = 0,
+  /* Successfully completely done */
+  BROTLI_RESULT_SUCCESS = 1,
+  /* Partially done, but must be called again with more input */
+  BROTLI_RESULT_NEEDS_MORE_INPUT = 2,
+  /* Partially done, but must be called again with more output */
+  BROTLI_RESULT_NEEDS_MORE_OUTPUT = 3
+} BrotliResult;
+
+/* BROTLI_FAILURE macro unwraps to BROTLI_RESULT_ERROR in non-debug build. */
+/* In debug build it dumps file name, line and pretty function name. */
+#if defined(_MSC_VER) || !defined(BROTLI_DEBUG)
+#define BROTLI_FAILURE() BROTLI_RESULT_ERROR
+#else
+#define BROTLI_FAILURE() \
+    BrotliFailure(__FILE__, __LINE__, __PRETTY_FUNCTION__)
+static inline BrotliResult BrotliFailure(const char *f, int l, const char *fn) {
+  fprintf(stderr, "ERROR at %s:%d (%s)\n", f, l, fn);
+  fflush(stderr);
+  return BROTLI_RESULT_ERROR;
+}
+#endif
+
 /* Sets *decoded_size to the decompressed size of the given encoded stream. */
 /* This function only works if the encoded buffer has a single meta block, */
 /* or if it has two meta-blocks, where the first is uncompressed and the */
 /* second is empty. */
 /* Returns 1 on success, 0 on failure. */
 int BrotliDecompressedSize(size_t encoded_size,
                            const uint8_t* encoded_buffer,
                            size_t* decoded_size);
 
 /* Decompresses the data in encoded_buffer into decoded_buffer, and sets */
 /* *decoded_size to the decompressed length. */
 /* Returns 0 if there was either a bit stream error or memory allocation */
 /* error, and 1 otherwise. */
 /* If decoded size is zero, returns 1 and keeps decoded_buffer unchanged. */
-int BrotliDecompressBuffer(size_t encoded_size,
-                           const uint8_t* encoded_buffer,
-                           size_t* decoded_size,
-                           uint8_t* decoded_buffer);
+BrotliResult BrotliDecompressBuffer(size_t encoded_size,
+                                    const uint8_t* encoded_buffer,
+                                    size_t* decoded_size,
+                                    uint8_t* decoded_buffer);
 
 /* Same as above, but uses the specified input and output callbacks instead */
 /* of reading from and writing to pre-allocated memory buffers. */
-int BrotliDecompress(BrotliInput input, BrotliOutput output);
+BrotliResult BrotliDecompress(BrotliInput input, BrotliOutput output);
+
+/* Same as above, but supports the caller to call the decoder repeatedly with
+   partial data to support streaming. The state must be initialized with
+   BrotliStateInit and reused with every call for the same stream.
+   Return values:
+   0: failure.
+   1: success, and done.
+   2: success so far, end not reached so should call again with more input.
+   The finish parameter is used as follows, for a series of calls with the
+   same state:
+   0: Every call except the last one must be called with finish set to 0. The
+      last call may have finish set to either 0 or 1. Only if finish is 0, can
+      the function return 2. It may also return 0 or 1, in that case no more
+      calls (even with finish 1) may be made.
+   1: Only the last call may have finish set to 1. It's ok to give empty input
+      if all input was already given to previous calls. It is also ok to have
+      only one single call in total, with finish 1, and with all input
+      available immediately. That matches the non-streaming case. If finish is
+      1, the function can only return 0 or 1, never 2. After a finish, no more
+      calls may be done.
+   After everything is done, the state must be cleaned with BrotliStateCleanup
+   to free allocated resources.
+   The given BrotliOutput must always accept all output and make enough space,
+   it returning a smaller value than the amount of bytes to write always results
+   in an error.
+*/
+BrotliResult BrotliDecompressStreaming(BrotliInput input, BrotliOutput output,
+                                       int finish, BrotliState* s);
+
+/* Same as above, but with memory buffers.
+   Must be called with an allocated input buffer in *next_in and an allocated
+   output buffer in *next_out. The values *available_in and *available_out
+   must specify the allocated size in *next_in and *next_out respectively.
+   The value *total_out must be 0 initially, and will be summed with the
+   amount of output bytes written after each call, so that at the end it
+   gives the complete decoded size.
+   After each call, *available_in will be decremented by the amount of input
+   bytes consumed, and the *next_in pointer will be incremented by that amount.
+   Similarly, *available_out will be decremented by the amount of output
+   bytes written, and the *next_out pointer will be incremented by that
+   amount.
+
+   The input may be partial. With each next function call, *next_in and
+   *available_in must be updated to point to a next part of the compressed
+   input. The current implementation will always consume all input unless
+   an error occurs, so normally *available_in will always be 0 after
+   calling this function and the next adjacent part of input is desired.
+
+   In the current implementation, the function requires that there is enough
+   output buffer size to write all currently processed input, so
+   *available_out must be large enough. Since the function updates *next_out
+   each time, as long as the output buffer is large enough you can keep
+   reusing this variable. It is also possible to update *next_out and
+   *available_out yourself before a next call, e.g. to point to a new larger
+   buffer.
+*/
+BrotliResult BrotliDecompressBufferStreaming(size_t* available_in,
+                                             const uint8_t** next_in,
+                                             int finish,
+                                             size_t* available_out,
+                                             uint8_t** next_out,
+                                             size_t* total_out,
+                                             BrotliState* s);
+
+/* Fills the new state with a dictionary for LZ77, warming up the ringbuffer,
+   e.g. for custom static dictionaries for data formats.
+   Not to be confused with the built-in transformable dictionary of Brotli.
+   The dictionary must exist in memory until decoding is done and is owned by
+   the caller. To use:
+   -initialize state with BrotliStateInit
+   -use BrotliSetCustomDictionary
+   -use BrotliDecompressBufferStreaming
+   -clean up with BrotliStateCleanup
+*/
+void BrotliSetCustomDictionary(
+    size_t size, const uint8_t* dict, BrotliState* s);
+
+/* Escalate internal functions visibility; for testing purposes only. */
+void InverseMoveToFrontTransformForTesting(uint8_t* v, int l, BrotliState* s);
 
 #if defined(__cplusplus) || defined(c_plusplus)
-}    /* extern "C" */
+} /* extern "C" */
 #endif
 
 #endif  /* BROTLI_DEC_DECODE_H_ */
--- a/modules/brotli/dec/dictionary.h
+++ b/modules/brotli/dec/dictionary.h
@@ -6,19 +6,19 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Collection of static dictionary words.
-*/
+/* Collection of static dictionary words. */
 
 #ifndef BROTLI_DEC_DICTIONARY_H_
 #define BROTLI_DEC_DICTIONARY_H_
 
 #include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
@@ -9473,17 +9473,17 @@ static const uint8_t kBrotliDictionary[]
 };
 
 static const int kBrotliDictionaryOffsetsByLength[] = {
      0,     0,     0,     0,     0,  4096,  9216, 21504, 35840, 44032,
  53248, 63488, 74752, 87040, 93696, 100864, 104704, 106752, 108928, 113536,
  115968, 118528, 119872, 121280, 122016,
 };
 
-static const int kBrotliDictionarySizeBitsByLength[] = {
+static const int8_t kBrotliDictionarySizeBitsByLength[] = {
   0,  0,  0,  0, 10, 10, 11, 11, 10, 10,
  10, 10, 10,  9,  9,  8,  7,  7,  8,  7,
   7,  6,  6,  5,  5,
 };
 
 static const int kMinDictionaryWordLength = 4;
 static const int kMaxDictionaryWordLength = 24;
 
--- a/modules/brotli/dec/huffman.c
+++ b/modules/brotli/dec/huffman.c
@@ -6,159 +6,320 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
-
-   Utilities for building Huffman decoding tables.
 */
 
-#include <assert.h>
+/* Utilities for building Huffman decoding tables. */
+
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
 #include "./huffman.h"
-#include "./safe_malloc.h"
+#include "./port.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
-#define MAX_LENGTH 15
-
 /* Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the
    bit-wise reversal of the len least significant bits of key. */
-static BROTLI_INLINE int GetNextKey(int key, int len) {
-  int step = 1 << (len - 1);
+static BROTLI_INLINE uint32_t GetNextKey(uint32_t key, int len) {
+#ifdef BROTLI_RBIT
+  return BROTLI_RBIT(BROTLI_RBIT(key) + (1 << (8 * sizeof(unsigned) - len)));
+#else
+  unsigned step = (unsigned)(1 << (len - 1));
   while (key & step) {
     step >>= 1;
   }
   return (key & (step - 1)) + step;
+#endif
 }
 
 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
 /* Assumes that end is an integer multiple of step */
 static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
                                          int step, int end,
                                          HuffmanCode code) {
   do {
     end -= step;
     table[end] = code;
   } while (end > 0);
 }
 
 /* Returns the table width of the next 2nd level table. count is the histogram
    of bit lengths for the remaining symbols, len is the code length of the next
    processed symbol */
-static BROTLI_INLINE int NextTableBitSize(const int* const count,
+static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count,
                                           int len, int root_bits) {
   int left = 1 << (len - root_bits);
-  while (len < MAX_LENGTH) {
+  while (len < BROTLI_HUFFMAN_MAX_CODE_LENGTH) {
     left -= count[len];
     if (left <= 0) break;
     ++len;
     left <<= 1;
   }
   return len - root_bits;
 }
 
+
+void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
+                                        const uint8_t* const code_lengths,
+                                        uint16_t *count) {
+  HuffmanCode code;    /* current table entry */
+  int symbol;          /* symbol index in original or sorted table */
+  unsigned key;        /* reversed prefix code */
+  int step;            /* step size to replicate values in current table */
+  int table_size;      /* size of current table */
+  int sorted[18];      /* symbols sorted by code length */
+  /* offsets in sorted table for each length */
+  int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1];
+  int bits;
+  int bits_count;
+
+  /* generate offsets into sorted symbol table by code length */
+  symbol = -1;
+  bits = 1;
+  BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
+    symbol += count[bits];
+    offset[bits] = symbol;
+    bits++;
+  });
+  offset[0] = 17;
+
+  /* sort symbols by length, by symbol order within each length */
+  symbol = 18;
+  do {
+    BROTLI_REPEAT(6, {
+      symbol--;
+      sorted[offset[code_lengths[symbol]]--] = symbol;
+    });
+  } while (symbol != 0);
+
+  table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
+
+  /* special case code with only one value */
+  if (offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH] == 0) {
+    code.bits = 0;
+    code.value = (uint16_t)sorted[0];
+    for (key = 0; key < table_size; ++key) {
+      table[key] = code;
+    }
+    return;
+  }
+
+  /* fill in table */
+  key = 0;
+  symbol = 0;
+  bits = 1;
+  step = 2;
+  do {
+    code.bits = (uint8_t)bits;
+    for (bits_count = count[bits]; bits_count != 0; --bits_count) {
+      code.value = (uint16_t)sorted[symbol++];
+      ReplicateValue(&table[key], step, table_size, code);
+      key = GetNextKey(key, bits);
+    }
+    step <<= 1;
+  } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
+}
+
 int BrotliBuildHuffmanTable(HuffmanCode* root_table,
                             int root_bits,
-                            const uint8_t* const code_lengths,
-                            int code_lengths_size) {
+                            const uint16_t* const symbol_lists,
+                            uint16_t *count) {
   HuffmanCode code;    /* current table entry */
   HuffmanCode* table;  /* next available space in table */
   int len;             /* current code length */
   int symbol;          /* symbol index in original or sorted table */
-  int key;             /* reversed prefix code */
+  unsigned key;        /* reversed prefix code */
   int step;            /* step size to replicate values in current table */
-  int low;             /* low bits for current root entry */
-  int mask;            /* mask for low bits */
+  unsigned low;        /* low bits for current root entry */
+  unsigned mask;       /* mask for low bits */
   int table_bits;      /* key length of current table */
   int table_size;      /* size of current table */
   int total_size;      /* sum of root table size and 2nd level table sizes */
-  int* sorted;         /* symbols sorted by code length */
-  int count[MAX_LENGTH + 1] = { 0 };  /* number of codes of each length */
-  int offset[MAX_LENGTH + 1];  /* offsets in sorted table for each length */
-
-  sorted = (int*)malloc((size_t)code_lengths_size * sizeof(*sorted));
-  if (sorted == NULL) {
-    return 0;
-  }
+  int max_length = -1;
+  int bits;
+  int bits_count;
 
-  /* build histogram of code lengths */
-  for (symbol = 0; symbol < code_lengths_size; symbol++) {
-    count[code_lengths[symbol]]++;
-  }
-
-  /* generate offsets into sorted symbol table by code length */
-  offset[1] = 0;
-  for (len = 1; len < MAX_LENGTH; len++) {
-    offset[len + 1] = offset[len] + count[len];
-  }
-
-  /* sort symbols by length, by symbol order within each length */
-  for (symbol = 0; symbol < code_lengths_size; symbol++) {
-    if (code_lengths[symbol] != 0) {
-      sorted[offset[code_lengths[symbol]]++] = symbol;
-    }
-  }
+  while (symbol_lists[max_length] == 0xFFFF) max_length--;
+  max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
 
   table = root_table;
   table_bits = root_bits;
   table_size = 1 << table_bits;
   total_size = table_size;
 
-  /* special case code with only one value */
-  if (offset[MAX_LENGTH] == 1) {
-    code.bits = 0;
-    code.value = (uint16_t)sorted[0];
-    for (key = 0; key < total_size; ++key) {
-      table[key] = code;
+  /* fill in root table */
+  /* let's reduce the table size to a smaller size if possible, and */
+  /* create the repetitions by memcpy if possible in the coming loop */
+  if (table_bits > max_length) {
+    table_bits = max_length;
+    table_size = 1 << table_bits;
+  }
+  key = 0;
+  bits = 1;
+  step = 2;
+  do {
+    code.bits = (uint8_t)bits;
+    symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
+    for (bits_count = count[bits]; bits_count != 0; --bits_count) {
+      symbol = symbol_lists[symbol];
+      code.value = (uint16_t)symbol;
+      ReplicateValue(&table[key], step, table_size, code);
+      key = GetNextKey(key, bits);
     }
-    free(sorted);
-    return total_size;
-  }
+    step <<= 1;
+  } while (++bits <= table_bits);
 
-  /* fill in root table */
-  key = 0;
-  symbol = 0;
-  for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
-    for (; count[len] > 0; --count[len]) {
-      code.bits = (uint8_t)(len);
-      code.value = (uint16_t)sorted[symbol++];
-      ReplicateValue(&table[key], step, table_size, code);
-      key = GetNextKey(key, len);
-    }
+  /* if root_bits != table_bits we only created one fraction of the */
+  /* table, and we need to replicate it now. */
+  while (total_size != table_size) {
+    memcpy(&table[table_size], &table[0],
+           (size_t)table_size * sizeof(table[0]));
+    table_size <<= 1;
   }
 
   /* fill in 2nd level tables and add pointers to root table */
-  mask = total_size - 1;
-  low = -1;
-  for (len = root_bits + 1, step = 2; len <= MAX_LENGTH; ++len, step <<= 1) {
-    for (; count[len] > 0; --count[len]) {
+  mask = (unsigned)(total_size - 1);
+  low = (unsigned)-1;
+  for (len = root_bits + 1, step = 2; len <= max_length; ++len, step <<= 1) {
+    symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
+    for (; count[len] != 0; --count[len]) {
       if ((key & mask) != low) {
         table += table_size;
         table_bits = NextTableBitSize(count, len, root_bits);
         table_size = 1 << table_bits;
         total_size += table_size;
         low = key & mask;
         root_table[low].bits = (uint8_t)(table_bits + root_bits);
-        root_table[low].value = (uint16_t)((table - root_table) - low);
+        root_table[low].value = (uint16_t)(
+            ((size_t)(table - root_table)) - low);
       }
       code.bits = (uint8_t)(len - root_bits);
-      code.value = (uint16_t)sorted[symbol++];
+      symbol = symbol_lists[symbol];
+      code.value = (uint16_t)symbol;
       ReplicateValue(&table[key >> root_bits], step, table_size, code);
       key = GetNextKey(key, len);
     }
   }
+  return total_size;
+}
 
-  free(sorted);
-  return total_size;
+int BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
+                                  int root_bits,
+                                  uint16_t *val,
+                                  uint32_t num_symbols) {
+  int table_size = 1;
+  const int goal_size = 1 << root_bits;
+  switch (num_symbols) {
+    case 0:
+      table[0].bits = 0;
+      table[0].value = val[0];
+      break;
+    case 1:
+      table[0].bits = 1;
+      table[1].bits = 1;
+      if (val[1] > val[0]) {
+        table[0].value = val[0];
+        table[1].value = val[1];
+      } else {
+        table[0].value = val[1];
+        table[1].value = val[0];
+      }
+      table_size = 2;
+      break;
+    case 2:
+      table[0].bits = 1;
+      table[0].value = val[0];
+      table[2].bits = 1;
+      table[2].value = val[0];
+      if (val[2] > val[1]) {
+        table[1].value = val[1];
+        table[3].value = val[2];
+      } else {
+        table[1].value = val[2];
+        table[3].value = val[1];
+      }
+      table[1].bits = 2;
+      table[3].bits = 2;
+      table_size = 4;
+      break;
+    case 3:
+      {
+        int i, k;
+        for (i = 0; i < 3; ++i) {
+          for (k = i + 1; k < 4; ++k) {
+            if (val[k] < val[i]) {
+              uint16_t t = val[k];
+              val[k] = val[i];
+              val[i] = t;
+            }
+          }
+        }
+        for (i = 0; i < 4; ++i) {
+          table[i].bits = 2;
+        }
+        table[0].value = val[0];
+        table[2].value = val[1];
+        table[1].value = val[2];
+        table[3].value = val[3];
+        table_size = 4;
+      }
+      break;
+    case 4:
+      {
+        int i;
+        if (val[3] < val[2]) {
+          uint16_t t = val[3];
+          val[3] = val[2];
+          val[2] = t;
+        }
+        for (i = 0; i < 7; ++i) {
+          table[i].value = val[0];
+          table[i].bits = (uint8_t)(1 + (i & 1));
+        }
+        table[1].value = val[1];
+        table[3].value = val[2];
+        table[5].value = val[1];
+        table[7].value = val[3];
+        table[3].bits = 3;
+        table[7].bits = 3;
+        table_size = 8;
+      }
+      break;
+  }
+  while (table_size != goal_size) {
+    memcpy(&table[table_size], &table[0],
+           (size_t)table_size * sizeof(table[0]));
+    table_size <<= 1;
+  }
+  return goal_size;
+}
+
+void BrotliHuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size,
+                                int ntrees) {
+  /* Pack two mallocs into one */
+  const size_t code_size =
+      sizeof(HuffmanCode) * (size_t)(ntrees * BROTLI_HUFFMAN_MAX_TABLE_SIZE);
+  const size_t htree_size = sizeof(HuffmanCode*) * (size_t)ntrees;
+  char *p = (char*)malloc(code_size + htree_size);
+  group->alphabet_size = (int16_t)alphabet_size;
+  group->num_htrees = (int16_t)ntrees;
+  group->codes = (HuffmanCode*)p;
+  group->htrees = (HuffmanCode**)(p + code_size);
+}
+
+void BrotliHuffmanTreeGroupRelease(HuffmanTreeGroup* group) {
+  if (group->codes) {
+    free(group->codes);
+  }
 }
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    /* extern "C" */
 #endif
--- a/modules/brotli/dec/huffman.h
+++ b/modules/brotli/dec/huffman.h
@@ -6,39 +6,72 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Utilities for building Huffman decoding tables.
-*/
+/* Utilities for building Huffman decoding tables. */
 
 #ifndef BROTLI_DEC_HUFFMAN_H_
 #define BROTLI_DEC_HUFFMAN_H_
 
-#include <assert.h>
 #include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
+#define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15
+
+/* For current format this constant equals to kNumInsertAndCopyCodes */
+#define BROTLI_HUFFMAN_MAX_CODE_LENGTHS_SIZE 704
+
+/* Maximum possible Huffman table size for an alphabet size of 704, max code
+ * length 15 and root table bits 8. */
+#define BROTLI_HUFFMAN_MAX_TABLE_SIZE 1080
+
+#define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5
+
 typedef struct {
   uint8_t bits;     /* number of bits used for this symbol */
   uint16_t value;   /* symbol value or table offset */
 } HuffmanCode;
 
+
 /* Builds Huffman lookup table assuming code lengths are in symbol order. */
-/* Returns false in case of error (invalid tree or memory error). */
+void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,
+                                        const uint8_t* const code_lengths,
+                                        uint16_t *count);
+
+/* Builds Huffman lookup table assuming code lengths are in symbol order. */
+/* Returns size of resulting table. */
 int BrotliBuildHuffmanTable(HuffmanCode* root_table,
                             int root_bits,
-                            const uint8_t* const code_lengths,
-                            int code_lengths_size);
+                            const uint16_t* const symbol_lists,
+                            uint16_t *count_arg);
+
+int BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
+                                  int root_bits,
+                                  uint16_t *symbols,
+                                  uint32_t num_symbols);
+
+/* Contains a collection of huffman trees with the same alphabet size. */
+typedef struct {
+  HuffmanCode** htrees;
+  HuffmanCode* codes;
+  int16_t alphabet_size;
+  int16_t num_htrees;
+} HuffmanTreeGroup;
+
+void BrotliHuffmanTreeGroupInit(HuffmanTreeGroup* group,
+                                int alphabet_size, int ntrees);
+void BrotliHuffmanTreeGroupRelease(HuffmanTreeGroup* group);
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    /* extern "C" */
 #endif
 
 #endif  /* BROTLI_DEC_HUFFMAN_H_ */
new file mode 100644
--- /dev/null
+++ b/modules/brotli/dec/port.h
@@ -0,0 +1,148 @@
+/* Copyright 2015 Google Inc. All Rights Reserved.
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+   http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+*/
+
+/* Macros for branch prediction. */
+
+#ifndef BROTLI_DEC_PORT_H_
+#define BROTLI_DEC_PORT_H_
+
+#include<assert.h>
+
+/* Compatibility with non-clang compilers. */
+#ifndef __has_builtin
+#define __has_builtin(x) 0
+#endif
+
+#ifndef __has_attribute
+#define __has_attribute(x) 0
+#endif
+
+#ifndef __has_feature
+#define __has_feature(x) 0
+#endif
+
+#define BROTLI_ASAN_BUILD __has_feature(address_sanitizer)
+
+/* Define "PREDICT_TRUE" and "PREDICT_FALSE" macros for capable compilers.
+
+To apply compiler hint, enclose the branching condition into macros, like this:
+
+  if (PREDICT_TRUE(zero == 0)) {
+    // main execution path
+  } else {
+    // compiler should place this code outside of main execution path
+  }
+
+OR:
+
+  if (PREDICT_FALSE(something_rare_or_unexpected_happens)) {
+    // compiler should place this code outside of main execution path
+  }
+
+*/
+#if (__GNUC__ > 2) || (__GNUC__ == 2 && __GNUC_MINOR__ > 95) || \
+    (defined(__llvm__) && __has_builtin(__builtin_expect))
+#define PREDICT_TRUE(x) (__builtin_expect(!!(x), 1))
+#define PREDICT_FALSE(x) (__builtin_expect(x, 0))
+#else
+#define PREDICT_FALSE(x) (x)
+#define PREDICT_TRUE(x) (x)
+#endif
+
+/* IS_CONSTANT macros returns true for compile-time constant expressions. */
+#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ > 0) || \
+    (defined(__llvm__) && __has_builtin(__builtin_constant_p))
+#define IS_CONSTANT(x) __builtin_constant_p(x)
+#else
+#define IS_CONSTANT(x) 0
+#endif
+
+#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ > 0) || \
+    (defined(__llvm__) && __has_attribute(always_inline))
+#define ATTRIBUTE_ALWAYS_INLINE __attribute__ ((always_inline))
+#else
+#define ATTRIBUTE_ALWAYS_INLINE
+#endif
+
+#ifndef _MSC_VER
+#if defined(__cplusplus) || !defined(__STRICT_ANSI__) \
+    || __STDC_VERSION__ >= 199901L
+#define BROTLI_INLINE inline ATTRIBUTE_ALWAYS_INLINE
+#else
+#define BROTLI_INLINE
+#endif
+#else  /* _MSC_VER */
+#define BROTLI_INLINE __forceinline
+#endif  /* _MSC_VER */
+
+#ifdef BROTLI_DECODE_DEBUG
+#define BROTLI_DCHECK(x) assert(x)
+#else
+#define BROTLI_DCHECK(x)
+#endif
+
+#if (defined(__x86_64__) || defined(_M_X64) || defined(__aarch64__) || \
+     defined(__PPC64__))
+#define BROTLI_64_BITS 1
+#else
+#define BROTLI_64_BITS 0
+#endif
+
+#if (defined(__BYTE_ORDER__) && (__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__))
+#define BROTLI_LITTLE_ENDIAN 1
+#elif defined(_WIN32)
+/* Win32 can currently always be assumed to be little endian */
+#define BROTLI_LITTLE_ENDIAN 1
+#else
+#define BROTLI_LITTLE_ENDIAN 0
+#endif
+
+#if (BROTLI_64_BITS && BROTLI_LITTLE_ENDIAN)
+#define BROTLI_64_BITS_LITTLE_ENDIAN 1
+#else
+#define BROTLI_64_BITS_LITTLE_ENDIAN 0
+#endif
+
+#if (__GNUC__ > 3) || (__GNUC__ == 3 && __GNUC_MINOR__ >= 1) || \
+    (defined(__llvm__) && __has_attribute(noinline))
+#define BROTLI_NOINLINE __attribute__ ((noinline))
+#else
+#define BROTLI_NOINLINE
+#endif
+
+#if BROTLI_ASAN_BUILD
+#define BROTLI_NO_ASAN __attribute__((no_sanitize("address"))) BROTLI_NOINLINE
+#else
+#define BROTLI_NO_ASAN
+#endif
+
+#define BROTLI_REPEAT(N, X) { \
+  if ((N & 1) != 0) {X;} \
+  if ((N & 2) != 0) {X; X;} \
+  if ((N & 4) != 0) {X; X; X; X;} \
+}
+
+#if (__GNUC__ > 2) || defined(__llvm__)
+#if (defined(__ARM_ARCH) && (__ARM_ARCH >= 7))
+static BROTLI_INLINE unsigned BrotliRBit(unsigned input) {
+  unsigned output;
+  __asm__("rbit %0, %1\n" : "=r"(output) : "r"(input));
+  return output;
+}
+#define BROTLI_RBIT(x) BrotliRBit(x)
+#endif  /* armv7 */
+#endif  /* gcc || clang */
+
+#endif  /* BROTLI_DEC_PORT_H_ */
--- a/modules/brotli/dec/prefix.h
+++ b/modules/brotli/dec/prefix.h
@@ -6,60 +6,751 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Lookup tables to map prefix codes to value ranges. This is used during
+/* Lookup tables to map prefix codes to value ranges. This is used during
    decoding of the block lengths, literal insertion lengths and copy lengths.
 */
 
 #ifndef BROTLI_DEC_PREFIX_H_
 #define BROTLI_DEC_PREFIX_H_
 
 /* Represents the range of values belonging to a prefix code: */
 /* [offset, offset + 2^nbits) */
 struct PrefixCodeRange {
-  int offset;
-  int nbits;
+  int16_t offset;
+  int8_t nbits;
 };
 
 static const struct PrefixCodeRange kBlockLengthPrefixCode[] = {
   {   1,  2}, {    5,  2}, {  9,   2}, {  13,  2},
   {  17,  3}, {   25,  3}, {  33,  3}, {  41,  3},
   {  49,  4}, {   65,  4}, {  81,  4}, {  97,  4},
   { 113,  5}, {  145,  5}, { 177,  5}, { 209,  5},
   { 241,  6}, {  305,  6}, { 369,  7}, { 497,  8},
   { 753,  9}, { 1265, 10}, {2289, 11}, {4337, 12},
   {8433, 13}, {16625, 24}
 };
 
-static const struct PrefixCodeRange kInsertLengthPrefixCode[] = {
-  {   0,  0}, {   1,  0}, {  2,   0}, {    3,  0},
-  {   4,  0}, {   5,  0}, {  6,   1}, {    8,  1},
-  {  10,  2}, {  14,  2}, { 18,   3}, {   26,  3},
-  {  34,  4}, {  50,  4}, { 66,   5}, {   98,  5},
-  { 130,  6}, { 194,  7}, { 322,  8}, {  578,  9},
-  {1090, 10}, {2114, 12}, {6210, 14}, {22594, 24},
-};
+typedef struct CmdLutElement {
+  uint8_t insert_len_extra_bits;
+  uint8_t copy_len_extra_bits;
+  int8_t distance_code;
+  uint8_t context;
+  uint16_t insert_len_offset;
+  uint16_t copy_len_offset;
+} CmdLutElement;
 
-static const struct PrefixCodeRange kCopyLengthPrefixCode[] = {
-  {  2, 0}, {   3,  0}, {   4,  0}, {   5,  0},
-  {  6, 0}, {   7,  0}, {   8,  0}, {   9,  0},
-  { 10, 1}, {  12,  1}, {  14,  2}, {  18,  2},
-  { 22, 3}, {  30,  3}, {  38,  4}, {  54,  4},
-  { 70, 5}, { 102,  5}, { 134,  6}, { 198,  7},
-  {326, 8}, { 582,  9}, {1094, 10}, {2118, 24},
-};
-
-static const int kInsertRangeLut[9] = {
-  0, 0, 8, 8, 0, 16, 8, 16, 16,
-};
-
-static const int kCopyRangeLut[9] = {
-  0, 8, 0, 8, 16, 0, 16, 8, 16,
+static const CmdLutElement kCmdLut[704] = {
+  { 0x00, 0x00, 0, 0x00, 0x0000, 0x0002 },
+  { 0x00, 0x00, 0, 0x01, 0x0000, 0x0003 },
+  { 0x00, 0x00, 0, 0x02, 0x0000, 0x0004 },
+  { 0x00, 0x00, 0, 0x03, 0x0000, 0x0005 },
+  { 0x00, 0x00, 0, 0x03, 0x0000, 0x0006 },
+  { 0x00, 0x00, 0, 0x03, 0x0000, 0x0007 },
+  { 0x00, 0x00, 0, 0x03, 0x0000, 0x0008 },
+  { 0x00, 0x00, 0, 0x03, 0x0000, 0x0009 },
+  { 0x00, 0x00, 0, 0x00, 0x0001, 0x0002 },
+  { 0x00, 0x00, 0, 0x01, 0x0001, 0x0003 },
+  { 0x00, 0x00, 0, 0x02, 0x0001, 0x0004 },
+  { 0x00, 0x00, 0, 0x03, 0x0001, 0x0005 },
+  { 0x00, 0x00, 0, 0x03, 0x0001, 0x0006 },
+  { 0x00, 0x00, 0, 0x03, 0x0001, 0x0007 },
+  { 0x00, 0x00, 0, 0x03, 0x0001, 0x0008 },
+  { 0x00, 0x00, 0, 0x03, 0x0001, 0x0009 },
+  { 0x00, 0x00, 0, 0x00, 0x0002, 0x0002 },
+  { 0x00, 0x00, 0, 0x01, 0x0002, 0x0003 },
+  { 0x00, 0x00, 0, 0x02, 0x0002, 0x0004 },
+  { 0x00, 0x00, 0, 0x03, 0x0002, 0x0005 },
+  { 0x00, 0x00, 0, 0x03, 0x0002, 0x0006 },
+  { 0x00, 0x00, 0, 0x03, 0x0002, 0x0007 },
+  { 0x00, 0x00, 0, 0x03, 0x0002, 0x0008 },
+  { 0x00, 0x00, 0, 0x03, 0x0002, 0x0009 },
+  { 0x00, 0x00, 0, 0x00, 0x0003, 0x0002 },
+  { 0x00, 0x00, 0, 0x01, 0x0003, 0x0003 },
+  { 0x00, 0x00, 0, 0x02, 0x0003, 0x0004 },
+  { 0x00, 0x00, 0, 0x03, 0x0003, 0x0005 },
+  { 0x00, 0x00, 0, 0x03, 0x0003, 0x0006 },
+  { 0x00, 0x00, 0, 0x03, 0x0003, 0x0007 },
+  { 0x00, 0x00, 0, 0x03, 0x0003, 0x0008 },
+  { 0x00, 0x00, 0, 0x03, 0x0003, 0x0009 },
+  { 0x00, 0x00, 0, 0x00, 0x0004, 0x0002 },
+  { 0x00, 0x00, 0, 0x01, 0x0004, 0x0003 },
+  { 0x00, 0x00, 0, 0x02, 0x0004, 0x0004 },
+  { 0x00, 0x00, 0, 0x03, 0x0004, 0x0005 },
+  { 0x00, 0x00, 0, 0x03, 0x0004, 0x0006 },
+  { 0x00, 0x00, 0, 0x03, 0x0004, 0x0007 },
+  { 0x00, 0x00, 0, 0x03, 0x0004, 0x0008 },
+  { 0x00, 0x00, 0, 0x03, 0x0004, 0x0009 },
+  { 0x00, 0x00, 0, 0x00, 0x0005, 0x0002 },
+  { 0x00, 0x00, 0, 0x01, 0x0005, 0x0003 },
+  { 0x00, 0x00, 0, 0x02, 0x0005, 0x0004 },
+  { 0x00, 0x00, 0, 0x03, 0x0005, 0x0005 },
+  { 0x00, 0x00, 0, 0x03, 0x0005, 0x0006 },
+  { 0x00, 0x00, 0, 0x03, 0x0005, 0x0007 },
+  { 0x00, 0x00, 0, 0x03, 0x0005, 0x0008 },
+  { 0x00, 0x00, 0, 0x03, 0x0005, 0x0009 },
+  { 0x01, 0x00, 0, 0x00, 0x0006, 0x0002 },
+  { 0x01, 0x00, 0, 0x01, 0x0006, 0x0003 },
+  { 0x01, 0x00, 0, 0x02, 0x0006, 0x0004 },
+  { 0x01, 0x00, 0, 0x03, 0x0006, 0x0005 },
+  { 0x01, 0x00, 0, 0x03, 0x0006, 0x0006 },
+  { 0x01, 0x00, 0, 0x03, 0x0006, 0x0007 },
+  { 0x01, 0x00, 0, 0x03, 0x0006, 0x0008 },
+  { 0x01, 0x00, 0, 0x03, 0x0006, 0x0009 },
+  { 0x01, 0x00, 0, 0x00, 0x0008, 0x0002 },
+  { 0x01, 0x00, 0, 0x01, 0x0008, 0x0003 },
+  { 0x01, 0x00, 0, 0x02, 0x0008, 0x0004 },
+  { 0x01, 0x00, 0, 0x03, 0x0008, 0x0005 },
+  { 0x01, 0x00, 0, 0x03, 0x0008, 0x0006 },
+  { 0x01, 0x00, 0, 0x03, 0x0008, 0x0007 },
+  { 0x01, 0x00, 0, 0x03, 0x0008, 0x0008 },
+  { 0x01, 0x00, 0, 0x03, 0x0008, 0x0009 },
+  { 0x00, 0x01, 0, 0x03, 0x0000, 0x000a },
+  { 0x00, 0x01, 0, 0x03, 0x0000, 0x000c },
+  { 0x00, 0x02, 0, 0x03, 0x0000, 0x000e },
+  { 0x00, 0x02, 0, 0x03, 0x0000, 0x0012 },
+  { 0x00, 0x03, 0, 0x03, 0x0000, 0x0016 },
+  { 0x00, 0x03, 0, 0x03, 0x0000, 0x001e },
+  { 0x00, 0x04, 0, 0x03, 0x0000, 0x0026 },
+  { 0x00, 0x04, 0, 0x03, 0x0000, 0x0036 },
+  { 0x00, 0x01, 0, 0x03, 0x0001, 0x000a },
+  { 0x00, 0x01, 0, 0x03, 0x0001, 0x000c },
+  { 0x00, 0x02, 0, 0x03, 0x0001, 0x000e },
+  { 0x00, 0x02, 0, 0x03, 0x0001, 0x0012 },
+  { 0x00, 0x03, 0, 0x03, 0x0001, 0x0016 },
+  { 0x00, 0x03, 0, 0x03, 0x0001, 0x001e },
+  { 0x00, 0x04, 0, 0x03, 0x0001, 0x0026 },
+  { 0x00, 0x04, 0, 0x03, 0x0001, 0x0036 },
+  { 0x00, 0x01, 0, 0x03, 0x0002, 0x000a },
+  { 0x00, 0x01, 0, 0x03, 0x0002, 0x000c },
+  { 0x00, 0x02, 0, 0x03, 0x0002, 0x000e },
+  { 0x00, 0x02, 0, 0x03, 0x0002, 0x0012 },
+  { 0x00, 0x03, 0, 0x03, 0x0002, 0x0016 },
+  { 0x00, 0x03, 0, 0x03, 0x0002, 0x001e },
+  { 0x00, 0x04, 0, 0x03, 0x0002, 0x0026 },
+  { 0x00, 0x04, 0, 0x03, 0x0002, 0x0036 },
+  { 0x00, 0x01, 0, 0x03, 0x0003, 0x000a },
+  { 0x00, 0x01, 0, 0x03, 0x0003, 0x000c },
+  { 0x00, 0x02, 0, 0x03, 0x0003, 0x000e },
+  { 0x00, 0x02, 0, 0x03, 0x0003, 0x0012 },
+  { 0x00, 0x03, 0, 0x03, 0x0003, 0x0016 },
+  { 0x00, 0x03, 0, 0x03, 0x0003, 0x001e },
+  { 0x00, 0x04, 0, 0x03, 0x0003, 0x0026 },
+  { 0x00, 0x04, 0, 0x03, 0x0003, 0x0036 },
+  { 0x00, 0x01, 0, 0x03, 0x0004, 0x000a },
+  { 0x00, 0x01, 0, 0x03, 0x0004, 0x000c },
+  { 0x00, 0x02, 0, 0x03, 0x0004, 0x000e },
+  { 0x00, 0x02, 0, 0x03, 0x0004, 0x0012 },
+  { 0x00, 0x03, 0, 0x03, 0x0004, 0x0016 },
+  { 0x00, 0x03, 0, 0x03, 0x0004, 0x001e },
+  { 0x00, 0x04, 0, 0x03, 0x0004, 0x0026 },
+  { 0x00, 0x04, 0, 0x03, 0x0004, 0x0036 },
+  { 0x00, 0x01, 0, 0x03, 0x0005, 0x000a },
+  { 0x00, 0x01, 0, 0x03, 0x0005, 0x000c },
+  { 0x00, 0x02, 0, 0x03, 0x0005, 0x000e },
+  { 0x00, 0x02, 0, 0x03, 0x0005, 0x0012 },
+  { 0x00, 0x03, 0, 0x03, 0x0005, 0x0016 },
+  { 0x00, 0x03, 0, 0x03, 0x0005, 0x001e },
+  { 0x00, 0x04, 0, 0x03, 0x0005, 0x0026 },
+  { 0x00, 0x04, 0, 0x03, 0x0005, 0x0036 },
+  { 0x01, 0x01, 0, 0x03, 0x0006, 0x000a },
+  { 0x01, 0x01, 0, 0x03, 0x0006, 0x000c },
+  { 0x01, 0x02, 0, 0x03, 0x0006, 0x000e },
+  { 0x01, 0x02, 0, 0x03, 0x0006, 0x0012 },
+  { 0x01, 0x03, 0, 0x03, 0x0006, 0x0016 },
+  { 0x01, 0x03, 0, 0x03, 0x0006, 0x001e },
+  { 0x01, 0x04, 0, 0x03, 0x0006, 0x0026 },
+  { 0x01, 0x04, 0, 0x03, 0x0006, 0x0036 },
+  { 0x01, 0x01, 0, 0x03, 0x0008, 0x000a },
+  { 0x01, 0x01, 0, 0x03, 0x0008, 0x000c },
+  { 0x01, 0x02, 0, 0x03, 0x0008, 0x000e },
+  { 0x01, 0x02, 0, 0x03, 0x0008, 0x0012 },
+  { 0x01, 0x03, 0, 0x03, 0x0008, 0x0016 },
+  { 0x01, 0x03, 0, 0x03, 0x0008, 0x001e },
+  { 0x01, 0x04, 0, 0x03, 0x0008, 0x0026 },
+  { 0x01, 0x04, 0, 0x03, 0x0008, 0x0036 },
+  { 0x00, 0x00, -1, 0x00, 0x0000, 0x0002 },
+  { 0x00, 0x00, -1, 0x01, 0x0000, 0x0003 },
+  { 0x00, 0x00, -1, 0x02, 0x0000, 0x0004 },
+  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0005 },
+  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0006 },
+  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0007 },
+  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0008 },
+  { 0x00, 0x00, -1, 0x03, 0x0000, 0x0009 },
+  { 0x00, 0x00, -1, 0x00, 0x0001, 0x0002 },
+  { 0x00, 0x00, -1, 0x01, 0x0001, 0x0003 },
+  { 0x00, 0x00, -1, 0x02, 0x0001, 0x0004 },
+  { 0x00, 0x00, -1, 0x03, 0x0001, 0x0005 },
+  { 0x00, 0x00, -1, 0x03, 0x0001, 0x0006 },
+  { 0x00, 0x00, -1, 0x03, 0x0001, 0x0007 },
+  { 0x00, 0x00, -1, 0x03, 0x0001, 0x0008 },
+  { 0x00, 0x00, -1, 0x03, 0x0001, 0x0009 },
+  { 0x00, 0x00, -1, 0x00, 0x0002, 0x0002 },
+  { 0x00, 0x00, -1, 0x01, 0x0002, 0x0003 },
+  { 0x00, 0x00, -1, 0x02, 0x0002, 0x0004 },
+  { 0x00, 0x00, -1, 0x03, 0x0002, 0x0005 },
+  { 0x00, 0x00, -1, 0x03, 0x0002, 0x0006 },
+  { 0x00, 0x00, -1, 0x03, 0x0002, 0x0007 },
+  { 0x00, 0x00, -1, 0x03, 0x0002, 0x0008 },
+  { 0x00, 0x00, -1, 0x03, 0x0002, 0x0009 },
+  { 0x00, 0x00, -1, 0x00, 0x0003, 0x0002 },
+  { 0x00, 0x00, -1, 0x01, 0x0003, 0x0003 },
+  { 0x00, 0x00, -1, 0x02, 0x0003, 0x0004 },
+  { 0x00, 0x00, -1, 0x03, 0x0003, 0x0005 },
+  { 0x00, 0x00, -1, 0x03, 0x0003, 0x0006 },
+  { 0x00, 0x00, -1, 0x03, 0x0003, 0x0007 },
+  { 0x00, 0x00, -1, 0x03, 0x0003, 0x0008 },
+  { 0x00, 0x00, -1, 0x03, 0x0003, 0x0009 },
+  { 0x00, 0x00, -1, 0x00, 0x0004, 0x0002 },
+  { 0x00, 0x00, -1, 0x01, 0x0004, 0x0003 },
+  { 0x00, 0x00, -1, 0x02, 0x0004, 0x0004 },
+  { 0x00, 0x00, -1, 0x03, 0x0004, 0x0005 },
+  { 0x00, 0x00, -1, 0x03, 0x0004, 0x0006 },
+  { 0x00, 0x00, -1, 0x03, 0x0004, 0x0007 },
+  { 0x00, 0x00, -1, 0x03, 0x0004, 0x0008 },
+  { 0x00, 0x00, -1, 0x03, 0x0004, 0x0009 },
+  { 0x00, 0x00, -1, 0x00, 0x0005, 0x0002 },
+  { 0x00, 0x00, -1, 0x01, 0x0005, 0x0003 },
+  { 0x00, 0x00, -1, 0x02, 0x0005, 0x0004 },
+  { 0x00, 0x00, -1, 0x03, 0x0005, 0x0005 },
+  { 0x00, 0x00, -1, 0x03, 0x0005, 0x0006 },
+  { 0x00, 0x00, -1, 0x03, 0x0005, 0x0007 },
+  { 0x00, 0x00, -1, 0x03, 0x0005, 0x0008 },
+  { 0x00, 0x00, -1, 0x03, 0x0005, 0x0009 },
+  { 0x01, 0x00, -1, 0x00, 0x0006, 0x0002 },
+  { 0x01, 0x00, -1, 0x01, 0x0006, 0x0003 },
+  { 0x01, 0x00, -1, 0x02, 0x0006, 0x0004 },
+  { 0x01, 0x00, -1, 0x03, 0x0006, 0x0005 },
+  { 0x01, 0x00, -1, 0x03, 0x0006, 0x0006 },
+  { 0x01, 0x00, -1, 0x03, 0x0006, 0x0007 },
+  { 0x01, 0x00, -1, 0x03, 0x0006, 0x0008 },
+  { 0x01, 0x00, -1, 0x03, 0x0006, 0x0009 },
+  { 0x01, 0x00, -1, 0x00, 0x0008, 0x0002 },
+  { 0x01, 0x00, -1, 0x01, 0x0008, 0x0003 },
+  { 0x01, 0x00, -1, 0x02, 0x0008, 0x0004 },
+  { 0x01, 0x00, -1, 0x03, 0x0008, 0x0005 },
+  { 0x01, 0x00, -1, 0x03, 0x0008, 0x0006 },
+  { 0x01, 0x00, -1, 0x03, 0x0008, 0x0007 },
+  { 0x01, 0x00, -1, 0x03, 0x0008, 0x0008 },
+  { 0x01, 0x00, -1, 0x03, 0x0008, 0x0009 },
+  { 0x00, 0x01, -1, 0x03, 0x0000, 0x000a },
+  { 0x00, 0x01, -1, 0x03, 0x0000, 0x000c },
+  { 0x00, 0x02, -1, 0x03, 0x0000, 0x000e },
+  { 0x00, 0x02, -1, 0x03, 0x0000, 0x0012 },
+  { 0x00, 0x03, -1, 0x03, 0x0000, 0x0016 },
+  { 0x00, 0x03, -1, 0x03, 0x0000, 0x001e },
+  { 0x00, 0x04, -1, 0x03, 0x0000, 0x0026 },
+  { 0x00, 0x04, -1, 0x03, 0x0000, 0x0036 },
+  { 0x00, 0x01, -1, 0x03, 0x0001, 0x000a },
+  { 0x00, 0x01, -1, 0x03, 0x0001, 0x000c },
+  { 0x00, 0x02, -1, 0x03, 0x0001, 0x000e },
+  { 0x00, 0x02, -1, 0x03, 0x0001, 0x0012 },
+  { 0x00, 0x03, -1, 0x03, 0x0001, 0x0016 },
+  { 0x00, 0x03, -1, 0x03, 0x0001, 0x001e },
+  { 0x00, 0x04, -1, 0x03, 0x0001, 0x0026 },
+  { 0x00, 0x04, -1, 0x03, 0x0001, 0x0036 },
+  { 0x00, 0x01, -1, 0x03, 0x0002, 0x000a },
+  { 0x00, 0x01, -1, 0x03, 0x0002, 0x000c },
+  { 0x00, 0x02, -1, 0x03, 0x0002, 0x000e },
+  { 0x00, 0x02, -1, 0x03, 0x0002, 0x0012 },
+  { 0x00, 0x03, -1, 0x03, 0x0002, 0x0016 },
+  { 0x00, 0x03, -1, 0x03, 0x0002, 0x001e },
+  { 0x00, 0x04, -1, 0x03, 0x0002, 0x0026 },
+  { 0x00, 0x04, -1, 0x03, 0x0002, 0x0036 },
+  { 0x00, 0x01, -1, 0x03, 0x0003, 0x000a },
+  { 0x00, 0x01, -1, 0x03, 0x0003, 0x000c },
+  { 0x00, 0x02, -1, 0x03, 0x0003, 0x000e },
+  { 0x00, 0x02, -1, 0x03, 0x0003, 0x0012 },
+  { 0x00, 0x03, -1, 0x03, 0x0003, 0x0016 },
+  { 0x00, 0x03, -1, 0x03, 0x0003, 0x001e },
+  { 0x00, 0x04, -1, 0x03, 0x0003, 0x0026 },
+  { 0x00, 0x04, -1, 0x03, 0x0003, 0x0036 },
+  { 0x00, 0x01, -1, 0x03, 0x0004, 0x000a },
+  { 0x00, 0x01, -1, 0x03, 0x0004, 0x000c },
+  { 0x00, 0x02, -1, 0x03, 0x0004, 0x000e },
+  { 0x00, 0x02, -1, 0x03, 0x0004, 0x0012 },
+  { 0x00, 0x03, -1, 0x03, 0x0004, 0x0016 },
+  { 0x00, 0x03, -1, 0x03, 0x0004, 0x001e },
+  { 0x00, 0x04, -1, 0x03, 0x0004, 0x0026 },
+  { 0x00, 0x04, -1, 0x03, 0x0004, 0x0036 },
+  { 0x00, 0x01, -1, 0x03, 0x0005, 0x000a },
+  { 0x00, 0x01, -1, 0x03, 0x0005, 0x000c },
+  { 0x00, 0x02, -1, 0x03, 0x0005, 0x000e },
+  { 0x00, 0x02, -1, 0x03, 0x0005, 0x0012 },
+  { 0x00, 0x03, -1, 0x03, 0x0005, 0x0016 },
+  { 0x00, 0x03, -1, 0x03, 0x0005, 0x001e },
+  { 0x00, 0x04, -1, 0x03, 0x0005, 0x0026 },
+  { 0x00, 0x04, -1, 0x03, 0x0005, 0x0036 },
+  { 0x01, 0x01, -1, 0x03, 0x0006, 0x000a },
+  { 0x01, 0x01, -1, 0x03, 0x0006, 0x000c },
+  { 0x01, 0x02, -1, 0x03, 0x0006, 0x000e },
+  { 0x01, 0x02, -1, 0x03, 0x0006, 0x0012 },
+  { 0x01, 0x03, -1, 0x03, 0x0006, 0x0016 },
+  { 0x01, 0x03, -1, 0x03, 0x0006, 0x001e },
+  { 0x01, 0x04, -1, 0x03, 0x0006, 0x0026 },
+  { 0x01, 0x04, -1, 0x03, 0x0006, 0x0036 },
+  { 0x01, 0x01, -1, 0x03, 0x0008, 0x000a },
+  { 0x01, 0x01, -1, 0x03, 0x0008, 0x000c },
+  { 0x01, 0x02, -1, 0x03, 0x0008, 0x000e },
+  { 0x01, 0x02, -1, 0x03, 0x0008, 0x0012 },
+  { 0x01, 0x03, -1, 0x03, 0x0008, 0x0016 },
+  { 0x01, 0x03, -1, 0x03, 0x0008, 0x001e },
+  { 0x01, 0x04, -1, 0x03, 0x0008, 0x0026 },
+  { 0x01, 0x04, -1, 0x03, 0x0008, 0x0036 },
+  { 0x02, 0x00, -1, 0x00, 0x000a, 0x0002 },
+  { 0x02, 0x00, -1, 0x01, 0x000a, 0x0003 },
+  { 0x02, 0x00, -1, 0x02, 0x000a, 0x0004 },
+  { 0x02, 0x00, -1, 0x03, 0x000a, 0x0005 },
+  { 0x02, 0x00, -1, 0x03, 0x000a, 0x0006 },
+  { 0x02, 0x00, -1, 0x03, 0x000a, 0x0007 },
+  { 0x02, 0x00, -1, 0x03, 0x000a, 0x0008 },
+  { 0x02, 0x00, -1, 0x03, 0x000a, 0x0009 },
+  { 0x02, 0x00, -1, 0x00, 0x000e, 0x0002 },
+  { 0x02, 0x00, -1, 0x01, 0x000e, 0x0003 },
+  { 0x02, 0x00, -1, 0x02, 0x000e, 0x0004 },
+  { 0x02, 0x00, -1, 0x03, 0x000e, 0x0005 },
+  { 0x02, 0x00, -1, 0x03, 0x000e, 0x0006 },
+  { 0x02, 0x00, -1, 0x03, 0x000e, 0x0007 },
+  { 0x02, 0x00, -1, 0x03, 0x000e, 0x0008 },
+  { 0x02, 0x00, -1, 0x03, 0x000e, 0x0009 },
+  { 0x03, 0x00, -1, 0x00, 0x0012, 0x0002 },
+  { 0x03, 0x00, -1, 0x01, 0x0012, 0x0003 },
+  { 0x03, 0x00, -1, 0x02, 0x0012, 0x0004 },
+  { 0x03, 0x00, -1, 0x03, 0x0012, 0x0005 },
+  { 0x03, 0x00, -1, 0x03, 0x0012, 0x0006 },
+  { 0x03, 0x00, -1, 0x03, 0x0012, 0x0007 },
+  { 0x03, 0x00, -1, 0x03, 0x0012, 0x0008 },
+  { 0x03, 0x00, -1, 0x03, 0x0012, 0x0009 },
+  { 0x03, 0x00, -1, 0x00, 0x001a, 0x0002 },
+  { 0x03, 0x00, -1, 0x01, 0x001a, 0x0003 },
+  { 0x03, 0x00, -1, 0x02, 0x001a, 0x0004 },
+  { 0x03, 0x00, -1, 0x03, 0x001a, 0x0005 },
+  { 0x03, 0x00, -1, 0x03, 0x001a, 0x0006 },
+  { 0x03, 0x00, -1, 0x03, 0x001a, 0x0007 },
+  { 0x03, 0x00, -1, 0x03, 0x001a, 0x0008 },
+  { 0x03, 0x00, -1, 0x03, 0x001a, 0x0009 },
+  { 0x04, 0x00, -1, 0x00, 0x0022, 0x0002 },
+  { 0x04, 0x00, -1, 0x01, 0x0022, 0x0003 },
+  { 0x04, 0x00, -1, 0x02, 0x0022, 0x0004 },
+  { 0x04, 0x00, -1, 0x03, 0x0022, 0x0005 },
+  { 0x04, 0x00, -1, 0x03, 0x0022, 0x0006 },
+  { 0x04, 0x00, -1, 0x03, 0x0022, 0x0007 },
+  { 0x04, 0x00, -1, 0x03, 0x0022, 0x0008 },
+  { 0x04, 0x00, -1, 0x03, 0x0022, 0x0009 },
+  { 0x04, 0x00, -1, 0x00, 0x0032, 0x0002 },
+  { 0x04, 0x00, -1, 0x01, 0x0032, 0x0003 },
+  { 0x04, 0x00, -1, 0x02, 0x0032, 0x0004 },
+  { 0x04, 0x00, -1, 0x03, 0x0032, 0x0005 },
+  { 0x04, 0x00, -1, 0x03, 0x0032, 0x0006 },
+  { 0x04, 0x00, -1, 0x03, 0x0032, 0x0007 },
+  { 0x04, 0x00, -1, 0x03, 0x0032, 0x0008 },
+  { 0x04, 0x00, -1, 0x03, 0x0032, 0x0009 },
+  { 0x05, 0x00, -1, 0x00, 0x0042, 0x0002 },
+  { 0x05, 0x00, -1, 0x01, 0x0042, 0x0003 },
+  { 0x05, 0x00, -1, 0x02, 0x0042, 0x0004 },
+  { 0x05, 0x00, -1, 0x03, 0x0042, 0x0005 },
+  { 0x05, 0x00, -1, 0x03, 0x0042, 0x0006 },
+  { 0x05, 0x00, -1, 0x03, 0x0042, 0x0007 },
+  { 0x05, 0x00, -1, 0x03, 0x0042, 0x0008 },
+  { 0x05, 0x00, -1, 0x03, 0x0042, 0x0009 },
+  { 0x05, 0x00, -1, 0x00, 0x0062, 0x0002 },
+  { 0x05, 0x00, -1, 0x01, 0x0062, 0x0003 },
+  { 0x05, 0x00, -1, 0x02, 0x0062, 0x0004 },
+  { 0x05, 0x00, -1, 0x03, 0x0062, 0x0005 },
+  { 0x05, 0x00, -1, 0x03, 0x0062, 0x0006 },
+  { 0x05, 0x00, -1, 0x03, 0x0062, 0x0007 },
+  { 0x05, 0x00, -1, 0x03, 0x0062, 0x0008 },
+  { 0x05, 0x00, -1, 0x03, 0x0062, 0x0009 },
+  { 0x02, 0x01, -1, 0x03, 0x000a, 0x000a },
+  { 0x02, 0x01, -1, 0x03, 0x000a, 0x000c },
+  { 0x02, 0x02, -1, 0x03, 0x000a, 0x000e },
+  { 0x02, 0x02, -1, 0x03, 0x000a, 0x0012 },
+  { 0x02, 0x03, -1, 0x03, 0x000a, 0x0016 },
+  { 0x02, 0x03, -1, 0x03, 0x000a, 0x001e },
+  { 0x02, 0x04, -1, 0x03, 0x000a, 0x0026 },
+  { 0x02, 0x04, -1, 0x03, 0x000a, 0x0036 },
+  { 0x02, 0x01, -1, 0x03, 0x000e, 0x000a },
+  { 0x02, 0x01, -1, 0x03, 0x000e, 0x000c },
+  { 0x02, 0x02, -1, 0x03, 0x000e, 0x000e },
+  { 0x02, 0x02, -1, 0x03, 0x000e, 0x0012 },
+  { 0x02, 0x03, -1, 0x03, 0x000e, 0x0016 },
+  { 0x02, 0x03, -1, 0x03, 0x000e, 0x001e },
+  { 0x02, 0x04, -1, 0x03, 0x000e, 0x0026 },
+  { 0x02, 0x04, -1, 0x03, 0x000e, 0x0036 },
+  { 0x03, 0x01, -1, 0x03, 0x0012, 0x000a },
+  { 0x03, 0x01, -1, 0x03, 0x0012, 0x000c },
+  { 0x03, 0x02, -1, 0x03, 0x0012, 0x000e },
+  { 0x03, 0x02, -1, 0x03, 0x0012, 0x0012 },
+  { 0x03, 0x03, -1, 0x03, 0x0012, 0x0016 },
+  { 0x03, 0x03, -1, 0x03, 0x0012, 0x001e },
+  { 0x03, 0x04, -1, 0x03, 0x0012, 0x0026 },
+  { 0x03, 0x04, -1, 0x03, 0x0012, 0x0036 },
+  { 0x03, 0x01, -1, 0x03, 0x001a, 0x000a },
+  { 0x03, 0x01, -1, 0x03, 0x001a, 0x000c },
+  { 0x03, 0x02, -1, 0x03, 0x001a, 0x000e },
+  { 0x03, 0x02, -1, 0x03, 0x001a, 0x0012 },
+  { 0x03, 0x03, -1, 0x03, 0x001a, 0x0016 },
+  { 0x03, 0x03, -1, 0x03, 0x001a, 0x001e },
+  { 0x03, 0x04, -1, 0x03, 0x001a, 0x0026 },
+  { 0x03, 0x04, -1, 0x03, 0x001a, 0x0036 },
+  { 0x04, 0x01, -1, 0x03, 0x0022, 0x000a },
+  { 0x04, 0x01, -1, 0x03, 0x0022, 0x000c },
+  { 0x04, 0x02, -1, 0x03, 0x0022, 0x000e },
+  { 0x04, 0x02, -1, 0x03, 0x0022, 0x0012 },
+  { 0x04, 0x03, -1, 0x03, 0x0022, 0x0016 },
+  { 0x04, 0x03, -1, 0x03, 0x0022, 0x001e },
+  { 0x04, 0x04, -1, 0x03, 0x0022, 0x0026 },
+  { 0x04, 0x04, -1, 0x03, 0x0022, 0x0036 },
+  { 0x04, 0x01, -1, 0x03, 0x0032, 0x000a },
+  { 0x04, 0x01, -1, 0x03, 0x0032, 0x000c },
+  { 0x04, 0x02, -1, 0x03, 0x0032, 0x000e },
+  { 0x04, 0x02, -1, 0x03, 0x0032, 0x0012 },
+  { 0x04, 0x03, -1, 0x03, 0x0032, 0x0016 },
+  { 0x04, 0x03, -1, 0x03, 0x0032, 0x001e },
+  { 0x04, 0x04, -1, 0x03, 0x0032, 0x0026 },
+  { 0x04, 0x04, -1, 0x03, 0x0032, 0x0036 },
+  { 0x05, 0x01, -1, 0x03, 0x0042, 0x000a },
+  { 0x05, 0x01, -1, 0x03, 0x0042, 0x000c },
+  { 0x05, 0x02, -1, 0x03, 0x0042, 0x000e },
+  { 0x05, 0x02, -1, 0x03, 0x0042, 0x0012 },
+  { 0x05, 0x03, -1, 0x03, 0x0042, 0x0016 },
+  { 0x05, 0x03, -1, 0x03, 0x0042, 0x001e },
+  { 0x05, 0x04, -1, 0x03, 0x0042, 0x0026 },
+  { 0x05, 0x04, -1, 0x03, 0x0042, 0x0036 },
+  { 0x05, 0x01, -1, 0x03, 0x0062, 0x000a },
+  { 0x05, 0x01, -1, 0x03, 0x0062, 0x000c },
+  { 0x05, 0x02, -1, 0x03, 0x0062, 0x000e },
+  { 0x05, 0x02, -1, 0x03, 0x0062, 0x0012 },
+  { 0x05, 0x03, -1, 0x03, 0x0062, 0x0016 },
+  { 0x05, 0x03, -1, 0x03, 0x0062, 0x001e },
+  { 0x05, 0x04, -1, 0x03, 0x0062, 0x0026 },
+  { 0x05, 0x04, -1, 0x03, 0x0062, 0x0036 },
+  { 0x00, 0x05, -1, 0x03, 0x0000, 0x0046 },
+  { 0x00, 0x05, -1, 0x03, 0x0000, 0x0066 },
+  { 0x00, 0x06, -1, 0x03, 0x0000, 0x0086 },
+  { 0x00, 0x07, -1, 0x03, 0x0000, 0x00c6 },
+  { 0x00, 0x08, -1, 0x03, 0x0000, 0x0146 },
+  { 0x00, 0x09, -1, 0x03, 0x0000, 0x0246 },
+  { 0x00, 0x0a, -1, 0x03, 0x0000, 0x0446 },
+  { 0x00, 0x18, -1, 0x03, 0x0000, 0x0846 },
+  { 0x00, 0x05, -1, 0x03, 0x0001, 0x0046 },
+  { 0x00, 0x05, -1, 0x03, 0x0001, 0x0066 },
+  { 0x00, 0x06, -1, 0x03, 0x0001, 0x0086 },
+  { 0x00, 0x07, -1, 0x03, 0x0001, 0x00c6 },
+  { 0x00, 0x08, -1, 0x03, 0x0001, 0x0146 },
+  { 0x00, 0x09, -1, 0x03, 0x0001, 0x0246 },
+  { 0x00, 0x0a, -1, 0x03, 0x0001, 0x0446 },
+  { 0x00, 0x18, -1, 0x03, 0x0001, 0x0846 },
+  { 0x00, 0x05, -1, 0x03, 0x0002, 0x0046 },
+  { 0x00, 0x05, -1, 0x03, 0x0002, 0x0066 },
+  { 0x00, 0x06, -1, 0x03, 0x0002, 0x0086 },
+  { 0x00, 0x07, -1, 0x03, 0x0002, 0x00c6 },
+  { 0x00, 0x08, -1, 0x03, 0x0002, 0x0146 },
+  { 0x00, 0x09, -1, 0x03, 0x0002, 0x0246 },
+  { 0x00, 0x0a, -1, 0x03, 0x0002, 0x0446 },
+  { 0x00, 0x18, -1, 0x03, 0x0002, 0x0846 },
+  { 0x00, 0x05, -1, 0x03, 0x0003, 0x0046 },
+  { 0x00, 0x05, -1, 0x03, 0x0003, 0x0066 },
+  { 0x00, 0x06, -1, 0x03, 0x0003, 0x0086 },
+  { 0x00, 0x07, -1, 0x03, 0x0003, 0x00c6 },
+  { 0x00, 0x08, -1, 0x03, 0x0003, 0x0146 },
+  { 0x00, 0x09, -1, 0x03, 0x0003, 0x0246 },
+  { 0x00, 0x0a, -1, 0x03, 0x0003, 0x0446 },
+  { 0x00, 0x18, -1, 0x03, 0x0003, 0x0846 },
+  { 0x00, 0x05, -1, 0x03, 0x0004, 0x0046 },
+  { 0x00, 0x05, -1, 0x03, 0x0004, 0x0066 },
+  { 0x00, 0x06, -1, 0x03, 0x0004, 0x0086 },
+  { 0x00, 0x07, -1, 0x03, 0x0004, 0x00c6 },
+  { 0x00, 0x08, -1, 0x03, 0x0004, 0x0146 },
+  { 0x00, 0x09, -1, 0x03, 0x0004, 0x0246 },
+  { 0x00, 0x0a, -1, 0x03, 0x0004, 0x0446 },
+  { 0x00, 0x18, -1, 0x03, 0x0004, 0x0846 },
+  { 0x00, 0x05, -1, 0x03, 0x0005, 0x0046 },
+  { 0x00, 0x05, -1, 0x03, 0x0005, 0x0066 },
+  { 0x00, 0x06, -1, 0x03, 0x0005, 0x0086 },
+  { 0x00, 0x07, -1, 0x03, 0x0005, 0x00c6 },
+  { 0x00, 0x08, -1, 0x03, 0x0005, 0x0146 },
+  { 0x00, 0x09, -1, 0x03, 0x0005, 0x0246 },
+  { 0x00, 0x0a, -1, 0x03, 0x0005, 0x0446 },
+  { 0x00, 0x18, -1, 0x03, 0x0005, 0x0846 },
+  { 0x01, 0x05, -1, 0x03, 0x0006, 0x0046 },
+  { 0x01, 0x05, -1, 0x03, 0x0006, 0x0066 },
+  { 0x01, 0x06, -1, 0x03, 0x0006, 0x0086 },
+  { 0x01, 0x07, -1, 0x03, 0x0006, 0x00c6 },
+  { 0x01, 0x08, -1, 0x03, 0x0006, 0x0146 },
+  { 0x01, 0x09, -1, 0x03, 0x0006, 0x0246 },
+  { 0x01, 0x0a, -1, 0x03, 0x0006, 0x0446 },
+  { 0x01, 0x18, -1, 0x03, 0x0006, 0x0846 },
+  { 0x01, 0x05, -1, 0x03, 0x0008, 0x0046 },
+  { 0x01, 0x05, -1, 0x03, 0x0008, 0x0066 },
+  { 0x01, 0x06, -1, 0x03, 0x0008, 0x0086 },
+  { 0x01, 0x07, -1, 0x03, 0x0008, 0x00c6 },
+  { 0x01, 0x08, -1, 0x03, 0x0008, 0x0146 },
+  { 0x01, 0x09, -1, 0x03, 0x0008, 0x0246 },
+  { 0x01, 0x0a, -1, 0x03, 0x0008, 0x0446 },
+  { 0x01, 0x18, -1, 0x03, 0x0008, 0x0846 },
+  { 0x06, 0x00, -1, 0x00, 0x0082, 0x0002 },
+  { 0x06, 0x00, -1, 0x01, 0x0082, 0x0003 },
+  { 0x06, 0x00, -1, 0x02, 0x0082, 0x0004 },
+  { 0x06, 0x00, -1, 0x03, 0x0082, 0x0005 },
+  { 0x06, 0x00, -1, 0x03, 0x0082, 0x0006 },
+  { 0x06, 0x00, -1, 0x03, 0x0082, 0x0007 },
+  { 0x06, 0x00, -1, 0x03, 0x0082, 0x0008 },
+  { 0x06, 0x00, -1, 0x03, 0x0082, 0x0009 },
+  { 0x07, 0x00, -1, 0x00, 0x00c2, 0x0002 },
+  { 0x07, 0x00, -1, 0x01, 0x00c2, 0x0003 },
+  { 0x07, 0x00, -1, 0x02, 0x00c2, 0x0004 },
+  { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0005 },
+  { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0006 },
+  { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0007 },
+  { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0008 },
+  { 0x07, 0x00, -1, 0x03, 0x00c2, 0x0009 },
+  { 0x08, 0x00, -1, 0x00, 0x0142, 0x0002 },
+  { 0x08, 0x00, -1, 0x01, 0x0142, 0x0003 },
+  { 0x08, 0x00, -1, 0x02, 0x0142, 0x0004 },
+  { 0x08, 0x00, -1, 0x03, 0x0142, 0x0005 },
+  { 0x08, 0x00, -1, 0x03, 0x0142, 0x0006 },
+  { 0x08, 0x00, -1, 0x03, 0x0142, 0x0007 },
+  { 0x08, 0x00, -1, 0x03, 0x0142, 0x0008 },
+  { 0x08, 0x00, -1, 0x03, 0x0142, 0x0009 },
+  { 0x09, 0x00, -1, 0x00, 0x0242, 0x0002 },
+  { 0x09, 0x00, -1, 0x01, 0x0242, 0x0003 },
+  { 0x09, 0x00, -1, 0x02, 0x0242, 0x0004 },
+  { 0x09, 0x00, -1, 0x03, 0x0242, 0x0005 },
+  { 0x09, 0x00, -1, 0x03, 0x0242, 0x0006 },
+  { 0x09, 0x00, -1, 0x03, 0x0242, 0x0007 },
+  { 0x09, 0x00, -1, 0x03, 0x0242, 0x0008 },
+  { 0x09, 0x00, -1, 0x03, 0x0242, 0x0009 },
+  { 0x0a, 0x00, -1, 0x00, 0x0442, 0x0002 },
+  { 0x0a, 0x00, -1, 0x01, 0x0442, 0x0003 },
+  { 0x0a, 0x00, -1, 0x02, 0x0442, 0x0004 },
+  { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0005 },
+  { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0006 },
+  { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0007 },
+  { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0008 },
+  { 0x0a, 0x00, -1, 0x03, 0x0442, 0x0009 },
+  { 0x0c, 0x00, -1, 0x00, 0x0842, 0x0002 },
+  { 0x0c, 0x00, -1, 0x01, 0x0842, 0x0003 },
+  { 0x0c, 0x00, -1, 0x02, 0x0842, 0x0004 },
+  { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0005 },
+  { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0006 },
+  { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0007 },
+  { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0008 },
+  { 0x0c, 0x00, -1, 0x03, 0x0842, 0x0009 },
+  { 0x0e, 0x00, -1, 0x00, 0x1842, 0x0002 },
+  { 0x0e, 0x00, -1, 0x01, 0x1842, 0x0003 },
+  { 0x0e, 0x00, -1, 0x02, 0x1842, 0x0004 },
+  { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0005 },
+  { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0006 },
+  { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0007 },
+  { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0008 },
+  { 0x0e, 0x00, -1, 0x03, 0x1842, 0x0009 },
+  { 0x18, 0x00, -1, 0x00, 0x5842, 0x0002 },
+  { 0x18, 0x00, -1, 0x01, 0x5842, 0x0003 },
+  { 0x18, 0x00, -1, 0x02, 0x5842, 0x0004 },
+  { 0x18, 0x00, -1, 0x03, 0x5842, 0x0005 },
+  { 0x18, 0x00, -1, 0x03, 0x5842, 0x0006 },
+  { 0x18, 0x00, -1, 0x03, 0x5842, 0x0007 },
+  { 0x18, 0x00, -1, 0x03, 0x5842, 0x0008 },
+  { 0x18, 0x00, -1, 0x03, 0x5842, 0x0009 },
+  { 0x02, 0x05, -1, 0x03, 0x000a, 0x0046 },
+  { 0x02, 0x05, -1, 0x03, 0x000a, 0x0066 },
+  { 0x02, 0x06, -1, 0x03, 0x000a, 0x0086 },
+  { 0x02, 0x07, -1, 0x03, 0x000a, 0x00c6 },
+  { 0x02, 0x08, -1, 0x03, 0x000a, 0x0146 },
+  { 0x02, 0x09, -1, 0x03, 0x000a, 0x0246 },
+  { 0x02, 0x0a, -1, 0x03, 0x000a, 0x0446 },
+  { 0x02, 0x18, -1, 0x03, 0x000a, 0x0846 },
+  { 0x02, 0x05, -1, 0x03, 0x000e, 0x0046 },
+  { 0x02, 0x05, -1, 0x03, 0x000e, 0x0066 },
+  { 0x02, 0x06, -1, 0x03, 0x000e, 0x0086 },
+  { 0x02, 0x07, -1, 0x03, 0x000e, 0x00c6 },
+  { 0x02, 0x08, -1, 0x03, 0x000e, 0x0146 },
+  { 0x02, 0x09, -1, 0x03, 0x000e, 0x0246 },
+  { 0x02, 0x0a, -1, 0x03, 0x000e, 0x0446 },
+  { 0x02, 0x18, -1, 0x03, 0x000e, 0x0846 },
+  { 0x03, 0x05, -1, 0x03, 0x0012, 0x0046 },
+  { 0x03, 0x05, -1, 0x03, 0x0012, 0x0066 },
+  { 0x03, 0x06, -1, 0x03, 0x0012, 0x0086 },
+  { 0x03, 0x07, -1, 0x03, 0x0012, 0x00c6 },
+  { 0x03, 0x08, -1, 0x03, 0x0012, 0x0146 },
+  { 0x03, 0x09, -1, 0x03, 0x0012, 0x0246 },
+  { 0x03, 0x0a, -1, 0x03, 0x0012, 0x0446 },
+  { 0x03, 0x18, -1, 0x03, 0x0012, 0x0846 },
+  { 0x03, 0x05, -1, 0x03, 0x001a, 0x0046 },
+  { 0x03, 0x05, -1, 0x03, 0x001a, 0x0066 },
+  { 0x03, 0x06, -1, 0x03, 0x001a, 0x0086 },
+  { 0x03, 0x07, -1, 0x03, 0x001a, 0x00c6 },
+  { 0x03, 0x08, -1, 0x03, 0x001a, 0x0146 },
+  { 0x03, 0x09, -1, 0x03, 0x001a, 0x0246 },
+  { 0x03, 0x0a, -1, 0x03, 0x001a, 0x0446 },
+  { 0x03, 0x18, -1, 0x03, 0x001a, 0x0846 },
+  { 0x04, 0x05, -1, 0x03, 0x0022, 0x0046 },
+  { 0x04, 0x05, -1, 0x03, 0x0022, 0x0066 },
+  { 0x04, 0x06, -1, 0x03, 0x0022, 0x0086 },
+  { 0x04, 0x07, -1, 0x03, 0x0022, 0x00c6 },
+  { 0x04, 0x08, -1, 0x03, 0x0022, 0x0146 },
+  { 0x04, 0x09, -1, 0x03, 0x0022, 0x0246 },
+  { 0x04, 0x0a, -1, 0x03, 0x0022, 0x0446 },
+  { 0x04, 0x18, -1, 0x03, 0x0022, 0x0846 },
+  { 0x04, 0x05, -1, 0x03, 0x0032, 0x0046 },
+  { 0x04, 0x05, -1, 0x03, 0x0032, 0x0066 },
+  { 0x04, 0x06, -1, 0x03, 0x0032, 0x0086 },
+  { 0x04, 0x07, -1, 0x03, 0x0032, 0x00c6 },
+  { 0x04, 0x08, -1, 0x03, 0x0032, 0x0146 },
+  { 0x04, 0x09, -1, 0x03, 0x0032, 0x0246 },
+  { 0x04, 0x0a, -1, 0x03, 0x0032, 0x0446 },
+  { 0x04, 0x18, -1, 0x03, 0x0032, 0x0846 },
+  { 0x05, 0x05, -1, 0x03, 0x0042, 0x0046 },
+  { 0x05, 0x05, -1, 0x03, 0x0042, 0x0066 },
+  { 0x05, 0x06, -1, 0x03, 0x0042, 0x0086 },
+  { 0x05, 0x07, -1, 0x03, 0x0042, 0x00c6 },
+  { 0x05, 0x08, -1, 0x03, 0x0042, 0x0146 },
+  { 0x05, 0x09, -1, 0x03, 0x0042, 0x0246 },
+  { 0x05, 0x0a, -1, 0x03, 0x0042, 0x0446 },
+  { 0x05, 0x18, -1, 0x03, 0x0042, 0x0846 },
+  { 0x05, 0x05, -1, 0x03, 0x0062, 0x0046 },
+  { 0x05, 0x05, -1, 0x03, 0x0062, 0x0066 },
+  { 0x05, 0x06, -1, 0x03, 0x0062, 0x0086 },
+  { 0x05, 0x07, -1, 0x03, 0x0062, 0x00c6 },
+  { 0x05, 0x08, -1, 0x03, 0x0062, 0x0146 },
+  { 0x05, 0x09, -1, 0x03, 0x0062, 0x0246 },
+  { 0x05, 0x0a, -1, 0x03, 0x0062, 0x0446 },
+  { 0x05, 0x18, -1, 0x03, 0x0062, 0x0846 },
+  { 0x06, 0x01, -1, 0x03, 0x0082, 0x000a },
+  { 0x06, 0x01, -1, 0x03, 0x0082, 0x000c },
+  { 0x06, 0x02, -1, 0x03, 0x0082, 0x000e },
+  { 0x06, 0x02, -1, 0x03, 0x0082, 0x0012 },
+  { 0x06, 0x03, -1, 0x03, 0x0082, 0x0016 },
+  { 0x06, 0x03, -1, 0x03, 0x0082, 0x001e },
+  { 0x06, 0x04, -1, 0x03, 0x0082, 0x0026 },
+  { 0x06, 0x04, -1, 0x03, 0x0082, 0x0036 },
+  { 0x07, 0x01, -1, 0x03, 0x00c2, 0x000a },
+  { 0x07, 0x01, -1, 0x03, 0x00c2, 0x000c },
+  { 0x07, 0x02, -1, 0x03, 0x00c2, 0x000e },
+  { 0x07, 0x02, -1, 0x03, 0x00c2, 0x0012 },
+  { 0x07, 0x03, -1, 0x03, 0x00c2, 0x0016 },
+  { 0x07, 0x03, -1, 0x03, 0x00c2, 0x001e },
+  { 0x07, 0x04, -1, 0x03, 0x00c2, 0x0026 },
+  { 0x07, 0x04, -1, 0x03, 0x00c2, 0x0036 },
+  { 0x08, 0x01, -1, 0x03, 0x0142, 0x000a },
+  { 0x08, 0x01, -1, 0x03, 0x0142, 0x000c },
+  { 0x08, 0x02, -1, 0x03, 0x0142, 0x000e },
+  { 0x08, 0x02, -1, 0x03, 0x0142, 0x0012 },
+  { 0x08, 0x03, -1, 0x03, 0x0142, 0x0016 },
+  { 0x08, 0x03, -1, 0x03, 0x0142, 0x001e },
+  { 0x08, 0x04, -1, 0x03, 0x0142, 0x0026 },
+  { 0x08, 0x04, -1, 0x03, 0x0142, 0x0036 },
+  { 0x09, 0x01, -1, 0x03, 0x0242, 0x000a },
+  { 0x09, 0x01, -1, 0x03, 0x0242, 0x000c },
+  { 0x09, 0x02, -1, 0x03, 0x0242, 0x000e },
+  { 0x09, 0x02, -1, 0x03, 0x0242, 0x0012 },
+  { 0x09, 0x03, -1, 0x03, 0x0242, 0x0016 },
+  { 0x09, 0x03, -1, 0x03, 0x0242, 0x001e },
+  { 0x09, 0x04, -1, 0x03, 0x0242, 0x0026 },
+  { 0x09, 0x04, -1, 0x03, 0x0242, 0x0036 },
+  { 0x0a, 0x01, -1, 0x03, 0x0442, 0x000a },
+  { 0x0a, 0x01, -1, 0x03, 0x0442, 0x000c },
+  { 0x0a, 0x02, -1, 0x03, 0x0442, 0x000e },
+  { 0x0a, 0x02, -1, 0x03, 0x0442, 0x0012 },
+  { 0x0a, 0x03, -1, 0x03, 0x0442, 0x0016 },
+  { 0x0a, 0x03, -1, 0x03, 0x0442, 0x001e },
+  { 0x0a, 0x04, -1, 0x03, 0x0442, 0x0026 },
+  { 0x0a, 0x04, -1, 0x03, 0x0442, 0x0036 },
+  { 0x0c, 0x01, -1, 0x03, 0x0842, 0x000a },
+  { 0x0c, 0x01, -1, 0x03, 0x0842, 0x000c },
+  { 0x0c, 0x02, -1, 0x03, 0x0842, 0x000e },
+  { 0x0c, 0x02, -1, 0x03, 0x0842, 0x0012 },
+  { 0x0c, 0x03, -1, 0x03, 0x0842, 0x0016 },
+  { 0x0c, 0x03, -1, 0x03, 0x0842, 0x001e },
+  { 0x0c, 0x04, -1, 0x03, 0x0842, 0x0026 },
+  { 0x0c, 0x04, -1, 0x03, 0x0842, 0x0036 },
+  { 0x0e, 0x01, -1, 0x03, 0x1842, 0x000a },
+  { 0x0e, 0x01, -1, 0x03, 0x1842, 0x000c },
+  { 0x0e, 0x02, -1, 0x03, 0x1842, 0x000e },
+  { 0x0e, 0x02, -1, 0x03, 0x1842, 0x0012 },
+  { 0x0e, 0x03, -1, 0x03, 0x1842, 0x0016 },
+  { 0x0e, 0x03, -1, 0x03, 0x1842, 0x001e },
+  { 0x0e, 0x04, -1, 0x03, 0x1842, 0x0026 },
+  { 0x0e, 0x04, -1, 0x03, 0x1842, 0x0036 },
+  { 0x18, 0x01, -1, 0x03, 0x5842, 0x000a },
+  { 0x18, 0x01, -1, 0x03, 0x5842, 0x000c },
+  { 0x18, 0x02, -1, 0x03, 0x5842, 0x000e },
+  { 0x18, 0x02, -1, 0x03, 0x5842, 0x0012 },
+  { 0x18, 0x03, -1, 0x03, 0x5842, 0x0016 },
+  { 0x18, 0x03, -1, 0x03, 0x5842, 0x001e },
+  { 0x18, 0x04, -1, 0x03, 0x5842, 0x0026 },
+  { 0x18, 0x04, -1, 0x03, 0x5842, 0x0036 },
+  { 0x06, 0x05, -1, 0x03, 0x0082, 0x0046 },
+  { 0x06, 0x05, -1, 0x03, 0x0082, 0x0066 },
+  { 0x06, 0x06, -1, 0x03, 0x0082, 0x0086 },
+  { 0x06, 0x07, -1, 0x03, 0x0082, 0x00c6 },
+  { 0x06, 0x08, -1, 0x03, 0x0082, 0x0146 },
+  { 0x06, 0x09, -1, 0x03, 0x0082, 0x0246 },
+  { 0x06, 0x0a, -1, 0x03, 0x0082, 0x0446 },
+  { 0x06, 0x18, -1, 0x03, 0x0082, 0x0846 },
+  { 0x07, 0x05, -1, 0x03, 0x00c2, 0x0046 },
+  { 0x07, 0x05, -1, 0x03, 0x00c2, 0x0066 },
+  { 0x07, 0x06, -1, 0x03, 0x00c2, 0x0086 },
+  { 0x07, 0x07, -1, 0x03, 0x00c2, 0x00c6 },
+  { 0x07, 0x08, -1, 0x03, 0x00c2, 0x0146 },
+  { 0x07, 0x09, -1, 0x03, 0x00c2, 0x0246 },
+  { 0x07, 0x0a, -1, 0x03, 0x00c2, 0x0446 },
+  { 0x07, 0x18, -1, 0x03, 0x00c2, 0x0846 },
+  { 0x08, 0x05, -1, 0x03, 0x0142, 0x0046 },
+  { 0x08, 0x05, -1, 0x03, 0x0142, 0x0066 },
+  { 0x08, 0x06, -1, 0x03, 0x0142, 0x0086 },
+  { 0x08, 0x07, -1, 0x03, 0x0142, 0x00c6 },
+  { 0x08, 0x08, -1, 0x03, 0x0142, 0x0146 },
+  { 0x08, 0x09, -1, 0x03, 0x0142, 0x0246 },
+  { 0x08, 0x0a, -1, 0x03, 0x0142, 0x0446 },
+  { 0x08, 0x18, -1, 0x03, 0x0142, 0x0846 },
+  { 0x09, 0x05, -1, 0x03, 0x0242, 0x0046 },
+  { 0x09, 0x05, -1, 0x03, 0x0242, 0x0066 },
+  { 0x09, 0x06, -1, 0x03, 0x0242, 0x0086 },
+  { 0x09, 0x07, -1, 0x03, 0x0242, 0x00c6 },
+  { 0x09, 0x08, -1, 0x03, 0x0242, 0x0146 },
+  { 0x09, 0x09, -1, 0x03, 0x0242, 0x0246 },
+  { 0x09, 0x0a, -1, 0x03, 0x0242, 0x0446 },
+  { 0x09, 0x18, -1, 0x03, 0x0242, 0x0846 },
+  { 0x0a, 0x05, -1, 0x03, 0x0442, 0x0046 },
+  { 0x0a, 0x05, -1, 0x03, 0x0442, 0x0066 },
+  { 0x0a, 0x06, -1, 0x03, 0x0442, 0x0086 },
+  { 0x0a, 0x07, -1, 0x03, 0x0442, 0x00c6 },
+  { 0x0a, 0x08, -1, 0x03, 0x0442, 0x0146 },
+  { 0x0a, 0x09, -1, 0x03, 0x0442, 0x0246 },
+  { 0x0a, 0x0a, -1, 0x03, 0x0442, 0x0446 },
+  { 0x0a, 0x18, -1, 0x03, 0x0442, 0x0846 },
+  { 0x0c, 0x05, -1, 0x03, 0x0842, 0x0046 },
+  { 0x0c, 0x05, -1, 0x03, 0x0842, 0x0066 },
+  { 0x0c, 0x06, -1, 0x03, 0x0842, 0x0086 },
+  { 0x0c, 0x07, -1, 0x03, 0x0842, 0x00c6 },
+  { 0x0c, 0x08, -1, 0x03, 0x0842, 0x0146 },
+  { 0x0c, 0x09, -1, 0x03, 0x0842, 0x0246 },
+  { 0x0c, 0x0a, -1, 0x03, 0x0842, 0x0446 },
+  { 0x0c, 0x18, -1, 0x03, 0x0842, 0x0846 },
+  { 0x0e, 0x05, -1, 0x03, 0x1842, 0x0046 },
+  { 0x0e, 0x05, -1, 0x03, 0x1842, 0x0066 },
+  { 0x0e, 0x06, -1, 0x03, 0x1842, 0x0086 },
+  { 0x0e, 0x07, -1, 0x03, 0x1842, 0x00c6 },
+  { 0x0e, 0x08, -1, 0x03, 0x1842, 0x0146 },
+  { 0x0e, 0x09, -1, 0x03, 0x1842, 0x0246 },
+  { 0x0e, 0x0a, -1, 0x03, 0x1842, 0x0446 },
+  { 0x0e, 0x18, -1, 0x03, 0x1842, 0x0846 },
+  { 0x18, 0x05, -1, 0x03, 0x5842, 0x0046 },
+  { 0x18, 0x05, -1, 0x03, 0x5842, 0x0066 },
+  { 0x18, 0x06, -1, 0x03, 0x5842, 0x0086 },
+  { 0x18, 0x07, -1, 0x03, 0x5842, 0x00c6 },
+  { 0x18, 0x08, -1, 0x03, 0x5842, 0x0146 },
+  { 0x18, 0x09, -1, 0x03, 0x5842, 0x0246 },
+  { 0x18, 0x0a, -1, 0x03, 0x5842, 0x0446 },
+  { 0x18, 0x18, -1, 0x03, 0x5842, 0x0846 },
 };
 
 #endif  /* BROTLI_DEC_PREFIX_H_ */
deleted file mode 100644
--- a/modules/brotli/dec/safe_malloc.c
+++ /dev/null
@@ -1,42 +0,0 @@
-/* Copyright 2013 Google Inc. All Rights Reserved.
-
-   Licensed under the Apache License, Version 2.0 (the "License");
-   you may not use this file except in compliance with the License.
-   You may obtain a copy of the License at
-
-   http://www.apache.org/licenses/LICENSE-2.0
-
-   Unless required by applicable law or agreed to in writing, software
-   distributed under the License is distributed on an "AS IS" BASIS,
-   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-   See the License for the specific language governing permissions and
-   limitations under the License.
-
-   Size-checked memory allocation.
-*/
-
-#include <stdlib.h>
-#include "./safe_malloc.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-/* Returns 0 in case of overflow of nmemb * size. */
-static int CheckSizeArgumentsOverflow(uint64_t nmemb, size_t size) {
-  const uint64_t total_size = nmemb * size;
-  if (nmemb == 0) return 1;
-  if ((uint64_t)size > BROTLI_MAX_ALLOCABLE_MEMORY / nmemb) return 0;
-  if (total_size != (size_t)total_size) return 0;
-  return 1;
-}
-
-void* BrotliSafeMalloc(uint64_t nmemb, size_t size) {
-  if (!CheckSizeArgumentsOverflow(nmemb, size)) return NULL;
-  assert(nmemb * size > 0);
-  return malloc((size_t)(nmemb * size));
-}
-
-#if defined(__cplusplus) || defined(c_plusplus)
-}    /* extern "C" */
-#endif
deleted file mode 100644
--- a/modules/brotli/dec/safe_malloc.h
+++ /dev/null
@@ -1,45 +0,0 @@
-/* Copyright 2013 Google Inc. All Rights Reserved.
-
-   Licensed under the Apache License, Version 2.0 (the "License");
-   you may not use this file except in compliance with the License.
-   You may obtain a copy of the License at
-
-   http://www.apache.org/licenses/LICENSE-2.0
-
-   Unless required by applicable law or agreed to in writing, software
-   distributed under the License is distributed on an "AS IS" BASIS,
-   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-   See the License for the specific language governing permissions and
-   limitations under the License.
-
-   Size-checked memory allocation.
-*/
-
-#ifndef BROTLI_DEC_SAFE_MALLOC_H_
-#define BROTLI_DEC_SAFE_MALLOC_H_
-
-#include <assert.h>
-
-#include "./types.h"
-
-#if defined(__cplusplus) || defined(c_plusplus)
-extern "C" {
-#endif
-
-/* This is the maximum memory amount that we will ever try to allocate. */
-#define BROTLI_MAX_ALLOCABLE_MEMORY (1 << 30)
-
-/* size-checking safe malloc/calloc: verify that the requested size is not too
-   large, or return NULL. You don't need to call these for constructs like
-   malloc(sizeof(foo)), but only if there's font-dependent size involved
-   somewhere (like: malloc(decoded_size * sizeof(*something))). That's why this
-   safe malloc() borrows the signature from calloc(), pointing at the dangerous
-   underlying multiply involved.
-*/
-void* BrotliSafeMalloc(uint64_t nmemb, size_t size);
-
-#if defined(__cplusplus) || defined(c_plusplus)
-}    /* extern "C" */
-#endif
-
-#endif  /* BROTLI_DEC_SAFE_MALLOC_H_ */
new file mode 100644
--- /dev/null
+++ b/modules/brotli/dec/state.c
@@ -0,0 +1,149 @@
+/* Copyright 2015 Google Inc. All Rights Reserved.
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+   http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+*/
+
+#include "./huffman.h"
+#include "./state.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+void BrotliStateInit(BrotliState* s) {
+  s->state = BROTLI_STATE_UNINITED;
+  s->sub0_state = BROTLI_STATE_SUB0_NONE;
+  s->sub1_state = BROTLI_STATE_SUB1_NONE;
+
+  s->block_type_trees = NULL;
+  s->block_len_trees = NULL;
+  s->ringbuffer = NULL;
+
+  s->context_map = NULL;
+  s->context_modes = NULL;
+  s->dist_context_map = NULL;
+  s->context_map_slice = NULL;
+  s->dist_context_map_slice = NULL;
+
+  s->literal_hgroup.codes = NULL;
+  s->literal_hgroup.htrees = NULL;
+  s->insert_copy_hgroup.codes = NULL;
+  s->insert_copy_hgroup.htrees = NULL;
+  s->distance_hgroup.codes = NULL;
+  s->distance_hgroup.htrees = NULL;
+
+  s->custom_dict = NULL;
+  s->custom_dict_size = 0;
+
+  s->input_end = 0;
+  s->window_bits = 0;
+  s->max_distance = 0;
+  s->dist_rb[0] = 16;
+  s->dist_rb[1] = 15;
+  s->dist_rb[2] = 11;
+  s->dist_rb[3] = 4;
+  s->dist_rb_idx = 0;
+  s->block_type_trees = NULL;
+  s->block_len_trees = NULL;
+
+  /* Make small negative indexes addressable. */
+  s->symbol_lists = &s->symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1];
+
+  s->mtf_upper_bound = 255;
+}
+
+void BrotliStateMetablockBegin(BrotliState* s) {
+  s->meta_block_remaining_len = 0;
+  s->block_length[0] = 1 << 28;
+  s->block_length[1] = 1 << 28;
+  s->block_length[2] = 1 << 28;
+  s->num_block_types[0] = 1;
+  s->num_block_types[1] = 1;
+  s->num_block_types[2] = 1;
+  s->block_type_rb[0] = 1;
+  s->block_type_rb[1] = 0;
+  s->block_type_rb[2] = 1;
+  s->block_type_rb[3] = 0;
+  s->block_type_rb[4] = 1;
+  s->block_type_rb[5] = 0;
+  s->context_map = NULL;
+  s->context_modes = NULL;
+  s->dist_context_map = NULL;
+  s->context_map_slice = NULL;
+  s->literal_htree_index = 0;
+  s->literal_htree = NULL;
+  s->dist_context_map_slice = NULL;
+  s->dist_htree_index = 0;
+  s->context_lookup1 = NULL;
+  s->context_lookup2 = NULL;
+  s->literal_hgroup.codes = NULL;
+  s->literal_hgroup.htrees = NULL;
+  s->insert_copy_hgroup.codes = NULL;
+  s->insert_copy_hgroup.htrees = NULL;
+  s->distance_hgroup.codes = NULL;
+  s->distance_hgroup.htrees = NULL;
+}
+
+void BrotliStateCleanupAfterMetablock(BrotliState* s) {
+  if (s->context_modes != 0) {
+    free(s->context_modes);
+    s->context_modes = NULL;
+  }
+  if (s->context_map != 0) {
+    free(s->context_map);
+    s->context_map = NULL;
+  }
+  if (s->dist_context_map != 0) {
+    free(s->dist_context_map);
+    s->dist_context_map = NULL;
+  }
+
+  BrotliHuffmanTreeGroupRelease(&s->literal_hgroup);
+  BrotliHuffmanTreeGroupRelease(&s->insert_copy_hgroup);
+  BrotliHuffmanTreeGroupRelease(&s->distance_hgroup);
+  s->literal_hgroup.codes = NULL;
+  s->literal_hgroup.htrees = NULL;
+  s->insert_copy_hgroup.codes = NULL;
+  s->insert_copy_hgroup.htrees = NULL;
+  s->distance_hgroup.codes = NULL;
+  s->distance_hgroup.htrees = NULL;
+}
+
+void BrotliStateCleanup(BrotliState* s) {
+  if (s->context_modes != 0) {
+    free(s->context_modes);
+  }
+  if (s->context_map != 0) {
+    free(s->context_map);
+  }
+  if (s->dist_context_map != 0) {
+    free(s->dist_context_map);
+  }
+  BrotliHuffmanTreeGroupRelease(&s->literal_hgroup);
+  BrotliHuffmanTreeGroupRelease(&s->insert_copy_hgroup);
+  BrotliHuffmanTreeGroupRelease(&s->distance_hgroup);
+
+  if (s->ringbuffer != 0) {
+    free(s->ringbuffer);
+  }
+  if (s->block_type_trees != 0) {
+    free(s->block_type_trees);
+  }
+}
+
+#if defined(__cplusplus) || defined(c_plusplus)
+} /* extern "C" */
+#endif
new file mode 100644
--- /dev/null
+++ b/modules/brotli/dec/state.h
@@ -0,0 +1,185 @@
+/* Copyright 2015 Google Inc. All Rights Reserved.
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+   http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
+*/
+
+/* Brotli state for partial streaming decoding. */
+
+#ifndef BROTLI_DEC_STATE_H_
+#define BROTLI_DEC_STATE_H_
+
+#include <stdio.h>
+#include "./bit_reader.h"
+#include "./huffman.h"
+#include "./streams.h"
+#include "./types.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+typedef enum {
+  BROTLI_STATE_UNINITED,
+  BROTLI_STATE_BITREADER_WARMUP,
+  BROTLI_STATE_METABLOCK_BEGIN,
+  BROTLI_STATE_METABLOCK_HEADER_1,
+  BROTLI_STATE_METABLOCK_HEADER_2,
+  BROTLI_STATE_COMMAND_BEGIN,
+  BROTLI_STATE_COMMAND_INNER,
+  BROTLI_STATE_UNCOMPRESSED,
+  BROTLI_STATE_METADATA,
+  BROTLI_STATE_COMMAND_INNER_WRITE,
+  BROTLI_STATE_METABLOCK_DONE,
+  BROTLI_STATE_COMMAND_POST_WRITE_1,
+  BROTLI_STATE_COMMAND_POST_WRITE_2,
+  BROTLI_STATE_COMMAND_POST_WRAP_COPY,
+  BROTLI_STATE_HUFFMAN_CODE_0,
+  BROTLI_STATE_HUFFMAN_CODE_1,
+  BROTLI_STATE_HUFFMAN_CODE_2,
+  BROTLI_STATE_CONTEXT_MAP_1,
+  BROTLI_STATE_CONTEXT_MAP_2,
+  BROTLI_STATE_TREE_GROUP,
+  BROTLI_STATE_DONE
+} BrotliRunningState;
+
+typedef enum {
+  BROTLI_STATE_SUB0_NONE,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_SHORT,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_FILL,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_COPY,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_WARMUP,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_1,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_2,
+  BROTLI_STATE_SUB0_UNCOMPRESSED_WRITE_3,
+  BROTLI_STATE_SUB0_TREE_GROUP,
+  BROTLI_STATE_SUB0_CONTEXT_MAP_HUFFMAN,
+  BROTLI_STATE_SUB0_CONTEXT_MAPS
+} BrotliRunningSub0State;
+
+typedef enum {
+  BROTLI_STATE_SUB1_NONE,
+  BROTLI_STATE_SUB1_HUFFMAN_LENGTH_SYMBOLS
+} BrotliRunningSub1State;
+
+typedef struct {
+  BrotliRunningState state;
+  /* This counter is reused for several disjoint loops. */
+  BrotliBitReader br;
+  int loop_counter;
+  int pos;
+  int max_backward_distance;
+  int max_backward_distance_minus_custom_dict_size;
+  int max_distance;
+  int ringbuffer_size;
+  int ringbuffer_mask;
+  int dist_rb_idx;
+  int dist_rb[4];
+  uint8_t* ringbuffer;
+  uint8_t* ringbuffer_end;
+  HuffmanCode* htree_command;
+  const uint8_t* context_lookup1;
+  const uint8_t* context_lookup2;
+  uint8_t* context_map_slice;
+  uint8_t* dist_context_map_slice;
+
+  /* This ring buffer holds a few past copy distances that will be used by */
+  /* some special distance codes. */
+  HuffmanTreeGroup literal_hgroup;
+  HuffmanTreeGroup insert_copy_hgroup;
+  HuffmanTreeGroup distance_hgroup;
+  HuffmanCode* block_type_trees;
+  HuffmanCode* block_len_trees;
+  /* This is true if the literal context map histogram type always matches the
+  block type. It is then not needed to keep the context (faster decoding). */
+  int trivial_literal_context;
+  int distance_context;
+  int meta_block_remaining_len;
+  int block_length[3];
+  int num_block_types[3];
+  int block_type_rb[6];
+  int distance_postfix_bits;
+  int num_direct_distance_codes;
+  int distance_postfix_mask;
+  uint8_t* dist_context_map;
+  uint8_t literal_htree_index;
+  HuffmanCode *literal_htree;
+  uint8_t dist_htree_index;
+  uint8_t repeat_code_len;
+  uint8_t prev_code_len;
+
+  int copy_length;
+  int distance_code;
+
+  /* For partial write operations */
+  int to_write;
+  int partially_written;
+
+  /* For ReadHuffmanCode */
+  uint32_t symbol;
+  uint32_t repeat;
+  uint32_t space;
+
+  HuffmanCode table[32];
+  /* List of of symbol chains. */
+  uint16_t* symbol_lists;
+  /* Storage from symbol_lists. */
+  uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 +
+      BROTLI_HUFFMAN_MAX_CODE_LENGTHS_SIZE];
+  /* Tails of symbol chains. */
+  int next_symbol[32];
+  uint8_t code_length_code_lengths[18];
+  /* Population counts for the code lengths */
+  uint16_t code_length_histo[16];
+
+  /* For HuffmanTreeGroupDecode */
+  int htree_index;
+  HuffmanCode* next;
+
+  /* For DecodeContextMap */
+  int context_index;
+  int max_run_length_prefix;
+  HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_TABLE_SIZE];
+
+  /* For InverseMoveToFrontTransform */
+  int mtf_upper_bound;
+  uint8_t mtf[256];
+
+  /* For custom dictionaries */
+  const uint8_t* custom_dict;
+  int custom_dict_size;
+
+  /* less used attributes are in the end of this struct */
+  BrotliRunningSub0State sub0_state;  /* State inside function call */
+  BrotliRunningSub1State sub1_state;  /* State inside function call */
+
+  int input_end;
+  uint32_t window_bits;
+
+  /* For CopyUncompressedBlockToOutput */
+  int nbytes;
+
+  int num_literal_htrees;
+  uint8_t* context_map;
+  uint8_t* context_modes;
+} BrotliState;
+
+void BrotliStateInit(BrotliState* s);
+void BrotliStateCleanup(BrotliState* s);
+void BrotliStateMetablockBegin(BrotliState* s);
+void BrotliStateCleanupAfterMetablock(BrotliState* s);
+
+#if defined(__cplusplus) || defined(c_plusplus)
+} /* extern "C" */
+#endif
+
+#endif  /* BROTLI_DEC_STATE_H_ */
--- a/modules/brotli/dec/streams.c
+++ b/modules/brotli/dec/streams.c
@@ -6,19 +6,19 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Functions for streaming input and output.
-*/
+/* Functions for streaming input and output. */
 
 #include <string.h>
 #ifndef _WIN32
 #include <unistd.h>
 #endif
 #include "./streams.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
@@ -46,18 +46,19 @@ BrotliInput BrotliInitMemInput(const uin
   mem_input->pos = 0;
   input.cb_ = &BrotliMemInputFunction;
   input.data_ = mem_input;
   return input;
 }
 
 int BrotliMemOutputFunction(void* data, const uint8_t* buf, size_t count) {
   BrotliMemOutput* output = (BrotliMemOutput*)data;
-  if (output->pos + count > output->length) {
-    return -1;
+  size_t limit = output->length - output->pos;
+  if (count > limit) {
+    count = limit;
   }
   memcpy(output->buffer + output->pos, buf, count);
   output->pos += count;
   return (int)count;
 }
 
 BrotliOutput BrotliInitMemOutput(uint8_t* buffer, size_t length,
                                  BrotliMemOutput* mem_output) {
@@ -65,48 +66,16 @@ BrotliOutput BrotliInitMemOutput(uint8_t
   mem_output->buffer = buffer;
   mem_output->length = length;
   mem_output->pos = 0;
   output.cb_ = &BrotliMemOutputFunction;
   output.data_ = mem_output;
   return output;
 }
 
-int BrotliStdinInputFunction(void* data, uint8_t* buf, size_t count) {
-  (void) data; /* Shut up LLVM */
-#ifndef _WIN32
-  return (int)read(STDIN_FILENO, buf, count);
-#else
-  return -1;
-#endif
-}
-
-BrotliInput BrotliStdinInput() {
-  BrotliInput in;
-  in.cb_ = BrotliStdinInputFunction;
-  in.data_ = NULL;
-  return in;
-}
-
-int BrotliStdoutOutputFunction(void* data, const uint8_t* buf, size_t count) {
-  (void) data; /* Shut up LLVM */
-#ifndef _WIN32
-  return (int)write(STDOUT_FILENO, buf, count);
-#else
-  return -1;
-#endif
-}
-
-BrotliOutput BrotliStdoutOutput() {
-  BrotliOutput out;
-  out.cb_ = BrotliStdoutOutputFunction;
-  out.data_ = NULL;
-  return out;
-}
-
 int BrotliFileInputFunction(void* data, uint8_t* buf, size_t count) {
   return (int)fread(buf, 1, count, (FILE*)data);
 }
 
 BrotliInput BrotliFileInput(FILE* f) {
   BrotliInput in;
   in.cb_ = BrotliFileInputFunction;
   in.data_ = f;
--- a/modules/brotli/dec/streams.h
+++ b/modules/brotli/dec/streams.h
@@ -6,24 +6,25 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Functions for streaming input and output.
-*/
+/* Functions for streaming input and output. */
 
 #ifndef BROTLI_DEC_STREAMS_H_
 #define BROTLI_DEC_STREAMS_H_
 
 #include <stdio.h>
+#include "./port.h"
 #include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
 /* Function pointer type used to read len bytes into buf. Returns the */
 /* number of bytes read or -1 on error. */
@@ -79,24 +80,16 @@ typedef struct {
 
 /* Output callback where *data is a BrotliMemOutput struct. */
 int BrotliMemOutputFunction(void* data, const uint8_t* buf, size_t count);
 
 /* Returns an output callback that wraps the given memory region. */
 BrotliOutput BrotliInitMemOutput(uint8_t* buffer, size_t length,
                                  BrotliMemOutput* mem_output);
 
-/* Input callback that reads from standard input. */
-int BrotliStdinInputFunction(void* data, uint8_t* buf, size_t count);
-BrotliInput BrotliStdinInput();
-
-/* Output callback that writes to standard output. */
-int BrotliStdoutOutputFunction(void* data, const uint8_t* buf, size_t count);
-BrotliOutput BrotliStdoutOutput();
-
 /* Input callback that reads from a file. */
 int BrotliFileInputFunction(void* data, uint8_t* buf, size_t count);
 BrotliInput BrotliFileInput(FILE* f);
 
 /* Output callback that writes to a file. */
 int BrotliFileOutputFunction(void* data, const uint8_t* buf, size_t count);
 BrotliOutput BrotliFileOutput(FILE* f);
 
--- a/modules/brotli/dec/transform.h
+++ b/modules/brotli/dec/transform.h
@@ -6,25 +6,26 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Transformations on dictionary words.
-*/
+/* Transformations on dictionary words. */
 
 #ifndef BROTLI_DEC_TRANSFORM_H_
 #define BROTLI_DEC_TRANSFORM_H_
 
 #include <stdio.h>
 #include <ctype.h>
+#include "./port.h"
 #include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
 enum WordTransformType {
   kIdentity       = 0,
@@ -46,143 +47,212 @@ enum WordTransformType {
   kOmitFirst5     = 16,
   kOmitFirst6     = 17,
   kOmitFirst7     = 18,
   kOmitFirst8     = 19,
   kOmitFirst9     = 20
 };
 
 typedef struct {
-  const char* prefix;
-  enum WordTransformType transform;
-  const char* suffix;
+  const uint8_t prefix_id;
+  const uint8_t transform;
+  const uint8_t suffix_id;
 } Transform;
 
+static const char kPrefixSuffix[208] =
+    "\0 \0, \0 of the \0 of \0s \0.\0 and \0 in \0\"\0 to \0\">\0\n\0. \0]\0"
+    " for \0 a \0 that \0\'\0 with \0 from \0 by \0(\0. The \0 on \0 as \0"
+    " is \0ing \0\n\t\0:\0ed \0=\"\0 at \0ly \0,\0=\'\0.com/\0. This \0"
+    " not \0er \0al \0ful \0ive \0less \0est \0ize \0\xc2\xa0\0ous ";
+
+enum {
+  /* EMPTY = ""
+     SP = " "
+     DQUOT = "\""
+     SQUOT = "'"
+     CLOSEBR = "]"
+     OPEN = "("
+     SLASH = "/"
+     NBSP = non-breaking space "\0xc2\xa0"
+  */
+  kPFix_EMPTY = 0,
+  kPFix_SP = 1,
+  kPFix_COMMASP = 3,
+  kPFix_SPofSPtheSP = 6,
+  kPFix_SPtheSP  = 9,
+  kPFix_eSP = 12,
+  kPFix_SPofSP  = 15,
+  kPFix_sSP = 20,
+  kPFix_DOT = 23,
+  kPFix_SPandSP = 25,
+  kPFix_SPinSP = 31,
+  kPFix_DQUOT = 36,
+  kPFix_SPtoSP  = 38,
+  kPFix_DQUOTGT = 43,
+  kPFix_NEWLINE = 46,
+  kPFix_DOTSP = 48,
+  kPFix_CLOSEBR = 51,
+  kPFix_SPforSP = 53,
+  kPFix_SPaSP = 59,
+  kPFix_SPthatSP = 63,
+  kPFix_SQUOT = 70,
+  kPFix_SPwithSP = 72,
+  kPFix_SPfromSP  = 79,
+  kPFix_SPbySP  = 86,
+  kPFix_OPEN = 91,
+  kPFix_DOTSPTheSP = 93,
+  kPFix_SPonSP  = 100,
+  kPFix_SPasSP  = 105,
+  kPFix_SPisSP  = 110,
+  kPFix_ingSP = 115,
+  kPFix_NEWLINETAB = 120,
+  kPFix_COLON = 123,
+  kPFix_edSP = 125,
+  kPFix_EQDQUOT = 129,
+  kPFix_SPatSP = 132,
+  kPFix_lySP  = 137,
+  kPFix_COMMA = 141,
+  kPFix_EQSQUOT = 143,
+  kPFix_DOTcomSLASH = 146,
+  kPFix_DOTSPThisSP = 152,
+  kPFix_SPnotSP = 160,
+  kPFix_erSP = 166,
+  kPFix_alSP = 170,
+  kPFix_fulSP = 174,
+  kPFix_iveSP = 179,
+  kPFix_lessSP = 184,
+  kPFix_estSP = 190,
+  kPFix_izeSP = 195,
+  kPFix_NBSP = 200,
+  kPFix_ousSP = 203
+};
+
+
 static const Transform kTransforms[] = {
-     {         "", kIdentity,       ""           },
-     {         "", kIdentity,       " "          },
-     {        " ", kIdentity,       " "          },
-     {         "", kOmitFirst1,     ""           },
-     {         "", kUppercaseFirst, " "          },
-     {         "", kIdentity,       " the "      },
-     {        " ", kIdentity,       ""           },
-     {       "s ", kIdentity,       " "          },
-     {         "", kIdentity,       " of "       },
-     {         "", kUppercaseFirst, ""           },
-     {         "", kIdentity,       " and "      },
-     {         "", kOmitFirst2,     ""           },
-     {         "", kOmitLast1,      ""           },
-     {       ", ", kIdentity,       " "          },
-     {         "", kIdentity,       ", "         },
-     {        " ", kUppercaseFirst, " "          },
-     {         "", kIdentity,       " in "       },
-     {         "", kIdentity,       " to "       },
-     {       "e ", kIdentity,       " "          },
-     {         "", kIdentity,       "\""         },
-     {         "", kIdentity,       "."          },
-     {         "", kIdentity,       "\">"        },
-     {         "", kIdentity,       "\n"         },
-     {         "", kOmitLast3,      ""           },
-     {         "", kIdentity,       "]"          },
-     {         "", kIdentity,       " for "      },
-     {         "", kOmitFirst3,     ""           },
-     {         "", kOmitLast2,      ""           },
-     {         "", kIdentity,       " a "        },
-     {         "", kIdentity,       " that "     },
-     {        " ", kUppercaseFirst, ""           },
-     {         "", kIdentity,       ". "         },
-     {        ".", kIdentity,       ""           },
-     {        " ", kIdentity,       ", "         },
-     {         "", kOmitFirst4,     ""           },
-     {         "", kIdentity,       " with "     },
-     {         "", kIdentity,       "'"          },
-     {         "", kIdentity,       " from "     },
-     {         "", kIdentity,       " by "       },
-     {         "", kOmitFirst5,     ""           },
-     {         "", kOmitFirst6,     ""           },
-     {    " the ", kIdentity,       ""           },
-     {         "", kOmitLast4,      ""           },
-     {         "", kIdentity,       ". The "     },
-     {         "", kUppercaseAll,   ""           },
-     {         "", kIdentity,       " on "       },
-     {         "", kIdentity,       " as "       },
-     {         "", kIdentity,       " is "       },
-     {         "", kOmitLast7,      ""           },
-     {         "", kOmitLast1,      "ing "       },
-     {         "", kIdentity,       "\n\t"       },
-     {         "", kIdentity,       ":"          },
-     {        " ", kIdentity,       ". "         },
-     {         "", kIdentity,       "ed "        },
-     {         "", kOmitFirst9,     ""           },
-     {         "", kOmitFirst7,     ""           },
-     {         "", kOmitLast6,      ""           },
-     {         "", kIdentity,       "("          },
-     {         "", kUppercaseFirst, ", "         },
-     {         "", kOmitLast8,      ""           },
-     {         "", kIdentity,       " at "       },
-     {         "", kIdentity,       "ly "        },
-     {    " the ", kIdentity,       " of "       },
-     {         "", kOmitLast5,      ""           },
-     {         "", kOmitLast9,      ""           },
-     {        " ", kUppercaseFirst, ", "         },
-     {         "", kUppercaseFirst, "\""         },
-     {        ".", kIdentity,       "("          },
-     {         "", kUppercaseAll,   " "          },
-     {         "", kUppercaseFirst, "\">"        },
-     {         "", kIdentity,       "=\""        },
-     {        " ", kIdentity,       "."          },
-     {    ".com/", kIdentity,       ""           },
-     {    " the ", kIdentity,       " of the "   },
-     {         "", kUppercaseFirst, "'"          },
-     {         "", kIdentity,       ". This "    },
-     {         "", kIdentity,       ","          },
-     {        ".", kIdentity,       " "          },
-     {         "", kUppercaseFirst, "("          },
-     {         "", kUppercaseFirst, "."          },
-     {         "", kIdentity,       " not "      },
-     {        " ", kIdentity,       "=\""        },
-     {         "", kIdentity,       "er "        },
-     {        " ", kUppercaseAll,   " "          },
-     {         "", kIdentity,       "al "        },
-     {        " ", kUppercaseAll,   ""           },
-     {         "", kIdentity,       "='"         },
-     {         "", kUppercaseAll,   "\""         },
-     {         "", kUppercaseFirst, ". "         },
-     {        " ", kIdentity,       "("          },
-     {         "", kIdentity,       "ful "       },
-     {        " ", kUppercaseFirst, ". "         },
-     {         "", kIdentity,       "ive "       },
-     {         "", kIdentity,       "less "      },
-     {         "", kUppercaseAll,   "'"          },
-     {         "", kIdentity,       "est "       },
-     {        " ", kUppercaseFirst, "."          },
-     {         "", kUppercaseAll,   "\">"        },
-     {        " ", kIdentity,       "='"         },
-     {         "", kUppercaseFirst, ","          },
-     {         "", kIdentity,       "ize "       },
-     {         "", kUppercaseAll,   "."          },
-     { "\xc2\xa0", kIdentity,       ""           },
-     {        " ", kIdentity,       ","          },
-     {         "", kUppercaseFirst, "=\""        },
-     {         "", kUppercaseAll,   "=\""        },
-     {         "", kIdentity,       "ous "       },
-     {         "", kUppercaseAll,   ", "         },
-     {         "", kUppercaseFirst, "='"         },
-     {        " ", kUppercaseFirst, ","          },
-     {        " ", kUppercaseAll,   "=\""        },
-     {        " ", kUppercaseAll,   ", "         },
-     {         "", kUppercaseAll,   ","          },
-     {         "", kUppercaseAll,   "("          },
-     {         "", kUppercaseAll,   ". "         },
-     {        " ", kUppercaseAll,   "."          },
-     {         "", kUppercaseAll,   "='"         },
-     {        " ", kUppercaseAll,   ". "         },
-     {        " ", kUppercaseFirst, "=\""        },
-     {        " ", kUppercaseAll,   "='"         },
-     {        " ", kUppercaseFirst, "='"         },
+  { kPFix_EMPTY, kIdentity, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_SP },
+  { kPFix_SP, kIdentity, kPFix_SP },
+  { kPFix_EMPTY, kOmitFirst1, kPFix_EMPTY },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_SP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPtheSP },
+  { kPFix_SP, kIdentity, kPFix_EMPTY },
+  { kPFix_sSP, kIdentity, kPFix_SP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPofSP },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_SPandSP },
+  { kPFix_EMPTY, kOmitFirst2, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitLast1, kPFix_EMPTY },
+  { kPFix_COMMASP, kIdentity, kPFix_SP },
+  { kPFix_EMPTY, kIdentity, kPFix_COMMASP },
+  { kPFix_SP, kUppercaseFirst, kPFix_SP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPinSP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPtoSP },
+  { kPFix_eSP, kIdentity, kPFix_SP },
+  { kPFix_EMPTY, kIdentity, kPFix_DQUOT },
+  { kPFix_EMPTY, kIdentity, kPFix_DOT },
+  { kPFix_EMPTY, kIdentity, kPFix_DQUOTGT },
+  { kPFix_EMPTY, kIdentity, kPFix_NEWLINE },
+  { kPFix_EMPTY, kOmitLast3, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_CLOSEBR },
+  { kPFix_EMPTY, kIdentity, kPFix_SPforSP },
+  { kPFix_EMPTY, kOmitFirst3, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitLast2, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_SPaSP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPthatSP },
+  { kPFix_SP, kUppercaseFirst, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_DOTSP },
+  { kPFix_DOT, kIdentity, kPFix_EMPTY },
+  { kPFix_SP, kIdentity, kPFix_COMMASP },
+  { kPFix_EMPTY, kOmitFirst4, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_SPwithSP },
+  { kPFix_EMPTY, kIdentity, kPFix_SQUOT },
+  { kPFix_EMPTY, kIdentity, kPFix_SPfromSP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPbySP },
+  { kPFix_EMPTY, kOmitFirst5, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitFirst6, kPFix_EMPTY },
+  { kPFix_SPtheSP, kIdentity, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitLast4, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_DOTSPTheSP },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_SPonSP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPasSP },
+  { kPFix_EMPTY, kIdentity, kPFix_SPisSP },
+  { kPFix_EMPTY, kOmitLast7, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitLast1, kPFix_ingSP },
+  { kPFix_EMPTY, kIdentity, kPFix_NEWLINETAB },
+  { kPFix_EMPTY, kIdentity, kPFix_COLON },
+  { kPFix_SP, kIdentity, kPFix_DOTSP },
+  { kPFix_EMPTY, kIdentity, kPFix_edSP },
+  { kPFix_EMPTY, kOmitFirst9, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitFirst7, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitLast6, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_OPEN },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_COMMASP },
+  { kPFix_EMPTY, kOmitLast8, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_SPatSP },
+  { kPFix_EMPTY, kIdentity, kPFix_lySP },
+  { kPFix_SPtheSP, kIdentity, kPFix_SPofSP },
+  { kPFix_EMPTY, kOmitLast5, kPFix_EMPTY },
+  { kPFix_EMPTY, kOmitLast9, kPFix_EMPTY },
+  { kPFix_SP, kUppercaseFirst, kPFix_COMMASP },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_DQUOT },
+  { kPFix_DOT, kIdentity, kPFix_OPEN },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_SP },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_DQUOTGT },
+  { kPFix_EMPTY, kIdentity, kPFix_EQDQUOT },
+  { kPFix_SP, kIdentity, kPFix_DOT },
+  { kPFix_DOTcomSLASH, kIdentity, kPFix_EMPTY },
+  { kPFix_SPtheSP, kIdentity, kPFix_SPofSPtheSP },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_SQUOT },
+  { kPFix_EMPTY, kIdentity, kPFix_DOTSPThisSP },
+  { kPFix_EMPTY, kIdentity, kPFix_COMMA },
+  { kPFix_DOT, kIdentity, kPFix_SP },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_OPEN },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_DOT },
+  { kPFix_EMPTY, kIdentity, kPFix_SPnotSP },
+  { kPFix_SP, kIdentity, kPFix_EQDQUOT },
+  { kPFix_EMPTY, kIdentity, kPFix_erSP },
+  { kPFix_SP, kUppercaseAll, kPFix_SP },
+  { kPFix_EMPTY, kIdentity, kPFix_alSP },
+  { kPFix_SP, kUppercaseAll, kPFix_EMPTY },
+  { kPFix_EMPTY, kIdentity, kPFix_EQSQUOT },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_DQUOT },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_DOTSP },
+  { kPFix_SP, kIdentity, kPFix_OPEN },
+  { kPFix_EMPTY, kIdentity, kPFix_fulSP },
+  { kPFix_SP, kUppercaseFirst, kPFix_DOTSP },
+  { kPFix_EMPTY, kIdentity, kPFix_iveSP },
+  { kPFix_EMPTY, kIdentity, kPFix_lessSP },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_SQUOT },
+  { kPFix_EMPTY, kIdentity, kPFix_estSP },
+  { kPFix_SP, kUppercaseFirst, kPFix_DOT },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_DQUOTGT },
+  { kPFix_SP, kIdentity, kPFix_EQSQUOT },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_COMMA },
+  { kPFix_EMPTY, kIdentity, kPFix_izeSP },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_DOT },
+  { kPFix_NBSP, kIdentity, kPFix_EMPTY },
+  { kPFix_SP, kIdentity, kPFix_COMMA },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_EQDQUOT },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_EQDQUOT },
+  { kPFix_EMPTY, kIdentity, kPFix_ousSP },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_COMMASP },
+  { kPFix_EMPTY, kUppercaseFirst, kPFix_EQSQUOT },
+  { kPFix_SP, kUppercaseFirst, kPFix_COMMA },
+  { kPFix_SP, kUppercaseAll, kPFix_EQDQUOT },
+  { kPFix_SP, kUppercaseAll, kPFix_COMMASP },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_COMMA },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_OPEN },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_DOTSP },
+  { kPFix_SP, kUppercaseAll, kPFix_DOT },
+  { kPFix_EMPTY, kUppercaseAll, kPFix_EQSQUOT },
+  { kPFix_SP, kUppercaseAll, kPFix_DOTSP },
+  { kPFix_SP, kUppercaseFirst, kPFix_EQDQUOT },
+  { kPFix_SP, kUppercaseAll, kPFix_EQSQUOT },
+  { kPFix_SP, kUppercaseFirst, kPFix_EQSQUOT },
 };
 
 static const int kNumTransforms = sizeof(kTransforms) / sizeof(kTransforms[0]);
 
 static int ToUpperCase(uint8_t *p) {
   if (p[0] < 0xc0) {
     if (p[0] >= 'a' && p[0] <= 'z') {
       p[0] ^= 32;
@@ -194,46 +264,52 @@ static int ToUpperCase(uint8_t *p) {
     p[1] ^= 32;
     return 2;
   }
   /* An arbitrary transform for three byte characters. */
   p[2] ^= 5;
   return 3;
 }
 
-static BROTLI_INLINE int TransformDictionaryWord(
+static BROTLI_NOINLINE int TransformDictionaryWord(
     uint8_t* dst, const uint8_t* word, int len, int transform) {
-  const char* prefix = kTransforms[transform].prefix;
-  const char* suffix = kTransforms[transform].suffix;
-  const int t = kTransforms[transform].transform;
-  int skip = t < kOmitFirst1 ? 0 : t - (kOmitFirst1 - 1);
   int idx = 0;
-  int i = 0;
-  uint8_t* uppercase;
-  if (skip > len) {
-    skip = len;
+  {
+    const char* prefix = &kPrefixSuffix[kTransforms[transform].prefix_id];
+    while (*prefix) { dst[idx++] = (uint8_t)*prefix++; }
   }
-  while (*prefix) { dst[idx++] = (uint8_t)*prefix++; }
-  word += skip;
-  len -= skip;
-  if (t <= kOmitLast9) {
-    len -= t;
-  }
-  while (i < len) { dst[idx++] = word[i++]; }
-  uppercase = &dst[idx - len];
-  if (t == kUppercaseFirst) {
-    ToUpperCase(uppercase);
-  } else if (t == kUppercaseAll) {
-    while (len > 0) {
-      int step = ToUpperCase(uppercase);
-      uppercase += step;
-      len -= step;
+  {
+    const int t = kTransforms[transform].transform;
+    int skip = t < kOmitFirst1 ? 0 : t - (kOmitFirst1 - 1);
+    int i = 0;
+    uint8_t* uppercase;
+    if (skip > len) {
+      skip = len;
+    }
+    word += skip;
+    len -= skip;
+    if (t <= kOmitLast9) {
+      len -= t;
+    }
+    while (i < len) { dst[idx++] = word[i++]; }
+    uppercase = &dst[idx - len];
+    if (t == kUppercaseFirst) {
+      ToUpperCase(uppercase);
+    } else if (t == kUppercaseAll) {
+      while (len > 0) {
+        int step = ToUpperCase(uppercase);
+        uppercase += step;
+        len -= step;
+      }
     }
   }
-  while (*suffix) { dst[idx++] = (uint8_t)*suffix++; }
-  return idx;
+  {
+    const char* suffix = &kPrefixSuffix[kTransforms[transform].suffix_id];
+    while (*suffix) { dst[idx++] = (uint8_t)*suffix++; }
+    return idx;
+  }
 }
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }    /* extern "C" */
 #endif
 
 #endif  /* BROTLI_DEC_TRANSFORM_H_ */
--- a/modules/brotli/dec/types.h
+++ b/modules/brotli/dec/types.h
@@ -6,38 +6,31 @@
 
    http://www.apache.org/licenses/LICENSE-2.0
 
    Unless required by applicable law or agreed to in writing, software
    distributed under the License is distributed on an "AS IS" BASIS,
    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    See the License for the specific language governing permissions and
    limitations under the License.
+*/
 
-   Common types
-*/
+/* Common types */
 
 #ifndef BROTLI_DEC_TYPES_H_
 #define BROTLI_DEC_TYPES_H_
 
 #include <stddef.h>  /* for size_t */
 
-#ifndef _MSC_VER
-#include <inttypes.h>
-#if defined(__cplusplus) || !defined(__STRICT_ANSI__) \
-    || __STDC_VERSION__ >= 199901L
-#define BROTLI_INLINE inline
-#else
-#define BROTLI_INLINE
-#endif
-#else
+#if defined(_MSC_VER) && (_MSC_VER < 1600)
 typedef signed   char int8_t;
 typedef unsigned char uint8_t;
 typedef signed   short int16_t;
 typedef unsigned short uint16_t;
 typedef signed   int int32_t;
 typedef unsigned int uint32_t;
 typedef unsigned long long int uint64_t;
 typedef long long int int64_t;
-#define BROTLI_INLINE __forceinline
-#endif  /* _MSC_VER */
+#else
+#include <stdint.h>
+#endif  /* defined(_MSC_VER) && (_MSC_VER < 1600) */
 
 #endif  /* BROTLI_DEC_TYPES_H_ */
--- a/modules/brotli/moz.build
+++ b/modules/brotli/moz.build
@@ -1,21 +1,27 @@
 # -*- Mode: python; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 40 -*-
 # vim: set filetype=python:
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 EXPORTS += [
+    'dec/bit_reader.h',
     'dec/decode.h',
+    'dec/huffman.h',
+    'dec/port.h',
+    'dec/state.h',
     'dec/streams.h',
     'dec/types.h',
 ]
 
 UNIFIED_SOURCES += [
     'dec/bit_reader.c',
     'dec/decode.c',
     'dec/huffman.c',
-    'dec/safe_malloc.c',
+    'dec/state.c',
     'dec/streams.c',
 ]
 
+ALLOW_COMPILER_WARNINGS = True
+
 Library('brotli')