--- /dev/null
+/* 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
+/* Algorithms for distributing the literals and commands of a metablock between\r
+ block types and contexts. */\r
+\r
+#include "./metablock.h"\r
+\r
+#include "../common/constants.h"\r
+#include "../common/types.h"\r
+#include "./bit_cost.h"\r
+#include "./block_splitter.h"\r
+#include "./cluster.h"\r
+#include "./context.h"\r
+#include "./entropy_encode.h"\r
+#include "./histogram.h"\r
+#include "./memory.h"\r
+#include "./port.h"\r
+#include "./quality.h"\r
+\r
+#if defined(__cplusplus) || defined(c_plusplus)\r
+extern "C" {\r
+#endif\r
+\r
+void BrotliBuildMetaBlock(MemoryManager* m,\r
+ const uint8_t* ringbuffer,\r
+ const size_t pos,\r
+ const size_t mask,\r
+ const BrotliEncoderParams* params,\r
+ uint8_t prev_byte,\r
+ uint8_t prev_byte2,\r
+ const Command* cmds,\r
+ size_t num_commands,\r
+ ContextType literal_context_mode,\r
+ MetaBlockSplit* mb) {\r
+ /* Histogram ids need to fit in one byte. */\r
+ static const size_t kMaxNumberOfHistograms = 256;\r
+ HistogramDistance* distance_histograms;\r
+ HistogramLiteral* literal_histograms;\r
+ ContextType* literal_context_modes;\r
+ size_t num_literal_contexts;\r
+ size_t num_distance_contexts;\r
+ size_t i;\r
+\r
+ BrotliSplitBlock(m, cmds, num_commands,\r
+ ringbuffer, pos, mask, params,\r
+ &mb->literal_split,\r
+ &mb->command_split,\r
+ &mb->distance_split);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+\r
+ literal_context_modes =\r
+ BROTLI_ALLOC(m, ContextType, mb->literal_split.num_types);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ for (i = 0; i < mb->literal_split.num_types; ++i) {\r
+ literal_context_modes[i] = literal_context_mode;\r
+ }\r
+\r
+ num_literal_contexts =\r
+ mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS;\r
+ num_distance_contexts =\r
+ mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;\r
+ literal_histograms = BROTLI_ALLOC(m, HistogramLiteral, num_literal_contexts);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ ClearHistogramsLiteral(literal_histograms, num_literal_contexts);\r
+\r
+ assert(mb->command_histograms == 0);\r
+ mb->command_histograms_size = mb->command_split.num_types;\r
+ mb->command_histograms =\r
+ BROTLI_ALLOC(m, HistogramCommand, mb->command_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ ClearHistogramsCommand(mb->command_histograms, mb->command_histograms_size);\r
+ distance_histograms =\r
+ BROTLI_ALLOC(m, HistogramDistance, num_distance_contexts);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ ClearHistogramsDistance(distance_histograms, num_distance_contexts);\r
+ BrotliBuildHistogramsWithContext(cmds, num_commands,\r
+ &mb->literal_split, &mb->command_split, &mb->distance_split,\r
+ ringbuffer, pos, mask, prev_byte, prev_byte2, literal_context_modes,\r
+ literal_histograms, mb->command_histograms, distance_histograms);\r
+ BROTLI_FREE(m, literal_context_modes);\r
+\r
+ assert(mb->literal_context_map == 0);\r
+ mb->literal_context_map_size =\r
+ mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS;\r
+ mb->literal_context_map =\r
+ BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ assert(mb->literal_histograms == 0);\r
+ mb->literal_histograms_size = mb->literal_context_map_size;\r
+ mb->literal_histograms =\r
+ BROTLI_ALLOC(m, HistogramLiteral, mb->literal_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ BrotliClusterHistogramsLiteral(m, literal_histograms,\r
+ mb->literal_context_map_size,\r
+ kMaxNumberOfHistograms,\r
+ mb->literal_histograms,\r
+ &mb->literal_histograms_size,\r
+ mb->literal_context_map);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ BROTLI_FREE(m, literal_histograms);\r
+\r
+ assert(mb->distance_context_map == 0);\r
+ mb->distance_context_map_size =\r
+ mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;\r
+ mb->distance_context_map =\r
+ BROTLI_ALLOC(m, uint32_t, mb->distance_context_map_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ assert(mb->distance_histograms == 0);\r
+ mb->distance_histograms_size = mb->distance_context_map_size;\r
+ mb->distance_histograms =\r
+ BROTLI_ALLOC(m, HistogramDistance, mb->distance_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ BrotliClusterHistogramsDistance(m, distance_histograms,\r
+ mb->distance_context_map_size,\r
+ kMaxNumberOfHistograms,\r
+ mb->distance_histograms,\r
+ &mb->distance_histograms_size,\r
+ mb->distance_context_map);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ BROTLI_FREE(m, distance_histograms);\r
+}\r
+\r
+#define FN(X) X ## Literal\r
+#include "./metablock_inc.h" /* NOLINT(build/include) */\r
+#undef FN\r
+\r
+#define FN(X) X ## Command\r
+#include "./metablock_inc.h" /* NOLINT(build/include) */\r
+#undef FN\r
+\r
+#define FN(X) X ## Distance\r
+#include "./metablock_inc.h" /* NOLINT(build/include) */\r
+#undef FN\r
+\r
+void BrotliBuildMetaBlockGreedy(MemoryManager* m,\r
+ const uint8_t* ringbuffer,\r
+ size_t pos,\r
+ size_t mask,\r
+ const Command *commands,\r
+ size_t n_commands,\r
+ MetaBlockSplit* mb) {\r
+ BlockSplitterLiteral lit_blocks;\r
+ BlockSplitterCommand cmd_blocks;\r
+ BlockSplitterDistance dist_blocks;\r
+ size_t num_literals = 0;\r
+ size_t i;\r
+ for (i = 0; i < n_commands; ++i) {\r
+ num_literals += commands[i].insert_len_;\r
+ }\r
+\r
+ InitBlockSplitterLiteral(m, &lit_blocks, 256, 512, 400.0, num_literals,\r
+ &mb->literal_split, &mb->literal_histograms,\r
+ &mb->literal_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ InitBlockSplitterCommand(m, &cmd_blocks, BROTLI_NUM_COMMAND_SYMBOLS, 1024,\r
+ 500.0, n_commands, &mb->command_split, &mb->command_histograms,\r
+ &mb->command_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ InitBlockSplitterDistance(m, &dist_blocks, 64, 512, 100.0, n_commands,\r
+ &mb->distance_split, &mb->distance_histograms,\r
+ &mb->distance_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+\r
+ for (i = 0; i < n_commands; ++i) {\r
+ const Command cmd = commands[i];\r
+ size_t j;\r
+ BlockSplitterAddSymbolCommand(&cmd_blocks, cmd.cmd_prefix_);\r
+ for (j = cmd.insert_len_; j != 0; --j) {\r
+ BlockSplitterAddSymbolLiteral(&lit_blocks, ringbuffer[pos & mask]);\r
+ ++pos;\r
+ }\r
+ pos += CommandCopyLen(&cmd);\r
+ if (CommandCopyLen(&cmd) && cmd.cmd_prefix_ >= 128) {\r
+ BlockSplitterAddSymbolDistance(&dist_blocks, cmd.dist_prefix_);\r
+ }\r
+ }\r
+\r
+ BlockSplitterFinishBlockLiteral(&lit_blocks, /* is_final = */ BROTLI_TRUE);\r
+ BlockSplitterFinishBlockCommand(&cmd_blocks, /* is_final = */ BROTLI_TRUE);\r
+ BlockSplitterFinishBlockDistance(&dist_blocks, /* is_final = */ BROTLI_TRUE);\r
+}\r
+\r
+/* Greedy block splitter for one block category (literal, command or distance).\r
+ Gathers histograms for all context buckets. */\r
+typedef struct ContextBlockSplitter {\r
+ /* Alphabet size of particular block category. */\r
+ size_t alphabet_size_;\r
+ size_t num_contexts_;\r
+ size_t max_block_types_;\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
+ HistogramLiteral* 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_;\r
+ /* The number of times we merged the current block with the last one. */\r
+ size_t merge_last_count_;\r
+} ContextBlockSplitter;\r
+\r
+static void InitContextBlockSplitter(\r
+ MemoryManager* m, ContextBlockSplitter* self, size_t alphabet_size,\r
+ size_t num_contexts, size_t min_block_size, double split_threshold,\r
+ size_t num_symbols, BlockSplit* split, HistogramLiteral** histograms,\r
+ size_t* histograms_size) {\r
+ size_t max_num_blocks = num_symbols / min_block_size + 1;\r
+ size_t max_num_types;\r
+\r
+ self->alphabet_size_ = alphabet_size;\r
+ self->num_contexts_ = num_contexts;\r
+ self->max_block_types_ = BROTLI_MAX_NUMBER_OF_BLOCK_TYPES / num_contexts;\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
+\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
+ max_num_types =\r
+ BROTLI_MIN(size_t, max_num_blocks, self->max_block_types_ + 1);\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
+ split->num_blocks = max_num_blocks;\r
+ self->last_entropy_ = BROTLI_ALLOC(m, double, 2 * num_contexts);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ assert(*histograms == 0);\r
+ *histograms_size = max_num_types * num_contexts;\r
+ *histograms = BROTLI_ALLOC(m, HistogramLiteral, *histograms_size);\r
+ self->histograms_ = *histograms;\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ /* Clear only current historgram. */\r
+ ClearHistogramsLiteral(&self->histograms_[0], num_contexts);\r
+ self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0;\r
+}\r
+\r
+static void CleanupContextBlockSplitter(\r
+ MemoryManager* m, ContextBlockSplitter* self) {\r
+ BROTLI_FREE(m, self->last_entropy_);\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 ContextBlockSplitterFinishBlock(\r
+ MemoryManager* m, ContextBlockSplitter* self, BROTLI_BOOL is_final) {\r
+ BlockSplit* split = self->split_;\r
+ const size_t num_contexts = self->num_contexts_;\r
+ double* last_entropy = self->last_entropy_;\r
+ HistogramLiteral* histograms = self->histograms_;\r
+\r
+ if (self->block_size_ < self->min_block_size_) {\r
+ self->block_size_ = self->min_block_size_;\r
+ }\r
+ if (self->num_blocks_ == 0) {\r
+ size_t i;\r
+ /* Create first block. */\r
+ split->lengths[0] = (uint32_t)self->block_size_;\r
+ split->types[0] = 0;\r
+\r
+ for (i = 0; i < num_contexts; ++i) {\r
+ last_entropy[i] =\r
+ BitsEntropy(histograms[i].data_, self->alphabet_size_);\r
+ last_entropy[num_contexts + i] = last_entropy[i];\r
+ }\r
+ ++self->num_blocks_;\r
+ ++split->num_types;\r
+ self->curr_histogram_ix_ += num_contexts;\r
+ if (self->curr_histogram_ix_ < *self->histograms_size_) {\r
+ ClearHistogramsLiteral(\r
+ &self->histograms_[self->curr_histogram_ix_], self->num_contexts_);\r
+ }\r
+ self->block_size_ = 0;\r
+ } else if (self->block_size_ > 0) {\r
+ /* Try merging the set of histograms for the current block type with the\r
+ respective set of histograms for the last and second last block types.\r
+ Decide over the split based on the total reduction of entropy across\r
+ all contexts. */\r
+ double* entropy = BROTLI_ALLOC(m, double, num_contexts);\r
+ HistogramLiteral* combined_histo =\r
+ BROTLI_ALLOC(m, HistogramLiteral, 2 * num_contexts);\r
+ double* combined_entropy = BROTLI_ALLOC(m, double, 2 * num_contexts);\r
+ double diff[2] = { 0.0 };\r
+ size_t i;\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ for (i = 0; i < num_contexts; ++i) {\r
+ size_t curr_histo_ix = self->curr_histogram_ix_ + i;\r
+ size_t j;\r
+ entropy[i] = BitsEntropy(histograms[curr_histo_ix].data_,\r
+ self->alphabet_size_);\r
+ for (j = 0; j < 2; ++j) {\r
+ size_t jx = j * num_contexts + i;\r
+ size_t last_histogram_ix = self->last_histogram_ix_[j] + i;\r
+ combined_histo[jx] = histograms[curr_histo_ix];\r
+ HistogramAddHistogramLiteral(&combined_histo[jx],\r
+ &histograms[last_histogram_ix]);\r
+ combined_entropy[jx] = BitsEntropy(\r
+ &combined_histo[jx].data_[0], self->alphabet_size_);\r
+ diff[j] += combined_entropy[jx] - entropy[i] - last_entropy[jx];\r
+ }\r
+ }\r
+\r
+ if (split->num_types < self->max_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] = split->num_types * num_contexts;\r
+ for (i = 0; i < num_contexts; ++i) {\r
+ last_entropy[num_contexts + i] = last_entropy[i];\r
+ last_entropy[i] = entropy[i];\r
+ }\r
+ ++self->num_blocks_;\r
+ ++split->num_types;\r
+ self->curr_histogram_ix_ += num_contexts;\r
+ if (self->curr_histogram_ix_ < *self->histograms_size_) {\r
+ ClearHistogramsLiteral(\r
+ &self->histograms_[self->curr_histogram_ix_], self->num_contexts_);\r
+ }\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
+ for (i = 0; i < num_contexts; ++i) {\r
+ histograms[self->last_histogram_ix_[0] + i] =\r
+ combined_histo[num_contexts + i];\r
+ last_entropy[num_contexts + i] = last_entropy[i];\r
+ last_entropy[i] = combined_entropy[num_contexts + i];\r
+ HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]);\r
+ }\r
+ ++self->num_blocks_;\r
+ self->block_size_ = 0;\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
+ for (i = 0; i < num_contexts; ++i) {\r
+ histograms[self->last_histogram_ix_[0] + i] = combined_histo[i];\r
+ last_entropy[i] = combined_entropy[i];\r
+ if (split->num_types == 1) {\r
+ last_entropy[num_contexts + i] = last_entropy[i];\r
+ }\r
+ HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]);\r
+ }\r
+ self->block_size_ = 0;\r
+ if (++self->merge_last_count_ > 1) {\r
+ self->target_block_size_ += self->min_block_size_;\r
+ }\r
+ }\r
+ BROTLI_FREE(m, combined_entropy);\r
+ BROTLI_FREE(m, combined_histo);\r
+ BROTLI_FREE(m, entropy);\r
+ }\r
+ if (is_final) {\r
+ *self->histograms_size_ = split->num_types * num_contexts;\r
+ split->num_blocks = self->num_blocks_;\r
+ }\r
+}\r
+\r
+/* Adds the next symbol to the current block type and context. When the\r
+ current block reaches the target size, decides on merging the block. */\r
+static void ContextBlockSplitterAddSymbol(MemoryManager* m,\r
+ ContextBlockSplitter* self, size_t symbol, size_t context) {\r
+ HistogramAddLiteral(&self->histograms_[self->curr_histogram_ix_ + context],\r
+ symbol);\r
+ ++self->block_size_;\r
+ if (self->block_size_ == self->target_block_size_) {\r
+ ContextBlockSplitterFinishBlock(m, self, /* is_final = */ BROTLI_FALSE);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ }\r
+}\r
+\r
+void BrotliBuildMetaBlockGreedyWithContexts(MemoryManager* m,\r
+ const uint8_t* ringbuffer,\r
+ size_t pos,\r
+ size_t mask,\r
+ uint8_t prev_byte,\r
+ uint8_t prev_byte2,\r
+ ContextType literal_context_mode,\r
+ size_t num_contexts,\r
+ const uint32_t* static_context_map,\r
+ const Command *commands,\r
+ size_t n_commands,\r
+ MetaBlockSplit* mb) {\r
+ ContextBlockSplitter lit_blocks;\r
+ BlockSplitterCommand cmd_blocks;\r
+ BlockSplitterDistance dist_blocks;\r
+ size_t num_literals = 0;\r
+ size_t i;\r
+ for (i = 0; i < n_commands; ++i) {\r
+ num_literals += commands[i].insert_len_;\r
+ }\r
+\r
+ InitContextBlockSplitter(m, &lit_blocks, 256, num_contexts, 512, 400.0,\r
+ num_literals, &mb->literal_split, &mb->literal_histograms,\r
+ &mb->literal_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ InitBlockSplitterCommand(m, &cmd_blocks, BROTLI_NUM_COMMAND_SYMBOLS, 1024,\r
+ 500.0, n_commands, &mb->command_split, &mb->command_histograms,\r
+ &mb->command_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ InitBlockSplitterDistance(m, &dist_blocks, 64, 512, 100.0, n_commands,\r
+ &mb->distance_split, &mb->distance_histograms,\r
+ &mb->distance_histograms_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+\r
+ for (i = 0; i < n_commands; ++i) {\r
+ const Command cmd = commands[i];\r
+ size_t j;\r
+ BlockSplitterAddSymbolCommand(&cmd_blocks, cmd.cmd_prefix_);\r
+ for (j = cmd.insert_len_; j != 0; --j) {\r
+ size_t context = Context(prev_byte, prev_byte2, literal_context_mode);\r
+ uint8_t literal = ringbuffer[pos & mask];\r
+ ContextBlockSplitterAddSymbol(\r
+ m, &lit_blocks, literal, static_context_map[context]);\r
+ prev_byte2 = prev_byte;\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ prev_byte = literal;\r
+ ++pos;\r
+ }\r
+ pos += CommandCopyLen(&cmd);\r
+ if (CommandCopyLen(&cmd)) {\r
+ prev_byte2 = ringbuffer[(pos - 2) & mask];\r
+ prev_byte = ringbuffer[(pos - 1) & mask];\r
+ if (cmd.cmd_prefix_ >= 128) {\r
+ BlockSplitterAddSymbolDistance(&dist_blocks, cmd.dist_prefix_);\r
+ }\r
+ }\r
+ }\r
+\r
+ ContextBlockSplitterFinishBlock(m, &lit_blocks, /* is_final = */ BROTLI_TRUE);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+ CleanupContextBlockSplitter(m, &lit_blocks);\r
+ BlockSplitterFinishBlockCommand(&cmd_blocks, /* is_final = */ BROTLI_TRUE);\r
+ BlockSplitterFinishBlockDistance(&dist_blocks, /* is_final = */ BROTLI_TRUE);\r
+\r
+ assert(mb->literal_context_map == 0);\r
+ mb->literal_context_map_size =\r
+ mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS;\r
+ mb->literal_context_map =\r
+ BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size);\r
+ if (BROTLI_IS_OOM(m)) return;\r
+\r
+ for (i = 0; i < mb->literal_split.num_types; ++i) {\r
+ size_t j;\r
+ for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS); ++j) {\r
+ mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] =\r
+ (uint32_t)(i * num_contexts) + static_context_map[j];\r
+ }\r
+ }\r
+}\r
+\r
+void BrotliOptimizeHistograms(size_t num_direct_distance_codes,\r
+ size_t distance_postfix_bits,\r
+ MetaBlockSplit* mb) {\r
+ uint8_t good_for_rle[BROTLI_NUM_COMMAND_SYMBOLS];\r
+ size_t num_distance_codes;\r
+ size_t i;\r
+ for (i = 0; i < mb->literal_histograms_size; ++i) {\r
+ BrotliOptimizeHuffmanCountsForRle(256, mb->literal_histograms[i].data_,\r
+ good_for_rle);\r
+ }\r
+ for (i = 0; i < mb->command_histograms_size; ++i) {\r
+ BrotliOptimizeHuffmanCountsForRle(BROTLI_NUM_COMMAND_SYMBOLS,\r
+ mb->command_histograms[i].data_,\r
+ good_for_rle);\r
+ }\r
+ num_distance_codes = BROTLI_NUM_DISTANCE_SHORT_CODES +\r
+ num_direct_distance_codes + (48u << distance_postfix_bits);\r
+ for (i = 0; i < mb->distance_histograms_size; ++i) {\r
+ BrotliOptimizeHuffmanCountsForRle(num_distance_codes,\r
+ mb->distance_histograms[i].data_,\r
+ good_for_rle);\r
+ }\r
+}\r
+\r
+#if defined(__cplusplus) || defined(c_plusplus)\r
+} /* extern "C" */\r
+#endif\r
projects / mirror_edk2.git / blobdiff