aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkConvolver.cpp
blob: 9f0cfea821fac9f297f07389e2318bd94a42623e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
// 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;
}