Compare SkRegion and android::Region performance.

cc/android_region.cc

Index: cc/android_region.cc
diff --git a/cc/android_region.cc b/cc/android_region.cc
new file mode 100644
index 0000000000000000000000000000000000000000..a00cb80039ca871e44d708ed8749961131be3aad
--- /dev/null
+++ b/cc/android_region.cc
@@ -0,0 +1,690 @@
+/*
+ * Copyright (C) 2007 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "cc/android_region.h"
+
+#include <limits>
+
+#include "cc/android_region_helper.h"
+#include "third_party/skia/include/core/SkRect.h"
+#include "ui/gfx/rect.h"
+
+// ----------------------------------------------------------------------------
+#define VALIDATE_REGIONS        (false)
+#define VALIDATE_WITH_CORECG    (false)
+// ----------------------------------------------------------------------------
+
+#if VALIDATE_WITH_CORECG
+#include <core/SkRegion.h>
+#endif
+
+namespace android {
+// ----------------------------------------------------------------------------
+
+enum {
+    op_nand = region_operator<SkIRect, int>::op_nand,
+    op_and  = region_operator<SkIRect, int>::op_and,
+    op_or   = region_operator<SkIRect, int>::op_or,
+    op_xor  = region_operator<SkIRect, int>::op_xor
+};
+
+// ----------------------------------------------------------------------------
+
+Region::Region()
+    : mBounds(SkIRect::MakeWH(0,0))
+{
+}
+
+Region::Region(const Region& rhs)
+    : mBounds(rhs.mBounds), mStorage(rhs.mStorage)
+{
+#if VALIDATE_REGIONS
+    validate(rhs, "rhs copy-ctor");
+#endif
+}
+
+Region::Region(const SkIRect& rhs)
+    : mBounds(rhs)
+{
+}
+
+#if 0
+Region::Region(const void* buffer)
+{
+    status_t err = read(buffer);
+    ALOGE_IF(err<0, "error %s reading Region from buffer", strerror(err));
+}
+#endif
+
+Region::~Region()
+{
+}
+
+Region& Region::operator = (const Region& rhs)
+{
+#if VALIDATE_REGIONS
+    validate(*this, "this->operator=");
+    validate(rhs, "rhs.operator=");
+#endif
+    mBounds = rhs.mBounds;
+    mStorage = rhs.mStorage;
+    return *this;
+}
+
+Region& Region::makeBoundsSelf()
+{
+    mStorage.clear();
+    return *this;
+}
+
+void Region::clear()
+{
+    mBounds.setEmpty();
+    mStorage.clear();
+}
+
+void Region::set(const SkIRect& r)
+{
+    mBounds = r;
+    mStorage.clear();
+}
+
+void Region::set(int w, int h)
+{
+    mBounds = SkIRect::MakeWH(w, h);
+    mStorage.clear();
+}
+
+// ----------------------------------------------------------------------------
+
+void Region::addRectUnchecked(int l, int t, int r, int b)
+{
+    mStorage.push_back(SkIRect::MakeLTRB(l,t,r,b));
+#if VALIDATE_REGIONS
+    validate(*this, "addRectUnchecked");
+#endif
+}
+
+// ----------------------------------------------------------------------------
+
+Region& Region::orSelf(const SkIRect& r) {
+    return operationSelf(r, op_or);
+}
+Region& Region::xorSelf(const SkIRect& r) {
+    return operationSelf(r, op_xor);
+}
+Region& Region::andSelf(const SkIRect& r) {
+    return operationSelf(r, op_and);
+}
+Region& Region::subtractSelf(const SkIRect& r) {
+    return operationSelf(r, op_nand);
+}
+Region& Region::operationSelf(const SkIRect& r, int op) {
+    Region lhs(*this);
+    boolean_operation(op, *this, lhs, r);
+    return *this;
+}
+
+// ----------------------------------------------------------------------------
+
+Region& Region::orSelf(const Region& rhs) {
+    return operationSelf(rhs, op_or);
+}
+Region& Region::xorSelf(const Region& rhs) {
+    return operationSelf(rhs, op_xor);
+}
+Region& Region::andSelf(const Region& rhs) {
+    return operationSelf(rhs, op_and);
+}
+Region& Region::subtractSelf(const Region& rhs) {
+    return operationSelf(rhs, op_nand);
+}
+Region& Region::operationSelf(const Region& rhs, int op) {
+    Region lhs(*this);
+    boolean_operation(op, *this, lhs, rhs);
+    return *this;
+}
+
+Region& Region::translateSelf(int x, int y) {
+    if (x|y) translate(*this, x, y);
+    return *this;
+}
+
+// ----------------------------------------------------------------------------
+
+const Region Region::merge(const SkIRect& rhs) const {
+    return operation(rhs, op_or);
+}
+const Region Region::mergeExclusive(const SkIRect& rhs) const {
+    return operation(rhs, op_xor);
+}
+const Region Region::intersect(const SkIRect& rhs) const {
+    return operation(rhs, op_and);
+}
+const Region Region::subtract(const SkIRect& rhs) const {
+    return operation(rhs, op_nand);
+}
+const Region Region::operation(const SkIRect& rhs, int op) const {
+    Region result;
+    boolean_operation(op, result, *this, rhs);
+    return result;
+}
+
+// ----------------------------------------------------------------------------
+
+const Region Region::merge(const Region& rhs) const {
+    return operation(rhs, op_or);
+}
+const Region Region::mergeExclusive(const Region& rhs) const {
+    return operation(rhs, op_xor);
+}
+const Region Region::intersect(const Region& rhs) const {
+    return operation(rhs, op_and);
+}
+const Region Region::subtract(const Region& rhs) const {
+    return operation(rhs, op_nand);
+}
+const Region Region::operation(const Region& rhs, int op) const {
+    Region result;
+    boolean_operation(op, result, *this, rhs);
+    return result;
+}
+
+const Region Region::translate(int x, int y) const {
+    Region result;
+    translate(result, *this, x, y);
+    return result;
+}
+
+// ----------------------------------------------------------------------------
+
+Region& Region::orSelf(const Region& rhs, int dx, int dy) {
+    return operationSelf(rhs, dx, dy, op_or);
+}
+Region& Region::xorSelf(const Region& rhs, int dx, int dy) {
+    return operationSelf(rhs, dx, dy, op_xor);
+}
+Region& Region::andSelf(const Region& rhs, int dx, int dy) {
+    return operationSelf(rhs, dx, dy, op_and);
+}
+Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
+    return operationSelf(rhs, dx, dy, op_nand);
+}
+Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) {
+    Region lhs(*this);
+    boolean_operation(op, *this, lhs, rhs, dx, dy);
+    return *this;
+}
+
+// ----------------------------------------------------------------------------
+
+const Region Region::merge(const Region& rhs, int dx, int dy) const {
+    return operation(rhs, dx, dy, op_or);
+}
+const Region Region::mergeExclusive(const Region& rhs, int dx, int dy) const {
+    return operation(rhs, dx, dy, op_xor);
+}
+const Region Region::intersect(const Region& rhs, int dx, int dy) const {
+    return operation(rhs, dx, dy, op_and);
+}
+const Region Region::subtract(const Region& rhs, int dx, int dy) const {
+    return operation(rhs, dx, dy, op_nand);
+}
+const Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
+    Region result;
+    boolean_operation(op, result, *this, rhs, dx, dy);
+    return result;
+}
+
+// ----------------------------------------------------------------------------
+
+// This is our region rasterizer, which merges rects and spans together
+// to obtain an optimal region.
+class Region::rasterizer : public region_operator<SkIRect, int>::region_rasterizer 
+{
+    SkIRect& bounds;
+    std::vector<SkIRect>& storage;
+    SkIRect* head;
+    SkIRect* tail;
+    std::vector<SkIRect> span;
+    SkIRect* cur;
+public:
+    rasterizer(Region& reg) 
+        : bounds(reg.mBounds), storage(reg.mStorage), head(), tail(), cur() {
+        bounds.fTop = bounds.fBottom = 0;
+        bounds.fLeft   = INT_MAX;
+        bounds.fRight  = INT_MIN;
+        storage.clear();
+    }
+
+    ~rasterizer() {
+        if (span.size()) {
+            flushSpan();
+        }
+        if (storage.size()) {
+            bounds.fTop = storage.front().fTop;
+            bounds.fBottom = storage.back().fBottom;
+            if (storage.size() == 1) {
+                storage.clear();
+            }
+        } else {
+            bounds.fLeft  = 0;
+            bounds.fRight = 0;
+        }
+    }
+    
+    virtual void operator()(const SkIRect& rect) {
+        //ALOGD(">>> %3d, %3d, %3d, %3d",
+        //        rect.fLeft, rect.fTop, rect.fRight, rect.fBottom);
+        if (span.size()) {
+            if (cur->fTop != rect.fTop) {
+                flushSpan();
+            } else if (cur->fRight == rect.fLeft) {
+                cur->fRight = rect.fRight;
+                return;
+            }
+        }
+        span.push_back(rect);
+        cur = &span.front() + (span.size() - 1);
+    }
+private:
+    template<typename T> 
+    static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
+    template<typename T> 
+    static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
+    void flushSpan() {
+        bool merge = false;
+        if (tail-head == ssize_t(span.size())) {
+            SkIRect const* p = &span.front();
+            SkIRect const* q = head;
+            if (p->fTop == q->fBottom) {
+                merge = true;
+                while (q != tail) {
+                    if ((p->fLeft != q->fLeft) || (p->fRight != q->fRight)) {
+                        merge = false;
+                        break;
+                    }
+                    p++, q++;
+                }
+            }
+        }
+        if (merge) {
+            const int bottom = span[0].fBottom;
+            SkIRect* r = head;
+            while (r != tail) {
+                r->fBottom = bottom;
+                r++;
+            }
+        } else {
+            bounds.fLeft = min(span.front().fLeft, bounds.fLeft);
+            bounds.fRight = max(span.back().fRight, bounds.fRight);
+            storage.insert(storage.end(), span.begin(), span.end());
+            tail = &storage.front() + storage.size();
+            head = tail - span.size();
+        }
+        span.clear();
+    }
+};
+
+bool Region::validate(const Region& reg, const char* name)
+{
+#if !VALIDATE_REGIONS
+    return true;
+#else
+    bool result = true;
+    const_iterator cur = reg.begin();
+    const_iterator const tail = reg.end();
+    const_iterator prev = cur++;
+    SkIRect b(*prev);
+    while (cur != tail) {
+        b.fLeft   = b.fLeft   < cur->fLeft   ? b.fLeft   : cur->fLeft;
+        b.fTop    = b.fTop    < cur->fTop    ? b.fTop    : cur->fTop;
+        b.fRight  = b.fRight  > cur->fRight  ? b.fRight  : cur->fRight;
+        b.fBottom = b.fBottom > cur->fBottom ? b.fBottom : cur->fBottom;
+        if (cur->fTop == prev->fTop) {
+            if (cur->fBottom != prev->fBottom) {
+                ALOGE("%s: invalid span %p", name, cur);
+                result = false;
+            } else if (cur->fLeft < prev->fRight) {
+                ALOGE("%s: spans overlap horizontally prev=%p, cur=%p",
+                        name, prev, cur);
+                result = false;
+            }
+        } else if (cur->fTop < prev->fBottom) {
+            ALOGE("%s: spans overlap vertically prev=%p, cur=%p",
+                    name, prev, cur);
+            result = false;
+        }
+        prev = cur;
+        cur++;
+    }
+    if (b != reg.getBounds()) {
+        result = false;
+        ALOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
+                b.fLeft, b.fTop, b.fRight, b.fBottom,
+                reg.getBounds().fLeft, reg.getBounds().fTop, 
+                reg.getBounds().fRight, reg.getBounds().fBottom);
+    }
+    if (result == false) {
+        reg.dump(name);
+    }
+    return result;
+#endif
+}
+
+void Region::boolean_operation(int op, Region& dst,
+        const Region& lhs,
+        const Region& rhs, int dx, int dy)
+{
+#if VALIDATE_REGIONS
+    validate(lhs, "boolean_operation (before): lhs");
+    validate(rhs, "boolean_operation (before): rhs");
+    validate(dst, "boolean_operation (before): dst");
+#endif
+
+    size_t lhs_count;
+    SkIRect const * const lhs_rects = lhs.getArray(&lhs_count);
+
+    size_t rhs_count;
+    SkIRect const * const rhs_rects = rhs.getArray(&rhs_count);
+
+    region_operator<SkIRect, int>::region lhs_region(lhs_rects, lhs_count);
+    region_operator<SkIRect, int>::region rhs_region(rhs_rects, rhs_count, dx, dy);
+    region_operator<SkIRect, int> operation(op, lhs_region, rhs_region);
+    { // scope for rasterizer (dtor has side effects)
+        rasterizer r(dst);
+        operation(r);
+    }
+
+#if VALIDATE_REGIONS
+    validate(lhs, "boolean_operation: lhs");
+    validate(rhs, "boolean_operation: rhs");
+    validate(dst, "boolean_operation: dst");
+#endif
+
+#if VALIDATE_WITH_CORECG
+    SkRegion sk_lhs;
+    SkRegion sk_rhs;
+    SkRegion sk_dst;
+    
+    for (size_t i=0 ; i<lhs_count ; i++)
+        sk_lhs.op(
+                lhs_rects[i].fLeft   + dx,
+                lhs_rects[i].fTop    + dy,
+                lhs_rects[i].fRight  + dx,
+                lhs_rects[i].fBottom + dy,
+                SkRegion::kUnion_Op);
+    
+    for (size_t i=0 ; i<rhs_count ; i++)
+        sk_rhs.op(
+                rhs_rects[i].fLeft   + dx,
+                rhs_rects[i].fTop    + dy,
+                rhs_rects[i].fRight  + dx,
+                rhs_rects[i].fBottom + dy,
+                SkRegion::kUnion_Op);
+ 
+    const char* name = "---";
+    SkRegion::Op sk_op;
+    switch (op) {
+        case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
+        case op_xor: sk_op = SkRegion::kUnion_XOR; name="XOR"; break;
+        case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
+        case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
+    }
+    sk_dst.op(sk_lhs, sk_rhs, sk_op);
+
+    if (sk_dst.isEmpty() && dst.isEmpty())
+        return;
+    
+    bool same = true;
+    Region::const_iterator head = dst.begin();
+    Region::const_iterator const tail = dst.end();
+    SkRegion::Iterator it(sk_dst);
+    while (!it.done()) {
+        if (head != tail) {
+            if (
+                    head->fLeft != it.rect().fLeft ||     
+                    head->fTop != it.rect().fTop ||     
+                    head->fRight != it.rect().fRight ||     
+                    head->fBottom != it.rect().fBottom
+            ) {
+                same = false;
+                break;
+            }
+        } else {
+            same = false;
+            break;
+        }
+        head++;
+        it.next();
+    }
+    
+    if (head != tail) {
+        same = false;
+    }
+    
+    if(!same) {
+        ALOGD("---\nregion boolean %s failed", name);
+        lhs.dump("lhs");
+        rhs.dump("rhs");
+        dst.dump("dst");
+        ALOGD("should be");
+        SkRegion::Iterator it(sk_dst);
+        while (!it.done()) {
+            ALOGD("    [%3d, %3d, %3d, %3d]",
+                it.rect().fLeft,
+                it.rect().fTop,
+                it.rect().fRight,
+                it.rect().fBottom);
+            it.next();
+        }
+    }
+#endif
+}
+
+void Region::boolean_operation(int op, Region& dst,
+        const Region& lhs,
+        const SkIRect& rhs, int dx, int dy)
+{
+    if (rhs.width() < 0 || rhs.height() < 0) {
+#if 0
+        ALOGE("Region::boolean_operation(op=%d) invalid SkIRect={%d,%d,%d,%d}",
+                op, rhs.fLeft, rhs.fTop, rhs.fRight, rhs.fBottom);
+#endif
+        return;
+    }
+
+#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
+    boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
+#else
+    size_t lhs_count;
+    SkIRect const * const lhs_rects = lhs.getArray(&lhs_count);
+
+    region_operator<SkIRect, int>::region lhs_region(lhs_rects, lhs_count);
+    region_operator<SkIRect, int>::region rhs_region(&rhs, 1, dx, dy);
+    region_operator<SkIRect, int> operation(op, lhs_region, rhs_region);
+    { // scope for rasterizer (dtor has side effects)
+        rasterizer r(dst);
+        operation(r);
+    }
+
+#endif
+}
+
+void Region::boolean_operation(int op, Region& dst,
+        const Region& lhs, const Region& rhs)
+{
+    boolean_operation(op, dst, lhs, rhs, 0, 0);
+}
+
+void Region::boolean_operation(int op, Region& dst,
+        const Region& lhs, const SkIRect& rhs)
+{
+    boolean_operation(op, dst, lhs, rhs, 0, 0);
+}
+
+void Region::translate(Region& reg, int dx, int dy)
+{
+    if (!reg.isEmpty()) {
+#if VALIDATE_REGIONS
+        validate(reg, "translate (before)");
+#endif
+        reg.mBounds.offset(dx, dy);
+        size_t count = reg.mStorage.size();
+        SkIRect* rects = &reg.mStorage.front();
+        while (count) {
+            rects->offset(dx, dy);
+            rects++;
+            count--;
+        }
+#if VALIDATE_REGIONS
+        validate(reg, "translate (after)");
+#endif
+    }
+}
+
+void Region::translate(Region& dst, const Region& reg, int dx, int dy)
+{
+    dst = reg;
+    translate(dst, dx, dy);
+}
+
+// ----------------------------------------------------------------------------
+#if 0
+ssize_t Region::write(void* buffer, size_t size) const
+{
+#if VALIDATE_REGIONS
+    validate(*this, "write(buffer)");
+#endif
+    const size_t count = mStorage.size();
+    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(SkIRect);
+    if (buffer != NULL) {
+        if (sizeNeeded > size) return NO_MEMORY;
+        int32_t* const p = static_cast<int32_t*>(buffer);
+        *p = count;
+        memcpy(p+1, &mBounds, sizeof(SkIRect));
+        if (count) {
+            memcpy(p+5, &mStorage.front(), count*sizeof(SkIRect));
+        }
+    }
+    return ssize_t(sizeNeeded);
+}
+
+ssize_t Region::read(const void* buffer)
+{
+    int32_t const* const p = static_cast<int32_t const*>(buffer); 
+    const size_t count = *p;
+    memcpy(&mBounds, p+1, sizeof(SkIRect));
+    mStorage.clear();
+    if (count) {
+        mStorage.insertAt(0, count);
+        memcpy(&mStorage.front(), p+5, count*sizeof(SkIRect));
+    }
+#if VALIDATE_REGIONS
+    validate(*this, "read(buffer)");
+#endif
+    return ssize_t(sizeof(int32_t) + (1+count)*sizeof(SkIRect));
+}
+
+ssize_t Region::writeEmpty(void* buffer, size_t size)
+{
+    const size_t sizeNeeded = sizeof(int32_t) + sizeof(SkIRect);
+    if (sizeNeeded > size) return NO_MEMORY;
+    int32_t* const p = static_cast<int32_t*>(buffer); 
+    memset(p, 0, sizeNeeded);
+    return ssize_t(sizeNeeded);
+}
+
+bool Region::isEmpty(void* buffer)
+{
+    int32_t const* const p = static_cast<int32_t const*>(buffer); 
+    SkIRect const* const b = reinterpret_cast<SkIRect const *>(p+1);
+    return b->isEmpty();
+}
+#endif
+// ----------------------------------------------------------------------------
+
+Region::const_iterator Region::begin() const {
+    return isRect() ? &mBounds : &mStorage.front();
+}
+
+Region::const_iterator Region::end() const {
+    if (isRect()) {
+        if (isEmpty()) {
+            return &mBounds;
+        } else {
+            return &mBounds + 1;
+        }
+    } else {
+        return &mStorage.front() + mStorage.size();
+    }
+}
+
+SkIRect const* Region::getArray(size_t* count) const {
+    const_iterator const b(begin());
+    const_iterator const e(end());
+    if (count) *count = e-b;
+    return b;
+}
+
+size_t Region::getRects(std::vector<SkIRect>& rectList) const
+{
+    rectList = mStorage;
+    if (rectList.empty()) {
+        rectList.clear();
+        rectList.push_back(mBounds);
+    }
+    return rectList.size();
+}
+
+// ----------------------------------------------------------------------------
+#if 0
+void Region::dump(String8& out, const char* what, uint32_t flags) const
+{
+    (void)flags;
+    const_iterator head = begin();
+    const_iterator const tail = end();
+
+    size_t SIZE = 256;
+    char buffer[SIZE];
+
+    snprintf(buffer, SIZE, "  Region %s (this=%p, count=%d)\n",
+            what, this, tail-head);
+    out.append(buffer);
+    while (head != tail) {
+        snprintf(buffer, SIZE, "    [%3d, %3d, %3d, %3d]\n",
+                head->fLeft, head->fTop, head->fRight, head->fBottom);
+        out.append(buffer);
+        head++;
+    }
+}
+
+void Region::dump(const char* what, uint32_t flags) const
+{
+    (void)flags;
+    const_iterator head = begin();
+    const_iterator const tail = end();
+    ALOGD("  Region %s (this=%p, count=%d)\n", what, this, tail-head);
+    while (head != tail) {
+        ALOGD("    [%3d, %3d, %3d, %3d]\n",
+                head->fLeft, head->fTop, head->fRight, head->fBottom);
+        head++;
+    }
+}
+#endif
+// ----------------------------------------------------------------------------
+
+}; // namespace android