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