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