From ef7cee4bbc7c4c1c21b00834de7119634a3c35c9 Mon Sep 17 00:00:00 2001 From: caryclark Date: Tue, 6 Sep 2016 09:05:54 -0700 Subject: provide safe exit for runaway intersections Curve intersections with extreme numbers may cause the intersection template code to loop forever. Detect this by looking for marking more spans gone than exist, and return without any intersections found. TBR=reed@google.com BUG=643855 GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=2310113002 Review-Url: https://codereview.chromium.org/2310113002 --- src/pathops/SkPathOpsTSect.h | 66 ++++++++++++++++++++++++++++---------------- tests/PathOpsOpTest.cpp | 26 +++++++++++++++++ 2 files changed, 68 insertions(+), 24 deletions(-) diff --git a/src/pathops/SkPathOpsTSect.h b/src/pathops/SkPathOpsTSect.h index bd26e5ace3..70ee8ababd 100644 --- a/src/pathops/SkPathOpsTSect.h +++ b/src/pathops/SkPathOpsTSect.h @@ -274,7 +274,7 @@ private: bool binarySearchCoin(SkTSect* , double tStart, double tStep, double* t, double* oppT); SkTSpan* boundsMax() const; - void coincidentCheck(SkTSect* sect2); + bool coincidentCheck(SkTSect* sect2); void coincidentForce(SkTSect* sect2, double start1s, double start1e); bool coincidentHasT(double t); int collapsed() const; @@ -287,14 +287,13 @@ private: return PATH_OPS_DEBUG_T_SECT_RELEASE(fID, -1); } - void deleteEmptySpans(); + bool deleteEmptySpans(); void dumpCommon(const SkTSpan* ) const; void dumpCommonCurves(const SkTSpan* ) const; static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* ); - SkTSpan* extractCoincident(SkTSect* sect2, - SkTSpan* first, - SkTSpan* last); + bool extractCoincident(SkTSect* sect2, SkTSpan* first, + SkTSpan* last, SkTSpan** result); SkTSpan* findCoincidentRun(SkTSpan* first, SkTSpan** lastPtr); int intersects(SkTSpan* span, SkTSect* opp, @@ -302,7 +301,7 @@ private: bool isParallel(const SkDLine& thisLine, const SkTSect* opp) const; int linesIntersect(SkTSpan* span, SkTSect* opp, SkTSpan* oppSpan, SkIntersections* ); - void markSpanGone(SkTSpan* span); + bool markSpanGone(SkTSpan* span); bool matchedDirection(double t, const SkTSect* sect2, double t2) const; void matchedDirCheck(double t, const SkTSect* sect2, double t2, bool* calcMatched, bool* oppMatched) const; @@ -313,7 +312,7 @@ private: void removeCoincident(SkTSpan* span, bool isBetween); void removeAllBut(const SkTSpan* keep, SkTSpan* span, SkTSect* opp); - void removeSpan(SkTSpan* span); + bool removeSpan(SkTSpan* span); void removeSpanRange(SkTSpan* first, SkTSpan* last); void removeSpans(SkTSpan* span, SkTSect* opp); SkTSpan* spanAtT(double t, SkTSpan** priorSpan); @@ -981,7 +980,7 @@ SkTSpan* SkTSect::boundsMax() const { } template -void SkTSect::coincidentCheck(SkTSect* sect2) { +bool SkTSect::coincidentCheck(SkTSect* sect2) { SkTSpan* first = fHead; SkTSpan* last, * next; do { @@ -998,7 +997,10 @@ void SkTSect::coincidentCheck(SkTSect* sect2 // check to see if a range of points are on the curve SkTSpan* coinStart = first; do { - coinStart = this->extractCoincident(sect2, coinStart, last); + bool success = this->extractCoincident(sect2, coinStart, last, &coinStart); + if (!success) { + return false; + } } while (coinStart && !last->fDeleted); if (!fHead || !sect2->fHead) { break; @@ -1007,6 +1009,7 @@ void SkTSect::coincidentCheck(SkTSect* sect2 break; } } while ((first = next)); + return true; } template @@ -1143,24 +1146,29 @@ bool SkTSect::debugHasBounded(const SkTSpan* } template -void SkTSect::deleteEmptySpans() { +bool SkTSect::deleteEmptySpans() { SkTSpan* test; SkTSpan* next = fHead; while ((test = next)) { next = test->fNext; if (!test->fBounded) { - this->removeSpan(test); + if (!this->removeSpan(test)) { + return false; + } } } + return true; } template -SkTSpan* SkTSect::extractCoincident( +bool SkTSect::extractCoincident( SkTSect* sect2, - SkTSpan* first, SkTSpan* last) { + SkTSpan* first, SkTSpan* last, + SkTSpan** result) { first = findCoincidentRun(first, &last); if (!first || !last) { - return nullptr; + *result = nullptr; + return true; } // march outwards to find limit of coincidence from here to previous and next spans double startT = first->fStartT; @@ -1218,10 +1226,12 @@ SkTSpan* SkTSect::extractCoincident( SkOPASSERT(oppStartT == oppFirst->fStartT); SkOPASSERT(oppEndT == oppLast->fEndT); if (!oppFirst) { - return nullptr; + *result = nullptr; + return true; } if (!oppLast) { - return nullptr; + *result = nullptr; + return true; } // reduce coincident runs to single entries this->validate(); @@ -1250,12 +1260,15 @@ SkTSpan* SkTSect::extractCoincident( this->removeCoincident(first, false); sect2->removeCoincident(oppFirst, true); if (deleteEmptySpans) { - this->deleteEmptySpans(); - sect2->deleteEmptySpans(); + if (!this->deleteEmptySpans() || !sect2->deleteEmptySpans()) { + *result = nullptr; + return false; + } } this->validate(); sect2->validate(); - return last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr; + *result = last && !last->fDeleted && fHead && sect2->fHead ? last : nullptr; + return true; } template @@ -1540,12 +1553,15 @@ int SkTSect::linesIntersect(SkTSpan* span, template -void SkTSect::markSpanGone(SkTSpan* span) { - --fActiveCount; +bool SkTSect::markSpanGone(SkTSpan* span) { + if (--fActiveCount < 0) { + return false; + } span->fNext = fDeleted; fDeleted = span; SkOPASSERT(!span->fDeleted); span->fDeleted = true; + return true; } template @@ -1710,9 +1726,9 @@ void SkTSect::removeCoincident(SkTSpan* span } template -void SkTSect::removeSpan(SkTSpan* span) { +bool SkTSect::removeSpan(SkTSpan* span) { this->unlinkSpan(span); - this->markSpanGone(span); + return this->markSpanGone(span); } template @@ -2148,7 +2164,9 @@ void SkTSect::BinarySearch(SkTSect* sect1, start1s = sect1->fHead->fStartT; start1e = sect1->tail()->fEndT; } - sect1->coincidentCheck(sect2); + if (!sect1->coincidentCheck(sect2)) { + return; + } sect1->validate(); sect2->validate(); #if DEBUG_T_SECT_LOOP_COUNT diff --git a/tests/PathOpsOpTest.cpp b/tests/PathOpsOpTest.cpp index 3316f7e0cb..7261455019 100644 --- a/tests/PathOpsOpTest.cpp +++ b/tests/PathOpsOpTest.cpp @@ -7407,7 +7407,33 @@ path.cubicTo(SkBits2Float(0x6d6d6d6d), SkBits2Float(0x6d6d6d6d), SkBits2Float(0x testPathOpFuzz(reporter, path1, path2, (SkPathOp) 2, filename); } +static void fuzz763_31(skiatest::Reporter* reporter, const char* filename) { + SkPath path; + path.setFillType((SkPath::FillType) 1); + + SkPath path1(path); + path.reset(); + path.setFillType((SkPath::FillType) 0); +path.moveTo(SkBits2Float(0xd72a8c55), SkBits2Float(0x61081f2a)); // -1.8752e+14f, 1.56938e+20f +path.conicTo(SkBits2Float(0x6a4b7bc0), SkBits2Float(0x4793ed7a), SkBits2Float(0x282a3a21), SkBits2Float(0xdf3a2128), SkBits2Float(0x471ac575)); // 6.14991e+25f, 75739, 9.4495e-15f, -1.3412e+19f, 39621.5f +path.lineTo(SkBits2Float(0x28404040), SkBits2Float(0x552a298a)); // 1.06721e-14f, 1.16935e+13f +path.moveTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a)); // 5.8414e-19f, 4.61198e-19f +path.conicTo(SkBits2Float(0x6a4b7bc0), SkBits2Float(0x80ed7a3a), SkBits2Float(0x2a3a2147), SkBits2Float(0xdf212828), SkBits2Float(0x4f1a3a3a)); // 6.14991e+25f, -2.18089e-38f, 1.65317e-13f, -1.16126e+19f, 2.58751e+09f +path.lineTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a)); // 5.8414e-19f, 4.61198e-19f +path.close(); +path.moveTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a)); // 5.8414e-19f, 4.61198e-19f +path.cubicTo(SkBits2Float(0x3ac2213a), SkBits2Float(0x432a2928), SkBits2Float(0x96812be6), SkBits2Float(0x272a1d2a), SkBits2Float(0x3a2a3529), SkBits2Float(0x3b1e2ab0)); // 0.00148109f, 170.161f, -2.08688e-25f, 2.3608e-15f, 0.000649291f, 0.00241343f +path.lineTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a)); // 5.8414e-19f, 4.61198e-19f +path.close(); +path.moveTo(SkBits2Float(0x212c685b), SkBits2Float(0x21081f2a)); // 5.8414e-19f, 4.61198e-19f +path.cubicTo(SkBits2Float(0xc5272927), SkBits2Float(0x22383b39), SkBits2Float(0x1051523a), SkBits2Float(0x2927b029), SkBits2Float(0x685b2d27), SkBits2Float(0x5b2d6855)); // -2674.57f, 2.4968e-18f, 4.12813e-29f, 3.72342e-14f, 4.14012e+24f, 4.88099e+16f + + SkPath path2(path); + testPathOpFuzz(reporter, path1, path2, (SkPathOp) 4, filename); +} + static struct TestDesc failTests[] = { + TEST(fuzz763_31), TEST(fuzz763_30), TEST(fuzz763_29), TEST(fuzz763_28), -- cgit v1.2.3