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