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