Source code
Revision control
Copy as Markdown
Other Tools
// 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 (vrabaud@google.com)
//
#include <assert.h>
#include <string.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"
#include "src/webp/format_constants.h"
#include "src/webp/types.h"
#define VALUES_IN_BYTE 256
extern void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs);
extern int VP8LDistanceToPlaneCode(int xsize, int dist);
extern void VP8LBackwardRefsCursorAdd(VP8LBackwardRefs* const refs,
const PixOrCopy v);
typedef struct {
uint32_t alpha[VALUES_IN_BYTE];
uint32_t red[VALUES_IN_BYTE];
uint32_t blue[VALUES_IN_BYTE];
uint32_t distance[NUM_DISTANCE_CODES];
uint32_t* literal;
} CostModel;
static void ConvertPopulationCountTableToBitEstimates(
int num_symbols, const uint32_t population_counts[], uint32_t output[]) {
uint32_t sum = 0;
int nonzeros = 0;
int i;
for (i = 0; i < num_symbols; ++i) {
sum += population_counts[i];
if (population_counts[i] > 0) {
++nonzeros;
}
}
if (nonzeros <= 1) {
memset(output, 0, num_symbols * sizeof(*output));
} else {
const uint32_t logsum = VP8LFastLog2(sum);
for (i = 0; i < num_symbols; ++i) {
output[i] = logsum - VP8LFastLog2(population_counts[i]);
}
}
}
static int CostModelBuild(CostModel* const m, int xsize, int cache_bits,
const VP8LBackwardRefs* const refs) {
int ok = 0;
VP8LHistogram* const histo = VP8LAllocateHistogram(cache_bits);
if (histo == NULL) goto Error;
// The following code is similar to VP8LHistogramCreate but converts the
// distance to plane code.
VP8LHistogramInit(histo, cache_bits, /*init_arrays=*/ 1);
VP8LHistogramStoreRefs(refs, VP8LDistanceToPlaneCode, xsize, histo);
ConvertPopulationCountTableToBitEstimates(
VP8LHistogramNumCodes(histo->palette_code_bits), histo->literal,
m->literal);
ConvertPopulationCountTableToBitEstimates(
VALUES_IN_BYTE, histo->red, m->red);
ConvertPopulationCountTableToBitEstimates(
VALUES_IN_BYTE, histo->blue, m->blue);
ConvertPopulationCountTableToBitEstimates(
VALUES_IN_BYTE, histo->alpha, m->alpha);
ConvertPopulationCountTableToBitEstimates(
NUM_DISTANCE_CODES, histo->distance, m->distance);
ok = 1;
Error:
VP8LFreeHistogram(histo);
return ok;
}
static WEBP_INLINE int64_t GetLiteralCost(const CostModel* const m,
uint32_t v) {
return (int64_t)m->alpha[v >> 24] + m->red[(v >> 16) & 0xff] +
m->literal[(v >> 8) & 0xff] + m->blue[v & 0xff];
}
static WEBP_INLINE int64_t GetCacheCost(const CostModel* const m,
uint32_t idx) {
const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx;
return (int64_t)m->literal[literal_idx];
}
static WEBP_INLINE int64_t GetLengthCost(const CostModel* const m,
uint32_t length) {
int code, extra_bits;
VP8LPrefixEncodeBits(length, &code, &extra_bits);
return (int64_t)m->literal[VALUES_IN_BYTE + code] +
((int64_t)extra_bits << LOG_2_PRECISION_BITS);
}
static WEBP_INLINE int64_t GetDistanceCost(const CostModel* const m,
uint32_t distance) {
int code, extra_bits;
VP8LPrefixEncodeBits(distance, &code, &extra_bits);
return (int64_t)m->distance[code] +
((int64_t)extra_bits << LOG_2_PRECISION_BITS);
}
static WEBP_INLINE void AddSingleLiteralWithCostModel(
const uint32_t* const argb, VP8LColorCache* const hashers,
const CostModel* const cost_model, int idx, int use_color_cache,
int64_t prev_cost, int64_t* const cost, uint16_t* const dist_array) {
int64_t cost_val = prev_cost;
const uint32_t color = argb[idx];
const int ix = use_color_cache ? VP8LColorCacheContains(hashers, color) : -1;
if (ix >= 0) {
// use_color_cache is true and hashers contains color
cost_val += DivRound(GetCacheCost(cost_model, ix) * 68, 100);
} else {
if (use_color_cache) VP8LColorCacheInsert(hashers, color);
cost_val += DivRound(GetLiteralCost(cost_model, color) * 82, 100);
}
if (cost[idx] > cost_val) {
cost[idx] = cost_val;
dist_array[idx] = 1; // only one is inserted.
}
}
// -----------------------------------------------------------------------------
// CostManager and interval handling
// Empirical value to avoid high memory consumption but good for performance.
#define COST_CACHE_INTERVAL_SIZE_MAX 500
// 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.
typedef struct CostInterval CostInterval;
struct CostInterval {
int64_t cost;
int start;
int end;
int index;
CostInterval* previous;
CostInterval* next;
};
// The GetLengthCost(cost_model, k) are cached in a CostCacheInterval.
typedef struct {
int64_t cost;
int start;
int end; // Exclusive.
} 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 10
typedef struct {
CostInterval* head;
int count; // The number of stored intervals.
CostCacheInterval* cache_intervals;
size_t cache_intervals_size;
// Contains the GetLengthCost(cost_model, k).
int64_t cost_cache[MAX_LENGTH];
int64_t* costs;
uint16_t* dist_array;
// Most of the time, we only need few intervals -> use a free-list, to avoid
// fragmentation with small allocs in most common cases.
CostInterval intervals[COST_MANAGER_MAX_FREE_LIST];
CostInterval* free_intervals;
// These are regularly malloc'd remains. This list can't grow larger than than
// size COST_CACHE_INTERVAL_SIZE_MAX - COST_MANAGER_MAX_FREE_LIST, note.
CostInterval* recycled_intervals;
} CostManager;
static void CostIntervalAddToFreeList(CostManager* const manager,
CostInterval* const interval) {
interval->next = manager->free_intervals;
manager->free_intervals = interval;
}
static int CostIntervalIsInFreeList(const CostManager* const manager,
const CostInterval* const interval) {
return (interval >= &manager->intervals[0] &&
interval <= &manager->intervals[COST_MANAGER_MAX_FREE_LIST - 1]);
}
static void CostManagerInitFreeList(CostManager* const manager) {
int i;
manager->free_intervals = NULL;
for (i = 0; i < COST_MANAGER_MAX_FREE_LIST; ++i) {
CostIntervalAddToFreeList(manager, &manager->intervals[i]);
}
}
static void DeleteIntervalList(CostManager* const manager,
const CostInterval* interval) {
while (interval != NULL) {
const CostInterval* const next = interval->next;
if (!CostIntervalIsInFreeList(manager, interval)) {
WebPSafeFree((void*)interval);
} // else: do nothing
interval = next;
}
}
static void CostManagerClear(CostManager* const manager) {
if (manager == NULL) return;
WebPSafeFree(manager->costs);
WebPSafeFree(manager->cache_intervals);
// Clear the interval lists.
DeleteIntervalList(manager, manager->head);
manager->head = NULL;
DeleteIntervalList(manager, manager->recycled_intervals);
manager->recycled_intervals = NULL;
// Reset pointers, 'count' and 'cache_intervals_size'.
memset(manager, 0, sizeof(*manager));
CostManagerInitFreeList(manager);
}
static int CostManagerInit(CostManager* const manager,
uint16_t* const dist_array, int pix_count,
const CostModel* const cost_model) {
int i;
const int cost_cache_size = (pix_count > MAX_LENGTH) ? MAX_LENGTH : pix_count;
manager->costs = NULL;
manager->cache_intervals = NULL;
manager->head = NULL;
manager->recycled_intervals = NULL;
manager->count = 0;
manager->dist_array = dist_array;
CostManagerInitFreeList(manager);
// Fill in the 'cost_cache'.
// Has to be done in two passes due to a GCC bug on i686
for (i = 0; i < cost_cache_size; ++i) {
manager->cost_cache[i] = GetLengthCost(cost_model, i);
}
manager->cache_intervals_size = 1;
for (i = 1; i < cost_cache_size; ++i) {
// Get the number of bound intervals.
if (manager->cost_cache[i] != manager->cost_cache[i - 1]) {
++manager->cache_intervals_size;
}
}
// With the current cost model, we usually have below 20 intervals.
// The worst case scenario with a cost model would be if every length has a
// different cost, hence MAX_LENGTH but that is impossible with the current
// implementation that spirals around a pixel.
assert(manager->cache_intervals_size <= MAX_LENGTH);
manager->cache_intervals = (CostCacheInterval*)WebPSafeMalloc(
manager->cache_intervals_size, sizeof(*manager->cache_intervals));
if (manager->cache_intervals == NULL) {
CostManagerClear(manager);
return 0;
}
// Fill in the 'cache_intervals'.
{
CostCacheInterval* cur = manager->cache_intervals;
// Consecutive values in 'cost_cache' are compared and if a big enough
// difference is found, a new interval is created and bounded.
cur->start = 0;
cur->end = 1;
cur->cost = manager->cost_cache[0];
for (i = 1; i < cost_cache_size; ++i) {
const int64_t cost_val = manager->cost_cache[i];
if (cost_val != cur->cost) {
++cur;
// Initialize an interval.
cur->start = i;
cur->cost = cost_val;
}
cur->end = i + 1;
}
assert((size_t)(cur - manager->cache_intervals) + 1 ==
manager->cache_intervals_size);
}
manager->costs =
(int64_t*)WebPSafeMalloc(pix_count, sizeof(*manager->costs));
if (manager->costs == NULL) {
CostManagerClear(manager);
return 0;
}
// Set the initial 'costs' to INT64_MAX for every pixel as we will keep the
// minimum.
for (i = 0; i < pix_count; ++i) manager->costs[i] = WEBP_INT64_MAX;
return 1;
}
// 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, int64_t cost) {
const int k = i - position;
assert(k >= 0 && k < MAX_LENGTH);
if (manager->costs[i] > cost) {
manager->costs[i] = cost;
manager->dist_array[i] = k + 1;
}
}
// 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,
int64_t cost) {
int i;
for (i = start; i < end; ++i) UpdateCost(manager, i, position, 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) {
if (prev != NULL) {
prev->next = next;
} else {
manager->head = next;
}
if (next != NULL) next->previous = prev;
}
// Pop an interval in the manager.
static WEBP_INLINE void PopInterval(CostManager* const manager,
CostInterval* const interval) {
if (interval == NULL) return;
ConnectIntervals(manager, interval->previous, interval->next);
if (CostIntervalIsInFreeList(manager, interval)) {
CostIntervalAddToFreeList(manager, interval);
} else { // recycle regularly malloc'd intervals too
interval->next = manager->recycled_intervals;
manager->recycled_intervals = interval;
}
--manager->count;
assert(manager->count >= 0);
}
// 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) {
CostInterval* current = manager->head;
while (current != NULL && current->start <= i) {
CostInterval* const next = current->next;
if (current->end <= i) {
if (do_clean_intervals) {
// We have an outdated interval, remove it.
PopInterval(manager, current);
}
} else {
UpdateCost(manager, i, current->index, current->cost);
}
current = next;
}
}
// 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) {
assert(current != NULL);
if (previous == NULL) previous = manager->head;
while (previous != NULL && current->start < previous->start) {
previous = previous->previous;
}
while (previous != NULL && previous->next != NULL &&
previous->next->start < current->start) {
previous = previous->next;
}
if (previous != NULL) {
ConnectIntervals(manager, current, previous->next);
} else {
ConnectIntervals(manager, current, manager->head);
}
ConnectIntervals(manager, previous, current);
}
// 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,
int64_t cost, int position, int start,
int end) {
CostInterval* interval_new;
if (start >= end) return;
if (manager->count >= COST_CACHE_INTERVAL_SIZE_MAX) {
// Serialize the interval if we cannot store it.
UpdateCostPerInterval(manager, start, end, position, cost);
return;
}
if (manager->free_intervals != NULL) {
interval_new = manager->free_intervals;
manager->free_intervals = interval_new->next;
} else if (manager->recycled_intervals != NULL) {
interval_new = manager->recycled_intervals;
manager->recycled_intervals = interval_new->next;
} else { // malloc for good
interval_new = (CostInterval*)WebPSafeMalloc(1, sizeof(*interval_new));
if (interval_new == NULL) {
// Write down the interval if we cannot create it.
UpdateCostPerInterval(manager, start, end, position, cost);
return;
}
}
interval_new->cost = cost;
interval_new->index = position;
interval_new->start = start;
interval_new->end = end;
PositionOrphanInterval(manager, interval_new, interval_in);
++manager->count;
}
// 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,
int64_t distance_cost, int position,
int len) {
size_t i;
CostInterval* interval = manager->head;
CostInterval* interval_next;
const CostCacheInterval* const cost_cache_intervals =
manager->cache_intervals;
// If the interval is small enough, no need to deal with the heavy
// interval logic, just serialize it right away. This constant is empirical.
const int kSkipDistance = 10;
if (len < kSkipDistance) {
int j;
for (j = position; j < position + len; ++j) {
const int k = j - position;
int64_t cost_tmp;
assert(k >= 0 && k < MAX_LENGTH);
cost_tmp = distance_cost + manager->cost_cache[k];
if (manager->costs[j] > cost_tmp) {
manager->costs[j] = cost_tmp;
manager->dist_array[j] = k + 1;
}
}
return;
}
for (i = 0; i < manager->cache_intervals_size &&
cost_cache_intervals[i].start < len;
++i) {
// Define the intersection of the ith interval with the new one.
int start = position + cost_cache_intervals[i].start;
const int end = position + (cost_cache_intervals[i].end > len
? len
: cost_cache_intervals[i].end);
const int64_t cost = distance_cost + cost_cache_intervals[i].cost;
for (; interval != NULL && interval->start < end;
interval = interval_next) {
interval_next = interval->next;
// Make sure we have some overlap
if (start >= interval->end) continue;
if (cost >= interval->cost) {
// When intervals are represented, the lower, the better.
// [**********************************************************[
// start end
// [----------------------------------[
// interval->start interval->end
// If we are worse than what we already have, add whatever we have so
// far up to interval.
const int start_new = interval->end;
InsertInterval(manager, interval, cost, position, start,
interval->start);
start = start_new;
if (start >= end) break;
continue;
}
if (start <= interval->start) {
if (interval->end <= end) {
// [----------------------------------[
// interval->start interval->end
// [**************************************************************[
// start end
// We can safely remove the old interval as it is fully included.
PopInterval(manager, interval);
} else {
// [------------------------------------[
// interval->start interval->end
// [*****************************[
// start end
interval->start = end;
break;
}
} else {
if (end < interval->end) {
// [--------------------------------------------------------------[
// interval->start interval->end
// [*****************************[
// start end
// We have to split the old interval as it fully contains the new one.
const int end_original = interval->end;
interval->end = start;
InsertInterval(manager, interval, interval->cost, interval->index,
end, end_original);
interval = interval->next;
break;
} else {
// [------------------------------------[
// interval->start interval->end
// [*****************************[
// start end
interval->end = start;
}
}
}
// Insert the remaining interval from start to end.
InsertInterval(manager, interval, cost, position, start, end);
}
}
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) {
int i;
int ok = 0;
int cc_init = 0;
const int pix_count = xsize * ysize;
const int use_color_cache = (cache_bits > 0);
const size_t literal_array_size =
sizeof(*((CostModel*)NULL)->literal) * VP8LHistogramNumCodes(cache_bits);
const size_t cost_model_size = sizeof(CostModel) + literal_array_size;
CostModel* const cost_model =
(CostModel*)WebPSafeCalloc(1ULL, cost_model_size);
VP8LColorCache hashers;
CostManager* cost_manager =
(CostManager*)WebPSafeCalloc(1ULL, sizeof(*cost_manager));
int offset_prev = -1, len_prev = -1;
int64_t offset_cost = -1;
int first_offset_is_constant = -1; // initialized with 'impossible' value
int reach = 0;
if (cost_model == NULL || cost_manager == NULL) goto Error;
cost_model->literal = (uint32_t*)(cost_model + 1);
if (use_color_cache) {
cc_init = VP8LColorCacheInit(&hashers, cache_bits);
if (!cc_init) goto Error;
}
if (!CostModelBuild(cost_model, xsize, cache_bits, refs)) {
goto Error;
}
if (!CostManagerInit(cost_manager, dist_array, pix_count, cost_model)) {
goto Error;
}
// We loop one pixel at a time, but store all currently best points to
// non-processed locations from this point.
dist_array[0] = 0;
// Add first pixel as literal.
AddSingleLiteralWithCostModel(argb, &hashers, cost_model, /*idx=*/0,
use_color_cache, /*prev_cost=*/0,
cost_manager->costs, dist_array);
for (i = 1; i < pix_count; ++i) {
const int64_t prev_cost = cost_manager->costs[i - 1];
int offset, len;
VP8LHashChainFindCopy(hash_chain, i, &offset, &len);
// Try adding the pixel as a literal.
AddSingleLiteralWithCostModel(argb, &hashers, cost_model, i,
use_color_cache, prev_cost,
cost_manager->costs, dist_array);
// If we are dealing with a non-literal.
if (len >= 2) {
if (offset != offset_prev) {
const int code = VP8LDistanceToPlaneCode(xsize, offset);
offset_cost = GetDistanceCost(cost_model, code);
first_offset_is_constant = 1;
PushInterval(cost_manager, prev_cost + offset_cost, i, len);
} else {
assert(offset_cost >= 0);
assert(len_prev >= 0);
assert(first_offset_is_constant == 0 || first_offset_is_constant == 1);
// Instead of considering all contributions from a pixel i by calling:
// PushInterval(cost_manager, prev_cost + offset_cost, i, len);
// we optimize these contributions in case offset_cost stays the same
// for consecutive pixels. This describes a set of pixels similar to a
// previous set (e.g. constant color regions).
if (first_offset_is_constant) {
reach = i - 1 + len_prev - 1;
first_offset_is_constant = 0;
}
if (i + len - 1 > reach) {
// We can only be go further with the same offset if the previous
// length was maxed, hence len_prev == len == MAX_LENGTH.
// TODO(vrabaud), bump i to the end right away (insert cache and
// update cost).
// TODO(vrabaud), check if one of the points in between does not have
// a lower cost.
// Already consider the pixel at "reach" to add intervals that are
// better than whatever we add.
int offset_j, len_j = 0;
int j;
assert(len == MAX_LENGTH || len == pix_count - i);
// Figure out the last consecutive pixel within [i, reach + 1] with
// the same offset.
for (j = i; j <= reach; ++j) {
VP8LHashChainFindCopy(hash_chain, j + 1, &offset_j, &len_j);
if (offset_j != offset) {
VP8LHashChainFindCopy(hash_chain, j, &offset_j, &len_j);
break;
}
}
// Update the cost at j - 1 and j.
UpdateCostAtIndex(cost_manager, j - 1, 0);
UpdateCostAtIndex(cost_manager, j, 0);
PushInterval(cost_manager, cost_manager->costs[j - 1] + offset_cost,
j, len_j);
reach = j + len_j - 1;
}
}
}
UpdateCostAtIndex(cost_manager, i, 1);
offset_prev = offset;
len_prev = len;
}
ok = !refs->error;
Error:
if (cc_init) VP8LColorCacheClear(&hashers);
CostManagerClear(cost_manager);
WebPSafeFree(cost_model);
WebPSafeFree(cost_manager);
return ok;
}
// 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) {
uint16_t* path = dist_array + dist_array_size;
uint16_t* cur = dist_array + dist_array_size - 1;
while (cur >= dist_array) {
const int k = *cur;
--path;
*path = k;
cur -= k;
}
*chosen_path = path;
*chosen_path_size = (int)(dist_array + dist_array_size - path);
}
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) {
const int use_color_cache = (cache_bits > 0);
int ix;
int i = 0;
int ok = 0;
int cc_init = 0;
VP8LColorCache hashers;
if (use_color_cache) {
cc_init = VP8LColorCacheInit(&hashers, cache_bits);
if (!cc_init) goto Error;
}
VP8LClearBackwardRefs(refs);
for (ix = 0; ix < chosen_path_size; ++ix) {
const int len = chosen_path[ix];
if (len != 1) {
int k;
const int offset = VP8LHashChainFindOffset(hash_chain, i);
VP8LBackwardRefsCursorAdd(refs, PixOrCopyCreateCopy(offset, len));
if (use_color_cache) {
for (k = 0; k < len; ++k) {
VP8LColorCacheInsert(&hashers, argb[i + k]);
}
}
i += len;
} else {
PixOrCopy v;
const int idx =
use_color_cache ? VP8LColorCacheContains(&hashers, argb[i]) : -1;
if (idx >= 0) {
// use_color_cache is true and hashers contains argb[i]
// push pixel as a color cache index
v = PixOrCopyCreateCacheIdx(idx);
} else {
if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
v = PixOrCopyCreateLiteral(argb[i]);
}
VP8LBackwardRefsCursorAdd(refs, v);
++i;
}
}
ok = !refs->error;
Error:
if (cc_init) VP8LColorCacheClear(&hashers);
return ok;
}
// 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) {
int ok = 0;
const int dist_array_size = xsize * ysize;
uint16_t* chosen_path = NULL;
int chosen_path_size = 0;
uint16_t* dist_array =
(uint16_t*)WebPSafeMalloc(dist_array_size, sizeof(*dist_array));
if (dist_array == NULL) goto Error;
if (!BackwardReferencesHashChainDistanceOnly(
xsize, ysize, argb, cache_bits, hash_chain, refs_src, dist_array)) {
goto Error;
}
TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size);
if (!BackwardReferencesHashChainFollowChosenPath(
argb, cache_bits, chosen_path, chosen_path_size, hash_chain,
refs_dst)) {
goto Error;
}
ok = 1;
Error:
WebPSafeFree(dist_array);
return ok;
}