Initial revision

1 files changed, 271 insertions, 0 deletions

diff --git a/pdf/splash/SplashXPathScanner.cc b/pdf/splash/SplashXPathScanner.cc
new file mode 100644
index 0000000..c93cc49
--- /dev/null
+++ b/pdf/splash/SplashXPathScanner.cc
@@ -0,0 +1,271 @@
+//========================================================================
+//
+// SplashXPathScanner.cc
+//
+//========================================================================
+
+#include <aconf.h>
+
+#ifdef USE_GCC_PRAGMAS
+#pragma implementation
+#endif
+
+#include <stdlib.h>
+#include "gmem.h"
+#include "SplashMath.h"
+#include "SplashXPath.h"
+#include "SplashXPathScanner.h"
+
+//------------------------------------------------------------------------
+
+struct SplashIntersect {
+  int x0, x1;			// intersection of segment with [y, y+1)
+  int count;			// EO/NZWN counter increment
+};
+
+static int cmpIntersect(const void *p0, const void *p1) {
+  return ((SplashIntersect *)p0)->x0 - ((SplashIntersect *)p1)->x0;
+}
+
+//------------------------------------------------------------------------
+// SplashXPathScanner
+//------------------------------------------------------------------------
+
+SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA) {
+  SplashXPathSeg *seg;
+  SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
+  int i;
+
+  xPath = xPathA;
+  eo = eoA;
+
+  // compute the bbox
+  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);
+
+  interY = 0;
+  xPathIdx = 0;
+  inter = NULL;
+  interLen = interSize = 0;
+  computeIntersections(yMin);
+}
+
+SplashXPathScanner::~SplashXPathScanner() {
+  gfree(inter);
+}
+
+void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
+  if (interY != y) {
+    computeIntersections(y);
+  }
+  if (interLen > 0) {
+    *spanXMin = inter[0].x0;
+    *spanXMax = inter[interLen - 1].x1;
+  } else {
+    *spanXMin = xMax + 1;
+    *spanXMax = xMax;
+  }
+}
+
+GBool SplashXPathScanner::test(int x, int y) {
+  int count, i;
+
+  if (interY != y) {
+    computeIntersections(y);
+  }
+  count = 0;
+  for (i = 0; i < interLen && inter[i].x0 <= x; ++i) {
+    if (x <= inter[i].x1) {
+      return gTrue;
+    }
+    count += inter[i].count;
+  }
+  return eo ? (count & 1) : (count != 0);
+}
+
+GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
+  int count, xx1, i;
+
+  if (interY != y) {
+    computeIntersections(y);
+  }
+
+  count = 0;
+  for (i = 0; i < interLen && inter[i].x1 < x0; ++i) {
+    count += inter[i].count;
+  }
+
+  // invariant: the subspan [x0,xx1] is inside the path
+  xx1 = x0 - 1;
+  while (xx1 < x1) {
+    if (i >= interLen) {
+      return gFalse;
+    }
+    if (inter[i].x0 > xx1 + 1 &&
+	!(eo ? (count & 1) : (count != 0))) {
+      return gFalse;
+    }
+    if (inter[i].x1 > xx1) {
+      xx1 = inter[i].x1;
+    }
+    count += inter[i].count;
+    ++i;
+  }
+
+  return gTrue;
+}
+
+GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
+  int xx0, xx1;
+
+  if (interY != y) {
+    computeIntersections(y);
+  }
+  if (interIdx >= interLen) {
+    return gFalse;
+  }
+  xx0 = inter[interIdx].x0;
+  xx1 = inter[interIdx].x1;
+  interCount += inter[interIdx].count;
+  ++interIdx;
+  while (interIdx < interLen &&
+	 (inter[interIdx].x0 <= xx1 ||
+	  (eo ? (interCount & 1) : (interCount != 0)))) {
+    if (inter[interIdx].x1 > xx1) {
+      xx1 = inter[interIdx].x1;
+    }
+    interCount += inter[interIdx].count;
+    ++interIdx;
+  }
+  *x0 = xx0;
+  *x1 = xx1;
+  return gTrue;
+}
+
+void SplashXPathScanner::computeIntersections(int y) {
+  SplashCoord ySegMin, ySegMax, xx0, xx1;
+  SplashXPathSeg *seg;
+  int i, j;
+
+  // find the first segment that intersects [y, y+1)
+  i = (y >= interY) ? xPathIdx : 0;
+  while (i < xPath->length &&
+	 xPath->segs[i].y0 < y && xPath->segs[i].y1 < y) {
+    ++i;
+  }
+  xPathIdx = i;
+
+  // find all of the segments that intersect [y, y+1) and create an
+  // Intersect element for each one
+  interLen = 0;
+  for (j = i; j < xPath->length; ++j) {
+    seg = &xPath->segs[j];
+    if (seg->flags & splashXPathFlip) {
+      ySegMin = seg->y1;
+      ySegMax = seg->y0;
+    } else {
+      ySegMin = seg->y0;
+      ySegMax = seg->y1;
+    }
+
+    // ensure that:      ySegMin < y+1
+    //              y <= ySegMax
+    if (ySegMin >= y + 1) {
+      break;
+    }
+    if (ySegMax < y) {
+      continue;
+    }
+
+    if (interLen == interSize) {
+      if (interSize == 0) {
+	interSize = 16;
+      } else {
+	interSize *= 2;
+      }
+      inter = (SplashIntersect *)grealloc(inter,
+					  interSize * sizeof(SplashIntersect));
+    }
+
+    if (seg->flags & splashXPathHoriz) {
+      xx0 = seg->x0;
+      xx1 = seg->x1;
+    } else if (seg->flags & splashXPathVert) {
+      xx0 = xx1 = seg->x0;
+    } else {
+      if (ySegMin <= y) {
+	// intersection with top edge
+	xx0 = seg->x0 + (y - seg->y0) * seg->dxdy;
+      } else {
+	// x coord of segment endpoint with min y coord
+	xx0 = (seg->flags & splashXPathFlip) ? seg->x1 : seg->x0;
+      }
+      if (ySegMax >= y + 1) {
+	// intersection with bottom edge
+	xx1 = seg->x0 + (y + 1 - seg->y0) * seg->dxdy;
+      } else {
+	// x coord of segment endpoint with max y coord
+	xx1 = (seg->flags & splashXPathFlip) ? seg->x0 : seg->x1;
+      }
+    }
+    if (xx0 < xx1) {
+      inter[interLen].x0 = splashFloor(xx0);
+      inter[interLen].x1 = splashFloor(xx1);
+    } else {
+      inter[interLen].x0 = splashFloor(xx1);
+      inter[interLen].x1 = splashFloor(xx0);
+    }
+    if (ySegMin <= y && y < ySegMax && !(seg->flags & splashXPathHoriz)) {
+      inter[interLen].count = eo ? 1
+	                         : (seg->flags & splashXPathFlip) ? 1 : -1;
+    } else {
+      inter[interLen].count = 0;
+    }
+    ++interLen;
+  }
+
+  qsort(inter, interLen, sizeof(SplashIntersect), &cmpIntersect);
+
+  interY = y;
+  interIdx = 0;
+  interCount = 0;
+}