bit_cost.c (1427B)
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 to estimate the bit cost of Huffman trees. */ 8 9 #include "bit_cost.h" 10 11 #include "../common/platform.h" 12 #include "fast_log.h" 13 14 #if defined(__cplusplus) || defined(c_plusplus) 15 extern "C" { 16 #endif 17 18 double BrotliBitsEntropy(const uint32_t* population, size_t size) { 19 size_t sum = 0; 20 double retval = 0; 21 const uint32_t* population_end = population + size; 22 size_t p; 23 if (size & 1) { 24 goto odd_number_of_elements_left; 25 } 26 while (population < population_end) { 27 p = *population++; 28 sum += p; 29 retval -= (double)p * FastLog2(p); 30 odd_number_of_elements_left: 31 p = *population++; 32 sum += p; 33 retval -= (double)p * FastLog2(p); 34 } 35 if (sum) retval += (double)sum * FastLog2(sum); 36 37 if (retval < (double)sum) { 38 /* TODO(eustas): consider doing that per-symbol? */ 39 /* At least one bit per literal is needed. */ 40 retval = (double)sum; 41 } 42 43 return retval; 44 } 45 46 #define FN(X) X ## Literal 47 #include "bit_cost_inc.h" /* NOLINT(build/include) */ 48 #undef FN 49 50 #define FN(X) X ## Command 51 #include "bit_cost_inc.h" /* NOLINT(build/include) */ 52 #undef FN 53 54 #define FN(X) X ## Distance 55 #include "bit_cost_inc.h" /* NOLINT(build/include) */ 56 #undef FN 57 58 #if defined(__cplusplus) || defined(c_plusplus) 59 } /* extern "C" */ 60 #endif