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 // There's a bug somewhere here with GCC autovectorization (-ftree-vectorize). We originally 162 // thought this was 32 bit only, but subsequent tests show that some 64 bit gcc compiles 163 // suffer here too. 164 // 165 // Dropping to -O2 disables -ftree-vectorize. GCC 4.6 needs noinline. http://skbug.com/2575 166 #if SK_HAS_ATTRIBUTE(optimize) && defined(SK_RELEASE) 167 #define SK_MAYBE_DISABLE_VECTORIZATION __attribute__((optimize("O2"), noinline)) 168 #else 169 #define SK_MAYBE_DISABLE_VECTORIZATION 170 #endif 171 172 SK_MAYBE_DISABLE_VECTORIZATION 173 static void ConvolveHorizontallyAlpha(const unsigned char* srcData, 174 const SkConvolutionFilter1D& filter, 175 unsigned char* outRow) { 176 return ConvolveHorizontally<true>(srcData, filter, outRow); 177 } 178 179 SK_MAYBE_DISABLE_VECTORIZATION 180 static void ConvolveHorizontallyNoAlpha(const unsigned char* srcData, 181 const SkConvolutionFilter1D& filter, 182 unsigned char* outRow) { 183 return ConvolveHorizontally<false>(srcData, filter, outRow); 184 } 185 186 #undef SK_MAYBE_DISABLE_VECTORIZATION 187 188 189// Does vertical convolution to produce one output row. The filter values and 190// length are given in the first two parameters. These are applied to each 191// of the rows pointed to in the |sourceDataRows| array, with each row 192// being |pixelWidth| wide. 193// 194// The output must have room for |pixelWidth * 4| bytes. 195template<bool hasAlpha> 196 void ConvolveVertically(const SkConvolutionFilter1D::ConvolutionFixed* filterValues, 197 int filterLength, 198 unsigned char* const* sourceDataRows, 199 int pixelWidth, 200 unsigned char* outRow) { 201 // We go through each column in the output and do a vertical convolution, 202 // generating one output pixel each time. 203 for (int outX = 0; outX < pixelWidth; outX++) { 204 // Compute the number of bytes over in each row that the current column 205 // we're convolving starts at. The pixel will cover the next 4 bytes. 206 int byteOffset = outX * 4; 207 208 // Apply the filter to one column of pixels. 209 int accum[4] = {0}; 210 for (int filterY = 0; filterY < filterLength; filterY++) { 211 SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterY]; 212 accum[0] += curFilter * sourceDataRows[filterY][byteOffset + 0]; 213 accum[1] += curFilter * sourceDataRows[filterY][byteOffset + 1]; 214 accum[2] += curFilter * sourceDataRows[filterY][byteOffset + 2]; 215 if (hasAlpha) { 216 accum[3] += curFilter * sourceDataRows[filterY][byteOffset + 3]; 217 } 218 } 219 220 // Bring this value back in range. All of the filter scaling factors 221 // are in fixed point with kShiftBits bits of precision. 222 accum[0] >>= SkConvolutionFilter1D::kShiftBits; 223 accum[1] >>= SkConvolutionFilter1D::kShiftBits; 224 accum[2] >>= SkConvolutionFilter1D::kShiftBits; 225 if (hasAlpha) { 226 accum[3] >>= SkConvolutionFilter1D::kShiftBits; 227 } 228 229 // Store the new pixel. 230 outRow[byteOffset + 0] = ClampTo8(accum[0]); 231 outRow[byteOffset + 1] = ClampTo8(accum[1]); 232 outRow[byteOffset + 2] = ClampTo8(accum[2]); 233 if (hasAlpha) { 234 unsigned char alpha = ClampTo8(accum[3]); 235 236 // Make sure the alpha channel doesn't come out smaller than any of the 237 // color channels. We use premultipled alpha channels, so this should 238 // never happen, but rounding errors will cause this from time to time. 239 // These "impossible" colors will cause overflows (and hence random pixel 240 // values) when the resulting bitmap is drawn to the screen. 241 // 242 // We only need to do this when generating the final output row (here). 243 int maxColorChannel = SkTMax(outRow[byteOffset + 0], 244 SkTMax(outRow[byteOffset + 1], 245 outRow[byteOffset + 2])); 246 if (alpha < maxColorChannel) { 247 outRow[byteOffset + 3] = maxColorChannel; 248 } else { 249 outRow[byteOffset + 3] = alpha; 250 } 251 } else { 252 // No alpha channel, the image is opaque. 253 outRow[byteOffset + 3] = 0xff; 254 } 255 } 256 } 257 258 void ConvolveVertically(const SkConvolutionFilter1D::ConvolutionFixed* filterValues, 259 int filterLength, 260 unsigned char* const* sourceDataRows, 261 int pixelWidth, 262 unsigned char* outRow, 263 bool sourceHasAlpha) { 264 if (sourceHasAlpha) { 265 ConvolveVertically<true>(filterValues, filterLength, 266 sourceDataRows, pixelWidth, 267 outRow); 268 } else { 269 ConvolveVertically<false>(filterValues, filterLength, 270 sourceDataRows, pixelWidth, 271 outRow); 272 } 273 } 274 275} // namespace 276 277// SkConvolutionFilter1D --------------------------------------------------------- 278 279SkConvolutionFilter1D::SkConvolutionFilter1D() 280: fMaxFilter(0) { 281} 282 283SkConvolutionFilter1D::~SkConvolutionFilter1D() { 284} 285 286void SkConvolutionFilter1D::AddFilter(int filterOffset, 287 const float* filterValues, 288 int filterLength) { 289 SkASSERT(filterLength > 0); 290 291 SkTArray<ConvolutionFixed> fixedValues; 292 fixedValues.reset(filterLength); 293 294 for (int i = 0; i < filterLength; ++i) { 295 fixedValues.push_back(FloatToFixed(filterValues[i])); 296 } 297 298 AddFilter(filterOffset, &fixedValues[0], filterLength); 299} 300 301void SkConvolutionFilter1D::AddFilter(int filterOffset, 302 const ConvolutionFixed* filterValues, 303 int filterLength) { 304 // It is common for leading/trailing filter values to be zeros. In such 305 // cases it is beneficial to only store the central factors. 306 // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on 307 // a 1080p image this optimization gives a ~10% speed improvement. 308 int filterSize = filterLength; 309 int firstNonZero = 0; 310 while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) { 311 firstNonZero++; 312 } 313 314 if (firstNonZero < filterLength) { 315 // Here we have at least one non-zero factor. 316 int lastNonZero = filterLength - 1; 317 while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) { 318 lastNonZero--; 319 } 320 321 filterOffset += firstNonZero; 322 filterLength = lastNonZero + 1 - firstNonZero; 323 SkASSERT(filterLength > 0); 324 325 for (int i = firstNonZero; i <= lastNonZero; i++) { 326 fFilterValues.push_back(filterValues[i]); 327 } 328 } else { 329 // Here all the factors were zeroes. 330 filterLength = 0; 331 } 332 333 FilterInstance instance; 334 335 // We pushed filterLength elements onto fFilterValues 336 instance.fDataLocation = (static_cast<int>(fFilterValues.count()) - 337 filterLength); 338 instance.fOffset = filterOffset; 339 instance.fTrimmedLength = filterLength; 340 instance.fLength = filterSize; 341 fFilters.push_back(instance); 342 343 fMaxFilter = SkTMax(fMaxFilter, filterLength); 344} 345 346const SkConvolutionFilter1D::ConvolutionFixed* SkConvolutionFilter1D::GetSingleFilter( 347 int* specifiedFilterlength, 348 int* filterOffset, 349 int* filterLength) const { 350 const FilterInstance& filter = fFilters[0]; 351 *filterOffset = filter.fOffset; 352 *filterLength = filter.fTrimmedLength; 353 *specifiedFilterlength = filter.fLength; 354 if (filter.fTrimmedLength == 0) { 355 return NULL; 356 } 357 358 return &fFilterValues[filter.fDataLocation]; 359} 360 361void BGRAConvolve2D(const unsigned char* sourceData, 362 int sourceByteRowStride, 363 bool sourceHasAlpha, 364 const SkConvolutionFilter1D& filterX, 365 const SkConvolutionFilter1D& filterY, 366 int outputByteRowStride, 367 unsigned char* output, 368 const SkConvolutionProcs& convolveProcs, 369 bool useSimdIfPossible) { 370 371 int maxYFilterSize = filterY.maxFilter(); 372 373 // The next row in the input that we will generate a horizontally 374 // convolved row for. If the filter doesn't start at the beginning of the 375 // image (this is the case when we are only resizing a subset), then we 376 // don't want to generate any output rows before that. Compute the starting 377 // row for convolution as the first pixel for the first vertical filter. 378 int filterOffset, filterLength; 379 const SkConvolutionFilter1D::ConvolutionFixed* filterValues = 380 filterY.FilterForValue(0, &filterOffset, &filterLength); 381 int nextXRow = filterOffset; 382 383 // We loop over each row in the input doing a horizontal convolution. This 384 // will result in a horizontally convolved image. We write the results into 385 // a circular buffer of convolved rows and do vertical convolution as rows 386 // are available. This prevents us from having to store the entire 387 // intermediate image and helps cache coherency. 388 // We will need four extra rows to allow horizontal convolution could be done 389 // simultaneously. We also pad each row in row buffer to be aligned-up to 390 // 16 bytes. 391 // TODO(jiesun): We do not use aligned load from row buffer in vertical 392 // convolution pass yet. Somehow Windows does not like it. 393 int rowBufferWidth = (filterX.numValues() + 15) & ~0xF; 394 int rowBufferHeight = maxYFilterSize + 395 (convolveProcs.fConvolve4RowsHorizontally ? 4 : 0); 396 CircularRowBuffer rowBuffer(rowBufferWidth, 397 rowBufferHeight, 398 filterOffset); 399 400 // Loop over every possible output row, processing just enough horizontal 401 // convolutions to run each subsequent vertical convolution. 402 SkASSERT(outputByteRowStride >= filterX.numValues() * 4); 403 int numOutputRows = filterY.numValues(); 404 405 // We need to check which is the last line to convolve before we advance 4 406 // lines in one iteration. 407 int lastFilterOffset, lastFilterLength; 408 409 // SSE2 can access up to 3 extra pixels past the end of the 410 // buffer. At the bottom of the image, we have to be careful 411 // not to access data past the end of the buffer. Normally 412 // we fall back to the C++ implementation for the last row. 413 // If the last row is less than 3 pixels wide, we may have to fall 414 // back to the C++ version for more rows. Compute how many 415 // rows we need to avoid the SSE implementation for here. 416 filterX.FilterForValue(filterX.numValues() - 1, &lastFilterOffset, 417 &lastFilterLength); 418 int avoidSimdRows = 1 + convolveProcs.fExtraHorizontalReads / 419 (lastFilterOffset + lastFilterLength); 420 421 filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset, 422 &lastFilterLength); 423 424 for (int outY = 0; outY < numOutputRows; outY++) { 425 filterValues = filterY.FilterForValue(outY, 426 &filterOffset, &filterLength); 427 428 // Generate output rows until we have enough to run the current filter. 429 while (nextXRow < filterOffset + filterLength) { 430 if (convolveProcs.fConvolve4RowsHorizontally && 431 nextXRow + 3 < lastFilterOffset + lastFilterLength - 432 avoidSimdRows) { 433 const unsigned char* src[4]; 434 unsigned char* outRow[4]; 435 for (int i = 0; i < 4; ++i) { 436 src[i] = &sourceData[(uint64_t)(nextXRow + i) * sourceByteRowStride]; 437 outRow[i] = rowBuffer.advanceRow(); 438 } 439 convolveProcs.fConvolve4RowsHorizontally(src, filterX, outRow); 440 nextXRow += 4; 441 } else { 442 // Check if we need to avoid SSE2 for this row. 443 if (convolveProcs.fConvolveHorizontally && 444 nextXRow < lastFilterOffset + lastFilterLength - 445 avoidSimdRows) { 446 convolveProcs.fConvolveHorizontally( 447 &sourceData[(uint64_t)nextXRow * sourceByteRowStride], 448 filterX, rowBuffer.advanceRow(), sourceHasAlpha); 449 } else { 450 if (sourceHasAlpha) { 451 ConvolveHorizontallyAlpha( 452 &sourceData[(uint64_t)nextXRow * sourceByteRowStride], 453 filterX, rowBuffer.advanceRow()); 454 } else { 455 ConvolveHorizontallyNoAlpha( 456 &sourceData[(uint64_t)nextXRow * sourceByteRowStride], 457 filterX, rowBuffer.advanceRow()); 458 } 459 } 460 nextXRow++; 461 } 462 } 463 464 // Compute where in the output image this row of final data will go. 465 unsigned char* curOutputRow = &output[(uint64_t)outY * outputByteRowStride]; 466 467 // Get the list of rows that the circular buffer has, in order. 468 int firstRowInCircularBuffer; 469 unsigned char* const* rowsToConvolve = 470 rowBuffer.GetRowAddresses(&firstRowInCircularBuffer); 471 472 // Now compute the start of the subset of those rows that the filter 473 // needs. 474 unsigned char* const* firstRowForFilter = 475 &rowsToConvolve[filterOffset - firstRowInCircularBuffer]; 476 477 if (convolveProcs.fConvolveVertically) { 478 convolveProcs.fConvolveVertically(filterValues, filterLength, 479 firstRowForFilter, 480 filterX.numValues(), curOutputRow, 481 sourceHasAlpha); 482 } else { 483 ConvolveVertically(filterValues, filterLength, 484 firstRowForFilter, 485 filterX.numValues(), curOutputRow, 486 sourceHasAlpha); 487 } 488 } 489} 490