path: root/gfx/2d/SkConvolver.cpp

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
// Copyright (c) 2011-2016 Google Inc.
// Use of this source code is governed by a BSD-style license that can be
// found in the gfx/skia/LICENSE file.

#include "SkConvolver.h"

#ifdef USE_SSE2
#  include "mozilla/SSE.h"
#endif

#ifdef USE_NEON
#  include "mozilla/arm.h"
#endif

namespace skia {

// Converts the argument to an 8-bit unsigned value by clamping to the range
// 0-255.
static inline unsigned char ClampTo8(int a) {
  if (static_cast<unsigned>(a) < 256) {
    return a;  // Avoid the extra check in the common case.
  }
  if (a < 0) {
    return 0;
  }
  return 255;
}

// Convolves horizontally along a single row. The row data is given in
// |srcData| and continues for the numValues() of the filter.
template <bool hasAlpha>
void ConvolveHorizontally(const unsigned char* srcData,
                          const SkConvolutionFilter1D& filter,
                          unsigned char* outRow) {
  // Loop over each pixel on this row in the output image.
  int numValues = filter.numValues();
  for (int outX = 0; outX < numValues; outX++) {
    // Get the filter that determines the current output pixel.
    int filterOffset, filterLength;
    const SkConvolutionFilter1D::ConvolutionFixed* filterValues =
        filter.FilterForValue(outX, &filterOffset, &filterLength);

    // Compute the first pixel in this row that the filter affects. It will
    // touch |filterLength| pixels (4 bytes each) after this.
    const unsigned char* rowToFilter = &srcData[filterOffset * 4];

    // Apply the filter to the row to get the destination pixel in |accum|.
    int accum[4] = {0};
    for (int filterX = 0; filterX < filterLength; filterX++) {
      SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterX];
      accum[0] += curFilter * rowToFilter[filterX * 4 + 0];
      accum[1] += curFilter * rowToFilter[filterX * 4 + 1];
      accum[2] += curFilter * rowToFilter[filterX * 4 + 2];
      if (hasAlpha) {
        accum[3] += curFilter * rowToFilter[filterX * 4 + 3];
      }
    }

    // Bring this value back in range. All of the filter scaling factors
    // are in fixed point with kShiftBits bits of fractional part.
    accum[0] >>= SkConvolutionFilter1D::kShiftBits;
    accum[1] >>= SkConvolutionFilter1D::kShiftBits;
    accum[2] >>= SkConvolutionFilter1D::kShiftBits;

    if (hasAlpha) {
      accum[3] >>= SkConvolutionFilter1D::kShiftBits;
    }

    // Store the new pixel.
    outRow[outX * 4 + 0] = ClampTo8(accum[0]);
    outRow[outX * 4 + 1] = ClampTo8(accum[1]);
    outRow[outX * 4 + 2] = ClampTo8(accum[2]);
    if (hasAlpha) {
      outRow[outX * 4 + 3] = ClampTo8(accum[3]);
    }
  }
}

// Does vertical convolution to produce one output row. The filter values and
// length are given in the first two parameters. These are applied to each
// of the rows pointed to in the |sourceDataRows| array, with each row
// being |pixelWidth| wide.
//
// The output must have room for |pixelWidth * 4| bytes.
template <bool hasAlpha>
void ConvolveVertically(
    const SkConvolutionFilter1D::ConvolutionFixed* filterValues,
    int filterLength, unsigned char* const* sourceDataRows, int pixelWidth,
    unsigned char* outRow) {
  // We go through each column in the output and do a vertical convolution,
  // generating one output pixel each time.
  for (int outX = 0; outX < pixelWidth; outX++) {
    // Compute the number of bytes over in each row that the current column
    // we're convolving starts at. The pixel will cover the next 4 bytes.
    int byteOffset = outX * 4;

    // Apply the filter to one column of pixels.
    int accum[4] = {0};
    for (int filterY = 0; filterY < filterLength; filterY++) {
      SkConvolutionFilter1D::ConvolutionFixed curFilter = filterValues[filterY];
      accum[0] += curFilter * sourceDataRows[filterY][byteOffset + 0];
      accum[1] += curFilter * sourceDataRows[filterY][byteOffset + 1];
      accum[2] += curFilter * sourceDataRows[filterY][byteOffset + 2];
      if (hasAlpha) {
        accum[3] += curFilter * sourceDataRows[filterY][byteOffset + 3];
      }
    }

    // Bring this value back in range. All of the filter scaling factors
    // are in fixed point with kShiftBits bits of precision.
    accum[0] >>= SkConvolutionFilter1D::kShiftBits;
    accum[1] >>= SkConvolutionFilter1D::kShiftBits;
    accum[2] >>= SkConvolutionFilter1D::kShiftBits;
    if (hasAlpha) {
      accum[3] >>= SkConvolutionFilter1D::kShiftBits;
    }

    // Store the new pixel.
    outRow[byteOffset + 0] = ClampTo8(accum[0]);
    outRow[byteOffset + 1] = ClampTo8(accum[1]);
    outRow[byteOffset + 2] = ClampTo8(accum[2]);

    if (hasAlpha) {
      unsigned char alpha = ClampTo8(accum[3]);

      // Make sure the alpha channel doesn't come out smaller than any of the
      // color channels. We use premultipled alpha channels, so this should
      // never happen, but rounding errors will cause this from time to time.
      // These "impossible" colors will cause overflows (and hence random pixel
      // values) when the resulting bitmap is drawn to the screen.
      //
      // We only need to do this when generating the final output row (here).
      int maxColorChannel =
          std::max(outRow[byteOffset + 0],
                   std::max(outRow[byteOffset + 1], outRow[byteOffset + 2]));
      if (alpha < maxColorChannel) {
        outRow[byteOffset + 3] = maxColorChannel;
      } else {
        outRow[byteOffset + 3] = alpha;
      }
    } else {
      // No alpha channel, the image is opaque.
      outRow[byteOffset + 3] = 0xff;
    }
  }
}

#ifdef USE_SSE2
void convolve_vertically_avx2(const int16_t* filter, int filterLen,
                              uint8_t* const* srcRows, int width, uint8_t* out,
                              bool hasAlpha);
void convolve_horizontally_sse2(const unsigned char* srcData,
                                const SkConvolutionFilter1D& filter,
                                unsigned char* outRow, bool hasAlpha);
void convolve_vertically_sse2(const int16_t* filter, int filterLen,
                              uint8_t* const* srcRows, int width, uint8_t* out,
                              bool hasAlpha);
#elif defined(USE_NEON)
void convolve_horizontally_neon(const unsigned char* srcData,
                                const SkConvolutionFilter1D& filter,
                                unsigned char* outRow, bool hasAlpha);
void convolve_vertically_neon(const int16_t* filter, int filterLen,
                              uint8_t* const* srcRows, int width, uint8_t* out,
                              bool hasAlpha);
#endif

void convolve_horizontally(const unsigned char* srcData,
                           const SkConvolutionFilter1D& filter,
                           unsigned char* outRow, bool hasAlpha) {
#ifdef USE_SSE2
  if (mozilla::supports_sse2()) {
    convolve_horizontally_sse2(srcData, filter, outRow, hasAlpha);
    return;
  }
#elif defined(USE_NEON)
  if (mozilla::supports_neon()) {
    convolve_horizontally_neon(srcData, filter, outRow, hasAlpha);
    return;
  }
#endif
  if (hasAlpha) {
    ConvolveHorizontally<true>(srcData, filter, outRow);
  } else {
    ConvolveHorizontally<false>(srcData, filter, outRow);
  }
}

void convolve_vertically(
    const SkConvolutionFilter1D::ConvolutionFixed* filterValues,
    int filterLength, unsigned char* const* sourceDataRows, int pixelWidth,
    unsigned char* outRow, bool hasAlpha) {
#ifdef USE_SSE2
  if (mozilla::supports_avx2()) {
    convolve_vertically_avx2(filterValues, filterLength, sourceDataRows,
                             pixelWidth, outRow, hasAlpha);
    return;
  }
  if (mozilla::supports_sse2()) {
    convolve_vertically_sse2(filterValues, filterLength, sourceDataRows,
                             pixelWidth, outRow, hasAlpha);
    return;
  }
#elif defined(USE_NEON)
  if (mozilla::supports_neon()) {
    convolve_vertically_neon(filterValues, filterLength, sourceDataRows,
                             pixelWidth, outRow, hasAlpha);
    return;
  }
#endif
  if (hasAlpha) {
    ConvolveVertically<true>(filterValues, filterLength, sourceDataRows,
                             pixelWidth, outRow);
  } else {
    ConvolveVertically<false>(filterValues, filterLength, sourceDataRows,
                              pixelWidth, outRow);
  }
}

// Stores a list of rows in a circular buffer. The usage is you write into it
// by calling AdvanceRow. It will keep track of which row in the buffer it
// should use next, and the total number of rows added.
class CircularRowBuffer {
 public:
  // The number of pixels in each row is given in |sourceRowPixelWidth|.
  // The maximum number of rows needed in the buffer is |maxYFilterSize|
  // (we only need to store enough rows for the biggest filter).
  //
  // We use the |firstInputRow| to compute the coordinates of all of the
  // following rows returned by Advance().
  CircularRowBuffer(int destRowPixelWidth, int maxYFilterSize,
                    int firstInputRow)
      : fRowByteWidth(destRowPixelWidth * 4),
        fNumRows(maxYFilterSize),
        fNextRow(0),
        fNextRowCoordinate(firstInputRow) {}

  bool AllocBuffer() {
    return fBuffer.resize(fRowByteWidth * fNumRows) &&
           fRowAddresses.resize(fNumRows);
  }

  // Moves to the next row in the buffer, returning a pointer to the beginning
  // of it.
  unsigned char* advanceRow() {
    unsigned char* row = &fBuffer[fNextRow * fRowByteWidth];
    fNextRowCoordinate++;

    // Set the pointer to the next row to use, wrapping around if necessary.
    fNextRow++;
    if (fNextRow == fNumRows) {
      fNextRow = 0;
    }
    return row;
  }

  // Returns a pointer to an "unrolled" array of rows. These rows will start
  // at the y coordinate placed into |*firstRowIndex| and will continue in
  // order for the maximum number of rows in this circular buffer.
  //
  // The |firstRowIndex_| may be negative. This means the circular buffer
  // starts before the top of the image (it hasn't been filled yet).
  unsigned char* const* GetRowAddresses(int* firstRowIndex) {
    // Example for a 4-element circular buffer holding coords 6-9.
    //   Row 0   Coord 8
    //   Row 1   Coord 9
    //   Row 2   Coord 6  <- fNextRow = 2, fNextRowCoordinate = 10.
    //   Row 3   Coord 7
    //
    // The "next" row is also the first (lowest) coordinate. This computation
    // may yield a negative value, but that's OK, the math will work out
    // since the user of this buffer will compute the offset relative
    // to the firstRowIndex and the negative rows will never be used.
    *firstRowIndex = fNextRowCoordinate - fNumRows;

    int curRow = fNextRow;
    for (int i = 0; i < fNumRows; i++) {
      fRowAddresses[i] = &fBuffer[curRow * fRowByteWidth];

      // Advance to the next row, wrapping if necessary.
      curRow++;
      if (curRow == fNumRows) {
        curRow = 0;
      }
    }
    return &fRowAddresses[0];
  }

 private:
  // The buffer storing the rows. They are packed, each one fRowByteWidth.
  mozilla::Vector<unsigned char> fBuffer;

  // Number of bytes per row in the |buffer|.
  int fRowByteWidth;

  // The number of rows available in the buffer.
  int fNumRows;

  // The next row index we should write into. This wraps around as the
  // circular buffer is used.
  int fNextRow;

  // The y coordinate of the |fNextRow|. This is incremented each time a
  // new row is appended and does not wrap.
  int fNextRowCoordinate;

  // Buffer used by GetRowAddresses().
  mozilla::Vector<unsigned char*> fRowAddresses;
};

SkConvolutionFilter1D::SkConvolutionFilter1D() : fMaxFilter(0) {}

SkConvolutionFilter1D::~SkConvolutionFilter1D() = default;

bool SkConvolutionFilter1D::AddFilter(int filterOffset,
                                      const ConvolutionFixed* filterValues,
                                      int filterLength) {
  // It is common for leading/trailing filter values to be zeros. In such
  // cases it is beneficial to only store the central factors.
  // For a scaling to 1/4th in each dimension using a Lanczos-2 filter on
  // a 1080p image this optimization gives a ~10% speed improvement.
  int filterSize = filterLength;
  int firstNonZero = 0;
  while (firstNonZero < filterLength && filterValues[firstNonZero] == 0) {
    firstNonZero++;
  }

  if (firstNonZero < filterLength) {
    // Here we have at least one non-zero factor.
    int lastNonZero = filterLength - 1;
    while (lastNonZero >= 0 && filterValues[lastNonZero] == 0) {
      lastNonZero--;
    }

    filterOffset += firstNonZero;
    filterLength = lastNonZero + 1 - firstNonZero;
    MOZ_ASSERT(filterLength > 0);

    if (!fFilterValues.append(&filterValues[firstNonZero], filterLength)) {
      return false;
    }
  } else {
    // Here all the factors were zeroes.
    filterLength = 0;
  }

  FilterInstance instance = {
      // We pushed filterLength elements onto fFilterValues
      int(fFilterValues.length()) - filterLength, filterOffset, filterLength,
      filterSize};
  if (!fFilters.append(instance)) {
    if (filterLength > 0) {
      fFilterValues.shrinkBy(filterLength);
    }
    return false;
  }

  fMaxFilter = std::max(fMaxFilter, filterLength);
  return true;
}

bool SkConvolutionFilter1D::ComputeFilterValues(
    const SkBitmapFilter& aBitmapFilter, int32_t aSrcSize, int32_t aDstSize) {
  // When we're doing a magnification, the scale will be larger than one. This
  // means the destination pixels are much smaller than the source pixels, and
  // that the range covered by the filter won't necessarily cover any source
  // pixel boundaries. Therefore, we use these clamped values (max of 1) for
  // some computations.
  float scale = float(aDstSize) / float(aSrcSize);
  float clampedScale = std::min(1.0f, scale);
  // This is how many source pixels from the center we need to count
  // to support the filtering function.
  float srcSupport = aBitmapFilter.width() / clampedScale;
  float invScale = 1.0f / scale;

  mozilla::Vector<float, 64> filterValues;
  mozilla::Vector<ConvolutionFixed, 64> fixedFilterValues;

  // Loop over all pixels in the output range. We will generate one set of
  // filter values for each one. Those values will tell us how to blend the
  // source pixels to compute the destination pixel.

  // This value is computed based on how SkTDArray::resizeStorageToAtLeast works
  // in order to ensure that it does not overflow or assert. That functions
  // computes
  //   n+4 + (n+4)/4
  // and we want to to fit in a 32 bit signed int. Equating that to 2^31-1 and
  // solving n gives n = (2^31-6)*4/5 = 1717986913.6
  const int32_t maxToPassToReserveAdditional = 1717986913;

  int32_t filterValueCount = int32_t(ceilf(aDstSize * srcSupport * 2));
  if (aDstSize > maxToPassToReserveAdditional || filterValueCount < 0 ||
      filterValueCount > maxToPassToReserveAdditional ||
      !reserveAdditional(aDstSize, filterValueCount)) {
    return false;
  }
  size_t oldFiltersLength = fFilters.length();
  size_t oldFilterValuesLength = fFilterValues.length();
  int oldMaxFilter = fMaxFilter;
  for (int32_t destI = 0; destI < aDstSize; destI++) {
    // This is the pixel in the source directly under the pixel in the dest.
    // Note that we base computations on the "center" of the pixels. To see
    // why, observe that the destination pixel at coordinates (0, 0) in a 5.0x
    // downscale should "cover" the pixels around the pixel with *its center*
    // at coordinates (2.5, 2.5) in the source, not those around (0, 0).
    // Hence we need to scale coordinates (0.5, 0.5), not (0, 0).
    float srcPixel = (static_cast<float>(destI) + 0.5f) * invScale;

    // Compute the (inclusive) range of source pixels the filter covers.
    float srcBegin = std::max(0.0f, floorf(srcPixel - srcSupport));
    float srcEnd = std::min(aSrcSize - 1.0f, ceilf(srcPixel + srcSupport));

    // Compute the unnormalized filter value at each location of the source
    // it covers.

    // Sum of the filter values for normalizing.
    // Distance from the center of the filter, this is the filter coordinate
    // in source space. We also need to consider the center of the pixel
    // when comparing distance against 'srcPixel'. In the 5x downscale
    // example used above the distance from the center of the filter to
    // the pixel with coordinates (2, 2) should be 0, because its center
    // is at (2.5, 2.5).
    int32_t filterCount = int32_t(srcEnd - srcBegin) + 1;
    if (filterCount <= 0 || !filterValues.resize(filterCount) ||
        !fixedFilterValues.resize(filterCount)) {
      return false;
    }

    float destFilterDist = (srcBegin + 0.5f - srcPixel) * clampedScale;
    float filterSum = 0.0f;
    for (int32_t index = 0; index < filterCount; index++) {
      float filterValue = aBitmapFilter.evaluate(destFilterDist);
      filterValues[index] = filterValue;
      filterSum += filterValue;
      destFilterDist += clampedScale;
    }

    // The filter must be normalized so that we don't affect the brightness of
    // the image. Convert to normalized fixed point.
    ConvolutionFixed fixedSum = 0;
    float invFilterSum = 1.0f / filterSum;
    for (int32_t fixedI = 0; fixedI < filterCount; fixedI++) {
      ConvolutionFixed curFixed = ToFixed(filterValues[fixedI] * invFilterSum);
      fixedSum += curFixed;
      fixedFilterValues[fixedI] = curFixed;
    }

    // The conversion to fixed point will leave some rounding errors, which
    // we add back in to avoid affecting the brightness of the image. We
    // arbitrarily add this to the center of the filter array (this won't always
    // be the center of the filter function since it could get clipped on the
    // edges, but it doesn't matter enough to worry about that case).
    ConvolutionFixed leftovers = ToFixed(1) - fixedSum;
    fixedFilterValues[filterCount / 2] += leftovers;

    if (!AddFilter(int32_t(srcBegin), fixedFilterValues.begin(), filterCount)) {
      fFilters.shrinkTo(oldFiltersLength);
      fFilterValues.shrinkTo(oldFilterValuesLength);
      fMaxFilter = oldMaxFilter;
      return false;
    }
  }

  return maxFilter() > 0 && numValues() == aDstSize;
}

// Does a two-dimensional convolution on the given source image.
//
// It is assumed the source pixel offsets referenced in the input filters
// reference only valid pixels, so the source image size is not required. Each
// row of the source image starts |sourceByteRowStride| after the previous
// one (this allows you to have rows with some padding at the end).
//
// The result will be put into the given output buffer. The destination image
// size will be xfilter.numValues() * yfilter.numValues() pixels. It will be
// in rows of exactly xfilter.numValues() * 4 bytes.
//
// |sourceHasAlpha| is a hint that allows us to avoid doing computations on
// the alpha channel if the image is opaque. If you don't know, set this to
// true and it will work properly, but setting this to false will be a few
// percent faster if you know the image is opaque.
//
// The layout in memory is assumed to be 4-bytes per pixel in B-G-R-A order
// (this is ARGB when loaded into 32-bit words on a little-endian machine).
/**
 *  Returns false if it was unable to perform the convolution/rescale. in which
 * case the output buffer is assumed to be undefined.
 */
bool BGRAConvolve2D(const unsigned char* sourceData, int sourceByteRowStride,
                    bool sourceHasAlpha, const SkConvolutionFilter1D& filterX,
                    const SkConvolutionFilter1D& filterY,
                    int outputByteRowStride, unsigned char* output) {
  int maxYFilterSize = filterY.maxFilter();

  // The next row in the input that we will generate a horizontally
  // convolved row for. If the filter doesn't start at the beginning of the
  // image (this is the case when we are only resizing a subset), then we
  // don't want to generate any output rows before that. Compute the starting
  // row for convolution as the first pixel for the first vertical filter.
  int filterOffset = 0, filterLength = 0;
  const SkConvolutionFilter1D::ConvolutionFixed* filterValues =
      filterY.FilterForValue(0, &filterOffset, &filterLength);
  int nextXRow = filterOffset;

  // We loop over each row in the input doing a horizontal convolution. This
  // will result in a horizontally convolved image. We write the results into
  // a circular buffer of convolved rows and do vertical convolution as rows
  // are available. This prevents us from having to store the entire
  // intermediate image and helps cache coherency.
  // We will need four extra rows to allow horizontal convolution could be done
  // simultaneously. We also pad each row in row buffer to be aligned-up to
  // 32 bytes.
  // TODO(jiesun): We do not use aligned load from row buffer in vertical
  // convolution pass yet. Somehow Windows does not like it.
  int rowBufferWidth = (filterX.numValues() + 31) & ~0x1F;
  int rowBufferHeight = maxYFilterSize;

  // check for too-big allocation requests : crbug.com/528628
  {
    int64_t size = int64_t(rowBufferWidth) * int64_t(rowBufferHeight);
    // need some limit, to avoid over-committing success from malloc, but then
    // crashing when we try to actually use the memory.
    // 100meg seems big enough to allow "normal" zoom factors and image sizes
    // through while avoiding the crash seen by the bug (crbug.com/528628)
    if (size > 100 * 1024 * 1024) {
      //            printf_stderr("BGRAConvolve2D: tmp allocation [%lld] too
      //            big\n", size);
      return false;
    }
  }

  CircularRowBuffer rowBuffer(rowBufferWidth, rowBufferHeight, filterOffset);
  if (!rowBuffer.AllocBuffer()) {
    return false;
  }

  // Loop over every possible output row, processing just enough horizontal
  // convolutions to run each subsequent vertical convolution.
  MOZ_ASSERT(outputByteRowStride >= filterX.numValues() * 4);
  int numOutputRows = filterY.numValues();

  // We need to check which is the last line to convolve before we advance 4
  // lines in one iteration.
  int lastFilterOffset, lastFilterLength;
  filterY.FilterForValue(numOutputRows - 1, &lastFilterOffset,
                         &lastFilterLength);

  for (int outY = 0; outY < numOutputRows; outY++) {
    filterValues = filterY.FilterForValue(outY, &filterOffset, &filterLength);

    // Generate output rows until we have enough to run the current filter.
    while (nextXRow < filterOffset + filterLength) {
      convolve_horizontally(
          &sourceData[(uint64_t)nextXRow * sourceByteRowStride], filterX,
          rowBuffer.advanceRow(), sourceHasAlpha);
      nextXRow++;
    }

    // Compute where in the output image this row of final data will go.
    unsigned char* curOutputRow = &output[(uint64_t)outY * outputByteRowStride];

    // Get the list of rows that the circular buffer has, in order.
    int firstRowInCircularBuffer;
    unsigned char* const* rowsToConvolve =
        rowBuffer.GetRowAddresses(&firstRowInCircularBuffer);

    // Now compute the start of the subset of those rows that the filter needs.
    unsigned char* const* firstRowForFilter =
        &rowsToConvolve[filterOffset - firstRowInCircularBuffer];

    convolve_vertically(filterValues, filterLength, firstRowForFilter,
                        filterX.numValues(), curOutputRow, sourceHasAlpha);
  }
  return true;
}

}  // namespace skia