]>
Commit | Line | Data |
---|---|---|
11b7501a SB |
1 | /* Copyright 2013 Google Inc. All Rights Reserved.\r |
2 | \r | |
3 | Distributed under MIT license.\r | |
4 | See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r | |
5 | */\r | |
6 | \r | |
7 | /* Functions to estimate the bit cost of Huffman trees. */\r | |
8 | \r | |
9 | #ifndef BROTLI_ENC_BIT_COST_H_\r | |
10 | #define BROTLI_ENC_BIT_COST_H_\r | |
11 | \r | |
12 | #include "../common/types.h"\r | |
13 | #include "./fast_log.h"\r | |
14 | #include "./histogram.h"\r | |
15 | #include "./port.h"\r | |
16 | \r | |
17 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
18 | extern "C" {\r | |
19 | #endif\r | |
20 | \r | |
21 | static BROTLI_INLINE double ShannonEntropy(const uint32_t *population,\r | |
22 | size_t size, size_t *total) {\r | |
23 | size_t sum = 0;\r | |
24 | double retval = 0;\r | |
25 | const uint32_t *population_end = population + size;\r | |
26 | size_t p;\r | |
27 | if (size & 1) {\r | |
28 | goto odd_number_of_elements_left;\r | |
29 | }\r | |
30 | while (population < population_end) {\r | |
31 | p = *population++;\r | |
32 | sum += p;\r | |
33 | retval -= (double)p * FastLog2(p);\r | |
34 | odd_number_of_elements_left:\r | |
35 | p = *population++;\r | |
36 | sum += p;\r | |
37 | retval -= (double)p * FastLog2(p);\r | |
38 | }\r | |
39 | if (sum) retval += (double)sum * FastLog2(sum);\r | |
40 | *total = sum;\r | |
41 | return retval;\r | |
42 | }\r | |
43 | \r | |
44 | static BROTLI_INLINE double BitsEntropy(\r | |
45 | const uint32_t *population, size_t size) {\r | |
46 | size_t sum;\r | |
47 | double retval = ShannonEntropy(population, size, &sum);\r | |
48 | if (retval < sum) {\r | |
49 | /* At least one bit per literal is needed. */\r | |
50 | retval = (double)sum;\r | |
51 | }\r | |
52 | return retval;\r | |
53 | }\r | |
54 | \r | |
55 | BROTLI_INTERNAL double BrotliPopulationCostLiteral(const HistogramLiteral*);\r | |
56 | BROTLI_INTERNAL double BrotliPopulationCostCommand(const HistogramCommand*);\r | |
57 | BROTLI_INTERNAL double BrotliPopulationCostDistance(const HistogramDistance*);\r | |
58 | \r | |
59 | #if defined(__cplusplus) || defined(c_plusplus)\r | |
60 | } /* extern "C" */\r | |
61 | #endif\r | |
62 | \r | |
63 | #endif /* BROTLI_ENC_BIT_COST_H_ */\r |