11cb0ef41Sopenharmony_ci/* Copyright 2013 Google Inc. All Rights Reserved. 21cb0ef41Sopenharmony_ci 31cb0ef41Sopenharmony_ci Distributed under MIT license. 41cb0ef41Sopenharmony_ci See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 51cb0ef41Sopenharmony_ci*/ 61cb0ef41Sopenharmony_ci 71cb0ef41Sopenharmony_ci/* Functions for clustering similar histograms together. */ 81cb0ef41Sopenharmony_ci 91cb0ef41Sopenharmony_ci#include "./cluster.h" 101cb0ef41Sopenharmony_ci 111cb0ef41Sopenharmony_ci#include "../common/platform.h" 121cb0ef41Sopenharmony_ci#include <brotli/types.h> 131cb0ef41Sopenharmony_ci#include "./bit_cost.h" /* BrotliPopulationCost */ 141cb0ef41Sopenharmony_ci#include "./fast_log.h" 151cb0ef41Sopenharmony_ci#include "./histogram.h" 161cb0ef41Sopenharmony_ci#include "./memory.h" 171cb0ef41Sopenharmony_ci 181cb0ef41Sopenharmony_ci#if defined(__cplusplus) || defined(c_plusplus) 191cb0ef41Sopenharmony_ciextern "C" { 201cb0ef41Sopenharmony_ci#endif 211cb0ef41Sopenharmony_ci 221cb0ef41Sopenharmony_cistatic BROTLI_INLINE BROTLI_BOOL HistogramPairIsLess( 231cb0ef41Sopenharmony_ci const HistogramPair* p1, const HistogramPair* p2) { 241cb0ef41Sopenharmony_ci if (p1->cost_diff != p2->cost_diff) { 251cb0ef41Sopenharmony_ci return TO_BROTLI_BOOL(p1->cost_diff > p2->cost_diff); 261cb0ef41Sopenharmony_ci } 271cb0ef41Sopenharmony_ci return TO_BROTLI_BOOL((p1->idx2 - p1->idx1) > (p2->idx2 - p2->idx1)); 281cb0ef41Sopenharmony_ci} 291cb0ef41Sopenharmony_ci 301cb0ef41Sopenharmony_ci/* Returns entropy reduction of the context map when we combine two clusters. */ 311cb0ef41Sopenharmony_cistatic BROTLI_INLINE double ClusterCostDiff(size_t size_a, size_t size_b) { 321cb0ef41Sopenharmony_ci size_t size_c = size_a + size_b; 331cb0ef41Sopenharmony_ci return (double)size_a * FastLog2(size_a) + 341cb0ef41Sopenharmony_ci (double)size_b * FastLog2(size_b) - 351cb0ef41Sopenharmony_ci (double)size_c * FastLog2(size_c); 361cb0ef41Sopenharmony_ci} 371cb0ef41Sopenharmony_ci 381cb0ef41Sopenharmony_ci#define CODE(X) X 391cb0ef41Sopenharmony_ci 401cb0ef41Sopenharmony_ci#define FN(X) X ## Literal 411cb0ef41Sopenharmony_ci#include "./cluster_inc.h" /* NOLINT(build/include) */ 421cb0ef41Sopenharmony_ci#undef FN 431cb0ef41Sopenharmony_ci 441cb0ef41Sopenharmony_ci#define FN(X) X ## Command 451cb0ef41Sopenharmony_ci#include "./cluster_inc.h" /* NOLINT(build/include) */ 461cb0ef41Sopenharmony_ci#undef FN 471cb0ef41Sopenharmony_ci 481cb0ef41Sopenharmony_ci#define FN(X) X ## Distance 491cb0ef41Sopenharmony_ci#include "./cluster_inc.h" /* NOLINT(build/include) */ 501cb0ef41Sopenharmony_ci#undef FN 511cb0ef41Sopenharmony_ci 521cb0ef41Sopenharmony_ci#undef CODE 531cb0ef41Sopenharmony_ci 541cb0ef41Sopenharmony_ci#if defined(__cplusplus) || defined(c_plusplus) 551cb0ef41Sopenharmony_ci} /* extern "C" */ 561cb0ef41Sopenharmony_ci#endif 57