/src/xpdf-4.06/splash/SplashXPathScanner.cc

Source
//========================================================================
//
// SplashXPathScanner.cc
//
// Copyright 2003-2013 Glyph & Cog, LLC
//
//========================================================================

#include <aconf.h>

#include <stdlib.h>
#include <string.h>
#if HAVE_STD_SORT
#include <algorithm>
#endif
#include "gmem.h"
#include "gmempp.h"
#include "GList.h"
#include "SplashMath.h"
#include "SplashXPath.h"
#include "SplashXPathScanner.h"

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

#if ANTIALIAS_256

#define aaVert  15
#define aaHoriz 17

#else

#define aaVert  4
#define aaHoriz 4

// 4x4 oversampling tends to generate alpha (coverage) values that are
// too high, so we reduce them here. (Yes, this is a kludge.)
static Guchar map16to255[17] = {
  0,
  16 / 2,
  32 / 2,
  48 / 2,
  64 - 32,
  80 - 32,
  96 - 32,
  112 - 32,
  128 - 32,
  143 - 32,
  159 - 32,
  175 - 32,
  191 - 32,
  207 - 32,
  223 - 32,
  239 - 32,
  255
};

#endif

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

SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eo,
               int yMinA, int yMaxA) {
  xPath = xPathA;
  eoMask = eo ? 1 : 0xffffffff;
  yMin = yMinA;
  yMax = yMaxA;
  if (xPath->isRect) {
    rectX0I = splashFloor(xPath->rectX0);
    rectY0I = splashFloor(xPath->rectY0);
    rectX1I = splashFloor(xPath->rectX1);
    rectY1I = splashFloor(xPath->rectY1);
  }

  pre = &preSeg;
  post = &postSeg;
  pre->mx = xPath->xMin - 1;
  post->mx = xPath->xMax + 1;

  resetDone = gFalse;
  resetAA = gFalse;
}

SplashXPathScanner::~SplashXPathScanner() {
}

void SplashXPathScanner::insertSegmentBefore(SplashXPathSeg *s,
               SplashXPathSeg *sNext) {
  SplashXPathSeg *sPrev;

  sPrev = sNext->prev;
  sPrev->next = s;
  s->prev = sPrev;
  s->next = sNext;
  sNext->prev = s;
}

void SplashXPathScanner::removeSegment(SplashXPathSeg *s) {
  SplashXPathSeg *sPrev, *sNext;

  sPrev = s->prev;
  sNext = s->next;
  sPrev->next = sNext;
  sNext->prev = sPrev;
  s->prev = s->next = NULL;
}

void SplashXPathScanner::moveSegmentAfter(SplashXPathSeg *s,
            SplashXPathSeg *sPrev) {
  SplashXPathSeg *sNext;

  s->prev->next = s->next;
  s->next->prev = s->prev;

  sNext = sPrev->next;
  sPrev->next = s;
  s->prev = sPrev;
  s->next = sNext;
  sNext->prev = s;
}

void SplashXPathScanner::reset(GBool aa, GBool aaChanged) {
  SplashXPathSeg *seg;
  SplashCoord y;
  int i;

  //--- initialize segment parameters
  for (i = 0; i < xPath->length; ++i) {
    seg = &xPath->segs[i];
    if (aa) {
      if (aaChanged) {
  seg->iy = splashFloor(seg->y0 * aaVert);
      }
      y = (SplashCoord)(seg->iy + 1) / (SplashCoord)aaVert;
    } else {
      if (aaChanged) {
  seg->iy = splashFloor(seg->y0);
      }
      y = (SplashCoord)(seg->iy + 1);
    }
    seg->sx0 = seg->x0;
    if (seg->y1 <= y) {
      seg->sx1 = seg->x1;
    } else {
      seg->sx1 = seg->x0 + (y - seg->y0) * seg->dxdy;
    }
    seg->mx = (seg->sx0 <= seg->sx1) ? seg->sx0 : seg->sx1;
    seg->prev = seg->next = NULL;
  }

  //--- sort the inactive segments by iy, mx
  if (aaChanged) {
#if HAVE_STD_SORT
    std::sort(xPath->segs, xPath->segs + xPath->length, &SplashXPathSeg::cmpMX);
#else
    qsort(xPath->segs, xPath->length, sizeof(SplashXPathSeg),
    &SplashXPathSeg::cmpMX);
#endif
  }

  //--- initialize the active list
  pre->prev = NULL;
  pre->next = post;
  post->prev = pre;
  post->next = NULL;

  //--- initialize the scan state
  nextSeg = 0;
  if (xPath->length) {
    yBottomI = xPath->segs[0].iy;
    if (aa) {
      yBottomI -= yBottomI % aaVert;
    }
  } else {
    yBottomI = 0;
  }
  yTopI = yBottomI - 1;
  if (aa) {
    yTop = (SplashCoord)yTopI / (SplashCoord)aaVert;
    yBottom = (SplashCoord)yBottomI / (SplashCoord)aaVert;
  } else {
    yTop = (SplashCoord)yTopI;
    yBottom = (SplashCoord)yBottomI;
  }

  resetDone = gTrue;
  resetAA = aa;
}

void SplashXPathScanner::skip(int newYBottomI, GBool aa) {
  SplashXPathSeg *s0, *s1,*s2;
  int iy;

  yTopI = newYBottomI - 1;
  yBottomI = newYBottomI;
  if (aa) {
    yTop = (SplashCoord)yTopI / (SplashCoord)aaVert;
    yBottom = (SplashCoord)yBottomI / (SplashCoord)aaVert;
  } else {
    yTop = (SplashCoord)yTopI;
    yBottom = (SplashCoord)yBottomI;
  }

  //--- remove finished segments; update sx0, sx1, mx for active segments
  s0 = pre->next;
  while (s0 != post) {
    s1 = s0->next;

    // check for a finished segment
    if (s0->y1 < yTop) {
      removeSegment(s0);

    // compute sx0, sx1, mx
    } else {
      if (s0->y0 >= yTop) {
  s0->sx0 = s0->x0;
      } else {
  s0->sx0 = s0->x0 + (yTop - s0->y0) * s0->dxdy;
      }
      if (s0->y1 <= yBottom) {
  s0->sx1 = s0->x1;
      } else {
  s0->sx1 = s0->x0 + (yBottom - s0->y0) * s0->dxdy;
      }
      s0->mx = (s0->sx0 <= s0->sx1) ? s0->sx0 : s0->sx1;
    }

    s0 = s1;
  }

  //--- check for intersections
  s0 = pre->next;
  if (s0 != post) {
    s1 = s0->next;
    while (s1 != post) {
      if (s1->mx < s0->mx) {
  for (s2 = s0->prev; s1->mx < s2->mx; s2 = s2->prev) ;
  moveSegmentAfter(s1, s2);
      } else {
  s0 = s1;
      }
      s1 = s0->next;
    }
  }

  //--- insert new segments with a merge sort
  // - this has to be done one (sub)scanline at a time, because the
  //   inactive list is bin-sorted by (sub)scanline
  while (nextSeg < xPath->length && xPath->segs[nextSeg].iy <= yTopI) {
    // the first inactive segment determines the next scanline to process
    iy = xPath->segs[nextSeg].iy;
    s0 = pre->next;
    do {
      s1 = &xPath->segs[nextSeg];
      ++nextSeg;
      if (s1->y1 < yTop) {
  continue;
      }
      if (s1->y0 >= yTop) {
  s1->sx0 = s1->x0;
      } else {
  s1->sx0 = s1->x0 + (yTop - s1->y0) * s1->dxdy;
      }
      if (s1->y1 <= yBottom) {
  s1->sx1 = s1->x1;
      } else {
  s1->sx1 = s1->x0 + (yBottom - s1->y0) * s1->dxdy;
      }
      s1->mx = (s1->sx0 <= s1->sx1) ? s1->sx0 : s1->sx1;
      insertSegmentBefore(s1, s0);
    } while (nextSeg < xPath->length && xPath->segs[nextSeg].iy <= iy);
  }
}

void SplashXPathScanner::advance(GBool aa) {
  SplashXPathSeg *s, *sNext, *s1;

  yTopI = yBottomI;
  yTop = yBottom;
  yBottomI = yTopI + 1;
  if (aa) {
    yBottom = (SplashCoord)yBottomI / (SplashCoord)aaVert;
  } else {
    yBottom = (SplashCoord)yBottomI;
  }

  s = pre->next;
  while (s != post) {
    sNext = s->next;

    // check for a finished segment
    if (s->y1 < yTop) {
      removeSegment(s);

    } else {

      // compute sx0, sx1, mx
      s->sx0 = s->sx1;
      if (s->y1 <= yBottom) {
  s->sx1 = s->x1;
      } else {
  s->sx1 = s->x0 + (yBottom - s->y0) * s->dxdy;
      }
      s->mx = (s->sx0 <= s->sx1) ? s->sx0 : s->sx1;

      // check for intersection
      if (s->mx < s->prev->mx) {
  for (s1 = s->prev->prev; s->mx < s1->mx; s1 = s1->prev) ;
  moveSegmentAfter(s, s1);
      }
    }

    s = sNext;
  }

  // insert new segments
  s = pre->next;
  while (nextSeg < xPath->length && xPath->segs[nextSeg].iy <= yTopI) {
    s1 = &xPath->segs[nextSeg];
    ++nextSeg;
    while (s1->mx > s->mx) {
      s = s->next;
    }
    insertSegmentBefore(s1, s);
  }
}

void SplashXPathScanner::generatePixels(int x0, int x1, Guchar *line,
          int *xMin, int *xMax) {
  SplashXPathSeg *s;
  int fillCount, x, xEnd, ix0, ix1, t;

  fillCount = 0;
  x = x0 * aaHoriz;
  xEnd = (x1 + 1) * aaHoriz;
  for (s = pre->next; s != post && x < xEnd; s = s->next) {
    ix0 = splashFloor(s->sx0 * aaHoriz);
    ix1 = splashFloor(s->sx1 * aaHoriz);
    if (ix0 > ix1) {
      t = ix0;  ix0 = ix1;  ix1 = t;
    }
    if (!(fillCount & eoMask)) {
      if (ix0 > x) {
  x = ix0;
      }
    }
    if (ix1 >= xEnd) {
      ix1 = xEnd - 1;
    }
    if (x / aaHoriz < *xMin) {
      *xMin = x / aaHoriz;
    }
    if (ix1 / aaHoriz > *xMax) {
      *xMax = ix1 / aaHoriz;
    }
    for (; x <= ix1; ++x) {
      ++line[x / aaHoriz];
    }
    if (s->y0 <= yTop && s->y1 > yTop) {
      fillCount += s->count;
    }
  }
}

void SplashXPathScanner::generatePixelsBinary(int x0, int x1, Guchar *line,
                int *xMin, int *xMax) {
  SplashXPathSeg *s;
  int fillCount, x, xEnd, ix0, ix1, t;

  fillCount = 0;
  x = x0;
  xEnd = x1 + 1;
  for (s = pre->next; s != post && x < xEnd; s = s->next) {
    ix0 = splashFloor(s->sx0);
    ix1 = splashFloor(s->sx1);
    if (ix0 > ix1) {
      t = ix0;  ix0 = ix1;  ix1 = t;
    }
    if (!(fillCount & eoMask)) {
      if (ix0 > x) {
  x = ix0;
      }
    }
    if (ix1 >= xEnd) {
      ix1 = xEnd - 1;
    }
    if (x < *xMin) {
      *xMin = x;
    }
    if (ix1 > *xMax) {
      *xMax = ix1;
    }
    for (; x <= ix1; ++x) {
      line[x] = 255;
    }
    if (s->y0 <= yTop && s->y1 > yTop) {
      fillCount += s->count;
    }
  }
}

void SplashXPathScanner::drawRectangleSpan(Guchar *line, int y,
             int x0, int x1,
             int *xMin, int *xMax) {
  SplashCoord edge;
  Guchar pix;
  int xe, x;

  if (rectX0I > x1 || rectX1I < x0) {
    return;
  }

  *xMin = x0 <= rectX0I ? rectX0I : x0;
  *xMax = rectX1I <= x1 ? rectX1I : x1;

  //--- upper edge
  if (y == rectY0I) {

    // handle a rectangle less than one pixel high
    if (rectY0I == rectY1I) {
      edge = xPath->rectY1 - xPath->rectY0;
    } else {
      edge = (SplashCoord)1 - (xPath->rectY0 - rectY0I);
    }

    // upper left corner
    if (x0 <= rectX0I) {
      pix = (Guchar)splashCeil(edge
             * ((SplashCoord)1 - (xPath->rectX0 - rectX0I))
             * 255);
      if (pix < 16) {
  pix = 16;
      }
      line[rectX0I] = pix;
      x = rectX0I + 1;
    } else {
      x = x0;
    }

    // upper right corner
    if (rectX1I <= x1) {
      pix = (Guchar)splashCeil(edge * (xPath->rectX1 - rectX1I) * 255);
      if (pix < 16) {
  pix = 16;
      }
      line[rectX1I] = pix;
      xe = rectX1I - 1;
    } else {
      xe = x1;
    }

    // upper edge
    pix = (Guchar)splashCeil(edge * 255);
    if (pix < 16) {
      pix = 16;
    }
    for (; x <= xe; ++x) {
      line[x] = pix;
    }

  //--- lower edge
  } else if (y == rectY1I) {
    edge = xPath->rectY1 - rectY1I;

    // lower left corner
    if (x0 <= rectX0I) {
      pix = (Guchar)splashCeil(edge
             * ((SplashCoord)1 - (xPath->rectX0 - rectX0I))
             * 255);
      if (pix < 16) {
  pix = 16;
      }
      line[rectX0I] = pix;
      x = rectX0I + 1;
    } else {
      x = x0;
    }

    // lower right corner
    if (rectX1I <= x1) {
      pix = (Guchar)splashCeil(edge * (xPath->rectX1 - rectX1I) * 255);
      if (pix < 16) {
  pix = 16;
      }
      line[rectX1I] = pix;
      xe = rectX1I - 1;
    } else {
      xe = x1;
    }

    // lower edge
    pix = (Guchar)splashCeil(edge * 255);
    if (pix < 16) {
      pix = 16;
    }
    for (; x <= xe; ++x) {
      line[x] = pix;
    }

  //--- between the upper and lower edges
  } else if (y > rectY0I && y < rectY1I) {

    // left edge
    if (x0 <= rectX0I) {
      pix = (Guchar)splashCeil(((SplashCoord)1 - (xPath->rectX0 - rectX0I))
             * 255);
      if (pix < 16) {
  pix = 16;
      }
      line[rectX0I] = pix;
      x = rectX0I + 1;
    } else {
      x = x0;
    }

    // right edge
    if (rectX1I <= x1) {
      pix = (Guchar)splashCeil((xPath->rectX1 - rectX1I) * 255);
      if (pix < 16) {
  pix = 16;
      }
      line[rectX1I] = pix;
      xe = rectX1I - 1;
    } else {
      xe = x1;
    }

    // middle
    for (; x <= xe; ++x) {
      line[x] = 255;
    }
  }
}

void SplashXPathScanner::drawRectangleSpanBinary(Guchar *line, int y,
             int x0, int x1,
             int *xMin, int *xMax) {
  int xe, x;

  if (y >= rectY0I && y <= rectY1I) {
    if (x0 <= rectX0I) {
      x = rectX0I;
    } else {
      x = x0;
    }
    *xMin = x;
    if (rectX1I <= x1) {
      xe = rectX1I;
    } else {
      xe = x1;
    }
    *xMax = xe;
    for (; x <= xe; ++x) {
      line[x] = 255;
    }
  }
}

void SplashXPathScanner::getSpan(Guchar *line, int y, int x0, int x1,
         int *xMin, int *xMax) {
  int iy, x, k;

  iy = y * aaVert;
  if (!resetDone || !resetAA) {
    reset(gTrue, gTrue);
  } else if (yBottomI > iy) {
    reset(gTrue, gFalse);
  }
  memset(line + x0, 0, x1 - x0 + 1);

  *xMin = x1 + 1;
  *xMax = x0 - 1;

  if (xPath->isRect) {
    drawRectangleSpan(line, y, x0, x1, xMin, xMax);
    return;
  }

  if (yBottomI < iy) {
    skip(iy, gTrue);
  }
  for (k = 0; k < aaVert; ++k, ++iy) {
    advance(gTrue);
    generatePixels(x0, x1, line, xMin, xMax);
  }

#if !ANTIALIAS_256
  for (x = *xMin; x <= *xMax; ++x) {
    line[x] = map16to255[line[x]];
  }
#endif
}

void SplashXPathScanner::getSpanBinary(Guchar *line, int y, int x0, int x1,
               int *xMin, int *xMax) {
  int iy;

  iy = y;
  if (!resetDone || resetAA) {
    reset(gFalse, gTrue);
  } else if (yBottomI > iy) {
    reset(gFalse, gFalse);
  }
  memset(line + x0, 0, x1 - x0 + 1);

  *xMin = x1 + 1;
  *xMax = x0 - 1;

  if (xPath->isRect) {
    drawRectangleSpanBinary(line, y, x0, x1, xMin, xMax);
    return;
  }

  if (yBottomI < iy) {
    skip(iy, gFalse);
  }
  advance(gFalse);
  generatePixelsBinary(x0, x1, line, xMin, xMax);
}

Coverage Report

Created: 2026-02-04 06:14

Line	Count	Source
1		//========================================================================
2		//
3		// SplashXPathScanner.cc
4		//
5		// Copyright 2003-2013 Glyph & Cog, LLC
6		//
7		//========================================================================
8
9		#include <aconf.h>
10
11		#include <stdlib.h>
12		#include <string.h>
13		#if HAVE_STD_SORT
14		#include <algorithm>
15		#endif
16		#include "gmem.h"
17		#include "gmempp.h"
18		#include "GList.h"
19		#include "SplashMath.h"
20		#include "SplashXPath.h"
21		#include "SplashXPathScanner.h"
22
23		//------------------------------------------------------------------------
24
25		#if ANTIALIAS_256
26
27		#define aaVert 15
28		#define aaHoriz 17
29
30		#else
31
32	62.4M	#define aaVert 4
33	6.58M	#define aaHoriz 4
34
35		// 4x4 oversampling tends to generate alpha (coverage) values that are
36		// too high, so we reduce them here. (Yes, this is a kludge.)
37		static Guchar map16to255[17] = {
38		0,
39		16 / 2,
40		32 / 2,
41		48 / 2,
42		64 - 32,
43		80 - 32,
44		96 - 32,
45		112 - 32,
46		128 - 32,
47		143 - 32,
48		159 - 32,
49		175 - 32,
50		191 - 32,
51		207 - 32,
52		223 - 32,
53		239 - 32,
54		255
55		};
56
57		#endif
58
59		//------------------------------------------------------------------------
60
61		SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eo,
62	89.2k	int yMinA, int yMaxA) {
63	89.2k	xPath = xPathA;
64	89.2k	eoMask = eo ? 1 : 0xffffffff;
65	89.2k	yMin = yMinA;
66	89.2k	yMax = yMaxA;
67	89.2k	if (xPath->isRect) {
68	19.5k	rectX0I = splashFloor(xPath->rectX0);
69	19.5k	rectY0I = splashFloor(xPath->rectY0);
70	19.5k	rectX1I = splashFloor(xPath->rectX1);
71	19.5k	rectY1I = splashFloor(xPath->rectY1);
72	19.5k	}
73
74	89.2k	pre = &preSeg;
75	89.2k	post = &postSeg;
76	89.2k	pre->mx = xPath->xMin - 1;
77	89.2k	post->mx = xPath->xMax + 1;
78
79	89.2k	resetDone = gFalse;
80	89.2k	resetAA = gFalse;
81	89.2k	}
82
83	89.2k	SplashXPathScanner::~SplashXPathScanner() {
84	89.2k	}
85
86		void SplashXPathScanner::insertSegmentBefore(SplashXPathSeg *s,
87	2.86M	SplashXPathSeg *sNext) {
88	2.86M	SplashXPathSeg *sPrev;
89
90	2.86M	sPrev = sNext->prev;
91	2.86M	sPrev->next = s;
92	2.86M	s->prev = sPrev;
93	2.86M	s->next = sNext;
94	2.86M	sNext->prev = s;
95	2.86M	}
96
97	1.69M	void SplashXPathScanner::removeSegment(SplashXPathSeg *s) {
98	1.69M	SplashXPathSeg sPrev, sNext;
99
100	1.69M	sPrev = s->prev;
101	1.69M	sNext = s->next;
102	1.69M	sPrev->next = sNext;
103	1.69M	sNext->prev = sPrev;
104	1.69M	s->prev = s->next = NULL;
105	1.69M	}
106
107		void SplashXPathScanner::moveSegmentAfter(SplashXPathSeg *s,
108	190k	SplashXPathSeg *sPrev) {
109	190k	SplashXPathSeg *sNext;
110
111	190k	s->prev->next = s->next;
112	190k	s->next->prev = s->prev;
113
114	190k	sNext = sPrev->next;
115	190k	sPrev->next = s;
116	190k	s->prev = sPrev;
117	190k	s->next = sNext;
118	190k	sNext->prev = s;
119	190k	}
120
121	34.2k	void SplashXPathScanner::reset(GBool aa, GBool aaChanged) {
122	34.2k	SplashXPathSeg *seg;
123	34.2k	SplashCoord y;
124	34.2k	int i;
125
126		//--- initialize segment parameters
127	37.4M	for (i = 0; i < xPath->length; ++i) {
128	37.4M	seg = &xPath->segs[i];
129	37.4M	if (aa) {
130	32.5M	if (aaChanged) {
131	29.6M	seg->iy = splashFloor(seg->y0 * aaVert);
132	29.6M	}
133	32.5M	y = (SplashCoord)(seg->iy + 1) / (SplashCoord)aaVert;
134	32.5M	} else {
135	4.89M	if (aaChanged) {
136	846k	seg->iy = splashFloor(seg->y0);
137	846k	}
138	4.89M	y = (SplashCoord)(seg->iy + 1);
139	4.89M	}
140	37.4M	seg->sx0 = seg->x0;
141	37.4M	if (seg->y1 <= y) {
142	24.2M	seg->sx1 = seg->x1;
143	24.2M	} else {
144	13.1M	seg->sx1 = seg->x0 + (y - seg->y0) * seg->dxdy;
145	13.1M	}
146	37.4M	seg->mx = (seg->sx0 <= seg->sx1) ? seg->sx0 : seg->sx1;
147	37.4M	seg->prev = seg->next = NULL;
148	37.4M	}
149
150		//--- sort the inactive segments by iy, mx
151	34.2k	if (aaChanged) {
152	27.5k	#if HAVE_STD_SORT
153	27.5k	std::sort(xPath->segs, xPath->segs + xPath->length, &SplashXPathSeg::cmpMX);
154		#else
155		qsort(xPath->segs, xPath->length, sizeof(SplashXPathSeg),
156		&SplashXPathSeg::cmpMX);
157		#endif
158	27.5k	}
159
160		//--- initialize the active list
161	34.2k	pre->prev = NULL;
162	34.2k	pre->next = post;
163	34.2k	post->prev = pre;
164	34.2k	post->next = NULL;
165
166		//--- initialize the scan state
167	34.2k	nextSeg = 0;
168	34.2k	if (xPath->length) {
169	28.8k	yBottomI = xPath->segs[0].iy;
170	28.8k	if (aa) {
171	26.1k	yBottomI -= yBottomI % aaVert;
172	26.1k	}
173	28.8k	} else {
174	5.46k	yBottomI = 0;
175	5.46k	}
176	34.2k	yTopI = yBottomI - 1;
177	34.2k	if (aa) {
178	31.6k	yTop = (SplashCoord)yTopI / (SplashCoord)aaVert;
179	31.6k	yBottom = (SplashCoord)yBottomI / (SplashCoord)aaVert;
180	31.6k	} else {
181	2.60k	yTop = (SplashCoord)yTopI;
182	2.60k	yBottom = (SplashCoord)yBottomI;
183	2.60k	}
184
185	34.2k	resetDone = gTrue;
186	34.2k	resetAA = aa;
187	34.2k	}
188
189	14.6k	void SplashXPathScanner::skip(int newYBottomI, GBool aa) {
190	14.6k	SplashXPathSeg s0, s1,*s2;
191	14.6k	int iy;
192
193	14.6k	yTopI = newYBottomI - 1;
194	14.6k	yBottomI = newYBottomI;
195	14.6k	if (aa) {
196	12.2k	yTop = (SplashCoord)yTopI / (SplashCoord)aaVert;
197	12.2k	yBottom = (SplashCoord)yBottomI / (SplashCoord)aaVert;
198	12.2k	} else {
199	2.36k	yTop = (SplashCoord)yTopI;
200	2.36k	yBottom = (SplashCoord)yBottomI;
201	2.36k	}
202
203		//--- remove finished segments; update sx0, sx1, mx for active segments
204	14.6k	s0 = pre->next;
205	14.6k	while (s0 != post) {
206	0	s1 = s0->next;
207
208		// check for a finished segment
209	0	if (s0->y1 < yTop) {
210	0	removeSegment(s0);
211
212		// compute sx0, sx1, mx
213	0	} else {
214	0	if (s0->y0 >= yTop) {
215	0	s0->sx0 = s0->x0;
216	0	} else {
217	0	s0->sx0 = s0->x0 + (yTop - s0->y0) * s0->dxdy;
218	0	}
219	0	if (s0->y1 <= yBottom) {
220	0	s0->sx1 = s0->x1;
221	0	} else {
222	0	s0->sx1 = s0->x0 + (yBottom - s0->y0) * s0->dxdy;
223	0	}
224	0	s0->mx = (s0->sx0 <= s0->sx1) ? s0->sx0 : s0->sx1;
225	0	}
226
227	0	s0 = s1;
228	0	}
229
230		//--- check for intersections
231	14.6k	s0 = pre->next;
232	14.6k	if (s0 != post) {
233	0	s1 = s0->next;
234	0	while (s1 != post) {
235	0	if (s1->mx < s0->mx) {
236	0	for (s2 = s0->prev; s1->mx < s2->mx; s2 = s2->prev) ;
237	0	moveSegmentAfter(s1, s2);
238	0	} else {
239	0	s0 = s1;
240	0	}
241	0	s1 = s0->next;
242	0	}
243	0	}
244
245		//--- insert new segments with a merge sort
246		// - this has to be done one (sub)scanline at a time, because the
247		// inactive list is bin-sorted by (sub)scanline
248	4.82M	while (nextSeg < xPath->length && xPath->segs[nextSeg].iy <= yTopI) {
249		// the first inactive segment determines the next scanline to process
250	4.80M	iy = xPath->segs[nextSeg].iy;
251	4.80M	s0 = pre->next;
252	14.1M	do {
253	14.1M	s1 = &xPath->segs[nextSeg];
254	14.1M	++nextSeg;
255	14.1M	if (s1->y1 < yTop) {
256	13.2M	continue;
257	13.2M	}
258	883k	if (s1->y0 >= yTop) {
259	2.17k	s1->sx0 = s1->x0;
260	881k	} else {
261	881k	s1->sx0 = s1->x0 + (yTop - s1->y0) * s1->dxdy;
262	881k	}
263	883k	if (s1->y1 <= yBottom) {
264	12.1k	s1->sx1 = s1->x1;
265	871k	} else {
266	871k	s1->sx1 = s1->x0 + (yBottom - s1->y0) * s1->dxdy;
267	871k	}
268	883k	s1->mx = (s1->sx0 <= s1->sx1) ? s1->sx0 : s1->sx1;
269	883k	insertSegmentBefore(s1, s0);
270	14.1M	} while (nextSeg < xPath->length && xPath->segs[nextSeg].iy <= iy);
271	4.80M	}
272	14.6k	}
273
274	80.2k	void SplashXPathScanner::advance(GBool aa) {
275	80.2k	SplashXPathSeg s, sNext, *s1;
276
277	80.2k	yTopI = yBottomI;
278	80.2k	yTop = yBottom;
279	80.2k	yBottomI = yTopI + 1;
280	80.2k	if (aa) {
281	77.6k	yBottom = (SplashCoord)yBottomI / (SplashCoord)aaVert;
282	77.6k	} else {
283	2.60k	yBottom = (SplashCoord)yBottomI;
284	2.60k	}
285
286	80.2k	s = pre->next;
287	5.25M	while (s != post) {
288	5.17M	sNext = s->next;
289
290		// check for a finished segment
291	5.17M	if (s->y1 < yTop) {
292	1.69M	removeSegment(s);
293
294	3.47M	} else {
295
296		// compute sx0, sx1, mx
297	3.47M	s->sx0 = s->sx1;
298	3.47M	if (s->y1 <= yBottom) {
299	10.3k	s->sx1 = s->x1;
300	3.46M	} else {
301	3.46M	s->sx1 = s->x0 + (yBottom - s->y0) * s->dxdy;
302	3.46M	}
303	3.47M	s->mx = (s->sx0 <= s->sx1) ? s->sx0 : s->sx1;
304
305		// check for intersection
306	3.47M	if (s->mx < s->prev->mx) {
307	25.3M	for (s1 = s->prev->prev; s->mx < s1->mx; s1 = s1->prev) ;
308	190k	moveSegmentAfter(s, s1);
309	190k	}
310	3.47M	}
311
312	5.17M	s = sNext;
313	5.17M	}
314
315		// insert new segments
316	80.2k	s = pre->next;
317	2.05M	while (nextSeg < xPath->length && xPath->segs[nextSeg].iy <= yTopI) {
318	1.97M	s1 = &xPath->segs[nextSeg];
319	1.97M	++nextSeg;
320	1.99M	while (s1->mx > s->mx) {
321	17.2k	s = s->next;
322	17.2k	}
323	1.97M	insertSegmentBefore(s1, s);
324	1.97M	}
325	80.2k	}
326
327		void SplashXPathScanner::generatePixels(int x0, int x1, Guchar *line,
328	77.6k	int xMin, int xMax) {
329	77.6k	SplashXPathSeg *s;
330	77.6k	int fillCount, x, xEnd, ix0, ix1, t;
331
332	77.6k	fillCount = 0;
333	77.6k	x = x0 * aaHoriz;
334	77.6k	xEnd = (x1 + 1) * aaHoriz;
335	1.66M	for (s = pre->next; s != post && x < xEnd; s = s->next) {
336	1.58M	ix0 = splashFloor(s->sx0 * aaHoriz);
337	1.58M	ix1 = splashFloor(s->sx1 * aaHoriz);
338	1.58M	if (ix0 > ix1) {
339	591k	t = ix0; ix0 = ix1; ix1 = t;
340	591k	}
341	1.58M	if (!(fillCount & eoMask)) {
342	280k	if (ix0 > x) {
343	11.4k	x = ix0;
344	11.4k	}
345	280k	}
346	1.58M	if (ix1 >= xEnd) {
347	16.7k	ix1 = xEnd - 1;
348	16.7k	}
349	1.58M	if (x / aaHoriz < *xMin) {
350	12.5k	*xMin = x / aaHoriz;
351	12.5k	}
352	1.58M	if (ix1 / aaHoriz > *xMax) {
353	12.6k	*xMax = ix1 / aaHoriz;
354	12.6k	}
355	1.64M	for (; x <= ix1; ++x) {
356	58.8k	++line[x / aaHoriz];
357	58.8k	}
358	1.58M	if (s->y0 <= yTop && s->y1 > yTop) {
359	1.55M	fillCount += s->count;
360	1.55M	}
361	1.58M	}
362	77.6k	}
363
364		void SplashXPathScanner::generatePixelsBinary(int x0, int x1, Guchar *line,
365	2.60k	int xMin, int xMax) {
366	2.60k	SplashXPathSeg *s;
367	2.60k	int fillCount, x, xEnd, ix0, ix1, t;
368
369	2.60k	fillCount = 0;
370	2.60k	x = x0;
371	2.60k	xEnd = x1 + 1;
372	11.7k	for (s = pre->next; s != post && x < xEnd; s = s->next) {
373	9.16k	ix0 = splashFloor(s->sx0);
374	9.16k	ix1 = splashFloor(s->sx1);
375	9.16k	if (ix0 > ix1) {
376	1.96k	t = ix0; ix0 = ix1; ix1 = t;
377	1.96k	}
378	9.16k	if (!(fillCount & eoMask)) {
379	3.56k	if (ix0 > x) {
380	28	x = ix0;
381	28	}
382	3.56k	}
383	9.16k	if (ix1 >= xEnd) {
384	507	ix1 = xEnd - 1;
385	507	}
386	9.16k	if (x < *xMin) {
387	2.54k	*xMin = x;
388	2.54k	}
389	9.16k	if (ix1 > *xMax) {
390	2.49k	*xMax = ix1;
391	2.49k	}
392	11.6k	for (; x <= ix1; ++x) {
393	2.46k	line[x] = 255;
394	2.46k	}
395	9.16k	if (s->y0 <= yTop && s->y1 > yTop) {
396	6.34k	fillCount += s->count;
397	6.34k	}
398	9.16k	}
399	2.60k	}
400
401		void SplashXPathScanner::drawRectangleSpan(Guchar *line, int y,
402		int x0, int x1,
403	12.2k	int xMin, int xMax) {
404	12.2k	SplashCoord edge;
405	12.2k	Guchar pix;
406	12.2k	int xe, x;
407
408	12.2k	if (rectX0I > x1 \|\| rectX1I < x0) {
409	196	return;
410	196	}
411
412	12.0k	*xMin = x0 <= rectX0I ? rectX0I : x0;
413	12.0k	*xMax = rectX1I <= x1 ? rectX1I : x1;
414
415		//--- upper edge
416	12.0k	if (y == rectY0I) {
417
418		// handle a rectangle less than one pixel high
419	2.54k	if (rectY0I == rectY1I) {
420	1.90k	edge = xPath->rectY1 - xPath->rectY0;
421	1.90k	} else {
422	646	edge = (SplashCoord)1 - (xPath->rectY0 - rectY0I);
423	646	}
424
425		// upper left corner
426	2.54k	if (x0 <= rectX0I) {
427	2.54k	pix = (Guchar)splashCeil(edge
428	2.54k	* ((SplashCoord)1 - (xPath->rectX0 - rectX0I))
429	2.54k	* 255);
430	2.54k	if (pix < 16) {
431	1.89k	pix = 16;
432	1.89k	}
433	2.54k	line[rectX0I] = pix;
434	2.54k	x = rectX0I + 1;
435	2.54k	} else {
436	8	x = x0;
437	8	}
438
439		// upper right corner
440	2.54k	if (rectX1I <= x1) {
441	2.52k	pix = (Guchar)splashCeil(edge * (xPath->rectX1 - rectX1I) * 255);
442	2.52k	if (pix < 16) {
443	2.51k	pix = 16;
444	2.51k	}
445	2.52k	line[rectX1I] = pix;
446	2.52k	xe = rectX1I - 1;
447	2.52k	} else {
448	22	xe = x1;
449	22	}
450
451		// upper edge
452	2.54k	pix = (Guchar)splashCeil(edge * 255);
453	2.54k	if (pix < 16) {
454	1.90k	pix = 16;
455	1.90k	}
456	2.55k	for (; x <= xe; ++x) {
457	8	line[x] = pix;
458	8	}
459
460		//--- lower edge
461	9.52k	} else if (y == rectY1I) {
462	151	edge = xPath->rectY1 - rectY1I;
463
464		// lower left corner
465	151	if (x0 <= rectX0I) {
466	151	pix = (Guchar)splashCeil(edge
467	151	* ((SplashCoord)1 - (xPath->rectX0 - rectX0I))
468	151	* 255);
469	151	if (pix < 16) {
470	144	pix = 16;
471	144	}
472	151	line[rectX0I] = pix;
473	151	x = rectX0I + 1;
474	151	} else {
475	0	x = x0;
476	0	}
477
478		// lower right corner
479	151	if (rectX1I <= x1) {
480	151	pix = (Guchar)splashCeil(edge * (xPath->rectX1 - rectX1I) * 255);
481	151	if (pix < 16) {
482	151	pix = 16;
483	151	}
484	151	line[rectX1I] = pix;
485	151	xe = rectX1I - 1;
486	151	} else {
487	0	xe = x1;
488	0	}
489
490		// lower edge
491	151	pix = (Guchar)splashCeil(edge * 255);
492	151	if (pix < 16) {
493	144	pix = 16;
494	144	}
495	151	for (; x <= xe; ++x) {
496	0	line[x] = pix;
497	0	}
498
499		//--- between the upper and lower edges
500	9.37k	} else if (y > rectY0I && y < rectY1I) {
501
502		// left edge
503	9.19k	if (x0 <= rectX0I) {
504	8.10k	pix = (Guchar)splashCeil(((SplashCoord)1 - (xPath->rectX0 - rectX0I))
505	8.10k	* 255);
506	8.10k	if (pix < 16) {
507	0	pix = 16;
508	0	}
509	8.10k	line[rectX0I] = pix;
510	8.10k	x = rectX0I + 1;
511	8.10k	} else {
512	1.09k	x = x0;
513	1.09k	}
514
515		// right edge
516	9.19k	if (rectX1I <= x1) {
517	4.09k	pix = (Guchar)splashCeil((xPath->rectX1 - rectX1I) * 255);
518	4.09k	if (pix < 16) {
519	4.01k	pix = 16;
520	4.01k	}
521	4.09k	line[rectX1I] = pix;
522	4.09k	xe = rectX1I - 1;
523	5.10k	} else {
524	5.10k	xe = x1;
525	5.10k	}
526
527		// middle
528	10.2k	for (; x <= xe; ++x) {
529	1.09k	line[x] = 255;
530	1.09k	}
531	9.19k	}
532	12.0k	}
533
534		void SplashXPathScanner::drawRectangleSpanBinary(Guchar *line, int y,
535		int x0, int x1,
536	0	int xMin, int xMax) {
537	0	int xe, x;
538
539	0	if (y >= rectY0I && y <= rectY1I) {
540	0	if (x0 <= rectX0I) {
541	0	x = rectX0I;
542	0	} else {
543	0	x = x0;
544	0	}
545	0	*xMin = x;
546	0	if (rectX1I <= x1) {
547	0	xe = rectX1I;
548	0	} else {
549	0	xe = x1;
550	0	}
551	0	*xMax = xe;
552	0	for (; x <= xe; ++x) {
553	0	line[x] = 255;
554	0	}
555	0	}
556	0	}
557
558		void SplashXPathScanner::getSpan(Guchar *line, int y, int x0, int x1,
559	31.6k	int xMin, int xMax) {
560	31.6k	int iy, x, k;
561
562	31.6k	iy = y * aaVert;
563	31.6k	if (!resetDone \|\| !resetAA) {
564	27.1k	reset(gTrue, gTrue);
565	27.1k	} else if (yBottomI > iy) {
566	4.51k	reset(gTrue, gFalse);
567	4.51k	}
568	31.6k	memset(line + x0, 0, x1 - x0 + 1);
569
570	31.6k	*xMin = x1 + 1;
571	31.6k	*xMax = x0 - 1;
572
573	31.6k	if (xPath->isRect) {
574	12.2k	drawRectangleSpan(line, y, x0, x1, xMin, xMax);
575	12.2k	return;
576	12.2k	}
577
578	19.4k	if (yBottomI < iy) {
579	12.2k	skip(iy, gTrue);
580	12.2k	}
581	97.0k	for (k = 0; k < aaVert; ++k, ++iy) {
582	77.6k	advance(gTrue);
583	77.6k	generatePixels(x0, x1, line, xMin, xMax);
584	77.6k	}
585
586	19.4k	#if !ANTIALIAS_256
587	30.9k	for (x = xMin; x <= xMax; ++x) {
588	11.5k	line[x] = map16to255[line[x]];
589	11.5k	}
590	19.4k	#endif
591	19.4k	}
592
593		void SplashXPathScanner::getSpanBinary(Guchar *line, int y, int x0, int x1,
594	2.60k	int xMin, int xMax) {
595	2.60k	int iy;
596
597	2.60k	iy = y;
598	2.60k	if (!resetDone \|\| resetAA) {
599	364	reset(gFalse, gTrue);
600	2.24k	} else if (yBottomI > iy) {
601	2.24k	reset(gFalse, gFalse);
602	2.24k	}
603	2.60k	memset(line + x0, 0, x1 - x0 + 1);
604
605	2.60k	*xMin = x1 + 1;
606	2.60k	*xMax = x0 - 1;
607
608	2.60k	if (xPath->isRect) {
609	0	drawRectangleSpanBinary(line, y, x0, x1, xMin, xMax);
610	0	return;
611	0	}
612
613	2.60k	if (yBottomI < iy) {
614	2.36k	skip(iy, gFalse);
615	2.36k	}
616	2.60k	advance(gFalse);
617	2.60k	generatePixelsBinary(x0, x1, line, xMin, xMax);
618	2.60k	}