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