text: /*
   * 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 <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->setLTRB(runs[3], runs[0], runs[4], runs[1]);
      return true;
    }
    return false;
  }
  
  //////////////////////////////////////////////////////////////////////////
  
  SkRegion::SkRegion() {
    fBounds.setEmpty();
    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.setEmpty();
    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,  // fake 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(std::min(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::Intersects(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 safety 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.setLTRB(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 = std::max(fLeft, runs[0]);
    }
    if (right) {
      *right = std::min(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));
    }
  }
  