diff options
Diffstat (limited to 'deps/node/deps/brotli/c/enc/metablock.c')
| -rw-r--r-- | deps/node/deps/brotli/c/enc/metablock.c | 667 |
1 files changed, 0 insertions, 667 deletions
diff --git a/deps/node/deps/brotli/c/enc/metablock.c b/deps/node/deps/brotli/c/enc/metablock.c deleted file mode 100644 index 4e80044f..00000000 --- a/deps/node/deps/brotli/c/enc/metablock.c +++ /dev/null @@ -1,667 +0,0 @@ -/* 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 "../common/constants.h" -#include "../common/context.h" -#include "../common/platform.h" -#include <brotli/types.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" - -#if defined(__cplusplus) || defined(c_plusplus) -extern "C" { -#endif - -void BrotliInitDistanceParams(BrotliEncoderParams* params, - uint32_t npostfix, uint32_t ndirect) { - BrotliDistanceParams* dist_params = ¶ms->dist; - uint32_t alphabet_size, max_distance; - - dist_params->distance_postfix_bits = npostfix; - dist_params->num_direct_distance_codes = ndirect; - - alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE( - npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS); - max_distance = ndirect + (1U << (BROTLI_MAX_DISTANCE_BITS + npostfix + 2)) - - (1U << (npostfix + 2)); - - if (params->large_window) { - static const uint32_t bound[BROTLI_MAX_NPOSTFIX + 1] = {0, 4, 12, 28}; - uint32_t postfix = 1U << npostfix; - alphabet_size = BROTLI_DISTANCE_ALPHABET_SIZE( - npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS); - /* The maximum distance is set so that no distance symbol used can encode - a distance larger than BROTLI_MAX_ALLOWED_DISTANCE with all - its extra bits set. */ - if (ndirect < bound[npostfix]) { - max_distance = BROTLI_MAX_ALLOWED_DISTANCE - (bound[npostfix] - ndirect); - } else if (ndirect >= bound[npostfix] + postfix) { - max_distance = (3U << 29) - 4 + (ndirect - bound[npostfix]); - } else { - max_distance = BROTLI_MAX_ALLOWED_DISTANCE; - } - } - - dist_params->alphabet_size = alphabet_size; - 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) { - size_t i; - BROTLI_BOOL equal_params = BROTLI_FALSE; - uint16_t dist_prefix; - uint32_t dist_extra; - double extra_bits = 0.0; - HistogramDistance histo; - HistogramClearDistance(&histo); - - 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(&histo, dist_prefix & 0x3FF); - extra_bits += dist_prefix >> 10; - } - } - - *cost = BrotliPopulationCostDistance(&histo) + extra_bits; - return BROTLI_TRUE; -} - -void 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; - BrotliEncoderParams orig_params = *params; - BrotliEncoderParams new_params = *params; - - 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); - if (npostfix == orig_params.dist.distance_postfix_bits && - ndirect == orig_params.dist.num_direct_distance_codes) { - check_orig = BROTLI_FALSE; - } - skip = !ComputeDistanceCost( - cmds, num_commands, - &orig_params.dist, &new_params.dist, &dist_cost); - if (skip || (dist_cost > best_dist_cost)) { - break; - } - best_dist_cost = dist_cost; - params->dist = new_params.dist; - } - if (ndirect_msb > 0) ndirect_msb--; - ndirect_msb /= 2; - } - if (check_orig) { - double dist_cost; - ComputeDistanceCost(cmds, num_commands, - &orig_params.dist, &orig_params.dist, &dist_cost); - 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.dist; - } - } - RecomputeDistancePrefixes(cmds, num_commands, - &orig_params.dist, ¶ms->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)) 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)) 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)) 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)) 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)) 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)) 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)) 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)) 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 -#include "./metablock_inc.h" /* NOLINT(build/include) */ -#undef FN - -#define FN(X) X ## Command -#include "./metablock_inc.h" /* NOLINT(build/include) */ -#undef FN - -#define FN(X) X ## Distance -#include "./metablock_inc.h" /* NOLINT(build/include) */ -#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; - 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; - - /* 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. */ - max_num_types = - BROTLI_MIN(size_t, max_num_blocks, self->max_block_types_ + 1); - 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; - split->num_blocks = max_num_blocks; - if (BROTLI_IS_OOM(m)) return; - BROTLI_DCHECK(*histograms == 0); - *histograms_size = max_num_types * num_contexts; - *histograms = BROTLI_ALLOC(m, HistogramLiteral, *histograms_size); - self->histograms_ = *histograms; - if (BROTLI_IS_OOM(m)) return; - /* Clear only current histogram. */ - ClearHistogramsLiteral(&self->histograms_[0], num_contexts); - 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 ContextBlockSplitterFinishBlock( - ContextBlockSplitter* self, MemoryManager* m, BROTLI_BOOL is_final) { - BlockSplit* split = self->split_; - const size_t num_contexts = self->num_contexts_; - double* last_entropy = self->last_entropy_; - HistogramLiteral* histograms = self->histograms_; - - if (self->block_size_ < self->min_block_size_) { - self->block_size_ = self->min_block_size_; - } - if (self->num_blocks_ == 0) { - size_t i; - /* Create first block. */ - split->lengths[0] = (uint32_t)self->block_size_; - split->types[0] = 0; - - for (i = 0; i < num_contexts; ++i) { - last_entropy[i] = - BitsEntropy(histograms[i].data_, self->alphabet_size_); - last_entropy[num_contexts + i] = last_entropy[i]; - } - ++self->num_blocks_; - ++split->num_types; - self->curr_histogram_ix_ += num_contexts; - if (self->curr_histogram_ix_ < *self->histograms_size_) { - ClearHistogramsLiteral( - &self->histograms_[self->curr_histogram_ix_], self->num_contexts_); - } - self->block_size_ = 0; - } else if (self->block_size_ > 0) { - /* Try merging the set of histograms for the current block type with the - respective set of histograms for the last and second last block types. - Decide over the split based on the total reduction of entropy across - all contexts. */ - double entropy[BROTLI_MAX_STATIC_CONTEXTS]; - HistogramLiteral* combined_histo = - BROTLI_ALLOC(m, HistogramLiteral, 2 * num_contexts); - double combined_entropy[2 * BROTLI_MAX_STATIC_CONTEXTS]; - double diff[2] = { 0.0 }; - size_t i; - if (BROTLI_IS_OOM(m)) return; - for (i = 0; i < num_contexts; ++i) { - size_t curr_histo_ix = self->curr_histogram_ix_ + i; - size_t j; - entropy[i] = BitsEntropy(histograms[curr_histo_ix].data_, - self->alphabet_size_); - for (j = 0; j < 2; ++j) { - size_t jx = j * num_contexts + i; - size_t last_histogram_ix = self->last_histogram_ix_[j] + i; - combined_histo[jx] = histograms[curr_histo_ix]; - HistogramAddHistogramLiteral(&combined_histo[jx], - &histograms[last_histogram_ix]); - combined_entropy[jx] = BitsEntropy( - &combined_histo[jx].data_[0], self->alphabet_size_); - diff[j] += combined_entropy[jx] - entropy[i] - last_entropy[jx]; - } - } - - if (split->num_types < self->max_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] = split->num_types * num_contexts; - for (i = 0; i < num_contexts; ++i) { - last_entropy[num_contexts + i] = last_entropy[i]; - last_entropy[i] = entropy[i]; - } - ++self->num_blocks_; - ++split->num_types; - self->curr_histogram_ix_ += num_contexts; - if (self->curr_histogram_ix_ < *self->histograms_size_) { - ClearHistogramsLiteral( - &self->histograms_[self->curr_histogram_ix_], self->num_contexts_); - } - 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); - for (i = 0; i < num_contexts; ++i) { - histograms[self->last_histogram_ix_[0] + i] = - combined_histo[num_contexts + i]; - last_entropy[num_contexts + i] = last_entropy[i]; - last_entropy[i] = combined_entropy[num_contexts + i]; - HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]); - } - ++self->num_blocks_; - self->block_size_ = 0; - 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_; - for (i = 0; i < num_contexts; ++i) { - histograms[self->last_histogram_ix_[0] + i] = combined_histo[i]; - last_entropy[i] = combined_entropy[i]; - if (split->num_types == 1) { - last_entropy[num_contexts + i] = last_entropy[i]; - } - HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]); - } - self->block_size_ = 0; - if (++self->merge_last_count_ > 1) { - self->target_block_size_ += self->min_block_size_; - } - } - BROTLI_FREE(m, combined_histo); - } - if (is_final) { - *self->histograms_size_ = split->num_types * num_contexts; - split->num_blocks = self->num_blocks_; - } -} - -/* Adds the next symbol to the current block type and context. When the - current block reaches the target size, decides on merging the block. */ -static void ContextBlockSplitterAddSymbol( - ContextBlockSplitter* self, MemoryManager* m, - size_t symbol, size_t context) { - HistogramAddLiteral(&self->histograms_[self->curr_histogram_ix_ + context], - symbol); - ++self->block_size_; - if (self->block_size_ == self->target_block_size_) { - ContextBlockSplitterFinishBlock(self, m, /* is_final = */ BROTLI_FALSE); - if (BROTLI_IS_OOM(m)) return; - } -} - -static void MapStaticContexts(MemoryManager* m, - size_t num_contexts, - const uint32_t* static_context_map, - MetaBlockSplit* mb) { - size_t i; - 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)) return; - - for (i = 0; i < mb->literal_split.num_types; ++i) { - uint32_t offset = (uint32_t)(i * num_contexts); - size_t j; - for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS); ++j) { - mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] = - offset + static_context_map[j]; - } - } -} - -static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal( - MemoryManager* m, const uint8_t* ringbuffer, size_t pos, size_t mask, - uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut, - const size_t num_contexts, const uint32_t* static_context_map, - const Command* commands, size_t n_commands, MetaBlockSplit* mb) { - union { - BlockSplitterLiteral plain; - ContextBlockSplitter ctx; - } lit_blocks; - BlockSplitterCommand cmd_blocks; - BlockSplitterDistance dist_blocks; - size_t num_literals = 0; - size_t i; - for (i = 0; i < n_commands; ++i) { - num_literals += commands[i].insert_len_; - } - - if (num_contexts == 1) { - InitBlockSplitterLiteral(m, &lit_blocks.plain, 256, 512, 400.0, - num_literals, &mb->literal_split, &mb->literal_histograms, - &mb->literal_histograms_size); - } else { - InitContextBlockSplitter(m, &lit_blocks.ctx, 256, num_contexts, 512, 400.0, - num_literals, &mb->literal_split, &mb->literal_histograms, - &mb->literal_histograms_size); - } - if (BROTLI_IS_OOM(m)) return; - InitBlockSplitterCommand(m, &cmd_blocks, BROTLI_NUM_COMMAND_SYMBOLS, 1024, - 500.0, n_commands, &mb->command_split, &mb->command_histograms, - &mb->command_histograms_size); - if (BROTLI_IS_OOM(m)) return; - InitBlockSplitterDistance(m, &dist_blocks, 64, 512, 100.0, n_commands, - &mb->distance_split, &mb->distance_histograms, - &mb->distance_histograms_size); - if (BROTLI_IS_OOM(m)) return; - - for (i = 0; i < n_commands; ++i) { - const Command cmd = commands[i]; - size_t j; - BlockSplitterAddSymbolCommand(&cmd_blocks, cmd.cmd_prefix_); - for (j = cmd.insert_len_; j != 0; --j) { - uint8_t literal = ringbuffer[pos & mask]; - if (num_contexts == 1) { - BlockSplitterAddSymbolLiteral(&lit_blocks.plain, literal); - } else { - size_t context = - BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut); - ContextBlockSplitterAddSymbol(&lit_blocks.ctx, m, literal, - static_context_map[context]); - if (BROTLI_IS_OOM(m)) return; - } - prev_byte2 = prev_byte; - prev_byte = literal; - ++pos; - } - pos += CommandCopyLen(&cmd); - if (CommandCopyLen(&cmd)) { - prev_byte2 = ringbuffer[(pos - 2) & mask]; - prev_byte = ringbuffer[(pos - 1) & mask]; - if (cmd.cmd_prefix_ >= 128) { - BlockSplitterAddSymbolDistance(&dist_blocks, cmd.dist_prefix_ & 0x3FF); - } - } - } - - if (num_contexts == 1) { - BlockSplitterFinishBlockLiteral( - &lit_blocks.plain, /* is_final = */ BROTLI_TRUE); - } else { - ContextBlockSplitterFinishBlock( - &lit_blocks.ctx, m, /* is_final = */ BROTLI_TRUE); - if (BROTLI_IS_OOM(m)) return; - } - BlockSplitterFinishBlockCommand(&cmd_blocks, /* is_final = */ BROTLI_TRUE); - BlockSplitterFinishBlockDistance(&dist_blocks, /* is_final = */ BROTLI_TRUE); - - if (num_contexts > 1) { - MapStaticContexts(m, num_contexts, static_context_map, mb); - } -} - -void BrotliBuildMetaBlockGreedy(MemoryManager* m, - const uint8_t* ringbuffer, - size_t pos, - size_t mask, - uint8_t prev_byte, - uint8_t prev_byte2, - ContextLut literal_context_lut, - size_t num_contexts, - const uint32_t* static_context_map, - const Command* commands, - size_t n_commands, - MetaBlockSplit* mb) { - if (num_contexts == 1) { - BrotliBuildMetaBlockGreedyInternal(m, ringbuffer, pos, mask, prev_byte, - prev_byte2, literal_context_lut, 1, NULL, commands, n_commands, mb); - } else { - BrotliBuildMetaBlockGreedyInternal(m, ringbuffer, pos, mask, prev_byte, - prev_byte2, literal_context_lut, num_contexts, static_context_map, - commands, n_commands, mb); - } -} - -void BrotliOptimizeHistograms(uint32_t num_distance_codes, - MetaBlockSplit* mb) { - uint8_t good_for_rle[BROTLI_NUM_COMMAND_SYMBOLS]; - size_t i; - for (i = 0; i < mb->literal_histograms_size; ++i) { - BrotliOptimizeHuffmanCountsForRle(256, mb->literal_histograms[i].data_, - good_for_rle); - } - for (i = 0; i < mb->command_histograms_size; ++i) { - BrotliOptimizeHuffmanCountsForRle(BROTLI_NUM_COMMAND_SYMBOLS, - mb->command_histograms[i].data_, - good_for_rle); - } - for (i = 0; i < mb->distance_histograms_size; ++i) { - BrotliOptimizeHuffmanCountsForRle(num_distance_codes, - mb->distance_histograms[i].data_, - good_for_rle); - } -} - -#if defined(__cplusplus) || defined(c_plusplus) -} /* extern "C" */ -#endif |