SkScan_AntiPath.cpp revision 562a2ac95b8cd8b359574f8c4d6300b0475938db
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/* 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 NEW_AA is a set of code-changes to try to make both paths produce identical 29 results. Its not quite there yet, though the remaining differences may be 30 in the subsequent blits, and not in the different masks/runs... 31 */ 32//#define FORCE_SUPERMASK 33//#define FORCE_RLE 34//#define SK_SUPPORT_NEW_AA 35 36/////////////////////////////////////////////////////////////////////////////// 37 38class BaseSuperBlitter : public SkBlitter { 39public: 40 BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 41 const SkRegion& clip); 42 43 virtual void blitAntiH(int x, int y, const SkAlpha antialias[], 44 const int16_t runs[]) { 45 SkASSERT(!"How did I get here?"); 46 } 47 virtual void blitV(int x, int y, int height, SkAlpha alpha) { 48 SkASSERT(!"How did I get here?"); 49 } 50 51protected: 52 SkBlitter* fRealBlitter; 53 int fCurrIY; 54 int fWidth, fLeft, fSuperLeft; 55 56 SkDEBUGCODE(int fCurrX;) 57 int fCurrY; 58 int fTop; 59}; 60 61BaseSuperBlitter::BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 62 const SkRegion& clip) { 63 fRealBlitter = realBlitter; 64 65 // take the union of the ir bounds and clip, since we may be called with an 66 // inverse filltype 67 const int left = SkMin32(ir.fLeft, clip.getBounds().fLeft); 68 const int right = SkMax32(ir.fRight, clip.getBounds().fRight); 69 70 fLeft = left; 71 fSuperLeft = left << SHIFT; 72 fWidth = right - left; 73#if 0 74 fCurrIY = -1; 75 fCurrY = -1; 76#else 77 fTop = ir.fTop; 78 fCurrIY = ir.fTop - 1; 79 fCurrY = (ir.fTop << SHIFT) - 1; 80#endif 81 SkDEBUGCODE(fCurrX = -1;) 82} 83 84class SuperBlitter : public BaseSuperBlitter { 85public: 86 SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 87 const SkRegion& clip); 88 89 virtual ~SuperBlitter() { 90 this->flush(); 91 sk_free(fRuns.fRuns); 92 } 93 94 void flush(); 95 96 virtual void blitH(int x, int y, int width); 97 98private: 99 SkAlphaRuns fRuns; 100 int fOffsetX; 101}; 102 103SuperBlitter::SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 104 const SkRegion& clip) 105 : BaseSuperBlitter(realBlitter, ir, clip) { 106 const int width = fWidth; 107 108 // extra one to store the zero at the end 109 fRuns.fRuns = (int16_t*)sk_malloc_throw((width + 1 + (width + 2)/2) * sizeof(int16_t)); 110 fRuns.fAlpha = (uint8_t*)(fRuns.fRuns + width + 1); 111 fRuns.reset(width); 112 113 fOffsetX = 0; 114} 115 116void SuperBlitter::flush() { 117 if (fCurrIY >= fTop) { 118 if (!fRuns.empty()) { 119 // SkDEBUGCODE(fRuns.dump();) 120 fRealBlitter->blitAntiH(fLeft, fCurrIY, fRuns.fAlpha, fRuns.fRuns); 121 fRuns.reset(fWidth); 122 fOffsetX = 0; 123 } 124 fCurrIY = fTop - 1; 125 SkDEBUGCODE(fCurrX = -1;) 126 } 127} 128 129static inline int coverage_to_alpha(int aa) { 130 aa <<= 8 - 2*SHIFT; 131 aa -= aa >> (8 - SHIFT - 1); 132 return aa; 133} 134 135#define SUPER_Mask ((1 << SHIFT) - 1) 136 137void SuperBlitter::blitH(int x, int y, int width) { 138 int iy = y >> SHIFT; 139 SkASSERT(iy >= fCurrIY); 140 141 x -= fSuperLeft; 142 // hack, until I figure out why my cubics (I think) go beyond the bounds 143 if (x < 0) { 144 width += x; 145 x = 0; 146 } 147 148#ifdef SK_DEBUG 149 SkASSERT(y != fCurrY || x >= fCurrX); 150#endif 151 SkASSERT(y >= fCurrY); 152 if (fCurrY != y) { 153 fOffsetX = 0; 154 fCurrY = y; 155 } 156 157 if (iy != fCurrIY) { // new scanline 158 this->flush(); 159 fCurrIY = iy; 160 } 161 162 // we sub 1 from maxValue 1 time for each block, so that we don't 163 // hit 256 as a summed max, but 255. 164// int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT); 165 166 int start = x; 167 int stop = x + width; 168 169 SkASSERT(start >= 0 && stop > start); 170 int fb = start & SUPER_Mask; 171 int fe = stop & SUPER_Mask; 172 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 173 174 if (n < 0) { 175 fb = fe - fb; 176 n = 0; 177 fe = 0; 178 } else { 179 if (fb == 0) { 180 n += 1; 181 } else { 182 fb = (1 << SHIFT) - fb; 183 } 184 } 185 186 fOffsetX = fRuns.add(x >> SHIFT, coverage_to_alpha(fb), n, coverage_to_alpha(fe), 187 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT), 188 fOffsetX); 189 190#ifdef SK_DEBUG 191 fRuns.assertValid(y & MASK, (1 << (8 - SHIFT))); 192 fCurrX = x + width; 193#endif 194} 195 196/////////////////////////////////////////////////////////////////////////////// 197 198class MaskSuperBlitter : public BaseSuperBlitter { 199public: 200 MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 201 const SkRegion& clip); 202 virtual ~MaskSuperBlitter() { 203 fRealBlitter->blitMask(fMask, fClipRect); 204 } 205 206 virtual void blitH(int x, int y, int width); 207 208 static bool CanHandleRect(const SkIRect& bounds) { 209#ifdef FORCE_RLE 210 return false; 211#endif 212 int width = bounds.width(); 213 int rb = SkAlign4(width); 214 215 return (width <= MaskSuperBlitter::kMAX_WIDTH) && 216 (rb * bounds.height() <= MaskSuperBlitter::kMAX_STORAGE); 217 } 218 219private: 220 enum { 221#ifdef FORCE_SUPERMASK 222 kMAX_WIDTH = 2048, 223 kMAX_STORAGE = 1024 * 1024 * 2 224#else 225 kMAX_WIDTH = 32, // so we don't try to do very wide things, where the RLE blitter would be faster 226 kMAX_STORAGE = 1024 227#endif 228 }; 229 230 SkMask fMask; 231 SkIRect fClipRect; 232 // we add 1 because add_aa_span can write (unchanged) 1 extra byte at the end, rather than 233 // perform a test to see if stopAlpha != 0 234 uint32_t fStorage[(kMAX_STORAGE >> 2) + 1]; 235}; 236 237MaskSuperBlitter::MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 238 const SkRegion& clip) 239 : BaseSuperBlitter(realBlitter, ir, clip) { 240 SkASSERT(CanHandleRect(ir)); 241 242 fMask.fImage = (uint8_t*)fStorage; 243 fMask.fBounds = ir; 244 fMask.fRowBytes = ir.width(); 245 fMask.fFormat = SkMask::kA8_Format; 246 247 fClipRect = ir; 248 fClipRect.intersect(clip.getBounds()); 249 250 // For valgrind, write 1 extra byte at the end so we don't read 251 // uninitialized memory. See comment in add_aa_span and fStorage[]. 252 memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 1); 253} 254 255static void add_aa_span(uint8_t* alpha, U8CPU startAlpha) { 256 /* I should be able to just add alpha[x] + startAlpha. 257 However, if the trailing edge of the previous span and the leading 258 edge of the current span round to the same super-sampled x value, 259 I might overflow to 256 with this add, hence the funny subtract. 260 */ 261 unsigned tmp = *alpha + startAlpha; 262 SkASSERT(tmp <= 256); 263 *alpha = SkToU8(tmp - (tmp >> 8)); 264} 265 266static inline uint32_t quadplicate_byte(U8CPU value) { 267 uint32_t pair = (value << 8) | value; 268 return (pair << 16) | pair; 269} 270 271// minimum count before we want to setup an inner loop, adding 4-at-a-time 272#define MIN_COUNT_FOR_QUAD_LOOP 16 273 274static void add_aa_span(uint8_t* alpha, U8CPU startAlpha, int middleCount, 275 U8CPU stopAlpha, U8CPU maxValue) { 276 SkASSERT(middleCount >= 0); 277 278 /* I should be able to just add alpha[x] + startAlpha. 279 However, if the trailing edge of the previous span and the leading 280 edge of the current span round to the same super-sampled x value, 281 I might overflow to 256 with this add, hence the funny subtract. 282 */ 283#ifdef SK_SUPPORT_NEW_AA 284 if (startAlpha) { 285 unsigned tmp = *alpha + startAlpha; 286 SkASSERT(tmp <= 256); 287 *alpha++ = SkToU8(tmp - (tmp >> 8)); 288 } 289#else 290 unsigned tmp = *alpha + startAlpha; 291 SkASSERT(tmp <= 256); 292 *alpha++ = SkToU8(tmp - (tmp >> 8)); 293#endif 294 295 if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) { 296 // loop until we're quad-byte aligned 297 while (SkTCast<intptr_t>(alpha) & 0x3) { 298 alpha[0] = SkToU8(alpha[0] + maxValue); 299 alpha += 1; 300 middleCount -= 1; 301 } 302 303 int bigCount = middleCount >> 2; 304 uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha); 305 uint32_t qval = quadplicate_byte(maxValue); 306 do { 307 *qptr++ += qval; 308 } while (--bigCount > 0); 309 310 middleCount &= 3; 311 alpha = reinterpret_cast<uint8_t*> (qptr); 312 // fall through to the following while-loop 313 } 314 315 while (--middleCount >= 0) { 316 alpha[0] = SkToU8(alpha[0] + maxValue); 317 alpha += 1; 318 } 319 320 // potentially this can be off the end of our "legal" alpha values, but that 321 // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0 322 // every time (slow), we just do it, and ensure that we've allocated extra space 323 // (see the + 1 comment in fStorage[] 324 *alpha = SkToU8(*alpha + stopAlpha); 325} 326 327void MaskSuperBlitter::blitH(int x, int y, int width) { 328 int iy = (y >> SHIFT); 329 330 SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom); 331 iy -= fMask.fBounds.fTop; // make it relative to 0 332 333 // This should never happen, but it does. Until the true cause is 334 // discovered, let's skip this span instead of crashing. 335 // See http://crbug.com/17569. 336 if (iy < 0) { 337 return; 338 } 339 340#ifdef SK_DEBUG 341 { 342 int ix = x >> SHIFT; 343 SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight); 344 } 345#endif 346 347 x -= (fMask.fBounds.fLeft << SHIFT); 348 349 // hack, until I figure out why my cubics (I think) go beyond the bounds 350 if (x < 0) { 351 width += x; 352 x = 0; 353 } 354 355 // we sub 1 from maxValue 1 time for each block, so that we don't 356 // hit 256 as a summed max, but 255. 357// int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT); 358 359 uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT); 360 361 int start = x; 362 int stop = x + width; 363 364 SkASSERT(start >= 0 && stop > start); 365 int fb = start & SUPER_Mask; 366 int fe = stop & SUPER_Mask; 367 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 368 369 370 if (n < 0) { 371 SkASSERT(row >= fMask.fImage); 372 SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1); 373 add_aa_span(row, coverage_to_alpha(fe - fb)); 374 } else { 375#ifdef SK_SUPPORT_NEW_AA 376 if (0 == fb) { 377 n += 1; 378 } else { 379 fb = (1 << SHIFT) - fb; 380 } 381#else 382 fb = (1 << SHIFT) - fb; 383#endif 384 SkASSERT(row >= fMask.fImage); 385 SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1); 386 add_aa_span(row, coverage_to_alpha(fb), n, coverage_to_alpha(fe), 387 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT)); 388 } 389 390#ifdef SK_DEBUG 391 fCurrX = x + width; 392#endif 393} 394 395/////////////////////////////////////////////////////////////////////////////// 396 397/* Returns non-zero if (value << shift) overflows a short, which would mean 398 we could not shift it up and then convert to SkFixed. 399 i.e. is x expressible as signed (16-shift) bits? 400 */ 401static int overflows_short_shift(int value, int shift) { 402 const int s = 16 + shift; 403 return (value << s >> s) - value; 404} 405 406void SkScan::AntiFillPath(const SkPath& path, const SkRegion& clip, 407 SkBlitter* blitter, bool forceRLE) { 408 if (clip.isEmpty()) { 409 return; 410 } 411 412 SkIRect ir; 413 path.getBounds().roundOut(&ir); 414 if (ir.isEmpty()) { 415 return; 416 } 417 418 // use bit-or since we expect all to pass, so no need to go slower with 419 // a short-circuiting logical-or 420 if (overflows_short_shift(ir.fLeft, SHIFT) | 421 overflows_short_shift(ir.fRight, SHIFT) | 422 overflows_short_shift(ir.fTop, SHIFT) | 423 overflows_short_shift(ir.fBottom, SHIFT)) { 424 // can't supersample, so draw w/o antialiasing 425 SkScan::FillPath(path, clip, blitter); 426 return; 427 } 428 429 SkScanClipper clipper(blitter, &clip, ir); 430 const SkIRect* clipRect = clipper.getClipRect(); 431 432 if (clipper.getBlitter() == NULL) { // clipped out 433 if (path.isInverseFillType()) { 434 blitter->blitRegion(clip); 435 } 436 return; 437 } 438 439 // now use the (possibly wrapped) blitter 440 blitter = clipper.getBlitter(); 441 442 if (path.isInverseFillType()) { 443 sk_blit_above(blitter, ir, clip); 444 } 445 446 SkIRect superRect, *superClipRect = NULL; 447 448 if (clipRect) { 449 superRect.set( clipRect->fLeft << SHIFT, clipRect->fTop << SHIFT, 450 clipRect->fRight << SHIFT, clipRect->fBottom << SHIFT); 451 superClipRect = &superRect; 452 } 453 454 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 455 456 // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it 457 // if we're an inverse filltype 458 if (!path.isInverseFillType() && MaskSuperBlitter::CanHandleRect(ir) && !forceRLE) { 459 MaskSuperBlitter superBlit(blitter, ir, clip); 460 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 461 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 462 } else { 463 SuperBlitter superBlit(blitter, ir, clip); 464 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 465 } 466 467 if (path.isInverseFillType()) { 468 sk_blit_below(blitter, ir, clip); 469 } 470} 471 472/////////////////////////////////////////////////////////////////////////////// 473 474#include "SkRasterClip.h" 475 476void SkScan::FillPath(const SkPath& path, const SkRasterClip& clip, 477 SkBlitter* blitter) { 478 if (clip.isEmpty()) { 479 return; 480 } 481 482 if (clip.isBW()) { 483 FillPath(path, clip.bwRgn(), blitter); 484 } else { 485 SkRegion tmp; 486 SkAAClipBlitter aaBlitter; 487 488 tmp.setRect(clip.getBounds()); 489 aaBlitter.init(blitter, &clip.aaRgn()); 490 SkScan::FillPath(path, tmp, &aaBlitter); 491 } 492} 493 494void SkScan::AntiFillPath(const SkPath& path, const SkRasterClip& clip, 495 SkBlitter* blitter) { 496 if (clip.isEmpty()) { 497 return; 498 } 499 500 if (clip.isBW()) { 501 AntiFillPath(path, clip.bwRgn(), blitter); 502 } else { 503 SkRegion tmp; 504 SkAAClipBlitter aaBlitter; 505 506 tmp.setRect(clip.getBounds()); 507 aaBlitter.init(blitter, &clip.aaRgn()); 508 SkScan::AntiFillPath(path, tmp, &aaBlitter, true); 509 } 510} 511 512