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
PredictLine(const uint8_t * src,const uint8_t * pred,uint8_t * dst,int length,int inverse)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
DoHorizontalFilter(const uint8_t * in,int width,int height,int stride,int row,int num_rows,int inverse,uint8_t * out)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
HorizontalFilter(const uint8_t * data,int width,int height,int stride,uint8_t * filtered_data)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
HorizontalUnfilter(int width,int height,int stride,int row,int num_rows,uint8_t * data)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
DoVerticalFilter(const uint8_t * in,int width,int height,int stride,int row,int num_rows,int inverse,uint8_t * out)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
VerticalFilter(const uint8_t * data,int width,int height,int stride,uint8_t * filtered_data)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
VerticalUnfilter(int width,int height,int stride,int row,int num_rows,uint8_t * data)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
GradientPredictor(uint8_t a,uint8_t b,uint8_t c)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
DoGradientFilter(const uint8_t * in,int width,int height,int stride,int row,int num_rows,int inverse,uint8_t * out)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
GradientFilter(const uint8_t * data,int width,int height,int stride,uint8_t * filtered_data)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
GradientUnfilter(int width,int height,int stride,int row,int num_rows,uint8_t * data)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
EstimateBestFilter(const uint8_t * data,int width,int height,int stride)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
267