/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 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 "goo/gmem.h"
#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)
{
    const SplashXPathSeg *seg;
    SplashCoord xMinFP, yMinFP, xMaxFP, yMaxFP;
    int i;

    eo = eoA;
    partialClip = false;

    // compute the bbox
    xMin = yMin = 1;
    xMax = yMax = 0;
    if (xPath.length > 0) {
        seg = &xPath.segs[0];
        if (unlikely(std::isnan(seg->x0) || std::isnan(seg->x1) || std::isnan(seg->y0) || std::isnan(seg->y1))) {
            return;
        }
        if (seg->x0 <= seg->x1) {
            xMinFP = seg->x0;
            xMaxFP = seg->x1;
        } else {
            xMinFP = seg->x1;
            xMaxFP = seg->x0;
        }
        if (seg->flags & splashXPathFlip) {
            yMinFP = seg->y1;
            yMaxFP = seg->y0;
        } else {
            yMinFP = seg->y0;
            yMaxFP = seg->y1;
        }
        for (i = 1; i < xPath.length; ++i) {
            seg = &xPath.segs[i];
            if (unlikely(std::isnan(seg->x0) || std::isnan(seg->x1) || std::isnan(seg->y0) || std::isnan(seg->y1))) {
                return;
            }
            if (seg->x0 < xMinFP) {
                xMinFP = seg->x0;
            } else if (seg->x0 > xMaxFP) {
                xMaxFP = seg->x0;
            }
            if (seg->x1 < xMinFP) {
                xMinFP = seg->x1;
            } else if (seg->x1 > xMaxFP) {
                xMaxFP = seg->x1;
            }
            if (seg->flags & splashXPathFlip) {
                if (seg->y0 > yMaxFP) {
                    yMaxFP = seg->y0;
                }
            } else {
                if (seg->y1 > yMaxFP) {
                    yMaxFP = seg->y1;
                }
            }
        }
        xMin = splashFloor(xMinFP);
        xMax = splashFloor(xMaxFP);
        yMin = splashFloor(yMinFP);
        yMax = splashFloor(yMaxFP);
        if (clipYMin > yMin) {
            yMin = clipYMin;
            partialClip = true;
        }
        if (clipYMax < yMax) {
            yMax = clipYMax;
            partialClip = true;
        }
    }

    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;
}

void SplashXPathScanner::getSpanBounds(int y, int *spanXMin, int *spanXMax) const
{
    if (y < yMin || y > yMax) {
        *spanXMin = xMax + 1;
        *spanXMax = xMax;
        return;
    }
    const auto &line = allIntersections[y - yMin];
    if (!line.empty()) {
        *spanXMin = line[0].x0;
        int xx = line[0].x1;
        for (const SplashIntersect &intersect : line) {
            if (intersect.x1 > xx) {
                xx = intersect.x1;
            }
        }
        *spanXMax = xx;
    } else {
        *spanXMin = xMax + 1;
        *spanXMax = xMax;
    }
}

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;
    while (xx1 < x1) {
        if (i >= line.size()) {
            return false;
        }
        if (line[i].x0 > xx1 + 1 && !(eo ? (count & 1) : (count != 0))) {
            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;
    }
    xx0 = line[interIdx].x0;
    xx1 = line[interIdx].x1;
    interCount += line[interIdx].count;
    ++interIdx;
    while (interIdx < line.size() && (line[interIdx].x0 <= xx1 || (eo ? (interCount & 1) : (interCount != 0)))) {
        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]), interIdx(0), interCount(0), eo(scanner.eo)
{
    if (y < scanner.yMin || y > scanner.yMax) {
        // set index to line end
        interIdx = line.size();
    }
}

void SplashXPathScanner::computeIntersections(const SplashXPath &xPath)
{
    const SplashXPathSeg *seg;
    SplashCoord segXMin, segXMax, segYMin, segYMax;

    if (yMin > yMax) {
        return;
    }

    // build the list of all intersections
    allIntersections.resize(yMax - yMin + 1);

    for (int i = 0; i < xPath.length; ++i) {
        seg = &xPath.segs[i];
        if (seg->flags & splashXPathFlip) {
            segYMin = seg->y1;
            segYMax = seg->y0;
        } else {
            segYMin = seg->y0;
            segYMax = seg->y1;
        }
        if (seg->flags & splashXPathHoriz) {
            int y = splashFloor(seg->y0);
            if (y >= yMin && y <= yMax) {
                addIntersection(segYMin, segYMax, y, splashFloor(seg->x0), splashFloor(seg->x1), 0);
            }
        } else if (seg->flags & splashXPathVert) {
            int y0 = splashFloor(segYMin);
            if (y0 < yMin) {
                y0 = yMin;
            }
            int y1 = splashFloor(segYMax);
            if (y1 > yMax) {
                y1 = yMax;
            }
            int x = splashFloor(seg->x0);
            int count = eo || (seg->flags & splashXPathFlip) ? 1 : -1;
            for (int y = y0; y <= y1; ++y) {
                addIntersection(segYMin, segYMax, y, x, x, count);
            }
        } else {
            if (seg->x0 < seg->x1) {
                segXMin = seg->x0;
                segXMax = seg->x1;
            } else {
                segXMin = seg->x1;
                segXMax = seg->x0;
            }
            int y0 = splashFloor(segYMin);
            if (y0 < yMin) {
                y0 = yMin;
            }
            int y1 = splashFloor(segYMax);
            if (y1 > yMax) {
                y1 = yMax;
            }
            int count = eo || (seg->flags & splashXPathFlip) ? 1 : -1;
            // Calculate the projected intersection of the segment with the
            // X-Axis.
            SplashCoord xbase = seg->x0 - (seg->y0 * seg->dxdy);
            SplashCoord xx0 = xbase + ((SplashCoord)y0) * seg->dxdy;
            // 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) {
                SplashCoord xx1 = xbase + ((SplashCoord)(y + 1) * seg->dxdy);

                if (xx1 < segXMin) {
                    xx1 = segXMin;
                } else if (xx1 > segXMax) {
                    xx1 = segXMax;
                }
                int x1 = splashFloor(xx1);
                addIntersection(segYMin, segYMax, 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, double segYMax, int y, int x0, int x1, int count)
{
    SplashIntersect intersect;
    intersect.y = y;
    if (x0 < x1) {
        intersect.x0 = x0;
        intersect.x1 = x1;
    } else {
        intersect.x0 = x1;
        intersect.x1 = x0;
    }
    if (segYMin <= y && (SplashCoord)y < segYMax) {
        intersect.count = count;
    } else {
        intersect.count = 0;
    }

    auto &line = allIntersections[y - yMin];
#ifndef USE_BOOST_HEADERS
    if (line.empty()) {
        line.reserve(4);
    }
#endif
    line.push_back(intersect);
}

void SplashXPathScanner::renderAALine(SplashBitmap *aaBuf, int *x0, int *x1, int y, bool adjustVertLine) const
{
    int xx0, xx1, xx, xxMin, xxMax, yy, yyMax, interCount;
    size_t interIdx;
    unsigned char mask;
    SplashColorPtr p;

    memset(aaBuf->getDataPtr(), 0, aaBuf->getRowSize() * aaBuf->getHeight());
    xxMin = aaBuf->getWidth();
    xxMax = -1;
    if (yMin <= yMax) {
        yy = 0;
        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;
        }

        for (; yy <= yyMax; ++yy) {
            const auto &line = allIntersections[splashAASize * y + yy - yMin];
            interIdx = 0;
            interCount = 0;
            while (interIdx < line.size()) {
                xx0 = line[interIdx].x0;
                xx1 = line[interIdx].x1;
                interCount += line[interIdx].count;
                ++interIdx;
                while (interIdx < line.size() && (line[interIdx].x0 <= xx1 || (eo ? (interCount & 1) : (interCount != 0)))) {
                    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) {
                    xx = xx0;
                    p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
                    if (xx & 7) {
                        mask = adjustVertLine ? 0xff : 0xff >> (xx & 7);
                        if (!adjustVertLine && (xx & ~7) == (xx1 & ~7)) {
                            mask &= (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 : (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 xx0, xx1, xx, yy, yyMin, yyMax, interCount;
    size_t interIdx;
    unsigned char mask;
    SplashColorPtr p;

    yyMin = 0;
    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;
    }
    for (yy = 0; yy < splashAASize; ++yy) {
        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];
            interIdx = 0;
            interCount = 0;
            while (interIdx < line.size() && xx < (*x1 + 1) * splashAASize) {
                xx0 = line[interIdx].x0;
                xx1 = line[interIdx].x1;
                interCount += line[interIdx].count;
                ++interIdx;
                while (interIdx < line.size() && (line[interIdx].x0 <= xx1 || (eo ? (interCount & 1) : (interCount != 0)))) {
                    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) {
                    p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
                    if (xx & 7) {
                        mask = (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;
                }
            }
        }
        xx0 = (*x1 + 1) * splashAASize;
        if (xx0 > aaBuf->getWidth()) {
            xx0 = aaBuf->getWidth();
        }
        // set [xx, xx0) to 0
        if (xx < xx0 && xx >= 0) {
            p = aaBuf->getDataPtr() + yy * aaBuf->getRowSize() + (xx >> 3);
            if (xx & 7) {
                mask = (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: 2025-09-27 07:50

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