SkRegion: Use less memory for SkRegion::Oper

Also add fuzzer.

BUG=chromium:797940
Change-Id: Id6d483120f3325c3b1085a90277d56a4f7a0e989
Reviewed-on: https://skia-review.googlesource.com/118623
Commit-Queue: Hal Canary <halcanary@google.com>
Reviewed-by: Cary Clark <caryclark@skia.org>

1 files changed, 94 insertions, 71 deletions

diff --git a/src/core/SkRegion.cpp b/src/core/SkRegion.cpp
index 204e35479d..2f4e2f8992 100644
--- a/src/core/SkRegion.cpp
+++ b/src/core/SkRegion.cpp
@@ -26,6 +26,44 @@ SkDEBUGCODE(int32_t gRgnAllocCounter;)
 
 /////////////////////////////////////////////////////////////////////////////////////////////////
 
+constexpr int kRunArrayStackCount = 256;
+// This is a simple data structure which is like a SkSTArray<N,T,true>, except that:
+//   - It does not initialize memory.
+//   - It does not distinguish between reserved space and initialized space.
+//   - resizeToAtLeast() instead of resize()
+//   - Uses sk_realloc_throw()
+//   - Can never be made smaller.
+// Measurement:  for the `region_union_16` benchmark, this is 6% faster.
+class RunArray {
+public:
+    RunArray() { fPtr = fStack; }
+    #ifdef SK_DEBUG
+    int count() const { return fCount; }
+    #endif
+    SkRegion::RunType& operator[](int i) {
+        SkASSERT((unsigned)i < (unsigned)fCount);
+        return fPtr[i];
+    }
+    /** Resize the array to a size greater-than-or-equal-to count. */
+    void resizeToAtLeast(int count) {
+        if (count > fCount) {
+            // leave at least 50% extra space for future growth.
+            count += count >> 1;
+            fMalloc.realloc(count);
+            if (fPtr == fStack) {
+                memcpy(fMalloc.get(), fStack, fCount * sizeof(SkRegion::RunType));
+            }
+            fPtr = fMalloc.get();
+            fCount = count;
+        }
+    }
+private:
+    SkRegion::RunType fStack[kRunArrayStackCount];
+    SkAutoTMalloc<SkRegion::RunType> fMalloc;
+    int fCount = kRunArrayStackCount;
+    SkRegion::RunType* fPtr;  // non-owning pointer
+};
+
 /*  Pass in the beginning with the intervals.
  *  We back up 1 to read the interval-count.
  *  Return the beginning of the next scanline (i.e. the next Y-value)
@@ -711,10 +749,21 @@ struct spanRec {
     }
 };
 
-static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[],
-                                          const SkRegion::RunType b_runs[],
-                                          SkRegion::RunType dst[],
-                                          int min, int max) {
+static int distance_to_sentinel(const SkRegion::RunType* runs) {
+    const SkRegion::RunType* ptr = runs;
+    while (*ptr != SkRegion::kRunTypeSentinel) { ptr += 2; }
+    return ptr - runs;
+}
+
+static int operate_on_span(const SkRegion::RunType a_runs[],
+                           const SkRegion::RunType b_runs[],
+                           RunArray* array, int dstOffset,
+                           int min, int max) {
+    // This is a worst-case for this span plus two for TWO terminating sentinels.
+    array->resizeToAtLeast(
+            dstOffset + distance_to_sentinel(a_runs) + distance_to_sentinel(b_runs) + 2);
+    SkRegion::RunType* dst = &(*array)[dstOffset]; // get pointer AFTER resizing.
+
     spanRec rec;
     bool    firstInterval = true;
 
@@ -729,19 +778,19 @@ static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[],
         // add left,rite to our dst buffer (checking for coincidence
         if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) &&
                 left < rite) {    // skip if equal
-            if (firstInterval || dst[-1] < left) {
+            if (firstInterval || *(dst - 1) < left) {
                 *dst++ = (SkRegion::RunType)(left);
                 *dst++ = (SkRegion::RunType)(rite);
                 firstInterval = false;
             } else {
                 // update the right edge
-                dst[-1] = (SkRegion::RunType)(rite);
+                *(dst - 1) = (SkRegion::RunType)(rite);
             }
         }
     }
-
+    SkASSERT(dst < &(*array)[array->count() - 1]);
     *dst++ = SkRegion::kRunTypeSentinel;
-    return dst;
+    return dst - &(*array)[0];
 }
 
 #if defined _WIN32
@@ -757,47 +806,45 @@ static const struct {
     { 1, 3 },   // Union
     { 1, 2 }    // XOR
 };
+// need to ensure that the op enum lines up with our minmax array
+static_assert(0 == SkRegion::kDifference_Op, "");
+static_assert(1 == SkRegion::kIntersect_Op,  "");
+static_assert(2 == SkRegion::kUnion_Op,      "");
+static_assert(3 == SkRegion::kXOR_Op,        "");
 
 class RgnOper {
 public:
-    RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) {
-        // need to ensure that the op enum lines up with our minmax array
-        SkASSERT(SkRegion::kDifference_Op == 0);
-        SkASSERT(SkRegion::kIntersect_Op == 1);
-        SkASSERT(SkRegion::kUnion_Op == 2);
-        SkASSERT(SkRegion::kXOR_Op == 3);
-        SkASSERT((unsigned)op <= 3);
-
-        fStartDst = dst;
-        fPrevDst = dst + 1;
-        fPrevLen = 0;       // will never match a length from operate_on_span
-        fTop = (SkRegion::RunType)(top);    // just a first guess, we might update this
-
-        fMin = gOpMinMax[op].fMin;
-        fMax = gOpMinMax[op].fMax;
-    }
+    RgnOper(int top, RunArray* array, SkRegion::Op op)
+        : fMin(gOpMinMax[op].fMin)
+        , fMax(gOpMinMax[op].fMax)
+        , fArray(array)
+        , fTop((SkRegion::RunType)top)  // just a first guess, we might update this
+        { SkASSERT((unsigned)op <= 3); }
 
     void addSpan(int bottom, const SkRegion::RunType a_runs[],
                  const SkRegion::RunType b_runs[]) {
         // skip X values and slots for the next Y+intervalCount
-        SkRegion::RunType*  start = fPrevDst + fPrevLen + 2;
+        int start = fPrevDst + fPrevLen + 2;
         // start points to beginning of dst interval
-        SkRegion::RunType*  stop = operate_on_span(a_runs, b_runs, start, fMin, fMax);
-        size_t              len = stop - start;
+        int stop = operate_on_span(a_runs, b_runs, fArray, start, fMin, fMax);
+        size_t len = SkToSizeT(stop - start);
         SkASSERT(len >= 1 && (len & 1) == 1);
-        SkASSERT(SkRegion::kRunTypeSentinel == stop[-1]);
+        SkASSERT(SkRegion::kRunTypeSentinel == (*fArray)[stop - 1]);
 
+        // Assert memcmp won't exceed fArray->count().
+        SkASSERT(fArray->count() >= SkToInt(start + len - 1));
         if (fPrevLen == len &&
-            (1 == len || !memcmp(fPrevDst, start,
+            (1 == len || !memcmp(&(*fArray)[fPrevDst],
+                                 &(*fArray)[start],
                                  (len - 1) * sizeof(SkRegion::RunType)))) {
             // update Y value
-            fPrevDst[-2] = (SkRegion::RunType)(bottom);
+            (*fArray)[fPrevDst - 2] = (SkRegion::RunType)bottom;
         } else {    // accept the new span
             if (len == 1 && fPrevLen == 0) {
-                fTop = (SkRegion::RunType)(bottom); // just update our bottom
+                fTop = (SkRegion::RunType)bottom; // just update our bottom
             } else {
-                start[-2] = (SkRegion::RunType)(bottom);
-                start[-1] = SkToS32(len >> 1);
+                (*fArray)[start - 2] = (SkRegion::RunType)bottom;
+                (*fArray)[start - 1] = SkToS32(len >> 1);
                 fPrevDst = start;
                 fPrevLen = len;
             }
@@ -805,8 +852,10 @@ public:
     }
 
     int flush() {
-        fStartDst[0] = fTop;
-        fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel;
+        (*fArray)[fStartDst] = fTop;
+        // Previously reserved enough for TWO sentinals.
+        SkASSERT(fArray->count() > SkToInt(fPrevDst + fPrevLen));
+        (*fArray)[fPrevDst + fPrevLen] = SkRegion::kRunTypeSentinel;
         return (int)(fPrevDst - fStartDst + fPrevLen + 1);
     }
 
@@ -815,10 +864,11 @@ public:
     uint8_t fMin, fMax;
 
 private:
-    SkRegion::RunType*  fStartDst;
-    SkRegion::RunType*  fPrevDst;
-    size_t              fPrevLen;
-    SkRegion::RunType   fTop;
+    RunArray* fArray;
+    int fStartDst = 0;
+    int fPrevDst = 1;
+    size_t fPrevLen = 0;  // will never match a length from operate_on_span
+    SkRegion::RunType fTop;
 };
 
 // want a unique value to signal that we exited due to quickExit
@@ -826,7 +876,7 @@ private:
 
 static int operate(const SkRegion::RunType a_runs[],
                    const SkRegion::RunType b_runs[],
-                   SkRegion::RunType dst[],
+                   RunArray* dst,
                    SkRegion::Op op,
                    bool quickExit) {
     const SkRegion::RunType gEmptyScanline[] = {
@@ -951,26 +1001,6 @@ static int count_to_intervals(int count) {
 }
 #endif
 
-/*  Given a number of intervals, what is the worst case representation of that
-    many intervals?
-
-    Worst case (from a storage perspective), is a vertical stack of single
-    intervals:  TOP + N * (BOTTOM INTERVALCOUNT LEFT RIGHT SENTINEL) + SENTINEL
- */
-static int intervals_to_count(int intervals) {
-    return 1 + intervals * 5 + 1;
-}
-
-/*  Given the intervalCounts of RunTypes in two regions, return the worst-case number
-    of RunTypes need to store the result after a region-op.
- */
-static int compute_worst_case_count(int a_intervals, int b_intervals) {
-    // Our heuristic worst case is ai * (bi + 1) + bi * (ai + 1)
-    int intervals = 2 * a_intervals * b_intervals + a_intervals + b_intervals;
-    // convert back to number of RunType values
-    return intervals_to_count(intervals);
-}
-
 static bool setEmptyCheck(SkRegion* result) {
     return result ? result->setEmpty() : false;
 }
@@ -1073,20 +1103,13 @@ bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op,
     const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals);
     const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals);
 
-    int dstCount = compute_worst_case_count(a_intervals, b_intervals);
-    SkAutoSTMalloc<256, RunType> array(dstCount);
-
-#ifdef SK_DEBUG
-//  Sometimes helpful to seed everything with a known value when debugging
-//  sk_memset32((uint32_t*)array.get(), 0x7FFFFFFF, dstCount);
-#endif
-
-    int count = operate(a_runs, b_runs, array.get(), op, nullptr == result);
-    SkASSERT(count <= dstCount);
+    RunArray array;
+    int count = operate(a_runs, b_runs, &array, op, nullptr == result);
+    SkASSERT(count <= array.count());
 
     if (result) {
         SkASSERT(count >= 0);
-        return result->setRuns(array.get(), count);
+        return result->setRuns(&array[0], count);
     } else {
         return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count);
     }