Update libwebp to 0.4.0

third_party/libwebp/enc/backward_references.c

 // Copyright 2012 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.
 // -----------------------------------------------------------------------------
 //
 // Author: Jyrki Alakuijala (jyrki@google.com)
@@ skipping 138 matching lines @@
   const int iter_mult = (quality < 27) ? 1 : 1 + ((quality - 27) >> 4);
   const int iter_neg = -iter_mult * (quality >> 1);
   // Limit the backward-ref window size for lower qualities.
   const int max_window_size = (quality > 50) ? WINDOW_SIZE
                             : (quality > 25) ? (xsize << 8)
                             : (xsize << 4);
   assert(xsize > 0);
   *window_size = (max_window_size > WINDOW_SIZE) ? WINDOW_SIZE
                : max_window_size;
   *iter_pos = 8 + (quality >> 3);
-  // For lower entropy images, the rigourous search loop in HashChainFindCopy
+  // For lower entropy images, the rigorous search loop in HashChainFindCopy
   // can be relaxed.
   *iter_limit = (cache_bits > 0) ? iter_neg : iter_neg / 2;
 }
 
 static int HashChainFindCopy(const HashChain* const p,
                              int base_position, int xsize_signed,
-                             const uint32_t* const argb, int maxlen,
+                             const uint32_t* const argb, int max_len,
                              int window_size, int iter_pos, int iter_limit,
                              int* const distance_ptr,
                              int* const length_ptr) {
   const uint32_t* const argb_start = argb + base_position;
   uint64_t best_val = 0;
   uint32_t best_length = 1;
   uint32_t best_distance = 0;
   const uint32_t xsize = (uint32_t)xsize_signed;
   const int min_pos =
       (base_position > window_size) ? base_position - window_size : 0;
   int pos;
   assert(xsize > 0);
+  if (max_len > MAX_LENGTH) {
+    max_len = MAX_LENGTH;
+  }
   for (pos = p->hash_to_first_index_[GetPixPairHash64(argb_start)];
        pos >= min_pos;
        pos = p->chain_[pos]) {
     uint64_t val;
     uint32_t curr_length;
     uint32_t distance;
+    const uint64_t* const ptr1 =
+        (const uint64_t*)(argb + pos + best_length - 1);
+    const uint64_t* const ptr2 =
+        (const uint64_t*)(argb_start + best_length - 1);
+
     if (iter_pos < 0) {
       if (iter_pos < iter_limit || best_val >= 0xff0000) {
         break;
       }
     }
     --iter_pos;
-    if (argb[pos + best_length - 1] != argb_start[best_length - 1]) {
-      continue;
-    }
-    curr_length = FindMatchLength(argb + pos, argb_start, maxlen);
-    if (curr_length < best_length) {
-      continue;
-    }
+
+    // Before 'expensive' linear match, check if the two arrays match at the
+    // current best length index and also for the succeeding elements.
+    if (*ptr1 != *ptr2) continue;
+
+    curr_length = FindMatchLength(argb + pos, argb_start, max_len);
+    if (curr_length < best_length) continue;
+
     distance = (uint32_t)(base_position - pos);
     val = curr_length << 16;
     // Favoring 2d locality here gives savings for certain images.
     if (distance < 9 * xsize) {
       const uint32_t y = distance / xsize;
       uint32_t x = distance % xsize;
       if (x > (xsize >> 1)) {
         x = xsize - x;
       }
       if (x <= 7) {
         val += 9 * 9 + 9 * 9;
         val -= y * y + x * x;
       }
     }
     if (best_val < val) {
       best_val = val;
       best_length = curr_length;
       best_distance = distance;
-      if (curr_length >= MAX_LENGTH) {
+      if (curr_length >= (uint32_t)max_len) {
         break;
       }
       if ((best_distance == 1 || distance == xsize) &&
           best_length >= 128) {
         break;
       }
     }
   }
   *distance_ptr = (int)best_distance;
   *length_ptr = best_length;
@@ skipping 57 matching lines @@
   if (!HashChainInit(hash_chain, pix_count)) goto Error;
 
   refs->size = 0;
   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
                                 &window_size, &iter_pos, &iter_limit);
   for (i = 0; i < pix_count; ) {
     // Alternative#1: Code the pixels starting at 'i' using backward reference.
     int offset = 0;
     int len = 0;
     if (i < pix_count - 1) {  // FindCopy(i,..) reads pixels at [i] and [i + 1].
-      int maxlen = pix_count - i;
-      if (maxlen > MAX_LENGTH) {
-        maxlen = MAX_LENGTH;
-      }
-      HashChainFindCopy(hash_chain, i, xsize, argb, maxlen,
+      int max_len = pix_count - i;
+      HashChainFindCopy(hash_chain, i, xsize, argb, max_len,
                         window_size, iter_pos, iter_limit,
                         &offset, &len);
     }
     if (len >= MIN_LENGTH) {
       // Alternative#2: Insert the pixel at 'i' as literal, and code the
       // pixels starting at 'i + 1' using backward reference.
       int offset2 = 0;
       int len2 = 0;
       int k;
       HashChainInsert(hash_chain, &argb[i], i);
       if (i < pix_count - 2) {  // FindCopy(i+1,..) reads [i + 1] and [i + 2].
-        int maxlen = pix_count - (i + 1);
-        if (maxlen > MAX_LENGTH) {
-          maxlen = MAX_LENGTH;
-        }
-        HashChainFindCopy(hash_chain, i + 1, xsize, argb, maxlen,
+        int max_len = pix_count - (i + 1);
+        HashChainFindCopy(hash_chain, i + 1, xsize, argb, max_len,
                           window_size, iter_pos, iter_limit,
                           &offset2, &len2);
         if (len2 > len + 1) {
           const uint32_t pixel = argb[i];
           // Alternative#2 is a better match. So push pixel at 'i' as literal.
           if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) {
             const int ix = VP8LColorCacheGetIndex(&hashers, pixel);
             refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix);
           } else {
+            if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
             refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel);
           }
           ++refs->size;
-          if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
           i++;  // Backward reference to be done for next pixel.
           len = len2;
           offset = offset2;
         }
       }
       if (len >= MAX_LENGTH) {
         len = MAX_LENGTH - 1;
       }
       refs->refs[refs->size++] = PixOrCopyCreateCopy(offset, len);
       if (use_color_cache) {
         for (k = 0; k < len; ++k) {
           VP8LColorCacheInsert(&hashers, argb[i + k]);
         }
       }
       // Add to the hash_chain (but cannot add the last pixel).
       {
         const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i;
         for (k = 1; k < last; ++k) {
           HashChainInsert(hash_chain, &argb[i + k], i + k);
         }
       }
       i += len;
     } else {
       const uint32_t pixel = argb[i];
       if (use_color_cache && VP8LColorCacheContains(&hashers, pixel)) {
         // push pixel as a PixOrCopyCreateCacheIdx pixel
         const int ix = VP8LColorCacheGetIndex(&hashers, pixel);
         refs->refs[refs->size] = PixOrCopyCreateCacheIdx(ix);
       } else {
+        if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
         refs->refs[refs->size] = PixOrCopyCreateLiteral(pixel);
       }
       ++refs->size;
-      if (use_color_cache) VP8LColorCacheInsert(&hashers, pixel);
       if (i + 1 < pix_count) {
         HashChainInsert(hash_chain, &argb[i], i);
       }
       ++i;
     }
   }
   ok = 1;
 Error:
   if (cc_init) VP8LColorCacheClear(&hashers);
   HashChainDelete(hash_chain);
@@ skipping 81 matching lines @@
          m->blue_[v & 0xff];
 }
 
 static WEBP_INLINE double GetCacheCost(const CostModel* const m, uint32_t idx) {
   const int literal_idx = VALUES_IN_BYTE + NUM_LENGTH_CODES + idx;
   return m->literal_[literal_idx];
 }
 
 static WEBP_INLINE double GetLengthCost(const CostModel* const m,
                                         uint32_t length) {
-  int code, extra_bits_count, extra_bits_value;
-  PrefixEncode(length, &code, &extra_bits_count, &extra_bits_value);
-  return m->literal_[VALUES_IN_BYTE + code] + extra_bits_count;
+  int code, extra_bits;
+  VP8LPrefixEncodeBits(length, &code, &extra_bits);
+  return m->literal_[VALUES_IN_BYTE + code] + extra_bits;
 }
 
 static WEBP_INLINE double GetDistanceCost(const CostModel* const m,
                                           uint32_t distance) {
-  int code, extra_bits_count, extra_bits_value;
-  PrefixEncode(distance, &code, &extra_bits_count, &extra_bits_value);
-  return m->distance_[code] + extra_bits_count;
+  int code, extra_bits;
+  VP8LPrefixEncodeBits(distance, &code, &extra_bits);
+  return m->distance_[code] + extra_bits;
 }
 
 static int BackwardReferencesHashChainDistanceOnly(
     int xsize, int ysize, int recursive_cost_model, const uint32_t* const argb,
     int quality, int cache_bits, uint32_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);
@@ skipping 33 matching lines @@
   for (i = 0; i < pix_count; ++i) {
     double prev_cost = 0.0;
     int shortmax;
     if (i > 0) {
       prev_cost = cost[i - 1];
     }
     for (shortmax = 0; shortmax < 2; ++shortmax) {
       int offset = 0;
       int len = 0;
       if (i < pix_count - 1) {  // FindCopy reads pixels at [i] and [i + 1].
-        int maxlen = shortmax ? 2 : MAX_LENGTH;
-        if (maxlen > pix_count - i) {
-          maxlen = pix_count - i;
-        }
-        HashChainFindCopy(hash_chain, i, xsize, argb, maxlen,
+        int max_len = shortmax ? 2 : pix_count - i;
+        HashChainFindCopy(hash_chain, i, xsize, argb, max_len,
                           window_size, iter_pos, iter_limit,
                           &offset, &len);
       }
       if (len >= MIN_LENGTH) {
         const int code = DistanceToPlaneCode(xsize, offset);
         const double distance_cost =
             prev_cost + GetDistanceCost(cost_model, code);
         int k;
         for (k = 1; k < len; ++k) {
           const double cost_val = distance_cost + GetLengthCost(cost_model, k);
@@ skipping 30 matching lines @@
     if (i < pix_count - 1) {
       HashChainInsert(hash_chain, &argb[i], i);
     }
     {
       // inserting a literal pixel
       double cost_val = prev_cost;
       if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) {
         const int ix = VP8LColorCacheGetIndex(&hashers, argb[i]);
         cost_val += GetCacheCost(cost_model, ix) * mul0;
       } else {
+        if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
         cost_val += GetLiteralCost(cost_model, argb[i]) * mul1;
       }
       if (cost[i] > cost_val) {
         cost[i] = (float)cost_val;
         dist_array[i] = 1;  // only one is inserted.
       }
-      if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
     }
  next_symbol: ;
   }
   // Last pixel still to do, it can only be a single step if not reached
   // through cheaper means already.
   ok = 1;
 Error:
   if (cc_init) VP8LColorCacheClear(&hashers);
   HashChainDelete(hash_chain);
   free(cost_model);
@@ skipping 46 matching lines @@
     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
     if (!cc_init) goto Error;
   }
 
   refs->size = 0;
   GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
                                 &window_size, &iter_pos, &iter_limit);
   for (ix = 0; ix < chosen_path_size; ++ix, ++size) {
     int offset = 0;
     int len = 0;
-    int maxlen = chosen_path[ix];
-    if (maxlen != 1) {
-      HashChainFindCopy(hash_chain, i, xsize, argb, maxlen,
+    int max_len = chosen_path[ix];
+    if (max_len != 1) {
+      HashChainFindCopy(hash_chain, i, xsize, argb, max_len,
                         window_size, iter_pos, iter_limit,
                         &offset, &len);
-      assert(len == maxlen);
+      assert(len == max_len);
       refs->refs[size] = PixOrCopyCreateCopy(offset, len);
       if (use_color_cache) {
         for (k = 0; k < len; ++k) {
           VP8LColorCacheInsert(&hashers, argb[i + k]);
         }
       }
       {
         const int last = (len < pix_count - 1 - i) ? len : pix_count - 1 - i;
         for (k = 0; k < last; ++k) {
           HashChainInsert(hash_chain, &argb[i + k], i + k);
         }
       }
       i += len;
     } else {
       if (use_color_cache && VP8LColorCacheContains(&hashers, argb[i])) {
         // push pixel as a color cache index
         const int idx = VP8LColorCacheGetIndex(&hashers, argb[i]);
         refs->refs[size] = PixOrCopyCreateCacheIdx(idx);
       } else {
+        if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
         refs->refs[size] = PixOrCopyCreateLiteral(argb[i]);
       }
-      if (use_color_cache) VP8LColorCacheInsert(&hashers, argb[i]);
       if (i + 1 < pix_count) {
         HashChainInsert(hash_chain, &argb[i], i);
       }
       ++i;
     }
   }
   assert(size <= refs->max_size);
   refs->size = size;
   ok = 1;
 Error:
@@ skipping 82 matching lines @@
     // Evaluate RLE coding
     VP8LHistogramCreate(histo, &refs_rle, cache_bits);
     bit_cost_rle = VP8LHistogramEstimateBits(histo);
     // Decide if LZ77 is useful.
     lz77_is_useful = (bit_cost_lz77 < bit_cost_rle);
     free(histo);
   }
 
   // Choose appropriate backward reference.
   if (lz77_is_useful) {
-    // TraceBackwards is costly. Don't execute it at lower quality (q <= 10).
-    const int try_lz77_trace_backwards = (quality > 10);
+    // TraceBackwards is costly. Don't execute it at lower quality.
+    const int try_lz77_trace_backwards = (quality >= 25);
     *best = refs_lz77;   // default guess: lz77 is better
     VP8LClearBackwardRefs(&refs_rle);
     if (try_lz77_trace_backwards) {
       // Set recursion level for large images using a color cache.
       const int recursion_level =
           (num_pix < 320 * 200) && (cache_bits > 0) ? 1 : 0;
       VP8LBackwardRefs refs_trace;
       if (!VP8LBackwardRefsAlloc(&refs_trace, num_pix)) {
         goto End;
       }
@@ skipping 90 matching lines @@
     if (cache_bits == 0 || cur_entropy < lowest_entropy) {
       *best_cache_bits = cache_bits;
       lowest_entropy = cur_entropy;
     }
   }
   ok = 1;
  Error:
   VP8LClearBackwardRefs(&refs);
   return ok;
 }