backward_references_enc.c | Explore in Territory

// Copyright 2012 Google Inc. All Rights Reserved.
//
// Use of this source code is governed by a BSD-style license
// that can be found in the COPYING file in the root of the source
// tree. An additional intellectual property rights grant can be found
// in the file PATENTS. All contributing project authors may
// be found in the AUTHORS file in the root of the source tree.
// -----------------------------------------------------------------------------
//
// Author: Jyrki Alakuijala ([email protected])
//

#include "src/enc/backward_references_enc.h"

#include <assert.h>
#include <float.h>
#include <math.h>

#include "src/dsp/dsp.h"
#include "src/dsp/lossless.h"
#include "src/dsp/lossless_common.h"
#include "src/enc/histogram_enc.h"
#include "src/enc/vp8i_enc.h"
#include "src/utils/color_cache_utils.h"
#include "src/utils/utils.h"
#include "src/webp/encode.h"

#define MIN_BLOCK_SIZE …

#define MAX_ENTROPY …

// 1M window (4M bytes) minus 120 special codes for short distances.
#define WINDOW_SIZE …

// Minimum number of pixels for which it is cheaper to encode a
// distance + length instead of each pixel as a literal.
#define MIN_LENGTH …

// -----------------------------------------------------------------------------

static const uint8_t plane_to_code_lut[128] = …;

extern int VP8LDistanceToPlaneCode(int xsize, int dist);
int VP8LDistanceToPlaneCode(int xsize, int dist) { … }

// Returns the exact index where array1 and array2 are different. For an index
// inferior or equal to best_len_match, the return value just has to be strictly
// inferior to best_len_match. The current behavior is to return 0 if this index
// is best_len_match, and the index itself otherwise.
// If no two elements are the same, it returns max_limit.
static WEBP_INLINE int FindMatchLength(const uint32_t* const array1,
                                       const uint32_t* const array2,
                                       int best_len_match, int max_limit) { … }

// -----------------------------------------------------------------------------
//  VP8LBackwardRefs

struct PixOrCopyBlock { … };

extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs);
void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs) { … }

void VP8LBackwardRefsClear(VP8LBackwardRefs* const refs) { … }

// Swaps the content of two VP8LBackwardRefs.
static void BackwardRefsSwap(VP8LBackwardRefs* const refs1,
                             VP8LBackwardRefs* const refs2) { … }

void VP8LBackwardRefsInit(VP8LBackwardRefs* const refs, int block_size) { … }

VP8LRefsCursor VP8LRefsCursorInit(const VP8LBackwardRefs* const refs) { … }

void VP8LRefsCursorNextBlock(VP8LRefsCursor* const c) { … }

// Create a new block, either from the free list or allocated
static PixOrCopyBlock* BackwardRefsNewBlock(VP8LBackwardRefs* const refs) { … }

// Return 1 on success, 0 on error.
static int BackwardRefsClone(const VP8LBackwardRefs* const from,
                             VP8LBackwardRefs* const to) { … }

extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs,
                                      const PixOrCopy v);
void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs,
                               const PixOrCopy v) { … }

// -----------------------------------------------------------------------------
// Hash chains

int VP8LHashChainInit(VP8LHashChain* const p, int size) { … }

void VP8LHashChainClear(VP8LHashChain* const p) { … }

// -----------------------------------------------------------------------------

static const uint32_t kHashMultiplierHi = …;
static const uint32_t kHashMultiplierLo = …;

static WEBP_UBSAN_IGNORE_UNSIGNED_OVERFLOW WEBP_INLINE
uint32_t GetPixPairHash64(const uint32_t* const argb) { … }

// Returns the maximum number of hash chain lookups to do for a
// given compression quality. Return value in range [8, 86].
static int GetMaxItersForQuality(int quality) { … }

static int GetWindowSizeForHashChain(int quality, int xsize) { … }

static WEBP_INLINE int MaxFindCopyLength(int len) { … }

int VP8LHashChainFill(VP8LHashChain* const p, int quality,
                      const uint32_t* const argb, int xsize, int ysize,
                      int low_effort, const WebPPicture* const pic,
                      int percent_range, int* const percent) { … }

static WEBP_INLINE void AddSingleLiteral(uint32_t pixel, int use_color_cache,
                                         VP8LColorCache* const hashers,
                                         VP8LBackwardRefs* const refs) { … }

static int BackwardReferencesRle(int xsize, int ysize,
                                 const uint32_t* const argb,
                                 int cache_bits, VP8LBackwardRefs* const refs) { … }

static int BackwardReferencesLz77(int xsize, int ysize,
                                  const uint32_t* const argb, int cache_bits,
                                  const VP8LHashChain* const hash_chain,
                                  VP8LBackwardRefs* const refs) { … }

// Compute an LZ77 by forcing matches to happen within a given distance cost.
// We therefore limit the algorithm to the lowest 32 values in the PlaneCode
// definition.
#define WINDOW_OFFSETS_SIZE_MAX …
static int BackwardReferencesLz77Box(int xsize, int ysize,
                                     const uint32_t* const argb, int cache_bits,
                                     const VP8LHashChain* const hash_chain_best,
                                     VP8LHashChain* hash_chain,
                                     VP8LBackwardRefs* const refs) { … }

// -----------------------------------------------------------------------------

static void BackwardReferences2DLocality(int xsize,
                                         const VP8LBackwardRefs* const refs) { … }

// Evaluate optimal cache bits for the local color cache.
// The input *best_cache_bits sets the maximum cache bits to use (passing 0
// implies disabling the local color cache). The local color cache is also
// disabled for the lower (<= 25) quality.
// Returns 0 in case of memory error.
static int CalculateBestCacheSize(const uint32_t* argb, int quality,
                                  const VP8LBackwardRefs* const refs,
                                  int* const best_cache_bits) { … }

// Update (in-place) backward references for specified cache_bits.
static int BackwardRefsWithLocalCache(const uint32_t* const argb,
                                      int cache_bits,
                                      VP8LBackwardRefs* const refs) { … }

static VP8LBackwardRefs* GetBackwardReferencesLowEffort(
    int width, int height, const uint32_t* const argb,
    int* const cache_bits, const VP8LHashChain* const hash_chain,
    VP8LBackwardRefs* const refs_lz77) { … }

extern int VP8LBackwardReferencesTraceBackwards(
    int xsize, int ysize, const uint32_t* const argb, int cache_bits,
    const VP8LHashChain* const hash_chain,
    const VP8LBackwardRefs* const refs_src, VP8LBackwardRefs* const refs_dst);
static int GetBackwardReferences(int width, int height,
                                 const uint32_t* const argb, int quality,
                                 int lz77_types_to_try, int cache_bits_max,
                                 int do_no_cache,
                                 const VP8LHashChain* const hash_chain,
                                 VP8LBackwardRefs* const refs,
                                 int* const cache_bits_best) { … }

int VP8LGetBackwardReferences(
    int width, int height, const uint32_t* const argb, int quality,
    int low_effort, int lz77_types_to_try, int cache_bits_max, int do_no_cache,
    const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs,
    int* const cache_bits_best, const WebPPicture* const pic, int percent_range,
    int* const percent) { … }
godot/thirdparty/libwebp/src/enc/backward_references_enc.c
