src/core/SkScan_AntiPath.cpp

   1
   2 /*
   3  * Copyright 2006 The Android Open Source Project
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9
  10 #include "SkScanPriv.h"
  11 #include "SkPath.h"
  12 #include "SkMatrix.h"
  13 #include "SkBlitter.h"
  14 #include "SkRegion.h"
  15 #include "SkAntiRun.h"
  16
  17 #define SHIFT   2
  18 #define SCALE   (1 << SHIFT)
  19 #define MASK    (SCALE - 1)
  20
  21 /*
  22     We have two techniques for capturing the output of the supersampler:
  23     - SUPERMASK, which records a large mask-bitmap
  24         this is often faster for small, complex objects
  25     - RLE, which records a rle-encoded scanline
  26         this is often faster for large objects with big spans
  27
  28     NEW_AA is a set of code-changes to try to make both paths produce identical
  29     results. Its not quite there yet, though the remaining differences may be
  30     in the subsequent blits, and not in the different masks/runs...
  31  */
  32 //#define FORCE_SUPERMASK
  33 //#define FORCE_RLE
  34 //#define SK_SUPPORT_NEW_AA
  35
  36 ///////////////////////////////////////////////////////////////////////////////
  37
  38 class BaseSuperBlitter : public SkBlitter {
  39 public:
  40     BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
  41                      const SkRegion& clip);
  42
  43     virtual void blitAntiH(int x, int y, const SkAlpha antialias[],
  44                            const int16_t runs[]) SK_OVERRIDE {
  45         SkASSERT(!"How did I get here?");
  46     }
  47     virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE {
  48         SkASSERT(!"How did I get here?");
  49     }
  50
  51 protected:
  52     SkBlitter*  fRealBlitter;
  53     int         fCurrIY;
  54     int         fWidth, fLeft, fSuperLeft;
  55
  56     SkDEBUGCODE(int fCurrX;)
  57     int fCurrY;
  58     int fTop;
  59 };
  60
  61 BaseSuperBlitter::BaseSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
  62                                    const SkRegion& clip) {
  63     fRealBlitter = realBlitter;
  64
  65     // take the union of the ir bounds and clip, since we may be called with an
  66     // inverse filltype
  67     const int left = SkMin32(ir.fLeft, clip.getBounds().fLeft);
  68     const int right = SkMax32(ir.fRight, clip.getBounds().fRight);
  69
  70     fLeft = left;
  71     fSuperLeft = left << SHIFT;
  72     fWidth = right - left;
  73 #if 0
  74     fCurrIY = -1;
  75     fCurrY = -1;
  76 #else
  77     fTop = ir.fTop;
  78     fCurrIY = ir.fTop - 1;
  79     fCurrY = (ir.fTop << SHIFT) - 1;
  80 #endif
  81     SkDEBUGCODE(fCurrX = -1;)
  82 }
  83
  84 class SuperBlitter : public BaseSuperBlitter {
  85 public:
  86     SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
  87                  const SkRegion& clip);
  88
  89     virtual ~SuperBlitter() {
  90         this->flush();
  91         sk_free(fRuns.fRuns);
  92     }
  93
  94     void flush();
  95
  96     virtual void blitH(int x, int y, int width) SK_OVERRIDE;
  97     virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE;
  98
  99 private:
 100     SkAlphaRuns fRuns;
 101     int         fOffsetX;
 102 };
 103
 104 SuperBlitter::SuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
 105                            const SkRegion& clip)
 106         : BaseSuperBlitter(realBlitter, ir, clip) {
 107     const int width = fWidth;
 108
 109     // extra one to store the zero at the end
 110     fRuns.fRuns = (int16_t*)sk_malloc_throw((width + 1 + (width + 2)/2) * sizeof(int16_t));
 111     fRuns.fAlpha = (uint8_t*)(fRuns.fRuns + width + 1);
 112     fRuns.reset(width);
 113
 114     fOffsetX = 0;
 115 }
 116
 117 void SuperBlitter::flush() {
 118     if (fCurrIY >= fTop) {
 119         if (!fRuns.empty()) {
 120         //  SkDEBUGCODE(fRuns.dump();)
 121             fRealBlitter->blitAntiH(fLeft, fCurrIY, fRuns.fAlpha, fRuns.fRuns);
 122             fRuns.reset(fWidth);
 123             fOffsetX = 0;
 124         }
 125         fCurrIY = fTop - 1;
 126         SkDEBUGCODE(fCurrX = -1;)
 127     }
 128 }
 129
 130 static inline int coverage_to_alpha(int aa) {
 131     aa <<= 8 - 2*SHIFT;
 132     aa -= aa >> (8 - SHIFT - 1);
 133     return aa;
 134 }
 135
 136 #define SUPER_Mask      ((1 << SHIFT) - 1)
 137
 138 void SuperBlitter::blitH(int x, int y, int width) {
 139     SkASSERT(width > 0);
 140
 141     int iy = y >> SHIFT;
 142     SkASSERT(iy >= fCurrIY);
 143
 144     x -= fSuperLeft;
 145     // hack, until I figure out why my cubics (I think) go beyond the bounds
 146     if (x < 0) {
 147         width += x;
 148         x = 0;
 149     }
 150
 151 #ifdef SK_DEBUG
 152     SkASSERT(y != fCurrY || x >= fCurrX);
 153 #endif
 154     SkASSERT(y >= fCurrY);
 155     if (fCurrY != y) {
 156         fOffsetX = 0;
 157         fCurrY = y;
 158     }
 159
 160     if (iy != fCurrIY) {  // new scanline
 161         this->flush();
 162         fCurrIY = iy;
 163     }
 164
 165     // we sub 1 from maxValue 1 time for each block, so that we don't
 166     // hit 256 as a summed max, but 255.
 167 //  int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT);
 168
 169     int start = x;
 170     int stop = x + width;
 171
 172     SkASSERT(start >= 0 && stop > start);
 173     int fb = start & SUPER_Mask;
 174     int fe = stop & SUPER_Mask;
 175     int n = (stop >> SHIFT) - (start >> SHIFT) - 1;
 176
 177     if (n < 0) {
 178         fb = fe - fb;
 179         n = 0;
 180         fe = 0;
 181     } else {
 182         if (fb == 0) {
 183             n += 1;
 184         } else {
 185             fb = (1 << SHIFT) - fb;
 186         }
 187     }
 188
 189     fOffsetX = fRuns.add(x >> SHIFT, coverage_to_alpha(fb), n, coverage_to_alpha(fe),
 190                          (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT),
 191                          fOffsetX);
 192
 193 #ifdef SK_DEBUG
 194     fRuns.assertValid(y & MASK, (1 << (8 - SHIFT)));
 195     fCurrX = x + width;
 196 #endif
 197 }
 198
 199 static void set_left_rite_runs(SkAlphaRuns& runs, int ileft, U8CPU leftA,
 200                                int n, U8CPU riteA) {
 201     SkASSERT(leftA <= 0xFF);
 202     SkASSERT(riteA <= 0xFF);
 203
 204     int16_t* run = runs.fRuns;
 205     uint8_t* aa = runs.fAlpha;
 206
 207     if (ileft > 0) {
 208         run[0] = ileft;
 209         aa[0] = 0;
 210         run += ileft;
 211         aa += ileft;
 212     }
 213
 214     SkASSERT(leftA < 0xFF);
 215     if (leftA > 0) {
 216         *run++ = 1;
 217         *aa++ = leftA;
 218     }
 219
 220     if (n > 0) {
 221         run[0] = n;
 222         aa[0] = 0xFF;
 223         run += n;
 224         aa += n;
 225     }
 226
 227     SkASSERT(riteA < 0xFF);
 228     if (riteA > 0) {
 229         *run++ = 1;
 230         *aa++ = riteA;
 231     }
 232     run[0] = 0;
 233 }
 234
 235 void SuperBlitter::blitRect(int x, int y, int width, int height) {
 236     SkASSERT(width > 0);
 237     SkASSERT(height > 0);
 238
 239     while ((y & SUPER_Mask)) {
 240         this->blitH(x, y++, width);
 241         if (--height <= 0) {
 242             return;
 243         }
 244     }
 245     SkASSERT(height > 0);
 246
 247     int start_y = y >> SHIFT;
 248     int stop_y = (y + height) >> SHIFT;
 249     int count = stop_y - start_y;
 250     if (count > 0) {
 251         y += count << SHIFT;
 252         height -= count << SHIFT;
 253
 254         // save original X for our tail blitH() loop at the bottom
 255         int origX = x;
 256
 257         x -= fSuperLeft;
 258         // hack, until I figure out why my cubics (I think) go beyond the bounds
 259         if (x < 0) {
 260             width += x;
 261             x = 0;
 262         }
 263
 264         int ileft = x >> SHIFT;
 265         int xleft = x & SUPER_Mask;
 266         int irite = (x + width) >> SHIFT;
 267         int xrite = (x + width) & SUPER_Mask;
 268         int n = irite - ileft - 1;
 269         if (n < 0) {
 270             // only one pixel, call blitV()?
 271             xleft = xrite - xleft;
 272             n = 0;
 273             xrite = 0;
 274         } else {
 275             if (0 == xleft) {
 276                 n += 1;
 277             } else {
 278                 xleft = (1 << SHIFT) - xleft;
 279             }
 280         }
 281
 282         // here we go
 283         SkASSERT(start_y > fCurrIY);
 284         this->flush();
 285
 286         // to be compatible with the blitH() version, we just shift these
 287         // values up. If we didn't care about that, we could be more precise
 288         // and compute these exactly (e.g. 2->128 instead of 2->124)
 289         //
 290         const int coverageL = coverage_to_alpha(xleft) << SHIFT;
 291         const int coverageR = coverage_to_alpha(xrite) << SHIFT;
 292         SkASSERT(n + (coverageR != 0) <= fWidth);
 293
 294         for (int i = start_y; i < stop_y; ++i) {
 295             // note: we should only need to call set_left_rite once, but
 296             // our clipping blitters sometimes modify runs/alpha in-place,
 297             // so for now we reset fRuns each time :(
 298             //
 299             //  TODO:
 300             //  - don't modify in-place, or at least tell us when you're going to
 301             //  - pass height down to blitAntiH (blitAntiHV) so that aaclip and
 302             //    other can take advantage of the vertical-repeat explicitly
 303             //
 304             set_left_rite_runs(fRuns, ileft, coverageL, n, coverageR);
 305             fRealBlitter->blitAntiH(fLeft, i, fRuns.fAlpha, fRuns.fRuns);
 306         }
 307
 308         // preamble for our next call to blitH()
 309         fCurrIY = stop_y - 1;
 310         fOffsetX = 0;
 311         fCurrY = y - 1;
 312         fRuns.reset(fWidth);
 313         x = origX;
 314     }
 315
 316     // catch any remaining few
 317     SkASSERT(height <= SUPER_Mask);
 318     while (--height >= 0) {
 319         this->blitH(x, y++, width);
 320     }
 321 }
 322
 323 ///////////////////////////////////////////////////////////////////////////////
 324
 325 class MaskSuperBlitter : public BaseSuperBlitter {
 326 public:
 327     MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
 328                      const SkRegion& clip);
 329     virtual ~MaskSuperBlitter() {
 330         fRealBlitter->blitMask(fMask, fClipRect);
 331     }
 332
 333     virtual void blitH(int x, int y, int width) SK_OVERRIDE;
 334
 335     static bool CanHandleRect(const SkIRect& bounds) {
 336 #ifdef FORCE_RLE
 337         return false;
 338 #endif
 339         int width = bounds.width();
 340         int rb = SkAlign4(width);
 341
 342         return (width <= MaskSuperBlitter::kMAX_WIDTH) &&
 343         (rb * bounds.height() <= MaskSuperBlitter::kMAX_STORAGE);
 344     }
 345
 346 private:
 347     enum {
 348 #ifdef FORCE_SUPERMASK
 349         kMAX_WIDTH = 2048,
 350         kMAX_STORAGE = 1024 * 1024 * 2
 351 #else
 352         kMAX_WIDTH = 32,    // so we don't try to do very wide things, where the RLE blitter would be faster
 353         kMAX_STORAGE = 1024
 354 #endif
 355     };
 356
 357     SkMask      fMask;
 358     SkIRect     fClipRect;
 359     // we add 1 because add_aa_span can write (unchanged) 1 extra byte at the end, rather than
 360     // perform a test to see if stopAlpha != 0
 361     uint32_t    fStorage[(kMAX_STORAGE >> 2) + 1];
 362 };
 363
 364 MaskSuperBlitter::MaskSuperBlitter(SkBlitter* realBlitter, const SkIRect& ir,
 365                                    const SkRegion& clip)
 366         : BaseSuperBlitter(realBlitter, ir, clip) {
 367     SkASSERT(CanHandleRect(ir));
 368
 369     fMask.fImage    = (uint8_t*)fStorage;
 370     fMask.fBounds   = ir;
 371     fMask.fRowBytes = ir.width();
 372     fMask.fFormat   = SkMask::kA8_Format;
 373
 374     fClipRect = ir;
 375     fClipRect.intersect(clip.getBounds());
 376
 377     // For valgrind, write 1 extra byte at the end so we don't read
 378     // uninitialized memory. See comment in add_aa_span and fStorage[].
 379     memset(fStorage, 0, fMask.fBounds.height() * fMask.fRowBytes + 1);
 380 }
 381
 382 static void add_aa_span(uint8_t* alpha, U8CPU startAlpha) {
 383     /*  I should be able to just add alpha[x] + startAlpha.
 384         However, if the trailing edge of the previous span and the leading
 385         edge of the current span round to the same super-sampled x value,
 386         I might overflow to 256 with this add, hence the funny subtract.
 387     */
 388     unsigned tmp = *alpha + startAlpha;
 389     SkASSERT(tmp <= 256);
 390     *alpha = SkToU8(tmp - (tmp >> 8));
 391 }
 392
 393 static inline uint32_t quadplicate_byte(U8CPU value) {
 394     uint32_t pair = (value << 8) | value;
 395     return (pair << 16) | pair;
 396 }
 397
 398 // minimum count before we want to setup an inner loop, adding 4-at-a-time
 399 #define MIN_COUNT_FOR_QUAD_LOOP  16
 400
 401 static void add_aa_span(uint8_t* alpha, U8CPU startAlpha, int middleCount,
 402                         U8CPU stopAlpha, U8CPU maxValue) {
 403     SkASSERT(middleCount >= 0);
 404
 405     /*  I should be able to just add alpha[x] + startAlpha.
 406         However, if the trailing edge of the previous span and the leading
 407         edge of the current span round to the same super-sampled x value,
 408         I might overflow to 256 with this add, hence the funny subtract.
 409     */
 410 #ifdef SK_SUPPORT_NEW_AA
 411     if (startAlpha) {
 412         unsigned tmp = *alpha + startAlpha;
 413         SkASSERT(tmp <= 256);
 414         *alpha++ = SkToU8(tmp - (tmp >> 8));
 415     }
 416 #else
 417     unsigned tmp = *alpha + startAlpha;
 418     SkASSERT(tmp <= 256);
 419     *alpha++ = SkToU8(tmp - (tmp >> 8));
 420 #endif
 421
 422     if (middleCount >= MIN_COUNT_FOR_QUAD_LOOP) {
 423         // loop until we're quad-byte aligned
 424         while (SkTCast<intptr_t>(alpha) & 0x3) {
 425             alpha[0] = SkToU8(alpha[0] + maxValue);
 426             alpha += 1;
 427             middleCount -= 1;
 428         }
 429
 430         int bigCount = middleCount >> 2;
 431         uint32_t* qptr = reinterpret_cast<uint32_t*>(alpha);
 432         uint32_t qval = quadplicate_byte(maxValue);
 433         do {
 434             *qptr++ += qval;
 435         } while (--bigCount > 0);
 436
 437         middleCount &= 3;
 438         alpha = reinterpret_cast<uint8_t*> (qptr);
 439         // fall through to the following while-loop
 440     }
 441
 442     while (--middleCount >= 0) {
 443         alpha[0] = SkToU8(alpha[0] + maxValue);
 444         alpha += 1;
 445     }
 446
 447     // potentially this can be off the end of our "legal" alpha values, but that
 448     // only happens if stopAlpha is also 0. Rather than test for stopAlpha != 0
 449     // every time (slow), we just do it, and ensure that we've allocated extra space
 450     // (see the + 1 comment in fStorage[]
 451     *alpha = SkToU8(*alpha + stopAlpha);
 452 }
 453
 454 void MaskSuperBlitter::blitH(int x, int y, int width) {
 455     int iy = (y >> SHIFT);
 456
 457     SkASSERT(iy >= fMask.fBounds.fTop && iy < fMask.fBounds.fBottom);
 458     iy -= fMask.fBounds.fTop;   // make it relative to 0
 459
 460     // This should never happen, but it does.  Until the true cause is
 461     // discovered, let's skip this span instead of crashing.
 462     // See http://crbug.com/17569.
 463     if (iy < 0) {
 464         return;
 465     }
 466
 467 #ifdef SK_DEBUG
 468     {
 469         int ix = x >> SHIFT;
 470         SkASSERT(ix >= fMask.fBounds.fLeft && ix < fMask.fBounds.fRight);
 471     }
 472 #endif
 473
 474     x -= (fMask.fBounds.fLeft << SHIFT);
 475
 476     // hack, until I figure out why my cubics (I think) go beyond the bounds
 477     if (x < 0) {
 478         width += x;
 479         x = 0;
 480     }
 481
 482     // we sub 1 from maxValue 1 time for each block, so that we don't
 483     // hit 256 as a summed max, but 255.
 484 //  int maxValue = (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT);
 485
 486     uint8_t* row = fMask.fImage + iy * fMask.fRowBytes + (x >> SHIFT);
 487
 488     int start = x;
 489     int stop = x + width;
 490
 491     SkASSERT(start >= 0 && stop > start);
 492     int fb = start & SUPER_Mask;
 493     int fe = stop & SUPER_Mask;
 494     int n = (stop >> SHIFT) - (start >> SHIFT) - 1;
 495
 496
 497     if (n < 0) {
 498         SkASSERT(row >= fMask.fImage);
 499         SkASSERT(row < fMask.fImage + kMAX_STORAGE + 1);
 500         add_aa_span(row, coverage_to_alpha(fe - fb));
 501     } else {
 502 #ifdef SK_SUPPORT_NEW_AA
 503         if (0 == fb) {
 504             n += 1;
 505         } else {
 506             fb = (1 << SHIFT) - fb;
 507         }
 508 #else
 509         fb = (1 << SHIFT) - fb;
 510 #endif
 511         SkASSERT(row >= fMask.fImage);
 512         SkASSERT(row + n + 1 < fMask.fImage + kMAX_STORAGE + 1);
 513         add_aa_span(row,  coverage_to_alpha(fb), n, coverage_to_alpha(fe),
 514                     (1 << (8 - SHIFT)) - (((y & MASK) + 1) >> SHIFT));
 515     }
 516
 517 #ifdef SK_DEBUG
 518     fCurrX = x + width;
 519 #endif
 520 }
 521
 522 ///////////////////////////////////////////////////////////////////////////////
 523
 524 /*  Returns non-zero if (value << shift) overflows a short, which would mean
 525     we could not shift it up and then convert to SkFixed.
 526     i.e. is x expressible as signed (16-shift) bits?
 527  */
 528 static int overflows_short_shift(int value, int shift) {
 529     const int s = 16 + shift;
 530     return (value << s >> s) - value;
 531 }
 532
 533 void SkScan::AntiFillPath(const SkPath& path, const SkRegion& clip,
 534                           SkBlitter* blitter, bool forceRLE) {
 535     if (clip.isEmpty()) {
 536         return;
 537     }
 538
 539     SkIRect ir;
 540     path.getBounds().roundOut(&ir);
 541     if (ir.isEmpty()) {
 542         return;
 543     }
 544
 545     // use bit-or since we expect all to pass, so no need to go slower with
 546     // a short-circuiting logical-or
 547     if (overflows_short_shift(ir.fLeft, SHIFT) |
 548             overflows_short_shift(ir.fRight, SHIFT) |
 549             overflows_short_shift(ir.fTop, SHIFT) |
 550             overflows_short_shift(ir.fBottom, SHIFT)) {
 551         // can't supersample, so draw w/o antialiasing
 552         SkScan::FillPath(path, clip, blitter);
 553         return;
 554     }
 555
 556     SkScanClipper   clipper(blitter, &clip, ir);
 557     const SkIRect*  clipRect = clipper.getClipRect();
 558
 559     if (clipper.getBlitter() == NULL) { // clipped out
 560         if (path.isInverseFillType()) {
 561             blitter->blitRegion(clip);
 562         }
 563         return;
 564     }
 565
 566     // now use the (possibly wrapped) blitter
 567     blitter = clipper.getBlitter();
 568
 569     if (path.isInverseFillType()) {
 570         sk_blit_above(blitter, ir, clip);
 571     }
 572
 573     SkIRect superRect, *superClipRect = NULL;
 574
 575     if (clipRect) {
 576         superRect.set(  clipRect->fLeft << SHIFT, clipRect->fTop << SHIFT,
 577                         clipRect->fRight << SHIFT, clipRect->fBottom << SHIFT);
 578         superClipRect = &superRect;
 579     }
 580
 581     SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
 582
 583     // MaskSuperBlitter can't handle drawing outside of ir, so we can't use it
 584     // if we're an inverse filltype
 585     if (!path.isInverseFillType() && MaskSuperBlitter::CanHandleRect(ir) && !forceRLE) {
 586         MaskSuperBlitter    superBlit(blitter, ir, clip);
 587         SkASSERT(SkIntToScalar(ir.fTop) <= path.getBounds().fTop);
 588         sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip);
 589     } else {
 590         SuperBlitter    superBlit(blitter, ir, clip);
 591         sk_fill_path(path, superClipRect, &superBlit, ir.fTop, ir.fBottom, SHIFT, clip);
 592     }
 593
 594     if (path.isInverseFillType()) {
 595         sk_blit_below(blitter, ir, clip);
 596     }
 597 }
 598
 599 ///////////////////////////////////////////////////////////////////////////////
 600
 601 #include "SkRasterClip.h"
 602
 603 void SkScan::FillPath(const SkPath& path, const SkRasterClip& clip,
 604                           SkBlitter* blitter) {
 605     if (clip.isEmpty()) {
 606         return;
 607     }
 608
 609     if (clip.isBW()) {
 610         FillPath(path, clip.bwRgn(), blitter);
 611     } else {
 612         SkRegion        tmp;
 613         SkAAClipBlitter aaBlitter;
 614
 615         tmp.setRect(clip.getBounds());
 616         aaBlitter.init(blitter, &clip.aaRgn());
 617         SkScan::FillPath(path, tmp, &aaBlitter);
 618     }
 619 }
 620
 621 void SkScan::AntiFillPath(const SkPath& path, const SkRasterClip& clip,
 622                           SkBlitter* blitter) {
 623     if (clip.isEmpty()) {
 624         return;
 625     }
 626
 627     if (clip.isBW()) {
 628         AntiFillPath(path, clip.bwRgn(), blitter);
 629     } else {
 630         SkRegion        tmp;
 631         SkAAClipBlitter aaBlitter;
 632
 633         tmp.setRect(clip.getBounds());
 634         aaBlitter.init(blitter, &clip.aaRgn());
 635         SkScan::AntiFillPath(path, tmp, &aaBlitter, true);
 636     }
 637 }
 638