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