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

source code of poppler/splash/SplashXPathScanner.cc