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