Line data Source code
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 0 : 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().
21 0 : CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize,
22 : int firstInputRow)
23 0 : : fRowByteWidth(destRowPixelWidth * 4),
24 : fNumRows(maxYFilterSize),
25 : fNextRow(0),
26 0 : fNextRowCoordinate(firstInputRow) {
27 0 : fBuffer.reset(fRowByteWidth * maxYFilterSize);
28 0 : fRowAddresses.reset(fNumRows);
29 0 : }
30 :
31 : // Moves to the next row in the buffer, returning a pointer to the beginning
32 : // of it.
33 0 : unsigned char* advanceRow() {
34 0 : unsigned char* row = &fBuffer[fNextRow * fRowByteWidth];
35 0 : fNextRowCoordinate++;
36 :
37 : // Set the pointer to the next row to use, wrapping around if necessary.
38 0 : fNextRow++;
39 0 : if (fNextRow == fNumRows) {
40 0 : fNextRow = 0;
41 : }
42 0 : 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).
51 0 : 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 0 : *firstRowIndex = fNextRowCoordinate - fNumRows;
63 :
64 0 : int curRow = fNextRow;
65 0 : for (int i = 0; i < fNumRows; i++) {
66 0 : fRowAddresses[i] = &fBuffer[curRow * fRowByteWidth];
67 :
68 : // Advance to the next row, wrapping if necessary.
69 0 : curRow++;
70 0 : if (curRow == fNumRows) {
71 0 : curRow = 0;
72 : }
73 : }
74 0 : 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 :
103 0 : SkConvolutionFilter1D::SkConvolutionFilter1D()
104 0 : : fMaxFilter(0) {
105 0 : }
106 :
107 0 : SkConvolutionFilter1D::~SkConvolutionFilter1D() {
108 0 : }
109 :
110 0 : 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 0 : int filterSize = filterLength;
118 0 : int firstNonZero = 0;
119 0 : while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) {
120 0 : firstNonZero++;
121 : }
122 :
123 0 : if (firstNonZero < filterLength) {
124 : // Here we have at least one non-zero factor.
125 0 : int lastNonZero = filterLength - 1;
126 0 : while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) {
127 0 : lastNonZero--;
128 : }
129 :
130 0 : filterOffset += firstNonZero;
131 0 : filterLength = lastNonZero + 1 - firstNonZero;
132 0 : SkASSERT(filterLength > 0);
133 :
134 0 : fFilterValues.append(filterLength, &filterValues[firstNonZero]);
135 : } else {
136 : // Here all the factors were zeroes.
137 0 : filterLength = 0;
138 : }
139 :
140 : FilterInstance instance;
141 :
142 : // We pushed filterLength elements onto fFilterValues
143 0 : instance.fDataLocation = (static_cast<int>(fFilterValues.count()) -
144 : filterLength);
145 0 : instance.fOffset = filterOffset;
146 0 : instance.fTrimmedLength = filterLength;
147 0 : instance.fLength = filterSize;
148 0 : fFilters.push(instance);
149 :
150 0 : fMaxFilter = SkTMax(fMaxFilter, filterLength);
151 0 : }
152 :
153 0 : const SkConvolutionFilter1D::ConvolutionFixed* SkConvolutionFilter1D::GetSingleFilter(
154 : int* specifiedFilterlength,
155 : int* filterOffset,
156 : int* filterLength) const {
157 0 : const FilterInstance& filter = fFilters[0];
158 0 : *filterOffset = filter.fOffset;
159 0 : *filterLength = filter.fTrimmedLength;
160 0 : *specifiedFilterlength = filter.fLength;
161 0 : if (filter.fTrimmedLength == 0) {
162 0 : return nullptr;
163 : }
164 :
165 0 : return &fFilterValues[filter.fDataLocation];
166 : }
167 :
168 0 : 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 0 : 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 0 : filterY.FilterForValue(0, &filterOffset, &filterLength);
186 0 : 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 0 : int rowBufferWidth = (filterX.numValues() + 31) & ~0x1F;
199 : int rowBufferHeight = maxYFilterSize +
200 0 : (SkOpts::convolve_4_rows_horizontally != nullptr ? 4 : 0);
201 :
202 : // check for too-big allocation requests : crbug.com/528628
203 : {
204 0 : 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 0 : if (size > 100 * 1024 * 1024) {
210 : // SkDebugf("BGRAConvolve2D: tmp allocation [%lld] too big\n", size);
211 0 : return false;
212 : }
213 : }
214 :
215 : CircularRowBuffer rowBuffer(rowBufferWidth,
216 : rowBufferHeight,
217 0 : filterOffset);
218 :
219 : // Loop over every possible output row, processing just enough horizontal
220 : // convolutions to run each subsequent vertical convolution.
221 0 : SkASSERT(outputByteRowStride >= filterX.numValues() * 4);
222 0 : 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 0 : filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset,
228 0 : &lastFilterLength);
229 :
230 0 : for (int outY = 0; outY < numOutputRows; outY++) {
231 : filterValues = filterY.FilterForValue(outY,
232 0 : &filterOffset, &filterLength);
233 :
234 : // Generate output rows until we have enough to run the current filter.
235 0 : while (nextXRow < filterOffset + filterLength) {
236 0 : if (SkOpts::convolve_4_rows_horizontally != nullptr &&
237 0 : nextXRow + 3 < lastFilterOffset + lastFilterLength) {
238 : const unsigned char* src[4];
239 : unsigned char* outRow[4];
240 0 : for (int i = 0; i < 4; ++i) {
241 0 : src[i] = &sourceData[(uint64_t)(nextXRow + i) * sourceByteRowStride];
242 0 : outRow[i] = rowBuffer.advanceRow();
243 : }
244 0 : SkOpts::convolve_4_rows_horizontally(src, filterX, outRow, 4*rowBufferWidth);
245 0 : nextXRow += 4;
246 : } else {
247 0 : SkOpts::convolve_horizontally(
248 0 : &sourceData[(uint64_t)nextXRow * sourceByteRowStride],
249 0 : filterX, rowBuffer.advanceRow(), sourceHasAlpha);
250 0 : nextXRow++;
251 : }
252 : }
253 :
254 : // Compute where in the output image this row of final data will go.
255 0 : 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 0 : 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 0 : &rowsToConvolve[filterOffset - firstRowInCircularBuffer];
265 :
266 0 : SkOpts::convolve_vertically(filterValues, filterLength,
267 : firstRowForFilter,
268 : filterX.numValues(), curOutputRow,
269 0 : sourceHasAlpha);
270 : }
271 0 : return true;
272 : }
|
