Quelle SkConvolver.cpp Sprache: C

/* -*- 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

quality91%

¤ Dauer der Verarbeitung: 0.14 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.