12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583 |
- /*
- * 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 "include/core/SkRegion.h"
- #include "include/private/SkMacros.h"
- #include "include/private/SkTemplates.h"
- #include "include/private/SkTo.h"
- #include "src/core/SkRegionPriv.h"
- #include "src/core/SkSafeMath.h"
- #include "src/utils/SkUTF.h"
- #include <utility>
- /* Region Layout
- *
- * TOP
- *
- * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ]
- * ...
- *
- * Y-Sentinel
- */
- /////////////////////////////////////////////////////////////////////////////////////////////////
- #define SkRegion_gEmptyRunHeadPtr ((SkRegionPriv::RunHead*)-1)
- #define SkRegion_gRectRunHeadPtr nullptr
- 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
- SkRegionPriv::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(SkRegionPriv::RunType));
- }
- fPtr = fMalloc.get();
- fCount = count;
- }
- }
- private:
- SkRegionPriv::RunType fStack[kRunArrayStackCount];
- SkAutoTMalloc<SkRegionPriv::RunType> fMalloc;
- int fCount = kRunArrayStackCount;
- SkRegionPriv::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)
- */
- static SkRegionPriv::RunType* skip_intervals(const SkRegionPriv::RunType runs[]) {
- int intervals = runs[-1];
- #ifdef SK_DEBUG
- if (intervals > 0) {
- SkASSERT(runs[0] < runs[1]);
- SkASSERT(runs[1] < SkRegion_kRunTypeSentinel);
- } else {
- SkASSERT(0 == intervals);
- SkASSERT(SkRegion_kRunTypeSentinel == runs[0]);
- }
- #endif
- runs += intervals * 2 + 1;
- return const_cast<SkRegionPriv::RunType*>(runs);
- }
- bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count,
- SkIRect* bounds) {
- assert_sentinel(runs[0], false); // top
- SkASSERT(count >= kRectRegionRuns);
- if (count == kRectRegionRuns) {
- assert_sentinel(runs[1], false); // bottom
- SkASSERT(1 == runs[2]);
- assert_sentinel(runs[3], false); // left
- assert_sentinel(runs[4], false); // right
- assert_sentinel(runs[5], true);
- assert_sentinel(runs[6], true);
- SkASSERT(runs[0] < runs[1]); // valid height
- SkASSERT(runs[3] < runs[4]); // valid width
- bounds->set(runs[3], runs[0], runs[4], runs[1]);
- return true;
- }
- 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 (this->isComplex()) {
- SkASSERT(fRunHead->fRefCnt >= 1);
- if (--fRunHead->fRefCnt == 0) {
- sk_free(fRunHead);
- }
- }
- }
- void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) {
- fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount);
- }
- void SkRegion::allocateRuns(int count) {
- fRunHead = RunHead::Alloc(count);
- }
- void SkRegion::allocateRuns(const RunHead& head) {
- fRunHead = RunHead::Alloc(head.fRunCount,
- head.getYSpanCount(),
- head.getIntervalCount());
- }
- SkRegion& SkRegion::operator=(const SkRegion& src) {
- (void)this->setRegion(src);
- return *this;
- }
- void SkRegion::swap(SkRegion& other) {
- using std::swap;
- swap(fBounds, other.fBounds);
- swap(fRunHead, other.fRunHead);
- }
- int SkRegion::computeRegionComplexity() const {
- if (this->isEmpty()) {
- return 0;
- } else if (this->isRect()) {
- return 1;
- }
- return fRunHead->getIntervalCount();
- }
- bool SkRegion::setEmpty() {
- this->freeRuns();
- fBounds.set(0, 0, 0, 0);
- fRunHead = SkRegion_gEmptyRunHeadPtr;
- return false;
- }
- bool SkRegion::setRect(const SkIRect& r) {
- if (r.isEmpty() ||
- SkRegion_kRunTypeSentinel == r.right() ||
- SkRegion_kRunTypeSentinel == r.bottom()) {
- return this->setEmpty();
- }
- this->freeRuns();
- fBounds = r;
- fRunHead = SkRegion_gRectRunHeadPtr;
- return true;
- }
- bool SkRegion::setRegion(const SkRegion& src) {
- if (this != &src) {
- this->freeRuns();
- fBounds = src.fBounds;
- fRunHead = src.fRunHead;
- if (this->isComplex()) {
- 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_FRAMEWORK
- #include <stdio.h>
- 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*)sk_malloc_throw(max);
- if (result == nullptr) {
- return nullptr;
- }
- count = snprintf(result, max, "SkRegion(");
- iter.reset(*this);
- while (!iter.done()) {
- const SkIRect& r = iter.rect();
- count += snprintf(result+count, max - count,
- "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom);
- iter.next();
- }
- count += snprintf(result+count, max - count, ")");
- return result;
- }
- #endif
- ///////////////////////////////////////////////////////////////////////////////
- int SkRegion::count_runtype_values(int* itop, int* ibot) const {
- int maxT;
- if (this->isRect()) {
- maxT = 2;
- } else {
- SkASSERT(this->isComplex());
- maxT = fRunHead->getIntervalCount() * 2;
- }
- *itop = fBounds.fTop;
- *ibot = fBounds.fBottom;
- return maxT;
- }
- static bool isRunCountEmpty(int count) {
- return count <= 2;
- }
- bool SkRegion::setRuns(RunType runs[], int count) {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- SkASSERT(count > 0);
- if (isRunCountEmpty(count)) {
- // 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
- // runs[2] is uncomputed intervalCount
- if (runs[3] == SkRegion_kRunTypeSentinel) { // should be first left...
- runs += 3; // skip empty initial span
- runs[0] = runs[-2]; // 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); // intervalcount
- assert_sentinel(runs[3], false); // left
- assert_sentinel(runs[4], false); // right
- }
- assert_sentinel(stop[-1], true);
- assert_sentinel(stop[-2], true);
- // now check for a trailing empty span
- if (stop[-5] == SkRegion_kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs
- stop[-4] = SkRegion_kRunTypeSentinel; // kill empty last span
- stop -= 3;
- assert_sentinel(stop[-1], true); // last y-sentinel
- assert_sentinel(stop[-2], true); // last x-sentinel
- assert_sentinel(stop[-3], false); // last right
- assert_sentinel(stop[-4], false); // last left
- assert_sentinel(stop[-5], false); // last interval-count
- assert_sentinel(stop[-6], false); // last bottom
- }
- count = (int)(stop - runs);
- }
- SkASSERT(count >= kRectRegionRuns);
- if (SkRegion::RunsAreARect(runs, count, &fBounds)) {
- return this->setRect(fBounds);
- }
- // if we get here, we need to become a complex region
- if (!this->isComplex() || fRunHead->fRunCount != count) {
- this->freeRuns();
- this->allocateRuns(count);
- SkASSERT(this->isComplex());
- }
- // 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));
- fRunHead->computeRunBounds(&fBounds);
- // Our computed bounds might be too large, so we have to check here.
- if (fBounds.isEmpty()) {
- return this->setEmpty();
- }
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- return true;
- }
- void SkRegion::BuildRectRuns(const SkIRect& bounds,
- RunType runs[kRectRegionRuns]) {
- runs[0] = bounds.fTop;
- runs[1] = bounds.fBottom;
- runs[2] = 1; // 1 interval for this scanline
- runs[3] = bounds.fLeft;
- runs[4] = bounds.fRight;
- runs[5] = SkRegion_kRunTypeSentinel;
- runs[6] = SkRegion_kRunTypeSentinel;
- }
- bool SkRegion::contains(int32_t x, int32_t y) const {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- if (!fBounds.contains(x, y)) {
- return false;
- }
- if (this->isRect()) {
- return true;
- }
- SkASSERT(this->isComplex());
- const RunType* runs = fRunHead->findScanline(y);
- // Skip the Bottom and IntervalCount
- runs += 2;
- // Just walk this scanline, checking each interval. The X-sentinel will
- // appear as a left-inteval (runs[0]) and should abort the search.
- //
- // We could do a bsearch, using interval-count (runs[1]), but need to time
- // when that would be worthwhile.
- //
- for (;;) {
- if (x < runs[0]) {
- break;
- }
- if (x < runs[1]) {
- return true;
- }
- runs += 2;
- }
- return false;
- }
- static SkRegionPriv::RunType scanline_bottom(const SkRegionPriv::RunType runs[]) {
- return runs[0];
- }
- static const SkRegionPriv::RunType* scanline_next(const SkRegionPriv::RunType runs[]) {
- // skip [B N [L R]... S]
- return runs + 2 + runs[1] * 2 + 1;
- }
- static bool scanline_contains(const SkRegionPriv::RunType runs[],
- SkRegionPriv::RunType L, SkRegionPriv::RunType R) {
- runs += 2; // skip Bottom and IntervalCount
- for (;;) {
- if (L < runs[0]) {
- break;
- }
- if (R <= runs[1]) {
- return true;
- }
- runs += 2;
- }
- return false;
- }
- bool SkRegion::contains(const SkIRect& r) const {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- if (!fBounds.contains(r)) {
- return false;
- }
- if (this->isRect()) {
- return true;
- }
- SkASSERT(this->isComplex());
- const RunType* scanline = fRunHead->findScanline(r.fTop);
- for (;;) {
- if (!scanline_contains(scanline, r.fLeft, r.fRight)) {
- return false;
- }
- if (r.fBottom <= scanline_bottom(scanline)) {
- break;
- }
- scanline = scanline_next(scanline);
- }
- return true;
- }
- bool SkRegion::contains(const SkRegion& rgn) const {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- SkDEBUGCODE(SkRegionPriv::Validate(rgn));
- if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) {
- return false;
- }
- if (this->isRect()) {
- return true;
- }
- if (rgn.isRect()) {
- return this->contains(rgn.getBounds());
- }
- /*
- * A contains B is equivalent to
- * B - A == 0
- */
- return !Oper(rgn, *this, kDifference_Op, nullptr);
- }
- const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[],
- int* intervals) const {
- SkASSERT(tmpStorage && intervals);
- const RunType* runs = tmpStorage;
- if (this->isEmpty()) {
- tmpStorage[0] = SkRegion_kRunTypeSentinel;
- *intervals = 0;
- } else if (this->isRect()) {
- BuildRectRuns(fBounds, tmpStorage);
- *intervals = 1;
- } else {
- runs = fRunHead->readonly_runs();
- *intervals = fRunHead->getIntervalCount();
- }
- return runs;
- }
- ///////////////////////////////////////////////////////////////////////////////
- static bool scanline_intersects(const SkRegionPriv::RunType runs[],
- SkRegionPriv::RunType L, SkRegionPriv::RunType R) {
- runs += 2; // skip Bottom and IntervalCount
- for (;;) {
- if (R <= runs[0]) {
- break;
- }
- if (L < runs[1]) {
- return true;
- }
- runs += 2;
- }
- return false;
- }
- bool SkRegion::intersects(const SkIRect& r) const {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- if (this->isEmpty() || r.isEmpty()) {
- return false;
- }
- SkIRect sect;
- if (!sect.intersect(fBounds, r)) {
- return false;
- }
- if (this->isRect()) {
- return true;
- }
- SkASSERT(this->isComplex());
- const RunType* scanline = fRunHead->findScanline(sect.fTop);
- for (;;) {
- if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) {
- return true;
- }
- if (sect.fBottom <= scanline_bottom(scanline)) {
- break;
- }
- scanline = scanline_next(scanline);
- }
- return false;
- }
- bool SkRegion::intersects(const SkRegion& rgn) const {
- if (this->isEmpty() || rgn.isEmpty()) {
- return false;
- }
- if (!SkIRect::Intersects(fBounds, rgn.fBounds)) {
- return false;
- }
- bool weAreARect = this->isRect();
- bool theyAreARect = rgn.isRect();
- if (weAreARect && theyAreARect) {
- return true;
- }
- if (weAreARect) {
- return rgn.intersects(this->getBounds());
- }
- if (theyAreARect) {
- return this->intersects(rgn.getBounds());
- }
- // both of us are complex
- return Oper(*this, rgn, kIntersect_Op, nullptr);
- }
- ///////////////////////////////////////////////////////////////////////////////
- bool SkRegion::operator==(const SkRegion& b) const {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- SkDEBUGCODE(SkRegionPriv::Validate(b));
- if (this == &b) {
- return true;
- }
- if (fBounds != b.fBounds) {
- return false;
- }
- const SkRegion::RunHead* ah = 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 (!this->isComplex() || !b.isComplex()) {
- return false;
- }
- return ah->fRunCount == bh->fRunCount &&
- !memcmp(ah->readonly_runs(), bh->readonly_runs(),
- ah->fRunCount * sizeof(SkRegion::RunType));
- }
- // Return a (new) offset such that when applied (+=) to min and max, we don't overflow/underflow
- static int32_t pin_offset_s32(int32_t min, int32_t max, int32_t offset) {
- SkASSERT(min <= max);
- const int32_t lo = -SK_MaxS32-1,
- hi = +SK_MaxS32;
- if ((int64_t)min + offset < lo) { offset = lo - min; }
- if ((int64_t)max + offset > hi) { offset = hi - max; }
- return offset;
- }
- void SkRegion::translate(int dx, int dy, SkRegion* dst) const {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- if (nullptr == dst) {
- return;
- }
- if (this->isEmpty()) {
- dst->setEmpty();
- return;
- }
- // pin dx and dy so we don't overflow our existing bounds
- dx = pin_offset_s32(fBounds.fLeft, fBounds.fRight, dx);
- dy = pin_offset_s32(fBounds.fTop, fBounds.fBottom, dy);
- if (this->isRect()) {
- dst->setRect(fBounds.makeOffset(dx, dy));
- } else {
- if (this == dst) {
- dst->fRunHead = dst->fRunHead->ensureWritable();
- } else {
- SkRegion tmp;
- tmp.allocateRuns(*fRunHead);
- SkASSERT(tmp.isComplex());
- 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 == SkRegion_kRunTypeSentinel) {
- break;
- }
- *druns++ = (SkRegion::RunType)(bottom + dy); // bottom;
- *druns++ = *sruns++; // copy intervalCount;
- for (;;) {
- int x = *sruns++;
- if (x == SkRegion_kRunTypeSentinel) {
- break;
- }
- *druns++ = (SkRegion::RunType)(x + dx);
- *druns++ = (SkRegion::RunType)(*sruns++ + dx);
- }
- *druns++ = SkRegion_kRunTypeSentinel; // x sentinel
- }
- *druns++ = SkRegion_kRunTypeSentinel; // y sentinel
- SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount);
- SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount);
- }
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- }
- ///////////////////////////////////////////////////////////////////////////////
- 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 // 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 SkRegionPriv::RunType* fA_runs;
- const SkRegionPriv::RunType* fB_runs;
- int fA_left, fA_rite, fB_left, fB_rite;
- int fLeft, fRite, fInside;
- void init(const SkRegionPriv::RunType a_runs[],
- const SkRegionPriv::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 int distance_to_sentinel(const SkRegionPriv::RunType* runs) {
- const SkRegionPriv::RunType* ptr = runs;
- while (*ptr != SkRegion_kRunTypeSentinel) { ptr += 2; }
- return ptr - runs;
- }
- static int operate_on_span(const SkRegionPriv::RunType a_runs[],
- const SkRegionPriv::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);
- SkRegionPriv::RunType* dst = &(*array)[dstOffset]; // get pointer AFTER resizing.
- 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++ = (SkRegionPriv::RunType)(left);
- *dst++ = (SkRegionPriv::RunType)(rite);
- firstInterval = false;
- } else {
- // update the right edge
- *(dst - 1) = (SkRegionPriv::RunType)(rite);
- }
- }
- }
- SkASSERT(dst < &(*array)[array->count() - 1]);
- *dst++ = SkRegion_kRunTypeSentinel;
- return dst - &(*array)[0];
- }
- #if defined _WIN32
- #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
- };
- // 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, RunArray* array, SkRegion::Op op)
- : fMin(gOpMinMax[op].fMin)
- , fMax(gOpMinMax[op].fMax)
- , fArray(array)
- , fTop((SkRegionPriv::RunType)top) // just a first guess, we might update this
- { SkASSERT((unsigned)op <= 3); }
- void addSpan(int bottom, const SkRegionPriv::RunType a_runs[],
- const SkRegionPriv::RunType b_runs[]) {
- // skip X values and slots for the next Y+intervalCount
- int start = fPrevDst + fPrevLen + 2;
- // start points to beginning of dst interval
- 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 == (*fArray)[stop - 1]);
- // Assert memcmp won't exceed fArray->count().
- SkASSERT(fArray->count() >= SkToInt(start + len - 1));
- if (fPrevLen == len &&
- (1 == len || !memcmp(&(*fArray)[fPrevDst],
- &(*fArray)[start],
- (len - 1) * sizeof(SkRegionPriv::RunType)))) {
- // update Y value
- (*fArray)[fPrevDst - 2] = (SkRegionPriv::RunType)bottom;
- } else { // accept the new span
- if (len == 1 && fPrevLen == 0) {
- fTop = (SkRegionPriv::RunType)bottom; // just update our bottom
- } else {
- (*fArray)[start - 2] = (SkRegionPriv::RunType)bottom;
- (*fArray)[start - 1] = SkToS32(len >> 1);
- fPrevDst = start;
- fPrevLen = len;
- }
- }
- }
- int flush() {
- (*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);
- }
- bool isEmpty() const { return 0 == fPrevLen; }
- uint8_t fMin, fMax;
- private:
- RunArray* fArray;
- int fStartDst = 0;
- int fPrevDst = 1;
- size_t fPrevLen = 0; // will never match a length from operate_on_span
- SkRegionPriv::RunType fTop;
- };
- // want a unique value to signal that we exited due to quickExit
- #define QUICK_EXIT_TRUE_COUNT (-1)
- static int operate(const SkRegionPriv::RunType a_runs[],
- const SkRegionPriv::RunType b_runs[],
- RunArray* dst,
- SkRegion::Op op,
- bool quickExit) {
- const SkRegionPriv::RunType gEmptyScanline[] = {
- 0, // dummy bottom value
- 0, // zero intervals
- 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.
- // This happens when we are using gSentinel, which is pointing at
- // our sentinel value.
- 0
- };
- const SkRegionPriv::RunType* const gSentinel = &gEmptyScanline[2];
- int a_top = *a_runs++;
- int a_bot = *a_runs++;
- int b_top = *b_runs++;
- int b_bot = *b_runs++;
- a_runs += 1; // skip the intervalCount;
- b_runs += 1; // skip the intervalCount;
- // Now a_runs and b_runs to their intervals (or sentinel)
- 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);
- 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 SkRegionPriv::RunType* run0 = gSentinel;
- const SkRegionPriv::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);
- if (quickExit && !oper.isEmpty()) {
- return QUICK_EXIT_TRUE_COUNT;
- }
- if (a_flush) {
- a_runs = skip_intervals(a_runs);
- a_top = a_bot;
- a_bot = *a_runs++;
- a_runs += 1; // skip uninitialized intervalCount
- if (a_bot == SkRegion_kRunTypeSentinel) {
- a_top = a_bot;
- }
- }
- if (b_flush) {
- b_runs = skip_intervals(b_runs);
- b_top = b_bot;
- b_bot = *b_runs++;
- b_runs += 1; // skip uninitialized intervalCount
- 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.
- */
- #if 0 // UNUSED
- static int count_to_intervals(int count) {
- SkASSERT(count >= 6); // a single rect is 6 values
- return (count - 4) >> 1;
- }
- #endif
- static bool setEmptyCheck(SkRegion* result) {
- return result ? result->setEmpty() : false;
- }
- static bool setRectCheck(SkRegion* result, const SkIRect& rect) {
- return result ? result->setRect(rect) : !rect.isEmpty();
- }
- static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) {
- return result ? result->setRegion(rgn) : !rgn.isEmpty();
- }
- bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op,
- SkRegion* result) {
- SkASSERT((unsigned)op < kOpCount);
- if (kReplace_Op == op) {
- return setRegionCheck(result, 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) {
- using std::swap;
- swap(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 setEmptyCheck(result);
- }
- if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds,
- rgnb->fBounds)) {
- return setRegionCheck(result, *rgna);
- }
- if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) {
- return setEmptyCheck(result);
- }
- break;
- case kIntersect_Op:
- if ((a_empty | b_empty)
- || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) {
- return setEmptyCheck(result);
- }
- if (a_rect & b_rect) {
- return setRectCheck(result, bounds);
- }
- if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
- return setRegionCheck(result, *rgnb);
- }
- if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
- return setRegionCheck(result, *rgna);
- }
- break;
- case kUnion_Op:
- if (a_empty) {
- return setRegionCheck(result, *rgnb);
- }
- if (b_empty) {
- return setRegionCheck(result, *rgna);
- }
- if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
- return setRegionCheck(result, *rgna);
- }
- if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
- return setRegionCheck(result, *rgnb);
- }
- break;
- case kXOR_Op:
- if (a_empty) {
- return setRegionCheck(result, *rgnb);
- }
- if (b_empty) {
- return setRegionCheck(result, *rgna);
- }
- break;
- default:
- SkDEBUGFAIL("unknown region op");
- return false;
- }
- RunType tmpA[kRectRegionRuns];
- RunType tmpB[kRectRegionRuns];
- int a_intervals, b_intervals;
- const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals);
- const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals);
- 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[0], count);
- } else {
- return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count);
- }
- }
- bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) {
- SkDEBUGCODE(SkRegionPriv::Validate(*this));
- return SkRegion::Oper(rgna, rgnb, op, this);
- }
- ///////////////////////////////////////////////////////////////////////////////
- #include "src/core/SkBuffer.h"
- size_t SkRegion::writeToMemory(void* storage) const {
- if (nullptr == storage) {
- size_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount
- if (!this->isEmpty()) {
- size += sizeof(fBounds);
- if (this->isComplex()) {
- size += 2 * sizeof(int32_t); // ySpanCount + intervalCount
- 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.write32(fRunHead->getYSpanCount());
- buffer.write32(fRunHead->getIntervalCount());
- buffer.write(fRunHead->readonly_runs(),
- fRunHead->fRunCount * sizeof(RunType));
- }
- }
- return buffer.pos();
- }
- static bool validate_run_count(int ySpanCount, int intervalCount, int runCount) {
- // return 2 + 3 * ySpanCount + 2 * intervalCount;
- if (ySpanCount < 1 || intervalCount < 2) {
- return false;
- }
- SkSafeMath safeMath;
- int sum = 2;
- sum = safeMath.addInt(sum, ySpanCount);
- sum = safeMath.addInt(sum, ySpanCount);
- sum = safeMath.addInt(sum, ySpanCount);
- sum = safeMath.addInt(sum, intervalCount);
- sum = safeMath.addInt(sum, intervalCount);
- return safeMath && sum == runCount;
- }
- // Validate that a memory sequence is a valid region.
- // Try to check all possible errors.
- // never read beyond &runs[runCount-1].
- static bool validate_run(const int32_t* runs,
- int runCount,
- const SkIRect& givenBounds,
- int32_t ySpanCount,
- int32_t intervalCount) {
- // Region Layout:
- // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel
- if (!validate_run_count(SkToInt(ySpanCount), SkToInt(intervalCount), runCount)) {
- return false;
- }
- SkASSERT(runCount >= 7); // 7==SkRegion::kRectRegionRuns
- // quick sanity check:
- if (runs[runCount - 1] != SkRegion_kRunTypeSentinel ||
- runs[runCount - 2] != SkRegion_kRunTypeSentinel) {
- return false;
- }
- const int32_t* const end = runs + runCount;
- SkIRect bounds = {0, 0, 0 ,0}; // calulated bounds
- SkIRect rect = {0, 0, 0, 0}; // current rect
- rect.fTop = *runs++;
- if (rect.fTop == SkRegion_kRunTypeSentinel) {
- return false; // no rect can contain SkRegion_kRunTypeSentinel
- }
- if (rect.fTop != givenBounds.fTop) {
- return false; // Must not begin with empty span that does not contribute to bounds.
- }
- do {
- --ySpanCount;
- if (ySpanCount < 0) {
- return false; // too many yspans
- }
- rect.fBottom = *runs++;
- if (rect.fBottom == SkRegion_kRunTypeSentinel) {
- return false;
- }
- if (rect.fBottom > givenBounds.fBottom) {
- return false; // Must not end with empty span that does not contribute to bounds.
- }
- if (rect.fBottom <= rect.fTop) {
- return false; // y-intervals must be ordered; rects must be non-empty.
- }
- int32_t xIntervals = *runs++;
- SkASSERT(runs < end);
- if (xIntervals < 0 || xIntervals > intervalCount || runs + 1 + 2 * xIntervals > end) {
- return false;
- }
- intervalCount -= xIntervals;
- bool firstInterval = true;
- int32_t lastRight = 0; // check that x-intervals are distinct and ordered.
- while (xIntervals-- > 0) {
- rect.fLeft = *runs++;
- rect.fRight = *runs++;
- if (rect.fLeft == SkRegion_kRunTypeSentinel ||
- rect.fRight == SkRegion_kRunTypeSentinel ||
- rect.fLeft >= rect.fRight || // check non-empty rect
- (!firstInterval && rect.fLeft <= lastRight)) {
- return false;
- }
- lastRight = rect.fRight;
- firstInterval = false;
- bounds.join(rect);
- }
- if (*runs++ != SkRegion_kRunTypeSentinel) {
- return false; // required check sentinal.
- }
- rect.fTop = rect.fBottom;
- SkASSERT(runs < end);
- } while (*runs != SkRegion_kRunTypeSentinel);
- ++runs;
- if (ySpanCount != 0 || intervalCount != 0 || givenBounds != bounds) {
- return false;
- }
- SkASSERT(runs == end); // if ySpanCount && intervalCount are right, must be correct length.
- return true;
- }
- size_t SkRegion::readFromMemory(const void* storage, size_t length) {
- SkRBuffer buffer(storage, length);
- SkRegion tmp;
- int32_t count;
- // Serialized Region Format:
- // Empty:
- // -1
- // Simple Rect:
- // 0 LEFT TOP RIGHT BOTTOM
- // Complex Region:
- // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT [RUNS....]
- if (!buffer.readS32(&count) || count < -1) {
- return 0;
- }
- if (count >= 0) {
- if (!buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)) || tmp.fBounds.isEmpty()) {
- return 0; // Short buffer or bad bounds for non-empty region; report failure.
- }
- if (count == 0) {
- tmp.fRunHead = SkRegion_gRectRunHeadPtr;
- } else {
- int32_t ySpanCount, intervalCount;
- if (!buffer.readS32(&ySpanCount) ||
- !buffer.readS32(&intervalCount) ||
- buffer.available() < count * sizeof(int32_t)) {
- return 0;
- }
- if (!validate_run((const int32_t*)((const char*)storage + buffer.pos()), count,
- tmp.fBounds, ySpanCount, intervalCount)) {
- return 0; // invalid runs, don't even allocate
- }
- tmp.allocateRuns(count, ySpanCount, intervalCount);
- SkASSERT(tmp.isComplex());
- SkAssertResult(buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(int32_t)));
- }
- }
- SkASSERT(tmp.isValid());
- SkASSERT(buffer.isValid());
- this->swap(tmp);
- return buffer.pos();
- }
- ///////////////////////////////////////////////////////////////////////////////
- bool SkRegion::isValid() const {
- if (this->isEmpty()) {
- return fBounds == SkIRect{0, 0, 0, 0};
- }
- if (fBounds.isEmpty()) {
- return false;
- }
- if (this->isRect()) {
- return true;
- }
- return fRunHead && fRunHead->fRefCnt > 0 &&
- validate_run(fRunHead->readonly_runs(), fRunHead->fRunCount, fBounds,
- fRunHead->getYSpanCount(), fRunHead->getIntervalCount());
- }
- #ifdef SK_DEBUG
- void SkRegionPriv::Validate(const SkRegion& rgn) { SkASSERT(rgn.isValid()); }
- 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 = nullptr;
- } else {
- fRuns = rgn.fRunHead->readonly_runs();
- fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]);
- fRuns += 5;
- // Now fRuns points to the 2nd interval (or x-sentinel)
- }
- }
- }
- void SkRegion::Iterator::next() {
- if (fDone) {
- return;
- }
- if (fRuns == nullptr) { // rect case
- fDone = true;
- return;
- }
- const RunType* runs = fRuns;
- if (runs[0] < SkRegion_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] < SkRegion_kRunTypeSentinel) { // valid Y value
- int intervals = runs[1];
- if (0 == intervals) { // empty line
- fRect.fTop = runs[0];
- runs += 3;
- } else {
- fRect.fTop = fRect.fBottom;
- }
- fRect.fBottom = runs[0];
- assert_sentinel(runs[2], false);
- assert_sentinel(runs[3], false);
- fRect.fLeft = runs[2];
- fRect.fRight = runs[3];
- runs += 4;
- } 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();
- }
- }
- ///////////////////////////////////////////////////////////////////////////////
- SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left,
- int right) {
- SkDEBUGCODE(SkRegionPriv::Validate(rgn));
- 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 = nullptr; // means we're a rect, not a rgn
- fDone = false;
- } else {
- const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y);
- runs += 2; // skip Bottom and IntervalCount
- 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 == nullptr) { // 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;
- }
- ///////////////////////////////////////////////////////////////////////////////////////////////////
- static void visit_pairs(int pairCount, int y, const int32_t pairs[],
- const std::function<void(const SkIRect&)>& visitor) {
- for (int i = 0; i < pairCount; ++i) {
- visitor({ pairs[0], y, pairs[1], y + 1 });
- pairs += 2;
- }
- }
- void SkRegionPriv::VisitSpans(const SkRegion& rgn,
- const std::function<void(const SkIRect&)>& visitor) {
- if (rgn.isEmpty()) {
- return;
- }
- if (rgn.isRect()) {
- visitor(rgn.getBounds());
- } else {
- const int32_t* p = rgn.fRunHead->readonly_runs();
- int32_t top = *p++;
- int32_t bot = *p++;
- do {
- int pairCount = *p++;
- if (pairCount == 1) {
- visitor({ p[0], top, p[1], bot });
- p += 2;
- } else if (pairCount > 1) {
- // we have to loop repeated in Y, sending each interval in Y -> X order
- for (int y = top; y < bot; ++y) {
- visit_pairs(pairCount, y, p, visitor);
- }
- p += pairCount * 2;
- }
- assert_sentinel(*p, true);
- p += 1; // skip sentinel
- // read next bottom or sentinel
- top = bot;
- bot = *p++;
- } while (!SkRegionValueIsSentinel(bot));
- }
- }
|