Move more of SkPath into SkPathRef

src/core/SkPathRef.cpp

Index: src/core/SkPathRef.cpp
===================================================================
--- src/core/SkPathRef.cpp	(revision 11888)
+++ src/core/SkPathRef.cpp	(working copy)
@@ -25,6 +25,7 @@
     }
     fPathRef = *pathRef;
     fPathRef->fGenerationID = 0;
+    fPathRef->fIsOval = false;
     SkDEBUGCODE(sk_atomic_inc(&fPathRef->fEditorsAttached);)
 }
 
@@ -35,6 +36,7 @@
     return pts;
 }
 
+
 //////////////////////////////////////////////////////////////////////////////
 void SkPathRef::CreateTransformedCopy(SkAutoTUnref<SkPathRef>* dst,
                                       const SkPathRef& src,
@@ -87,6 +89,29 @@
         (*dst)->fBoundsIsDirty = true;
     }
 
+    (*dst)->fLastMoveToIndex = src.fLastMoveToIndex;
+    (*dst)->fSegmentMask = src.fSegmentMask;
+    (*dst)->fConvexity   = src.fConvexity;
+
+    if (SkPath::kUnknown_Direction == src.fDirection) {
+        (*dst)->fDirection = SkPath::kUnknown_Direction;
+    } else {
+        SkScalar det2x2 =
+            SkScalarMul(matrix.get(SkMatrix::kMScaleX), matrix.get(SkMatrix::kMScaleY)) -
+            SkScalarMul(matrix.get(SkMatrix::kMSkewX), matrix.get(SkMatrix::kMSkewY));
+        if (det2x2 < 0) {
+            (*dst)->fDirection = SkPath::OppositeDirection(
+                                        static_cast<SkPath::Direction>(src.getDirection()));
+        } else if (det2x2 > 0) {
+            (*dst)->fDirection = src.fDirection;
+        } else {
+            (*dst)->fDirection = SkPath::kUnknown_Direction;
+        }
+    }
+
+    // It's an oval only if it stays a rect.
+    (*dst)->fIsOval = src.fIsOval && matrix.rectStaysRect();
+
     SkDEBUGCODE((*dst)->validate();)
 }
 
@@ -96,15 +121,12 @@
 #endif
     ) {
     SkPathRef* ref = SkNEW(SkPathRef);
+    int32_t packed;
 #ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
     if (newFormat) {
 #endif
-        int32_t packed = buffer->readU32();
-
-        ref->fIsFinite = (packed >> kIsFinite_SerializationShift) & 1;
+        packed = buffer->readU32();
 #ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
-    } else {
-        ref->fIsFinite = (oldPacked >> SkPath::kOldIsFinite_SerializationShift) & 1;
     }
 #endif
 
@@ -114,6 +136,24 @@
     int32_t conicCount = buffer->readS32();
     ref->resetToSize(verbCount, pointCount, conicCount);
 
+#ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
+    if (newFormat) {
+#endif
+        ref->fSegmentMask = (packed >> kSegmentMask_SerializationShift) & 0xF;
+        ref->fConvexity = (packed >> kConvexity_SerializationShift) & 0xFF;
+        ref->fIsOval = (packed >> kIsOval_SerializationShift) & 1;
+        ref->fIsFinite = (packed >> kIsFinite_SerializationShift) & 1;
+        ref->fDirection = (packed >> kDirection_SerializationShift) & 0x3;
+#ifndef DELETE_THIS_CODE_WHEN_SKPS_ARE_REBUILT_AT_V14_AND_ALL_OTHER_INSTANCES_TOO
+    } else {
+        ref->fSegmentMask = (oldPacked >> SkPath::kOldSegmentMask_SerializationShift) & 0xF;
+        ref->fConvexity = (oldPacked >> SkPath::kOldConvexity_SerializationShift) & 0xFF;
+        ref->fIsOval = (oldPacked >> SkPath::kOldIsOval_SerializationShift) & 1;
+        ref->fIsFinite = (oldPacked >> SkPath::kOldIsFinite_SerializationShift) & 1;
+        ref->fDirection = (oldPacked >> SkPath::kOldDirection_SerializationShift) & 0x3;
+    }
+#endif
+
     SkASSERT(verbCount == ref->countVerbs());
     SkASSERT(pointCount == ref->countPoints());
     SkASSERT(conicCount == ref->fConicWeights.count());
@@ -122,9 +162,54 @@
     buffer->read(ref->fConicWeights.begin(), conicCount * sizeof(SkScalar));
     buffer->read(&ref->fBounds, sizeof(SkRect));
     ref->fBoundsIsDirty = false;
+
+#ifdef SK_DEBUG_PATH
+    int lastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+    int pointCnt = 0;
+
+    for (int i = 0; i < ref->fVerbCnt; ++i) {
+        switch (ref->fVerbs[~i]) {
+            case kMove_Verb:
+                lastMoveToIndex = pointCnt;
+                ++pointCnt;
+                break;
+            case kLine_Verb:
+                ++pointCnt;
+                break;
+            case kQuad_Verb:
+                pointCnt += 2;
+                break;
+            case kConic_Verb:
+                pointCnt += 2;
+                break;
+            case kCubic_Verb:
+                pointCnt += 3;
+                break;
+            case kClose_Verb:
+                if (lastMoveToIndex >= 0) {
+                    lastMoveToIndex = ~lastMoveToIndex;
+                }
+                break;
+            case kDone_Verb:
+                // fall through
+            default:
+                SkDEBUGFAIL("default is not reached");
+        }
+    }
+    ref->fLastMoveToIndex = lastMoveToIndex;
+#endif
+
     return ref;
 }
 
+int /* SkPath::Convexity */ SkPathRef::getConvexity() const {
+    if (SkPath::kUnknown_Convexity != fConvexity) {
+        return fConvexity;
+    } else {
+        return this->internalGetConvexity();
+    }
+}
+
 void SkPathRef::Rewind(SkAutoTUnref<SkPathRef>* pathRef) {
     if ((*pathRef)->unique()) {
         SkDEBUGCODE((*pathRef)->validate();)
@@ -134,6 +219,11 @@
         (*pathRef)->fFreeSpace = (*pathRef)->currSize();
         (*pathRef)->fGenerationID = 0;
         (*pathRef)->fConicWeights.rewind();
+        (*pathRef)->fLastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+        (*pathRef)->fSegmentMask = 0;
+        (*pathRef)->fConvexity = SkPath::kUnknown_Convexity;
+        (*pathRef)->fDirection = SkPath::kUnknown_Direction;
+        (*pathRef)->fIsOval = false;
         SkDEBUGCODE((*pathRef)->validate();)
     } else {
         int oldVCnt = (*pathRef)->countVerbs();
@@ -146,6 +236,15 @@
 bool SkPathRef::operator== (const SkPathRef& ref) const {
     SkDEBUGCODE(this->validate();)
     SkDEBUGCODE(ref.validate();)
+    // note: don't need to look at isConvex or bounds, since just comparing the
+    // raw data is sufficient.
+
+    // We explicitly check fSegmentMask as a quick-reject. We could skip it,
+    // since it is only a cache of info in the fVerbs, but its a fast way to
+    // notice a difference
+    if (fSegmentMask != ref.fSegmentMask) {
+        return false;
+    }
     bool genIDMatch = fGenerationID && fGenerationID == ref.fGenerationID;
 #ifdef SK_RELEASE
     if (genIDMatch) {
@@ -183,7 +282,7 @@
     return true;
 }
 
-void SkPathRef::writeToBuffer(SkWBuffer* buffer) {
+void SkPathRef::writeToBuffer(SkWBuffer* buffer) const {
     SkDEBUGCODE(this->validate();)
     SkDEBUGCODE(size_t beforePos = buffer->pos();)
 
@@ -191,7 +290,11 @@
     // and fIsFinite are computed.
     const SkRect& bounds = this->getBounds();
 
-    int32_t packed = ((fIsFinite & 1) << kIsFinite_SerializationShift);
+    int32_t packed = ((fIsFinite & 1) << kIsFinite_SerializationShift) |
+                     ((fIsOval & 1) << kIsOval_SerializationShift) |
+                     (fConvexity << kConvexity_SerializationShift) |
+                     (fSegmentMask << kSegmentMask_SerializationShift) |
+                     (fDirection << kDirection_SerializationShift);
     buffer->write32(packed);
 
     // TODO: write gen ID here. Problem: We don't know if we're cross process or not from
@@ -208,7 +311,7 @@
     SkASSERT(buffer->pos() - beforePos == (size_t) this->writeSize());
 }
 
-uint32_t SkPathRef::writeSize() {
+uint32_t SkPathRef::writeSize() const {
     return uint32_t(5 * sizeof(uint32_t) +
                     fVerbCnt * sizeof(uint8_t) +
                     fPointCnt * sizeof(SkPoint) +
@@ -216,6 +319,23 @@
                     sizeof(SkRect));
 }
 
+SkPathRef::SkPathRef() {
+    fBoundsIsDirty = true;    // this also invalidates fIsFinite
+    fPointCnt = 0;
+    fVerbCnt = 0;
+    fVerbs = NULL;
+    fPoints = NULL;
+    fFreeSpace = 0;
+    fGenerationID = kEmptyGenID;
+    SkDEBUGCODE(fEditorsAttached = 0;)
+    fLastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+    fSegmentMask = 0;
+    fConvexity = SkPath::kUnknown_Convexity;
+    fDirection = SkPath::kUnknown_Direction;
+    fIsOval = false;
+    SkDEBUGCODE(this->validate();)
+}
+
 void SkPathRef::copy(const SkPathRef& ref,
                      int additionalReserveVerbs,
                      int additionalReservePoints) {
@@ -233,45 +353,201 @@
         fBounds = ref.fBounds;
         fIsFinite = ref.fIsFinite;
     }
+    fLastMoveToIndex = ref.fLastMoveToIndex;
+    fSegmentMask = ref.fSegmentMask;
+    fConvexity = ref.fConvexity;
+    fDirection = ref.fDirection;
+    fIsOval = ref.fIsOval;
     SkDEBUGCODE(this->validate();)
 }
 
-SkPoint* SkPathRef::growForVerb(int /* SkPath::Verb*/ verb) {
+void SkPathRef::resetToSize(int verbCount, int pointCount, int conicCount,
+                            int reserveVerbs, int reservePoints) {
     SkDEBUGCODE(this->validate();)
+    fBoundsIsDirty = true;      // this also invalidates fIsFinite
+    fGenerationID = 0;
+
+    fLastMoveToIndex = kINITIAL_LASTMOVETOINDEX_VALUE;
+    fSegmentMask = 0;
+    fConvexity = SkPath::kUnknown_Convexity;
+    fDirection = SkPath::kUnknown_Direction;
+    fIsOval = false;
+
+    size_t newSize = sizeof(uint8_t) * verbCount + sizeof(SkPoint) * pointCount;
+    size_t newReserve = sizeof(uint8_t) * reserveVerbs + sizeof(SkPoint) * reservePoints;
+    size_t minSize = newSize + newReserve;
+
+    ptrdiff_t sizeDelta = this->currSize() - minSize;
+
+    if (sizeDelta < 0 || static_cast<size_t>(sizeDelta) >= 3 * minSize) {
+        sk_free(fPoints);
+        fPoints = NULL;
+        fVerbs = NULL;
+        fFreeSpace = 0;
+        fVerbCnt = 0;
+        fPointCnt = 0;
+        this->makeSpace(minSize);
+        fVerbCnt = verbCount;
+        fPointCnt = pointCount;
+        fFreeSpace -= newSize;
+    } else {
+        fPointCnt = pointCount;
+        fVerbCnt = verbCount;
+        fFreeSpace = this->currSize() - minSize;
+    }
+    fConicWeights.setCount(conicCount);
+    SkDEBUGCODE(this->validate();)
+}
+
+// This method assumes space has already been allocated for the new
+// verb and point.
+void SkPathRef::injectMove() {
+    SkScalar x, y;
+    if (this->countVerbs() == 0) {
+        x = y = 0;
+    } else {
+        const SkPoint& pt = this->atPoint(~fLastMoveToIndex);
+        x = pt.fX;
+        y = pt.fY;
+    }
+    fPoints[fPointCnt].set(x, y);
+    fLastMoveToIndex = fPointCnt;
+    ++fPointCnt;
+    fVerbs[~fVerbCnt] = SkPath::kMove_Verb;
+    ++fVerbCnt;
+}
+
+SkPoint* SkPathRef::growForLines(int numLines) {
+    // This value is just made-up for now. When numLines is 3, calling memset was much
+    // slower than just writing the loop. This seems odd, and hopefully in the
+    // future this will appear to have been a fluke...
+    static const unsigned int kMIN_COUNT_FOR_MEMSET_TO_BE_FAST = 16;
+
+    // TODO: The following isn't hyper-optimized for the lines case since
+    // it should be expanded to handle quads, conics and cubics
+    SkDEBUGCODE(this->validate();)
+    bool dirtyAfterEdit = true;
+    bool moveInjectionNeeded = false;
+
+    moveInjectionNeeded = fLastMoveToIndex < 0;
+
+    size_t space = numLines * sizeof(uint8_t) + numLines * sizeof (SkPoint);
+    if (moveInjectionNeeded) {
+        space += sizeof(uint8_t) + sizeof(SkPoint);
+    }
+    this->makeSpace(space);
+    if (moveInjectionNeeded) {
+        SkASSERT(dirtyAfterEdit);
+        this->injectMove();
+    }
+    SkPoint* ret = fPoints + fPointCnt;
+    uint8_t* vb = fVerbs - fVerbCnt;
+
+    // cast to unsigned, so if MIN_COUNT_FOR_MEMSET_TO_BE_FAST is defined to
+    // be 0, the compiler will remove the test/branch entirely.
+    if ((unsigned)numLines >= kMIN_COUNT_FOR_MEMSET_TO_BE_FAST) {
+        memset(vb - numLines, SkPath::kLine_Verb, numLines);
+    } else {
+        for (int i = 0; i < numLines; ++i) {
+            vb[~i] = SkPath::kLine_Verb;
+        }
+    }
+    fSegmentMask |= SkPath::kLine_SegmentMask;
+
+    fVerbCnt += numLines;
+    fPointCnt += numLines;
+    fFreeSpace -= space;
+    fBoundsIsDirty = true;  // this also invalidates fIsFinite
+
+    if (dirtyAfterEdit) {
+        fConvexity = SkPath::kUnknown_Convexity;
+        fDirection = SkPath::kUnknown_Direction;
+        fIsOval = false;
+    }
+
+    SkDEBUGCODE(this->validate();)
+    return ret;
+}
+
+// In some cases we need to inject a leading moveTo before we add points
+// for lineTo, quadTo, conicTo, cubicTo
+//
+// SkPath path; path.lineTo(...);   <--- need a leading moveTo(0, 0)
+// SkPath path; ... path.close(); path.lineTo(...) <-- need a moveTo(previous moveTo)
+SkPoint* SkPathRef::growForVerb(int /* Verb */ verb) {
+    SkDEBUGCODE(this->validate();)
     int pCnt;
+    bool dirtyAfterEdit = true;
+    bool moveInjectionNeeded = false;
+    uint8_t newMask = 0;
+    int newLastMoveToIndex = fLastMoveToIndex;
+
     switch (verb) {
         case SkPath::kMove_Verb:
+            // remember the index
+            newLastMoveToIndex = this->countPoints();
             pCnt = 1;
+            dirtyAfterEdit = false;
             break;
         case SkPath::kLine_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = SkPath::kLine_SegmentMask;
             pCnt = 1;
             break;
         case SkPath::kQuad_Verb:
-            // fall through
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = SkPath::kQuad_SegmentMask;
+            pCnt = 2;
+            break;
         case SkPath::kConic_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = SkPath::kConic_SegmentMask;
             pCnt = 2;
             break;
         case SkPath::kCubic_Verb:
+            moveInjectionNeeded = fLastMoveToIndex < 0;
+            newMask = SkPath::kCubic_SegmentMask;
             pCnt = 3;
             break;
         case SkPath::kClose_Verb:
+            // signal that we need a moveTo to follow us (unless we're done)
+            newLastMoveToIndex ^= ~fLastMoveToIndex >> (8 * sizeof(fLastMoveToIndex) - 1);
             pCnt = 0;
+            dirtyAfterEdit = false;
             break;
         case SkPath::kDone_Verb:
             SkDEBUGFAIL("growForVerb called for kDone");
             // fall through
         default:
             SkDEBUGFAIL("default is not reached");
+            dirtyAfterEdit = false;
             pCnt = 0;
     }
     size_t space = sizeof(uint8_t) + pCnt * sizeof (SkPoint);
+    if (moveInjectionNeeded) {
+        space += sizeof(uint8_t) + sizeof(SkPoint);
+    }
     this->makeSpace(space);
-    this->fVerbs[~fVerbCnt] = verb;
+    fLastMoveToIndex = newLastMoveToIndex;
+    if (moveInjectionNeeded) {
+        SkASSERT(dirtyAfterEdit);
+        this->injectMove();
+    } else {
+        fLastMoveToIndex = newLastMoveToIndex;
+    }
+    fVerbs[~fVerbCnt] = verb;
+    fSegmentMask |= newMask;
     SkPoint* ret = fPoints + fPointCnt;
     fVerbCnt += 1;
     fPointCnt += pCnt;
     fFreeSpace -= space;
     fBoundsIsDirty = true;  // this also invalidates fIsFinite
+    if (dirtyAfterEdit) {
+        fConvexity = SkPath::kUnknown_Convexity;
+        fDirection = SkPath::kUnknown_Direction;
+        fIsOval = false;
+    }
+
     SkDEBUGCODE(this->validate();)
     return ret;
 }
@@ -306,7 +582,6 @@
     SkASSERT(this->currSize() ==
                 fFreeSpace + sizeof(SkPoint) * fPointCnt + sizeof(uint8_t) * fVerbCnt);
 
-#ifdef SK_DEBUG
     if (!fBoundsIsDirty && !fBounds.isEmpty()) {
         bool isFinite = true;
         for (int i = 0; i < fPointCnt; ++i) {
@@ -320,6 +595,553 @@
         }
         SkASSERT(SkToBool(fIsFinite) == isFinite);
     }
+
+#ifdef SK_DEBUG_PATH
+    if (!fBoundsIsDirty) {
+        SkRect bounds;
+
+        bool isFinite = ComputePtBounds(&bounds, fPoints, fPointCnt);
+        SkASSERT(SkToBool(fIsFinite) == isFinite);
+
+        if (fPointCnt <= 1) {
+            // if we're empty, fBounds may be empty but translated, so we can't
+            // necessarily compare to bounds directly
+            // try path.addOval(2, 2, 2, 2) which is empty, but the bounds will
+            // be [2, 2, 2, 2]
+            SkASSERT(bounds.isEmpty());
+            SkASSERT(fBounds.isEmpty());
+        } else {
+            if (bounds.isEmpty()) {
+                SkASSERT(fBounds.isEmpty());
+            } else {
+                if (!fBounds.isEmpty()) {
+                    SkASSERT(fBounds.contains(bounds));
+                }
+            }
+        }
+    }
+
+    uint32_t mask = 0;
+    int pointCnt = 0;
+    int lastMoveToIndex = ~0;
+    for (int i = 0; i < fVerbCnt; i++) {
+        switch (fVerbs[~i]) {
+            case kMove_Verb:
+                lastMoveToIndex = pointCnt;
+                ++pointCnt;
+                break;
+            case kLine_Verb:
+                mask |= kLine_SegmentMask;
+                ++pointCnt;
+                break;
+            case kQuad_Verb:
+                mask |= kQuad_SegmentMask;
+                pointCnt += 2;
+                break;
+            case kConic_Verb:
+                mask |= kConic_SegmentMask;
+                pointCnt += 2;
+                break;
+            case kCubic_Verb:
+                mask |= kCubic_SegmentMask;
+                pointCnt += 3;
+                break;
+            case kClose_Verb:
+                if (lastMoveToIndex >= 0) {
+                    lastMoveToIndex = ~lastMoveToIndex;
+                }
+                break;
+            case kDone_Verb:
+                SkDEBUGFAIL("Done verb shouldn't be recorded.");
+                break;
+            default:
+                SkDEBUGFAIL("Unknown Verb");
+                break;
+        }
+    }
+    SkASSERT(mask == fSegmentMask);
+    SkASSERT(lastMoveToIndex == fLastMoveToIndex);
+#endif // SK_DEBUG_PATH
+}
 #endif
+
+///////////////////////////////////////////////////////////////////////////////
+
+static int sign(SkScalar x) { return x < 0; }
+#define kValueNeverReturnedBySign   2
+
+static int CrossProductSign(const SkVector& a, const SkVector& b) {
+    return SkScalarSignAsInt(SkPoint::CrossProduct(a, b));
 }
+
+// only valid for a single contour
+struct Convexicator {
+    Convexicator()
+    : fPtCount(0)
+    , fConvexity(SkPath::kConvex_Convexity)
+    , fDirection(SkPath::kUnknown_Direction) {
+        fSign = 0;
+        // warnings
+        fCurrPt.set(0, 0);
+        fVec0.set(0, 0);
+        fVec1.set(0, 0);
+        fFirstVec.set(0, 0);
+
+        fDx = fDy = 0;
+        fSx = fSy = kValueNeverReturnedBySign;
+    }
+
+    SkPath::Convexity getConvexity() const { return fConvexity; }
+
+    /** The direction returned is only valid if the path is determined convex */
+    SkPath::Direction getDirection() const { return fDirection; }
+
+    void addPt(const SkPoint& pt) {
+        if (SkPath::kConcave_Convexity == fConvexity) {
+            return;
+        }
+
+        if (0 == fPtCount) {
+            fCurrPt = pt;
+            ++fPtCount;
+        } else {
+            SkVector vec = pt - fCurrPt;
+            if (vec.fX || vec.fY) {
+                fCurrPt = pt;
+                if (++fPtCount == 2) {
+                    fFirstVec = fVec1 = vec;
+                } else {
+                    SkASSERT(fPtCount > 2);
+                    this->addVec(vec);
+                }
+
+                int sx = sign(vec.fX);
+                int sy = sign(vec.fY);
+                fDx += (sx != fSx);
+                fDy += (sy != fSy);
+                fSx = sx;
+                fSy = sy;
+
+                if (fDx > 3 || fDy > 3) {
+                    fConvexity = SkPath::kConcave_Convexity;
+                }
+            }
+        }
+    }
+
+    void close() {
+        if (fPtCount > 2) {
+            this->addVec(fFirstVec);
+        }
+    }
+
+private:
+    void addVec(const SkVector& vec) {
+        SkASSERT(vec.fX || vec.fY);
+        fVec0 = fVec1;
+        fVec1 = vec;
+        int sign = CrossProductSign(fVec0, fVec1);
+        if (0 == fSign) {
+            fSign = sign;
+            if (1 == sign) {
+                fDirection = SkPath::kCW_Direction;
+            } else if (-1 == sign) {
+                fDirection = SkPath::kCCW_Direction;
+            }
+        } else if (sign) {
+            if (fSign != sign) {
+                fConvexity = SkPath::kConcave_Convexity;
+                fDirection = SkPath::kUnknown_Direction;
+            }
+        }
+    }
+
+    SkPoint              fCurrPt;
+    SkVector             fVec0, fVec1, fFirstVec;
+    int                  fPtCount;   // non-degenerate points
+    int                  fSign;
+    SkPath::Convexity    fConvexity;
+    SkPath::Direction    fDirection;
+    int                  fDx, fDy, fSx, fSy;
+};
+
+int /* SkPath::Convexity */ SkPathRef::internalGetConvexity() const {
+    SkASSERT(SkPath::kUnknown_Convexity == fConvexity);
+    SkPoint         pts[4];
+    SkPath::Verb    verb;
+    SkPath::Iter    iter(this, true);
+
+    int             contourCount = 0;
+    int             count;
+    Convexicator    state;
+
+    while ((verb = iter.next(pts)) != SkPath::kDone_Verb) {
+        switch (verb) {
+            case SkPath::kMove_Verb:
+                if (++contourCount > 1) {
+                    fConvexity = SkPath::kConcave_Convexity;
+                    return SkPath::kConcave_Convexity;
+                }
+                pts[1] = pts[0];
+                count = 1;
+                break;
+            case SkPath::kLine_Verb: count = 1; break;
+            case SkPath::kQuad_Verb: count = 2; break;
+            case SkPath::kConic_Verb: count = 2; break;
+            case SkPath::kCubic_Verb: count = 3; break;
+            case SkPath::kClose_Verb:
+                state.close();
+                count = 0;
+                break;
+            default:
+                SkDEBUGFAIL("bad verb");
+                fConvexity = SkPath::kConcave_Convexity;
+                return SkPath::kConcave_Convexity;
+        }
+
+        for (int i = 1; i <= count; i++) {
+            state.addPt(pts[i]);
+        }
+        // early exit
+        if (SkPath::kConcave_Convexity == state.getConvexity()) {
+            fConvexity = SkPath::kConcave_Convexity;
+            return SkPath::kConcave_Convexity;
+        }
+    }
+    fConvexity = state.getConvexity();
+    if (SkPath::kConvex_Convexity == fConvexity && SkPath::kUnknown_Direction == fDirection) {
+        fDirection = state.getDirection();
+    }
+    return fConvexity;
+}
+
+class ContourIter {
+public:
+    ContourIter(const SkPathRef& pathRef);
+
+    bool done() const { return fDone; }
+    // if !done() then these may be called
+    int count() const { return fCurrPtCount; }
+    const SkPoint* pts() const { return fCurrPt; }
+    void next();
+
+private:
+    int fCurrPtCount;
+    const SkPoint* fCurrPt;
+    const uint8_t* fCurrVerb;
+    const uint8_t* fStopVerbs;
+    const SkScalar* fCurrConicWeight;
+    bool fDone;
+    SkDEBUGCODE(int fContourCounter;)
+};
+
+ContourIter::ContourIter(const SkPathRef& pathRef) {
+    fStopVerbs = pathRef.verbsMemBegin();
+    fDone = false;
+    fCurrPt = pathRef.points();
+    fCurrVerb = pathRef.verbs();
+    fCurrConicWeight = pathRef.conicWeights();
+    fCurrPtCount = 0;
+    SkDEBUGCODE(fContourCounter = 0;)
+    this->next();
+}
+
+void ContourIter::next() {
+    if (fCurrVerb <= fStopVerbs) {
+        fDone = true;
+    }
+    if (fDone) {
+        return;
+    }
+
+    // skip pts of prev contour
+    fCurrPt += fCurrPtCount;
+
+    SkASSERT(SkPath::kMove_Verb == fCurrVerb[~0]);
+    int ptCount = 1;    // moveTo
+    const uint8_t* verbs = fCurrVerb;
+
+    for (--verbs; verbs > fStopVerbs; --verbs) {
+        switch (verbs[~0]) {
+            case SkPath::kMove_Verb:
+                goto CONTOUR_END;
+            case SkPath::kLine_Verb:
+                ptCount += 1;
+                break;
+            case SkPath::kConic_Verb:
+                fCurrConicWeight += 1;
+                // fall-through
+            case SkPath::kQuad_Verb:
+                ptCount += 2;
+                break;
+            case SkPath::kCubic_Verb:
+                ptCount += 3;
+                break;
+            case SkPath::kClose_Verb:
+                break;
+            default:
+                SkDEBUGFAIL("unexpected verb");
+                break;
+        }
+    }
+CONTOUR_END:
+    fCurrPtCount = ptCount;
+    fCurrVerb = verbs;
+    SkDEBUGCODE(++fContourCounter;)
+}
+
+// returns cross product of (p1 - p0) and (p2 - p0)
+static SkScalar cross_prod(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2) {
+    SkScalar cross = SkPoint::CrossProduct(p1 - p0, p2 - p0);
+    // We may get 0 when the above subtracts underflow. We expect this to be
+    // very rare and lazily promote to double.
+    if (0 == cross) {
+        double p0x = SkScalarToDouble(p0.fX);
+        double p0y = SkScalarToDouble(p0.fY);
+
+        double p1x = SkScalarToDouble(p1.fX);
+        double p1y = SkScalarToDouble(p1.fY);
+
+        double p2x = SkScalarToDouble(p2.fX);
+        double p2y = SkScalarToDouble(p2.fY);
+
+        cross = SkDoubleToScalar((p1x - p0x) * (p2y - p0y) -
+                                 (p1y - p0y) * (p2x - p0x));
+
+    }
+    return cross;
+}
+
+// Returns the first pt with the maximum Y coordinate
+static int find_max_y(const SkPoint pts[], int count) {
+    SkASSERT(count > 0);
+    SkScalar max = pts[0].fY;
+    int firstIndex = 0;
+    for (int i = 1; i < count; ++i) {
+        SkScalar y = pts[i].fY;
+        if (y > max) {
+            max = y;
+            firstIndex = i;
+        }
+    }
+    return firstIndex;
+}
+
+static int find_diff_pt(const SkPoint pts[], int index, int n, int inc) {
+    int i = index;
+    for (;;) {
+        i = (i + inc) % n;
+        if (i == index) {   // we wrapped around, so abort
+            break;
+        }
+        if (pts[index] != pts[i]) { // found a different point, success!
+            break;
+        }
+    }
+    return i;
+}
+
+/**
+ *  Starting at index, and moving forward (incrementing), find the xmin and
+ *  xmax of the contiguous points that have the same Y.
+ */
+static int find_min_max_x_at_y(const SkPoint pts[], int index, int n,
+                               int* maxIndexPtr) {
+    const SkScalar y = pts[index].fY;
+    SkScalar min = pts[index].fX;
+    SkScalar max = min;
+    int minIndex = index;
+    int maxIndex = index;
+    for (int i = index + 1; i < n; ++i) {
+        if (pts[i].fY != y) {
+            break;
+        }
+        SkScalar x = pts[i].fX;
+        if (x < min) {
+            min = x;
+            minIndex = i;
+        } else if (x > max) {
+            max = x;
+            maxIndex = i;
+        }
+    }
+    *maxIndexPtr = maxIndex;
+    return minIndex;
+}
+
+static void crossToDir(SkScalar cross, SkPath::Direction* dir) {
+    if (dir) {
+        *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
+    }
+}
+
+#if 0
+#include "SkString.h"
+#include "../utils/SkParsePath.h"
+static void dumpPath(const SkPath& path) {
+    SkString str;
+    SkParsePath::ToSVGString(path, &str);
+    SkDebugf("%s\n", str.c_str());
+}
 #endif
+
+namespace {
+// for use with convex_dir_test
+double mul(double a, double b) { return a * b; }
+SkScalar mul(SkScalar a, SkScalar b) { return SkScalarMul(a, b); }
+double toDouble(SkScalar a) { return SkScalarToDouble(a); }
+SkScalar toScalar(SkScalar a) { return a; }
+
+// determines the winding direction of a convex polygon with the precision
+// of T. CAST_SCALAR casts an SkScalar to T.
+template <typename T, T (CAST_SCALAR)(SkScalar)>
+bool convex_dir_test(int n, const SkPoint pts[], SkPath::Direction* dir) {
+    // we find the first three points that form a non-degenerate
+    // triangle. If there are no such points then the path is
+    // degenerate. The first is always point 0. Now we find the second
+    // point.
+    int i = 0;
+    enum { kX = 0, kY = 1 };
+    T v0[2];
+    while (1) {
+        v0[kX] = CAST_SCALAR(pts[i].fX) - CAST_SCALAR(pts[0].fX);
+        v0[kY] = CAST_SCALAR(pts[i].fY) - CAST_SCALAR(pts[0].fY);
+        if (v0[kX] || v0[kY]) {
+            break;
+        }
+        if (++i == n - 1) {
+            return false;
+        }
+    }
+    // now find a third point that is not colinear with the first two
+    // points and check the orientation of the triangle (which will be
+    // the same as the orientation of the path).
+    for (++i; i < n; ++i) {
+        T v1[2];
+        v1[kX] = CAST_SCALAR(pts[i].fX) - CAST_SCALAR(pts[0].fX);
+        v1[kY] = CAST_SCALAR(pts[i].fY) - CAST_SCALAR(pts[0].fY);
+        T cross = mul(v0[kX], v1[kY]) - mul(v0[kY], v1[kX]);
+        if (0 != cross) {
+            *dir = cross > 0 ? SkPath::kCW_Direction : SkPath::kCCW_Direction;
+            return true;
+        }
+    }
+    return false;
+}
+}
+
+/*
+ *  We loop through all contours, and keep the computed cross-product of the
+ *  contour that contained the global y-max. If we just look at the first
+ *  contour, we may find one that is wound the opposite way (correctly) since
+ *  it is the interior of a hole (e.g. 'o'). Thus we must find the contour
+ *  that is outer most (or at least has the global y-max) before we can consider
+ *  its cross product.
+ */
+bool SkPathRef::cheapComputeDirection(int* dir2) const {
+//    dumpPath(*this);
+    // don't want to pay the cost for computing this if it
+    // is unknown, so we don't call isConvex()
+
+    if (SkPath::kUnknown_Direction != fDirection) {
+        *dir2 = static_cast<SkPath::Direction>(fDirection);
+        return true;
+    }
+    const SkPath::Convexity conv = static_cast<SkPath::Convexity>(this->getConvexityOrUnknown());
+    SkPath::Direction tmp;
+
+    ContourIter iter(*this);
+
+    // initialize with our logical y-min
+    SkScalar ymax = this->getBounds().fTop;
+    SkScalar ymaxCross = 0;
+
+    for (; !iter.done(); iter.next()) {
+        int n = iter.count();
+        if (n < 3) {
+            continue;
+        }
+
+        const SkPoint* pts = iter.pts();
+        SkScalar cross = 0;
+        if (SkPath::kConvex_Convexity == conv) {
+            // We try first at scalar precision, and then again at double
+            // precision. This is because the vectors computed between distant
+            // points may lose too much precision.
+            if (convex_dir_test<SkScalar, toScalar>(n, pts, &tmp)) {
+                fDirection = tmp;
+                *dir2 = tmp;
+                return true;
+            }
+            if (convex_dir_test<double, toDouble>(n, pts, &tmp)) {
+                fDirection = tmp;
+                *dir2 = tmp;
+                return true;
+            } else {
+                return false;
+            }
+        } else {
+            int index = find_max_y(pts, n);
+            if (pts[index].fY < ymax) {
+                continue;
+            }
+
+            // If there is more than 1 distinct point at the y-max, we take the
+            // x-min and x-max of them and just subtract to compute the dir.
+            if (pts[(index + 1) % n].fY == pts[index].fY) {
+                int maxIndex;
+                int minIndex = find_min_max_x_at_y(pts, index, n, &maxIndex);
+                if (minIndex == maxIndex) {
+                    goto TRY_CROSSPROD;
+                }
+                SkASSERT(pts[minIndex].fY == pts[index].fY);
+                SkASSERT(pts[maxIndex].fY == pts[index].fY);
+                SkASSERT(pts[minIndex].fX <= pts[maxIndex].fX);
+                // we just subtract the indices, and let that auto-convert to
+                // SkScalar, since we just want - or + to signal the direction.
+                cross = minIndex - maxIndex;
+            } else {
+                TRY_CROSSPROD:
+                // Find a next and prev index to use for the cross-product test,
+                // but we try to find pts that form non-zero vectors from pts[index]
+                //
+                // Its possible that we can't find two non-degenerate vectors, so
+                // we have to guard our search (e.g. all the pts could be in the
+                // same place).
+
+                // we pass n - 1 instead of -1 so we don't foul up % operator by
+                // passing it a negative LH argument.
+                int prev = find_diff_pt(pts, index, n, n - 1);
+                if (prev == index) {
+                    // completely degenerate, skip to next contour
+                    continue;
+                }
+                int next = find_diff_pt(pts, index, n, 1);
+                SkASSERT(next != index);
+                cross = cross_prod(pts[prev], pts[index], pts[next]);
+                // if we get a zero and the points are horizontal, then we look at the spread in
+                // x-direction. We really should continue to walk away from the degeneracy until
+                // there is a divergence.
+                if (0 == cross && pts[prev].fY == pts[index].fY && pts[next].fY == pts[index].fY) {
+                    // construct the subtract so we get the correct Direction below
+                    cross = pts[index].fX - pts[next].fX;
+                }
+            }
+
+            if (cross) {
+                // record our best guess so far
+                ymax = pts[index].fY;
+                ymaxCross = cross;
+            }
+        }
+    }
+    if (ymaxCross) {
+        crossToDir(ymaxCross, &tmp);
+        *dir2 = tmp;
+        fDirection = tmp;
+        return true;
+    } else {
+        return false;
+    }
+}
+