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