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
31static 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
44static 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
78static 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
83static 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
91static 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
126static 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
131static 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
139static 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
144static 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
184static 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
189static 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
202WEBP_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
251const 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
258const 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
267