Production quality fast image up/downsampler

src/core/SkConvolver.cpp

+// 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 "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) {

[reed1, 2013/07/19 18:39:05]

Thanks for this fix. Just about every "if" in this file (and likely the other
files that were copied from chrome) has the same problem. If we're not going to
address these now, it should be a high-priority to do as a next CL.

+            a = 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.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 |*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.
+        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;
+    };
+
+// 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::ConvolutionFixed* 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::ConvolutionFixed 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::ConvolutionFixed* 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::ConvolutionFixed 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 = SkTMax(out_row[byte_offset + 0],
+                    SkTMax(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::ConvolutionFixed* 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);
+
+    SkTArray<ConvolutionFixed> fixed_values;
+    fixed_values.reset(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 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 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.count()) -
+        filterLength);
+    instance.fOffset = filterOffset;
+    instance.fTrimmedLength = filterLength;
+    instance.fLength = filter_size;
+    fFilters.push_back(instance);
+
+    fMaxFilter = SkTMax(fMaxFilter, filterLength);
+}
+
+const SkConvolutionFilter1D::ConvolutionFixed* 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::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
+    // 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);
+        }
+    }
+}