SkRegion.cpp 47 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583
  1. /*
  2. * Copyright 2006 The Android Open Source Project
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "include/core/SkRegion.h"
  8. #include "include/private/SkMacros.h"
  9. #include "include/private/SkTemplates.h"
  10. #include "include/private/SkTo.h"
  11. #include "src/core/SkRegionPriv.h"
  12. #include "src/core/SkSafeMath.h"
  13. #include "src/utils/SkUTF.h"
  14. #include <utility>
  15. /* Region Layout
  16. *
  17. * TOP
  18. *
  19. * [ Bottom, X-Intervals, [Left, Right]..., X-Sentinel ]
  20. * ...
  21. *
  22. * Y-Sentinel
  23. */
  24. /////////////////////////////////////////////////////////////////////////////////////////////////
  25. #define SkRegion_gEmptyRunHeadPtr ((SkRegionPriv::RunHead*)-1)
  26. #define SkRegion_gRectRunHeadPtr nullptr
  27. constexpr int kRunArrayStackCount = 256;
  28. // This is a simple data structure which is like a SkSTArray<N,T,true>, except that:
  29. // - It does not initialize memory.
  30. // - It does not distinguish between reserved space and initialized space.
  31. // - resizeToAtLeast() instead of resize()
  32. // - Uses sk_realloc_throw()
  33. // - Can never be made smaller.
  34. // Measurement: for the `region_union_16` benchmark, this is 6% faster.
  35. class RunArray {
  36. public:
  37. RunArray() { fPtr = fStack; }
  38. #ifdef SK_DEBUG
  39. int count() const { return fCount; }
  40. #endif
  41. SkRegionPriv::RunType& operator[](int i) {
  42. SkASSERT((unsigned)i < (unsigned)fCount);
  43. return fPtr[i];
  44. }
  45. /** Resize the array to a size greater-than-or-equal-to count. */
  46. void resizeToAtLeast(int count) {
  47. if (count > fCount) {
  48. // leave at least 50% extra space for future growth.
  49. count += count >> 1;
  50. fMalloc.realloc(count);
  51. if (fPtr == fStack) {
  52. memcpy(fMalloc.get(), fStack, fCount * sizeof(SkRegionPriv::RunType));
  53. }
  54. fPtr = fMalloc.get();
  55. fCount = count;
  56. }
  57. }
  58. private:
  59. SkRegionPriv::RunType fStack[kRunArrayStackCount];
  60. SkAutoTMalloc<SkRegionPriv::RunType> fMalloc;
  61. int fCount = kRunArrayStackCount;
  62. SkRegionPriv::RunType* fPtr; // non-owning pointer
  63. };
  64. /* Pass in the beginning with the intervals.
  65. * We back up 1 to read the interval-count.
  66. * Return the beginning of the next scanline (i.e. the next Y-value)
  67. */
  68. static SkRegionPriv::RunType* skip_intervals(const SkRegionPriv::RunType runs[]) {
  69. int intervals = runs[-1];
  70. #ifdef SK_DEBUG
  71. if (intervals > 0) {
  72. SkASSERT(runs[0] < runs[1]);
  73. SkASSERT(runs[1] < SkRegion_kRunTypeSentinel);
  74. } else {
  75. SkASSERT(0 == intervals);
  76. SkASSERT(SkRegion_kRunTypeSentinel == runs[0]);
  77. }
  78. #endif
  79. runs += intervals * 2 + 1;
  80. return const_cast<SkRegionPriv::RunType*>(runs);
  81. }
  82. bool SkRegion::RunsAreARect(const SkRegion::RunType runs[], int count,
  83. SkIRect* bounds) {
  84. assert_sentinel(runs[0], false); // top
  85. SkASSERT(count >= kRectRegionRuns);
  86. if (count == kRectRegionRuns) {
  87. assert_sentinel(runs[1], false); // bottom
  88. SkASSERT(1 == runs[2]);
  89. assert_sentinel(runs[3], false); // left
  90. assert_sentinel(runs[4], false); // right
  91. assert_sentinel(runs[5], true);
  92. assert_sentinel(runs[6], true);
  93. SkASSERT(runs[0] < runs[1]); // valid height
  94. SkASSERT(runs[3] < runs[4]); // valid width
  95. bounds->set(runs[3], runs[0], runs[4], runs[1]);
  96. return true;
  97. }
  98. return false;
  99. }
  100. //////////////////////////////////////////////////////////////////////////
  101. SkRegion::SkRegion() {
  102. fBounds.set(0, 0, 0, 0);
  103. fRunHead = SkRegion_gEmptyRunHeadPtr;
  104. }
  105. SkRegion::SkRegion(const SkRegion& src) {
  106. fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
  107. this->setRegion(src);
  108. }
  109. SkRegion::SkRegion(const SkIRect& rect) {
  110. fRunHead = SkRegion_gEmptyRunHeadPtr; // just need a value that won't trigger sk_free(fRunHead)
  111. this->setRect(rect);
  112. }
  113. SkRegion::~SkRegion() {
  114. this->freeRuns();
  115. }
  116. void SkRegion::freeRuns() {
  117. if (this->isComplex()) {
  118. SkASSERT(fRunHead->fRefCnt >= 1);
  119. if (--fRunHead->fRefCnt == 0) {
  120. sk_free(fRunHead);
  121. }
  122. }
  123. }
  124. void SkRegion::allocateRuns(int count, int ySpanCount, int intervalCount) {
  125. fRunHead = RunHead::Alloc(count, ySpanCount, intervalCount);
  126. }
  127. void SkRegion::allocateRuns(int count) {
  128. fRunHead = RunHead::Alloc(count);
  129. }
  130. void SkRegion::allocateRuns(const RunHead& head) {
  131. fRunHead = RunHead::Alloc(head.fRunCount,
  132. head.getYSpanCount(),
  133. head.getIntervalCount());
  134. }
  135. SkRegion& SkRegion::operator=(const SkRegion& src) {
  136. (void)this->setRegion(src);
  137. return *this;
  138. }
  139. void SkRegion::swap(SkRegion& other) {
  140. using std::swap;
  141. swap(fBounds, other.fBounds);
  142. swap(fRunHead, other.fRunHead);
  143. }
  144. int SkRegion::computeRegionComplexity() const {
  145. if (this->isEmpty()) {
  146. return 0;
  147. } else if (this->isRect()) {
  148. return 1;
  149. }
  150. return fRunHead->getIntervalCount();
  151. }
  152. bool SkRegion::setEmpty() {
  153. this->freeRuns();
  154. fBounds.set(0, 0, 0, 0);
  155. fRunHead = SkRegion_gEmptyRunHeadPtr;
  156. return false;
  157. }
  158. bool SkRegion::setRect(const SkIRect& r) {
  159. if (r.isEmpty() ||
  160. SkRegion_kRunTypeSentinel == r.right() ||
  161. SkRegion_kRunTypeSentinel == r.bottom()) {
  162. return this->setEmpty();
  163. }
  164. this->freeRuns();
  165. fBounds = r;
  166. fRunHead = SkRegion_gRectRunHeadPtr;
  167. return true;
  168. }
  169. bool SkRegion::setRegion(const SkRegion& src) {
  170. if (this != &src) {
  171. this->freeRuns();
  172. fBounds = src.fBounds;
  173. fRunHead = src.fRunHead;
  174. if (this->isComplex()) {
  175. fRunHead->fRefCnt++;
  176. }
  177. }
  178. return fRunHead != SkRegion_gEmptyRunHeadPtr;
  179. }
  180. bool SkRegion::op(const SkIRect& rect, const SkRegion& rgn, Op op) {
  181. SkRegion tmp(rect);
  182. return this->op(tmp, rgn, op);
  183. }
  184. bool SkRegion::op(const SkRegion& rgn, const SkIRect& rect, Op op) {
  185. SkRegion tmp(rect);
  186. return this->op(rgn, tmp, op);
  187. }
  188. ///////////////////////////////////////////////////////////////////////////////
  189. #ifdef SK_BUILD_FOR_ANDROID_FRAMEWORK
  190. #include <stdio.h>
  191. char* SkRegion::toString() {
  192. Iterator iter(*this);
  193. int count = 0;
  194. while (!iter.done()) {
  195. count++;
  196. iter.next();
  197. }
  198. // 4 ints, up to 10 digits each plus sign, 3 commas, '(', ')', SkRegion() and '\0'
  199. const int max = (count*((11*4)+5))+11+1;
  200. char* result = (char*)sk_malloc_throw(max);
  201. if (result == nullptr) {
  202. return nullptr;
  203. }
  204. count = snprintf(result, max, "SkRegion(");
  205. iter.reset(*this);
  206. while (!iter.done()) {
  207. const SkIRect& r = iter.rect();
  208. count += snprintf(result+count, max - count,
  209. "(%d,%d,%d,%d)", r.fLeft, r.fTop, r.fRight, r.fBottom);
  210. iter.next();
  211. }
  212. count += snprintf(result+count, max - count, ")");
  213. return result;
  214. }
  215. #endif
  216. ///////////////////////////////////////////////////////////////////////////////
  217. int SkRegion::count_runtype_values(int* itop, int* ibot) const {
  218. int maxT;
  219. if (this->isRect()) {
  220. maxT = 2;
  221. } else {
  222. SkASSERT(this->isComplex());
  223. maxT = fRunHead->getIntervalCount() * 2;
  224. }
  225. *itop = fBounds.fTop;
  226. *ibot = fBounds.fBottom;
  227. return maxT;
  228. }
  229. static bool isRunCountEmpty(int count) {
  230. return count <= 2;
  231. }
  232. bool SkRegion::setRuns(RunType runs[], int count) {
  233. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  234. SkASSERT(count > 0);
  235. if (isRunCountEmpty(count)) {
  236. // SkDEBUGF("setRuns: empty\n");
  237. assert_sentinel(runs[count-1], true);
  238. return this->setEmpty();
  239. }
  240. // trim off any empty spans from the top and bottom
  241. // weird I should need this, perhaps op() could be smarter...
  242. if (count > kRectRegionRuns) {
  243. RunType* stop = runs + count;
  244. assert_sentinel(runs[0], false); // top
  245. assert_sentinel(runs[1], false); // bottom
  246. // runs[2] is uncomputed intervalCount
  247. if (runs[3] == SkRegion_kRunTypeSentinel) { // should be first left...
  248. runs += 3; // skip empty initial span
  249. runs[0] = runs[-2]; // set new top to prev bottom
  250. assert_sentinel(runs[1], false); // bot: a sentinal would mean two in a row
  251. assert_sentinel(runs[2], false); // intervalcount
  252. assert_sentinel(runs[3], false); // left
  253. assert_sentinel(runs[4], false); // right
  254. }
  255. assert_sentinel(stop[-1], true);
  256. assert_sentinel(stop[-2], true);
  257. // now check for a trailing empty span
  258. if (stop[-5] == SkRegion_kRunTypeSentinel) { // eek, stop[-4] was a bottom with no x-runs
  259. stop[-4] = SkRegion_kRunTypeSentinel; // kill empty last span
  260. stop -= 3;
  261. assert_sentinel(stop[-1], true); // last y-sentinel
  262. assert_sentinel(stop[-2], true); // last x-sentinel
  263. assert_sentinel(stop[-3], false); // last right
  264. assert_sentinel(stop[-4], false); // last left
  265. assert_sentinel(stop[-5], false); // last interval-count
  266. assert_sentinel(stop[-6], false); // last bottom
  267. }
  268. count = (int)(stop - runs);
  269. }
  270. SkASSERT(count >= kRectRegionRuns);
  271. if (SkRegion::RunsAreARect(runs, count, &fBounds)) {
  272. return this->setRect(fBounds);
  273. }
  274. // if we get here, we need to become a complex region
  275. if (!this->isComplex() || fRunHead->fRunCount != count) {
  276. this->freeRuns();
  277. this->allocateRuns(count);
  278. SkASSERT(this->isComplex());
  279. }
  280. // must call this before we can write directly into runs()
  281. // in case we are sharing the buffer with another region (copy on write)
  282. fRunHead = fRunHead->ensureWritable();
  283. memcpy(fRunHead->writable_runs(), runs, count * sizeof(RunType));
  284. fRunHead->computeRunBounds(&fBounds);
  285. // Our computed bounds might be too large, so we have to check here.
  286. if (fBounds.isEmpty()) {
  287. return this->setEmpty();
  288. }
  289. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  290. return true;
  291. }
  292. void SkRegion::BuildRectRuns(const SkIRect& bounds,
  293. RunType runs[kRectRegionRuns]) {
  294. runs[0] = bounds.fTop;
  295. runs[1] = bounds.fBottom;
  296. runs[2] = 1; // 1 interval for this scanline
  297. runs[3] = bounds.fLeft;
  298. runs[4] = bounds.fRight;
  299. runs[5] = SkRegion_kRunTypeSentinel;
  300. runs[6] = SkRegion_kRunTypeSentinel;
  301. }
  302. bool SkRegion::contains(int32_t x, int32_t y) const {
  303. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  304. if (!fBounds.contains(x, y)) {
  305. return false;
  306. }
  307. if (this->isRect()) {
  308. return true;
  309. }
  310. SkASSERT(this->isComplex());
  311. const RunType* runs = fRunHead->findScanline(y);
  312. // Skip the Bottom and IntervalCount
  313. runs += 2;
  314. // Just walk this scanline, checking each interval. The X-sentinel will
  315. // appear as a left-inteval (runs[0]) and should abort the search.
  316. //
  317. // We could do a bsearch, using interval-count (runs[1]), but need to time
  318. // when that would be worthwhile.
  319. //
  320. for (;;) {
  321. if (x < runs[0]) {
  322. break;
  323. }
  324. if (x < runs[1]) {
  325. return true;
  326. }
  327. runs += 2;
  328. }
  329. return false;
  330. }
  331. static SkRegionPriv::RunType scanline_bottom(const SkRegionPriv::RunType runs[]) {
  332. return runs[0];
  333. }
  334. static const SkRegionPriv::RunType* scanline_next(const SkRegionPriv::RunType runs[]) {
  335. // skip [B N [L R]... S]
  336. return runs + 2 + runs[1] * 2 + 1;
  337. }
  338. static bool scanline_contains(const SkRegionPriv::RunType runs[],
  339. SkRegionPriv::RunType L, SkRegionPriv::RunType R) {
  340. runs += 2; // skip Bottom and IntervalCount
  341. for (;;) {
  342. if (L < runs[0]) {
  343. break;
  344. }
  345. if (R <= runs[1]) {
  346. return true;
  347. }
  348. runs += 2;
  349. }
  350. return false;
  351. }
  352. bool SkRegion::contains(const SkIRect& r) const {
  353. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  354. if (!fBounds.contains(r)) {
  355. return false;
  356. }
  357. if (this->isRect()) {
  358. return true;
  359. }
  360. SkASSERT(this->isComplex());
  361. const RunType* scanline = fRunHead->findScanline(r.fTop);
  362. for (;;) {
  363. if (!scanline_contains(scanline, r.fLeft, r.fRight)) {
  364. return false;
  365. }
  366. if (r.fBottom <= scanline_bottom(scanline)) {
  367. break;
  368. }
  369. scanline = scanline_next(scanline);
  370. }
  371. return true;
  372. }
  373. bool SkRegion::contains(const SkRegion& rgn) const {
  374. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  375. SkDEBUGCODE(SkRegionPriv::Validate(rgn));
  376. if (this->isEmpty() || rgn.isEmpty() || !fBounds.contains(rgn.fBounds)) {
  377. return false;
  378. }
  379. if (this->isRect()) {
  380. return true;
  381. }
  382. if (rgn.isRect()) {
  383. return this->contains(rgn.getBounds());
  384. }
  385. /*
  386. * A contains B is equivalent to
  387. * B - A == 0
  388. */
  389. return !Oper(rgn, *this, kDifference_Op, nullptr);
  390. }
  391. const SkRegion::RunType* SkRegion::getRuns(RunType tmpStorage[],
  392. int* intervals) const {
  393. SkASSERT(tmpStorage && intervals);
  394. const RunType* runs = tmpStorage;
  395. if (this->isEmpty()) {
  396. tmpStorage[0] = SkRegion_kRunTypeSentinel;
  397. *intervals = 0;
  398. } else if (this->isRect()) {
  399. BuildRectRuns(fBounds, tmpStorage);
  400. *intervals = 1;
  401. } else {
  402. runs = fRunHead->readonly_runs();
  403. *intervals = fRunHead->getIntervalCount();
  404. }
  405. return runs;
  406. }
  407. ///////////////////////////////////////////////////////////////////////////////
  408. static bool scanline_intersects(const SkRegionPriv::RunType runs[],
  409. SkRegionPriv::RunType L, SkRegionPriv::RunType R) {
  410. runs += 2; // skip Bottom and IntervalCount
  411. for (;;) {
  412. if (R <= runs[0]) {
  413. break;
  414. }
  415. if (L < runs[1]) {
  416. return true;
  417. }
  418. runs += 2;
  419. }
  420. return false;
  421. }
  422. bool SkRegion::intersects(const SkIRect& r) const {
  423. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  424. if (this->isEmpty() || r.isEmpty()) {
  425. return false;
  426. }
  427. SkIRect sect;
  428. if (!sect.intersect(fBounds, r)) {
  429. return false;
  430. }
  431. if (this->isRect()) {
  432. return true;
  433. }
  434. SkASSERT(this->isComplex());
  435. const RunType* scanline = fRunHead->findScanline(sect.fTop);
  436. for (;;) {
  437. if (scanline_intersects(scanline, sect.fLeft, sect.fRight)) {
  438. return true;
  439. }
  440. if (sect.fBottom <= scanline_bottom(scanline)) {
  441. break;
  442. }
  443. scanline = scanline_next(scanline);
  444. }
  445. return false;
  446. }
  447. bool SkRegion::intersects(const SkRegion& rgn) const {
  448. if (this->isEmpty() || rgn.isEmpty()) {
  449. return false;
  450. }
  451. if (!SkIRect::Intersects(fBounds, rgn.fBounds)) {
  452. return false;
  453. }
  454. bool weAreARect = this->isRect();
  455. bool theyAreARect = rgn.isRect();
  456. if (weAreARect && theyAreARect) {
  457. return true;
  458. }
  459. if (weAreARect) {
  460. return rgn.intersects(this->getBounds());
  461. }
  462. if (theyAreARect) {
  463. return this->intersects(rgn.getBounds());
  464. }
  465. // both of us are complex
  466. return Oper(*this, rgn, kIntersect_Op, nullptr);
  467. }
  468. ///////////////////////////////////////////////////////////////////////////////
  469. bool SkRegion::operator==(const SkRegion& b) const {
  470. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  471. SkDEBUGCODE(SkRegionPriv::Validate(b));
  472. if (this == &b) {
  473. return true;
  474. }
  475. if (fBounds != b.fBounds) {
  476. return false;
  477. }
  478. const SkRegion::RunHead* ah = fRunHead;
  479. const SkRegion::RunHead* bh = b.fRunHead;
  480. // this catches empties and rects being equal
  481. if (ah == bh) {
  482. return true;
  483. }
  484. // now we insist that both are complex (but different ptrs)
  485. if (!this->isComplex() || !b.isComplex()) {
  486. return false;
  487. }
  488. return ah->fRunCount == bh->fRunCount &&
  489. !memcmp(ah->readonly_runs(), bh->readonly_runs(),
  490. ah->fRunCount * sizeof(SkRegion::RunType));
  491. }
  492. // Return a (new) offset such that when applied (+=) to min and max, we don't overflow/underflow
  493. static int32_t pin_offset_s32(int32_t min, int32_t max, int32_t offset) {
  494. SkASSERT(min <= max);
  495. const int32_t lo = -SK_MaxS32-1,
  496. hi = +SK_MaxS32;
  497. if ((int64_t)min + offset < lo) { offset = lo - min; }
  498. if ((int64_t)max + offset > hi) { offset = hi - max; }
  499. return offset;
  500. }
  501. void SkRegion::translate(int dx, int dy, SkRegion* dst) const {
  502. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  503. if (nullptr == dst) {
  504. return;
  505. }
  506. if (this->isEmpty()) {
  507. dst->setEmpty();
  508. return;
  509. }
  510. // pin dx and dy so we don't overflow our existing bounds
  511. dx = pin_offset_s32(fBounds.fLeft, fBounds.fRight, dx);
  512. dy = pin_offset_s32(fBounds.fTop, fBounds.fBottom, dy);
  513. if (this->isRect()) {
  514. dst->setRect(fBounds.makeOffset(dx, dy));
  515. } else {
  516. if (this == dst) {
  517. dst->fRunHead = dst->fRunHead->ensureWritable();
  518. } else {
  519. SkRegion tmp;
  520. tmp.allocateRuns(*fRunHead);
  521. SkASSERT(tmp.isComplex());
  522. tmp.fBounds = fBounds;
  523. dst->swap(tmp);
  524. }
  525. dst->fBounds.offset(dx, dy);
  526. const RunType* sruns = fRunHead->readonly_runs();
  527. RunType* druns = dst->fRunHead->writable_runs();
  528. *druns++ = (SkRegion::RunType)(*sruns++ + dy); // top
  529. for (;;) {
  530. int bottom = *sruns++;
  531. if (bottom == SkRegion_kRunTypeSentinel) {
  532. break;
  533. }
  534. *druns++ = (SkRegion::RunType)(bottom + dy); // bottom;
  535. *druns++ = *sruns++; // copy intervalCount;
  536. for (;;) {
  537. int x = *sruns++;
  538. if (x == SkRegion_kRunTypeSentinel) {
  539. break;
  540. }
  541. *druns++ = (SkRegion::RunType)(x + dx);
  542. *druns++ = (SkRegion::RunType)(*sruns++ + dx);
  543. }
  544. *druns++ = SkRegion_kRunTypeSentinel; // x sentinel
  545. }
  546. *druns++ = SkRegion_kRunTypeSentinel; // y sentinel
  547. SkASSERT(sruns - fRunHead->readonly_runs() == fRunHead->fRunCount);
  548. SkASSERT(druns - dst->fRunHead->readonly_runs() == dst->fRunHead->fRunCount);
  549. }
  550. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  551. }
  552. ///////////////////////////////////////////////////////////////////////////////
  553. bool SkRegion::setRects(const SkIRect rects[], int count) {
  554. if (0 == count) {
  555. this->setEmpty();
  556. } else {
  557. this->setRect(rects[0]);
  558. for (int i = 1; i < count; i++) {
  559. this->op(rects[i], kUnion_Op);
  560. }
  561. }
  562. return !this->isEmpty();
  563. }
  564. ///////////////////////////////////////////////////////////////////////////////
  565. #if defined _WIN32 // disable warning : local variable used without having been initialized
  566. #pragma warning ( push )
  567. #pragma warning ( disable : 4701 )
  568. #endif
  569. #ifdef SK_DEBUG
  570. static void assert_valid_pair(int left, int rite)
  571. {
  572. SkASSERT(left == SkRegion_kRunTypeSentinel || left < rite);
  573. }
  574. #else
  575. #define assert_valid_pair(left, rite)
  576. #endif
  577. struct spanRec {
  578. const SkRegionPriv::RunType* fA_runs;
  579. const SkRegionPriv::RunType* fB_runs;
  580. int fA_left, fA_rite, fB_left, fB_rite;
  581. int fLeft, fRite, fInside;
  582. void init(const SkRegionPriv::RunType a_runs[],
  583. const SkRegionPriv::RunType b_runs[]) {
  584. fA_left = *a_runs++;
  585. fA_rite = *a_runs++;
  586. fB_left = *b_runs++;
  587. fB_rite = *b_runs++;
  588. fA_runs = a_runs;
  589. fB_runs = b_runs;
  590. }
  591. bool done() const {
  592. SkASSERT(fA_left <= SkRegion_kRunTypeSentinel);
  593. SkASSERT(fB_left <= SkRegion_kRunTypeSentinel);
  594. return fA_left == SkRegion_kRunTypeSentinel &&
  595. fB_left == SkRegion_kRunTypeSentinel;
  596. }
  597. void next() {
  598. assert_valid_pair(fA_left, fA_rite);
  599. assert_valid_pair(fB_left, fB_rite);
  600. int inside, left, rite SK_INIT_TO_AVOID_WARNING;
  601. bool a_flush = false;
  602. bool b_flush = false;
  603. int a_left = fA_left;
  604. int a_rite = fA_rite;
  605. int b_left = fB_left;
  606. int b_rite = fB_rite;
  607. if (a_left < b_left) {
  608. inside = 1;
  609. left = a_left;
  610. if (a_rite <= b_left) { // [...] <...>
  611. rite = a_rite;
  612. a_flush = true;
  613. } else { // [...<..]...> or [...<...>...]
  614. rite = a_left = b_left;
  615. }
  616. } else if (b_left < a_left) {
  617. inside = 2;
  618. left = b_left;
  619. if (b_rite <= a_left) { // [...] <...>
  620. rite = b_rite;
  621. b_flush = true;
  622. } else { // [...<..]...> or [...<...>...]
  623. rite = b_left = a_left;
  624. }
  625. } else { // a_left == b_left
  626. inside = 3;
  627. left = a_left; // or b_left
  628. if (a_rite <= b_rite) {
  629. rite = b_left = a_rite;
  630. a_flush = true;
  631. }
  632. if (b_rite <= a_rite) {
  633. rite = a_left = b_rite;
  634. b_flush = true;
  635. }
  636. }
  637. if (a_flush) {
  638. a_left = *fA_runs++;
  639. a_rite = *fA_runs++;
  640. }
  641. if (b_flush) {
  642. b_left = *fB_runs++;
  643. b_rite = *fB_runs++;
  644. }
  645. SkASSERT(left <= rite);
  646. // now update our state
  647. fA_left = a_left;
  648. fA_rite = a_rite;
  649. fB_left = b_left;
  650. fB_rite = b_rite;
  651. fLeft = left;
  652. fRite = rite;
  653. fInside = inside;
  654. }
  655. };
  656. static int distance_to_sentinel(const SkRegionPriv::RunType* runs) {
  657. const SkRegionPriv::RunType* ptr = runs;
  658. while (*ptr != SkRegion_kRunTypeSentinel) { ptr += 2; }
  659. return ptr - runs;
  660. }
  661. static int operate_on_span(const SkRegionPriv::RunType a_runs[],
  662. const SkRegionPriv::RunType b_runs[],
  663. RunArray* array, int dstOffset,
  664. int min, int max) {
  665. // This is a worst-case for this span plus two for TWO terminating sentinels.
  666. array->resizeToAtLeast(
  667. dstOffset + distance_to_sentinel(a_runs) + distance_to_sentinel(b_runs) + 2);
  668. SkRegionPriv::RunType* dst = &(*array)[dstOffset]; // get pointer AFTER resizing.
  669. spanRec rec;
  670. bool firstInterval = true;
  671. rec.init(a_runs, b_runs);
  672. while (!rec.done()) {
  673. rec.next();
  674. int left = rec.fLeft;
  675. int rite = rec.fRite;
  676. // add left,rite to our dst buffer (checking for coincidence
  677. if ((unsigned)(rec.fInside - min) <= (unsigned)(max - min) &&
  678. left < rite) { // skip if equal
  679. if (firstInterval || *(dst - 1) < left) {
  680. *dst++ = (SkRegionPriv::RunType)(left);
  681. *dst++ = (SkRegionPriv::RunType)(rite);
  682. firstInterval = false;
  683. } else {
  684. // update the right edge
  685. *(dst - 1) = (SkRegionPriv::RunType)(rite);
  686. }
  687. }
  688. }
  689. SkASSERT(dst < &(*array)[array->count() - 1]);
  690. *dst++ = SkRegion_kRunTypeSentinel;
  691. return dst - &(*array)[0];
  692. }
  693. #if defined _WIN32
  694. #pragma warning ( pop )
  695. #endif
  696. static const struct {
  697. uint8_t fMin;
  698. uint8_t fMax;
  699. } gOpMinMax[] = {
  700. { 1, 1 }, // Difference
  701. { 3, 3 }, // Intersection
  702. { 1, 3 }, // Union
  703. { 1, 2 } // XOR
  704. };
  705. // need to ensure that the op enum lines up with our minmax array
  706. static_assert(0 == SkRegion::kDifference_Op, "");
  707. static_assert(1 == SkRegion::kIntersect_Op, "");
  708. static_assert(2 == SkRegion::kUnion_Op, "");
  709. static_assert(3 == SkRegion::kXOR_Op, "");
  710. class RgnOper {
  711. public:
  712. RgnOper(int top, RunArray* array, SkRegion::Op op)
  713. : fMin(gOpMinMax[op].fMin)
  714. , fMax(gOpMinMax[op].fMax)
  715. , fArray(array)
  716. , fTop((SkRegionPriv::RunType)top) // just a first guess, we might update this
  717. { SkASSERT((unsigned)op <= 3); }
  718. void addSpan(int bottom, const SkRegionPriv::RunType a_runs[],
  719. const SkRegionPriv::RunType b_runs[]) {
  720. // skip X values and slots for the next Y+intervalCount
  721. int start = fPrevDst + fPrevLen + 2;
  722. // start points to beginning of dst interval
  723. int stop = operate_on_span(a_runs, b_runs, fArray, start, fMin, fMax);
  724. size_t len = SkToSizeT(stop - start);
  725. SkASSERT(len >= 1 && (len & 1) == 1);
  726. SkASSERT(SkRegion_kRunTypeSentinel == (*fArray)[stop - 1]);
  727. // Assert memcmp won't exceed fArray->count().
  728. SkASSERT(fArray->count() >= SkToInt(start + len - 1));
  729. if (fPrevLen == len &&
  730. (1 == len || !memcmp(&(*fArray)[fPrevDst],
  731. &(*fArray)[start],
  732. (len - 1) * sizeof(SkRegionPriv::RunType)))) {
  733. // update Y value
  734. (*fArray)[fPrevDst - 2] = (SkRegionPriv::RunType)bottom;
  735. } else { // accept the new span
  736. if (len == 1 && fPrevLen == 0) {
  737. fTop = (SkRegionPriv::RunType)bottom; // just update our bottom
  738. } else {
  739. (*fArray)[start - 2] = (SkRegionPriv::RunType)bottom;
  740. (*fArray)[start - 1] = SkToS32(len >> 1);
  741. fPrevDst = start;
  742. fPrevLen = len;
  743. }
  744. }
  745. }
  746. int flush() {
  747. (*fArray)[fStartDst] = fTop;
  748. // Previously reserved enough for TWO sentinals.
  749. SkASSERT(fArray->count() > SkToInt(fPrevDst + fPrevLen));
  750. (*fArray)[fPrevDst + fPrevLen] = SkRegion_kRunTypeSentinel;
  751. return (int)(fPrevDst - fStartDst + fPrevLen + 1);
  752. }
  753. bool isEmpty() const { return 0 == fPrevLen; }
  754. uint8_t fMin, fMax;
  755. private:
  756. RunArray* fArray;
  757. int fStartDst = 0;
  758. int fPrevDst = 1;
  759. size_t fPrevLen = 0; // will never match a length from operate_on_span
  760. SkRegionPriv::RunType fTop;
  761. };
  762. // want a unique value to signal that we exited due to quickExit
  763. #define QUICK_EXIT_TRUE_COUNT (-1)
  764. static int operate(const SkRegionPriv::RunType a_runs[],
  765. const SkRegionPriv::RunType b_runs[],
  766. RunArray* dst,
  767. SkRegion::Op op,
  768. bool quickExit) {
  769. const SkRegionPriv::RunType gEmptyScanline[] = {
  770. 0, // dummy bottom value
  771. 0, // zero intervals
  772. SkRegion_kRunTypeSentinel,
  773. // just need a 2nd value, since spanRec.init() reads 2 values, even
  774. // though if the first value is the sentinel, it ignores the 2nd value.
  775. // w/o the 2nd value here, we might read uninitialized memory.
  776. // This happens when we are using gSentinel, which is pointing at
  777. // our sentinel value.
  778. 0
  779. };
  780. const SkRegionPriv::RunType* const gSentinel = &gEmptyScanline[2];
  781. int a_top = *a_runs++;
  782. int a_bot = *a_runs++;
  783. int b_top = *b_runs++;
  784. int b_bot = *b_runs++;
  785. a_runs += 1; // skip the intervalCount;
  786. b_runs += 1; // skip the intervalCount;
  787. // Now a_runs and b_runs to their intervals (or sentinel)
  788. assert_sentinel(a_top, false);
  789. assert_sentinel(a_bot, false);
  790. assert_sentinel(b_top, false);
  791. assert_sentinel(b_bot, false);
  792. RgnOper oper(SkMin32(a_top, b_top), dst, op);
  793. int prevBot = SkRegion_kRunTypeSentinel; // so we fail the first test
  794. while (a_bot < SkRegion_kRunTypeSentinel ||
  795. b_bot < SkRegion_kRunTypeSentinel) {
  796. int top, bot SK_INIT_TO_AVOID_WARNING;
  797. const SkRegionPriv::RunType* run0 = gSentinel;
  798. const SkRegionPriv::RunType* run1 = gSentinel;
  799. bool a_flush = false;
  800. bool b_flush = false;
  801. if (a_top < b_top) {
  802. top = a_top;
  803. run0 = a_runs;
  804. if (a_bot <= b_top) { // [...] <...>
  805. bot = a_bot;
  806. a_flush = true;
  807. } else { // [...<..]...> or [...<...>...]
  808. bot = a_top = b_top;
  809. }
  810. } else if (b_top < a_top) {
  811. top = b_top;
  812. run1 = b_runs;
  813. if (b_bot <= a_top) { // [...] <...>
  814. bot = b_bot;
  815. b_flush = true;
  816. } else { // [...<..]...> or [...<...>...]
  817. bot = b_top = a_top;
  818. }
  819. } else { // a_top == b_top
  820. top = a_top; // or b_top
  821. run0 = a_runs;
  822. run1 = b_runs;
  823. if (a_bot <= b_bot) {
  824. bot = b_top = a_bot;
  825. a_flush = true;
  826. }
  827. if (b_bot <= a_bot) {
  828. bot = a_top = b_bot;
  829. b_flush = true;
  830. }
  831. }
  832. if (top > prevBot) {
  833. oper.addSpan(top, gSentinel, gSentinel);
  834. }
  835. oper.addSpan(bot, run0, run1);
  836. if (quickExit && !oper.isEmpty()) {
  837. return QUICK_EXIT_TRUE_COUNT;
  838. }
  839. if (a_flush) {
  840. a_runs = skip_intervals(a_runs);
  841. a_top = a_bot;
  842. a_bot = *a_runs++;
  843. a_runs += 1; // skip uninitialized intervalCount
  844. if (a_bot == SkRegion_kRunTypeSentinel) {
  845. a_top = a_bot;
  846. }
  847. }
  848. if (b_flush) {
  849. b_runs = skip_intervals(b_runs);
  850. b_top = b_bot;
  851. b_bot = *b_runs++;
  852. b_runs += 1; // skip uninitialized intervalCount
  853. if (b_bot == SkRegion_kRunTypeSentinel) {
  854. b_top = b_bot;
  855. }
  856. }
  857. prevBot = bot;
  858. }
  859. return oper.flush();
  860. }
  861. ///////////////////////////////////////////////////////////////////////////////
  862. /* Given count RunTypes in a complex region, return the worst case number of
  863. logical intervals that represents (i.e. number of rects that would be
  864. returned from the iterator).
  865. We could just return count/2, since there must be at least 2 values per
  866. interval, but we can first trim off the const overhead of the initial TOP
  867. value, plus the final BOTTOM + 2 sentinels.
  868. */
  869. #if 0 // UNUSED
  870. static int count_to_intervals(int count) {
  871. SkASSERT(count >= 6); // a single rect is 6 values
  872. return (count - 4) >> 1;
  873. }
  874. #endif
  875. static bool setEmptyCheck(SkRegion* result) {
  876. return result ? result->setEmpty() : false;
  877. }
  878. static bool setRectCheck(SkRegion* result, const SkIRect& rect) {
  879. return result ? result->setRect(rect) : !rect.isEmpty();
  880. }
  881. static bool setRegionCheck(SkRegion* result, const SkRegion& rgn) {
  882. return result ? result->setRegion(rgn) : !rgn.isEmpty();
  883. }
  884. bool SkRegion::Oper(const SkRegion& rgnaOrig, const SkRegion& rgnbOrig, Op op,
  885. SkRegion* result) {
  886. SkASSERT((unsigned)op < kOpCount);
  887. if (kReplace_Op == op) {
  888. return setRegionCheck(result, rgnbOrig);
  889. }
  890. // swith to using pointers, so we can swap them as needed
  891. const SkRegion* rgna = &rgnaOrig;
  892. const SkRegion* rgnb = &rgnbOrig;
  893. // after this point, do not refer to rgnaOrig or rgnbOrig!!!
  894. // collaps difference and reverse-difference into just difference
  895. if (kReverseDifference_Op == op) {
  896. using std::swap;
  897. swap(rgna, rgnb);
  898. op = kDifference_Op;
  899. }
  900. SkIRect bounds;
  901. bool a_empty = rgna->isEmpty();
  902. bool b_empty = rgnb->isEmpty();
  903. bool a_rect = rgna->isRect();
  904. bool b_rect = rgnb->isRect();
  905. switch (op) {
  906. case kDifference_Op:
  907. if (a_empty) {
  908. return setEmptyCheck(result);
  909. }
  910. if (b_empty || !SkIRect::IntersectsNoEmptyCheck(rgna->fBounds,
  911. rgnb->fBounds)) {
  912. return setRegionCheck(result, *rgna);
  913. }
  914. if (b_rect && rgnb->fBounds.containsNoEmptyCheck(rgna->fBounds)) {
  915. return setEmptyCheck(result);
  916. }
  917. break;
  918. case kIntersect_Op:
  919. if ((a_empty | b_empty)
  920. || !bounds.intersect(rgna->fBounds, rgnb->fBounds)) {
  921. return setEmptyCheck(result);
  922. }
  923. if (a_rect & b_rect) {
  924. return setRectCheck(result, bounds);
  925. }
  926. if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
  927. return setRegionCheck(result, *rgnb);
  928. }
  929. if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
  930. return setRegionCheck(result, *rgna);
  931. }
  932. break;
  933. case kUnion_Op:
  934. if (a_empty) {
  935. return setRegionCheck(result, *rgnb);
  936. }
  937. if (b_empty) {
  938. return setRegionCheck(result, *rgna);
  939. }
  940. if (a_rect && rgna->fBounds.contains(rgnb->fBounds)) {
  941. return setRegionCheck(result, *rgna);
  942. }
  943. if (b_rect && rgnb->fBounds.contains(rgna->fBounds)) {
  944. return setRegionCheck(result, *rgnb);
  945. }
  946. break;
  947. case kXOR_Op:
  948. if (a_empty) {
  949. return setRegionCheck(result, *rgnb);
  950. }
  951. if (b_empty) {
  952. return setRegionCheck(result, *rgna);
  953. }
  954. break;
  955. default:
  956. SkDEBUGFAIL("unknown region op");
  957. return false;
  958. }
  959. RunType tmpA[kRectRegionRuns];
  960. RunType tmpB[kRectRegionRuns];
  961. int a_intervals, b_intervals;
  962. const RunType* a_runs = rgna->getRuns(tmpA, &a_intervals);
  963. const RunType* b_runs = rgnb->getRuns(tmpB, &b_intervals);
  964. RunArray array;
  965. int count = operate(a_runs, b_runs, &array, op, nullptr == result);
  966. SkASSERT(count <= array.count());
  967. if (result) {
  968. SkASSERT(count >= 0);
  969. return result->setRuns(&array[0], count);
  970. } else {
  971. return (QUICK_EXIT_TRUE_COUNT == count) || !isRunCountEmpty(count);
  972. }
  973. }
  974. bool SkRegion::op(const SkRegion& rgna, const SkRegion& rgnb, Op op) {
  975. SkDEBUGCODE(SkRegionPriv::Validate(*this));
  976. return SkRegion::Oper(rgna, rgnb, op, this);
  977. }
  978. ///////////////////////////////////////////////////////////////////////////////
  979. #include "src/core/SkBuffer.h"
  980. size_t SkRegion::writeToMemory(void* storage) const {
  981. if (nullptr == storage) {
  982. size_t size = sizeof(int32_t); // -1 (empty), 0 (rect), runCount
  983. if (!this->isEmpty()) {
  984. size += sizeof(fBounds);
  985. if (this->isComplex()) {
  986. size += 2 * sizeof(int32_t); // ySpanCount + intervalCount
  987. size += fRunHead->fRunCount * sizeof(RunType);
  988. }
  989. }
  990. return size;
  991. }
  992. SkWBuffer buffer(storage);
  993. if (this->isEmpty()) {
  994. buffer.write32(-1);
  995. } else {
  996. bool isRect = this->isRect();
  997. buffer.write32(isRect ? 0 : fRunHead->fRunCount);
  998. buffer.write(&fBounds, sizeof(fBounds));
  999. if (!isRect) {
  1000. buffer.write32(fRunHead->getYSpanCount());
  1001. buffer.write32(fRunHead->getIntervalCount());
  1002. buffer.write(fRunHead->readonly_runs(),
  1003. fRunHead->fRunCount * sizeof(RunType));
  1004. }
  1005. }
  1006. return buffer.pos();
  1007. }
  1008. static bool validate_run_count(int ySpanCount, int intervalCount, int runCount) {
  1009. // return 2 + 3 * ySpanCount + 2 * intervalCount;
  1010. if (ySpanCount < 1 || intervalCount < 2) {
  1011. return false;
  1012. }
  1013. SkSafeMath safeMath;
  1014. int sum = 2;
  1015. sum = safeMath.addInt(sum, ySpanCount);
  1016. sum = safeMath.addInt(sum, ySpanCount);
  1017. sum = safeMath.addInt(sum, ySpanCount);
  1018. sum = safeMath.addInt(sum, intervalCount);
  1019. sum = safeMath.addInt(sum, intervalCount);
  1020. return safeMath && sum == runCount;
  1021. }
  1022. // Validate that a memory sequence is a valid region.
  1023. // Try to check all possible errors.
  1024. // never read beyond &runs[runCount-1].
  1025. static bool validate_run(const int32_t* runs,
  1026. int runCount,
  1027. const SkIRect& givenBounds,
  1028. int32_t ySpanCount,
  1029. int32_t intervalCount) {
  1030. // Region Layout:
  1031. // Top ( Bottom Span_Interval_Count ( Left Right )* Sentinel )+ Sentinel
  1032. if (!validate_run_count(SkToInt(ySpanCount), SkToInt(intervalCount), runCount)) {
  1033. return false;
  1034. }
  1035. SkASSERT(runCount >= 7); // 7==SkRegion::kRectRegionRuns
  1036. // quick sanity check:
  1037. if (runs[runCount - 1] != SkRegion_kRunTypeSentinel ||
  1038. runs[runCount - 2] != SkRegion_kRunTypeSentinel) {
  1039. return false;
  1040. }
  1041. const int32_t* const end = runs + runCount;
  1042. SkIRect bounds = {0, 0, 0 ,0}; // calulated bounds
  1043. SkIRect rect = {0, 0, 0, 0}; // current rect
  1044. rect.fTop = *runs++;
  1045. if (rect.fTop == SkRegion_kRunTypeSentinel) {
  1046. return false; // no rect can contain SkRegion_kRunTypeSentinel
  1047. }
  1048. if (rect.fTop != givenBounds.fTop) {
  1049. return false; // Must not begin with empty span that does not contribute to bounds.
  1050. }
  1051. do {
  1052. --ySpanCount;
  1053. if (ySpanCount < 0) {
  1054. return false; // too many yspans
  1055. }
  1056. rect.fBottom = *runs++;
  1057. if (rect.fBottom == SkRegion_kRunTypeSentinel) {
  1058. return false;
  1059. }
  1060. if (rect.fBottom > givenBounds.fBottom) {
  1061. return false; // Must not end with empty span that does not contribute to bounds.
  1062. }
  1063. if (rect.fBottom <= rect.fTop) {
  1064. return false; // y-intervals must be ordered; rects must be non-empty.
  1065. }
  1066. int32_t xIntervals = *runs++;
  1067. SkASSERT(runs < end);
  1068. if (xIntervals < 0 || xIntervals > intervalCount || runs + 1 + 2 * xIntervals > end) {
  1069. return false;
  1070. }
  1071. intervalCount -= xIntervals;
  1072. bool firstInterval = true;
  1073. int32_t lastRight = 0; // check that x-intervals are distinct and ordered.
  1074. while (xIntervals-- > 0) {
  1075. rect.fLeft = *runs++;
  1076. rect.fRight = *runs++;
  1077. if (rect.fLeft == SkRegion_kRunTypeSentinel ||
  1078. rect.fRight == SkRegion_kRunTypeSentinel ||
  1079. rect.fLeft >= rect.fRight || // check non-empty rect
  1080. (!firstInterval && rect.fLeft <= lastRight)) {
  1081. return false;
  1082. }
  1083. lastRight = rect.fRight;
  1084. firstInterval = false;
  1085. bounds.join(rect);
  1086. }
  1087. if (*runs++ != SkRegion_kRunTypeSentinel) {
  1088. return false; // required check sentinal.
  1089. }
  1090. rect.fTop = rect.fBottom;
  1091. SkASSERT(runs < end);
  1092. } while (*runs != SkRegion_kRunTypeSentinel);
  1093. ++runs;
  1094. if (ySpanCount != 0 || intervalCount != 0 || givenBounds != bounds) {
  1095. return false;
  1096. }
  1097. SkASSERT(runs == end); // if ySpanCount && intervalCount are right, must be correct length.
  1098. return true;
  1099. }
  1100. size_t SkRegion::readFromMemory(const void* storage, size_t length) {
  1101. SkRBuffer buffer(storage, length);
  1102. SkRegion tmp;
  1103. int32_t count;
  1104. // Serialized Region Format:
  1105. // Empty:
  1106. // -1
  1107. // Simple Rect:
  1108. // 0 LEFT TOP RIGHT BOTTOM
  1109. // Complex Region:
  1110. // COUNT LEFT TOP RIGHT BOTTOM Y_SPAN_COUNT TOTAL_INTERVAL_COUNT [RUNS....]
  1111. if (!buffer.readS32(&count) || count < -1) {
  1112. return 0;
  1113. }
  1114. if (count >= 0) {
  1115. if (!buffer.read(&tmp.fBounds, sizeof(tmp.fBounds)) || tmp.fBounds.isEmpty()) {
  1116. return 0; // Short buffer or bad bounds for non-empty region; report failure.
  1117. }
  1118. if (count == 0) {
  1119. tmp.fRunHead = SkRegion_gRectRunHeadPtr;
  1120. } else {
  1121. int32_t ySpanCount, intervalCount;
  1122. if (!buffer.readS32(&ySpanCount) ||
  1123. !buffer.readS32(&intervalCount) ||
  1124. buffer.available() < count * sizeof(int32_t)) {
  1125. return 0;
  1126. }
  1127. if (!validate_run((const int32_t*)((const char*)storage + buffer.pos()), count,
  1128. tmp.fBounds, ySpanCount, intervalCount)) {
  1129. return 0; // invalid runs, don't even allocate
  1130. }
  1131. tmp.allocateRuns(count, ySpanCount, intervalCount);
  1132. SkASSERT(tmp.isComplex());
  1133. SkAssertResult(buffer.read(tmp.fRunHead->writable_runs(), count * sizeof(int32_t)));
  1134. }
  1135. }
  1136. SkASSERT(tmp.isValid());
  1137. SkASSERT(buffer.isValid());
  1138. this->swap(tmp);
  1139. return buffer.pos();
  1140. }
  1141. ///////////////////////////////////////////////////////////////////////////////
  1142. bool SkRegion::isValid() const {
  1143. if (this->isEmpty()) {
  1144. return fBounds == SkIRect{0, 0, 0, 0};
  1145. }
  1146. if (fBounds.isEmpty()) {
  1147. return false;
  1148. }
  1149. if (this->isRect()) {
  1150. return true;
  1151. }
  1152. return fRunHead && fRunHead->fRefCnt > 0 &&
  1153. validate_run(fRunHead->readonly_runs(), fRunHead->fRunCount, fBounds,
  1154. fRunHead->getYSpanCount(), fRunHead->getIntervalCount());
  1155. }
  1156. #ifdef SK_DEBUG
  1157. void SkRegionPriv::Validate(const SkRegion& rgn) { SkASSERT(rgn.isValid()); }
  1158. void SkRegion::dump() const {
  1159. if (this->isEmpty()) {
  1160. SkDebugf(" rgn: empty\n");
  1161. } else {
  1162. SkDebugf(" rgn: [%d %d %d %d]", fBounds.fLeft, fBounds.fTop, fBounds.fRight, fBounds.fBottom);
  1163. if (this->isComplex()) {
  1164. const RunType* runs = fRunHead->readonly_runs();
  1165. for (int i = 0; i < fRunHead->fRunCount; i++)
  1166. SkDebugf(" %d", runs[i]);
  1167. }
  1168. SkDebugf("\n");
  1169. }
  1170. }
  1171. #endif
  1172. ///////////////////////////////////////////////////////////////////////////////
  1173. SkRegion::Iterator::Iterator(const SkRegion& rgn) {
  1174. this->reset(rgn);
  1175. }
  1176. bool SkRegion::Iterator::rewind() {
  1177. if (fRgn) {
  1178. this->reset(*fRgn);
  1179. return true;
  1180. }
  1181. return false;
  1182. }
  1183. void SkRegion::Iterator::reset(const SkRegion& rgn) {
  1184. fRgn = &rgn;
  1185. if (rgn.isEmpty()) {
  1186. fDone = true;
  1187. } else {
  1188. fDone = false;
  1189. if (rgn.isRect()) {
  1190. fRect = rgn.fBounds;
  1191. fRuns = nullptr;
  1192. } else {
  1193. fRuns = rgn.fRunHead->readonly_runs();
  1194. fRect.set(fRuns[3], fRuns[0], fRuns[4], fRuns[1]);
  1195. fRuns += 5;
  1196. // Now fRuns points to the 2nd interval (or x-sentinel)
  1197. }
  1198. }
  1199. }
  1200. void SkRegion::Iterator::next() {
  1201. if (fDone) {
  1202. return;
  1203. }
  1204. if (fRuns == nullptr) { // rect case
  1205. fDone = true;
  1206. return;
  1207. }
  1208. const RunType* runs = fRuns;
  1209. if (runs[0] < SkRegion_kRunTypeSentinel) { // valid X value
  1210. fRect.fLeft = runs[0];
  1211. fRect.fRight = runs[1];
  1212. runs += 2;
  1213. } else { // we're at the end of a line
  1214. runs += 1;
  1215. if (runs[0] < SkRegion_kRunTypeSentinel) { // valid Y value
  1216. int intervals = runs[1];
  1217. if (0 == intervals) { // empty line
  1218. fRect.fTop = runs[0];
  1219. runs += 3;
  1220. } else {
  1221. fRect.fTop = fRect.fBottom;
  1222. }
  1223. fRect.fBottom = runs[0];
  1224. assert_sentinel(runs[2], false);
  1225. assert_sentinel(runs[3], false);
  1226. fRect.fLeft = runs[2];
  1227. fRect.fRight = runs[3];
  1228. runs += 4;
  1229. } else { // end of rgn
  1230. fDone = true;
  1231. }
  1232. }
  1233. fRuns = runs;
  1234. }
  1235. SkRegion::Cliperator::Cliperator(const SkRegion& rgn, const SkIRect& clip)
  1236. : fIter(rgn), fClip(clip), fDone(true) {
  1237. const SkIRect& r = fIter.rect();
  1238. while (!fIter.done()) {
  1239. if (r.fTop >= clip.fBottom) {
  1240. break;
  1241. }
  1242. if (fRect.intersect(clip, r)) {
  1243. fDone = false;
  1244. break;
  1245. }
  1246. fIter.next();
  1247. }
  1248. }
  1249. void SkRegion::Cliperator::next() {
  1250. if (fDone) {
  1251. return;
  1252. }
  1253. const SkIRect& r = fIter.rect();
  1254. fDone = true;
  1255. fIter.next();
  1256. while (!fIter.done()) {
  1257. if (r.fTop >= fClip.fBottom) {
  1258. break;
  1259. }
  1260. if (fRect.intersect(fClip, r)) {
  1261. fDone = false;
  1262. break;
  1263. }
  1264. fIter.next();
  1265. }
  1266. }
  1267. ///////////////////////////////////////////////////////////////////////////////
  1268. SkRegion::Spanerator::Spanerator(const SkRegion& rgn, int y, int left,
  1269. int right) {
  1270. SkDEBUGCODE(SkRegionPriv::Validate(rgn));
  1271. const SkIRect& r = rgn.getBounds();
  1272. fDone = true;
  1273. if (!rgn.isEmpty() && y >= r.fTop && y < r.fBottom &&
  1274. right > r.fLeft && left < r.fRight) {
  1275. if (rgn.isRect()) {
  1276. if (left < r.fLeft) {
  1277. left = r.fLeft;
  1278. }
  1279. if (right > r.fRight) {
  1280. right = r.fRight;
  1281. }
  1282. fLeft = left;
  1283. fRight = right;
  1284. fRuns = nullptr; // means we're a rect, not a rgn
  1285. fDone = false;
  1286. } else {
  1287. const SkRegion::RunType* runs = rgn.fRunHead->findScanline(y);
  1288. runs += 2; // skip Bottom and IntervalCount
  1289. for (;;) {
  1290. // runs[0..1] is to the right of the span, so we're done
  1291. if (runs[0] >= right) {
  1292. break;
  1293. }
  1294. // runs[0..1] is to the left of the span, so continue
  1295. if (runs[1] <= left) {
  1296. runs += 2;
  1297. continue;
  1298. }
  1299. // runs[0..1] intersects the span
  1300. fRuns = runs;
  1301. fLeft = left;
  1302. fRight = right;
  1303. fDone = false;
  1304. break;
  1305. }
  1306. }
  1307. }
  1308. }
  1309. bool SkRegion::Spanerator::next(int* left, int* right) {
  1310. if (fDone) {
  1311. return false;
  1312. }
  1313. if (fRuns == nullptr) { // we're a rect
  1314. fDone = true; // ok, now we're done
  1315. if (left) {
  1316. *left = fLeft;
  1317. }
  1318. if (right) {
  1319. *right = fRight;
  1320. }
  1321. return true; // this interval is legal
  1322. }
  1323. const SkRegion::RunType* runs = fRuns;
  1324. if (runs[0] >= fRight) {
  1325. fDone = true;
  1326. return false;
  1327. }
  1328. SkASSERT(runs[1] > fLeft);
  1329. if (left) {
  1330. *left = SkMax32(fLeft, runs[0]);
  1331. }
  1332. if (right) {
  1333. *right = SkMin32(fRight, runs[1]);
  1334. }
  1335. fRuns = runs + 2;
  1336. return true;
  1337. }
  1338. ///////////////////////////////////////////////////////////////////////////////////////////////////
  1339. static void visit_pairs(int pairCount, int y, const int32_t pairs[],
  1340. const std::function<void(const SkIRect&)>& visitor) {
  1341. for (int i = 0; i < pairCount; ++i) {
  1342. visitor({ pairs[0], y, pairs[1], y + 1 });
  1343. pairs += 2;
  1344. }
  1345. }
  1346. void SkRegionPriv::VisitSpans(const SkRegion& rgn,
  1347. const std::function<void(const SkIRect&)>& visitor) {
  1348. if (rgn.isEmpty()) {
  1349. return;
  1350. }
  1351. if (rgn.isRect()) {
  1352. visitor(rgn.getBounds());
  1353. } else {
  1354. const int32_t* p = rgn.fRunHead->readonly_runs();
  1355. int32_t top = *p++;
  1356. int32_t bot = *p++;
  1357. do {
  1358. int pairCount = *p++;
  1359. if (pairCount == 1) {
  1360. visitor({ p[0], top, p[1], bot });
  1361. p += 2;
  1362. } else if (pairCount > 1) {
  1363. // we have to loop repeated in Y, sending each interval in Y -> X order
  1364. for (int y = top; y < bot; ++y) {
  1365. visit_pairs(pairCount, y, p, visitor);
  1366. }
  1367. p += pairCount * 2;
  1368. }
  1369. assert_sentinel(*p, true);
  1370. p += 1; // skip sentinel
  1371. // read next bottom or sentinel
  1372. top = bot;
  1373. bot = *p++;
  1374. } while (!SkRegionValueIsSentinel(bot));
  1375. }
  1376. }