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