Region now has its own implementation instead of relying on SkRegion, which allows us to break libui's dependency on libcorecg.

13 files changed, 1001 insertions, 237 deletions

diff --git a/include/private/ui/RegionHelper.h b/include/private/ui/RegionHelper.h
new file mode 100644
index 0000000..6c847ff
--- /dev/null
+++ b/include/private/ui/RegionHelper.h
@@ -0,0 +1,279 @@
+/*
+ * Copyright (C) 2009 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.
+ */
+
+#ifndef ANDROID_UI_PRIVATE_REGION_HELPER_H
+#define ANDROID_UI_PRIVATE_REGION_HELPER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+namespace android {
+// ----------------------------------------------------------------------------
+
+template<typename RECT>
+class region_operator
+{
+    typedef typename RECT::value_type TYPE;    
+    static const TYPE max_value = 0x7FFFFFF;
+
+public:
+    /* 
+     * Common boolean operations:
+     * value is computed as 0b101 op 0b110
+     *    other boolean operation are possible, simply compute
+     *    their corresponding value with the above formulae and use
+     *    it when instantiating a region_operator.
+     */
+    static const uint32_t LHS = 0x5;  // 0b101
+    static const uint32_t RHS = 0x6;  // 0b110
+    enum {
+        op_nand = LHS & ~RHS,
+        op_and  = LHS &  RHS,
+        op_or   = LHS |  RHS,
+        op_xor  = LHS ^  RHS
+    };
+
+    struct region {
+        RECT const* rects;
+        size_t count;
+        TYPE dx;
+        TYPE dy;
+        inline region(const region& rhs) 
+            : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
+        inline region(RECT const* r, size_t c) 
+            : rects(r), count(c), dx(), dy() { }
+        inline region(RECT const* r, size_t c, TYPE dx, TYPE dy) 
+            : rects(r), count(c), dx(dx), dy(dy) { }
+    };
+
+    class region_rasterizer {
+        friend class region_operator;
+        virtual void operator()(const RECT& rect) = 0;
+    };
+    
+    inline region_operator(int op, const region& lhs, const region& rhs) 
+        : op_mask(op), spanner(lhs, rhs) 
+    {
+    }
+
+    void operator()(region_rasterizer& rasterizer) {
+        RECT current;
+        do {
+            SpannerInner spannerInner(spanner.lhs, spanner.rhs);
+            int inside = spanner.next(current.top, current.bottom);
+            spannerInner.prepare(inside);
+            do {
+                TYPE left, right;
+                int inside = spannerInner.next(current.left, current.right);
+                if ((op_mask >> inside) & 1) {
+                    if (current.left < current.right && 
+                            current.top < current.bottom) {
+                        rasterizer(current);
+                    }
+                }
+            } while(!spannerInner.isDone());            
+        } while(!spanner.isDone());
+    }
+
+private:    
+    uint32_t op_mask;
+
+    class SpannerBase
+    {
+    public:
+        enum {
+            lhs_before_rhs   = 0,
+            lhs_after_rhs    = 1,
+            lhs_coincide_rhs = 2
+        };
+
+    protected:
+        TYPE lhs_head;
+        TYPE lhs_tail;
+        TYPE rhs_head;
+        TYPE rhs_tail;
+
+        inline int next(TYPE& head, TYPE& tail,
+                bool& more_lhs, bool& more_rhs) 
+        {
+            int inside;
+            more_lhs = false;
+            more_rhs = false;
+            if (lhs_head < rhs_head) {
+                inside = lhs_before_rhs;
+                head = lhs_head;
+                if (lhs_tail <= rhs_head) {
+                    tail = lhs_tail;
+                    more_lhs = true;
+                } else {
+                    lhs_head = rhs_head;
+                    tail = rhs_head;
+                }
+            } else if (rhs_head < lhs_head) {
+                inside = lhs_after_rhs;
+                head = rhs_head;
+                if (rhs_tail <= lhs_head) {
+                    tail = rhs_tail;
+                    more_rhs = true;
+                } else {
+                    rhs_head = lhs_head;
+                    tail = lhs_head;
+                }
+            } else {
+                inside = lhs_coincide_rhs;
+                head = lhs_head;
+                if (lhs_tail <= rhs_tail) {
+                    tail = rhs_head = lhs_tail;
+                    more_lhs = true;
+                }
+                if (rhs_tail <= lhs_tail) {
+                    tail = lhs_head = rhs_tail;
+                    more_rhs = true;
+                }
+            }
+            return inside;
+        }
+    };
+
+    class Spanner : protected SpannerBase 
+    {
+        friend class region_operator;
+        region lhs;
+        region rhs;
+
+    public:
+        inline Spanner(const region& lhs, const region& rhs)
+            : lhs(lhs), rhs(rhs) 
+        {
+            SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
+            SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
+            SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
+            SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
+        }
+
+        inline bool isDone() const {
+            return !rhs.count && !lhs.count;
+        }
+
+        inline int next(TYPE& top, TYPE& bottom) 
+        {
+            bool more_lhs = false;
+            bool more_rhs = false;
+            int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
+            if (more_lhs) {
+                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
+            }
+            if (more_rhs) {
+                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
+            }
+            return inside;
+        }
+
+    private:
+        static inline 
+        void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
+            // got to next span
+            size_t count = reg.count;
+            RECT const * rects = reg.rects;
+            RECT const * const end = rects + count;
+            const int top = rects->top;
+            while (rects != end && rects->top == top) {
+                rects++;
+                count--;
+            }
+            if (rects != end) {
+                aTop    = rects->top    + reg.dy;
+                aBottom = rects->bottom + reg.dy;
+            } else {
+                aTop    = max_value;
+                aBottom = max_value;
+            }
+            reg.rects = rects;
+            reg.count = count;
+        }
+    };
+
+    class SpannerInner : protected SpannerBase 
+    {
+        region lhs;
+        region rhs;
+        
+    public:
+        inline SpannerInner(const region& lhs, const region& rhs)
+            : lhs(lhs), rhs(rhs) 
+        {
+        }
+
+        inline void prepare(int inside) {
+            SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
+            SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
+            SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
+            SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
+            if (inside == SpannerBase::lhs_before_rhs) {
+                SpannerBase::rhs_head = max_value;
+                SpannerBase::rhs_tail = max_value;
+            } else if (inside == SpannerBase::lhs_after_rhs) {
+                SpannerBase::lhs_head = max_value;
+                SpannerBase::lhs_tail = max_value;
+            } else {
+                // use both spans
+            }
+        }
+
+        inline bool isDone() const {
+            return SpannerBase::lhs_head == max_value && 
+                   SpannerBase::rhs_head == max_value;
+        }
+
+        inline int next(TYPE& left, TYPE& right) 
+        {
+            bool more_lhs = false;
+            bool more_rhs = false;
+            int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
+            if (more_lhs) {
+                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
+            }
+            if (more_rhs) {
+                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
+            }
+            return inside;
+        }
+
+    private:
+        static inline 
+        void advance(region& reg, TYPE& left, TYPE& right) {
+            if (reg.rects && reg.count) {
+                const int cur_span_top = reg.rects->top;
+                reg.rects++;
+                reg.count--;
+                if (!reg.count || reg.rects->top != cur_span_top) {
+                    left  = max_value;
+                    right = max_value;
+                } else {
+                    left  = reg.rects->left  + reg.dx;
+                    right = reg.rects->right + reg.dx;
+                }
+            }
+        }
+    };
+
+    Spanner spanner;
+};
+
+// ----------------------------------------------------------------------------
+};
+
+#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */
diff --git a/include/ui/Rect.h b/include/ui/Rect.h
index d232847..902324d 100644
--- a/include/ui/Rect.h
+++ b/include/ui/Rect.h
@@ -30,6 +30,8 @@ public:
     int right;
     int bottom;
 
+    typedef int value_type;
+    
     // we don't provide copy-ctor and operator= on purpose
     // because we want the compiler generated versions
 
@@ -54,6 +56,10 @@ public:
 
     void makeInvalid();
     
+    inline void clear() {
+        left = top = right = bottom = 0;
+    }
+    
     // a valid rectangle has a non negative width and height
     inline bool isValid() const {
         return (width()>=0) && (height()>=0);
@@ -78,28 +84,29 @@ public:
         return bottom-top;
     }
 
-    // returns left-top Point non-const reference, can be assigned
-    inline Point& leftTop() {
-        return reinterpret_cast<Point&>(left);
-    }
-    // returns right bottom non-const reference, can be assigned
-    inline Point& rightBottom() {
-        return reinterpret_cast<Point&>(right);
-    }
-    
     // the following 4 functions return the 4 corners of the rect as Point
-    inline const Point& leftTop() const {
-        return reinterpret_cast<const Point&>(left);
+    inline Point leftTop() const {
+        return Point(left, top);
     }
-    inline const Point& rightBottom() const {
-        return reinterpret_cast<const Point&>(right);
+    inline Point rightBottom() const {
+        return Point(right, bottom);
     }
-    Point rightTop() const {
+    inline Point rightTop() const {
         return Point(right, top);
     }
-    Point leftBottom() const {
+    inline Point leftBottom() const {
         return Point(left, bottom);
     }
+    
+    inline void setLeftTop(const Point& p) {
+        left = p.x;
+        top  = p.y;
+    }
+
+    inline void setRightBottom(const Point& p) {
+        right  = p.x;
+        bottom = p.y;
+    }
 
     // comparisons
     inline bool operator == (const Rect& rhs) const {
diff --git a/include/ui/Region.h b/include/ui/Region.h
index 5efeff7..849369d 100644
--- a/include/ui/Region.h
+++ b/include/ui/Region.h
@@ -27,8 +27,6 @@
 
 #include <hardware/copybit.h>
 
-#include <core/SkRegion.h>
-
 namespace android {
 // ---------------------------------------------------------------------------
 
@@ -40,7 +38,6 @@ class Region
 public:
                         Region();
                         Region(const Region& rhs);
-    explicit            Region(const SkRegion& rhs);
     explicit            Region(const Rect& rhs);
     explicit            Region(const Parcel& parcel);
     explicit            Region(const void* buffer);
@@ -48,12 +45,11 @@ public:
                         
         Region& operator = (const Region& rhs);
 
-    inline  bool        isEmpty() const     { return mRegion.isEmpty(); }
-    inline  bool        isRect() const      { return mRegion.isRect(); }
-
-            Rect        bounds() const;
+    inline  bool        isEmpty() const     { return mBounds.isEmpty();  }
+    inline  bool        isRect() const      { return mStorage.isEmpty(); }
 
-            const SkRegion& toSkRegion() const;
+    inline  const Rect& getBounds() const   { return mBounds; }
+    inline  const Rect& bounds() const      { return getBounds(); }
 
             void        clear();
             void        set(const Rect& r);
@@ -61,17 +57,17 @@ public:
         
             Region&     orSelf(const Rect& rhs);
             Region&     andSelf(const Rect& rhs);
+            Region&     subtractSelf(const Rect& rhs);
 
             // boolean operators, applied on this
             Region&     orSelf(const Region& rhs);
             Region&     andSelf(const Region& rhs);
             Region&     subtractSelf(const Region& rhs);
 
-            // these translate rhs first
-            Region&     translateSelf(int dx, int dy);
-            Region&     orSelf(const Region& rhs, int dx, int dy);
-            Region&     andSelf(const Region& rhs, int dx, int dy);
-            Region&     subtractSelf(const Region& rhs, int dx, int dy);
+            // boolean operators
+            Region      merge(const Rect& rhs) const;
+            Region      intersect(const Rect& rhs) const;
+            Region      subtract(const Rect& rhs) const;
 
             // boolean operators
             Region      merge(const Region& rhs) const;
@@ -79,6 +75,12 @@ public:
             Region      subtract(const Region& rhs) const;
 
             // these translate rhs first
+            Region&     translateSelf(int dx, int dy);
+            Region&     orSelf(const Region& rhs, int dx, int dy);
+            Region&     andSelf(const Region& rhs, int dx, int dy);
+            Region&     subtractSelf(const Region& rhs, int dx, int dy);
+
+            // these translate rhs first
             Region      translate(int dx, int dy) const;
             Region      merge(const Region& rhs, int dx, int dy) const;
             Region      intersect(const Region& rhs, int dx, int dy) const;
@@ -95,19 +97,23 @@ public:
     inline  Region&     operator -= (const Region& rhs);
     inline  Region&     operator += (const Point& pt);
 
-    class iterator {
-        SkRegion::Iterator  mIt;
-    public:
-        iterator(const Region& r);
-        inline operator bool () const { return !done(); }
-        int iterate(Rect* rect);
-    private:
-        inline bool done() const {
-            return const_cast<SkRegion::Iterator&>(mIt).done();
-        }
-    };
+    
+    /* various ways to access the rectangle list */
+    
+    typedef Rect const* const_iterator;
+    
+            const_iterator begin() const;
+            const_iterator end() const;
+
+    /* no user serviceable parts here... */
+            
+            size_t      getRects(Vector<Rect>& rectList) const;
+            Rect const* getArray(size_t* count) const;
 
-            size_t      rects(Vector<Rect>& rectList) const;
+            
+            // add a rectangle to the internal list. This rectangle must
+            // be sorted in Y and X and must not make the region invalid.
+            void        addRectUnchecked(int l, int t, int r, int b);
 
             // flatten/unflatten a region to/from a Parcel
             status_t    write(Parcel& parcel) const;
@@ -124,7 +130,33 @@ public:
     void        dump(const char* what, uint32_t flags=0) const;
 
 private:
-    SkRegion    mRegion;
+    class rasterizer;
+    friend class rasterizer;
+    
+    Region& operationSelf(const Rect& r, int op);
+    Region& operationSelf(const Region& r, int op);
+    Region& operationSelf(const Region& r, int dx, int dy, int op);
+    Region operation(const Rect& rhs, int op) const;
+    Region operation(const Region& rhs, int op) const;
+    Region operation(const Region& rhs, int dx, int dy, int op) const;
+
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Region& rhs, int dx, int dy);
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Rect& rhs, int dx, int dy);
+
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Region& rhs);
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Rect& rhs);
+
+    static void translate(Region& reg, int dx, int dy);
+    static void translate(Region& dst, const Region& reg, int dx, int dy);
+
+    static bool validate(const Region& reg, const char* name);
+    
+    Rect            mBounds;
+    Vector<Rect>    mStorage;
 };
 
 
@@ -158,16 +190,23 @@ Region& Region::operator += (const Point& pt) {
 // ---------------------------------------------------------------------------
 
 struct region_iterator : public copybit_region_t {
-    region_iterator(const Region& region) : i(region) {
+    region_iterator(const Region& region)
+        : b(region.begin()), e(region.end()) {
         this->next = iterate;
     }
 private:
     static int iterate(copybit_region_t const * self, copybit_rect_t* rect) {
-        return static_cast<const region_iterator*>(self)
-        ->i.iterate(reinterpret_cast<Rect*>(rect));
+        region_iterator const* me = static_cast<region_iterator const*>(self);
+        if (me->b != me->e) {
+            *reinterpret_cast<Rect*>(rect) = *me->b++;
+            return 1;
+        }
+        return 0;
     }
-    mutable Region::iterator i;
+    mutable Region::const_iterator b;
+    Region::const_iterator const e;
 };
+
 // ---------------------------------------------------------------------------
 }; // namespace android
 
diff --git a/libs/surfaceflinger/LayerBase.cpp b/libs/surfaceflinger/LayerBase.cpp
index cc9c586..4547a83 100644
--- a/libs/surfaceflinger/LayerBase.cpp
+++ b/libs/surfaceflinger/LayerBase.cpp
@@ -289,8 +289,9 @@ void LayerBase::invalidate()
 
 void LayerBase::drawRegion(const Region& reg) const
 {
-    Region::iterator iterator(reg);
-    if (iterator) {
+    Region::const_iterator it = reg.begin();
+    Region::const_iterator const end = reg.end();
+    if (it != end) {
         Rect r;
         const DisplayHardware& hw(graphicPlane(0).displayHardware());
         const int32_t fbWidth  = hw.getWidth();
@@ -298,7 +299,8 @@ void LayerBase::drawRegion(const Region& reg) const
         const GLshort vertices[][2] = { { 0, 0 }, { fbWidth, 0 }, 
                 { fbWidth, fbHeight }, { 0, fbHeight }  };
         glVertexPointer(2, GL_SHORT, 0, vertices);
-        while (iterator.iterate(&r)) {
+        while (it != end) {
+            const Rect& r = *it++;
             const GLint sy = fbHeight - (r.top + r.height());
             glScissor(r.left, sy, r.width(), r.height());
             glDrawArrays(GL_TRIANGLE_FAN, 0, 4); 
@@ -363,12 +365,14 @@ void LayerBase::clearWithOpenGL(const Region& clip) const
     glDisable(GL_TEXTURE_2D);
     glDisable(GL_BLEND);
     glDisable(GL_DITHER);
-    Rect r;
-    Region::iterator iterator(clip);
-    if (iterator) {
+
+    Region::const_iterator it = clip.begin();
+    Region::const_iterator const end = clip.end();
+    if (it != end) {
         glEnable(GL_SCISSOR_TEST);
         glVertexPointer(2, GL_FIXED, 0, mVertices);
-        while (iterator.iterate(&r)) {
+        while (it != end) {
+            const Rect& r = *it++;
             const GLint sy = fbHeight - (r.top + r.height());
             glScissor(r.left, sy, r.width(), r.height());
             glDrawArrays(GL_TRIANGLE_FAN, 0, 4); 
@@ -434,8 +438,9 @@ void LayerBase::drawWithOpenGL(const Region& clip,
             || !(mFlags & DisplayHardware::DRAW_TEXTURE_EXTENSION) )) 
     {
         //StopWatch watch("GL transformed");
-        Region::iterator iterator(clip);
-        if (iterator) {
+        Region::const_iterator it = clip.begin();
+        Region::const_iterator const end = clip.end();
+        if (it != end) {
             // always use high-quality filtering with fast configurations
             bool fast = !(mFlags & DisplayHardware::SLOW_CONFIG);
             if (!fast && s.flags & ISurfaceComposer::eLayerFilter) {
@@ -474,8 +479,8 @@ void LayerBase::drawWithOpenGL(const Region& clip,
             glVertexPointer(2, GL_FIXED, 0, mVertices);
             glTexCoordPointer(2, GL_FIXED, 0, texCoords);
 
-            Rect r;
-            while (iterator.iterate(&r)) {
+            while (it != end) {
+                const Rect& r = *it++;
                 const GLint sy = fbHeight - (r.top + r.height());
                 glScissor(r.left, sy, r.width(), r.height());
                 glDrawArrays(GL_TRIANGLE_FAN, 0, 4); 
@@ -488,15 +493,16 @@ void LayerBase::drawWithOpenGL(const Region& clip,
             glDisableClientState(GL_TEXTURE_COORD_ARRAY);
         }
     } else {
-        Region::iterator iterator(clip);
-        if (iterator) {
-            Rect r;
+        Region::const_iterator it = clip.begin();
+        Region::const_iterator const end = clip.end();
+        if (it != end) {
             GLint crop[4] = { 0, height, width, -height };
             glTexParameteriv(GL_TEXTURE_2D, GL_TEXTURE_CROP_RECT_OES, crop);
             int x = tx();
             int y = ty();
             y = fbHeight - (y + height);
-            while (iterator.iterate(&r)) {
+            while (it != end) {
+                const Rect& r = *it++;
                 const GLint sy = fbHeight - (r.top + r.height());
                 glScissor(r.left, sy, r.width(), r.height());
                 glDrawTexiOES(x, y, 0, width, height);
diff --git a/libs/surfaceflinger/LayerBlur.cpp b/libs/surfaceflinger/LayerBlur.cpp
index cac3cf1..3d22e3a 100644
--- a/libs/surfaceflinger/LayerBlur.cpp
+++ b/libs/surfaceflinger/LayerBlur.cpp
@@ -136,8 +136,9 @@ void LayerBlur::onDraw(const Region& clip) const
         glGenTextures(1, &mTextureName);
     }
 
-    Region::iterator iterator(clip);
-    if (iterator) {
+    Region::const_iterator it = clip.begin();
+    Region::const_iterator const end = clip.end();
+    if (it != end) {
         glEnable(GL_TEXTURE_2D);
         glBindTexture(GL_TEXTURE_2D, mTextureName);
     
@@ -198,27 +199,25 @@ void LayerBlur::onDraw(const Region& clip) const
             glEnableClientState(GL_TEXTURE_COORD_ARRAY);
             glVertexPointer(2, GL_FIXED, 0, mVertices);
             glTexCoordPointer(2, GL_FIXED, 0, mVertices);
-            Rect r;
-            while (iterator.iterate(&r)) {
+            while (it != end) {
+                const Rect& r = *it++;
                 const GLint sy = fbHeight - (r.top + r.height());
                 glScissor(r.left, sy, r.width(), r.height());
                 glDrawArrays(GL_TRIANGLE_FAN, 0, 4); 
             }       
         } else {
-            Region::iterator iterator(clip);
-            if (iterator) {
-                // NOTE: this is marginally faster with the software gl, because
-                // glReadPixels() reads the fb bottom-to-top, however we'll
-                // skip all the jaccobian computations.
-                Rect r;
-                GLint crop[4] = { 0, 0, w, h };
-                glTexParameteriv(GL_TEXTURE_2D, GL_TEXTURE_CROP_RECT_OES, crop);
-                y = fbHeight - (y + h);
-                while (iterator.iterate(&r)) {
-                    const GLint sy = fbHeight - (r.top + r.height());
-                    glScissor(r.left, sy, r.width(), r.height());
-                    glDrawTexiOES(x, y, 0, w, h);
-                }
+            // NOTE: this is marginally faster with the software gl, because
+            // glReadPixels() reads the fb bottom-to-top, however we'll
+            // skip all the jaccobian computations.
+            Rect r;
+            GLint crop[4] = { 0, 0, w, h };
+            glTexParameteriv(GL_TEXTURE_2D, GL_TEXTURE_CROP_RECT_OES, crop);
+            y = fbHeight - (y + h);
+            while (it != end) {
+                const Rect& r = *it++;
+                const GLint sy = fbHeight - (r.top + r.height());
+                glScissor(r.left, sy, r.width(), r.height());
+                glDrawTexiOES(x, y, 0, w, h);
             }
         }
     }
diff --git a/libs/surfaceflinger/LayerDim.cpp b/libs/surfaceflinger/LayerDim.cpp
index f2519c4..c1e8ad6 100644
--- a/libs/surfaceflinger/LayerDim.cpp
+++ b/libs/surfaceflinger/LayerDim.cpp
@@ -52,8 +52,9 @@ void LayerDim::onDraw(const Region& clip) const
     // FIXME: on some h/w (like msm7K, it will be faster to use a texture)
     
     const State& s(drawingState());
-    Region::iterator iterator(clip);
-    if (s.alpha>0 && iterator) {
+    Region::const_iterator it = clip.begin();
+    Region::const_iterator const end = clip.end();
+    if (s.alpha>0 && (it != end)) {
         const DisplayHardware& hw(graphicPlane(0).displayHardware());
         const GGLfixed alpha = (s.alpha << 16)/255;
         const uint32_t fbHeight = hw.getHeight();
@@ -63,8 +64,8 @@ void LayerDim::onDraw(const Region& clip) const
         glBlendFunc(GL_ONE, GL_ONE_MINUS_SRC_ALPHA);
         glColor4x(0, 0, 0, alpha);
         glVertexPointer(2, GL_FIXED, 0, mVertices);
-        Rect r;
-        while (iterator.iterate(&r)) {
+        while (it != end) {
+            const Rect& r = *it++;
             const GLint sy = fbHeight - (r.top + r.height());
             glScissor(r.left, sy, r.width(), r.height());
             glDrawArrays(GL_TRIANGLE_FAN, 0, 4); 
diff --git a/libs/surfaceflinger/SurfaceFlinger.cpp b/libs/surfaceflinger/SurfaceFlinger.cpp
index b8c246c..e0728eb 100644
--- a/libs/surfaceflinger/SurfaceFlinger.cpp
+++ b/libs/surfaceflinger/SurfaceFlinger.cpp
@@ -913,9 +913,10 @@ void SurfaceFlinger::debugFlashRegions()
         glColor4x(0x10000, 0x10000, 0, 0x10000);
     }
 
-    Rect r;
-    Region::iterator iterator(mDirtyRegion);
-    while (iterator.iterate(&r)) {
+    Region::const_iterator it = mDirtyRegion.begin();
+    Region::const_iterator const end = mDirtyRegion.end();
+    while (it != end) {
+        const Rect& r = *it++;
         GLfloat vertices[][2] = {
                 { r.left,  r.top },
                 { r.left,  r.bottom },
@@ -951,9 +952,10 @@ void SurfaceFlinger::drawWormhole() const
 
     if (LIKELY(!mDebugBackground)) {
         glClearColorx(0,0,0,0);
-        Rect r;
-        Region::iterator iterator(region);
-        while (iterator.iterate(&r)) {
+        Region::const_iterator it = region.begin();
+        Region::const_iterator const end = region.end();
+        while (it != end) {
+            const Rect& r = *it++;
             const GLint sy = height - (r.top + r.height());
             glScissor(r.left, sy, r.width(), r.height());
             glClear(GL_COLOR_BUFFER_BIT);
@@ -971,9 +973,10 @@ void SurfaceFlinger::drawWormhole() const
         glMatrixMode(GL_TEXTURE);
         glLoadIdentity();
         glScalef(width*(1.0f/32.0f), height*(1.0f/32.0f), 1);
-        Rect r;
-        Region::iterator iterator(region);
-        while (iterator.iterate(&r)) {
+        Region::const_iterator it = region.begin();
+        Region::const_iterator const end = region.end();
+        while (it != end) {
+            const Rect& r = *it++;
             const GLint sy = height - (r.top + r.height());
             glScissor(r.left, sy, r.width(), r.height());
             glDrawArrays(GL_TRIANGLE_FAN, 0, 4);
diff --git a/libs/surfaceflinger/Transform.cpp b/libs/surfaceflinger/Transform.cpp
index e8b0f45..1501536 100644
--- a/libs/surfaceflinger/Transform.cpp
+++ b/libs/surfaceflinger/Transform.cpp
@@ -177,10 +177,10 @@ Region Transform::transform(const Region& reg) const
     Region out;
     if (UNLIKELY(transformed())) {
         if (LIKELY(preserveRects())) {
-            Rect r;
-            Region::iterator iterator(reg);
-            while (iterator.iterate(&r)) {
-                out.orSelf(transform(r));
+            Region::const_iterator it = reg.begin();
+            Region::const_iterator const end = reg.end();
+            while (it != end) {
+                out.orSelf(transform(*it++));
             }
         } else {
             out.set(transform(reg.bounds()));
diff --git a/libs/ui/Android.mk b/libs/ui/Android.mk
index d44d2f9..7c367ef 100644
--- a/libs/ui/Android.mk
+++ b/libs/ui/Android.mk
@@ -29,7 +29,6 @@ LOCAL_SRC_FILES:= \
 	Time.cpp
 
 LOCAL_SHARED_LIBRARIES := \
-	libcorecg \
 	libcutils \
 	libutils \
 	libpixelflinger \
diff --git a/libs/ui/Region.cpp b/libs/ui/Region.cpp
index 30da911..065ed54 100644
--- a/libs/ui/Region.cpp
+++ b/libs/ui/Region.cpp
@@ -16,302 +16,653 @@
 
 #define LOG_TAG "Region"
 
-#include <stdio.h>
-#include <utils/Atomic.h>
-#include <utils/Debug.h>
+#include <utils/Log.h>
 #include <utils/String8.h>
+
+#include <ui/Rect.h>
 #include <ui/Region.h>
+#include <ui/Point.h>
+
+#include <private/ui/RegionHelper.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<Rect>::op_nand,
+    op_and  = region_operator<Rect>::op_and,
+    op_or   = region_operator<Rect>::op_or,
+    op_xor  = region_operator<Rect>::op_xor
+};
 
 // ----------------------------------------------------------------------------
 
 Region::Region()
+    : mBounds(0,0)
 {
 }
 
 Region::Region(const Region& rhs)
-    : mRegion(rhs.mRegion)
-{
-}
-
-Region::Region(const SkRegion& rhs)
-    : mRegion(rhs)
-{
-}
-
-Region::~Region()
+    : mBounds(rhs.mBounds), mStorage(rhs.mStorage)
 {
 }
 
 Region::Region(const Rect& rhs)
+    : mBounds(rhs)
 {
-    set(rhs);
 }
 
 Region::Region(const Parcel& parcel)
 {
-    read(parcel);
+    status_t err = read(parcel);
+    LOGE_IF(err<0, "error %s reading Region from parcel", strerror(err));
 }
 
 Region::Region(const void* buffer)
 {
-    read(buffer);
-}
-
-Region& Region::operator = (const Region& rhs)
-{
-    mRegion = rhs.mRegion;
-    return *this;
+    status_t err = read(buffer);
+    LOGE_IF(err<0, "error %s reading Region from parcel", strerror(err));
 }
 
-const SkRegion& Region::toSkRegion() const
+Region::~Region()
 {
-    return mRegion;
 }
 
-Rect Region::bounds() const
+Region& Region::operator = (const Region& rhs)
 {
-    const SkIRect& b(mRegion.getBounds());
-    return Rect(b.fLeft, b.fTop, b.fRight, b.fBottom);
+#if VALIDATE_REGIONS
+    validate(rhs, "operator=");
+#endif
+    mBounds = rhs.mBounds;
+    mStorage = rhs.mStorage;
+    return *this;
 }
 
 void Region::clear()
 {
-    mRegion.setEmpty();
+    mBounds.clear();
+    mStorage.clear();
 }
 
 void Region::set(const Rect& r)
 {
-    SkIRect ir;
-    ir.set(r.left, r.top, r.right, r.bottom);
-    mRegion.setRect(ir);
+    mBounds = r;
+    mStorage.clear();
 }
 
 void Region::set(uint32_t w, uint32_t h)
 {
-    SkIRect ir;
-    ir.set(0, 0, w, h);
-    mRegion.setRect(ir);
+    mBounds = Rect(int(w), int(h));
+    mStorage.clear();
 }
 
 // ----------------------------------------------------------------------------
 
-Region& Region::orSelf(const Rect& r)
+void Region::addRectUnchecked(int l, int t, int r, int b)
 {
-    SkIRect ir;
-    ir.set(r.left, r.top, r.right, r.bottom);
-    mRegion.op(ir, SkRegion::kUnion_Op);
-    return *this;
+    mStorage.add(Rect(l,t,r,b));
+#if VALIDATE_REGIONS
+    validate(*this, "addRectUnchecked");
+#endif
 }
 
-Region& Region::andSelf(const Rect& r)
-{
-    SkIRect ir;
-    ir.set(r.left, r.top, r.right, r.bottom);
-    mRegion.op(ir, SkRegion::kIntersect_Op);
+// ----------------------------------------------------------------------------
+
+Region& Region::orSelf(const Rect& r) {
+    return operationSelf(r, op_or);
+}
+Region& Region::andSelf(const Rect& r) {
+    return operationSelf(r, op_and);
+}
+Region& Region::subtractSelf(const Rect& r) {
+    return operationSelf(r, op_nand);
+}
+Region& Region::operationSelf(const Rect& r, int op) {
+    Region lhs(*this);
+    boolean_operation(op, *this, lhs, r);
     return *this;
 }
 
 // ----------------------------------------------------------------------------
 
 Region& Region::orSelf(const Region& rhs) {
-    mRegion.op(rhs.mRegion, SkRegion::kUnion_Op);
-    return *this;
+    return operationSelf(rhs, op_or);
 }
-
 Region& Region::andSelf(const Region& rhs) {
-    mRegion.op(rhs.mRegion, SkRegion::kIntersect_Op);
-    return *this;
+    return operationSelf(rhs, op_and);
 }
-
 Region& Region::subtractSelf(const Region& rhs) {
-    mRegion.op(rhs.mRegion, SkRegion::kDifference_Op);
+    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) mRegion.translate(x, y);
+    if (x|y) translate(*this, x, y);
     return *this;
 }
 
-Region Region::merge(const Region& rhs) const {
+// ----------------------------------------------------------------------------
+
+Region Region::merge(const Rect& rhs) const {
+    return operation(rhs, op_or);
+}
+Region Region::intersect(const Rect& rhs) const {
+    return operation(rhs, op_and);
+}
+Region Region::subtract(const Rect& rhs) const {
+    return operation(rhs, op_nand);
+}
+Region Region::operation(const Rect& rhs, int op) const {
     Region result;
-    result.mRegion.op(mRegion, rhs.mRegion, SkRegion::kUnion_Op);
+    boolean_operation(op, result, *this, rhs);
     return result;
 }
 
+// ----------------------------------------------------------------------------
+
+Region Region::merge(const Region& rhs) const {
+    return operation(rhs, op_or);
+}
 Region Region::intersect(const Region& rhs) const {
-    Region result;
-    result.mRegion.op(mRegion, rhs.mRegion, SkRegion::kIntersect_Op);
-    return result;
+    return operation(rhs, op_and);
 }
-
 Region Region::subtract(const Region& rhs) const {
+    return operation(rhs, op_nand);
+}
+Region Region::operation(const Region& rhs, int op) const {
     Region result;
-    result.mRegion.op(mRegion, rhs.mRegion, SkRegion::kDifference_Op);
+    boolean_operation(op, result, *this, rhs);
     return result;
 }
 
 Region Region::translate(int x, int y) const {
     Region result;
-    mRegion.translate(x, y, &result.mRegion);
+    translate(result, *this, x, y);
     return result;
 }
 
 // ----------------------------------------------------------------------------
 
 Region& Region::orSelf(const Region& rhs, int dx, int dy) {
-    SkRegion r(rhs.mRegion);
-    r.translate(dx, dy);
-    mRegion.op(r, SkRegion::kUnion_Op);
-    return *this;
+    return operationSelf(rhs, dx, dy, op_or);
 }
-
 Region& Region::andSelf(const Region& rhs, int dx, int dy) {
-    SkRegion r(rhs.mRegion);
-    r.translate(dx, dy);
-    mRegion.op(r, SkRegion::kIntersect_Op);
-    return *this;
+    return operationSelf(rhs, dx, dy, op_and);
 }
-
 Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
-    SkRegion r(rhs.mRegion);
-    r.translate(dx, dy);
-    mRegion.op(r, SkRegion::kDifference_Op);
+    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;
 }
 
+// ----------------------------------------------------------------------------
+
 Region Region::merge(const Region& rhs, int dx, int dy) const {
-    Region result;
-    SkRegion r(rhs.mRegion);
-    r.translate(dx, dy);
-    result.mRegion.op(mRegion, r, SkRegion::kUnion_Op);
-    return result;
+    return operation(rhs, dx, dy, op_or);
 }
-
 Region Region::intersect(const Region& rhs, int dx, int dy) const {
-    Region result;
-    SkRegion r(rhs.mRegion);
-    r.translate(dx, dy);
-    result.mRegion.op(mRegion, r, SkRegion::kIntersect_Op);
-    return result;
+    return operation(rhs, dx, dy, op_and);
 }
-
 Region Region::subtract(const Region& rhs, int dx, int dy) const {
+    return operation(rhs, dx, dy, op_nand);
+}
+Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
     Region result;
-    SkRegion r(rhs.mRegion);
-    r.translate(dx, dy);
-    result.mRegion.op(mRegion, r, SkRegion::kDifference_Op);
+    boolean_operation(op, result, *this, rhs, dx, dy);
     return result;
 }
 
 // ----------------------------------------------------------------------------
 
-Region::iterator::iterator(const Region& r)
-    : mIt(r.mRegion)
+// This is our region rasterizer, which merges rects and spans together
+// to obtain an optimal region.
+class Region::rasterizer : public region_operator<Rect>::region_rasterizer 
+{
+    Rect& bounds;
+    Vector<Rect>& storage;
+    Rect* head;
+    Rect* tail;
+    Vector<Rect> span;
+    Rect* cur;
+public:
+    rasterizer(Region& reg) 
+        : bounds(reg.mBounds), storage(reg.mStorage), head(), tail(), cur() {
+        bounds.top = bounds.bottom = 0;
+        bounds.left   = INT_MAX;
+        bounds.right  = INT_MIN;
+        storage.clear();
+    }
+
+    ~rasterizer() {
+        if (span.size()) {
+            flushSpan();
+        }
+        if (storage.size()) {
+            bounds.top = storage.itemAt(0).top;
+            bounds.bottom = storage.top().bottom;
+            if (storage.size() == 1) {
+                storage.clear();
+            }
+        } else {
+            bounds.left  = 0;
+            bounds.right = 0;
+        }
+    }
+    
+    virtual void operator()(const Rect& rect) {
+        //LOGD(">>> %3d, %3d, %3d, %3d", 
+        //        rect.left, rect.top, rect.right, rect.bottom);
+        if (span.size()) {
+            if (cur->top != rect.top) {
+                flushSpan();
+            } else if (cur->right == rect.left) {
+                cur->right = rect.right;
+                return;
+            }
+        }
+        span.add(rect);
+        cur = span.editArray() + (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())) {
+            Rect const* p = cur;
+            Rect const* q = head;
+            if (p->top == q->bottom) {
+                merge = true;
+                while (q != tail) {
+                    if ((p->left != q->left) || (p->right != q->right)) {
+                        merge = false;
+                        break;
+                    }
+                    p++, q++;
+                }
+            }
+        }
+        if (merge) {
+            const int bottom = span[0].bottom;
+            Rect* r = head;
+            while (r != tail) {
+                r->bottom = bottom;
+                r++;
+            }
+        } else {
+            bounds.left = min(span.itemAt(0).left, bounds.left);
+            bounds.right = max(span.top().right, bounds.right);
+            storage.appendVector(span);
+            tail = storage.editArray() + storage.size();
+            head = tail - span.size();
+        }
+        span.clear();
+    }
+};
+
+bool Region::validate(const Region& reg, const char* name)
 {
+    bool result = true;
+    const_iterator cur = reg.begin();
+    const_iterator const tail = reg.end();
+    const_iterator prev = cur++;
+    Rect b(*prev);
+    while (cur != tail) {
+        b.left   = b.left   < cur->left   ? b.left   : cur->left;
+        b.top    = b.top    < cur->top    ? b.top    : cur->top;
+        b.right  = b.right  > cur->right  ? b.right  : cur->right;
+        b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom;
+        if (cur->top == prev->top) {
+            if (cur->bottom != prev->bottom) {
+                LOGE("%s: invalid span %p", name, cur);
+                result = false;
+            } else if (cur->left < prev->right) {
+                LOGE("%s: spans overlap horizontally prev=%p, cur=%p",
+                        name, prev, cur);
+                result = false;
+            }
+        } else if (cur->top < prev->bottom) {
+            LOGE("%s: spans overlap vertically prev=%p, cur=%p",
+                    name, prev, cur);
+            result = false;
+        }
+        prev = cur;
+        cur++;
+    }
+    if (b != reg.getBounds()) {
+        result = false;
+        LOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
+                b.left, b.top, b.right, b.bottom,
+                reg.getBounds().left, reg.getBounds().top, 
+                reg.getBounds().right, reg.getBounds().bottom);
+    }
+    if (result == false) {
+        reg.dump(name);
+    }
+    return result;
 }
 
-int Region::iterator::iterate(Rect* rect)
+void Region::boolean_operation(int op, Region& dst,
+        const Region& lhs,
+        const Region& rhs, int dx, int dy)
 {
-    if (mIt.done())
-        return 0;
-    const SkIRect& r(mIt.rect());
-    rect->left  = r.fLeft;
-    rect->top   = r.fTop;
-    rect->right = r.fRight;
-    rect->bottom= r.fBottom;
-    mIt.next();
-    return 1;
+    size_t lhs_count;
+    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
+
+    size_t rhs_count;
+    Rect const * const rhs_rects = rhs.getArray(&rhs_count);
+
+    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
+    region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
+    region_operator<Rect> 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].left   + dx,
+                lhs_rects[i].top    + dy,
+                lhs_rects[i].right  + dx,
+                lhs_rects[i].bottom + dy,
+                SkRegion::kUnion_Op);
+    
+    for (size_t i=0 ; i<rhs_count ; i++)
+        sk_rhs.op(
+                rhs_rects[i].left   + dx,
+                rhs_rects[i].top    + dy,
+                rhs_rects[i].right  + dx,
+                rhs_rects[i].bottom + 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_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->left != it.rect().fLeft ||     
+                    head->top != it.rect().fTop ||     
+                    head->right != it.rect().fRight ||     
+                    head->bottom != it.rect().fBottom
+            ) {
+                same = false;
+                break;
+            }
+        } else {
+            same = false;
+            break;
+        }
+        head++;
+        it.next();
+    }
+    
+    if (head != tail) {
+        same = false;
+    }
+    
+    if(!same) {
+        LOGD("---\nregion boolean %s failed", name);
+        lhs.dump("lhs");
+        rhs.dump("rhs");
+        dst.dump("dst");
+        LOGD("should be");
+        SkRegion::Iterator it(sk_dst);
+        while (!it.done()) {
+            LOGD("    [%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 Rect& rhs, int dx, int dy)
+{
+#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
+    boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
+#else
+    size_t lhs_count;
+    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
+
+    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
+    region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
+    region_operator<Rect> operation(op, lhs_region, rhs_region);
+    { // scope for rasterizer (dtor has side effects)
+        rasterizer r(dst);
+        operation(r);
+    }
 
-// we write a 4byte size ahead of the actual region, so we know how much we'll need for reading
+#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 Rect& 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.translate(dx, dy);
+        size_t count = reg.mStorage.size();
+        Rect* rects = reg.mStorage.editArray();
+        while (count) {
+            rects->translate(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);
+}
+
+// ----------------------------------------------------------------------------
 
 status_t Region::write(Parcel& parcel) const
 {
-    int32_t size = mRegion.flatten(NULL);
-    parcel.writeInt32(size);
-    mRegion.flatten(parcel.writeInplace(size));
+#if VALIDATE_REGIONS
+    validate(*this, "write(Parcel)");
+#endif
+    status_t err;
+    const size_t count = mStorage.size();
+    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
+    void* buffer = parcel.writeInplace(sizeNeeded);
+    if (!buffer) return NO_MEMORY;
+    ssize_t written = Region::write(buffer, sizeNeeded);
+    if (written < 0) return status_t(written);
     return NO_ERROR;
 }
 
 status_t Region::read(const Parcel& parcel)
 {
-    size_t size = parcel.readInt32();
-    mRegion.unflatten(parcel.readInplace(size));
+    void const* buffer = parcel.readInplace(sizeof(int32_t));
+    if (!buffer) return NO_MEMORY;
+    const size_t count = *static_cast<int32_t const *>(buffer);
+    void const* dummy = parcel.readInplace((1+count)*sizeof(Rect));
+    if (!dummy) return NO_MEMORY;
+    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
+    const ssize_t read = Region::read(buffer);
+    if (read < 0) return status_t(read);
+#if VALIDATE_REGIONS
+    validate(*this, "read(Parcel)");
+#endif
     return NO_ERROR;
 }
 
 ssize_t Region::write(void* buffer, size_t size) const
 {
-    size_t sizeNeeded = mRegion.flatten(NULL);
+#if VALIDATE_REGIONS
+    validate(*this, "write(buffer)");
+#endif
+    const size_t count = mStorage.size();
+    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
     if (sizeNeeded > size) return NO_MEMORY;
-    return mRegion.flatten(buffer);
+    int32_t* const p = static_cast<int32_t*>(buffer); 
+    *p = count;
+    memcpy(p+1, &mBounds, sizeof(Rect));
+    if (count) {
+        memcpy(p+5, mStorage.array(), count*sizeof(Rect));
+    }
+    return ssize_t(sizeNeeded);
 }
 
 ssize_t Region::read(const void* buffer)
 {
-    return mRegion.unflatten(buffer);
+    int32_t const* const p = static_cast<int32_t const*>(buffer); 
+    const size_t count = *p;
+    memcpy(&mBounds, p+1, sizeof(Rect));
+    mStorage.clear();
+    if (count) {
+        mStorage.insertAt(0, count);
+        memcpy(mStorage.editArray(), p+5, count*sizeof(Rect));
+    }
+#if VALIDATE_REGIONS
+    validate(*this, "read(buffer)");
+#endif
+    return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect));
 }
 
 ssize_t Region::writeEmpty(void* buffer, size_t size)
 {
-    if (size < 4) return NO_MEMORY;
-    // this needs to stay in sync with SkRegion
-    *static_cast<int32_t*>(buffer) = -1;
-    return 4;
+    const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect);
+    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)
 {
-    // this needs to stay in sync with SkRegion
-    return *static_cast<int32_t*>(buffer) == -1;
+    int32_t const* const p = static_cast<int32_t const*>(buffer); 
+    Rect const* const b = reinterpret_cast<Rect const *>(p+1);
+    return b->isEmpty();
+}
+
+// ----------------------------------------------------------------------------
+
+Region::const_iterator Region::begin() const {
+    return isRect() ? &mBounds : mStorage.array();
+}
+
+Region::const_iterator Region::end() const {
+    return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size());
+}
+
+Rect 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::rects(Vector<Rect>& rectList) const
+size_t Region::getRects(Vector<Rect>& rectList) const
 {
-    rectList.clear();
-    if (!isEmpty()) {
-        SkRegion::Iterator iterator(mRegion);
-        while( !iterator.done() ) {
-            const SkIRect& ir(iterator.rect());
-            rectList.push(Rect(ir.fLeft, ir.fTop, ir.fRight, ir.fBottom));
-            iterator.next();
-        }
+    rectList = mStorage;
+    if (rectList.isEmpty()) {
+        rectList.clear();
+        rectList.add(mBounds);
     }
     return rectList.size();
 }
 
+// ----------------------------------------------------------------------------
+
 void Region::dump(String8& out, const char* what, uint32_t flags) const
 {
     (void)flags;
-    Vector<Rect> r;
-    rects(r);
-    
+    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, r.size());
+
+    snprintf(buffer, SIZE, "  Region %s (this=%p, count=%d)\n",
+            what, this, tail-head);
     out.append(buffer);
-    for (size_t i=0 ; i<r.size() ; i++) {
+    while (head != tail) {
         snprintf(buffer, SIZE, "    [%3d, %3d, %3d, %3d]\n",
-            r[i].left, r[i].top,r[i].right,r[i].bottom);
+                head->left, head->top, head->right, head->bottom);
         out.append(buffer);
+        head++;
     }
 }
 
 void Region::dump(const char* what, uint32_t flags) const
 {
     (void)flags;
-    Vector<Rect> r;
-    rects(r);
-    LOGD("  Region %s (this=%p, count=%d)\n", what, this, r.size());
-    for (size_t i=0 ; i<r.size() ; i++) {
+    const_iterator head = begin();
+    const_iterator const tail = end();
+    LOGD("  Region %s (this=%p, count=%d)\n", what, this, tail-head);
+    while (head != tail) {
         LOGD("    [%3d, %3d, %3d, %3d]\n",
-            r[i].left, r[i].top,r[i].right,r[i].bottom);
+                head->left, head->top, head->right, head->bottom);
+        head++;
     }
 }
 
diff --git a/libs/ui/Surface.cpp b/libs/ui/Surface.cpp
index 6437619..6db30c3 100644
--- a/libs/ui/Surface.cpp
+++ b/libs/ui/Surface.cpp
@@ -125,15 +125,17 @@ static void copyBlt(
     uint8_t* dst_bits;
     dst->lock(GRALLOC_USAGE_SW_WRITE_OFTEN, reg.bounds(), (void**)&dst_bits);
     
-    Region::iterator iterator(reg);
-    if (iterator) {
+    size_t c;
+    Rect const* const rects = reg.getArray(&c);
+    
+    if (c) {
         // NOTE: dst and src must be the same format
-        Rect r;
         const size_t bpp = bytesPerPixel(src->format);
         const size_t dbpr = dst->stride * bpp;
         const size_t sbpr = src->stride * bpp;
 
-        while (iterator.iterate(&r)) {
+        for (size_t i=0 ; i<c ; i++) {
+            const Rect& r = rects[i];
             ssize_t h = r.height();
             if (h <= 0) continue;
             size_t size = r.width() * bpp;
diff --git a/libs/ui/tests/Android.mk b/libs/ui/tests/Android.mk
new file mode 100644
index 0000000..6cc4a5a
--- /dev/null
+++ b/libs/ui/tests/Android.mk
@@ -0,0 +1,16 @@
+LOCAL_PATH:= $(call my-dir)
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES:= \
+	region.cpp
+
+LOCAL_SHARED_LIBRARIES := \
+	libcutils \
+	libutils \
+    libui
+
+LOCAL_MODULE:= test-region
+
+LOCAL_MODULE_TAGS := tests
+
+include $(BUILD_EXECUTABLE)
diff --git a/libs/ui/tests/region.cpp b/libs/ui/tests/region.cpp
new file mode 100644
index 0000000..0deb2ba
--- /dev/null
+++ b/libs/ui/tests/region.cpp
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2009 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.
+ */
+
+#define LOG_TAG "Region"
+
+#include <stdio.h>
+#include <utils/Debug.h>
+#include <ui/Rect.h>
+#include <ui/Region.h>
+
+using namespace android;
+
+int main()
+{
+    Region reg0( Rect(  0, 0,  100, 100 ) );
+    Region reg1 = reg0;
+    Region reg2, reg3;
+    
+    reg0.dump("reg0");
+    reg1.dump("reg1");
+
+    reg0 = reg0 | reg0.translate(150, 0);
+    reg0.dump("reg0");
+    reg1.dump("reg1");
+
+    reg0 = reg0 | reg0.translate(300, 0);
+    reg0.dump("reg0");
+    reg1.dump("reg1");
+
+    //reg2 = reg0 | reg0.translate(0, 100);
+    //reg0.dump("reg0");
+    //reg1.dump("reg1");
+    //reg2.dump("reg2");
+
+    //reg3 = reg0 | reg0.translate(0, 150);
+    //reg0.dump("reg0");
+    //reg1.dump("reg1");
+    //reg2.dump("reg2");
+    //reg3.dump("reg3");
+
+    LOGD("---");
+    reg2 = reg0 | reg0.translate(100, 0);
+    reg0.dump("reg0");
+    reg1.dump("reg1");
+    reg2.dump("reg2");
+    
+    return 0;
+}
+