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