src/SDL2/external/libwebp-0.3.0/src/utils/filters.c

   1 // Copyright 2011 Google Inc. All Rights Reserved.
   2 //
   3 // This code is licensed under the same terms as WebM:
   4 //  Software License Agreement:  http://www.webmproject.org/license/software/
   5 //  Additional IP Rights Grant:  http://www.webmproject.org/license/additional/
   6 // -----------------------------------------------------------------------------
   7 //
   8 // Spatial prediction using various filters
   9 //
  10 // Author: Urvang (urvang@google.com)
  11
  12 #include "./filters.h"
  13 #include <assert.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16
  17 #if defined(__cplusplus) || defined(c_plusplus)
  18 extern "C" {
  19 #endif
  20
  21 //------------------------------------------------------------------------------
  22 // Helpful macro.
  23
  24 # define SANITY_CHECK(in, out)                              \
  25   assert(in != NULL);                                       \
  26   assert(out != NULL);                                      \
  27   assert(width > 0);                                        \
  28   assert(height > 0);                                       \
  29   assert(stride >= width);
  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 inverse, uint8_t* out) {
  47   int h;
  48   const uint8_t* preds = (inverse ? out : in);
  49   SANITY_CHECK(in, out);
  50
  51   // Filter line-by-line.
  52   for (h = 0; h < height; ++h) {
  53     // Leftmost pixel is predicted from above (except for topmost scanline).
  54     if (h == 0) {
  55       out[0] = in[0];
  56     } else {
  57       PredictLine(in, preds - stride, out, 1, inverse);
  58     }
  59     PredictLine(in + 1, preds, out + 1, width - 1, inverse);
  60     preds += stride;
  61     in += stride;
  62     out += stride;
  63   }
  64 }
  65
  66 static void HorizontalFilter(const uint8_t* data, int width, int height,
  67                              int stride, uint8_t* filtered_data) {
  68   DoHorizontalFilter(data, width, height, stride, 0, filtered_data);
  69 }
  70
  71 static void HorizontalUnfilter(int width, int height, int stride,
  72                                uint8_t* data) {
  73   DoHorizontalFilter(data, width, height, stride, 1, data);
  74 }
  75
  76 //------------------------------------------------------------------------------
  77 // Vertical filter.
  78
  79 static WEBP_INLINE void DoVerticalFilter(const uint8_t* in,
  80                                          int width, int height, int stride,
  81                                          int inverse, uint8_t* out) {
  82   int h;
  83   const uint8_t* preds = (inverse ? out : in);
  84   SANITY_CHECK(in, out);
  85
  86   // Very first top-left pixel is copied.
  87   out[0] = in[0];
  88   // Rest of top scan-line is left-predicted.
  89   PredictLine(in + 1, preds, out + 1, width - 1, inverse);
  90
  91   // Filter line-by-line.
  92   for (h = 1; h < height; ++h) {
  93     in += stride;
  94     out += stride;
  95     PredictLine(in, preds, out, width, inverse);
  96     preds += stride;
  97   }
  98 }
  99
 100 static void VerticalFilter(const uint8_t* data, int width, int height,
 101                            int stride, uint8_t* filtered_data) {
 102   DoVerticalFilter(data, width, height, stride, 0, filtered_data);
 103 }
 104
 105 static void VerticalUnfilter(int width, int height, int stride, uint8_t* data) {
 106   DoVerticalFilter(data, width, height, stride, 1, data);
 107 }
 108
 109 //------------------------------------------------------------------------------
 110 // Gradient filter.
 111
 112 static WEBP_INLINE int GradientPredictor(uint8_t a, uint8_t b, uint8_t c) {
 113   const int g = a + b - c;
 114   return ((g & ~0xff) == 0) ? g : (g < 0) ? 0 : 255;  // clip to 8bit
 115 }
 116
 117 static WEBP_INLINE
 118 void DoGradientFilter(const uint8_t* in, int width, int height,
 119                       int stride, int inverse, uint8_t* out) {
 120   const uint8_t* preds = (inverse ? out : in);
 121   int h;
 122   SANITY_CHECK(in, out);
 123
 124   // left prediction for top scan-line
 125   out[0] = in[0];
 126   PredictLine(in + 1, preds, out + 1, width - 1, inverse);
 127
 128   // Filter line-by-line.
 129   for (h = 1; h < height; ++h) {
 130     int w;
 131     preds += stride;
 132     in += stride;
 133     out += stride;
 134     // leftmost pixel: predict from above.
 135     PredictLine(in, preds - stride, out, 1, inverse);
 136     for (w = 1; w < width; ++w) {
 137       const int pred = GradientPredictor(preds[w - 1],
 138                                          preds[w - stride],
 139                                          preds[w - stride - 1]);
 140       out[w] = in[w] + (inverse ? pred : -pred);
 141     }
 142   }
 143 }
 144
 145 static void GradientFilter(const uint8_t* data, int width, int height,
 146                            int stride, uint8_t* filtered_data) {
 147   DoGradientFilter(data, width, height, stride, 0, filtered_data);
 148 }
 149
 150 static void GradientUnfilter(int width, int height, int stride, uint8_t* data) {
 151   DoGradientFilter(data, width, height, stride, 1, data);
 152 }
 153
 154 #undef SANITY_CHECK
 155
 156 // -----------------------------------------------------------------------------
 157 // Quick estimate of a potentially interesting filter mode to try.
 158
 159 #define SMAX 16
 160 #define SDIFF(a, b) (abs((a) - (b)) >> 4)   // Scoring diff, in [0..SMAX)
 161
 162 WEBP_FILTER_TYPE EstimateBestFilter(const uint8_t* data,
 163                                     int width, int height, int stride) {
 164   int i, j;
 165   int bins[WEBP_FILTER_LAST][SMAX];
 166   memset(bins, 0, sizeof(bins));
 167
 168   // We only sample every other pixels. That's enough.
 169   for (j = 2; j < height - 1; j += 2) {
 170     const uint8_t* const p = data + j * stride;
 171     int mean = p[0];
 172     for (i = 2; i < width - 1; i += 2) {
 173       const int diff0 = SDIFF(p[i], mean);
 174       const int diff1 = SDIFF(p[i], p[i - 1]);
 175       const int diff2 = SDIFF(p[i], p[i - width]);
 176       const int grad_pred =
 177           GradientPredictor(p[i - 1], p[i - width], p[i - width - 1]);
 178       const int diff3 = SDIFF(p[i], grad_pred);
 179       bins[WEBP_FILTER_NONE][diff0] = 1;
 180       bins[WEBP_FILTER_HORIZONTAL][diff1] = 1;
 181       bins[WEBP_FILTER_VERTICAL][diff2] = 1;
 182       bins[WEBP_FILTER_GRADIENT][diff3] = 1;
 183       mean = (3 * mean + p[i] + 2) >> 2;
 184     }
 185   }
 186   {
 187     WEBP_FILTER_TYPE filter, best_filter = WEBP_FILTER_NONE;
 188     int best_score = 0x7fffffff;
 189     for (filter = WEBP_FILTER_NONE; filter < WEBP_FILTER_LAST; ++filter) {
 190       int score = 0;
 191       for (i = 0; i < SMAX; ++i) {
 192         if (bins[filter][i] > 0) {
 193           score += i;
 194         }
 195       }
 196       if (score < best_score) {
 197         best_score = score;
 198         best_filter = filter;
 199       }
 200     }
 201     return best_filter;
 202   }
 203 }
 204
 205 #undef SMAX
 206 #undef SDIFF
 207
 208 //------------------------------------------------------------------------------
 209
 210 const WebPFilterFunc WebPFilters[WEBP_FILTER_LAST] = {
 211   NULL,              // WEBP_FILTER_NONE
 212   HorizontalFilter,  // WEBP_FILTER_HORIZONTAL
 213   VerticalFilter,    // WEBP_FILTER_VERTICAL
 214   GradientFilter     // WEBP_FILTER_GRADIENT
 215 };
 216
 217 const WebPUnfilterFunc WebPUnfilters[WEBP_FILTER_LAST] = {
 218   NULL,                // WEBP_FILTER_NONE
 219   HorizontalUnfilter,  // WEBP_FILTER_HORIZONTAL
 220   VerticalUnfilter,    // WEBP_FILTER_VERTICAL
 221   GradientUnfilter     // WEBP_FILTER_GRADIENT
 222 };
 223
 224 //------------------------------------------------------------------------------
 225
 226 #if defined(__cplusplus) || defined(c_plusplus)
 227 }    // extern "C"
 228 #endif