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, CODE */ |
9 | |
10 | #define HistogramType FN(Histogram) |
11 | |
12 | /* Computes the bit cost reduction by combining out[idx1] and out[idx2] and if |
13 | it is below a threshold, stores the pair (idx1, idx2) in the *pairs queue. */ |
14 | BROTLI_INTERNAL void FN(BrotliCompareAndPushToQueue)( |
15 | const HistogramType* out, const uint32_t* cluster_size, uint32_t idx1, |
16 | uint32_t idx2, size_t max_num_pairs, HistogramPair* pairs, |
17 | size_t* num_pairs) CODE({ |
18 | BROTLI_BOOL is_good_pair = BROTLI_FALSE; |
19 | HistogramPair p; |
20 | p.idx1 = p.idx2 = 0; |
21 | p.cost_diff = p.cost_combo = 0; |
22 | if (idx1 == idx2) { |
23 | return; |
24 | } |
25 | if (idx2 < idx1) { |
26 | uint32_t t = idx2; |
27 | idx2 = idx1; |
28 | idx1 = t; |
29 | } |
30 | p.idx1 = idx1; |
31 | p.idx2 = idx2; |
32 | p.cost_diff = 0.5 * ClusterCostDiff(cluster_size[idx1], cluster_size[idx2]); |
33 | p.cost_diff -= out[idx1].bit_cost_; |
34 | p.cost_diff -= out[idx2].bit_cost_; |
35 | |
36 | if (out[idx1].total_count_ == 0) { |
37 | p.cost_combo = out[idx2].bit_cost_; |
38 | is_good_pair = BROTLI_TRUE; |
39 | } else if (out[idx2].total_count_ == 0) { |
40 | p.cost_combo = out[idx1].bit_cost_; |
41 | is_good_pair = BROTLI_TRUE; |
42 | } else { |
43 | double threshold = *num_pairs == 0 ? 1e99 : |
44 | BROTLI_MAX(double, 0.0, pairs[0].cost_diff); |
45 | HistogramType combo = out[idx1]; |
46 | double cost_combo; |
47 | FN(HistogramAddHistogram)(&combo, &out[idx2]); |
48 | cost_combo = FN(BrotliPopulationCost)(&combo); |
49 | if (cost_combo < threshold - p.cost_diff) { |
50 | p.cost_combo = cost_combo; |
51 | is_good_pair = BROTLI_TRUE; |
52 | } |
53 | } |
54 | if (is_good_pair) { |
55 | p.cost_diff += p.cost_combo; |
56 | if (*num_pairs > 0 && HistogramPairIsLess(&pairs[0], &p)) { |
57 | /* Replace the top of the queue if needed. */ |
58 | if (*num_pairs < max_num_pairs) { |
59 | pairs[*num_pairs] = pairs[0]; |
60 | ++(*num_pairs); |
61 | } |
62 | pairs[0] = p; |
63 | } else if (*num_pairs < max_num_pairs) { |
64 | pairs[*num_pairs] = p; |
65 | ++(*num_pairs); |
66 | } |
67 | } |
68 | }) |
69 | |
70 | BROTLI_INTERNAL size_t FN(BrotliHistogramCombine)(HistogramType* out, |
71 | uint32_t* cluster_size, |
72 | uint32_t* symbols, |
73 | uint32_t* clusters, |
74 | HistogramPair* pairs, |
75 | size_t num_clusters, |
76 | size_t symbols_size, |
77 | size_t max_clusters, |
78 | size_t max_num_pairs) CODE({ |
79 | double cost_diff_threshold = 0.0; |
80 | size_t min_cluster_size = 1; |
81 | size_t num_pairs = 0; |
82 | |
83 | { |
84 | /* We maintain a vector of histogram pairs, with the property that the pair |
85 | with the maximum bit cost reduction is the first. */ |
86 | size_t idx1; |
87 | for (idx1 = 0; idx1 < num_clusters; ++idx1) { |
88 | size_t idx2; |
89 | for (idx2 = idx1 + 1; idx2 < num_clusters; ++idx2) { |
90 | FN(BrotliCompareAndPushToQueue)(out, cluster_size, clusters[idx1], |
91 | clusters[idx2], max_num_pairs, &pairs[0], &num_pairs); |
92 | } |
93 | } |
94 | } |
95 | |
96 | while (num_clusters > min_cluster_size) { |
97 | uint32_t best_idx1; |
98 | uint32_t best_idx2; |
99 | size_t i; |
100 | if (pairs[0].cost_diff >= cost_diff_threshold) { |
101 | cost_diff_threshold = 1e99; |
102 | min_cluster_size = max_clusters; |
103 | continue; |
104 | } |
105 | /* Take the best pair from the top of heap. */ |
106 | best_idx1 = pairs[0].idx1; |
107 | best_idx2 = pairs[0].idx2; |
108 | FN(HistogramAddHistogram)(&out[best_idx1], &out[best_idx2]); |
109 | out[best_idx1].bit_cost_ = pairs[0].cost_combo; |
110 | cluster_size[best_idx1] += cluster_size[best_idx2]; |
111 | for (i = 0; i < symbols_size; ++i) { |
112 | if (symbols[i] == best_idx2) { |
113 | symbols[i] = best_idx1; |
114 | } |
115 | } |
116 | for (i = 0; i < num_clusters; ++i) { |
117 | if (clusters[i] == best_idx2) { |
118 | memmove(&clusters[i], &clusters[i + 1], |
119 | (num_clusters - i - 1) * sizeof(clusters[0])); |
120 | break; |
121 | } |
122 | } |
123 | --num_clusters; |
124 | { |
125 | /* Remove pairs intersecting the just combined best pair. */ |
126 | size_t copy_to_idx = 0; |
127 | for (i = 0; i < num_pairs; ++i) { |
128 | HistogramPair* p = &pairs[i]; |
129 | if (p->idx1 == best_idx1 || p->idx2 == best_idx1 || |
130 | p->idx1 == best_idx2 || p->idx2 == best_idx2) { |
131 | /* Remove invalid pair from the queue. */ |
132 | continue; |
133 | } |
134 | if (HistogramPairIsLess(&pairs[0], p)) { |
135 | /* Replace the top of the queue if needed. */ |
136 | HistogramPair front = pairs[0]; |
137 | pairs[0] = *p; |
138 | pairs[copy_to_idx] = front; |
139 | } else { |
140 | pairs[copy_to_idx] = *p; |
141 | } |
142 | ++copy_to_idx; |
143 | } |
144 | num_pairs = copy_to_idx; |
145 | } |
146 | |
147 | /* Push new pairs formed with the combined histogram to the heap. */ |
148 | for (i = 0; i < num_clusters; ++i) { |
149 | FN(BrotliCompareAndPushToQueue)(out, cluster_size, best_idx1, clusters[i], |
150 | max_num_pairs, &pairs[0], &num_pairs); |
151 | } |
152 | } |
153 | return num_clusters; |
154 | }) |
155 | |
156 | /* What is the bit cost of moving histogram from cur_symbol to candidate. */ |
157 | BROTLI_INTERNAL double FN(BrotliHistogramBitCostDistance)( |
158 | const HistogramType* histogram, const HistogramType* candidate) CODE({ |
159 | if (histogram->total_count_ == 0) { |
160 | return 0.0; |
161 | } else { |
162 | HistogramType tmp = *histogram; |
163 | FN(HistogramAddHistogram)(&tmp, candidate); |
164 | return FN(BrotliPopulationCost)(&tmp) - candidate->bit_cost_; |
165 | } |
166 | }) |
167 | |
168 | /* Find the best 'out' histogram for each of the 'in' histograms. |
169 | When called, clusters[0..num_clusters) contains the unique values from |
170 | symbols[0..in_size), but this property is not preserved in this function. |
171 | Note: we assume that out[]->bit_cost_ is already up-to-date. */ |
172 | BROTLI_INTERNAL void FN(BrotliHistogramRemap)(const HistogramType* in, |
173 | size_t in_size, const uint32_t* clusters, size_t num_clusters, |
174 | HistogramType* out, uint32_t* symbols) CODE({ |
175 | size_t i; |
176 | for (i = 0; i < in_size; ++i) { |
177 | uint32_t best_out = i == 0 ? symbols[0] : symbols[i - 1]; |
178 | double best_bits = |
179 | FN(BrotliHistogramBitCostDistance)(&in[i], &out[best_out]); |
180 | size_t j; |
181 | for (j = 0; j < num_clusters; ++j) { |
182 | const double cur_bits = |
183 | FN(BrotliHistogramBitCostDistance)(&in[i], &out[clusters[j]]); |
184 | if (cur_bits < best_bits) { |
185 | best_bits = cur_bits; |
186 | best_out = clusters[j]; |
187 | } |
188 | } |
189 | symbols[i] = best_out; |
190 | } |
191 | |
192 | /* Recompute each out based on raw and symbols. */ |
193 | for (i = 0; i < num_clusters; ++i) { |
194 | FN(HistogramClear)(&out[clusters[i]]); |
195 | } |
196 | for (i = 0; i < in_size; ++i) { |
197 | FN(HistogramAddHistogram)(&out[symbols[i]], &in[i]); |
198 | } |
199 | }) |
200 | |
201 | /* Reorders elements of the out[0..length) array and changes values in |
202 | symbols[0..length) array in the following way: |
203 | * when called, symbols[] contains indexes into out[], and has N unique |
204 | values (possibly N < length) |
205 | * on return, symbols'[i] = f(symbols[i]) and |
206 | out'[symbols'[i]] = out[symbols[i]], for each 0 <= i < length, |
207 | where f is a bijection between the range of symbols[] and [0..N), and |
208 | the first occurrences of values in symbols'[i] come in consecutive |
209 | increasing order. |
210 | Returns N, the number of unique values in symbols[]. */ |
211 | BROTLI_INTERNAL size_t FN(BrotliHistogramReindex)(MemoryManager* m, |
212 | HistogramType* out, uint32_t* symbols, size_t length) CODE({ |
213 | static const uint32_t kInvalidIndex = BROTLI_UINT32_MAX; |
214 | uint32_t* new_index = BROTLI_ALLOC(m, uint32_t, length); |
215 | uint32_t next_index; |
216 | HistogramType* tmp; |
217 | size_t i; |
218 | if (BROTLI_IS_OOM(m)) return 0; |
219 | for (i = 0; i < length; ++i) { |
220 | new_index[i] = kInvalidIndex; |
221 | } |
222 | next_index = 0; |
223 | for (i = 0; i < length; ++i) { |
224 | if (new_index[symbols[i]] == kInvalidIndex) { |
225 | new_index[symbols[i]] = next_index; |
226 | ++next_index; |
227 | } |
228 | } |
229 | /* TODO: by using idea of "cycle-sort" we can avoid allocation of |
230 | tmp and reduce the number of copying by the factor of 2. */ |
231 | tmp = BROTLI_ALLOC(m, HistogramType, next_index); |
232 | if (BROTLI_IS_OOM(m)) return 0; |
233 | next_index = 0; |
234 | for (i = 0; i < length; ++i) { |
235 | if (new_index[symbols[i]] == next_index) { |
236 | tmp[next_index] = out[symbols[i]]; |
237 | ++next_index; |
238 | } |
239 | symbols[i] = new_index[symbols[i]]; |
240 | } |
241 | BROTLI_FREE(m, new_index); |
242 | for (i = 0; i < next_index; ++i) { |
243 | out[i] = tmp[i]; |
244 | } |
245 | BROTLI_FREE(m, tmp); |
246 | return next_index; |
247 | }) |
248 | |
249 | BROTLI_INTERNAL void FN(BrotliClusterHistograms)( |
250 | MemoryManager* m, const HistogramType* in, const size_t in_size, |
251 | size_t max_histograms, HistogramType* out, size_t* out_size, |
252 | uint32_t* histogram_symbols) CODE({ |
253 | uint32_t* cluster_size = BROTLI_ALLOC(m, uint32_t, in_size); |
254 | uint32_t* clusters = BROTLI_ALLOC(m, uint32_t, in_size); |
255 | size_t num_clusters = 0; |
256 | const size_t max_input_histograms = 64; |
257 | size_t pairs_capacity = max_input_histograms * max_input_histograms / 2; |
258 | /* For the first pass of clustering, we allow all pairs. */ |
259 | HistogramPair* pairs = BROTLI_ALLOC(m, HistogramPair, pairs_capacity + 1); |
260 | size_t i; |
261 | |
262 | if (BROTLI_IS_OOM(m)) return; |
263 | |
264 | for (i = 0; i < in_size; ++i) { |
265 | cluster_size[i] = 1; |
266 | } |
267 | |
268 | for (i = 0; i < in_size; ++i) { |
269 | out[i] = in[i]; |
270 | out[i].bit_cost_ = FN(BrotliPopulationCost)(&in[i]); |
271 | histogram_symbols[i] = (uint32_t)i; |
272 | } |
273 | |
274 | for (i = 0; i < in_size; i += max_input_histograms) { |
275 | size_t num_to_combine = |
276 | BROTLI_MIN(size_t, in_size - i, max_input_histograms); |
277 | size_t num_new_clusters; |
278 | size_t j; |
279 | for (j = 0; j < num_to_combine; ++j) { |
280 | clusters[num_clusters + j] = (uint32_t)(i + j); |
281 | } |
282 | num_new_clusters = |
283 | FN(BrotliHistogramCombine)(out, cluster_size, |
284 | &histogram_symbols[i], |
285 | &clusters[num_clusters], pairs, |
286 | num_to_combine, num_to_combine, |
287 | max_histograms, pairs_capacity); |
288 | num_clusters += num_new_clusters; |
289 | } |
290 | |
291 | { |
292 | /* For the second pass, we limit the total number of histogram pairs. |
293 | After this limit is reached, we only keep searching for the best pair. */ |
294 | size_t max_num_pairs = BROTLI_MIN(size_t, |
295 | 64 * num_clusters, (num_clusters / 2) * num_clusters); |
296 | BROTLI_ENSURE_CAPACITY( |
297 | m, HistogramPair, pairs, pairs_capacity, max_num_pairs + 1); |
298 | if (BROTLI_IS_OOM(m)) return; |
299 | |
300 | /* Collapse similar histograms. */ |
301 | num_clusters = FN(BrotliHistogramCombine)(out, cluster_size, |
302 | histogram_symbols, clusters, |
303 | pairs, num_clusters, in_size, |
304 | max_histograms, max_num_pairs); |
305 | } |
306 | BROTLI_FREE(m, pairs); |
307 | BROTLI_FREE(m, cluster_size); |
308 | /* Find the optimal map from original histograms to the final ones. */ |
309 | FN(BrotliHistogramRemap)(in, in_size, clusters, num_clusters, |
310 | out, histogram_symbols); |
311 | BROTLI_FREE(m, clusters); |
312 | /* Convert the context map to a canonical form. */ |
313 | *out_size = FN(BrotliHistogramReindex)(m, out, histogram_symbols, in_size); |
314 | if (BROTLI_IS_OOM(m)) return; |
315 | }) |
316 | |
317 | #undef HistogramType |
318 | |