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