third_party/libwebp/utils/filters.c

   1 // Copyright 2011 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 // Spatial prediction using various filters
  11 //
  12 // Author: Urvang (urvang@google.com)
  13
  14 #include "./filters.h"
  15 #include <assert.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18
  19 //------------------------------------------------------------------------------
  20 // Helpful macro.
  21
  22 # define SANITY_CHECK(in, out)                                                 \
  23   assert(in != NULL);                                                          \
  24   assert(out != NULL);                                                         \
  25   assert(width > 0);                                                           \
  26   assert(height > 0);                                                          \
  27   assert(stride >= width);                                                     \
  28   assert(row >= 0 && num_rows > 0 && row + num_rows <= height);                \
  29   (void)height;  // Silence unused warning.
  30
  31 static WEBP_INLINE void PredictLine(const uint8_t* src, const uint8_t* pred,
  32                                     uint8_t* dst, int length, int inverse) {
  33   int i;
  34   if (inverse) {
  35     for (i = 0; i < length; ++i) dst[i] = src[i] + pred[i];
  36   } else {
  37     for (i = 0; i < length; ++i) dst[i] = src[i] - pred[i];
  38   }
  39 }
  40
  41 //------------------------------------------------------------------------------
  42 // Horizontal filter.
  43
  44 static WEBP_INLINE void DoHorizontalFilter(const uint8_t* in,
  45                                            int width, int height, int stride,
  46                                            int row, int num_rows,
  47                                            int inverse, uint8_t* out) {
  48   const uint8_t* preds;
  49   const size_t start_offset = row * stride;
  50   const int last_row = row + num_rows;
  51   SANITY_CHECK(in, out);
  52   in += start_offset;
  53   out += start_offset;
  54   preds = inverse ? out : in;
  55
  56   if (row == 0) {
  57     // Leftmost pixel is the same as input for topmost scanline.
  58     out[0] = in[0];
  59     PredictLine(in + 1, preds, out + 1, width - 1, inverse);
  60     row = 1;
  61     preds += stride;
  62     in += stride;
  63     out += stride;
  64   }
  65
  66   // Filter line-by-line.
  67   while (row < last_row) {
  68     // Leftmost pixel is predicted from above.
  69     PredictLine(in, preds - stride, out, 1, inverse);
  70     PredictLine(in + 1, preds, out + 1, width - 1, inverse);
  71     ++row;
  72     preds += stride;
  73     in += stride;
  74     out += stride;
  75   }
  76 }
  77
  78 static void HorizontalFilter(const uint8_t* data, int width, int height,
  79                              int stride, uint8_t* filtered_data) {
  80   DoHorizontalFilter(data, width, height, stride, 0, height, 0, filtered_data);
  81 }
  82
  83 static void HorizontalUnfilter(int width, int height, int stride, int row,
  84                                int num_rows, uint8_t* data) {
  85   DoHorizontalFilter(data, width, height, stride, row, num_rows, 1, data);
  86 }
  87
  88 //------------------------------------------------------------------------------
  89 // Vertical filter.
  90
  91 static WEBP_INLINE void DoVerticalFilter(const uint8_t* in,
  92                                          int width, int height, int stride,
  93                                          int row, int num_rows,
  94                                          int inverse, uint8_t* out) {
  95   const uint8_t* preds;
  96   const size_t start_offset = row * stride;
  97   const int last_row = row + num_rows;
  98   SANITY_CHECK(in, out);
  99   in += start_offset;
 100   out += start_offset;
 101   preds = inverse ? out : in;
 102
 103   if (row == 0) {
 104     // Very first top-left pixel is copied.
 105     out[0] = in[0];
 106     // Rest of top scan-line is left-predicted.
 107     PredictLine(in + 1, preds, out + 1, width - 1, inverse);
 108     row = 1;
 109     in += stride;
 110     out += stride;
 111   } else {
 112     // We are starting from in-between. Make sure 'preds' points to prev row.
 113     preds -= stride;
 114   }
 115
 116   // Filter line-by-line.
 117   while (row < last_row) {
 118     PredictLine(in, preds, out, width, inverse);
 119     ++row;
 120     preds += stride;
 121     in += stride;
 122     out += stride;
 123   }
 124 }
 125
 126 static void VerticalFilter(const uint8_t* data, int width, int height,
 127                            int stride, uint8_t* filtered_data) {
 128   DoVerticalFilter(data, width, height, stride, 0, height, 0, filtered_data);
 129 }
 130
 131 static void VerticalUnfilter(int width, int height, int stride, int row,
 132                              int num_rows, uint8_t* data) {
 133   DoVerticalFilter(data, width, height, stride, row, num_rows, 1, data);
 134 }
 135
 136 //------------------------------------------------------------------------------
 137 // Gradient filter.
 138
 139 static WEBP_INLINE int GradientPredictor(uint8_t a, uint8_t b, uint8_t c) {
 140   const int g = a + b - c;
 141   return ((g & ~0xff) == 0) ? g : (g < 0) ? 0 : 255;  // clip to 8bit
 142 }
 143
 144 static WEBP_INLINE void DoGradientFilter(const uint8_t* in,
 145                                          int width, int height, int stride,
 146                                          int row, int num_rows,
 147                                          int inverse, uint8_t* out) {
 148   const uint8_t* preds;
 149   const size_t start_offset = row * stride;
 150   const int last_row = row + num_rows;
 151   SANITY_CHECK(in, out);
 152   in += start_offset;
 153   out += start_offset;
 154   preds = inverse ? out : in;
 155
 156   // left prediction for top scan-line
 157   if (row == 0) {
 158     out[0] = in[0];
 159     PredictLine(in + 1, preds, out + 1, width - 1, inverse);
 160     row = 1;
 161     preds += stride;
 162     in += stride;
 163     out += stride;
 164   }
 165
 166   // Filter line-by-line.
 167   while (row < last_row) {
 168     int w;
 169     // leftmost pixel: predict from above.
 170     PredictLine(in, preds - stride, out, 1, inverse);
 171     for (w = 1; w < width; ++w) {
 172       const int pred = GradientPredictor(preds[w - 1],
 173                                          preds[w - stride],
 174                                          preds[w - stride - 1]);
 175       out[w] = in[w] + (inverse ? pred : -pred);
 176     }
 177     ++row;
 178     preds += stride;
 179     in += stride;
 180     out += stride;
 181   }
 182 }
 183
 184 static void GradientFilter(const uint8_t* data, int width, int height,
 185                            int stride, uint8_t* filtered_data) {
 186   DoGradientFilter(data, width, height, stride, 0, height, 0, filtered_data);
 187 }
 188
 189 static void GradientUnfilter(int width, int height, int stride, int row,
 190                              int num_rows, uint8_t* data) {
 191   DoGradientFilter(data, width, height, stride, row, num_rows, 1, data);
 192 }
 193
 194 #undef SANITY_CHECK
 195
 196 // -----------------------------------------------------------------------------
 197 // Quick estimate of a potentially interesting filter mode to try.
 198
 199 #define SMAX 16
 200 #define SDIFF(a, b) (abs((a) - (b)) >> 4)   // Scoring diff, in [0..SMAX)
 201
 202 WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data,
 203                                     int width, int height, int stride) {
 204   int i, j;
 205   int bins[WEBP_FILTER_LAST][SMAX];
 206   memset(bins, 0, sizeof(bins));
 207
 208   // We only sample every other pixels. That's enough.
 209   for (j = 2; j < height - 1; j += 2) {
 210     const uint8_t* const p = data + j * stride;
 211     int mean = p[0];
 212     for (i = 2; i < width - 1; i += 2) {
 213       const int diff0 = SDIFF(p[i], mean);
 214       const int diff1 = SDIFF(p[i], p[i - 1]);
 215       const int diff2 = SDIFF(p[i], p[i - width]);
 216       const int grad_pred =
 217           GradientPredictor(p[i - 1], p[i - width], p[i - width - 1]);
 218       const int diff3 = SDIFF(p[i], grad_pred);
 219       bins[WEBP_FILTER_NONE][diff0] = 1;
 220       bins[WEBP_FILTER_HORIZONTAL][diff1] = 1;
 221       bins[WEBP_FILTER_VERTICAL][diff2] = 1;
 222       bins[WEBP_FILTER_GRADIENT][diff3] = 1;
 223       mean = (3 * mean + p[i] + 2) >> 2;
 224     }
 225   }
 226   {
 227     int filter;
 228     WEBP_FILTER_TYPE best_filter = WEBP_FILTER_NONE;
 229     int best_score = 0x7fffffff;
 230     for (filter = WEBP_FILTER_NONE; filter < WEBP_FILTER_LAST; ++filter) {
 231       int score = 0;
 232       for (i = 0; i < SMAX; ++i) {
 233         if (bins[filter][i] > 0) {
 234           score += i;
 235         }
 236       }
 237       if (score < best_score) {
 238         best_score = score;
 239         best_filter = (WEBP_FILTER_TYPE)filter;
 240       }
 241     }
 242     return best_filter;
 243   }
 244 }
 245
 246 #undef SMAX
 247 #undef SDIFF
 248
 249 //------------------------------------------------------------------------------
 250
 251 const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST] = {
 252   NULL,              // WEBP_FILTER_NONE
 253   HorizontalFilter,  // WEBP_FILTER_HORIZONTAL
 254   VerticalFilter,    // WEBP_FILTER_VERTICAL
 255   GradientFilter     // WEBP_FILTER_GRADIENT
 256 };
 257
 258 const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST] = {
 259   NULL,                // WEBP_FILTER_NONE
 260   HorizontalUnfilter,  // WEBP_FILTER_HORIZONTAL
 261   VerticalUnfilter,    // WEBP_FILTER_VERTICAL
 262   GradientUnfilter     // WEBP_FILTER_GRADIENT
 263 };
 264
 265 //------------------------------------------------------------------------------
 266