Region.cpp revision 72b0ffe4c3776b33844bb00b9be5693bddd391f9
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