BaseTools/Source/C/BrotliCompress/enc/bit_cost.h

   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/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_ */