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

Source (jump to first uncovered line)
//========================================================================
//
// SplashXPathScanner.cc
//
// Copyright 2003-2013 Glyph & Cog, LLC
//
//========================================================================

#include <aconf.h>

#ifdef USE_GCC_PRAGMAS
#pragma implementation
#endif

#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: 2023-09-25 06:41

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