libwebp-0.3.1

third_party/libwebp/enc/backward_references.c

 // Copyright 2012 Google Inc. All Rights Reserved.
 //
-// This code is licensed under the same terms as WebM:
-//  Software License Agreement:  http://www.webmproject.org/license/software/
-//  Additional IP Rights Grant:  http://www.webmproject.org/license/additional/
+// 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)
 //
 
 #include <assert.h>
 #include <math.h>
 #include <stdio.h>
 
 #include "./backward_references.h"
@@ skipping 119 matching lines @@
 
 // Insertion of two pixels at a time.
 static void HashChainInsert(HashChain* const p,
                             const uint32_t* const argb, int pos) {
   const uint64_t hash_code = GetPixPairHash64(argb);
   p->chain_[pos] = p->hash_to_first_index_[hash_code];
   p->hash_to_first_index_[hash_code] = pos;
 }
 
 static void GetParamsForHashChainFindCopy(int quality, int xsize,
-                                          int* window_size, int* iter_pos,
-                                          int* iter_limit) {
+                                          int cache_bits, int* window_size,
+                                          int* iter_pos, int* iter_limit) {
   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 = 5 + (quality >> 3);
-  *iter_limit = -quality * iter_mult;
+  *iter_pos = 8 + (quality >> 3);
+  // For lower entropy images, the rigourous 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,
+                             int base_position, int xsize_signed,
                              const uint32_t* const argb, int maxlen,
                              int window_size, int iter_pos, int iter_limit,
                              int* const distance_ptr,
                              int* const length_ptr) {
-  const uint64_t hash_code = GetPixPairHash64(&argb[base_position]);
-  int prev_length = 0;
-  int64_t best_val = 0;
-  int best_length = 0;
-  int best_distance = 0;
   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);
-  for (pos = p->hash_to_first_index_[hash_code];
+  for (pos = p->hash_to_first_index_[GetPixPairHash64(argb_start)];
        pos >= min_pos;
        pos = p->chain_[pos]) {
-    int64_t val;
-    int curr_length;
+    uint64_t val;
+    uint32_t curr_length;
+    uint32_t distance;
     if (iter_pos < 0) {
       if (iter_pos < iter_limit || best_val >= 0xff0000) {
         break;
       }
     }
     --iter_pos;
-    if (best_length != 0 &&
-        argb[pos + best_length - 1] != argb_start[best_length - 1]) {
+    if (argb[pos + best_length - 1] != argb_start[best_length - 1]) {
       continue;
     }
     curr_length = FindMatchLength(argb + pos, argb_start, maxlen);
-    if (curr_length < prev_length) {
+    if (curr_length < best_length) {
       continue;
     }
-    val = 65536 * curr_length;
+    distance = (uint32_t)(base_position - pos);
+    val = curr_length << 16;
     // Favoring 2d locality here gives savings for certain images.
-    if (base_position - pos < 9 * xsize) {
-      const int y = (base_position - pos) / xsize;
-      int x = (base_position - pos) % xsize;
-      if (x > xsize / 2) {
+    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 && x >= -8) {
+      if (x <= 7) {
+        val += 9 * 9 + 9 * 9;
         val -= y * y + x * x;
-      } else {
-        val -= 9 * 9 + 9 * 9;
       }
-    } else {
-      val -= 9 * 9 + 9 * 9;
     }
     if (best_val < val) {
-      prev_length = curr_length;
       best_val = val;
       best_length = curr_length;
-      best_distance = base_position - pos;
+      best_distance = distance;
       if (curr_length >= MAX_LENGTH) {
         break;
       }
-      if ((best_distance == 1 || best_distance == xsize) &&
+      if ((best_distance == 1 || distance == xsize) &&
           best_length >= 128) {
         break;
       }
     }
   }
-  *distance_ptr = best_distance;
+  *distance_ptr = (int)best_distance;
   *length_ptr = best_length;
   return (best_length >= MIN_LENGTH);
 }
 
 static WEBP_INLINE void PushBackCopy(VP8LBackwardRefs* const refs, int length) {
   int size = refs->size;
   while (length >= MAX_LENGTH) {
     refs->refs[size++] = PixOrCopyCreateCopy(1, MAX_LENGTH);
     length -= MAX_LENGTH;
   }
@@ skipping 41 matching lines @@
 
   if (hash_chain == NULL) return 0;
   if (use_color_cache) {
     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
     if (!cc_init) goto Error;
   }
 
   if (!HashChainInit(hash_chain, pix_count)) goto Error;
 
   refs->size = 0;
-  GetParamsForHashChainFindCopy(quality, xsize, &window_size, &iter_pos,
-                                &iter_limit);
+  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,
@@ skipping 204 matching lines @@
   if (!CostModelBuild(cost_model, xsize, ysize, recursive_cost_model, argb,
                       quality, cache_bits)) {
     goto Error;
   }
 
   for (i = 0; i < pix_count; ++i) cost[i] = 1e38f;
 
   // We loop one pixel at a time, but store all currently best points to
   // non-processed locations from this point.
   dist_array[0] = 0;
-  GetParamsForHashChainFindCopy(quality, xsize, &window_size, &iter_pos,
-                                &iter_limit);
+  GetParamsForHashChainFindCopy(quality, xsize, cache_bits,
+                                &window_size, &iter_pos, &iter_limit);
   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].
@@ skipping 113 matching lines @@
 
   if (hash_chain == NULL || !HashChainInit(hash_chain, pix_count)) {
     goto Error;
   }
   if (use_color_cache) {
     cc_init = VP8LColorCacheInit(&hashers, cache_bits);
     if (!cc_init) goto Error;
   }
 
   refs->size = 0;
-  GetParamsForHashChainFindCopy(quality, xsize, &window_size, &iter_pos,
-                                &iter_limit);
+  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,
                         window_size, iter_pos, iter_limit,
                         &offset, &len);
       assert(len == maxlen);
       refs->refs[size] = PixOrCopyCreateCopy(offset, len);
@@ skipping 118 matching lines @@
     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);
     *best = refs_lz77;   // default guess: lz77 is better
     VP8LClearBackwardRefs(&refs_rle);
     if (try_lz77_trace_backwards) {
-      const int recursion_level = (num_pix < 320 * 200) ? 1 : 0;
+      // 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;
       }
       if (BackwardReferencesTraceBackwards(width, height, recursion_level, argb,
                                            quality, cache_bits, &refs_trace)) {
         VP8LClearBackwardRefs(&refs_lz77);
         *best = refs_trace;
       }
     }
@@ skipping 84 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;
 }