skia/ext/convolver_unittest.cc

   1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <string.h>
   6 #include <time.h>
   7 #include <vector>
   8
   9 #include "base/basictypes.h"
  10 #include "base/logging.h"
  11 #include "base/time.h"
  12 #include "skia/ext/convolver.h"
  13 #include "testing/gtest/include/gtest/gtest.h"
  14 #include "third_party/skia/include/core/SkBitmap.h"
  15 #include "third_party/skia/include/core/SkColorPriv.h"
  16 #include "third_party/skia/include/core/SkRect.h"
  17 #include "third_party/skia/include/core/SkTypes.h"
  18
  19 namespace skia {
  20
  21 namespace {
  22
  23 // Fills the given filter with impulse functions for the range 0->num_entries.
  24 void FillImpulseFilter(int num_entries, ConvolutionFilter1D* filter) {
  25   float one = 1.0f;
  26   for (int i = 0; i < num_entries; i++)
  27     filter->AddFilter(i, &one, 1);
  28 }
  29
  30 // Filters the given input with the impulse function, and verifies that it
  31 // does not change.
  32 void TestImpulseConvolution(const unsigned char* data, int width, int height) {
  33   int byte_count = width * height * 4;
  34
  35   ConvolutionFilter1D filter_x;
  36   FillImpulseFilter(width, &filter_x);
  37
  38   ConvolutionFilter1D filter_y;
  39   FillImpulseFilter(height, &filter_y);
  40
  41   std::vector<unsigned char> output;
  42   output.resize(byte_count);
  43   BGRAConvolve2D(data, width * 4, true, filter_x, filter_y,
  44                  filter_x.num_values() * 4, &output[0], false);
  45
  46   // Output should exactly match input.
  47   EXPECT_EQ(0, memcmp(data, &output[0], byte_count));
  48 }
  49
  50 // Fills the destination filter with a box filter averaging every two pixels
  51 // to produce the output.
  52 void FillBoxFilter(int size, ConvolutionFilter1D* filter) {
  53   const float box[2] = { 0.5, 0.5 };
  54   for (int i = 0; i < size; i++)
  55     filter->AddFilter(i * 2, box, 2);
  56 }
  57
  58 }  // namespace
  59
  60 // Tests that each pixel, when set and run through the impulse filter, does
  61 // not change.
  62 TEST(Convolver, Impulse) {
  63   // We pick an "odd" size that is not likely to fit on any boundaries so that
  64   // we can see if all the widths and paddings are handled properly.
  65   int width = 15;
  66   int height = 31;
  67   int byte_count = width * height * 4;
  68   std::vector<unsigned char> input;
  69   input.resize(byte_count);
  70
  71   unsigned char* input_ptr = &input[0];
  72   for (int y = 0; y < height; y++) {
  73     for (int x = 0; x < width; x++) {
  74       for (int channel = 0; channel < 3; channel++) {
  75         memset(input_ptr, 0, byte_count);
  76         input_ptr[(y * width + x) * 4 + channel] = 0xff;
  77         // Always set the alpha channel or it will attempt to "fix" it for us.
  78         input_ptr[(y * width + x) * 4 + 3] = 0xff;
  79         TestImpulseConvolution(input_ptr, width, height);
  80       }
  81     }
  82   }
  83 }
  84
  85 // Tests that using a box filter to halve an image results in every square of 4
  86 // pixels in the original get averaged to a pixel in the output.
  87 TEST(Convolver, Halve) {
  88   static const int kSize = 16;
  89
  90   int src_width = kSize;
  91   int src_height = kSize;
  92   int src_row_stride = src_width * 4;
  93   int src_byte_count = src_row_stride * src_height;
  94   std::vector<unsigned char> input;
  95   input.resize(src_byte_count);
  96
  97   int dest_width = src_width / 2;
  98   int dest_height = src_height / 2;
  99   int dest_byte_count = dest_width * dest_height * 4;
 100   std::vector<unsigned char> output;
 101   output.resize(dest_byte_count);
 102
 103   // First fill the array with a bunch of random data.
 104   srand(static_cast<unsigned>(time(NULL)));
 105   for (int i = 0; i < src_byte_count; i++)
 106     input[i] = rand() * 255 / RAND_MAX;
 107
 108   // Compute the filters.
 109   ConvolutionFilter1D filter_x, filter_y;
 110   FillBoxFilter(dest_width, &filter_x);
 111   FillBoxFilter(dest_height, &filter_y);
 112
 113   // Do the convolution.
 114   BGRAConvolve2D(&input[0], src_width, true, filter_x, filter_y,
 115                  filter_x.num_values() * 4, &output[0], false);
 116
 117   // Compute the expected results and check, allowing for a small difference
 118   // to account for rounding errors.
 119   for (int y = 0; y < dest_height; y++) {
 120     for (int x = 0; x < dest_width; x++) {
 121       for (int channel = 0; channel < 4; channel++) {
 122         int src_offset = (y * 2 * src_row_stride + x * 2 * 4) + channel;
 123         int value = input[src_offset] +  // Top left source pixel.
 124                     input[src_offset + 4] +  // Top right source pixel.
 125                     input[src_offset + src_row_stride] +  // Lower left.
 126                     input[src_offset + src_row_stride + 4];  // Lower right.
 127         value /= 4;  // Average.
 128         int difference = value - output[(y * dest_width + x) * 4 + channel];
 129         EXPECT_TRUE(difference >= -1 || difference <= 1);
 130       }
 131     }
 132   }
 133 }
 134
 135 // Tests the optimization in Convolver1D::AddFilter that avoids storing
 136 // leading/trailing zeroes.
 137 TEST(Convolver, AddFilter) {
 138   skia::ConvolutionFilter1D filter;
 139
 140   const skia::ConvolutionFilter1D::Fixed* values = NULL;
 141   int filter_offset = 0;
 142   int filter_length = 0;
 143
 144   // An all-zero filter is handled correctly, all factors ignored
 145   static const float factors1[] = { 0.0f, 0.0f, 0.0f };
 146   filter.AddFilter(11, factors1, arraysize(factors1));
 147   ASSERT_EQ(0, filter.max_filter());
 148   ASSERT_EQ(1, filter.num_values());
 149
 150   values = filter.FilterForValue(0, &filter_offset, &filter_length);
 151   ASSERT_TRUE(values == NULL);   // No values => NULL.
 152   ASSERT_EQ(11, filter_offset);  // Same as input offset.
 153   ASSERT_EQ(0, filter_length);   // But no factors since all are zeroes.
 154
 155   // Zeroes on the left are ignored
 156   static const float factors2[] = { 0.0f, 1.0f, 1.0f, 1.0f, 1.0f };
 157   filter.AddFilter(22, factors2, arraysize(factors2));
 158   ASSERT_EQ(4, filter.max_filter());
 159   ASSERT_EQ(2, filter.num_values());
 160
 161   values = filter.FilterForValue(1, &filter_offset, &filter_length);
 162   ASSERT_TRUE(values != NULL);
 163   ASSERT_EQ(23, filter_offset);  // 22 plus 1 leading zero
 164   ASSERT_EQ(4, filter_length);   // 5 - 1 leading zero
 165
 166   // Zeroes on the right are ignored
 167   static const float factors3[] = { 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 0.0f, 0.0f };
 168   filter.AddFilter(33, factors3, arraysize(factors3));
 169   ASSERT_EQ(5, filter.max_filter());
 170   ASSERT_EQ(3, filter.num_values());
 171
 172   values = filter.FilterForValue(2, &filter_offset, &filter_length);
 173   ASSERT_TRUE(values != NULL);
 174   ASSERT_EQ(33, filter_offset);  // 33, same as input due to no leading zero
 175   ASSERT_EQ(5, filter_length);   // 7 - 2 trailing zeroes
 176
 177   // Zeroes in leading & trailing positions
 178   static const float factors4[] = { 0.0f, 0.0f, 1.0f, 1.0f, 1.0f, 0.0f, 0.0f };
 179   filter.AddFilter(44, factors4, arraysize(factors4));
 180   ASSERT_EQ(5, filter.max_filter());  // No change from existing value.
 181   ASSERT_EQ(4, filter.num_values());
 182
 183   values = filter.FilterForValue(3, &filter_offset, &filter_length);
 184   ASSERT_TRUE(values != NULL);
 185   ASSERT_EQ(46, filter_offset);  // 44 plus 2 leading zeroes
 186   ASSERT_EQ(3, filter_length);   // 7 - (2 leading + 2 trailing) zeroes
 187
 188   // Zeroes surrounded by non-zero values are ignored
 189   static const float factors5[] = { 0.0f, 0.0f,
 190                                     1.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f,
 191                                     0.0f };
 192   filter.AddFilter(55, factors5, arraysize(factors5));
 193   ASSERT_EQ(6, filter.max_filter());
 194   ASSERT_EQ(5, filter.num_values());
 195
 196   values = filter.FilterForValue(4, &filter_offset, &filter_length);
 197   ASSERT_TRUE(values != NULL);
 198   ASSERT_EQ(57, filter_offset);  // 55 plus 2 leading zeroes
 199   ASSERT_EQ(6, filter_length);   // 9 - (2 leading + 1 trailing) zeroes
 200
 201   // All-zero filters after the first one also work
 202   static const float factors6[] = { 0.0f };
 203   filter.AddFilter(66, factors6, arraysize(factors6));
 204   ASSERT_EQ(6, filter.max_filter());
 205   ASSERT_EQ(6, filter.num_values());
 206
 207   values = filter.FilterForValue(5, &filter_offset, &filter_length);
 208   ASSERT_TRUE(values == NULL);   // filter_length == 0 => values is NULL
 209   ASSERT_EQ(66, filter_offset);  // value passed in
 210   ASSERT_EQ(0, filter_length);
 211 }
 212
 213 TEST(Convolver, SIMDVerification) {
 214   int source_sizes[][2] = {
 215     {1,1}, {1,2}, {1,3}, {1,4}, {1,5},
 216     {2,1}, {2,2}, {2,3}, {2,4}, {2,5},
 217     {3,1}, {3,2}, {3,3}, {3,4}, {3,5},
 218     {4,1}, {4,2}, {4,3}, {4,4}, {4,5},
 219     {1920, 1080},
 220     {720, 480},
 221     {1377, 523},
 222     {325, 241} };
 223   int dest_sizes[][2] = { {1280, 1024}, {480, 270}, {177, 123} };
 224   float filter[] = { 0.05f, -0.15f, 0.6f, 0.6f, -0.15f, 0.05f };
 225
 226   srand(static_cast<unsigned int>(time(0)));
 227
 228   // Loop over some specific source and destination dimensions.
 229   for (unsigned int i = 0; i < arraysize(source_sizes); ++i) {
 230     unsigned int source_width = source_sizes[i][0];
 231     unsigned int source_height = source_sizes[i][1];
 232     for (unsigned int j = 0; j < arraysize(dest_sizes); ++j) {
 233       unsigned int dest_width = dest_sizes[j][0];
 234       unsigned int dest_height = dest_sizes[j][1];
 235
 236       // Preparing convolve coefficients.
 237       ConvolutionFilter1D x_filter, y_filter;
 238       for (unsigned int p = 0; p < dest_width; ++p) {
 239         unsigned int offset = source_width * p / dest_width;
 240         EXPECT_LT(offset, source_width);
 241         x_filter.AddFilter(offset, filter,
 242                            std::min<int>(arraysize(filter),
 243                                          source_width - offset));
 244       }
 245       x_filter.PaddingForSIMD();
 246       for (unsigned int p = 0; p < dest_height; ++p) {
 247         unsigned int offset = source_height * p / dest_height;
 248         y_filter.AddFilter(offset, filter,
 249                            std::min<int>(arraysize(filter),
 250                                          source_height - offset));
 251       }
 252       y_filter.PaddingForSIMD();
 253
 254       // Allocate input and output skia bitmap.
 255       SkBitmap source, result_c, result_sse;
 256       source.setConfig(SkBitmap::kARGB_8888_Config,
 257                        source_width, source_height);
 258       source.allocPixels();
 259       result_c.setConfig(SkBitmap::kARGB_8888_Config,
 260                          dest_width, dest_height);
 261       result_c.allocPixels();
 262       result_sse.setConfig(SkBitmap::kARGB_8888_Config,
 263                            dest_width, dest_height);
 264       result_sse.allocPixels();
 265
 266       // Randomize source bitmap for testing.
 267       unsigned char* src_ptr = static_cast<unsigned char*>(source.getPixels());
 268       for (int y = 0; y < source.height(); y++) {
 269         for (unsigned int x = 0; x < source.rowBytes(); x++)
 270           src_ptr[x] = rand() % 255;
 271         src_ptr += source.rowBytes();
 272       }
 273
 274       // Test both cases with different has_alpha.
 275       for (int alpha = 0; alpha < 2; alpha++) {
 276         // Convolve using C code.
 277         base::TimeTicks resize_start;
 278         base::TimeDelta delta_c, delta_sse;
 279         unsigned char* r1 = static_cast<unsigned char*>(result_c.getPixels());
 280         unsigned char* r2 = static_cast<unsigned char*>(result_sse.getPixels());
 281
 282         resize_start = base::TimeTicks::Now();
 283         BGRAConvolve2D(static_cast<const uint8*>(source.getPixels()),
 284                        static_cast<int>(source.rowBytes()),
 285                        (alpha != 0), x_filter, y_filter,
 286                        static_cast<int>(result_c.rowBytes()), r1, false);
 287         delta_c = base::TimeTicks::Now() - resize_start;
 288
 289         resize_start = base::TimeTicks::Now();
 290         // Convolve using SSE2 code
 291         BGRAConvolve2D(static_cast<const uint8*>(source.getPixels()),
 292                        static_cast<int>(source.rowBytes()),
 293                        (alpha != 0), x_filter, y_filter,
 294                        static_cast<int>(result_sse.rowBytes()), r2, true);
 295         delta_sse = base::TimeTicks::Now() - resize_start;
 296
 297         // Unfortunately I could not enable the performance check now.
 298         // Most bots use debug version, and there are great difference between
 299         // the code generation for intrinsic, etc. In release version speed
 300         // difference was 150%-200% depend on alpha channel presence;
 301         // while in debug version speed difference was 96%-120%.
 302         // TODO(jiesun): optimize further until we could enable this for
 303         // debug version too.
 304         // EXPECT_LE(delta_sse, delta_c);
 305
 306         int64 c_us = delta_c.InMicroseconds();
 307         int64 sse_us = delta_sse.InMicroseconds();
 308         VLOG(1) << "from:" << source_width << "x" << source_height
 309                 << " to:" << dest_width << "x" << dest_height
 310                 << (alpha ? " with alpha" : " w/o alpha");
 311         VLOG(1) << "c:" << c_us << " sse:" << sse_us;
 312         VLOG(1) << "ratio:" << static_cast<float>(c_us) / sse_us;
 313
 314         // Comparing result.
 315         for (unsigned int i = 0; i < dest_height; i++) {
 316           for (unsigned int x = 0; x < dest_width * 4; x++) {  // RGBA always.
 317             EXPECT_EQ(r1[x], r2[x]);
 318           }
 319           r1 += result_c.rowBytes();
 320           r2 += result_sse.rowBytes();
 321         }
 322       }
 323     }
 324   }
 325 }
 326
 327 }  // namespace skia