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, DataType */
9
10#define HistogramType FN(Histogram)
11
12static void FN(InitialEntropyCodes)(const DataType* data, size_t length,
13                                    size_t stride,
14                                    size_t num_histograms,
15                                    HistogramType* histograms) {
16  unsigned int seed = 7;
17  size_t block_length = length / num_histograms;
18  size_t i;
19  FN(ClearHistograms)(histograms, num_histograms);
20  for (i = 0; i < num_histograms; ++i) {
21    size_t pos = length * i / num_histograms;
22    if (i != 0) {
23      pos += MyRand(&seed) % block_length;
24    }
25    if (pos + stride >= length) {
26      pos = length - stride - 1;
27    }
28    FN(HistogramAddVector)(&histograms[i], data + pos, stride);
29  }
30}
31
32static void FN(RandomSample)(unsigned int* seed,
33                             const DataType* data,
34                             size_t length,
35                             size_t stride,
36                             HistogramType* sample) {
37  size_t pos = 0;
38  if (stride >= length) {
39    pos = 0;
40    stride = length;
41  } else {
42    pos = MyRand(seed) % (length - stride + 1);
43  }
44  FN(HistogramAddVector)(sample, data + pos, stride);
45}
46
47static void FN(RefineEntropyCodes)(const DataType* data, size_t length,
48                                   size_t stride,
49                                   size_t num_histograms,
50                                   HistogramType* histograms) {
51  size_t iters =
52      kIterMulForRefining * length / stride + kMinItersForRefining;
53  unsigned int seed = 7;
54  size_t iter;
55  iters = ((iters + num_histograms - 1) / num_histograms) * num_histograms;
56  for (iter = 0; iter < iters; ++iter) {
57    HistogramType sample;
58    FN(HistogramClear)(&sample);
59    FN(RandomSample)(&seed, data, length, stride, &sample);
60    FN(HistogramAddHistogram)(&histograms[iter % num_histograms], &sample);
61  }
62}
63
64/* Assigns a block id from the range [0, num_histograms) to each data element
65   in data[0..length) and fills in block_id[0..length) with the assigned values.
66   Returns the number of blocks, i.e. one plus the number of block switches. */
67static size_t FN(FindBlocks)(const DataType* data, const size_t length,
68                             const double block_switch_bitcost,
69                             const size_t num_histograms,
70                             const HistogramType* histograms,
71                             double* insert_cost,
72                             double* cost,
73                             uint8_t* switch_signal,
74                             uint8_t *block_id) {
75  const size_t data_size = FN(HistogramDataSize)();
76  const size_t bitmaplen = (num_histograms + 7) >> 3;
77  size_t num_blocks = 1;
78  size_t i;
79  size_t j;
80  assert(num_histograms <= 256);
81  if (num_histograms <= 1) {
82    for (i = 0; i < length; ++i) {
83      block_id[i] = 0;
84    }
85    return 1;
86  }
87  memset(insert_cost, 0, sizeof(insert_cost[0]) * data_size * num_histograms);
88  for (i = 0; i < num_histograms; ++i) {
89    insert_cost[i] = FastLog2((uint32_t)histograms[i].total_count_);
90  }
91  for (i = data_size; i != 0;) {
92    --i;
93    for (j = 0; j < num_histograms; ++j) {
94      insert_cost[i * num_histograms + j] =
95          insert_cost[j] - BitCost(histograms[j].data_[i]);
96    }
97  }
98  memset(cost, 0, sizeof(cost[0]) * num_histograms);
99  memset(switch_signal, 0, sizeof(switch_signal[0]) * length * bitmaplen);
100  /* After each iteration of this loop, cost[k] will contain the difference
101     between the minimum cost of arriving at the current byte position using
102     entropy code k, and the minimum cost of arriving at the current byte
103     position. This difference is capped at the block switch cost, and if it
104     reaches block switch cost, it means that when we trace back from the last
105     position, we need to switch here. */
106  for (i = 0; i < length; ++i) {
107    const size_t byte_ix = i;
108    size_t ix = byte_ix * bitmaplen;
109    size_t insert_cost_ix = data[byte_ix] * num_histograms;
110    double min_cost = 1e99;
111    double block_switch_cost = block_switch_bitcost;
112    size_t k;
113    for (k = 0; k < num_histograms; ++k) {
114      /* We are coding the symbol in data[byte_ix] with entropy code k. */
115      cost[k] += insert_cost[insert_cost_ix + k];
116      if (cost[k] < min_cost) {
117        min_cost = cost[k];
118        block_id[byte_ix] = (uint8_t)k;
119      }
120    }
121    /* More blocks for the beginning. */
122    if (byte_ix < 2000) {
123      block_switch_cost *= 0.77 + 0.07 * (double)byte_ix / 2000;
124    }
125    for (k = 0; k < num_histograms; ++k) {
126      cost[k] -= min_cost;
127      if (cost[k] >= block_switch_cost) {
128        const uint8_t mask = (uint8_t)(1u << (k & 7));
129        cost[k] = block_switch_cost;
130        assert((k >> 3) < bitmaplen);
131        switch_signal[ix + (k >> 3)] |= mask;
132      }
133    }
134  }
135  {  /* Trace back from the last position and switch at the marked places. */
136    size_t byte_ix = length - 1;
137    size_t ix = byte_ix * bitmaplen;
138    uint8_t cur_id = block_id[byte_ix];
139    while (byte_ix > 0) {
140      const uint8_t mask = (uint8_t)(1u << (cur_id & 7));
141      assert(((size_t)cur_id >> 3) < bitmaplen);
142      --byte_ix;
143      ix -= bitmaplen;
144      if (switch_signal[ix + (cur_id >> 3)] & mask) {
145        if (cur_id != block_id[byte_ix]) {
146          cur_id = block_id[byte_ix];
147          ++num_blocks;
148        }
149      }
150      block_id[byte_ix] = cur_id;
151    }
152  }
153  return num_blocks;
154}
155
156static size_t FN(RemapBlockIds)(uint8_t* block_ids, const size_t length,
157                                uint16_t* new_id, const size_t num_histograms) {
158  static const uint16_t kInvalidId = 256;
159  uint16_t next_id = 0;
160  size_t i;
161  for (i = 0; i < num_histograms; ++i) {
162    new_id[i] = kInvalidId;
163  }
164  for (i = 0; i < length; ++i) {
165    assert(block_ids[i] < num_histograms);
166    if (new_id[block_ids[i]] == kInvalidId) {
167      new_id[block_ids[i]] = next_id++;
168    }
169  }
170  for (i = 0; i < length; ++i) {
171    block_ids[i] = (uint8_t)new_id[block_ids[i]];
172    assert(block_ids[i] < num_histograms);
173  }
174  assert(next_id <= num_histograms);
175  return next_id;
176}
177
178static void FN(BuildBlockHistograms)(const DataType* data, const size_t length,
179                                     const uint8_t* block_ids,
180                                     const size_t num_histograms,
181                                     HistogramType* histograms) {
182  size_t i;
183  FN(ClearHistograms)(histograms, num_histograms);
184  for (i = 0; i < length; ++i) {
185    FN(HistogramAdd)(&histograms[block_ids[i]], data[i]);
186  }
187}
188
189static void FN(ClusterBlocks)(MemoryManager* m,
190                              const DataType* data, const size_t length,
191                              const size_t num_blocks,
192                              uint8_t* block_ids,
193                              BlockSplit* split) {
194  uint32_t* histogram_symbols = BROTLI_ALLOC(m, uint32_t, num_blocks);
195  uint32_t* block_lengths = BROTLI_ALLOC(m, uint32_t, num_blocks);
196  const size_t expected_num_clusters = CLUSTERS_PER_BATCH *
197      (num_blocks + HISTOGRAMS_PER_BATCH - 1) / HISTOGRAMS_PER_BATCH;
198  size_t all_histograms_size = 0;
199  size_t all_histograms_capacity = expected_num_clusters;
200  HistogramType* all_histograms =
201      BROTLI_ALLOC(m, HistogramType, all_histograms_capacity);
202  size_t cluster_size_size = 0;
203  size_t cluster_size_capacity = expected_num_clusters;
204  uint32_t* cluster_size = BROTLI_ALLOC(m, uint32_t, cluster_size_capacity);
205  size_t num_clusters = 0;
206  HistogramType* histograms = BROTLI_ALLOC(m, HistogramType,
207      BROTLI_MIN(size_t, num_blocks, HISTOGRAMS_PER_BATCH));
208  size_t max_num_pairs =
209      HISTOGRAMS_PER_BATCH * HISTOGRAMS_PER_BATCH / 2;
210  size_t pairs_capacity = max_num_pairs + 1;
211  HistogramPair* pairs = BROTLI_ALLOC(m, HistogramPair, pairs_capacity);
212  size_t pos = 0;
213  uint32_t* clusters;
214  size_t num_final_clusters;
215  static const uint32_t kInvalidIndex = BROTLI_UINT32_MAX;
216  uint32_t* new_index;
217  size_t i;
218  uint32_t sizes[HISTOGRAMS_PER_BATCH] = { 0 };
219  uint32_t new_clusters[HISTOGRAMS_PER_BATCH] = { 0 };
220  uint32_t symbols[HISTOGRAMS_PER_BATCH] = { 0 };
221  uint32_t remap[HISTOGRAMS_PER_BATCH] = { 0 };
222
223  if (BROTLI_IS_OOM(m)) return;
224
225  memset(block_lengths, 0, num_blocks * sizeof(uint32_t));
226
227  {
228    size_t block_idx = 0;
229    for (i = 0; i < length; ++i) {
230      assert(block_idx < num_blocks);
231      ++block_lengths[block_idx];
232      if (i + 1 == length || block_ids[i] != block_ids[i + 1]) {
233        ++block_idx;
234      }
235    }
236    assert(block_idx == num_blocks);
237  }
238
239  for (i = 0; i < num_blocks; i += HISTOGRAMS_PER_BATCH) {
240    const size_t num_to_combine =
241        BROTLI_MIN(size_t, num_blocks - i, HISTOGRAMS_PER_BATCH);
242    size_t num_new_clusters;
243    size_t j;
244    for (j = 0; j < num_to_combine; ++j) {
245      size_t k;
246      FN(HistogramClear)(&histograms[j]);
247      for (k = 0; k < block_lengths[i + j]; ++k) {
248        FN(HistogramAdd)(&histograms[j], data[pos++]);
249      }
250      histograms[j].bit_cost_ = FN(BrotliPopulationCost)(&histograms[j]);
251      new_clusters[j] = (uint32_t)j;
252      symbols[j] = (uint32_t)j;
253      sizes[j] = 1;
254    }
255    num_new_clusters = FN(BrotliHistogramCombine)(
256        histograms, sizes, symbols, new_clusters, pairs, num_to_combine,
257        num_to_combine, HISTOGRAMS_PER_BATCH, max_num_pairs);
258    BROTLI_ENSURE_CAPACITY(m, HistogramType, all_histograms,
259        all_histograms_capacity, all_histograms_size + num_new_clusters);
260    BROTLI_ENSURE_CAPACITY(m, uint32_t, cluster_size,
261        cluster_size_capacity, cluster_size_size + num_new_clusters);
262    if (BROTLI_IS_OOM(m)) return;
263    for (j = 0; j < num_new_clusters; ++j) {
264      all_histograms[all_histograms_size++] = histograms[new_clusters[j]];
265      cluster_size[cluster_size_size++] = sizes[new_clusters[j]];
266      remap[new_clusters[j]] = (uint32_t)j;
267    }
268    for (j = 0; j < num_to_combine; ++j) {
269      histogram_symbols[i + j] = (uint32_t)num_clusters + remap[symbols[j]];
270    }
271    num_clusters += num_new_clusters;
272    assert(num_clusters == cluster_size_size);
273    assert(num_clusters == all_histograms_size);
274  }
275  BROTLI_FREE(m, histograms);
276
277  max_num_pairs =
278      BROTLI_MIN(size_t, 64 * num_clusters, (num_clusters / 2) * num_clusters);
279  if (pairs_capacity < max_num_pairs + 1) {
280    BROTLI_FREE(m, pairs);
281    pairs = BROTLI_ALLOC(m, HistogramPair, max_num_pairs + 1);
282    if (BROTLI_IS_OOM(m)) return;
283  }
284
285  clusters = BROTLI_ALLOC(m, uint32_t, num_clusters);
286  if (BROTLI_IS_OOM(m)) return;
287  for (i = 0; i < num_clusters; ++i) {
288    clusters[i] = (uint32_t)i;
289  }
290  num_final_clusters = FN(BrotliHistogramCombine)(
291      all_histograms, cluster_size, histogram_symbols, clusters, pairs,
292      num_clusters, num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES,
293      max_num_pairs);
294  BROTLI_FREE(m, pairs);
295  BROTLI_FREE(m, cluster_size);
296
297  new_index = BROTLI_ALLOC(m, uint32_t, num_clusters);
298  if (BROTLI_IS_OOM(m)) return;
299  for (i = 0; i < num_clusters; ++i) new_index[i] = kInvalidIndex;
300  pos = 0;
301  {
302    uint32_t next_index = 0;
303    for (i = 0; i < num_blocks; ++i) {
304      HistogramType histo;
305      size_t j;
306      uint32_t best_out;
307      double best_bits;
308      FN(HistogramClear)(&histo);
309      for (j = 0; j < block_lengths[i]; ++j) {
310        FN(HistogramAdd)(&histo, data[pos++]);
311      }
312      best_out = (i == 0) ? histogram_symbols[0] : histogram_symbols[i - 1];
313      best_bits =
314          FN(BrotliHistogramBitCostDistance)(&histo, &all_histograms[best_out]);
315      for (j = 0; j < num_final_clusters; ++j) {
316        const double cur_bits = FN(BrotliHistogramBitCostDistance)(
317            &histo, &all_histograms[clusters[j]]);
318        if (cur_bits < best_bits) {
319          best_bits = cur_bits;
320          best_out = clusters[j];
321        }
322      }
323      histogram_symbols[i] = best_out;
324      if (new_index[best_out] == kInvalidIndex) {
325        new_index[best_out] = next_index++;
326      }
327    }
328  }
329  BROTLI_FREE(m, clusters);
330  BROTLI_FREE(m, all_histograms);
331  BROTLI_ENSURE_CAPACITY(
332      m, uint8_t, split->types, split->types_alloc_size, num_blocks);
333  BROTLI_ENSURE_CAPACITY(
334      m, uint32_t, split->lengths, split->lengths_alloc_size, num_blocks);
335  if (BROTLI_IS_OOM(m)) return;
336  {
337    uint32_t cur_length = 0;
338    size_t block_idx = 0;
339    uint8_t max_type = 0;
340    for (i = 0; i < num_blocks; ++i) {
341      cur_length += block_lengths[i];
342      if (i + 1 == num_blocks ||
343          histogram_symbols[i] != histogram_symbols[i + 1]) {
344        const uint8_t id = (uint8_t)new_index[histogram_symbols[i]];
345        split->types[block_idx] = id;
346        split->lengths[block_idx] = cur_length;
347        max_type = BROTLI_MAX(uint8_t, max_type, id);
348        cur_length = 0;
349        ++block_idx;
350      }
351    }
352    split->num_blocks = block_idx;
353    split->num_types = (size_t)max_type + 1;
354  }
355  BROTLI_FREE(m, new_index);
356  BROTLI_FREE(m, block_lengths);
357  BROTLI_FREE(m, histogram_symbols);
358}
359
360static void FN(SplitByteVector)(MemoryManager* m,
361                                const DataType* data, const size_t length,
362                                const size_t literals_per_histogram,
363                                const size_t max_histograms,
364                                const size_t sampling_stride_length,
365                                const double block_switch_cost,
366                                const BrotliEncoderParams* params,
367                                BlockSplit* split) {
368  const size_t data_size = FN(HistogramDataSize)();
369  size_t num_histograms = length / literals_per_histogram + 1;
370  HistogramType* histograms;
371  if (num_histograms > max_histograms) {
372    num_histograms = max_histograms;
373  }
374  if (length == 0) {
375    split->num_types = 1;
376    return;
377  } else if (length < kMinLengthForBlockSplitting) {
378    BROTLI_ENSURE_CAPACITY(m, uint8_t,
379        split->types, split->types_alloc_size, split->num_blocks + 1);
380    BROTLI_ENSURE_CAPACITY(m, uint32_t,
381        split->lengths, split->lengths_alloc_size, split->num_blocks + 1);
382    if (BROTLI_IS_OOM(m)) return;
383    split->num_types = 1;
384    split->types[split->num_blocks] = 0;
385    split->lengths[split->num_blocks] = (uint32_t)length;
386    split->num_blocks++;
387    return;
388  }
389  histograms = BROTLI_ALLOC(m, HistogramType, num_histograms);
390  if (BROTLI_IS_OOM(m)) return;
391  /* Find good entropy codes. */
392  FN(InitialEntropyCodes)(data, length,
393                          sampling_stride_length,
394                          num_histograms, histograms);
395  FN(RefineEntropyCodes)(data, length,
396                         sampling_stride_length,
397                         num_histograms, histograms);
398  {
399    /* Find a good path through literals with the good entropy codes. */
400    uint8_t* block_ids = BROTLI_ALLOC(m, uint8_t, length);
401    size_t num_blocks = 0;
402    const size_t bitmaplen = (num_histograms + 7) >> 3;
403    double* insert_cost = BROTLI_ALLOC(m, double, data_size * num_histograms);
404    double* cost = BROTLI_ALLOC(m, double, num_histograms);
405    uint8_t* switch_signal = BROTLI_ALLOC(m, uint8_t, length * bitmaplen);
406    uint16_t* new_id = BROTLI_ALLOC(m, uint16_t, num_histograms);
407    const size_t iters = params->quality < HQ_ZOPFLIFICATION_QUALITY ? 3 : 10;
408    size_t i;
409    if (BROTLI_IS_OOM(m)) return;
410    for (i = 0; i < iters; ++i) {
411      num_blocks = FN(FindBlocks)(data, length,
412                                  block_switch_cost,
413                                  num_histograms, histograms,
414                                  insert_cost, cost, switch_signal,
415                                  block_ids);
416      num_histograms = FN(RemapBlockIds)(block_ids, length,
417                                         new_id, num_histograms);
418      FN(BuildBlockHistograms)(data, length, block_ids,
419                               num_histograms, histograms);
420    }
421    BROTLI_FREE(m, insert_cost);
422    BROTLI_FREE(m, cost);
423    BROTLI_FREE(m, switch_signal);
424    BROTLI_FREE(m, new_id);
425    BROTLI_FREE(m, histograms);
426    FN(ClusterBlocks)(m, data, length, num_blocks, block_ids, split);
427    if (BROTLI_IS_OOM(m)) return;
428    BROTLI_FREE(m, block_ids);
429  }
430}
431
432#undef HistogramType
433