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 (at) 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 267
