/src/poppler/splash/SplashXPathScanner.cc

Source
//========================================================================
//
// SplashXPathScanner.cc
//
//========================================================================

//========================================================================
//
// Modified under the Poppler project - http://poppler.freedesktop.org
//
// All changes made under the Poppler project to this file are licensed
// under GPL version 2 or later
//
// Copyright (C) 2008, 2010, 2014, 2018, 2019, 2021, 2022, 2024-2026 Albert Astals Cid <aacid@kde.org>
// Copyright (C) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>
// Copyright (C) 2013, 2014, 2021 Thomas Freitag <Thomas.Freitag@alfa.de>
// Copyright (C) 2018, 2025 Stefan Brüns <stefan.bruens@rwth-aachen.de>
//
// To see a description of the changes please see the Changelog file that
// came with your tarball or type make ChangeLog if you are building from git
//
//========================================================================

#include <config.h>

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <limits>
#include "goo/GooLikely.h"
#include "SplashMath.h"
#include "SplashXPath.h"
#include "SplashBitmap.h"
#include "SplashXPathScanner.h"

//------------------------------------------------------------------------

//------------------------------------------------------------------------
// SplashXPathScanner
//------------------------------------------------------------------------

SplashXPathScanner::SplashXPathScanner(const SplashXPath &xPath, bool eoA, int clipYMin, int clipYMax) //
    : eo(eoA)
{
    // compute the bbox
    if (xPath.length == 0) {
        return;
    }
    if (clipYMin > clipYMax) {
        return;
    }

    double xMaxFP = std::numeric_limits<double>::lowest();
    double xMinFP = std::numeric_limits<double>::max();
    double yMaxFP = std::numeric_limits<double>::lowest();
    double yMinFP = std::numeric_limits<double>::max();

    double clipYMinFP = clipYMin;
    double clipYMaxFP = clipYMax + 1.0;

    for (int i = 0; i < xPath.length; ++i) {
        const SplashXPathSeg *seg = &xPath.segs[i];
        if (unlikely(std::isnan(seg->x0) || std::isnan(seg->x1) || std::isnan(seg->y0) || std::isnan(seg->y1))) {
            return;
        }

        const double segYMin = seg->y0;
        const double segYMax = seg->y1;
        if (segYMin >= clipYMaxFP) {
            continue;
        }
        if (segYMax < clipYMinFP) {
            continue;
        }

        if (segYMin < yMinFP) {
            yMinFP = segYMin;
        }
        if (segYMax > yMaxFP) {
            yMaxFP = segYMax;
        }
        if (seg->x0 < xMinFP) {
            xMinFP = seg->x0;
        }
        if (seg->x0 > xMaxFP) {
            xMaxFP = seg->x0;
        }
        if (seg->x1 < xMinFP) {
            xMinFP = seg->x1;
        }
        if (seg->x1 > xMaxFP) {
            xMaxFP = seg->x1;
        }
    }
    if (yMinFP > yMaxFP) {
        return;
    }

    xMin = splashFloor(xMinFP);
    xMax = splashFloor(xMaxFP);
    yMin = splashFloor(yMinFP);
    yMax = splashFloor(yMaxFP);
    if (clipYMin > yMin) {
        yMin = clipYMin;
    }
    if (clipYMax < yMax) {
        yMax = clipYMax;
    }

    if (yMin > yMax) {
        // This means the splashFloors overflowed/underflowed
        return;
    }

    computeIntersections(xPath);
}

SplashXPathScanner::~SplashXPathScanner() = default;

void SplashXPathScanner::getBBoxAA(int *xMinA, int *yMinA, int *xMaxA, int *yMaxA) const
{
    *xMinA = xMin / splashAASize;
    *yMinA = yMin / splashAASize;
    *xMaxA = xMax / splashAASize;
    *yMaxA = yMax / splashAASize;
}

bool SplashXPathScanner::test(int x, int y) const
{
    if (y < yMin || y > yMax) {
        return false;
    }
    const auto &line = allIntersections[y - yMin];
    int count = 0;
    for (unsigned int i = 0; i < line.size() && line[i].x0 <= x; ++i) {
        if (x <= line[i].x1) {
            return true;
        }
        count += line[i].count;
    }
    return eo ? (count & 1) : (count != 0);
}

bool SplashXPathScanner::testSpan(int x0, int x1, int y) const
{
    unsigned int i;

    if (y < yMin || y > yMax) {
        return false;
    }
    const auto &line = allIntersections[y - yMin];
    int count = 0;
    for (i = 0; i < line.size() && line[i].x1 < x0; ++i) {
        count += line[i].count;
    }

    // invariant: the subspan [x0,xx1] is inside the path
    int xx1 = x0 - 1;
    int eoMask = eo ? 0x1 : ~0;
    while (xx1 < x1) {
        if (i >= line.size()) {
            return false;
        }
        if (line[i].x0 > xx1 + 1 && !(count & eoMask)) {
            return false;
        }
        if (line[i].x1 > xx1) {
            xx1 = line[i].x1;
        }
        count += line[i].count;
        ++i;
    }

    return true;
}

bool SplashXPathScanIterator::getNextSpan(int *x0, int *x1)
{
    int xx0, xx1;

    if (interIdx >= line.size()) {
        return false;
    }
    int eoMask = eo ? 0x1 : ~0;
    xx0 = line[interIdx].x0;
    xx1 = line[interIdx].x1;
    interCount += line[interIdx].count;
    ++interIdx;
    while (interIdx < line.size() && (line[interIdx].x0 <= xx1 || (interCount & eoMask))) {
        if (line[interIdx].x1 > xx1) {
            xx1 = line[interIdx].x1;
        }
        interCount += line[interIdx].count;
        ++interIdx;
    }
    *x0 = xx0;
    *x1 = xx1;
    return true;
}

SplashXPathScanIterator::SplashXPathScanIterator(const SplashXPathScanner &scanner, int y) : line((y < scanner.yMin || y > scanner.yMax) ? scanner.allIntersections[0] : scanner.allIntersections[y - scanner.yMin]), eo(scanner.eo)
{
    if (y < scanner.yMin || y > scanner.yMax) {
        // set index to line end
        interIdx = line.size();
    }
}

void SplashXPathScanner::computeIntersections(const SplashXPath &xPath)
{
    // build the list of all intersections
    allIntersections.resize(yMax - yMin + 1);

    const double clipYMinFP = yMin;
    const double clipYMaxFP = yMax + 1.0;

    for (int i = 0; i < xPath.length; ++i) {
        const SplashXPathSeg *seg = &xPath.segs[i];
        const double segYMin = seg->y0;
        const double segYMax = seg->y1;
        if (segYMin >= clipYMaxFP) {
            continue;
        }
        if (segYMax < clipYMinFP) {
            continue;
        }

        int y1 = splashFloor(segYMax);
        int y0 = (seg->flags & splashXPathHoriz) ? y1 : splashFloor(segYMin);

        if (y1 == y0) {
            addIntersection(segYMin, y1, splashFloor(seg->x0), splashFloor(seg->x1), 0);
        } else if (seg->flags & splashXPathVert) {
            if (y0 < yMin) {
                y0 = yMin;
            }
            if (y1 > yMax) {
                y1 = yMax;
            }
            int x = splashFloor(seg->x0);
            int count = (seg->flags & splashXPathFlipped) ? 1 : -1;
            for (int y = y0; y <= y1; ++y) {
                addIntersection(segYMin, y, x, x, count);
            }
        } else {
            double segXMin, segXMax;

            if (seg->x0 < seg->x1) {
                segXMin = seg->x0;
                segXMax = seg->x1;
            } else {
                segXMin = seg->x1;
                segXMax = seg->x0;
            }
            // Calculate the projected intersection of the segment with the
            // X-Axis.
            double xbase = seg->x0 - (seg->y0 * seg->dxdy);
            double xx0 = seg->x0;
            if (y0 < yMin) {
                y0 = yMin;
                xx0 = xbase + static_cast<double>(y0) * seg->dxdy;
            }
            if (y1 > yMax) {
                y1 = yMax;
            }
            int count = (seg->flags & splashXPathFlipped) ? 1 : -1;
            // the segment may not actually extend to the top and/or bottom edges
            if (xx0 < segXMin) {
                xx0 = segXMin;
            } else if (xx0 > segXMax) {
                xx0 = segXMax;
            }
            int x0 = splashFloor(xx0);

            for (int y = y0; y <= y1; ++y) {
                double xx1 = xbase + (static_cast<double>(y + 1) * seg->dxdy);

                if (xx1 < segXMin) {
                    xx1 = segXMin;
                } else if (xx1 > segXMax) {
                    xx1 = segXMax;
                }
                int x1 = splashFloor(xx1);
                addIntersection(segYMin, y, x0, x1, count);

                x0 = x1;
            }
        }
    }
    for (auto &line : allIntersections) {
        std::ranges::sort(line, [](const SplashIntersect i0, const SplashIntersect i1) { return i0.x0 < i1.x0; });
    }
}

inline void SplashXPathScanner::addIntersection(double segYMin, int y, int x0, int x1, int count)
{
    SplashIntersect intersect;
    if (x0 < x1) {
        intersect.x0 = x0;
        intersect.x1 = x1;
    } else {
        intersect.x0 = x1;
        intersect.x1 = x0;
    }
    if (segYMin < y) {
        intersect.count = count;
    } else {
        intersect.count = 0;
    }

    auto &line = allIntersections[y - yMin];
    if (line.empty()) {
#if !USE_BOOST_HEADERS
        line.reserve(4);
#endif
        line.push_back(intersect);
    } else {
        auto &last = line.back();
        // Check if last and new overlap/touch
        if ((last.x1 + 1) < intersect.x0) {
            line.push_back(intersect);
        } else if (last.x0 > (intersect.x1 + 1)) {
            line.push_back(intersect);
        } else {
            last.count += intersect.count;
            last.x0 = last.x0 < intersect.x0 ? last.x0 : intersect.x0;
            last.x1 = last.x1 > intersect.x1 ? last.x1 : intersect.x1;
        }
    }
}

void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf, int *x0, int *x1, int y, bool adjustVertLine) const
{
    memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
    int xxMin = aaBuf->getWidth();
    int xxMax = -1;
    if (yMin <= yMax) {
        int yy = 0;
        int yyMax = splashAASize - 1;
        // clamp start and end position
        if (yMin > splashAASize * y) {
            yy = yMin - splashAASize * y;
        }
        if (yyMax + splashAASize * y > yMax) {
            yyMax = yMax - splashAASize * y;
        }

        int eoMask = eo ? 0x1 : ~0;
        for (; yy <= yyMax; ++yy) {
            const auto &line = allIntersections[splashAASize * y + yy - yMin];
            size_t interIdx = 0;
            int interCount = 0;
            while (interIdx < line.size()) {
                int xx0 = line[interIdx].x0;
                int xx1 = line[interIdx].x1;
                interCount += line[interIdx].count;
                ++interIdx;
                while (interIdx < line.size() && (line[interIdx].x0 <= xx1 || (interCount & eoMask))) {
                    if (line[interIdx].x1 > xx1) {
                        xx1 = line[interIdx].x1;
                    }
                    interCount += line[interIdx].count;
                    ++interIdx;
                }
                if (xx0 < 0) {
                    xx0 = 0;
                }
                ++xx1;
                if (xx1 > aaBuf->getWidth()) {
                    xx1 = aaBuf->getWidth();
                }
                // set [xx0, xx1) to 1
                if (xx0 < xx1) {
                    int xx = xx0;
                    SplashColorPtr p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
                    if (xx & 7) {
                        unsigned char mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
                        if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
                            mask &= static_cast<unsigned char>(0xff00 >> (xx1 & 7));
                        }
                        *p++ |= mask;
                        xx = (xx & ~7) + 8;
                    }
                    for (; xx + 7 < xx1; xx += 8) {
                        *p++ |= 0xff;
                    }
                    if (xx < xx1) {
                        *p |= adjustVertLine ? 0xff : static_cast<unsigned char>(0xff00 >> (xx1 & 7));
                    }
                }
                if (xx0 < xxMin) {
                    xxMin = xx0;
                }
                if (xx1 > xxMax) {
                    xxMax = xx1;
                }
            }
        }
    }
    if (xxMin > xxMax) {
        xxMin = xxMax;
    }
    *x0 = xxMin / splashAASize;
    *x1 = (xxMax - 1) / splashAASize;
}

void SplashXPathScanner::clipAALine(SplashBitmap *aaBuf, const int *x0, const int *x1, int y) const
{
    int yyMin = 0;
    int yyMax = splashAASize - 1;
    // clamp start and end position
    if (yMin > splashAASize * y) {
        yyMin = yMin - splashAASize * y;
    }
    if (yyMax + splashAASize * y > yMax) {
        yyMax = yMax - splashAASize * y;
    }
    int eoMask = eo ? 0x1 : ~0;
    for (int yy = 0; yy < splashAASize; ++yy) {
        int xx = *x0 * splashAASize;
        if (yy >= yyMin && yy <= yyMax) {
            const int intersectionIndex = splashAASize * y + yy - yMin;
            if (unlikely(intersectionIndex < 0 || (unsigned)intersectionIndex >= allIntersections.size())) {
                break;
            }
            const auto &line = allIntersections[intersectionIndex];
            size_t interIdx = 0;
            int interCount = 0;
            while (interIdx < line.size() && xx < (*x1 + 1) * splashAASize) {
                int xx0 = line[interIdx].x0;
                int xx1 = line[interIdx].x1;
                interCount += line[interIdx].count;
                ++interIdx;
                while (interIdx < line.size() && (line[interIdx].x0 <= xx1 || (interCount & eoMask))) {
                    if (line[interIdx].x1 > xx1) {
                        xx1 = line[interIdx].x1;
                    }
                    interCount += line[interIdx].count;
                    ++interIdx;
                }
                if (xx0 > aaBuf->getWidth()) {
                    xx0 = aaBuf->getWidth();
                }
                // set [xx, xx0) to 0
                if (xx < xx0) {
                    SplashColorPtr p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
                    if (xx & 7) {
                        auto mask = static_cast<unsigned char>(0xff00 >> (xx & 7));
                        if ((xx & ~7) == (xx0 & ~7)) {
                            mask |= 0xff >> (xx0 & 7);
                        }
                        *p++ &= mask;
                        xx = (xx & ~7) + 8;
                    }
                    for (; xx + 7 < xx0; xx += 8) {
                        *p++ = 0x00;
                    }
                    if (xx < xx0) {
                        *p &= 0xff >> (xx0 & 7);
                    }
                }
                if (xx1 >= xx) {
                    xx = xx1 + 1;
                }
            }
        }
        int xx0 = (*x1 + 1) * splashAASize;
        if (xx0 > aaBuf->getWidth()) {
            xx0 = aaBuf->getWidth();
        }
        // set [xx, xx0) to 0
        if (xx < xx0 && xx >= 0) {
            SplashColorPtr p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
            if (xx & 7) {
                auto mask = static_cast<unsigned char>(0xff00 >> (xx & 7));
                if ((xx & ~7) == (xx0 & ~7)) {
                    mask &= 0xff >> (xx0 & 7);
                }
                *p++ &= mask;
                xx = (xx & ~7) + 8;
            }
            for (; xx + 7 < xx0; xx += 8) {
                *p++ = 0x00;
            }
            if (xx < xx0) {
                *p &= 0xff >> (xx0 & 7);
            }
        }
    }
}

Coverage Report

Created: 2026-09-28 08:21

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