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