SkRegionPriv.h 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259
  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. #ifndef SkRegionPriv_DEFINED
  8. #define SkRegionPriv_DEFINED
  9. #include "include/core/SkRegion.h"
  10. #include "include/private/SkMalloc.h"
  11. #include "include/private/SkTo.h"
  12. #include <atomic>
  13. #include <functional>
  14. class SkRegionPriv {
  15. public:
  16. static constexpr int kRunTypeSentinel = 0x7FFFFFFF;
  17. typedef SkRegion::RunType RunType;
  18. typedef SkRegion::RunHead RunHead;
  19. // Call the function with each span, in Y -> X ascending order.
  20. // We pass a rect, but we will still ensure the span Y->X ordering, so often the height
  21. // of the rect may be 1. It should never be empty.
  22. static void VisitSpans(const SkRegion& rgn, const std::function<void(const SkIRect&)>&);
  23. #ifdef SK_DEBUG
  24. static void Validate(const SkRegion& rgn);
  25. #endif
  26. };
  27. static constexpr int SkRegion_kRunTypeSentinel = 0x7FFFFFFF;
  28. inline bool SkRegionValueIsSentinel(int32_t value) {
  29. return value == (int32_t)SkRegion_kRunTypeSentinel;
  30. }
  31. #define assert_sentinel(value, isSentinel) \
  32. SkASSERT(SkRegionValueIsSentinel(value) == isSentinel)
  33. #ifdef SK_DEBUG
  34. // Given the first interval (just past the interval-count), compute the
  35. // interval count, by search for the x-sentinel
  36. //
  37. static int compute_intervalcount(const SkRegionPriv::RunType runs[]) {
  38. const SkRegionPriv::RunType* curr = runs;
  39. while (*curr < SkRegion_kRunTypeSentinel) {
  40. SkASSERT(curr[0] < curr[1]);
  41. SkASSERT(curr[1] < SkRegion_kRunTypeSentinel);
  42. curr += 2;
  43. }
  44. return SkToInt((curr - runs) >> 1);
  45. }
  46. #endif
  47. struct SkRegion::RunHead {
  48. private:
  49. public:
  50. std::atomic<int32_t> fRefCnt;
  51. int32_t fRunCount;
  52. /**
  53. * Number of spans with different Y values. This does not count the initial
  54. * Top value, nor does it count the final Y-Sentinel value. In the logical
  55. * case of a rectangle, this would return 1, and an empty region would
  56. * return 0.
  57. */
  58. int getYSpanCount() const {
  59. return fYSpanCount;
  60. }
  61. /**
  62. * Number of intervals in the entire region. This equals the number of
  63. * rects that would be returned by the Iterator. In the logical case of
  64. * a rect, this would return 1, and an empty region would return 0.
  65. */
  66. int getIntervalCount() const {
  67. return fIntervalCount;
  68. }
  69. static RunHead* Alloc(int count) {
  70. if (count < SkRegion::kRectRegionRuns) {
  71. return nullptr;
  72. }
  73. const int64_t size = sk_64_mul(count, sizeof(RunType)) + sizeof(RunHead);
  74. if (count < 0 || !SkTFitsIn<int32_t>(size)) { SK_ABORT("Invalid Size"); }
  75. RunHead* head = (RunHead*)sk_malloc_throw(size);
  76. head->fRefCnt = 1;
  77. head->fRunCount = count;
  78. // these must be filled in later, otherwise we will be invalid
  79. head->fYSpanCount = 0;
  80. head->fIntervalCount = 0;
  81. return head;
  82. }
  83. static RunHead* Alloc(int count, int yspancount, int intervalCount) {
  84. if (yspancount <= 0 || intervalCount <= 1) {
  85. return nullptr;
  86. }
  87. RunHead* head = Alloc(count);
  88. if (!head) {
  89. return nullptr;
  90. }
  91. head->fYSpanCount = yspancount;
  92. head->fIntervalCount = intervalCount;
  93. return head;
  94. }
  95. SkRegion::RunType* writable_runs() {
  96. SkASSERT(fRefCnt == 1);
  97. return (SkRegion::RunType*)(this + 1);
  98. }
  99. const SkRegion::RunType* readonly_runs() const {
  100. return (const SkRegion::RunType*)(this + 1);
  101. }
  102. RunHead* ensureWritable() {
  103. RunHead* writable = this;
  104. if (fRefCnt > 1) {
  105. // We need to alloc & copy the current region before decrease
  106. // the refcount because it could be freed in the meantime.
  107. writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
  108. memcpy(writable->writable_runs(), this->readonly_runs(),
  109. fRunCount * sizeof(RunType));
  110. // fRefCount might have changed since we last checked.
  111. // If we own the last reference at this point, we need to
  112. // free the memory.
  113. if (--fRefCnt == 0) {
  114. sk_free(this);
  115. }
  116. }
  117. return writable;
  118. }
  119. /**
  120. * Given a scanline (including its Bottom value at runs[0]), return the next
  121. * scanline. Asserts that there is one (i.e. runs[0] < Sentinel)
  122. */
  123. static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
  124. // we are not the Y Sentinel
  125. SkASSERT(runs[0] < SkRegion_kRunTypeSentinel);
  126. const int intervals = runs[1];
  127. SkASSERT(runs[2 + intervals * 2] == SkRegion_kRunTypeSentinel);
  128. #ifdef SK_DEBUG
  129. {
  130. int n = compute_intervalcount(&runs[2]);
  131. SkASSERT(n == intervals);
  132. }
  133. #endif
  134. // skip the entire line [B N [L R] S]
  135. runs += 1 + 1 + intervals * 2 + 1;
  136. return const_cast<SkRegion::RunType*>(runs);
  137. }
  138. /**
  139. * Return the scanline that contains the Y value. This requires that the Y
  140. * value is already known to be contained within the bounds of the region,
  141. * and so this routine never returns nullptr.
  142. *
  143. * It returns the beginning of the scanline, starting with its Bottom value.
  144. */
  145. SkRegion::RunType* findScanline(int y) const {
  146. const RunType* runs = this->readonly_runs();
  147. // if the top-check fails, we didn't do a quick check on the bounds
  148. SkASSERT(y >= runs[0]);
  149. runs += 1; // skip top-Y
  150. for (;;) {
  151. int bottom = runs[0];
  152. // If we hit this, we've walked off the region, and our bounds check
  153. // failed.
  154. SkASSERT(bottom < SkRegion_kRunTypeSentinel);
  155. if (y < bottom) {
  156. break;
  157. }
  158. runs = SkipEntireScanline(runs);
  159. }
  160. return const_cast<SkRegion::RunType*>(runs);
  161. }
  162. // Copy src runs into us, computing interval counts and bounds along the way
  163. void computeRunBounds(SkIRect* bounds) {
  164. RunType* runs = this->writable_runs();
  165. bounds->fTop = *runs++;
  166. int bot;
  167. int ySpanCount = 0;
  168. int intervalCount = 0;
  169. int left = SK_MaxS32;
  170. int rite = SK_MinS32;
  171. do {
  172. bot = *runs++;
  173. SkASSERT(bot < SkRegion_kRunTypeSentinel);
  174. ySpanCount += 1;
  175. const int intervals = *runs++;
  176. SkASSERT(intervals >= 0);
  177. SkASSERT(intervals < SkRegion_kRunTypeSentinel);
  178. if (intervals > 0) {
  179. #ifdef SK_DEBUG
  180. {
  181. int n = compute_intervalcount(runs);
  182. SkASSERT(n == intervals);
  183. }
  184. #endif
  185. RunType L = runs[0];
  186. SkASSERT(L < SkRegion_kRunTypeSentinel);
  187. if (left > L) {
  188. left = L;
  189. }
  190. runs += intervals * 2;
  191. RunType R = runs[-1];
  192. SkASSERT(R < SkRegion_kRunTypeSentinel);
  193. if (rite < R) {
  194. rite = R;
  195. }
  196. intervalCount += intervals;
  197. }
  198. SkASSERT(SkRegion_kRunTypeSentinel == *runs);
  199. runs += 1; // skip x-sentinel
  200. // test Y-sentinel
  201. } while (SkRegion_kRunTypeSentinel > *runs);
  202. #ifdef SK_DEBUG
  203. // +1 to skip the last Y-sentinel
  204. int runCount = SkToInt(runs - this->writable_runs() + 1);
  205. SkASSERT(runCount == fRunCount);
  206. #endif
  207. fYSpanCount = ySpanCount;
  208. fIntervalCount = intervalCount;
  209. bounds->fLeft = left;
  210. bounds->fRight = rite;
  211. bounds->fBottom = bot;
  212. }
  213. private:
  214. int32_t fYSpanCount;
  215. int32_t fIntervalCount;
  216. };
  217. #endif