Region.cpp revision 2401ead70099c982796ecc3ec63ec8a5570948fc 
1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#define LOG_TAG "Region"
18
19#include <limits.h>
20
21#include <utils/Log.h>
22#include <utils/String8.h>
23
24#include <ui/Rect.h>
25#include <ui/Region.h>
26#include <ui/Point.h>
27
28#include <private/ui/RegionHelper.h>
29
30// ----------------------------------------------------------------------------
31#define VALIDATE_REGIONS        (false)
32#define VALIDATE_WITH_CORECG    (false)
33// ----------------------------------------------------------------------------
34
35#if VALIDATE_WITH_CORECG
36#include <core/SkRegion.h>
37#endif
38
39namespace android {
40// ----------------------------------------------------------------------------
41
42enum {
43    op_nand = region_operator<Rect>::op_nand,
44    op_and  = region_operator<Rect>::op_and,
45    op_or   = region_operator<Rect>::op_or,
46    op_xor  = region_operator<Rect>::op_xor
47};
48
49// ----------------------------------------------------------------------------
50
51Region::Region() {
52    mStorage.add(Rect(0,0));
53}
54
55Region::Region(const Region& rhs)
56    : mStorage(rhs.mStorage)
57{
58#if VALIDATE_REGIONS
59    validate(rhs, "rhs copy-ctor");
60#endif
61}
62
63Region::Region(const Rect& rhs) {
64    mStorage.add(rhs);
65}
66
67Region::~Region()
68{
69}
70
71Region& Region::operator = (const Region& rhs)
72{
73#if VALIDATE_REGIONS
74    validate(*this, "this->operator=");
75    validate(rhs, "rhs.operator=");
76#endif
77    mStorage = rhs.mStorage;
78    return *this;
79}
80
81Region& Region::makeBoundsSelf()
82{
83    if (mStorage.size() >= 2) {
84        const Rect bounds(getBounds());
85        mStorage.clear();
86        mStorage.add(bounds);
87    }
88    return *this;
89}
90
91void Region::clear()
92{
93    mStorage.clear();
94    mStorage.add(Rect(0,0));
95}
96
97void Region::set(const Rect& r)
98{
99    mStorage.clear();
100    mStorage.add(r);
101}
102
103void Region::set(uint32_t w, uint32_t h)
104{
105    mStorage.clear();
106    mStorage.add(Rect(w,h));
107}
108
109// ----------------------------------------------------------------------------
110
111void Region::addRectUnchecked(int l, int t, int r, int b)
112{
113    Rect rect(l,t,r,b);
114    size_t where = mStorage.size() - 1;
115    mStorage.insertAt(rect, where, 1);
116
117#if VALIDATE_REGIONS
118    validate(*this, "addRectUnchecked");
119#endif
120}
121
122// ----------------------------------------------------------------------------
123
124Region& Region::orSelf(const Rect& r) {
125    return operationSelf(r, op_or);
126}
127Region& Region::xorSelf(const Rect& r) {
128    return operationSelf(r, op_xor);
129}
130Region& Region::andSelf(const Rect& r) {
131    return operationSelf(r, op_and);
132}
133Region& Region::subtractSelf(const Rect& r) {
134    return operationSelf(r, op_nand);
135}
136Region& Region::operationSelf(const Rect& r, int op) {
137    Region lhs(*this);
138    boolean_operation(op, *this, lhs, r);
139    return *this;
140}
141
142// ----------------------------------------------------------------------------
143
144Region& Region::orSelf(const Region& rhs) {
145    return operationSelf(rhs, op_or);
146}
147Region& Region::xorSelf(const Region& rhs) {
148    return operationSelf(rhs, op_xor);
149}
150Region& Region::andSelf(const Region& rhs) {
151    return operationSelf(rhs, op_and);
152}
153Region& Region::subtractSelf(const Region& rhs) {
154    return operationSelf(rhs, op_nand);
155}
156Region& Region::operationSelf(const Region& rhs, int op) {
157    Region lhs(*this);
158    boolean_operation(op, *this, lhs, rhs);
159    return *this;
160}
161
162Region& Region::translateSelf(int x, int y) {
163    if (x|y) translate(*this, x, y);
164    return *this;
165}
166
167// ----------------------------------------------------------------------------
168
169const Region Region::merge(const Rect& rhs) const {
170    return operation(rhs, op_or);
171}
172const Region Region::mergeExclusive(const Rect& rhs) const {
173    return operation(rhs, op_xor);
174}
175const Region Region::intersect(const Rect& rhs) const {
176    return operation(rhs, op_and);
177}
178const Region Region::subtract(const Rect& rhs) const {
179    return operation(rhs, op_nand);
180}
181const Region Region::operation(const Rect& rhs, int op) const {
182    Region result;
183    boolean_operation(op, result, *this, rhs);
184    return result;
185}
186
187// ----------------------------------------------------------------------------
188
189const Region Region::merge(const Region& rhs) const {
190    return operation(rhs, op_or);
191}
192const Region Region::mergeExclusive(const Region& rhs) const {
193    return operation(rhs, op_xor);
194}
195const Region Region::intersect(const Region& rhs) const {
196    return operation(rhs, op_and);
197}
198const Region Region::subtract(const Region& rhs) const {
199    return operation(rhs, op_nand);
200}
201const Region Region::operation(const Region& rhs, int op) const {
202    Region result;
203    boolean_operation(op, result, *this, rhs);
204    return result;
205}
206
207const Region Region::translate(int x, int y) const {
208    Region result;
209    translate(result, *this, x, y);
210    return result;
211}
212
213// ----------------------------------------------------------------------------
214
215Region& Region::orSelf(const Region& rhs, int dx, int dy) {
216    return operationSelf(rhs, dx, dy, op_or);
217}
218Region& Region::xorSelf(const Region& rhs, int dx, int dy) {
219    return operationSelf(rhs, dx, dy, op_xor);
220}
221Region& Region::andSelf(const Region& rhs, int dx, int dy) {
222    return operationSelf(rhs, dx, dy, op_and);
223}
224Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
225    return operationSelf(rhs, dx, dy, op_nand);
226}
227Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) {
228    Region lhs(*this);
229    boolean_operation(op, *this, lhs, rhs, dx, dy);
230    return *this;
231}
232
233// ----------------------------------------------------------------------------
234
235const Region Region::merge(const Region& rhs, int dx, int dy) const {
236    return operation(rhs, dx, dy, op_or);
237}
238const Region Region::mergeExclusive(const Region& rhs, int dx, int dy) const {
239    return operation(rhs, dx, dy, op_xor);
240}
241const Region Region::intersect(const Region& rhs, int dx, int dy) const {
242    return operation(rhs, dx, dy, op_and);
243}
244const Region Region::subtract(const Region& rhs, int dx, int dy) const {
245    return operation(rhs, dx, dy, op_nand);
246}
247const Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
248    Region result;
249    boolean_operation(op, result, *this, rhs, dx, dy);
250    return result;
251}
252
253// ----------------------------------------------------------------------------
254
255// This is our region rasterizer, which merges rects and spans together
256// to obtain an optimal region.
257class Region::rasterizer : public region_operator<Rect>::region_rasterizer
258{
259    Rect bounds;
260    Vector<Rect>& storage;
261    Rect* head;
262    Rect* tail;
263    Vector<Rect> span;
264    Rect* cur;
265public:
266    rasterizer(Region& reg)
267        : bounds(INT_MAX, 0, INT_MIN, 0), storage(reg.mStorage), head(), tail(), cur() {
268        storage.clear();
269    }
270
271    ~rasterizer() {
272        if (span.size()) {
273            flushSpan();
274        }
275        if (storage.size()) {
276            bounds.top = storage.itemAt(0).top;
277            bounds.bottom = storage.top().bottom;
278            if (storage.size() == 1) {
279                storage.clear();
280            }
281        } else {
282            bounds.left  = 0;
283            bounds.right = 0;
284        }
285        storage.add(bounds);
286    }
287
288    virtual void operator()(const Rect& rect) {
289        //ALOGD(">>> %3d, %3d, %3d, %3d",
290        //        rect.left, rect.top, rect.right, rect.bottom);
291        if (span.size()) {
292            if (cur->top != rect.top) {
293                flushSpan();
294            } else if (cur->right == rect.left) {
295                cur->right = rect.right;
296                return;
297            }
298        }
299        span.add(rect);
300        cur = span.editArray() + (span.size() - 1);
301    }
302private:
303    template<typename T>
304    static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
305    template<typename T>
306    static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
307    void flushSpan() {
308        bool merge = false;
309        if (tail-head == ssize_t(span.size())) {
310            Rect const* p = span.editArray();
311            Rect const* q = head;
312            if (p->top == q->bottom) {
313                merge = true;
314                while (q != tail) {
315                    if ((p->left != q->left) || (p->right != q->right)) {
316                        merge = false;
317                        break;
318                    }
319                    p++, q++;
320                }
321            }
322        }
323        if (merge) {
324            const int bottom = span[0].bottom;
325            Rect* r = head;
326            while (r != tail) {
327                r->bottom = bottom;
328                r++;
329            }
330        } else {
331            bounds.left = min(span.itemAt(0).left, bounds.left);
332            bounds.right = max(span.top().right, bounds.right);
333            storage.appendVector(span);
334            tail = storage.editArray() + storage.size();
335            head = tail - span.size();
336        }
337        span.clear();
338    }
339};
340
341bool Region::validate(const Region& reg, const char* name)
342{
343    bool result = true;
344    const_iterator cur = reg.begin();
345    const_iterator const tail = reg.end();
346    const_iterator prev = cur++;
347    Rect b(*prev);
348    while (cur != tail) {
349        b.left   = b.left   < cur->left   ? b.left   : cur->left;
350        b.top    = b.top    < cur->top    ? b.top    : cur->top;
351        b.right  = b.right  > cur->right  ? b.right  : cur->right;
352        b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom;
353        if (cur->top == prev->top) {
354            if (cur->bottom != prev->bottom) {
355                ALOGE("%s: invalid span %p", name, cur);
356                result = false;
357            } else if (cur->left < prev->right) {
358                ALOGE("%s: spans overlap horizontally prev=%p, cur=%p",
359                        name, prev, cur);
360                result = false;
361            }
362        } else if (cur->top < prev->bottom) {
363            ALOGE("%s: spans overlap vertically prev=%p, cur=%p",
364                    name, prev, cur);
365            result = false;
366        }
367        prev = cur;
368        cur++;
369    }
370    if (b != reg.getBounds()) {
371        result = false;
372        ALOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
373                b.left, b.top, b.right, b.bottom,
374                reg.getBounds().left, reg.getBounds().top,
375                reg.getBounds().right, reg.getBounds().bottom);
376    }
377    if (reg.mStorage.size() == 2) {
378        ALOGE("mStorage size is 2, which is never valid");
379    }
380    if (result == false) {
381        reg.dump(name);
382    }
383    return result;
384}
385
386void Region::boolean_operation(int op, Region& dst,
387        const Region& lhs,
388        const Region& rhs, int dx, int dy)
389{
390#if VALIDATE_REGIONS
391    validate(lhs, "boolean_operation (before): lhs");
392    validate(rhs, "boolean_operation (before): rhs");
393    validate(dst, "boolean_operation (before): dst");
394#endif
395
396    size_t lhs_count;
397    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
398
399    size_t rhs_count;
400    Rect const * const rhs_rects = rhs.getArray(&rhs_count);
401
402    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
403    region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
404    region_operator<Rect> operation(op, lhs_region, rhs_region);
405    { // scope for rasterizer (dtor has side effects)
406        rasterizer r(dst);
407        operation(r);
408    }
409
410#if VALIDATE_REGIONS
411    validate(lhs, "boolean_operation: lhs");
412    validate(rhs, "boolean_operation: rhs");
413    validate(dst, "boolean_operation: dst");
414#endif
415
416#if VALIDATE_WITH_CORECG
417    SkRegion sk_lhs;
418    SkRegion sk_rhs;
419    SkRegion sk_dst;
420
421    for (size_t i=0 ; i<lhs_count ; i++)
422        sk_lhs.op(
423                lhs_rects[i].left   + dx,
424                lhs_rects[i].top    + dy,
425                lhs_rects[i].right  + dx,
426                lhs_rects[i].bottom + dy,
427                SkRegion::kUnion_Op);
428
429    for (size_t i=0 ; i<rhs_count ; i++)
430        sk_rhs.op(
431                rhs_rects[i].left   + dx,
432                rhs_rects[i].top    + dy,
433                rhs_rects[i].right  + dx,
434                rhs_rects[i].bottom + dy,
435                SkRegion::kUnion_Op);
436
437    const char* name = "---";
438    SkRegion::Op sk_op;
439    switch (op) {
440        case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
441        case op_xor: sk_op = SkRegion::kUnion_XOR; name="XOR"; break;
442        case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
443        case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
444    }
445    sk_dst.op(sk_lhs, sk_rhs, sk_op);
446
447    if (sk_dst.isEmpty() && dst.isEmpty())
448        return;
449
450    bool same = true;
451    Region::const_iterator head = dst.begin();
452    Region::const_iterator const tail = dst.end();
453    SkRegion::Iterator it(sk_dst);
454    while (!it.done()) {
455        if (head != tail) {
456            if (
457                    head->left != it.rect().fLeft ||
458                    head->top != it.rect().fTop ||
459                    head->right != it.rect().fRight ||
460                    head->bottom != it.rect().fBottom
461            ) {
462                same = false;
463                break;
464            }
465        } else {
466            same = false;
467            break;
468        }
469        head++;
470        it.next();
471    }
472
473    if (head != tail) {
474        same = false;
475    }
476
477    if(!same) {
478        ALOGD("---\nregion boolean %s failed", name);
479        lhs.dump("lhs");
480        rhs.dump("rhs");
481        dst.dump("dst");
482        ALOGD("should be");
483        SkRegion::Iterator it(sk_dst);
484        while (!it.done()) {
485            ALOGD("    [%3d, %3d, %3d, %3d]",
486                it.rect().fLeft,
487                it.rect().fTop,
488                it.rect().fRight,
489                it.rect().fBottom);
490            it.next();
491        }
492    }
493#endif
494}
495
496void Region::boolean_operation(int op, Region& dst,
497        const Region& lhs,
498        const Rect& rhs, int dx, int dy)
499{
500    if (!rhs.isValid()) {
501        ALOGE("Region::boolean_operation(op=%d) invalid Rect={%d,%d,%d,%d}",
502                op, rhs.left, rhs.top, rhs.right, rhs.bottom);
503        return;
504    }
505
506#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
507    boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
508#else
509    size_t lhs_count;
510    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
511
512    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
513    region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
514    region_operator<Rect> operation(op, lhs_region, rhs_region);
515    { // scope for rasterizer (dtor has side effects)
516        rasterizer r(dst);
517        operation(r);
518    }
519
520#endif
521}
522
523void Region::boolean_operation(int op, Region& dst,
524        const Region& lhs, const Region& rhs)
525{
526    boolean_operation(op, dst, lhs, rhs, 0, 0);
527}
528
529void Region::boolean_operation(int op, Region& dst,
530        const Region& lhs, const Rect& rhs)
531{
532    boolean_operation(op, dst, lhs, rhs, 0, 0);
533}
534
535void Region::translate(Region& reg, int dx, int dy)
536{
537    if ((dx || dy) && !reg.isEmpty()) {
538#if VALIDATE_REGIONS
539        validate(reg, "translate (before)");
540#endif
541        size_t count = reg.mStorage.size();
542        Rect* rects = reg.mStorage.editArray();
543        while (count) {
544            rects->translate(dx, dy);
545            rects++;
546            count--;
547        }
548#if VALIDATE_REGIONS
549        validate(reg, "translate (after)");
550#endif
551    }
552}
553
554void Region::translate(Region& dst, const Region& reg, int dx, int dy)
555{
556    dst = reg;
557    translate(dst, dx, dy);
558}
559
560// ----------------------------------------------------------------------------
561
562size_t Region::getSize() const {
563    return mStorage.size() * sizeof(Rect);
564}
565
566status_t Region::flatten(void* buffer) const {
567    Rect* rects = reinterpret_cast<Rect*>(buffer);
568    memcpy(rects, mStorage.array(), mStorage.size() * sizeof(Rect));
569    return NO_ERROR;
570}
571
572status_t Region::unflatten(void const* buffer, size_t size) {
573    mStorage.clear();
574    if (size >= sizeof(Rect)) {
575        Rect const* rects = reinterpret_cast<Rect const*>(buffer);
576        size_t count = size / sizeof(Rect);
577        if (count > 0) {
578            ssize_t err = mStorage.insertAt(0, count);
579            if (err < 0) {
580                return status_t(err);
581            }
582            memcpy(mStorage.editArray(), rects, count*sizeof(Rect));
583        }
584    }
585#if VALIDATE_REGIONS
586    validate(*this, "Region::unflatten");
587#endif
588    return NO_ERROR;
589}
590
591// ----------------------------------------------------------------------------
592
593Region::const_iterator Region::begin() const {
594    return mStorage.array();
595}
596
597Region::const_iterator Region::end() const {
598    size_t numRects = isRect() ? 1 : mStorage.size() - 1;
599    return mStorage.array() + numRects;
600}
601
602Rect const* Region::getArray(size_t* count) const {
603    const_iterator const b(begin());
604    const_iterator const e(end());
605    if (count) *count = e-b;
606    return b;
607}
608
609SharedBuffer const* Region::getSharedBuffer(size_t* count) const {
610    // We can get to the SharedBuffer of a Vector<Rect> because Rect has
611    // a trivial destructor.
612    SharedBuffer const* sb = SharedBuffer::bufferFromData(mStorage.array());
613    if (count) {
614        size_t numRects = isRect() ? 1 : mStorage.size() - 1;
615        count[0] = numRects;
616    }
617    sb->acquire();
618    return sb;
619}
620
621// ----------------------------------------------------------------------------
622
623void Region::dump(String8& out, const char* what, uint32_t flags) const
624{
625    (void)flags;
626    const_iterator head = begin();
627    const_iterator const tail = end();
628
629    size_t SIZE = 256;
630    char buffer[SIZE];
631
632    snprintf(buffer, SIZE, "  Region %s (this=%p, count=%d)\n",
633            what, this, tail-head);
634    out.append(buffer);
635    while (head != tail) {
636        snprintf(buffer, SIZE, "    [%3d, %3d, %3d, %3d]\n",
637                head->left, head->top, head->right, head->bottom);
638        out.append(buffer);
639        head++;
640    }
641}
642
643void Region::dump(const char* what, uint32_t flags) const
644{
645    (void)flags;
646    const_iterator head = begin();
647    const_iterator const tail = end();
648    ALOGD("  Region %s (this=%p, count=%d)\n", what, this, tail-head);
649    while (head != tail) {
650        ALOGD("    [%3d, %3d, %3d, %3d]\n",
651                head->left, head->top, head->right, head->bottom);
652        head++;
653    }
654}
655
656// ----------------------------------------------------------------------------
657
658}; // namespace android
659