src/third_party/libwebp/enc/backward_references.c

   1 // Copyright 2012 Google Inc. All Rights Reserved.
   2 //
   3 // Use of this source code is governed by a BSD-style license
   4 // that can be found in the COPYING file in the root of the source
   5 // tree. An additional intellectual property rights grant can be found
   6 // in the file PATENTS. All contributing project authors may
   7 // be found in the AUTHORS file in the root of the source tree.
   8 // -----------------------------------------------------------------------------
   9 //
  10 // Author: Jyrki Alakuijala (jyrki@google.com)
  11 //
  12
  13 #include <assert.h>
  14 #include <math.h>
  15 #include <stdio.h>
  16
  17 #include "./backward_references.h"
  18 #include "./histogram.h"
  19 #include "../dsp/lossless.h"
  20 #include "../utils/color_cache.h"
  21 #include "../utils/utils.h"
  22
  23 #define VALUES_IN_BYTE 256
  24
  25 #define HASH_BITS 18
  26 #define HASH_SIZE (1 << HASH_BITS)
  27 #define HASH_MULTIPLIER (0xc6a4a7935bd1e995ULL)
  28
  29 // 1M window (4M bytes) minus 120 special codes for short distances.
  30 #define WINDOW_SIZE ((1 << 20) - 120)
  31
  32 // Bounds for the match length.
  33 #define MIN_LENGTH 2
  34 #define MAX_LENGTH 4096
  35
  36 typedef struct {
  37   // Stores the most recently added position with the given hash value.
  38   int32_t hash_to_first_index_[HASH_SIZE];
  39   // chain_[pos] stores the previous position with the same hash value
  40   // for every pixel in the image.
  41   int32_t* chain_;
  42 } HashChain;
  43
  44 // -----------------------------------------------------------------------------
  45
  46 static const uint8_t plane_to_code_lut[128] = {
  47  96,   73,  55,  39,  23,  13,   5,  1,  255, 255, 255, 255, 255, 255, 255, 255,
  48  101,  78,  58,  42,  26,  16,   8,  2,    0,   3,  9,   17,  27,  43,  59,  79,
  49  102,  86,  62,  46,  32,  20,  10,  6,    4,   7,  11,  21,  33,  47,  63,  87,
  50  105,  90,  70,  52,  37,  28,  18,  14,  12,  15,  19,  29,  38,  53,  71,  91,
  51  110,  99,  82,  66,  48,  35,  30,  24,  22,  25,  31,  36,  49,  67,  83, 100,
  52  115, 108,  94,  76,  64,  50,  44,  40,  34,  41,  45,  51,  65,  77,  95, 109,
  53  118, 113, 103,  92,  80,  68,  60,  56,  54,  57,  61,  69,  81,  93, 104, 114,
  54  119, 116, 111, 106,  97,  88,  84,  74,  72,  75,  85,  89,  98, 107, 112, 117
  55 };
  56
  57 static int DistanceToPlaneCode(int xsize, int dist) {
  58   const int yoffset = dist / xsize;
  59   const int xoffset = dist - yoffset * xsize;
  60   if (xoffset <= 8 && yoffset < 8) {
  61     return plane_to_code_lut[yoffset * 16 + 8 - xoffset] + 1;
  62   } else if (xoffset > xsize - 8 && yoffset < 7) {
  63     return plane_to_code_lut[(yoffset + 1) * 16 + 8 + (xsize - xoffset)] + 1;
  64   }
  65   return dist + 120;
  66 }
  67
  68 static WEBP_INLINE int FindMatchLength(const uint32_t* const array1,
  69                                        const uint32_t* const array2,
  70                                        const int max_limit) {
  71   int match_len = 0;
  72   while (match_len < max_limit && array1[match_len] == array2[match_len]) {
  73     ++match_len;
  74   }
  75   return match_len;
  76 }
  77
  78 // -----------------------------------------------------------------------------
  79 //  VP8LBackwardRefs
  80
  81 void VP8LInitBackwardRefs(VP8LBackwardRefs* const refs) {
  82   if (refs != NULL) {
  83     refs->refs = NULL;
  84     refs->size = 0;
  85     refs->max_size = 0;
  86   }
  87 }
  88
  89 void VP8LClearBackwardRefs(VP8LBackwardRefs* const refs) {
  90   if (refs != NULL) {
  91     free(refs->refs);
  92     VP8LInitBackwardRefs(refs);
  93   }
  94 }
  95
  96 int VP8LBackwardRefsAlloc(VP8LBackwardRefs* const refs, int max_size) {
  97   assert(refs != NULL);
  98   refs->size = 0;
  99   refs->max_size = 0;
 100   refs->refs = (PixOrCopy*)WebPSafeMalloc((uint64_t)max_size,
 101                                           sizeof(*refs->refs));
 102   if (refs->refs == NULL) return 0;
 103   refs->max_size = max_size;
 104   return 1;
 105 }
 106
 107 // -----------------------------------------------------------------------------
 108 // Hash chains
 109
 110 static WEBP_INLINE uint64_t GetPixPairHash64(const uint32_t* const argb) {
 111   uint64_t key = ((uint64_t)(argb[1]) << 32) | argb[0];
 112   key = (key * HASH_MULTIPLIER) >> (64 - HASH_BITS);
 113   return key;
 114 }
 115
 116 static int HashChainInit(HashChain* const p, int size) {
 117   int i;
 118   p->chain_ = (int*)WebPSafeMalloc((uint64_t)size, sizeof(*p->chain_));
 119   if (p->chain_ == NULL) {
 120     return 0;
 121   }
 122   for (i = 0; i < size; ++i) {
 123     p->chain_[i] = -1;
 124   }
 125   for (i = 0; i < HASH_SIZE; ++i) {
 126     p->hash_to_first_index_[i] = -1;
 127   }
 128   return 1;
 129 }
 130
 131 static void HashChainDelete(HashChain* const p) {
 132   if (p != NULL) {
 133     free(p->chain_);
 134     free(p);
 135   }
 136 }
 137
 138 // Insertion of two pixels at a time.
 139 static void HashChainInsert(HashChain* const p,
 140                             const uint32_t* const argb, int pos) {
 141   const uint64_t hash_code = GetPixPairHash64(argb);
 142   p->chain_[pos] = p->hash_to_first_index_[hash_code];
 143   p->hash_to_first_index_[hash_code] = pos;
 144 }
 145
 146 static void GetParamsForHashChainFindCopy(int quality, int xsize,
 147                                           int cache_bits, int* window_size,
 148                                           int* iter_pos, int* iter_limit) {
 149   const int iter_mult = (quality < 27) ? 1 : 1 + ((quality - 27) >> 4);
 150   const int iter_neg = -iter_mult * (quality >> 1);
 151   // Limit the backward-ref window size for lower qualities.
 152   const int max_window_size = (quality > 50) ? WINDOW_SIZE
 153                             : (quality > 25) ? (xsize << 8)
 154                             : (xsize << 4);
 155   assert(xsize > 0);
 156   *window_size = (max_window_size > WINDOW_SIZE) ? WINDOW_SIZE
 157                : max_window_size;
 158   *iter_pos = 8 + (quality >> 3);
 159   // For lower entropy images, the rigourous search loop in HashChainFindCopy
 160   // can be relaxed.
 161   *iter_limit = (cache_bits > 0) ? iter_neg : iter_neg / 2;
 162 }
 163
 164 static int HashChainFindCopy(const HashChain* const p,
 165                              int base_position, int xsize_signed,
 166                              const uint32_t* const argb, int maxlen,
 167                              int window_size, int iter_pos, int iter_limit,
 168                              int* const distance_ptr,
 169                              int* const length_ptr) {
 170   const uint32_t* const argb_start = argb + base_position;
 171   uint64_t best_val = 0;
 172   uint32_t best_length = 1;
 173   uint32_t best_distance = 0;
 174   const uint32_t xsize = (uint32_t)xsize_signed;
 175   const int min_pos =
 176       (base_position > window_size) ? base_position - window_size : 0;
 177   int pos;
 178   assert(xsize > 0);
 179   for (pos = p->hash_to_first_index_[GetPixPairHash64(argb_start)];
 180        pos >= min_pos;
 181        pos = p->chain_[pos]) {
 182     uint64_t val;
 183     uint32_t curr_length;
 184     uint32_t distance;
 185     if (iter_pos < 0) {
 186       if (iter_pos < iter_limit || best_val >= 0xff0000) {
 187         break;
 188       }
 189     }
 190     --iter_pos;
 191     if (argb[pos + best_length - 1] != argb_start[best_length - 1]) {
 192       continue;
 193     }
 194     curr_length = FindMatchLength(argb + pos, argb_start, maxlen);
 195     if (curr_length < best_length) {
 196       continue;
 197     }
 198     distance = (uint32_t)(base_position - pos);
 199     val = curr_length << 16;
 200     // Favoring 2d locality here gives savings for certain images.
 201     if (distance < 9 * xsize) {
 202       const uint32_t y = distance / xsize;
 203       uint32_t x = distance % xsize;
 204       if (x > (xsize >> 1)) {
 205         x = xsize - x;
 206       }
 207       if (x <= 7) {
 208         val += 9 * 9 + 9 * 9;
 209         val -= y * y + x * x;
 210       }
 211     }
 212     if (best_val < val) {
 213       best_val = val;
 214       best_length = curr_length;
 215       best_distance = distance;
 216       if (curr_length >= MAX_LENGTH) {
 217         break;
 218       }
 219       if ((best_distance == 1 || distance == xsize) &&
 220           best_length >= 128) {
 221         break;
 222       }
 223     }
 224   }
 225   *distance_ptr = (int)best_distance;
 226   *length_ptr = best_length;
 227   return (best_length >= MIN_LENGTH);
 228 }
 229
 230 static WEBP_INLINE void PushBackCopy(VP8LBackwardRefs* const refs, int length) {
 231   int size = refs->size;
 232   while (length >= MAX_LENGTH) {
 233     refs->refs[size++] = PixOrCopyCreateCopy(1, MAX_LENGTH);
 234     length -= MAX_LENGTH;
 235   }
 236   if (length > 0) {
 237     refs->refs[size++] = PixOrCopyCreateCopy(1, length);
 238   }
 239   refs->size = size;
 240 }
 241
 242 static void BackwardReferencesRle(int xsize, int ysize,
 243                                   const uint32_t* const argb,
 244                                   VP8LBackwardRefs* const refs) {
 245   const int pix_count = xsize * ysize;
 246   int match_len = 0;
 247   int i;
 248   refs->size = 0;
 249   PushBackCopy(refs, match_len);    // i=0 case
 250   refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[0]);
 251   for (i = 1; i < pix_count; ++i) {
 252     if (argb[i] == argb[i - 1]) {
 253       ++match_len;
 254     } else {
 255       PushBackCopy(refs, match_len);
 256       match_len = 0;
 257       refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[i]);
 258     }
 259   }
 260   PushBackCopy(refs, match_len);
 261 }
 262
 263 static int BackwardReferencesHashChain(int xsize, int ysize,
 264                                        const uint32_t* const argb,
 265                                        int cache_bits, int quality,
 266                                        VP8LBackwardRefs* const refs) {
 267   int i;
 268   int ok = 0;
 269   int cc_init = 0;
 270   const int use_color_cache = (cache_bits > 0);
 271   const int pix_count = xsize * ysize;
 272   HashChain* const hash_chain = (HashChain*)malloc(sizeof(*hash_chain));
 273   VP8LColorCache hashers;
 274   int window_size = WINDOW_SIZE;
 275   int iter_pos = 1;
 276   int iter_limit = -1;
 277
 278   if (hash_chain == NULL) return 0;
 279   if (use_color_cache) {
 280     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
 281     if (!cc_init) goto Error;
 282   }
 283
 284   if (!HashChainInit(hash_chain, pix_count)) goto Error;
 285
 286   refs->size = 0;
 287   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
 288                                 &window_size, &iter_pos, &iter_limit);
 289   for (i = 0; i < pix_count; ) {
 290     // Alternative#1: Code the pixels starting at 'i' using backward reference.
 291     int offset = 0;
 292     int len = 0;
 293     if (i < pix_count - 1) {  // FindCopy(i,..) reads pixels at [i] and [i + 1].
 294       int maxlen = pix_count - i;
 295       if (maxlen > MAX_LENGTH) {
 296         maxlen = MAX_LENGTH;
 297       }
 298       HashChainFindCopy(hash_chain, i, xsize, argb, maxlen,
 299                         window_size, iter_pos, iter_limit,
 300                         &offset, &len);
 301     }
 302     if (len >= MIN_LENGTH) {
 303       // Alternative#2: Insert the pixel at 'i' as literal, and code the
 304       // pixels starting at 'i + 1' using backward reference.
 305       int offset2 = 0;
 306       int len2 = 0;
 307       int k;
 308       HashChainInsert(hash_chain, &argb[i], i);
 309       if (i < pix_count - 2) {  // FindCopy(i+1,..) reads [i + 1] and [i + 2].
 310         int maxlen = pix_count - (i + 1);
 311         if (maxlen > MAX_LENGTH) {
 312           maxlen = MAX_LENGTH;
 313         }
 314         HashChainFindCopy(hash_chain, i + 1, xsize, argb, maxlen,
 315                           window_size, iter_pos, iter_limit,
 316                           &offset2, &len2);
 317         if (len2 > len + 1) {
 318           const uint32_t pixel = argb[i];
 319           // Alternative#2 is a better match. So push pixel at 'i' as literal.
 320           if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) {
 321             const int ix = VP8LColorCacheGetIndex(&hashers, pixel);
 322             refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix);
 323           } else {
 324             refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel);
 325           }
 326           ++refs->size;
 327           if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
 328           i++;  // Backward reference to be done for next pixel.
 329           len = len2;
 330           offset = offset2;
 331         }
 332       }
 333       if (len >= MAX_LENGTH) {
 334         len = MAX_LENGTH - 1;
 335       }
 336       refs->refs[refs->size++] = PixOrCopyCreateCopy(offset, len);
 337       if (use_color_cache) {
 338         for (k = 0; k < len; ++k) {
 339           VP8LColorCacheInsert(&hashers, argb[i + k]);
 340         }
 341       }
 342       // Add to the hash_chain (but cannot add the last pixel).
 343       {
 344         const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i;
 345         for (k = 1; k < last; ++k) {
 346           HashChainInsert(hash_chain, &argb[i + k], i + k);
 347         }
 348       }
 349       i += len;
 350     } else {
 351       const uint32_t pixel = argb[i];
 352       if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) {
 353         // push pixel as a PixOrCopyCreateCacheIdx pixel
 354         const int ix = VP8LColorCacheGetIndex(&hashers, pixel);
 355         refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix);
 356       } else {
 357         refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel);
 358       }
 359       ++refs->size;
 360       if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
 361       if (i + 1 < pix_count) {
 362         HashChainInsert(hash_chain, &argb[i], i);
 363       }
 364       ++i;
 365     }
 366   }
 367   ok = 1;
 368 Error:
 369   if (cc_init) VP8LColorCacheClear(&hashers);
 370   HashChainDelete(hash_chain);
 371   return ok;
 372 }
 373
 374 // -----------------------------------------------------------------------------
 375
 376 typedef struct {
 377   double alpha_[VALUES_IN_BYTE];
 378   double red_[VALUES_IN_BYTE];
 379   double literal_[PIX_OR_COPY_CODES_MAX];
 380   double blue_[VALUES_IN_BYTE];
 381   double distance_[NUM_DISTANCE_CODES];
 382 } CostModel;
 383
 384 static int BackwardReferencesTraceBackwards(
 385     int xsize, int ysize, int recursive_cost_model,
 386     const uint32_t* const argb, int quality, int cache_bits,
 387     VP8LBackwardRefs* const refs);
 388
 389 static void ConvertPopulationCountTableToBitEstimates(
 390     int num_symbols, const int population_counts[], double output[]) {
 391   int sum = 0;
 392   int nonzeros = 0;
 393   int i;
 394   for (i = 0; i < num_symbols; ++i) {
 395     sum += population_counts[i];
 396     if (population_counts[i] > 0) {
 397       ++nonzeros;
 398     }
 399   }
 400   if (nonzeros <= 1) {
 401     memset(output, 0, num_symbols * sizeof(*output));
 402   } else {
 403     const double logsum = VP8LFastLog2(sum);
 404     for (i = 0; i < num_symbols; ++i) {
 405       output[i] = logsum - VP8LFastLog2(population_counts[i]);
 406     }
 407   }
 408 }
 409
 410 static int CostModelBuild(CostModel* const m, int xsize, int ysize,
 411                           int recursion_level, const uint32_t* const argb,
 412                           int quality, int cache_bits) {
 413   int ok = 0;
 414   VP8LHistogram histo;
 415   VP8LBackwardRefs refs;
 416
 417   if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize)) goto Error;
 418
 419   if (recursion_level > 0) {
 420     if (!BackwardReferencesTraceBackwards(xsize, ysize, recursion_level - 1,
 421                                           argb, quality, cache_bits, &refs)) {
 422       goto Error;
 423     }
 424   } else {
 425     if (!BackwardReferencesHashChain(xsize, ysize, argb, cache_bits, quality,
 426                                      &refs)) {
 427       goto Error;
 428     }
 429   }
 430   VP8LHistogramCreate(&histo, &refs, cache_bits);
 431   ConvertPopulationCountTableToBitEstimates(
 432       VP8LHistogramNumCodes(&histo), histo.literal_, m->literal_);
 433   ConvertPopulationCountTableToBitEstimates(
 434       VALUES_IN_BYTE, histo.red_, m->red_);
 435   ConvertPopulationCountTableToBitEstimates(
 436       VALUES_IN_BYTE, histo.blue_, m->blue_);
 437   ConvertPopulationCountTableToBitEstimates(
 438       VALUES_IN_BYTE, histo.alpha_, m->alpha_);
 439   ConvertPopulationCountTableToBitEstimates(
 440       NUM_DISTANCE_CODES, histo.distance_, m->distance_);
 441   ok = 1;
 442
 443  Error:
 444   VP8LClearBackwardRefs(&refs);
 445   return ok;
 446 }
 447
 448 static WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) {
 449   return m->alpha_[v >> 24] +
 450          m->red_[(v >> 16) & 0xff] +
 451          m->literal_[(v >> 8) & 0xff] +
 452          m->blue_[v & 0xff];
 453 }
 454
 455 static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) {
 456   const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx;
 457   return m->literal_[literal_idx];
 458 }
 459
 460 static WEBP_INLINE double GetLengthCost(const CostModel* const m,
 461                                         uint32_t length) {
 462   int code, extra_bits_count, extra_bits_value;
 463   PrefixEncode(length, &code, &extra_bits_count, &extra_bits_value);
 464   return m->literal_[VALUES_IN_BYTE + code] + extra_bits_count;
 465 }
 466
 467 static WEBP_INLINE double GetDistanceCost(const CostModel* const m,
 468                                           uint32_t distance) {
 469   int code, extra_bits_count, extra_bits_value;
 470   PrefixEncode(distance, &code, &extra_bits_count, &extra_bits_value);
 471   return m->distance_[code] + extra_bits_count;
 472 }
 473
 474 static int BackwardReferencesHashChainDistanceOnly(
 475     int xsize, int ysize, int recursive_cost_model, const uint32_t* const argb,
 476     int quality, int cache_bits, uint32_t* const dist_array) {
 477   int i;
 478   int ok = 0;
 479   int cc_init = 0;
 480   const int pix_count = xsize * ysize;
 481   const int use_color_cache = (cache_bits > 0);
 482   float* const cost =
 483       (float*)WebPSafeMalloc((uint64_t)pix_count, sizeof(*cost));
 484   CostModel* cost_model = (CostModel*)malloc(sizeof(*cost_model));
 485   HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain));
 486   VP8LColorCache hashers;
 487   const double mul0 = (recursive_cost_model != 0) ? 1.0 : 0.68;
 488   const double mul1 = (recursive_cost_model != 0) ? 1.0 : 0.82;
 489   const int min_distance_code = 2;  // TODO(vikasa): tune as function of quality
 490   int window_size = WINDOW_SIZE;
 491   int iter_pos = 1;
 492   int iter_limit = -1;
 493
 494   if (cost == NULL || cost_model == NULL || hash_chain == NULL) goto Error;
 495
 496   if (!HashChainInit(hash_chain, pix_count)) goto Error;
 497
 498   if (use_color_cache) {
 499     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
 500     if (!cc_init) goto Error;
 501   }
 502
 503   if (!CostModelBuild(cost_model, xsize, ysize, recursive_cost_model, argb,
 504                       quality, cache_bits)) {
 505     goto Error;
 506   }
 507
 508   for (i = 0; i < pix_count; ++i) cost[i] = 1e38f;
 509
 510   // We loop one pixel at a time, but store all currently best points to
 511   // non-processed locations from this point.
 512   dist_array[0] = 0;
 513   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
 514                                 &window_size, &iter_pos, &iter_limit);
 515   for (i = 0; i < pix_count; ++i) {
 516     double prev_cost = 0.0;
 517     int shortmax;
 518     if (i > 0) {
 519       prev_cost = cost[i - 1];
 520     }
 521     for (shortmax = 0; shortmax < 2; ++shortmax) {
 522       int offset = 0;
 523       int len = 0;
 524       if (i < pix_count - 1) {  // FindCopy reads pixels at [i] and [i + 1].
 525         int maxlen = shortmax ? 2 : MAX_LENGTH;
 526         if (maxlen > pix_count - i) {
 527           maxlen = pix_count - i;
 528         }
 529         HashChainFindCopy(hash_chain, i, xsize, argb, maxlen,
 530                           window_size, iter_pos, iter_limit,
 531                           &offset, &len);
 532       }
 533       if (len >= MIN_LENGTH) {
 534         const int code = DistanceToPlaneCode(xsize, offset);
 535         const double distance_cost =
 536             prev_cost + GetDistanceCost(cost_model, code);
 537         int k;
 538         for (k = 1; k < len; ++k) {
 539           const double cost_val = distance_cost + GetLengthCost(cost_model, k);
 540           if (cost[i + k] > cost_val) {
 541             cost[i + k] = (float)cost_val;
 542             dist_array[i + k] = k + 1;
 543           }
 544         }
 545         // This if is for speedup only. It roughly doubles the speed, and
 546         // makes compression worse by .1 %.
 547         if (len >= 128 && code <= min_distance_code) {
 548           // Long copy for short distances, let's skip the middle
 549           // lookups for better copies.
 550           // 1) insert the hashes.
 551           if (use_color_cache) {
 552             for (k = 0; k < len; ++k) {
 553               VP8LColorCacheInsert(&hashers, argb[i + k]);
 554             }
 555           }
 556           // 2) Add to the hash_chain (but cannot add the last pixel)
 557           {
 558             const int last = (len + i < pix_count - 1) ? len + i
 559                                                        : pix_count - 1;
 560             for (k = i; k < last; ++k) {
 561               HashChainInsert(hash_chain, &argb[k], k);
 562             }
 563           }
 564           // 3) jump.
 565           i += len - 1;  // for loop does ++i, thus -1 here.
 566           goto next_symbol;
 567         }
 568       }
 569     }
 570     if (i < pix_count - 1) {
 571       HashChainInsert(hash_chain, &argb[i], i);
 572     }
 573     {
 574       // inserting a literal pixel
 575       double cost_val = prev_cost;
 576       if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) {
 577         const int ix = VP8LColorCacheGetIndex(&hashers, argb[i]);
 578         cost_val += GetCacheCost(cost_model, ix) * mul0;
 579       } else {
 580         cost_val += GetLiteralCost(cost_model, argb[i]) * mul1;
 581       }
 582       if (cost[i] > cost_val) {
 583         cost[i] = (float)cost_val;
 584         dist_array[i] = 1;  // only one is inserted.
 585       }
 586       if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
 587     }
 588  next_symbol: ;
 589   }
 590   // Last pixel still to do, it can only be a single step if not reached
 591   // through cheaper means already.
 592   ok = 1;
 593 Error:
 594   if (cc_init) VP8LColorCacheClear(&hashers);
 595   HashChainDelete(hash_chain);
 596   free(cost_model);
 597   free(cost);
 598   return ok;
 599 }
 600
 601 // We pack the path at the end of *dist_array and return
 602 // a pointer to this part of the array. Example:
 603 // dist_array = [1x2xx3x2] => packed [1x2x1232], chosen_path = [1232]
 604 static void TraceBackwards(uint32_t* const dist_array,
 605                            int dist_array_size,
 606                            uint32_t** const chosen_path,
 607                            int* const chosen_path_size) {
 608   uint32_t* path = dist_array + dist_array_size;
 609   uint32_t* cur = dist_array + dist_array_size - 1;
 610   while (cur >= dist_array) {
 611     const int k = *cur;
 612     --path;
 613     *path = k;
 614     cur -= k;
 615   }
 616   *chosen_path = path;
 617   *chosen_path_size = (int)(dist_array + dist_array_size - path);
 618 }
 619
 620 static int BackwardReferencesHashChainFollowChosenPath(
 621     int xsize, int ysize, const uint32_t* const argb,
 622     int quality, int cache_bits,
 623     const uint32_t* const chosen_path, int chosen_path_size,
 624     VP8LBackwardRefs* const refs) {
 625   const int pix_count = xsize * ysize;
 626   const int use_color_cache = (cache_bits > 0);
 627   int size = 0;
 628   int i = 0;
 629   int k;
 630   int ix;
 631   int ok = 0;
 632   int cc_init = 0;
 633   int window_size = WINDOW_SIZE;
 634   int iter_pos = 1;
 635   int iter_limit = -1;
 636   HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain));
 637   VP8LColorCache hashers;
 638
 639   if (hash_chain == NULL || !HashChainInit(hash_chain, pix_count)) {
 640     goto Error;
 641   }
 642   if (use_color_cache) {
 643     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
 644     if (!cc_init) goto Error;
 645   }
 646
 647   refs->size = 0;
 648   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
 649                                 &window_size, &iter_pos, &iter_limit);
 650   for (ix = 0; ix < chosen_path_size; ++ix, ++size) {
 651     int offset = 0;
 652     int len = 0;
 653     int maxlen = chosen_path[ix];
 654     if (maxlen != 1) {
 655       HashChainFindCopy(hash_chain, i, xsize, argb, maxlen,
 656                         window_size, iter_pos, iter_limit,
 657                         &offset, &len);
 658       assert(len == maxlen);
 659       refs->refs[size] = PixOrCopyCreateCopy(offset, len);
 660       if (use_color_cache) {
 661         for (k = 0; k < len; ++k) {
 662           VP8LColorCacheInsert(&hashers, argb[i + k]);
 663         }
 664       }
 665       {
 666         const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i;
 667         for (k = 0; k < last; ++k) {
 668           HashChainInsert(hash_chain, &argb[i + k], i + k);
 669         }
 670       }
 671       i += len;
 672     } else {
 673       if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) {
 674         // push pixel as a color cache index
 675         const int idx = VP8LColorCacheGetIndex(&hashers, argb[i]);
 676         refs->refs[size] = PixOrCopyCreateCacheIdx(idx);
 677       } else {
 678         refs->refs[size] = PixOrCopyCreateLiteral(argb[i]);
 679       }
 680       if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
 681       if (i + 1 < pix_count) {
 682         HashChainInsert(hash_chain, &argb[i], i);
 683       }
 684       ++i;
 685     }
 686   }
 687   assert(size <= refs->max_size);
 688   refs->size = size;
 689   ok = 1;
 690 Error:
 691   if (cc_init) VP8LColorCacheClear(&hashers);
 692   HashChainDelete(hash_chain);
 693   return ok;
 694 }
 695
 696 // Returns 1 on success.
 697 static int BackwardReferencesTraceBackwards(int xsize, int ysize,
 698                                             int recursive_cost_model,
 699                                             const uint32_t* const argb,
 700                                             int quality, int cache_bits,
 701                                             VP8LBackwardRefs* const refs) {
 702   int ok = 0;
 703   const int dist_array_size = xsize * ysize;
 704   uint32_t* chosen_path = NULL;
 705   int chosen_path_size = 0;
 706   uint32_t* dist_array =
 707       (uint32_t*)WebPSafeMalloc((uint64_t)dist_array_size, sizeof(*dist_array));
 708
 709   if (dist_array == NULL) goto Error;
 710
 711   if (!BackwardReferencesHashChainDistanceOnly(
 712       xsize, ysize, recursive_cost_model, argb, quality, cache_bits,
 713       dist_array)) {
 714     goto Error;
 715   }
 716   TraceBackwards(dist_array, dist_array_size, &chosen_path, &chosen_path_size);
 717   if (!BackwardReferencesHashChainFollowChosenPath(
 718       xsize, ysize, argb, quality, cache_bits, chosen_path, chosen_path_size,
 719       refs)) {
 720     goto Error;
 721   }
 722   ok = 1;
 723  Error:
 724   free(dist_array);
 725   return ok;
 726 }
 727
 728 static void BackwardReferences2DLocality(int xsize,
 729                                          VP8LBackwardRefs* const refs) {
 730   int i;
 731   for (i = 0; i < refs->size; ++i) {
 732     if (PixOrCopyIsCopy(&refs->refs[i])) {
 733       const int dist = refs->refs[i].argb_or_distance;
 734       const int transformed_dist = DistanceToPlaneCode(xsize, dist);
 735       refs->refs[i].argb_or_distance = transformed_dist;
 736     }
 737   }
 738 }
 739
 740 int VP8LGetBackwardReferences(int width, int height,
 741                               const uint32_t* const argb,
 742                               int quality, int cache_bits, int use_2d_locality,
 743                               VP8LBackwardRefs* const best) {
 744   int ok = 0;
 745   int lz77_is_useful;
 746   VP8LBackwardRefs refs_rle, refs_lz77;
 747   const int num_pix = width * height;
 748
 749   VP8LBackwardRefsAlloc(&refs_rle, num_pix);
 750   VP8LBackwardRefsAlloc(&refs_lz77, num_pix);
 751   VP8LInitBackwardRefs(best);
 752   if (refs_rle.refs == NULL || refs_lz77.refs == NULL) {
 753  Error1:
 754     VP8LClearBackwardRefs(&refs_rle);
 755     VP8LClearBackwardRefs(&refs_lz77);
 756     goto End;
 757   }
 758
 759   if (!BackwardReferencesHashChain(width, height, argb, cache_bits, quality,
 760                                    &refs_lz77)) {
 761     goto End;
 762   }
 763   // Backward Reference using RLE only.
 764   BackwardReferencesRle(width, height, argb, &refs_rle);
 765
 766   {
 767     double bit_cost_lz77, bit_cost_rle;
 768     VP8LHistogram* const histo = (VP8LHistogram*)malloc(sizeof(*histo));
 769     if (histo == NULL) goto Error1;
 770     // Evaluate lz77 coding
 771     VP8LHistogramCreate(histo, &refs_lz77, cache_bits);
 772     bit_cost_lz77 = VP8LHistogramEstimateBits(histo);
 773     // Evaluate RLE coding
 774     VP8LHistogramCreate(histo, &refs_rle, cache_bits);
 775     bit_cost_rle = VP8LHistogramEstimateBits(histo);
 776     // Decide if LZ77 is useful.
 777     lz77_is_useful = (bit_cost_lz77 < bit_cost_rle);
 778     free(histo);
 779   }
 780
 781   // Choose appropriate backward reference.
 782   if (lz77_is_useful) {
 783     // TraceBackwards is costly. Don't execute it at lower quality (q <= 10).
 784     const int try_lz77_trace_backwards = (quality > 10);
 785     *best = refs_lz77;   // default guess: lz77 is better
 786     VP8LClearBackwardRefs(&refs_rle);
 787     if (try_lz77_trace_backwards) {
 788       // Set recursion level for large images using a color cache.
 789       const int recursion_level =
 790           (num_pix < 320 * 200) && (cache_bits > 0) ? 1 : 0;
 791       VP8LBackwardRefs refs_trace;
 792       if (!VP8LBackwardRefsAlloc(&refs_trace, num_pix)) {
 793         goto End;
 794       }
 795       if (BackwardReferencesTraceBackwards(width, height, recursion_level, argb,
 796                                            quality, cache_bits, &refs_trace)) {
 797         VP8LClearBackwardRefs(&refs_lz77);
 798         *best = refs_trace;
 799       }
 800     }
 801   } else {
 802     VP8LClearBackwardRefs(&refs_lz77);
 803     *best = refs_rle;
 804   }
 805
 806   if (use_2d_locality) BackwardReferences2DLocality(width, best);
 807
 808   ok = 1;
 809
 810  End:
 811   if (!ok) {
 812     VP8LClearBackwardRefs(best);
 813   }
 814   return ok;
 815 }
 816
 817 // Returns 1 on success.
 818 static int ComputeCacheHistogram(const uint32_t* const argb,
 819                                  int xsize, int ysize,
 820                                  const VP8LBackwardRefs* const refs,
 821                                  int cache_bits,
 822                                  VP8LHistogram* const histo) {
 823   int pixel_index = 0;
 824   int i;
 825   uint32_t k;
 826   VP8LColorCache hashers;
 827   const int use_color_cache = (cache_bits > 0);
 828   int cc_init = 0;
 829
 830   if (use_color_cache) {
 831     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
 832     if (!cc_init) return 0;
 833   }
 834
 835   for (i = 0; i < refs->size; ++i) {
 836     const PixOrCopy* const v = &refs->refs[i];
 837     if (PixOrCopyIsLiteral(v)) {
 838       if (use_color_cache &&
 839           VP8LColorCacheContains(&hashers, argb[pixel_index])) {
 840         // push pixel as a cache index
 841         const int ix = VP8LColorCacheGetIndex(&hashers, argb[pixel_index]);
 842         const PixOrCopy token = PixOrCopyCreateCacheIdx(ix);
 843         VP8LHistogramAddSinglePixOrCopy(histo, &token);
 844       } else {
 845         VP8LHistogramAddSinglePixOrCopy(histo, v);
 846       }
 847     } else {
 848       VP8LHistogramAddSinglePixOrCopy(histo, v);
 849     }
 850     if (use_color_cache) {
 851       for (k = 0; k < PixOrCopyLength(v); ++k) {
 852         VP8LColorCacheInsert(&hashers, argb[pixel_index + k]);
 853       }
 854     }
 855     pixel_index += PixOrCopyLength(v);
 856   }
 857   assert(pixel_index == xsize * ysize);
 858   (void)xsize;  // xsize is not used in non-debug compilations otherwise.
 859   (void)ysize;  // ysize is not used in non-debug compilations otherwise.
 860   if (cc_init) VP8LColorCacheClear(&hashers);
 861   return 1;
 862 }
 863
 864 // Returns how many bits are to be used for a color cache.
 865 int VP8LCalculateEstimateForCacheSize(const uint32_t* const argb,
 866                                       int xsize, int ysize,
 867                                       int* const best_cache_bits) {
 868   int ok = 0;
 869   int cache_bits;
 870   double lowest_entropy = 1e99;
 871   VP8LBackwardRefs refs;
 872   static const double kSmallPenaltyForLargeCache = 4.0;
 873   static const int quality = 30;
 874   if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize) ||
 875       !BackwardReferencesHashChain(xsize, ysize, argb, 0, quality, &refs)) {
 876     goto Error;
 877   }
 878   for (cache_bits = 0; cache_bits <= MAX_COLOR_CACHE_BITS; ++cache_bits) {
 879     double cur_entropy;
 880     VP8LHistogram histo;
 881     VP8LHistogramInit(&histo, cache_bits);
 882     ComputeCacheHistogram(argb, xsize, ysize, &refs, cache_bits, &histo);
 883     cur_entropy = VP8LHistogramEstimateBits(&histo) +
 884         kSmallPenaltyForLargeCache * cache_bits;
 885     if (cache_bits == 0 || cur_entropy < lowest_entropy) {
 886       *best_cache_bits = cache_bits;
 887       lowest_entropy = cur_entropy;
 888     }
 889   }
 890   ok = 1;
 891  Error:
 892   VP8LClearBackwardRefs(&refs);
 893   return ok;
 894 }