record yspancount and intervalcount in regions
Review URL: https://codereview.appspot.com/6132055
git-svn-id: http://skia.googlecode.com/svn/trunk@3808 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/include/core/SkRegion.h b/include/core/SkRegion.h
index f957cb5..9090a6d 100644
--- a/include/core/SkRegion.h
+++ b/include/core/SkRegion.h
@@ -382,15 +382,18 @@
};
friend class android::Region; // needed for marshalling efficiently
- void allocateRuns(int count); // allocate space for count runs
struct RunHead;
+
+ // allocate space for count runs
+ void allocateRuns(int count, int ySpanCount, int intervalCount);
+ void allocateRuns(const RunHead& src);
SkIRect fBounds;
RunHead* fRunHead;
void freeRuns();
- const RunType* getRuns(RunType tmpStorage[], int* count) const;
+ const RunType* getRuns(RunType tmpStorage[], int* intervals) const;
bool setRuns(RunType runs[], int count);
int count_runtype_values(int* itop, int* ibot) const;
@@ -399,7 +402,7 @@
RunType runs[kRectRegionRuns]);
// returns true if runs are just a rect
static bool ComputeRunBounds(const RunType runs[], int count,
- SkIRect* bounds);
+ SkIRect*, int* ySpanCount, int* intervalCount);
/**
* If the last arg is null, just return if the result is non-empty,
diff --git a/src/core/SkRegion.cpp b/src/core/SkRegion.cpp
index fd95848..a7e88f4 100644
--- a/src/core/SkRegion.cpp
+++ b/src/core/SkRegion.cpp
@@ -27,7 +27,8 @@
// returns true if runs are just a rect
bool SkRegion::ComputeRunBounds(const SkRegion::RunType runs[], int count,
- SkIRect* bounds) {
+ SkIRect* bounds, int* ySpanCountPtr,
+ int* intervalCountPtr) {
assert_sentinel(runs[0], false); // top
if (count == kRectRegionRuns) {
@@ -41,21 +42,36 @@
SkASSERT(runs[2] < runs[3]); // valid width
bounds->set(runs[2], runs[0], runs[3], runs[1]);
+ *ySpanCountPtr = 1;
+ *intervalCountPtr = 1;
return true;
}
int left = SK_MaxS32;
int rite = SK_MinS32;
int bot;
+ int ySpanCount = 0;
+ int intervalCount = 0;
bounds->fTop = *runs++;
do {
bot = *runs++;
+ ySpanCount += 1;
+
if (*runs < SkRegion::kRunTypeSentinel) {
if (left > *runs) {
left = *runs;
}
+
+ const RunType* prevRuns = runs;
runs = skip_scanline(runs);
+ // 2 run values == 1 pair, so hench the shift
+ // runs - prevRuns will be odd, since it is #pairs + 1 for the sentinel
+ // but our shift still gives us the right answer. More correct would
+ // be (runs - prevRuns - 1) >> 1, but that extra math is not needed
+ // since the shift truncates away the odd value.
+ intervalCount += (runs - prevRuns) >> 1;
+
if (rite < runs[-2]) {
rite = runs[-2];
}
@@ -63,9 +79,12 @@
runs += 1; // skip X-sentinel
}
} while (runs[0] < SkRegion::kRunTypeSentinel);
+
bounds->fLeft = left;
bounds->fRight = rite;
bounds->fBottom = bot;
+ *ySpanCountPtr = ySpanCount;
+ *intervalCountPtr = intervalCount;
return false;
}
@@ -102,8 +121,14 @@
}
}
-void SkRegion::allocateRuns(int count) {
- fRunHead = RunHead::Alloc(count);
+void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) {
+ fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount);
+}
+
+void SkRegion::allocateRuns(const RunHead& head) {
+ fRunHead = RunHead::Alloc(head.fRunCount,
+ head.getYSpanCount(),
+ head.getIntervalCount());
}
SkRegion& SkRegion::operator=(const SkRegion& src) {
@@ -206,6 +231,9 @@
maxT = 2;
} else {
SkASSERT(this->isComplex());
+
+ // compute the intervalCount, for consistency checking
+#ifdef SK_DEBUG
// skip the top
const RunType* runs = fRunHead->readonly_runs() + 1;
maxT = 0;
@@ -219,6 +247,10 @@
}
runs = next;
} while (runs[0] < SkRegion::kRunTypeSentinel);
+
+ SkASSERT(fRunHead->getIntervalCount() * 2 == maxT);
+#endif
+ maxT = fRunHead->getIntervalCount() * 2;
}
*itop = fBounds.fTop;
*ibot = fBounds.fBottom;
@@ -271,7 +303,8 @@
SkASSERT(count >= kRectRegionRuns);
- if (ComputeRunBounds(runs, count, &fBounds)) {
+ int ySpanCount, intervalCount;
+ if (ComputeRunBounds(runs, count, &fBounds, &ySpanCount, &intervalCount)) {
// SkDEBUGF(("setRuns: rect[%d %d %d %d]\n", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom));
return this->setRect(fBounds);
}
@@ -296,12 +329,16 @@
}
#endif
this->freeRuns();
- this->allocateRuns(count);
+ this->allocateRuns(count, ySpanCount, intervalCount);
}
// must call this before we can write directly into runs()
// in case we are sharing the buffer with another region (copy on write)
fRunHead = fRunHead->ensureWritable();
+ // we may not have reallocated the runhead (because the total-size is the
+ // the same) but we may still different yspans or xpairs, so update these.
+ fRunHead->updateYSpanCount(ySpanCount);
+ fRunHead->updateIntervalCount(intervalCount);
memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType));
SkDEBUGCODE(this->validate();)
@@ -380,19 +417,19 @@
}
const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[],
- int* count) const {
- SkASSERT(tmpStorage && count);
+ int* intervals) const {
+ SkASSERT(tmpStorage && intervals);
const RunType* runs = tmpStorage;
if (this->isEmpty()) {
tmpStorage[0] = kRunTypeSentinel;
- *count = 1;
+ *intervals = 0;
} else if (this->isRect()) {
BuildRectRuns(fBounds, tmpStorage);
- *count = kRectRegionRuns;
+ *intervals = 1;
} else {
- *count = fRunHead->fRunCount;
runs = fRunHead->readonly_runs();
+ *intervals = fRunHead->getIntervalCount();
}
return runs;
}
@@ -478,7 +515,7 @@
dst->fRunHead = dst->fRunHead->ensureWritable();
} else {
SkRegion tmp;
- tmp.allocateRuns(fRunHead->fRunCount);
+ tmp.allocateRuns(*fRunHead);
tmp.fBounds = fBounds;
dst->swap(tmp);
}
@@ -867,12 +904,10 @@
return 1 + intervals * 4 + 1;
}
-/* Given the counts of RunTypes in two regions, return the worst-case number
+/* 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_count, int b_count) {
- int a_intervals = count_to_intervals(a_count);
- int b_intervals = count_to_intervals(b_count);
+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
@@ -967,15 +1002,16 @@
RunType tmpA[kRectRegionRuns];
RunType tmpB[kRectRegionRuns];
- int a_count, b_count;
- const RunType* a_runs = rgna->getRuns(tmpA, &a_count);
- const RunType* b_runs = rgnb->getRuns(tmpB, &b_count);
+ int a_intervals, b_intervals;
+ 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_count, b_count);
- SkAutoSTMalloc<64, RunType> array(dstCount);
+ int dstCount = compute_worst_case_count(a_intervals, b_intervals);
+ SkAutoSTMalloc<256, RunType> array(dstCount);
int count = operate(a_runs, b_runs, array.get(), op, NULL == result);
SkASSERT(count <= dstCount);
+
if (result) {
SkASSERT(count >= 0);
return result->setRuns(array.get(), count);
@@ -999,6 +1035,7 @@
if (!this->isEmpty()) {
size += sizeof(fBounds);
if (this->isComplex()) {
+ size += 2 * sizeof(int32_t); // ySpanCount + intervalCount
size += fRunHead->fRunCount * sizeof(RunType);
}
}
@@ -1016,6 +1053,8 @@
buffer.write(&fBounds, sizeof(fBounds));
if (!isRect) {
+ buffer.write32(fRunHead->getYSpanCount());
+ buffer.write32(fRunHead->getIntervalCount());
buffer.write(fRunHead->readonly_runs(),
fRunHead->fRunCount * sizeof(RunType));
}
@@ -1034,7 +1073,9 @@
if (count == 0) {
tmp.fRunHead = SkRegion_gRectRunHeadPtr;
} else {
- tmp.allocateRuns(count);
+ int32_t ySpanCount = buffer.readS32();
+ int32_t intervalCount = buffer.readS32();
+ tmp.allocateRuns(count, ySpanCount, intervalCount);
buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType));
}
}
@@ -1093,9 +1134,15 @@
// check that our bounds match our runs
{
SkIRect bounds;
- bool isARect = ComputeRunBounds(run, stop - run, &bounds);
+ int ySpanCount, intervalCount;
+ bool isARect = ComputeRunBounds(run, stop - run, &bounds,
+ &ySpanCount, &intervalCount);
SkASSERT(!isARect);
SkASSERT(bounds == fBounds);
+ SkASSERT(ySpanCount > 0);
+ SkASSERT(fRunHead->getYSpanCount() == ySpanCount);
+ SkASSERT(intervalCount > 1);
+ SkASSERT(fRunHead->getIntervalCount() == intervalCount);
}
SkASSERT(*run == fBounds.fTop);
diff --git a/src/core/SkRegionPriv.h b/src/core/SkRegionPriv.h
index cef4b35..fe0dfbe 100644
--- a/src/core/SkRegionPriv.h
+++ b/src/core/SkRegionPriv.h
@@ -22,15 +22,57 @@
int32_t fRefCnt;
int32_t fRunCount;
+ /**
+ * Number of spans with different Y values. This does not count the initial
+ * Top value, nor does it count the final Y-Sentinel value. In the logical
+ * case of a rectangle, this would return 1, and an empty region would
+ * return 0.
+ */
+ int getYSpanCount() const {
+ return fYSpanCount;
+ }
+
+ /**
+ * Number of intervals in the entire region. This equals the number of
+ * rects that would be returned by the Iterator. In the logical case of
+ * a rect, this would return 1, and an empty region would return 0.
+ */
+ int getIntervalCount() const {
+ return fIntervalCount;
+ }
+
+ void updateYSpanCount(int n) {
+ SkASSERT(n > 0);
+ fYSpanCount = n;
+ }
+
+ void updateIntervalCount(int n) {
+ SkASSERT(n > 1);
+ fIntervalCount = n;
+ }
+
static RunHead* Alloc(int count) {
//SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
//SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));
-
+
SkASSERT(count >= SkRegion::kRectRegionRuns);
-
+
RunHead* head = (RunHead*)sk_malloc_throw(sizeof(RunHead) + count * sizeof(RunType));
head->fRefCnt = 1;
head->fRunCount = count;
+ // these must be filled in later, otherwise we will be invalid
+ head->fYSpanCount = 0;
+ head->fIntervalCount = 0;
+ return head;
+ }
+
+ static RunHead* Alloc(int count, int yspancount, int intervalCount) {
+ SkASSERT(yspancount > 0);
+ SkASSERT(intervalCount > 1);
+
+ RunHead* head = Alloc(count);
+ head->fYSpanCount = yspancount;
+ head->fIntervalCount = intervalCount;
return head;
}
@@ -57,7 +99,7 @@
// We need to alloc & copy the current region before we call
// sk_atomic_dec because it could be freed in the meantime,
// otherwise.
- writable = Alloc(fRunCount);
+ writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
memcpy(writable->writable_runs(), this->readonly_runs(),
fRunCount * sizeof(RunType));
@@ -70,6 +112,10 @@
}
return writable;
}
+
+private:
+ int32_t fYSpanCount;
+ int32_t fIntervalCount;
};
#endif
diff --git a/src/core/SkRegion_path.cpp b/src/core/SkRegion_path.cpp
index 345ecf8..af88353 100644
--- a/src/core/SkRegion_path.cpp
+++ b/src/core/SkRegion_path.cpp
@@ -302,10 +302,14 @@
this->setRect(fBounds);
} else {
SkRegion tmp;
+ int ySpanCount, intervalCount;
tmp.fRunHead = RunHead::Alloc(count);
builder.copyToRgn(tmp.fRunHead->writable_runs());
- ComputeRunBounds(tmp.fRunHead->readonly_runs(), count, &tmp.fBounds);
+ ComputeRunBounds(tmp.fRunHead->readonly_runs(), count, &tmp.fBounds,
+ &ySpanCount, &intervalCount);
+ tmp.fRunHead->updateYSpanCount(ySpanCount);
+ tmp.fRunHead->updateIntervalCount(intervalCount);
this->swap(tmp);
}
SkDEBUGCODE(this->validate();)