SkScan_AntiPath.cpp revision 9f2f0a84d5a1b7c67c1d2a253bc2d7ee6f3f4625
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//#define FORCE_SUPERMASK 30//#define FORCE_RLE 31 32/////////////////////////////////////////////////////////////////////////////// 33 34class BaseSuperBlitter : public SkBlitter { 35public: 36 BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 37 const SkRegion& clip); 38 39 virtual void blitAntiH(int x, int y, const SkAlpha antialias[], 40 const int16_t runs[]) { 41 SkASSERT(!"How did I get here?"); 42 } 43 virtual void blitV(int x, int y, int height, SkAlpha alpha) { 44 SkASSERT(!"How did I get here?"); 45 } 46 virtual void blitRect(int x, int y, int width, int height) { 47 SkASSERT(!"How did I get here?"); 48 } 49 50protected: 51 SkBlitter* fRealBlitter; 52 int fCurrIY; 53 int fWidth, fLeft, fSuperLeft; 54 55 SkDEBUGCODE(int fCurrX;) 56 SkDEBUGCODE(int fCurrY;) 57}; 58 59BaseSuperBlitter::BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 60 const SkRegion& clip) { 61 fRealBlitter = realBlitter; 62 63 // take the union of the ir bounds and clip, since we may be called with an 64 // inverse filltype 65 const int left = SkMin32(ir.fLeft, clip.getBounds().fLeft); 66 const int right = SkMax32(ir.fRight, clip.getBounds().fRight); 67 68 fLeft = left; 69 fSuperLeft = left << SHIFT; 70 fWidth = right - left; 71 fCurrIY = -1; 72 SkDEBUGCODE(fCurrX = -1; fCurrY = -1;) 73} 74 75class SuperBlitter : public BaseSuperBlitter { 76public: 77 SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 78 const SkRegion& clip); 79 80 virtual ~SuperBlitter() { 81 this->flush(); 82 sk_free(fRuns.fRuns); 83 } 84 85 void flush(); 86 87 virtual void blitH(int x, int y, int width); 88 virtual void blitRect(int x, int y, int width, int height); 89 90private: 91 SkAlphaRuns fRuns; 92}; 93 94SuperBlitter::SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir, 95 const SkRegion& clip) 96 : BaseSuperBlitter(realBlitter, ir, clip) { 97 const int width = fWidth; 98 99 // extra one to store the zero at the end 100 fRuns.fRuns = (int16_t*)sk_malloc_throw((width + 1 + (width + 2)/2) * sizeof(int16_t)); 101 fRuns.fAlpha = (uint8_t*)(fRuns.fRuns + width + 1); 102 fRuns.reset(width); 103} 104 105void SuperBlitter::flush() { 106 if (fCurrIY >= 0) { 107 if (!fRuns.empty()) { 108 // SkDEBUGCODE(fRuns.dump();) 109 fRealBlitter->blitAntiH(fLeft, fCurrIY, fRuns.fAlpha, fRuns.fRuns); 110 fRuns.reset(fWidth); 111 } 112 fCurrIY = -1; 113 SkDEBUGCODE(fCurrX = -1;) 114 } 115} 116 117static inline int coverage_to_alpha(int aa) { 118 aa <<= 8 - 2*SHIFT; 119 aa -= aa >> (8 - SHIFT - 1); 120 return aa; 121} 122 123#define SUPER_Mask ((1 << SHIFT) - 1) 124 125void SuperBlitter::blitH(int x, int y, int width) { 126 int iy = y >> SHIFT; 127 SkASSERT(iy >= fCurrIY); 128 129 x -= fSuperLeft; 130 // hack, until I figure out why my cubics (I think) go beyond the bounds 131 if (x < 0) { 132 width += x; 133 x = 0; 134 } 135 136#ifdef SK_DEBUG 137 SkASSERT(y >= fCurrY); 138 SkASSERT(y != fCurrY || x >= fCurrX); 139 fCurrY = y; 140#endif 141 142 if (iy != fCurrIY) { // new scanline 143 this->flush(); 144 fCurrIY = iy; 145 } 146 147 // we sub 1 from maxValue 1 time for each block, so that we don't 148 // hit 256 as a summed max, but 255. 149// int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT); 150 151#if 0 152 SkAntiRun<SHIFT> arun; 153 arun.set(x, x + width); 154 fRuns.add(x >> SHIFT, arun.getStartAlpha(), arun.getMiddleCount(), 155 arun.getStopAlpha(), maxValue); 156#else 157 { 158 int start = x; 159 int stop = x + width; 160 161 SkASSERT(start >= 0 && stop > start); 162 int fb = start & SUPER_Mask; 163 int fe = stop & SUPER_Mask; 164 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 165 166 if (n < 0) { 167 fb = fe - fb; 168 n = 0; 169 fe = 0; 170 } else { 171 if (fb == 0) { 172 n += 1; 173 } else { 174 fb = (1 << SHIFT) - fb; 175 } 176 } 177 fRuns.add(x >> SHIFT, coverage_to_alpha(fb), n, coverage_to_alpha(fe), 178 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT)); 179 } 180#endif 181 182#ifdef SK_DEBUG 183 fRuns.assertValid(y & MASK, (1 << (8 - SHIFT))); 184 fCurrX = x + width; 185#endif 186} 187 188void SuperBlitter::blitRect(int x, int y, int width, int height) { 189 for (int i = 0; i < height; ++i) { 190 blitH(x, y + i, width); 191 } 192 193 flush(); 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 unsigned tmp = *alpha + startAlpha; 284 SkASSERT(tmp <= 256); 285 *alpha++ = SkToU8(tmp - (tmp >> 8)); 286 287 if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) { 288 // loop until we're quad-byte aligned 289 while (SkTCast<intptr_t>(alpha) & 0x3) { 290 alpha[0] = SkToU8(alpha[0] + maxValue); 291 alpha += 1; 292 middleCount -= 1; 293 } 294 295 int bigCount = middleCount >> 2; 296 uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha); 297 uint32_t qval = quadplicate_byte(maxValue); 298 do { 299 *qptr++ += qval; 300 } while (--bigCount > 0); 301 302 middleCount &= 3; 303 alpha = reinterpret_cast<uint8_t*> (qptr); 304 // fall through to the following while-loop 305 } 306 307 while (--middleCount >= 0) { 308 alpha[0] = SkToU8(alpha[0] + maxValue); 309 alpha += 1; 310 } 311 312 // potentially this can be off the end of our "legal" alpha values, but that 313 // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0 314 // every time (slow), we just do it, and ensure that we've allocated extra space 315 // (see the + 1 comment in fStorage[] 316 *alpha = SkToU8(*alpha + stopAlpha); 317} 318 319void MaskSuperBlitter::blitH(int x, int y, int width) { 320 int iy = (y >> SHIFT); 321 322 SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom); 323 iy -= fMask.fBounds.fTop; // make it relative to 0 324 325 // This should never happen, but it does. Until the true cause is 326 // discovered, let's skip this span instead of crashing. 327 // See http://crbug.com/17569. 328 if (iy < 0) { 329 return; 330 } 331 332#ifdef SK_DEBUG 333 { 334 int ix = x >> SHIFT; 335 SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight); 336 } 337#endif 338 339 x -= (fMask.fBounds.fLeft << SHIFT); 340 341 // hack, until I figure out why my cubics (I think) go beyond the bounds 342 if (x < 0) { 343 width += x; 344 x = 0; 345 } 346 347 // we sub 1 from maxValue 1 time for each block, so that we don't 348 // hit 256 as a summed max, but 255. 349// int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT); 350 351 uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT); 352 353 int start = x; 354 int stop = x + width; 355 356 SkASSERT(start >= 0 && stop > start); 357 int fb = start & SUPER_Mask; 358 int fe = stop & SUPER_Mask; 359 int n = (stop >> SHIFT) - (start >> SHIFT) - 1; 360 361 362 if (n < 0) { 363 SkASSERT(row >= fMask.fImage); 364 SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1); 365 add_aa_span(row, coverage_to_alpha(fe - fb)); 366 } else { 367 fb = (1 << SHIFT) - fb; 368 SkASSERT(row >= fMask.fImage); 369 SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1); 370 add_aa_span(row, coverage_to_alpha(fb), n, coverage_to_alpha(fe), 371 (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT)); 372 } 373 374#ifdef SK_DEBUG 375 fCurrX = x + width; 376#endif 377} 378 379/////////////////////////////////////////////////////////////////////////////// 380 381/* Returns non-zero if (value << shift) overflows a short, which would mean 382 we could not shift it up and then convert to SkFixed. 383 i.e. is x expressible as signed (16-shift) bits? 384 */ 385static int overflows_short_shift(int value, int shift) { 386 const int s = 16 + shift; 387 return (value << s >> s) - value; 388} 389 390void SkScan::AntiFillPath(const SkPath& path, const SkRegion& clip, 391 SkBlitter* blitter) { 392 if (clip.isEmpty()) { 393 return; 394 } 395 396 SkIRect ir; 397 path.getBounds().roundOut(&ir); 398 if (ir.isEmpty()) { 399 return; 400 } 401 402 // use bit-or since we expect all to pass, so no need to go slower with 403 // a short-circuiting logical-or 404 if (overflows_short_shift(ir.fLeft, SHIFT) | 405 overflows_short_shift(ir.fRight, SHIFT) | 406 overflows_short_shift(ir.fTop, SHIFT) | 407 overflows_short_shift(ir.fBottom, SHIFT)) { 408 // can't supersample, so draw w/o antialiasing 409 SkScan::FillPath(path, clip, blitter); 410 return; 411 } 412 413 SkScanClipper clipper(blitter, &clip, ir); 414 const SkIRect* clipRect = clipper.getClipRect(); 415 416 if (clipper.getBlitter() == NULL) { // clipped out 417 if (path.isInverseFillType()) { 418 blitter->blitRegion(clip); 419 } 420 return; 421 } 422 423 // now use the (possibly wrapped) blitter 424 blitter = clipper.getBlitter(); 425 426 if (path.isInverseFillType()) { 427 sk_blit_above(blitter, ir, clip); 428 } 429 430 SkIRect superRect, *superClipRect = NULL; 431 432 if (clipRect) { 433 superRect.set( clipRect->fLeft << SHIFT, clipRect->fTop << SHIFT, 434 clipRect->fRight << SHIFT, clipRect->fBottom << SHIFT); 435 superClipRect = &superRect; 436 } 437 438 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 439 440 // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it 441 // if we're an inverse filltype 442 if (!path.isInverseFillType() && MaskSuperBlitter::CanHandleRect(ir)) { 443 MaskSuperBlitter superBlit(blitter, ir, clip); 444 SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop); 445 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 446 } else { 447 SuperBlitter superBlit(blitter, ir, clip); 448 sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip); 449 } 450 451 if (path.isInverseFillType()) { 452 sk_blit_below(blitter, ir, clip); 453 } 454} 455