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