path: root/src/core/SkCoverageDelta.h

/*
 * Copyright 2017 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#ifndef SkCoverageDelta_DEFINED
#define SkCoverageDelta_DEFINED

#include "SkArenaAlloc.h"
#include "SkFixed.h"
#include "SkMask.h"
#include "SkTSort.h"
#include "SkUtils.h"

// Future todo: maybe we can make fX and fDelta 16-bit long to speed it up a little bit.
struct SkCoverageDelta {
    int     fX;     // the y coordinate will be implied in SkCoverageDeltaList
    SkFixed fDelta; // the amount that the alpha changed

    // Sort according to fX
    bool operator<(const SkCoverageDelta& other) const {
        return fX < other.fX;
    }
};

// All the arguments needed for SkBlitter::blitAntiRect
struct SkAntiRect {
    int     fX;
    int     fY;
    int     fWidth;
    int     fHeight;
    SkAlpha fLeftAlpha;
    SkAlpha fRightAlpha;
};

// A list of SkCoverageDelta with y from top() to bottom().
// For each row y, there are count(y) number of deltas.
// You can ask whether they are sorted or not by sorted(y), and you can sort them by sort(y).
// Once sorted, getDelta(y, i) should return the i-th leftmost delta on row y.
class SkCoverageDeltaList {
public:
    // We can store INIT_ROW_SIZE deltas per row (i.e., per y-scanline) initially.
#ifdef SK_BUILD_FOR_GOOGLE3
    static constexpr int INIT_ROW_SIZE = 8; // google3 has 16k stack limit; so we make it small
#else
    static constexpr int INIT_ROW_SIZE = 32;
#endif

    SkCoverageDeltaList(SkArenaAlloc* alloc, int top, int bottom, bool forceRLE);

    int  top() const { return fTop; }
    int  bottom() const { return fBottom; }
    bool forceRLE() const { return fForceRLE; }
    int  count(int y) const { this->checkY(y); return fCounts[y]; }
    bool sorted(int y) const { this->checkY(y); return fSorted[y]; }

    SK_ALWAYS_INLINE void addDelta(int x, int y, SkFixed delta) { this->push_back(y, {x, delta}); }
    SK_ALWAYS_INLINE const SkCoverageDelta& getDelta(int y, int i) const {
        this->checkY(y);
        SkASSERT(i < fCounts[y]);
        return fRows[y][i];
    }

    // It might be better to sort right before blitting to make the memory hot
    void sort(int y) {
        this->checkY(y);
        if (!fSorted[y]) {
            SkTQSort(fRows[y], fRows[y] + fCounts[y] - 1);
            fSorted[y] = true;
        }
    }

    const SkAntiRect& getAntiRect() const { return fAntiRect; }
    void setAntiRect(int x, int y, int width, int height,
            SkAlpha leftAlpha, SkAlpha rightAlpha) {
        fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
    }

private:
    SkArenaAlloc*               fAlloc;
    SkCoverageDelta**           fRows;
    bool*                       fSorted;
    int*                        fCounts;
    int*                        fMaxCounts;
    int                         fTop;
    int                         fBottom;
    SkAntiRect                  fAntiRect;
    bool                        fForceRLE;

    void checkY(int y) const { SkASSERT(y >= fTop && y < fBottom); }

    SK_ALWAYS_INLINE void push_back(int y, const SkCoverageDelta& delta) {
        this->checkY(y);
        if (fCounts[y] == fMaxCounts[y]) {
            fMaxCounts[y] *= 4;
            SkCoverageDelta* newRow = fAlloc->makeArrayDefault<SkCoverageDelta>(fMaxCounts[y]);
            memcpy(newRow, fRows[y], sizeof(SkCoverageDelta) * fCounts[y]);
            fRows[y] = newRow;
        }
        SkASSERT(fCounts[y] < fMaxCounts[y]);
        fRows[y][fCounts[y]++] = delta;
        fSorted[y] = fSorted[y] && (fCounts[y] == 1 || delta.fX >= fRows[y][fCounts[y] - 2].fX);
    }
};

class SkCoverageDeltaMask {
public:
    // 1 for precision error, 1 for boundary delta (e.g., -SK_Fixed1 at fBounds.fRight + 1)
    static constexpr int PADDING        = 2;

    static constexpr int SIMD_WIDTH     = 8;
    static constexpr int SUITABLE_WIDTH = 32;
#ifdef SK_BUILD_FOR_GOOGLE3
    static constexpr int MAX_MASK_SIZE  = 1024; // G3 has 16k stack limit based on -fstack-usage
#else
    static constexpr int MAX_MASK_SIZE  = 2048;
#endif
    static constexpr int MAX_SIZE       = MAX_MASK_SIZE * (sizeof(SkFixed) + sizeof(SkAlpha));

    // Expand PADDING on both sides, and make it a multiple of SIMD_WIDTH
    static int  ExpandWidth(int width);
    static bool CanHandle(const SkIRect& bounds);   // whether bounds fits into MAX_MASK_SIZE
    static bool Suitable(const SkIRect& bounds);    // CanHandle(bounds) && width <= SUITABLE_WIDTH

    SkCoverageDeltaMask(SkArenaAlloc* alloc, const SkIRect& bounds);

    int              top()       const { return fBounds.fTop; }
    int              bottom()    const { return fBounds.fBottom; }
    SkAlpha*         getMask()         { return fMask; }
    const SkIRect&   getBounds() const { return fBounds; }

    SK_ALWAYS_INLINE void addDelta (int x, int y, SkFixed delta) { this->delta(x, y) += delta; }
    SK_ALWAYS_INLINE SkFixed& delta (int x, int y) {
        this->checkX(x);
        this->checkY(y);
        return fDeltas[this->index(x, y)];
    }

    void setAntiRect(int x, int y, int width, int height,
                            SkAlpha leftAlpha, SkAlpha rightAlpha) {
        fAntiRect = {x, y, width, height, leftAlpha, rightAlpha};
    }

    SkMask prepareSkMask() {
        SkMask mask;
        mask.fImage     = fMask;
        mask.fBounds    = fBounds;
        mask.fRowBytes  = fBounds.width();
        mask.fFormat    = SkMask::kA8_Format;
        return mask;
    }

    void convertCoverageToAlpha(bool isEvenOdd, bool isInverse, bool isConvex);

private:
    SkIRect     fBounds;
    SkFixed*    fDeltaStorage;
    SkFixed*    fDeltas;
    SkAlpha*    fMask;
    int         fExpandedWidth;
    SkAntiRect  fAntiRect;

    SK_ALWAYS_INLINE int index(int x, int y) const { return y * fExpandedWidth + x; }

    void checkY(int y) const { SkASSERT(y >= fBounds.fTop && y < fBounds.fBottom); }
    void checkX(int x) const {
        SkASSERT(x >= fBounds.fLeft - PADDING && x < fBounds.fRight + PADDING);
    }
};

static SK_ALWAYS_INLINE SkAlpha CoverageToAlpha(SkFixed coverage, bool isEvenOdd, bool isInverse) {
    SkAlpha result;
    if (isEvenOdd) {
        SkFixed mod17 = coverage & 0x1ffff;
        SkFixed mod16 = coverage & 0xffff;
        result = SkTPin(SkAbs32((mod16 << 1) - mod17) >> 8, 0, 255);
    } else {
        result = SkTPin(SkAbs32(coverage) >> 8, 0, 255);
    }
    return isInverse ? 255 - result : result;
}

struct SkDAARecord {
    enum class Type {
        kToBeComputed,
        kMask,
        kList,
        kEmpty
    } fType;

    SkMask               fMask;
    SkCoverageDeltaList* fList;
    SkArenaAlloc*        fAlloc;

    SkDAARecord(SkArenaAlloc* alloc) : fType(Type::kToBeComputed), fAlloc(alloc) {}

    // When the scan converter returns early (e.g., the path is completely out of the clip), we set
    // the type to empty to signal that the record has been computed and it's empty. This is
    // required only for DEBUG where we check that the type must not be kToBeComputed after
    // init-once.
    void setEmpty() { fType = Type::kEmpty; }
    static inline void SetEmpty(SkDAARecord* record) { // record may be nullptr
#ifdef SK_DEBUG
        if (record) {
            record->setEmpty();
        }
#endif
    }
};

template<typename T>
static SK_ALWAYS_INLINE T CoverageToAlpha(const T&  coverage, bool isEvenOdd, bool isInverse) {
    T t0(0), t255(255);
    T result;
    if (isEvenOdd) {
        T mod17 = coverage & 0x1ffff;
        T mod16 = coverage & 0xffff;
        result = ((mod16 << 1) - mod17).abs() >> 8;
    } else {
        result = coverage.abs() >> 8;;
    }
    result = T::Min(result, t255);
    result = T::Max(result, t0);
    return isInverse ? 255 - result : result;
}

// For convex paths (including inverse mode), the coverage is guaranteed to be
// between [-SK_Fixed1, SK_Fixed1] so we can skip isEvenOdd and SkTPin.
static SK_ALWAYS_INLINE SkAlpha ConvexCoverageToAlpha(SkFixed coverage, bool isInverse) {
    SkASSERT(coverage >= -SK_Fixed1 && coverage <= SK_Fixed1);
    int result = SkAbs32(coverage) >> 8;
    result -= (result >> 8); // 256 to 255
    return isInverse ? 255 - result : result;
}

template<typename T>
static SK_ALWAYS_INLINE T ConvexCoverageToAlpha(const T& coverage, bool isInverse) {
    // allTrue is not implemented
    // SkASSERT((coverage >= 0).allTrue() && (coverage <= SK_Fixed1).allTrue());
    T result = coverage.abs() >> 8;
    result -= (result >> 8); // 256 to 255
    return isInverse ? 255 - result : result;
}

#endif