Lower cubic stroke recursion limit to 24
The current limit of 78 is quite conservative, and we see no diffs via
gold when using a limit of 24. This also fixes a timeout uncovered by a
fuzzer.
Bug: oss-fuzz:23989
Change-Id: I0d7c33afca7e7e852bedfea52b104d6c7d8fcfd5
Reviewed-on: https://skia-review.googlesource.com/c/skia/+/301938
Commit-Queue: Mike Reed <reed@google.com>
Reviewed-by: Mike Reed <reed@google.com>
Reviewed-by: Florin Malita <fmalita@chromium.org>
diff --git a/bench/PathBench.cpp b/bench/PathBench.cpp
index 93824bc..030d7b9 100644
--- a/bench/PathBench.cpp
+++ b/bench/PathBench.cpp
@@ -16,6 +16,8 @@
#include "include/private/SkTArray.h"
#include "include/utils/SkRandom.h"
+#include "src/core/SkDraw.h"
+
enum Flags {
kStroke_Flag = 1 << 0,
kBig_Flag = 1 << 1
@@ -966,6 +968,41 @@
DEF_BENCH( return new ConicBench_EvalTan(false); )
DEF_BENCH( return new ConicBench_EvalTan(true); )
+class ConicBench_TinyError : public Benchmark {
+protected:
+ SkString fName;
+
+public:
+ ConicBench_TinyError() : fName("conic-tinyerror") {}
+
+protected:
+ const char* onGetName() override { return fName.c_str(); }
+
+ void onDraw(int loops, SkCanvas*) override {
+ SkPaint paint;
+ paint.setColor(SK_ColorBLACK);
+ paint.setAntiAlias(true);
+ paint.setStyle(SkPaint::kStroke_Style);
+ paint.setStrokeWidth(2);
+
+ SkPath path;
+ path.moveTo(-100, 1);
+ path.cubicTo(-101, 1, -118, -47, -138, -44);
+
+ // The large y scale factor produces a tiny error threshold.
+ const SkMatrix mtx = SkMatrix::MakeAll(3.07294035f, 0.833333373f, 361.111115f, 0.0f,
+ 6222222.5f, 28333.334f, 0.0f, 0.0f, 1.0f);
+ for (int i = 0; i < loops; ++i) {
+ SkPath dst;
+ paint.getFillPath(path, &dst, nullptr, SkDraw::ComputeResScaleForStroking(mtx));
+ }
+ }
+
+private:
+ typedef Benchmark INHERITED;
+};
+DEF_BENCH( return new ConicBench_TinyError; )
+
///////////////////////////////////////////////////////////////////////////////
static void rand_conic(SkConic* conic, SkRandom& rand) {
diff --git a/src/core/SkStroke.cpp b/src/core/SkStroke.cpp
index ec25e75..b1e67d6 100644
--- a/src/core/SkStroke.cpp
+++ b/src/core/SkStroke.cpp
@@ -25,7 +25,11 @@
// quads with extreme widths (e.g. (0,1) (1,6) (0,3) width=5e7) recurse to point of failure
// largest seen for normal cubics : 5, 26
// largest seen for normal quads : 11
-static const int kRecursiveLimits[] = { 5*3, 26*3, 11*3, 11*3 }; // 3x limits seen in practice
+// 3x limits seen in practice, except for cubics (3x limit would be ~75).
+// For cubics, we never get close to 75 when running through dm. The limit of 24
+// was chosen because it's close to the peak in a count of cubic recursion depths visited
+// (define DEBUG_CUBIC_RECURSION_DEPTHS) and no diffs were produced on gold when using it.
+static const int kRecursiveLimits[] = { 5*3, 24, 11*3, 11*3 };
static_assert(0 == kTangent_RecursiveLimit, "cubic_stroke_relies_on_tangent_equalling_zero");
static_assert(1 == kCubic_RecursiveLimit, "cubic_stroke_relies_on_cubic_equalling_one");
@@ -53,6 +57,35 @@
#define STROKER_DEBUG_PARAMS(...)
#endif
+#ifndef DEBUG_CUBIC_RECURSION_DEPTHS
+#define DEBUG_CUBIC_RECURSION_DEPTHS 0
+#endif
+#if DEBUG_CUBIC_RECURSION_DEPTHS
+ /* Prints a histogram of recursion depths at process termination. */
+ static struct DepthHistogram {
+ static constexpr int kMaxDepth = 75;
+ int fCubicDepths[kMaxDepth + 1];
+
+ DepthHistogram() { memset(fCubicDepths, 0, sizeof(fCubicDepths)); }
+
+ ~DepthHistogram() {
+ SkDebugf("# times recursion terminated per depth:\n");
+ for (int i = 0; i <= kMaxDepth; i++) {
+ SkDebugf(" depth %d: %d\n", i, fCubicDepths[i]);
+ }
+ }
+
+ inline void incDepth(int depth) {
+ SkASSERT(depth >= 0 && depth <= kMaxDepth);
+ fCubicDepths[depth]++;
+ }
+ } sCubicDepthHistogram;
+
+#define DEBUG_CUBIC_RECURSION_TRACK_DEPTH(depth) sCubicDepthHistogram.incDepth(depth)
+#else
+#define DEBUG_CUBIC_RECURSION_TRACK_DEPTH(depth) (void)(depth)
+#endif
+
static inline bool degenerate_vector(const SkVector& v) {
return !SkPointPriv::CanNormalize(v.fX, v.fY);
}
@@ -1118,6 +1151,7 @@
|| points_within_dist(quadPts->fQuad[0], quadPts->fQuad[2],
fInvResScale)) && cubicMidOnLine(cubic, quadPts)) {
addDegenerateLine(quadPts);
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
return true;
}
} else {
@@ -1130,16 +1164,19 @@
SkPath* path = fStrokeType == kOuter_StrokeType ? &fOuter : &fInner;
const SkPoint* stroke = quadPts->fQuad;
path->quadTo(stroke[1].fX, stroke[1].fY, stroke[2].fX, stroke[2].fY);
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
return true;
}
if (kDegenerate_ResultType == resultType) {
if (!quadPts->fOppositeTangents) {
addDegenerateLine(quadPts);
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
return true;
}
}
}
if (!SkScalarIsFinite(quadPts->fQuad[2].fX) || !SkScalarIsFinite(quadPts->fQuad[2].fY)) {
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
return false; // just abort if projected quad isn't representable
}
#if QUAD_STROKE_APPROX_EXTENDED_DEBUGGING
@@ -1147,11 +1184,13 @@
fRecursionDepth + 1));
#endif
if (++fRecursionDepth > kRecursiveLimits[fFoundTangents]) {
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
return false; // just abort if projected quad isn't representable
}
SkQuadConstruct half;
if (!half.initWithStart(quadPts)) {
addDegenerateLine(quadPts);
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
--fRecursionDepth;
return true;
}
@@ -1160,6 +1199,7 @@
}
if (!half.initWithEnd(quadPts)) {
addDegenerateLine(quadPts);
+ DEBUG_CUBIC_RECURSION_TRACK_DEPTH(fRecursionDepth);
--fRecursionDepth;
return true;
}