Add brotli decompressor

This commit is for the decoder for brotli compression format.
Brotli is a generic byte-level compression algorithm.

13 files changed, 1935 insertions, 0 deletions

diff --git a/brotli/LICENSE b/brotli/LICENSE
new file mode 100644
index 0000000..d645695
--- /dev/null
+++ b/brotli/LICENSE
@@ -0,0 +1,202 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   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.
diff --git a/brotli/dec/README b/brotli/dec/README
new file mode 100644
index 0000000..933bdfd
--- /dev/null
+++ b/brotli/dec/README
@@ -0,0 +1,3 @@
+This directory holds the decoder for brotli compression format.
+
+Brotli is proposed to be used at the byte-compression level in WOFF 2.0 format.
diff --git a/brotli/dec/bit_reader.c b/brotli/dec/bit_reader.c
new file mode 100644
index 0000000..858afcb
--- /dev/null
+++ b/brotli/dec/bit_reader.c
@@ -0,0 +1,122 @@
+// 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.
+//
+// Bit reading helpers
+
+#include <assert.h>
+
+#include "./bit_reader.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+#define MAX_NUM_BIT_READ 25
+
+#define LBITS 64      // Number of bits prefetched.
+#define WBITS 32      // Minimum number of bytes needed after
+                      // BrotliFillBitWindow.
+#define LOG8_WBITS 4  // Number of bytes needed to store WBITS bits.
+
+static const uint32_t kBitMask[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
+};
+
+void BrotliInitBitReader(BrotliBitReader* const br,
+                         const uint8_t* const start,
+                         size_t length) {
+  size_t i;
+  assert(br != NULL);
+  assert(start != NULL);
+  assert(length < 0xfffffff8u);   // can't happen with a RIFF chunk.
+
+  br->buf_ = start;
+  br->len_ = length;
+  br->val_ = 0;
+  br->pos_ = 0;
+  br->bit_pos_ = 0;
+  br->eos_ = 0;
+  br->error_ = 0;
+  for (i = 0; i < sizeof(br->val_) && i < br->len_; ++i) {
+    br->val_ |= ((uint64_t)br->buf_[br->pos_]) << (8 * i);
+    ++br->pos_;
+  }
+}
+
+void BrotliBitReaderSetBuffer(BrotliBitReader* const br,
+                              const uint8_t* const buf, size_t len) {
+  assert(br != NULL);
+  assert(buf != NULL);
+  assert(len < 0xfffffff8u);   // can't happen with a RIFF chunk.
+  br->eos_ = (br->pos_ >= len);
+  br->buf_ = buf;
+  br->len_ = len;
+}
+
+// If not at EOS, reload up to LBITS byte-by-byte
+static void ShiftBytes(BrotliBitReader* const br) {
+  while (br->bit_pos_ >= 8 && br->pos_ < br->len_) {
+    br->val_ >>= 8;
+    br->val_ |= ((uint64_t)br->buf_[br->pos_]) << (LBITS - 8);
+    ++br->pos_;
+    br->bit_pos_ -= 8;
+  }
+}
+
+void BrotliFillBitWindow(BrotliBitReader* const br) {
+  if (br->bit_pos_ >= WBITS) {
+#if (defined(__x86_64__) || defined(_M_X64))
+    if (br->pos_ + sizeof(br->val_) < br->len_) {
+      br->val_ >>= WBITS;
+      br->bit_pos_ -= WBITS;
+      // The expression below needs a little-endian arch to work correctly.
+      // This gives a large speedup for decoding speed.
+      br->val_ |= *(const uint64_t*)(br->buf_ + br->pos_) << (LBITS - WBITS);
+      br->pos_ += LOG8_WBITS;
+      return;
+    }
+#endif
+    ShiftBytes(br);       // Slow path.
+    if (br->pos_ == br->len_ && br->bit_pos_ == LBITS) {
+      br->eos_ = 1;
+    }
+  }
+}
+
+uint32_t BrotliReadBits(BrotliBitReader* const br, int n_bits) {
+  assert(n_bits >= 0);
+  // Flag an error if end_of_stream or n_bits is more than allowed limit.
+  if (n_bits == 0 || (!br->eos_ && n_bits < MAX_NUM_BIT_READ)) {
+    const uint32_t val =
+        (uint32_t)(br->val_ >> br->bit_pos_) & kBitMask[n_bits];
+    const int new_bits = br->bit_pos_ + n_bits;
+    br->bit_pos_ = new_bits;
+    // If this read is going to cross the read buffer, set the eos flag.
+    if (br->pos_ == br->len_) {
+      if (new_bits >= LBITS) {
+        br->eos_ = 1;
+      }
+    }
+    ShiftBytes(br);
+    return val;
+  } else {
+    br->error_ = 1;
+    return 0;
+  }
+}
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif
diff --git a/brotli/dec/bit_reader.h b/brotli/dec/bit_reader.h
new file mode 100644
index 0000000..8ee16e5
--- /dev/null
+++ b/brotli/dec/bit_reader.h
@@ -0,0 +1,67 @@
+// 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.
+//
+// Bit reading helpers
+
+#ifndef BROTLI_DEC_BIT_READER_H_
+#define BROTLI_DEC_BIT_READER_H_
+
+#include "./types.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+typedef struct {
+  uint64_t       val_;        // pre-fetched bits
+  const uint8_t* buf_;        // input byte buffer
+  size_t         len_;        // buffer length
+  size_t         pos_;        // byte position in buf_
+  int            bit_pos_;    // current bit-reading position in val_
+  int            eos_;        // bitstream is finished
+  int            error_;      // an error occurred (buffer overflow attempt...)
+} BrotliBitReader;
+
+void BrotliInitBitReader(BrotliBitReader* const br,
+                         const uint8_t* const start,
+                         size_t length);
+
+//  Sets a new data buffer.
+void BrotliBitReaderSetBuffer(BrotliBitReader* const br,
+                              const uint8_t* const buffer, size_t length);
+
+// Reads the specified number of bits from Read Buffer.
+// Flags an error in case end_of_stream or n_bits is more than allowed limit.
+// Flags eos if this read attempt is going to cross the read buffer.
+uint32_t BrotliReadBits(BrotliBitReader* const br, int n_bits);
+
+// 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, int val) {
+  br->bit_pos_ = val;
+}
+
+// Advances the Read buffer by 4 bytes to make room for reading next 32 bits.
+void BrotliFillBitWindow(BrotliBitReader* const br);
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif
+
+#endif  // BROTLI_DEC_BIT_READER_H_
diff --git a/brotli/dec/context.h b/brotli/dec/context.h
new file mode 100644
index 0000000..0b1abd1
--- /dev/null
+++ b/brotli/dec/context.h
@@ -0,0 +1,124 @@
+// 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.
+//
+// Lookup tables to map the previous one to three bytes to a context id.
+
+#ifndef BROTLI_DEC_CONTEXT_H_
+#define BROTLI_DEC_CONTEXT_H_
+
+
+#include "./types.h"
+
+static const int kSigned2BitContextLookup[] = {
+  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3,
+};
+
+static const int kSigned3BitContextLookup[] = {
+  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
+  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
+  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7,
+};
+
+static const int kSigned4BitContextLookup[] = {
+   0,  1,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  4,  4,  4,  4,
+   5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
+   6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
+   6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
+   7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
+   7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
+   7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
+   7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
+   8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
+   8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
+   8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
+   8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
+   9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
+   9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
+  10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
+  11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 15,
+};
+
+enum ContextType {
+  CONTEXT_FULL        = 0,
+  CONTEXT_MSB7        = 1,
+  CONTEXT_MSB6        = 2,
+  CONTEXT_MSB5        = 3,
+  CONTEXT_MSB4        = 4,
+  CONTEXT_MSB3        = 5,
+  CONTEXT_MSB2        = 6,
+  CONTEXT_MSB1        = 7,
+  CONTEXT_IS_ZERO     = 8,
+  CONTEXT_SIGNED_2BIT = 9,
+  CONTEXT_SIGNED_3BIT = 10,
+  CONTEXT_SIGNED_4BIT = 11,
+  CONTEXT_SIGNED_MIXED_3BYTE = 12,
+};
+
+static const int kContextSize[] = {
+  256, 128, 64, 32, 16, 8, 4, 2, 2, 4, 8, 16, 64,
+};
+
+static BROTLI_INLINE int NumContexts(int mode) {
+  return kContextSize[mode];
+}
+
+static BROTLI_INLINE uint8_t Context(uint8_t prev_byte, uint8_t prev_byte2,
+                                     uint8_t prev_byte3, int mode) {
+  switch (mode) {
+    case CONTEXT_IS_ZERO:
+      return prev_byte == 0 ? 0 : 1;
+    case CONTEXT_SIGNED_2BIT:
+      return kSigned2BitContextLookup[prev_byte];
+    case CONTEXT_SIGNED_3BIT:
+      return kSigned3BitContextLookup[prev_byte];
+    case CONTEXT_SIGNED_4BIT:
+      return kSigned4BitContextLookup[prev_byte];
+    case CONTEXT_SIGNED_MIXED_3BYTE:
+      return ((kSigned3BitContextLookup[prev_byte] << 3) +
+              (kSigned2BitContextLookup[prev_byte2] << 1) +
+              (prev_byte3 == 0 ? 0 : 1));
+    default:
+      return prev_byte >> mode;
+  }
+}
+
+#endif  // BROTLI_DEC_CONTEXT_H_
diff --git a/brotli/dec/decode.c b/brotli/dec/decode.c
new file mode 100644
index 0000000..85f906a
--- /dev/null
+++ b/brotli/dec/decode.c
@@ -0,0 +1,788 @@
+// 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.
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include "./bit_reader.h"
+#include "./context.h"
+#include "./decode.h"
+#include "./huffman.h"
+#include "./prefix.h"
+#include "./safe_malloc.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+#ifdef BROTLI_DECODE_DEBUG
+#define BROTLI_LOG_UINT(name)                                    \
+  printf("[%s] %s = %zd\n", __func__, #name, (size_t)name)
+#define BROTLI_LOG_ARRAY_INDEX(array_name, idx)                  \
+  printf("[%s] %s[%zd] = %zd\n", __func__, #array_name, \
+         (size_t)idx, (size_t)array_name[idx])
+#else
+#define BROTLI_LOG_UINT(name)
+#define BROTLI_LOG_ARRAY_INDEX(array_name, idx)
+#endif
+
+static const int kDefaultCodeLength = 8;
+static const int kCodeLengthLiterals = 16;
+static const int kCodeLengthRepeatCode = 16;
+static const int kCodeLengthExtraBits[3] = { 2, 3, 7 };
+static const int kCodeLengthRepeatOffsets[3] = { 3, 3, 11 };
+
+static const int kNumLiteralCodes = 256;
+static const int kNumInsertAndCopyCodes = 704;
+static const int kNumBlockLengthCodes = 26;
+
+#define CODE_LENGTH_CODES 19
+static const uint8_t kCodeLengthCodeOrder[CODE_LENGTH_CODES] = {
+  17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 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 int DecodeSize(BrotliBitReader* br, size_t* len) {
+  int size_bytes = BrotliReadBits(br, 3);
+  *len = 0;
+  int i = 0;
+  for (; i < size_bytes; ++i) {
+    *len |= BrotliReadBits(br, 8) << (i * 8);
+  }
+  return !br->error_;
+}
+
+static int DecodeMetaBlockLength(int input_size_bits,
+                                 size_t remaining_length,
+                                 BrotliBitReader* br,
+                                 size_t* meta_block_length) {
+  if (BrotliReadBits(br, 1)) {
+    *meta_block_length = remaining_length;
+    return 1;
+  }
+  *meta_block_length = 0;
+  int shift = 0;
+  while (input_size_bits > 0) {
+    *meta_block_length |= BrotliReadBits(br, 8) << shift;
+    input_size_bits -= 8;
+    shift += 8;
+  }
+  if (input_size_bits > 0) {
+    *meta_block_length |= BrotliReadBits(br, input_size_bits) << shift;
+  }
+  ++(*meta_block_length);
+  return !br->error_;
+}
+
+// Decodes the next Huffman code from bit-stream.
+// FillBitWindow(br) needs to be called at minimum every second call
+// to ReadSymbol, in order to pre-fetch enough bits.
+static BROTLI_INLINE int ReadSymbol(const HuffmanTree* tree,
+                                    BrotliBitReader* br) {
+  if (tree->fixed_bit_length_ > 0) {
+    return BrotliReadBits(br, tree->fixed_bit_length_);
+  }
+  const HuffmanTreeNode* node = tree->root_;
+  uint32_t bits = BrotliPrefetchBits(br);
+  int bitpos = br->bit_pos_;
+  // Check if we find the bit combination from the Huffman lookup table.
+  const int lut_ix = bits & (HUFF_LUT - 1);
+  const int lut_bits = tree->lut_bits_[lut_ix];
+  if (lut_bits <= HUFF_LUT_BITS) {
+    BrotliSetBitPos(br, bitpos + lut_bits);
+    return tree->lut_symbol_[lut_ix];
+  }
+  node += tree->lut_jump_[lut_ix];
+  bitpos += HUFF_LUT_BITS;
+  bits >>= HUFF_LUT_BITS;
+
+  // Decode the value from a binary tree.
+  assert(node != NULL);
+  do {
+    node = HuffmanTreeNextNode(node, bits & 1);
+    bits >>= 1;
+    ++bitpos;
+  } while (HuffmanTreeNodeIsNotLeaf(node));
+  BrotliSetBitPos(br, bitpos);
+  return node->symbol_;
+}
+
+static void PrintIntVector(const int* v, int len) {
+  while (len-- > 0) printf(" %d", *v++);
+  printf("\n");
+}
+
+static int ReadHuffmanCodeLengths(
+    const int* code_length_code_lengths,
+    int num_symbols, int* code_lengths,
+    BrotliBitReader* br) {
+  int ok = 0;
+  int symbol;
+  int max_symbol;
+  int prev_code_len = kDefaultCodeLength;
+  HuffmanTree tree;
+
+  if (!HuffmanTreeBuildImplicit(&tree, code_length_code_lengths,
+                                CODE_LENGTH_CODES)) {
+    printf("[ReadHuffmanCodeLengths] Building code length tree failed: ");
+    PrintIntVector(code_length_code_lengths, CODE_LENGTH_CODES);
+    return 0;
+  }
+
+  int use_length = BrotliReadBits(br, 1);
+  BROTLI_LOG_UINT(use_length);
+  if (use_length) {
+    const int length_nbits = 2 + 2 * BrotliReadBits(br, 3);
+    max_symbol = 2 + BrotliReadBits(br, length_nbits);
+    BROTLI_LOG_UINT(length_nbits);
+    if (max_symbol > num_symbols) {
+      printf("[ReadHuffmanCodeLengths] max_symbol > num_symbols (%d vs %d)\n",
+             max_symbol, num_symbols);
+      goto End;
+    }
+  } else {
+    max_symbol = num_symbols;
+  }
+  BROTLI_LOG_UINT(max_symbol);
+
+  symbol = 0;
+  while (symbol < num_symbols) {
+    int code_len;
+    if (max_symbol-- == 0) break;
+    BrotliFillBitWindow(br);
+    code_len = ReadSymbol(&tree, br);
+    BROTLI_LOG_UINT(symbol);
+    BROTLI_LOG_UINT(code_len);
+    if (code_len < kCodeLengthLiterals) {
+      code_lengths[symbol++] = code_len;
+      if (code_len != 0) prev_code_len = code_len;
+    } else {
+      const int use_prev = (code_len == kCodeLengthRepeatCode);
+      const int slot = code_len - kCodeLengthLiterals;
+      const int extra_bits = kCodeLengthExtraBits[slot];
+      const int repeat_offset = kCodeLengthRepeatOffsets[slot];
+      const int length = use_prev ? prev_code_len : 0;
+      int repeat = BrotliReadBits(br, extra_bits) + repeat_offset;
+      BROTLI_LOG_UINT(repeat);
+      BROTLI_LOG_UINT(length);
+      if (symbol + repeat > num_symbols) {
+        printf("[ReadHuffmanCodeLengths] symbol + repeat > num_symbols "
+               "(%d + %d vs %d)\n", symbol, repeat, num_symbols);
+        goto End;
+      } else {
+        while (repeat-- > 0) {
+          code_lengths[symbol++] = length;
+        }
+      }
+    }
+  }
+  while (symbol < num_symbols) code_lengths[symbol++] = 0;
+  ok = 1;
+
+ End:
+  HuffmanTreeRelease(&tree);
+  return ok;
+}
+
+static const int64_t kUnitInterval = 1LL<<30;
+
+static int RepairHuffmanCodeLengths(int num_symbols, int* code_lengths) {
+  int i;
+  int64_t space = kUnitInterval;
+  int max_length = 0;
+  for(i = 0; i < num_symbols; i++)
+    if (code_lengths[i] != 0) {
+      if (code_lengths[i] > max_length)
+        max_length = code_lengths[i];
+      space -= kUnitInterval >> code_lengths[i];
+    }
+  // The code which contains one symbol of length one cannot be made optimal.
+  if (max_length == 1)
+    return 1;
+  if (space < 0) {
+    int count_longest = 0;
+    for(i = 0; i < num_symbols; i++) {
+      if (code_lengths[i] == max_length)
+        count_longest++;
+    }
+    // Substitute all longest codes with sufficiently longer ones, so that all
+    // code words fit into the unit interval. Leftover space will be
+    // redistributed later.
+    space += count_longest * (kUnitInterval >> max_length);
+    if (space < 0)
+      return 0;
+    int new_length = max_length;
+    while (space < count_longest * (kUnitInterval >> new_length))
+      new_length++;
+    space -= count_longest * (kUnitInterval >> new_length);
+    for(i = 0; i < num_symbols; i++) {
+      if (code_lengths[i] == max_length)
+        code_lengths[i] = new_length;
+    }
+  }
+
+  while (space > 0) {
+    // Redistribute leftover space in an approximation of a uniform fashion.
+    for(i = 0; i < num_symbols; i++) {
+      if (code_lengths[i] > 1 && space >= (kUnitInterval >> code_lengths[i])) {
+        space -= kUnitInterval >> code_lengths[i];
+        code_lengths[i]--;
+      }
+      if (space == 0)
+        break;
+    }
+  }
+  return 1;
+}
+
+static int ReadHuffmanCode(int alphabet_size,
+                           HuffmanTree* tree,
+                           BrotliBitReader* br) {
+  int ok = 0;
+  const int simple_code = BrotliReadBits(br, 1);
+  BROTLI_LOG_UINT(simple_code);
+
+  if (simple_code) {  // Read symbols, codes & code lengths directly.
+    int symbols[2] = { 0 };
+    int codes[2];
+    int code_lengths[2];
+    const int num_symbols = BrotliReadBits(br, 1) + 1;
+    const int first_symbol_len_code = BrotliReadBits(br, 1);
+    // The first code is either 1 bit or 8 bit code.
+    symbols[0] = BrotliReadBits(br, (first_symbol_len_code == 0) ? 1 : 8);
+    codes[0] = 0;
+    code_lengths[0] = num_symbols - 1;
+    // The second code (if present), is always 8 bit long.
+    if (num_symbols == 2) {
+      symbols[1] = BrotliReadBits(br, 8);
+      codes[1] = 1;
+      code_lengths[1] = num_symbols - 1;
+    }
+    BROTLI_LOG_UINT(num_symbols);
+    BROTLI_LOG_UINT(first_symbol_len_code);
+    BROTLI_LOG_UINT(symbols[0]);
+    BROTLI_LOG_UINT(symbols[1]);
+    ok = HuffmanTreeBuildExplicit(tree, code_lengths, codes, symbols,
+                                  alphabet_size, num_symbols);
+    if (!ok) {
+      printf("[ReadHuffmanCode] HuffmanTreeBuildExplicit failed: ");
+      PrintIntVector(code_lengths, num_symbols);
+    }
+  } else {  // Decode Huffman-coded code lengths.
+    int* code_lengths = NULL;
+    int i;
+    int code_length_code_lengths[CODE_LENGTH_CODES] = { 0 };
+    const int num_codes = BrotliReadBits(br, 4) + 4;
+    BROTLI_LOG_UINT(num_codes);
+    if (num_codes > CODE_LENGTH_CODES) {
+      return 0;
+    }
+
+    code_lengths =
+        (int*)BrotliSafeMalloc((uint64_t)alphabet_size, sizeof(*code_lengths));
+    if (code_lengths == NULL) {
+      return 0;
+    }
+
+    for (i = 0; i < num_codes; ++i) {
+      int code_len_idx = kCodeLengthCodeOrder[i];
+      code_length_code_lengths[code_len_idx] = BrotliReadBits(br, 3);
+      BROTLI_LOG_ARRAY_INDEX(code_length_code_lengths, code_len_idx);
+    }
+    ok = ReadHuffmanCodeLengths(code_length_code_lengths, alphabet_size,
+                                code_lengths, br) &&
+         RepairHuffmanCodeLengths(alphabet_size, code_lengths);
+    if (ok) {
+      ok = HuffmanTreeBuildImplicit(tree, code_lengths, alphabet_size);
+      if (!ok) {
+        printf("[ReadHuffmanCode] HuffmanTreeBuildImplicit failed: ");
+        PrintIntVector(code_lengths, alphabet_size);
+      }
+    }
+    free(code_lengths);
+  }
+  ok = ok && !br->error_;
+  if (!ok) {
+    return 0;
+  }
+  return 1;
+}
+
+static int ReadCopyDistance(const HuffmanTree* tree,
+                            int num_direct_codes,
+                            int postfix_bits,
+                            uint32_t postfix_mask,
+                            BrotliBitReader* br) {
+  BrotliFillBitWindow(br);
+  int code = ReadSymbol(tree, br);
+  if (code < num_direct_codes) {
+    return code;
+  }
+  code -= num_direct_codes;
+  int postfix = code & postfix_mask;
+  code >>= postfix_bits;
+  int nbits = (code >> 1) + 1;
+  int offset = ((2 + (code & 1)) << nbits) - 4;
+  return (num_direct_codes +
+          ((offset + BrotliReadBits(br, nbits)) << postfix_bits) +
+          postfix);
+}
+
+static int ReadBlockLength(const HuffmanTree* tree, BrotliBitReader* br) {
+  BrotliFillBitWindow(br);
+  int code = ReadSymbol(tree, br);
+  int nbits = kBlockLengthPrefixCode[code].nbits;
+  return kBlockLengthPrefixCode[code].offset + BrotliReadBits(br, nbits);
+}
+
+static void ReadInsertAndCopy(const HuffmanTree* tree,
+                              int* insert_len,
+                              int* copy_len,
+                              int* copy_dist,
+                              BrotliBitReader* br) {
+  BrotliFillBitWindow(br);
+  int code = ReadSymbol(tree, br);
+  int range_idx = code >> 6;
+  if (range_idx >= 2) {
+    range_idx -= 2;
+    *copy_dist = -1;
+  } else {
+    *copy_dist = 0;
+  }
+  int insert_code = (kInsertRangeLut[range_idx] << 3) + ((code >> 3) & 7);
+  int copy_code = (kCopyRangeLut[range_idx] << 3) + (code & 7);
+  *insert_len =
+      kInsertLengthPrefixCode[insert_code].offset +
+      BrotliReadBits(br, kInsertLengthPrefixCode[insert_code].nbits);
+  *copy_len =
+      kCopyLengthPrefixCode[copy_code].offset +
+      BrotliReadBits(br, kCopyLengthPrefixCode[copy_code].nbits);
+}
+
+static int TranslateShortCodes(int code, int* ringbuffer, size_t* index) {
+  int val;
+  if (code < NUM_DISTANCE_SHORT_CODES) {
+    val = code;
+    int index_offset = kDistanceShortCodeIndexOffset[val];
+    int value_offset = kDistanceShortCodeValueOffset[val];
+    val = ringbuffer[(*index + index_offset) & 3] + value_offset;
+  } else {
+    val = code - NUM_DISTANCE_SHORT_CODES + 1;
+  }
+  if (code > 0) {
+    ringbuffer[*index & 3] = val;
+    ++(*index);
+  }
+  return val;
+}
+
+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;
+}
+
+static void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
+  uint8_t mtf[256];
+  int i;
+  for (i = 0; i < 256; ++i) {
+    mtf[i] = i;
+  }
+  for (i = 0; i < v_len; ++i) {
+    uint8_t index = v[i];
+    v[i] = mtf[index];
+    if (index) MoveToFront(mtf, index);
+  }
+}
+
+// Contains a collection of huffman trees with the same alphabet size.
+typedef struct {
+  int alphabet_size;
+  int num_htrees;
+  HuffmanTree* htrees;
+} HuffmanTreeGroup;
+
+void HuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size,
+                          int ntrees) {
+  group->alphabet_size = alphabet_size;
+  group->num_htrees = ntrees;
+  group->htrees = (HuffmanTree*)malloc(sizeof(HuffmanTree) * ntrees);
+}
+
+void HuffmanTreeGroupRelease(HuffmanTreeGroup* group) {
+  int i;
+  for (i = 0; i < group->num_htrees; ++i) {
+    HuffmanTreeRelease(&group->htrees[i]);
+  }
+  free(group->htrees);
+}
+
+int HuffmanTreeGroupDecode(HuffmanTreeGroup* group, BrotliBitReader* br) {
+  int i;
+  for (i = 0; i < group->num_htrees; ++i) {
+    ReadHuffmanCode(group->alphabet_size, &group->htrees[i], br);
+  }
+  return 1;
+}
+
+int DecodeContextMap(int num_block_types,
+                     int stream_type,
+                     int* context_mode,
+                     int* contexts_per_block,
+                     int* num_htrees,
+                     uint8_t** context_map,
+                     BrotliBitReader* br) {
+  int use_context = BrotliReadBits(br, 1);
+  if (!use_context) {
+    *context_mode = 0;
+    *contexts_per_block = 1;
+    *context_map = NULL;
+    *num_htrees = num_block_types;
+    return 1;
+  }
+  switch (stream_type) {
+    case 0:
+      *context_mode = BrotliReadBits(br, 4);
+      *contexts_per_block = NumContexts(*context_mode);
+      break;
+    case 2:
+      *context_mode = 1;
+      *contexts_per_block = 4;
+      break;
+  }
+  int context_map_size = *contexts_per_block * num_block_types;
+  *num_htrees = BrotliReadBits(br, 8) + 1;
+
+  BROTLI_LOG_UINT(*context_mode);
+  BROTLI_LOG_UINT(context_map_size);
+  BROTLI_LOG_UINT(*num_htrees);
+
+  *context_map = (uint8_t*)malloc(context_map_size);
+  if (*num_htrees <= 1) {
+    memset(*context_map, 0, context_map_size);
+    return 1;
+  }
+
+  int i;
+  if (*num_htrees == context_map_size) {
+    for (i = 0; i < context_map_size; ++i) {
+      (*context_map)[i] = i;
+    }
+    return 1;
+  }
+  int use_rle_for_zeros = BrotliReadBits(br, 1);
+  int max_run_length_prefix = 0;
+  if (use_rle_for_zeros) {
+    max_run_length_prefix = BrotliReadBits(br, 4) + 1;
+  }
+  HuffmanTree tree_index_htree;
+  ReadHuffmanCode(*num_htrees + max_run_length_prefix,
+                  &tree_index_htree, br);
+  if (use_rle_for_zeros) {
+    for (i = 0; i < context_map_size;) {
+      BrotliFillBitWindow(br);
+      int code = ReadSymbol(&tree_index_htree, br);
+      if (code == 0) {
+        (*context_map)[i] = 0;
+        ++i;
+      } else if (code <= max_run_length_prefix) {
+        int reps = 1 + (1 << code) + BrotliReadBits(br, code);
+        while (--reps) {
+          (*context_map)[i] = 0;
+          ++i;
+        }
+      } else {
+        (*context_map)[i] = code - max_run_length_prefix;
+        ++i;
+      }
+    }
+  } else {
+    for (i = 0; i < context_map_size; ++i) {
+      BrotliFillBitWindow(br);
+      (*context_map)[i] = ReadSymbol(&tree_index_htree, br);
+    }
+  }
+  HuffmanTreeRelease(&tree_index_htree);
+  if (BrotliReadBits(br, 1)) {
+    InverseMoveToFrontTransform(*context_map, context_map_size);
+  }
+  return 1;
+}
+
+static BROTLI_INLINE void DecodeBlockType(const HuffmanTree* trees,
+                                         int tree_type,
+                                         int* block_types,
+                                         int* ringbuffers,
+                                         size_t* indexes,
+                                         BrotliBitReader* br) {
+  int* ringbuffer = ringbuffers + tree_type * 2;
+  size_t* index = indexes + tree_type;
+  int type_code = ReadSymbol(trees + tree_type, 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;
+  }
+  block_types[tree_type] = block_type;
+  ringbuffer[(*index) & 1] = block_type;
+  ++(*index);
+}
+
+int BrotliDecompressedSize(size_t encoded_size,
+                           const uint8_t* encoded_buffer,
+                           size_t* decoded_size) {
+  BrotliBitReader br;
+  BrotliInitBitReader(&br, encoded_buffer, encoded_size);
+  return DecodeSize(&br, decoded_size);
+}
+
+int BrotliDecompressBuffer(size_t encoded_size,
+                           const uint8_t* encoded_buffer,
+                           size_t* decoded_size,
+                           uint8_t* decoded_buffer) {
+  BrotliBitReader br;
+  BrotliInitBitReader(&br, encoded_buffer, encoded_size);
+
+  int ok = DecodeSize(&br, decoded_size);
+  if (!ok) return 0;
+
+  if (*decoded_size == 0) {
+    return 1;
+  }
+  size_t n = *decoded_size;
+  int input_size_bits = (n == (n &~ (n - 1))) ? -1 : 0;
+  while (n) {
+    ++input_size_bits;
+    n >>= 1;
+  }
+
+  BROTLI_LOG_UINT(*decoded_size);
+  BROTLI_LOG_UINT(input_size_bits);
+
+  int i;
+  size_t pos = 0;
+  const size_t end = *decoded_size;
+  uint8_t* data = decoded_buffer;
+  // This ring buffer holds a few past copy distances that will be used by
+  // some special distance codes.
+  int dist_rb[4] = { 4, 11, 15, 16 };
+  size_t dist_rb_idx = 0;
+  HuffmanTreeGroup hgroup[3];
+
+  while (pos < end && ok) {
+    BROTLI_LOG_UINT(pos);
+    size_t meta_block_len = 0;
+    if (!DecodeMetaBlockLength(input_size_bits, end - pos,
+                               &br, &meta_block_len)) {
+      printf("Could not decode meta-block length.\n");
+      ok = 0;
+      goto End;
+    }
+    BROTLI_LOG_UINT(meta_block_len);
+    size_t meta_block_end = pos + meta_block_len;
+    size_t block_length[3] = { 0 };
+    int block_type[3] = { 0 };
+    int num_block_types[3] = { 0 };
+    int block_type_rb[6] = { 0, 1, 0, 1, 0, 1 };
+    size_t block_type_rb_index[3] = { 0 };
+    HuffmanTree block_type_trees[3];
+    HuffmanTree block_len_trees[3];
+    for (i = 0; i < 3; ++i) {
+      block_type_trees[i].root_ = NULL;
+      block_len_trees[i].root_ = NULL;
+      if (BrotliReadBits(&br, 1)) {
+        num_block_types[i] = BrotliReadBits(&br, 8) + 1;
+        ReadHuffmanCode(num_block_types[i] + 2, &block_type_trees[i], &br);
+        ReadHuffmanCode(kNumBlockLengthCodes, &block_len_trees[i], &br);
+        block_length[i] = ReadBlockLength(&block_len_trees[i], &br);
+        block_type_rb_index[i] = 1;
+      } else {
+        num_block_types[i] = 1;
+        block_length[i] = meta_block_len;
+      }
+    }
+
+    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]);
+
+    int distance_postfix_bits = BrotliReadBits(&br, 2);
+    int num_direct_distance_codes =
+        NUM_DISTANCE_SHORT_CODES +
+        (BrotliReadBits(&br, 4) << distance_postfix_bits);
+    uint32_t distance_postfix_mask = (1 << distance_postfix_bits) - 1;
+    int num_distance_codes = (num_direct_distance_codes +
+                              (48 << distance_postfix_bits));
+    BROTLI_LOG_UINT(num_direct_distance_codes);
+    BROTLI_LOG_UINT(distance_postfix_bits);
+
+    uint8_t* context_map;
+    int context_mode;
+    int contexts_per_block;
+    int num_literal_htrees;
+    DecodeContextMap(num_block_types[0], 0, &context_mode, &contexts_per_block,
+                     &num_literal_htrees, &context_map, &br);
+
+    uint8_t* dist_context_map;
+    int dist_context_mode;
+    int dist_contexts_per_block;
+    int num_dist_htrees;
+    DecodeContextMap(num_block_types[2], 2, &dist_context_mode,
+                     &dist_contexts_per_block,
+                     &num_dist_htrees, &dist_context_map, &br);
+
+    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) {
+      HuffmanTreeGroupDecode(&hgroup[i], &br);
+    }
+
+    HuffmanTree* literal_htrees = hgroup[0].htrees;
+    int context_offset = 0;
+    uint8_t* context_map_slice = context_map;
+    uint8_t literal_htree_index = 0;
+    int dist_context_offset = 0;
+    uint8_t* dist_context_map_slice = dist_context_map;
+    uint8_t dist_htree_index = 0;
+
+    while (pos < meta_block_end) {
+      if (block_length[1] == 0) {
+        DecodeBlockType(block_type_trees, 1, block_type, block_type_rb,
+                        block_type_rb_index, &br);
+        block_length[1] = ReadBlockLength(&block_len_trees[1], &br);
+      }
+      --block_length[1];
+      int insert_length;
+      int copy_length;
+      int distance_code;
+      ReadInsertAndCopy(&hgroup[1].htrees[block_type[1]],
+                        &insert_length, &copy_length, &distance_code, &br);
+      BROTLI_LOG_UINT(insert_length);
+      BROTLI_LOG_UINT(copy_length);
+      BROTLI_LOG_UINT(distance_code);
+      int j;
+      for (j = 0; j < insert_length; ++j) {
+        if (block_length[0] == 0) {
+          DecodeBlockType(block_type_trees, 0, block_type, block_type_rb,
+                          block_type_rb_index, &br);
+          block_length[0] = ReadBlockLength(&block_len_trees[0], &br);
+          literal_htree_index = block_type[0];
+          context_offset = block_type[0] * contexts_per_block;
+          context_map_slice = context_map + context_offset;
+        }
+        --block_length[0];
+        BrotliFillBitWindow(&br);
+        // Figure out htree
+        if (contexts_per_block > 1) {
+          uint8_t prev_byte = pos > 0 ? data[pos - 1] : 0;
+          uint8_t prev_byte2 = pos > 1 ? data[pos - 2] : 0;
+          uint8_t prev_byte3 = pos > 2 ? data[pos - 3] : 0;
+          uint8_t context = Context(prev_byte, prev_byte2, prev_byte3,
+                                    context_mode);
+          BROTLI_LOG_UINT(context);
+          literal_htree_index = context_map_slice[context];
+        }
+        data[pos] = ReadSymbol(&literal_htrees[literal_htree_index], &br);
+        BROTLI_LOG_UINT(literal_htree_index);
+        BROTLI_LOG_ARRAY_INDEX(data, pos);
+        ++pos;
+      }
+      if (br.error_) {
+        printf("Read error after decoding literal sequence.\n");
+        ok = 0;
+        goto End;
+      }
+
+      if (pos == meta_block_end) break;
+
+      if (distance_code < 0) {
+        if (block_length[2] == 0) {
+          DecodeBlockType(block_type_trees, 2, block_type, block_type_rb,
+                          block_type_rb_index, &br);
+          block_length[2] = ReadBlockLength(&block_len_trees[2], &br);
+          dist_htree_index = block_type[2];
+          dist_context_offset = block_type[2] * dist_contexts_per_block;
+          dist_context_map_slice = dist_context_map + dist_context_offset;
+        }
+        --block_length[2];
+        if (dist_contexts_per_block > 1) {
+          uint8_t context = copy_length > 4 ? 3 : copy_length - 2;
+          dist_htree_index = dist_context_map_slice[context];
+        }
+        distance_code = ReadCopyDistance(&hgroup[2].htrees[dist_htree_index],
+                                         num_direct_distance_codes,
+                                         distance_postfix_bits,
+                                         distance_postfix_mask,
+                                         &br);
+        if (br.error_) {
+          printf("Could not read copy distance.\n");
+          ok = 0;
+          goto End;
+        }
+      }
+
+      // Convert the distance code to the actual distance by possibly looking
+      // up past distnaces from the ringbuffer.
+      int dist = TranslateShortCodes(distance_code, dist_rb, &dist_rb_idx);
+      BROTLI_LOG_UINT(dist);
+
+      // Do the actual copy if it is valid.
+      if (pos >= dist && pos + copy_length <= end) {
+        int j;
+        for (j = 0; j < copy_length; ++j) {
+          data[pos + j] = data[pos + j - dist];
+        }
+        pos += copy_length;
+      } else {
+        printf("Invalid backward reference. pos: %zd dist: %d "
+               "len: %d end:%zd\n",
+                 pos, dist, copy_length, end);
+        ok = 0;
+        goto End;
+      }
+    }
+ End:
+    free(context_map);
+    free(dist_context_map);
+    for (i = 0; i < 3; ++i) {
+      HuffmanTreeGroupRelease(&hgroup[i]);
+      HuffmanTreeRelease(&block_type_trees[i]);
+      HuffmanTreeRelease(&block_len_trees[i]);
+    }
+  }
+
+  return ok;
+}
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif
diff --git a/brotli/dec/decode.h b/brotli/dec/decode.h
new file mode 100644
index 0000000..6d63e3a
--- /dev/null
+++ b/brotli/dec/decode.h
@@ -0,0 +1,46 @@
+// 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.
+//
+// API for Brotli decompression
+
+#ifndef BROTLI_DEC_DECODE_H_
+#define BROTLI_DEC_DECODE_H_
+
+#include "./types.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+// Sets *decoded_size to the decompressed size of the given encoded stream.
+// 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);
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif
+
+#endif  // BROTLI_DEC_DECODE_H_
diff --git a/brotli/dec/huffman.c b/brotli/dec/huffman.c
new file mode 100644
index 0000000..5f37df4
--- /dev/null
+++ b/brotli/dec/huffman.c
@@ -0,0 +1,299 @@
+// 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.
+//
+// Utilities for building and looking up Huffman trees.
+
+#include <assert.h>
+#include <stdlib.h>
+#include <string.h>
+#include "./huffman.h"
+#include "./safe_malloc.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+// Uncomment the following to use look-up table for ReverseBits()
+// (might be faster on some platform)
+// #define USE_LUT_REVERSE_BITS
+
+#define NON_EXISTENT_SYMBOL (-1)
+#define MAX_ALLOWED_CODE_LENGTH      15
+
+static void TreeNodeInit(HuffmanTreeNode* const node) {
+  node->children_ = -1;   // means: 'unassigned so far'
+}
+
+static int NodeIsEmpty(const HuffmanTreeNode* const node) {
+  return (node->children_ < 0);
+}
+
+static int IsFull(const HuffmanTree* const tree) {
+  return (tree->num_nodes_ == tree->max_nodes_);
+}
+
+static void AssignChildren(HuffmanTree* const tree,
+                           HuffmanTreeNode* const node) {
+  HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_;
+  node->children_ = (int)(children - node);
+  assert(children - node == (int)(children - node));
+  tree->num_nodes_ += 2;
+  TreeNodeInit(children + 0);
+  TreeNodeInit(children + 1);
+}
+
+static int TreeInit(HuffmanTree* const tree, int num_leaves) {
+  assert(tree != NULL);
+  tree->fixed_bit_length_ = 0;
+  if (num_leaves == 0) return 0;
+  // We allocate maximum possible nodes in the tree at once.
+  // Note that a Huffman tree is a full binary tree; and in a full binary tree
+  // with L leaves, the total number of nodes N = 2 * L - 1.
+  tree->max_nodes_ = 2 * num_leaves - 1;
+  assert(tree->max_nodes_ < (1 << 16));   // limit for the lut_jump_ table
+  tree->root_ = (HuffmanTreeNode*)BrotliSafeMalloc((uint64_t)tree->max_nodes_,
+                                                  sizeof(*tree->root_));
+  if (tree->root_ == NULL) return 0;
+  TreeNodeInit(tree->root_);  // Initialize root.
+  tree->num_nodes_ = 1;
+  memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_));
+  memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_));
+  return 1;
+}
+
+void HuffmanTreeRelease(HuffmanTree* const tree) {
+  if (tree != NULL) {
+    free(tree->root_);
+    tree->root_ = NULL;
+    tree->max_nodes_ = 0;
+    tree->num_nodes_ = 0;
+  }
+}
+
+int HuffmanCodeLengthsToCodes(const int* const code_lengths,
+                              int code_lengths_size, int* const huff_codes) {
+  int symbol;
+  int code_len;
+  int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
+  int curr_code;
+  int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
+  int max_code_length = 0;
+
+  assert(code_lengths != NULL);
+  assert(code_lengths_size > 0);
+  assert(huff_codes != NULL);
+
+  // Calculate max code length.
+  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
+    if (code_lengths[symbol] > max_code_length) {
+      max_code_length = code_lengths[symbol];
+    }
+  }
+  if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0;
+
+  // Calculate code length histogram.
+  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
+    ++code_length_hist[code_lengths[symbol]];
+  }
+  code_length_hist[0] = 0;
+
+  // Calculate the initial values of 'next_codes' for each code length.
+  // next_codes[code_len] denotes the code to be assigned to the next symbol
+  // of code length 'code_len'.
+  curr_code = 0;
+  next_codes[0] = -1;  // Unused, as code length = 0 implies code doesn't exist.
+  for (code_len = 1; code_len <= max_code_length; ++code_len) {
+    curr_code = (curr_code + code_length_hist[code_len - 1]) << 1;
+    next_codes[code_len] = curr_code;
+  }
+
+  // Get symbols.
+  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
+    if (code_lengths[symbol] > 0) {
+      huff_codes[symbol] = next_codes[code_lengths[symbol]]++;
+    } else {
+      huff_codes[symbol] = NON_EXISTENT_SYMBOL;
+    }
+  }
+  return 1;
+}
+
+#ifndef USE_LUT_REVERSE_BITS
+
+static int ReverseBitsShort(int bits, int num_bits) {
+  int retval = 0;
+  int i;
+  assert(num_bits <= 8);   // Not a hard requirement, just for coherency.
+  for (i = 0; i < num_bits; ++i) {
+    retval <<= 1;
+    retval |= bits & 1;
+    bits >>= 1;
+  }
+  return retval;
+}
+
+#else
+
+static const uint8_t kReversedBits[16] = {  // Pre-reversed 4-bit values.
+  0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
+  0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
+};
+
+static int ReverseBitsShort(int bits, int num_bits) {
+  const uint8_t v = (kReversedBits[bits & 0xf] << 4) | kReversedBits[bits >> 4];
+  assert(num_bits <= 8);
+  return v >> (8 - num_bits);
+}
+
+#endif
+
+static int TreeAddSymbol(HuffmanTree* const tree,
+                         int symbol, int code, int code_length) {
+  int step = HUFF_LUT_BITS;
+  int base_code;
+  HuffmanTreeNode* node = tree->root_;
+  const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_;
+  assert(symbol == (int16_t)symbol);
+  if (code_length <= HUFF_LUT_BITS) {
+    int i;
+    base_code = ReverseBitsShort(code, code_length);
+    for (i = 0; i < (1 << (HUFF_LUT_BITS - code_length)); ++i) {
+      const int idx = base_code | (i << code_length);
+      tree->lut_symbol_[idx] = (int16_t)symbol;
+      tree->lut_bits_[idx] = code_length;
+    }
+  } else {
+    base_code = ReverseBitsShort((code >> (code_length - HUFF_LUT_BITS)),
+                                 HUFF_LUT_BITS);
+  }
+  while (code_length-- > 0) {
+    if (node >= max_node) {
+      return 0;
+    }
+    if (NodeIsEmpty(node)) {
+      if (IsFull(tree)) return 0;    // error: too many symbols.
+      AssignChildren(tree, node);
+    } else if (!HuffmanTreeNodeIsNotLeaf(node)) {
+      return 0;  // leaf is already occupied.
+    }
+    node += node->children_ + ((code >> code_length) & 1);
+    if (--step == 0) {
+      tree->lut_jump_[base_code] = (int16_t)(node - tree->root_);
+    }
+  }
+  if (NodeIsEmpty(node)) {
+    node->children_ = 0;      // turn newly created node into a leaf.
+  } else if (HuffmanTreeNodeIsNotLeaf(node)) {
+    return 0;   // trying to assign a symbol to already used code.
+  }
+  node->symbol_ = symbol;  // Add symbol in this node.
+  return 1;
+}
+
+int HuffmanTreeBuildImplicit(HuffmanTree* const tree,
+                             const int* const code_lengths,
+                             int code_lengths_size) {
+  int symbol;
+  int num_symbols = 0;
+  int root_symbol = 0;
+
+  assert(tree != NULL);
+  assert(code_lengths != NULL);
+
+  // Find out number of symbols and the root symbol.
+  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
+    if (code_lengths[symbol] > 0) {
+      // Note: code length = 0 indicates non-existent symbol.
+      ++num_symbols;
+      root_symbol = symbol;
+    }
+  }
+
+  // Initialize the tree. Will fail for num_symbols = 0
+  if (!TreeInit(tree, num_symbols)) return 0;
+
+  // Build tree.
+  if (num_symbols == 1) {  // Trivial case.
+    const int max_symbol = code_lengths_size;
+    if (root_symbol < 0 || root_symbol >= max_symbol) {
+      HuffmanTreeRelease(tree);
+      return 0;
+    }
+    return TreeAddSymbol(tree, root_symbol, 0, 0);
+  } else {  // Normal case.
+    int ok = 0;
+
+    // Get Huffman codes from the code lengths.
+    int* const codes =
+        (int*)BrotliSafeMalloc((uint64_t)code_lengths_size, sizeof(*codes));
+    if (codes == NULL) goto End;
+
+    if (!HuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, codes)) {
+      goto End;
+    }
+
+    // Add symbols one-by-one.
+    for (symbol = 0; symbol < code_lengths_size; ++symbol) {
+      if (code_lengths[symbol] > 0) {
+        if (!TreeAddSymbol(tree, symbol, codes[symbol], code_lengths[symbol])) {
+          goto End;
+        }
+      }
+    }
+    ok = 1;
+ End:
+    free(codes);
+    ok = ok && IsFull(tree);
+    if (!ok) HuffmanTreeRelease(tree);
+    return ok;
+  }
+}
+
+int HuffmanTreeBuildExplicit(HuffmanTree* const tree,
+                             const int* const code_lengths,
+                             const int* const codes,
+                             const int* const symbols, int max_symbol,
+                             int num_symbols) {
+  int ok = 0;
+  int i;
+
+  assert(tree != NULL);
+  assert(code_lengths != NULL);
+  assert(codes != NULL);
+  assert(symbols != NULL);
+
+  // Initialize the tree. Will fail if num_symbols = 0.
+  if (!TreeInit(tree, num_symbols)) return 0;
+
+  // Add symbols one-by-one.
+  for (i = 0; i < num_symbols; ++i) {
+    if (codes[i] != NON_EXISTENT_SYMBOL) {
+      if (symbols[i] < 0 || symbols[i] >= max_symbol) {
+        goto End;
+      }
+      if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) {
+        goto End;
+      }
+    }
+  }
+  ok = 1;
+ End:
+  ok = ok && IsFull(tree);
+  if (!ok) HuffmanTreeRelease(tree);
+  return ok;
+}
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif
diff --git a/brotli/dec/huffman.h b/brotli/dec/huffman.h
new file mode 100644
index 0000000..2c21fdd
--- /dev/null
+++ b/brotli/dec/huffman.h
@@ -0,0 +1,91 @@
+// 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.
+//
+// Utilities for building and looking up Huffman trees.
+
+#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
+
+// A node of a Huffman tree.
+typedef struct {
+  int symbol_;
+  int children_;  // delta offset to both children (contiguous) or 0 if leaf.
+} HuffmanTreeNode;
+
+// Huffman Tree.
+#define HUFF_LUT_BITS 7
+#define HUFF_LUT (1U << HUFF_LUT_BITS)
+typedef struct HuffmanTree HuffmanTree;
+struct HuffmanTree {
+  // Fast lookup for short bit lengths.
+  uint8_t lut_bits_[HUFF_LUT];
+  int16_t lut_symbol_[HUFF_LUT];
+  int16_t lut_jump_[HUFF_LUT];
+  // Complete tree for lookups.
+  HuffmanTreeNode* root_;   // all the nodes, starting at root.
+  int max_nodes_;           // max number of nodes
+  int num_nodes_;           // number of currently occupied nodes
+  int fixed_bit_length_;     // If non-zero, uses fixed length coding
+};
+
+// Returns true if the given node is not a leaf of the Huffman tree.
+static BROTLI_INLINE int HuffmanTreeNodeIsNotLeaf(
+    const HuffmanTreeNode* const node) {
+  return node->children_;
+}
+
+// Go down one level. Most critical function. 'right_child' must be 0 or 1.
+static BROTLI_INLINE const HuffmanTreeNode* HuffmanTreeNextNode(
+    const HuffmanTreeNode* node, int right_child) {
+  return node + node->children_ + right_child;
+}
+
+// Releases the nodes of the Huffman tree.
+// Note: It does NOT free 'tree' itself.
+void HuffmanTreeRelease(HuffmanTree* const tree);
+
+// Builds Huffman tree assuming code lengths are implicitly in symbol order.
+// Returns false in case of error (invalid tree or memory error).
+int HuffmanTreeBuildImplicit(HuffmanTree* const tree,
+                             const int* const code_lengths,
+                             int code_lengths_size);
+
+// Build a Huffman tree with explicitly given lists of code lengths, codes
+// and symbols. Verifies that all symbols added are smaller than max_symbol.
+// Returns false in case of an invalid symbol, invalid tree or memory error.
+int HuffmanTreeBuildExplicit(HuffmanTree* const tree,
+                             const int* const code_lengths,
+                             const int* const codes,
+                             const int* const symbols, int max_symbol,
+                             int num_symbols);
+
+// Utility: converts Huffman code lengths to corresponding Huffman codes.
+// 'huff_codes' should be pre-allocated.
+// Returns false in case of error (memory allocation, invalid codes).
+int HuffmanCodeLengthsToCodes(const int* const code_lengths,
+                              int code_lengths_size, int* const huff_codes);
+
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}    // extern "C"
+#endif
+
+#endif  // BROTLI_DEC_HUFFMAN_H_
diff --git a/brotli/dec/prefix.h b/brotli/dec/prefix.h
new file mode 100644
index 0000000..dda01b1
--- /dev/null
+++ b/brotli/dec/prefix.h
@@ -0,0 +1,68 @@
+// 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.
+//
+// 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;
+};
+
+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},
+};
+
+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 kInsertAndCopyRangeLut[9] = {
+  0, 1, 4, 2, 3, 6, 5, 7, 8,
+};
+
+static const int kInsertRangeLut[9] = {
+  0, 0, 1, 1, 0, 2, 1, 2, 2,
+};
+
+static const int kCopyRangeLut[9] = {
+  0, 1, 0, 1, 2, 0, 2, 1, 2,
+};
+
+#endif  // BROTLI_DEC_PREFIX_H_
diff --git a/brotli/dec/safe_malloc.c b/brotli/dec/safe_malloc.c
new file mode 100644
index 0000000..41fa480
--- /dev/null
+++ b/brotli/dec/safe_malloc.c
@@ -0,0 +1,41 @@
+// 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
diff --git a/brotli/dec/safe_malloc.h b/brotli/dec/safe_malloc.h
new file mode 100644
index 0000000..5a334fc
--- /dev/null
+++ b/brotli/dec/safe_malloc.h
@@ -0,0 +1,43 @@
+// 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_UTILS_UTILS_H_
+#define BROTLI_UTILS_UTILS_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 (1ULL << 40)
+
+// 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_UTILS_UTILS_H_ */
diff --git a/brotli/dec/types.h b/brotli/dec/types.h
new file mode 100644
index 0000000..41696e4
--- /dev/null
+++ b/brotli/dec/types.h
@@ -0,0 +1,41 @@
+// 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.
+//
+// Common types
+
+#ifndef BROTLI_DEC_TYPES_H_
+#define BROTLI_DEC_TYPES_H_
+
+#include <stddef.h>  // for size_t
+
+#ifndef _MSC_VER
+#include <inttypes.h>
+#ifdef __STRICT_ANSI__
+#define BROTLI_INLINE
+#else  /* __STRICT_ANSI__ */
+#define BROTLI_INLINE inline
+#endif
+#else
+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 */
+
+#endif  // BROTLI_DEC_TYPES_H_