// 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]) // #ifdef HAVE_CONFIG_H #include "src/webp/config.h" #endif #include <float.h> #include <math.h> #include "src/dsp/lossless.h" #include "src/dsp/lossless_common.h" #include "src/enc/backward_references_enc.h" #include "src/enc/histogram_enc.h" #include "src/enc/vp8i_enc.h" #include "src/utils/utils.h" #define MAX_BIT_COST … // Number of partitions for the three dominant (literal, red and blue) symbol // costs. #define NUM_PARTITIONS … // The size of the bin-hash corresponding to the three dominant costs. #define BIN_SIZE … // Maximum number of histograms allowed in greedy combining algorithm. #define MAX_HISTO_GREEDY … static void HistogramClear(VP8LHistogram* const p) { … } // Swap two histogram pointers. static void HistogramSwap(VP8LHistogram** const A, VP8LHistogram** const B) { … } static void HistogramCopy(const VP8LHistogram* const src, VP8LHistogram* const dst) { … } int VP8LGetHistogramSize(int cache_bits) { … } void VP8LFreeHistogram(VP8LHistogram* const histo) { … } void VP8LFreeHistogramSet(VP8LHistogramSet* const histo) { … } void VP8LHistogramStoreRefs(const VP8LBackwardRefs* const refs, VP8LHistogram* const histo) { … } void VP8LHistogramCreate(VP8LHistogram* const p, const VP8LBackwardRefs* const refs, int palette_code_bits) { … } void VP8LHistogramInit(VP8LHistogram* const p, int palette_code_bits, int init_arrays) { … } VP8LHistogram* VP8LAllocateHistogram(int cache_bits) { … } // Resets the pointers of the histograms to point to the bit buffer in the set. static void HistogramSetResetPointers(VP8LHistogramSet* const set, int cache_bits) { … } // Returns the total size of the VP8LHistogramSet. static size_t HistogramSetTotalSize(int size, int cache_bits) { … } VP8LHistogramSet* VP8LAllocateHistogramSet(int size, int cache_bits) { … } void VP8LHistogramSetClear(VP8LHistogramSet* const set) { … } // Removes the histogram 'i' from 'set' by setting it to NULL. static void HistogramSetRemoveHistogram(VP8LHistogramSet* const set, int i, int* const num_used) { … } // ----------------------------------------------------------------------------- void VP8LHistogramAddSinglePixOrCopy(VP8LHistogram* const histo, const PixOrCopy* const v, int (*const distance_modifier)(int, int), int distance_modifier_arg0) { … } // ----------------------------------------------------------------------------- // Entropy-related functions. static WEBP_INLINE float BitsEntropyRefine(const VP8LBitEntropy* entropy) { … } float VP8LBitsEntropy(const uint32_t* const array, int n) { … } static float InitialHuffmanCost(void) { … } // Finalize the Huffman cost based on streak numbers and length type (<3 or >=3) static float FinalHuffmanCost(const VP8LStreaks* const stats) { … } // Get the symbol entropy for the distribution 'population'. // Set 'trivial_sym', if there's only one symbol present in the distribution. static float PopulationCost(const uint32_t* const population, int length, uint32_t* const trivial_sym, uint8_t* const is_used) { … } // trivial_at_end is 1 if the two histograms only have one element that is // non-zero: both the zero-th one, or both the last one. static WEBP_INLINE float GetCombinedEntropy(const uint32_t* const X, const uint32_t* const Y, int length, int is_X_used, int is_Y_used, int trivial_at_end) { … } // Estimates the Entropy + Huffman + other block overhead size cost. float VP8LHistogramEstimateBits(VP8LHistogram* const p) { … } // ----------------------------------------------------------------------------- // Various histogram combine/cost-eval functions static int GetCombinedHistogramEntropy(const VP8LHistogram* const a, const VP8LHistogram* const b, float cost_threshold, float* cost) { … } static WEBP_INLINE void HistogramAdd(const VP8LHistogram* const a, const VP8LHistogram* const b, VP8LHistogram* const out) { … } // Performs out = a + b, computing the cost C(a+b) - C(a) - C(b) while comparing // to the threshold value 'cost_threshold'. The score returned is // Score = C(a+b) - C(a) - C(b), where C(a) + C(b) is known and fixed. // Since the previous score passed is 'cost_threshold', we only need to compare // the partial cost against 'cost_threshold + C(a) + C(b)' to possibly bail-out // early. static float HistogramAddEval(const VP8LHistogram* const a, const VP8LHistogram* const b, VP8LHistogram* const out, float cost_threshold) { … } // Same as HistogramAddEval(), except that the resulting histogram // is not stored. Only the cost C(a+b) - C(a) is evaluated. We omit // the term C(b) which is constant over all the evaluations. static float HistogramAddThresh(const VP8LHistogram* const a, const VP8LHistogram* const b, float cost_threshold) { … } // ----------------------------------------------------------------------------- // The structure to keep track of cost range for the three dominant entropy // symbols. DominantCostRange; static void DominantCostRangeInit(DominantCostRange* const c) { … } static void UpdateDominantCostRange( const VP8LHistogram* const h, DominantCostRange* const c) { … } static void UpdateHistogramCost(VP8LHistogram* const h) { … } static int GetBinIdForEntropy(float min, float max, float val) { … } static int GetHistoBinIndex(const VP8LHistogram* const h, const DominantCostRange* const c, int low_effort) { … } // Construct the histograms from backward references. static void HistogramBuild( int xsize, int histo_bits, const VP8LBackwardRefs* const backward_refs, VP8LHistogramSet* const image_histo) { … } // Copies the histograms and computes its bit_cost. static const uint16_t kInvalidHistogramSymbol = …; static void HistogramCopyAndAnalyze(VP8LHistogramSet* const orig_histo, VP8LHistogramSet* const image_histo, int* const num_used, uint16_t* const histogram_symbols) { … } // Partition histograms to different entropy bins for three dominant (literal, // red and blue) symbol costs and compute the histogram aggregate bit_cost. static void HistogramAnalyzeEntropyBin(VP8LHistogramSet* const image_histo, uint16_t* const bin_map, int low_effort) { … } // Merges some histograms with same bin_id together if it's advantageous. // Sets the remaining histograms to NULL. static void HistogramCombineEntropyBin( VP8LHistogramSet* const image_histo, int* num_used, const uint16_t* const clusters, uint16_t* const cluster_mappings, VP8LHistogram* cur_combo, const uint16_t* const bin_map, int num_bins, float combine_cost_factor, int low_effort) { … } // Implement a Lehmer random number generator with a multiplicative constant of // 48271 and a modulo constant of 2^31 - 1. static uint32_t MyRand(uint32_t* const seed) { … } // ----------------------------------------------------------------------------- // Histogram pairs priority queue // Pair of histograms. Negative idx1 value means that pair is out-of-date. HistogramPair; HistoQueue; static int HistoQueueInit(HistoQueue* const histo_queue, const int max_size) { … } static void HistoQueueClear(HistoQueue* const histo_queue) { … } // Pop a specific pair in the queue by replacing it with the last one // and shrinking the queue. static void HistoQueuePopPair(HistoQueue* const histo_queue, HistogramPair* const pair) { … } // Check whether a pair in the queue should be updated as head or not. static void HistoQueueUpdateHead(HistoQueue* const histo_queue, HistogramPair* const pair) { … } // Update the cost diff and combo of a pair of histograms. This needs to be // called when the the histograms have been merged with a third one. static void HistoQueueUpdatePair(const VP8LHistogram* const h1, const VP8LHistogram* const h2, float threshold, HistogramPair* const pair) { … } // Create a pair from indices "idx1" and "idx2" provided its cost // is inferior to "threshold", a negative entropy. // It returns the cost of the pair, or 0. if it superior to threshold. static float HistoQueuePush(HistoQueue* const histo_queue, VP8LHistogram** const histograms, int idx1, int idx2, float threshold) { … } // ----------------------------------------------------------------------------- // Combines histograms by continuously choosing the one with the highest cost // reduction. static int HistogramCombineGreedy(VP8LHistogramSet* const image_histo, int* const num_used) { … } // Perform histogram aggregation using a stochastic approach. // 'do_greedy' is set to 1 if a greedy approach needs to be performed // afterwards, 0 otherwise. static int PairComparison(const void* idx1, const void* idx2) { … } static int HistogramCombineStochastic(VP8LHistogramSet* const image_histo, int* const num_used, int min_cluster_size, int* const do_greedy) { … } // ----------------------------------------------------------------------------- // Histogram refinement // Find the best 'out' histogram for each of the 'in' histograms. // At call-time, 'out' contains the histograms of the clusters. // Note: we assume that out[]->bit_cost_ is already up-to-date. static void HistogramRemap(const VP8LHistogramSet* const in, VP8LHistogramSet* const out, uint16_t* const symbols) { … } static float GetCombineCostFactor(int histo_size, int quality) { … } // Given a HistogramSet 'set', the mapping of clusters 'cluster_mapping' and the // current assignment of the cells in 'symbols', merge the clusters and // assign the smallest possible clusters values. static void OptimizeHistogramSymbols(const VP8LHistogramSet* const set, uint16_t* const cluster_mappings, int num_clusters, uint16_t* const cluster_mappings_tmp, uint16_t* const symbols) { … } static void RemoveEmptyHistograms(VP8LHistogramSet* const image_histo) { … } int VP8LGetHistoImageSymbols(int xsize, int ysize, const VP8LBackwardRefs* const refs, int quality, int low_effort, int histogram_bits, int cache_bits, VP8LHistogramSet* const image_histo, VP8LHistogram* const tmp_histo, uint16_t* const histogram_symbols, const WebPPicture* const pic, int percent_range, int* const percent) { … }
Codebase Browser
godot