backward_references_hq.c | Explore in Territory

/* Copyright 2013 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Function to find backward reference copies. */

#include "backward_references_hq.h"

#include <string.h>  /* memcpy, memset */

#include "../common/constants.h"
#include "../common/platform.h"
#include <brotli/types.h>
#include "command.h"
#include "compound_dictionary.h"
#include "encoder_dict.h"
#include "fast_log.h"
#include "find_match_length.h"
#include "literal_cost.h"
#include "memory.h"
#include "params.h"
#include "prefix.h"
#include "quality.h"

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

/* BrotliCalculateDistanceCodeLimit(BROTLI_MAX_ALLOWED_DISTANCE, 3, 120). */
#define BROTLI_MAX_EFFECTIVE_DISTANCE_ALPHABET_SIZE …

static const float kInfinity = …;  /* ~= 2 ^ 127 */

static const uint32_t kDistanceCacheIndex[] = …;
static const int kDistanceCacheOffset[] = …;

void BrotliInitZopfliNodes(ZopfliNode* array, size_t length) { … }

static BROTLI_INLINE uint32_t ZopfliNodeCopyLength(const ZopfliNode* self) { … }

static BROTLI_INLINE uint32_t ZopfliNodeLengthCode(const ZopfliNode* self) { … }

static BROTLI_INLINE uint32_t ZopfliNodeCopyDistance(const ZopfliNode* self) { … }

static BROTLI_INLINE uint32_t ZopfliNodeDistanceCode(const ZopfliNode* self) { … }

static BROTLI_INLINE uint32_t ZopfliNodeCommandLength(const ZopfliNode* self) { … }

/* Temporary data for ZopfliCostModelSetFromCommands. */
ZopfliCostModelArena;

/* Histogram based cost model for zopflification. */
ZopfliCostModel;

static void InitZopfliCostModel(
    MemoryManager* m, ZopfliCostModel* self, const BrotliDistanceParams* dist,
    size_t num_bytes) { … }

static void CleanupZopfliCostModel(MemoryManager* m, ZopfliCostModel* self) { … }

static void SetCost(const uint32_t* histogram, size_t histogram_size,
                    BROTLI_BOOL literal_histogram, float* cost) { … }

static void ZopfliCostModelSetFromCommands(ZopfliCostModel* self,
                                           size_t position,
                                           const uint8_t* ringbuffer,
                                           size_t ringbuffer_mask,
                                           const Command* commands,
                                           size_t num_commands,
                                           size_t last_insert_len) { … }

static void ZopfliCostModelSetFromLiteralCosts(ZopfliCostModel* self,
                                               size_t position,
                                               const uint8_t* ringbuffer,
                                               size_t ringbuffer_mask) { … }

static BROTLI_INLINE float ZopfliCostModelGetCommandCost(
    const ZopfliCostModel* self, uint16_t cmdcode) { … }

static BROTLI_INLINE float ZopfliCostModelGetDistanceCost(
    const ZopfliCostModel* self, size_t distcode) { … }

static BROTLI_INLINE float ZopfliCostModelGetLiteralCosts(
    const ZopfliCostModel* self, size_t from, size_t to) { … }

static BROTLI_INLINE float ZopfliCostModelGetMinCostCmd(
    const ZopfliCostModel* self) { … }

/* REQUIRES: len >= 2, start_pos <= pos */
/* REQUIRES: cost < kInfinity, nodes[start_pos].cost < kInfinity */
/* Maintains the "ZopfliNode array invariant". */
static BROTLI_INLINE void UpdateZopfliNode(ZopfliNode* nodes, size_t pos,
    size_t start_pos, size_t len, size_t len_code, size_t dist,
    size_t short_code, float cost) { … }

PosData;

/* Maintains the smallest 8 cost difference together with their positions */
StartPosQueue;

static BROTLI_INLINE void InitStartPosQueue(StartPosQueue* self) { … }

static size_t StartPosQueueSize(const StartPosQueue* self) { … }

static void StartPosQueuePush(StartPosQueue* self, const PosData* posdata) { … }

static const PosData* StartPosQueueAt(const StartPosQueue* self, size_t k) { … }

/* Returns the minimum possible copy length that can improve the cost of any */
/* future position. */
static size_t ComputeMinimumCopyLength(const float start_cost,
                                       const ZopfliNode* nodes,
                                       const size_t num_bytes,
                                       const size_t pos) { … }

/* REQUIRES: nodes[pos].cost < kInfinity
   REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
static uint32_t ComputeDistanceShortcut(const size_t block_start,
                                        const size_t pos,
                                        const size_t max_backward_limit,
                                        const size_t gap,
                                        const ZopfliNode* nodes) { … }

/* Fills in dist_cache[0..3] with the last four distances (as defined by
   Section 4. of the Spec) that would be used at (block_start + pos) if we
   used the shortest path of commands from block_start, computed from
   nodes[0..pos]. The last four distances at block_start are in
   starting_dist_cache[0..3].
   REQUIRES: nodes[pos].cost < kInfinity
   REQUIRES: nodes[0..pos] satisfies that "ZopfliNode array invariant". */
static void ComputeDistanceCache(const size_t pos,
                                 const int* starting_dist_cache,
                                 const ZopfliNode* nodes,
                                 int* dist_cache) { … }

/* Maintains "ZopfliNode array invariant" and pushes node to the queue, if it
   is eligible. */
static void EvaluateNode(
    const size_t block_start, const size_t pos, const size_t max_backward_limit,
    const size_t gap, const int* starting_dist_cache,
    const ZopfliCostModel* model, StartPosQueue* queue, ZopfliNode* nodes) { … }

/* Returns longest copy length. */
static size_t UpdateNodes(
    const size_t num_bytes, const size_t block_start, const size_t pos,
    const uint8_t* ringbuffer, const size_t ringbuffer_mask,
    const BrotliEncoderParams* params, const size_t max_backward_limit,
    const int* starting_dist_cache, const size_t num_matches,
    const BackwardMatch* matches, const ZopfliCostModel* model,
    StartPosQueue* queue, ZopfliNode* nodes) { … }

static size_t ComputeShortestPathFromNodes(size_t num_bytes,
    ZopfliNode* nodes) { … }

/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */
void BrotliZopfliCreateCommands(const size_t num_bytes,
    const size_t block_start, const ZopfliNode* nodes, int* dist_cache,
    size_t* last_insert_len, const BrotliEncoderParams* params,
    Command* commands, size_t* num_literals) { … }

static size_t ZopfliIterate(size_t num_bytes, size_t position,
    const uint8_t* ringbuffer, size_t ringbuffer_mask,
    const BrotliEncoderParams* params, const size_t gap, const int* dist_cache,
    const ZopfliCostModel* model, const uint32_t* num_matches,
    const BackwardMatch* matches, ZopfliNode* nodes) { … }

static void MergeMatches(BackwardMatch* dst,
    BackwardMatch* src1, size_t len1, BackwardMatch* src2, size_t len2) { … }

/* REQUIRES: nodes != NULL and len(nodes) >= num_bytes + 1 */
size_t BrotliZopfliComputeShortestPath(MemoryManager* m, size_t num_bytes,
    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
    ContextLut literal_context_lut, const BrotliEncoderParams* params,
    const int* dist_cache, Hasher* hasher, ZopfliNode* nodes) { … }

void BrotliCreateZopfliBackwardReferences(MemoryManager* m, size_t num_bytes,
    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
    ContextLut literal_context_lut, const BrotliEncoderParams* params,
    Hasher* hasher, int* dist_cache, size_t* last_insert_len,
    Command* commands, size_t* num_commands, size_t* num_literals) { … }

void BrotliCreateHqZopfliBackwardReferences(MemoryManager* m, size_t num_bytes,
    size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask,
    ContextLut literal_context_lut, const BrotliEncoderParams* params,
    Hasher* hasher, int* dist_cache, size_t* last_insert_len,
    Command* commands, size_t* num_commands, size_t* num_literals) { … }

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif
chromium/third_party/brotli/enc/backward_references_hq.c
