Update brotli to v1.0.0-snapshot.

third_party/brotli/enc/histogram.c

Index: third_party/brotli/enc/histogram.c
diff --git a/third_party/brotli/enc/histogram.c b/third_party/brotli/enc/histogram.c
new file mode 100644
index 0000000000000000000000000000000000000000..a8f0413024e4601feeb32303f4a1e838e884a66c
--- /dev/null
+++ b/third_party/brotli/enc/histogram.c
@@ -0,0 +1,95 @@
+/* Copyright 2013 Google Inc. All Rights Reserved.
+
+   Distributed under MIT license.
+   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
+*/
+
+/* Build per-context histograms of literals, commands and distance codes. */
+
+#include "./histogram.h"
+
+#include "./block_splitter.h"
+#include "./command.h"
+#include "./context.h"
+
+#if defined(__cplusplus) || defined(c_plusplus)
+extern "C" {
+#endif
+
+typedef struct BlockSplitIterator {
+  const BlockSplit* split_;  /* Not owned. */
+  size_t idx_;
+  size_t type_;
+  size_t length_;
+} BlockSplitIterator;
+
+static void InitBlockSplitIterator(BlockSplitIterator* self,
+    const BlockSplit* split) {
+  self->split_ = split;
+  self->idx_ = 0;
+  self->type_ = 0;
+  self->length_ = split->lengths ? split->lengths[0] : 0;
+}
+
+static void BlockSplitIteratorNext(BlockSplitIterator* self) {
+  if (self->length_ == 0) {
+    ++self->idx_;
+    self->type_ = self->split_->types[self->idx_];
+    self->length_ = self->split_->lengths[self->idx_];
+  }
+  --self->length_;
+}
+
+void BrotliBuildHistogramsWithContext(
+    const Command* cmds, const size_t num_commands,
+    const BlockSplit* literal_split, const BlockSplit* insert_and_copy_split,
+    const BlockSplit* dist_split, const uint8_t* ringbuffer, size_t start_pos,
+    size_t mask, uint8_t prev_byte, uint8_t prev_byte2,
+    const ContextType* context_modes, HistogramLiteral* literal_histograms,
+    HistogramCommand* insert_and_copy_histograms,
+    HistogramDistance* copy_dist_histograms) {
+  size_t pos = start_pos;
+  BlockSplitIterator literal_it;
+  BlockSplitIterator insert_and_copy_it;
+  BlockSplitIterator dist_it;
+  size_t i;
+
+  InitBlockSplitIterator(&literal_it, literal_split);
+  InitBlockSplitIterator(&insert_and_copy_it, insert_and_copy_split);
+  InitBlockSplitIterator(&dist_it, dist_split);
+  for (i = 0; i < num_commands; ++i) {
+    const Command* cmd = &cmds[i];
+    size_t j;
+    BlockSplitIteratorNext(&insert_and_copy_it);
+    HistogramAddCommand(&insert_and_copy_histograms[insert_and_copy_it.type_],
+        cmd->cmd_prefix_);
+    for (j = cmd->insert_len_; j != 0; --j) {
+      size_t context;
+      BlockSplitIteratorNext(&literal_it);
+      context = (literal_it.type_ << BROTLI_LITERAL_CONTEXT_BITS) +
+          Context(prev_byte, prev_byte2, context_modes[literal_it.type_]);
+      HistogramAddLiteral(&literal_histograms[context],
+          ringbuffer[pos & mask]);
+      prev_byte2 = prev_byte;
+      prev_byte = ringbuffer[pos & mask];
+      ++pos;
+    }
+    pos += CommandCopyLen(cmd);
+    if (CommandCopyLen(cmd)) {
+      prev_byte2 = ringbuffer[(pos - 2) & mask];
+      prev_byte = ringbuffer[(pos - 1) & mask];
+      if (cmd->cmd_prefix_ >= 128) {
+        size_t context;
+        BlockSplitIteratorNext(&dist_it);
+        context = (dist_it.type_ << BROTLI_DISTANCE_CONTEXT_BITS) +
+            CommandDistanceContext(cmd);
+        HistogramAddDistance(&copy_dist_histograms[context],
+            cmd->dist_prefix_);
+      }
+    }
+  }
+}
+
+#if defined(__cplusplus) || defined(c_plusplus)
+}  /* extern "C" */
+#endif