blob: 0a8ab6557ecc4e46b45e177db14df18237a17959 [file] [log] [blame]
/*
* Copyright 2006 The Android Open Source Project
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "SkRegionPriv.h"
#include "SkTemplates.h"
#include "SkThread.h"
SkDEBUGCODE(int32_t gRgnAllocCounter;)
/////////////////////////////////////////////////////////////////////////////////////////////////
/* Pass in a scanline, beginning with the Left value of the pair (i.e. not the Y beginning)
*/
static SkRegion::RunType* skip_scanline(const SkRegion::RunType runs[])
{
while (runs[0] != SkRegion::kRunTypeSentinel)
{
SkASSERT(runs[0] < runs[1]); // valid span
runs += 2;
}
return (SkRegion::RunType*)(runs + 1); // return past the X-sentinel
}
// returns true if runs are just a rect
bool SkRegion::ComputeRunBounds(const SkRegion::RunType runs[], int count, SkIRect* bounds)
{
assert_sentinel(runs[0], false); // top
if (count == kRectRegionRuns)
{
assert_sentinel(runs[1], false); // bottom
assert_sentinel(runs[2], false); // left
assert_sentinel(runs[3], false); // right
assert_sentinel(runs[4], true);
assert_sentinel(runs[5], true);
SkASSERT(runs[0] < runs[1]); // valid height
SkASSERT(runs[2] < runs[3]); // valid width
bounds->set(runs[2], runs[0], runs[3], runs[1]);
return true;
}
int left = SK_MaxS32;
int rite = SK_MinS32;
int bot;
bounds->fTop = *runs++;
do {
bot = *runs++;
if (*runs < SkRegion::kRunTypeSentinel)
{
if (left > *runs)
left = *runs;
runs = skip_scanline(runs);
if (rite < runs[-2])
rite = runs[-2];
}
else
runs += 1; // skip X-sentinel
} while (runs[0] < SkRegion::kRunTypeSentinel);
bounds->fLeft = left;
bounds->fRight = rite;
bounds->fBottom = bot;
return false;
}
//////////////////////////////////////////////////////////////////////////
SkRegion::SkRegion() {
fBounds.set(0, 0, 0, 0);
fRunHead = SkRegion_gEmptyRunHeadPtr;
}
SkRegion::SkRegion(const SkRegion& src) {
fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
this->setRegion(src);
}
SkRegion::SkRegion(const SkIRect& rect) {
fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
this->setRect(rect);
}
SkRegion::~SkRegion() {
this->freeRuns();
}
void SkRegion::freeRuns() {
if (fRunHead->isComplex()) {
SkASSERT(fRunHead->fRefCnt >= 1);
if (sk_atomic_dec(&fRunHead->fRefCnt) == 1) {
//SkASSERT(gRgnAllocCounter > 0);
//SkDEBUGCODE(sk_atomic_dec(&gRgnAllocCounter));
//SkDEBUGF(("************** gRgnAllocCounter::free %d\n", gRgnAllocCounter));
sk_free(fRunHead);
}
}
}
void SkRegion::allocateRuns(int count) {
fRunHead = RunHead::Alloc(count);
}
SkRegion& SkRegion::operator=(const SkRegion& src) {
(void)this->setRegion(src);
return *this;
}
void SkRegion::swap(SkRegion& other) {
SkTSwap<SkIRect>(fBounds, other.fBounds);
SkTSwap<RunHead*>(fRunHead, other.fRunHead);
}
bool SkRegion::setEmpty() {
this->freeRuns();
fBounds.set(0, 0, 0, 0);
fRunHead = SkRegion_gEmptyRunHeadPtr;
return false;
}
bool SkRegion::setRect(int32_t left, int32_t top,
int32_t right, int32_t bottom) {
if (left >= right || top >= bottom) {
return this->setEmpty();
}
this->freeRuns();
fBounds.set(left, top, right, bottom);
fRunHead = SkRegion_gRectRunHeadPtr;
return true;
}
bool SkRegion::setRect(const SkIRect& r) {
return this->setRect(r.fLeft, r.fTop, r.fRight, r.fBottom);
}
bool SkRegion::setRegion(const SkRegion& src) {
if (this != &src) {
this->freeRuns();
fBounds = src.fBounds;
fRunHead = src.fRunHead;
if (fRunHead->isComplex()) {
sk_atomic_inc(&fRunHead->fRefCnt);
}
}
return fRunHead != SkRegion_gEmptyRunHeadPtr;
}
bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) {
SkRegion tmp(rect);
return this->op(tmp, rgn, op);
}
bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) {
SkRegion tmp(rect);
return this->op(rgn, tmp, op);
}
///////////////////////////////////////////////////////////////////////////////
#ifdef SK_BUILD_FOR_ANDROID
char* SkRegion::toString()
{
Iterator iter(*this);
int count = 0;
while (!iter.done()) {
count++;
iter.next();
}
// 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0'
const int max = (count*((11*4)+5))+11+1;
char* result = (char*)malloc(max);
if (result == NULL) {
return NULL;
}
count = sprintf(result, "SkRegion(");
iter.reset(*this);
while (!iter.done()) {
const SkIRect& r = iter.rect();
count += sprintf(result+count, "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom);
iter.next();
}
count += sprintf(result+count, ")");
return result;
}
#endif
//////////////////////////////////////////////////////////////////////////////////////
int SkRegion::count_runtype_values(int* itop, int* ibot) const
{
if (this == NULL)
{
*itop = SK_MinS32;
*ibot = SK_MaxS32;
return 0;
}
int maxT;
if (this->isRect())
maxT = 2;
else
{
SkASSERT(this->isComplex());
// skip the top
const RunType* runs = fRunHead->readonly_runs() + 1;
maxT = 0;
do {
const RunType* next = skip_scanline(runs + 1);
SkASSERT(next > runs);
int T = (int)(next - runs - 1);
if (maxT < T)
maxT = T;
runs = next;
} while (runs[0] < SkRegion::kRunTypeSentinel);
}
*itop = fBounds.fTop;
*ibot = fBounds.fBottom;
return maxT;
}
bool SkRegion::setRuns(RunType runs[], int count)
{
SkDEBUGCODE(this->validate();)
SkASSERT(count > 0);
if (count <= 2)
{
// SkDEBUGF(("setRuns: empty\n"));
assert_sentinel(runs[count-1], true);
return this->setEmpty();
}
// trim off any empty spans from the top and bottom
// weird I should need this, perhaps op() could be smarter...
if (count > kRectRegionRuns)
{
RunType* stop = runs + count;
assert_sentinel(runs[0], false); // top
assert_sentinel(runs[1], false); // bottom
if (runs[2] == SkRegion::kRunTypeSentinel) // should be first left...
{
runs += 2; // skip empty initial span
runs[0] = runs[-1]; // set new top to prev bottom
assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row
assert_sentinel(runs[2], false); // left
assert_sentinel(runs[3], false); // right
}
// now check for a trailing empty span
assert_sentinel(stop[-1], true);
assert_sentinel(stop[-2], true);
assert_sentinel(stop[-3], false); // should be last right
if (stop[-4] == SkRegion::kRunTypeSentinel) // eek, stop[-3] was a bottom with no x-runs
{
stop[-3] = SkRegion::kRunTypeSentinel; // kill empty last span
stop -= 2;
assert_sentinel(stop[-1], true);
assert_sentinel(stop[-2], true);
assert_sentinel(stop[-3], false);
assert_sentinel(stop[-4], false);
assert_sentinel(stop[-5], false);
}
count = (int)(stop - runs);
}
SkASSERT(count >= kRectRegionRuns);
if (ComputeRunBounds(runs, count, &fBounds))
{
// SkDEBUGF(("setRuns: rect[%d %d %d %d]\n", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom));
return this->setRect(fBounds);
}
// if we get here, we need to become a complex region
if (!fRunHead->isComplex() || fRunHead->fRunCount != count)
{
#ifdef SK_DEBUGx
SkDebugf("setRuns: rgn [");
{
const RunType* r = runs;
SkDebugf(" top: %d\n", *r++);
while (*r < SkRegion::kRunTypeSentinel)
{
SkDebugf(" bottom: %d", *r++);
while (*r < SkRegion::kRunTypeSentinel)
{
SkDebugf(" [%d %d]", r[0], r[1]);
r += 2;
}
SkDebugf("\n");
}
}
#endif
this->freeRuns();
this->allocateRuns(count);
}
// 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();
memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType));
SkDEBUGCODE(this->validate();)
return true;
}
void SkRegion::BuildRectRuns(const SkIRect& bounds,
RunType runs[kRectRegionRuns])
{
runs[0] = bounds.fTop;
runs[1] = bounds.fBottom;
runs[2] = bounds.fLeft;
runs[3] = bounds.fRight;
runs[4] = kRunTypeSentinel;
runs[5] = kRunTypeSentinel;
}
static SkRegion::RunType* find_scanline(const SkRegion::RunType runs[], int y)
{
SkASSERT(y >= runs[0]); // if this fails, we didn't do a quick check on the boudns
runs += 1; // skip top-Y
for (;;)
{
if (runs[0] == SkRegion::kRunTypeSentinel)
break;
if (y < runs[0])
return (SkRegion::RunType*)&runs[1];
runs = skip_scanline(runs + 1); // skip the Y value before calling
}
return NULL;
}
bool SkRegion::contains(int32_t x, int32_t y) const
{
if (!fBounds.contains(x, y))
return false;
if (this->isRect())
return true;
SkASSERT(this->isComplex());
const RunType* runs = find_scanline(fRunHead->readonly_runs(), y);
if (runs)
{ for (;;)
{ if (x < runs[0])
break;
if (x < runs[1])
return true;
runs += 2;
}
}
return false;
}
bool SkRegion::contains(const SkIRect& r) const
{
SkRegion tmp(r);
return this->contains(tmp);
}
bool SkRegion::contains(const SkRegion& rgn) const
{
if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds))
return false;
if (this->isRect())
return true;
SkRegion tmp;
tmp.op(*this, rgn, kUnion_Op);
return tmp == *this;
}
const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[], int* count) const
{
SkASSERT(tmpStorage && count);
const RunType* runs = tmpStorage;
if (this->isEmpty())
{
tmpStorage[0] = kRunTypeSentinel;
*count = 1;
}
else if (this->isRect())
{
BuildRectRuns(fBounds, tmpStorage);
*count = kRectRegionRuns;
}
else
{
*count = fRunHead->fRunCount;
runs = fRunHead->readonly_runs();
}
return runs;
}
/////////////////////////////////////////////////////////////////////////////////////
bool SkRegion::intersects(const SkIRect& r) const {
if (this->isEmpty() || r.isEmpty()) {
return false;
}
if (!SkIRect::Intersects(fBounds, r)) {
return false;
}
if (this->isRect()) {
return true;
}
// we are complex
SkRegion tmp;
return tmp.op(*this, r, kIntersect_Op);
}
bool SkRegion::intersects(const SkRegion& rgn) const {
if (this->isEmpty() || rgn.isEmpty()) {
return false;
}
if (!SkIRect::Intersects(fBounds, rgn.fBounds)) {
return false;
}
if (this->isRect() && rgn.isRect()) {
return true;
}
// one or both of us is complex
// TODO: write a faster version that aborts as soon as we write the first
// non-empty span, to avoid build the entire result
SkRegion tmp;
return tmp.op(*this, rgn, kIntersect_Op);
}
/////////////////////////////////////////////////////////////////////////////////////
bool operator==(const SkRegion& a, const SkRegion& b) {
SkDEBUGCODE(a.validate();)
SkDEBUGCODE(b.validate();)
if (&a == &b) {
return true;
}
if (a.fBounds != b.fBounds) {
return false;
}
const SkRegion::RunHead* ah = a.fRunHead;
const SkRegion::RunHead* bh = b.fRunHead;
// this catches empties and rects being equal
if (ah == bh) {
return true;
}
// now we insist that both are complex (but different ptrs)
if (!ah->isComplex() || !bh->isComplex()) {
return false;
}
return ah->fRunCount == bh->fRunCount &&
!memcmp(ah->readonly_runs(), bh->readonly_runs(),
ah->fRunCount * sizeof(SkRegion::RunType));
}
void SkRegion::translate(int dx, int dy, SkRegion* dst) const {
SkDEBUGCODE(this->validate();)
if (NULL == dst) {
return;
}
if (this->isEmpty()) {
dst->setEmpty();
} else if (this->isRect()) {
dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy,
fBounds.fRight + dx, fBounds.fBottom + dy);
} else {
if (this == dst) {
dst->fRunHead = dst->fRunHead->ensureWritable();
} else {
SkRegion tmp;
tmp.allocateRuns(fRunHead->fRunCount);
tmp.fBounds = fBounds;
dst->swap(tmp);
}
dst->fBounds.offset(dx, dy);
const RunType* sruns = fRunHead->readonly_runs();
RunType* druns = dst->fRunHead->writable_runs();
*druns++ = (SkRegion::RunType)(*sruns++ + dy); // top
for (;;) {
int bottom = *sruns++;
if (bottom == kRunTypeSentinel) {
break;
}
*druns++ = (SkRegion::RunType)(bottom + dy); // bottom;
for (;;) {
int x = *sruns++;
if (x == kRunTypeSentinel) {
break;
}
*druns++ = (SkRegion::RunType)(x + dx);
*druns++ = (SkRegion::RunType)(*sruns++ + dx);
}
*druns++ = kRunTypeSentinel; // x sentinel
}
*druns++ = kRunTypeSentinel; // y sentinel
SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount);
SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount);
}
SkDEBUGCODE(this->validate();)
}
///////////////////////////////////////////////////////////////////////////////
bool SkRegion::setRects(const SkIRect rects[], int count) {
if (0 == count) {
this->setEmpty();
} else {
this->setRect(rects[0]);
for (int i = 1; i < count; i++) {
this->op(rects[i], kUnion_Op);
}
}
return !this->isEmpty();
}
///////////////////////////////////////////////////////////////////////////////
#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized
#pragma warning ( push )
#pragma warning ( disable : 4701 )
#endif
#ifdef SK_DEBUG
static void assert_valid_pair(int left, int rite)
{
SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite);
}
#else
#define assert_valid_pair(left, rite)
#endif
struct spanRec {
const SkRegion::RunType* fA_runs;
const SkRegion::RunType* fB_runs;
int fA_left, fA_rite, fB_left, fB_rite;
int fLeft, fRite, fInside;
void init(const SkRegion::RunType a_runs[], const SkRegion::RunType b_runs[])
{
fA_left = *a_runs++;
fA_rite = *a_runs++;
fB_left = *b_runs++;
fB_rite = *b_runs++;
fA_runs = a_runs;
fB_runs = b_runs;
}
bool done() const
{
SkASSERT(fA_left <= SkRegion::kRunTypeSentinel);
SkASSERT(fB_left <= SkRegion::kRunTypeSentinel);
return fA_left == SkRegion::kRunTypeSentinel && fB_left == SkRegion::kRunTypeSentinel;
}
void next()
{
assert_valid_pair(fA_left, fA_rite);
assert_valid_pair(fB_left, fB_rite);
int inside, left, rite SK_INIT_TO_AVOID_WARNING;
bool a_flush = false;
bool b_flush = false;
int a_left = fA_left;
int a_rite = fA_rite;
int b_left = fB_left;
int b_rite = fB_rite;
if (a_left < b_left)
{
inside = 1;
left = a_left;
if (a_rite <= b_left) // [...] <...>
{
rite = a_rite;
a_flush = true;
}
else // [...<..]...> or [...<...>...]
rite = a_left = b_left;
}
else if (b_left < a_left)
{
inside = 2;
left = b_left;
if (b_rite <= a_left) // [...] <...>
{
rite = b_rite;
b_flush = true;
}
else // [...<..]...> or [...<...>...]
rite = b_left = a_left;
}
else // a_left == b_left
{
inside = 3;
left = a_left; // or b_left
if (a_rite <= b_rite)
{
rite = b_left = a_rite;
a_flush = true;
}
if (b_rite <= a_rite)
{
rite = a_left = b_rite;
b_flush = true;
}
}
if (a_flush)
{
a_left = *fA_runs++;
a_rite = *fA_runs++;
}
if (b_flush)
{
b_left = *fB_runs++;
b_rite = *fB_runs++;
}
SkASSERT(left <= rite);
// now update our state
fA_left = a_left;
fA_rite = a_rite;
fB_left = b_left;
fB_rite = b_rite;
fLeft = left;
fRite = rite;
fInside = inside;
}
};
static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[],
const SkRegion::RunType b_runs[],
SkRegion::RunType dst[],
int min, int max)
{
spanRec rec;
bool firstInterval = true;
rec.init(a_runs, b_runs);
while (!rec.done())
{
rec.next();
int left = rec.fLeft;
int rite = rec.fRite;
// 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)
{
*dst++ = (SkRegion::RunType)(left);
*dst++ = (SkRegion::RunType)(rite);
firstInterval = false;
}
else // update the right edge
dst[-1] = (SkRegion::RunType)(rite);
}
}
*dst++ = SkRegion::kRunTypeSentinel;
return dst;
}
#if defined _WIN32 && _MSC_VER >= 1300
#pragma warning ( pop )
#endif
static const struct {
uint8_t fMin;
uint8_t fMax;
} gOpMinMax[] = {
{ 1, 1 }, // Difference
{ 3, 3 }, // Intersection
{ 1, 3 }, // Union
{ 1, 2 } // XOR
};
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;
}
void addSpan(int bottom, const SkRegion::RunType a_runs[], const SkRegion::RunType b_runs[])
{
SkRegion::RunType* start = fPrevDst + fPrevLen + 1; // skip X values and slot for the next Y
SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax);
size_t len = stop - start;
if (fPrevLen == len && !memcmp(fPrevDst, start, len * sizeof(SkRegion::RunType))) // update Y value
fPrevDst[-1] = (SkRegion::RunType)(bottom);
else // accept the new span
{
if (len == 1 && fPrevLen == 0) {
fTop = (SkRegion::RunType)(bottom); // just update our bottom
} else {
start[-1] = (SkRegion::RunType)(bottom);
fPrevDst = start;
fPrevLen = len;
}
}
}
int flush()
{
fStartDst[0] = fTop;
fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel;
return (int)(fPrevDst - fStartDst + fPrevLen + 1);
}
uint8_t fMin, fMax;
private:
SkRegion::RunType* fStartDst;
SkRegion::RunType* fPrevDst;
size_t fPrevLen;
SkRegion::RunType fTop;
};
static int operate(const SkRegion::RunType a_runs[],
const SkRegion::RunType b_runs[],
SkRegion::RunType dst[],
SkRegion::Op op) {
const SkRegion::RunType gSentinel[] = {
SkRegion::kRunTypeSentinel,
// just need a 2nd value, since spanRec.init() reads 2 values, even
// though if the first value is the sentinel, it ignores the 2nd value.
// w/o the 2nd value here, we might read uninitialized memory.
0,
};
int a_top = *a_runs++;
int a_bot = *a_runs++;
int b_top = *b_runs++;
int b_bot = *b_runs++;
assert_sentinel(a_top, false);
assert_sentinel(a_bot, false);
assert_sentinel(b_top, false);
assert_sentinel(b_bot, false);
RgnOper oper(SkMin32(a_top, b_top), dst, op);
bool firstInterval = true;
int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test
while (a_bot < SkRegion::kRunTypeSentinel ||
b_bot < SkRegion::kRunTypeSentinel) {
int top, bot SK_INIT_TO_AVOID_WARNING;
const SkRegion::RunType* run0 = gSentinel;
const SkRegion::RunType* run1 = gSentinel;
bool a_flush = false;
bool b_flush = false;
if (a_top < b_top) {
top = a_top;
run0 = a_runs;
if (a_bot <= b_top) { // [...] <...>
bot = a_bot;
a_flush = true;
} else { // [...<..]...> or [...<...>...]
bot = a_top = b_top;
}
} else if (b_top < a_top) {
top = b_top;
run1 = b_runs;
if (b_bot <= a_top) { // [...] <...>
bot = b_bot;
b_flush = true;
} else { // [...<..]...> or [...<...>...]
bot = b_top = a_top;
}
} else { // a_top == b_top
top = a_top; // or b_top
run0 = a_runs;
run1 = b_runs;
if (a_bot <= b_bot) {
bot = b_top = a_bot;
a_flush = true;
}
if (b_bot <= a_bot) {
bot = a_top = b_bot;
b_flush = true;
}
}
if (top > prevBot) {
oper.addSpan(top, gSentinel, gSentinel);
}
oper.addSpan(bot, run0, run1);
firstInterval = false;
if (a_flush) {
a_runs = skip_scanline(a_runs);
a_top = a_bot;
a_bot = *a_runs++;
if (a_bot == SkRegion::kRunTypeSentinel) {
a_top = a_bot;
}
}
if (b_flush) {
b_runs = skip_scanline(b_runs);
b_top = b_bot;
b_bot = *b_runs++;
if (b_bot == SkRegion::kRunTypeSentinel) {
b_top = b_bot;
}
}
prevBot = bot;
}
return oper.flush();
}
///////////////////////////////////////////////////////////////////////////////
/* Given count RunTypes in a complex region, return the worst case number of
logical intervals that represents (i.e. number of rects that would be
returned from the iterator).
We could just return count/2, since there must be at least 2 values per
interval, but we can first trim off the const overhead of the initial TOP
value, plus the final BOTTOM + 2 sentinels.
*/
static int count_to_intervals(int count) {
SkASSERT(count >= 6); // a single rect is 6 values
return (count - 4) >> 1;
}
/* 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 LEFT RIGHT SENTINEL) + SENTINEL
*/
static int intervals_to_count(int intervals) {
return 1 + intervals * 4 + 1;
}
/* Given the counts 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);
// 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);
}
bool SkRegion::op(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op)
{
SkDEBUGCODE(this->validate();)
SkASSERT((unsigned)op < kOpCount);
if (kReplace_Op == op)
return this->set(rgnbOrig);
// swith to using pointers, so we can swap them as needed
const SkRegion* rgna = &rgnaOrig;
const SkRegion* rgnb = &rgnbOrig;
// after this point, do not refer to rgnaOrig or rgnbOrig!!!
// collaps difference and reverse-difference into just difference
if (kReverseDifference_Op == op)
{
SkTSwap<const SkRegion*>(rgna, rgnb);
op = kDifference_Op;
}
SkIRect bounds;
bool a_empty = rgna->isEmpty();
bool b_empty = rgnb->isEmpty();
bool a_rect = rgna->isRect();
bool b_rect = rgnb->isRect();
switch (op) {
case kDifference_Op:
if (a_empty)
return this->setEmpty();
if (b_empty || !SkIRect::Intersects(rgna->fBounds, rgnb->fBounds))
return this->setRegion(*rgna);
break;
case kIntersect_Op:
if ((a_empty | b_empty)
|| !bounds.intersect(rgna->fBounds, rgnb->fBounds))
return this->setEmpty();
if (a_rect & b_rect)
return this->setRect(bounds);
break;
case kUnion_Op:
if (a_empty)
return this->setRegion(*rgnb);
if (b_empty)
return this->setRegion(*rgna);
if (a_rect && rgna->fBounds.contains(rgnb->fBounds))
return this->setRegion(*rgna);
if (b_rect && rgnb->fBounds.contains(rgna->fBounds))
return this->setRegion(*rgnb);
break;
case kXOR_Op:
if (a_empty)
return this->setRegion(*rgnb);
if (b_empty)
return this->setRegion(*rgna);
break;
default:
SkDEBUGFAIL("unknown region op");
return !this->isEmpty();
}
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 dstCount = compute_worst_case_count(a_count, b_count);
SkAutoSTMalloc<32, RunType> array(dstCount);
int count = operate(a_runs, b_runs, array.get(), op);
SkASSERT(count <= dstCount);
return this->setRuns(array.get(), count);
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////
#include "SkBuffer.h"
uint32_t SkRegion::flatten(void* storage) const {
if (NULL == storage) {
uint32_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount
if (!this->isEmpty()) {
size += sizeof(fBounds);
if (this->isComplex()) {
size += fRunHead->fRunCount * sizeof(RunType);
}
}
return size;
}
SkWBuffer buffer(storage);
if (this->isEmpty()) {
buffer.write32(-1);
} else {
bool isRect = this->isRect();
buffer.write32(isRect ? 0 : fRunHead->fRunCount);
buffer.write(&fBounds, sizeof(fBounds));
if (!isRect) {
buffer.write(fRunHead->readonly_runs(),
fRunHead->fRunCount * sizeof(RunType));
}
}
return buffer.pos();
}
uint32_t SkRegion::unflatten(const void* storage) {
SkRBuffer buffer(storage);
SkRegion tmp;
int32_t count;
count = buffer.readS32();
if (count >= 0) {
buffer.read(&tmp.fBounds, sizeof(tmp.fBounds));
if (count == 0) {
tmp.fRunHead = SkRegion_gRectRunHeadPtr;
} else {
tmp.allocateRuns(count);
buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType));
}
}
this->swap(tmp);
return buffer.pos();
}
///////////////////////////////////////////////////////////////////////////////
const SkRegion& SkRegion::GetEmptyRegion() {
static SkRegion gEmpty;
return gEmpty;
}
///////////////////////////////////////////////////////////////////////////////
#ifdef SK_DEBUG
static const SkRegion::RunType* validate_line(const SkRegion::RunType run[], const SkIRect& bounds)
{
// *run is the bottom of the current span
SkASSERT(*run > bounds.fTop);
SkASSERT(*run <= bounds.fBottom);
run += 1;
// check for empty span
if (*run != SkRegion::kRunTypeSentinel)
{
int prevRite = bounds.fLeft - 1;
do {
int left = *run++;
int rite = *run++;
SkASSERT(left < rite);
SkASSERT(left > prevRite);
SkASSERT(rite <= bounds.fRight);
prevRite = rite;
} while (*run < SkRegion::kRunTypeSentinel);
}
return run + 1; // skip sentinel
}
void SkRegion::validate() const
{
if (this->isEmpty())
{
// check for explicit empty (the zero rect), so we can compare rects to know when
// two regions are equal (i.e. emptyRectA == emptyRectB)
// this is stricter than just asserting fBounds.isEmpty()
SkASSERT(fBounds.fLeft == 0 && fBounds.fTop == 0 && fBounds.fRight == 0 && fBounds.fBottom == 0);
}
else
{
SkASSERT(!fBounds.isEmpty());
if (!this->isRect())
{
SkASSERT(fRunHead->fRefCnt >= 1);
SkASSERT(fRunHead->fRunCount >= kRectRegionRuns);
const RunType* run = fRunHead->readonly_runs();
const RunType* stop = run + fRunHead->fRunCount;
// check that our bounds match our runs
{
SkIRect bounds;
bool isARect = ComputeRunBounds(run, stop - run, &bounds);
SkASSERT(!isARect);
SkASSERT(bounds == fBounds);
}
SkASSERT(*run == fBounds.fTop);
run++;
do {
run = validate_line(run, fBounds);
} while (*run < kRunTypeSentinel);
SkASSERT(run + 1 == stop);
}
}
}
void SkRegion::dump() const
{
if (this->isEmpty())
SkDebugf(" rgn: empty\n");
else
{
SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
if (this->isComplex())
{
const RunType* runs = fRunHead->readonly_runs();
for (int i = 0; i < fRunHead->fRunCount; i++)
SkDebugf(" %d", runs[i]);
}
SkDebugf("\n");
}
}
#endif
/////////////////////////////////////////////////////////////////////////////////////
SkRegion::Iterator::Iterator(const SkRegion& rgn) {
this->reset(rgn);
}
bool SkRegion::Iterator::rewind() {
if (fRgn) {
this->reset(*fRgn);
return true;
}
return false;
}
void SkRegion::Iterator::reset(const SkRegion& rgn) {
fRgn = &rgn;
if (rgn.isEmpty()) {
fDone = true;
} else {
fDone = false;
if (rgn.isRect()) {
fRect = rgn.fBounds;
fRuns = NULL;
} else {
fRuns = rgn.fRunHead->readonly_runs();
fRect.set(fRuns[2], fRuns[0], fRuns[3], fRuns[1]);
fRuns += 4;
}
}
}
void SkRegion::Iterator::next() {
if (fDone) {
return;
}
if (fRuns == NULL) { // rect case
fDone = true;
return;
}
const RunType* runs = fRuns;
if (runs[0] < kRunTypeSentinel) { // valid X value
fRect.fLeft = runs[0];
fRect.fRight = runs[1];
runs += 2;
} else { // we're at the end of a line
runs += 1;
if (runs[0] < kRunTypeSentinel) { // valid Y value
if (runs[1] == kRunTypeSentinel) { // empty line
fRect.fTop = runs[0];
runs += 2;
} else {
fRect.fTop = fRect.fBottom;
}
fRect.fBottom = runs[0];
assert_sentinel(runs[1], false);
fRect.fLeft = runs[1];
fRect.fRight = runs[2];
runs += 3;
} else { // end of rgn
fDone = true;
}
}
fRuns = runs;
}
SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip)
: fIter(rgn), fClip(clip), fDone(true) {
const SkIRect& r = fIter.rect();
while (!fIter.done()) {
if (r.fTop >= clip.fBottom) {
break;
}
if (fRect.intersect(clip, r)) {
fDone = false;
break;
}
fIter.next();
}
}
void SkRegion::Cliperator::next() {
if (fDone) {
return;
}
const SkIRect& r = fIter.rect();
fDone = true;
fIter.next();
while (!fIter.done()) {
if (r.fTop >= fClip.fBottom) {
break;
}
if (fRect.intersect(fClip, r)) {
fDone = false;
break;
}
fIter.next();
}
}
///////////////////////////////////////////////////////////////////////////////
static SkRegion::RunType* find_y(const SkRegion::RunType runs[], int y) {
int top = *runs++;
if (top <= y) {
for (;;) {
int bot = *runs++;
if (bot > y) {
if (bot == SkRegion::kRunTypeSentinel ||
*runs == SkRegion::kRunTypeSentinel) {
break;
}
return (SkRegion::RunType*)runs;
}
runs = skip_scanline(runs);
}
}
return NULL;
}
SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left,
int right) {
SkDEBUGCODE(rgn.validate();)
const SkIRect& r = rgn.getBounds();
fDone = true;
if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom &&
right > r.fLeft && left < r.fRight) {
if (rgn.isRect()) {
if (left < r.fLeft) {
left = r.fLeft;
}
if (right > r.fRight) {
right = r.fRight;
}
fLeft = left;
fRight = right;
fRuns = NULL; // means we're a rect, not a rgn
fDone = false;
} else {
const SkRegion::RunType* runs = find_y(
rgn.fRunHead->readonly_runs(), y);
if (runs) {
for (;;) {
// runs[0..1] is to the right of the span, so we're done
if (runs[0] >= right) {
break;
}
// runs[0..1] is to the left of the span, so continue
if (runs[1] <= left) {
runs += 2;
continue;
}
// runs[0..1] intersects the span
fRuns = runs;
fLeft = left;
fRight = right;
fDone = false;
break;
}
}
}
}
}
bool SkRegion::Spanerator::next(int* left, int* right) {
if (fDone) {
return false;
}
if (fRuns == NULL) { // we're a rect
fDone = true; // ok, now we're done
if (left) {
*left = fLeft;
}
if (right) {
*right = fRight;
}
return true; // this interval is legal
}
const SkRegion::RunType* runs = fRuns;
if (runs[0] >= fRight) {
fDone = true;
return false;
}
SkASSERT(runs[1] > fLeft);
if (left) {
*left = SkMax32(fLeft, runs[0]);
}
if (right) {
*right = SkMin32(fRight, runs[1]);
}
fRuns = runs + 2;
return true;
}
///////////////////////////////////////////////////////////////////////////////
#ifdef SK_DEBUG
bool SkRegion::debugSetRuns(const RunType runs[], int count) {
// we need to make a copy, since the real method may modify the array, and
// so it cannot be const.
SkAutoTArray<RunType> storage(count);
memcpy(storage.get(), runs, count * sizeof(RunType));
return this->setRuns(storage.get(), count);
}
#endif