fix edgecase in chopcubic where we computed duplicate tvalues

git-svn-id: http://skia.googlecode.com/svn/trunk@3285 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 69 insertions, 1 deletions

diff --git a/src/core/SkGeometry.cpp b/src/core/SkGeometry.cpp
index 5308d56dc0..de868274e1 100644
--- a/src/core/SkGeometry.cpp
+++ b/src/core/SkGeometry.cpp
@@ -834,6 +834,65 @@ static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root)
 }
 #endif
 
+/**
+ *  Given an array and count, remove all pair-wise duplicates from the array,
+ *  keeping the existing sorting, and return the new count
+ */
+static int collaps_duplicates(float array[], int count) {
+    int n = count;
+    for (int n = count; n > 1; --n) {
+        if (array[0] == array[1]) {
+            for (int i = 1; i < n; ++i) {
+                array[i - 1] = array[i];
+            }
+            count -= 1;
+        } else {
+            array += 1;
+        }
+    }
+    return count;
+}
+
+#ifdef SK_DEBUG
+
+#define TEST_COLLAPS_ENTRY(array)   array, SK_ARRAY_COUNT(array)
+
+static void test_collaps_duplicates() {
+    static bool gOnce;
+    if (gOnce) { return; }
+    gOnce = true;
+    const float src0[] = { 0 };
+    const float src1[] = { 0, 0 };
+    const float src2[] = { 0, 1 };
+    const float src3[] = { 0, 0, 0 };
+    const float src4[] = { 0, 0, 1 };
+    const float src5[] = { 0, 1, 1 };
+    const float src6[] = { 0, 1, 2 };
+    const struct {
+        const float* fData;
+        int fCount;
+        int fCollapsedCount;
+    } data[] = {
+        { TEST_COLLAPS_ENTRY(src0), 1 },
+        { TEST_COLLAPS_ENTRY(src1), 1 },
+        { TEST_COLLAPS_ENTRY(src2), 2 },
+        { TEST_COLLAPS_ENTRY(src3), 1 },
+        { TEST_COLLAPS_ENTRY(src4), 2 },
+        { TEST_COLLAPS_ENTRY(src5), 2 },
+        { TEST_COLLAPS_ENTRY(src6), 3 },
+    };
+    for (size_t i = 0; i < SK_ARRAY_COUNT(data); ++i) {
+        float dst[3];
+        memcpy(dst, data[i].fData, data[i].fCount * sizeof(dst[0]));
+        int count = collaps_duplicates(dst, data[i].fCount);
+        SkASSERT(data[i].fCollapsedCount == count);
+        for (int j = 1; j < count; ++j) {
+            SkASSERT(dst[j-1] < dst[j]);
+        }
+    }
+}
+#endif
+
 #if defined _WIN32 && _MSC_VER >= 1300  && defined SK_SCALAR_IS_FIXED // disable warning : unreachable code if building fixed point for windows desktop
 #pragma warning ( disable : 4702 )
 #endif
@@ -841,6 +900,9 @@ static SkScalar refine_cubic_root(const SkFP coeff[4], SkScalar root)
 /*  Solve coeff(t) == 0, returning the number of roots that
     lie withing 0 < t < 1.
     coeff[0]t^3 + coeff[1]t^2 + coeff[2]t + coeff[3]
+ 
+    Eliminates repeated roots (so that all tValues are distinct, and are always
+    in increasing order.
 */
 static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3])
 {
@@ -895,8 +957,14 @@ static int solve_cubic_polynomial(const SkFP coeff[4], SkScalar tValues[3])
         if (is_unit_interval(r))
             *roots++ = r;
 
+        SkDEBUGCODE(test_collaps_duplicates();)
+
         // now sort the roots
-        bubble_sort(tValues, (int)(roots - tValues));
+        int count = (int)(roots - tValues);
+        SkASSERT((unsigned)count <= 3);
+        bubble_sort(tValues, count);
+        count = collaps_duplicates(tValues, count);
+        roots = tValues + count;    // so we compute the proper count below
 #endif
     }
     else                // we have 1 real root