SkAAClip.cpp revision e36707a4a82a4dea7d480d969220f3ed223305dc
1 2/* 3 * Copyright 2011 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9#include "SkAAClip.h" 10#include "SkBlitter.h" 11#include "SkPath.h" 12#include "SkScan.h" 13#include "SkThread.h" 14 15static inline bool x_in_rect(int x, const SkIRect& rect) { 16 return (unsigned)(x - rect.fLeft) < (unsigned)rect.width(); 17} 18 19static inline bool y_in_rect(int y, const SkIRect& rect) { 20 return (unsigned)(y - rect.fTop) < (unsigned)rect.height(); 21} 22 23/* 24 * Data runs are packed [count, alpha] 25 */ 26 27struct SkAAClip::YOffset { 28 int32_t fY; 29 uint32_t fOffset; 30}; 31 32struct SkAAClip::RunHead { 33 int32_t fRefCnt; 34 int32_t fRowCount; 35 int32_t fDataSize; 36 37 YOffset* yoffsets() { 38 return (YOffset*)((char*)this + sizeof(RunHead)); 39 } 40 const YOffset* yoffsets() const { 41 return (const YOffset*)((const char*)this + sizeof(RunHead)); 42 } 43 uint8_t* data() { 44 return (uint8_t*)(this->yoffsets() + fRowCount); 45 } 46 const uint8_t* data() const { 47 return (const uint8_t*)(this->yoffsets() + fRowCount); 48 } 49 50 static RunHead* Alloc(int rowCount, size_t dataSize) { 51 size_t size = sizeof(RunHead) + rowCount * sizeof(YOffset) + dataSize; 52 RunHead* head = (RunHead*)sk_malloc_throw(size); 53 head->fRefCnt = 1; 54 head->fRowCount = rowCount; 55 head->fDataSize = dataSize; 56 return head; 57 } 58}; 59 60/////////////////////////////////////////////////////////////////////////////// 61 62void SkAAClip::freeRuns() { 63 if (this->isComplex()) { 64 SkASSERT(fRunHead->fRefCnt >= 1); 65 if (1 == sk_atomic_dec(&fRunHead->fRefCnt)) { 66 sk_free(fRunHead); 67 } 68 } 69} 70 71SkAAClip::SkAAClip() { 72 fBounds.setEmpty(); 73 fRunHead = SkAAClip_gEmptyPtr; 74} 75 76SkAAClip::SkAAClip(const SkAAClip& src) { 77 fRunHead = SkAAClip_gEmptyPtr; 78 *this = src; 79} 80 81SkAAClip::~SkAAClip() { 82 this->freeRuns(); 83} 84 85SkAAClip& SkAAClip::operator=(const SkAAClip& src) { 86 if (this != &src) { 87 this->freeRuns(); 88 fBounds = src.fBounds; 89 fRunHead = src.fRunHead; 90 if (this->isComplex()) { 91 sk_atomic_inc(&fRunHead->fRefCnt); 92 } 93 } 94 return *this; 95} 96 97bool operator==(const SkAAClip& a, const SkAAClip& b) { 98 if (&a == &b) { 99 return true; 100 } 101 if (a.fBounds != b.fBounds) { 102 return false; 103 } 104 105 const SkAAClip::RunHead* ah = a.fRunHead; 106 const SkAAClip::RunHead* bh = b.fRunHead; 107 108 // this catches empties and rects being equal 109 if (ah == bh) { 110 return true; 111 } 112 113 // now we insist that both are complex (but different ptrs) 114 if (!a.isComplex() || !b.isComplex()) { 115 return false; 116 } 117 118 return ah->fRowCount == bh->fRowCount && 119 ah->fDataSize == bh->fDataSize && 120 !memcmp(ah->data(), bh->data(), ah->fDataSize); 121} 122 123void SkAAClip::swap(SkAAClip& other) { 124 SkTSwap(fBounds, other.fBounds); 125 SkTSwap(fRunHead, other.fRunHead); 126} 127 128bool SkAAClip::setEmpty() { 129 this->freeRuns(); 130 fBounds.setEmpty(); 131 fRunHead = SkAAClip_gEmptyPtr; 132 return false; 133} 134 135bool SkAAClip::setRect(const SkIRect& bounds) { 136 if (bounds.isEmpty()) { 137 return this->setEmpty(); 138 } 139 this->freeRuns(); 140 fBounds = bounds; 141 fRunHead = SkAAClip_gRectPtr; 142 return true; 143} 144 145bool SkAAClip::setRect(const SkRect& r) { 146 if (r.isEmpty()) { 147 return this->setEmpty(); 148 } 149 150 SkIRect ibounds; 151 r.roundOut(&ibounds); 152 153 SkRegion clip; 154 clip.setRect(ibounds); 155 156 SkPath path; 157 path.addRect(r); 158 return this->setPath(path, clip); 159} 160 161/////////////////////////////////////////////////////////////////////////////// 162 163const uint8_t* SkAAClip::findRow(int y, int* lastYForRow) const { 164 SkASSERT(this->isComplex()); 165 166 if (!y_in_rect(y, fBounds)) { 167 return NULL; 168 } 169 y -= fBounds.y(); // our yoffs values are relative to the top 170 171 const YOffset* yoff = fRunHead->yoffsets(); 172 while (yoff->fY < y) { 173 yoff += 1; 174 SkASSERT(yoff - fRunHead->yoffsets() < fRunHead->fRowCount); 175 } 176 177 if (lastYForRow) { 178 *lastYForRow = yoff->fY; 179 } 180 return fRunHead->data() + yoff->fOffset; 181} 182 183const uint8_t* SkAAClip::findX(const uint8_t data[], int x, int* initialCount) const { 184 SkASSERT(x_in_rect(x, fBounds)); 185 x -= fBounds.x(); 186 187 // first skip up to X 188 for (;;) { 189 int n = data[0]; 190 if (x < n) { 191 *initialCount = n - x; 192 break; 193 } 194 data += 2; 195 x -= n; 196 } 197 return data; 198} 199 200bool SkAAClip::quickContains(int left, int top, int right, int bottom) const { 201 if (this->isEmpty()) { 202 return false; 203 } 204 if (!fBounds.contains(left, top, right, bottom)) { 205 return false; 206 } 207 if (this->isRect()) { 208 return true; 209 } 210 211 int lastY; 212 const uint8_t* row = this->findRow(top, &lastY); 213 if (lastY < bottom) { 214 return false; 215 } 216 // now just need to check in X 217 int initialCount; 218 row = this->findX(row, left, &initialCount); 219 return initialCount >= (right - left) && 0xFF == row[1]; 220} 221 222/////////////////////////////////////////////////////////////////////////////// 223 224class SkAAClip::Builder { 225 SkIRect fBounds; 226 struct Row { 227 int fY; 228 int fWidth; 229 SkTDArray<uint8_t>* fData; 230 }; 231 SkTDArray<Row> fRows; 232 Row* fCurrRow; 233 int fPrevY; 234 int fWidth; 235 236public: 237 Builder(const SkIRect& bounds) : fBounds(bounds) { 238 fPrevY = -1; 239 fWidth = bounds.width(); 240 fCurrRow = NULL; 241 } 242 243 ~Builder() { 244 Row* row = fRows.begin(); 245 Row* stop = fRows.end(); 246 while (row < stop) { 247 delete row->fData; 248 row += 1; 249 } 250 } 251 252 void addRun(int x, int y, U8CPU alpha, int count) { 253 SkASSERT(count > 0); 254 SkASSERT(fBounds.contains(x, y)); 255 SkASSERT(fBounds.contains(x + count - 1, y)); 256 257 x -= fBounds.left(); 258 y -= fBounds.top(); 259 260 Row* row = fCurrRow; 261 if (y != fPrevY) { 262 SkASSERT(y > fPrevY); 263 fPrevY = y; 264 row = this->flushRow(true); 265 row->fY = y; 266 row->fWidth = 0; 267 SkASSERT(row->fData); 268 SkASSERT(0 == row->fData->count()); 269 fCurrRow = row; 270 } 271 272 SkASSERT(row->fWidth <= x); 273 SkASSERT(row->fWidth < fBounds.width()); 274 275 SkTDArray<uint8_t>& data = *row->fData; 276 277 int gap = x - row->fWidth; 278 if (gap) { 279 AppendRun(data, 0, gap); 280 row->fWidth += gap; 281 SkASSERT(row->fWidth < fBounds.width()); 282 } 283 284 AppendRun(data, alpha, count); 285 row->fWidth += count; 286 SkASSERT(row->fWidth <= fBounds.width()); 287 } 288 289 RunHead* finish() { 290 this->flushRow(false); 291 292 const Row* row = fRows.begin(); 293 const Row* stop = fRows.end(); 294 295 size_t dataSize = 0; 296 while (row < stop) { 297 dataSize += row->fData->count(); 298 row += 1; 299 } 300 301 RunHead* head = RunHead::Alloc(fRows.count(), dataSize); 302 YOffset* yoffset = head->yoffsets(); 303 uint8_t* data = head->data(); 304 uint8_t* baseData = data; 305 306 row = fRows.begin(); 307 while (row < stop) { 308 yoffset->fY = row->fY; 309 yoffset->fOffset = data - baseData; 310 yoffset += 1; 311 312 size_t n = row->fData->count(); 313 memcpy(data, row->fData->begin(), n); 314 data += n; 315 316 row += 1; 317 } 318 319 return head; 320 } 321 322 void dump() { 323 this->validate(); 324 int y; 325 for (y = 0; y < fRows.count(); ++y) { 326 const Row& row = fRows[y]; 327 SkDebugf("Y:%3d W:%3d", row.fY, row.fWidth); 328 const SkTDArray<uint8_t>& data = *row.fData; 329 int count = data.count(); 330 SkASSERT(!(count & 1)); 331 const uint8_t* ptr = data.begin(); 332 for (int x = 0; x < count; x += 2) { 333 SkDebugf(" [%3d:%02X]", ptr[0], ptr[1]); 334 ptr += 2; 335 } 336 SkDebugf("\n"); 337 } 338 339#if 0 340 int prevY = -1; 341 for (y = 0; y < fRows.count(); ++y) { 342 const Row& row = fRows[y]; 343 const SkTDArray<uint8_t>& data = *row.fData; 344 int count = data.count(); 345 for (int n = prevY; n < row.fY; ++n) { 346 const uint8_t* ptr = data.begin(); 347 for (int x = 0; x < count; x += 2) { 348 for (int i = 0; i < ptr[0]; ++i) { 349 SkDebugf("%02X", ptr[1]); 350 } 351 ptr += 2; 352 } 353 SkDebugf("\n"); 354 } 355 prevY = row.fY; 356 } 357#endif 358 } 359 360 void validate() { 361#ifdef SK_DEBUG 362 int prevY = -1; 363 for (int i = 0; i < fRows.count(); ++i) { 364 const Row& row = fRows[i]; 365 SkASSERT(prevY < row.fY); 366 SkASSERT(fWidth == row.fWidth); 367 int count = row.fData->count(); 368 const uint8_t* ptr = row.fData->begin(); 369 SkASSERT(!(count & 1)); 370 int w = 0; 371 for (int x = 0; x < count; x += 2) { 372 w += ptr[0]; 373 SkASSERT(w <= fWidth); 374 ptr += 2; 375 } 376 SkASSERT(w == fWidth); 377 prevY = row.fY; 378 } 379#endif 380 } 381 382private: 383 Row* flushRow(bool readyForAnother) { 384 Row* next = NULL; 385 int count = fRows.count(); 386 if (count > 0) { 387 // flush current row if needed 388 Row* curr = &fRows[count - 1]; 389 if (curr->fWidth < fWidth) { 390 AppendRun(*curr->fData, 0, fWidth - curr->fWidth); 391 } 392 } 393 if (count > 1) { 394 // are our last two runs the same? 395 Row* prev = &fRows[count - 2]; 396 Row* curr = &fRows[count - 1]; 397 SkASSERT(prev->fWidth == fWidth); 398 SkASSERT(curr->fWidth == fWidth); 399 if (*prev->fData == *curr->fData) { 400 prev->fY = curr->fY; 401 if (readyForAnother) { 402 curr->fData->rewind(); 403 next = curr; 404 } else { 405 delete curr->fData; 406 fRows.removeShuffle(count - 1); 407 } 408 } else { 409 if (readyForAnother) { 410 next = fRows.append(); 411 next->fData = new SkTDArray<uint8_t>; 412 } 413 } 414 } else { 415 if (readyForAnother) { 416 next = fRows.append(); 417 next->fData = new SkTDArray<uint8_t>; 418 } 419 } 420 return next; 421 } 422 423 static void AppendRun(SkTDArray<uint8_t>& data, U8CPU alpha, int count) { 424 do { 425 int n = count; 426 if (n > 255) { 427 n = 255; 428 } 429 uint8_t* ptr = data.append(2); 430 ptr[0] = n; 431 ptr[1] = alpha; 432 count -= n; 433 } while (count > 0); 434 } 435}; 436 437class SkAAClip::BuilderBlitter : public SkBlitter { 438public: 439 BuilderBlitter(Builder* builder) { 440 fBuilder = builder; 441 } 442 443 virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE 444 { unexpected(); } 445 virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE 446 { unexpected(); } 447 virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE 448 { unexpected(); } 449 450 virtual const SkBitmap* justAnOpaqueColor(uint32_t*) SK_OVERRIDE { 451 return false; 452 } 453 454 virtual void blitH(int x, int y, int width) SK_OVERRIDE { 455 fBuilder->addRun(x, y, 0xFF, width); 456 } 457 458 virtual void blitAntiH(int x, int y, const SkAlpha alpha[], 459 const int16_t runs[]) SK_OVERRIDE { 460 for (;;) { 461 int count = *runs; 462 if (count <= 0) { 463 return; 464 } 465 fBuilder->addRun(x, y, *alpha, count); 466 runs += count; 467 alpha += count; 468 x += count; 469 } 470 } 471 472private: 473 Builder* fBuilder; 474 475 void unexpected() { 476 SkDebugf("---- did not expect to get called here"); 477 sk_throw(); 478 } 479}; 480 481bool SkAAClip::setPath(const SkPath& path, const SkRegion& clip) { 482 if (clip.isEmpty()) { 483 return this->setEmpty(); 484 } 485 486 SkIRect ibounds; 487 488 if (!path.isInverseFillType()) { 489 path.getBounds().roundOut(&ibounds); 490 if (ibounds.isEmpty() || !ibounds.intersect(clip.getBounds())) { 491 return this->setEmpty(); 492 } 493 } else { 494 ibounds = clip.getBounds(); 495 } 496 497 Builder builder(ibounds); 498 BuilderBlitter blitter(&builder); 499 500 SkScan::AntiFillPath(path, clip, &blitter, true); 501 502 this->freeRuns(); 503 fBounds = ibounds; 504 fRunHead = builder.finish(); 505 506 builder.dump(); 507} 508 509/////////////////////////////////////////////////////////////////////////////// 510 511bool SkAAClip::op(const SkAAClip&, const SkAAClip&, SkRegion::Op op) { 512 return true; 513} 514 515/////////////////////////////////////////////////////////////////////////////// 516/////////////////////////////////////////////////////////////////////////////// 517 518static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width, 519 int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) { 520 // we don't read our initial n from data, since the caller may have had to 521 // clip it, hence the initialCount parameter. 522 int n = initialCount; 523 for (;;) { 524 if (n > width) { 525 n = width; 526 } 527 SkASSERT(n > 0); 528 runs[0] = n; 529 runs += n; 530 531 aa[0] = data[1]; 532 aa += n; 533 534 data += 2; 535 width -= n; 536 if (0 == width) { 537 break; 538 } 539 // load the next count 540 n = data[0]; 541 } 542 runs[0] = 0; // sentinel 543} 544 545SkAAClipBlitter::~SkAAClipBlitter() { 546 sk_free(fRuns); 547} 548 549void SkAAClipBlitter::ensureRunsAndAA() { 550 if (NULL == fRuns) { 551 // add 1 so we can store the terminating run count of 0 552 int count = fAAClipBounds.width() + 1; 553 fRuns = (int16_t*)sk_malloc_throw(count * sizeof(int16_t) + 554 count * sizeof(SkAlpha)); 555 fAA = (SkAlpha*)(fRuns + count); 556 } 557} 558 559void SkAAClipBlitter::blitH(int x, int y, int width) { 560 SkASSERT(width > 0); 561 SkASSERT(fAAClipBounds.contains(x, y)); 562 SkASSERT(fAAClipBounds.contains(x + width - 1, y)); 563 564 int lastY; 565 const uint8_t* row = fAAClip->findRow(y, &lastY); 566 int initialCount; 567 row = fAAClip->findX(row, x, &initialCount); 568 569 if (initialCount >= width) { 570 SkAlpha alpha = row[1]; 571 if (0 == alpha) { 572 return; 573 } 574 if (0xFF == alpha) { 575 fBlitter->blitH(x, y, width); 576 return; 577 } 578 } 579 580 this->ensureRunsAndAA(); 581 expandToRuns(row, initialCount, width, fRuns, fAA); 582 583 fBlitter->blitAntiH(x, y, fAA, fRuns); 584} 585 586static void merge(const uint8_t* SK_RESTRICT row, int rowN, 587 const SkAlpha* SK_RESTRICT srcAA, 588 const int16_t* SK_RESTRICT srcRuns, 589 SkAlpha* SK_RESTRICT dstAA, 590 int16_t* SK_RESTRICT dstRuns, 591 int width) { 592 SkDEBUGCODE(int accumulated = 0;) 593 int srcN = srcRuns[0]; 594 for (;;) { 595 if (0 == srcN) { 596 break; 597 } 598 SkASSERT(rowN > 0); 599 SkASSERT(srcN > 0); 600 601 unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]); 602 int minN = SkMin32(srcN, rowN); 603 dstRuns[0] = minN; 604 dstRuns += minN; 605 dstAA[0] = newAlpha; 606 dstAA += minN; 607 608 if (0 == (srcN -= minN)) { 609 srcN = srcRuns[0]; // refresh 610 srcRuns += srcN; 611 srcAA += srcN; 612 srcN = srcRuns[0]; // reload 613 } 614 if (0 == (rowN -= minN)) { 615 row += 2; 616 rowN = row[0]; // reload 617 } 618 619 SkDEBUGCODE(accumulated += minN;) 620 SkASSERT(accumulated <= width); 621 } 622} 623 624void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[], 625 const int16_t runs[]) { 626 int lastY; 627 const uint8_t* row = fAAClip->findRow(y, &lastY); 628 int initialCount; 629 row = fAAClip->findX(row, x, &initialCount); 630 631 this->ensureRunsAndAA(); 632 633 merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width()); 634 fBlitter->blitAntiH(x, y, fAA, fRuns); 635} 636 637void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) { 638 if (fAAClip->quickContains(x, y, x + 1, y + height)) { 639 fBlitter->blitV(x, y, height, alpha); 640 return; 641 } 642 643 int stopY = y + height; 644 do { 645 int lastY; 646 const uint8_t* row = fAAClip->findRow(y, &lastY); 647 int initialCount; 648 row = fAAClip->findX(row, x, &initialCount); 649 SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]); 650 if (newAlpha) { 651 fBlitter->blitV(x, y, lastY - y + 1, newAlpha); 652 } 653 y = lastY + 1; 654 } while (y < stopY); 655} 656 657void SkAAClipBlitter::blitRect(int x, int y, int width, int height) { 658 if (fAAClip->quickContains(x, y, x + width, y + height)) { 659 fBlitter->blitRect(x, y, width, height); 660 return; 661 } 662 663 while (--height >= 0) { 664 this->blitH(x, y, width); 665 y += 1; 666 } 667} 668 669void SkAAClipBlitter::blitMask(const SkMask& mask, const SkIRect& clip) { 670 fBlitter->blitMask(mask, clip); 671} 672 673const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) { 674 return NULL; 675} 676 677