Optimized implementation of quickReject()

src/core/SkCanvas.cpp

 /*
  * Copyright 2008 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkBitmapDevice.h"
 #include "SkCanvas.h"
 #include "SkCanvasPriv.h"
 #include "SkClipStack.h"
 #include "SkColorFilter.h"
 #include "SkDraw.h"
 #include "SkDrawable.h"
 #include "SkDrawFilter.h"
 #include "SkDrawLooper.h"
 #include "SkErrorInternals.h"
 #include "SkImage.h"
 #include "SkImage_Base.h"
 #include "SkImageFilter.h"
 #include "SkImageFilterCache.h"
 #include "SkLatticeIter.h"
 #include "SkMatrixUtils.h"
 #include "SkMetaData.h"
+#include "SkNx.h"
 #include "SkPaintPriv.h"
 #include "SkPatchUtils.h"
 #include "SkPicture.h"
 #include "SkRasterClip.h"
 #include "SkReadPixelsRec.h"
 #include "SkRRect.h"
 #include "SkSmallAllocator.h"
 #include "SkSpecialImage.h"
 #include "SkSurface_Base.h"
 #include "SkTextBlob.h"
@@ skipping 588 matching lines @@
 #define LOOPER_BEGIN_CHECK_COMPLETE_OVERWRITE(paint, type, bounds, auxOpaque)  \
     this->predrawNotify(bounds, &paint, auxOpaque);                 \
     AutoDrawLooper  looper(this, fProps, paint, false, bounds);     \
     while (looper.next(type)) {                                     \
         SkDrawIter          iter(this);
 
 #define LOOPER_END    }
 
 ////////////////////////////////////////////////////////////////////////////
 
+static inline SkRect qr_clip_bounds(const SkIRect& bounds) {
+    // Expand bounds out by 1 in case we are anti-aliasing.  We store the
+    // bounds as floats to enable a faster quick reject implementation.
+    SkRect dst;
+    SkNx_cast<float>(Sk4i::Load(&bounds.fLeft) + Sk4i(-1,-1,1,1)).store(&dst.fLeft);
+    return dst;
+}
+
 void SkCanvas::resetForNextPicture(const SkIRect& bounds) {
     this->restoreToCount(1);
-    fCachedLocalClipBounds.setEmpty();
-    fCachedLocalClipBoundsDirty = true;
     fClipStack->reset();
     fMCRec->reset(bounds);
 
     // We're peering through a lot of structs here.  Only at this scope do we
     // know that the device is an SkBitmapDevice (really an SkNoPixelsBitmapDevice).
     static_cast<SkBitmapDevice*>(fMCRec->fLayer->fDevice)->setNewSize(bounds.size());
+    fDeviceClipBounds = qr_clip_bounds(bounds);
+    fConservativeIsScaleTranslate = true;
 }
 
 SkBaseDevice* SkCanvas::init(SkBaseDevice* device, InitFlags flags) {
     if (device && device->forceConservativeRasterClip()) {
         flags = InitFlags(flags | kConservativeRasterClip_InitFlag);
     }
     // Since init() is only called once by our constructors, it is safe to perform this
     // const-cast.
     *const_cast<bool*>(&fConservativeRasterClip) = SkToBool(flags & kConservativeRasterClip_InitFlag);
 
-    fCachedLocalClipBounds.setEmpty();
-    fCachedLocalClipBoundsDirty = true;
     fAllowSoftClip = true;
     fAllowSimplifyClip = false;
     fDeviceCMDirty = true;
     fSaveCount = 1;
     fMetaData = nullptr;
 #ifdef SK_EXPERIMENTAL_SHADOWING
     fLights = nullptr;
 #endif
 
     fClipStack.reset(new SkClipStack);
 
     fMCRec = (MCRec*)fMCStack.push_back();
     new (fMCRec) MCRec(fConservativeRasterClip);
 
     SkASSERT(sizeof(DeviceCM) <= sizeof(fDeviceCMStorage));
     fMCRec->fLayer = (DeviceCM*)fDeviceCMStorage;
     new (fDeviceCMStorage) DeviceCM(nullptr, nullptr, nullptr, fConservativeRasterClip,
                                     fMCRec->fMatrix);
 
     fMCRec->fTopLayer = fMCRec->fLayer;
 
     fSurfaceBase = nullptr;
 
     if (device) {
         // The root device and the canvas should always have the same pixel geometry
         SkASSERT(fProps.pixelGeometry() == device->surfaceProps().pixelGeometry());
         fMCRec->fLayer->fDevice = SkRef(device);
         fMCRec->fRasterClip.setRect(device->getGlobalBounds());
+        fDeviceClipBounds = qr_clip_bounds(device->getGlobalBounds());
+        fConservativeIsScaleTranslate = true;
     }
+
     return device;
 }
 
 SkCanvas::SkCanvas()
     : fMCStack(sizeof(MCRec), fMCRecStorage, sizeof(fMCRecStorage))
     , fProps(SkSurfaceProps::kLegacyFontHost_InitType)
     , fConservativeRasterClip(false)
 {
     inc_canvas();
 
@@ skipping 394 matching lines @@
     }
     SkIRect ir;
     if (bounds) {
         SkRect r;
 
         ctm.mapRect(&r, *bounds);
         r.roundOut(&ir);
         // early exit if the layer's bounds are clipped out
         if (!ir.intersect(clipBounds)) {
             if (BoundsAffectsClip(saveLayerFlags)) {
-                fCachedLocalClipBoundsDirty = true;
                 fMCRec->fRasterClip.setEmpty();
+                fDeviceClipBounds.setEmpty();
             }
             return false;
         }
     } else {    // no user bounds, so just use the clip
         ir = clipBounds;
     }
     SkASSERT(!ir.isEmpty());
 
     if (BoundsAffectsClip(saveLayerFlags)) {
         // Simplify the current clips since they will be applied properly during restore()
-        fCachedLocalClipBoundsDirty = true;
         fClipStack->clipDevRect(ir, SkRegion::kReplace_Op);
         fMCRec->fRasterClip.setRect(ir);
+        fDeviceClipBounds = qr_clip_bounds(ir);
     }
 
     if (intersection) {
         *intersection = ir;
     }
     return true;
 }
 
 
 int SkCanvas::saveLayer(const SkRect* bounds, const SkPaint* paint) {
@@ skipping 171 matching lines @@
         SkPaint tmpPaint;
         tmpPaint.setAlpha(alpha);
         return this->saveLayer(bounds, &tmpPaint);
     }
 }
 
 void SkCanvas::internalRestore() {
     SkASSERT(fMCStack.count() != 0);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
 
     fClipStack->restore();
 
     // reserve our layer (if any)
     DeviceCM* layer = fMCRec->fLayer;   // may be null
     // now detach it from fMCRec so we can pop(). Gets freed after its drawn
     fMCRec->fLayer = nullptr;
 
     // now do the normal restore()
     fMCRec->~MCRec();       // balanced in save()
@@ skipping 13 matching lines @@
             // reset this, since internalDrawDevice will have set it to true
             fDeviceCMDirty = true;
             delete layer;
         } else {
             // we're at the root
             SkASSERT(layer == (void*)fDeviceCMStorage);
             layer->~DeviceCM();
             // no need to update fMCRec, 'cause we're killing the canvas
         }
     }
+
+    if (fMCRec) {
+        fConservativeIsScaleTranslate = fMCRec->fMatrix.isScaleTranslate();
+        fDeviceClipBounds = qr_clip_bounds(fMCRec->fRasterClip.getBounds());
+    }
 }
 
 sk_sp<SkSurface> SkCanvas::makeSurface(const SkImageInfo& info, const SkSurfaceProps* props) {
     if (nullptr == props) {
         props = &fProps;
     }
     return this->onNewSurface(info, *props);
 }
 
 sk_sp<SkSurface> SkCanvas::onNewSurface(const SkImageInfo& info, const SkSurfaceProps& props) {
@@ skipping 134 matching lines @@
     this->concat(m);
 }
 
 void SkCanvas::concat(const SkMatrix& matrix) {
     if (matrix.isIdentity()) {
         return;
     }
 
     this->checkForDeferredSave();
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
     fMCRec->fMatrix.preConcat(matrix);
 
+    // We may miss some rare cases here.  Ex: rotate 45 then -45.  But being data
+    // independ of preConcat() may allow us to go faster.

[mtklein, 2016/08/11 20:19:12]

independ -> independent

Did this actually help?

[msarett, 2016/08/11 21:11:57]

Added a bench for concat and dropped this optimization - seems to make no
difference.

+    fConservativeIsScaleTranslate = fConservativeIsScaleTranslate && matrix.isScaleTranslate();
     this->didConcat(matrix);
 }
 
 void SkCanvas::internalSetMatrix(const SkMatrix& matrix) {
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
     fMCRec->fMatrix = matrix;
 }
 
 void SkCanvas::setMatrix(const SkMatrix& matrix) {
     this->checkForDeferredSave();
     this->internalSetMatrix(matrix);
+    fConservativeIsScaleTranslate = matrix.isScaleTranslate();
     this->didSetMatrix(matrix);
 }
 
 void SkCanvas::resetMatrix() {
     this->setMatrix(SkMatrix::I());
 }
 
 #ifdef SK_EXPERIMENTAL_SHADOWING
 void SkCanvas::translateZ(SkScalar z) {
     this->checkForDeferredSave();
@@ skipping 80 matching lines @@
                      rect.left(), rect.top(), rect.right(), rect.bottom());
 #endif
             return;
         }
     }
 #endif
 
     AutoValidateClip avc(this);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
 
     if (isScaleTrans) {
         const bool isAA = kSoft_ClipEdgeStyle == edgeStyle;
         fClipStack->clipDevRect(devR, op, isAA);
         fMCRec->fRasterClip.op(devR, this->getTopLayerBounds(), op, isAA);
     } else {
         // since we're rotated or some such thing, we convert the rect to a path
         // and clip against that, since it can handle any matrix. However, to
         // avoid recursion in the case where we are subclassed (e.g. Pictures)
         // we explicitly call "our" version of clipPath.
         SkPath  path;
 
         path.addRect(rect);
         this->SkCanvas::onClipPath(path, op, edgeStyle);
     }
+
+    fDeviceClipBounds = qr_clip_bounds(fMCRec->fRasterClip.getBounds());
 }
 
 void SkCanvas::clipRRect(const SkRRect& rrect, SkRegion::Op op, bool doAA) {
     this->checkForDeferredSave();
     ClipEdgeStyle edgeStyle = doAA ? kSoft_ClipEdgeStyle : kHard_ClipEdgeStyle;
     if (rrect.isRect()) {
         this->onClipRect(rrect.getBounds(), op, edgeStyle);
     } else {
         this->onClipRRect(rrect, op, edgeStyle);
     }
 }
 
 void SkCanvas::onClipRRect(const SkRRect& rrect, SkRegion::Op op, ClipEdgeStyle edgeStyle) {
     SkRRect transformedRRect;
     if (rrect.transform(fMCRec->fMatrix, &transformedRRect)) {
         AutoValidateClip avc(this);
 
         fDeviceCMDirty = true;
-        fCachedLocalClipBoundsDirty = true;
         if (!fAllowSoftClip) {
             edgeStyle = kHard_ClipEdgeStyle;
         }
 
         fClipStack->clipDevRRect(transformedRRect, op, kSoft_ClipEdgeStyle == edgeStyle);
 
         fMCRec->fRasterClip.op(transformedRRect, this->getTopLayerBounds(), op,
                                kSoft_ClipEdgeStyle == edgeStyle);
+        fDeviceClipBounds = qr_clip_bounds(fMCRec->fRasterClip.getBounds());
         return;
     }
 
     SkPath path;
     path.addRRect(rrect);
     // call the non-virtual version
     this->SkCanvas::onClipPath(path, op, edgeStyle);
 }
 
 void SkCanvas::clipPath(const SkPath& path, SkRegion::Op op, bool doAA) {
@@ skipping 35 matching lines @@
             fClipStack->clipEmpty();
             (void)fMCRec->fRasterClip.setEmpty();
             return;
         }
     }
 #endif
 
     AutoValidateClip avc(this);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
     if (!fAllowSoftClip) {
         edgeStyle = kHard_ClipEdgeStyle;
     }
 
     SkPath devPath;
     path.transform(fMCRec->fMatrix, &devPath);
 
     // Check if the transfomation, or the original path itself
     // made us empty. Note this can also happen if we contained NaN
     // values. computing the bounds detects this, and will set our
@@ skipping 10 matching lines @@
     if (fAllowSimplifyClip) {
         bool clipIsAA = getClipStack()->asPath(&devPath);
         if (clipIsAA) {
             edgeStyle = kSoft_ClipEdgeStyle;
         }
 
         op = SkRegion::kReplace_Op;
     }
 
     fMCRec->fRasterClip.op(devPath, this->getTopLayerBounds(), op, edgeStyle);
+    fDeviceClipBounds = qr_clip_bounds(fMCRec->fRasterClip.getBounds());
 }
 
 void SkCanvas::clipRegion(const SkRegion& rgn, SkRegion::Op op) {
     this->checkForDeferredSave();
     this->onClipRegion(rgn, op);
 }
 
 void SkCanvas::onClipRegion(const SkRegion& rgn, SkRegion::Op op) {
     AutoValidateClip avc(this);
 
     fDeviceCMDirty = true;
-    fCachedLocalClipBoundsDirty = true;
 
     // todo: signal fClipStack that we have a region, and therefore (I guess)
     // we have to ignore it, and use the region directly?
     fClipStack->clipDevRect(rgn.getBounds(), op);
 
     fMCRec->fRasterClip.op(rgn, op);
+    fDeviceClipBounds = qr_clip_bounds(fMCRec->fRasterClip.getBounds());
 }
 
 #ifdef SK_DEBUG
 void SkCanvas::validateClip() const {
     // construct clipRgn from the clipstack
     const SkBaseDevice* device = this->getDevice();
     if (!device) {
         SkASSERT(this->isClipEmpty());
         return;
     }
@@ skipping 36 matching lines @@
 ///////////////////////////////////////////////////////////////////////////////
 
 bool SkCanvas::isClipEmpty() const {
     return fMCRec->fRasterClip.isEmpty();
 }
 
 bool SkCanvas::isClipRect() const {
     return fMCRec->fRasterClip.isRect();
 }
 
-bool SkCanvas::quickReject(const SkRect& rect) const {
-    if (!rect.isFinite())
-        return true;
+static inline bool is_nan_or_clipped(const Sk4f& devRect, const Sk4f& devClip) {
+#if SK_CPU_SSE_LEVEL >= SK_CPU_SSE_LEVEL_SSE2
+    __m128 lLtT = _mm_unpacklo_ps(devRect.fVec, devClip.fVec);
+    __m128 RrBb = _mm_unpackhi_ps(devClip.fVec, devRect.fVec);
+    __m128 mask = _mm_cmplt_ps(lLtT, RrBb);
+    return 0xF != _mm_movemask_ps(mask);
+#elif defined(SK_ARM_HAS_NEON)
+    float32x4_t lLtT = vzipq_f32(devRect.fVec, devClip.fVec).val[0];
+    float32x4_t RrBb = vzipq_f32(devClip.fVec, devRect.fVec).val[1];
+    uint32x4_t mask = vcltq_f32(lLtT, RrBb);
+    return 0xFFFFFFFFFFFFFFFF != (uint64_t) vmovn_u32(mask);
+#else
+    SkRect devRectAsRect;
+    SkRect devClipAsRect;
+    devRect.store(&devRectAsRect.fLeft);
+    devClip.store(&devClipAsRect.fLeft);
+    return !devRectAsRect.isFinite() || !devRectAsRect.intersect(devClipAsRect);
+#endif
+}
 
-    if (fMCRec->fRasterClip.isEmpty()) {
-        return true;
+// It's important for this function to not be inlined.  Otherwise the compiler will share code
+// between the fast path and the slow path, resulting in two slow paths.
+static SK_NEVER_INLINE bool quick_reject_slow_path(const SkRect& src, const SkRect& deviceClip,
+                                                   const SkMatrix& matrix) {
+    SkRect deviceRect;
+    matrix.mapRect(&deviceRect, src);
+    return !deviceRect.isFinite() || !deviceRect.intersect(deviceClip);
+}
+
+bool SkCanvas::quickReject(const SkRect& src) const {
+#ifdef SK_DEBUG
+    // Verify that fDeviceClipBounds are set properly.
+    SkRect tmp = qr_clip_bounds(fMCRec->fRasterClip.getBounds());
+    SkASSERT(tmp == fDeviceClipBounds);
+
+    // Verify that fConservativeIsScaleTranslate is set properly.
+    SkASSERT(!fConservativeIsScaleTranslate || fMCRec->fMatrix.isScaleTranslate());
+#endif
+
+    if (!fConservativeIsScaleTranslate) {
+        return quick_reject_slow_path(src, fDeviceClipBounds, fMCRec->fMatrix);
     }
 
-    if (fMCRec->fMatrix.hasPerspective()) {
-        SkRect dst;
-        fMCRec->fMatrix.mapRect(&dst, rect);
-        return !SkIRect::Intersects(dst.roundOut(), fMCRec->fRasterClip.getBounds());
-    } else {
-        const SkRect& clipR = this->getLocalClipBounds();
+    // We inline the implementation of mapScaleTranslate() for the fast path.
+    float sx = fMCRec->fMatrix.getScaleX();
+    float sy = fMCRec->fMatrix.getScaleY();
+    float tx = fMCRec->fMatrix.getTranslateX();
+    float ty = fMCRec->fMatrix.getTranslateY();
+    Sk4f scale(sx, sy, sx, sy);
+    Sk4f trans(tx, ty, tx, ty);
 
-        // for speed, do the most likely reject compares first
-        // TODO: should we use | instead, or compare all 4 at once?
-        if (rect.fTop >= clipR.fBottom || rect.fBottom <= clipR.fTop) {
-            return true;
-        }
-        if (rect.fLeft >= clipR.fRight || rect.fRight <= clipR.fLeft) {
-            return true;
-        }
-        return false;
-    }
+    // Apply matrix.
+    Sk4f ltrb = Sk4f::Load(&src.fLeft) * scale + trans;
+
+    // Make sure left < right, top < bottom.
+    Sk4f rblt(ltrb[2], ltrb[3], ltrb[0], ltrb[1]);
+    Sk4f min = Sk4f::Min(ltrb, rblt);
+    Sk4f max = Sk4f::Max(ltrb, rblt);
+    // We can extract either pair [0,1] or [2,3] from min and max and be correct, but on
+    // ARM this sequence generates the fastest (a single instruction).
+    Sk4f devRect = Sk4f(min[2], min[3], max[0], max[1]);
+
+    // Check if the device rect is NaN or outside the clip.
+    return is_nan_or_clipped(devRect, Sk4f::Load(&fDeviceClipBounds.fLeft));
 }
 
 bool SkCanvas::quickReject(const SkPath& path) const {
     return path.isEmpty() || this->quickReject(path.getBounds());
 }
 
 bool SkCanvas::getClipBounds(SkRect* bounds) const {
     SkIRect ibounds;
     if (!this->getClipDeviceBounds(&ibounds)) {
         return false;
@@ skipping 1323 matching lines @@
 
 SkAutoCanvasMatrixPaint::~SkAutoCanvasMatrixPaint() {
     fCanvas->restoreToCount(fSaveCount);
 }
 
 #ifdef SK_SUPPORT_LEGACY_NEW_SURFACE_API
 SkSurface* SkCanvas::newSurface(const SkImageInfo& info, const SkSurfaceProps* props) {
     return this->makeSurface(info, props).release();
 }
 #endif