1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkRegion.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,1485 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2006 The Android Open Source Project
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +
1.12 +
1.13 +#include "SkRegionPriv.h"
1.14 +#include "SkTemplates.h"
1.15 +#include "SkThread.h"
1.16 +#include "SkUtils.h"
1.17 +
1.18 +/* Region Layout
1.19 + *
1.20 + * TOP
1.21 + *
1.22 + * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ]
1.23 + * ...
1.24 + *
1.25 + * Y-Sentinel
1.26 + */
1.27 +
1.28 +SkDEBUGCODE(int32_t gRgnAllocCounter;)
1.29 +
1.30 +/////////////////////////////////////////////////////////////////////////////////////////////////
1.31 +
1.32 +/* Pass in the beginning with the intervals.
1.33 + * We back up 1 to read the interval-count.
1.34 + * Return the beginning of the next scanline (i.e. the next Y-value)
1.35 + */
1.36 +static SkRegion::RunType* skip_intervals(const SkRegion::RunType runs[]) {
1.37 + int intervals = runs[-1];
1.38 +#ifdef SK_DEBUG
1.39 + if (intervals > 0) {
1.40 + SkASSERT(runs[0] < runs[1]);
1.41 + SkASSERT(runs[1] < SkRegion::kRunTypeSentinel);
1.42 + } else {
1.43 + SkASSERT(0 == intervals);
1.44 + SkASSERT(SkRegion::kRunTypeSentinel == runs[0]);
1.45 + }
1.46 +#endif
1.47 + runs += intervals * 2 + 1;
1.48 + return const_cast<SkRegion::RunType*>(runs);
1.49 +}
1.50 +
1.51 +bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count,
1.52 + SkIRect* bounds) {
1.53 + assert_sentinel(runs[0], false); // top
1.54 + SkASSERT(count >= kRectRegionRuns);
1.55 +
1.56 + if (count == kRectRegionRuns) {
1.57 + assert_sentinel(runs[1], false); // bottom
1.58 + SkASSERT(1 == runs[2]);
1.59 + assert_sentinel(runs[3], false); // left
1.60 + assert_sentinel(runs[4], false); // right
1.61 + assert_sentinel(runs[5], true);
1.62 + assert_sentinel(runs[6], true);
1.63 +
1.64 + SkASSERT(runs[0] < runs[1]); // valid height
1.65 + SkASSERT(runs[3] < runs[4]); // valid width
1.66 +
1.67 + bounds->set(runs[3], runs[0], runs[4], runs[1]);
1.68 + return true;
1.69 + }
1.70 + return false;
1.71 +}
1.72 +
1.73 +//////////////////////////////////////////////////////////////////////////
1.74 +
1.75 +SkRegion::SkRegion() {
1.76 + fBounds.set(0, 0, 0, 0);
1.77 + fRunHead = SkRegion_gEmptyRunHeadPtr;
1.78 +}
1.79 +
1.80 +SkRegion::SkRegion(const SkRegion& src) {
1.81 + fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
1.82 + this->setRegion(src);
1.83 +}
1.84 +
1.85 +SkRegion::SkRegion(const SkIRect& rect) {
1.86 + fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
1.87 + this->setRect(rect);
1.88 +}
1.89 +
1.90 +SkRegion::~SkRegion() {
1.91 + this->freeRuns();
1.92 +}
1.93 +
1.94 +void SkRegion::freeRuns() {
1.95 + if (this->isComplex()) {
1.96 + SkASSERT(fRunHead->fRefCnt >= 1);
1.97 + if (sk_atomic_dec(&fRunHead->fRefCnt) == 1) {
1.98 + //SkASSERT(gRgnAllocCounter > 0);
1.99 + //SkDEBUGCODE(sk_atomic_dec(&gRgnAllocCounter));
1.100 + //SkDEBUGF(("************** gRgnAllocCounter::free %d\n", gRgnAllocCounter));
1.101 + sk_free(fRunHead);
1.102 + }
1.103 + }
1.104 +}
1.105 +
1.106 +void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) {
1.107 + fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount);
1.108 +}
1.109 +
1.110 +void SkRegion::allocateRuns(int count) {
1.111 + fRunHead = RunHead::Alloc(count);
1.112 +}
1.113 +
1.114 +void SkRegion::allocateRuns(const RunHead& head) {
1.115 + fRunHead = RunHead::Alloc(head.fRunCount,
1.116 + head.getYSpanCount(),
1.117 + head.getIntervalCount());
1.118 +}
1.119 +
1.120 +SkRegion& SkRegion::operator=(const SkRegion& src) {
1.121 + (void)this->setRegion(src);
1.122 + return *this;
1.123 +}
1.124 +
1.125 +void SkRegion::swap(SkRegion& other) {
1.126 + SkTSwap<SkIRect>(fBounds, other.fBounds);
1.127 + SkTSwap<RunHead*>(fRunHead, other.fRunHead);
1.128 +}
1.129 +
1.130 +int SkRegion::computeRegionComplexity() const {
1.131 + if (this->isEmpty()) {
1.132 + return 0;
1.133 + } else if (this->isRect()) {
1.134 + return 1;
1.135 + }
1.136 + return fRunHead->getIntervalCount();
1.137 +}
1.138 +
1.139 +bool SkRegion::setEmpty() {
1.140 + this->freeRuns();
1.141 + fBounds.set(0, 0, 0, 0);
1.142 + fRunHead = SkRegion_gEmptyRunHeadPtr;
1.143 + return false;
1.144 +}
1.145 +
1.146 +bool SkRegion::setRect(int32_t left, int32_t top,
1.147 + int32_t right, int32_t bottom) {
1.148 + if (left >= right || top >= bottom) {
1.149 + return this->setEmpty();
1.150 + }
1.151 + this->freeRuns();
1.152 + fBounds.set(left, top, right, bottom);
1.153 + fRunHead = SkRegion_gRectRunHeadPtr;
1.154 + return true;
1.155 +}
1.156 +
1.157 +bool SkRegion::setRect(const SkIRect& r) {
1.158 + return this->setRect(r.fLeft, r.fTop, r.fRight, r.fBottom);
1.159 +}
1.160 +
1.161 +bool SkRegion::setRegion(const SkRegion& src) {
1.162 + if (this != &src) {
1.163 + this->freeRuns();
1.164 +
1.165 + fBounds = src.fBounds;
1.166 + fRunHead = src.fRunHead;
1.167 + if (this->isComplex()) {
1.168 + sk_atomic_inc(&fRunHead->fRefCnt);
1.169 + }
1.170 + }
1.171 + return fRunHead != SkRegion_gEmptyRunHeadPtr;
1.172 +}
1.173 +
1.174 +bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) {
1.175 + SkRegion tmp(rect);
1.176 +
1.177 + return this->op(tmp, rgn, op);
1.178 +}
1.179 +
1.180 +bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) {
1.181 + SkRegion tmp(rect);
1.182 +
1.183 + return this->op(rgn, tmp, op);
1.184 +}
1.185 +
1.186 +///////////////////////////////////////////////////////////////////////////////
1.187 +
1.188 +#ifdef SK_BUILD_FOR_ANDROID
1.189 +#include <stdio.h>
1.190 +char* SkRegion::toString() {
1.191 + Iterator iter(*this);
1.192 + int count = 0;
1.193 + while (!iter.done()) {
1.194 + count++;
1.195 + iter.next();
1.196 + }
1.197 + // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0'
1.198 + const int max = (count*((11*4)+5))+11+1;
1.199 + char* result = (char*)malloc(max);
1.200 + if (result == NULL) {
1.201 + return NULL;
1.202 + }
1.203 + count = sprintf(result, "SkRegion(");
1.204 + iter.reset(*this);
1.205 + while (!iter.done()) {
1.206 + const SkIRect& r = iter.rect();
1.207 + count += sprintf(result+count, "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom);
1.208 + iter.next();
1.209 + }
1.210 + count += sprintf(result+count, ")");
1.211 + return result;
1.212 +}
1.213 +#endif
1.214 +
1.215 +///////////////////////////////////////////////////////////////////////////////
1.216 +
1.217 +int SkRegion::count_runtype_values(int* itop, int* ibot) const {
1.218 + if (this == NULL) {
1.219 + *itop = SK_MinS32;
1.220 + *ibot = SK_MaxS32;
1.221 + return 0;
1.222 + }
1.223 +
1.224 + int maxT;
1.225 +
1.226 + if (this->isRect()) {
1.227 + maxT = 2;
1.228 + } else {
1.229 + SkASSERT(this->isComplex());
1.230 + maxT = fRunHead->getIntervalCount() * 2;
1.231 + }
1.232 + *itop = fBounds.fTop;
1.233 + *ibot = fBounds.fBottom;
1.234 + return maxT;
1.235 +}
1.236 +
1.237 +static bool isRunCountEmpty(int count) {
1.238 + return count <= 2;
1.239 +}
1.240 +
1.241 +bool SkRegion::setRuns(RunType runs[], int count) {
1.242 + SkDEBUGCODE(this->validate();)
1.243 + SkASSERT(count > 0);
1.244 +
1.245 + if (isRunCountEmpty(count)) {
1.246 + // SkDEBUGF(("setRuns: empty\n"));
1.247 + assert_sentinel(runs[count-1], true);
1.248 + return this->setEmpty();
1.249 + }
1.250 +
1.251 + // trim off any empty spans from the top and bottom
1.252 + // weird I should need this, perhaps op() could be smarter...
1.253 + if (count > kRectRegionRuns) {
1.254 + RunType* stop = runs + count;
1.255 + assert_sentinel(runs[0], false); // top
1.256 + assert_sentinel(runs[1], false); // bottom
1.257 + // runs[2] is uncomputed intervalCount
1.258 +
1.259 + if (runs[3] == SkRegion::kRunTypeSentinel) { // should be first left...
1.260 + runs += 3; // skip empty initial span
1.261 + runs[0] = runs[-2]; // set new top to prev bottom
1.262 + assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row
1.263 + assert_sentinel(runs[2], false); // intervalcount
1.264 + assert_sentinel(runs[3], false); // left
1.265 + assert_sentinel(runs[4], false); // right
1.266 + }
1.267 +
1.268 + assert_sentinel(stop[-1], true);
1.269 + assert_sentinel(stop[-2], true);
1.270 +
1.271 + // now check for a trailing empty span
1.272 + if (stop[-5] == SkRegion::kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs
1.273 + stop[-4] = SkRegion::kRunTypeSentinel; // kill empty last span
1.274 + stop -= 3;
1.275 + assert_sentinel(stop[-1], true); // last y-sentinel
1.276 + assert_sentinel(stop[-2], true); // last x-sentinel
1.277 + assert_sentinel(stop[-3], false); // last right
1.278 + assert_sentinel(stop[-4], false); // last left
1.279 + assert_sentinel(stop[-5], false); // last interval-count
1.280 + assert_sentinel(stop[-6], false); // last bottom
1.281 + }
1.282 + count = (int)(stop - runs);
1.283 + }
1.284 +
1.285 + SkASSERT(count >= kRectRegionRuns);
1.286 +
1.287 + if (SkRegion::RunsAreARect(runs, count, &fBounds)) {
1.288 + return this->setRect(fBounds);
1.289 + }
1.290 +
1.291 + // if we get here, we need to become a complex region
1.292 +
1.293 + if (!this->isComplex() || fRunHead->fRunCount != count) {
1.294 + this->freeRuns();
1.295 + this->allocateRuns(count);
1.296 + }
1.297 +
1.298 + // must call this before we can write directly into runs()
1.299 + // in case we are sharing the buffer with another region (copy on write)
1.300 + fRunHead = fRunHead->ensureWritable();
1.301 + memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType));
1.302 + fRunHead->computeRunBounds(&fBounds);
1.303 +
1.304 + SkDEBUGCODE(this->validate();)
1.305 +
1.306 + return true;
1.307 +}
1.308 +
1.309 +void SkRegion::BuildRectRuns(const SkIRect& bounds,
1.310 + RunType runs[kRectRegionRuns]) {
1.311 + runs[0] = bounds.fTop;
1.312 + runs[1] = bounds.fBottom;
1.313 + runs[2] = 1; // 1 interval for this scanline
1.314 + runs[3] = bounds.fLeft;
1.315 + runs[4] = bounds.fRight;
1.316 + runs[5] = kRunTypeSentinel;
1.317 + runs[6] = kRunTypeSentinel;
1.318 +}
1.319 +
1.320 +bool SkRegion::contains(int32_t x, int32_t y) const {
1.321 + SkDEBUGCODE(this->validate();)
1.322 +
1.323 + if (!fBounds.contains(x, y)) {
1.324 + return false;
1.325 + }
1.326 + if (this->isRect()) {
1.327 + return true;
1.328 + }
1.329 + SkASSERT(this->isComplex());
1.330 +
1.331 + const RunType* runs = fRunHead->findScanline(y);
1.332 +
1.333 + // Skip the Bottom and IntervalCount
1.334 + runs += 2;
1.335 +
1.336 + // Just walk this scanline, checking each interval. The X-sentinel will
1.337 + // appear as a left-inteval (runs[0]) and should abort the search.
1.338 + //
1.339 + // We could do a bsearch, using interval-count (runs[1]), but need to time
1.340 + // when that would be worthwhile.
1.341 + //
1.342 + for (;;) {
1.343 + if (x < runs[0]) {
1.344 + break;
1.345 + }
1.346 + if (x < runs[1]) {
1.347 + return true;
1.348 + }
1.349 + runs += 2;
1.350 + }
1.351 + return false;
1.352 +}
1.353 +
1.354 +static SkRegion::RunType scanline_bottom(const SkRegion::RunType runs[]) {
1.355 + return runs[0];
1.356 +}
1.357 +
1.358 +static const SkRegion::RunType* scanline_next(const SkRegion::RunType runs[]) {
1.359 + // skip [B N [L R]... S]
1.360 + return runs + 2 + runs[1] * 2 + 1;
1.361 +}
1.362 +
1.363 +static bool scanline_contains(const SkRegion::RunType runs[],
1.364 + SkRegion::RunType L, SkRegion::RunType R) {
1.365 + runs += 2; // skip Bottom and IntervalCount
1.366 + for (;;) {
1.367 + if (L < runs[0]) {
1.368 + break;
1.369 + }
1.370 + if (R <= runs[1]) {
1.371 + return true;
1.372 + }
1.373 + runs += 2;
1.374 + }
1.375 + return false;
1.376 +}
1.377 +
1.378 +bool SkRegion::contains(const SkIRect& r) const {
1.379 + SkDEBUGCODE(this->validate();)
1.380 +
1.381 + if (!fBounds.contains(r)) {
1.382 + return false;
1.383 + }
1.384 + if (this->isRect()) {
1.385 + return true;
1.386 + }
1.387 + SkASSERT(this->isComplex());
1.388 +
1.389 + const RunType* scanline = fRunHead->findScanline(r.fTop);
1.390 + for (;;) {
1.391 + if (!scanline_contains(scanline, r.fLeft, r.fRight)) {
1.392 + return false;
1.393 + }
1.394 + if (r.fBottom <= scanline_bottom(scanline)) {
1.395 + break;
1.396 + }
1.397 + scanline = scanline_next(scanline);
1.398 + }
1.399 + return true;
1.400 +}
1.401 +
1.402 +bool SkRegion::contains(const SkRegion& rgn) const {
1.403 + SkDEBUGCODE(this->validate();)
1.404 + SkDEBUGCODE(rgn.validate();)
1.405 +
1.406 + if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) {
1.407 + return false;
1.408 + }
1.409 + if (this->isRect()) {
1.410 + return true;
1.411 + }
1.412 + if (rgn.isRect()) {
1.413 + return this->contains(rgn.getBounds());
1.414 + }
1.415 +
1.416 + /*
1.417 + * A contains B is equivalent to
1.418 + * B - A == 0
1.419 + */
1.420 + return !Oper(rgn, *this, kDifference_Op, NULL);
1.421 +}
1.422 +
1.423 +const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[],
1.424 + int* intervals) const {
1.425 + SkASSERT(tmpStorage && intervals);
1.426 + const RunType* runs = tmpStorage;
1.427 +
1.428 + if (this->isEmpty()) {
1.429 + tmpStorage[0] = kRunTypeSentinel;
1.430 + *intervals = 0;
1.431 + } else if (this->isRect()) {
1.432 + BuildRectRuns(fBounds, tmpStorage);
1.433 + *intervals = 1;
1.434 + } else {
1.435 + runs = fRunHead->readonly_runs();
1.436 + *intervals = fRunHead->getIntervalCount();
1.437 + }
1.438 + return runs;
1.439 +}
1.440 +
1.441 +///////////////////////////////////////////////////////////////////////////////
1.442 +
1.443 +static bool scanline_intersects(const SkRegion::RunType runs[],
1.444 + SkRegion::RunType L, SkRegion::RunType R) {
1.445 + runs += 2; // skip Bottom and IntervalCount
1.446 + for (;;) {
1.447 + if (R <= runs[0]) {
1.448 + break;
1.449 + }
1.450 + if (L < runs[1]) {
1.451 + return true;
1.452 + }
1.453 + runs += 2;
1.454 + }
1.455 + return false;
1.456 +}
1.457 +
1.458 +bool SkRegion::intersects(const SkIRect& r) const {
1.459 + SkDEBUGCODE(this->validate();)
1.460 +
1.461 + if (this->isEmpty() || r.isEmpty()) {
1.462 + return false;
1.463 + }
1.464 +
1.465 + SkIRect sect;
1.466 + if (!sect.intersect(fBounds, r)) {
1.467 + return false;
1.468 + }
1.469 + if (this->isRect()) {
1.470 + return true;
1.471 + }
1.472 + SkASSERT(this->isComplex());
1.473 +
1.474 + const RunType* scanline = fRunHead->findScanline(sect.fTop);
1.475 + for (;;) {
1.476 + if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) {
1.477 + return true;
1.478 + }
1.479 + if (sect.fBottom <= scanline_bottom(scanline)) {
1.480 + break;
1.481 + }
1.482 + scanline = scanline_next(scanline);
1.483 + }
1.484 + return false;
1.485 +}
1.486 +
1.487 +bool SkRegion::intersects(const SkRegion& rgn) const {
1.488 + if (this->isEmpty() || rgn.isEmpty()) {
1.489 + return false;
1.490 + }
1.491 +
1.492 + if (!SkIRect::Intersects(fBounds, rgn.fBounds)) {
1.493 + return false;
1.494 + }
1.495 +
1.496 + bool weAreARect = this->isRect();
1.497 + bool theyAreARect = rgn.isRect();
1.498 +
1.499 + if (weAreARect && theyAreARect) {
1.500 + return true;
1.501 + }
1.502 + if (weAreARect) {
1.503 + return rgn.intersects(this->getBounds());
1.504 + }
1.505 + if (theyAreARect) {
1.506 + return this->intersects(rgn.getBounds());
1.507 + }
1.508 +
1.509 + // both of us are complex
1.510 + return Oper(*this, rgn, kIntersect_Op, NULL);
1.511 +}
1.512 +
1.513 +///////////////////////////////////////////////////////////////////////////////
1.514 +
1.515 +bool SkRegion::operator==(const SkRegion& b) const {
1.516 + SkDEBUGCODE(validate();)
1.517 + SkDEBUGCODE(b.validate();)
1.518 +
1.519 + if (this == &b) {
1.520 + return true;
1.521 + }
1.522 + if (fBounds != b.fBounds) {
1.523 + return false;
1.524 + }
1.525 +
1.526 + const SkRegion::RunHead* ah = fRunHead;
1.527 + const SkRegion::RunHead* bh = b.fRunHead;
1.528 +
1.529 + // this catches empties and rects being equal
1.530 + if (ah == bh) {
1.531 + return true;
1.532 + }
1.533 + // now we insist that both are complex (but different ptrs)
1.534 + if (!this->isComplex() || !b.isComplex()) {
1.535 + return false;
1.536 + }
1.537 + return ah->fRunCount == bh->fRunCount &&
1.538 + !memcmp(ah->readonly_runs(), bh->readonly_runs(),
1.539 + ah->fRunCount * sizeof(SkRegion::RunType));
1.540 +}
1.541 +
1.542 +void SkRegion::translate(int dx, int dy, SkRegion* dst) const {
1.543 + SkDEBUGCODE(this->validate();)
1.544 +
1.545 + if (NULL == dst) {
1.546 + return;
1.547 + }
1.548 + if (this->isEmpty()) {
1.549 + dst->setEmpty();
1.550 + } else if (this->isRect()) {
1.551 + dst->setRect(fBounds.fLeft + dx, fBounds.fTop + dy,
1.552 + fBounds.fRight + dx, fBounds.fBottom + dy);
1.553 + } else {
1.554 + if (this == dst) {
1.555 + dst->fRunHead = dst->fRunHead->ensureWritable();
1.556 + } else {
1.557 + SkRegion tmp;
1.558 + tmp.allocateRuns(*fRunHead);
1.559 + tmp.fBounds = fBounds;
1.560 + dst->swap(tmp);
1.561 + }
1.562 +
1.563 + dst->fBounds.offset(dx, dy);
1.564 +
1.565 + const RunType* sruns = fRunHead->readonly_runs();
1.566 + RunType* druns = dst->fRunHead->writable_runs();
1.567 +
1.568 + *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top
1.569 + for (;;) {
1.570 + int bottom = *sruns++;
1.571 + if (bottom == kRunTypeSentinel) {
1.572 + break;
1.573 + }
1.574 + *druns++ = (SkRegion::RunType)(bottom + dy); // bottom;
1.575 + *druns++ = *sruns++; // copy intervalCount;
1.576 + for (;;) {
1.577 + int x = *sruns++;
1.578 + if (x == kRunTypeSentinel) {
1.579 + break;
1.580 + }
1.581 + *druns++ = (SkRegion::RunType)(x + dx);
1.582 + *druns++ = (SkRegion::RunType)(*sruns++ + dx);
1.583 + }
1.584 + *druns++ = kRunTypeSentinel; // x sentinel
1.585 + }
1.586 + *druns++ = kRunTypeSentinel; // y sentinel
1.587 +
1.588 + SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount);
1.589 + SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount);
1.590 + }
1.591 +
1.592 + SkDEBUGCODE(this->validate();)
1.593 +}
1.594 +
1.595 +///////////////////////////////////////////////////////////////////////////////
1.596 +
1.597 +bool SkRegion::setRects(const SkIRect rects[], int count) {
1.598 + if (0 == count) {
1.599 + this->setEmpty();
1.600 + } else {
1.601 + this->setRect(rects[0]);
1.602 + for (int i = 1; i < count; i++) {
1.603 + this->op(rects[i], kUnion_Op);
1.604 + }
1.605 + }
1.606 + return !this->isEmpty();
1.607 +}
1.608 +
1.609 +///////////////////////////////////////////////////////////////////////////////
1.610 +
1.611 +#if defined _WIN32 && _MSC_VER >= 1300 // disable warning : local variable used without having been initialized
1.612 +#pragma warning ( push )
1.613 +#pragma warning ( disable : 4701 )
1.614 +#endif
1.615 +
1.616 +#ifdef SK_DEBUG
1.617 +static void assert_valid_pair(int left, int rite)
1.618 +{
1.619 + SkASSERT(left == SkRegion::kRunTypeSentinel || left < rite);
1.620 +}
1.621 +#else
1.622 + #define assert_valid_pair(left, rite)
1.623 +#endif
1.624 +
1.625 +struct spanRec {
1.626 + const SkRegion::RunType* fA_runs;
1.627 + const SkRegion::RunType* fB_runs;
1.628 + int fA_left, fA_rite, fB_left, fB_rite;
1.629 + int fLeft, fRite, fInside;
1.630 +
1.631 + void init(const SkRegion::RunType a_runs[],
1.632 + const SkRegion::RunType b_runs[]) {
1.633 + fA_left = *a_runs++;
1.634 + fA_rite = *a_runs++;
1.635 + fB_left = *b_runs++;
1.636 + fB_rite = *b_runs++;
1.637 +
1.638 + fA_runs = a_runs;
1.639 + fB_runs = b_runs;
1.640 + }
1.641 +
1.642 + bool done() const {
1.643 + SkASSERT(fA_left <= SkRegion::kRunTypeSentinel);
1.644 + SkASSERT(fB_left <= SkRegion::kRunTypeSentinel);
1.645 + return fA_left == SkRegion::kRunTypeSentinel &&
1.646 + fB_left == SkRegion::kRunTypeSentinel;
1.647 + }
1.648 +
1.649 + void next() {
1.650 + assert_valid_pair(fA_left, fA_rite);
1.651 + assert_valid_pair(fB_left, fB_rite);
1.652 +
1.653 + int inside, left, rite SK_INIT_TO_AVOID_WARNING;
1.654 + bool a_flush = false;
1.655 + bool b_flush = false;
1.656 +
1.657 + int a_left = fA_left;
1.658 + int a_rite = fA_rite;
1.659 + int b_left = fB_left;
1.660 + int b_rite = fB_rite;
1.661 +
1.662 + if (a_left < b_left) {
1.663 + inside = 1;
1.664 + left = a_left;
1.665 + if (a_rite <= b_left) { // [...] <...>
1.666 + rite = a_rite;
1.667 + a_flush = true;
1.668 + } else { // [...<..]...> or [...<...>...]
1.669 + rite = a_left = b_left;
1.670 + }
1.671 + } else if (b_left < a_left) {
1.672 + inside = 2;
1.673 + left = b_left;
1.674 + if (b_rite <= a_left) { // [...] <...>
1.675 + rite = b_rite;
1.676 + b_flush = true;
1.677 + } else { // [...<..]...> or [...<...>...]
1.678 + rite = b_left = a_left;
1.679 + }
1.680 + } else { // a_left == b_left
1.681 + inside = 3;
1.682 + left = a_left; // or b_left
1.683 + if (a_rite <= b_rite) {
1.684 + rite = b_left = a_rite;
1.685 + a_flush = true;
1.686 + }
1.687 + if (b_rite <= a_rite) {
1.688 + rite = a_left = b_rite;
1.689 + b_flush = true;
1.690 + }
1.691 + }
1.692 +
1.693 + if (a_flush) {
1.694 + a_left = *fA_runs++;
1.695 + a_rite = *fA_runs++;
1.696 + }
1.697 + if (b_flush) {
1.698 + b_left = *fB_runs++;
1.699 + b_rite = *fB_runs++;
1.700 + }
1.701 +
1.702 + SkASSERT(left <= rite);
1.703 +
1.704 + // now update our state
1.705 + fA_left = a_left;
1.706 + fA_rite = a_rite;
1.707 + fB_left = b_left;
1.708 + fB_rite = b_rite;
1.709 +
1.710 + fLeft = left;
1.711 + fRite = rite;
1.712 + fInside = inside;
1.713 + }
1.714 +};
1.715 +
1.716 +static SkRegion::RunType* operate_on_span(const SkRegion::RunType a_runs[],
1.717 + const SkRegion::RunType b_runs[],
1.718 + SkRegion::RunType dst[],
1.719 + int min, int max) {
1.720 + spanRec rec;
1.721 + bool firstInterval = true;
1.722 +
1.723 + rec.init(a_runs, b_runs);
1.724 +
1.725 + while (!rec.done()) {
1.726 + rec.next();
1.727 +
1.728 + int left = rec.fLeft;
1.729 + int rite = rec.fRite;
1.730 +
1.731 + // add left,rite to our dst buffer (checking for coincidence
1.732 + if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) &&
1.733 + left < rite) { // skip if equal
1.734 + if (firstInterval || dst[-1] < left) {
1.735 + *dst++ = (SkRegion::RunType)(left);
1.736 + *dst++ = (SkRegion::RunType)(rite);
1.737 + firstInterval = false;
1.738 + } else {
1.739 + // update the right edge
1.740 + dst[-1] = (SkRegion::RunType)(rite);
1.741 + }
1.742 + }
1.743 + }
1.744 +
1.745 + *dst++ = SkRegion::kRunTypeSentinel;
1.746 + return dst;
1.747 +}
1.748 +
1.749 +#if defined _WIN32 && _MSC_VER >= 1300
1.750 +#pragma warning ( pop )
1.751 +#endif
1.752 +
1.753 +static const struct {
1.754 + uint8_t fMin;
1.755 + uint8_t fMax;
1.756 +} gOpMinMax[] = {
1.757 + { 1, 1 }, // Difference
1.758 + { 3, 3 }, // Intersection
1.759 + { 1, 3 }, // Union
1.760 + { 1, 2 } // XOR
1.761 +};
1.762 +
1.763 +class RgnOper {
1.764 +public:
1.765 + RgnOper(int top, SkRegion::RunType dst[], SkRegion::Op op) {
1.766 + // need to ensure that the op enum lines up with our minmax array
1.767 + SkASSERT(SkRegion::kDifference_Op == 0);
1.768 + SkASSERT(SkRegion::kIntersect_Op == 1);
1.769 + SkASSERT(SkRegion::kUnion_Op == 2);
1.770 + SkASSERT(SkRegion::kXOR_Op == 3);
1.771 + SkASSERT((unsigned)op <= 3);
1.772 +
1.773 + fStartDst = dst;
1.774 + fPrevDst = dst + 1;
1.775 + fPrevLen = 0; // will never match a length from operate_on_span
1.776 + fTop = (SkRegion::RunType)(top); // just a first guess, we might update this
1.777 +
1.778 + fMin = gOpMinMax[op].fMin;
1.779 + fMax = gOpMinMax[op].fMax;
1.780 + }
1.781 +
1.782 + void addSpan(int bottom, const SkRegion::RunType a_runs[],
1.783 + const SkRegion::RunType b_runs[]) {
1.784 + // skip X values and slots for the next Y+intervalCount
1.785 + SkRegion::RunType* start = fPrevDst + fPrevLen + 2;
1.786 + // start points to beginning of dst interval
1.787 + SkRegion::RunType* stop = operate_on_span(a_runs, b_runs, start, fMin, fMax);
1.788 + size_t len = stop - start;
1.789 + SkASSERT(len >= 1 && (len & 1) == 1);
1.790 + SkASSERT(SkRegion::kRunTypeSentinel == stop[-1]);
1.791 +
1.792 + if (fPrevLen == len &&
1.793 + (1 == len || !memcmp(fPrevDst, start,
1.794 + (len - 1) * sizeof(SkRegion::RunType)))) {
1.795 + // update Y value
1.796 + fPrevDst[-2] = (SkRegion::RunType)(bottom);
1.797 + } else { // accept the new span
1.798 + if (len == 1 && fPrevLen == 0) {
1.799 + fTop = (SkRegion::RunType)(bottom); // just update our bottom
1.800 + } else {
1.801 + start[-2] = (SkRegion::RunType)(bottom);
1.802 + start[-1] = len >> 1;
1.803 + fPrevDst = start;
1.804 + fPrevLen = len;
1.805 + }
1.806 + }
1.807 + }
1.808 +
1.809 + int flush() {
1.810 + fStartDst[0] = fTop;
1.811 + fPrevDst[fPrevLen] = SkRegion::kRunTypeSentinel;
1.812 + return (int)(fPrevDst - fStartDst + fPrevLen + 1);
1.813 + }
1.814 +
1.815 + bool isEmpty() const { return 0 == fPrevLen; }
1.816 +
1.817 + uint8_t fMin, fMax;
1.818 +
1.819 +private:
1.820 + SkRegion::RunType* fStartDst;
1.821 + SkRegion::RunType* fPrevDst;
1.822 + size_t fPrevLen;
1.823 + SkRegion::RunType fTop;
1.824 +};
1.825 +
1.826 +// want a unique value to signal that we exited due to quickExit
1.827 +#define QUICK_EXIT_TRUE_COUNT (-1)
1.828 +
1.829 +static int operate(const SkRegion::RunType a_runs[],
1.830 + const SkRegion::RunType b_runs[],
1.831 + SkRegion::RunType dst[],
1.832 + SkRegion::Op op,
1.833 + bool quickExit) {
1.834 + const SkRegion::RunType gEmptyScanline[] = {
1.835 + 0, // dummy bottom value
1.836 + 0, // zero intervals
1.837 + SkRegion::kRunTypeSentinel,
1.838 + // just need a 2nd value, since spanRec.init() reads 2 values, even
1.839 + // though if the first value is the sentinel, it ignores the 2nd value.
1.840 + // w/o the 2nd value here, we might read uninitialized memory.
1.841 + // This happens when we are using gSentinel, which is pointing at
1.842 + // our sentinel value.
1.843 + 0
1.844 + };
1.845 + const SkRegion::RunType* const gSentinel = &gEmptyScanline[2];
1.846 +
1.847 + int a_top = *a_runs++;
1.848 + int a_bot = *a_runs++;
1.849 + int b_top = *b_runs++;
1.850 + int b_bot = *b_runs++;
1.851 +
1.852 + a_runs += 1; // skip the intervalCount;
1.853 + b_runs += 1; // skip the intervalCount;
1.854 +
1.855 + // Now a_runs and b_runs to their intervals (or sentinel)
1.856 +
1.857 + assert_sentinel(a_top, false);
1.858 + assert_sentinel(a_bot, false);
1.859 + assert_sentinel(b_top, false);
1.860 + assert_sentinel(b_bot, false);
1.861 +
1.862 + RgnOper oper(SkMin32(a_top, b_top), dst, op);
1.863 +
1.864 + int prevBot = SkRegion::kRunTypeSentinel; // so we fail the first test
1.865 +
1.866 + while (a_bot < SkRegion::kRunTypeSentinel ||
1.867 + b_bot < SkRegion::kRunTypeSentinel) {
1.868 + int top, bot SK_INIT_TO_AVOID_WARNING;
1.869 + const SkRegion::RunType* run0 = gSentinel;
1.870 + const SkRegion::RunType* run1 = gSentinel;
1.871 + bool a_flush = false;
1.872 + bool b_flush = false;
1.873 +
1.874 + if (a_top < b_top) {
1.875 + top = a_top;
1.876 + run0 = a_runs;
1.877 + if (a_bot <= b_top) { // [...] <...>
1.878 + bot = a_bot;
1.879 + a_flush = true;
1.880 + } else { // [...<..]...> or [...<...>...]
1.881 + bot = a_top = b_top;
1.882 + }
1.883 + } else if (b_top < a_top) {
1.884 + top = b_top;
1.885 + run1 = b_runs;
1.886 + if (b_bot <= a_top) { // [...] <...>
1.887 + bot = b_bot;
1.888 + b_flush = true;
1.889 + } else { // [...<..]...> or [...<...>...]
1.890 + bot = b_top = a_top;
1.891 + }
1.892 + } else { // a_top == b_top
1.893 + top = a_top; // or b_top
1.894 + run0 = a_runs;
1.895 + run1 = b_runs;
1.896 + if (a_bot <= b_bot) {
1.897 + bot = b_top = a_bot;
1.898 + a_flush = true;
1.899 + }
1.900 + if (b_bot <= a_bot) {
1.901 + bot = a_top = b_bot;
1.902 + b_flush = true;
1.903 + }
1.904 + }
1.905 +
1.906 + if (top > prevBot) {
1.907 + oper.addSpan(top, gSentinel, gSentinel);
1.908 + }
1.909 + oper.addSpan(bot, run0, run1);
1.910 +
1.911 + if (quickExit && !oper.isEmpty()) {
1.912 + return QUICK_EXIT_TRUE_COUNT;
1.913 + }
1.914 +
1.915 + if (a_flush) {
1.916 + a_runs = skip_intervals(a_runs);
1.917 + a_top = a_bot;
1.918 + a_bot = *a_runs++;
1.919 + a_runs += 1; // skip uninitialized intervalCount
1.920 + if (a_bot == SkRegion::kRunTypeSentinel) {
1.921 + a_top = a_bot;
1.922 + }
1.923 + }
1.924 + if (b_flush) {
1.925 + b_runs = skip_intervals(b_runs);
1.926 + b_top = b_bot;
1.927 + b_bot = *b_runs++;
1.928 + b_runs += 1; // skip uninitialized intervalCount
1.929 + if (b_bot == SkRegion::kRunTypeSentinel) {
1.930 + b_top = b_bot;
1.931 + }
1.932 + }
1.933 +
1.934 + prevBot = bot;
1.935 + }
1.936 + return oper.flush();
1.937 +}
1.938 +
1.939 +///////////////////////////////////////////////////////////////////////////////
1.940 +
1.941 +/* Given count RunTypes in a complex region, return the worst case number of
1.942 + logical intervals that represents (i.e. number of rects that would be
1.943 + returned from the iterator).
1.944 +
1.945 + We could just return count/2, since there must be at least 2 values per
1.946 + interval, but we can first trim off the const overhead of the initial TOP
1.947 + value, plus the final BOTTOM + 2 sentinels.
1.948 + */
1.949 +#if 0 // UNUSED
1.950 +static int count_to_intervals(int count) {
1.951 + SkASSERT(count >= 6); // a single rect is 6 values
1.952 + return (count - 4) >> 1;
1.953 +}
1.954 +#endif
1.955 +
1.956 +/* Given a number of intervals, what is the worst case representation of that
1.957 + many intervals?
1.958 +
1.959 + Worst case (from a storage perspective), is a vertical stack of single
1.960 + intervals: TOP + N * (BOTTOM INTERVALCOUNT LEFT RIGHT SENTINEL) + SENTINEL
1.961 + */
1.962 +static int intervals_to_count(int intervals) {
1.963 + return 1 + intervals * 5 + 1;
1.964 +}
1.965 +
1.966 +/* Given the intervalCounts of RunTypes in two regions, return the worst-case number
1.967 + of RunTypes need to store the result after a region-op.
1.968 + */
1.969 +static int compute_worst_case_count(int a_intervals, int b_intervals) {
1.970 + // Our heuristic worst case is ai * (bi + 1) + bi * (ai + 1)
1.971 + int intervals = 2 * a_intervals * b_intervals + a_intervals + b_intervals;
1.972 + // convert back to number of RunType values
1.973 + return intervals_to_count(intervals);
1.974 +}
1.975 +
1.976 +static bool setEmptyCheck(SkRegion* result) {
1.977 + return result ? result->setEmpty() : false;
1.978 +}
1.979 +
1.980 +static bool setRectCheck(SkRegion* result, const SkIRect& rect) {
1.981 + return result ? result->setRect(rect) : !rect.isEmpty();
1.982 +}
1.983 +
1.984 +static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) {
1.985 + return result ? result->setRegion(rgn) : !rgn.isEmpty();
1.986 +}
1.987 +
1.988 +bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op,
1.989 + SkRegion* result) {
1.990 + SkASSERT((unsigned)op < kOpCount);
1.991 +
1.992 + if (kReplace_Op == op) {
1.993 + return setRegionCheck(result, rgnbOrig);
1.994 + }
1.995 +
1.996 + // swith to using pointers, so we can swap them as needed
1.997 + const SkRegion* rgna = &rgnaOrig;
1.998 + const SkRegion* rgnb = &rgnbOrig;
1.999 + // after this point, do not refer to rgnaOrig or rgnbOrig!!!
1.1000 +
1.1001 + // collaps difference and reverse-difference into just difference
1.1002 + if (kReverseDifference_Op == op) {
1.1003 + SkTSwap<const SkRegion*>(rgna, rgnb);
1.1004 + op = kDifference_Op;
1.1005 + }
1.1006 +
1.1007 + SkIRect bounds;
1.1008 + bool a_empty = rgna->isEmpty();
1.1009 + bool b_empty = rgnb->isEmpty();
1.1010 + bool a_rect = rgna->isRect();
1.1011 + bool b_rect = rgnb->isRect();
1.1012 +
1.1013 + switch (op) {
1.1014 + case kDifference_Op:
1.1015 + if (a_empty) {
1.1016 + return setEmptyCheck(result);
1.1017 + }
1.1018 + if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds,
1.1019 + rgnb->fBounds)) {
1.1020 + return setRegionCheck(result, *rgna);
1.1021 + }
1.1022 + if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) {
1.1023 + return setEmptyCheck(result);
1.1024 + }
1.1025 + break;
1.1026 +
1.1027 + case kIntersect_Op:
1.1028 + if ((a_empty | b_empty)
1.1029 + || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) {
1.1030 + return setEmptyCheck(result);
1.1031 + }
1.1032 + if (a_rect & b_rect) {
1.1033 + return setRectCheck(result, bounds);
1.1034 + }
1.1035 + if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
1.1036 + return setRegionCheck(result, *rgnb);
1.1037 + }
1.1038 + if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
1.1039 + return setRegionCheck(result, *rgna);
1.1040 + }
1.1041 + break;
1.1042 +
1.1043 + case kUnion_Op:
1.1044 + if (a_empty) {
1.1045 + return setRegionCheck(result, *rgnb);
1.1046 + }
1.1047 + if (b_empty) {
1.1048 + return setRegionCheck(result, *rgna);
1.1049 + }
1.1050 + if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
1.1051 + return setRegionCheck(result, *rgna);
1.1052 + }
1.1053 + if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
1.1054 + return setRegionCheck(result, *rgnb);
1.1055 + }
1.1056 + break;
1.1057 +
1.1058 + case kXOR_Op:
1.1059 + if (a_empty) {
1.1060 + return setRegionCheck(result, *rgnb);
1.1061 + }
1.1062 + if (b_empty) {
1.1063 + return setRegionCheck(result, *rgna);
1.1064 + }
1.1065 + break;
1.1066 + default:
1.1067 + SkDEBUGFAIL("unknown region op");
1.1068 + return false;
1.1069 + }
1.1070 +
1.1071 + RunType tmpA[kRectRegionRuns];
1.1072 + RunType tmpB[kRectRegionRuns];
1.1073 +
1.1074 + int a_intervals, b_intervals;
1.1075 + const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals);
1.1076 + const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals);
1.1077 +
1.1078 + int dstCount = compute_worst_case_count(a_intervals, b_intervals);
1.1079 + SkAutoSTMalloc<256, RunType> array(dstCount);
1.1080 +
1.1081 +#ifdef SK_DEBUG
1.1082 +// Sometimes helpful to seed everything with a known value when debugging
1.1083 +// sk_memset32((uint32_t*)array.get(), 0x7FFFFFFF, dstCount);
1.1084 +#endif
1.1085 +
1.1086 + int count = operate(a_runs, b_runs, array.get(), op, NULL == result);
1.1087 + SkASSERT(count <= dstCount);
1.1088 +
1.1089 + if (result) {
1.1090 + SkASSERT(count >= 0);
1.1091 + return result->setRuns(array.get(), count);
1.1092 + } else {
1.1093 + return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count);
1.1094 + }
1.1095 +}
1.1096 +
1.1097 +bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) {
1.1098 + SkDEBUGCODE(this->validate();)
1.1099 + return SkRegion::Oper(rgna, rgnb, op, this);
1.1100 +}
1.1101 +
1.1102 +///////////////////////////////////////////////////////////////////////////////
1.1103 +
1.1104 +#include "SkBuffer.h"
1.1105 +
1.1106 +size_t SkRegion::writeToMemory(void* storage) const {
1.1107 + if (NULL == storage) {
1.1108 + size_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount
1.1109 + if (!this->isEmpty()) {
1.1110 + size += sizeof(fBounds);
1.1111 + if (this->isComplex()) {
1.1112 + size += 2 * sizeof(int32_t); // ySpanCount + intervalCount
1.1113 + size += fRunHead->fRunCount * sizeof(RunType);
1.1114 + }
1.1115 + }
1.1116 + return size;
1.1117 + }
1.1118 +
1.1119 + SkWBuffer buffer(storage);
1.1120 +
1.1121 + if (this->isEmpty()) {
1.1122 + buffer.write32(-1);
1.1123 + } else {
1.1124 + bool isRect = this->isRect();
1.1125 +
1.1126 + buffer.write32(isRect ? 0 : fRunHead->fRunCount);
1.1127 + buffer.write(&fBounds, sizeof(fBounds));
1.1128 +
1.1129 + if (!isRect) {
1.1130 + buffer.write32(fRunHead->getYSpanCount());
1.1131 + buffer.write32(fRunHead->getIntervalCount());
1.1132 + buffer.write(fRunHead->readonly_runs(),
1.1133 + fRunHead->fRunCount * sizeof(RunType));
1.1134 + }
1.1135 + }
1.1136 + return buffer.pos();
1.1137 +}
1.1138 +
1.1139 +size_t SkRegion::readFromMemory(const void* storage, size_t length) {
1.1140 + SkRBufferWithSizeCheck buffer(storage, length);
1.1141 + SkRegion tmp;
1.1142 + int32_t count;
1.1143 +
1.1144 + if (buffer.readS32(&count) && (count >= 0) && buffer.read(&tmp.fBounds, sizeof(tmp.fBounds))) {
1.1145 + if (count == 0) {
1.1146 + tmp.fRunHead = SkRegion_gRectRunHeadPtr;
1.1147 + } else {
1.1148 + int32_t ySpanCount, intervalCount;
1.1149 + if (buffer.readS32(&ySpanCount) && buffer.readS32(&intervalCount)) {
1.1150 + tmp.allocateRuns(count, ySpanCount, intervalCount);
1.1151 + buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(RunType));
1.1152 + }
1.1153 + }
1.1154 + }
1.1155 + size_t sizeRead = 0;
1.1156 + if (buffer.isValid()) {
1.1157 + this->swap(tmp);
1.1158 + sizeRead = buffer.pos();
1.1159 + }
1.1160 + return sizeRead;
1.1161 +}
1.1162 +
1.1163 +///////////////////////////////////////////////////////////////////////////////
1.1164 +
1.1165 +const SkRegion& SkRegion::GetEmptyRegion() {
1.1166 + static SkRegion gEmpty;
1.1167 + return gEmpty;
1.1168 +}
1.1169 +
1.1170 +///////////////////////////////////////////////////////////////////////////////
1.1171 +
1.1172 +#ifdef SK_DEBUG
1.1173 +
1.1174 +// Starts with first X-interval, and returns a ptr to the X-sentinel
1.1175 +static const SkRegion::RunType* skip_intervals_slow(const SkRegion::RunType runs[]) {
1.1176 + // want to track that our intevals are all disjoint, such that
1.1177 + // prev-right < next-left. We rely on this optimization in places such as
1.1178 + // contains().
1.1179 + //
1.1180 + SkRegion::RunType prevR = -SkRegion::kRunTypeSentinel;
1.1181 +
1.1182 + while (runs[0] < SkRegion::kRunTypeSentinel) {
1.1183 + SkASSERT(prevR < runs[0]);
1.1184 + SkASSERT(runs[0] < runs[1]);
1.1185 + SkASSERT(runs[1] < SkRegion::kRunTypeSentinel);
1.1186 + prevR = runs[1];
1.1187 + runs += 2;
1.1188 + }
1.1189 + return runs;
1.1190 +}
1.1191 +
1.1192 +static void compute_bounds(const SkRegion::RunType runs[],
1.1193 + SkIRect* bounds, int* ySpanCountPtr,
1.1194 + int* intervalCountPtr) {
1.1195 + assert_sentinel(runs[0], false); // top
1.1196 +
1.1197 + int left = SK_MaxS32;
1.1198 + int rite = SK_MinS32;
1.1199 + int bot;
1.1200 + int ySpanCount = 0;
1.1201 + int intervalCount = 0;
1.1202 +
1.1203 + bounds->fTop = *runs++;
1.1204 + do {
1.1205 + bot = *runs++;
1.1206 + SkASSERT(SkRegion::kRunTypeSentinel > bot);
1.1207 +
1.1208 + ySpanCount += 1;
1.1209 +
1.1210 + runs += 1; // skip intervalCount for now
1.1211 + if (*runs < SkRegion::kRunTypeSentinel) {
1.1212 + if (left > *runs) {
1.1213 + left = *runs;
1.1214 + }
1.1215 +
1.1216 + const SkRegion::RunType* prev = runs;
1.1217 + runs = skip_intervals_slow(runs);
1.1218 + int intervals = (runs - prev) >> 1;
1.1219 + SkASSERT(prev[-1] == intervals);
1.1220 + intervalCount += intervals;
1.1221 +
1.1222 + if (rite < runs[-1]) {
1.1223 + rite = runs[-1];
1.1224 + }
1.1225 + } else {
1.1226 + SkASSERT(0 == runs[-1]); // no intervals
1.1227 + }
1.1228 + SkASSERT(SkRegion::kRunTypeSentinel == *runs);
1.1229 + runs += 1;
1.1230 + } while (SkRegion::kRunTypeSentinel != *runs);
1.1231 +
1.1232 + bounds->fLeft = left;
1.1233 + bounds->fRight = rite;
1.1234 + bounds->fBottom = bot;
1.1235 + *ySpanCountPtr = ySpanCount;
1.1236 + *intervalCountPtr = intervalCount;
1.1237 +}
1.1238 +
1.1239 +void SkRegion::validate() const {
1.1240 + if (this->isEmpty()) {
1.1241 + // check for explicit empty (the zero rect), so we can compare rects to know when
1.1242 + // two regions are equal (i.e. emptyRectA == emptyRectB)
1.1243 + // this is stricter than just asserting fBounds.isEmpty()
1.1244 + SkASSERT(fBounds.fLeft == 0 && fBounds.fTop == 0 && fBounds.fRight == 0 && fBounds.fBottom == 0);
1.1245 + } else {
1.1246 + SkASSERT(!fBounds.isEmpty());
1.1247 + if (!this->isRect()) {
1.1248 + SkASSERT(fRunHead->fRefCnt >= 1);
1.1249 + SkASSERT(fRunHead->fRunCount > kRectRegionRuns);
1.1250 +
1.1251 + const RunType* run = fRunHead->readonly_runs();
1.1252 +
1.1253 + // check that our bounds match our runs
1.1254 + {
1.1255 + SkIRect bounds;
1.1256 + int ySpanCount, intervalCount;
1.1257 + compute_bounds(run, &bounds, &ySpanCount, &intervalCount);
1.1258 +
1.1259 + SkASSERT(bounds == fBounds);
1.1260 + SkASSERT(ySpanCount > 0);
1.1261 + SkASSERT(fRunHead->getYSpanCount() == ySpanCount);
1.1262 + // SkASSERT(intervalCount > 1);
1.1263 + SkASSERT(fRunHead->getIntervalCount() == intervalCount);
1.1264 + }
1.1265 + }
1.1266 + }
1.1267 +}
1.1268 +
1.1269 +void SkRegion::dump() const {
1.1270 + if (this->isEmpty()) {
1.1271 + SkDebugf(" rgn: empty\n");
1.1272 + } else {
1.1273 + SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
1.1274 + if (this->isComplex()) {
1.1275 + const RunType* runs = fRunHead->readonly_runs();
1.1276 + for (int i = 0; i < fRunHead->fRunCount; i++)
1.1277 + SkDebugf(" %d", runs[i]);
1.1278 + }
1.1279 + SkDebugf("\n");
1.1280 + }
1.1281 +}
1.1282 +
1.1283 +#endif
1.1284 +
1.1285 +///////////////////////////////////////////////////////////////////////////////
1.1286 +
1.1287 +SkRegion::Iterator::Iterator(const SkRegion& rgn) {
1.1288 + this->reset(rgn);
1.1289 +}
1.1290 +
1.1291 +bool SkRegion::Iterator::rewind() {
1.1292 + if (fRgn) {
1.1293 + this->reset(*fRgn);
1.1294 + return true;
1.1295 + }
1.1296 + return false;
1.1297 +}
1.1298 +
1.1299 +void SkRegion::Iterator::reset(const SkRegion& rgn) {
1.1300 + fRgn = &rgn;
1.1301 + if (rgn.isEmpty()) {
1.1302 + fDone = true;
1.1303 + } else {
1.1304 + fDone = false;
1.1305 + if (rgn.isRect()) {
1.1306 + fRect = rgn.fBounds;
1.1307 + fRuns = NULL;
1.1308 + } else {
1.1309 + fRuns = rgn.fRunHead->readonly_runs();
1.1310 + fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]);
1.1311 + fRuns += 5;
1.1312 + // Now fRuns points to the 2nd interval (or x-sentinel)
1.1313 + }
1.1314 + }
1.1315 +}
1.1316 +
1.1317 +void SkRegion::Iterator::next() {
1.1318 + if (fDone) {
1.1319 + return;
1.1320 + }
1.1321 +
1.1322 + if (fRuns == NULL) { // rect case
1.1323 + fDone = true;
1.1324 + return;
1.1325 + }
1.1326 +
1.1327 + const RunType* runs = fRuns;
1.1328 +
1.1329 + if (runs[0] < kRunTypeSentinel) { // valid X value
1.1330 + fRect.fLeft = runs[0];
1.1331 + fRect.fRight = runs[1];
1.1332 + runs += 2;
1.1333 + } else { // we're at the end of a line
1.1334 + runs += 1;
1.1335 + if (runs[0] < kRunTypeSentinel) { // valid Y value
1.1336 + int intervals = runs[1];
1.1337 + if (0 == intervals) { // empty line
1.1338 + fRect.fTop = runs[0];
1.1339 + runs += 3;
1.1340 + } else {
1.1341 + fRect.fTop = fRect.fBottom;
1.1342 + }
1.1343 +
1.1344 + fRect.fBottom = runs[0];
1.1345 + assert_sentinel(runs[2], false);
1.1346 + assert_sentinel(runs[3], false);
1.1347 + fRect.fLeft = runs[2];
1.1348 + fRect.fRight = runs[3];
1.1349 + runs += 4;
1.1350 + } else { // end of rgn
1.1351 + fDone = true;
1.1352 + }
1.1353 + }
1.1354 + fRuns = runs;
1.1355 +}
1.1356 +
1.1357 +SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip)
1.1358 + : fIter(rgn), fClip(clip), fDone(true) {
1.1359 + const SkIRect& r = fIter.rect();
1.1360 +
1.1361 + while (!fIter.done()) {
1.1362 + if (r.fTop >= clip.fBottom) {
1.1363 + break;
1.1364 + }
1.1365 + if (fRect.intersect(clip, r)) {
1.1366 + fDone = false;
1.1367 + break;
1.1368 + }
1.1369 + fIter.next();
1.1370 + }
1.1371 +}
1.1372 +
1.1373 +void SkRegion::Cliperator::next() {
1.1374 + if (fDone) {
1.1375 + return;
1.1376 + }
1.1377 +
1.1378 + const SkIRect& r = fIter.rect();
1.1379 +
1.1380 + fDone = true;
1.1381 + fIter.next();
1.1382 + while (!fIter.done()) {
1.1383 + if (r.fTop >= fClip.fBottom) {
1.1384 + break;
1.1385 + }
1.1386 + if (fRect.intersect(fClip, r)) {
1.1387 + fDone = false;
1.1388 + break;
1.1389 + }
1.1390 + fIter.next();
1.1391 + }
1.1392 +}
1.1393 +
1.1394 +///////////////////////////////////////////////////////////////////////////////
1.1395 +
1.1396 +SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left,
1.1397 + int right) {
1.1398 + SkDEBUGCODE(rgn.validate();)
1.1399 +
1.1400 + const SkIRect& r = rgn.getBounds();
1.1401 +
1.1402 + fDone = true;
1.1403 + if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom &&
1.1404 + right > r.fLeft && left < r.fRight) {
1.1405 + if (rgn.isRect()) {
1.1406 + if (left < r.fLeft) {
1.1407 + left = r.fLeft;
1.1408 + }
1.1409 + if (right > r.fRight) {
1.1410 + right = r.fRight;
1.1411 + }
1.1412 + fLeft = left;
1.1413 + fRight = right;
1.1414 + fRuns = NULL; // means we're a rect, not a rgn
1.1415 + fDone = false;
1.1416 + } else {
1.1417 + const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y);
1.1418 + runs += 2; // skip Bottom and IntervalCount
1.1419 + for (;;) {
1.1420 + // runs[0..1] is to the right of the span, so we're done
1.1421 + if (runs[0] >= right) {
1.1422 + break;
1.1423 + }
1.1424 + // runs[0..1] is to the left of the span, so continue
1.1425 + if (runs[1] <= left) {
1.1426 + runs += 2;
1.1427 + continue;
1.1428 + }
1.1429 + // runs[0..1] intersects the span
1.1430 + fRuns = runs;
1.1431 + fLeft = left;
1.1432 + fRight = right;
1.1433 + fDone = false;
1.1434 + break;
1.1435 + }
1.1436 + }
1.1437 + }
1.1438 +}
1.1439 +
1.1440 +bool SkRegion::Spanerator::next(int* left, int* right) {
1.1441 + if (fDone) {
1.1442 + return false;
1.1443 + }
1.1444 +
1.1445 + if (fRuns == NULL) { // we're a rect
1.1446 + fDone = true; // ok, now we're done
1.1447 + if (left) {
1.1448 + *left = fLeft;
1.1449 + }
1.1450 + if (right) {
1.1451 + *right = fRight;
1.1452 + }
1.1453 + return true; // this interval is legal
1.1454 + }
1.1455 +
1.1456 + const SkRegion::RunType* runs = fRuns;
1.1457 +
1.1458 + if (runs[0] >= fRight) {
1.1459 + fDone = true;
1.1460 + return false;
1.1461 + }
1.1462 +
1.1463 + SkASSERT(runs[1] > fLeft);
1.1464 +
1.1465 + if (left) {
1.1466 + *left = SkMax32(fLeft, runs[0]);
1.1467 + }
1.1468 + if (right) {
1.1469 + *right = SkMin32(fRight, runs[1]);
1.1470 + }
1.1471 + fRuns = runs + 2;
1.1472 + return true;
1.1473 +}
1.1474 +
1.1475 +///////////////////////////////////////////////////////////////////////////////
1.1476 +
1.1477 +#ifdef SK_DEBUG
1.1478 +
1.1479 +bool SkRegion::debugSetRuns(const RunType runs[], int count) {
1.1480 + // we need to make a copy, since the real method may modify the array, and
1.1481 + // so it cannot be const.
1.1482 +
1.1483 + SkAutoTArray<RunType> storage(count);
1.1484 + memcpy(storage.get(), runs, count * sizeof(RunType));
1.1485 + return this->setRuns(storage.get(), count);
1.1486 +}
1.1487 +
1.1488 +#endif
