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 #ifndef BROTLI_ENC_BIT_COST_H_ 10 #define BROTLI_ENC_BIT_COST_H_ 11 12 #include <brotli/types.h> 13 14 #include "../common/platform.h" 15 #include "fast_log.h" 16 #include "histogram.h" 17 18 #if defined(__cplusplus) || defined(c_plusplus) 19 extern "C" { 20 #endif 21 ShannonEntropy(const uint32_t * population,size_t size,size_t * total)22static BROTLI_INLINE double ShannonEntropy( 23 const uint32_t* population, size_t size, size_t* total) { 24 size_t sum = 0; 25 double retval = 0; 26 const uint32_t* population_end = population + size; 27 size_t p; 28 if (size & 1) { 29 goto odd_number_of_elements_left; 30 } 31 while (population < population_end) { 32 p = *population++; 33 sum += p; 34 retval -= (double)p * FastLog2(p); 35 odd_number_of_elements_left: 36 p = *population++; 37 sum += p; 38 retval -= (double)p * FastLog2(p); 39 } 40 if (sum) retval += (double)sum * FastLog2(sum); 41 *total = sum; 42 return retval; 43 } 44 BitsEntropy(const uint32_t * population,size_t size)45static BROTLI_INLINE double BitsEntropy( 46 const uint32_t* population, size_t size) { 47 size_t sum; 48 double retval = ShannonEntropy(population, size, &sum); 49 if (retval < (double)sum) { 50 /* At least one bit per literal is needed. */ 51 retval = (double)sum; 52 } 53 return retval; 54 } 55 56 BROTLI_INTERNAL double BrotliPopulationCostLiteral(const HistogramLiteral*); 57 BROTLI_INTERNAL double BrotliPopulationCostCommand(const HistogramCommand*); 58 BROTLI_INTERNAL double BrotliPopulationCostDistance(const HistogramDistance*); 59 60 #if defined(__cplusplus) || defined(c_plusplus) 61 } /* extern "C" */ 62 #endif 63 64 #endif /* BROTLI_ENC_BIT_COST_H_ */ 65