| // 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 "SkConvolver.h" |
| #include "SkOpts.h" |
| #include "SkTArray.h" |
| |
| namespace { |
| // 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 |sourceRowPixelWidth|. |
| // The maximum number of rows needed in the buffer is |maxYFilterSize| |
| // (we only need to store enough rows for the biggest filter). |
| // |
| // We use the |firstInputRow| 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.reset(fRowByteWidth * maxYFilterSize); |
| fRowAddresses.reset(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 |*firstRowIndex| and will continue in |
| // order for the maximum number of rows in this circular buffer. |
| // |
| // The |firstRowIndex_| 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 curRow = fNextRow; |
| for (int i = 0; i < fNumRows; i++) { |
| fRowAddresses[i] = &fBuffer[curRow * fRowByteWidth]; |
| |
| // Advance to the next row, wrapping if necessary. |
| curRow++; |
| if (curRow == fNumRows) { |
| curRow = 0; |
| } |
| } |
| return &fRowAddresses[0]; |
| } |
| |
| private: |
| // The buffer storing the rows. They are packed, each one fRowByteWidth. |
| SkTArray<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(). |
| SkTArray<unsigned char*> fRowAddresses; |
| }; |
| |
| } // namespace |
| |
| // SkConvolutionFilter1D --------------------------------------------------------- |
| |
| SkConvolutionFilter1D::SkConvolutionFilter1D() |
| : fMaxFilter(0) { |
| } |
| |
| SkConvolutionFilter1D::~SkConvolutionFilter1D() { |
| } |
| |
| void SkConvolutionFilter1D::AddFilter(int filterOffset, |
| const ConvolutionFixed* 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 filterSize = filterLength; |
| int firstNonZero = 0; |
| while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) { |
| firstNonZero++; |
| } |
| |
| if (firstNonZero < filterLength) { |
| // Here we have at least one non-zero factor. |
| int lastNonZero = filterLength - 1; |
| while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) { |
| lastNonZero--; |
| } |
| |
| filterOffset += firstNonZero; |
| filterLength = lastNonZero + 1 - firstNonZero; |
| SkASSERT(filterLength > 0); |
| |
| fFilterValues.append(filterLength, &filterValues[firstNonZero]); |
| } else { |
| // Here all the factors were zeroes. |
| filterLength = 0; |
| } |
| |
| FilterInstance instance; |
| |
| // We pushed filterLength elements onto fFilterValues |
| instance.fDataLocation = (static_cast<int>(fFilterValues.count()) - |
| filterLength); |
| instance.fOffset = filterOffset; |
| instance.fTrimmedLength = filterLength; |
| instance.fLength = filterSize; |
| fFilters.push(instance); |
| |
| fMaxFilter = SkTMax(fMaxFilter, filterLength); |
| } |
| |
| const SkConvolutionFilter1D::ConvolutionFixed* SkConvolutionFilter1D::GetSingleFilter( |
| int* specifiedFilterlength, |
| int* filterOffset, |
| int* filterLength) const { |
| const FilterInstance& filter = fFilters[0]; |
| *filterOffset = filter.fOffset; |
| *filterLength = filter.fTrimmedLength; |
| *specifiedFilterlength = filter.fLength; |
| if (filter.fTrimmedLength == 0) { |
| return nullptr; |
| } |
| |
| return &fFilterValues[filter.fDataLocation]; |
| } |
| |
| bool BGRAConvolve2D(const unsigned char* sourceData, |
| int sourceByteRowStride, |
| bool sourceHasAlpha, |
| const SkConvolutionFilter1D& filterX, |
| const SkConvolutionFilter1D& filterY, |
| int outputByteRowStride, |
| unsigned char* output) { |
| |
| 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::ConvolutionFixed* 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 pad each row in row buffer to be aligned-up to |
| // 32 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() + 31) & ~0x1F; |
| int rowBufferHeight = maxYFilterSize + |
| (SkOpts::convolve_4_rows_horizontally != nullptr ? 4 : 0); |
| |
| // check for too-big allocation requests : crbug.com/528628 |
| { |
| int64_t size = sk_64_mul(rowBufferWidth, rowBufferHeight); |
| // need some limit, to avoid over-committing success from malloc, but then |
| // crashing when we try to actually use the memory. |
| // 100meg seems big enough to allow "normal" zoom factors and image sizes through |
| // while avoiding the crash seen by the bug (crbug.com/528628) |
| if (size > 100 * 1024 * 1024) { |
| // SkDebugf("BGRAConvolve2D: tmp allocation [%lld] too big\n", size); |
| return false; |
| } |
| } |
| |
| 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; |
| 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 (SkOpts::convolve_4_rows_horizontally != nullptr && |
| nextXRow + 3 < lastFilterOffset + lastFilterLength) { |
| const unsigned char* src[4]; |
| unsigned char* outRow[4]; |
| for (int i = 0; i < 4; ++i) { |
| src[i] = &sourceData[(uint64_t)(nextXRow + i) * sourceByteRowStride]; |
| outRow[i] = rowBuffer.advanceRow(); |
| } |
| SkOpts::convolve_4_rows_horizontally(src, filterX, outRow, 4*rowBufferWidth); |
| nextXRow += 4; |
| } else { |
| SkOpts::convolve_horizontally( |
| &sourceData[(uint64_t)nextXRow * sourceByteRowStride], |
| filterX, rowBuffer.advanceRow(), sourceHasAlpha); |
| nextXRow++; |
| } |
| } |
| |
| // Compute where in the output image this row of final data will go. |
| unsigned char* curOutputRow = &output[(uint64_t)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]; |
| |
| SkOpts::convolve_vertically(filterValues, filterLength, |
| firstRowForFilter, |
| filterX.numValues(), curOutputRow, |
| sourceHasAlpha); |
| } |
| return true; |
| } |
