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