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