SkScan_AntiPath.cpp revision 4714359ec091b34a4f88eb9708868a58a22177d3
1 2/* 3 * Copyright 2006 The Android Open Source Project 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 10#include "SkScanPriv.h" 11#include "SkPath.h" 12#include "SkMatrix.h" 13#include "SkBlitter.h" 14#include "SkRegion.h" 15#include "SkAntiRun.h" 16 17#define SHIFT 2 18#define SCALE (1 << SHIFT) 19#define MASK (SCALE - 1) 20 21/** @file 22 We have two techniques for capturing the output of the supersampler: 23 - SUPERMASK, which records a large mask-bitmap 24 this is often faster for small, complex objects 25 - RLE, which records a rle-encoded scanline 26 this is often faster for large objects with big spans 27 28 These blitters use two coordinate systems: 29 - destination coordinates, scale equal to the output - often 30 abbreviated with 'i' or 'I' in variable names 31 - supersampled coordinates, scale equal to the output * SCALE 32 33 NEW_AA is a set of code-changes to try to make both paths produce identical 34 results. Its not quite there yet, though the remaining differences may be 35 in the subsequent blits, and not in the different masks/runs... 36 */ 37//#define FORCE_SUPERMASK 38//#define FORCE_RLE 39//#define SK_SUPPORT_NEW_AA 40 41/////////////////////////////////////////////////////////////////////////////// 42 43/// Base class for a single-pass supersampled blitter. 44class BaseSuperBlitter : public SkBlitter { 45public: 46 BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 47 const SkRegion& clip); 48 49 /// Must be explicitly defined on subclasses. 50 virtual void blitAntiH(int x, int y, const SkAlpha antialias[], 51 const int16_t runs[]) SK_OVERRIDE { 52 SkDEBUGFAIL("How did I get here?"); 53 } 54 /// May not be called on BaseSuperBlitter because it blits out of order. 55 virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE { 56 SkDEBUGFAIL("How did I get here?"); 57 } 58 59protected: 60 SkBlitter* fRealBlitter; 61 /// Current y coordinate, in destination coordinates. 62 int fCurrIY; 63 /// Widest row of region to be blitted, in destination coordinates. 64 int fWidth; 65 /// Leftmost x coordinate in any row, in destination coordinates. 66 int fLeft; 67 /// Leftmost x coordinate in any row, in supersampled coordinates. 68 int fSuperLeft; 69 70 SkDEBUGCODE(int fCurrX;) 71 /// Current y coordinate in supersampled coordinates. 72 int fCurrY; 73 /// Initial y coordinate (top of bounds). 74 int fTop; 75}; 76 77BaseSuperBlitter::BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 78 const SkRegion& clip) { 79 fRealBlitter = realBlitter; 80 81 // take the union of the ir bounds and clip, since we may be called with an 82 // inverse filltype 83 const int left = SkMin32(ir.fLeft, clip.getBounds().fLeft); 84 const int right = SkMax32(ir.fRight, clip.getBounds().fRight); 85 86 fLeft = left; 87 fSuperLeft = left << SHIFT; 88 fWidth = right - left; 89#if 0 90 fCurrIY = -1; 91 fCurrY = -1; 92#else 93 fTop = ir.fTop; 94 fCurrIY = ir.fTop - 1; 95 fCurrY = (ir.fTop << SHIFT) - 1; 96#endif 97 SkDEBUGCODE(fCurrX = -1;) 98} 99 100/// Run-length-encoded supersampling antialiased blitter. 101class SuperBlitter : public BaseSuperBlitter { 102public: 103 SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 104 const SkRegion& clip); 105 106 virtual ~SuperBlitter() { 107 this->flush(); 108 sk_free(fRuns.fRuns); 109 } 110 111 /// Once fRuns contains a complete supersampled row, flush() blits 112 /// it out through the wrapped blitter. 113 void flush(); 114 115 /// Blits a row of pixels, with location and width specified 116 /// in supersampled coordinates. 117 virtual void blitH(int x, int y, int width) SK_OVERRIDE; 118 /// Blits a rectangle of pixels, with location and size specified 119 /// in supersampled coordinates. 120 virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE; 121 122private: 123 SkAlphaRuns fRuns; 124 int fOffsetX; 125}; 126 127SuperBlitter::SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 128 const SkRegion& clip) 129 : BaseSuperBlitter(realBlitter, ir, clip) { 130 const int width = fWidth; 131 132 // extra one to store the zero at the end 133 fRuns.fRuns = (int16_t*)sk_malloc_throw((width + 1 + (width + 2)/2) * sizeof(int16_t)); 134 fRuns.fAlpha = (uint8_t*)(fRuns.fRuns + width + 1); 135 fRuns.reset(width); 136 137 fOffsetX = 0; 138} 139 140void SuperBlitter::flush() { 141 if (fCurrIY >= fTop) { 142 if (!fRuns.empty()) { 143 // SkDEBUGCODE(fRuns.dump();) 144 fRealBlitter->blitAntiH(fLeft, fCurrIY, fRuns.fAlpha, fRuns.fRuns); 145 fRuns.reset(fWidth); 146 fOffsetX = 0; 147 } 148 fCurrIY = fTop - 1; 149 SkDEBUGCODE(fCurrX = -1;) 150 } 151} 152 153static inline int coverage_to_alpha(int aa) { 154 aa <<= 8 - 2*SHIFT; 155 aa -= aa >> (8 - SHIFT - 1); 156 return aa; 157} 158 159static inline int coverage_to_exact_alpha(int aa) { 160 static int map [] = { 0, 64, 128, 192, 255 }; 161 SkASSERT(SHIFT == 2); 162 return map[aa]; 163} 164 165void SuperBlitter::blitH(int x, int y, int width) { 166 SkASSERT(width > 0); 167 168 int iy = y >> SHIFT; 169 SkASSERT(iy >= fCurrIY); 170 171 x -= fSuperLeft; 172 // hack, until I figure out why my cubics (I think) go beyond the bounds 173 if (x < 0) { 174 width += x; 175 x = 0; 176 } 177 178#ifdef SK_DEBUG 179 SkASSERT(y != fCurrY || x >= fCurrX); 180#endif 181 SkASSERT(y >= fCurrY); 182 if (fCurrY != y) { 183 fOffsetX = 0; 184 fCurrY = y; 185 } 186 187 if (iy != fCurrIY) { // new scanline 188 this->flush(); 189 fCurrIY = iy; 190 } 191 192 int start = x; 193 int stop = x + width; 194 195 SkASSERT(start >= 0 && stop > start); 196 // integer-pixel-aligned ends of blit, rounded out 197 int fb = start & MASK; 198 int fe = stop & MASK; 199 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 200 201 if (n < 0) { 202 fb = fe - fb; 203 n = 0; 204 fe = 0; 205 } else { 206 if (fb == 0) { 207 n += 1; 208 } else { 209 fb = SCALE - fb; 210 } 211 } 212 213 // TODO - should this be using coverage_to_exact_alpha? 214 fOffsetX = fRuns.add(x >> SHIFT, coverage_to_alpha(fb), 215 n, coverage_to_alpha(fe), 216 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT), 217 fOffsetX); 218 219#ifdef SK_DEBUG 220 fRuns.assertValid(y & MASK, (1 << (8 - SHIFT))); 221 fCurrX = x + width; 222#endif 223} 224 225static void set_left_rite_runs(SkAlphaRuns& runs, int ileft, U8CPU leftA, 226 int n, U8CPU riteA) { 227 SkASSERT(leftA <= 0xFF); 228 SkASSERT(riteA <= 0xFF); 229 230 int16_t* run = runs.fRuns; 231 uint8_t* aa = runs.fAlpha; 232 233 if (ileft > 0) { 234 run[0] = ileft; 235 aa[0] = 0; 236 run += ileft; 237 aa += ileft; 238 } 239 240 SkASSERT(leftA < 0xFF); 241 if (leftA > 0) { 242 *run++ = 1; 243 *aa++ = leftA; 244 } 245 246 if (n > 0) { 247 run[0] = n; 248 aa[0] = 0xFF; 249 run += n; 250 aa += n; 251 } 252 253 SkASSERT(riteA < 0xFF); 254 if (riteA > 0) { 255 *run++ = 1; 256 *aa++ = riteA; 257 } 258 run[0] = 0; 259} 260 261void SuperBlitter::blitRect(int x, int y, int width, int height) { 262 SkASSERT(width > 0); 263 SkASSERT(height > 0); 264 265 // blit leading rows 266 while ((y & MASK)) { 267 this->blitH(x, y++, width); 268 if (--height <= 0) { 269 return; 270 } 271 } 272 SkASSERT(height > 0); 273 274 // Since this is a rect, instead of blitting supersampled rows one at a 275 // time and then resolving to the destination canvas, we can blit 276 // directly to the destintion canvas one row per SCALE supersampled rows. 277 int start_y = y >> SHIFT; 278 int stop_y = (y + height) >> SHIFT; 279 int count = stop_y - start_y; 280 if (count > 0) { 281 y += count << SHIFT; 282 height -= count << SHIFT; 283 284 // save original X for our tail blitH() loop at the bottom 285 int origX = x; 286 287 x -= fSuperLeft; 288 // hack, until I figure out why my cubics (I think) go beyond the bounds 289 if (x < 0) { 290 width += x; 291 x = 0; 292 } 293 294 // There is always a left column, a middle, and a right column. 295 // ileft is the destination x of the first pixel of the entire rect. 296 // xleft is (SCALE - # of covered supersampled pixels) in that 297 // destination pixel. 298 int ileft = x >> SHIFT; 299 int xleft = x & MASK; 300 // irite is the destination x of the last pixel of the OPAQUE section. 301 // xrite is the number of supersampled pixels extending beyond irite; 302 // xrite/SCALE should give us alpha. 303 int irite = (x + width) >> SHIFT; 304 int xrite = (x + width) & MASK; 305 if (!xrite) { 306 xrite = SCALE; 307 irite--; 308 } 309 310 // Need to call flush() to clean up pending draws before we 311 // even consider blitV(), since otherwise it can look nonmonotonic. 312 SkASSERT(start_y > fCurrIY); 313 this->flush(); 314 315 int n = irite - ileft - 1; 316 if (n < 0) { 317 // If n < 0, we'll only have a single partially-transparent column 318 // of pixels to render. 319 xleft = xrite - xleft; 320 SkASSERT(xleft <= SCALE); 321 SkASSERT(xleft > 0); 322 xrite = 0; 323 fRealBlitter->blitV(ileft + fLeft, start_y, count, 324 coverage_to_exact_alpha(xleft)); 325 } else { 326 // With n = 0, we have two possibly-transparent columns of pixels 327 // to render; with n > 0, we have opaque columns between them. 328 329 xleft = SCALE - xleft; 330 331 // Using coverage_to_exact_alpha is not consistent with blitH() 332 const int coverageL = coverage_to_exact_alpha(xleft); 333 const int coverageR = coverage_to_exact_alpha(xrite); 334 335 SkASSERT(coverageL > 0 || n > 0 || coverageR > 0); 336 SkASSERT((coverageL != 0) + n + (coverageR != 0) <= fWidth); 337 338 fRealBlitter->blitAntiRect(ileft + fLeft, start_y, n, count, 339 coverageL, coverageR); 340 } 341 342 // preamble for our next call to blitH() 343 fCurrIY = stop_y - 1; 344 fOffsetX = 0; 345 fCurrY = y - 1; 346 fRuns.reset(fWidth); 347 x = origX; 348 } 349 350 // catch any remaining few rows 351 SkASSERT(height <= MASK); 352 while (--height >= 0) { 353 this->blitH(x, y++, width); 354 } 355} 356 357/////////////////////////////////////////////////////////////////////////////// 358 359/// Masked supersampling antialiased blitter. 360class MaskSuperBlitter : public BaseSuperBlitter { 361public: 362 MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 363 const SkRegion& clip); 364 virtual ~MaskSuperBlitter() { 365 fRealBlitter->blitMask(fMask, fClipRect); 366 } 367 368 virtual void blitH(int x, int y, int width) SK_OVERRIDE; 369 370 static bool CanHandleRect(const SkIRect& bounds) { 371#ifdef FORCE_RLE 372 return false; 373#endif 374 int width = bounds.width(); 375 int rb = SkAlign4(width); 376 377 return (width <= MaskSuperBlitter::kMAX_WIDTH) && 378 (rb * bounds.height() <= MaskSuperBlitter::kMAX_STORAGE); 379 } 380 381private: 382 enum { 383#ifdef FORCE_SUPERMASK 384 kMAX_WIDTH = 2048, 385 kMAX_STORAGE = 1024 * 1024 * 2 386#else 387 kMAX_WIDTH = 32, // so we don't try to do very wide things, where the RLE blitter would be faster 388 kMAX_STORAGE = 1024 389#endif 390 }; 391 392 SkMask fMask; 393 SkIRect fClipRect; 394 // we add 1 because add_aa_span can write (unchanged) 1 extra byte at the end, rather than 395 // perform a test to see if stopAlpha != 0 396 uint32_t fStorage[(kMAX_STORAGE >> 2) + 1]; 397}; 398 399MaskSuperBlitter::MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 400 const SkRegion& clip) 401 : BaseSuperBlitter(realBlitter, ir, clip) { 402 SkASSERT(CanHandleRect(ir)); 403 404 fMask.fImage = (uint8_t*)fStorage; 405 fMask.fBounds = ir; 406 fMask.fRowBytes = ir.width(); 407 fMask.fFormat = SkMask::kA8_Format; 408 409 fClipRect = ir; 410 fClipRect.intersect(clip.getBounds()); 411 412 // For valgrind, write 1 extra byte at the end so we don't read 413 // uninitialized memory. See comment in add_aa_span and fStorage[]. 414 memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 1); 415} 416 417static void add_aa_span(uint8_t* alpha, U8CPU startAlpha) { 418 /* I should be able to just add alpha[x] + startAlpha. 419 However, if the trailing edge of the previous span and the leading 420 edge of the current span round to the same super-sampled x value, 421 I might overflow to 256 with this add, hence the funny subtract. 422 */ 423 unsigned tmp = *alpha + startAlpha; 424 SkASSERT(tmp <= 256); 425 *alpha = SkToU8(tmp - (tmp >> 8)); 426} 427 428static inline uint32_t quadplicate_byte(U8CPU value) { 429 uint32_t pair = (value << 8) | value; 430 return (pair << 16) | pair; 431} 432 433// minimum count before we want to setup an inner loop, adding 4-at-a-time 434#define MIN_COUNT_FOR_QUAD_LOOP 16 435 436static void add_aa_span(uint8_t* alpha, U8CPU startAlpha, int middleCount, 437 U8CPU stopAlpha, U8CPU maxValue) { 438 SkASSERT(middleCount >= 0); 439 440 /* I should be able to just add alpha[x] + startAlpha. 441 However, if the trailing edge of the previous span and the leading 442 edge of the current span round to the same super-sampled x value, 443 I might overflow to 256 with this add, hence the funny subtract. 444 */ 445#ifdef SK_SUPPORT_NEW_AA 446 if (startAlpha) { 447 unsigned tmp = *alpha + startAlpha; 448 SkASSERT(tmp <= 256); 449 *alpha++ = SkToU8(tmp - (tmp >> 8)); 450 } 451#else 452 unsigned tmp = *alpha + startAlpha; 453 SkASSERT(tmp <= 256); 454 *alpha++ = SkToU8(tmp - (tmp >> 8)); 455#endif 456 457 if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) { 458 // loop until we're quad-byte aligned 459 while (SkTCast<intptr_t>(alpha) & 0x3) { 460 alpha[0] = SkToU8(alpha[0] + maxValue); 461 alpha += 1; 462 middleCount -= 1; 463 } 464 465 int bigCount = middleCount >> 2; 466 uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha); 467 uint32_t qval = quadplicate_byte(maxValue); 468 do { 469 *qptr++ += qval; 470 } while (--bigCount > 0); 471 472 middleCount &= 3; 473 alpha = reinterpret_cast<uint8_t*> (qptr); 474 // fall through to the following while-loop 475 } 476 477 while (--middleCount >= 0) { 478 alpha[0] = SkToU8(alpha[0] + maxValue); 479 alpha += 1; 480 } 481 482 // potentially this can be off the end of our "legal" alpha values, but that 483 // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0 484 // every time (slow), we just do it, and ensure that we've allocated extra space 485 // (see the + 1 comment in fStorage[] 486 *alpha = SkToU8(*alpha + stopAlpha); 487} 488 489void MaskSuperBlitter::blitH(int x, int y, int width) { 490 int iy = (y >> SHIFT); 491 492 SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom); 493 iy -= fMask.fBounds.fTop; // make it relative to 0 494 495 // This should never happen, but it does. Until the true cause is 496 // discovered, let's skip this span instead of crashing. 497 // See http://crbug.com/17569. 498 if (iy < 0) { 499 return; 500 } 501 502#ifdef SK_DEBUG 503 { 504 int ix = x >> SHIFT; 505 SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight); 506 } 507#endif 508 509 x -= (fMask.fBounds.fLeft << SHIFT); 510 511 // hack, until I figure out why my cubics (I think) go beyond the bounds 512 if (x < 0) { 513 width += x; 514 x = 0; 515 } 516 517 uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT); 518 519 int start = x; 520 int stop = x + width; 521 522 SkASSERT(start >= 0 && stop > start); 523 int fb = start & MASK; 524 int fe = stop & MASK; 525 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 526 527 528 if (n < 0) { 529 SkASSERT(row >= fMask.fImage); 530 SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1); 531 add_aa_span(row, coverage_to_alpha(fe - fb)); 532 } else { 533#ifdef SK_SUPPORT_NEW_AA 534 if (0 == fb) { 535 n += 1; 536 } else { 537 fb = SCALE - fb; 538 } 539#else 540 fb = SCALE - fb; 541#endif 542 SkASSERT(row >= fMask.fImage); 543 SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1); 544 add_aa_span(row, coverage_to_alpha(fb), n, coverage_to_alpha(fe), 545 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT)); 546 } 547 548#ifdef SK_DEBUG 549 fCurrX = x + width; 550#endif 551} 552 553/////////////////////////////////////////////////////////////////////////////// 554 555/* Returns non-zero if (value << shift) overflows a short, which would mean 556 we could not shift it up and then convert to SkFixed. 557 i.e. is x expressible as signed (16-shift) bits? 558 */ 559static int overflows_short_shift(int value, int shift) { 560 const int s = 16 + shift; 561 return (value << s >> s) - value; 562} 563 564void SkScan::AntiFillPath(const SkPath& path, const SkRegion& clip, 565 SkBlitter* blitter, bool forceRLE) { 566 if (clip.isEmpty()) { 567 return; 568 } 569 570 SkIRect ir; 571 path.getBounds().roundOut(&ir); 572 if (ir.isEmpty()) { 573 if (path.isInverseFillType()) { 574 blitter->blitRegion(clip); 575 } 576 return; 577 } 578 579 // use bit-or since we expect all to pass, so no need to go slower with 580 // a short-circuiting logical-or 581 if (overflows_short_shift(ir.fLeft, SHIFT) | 582 overflows_short_shift(ir.fRight, SHIFT) | 583 overflows_short_shift(ir.fTop, SHIFT) | 584 overflows_short_shift(ir.fBottom, SHIFT)) { 585 // can't supersample, so draw w/o antialiasing 586 SkScan::FillPath(path, clip, blitter); 587 return; 588 } 589 590 SkScanClipper clipper(blitter, &clip, ir); 591 const SkIRect* clipRect = clipper.getClipRect(); 592 593 if (clipper.getBlitter() == NULL) { // clipped out 594 if (path.isInverseFillType()) { 595 blitter->blitRegion(clip); 596 } 597 return; 598 } 599 600 // now use the (possibly wrapped) blitter 601 blitter = clipper.getBlitter(); 602 603 if (path.isInverseFillType()) { 604 sk_blit_above(blitter, ir, clip); 605 } 606 607 SkIRect superRect, *superClipRect = NULL; 608 609 if (clipRect) { 610 superRect.set( clipRect->fLeft << SHIFT, clipRect->fTop << SHIFT, 611 clipRect->fRight << SHIFT, clipRect->fBottom << SHIFT); 612 superClipRect = &superRect; 613 } 614 615 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 616 617 // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it 618 // if we're an inverse filltype 619 if (!path.isInverseFillType() && MaskSuperBlitter::CanHandleRect(ir) && !forceRLE) { 620 MaskSuperBlitter superBlit(blitter, ir, clip); 621 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 622 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 623 } else { 624 SuperBlitter superBlit(blitter, ir, clip); 625 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 626 } 627 628 if (path.isInverseFillType()) { 629 sk_blit_below(blitter, ir, clip); 630 } 631} 632 633/////////////////////////////////////////////////////////////////////////////// 634 635#include "SkRasterClip.h" 636 637void SkScan::FillPath(const SkPath& path, const SkRasterClip& clip, 638 SkBlitter* blitter) { 639 if (clip.isEmpty()) { 640 return; 641 } 642 643 if (clip.isBW()) { 644 FillPath(path, clip.bwRgn(), blitter); 645 } else { 646 SkRegion tmp; 647 SkAAClipBlitter aaBlitter; 648 649 tmp.setRect(clip.getBounds()); 650 aaBlitter.init(blitter, &clip.aaRgn()); 651 SkScan::FillPath(path, tmp, &aaBlitter); 652 } 653} 654 655void SkScan::AntiFillPath(const SkPath& path, const SkRasterClip& clip, 656 SkBlitter* blitter) { 657 if (clip.isEmpty()) { 658 return; 659 } 660 661 if (clip.isBW()) { 662 AntiFillPath(path, clip.bwRgn(), blitter); 663 } else { 664 SkRegion tmp; 665 SkAAClipBlitter aaBlitter; 666 667 tmp.setRect(clip.getBounds()); 668 aaBlitter.init(blitter, &clip.aaRgn()); 669 SkScan::AntiFillPath(path, tmp, &aaBlitter, true); 670 } 671} 672 673