src/core/SkRegion_path.cpp - skia - Git at Google

 /*
  * 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 "SkRegionPriv.h"
 #include "SkBlitter.h"
 #include "SkScan.h"
 #include "SkTDArray.h"
 #include "SkPath.h"

 // The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so
 // we may not want to promote this to a "std" routine just yet.
 static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
     for (int i = 0; i < count; ++i) {
         if (a[i] != b[i]) {
             return false;
         }
     }
     return true;
 }

 class SkRgnBuilder : public SkBlitter {
 public:
     SkRgnBuilder();
     virtual ~SkRgnBuilder();

     // returns true if it could allocate the working storage needed
     bool init(int maxHeight, int maxTransitions, bool pathIsInverse);

     void done() {
         if (fCurrScanline != NULL) {
             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
             if (!this->collapsWithPrev()) { // flush the last line
                 fCurrScanline = fCurrScanline->nextScanline();
             }
         }
     }

     int     computeRunCount() const;
     void    copyToRect(SkIRect*) const;
     void    copyToRgn(SkRegion::RunType runs[]) const;

     virtual void blitH(int x, int y, int width);

 #ifdef SK_DEBUG
     void dump() const {
         SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
         const Scanline* line = (Scanline*)fStorage;
         while (line < fCurrScanline) {
             SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
             for (int i = 0; i < line->fXCount; i++) {
                 SkDebugf(" %d", line->firstX()[i]);
             }
             SkDebugf("\n");

             line = line->nextScanline();
         }
     }
 #endif
 private:
     /*
      *  Scanline mimics a row in the region, nearly. A row in a region is:
      *      [Bottom IntervalCount [L R]... Sentinel]
      *  while a Scanline is
      *      [LastY XCount [L R]... uninitialized]
      *  The two are the same length (which is good), but we have to transmute
      *  the scanline a little when we convert it to a region-row.
      *
      *  Potentially we could recode this to exactly match the row format, in
      *  which case copyToRgn() could be a single memcpy. Not sure that is worth
      *  the effort.
      */
     struct Scanline {
         SkRegion::RunType fLastY;
         SkRegion::RunType fXCount;

         SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
         Scanline* nextScanline() const {
             // add final +1 for the x-sentinel
             return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1);
         }
     };
     SkRegion::RunType*  fStorage;
     Scanline*           fCurrScanline;
     Scanline*           fPrevScanline;
     //  points at next avialable x[] in fCurrScanline
     SkRegion::RunType*  fCurrXPtr;
     SkRegion::RunType   fTop;           // first Y value

     int fStorageCount;

     bool collapsWithPrev() {
         if (fPrevScanline != NULL &&
             fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
             fPrevScanline->fXCount == fCurrScanline->fXCount &&
             sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
         {
             // update the height of fPrevScanline
             fPrevScanline->fLastY = fCurrScanline->fLastY;
             return true;
         }
         return false;
     }
 };

 SkRgnBuilder::SkRgnBuilder()
     : fStorage(NULL) {
 }

 SkRgnBuilder::~SkRgnBuilder() {
     sk_free(fStorage);
 }

 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
     if ((maxHeight | maxTransitions) < 0) {
         return false;
     }

     if (pathIsInverse) {
         // allow for additional X transitions to "invert" each scanline
         // [ L' ... normal transitions ... R' ]
         //
         maxTransitions += 2;
     }

     // compute the count with +1 and +3 slop for the working buffer
     int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);

     if (pathIsInverse) {
         // allow for two "empty" rows for the top and bottom
         //      [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
         count += 10;
     }

     if (count < 0 || !sk_64_isS32(count)) {
         return false;
     }
     fStorageCount = sk_64_asS32(count);

     int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
     if (size < 0 || !sk_64_isS32(size)) {
         return false;
     }

     fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
     if (NULL == fStorage) {
         return false;
     }

     fCurrScanline = NULL;    // signal empty collection
     fPrevScanline = NULL;    // signal first scanline
     return true;
 }

 void SkRgnBuilder::blitH(int x, int y, int width) {
     if (fCurrScanline == NULL) {  // first time
         fTop = (SkRegion::RunType)(y);
         fCurrScanline = (Scanline*)fStorage;
         fCurrScanline->fLastY = (SkRegion::RunType)(y);
         fCurrXPtr = fCurrScanline->firstX();
     } else {
         SkASSERT(y >= fCurrScanline->fLastY);

         if (y > fCurrScanline->fLastY) {
             // if we get here, we're done with fCurrScanline
             fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));

             int prevLastY = fCurrScanline->fLastY;
             if (!this->collapsWithPrev()) {
                 fPrevScanline = fCurrScanline;
                 fCurrScanline = fCurrScanline->nextScanline();

             }
             if (y - 1 > prevLastY) {  // insert empty run
                 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
                 fCurrScanline->fXCount = 0;
                 fCurrScanline = fCurrScanline->nextScanline();
             }
             // setup for the new curr line
             fCurrScanline->fLastY = (SkRegion::RunType)(y);
             fCurrXPtr = fCurrScanline->firstX();
         }
     }
     //  check if we should extend the current run, or add a new one
     if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
         fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
     } else {
         fCurrXPtr[0] = (SkRegion::RunType)(x);
         fCurrXPtr[1] = (SkRegion::RunType)(x + width);
         fCurrXPtr += 2;
     }
     SkASSERT(fCurrXPtr - fStorage < fStorageCount);
 }

 int SkRgnBuilder::computeRunCount() const {
     if (fCurrScanline == NULL) {
         return 0;
     }

     const SkRegion::RunType*  line = fStorage;
     const SkRegion::RunType*  stop = (const SkRegion::RunType*)fCurrScanline;

     return 2 + (int)(stop - line);
 }

 void SkRgnBuilder::copyToRect(SkIRect* r) const {
     SkASSERT(fCurrScanline != NULL);
     // A rect's scanline is [bottom intervals left right sentinel] == 5
     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);

     const Scanline* line = (const Scanline*)fStorage;
     SkASSERT(line->fXCount == 2);

     r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
 }

 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
     SkASSERT(fCurrScanline != NULL);
     SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);

     const Scanline* line = (const Scanline*)fStorage;
     const Scanline* stop = fCurrScanline;

     *runs++ = fTop;
     do {
         *runs++ = (SkRegion::RunType)(line->fLastY + 1);
         int count = line->fXCount;
         *runs++ = count >> 1;   // intervalCount
         if (count) {
             memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
             runs += count;
         }
         *runs++ = SkRegion::kRunTypeSentinel;
         line = line->nextScanline();
     } while (line < stop);
     SkASSERT(line == stop);
     *runs = SkRegion::kRunTypeSentinel;
 }

 static unsigned verb_to_initial_last_index(unsigned verb) {
     static const uint8_t gPathVerbToInitialLastIndex[] = {
         0,  //  kMove_Verb
         1,  //  kLine_Verb
         2,  //  kQuad_Verb
         2,  //  kConic_Verb
         3,  //  kCubic_Verb
         0,  //  kClose_Verb
         0   //  kDone_Verb
     };
     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
     return gPathVerbToInitialLastIndex[verb];
 }

 static unsigned verb_to_max_edges(unsigned verb) {
     static const uint8_t gPathVerbToMaxEdges[] = {
         0,  //  kMove_Verb
         1,  //  kLine_Verb
         2,  //  kQuad_VerbB
         2,  //  kConic_VerbB
         3,  //  kCubic_Verb
         0,  //  kClose_Verb
         0   //  kDone_Verb
     };
     SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
     return gPathVerbToMaxEdges[verb];
 }


 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
     SkPath::Iter    iter(path, true);
     SkPoint         pts[4];
     SkPath::Verb    verb;

     int maxEdges = 0;
     SkScalar    top = SkIntToScalar(SK_MaxS16);
     SkScalar    bot = SkIntToScalar(SK_MinS16);

     while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
         maxEdges += verb_to_max_edges(verb);

         int lastIndex = verb_to_initial_last_index(verb);
         if (lastIndex > 0) {
             for (int i = 1; i <= lastIndex; i++) {
                 if (top > pts[i].fY) {
                     top = pts[i].fY;
                 } else if (bot < pts[i].fY) {
                     bot = pts[i].fY;
                 }
             }
         } else if (SkPath::kMove_Verb == verb) {
             if (top > pts[0].fY) {
                 top = pts[0].fY;
             } else if (bot < pts[0].fY) {
                 bot = pts[0].fY;
             }
         }
     }
     SkASSERT(top <= bot);

     *itop = SkScalarRoundToInt(top);
     *ibot = SkScalarRoundToInt(bot);
     return maxEdges;
 }

 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
     SkDEBUGCODE(this->validate();)

     if (clip.isEmpty()) {
         return this->setEmpty();
     }

     if (path.isEmpty()) {
         if (path.isInverseFillType()) {
             return this->set(clip);
         } else {
             return this->setEmpty();
         }
     }

     //  compute worst-case rgn-size for the path
     int pathTop, pathBot;
     int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
     int clipTop, clipBot;
     int clipTransitions;

     clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);

     int top = SkMax32(pathTop, clipTop);
     int bot = SkMin32(pathBot, clipBot);

     if (top >= bot)
         return this->setEmpty();

     SkRgnBuilder builder;

     if (!builder.init(bot - top,
                       SkMax32(pathTransitions, clipTransitions),
                       path.isInverseFillType())) {
         // can't allocate working space, so return false
         return this->setEmpty();
     }

     SkScan::FillPath(path, clip, &builder);
     builder.done();

     int count = builder.computeRunCount();
     if (count == 0) {
         return this->setEmpty();
     } else if (count == kRectRegionRuns) {
         builder.copyToRect(&fBounds);
         this->setRect(fBounds);
     } else {
         SkRegion tmp;

         tmp.fRunHead = RunHead::Alloc(count);
         builder.copyToRgn(tmp.fRunHead->writable_runs());
         tmp.fRunHead->computeRunBounds(&tmp.fBounds);
         this->swap(tmp);
     }
     SkDEBUGCODE(this->validate();)
     return true;
 }

 /////////////////////////////////////////////////////////////////////////////////////////////////
 /////////////////////////////////////////////////////////////////////////////////////////////////

 struct Edge {
     enum {
         kY0Link = 0x01,
         kY1Link = 0x02,

         kCompleteLink = (kY0Link | kY1Link)
     };

     SkRegion::RunType fX;
     SkRegion::RunType fY0, fY1;
     uint8_t fFlags;
     Edge*   fNext;

     void set(int x, int y0, int y1) {
         SkASSERT(y0 != y1);

         fX = (SkRegion::RunType)(x);
         fY0 = (SkRegion::RunType)(y0);
         fY1 = (SkRegion::RunType)(y1);
         fFlags = 0;
         SkDEBUGCODE(fNext = NULL;)
     }

     int top() const {
         return SkFastMin32(fY0, fY1);
     }
 };

 static void find_link(Edge* base, Edge* stop) {
     SkASSERT(base < stop);

     if (base->fFlags == Edge::kCompleteLink) {
         SkASSERT(base->fNext);
         return;
     }

     SkASSERT(base + 1 < stop);

     int y0 = base->fY0;
     int y1 = base->fY1;

     Edge* e = base;
     if ((base->fFlags & Edge::kY0Link) == 0) {
         for (;;) {
             e += 1;
             if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
                 SkASSERT(NULL == e->fNext);
                 e->fNext = base;
                 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link);
                 break;
             }
         }
     }

     e = base;
     if ((base->fFlags & Edge::kY1Link) == 0) {
         for (;;) {
             e += 1;
             if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
                 SkASSERT(NULL == base->fNext);
                 base->fNext = e;
                 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link);
                 break;
             }
         }
     }

     base->fFlags = Edge::kCompleteLink;
 }

 static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
     while (0 == edge->fFlags) {
         edge++; // skip over "used" edges
     }

     SkASSERT(edge < stop);

     Edge* base = edge;
     Edge* prev = edge;
     edge = edge->fNext;
     SkASSERT(edge != base);

     int count = 1;
     path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
     prev->fFlags = 0;
     do {
         if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear
             path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
             path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0));    // H
         }
         prev = edge;
         edge = edge->fNext;
         count += 1;
         prev->fFlags = 0;
     } while (edge != base);
     path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1));    // V
     path->close();
     return count;
 }

 #include "SkTSearch.h"

 static int EdgeProc(const Edge* a, const Edge* b) {
     return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
 }

 bool SkRegion::getBoundaryPath(SkPath* path) const {
     // path could safely be NULL if we're empty, but the caller shouldn't
     // *know* that
     SkASSERT(path);

     if (this->isEmpty()) {
         return false;
     }

     const SkIRect& bounds = this->getBounds();

     if (this->isRect()) {
         SkRect  r;
         r.set(bounds);      // this converts the ints to scalars
         path->addRect(r);
         return true;
     }

     SkRegion::Iterator  iter(*this);
     SkTDArray<Edge>     edges;

     for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
         Edge* edge = edges.append(2);
         edge[0].set(r.fLeft, r.fBottom, r.fTop);
         edge[1].set(r.fRight, r.fTop, r.fBottom);
     }
     qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));

     int count = edges.count();
     Edge* start = edges.begin();
     Edge* stop = start + count;
     Edge* e;

     for (e = start; e != stop; e++) {
         find_link(e, stop);
     }

 #ifdef SK_DEBUG
     for (e = start; e != stop; e++) {
         SkASSERT(e->fNext != NULL);
         SkASSERT(e->fFlags == Edge::kCompleteLink);
     }
 #endif

     path->incReserve(count << 1);
     do {
         SkASSERT(count > 1);
         count -= extract_path(start, stop, path);
     } while (count > 0);

     return true;
 }
	/*
	* 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 "SkRegionPriv.h"
	#include "SkBlitter.h"
	#include "SkScan.h"
	#include "SkTDArray.h"
	#include "SkPath.h"

	// The rgnbuilder caller seems to pass short counts, possible often seens early failure, so
	// we may not want to promote this to a "std" routine just yet.
	static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) {
	for (int i = 0; i < count; ++i) {
	if (a[i] != b[i]) {
	return false;
	}
	}
	return true;
	}

	class SkRgnBuilder : public SkBlitter {
	public:
	SkRgnBuilder();
	virtual ~SkRgnBuilder();

	// returns true if it could allocate the working storage needed
	bool init(int maxHeight, int maxTransitions, bool pathIsInverse);

	void done() {
	if (fCurrScanline != NULL) {
	fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));
	if (!this->collapsWithPrev()) { // flush the last line
	fCurrScanline = fCurrScanline->nextScanline();
	}
	}
	}

	int computeRunCount() const;
	void copyToRect(SkIRect*) const;
	void copyToRgn(SkRegion::RunType runs[]) const;

	virtual void blitH(int x, int y, int width);

	#ifdef SK_DEBUG
	void dump() const {
	SkDebugf("SkRgnBuilder: Top = %d\n", fTop);
	const Scanline* line = (Scanline*)fStorage;
	while (line < fCurrScanline) {
	SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount);
	for (int i = 0; i < line->fXCount; i++) {
	SkDebugf(" %d", line->firstX()[i]);
	}
	SkDebugf("\n");

	line = line->nextScanline();
	}
	}
	#endif
	private:
	/*
	* Scanline mimics a row in the region, nearly. A row in a region is:
	* [Bottom IntervalCount [L R]... Sentinel]
	* while a Scanline is
	* [LastY XCount [L R]... uninitialized]
	* The two are the same length (which is good), but we have to transmute
	* the scanline a little when we convert it to a region-row.
	*
	* Potentially we could recode this to exactly match the row format, in
	* which case copyToRgn() could be a single memcpy. Not sure that is worth
	* the effort.
	*/
	struct Scanline {
	SkRegion::RunType fLastY;
	SkRegion::RunType fXCount;

	SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); }
	Scanline* nextScanline() const {
	// add final +1 for the x-sentinel
	return (Scanline)((SkRegion::RunType)(this + 1) + fXCount + 1);
	}
	};
	SkRegion::RunType* fStorage;
	Scanline* fCurrScanline;
	Scanline* fPrevScanline;
	// points at next avialable x[] in fCurrScanline
	SkRegion::RunType* fCurrXPtr;
	SkRegion::RunType fTop; // first Y value

	int fStorageCount;

	bool collapsWithPrev() {
	if (fPrevScanline != NULL &&
	fPrevScanline->fLastY + 1 == fCurrScanline->fLastY &&
	fPrevScanline->fXCount == fCurrScanline->fXCount &&
	sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount))
	{
	// update the height of fPrevScanline
	fPrevScanline->fLastY = fCurrScanline->fLastY;
	return true;
	}
	return false;
	}
	};

	SkRgnBuilder::SkRgnBuilder()
	: fStorage(NULL) {
	}

	SkRgnBuilder::~SkRgnBuilder() {
	sk_free(fStorage);
	}

	bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) {
	if ((maxHeight \| maxTransitions) < 0) {
	return false;
	}

	if (pathIsInverse) {
	// allow for additional X transitions to "invert" each scanline
	// [ L' ... normal transitions ... R' ]
	//
	maxTransitions += 2;
	}

	// compute the count with +1 and +3 slop for the working buffer
	int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions);

	if (pathIsInverse) {
	// allow for two "empty" rows for the top and bottom
	// [ Y, 1, L, R, S] == 5 (*2 for top and bottom)
	count += 10;
	}

	if (count < 0 \|\| !sk_64_isS32(count)) {
	return false;
	}
	fStorageCount = sk_64_asS32(count);

	int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType));
	if (size < 0 \|\| !sk_64_isS32(size)) {
	return false;
	}

	fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0);
	if (NULL == fStorage) {
	return false;
	}

	fCurrScanline = NULL; // signal empty collection
	fPrevScanline = NULL; // signal first scanline
	return true;
	}

	void SkRgnBuilder::blitH(int x, int y, int width) {
	if (fCurrScanline == NULL) { // first time
	fTop = (SkRegion::RunType)(y);
	fCurrScanline = (Scanline*)fStorage;
	fCurrScanline->fLastY = (SkRegion::RunType)(y);
	fCurrXPtr = fCurrScanline->firstX();
	} else {
	SkASSERT(y >= fCurrScanline->fLastY);

	if (y > fCurrScanline->fLastY) {
	// if we get here, we're done with fCurrScanline
	fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX()));

	int prevLastY = fCurrScanline->fLastY;
	if (!this->collapsWithPrev()) {
	fPrevScanline = fCurrScanline;
	fCurrScanline = fCurrScanline->nextScanline();

	}
	if (y - 1 > prevLastY) { // insert empty run
	fCurrScanline->fLastY = (SkRegion::RunType)(y - 1);
	fCurrScanline->fXCount = 0;
	fCurrScanline = fCurrScanline->nextScanline();
	}
	// setup for the new curr line
	fCurrScanline->fLastY = (SkRegion::RunType)(y);
	fCurrXPtr = fCurrScanline->firstX();
	}
	}
	// check if we should extend the current run, or add a new one
	if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) {
	fCurrXPtr[-1] = (SkRegion::RunType)(x + width);
	} else {
	fCurrXPtr[0] = (SkRegion::RunType)(x);
	fCurrXPtr[1] = (SkRegion::RunType)(x + width);
	fCurrXPtr += 2;
	}
	SkASSERT(fCurrXPtr - fStorage < fStorageCount);
	}

	int SkRgnBuilder::computeRunCount() const {
	if (fCurrScanline == NULL) {
	return 0;
	}

	const SkRegion::RunType* line = fStorage;
	const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline;

	return 2 + (int)(stop - line);
	}

	void SkRgnBuilder::copyToRect(SkIRect* r) const {
	SkASSERT(fCurrScanline != NULL);
	// A rect's scanline is [bottom intervals left right sentinel] == 5
	SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5);

	const Scanline* line = (const Scanline*)fStorage;
	SkASSERT(line->fXCount == 2);

	r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1);
	}

	void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const {
	SkASSERT(fCurrScanline != NULL);
	SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4);

	const Scanline* line = (const Scanline*)fStorage;
	const Scanline* stop = fCurrScanline;

	*runs++ = fTop;
	do {
	*runs++ = (SkRegion::RunType)(line->fLastY + 1);
	int count = line->fXCount;
	*runs++ = count >> 1; // intervalCount
	if (count) {
	memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType));
	runs += count;
	}
	*runs++ = SkRegion::kRunTypeSentinel;
	line = line->nextScanline();
	} while (line < stop);
	SkASSERT(line == stop);
	*runs = SkRegion::kRunTypeSentinel;
	}

	static unsigned verb_to_initial_last_index(unsigned verb) {
	static const uint8_t gPathVerbToInitialLastIndex[] = {
	0, // kMove_Verb
	1, // kLine_Verb
	2, // kQuad_Verb
	2, // kConic_Verb
	3, // kCubic_Verb
	0, // kClose_Verb
	0 // kDone_Verb
	};
	SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex));
	return gPathVerbToInitialLastIndex[verb];
	}

	static unsigned verb_to_max_edges(unsigned verb) {
	static const uint8_t gPathVerbToMaxEdges[] = {
	0, // kMove_Verb
	1, // kLine_Verb
	2, // kQuad_VerbB
	2, // kConic_VerbB
	3, // kCubic_Verb
	0, // kClose_Verb
	0 // kDone_Verb
	};
	SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges));
	return gPathVerbToMaxEdges[verb];
	}


	static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) {
	SkPath::Iter iter(path, true);
	SkPoint pts[4];
	SkPath::Verb verb;

	int maxEdges = 0;
	SkScalar top = SkIntToScalar(SK_MaxS16);
	SkScalar bot = SkIntToScalar(SK_MinS16);

	while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) {
	maxEdges += verb_to_max_edges(verb);

	int lastIndex = verb_to_initial_last_index(verb);
	if (lastIndex > 0) {
	for (int i = 1; i <= lastIndex; i++) {
	if (top > pts[i].fY) {
	top = pts[i].fY;
	} else if (bot < pts[i].fY) {
	bot = pts[i].fY;
	}
	}
	} else if (SkPath::kMove_Verb == verb) {
	if (top > pts[0].fY) {
	top = pts[0].fY;
	} else if (bot < pts[0].fY) {
	bot = pts[0].fY;
	}
	}
	}
	SkASSERT(top <= bot);

	*itop = SkScalarRoundToInt(top);
	*ibot = SkScalarRoundToInt(bot);
	return maxEdges;
	}

	bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) {
	SkDEBUGCODE(this->validate();)

	if (clip.isEmpty()) {
	return this->setEmpty();
	}

	if (path.isEmpty()) {
	if (path.isInverseFillType()) {
	return this->set(clip);
	} else {
	return this->setEmpty();
	}
	}

	// compute worst-case rgn-size for the path
	int pathTop, pathBot;
	int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot);
	int clipTop, clipBot;
	int clipTransitions;

	clipTransitions = clip.count_runtype_values(&clipTop, &clipBot);

	int top = SkMax32(pathTop, clipTop);
	int bot = SkMin32(pathBot, clipBot);

	if (top >= bot)
	return this->setEmpty();

	SkRgnBuilder builder;

	if (!builder.init(bot - top,
	SkMax32(pathTransitions, clipTransitions),
	path.isInverseFillType())) {
	// can't allocate working space, so return false
	return this->setEmpty();
	}

	SkScan::FillPath(path, clip, &builder);
	builder.done();

	int count = builder.computeRunCount();
	if (count == 0) {
	return this->setEmpty();
	} else if (count == kRectRegionRuns) {
	builder.copyToRect(&fBounds);
	this->setRect(fBounds);
	} else {
	SkRegion tmp;

	tmp.fRunHead = RunHead::Alloc(count);
	builder.copyToRgn(tmp.fRunHead->writable_runs());
	tmp.fRunHead->computeRunBounds(&tmp.fBounds);
	this->swap(tmp);
	}
	SkDEBUGCODE(this->validate();)
	return true;
	}

	/////////////////////////////////////////////////////////////////////////////////////////////////
	/////////////////////////////////////////////////////////////////////////////////////////////////

	struct Edge {
	enum {
	kY0Link = 0x01,
	kY1Link = 0x02,

	kCompleteLink = (kY0Link \| kY1Link)
	};

	SkRegion::RunType fX;
	SkRegion::RunType fY0, fY1;
	uint8_t fFlags;
	Edge* fNext;

	void set(int x, int y0, int y1) {
	SkASSERT(y0 != y1);

	fX = (SkRegion::RunType)(x);
	fY0 = (SkRegion::RunType)(y0);
	fY1 = (SkRegion::RunType)(y1);
	fFlags = 0;
	SkDEBUGCODE(fNext = NULL;)
	}

	int top() const {
	return SkFastMin32(fY0, fY1);
	}
	};

	static void find_link(Edge* base, Edge* stop) {
	SkASSERT(base < stop);

	if (base->fFlags == Edge::kCompleteLink) {
	SkASSERT(base->fNext);
	return;
	}

	SkASSERT(base + 1 < stop);

	int y0 = base->fY0;
	int y1 = base->fY1;

	Edge* e = base;
	if ((base->fFlags & Edge::kY0Link) == 0) {
	for (;;) {
	e += 1;
	if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) {
	SkASSERT(NULL == e->fNext);
	e->fNext = base;
	e->fFlags = SkToU8(e->fFlags \| Edge::kY1Link);
	break;
	}
	}
	}

	e = base;
	if ((base->fFlags & Edge::kY1Link) == 0) {
	for (;;) {
	e += 1;
	if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) {
	SkASSERT(NULL == base->fNext);
	base->fNext = e;
	e->fFlags = SkToU8(e->fFlags \| Edge::kY0Link);
	break;
	}
	}
	}

	base->fFlags = Edge::kCompleteLink;
	}

	static int extract_path(Edge* edge, Edge* stop, SkPath* path) {
	while (0 == edge->fFlags) {
	edge++; // skip over "used" edges
	}

	SkASSERT(edge < stop);

	Edge* base = edge;
	Edge* prev = edge;
	edge = edge->fNext;
	SkASSERT(edge != base);

	int count = 1;
	path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0));
	prev->fFlags = 0;
	do {
	if (prev->fX != edge->fX \|\| prev->fY1 != edge->fY0) { // skip collinear
	path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
	path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H
	}
	prev = edge;
	edge = edge->fNext;
	count += 1;
	prev->fFlags = 0;
	} while (edge != base);
	path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V
	path->close();
	return count;
	}

	#include "SkTSearch.h"

	static int EdgeProc(const Edge* a, const Edge* b) {
	return (a->fX == b->fX) ? a->top() - b->top() : a->fX - b->fX;
	}

	bool SkRegion::getBoundaryPath(SkPath* path) const {
	// path could safely be NULL if we're empty, but the caller shouldn't
	// know that
	SkASSERT(path);

	if (this->isEmpty()) {
	return false;
	}

	const SkIRect& bounds = this->getBounds();

	if (this->isRect()) {
	SkRect r;
	r.set(bounds); // this converts the ints to scalars
	path->addRect(r);
	return true;
	}

	SkRegion::Iterator iter(*this);
	SkTDArray<Edge> edges;

	for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) {
	Edge* edge = edges.append(2);
	edge[0].set(r.fLeft, r.fBottom, r.fTop);
	edge[1].set(r.fRight, r.fTop, r.fBottom);
	}
	qsort(edges.begin(), edges.count(), sizeof(Edge), SkCastForQSort(EdgeProc));

	int count = edges.count();
	Edge* start = edges.begin();
	Edge* stop = start + count;
	Edge* e;

	for (e = start; e != stop; e++) {
	find_link(e, stop);
	}

	#ifdef SK_DEBUG
	for (e = start; e != stop; e++) {
	SkASSERT(e->fNext != NULL);
	SkASSERT(e->fFlags == Edge::kCompleteLink);
	}
	#endif

	path->incReserve(count << 1);
	do {
	SkASSERT(count > 1);
	count -= extract_path(start, stop, path);
	} while (count > 0);

	return true;
	}