1 // Copyright (c) 2006-2012 The Chromium Authors. All rights reserved.
2 //
3 // Redistribution and use in source and binary forms, with or without
4 // modification, are permitted provided that the following conditions
5 // are met:
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above copyright
9 // notice, this list of conditions and the following disclaimer in
10 // the documentation and/or other materials provided with the
11 // distribution.
12 // * Neither the name of Google, Inc. nor the names of its contributors
13 // may be used to endorse or promote products derived from this
14 // software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 // COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
22 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
23 // OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24 // AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26 // OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 // SUCH DAMAGE.
28
29 #include "base/basictypes.h"
30
31 #include <algorithm>
32 #include <cmath>
33 #include <limits>
34
35 #include "image_operations.h"
36
37 #include "base/stack_container.h"
38 #include "convolver.h"
39 #include "skia/include/core/SkColorPriv.h"
40 #include "skia/include/core/SkBitmap.h"
41 #include "skia/include/core/SkRect.h"
42 #include "skia/include/core/SkFontLCDConfig.h"
43
44 namespace skia {
45
46 namespace resize {
47
48 // TODO(egouriou): Take advantage of periods in the convolution.
49 // Practical resizing filters are periodic outside of the border area.
50 // For Lanczos, a scaling by a (reduced) factor of p/q (q pixels in the
51 // source become p pixels in the destination) will have a period of p.
52 // A nice consequence is a period of 1 when downscaling by an integral
53 // factor. Downscaling from typical display resolutions is also bound
54 // to produce interesting periods as those are chosen to have multiple
55 // small factors.
56 // Small periods reduce computational load and improve cache usage if
57 // the coefficients can be shared. For periods of 1 we can consider
58 // loading the factors only once outside the borders.
ComputeFilters(ImageOperations::ResizeMethod method,int src_size,int dst_size,int dest_subset_lo,int dest_subset_size,ConvolutionFilter1D * output)59 void ComputeFilters(ImageOperations::ResizeMethod method,
60 int src_size, int dst_size,
61 int dest_subset_lo, int dest_subset_size,
62 ConvolutionFilter1D* output) {
63 // method_ will only ever refer to an "algorithm method".
64 SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method) &&
65 (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));
66
67 float scale = static_cast<float>(dst_size) / static_cast<float>(src_size);
68
69 int dest_subset_hi = dest_subset_lo + dest_subset_size; // [lo, hi)
70
71 // When we're doing a magnification, the scale will be larger than one. This
72 // means the destination pixels are much smaller than the source pixels, and
73 // that the range covered by the filter won't necessarily cover any source
74 // pixel boundaries. Therefore, we use these clamped values (max of 1) for
75 // some computations.
76 float clamped_scale = std::min(1.0f, scale);
77
78 float src_support = GetFilterSupport(method, clamped_scale) / clamped_scale;
79
80 // Speed up the divisions below by turning them into multiplies.
81 float inv_scale = 1.0f / scale;
82
83 StackVector<float, 64> filter_values;
84 StackVector<int16_t, 64> fixed_filter_values;
85
86 // Loop over all pixels in the output range. We will generate one set of
87 // filter values for each one. Those values will tell us how to blend the
88 // source pixels to compute the destination pixel.
89 for (int dest_subset_i = dest_subset_lo; dest_subset_i < dest_subset_hi;
90 dest_subset_i++) {
91 // Reset the arrays. We don't declare them inside so they can re-use the
92 // same malloc-ed buffer.
93 filter_values->clear();
94 fixed_filter_values->clear();
95
96 // This is the pixel in the source directly under the pixel in the dest.
97 // Note that we base computations on the "center" of the pixels. To see
98 // why, observe that the destination pixel at coordinates (0, 0) in a 5.0x
99 // downscale should "cover" the pixels around the pixel with *its center*
100 // at coordinates (2.5, 2.5) in the source, not those around (0, 0).
101 // Hence we need to scale coordinates (0.5, 0.5), not (0, 0).
102 float src_pixel = (static_cast<float>(dest_subset_i) + 0.5f) * inv_scale;
103
104 // Compute the (inclusive) range of source pixels the filter covers.
105 int src_begin = std::max(0, FloorInt(src_pixel - src_support));
106 int src_end = std::min(src_size - 1, CeilInt(src_pixel + src_support));
107
108 // Compute the unnormalized filter value at each location of the source
109 // it covers.
110 float filter_sum = 0.0f; // Sub of the filter values for normalizing.
111 for (int cur_filter_pixel = src_begin; cur_filter_pixel <= src_end;
112 cur_filter_pixel++) {
113 // Distance from the center of the filter, this is the filter coordinate
114 // in source space. We also need to consider the center of the pixel
115 // when comparing distance against 'src_pixel'. In the 5x downscale
116 // example used above the distance from the center of the filter to
117 // the pixel with coordinates (2, 2) should be 0, because its center
118 // is at (2.5, 2.5).
119 float src_filter_dist =
120 ((static_cast<float>(cur_filter_pixel) + 0.5f) - src_pixel);
121
122 // Since the filter really exists in dest space, map it there.
123 float dest_filter_dist = src_filter_dist * clamped_scale;
124
125 // Compute the filter value at that location.
126 float filter_value = ComputeFilter(method, dest_filter_dist);
127 filter_values->push_back(filter_value);
128
129 filter_sum += filter_value;
130 }
131
132 // The filter must be normalized so that we don't affect the brightness of
133 // the image. Convert to normalized fixed point.
134 int16_t fixed_sum = 0;
135 for (size_t i = 0; i < filter_values->size(); i++) {
136 int16_t cur_fixed = output->FloatToFixed(filter_values[i] / filter_sum);
137 fixed_sum += cur_fixed;
138 fixed_filter_values->push_back(cur_fixed);
139 }
140
141 // The conversion to fixed point will leave some rounding errors, which
142 // we add back in to avoid affecting the brightness of the image. We
143 // arbitrarily add this to the center of the filter array (this won't always
144 // be the center of the filter function since it could get clipped on the
145 // edges, but it doesn't matter enough to worry about that case).
146 int16_t leftovers = output->FloatToFixed(1.0f) - fixed_sum;
147 fixed_filter_values[fixed_filter_values->size() / 2] += leftovers;
148
149 // Now it's ready to go.
150 output->AddFilter(src_begin, &fixed_filter_values[0],
151 static_cast<int>(fixed_filter_values->size()));
152 }
153
154 output->PaddingForSIMD(8);
155 }
156
157 } // namespace resize
158
ResizeMethodToAlgorithmMethod(ImageOperations::ResizeMethod method)159 ImageOperations::ResizeMethod ResizeMethodToAlgorithmMethod(
160 ImageOperations::ResizeMethod method) {
161 // Convert any "Quality Method" into an "Algorithm Method"
162 if (method >= ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD &&
163 method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD) {
164 return method;
165 }
166 // The call to ImageOperationsGtv::Resize() above took care of
167 // GPU-acceleration in the cases where it is possible. So now we just
168 // pick the appropriate software method for each resize quality.
169 switch (method) {
170 // Users of RESIZE_GOOD are willing to trade a lot of quality to
171 // get speed, allowing the use of linear resampling to get hardware
172 // acceleration (SRB). Hence any of our "good" software filters
173 // will be acceptable, and we use the fastest one, Hamming-1.
174 case ImageOperations::RESIZE_GOOD:
175 // Users of RESIZE_BETTER are willing to trade some quality in order
176 // to improve performance, but are guaranteed not to devolve to a linear
177 // resampling. In visual tests we see that Hamming-1 is not as good as
178 // Lanczos-2, however it is about 40% faster and Lanczos-2 itself is
179 // about 30% faster than Lanczos-3. The use of Hamming-1 has been deemed
180 // an acceptable trade-off between quality and speed.
181 case ImageOperations::RESIZE_BETTER:
182 return ImageOperations::RESIZE_HAMMING1;
183 default:
184 return ImageOperations::RESIZE_LANCZOS3;
185 }
186 }
187
188 // Resize ----------------------------------------------------------------------
189
190 // static
Resize(const SkBitmap & source,ResizeMethod method,int dest_width,int dest_height,const SkIRect & dest_subset,void * dest_pixels)191 SkBitmap ImageOperations::Resize(const SkBitmap& source,
192 ResizeMethod method,
193 int dest_width, int dest_height,
194 const SkIRect& dest_subset,
195 void* dest_pixels /* = nullptr */) {
196 if (method == ImageOperations::RESIZE_SUBPIXEL)
197 return ResizeSubpixel(source, dest_width, dest_height, dest_subset);
198 else
199 return ResizeBasic(source, method, dest_width, dest_height, dest_subset,
200 dest_pixels);
201 }
202
203 // static
ResizeSubpixel(const SkBitmap & source,int dest_width,int dest_height,const SkIRect & dest_subset)204 SkBitmap ImageOperations::ResizeSubpixel(const SkBitmap& source,
205 int dest_width, int dest_height,
206 const SkIRect& dest_subset) {
207 // Currently only works on Linux/BSD because these are the only platforms
208 // where SkFontLCDConfig::GetSubpixelOrder is defined.
209 #if defined(XP_UNIX)
210 // Understand the display.
211 const SkFontLCDConfig::LCDOrder order = SkFontLCDConfig::GetSubpixelOrder();
212 const SkFontLCDConfig::LCDOrientation orientation =
213 SkFontLCDConfig::GetSubpixelOrientation();
214
215 // Decide on which dimension, if any, to deploy subpixel rendering.
216 int w = 1;
217 int h = 1;
218 switch (orientation) {
219 case SkFontLCDConfig::kHorizontal_LCDOrientation:
220 w = dest_width < source.width() ? 3 : 1;
221 break;
222 case SkFontLCDConfig::kVertical_LCDOrientation:
223 h = dest_height < source.height() ? 3 : 1;
224 break;
225 }
226
227 // Resize the image.
228 const int width = dest_width * w;
229 const int height = dest_height * h;
230 SkIRect subset = { dest_subset.fLeft, dest_subset.fTop,
231 dest_subset.fLeft + dest_subset.width() * w,
232 dest_subset.fTop + dest_subset.height() * h };
233 SkBitmap img = ResizeBasic(source, ImageOperations::RESIZE_LANCZOS3, width,
234 height, subset);
235 const int row_words = img.rowBytes() / 4;
236 if (w == 1 && h == 1)
237 return img;
238
239 // Render into subpixels.
240 SkBitmap result;
241 SkImageInfo info = SkImageInfo::Make(dest_subset.width(),
242 dest_subset.height(),
243 kBGRA_8888_SkColorType,
244 kPremul_SkAlphaType);
245
246
247 result.allocPixels(info);
248 if (!result.readyToDraw())
249 return img;
250
251 SkAutoLockPixels locker(img);
252 if (!img.readyToDraw())
253 return img;
254
255 uint32_t* src_row = img.getAddr32(0, 0);
256 uint32_t* dst_row = result.getAddr32(0, 0);
257 for (int y = 0; y < dest_subset.height(); y++) {
258 uint32_t* src = src_row;
259 uint32_t* dst = dst_row;
260 for (int x = 0; x < dest_subset.width(); x++, src += w, dst++) {
261 uint8_t r = 0, g = 0, b = 0, a = 0;
262 switch (order) {
263 case SkFontLCDConfig::kRGB_LCDOrder:
264 switch (orientation) {
265 case SkFontLCDConfig::kHorizontal_LCDOrientation:
266 r = SkGetPackedR32(src[0]);
267 g = SkGetPackedG32(src[1]);
268 b = SkGetPackedB32(src[2]);
269 a = SkGetPackedA32(src[1]);
270 break;
271 case SkFontLCDConfig::kVertical_LCDOrientation:
272 r = SkGetPackedR32(src[0 * row_words]);
273 g = SkGetPackedG32(src[1 * row_words]);
274 b = SkGetPackedB32(src[2 * row_words]);
275 a = SkGetPackedA32(src[1 * row_words]);
276 break;
277 }
278 break;
279 case SkFontLCDConfig::kBGR_LCDOrder:
280 switch (orientation) {
281 case SkFontLCDConfig::kHorizontal_LCDOrientation:
282 b = SkGetPackedB32(src[0]);
283 g = SkGetPackedG32(src[1]);
284 r = SkGetPackedR32(src[2]);
285 a = SkGetPackedA32(src[1]);
286 break;
287 case SkFontLCDConfig::kVertical_LCDOrientation:
288 b = SkGetPackedB32(src[0 * row_words]);
289 g = SkGetPackedG32(src[1 * row_words]);
290 r = SkGetPackedR32(src[2 * row_words]);
291 a = SkGetPackedA32(src[1 * row_words]);
292 break;
293 }
294 break;
295 case SkFontLCDConfig::kNONE_LCDOrder:
296 break;
297 }
298 // Premultiplied alpha is very fragile.
299 a = a > r ? a : r;
300 a = a > g ? a : g;
301 a = a > b ? a : b;
302 *dst = SkPackARGB32(a, r, g, b);
303 }
304 src_row += h * row_words;
305 dst_row += result.rowBytes() / 4;
306 }
307 result.setAlphaType(img.alphaType());
308 return result;
309 #else
310 return SkBitmap();
311 #endif // OS_POSIX && !OS_MACOSX && !defined(OS_ANDROID)
312 }
313
314 // static
ResizeBasic(const SkBitmap & source,ResizeMethod method,int dest_width,int dest_height,const SkIRect & dest_subset,void * dest_pixels)315 SkBitmap ImageOperations::ResizeBasic(const SkBitmap& source,
316 ResizeMethod method,
317 int dest_width, int dest_height,
318 const SkIRect& dest_subset,
319 void* dest_pixels /* = nullptr */) {
320 // Ensure that the ResizeMethod enumeration is sound.
321 SkASSERT(((RESIZE_FIRST_QUALITY_METHOD <= method) &&
322 (method <= RESIZE_LAST_QUALITY_METHOD)) ||
323 ((RESIZE_FIRST_ALGORITHM_METHOD <= method) &&
324 (method <= RESIZE_LAST_ALGORITHM_METHOD)));
325
326 // If the size of source or destination is 0, i.e. 0x0, 0xN or Nx0, just
327 // return empty.
328 if (source.width() < 1 || source.height() < 1 ||
329 dest_width < 1 || dest_height < 1)
330 return SkBitmap();
331
332 method = ResizeMethodToAlgorithmMethod(method);
333 // Check that we deal with an "algorithm methods" from this point onward.
334 SkASSERT((ImageOperations::RESIZE_FIRST_ALGORITHM_METHOD <= method) &&
335 (method <= ImageOperations::RESIZE_LAST_ALGORITHM_METHOD));
336
337 SkAutoLockPixels locker(source);
338 if (!source.readyToDraw())
339 return SkBitmap();
340
341 ConvolutionFilter1D x_filter;
342 ConvolutionFilter1D y_filter;
343
344 resize::ComputeFilters(method, source.width(), dest_width, dest_subset.fLeft, dest_subset.width(), &x_filter);
345 resize::ComputeFilters(method, source.height(), dest_height, dest_subset.fTop, dest_subset.height(), &y_filter);
346
347 // Get a source bitmap encompassing this touched area. We construct the
348 // offsets and row strides such that it looks like a new bitmap, while
349 // referring to the old data.
350 const uint8_t* source_subset =
351 reinterpret_cast<const uint8_t*>(source.getPixels());
352
353 // Convolve into the result.
354 SkBitmap result;
355 SkImageInfo info = SkImageInfo::Make(dest_subset.width(),
356 dest_subset.height(),
357 kBGRA_8888_SkColorType,
358 kPremul_SkAlphaType);
359
360 if (dest_pixels) {
361 result.installPixels(info, dest_pixels, info.minRowBytes());
362 } else {
363 result.allocPixels(info);
364 }
365
366 if (!result.readyToDraw())
367 return SkBitmap();
368
369 BGRAConvolve2D(source_subset, static_cast<int>(source.rowBytes()),
370 !source.isOpaque(), x_filter, y_filter,
371 static_cast<int>(result.rowBytes()),
372 static_cast<unsigned char*>(result.getPixels()));
373
374 // Preserve the "opaque" flag for use as an optimization later.
375 result.setAlphaType(source.alphaType());
376
377 return result;
378 }
379
380 // static
Resize(const SkBitmap & source,ResizeMethod method,int dest_width,int dest_height,void * dest_pixels)381 SkBitmap ImageOperations::Resize(const SkBitmap& source,
382 ResizeMethod method,
383 int dest_width, int dest_height,
384 void* dest_pixels /* = nullptr */) {
385 SkIRect dest_subset = { 0, 0, dest_width, dest_height };
386 return Resize(source, method, dest_width, dest_height, dest_subset,
387 dest_pixels);
388 }
389
390 } // namespace skia
391