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