chromium/third_party/brotli/enc/metablock.c

/* 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(BrotliDistanceParams* dist_params,
    uint32_t npostfix, uint32_t ndirect, BROTLI_BOOL large_window) { … }

static void RecomputeDistancePrefixes(Command* cmds,
                                      size_t num_commands,
                                      const BrotliDistanceParams* orig_params,
                                      const BrotliDistanceParams* new_params) { … }

static BROTLI_BOOL ComputeDistanceCost(const Command* cmds,
                                       size_t num_commands,
                                       const BrotliDistanceParams* orig_params,
                                       const BrotliDistanceParams* new_params,
                                       double* cost,
                                       HistogramDistance* tmp) { … }

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) { … }

#define FN …
#include "metablock_inc.h"  /* NOLINT(build/include) */
#undef FN

#define FN …
#include "metablock_inc.h"  /* NOLINT(build/include) */
#undef FN

#define FN …
#include "metablock_inc.h"  /* NOLINT(build/include) */
#undef FN

#define BROTLI_MAX_STATIC_CONTEXTS …

/* Greedy block splitter for one block category (literal, command or distance).
   Gathers histograms for all context buckets. */
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) { … }

/* 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) { … }

/* 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) { … }

static void MapStaticContexts(MemoryManager* m,
                              size_t num_contexts,
                              const uint32_t* static_context_map,
                              MetaBlockSplit* mb) { … }

GreedyMetablockArena;

static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal(
    MemoryManager* m, GreedyMetablockArena* arena, 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) { … }

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) { … }

void BrotliOptimizeHistograms(uint32_t num_distance_codes,
                              MetaBlockSplit* mb) { … }

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif