Region.cpp revision 9f96145725ff3f265712d607d19078fb91a5c8ec 
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 <utils/Log.h>
20#include <utils/String8.h>
21
22#include <ui/Rect.h>
23#include <ui/Region.h>
24#include <ui/Point.h>
25
26#include <private/ui/RegionHelper.h>
27
28// ----------------------------------------------------------------------------
29#define VALIDATE_REGIONS        (false)
30#define VALIDATE_WITH_CORECG    (false)
31// ----------------------------------------------------------------------------
32
33#if VALIDATE_WITH_CORECG
34#include <core/SkRegion.h>
35#endif
36
37namespace android {
38// ----------------------------------------------------------------------------
39
40enum {
41    op_nand = region_operator<Rect>::op_nand,
42    op_and  = region_operator<Rect>::op_and,
43    op_or   = region_operator<Rect>::op_or,
44    op_xor  = region_operator<Rect>::op_xor
45};
46
47// ----------------------------------------------------------------------------
48
49Region::Region()
50    : mBounds(0,0)
51{
52}
53
54Region::Region(const Region& rhs)
55    : mBounds(rhs.mBounds), mStorage(rhs.mStorage)
56{
57}
58
59Region::Region(const Rect& rhs)
60    : mBounds(rhs)
61{
62}
63
64Region::Region(const Parcel& parcel)
65{
66    status_t err = read(parcel);
67    LOGE_IF(err<0, "error %s reading Region from parcel", strerror(err));
68}
69
70Region::Region(const void* buffer)
71{
72    status_t err = read(buffer);
73    LOGE_IF(err<0, "error %s reading Region from parcel", strerror(err));
74}
75
76Region::~Region()
77{
78}
79
80Region& Region::operator = (const Region& rhs)
81{
82#if VALIDATE_REGIONS
83    validate(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 = cur;
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    size_t lhs_count;
374    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
375
376    size_t rhs_count;
377    Rect const * const rhs_rects = rhs.getArray(&rhs_count);
378
379    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
380    region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
381    region_operator<Rect> operation(op, lhs_region, rhs_region);
382    { // scope for rasterizer (dtor has side effects)
383        rasterizer r(dst);
384        operation(r);
385    }
386
387#if VALIDATE_REGIONS
388    validate(lhs, "boolean_operation: lhs");
389    validate(rhs, "boolean_operation: rhs");
390    validate(dst, "boolean_operation: dst");
391#endif
392
393#if VALIDATE_WITH_CORECG
394    SkRegion sk_lhs;
395    SkRegion sk_rhs;
396    SkRegion sk_dst;
397
398    for (size_t i=0 ; i<lhs_count ; i++)
399        sk_lhs.op(
400                lhs_rects[i].left   + dx,
401                lhs_rects[i].top    + dy,
402                lhs_rects[i].right  + dx,
403                lhs_rects[i].bottom + dy,
404                SkRegion::kUnion_Op);
405
406    for (size_t i=0 ; i<rhs_count ; i++)
407        sk_rhs.op(
408                rhs_rects[i].left   + dx,
409                rhs_rects[i].top    + dy,
410                rhs_rects[i].right  + dx,
411                rhs_rects[i].bottom + dy,
412                SkRegion::kUnion_Op);
413
414    const char* name = "---";
415    SkRegion::Op sk_op;
416    switch (op) {
417        case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
418        case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
419        case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
420    }
421    sk_dst.op(sk_lhs, sk_rhs, sk_op);
422
423    if (sk_dst.isEmpty() && dst.isEmpty())
424        return;
425
426    bool same = true;
427    Region::const_iterator head = dst.begin();
428    Region::const_iterator const tail = dst.end();
429    SkRegion::Iterator it(sk_dst);
430    while (!it.done()) {
431        if (head != tail) {
432            if (
433                    head->left != it.rect().fLeft ||
434                    head->top != it.rect().fTop ||
435                    head->right != it.rect().fRight ||
436                    head->bottom != it.rect().fBottom
437            ) {
438                same = false;
439                break;
440            }
441        } else {
442            same = false;
443            break;
444        }
445        head++;
446        it.next();
447    }
448
449    if (head != tail) {
450        same = false;
451    }
452
453    if(!same) {
454        LOGD("---\nregion boolean %s failed", name);
455        lhs.dump("lhs");
456        rhs.dump("rhs");
457        dst.dump("dst");
458        LOGD("should be");
459        SkRegion::Iterator it(sk_dst);
460        while (!it.done()) {
461            LOGD("    [%3d, %3d, %3d, %3d]",
462                it.rect().fLeft,
463                it.rect().fTop,
464                it.rect().fRight,
465                it.rect().fBottom);
466            it.next();
467        }
468    }
469#endif
470}
471
472void Region::boolean_operation(int op, Region& dst,
473        const Region& lhs,
474        const Rect& rhs, int dx, int dy)
475{
476#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
477    boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
478#else
479    size_t lhs_count;
480    Rect const * const lhs_rects = lhs.getArray(&lhs_count);
481
482    region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
483    region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
484    region_operator<Rect> operation(op, lhs_region, rhs_region);
485    { // scope for rasterizer (dtor has side effects)
486        rasterizer r(dst);
487        operation(r);
488    }
489
490#endif
491}
492
493void Region::boolean_operation(int op, Region& dst,
494        const Region& lhs, const Region& rhs)
495{
496    boolean_operation(op, dst, lhs, rhs, 0, 0);
497}
498
499void Region::boolean_operation(int op, Region& dst,
500        const Region& lhs, const Rect& rhs)
501{
502    boolean_operation(op, dst, lhs, rhs, 0, 0);
503}
504
505void Region::translate(Region& reg, int dx, int dy)
506{
507    if (!reg.isEmpty()) {
508#if VALIDATE_REGIONS
509        validate(reg, "translate (before)");
510#endif
511        reg.mBounds.translate(dx, dy);
512        size_t count = reg.mStorage.size();
513        Rect* rects = reg.mStorage.editArray();
514        while (count) {
515            rects->translate(dx, dy);
516            rects++;
517            count--;
518        }
519#if VALIDATE_REGIONS
520        validate(reg, "translate (after)");
521#endif
522    }
523}
524
525void Region::translate(Region& dst, const Region& reg, int dx, int dy)
526{
527    dst = reg;
528    translate(dst, dx, dy);
529}
530
531// ----------------------------------------------------------------------------
532
533status_t Region::write(Parcel& parcel) const
534{
535#if VALIDATE_REGIONS
536    validate(*this, "write(Parcel)");
537#endif
538    status_t err;
539    const size_t count = mStorage.size();
540    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
541    void* buffer = parcel.writeInplace(sizeNeeded);
542    if (!buffer) return NO_MEMORY;
543    ssize_t written = Region::write(buffer, sizeNeeded);
544    if (written < 0) return status_t(written);
545    return NO_ERROR;
546}
547
548status_t Region::read(const Parcel& parcel)
549{
550    void const* buffer = parcel.readInplace(sizeof(int32_t));
551    if (!buffer) return NO_MEMORY;
552    const size_t count = *static_cast<int32_t const *>(buffer);
553    void const* dummy = parcel.readInplace((1+count)*sizeof(Rect));
554    if (!dummy) return NO_MEMORY;
555    const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
556    const ssize_t read = Region::read(buffer);
557    if (read < 0) return status_t(read);
558#if VALIDATE_REGIONS
559    validate(*this, "read(Parcel)");
560#endif
561    return NO_ERROR;
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 (sizeNeeded > size) return NO_MEMORY;
572    int32_t* const p = static_cast<int32_t*>(buffer);
573    *p = count;
574    memcpy(p+1, &mBounds, sizeof(Rect));
575    if (count) {
576        memcpy(p+5, mStorage.array(), count*sizeof(Rect));
577    }
578    return ssize_t(sizeNeeded);
579}
580
581ssize_t Region::read(const void* buffer)
582{
583    int32_t const* const p = static_cast<int32_t const*>(buffer);
584    const size_t count = *p;
585    memcpy(&mBounds, p+1, sizeof(Rect));
586    mStorage.clear();
587    if (count) {
588        mStorage.insertAt(0, count);
589        memcpy(mStorage.editArray(), p+5, count*sizeof(Rect));
590    }
591#if VALIDATE_REGIONS
592    validate(*this, "read(buffer)");
593#endif
594    return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect));
595}
596
597ssize_t Region::writeEmpty(void* buffer, size_t size)
598{
599    const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect);
600    if (sizeNeeded > size) return NO_MEMORY;
601    int32_t* const p = static_cast<int32_t*>(buffer);
602    memset(p, 0, sizeNeeded);
603    return ssize_t(sizeNeeded);
604}
605
606bool Region::isEmpty(void* buffer)
607{
608    int32_t const* const p = static_cast<int32_t const*>(buffer);
609    Rect const* const b = reinterpret_cast<Rect const *>(p+1);
610    return b->isEmpty();
611}
612
613// ----------------------------------------------------------------------------
614
615Region::const_iterator Region::begin() const {
616    return isRect() ? &mBounds : mStorage.array();
617}
618
619Region::const_iterator Region::end() const {
620    return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size());
621}
622
623Rect const* Region::getArray(size_t* count) const {
624    const_iterator const b(begin());
625    const_iterator const e(end());
626    if (count) *count = e-b;
627    return b;
628}
629
630size_t Region::getRects(Vector<Rect>& rectList) const
631{
632    rectList = mStorage;
633    if (rectList.isEmpty()) {
634        rectList.clear();
635        rectList.add(mBounds);
636    }
637    return rectList.size();
638}
639
640// ----------------------------------------------------------------------------
641
642void Region::dump(String8& out, const char* what, uint32_t flags) const
643{
644    (void)flags;
645    const_iterator head = begin();
646    const_iterator const tail = end();
647
648    size_t SIZE = 256;
649    char buffer[SIZE];
650
651    snprintf(buffer, SIZE, "  Region %s (this=%p, count=%d)\n",
652            what, this, tail-head);
653    out.append(buffer);
654    while (head != tail) {
655        snprintf(buffer, SIZE, "    [%3d, %3d, %3d, %3d]\n",
656                head->left, head->top, head->right, head->bottom);
657        out.append(buffer);
658        head++;
659    }
660}
661
662void Region::dump(const char* what, uint32_t flags) const
663{
664    (void)flags;
665    const_iterator head = begin();
666    const_iterator const tail = end();
667    LOGD("  Region %s (this=%p, count=%d)\n", what, this, tail-head);
668    while (head != tail) {
669        LOGD("    [%3d, %3d, %3d, %3d]\n",
670                head->left, head->top, head->right, head->bottom);
671        head++;
672    }
673}
674
675// ----------------------------------------------------------------------------
676
677}; // namespace android
678