tor-browser

backward_references_cost_enc.c (29637B)

---

// 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
 // related to https://gcc.gnu.org/bugzilla/show_bug.cgi?id=323
 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;
}