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