SkScan_AntiPath.cpp revision a89c77b5cafcc13d76cb07c3240e48705cb30d8f
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 SkASSERT(!"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 SkASSERT(!"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 159void SuperBlitter::blitH(int x, int y, int width) { 160 SkASSERT(width > 0); 161 162 int iy = y >> SHIFT; 163 SkASSERT(iy >= fCurrIY); 164 165 x -= fSuperLeft; 166 // hack, until I figure out why my cubics (I think) go beyond the bounds 167 if (x < 0) { 168 width += x; 169 x = 0; 170 } 171 172#ifdef SK_DEBUG 173 SkASSERT(y != fCurrY || x >= fCurrX); 174#endif 175 SkASSERT(y >= fCurrY); 176 if (fCurrY != y) { 177 fOffsetX = 0; 178 fCurrY = y; 179 } 180 181 if (iy != fCurrIY) { // new scanline 182 this->flush(); 183 fCurrIY = iy; 184 } 185 186 // we sub 1 from maxValue 1 time for each block, so that we don't 187 // hit 256 as a summed max, but 255. 188// int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT); 189 190 int start = x; 191 int stop = x + width; 192 193 SkASSERT(start >= 0 && stop > start); 194 // integer-pixel-aligned ends of blit, rounded out 195 int fb = start & MASK; 196 int fe = stop & MASK; 197 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 198 199 if (n < 0) { 200 fb = fe - fb; 201 n = 0; 202 fe = 0; 203 } else { 204 if (fb == 0) { 205 n += 1; 206 } else { 207 fb = (1 << SHIFT) - fb; 208 } 209 } 210 211 fOffsetX = fRuns.add(x >> SHIFT, coverage_to_alpha(fb), 212 n, coverage_to_alpha(fe), 213 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT), 214 fOffsetX); 215 216#ifdef SK_DEBUG 217 fRuns.assertValid(y & MASK, (1 << (8 - SHIFT))); 218 fCurrX = x + width; 219#endif 220} 221 222static void set_left_rite_runs(SkAlphaRuns& runs, int ileft, U8CPU leftA, 223 int n, U8CPU riteA) { 224 SkASSERT(leftA <= 0xFF); 225 SkASSERT(riteA <= 0xFF); 226 227 int16_t* run = runs.fRuns; 228 uint8_t* aa = runs.fAlpha; 229 230 if (ileft > 0) { 231 run[0] = ileft; 232 aa[0] = 0; 233 run += ileft; 234 aa += ileft; 235 } 236 237 SkASSERT(leftA < 0xFF); 238 if (leftA > 0) { 239 *run++ = 1; 240 *aa++ = leftA; 241 } 242 243 if (n > 0) { 244 run[0] = n; 245 aa[0] = 0xFF; 246 run += n; 247 aa += n; 248 } 249 250 SkASSERT(riteA < 0xFF); 251 if (riteA > 0) { 252 *run++ = 1; 253 *aa++ = riteA; 254 } 255 run[0] = 0; 256} 257 258void SuperBlitter::blitRect(int x, int y, int width, int height) { 259 SkASSERT(width > 0); 260 SkASSERT(height > 0); 261 262 // blit leading rows 263 while ((y & MASK)) { 264 this->blitH(x, y++, width); 265 if (--height <= 0) { 266 return; 267 } 268 } 269 SkASSERT(height > 0); 270 271 // Since this is a rect, instead of blitting supersampled rows one at a 272 // time and then resolving to the destination canvas, we can blit 273 // directly to the destintion canvas one row per SCALE supersampled rows. 274 int start_y = y >> SHIFT; 275 int stop_y = (y + height) >> SHIFT; 276 int count = stop_y - start_y; 277 if (count > 0) { 278 y += count << SHIFT; 279 height -= count << SHIFT; 280 281 // save original X for our tail blitH() loop at the bottom 282 int origX = x; 283 284 x -= fSuperLeft; 285 // hack, until I figure out why my cubics (I think) go beyond the bounds 286 if (x < 0) { 287 width += x; 288 x = 0; 289 } 290 291 int ileft = x >> SHIFT; 292 int xleft = x & MASK; 293 int irite = (x + width) >> SHIFT; 294 int xrite = (x + width) & MASK; 295 int n = irite - ileft - 1; 296 if (n < 0) { 297 // only one pixel, call blitV()? 298 xleft = xrite - xleft; 299 n = 0; 300 xrite = 0; 301 } else { 302 if (0 == xleft) { 303 n += 1; 304 } else { 305 xleft = (1 << SHIFT) - xleft; 306 } 307 } 308 309 // here we go 310 SkASSERT(start_y > fCurrIY); 311 this->flush(); 312 313 // to be compatible with the blitH() version, we just shift these 314 // values up. If we didn't care about that, we could be more precise 315 // and compute these exactly (e.g. 2->128 instead of 2->124) 316 // 317 const int coverageL = coverage_to_alpha(xleft) << SHIFT; 318 const int coverageR = coverage_to_alpha(xrite) << SHIFT; 319 SkASSERT(n + (coverageR != 0) <= fWidth); 320 321 for (int i = start_y; i < stop_y; ++i) { 322 // note: we should only need to call set_left_rite once, but 323 // our clipping blitters sometimes modify runs/alpha in-place, 324 // so for now we reset fRuns each time :( 325 // 326 // TODO: 327 // - don't modify in-place, or at least tell us when you're going to 328 // - pass height down to blitAntiH (blitAntiHV) so that aaclip and 329 // other can take advantage of the vertical-repeat explicitly 330 // 331 set_left_rite_runs(fRuns, ileft, coverageL, n, coverageR); 332 fRealBlitter->blitAntiH(fLeft, i, fRuns.fAlpha, fRuns.fRuns); 333 } 334 335 // preamble for our next call to blitH() 336 fCurrIY = stop_y - 1; 337 fOffsetX = 0; 338 fCurrY = y - 1; 339 fRuns.reset(fWidth); 340 x = origX; 341 } 342 343 // catch any remaining few 344 SkASSERT(height <= MASK); 345 while (--height >= 0) { 346 this->blitH(x, y++, width); 347 } 348} 349 350/////////////////////////////////////////////////////////////////////////////// 351 352/// Masked supersampling antialiased blitter. 353class MaskSuperBlitter : public BaseSuperBlitter { 354public: 355 MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 356 const SkRegion& clip); 357 virtual ~MaskSuperBlitter() { 358 fRealBlitter->blitMask(fMask, fClipRect); 359 } 360 361 virtual void blitH(int x, int y, int width) SK_OVERRIDE; 362 363 static bool CanHandleRect(const SkIRect& bounds) { 364#ifdef FORCE_RLE 365 return false; 366#endif 367 int width = bounds.width(); 368 int rb = SkAlign4(width); 369 370 return (width <= MaskSuperBlitter::kMAX_WIDTH) && 371 (rb * bounds.height() <= MaskSuperBlitter::kMAX_STORAGE); 372 } 373 374private: 375 enum { 376#ifdef FORCE_SUPERMASK 377 kMAX_WIDTH = 2048, 378 kMAX_STORAGE = 1024 * 1024 * 2 379#else 380 kMAX_WIDTH = 32, // so we don't try to do very wide things, where the RLE blitter would be faster 381 kMAX_STORAGE = 1024 382#endif 383 }; 384 385 SkMask fMask; 386 SkIRect fClipRect; 387 // we add 1 because add_aa_span can write (unchanged) 1 extra byte at the end, rather than 388 // perform a test to see if stopAlpha != 0 389 uint32_t fStorage[(kMAX_STORAGE >> 2) + 1]; 390}; 391 392MaskSuperBlitter::MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 393 const SkRegion& clip) 394 : BaseSuperBlitter(realBlitter, ir, clip) { 395 SkASSERT(CanHandleRect(ir)); 396 397 fMask.fImage = (uint8_t*)fStorage; 398 fMask.fBounds = ir; 399 fMask.fRowBytes = ir.width(); 400 fMask.fFormat = SkMask::kA8_Format; 401 402 fClipRect = ir; 403 fClipRect.intersect(clip.getBounds()); 404 405 // For valgrind, write 1 extra byte at the end so we don't read 406 // uninitialized memory. See comment in add_aa_span and fStorage[]. 407 memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 1); 408} 409 410static void add_aa_span(uint8_t* alpha, U8CPU startAlpha) { 411 /* I should be able to just add alpha[x] + startAlpha. 412 However, if the trailing edge of the previous span and the leading 413 edge of the current span round to the same super-sampled x value, 414 I might overflow to 256 with this add, hence the funny subtract. 415 */ 416 unsigned tmp = *alpha + startAlpha; 417 SkASSERT(tmp <= 256); 418 *alpha = SkToU8(tmp - (tmp >> 8)); 419} 420 421static inline uint32_t quadplicate_byte(U8CPU value) { 422 uint32_t pair = (value << 8) | value; 423 return (pair << 16) | pair; 424} 425 426// minimum count before we want to setup an inner loop, adding 4-at-a-time 427#define MIN_COUNT_FOR_QUAD_LOOP 16 428 429static void add_aa_span(uint8_t* alpha, U8CPU startAlpha, int middleCount, 430 U8CPU stopAlpha, U8CPU maxValue) { 431 SkASSERT(middleCount >= 0); 432 433 /* I should be able to just add alpha[x] + startAlpha. 434 However, if the trailing edge of the previous span and the leading 435 edge of the current span round to the same super-sampled x value, 436 I might overflow to 256 with this add, hence the funny subtract. 437 */ 438#ifdef SK_SUPPORT_NEW_AA 439 if (startAlpha) { 440 unsigned tmp = *alpha + startAlpha; 441 SkASSERT(tmp <= 256); 442 *alpha++ = SkToU8(tmp - (tmp >> 8)); 443 } 444#else 445 unsigned tmp = *alpha + startAlpha; 446 SkASSERT(tmp <= 256); 447 *alpha++ = SkToU8(tmp - (tmp >> 8)); 448#endif 449 450 if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) { 451 // loop until we're quad-byte aligned 452 while (SkTCast<intptr_t>(alpha) & 0x3) { 453 alpha[0] = SkToU8(alpha[0] + maxValue); 454 alpha += 1; 455 middleCount -= 1; 456 } 457 458 int bigCount = middleCount >> 2; 459 uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha); 460 uint32_t qval = quadplicate_byte(maxValue); 461 do { 462 *qptr++ += qval; 463 } while (--bigCount > 0); 464 465 middleCount &= 3; 466 alpha = reinterpret_cast<uint8_t*> (qptr); 467 // fall through to the following while-loop 468 } 469 470 while (--middleCount >= 0) { 471 alpha[0] = SkToU8(alpha[0] + maxValue); 472 alpha += 1; 473 } 474 475 // potentially this can be off the end of our "legal" alpha values, but that 476 // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0 477 // every time (slow), we just do it, and ensure that we've allocated extra space 478 // (see the + 1 comment in fStorage[] 479 *alpha = SkToU8(*alpha + stopAlpha); 480} 481 482void MaskSuperBlitter::blitH(int x, int y, int width) { 483 int iy = (y >> SHIFT); 484 485 SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom); 486 iy -= fMask.fBounds.fTop; // make it relative to 0 487 488 // This should never happen, but it does. Until the true cause is 489 // discovered, let's skip this span instead of crashing. 490 // See http://crbug.com/17569. 491 if (iy < 0) { 492 return; 493 } 494 495#ifdef SK_DEBUG 496 { 497 int ix = x >> SHIFT; 498 SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight); 499 } 500#endif 501 502 x -= (fMask.fBounds.fLeft << SHIFT); 503 504 // hack, until I figure out why my cubics (I think) go beyond the bounds 505 if (x < 0) { 506 width += x; 507 x = 0; 508 } 509 510 // we sub 1 from maxValue 1 time for each block, so that we don't 511 // hit 256 as a summed max, but 255. 512// int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT); 513 514 uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT); 515 516 int start = x; 517 int stop = x + width; 518 519 SkASSERT(start >= 0 && stop > start); 520 int fb = start & MASK; 521 int fe = stop & MASK; 522 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 523 524 525 if (n < 0) { 526 SkASSERT(row >= fMask.fImage); 527 SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1); 528 add_aa_span(row, coverage_to_alpha(fe - fb)); 529 } else { 530#ifdef SK_SUPPORT_NEW_AA 531 if (0 == fb) { 532 n += 1; 533 } else { 534 fb = (1 << SHIFT) - fb; 535 } 536#else 537 fb = (1 << SHIFT) - fb; 538#endif 539 SkASSERT(row >= fMask.fImage); 540 SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1); 541 add_aa_span(row, coverage_to_alpha(fb), n, coverage_to_alpha(fe), 542 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT)); 543 } 544 545#ifdef SK_DEBUG 546 fCurrX = x + width; 547#endif 548} 549 550/////////////////////////////////////////////////////////////////////////////// 551 552/* Returns non-zero if (value << shift) overflows a short, which would mean 553 we could not shift it up and then convert to SkFixed. 554 i.e. is x expressible as signed (16-shift) bits? 555 */ 556static int overflows_short_shift(int value, int shift) { 557 const int s = 16 + shift; 558 return (value << s >> s) - value; 559} 560 561void SkScan::AntiFillPath(const SkPath& path, const SkRegion& clip, 562 SkBlitter* blitter, bool forceRLE) { 563 if (clip.isEmpty()) { 564 return; 565 } 566 567 SkIRect ir; 568 path.getBounds().roundOut(&ir); 569 if (ir.isEmpty()) { 570 return; 571 } 572 573 // use bit-or since we expect all to pass, so no need to go slower with 574 // a short-circuiting logical-or 575 if (overflows_short_shift(ir.fLeft, SHIFT) | 576 overflows_short_shift(ir.fRight, SHIFT) | 577 overflows_short_shift(ir.fTop, SHIFT) | 578 overflows_short_shift(ir.fBottom, SHIFT)) { 579 // can't supersample, so draw w/o antialiasing 580 SkScan::FillPath(path, clip, blitter); 581 return; 582 } 583 584 SkScanClipper clipper(blitter, &clip, ir); 585 const SkIRect* clipRect = clipper.getClipRect(); 586 587 if (clipper.getBlitter() == NULL) { // clipped out 588 if (path.isInverseFillType()) { 589 blitter->blitRegion(clip); 590 } 591 return; 592 } 593 594 // now use the (possibly wrapped) blitter 595 blitter = clipper.getBlitter(); 596 597 if (path.isInverseFillType()) { 598 sk_blit_above(blitter, ir, clip); 599 } 600 601 SkIRect superRect, *superClipRect = NULL; 602 603 if (clipRect) { 604 superRect.set( clipRect->fLeft << SHIFT, clipRect->fTop << SHIFT, 605 clipRect->fRight << SHIFT, clipRect->fBottom << SHIFT); 606 superClipRect = &superRect; 607 } 608 609 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 610 611 // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it 612 // if we're an inverse filltype 613 if (!path.isInverseFillType() && MaskSuperBlitter::CanHandleRect(ir) && !forceRLE) { 614 MaskSuperBlitter superBlit(blitter, ir, clip); 615 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 616 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 617 } else { 618 SuperBlitter superBlit(blitter, ir, clip); 619 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 620 } 621 622 if (path.isInverseFillType()) { 623 sk_blit_below(blitter, ir, clip); 624 } 625} 626 627/////////////////////////////////////////////////////////////////////////////// 628 629#include "SkRasterClip.h" 630 631void SkScan::FillPath(const SkPath& path, const SkRasterClip& clip, 632 SkBlitter* blitter) { 633 if (clip.isEmpty()) { 634 return; 635 } 636 637 if (clip.isBW()) { 638 FillPath(path, clip.bwRgn(), blitter); 639 } else { 640 SkRegion tmp; 641 SkAAClipBlitter aaBlitter; 642 643 tmp.setRect(clip.getBounds()); 644 aaBlitter.init(blitter, &clip.aaRgn()); 645 SkScan::FillPath(path, tmp, &aaBlitter); 646 } 647} 648 649void SkScan::AntiFillPath(const SkPath& path, const SkRasterClip& clip, 650 SkBlitter* blitter) { 651 if (clip.isEmpty()) { 652 return; 653 } 654 655 if (clip.isBW()) { 656 AntiFillPath(path, clip.bwRgn(), blitter); 657 } else { 658 SkRegion tmp; 659 SkAAClipBlitter aaBlitter; 660 661 tmp.setRect(clip.getBounds()); 662 aaBlitter.init(blitter, &clip.aaRgn()); 663 SkScan::AntiFillPath(path, tmp, &aaBlitter, true); 664 } 665} 666 667