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