+++ /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/context.h"\r
-#include "../common/platform.h"\r
-#include <brotli/types.h>\r
-#include "./bit_cost.h"\r
-#include "./block_splitter.h"\r
-#include "./cluster.h"\r
-#include "./entropy_encode.h"\r
-#include "./histogram.h"\r
-#include "./memory.h"\r
-#include "./quality.h"\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-extern "C" {\r
-#endif\r
-\r
-void BrotliInitDistanceParams(BrotliEncoderParams* params,\r
- uint32_t npostfix, uint32_t ndirect) {\r
- BrotliDistanceParams* dist_params = ¶ms->dist;\r
- uint32_t alphabet_size, max_distance;\r
-\r
- dist_params->distance_postfix_bits = npostfix;\r
- dist_params->num_direct_distance_codes = ndirect;\r
-\r
- alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE(\r
- npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS);\r
- max_distance = ndirect + (1U << (BROTLI_MAX_DISTANCE_BITS + npostfix + 2)) -\r
- (1U << (npostfix + 2));\r
-\r
- if (params->large_window) {\r
- static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28};\r
- uint32_t postfix = 1U << npostfix;\r
- alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE(\r
- npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS);\r
- /* The maximum distance is set so that no distance symbol used can encode\r
- a distance larger than BROTLI_MAX_ALLOWED_DISTANCE with all\r
- its extra bits set. */\r
- if (ndirect < bound[npostfix]) {\r
- max_distance = BROTLI_MAX_ALLOWED_DISTANCE - (bound[npostfix] - ndirect);\r
- } else if (ndirect >= bound[npostfix] + postfix) {\r
- max_distance = (3U << 29) - 4 + (ndirect - bound[npostfix]);\r
- } else {\r
- max_distance = BROTLI_MAX_ALLOWED_DISTANCE;\r
- }\r
- }\r
-\r
- dist_params->alphabet_size = alphabet_size;\r
- dist_params->max_distance = max_distance;\r
-}\r
-\r
-static void RecomputeDistancePrefixes(Command* cmds,\r
- size_t num_commands,\r
- const BrotliDistanceParams* orig_params,\r
- const BrotliDistanceParams* new_params) {\r
- size_t i;\r
-\r
- if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits &&\r
- orig_params->num_direct_distance_codes ==\r
- new_params->num_direct_distance_codes) {\r
- return;\r
- }\r
-\r
- for (i = 0; i < num_commands; ++i) {\r
- Command* cmd = &cmds[i];\r
- if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {\r
- PrefixEncodeCopyDistance(CommandRestoreDistanceCode(cmd, orig_params),\r
- new_params->num_direct_distance_codes,\r
- new_params->distance_postfix_bits,\r
- &cmd->dist_prefix_,\r
- &cmd->dist_extra_);\r
- }\r
- }\r
-}\r
-\r
-static BROTLI_BOOL ComputeDistanceCost(const Command* cmds,\r
- size_t num_commands,\r
- const BrotliDistanceParams* orig_params,\r
- const BrotliDistanceParams* new_params,\r
- double* cost) {\r
- size_t i;\r
- BROTLI_BOOL equal_params = BROTLI_FALSE;\r
- uint16_t dist_prefix;\r
- uint32_t dist_extra;\r
- double extra_bits = 0.0;\r
- HistogramDistance histo;\r
- HistogramClearDistance(&histo);\r
-\r
- if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits &&\r
- orig_params->num_direct_distance_codes ==\r
- new_params->num_direct_distance_codes) {\r
- equal_params = BROTLI_TRUE;\r
- }\r
-\r
- for (i = 0; i < num_commands; i++) {\r
- const Command* cmd = &cmds[i];\r
- if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) {\r
- if (equal_params) {\r
- dist_prefix = cmd->dist_prefix_;\r
- } else {\r
- uint32_t distance = CommandRestoreDistanceCode(cmd, orig_params);\r
- if (distance > new_params->max_distance) {\r
- return BROTLI_FALSE;\r
- }\r
- PrefixEncodeCopyDistance(distance,\r
- new_params->num_direct_distance_codes,\r
- new_params->distance_postfix_bits,\r
- &dist_prefix,\r
- &dist_extra);\r
- }\r
- HistogramAddDistance(&histo, dist_prefix & 0x3FF);\r
- extra_bits += dist_prefix >> 10;\r
- }\r
- }\r
-\r
- *cost = BrotliPopulationCostDistance(&histo) + extra_bits;\r
- return BROTLI_TRUE;\r
-}\r
-\r
-void BrotliBuildMetaBlock(MemoryManager* m,\r
- const uint8_t* ringbuffer,\r
- const size_t pos,\r
- const size_t mask,\r
- BrotliEncoderParams* params,\r
- uint8_t prev_byte,\r
- uint8_t prev_byte2,\r
- 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 = NULL;\r
- size_t literal_histograms_size;\r
- size_t distance_histograms_size;\r
- size_t i;\r
- size_t literal_context_multiplier = 1;\r
- uint32_t npostfix;\r
- uint32_t ndirect_msb = 0;\r
- BROTLI_BOOL check_orig = BROTLI_TRUE;\r
- double best_dist_cost = 1e99;\r
- BrotliEncoderParams orig_params = *params;\r
- BrotliEncoderParams new_params = *params;\r
-\r
- for (npostfix = 0; npostfix <= BROTLI_MAX_NPOSTFIX; npostfix++) {\r
- for (; ndirect_msb < 16; ndirect_msb++) {\r
- uint32_t ndirect = ndirect_msb << npostfix;\r
- BROTLI_BOOL skip;\r
- double dist_cost;\r
- BrotliInitDistanceParams(&new_params, npostfix, ndirect);\r
- if (npostfix == orig_params.dist.distance_postfix_bits &&\r
- ndirect == orig_params.dist.num_direct_distance_codes) {\r
- check_orig = BROTLI_FALSE;\r
- }\r
- skip = !ComputeDistanceCost(\r
- cmds, num_commands,\r
- &orig_params.dist, &new_params.dist, &dist_cost);\r
- if (skip || (dist_cost > best_dist_cost)) {\r
- break;\r
- }\r
- best_dist_cost = dist_cost;\r
- params->dist = new_params.dist;\r
- }\r
- if (ndirect_msb > 0) ndirect_msb--;\r
- ndirect_msb /= 2;\r
- }\r
- if (check_orig) {\r
- double dist_cost;\r
- ComputeDistanceCost(cmds, num_commands,\r
- &orig_params.dist, &orig_params.dist, &dist_cost);\r
- if (dist_cost < best_dist_cost) {\r
- /* NB: currently unused; uncomment when more param tuning is added. */\r
- /* best_dist_cost = dist_cost; */\r
- params->dist = orig_params.dist;\r
- }\r
- }\r
- RecomputeDistancePrefixes(cmds, num_commands,\r
- &orig_params.dist, ¶ms->dist);\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
- if (!params->disable_literal_context_modeling) {\r
- literal_context_multiplier = 1 << BROTLI_LITERAL_CONTEXT_BITS;\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
-\r
- literal_histograms_size =\r
- mb->literal_split.num_types * literal_context_multiplier;\r
- literal_histograms =\r
- BROTLI_ALLOC(m, HistogramLiteral, literal_histograms_size);\r
- if (BROTLI_IS_OOM(m)) return;\r
- ClearHistogramsLiteral(literal_histograms, literal_histograms_size);\r
-\r
- distance_histograms_size =\r
- mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS;\r
- distance_histograms =\r
- BROTLI_ALLOC(m, HistogramDistance, distance_histograms_size);\r
- if (BROTLI_IS_OOM(m)) return;\r
- ClearHistogramsDistance(distance_histograms, distance_histograms_size);\r
-\r
- BROTLI_DCHECK(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
-\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
- BROTLI_DCHECK(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
- BROTLI_DCHECK(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
-\r
- BrotliClusterHistogramsLiteral(m, literal_histograms, literal_histograms_size,\r
- kMaxNumberOfHistograms, mb->literal_histograms,\r
- &mb->literal_histograms_size, mb->literal_context_map);\r
- if (BROTLI_IS_OOM(m)) return;\r
- BROTLI_FREE(m, literal_histograms);\r
-\r
- if (params->disable_literal_context_modeling) {\r
- /* Distribute assignment to all contexts. */\r
- for (i = mb->literal_split.num_types; i != 0;) {\r
- size_t j = 0;\r
- i--;\r
- for (; j < (1 << BROTLI_LITERAL_CONTEXT_BITS); j++) {\r
- mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] =\r
- mb->literal_context_map[i];\r
- }\r
- }\r
- }\r
-\r
- BROTLI_DCHECK(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
-\r
- BROTLI_DCHECK(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
-\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
-#define BROTLI_MAX_STATIC_CONTEXTS 13\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_[2 * BROTLI_MAX_STATIC_CONTEXTS];\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
- BROTLI_DCHECK(num_contexts <= BROTLI_MAX_STATIC_CONTEXTS);\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
- if (BROTLI_IS_OOM(m)) return;\r
- BROTLI_DCHECK(*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 histogram. */\r
- ClearHistogramsLiteral(&self->histograms_[0], num_contexts);\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 ContextBlockSplitterFinishBlock(\r
- ContextBlockSplitter* self, MemoryManager* m, 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_MAX_STATIC_CONTEXTS];\r
- HistogramLiteral* combined_histo =\r
- BROTLI_ALLOC(m, HistogramLiteral, 2 * num_contexts);\r
- double combined_entropy[2 * BROTLI_MAX_STATIC_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_histo);\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(\r
- ContextBlockSplitter* self, MemoryManager* m,\r
- 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(self, m, /* is_final = */ BROTLI_FALSE);\r
- if (BROTLI_IS_OOM(m)) return;\r
- }\r
-}\r
-\r
-static void MapStaticContexts(MemoryManager* m,\r
- size_t num_contexts,\r
- const uint32_t* static_context_map,\r
- MetaBlockSplit* mb) {\r
- size_t i;\r
- BROTLI_DCHECK(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
- uint32_t offset = (uint32_t)(i * num_contexts);\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
- offset + static_context_map[j];\r
- }\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal(\r
- MemoryManager* m, const uint8_t* ringbuffer, size_t pos, size_t mask,\r
- uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut,\r
- const size_t num_contexts, const uint32_t* static_context_map,\r
- const Command* commands, size_t n_commands, MetaBlockSplit* mb) {\r
- union {\r
- BlockSplitterLiteral plain;\r
- ContextBlockSplitter ctx;\r
- } 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
- if (num_contexts == 1) {\r
- InitBlockSplitterLiteral(m, &lit_blocks.plain, 256, 512, 400.0,\r
- num_literals, &mb->literal_split, &mb->literal_histograms,\r
- &mb->literal_histograms_size);\r
- } else {\r
- InitContextBlockSplitter(m, &lit_blocks.ctx, 256, num_contexts, 512, 400.0,\r
- num_literals, &mb->literal_split, &mb->literal_histograms,\r
- &mb->literal_histograms_size);\r
- }\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
- uint8_t literal = ringbuffer[pos & mask];\r
- if (num_contexts == 1) {\r
- BlockSplitterAddSymbolLiteral(&lit_blocks.plain, literal);\r
- } else {\r
- size_t context =\r
- BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut);\r
- ContextBlockSplitterAddSymbol(&lit_blocks.ctx, m, literal,\r
- static_context_map[context]);\r
- if (BROTLI_IS_OOM(m)) return;\r
- }\r
- prev_byte2 = prev_byte;\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_ & 0x3FF);\r
- }\r
- }\r
- }\r
-\r
- if (num_contexts == 1) {\r
- BlockSplitterFinishBlockLiteral(\r
- &lit_blocks.plain, /* is_final = */ BROTLI_TRUE);\r
- } else {\r
- ContextBlockSplitterFinishBlock(\r
- &lit_blocks.ctx, m, /* is_final = */ BROTLI_TRUE);\r
- if (BROTLI_IS_OOM(m)) return;\r
- }\r
- BlockSplitterFinishBlockCommand(&cmd_blocks, /* is_final = */ BROTLI_TRUE);\r
- BlockSplitterFinishBlockDistance(&dist_blocks, /* is_final = */ BROTLI_TRUE);\r
-\r
- if (num_contexts > 1) {\r
- MapStaticContexts(m, num_contexts, static_context_map, mb);\r
- }\r
-}\r
-\r
-void BrotliBuildMetaBlockGreedy(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
- ContextLut literal_context_lut,\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
- if (num_contexts == 1) {\r
- BrotliBuildMetaBlockGreedyInternal(m, ringbuffer, pos, mask, prev_byte,\r
- prev_byte2, literal_context_lut, 1, NULL, commands, n_commands, mb);\r
- } else {\r
- BrotliBuildMetaBlockGreedyInternal(m, ringbuffer, pos, mask, prev_byte,\r
- prev_byte2, literal_context_lut, num_contexts, static_context_map,\r
- commands, n_commands, mb);\r
- }\r
-}\r
-\r
-void BrotliOptimizeHistograms(uint32_t num_distance_codes,\r
- MetaBlockSplit* mb) {\r
- uint8_t good_for_rle[BROTLI_NUM_COMMAND_SYMBOLS];\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
- 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