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