projects / mirror_edk2.git / blame
| 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 |