Pin Chrome's shortcut to the Win10 Start menu on install and OS upgrade.
[chromium-blink-merge.git] / skia / ext / convolver_unittest.cc
blobe833b45a7139fd84c817a4789a84d17229082477
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.
5 #include <string.h>
6 #include <time.h>
7 #include <algorithm>
8 #include <numeric>
9 #include <vector>
11 #include "base/basictypes.h"
12 #include "base/logging.h"
13 #include "base/time/time.h"
14 #include "skia/ext/convolver.h"
15 #include "testing/gtest/include/gtest/gtest.h"
16 #include "third_party/skia/include/core/SkBitmap.h"
17 #include "third_party/skia/include/core/SkColorPriv.h"
18 #include "third_party/skia/include/core/SkRect.h"
19 #include "third_party/skia/include/core/SkTypes.h"
21 namespace skia {
23 namespace {
25 // Fills the given filter with impulse functions for the range 0->num_entries.
26 void FillImpulseFilter(int num_entries, ConvolutionFilter1D* filter) {
27 float one = 1.0f;
28 for (int i = 0; i < num_entries; i++)
29 filter->AddFilter(i, &one, 1);
32 // Filters the given input with the impulse function, and verifies that it
33 // does not change.
34 void TestImpulseConvolution(const unsigned char* data, int width, int height) {
35 int byte_count = width * height * 4;
37 ConvolutionFilter1D filter_x;
38 FillImpulseFilter(width, &filter_x);
40 ConvolutionFilter1D filter_y;
41 FillImpulseFilter(height, &filter_y);
43 std::vector<unsigned char> output;
44 output.resize(byte_count);
45 BGRAConvolve2D(data, width * 4, true, filter_x, filter_y,
46 filter_x.num_values() * 4, &output[0], false);
48 // Output should exactly match input.
49 EXPECT_EQ(0, memcmp(data, &output[0], byte_count));
52 // Fills the destination filter with a box filter averaging every two pixels
53 // to produce the output.
54 void FillBoxFilter(int size, ConvolutionFilter1D* filter) {
55 const float box[2] = { 0.5, 0.5 };
56 for (int i = 0; i < size; i++)
57 filter->AddFilter(i * 2, box, 2);
60 } // namespace
62 // Tests that each pixel, when set and run through the impulse filter, does
63 // not change.
64 TEST(Convolver, Impulse) {
65 // We pick an "odd" size that is not likely to fit on any boundaries so that
66 // we can see if all the widths and paddings are handled properly.
67 int width = 15;
68 int height = 31;
69 int byte_count = width * height * 4;
70 std::vector<unsigned char> input;
71 input.resize(byte_count);
73 unsigned char* input_ptr = &input[0];
74 for (int y = 0; y < height; y++) {
75 for (int x = 0; x < width; x++) {
76 for (int channel = 0; channel < 3; channel++) {
77 memset(input_ptr, 0, byte_count);
78 input_ptr[(y * width + x) * 4 + channel] = 0xff;
79 // Always set the alpha channel or it will attempt to "fix" it for us.
80 input_ptr[(y * width + x) * 4 + 3] = 0xff;
81 TestImpulseConvolution(input_ptr, width, height);
87 // Tests that using a box filter to halve an image results in every square of 4
88 // pixels in the original get averaged to a pixel in the output.
89 TEST(Convolver, Halve) {
90 static const int kSize = 16;
92 int src_width = kSize;
93 int src_height = kSize;
94 int src_row_stride = src_width * 4;
95 int src_byte_count = src_row_stride * src_height;
96 std::vector<unsigned char> input;
97 input.resize(src_byte_count);
99 int dest_width = src_width / 2;
100 int dest_height = src_height / 2;
101 int dest_byte_count = dest_width * dest_height * 4;
102 std::vector<unsigned char> output;
103 output.resize(dest_byte_count);
105 // First fill the array with a bunch of random data.
106 srand(static_cast<unsigned>(time(NULL)));
107 for (int i = 0; i < src_byte_count; i++)
108 input[i] = rand() * 255 / RAND_MAX;
110 // Compute the filters.
111 ConvolutionFilter1D filter_x, filter_y;
112 FillBoxFilter(dest_width, &filter_x);
113 FillBoxFilter(dest_height, &filter_y);
115 // Do the convolution.
116 BGRAConvolve2D(&input[0], src_width, true, filter_x, filter_y,
117 filter_x.num_values() * 4, &output[0], false);
119 // Compute the expected results and check, allowing for a small difference
120 // to account for rounding errors.
121 for (int y = 0; y < dest_height; y++) {
122 for (int x = 0; x < dest_width; x++) {
123 for (int channel = 0; channel < 4; channel++) {
124 int src_offset = (y * 2 * src_row_stride + x * 2 * 4) + channel;
125 int value = input[src_offset] + // Top left source pixel.
126 input[src_offset + 4] + // Top right source pixel.
127 input[src_offset + src_row_stride] + // Lower left.
128 input[src_offset + src_row_stride + 4]; // Lower right.
129 value /= 4; // Average.
130 int difference = value - output[(y * dest_width + x) * 4 + channel];
131 EXPECT_TRUE(difference >= -1 || difference <= 1);
137 // Tests the optimization in Convolver1D::AddFilter that avoids storing
138 // leading/trailing zeroes.
139 TEST(Convolver, AddFilter) {
140 skia::ConvolutionFilter1D filter;
142 const skia::ConvolutionFilter1D::Fixed* values = NULL;
143 int filter_offset = 0;
144 int filter_length = 0;
146 // An all-zero filter is handled correctly, all factors ignored
147 static const float factors1[] = { 0.0f, 0.0f, 0.0f };
148 filter.AddFilter(11, factors1, arraysize(factors1));
149 ASSERT_EQ(0, filter.max_filter());
150 ASSERT_EQ(1, filter.num_values());
152 values = filter.FilterForValue(0, &filter_offset, &filter_length);
153 ASSERT_TRUE(values == NULL); // No values => NULL.
154 ASSERT_EQ(11, filter_offset); // Same as input offset.
155 ASSERT_EQ(0, filter_length); // But no factors since all are zeroes.
157 // Zeroes on the left are ignored
158 static const float factors2[] = { 0.0f, 1.0f, 1.0f, 1.0f, 1.0f };
159 filter.AddFilter(22, factors2, arraysize(factors2));
160 ASSERT_EQ(4, filter.max_filter());
161 ASSERT_EQ(2, filter.num_values());
163 values = filter.FilterForValue(1, &filter_offset, &filter_length);
164 ASSERT_TRUE(values != NULL);
165 ASSERT_EQ(23, filter_offset); // 22 plus 1 leading zero
166 ASSERT_EQ(4, filter_length); // 5 - 1 leading zero
168 // Zeroes on the right are ignored
169 static const float factors3[] = { 1.0f, 1.0f, 1.0f, 1.0f, 1.0f, 0.0f, 0.0f };
170 filter.AddFilter(33, factors3, arraysize(factors3));
171 ASSERT_EQ(5, filter.max_filter());
172 ASSERT_EQ(3, filter.num_values());
174 values = filter.FilterForValue(2, &filter_offset, &filter_length);
175 ASSERT_TRUE(values != NULL);
176 ASSERT_EQ(33, filter_offset); // 33, same as input due to no leading zero
177 ASSERT_EQ(5, filter_length); // 7 - 2 trailing zeroes
179 // Zeroes in leading & trailing positions
180 static const float factors4[] = { 0.0f, 0.0f, 1.0f, 1.0f, 1.0f, 0.0f, 0.0f };
181 filter.AddFilter(44, factors4, arraysize(factors4));
182 ASSERT_EQ(5, filter.max_filter()); // No change from existing value.
183 ASSERT_EQ(4, filter.num_values());
185 values = filter.FilterForValue(3, &filter_offset, &filter_length);
186 ASSERT_TRUE(values != NULL);
187 ASSERT_EQ(46, filter_offset); // 44 plus 2 leading zeroes
188 ASSERT_EQ(3, filter_length); // 7 - (2 leading + 2 trailing) zeroes
190 // Zeroes surrounded by non-zero values are ignored
191 static const float factors5[] = { 0.0f, 0.0f,
192 1.0f, 0.0f, 0.0f, 0.0f, 0.0f, 1.0f,
193 0.0f };
194 filter.AddFilter(55, factors5, arraysize(factors5));
195 ASSERT_EQ(6, filter.max_filter());
196 ASSERT_EQ(5, filter.num_values());
198 values = filter.FilterForValue(4, &filter_offset, &filter_length);
199 ASSERT_TRUE(values != NULL);
200 ASSERT_EQ(57, filter_offset); // 55 plus 2 leading zeroes
201 ASSERT_EQ(6, filter_length); // 9 - (2 leading + 1 trailing) zeroes
203 // All-zero filters after the first one also work
204 static const float factors6[] = { 0.0f };
205 filter.AddFilter(66, factors6, arraysize(factors6));
206 ASSERT_EQ(6, filter.max_filter());
207 ASSERT_EQ(6, filter.num_values());
209 values = filter.FilterForValue(5, &filter_offset, &filter_length);
210 ASSERT_TRUE(values == NULL); // filter_length == 0 => values is NULL
211 ASSERT_EQ(66, filter_offset); // value passed in
212 ASSERT_EQ(0, filter_length);
215 void VerifySIMD(unsigned int source_width,
216 unsigned int source_height,
217 unsigned int dest_width,
218 unsigned int dest_height) {
219 float filter[] = { 0.05f, -0.15f, 0.6f, 0.6f, -0.15f, 0.05f };
220 // Preparing convolve coefficients.
221 ConvolutionFilter1D x_filter, y_filter;
222 for (unsigned int p = 0; p < dest_width; ++p) {
223 unsigned int offset = source_width * p / dest_width;
224 EXPECT_LT(offset, source_width);
225 x_filter.AddFilter(offset, filter,
226 std::min<int>(arraysize(filter),
227 source_width - offset));
229 x_filter.PaddingForSIMD();
230 for (unsigned int p = 0; p < dest_height; ++p) {
231 unsigned int offset = source_height * p / dest_height;
232 y_filter.AddFilter(offset, filter,
233 std::min<int>(arraysize(filter),
234 source_height - offset));
236 y_filter.PaddingForSIMD();
238 // Allocate input and output skia bitmap.
239 SkBitmap source, result_c, result_sse;
240 source.allocN32Pixels(source_width, source_height);
241 result_c.allocN32Pixels(dest_width, dest_height);
242 result_sse.allocN32Pixels(dest_width, dest_height);
244 // Randomize source bitmap for testing.
245 unsigned char* src_ptr = static_cast<unsigned char*>(source.getPixels());
246 for (int y = 0; y < source.height(); y++) {
247 for (unsigned int x = 0; x < source.rowBytes(); x++)
248 src_ptr[x] = rand() % 255;
249 src_ptr += source.rowBytes();
252 // Test both cases with different has_alpha.
253 for (int alpha = 0; alpha < 2; alpha++) {
254 // Convolve using C code.
255 base::TimeTicks resize_start;
256 base::TimeDelta delta_c, delta_sse;
257 unsigned char* r1 = static_cast<unsigned char*>(result_c.getPixels());
258 unsigned char* r2 = static_cast<unsigned char*>(result_sse.getPixels());
260 resize_start = base::TimeTicks::Now();
261 BGRAConvolve2D(static_cast<const uint8*>(source.getPixels()),
262 static_cast<int>(source.rowBytes()),
263 (alpha != 0), x_filter, y_filter,
264 static_cast<int>(result_c.rowBytes()), r1, false);
265 delta_c = base::TimeTicks::Now() - resize_start;
267 resize_start = base::TimeTicks::Now();
268 // Convolve using SSE2 code
269 BGRAConvolve2D(static_cast<const uint8*>(source.getPixels()),
270 static_cast<int>(source.rowBytes()),
271 (alpha != 0), x_filter, y_filter,
272 static_cast<int>(result_sse.rowBytes()), r2, true);
273 delta_sse = base::TimeTicks::Now() - resize_start;
275 // Unfortunately I could not enable the performance check now.
276 // Most bots use debug version, and there are great difference between
277 // the code generation for intrinsic, etc. In release version speed
278 // difference was 150%-200% depend on alpha channel presence;
279 // while in debug version speed difference was 96%-120%.
280 // TODO(jiesun): optimize further until we could enable this for
281 // debug version too.
282 // EXPECT_LE(delta_sse, delta_c);
284 int64 c_us = delta_c.InMicroseconds();
285 int64 sse_us = delta_sse.InMicroseconds();
286 VLOG(1) << "from:" << source_width << "x" << source_height
287 << " to:" << dest_width << "x" << dest_height
288 << (alpha ? " with alpha" : " w/o alpha");
289 VLOG(1) << "c:" << c_us << " sse:" << sse_us;
290 VLOG(1) << "ratio:" << static_cast<float>(c_us) / sse_us;
292 // Comparing result.
293 for (unsigned int i = 0; i < dest_height; i++) {
294 EXPECT_FALSE(memcmp(r1, r2, dest_width * 4)); // RGBA always
295 r1 += result_c.rowBytes();
296 r2 += result_sse.rowBytes();
301 TEST(Convolver, VerifySIMDEdgeCases) {
302 srand(static_cast<unsigned int>(time(0)));
303 // Loop over all possible (small) image sizes
304 for (unsigned int width = 1; width < 20; width++) {
305 for (unsigned int height = 1; height < 20; height++) {
306 VerifySIMD(width, height, 8, 8);
307 VerifySIMD(8, 8, width, height);
312 // Verify that lage upscales/downscales produce the same result
313 // with and without SIMD.
314 TEST(Convolver, VerifySIMDPrecision) {
315 int source_sizes[][2] = { {1920, 1080}, {1377, 523}, {325, 241} };
316 int dest_sizes[][2] = { {1280, 1024}, {177, 123} };
318 srand(static_cast<unsigned int>(time(0)));
320 // Loop over some specific source and destination dimensions.
321 for (unsigned int i = 0; i < arraysize(source_sizes); ++i) {
322 unsigned int source_width = source_sizes[i][0];
323 unsigned int source_height = source_sizes[i][1];
324 for (unsigned int j = 0; j < arraysize(dest_sizes); ++j) {
325 unsigned int dest_width = dest_sizes[j][0];
326 unsigned int dest_height = dest_sizes[j][1];
327 VerifySIMD(source_width, source_height, dest_width, dest_height);
332 TEST(Convolver, SeparableSingleConvolution) {
333 static const int kImgWidth = 1024;
334 static const int kImgHeight = 1024;
335 static const int kChannelCount = 3;
336 static const int kStrideSlack = 22;
337 ConvolutionFilter1D filter;
338 const float box[5] = { 0.2f, 0.2f, 0.2f, 0.2f, 0.2f };
339 filter.AddFilter(0, box, 5);
341 // Allocate a source image and set to 0.
342 const int src_row_stride = kImgWidth * kChannelCount + kStrideSlack;
343 int src_byte_count = src_row_stride * kImgHeight;
344 std::vector<unsigned char> input;
345 const int signal_x = kImgWidth / 2;
346 const int signal_y = kImgHeight / 2;
347 input.resize(src_byte_count, 0);
348 // The image has a single impulse pixel in channel 1, smack in the middle.
349 const int non_zero_pixel_index =
350 signal_y * src_row_stride + signal_x * kChannelCount + 1;
351 input[non_zero_pixel_index] = 255;
353 // Destination will be a single channel image with stide matching width.
354 const int dest_row_stride = kImgWidth;
355 const int dest_byte_count = dest_row_stride * kImgHeight;
356 std::vector<unsigned char> output;
357 output.resize(dest_byte_count);
359 // Apply convolution in X.
360 SingleChannelConvolveX1D(&input[0], src_row_stride, 1, kChannelCount,
361 filter, SkISize::Make(kImgWidth, kImgHeight),
362 &output[0], dest_row_stride, 0, 1, false);
363 for (int x = signal_x - 2; x <= signal_x + 2; ++x)
364 EXPECT_GT(output[signal_y * dest_row_stride + x], 0);
366 EXPECT_EQ(output[signal_y * dest_row_stride + signal_x - 3], 0);
367 EXPECT_EQ(output[signal_y * dest_row_stride + signal_x + 3], 0);
369 // Apply convolution in Y.
370 SingleChannelConvolveY1D(&input[0], src_row_stride, 1, kChannelCount,
371 filter, SkISize::Make(kImgWidth, kImgHeight),
372 &output[0], dest_row_stride, 0, 1, false);
373 for (int y = signal_y - 2; y <= signal_y + 2; ++y)
374 EXPECT_GT(output[y * dest_row_stride + signal_x], 0);
376 EXPECT_EQ(output[(signal_y - 3) * dest_row_stride + signal_x], 0);
377 EXPECT_EQ(output[(signal_y + 3) * dest_row_stride + signal_x], 0);
379 EXPECT_EQ(output[signal_y * dest_row_stride + signal_x - 1], 0);
380 EXPECT_EQ(output[signal_y * dest_row_stride + signal_x + 1], 0);
382 // The main point of calling this is to invoke the routine on input without
383 // padding.
384 std::vector<unsigned char> output2;
385 output2.resize(dest_byte_count);
386 SingleChannelConvolveX1D(&output[0], dest_row_stride, 0, 1,
387 filter, SkISize::Make(kImgWidth, kImgHeight),
388 &output2[0], dest_row_stride, 0, 1, false);
389 // This should be a result of 2D convolution.
390 for (int x = signal_x - 2; x <= signal_x + 2; ++x) {
391 for (int y = signal_y - 2; y <= signal_y + 2; ++y)
392 EXPECT_GT(output2[y * dest_row_stride + x], 0);
394 EXPECT_EQ(output2[0], 0);
395 EXPECT_EQ(output2[dest_row_stride - 1], 0);
396 EXPECT_EQ(output2[dest_byte_count - 1], 0);
399 TEST(Convolver, SeparableSingleConvolutionEdges) {
400 // The purpose of this test is to check if the implementation treats correctly
401 // edges of the image.
402 static const int kImgWidth = 600;
403 static const int kImgHeight = 800;
404 static const int kChannelCount = 3;
405 static const int kStrideSlack = 22;
406 static const int kChannel = 1;
407 ConvolutionFilter1D filter;
408 const float box[5] = { 0.2f, 0.2f, 0.2f, 0.2f, 0.2f };
409 filter.AddFilter(0, box, 5);
411 // Allocate a source image and set to 0.
412 int src_row_stride = kImgWidth * kChannelCount + kStrideSlack;
413 int src_byte_count = src_row_stride * kImgHeight;
414 std::vector<unsigned char> input(src_byte_count);
416 // Draw a frame around the image.
417 for (int i = 0; i < src_byte_count; ++i) {
418 int row = i / src_row_stride;
419 int col = i % src_row_stride / kChannelCount;
420 int channel = i % src_row_stride % kChannelCount;
421 if (channel != kChannel || col > kImgWidth) {
422 input[i] = 255;
423 } else if (row == 0 || col == 0 ||
424 col == kImgWidth - 1 || row == kImgHeight - 1) {
425 input[i] = 100;
426 } else if (row == 1 || col == 1 ||
427 col == kImgWidth - 2 || row == kImgHeight - 2) {
428 input[i] = 200;
429 } else {
430 input[i] = 0;
434 // Destination will be a single channel image with stide matching width.
435 int dest_row_stride = kImgWidth;
436 int dest_byte_count = dest_row_stride * kImgHeight;
437 std::vector<unsigned char> output;
438 output.resize(dest_byte_count);
440 // Apply convolution in X.
441 SingleChannelConvolveX1D(&input[0], src_row_stride, 1, kChannelCount,
442 filter, SkISize::Make(kImgWidth, kImgHeight),
443 &output[0], dest_row_stride, 0, 1, false);
445 // Sadly, comparison is not as simple as retaining all values.
446 int invalid_values = 0;
447 const unsigned char first_value = output[0];
448 EXPECT_NEAR(first_value, 100, 1);
449 for (int i = 0; i < dest_row_stride; ++i) {
450 if (output[i] != first_value)
451 ++invalid_values;
453 EXPECT_EQ(0, invalid_values);
455 int test_row = 22;
456 EXPECT_NEAR(output[test_row * dest_row_stride], 100, 1);
457 EXPECT_NEAR(output[test_row * dest_row_stride + 1], 80, 1);
458 EXPECT_NEAR(output[test_row * dest_row_stride + 2], 60, 1);
459 EXPECT_NEAR(output[test_row * dest_row_stride + 3], 40, 1);
460 EXPECT_NEAR(output[(test_row + 1) * dest_row_stride - 1], 100, 1);
461 EXPECT_NEAR(output[(test_row + 1) * dest_row_stride - 2], 80, 1);
462 EXPECT_NEAR(output[(test_row + 1) * dest_row_stride - 3], 60, 1);
463 EXPECT_NEAR(output[(test_row + 1) * dest_row_stride - 4], 40, 1);
465 SingleChannelConvolveY1D(&input[0], src_row_stride, 1, kChannelCount,
466 filter, SkISize::Make(kImgWidth, kImgHeight),
467 &output[0], dest_row_stride, 0, 1, false);
469 int test_column = 42;
470 EXPECT_NEAR(output[test_column], 100, 1);
471 EXPECT_NEAR(output[test_column + dest_row_stride], 80, 1);
472 EXPECT_NEAR(output[test_column + dest_row_stride * 2], 60, 1);
473 EXPECT_NEAR(output[test_column + dest_row_stride * 3], 40, 1);
475 EXPECT_NEAR(output[test_column + dest_row_stride * (kImgHeight - 1)], 100, 1);
476 EXPECT_NEAR(output[test_column + dest_row_stride * (kImgHeight - 2)], 80, 1);
477 EXPECT_NEAR(output[test_column + dest_row_stride * (kImgHeight - 3)], 60, 1);
478 EXPECT_NEAR(output[test_column + dest_row_stride * (kImgHeight - 4)], 40, 1);
481 TEST(Convolver, SetUpGaussianConvolutionFilter) {
482 ConvolutionFilter1D smoothing_filter;
483 ConvolutionFilter1D gradient_filter;
484 SetUpGaussianConvolutionKernel(&smoothing_filter, 4.5f, false);
485 SetUpGaussianConvolutionKernel(&gradient_filter, 3.0f, true);
487 int specified_filter_length;
488 int filter_offset;
489 int filter_length;
491 const ConvolutionFilter1D::Fixed* smoothing_kernel =
492 smoothing_filter.GetSingleFilter(
493 &specified_filter_length, &filter_offset, &filter_length);
494 EXPECT_TRUE(smoothing_kernel);
495 std::vector<float> fp_smoothing_kernel(filter_length);
496 std::transform(smoothing_kernel,
497 smoothing_kernel + filter_length,
498 fp_smoothing_kernel.begin(),
499 ConvolutionFilter1D::FixedToFloat);
500 // Should sum-up to 1 (nearly), and all values whould be in ]0, 1[.
501 EXPECT_NEAR(std::accumulate(
502 fp_smoothing_kernel.begin(), fp_smoothing_kernel.end(), 0.0f),
503 1.0f, 0.01f);
504 EXPECT_GT(*std::min_element(fp_smoothing_kernel.begin(),
505 fp_smoothing_kernel.end()), 0.0f);
506 EXPECT_LT(*std::max_element(fp_smoothing_kernel.begin(),
507 fp_smoothing_kernel.end()), 1.0f);
509 const ConvolutionFilter1D::Fixed* gradient_kernel =
510 gradient_filter.GetSingleFilter(
511 &specified_filter_length, &filter_offset, &filter_length);
512 EXPECT_TRUE(gradient_kernel);
513 std::vector<float> fp_gradient_kernel(filter_length);
514 std::transform(gradient_kernel,
515 gradient_kernel + filter_length,
516 fp_gradient_kernel.begin(),
517 ConvolutionFilter1D::FixedToFloat);
518 // Should sum-up to 0, and all values whould be in ]-1.5, 1.5[.
519 EXPECT_NEAR(std::accumulate(
520 fp_gradient_kernel.begin(), fp_gradient_kernel.end(), 0.0f),
521 0.0f, 0.01f);
522 EXPECT_GT(*std::min_element(fp_gradient_kernel.begin(),
523 fp_gradient_kernel.end()), -1.5f);
524 EXPECT_LT(*std::min_element(fp_gradient_kernel.begin(),
525 fp_gradient_kernel.end()), 0.0f);
526 EXPECT_LT(*std::max_element(fp_gradient_kernel.begin(),
527 fp_gradient_kernel.end()), 1.5f);
528 EXPECT_GT(*std::max_element(fp_gradient_kernel.begin(),
529 fp_gradient_kernel.end()), 0.0f);
532 } // namespace skia