gfx/skia/trunk/src/core/SkConvolver.cpp@97036ab72558
gfx/skia/trunk/src/core/SkConvolver.cpp
Tue, 06 Jan 2015 21:39:09 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Tue, 06 Jan 2015 21:39:09 +0100
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
- permissions
- -rw-r--r--
Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.
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.
5 #include "SkConvolver.h"
6 #include "SkSize.h"
7 #include "SkTypes.h"
9 namespace {
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 }
17 if (a < 0) {
18 return 0;
19 }
20 return 255;
21 }
23 // Stores a list of rows in a circular buffer. The usage is you write into it
24 // by calling AdvanceRow. It will keep track of which row in the buffer it
25 // should use next, and the total number of rows added.
26 class CircularRowBuffer {
27 public:
28 // The number of pixels in each row is given in |sourceRowPixelWidth|.
29 // The maximum number of rows needed in the buffer is |maxYFilterSize|
30 // (we only need to store enough rows for the biggest filter).
31 //
32 // We use the |firstInputRow| to compute the coordinates of all of the
33 // following rows returned by Advance().
34 CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize,
35 int firstInputRow)
36 : fRowByteWidth(destRowPixelWidth * 4),
37 fNumRows(maxYFilterSize),
38 fNextRow(0),
39 fNextRowCoordinate(firstInputRow) {
40 fBuffer.reset(fRowByteWidth * maxYFilterSize);
41 fRowAddresses.reset(fNumRows);
42 }
44 // Moves to the next row in the buffer, returning a pointer to the beginning
45 // of it.
46 unsigned char* advanceRow() {
47 unsigned char* row = &fBuffer[fNextRow * fRowByteWidth];
48 fNextRowCoordinate++;
50 // Set the pointer to the next row to use, wrapping around if necessary.
51 fNextRow++;
52 if (fNextRow == fNumRows) {
53 fNextRow = 0;
54 }
55 return row;
56 }
58 // Returns a pointer to an "unrolled" array of rows. These rows will start
59 // at the y coordinate placed into |*firstRowIndex| and will continue in
60 // order for the maximum number of rows in this circular buffer.
61 //
62 // The |firstRowIndex_| may be negative. This means the circular buffer
63 // starts before the top of the image (it hasn't been filled yet).
64 unsigned char* const* GetRowAddresses(int* firstRowIndex) {
65 // Example for a 4-element circular buffer holding coords 6-9.
66 // Row 0 Coord 8
67 // Row 1 Coord 9
68 // Row 2 Coord 6 <- fNextRow = 2, fNextRowCoordinate = 10.
69 // Row 3 Coord 7
70 //
71 // The "next" row is also the first (lowest) coordinate. This computation
72 // may yield a negative value, but that's OK, the math will work out
73 // since the user of this buffer will compute the offset relative
74 // to the firstRowIndex and the negative rows will never be used.
75 *firstRowIndex = fNextRowCoordinate - fNumRows;
77 int curRow = fNextRow;
78 for (int i = 0; i < fNumRows; i++) {
79 fRowAddresses[i] = &fBuffer[curRow * fRowByteWidth];
81 // Advance to the next row, wrapping if necessary.
82 curRow++;
83 if (curRow == fNumRows) {
84 curRow = 0;
85 }
86 }
87 return &fRowAddresses[0];
88 }
90 private:
91 // The buffer storing the rows. They are packed, each one fRowByteWidth.
92 SkTArray<unsigned char> fBuffer;
94 // Number of bytes per row in the |buffer|.
95 int fRowByteWidth;
97 // The number of rows available in the buffer.
98 int fNumRows;
100 // The next row index we should write into. This wraps around as the
101 // circular buffer is used.
102 int fNextRow;
104 // The y coordinate of the |fNextRow|. This is incremented each time a
105 // new row is appended and does not wrap.
106 int fNextRowCoordinate;
108 // Buffer used by GetRowAddresses().
109 SkTArray<unsigned char*> fRowAddresses;
110 };
112 // Convolves horizontally along a single row. The row data is given in
113 // |srcData| and continues for the numValues() of the filter.
114 template<bool hasAlpha>
115 void ConvolveHorizontally(const unsigned char* srcData,
116 const SkConvolutionFilter1D& filter,
117 unsigned char* outRow) {
118 // Loop over each pixel on this row in the output image.
119 int numValues = filter.numValues();
120 for (int outX = 0; outX < numValues; outX++) {
121 // Get the filter that determines the current output pixel.
122 int filterOffset, filterLength;
123 const SkConvolutionFilter1D::ConvolutionFixed* filterValues =
124 filter.FilterForValue(outX, &filterOffset, &filterLength);
126 // Compute the first pixel in this row that the filter affects. It will
127 // touch |filterLength| pixels (4 bytes each) after this.
128 const unsigned char* rowToFilter = &srcData[filterOffset * 4];
130 // Apply the filter to the row to get the destination pixel in |accum|.
131 int accum[4] = {0};
132 for (int filterX = 0; filterX < filterLength; filterX++) {
133 SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterX];
134 accum[0] += curFilter * rowToFilter[filterX * 4 + 0];
135 accum[1] += curFilter * rowToFilter[filterX * 4 + 1];
136 accum[2] += curFilter * rowToFilter[filterX * 4 + 2];
137 if (hasAlpha) {
138 accum[3] += curFilter * rowToFilter[filterX * 4 + 3];
139 }
140 }
142 // Bring this value back in range. All of the filter scaling factors
143 // are in fixed point with kShiftBits bits of fractional part.
144 accum[0] >>= SkConvolutionFilter1D::kShiftBits;
145 accum[1] >>= SkConvolutionFilter1D::kShiftBits;
146 accum[2] >>= SkConvolutionFilter1D::kShiftBits;
147 if (hasAlpha) {
148 accum[3] >>= SkConvolutionFilter1D::kShiftBits;
149 }
151 // Store the new pixel.
152 outRow[outX * 4 + 0] = ClampTo8(accum[0]);
153 outRow[outX * 4 + 1] = ClampTo8(accum[1]);
154 outRow[outX * 4 + 2] = ClampTo8(accum[2]);
155 if (hasAlpha) {
156 outRow[outX * 4 + 3] = ClampTo8(accum[3]);
157 }
158 }
159 }
161 // Does vertical convolution to produce one output row. The filter values and
162 // length are given in the first two parameters. These are applied to each
163 // of the rows pointed to in the |sourceDataRows| array, with each row
164 // being |pixelWidth| wide.
165 //
166 // The output must have room for |pixelWidth * 4| bytes.
167 template<bool hasAlpha>
168 void ConvolveVertically(const SkConvolutionFilter1D::ConvolutionFixed* filterValues,
169 int filterLength,
170 unsigned char* const* sourceDataRows,
171 int pixelWidth,
172 unsigned char* outRow) {
173 // We go through each column in the output and do a vertical convolution,
174 // generating one output pixel each time.
175 for (int outX = 0; outX < pixelWidth; outX++) {
176 // Compute the number of bytes over in each row that the current column
177 // we're convolving starts at. The pixel will cover the next 4 bytes.
178 int byteOffset = outX * 4;
180 // Apply the filter to one column of pixels.
181 int accum[4] = {0};
182 for (int filterY = 0; filterY < filterLength; filterY++) {
183 SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterY];
184 accum[0] += curFilter * sourceDataRows[filterY][byteOffset + 0];
185 accum[1] += curFilter * sourceDataRows[filterY][byteOffset + 1];
186 accum[2] += curFilter * sourceDataRows[filterY][byteOffset + 2];
187 if (hasAlpha) {
188 accum[3] += curFilter * sourceDataRows[filterY][byteOffset + 3];
189 }
190 }
192 // Bring this value back in range. All of the filter scaling factors
193 // are in fixed point with kShiftBits bits of precision.
194 accum[0] >>= SkConvolutionFilter1D::kShiftBits;
195 accum[1] >>= SkConvolutionFilter1D::kShiftBits;
196 accum[2] >>= SkConvolutionFilter1D::kShiftBits;
197 if (hasAlpha) {
198 accum[3] >>= SkConvolutionFilter1D::kShiftBits;
199 }
201 // Store the new pixel.
202 outRow[byteOffset + 0] = ClampTo8(accum[0]);
203 outRow[byteOffset + 1] = ClampTo8(accum[1]);
204 outRow[byteOffset + 2] = ClampTo8(accum[2]);
205 if (hasAlpha) {
206 unsigned char alpha = ClampTo8(accum[3]);
208 // Make sure the alpha channel doesn't come out smaller than any of the
209 // color channels. We use premultipled alpha channels, so this should
210 // never happen, but rounding errors will cause this from time to time.
211 // These "impossible" colors will cause overflows (and hence random pixel
212 // values) when the resulting bitmap is drawn to the screen.
213 //
214 // We only need to do this when generating the final output row (here).
215 int maxColorChannel = SkTMax(outRow[byteOffset + 0],
216 SkTMax(outRow[byteOffset + 1],
217 outRow[byteOffset + 2]));
218 if (alpha < maxColorChannel) {
219 outRow[byteOffset + 3] = maxColorChannel;
220 } else {
221 outRow[byteOffset + 3] = alpha;
222 }
223 } else {
224 // No alpha channel, the image is opaque.
225 outRow[byteOffset + 3] = 0xff;
226 }
227 }
228 }
230 void ConvolveVertically(const SkConvolutionFilter1D::ConvolutionFixed* filterValues,
231 int filterLength,
232 unsigned char* const* sourceDataRows,
233 int pixelWidth,
234 unsigned char* outRow,
235 bool sourceHasAlpha) {
236 if (sourceHasAlpha) {
237 ConvolveVertically<true>(filterValues, filterLength,
238 sourceDataRows, pixelWidth,
239 outRow);
240 } else {
241 ConvolveVertically<false>(filterValues, filterLength,
242 sourceDataRows, pixelWidth,
243 outRow);
244 }
245 }
247 } // namespace
249 // SkConvolutionFilter1D ---------------------------------------------------------
251 SkConvolutionFilter1D::SkConvolutionFilter1D()
252 : fMaxFilter(0) {
253 }
255 SkConvolutionFilter1D::~SkConvolutionFilter1D() {
256 }
258 void SkConvolutionFilter1D::AddFilter(int filterOffset,
259 const float* filterValues,
260 int filterLength) {
261 SkASSERT(filterLength > 0);
263 SkTArray<ConvolutionFixed> fixedValues;
264 fixedValues.reset(filterLength);
266 for (int i = 0; i < filterLength; ++i) {
267 fixedValues.push_back(FloatToFixed(filterValues[i]));
268 }
270 AddFilter(filterOffset, &fixedValues[0], filterLength);
271 }
273 void SkConvolutionFilter1D::AddFilter(int filterOffset,
274 const ConvolutionFixed* filterValues,
275 int filterLength) {
276 // It is common for leading/trailing filter values to be zeros. In such
277 // cases it is beneficial to only store the central factors.
278 // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on
279 // a 1080p image this optimization gives a ~10% speed improvement.
280 int filterSize = filterLength;
281 int firstNonZero = 0;
282 while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) {
283 firstNonZero++;
284 }
286 if (firstNonZero < filterLength) {
287 // Here we have at least one non-zero factor.
288 int lastNonZero = filterLength - 1;
289 while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) {
290 lastNonZero--;
291 }
293 filterOffset += firstNonZero;
294 filterLength = lastNonZero + 1 - firstNonZero;
295 SkASSERT(filterLength > 0);
297 for (int i = firstNonZero; i <= lastNonZero; i++) {
298 fFilterValues.push_back(filterValues[i]);
299 }
300 } else {
301 // Here all the factors were zeroes.
302 filterLength = 0;
303 }
305 FilterInstance instance;
307 // We pushed filterLength elements onto fFilterValues
308 instance.fDataLocation = (static_cast<int>(fFilterValues.count()) -
309 filterLength);
310 instance.fOffset = filterOffset;
311 instance.fTrimmedLength = filterLength;
312 instance.fLength = filterSize;
313 fFilters.push_back(instance);
315 fMaxFilter = SkTMax(fMaxFilter, filterLength);
316 }
318 const SkConvolutionFilter1D::ConvolutionFixed* SkConvolutionFilter1D::GetSingleFilter(
319 int* specifiedFilterlength,
320 int* filterOffset,
321 int* filterLength) const {
322 const FilterInstance& filter = fFilters[0];
323 *filterOffset = filter.fOffset;
324 *filterLength = filter.fTrimmedLength;
325 *specifiedFilterlength = filter.fLength;
326 if (filter.fTrimmedLength == 0) {
327 return NULL;
328 }
330 return &fFilterValues[filter.fDataLocation];
331 }
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 const SkConvolutionProcs& convolveProcs,
341 bool useSimdIfPossible) {
343 int maxYFilterSize = filterY.maxFilter();
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::ConvolutionFixed* filterValues =
352 filterY.FilterForValue(0, &filterOffset, &filterLength);
353 int nextXRow = filterOffset;
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 done
361 // simultaneously. We also pad each row in row buffer to be aligned-up to
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);
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();
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;
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);
393 filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset,
394 &lastFilterLength);
396 for (int outY = 0; outY < numOutputRows; outY++) {
397 filterValues = filterY.FilterForValue(outY,
398 &filterOffset, &filterLength);
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 }
436 // Compute where in the output image this row of final data will go.
437 unsigned char* curOutputRow = &output[outY * outputByteRowStride];
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);
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];
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 }
