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