BaseTools/Source/C/BrotliCompress/enc/block_splitter_inc.h

   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
  12 static 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
  32 static 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
  47 static 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, vec.size()) 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. */
  67 static 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
 156 static 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
 178 static 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
 189 static 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   uint8_t max_type = 0;
 218   size_t i;
 219   uint32_t sizes[HISTOGRAMS_PER_BATCH] = { 0 };
 220   uint32_t new_clusters[HISTOGRAMS_PER_BATCH] = { 0 };
 221   uint32_t symbols[HISTOGRAMS_PER_BATCH] = { 0 };
 222   uint32_t remap[HISTOGRAMS_PER_BATCH] = { 0 };
 223
 224   if (BROTLI_IS_OOM(m)) return;
 225
 226   memset(block_lengths, 0, num_blocks * sizeof(uint32_t));
 227
 228   {
 229     size_t block_idx = 0;
 230     for (i = 0; i < length; ++i) {
 231       assert(block_idx < num_blocks);
 232       ++block_lengths[block_idx];
 233       if (i + 1 == length || block_ids[i] != block_ids[i + 1]) {
 234         ++block_idx;
 235       }
 236     }
 237     assert(block_idx == num_blocks);
 238   }
 239
 240   for (i = 0; i < num_blocks; i += HISTOGRAMS_PER_BATCH) {
 241     const size_t num_to_combine =
 242         BROTLI_MIN(size_t, num_blocks - i, HISTOGRAMS_PER_BATCH);
 243     size_t num_new_clusters;
 244     size_t j;
 245     for (j = 0; j < num_to_combine; ++j) {
 246       size_t k;
 247       FN(HistogramClear)(&histograms[j]);
 248       for (k = 0; k < block_lengths[i + j]; ++k) {
 249         FN(HistogramAdd)(&histograms[j], data[pos++]);
 250       }
 251       histograms[j].bit_cost_ = FN(BrotliPopulationCost)(&histograms[j]);
 252       new_clusters[j] = (uint32_t)j;
 253       symbols[j] = (uint32_t)j;
 254       sizes[j] = 1;
 255     }
 256     num_new_clusters = FN(BrotliHistogramCombine)(
 257         histograms, sizes, symbols, new_clusters, pairs, num_to_combine,
 258         num_to_combine, HISTOGRAMS_PER_BATCH, max_num_pairs);
 259     BROTLI_ENSURE_CAPACITY(m, HistogramType, all_histograms,
 260         all_histograms_capacity, all_histograms_size + num_new_clusters);
 261     BROTLI_ENSURE_CAPACITY(m, uint32_t, cluster_size,
 262         cluster_size_capacity, cluster_size_size + num_new_clusters);
 263     if (BROTLI_IS_OOM(m)) return;
 264     for (j = 0; j < num_new_clusters; ++j) {
 265       all_histograms[all_histograms_size++] = histograms[new_clusters[j]];
 266       cluster_size[cluster_size_size++] = sizes[new_clusters[j]];
 267       remap[new_clusters[j]] = (uint32_t)j;
 268     }
 269     for (j = 0; j < num_to_combine; ++j) {
 270       histogram_symbols[i + j] = (uint32_t)num_clusters + remap[symbols[j]];
 271     }
 272     num_clusters += num_new_clusters;
 273     assert(num_clusters == cluster_size_size);
 274     assert(num_clusters == all_histograms_size);
 275   }
 276   BROTLI_FREE(m, histograms);
 277
 278   max_num_pairs =
 279       BROTLI_MIN(size_t, 64 * num_clusters, (num_clusters / 2) * num_clusters);
 280   if (pairs_capacity < max_num_pairs + 1) {
 281     BROTLI_FREE(m, pairs);
 282     pairs = BROTLI_ALLOC(m, HistogramPair, max_num_pairs + 1);
 283     if (BROTLI_IS_OOM(m)) return;
 284   }
 285
 286   clusters = BROTLI_ALLOC(m, uint32_t, num_clusters);
 287   if (BROTLI_IS_OOM(m)) return;
 288   for (i = 0; i < num_clusters; ++i) {
 289     clusters[i] = (uint32_t)i;
 290   }
 291   num_final_clusters = FN(BrotliHistogramCombine)(
 292       all_histograms, cluster_size, histogram_symbols, clusters, pairs,
 293       num_clusters, num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES,
 294       max_num_pairs);
 295   BROTLI_FREE(m, pairs);
 296   BROTLI_FREE(m, cluster_size);
 297
 298   new_index = BROTLI_ALLOC(m, uint32_t, num_clusters);
 299   if (BROTLI_IS_OOM(m)) return;
 300   for (i = 0; i < num_clusters; ++i) new_index[i] = kInvalidIndex;
 301   pos = 0;
 302   {
 303     uint32_t next_index = 0;
 304     for (i = 0; i < num_blocks; ++i) {
 305       HistogramType histo;
 306       size_t j;
 307       uint32_t best_out;
 308       double best_bits;
 309       FN(HistogramClear)(&histo);
 310       for (j = 0; j < block_lengths[i]; ++j) {
 311         FN(HistogramAdd)(&histo, data[pos++]);
 312       }
 313       best_out = (i == 0) ? histogram_symbols[0] : histogram_symbols[i - 1];
 314       best_bits =
 315           FN(BrotliHistogramBitCostDistance)(&histo, &all_histograms[best_out]);
 316       for (j = 0; j < num_final_clusters; ++j) {
 317         const double cur_bits = FN(BrotliHistogramBitCostDistance)(
 318             &histo, &all_histograms[clusters[j]]);
 319         if (cur_bits < best_bits) {
 320           best_bits = cur_bits;
 321           best_out = clusters[j];
 322         }
 323       }
 324       histogram_symbols[i] = best_out;
 325       if (new_index[best_out] == kInvalidIndex) {
 326         new_index[best_out] = next_index++;
 327       }
 328     }
 329   }
 330   BROTLI_FREE(m, clusters);
 331   BROTLI_FREE(m, all_histograms);
 332   BROTLI_ENSURE_CAPACITY(
 333       m, uint8_t, split->types, split->types_alloc_size, num_blocks);
 334   BROTLI_ENSURE_CAPACITY(
 335       m, uint32_t, split->lengths, split->lengths_alloc_size, num_blocks);
 336   if (BROTLI_IS_OOM(m)) return;
 337   {
 338     uint32_t cur_length = 0;
 339     size_t block_idx = 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
 360 static 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;
 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