Region.cpp revision 0450452e8c6ea48341d57d8bc51d56252e9806b8 
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    LOGE_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::andSelf(const Rect& r) {
130    return operationSelf(r, op_and);
131}
132Region& Region::subtractSelf(const Rect& r) {
133    return operationSelf(r, op_nand);
134}
135Region& Region::operationSelf(const Rect& r, int op) {
136    Region lhs(*this);
137    boolean_operation(op, *this, lhs, r);
138    return *this;
139}
140
141// ----------------------------------------------------------------------------
142
143Region& Region::orSelf(const Region& rhs) {
144    return operationSelf(rhs, op_or);
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::intersect(const Rect& rhs) const {
169    return operation(rhs, op_and);
170}
171const Region Region::subtract(const Rect& rhs) const {
172    return operation(rhs, op_nand);
173}
174const Region Region::operation(const Rect& rhs, int op) const {
175    Region result;
176    boolean_operation(op, result, *this, rhs);
177    return result;
178}
179
180// ----------------------------------------------------------------------------
181
182const Region Region::merge(const Region& rhs) const {
183    return operation(rhs, op_or);
184}
185const Region Region::intersect(const Region& rhs) const {
186    return operation(rhs, op_and);
187}
188const Region Region::subtract(const Region& rhs) const {
189    return operation(rhs, op_nand);
190}
191const Region Region::operation(const Region& rhs, int op) const {
192    Region result;
193    boolean_operation(op, result, *this, rhs);
194    return result;
195}
196
197const Region Region::translate(int x, int y) const {
198    Region result;
199    translate(result, *this, x, y);
200    return result;
201}
202
203// ----------------------------------------------------------------------------
204
205Region& Region::orSelf(const Region& rhs, int dx, int dy) {
206    return operationSelf(rhs, dx, dy, op_or);
207}
208Region& Region::andSelf(const Region& rhs, int dx, int dy) {
209    return operationSelf(rhs, dx, dy, op_and);
210}
211Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
212    return operationSelf(rhs, dx, dy, op_nand);
213}
214Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) {
215    Region lhs(*this);
216    boolean_operation(op, *this, lhs, rhs, dx, dy);
217    return *this;
218}
219
220// ----------------------------------------------------------------------------
221
222const Region Region::merge(const Region& rhs, int dx, int dy) const {
223    return operation(rhs, dx, dy, op_or);
224}
225const Region Region::intersect(const Region& rhs, int dx, int dy) const {
226    return operation(rhs, dx, dy, op_and);
227}
228const Region Region::subtract(const Region& rhs, int dx, int dy) const {
229    return operation(rhs, dx, dy, op_nand);
230}
231const Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
232    Region result;
233    boolean_operation(op, result, *this, rhs, dx, dy);
234    return result;
235}
236
237// ----------------------------------------------------------------------------
238
239// This is our region rasterizer, which merges rects and spans together
240// to obtain an optimal region.
241class Region::rasterizer : public region_operator<Rect>::region_rasterizer
242{
243    Rect& bounds;
244    Vector<Rect>& storage;
245    Rect* head;
246    Rect* tail;
247    Vector<Rect> span;
248    Rect* cur;
249public:
250    rasterizer(Region& reg)
251        : bounds(reg.mBounds), storage(reg.mStorage), head(), tail(), cur() {
252        bounds.top = bounds.bottom = 0;
253        bounds.left   = INT_MAX;
254        bounds.right  = INT_MIN;
255        storage.clear();
256    }
257
258    ~rasterizer() {
259        if (span.size()) {
260            flushSpan();
261        }
262        if (storage.size()) {
263            bounds.top = storage.itemAt(0).top;
264            bounds.bottom = storage.top().bottom;
265            if (storage.size() == 1) {
266                storage.clear();
267            }
268        } else {
269            bounds.left  = 0;
270            bounds.right = 0;
271        }
272    }
273
274    virtual void operator()(const Rect& rect) {
275        //LOGD(">>> %3d, %3d, %3d, %3d",
276        //        rect.left, rect.top, rect.right, rect.bottom);
277        if (span.size()) {
278            if (cur->top != rect.top) {
279                flushSpan();
280            } else if (cur->right == rect.left) {
281                cur->right = rect.right;
282                return;
283            }
284        }
285        span.add(rect);
286        cur = span.editArray() + (span.size() - 1);
287    }
288private:
289    template<typename T>
290    static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
291    template<typename T>
292    static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
293    void flushSpan() {
294        bool merge = false;
295        if (tail-head == ssize_t(span.size())) {
296            Rect const* p = span.editArray();
297            Rect const* q = head;
298            if (p->top == q->bottom) {
299                merge = true;
300                while (q != tail) {
301                    if ((p->left != q->left) || (p->right != q->right)) {
302                        merge = false;
303                        break;
304                    }
305                    p++, q++;
306                }
307            }
308        }
309        if (merge) {
310            const int bottom = span[0].bottom;
311            Rect* r = head;
312            while (r != tail) {
313                r->bottom = bottom;
314                r++;
315            }
316        } else {
317            bounds.left = min(span.itemAt(0).left, bounds.left);
318            bounds.right = max(span.top().right, bounds.right);
319            storage.appendVector(span);
320            tail = storage.editArray() + storage.size();
321            head = tail - span.size();
322        }
323        span.clear();
324    }
325};
326
327bool Region::validate(const Region& reg, const char* name)
328{
329    bool result = true;
330    const_iterator cur = reg.begin();
331    const_iterator const tail = reg.end();
332    const_iterator prev = cur++;
333    Rect b(*prev);
334    while (cur != tail) {
335        b.left   = b.left   < cur->left   ? b.left   : cur->left;
336        b.top    = b.top    < cur->top    ? b.top    : cur->top;
337        b.right  = b.right  > cur->right  ? b.right  : cur->right;
338        b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom;
339        if (cur->top == prev->top) {
340            if (cur->bottom != prev->bottom) {
341                LOGE("%s: invalid span %p", name, cur);
342                result = false;
343            } else if (cur->left < prev->right) {
344                LOGE("%s: spans overlap horizontally prev=%p, cur=%p",
345                        name, prev, cur);
346                result = false;
347            }
348        } else if (cur->top < prev->bottom) {
349            LOGE("%s: spans overlap vertically prev=%p, cur=%p",
350                    name, prev, cur);
351            result = false;
352        }
353        prev = cur;
354        cur++;
355    }
356    if (b != reg.getBounds()) {
357        result = false;
358        LOGE("%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
359                b.left, b.top, b.right, b.bottom,
360                reg.getBounds().left, reg.getBounds().top,
361                reg.getBounds().right, reg.getBounds().bottom);
362    }
363    if (result == false) {
364        reg.dump(name);
365    }
366    return result;
367}
368
369void Region::boolean_operation(int op, Region& dst,
370        const Region& lhs,
371        const Region& rhs, int dx, int dy)
372{
373#if VALIDATE_REGIONS
374    validate(lhs, "boolean_operation (before): lhs");
375    validate(rhs, "boolean_operation (before): rhs");
376    validate(dst, "boolean_operation (before): dst");
377#endif
378
379    size_t lhs_count;
380    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
381
382    size_t rhs_count;
383    Rect const * const rhs_rects = rhs.getArray(&rhs_count);
384
385    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
386    region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
387    region_operator<Rect> operation(op, lhs_region, rhs_region);
388    { // scope for rasterizer (dtor has side effects)
389        rasterizer r(dst);
390        operation(r);
391    }
392
393#if VALIDATE_REGIONS
394    validate(lhs, "boolean_operation: lhs");
395    validate(rhs, "boolean_operation: rhs");
396    validate(dst, "boolean_operation: dst");
397#endif
398
399#if VALIDATE_WITH_CORECG
400    SkRegion sk_lhs;
401    SkRegion sk_rhs;
402    SkRegion sk_dst;
403
404    for (size_t i=0 ; i<lhs_count ; i++)
405        sk_lhs.op(
406                lhs_rects[i].left   + dx,
407                lhs_rects[i].top    + dy,
408                lhs_rects[i].right  + dx,
409                lhs_rects[i].bottom + dy,
410                SkRegion::kUnion_Op);
411
412    for (size_t i=0 ; i<rhs_count ; i++)
413        sk_rhs.op(
414                rhs_rects[i].left   + dx,
415                rhs_rects[i].top    + dy,
416                rhs_rects[i].right  + dx,
417                rhs_rects[i].bottom + dy,
418                SkRegion::kUnion_Op);
419
420    const char* name = "---";
421    SkRegion::Op sk_op;
422    switch (op) {
423        case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
424        case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
425        case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
426    }
427    sk_dst.op(sk_lhs, sk_rhs, sk_op);
428
429    if (sk_dst.isEmpty() && dst.isEmpty())
430        return;
431
432    bool same = true;
433    Region::const_iterator head = dst.begin();
434    Region::const_iterator const tail = dst.end();
435    SkRegion::Iterator it(sk_dst);
436    while (!it.done()) {
437        if (head != tail) {
438            if (
439                    head->left != it.rect().fLeft ||
440                    head->top != it.rect().fTop ||
441                    head->right != it.rect().fRight ||
442                    head->bottom != it.rect().fBottom
443            ) {
444                same = false;
445                break;
446            }
447        } else {
448            same = false;
449            break;
450        }
451        head++;
452        it.next();
453    }
454
455    if (head != tail) {
456        same = false;
457    }
458
459    if(!same) {
460        LOGD("---\nregion boolean %s failed", name);
461        lhs.dump("lhs");
462        rhs.dump("rhs");
463        dst.dump("dst");
464        LOGD("should be");
465        SkRegion::Iterator it(sk_dst);
466        while (!it.done()) {
467            LOGD("    [%3d, %3d, %3d, %3d]",
468                it.rect().fLeft,
469                it.rect().fTop,
470                it.rect().fRight,
471                it.rect().fBottom);
472            it.next();
473        }
474    }
475#endif
476}
477
478void Region::boolean_operation(int op, Region& dst,
479        const Region& lhs,
480        const Rect& rhs, int dx, int dy)
481{
482    if (!rhs.isValid()) {
483        LOGE("Region::boolean_operation(op=%d) invalid Rect={%d,%d,%d,%d}",
484                op, rhs.left, rhs.top, rhs.right, rhs.bottom);
485    }
486
487#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
488    boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
489#else
490    size_t lhs_count;
491    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
492
493    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
494    region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
495    region_operator<Rect> operation(op, lhs_region, rhs_region);
496    { // scope for rasterizer (dtor has side effects)
497        rasterizer r(dst);
498        operation(r);
499    }
500
501#endif
502}
503
504void Region::boolean_operation(int op, Region& dst,
505        const Region& lhs, const Region& rhs)
506{
507    boolean_operation(op, dst, lhs, rhs, 0, 0);
508}
509
510void Region::boolean_operation(int op, Region& dst,
511        const Region& lhs, const Rect& rhs)
512{
513    boolean_operation(op, dst, lhs, rhs, 0, 0);
514}
515
516void Region::translate(Region& reg, int dx, int dy)
517{
518    if (!reg.isEmpty()) {
519#if VALIDATE_REGIONS
520        validate(reg, "translate (before)");
521#endif
522        reg.mBounds.translate(dx, dy);
523        size_t count = reg.mStorage.size();
524        Rect* rects = reg.mStorage.editArray();
525        while (count) {
526            rects->translate(dx, dy);
527            rects++;
528            count--;
529        }
530#if VALIDATE_REGIONS
531        validate(reg, "translate (after)");
532#endif
533    }
534}
535
536void Region::translate(Region& dst, const Region& reg, int dx, int dy)
537{
538    dst = reg;
539    translate(dst, dx, dy);
540}
541
542// ----------------------------------------------------------------------------
543
544ssize_t Region::write(void* buffer, size_t size) const
545{
546#if VALIDATE_REGIONS
547    validate(*this, "write(buffer)");
548#endif
549    const size_t count = mStorage.size();
550    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
551    if (buffer != NULL) {
552        if (sizeNeeded > size) return NO_MEMORY;
553        int32_t* const p = static_cast<int32_t*>(buffer);
554        *p = count;
555        memcpy(p+1, &mBounds, sizeof(Rect));
556        if (count) {
557            memcpy(p+5, mStorage.array(), count*sizeof(Rect));
558        }
559    }
560    return ssize_t(sizeNeeded);
561}
562
563ssize_t Region::read(const void* buffer)
564{
565    int32_t const* const p = static_cast<int32_t const*>(buffer);
566    const size_t count = *p;
567    memcpy(&mBounds, p+1, sizeof(Rect));
568    mStorage.clear();
569    if (count) {
570        mStorage.insertAt(0, count);
571        memcpy(mStorage.editArray(), p+5, count*sizeof(Rect));
572    }
573#if VALIDATE_REGIONS
574    validate(*this, "read(buffer)");
575#endif
576    return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect));
577}
578
579ssize_t Region::writeEmpty(void* buffer, size_t size)
580{
581    const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect);
582    if (sizeNeeded > size) return NO_MEMORY;
583    int32_t* const p = static_cast<int32_t*>(buffer);
584    memset(p, 0, sizeNeeded);
585    return ssize_t(sizeNeeded);
586}
587
588bool Region::isEmpty(void* buffer)
589{
590    int32_t const* const p = static_cast<int32_t const*>(buffer);
591    Rect const* const b = reinterpret_cast<Rect const *>(p+1);
592    return b->isEmpty();
593}
594
595// ----------------------------------------------------------------------------
596
597Region::const_iterator Region::begin() const {
598    return isRect() ? &mBounds : mStorage.array();
599}
600
601Region::const_iterator Region::end() const {
602    return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size());
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    LOGD("  Region %s (this=%p, count=%d)\n", what, this, tail-head);
650    while (head != tail) {
651        LOGD("    [%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