Add brotli compressor

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

24 files changed, 3904 insertions, 0 deletions

diff --git a/brotli/enc/README b/brotli/enc/README
new file mode 100644
index 0000000..c988ae7
--- /dev/null
+++ b/brotli/enc/README
@@ -0,0 +1,3 @@
+This directory holds the encoder for brotli compression format.
+
+Brotli is proposed to be used at the byte-compression level in WOFF 2.0 format.
diff --git a/brotli/enc/backward_references.cc b/brotli/enc/backward_references.cc
new file mode 100644
index 0000000..606fb99
--- /dev/null
+++ b/brotli/enc/backward_references.cc
@@ -0,0 +1,137 @@
+// 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.
+//
+// Function to find backward reference copies.
+
+#include "./backward_references.h"
+
+#include <algorithm>
+#include <vector>
+
+#include "./command.h"
+#include "./hash.h"
+#include "./literal_cost.h"
+
+namespace brotli {
+
+void CreateBackwardReferences(const uint8_t* data,
+                              int length,
+                              std::vector<Command>* commands) {
+  HashLongestMatch<13,11> *hasher = new HashLongestMatch<13,11>;
+  float *literal_cost = new float[length];
+  EstimateBitCostsForLiterals(length, data, literal_cost);
+  hasher->SetLiteralCost(literal_cost);
+
+  // Length heuristic that seems to help probably by better selection
+  // of lazy matches of similar lengths.
+  int insert_length = 0;
+  size_t i = 0;
+
+  double average_cost = 0.0;
+  for (int i = 0; i < length; ++i) {
+    average_cost += literal_cost[i];
+  }
+  average_cost /= length;
+  hasher->set_average_cost(average_cost);
+
+  while (i + 2 < length) {
+    size_t best_len = 0;
+    size_t best_dist = 0;
+    double best_score = 0;
+    const size_t max_distance = std::min(i, 1UL << 24);
+    hasher->set_insert_length(insert_length);
+    bool match_found = hasher->FindLongestMatch(
+        data, i, length - i, max_distance,
+        &best_len, &best_dist, &best_score);
+    if (match_found) {
+      // Found a match. Let's look for something even better ahead.
+      int delayed_backward_references_in_row = 0;
+      while (i + 4 < length &&
+             delayed_backward_references_in_row < 4) {
+        size_t best_len_2 = 0;
+        size_t best_dist_2 = 0;
+        double best_score_2 = 0;
+        hasher->Store(data + i, i);
+        match_found = hasher->FindLongestMatch(
+            data, i + 1, length - i - 1, max_distance,
+            &best_len_2, &best_dist_2, &best_score_2);
+        double cost_diff_lazy = 0;
+        if (best_len >= 4) {
+          cost_diff_lazy += hasher->literal_cost(i + 4) - average_cost;
+        }
+        {
+          const int tail_length = best_len_2 - best_len + 1;
+          for (int k = 0; k < tail_length; ++k) {
+            cost_diff_lazy -= hasher->literal_cost(i + best_len + k) -
+                average_cost;
+          }
+        }
+        // If we are not inserting any symbols, inserting one is more
+        // expensive than if we were inserting symbols anyways.
+        if (insert_length < 1) {
+          cost_diff_lazy += 1.0;
+        }
+        // Add bias to slightly avoid lazy matching.
+        cost_diff_lazy += 2.0 + delayed_backward_references_in_row * 0.2;
+        cost_diff_lazy += 0.04 * hasher->literal_cost(i);
+
+        if (match_found && best_score_2 >= best_score + cost_diff_lazy) {
+          // Ok, let's just write one byte for now and start a match from the
+          // next byte.
+          ++insert_length;
+          ++delayed_backward_references_in_row;
+          best_len = best_len_2;
+          best_dist = best_dist_2;
+          best_score = best_score_2;
+          i++;
+        } else {
+          break;
+        }
+      }
+      Command cmd;
+      cmd.insert_length_ = insert_length;
+      cmd.copy_length_ = best_len;
+      cmd.copy_distance_ = best_dist;
+      commands->push_back(cmd);
+      hasher->set_last_distance(best_dist);
+
+      insert_length = 0;
+      ++i;
+      for (int j = 1; j < best_len; ++j) {
+        if (i + 2 < length) {
+          hasher->Store(data + i, i);
+        }
+        ++i;
+      }
+    } else {
+      ++insert_length;
+      hasher->Store(data + i, i);
+      ++i;
+    }
+  }
+  insert_length += (length - i);
+
+  if (insert_length > 0) {
+    Command cmd;
+    cmd.insert_length_ = insert_length;
+    cmd.copy_length_ = 0;
+    cmd.copy_distance_ = 0;
+    commands->push_back(cmd);
+  }
+
+  delete[] literal_cost;
+  delete hasher;
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/backward_references.h b/brotli/enc/backward_references.h
new file mode 100644
index 0000000..795f613
--- /dev/null
+++ b/brotli/enc/backward_references.h
@@ -0,0 +1,33 @@
+// 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.
+//
+// Function to find backward reference copies.
+
+#ifndef BROTLI_ENC_BACKWARD_REFERENCES_H_
+#define BROTLI_ENC_BACKWARD_REFERENCES_H_
+
+#include <stdint.h>
+#include <vector>
+
+#include "./command.h"
+
+namespace brotli {
+
+void CreateBackwardReferences(const uint8_t* data,
+                              int length,
+                              std::vector<Command>* commands);
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_BACKWARD_REFERENCES_H_
diff --git a/brotli/enc/bit_cost.h b/brotli/enc/bit_cost.h
new file mode 100644
index 0000000..fc5381b
--- /dev/null
+++ b/brotli/enc/bit_cost.h
@@ -0,0 +1,150 @@
+// 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.
+//
+// Functions to estimate the bit cost of Huffman trees.
+
+#ifndef BROTLI_ENC_BIT_COST_H_
+#define BROTLI_ENC_BIT_COST_H_
+
+#include <stdint.h>
+
+#include "./entropy_encode.h"
+#include "./fast_log.h"
+
+namespace brotli {
+
+static const int kHuffmanExtraBits[kCodeLengthCodes] = {
+  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7,
+};
+
+static inline int HuffmanTreeBitCost(const int* counts, const uint8_t* depth) {
+  int nbits = 0;
+  for (int i = 0; i < kCodeLengthCodes; ++i) {
+    nbits += counts[i] * (depth[i] + kHuffmanExtraBits[i]);
+  }
+  return nbits;
+}
+
+static inline int HuffmanTreeBitCost(
+    const Histogram<kCodeLengthCodes>& histogram,
+    const EntropyCode<kCodeLengthCodes>& entropy) {
+  return HuffmanTreeBitCost(&histogram.data_[0], &entropy.depth_[0]);
+}
+
+static inline int HuffmanBitCost(const uint8_t* depth, int length) {
+  int max_depth = 1;
+  int histogram[kCodeLengthCodes] = { 0 };
+  int tail_start = 0;
+  // compute histogram of compacted huffman tree
+  for (int i = 0; i < length;) {
+    const int value = depth[i];
+    if (value > max_depth) {
+      max_depth = value;
+    }
+    int reps = 1;
+    for (int k = i + 1; k < length && depth[k] == value; ++k) {
+      ++reps;
+    }
+    i += reps;
+    if (value == 0) {
+      while (reps > 10) {
+        ++histogram[18];
+        reps -= 138;
+      }
+      if (reps > 2) {
+        ++histogram[17];
+      } else if (reps > 0) {
+        histogram[0] += reps;
+      }
+    } else {
+      tail_start = i;
+      ++histogram[value];
+      --reps;
+      while (reps > 2) {
+        ++histogram[16];
+        reps -= 6;
+      }
+      if (reps > 0) {
+        histogram[value] += reps;
+      }
+    }
+  }
+
+  // create huffman tree of huffman tree
+  uint8_t cost[kCodeLengthCodes] = { 0 };
+  CreateHuffmanTree(histogram, kCodeLengthCodes, 7, cost);
+  // account for rle extra bits
+  cost[16] += 2;
+  cost[17] += 3;
+  cost[18] += 7;
+
+  int tree_size = 0;
+  int bits = 6 + 3 * max_depth;  // huffman tree of huffman tree cost
+  for (int i = 0; i < kCodeLengthCodes; ++i) {
+    bits += histogram[i] * cost[i];  // huffman tree bit cost
+    tree_size += histogram[i];
+  }
+  // bit cost adjustment for long trailing zero sequence
+  int tail_size = length - tail_start;
+  int tail_bits = 0;
+  while (tail_size >= 1) {
+    if (tail_size < 3) {
+      tail_bits += tail_size * cost[0];
+      tree_size -= tail_size;
+      break;
+    } else if (tail_size < 11) {
+      tail_bits += cost[17];
+      --tree_size;
+      break;
+    } else {
+      tail_bits += cost[18];
+      tail_size -= 138;
+      --tree_size;
+    }
+  }
+  if (tail_bits > 12) {
+    bits += ((Log2Ceiling(tree_size - 1) + 1) & ~1) + 3 - tail_bits;
+  }
+  return bits;
+}
+
+template<int kSize>
+double PopulationCost(const Histogram<kSize>& histogram) {
+  if (histogram.total_count_ == 0) {
+    return 4;
+  }
+  int symbols[2] = { 0 };
+  int count = 0;
+  for (int i = 0; i < kSize && count < 3; ++i) {
+    if (histogram.data_[i] > 0) {
+      if (count < 2) symbols[count] = i;
+      ++count;
+    }
+  }
+  if (count <= 2 && symbols[0] < 256 && symbols[1] < 256) {
+    return ((symbols[0] <= 1 ? 4 : 11) +
+            (count == 2 ? 8 + histogram.total_count_ : 0));
+  }
+  uint8_t depth[kSize] = { 0 };
+  CreateHuffmanTree(&histogram.data_[0], kSize, 15, depth);
+  int bits = HuffmanBitCost(depth, kSize);
+  for (int i = 0; i < kSize; ++i) {
+    bits += histogram.data_[i] * depth[i];
+  }
+  return bits;
+}
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_BIT_COST_H_
diff --git a/brotli/enc/block_splitter.cc b/brotli/enc/block_splitter.cc
new file mode 100644
index 0000000..5552541
--- /dev/null
+++ b/brotli/enc/block_splitter.cc
@@ -0,0 +1,411 @@
+// 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.
+//
+// Block split point selection utilities.
+
+#include "./block_splitter.h"
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <algorithm>
+#include <map>
+
+#include "./cluster.h"
+#include "./command.h"
+#include "./fast_log.h"
+#include "./histogram.h"
+
+namespace brotli {
+
+static const int kMaxLiteralHistograms = 48;
+static const int kMaxCommandHistograms = 50;
+static const double kLiteralBlockSwitchCost = 26;
+static const double kCommandBlockSwitchCost = 13.5;
+static const double kDistanceBlockSwitchCost = 14.6;
+static const int kLiteralStrideLength = 70;
+static const int kCommandStrideLength = 40;
+static const int kSymbolsPerLiteralHistogram = 550;
+static const int kSymbolsPerCommandHistogram = 530;
+static const int kSymbolsPerDistanceHistogram = 550;
+static const int kMinLengthForBlockSplitting = 128;
+static const int kIterMulForRefining = 2;
+static const int kMinItersForRefining = 100;
+
+void CopyLiteralsToByteArray(const std::vector<Command>& cmds,
+                             const uint8_t* data,
+                             std::vector<uint8_t>* literals) {
+  // Count how many we have.
+  size_t total_length = 0;
+  for (int i = 0; i < cmds.size(); ++i) {
+    total_length += cmds[i].insert_length_;
+  }
+  if (total_length == 0) {
+    return;
+  }
+
+  // Allocate.
+  literals->resize(total_length);
+
+  // Loop again, and copy this time.
+  size_t pos = 0;
+  size_t from_pos = 0;
+  for (int i = 0; i < cmds.size() && pos < total_length; ++i) {
+    memcpy(&(*literals)[pos], data + from_pos, cmds[i].insert_length_);
+    pos += cmds[i].insert_length_;
+    from_pos += cmds[i].insert_length_ + cmds[i].copy_length_;
+  }
+}
+
+void CopyCommandsToByteArray(const std::vector<Command>& cmds,
+                             std::vector<uint16_t>* insert_and_copy_codes,
+                             std::vector<uint8_t>* distance_prefixes) {
+  for (int i = 0; i < cmds.size(); ++i) {
+    const Command& cmd = cmds[i];
+    insert_and_copy_codes->push_back(cmd.command_prefix_);
+    if (cmd.copy_length_ > 0 && cmd.distance_prefix_ != 0xffff) {
+      distance_prefixes->push_back(cmd.distance_prefix_);
+    }
+  }
+}
+
+template<int kSize>
+double HistogramAddEval(const Histogram<kSize>& a,
+                        const Histogram<kSize>& b) {
+  int total = a.total_count_ + b.total_count_;
+  double retval = total * FastLog2(total);
+  for (int i = 0; i < kSize; ++i) {
+    int count = a.data_[i] + b.data_[i];
+    retval -= count * FastLog2(count);
+  }
+  return retval;
+}
+
+template<typename HistogramType, typename DataType>
+void InitialEntropyCodes(const DataType* data, size_t length,
+                         int literals_per_histogram,
+                         int max_histograms,
+                         size_t stride,
+                         std::vector<HistogramType>* vec) {
+  int total_histograms = length / literals_per_histogram + 1;
+  if (total_histograms > max_histograms) {
+    total_histograms = max_histograms;
+  }
+  unsigned int seed = 7;
+  int block_length = length / total_histograms;
+  for (int i = 0; i < total_histograms; ++i) {
+    int pos = length * i / total_histograms;
+    if (i != 0) {
+      pos += rand_r(&seed) % block_length;
+    }
+    if (pos + stride >= length) {
+      pos = length - stride - 1;
+    }
+    HistogramType histo;
+    histo.Add(data + pos, stride);
+    vec->push_back(histo);
+  }
+}
+
+template<typename HistogramType>
+int FindClosest(const HistogramType& sample,
+                const std::vector<HistogramType>& vec) {
+  double best_distance = 1e99;
+  int best_ix = 0;
+  for (int i = 0; i < vec.size(); ++i) {
+    double distance = HistogramAddEval(sample, vec[i]);
+    if (distance < best_distance) {
+      best_ix = i;
+      best_distance = distance;
+    }
+  }
+  return best_ix;
+}
+
+template<typename HistogramType, typename DataType>
+void RandomSample(unsigned int* seed,
+                  const DataType* data,
+                  size_t length,
+                  size_t stride,
+                  HistogramType* sample) {
+  size_t pos = rand_r(seed) % (length - stride);
+  sample->Add(data + pos, stride);
+}
+
+template<typename HistogramType, typename DataType>
+void RefineEntropyCodes(const DataType* data, size_t length,
+                        size_t stride,
+                        std::vector<HistogramType>* vec) {
+  const int iters =
+      kIterMulForRefining * length / stride + kMinItersForRefining;
+  unsigned int seed = 7;
+  for (int iter = 0; iter < iters; ++iter) {
+    HistogramType sample;
+    RandomSample(&seed, data, length, stride, &sample);
+    int ix = FindClosest(sample, *vec);
+    (*vec)[ix].AddHistogram(sample);
+  }
+}
+
+inline static float BitCost(int total, int count) {
+  return count == 0 ? FastLog2(total) + 2 : FastLog2(total) - FastLog2(count);
+}
+
+template<typename DataType, int kSize>
+void FindBlocks(const DataType* data, const size_t length,
+                const double block_switch_bitcost,
+                const std::vector<Histogram<kSize> > &vec,
+                uint8_t *block_id) {
+  if (vec.size() <= 1) {
+    for (int i = 0; i < length; ++i) {
+      block_id[i] = 0;
+    }
+    return;
+  }
+  int vecsize = vec.size();
+  double* insert_cost = new double[kSize * vecsize];
+  memset(insert_cost, 0, sizeof(insert_cost[0]) * kSize * vecsize);
+  for (int i = 0; i < kSize; ++i) {
+    for (int j = 0; j < vecsize; ++j) {
+      insert_cost[i * vecsize + j] =
+          BitCost(vec[j].total_count_, vec[j].data_[i]);
+    }
+  }
+  double *cost = new double[vecsize];
+  memset(cost, 0, sizeof(cost[0]) * vecsize);
+  bool* switch_signal = new bool[length * vecsize];
+  memset(switch_signal, 0, sizeof(switch_signal[0]) * length * vecsize);
+  // After each iteration of this loop, cost[k] will contain the difference
+  // between the minimum cost of arriving at the current byte position using
+  // entropy code k, and the minimum cost of arriving at the current byte
+  // position. This difference is capped at the block switch cost, and if it
+  // reaches block switch cost, it means that when we trace back from the last
+  // position, we need to switch here.
+  for (size_t byte_ix = 0; byte_ix < length; ++byte_ix) {
+    int ix = byte_ix * vecsize;
+    int insert_cost_ix = data[byte_ix] * vecsize;
+    double min_cost = 1e99;
+    for (int k = 0; k < vecsize; ++k) {
+      // We are coding the symbol in data[byte_ix] with entropy code k.
+      cost[k] += insert_cost[insert_cost_ix + k];
+      if (cost[k] < min_cost) {
+        min_cost = cost[k];
+        block_id[byte_ix] = k;
+      }
+    }
+    double block_switch_cost = block_switch_bitcost;
+    // More blocks for the beginning.
+    if (byte_ix < 2000) {
+      block_switch_cost *= 0.77 + 0.07 * byte_ix / 2000;
+    }
+    for (int k = 0; k < vecsize; ++k) {
+      cost[k] -= min_cost;
+      if (cost[k] >= block_switch_cost) {
+        cost[k] = block_switch_cost;
+        switch_signal[ix + k] = true;
+      }
+    }
+  }
+  // Now trace back from the last position and switch at the marked places.
+  int byte_ix = length - 1;
+  int ix = byte_ix * vecsize;
+  int cur_id = block_id[byte_ix];
+  while (byte_ix > 0) {
+    --byte_ix;
+    ix -= vecsize;
+    if (switch_signal[ix + cur_id]) {
+      cur_id = block_id[byte_ix];
+    }
+    block_id[byte_ix] = cur_id;
+  }
+  delete[] insert_cost;
+  delete[] cost;
+  delete[] switch_signal;
+}
+
+int RemapBlockIds(uint8_t* block_ids, const size_t length) {
+  std::map<uint8_t, uint8_t> new_id;
+  int next_id = 0;
+  for (int i = 0; i < length; ++i) {
+    if (new_id.find(block_ids[i]) == new_id.end()) {
+      new_id[block_ids[i]] = next_id;
+      ++next_id;
+    }
+  }
+  for (int i = 0; i < length; ++i) {
+    block_ids[i] = new_id[block_ids[i]];
+  }
+  return next_id;
+}
+
+template<typename HistogramType, typename DataType>
+void BuildBlockHistograms(const DataType* data, const size_t length,
+                          uint8_t* block_ids,
+                          std::vector<HistogramType>* histograms) {
+  int num_types = RemapBlockIds(block_ids, length);
+  histograms->clear();
+  histograms->resize(num_types);
+  for (int i = 0; i < length; ++i) {
+    (*histograms)[block_ids[i]].Add(data[i]);
+  }
+}
+
+template<typename HistogramType, typename DataType>
+void ClusterBlocks(const DataType* data, const size_t length,
+                   uint8_t* block_ids) {
+  std::vector<HistogramType> histograms;
+  std::vector<int> block_index(length);
+  int cur_idx = 0;
+  HistogramType cur_histogram;
+  for (int i = 0; i < length; ++i) {
+    bool block_boundary = (i + 1 == length || block_ids[i] != block_ids[i + 1]);
+    block_index[i] = cur_idx;
+    cur_histogram.Add(data[i]);
+    if (block_boundary) {
+      histograms.push_back(cur_histogram);
+      cur_histogram.Clear();
+      ++cur_idx;
+    }
+  }
+  std::vector<HistogramType> clustered_histograms;
+  std::vector<int> histogram_symbols;
+  // Block ids need to fit in one byte and there are two ids reserved for
+  // indicating 'same as last' and 'last plus one'.
+  static const int kMaxNumberOfBlockTypes = 254;
+  ClusterHistograms(histograms, 1, histograms.size(),
+                    kMaxNumberOfBlockTypes,
+                    &clustered_histograms,
+                    &histogram_symbols);
+  for (int i = 0; i < length; ++i) {
+    block_ids[i] = histogram_symbols[block_index[i]];
+  }
+}
+
+void BuildBlockSplit(const std::vector<uint8_t>& block_ids, BlockSplit* split) {
+  int cur_id = block_ids[0];
+  int cur_length = 1;
+  split->num_types_ = -1;
+  for (int i = 1; i < block_ids.size(); ++i) {
+    if (block_ids[i] != cur_id) {
+      split->types_.push_back(cur_id);
+      split->lengths_.push_back(cur_length);
+      split->num_types_ = std::max(split->num_types_, cur_id);
+      cur_id = block_ids[i];
+      cur_length = 0;
+    }
+    ++cur_length;
+  }
+  split->types_.push_back(cur_id);
+  split->lengths_.push_back(cur_length);
+  split->num_types_ = std::max(split->num_types_, cur_id);
+  ++split->num_types_;
+}
+
+template<typename HistogramType, typename DataType>
+void SplitByteVector(const std::vector<DataType>& data,
+                     const int literals_per_histogram,
+                     const int max_histograms,
+                     const int sampling_stride_length,
+                     const double block_switch_cost,
+                     BlockSplit* split) {
+  if (data.empty()) {
+    split->num_types_ = 0;
+    return;
+  } else if (data.size() < kMinLengthForBlockSplitting) {
+    split->num_types_ = 1;
+    split->types_.push_back(0);
+    split->lengths_.push_back(data.size());
+    return;
+  }
+  std::vector<HistogramType> histograms;
+  // Find good entropy codes.
+  InitialEntropyCodes(data.data(), data.size(),
+                      literals_per_histogram,
+                      max_histograms,
+                      sampling_stride_length,
+                      &histograms);
+  RefineEntropyCodes(data.data(), data.size(),
+                     sampling_stride_length,
+                     &histograms);
+  // Find a good path through literals with the good entropy codes.
+  std::vector<uint8_t> block_ids(data.size());
+  for (int i = 0; i < 10; ++i) {
+    FindBlocks(data.data(), data.size(),
+               block_switch_cost,
+               histograms,
+               &block_ids[0]);
+    BuildBlockHistograms(data.data(), data.size(), &block_ids[0], &histograms);
+  }
+  ClusterBlocks<HistogramType>(data.data(), data.size(), &block_ids[0]);
+  BuildBlockSplit(block_ids, split);
+}
+
+void SplitBlock(const std::vector<Command>& cmds,
+                const uint8_t* data,
+                BlockSplit* literal_split,
+                BlockSplit* insert_and_copy_split,
+                BlockSplit* dist_split) {
+  // Create a continuous array of literals.
+  std::vector<uint8_t> literals;
+  CopyLiteralsToByteArray(cmds, data, &literals);
+
+  // Compute prefix codes for commands.
+  std::vector<uint16_t> insert_and_copy_codes;
+  std::vector<uint8_t> distance_prefixes;
+  CopyCommandsToByteArray(cmds,
+                          &insert_and_copy_codes,
+                          &distance_prefixes);
+
+  SplitByteVector<HistogramLiteral>(
+      literals,
+      kSymbolsPerLiteralHistogram, kMaxLiteralHistograms,
+      kLiteralStrideLength, kLiteralBlockSwitchCost,
+      literal_split);
+  SplitByteVector<HistogramCommand>(
+      insert_and_copy_codes,
+      kSymbolsPerCommandHistogram, kMaxCommandHistograms,
+      kCommandStrideLength, kCommandBlockSwitchCost,
+      insert_and_copy_split);
+  SplitByteVector<HistogramDistance>(
+      distance_prefixes,
+      kSymbolsPerDistanceHistogram, kMaxCommandHistograms,
+      kCommandStrideLength, kDistanceBlockSwitchCost,
+      dist_split);
+}
+
+void SplitBlockByTotalLength(const std::vector<Command>& all_commands,
+                             int input_size,
+                             int target_length,
+                             std::vector<std::vector<Command> >* blocks) {
+  int num_blocks = input_size / target_length + 1;
+  int length_limit = input_size / num_blocks + 1;
+  int total_length = 0;
+  std::vector<Command> cur_block;
+  for (int i = 0; i < all_commands.size(); ++i) {
+    const Command& cmd = all_commands[i];
+    int cmd_length = cmd.insert_length_ + cmd.copy_length_;
+    if (total_length > length_limit) {
+      blocks->push_back(cur_block);
+      cur_block.clear();
+      total_length = 0;
+    }
+    cur_block.push_back(cmd);
+    total_length += cmd_length;
+  }
+  blocks->push_back(cur_block);
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/block_splitter.h b/brotli/enc/block_splitter.h
new file mode 100644
index 0000000..272904c
--- /dev/null
+++ b/brotli/enc/block_splitter.h
@@ -0,0 +1,77 @@
+// 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.
+//
+// Block split point selection utilities.
+
+#ifndef BROTLI_ENC_BLOCK_SPLITTER_H_
+#define BROTLI_ENC_BLOCK_SPLITTER_H_
+
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include <vector>
+#include <utility>
+
+#include "./command.h"
+
+namespace brotli {
+
+struct BlockSplit {
+  int num_types_;
+  std::vector<uint8_t> types_;
+  std::vector<uint8_t> type_codes_;
+  std::vector<int> lengths_;
+};
+
+struct BlockSplitIterator {
+  explicit BlockSplitIterator(const BlockSplit& split)
+      : split_(split), idx_(0), type_(0), length_(0) {
+    if (!split.lengths_.empty()) {
+      length_ = split.lengths_[0];
+    }
+  }
+
+  void Next() {
+    if (length_ == 0) {
+      ++idx_;
+      type_ = split_.types_[idx_];
+      length_ = split_.lengths_[idx_];
+    }
+    --length_;
+  }
+
+  const BlockSplit& split_;
+  int idx_;
+  int type_;
+  int length_;
+};
+
+void CopyLiteralsToByteArray(const std::vector<Command>& cmds,
+                             const uint8_t* data,
+                             std::vector<uint8_t>* literals);
+
+void SplitBlock(const std::vector<Command>& cmds,
+                const uint8_t* data,
+                BlockSplit* literal_split,
+                BlockSplit* insert_and_copy_split,
+                BlockSplit* dist_split);
+
+void SplitBlockByTotalLength(const std::vector<Command>& all_commands,
+                             int input_size,
+                             int target_length,
+                             std::vector<std::vector<Command> >* blocks);
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_BLOCK_SPLITTER_H_
diff --git a/brotli/enc/cluster.h b/brotli/enc/cluster.h
new file mode 100644
index 0000000..855a88d
--- /dev/null
+++ b/brotli/enc/cluster.h
@@ -0,0 +1,288 @@
+// 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.
+//
+// Functions for clustering similar histograms together.
+
+#ifndef BROTLI_ENC_CLUSTER_H_
+#define BROTLI_ENC_CLUSTER_H_
+
+#include <math.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <complex>
+#include <map>
+#include <set>
+#include <utility>
+#include <vector>
+
+#include "./bit_cost.h"
+#include "./entropy_encode.h"
+#include "./fast_log.h"
+#include "./histogram.h"
+
+namespace brotli {
+
+struct HistogramPair {
+  int idx1;
+  int idx2;
+  bool valid;
+  double cost_combo;
+  double cost_diff;
+};
+
+struct HistogramPairComparator {
+  bool operator()(const HistogramPair& p1, const HistogramPair& p2) {
+    if (p1.cost_diff != p2.cost_diff) {
+      return p1.cost_diff > p2.cost_diff;
+    }
+    return abs(p1.idx1 - p1.idx2) > abs(p2.idx1 - p2.idx2);
+  }
+};
+
+// Returns entropy reduction of the context map when we combine two clusters.
+inline double ClusterCostDiff(int size_a, int size_b) {
+  int size_c = size_a + size_b;
+  return size_a * FastLog2(size_a) + size_b * FastLog2(size_b) -
+      size_c * FastLog2(size_c);
+}
+
+// Computes the bit cost reduction by combining out[idx1] and out[idx2] and if
+// it is below a threshold, stores the pair (idx1, idx2) in the *pairs heap.
+template<int kSize>
+void CompareAndPushToHeap(const Histogram<kSize>* out,
+                          const int* cluster_size,
+                          int idx1, int idx2,
+                          std::vector<HistogramPair>* pairs) {
+  if (idx1 == idx2) {
+    return;
+  }
+  if (idx2 < idx1) {
+    int t = idx2;
+    idx2 = idx1;
+    idx1 = t;
+  }
+  bool store_pair = false;
+  HistogramPair p;
+  p.idx1 = idx1;
+  p.idx2 = idx2;
+  p.valid = true;
+  p.cost_diff = 0.5 * ClusterCostDiff(cluster_size[idx1], cluster_size[idx2]);
+  p.cost_diff -= out[idx1].bit_cost_;
+  p.cost_diff -= out[idx2].bit_cost_;
+
+  if (out[idx1].total_count_ == 0) {
+    p.cost_combo = out[idx2].bit_cost_;
+    store_pair = true;
+  } else if (out[idx2].total_count_ == 0) {
+    p.cost_combo = out[idx1].bit_cost_;
+    store_pair = true;
+  } else {
+    double threshold = pairs->empty() ? 1e99 :
+        std::max(0.0, (*pairs)[0].cost_diff);
+    Histogram<kSize> combo = out[idx1];
+    combo.AddHistogram(out[idx2]);
+    double cost_combo = PopulationCost(combo);
+    if (cost_combo < threshold - p.cost_diff) {
+      p.cost_combo = cost_combo;
+      store_pair = true;
+    }
+  }
+  if (store_pair) {
+    p.cost_diff += p.cost_combo;
+    pairs->push_back(p);
+    push_heap(pairs->begin(), pairs->end(), HistogramPairComparator());
+  }
+}
+
+template<int kSize>
+void HistogramCombine(Histogram<kSize>* out,
+                      int* cluster_size,
+                      int* symbols,
+                      int symbols_size,
+                      int max_clusters) {
+  double cost_diff_threshold = 0.0;
+  int min_cluster_size = 1;
+  std::set<int> all_symbols;
+  std::vector<int> clusters;
+  for (int i = 0; i < symbols_size; ++i) {
+    if (all_symbols.find(symbols[i]) == all_symbols.end()) {
+      all_symbols.insert(symbols[i]);
+      clusters.push_back(symbols[i]);
+    }
+  }
+
+  // We maintain a heap of histogram pairs, ordered by the bit cost reduction.
+  std::vector<HistogramPair> pairs;
+  for (int idx1 = 0; idx1 < clusters.size(); ++idx1) {
+    for (int idx2 = idx1 + 1; idx2 < clusters.size(); ++idx2) {
+      CompareAndPushToHeap(out, cluster_size, clusters[idx1], clusters[idx2],
+                           &pairs);
+    }
+  }
+
+  while (clusters.size() > min_cluster_size) {
+    if (pairs[0].cost_diff >= cost_diff_threshold) {
+      cost_diff_threshold = 1e99;
+      min_cluster_size = max_clusters;
+      continue;
+    }
+    // Take the best pair from the top of heap.
+    int best_idx1 = pairs[0].idx1;
+    int best_idx2 = pairs[0].idx2;
+    out[best_idx1].AddHistogram(out[best_idx2]);
+    out[best_idx1].bit_cost_ = pairs[0].cost_combo;
+    cluster_size[best_idx1] += cluster_size[best_idx2];
+    for (int i = 0; i < symbols_size; ++i) {
+      if (symbols[i] == best_idx2) {
+        symbols[i] = best_idx1;
+      }
+    }
+    for (int i = 0; i + 1 < clusters.size(); ++i) {
+      if (clusters[i] >= best_idx2) {
+        clusters[i] = clusters[i + 1];
+      }
+    }
+    clusters.pop_back();
+    // Invalidate pairs intersecting the just combined best pair.
+    for (int i = 0; i < pairs.size(); ++i) {
+      HistogramPair& p = pairs[i];
+      if (p.idx1 == best_idx1 || p.idx2 == best_idx1 ||
+          p.idx1 == best_idx2 || p.idx2 == best_idx2) {
+        p.valid = false;
+      }
+    }
+    // Pop invalid pairs from the top of the heap.
+    while (!pairs.empty() && !pairs[0].valid) {
+      pop_heap(pairs.begin(), pairs.end(), HistogramPairComparator());
+      pairs.pop_back();
+    }
+    // Push new pairs formed with the combined histogram to the heap.
+    for (int i = 0; i < clusters.size(); ++i) {
+      CompareAndPushToHeap(out, cluster_size, best_idx1, clusters[i], &pairs);
+    }
+  }
+}
+
+// -----------------------------------------------------------------------------
+// Histogram refinement
+
+// What is the bit cost of moving histogram from cur_symbol to candidate.
+template<int kSize>
+double HistogramBitCostDistance(const Histogram<kSize>& histogram,
+                                const Histogram<kSize>& candidate) {
+  if (histogram.total_count_ == 0) {
+    return 0.0;
+  }
+  Histogram<kSize> tmp = histogram;
+  tmp.AddHistogram(candidate);
+  return PopulationCost(tmp) - candidate.bit_cost_;
+}
+
+// Find the best 'out' histogram for each of the 'in' histograms.
+// Note: we assume that out[]->bit_cost_ is already up-to-date.
+template<int kSize>
+void HistogramRemap(const Histogram<kSize>* in, int in_size,
+                    Histogram<kSize>* out, int* symbols) {
+  std::set<int> all_symbols;
+  for (int i = 0; i < in_size; ++i) {
+    all_symbols.insert(symbols[i]);
+  }
+  for (int i = 0; i < in_size; ++i) {
+    int best_out = i == 0 ? symbols[0] : symbols[i - 1];
+    double best_bits = HistogramBitCostDistance(in[i], out[best_out]);
+    for (std::set<int>::const_iterator k = all_symbols.begin();
+         k != all_symbols.end(); ++k) {
+      const double cur_bits = HistogramBitCostDistance(in[i], out[*k]);
+      if (cur_bits < best_bits) {
+        best_bits = cur_bits;
+        best_out = *k;
+      }
+    }
+    symbols[i] = best_out;
+  }
+
+  // Recompute each out based on raw and symbols.
+  for (std::set<int>::const_iterator k = all_symbols.begin();
+       k != all_symbols.end(); ++k) {
+    out[*k].Clear();
+  }
+  for (int i = 0; i < in_size; ++i) {
+    out[symbols[i]].AddHistogram(in[i]);
+  }
+}
+
+// Reorder histograms in *out so that the new symbols in *symbols come in
+// increasing order.
+template<int kSize>
+void HistogramReindex(std::vector<Histogram<kSize> >* out,
+                      std::vector<int>* symbols) {
+  std::vector<Histogram<kSize> > tmp(*out);
+  std::map<int, int> new_index;
+  int next_index = 0;
+  for (int i = 0; i < symbols->size(); ++i) {
+    if (new_index.find((*symbols)[i]) == new_index.end()) {
+      new_index[(*symbols)[i]] = next_index;
+      (*out)[next_index] = tmp[(*symbols)[i]];
+      ++next_index;
+    }
+  }
+  out->resize(next_index);
+  for (int i = 0; i < symbols->size(); ++i) {
+    (*symbols)[i] = new_index[(*symbols)[i]];
+  }
+}
+
+// Clusters similar histograms in 'in' together, the selected histograms are
+// placed in 'out', and for each index in 'in', *histogram_symbols will
+// indicate which of the 'out' histograms is the best approximation.
+template<int kSize>
+void ClusterHistograms(const std::vector<Histogram<kSize> >& in,
+                       int num_contexts, int num_blocks,
+                       int max_histograms,
+                       std::vector<Histogram<kSize> >* out,
+                       std::vector<int>* histogram_symbols) {
+  const int in_size = num_contexts * num_blocks;
+  std::vector<int> cluster_size(in_size, 1);
+  out->resize(in_size);
+  histogram_symbols->resize(in_size);
+  for (int i = 0; i < in_size; ++i) {
+    (*out)[i] = in[i];
+    (*out)[i].bit_cost_ = PopulationCost(in[i]);
+    (*histogram_symbols)[i] = i;
+  }
+
+  // Collapse similar histograms within a block type.
+  if (num_contexts > 1) {
+    for (int i = 0; i < num_blocks; ++i) {
+      HistogramCombine(&(*out)[0], &cluster_size[0],
+                       &(*histogram_symbols)[i * num_contexts], num_contexts,
+                       max_histograms);
+    }
+  }
+
+  // Collapse similar histograms.
+  HistogramCombine(&(*out)[0], &cluster_size[0],
+                   &(*histogram_symbols)[0], in_size,
+                   max_histograms);
+
+  // Find the optimal map from original histograms to the final ones.
+  HistogramRemap(&in[0], in_size, &(*out)[0], &(*histogram_symbols)[0]);
+
+  // Convert the context map to a canonical form.
+  HistogramReindex(out, histogram_symbols);
+}
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_CLUSTER_H_
diff --git a/brotli/enc/command.h b/brotli/enc/command.h
new file mode 100644
index 0000000..8a539d0
--- /dev/null
+++ b/brotli/enc/command.h
@@ -0,0 +1,45 @@
+// 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.
+//
+// This class models a sequence of literals and a backward reference copy.
+
+#ifndef BROTLI_ENC_COMMAND_H_
+#define BROTLI_ENC_COMMAND_H_
+
+#include <stdint.h>
+
+namespace brotli {
+
+// Command holds a sequence of literals and a backward reference copy.
+class Command {
+ public:
+  Command() : insert_length_(0), copy_length_(0),
+              copy_distance_(0), distance_code_(0),
+              distance_prefix_(0), command_prefix_(0),
+              distance_extra_bits_(0), distance_extra_bits_value_(0) {}
+
+  uint32_t insert_length_;
+  uint32_t copy_length_;
+  uint32_t copy_distance_;
+  // Values <= 16 are short codes, values > 16 are distances shifted by 16.
+  uint32_t distance_code_;
+  uint16_t distance_prefix_;
+  uint16_t command_prefix_;
+  int distance_extra_bits_;
+  uint32_t distance_extra_bits_value_;
+};
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_COMMAND_H_
diff --git a/brotli/enc/context.h b/brotli/enc/context.h
new file mode 100644
index 0000000..9bf9227
--- /dev/null
+++ b/brotli/enc/context.h
@@ -0,0 +1,130 @@
+// 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.
+//
+// Functions to map previous bytes into a context id.
+
+#ifndef BROTLI_ENC_CONTEXT_H_
+#define BROTLI_ENC_CONTEXT_H_
+
+#include <stdint.h>
+
+namespace brotli {
+
+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_NONE        = 0,
+  CONTEXT_FULL        = 1,
+  CONTEXT_MSB7        = 2,
+  CONTEXT_MSB6        = 3,
+  CONTEXT_MSB5        = 4,
+  CONTEXT_MSB4        = 5,
+  CONTEXT_MSB3        = 6,
+  CONTEXT_MSB2        = 7,
+  CONTEXT_MSB1        = 8,
+  CONTEXT_IS_ZERO     = 9,
+  CONTEXT_SIGNED_2BIT = 10,
+  CONTEXT_SIGNED_3BIT = 11,
+  CONTEXT_SIGNED_4BIT = 12,
+  CONTEXT_SIGNED_MIXED_3BYTE = 13,
+};
+
+static const int kContextSize[] = {
+  1, 256, 128, 64, 32, 16, 8, 4, 2, 2, 4, 8, 16, 64,
+};
+
+static inline int NumContexts(int mode) {
+  return kContextSize[mode];
+}
+
+static inline uint8_t Context(uint8_t prev_byte, uint8_t prev_byte2,
+                              uint8_t prev_byte3, int mode) {
+  switch (mode) {
+    case CONTEXT_NONE:
+      return 0;
+    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 - 1);
+  }
+}
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_CONTEXT_H_
diff --git a/brotli/enc/encode.cc b/brotli/enc/encode.cc
new file mode 100644
index 0000000..cefc7dc
--- /dev/null
+++ b/brotli/enc/encode.cc
@@ -0,0 +1,778 @@
+// 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.
+//
+// Implementation of Brotli compressor.
+
+#include "./encode.h"
+
+#include <algorithm>
+#include <limits>
+
+#include "./backward_references.h"
+#include "./bit_cost.h"
+#include "./block_splitter.h"
+#include "./cluster.h"
+#include "./context.h"
+#include "./entropy_encode.h"
+#include "./fast_log.h"
+#include "./histogram.h"
+#include "./prefix.h"
+#include "./write_bits.h"
+
+namespace brotli {
+
+template<int kSize>
+double Entropy(const std::vector<Histogram<kSize> >& histograms) {
+  double retval = 0;
+  for (int i = 0; i < histograms.size(); ++i) {
+    retval += histograms[i].EntropyBitCost();
+  }
+  return retval;
+}
+
+void EncodeSize(size_t len, int* storage_ix, uint8_t* storage) {
+  std::vector<uint8_t> len_bytes;
+  while (len > 0) {
+    len_bytes.push_back(len & 0xff);
+    len >>= 8;
+  };
+  WriteBits(3, len_bytes.size(), storage_ix, storage);
+  for (int i = 0; i < len_bytes.size(); ++i) {
+    WriteBits(8, len_bytes[i], storage_ix, storage);
+  }
+}
+
+void EncodeMetaBlockLength(int input_size_bits,
+                           size_t meta_block_size,
+                           bool is_last_meta_block,
+                           int* storage_ix, uint8_t* storage) {
+  WriteBits(1, is_last_meta_block, storage_ix, storage);
+  if (is_last_meta_block) return;
+  while (input_size_bits > 0) {
+    WriteBits(8, meta_block_size & 0xff, storage_ix, storage);
+    meta_block_size >>= 8;
+    input_size_bits -= 8;
+  }
+  if (input_size_bits > 0) {
+    WriteBits(input_size_bits, meta_block_size, storage_ix, storage);
+  }
+}
+
+template<int kSize>
+void EntropyEncode(int val, const EntropyCode<kSize>& code,
+                   int* storage_ix, uint8_t* storage) {
+  if (code.count_ <= 1) {
+    return;
+  };
+  WriteBits(code.depth_[val], code.bits_[val], storage_ix, storage);
+}
+
+void StoreHuffmanTreeOfHuffmanTreeToBitMask(
+    const uint8_t* code_length_bitdepth,
+    int* storage_ix, uint8_t* storage) {
+  static const uint8_t kStorageOrder[kCodeLengthCodes] = {
+    17, 18, 0, 1, 2, 3, 4, 5, 16, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
+  };
+  // Throw away trailing zeros:
+  int codes_to_store = kCodeLengthCodes;
+  for (; codes_to_store > 4; --codes_to_store) {
+    if (code_length_bitdepth[kStorageOrder[codes_to_store - 1]] != 0) {
+      break;
+    }
+  }
+  WriteBits(4, codes_to_store - 4, storage_ix, storage);
+  for (int i = 0; i < codes_to_store; ++i) {
+    WriteBits(3, code_length_bitdepth[kStorageOrder[i]], storage_ix, storage);
+  }
+}
+
+void StoreHuffmanTreeToBitMask(
+    const uint8_t* huffman_tree,
+    const uint8_t* huffman_tree_extra_bits,
+    const int huffman_tree_size,
+    const EntropyCode<kCodeLengthCodes>& entropy,
+    int* storage_ix, uint8_t* storage) {
+  for (int i = 0; i < huffman_tree_size; ++i) {
+    const int ix = huffman_tree[i];
+    const int extra_bits = huffman_tree_extra_bits[i];
+    EntropyEncode(ix, entropy, storage_ix, storage);
+    switch (ix) {
+      case 16:
+        WriteBits(2, extra_bits, storage_ix, storage);
+        break;
+      case 17:
+        WriteBits(3, extra_bits, storage_ix, storage);
+        break;
+      case 18:
+        WriteBits(7, extra_bits, storage_ix, storage);
+        break;
+    }
+  }
+}
+
+template<int kSize>
+void StoreHuffmanCode(const EntropyCode<kSize>& code, int alphabet_size,
+                      int* storage_ix, uint8_t* storage) {
+  const int kMaxBits = 8;
+  const int kMaxSymbol = 1 << kMaxBits;
+
+  if (code.count_ == 0) {   // emit minimal tree for empty cases
+    // bits: small tree marker: 1, count-1: 0, large 8-bit code: 0, code: 0
+    WriteBits(4, 0x01, storage_ix, storage);
+    return;
+  }
+  if (code.count_ <= 2 &&
+      code.symbols_[0] < kMaxSymbol &&
+      code.symbols_[1] < kMaxSymbol) {
+    // Small tree marker to encode 1 or 2 symbols.
+    WriteBits(1, 1, storage_ix, storage);
+    WriteBits(1, code.count_ - 1, storage_ix, storage);
+    if (code.symbols_[0] <= 1) {
+      // Code bit for small (1 bit) symbol value.
+      WriteBits(1, 0, storage_ix, storage);
+      WriteBits(1, code.symbols_[0], storage_ix, storage);
+    } else {
+      WriteBits(1, 1, storage_ix, storage);
+      WriteBits(8, code.symbols_[0], storage_ix, storage);
+    }
+    if (code.count_ == 2) {
+      WriteBits(8, code.symbols_[1], storage_ix, storage);
+    }
+    return;
+  }
+  WriteBits(1, 0, storage_ix, storage);
+
+  uint8_t huffman_tree[kSize];
+  uint8_t huffman_tree_extra_bits[kSize];
+  int huffman_tree_size = 0;
+  WriteHuffmanTree(&code.depth_[0],
+                   alphabet_size,
+                   &huffman_tree[0],
+                   &huffman_tree_extra_bits[0],
+                   &huffman_tree_size);
+  Histogram<kCodeLengthCodes> huffman_tree_histogram;
+  memset(huffman_tree_histogram.data_, 0, sizeof(huffman_tree_histogram.data_));
+  for (int i = 0; i < huffman_tree_size; ++i) {
+    huffman_tree_histogram.Add(huffman_tree[i]);
+  }
+  EntropyCode<kCodeLengthCodes> huffman_tree_entropy;
+  BuildEntropyCode(huffman_tree_histogram, 7, kCodeLengthCodes,
+                   &huffman_tree_entropy);
+  Histogram<kCodeLengthCodes> trimmed_histogram = huffman_tree_histogram;
+  uint8_t* last_code = &huffman_tree[huffman_tree_size - 1];
+  while (*last_code == 0 || *last_code >= 17) {
+    trimmed_histogram.Remove(*last_code--);
+  }
+  int trimmed_size = trimmed_histogram.total_count_;
+  bool write_length = false;
+  if (trimmed_size > 1 && trimmed_size < huffman_tree_size) {
+    EntropyCode<kCodeLengthCodes> trimmed_entropy;
+    BuildEntropyCode(trimmed_histogram, 7, kCodeLengthCodes, &trimmed_entropy);
+    int huffman_bit_cost = HuffmanTreeBitCost(huffman_tree_histogram,
+                                              huffman_tree_entropy);
+    int trimmed_bit_cost = HuffmanTreeBitCost(trimmed_histogram,
+                                              trimmed_entropy);;
+    const int nbits = Log2Ceiling(trimmed_size - 1);
+    const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2;
+    if (trimmed_bit_cost + 3 + 2 * nbitpairs < huffman_bit_cost) {
+      write_length = true;
+      huffman_tree_size = trimmed_size;
+      huffman_tree_entropy = trimmed_entropy;
+    }
+  }
+
+  StoreHuffmanTreeOfHuffmanTreeToBitMask(
+      &huffman_tree_entropy.depth_[0], storage_ix, storage);
+  WriteBits(1, write_length, storage_ix, storage);
+  if (write_length) {
+    const int nbits = Log2Ceiling(huffman_tree_size - 1);
+    const int nbitpairs = (nbits == 0) ? 1 : (nbits + 1) / 2;
+    WriteBits(3, nbitpairs - 1, storage_ix, storage);
+    WriteBits(nbitpairs * 2, huffman_tree_size - 2, storage_ix, storage);
+  }
+  StoreHuffmanTreeToBitMask(&huffman_tree[0], &huffman_tree_extra_bits[0],
+                            huffman_tree_size, huffman_tree_entropy,
+                            storage_ix, storage);
+}
+
+template<int kSize>
+void StoreHuffmanCodes(const std::vector<EntropyCode<kSize> >& codes,
+                       int alphabet_size,
+                       int* storage_ix, uint8_t* storage) {
+  for (int i = 0; i < codes.size(); ++i) {
+    StoreHuffmanCode(codes[i], alphabet_size, storage_ix, storage);
+  }
+}
+
+void EncodeCommand(const Command& cmd,
+                   const EntropyCodeCommand& entropy,
+                   int* storage_ix, uint8_t* storage) {
+  int code = cmd.command_prefix_;
+  EntropyEncode(code, entropy, storage_ix, storage);
+  if (code >= 128) {
+    code -= 128;
+  }
+  int insert_extra_bits = InsertLengthExtraBits(code);
+  uint64_t insert_extra_bits_val =
+      cmd.insert_length_ - InsertLengthOffset(code);
+  int copy_extra_bits = CopyLengthExtraBits(code);
+  uint64_t copy_extra_bits_val = cmd.copy_length_ - CopyLengthOffset(code);
+  if (insert_extra_bits > 0) {
+    WriteBits(insert_extra_bits, insert_extra_bits_val, storage_ix, storage);
+  }
+  if (copy_extra_bits > 0) {
+    WriteBits(copy_extra_bits, copy_extra_bits_val, storage_ix, storage);
+  }
+}
+
+void EncodeCopyDistance(const Command& cmd, const EntropyCodeDistance& entropy,
+                        int* storage_ix, uint8_t* storage) {
+  int code = cmd.distance_prefix_;
+  int extra_bits = cmd.distance_extra_bits_;
+  uint64_t extra_bits_val = cmd.distance_extra_bits_value_;
+  EntropyEncode(code, entropy, storage_ix, storage);
+  if (extra_bits > 0) {
+    WriteBits(extra_bits, extra_bits_val, storage_ix, storage);
+  }
+}
+
+
+void ComputeDistanceShortCodes(std::vector<Command>* cmds) {
+  static const int kIndexOffset[16] = {
+    3, 2, 1, 0, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2
+  };
+  static const int kValueOffset[16] = {
+    0, 0, 0, 0, -1, 1, -2, 2, -3, 3, -1, 1, -2, 2, -3, 3
+  };
+  int dist_ringbuffer[4] = { 4, 11, 15, 16 };
+  int ringbuffer_idx = 0;
+  for (int i = 0; i < cmds->size(); ++i) {
+    int cur_dist = (*cmds)[i].copy_distance_;
+    if (cur_dist == 0) break;
+    int dist_code = cur_dist + 16;
+    for (int k = 0; k < 16; ++k) {
+      // Only accept more popular choices.
+      if (cur_dist < 11 && ((k >= 2 && k < 4) || k >= 6)) {
+        // Typically unpopular ranges, don't replace a short distance
+        // with them.
+        continue;
+      }
+      int comp = (dist_ringbuffer[(ringbuffer_idx + kIndexOffset[k]) & 3] +
+                  kValueOffset[k]);
+      if (cur_dist == comp) {
+        dist_code = k + 1;
+        break;
+      }
+    }
+    if (dist_code > 1) {
+      dist_ringbuffer[ringbuffer_idx & 3] = cur_dist;
+      ++ringbuffer_idx;
+    }
+    (*cmds)[i].distance_code_ = dist_code;
+  }
+}
+
+void ComputeCommandPrefixes(std::vector<Command>* cmds,
+                            int num_direct_distance_codes,
+                            int distance_postfix_bits) {
+  for (int i = 0; i < cmds->size(); ++i) {
+    Command* cmd = &(*cmds)[i];
+    cmd->command_prefix_ = CommandPrefix(cmd->insert_length_,
+                                         cmd->copy_length_);
+    if (cmd->copy_length_ > 0) {
+      PrefixEncodeCopyDistance(cmd->distance_code_,
+                               num_direct_distance_codes,
+                               distance_postfix_bits,
+                               &cmd->distance_prefix_,
+                               &cmd->distance_extra_bits_,
+                               &cmd->distance_extra_bits_value_);
+    }
+    if (cmd->command_prefix_ < 128 && cmd->distance_prefix_ == 0) {
+      cmd->distance_prefix_ = 0xffff;
+    } else {
+      cmd->command_prefix_ += 128;
+    }
+  }
+}
+
+int IndexOf(const std::vector<int>& v, int value) {
+  for (int i = 0; i < v.size(); ++i) {
+    if (v[i] == value) return i;
+  }
+  return -1;
+}
+
+void MoveToFront(std::vector<int>* v, int index) {
+  int value = (*v)[index];
+  for (int i = index; i > 0; --i) {
+    (*v)[i] = (*v)[i - 1];
+  }
+  (*v)[0] = value;
+}
+
+std::vector<int> MoveToFrontTransform(const std::vector<int>& v) {
+  if (v.empty()) return v;
+  std::vector<int> mtf(*max_element(v.begin(), v.end()) + 1);
+  for (int i = 0; i < mtf.size(); ++i) mtf[i] = i;
+  std::vector<int> result(v.size());
+  for (int i = 0; i < v.size(); ++i) {
+    int index = IndexOf(mtf, v[i]);
+    result[i] = index;
+    MoveToFront(&mtf, index);
+  }
+  return result;
+}
+
+// Finds runs of zeros in v_in and replaces them with a prefix code of the run
+// length plus extra bits in *v_out and *extra_bits. Non-zero values in v_in are
+// shifted by *max_length_prefix. Will not create prefix codes bigger than the
+// initial value of *max_run_length_prefix. The prefix code of run length L is
+// simply Log2Floor(L) and the number of extra bits is the same as the prefix
+// code.
+void RunLengthCodeZeros(const std::vector<int>& v_in,
+                        int* max_run_length_prefix,
+                        std::vector<int>* v_out,
+                        std::vector<int>* extra_bits) {
+  int max_reps = 0;
+  for (int i = 0; i < v_in.size();) {
+    for (; i < v_in.size() && v_in[i] != 0; ++i) ;
+    int reps = 0;
+    for (; i < v_in.size() && v_in[i] == 0; ++i) {
+      ++reps;
+    }
+    max_reps = std::max(reps, max_reps);
+  }
+  int max_prefix = max_reps > 0 ? Log2Floor(max_reps) : 0;
+  *max_run_length_prefix = std::min(max_prefix, *max_run_length_prefix);
+  for (int i = 0; i < v_in.size();) {
+    if (v_in[i] != 0) {
+      v_out->push_back(v_in[i] + *max_run_length_prefix);
+      extra_bits->push_back(0);
+      ++i;
+    } else {
+      int reps = 1;
+      for (uint32_t k = i + 1; k < v_in.size() && v_in[k] == 0; ++k) {
+        ++reps;
+      }
+      i += reps;
+      while (reps) {
+        if (reps < (2 << *max_run_length_prefix)) {
+          int run_length_prefix = Log2Floor(reps);
+          v_out->push_back(run_length_prefix);
+          extra_bits->push_back(reps - (1 << run_length_prefix));
+          break;
+        } else {
+          v_out->push_back(*max_run_length_prefix);
+          extra_bits->push_back((1 << *max_run_length_prefix) - 1);
+          reps -= (2 << *max_run_length_prefix) - 1;
+        }
+      }
+    }
+  }
+}
+
+// Returns a maximum zero-run-length-prefix value such that run-length coding
+// zeros in v with this maximum prefix value and then encoding the resulting
+// histogram and entropy-coding v produces the least amount of bits.
+int BestMaxZeroRunLengthPrefix(const std::vector<int>& v) {
+  int min_cost = std::numeric_limits<int>::max();
+  int best_max_prefix = 0;
+  for (int max_prefix = 0; max_prefix <= 16; ++max_prefix) {
+    std::vector<int> rle_symbols;
+    std::vector<int> extra_bits;
+    int max_run_length_prefix = max_prefix;
+    RunLengthCodeZeros(v, &max_run_length_prefix, &rle_symbols, &extra_bits);
+    if (max_run_length_prefix < max_prefix) break;
+    HistogramLiteral histogram;
+    for (int i = 0; i < rle_symbols.size(); ++i) {
+      histogram.Add(rle_symbols[i]);
+    }
+    int bit_cost = PopulationCost(histogram);
+    if (max_prefix > 0) {
+      bit_cost += 4;
+    }
+    for (int i = 1; i <= max_prefix; ++i) {
+      bit_cost += histogram.data_[i] * i;  // extra bits
+    }
+    if (bit_cost < min_cost) {
+      min_cost = bit_cost;
+      best_max_prefix = max_prefix;
+    }
+  }
+  return best_max_prefix;
+}
+
+void EncodeContextMap(const std::vector<int>& context_map,
+                      int context_mode,
+                      int context_mode_bits,
+                      int num_clusters,
+                      int* storage_ix, uint8_t* storage) {
+  if (context_mode == 0) {
+    WriteBits(1, 0, storage_ix, storage);  // no context
+    return;
+  }
+
+  WriteBits(1, 1, storage_ix, storage);  // have context
+  if (context_mode_bits > 0) {
+    WriteBits(context_mode_bits, context_mode - 1, storage_ix, storage);
+  }
+  WriteBits(8, num_clusters - 1, storage_ix, storage);
+
+  if (num_clusters == 1 || num_clusters == context_map.size()) {
+    return;
+  }
+
+  std::vector<int> transformed_symbols = MoveToFrontTransform(context_map);
+  std::vector<int> rle_symbols;
+  std::vector<int> extra_bits;
+  int max_run_length_prefix = BestMaxZeroRunLengthPrefix(transformed_symbols);
+  RunLengthCodeZeros(transformed_symbols, &max_run_length_prefix,
+                     &rle_symbols, &extra_bits);
+  HistogramLiteral symbol_histogram;
+  for (int i = 0; i < rle_symbols.size(); ++i) {
+    symbol_histogram.Add(rle_symbols[i]);
+  }
+  EntropyCodeLiteral symbol_code;
+  BuildEntropyCode(symbol_histogram, 15, num_clusters + max_run_length_prefix,
+                   &symbol_code);
+  bool use_rle = max_run_length_prefix > 0;
+  WriteBits(1, use_rle, storage_ix, storage);
+  if (use_rle) {
+    WriteBits(4, max_run_length_prefix - 1, storage_ix, storage);
+  }
+  StoreHuffmanCode(symbol_code, num_clusters + max_run_length_prefix,
+                   storage_ix, storage);
+  for (int i = 0; i < rle_symbols.size(); ++i) {
+    EntropyEncode(rle_symbols[i], symbol_code, storage_ix, storage);
+    if (rle_symbols[i] > 0 && rle_symbols[i] <= max_run_length_prefix) {
+      WriteBits(rle_symbols[i], extra_bits[i], storage_ix, storage);
+    }
+  }
+  WriteBits(1, 1, storage_ix, storage);  // use move-to-front
+}
+
+template<int kSize>
+void BuildEntropyCodes(const std::vector<Histogram<kSize> >& histograms,
+                       int alphabet_size,
+                       std::vector<EntropyCode<kSize> >* entropy_codes) {
+  entropy_codes->resize(histograms.size());
+  for (int i = 0; i < histograms.size(); ++i) {
+    BuildEntropyCode(histograms[i], 15, alphabet_size, &(*entropy_codes)[i]);
+  }
+}
+
+struct BlockSplitCode {
+  EntropyCodeLiteral block_type_code;
+  EntropyCodeBlockLength block_len_code;
+};
+
+void EncodeBlockLength(const EntropyCodeBlockLength& entropy,
+                       int length,
+                       int* storage_ix, uint8_t* storage) {
+  int len_code = BlockLengthPrefix(length);
+  int extra_bits = BlockLengthExtraBits(len_code);
+  int extra_bits_value = length - BlockLengthOffset(len_code);
+  EntropyEncode(len_code, entropy, storage_ix, storage);
+
+  if (extra_bits > 0) {
+    WriteBits(extra_bits, extra_bits_value, storage_ix, storage);
+  }
+}
+
+void ComputeBlockTypeShortCodes(BlockSplit* split) {
+  if (split->num_types_ <= 1) {
+    split->num_types_ = 1;
+    return;
+  }
+  int ringbuffer[2] = { 0, 1 };
+  size_t index = 0;
+  for (int i = 0; i < split->types_.size(); ++i) {
+    int type = split->types_[i];
+    int type_code;
+    if (type == ringbuffer[index & 1]) {
+      type_code = 0;
+    } else if (type == ringbuffer[(index - 1) & 1] + 1) {
+      type_code = 1;
+    } else {
+      type_code = type + 2;
+    }
+    ringbuffer[index & 1] = type;
+    ++index;
+    split->type_codes_.push_back(type_code);
+  }
+}
+
+void BuildAndEncodeBlockSplitCode(const BlockSplit& split,
+                                  BlockSplitCode* code,
+                                  int* storage_ix, uint8_t* storage) {
+  if (split.num_types_ <= 1) {
+    WriteBits(1, 0, storage_ix, storage);
+    return;
+  }
+  WriteBits(1, 1, storage_ix, storage);
+  HistogramLiteral type_histo;
+  for (int i = 0; i < split.type_codes_.size(); ++i) {
+    type_histo.Add(split.type_codes_[i]);
+  }
+  BuildEntropyCode(type_histo, 15, split.num_types_ + 2,
+                   &code->block_type_code);
+  HistogramBlockLength length_histo;
+  for (int i = 0; i < split.lengths_.size(); ++i) {
+    length_histo.Add(BlockLengthPrefix(split.lengths_[i]));
+  }
+  BuildEntropyCode(length_histo, 15, kNumBlockLenPrefixes,
+                   &code->block_len_code);
+  WriteBits(8, split.num_types_ - 1, storage_ix, storage);
+  StoreHuffmanCode(code->block_type_code, split.num_types_ + 2,
+                   storage_ix, storage);
+  StoreHuffmanCode(code->block_len_code, kNumBlockLenPrefixes,
+                   storage_ix, storage);
+  EncodeBlockLength(code->block_len_code, split.lengths_[0],
+                    storage_ix, storage);
+}
+
+void MoveAndEncode(const BlockSplitCode& code,
+                   BlockSplitIterator* it,
+                   int* storage_ix, uint8_t* storage) {
+  if (it->length_ == 0) {
+    ++it->idx_;
+    it->type_ = it->split_.types_[it->idx_];
+    it->length_ = it->split_.lengths_[it->idx_];
+    uint8_t type_code = it->split_.type_codes_[it->idx_];
+    EntropyEncode(type_code, code.block_type_code, storage_ix, storage);
+    EncodeBlockLength(code.block_len_code, it->length_, storage_ix, storage);
+  }
+  --it->length_;
+}
+
+struct EncodingParams {
+  int num_direct_distance_codes;
+  int distance_postfix_bits;
+  int literal_context_mode;
+  int distance_context_mode;
+};
+
+struct MetaBlock {
+  std::vector<Command> cmds;
+  EncodingParams params;
+  BlockSplit literal_split;
+  BlockSplit command_split;
+  BlockSplit distance_split;
+  std::vector<int> literal_context_map;
+  std::vector<int> distance_context_map;
+  std::vector<HistogramLiteral> literal_histograms;
+  std::vector<HistogramCommand> command_histograms;
+  std::vector<HistogramDistance> distance_histograms;
+};
+
+void BuildMetaBlock(const EncodingParams& params,
+                    const std::vector<Command>& cmds,
+                    const uint8_t* input_buffer,
+                    size_t pos,
+                    MetaBlock* mb) {
+  mb->cmds = cmds;
+  mb->params = params;
+  ComputeCommandPrefixes(&mb->cmds,
+                         mb->params.num_direct_distance_codes,
+                         mb->params.distance_postfix_bits);
+  SplitBlock(mb->cmds,
+             input_buffer + pos,
+             &mb->literal_split,
+             &mb->command_split,
+             &mb->distance_split);
+  ComputeBlockTypeShortCodes(&mb->literal_split);
+  ComputeBlockTypeShortCodes(&mb->command_split);
+  ComputeBlockTypeShortCodes(&mb->distance_split);
+
+  int num_literal_contexts_per_block_type =
+      NumContexts(mb->params.literal_context_mode);
+  int num_literal_contexts =
+      mb->literal_split.num_types_ *
+      num_literal_contexts_per_block_type;
+  int num_distance_contexts_per_block_type =
+      (mb->params.distance_context_mode > 0 ? 4 : 1);
+  int num_distance_contexts =
+      mb->distance_split.num_types_ *
+      num_distance_contexts_per_block_type;
+  std::vector<HistogramLiteral> literal_histograms(num_literal_contexts);
+  mb->command_histograms.resize(mb->command_split.num_types_);
+  std::vector<HistogramDistance> distance_histograms(num_distance_contexts);
+  BuildHistograms(mb->cmds,
+                  mb->literal_split,
+                  mb->command_split,
+                  mb->distance_split,
+                  input_buffer,
+                  pos,
+                  mb->params.literal_context_mode,
+                  mb->params.distance_context_mode,
+                  &literal_histograms,
+                  &mb->command_histograms,
+                  &distance_histograms);
+
+  // Histogram ids need to fit in one byte and there are 16 ids reserved for
+  // run length codes, which leaves a maximum number of 240 histograms.
+  static const int kMaxNumberOfHistograms = 240;
+
+  mb->literal_histograms = literal_histograms;
+  if (mb->params.literal_context_mode > 0) {
+    ClusterHistograms(literal_histograms,
+                      num_literal_contexts_per_block_type,
+                      mb->literal_split.num_types_,
+                      kMaxNumberOfHistograms,
+                      &mb->literal_histograms,
+                      &mb->literal_context_map);
+  }
+
+  mb->distance_histograms = distance_histograms;
+  if (mb->params.distance_context_mode > 0) {
+    ClusterHistograms(distance_histograms,
+                      num_distance_contexts_per_block_type,
+                      mb->distance_split.num_types_,
+                      kMaxNumberOfHistograms,
+                      &mb->distance_histograms,
+                      &mb->distance_context_map);
+  }
+}
+
+size_t MetaBlockLength(const std::vector<Command>& cmds) {
+  size_t length = 0;
+  for (int i = 0; i < cmds.size(); ++i) {
+    const Command& cmd = cmds[i];
+    length += cmd.insert_length_ + cmd.copy_length_;
+  }
+  return length;
+}
+
+void StoreMetaBlock(const MetaBlock& mb,
+                    const uint8_t* input_buffer,
+                    int input_size_bits,
+                    bool is_last,
+                    size_t* pos,
+                    int* storage_ix, uint8_t* storage) {
+  size_t length = MetaBlockLength(mb.cmds);
+  const size_t end_pos = *pos + length;
+  EncodeMetaBlockLength(input_size_bits, length - 1, is_last,
+                        storage_ix, storage);
+  BlockSplitCode literal_split_code;
+  BlockSplitCode command_split_code;
+  BlockSplitCode distance_split_code;
+  BuildAndEncodeBlockSplitCode(mb.literal_split, &literal_split_code,
+                               storage_ix, storage);
+  BuildAndEncodeBlockSplitCode(mb.command_split, &command_split_code,
+                               storage_ix, storage);
+  BuildAndEncodeBlockSplitCode(mb.distance_split, &distance_split_code,
+                               storage_ix, storage);
+  WriteBits(2, mb.params.distance_postfix_bits, storage_ix, storage);
+  WriteBits(4,
+            mb.params.num_direct_distance_codes >>
+            mb.params.distance_postfix_bits, storage_ix, storage);
+  int num_distance_codes =
+      kNumDistanceShortCodes + mb.params.num_direct_distance_codes +
+      (48 << mb.params.distance_postfix_bits);
+  EncodeContextMap(mb.literal_context_map, mb.params.literal_context_mode, 4,
+                   mb.literal_histograms.size(), storage_ix, storage);
+  EncodeContextMap(mb.distance_context_map, mb.params.distance_context_mode, 0,
+                   mb.distance_histograms.size(), storage_ix, storage);
+  std::vector<EntropyCodeLiteral> literal_codes;
+  std::vector<EntropyCodeCommand> command_codes;
+  std::vector<EntropyCodeDistance> distance_codes;
+  BuildEntropyCodes(mb.literal_histograms, 256, &literal_codes);
+  BuildEntropyCodes(mb.command_histograms, kNumCommandPrefixes,
+                    &command_codes);
+  BuildEntropyCodes(mb.distance_histograms, num_distance_codes,
+                    &distance_codes);
+  StoreHuffmanCodes(literal_codes, 256, storage_ix, storage);
+  StoreHuffmanCodes(command_codes, kNumCommandPrefixes, storage_ix, storage);
+  StoreHuffmanCodes(distance_codes, num_distance_codes, storage_ix, storage);
+  BlockSplitIterator literal_it(mb.literal_split);
+  BlockSplitIterator command_it(mb.command_split);
+  BlockSplitIterator distance_it(mb.distance_split);
+  for (int i = 0; i < mb.cmds.size(); ++i) {
+    const Command& cmd = mb.cmds[i];
+    MoveAndEncode(command_split_code, &command_it, storage_ix, storage);
+    EncodeCommand(cmd, command_codes[command_it.type_], storage_ix, storage);
+    for (int j = 0; j < cmd.insert_length_; ++j) {
+      MoveAndEncode(literal_split_code, &literal_it, storage_ix, storage);
+      int histogram_idx = literal_it.type_;
+      if (mb.params.literal_context_mode > 0) {
+        uint8_t prev_byte = *pos > 0 ? input_buffer[*pos - 1] : 0;
+        uint8_t prev_byte2 = *pos > 1 ? input_buffer[*pos - 2] : 0;
+        uint8_t prev_byte3 = *pos > 2 ? input_buffer[*pos - 3] : 0;
+        int context = (literal_it.type_ *
+                       NumContexts(mb.params.literal_context_mode) +
+                       Context(prev_byte, prev_byte2, prev_byte3,
+                               mb.params.literal_context_mode));
+        histogram_idx = mb.literal_context_map[context];
+      }
+      EntropyEncode(input_buffer[(*pos)++],
+                    literal_codes[histogram_idx], storage_ix, storage);
+    }
+    if (*pos < end_pos && cmd.distance_prefix_ != 0xffff) {
+      MoveAndEncode(distance_split_code, &distance_it, storage_ix, storage);
+      int histogram_index = distance_it.type_;
+      if (mb.params.distance_context_mode > 0) {
+        int context = distance_it.type_ << 2;
+        context += (cmd.copy_length_ > 4) ? 3 : cmd.copy_length_ - 2;
+        histogram_index = mb.distance_context_map[context];
+      }
+      EncodeCopyDistance(cmd, distance_codes[histogram_index],
+                         storage_ix, storage);
+    }
+    *pos += cmd.copy_length_;
+  }
+}
+
+int BrotliCompressBuffer(size_t input_size,
+                         const uint8_t* input_buffer,
+                         size_t* encoded_size,
+                         uint8_t* encoded_buffer) {
+  int storage_ix = 0;
+  uint8_t* storage = encoded_buffer;
+  WriteBitsPrepareStorage(storage_ix, storage);
+  EncodeSize(input_size, &storage_ix, storage);
+
+  if (input_size == 0) {
+    *encoded_size = (storage_ix + 7) >> 3;
+    return 1;
+  }
+  int input_size_bits = Log2Ceiling(input_size);
+
+  std::vector<Command> all_commands;
+  CreateBackwardReferences(input_buffer, input_size, &all_commands);
+  ComputeDistanceShortCodes(&all_commands);
+
+  std::vector<std::vector<Command> > meta_block_commands;
+  SplitBlockByTotalLength(all_commands, input_size, 2 << 20,
+                          &meta_block_commands);
+
+  size_t pos = 0;
+  for (int block_idx = 0; block_idx < meta_block_commands.size(); ++block_idx) {
+    const std::vector<Command>& commands = meta_block_commands[block_idx];
+    bool is_last_meta_block = (block_idx + 1 == meta_block_commands.size());
+    EncodingParams params;
+    params.num_direct_distance_codes = 12;
+    params.distance_postfix_bits = 1;
+    params.literal_context_mode = CONTEXT_SIGNED_MIXED_3BYTE;
+    params.distance_context_mode = 1;
+    MetaBlock mb;
+    BuildMetaBlock(params, commands, input_buffer, pos, &mb);
+    StoreMetaBlock(mb, input_buffer, input_size_bits, is_last_meta_block,
+                   &pos, &storage_ix, storage);
+  }
+
+  *encoded_size = (storage_ix + 7) >> 3;
+  return 1;
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/encode.h b/brotli/enc/encode.h
new file mode 100644
index 0000000..6e4044d
--- /dev/null
+++ b/brotli/enc/encode.h
@@ -0,0 +1,37 @@
+// 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 compression
+
+#ifndef BROTLI_ENC_ENCODE_H_
+#define BROTLI_ENC_ENCODE_H_
+
+#include <stddef.h>
+#include <stdint.h>
+#include <string>
+
+namespace brotli {
+
+// Compresses the data in input_buffer into encoded_buffer, and sets
+// *encoded_size to the compressed length.
+// Returns 0 if there was an error and 1 otherwise.
+int BrotliCompressBuffer(size_t input_size,
+                         const uint8_t* input_buffer,
+                         size_t* encoded_size,
+                         uint8_t* encoded_buffer);
+
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_ENCODE_H_
diff --git a/brotli/enc/entropy_encode.cc b/brotli/enc/entropy_encode.cc
new file mode 100644
index 0000000..9a4d3e4
--- /dev/null
+++ b/brotli/enc/entropy_encode.cc
@@ -0,0 +1,397 @@
+// Copyright 2010 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.
+//
+// Entropy encoding (Huffman) utilities.
+
+#include "./entropy_encode.h"
+
+#include <stdint.h>
+#include <algorithm>
+#include <limits>
+#include <vector>
+
+#include "./histogram.h"
+
+namespace brotli {
+
+namespace {
+
+struct HuffmanTree {
+  HuffmanTree();
+  HuffmanTree(int count, int16_t left, int16_t right)
+      : total_count_(count),
+        index_left_(left),
+        index_right_or_value_(right) {
+  }
+  int total_count_;
+  int16_t index_left_;
+  int16_t index_right_or_value_;
+};
+
+HuffmanTree::HuffmanTree() {}
+
+// Sort the root nodes, least popular first.
+bool SortHuffmanTree(const HuffmanTree &v0, const HuffmanTree &v1) {
+  return v0.total_count_ < v1.total_count_;
+}
+
+void SetDepth(const HuffmanTree &p,
+              HuffmanTree *pool,
+              uint8_t *depth,
+              int level) {
+  if (p.index_left_ >= 0) {
+    ++level;
+    SetDepth(pool[p.index_left_], pool, depth, level);
+    SetDepth(pool[p.index_right_or_value_], pool, depth, level);
+  } else {
+    depth[p.index_right_or_value_] = level;
+  }
+}
+
+}  // namespace
+
+// This function will create a Huffman tree.
+//
+// The catch here is that the tree cannot be arbitrarily deep.
+// Brotli specifies a maximum depth of 15 bits for "code trees"
+// and 7 bits for "code length code trees."
+//
+// count_limit is the value that is to be faked as the minimum value
+// and this minimum value is raised until the tree matches the
+// maximum length requirement.
+//
+// This algorithm is not of excellent performance for very long data blocks,
+// especially when population counts are longer than 2**tree_limit, but
+// we are not planning to use this with extremely long blocks.
+//
+// See http://en.wikipedia.org/wiki/Huffman_coding
+void CreateHuffmanTree(const int *data,
+                       const int length,
+                       const int tree_limit,
+                       uint8_t *depth) {
+  // For block sizes below 64 kB, we never need to do a second iteration
+  // of this loop. Probably all of our block sizes will be smaller than
+  // that, so this loop is mostly of academic interest. If we actually
+  // would need this, we would be better off with the Katajainen algorithm.
+  for (int count_limit = 1; ; count_limit *= 2) {
+    std::vector<HuffmanTree> tree;
+    tree.reserve(2 * length + 1);
+
+    for (int i = 0; i < length; ++i) {
+      if (data[i]) {
+        const int count = std::max(data[i], count_limit);
+        tree.push_back(HuffmanTree(count, -1, i));
+      }
+    }
+
+    const int n = tree.size();
+    if (n == 1) {
+      depth[tree[0].index_right_or_value_] = 1;      // Only one element.
+      break;
+    }
+
+    std::sort(tree.begin(), tree.end(), SortHuffmanTree);
+
+    // The nodes are:
+    // [0, n): the sorted leaf nodes that we start with.
+    // [n]: we add a sentinel here.
+    // [n + 1, 2n): new parent nodes are added here, starting from
+    //              (n+1). These are naturally in ascending order.
+    // [2n]: we add a sentinel at the end as well.
+    // There will be (2n+1) elements at the end.
+    const HuffmanTree sentinel(std::numeric_limits<int>::max(), -1, -1);
+    tree.push_back(sentinel);
+    tree.push_back(sentinel);
+
+    int i = 0;      // Points to the next leaf node.
+    int j = n + 1;  // Points to the next non-leaf node.
+    for (int k = n - 1; k > 0; --k) {
+      int left, right;
+      if (tree[i].total_count_ <= tree[j].total_count_) {
+        left = i;
+        ++i;
+      } else {
+        left = j;
+        ++j;
+      }
+      if (tree[i].total_count_ <= tree[j].total_count_) {
+        right = i;
+        ++i;
+      } else {
+        right = j;
+        ++j;
+      }
+
+      // The sentinel node becomes the parent node.
+      int j_end = tree.size() - 1;
+      tree[j_end].total_count_ =
+          tree[left].total_count_ + tree[right].total_count_;
+      tree[j_end].index_left_ = left;
+      tree[j_end].index_right_or_value_ = right;
+
+      // Add back the last sentinel node.
+      tree.push_back(sentinel);
+    }
+    SetDepth(tree[2 * n - 1], &tree[0], depth, 0);
+
+    // We need to pack the Huffman tree in tree_limit bits.
+    // If this was not successful, add fake entities to the lowest values
+    // and retry.
+    if (*std::max_element(&depth[0], &depth[length]) <= tree_limit) {
+      break;
+    }
+  }
+}
+
+void WriteHuffmanTreeRepetitions(
+    const int previous_value,
+    const int value,
+    int repetitions,
+    uint8_t* tree,
+    uint8_t* extra_bits,
+    int* tree_size) {
+  if (previous_value != value) {
+    tree[*tree_size] = value;
+    extra_bits[*tree_size] = 0;
+    ++(*tree_size);
+    --repetitions;
+  }
+  while (repetitions >= 1) {
+    if (repetitions < 3) {
+      for (int i = 0; i < repetitions; ++i) {
+        tree[*tree_size] = value;
+        extra_bits[*tree_size] = 0;
+        ++(*tree_size);
+      }
+      return;
+    } else if (repetitions < 7) {
+      // 3 to 6 left.
+      tree[*tree_size] = 16;
+      extra_bits[*tree_size] = repetitions - 3;
+      ++(*tree_size);
+      return;
+    } else {
+      tree[*tree_size] = 16;
+      extra_bits[*tree_size] = 3;
+      ++(*tree_size);
+      repetitions -= 6;
+    }
+  }
+}
+
+void WriteHuffmanTreeRepetitionsZeros(
+    int repetitions,
+    uint8_t* tree,
+    uint8_t* extra_bits,
+    int* tree_size) {
+  while (repetitions >= 1) {
+    if (repetitions < 3) {
+      for (int i = 0; i < repetitions; ++i) {
+        tree[*tree_size] = 0;
+        extra_bits[*tree_size] = 0;
+        ++(*tree_size);
+      }
+      return;
+    } else if (repetitions < 11) {
+      tree[*tree_size] = 17;
+      extra_bits[*tree_size] = repetitions - 3;
+      ++(*tree_size);
+      return;
+    } else if (repetitions < 139) {
+      tree[*tree_size] = 18;
+      extra_bits[*tree_size] = repetitions - 11;
+      ++(*tree_size);
+      return;
+    } else {
+      tree[*tree_size] = 18;
+      extra_bits[*tree_size] = 0x7f;  // 138 repeated 0s
+      ++(*tree_size);
+      repetitions -= 138;
+    }
+  }
+}
+
+
+// Heuristics for selecting the stride ranges to collapse.
+int ValuesShouldBeCollapsedToStrideAverage(int a, int b) {
+  return abs(a - b) < 4;
+}
+
+int OptimizeHuffmanCountsForRle(int length, int* counts) {
+  int stride;
+  int limit;
+  int sum;
+  uint8_t* good_for_rle;
+  // Let's make the Huffman code more compatible with rle encoding.
+  int i;
+  for (; length >= 0; --length) {
+    if (length == 0) {
+      return 1;  // All zeros.
+    }
+    if (counts[length - 1] != 0) {
+      // Now counts[0..length - 1] does not have trailing zeros.
+      break;
+    }
+  }
+  // 2) Let's mark all population counts that already can be encoded
+  // with an rle code.
+  good_for_rle = (uint8_t*)calloc(length, 1);
+  if (good_for_rle == NULL) {
+    return 0;
+  }
+  {
+    // Let's not spoil any of the existing good rle codes.
+    // Mark any seq of 0's that is longer as 5 as a good_for_rle.
+    // Mark any seq of non-0's that is longer as 7 as a good_for_rle.
+    int symbol = counts[0];
+    int stride = 0;
+    for (i = 0; i < length + 1; ++i) {
+      if (i == length || counts[i] != symbol) {
+        if ((symbol == 0 && stride >= 5) ||
+            (symbol != 0 && stride >= 7)) {
+          int k;
+          for (k = 0; k < stride; ++k) {
+            good_for_rle[i - k - 1] = 1;
+          }
+        }
+        stride = 1;
+        if (i != length) {
+          symbol = counts[i];
+        }
+      } else {
+        ++stride;
+      }
+    }
+  }
+  // 3) Let's replace those population counts that lead to more rle codes.
+  stride = 0;
+  limit = counts[0];
+  sum = 0;
+  for (i = 0; i < length + 1; ++i) {
+    if (i == length || good_for_rle[i] ||
+        (i != 0 && good_for_rle[i - 1]) ||
+        !ValuesShouldBeCollapsedToStrideAverage(counts[i], limit)) {
+      if (stride >= 4 || (stride >= 3 && sum == 0)) {
+        int k;
+        // The stride must end, collapse what we have, if we have enough (4).
+        int count = (sum + stride / 2) / stride;
+        if (count < 1) {
+          count = 1;
+        }
+        if (sum == 0) {
+          // Don't make an all zeros stride to be upgraded to ones.
+          count = 0;
+        }
+        for (k = 0; k < stride; ++k) {
+          // We don't want to change value at counts[i],
+          // that is already belonging to the next stride. Thus - 1.
+          counts[i - k - 1] = count;
+        }
+      }
+      stride = 0;
+      sum = 0;
+      if (i < length - 3) {
+        // All interesting strides have a count of at least 4,
+        // at least when non-zeros.
+        limit = (counts[i] + counts[i + 1] +
+                 counts[i + 2] + counts[i + 3] + 2) / 4;
+      } else if (i < length) {
+        limit = counts[i];
+      } else {
+        limit = 0;
+      }
+    }
+    ++stride;
+    if (i != length) {
+      sum += counts[i];
+      if (stride >= 4) {
+        limit = (sum + stride / 2) / stride;
+      }
+    }
+  }
+  free(good_for_rle);
+  return 1;
+}
+
+
+void WriteHuffmanTree(const uint8_t* depth, const int length,
+                      uint8_t* tree,
+                      uint8_t* extra_bits_data,
+                      int* huffman_tree_size) {
+  int previous_value = 0;
+  for (uint32_t i = 0; i < length;) {
+    const int value = depth[i];
+    int reps = 1;
+    for (uint32_t k = i + 1; k < length && depth[k] == value; ++k) {
+      ++reps;
+    }
+    if (value == 0) {
+      WriteHuffmanTreeRepetitionsZeros(reps, tree, extra_bits_data,
+                                       huffman_tree_size);
+    } else {
+      WriteHuffmanTreeRepetitions(previous_value, value, reps, tree,
+                                  extra_bits_data, huffman_tree_size);
+      previous_value = value;
+    }
+    i += reps;
+  }
+}
+
+namespace {
+
+uint16_t ReverseBits(int num_bits, uint16_t bits) {
+  static const size_t kLut[16] = {  // Pre-reversed 4-bit values.
+    0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
+    0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
+  };
+  size_t retval = kLut[bits & 0xf];
+  for (int i = 4; i < num_bits; i += 4) {
+    retval <<= 4;
+    bits >>= 4;
+    retval |= kLut[bits & 0xf];
+  }
+  retval >>= (-num_bits & 0x3);
+  return retval;
+}
+
+}  // namespace
+
+void ConvertBitDepthsToSymbols(const uint8_t *depth, int len, uint16_t *bits) {
+  // In Brotli, all bit depths are [1..15]
+  // 0 bit depth means that the symbol does not exist.
+  const int kMaxBits = 16;  // 0..15 are values for bits
+  uint16_t bl_count[kMaxBits] = { 0 };
+  {
+    for (int i = 0; i < len; ++i) {
+      ++bl_count[depth[i]];
+    }
+    bl_count[0] = 0;
+  }
+  uint16_t next_code[kMaxBits];
+  next_code[0] = 0;
+  {
+    int code = 0;
+    for (int bits = 1; bits < kMaxBits; ++bits) {
+      code = (code + bl_count[bits - 1]) << 1;
+      next_code[bits] = code;
+    }
+  }
+  for (int i = 0; i < len; ++i) {
+    if (depth[i]) {
+      bits[i] = ReverseBits(depth[i], next_code[depth[i]]++);
+    }
+  }
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/entropy_encode.h b/brotli/enc/entropy_encode.h
new file mode 100644
index 0000000..e5993e6
--- /dev/null
+++ b/brotli/enc/entropy_encode.h
@@ -0,0 +1,112 @@
+// Copyright 2010 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.
+//
+// Entropy encoding (Huffman) utilities.
+
+#ifndef BROTLI_ENC_ENTROPY_ENCODE_H_
+#define BROTLI_ENC_ENTROPY_ENCODE_H_
+
+#include <stdint.h>
+#include <string.h>
+#include "./histogram.h"
+#include "./prefix.h"
+
+namespace brotli {
+
+// This function will create a Huffman tree.
+//
+// The (data,length) contains the population counts.
+// The tree_limit is the maximum bit depth of the Huffman codes.
+//
+// The depth contains the tree, i.e., how many bits are used for
+// the symbol.
+//
+// See http://en.wikipedia.org/wiki/Huffman_coding
+void CreateHuffmanTree(const int *data,
+                       const int length,
+                       const int tree_limit,
+                       uint8_t *depth);
+
+// Change the population counts in a way that the consequent
+// Hufmann tree compression, especially its rle-part will be more
+// likely to compress this data more efficiently.
+//
+// length contains the size of the histogram.
+// counts contains the population counts.
+int OptimizeHuffmanCountsForRle(int length, int* counts);
+
+
+// Write a huffman tree from bit depths into the bitstream representation
+// of a Huffman tree. The generated Huffman tree is to be compressed once
+// more using a Huffman tree
+void WriteHuffmanTree(const uint8_t* depth, const int length,
+                      uint8_t* tree,
+                      uint8_t* extra_bits_data,
+                      int* huffman_tree_size);
+
+// Get the actual bit values for a tree of bit depths.
+void ConvertBitDepthsToSymbols(const uint8_t *depth, int len, uint16_t *bits);
+
+template<int kSize>
+struct EntropyCode {
+  // How many bits for symbol.
+  uint8_t depth_[kSize];
+  // Actual bits used to represent the symbol.
+  uint16_t bits_[kSize];
+  // How many non-zero depth.
+  int count_;
+  // First two symbols with non-zero depth.
+  int symbols_[2];
+};
+
+template<int kSize>
+void BuildEntropyCode(const Histogram<kSize>& histogram,
+                      const int tree_limit,
+                      const int alphabet_size,
+                      EntropyCode<kSize>* code) {
+  memset(code->depth_, 0, sizeof(code->depth_));
+  memset(code->bits_, 0, sizeof(code->bits_));
+  memset(code->symbols_, 0, sizeof(code->symbols_));
+  code->count_ = 0;
+  if (histogram.total_count_ == 0) return;
+  for (int i = 0; i < kSize; ++i) {
+    if (histogram.data_[i] > 0) {
+      if (code->count_ < 2) code->symbols_[code->count_] = i;
+      ++code->count_;
+    }
+  }
+  if (code->count_ >= 64) {
+    int counts[kSize];
+    memcpy(counts, &histogram.data_[0], sizeof(counts[0]) * kSize);
+    OptimizeHuffmanCountsForRle(alphabet_size, counts);
+    CreateHuffmanTree(counts, alphabet_size, tree_limit, &code->depth_[0]);
+  } else {
+    CreateHuffmanTree(&histogram.data_[0], alphabet_size, tree_limit,
+                      &code->depth_[0]);
+  }
+  ConvertBitDepthsToSymbols(&code->depth_[0], alphabet_size, &code->bits_[0]);
+}
+
+static const int kCodeLengthCodes = 19;
+
+// Literal entropy code.
+typedef EntropyCode<256> EntropyCodeLiteral;
+// Prefix entropy codes.
+typedef EntropyCode<kNumCommandPrefixes> EntropyCodeCommand;
+typedef EntropyCode<kNumDistancePrefixes> EntropyCodeDistance;
+typedef EntropyCode<kNumBlockLenPrefixes> EntropyCodeBlockLength;
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_ENTROPY_ENCODE_H_
diff --git a/brotli/enc/fast_log.h b/brotli/enc/fast_log.h
new file mode 100644
index 0000000..0b09ea6
--- /dev/null
+++ b/brotli/enc/fast_log.h
@@ -0,0 +1,161 @@
+// 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 fast computation of logarithms.
+
+#ifndef BROTLI_ENC_FAST_LOG_H_
+#define BROTLI_ENC_FAST_LOG_H_
+
+#include <math.h>
+#include <stdint.h>
+
+namespace brotli {
+
+// Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0.
+inline int Log2Floor(uint32_t n) {
+#if defined(__clang__) ||                       \
+  (defined(__GNUC__) &&                                         \
+   ((__GNUC__ == 3 && __GNUC_MINOR__ >= 4) || __GNUC__ >= 4))
+  return n == 0 ? -1 : 31 ^ __builtin_clz(n);
+#else
+  if (n == 0)
+    return -1;
+  int log = 0;
+  uint32_t value = n;
+  for (int i = 4; i >= 0; --i) {
+    int shift = (1 << i);
+    uint32_t x = value >> shift;
+    if (x != 0) {
+      value = x;
+      log += shift;
+    }
+  }
+  assert(value == 1);
+  return log;
+#endif
+}
+
+// Return ceiling(log2(n)) for positive integer n.  Returns -1 iff n == 0.
+inline int Log2Ceiling(uint32_t n) {
+  int floor = Log2Floor(n);
+  if (n == (n &~ (n - 1)))              // zero or a power of two
+    return floor;
+  else
+    return floor + 1;
+}
+
+// A lookup table for small values of log2(int) to be used in entropy
+// computation.
+//
+// ", ".join(["%.16ff" % x for x in [0.0]+[log2(x) for x in range(1, 256)]])
+static const float kLog2Table[] = {
+  0.0000000000000000f, 0.0000000000000000f, 1.0000000000000000f,
+  1.5849625007211563f, 2.0000000000000000f, 2.3219280948873622f,
+  2.5849625007211561f, 2.8073549220576042f, 3.0000000000000000f,
+  3.1699250014423126f, 3.3219280948873626f, 3.4594316186372978f,
+  3.5849625007211565f, 3.7004397181410922f, 3.8073549220576037f,
+  3.9068905956085187f, 4.0000000000000000f, 4.0874628412503400f,
+  4.1699250014423122f, 4.2479275134435852f, 4.3219280948873626f,
+  4.3923174227787607f, 4.4594316186372973f, 4.5235619560570131f,
+  4.5849625007211570f, 4.6438561897747244f, 4.7004397181410926f,
+  4.7548875021634691f, 4.8073549220576037f, 4.8579809951275728f,
+  4.9068905956085187f, 4.9541963103868758f, 5.0000000000000000f,
+  5.0443941193584534f, 5.0874628412503400f, 5.1292830169449664f,
+  5.1699250014423122f, 5.2094533656289501f, 5.2479275134435852f,
+  5.2854022188622487f, 5.3219280948873626f, 5.3575520046180838f,
+  5.3923174227787607f, 5.4262647547020979f, 5.4594316186372973f,
+  5.4918530963296748f, 5.5235619560570131f, 5.5545888516776376f,
+  5.5849625007211570f, 5.6147098441152083f, 5.6438561897747244f,
+  5.6724253419714961f, 5.7004397181410926f, 5.7279204545631996f,
+  5.7548875021634691f, 5.7813597135246599f, 5.8073549220576046f,
+  5.8328900141647422f, 5.8579809951275719f, 5.8826430493618416f,
+  5.9068905956085187f, 5.9307373375628867f, 5.9541963103868758f,
+  5.9772799234999168f, 6.0000000000000000f, 6.0223678130284544f,
+  6.0443941193584534f, 6.0660891904577721f, 6.0874628412503400f,
+  6.1085244567781700f, 6.1292830169449672f, 6.1497471195046822f,
+  6.1699250014423122f, 6.1898245588800176f, 6.2094533656289510f,
+  6.2288186904958804f, 6.2479275134435861f, 6.2667865406949019f,
+  6.2854022188622487f, 6.3037807481771031f, 6.3219280948873617f,
+  6.3398500028846252f, 6.3575520046180847f, 6.3750394313469254f,
+  6.3923174227787598f, 6.4093909361377026f, 6.4262647547020979f,
+  6.4429434958487288f, 6.4594316186372982f, 6.4757334309663976f,
+  6.4918530963296748f, 6.5077946401986964f, 6.5235619560570131f,
+  6.5391588111080319f, 6.5545888516776376f, 6.5698556083309478f,
+  6.5849625007211561f, 6.5999128421871278f, 6.6147098441152092f,
+  6.6293566200796095f, 6.6438561897747253f, 6.6582114827517955f,
+  6.6724253419714952f, 6.6865005271832185f, 6.7004397181410917f,
+  6.7142455176661224f, 6.7279204545631988f, 6.7414669864011465f,
+  6.7548875021634691f, 6.7681843247769260f, 6.7813597135246599f,
+  6.7944158663501062f, 6.8073549220576037f, 6.8201789624151887f,
+  6.8328900141647422f, 6.8454900509443757f, 6.8579809951275719f,
+  6.8703647195834048f, 6.8826430493618416f, 6.8948177633079437f,
+  6.9068905956085187f, 6.9188632372745955f, 6.9307373375628867f,
+  6.9425145053392399f, 6.9541963103868758f, 6.9657842846620879f,
+  6.9772799234999168f, 6.9886846867721664f, 7.0000000000000000f,
+  7.0112272554232540f, 7.0223678130284544f, 7.0334230015374501f,
+  7.0443941193584534f, 7.0552824355011898f, 7.0660891904577721f,
+  7.0768155970508317f, 7.0874628412503400f, 7.0980320829605272f,
+  7.1085244567781700f, 7.1189410727235076f, 7.1292830169449664f,
+  7.1395513523987937f, 7.1497471195046822f, 7.1598713367783891f,
+  7.1699250014423130f, 7.1799090900149345f, 7.1898245588800176f,
+  7.1996723448363644f, 7.2094533656289492f, 7.2191685204621621f,
+  7.2288186904958804f, 7.2384047393250794f, 7.2479275134435861f,
+  7.2573878426926521f, 7.2667865406949019f, 7.2761244052742384f,
+  7.2854022188622487f, 7.2946207488916270f, 7.3037807481771031f,
+  7.3128829552843557f, 7.3219280948873617f, 7.3309168781146177f,
+  7.3398500028846243f, 7.3487281542310781f, 7.3575520046180847f,
+  7.3663222142458151f, 7.3750394313469254f, 7.3837042924740528f,
+  7.3923174227787607f, 7.4008794362821844f, 7.4093909361377026f,
+  7.4178525148858991f, 7.4262647547020979f, 7.4346282276367255f,
+  7.4429434958487288f, 7.4512111118323299f, 7.4594316186372973f,
+  7.4676055500829976f, 7.4757334309663976f, 7.4838157772642564f,
+  7.4918530963296748f, 7.4998458870832057f, 7.5077946401986964f,
+  7.5156998382840436f, 7.5235619560570131f, 7.5313814605163119f,
+  7.5391588111080319f, 7.5468944598876373f, 7.5545888516776376f,
+  7.5622424242210728f, 7.5698556083309478f, 7.5774288280357487f,
+  7.5849625007211561f, 7.5924570372680806f, 7.5999128421871278f,
+  7.6073303137496113f, 7.6147098441152075f, 7.6220518194563764f,
+  7.6293566200796095f, 7.6366246205436488f, 7.6438561897747244f,
+  7.6510516911789290f, 7.6582114827517955f, 7.6653359171851765f,
+  7.6724253419714952f, 7.6794800995054464f, 7.6865005271832185f,
+  7.6934869574993252f, 7.7004397181410926f, 7.7073591320808825f,
+  7.7142455176661224f, 7.7210991887071856f, 7.7279204545631996f,
+  7.7347096202258392f, 7.7414669864011465f, 7.7481928495894596f,
+  7.7548875021634691f, 7.7615512324444795f, 7.7681843247769260f,
+  7.7747870596011737f, 7.7813597135246608f, 7.7879025593914317f,
+  7.7944158663501062f, 7.8008998999203047f, 7.8073549220576037f,
+  7.8137811912170374f, 7.8201789624151887f, 7.8265484872909159f,
+  7.8328900141647422f, 7.8392037880969445f, 7.8454900509443757f,
+  7.8517490414160571f, 7.8579809951275719f, 7.8641861446542798f,
+  7.8703647195834048f, 7.8765169465650002f, 7.8826430493618425f,
+  7.8887432488982601f, 7.8948177633079446f, 7.9008668079807496f,
+  7.9068905956085187f, 7.9128893362299619f, 7.9188632372745955f,
+  7.9248125036057813f, 7.9307373375628867f, 7.9366379390025719f,
+  7.9425145053392399f, 7.9483672315846778f, 7.9541963103868758f,
+  7.9600019320680806f, 7.9657842846620870f, 7.9715435539507720f,
+  7.9772799234999168f, 7.9829935746943104f, 7.9886846867721664f,
+  7.9943534368588578f
+};
+
+// Faster logarithm for small integers, with the property of log2(0) == 0.
+static inline double FastLog2(int v) {
+  if (v < (int)(sizeof(kLog2Table) / sizeof(kLog2Table[0]))) {
+    return kLog2Table[v];
+  }
+  return log2(v);
+}
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_FAST_LOG_H_
diff --git a/brotli/enc/find_match_length.h b/brotli/enc/find_match_length.h
new file mode 100644
index 0000000..0994ac2
--- /dev/null
+++ b/brotli/enc/find_match_length.h
@@ -0,0 +1,85 @@
+// Copyright 2010 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.
+//
+// Function to find maximal matching prefixes of strings.
+
+#ifndef BROTLI_ENC_FIND_MATCH_LENGTH_H_
+#define BROTLI_ENC_FIND_MATCH_LENGTH_H_
+
+#include <stdint.h>
+
+#include "./port.h"
+
+namespace brotli {
+
+// Separate implementation for x86_64, for speed.
+#if defined(__GNUC__) && defined(ARCH_K8)
+
+static inline int FindMatchLengthWithLimit(const uint8_t* s1,
+                                           const uint8_t* s2,
+                                           size_t limit) {
+  int matched = 0;
+  size_t limit2 = (limit >> 3) + 1;  // + 1 is for pre-decrement in while
+  while (PREDICT_TRUE(--limit2)) {
+    if (PREDICT_FALSE(BROTLI_UNALIGNED_LOAD64(s2) ==
+                      BROTLI_UNALIGNED_LOAD64(s1 + matched))) {
+      s2 += 8;
+      matched += 8;
+    } else {
+      uint64_t x =
+          BROTLI_UNALIGNED_LOAD64(s2) ^ BROTLI_UNALIGNED_LOAD64(s1 + matched);
+      int matching_bits =  __builtin_ctzll(x);
+      matched += matching_bits >> 3;
+      return matched;
+    }
+  }
+  limit = (limit & 7) + 1;  // + 1 is for pre-decrement in while
+  while (--limit) {
+    if (PREDICT_TRUE(s1[matched] == *s2)) {
+      ++s2;
+      ++matched;
+    } else {
+      return matched;
+    }
+  }
+  return matched;
+}
+#else
+static inline int FindMatchLengthWithLimit(const uint8_t* s1,
+                                           const uint8_t* s2,
+                                           size_t limit) {
+  int matched = 0;
+  const uint8_t* s2_limit = s2 + limit;
+  const uint8_t* s2_ptr = s2;
+  // Find out how long the match is. We loop over the data 32 bits at a
+  // time until we find a 32-bit block that doesn't match; then we find
+  // the first non-matching bit and use that to calculate the total
+  // length of the match.
+  while (s2_ptr <= s2_limit - 4 &&
+         BROTLI_UNALIGNED_LOAD32(s2_ptr) ==
+         BROTLI_UNALIGNED_LOAD32(s1 + matched)) {
+    s2_ptr += 4;
+    matched += 4;
+  }
+  while ((s2_ptr < s2_limit) && (s1[matched] == *s2_ptr)) {
+    ++s2_ptr;
+    ++matched;
+  }
+  return matched;
+}
+#endif
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_FIND_MATCH_LENGTH_H_
diff --git a/brotli/enc/hash.h b/brotli/enc/hash.h
new file mode 100644
index 0000000..9cacf7e
--- /dev/null
+++ b/brotli/enc/hash.h
@@ -0,0 +1,354 @@
+// Copyright 2010 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.
+//
+// A (forgetful) hash table to the data seen by the compressor, to
+// help create backward references to previous data.
+
+#ifndef BROTLI_ENC_HASH_H_
+#define BROTLI_ENC_HASH_H_
+
+#include <stddef.h>
+#include <stdint.h>
+#include <string.h>
+#include <sys/types.h>
+#include <algorithm>
+
+#include "./fast_log.h"
+#include "./find_match_length.h"
+#include "./port.h"
+
+namespace brotli {
+
+// kHashMul32 multiplier has these properties:
+// * The multiplier must be odd. Otherwise we may lose the highest bit.
+// * No long streaks of 1s or 0s.
+// * There is no effort to ensure that it is a prime, the oddity is enough
+//   for this use.
+// * The number has been tuned heuristically against compression benchmarks.
+static const uint32_t kHashMul32 = 0x1e35a7bd;
+
+inline uint32_t Hash3Bytes(const uint8_t *data, const int bits) {
+  uint32_t h = (BROTLI_UNALIGNED_LOAD32(data) & 0xffffff) * kHashMul32;
+  // The higher bits contain more mixture from the multiplication,
+  // so we take our results from there.
+  return h >> (32 - bits);
+}
+
+// Usually, we always choose the longest backward reference. This function
+// allows for the exception of that rule.
+//
+// If we choose a backward reference that is further away, it will
+// usually be coded with more bits. We approximate this by assuming
+// log2(distance). If the distance can be expressed in terms of the
+// last four distances, we use some heuristic constants to estimate
+// the bits cost. For the first up to four literals we use the bit
+// cost of the literals from the literal cost model, after that we
+// use the average bit cost of the cost model.
+//
+// This function is used to sometimes discard a longer backward reference
+// when it is not much longer and the bit cost for encoding it is more
+// than the saved literals.
+inline double BackwardReferenceScore(double average_cost,
+                                     double start_cost4,
+                                     double start_cost3,
+                                     double start_cost2,
+                                     int copy_length,
+                                     int backward_reference_offset,
+                                     int last_distance1,
+                                     int last_distance2,
+                                     int last_distance3,
+                                     int last_distance4) {
+  double retval = 0;
+  switch (copy_length) {
+    case 2: retval = start_cost2; break;
+    case 3: retval = start_cost3; break;
+    default: retval = start_cost4 + (copy_length - 4) * average_cost; break;
+  }
+  int diff_last1 = abs(backward_reference_offset - last_distance1);
+  int diff_last2 = abs(backward_reference_offset - last_distance2);
+  if (diff_last1 == 0) {
+    retval += 0.6;
+  } else if (diff_last1 < 4) {
+    retval -= 0.9 + 0.03 * diff_last1;
+  } else if (diff_last2 < 4) {
+    retval -= 0.95 + 0.1 * diff_last2;
+  } else if (backward_reference_offset == last_distance3) {
+    retval -= 1.17;
+  } else if (backward_reference_offset == last_distance4) {
+    retval -= 1.27;
+  } else {
+    retval -= 1.20 * Log2Floor(backward_reference_offset);
+  }
+  return retval;
+}
+
+// A (forgetful) hash table to the data seen by the compressor, to
+// help create backward references to previous data.
+//
+// This is a hash map of fixed size (kBucketSize) to a ring buffer of
+// fixed size (kBlockSize). The ring buffer contains the last kBlockSize
+// index positions of the given hash key in the compressed data.
+template <int kBucketBits, int kBlockBits>
+class HashLongestMatch {
+ public:
+  HashLongestMatch()
+      : literal_cost_(NULL),
+        last_distance1_(4),
+        last_distance2_(11),
+        last_distance3_(15),
+        last_distance4_(16),
+        insert_length_(0),
+        average_cost_(5.4) {
+    Reset();
+  }
+  void Reset() {
+    std::fill(&num_[0], &num_[sizeof(num_) / sizeof(num_[0])], 0);
+  }
+  void SetLiteralCost(float *cost) {
+    literal_cost_ = cost;
+  }
+  double literal_cost(int i) const { return literal_cost_[i]; }
+
+  // Look at 3 bytes at data.
+  // Compute a hash from these, and store the value of ix at that position.
+  inline void Store(const uint8_t *data, const int ix) {
+    const uint32_t key = Hash3Bytes(data, kBucketBits);
+    const int minor_ix = num_[key] & kBlockMask;
+    buckets_[key][minor_ix] = ix;
+    ++num_[key];
+  }
+
+  // Store hashes for a range of data.
+  void StoreHashes(const uint8_t *data, size_t len, int startix, int mask) {
+    for (int p = 0; p < len; ++p) {
+      Store(&data[p & mask], startix + p);
+    }
+  }
+
+  // Find a longest backward match of &data[cur_ix] up to the length of
+  // max_length.
+  //
+  // Does not look for matches longer than max_length.
+  // Does not look for matches further away than max_backward.
+  // Writes the best found match length into best_len_out.
+  // Writes the index (&data[index]) offset from the start of the best match
+  // into best_distance_out.
+  // Write the score of the best match into best_score_out.
+  bool FindLongestMatch(const uint8_t * __restrict data,
+                        const uint32_t cur_ix,
+                        uint32_t max_length,
+                        const uint32_t max_backward,
+                        size_t * __restrict best_len_out,
+                        size_t * __restrict best_distance_out,
+                        double * __restrict best_score_out) {
+    const double start_cost4 = literal_cost_ == NULL ? 20 :
+        literal_cost_[cur_ix] +
+        literal_cost_[cur_ix + 1] +
+        literal_cost_[cur_ix + 2] +
+        literal_cost_[cur_ix + 3];
+
+    const double start_cost3 = literal_cost_ == NULL ? 15 :
+        literal_cost_[cur_ix] +
+        literal_cost_[cur_ix + 1] +
+        literal_cost_[cur_ix + 2] + 0.3;
+    double start_cost2 = literal_cost_ == NULL ? 10 :
+        literal_cost_[cur_ix] +
+        literal_cost_[cur_ix + 1] + 1.2;
+    bool match_found = false;
+    // Don't accept a short copy from far away.
+    double best_score = 8.25;
+    if (insert_length_ < 4) {
+      double cost_diff[4] = { 0.20, 0.09, 0.05, 0.03 };
+      best_score += cost_diff[insert_length_];
+    }
+    size_t best_len = *best_len_out;
+    *best_len_out = 0;
+    size_t best_ix = 1;
+    // Try last distance first.
+    for (int i = 0; i < 16; ++i) {
+      int prev_ix = cur_ix;
+      switch(i) {
+        case 0: prev_ix -= last_distance1_; break;
+        case 1: prev_ix -= last_distance2_; break;
+        case 2: prev_ix -= last_distance3_; break;
+        case 3: prev_ix -= last_distance4_; break;
+
+        case 4: prev_ix -= last_distance1_ - 1; break;
+        case 5: prev_ix -= last_distance1_ + 1; break;
+        case 6: prev_ix -= last_distance1_ - 2; break;
+        case 7: prev_ix -= last_distance1_ + 2; break;
+        case 8: prev_ix -= last_distance1_ - 3; break;
+        case 9: prev_ix -= last_distance1_ + 3; break;
+
+        case 10: prev_ix -= last_distance2_ - 1; break;
+        case 11: prev_ix -= last_distance2_ + 1; break;
+        case 12: prev_ix -= last_distance2_ - 2; break;
+        case 13: prev_ix -= last_distance2_ + 2; break;
+        case 14: prev_ix -= last_distance2_ - 3; break;
+        case 15: prev_ix -= last_distance2_ + 3; break;
+      }
+      if (prev_ix >= cur_ix) {
+        continue;
+      }
+      const size_t backward = cur_ix - prev_ix;
+      if (PREDICT_FALSE(backward > max_backward)) {
+        continue;
+      }
+      if (data[cur_ix + best_len] != data[prev_ix + best_len]) {
+        continue;
+      }
+      const size_t len =
+          FindMatchLengthWithLimit(&data[prev_ix], &data[cur_ix], max_length);
+      if (len >= 3 || (len == 2 && i < 2)) {
+        // Comparing for >= 2 does not change the semantics, but just saves for
+        // a few unnecessary binary logarithms in backward reference score,
+        // since we are not interested in such short matches.
+        const double score = BackwardReferenceScore(average_cost_,
+                                                    start_cost4,
+                                                    start_cost3,
+                                                    start_cost2,
+                                                    len, backward,
+                                                    last_distance1_,
+                                                    last_distance2_,
+                                                    last_distance3_,
+                                                    last_distance4_);
+        if (best_score < score) {
+          best_score = score;
+          best_len = len;
+          best_ix = backward;
+          *best_len_out = best_len;
+          *best_distance_out = best_ix;
+          *best_score_out = best_score;
+          match_found = true;
+        }
+      }
+    }
+    const uint32_t key = Hash3Bytes(&data[cur_ix], kBucketBits);
+    const uint32_t * __restrict const bucket = &buckets_[key][0];
+    const int down = (num_[key] > kBlockSize) ? (num_[key] - kBlockSize) : 0;
+    int stop = int(cur_ix) - 64;
+    if (stop < 0) { stop = 0; }
+
+    start_cost2 -= 1.0;
+    for (int i = cur_ix - 1; i > stop; --i) {
+      size_t prev_ix = i;
+      const size_t backward = cur_ix - prev_ix;
+      if (PREDICT_FALSE(backward > max_backward)) {
+        break;
+      }
+      if (data[cur_ix] != data[prev_ix] ||
+          data[cur_ix + 1] != data[prev_ix + 1]) {
+        continue;
+      }
+      int len = 2;
+      const double score = start_cost2 - 1.70 * Log2Floor(backward);
+
+      if (best_score < score) {
+        best_score = score;
+        best_len = len;
+        best_ix = backward;
+        *best_len_out = best_len;
+        *best_distance_out = best_ix;
+        match_found = true;
+      }
+    }
+    for (int i = num_[key] - 1; i >= down; --i) {
+      size_t prev_ix = bucket[i & kBlockMask];
+      const size_t backward = cur_ix - prev_ix;
+      if (PREDICT_FALSE(backward > max_backward)) {
+        break;
+      }
+      if (data[cur_ix + best_len] != data[prev_ix + best_len]) {
+        continue;
+      }
+      const size_t len =
+          FindMatchLengthWithLimit(&data[prev_ix], &data[cur_ix], max_length);
+      if (len >= 3) {
+        // Comparing for >= 3 does not change the semantics, but just saves for
+        // a few unnecessary binary logarithms in backward reference score,
+        // since we are not interested in such short matches.
+        const double score = BackwardReferenceScore(average_cost_,
+                                                    start_cost4,
+                                                    start_cost3,
+                                                    start_cost2,
+                                                    len, backward,
+                                                    last_distance1_,
+                                                    last_distance2_,
+                                                    last_distance3_,
+                                                    last_distance4_);
+        if (best_score < score) {
+          best_score = score;
+          best_len = len;
+          best_ix = backward;
+          *best_len_out = best_len;
+          *best_distance_out = best_ix;
+          *best_score_out = best_score;
+          match_found = true;
+        }
+      }
+    }
+    return match_found;
+  }
+
+  void set_last_distance(int v) {
+    if (last_distance1_ != v) {
+      last_distance4_ = last_distance3_;
+      last_distance3_ = last_distance2_;
+      last_distance2_ = last_distance1_;
+      last_distance1_ = v;
+    }
+  }
+
+  int last_distance() const { return last_distance1_; }
+
+  void set_insert_length(int v) { insert_length_ = v; }
+
+  void set_average_cost(double v) { average_cost_ = v; }
+
+ private:
+  // Number of hash buckets.
+  static const uint32_t kBucketSize = 1 << kBucketBits;
+
+  // Only kBlockSize newest backward references are kept,
+  // and the older are forgotten.
+  static const uint32_t kBlockSize = 1 << kBlockBits;
+
+  // Mask for accessing entries in a block (in a ringbuffer manner).
+  static const uint32_t kBlockMask = (1 << kBlockBits) - 1;
+
+  // Number of entries in a particular bucket.
+  uint16_t num_[kBucketSize];
+
+  // Buckets containing kBlockSize of backward references.
+  uint32_t buckets_[kBucketSize][kBlockSize];
+
+  // Model of how much the ith literal costs to encode using
+  // the entropy model.
+  float *literal_cost_;
+
+  int last_distance1_;
+  int last_distance2_;
+  int last_distance3_;
+  int last_distance4_;
+
+  // Cost adjustment for how many literals we are planning to insert
+  // anyway.
+  int insert_length_;
+
+  double average_cost_;
+};
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_HASH_H_
diff --git a/brotli/enc/histogram.cc b/brotli/enc/histogram.cc
new file mode 100644
index 0000000..32d7730
--- /dev/null
+++ b/brotli/enc/histogram.cc
@@ -0,0 +1,72 @@
+// 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.
+//
+// Build per-context histograms of literals, commands and distance codes.
+
+#include "./histogram.h"
+
+#include <stdint.h>
+#include <cmath>
+
+#include "./block_splitter.h"
+#include "./command.h"
+#include "./context.h"
+#include "./prefix.h"
+
+namespace brotli {
+
+void BuildHistograms(
+    const std::vector<Command>& cmds,
+    const BlockSplit& literal_split,
+    const BlockSplit& insert_and_copy_split,
+    const BlockSplit& dist_split,
+    const uint8_t* input_buffer,
+    size_t pos,
+    int context_mode,
+    int distance_context_mode,
+    std::vector<HistogramLiteral>* literal_histograms,
+    std::vector<HistogramCommand>* insert_and_copy_histograms,
+    std::vector<HistogramDistance>* copy_dist_histograms) {
+  BlockSplitIterator literal_it(literal_split);
+  BlockSplitIterator insert_and_copy_it(insert_and_copy_split);
+  BlockSplitIterator dist_it(dist_split);
+  for (int i = 0; i < cmds.size(); ++i) {
+    const Command &cmd = cmds[i];
+    insert_and_copy_it.Next();
+    (*insert_and_copy_histograms)[insert_and_copy_it.type_].Add(
+        cmd.command_prefix_);
+    for (int j = 0; j < cmd.insert_length_; ++j) {
+      literal_it.Next();
+      uint8_t prev_byte = pos > 0 ? input_buffer[pos - 1] : 0;
+      uint8_t prev_byte2 = pos > 1 ? input_buffer[pos - 2] : 0;
+      uint8_t prev_byte3 = pos > 2 ? input_buffer[pos - 3] : 0;
+      int context = (literal_it.type_ * NumContexts(context_mode) +
+                     Context(prev_byte, prev_byte2, prev_byte3, context_mode));
+      (*literal_histograms)[context].Add(input_buffer[pos]);
+      ++pos;
+    }
+    pos += cmd.copy_length_;
+    if (cmd.copy_length_ > 0 && cmd.distance_prefix_ != 0xffff) {
+      dist_it.Next();
+      int context = dist_it.type_;
+      if (distance_context_mode > 0) {
+        context <<= 2;
+        context += (cmd.copy_length_ > 4) ? 3 : cmd.copy_length_ - 2;
+      }
+      (*copy_dist_histograms)[context].Add(cmd.distance_prefix_);
+    }
+  }
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/histogram.h b/brotli/enc/histogram.h
new file mode 100644
index 0000000..69f8b9a
--- /dev/null
+++ b/brotli/enc/histogram.h
@@ -0,0 +1,97 @@
+// 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.
+//
+// Models the histograms of literals, commands and distance codes.
+
+#ifndef BROTLI_ENC_HISTOGRAM_H_
+#define BROTLI_ENC_HISTOGRAM_H_
+
+#include <stdint.h>
+#include <string.h>
+#include <vector>
+#include <utility>
+#include "./command.h"
+#include "./fast_log.h"
+#include "./prefix.h"
+
+namespace brotli {
+
+class BlockSplit;
+
+// A simple container for histograms of data in blocks.
+template<int kDataSize>
+struct Histogram {
+  Histogram() {
+    Clear();
+  }
+  void Clear() {
+    memset(data_, 0, sizeof(data_));
+    total_count_ = 0;
+  }
+  void Add(int val) {
+    ++data_[val];
+    ++total_count_;
+  }
+  void Remove(int val) {
+    --data_[val];
+    --total_count_;
+  }
+  template<typename DataType>
+  void Add(const DataType *p, size_t n) {
+    total_count_ += n;
+    n += 1;
+    while(--n) ++data_[*p++];
+  }
+  void AddHistogram(const Histogram& v) {
+    total_count_ += v.total_count_;
+    for (int i = 0; i < kDataSize; ++i) {
+      data_[i] += v.data_[i];
+    }
+  }
+  double EntropyBitCost() const {
+    double retval = total_count_ * FastLog2(total_count_);
+    for (int i = 0; i < kDataSize; ++i) {
+      retval -= data_[i] * FastLog2(data_[i]);
+    }
+    return retval;
+  }
+
+  int data_[kDataSize];
+  int total_count_;
+  double bit_cost_;
+};
+
+// Literal histogram.
+typedef Histogram<256> HistogramLiteral;
+// Prefix histograms.
+typedef Histogram<kNumCommandPrefixes> HistogramCommand;
+typedef Histogram<kNumDistancePrefixes> HistogramDistance;
+typedef Histogram<kNumBlockLenPrefixes> HistogramBlockLength;
+
+void BuildHistograms(
+    const std::vector<Command>& cmds,
+    const BlockSplit& literal_split,
+    const BlockSplit& insert_and_copy_split,
+    const BlockSplit& dist_split,
+    const uint8_t* input_buffer,
+    size_t pos,
+    int context_mode,
+    int distance_context_mode,
+    std::vector<HistogramLiteral>* literal_histograms,
+    std::vector<HistogramCommand>* insert_and_copy_histograms,
+    std::vector<HistogramDistance>* copy_dist_histograms);
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_HISTOGRAM_H_
diff --git a/brotli/enc/literal_cost.cc b/brotli/enc/literal_cost.cc
new file mode 100644
index 0000000..0dac1a6
--- /dev/null
+++ b/brotli/enc/literal_cost.cc
@@ -0,0 +1,60 @@
+// 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.
+//
+// Literal cost model to allow backward reference replacement to be efficient.
+
+#include "./literal_cost.h"
+
+#include <math.h>
+#include <stdint.h>
+#include <algorithm>
+
+namespace brotli {
+
+void EstimateBitCostsForLiterals(size_t len, const uint8_t *data, float *cost) {
+  int histogram[256] = { 0 };
+  int window_half = 2000;
+  int in_window = std::min(static_cast<size_t>(window_half), len);
+
+  // Bootstrap histogram.
+  for (int i = 0; i < in_window; ++i) {
+    ++histogram[data[i]];
+  }
+
+  // Compute bit costs with sliding window.
+  for (int i = 0; i < len; ++i) {
+    if (i - window_half >= 0) {
+      // Remove a byte in the past.
+      --histogram[data[i - window_half]];
+      --in_window;
+    }
+    if (i + window_half < len) {
+      // Add a byte in the future.
+      ++histogram[data[i + window_half]];
+      ++in_window;
+    }
+    int histo = histogram[data[i]];
+    if (histo == 0) {
+      histo = 1;
+    }
+    cost[i] = log2(static_cast<double>(in_window) / histo);
+    cost[i] += 0.03;
+    if (cost[i] < 1.0) {
+      cost[i] *= 0.5;
+      cost[i] += 0.5;
+    }
+  }
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/literal_cost.h b/brotli/enc/literal_cost.h
new file mode 100644
index 0000000..0dbbc3f
--- /dev/null
+++ b/brotli/enc/literal_cost.h
@@ -0,0 +1,31 @@
+// 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.
+//
+// Literal cost model to allow backward reference replacement to be efficient.
+
+#ifndef BROTLI_ENC_LITERAL_COST_H_
+#define BROTLI_ENC_LITERAL_COST_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+namespace brotli {
+
+// Input: length of data, and the bytes.
+// Output: estimate of how many bits the literal will take entropy coded.
+void EstimateBitCostsForLiterals(size_t len, const uint8_t *data, float *cost);
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_LITERAL_COST_H_
diff --git a/brotli/enc/port.h b/brotli/enc/port.h
new file mode 100644
index 0000000..36a365e
--- /dev/null
+++ b/brotli/enc/port.h
@@ -0,0 +1,138 @@
+// 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.
+//
+// Macros for endianness, branch prediction and unaligned loads and stores.
+
+#ifndef BROTLI_ENC_PORT_H_
+#define BROTLI_ENC_PORT_H_
+
+#if defined OS_LINUX || defined OS_CYGWIN
+#include <endian.h>
+#elif defined OS_FREEBSD
+#include <machine/endian.h>
+#elif defined OS_MACOSX
+#include <machine/endian.h>
+/* Let's try and follow the Linux convention */
+#define __BYTE_ORDER  BYTE_ORDER
+#define __LITTLE_ENDIAN LITTLE_ENDIAN
+#define __BIG_ENDIAN BIG_ENDIAN
+#endif
+
+// define the macros IS_LITTLE_ENDIAN or IS_BIG_ENDIAN
+// using the above endian definitions from endian.h if
+// endian.h was included
+#ifdef __BYTE_ORDER
+#if __BYTE_ORDER == __LITTLE_ENDIAN
+#define IS_LITTLE_ENDIAN
+#endif
+
+#if __BYTE_ORDER == __BIG_ENDIAN
+#define IS_BIG_ENDIAN
+#endif
+
+#else
+
+#if defined(__LITTLE_ENDIAN__)
+#define IS_LITTLE_ENDIAN
+#elif defined(__BIG_ENDIAN__)
+#define IS_BIG_ENDIAN
+#endif
+#endif  // __BYTE_ORDER
+
+#if defined(COMPILER_GCC3)
+#define PREDICT_FALSE(x) (__builtin_expect(x, 0))
+#define PREDICT_TRUE(x) (__builtin_expect(!!(x), 1))
+#else
+#define PREDICT_FALSE(x) x
+#define PREDICT_TRUE(x) x
+#endif
+
+// Portable handling of unaligned loads, stores, and copies.
+// On some platforms, like ARM, the copy functions can be more efficient
+// then a load and a store.
+
+#if defined(ARCH_PIII) || defined(ARCH_ATHLON) || \
+  defined(ARCH_K8) || defined(_ARCH_PPC)
+
+// x86 and x86-64 can perform unaligned loads/stores directly;
+// modern PowerPC hardware can also do unaligned integer loads and stores;
+// but note: the FPU still sends unaligned loads and stores to a trap handler!
+
+#define BROTLI_UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32_t *>(_p))
+#define BROTLI_UNALIGNED_LOAD64(_p) (*reinterpret_cast<const uint64_t *>(_p))
+
+#define BROTLI_UNALIGNED_STORE32(_p, _val) \
+  (*reinterpret_cast<uint32_t *>(_p) = (_val))
+#define BROTLI_UNALIGNED_STORE64(_p, _val) \
+  (*reinterpret_cast<uint64_t *>(_p) = (_val))
+
+#elif defined(__arm__) && \
+  !defined(__ARM_ARCH_5__) && \
+  !defined(__ARM_ARCH_5T__) && \
+  !defined(__ARM_ARCH_5TE__) && \
+  !defined(__ARM_ARCH_5TEJ__) && \
+  !defined(__ARM_ARCH_6__) && \
+  !defined(__ARM_ARCH_6J__) && \
+  !defined(__ARM_ARCH_6K__) && \
+  !defined(__ARM_ARCH_6Z__) && \
+  !defined(__ARM_ARCH_6ZK__) && \
+  !defined(__ARM_ARCH_6T2__)
+
+// ARMv7 and newer support native unaligned accesses, but only of 16-bit
+// and 32-bit values (not 64-bit); older versions either raise a fatal signal,
+// do an unaligned read and rotate the words around a bit, or do the reads very
+// slowly (trip through kernel mode).
+
+#define BROTLI_UNALIGNED_LOAD32(_p) (*reinterpret_cast<const uint32_t *>(_p))
+#define BROTLI_UNALIGNED_STORE32(_p, _val) \
+  (*reinterpret_cast<uint32_t *>(_p) = (_val))
+
+inline uint64_t BROTLI_UNALIGNED_LOAD64(const void *p) {
+  uint64_t t;
+  memcpy(&t, p, sizeof t);
+  return t;
+}
+
+inline void BROTLI_UNALIGNED_STORE64(void *p, uint64_t v) {
+  memcpy(p, &v, sizeof v);
+}
+
+#else
+
+// These functions are provided for architectures that don't support
+// unaligned loads and stores.
+
+inline uint32_t BROTLI_UNALIGNED_LOAD32(const void *p) {
+  uint32_t t;
+  memcpy(&t, p, sizeof t);
+  return t;
+}
+
+inline uint64_t BROTLI_UNALIGNED_LOAD64(const void *p) {
+  uint64_t t;
+  memcpy(&t, p, sizeof t);
+  return t;
+}
+
+inline void BROTLI_UNALIGNED_STORE32(void *p, uint32_t v) {
+  memcpy(p, &v, sizeof v);
+}
+
+inline void BROTLI_UNALIGNED_STORE64(void *p, uint64_t v) {
+  memcpy(p, &v, sizeof v);
+}
+
+#endif
+
+#endif  // BROTLI_ENC_PORT_H_
diff --git a/brotli/enc/prefix.cc b/brotli/enc/prefix.cc
new file mode 100644
index 0000000..3e43501
--- /dev/null
+++ b/brotli/enc/prefix.cc
@@ -0,0 +1,166 @@
+// 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.
+//
+// Functions for encoding of integers into prefix codes the amount of extra
+// bits, and the actual values of the extra bits.
+
+#include "./prefix.h"
+
+#include "./fast_log.h"
+
+namespace brotli {
+
+// Represents the range of values belonging to a prefix code:
+// [offset, offset + 2^nbits)
+struct PrefixCodeRange {
+  int offset;
+  int nbits;
+};
+
+static const PrefixCodeRange kBlockLengthPrefixCode[kNumBlockLenPrefixes] = {
+  {   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 PrefixCodeRange kInsertLengthPrefixCode[kNumInsertLenPrefixes] = {
+  {   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 PrefixCodeRange kCopyLengthPrefixCode[kNumCopyLenPrefixes] = {
+  {  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,
+};
+
+int InsertLengthPrefix(int length) {
+  for (int i = 0; i < kNumInsertLenPrefixes; ++i) {
+    const PrefixCodeRange& range = kInsertLengthPrefixCode[i];
+    if (length >= range.offset && length < range.offset + (1 << range.nbits)) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+int CopyLengthPrefix(int length) {
+  for (int i = 0; i < kNumCopyLenPrefixes; ++i) {
+    const PrefixCodeRange& range = kCopyLengthPrefixCode[i];
+    if (length >= range.offset && length < range.offset + (1 << range.nbits)) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+int CommandPrefix(int insert_length, int copy_length) {
+  if (copy_length == 0) {
+    copy_length = 3;
+  }
+  int insert_prefix = InsertLengthPrefix(insert_length);
+  int copy_prefix = CopyLengthPrefix(copy_length);
+  int range_idx = 3 * (insert_prefix >> 3) + (copy_prefix >> 3);
+  return ((kInsertAndCopyRangeLut[range_idx] << 6) +
+          ((insert_prefix & 7) << 3) + (copy_prefix & 7));
+}
+
+int InsertLengthExtraBits(int code) {
+  int insert_code = (kInsertRangeLut[code >> 6] << 3) + ((code >> 3) & 7);
+  return kInsertLengthPrefixCode[insert_code].nbits;
+}
+
+int InsertLengthOffset(int code) {
+  int insert_code = (kInsertRangeLut[code >> 6] << 3) + ((code >> 3) & 7);
+  return kInsertLengthPrefixCode[insert_code].offset;
+}
+
+int CopyLengthExtraBits(int code) {
+  int copy_code = (kCopyRangeLut[code >> 6] << 3) + (code & 7);
+  return kCopyLengthPrefixCode[copy_code].nbits;
+}
+
+int CopyLengthOffset(int code) {
+  int copy_code = (kCopyRangeLut[code >> 6] << 3) + (code & 7);
+  return kCopyLengthPrefixCode[copy_code].offset;
+}
+
+void PrefixEncodeCopyDistance(int distance_code,
+                              int num_direct_codes,
+                              int postfix_bits,
+                              uint16_t* code,
+                              int* nbits,
+                              uint32_t* extra_bits) {
+  distance_code -= 1;
+  if (distance_code < kNumDistanceShortCodes + num_direct_codes) {
+    *code = distance_code;
+    *nbits = 0;
+    *extra_bits = 0;
+    return;
+  }
+  distance_code -= kNumDistanceShortCodes + num_direct_codes;
+  distance_code += (1 << (postfix_bits + 2));
+  int bucket = Log2Floor(distance_code) - 1;
+  int postfix_mask = (1 << postfix_bits) - 1;
+  int postfix = distance_code & postfix_mask;
+  int prefix = (distance_code >> bucket) & 1;
+  int offset = (2 + prefix) << bucket;
+  *nbits = bucket - postfix_bits;
+  *code = kNumDistanceShortCodes + num_direct_codes +
+      ((2 * (*nbits - 1) + prefix) << postfix_bits) + postfix;
+  *extra_bits = (distance_code - offset) >> postfix_bits;
+}
+
+int BlockLengthPrefix(int length) {
+  for (int i = 0; i < kNumBlockLenPrefixes; ++i) {
+    const PrefixCodeRange& range = kBlockLengthPrefixCode[i];
+    if (length >= range.offset && length < range.offset + (1 << range.nbits)) {
+      return i;
+    }
+  }
+  return -1;
+}
+
+int BlockLengthExtraBits(int length_code) {
+  return kBlockLengthPrefixCode[length_code].nbits;
+}
+
+int BlockLengthOffset(int length_code) {
+  return kBlockLengthPrefixCode[length_code].offset;
+}
+
+}  // namespace brotli
diff --git a/brotli/enc/prefix.h b/brotli/enc/prefix.h
new file mode 100644
index 0000000..47974f8
--- /dev/null
+++ b/brotli/enc/prefix.h
@@ -0,0 +1,51 @@
+// 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.
+//
+// Functions for encoding of integers into prefix codes the amount of extra
+// bits, and the actual values of the extra bits.
+
+#ifndef BROTLI_ENC_PREFIX_H_
+#define BROTLI_ENC_PREFIX_H_
+
+#include <stdint.h>
+
+namespace brotli {
+
+static const int kNumInsertLenPrefixes = 24;
+static const int kNumCopyLenPrefixes = 24;
+static const int kNumCommandPrefixes = 704;
+static const int kNumBlockLenPrefixes = 26;
+static const int kNumDistanceShortCodes = 16;
+static const int kNumDistancePrefixes = 520;
+
+int CommandPrefix(int insert_length, int copy_length);
+int InsertLengthExtraBits(int prefix);
+int InsertLengthOffset(int prefix);
+int CopyLengthExtraBits(int prefix);
+int CopyLengthOffset(int prefix);
+
+void PrefixEncodeCopyDistance(int distance_code,
+                              int num_direct_codes,
+                              int shift_bits,
+                              uint16_t* prefix,
+                              int* nbits,
+                              uint32_t* extra_bits);
+
+int BlockLengthPrefix(int length);
+int BlockLengthExtraBits(int prefix);
+int BlockLengthOffset(int prefix);
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_PREFIX_H_
diff --git a/brotli/enc/write_bits.h b/brotli/enc/write_bits.h
new file mode 100644
index 0000000..ce888e6
--- /dev/null
+++ b/brotli/enc/write_bits.h
@@ -0,0 +1,91 @@
+// Copyright 2010 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.
+//
+// Write bits into a byte array.
+
+#ifndef BROTLI_ENC_WRITE_BITS_H_
+#define BROTLI_ENC_WRITE_BITS_H_
+
+#include <assert.h>
+#include <endian.h>
+#include <stdint.h>
+#include <stdio.h>
+
+#include "./port.h"
+
+namespace brotli {
+
+//#define BIT_WRITER_DEBUG
+
+// This function writes bits into bytes in increasing addresses, and within
+// a byte least-significant-bit first.
+//
+// The function can write up to 56 bits in one go with WriteBits
+// Example: let's assume that 3 bits (Rs below) have been written already:
+//
+// BYTE-0     BYTE+1       BYTE+2
+//
+// 0000 0RRR    0000 0000    0000 0000
+//
+// Now, we could write 5 or less bits in MSB by just sifting by 3
+// and OR'ing to BYTE-0.
+//
+// For n bits, we take the last 5 bits, OR that with high bits in BYTE-0,
+// and locate the rest in BYTE+1, BYTE+2, etc.
+inline void WriteBits(int n_bits,
+                      uint64_t bits,
+                      int * __restrict pos,
+                      uint8_t * __restrict array) {
+#ifdef BIT_WRITER_DEBUG
+  printf("WriteBits  %2d  0x%016llx  %10d\n", n_bits, bits, *pos);
+#endif
+#ifdef IS_LITTLE_ENDIAN
+  // This branch of the code can write up to 56 bits at a time,
+  // 7 bits are lost by being perhaps already in *p and at least
+  // 1 bit is needed to initialize the bit-stream ahead (i.e. if 7
+  // bits are in *p and we write 57 bits, then the next write will
+  // access a byte that was never initialized).
+  uint8_t *p = &array[*pos >> 3];
+  uint64_t v = *p;
+  v |= bits << (*pos & 7);
+  BROTLI_UNALIGNED_STORE64(p, v);  // Set some bits.
+  *pos += n_bits;
+#else
+  // implicit & 0xff is assumed for uint8_t arithmetics
+  uint8_t *array_pos = &array[*pos >> 3];
+  const int bits_reserved_in_first_byte = (*pos & 7);
+  bits <<= bits_reserved_in_first_byte;
+  *array_pos++ |= bits;
+  for (int bits_left_to_write = n_bits - 8 + bits_reserved_in_first_byte;
+       bits_left_to_write >= 1;
+       bits_left_to_write -= 8) {
+    bits >>= 8;
+    *array_pos++ = bits;
+  }
+  *array_pos = 0;
+  *pos += n_bits;
+#endif
+}
+
+inline void WriteBitsPrepareStorage(int pos, uint8_t *array) {
+#ifdef BIT_WRITER_DEBUG
+  printf("WriteBitsPrepareStorage            %10d\n", pos);
+#endif
+  assert((pos & 7) == 0);
+  array[pos >> 3] = 0;
+}
+
+}  // namespace brotli
+
+#endif  // BROTLI_ENC_WRITE_BITS_H_