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