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
39 namespace android {
40 // ----------------------------------------------------------------------------
41
42 enum {
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
Region()51 Region::Region()
52 : mBounds(0,0)
53 {
54 }
55
Region(const Region & rhs)56 Region::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
Region(const Rect & rhs)64 Region::Region(const Rect& rhs)
65 : mBounds(rhs)
66 {
67 }
68
Region(const void * buffer)69 Region::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
~Region()75 Region::~Region()
76 {
77 }
78
operator =(const Region & rhs)79 Region& 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
makeBoundsSelf()90 Region& Region::makeBoundsSelf()
91 {
92 mStorage.clear();
93 return *this;
94 }
95
clear()96 void Region::clear()
97 {
98 mBounds.clear();
99 mStorage.clear();
100 }
101
set(const Rect & r)102 void Region::set(const Rect& r)
103 {
104 mBounds = r;
105 mStorage.clear();
106 }
107
set(uint32_t w,uint32_t h)108 void Region::set(uint32_t w, uint32_t h)
109 {
110 mBounds = Rect(int(w), int(h));
111 mStorage.clear();
112 }
113
114 // ----------------------------------------------------------------------------
115
addRectUnchecked(int l,int t,int r,int b)116 void 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
orSelf(const Rect & r)126 Region& Region::orSelf(const Rect& r) {
127 return operationSelf(r, op_or);
128 }
andSelf(const Rect & r)129 Region& Region::andSelf(const Rect& r) {
130 return operationSelf(r, op_and);
131 }
subtractSelf(const Rect & r)132 Region& Region::subtractSelf(const Rect& r) {
133 return operationSelf(r, op_nand);
134 }
operationSelf(const Rect & r,int op)135 Region& 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
orSelf(const Region & rhs)143 Region& Region::orSelf(const Region& rhs) {
144 return operationSelf(rhs, op_or);
145 }
andSelf(const Region & rhs)146 Region& Region::andSelf(const Region& rhs) {
147 return operationSelf(rhs, op_and);
148 }
subtractSelf(const Region & rhs)149 Region& Region::subtractSelf(const Region& rhs) {
150 return operationSelf(rhs, op_nand);
151 }
operationSelf(const Region & rhs,int op)152 Region& Region::operationSelf(const Region& rhs, int op) {
153 Region lhs(*this);
154 boolean_operation(op, *this, lhs, rhs);
155 return *this;
156 }
157
translateSelf(int x,int y)158 Region& Region::translateSelf(int x, int y) {
159 if (x|y) translate(*this, x, y);
160 return *this;
161 }
162
163 // ----------------------------------------------------------------------------
164
merge(const Rect & rhs) const165 const Region Region::merge(const Rect& rhs) const {
166 return operation(rhs, op_or);
167 }
intersect(const Rect & rhs) const168 const Region Region::intersect(const Rect& rhs) const {
169 return operation(rhs, op_and);
170 }
subtract(const Rect & rhs) const171 const Region Region::subtract(const Rect& rhs) const {
172 return operation(rhs, op_nand);
173 }
operation(const Rect & rhs,int op) const174 const 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
merge(const Region & rhs) const182 const Region Region::merge(const Region& rhs) const {
183 return operation(rhs, op_or);
184 }
intersect(const Region & rhs) const185 const Region Region::intersect(const Region& rhs) const {
186 return operation(rhs, op_and);
187 }
subtract(const Region & rhs) const188 const Region Region::subtract(const Region& rhs) const {
189 return operation(rhs, op_nand);
190 }
operation(const Region & rhs,int op) const191 const Region Region::operation(const Region& rhs, int op) const {
192 Region result;
193 boolean_operation(op, result, *this, rhs);
194 return result;
195 }
196
translate(int x,int y) const197 const Region Region::translate(int x, int y) const {
198 Region result;
199 translate(result, *this, x, y);
200 return result;
201 }
202
203 // ----------------------------------------------------------------------------
204
orSelf(const Region & rhs,int dx,int dy)205 Region& Region::orSelf(const Region& rhs, int dx, int dy) {
206 return operationSelf(rhs, dx, dy, op_or);
207 }
andSelf(const Region & rhs,int dx,int dy)208 Region& Region::andSelf(const Region& rhs, int dx, int dy) {
209 return operationSelf(rhs, dx, dy, op_and);
210 }
subtractSelf(const Region & rhs,int dx,int dy)211 Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
212 return operationSelf(rhs, dx, dy, op_nand);
213 }
operationSelf(const Region & rhs,int dx,int dy,int op)214 Region& 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
merge(const Region & rhs,int dx,int dy) const222 const Region Region::merge(const Region& rhs, int dx, int dy) const {
223 return operation(rhs, dx, dy, op_or);
224 }
intersect(const Region & rhs,int dx,int dy) const225 const Region Region::intersect(const Region& rhs, int dx, int dy) const {
226 return operation(rhs, dx, dy, op_and);
227 }
subtract(const Region & rhs,int dx,int dy) const228 const Region Region::subtract(const Region& rhs, int dx, int dy) const {
229 return operation(rhs, dx, dy, op_nand);
230 }
operation(const Region & rhs,int dx,int dy,int op) const231 const 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.
241 class 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;
249 public:
rasterizer(Region & reg)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
~rasterizer()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
operator ()(const Rect & rect)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 }
288 private:
289 template<typename T>
min(T rhs,T lhs)290 static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
291 template<typename T>
max(T rhs,T lhs)292 static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
flushSpan()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
validate(const Region & reg,const char * name)327 bool 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
boolean_operation(int op,Region & dst,const Region & lhs,const Region & rhs,int dx,int dy)369 void 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
boolean_operation(int op,Region & dst,const Region & lhs,const Rect & rhs,int dx,int dy)478 void 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 return;
486 }
487
488 #if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
489 boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
490 #else
491 size_t lhs_count;
492 Rect const * const lhs_rects = lhs.getArray(&lhs_count);
493
494 region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
495 region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
496 region_operator<Rect> operation(op, lhs_region, rhs_region);
497 { // scope for rasterizer (dtor has side effects)
498 rasterizer r(dst);
499 operation(r);
500 }
501
502 #endif
503 }
504
boolean_operation(int op,Region & dst,const Region & lhs,const Region & rhs)505 void Region::boolean_operation(int op, Region& dst,
506 const Region& lhs, const Region& rhs)
507 {
508 boolean_operation(op, dst, lhs, rhs, 0, 0);
509 }
510
boolean_operation(int op,Region & dst,const Region & lhs,const Rect & rhs)511 void Region::boolean_operation(int op, Region& dst,
512 const Region& lhs, const Rect& rhs)
513 {
514 boolean_operation(op, dst, lhs, rhs, 0, 0);
515 }
516
translate(Region & reg,int dx,int dy)517 void Region::translate(Region& reg, int dx, int dy)
518 {
519 if (!reg.isEmpty()) {
520 #if VALIDATE_REGIONS
521 validate(reg, "translate (before)");
522 #endif
523 reg.mBounds.translate(dx, dy);
524 size_t count = reg.mStorage.size();
525 Rect* rects = reg.mStorage.editArray();
526 while (count) {
527 rects->translate(dx, dy);
528 rects++;
529 count--;
530 }
531 #if VALIDATE_REGIONS
532 validate(reg, "translate (after)");
533 #endif
534 }
535 }
536
translate(Region & dst,const Region & reg,int dx,int dy)537 void Region::translate(Region& dst, const Region& reg, int dx, int dy)
538 {
539 dst = reg;
540 translate(dst, dx, dy);
541 }
542
543 // ----------------------------------------------------------------------------
544
write(void * buffer,size_t size) const545 ssize_t Region::write(void* buffer, size_t size) const
546 {
547 #if VALIDATE_REGIONS
548 validate(*this, "write(buffer)");
549 #endif
550 const size_t count = mStorage.size();
551 const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect);
552 if (buffer != NULL) {
553 if (sizeNeeded > size) return NO_MEMORY;
554 int32_t* const p = static_cast<int32_t*>(buffer);
555 *p = count;
556 memcpy(p+1, &mBounds, sizeof(Rect));
557 if (count) {
558 memcpy(p+5, mStorage.array(), count*sizeof(Rect));
559 }
560 }
561 return ssize_t(sizeNeeded);
562 }
563
read(const void * buffer)564 ssize_t Region::read(const void* buffer)
565 {
566 int32_t const* const p = static_cast<int32_t const*>(buffer);
567 const size_t count = *p;
568 memcpy(&mBounds, p+1, sizeof(Rect));
569 mStorage.clear();
570 if (count) {
571 mStorage.insertAt(0, count);
572 memcpy(mStorage.editArray(), p+5, count*sizeof(Rect));
573 }
574 #if VALIDATE_REGIONS
575 validate(*this, "read(buffer)");
576 #endif
577 return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect));
578 }
579
writeEmpty(void * buffer,size_t size)580 ssize_t Region::writeEmpty(void* buffer, size_t size)
581 {
582 const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect);
583 if (sizeNeeded > size) return NO_MEMORY;
584 int32_t* const p = static_cast<int32_t*>(buffer);
585 memset(p, 0, sizeNeeded);
586 return ssize_t(sizeNeeded);
587 }
588
isEmpty(void * buffer)589 bool Region::isEmpty(void* buffer)
590 {
591 int32_t const* const p = static_cast<int32_t const*>(buffer);
592 Rect const* const b = reinterpret_cast<Rect const *>(p+1);
593 return b->isEmpty();
594 }
595
596 // ----------------------------------------------------------------------------
597
begin() const598 Region::const_iterator Region::begin() const {
599 return isRect() ? &mBounds : mStorage.array();
600 }
601
end() const602 Region::const_iterator Region::end() const {
603 return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size());
604 }
605
getArray(size_t * count) const606 Rect const* Region::getArray(size_t* count) const {
607 const_iterator const b(begin());
608 const_iterator const e(end());
609 if (count) *count = e-b;
610 return b;
611 }
612
getRects(Vector<Rect> & rectList) const613 size_t Region::getRects(Vector<Rect>& rectList) const
614 {
615 rectList = mStorage;
616 if (rectList.isEmpty()) {
617 rectList.clear();
618 rectList.add(mBounds);
619 }
620 return rectList.size();
621 }
622
623 // ----------------------------------------------------------------------------
624
dump(String8 & out,const char * what,uint32_t flags) const625 void Region::dump(String8& out, const char* what, uint32_t flags) const
626 {
627 (void)flags;
628 const_iterator head = begin();
629 const_iterator const tail = end();
630
631 size_t SIZE = 256;
632 char buffer[SIZE];
633
634 snprintf(buffer, SIZE, " Region %s (this=%p, count=%d)\n",
635 what, this, tail-head);
636 out.append(buffer);
637 while (head != tail) {
638 snprintf(buffer, SIZE, " [%3d, %3d, %3d, %3d]\n",
639 head->left, head->top, head->right, head->bottom);
640 out.append(buffer);
641 head++;
642 }
643 }
644
dump(const char * what,uint32_t flags) const645 void Region::dump(const char* what, uint32_t flags) const
646 {
647 (void)flags;
648 const_iterator head = begin();
649 const_iterator const tail = end();
650 LOGD(" Region %s (this=%p, count=%d)\n", what, this, tail-head);
651 while (head != tail) {
652 LOGD(" [%3d, %3d, %3d, %3d]\n",
653 head->left, head->top, head->right, head->bottom);
654 head++;
655 }
656 }
657
658 // ----------------------------------------------------------------------------
659
660 }; // namespace android
661