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 rigorous 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 max_len,
 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   if (max_len > MAX_LENGTH) {
 180     max_len = MAX_LENGTH;
 181   }
 182   for (pos = p->hash_to_first_index_[GetPixPairHash64(argb_start)];
 183        pos >= min_pos;
 184        pos = p->chain_[pos]) {
 185     uint64_t val;
 186     uint32_t curr_length;
 187     uint32_t distance;
 188     const uint64_t* const ptr1 =
 189         (const uint64_t*)(argb + pos + best_length - 1);
 190     const uint64_t* const ptr2 =
 191         (const uint64_t*)(argb_start + best_length - 1);
 192
 193     if (iter_pos < 0) {
 194       if (iter_pos < iter_limit || best_val >= 0xff0000) {
 195         break;
 196       }
 197     }
 198     --iter_pos;
 199
 200     // Before 'expensive' linear match, check if the two arrays match at the
 201     // current best length index and also for the succeeding elements.
 202     if (*ptr1 != *ptr2) continue;
 203
 204     curr_length = FindMatchLength(argb + pos, argb_start, max_len);
 205     if (curr_length < best_length) continue;
 206
 207     distance = (uint32_t)(base_position - pos);
 208     val = curr_length << 16;
 209     // Favoring 2d locality here gives savings for certain images.
 210     if (distance < 9 * xsize) {
 211       const uint32_t y = distance / xsize;
 212       uint32_t x = distance % xsize;
 213       if (x > (xsize >> 1)) {
 214         x = xsize - x;
 215       }
 216       if (x <= 7) {
 217         val += 9 * 9 + 9 * 9;
 218         val -= y * y + x * x;
 219       }
 220     }
 221     if (best_val < val) {
 222       best_val = val;
 223       best_length = curr_length;
 224       best_distance = distance;
 225       if (curr_length >= (uint32_t)max_len) {
 226         break;
 227       }
 228       if ((best_distance == 1 || distance == xsize) &&
 229           best_length >= 128) {
 230         break;
 231       }
 232     }
 233   }
 234   *distance_ptr = (int)best_distance;
 235   *length_ptr = best_length;
 236   return (best_length >= MIN_LENGTH);
 237 }
 238
 239 static WEBP_INLINE void PushBackCopy(VP8LBackwardRefs* const refs, int length) {
 240   int size = refs->size;
 241   while (length >= MAX_LENGTH) {
 242     refs->refs[size++] = PixOrCopyCreateCopy(1, MAX_LENGTH);
 243     length -= MAX_LENGTH;
 244   }
 245   if (length > 0) {
 246     refs->refs[size++] = PixOrCopyCreateCopy(1, length);
 247   }
 248   refs->size = size;
 249 }
 250
 251 static void BackwardReferencesRle(int xsize, int ysize,
 252                                   const uint32_t* const argb,
 253                                   VP8LBackwardRefs* const refs) {
 254   const int pix_count = xsize * ysize;
 255   int match_len = 0;
 256   int i;
 257   refs->size = 0;
 258   PushBackCopy(refs, match_len);    // i=0 case
 259   refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[0]);
 260   for (i = 1; i < pix_count; ++i) {
 261     if (argb[i] == argb[i - 1]) {
 262       ++match_len;
 263     } else {
 264       PushBackCopy(refs, match_len);
 265       match_len = 0;
 266       refs->refs[refs->size++] = PixOrCopyCreateLiteral(argb[i]);
 267     }
 268   }
 269   PushBackCopy(refs, match_len);
 270 }
 271
 272 static int BackwardReferencesHashChain(int xsize, int ysize,
 273                                        const uint32_t* const argb,
 274                                        int cache_bits, int quality,
 275                                        VP8LBackwardRefs* const refs) {
 276   int i;
 277   int ok = 0;
 278   int cc_init = 0;
 279   const int use_color_cache = (cache_bits > 0);
 280   const int pix_count = xsize * ysize;
 281   HashChain* const hash_chain = (HashChain*)malloc(sizeof(*hash_chain));
 282   VP8LColorCache hashers;
 283   int window_size = WINDOW_SIZE;
 284   int iter_pos = 1;
 285   int iter_limit = -1;
 286
 287   if (hash_chain == NULL) return 0;
 288   if (use_color_cache) {
 289     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
 290     if (!cc_init) goto Error;
 291   }
 292
 293   if (!HashChainInit(hash_chain, pix_count)) goto Error;
 294
 295   refs->size = 0;
 296   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
 297                                 &window_size, &iter_pos, &iter_limit);
 298   for (i = 0; i < pix_count; ) {
 299     // Alternative#1: Code the pixels starting at 'i' using backward reference.
 300     int offset = 0;
 301     int len = 0;
 302     if (i < pix_count - 1) {  // FindCopy(i,..) reads pixels at [i] and [i + 1].
 303       int max_len = pix_count - i;
 304       HashChainFindCopy(hash_chain, i, xsize, argb, max_len,
 305                         window_size, iter_pos, iter_limit,
 306                         &offset, &len);
 307     }
 308     if (len >= MIN_LENGTH) {
 309       // Alternative#2: Insert the pixel at 'i' as literal, and code the
 310       // pixels starting at 'i + 1' using backward reference.
 311       int offset2 = 0;
 312       int len2 = 0;
 313       int k;
 314       HashChainInsert(hash_chain, &argb[i], i);
 315       if (i < pix_count - 2) {  // FindCopy(i+1,..) reads [i + 1] and [i + 2].
 316         int max_len = pix_count - (i + 1);
 317         HashChainFindCopy(hash_chain, i + 1, xsize, argb, max_len,
 318                           window_size, iter_pos, iter_limit,
 319                           &offset2, &len2);
 320         if (len2 > len + 1) {
 321           const uint32_t pixel = argb[i];
 322           // Alternative#2 is a better match. So push pixel at 'i' as literal.
 323           if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) {
 324             const int ix = VP8LColorCacheGetIndex(&hashers, pixel);
 325             refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix);
 326           } else {
 327             if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
 328             refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel);
 329           }
 330           ++refs->size;
 331           i++;  // Backward reference to be done for next pixel.
 332           len = len2;
 333           offset = offset2;
 334         }
 335       }
 336       if (len >= MAX_LENGTH) {
 337         len = MAX_LENGTH - 1;
 338       }
 339       refs->refs[refs->size++] = PixOrCopyCreateCopy(offset, len);
 340       if (use_color_cache) {
 341         for (k = 0; k < len; ++k) {
 342           VP8LColorCacheInsert(&hashers, argb[i + k]);
 343         }
 344       }
 345       // Add to the hash_chain (but cannot add the last pixel).
 346       {
 347         const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i;
 348         for (k = 1; k < last; ++k) {
 349           HashChainInsert(hash_chain, &argb[i + k], i + k);
 350         }
 351       }
 352       i += len;
 353     } else {
 354       const uint32_t pixel = argb[i];
 355       if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) {
 356         // push pixel as a PixOrCopyCreateCacheIdx pixel
 357         const int ix = VP8LColorCacheGetIndex(&hashers, pixel);
 358         refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix);
 359       } else {
 360         if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
 361         refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel);
 362       }
 363       ++refs->size;
 364       if (i + 1 < pix_count) {
 365         HashChainInsert(hash_chain, &argb[i], i);
 366       }
 367       ++i;
 368     }
 369   }
 370   ok = 1;
 371 Error:
 372   if (cc_init) VP8LColorCacheClear(&hashers);
 373   HashChainDelete(hash_chain);
 374   return ok;
 375 }
 376
 377 // -----------------------------------------------------------------------------
 378
 379 typedef struct {
 380   double alpha_[VALUES_IN_BYTE];
 381   double red_[VALUES_IN_BYTE];
 382   double literal_[PIX_OR_COPY_CODES_MAX];
 383   double blue_[VALUES_IN_BYTE];
 384   double distance_[NUM_DISTANCE_CODES];
 385 } CostModel;
 386
 387 static int BackwardReferencesTraceBackwards(
 388     int xsize, int ysize, int recursive_cost_model,
 389     const uint32_t* const argb, int quality, int cache_bits,
 390     VP8LBackwardRefs* const refs);
 391
 392 static void ConvertPopulationCountTableToBitEstimates(
 393     int num_symbols, const int population_counts[], double output[]) {
 394   int sum = 0;
 395   int nonzeros = 0;
 396   int i;
 397   for (i = 0; i < num_symbols; ++i) {
 398     sum += population_counts[i];
 399     if (population_counts[i] > 0) {
 400       ++nonzeros;
 401     }
 402   }
 403   if (nonzeros <= 1) {
 404     memset(output, 0, num_symbols * sizeof(*output));
 405   } else {
 406     const double logsum = VP8LFastLog2(sum);
 407     for (i = 0; i < num_symbols; ++i) {
 408       output[i] = logsum - VP8LFastLog2(population_counts[i]);
 409     }
 410   }
 411 }
 412
 413 static int CostModelBuild(CostModel* const m, int xsize, int ysize,
 414                           int recursion_level, const uint32_t* const argb,
 415                           int quality, int cache_bits) {
 416   int ok = 0;
 417   VP8LHistogram histo;
 418   VP8LBackwardRefs refs;
 419
 420   if (!VP8LBackwardRefsAlloc(&refs, xsize * ysize)) goto Error;
 421
 422   if (recursion_level > 0) {
 423     if (!BackwardReferencesTraceBackwards(xsize, ysize, recursion_level - 1,
 424                                           argb, quality, cache_bits, &refs)) {
 425       goto Error;
 426     }
 427   } else {
 428     if (!BackwardReferencesHashChain(xsize, ysize, argb, cache_bits, quality,
 429                                      &refs)) {
 430       goto Error;
 431     }
 432   }
 433   VP8LHistogramCreate(&histo, &refs, cache_bits);
 434   ConvertPopulationCountTableToBitEstimates(
 435       VP8LHistogramNumCodes(&histo), histo.literal_, m->literal_);
 436   ConvertPopulationCountTableToBitEstimates(
 437       VALUES_IN_BYTE, histo.red_, m->red_);
 438   ConvertPopulationCountTableToBitEstimates(
 439       VALUES_IN_BYTE, histo.blue_, m->blue_);
 440   ConvertPopulationCountTableToBitEstimates(
 441       VALUES_IN_BYTE, histo.alpha_, m->alpha_);
 442   ConvertPopulationCountTableToBitEstimates(
 443       NUM_DISTANCE_CODES, histo.distance_, m->distance_);
 444   ok = 1;
 445
 446  Error:
 447   VP8LClearBackwardRefs(&refs);
 448   return ok;
 449 }
 450
 451 static WEBP_INLINE double GetLiteralCost(const CostModel* const m, uint32_t v) {
 452   return m->alpha_[v >> 24] +
 453          m->red_[(v >> 16) & 0xff] +
 454          m->literal_[(v >> 8) & 0xff] +
 455          m->blue_[v & 0xff];
 456 }
 457
 458 static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) {
 459   const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx;
 460   return m->literal_[literal_idx];
 461 }
 462
 463 static WEBP_INLINE double GetLengthCost(const CostModel* const m,
 464                                         uint32_t length) {
 465   int code, extra_bits;
 466   VP8LPrefixEncodeBits(length, &code, &extra_bits);
 467   return m->literal_[VALUES_IN_BYTE + code] + extra_bits;
 468 }
 469
 470 static WEBP_INLINE double GetDistanceCost(const CostModel* const m,
 471                                           uint32_t distance) {
 472   int code, extra_bits;
 473   VP8LPrefixEncodeBits(distance, &code, &extra_bits);
 474   return m->distance_[code] + extra_bits;
 475 }
 476
 477 static int BackwardReferencesHashChainDistanceOnly(
 478     int xsize, int ysize, int recursive_cost_model, const uint32_t* const argb,
 479     int quality, int cache_bits, uint32_t* const dist_array) {
 480   int i;
 481   int ok = 0;
 482   int cc_init = 0;
 483   const int pix_count = xsize * ysize;
 484   const int use_color_cache = (cache_bits > 0);
 485   float* const cost =
 486       (float*)WebPSafeMalloc((uint64_t)pix_count, sizeof(*cost));
 487   CostModel* cost_model = (CostModel*)malloc(sizeof(*cost_model));
 488   HashChain* hash_chain = (HashChain*)malloc(sizeof(*hash_chain));
 489   VP8LColorCache hashers;
 490   const double mul0 = (recursive_cost_model != 0) ? 1.0 : 0.68;
 491   const double mul1 = (recursive_cost_model != 0) ? 1.0 : 0.82;
 492   const int min_distance_code = 2;  // TODO(vikasa): tune as function of quality
 493   int window_size = WINDOW_SIZE;
 494   int iter_pos = 1;
 495   int iter_limit = -1;
 496
 497   if (cost == NULL || cost_model == NULL || hash_chain == NULL) goto Error;
 498
 499   if (!HashChainInit(hash_chain, pix_count)) goto Error;
 500
 501   if (use_color_cache) {
 502     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
 503     if (!cc_init) goto Error;
 504   }
 505
 506   if (!CostModelBuild(cost_model, xsize, ysize, recursive_cost_model, argb,
 507                       quality, cache_bits)) {
 508     goto Error;
 509   }
 510
 511   for (i = 0; i < pix_count; ++i) cost[i] = 1e38f;
 512
 513   // We loop one pixel at a time, but store all currently best points to
 514   // non-processed locations from this point.
 515   dist_array[0] = 0;
 516   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
 517                                 &window_size, &iter_pos, &iter_limit);
 518   for (i = 0; i < pix_count; ++i) {
 519     double prev_cost = 0.0;
 520     int shortmax;
 521     if (i > 0) {
 522       prev_cost = cost[i - 1];
 523     }
 524     for (shortmax = 0; shortmax < 2; ++shortmax) {
 525       int offset = 0;
 526       int len = 0;
 527       if (i < pix_count - 1) {  // FindCopy reads pixels at [i] and [i + 1].
 528         int max_len = shortmax ? 2 : pix_count - i;
 529         HashChainFindCopy(hash_chain, i, xsize, argb, max_len,
 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         if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
 581         cost_val += GetLiteralCost(cost_model, argb[i]) * mul1;
 582       }
 583       if (cost[i] > cost_val) {
 584         cost[i] = (float)cost_val;
 585         dist_array[i] = 1;  // only one is inserted.
 586       }
 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 max_len = chosen_path[ix];
 654     if (max_len != 1) {
 655       HashChainFindCopy(hash_chain, i, xsize, argb, max_len,
 656                         window_size, iter_pos, iter_limit,
 657                         &offset, &len);
 658       assert(len == max_len);
 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         if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
 679         refs->refs[size] = PixOrCopyCreateLiteral(argb[i]);
 680       }
 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.
 784     const int try_lz77_trace_backwards = (quality >= 25);
 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 }