src/third_party/skia/src/core/SkConvolver.cpp

   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
   9 namespace {
  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.
 114 template<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.
 195 template<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
 279 SkConvolutionFilter1D::SkConvolutionFilter1D()
 280 : fMaxFilter(0) {
 281 }
 282
 283 SkConvolutionFilter1D::~SkConvolutionFilter1D() {
 284 }
 285
 286 void 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
 301 void 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
 346 const 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
 361 void 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 }