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