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 "../common/platform.h" |
13 | #include <brotli/types.h> |
14 | #include "./fast_log.h" |
15 | #include "./histogram.h" |
16 | |
17 | #if defined(__cplusplus) || defined(c_plusplus) |
18 | extern "C"{ |
19 | #endif |
20 | |
21 | static BROTLI_INLINE double ShannonEntropy( |
22 | const uint32_t* population, 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 |