Index: src/core/SkConvolver.cpp |
diff --git a/src/core/SkConvolver.cpp b/src/core/SkConvolver.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..299d872b32adc7bf5aa8b3c3cf613294adc0021e |
--- /dev/null |
+++ b/src/core/SkConvolver.cpp |
@@ -0,0 +1,461 @@ |
+// Copyright (c) 2011 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#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.
|
+ |
+#include "SkConvolver.h" |
+#include "SkSize.h" |
+#include "SkTypes.h" |
+ |
+namespace { |
+ |
+ // Converts the argument to an 8-bit unsigned value by clamping to the range |
+ // 0-255. |
+ inline unsigned char ClampTo8(int a) { |
+ if (static_cast<unsigned>(a) < 256) |
+ return a; // Avoid the extra check in the common case. |
+ if (a < 0) |
+ return 0; |
+ return 255; |
+ } |
+ |
+ // Takes the value produced by accumulating element-wise product of image with |
+ // a kernel and brings it back into range. |
+ // All of the filter scaling factors are in fixed point with kShiftBits bits of |
+ // fractional part. |
+ inline unsigned char BringBackTo8(int a, bool takeAbsolute) { |
+ a >>= SkConvolutionFilter1D::kShiftBits; |
+ if (takeAbsolute) |
+ a = std::abs(a); |
+ return ClampTo8(a); |
+ } |
+ |
+ // Stores a list of rows in a circular buffer. The usage is you write into it |
+ // by calling AdvanceRow. It will keep track of which row in the buffer it |
+ // should use next, and the total number of rows added. |
+ class CircularRowBuffer { |
+ public: |
+ // The number of pixels in each row is given in |source_row_pixel_width|. |
+ // The maximum number of rows needed in the buffer is |max_y_filter_size| |
+ // (we only need to store enough rows for the biggest filter). |
+ // |
+ // We use the |first_input_row| to compute the coordinates of all of the |
+ // following rows returned by Advance(). |
+ CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize, |
+ int firstInputRow) |
+ : fRowByteWidth(destRowPixelWidth * 4), |
+ fNumRows(maxYFilterSize), |
+ fNextRow(0), |
+ fNextRowCoordinate(firstInputRow) { |
+ fBuffer.resize(fRowByteWidth * maxYFilterSize); |
+ fRowAddresses.resize(fNumRows); |
+ } |
+ |
+ // Moves to the next row in the buffer, returning a pointer to the beginning |
+ // of it. |
+ unsigned char* advanceRow() { |
+ unsigned char* row = &fBuffer[fNextRow * fRowByteWidth]; |
+ fNextRowCoordinate++; |
+ |
+ // Set the pointer to the next row to use, wrapping around if necessary. |
+ fNextRow++; |
+ if (fNextRow == fNumRows) |
+ fNextRow = 0; |
+ return row; |
+ } |
+ |
+ // Returns a pointer to an "unrolled" array of rows. These rows will start |
+ // at the y coordinate placed into |*first_row_index| and will continue in |
+ // order for the maximum number of rows in this circular buffer. |
+ // |
+ // The |first_row_index_| may be negative. This means the circular buffer |
+ // starts before the top of the image (it hasn't been filled yet). |
+ unsigned char* const* GetRowAddresses(int* firstRowIndex) { |
+ // Example for a 4-element circular buffer holding coords 6-9. |
+ // Row 0 Coord 8 |
+ // Row 1 Coord 9 |
+ // Row 2 Coord 6 <- fNextRow = 2, fNextRowCoordinate = 10. |
+ // Row 3 Coord 7 |
+ // |
+ // The "next" row is also the first (lowest) coordinate. This computation |
+ // may yield a negative value, but that's OK, the math will work out |
+ // since the user of this buffer will compute the offset relative |
+ // to the firstRowIndex and the negative rows will never be used. |
+ *firstRowIndex = fNextRowCoordinate - fNumRows; |
+ |
+ int cur_row = fNextRow; |
+ for (int i = 0; i < fNumRows; i++) { |
+ fRowAddresses[i] = &fBuffer[cur_row * fRowByteWidth]; |
+ |
+ // Advance to the next row, wrapping if necessary. |
+ cur_row++; |
+ if (cur_row == fNumRows) |
+ cur_row = 0; |
+ } |
+ return &fRowAddresses[0]; |
+ } |
+ |
+ private: |
+ // The buffer storing the rows. They are packed, each one fRowByteWidth. |
+ std::vector<unsigned char> fBuffer; |
+ |
+ // Number of bytes per row in the |buffer_|. |
+ int fRowByteWidth; |
+ |
+ // The number of rows available in the buffer. |
+ int fNumRows; |
+ |
+ // The next row index we should write into. This wraps around as the |
+ // circular buffer is used. |
+ int fNextRow; |
+ |
+ // The y coordinate of the |fNextRow|. This is incremented each time a |
+ // new row is appended and does not wrap. |
+ int fNextRowCoordinate; |
+ |
+ // Buffer used by GetRowAddresses(). |
+ std::vector<unsigned char*> fRowAddresses; |
+ }; |
+ |
+// Convolves horizontally along a single row. The row data is given in |
+// |src_data| and continues for the numValues() of the filter. |
+template<bool has_alpha> |
+ void ConvolveHorizontally(const unsigned char* src_data, |
+ const SkConvolutionFilter1D& filter, |
+ unsigned char* out_row) { |
+ // Loop over each pixel on this row in the output image. |
+ int numValues = filter.numValues(); |
+ for (int out_x = 0; out_x < numValues; out_x++) { |
+ // Get the filter that determines the current output pixel. |
+ int filterOffset, filterLength; |
+ const SkConvolutionFilter1D::Fixed* filterValues = |
+ filter.FilterForValue(out_x, &filterOffset, &filterLength); |
+ |
+ // Compute the first pixel in this row that the filter affects. It will |
+ // touch |filterLength| pixels (4 bytes each) after this. |
+ const unsigned char* row_to_filter = &src_data[filterOffset * 4]; |
+ |
+ // Apply the filter to the row to get the destination pixel in |accum|. |
+ int accum[4] = {0}; |
+ for (int filter_x = 0; filter_x < filterLength; filter_x++) { |
+ SkConvolutionFilter1D::Fixed cur_filter = filterValues[filter_x]; |
+ accum[0] += cur_filter * row_to_filter[filter_x * 4 + 0]; |
+ accum[1] += cur_filter * row_to_filter[filter_x * 4 + 1]; |
+ accum[2] += cur_filter * row_to_filter[filter_x * 4 + 2]; |
+ if (has_alpha) |
+ accum[3] += cur_filter * row_to_filter[filter_x * 4 + 3]; |
+ } |
+ |
+ // Bring this value back in range. All of the filter scaling factors |
+ // are in fixed point with kShiftBits bits of fractional part. |
+ accum[0] >>= SkConvolutionFilter1D::kShiftBits; |
+ accum[1] >>= SkConvolutionFilter1D::kShiftBits; |
+ accum[2] >>= SkConvolutionFilter1D::kShiftBits; |
+ if (has_alpha) |
+ accum[3] >>= SkConvolutionFilter1D::kShiftBits; |
+ |
+ // Store the new pixel. |
+ out_row[out_x * 4 + 0] = ClampTo8(accum[0]); |
+ out_row[out_x * 4 + 1] = ClampTo8(accum[1]); |
+ out_row[out_x * 4 + 2] = ClampTo8(accum[2]); |
+ if (has_alpha) |
+ out_row[out_x * 4 + 3] = ClampTo8(accum[3]); |
+ } |
+ } |
+ |
+// Does vertical convolution to produce one output row. The filter values and |
+// length are given in the first two parameters. These are applied to each |
+// of the rows pointed to in the |source_data_rows| array, with each row |
+// being |pixel_width| wide. |
+// |
+// The output must have room for |pixel_width * 4| bytes. |
+template<bool has_alpha> |
+ void ConvolveVertically(const SkConvolutionFilter1D::Fixed* filterValues, |
+ int filterLength, |
+ unsigned char* const* source_data_rows, |
+ int pixel_width, |
+ unsigned char* out_row) { |
+ // We go through each column in the output and do a vertical convolution, |
+ // generating one output pixel each time. |
+ for (int out_x = 0; out_x < pixel_width; out_x++) { |
+ // Compute the number of bytes over in each row that the current column |
+ // we're convolving starts at. The pixel will cover the next 4 bytes. |
+ int byte_offset = out_x * 4; |
+ |
+ // Apply the filter to one column of pixels. |
+ int accum[4] = {0}; |
+ for (int filter_y = 0; filter_y < filterLength; filter_y++) { |
+ SkConvolutionFilter1D::Fixed cur_filter = filterValues[filter_y]; |
+ accum[0] += cur_filter * source_data_rows[filter_y][byte_offset + 0]; |
+ accum[1] += cur_filter * source_data_rows[filter_y][byte_offset + 1]; |
+ accum[2] += cur_filter * source_data_rows[filter_y][byte_offset + 2]; |
+ if (has_alpha) |
+ accum[3] += cur_filter * source_data_rows[filter_y][byte_offset + 3]; |
+ } |
+ |
+ // Bring this value back in range. All of the filter scaling factors |
+ // are in fixed point with kShiftBits bits of precision. |
+ accum[0] >>= SkConvolutionFilter1D::kShiftBits; |
+ accum[1] >>= SkConvolutionFilter1D::kShiftBits; |
+ accum[2] >>= SkConvolutionFilter1D::kShiftBits; |
+ if (has_alpha) |
+ accum[3] >>= SkConvolutionFilter1D::kShiftBits; |
+ |
+ // Store the new pixel. |
+ out_row[byte_offset + 0] = ClampTo8(accum[0]); |
+ out_row[byte_offset + 1] = ClampTo8(accum[1]); |
+ out_row[byte_offset + 2] = ClampTo8(accum[2]); |
+ if (has_alpha) { |
+ unsigned char alpha = ClampTo8(accum[3]); |
+ |
+ // Make sure the alpha channel doesn't come out smaller than any of the |
+ // color channels. We use premultipled alpha channels, so this should |
+ // never happen, but rounding errors will cause this from time to time. |
+ // These "impossible" colors will cause overflows (and hence random pixel |
+ // values) when the resulting bitmap is drawn to the screen. |
+ // |
+ // We only need to do this when generating the final output row (here). |
+ int max_color_channel = std::max(out_row[byte_offset + 0], |
+ std::max(out_row[byte_offset + 1], out_row[byte_offset + 2])); |
+ if (alpha < max_color_channel) |
+ out_row[byte_offset + 3] = max_color_channel; |
+ else |
+ out_row[byte_offset + 3] = alpha; |
+ } else { |
+ // No alpha channel, the image is opaque. |
+ out_row[byte_offset + 3] = 0xff; |
+ } |
+ } |
+ } |
+ |
+ void ConvolveVertically(const SkConvolutionFilter1D::Fixed* filterValues, |
+ int filterLength, |
+ unsigned char* const* source_data_rows, |
+ int pixel_width, |
+ unsigned char* out_row, |
+ bool source_has_alpha) { |
+ if (source_has_alpha) { |
+ ConvolveVertically<true>(filterValues, filterLength, |
+ source_data_rows, |
+ pixel_width, |
+ out_row); |
+ } else { |
+ ConvolveVertically<false>(filterValues, filterLength, |
+ source_data_rows, |
+ pixel_width, |
+ out_row); |
+ } |
+ } |
+ |
+} // namespace |
+ |
+// SkConvolutionFilter1D --------------------------------------------------------- |
+ |
+SkConvolutionFilter1D::SkConvolutionFilter1D() |
+: fMaxFilter(0) { |
+} |
+ |
+SkConvolutionFilter1D::~SkConvolutionFilter1D() { |
+} |
+ |
+void SkConvolutionFilter1D::AddFilter(int filterOffset, |
+ const float* filterValues, |
+int filterLength) { |
+ SkASSERT(filterLength > 0); |
+ |
+ std::vector<Fixed> fixed_values; |
+ fixed_values.reserve(filterLength); |
+ |
+ for (int i = 0; i < filterLength; ++i) |
+ fixed_values.push_back(FloatToFixed(filterValues[i])); |
+ |
+ AddFilter(filterOffset, &fixed_values[0], filterLength); |
+} |
+ |
+void SkConvolutionFilter1D::AddFilter(int filterOffset, |
+ const Fixed* filterValues, |
+ int filterLength) { |
+ // It is common for leading/trailing filter values to be zeros. In such |
+ // cases it is beneficial to only store the central factors. |
+ // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on |
+ // a 1080p image this optimization gives a ~10% speed improvement. |
+ int filter_size = filterLength; |
+ int first_non_zero = 0; |
+ while (first_non_zero < filterLength && filterValues[first_non_zero] == 0) |
+ first_non_zero++; |
+ |
+ if (first_non_zero < filterLength) { |
+ // Here we have at least one non-zero factor. |
+ int last_non_zero = filterLength - 1; |
+ while (last_non_zero >= 0 && filterValues[last_non_zero] == 0) |
+ last_non_zero--; |
+ |
+ filterOffset += first_non_zero; |
+ filterLength = last_non_zero + 1 - first_non_zero; |
+ SkASSERT(filterLength > 0); |
+ |
+ for (int i = first_non_zero; i <= last_non_zero; i++) |
+ fFilterValues.push_back(filterValues[i]); |
+ } else { |
+ // Here all the factors were zeroes. |
+ filterLength = 0; |
+ } |
+ |
+ FilterInstance instance; |
+ |
+ // We pushed filterLength elements onto fFilterValues |
+ instance.fDataLocation = (static_cast<int>(fFilterValues.size()) - |
+ filterLength); |
+ instance.fOffset = filterOffset; |
+ instance.fTrimmedLength = filterLength; |
+ instance.fLength = filter_size; |
+ fFilters.push_back(instance); |
+ |
+ fMaxFilter = std::max(fMaxFilter, filterLength); |
+} |
+ |
+const SkConvolutionFilter1D::Fixed* SkConvolutionFilter1D::GetSingleFilter( |
+ int* specified_filterLength, |
+ int* filterOffset, |
+ int* filterLength) const { |
+ const FilterInstance& filter = fFilters[0]; |
+ *filterOffset = filter.fOffset; |
+ *filterLength = filter.fTrimmedLength; |
+ *specified_filterLength = filter.fLength; |
+ if (filter.fTrimmedLength == 0) { |
+ return NULL; |
+ } |
+ |
+ return &fFilterValues[filter.fDataLocation]; |
+} |
+ |
+void BGRAConvolve2D(const unsigned char* sourceData, |
+ int sourceByteRowStride, |
+ bool sourceHasAlpha, |
+ const SkConvolutionFilter1D& filterX, |
+ const SkConvolutionFilter1D& filterY, |
+ int outputByteRowStride, |
+ unsigned char* output, |
+ SkConvolutionProcs *convolveProcs, |
+ bool useSimdIfPossible) { |
+ |
+ int maxYFilterSize = filterY.maxFilter(); |
+ |
+ // The next row in the input that we will generate a horizontally |
+ // convolved row for. If the filter doesn't start at the beginning of the |
+ // image (this is the case when we are only resizing a subset), then we |
+ // don't want to generate any output rows before that. Compute the starting |
+ // row for convolution as the first pixel for the first vertical filter. |
+ int filterOffset, filterLength; |
+ const SkConvolutionFilter1D::Fixed* filterValues = |
+ filterY.FilterForValue(0, &filterOffset, &filterLength); |
+ int nextXRow = filterOffset; |
+ |
+ // We loop over each row in the input doing a horizontal convolution. This |
+ // will result in a horizontally convolved image. We write the results into |
+ // a circular buffer of convolved rows and do vertical convolution as rows |
+ // are available. This prevents us from having to store the entire |
+ // intermediate image and helps cache coherency. |
+ // We will need four extra rows to allow horizontal convolution could be done |
+ // simultaneously. We also padding each row in row buffer to be aligned-up to |
+ // 16 bytes. |
+ // TODO(jiesun): We do not use aligned load from row buffer in vertical |
+ // convolution pass yet. Somehow Windows does not like it. |
+ int rowBufferWidth = (filterX.numValues() + 15) & ~0xF; |
+ int rowBufferHeight = maxYFilterSize + |
+ (convolveProcs->fConvolve4RowsHorizontally ? 4 : 0); |
+ CircularRowBuffer rowBuffer(rowBufferWidth, |
+ rowBufferHeight, |
+ filterOffset); |
+ |
+ // Loop over every possible output row, processing just enough horizontal |
+ // convolutions to run each subsequent vertical convolution. |
+ SkASSERT(outputByteRowStride >= filterX.numValues() * 4); |
+ int numOutputRows = filterY.numValues(); |
+ |
+ // We need to check which is the last line to convolve before we advance 4 |
+ // lines in one iteration. |
+ int lastFilterOffset, lastFilterLength; |
+ |
+ // SSE2 can access up to 3 extra pixels past the end of the |
+ // buffer. At the bottom of the image, we have to be careful |
+ // not to access data past the end of the buffer. Normally |
+ // we fall back to the C++ implementation for the last row. |
+ // If the last row is less than 3 pixels wide, we may have to fall |
+ // back to the C++ version for more rows. Compute how many |
+ // rows we need to avoid the SSE implementation for here. |
+ filterX.FilterForValue(filterX.numValues() - 1, &lastFilterOffset, |
+ &lastFilterLength); |
+ int avoidSimdRows = 1 + convolveProcs->fExtraHorizontalReads / |
+ (lastFilterOffset + lastFilterLength); |
+ |
+ filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset, |
+ &lastFilterLength); |
+ |
+ for (int outY = 0; outY < numOutputRows; outY++) { |
+ filterValues = filterY.FilterForValue(outY, |
+ &filterOffset, &filterLength); |
+ |
+ // Generate output rows until we have enough to run the current filter. |
+ while (nextXRow < filterOffset + filterLength) { |
+ if (convolveProcs->fConvolve4RowsHorizontally && |
+ nextXRow + 3 < lastFilterOffset + lastFilterLength - |
+ avoidSimdRows) { |
+ const unsigned char* src[4]; |
+ unsigned char* outRow[4]; |
+ for (int i = 0; i < 4; ++i) { |
+ src[i] = &sourceData[(nextXRow + i) * sourceByteRowStride]; |
+ outRow[i] = rowBuffer.advanceRow(); |
+ } |
+ convolveProcs->fConvolve4RowsHorizontally(src, filterX, outRow); |
+ nextXRow += 4; |
+ } else { |
+ // Check if we need to avoid SSE2 for this row. |
+ if (convolveProcs->fConvolveHorizontally && |
+ nextXRow < lastFilterOffset + lastFilterLength - |
+ avoidSimdRows) { |
+ convolveProcs->fConvolveHorizontally( |
+ &sourceData[nextXRow * sourceByteRowStride], |
+ filterX, rowBuffer.advanceRow(), sourceHasAlpha); |
+ } else { |
+ if (sourceHasAlpha) { |
+ ConvolveHorizontally<true>( |
+ &sourceData[nextXRow * sourceByteRowStride], |
+ filterX, rowBuffer.advanceRow()); |
+ } else { |
+ ConvolveHorizontally<false>( |
+ &sourceData[nextXRow * sourceByteRowStride], |
+ filterX, rowBuffer.advanceRow()); |
+ } |
+ } |
+ nextXRow++; |
+ } |
+ } |
+ |
+ // Compute where in the output image this row of final data will go. |
+ unsigned char* curOutputRow = &output[outY * outputByteRowStride]; |
+ |
+ // Get the list of rows that the circular buffer has, in order. |
+ int firstRowInCircularBuffer; |
+ unsigned char* const* rowsToConvolve = |
+ rowBuffer.GetRowAddresses(&firstRowInCircularBuffer); |
+ |
+ // Now compute the start of the subset of those rows that the filter |
+ // needs. |
+ unsigned char* const* firstRowForFilter = |
+ &rowsToConvolve[filterOffset - firstRowInCircularBuffer]; |
+ |
+ if (convolveProcs->fConvolveVertically) { |
+ convolveProcs->fConvolveVertically(filterValues, filterLength, |
+ firstRowForFilter, |
+ filterX.numValues(), curOutputRow, |
+ sourceHasAlpha); |
+ } else { |
+ ConvolveVertically(filterValues, filterLength, |
+ firstRowForFilter, |
+ filterX.numValues(), curOutputRow, |
+ sourceHasAlpha); |
+ } |
+ } |
+} |