/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.

   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT

*/

/* Algorithms for distributing the literals and commands of a metablock between

   block types and contexts. */

#include "metablock.h"

#include <brotli/types.h>

#include "../common/brotli_constants.h"

#include "../common/context.h"

#include "../common/brotli_platform.h"

#include "bit_cost.h"

#include "block_splitter.h"

#include "cluster.h"

#include "entropy_encode.h"

#include "histogram.h"

#include "memory.h"

#include "quality.h"

using namespace duckdb_brotli;

void duckdb_brotli::BrotliInitDistanceParams(BrotliDistanceParams* dist_params,

    uint32_t npostfix, uint32_t ndirect, BROTLI_BOOL large_window) {

  uint32_t alphabet_size_max;

  uint32_t alphabet_size_limit;

  uint32_t max_distance;

  dist_params->distance_postfix_bits = npostfix;

  dist_params->num_direct_distance_codes = ndirect;

  alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE(

      npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS);

  alphabet_size_limit = alphabet_size_max;

  max_distance = ndirect + (1U << (BROTLI_MAX_DISTANCE_BITS + npostfix + 2)) -

      (1U << (npostfix + 2));

  if (large_window) {

    BrotliDistanceCodeLimit limit = BrotliCalculateDistanceCodeLimit(

        BROTLI_MAX_ALLOWED_DISTANCE, npostfix, ndirect);

    alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE(

        npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS);

    alphabet_size_limit = limit.max_alphabet_size;

    max_distance = limit.max_distance;

  }

  dist_params->alphabet_size_max = alphabet_size_max;

  dist_params->alphabet_size_limit = alphabet_size_limit;

  dist_params->max_distance = max_distance;

}

static void RecomputeDistancePrefixes(Command* cmds,

                                      size_t num_commands,

                                      const BrotliDistanceParams* orig_params,

                                      const BrotliDistanceParams* new_params) {

  size_t i;

  if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits &&

      orig_params->num_direct_distance_codes ==

      new_params->num_direct_distance_codes) {

    return;

  }

  for (i = 0; i < num_commands; ++i) {

    Command* cmd = &cmds[i];

    if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {

      PrefixEncodeCopyDistance(CommandRestoreDistanceCode(cmd, orig_params),

                               new_params->num_direct_distance_codes,

                               new_params->distance_postfix_bits,

                               &cmd->dist_prefix_,

                               &cmd->dist_extra_);

    }

  }

}

static BROTLI_BOOL ComputeDistanceCost(const Command* cmds,

                                       size_t num_commands,

                                       const BrotliDistanceParams* orig_params,

                                       const BrotliDistanceParams* new_params,

                                       double* cost,

                                       HistogramDistance* tmp) {

  size_t i;

  BROTLI_BOOL equal_params = BROTLI_FALSE;

  uint16_t dist_prefix;

  uint32_t dist_extra;

  double extra_bits = 0.0;

  HistogramClearDistance(tmp);

  if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits &&

      orig_params->num_direct_distance_codes ==

      new_params->num_direct_distance_codes) {

    equal_params = BROTLI_TRUE;

  }

  for (i = 0; i < num_commands; i++) {

    const Command* cmd = &cmds[i];

    if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {

      if (equal_params) {

        dist_prefix = cmd->dist_prefix_;

      } else {

        uint32_t distance = CommandRestoreDistanceCode(cmd, orig_params);

        if (distance > new_params->max_distance) {

          return BROTLI_FALSE;

        }

        PrefixEncodeCopyDistance(distance,

                                 new_params->num_direct_distance_codes,

                                 new_params->distance_postfix_bits,

                                 &dist_prefix,

                                 &dist_extra);

      }

      HistogramAddDistance(tmp, dist_prefix & 0x3FF);

      extra_bits += dist_prefix >> 10;

    }

  }

  *cost = BrotliPopulationCostDistance(tmp) + extra_bits;

  return BROTLI_TRUE;

}

void duckdb_brotli::BrotliBuildMetaBlock(MemoryManager* m,

                          const uint8_t* ringbuffer,

                          const size_t pos,

                          const size_t mask,

                          BrotliEncoderParams* params,

                          uint8_t prev_byte,

                          uint8_t prev_byte2,

                          Command* cmds,

                          size_t num_commands,

                          ContextType literal_context_mode,

                          MetaBlockSplit* mb) {

  /* Histogram ids need to fit in one byte. */

  static const size_t kMaxNumberOfHistograms = 256;

  HistogramDistance* distance_histograms;

  HistogramLiteral* literal_histograms;

  ContextType* literal_context_modes = NULL;

  size_t literal_histograms_size;

  size_t distance_histograms_size;

  size_t i;

  size_t literal_context_multiplier = 1;

  uint32_t npostfix;

  uint32_t ndirect_msb = 0;

  BROTLI_BOOL check_orig = BROTLI_TRUE;

  double best_dist_cost = 1e99;

  BrotliDistanceParams orig_params = params->dist;

  BrotliDistanceParams new_params = params->dist;

  HistogramDistance* tmp = BROTLI_ALLOC(m, HistogramDistance, 1);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(tmp)) return;

  for (npostfix = 0; npostfix <= BROTLI_MAX_NPOSTFIX; npostfix++) {

    for (; ndirect_msb < 16; ndirect_msb++) {

      uint32_t ndirect = ndirect_msb << npostfix;

      BROTLI_BOOL skip;

      double dist_cost;

      BrotliInitDistanceParams(&new_params, npostfix, ndirect,

                               params->large_window);

      if (npostfix == orig_params.distance_postfix_bits &&

          ndirect == orig_params.num_direct_distance_codes) {

        check_orig = BROTLI_FALSE;

      }

      skip = !ComputeDistanceCost(

          cmds, num_commands, &orig_params, &new_params, &dist_cost, tmp);

      if (skip || (dist_cost > best_dist_cost)) {

        break;

      }

      best_dist_cost = dist_cost;

      params->dist = new_params;

    }

    if (ndirect_msb > 0) ndirect_msb--;

    ndirect_msb /= 2;

  }

  if (check_orig) {

    double dist_cost;

    ComputeDistanceCost(cmds, num_commands, &orig_params, &orig_params,

                        &dist_cost, tmp);

    if (dist_cost < best_dist_cost) {

      /* NB: currently unused; uncomment when more param tuning is added. */

      /* best_dist_cost = dist_cost; */

      params->dist = orig_params;

    }

  }

  BROTLI_FREE(m, tmp);

  RecomputeDistancePrefixes(cmds, num_commands, &orig_params, &params->dist);

  BrotliSplitBlock(m, cmds, num_commands,

                   ringbuffer, pos, mask, params,

                   &mb->literal_split,

                   &mb->command_split,

                   &mb->distance_split);

  if (BROTLI_IS_OOM(m)) return;

  if (!params->disable_literal_context_modeling) {

    literal_context_multiplier = 1 << BROTLI_LITERAL_CONTEXT_BITS;

    literal_context_modes =

        BROTLI_ALLOC(m, ContextType, mb->literal_split.num_types);

    if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(literal_context_modes)) return;

    for (i = 0; i < mb->literal_split.num_types; ++i) {

      literal_context_modes[i] = literal_context_mode;

    }

  }

  literal_histograms_size =

      mb->literal_split.num_types * literal_context_multiplier;

  literal_histograms =

      BROTLI_ALLOC(m, HistogramLiteral, literal_histograms_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(literal_histograms)) return;

  ClearHistogramsLiteral(literal_histograms, literal_histograms_size);

  distance_histograms_size =

      mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;

  distance_histograms =

      BROTLI_ALLOC(m, HistogramDistance, distance_histograms_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(distance_histograms)) return;

  ClearHistogramsDistance(distance_histograms, distance_histograms_size);

  BROTLI_DCHECK(mb->command_histograms == 0);

  mb->command_histograms_size = mb->command_split.num_types;

  mb->command_histograms =

      BROTLI_ALLOC(m, HistogramCommand, mb->command_histograms_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->command_histograms)) return;

  ClearHistogramsCommand(mb->command_histograms, mb->command_histograms_size);

  BrotliBuildHistogramsWithContext(cmds, num_commands,

      &mb->literal_split, &mb->command_split, &mb->distance_split,

      ringbuffer, pos, mask, prev_byte, prev_byte2, literal_context_modes,

      literal_histograms, mb->command_histograms, distance_histograms);

  BROTLI_FREE(m, literal_context_modes);

  BROTLI_DCHECK(mb->literal_context_map == 0);

  mb->literal_context_map_size =

      mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS;

  mb->literal_context_map =

      BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->literal_context_map)) return;

  BROTLI_DCHECK(mb->literal_histograms == 0);

  mb->literal_histograms_size = mb->literal_context_map_size;

  mb->literal_histograms =

      BROTLI_ALLOC(m, HistogramLiteral, mb->literal_histograms_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->literal_histograms)) return;

  BrotliClusterHistogramsLiteral(m, literal_histograms, literal_histograms_size,

      kMaxNumberOfHistograms, mb->literal_histograms,

      &mb->literal_histograms_size, mb->literal_context_map);

  if (BROTLI_IS_OOM(m)) return;

  BROTLI_FREE(m, literal_histograms);

  if (params->disable_literal_context_modeling) {

    /* Distribute assignment to all contexts. */

    for (i = mb->literal_split.num_types; i != 0;) {

      size_t j = 0;

      i--;

      for (; j < (1 << BROTLI_LITERAL_CONTEXT_BITS); j++) {

        mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] =

            mb->literal_context_map[i];

      }

    }

  }

  BROTLI_DCHECK(mb->distance_context_map == 0);

  mb->distance_context_map_size =

      mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;

  mb->distance_context_map =

      BROTLI_ALLOC(m, uint32_t, mb->distance_context_map_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->distance_context_map)) return;

  BROTLI_DCHECK(mb->distance_histograms == 0);

  mb->distance_histograms_size = mb->distance_context_map_size;

  mb->distance_histograms =

      BROTLI_ALLOC(m, HistogramDistance, mb->distance_histograms_size);

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->distance_histograms)) return;

  BrotliClusterHistogramsDistance(m, distance_histograms,

                                  mb->distance_context_map_size,

                                  kMaxNumberOfHistograms,

                                  mb->distance_histograms,

                                  &mb->distance_histograms_size,

                                  mb->distance_context_map);

  if (BROTLI_IS_OOM(m)) return;

  BROTLI_FREE(m, distance_histograms);

}

#define FN(X) X ## Literal

/* NOLINT(build/header_guard) */

/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.

   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT

*/

/* template parameters: FN */

#define HistogramType FN(Histogram)

/* Greedy block splitter for one block category (literal, command or distance).

*/

typedef struct FN(BlockSplitter) {

  /* Alphabet size of particular block category. */

  size_t alphabet_size_;

  /* We collect at least this many symbols for each block. */

  size_t min_block_size_;

  /* We merge histograms A and B if

       entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,

     where A is the current histogram and B is the histogram of the last or the

     second last block type. */

  double split_threshold_;

  size_t num_blocks_;

  BlockSplit* split_;  /* not owned */

  HistogramType* histograms_;  /* not owned */

  size_t* histograms_size_;  /* not owned */

  /* Temporary storage for BlockSplitterFinishBlock. */

  HistogramType combined_histo[2];

  /* The number of symbols that we want to collect before deciding on whether

     or not to merge the block with a previous one or emit a new block. */

  size_t target_block_size_;

  /* The number of symbols in the current histogram. */

  size_t block_size_;

  /* Offset of the current histogram. */

  size_t curr_histogram_ix_;

  /* Offset of the histograms of the previous two block types. */

  size_t last_histogram_ix_[2];

  /* Entropy of the previous two block types. */

  double last_entropy_[2];

  /* The number of times we merged the current block with the last one. */

  size_t merge_last_count_;

} FN(BlockSplitter);

static void FN(InitBlockSplitter)(

    MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,

    size_t min_block_size, double split_threshold, size_t num_symbols,

    BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {

  size_t max_num_blocks = num_symbols / min_block_size + 1;

  /* We have to allocate one more histogram than the maximum number of block

     types for the current histogram when the meta-block is too big. */

  size_t max_num_types =

      BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);

  self->alphabet_size_ = alphabet_size;

  self->min_block_size_ = min_block_size;

  self->split_threshold_ = split_threshold;

  self->num_blocks_ = 0;

  self->split_ = split;

  self->histograms_size_ = histograms_size;

  self->target_block_size_ = min_block_size;

  self->block_size_ = 0;

  self->curr_histogram_ix_ = 0;

  self->merge_last_count_ = 0;

  BROTLI_ENSURE_CAPACITY(m, uint8_t,

      split->types, split->types_alloc_size, max_num_blocks);

  BROTLI_ENSURE_CAPACITY(m, uint32_t,

      split->lengths, split->lengths_alloc_size, max_num_blocks);

  if (BROTLI_IS_OOM(m)) return;

  self->split_->num_blocks = max_num_blocks;

  BROTLI_DCHECK(*histograms == 0);

  *histograms_size = max_num_types;

  *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size);

  self->histograms_ = *histograms;

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(*histograms)) return;

  /* Clear only current histogram. */

  FN(HistogramClear)(&self->histograms_[0]);

  self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;

}

/* Does either of three things:

     (1) emits the current block with a new block type;

     (2) emits the current block with the type of the second last block;

     (3) merges the current block with the last block. */

static void FN(BlockSplitterFinishBlock)(

    FN(BlockSplitter)* self, BROTLI_BOOL is_final) {

  BlockSplit* split = self->split_;

  double* last_entropy = self->last_entropy_;

  HistogramType* histograms = self->histograms_;

  self->block_size_ =

      BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);

  if (self->num_blocks_ == 0) {

    /* Create first block. */

    split->lengths[0] = (uint32_t)self->block_size_;

    split->types[0] = 0;

    last_entropy[0] =

        BitsEntropy(histograms[0].data_, self->alphabet_size_);

    last_entropy[1] = last_entropy[0];

    ++self->num_blocks_;

    ++split->num_types;

    ++self->curr_histogram_ix_;

    if (self->curr_histogram_ix_ < *self->histograms_size_)

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

    self->block_size_ = 0;

  } else if (self->block_size_ > 0) {

    double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,

                                 self->alphabet_size_);

    double combined_entropy[2];

    double diff[2];

    size_t j;

    for (j = 0; j < 2; ++j) {

      size_t last_histogram_ix = self->last_histogram_ix_[j];

      self->combined_histo[j] = histograms[self->curr_histogram_ix_];

      FN(HistogramAddHistogram)(&self->combined_histo[j],

          &histograms[last_histogram_ix]);

      combined_entropy[j] = BitsEntropy(

          &self->combined_histo[j].data_[0], self->alphabet_size_);

      diff[j] = combined_entropy[j] - entropy - last_entropy[j];

    }

    if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&

        diff[0] > self->split_threshold_ &&

        diff[1] > self->split_threshold_) {

      /* Create new block. */

      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;

      split->types[self->num_blocks_] = (uint8_t)split->num_types;

      self->last_histogram_ix_[1] = self->last_histogram_ix_[0];

      self->last_histogram_ix_[0] = (uint8_t)split->num_types;

      last_entropy[1] = last_entropy[0];

      last_entropy[0] = entropy;

      ++self->num_blocks_;

      ++split->num_types;

      ++self->curr_histogram_ix_;

      if (self->curr_histogram_ix_ < *self->histograms_size_)

        FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      self->block_size_ = 0;

      self->merge_last_count_ = 0;

      self->target_block_size_ = self->min_block_size_;

    } else if (diff[1] < diff[0] - 20.0) {

      /* Combine this block with second last block. */

      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;

      split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];

      BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);

      histograms[self->last_histogram_ix_[0]] = self->combined_histo[1];

      last_entropy[1] = last_entropy[0];

      last_entropy[0] = combined_entropy[1];

      ++self->num_blocks_;

      self->block_size_ = 0;

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      self->merge_last_count_ = 0;

      self->target_block_size_ = self->min_block_size_;

    } else {

      /* Combine this block with last block. */

      split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;

      histograms[self->last_histogram_ix_[0]] = self->combined_histo[0];

      last_entropy[0] = combined_entropy[0];

      if (split->num_types == 1) {

        last_entropy[1] = last_entropy[0];

      }

      self->block_size_ = 0;

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      if (++self->merge_last_count_ > 1) {

        self->target_block_size_ += self->min_block_size_;

      }

    }

  }

  if (is_final) {

    *self->histograms_size_ = split->num_types;

    split->num_blocks = self->num_blocks_;

  }

}

/* Adds the next symbol to the current histogram. When the current histogram

   reaches the target size, decides on merging the block. */

static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {

  FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);

  ++self->block_size_;

  if (self->block_size_ == self->target_block_size_) {

    FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);

  }

}

#undef HistogramType

#undef FN

#define FN(X) X ## Command

/* NOLINT(build/header_guard) */

/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.

   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT

*/

/* template parameters: FN */

#define HistogramType FN(Histogram)

/* Greedy block splitter for one block category (literal, command or distance).

*/

typedef struct FN(BlockSplitter) {

  /* Alphabet size of particular block category. */

  size_t alphabet_size_;

  /* We collect at least this many symbols for each block. */

  size_t min_block_size_;

  /* We merge histograms A and B if

       entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,

     where A is the current histogram and B is the histogram of the last or the

     second last block type. */

  double split_threshold_;

  size_t num_blocks_;

  BlockSplit* split_;  /* not owned */

  HistogramType* histograms_;  /* not owned */

  size_t* histograms_size_;  /* not owned */

  /* Temporary storage for BlockSplitterFinishBlock. */

  HistogramType combined_histo[2];

  /* The number of symbols that we want to collect before deciding on whether

     or not to merge the block with a previous one or emit a new block. */

  size_t target_block_size_;

  /* The number of symbols in the current histogram. */

  size_t block_size_;

  /* Offset of the current histogram. */

  size_t curr_histogram_ix_;

  /* Offset of the histograms of the previous two block types. */

  size_t last_histogram_ix_[2];

  /* Entropy of the previous two block types. */

  double last_entropy_[2];

  /* The number of times we merged the current block with the last one. */

  size_t merge_last_count_;

} FN(BlockSplitter);

static void FN(InitBlockSplitter)(

    MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,

    size_t min_block_size, double split_threshold, size_t num_symbols,

    BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {

  size_t max_num_blocks = num_symbols / min_block_size + 1;

  /* We have to allocate one more histogram than the maximum number of block

     types for the current histogram when the meta-block is too big. */

  size_t max_num_types =

      BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);

  self->alphabet_size_ = alphabet_size;

  self->min_block_size_ = min_block_size;

  self->split_threshold_ = split_threshold;

  self->num_blocks_ = 0;

  self->split_ = split;

  self->histograms_size_ = histograms_size;

  self->target_block_size_ = min_block_size;

  self->block_size_ = 0;

  self->curr_histogram_ix_ = 0;

  self->merge_last_count_ = 0;

  BROTLI_ENSURE_CAPACITY(m, uint8_t,

      split->types, split->types_alloc_size, max_num_blocks);

  BROTLI_ENSURE_CAPACITY(m, uint32_t,

      split->lengths, split->lengths_alloc_size, max_num_blocks);

  if (BROTLI_IS_OOM(m)) return;

  self->split_->num_blocks = max_num_blocks;

  BROTLI_DCHECK(*histograms == 0);

  *histograms_size = max_num_types;

  *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size);

  self->histograms_ = *histograms;

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(*histograms)) return;

  /* Clear only current histogram. */

  FN(HistogramClear)(&self->histograms_[0]);

  self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;

}

/* Does either of three things:

     (1) emits the current block with a new block type;

     (2) emits the current block with the type of the second last block;

     (3) merges the current block with the last block. */

static void FN(BlockSplitterFinishBlock)(

    FN(BlockSplitter)* self, BROTLI_BOOL is_final) {

  BlockSplit* split = self->split_;

  double* last_entropy = self->last_entropy_;

  HistogramType* histograms = self->histograms_;

  self->block_size_ =

      BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);

  if (self->num_blocks_ == 0) {

    /* Create first block. */

    split->lengths[0] = (uint32_t)self->block_size_;

    split->types[0] = 0;

    last_entropy[0] =

        BitsEntropy(histograms[0].data_, self->alphabet_size_);

    last_entropy[1] = last_entropy[0];

    ++self->num_blocks_;

    ++split->num_types;

    ++self->curr_histogram_ix_;

    if (self->curr_histogram_ix_ < *self->histograms_size_)

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

    self->block_size_ = 0;

  } else if (self->block_size_ > 0) {

    double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,

                                 self->alphabet_size_);

    double combined_entropy[2];

    double diff[2];

    size_t j;

    for (j = 0; j < 2; ++j) {

      size_t last_histogram_ix = self->last_histogram_ix_[j];

      self->combined_histo[j] = histograms[self->curr_histogram_ix_];

      FN(HistogramAddHistogram)(&self->combined_histo[j],

          &histograms[last_histogram_ix]);

      combined_entropy[j] = BitsEntropy(

          &self->combined_histo[j].data_[0], self->alphabet_size_);

      diff[j] = combined_entropy[j] - entropy - last_entropy[j];

    }

    if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&

        diff[0] > self->split_threshold_ &&

        diff[1] > self->split_threshold_) {

      /* Create new block. */

      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;

      split->types[self->num_blocks_] = (uint8_t)split->num_types;

      self->last_histogram_ix_[1] = self->last_histogram_ix_[0];

      self->last_histogram_ix_[0] = (uint8_t)split->num_types;

      last_entropy[1] = last_entropy[0];

      last_entropy[0] = entropy;

      ++self->num_blocks_;

      ++split->num_types;

      ++self->curr_histogram_ix_;

      if (self->curr_histogram_ix_ < *self->histograms_size_)

        FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      self->block_size_ = 0;

      self->merge_last_count_ = 0;

      self->target_block_size_ = self->min_block_size_;

    } else if (diff[1] < diff[0] - 20.0) {

      /* Combine this block with second last block. */

      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;

      split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];

      BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);

      histograms[self->last_histogram_ix_[0]] = self->combined_histo[1];

      last_entropy[1] = last_entropy[0];

      last_entropy[0] = combined_entropy[1];

      ++self->num_blocks_;

      self->block_size_ = 0;

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      self->merge_last_count_ = 0;

      self->target_block_size_ = self->min_block_size_;

    } else {

      /* Combine this block with last block. */

      split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;

      histograms[self->last_histogram_ix_[0]] = self->combined_histo[0];

      last_entropy[0] = combined_entropy[0];

      if (split->num_types == 1) {

        last_entropy[1] = last_entropy[0];

      }

      self->block_size_ = 0;

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      if (++self->merge_last_count_ > 1) {

        self->target_block_size_ += self->min_block_size_;

      }

    }

  }

  if (is_final) {

    *self->histograms_size_ = split->num_types;

    split->num_blocks = self->num_blocks_;

  }

}

/* Adds the next symbol to the current histogram. When the current histogram

   reaches the target size, decides on merging the block. */

static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {

  FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);

  ++self->block_size_;

  if (self->block_size_ == self->target_block_size_) {

    FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);

  }

}

#undef HistogramType

#undef FN

#define FN(X) X ## Distance

/* NOLINT(build/header_guard) */

/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.

   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT

*/

/* template parameters: FN */

#define HistogramType FN(Histogram)

/* Greedy block splitter for one block category (literal, command or distance).

*/

typedef struct FN(BlockSplitter) {

  /* Alphabet size of particular block category. */

  size_t alphabet_size_;

  /* We collect at least this many symbols for each block. */

  size_t min_block_size_;

  /* We merge histograms A and B if

       entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,

     where A is the current histogram and B is the histogram of the last or the

     second last block type. */

  double split_threshold_;

  size_t num_blocks_;

  BlockSplit* split_;  /* not owned */

  HistogramType* histograms_;  /* not owned */

  size_t* histograms_size_;  /* not owned */

  /* Temporary storage for BlockSplitterFinishBlock. */

  HistogramType combined_histo[2];

  /* The number of symbols that we want to collect before deciding on whether

     or not to merge the block with a previous one or emit a new block. */

  size_t target_block_size_;

  /* The number of symbols in the current histogram. */

  size_t block_size_;

  /* Offset of the current histogram. */

  size_t curr_histogram_ix_;

  /* Offset of the histograms of the previous two block types. */

  size_t last_histogram_ix_[2];

  /* Entropy of the previous two block types. */

  double last_entropy_[2];

  /* The number of times we merged the current block with the last one. */

  size_t merge_last_count_;

} FN(BlockSplitter);

static void FN(InitBlockSplitter)(

    MemoryManager* m, FN(BlockSplitter)* self, size_t alphabet_size,

    size_t min_block_size, double split_threshold, size_t num_symbols,

    BlockSplit* split, HistogramType** histograms, size_t* histograms_size) {

  size_t max_num_blocks = num_symbols / min_block_size + 1;

  /* We have to allocate one more histogram than the maximum number of block

     types for the current histogram when the meta-block is too big. */

  size_t max_num_types =

      BROTLI_MIN(size_t, max_num_blocks, BROTLI_MAX_NUMBER_OF_BLOCK_TYPES + 1);

  self->alphabet_size_ = alphabet_size;

  self->min_block_size_ = min_block_size;

  self->split_threshold_ = split_threshold;

  self->num_blocks_ = 0;

  self->split_ = split;

  self->histograms_size_ = histograms_size;

  self->target_block_size_ = min_block_size;

  self->block_size_ = 0;

  self->curr_histogram_ix_ = 0;

  self->merge_last_count_ = 0;

  BROTLI_ENSURE_CAPACITY(m, uint8_t,

      split->types, split->types_alloc_size, max_num_blocks);

  BROTLI_ENSURE_CAPACITY(m, uint32_t,

      split->lengths, split->lengths_alloc_size, max_num_blocks);

  if (BROTLI_IS_OOM(m)) return;

  self->split_->num_blocks = max_num_blocks;

  BROTLI_DCHECK(*histograms == 0);

  *histograms_size = max_num_types;

  *histograms = BROTLI_ALLOC(m, HistogramType, *histograms_size);

  self->histograms_ = *histograms;

  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(*histograms)) return;

  /* Clear only current histogram. */

  FN(HistogramClear)(&self->histograms_[0]);

  self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;

}

/* Does either of three things:

     (1) emits the current block with a new block type;

     (2) emits the current block with the type of the second last block;

     (3) merges the current block with the last block. */

static void FN(BlockSplitterFinishBlock)(

    FN(BlockSplitter)* self, BROTLI_BOOL is_final) {

  BlockSplit* split = self->split_;

  double* last_entropy = self->last_entropy_;

  HistogramType* histograms = self->histograms_;

  self->block_size_ =

      BROTLI_MAX(size_t, self->block_size_, self->min_block_size_);

  if (self->num_blocks_ == 0) {

    /* Create first block. */

    split->lengths[0] = (uint32_t)self->block_size_;

    split->types[0] = 0;

    last_entropy[0] =

        BitsEntropy(histograms[0].data_, self->alphabet_size_);

    last_entropy[1] = last_entropy[0];

    ++self->num_blocks_;

    ++split->num_types;

    ++self->curr_histogram_ix_;

    if (self->curr_histogram_ix_ < *self->histograms_size_)

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

    self->block_size_ = 0;

  } else if (self->block_size_ > 0) {

    double entropy = BitsEntropy(histograms[self->curr_histogram_ix_].data_,

                                 self->alphabet_size_);

    double combined_entropy[2];

    double diff[2];

    size_t j;

    for (j = 0; j < 2; ++j) {

      size_t last_histogram_ix = self->last_histogram_ix_[j];

      self->combined_histo[j] = histograms[self->curr_histogram_ix_];

      FN(HistogramAddHistogram)(&self->combined_histo[j],

          &histograms[last_histogram_ix]);

      combined_entropy[j] = BitsEntropy(

          &self->combined_histo[j].data_[0], self->alphabet_size_);

      diff[j] = combined_entropy[j] - entropy - last_entropy[j];

    }

    if (split->num_types < BROTLI_MAX_NUMBER_OF_BLOCK_TYPES &&

        diff[0] > self->split_threshold_ &&

        diff[1] > self->split_threshold_) {

      /* Create new block. */

      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;

      split->types[self->num_blocks_] = (uint8_t)split->num_types;

      self->last_histogram_ix_[1] = self->last_histogram_ix_[0];

      self->last_histogram_ix_[0] = (uint8_t)split->num_types;

      last_entropy[1] = last_entropy[0];

      last_entropy[0] = entropy;

      ++self->num_blocks_;

      ++split->num_types;

      ++self->curr_histogram_ix_;

      if (self->curr_histogram_ix_ < *self->histograms_size_)

        FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      self->block_size_ = 0;

      self->merge_last_count_ = 0;

      self->target_block_size_ = self->min_block_size_;

    } else if (diff[1] < diff[0] - 20.0) {

      /* Combine this block with second last block. */

      split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;

      split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];

      BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);

      histograms[self->last_histogram_ix_[0]] = self->combined_histo[1];

      last_entropy[1] = last_entropy[0];

      last_entropy[0] = combined_entropy[1];

      ++self->num_blocks_;

      self->block_size_ = 0;

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      self->merge_last_count_ = 0;

      self->target_block_size_ = self->min_block_size_;

    } else {

      /* Combine this block with last block. */

      split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;

      histograms[self->last_histogram_ix_[0]] = self->combined_histo[0];

      last_entropy[0] = combined_entropy[0];

      if (split->num_types == 1) {

        last_entropy[1] = last_entropy[0];

      }

      self->block_size_ = 0;

      FN(HistogramClear)(&histograms[self->curr_histogram_ix_]);

      if (++self->merge_last_count_ > 1) {

        self->target_block_size_ += self->min_block_size_;

      }

    }

  }

  if (is_final) {

    *self->histograms_size_ = split->num_types;

    split->num_blocks = self->num_blocks_;

  }

}

/* Adds the next symbol to the current histogram. When the current histogram

   reaches the target size, decides on merging the block. */

static void FN(BlockSplitterAddSymbol)(FN(BlockSplitter)* self, size_t symbol) {

  FN(HistogramAdd)(&self->histograms_[self->curr_histogram_ix_], symbol);

  ++self->block_size_;

  if (self->block_size_ == self->target_block_size_) {

    FN(BlockSplitterFinishBlock)(self, /* is_final = */ BROTLI_FALSE);

  }

}

#undef HistogramType

#undef FN

#define BROTLI_MAX_STATIC_CONTEXTS 13

/* Greedy block splitter for one block category (literal, command or distance).

   Gathers histograms for all context buckets. */

typedef struct ContextBlockSplitter {

  /* Alphabet size of particular block category. */

  size_t alphabet_size_;

  size_t num_contexts_;

  size_t max_block_types_;

  /* We collect at least this many symbols for each block. */

  size_t min_block_size_;

  /* We merge histograms A and B if

       entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,

     where A is the current histogram and B is the histogram of the last or the

     second last block type. */

  double split_threshold_;

  size_t num_blocks_;

  BlockSplit* split_;  /* not owned */

  HistogramLiteral* histograms_;  /* not owned */

  size_t* histograms_size_;  /* not owned */

  /* The number of symbols that we want to collect before deciding on whether

     or not to merge the block with a previous one or emit a new block. */

  size_t target_block_size_;

  /* The number of symbols in the current histogram. */

  size_t block_size_;

  /* Offset of the current histogram. */

  size_t curr_histogram_ix_;

  /* Offset of the histograms of the previous two block types. */

  size_t last_histogram_ix_[2];

  /* Entropy of the previous two block types. */

  double last_entropy_[2 * BROTLI_MAX_STATIC_CONTEXTS];

  /* The number of times we merged the current block with the last one. */

  size_t merge_last_count_;

} ContextBlockSplitter;

static void InitContextBlockSplitter(

    MemoryManager* m, ContextBlockSplitter* self, size_t alphabet_size,

    size_t num_contexts, size_t min_block_size, double split_threshold,

    size_t num_symbols, BlockSplit* split, HistogramLiteral** histograms,

    size_t* histograms_size) {

  size_t max_num_blocks = num_symbols / min_block_size + 1;

  size_t max_num_types;

  BROTLI_DCHECK(num_contexts <= BROTLI_MAX_STATIC_CONTEXTS);

  self->alphabet_size_ = alphabet_size;

  self->num_contexts_ = num_contexts;

  self->max_block_types_ = BROTLI_MAX_NUMBER_OF_BLOCK_TYPES / num_contexts;

  self->min_block_size_ = min_block_size;