Region.cpp revision 9f96145725ff3f265712d607d19078fb91a5c8ec
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 <utils/Log.h> 20#include <utils/String8.h> 21 22#include <ui/Rect.h> 23#include <ui/Region.h> 24#include <ui/Point.h> 25 26#include <private/ui/RegionHelper.h> 27 28// ---------------------------------------------------------------------------- 29#define VALIDATE_REGIONS (false) 30#define VALIDATE_WITH_CORECG (false) 31// ---------------------------------------------------------------------------- 32 33#if VALIDATE_WITH_CORECG 34#include <core/SkRegion.h> 35#endif 36 37namespace android { 38// ---------------------------------------------------------------------------- 39 40enum { 41 op_nand = region_operator<Rect>::op_nand, 42 op_and = region_operator<Rect>::op_and, 43 op_or = region_operator<Rect>::op_or, 44 op_xor = region_operator<Rect>::op_xor 45}; 46 47// ---------------------------------------------------------------------------- 48 49Region::Region() 50 : mBounds(0,0) 51{ 52} 53 54Region::Region(const Region& rhs) 55 : mBounds(rhs.mBounds), mStorage(rhs.mStorage) 56{ 57} 58 59Region::Region(const Rect& rhs) 60 : mBounds(rhs) 61{ 62} 63 64Region::Region(const Parcel& parcel) 65{ 66 status_t err = read(parcel); 67 LOGE_IF(err<0, "error %s reading Region from parcel", strerror(err)); 68} 69 70Region::Region(const void* buffer) 71{ 72 status_t err = read(buffer); 73 LOGE_IF(err<0, "error %s reading Region from parcel", strerror(err)); 74} 75 76Region::~Region() 77{ 78} 79 80Region& Region::operator = (const Region& rhs) 81{ 82#if VALIDATE_REGIONS 83 validate(rhs, "operator="); 84#endif 85 mBounds = rhs.mBounds; 86 mStorage = rhs.mStorage; 87 return *this; 88} 89 90Region& Region::makeBoundsSelf() 91{ 92 mStorage.clear(); 93 return *this; 94} 95 96void Region::clear() 97{ 98 mBounds.clear(); 99 mStorage.clear(); 100} 101 102void Region::set(const Rect& r) 103{ 104 mBounds = r; 105 mStorage.clear(); 106} 107 108void Region::set(uint32_t w, uint32_t h) 109{ 110 mBounds = Rect(int(w), int(h)); 111 mStorage.clear(); 112} 113 114// ---------------------------------------------------------------------------- 115 116void 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 126Region& Region::orSelf(const Rect& r) { 127 return operationSelf(r, op_or); 128} 129Region& Region::andSelf(const Rect& r) { 130 return operationSelf(r, op_and); 131} 132Region& Region::subtractSelf(const Rect& r) { 133 return operationSelf(r, op_nand); 134} 135Region& 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 143Region& Region::orSelf(const Region& rhs) { 144 return operationSelf(rhs, op_or); 145} 146Region& Region::andSelf(const Region& rhs) { 147 return operationSelf(rhs, op_and); 148} 149Region& Region::subtractSelf(const Region& rhs) { 150 return operationSelf(rhs, op_nand); 151} 152Region& Region::operationSelf(const Region& rhs, int op) { 153 Region lhs(*this); 154 boolean_operation(op, *this, lhs, rhs); 155 return *this; 156} 157 158Region& Region::translateSelf(int x, int y) { 159 if (x|y) translate(*this, x, y); 160 return *this; 161} 162 163// ---------------------------------------------------------------------------- 164 165const Region Region::merge(const Rect& rhs) const { 166 return operation(rhs, op_or); 167} 168const Region Region::intersect(const Rect& rhs) const { 169 return operation(rhs, op_and); 170} 171const Region Region::subtract(const Rect& rhs) const { 172 return operation(rhs, op_nand); 173} 174const 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 182const Region Region::merge(const Region& rhs) const { 183 return operation(rhs, op_or); 184} 185const Region Region::intersect(const Region& rhs) const { 186 return operation(rhs, op_and); 187} 188const Region Region::subtract(const Region& rhs) const { 189 return operation(rhs, op_nand); 190} 191const Region Region::operation(const Region& rhs, int op) const { 192 Region result; 193 boolean_operation(op, result, *this, rhs); 194 return result; 195} 196 197const Region Region::translate(int x, int y) const { 198 Region result; 199 translate(result, *this, x, y); 200 return result; 201} 202 203// ---------------------------------------------------------------------------- 204 205Region& Region::orSelf(const Region& rhs, int dx, int dy) { 206 return operationSelf(rhs, dx, dy, op_or); 207} 208Region& Region::andSelf(const Region& rhs, int dx, int dy) { 209 return operationSelf(rhs, dx, dy, op_and); 210} 211Region& Region::subtractSelf(const Region& rhs, int dx, int dy) { 212 return operationSelf(rhs, dx, dy, op_nand); 213} 214Region& 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 222const Region Region::merge(const Region& rhs, int dx, int dy) const { 223 return operation(rhs, dx, dy, op_or); 224} 225const Region Region::intersect(const Region& rhs, int dx, int dy) const { 226 return operation(rhs, dx, dy, op_and); 227} 228const Region Region::subtract(const Region& rhs, int dx, int dy) const { 229 return operation(rhs, dx, dy, op_nand); 230} 231const 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. 241class 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; 249public: 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 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 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 } 288private: 289 template<typename T> 290 static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; } 291 template<typename T> 292 static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; } 293 void flushSpan() { 294 bool merge = false; 295 if (tail-head == ssize_t(span.size())) { 296 Rect const* p = cur; 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 327bool 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 369void Region::boolean_operation(int op, Region& dst, 370 const Region& lhs, 371 const Region& rhs, int dx, int dy) 372{ 373 size_t lhs_count; 374 Rect const * const lhs_rects = lhs.getArray(&lhs_count); 375 376 size_t rhs_count; 377 Rect const * const rhs_rects = rhs.getArray(&rhs_count); 378 379 region_operator<Rect>::region lhs_region(lhs_rects, lhs_count); 380 region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy); 381 region_operator<Rect> operation(op, lhs_region, rhs_region); 382 { // scope for rasterizer (dtor has side effects) 383 rasterizer r(dst); 384 operation(r); 385 } 386 387#if VALIDATE_REGIONS 388 validate(lhs, "boolean_operation: lhs"); 389 validate(rhs, "boolean_operation: rhs"); 390 validate(dst, "boolean_operation: dst"); 391#endif 392 393#if VALIDATE_WITH_CORECG 394 SkRegion sk_lhs; 395 SkRegion sk_rhs; 396 SkRegion sk_dst; 397 398 for (size_t i=0 ; i<lhs_count ; i++) 399 sk_lhs.op( 400 lhs_rects[i].left + dx, 401 lhs_rects[i].top + dy, 402 lhs_rects[i].right + dx, 403 lhs_rects[i].bottom + dy, 404 SkRegion::kUnion_Op); 405 406 for (size_t i=0 ; i<rhs_count ; i++) 407 sk_rhs.op( 408 rhs_rects[i].left + dx, 409 rhs_rects[i].top + dy, 410 rhs_rects[i].right + dx, 411 rhs_rects[i].bottom + dy, 412 SkRegion::kUnion_Op); 413 414 const char* name = "---"; 415 SkRegion::Op sk_op; 416 switch (op) { 417 case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break; 418 case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break; 419 case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break; 420 } 421 sk_dst.op(sk_lhs, sk_rhs, sk_op); 422 423 if (sk_dst.isEmpty() && dst.isEmpty()) 424 return; 425 426 bool same = true; 427 Region::const_iterator head = dst.begin(); 428 Region::const_iterator const tail = dst.end(); 429 SkRegion::Iterator it(sk_dst); 430 while (!it.done()) { 431 if (head != tail) { 432 if ( 433 head->left != it.rect().fLeft || 434 head->top != it.rect().fTop || 435 head->right != it.rect().fRight || 436 head->bottom != it.rect().fBottom 437 ) { 438 same = false; 439 break; 440 } 441 } else { 442 same = false; 443 break; 444 } 445 head++; 446 it.next(); 447 } 448 449 if (head != tail) { 450 same = false; 451 } 452 453 if(!same) { 454 LOGD("---\nregion boolean %s failed", name); 455 lhs.dump("lhs"); 456 rhs.dump("rhs"); 457 dst.dump("dst"); 458 LOGD("should be"); 459 SkRegion::Iterator it(sk_dst); 460 while (!it.done()) { 461 LOGD(" [%3d, %3d, %3d, %3d]", 462 it.rect().fLeft, 463 it.rect().fTop, 464 it.rect().fRight, 465 it.rect().fBottom); 466 it.next(); 467 } 468 } 469#endif 470} 471 472void Region::boolean_operation(int op, Region& dst, 473 const Region& lhs, 474 const Rect& rhs, int dx, int dy) 475{ 476#if VALIDATE_WITH_CORECG || VALIDATE_REGIONS 477 boolean_operation(op, dst, lhs, Region(rhs), dx, dy); 478#else 479 size_t lhs_count; 480 Rect const * const lhs_rects = lhs.getArray(&lhs_count); 481 482 region_operator<Rect>::region lhs_region(lhs_rects, lhs_count); 483 region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy); 484 region_operator<Rect> operation(op, lhs_region, rhs_region); 485 { // scope for rasterizer (dtor has side effects) 486 rasterizer r(dst); 487 operation(r); 488 } 489 490#endif 491} 492 493void Region::boolean_operation(int op, Region& dst, 494 const Region& lhs, const Region& rhs) 495{ 496 boolean_operation(op, dst, lhs, rhs, 0, 0); 497} 498 499void Region::boolean_operation(int op, Region& dst, 500 const Region& lhs, const Rect& rhs) 501{ 502 boolean_operation(op, dst, lhs, rhs, 0, 0); 503} 504 505void Region::translate(Region& reg, int dx, int dy) 506{ 507 if (!reg.isEmpty()) { 508#if VALIDATE_REGIONS 509 validate(reg, "translate (before)"); 510#endif 511 reg.mBounds.translate(dx, dy); 512 size_t count = reg.mStorage.size(); 513 Rect* rects = reg.mStorage.editArray(); 514 while (count) { 515 rects->translate(dx, dy); 516 rects++; 517 count--; 518 } 519#if VALIDATE_REGIONS 520 validate(reg, "translate (after)"); 521#endif 522 } 523} 524 525void Region::translate(Region& dst, const Region& reg, int dx, int dy) 526{ 527 dst = reg; 528 translate(dst, dx, dy); 529} 530 531// ---------------------------------------------------------------------------- 532 533status_t Region::write(Parcel& parcel) const 534{ 535#if VALIDATE_REGIONS 536 validate(*this, "write(Parcel)"); 537#endif 538 status_t err; 539 const size_t count = mStorage.size(); 540 const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect); 541 void* buffer = parcel.writeInplace(sizeNeeded); 542 if (!buffer) return NO_MEMORY; 543 ssize_t written = Region::write(buffer, sizeNeeded); 544 if (written < 0) return status_t(written); 545 return NO_ERROR; 546} 547 548status_t Region::read(const Parcel& parcel) 549{ 550 void const* buffer = parcel.readInplace(sizeof(int32_t)); 551 if (!buffer) return NO_MEMORY; 552 const size_t count = *static_cast<int32_t const *>(buffer); 553 void const* dummy = parcel.readInplace((1+count)*sizeof(Rect)); 554 if (!dummy) return NO_MEMORY; 555 const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect); 556 const ssize_t read = Region::read(buffer); 557 if (read < 0) return status_t(read); 558#if VALIDATE_REGIONS 559 validate(*this, "read(Parcel)"); 560#endif 561 return NO_ERROR; 562} 563 564ssize_t Region::write(void* buffer, size_t size) const 565{ 566#if VALIDATE_REGIONS 567 validate(*this, "write(buffer)"); 568#endif 569 const size_t count = mStorage.size(); 570 const size_t sizeNeeded = sizeof(int32_t) + (1+count)*sizeof(Rect); 571 if (sizeNeeded > size) return NO_MEMORY; 572 int32_t* const p = static_cast<int32_t*>(buffer); 573 *p = count; 574 memcpy(p+1, &mBounds, sizeof(Rect)); 575 if (count) { 576 memcpy(p+5, mStorage.array(), count*sizeof(Rect)); 577 } 578 return ssize_t(sizeNeeded); 579} 580 581ssize_t Region::read(const void* buffer) 582{ 583 int32_t const* const p = static_cast<int32_t const*>(buffer); 584 const size_t count = *p; 585 memcpy(&mBounds, p+1, sizeof(Rect)); 586 mStorage.clear(); 587 if (count) { 588 mStorage.insertAt(0, count); 589 memcpy(mStorage.editArray(), p+5, count*sizeof(Rect)); 590 } 591#if VALIDATE_REGIONS 592 validate(*this, "read(buffer)"); 593#endif 594 return ssize_t(sizeof(int32_t) + (1+count)*sizeof(Rect)); 595} 596 597ssize_t Region::writeEmpty(void* buffer, size_t size) 598{ 599 const size_t sizeNeeded = sizeof(int32_t) + sizeof(Rect); 600 if (sizeNeeded > size) return NO_MEMORY; 601 int32_t* const p = static_cast<int32_t*>(buffer); 602 memset(p, 0, sizeNeeded); 603 return ssize_t(sizeNeeded); 604} 605 606bool Region::isEmpty(void* buffer) 607{ 608 int32_t const* const p = static_cast<int32_t const*>(buffer); 609 Rect const* const b = reinterpret_cast<Rect const *>(p+1); 610 return b->isEmpty(); 611} 612 613// ---------------------------------------------------------------------------- 614 615Region::const_iterator Region::begin() const { 616 return isRect() ? &mBounds : mStorage.array(); 617} 618 619Region::const_iterator Region::end() const { 620 return isRect() ? ((&mBounds) + 1) : (mStorage.array() + mStorage.size()); 621} 622 623Rect const* Region::getArray(size_t* count) const { 624 const_iterator const b(begin()); 625 const_iterator const e(end()); 626 if (count) *count = e-b; 627 return b; 628} 629 630size_t Region::getRects(Vector<Rect>& rectList) const 631{ 632 rectList = mStorage; 633 if (rectList.isEmpty()) { 634 rectList.clear(); 635 rectList.add(mBounds); 636 } 637 return rectList.size(); 638} 639 640// ---------------------------------------------------------------------------- 641 642void Region::dump(String8& out, const char* what, uint32_t flags) const 643{ 644 (void)flags; 645 const_iterator head = begin(); 646 const_iterator const tail = end(); 647 648 size_t SIZE = 256; 649 char buffer[SIZE]; 650 651 snprintf(buffer, SIZE, " Region %s (this=%p, count=%d)\n", 652 what, this, tail-head); 653 out.append(buffer); 654 while (head != tail) { 655 snprintf(buffer, SIZE, " [%3d, %3d, %3d, %3d]\n", 656 head->left, head->top, head->right, head->bottom); 657 out.append(buffer); 658 head++; 659 } 660} 661 662void Region::dump(const char* what, uint32_t flags) const 663{ 664 (void)flags; 665 const_iterator head = begin(); 666 const_iterator const tail = end(); 667 LOGD(" Region %s (this=%p, count=%d)\n", what, this, tail-head); 668 while (head != tail) { 669 LOGD(" [%3d, %3d, %3d, %3d]\n", 670 head->left, head->top, head->right, head->bottom); 671 head++; 672 } 673} 674 675// ---------------------------------------------------------------------------- 676 677}; // namespace android 678