1/* Copyright 2013 Google Inc. All Rights Reserved.
2
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
5*/
6
7/* Functions for clustering similar histograms together. */
8
9#include "./cluster.h"
10
11#include "../common/platform.h"
12#include <brotli/types.h>
13#include "./bit_cost.h" /* BrotliPopulationCost */
14#include "./fast_log.h"
15#include "./histogram.h"
16#include "./memory.h"
17
18#if defined(__cplusplus) || defined(c_plusplus)
19extern "C" {
20#endif
21
22static BROTLI_INLINE BROTLI_BOOL HistogramPairIsLess(
23 const HistogramPair* p1, const HistogramPair* p2) {
24 if (p1->cost_diff != p2->cost_diff) {
25 return TO_BROTLI_BOOL(p1->cost_diff > p2->cost_diff);
26 }
27 return TO_BROTLI_BOOL((p1->idx2 - p1->idx1) > (p2->idx2 - p2->idx1));
28}
29
30/* Returns entropy reduction of the context map when we combine two clusters. */
31static BROTLI_INLINE double ClusterCostDiff(size_t size_a, size_t size_b) {
32 size_t size_c = size_a + size_b;
33 return (double)size_a * FastLog2(size_a) +
34 (double)size_b * FastLog2(size_b) -
35 (double)size_c * FastLog2(size_c);
36}
37
38#define CODE(X) X
39
40#define FN(X) X ## Literal
41#include "./cluster_inc.h" /* NOLINT(build/include) */
42#undef FN
43
44#define FN(X) X ## Command
45#include "./cluster_inc.h" /* NOLINT(build/include) */
46#undef FN
47
48#define FN(X) X ## Distance
49#include "./cluster_inc.h" /* NOLINT(build/include) */
50#undef FN
51
52#undef CODE
53
54#if defined(__cplusplus) || defined(c_plusplus)
55} /* extern "C" */
56#endif
57