splash/SplashXPathScanner.cc - third_party/poppler - Git at Google

 //========================================================================
 //
 // SplashXPathScanner.cc
 //
 //========================================================================

 //========================================================================
 //
 // Modified under the Poppler project - http://poppler.freedesktop.org
 //
 // All changes made under the Poppler project to this file are licensed
 // under GPL version 2 or later
 //
 // Copyright (C) 2008, 2010, 2014 Albert Astals Cid <aacid@kde.org>
 // Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
 // Copyright (C) 2013, 2014 Thomas Freitag <Thomas.Freitag@alfa.de>
 //
 // To see a description of the changes please see the Changelog file that
 // came with your tarball or type make ChangeLog if you are building from git
 //
 //========================================================================

 #include <config.h>

 #ifdef USE_GCC_PRAGMAS
 #pragma implementation
 #endif

 #include <stdlib.h>
 #include <string.h>
 #include <algorithm>
 #include "goo/gmem.h"
 #include "SplashMath.h"
 #include "SplashXPath.h"
 #include "SplashBitmap.h"
 #include "SplashXPathScanner.h"

 //------------------------------------------------------------------------

 struct SplashIntersect {
   int y;
   int x0, x1;			// intersection of segment with [y, y+1)
   int count;			// EO/NZWN counter increment
 };

 struct cmpIntersectFunctor {
   bool operator()(const SplashIntersect &i0, const SplashIntersect &i1) {
     return (i0.y != i1.y) ? (i0.y < i1.y) : (i0.x0 < i1.x0);
   }
 };

 //------------------------------------------------------------------------
 // SplashXPathScanner
 //------------------------------------------------------------------------

 SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA,
 				       int clipYMin, int clipYMax) {
   SplashXPathSeg *seg;
   SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
   int i;

   xPath = xPathA;
   eo = eoA;
   partialClip = gFalse;

   // compute the bbox
   if (xPath->length == 0) {
     xMin = yMin = 1;
     xMax = yMax = 0;
   } else {
     seg = &xPath->segs[0];
     if (seg->x0 <= seg->x1) {
       xMinFP = seg->x0;
       xMaxFP = seg->x1;
     } else {
       xMinFP = seg->x1;
       xMaxFP = seg->x0;
     }
     if (seg->flags & splashXPathFlip) {
       yMinFP = seg->y1;
       yMaxFP = seg->y0;
     } else {
       yMinFP = seg->y0;
       yMaxFP = seg->y1;
     }
     for (i = 1; i < xPath->length; ++i) {
       seg = &xPath->segs[i];
       if (seg->x0 < xMinFP) {
 	xMinFP = seg->x0;
       } else if (seg->x0 > xMaxFP) {
 	xMaxFP = seg->x0;
       }
       if (seg->x1 < xMinFP) {
 	xMinFP = seg->x1;
       } else if (seg->x1 > xMaxFP) {
 	xMaxFP = seg->x1;
       }
       if (seg->flags & splashXPathFlip) {
 	if (seg->y0 > yMaxFP) {
 	  yMaxFP = seg->y0;
 	}
       } else {
 	if (seg->y1 > yMaxFP) {
 	  yMaxFP = seg->y1;
 	}
       }
     }
     xMin = splashFloor(xMinFP);
     xMax = splashFloor(xMaxFP);
     yMin = splashFloor(yMinFP);
     yMax = splashFloor(yMaxFP);
     if (clipYMin > yMin) {
       yMin = clipYMin;
       partialClip = gTrue;
     }
     if (clipYMax < yMax) {
       yMax = clipYMax;
       partialClip = gTrue;
     }
   }

   allInter = NULL;
   inter = NULL;
   computeIntersections();
   interY = yMin - 1;
 }

 SplashXPathScanner::~SplashXPathScanner() {
   gfree(inter);
   gfree(allInter);
 }

 void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA,
 				   int *xMaxA, int *yMaxA) {
   *xMinA = xMin / splashAASize;
   *yMinA = yMin / splashAASize;
   *xMaxA = xMax / splashAASize;
   *yMaxA = yMax / splashAASize;
 }

 void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
   int interBegin, interEnd, xx, i;

   if (y < yMin || y > yMax) {
     interBegin = interEnd = 0;
   } else {
     interBegin = inter[y - yMin];
     interEnd = inter[y - yMin + 1];
   }
   if (interBegin < interEnd) {
     *spanXMin = allInter[interBegin].x0;
     xx = allInter[interBegin].x1;
     for (i = interBegin + 1; i < interEnd; ++i) {
       if (allInter[i].x1 > xx) {
 	xx = allInter[i].x1;
       }
     }
     *spanXMax = xx;
   } else {
     *spanXMin = xMax + 1;
     *spanXMax = xMax;
   }
 }

 GBool SplashXPathScanner::test(int x, int y) {
   int interBegin, interEnd, count, i;

   if (y < yMin || y > yMax) {
     return gFalse;
   }
   interBegin = inter[y - yMin];
   interEnd = inter[y - yMin + 1];
   count = 0;
   for (i = interBegin; i < interEnd && allInter[i].x0 <= x; ++i) {
     if (x <= allInter[i].x1) {
       return gTrue;
     }
     count += allInter[i].count;
   }
   return eo ? (count & 1) : (count != 0);
 }

 GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
   int interBegin, interEnd, count, xx1, i;

   if (y < yMin || y > yMax) {
     return gFalse;
   }
   interBegin = inter[y - yMin];
   interEnd = inter[y - yMin + 1];
   count = 0;
   for (i = interBegin; i < interEnd && allInter[i].x1 < x0; ++i) {
     count += allInter[i].count;
   }

   // invariant: the subspan [x0,xx1] is inside the path
   xx1 = x0 - 1;
   while (xx1 < x1) {
     if (i >= interEnd) {
       return gFalse;
     }
     if (allInter[i].x0 > xx1 + 1 &&
 	!(eo ? (count & 1) : (count != 0))) {
       return gFalse;
     }
     if (allInter[i].x1 > xx1) {
       xx1 = allInter[i].x1;
     }
     count += allInter[i].count;
     ++i;
   }

   return gTrue;
 }

 GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
   int interEnd, xx0, xx1;

   if (y < yMin || y > yMax) {
     return gFalse;
   }
   if (interY != y) {
     interY = y;
     interIdx = inter[y - yMin];
     interCount = 0;
   }
   interEnd = inter[y - yMin + 1];
   if (interIdx >= interEnd) {
     return gFalse;
   }
   xx0 = allInter[interIdx].x0;
   xx1 = allInter[interIdx].x1;
   interCount += allInter[interIdx].count;
   ++interIdx;
   while (interIdx < interEnd &&
 	 (allInter[interIdx].x0 <= xx1 ||
 	  (eo ? (interCount & 1) : (interCount != 0)))) {
     if (allInter[interIdx].x1 > xx1) {
       xx1 = allInter[interIdx].x1;
     }
     interCount += allInter[interIdx].count;
     ++interIdx;
   }
   *x0 = xx0;
   *x1 = xx1;
   return gTrue;
 }

 void SplashXPathScanner::computeIntersections() {
   SplashXPathSeg *seg;
   SplashCoord segXMin, segXMax, segYMin, segYMax, xx0, xx1;
   int x, y, y0, y1, i;

   if (yMin > yMax) {
     return;
   }

   // build the list of all intersections
   allInterLen = 0;
   allInterSize = 16;
   allInter = (SplashIntersect *)gmallocn(allInterSize,
 					 sizeof(SplashIntersect));
   for (i = 0; i < xPath->length; ++i) {
     seg = &xPath->segs[i];
     if (seg->flags & splashXPathFlip) {
       segYMin = seg->y1;
       segYMax = seg->y0;
     } else {
       segYMin = seg->y0;
       segYMax = seg->y1;
     }
     if (seg->flags & splashXPathHoriz) {
       y = splashFloor(seg->y0);
       if (y >= yMin && y <= yMax) {
 	if (!addIntersection(segYMin, segYMax, seg->flags,
 			y, splashFloor(seg->x0), splashFloor(seg->x1)))
           break;
       }
     } else if (seg->flags & splashXPathVert) {
       y0 = splashFloor(segYMin);
       if (y0 < yMin) {
 	y0 = yMin;
       }
       y1 = splashFloor(segYMax);
       if (y1 > yMax) {
 	y1 = yMax;
       }
       x = splashFloor(seg->x0);
       for (y = y0; y <= y1; ++y) {
 	if (!addIntersection(segYMin, segYMax, seg->flags, y, x, x))
           break;
       }
     } else {
       if (seg->x0 < seg->x1) {
 	segXMin = seg->x0;
 	segXMax = seg->x1;
       } else {
 	segXMin = seg->x1;
 	segXMax = seg->x0;
       }
       y0 = splashFloor(segYMin);
       if (y0 < yMin) {
 	y0 = yMin;
       }
       y1 = splashFloor(segYMax);
       if (y1 > yMax) {
 	y1 = yMax;
       }
       // this loop could just add seg->dxdy to xx1 on each iteration,
       // but that introduces numerical accuracy problems
       xx1 = seg->x0 + ((SplashCoord)y0 - seg->y0) * seg->dxdy;
       for (y = y0; y <= y1; ++y) {
 	xx0 = xx1;
 	xx1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
 	// the segment may not actually extend to the top and/or bottom edges
 	if (xx0 < segXMin) {
 	  xx0 = segXMin;
 	} else if (xx0 > segXMax) {
 	  xx0 = segXMax;
 	}
 	if (xx1 < segXMin) {
 	  xx1 = segXMin;
 	} else if (xx1 > segXMax) {
 	  xx1 = segXMax;
 	}
 	if (!addIntersection(segYMin, segYMax, seg->flags, y,
 			splashFloor(xx0), splashFloor(xx1)))
           break;
       }
     }
   }
   std::sort(allInter, allInter + allInterLen, cmpIntersectFunctor());

   // build the list of y pointers
   inter = (int *)gmallocn(yMax - yMin + 2, sizeof(int));
   i = 0;
   for (y = yMin; y <= yMax; ++y) {
     inter[y - yMin] = i;
     while (i < allInterLen && allInter[i].y <= y) {
       ++i;
     }
   }
   inter[yMax - yMin + 1] = i;
 }

 GBool SplashXPathScanner::addIntersection(double segYMin, double segYMax,
 					 Guint segFlags,
 					 int y, int x0, int x1) {
   if (allInterLen == allInterSize) {
     unsigned int newInterSize = ((unsigned int) allInterSize * 2 > INT_MAX / sizeof(SplashIntersect)) ? allInterSize + 32768 : allInterSize * 2;
     if (newInterSize >= INT_MAX / sizeof(SplashIntersect)) {
       error(errInternal, -1, "Bogus memory allocation size in SplashXPathScanner::addIntersection {0:d}", newInterSize);
       return gFalse;
     }
     allInterSize = newInterSize;
     allInter = (SplashIntersect *)greallocn(allInter, newInterSize,
 					    sizeof(SplashIntersect));
   }
   allInter[allInterLen].y = y;
   if (x0 < x1) {
     allInter[allInterLen].x0 = x0;
     allInter[allInterLen].x1 = x1;
   } else {
     allInter[allInterLen].x0 = x1;
     allInter[allInterLen].x1 = x0;
   }
   if (segYMin <= y &&
       (SplashCoord)y < segYMax &&
       !(segFlags & splashXPathHoriz)) {
     allInter[allInterLen].count = eo ? 1
                                      : (segFlags & splashXPathFlip) ? 1 : -1;
   } else {
     allInter[allInterLen].count = 0;
   }
   ++allInterLen;
   return gTrue;
 }

 void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
 				      int *x0, int *x1, int y, GBool adjustVertLine) {
   int xx0, xx1, xx, xxMin, xxMax, yy, interEnd;
   Guchar mask;
   SplashColorPtr p;

   memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
   xxMin = aaBuf->getWidth();
   xxMax = -1;
   if (yMin <= yMax) {
     if (splashAASize * y < yMin) {
       interIdx = inter[0];
     } else if (splashAASize * y > yMax) {
       interIdx = inter[yMax - yMin + 1];
     } else {
       interIdx = inter[splashAASize * y - yMin];
     }
     for (yy = 0; yy < splashAASize; ++yy) {
       if (splashAASize * y + yy < yMin) {
 	interEnd = inter[0];
       } else if (splashAASize * y + yy > yMax) {
 	interEnd = inter[yMax - yMin + 1];
       } else {
 	interEnd = inter[splashAASize * y + yy - yMin + 1];
       }
       interCount = 0;
       while (interIdx < interEnd) {
 	xx0 = allInter[interIdx].x0;
 	xx1 = allInter[interIdx].x1;
 	interCount += allInter[interIdx].count;
 	++interIdx;
 	while (interIdx < interEnd &&
 	       (allInter[interIdx].x0 <= xx1 ||
 		(eo ? (interCount & 1) : (interCount != 0)))) {
 	  if (allInter[interIdx].x1 > xx1) {
 	    xx1 = allInter[interIdx].x1;
 	  }
 	  interCount += allInter[interIdx].count;
 	  ++interIdx;
 	}
 	if (xx0 < 0) {
 	  xx0 = 0;
 	}
 	++xx1;
 	if (xx1 > aaBuf->getWidth()) {
 	  xx1 = aaBuf->getWidth();
 	}
 	// set [xx0, xx1) to 1
 	if (xx0 < xx1) {
 	  xx = xx0;
 	  p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 	  if (xx & 7) {
 	    mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
 	    if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
 	      mask &= (Guchar)(0xff00 >> (xx1 & 7));
 	    }
 	    *p++ |= mask;
 	    xx = (xx & ~7) + 8;
 	  }
 	  for (; xx + 7 < xx1; xx += 8) {
 	    *p++ |= 0xff;
 	  }
 	  if (xx < xx1) {
 	    *p |= adjustVertLine ? 0xff : (Guchar)(0xff00 >> (xx1 & 7));
 	  }
 	}
 	if (xx0 < xxMin) {
 	  xxMin = xx0;
 	}
 	if (xx1 > xxMax) {
 	  xxMax = xx1;
 	}
       }
     }
   }
   if (xxMin > xxMax) {
     xxMin = xxMax;
   }
   *x0 = xxMin / splashAASize;
   *x1 = (xxMax - 1) / splashAASize;
 }

 void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
 				    int *x0, int *x1, int y) {
   int xx0, xx1, xx, yy, interEnd;
   Guchar mask;
   SplashColorPtr p;

   for (yy = 0; yy < splashAASize; ++yy) {
     xx = *x0 * splashAASize;
     if (yMin <= yMax) {
       if (splashAASize * y + yy < yMin) {
 	interIdx = interEnd = inter[0];
       } else if (splashAASize * y + yy > yMax) {
 	interIdx = interEnd = inter[yMax - yMin + 1];
       } else {
 	interIdx = inter[splashAASize * y + yy - yMin];
 	if (splashAASize * y + yy > yMax) {
 	  interEnd = inter[yMax - yMin + 1];
 	} else {
 	  interEnd = inter[splashAASize * y + yy - yMin + 1];
 	}
       }
       interCount = 0;
       while (interIdx < interEnd && xx < (*x1 + 1) * splashAASize) {
 	xx0 = allInter[interIdx].x0;
 	xx1 = allInter[interIdx].x1;
 	interCount += allInter[interIdx].count;
 	++interIdx;
 	while (interIdx < interEnd &&
 	       (allInter[interIdx].x0 <= xx1 ||
 		(eo ? (interCount & 1) : (interCount != 0)))) {
 	  if (allInter[interIdx].x1 > xx1) {
 	    xx1 = allInter[interIdx].x1;
 	  }
 	  interCount += allInter[interIdx].count;
 	  ++interIdx;
 	}
 	if (xx0 > aaBuf->getWidth()) {
 	  xx0 = aaBuf->getWidth();
 	}
 	// set [xx, xx0) to 0
 	if (xx < xx0) {
 	  p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
 	  if (xx & 7) {
 	    mask = (Guchar)(0xff00 >> (xx & 7));
 	    if ((xx & ~7) == (xx0 & ~7)) {
 	      mask |= 0xff >> (xx0 & 7);
 	    }
 	    *p++ &= mask;
 	    xx = (xx & ~7) + 8;
 	  }
 	  for (; xx + 7 < xx0; xx += 8) {
 	    *p++ = 0x00;
 	  }
 	  if (xx < xx0) {
 	    *p &= 0xff >> (xx0 & 7);
 	  }
 	}
 	if (xx1 >= xx) {
 	  xx = xx1 + 1;
 	}
       }
     }
     xx0 = (*x1 + 1) * splashAASize;
     if (xx0 > aaBuf->getWidth()) xx0 = aaBuf->getWidth();
     // set [xx, xx0) to 0
     if (xx < xx0 && xx >= 0) {
       p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
       if (xx & 7) {
 	mask = (Guchar)(0xff00 >> (xx & 7));
 	if ((xx & ~7) == (xx0 & ~7)) {
 	  mask &= 0xff >> (xx0 & 7);
 	}
 	*p++ &= mask;
 	xx = (xx & ~7) + 8;
       }
       for (; xx + 7 < xx0; xx += 8) {
 	*p++ = 0x00;
       }
       if (xx < xx0) {
 	*p &= 0xff >> (xx0 & 7);
       }
     }
   }
 }
	//========================================================================
	//
	// SplashXPathScanner.cc
	//
	//========================================================================

	//========================================================================
	//
	// Modified under the Poppler project - http://poppler.freedesktop.org
	//
	// All changes made under the Poppler project to this file are licensed
	// under GPL version 2 or later
	//
	// Copyright (C) 2008, 2010, 2014 Albert Astals Cid <aacid@kde.org>
	// Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
	// Copyright (C) 2013, 2014 Thomas Freitag <Thomas.Freitag@alfa.de>
	//
	// To see a description of the changes please see the Changelog file that
	// came with your tarball or type make ChangeLog if you are building from git
	//
	//========================================================================

	#include <config.h>

	#ifdef USE_GCC_PRAGMAS
	#pragma implementation
	#endif

	#include <stdlib.h>
	#include <string.h>
	#include <algorithm>
	#include "goo/gmem.h"
	#include "SplashMath.h"
	#include "SplashXPath.h"
	#include "SplashBitmap.h"
	#include "SplashXPathScanner.h"

	//------------------------------------------------------------------------

	struct SplashIntersect {
	int y;
	int x0, x1; // intersection of segment with [y, y+1)
	int count; // EO/NZWN counter increment
	};

	struct cmpIntersectFunctor {
	bool operator()(const SplashIntersect &i0, const SplashIntersect &i1) {
	return (i0.y != i1.y) ? (i0.y < i1.y) : (i0.x0 < i1.x0);
	}
	};

	//------------------------------------------------------------------------
	// SplashXPathScanner
	//------------------------------------------------------------------------

	SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA,
	int clipYMin, int clipYMax) {
	SplashXPathSeg *seg;
	SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
	int i;

	xPath = xPathA;
	eo = eoA;
	partialClip = gFalse;

	// compute the bbox
	if (xPath->length == 0) {
	xMin = yMin = 1;
	xMax = yMax = 0;
	} else {
	seg = &xPath->segs[0];
	if (seg->x0 <= seg->x1) {
	xMinFP = seg->x0;
	xMaxFP = seg->x1;
	} else {
	xMinFP = seg->x1;
	xMaxFP = seg->x0;
	}
	if (seg->flags & splashXPathFlip) {
	yMinFP = seg->y1;
	yMaxFP = seg->y0;
	} else {
	yMinFP = seg->y0;
	yMaxFP = seg->y1;
	}
	for (i = 1; i < xPath->length; ++i) {
	seg = &xPath->segs[i];
	if (seg->x0 < xMinFP) {
	xMinFP = seg->x0;
	} else if (seg->x0 > xMaxFP) {
	xMaxFP = seg->x0;
	}
	if (seg->x1 < xMinFP) {
	xMinFP = seg->x1;
	} else if (seg->x1 > xMaxFP) {
	xMaxFP = seg->x1;
	}
	if (seg->flags & splashXPathFlip) {
	if (seg->y0 > yMaxFP) {
	yMaxFP = seg->y0;
	}
	} else {
	if (seg->y1 > yMaxFP) {
	yMaxFP = seg->y1;
	}
	}
	}
	xMin = splashFloor(xMinFP);
	xMax = splashFloor(xMaxFP);
	yMin = splashFloor(yMinFP);
	yMax = splashFloor(yMaxFP);
	if (clipYMin > yMin) {
	yMin = clipYMin;
	partialClip = gTrue;
	}
	if (clipYMax < yMax) {
	yMax = clipYMax;
	partialClip = gTrue;
	}
	}

	allInter = NULL;
	inter = NULL;
	computeIntersections();
	interY = yMin - 1;
	}

	SplashXPathScanner::~SplashXPathScanner() {
	gfree(inter);
	gfree(allInter);
	}

	void SplashXPathScanner::getBBoxAA(int xMinA, int yMinA,
	int xMaxA, int yMaxA) {
	*xMinA = xMin / splashAASize;
	*yMinA = yMin / splashAASize;
	*xMaxA = xMax / splashAASize;
	*yMaxA = yMax / splashAASize;
	}

	void SplashXPathScanner::getSpanBounds(int y, int spanXMin, int spanXMax) {
	int interBegin, interEnd, xx, i;

	if (y < yMin \|\| y > yMax) {
	interBegin = interEnd = 0;
	} else {
	interBegin = inter[y - yMin];
	interEnd = inter[y - yMin + 1];
	}
	if (interBegin < interEnd) {
	*spanXMin = allInter[interBegin].x0;
	xx = allInter[interBegin].x1;
	for (i = interBegin + 1; i < interEnd; ++i) {
	if (allInter[i].x1 > xx) {
	xx = allInter[i].x1;
	}
	}
	*spanXMax = xx;
	} else {
	*spanXMin = xMax + 1;
	*spanXMax = xMax;
	}
	}

	GBool SplashXPathScanner::test(int x, int y) {
	int interBegin, interEnd, count, i;

	if (y < yMin \|\| y > yMax) {
	return gFalse;
	}
	interBegin = inter[y - yMin];
	interEnd = inter[y - yMin + 1];
	count = 0;
	for (i = interBegin; i < interEnd && allInter[i].x0 <= x; ++i) {
	if (x <= allInter[i].x1) {
	return gTrue;
	}
	count += allInter[i].count;
	}
	return eo ? (count & 1) : (count != 0);
	}

	GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
	int interBegin, interEnd, count, xx1, i;

	if (y < yMin \|\| y > yMax) {
	return gFalse;
	}
	interBegin = inter[y - yMin];
	interEnd = inter[y - yMin + 1];
	count = 0;
	for (i = interBegin; i < interEnd && allInter[i].x1 < x0; ++i) {
	count += allInter[i].count;
	}

	// invariant: the subspan [x0,xx1] is inside the path
	xx1 = x0 - 1;
	while (xx1 < x1) {
	if (i >= interEnd) {
	return gFalse;
	}
	if (allInter[i].x0 > xx1 + 1 &&
	!(eo ? (count & 1) : (count != 0))) {
	return gFalse;
	}
	if (allInter[i].x1 > xx1) {
	xx1 = allInter[i].x1;
	}
	count += allInter[i].count;
	++i;
	}

	return gTrue;
	}

	GBool SplashXPathScanner::getNextSpan(int y, int x0, int x1) {
	int interEnd, xx0, xx1;

	if (y < yMin \|\| y > yMax) {
	return gFalse;
	}
	if (interY != y) {
	interY = y;
	interIdx = inter[y - yMin];
	interCount = 0;
	}
	interEnd = inter[y - yMin + 1];
	if (interIdx >= interEnd) {
	return gFalse;
	}
	xx0 = allInter[interIdx].x0;
	xx1 = allInter[interIdx].x1;
	interCount += allInter[interIdx].count;
	++interIdx;
	while (interIdx < interEnd &&
	(allInter[interIdx].x0 <= xx1 \|\|
	(eo ? (interCount & 1) : (interCount != 0)))) {
	if (allInter[interIdx].x1 > xx1) {
	xx1 = allInter[interIdx].x1;
	}
	interCount += allInter[interIdx].count;
	++interIdx;
	}
	*x0 = xx0;
	*x1 = xx1;
	return gTrue;
	}

	void SplashXPathScanner::computeIntersections() {
	SplashXPathSeg *seg;
	SplashCoord segXMin, segXMax, segYMin, segYMax, xx0, xx1;
	int x, y, y0, y1, i;

	if (yMin > yMax) {
	return;
	}

	// build the list of all intersections
	allInterLen = 0;
	allInterSize = 16;
	allInter = (SplashIntersect *)gmallocn(allInterSize,
	sizeof(SplashIntersect));
	for (i = 0; i < xPath->length; ++i) {
	seg = &xPath->segs[i];
	if (seg->flags & splashXPathFlip) {
	segYMin = seg->y1;
	segYMax = seg->y0;
	} else {
	segYMin = seg->y0;
	segYMax = seg->y1;
	}
	if (seg->flags & splashXPathHoriz) {
	y = splashFloor(seg->y0);
	if (y >= yMin && y <= yMax) {
	if (!addIntersection(segYMin, segYMax, seg->flags,
	y, splashFloor(seg->x0), splashFloor(seg->x1)))
	break;
	}
	} else if (seg->flags & splashXPathVert) {
	y0 = splashFloor(segYMin);
	if (y0 < yMin) {
	y0 = yMin;
	}
	y1 = splashFloor(segYMax);
	if (y1 > yMax) {
	y1 = yMax;
	}
	x = splashFloor(seg->x0);
	for (y = y0; y <= y1; ++y) {
	if (!addIntersection(segYMin, segYMax, seg->flags, y, x, x))
	break;
	}
	} else {
	if (seg->x0 < seg->x1) {
	segXMin = seg->x0;
	segXMax = seg->x1;
	} else {
	segXMin = seg->x1;
	segXMax = seg->x0;
	}
	y0 = splashFloor(segYMin);
	if (y0 < yMin) {
	y0 = yMin;
	}
	y1 = splashFloor(segYMax);
	if (y1 > yMax) {
	y1 = yMax;
	}
	// this loop could just add seg->dxdy to xx1 on each iteration,
	// but that introduces numerical accuracy problems
	xx1 = seg->x0 + ((SplashCoord)y0 - seg->y0) * seg->dxdy;
	for (y = y0; y <= y1; ++y) {
	xx0 = xx1;
	xx1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
	// the segment may not actually extend to the top and/or bottom edges
	if (xx0 < segXMin) {
	xx0 = segXMin;
	} else if (xx0 > segXMax) {
	xx0 = segXMax;
	}
	if (xx1 < segXMin) {
	xx1 = segXMin;
	} else if (xx1 > segXMax) {
	xx1 = segXMax;
	}
	if (!addIntersection(segYMin, segYMax, seg->flags, y,
	splashFloor(xx0), splashFloor(xx1)))
	break;
	}
	}
	}
	std::sort(allInter, allInter + allInterLen, cmpIntersectFunctor());

	// build the list of y pointers
	inter = (int *)gmallocn(yMax - yMin + 2, sizeof(int));
	i = 0;
	for (y = yMin; y <= yMax; ++y) {
	inter[y - yMin] = i;
	while (i < allInterLen && allInter[i].y <= y) {
	++i;
	}
	}
	inter[yMax - yMin + 1] = i;
	}

	GBool SplashXPathScanner::addIntersection(double segYMin, double segYMax,
	Guint segFlags,
	int y, int x0, int x1) {
	if (allInterLen == allInterSize) {
	unsigned int newInterSize = ((unsigned int) allInterSize * 2 > INT_MAX / sizeof(SplashIntersect)) ? allInterSize + 32768 : allInterSize * 2;
	if (newInterSize >= INT_MAX / sizeof(SplashIntersect)) {
	error(errInternal, -1, "Bogus memory allocation size in SplashXPathScanner::addIntersection {0:d}", newInterSize);
	return gFalse;
	}
	allInterSize = newInterSize;
	allInter = (SplashIntersect *)greallocn(allInter, newInterSize,
	sizeof(SplashIntersect));
	}
	allInter[allInterLen].y = y;
	if (x0 < x1) {
	allInter[allInterLen].x0 = x0;
	allInter[allInterLen].x1 = x1;
	} else {
	allInter[allInterLen].x0 = x1;
	allInter[allInterLen].x1 = x0;
	}
	if (segYMin <= y &&
	(SplashCoord)y < segYMax &&
	!(segFlags & splashXPathHoriz)) {
	allInter[allInterLen].count = eo ? 1
	: (segFlags & splashXPathFlip) ? 1 : -1;
	} else {
	allInter[allInterLen].count = 0;
	}
	++allInterLen;
	return gTrue;
	}

	void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
	int x0, int x1, int y, GBool adjustVertLine) {
	int xx0, xx1, xx, xxMin, xxMax, yy, interEnd;
	Guchar mask;
	SplashColorPtr p;

	memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
	xxMin = aaBuf->getWidth();
	xxMax = -1;
	if (yMin <= yMax) {
	if (splashAASize * y < yMin) {
	interIdx = inter[0];
	} else if (splashAASize * y > yMax) {
	interIdx = inter[yMax - yMin + 1];
	} else {
	interIdx = inter[splashAASize * y - yMin];
	}
	for (yy = 0; yy < splashAASize; ++yy) {
	if (splashAASize * y + yy < yMin) {
	interEnd = inter[0];
	} else if (splashAASize * y + yy > yMax) {
	interEnd = inter[yMax - yMin + 1];
	} else {
	interEnd = inter[splashAASize * y + yy - yMin + 1];
	}
	interCount = 0;
	while (interIdx < interEnd) {
	xx0 = allInter[interIdx].x0;
	xx1 = allInter[interIdx].x1;
	interCount += allInter[interIdx].count;
	++interIdx;
	while (interIdx < interEnd &&
	(allInter[interIdx].x0 <= xx1 \|\|
	(eo ? (interCount & 1) : (interCount != 0)))) {
	if (allInter[interIdx].x1 > xx1) {
	xx1 = allInter[interIdx].x1;
	}
	interCount += allInter[interIdx].count;
	++interIdx;
	}
	if (xx0 < 0) {
	xx0 = 0;
	}
	++xx1;
	if (xx1 > aaBuf->getWidth()) {
	xx1 = aaBuf->getWidth();
	}
	// set [xx0, xx1) to 1
	if (xx0 < xx1) {
	xx = xx0;
	p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
	if (xx & 7) {
	mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
	if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
	mask &= (Guchar)(0xff00 >> (xx1 & 7));
	}
	*p++ \|= mask;
	xx = (xx & ~7) + 8;
	}
	for (; xx + 7 < xx1; xx += 8) {
	*p++ \|= 0xff;
	}
	if (xx < xx1) {
	*p \|= adjustVertLine ? 0xff : (Guchar)(0xff00 >> (xx1 & 7));
	}
	}
	if (xx0 < xxMin) {
	xxMin = xx0;
	}
	if (xx1 > xxMax) {
	xxMax = xx1;
	}
	}
	}
	}
	if (xxMin > xxMax) {
	xxMin = xxMax;
	}
	*x0 = xxMin / splashAASize;
	*x1 = (xxMax - 1) / splashAASize;
	}

	void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
	int x0, int x1, int y) {
	int xx0, xx1, xx, yy, interEnd;
	Guchar mask;
	SplashColorPtr p;

	for (yy = 0; yy < splashAASize; ++yy) {
	xx = x0 splashAASize;
	if (yMin <= yMax) {
	if (splashAASize * y + yy < yMin) {
	interIdx = interEnd = inter[0];
	} else if (splashAASize * y + yy > yMax) {
	interIdx = interEnd = inter[yMax - yMin + 1];
	} else {
	interIdx = inter[splashAASize * y + yy - yMin];
	if (splashAASize * y + yy > yMax) {
	interEnd = inter[yMax - yMin + 1];
	} else {
	interEnd = inter[splashAASize * y + yy - yMin + 1];
	}
	}
	interCount = 0;
	while (interIdx < interEnd && xx < (x1 + 1) splashAASize) {
	xx0 = allInter[interIdx].x0;
	xx1 = allInter[interIdx].x1;
	interCount += allInter[interIdx].count;
	++interIdx;
	while (interIdx < interEnd &&
	(allInter[interIdx].x0 <= xx1 \|\|
	(eo ? (interCount & 1) : (interCount != 0)))) {
	if (allInter[interIdx].x1 > xx1) {
	xx1 = allInter[interIdx].x1;
	}
	interCount += allInter[interIdx].count;
	++interIdx;
	}
	if (xx0 > aaBuf->getWidth()) {
	xx0 = aaBuf->getWidth();
	}
	// set [xx, xx0) to 0
	if (xx < xx0) {
	p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
	if (xx & 7) {
	mask = (Guchar)(0xff00 >> (xx & 7));
	if ((xx & ~7) == (xx0 & ~7)) {
	mask \|= 0xff >> (xx0 & 7);
	}
	*p++ &= mask;
	xx = (xx & ~7) + 8;
	}
	for (; xx + 7 < xx0; xx += 8) {
	*p++ = 0x00;
	}
	if (xx < xx0) {
	*p &= 0xff >> (xx0 & 7);
	}
	}
	if (xx1 >= xx) {
	xx = xx1 + 1;
	}
	}
	}
	xx0 = (x1 + 1) splashAASize;
	if (xx0 > aaBuf->getWidth()) xx0 = aaBuf->getWidth();
	// set [xx, xx0) to 0
	if (xx < xx0 && xx >= 0) {
	p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
	if (xx & 7) {
	mask = (Guchar)(0xff00 >> (xx & 7));
	if ((xx & ~7) == (xx0 & ~7)) {
	mask &= 0xff >> (xx0 & 7);
	}
	*p++ &= mask;
	xx = (xx & ~7) + 8;
	}
	for (; xx + 7 < xx0; xx += 8) {
	*p++ = 0x00;
	}
	if (xx < xx0) {
	*p &= 0xff >> (xx0 & 7);
	}
	}
	}
	}