BaseTools/Source/C/BrotliCompress/enc/metablock.c

   1 /* Copyright 2015 Google Inc. All Rights Reserved.
   2
   3    Distributed under MIT license.
   4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
   5 */
   6
   7 /* Algorithms for distributing the literals and commands of a metablock between
   8    block types and contexts. */
   9
  10 #include "./metablock.h"
  11
  12 #include "../common/constants.h"
  13 #include "../common/context.h"
  14 #include "../common/platform.h"
  15 #include <brotli/types.h>
  16 #include "./bit_cost.h"
  17 #include "./block_splitter.h"
  18 #include "./cluster.h"
  19 #include "./entropy_encode.h"
  20 #include "./histogram.h"
  21 #include "./memory.h"
  22 #include "./quality.h"
  23
  24 #if defined(__cplusplus) || defined(c_plusplus)
  25 extern "C" {
  26 #endif
  27
  28 void BrotliInitDistanceParams(BrotliEncoderParams* params,
  29     uint32_t npostfix, uint32_t ndirect) {
  30   BrotliDistanceParams* dist_params = &params->dist;
  31   uint32_t alphabet_size, max_distance;
  32
  33   dist_params->distance_postfix_bits = npostfix;
  34   dist_params->num_direct_distance_codes = ndirect;
  35
  36   alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE(
  37       npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS);
  38   max_distance = ndirect + (1U << (BROTLI_MAX_DISTANCE_BITS + npostfix + 2)) -
  39       (1U << (npostfix + 2));
  40
  41   if (params->large_window) {
  42     static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28};
  43     uint32_t postfix = 1U << npostfix;
  44     alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE(
  45         npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS);
  46     /* The maximum distance is set so that no distance symbol used can encode
  47        a distance larger than BROTLI_MAX_ALLOWED_DISTANCE with all
  48        its extra bits set. */
  49     if (ndirect < bound[npostfix]) {
  50       max_distance = BROTLI_MAX_ALLOWED_DISTANCE - (bound[npostfix] - ndirect);
  51     } else if (ndirect >= bound[npostfix] + postfix) {
  52       max_distance = (3U << 29) - 4 + (ndirect - bound[npostfix]);
  53     } else {
  54       max_distance = BROTLI_MAX_ALLOWED_DISTANCE;
  55     }
  56   }
  57
  58   dist_params->alphabet_size = alphabet_size;
  59   dist_params->max_distance = max_distance;
  60 }
  61
  62 static void RecomputeDistancePrefixes(Command* cmds,
  63                                       size_t num_commands,
  64                                       const BrotliDistanceParams* orig_params,
  65                                       const BrotliDistanceParams* new_params) {
  66   size_t i;
  67
  68   if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits &&
  69       orig_params->num_direct_distance_codes ==
  70       new_params->num_direct_distance_codes) {
  71     return;
  72   }
  73
  74   for (i = 0; i < num_commands; ++i) {
  75     Command* cmd = &cmds[i];
  76     if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {
  77       PrefixEncodeCopyDistance(CommandRestoreDistanceCode(cmd, orig_params),
  78                                new_params->num_direct_distance_codes,
  79                                new_params->distance_postfix_bits,
  80                                &cmd->dist_prefix_,
  81                                &cmd->dist_extra_);
  82     }
  83   }
  84 }
  85
  86 static BROTLI_BOOL ComputeDistanceCost(const Command* cmds,
  87                                        size_t num_commands,
  88                                        const BrotliDistanceParams* orig_params,
  89                                        const BrotliDistanceParams* new_params,
  90                                        double* cost) {
  91   size_t i;
  92   BROTLI_BOOL equal_params = BROTLI_FALSE;
  93   uint16_t dist_prefix;
  94   uint32_t dist_extra;
  95   double extra_bits = 0.0;
  96   HistogramDistance histo;
  97   HistogramClearDistance(&histo);
  98
  99   if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits &&
 100       orig_params->num_direct_distance_codes ==
 101       new_params->num_direct_distance_codes) {
 102     equal_params = BROTLI_TRUE;
 103   }
 104
 105   for (i = 0; i < num_commands; i++) {
 106     const Command* cmd = &cmds[i];
 107     if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {
 108       if (equal_params) {
 109         dist_prefix = cmd->dist_prefix_;
 110       } else {
 111         uint32_t distance = CommandRestoreDistanceCode(cmd, orig_params);
 112         if (distance > new_params->max_distance) {
 113           return BROTLI_FALSE;
 114         }
 115         PrefixEncodeCopyDistance(distance,
 116                                  new_params->num_direct_distance_codes,
 117                                  new_params->distance_postfix_bits,
 118                                  &dist_prefix,
 119                                  &dist_extra);
 120       }
 121       HistogramAddDistance(&histo, dist_prefix & 0x3FF);
 122       extra_bits += dist_prefix >> 10;
 123     }
 124   }
 125
 126   *cost = BrotliPopulationCostDistance(&histo) + extra_bits;
 127   return BROTLI_TRUE;
 128 }
 129
 130 void BrotliBuildMetaBlock(MemoryManager* m,
 131                           const uint8_t* ringbuffer,
 132                           const size_t pos,
 133                           const size_t mask,
 134                           BrotliEncoderParams* params,
 135                           uint8_t prev_byte,
 136                           uint8_t prev_byte2,
 137                           Command* cmds,
 138                           size_t num_commands,
 139                           ContextType literal_context_mode,
 140                           MetaBlockSplit* mb) {
 141   /* Histogram ids need to fit in one byte. */
 142   static const size_t kMaxNumberOfHistograms = 256;
 143   HistogramDistance* distance_histograms;
 144   HistogramLiteral* literal_histograms;
 145   ContextType* literal_context_modes = NULL;
 146   size_t literal_histograms_size;
 147   size_t distance_histograms_size;
 148   size_t i;
 149   size_t literal_context_multiplier = 1;
 150   uint32_t npostfix;
 151   uint32_t ndirect_msb = 0;
 152   BROTLI_BOOL check_orig = BROTLI_TRUE;
 153   double best_dist_cost = 1e99;
 154   BrotliEncoderParams orig_params = *params;
 155   BrotliEncoderParams new_params = *params;
 156
 157   for (npostfix = 0; npostfix <= BROTLI_MAX_NPOSTFIX; npostfix++) {
 158     for (; ndirect_msb < 16; ndirect_msb++) {
 159       uint32_t ndirect = ndirect_msb << npostfix;
 160       BROTLI_BOOL skip;
 161       double dist_cost;
 162       BrotliInitDistanceParams(&new_params, npostfix, ndirect);
 163       if (npostfix == orig_params.dist.distance_postfix_bits &&
 164           ndirect == orig_params.dist.num_direct_distance_codes) {
 165         check_orig = BROTLI_FALSE;
 166       }
 167       skip = !ComputeDistanceCost(
 168           cmds, num_commands,
 169           &orig_params.dist, &new_params.dist, &dist_cost);
 170       if (skip || (dist_cost > best_dist_cost)) {
 171         break;
 172       }
 173       best_dist_cost = dist_cost;
 174       params->dist = new_params.dist;
 175     }
 176     if (ndirect_msb > 0) ndirect_msb--;
 177     ndirect_msb /= 2;
 178   }
 179   if (check_orig) {
 180     double dist_cost;
 181     ComputeDistanceCost(cmds, num_commands,
 182                         &orig_params.dist, &orig_params.dist, &dist_cost);
 183     if (dist_cost < best_dist_cost) {
 184       /* NB: currently unused; uncomment when more param tuning is added. */
 185       /* best_dist_cost = dist_cost; */
 186       params->dist = orig_params.dist;
 187     }
 188   }
 189   RecomputeDistancePrefixes(cmds, num_commands,
 190                             &orig_params.dist, &params->dist);
 191
 192   BrotliSplitBlock(m, cmds, num_commands,
 193                    ringbuffer, pos, mask, params,
 194                    &mb->literal_split,
 195                    &mb->command_split,
 196                    &mb->distance_split);
 197   if (BROTLI_IS_OOM(m)) return;
 198
 199   if (!params->disable_literal_context_modeling) {
 200     literal_context_multiplier = 1 << BROTLI_LITERAL_CONTEXT_BITS;
 201     literal_context_modes =
 202         BROTLI_ALLOC(m, ContextType, mb->literal_split.num_types);
 203     if (BROTLI_IS_OOM(m)) return;
 204     for (i = 0; i < mb->literal_split.num_types; ++i) {
 205       literal_context_modes[i] = literal_context_mode;
 206     }
 207   }
 208
 209   literal_histograms_size =
 210       mb->literal_split.num_types * literal_context_multiplier;
 211   literal_histograms =
 212       BROTLI_ALLOC(m, HistogramLiteral, literal_histograms_size);
 213   if (BROTLI_IS_OOM(m)) return;
 214   ClearHistogramsLiteral(literal_histograms, literal_histograms_size);
 215
 216   distance_histograms_size =
 217       mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;
 218   distance_histograms =
 219       BROTLI_ALLOC(m, HistogramDistance, distance_histograms_size);
 220   if (BROTLI_IS_OOM(m)) return;
 221   ClearHistogramsDistance(distance_histograms, distance_histograms_size);
 222
 223   BROTLI_DCHECK(mb->command_histograms == 0);
 224   mb->command_histograms_size = mb->command_split.num_types;
 225   mb->command_histograms =
 226       BROTLI_ALLOC(m, HistogramCommand, mb->command_histograms_size);
 227   if (BROTLI_IS_OOM(m)) return;
 228   ClearHistogramsCommand(mb->command_histograms, mb->command_histograms_size);
 229
 230   BrotliBuildHistogramsWithContext(cmds, num_commands,
 231       &mb->literal_split, &mb->command_split, &mb->distance_split,
 232       ringbuffer, pos, mask, prev_byte, prev_byte2, literal_context_modes,
 233       literal_histograms, mb->command_histograms, distance_histograms);
 234   BROTLI_FREE(m, literal_context_modes);
 235
 236   BROTLI_DCHECK(mb->literal_context_map == 0);
 237   mb->literal_context_map_size =
 238       mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS;
 239   mb->literal_context_map =
 240       BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size);
 241   if (BROTLI_IS_OOM(m)) return;
 242
 243   BROTLI_DCHECK(mb->literal_histograms == 0);
 244   mb->literal_histograms_size = mb->literal_context_map_size;
 245   mb->literal_histograms =
 246       BROTLI_ALLOC(m, HistogramLiteral, mb->literal_histograms_size);
 247   if (BROTLI_IS_OOM(m)) return;
 248
 249   BrotliClusterHistogramsLiteral(m, literal_histograms, literal_histograms_size,
 250       kMaxNumberOfHistograms, mb->literal_histograms,
 251       &mb->literal_histograms_size, mb->literal_context_map);
 252   if (BROTLI_IS_OOM(m)) return;
 253   BROTLI_FREE(m, literal_histograms);
 254
 255   if (params->disable_literal_context_modeling) {
 256     /* Distribute assignment to all contexts. */
 257     for (i = mb->literal_split.num_types; i != 0;) {
 258       size_t j = 0;
 259       i--;
 260       for (; j < (1 << BROTLI_LITERAL_CONTEXT_BITS); j++) {
 261         mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] =
 262             mb->literal_context_map[i];
 263       }
 264     }
 265   }
 266
 267   BROTLI_DCHECK(mb->distance_context_map == 0);
 268   mb->distance_context_map_size =
 269       mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;
 270   mb->distance_context_map =
 271       BROTLI_ALLOC(m, uint32_t, mb->distance_context_map_size);
 272   if (BROTLI_IS_OOM(m)) return;
 273
 274   BROTLI_DCHECK(mb->distance_histograms == 0);
 275   mb->distance_histograms_size = mb->distance_context_map_size;
 276   mb->distance_histograms =
 277       BROTLI_ALLOC(m, HistogramDistance, mb->distance_histograms_size);
 278   if (BROTLI_IS_OOM(m)) return;
 279
 280   BrotliClusterHistogramsDistance(m, distance_histograms,
 281                                   mb->distance_context_map_size,
 282                                   kMaxNumberOfHistograms,
 283                                   mb->distance_histograms,
 284                                   &mb->distance_histograms_size,
 285                                   mb->distance_context_map);
 286   if (BROTLI_IS_OOM(m)) return;
 287   BROTLI_FREE(m, distance_histograms);
 288 }
 289
 290 #define FN(X) X ## Literal
 291 #include "./metablock_inc.h"  /* NOLINT(build/include) */
 292 #undef FN
 293
 294 #define FN(X) X ## Command
 295 #include "./metablock_inc.h"  /* NOLINT(build/include) */
 296 #undef FN
 297
 298 #define FN(X) X ## Distance
 299 #include "./metablock_inc.h"  /* NOLINT(build/include) */
 300 #undef FN
 301
 302 #define BROTLI_MAX_STATIC_CONTEXTS 13
 303
 304 /* Greedy block splitter for one block category (literal, command or distance).
 305    Gathers histograms for all context buckets. */
 306 typedef struct ContextBlockSplitter {
 307   /* Alphabet size of particular block category. */
 308   size_t alphabet_size_;
 309   size_t num_contexts_;
 310   size_t max_block_types_;
 311   /* We collect at least this many symbols for each block. */
 312   size_t min_block_size_;
 313   /* We merge histograms A and B if
 314        entropy(A+B) < entropy(A) + entropy(B) + split_threshold_,
 315      where A is the current histogram and B is the histogram of the last or the
 316      second last block type. */
 317   double split_threshold_;
 318
 319   size_t num_blocks_;
 320   BlockSplit* split_;  /* not owned */
 321   HistogramLiteral* histograms_;  /* not owned */
 322   size_t* histograms_size_;  /* not owned */
 323
 324   /* The number of symbols that we want to collect before deciding on whether
 325      or not to merge the block with a previous one or emit a new block. */
 326   size_t target_block_size_;
 327   /* The number of symbols in the current histogram. */
 328   size_t block_size_;
 329   /* Offset of the current histogram. */
 330   size_t curr_histogram_ix_;
 331   /* Offset of the histograms of the previous two block types. */
 332   size_t last_histogram_ix_[2];
 333   /* Entropy of the previous two block types. */
 334   double last_entropy_[2 * BROTLI_MAX_STATIC_CONTEXTS];
 335   /* The number of times we merged the current block with the last one. */
 336   size_t merge_last_count_;
 337 } ContextBlockSplitter;
 338
 339 static void InitContextBlockSplitter(
 340     MemoryManager* m, ContextBlockSplitter* self, size_t alphabet_size,
 341     size_t num_contexts, size_t min_block_size, double split_threshold,
 342     size_t num_symbols, BlockSplit* split, HistogramLiteral** histograms,
 343     size_t* histograms_size) {
 344   size_t max_num_blocks = num_symbols / min_block_size + 1;
 345   size_t max_num_types;
 346   BROTLI_DCHECK(num_contexts <= BROTLI_MAX_STATIC_CONTEXTS);
 347
 348   self->alphabet_size_ = alphabet_size;
 349   self->num_contexts_ = num_contexts;
 350   self->max_block_types_ = BROTLI_MAX_NUMBER_OF_BLOCK_TYPES / num_contexts;
 351   self->min_block_size_ = min_block_size;
 352   self->split_threshold_ = split_threshold;
 353   self->num_blocks_ = 0;
 354   self->split_ = split;
 355   self->histograms_size_ = histograms_size;
 356   self->target_block_size_ = min_block_size;
 357   self->block_size_ = 0;
 358   self->curr_histogram_ix_ = 0;
 359   self->merge_last_count_ = 0;
 360
 361   /* We have to allocate one more histogram than the maximum number of block
 362      types for the current histogram when the meta-block is too big. */
 363   max_num_types =
 364       BROTLI_MIN(size_t, max_num_blocks, self->max_block_types_ + 1);
 365   BROTLI_ENSURE_CAPACITY(m, uint8_t,
 366       split->types, split->types_alloc_size, max_num_blocks);
 367   BROTLI_ENSURE_CAPACITY(m, uint32_t,
 368       split->lengths, split->lengths_alloc_size, max_num_blocks);
 369   if (BROTLI_IS_OOM(m)) return;
 370   split->num_blocks = max_num_blocks;
 371   if (BROTLI_IS_OOM(m)) return;
 372   BROTLI_DCHECK(*histograms == 0);
 373   *histograms_size = max_num_types * num_contexts;
 374   *histograms = BROTLI_ALLOC(m, HistogramLiteral, *histograms_size);
 375   self->histograms_ = *histograms;
 376   if (BROTLI_IS_OOM(m)) return;
 377   /* Clear only current histogram. */
 378   ClearHistogramsLiteral(&self->histograms_[0], num_contexts);
 379   self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;
 380 }
 381
 382 /* Does either of three things:
 383      (1) emits the current block with a new block type;
 384      (2) emits the current block with the type of the second last block;
 385      (3) merges the current block with the last block. */
 386 static void ContextBlockSplitterFinishBlock(
 387     ContextBlockSplitter* self, MemoryManager* m, BROTLI_BOOL is_final) {
 388   BlockSplit* split = self->split_;
 389   const size_t num_contexts = self->num_contexts_;
 390   double* last_entropy = self->last_entropy_;
 391   HistogramLiteral* histograms = self->histograms_;
 392
 393   if (self->block_size_ < self->min_block_size_) {
 394     self->block_size_ = self->min_block_size_;
 395   }
 396   if (self->num_blocks_ == 0) {
 397     size_t i;
 398     /* Create first block. */
 399     split->lengths[0] = (uint32_t)self->block_size_;
 400     split->types[0] = 0;
 401
 402     for (i = 0; i < num_contexts; ++i) {
 403       last_entropy[i] =
 404           BitsEntropy(histograms[i].data_, self->alphabet_size_);
 405       last_entropy[num_contexts + i] = last_entropy[i];
 406     }
 407     ++self->num_blocks_;
 408     ++split->num_types;
 409     self->curr_histogram_ix_ += num_contexts;
 410     if (self->curr_histogram_ix_ < *self->histograms_size_) {
 411       ClearHistogramsLiteral(
 412           &self->histograms_[self->curr_histogram_ix_], self->num_contexts_);
 413     }
 414     self->block_size_ = 0;
 415   } else if (self->block_size_ > 0) {
 416     /* Try merging the set of histograms for the current block type with the
 417        respective set of histograms for the last and second last block types.
 418        Decide over the split based on the total reduction of entropy across
 419        all contexts. */
 420     double entropy[BROTLI_MAX_STATIC_CONTEXTS];
 421     HistogramLiteral* combined_histo =
 422         BROTLI_ALLOC(m, HistogramLiteral, 2 * num_contexts);
 423     double combined_entropy[2 * BROTLI_MAX_STATIC_CONTEXTS];
 424     double diff[2] = { 0.0 };
 425     size_t i;
 426     if (BROTLI_IS_OOM(m)) return;
 427     for (i = 0; i < num_contexts; ++i) {
 428       size_t curr_histo_ix = self->curr_histogram_ix_ + i;
 429       size_t j;
 430       entropy[i] = BitsEntropy(histograms[curr_histo_ix].data_,
 431                                self->alphabet_size_);
 432       for (j = 0; j < 2; ++j) {
 433         size_t jx = j * num_contexts + i;
 434         size_t last_histogram_ix = self->last_histogram_ix_[j] + i;
 435         combined_histo[jx] = histograms[curr_histo_ix];
 436         HistogramAddHistogramLiteral(&combined_histo[jx],
 437             &histograms[last_histogram_ix]);
 438         combined_entropy[jx] = BitsEntropy(
 439             &combined_histo[jx].data_[0], self->alphabet_size_);
 440         diff[j] += combined_entropy[jx] - entropy[i] - last_entropy[jx];
 441       }
 442     }
 443
 444     if (split->num_types < self->max_block_types_ &&
 445         diff[0] > self->split_threshold_ &&
 446         diff[1] > self->split_threshold_) {
 447       /* Create new block. */
 448       split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
 449       split->types[self->num_blocks_] = (uint8_t)split->num_types;
 450       self->last_histogram_ix_[1] = self->last_histogram_ix_[0];
 451       self->last_histogram_ix_[0] = split->num_types * num_contexts;
 452       for (i = 0; i < num_contexts; ++i) {
 453         last_entropy[num_contexts + i] = last_entropy[i];
 454         last_entropy[i] = entropy[i];
 455       }
 456       ++self->num_blocks_;
 457       ++split->num_types;
 458       self->curr_histogram_ix_ += num_contexts;
 459       if (self->curr_histogram_ix_ < *self->histograms_size_) {
 460         ClearHistogramsLiteral(
 461             &self->histograms_[self->curr_histogram_ix_], self->num_contexts_);
 462       }
 463       self->block_size_ = 0;
 464       self->merge_last_count_ = 0;
 465       self->target_block_size_ = self->min_block_size_;
 466     } else if (diff[1] < diff[0] - 20.0) {
 467       /* Combine this block with second last block. */
 468       split->lengths[self->num_blocks_] = (uint32_t)self->block_size_;
 469       split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2];
 470       BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1);
 471       for (i = 0; i < num_contexts; ++i) {
 472         histograms[self->last_histogram_ix_[0] + i] =
 473             combined_histo[num_contexts + i];
 474         last_entropy[num_contexts + i] = last_entropy[i];
 475         last_entropy[i] = combined_entropy[num_contexts + i];
 476         HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]);
 477       }
 478       ++self->num_blocks_;
 479       self->block_size_ = 0;
 480       self->merge_last_count_ = 0;
 481       self->target_block_size_ = self->min_block_size_;
 482     } else {
 483       /* Combine this block with last block. */
 484       split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_;
 485       for (i = 0; i < num_contexts; ++i) {
 486         histograms[self->last_histogram_ix_[0] + i] = combined_histo[i];
 487         last_entropy[i] = combined_entropy[i];
 488         if (split->num_types == 1) {
 489           last_entropy[num_contexts + i] = last_entropy[i];
 490         }
 491         HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]);
 492       }
 493       self->block_size_ = 0;
 494       if (++self->merge_last_count_ > 1) {
 495         self->target_block_size_ += self->min_block_size_;
 496       }
 497     }
 498     BROTLI_FREE(m, combined_histo);
 499   }
 500   if (is_final) {
 501     *self->histograms_size_ = split->num_types * num_contexts;
 502     split->num_blocks = self->num_blocks_;
 503   }
 504 }
 505
 506 /* Adds the next symbol to the current block type and context. When the
 507    current block reaches the target size, decides on merging the block. */
 508 static void ContextBlockSplitterAddSymbol(
 509     ContextBlockSplitter* self, MemoryManager* m,
 510     size_t symbol, size_t context) {
 511   HistogramAddLiteral(&self->histograms_[self->curr_histogram_ix_ + context],
 512       symbol);
 513   ++self->block_size_;
 514   if (self->block_size_ == self->target_block_size_) {
 515     ContextBlockSplitterFinishBlock(self, m, /* is_final = */ BROTLI_FALSE);
 516     if (BROTLI_IS_OOM(m)) return;
 517   }
 518 }
 519
 520 static void MapStaticContexts(MemoryManager* m,
 521                               size_t num_contexts,
 522                               const uint32_t* static_context_map,
 523                               MetaBlockSplit* mb) {
 524   size_t i;
 525   BROTLI_DCHECK(mb->literal_context_map == 0);
 526   mb->literal_context_map_size =
 527       mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS;
 528   mb->literal_context_map =
 529       BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size);
 530   if (BROTLI_IS_OOM(m)) return;
 531
 532   for (i = 0; i < mb->literal_split.num_types; ++i) {
 533     uint32_t offset = (uint32_t)(i * num_contexts);
 534     size_t j;
 535     for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS); ++j) {
 536       mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] =
 537           offset + static_context_map[j];
 538     }
 539   }
 540 }
 541
 542 static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal(
 543     MemoryManager* m, const uint8_t* ringbuffer, size_t pos, size_t mask,
 544     uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut,
 545     const size_t num_contexts, const uint32_t* static_context_map,
 546     const Command* commands, size_t n_commands, MetaBlockSplit* mb) {
 547   union {
 548     BlockSplitterLiteral plain;
 549     ContextBlockSplitter ctx;
 550   } lit_blocks;
 551   BlockSplitterCommand cmd_blocks;
 552   BlockSplitterDistance dist_blocks;
 553   size_t num_literals = 0;
 554   size_t i;
 555   for (i = 0; i < n_commands; ++i) {
 556     num_literals += commands[i].insert_len_;
 557   }
 558
 559   if (num_contexts == 1) {
 560     InitBlockSplitterLiteral(m, &lit_blocks.plain, 256, 512, 400.0,
 561         num_literals, &mb->literal_split, &mb->literal_histograms,
 562         &mb->literal_histograms_size);
 563   } else {
 564     InitContextBlockSplitter(m, &lit_blocks.ctx, 256, num_contexts, 512, 400.0,
 565         num_literals, &mb->literal_split, &mb->literal_histograms,
 566         &mb->literal_histograms_size);
 567   }
 568   if (BROTLI_IS_OOM(m)) return;
 569   InitBlockSplitterCommand(m, &cmd_blocks, BROTLI_NUM_COMMAND_SYMBOLS, 1024,
 570       500.0, n_commands, &mb->command_split, &mb->command_histograms,
 571       &mb->command_histograms_size);
 572   if (BROTLI_IS_OOM(m)) return;
 573   InitBlockSplitterDistance(m, &dist_blocks, 64, 512, 100.0, n_commands,
 574       &mb->distance_split, &mb->distance_histograms,
 575       &mb->distance_histograms_size);
 576   if (BROTLI_IS_OOM(m)) return;
 577
 578   for (i = 0; i < n_commands; ++i) {
 579     const Command cmd = commands[i];
 580     size_t j;
 581     BlockSplitterAddSymbolCommand(&cmd_blocks, cmd.cmd_prefix_);
 582     for (j = cmd.insert_len_; j != 0; --j) {
 583       uint8_t literal = ringbuffer[pos & mask];
 584       if (num_contexts == 1) {
 585         BlockSplitterAddSymbolLiteral(&lit_blocks.plain, literal);
 586       } else {
 587         size_t context =
 588             BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut);
 589         ContextBlockSplitterAddSymbol(&lit_blocks.ctx, m, literal,
 590                                       static_context_map[context]);
 591         if (BROTLI_IS_OOM(m)) return;
 592       }
 593       prev_byte2 = prev_byte;
 594       prev_byte = literal;
 595       ++pos;
 596     }
 597     pos += CommandCopyLen(&cmd);
 598     if (CommandCopyLen(&cmd)) {
 599       prev_byte2 = ringbuffer[(pos - 2) & mask];
 600       prev_byte = ringbuffer[(pos - 1) & mask];
 601       if (cmd.cmd_prefix_ >= 128) {
 602         BlockSplitterAddSymbolDistance(&dist_blocks, cmd.dist_prefix_ & 0x3FF);
 603       }
 604     }
 605   }
 606
 607   if (num_contexts == 1) {
 608     BlockSplitterFinishBlockLiteral(
 609         &lit_blocks.plain, /* is_final = */ BROTLI_TRUE);
 610   } else {
 611     ContextBlockSplitterFinishBlock(
 612         &lit_blocks.ctx, m, /* is_final = */ BROTLI_TRUE);
 613     if (BROTLI_IS_OOM(m)) return;
 614   }
 615   BlockSplitterFinishBlockCommand(&cmd_blocks, /* is_final = */ BROTLI_TRUE);
 616   BlockSplitterFinishBlockDistance(&dist_blocks, /* is_final = */ BROTLI_TRUE);
 617
 618   if (num_contexts > 1) {
 619     MapStaticContexts(m, num_contexts, static_context_map, mb);
 620   }
 621 }
 622
 623 void BrotliBuildMetaBlockGreedy(MemoryManager* m,
 624                                 const uint8_t* ringbuffer,
 625                                 size_t pos,
 626                                 size_t mask,
 627                                 uint8_t prev_byte,
 628                                 uint8_t prev_byte2,
 629                                 ContextLut literal_context_lut,
 630                                 size_t num_contexts,
 631                                 const uint32_t* static_context_map,
 632                                 const Command* commands,
 633                                 size_t n_commands,
 634                                 MetaBlockSplit* mb) {
 635   if (num_contexts == 1) {
 636     BrotliBuildMetaBlockGreedyInternal(m, ringbuffer, pos, mask, prev_byte,
 637         prev_byte2, literal_context_lut, 1, NULL, commands, n_commands, mb);
 638   } else {
 639     BrotliBuildMetaBlockGreedyInternal(m, ringbuffer, pos, mask, prev_byte,
 640         prev_byte2, literal_context_lut, num_contexts, static_context_map,
 641         commands, n_commands, mb);
 642   }
 643 }
 644
 645 void BrotliOptimizeHistograms(uint32_t num_distance_codes,
 646                               MetaBlockSplit* mb) {
 647   uint8_t good_for_rle[BROTLI_NUM_COMMAND_SYMBOLS];
 648   size_t i;
 649   for (i = 0; i < mb->literal_histograms_size; ++i) {
 650     BrotliOptimizeHuffmanCountsForRle(256, mb->literal_histograms[i].data_,
 651                                       good_for_rle);
 652   }
 653   for (i = 0; i < mb->command_histograms_size; ++i) {
 654     BrotliOptimizeHuffmanCountsForRle(BROTLI_NUM_COMMAND_SYMBOLS,
 655                                       mb->command_histograms[i].data_,
 656                                       good_for_rle);
 657   }
 658   for (i = 0; i < mb->distance_histograms_size; ++i) {
 659     BrotliOptimizeHuffmanCountsForRle(num_distance_codes,
 660                                       mb->distance_histograms[i].data_,
 661                                       good_for_rle);
 662   }
 663 }
 664
 665 #if defined(__cplusplus) || defined(c_plusplus)
 666 }  /* extern "C" */
 667 #endif