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