first cut at aaclipping

git-svn-id: http://skia.googlecode.com/svn/trunk@2410 2bbb7eff-a529-9590-31e7-b0007b416f81

2 files changed, 775 insertions, 0 deletions

diff --git a/src/core/SkAAClip.cpp b/src/core/SkAAClip.cpp
new file mode 100644
index 0000000000..c7cfca5c34
--- /dev/null
+++ b/src/core/SkAAClip.cpp
@@ -0,0 +1,676 @@
+
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkAAClip.h"
+#include "SkBlitter.h"
+#include "SkPath.h"
+#include "SkScan.h"
+#include "SkThread.h"
+
+static inline bool x_in_rect(int x, const SkIRect& rect) {
+    return (unsigned)(x - rect.fLeft) < (unsigned)rect.width();
+}
+
+static inline bool y_in_rect(int y, const SkIRect& rect) {
+    return (unsigned)(y - rect.fTop) < (unsigned)rect.height();
+}
+
+/*
+ *  Data runs are packed [count, alpha]
+ */
+
+struct SkAAClip::YOffset {
+    int32_t  fY;
+    uint32_t fOffset;
+};
+
+struct SkAAClip::RunHead {
+    int32_t fRefCnt;
+    int32_t fRowCount;
+    int32_t fDataSize;
+    
+    YOffset* yoffsets() {
+        return (YOffset*)((char*)this + sizeof(RunHead));
+    }
+    const YOffset* yoffsets() const {
+        return (const YOffset*)((const char*)this + sizeof(RunHead));
+    }
+    uint8_t* data() {
+        return (uint8_t*)(this->yoffsets() + fRowCount);
+    }
+    const uint8_t* data() const {
+        return (const uint8_t*)(this->yoffsets() + fRowCount);
+    }
+
+    static RunHead* Alloc(int rowCount, size_t dataSize) {
+        size_t size = sizeof(RunHead) + rowCount * sizeof(YOffset) + dataSize;
+        RunHead* head = (RunHead*)sk_malloc_throw(size);
+        head->fRefCnt = 1;
+        head->fRowCount = rowCount;
+        head->fDataSize = dataSize;
+        return head;
+    }
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+void SkAAClip::freeRuns() {
+    if (this->isComplex()) {
+        SkASSERT(fRunHead->fRefCnt >= 1);
+        if (1 == sk_atomic_dec(&fRunHead->fRefCnt)) {
+            sk_free(fRunHead);
+        }
+    }
+}
+
+SkAAClip::SkAAClip() {
+    fBounds.setEmpty();
+    fRunHead = SkAAClip_gEmptyPtr;
+}
+
+SkAAClip::SkAAClip(const SkAAClip& src) {
+    fRunHead = SkAAClip_gEmptyPtr;
+    *this = src;
+}
+
+SkAAClip::~SkAAClip() {
+    this->freeRuns();
+}
+
+SkAAClip& SkAAClip::operator=(const SkAAClip& src) {
+    if (this != &src) {
+        this->freeRuns();
+        fBounds = src.fBounds;
+        fRunHead = src.fRunHead;
+        if (this->isComplex()) {
+            sk_atomic_inc(&fRunHead->fRefCnt);
+        }
+    }
+    return *this;
+}
+
+bool operator==(const SkAAClip& a, const SkAAClip& b) {
+    if (&a == &b) {
+        return true;
+    }
+    if (a.fBounds != b.fBounds) {
+        return false;
+    }
+    
+    const SkAAClip::RunHead* ah = a.fRunHead;
+    const SkAAClip::RunHead* bh = b.fRunHead;
+    
+    // this catches empties and rects being equal
+    if (ah == bh) {
+        return true;
+    }
+
+    // now we insist that both are complex (but different ptrs)
+    if (!a.isComplex() || !b.isComplex()) {
+        return false;
+    }
+
+    return  ah->fRowCount == bh->fRowCount &&
+            ah->fDataSize == bh->fDataSize &&
+            !memcmp(ah->data(), bh->data(), ah->fDataSize);
+}
+
+void SkAAClip::swap(SkAAClip& other) {
+    SkTSwap(fBounds, other.fBounds);
+    SkTSwap(fRunHead, other.fRunHead);
+}
+
+bool SkAAClip::setEmpty() {
+    this->freeRuns();
+    fBounds.setEmpty();
+    fRunHead = SkAAClip_gEmptyPtr;
+    return false;
+}
+
+bool SkAAClip::setRect(const SkIRect& bounds) {
+    if (bounds.isEmpty()) {
+        return this->setEmpty();
+    }
+    this->freeRuns();
+    fBounds = bounds;
+    fRunHead = SkAAClip_gRectPtr;
+    return true;
+}
+
+bool SkAAClip::setRect(const SkRect& r) {
+    if (r.isEmpty()) {
+        return this->setEmpty();
+    }
+
+    SkIRect ibounds;
+    r.roundOut(&ibounds);
+
+    SkRegion clip;
+    clip.setRect(ibounds);
+
+    SkPath path;
+    path.addRect(r);
+    return this->setPath(path, clip);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+const uint8_t* SkAAClip::findRow(int y, int* lastYForRow) const {
+    SkASSERT(this->isComplex());
+
+    if (!y_in_rect(y, fBounds)) {
+        return NULL;
+    }
+    y -= fBounds.y();  // our yoffs values are relative to the top
+
+    const YOffset* yoff = fRunHead->yoffsets();
+    while (yoff->fY < y) {
+        yoff += 1;
+        SkASSERT(yoff - fRunHead->yoffsets() < fRunHead->fRowCount);
+    }
+
+    if (lastYForRow) {
+        *lastYForRow = yoff->fY;
+    }
+    return fRunHead->data() + yoff->fOffset;
+}
+
+const uint8_t* SkAAClip::findX(const uint8_t data[], int x, int* initialCount) const {
+    SkASSERT(x_in_rect(x, fBounds));
+    x -= fBounds.x();
+
+    // first skip up to X
+    for (;;) {
+        int n = data[0];
+        if (x < n) {
+            *initialCount = n - x;
+            break;
+        }
+        data += 2;
+        x -= n;
+    }
+    return data;
+}
+
+bool SkAAClip::quickContains(int left, int top, int right, int bottom) const {
+    if (this->isEmpty()) {
+        return false;
+    }
+    if (!fBounds.contains(left, top, right, bottom)) {
+        return false;
+    }
+    if (this->isRect()) {
+        return true;
+    }
+
+    int lastY;
+    const uint8_t* row = this->findRow(top, &lastY);
+    if (lastY < bottom) {
+        return false;
+    }
+    // now just need to check in X
+    int initialCount;
+    row = this->findX(row, left, &initialCount);
+    return initialCount >= (right - left) && 0xFF == row[1];
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+class SkAAClip::Builder {
+    SkIRect fBounds;
+    struct Row {
+        int fY;
+        int fWidth;
+        SkTDArray<uint8_t>* fData;
+    };
+    SkTDArray<Row>  fRows;
+    Row* fCurrRow;
+    int fPrevY;
+    int fWidth;
+
+public:
+    Builder(const SkIRect& bounds) : fBounds(bounds) {
+        fPrevY = -1;
+        fWidth = bounds.width();
+        fCurrRow = NULL;
+    }
+
+    ~Builder() {
+        Row* row = fRows.begin();
+        Row* stop = fRows.end();
+        while (row < stop) {
+            delete row->fData;
+            row += 1;
+        }
+    }
+
+    void addRun(int x, int y, U8CPU alpha, int count) {
+        SkASSERT(count > 0);
+        SkASSERT(fBounds.contains(x, y));
+        SkASSERT(fBounds.contains(x + count - 1, y));
+
+        x -= fBounds.left();
+        y -= fBounds.top();
+
+        Row* row = fCurrRow;
+        if (y != fPrevY) {
+            SkASSERT(y > fPrevY);
+            fPrevY = y;
+            row = this->flushRow(true);
+            row->fY = y;
+            row->fWidth = 0;
+            SkASSERT(row->fData);
+            SkASSERT(0 == row->fData->count());
+            fCurrRow = row;
+        }
+
+        SkASSERT(row->fWidth <= x);
+        SkASSERT(row->fWidth < fBounds.width());
+
+        SkTDArray<uint8_t>& data = *row->fData;
+
+        int gap = x - row->fWidth;
+        if (gap) {
+            AppendRun(data, 0, gap);
+            row->fWidth += gap;
+            SkASSERT(row->fWidth < fBounds.width());
+        }
+
+        AppendRun(data, alpha, count);
+        row->fWidth += count;
+        SkASSERT(row->fWidth <= fBounds.width());
+    }
+
+    RunHead* finish() {
+        this->flushRow(false);
+
+        const Row* row = fRows.begin();
+        const Row* stop = fRows.end();
+
+        size_t dataSize = 0;    
+        while (row < stop) {
+            dataSize += row->fData->count();
+            row += 1;
+        }
+
+        RunHead* head = RunHead::Alloc(fRows.count(), dataSize);
+        YOffset* yoffset = head->yoffsets();
+        uint8_t* data = head->data();
+        uint8_t* baseData = data;
+
+        row = fRows.begin();
+        while (row < stop) {
+            yoffset->fY = row->fY;
+            yoffset->fOffset = data - baseData;
+            yoffset += 1;
+            
+            size_t n = row->fData->count();
+            memcpy(data, row->fData->begin(), n);
+            data += n;
+            
+            row += 1;
+        }
+
+        return head;
+    }
+
+    void dump() {
+        this->validate();
+        int y;
+        for (y = 0; y < fRows.count(); ++y) {
+            const Row& row = fRows[y];
+            SkDebugf("Y:%3d W:%3d", row.fY, row.fWidth);
+            const SkTDArray<uint8_t>& data = *row.fData;
+            int count = data.count();
+            SkASSERT(!(count & 1));
+            const uint8_t* ptr = data.begin();
+            for (int x = 0; x < count; x += 2) {
+                SkDebugf(" [%3d:%02X]", ptr[0], ptr[1]);
+                ptr += 2;
+            }
+            SkDebugf("\n");
+        }
+
+#if 0
+        int prevY = -1;
+        for (y = 0; y < fRows.count(); ++y) {
+            const Row& row = fRows[y];
+            const SkTDArray<uint8_t>& data = *row.fData;
+            int count = data.count();
+            for (int n = prevY; n < row.fY; ++n) {
+                const uint8_t* ptr = data.begin();
+                for (int x = 0; x < count; x += 2) {
+                    for (int i = 0; i < ptr[0]; ++i) {
+                        SkDebugf("%02X", ptr[1]);
+                    }
+                    ptr += 2;
+                }
+                SkDebugf("\n");
+            }
+            prevY = row.fY;
+        }
+#endif
+    }
+
+    void validate() {
+#ifdef SK_DEBUG
+        int prevY = -1;
+        for (int i = 0; i < fRows.count(); ++i) {
+            const Row& row = fRows[i];
+            SkASSERT(prevY < row.fY);
+            SkASSERT(fWidth == row.fWidth);
+            int count = row.fData->count();
+            const uint8_t* ptr = row.fData->begin();
+            SkASSERT(!(count & 1));
+            int w = 0;
+            for (int x = 0; x < count; x += 2) {
+                w += ptr[0];
+                SkASSERT(w <= fWidth);
+                ptr += 2;
+            }
+            SkASSERT(w == fWidth);
+            prevY = row.fY;
+        }
+#endif
+    }
+
+private:
+    Row* flushRow(bool readyForAnother) {
+        Row* next = NULL;
+        int count = fRows.count();
+        if (count > 0) {
+            // flush current row if needed
+            Row* curr = &fRows[count - 1];
+            if (curr->fWidth < fWidth) {
+                AppendRun(*curr->fData, 0, fWidth - curr->fWidth);
+            }
+        }
+        if (count > 1) {
+            // are our last two runs the same?
+            Row* prev = &fRows[count - 2];
+            Row* curr = &fRows[count - 1];
+            SkASSERT(prev->fWidth == fWidth);
+            SkASSERT(curr->fWidth == fWidth);
+            if (*prev->fData == *curr->fData) {
+                prev->fY = curr->fY;
+                if (readyForAnother) {
+                    curr->fData->rewind();
+                    next = curr;
+                } else {
+                    delete curr->fData;
+                    fRows.removeShuffle(count - 1);
+                }
+            } else {
+                if (readyForAnother) {
+                    next = fRows.append();
+                    next->fData = new SkTDArray<uint8_t>;
+                }
+            }
+        } else {
+            if (readyForAnother) {
+                next = fRows.append();
+                next->fData = new SkTDArray<uint8_t>;
+            }
+        }
+        return next;
+    }
+
+    static void AppendRun(SkTDArray<uint8_t>& data, U8CPU alpha, int count) {
+        do {
+            int n = count;
+            if (n > 255) {
+                n = 255;
+            }
+            uint8_t* ptr = data.append(2);
+            ptr[0] = n;
+            ptr[1] = alpha;
+            count -= n;
+        } while (count > 0);
+    }
+};
+
+class SkAAClip::BuilderBlitter : public SkBlitter {
+public:
+    BuilderBlitter(Builder* builder) {
+        fBuilder = builder;
+    }
+
+    virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE
+        { unexpected(); }
+    virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE
+        { unexpected(); }
+    virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE
+        { unexpected(); }
+
+    virtual const SkBitmap* justAnOpaqueColor(uint32_t*) SK_OVERRIDE {
+        return false;
+    }
+
+    virtual void blitH(int x, int y, int width) SK_OVERRIDE {
+        fBuilder->addRun(x, y, 0xFF, width);
+    }
+
+    virtual void blitAntiH(int x, int y, const SkAlpha alpha[],
+                           const int16_t runs[]) SK_OVERRIDE {
+        for (;;) {
+            int count = *runs;
+            if (count <= 0) {
+                return;
+            }
+            fBuilder->addRun(x, y, *alpha, count);
+            runs += count;
+            alpha += count;
+            x += count;
+        }
+    }
+
+private:
+    Builder* fBuilder;
+
+    void unexpected() {
+        SkDebugf("---- did not expect to get called here");
+        sk_throw();
+    }
+};
+
+bool SkAAClip::setPath(const SkPath& path, const SkRegion& clip) {
+    if (clip.isEmpty()) {
+        return this->setEmpty();
+    }
+
+    SkIRect ibounds;
+
+    if (!path.isInverseFillType()) {
+        path.getBounds().roundOut(&ibounds);
+        if (ibounds.isEmpty() || !ibounds.intersect(clip.getBounds())) {
+            return this->setEmpty();
+        }
+    } else {
+        ibounds = clip.getBounds();
+    }
+
+    Builder        builder(ibounds);
+    BuilderBlitter blitter(&builder);
+
+    SkScan::AntiFillPath(path, clip, &blitter, true);
+
+    this->freeRuns();
+    fBounds = ibounds;
+    fRunHead = builder.finish();
+
+    builder.dump();
+}
+
+///////////////////////////////////////////////////////////////////////////////
+
+bool SkAAClip::op(const SkAAClip&, const SkAAClip&, SkRegion::Op op) {
+    return true;
+}
+
+///////////////////////////////////////////////////////////////////////////////
+///////////////////////////////////////////////////////////////////////////////
+
+static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width,
+                         int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) {
+    // we don't read our initial n from data, since the caller may have had to
+    // clip it, hence the initialCount parameter.
+    int n = initialCount;
+    for (;;) {
+        if (n > width) {
+            n = width;
+        }
+        SkASSERT(n > 0);
+        runs[0] = n;
+        runs += n;
+
+        aa[0] = data[1];
+        aa += n;
+        
+        data += 2;
+        width -= n;
+        if (0 == width) {
+            break;
+        }
+        // load the next count
+        n = data[0];
+    }
+    runs[0] = 0;    // sentinel
+}
+
+SkAAClipBlitter::~SkAAClipBlitter() {
+    sk_free(fRuns);
+}
+
+void SkAAClipBlitter::ensureRunsAndAA() {
+    if (NULL == fRuns) {
+        // add 1 so we can store the terminating run count of 0
+        int count = fAAClipBounds.width() + 1;
+        fRuns = (int16_t*)sk_malloc_throw(count * sizeof(int16_t) +
+                                          count * sizeof(SkAlpha));
+        fAA = (SkAlpha*)(fRuns + count);
+    }
+}
+
+void SkAAClipBlitter::blitH(int x, int y, int width) {
+    SkASSERT(width > 0);
+    SkASSERT(fAAClipBounds.contains(x, y));
+    SkASSERT(fAAClipBounds.contains(x + width  - 1, y));
+
+    int lastY;
+    const uint8_t* row = fAAClip->findRow(y, &lastY);
+    int initialCount;
+    row = fAAClip->findX(row, x, &initialCount);
+
+    if (initialCount >= width) {
+        SkAlpha alpha = row[1];
+        if (0 == alpha) {
+            return;
+        }
+        if (0xFF == alpha) {
+            fBlitter->blitH(x, y, width);
+            return;
+        }
+    }
+
+    this->ensureRunsAndAA();
+    expandToRuns(row, initialCount, width, fRuns, fAA);
+
+    fBlitter->blitAntiH(x, y, fAA, fRuns);
+}
+
+static void merge(const uint8_t* SK_RESTRICT row, int rowN,
+                  const SkAlpha* SK_RESTRICT srcAA,
+                  const int16_t* SK_RESTRICT srcRuns,
+                  SkAlpha* SK_RESTRICT dstAA,
+                  int16_t* SK_RESTRICT dstRuns,
+                  int width) {
+    SkDEBUGCODE(int accumulated = 0;)
+    int srcN = srcRuns[0];
+    for (;;) {
+        if (0 == srcN) {
+            break;
+        }
+        SkASSERT(rowN > 0);
+        SkASSERT(srcN > 0);
+
+        unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]);
+        int minN = SkMin32(srcN, rowN);
+        dstRuns[0] = minN;
+        dstRuns += minN;
+        dstAA[0] = newAlpha;
+        dstAA += minN;
+
+        if (0 == (srcN -= minN)) {
+            srcN = srcRuns[0];  // refresh
+            srcRuns += srcN;
+            srcAA += srcN;
+            srcN = srcRuns[0];  // reload
+        }
+        if (0 == (rowN -= minN)) {
+            row += 2;
+            rowN = row[0];  // reload
+        }
+        
+        SkDEBUGCODE(accumulated += minN;)
+        SkASSERT(accumulated <= width);
+    }
+}
+
+void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[],
+                                const int16_t runs[]) {
+    int lastY;
+    const uint8_t* row = fAAClip->findRow(y, &lastY);
+    int initialCount;
+    row = fAAClip->findX(row, x, &initialCount);
+
+    this->ensureRunsAndAA();
+
+    merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width());
+    fBlitter->blitAntiH(x, y, fAA, fRuns);
+}
+
+void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) {
+    if (fAAClip->quickContains(x, y, x + 1, y + height)) {
+        fBlitter->blitV(x, y, height, alpha);
+        return;
+    }
+
+    int stopY = y + height;
+    do {
+        int lastY;
+        const uint8_t* row = fAAClip->findRow(y, &lastY);
+        int initialCount;
+        row = fAAClip->findX(row, x, &initialCount);
+        SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]);
+        if (newAlpha) {
+            fBlitter->blitV(x, y, lastY - y + 1, newAlpha);
+        }
+        y = lastY + 1;
+    } while (y < stopY);
+}
+
+void SkAAClipBlitter::blitRect(int x, int y, int width, int height) {
+    if (fAAClip->quickContains(x, y, x + width, y + height)) {
+        fBlitter->blitRect(x, y, width, height);
+        return;
+    }
+
+    while (--height >= 0) {
+        this->blitH(x, y, width);
+        y += 1;
+    }
+}
+
+void SkAAClipBlitter::blitMask(const SkMask& mask, const SkIRect& clip) {
+    fBlitter->blitMask(mask, clip);
+}
+
+const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) {
+    return NULL;
+}
+
diff --git a/src/core/SkAAClip.h b/src/core/SkAAClip.h
new file mode 100644
index 0000000000..c62292f79e
--- /dev/null
+++ b/src/core/SkAAClip.h
@@ -0,0 +1,99 @@
+
+/*
+ * Copyright 2011 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkAAClip_DEFINED
+#define SkAAClip_DEFINED
+
+#include "SkBlitter.h"
+#include "SkRegion.h"
+
+#define SkAAClip_gEmptyPtr   ((SkAAClip::RunHead*)-1)
+#define SkAAClip_gRectPtr    NULL
+
+class SkAAClip {
+public:
+    SkAAClip();
+    SkAAClip(const SkAAClip&);
+    ~SkAAClip();
+
+    SkAAClip& operator=(const SkAAClip&);
+    friend bool operator==(const SkAAClip&, const SkAAClip&);
+    friend bool operator!=(const SkAAClip& a, const SkAAClip& b) {
+        return !(a == b);
+    }
+
+    void swap(SkAAClip&);
+
+    bool isEmpty() const { return SkAAClip_gEmptyPtr == fRunHead; }
+    bool isRect() const { return SkAAClip_gRectPtr == fRunHead; }
+    bool isComplex() const { return !this->isEmpty() && !this->isRect(); }
+    const SkIRect& getBounds() const { return fBounds; }
+
+    bool setEmpty();
+    bool setRect(const SkIRect&);
+    bool setRect(const SkRect&);
+    bool setPath(const SkPath&, const SkRegion& clip);
+
+    bool op(const SkAAClip&, const SkAAClip&, SkRegion::Op);
+
+    // called internally
+    
+    bool quickContains(int left, int top, int right, int bottom) const;
+    const uint8_t* findRow(int y, int* lastYForRow) const;
+    const uint8_t* findX(const uint8_t data[], int x, int* initialCount) const;
+
+private:
+    struct RunHead;
+    struct YOffset;
+
+    SkIRect  fBounds;
+    RunHead* fRunHead;
+
+    void freeRuns();
+
+    class Builder;
+    friend class Builder;
+    class BuilderBlitter;
+    friend class BuilderBlitter;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+class SkAAClipBlitter : public SkBlitter {
+public:
+    SkAAClipBlitter() : fRuns(NULL) {}
+    virtual ~SkAAClipBlitter();
+
+    void init(SkBlitter* blitter, const SkAAClip* aaclip) {
+        SkASSERT(aaclip && !aaclip->isEmpty());
+        fBlitter = blitter;
+        fAAClip = aaclip;
+        fAAClipBounds = aaclip->getBounds();
+    }
+    
+    virtual void blitH(int x, int y, int width) SK_OVERRIDE;
+    virtual void blitAntiH(int x, int y, const SkAlpha[],
+                           const int16_t runs[]) SK_OVERRIDE;
+    virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE;
+    virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE;
+    virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE;
+    virtual const SkBitmap* justAnOpaqueColor(uint32_t* value) SK_OVERRIDE;
+    
+private:
+    SkBlitter*      fBlitter;
+    const SkAAClip* fAAClip;
+    SkIRect         fAAClipBounds;
+
+    // lazily allocated
+    int16_t*        fRuns;
+    SkAlpha*        fAA;    // points into fRuns allocation
+
+    void ensureRunsAndAA();
+};
+
+#endif