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