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