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

Source (jump to first uncovered line)
//========================================================================
//
// 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

static Guchar map16to255[17] = {
  0,
  16,
  32,
  48,
  64,
  80,
  96,
  112,
  128,
  143,
  159,
  175,
  191,
  207,
  223,
  239,
  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: 2025-07-11 07:47

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