bit_cost_inc.h (4115B)
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 double FN(BrotliPopulationCost)(const HistogramType* histogram) { 13 static const double kOneSymbolHistogramCost = 12; 14 static const double kTwoSymbolHistogramCost = 20; 15 static const double kThreeSymbolHistogramCost = 28; 16 static const double kFourSymbolHistogramCost = 37; 17 const size_t data_size = FN(HistogramDataSize)(); 18 int count = 0; 19 size_t s[5]; 20 double bits = 0.0; 21 size_t i; 22 if (histogram->total_count_ == 0) { 23 return kOneSymbolHistogramCost; 24 } 25 for (i = 0; i < data_size; ++i) { 26 if (histogram->data_[i] > 0) { 27 s[count] = i; 28 ++count; 29 if (count > 4) break; 30 } 31 } 32 if (count == 1) { 33 return kOneSymbolHistogramCost; 34 } 35 if (count == 2) { 36 return (kTwoSymbolHistogramCost + (double)histogram->total_count_); 37 } 38 if (count == 3) { 39 const uint32_t histo0 = histogram->data_[s[0]]; 40 const uint32_t histo1 = histogram->data_[s[1]]; 41 const uint32_t histo2 = histogram->data_[s[2]]; 42 const uint32_t histomax = 43 BROTLI_MAX(uint32_t, histo0, BROTLI_MAX(uint32_t, histo1, histo2)); 44 return (kThreeSymbolHistogramCost + 45 2 * (histo0 + histo1 + histo2) - histomax); 46 } 47 if (count == 4) { 48 uint32_t histo[4]; 49 uint32_t h23; 50 uint32_t histomax; 51 for (i = 0; i < 4; ++i) { 52 histo[i] = histogram->data_[s[i]]; 53 } 54 /* Sort */ 55 for (i = 0; i < 4; ++i) { 56 size_t j; 57 for (j = i + 1; j < 4; ++j) { 58 if (histo[j] > histo[i]) { 59 BROTLI_SWAP(uint32_t, histo, j, i); 60 } 61 } 62 } 63 h23 = histo[2] + histo[3]; 64 histomax = BROTLI_MAX(uint32_t, h23, histo[0]); 65 return (kFourSymbolHistogramCost + 66 3 * h23 + 2 * (histo[0] + histo[1]) - histomax); 67 } 68 69 { 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 size_t max_depth = 1; 74 uint32_t depth_histo[BROTLI_CODE_LENGTH_CODES] = { 0 }; 75 const double log2total = FastLog2(histogram->total_count_); 76 for (i = 0; i < data_size;) { 77 if (histogram->data_[i] > 0) { 78 /* Compute -log2(P(symbol)) = -log2(count(symbol)/total_count) = 79 = log2(total_count) - log2(count(symbol)) */ 80 double log2p = log2total - FastLog2(histogram->data_[i]); 81 /* Approximate the bit depth by round(-log2(P(symbol))) */ 82 size_t depth = (size_t)(log2p + 0.5); 83 bits += histogram->data_[i] * log2p; 84 if (depth > 15) { 85 depth = 15; 86 } 87 if (depth > max_depth) { 88 max_depth = depth; 89 } 90 ++depth_histo[depth]; 91 ++i; 92 } 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 uint32_t reps = 1; 96 size_t k; 97 for (k = i + 1; k < data_size && histogram->data_[k] == 0; ++k) { 98 ++reps; 99 } 100 i += reps; 101 if (i == data_size) { 102 /* Don't add any cost for the last zero run, since these are encoded 103 only implicitly. */ 104 break; 105 } 106 if (reps < 3) { 107 depth_histo[0] += reps; 108 } else { 109 reps -= 2; 110 while (reps > 0) { 111 ++depth_histo[BROTLI_REPEAT_ZERO_CODE_LENGTH]; 112 /* Add the 3 extra bits for the 17 code length code. */ 113 bits += 3; 114 reps >>= 3; 115 } 116 } 117 } 118 } 119 /* Add the estimated encoding cost of the code length code histogram. */ 120 bits += (double)(18 + 2 * max_depth); 121 /* Add the entropy of the code length code histogram. */ 122 bits += BrotliBitsEntropy(depth_histo, BROTLI_CODE_LENGTH_CODES); 123 } 124 return bits; 125 } 126 127 #undef HistogramType