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

   1 /* NOLINT(build/header_guard) */
   2 /* Copyright 2015 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 */
   9
  10 #define HistogramType FN(Histogram)
  11
  12 /* Greedy block splitter for one block category (literal, command or distance).
  13 */
  14 typedef struct FN(BlockSplitter) {
  15   /* Alphabet size of particular block category. */
  16   size_t alphabet_size_;
  17   /* We collect at least this many symbols for each block. */
  18   size_t min_block_size_;
  19   /* We merge histograms A and B if
  20        entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,
  21      where A is the current histogram and B is the histogram of the last or the
  22      second last block type. */
  23   double split_threshold_;
  24
  25   size_t num_blocks_;
  26   BlockSplit* split_;  /* not owned */
  27   HistogramType* histograms_;  /* not owned */
  28   size_t* histograms_size_;  /* not owned */
  29
  30   /* The number of symbols that we want to collect before deciding on whether
  31      or not to merge the block with a previous one or emit a new block. */
  32   size_t target_block_size_;
  33   /* The number of symbols in the current histogram. */
  34   size_t block_size_;
  35   /* Offset of the current histogram. */
  36   size_t curr_histogram_ix_;
  37   /* Offset of the histograms of the previous two block types. */
  38   size_t last_histogram_ix_[2];
  39   /* Entropy of the previous two block types. */
  40   double last_entropy_[2];
  41   /* The number of times we merged the current block with the last one. */
  42   size_t merge_last_count_;
  43 } FN(BlockSplitter);
  44
  45 static void FN(InitBlockSplitter)(
  46     MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,
  47     size_t min_block_size, double split_threshold, size_t num_symbols,
  48     BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {
  49   size_t max_num_blocks = num_symbols / min_block_size + 1;
  50   /* We have to allocate one more histogram than the maximum number of block
  51      types for the current histogram when the meta-block is too big. */
  52   size_t max_num_types =
  53       BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);
  54   self->alphabet_size_ = alphabet_size;
  55   self->min_block_size_ = min_block_size;
  56   self->split_threshold_ = split_threshold;
  57   self->num_blocks_ = 0;
  58   self->split_ = split;
  59   self->histograms_size_ = histograms_size;
  60   self->target_block_size_ = min_block_size;
  61   self->block_size_ = 0;
  62   self->curr_histogram_ix_ = 0;
  63   self->merge_last_count_ = 0;
  64   BROTLI_ENSURE_CAPACITY(m, uint8_t,
  65       split->types, split->types_alloc_size, max_num_blocks);
  66   BROTLI_ENSURE_CAPACITY(m, uint32_t,
  67       split->lengths, split->lengths_alloc_size, max_num_blocks);
  68   if (BROTLI_IS_OOM(m)) return;
  69   self->split_->num_blocks = max_num_blocks;
  70   assert(*histograms == 0);
  71   *histograms_size = max_num_types;
  72   *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size);
  73   self->histograms_ = *histograms;
  74   if (BROTLI_IS_OOM(m)) return;
  75   /* Clear only current histogram. */
  76   FN(HistogramClear)(&self->histograms_[0]);
  77   self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;
  78 }
  79
  80 /* Does either of three things:
  81      (1) emits the current block with a new block type;
  82      (2) emits the current block with the type of the second last block;
  83      (3) merges the current block with the last block. */
  84 static void FN(BlockSplitterFinishBlock)(
  85     FN(BlockSplitter)* self, BROTLI_BOOL is_final) {
  86   BlockSplit* split = self->split_;
  87   double* last_entropy = self->last_entropy_;
  88   HistogramType* histograms = self->histograms_;
  89   self->block_size_ =
  90       BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);
  91   if (self->num_blocks_ == 0) {
  92     /* Create first block. */
  93     split->lengths[0] = (uint32_t)self->block_size_;
  94     split->types[0] = 0;
  95     last_entropy[0] =
  96         BitsEntropy(histograms[0].data_, self->alphabet_size_);
  97     last_entropy[1] = last_entropy[0];
  98     ++self->num_blocks_;
  99     ++split->num_types;
 100     ++self->curr_histogram_ix_;
 101     if (self->curr_histogram_ix_ < *self->histograms_size_)
 102       FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
 103     self->block_size_ = 0;
 104   } else if (self->block_size_ > 0) {
 105     double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,
 106                                  self->alphabet_size_);
 107     HistogramType combined_histo[2];
 108     double combined_entropy[2];
 109     double diff[2];
 110     size_t j;
 111     for (j = 0; j < 2; ++j) {
 112       size_t last_histogram_ix = self->last_histogram_ix_[j];
 113       combined_histo[j] = histograms[self->curr_histogram_ix_];
 114       FN(HistogramAddHistogram)(&combined_histo[j],
 115           &histograms[last_histogram_ix]);
 116       combined_entropy[j] = BitsEntropy(
 117           &combined_histo[j].data_[0], self->alphabet_size_);
 118       diff[j] = combined_entropy[j] - entropy - last_entropy[j];
 119     }
 120
 121     if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&
 122         diff[0] > self->split_threshold_ &&
 123         diff[1] > self->split_threshold_) {
 124       /* Create new block. */
 125       split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
 126       split->types[self->num_blocks_] = (uint8_t)split->num_types;
 127       self->last_histogram_ix_[1] = self->last_histogram_ix_[0];
 128       self->last_histogram_ix_[0] = (uint8_t)split->num_types;
 129       last_entropy[1] = last_entropy[0];
 130       last_entropy[0] = entropy;
 131       ++self->num_blocks_;
 132       ++split->num_types;
 133       ++self->curr_histogram_ix_;
 134       if (self->curr_histogram_ix_ < *self->histograms_size_)
 135         FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
 136       self->block_size_ = 0;
 137       self->merge_last_count_ = 0;
 138       self->target_block_size_ = self->min_block_size_;
 139     } else if (diff[1] < diff[0] - 20.0) {
 140       /* Combine this block with second last block. */
 141       split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
 142       split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];
 143       BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);
 144       histograms[self->last_histogram_ix_[0]] = combined_histo[1];
 145       last_entropy[1] = last_entropy[0];
 146       last_entropy[0] = combined_entropy[1];
 147       ++self->num_blocks_;
 148       self->block_size_ = 0;
 149       FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
 150       self->merge_last_count_ = 0;
 151       self->target_block_size_ = self->min_block_size_;
 152     } else {
 153       /* Combine this block with last block. */
 154       split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;
 155       histograms[self->last_histogram_ix_[0]] = combined_histo[0];
 156       last_entropy[0] = combined_entropy[0];
 157       if (split->num_types == 1) {
 158         last_entropy[1] = last_entropy[0];
 159       }
 160       self->block_size_ = 0;
 161       FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);
 162       if (++self->merge_last_count_ > 1) {
 163         self->target_block_size_ += self->min_block_size_;
 164       }
 165     }
 166   }
 167   if (is_final) {
 168     *self->histograms_size_ = split->num_types;
 169     split->num_blocks = self->num_blocks_;
 170   }
 171 }
 172
 173 /* Adds the next symbol to the current histogram. When the current histogram
 174    reaches the target size, decides on merging the block. */
 175 static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {
 176   FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);
 177   ++self->block_size_;
 178   if (self->block_size_ == self->target_block_size_) {
 179     FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);
 180   }
 181 }
 182
 183 #undef HistogramType