cluster.c (1458B)
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 "bit_cost.h" /* BrotliPopulationCost */ 13 #include "fast_log.h" 14 #include "histogram.h" 15 #include "memory.h" 16 17 #if defined(__cplusplus) || defined(c_plusplus) 18 extern "C" { 19 #endif 20 21 static BROTLI_INLINE BROTLI_BOOL HistogramPairIsLess( 22 const HistogramPair* p1, const HistogramPair* p2) { 23 if (p1->cost_diff != p2->cost_diff) { 24 return TO_BROTLI_BOOL(p1->cost_diff > p2->cost_diff); 25 } 26 return TO_BROTLI_BOOL((p1->idx2 - p1->idx1) > (p2->idx2 - p2->idx1)); 27 } 28 29 /* Returns entropy reduction of the context map when we combine two clusters. */ 30 static BROTLI_INLINE double ClusterCostDiff(size_t size_a, size_t size_b) { 31 size_t size_c = size_a + size_b; 32 return (double)size_a * FastLog2(size_a) + 33 (double)size_b * FastLog2(size_b) - 34 (double)size_c * FastLog2(size_c); 35 } 36 37 #define CODE(X) X 38 39 #define FN(X) X ## Literal 40 #include "cluster_inc.h" /* NOLINT(build/include) */ 41 #undef FN 42 43 #define FN(X) X ## Command 44 #include "cluster_inc.h" /* NOLINT(build/include) */ 45 #undef FN 46 47 #define FN(X) X ## Distance 48 #include "cluster_inc.h" /* NOLINT(build/include) */ 49 #undef FN 50 51 #undef CODE 52 53 #if defined(__cplusplus) || defined(c_plusplus) 54 } /* extern "C" */ 55 #endif