// Copyright 2017 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. // ----------------------------------------------------------------------------- // // Improves a given set of backward references by analyzing its bit cost. // The algorithm is similar to the Zopfli compression algorithm but tailored to // images. // // Author: Vincent Rabaud ([email protected]) // #include <assert.h> #include <float.h> #include "src/dsp/lossless_common.h" #include "src/enc/backward_references_enc.h" #include "src/enc/histogram_enc.h" #include "src/utils/color_cache_utils.h" #include "src/utils/utils.h" #define VALUES_IN_BYTE … extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs); extern int VP8LDistanceToPlaneCode(int xsize, int dist); extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs, const PixOrCopy v); CostModel; static void ConvertPopulationCountTableToBitEstimates( int num_symbols, const uint32_t population_counts[], float output[]) { … } static int CostModelBuild(CostModel* const m, int xsize, int cache_bits, const VP8LBackwardRefs* const refs) { … } static WEBP_INLINE float GetLiteralCost(const CostModel* const m, uint32_t v) { … } static WEBP_INLINE float GetCacheCost(const CostModel* const m, uint32_t idx) { … } static WEBP_INLINE float GetLengthCost(const CostModel* const m, uint32_t length) { … } static WEBP_INLINE float GetDistanceCost(const CostModel* const m, uint32_t distance) { … } static WEBP_INLINE void AddSingleLiteralWithCostModel( const uint32_t* const argb, VP8LColorCache* const hashers, const CostModel* const cost_model, int idx, int use_color_cache, float prev_cost, float* const cost, uint16_t* const dist_array) { … } // ----------------------------------------------------------------------------- // CostManager and interval handling // Empirical value to avoid high memory consumption but good for performance. #define COST_CACHE_INTERVAL_SIZE_MAX … // To perform backward reference every pixel at index index_ is considered and // the cost for the MAX_LENGTH following pixels computed. Those following pixels // at index index_ + k (k from 0 to MAX_LENGTH) have a cost of: // cost_ = distance cost at index + GetLengthCost(cost_model, k) // and the minimum value is kept. GetLengthCost(cost_model, k) is cached in an // array of size MAX_LENGTH. // Instead of performing MAX_LENGTH comparisons per pixel, we keep track of the // minimal values using intervals of constant cost. // An interval is defined by the index_ of the pixel that generated it and // is only useful in a range of indices from start_ to end_ (exclusive), i.e. // it contains the minimum value for pixels between start_ and end_. // Intervals are stored in a linked list and ordered by start_. When a new // interval has a better value, old intervals are split or removed. There are // therefore no overlapping intervals. CostInterval; struct CostInterval { … }; // The GetLengthCost(cost_model, k) are cached in a CostCacheInterval. CostCacheInterval; // This structure is in charge of managing intervals and costs. // It caches the different CostCacheInterval, caches the different // GetLengthCost(cost_model, k) in cost_cache_ and the CostInterval's (whose // count_ is limited by COST_CACHE_INTERVAL_SIZE_MAX). #define COST_MANAGER_MAX_FREE_LIST … CostManager; static void CostIntervalAddToFreeList(CostManager* const manager, CostInterval* const interval) { … } static int CostIntervalIsInFreeList(const CostManager* const manager, const CostInterval* const interval) { … } static void CostManagerInitFreeList(CostManager* const manager) { … } static void DeleteIntervalList(CostManager* const manager, const CostInterval* interval) { … } static void CostManagerClear(CostManager* const manager) { … } static int CostManagerInit(CostManager* const manager, uint16_t* const dist_array, int pix_count, const CostModel* const cost_model) { … } // Given the cost and the position that define an interval, update the cost at // pixel 'i' if it is smaller than the previously computed value. static WEBP_INLINE void UpdateCost(CostManager* const manager, int i, int position, float cost) { … } // Given the cost and the position that define an interval, update the cost for // all the pixels between 'start' and 'end' excluded. static WEBP_INLINE void UpdateCostPerInterval(CostManager* const manager, int start, int end, int position, float cost) { … } // Given two intervals, make 'prev' be the previous one of 'next' in 'manager'. static WEBP_INLINE void ConnectIntervals(CostManager* const manager, CostInterval* const prev, CostInterval* const next) { … } // Pop an interval in the manager. static WEBP_INLINE void PopInterval(CostManager* const manager, CostInterval* const interval) { … } // Update the cost at index i by going over all the stored intervals that // overlap with i. // If 'do_clean_intervals' is set to something different than 0, intervals that // end before 'i' will be popped. static WEBP_INLINE void UpdateCostAtIndex(CostManager* const manager, int i, int do_clean_intervals) { … } // Given a current orphan interval and its previous interval, before // it was orphaned (which can be NULL), set it at the right place in the list // of intervals using the start_ ordering and the previous interval as a hint. static WEBP_INLINE void PositionOrphanInterval(CostManager* const manager, CostInterval* const current, CostInterval* previous) { … } // Insert an interval in the list contained in the manager by starting at // interval_in as a hint. The intervals are sorted by start_ value. static WEBP_INLINE void InsertInterval(CostManager* const manager, CostInterval* const interval_in, float cost, int position, int start, int end) { … } // Given a new cost interval defined by its start at position, its length value // and distance_cost, add its contributions to the previous intervals and costs. // If handling the interval or one of its subintervals becomes to heavy, its // contribution is added to the costs right away. static WEBP_INLINE void PushInterval(CostManager* const manager, float distance_cost, int position, int len) { … } static int BackwardReferencesHashChainDistanceOnly( int xsize, int ysize, const uint32_t* const argb, int cache_bits, const VP8LHashChain* const hash_chain, const VP8LBackwardRefs* const refs, uint16_t* const dist_array) { … } // We pack the path at the end of *dist_array and return // a pointer to this part of the array. Example: // dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232] static void TraceBackwards(uint16_t* const dist_array, int dist_array_size, uint16_t** const chosen_path, int* const chosen_path_size) { … } static int BackwardReferencesHashChainFollowChosenPath( const uint32_t* const argb, int cache_bits, const uint16_t* const chosen_path, int chosen_path_size, const VP8LHashChain* const hash_chain, VP8LBackwardRefs* const refs) { … } // Returns 1 on success. 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); 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) { … }
Codebase Browser
godot