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. */
14BROTLI_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
70BROTLI_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. */
157BROTLI_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. */
172BROTLI_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[]. */
211BROTLI_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
249BROTLI_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