Coverage Report

Created: 2025-06-10 07:27

/src/ghostpdl/brotli/c/enc/bit_cost_inc.h
Line
Count
Source (jump to first uncovered line)
1
/* NOLINT(build/header_guard) */
2
/* Copyright 2013 Google Inc. All Rights Reserved.
3
4
   Distributed under MIT license.
5
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6
*/
7
8
/* template parameters: FN */
9
10
#define HistogramType FN(Histogram)
11
12
0
double FN(BrotliPopulationCost)(const HistogramType* histogram) {
13
0
  static const double kOneSymbolHistogramCost = 12;
14
0
  static const double kTwoSymbolHistogramCost = 20;
15
0
  static const double kThreeSymbolHistogramCost = 28;
16
0
  static const double kFourSymbolHistogramCost = 37;
17
0
  const size_t data_size = FN(HistogramDataSize)();
18
0
  int count = 0;
19
0
  size_t s[5];
20
0
  double bits = 0.0;
21
0
  size_t i;
22
0
  if (histogram->total_count_ == 0) {
23
0
    return kOneSymbolHistogramCost;
24
0
  }
25
0
  for (i = 0; i < data_size; ++i) {
26
0
    if (histogram->data_[i] > 0) {
27
0
      s[count] = i;
28
0
      ++count;
29
0
      if (count > 4) break;
30
0
    }
31
0
  }
32
0
  if (count == 1) {
33
0
    return kOneSymbolHistogramCost;
34
0
  }
35
0
  if (count == 2) {
36
0
    return (kTwoSymbolHistogramCost + (double)histogram->total_count_);
37
0
  }
38
0
  if (count == 3) {
39
0
    const uint32_t histo0 = histogram->data_[s[0]];
40
0
    const uint32_t histo1 = histogram->data_[s[1]];
41
0
    const uint32_t histo2 = histogram->data_[s[2]];
42
0
    const uint32_t histomax =
43
0
        BROTLI_MAX(uint32_t, histo0, BROTLI_MAX(uint32_t, histo1, histo2));
44
0
    return (kThreeSymbolHistogramCost +
45
0
            2 * (histo0 + histo1 + histo2) - histomax);
46
0
  }
47
0
  if (count == 4) {
48
0
    uint32_t histo[4];
49
0
    uint32_t h23;
50
0
    uint32_t histomax;
51
0
    for (i = 0; i < 4; ++i) {
52
0
      histo[i] = histogram->data_[s[i]];
53
0
    }
54
    /* Sort */
55
0
    for (i = 0; i < 4; ++i) {
56
0
      size_t j;
57
0
      for (j = i + 1; j < 4; ++j) {
58
0
        if (histo[j] > histo[i]) {
59
0
          BROTLI_SWAP(uint32_t, histo, j, i);
60
0
        }
61
0
      }
62
0
    }
63
0
    h23 = histo[2] + histo[3];
64
0
    histomax = BROTLI_MAX(uint32_t, h23, histo[0]);
65
0
    return (kFourSymbolHistogramCost +
66
0
            3 * h23 + 2 * (histo[0] + histo[1]) - histomax);
67
0
  }
68
69
0
  {
70
    /* In this loop we compute the entropy of the histogram and simultaneously
71
       build a simplified histogram of the code length codes where we use the
72
       zero repeat code 17, but we don't use the non-zero repeat code 16. */
73
0
    size_t max_depth = 1;
74
0
    uint32_t depth_histo[BROTLI_CODE_LENGTH_CODES] = { 0 };
75
0
    const double log2total = FastLog2(histogram->total_count_);
76
0
    for (i = 0; i < data_size;) {
77
0
      if (histogram->data_[i] > 0) {
78
        /* Compute -log2(P(symbol)) = -log2(count(symbol)/total_count) =
79
                                    = log2(total_count) - log2(count(symbol)) */
80
0
        double log2p = log2total - FastLog2(histogram->data_[i]);
81
        /* Approximate the bit depth by round(-log2(P(symbol))) */
82
0
        size_t depth = (size_t)(log2p + 0.5);
83
0
        bits += histogram->data_[i] * log2p;
84
0
        if (depth > 15) {
85
0
          depth = 15;
86
0
        }
87
0
        if (depth > max_depth) {
88
0
          max_depth = depth;
89
0
        }
90
0
        ++depth_histo[depth];
91
0
        ++i;
92
0
      } else {
93
        /* Compute the run length of zeros and add the appropriate number of 0
94
           and 17 code length codes to the code length code histogram. */
95
0
        uint32_t reps = 1;
96
0
        size_t k;
97
0
        for (k = i + 1; k < data_size && histogram->data_[k] == 0; ++k) {
98
0
          ++reps;
99
0
        }
100
0
        i += reps;
101
0
        if (i == data_size) {
102
          /* Don't add any cost for the last zero run, since these are encoded
103
             only implicitly. */
104
0
          break;
105
0
        }
106
0
        if (reps < 3) {
107
0
          depth_histo[0] += reps;
108
0
        } else {
109
0
          reps -= 2;
110
0
          while (reps > 0) {
111
0
            ++depth_histo[BROTLI_REPEAT_ZERO_CODE_LENGTH];
112
            /* Add the 3 extra bits for the 17 code length code. */
113
0
            bits += 3;
114
0
            reps >>= 3;
115
0
          }
116
0
        }
117
0
      }
118
0
    }
119
    /* Add the estimated encoding cost of the code length code histogram. */
120
0
    bits += (double)(18 + 2 * max_depth);
121
    /* Add the entropy of the code length code histogram. */
122
0
    bits += BitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES);
123
0
  }
124
0
  return bits;
125
0
}
Unexecuted instantiation: BrotliPopulationCostLiteral
Unexecuted instantiation: BrotliPopulationCostCommand
Unexecuted instantiation: BrotliPopulationCostDistance
126
127
#undef HistogramType