SkConvolver.cpp revision 4809e4d796a97d407970e224f1519b41638ab897
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 "SkSize.h" 7#include "SkTypes.h" 8 9namespace { 10 11 // Converts the argument to an 8-bit unsigned value by clamping to the range 12 // 0-255. 13 inline unsigned char ClampTo8(int a) { 14 if (static_cast<unsigned>(a) < 256) { 15 return a; // Avoid the extra check in the common case. 16 } 17 if (a < 0) { 18 return 0; 19 } 20 return 255; 21 } 22 23 // Stores a list of rows in a circular buffer. The usage is you write into it 24 // by calling AdvanceRow. It will keep track of which row in the buffer it 25 // should use next, and the total number of rows added. 26 class CircularRowBuffer { 27 public: 28 // The number of pixels in each row is given in |sourceRowPixelWidth|. 29 // The maximum number of rows needed in the buffer is |maxYFilterSize| 30 // (we only need to store enough rows for the biggest filter). 31 // 32 // We use the |firstInputRow| to compute the coordinates of all of the 33 // following rows returned by Advance(). 34 CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize, 35 int firstInputRow) 36 : fRowByteWidth(destRowPixelWidth * 4), 37 fNumRows(maxYFilterSize), 38 fNextRow(0), 39 fNextRowCoordinate(firstInputRow) { 40 fBuffer.reset(fRowByteWidth * maxYFilterSize); 41 fRowAddresses.reset(fNumRows); 42 } 43 44 // Moves to the next row in the buffer, returning a pointer to the beginning 45 // of it. 46 unsigned char* advanceRow() { 47 unsigned char* row = &fBuffer[fNextRow * fRowByteWidth]; 48 fNextRowCoordinate++; 49 50 // Set the pointer to the next row to use, wrapping around if necessary. 51 fNextRow++; 52 if (fNextRow == fNumRows) { 53 fNextRow = 0; 54 } 55 return row; 56 } 57 58 // Returns a pointer to an "unrolled" array of rows. These rows will start 59 // at the y coordinate placed into |*firstRowIndex| and will continue in 60 // order for the maximum number of rows in this circular buffer. 61 // 62 // The |firstRowIndex_| may be negative. This means the circular buffer 63 // starts before the top of the image (it hasn't been filled yet). 64 unsigned char* const* GetRowAddresses(int* firstRowIndex) { 65 // Example for a 4-element circular buffer holding coords 6-9. 66 // Row 0 Coord 8 67 // Row 1 Coord 9 68 // Row 2 Coord 6 <- fNextRow = 2, fNextRowCoordinate = 10. 69 // Row 3 Coord 7 70 // 71 // The "next" row is also the first (lowest) coordinate. This computation 72 // may yield a negative value, but that's OK, the math will work out 73 // since the user of this buffer will compute the offset relative 74 // to the firstRowIndex and the negative rows will never be used. 75 *firstRowIndex = fNextRowCoordinate - fNumRows; 76 77 int curRow = fNextRow; 78 for (int i = 0; i < fNumRows; i++) { 79 fRowAddresses[i] = &fBuffer[curRow * fRowByteWidth]; 80 81 // Advance to the next row, wrapping if necessary. 82 curRow++; 83 if (curRow == fNumRows) { 84 curRow = 0; 85 } 86 } 87 return &fRowAddresses[0]; 88 } 89 90 private: 91 // The buffer storing the rows. They are packed, each one fRowByteWidth. 92 SkTArray<unsigned char> fBuffer; 93 94 // Number of bytes per row in the |buffer|. 95 int fRowByteWidth; 96 97 // The number of rows available in the buffer. 98 int fNumRows; 99 100 // The next row index we should write into. This wraps around as the 101 // circular buffer is used. 102 int fNextRow; 103 104 // The y coordinate of the |fNextRow|. This is incremented each time a 105 // new row is appended and does not wrap. 106 int fNextRowCoordinate; 107 108 // Buffer used by GetRowAddresses(). 109 SkTArray<unsigned char*> fRowAddresses; 110 }; 111 112// Convolves horizontally along a single row. The row data is given in 113// |srcData| and continues for the numValues() of the filter. 114template<bool hasAlpha> 115 void ConvolveHorizontally(const unsigned char* srcData, 116 const SkConvolutionFilter1D& filter, 117 unsigned char* outRow) { 118 // Loop over each pixel on this row in the output image. 119 int numValues = filter.numValues(); 120 for (int outX = 0; outX < numValues; outX++) { 121 // Get the filter that determines the current output pixel. 122 int filterOffset, filterLength; 123 const SkConvolutionFilter1D::ConvolutionFixed* filterValues = 124 filter.FilterForValue(outX, &filterOffset, &filterLength); 125 126 // Compute the first pixel in this row that the filter affects. It will 127 // touch |filterLength| pixels (4 bytes each) after this. 128 const unsigned char* rowToFilter = &srcData[filterOffset * 4]; 129 130 // Apply the filter to the row to get the destination pixel in |accum|. 131 int accum[4] = {0}; 132 for (int filterX = 0; filterX < filterLength; filterX++) { 133 SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterX]; 134 accum[0] += curFilter * rowToFilter[filterX * 4 + 0]; 135 accum[1] += curFilter * rowToFilter[filterX * 4 + 1]; 136 accum[2] += curFilter * rowToFilter[filterX * 4 + 2]; 137 if (hasAlpha) { 138 accum[3] += curFilter * rowToFilter[filterX * 4 + 3]; 139 } 140 } 141 142 // Bring this value back in range. All of the filter scaling factors 143 // are in fixed point with kShiftBits bits of fractional part. 144 accum[0] >>= SkConvolutionFilter1D::kShiftBits; 145 accum[1] >>= SkConvolutionFilter1D::kShiftBits; 146 accum[2] >>= SkConvolutionFilter1D::kShiftBits; 147 if (hasAlpha) { 148 accum[3] >>= SkConvolutionFilter1D::kShiftBits; 149 } 150 151 // Store the new pixel. 152 outRow[outX * 4 + 0] = ClampTo8(accum[0]); 153 outRow[outX * 4 + 1] = ClampTo8(accum[1]); 154 outRow[outX * 4 + 2] = ClampTo8(accum[2]); 155 if (hasAlpha) { 156 outRow[outX * 4 + 3] = ClampTo8(accum[3]); 157 } 158 } 159 } 160 161// Does vertical convolution to produce one output row. The filter values and 162// length are given in the first two parameters. These are applied to each 163// of the rows pointed to in the |sourceDataRows| array, with each row 164// being |pixelWidth| wide. 165// 166// The output must have room for |pixelWidth * 4| bytes. 167template<bool hasAlpha> 168 void ConvolveVertically(const SkConvolutionFilter1D::ConvolutionFixed* filterValues, 169 int filterLength, 170 unsigned char* const* sourceDataRows, 171 int pixelWidth, 172 unsigned char* outRow) { 173 // We go through each column in the output and do a vertical convolution, 174 // generating one output pixel each time. 175 for (int outX = 0; outX < pixelWidth; outX++) { 176 // Compute the number of bytes over in each row that the current column 177 // we're convolving starts at. The pixel will cover the next 4 bytes. 178 int byteOffset = outX * 4; 179 180 // Apply the filter to one column of pixels. 181 int accum[4] = {0}; 182 for (int filterY = 0; filterY < filterLength; filterY++) { 183 SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterY]; 184 accum[0] += curFilter * sourceDataRows[filterY][byteOffset + 0]; 185 accum[1] += curFilter * sourceDataRows[filterY][byteOffset + 1]; 186 accum[2] += curFilter * sourceDataRows[filterY][byteOffset + 2]; 187 if (hasAlpha) { 188 accum[3] += curFilter * sourceDataRows[filterY][byteOffset + 3]; 189 } 190 } 191 192 // Bring this value back in range. All of the filter scaling factors 193 // are in fixed point with kShiftBits bits of precision. 194 accum[0] >>= SkConvolutionFilter1D::kShiftBits; 195 accum[1] >>= SkConvolutionFilter1D::kShiftBits; 196 accum[2] >>= SkConvolutionFilter1D::kShiftBits; 197 if (hasAlpha) { 198 accum[3] >>= SkConvolutionFilter1D::kShiftBits; 199 } 200 201 // Store the new pixel. 202 outRow[byteOffset + 0] = ClampTo8(accum[0]); 203 outRow[byteOffset + 1] = ClampTo8(accum[1]); 204 outRow[byteOffset + 2] = ClampTo8(accum[2]); 205 if (hasAlpha) { 206 unsigned char alpha = ClampTo8(accum[3]); 207 208 // Make sure the alpha channel doesn't come out smaller than any of the 209 // color channels. We use premultipled alpha channels, so this should 210 // never happen, but rounding errors will cause this from time to time. 211 // These "impossible" colors will cause overflows (and hence random pixel 212 // values) when the resulting bitmap is drawn to the screen. 213 // 214 // We only need to do this when generating the final output row (here). 215 int maxColorChannel = SkTMax(outRow[byteOffset + 0], 216 SkTMax(outRow[byteOffset + 1], 217 outRow[byteOffset + 2])); 218 if (alpha < maxColorChannel) { 219 outRow[byteOffset + 3] = maxColorChannel; 220 } else { 221 outRow[byteOffset + 3] = alpha; 222 } 223 } else { 224 // No alpha channel, the image is opaque. 225 outRow[byteOffset + 3] = 0xff; 226 } 227 } 228 } 229 230 void ConvolveVertically(const SkConvolutionFilter1D::ConvolutionFixed* filterValues, 231 int filterLength, 232 unsigned char* const* sourceDataRows, 233 int pixelWidth, 234 unsigned char* outRow, 235 bool sourceHasAlpha) { 236 if (sourceHasAlpha) { 237 ConvolveVertically<true>(filterValues, filterLength, 238 sourceDataRows, pixelWidth, 239 outRow); 240 } else { 241 ConvolveVertically<false>(filterValues, filterLength, 242 sourceDataRows, pixelWidth, 243 outRow); 244 } 245 } 246 247} // namespace 248 249// SkConvolutionFilter1D --------------------------------------------------------- 250 251SkConvolutionFilter1D::SkConvolutionFilter1D() 252: fMaxFilter(0) { 253} 254 255SkConvolutionFilter1D::~SkConvolutionFilter1D() { 256} 257 258void SkConvolutionFilter1D::AddFilter(int filterOffset, 259 const float* filterValues, 260 int filterLength) { 261 SkASSERT(filterLength > 0); 262 263 SkTArray<ConvolutionFixed> fixedValues; 264 fixedValues.reset(filterLength); 265 266 for (int i = 0; i < filterLength; ++i) { 267 fixedValues.push_back(FloatToFixed(filterValues[i])); 268 } 269 270 AddFilter(filterOffset, &fixedValues[0], filterLength); 271} 272 273void SkConvolutionFilter1D::AddFilter(int filterOffset, 274 const ConvolutionFixed* filterValues, 275 int filterLength) { 276 // It is common for leading/trailing filter values to be zeros. In such 277 // cases it is beneficial to only store the central factors. 278 // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on 279 // a 1080p image this optimization gives a ~10% speed improvement. 280 int filterSize = filterLength; 281 int firstNonZero = 0; 282 while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) { 283 firstNonZero++; 284 } 285 286 if (firstNonZero < filterLength) { 287 // Here we have at least one non-zero factor. 288 int lastNonZero = filterLength - 1; 289 while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) { 290 lastNonZero--; 291 } 292 293 filterOffset += firstNonZero; 294 filterLength = lastNonZero + 1 - firstNonZero; 295 SkASSERT(filterLength > 0); 296 297 for (int i = firstNonZero; i <= lastNonZero; i++) { 298 fFilterValues.push_back(filterValues[i]); 299 } 300 } else { 301 // Here all the factors were zeroes. 302 filterLength = 0; 303 } 304 305 FilterInstance instance; 306 307 // We pushed filterLength elements onto fFilterValues 308 instance.fDataLocation = (static_cast<int>(fFilterValues.count()) - 309 filterLength); 310 instance.fOffset = filterOffset; 311 instance.fTrimmedLength = filterLength; 312 instance.fLength = filterSize; 313 fFilters.push_back(instance); 314 315 fMaxFilter = SkTMax(fMaxFilter, filterLength); 316} 317 318const SkConvolutionFilter1D::ConvolutionFixed* SkConvolutionFilter1D::GetSingleFilter( 319 int* specifiedFilterlength, 320 int* filterOffset, 321 int* filterLength) const { 322 const FilterInstance& filter = fFilters[0]; 323 *filterOffset = filter.fOffset; 324 *filterLength = filter.fTrimmedLength; 325 *specifiedFilterlength = filter.fLength; 326 if (filter.fTrimmedLength == 0) { 327 return NULL; 328 } 329 330 return &fFilterValues[filter.fDataLocation]; 331} 332 333// There's a bug somewhere in here with GCC autovectorization (-ftree-vectorize) on 32 bit builds. 334// Dropping to -O2 disables -ftree-vectorize. http://skbug.com/2575 335#if defined(__i386) && SK_HAS_ATTRIBUTE(optimize) && defined(SK_RELEASE) 336 __attribute__((optimize("O2"))) 337#endif 338void BGRAConvolve2D(const unsigned char* sourceData, 339 int sourceByteRowStride, 340 bool sourceHasAlpha, 341 const SkConvolutionFilter1D& filterX, 342 const SkConvolutionFilter1D& filterY, 343 int outputByteRowStride, 344 unsigned char* output, 345 const SkConvolutionProcs& convolveProcs, 346 bool useSimdIfPossible) { 347 348 int maxYFilterSize = filterY.maxFilter(); 349 350 // The next row in the input that we will generate a horizontally 351 // convolved row for. If the filter doesn't start at the beginning of the 352 // image (this is the case when we are only resizing a subset), then we 353 // don't want to generate any output rows before that. Compute the starting 354 // row for convolution as the first pixel for the first vertical filter. 355 int filterOffset, filterLength; 356 const SkConvolutionFilter1D::ConvolutionFixed* filterValues = 357 filterY.FilterForValue(0, &filterOffset, &filterLength); 358 int nextXRow = filterOffset; 359 360 // We loop over each row in the input doing a horizontal convolution. This 361 // will result in a horizontally convolved image. We write the results into 362 // a circular buffer of convolved rows and do vertical convolution as rows 363 // are available. This prevents us from having to store the entire 364 // intermediate image and helps cache coherency. 365 // We will need four extra rows to allow horizontal convolution could be done 366 // simultaneously. We also pad each row in row buffer to be aligned-up to 367 // 16 bytes. 368 // TODO(jiesun): We do not use aligned load from row buffer in vertical 369 // convolution pass yet. Somehow Windows does not like it. 370 int rowBufferWidth = (filterX.numValues() + 15) & ~0xF; 371 int rowBufferHeight = maxYFilterSize + 372 (convolveProcs.fConvolve4RowsHorizontally ? 4 : 0); 373 CircularRowBuffer rowBuffer(rowBufferWidth, 374 rowBufferHeight, 375 filterOffset); 376 377 // Loop over every possible output row, processing just enough horizontal 378 // convolutions to run each subsequent vertical convolution. 379 SkASSERT(outputByteRowStride >= filterX.numValues() * 4); 380 int numOutputRows = filterY.numValues(); 381 382 // We need to check which is the last line to convolve before we advance 4 383 // lines in one iteration. 384 int lastFilterOffset, lastFilterLength; 385 386 // SSE2 can access up to 3 extra pixels past the end of the 387 // buffer. At the bottom of the image, we have to be careful 388 // not to access data past the end of the buffer. Normally 389 // we fall back to the C++ implementation for the last row. 390 // If the last row is less than 3 pixels wide, we may have to fall 391 // back to the C++ version for more rows. Compute how many 392 // rows we need to avoid the SSE implementation for here. 393 filterX.FilterForValue(filterX.numValues() - 1, &lastFilterOffset, 394 &lastFilterLength); 395 int avoidSimdRows = 1 + convolveProcs.fExtraHorizontalReads / 396 (lastFilterOffset + lastFilterLength); 397 398 filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset, 399 &lastFilterLength); 400 401 for (int outY = 0; outY < numOutputRows; outY++) { 402 filterValues = filterY.FilterForValue(outY, 403 &filterOffset, &filterLength); 404 405 // Generate output rows until we have enough to run the current filter. 406 while (nextXRow < filterOffset + filterLength) { 407 if (convolveProcs.fConvolve4RowsHorizontally && 408 nextXRow + 3 < lastFilterOffset + lastFilterLength - 409 avoidSimdRows) { 410 const unsigned char* src[4]; 411 unsigned char* outRow[4]; 412 for (int i = 0; i < 4; ++i) { 413 src[i] = &sourceData[(uint64_t)(nextXRow + i) * sourceByteRowStride]; 414 outRow[i] = rowBuffer.advanceRow(); 415 } 416 convolveProcs.fConvolve4RowsHorizontally(src, filterX, outRow); 417 nextXRow += 4; 418 } else { 419 // Check if we need to avoid SSE2 for this row. 420 if (convolveProcs.fConvolveHorizontally && 421 nextXRow < lastFilterOffset + lastFilterLength - 422 avoidSimdRows) { 423 convolveProcs.fConvolveHorizontally( 424 &sourceData[(uint64_t)nextXRow * sourceByteRowStride], 425 filterX, rowBuffer.advanceRow(), sourceHasAlpha); 426 } else { 427 if (sourceHasAlpha) { 428 ConvolveHorizontally<true>( 429 &sourceData[(uint64_t)nextXRow * sourceByteRowStride], 430 filterX, rowBuffer.advanceRow()); 431 } else { 432 ConvolveHorizontally<false>( 433 &sourceData[(uint64_t)nextXRow * sourceByteRowStride], 434 filterX, rowBuffer.advanceRow()); 435 } 436 } 437 nextXRow++; 438 } 439 } 440 441 // Compute where in the output image this row of final data will go. 442 unsigned char* curOutputRow = &output[outY * outputByteRowStride]; 443 444 // Get the list of rows that the circular buffer has, in order. 445 int firstRowInCircularBuffer; 446 unsigned char* const* rowsToConvolve = 447 rowBuffer.GetRowAddresses(&firstRowInCircularBuffer); 448 449 // Now compute the start of the subset of those rows that the filter 450 // needs. 451 unsigned char* const* firstRowForFilter = 452 &rowsToConvolve[filterOffset - firstRowInCircularBuffer]; 453 454 if (convolveProcs.fConvolveVertically) { 455 convolveProcs.fConvolveVertically(filterValues, filterLength, 456 firstRowForFilter, 457 filterX.numValues(), curOutputRow, 458 sourceHasAlpha); 459 } else { 460 ConvolveVertically(filterValues, filterLength, 461 firstRowForFilter, 462 filterX.numValues(), curOutputRow, 463 sourceHasAlpha); 464 } 465 } 466} 467