From e2faf17bcc523557e44ef443b48a53f286886a53 Mon Sep 17 00:00:00 2001
From: "reed@google.com" <reed@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Mon, 6 Aug 2012 19:01:34 +0000
Subject: [PATCH] Even when the pts are restricted to 32K values, we can still
 overflow computing a fixed-point coefficient for quadratics. To avoid this,
 we bias these coefficients, storing 1/2 of their actual value, and then apply
 the 2x unbias in updateQuadratic().

Fixes http://code.google.com/p/chromium/issues/detail?id=140803
Review URL: https://codereview.appspot.com/6450099

git-svn-id: http://skia.googlecode.com/svn/trunk@4960 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 src/core/SkEdge.cpp    | 35 ++++++++++++++++++++++++++++++-----
 tests/DrawPathTest.cpp | 18 ++++++++++++++++++
 2 files changed, 48 insertions(+), 5 deletions(-)

diff --git a/src/core/SkEdge.cpp b/src/core/SkEdge.cpp
index aab1c76..d328ca3 100644
--- a/src/core/SkEdge.cpp
+++ b/src/core/SkEdge.cpp
@@ -23,6 +23,12 @@
     or pt >> 8 for antialiasing. This is implemented as pt >> (10 - shift).
 */
 
+static inline SkFixed SkFDot6ToFixedDiv2(SkFDot6 value) {
+    // we want to return SkFDot6ToFixed(value >> 1), but we don't want to throw
+    // away data in value, so just perform a modify up-shift
+    return value << (16 - 6 - 1);
+}
+
 /////////////////////////////////////////////////////////////////////////
 
 int SkEdge::setLine(const SkPoint& p0, const SkPoint& p1, const SkIRect* clip,
@@ -221,19 +227,38 @@ int SkQuadraticEdge::setQuadratic(const SkPoint pts[3], int shift)
     }
     
     fWinding    = SkToS8(winding);
-    fCurveShift = SkToU8(shift);
     //fCubicDShift only set for cubics
     fCurveCount = SkToS8(1 << shift);
 
-    SkFixed A = SkFDot6ToFixed(x0 - x1 - x1 + x2);
-    SkFixed B = SkFDot6ToFixed(x1 - x0 + x1 - x0);
+    /*
+     *  We want to reformulate into polynomial form, to make it clear how we
+     *  should forward-difference.
+     *
+     *  p0 (1 - t)^2 + p1 t(1 - t) + p2 t^2 ==> At^2 + Bt + C
+     *
+     *  A = p0 - 2p1 + p2
+     *  B = 2(p1 - p0)
+     *  C = p0
+     *
+     *  Our caller must have constrained our inputs (p0..p2) to all fit into
+     *  16.16. However, as seen above, we sometimes compute values that can be
+     *  larger (e.g. B = 2*(p1 - p0)). To guard against overflow, we will store
+     *  A and B at 1/2 of their actual value, and just apply a 2x scale during
+     *  application in updateQuadratic(). Hence we store (shift - 1) in
+     *  fCurveShift.
+     */
+
+    fCurveShift = SkToU8(shift - 1);
+
+    SkFixed A = SkFDot6ToFixedDiv2(x0 - x1 - x1 + x2);  // 1/2 the real value
+    SkFixed B = SkFDot6ToFixed(x1 - x0);                // 1/2 the real value
 
     fQx     = SkFDot6ToFixed(x0);
     fQDx    = B + (A >> shift);     // biased by shift
     fQDDx   = A >> (shift - 1);     // biased by shift
 
-    A = SkFDot6ToFixed(y0 - y1 - y1 + y2);
-    B = SkFDot6ToFixed(y1 - y0 + y1 - y0);
+    A = SkFDot6ToFixedDiv2(y0 - y1 - y1 + y2);  // 1/2 the real value
+    B = SkFDot6ToFixed(y1 - y0);                // 1/2 the real value
 
     fQy     = SkFDot6ToFixed(y0);
     fQDy    = B + (A >> shift);     // biased by shift
diff --git a/tests/DrawPathTest.cpp b/tests/DrawPathTest.cpp
index f421ee8..8b787bb 100644
--- a/tests/DrawPathTest.cpp
+++ b/tests/DrawPathTest.cpp
@@ -76,6 +76,23 @@ static void test_crbug131181(skiatest::Reporter*) {
     canvas->drawPath(path, paint);
 }
 
+// This used to assert in debug builds (and crash writing bad memory in release)
+// because we overflowed an intermediate value (B coefficient) setting up our
+// stepper for the quadratic. Now we bias that value by 1/2 so we don't overflow
+static void test_crbug_140803(skiatest::Reporter* reporter) {
+    SkBitmap bm;
+    bm.setConfig(SkBitmap::kARGB_8888_Config, 2700, 30*1024);
+    bm.allocPixels();
+    SkCanvas canvas(bm);
+    
+    SkPath path;
+    path.moveTo(2762, 20);
+    path.quadTo(11, 21702, 10, 21706);
+    SkPaint paint;
+    paint.setAntiAlias(true);
+    canvas.drawPath(path, paint);
+}
+
 // Need to exercise drawing an inverse-path whose bounds intersect the clip,
 // but whose edges do not (since its a quad which draws only in the bottom half
 // of its bounds).
@@ -208,6 +225,7 @@ static void TestDrawPath(skiatest::Reporter* reporter) {
     test_bigcubic(reporter);
     test_crbug_124652(reporter);
     test_crbug_140642(reporter);
+    test_crbug_140803(reporter);
     test_inversepathwithclip(reporter);
 //    test_crbug131181(reporter);
 }
-- 
2.7.4