1 //========================================================================
2 //
3 // SplashXPathScanner.cc
4 //
5 //========================================================================
6 
7 //========================================================================
8 //
9 // Modified under the Poppler project - http://poppler.freedesktop.org
10 //
11 // All changes made under the Poppler project to this file are licensed
12 // under GPL version 2 or later
13 //
14 // Copyright (C) 2008, 2010, 2014 Albert Astals Cid <aacid@kde.org>
15 // Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
16 // Copyright (C) 2013, 2014 Thomas Freitag <Thomas.Freitag@alfa.de>
17 //
18 // To see a description of the changes please see the Changelog file that
19 // came with your tarball or type make ChangeLog if you are building from git
20 //
21 //========================================================================
22 
23 #include <config.h>
24 
25 #ifdef USE_GCC_PRAGMAS
26 #pragma implementation
27 #endif
28 
29 #include <stdlib.h>
30 #include <string.h>
31 #include <algorithm>
32 #include "goo/gmem.h"
33 #include "SplashMath.h"
34 #include "SplashXPath.h"
35 #include "SplashBitmap.h"
36 #include "SplashXPathScanner.h"
37 
38 //------------------------------------------------------------------------
39 
40 struct SplashIntersect {
41   int y;
42   int x0, x1;			// intersection of segment with [y, y+1)
43   int count;			// EO/NZWN counter increment
44 };
45 
46 struct cmpIntersectFunctor {
operator ()cmpIntersectFunctor47   bool operator()(const SplashIntersect &i0, const SplashIntersect &i1) {
48     return (i0.y != i1.y) ? (i0.y < i1.y) : (i0.x0 < i1.x0);
49   }
50 };
51 
52 //------------------------------------------------------------------------
53 // SplashXPathScanner
54 //------------------------------------------------------------------------
55 
SplashXPathScanner(SplashXPath * xPathA,GBool eoA,int clipYMin,int clipYMax)56 SplashXPathScanner::SplashXPathScanner(SplashXPath *xPathA, GBool eoA,
57 				       int clipYMin, int clipYMax) {
58   SplashXPathSeg *seg;
59   SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
60   int i;
61 
62   xPath = xPathA;
63   eo = eoA;
64   partialClip = gFalse;
65 
66   // compute the bbox
67   if (xPath->length == 0) {
68     xMin = yMin = 1;
69     xMax = yMax = 0;
70   } else {
71     seg = &xPath->segs[0];
72     if (seg->x0 <= seg->x1) {
73       xMinFP = seg->x0;
74       xMaxFP = seg->x1;
75     } else {
76       xMinFP = seg->x1;
77       xMaxFP = seg->x0;
78     }
79     if (seg->flags & splashXPathFlip) {
80       yMinFP = seg->y1;
81       yMaxFP = seg->y0;
82     } else {
83       yMinFP = seg->y0;
84       yMaxFP = seg->y1;
85     }
86     for (i = 1; i < xPath->length; ++i) {
87       seg = &xPath->segs[i];
88       if (seg->x0 < xMinFP) {
89 	xMinFP = seg->x0;
90       } else if (seg->x0 > xMaxFP) {
91 	xMaxFP = seg->x0;
92       }
93       if (seg->x1 < xMinFP) {
94 	xMinFP = seg->x1;
95       } else if (seg->x1 > xMaxFP) {
96 	xMaxFP = seg->x1;
97       }
98       if (seg->flags & splashXPathFlip) {
99 	if (seg->y0 > yMaxFP) {
100 	  yMaxFP = seg->y0;
101 	}
102       } else {
103 	if (seg->y1 > yMaxFP) {
104 	  yMaxFP = seg->y1;
105 	}
106       }
107     }
108     xMin = splashFloor(xMinFP);
109     xMax = splashFloor(xMaxFP);
110     yMin = splashFloor(yMinFP);
111     yMax = splashFloor(yMaxFP);
112     if (clipYMin > yMin) {
113       yMin = clipYMin;
114       partialClip = gTrue;
115     }
116     if (clipYMax < yMax) {
117       yMax = clipYMax;
118       partialClip = gTrue;
119     }
120   }
121 
122   allInter = NULL;
123   inter = NULL;
124   computeIntersections();
125   interY = yMin - 1;
126 }
127 
~SplashXPathScanner()128 SplashXPathScanner::~SplashXPathScanner() {
129   gfree(inter);
130   gfree(allInter);
131 }
132 
getBBoxAA(int * xMinA,int * yMinA,int * xMaxA,int * yMaxA)133 void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA,
134 				   int *xMaxA, int *yMaxA) {
135   *xMinA = xMin / splashAASize;
136   *yMinA = yMin / splashAASize;
137   *xMaxA = xMax / splashAASize;
138   *yMaxA = yMax / splashAASize;
139 }
140 
getSpanBounds(int y,int * spanXMin,int * spanXMax)141 void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) {
142   int interBegin, interEnd, xx, i;
143 
144   if (y < yMin || y > yMax) {
145     interBegin = interEnd = 0;
146   } else {
147     interBegin = inter[y - yMin];
148     interEnd = inter[y - yMin + 1];
149   }
150   if (interBegin < interEnd) {
151     *spanXMin = allInter[interBegin].x0;
152     xx = allInter[interBegin].x1;
153     for (i = interBegin + 1; i < interEnd; ++i) {
154       if (allInter[i].x1 > xx) {
155 	xx = allInter[i].x1;
156       }
157     }
158     *spanXMax = xx;
159   } else {
160     *spanXMin = xMax + 1;
161     *spanXMax = xMax;
162   }
163 }
164 
test(int x,int y)165 GBool SplashXPathScanner::test(int x, int y) {
166   int interBegin, interEnd, count, i;
167 
168   if (y < yMin || y > yMax) {
169     return gFalse;
170   }
171   interBegin = inter[y - yMin];
172   interEnd = inter[y - yMin + 1];
173   count = 0;
174   for (i = interBegin; i < interEnd && allInter[i].x0 <= x; ++i) {
175     if (x <= allInter[i].x1) {
176       return gTrue;
177     }
178     count += allInter[i].count;
179   }
180   return eo ? (count & 1) : (count != 0);
181 }
182 
testSpan(int x0,int x1,int y)183 GBool SplashXPathScanner::testSpan(int x0, int x1, int y) {
184   int interBegin, interEnd, count, xx1, i;
185 
186   if (y < yMin || y > yMax) {
187     return gFalse;
188   }
189   interBegin = inter[y - yMin];
190   interEnd = inter[y - yMin + 1];
191   count = 0;
192   for (i = interBegin; i < interEnd && allInter[i].x1 < x0; ++i) {
193     count += allInter[i].count;
194   }
195 
196   // invariant: the subspan [x0,xx1] is inside the path
197   xx1 = x0 - 1;
198   while (xx1 < x1) {
199     if (i >= interEnd) {
200       return gFalse;
201     }
202     if (allInter[i].x0 > xx1 + 1 &&
203 	!(eo ? (count & 1) : (count != 0))) {
204       return gFalse;
205     }
206     if (allInter[i].x1 > xx1) {
207       xx1 = allInter[i].x1;
208     }
209     count += allInter[i].count;
210     ++i;
211   }
212 
213   return gTrue;
214 }
215 
getNextSpan(int y,int * x0,int * x1)216 GBool SplashXPathScanner::getNextSpan(int y, int *x0, int *x1) {
217   int interEnd, xx0, xx1;
218 
219   if (y < yMin || y > yMax) {
220     return gFalse;
221   }
222   if (interY != y) {
223     interY = y;
224     interIdx = inter[y - yMin];
225     interCount = 0;
226   }
227   interEnd = inter[y - yMin + 1];
228   if (interIdx >= interEnd) {
229     return gFalse;
230   }
231   xx0 = allInter[interIdx].x0;
232   xx1 = allInter[interIdx].x1;
233   interCount += allInter[interIdx].count;
234   ++interIdx;
235   while (interIdx < interEnd &&
236 	 (allInter[interIdx].x0 <= xx1 ||
237 	  (eo ? (interCount & 1) : (interCount != 0)))) {
238     if (allInter[interIdx].x1 > xx1) {
239       xx1 = allInter[interIdx].x1;
240     }
241     interCount += allInter[interIdx].count;
242     ++interIdx;
243   }
244   *x0 = xx0;
245   *x1 = xx1;
246   return gTrue;
247 }
248 
computeIntersections()249 void SplashXPathScanner::computeIntersections() {
250   SplashXPathSeg *seg;
251   SplashCoord segXMin, segXMax, segYMin, segYMax, xx0, xx1;
252   int x, y, y0, y1, i;
253 
254   if (yMin > yMax) {
255     return;
256   }
257 
258   // build the list of all intersections
259   allInterLen = 0;
260   allInterSize = 16;
261   allInter = (SplashIntersect *)gmallocn(allInterSize,
262 					 sizeof(SplashIntersect));
263   for (i = 0; i < xPath->length; ++i) {
264     seg = &xPath->segs[i];
265     if (seg->flags & splashXPathFlip) {
266       segYMin = seg->y1;
267       segYMax = seg->y0;
268     } else {
269       segYMin = seg->y0;
270       segYMax = seg->y1;
271     }
272     if (seg->flags & splashXPathHoriz) {
273       y = splashFloor(seg->y0);
274       if (y >= yMin && y <= yMax) {
275 	if (!addIntersection(segYMin, segYMax, seg->flags,
276 			y, splashFloor(seg->x0), splashFloor(seg->x1)))
277           break;
278       }
279     } else if (seg->flags & splashXPathVert) {
280       y0 = splashFloor(segYMin);
281       if (y0 < yMin) {
282 	y0 = yMin;
283       }
284       y1 = splashFloor(segYMax);
285       if (y1 > yMax) {
286 	y1 = yMax;
287       }
288       x = splashFloor(seg->x0);
289       for (y = y0; y <= y1; ++y) {
290 	if (!addIntersection(segYMin, segYMax, seg->flags, y, x, x))
291           break;
292       }
293     } else {
294       if (seg->x0 < seg->x1) {
295 	segXMin = seg->x0;
296 	segXMax = seg->x1;
297       } else {
298 	segXMin = seg->x1;
299 	segXMax = seg->x0;
300       }
301       y0 = splashFloor(segYMin);
302       if (y0 < yMin) {
303 	y0 = yMin;
304       }
305       y1 = splashFloor(segYMax);
306       if (y1 > yMax) {
307 	y1 = yMax;
308       }
309       // this loop could just add seg->dxdy to xx1 on each iteration,
310       // but that introduces numerical accuracy problems
311       xx1 = seg->x0 + ((SplashCoord)y0 - seg->y0) * seg->dxdy;
312       for (y = y0; y <= y1; ++y) {
313 	xx0 = xx1;
314 	xx1 = seg->x0 + ((SplashCoord)(y + 1) - seg->y0) * seg->dxdy;
315 	// the segment may not actually extend to the top and/or bottom edges
316 	if (xx0 < segXMin) {
317 	  xx0 = segXMin;
318 	} else if (xx0 > segXMax) {
319 	  xx0 = segXMax;
320 	}
321 	if (xx1 < segXMin) {
322 	  xx1 = segXMin;
323 	} else if (xx1 > segXMax) {
324 	  xx1 = segXMax;
325 	}
326 	if (!addIntersection(segYMin, segYMax, seg->flags, y,
327 			splashFloor(xx0), splashFloor(xx1)))
328           break;
329       }
330     }
331   }
332   std::sort(allInter, allInter + allInterLen, cmpIntersectFunctor());
333 
334   // build the list of y pointers
335   inter = (int *)gmallocn(yMax - yMin + 2, sizeof(int));
336   i = 0;
337   for (y = yMin; y <= yMax; ++y) {
338     inter[y - yMin] = i;
339     while (i < allInterLen && allInter[i].y <= y) {
340       ++i;
341     }
342   }
343   inter[yMax - yMin + 1] = i;
344 }
345 
addIntersection(double segYMin,double segYMax,Guint segFlags,int y,int x0,int x1)346 GBool SplashXPathScanner::addIntersection(double segYMin, double segYMax,
347 					 Guint segFlags,
348 					 int y, int x0, int x1) {
349   if (allInterLen == allInterSize) {
350     unsigned int newInterSize = ((unsigned int) allInterSize * 2 > INT_MAX / sizeof(SplashIntersect)) ? allInterSize + 32768 : allInterSize * 2;
351     if (newInterSize >= INT_MAX / sizeof(SplashIntersect)) {
352       error(errInternal, -1, "Bogus memory allocation size in SplashXPathScanner::addIntersection {0:d}", newInterSize);
353       return gFalse;
354     }
355     allInterSize = newInterSize;
356     allInter = (SplashIntersect *)greallocn(allInter, newInterSize,
357 					    sizeof(SplashIntersect));
358   }
359   allInter[allInterLen].y = y;
360   if (x0 < x1) {
361     allInter[allInterLen].x0 = x0;
362     allInter[allInterLen].x1 = x1;
363   } else {
364     allInter[allInterLen].x0 = x1;
365     allInter[allInterLen].x1 = x0;
366   }
367   if (segYMin <= y &&
368       (SplashCoord)y < segYMax &&
369       !(segFlags & splashXPathHoriz)) {
370     allInter[allInterLen].count = eo ? 1
371                                      : (segFlags & splashXPathFlip) ? 1 : -1;
372   } else {
373     allInter[allInterLen].count = 0;
374   }
375   ++allInterLen;
376   return gTrue;
377 }
378 
renderAALine(SplashBitmap * aaBuf,int * x0,int * x1,int y,GBool adjustVertLine)379 void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf,
380 				      int *x0, int *x1, int y, GBool adjustVertLine) {
381   int xx0, xx1, xx, xxMin, xxMax, yy, interEnd;
382   Guchar mask;
383   SplashColorPtr p;
384 
385   memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
386   xxMin = aaBuf->getWidth();
387   xxMax = -1;
388   if (yMin <= yMax) {
389     if (splashAASize * y < yMin) {
390       interIdx = inter[0];
391     } else if (splashAASize * y > yMax) {
392       interIdx = inter[yMax - yMin + 1];
393     } else {
394       interIdx = inter[splashAASize * y - yMin];
395     }
396     for (yy = 0; yy < splashAASize; ++yy) {
397       if (splashAASize * y + yy < yMin) {
398 	interEnd = inter[0];
399       } else if (splashAASize * y + yy > yMax) {
400 	interEnd = inter[yMax - yMin + 1];
401       } else {
402 	interEnd = inter[splashAASize * y + yy - yMin + 1];
403       }
404       interCount = 0;
405       while (interIdx < interEnd) {
406 	xx0 = allInter[interIdx].x0;
407 	xx1 = allInter[interIdx].x1;
408 	interCount += allInter[interIdx].count;
409 	++interIdx;
410 	while (interIdx < interEnd &&
411 	       (allInter[interIdx].x0 <= xx1 ||
412 		(eo ? (interCount & 1) : (interCount != 0)))) {
413 	  if (allInter[interIdx].x1 > xx1) {
414 	    xx1 = allInter[interIdx].x1;
415 	  }
416 	  interCount += allInter[interIdx].count;
417 	  ++interIdx;
418 	}
419 	if (xx0 < 0) {
420 	  xx0 = 0;
421 	}
422 	++xx1;
423 	if (xx1 > aaBuf->getWidth()) {
424 	  xx1 = aaBuf->getWidth();
425 	}
426 	// set [xx0, xx1) to 1
427 	if (xx0 < xx1) {
428 	  xx = xx0;
429 	  p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
430 	  if (xx & 7) {
431 	    mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
432 	    if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
433 	      mask &= (Guchar)(0xff00 >> (xx1 & 7));
434 	    }
435 	    *p++ |= mask;
436 	    xx = (xx & ~7) + 8;
437 	  }
438 	  for (; xx + 7 < xx1; xx += 8) {
439 	    *p++ |= 0xff;
440 	  }
441 	  if (xx < xx1) {
442 	    *p |= adjustVertLine ? 0xff : (Guchar)(0xff00 >> (xx1 & 7));
443 	  }
444 	}
445 	if (xx0 < xxMin) {
446 	  xxMin = xx0;
447 	}
448 	if (xx1 > xxMax) {
449 	  xxMax = xx1;
450 	}
451       }
452     }
453   }
454   if (xxMin > xxMax) {
455     xxMin = xxMax;
456   }
457   *x0 = xxMin / splashAASize;
458   *x1 = (xxMax - 1) / splashAASize;
459 }
460 
clipAALine(SplashBitmap * aaBuf,int * x0,int * x1,int y)461 void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf,
462 				    int *x0, int *x1, int y) {
463   int xx0, xx1, xx, yy, interEnd;
464   Guchar mask;
465   SplashColorPtr p;
466 
467   for (yy = 0; yy < splashAASize; ++yy) {
468     xx = *x0 * splashAASize;
469     if (yMin <= yMax) {
470       if (splashAASize * y + yy < yMin) {
471 	interIdx = interEnd = inter[0];
472       } else if (splashAASize * y + yy > yMax) {
473 	interIdx = interEnd = inter[yMax - yMin + 1];
474       } else {
475 	interIdx = inter[splashAASize * y + yy - yMin];
476 	if (splashAASize * y + yy > yMax) {
477 	  interEnd = inter[yMax - yMin + 1];
478 	} else {
479 	  interEnd = inter[splashAASize * y + yy - yMin + 1];
480 	}
481       }
482       interCount = 0;
483       while (interIdx < interEnd && xx < (*x1 + 1) * splashAASize) {
484 	xx0 = allInter[interIdx].x0;
485 	xx1 = allInter[interIdx].x1;
486 	interCount += allInter[interIdx].count;
487 	++interIdx;
488 	while (interIdx < interEnd &&
489 	       (allInter[interIdx].x0 <= xx1 ||
490 		(eo ? (interCount & 1) : (interCount != 0)))) {
491 	  if (allInter[interIdx].x1 > xx1) {
492 	    xx1 = allInter[interIdx].x1;
493 	  }
494 	  interCount += allInter[interIdx].count;
495 	  ++interIdx;
496 	}
497 	if (xx0 > aaBuf->getWidth()) {
498 	  xx0 = aaBuf->getWidth();
499 	}
500 	// set [xx, xx0) to 0
501 	if (xx < xx0) {
502 	  p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
503 	  if (xx & 7) {
504 	    mask = (Guchar)(0xff00 >> (xx & 7));
505 	    if ((xx & ~7) == (xx0 & ~7)) {
506 	      mask |= 0xff >> (xx0 & 7);
507 	    }
508 	    *p++ &= mask;
509 	    xx = (xx & ~7) + 8;
510 	  }
511 	  for (; xx + 7 < xx0; xx += 8) {
512 	    *p++ = 0x00;
513 	  }
514 	  if (xx < xx0) {
515 	    *p &= 0xff >> (xx0 & 7);
516 	  }
517 	}
518 	if (xx1 >= xx) {
519 	  xx = xx1 + 1;
520 	}
521       }
522     }
523     xx0 = (*x1 + 1) * splashAASize;
524     if (xx0 > aaBuf->getWidth()) xx0 = aaBuf->getWidth();
525     // set [xx, xx0) to 0
526     if (xx < xx0 && xx >= 0) {
527       p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
528       if (xx & 7) {
529 	mask = (Guchar)(0xff00 >> (xx & 7));
530 	if ((xx & ~7) == (xx0 & ~7)) {
531 	  mask &= 0xff >> (xx0 & 7);
532 	}
533 	*p++ &= mask;
534 	xx = (xx & ~7) + 8;
535       }
536       for (; xx + 7 < xx0; xx += 8) {
537 	*p++ = 0x00;
538       }
539       if (xx < xx0) {
540 	*p &= 0xff >> (xx0 & 7);
541       }
542     }
543   }
544 }
545