126fa459cSmrg/* Copyright 2013 Google Inc. All Rights Reserved. 226fa459cSmrg 326fa459cSmrg Distributed under MIT license. 426fa459cSmrg See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 526fa459cSmrg*/ 626fa459cSmrg 726fa459cSmrg/* Functions for clustering similar histograms together. */ 826fa459cSmrg 926fa459cSmrg#include "./cluster.h" 1026fa459cSmrg 1126fa459cSmrg#include "../common/platform.h" 1226fa459cSmrg#include <brotli/types.h> 1326fa459cSmrg#include "./bit_cost.h" /* BrotliPopulationCost */ 1426fa459cSmrg#include "./fast_log.h" 1526fa459cSmrg#include "./histogram.h" 1626fa459cSmrg#include "./memory.h" 1726fa459cSmrg 1826fa459cSmrg#if defined(__cplusplus) || defined(c_plusplus) 1926fa459cSmrgextern "C" { 2026fa459cSmrg#endif 2126fa459cSmrg 2226fa459cSmrgstatic BROTLI_INLINE BROTLI_BOOL HistogramPairIsLess( 2326fa459cSmrg const HistogramPair* p1, const HistogramPair* p2) { 2426fa459cSmrg if (p1->cost_diff != p2->cost_diff) { 2526fa459cSmrg return TO_BROTLI_BOOL(p1->cost_diff > p2->cost_diff); 2626fa459cSmrg } 2726fa459cSmrg return TO_BROTLI_BOOL((p1->idx2 - p1->idx1) > (p2->idx2 - p2->idx1)); 2826fa459cSmrg} 2926fa459cSmrg 3026fa459cSmrg/* Returns entropy reduction of the context map when we combine two clusters. */ 3126fa459cSmrgstatic BROTLI_INLINE double ClusterCostDiff(size_t size_a, size_t size_b) { 3226fa459cSmrg size_t size_c = size_a + size_b; 3326fa459cSmrg return (double)size_a * FastLog2(size_a) + 3426fa459cSmrg (double)size_b * FastLog2(size_b) - 3526fa459cSmrg (double)size_c * FastLog2(size_c); 3626fa459cSmrg} 3726fa459cSmrg 3826fa459cSmrg#define CODE(X) X 3926fa459cSmrg 4026fa459cSmrg#define FN(X) X ## Literal 4126fa459cSmrg#include "./cluster_inc.h" /* NOLINT(build/include) */ 4226fa459cSmrg#undef FN 4326fa459cSmrg 4426fa459cSmrg#define FN(X) X ## Command 4526fa459cSmrg#include "./cluster_inc.h" /* NOLINT(build/include) */ 4626fa459cSmrg#undef FN 4726fa459cSmrg 4826fa459cSmrg#define FN(X) X ## Distance 4926fa459cSmrg#include "./cluster_inc.h" /* NOLINT(build/include) */ 5026fa459cSmrg#undef FN 5126fa459cSmrg 5226fa459cSmrg#undef CODE 5326fa459cSmrg 5426fa459cSmrg#if defined(__cplusplus) || defined(c_plusplus) 5526fa459cSmrg} /* extern "C" */ 5626fa459cSmrg#endif 57