BaseTools: Copy Brotli algorithm 3rd party source code for tool

[mirror_edk2.git] / BaseTools / Source / C / BrotliCompress / enc / metablock_inc.h

/* NOLINT(build/header_guard) */\r
/* Copyright 2015 Google Inc. All Rights Reserved.\r
\r
   Distributed under MIT license.\r
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
*/\r
\r
/* template parameters: FN */\r
\r
#define HistogramType FN(Histogram)\r
\r
/* Greedy block splitter for one block category (literal, command or distance).\r
*/\r
typedef struct FN(BlockSplitter) {\r
  /* Alphabet size of particular block category. */\r
  size_t alphabet_size_;\r
  /* We collect at least this many symbols for each block. */\r
  size_t min_block_size_;\r
  /* We merge histograms A and B if\r
       entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,\r
     where A is the current histogram and B is the histogram of the last or the\r
     second last block type. */\r
  double split_threshold_;\r
\r
  size_t num_blocks_;\r
  BlockSplit* split_;  /* not owned */\r
  HistogramType* histograms_;  /* not owned */\r
  size_t* histograms_size_;  /* not owned */\r
\r
  /* The number of symbols that we want to collect before deciding on whether\r
     or not to merge the block with a previous one or emit a new block. */\r
  size_t target_block_size_;\r
  /* The number of symbols in the current histogram. */\r
  size_t block_size_;\r
  /* Offset of the current histogram. */\r
  size_t curr_histogram_ix_;\r
  /* Offset of the histograms of the previous two block types. */\r
  size_t last_histogram_ix_[2];\r
  /* Entropy of the previous two block types. */\r
  double last_entropy_[2];\r
  /* The number of times we merged the current block with the last one. */\r
  size_t merge_last_count_;\r
} FN(BlockSplitter);\r
\r
static void FN(InitBlockSplitter)(\r
    MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,\r
    size_t min_block_size, double split_threshold, size_t num_symbols,\r
    BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {\r
  size_t max_num_blocks = num_symbols / min_block_size + 1;\r
  /* We have to allocate one more histogram than the maximum number of block\r
     types for the current histogram when the meta-block is too big. */\r
  size_t max_num_types =\r
      BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);\r
  self->alphabet_size_ = alphabet_size;\r
  self->min_block_size_ = min_block_size;\r
  self->split_threshold_ = split_threshold;\r
  self->num_blocks_ = 0;\r
  self->split_ = split;\r
  self->histograms_size_ = histograms_size;\r
  self->target_block_size_ = min_block_size;\r
  self->block_size_ = 0;\r
  self->curr_histogram_ix_ = 0;\r
  self->merge_last_count_ = 0;\r
  BROTLI_ENSURE_CAPACITY(m, uint8_t,\r
      split->types, split->types_alloc_size, max_num_blocks);\r
  BROTLI_ENSURE_CAPACITY(m, uint32_t,\r
      split->lengths, split->lengths_alloc_size, max_num_blocks);\r
  if (BROTLI_IS_OOM(m)) return;\r
  self->split_->num_blocks = max_num_blocks;\r
  assert(*histograms == 0);\r
  *histograms_size = max_num_types;\r
  *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size);\r
  self->histograms_ = *histograms;\r
  if (BROTLI_IS_OOM(m)) return;\r
  /* Clear only current histogram. */\r
  FN(HistogramClear)(&self->histograms_[0]);\r
  self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;\r
}\r
\r
/* Does either of three things:\r
     (1) emits the current block with a new block type;\r
     (2) emits the current block with the type of the second last block;\r
     (3) merges the current block with the last block. */\r
static void FN(BlockSplitterFinishBlock)(\r
    FN(BlockSplitter)* self, BROTLI_BOOL is_final) {\r
  BlockSplit* split = self->split_;\r
  double* last_entropy = self->last_entropy_;\r
  HistogramType* histograms = self->histograms_;\r
  self->block_size_ =\r
      BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);\r
  if (self->num_blocks_ == 0) {\r
    /* Create first block. */\r
    split->lengths[0] = (uint32_t)self->block_size_;\r
    split->types[0] = 0;\r
    last_entropy[0] =\r
        BitsEntropy(histograms[0].data_, self->alphabet_size_);\r
    last_entropy[1] = last_entropy[0];\r
    ++self->num_blocks_;\r
    ++split->num_types;\r
    ++self->curr_histogram_ix_;\r
    if (self->curr_histogram_ix_ < *self->histograms_size_)\r
      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);\r
    self->block_size_ = 0;\r
  } else if (self->block_size_ > 0) {\r
    double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,\r
                                 self->alphabet_size_);\r
    HistogramType combined_histo[2];\r
    double combined_entropy[2];\r
    double diff[2];\r
    size_t j;\r
    for (j = 0; j < 2; ++j) {\r
      size_t last_histogram_ix = self->last_histogram_ix_[j];\r
      combined_histo[j] = histograms[self->curr_histogram_ix_];\r
      FN(HistogramAddHistogram)(&combined_histo[j],\r
          &histograms[last_histogram_ix]);\r
      combined_entropy[j] = BitsEntropy(\r
          &combined_histo[j].data_[0], self->alphabet_size_);\r
      diff[j] = combined_entropy[j] - entropy - last_entropy[j];\r
    }\r
\r
    if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&\r
        diff[0] > self->split_threshold_ &&\r
        diff[1] > self->split_threshold_) {\r
      /* Create new block. */\r
      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;\r
      split->types[self->num_blocks_] = (uint8_t)split->num_types;\r
      self->last_histogram_ix_[1] = self->last_histogram_ix_[0];\r
      self->last_histogram_ix_[0] = (uint8_t)split->num_types;\r
      last_entropy[1] = last_entropy[0];\r
      last_entropy[0] = entropy;\r
      ++self->num_blocks_;\r
      ++split->num_types;\r
      ++self->curr_histogram_ix_;\r
      if (self->curr_histogram_ix_ < *self->histograms_size_)\r
        FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);\r
      self->block_size_ = 0;\r
      self->merge_last_count_ = 0;\r
      self->target_block_size_ = self->min_block_size_;\r
    } else if (diff[1] < diff[0] - 20.0) {\r
      /* Combine this block with second last block. */\r
      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;\r
      split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];\r
      BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);\r
      histograms[self->last_histogram_ix_[0]] = combined_histo[1];\r
      last_entropy[1] = last_entropy[0];\r
      last_entropy[0] = combined_entropy[1];\r
      ++self->num_blocks_;\r
      self->block_size_ = 0;\r
      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);\r
      self->merge_last_count_ = 0;\r
      self->target_block_size_ = self->min_block_size_;\r
    } else {\r
      /* Combine this block with last block. */\r
      split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;\r
      histograms[self->last_histogram_ix_[0]] = combined_histo[0];\r
      last_entropy[0] = combined_entropy[0];\r
      if (split->num_types == 1) {\r
        last_entropy[1] = last_entropy[0];\r
      }\r
      self->block_size_ = 0;\r
      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);\r
      if (++self->merge_last_count_ > 1) {\r
        self->target_block_size_ += self->min_block_size_;\r
      }\r
    }\r
  }\r
  if (is_final) {\r
    *self->histograms_size_ = split->num_types;\r
    split->num_blocks = self->num_blocks_;\r
  }\r
}\r
\r
/* Adds the next symbol to the current histogram. When the current histogram\r
   reaches the target size, decides on merging the block. */\r
static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {\r
  FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);\r
  ++self->block_size_;\r
  if (self->block_size_ == self->target_block_size_) {\r
    FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);\r
  }\r
}\r
\r
#undef HistogramType\r