OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2011 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 "SkConvolver.h" | |
6 #include "SkSize.h" | |
7 #include "SkTypes.h" | |
8 | |
9 namespace { | |
10 | |
11 // Converts the argument to an 8-bit unsigned value by clamping to the range | |
12 // 0-255. | |
13 inline unsigned char ClampTo8(int a) { | |
14 if (static_cast<unsigned>(a) < 256) | |
15 return a; // Avoid the extra check in the common case. | |
16 if (a < 0) | |
17 return 0; | |
18 return 255; | |
19 } | |
20 | |
21 // Takes the value produced by accumulating element-wise product of image wi th | |
22 // a kernel and brings it back into range. | |
23 // All of the filter scaling factors are in fixed point with kShiftBits bits of | |
24 // fractional part. | |
25 inline unsigned char BringBackTo8(int a, bool takeAbsolute) { | |
26 a >>= SkConvolutionFilter1D::kShiftBits; | |
27 if (takeAbsolute) | |
reed1
2013/07/19 17:47:23
nit: if-blocks should always have {}
| |
28 a = abs(a); | |
29 return ClampTo8(a); | |
30 } | |
31 | |
32 // Stores a list of rows in a circular buffer. The usage is you write into i t | |
33 // by calling AdvanceRow. It will keep track of which row in the buffer it | |
34 // should use next, and the total number of rows added. | |
35 class CircularRowBuffer { | |
36 public: | |
37 // The number of pixels in each row is given in |source_row_pixel_widt h|. | |
38 // The maximum number of rows needed in the buffer is |max_y_filter_si ze| | |
39 // (we only need to store enough rows for the biggest filter). | |
40 // | |
41 // We use the |first_input_row| to compute the coordinates of all of t he | |
42 // following rows returned by Advance(). | |
43 CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize, | |
44 int firstInputRow) | |
45 : fRowByteWidth(destRowPixelWidth * 4), | |
46 fNumRows(maxYFilterSize), | |
47 fNextRow(0), | |
48 fNextRowCoordinate(firstInputRow) { | |
49 fBuffer.reset(fRowByteWidth * maxYFilterSize); | |
50 fRowAddresses.reset(fNumRows); | |
51 } | |
52 | |
53 // Moves to the next row in the buffer, returning a pointer to the begin ning | |
54 // of it. | |
55 unsigned char* advanceRow() { | |
56 unsigned char* row = &fBuffer[fNextRow * fRowByteWidth]; | |
57 fNextRowCoordinate++; | |
58 | |
59 // Set the pointer to the next row to use, wrapping around if necess ary. | |
60 fNextRow++; | |
61 if (fNextRow == fNumRows) | |
62 fNextRow = 0; | |
63 return row; | |
64 } | |
65 | |
66 // Returns a pointer to an "unrolled" array of rows. These rows will sta rt | |
67 // at the y coordinate placed into |*first_row_index| and will continue in | |
68 // order for the maximum number of rows in this circular buffer. | |
69 // | |
70 // The |first_row_index_| may be negative. This means the circular buffe r | |
71 // starts before the top of the image (it hasn't been filled yet). | |
72 unsigned char* const* GetRowAddresses(int* firstRowIndex) { | |
73 // Example for a 4-element circular buffer holding coords 6-9. | |
74 // Row 0 Coord 8 | |
75 // Row 1 Coord 9 | |
76 // Row 2 Coord 6 <- fNextRow = 2, fNextRowCoordinate = 10. | |
77 // Row 3 Coord 7 | |
78 // | |
79 // The "next" row is also the first (lowest) coordinate. This comput ation | |
80 // may yield a negative value, but that's OK, the math will work out | |
81 // since the user of this buffer will compute the offset relative | |
82 // to the firstRowIndex and the negative rows will never be used. | |
83 *firstRowIndex = fNextRowCoordinate - fNumRows; | |
84 | |
85 int cur_row = fNextRow; | |
86 for (int i = 0; i < fNumRows; i++) { | |
87 fRowAddresses[i] = &fBuffer[cur_row * fRowByteWidth]; | |
88 | |
89 // Advance to the next row, wrapping if necessary. | |
90 cur_row++; | |
91 if (cur_row == fNumRows) | |
92 cur_row = 0; | |
93 } | |
94 return &fRowAddresses[0]; | |
95 } | |
96 | |
97 private: | |
98 // The buffer storing the rows. They are packed, each one fRowByteWidth. | |
99 SkTArray<unsigned char> fBuffer; | |
100 | |
101 // Number of bytes per row in the |buffer_|. | |
102 int fRowByteWidth; | |
103 | |
104 // The number of rows available in the buffer. | |
105 int fNumRows; | |
106 | |
107 // The next row index we should write into. This wraps around as the | |
108 // circular buffer is used. | |
109 int fNextRow; | |
110 | |
111 // The y coordinate of the |fNextRow|. This is incremented each time a | |
112 // new row is appended and does not wrap. | |
113 int fNextRowCoordinate; | |
114 | |
115 // Buffer used by GetRowAddresses(). | |
116 SkTArray<unsigned char*> fRowAddresses; | |
117 }; | |
118 | |
119 // Convolves horizontally along a single row. The row data is given in | |
120 // |src_data| and continues for the numValues() of the filter. | |
121 template<bool has_alpha> | |
122 void ConvolveHorizontally(const unsigned char* src_data, | |
123 const SkConvolutionFilter1D& filter, | |
124 unsigned char* out_row) { | |
125 // Loop over each pixel on this row in the output image. | |
126 int numValues = filter.numValues(); | |
127 for (int out_x = 0; out_x < numValues; out_x++) { | |
128 // Get the filter that determines the current output pixel. | |
129 int filterOffset, filterLength; | |
130 const SkConvolutionFilter1D::Fixed* filterValues = | |
131 filter.FilterForValue(out_x, &filterOffset, &filterLength); | |
132 | |
133 // Compute the first pixel in this row that the filter affects. It will | |
134 // touch |filterLength| pixels (4 bytes each) after this. | |
135 const unsigned char* row_to_filter = &src_data[filterOffset * 4]; | |
136 | |
137 // Apply the filter to the row to get the destination pixel in |accum|. | |
138 int accum[4] = {0}; | |
139 for (int filter_x = 0; filter_x < filterLength; filter_x++) { | |
140 SkConvolutionFilter1D::Fixed cur_filter = filterValues[filter_x] ; | |
141 accum[0] += cur_filter * row_to_filter[filter_x * 4 + 0]; | |
142 accum[1] += cur_filter * row_to_filter[filter_x * 4 + 1]; | |
143 accum[2] += cur_filter * row_to_filter[filter_x * 4 + 2]; | |
144 if (has_alpha) | |
145 accum[3] += cur_filter * row_to_filter[filter_x * 4 + 3]; | |
146 } | |
147 | |
148 // Bring this value back in range. All of the filter scaling factors | |
149 // are in fixed point with kShiftBits bits of fractional part. | |
150 accum[0] >>= SkConvolutionFilter1D::kShiftBits; | |
151 accum[1] >>= SkConvolutionFilter1D::kShiftBits; | |
152 accum[2] >>= SkConvolutionFilter1D::kShiftBits; | |
153 if (has_alpha) | |
154 accum[3] >>= SkConvolutionFilter1D::kShiftBits; | |
155 | |
156 // Store the new pixel. | |
157 out_row[out_x * 4 + 0] = ClampTo8(accum[0]); | |
158 out_row[out_x * 4 + 1] = ClampTo8(accum[1]); | |
159 out_row[out_x * 4 + 2] = ClampTo8(accum[2]); | |
160 if (has_alpha) | |
161 out_row[out_x * 4 + 3] = ClampTo8(accum[3]); | |
162 } | |
163 } | |
164 | |
165 // Does vertical convolution to produce one output row. The filter values and | |
166 // length are given in the first two parameters. These are applied to each | |
167 // of the rows pointed to in the |source_data_rows| array, with each row | |
168 // being |pixel_width| wide. | |
169 // | |
170 // The output must have room for |pixel_width * 4| bytes. | |
171 template<bool has_alpha> | |
172 void ConvolveVertically(const SkConvolutionFilter1D::Fixed* filterValues, | |
173 int filterLength, | |
174 unsigned char* const* source_data_rows, | |
175 int pixel_width, | |
176 unsigned char* out_row) { | |
177 // We go through each column in the output and do a vertical convolution, | |
178 // generating one output pixel each time. | |
179 for (int out_x = 0; out_x < pixel_width; out_x++) { | |
180 // Compute the number of bytes over in each row that the current column | |
181 // we're convolving starts at. The pixel will cover the next 4 bytes. | |
182 int byte_offset = out_x * 4; | |
183 | |
184 // Apply the filter to one column of pixels. | |
185 int accum[4] = {0}; | |
186 for (int filter_y = 0; filter_y < filterLength; filter_y++) { | |
187 SkConvolutionFilter1D::Fixed cur_filter = filterValues[filter_y] ; | |
188 accum[0] += cur_filter * source_data_rows[filter_y][byte_offset + 0]; | |
189 accum[1] += cur_filter * source_data_rows[filter_y][byte_offset + 1]; | |
190 accum[2] += cur_filter * source_data_rows[filter_y][byte_offset + 2]; | |
191 if (has_alpha) | |
192 accum[3] += cur_filter * source_data_rows[filter_y][byte_off set + 3]; | |
193 } | |
194 | |
195 // Bring this value back in range. All of the filter scaling factors | |
196 // are in fixed point with kShiftBits bits of precision. | |
197 accum[0] >>= SkConvolutionFilter1D::kShiftBits; | |
198 accum[1] >>= SkConvolutionFilter1D::kShiftBits; | |
199 accum[2] >>= SkConvolutionFilter1D::kShiftBits; | |
200 if (has_alpha) | |
201 accum[3] >>= SkConvolutionFilter1D::kShiftBits; | |
202 | |
203 // Store the new pixel. | |
204 out_row[byte_offset + 0] = ClampTo8(accum[0]); | |
205 out_row[byte_offset + 1] = ClampTo8(accum[1]); | |
206 out_row[byte_offset + 2] = ClampTo8(accum[2]); | |
207 if (has_alpha) { | |
208 unsigned char alpha = ClampTo8(accum[3]); | |
209 | |
210 // Make sure the alpha channel doesn't come out smaller than any of the | |
211 // color channels. We use premultipled alpha channels, so this should | |
212 // never happen, but rounding errors will cause this from time to time. | |
213 // These "impossible" colors will cause overflows (and hence random pixel | |
214 // values) when the resulting bitmap is drawn to the screen. | |
215 // | |
216 // We only need to do this when generating the final output row (here). | |
217 int max_color_channel = SkTMax(out_row[byte_offset + 0], | |
218 SkTMax(out_row[byte_offset + 1], out_row[byte_offset + 2])); | |
219 if (alpha < max_color_channel) | |
220 out_row[byte_offset + 3] = max_color_channel; | |
221 else | |
222 out_row[byte_offset + 3] = alpha; | |
223 } else { | |
224 // No alpha channel, the image is opaque. | |
225 out_row[byte_offset + 3] = 0xff; | |
226 } | |
227 } | |
228 } | |
229 | |
230 void ConvolveVertically(const SkConvolutionFilter1D::Fixed* filterValues, | |
231 int filterLength, | |
232 unsigned char* const* source_data_rows, | |
233 int pixel_width, | |
234 unsigned char* out_row, | |
235 bool source_has_alpha) { | |
236 if (source_has_alpha) { | |
237 ConvolveVertically<true>(filterValues, filterLength, | |
238 source_data_rows, | |
239 pixel_width, | |
240 out_row); | |
241 } else { | |
242 ConvolveVertically<false>(filterValues, filterLength, | |
243 source_data_rows, | |
244 pixel_width, | |
245 out_row); | |
246 } | |
247 } | |
248 | |
249 } // namespace | |
250 | |
251 // SkConvolutionFilter1D ------------------------------------------------------- -- | |
252 | |
253 SkConvolutionFilter1D::SkConvolutionFilter1D() | |
254 : fMaxFilter(0) { | |
255 } | |
256 | |
257 SkConvolutionFilter1D::~SkConvolutionFilter1D() { | |
258 } | |
259 | |
260 void SkConvolutionFilter1D::AddFilter(int filterOffset, | |
261 const float* filterValues, | |
262 int filterLength) { | |
263 SkASSERT(filterLength > 0); | |
264 | |
265 SkTArray<Fixed> fixed_values; | |
266 fixed_values.reset(filterLength); | |
267 | |
268 for (int i = 0; i < filterLength; ++i) | |
269 fixed_values.push_back(FloatToFixed(filterValues[i])); | |
270 | |
271 AddFilter(filterOffset, &fixed_values[0], filterLength); | |
272 } | |
273 | |
274 void SkConvolutionFilter1D::AddFilter(int filterOffset, | |
275 const Fixed* filterValues, | |
276 int filterLength) { | |
277 // It is common for leading/trailing filter values to be zeros. In such | |
278 // cases it is beneficial to only store the central factors. | |
279 // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on | |
280 // a 1080p image this optimization gives a ~10% speed improvement. | |
281 int filter_size = filterLength; | |
282 int first_non_zero = 0; | |
283 while (first_non_zero < filterLength && filterValues[first_non_zero] == 0) | |
284 first_non_zero++; | |
285 | |
286 if (first_non_zero < filterLength) { | |
287 // Here we have at least one non-zero factor. | |
288 int last_non_zero = filterLength - 1; | |
289 while (last_non_zero >= 0 && filterValues[last_non_zero] == 0) | |
290 last_non_zero--; | |
291 | |
292 filterOffset += first_non_zero; | |
293 filterLength = last_non_zero + 1 - first_non_zero; | |
294 SkASSERT(filterLength > 0); | |
295 | |
296 for (int i = first_non_zero; i <= last_non_zero; i++) | |
297 fFilterValues.push_back(filterValues[i]); | |
298 } else { | |
299 // Here all the factors were zeroes. | |
300 filterLength = 0; | |
301 } | |
302 | |
303 FilterInstance instance; | |
304 | |
305 // We pushed filterLength elements onto fFilterValues | |
306 instance.fDataLocation = (static_cast<int>(fFilterValues.count()) - | |
307 filterLength); | |
308 instance.fOffset = filterOffset; | |
309 instance.fTrimmedLength = filterLength; | |
310 instance.fLength = filter_size; | |
311 fFilters.push_back(instance); | |
312 | |
313 fMaxFilter = SkTMax(fMaxFilter, filterLength); | |
314 } | |
315 | |
316 const SkConvolutionFilter1D::Fixed* SkConvolutionFilter1D::GetSingleFilter( | |
317 int* specified_filterLength, | |
318 int* filterOffset, | |
319 int* filterLength) const { | |
320 const FilterInstance& filter = fFilters[0]; | |
321 *filterOffset = filter.fOffset; | |
322 *filterLength = filter.fTrimmedLength; | |
323 *specified_filterLength = filter.fLength; | |
324 if (filter.fTrimmedLength == 0) { | |
325 return NULL; | |
326 } | |
327 | |
328 return &fFilterValues[filter.fDataLocation]; | |
329 } | |
330 | |
331 void BGRAConvolve2D(const unsigned char* sourceData, | |
332 int sourceByteRowStride, | |
333 bool sourceHasAlpha, | |
334 const SkConvolutionFilter1D& filterX, | |
335 const SkConvolutionFilter1D& filterY, | |
336 int outputByteRowStride, | |
337 unsigned char* output, | |
338 SkConvolutionProcs *convolveProcs, | |
339 bool useSimdIfPossible) { | |
340 | |
341 int maxYFilterSize = filterY.maxFilter(); | |
342 | |
343 // The next row in the input that we will generate a horizontally | |
344 // convolved row for. If the filter doesn't start at the beginning of the | |
345 // image (this is the case when we are only resizing a subset), then we | |
346 // don't want to generate any output rows before that. Compute the starting | |
347 // row for convolution as the first pixel for the first vertical filter. | |
348 int filterOffset, filterLength; | |
349 const SkConvolutionFilter1D::Fixed* filterValues = | |
350 filterY.FilterForValue(0, &filterOffset, &filterLength); | |
351 int nextXRow = filterOffset; | |
352 | |
353 // We loop over each row in the input doing a horizontal convolution. This | |
354 // will result in a horizontally convolved image. We write the results into | |
355 // a circular buffer of convolved rows and do vertical convolution as rows | |
356 // are available. This prevents us from having to store the entire | |
357 // intermediate image and helps cache coherency. | |
358 // We will need four extra rows to allow horizontal convolution could be don e | |
359 // simultaneously. We also pad each row in row buffer to be aligned-up to | |
360 // 16 bytes. | |
361 // TODO(jiesun): We do not use aligned load from row buffer in vertical | |
362 // convolution pass yet. Somehow Windows does not like it. | |
363 int rowBufferWidth = (filterX.numValues() + 15) & ~0xF; | |
364 int rowBufferHeight = maxYFilterSize + | |
365 (convolveProcs->fConvolve4RowsHorizontally ? 4 : 0); | |
366 CircularRowBuffer rowBuffer(rowBufferWidth, | |
367 rowBufferHeight, | |
368 filterOffset); | |
369 | |
370 // Loop over every possible output row, processing just enough horizontal | |
371 // convolutions to run each subsequent vertical convolution. | |
372 SkASSERT(outputByteRowStride >= filterX.numValues() * 4); | |
373 int numOutputRows = filterY.numValues(); | |
374 | |
375 // We need to check which is the last line to convolve before we advance 4 | |
376 // lines in one iteration. | |
377 int lastFilterOffset, lastFilterLength; | |
378 | |
379 // SSE2 can access up to 3 extra pixels past the end of the | |
380 // buffer. At the bottom of the image, we have to be careful | |
381 // not to access data past the end of the buffer. Normally | |
382 // we fall back to the C++ implementation for the last row. | |
383 // If the last row is less than 3 pixels wide, we may have to fall | |
384 // back to the C++ version for more rows. Compute how many | |
385 // rows we need to avoid the SSE implementation for here. | |
386 filterX.FilterForValue(filterX.numValues() - 1, &lastFilterOffset, | |
387 &lastFilterLength); | |
388 int avoidSimdRows = 1 + convolveProcs->fExtraHorizontalReads / | |
389 (lastFilterOffset + lastFilterLength); | |
390 | |
391 filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset, | |
392 &lastFilterLength); | |
393 | |
394 for (int outY = 0; outY < numOutputRows; outY++) { | |
395 filterValues = filterY.FilterForValue(outY, | |
396 &filterOffset, &filterLength); | |
397 | |
398 // Generate output rows until we have enough to run the current filter. | |
399 while (nextXRow < filterOffset + filterLength) { | |
400 if (convolveProcs->fConvolve4RowsHorizontally && | |
401 nextXRow + 3 < lastFilterOffset + lastFilterLength - | |
402 avoidSimdRows) { | |
403 const unsigned char* src[4]; | |
404 unsigned char* outRow[4]; | |
405 for (int i = 0; i < 4; ++i) { | |
406 src[i] = &sourceData[(nextXRow + i) * sourceByteRowStride]; | |
407 outRow[i] = rowBuffer.advanceRow(); | |
408 } | |
409 convolveProcs->fConvolve4RowsHorizontally(src, filterX, outRow); | |
410 nextXRow += 4; | |
411 } else { | |
412 // Check if we need to avoid SSE2 for this row. | |
413 if (convolveProcs->fConvolveHorizontally && | |
414 nextXRow < lastFilterOffset + lastFilterLength - | |
415 avoidSimdRows) { | |
416 convolveProcs->fConvolveHorizontally( | |
417 &sourceData[nextXRow * sourceByteRowStride], | |
418 filterX, rowBuffer.advanceRow(), sourceHasAlpha); | |
419 } else { | |
420 if (sourceHasAlpha) { | |
421 ConvolveHorizontally<true>( | |
422 &sourceData[nextXRow * sourceByteRowStride], | |
423 filterX, rowBuffer.advanceRow()); | |
424 } else { | |
425 ConvolveHorizontally<false>( | |
426 &sourceData[nextXRow * sourceByteRowStride], | |
427 filterX, rowBuffer.advanceRow()); | |
428 } | |
429 } | |
430 nextXRow++; | |
431 } | |
432 } | |
433 | |
434 // Compute where in the output image this row of final data will go. | |
435 unsigned char* curOutputRow = &output[outY * outputByteRowStride]; | |
436 | |
437 // Get the list of rows that the circular buffer has, in order. | |
438 int firstRowInCircularBuffer; | |
439 unsigned char* const* rowsToConvolve = | |
440 rowBuffer.GetRowAddresses(&firstRowInCircularBuffer); | |
441 | |
442 // Now compute the start of the subset of those rows that the filter | |
443 // needs. | |
444 unsigned char* const* firstRowForFilter = | |
445 &rowsToConvolve[filterOffset - firstRowInCircularBuffer]; | |
446 | |
447 if (convolveProcs->fConvolveVertically) { | |
448 convolveProcs->fConvolveVertically(filterValues, filterLength, | |
449 firstRowForFilter, | |
450 filterX.numValues(), curOutputRow, | |
451 sourceHasAlpha); | |
452 } else { | |
453 ConvolveVertically(filterValues, filterLength, | |
454 firstRowForFilter, | |
455 filterX.numValues(), curOutputRow, | |
456 sourceHasAlpha); | |
457 } | |
458 } | |
459 } | |
OLD | NEW |