Update brotli to v1.0.0-snapshot.

third_party/brotli/enc/cluster.c

 /* Copyright 2013 Google Inc. All Rights Reserved.
 
    Distributed under MIT license.
    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
 */
 
-/* Bit reading helpers */
+/* Functions for clustering similar histograms together. */
 
-#include "./bit_reader.h"
+#include "./cluster.h"
 
+#include <brotli/types.h>
+#include "./bit_cost.h"  /* BrotliPopulationCost */
+#include "./fast_log.h"
+#include "./histogram.h"
+#include "./memory.h"
 #include "./port.h"
-#include "./types.h"
 
 #if defined(__cplusplus) || defined(c_plusplus)
 extern "C" {
 #endif
 
-void BrotliInitBitReader(BrotliBitReader* const br) {
-  br->val_ = 0;
-  br->bit_pos_ = sizeof(br->val_) << 3;
+static BROTLI_INLINE BROTLI_BOOL HistogramPairIsLess(
+    const HistogramPair* p1, const HistogramPair* p2) {
+  if (p1->cost_diff != p2->cost_diff) {
+    return TO_BROTLI_BOOL(p1->cost_diff > p2->cost_diff);
+  }
+  return TO_BROTLI_BOOL((p1->idx2 - p1->idx1) > (p2->idx2 - p2->idx1));
 }
 
-int BrotliWarmupBitReader(BrotliBitReader* const br) {
-  size_t aligned_read_mask = (sizeof(br->val_) >> 1) - 1;
-  /* Fixing alignment after unaligned BrotliFillWindow would result accumulator
-     overflow. If unalignment is caused by BrotliSafeReadBits, then there is
-     enough space in accumulator to fix aligment. */
-  if (!BROTLI_ALIGNED_READ) {
-    aligned_read_mask = 0;
-  }
-  if (BrotliGetAvailableBits(br) == 0) {
-    if (!BrotliPullByte(br)) {
-      return 0;
-    }
-  }
+/* Returns entropy reduction of the context map when we combine two clusters. */
+static BROTLI_INLINE double ClusterCostDiff(size_t size_a, size_t size_b) {
+  size_t size_c = size_a + size_b;
+  return (double)size_a * FastLog2(size_a) +
+    (double)size_b * FastLog2(size_b) -
+    (double)size_c * FastLog2(size_c);
+}
 
-  while ((((size_t)br->next_in) & aligned_read_mask) != 0) {
-    if (!BrotliPullByte(br)) {
-      /* If we consumed all the input, we don't care about the alignment. */
-      return 1;
-    }
-  }
-  return 1;
-}
+#define CODE(X) X
+
+#define FN(X) X ## Literal
+#include "./cluster_inc.h"  /* NOLINT(build/include) */
+#undef FN
+
+#define FN(X) X ## Command
+#include "./cluster_inc.h"  /* NOLINT(build/include) */
+#undef FN
+
+#define FN(X) X ## Distance
+#include "./cluster_inc.h"  /* NOLINT(build/include) */
+#undef FN
+
+#undef CODE
 
 #if defined(__cplusplus) || defined(c_plusplus)
 }  /* extern "C" */
 #endif