• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.
4 
5 #include "SkConvolver.h"
6 #include "SkOpts.h"
7 #include "SkTArray.h"
8 
9 namespace {
10     // Stores a list of rows in a circular buffer. The usage is you write into it
11     // by calling AdvanceRow. It will keep track of which row in the buffer it
12     // should use next, and the total number of rows added.
13     class CircularRowBuffer {
14     public:
15         // The number of pixels in each row is given in |sourceRowPixelWidth|.
16         // The maximum number of rows needed in the buffer is |maxYFilterSize|
17         // (we only need to store enough rows for the biggest filter).
18         //
19         // We use the |firstInputRow| to compute the coordinates of all of the
20         // following rows returned by Advance().
CircularRowBuffer(int destRowPixelWidth,int maxYFilterSize,int firstInputRow)21         CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize,
22                           int firstInputRow)
23             : fRowByteWidth(destRowPixelWidth * 4),
24               fNumRows(maxYFilterSize),
25               fNextRow(0),
26               fNextRowCoordinate(firstInputRow) {
27             fBuffer.reset(fRowByteWidth * maxYFilterSize);
28             fRowAddresses.reset(fNumRows);
29         }
30 
31         // Moves to the next row in the buffer, returning a pointer to the beginning
32         // of it.
advanceRow()33         unsigned char* advanceRow() {
34             unsigned char* row = &fBuffer[fNextRow * fRowByteWidth];
35             fNextRowCoordinate++;
36 
37             // Set the pointer to the next row to use, wrapping around if necessary.
38             fNextRow++;
39             if (fNextRow == fNumRows) {
40                 fNextRow = 0;
41             }
42             return row;
43         }
44 
45         // Returns a pointer to an "unrolled" array of rows. These rows will start
46         // at the y coordinate placed into |*firstRowIndex| and will continue in
47         // order for the maximum number of rows in this circular buffer.
48         //
49         // The |firstRowIndex_| may be negative. This means the circular buffer
50         // starts before the top of the image (it hasn't been filled yet).
GetRowAddresses(int * firstRowIndex)51         unsigned char* const* GetRowAddresses(int* firstRowIndex) {
52             // Example for a 4-element circular buffer holding coords 6-9.
53             //   Row 0   Coord 8
54             //   Row 1   Coord 9
55             //   Row 2   Coord 6  <- fNextRow = 2, fNextRowCoordinate = 10.
56             //   Row 3   Coord 7
57             //
58             // The "next" row is also the first (lowest) coordinate. This computation
59             // may yield a negative value, but that's OK, the math will work out
60             // since the user of this buffer will compute the offset relative
61             // to the firstRowIndex and the negative rows will never be used.
62             *firstRowIndex = fNextRowCoordinate - fNumRows;
63 
64             int curRow = fNextRow;
65             for (int i = 0; i < fNumRows; i++) {
66                 fRowAddresses[i] = &fBuffer[curRow * fRowByteWidth];
67 
68                 // Advance to the next row, wrapping if necessary.
69                 curRow++;
70                 if (curRow == fNumRows) {
71                     curRow = 0;
72                 }
73             }
74             return &fRowAddresses[0];
75         }
76 
77     private:
78         // The buffer storing the rows. They are packed, each one fRowByteWidth.
79         SkTArray<unsigned char> fBuffer;
80 
81         // Number of bytes per row in the |buffer|.
82         int fRowByteWidth;
83 
84         // The number of rows available in the buffer.
85         int fNumRows;
86 
87         // The next row index we should write into. This wraps around as the
88         // circular buffer is used.
89         int fNextRow;
90 
91         // The y coordinate of the |fNextRow|. This is incremented each time a
92         // new row is appended and does not wrap.
93         int fNextRowCoordinate;
94 
95         // Buffer used by GetRowAddresses().
96         SkTArray<unsigned char*> fRowAddresses;
97     };
98 
99 }  // namespace
100 
101 // SkConvolutionFilter1D ---------------------------------------------------------
102 
SkConvolutionFilter1D()103 SkConvolutionFilter1D::SkConvolutionFilter1D()
104 : fMaxFilter(0) {
105 }
106 
~SkConvolutionFilter1D()107 SkConvolutionFilter1D::~SkConvolutionFilter1D() {
108 }
109 
AddFilter(int filterOffset,const ConvolutionFixed * filterValues,int filterLength)110 void SkConvolutionFilter1D::AddFilter(int filterOffset,
111                                       const ConvolutionFixed* filterValues,
112                                       int filterLength) {
113     // It is common for leading/trailing filter values to be zeros. In such
114     // cases it is beneficial to only store the central factors.
115     // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on
116     // a 1080p image this optimization gives a ~10% speed improvement.
117     int filterSize = filterLength;
118     int firstNonZero = 0;
119     while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) {
120         firstNonZero++;
121     }
122 
123     if (firstNonZero < filterLength) {
124         // Here we have at least one non-zero factor.
125         int lastNonZero = filterLength - 1;
126         while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) {
127             lastNonZero--;
128         }
129 
130         filterOffset += firstNonZero;
131         filterLength = lastNonZero + 1 - firstNonZero;
132         SkASSERT(filterLength > 0);
133 
134         fFilterValues.append(filterLength, &filterValues[firstNonZero]);
135     } else {
136         // Here all the factors were zeroes.
137         filterLength = 0;
138     }
139 
140     FilterInstance instance;
141 
142     // We pushed filterLength elements onto fFilterValues
143     instance.fDataLocation = (static_cast<int>(fFilterValues.count()) -
144                                                filterLength);
145     instance.fOffset = filterOffset;
146     instance.fTrimmedLength = filterLength;
147     instance.fLength = filterSize;
148     fFilters.push(instance);
149 
150     fMaxFilter = SkTMax(fMaxFilter, filterLength);
151 }
152 
GetSingleFilter(int * specifiedFilterlength,int * filterOffset,int * filterLength) const153 const SkConvolutionFilter1D::ConvolutionFixed* SkConvolutionFilter1D::GetSingleFilter(
154                                         int* specifiedFilterlength,
155                                         int* filterOffset,
156                                         int* filterLength) const {
157     const FilterInstance& filter = fFilters[0];
158     *filterOffset = filter.fOffset;
159     *filterLength = filter.fTrimmedLength;
160     *specifiedFilterlength = filter.fLength;
161     if (filter.fTrimmedLength == 0) {
162         return nullptr;
163     }
164 
165     return &fFilterValues[filter.fDataLocation];
166 }
167 
BGRAConvolve2D(const unsigned char * sourceData,int sourceByteRowStride,bool sourceHasAlpha,const SkConvolutionFilter1D & filterX,const SkConvolutionFilter1D & filterY,int outputByteRowStride,unsigned char * output)168 bool BGRAConvolve2D(const unsigned char* sourceData,
169                     int sourceByteRowStride,
170                     bool sourceHasAlpha,
171                     const SkConvolutionFilter1D& filterX,
172                     const SkConvolutionFilter1D& filterY,
173                     int outputByteRowStride,
174                     unsigned char* output) {
175 
176     int maxYFilterSize = filterY.maxFilter();
177 
178     // The next row in the input that we will generate a horizontally
179     // convolved row for. If the filter doesn't start at the beginning of the
180     // image (this is the case when we are only resizing a subset), then we
181     // don't want to generate any output rows before that. Compute the starting
182     // row for convolution as the first pixel for the first vertical filter.
183     int filterOffset, filterLength;
184     const SkConvolutionFilter1D::ConvolutionFixed* filterValues =
185         filterY.FilterForValue(0, &filterOffset, &filterLength);
186     int nextXRow = filterOffset;
187 
188     // We loop over each row in the input doing a horizontal convolution. This
189     // will result in a horizontally convolved image. We write the results into
190     // a circular buffer of convolved rows and do vertical convolution as rows
191     // are available. This prevents us from having to store the entire
192     // intermediate image and helps cache coherency.
193     // We will need four extra rows to allow horizontal convolution could be done
194     // simultaneously. We also pad each row in row buffer to be aligned-up to
195     // 32 bytes.
196     // TODO(jiesun): We do not use aligned load from row buffer in vertical
197     // convolution pass yet. Somehow Windows does not like it.
198     int rowBufferWidth = (filterX.numValues() + 31) & ~0x1F;
199     int rowBufferHeight = maxYFilterSize +
200                           (SkOpts::convolve_4_rows_horizontally != nullptr ? 4 : 0);
201 
202     // check for too-big allocation requests : crbug.com/528628
203     {
204         int64_t size = sk_64_mul(rowBufferWidth, rowBufferHeight);
205         // need some limit, to avoid over-committing success from malloc, but then
206         // crashing when we try to actually use the memory.
207         // 100meg seems big enough to allow "normal" zoom factors and image sizes through
208         // while avoiding the crash seen by the bug (crbug.com/528628)
209         if (size > 100 * 1024 * 1024) {
210 //            SkDebugf("BGRAConvolve2D: tmp allocation [%lld] too big\n", size);
211             return false;
212         }
213     }
214 
215     CircularRowBuffer rowBuffer(rowBufferWidth,
216                                 rowBufferHeight,
217                                 filterOffset);
218 
219     // Loop over every possible output row, processing just enough horizontal
220     // convolutions to run each subsequent vertical convolution.
221     SkASSERT(outputByteRowStride >= filterX.numValues() * 4);
222     int numOutputRows = filterY.numValues();
223 
224     // We need to check which is the last line to convolve before we advance 4
225     // lines in one iteration.
226     int lastFilterOffset, lastFilterLength;
227     filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset,
228                            &lastFilterLength);
229 
230     for (int outY = 0; outY < numOutputRows; outY++) {
231         filterValues = filterY.FilterForValue(outY,
232                                               &filterOffset, &filterLength);
233 
234         // Generate output rows until we have enough to run the current filter.
235         while (nextXRow < filterOffset + filterLength) {
236             if (SkOpts::convolve_4_rows_horizontally != nullptr &&
237                 nextXRow + 3 < lastFilterOffset + lastFilterLength) {
238                 const unsigned char* src[4];
239                 unsigned char* outRow[4];
240                 for (int i = 0; i < 4; ++i) {
241                     src[i] = &sourceData[(uint64_t)(nextXRow + i) * sourceByteRowStride];
242                     outRow[i] = rowBuffer.advanceRow();
243                 }
244                 SkOpts::convolve_4_rows_horizontally(src, filterX, outRow, 4*rowBufferWidth);
245                 nextXRow += 4;
246             } else {
247                 SkOpts::convolve_horizontally(
248                         &sourceData[(uint64_t)nextXRow * sourceByteRowStride],
249                         filterX, rowBuffer.advanceRow(), sourceHasAlpha);
250                 nextXRow++;
251             }
252         }
253 
254         // Compute where in the output image this row of final data will go.
255         unsigned char* curOutputRow = &output[(uint64_t)outY * outputByteRowStride];
256 
257         // Get the list of rows that the circular buffer has, in order.
258         int firstRowInCircularBuffer;
259         unsigned char* const* rowsToConvolve =
260             rowBuffer.GetRowAddresses(&firstRowInCircularBuffer);
261 
262         // Now compute the start of the subset of those rows that the filter needs.
263         unsigned char* const* firstRowForFilter =
264             &rowsToConvolve[filterOffset - firstRowInCircularBuffer];
265 
266         SkOpts::convolve_vertically(filterValues, filterLength,
267                                     firstRowForFilter,
268                                     filterX.numValues(), curOutputRow,
269                                     sourceHasAlpha);
270     }
271     return true;
272 }
273