1 // Copyright 2013 Google Inc. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // Functions to estimate the bit cost of Huffman trees.
16
17 #ifndef BROTLI_ENC_BIT_COST_H_
18 #define BROTLI_ENC_BIT_COST_H_
19
20 #include <stdint.h>
21
22 #include "./entropy_encode.h"
23 #include "./fast_log.h"
24
25 namespace brotli {
26
27 static const int kHuffmanExtraBits[kCodeLengthCodes] = {
28 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3,
29 };
30
HuffmanTreeBitCost(const int * counts,const uint8_t * depth)31 static inline int HuffmanTreeBitCost(const int* counts, const uint8_t* depth) {
32 int nbits = 0;
33 for (int i = 0; i < kCodeLengthCodes; ++i) {
34 nbits += counts[i] * (depth[i] + kHuffmanExtraBits[i]);
35 }
36 return nbits;
37 }
38
HuffmanTreeBitCost(const Histogram<kCodeLengthCodes> & histogram,const EntropyCode<kCodeLengthCodes> & entropy)39 static inline int HuffmanTreeBitCost(
40 const Histogram<kCodeLengthCodes>& histogram,
41 const EntropyCode<kCodeLengthCodes>& entropy) {
42 return HuffmanTreeBitCost(&histogram.data_[0], &entropy.depth_[0]);
43 }
44
HuffmanBitCost(const uint8_t * depth,int length)45 static inline int HuffmanBitCost(const uint8_t* depth, int length) {
46 int max_depth = 1;
47 int histogram[kCodeLengthCodes] = { 0 };
48 int tail_start = 0;
49 int prev_value = 8;
50 // compute histogram of compacted huffman tree
51 for (int i = 0; i < length;) {
52 const int value = depth[i];
53 if (value > max_depth) {
54 max_depth = value;
55 }
56 int reps = 1;
57 for (int k = i + 1; k < length && depth[k] == value; ++k) {
58 ++reps;
59 }
60 i += reps;
61 if (i == length && value == 0)
62 break;
63 if (value == 0) {
64 if (reps < 3) {
65 histogram[0] += reps;
66 } else {
67 reps -= 2;
68 while (reps > 0) {
69 ++histogram[17];
70 reps >>= 3;
71 }
72 }
73 } else {
74 tail_start = i;
75 if (value != prev_value) {
76 ++histogram[value];
77 --reps;
78 }
79 prev_value = value;
80 if (reps < 3) {
81 histogram[value] += reps;
82 } else {
83 reps -= 2;
84 while (reps > 0) {
85 ++histogram[16];
86 reps >>= 2;
87 }
88 }
89 }
90 }
91
92 // create huffman tree of huffman tree
93 uint8_t cost[kCodeLengthCodes] = { 0 };
94 CreateHuffmanTree(histogram, kCodeLengthCodes, 7, cost);
95 // account for rle extra bits
96 cost[16] += 2;
97 cost[17] += 3;
98
99 int tree_size = 0;
100 int bits = 18 + 2 * max_depth; // huffman tree of huffman tree cost
101 for (int i = 0; i < kCodeLengthCodes; ++i) {
102 bits += histogram[i] * cost[i]; // huffman tree bit cost
103 tree_size += histogram[i];
104 }
105 return bits;
106 }
107
108 template<int kSize>
PopulationCost(const Histogram<kSize> & histogram)109 double PopulationCost(const Histogram<kSize>& histogram) {
110 if (histogram.total_count_ == 0) {
111 return 12;
112 }
113 int count = 0;
114 for (int i = 0; i < kSize && count < 5; ++i) {
115 if (histogram.data_[i] > 0) {
116 ++count;
117 }
118 }
119 if (count == 1) {
120 return 12;
121 }
122 if (count == 2) {
123 return 20 + histogram.total_count_;
124 }
125 uint8_t depth[kSize] = { 0 };
126 CreateHuffmanTree(&histogram.data_[0], kSize, 15, depth);
127 int bits = 0;
128 for (int i = 0; i < kSize; ++i) {
129 bits += histogram.data_[i] * depth[i];
130 }
131 if (count == 3) {
132 bits += 28;
133 } else if (count == 4) {
134 bits += 37;
135 } else {
136 bits += HuffmanBitCost(depth, kSize);
137 }
138 return bits;
139 }
140
141 } // namespace brotli
142
143 #endif // BROTLI_ENC_BIT_COST_H_
144