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