//========================================================================

//

// 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);

            }

        }

    }

}