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

//

// SplashXPath.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) 2010 Paweł Wiejacha <pawel.wiejacha@gmail.com>

// Copyright (C) 2010, 2011, 2018, 2019, 2021, 2025 Albert Astals Cid <aacid@kde.org>

// Copyright (C) 2013 Thomas Freitag <Thomas.Freitag@alfa.de>

// Copyright (C) 2017 Adrian Johnson <ajohnson@redneon.com>

// Copyright (C) 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 "goo/gmem.h"

#include "goo/GooLikely.h"

#include "SplashMath.h"

#include "SplashPath.h"

#include "SplashXPath.h"

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

struct SplashXPathPoint

{

    double x, y;

};

struct SplashXPathAdjust

{

    int firstPt, lastPt; // range of points

    bool vert; // vertical or horizontal hint

    double x0a, x0b, // hint boundaries

            xma, xmb, x1a, x1b;

    double x0, x1, xm; // adjusted coordinates

};

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

// Transform a point from user space to device space.

inline void SplashXPath::transform(const std::array<double, 6> &matrix, double xi, double yi, double *xo, double *yo)

{

    //                          [ m[0] m[1] 0 ]

    // [xo yo 1] = [xi yi 1] *  [ m[2] m[3] 0 ]

    //                          [ m[4] m[5] 1 ]

    *xo = xi * matrix[0] + yi * matrix[2] + matrix[4];

    *yo = xi * matrix[1] + yi * matrix[3] + matrix[5];

}

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

// SplashXPath

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

SplashXPath::SplashXPath(const SplashPath &path, const std::array<double, 6> &matrix, double flatness, bool closeSubpaths, bool adjustLines, int linePosI)

{

    SplashPathHint *hint;

    SplashXPathPoint *pts;

    SplashXPathAdjust *adjusts, *adjust;

    double x0, y0, x1, y1, x2, y2, x3, y3, xsp, ysp;

    double adj0, adj1;

    int curSubpath, i, j;

    // transform the points

    pts = static_cast<SplashXPathPoint *>(gmallocn(path.length, sizeof(SplashXPathPoint)));

    for (i = 0; i < path.length; ++i) {

        transform(matrix, path.pts[i].x, path.pts[i].y, &pts[i].x, &pts[i].y);

    }

    // set up the stroke adjustment hints

    if (path.hints) {

        adjusts = static_cast<SplashXPathAdjust *>(gmallocn_checkoverflow(path.hintsLength, sizeof(SplashXPathAdjust)));

        if (adjusts) {

            for (i = 0; i < path.hintsLength; ++i) {

                hint = &path.hints[i];

                if (hint->ctrl0 + 1 >= path.length || hint->ctrl1 + 1 >= path.length) {

                    gfree(adjusts);

                    adjusts = nullptr;

                    break;

                }

                x0 = pts[hint->ctrl0].x;

                y0 = pts[hint->ctrl0].y;

                x1 = pts[hint->ctrl0 + 1].x;

                y1 = pts[hint->ctrl0 + 1].y;

                x2 = pts[hint->ctrl1].x;

                y2 = pts[hint->ctrl1].y;

                x3 = pts[hint->ctrl1 + 1].x;

                y3 = pts[hint->ctrl1 + 1].y;

                if (x0 == x1 && x2 == x3) {

                    adjusts[i].vert = true;

                    adj0 = x0;

                    adj1 = x2;

                } else if (y0 == y1 && y2 == y3) {

                    adjusts[i].vert = false;

                    adj0 = y0;

                    adj1 = y2;

                } else {

                    gfree(adjusts);

                    adjusts = nullptr;

                    break;

                }

                if (adj0 > adj1) {

                    x0 = adj0;

                    adj0 = adj1;

                    adj1 = x0;

                }

                adjusts[i].x0a = adj0 - 0.01;

                adjusts[i].x0b = adj0 + 0.01;

                adjusts[i].xma = 0.5 * (adj0 + adj1) - 0.01;

                adjusts[i].xmb = 0.5 * (adj0 + adj1) + 0.01;

                adjusts[i].x1a = adj1 - 0.01;

                adjusts[i].x1b = adj1 + 0.01;

                // rounding both edge coordinates can result in lines of

                // different widths (e.g., adj=10.1, adj1=11.3 --> x0=10, x1=11;

                // adj0=10.4, adj1=11.6 --> x0=10, x1=12), but it has the

                // benefit of making adjacent strokes/fills line up without any

                // gaps between them

                x0 = splashRound(adj0);

                x1 = splashRound(adj1);

                if (x1 == x0) {

                    if (adjustLines) {

                        // the adjustment moves thin lines (clip rectangle with

                        // empty width or height) out of clip area, here we need

                        // a special adjustment:

                        x0 = linePosI;

                        x1 = x0 + 1;

                    } else {

                        x1 = x1 + 1;

                    }

                }

                adjusts[i].x0 = x0;

                adjusts[i].x1 = x1 - 0.01;

                adjusts[i].xm = 0.5 * (adjusts[i].x0 + adjusts[i].x1);

                adjusts[i].firstPt = hint->firstPt;

                adjusts[i].lastPt = hint->lastPt;

            }

        }

    } else {

        adjusts = nullptr;

    }

    // perform stroke adjustment

    if (adjusts) {

        for (i = 0, adjust = adjusts; i < path.hintsLength; ++i, ++adjust) {

            for (j = adjust->firstPt; j <= adjust->lastPt; ++j) {

                strokeAdjust(adjust, &pts[j].x, &pts[j].y);

            }

        }

        gfree(adjusts);

    }

    segs = nullptr;

    length = size = 0;

    x0 = y0 = xsp = ysp = 0; // make gcc happy

    adj0 = adj1 = 0; // make gcc happy

    curSubpath = 0;

    i = 0;

    // reserve space for segments, rough estimate

    grow(path.length * 2);

    while (i < path.length) {

        // first point in subpath - skip it

        if (path.flags[i] & splashPathFirst) {

            x0 = pts[i].x;

            y0 = pts[i].y;

            xsp = x0;

            ysp = y0;

            curSubpath = i;

            ++i;

        } else {

            // curve segment

            if (path.flags[i] & splashPathCurve) {

                x1 = pts[i].x;

                y1 = pts[i].y;

                x2 = pts[i + 1].x;

                y2 = pts[i + 1].y;

                x3 = pts[i + 2].x;

                y3 = pts[i + 2].y;

                addCurve(x0, y0, x1, y1, x2, y2, x3, y3, flatness);

                x0 = x3;

                y0 = y3;

                i += 3;

                // line segment

            } else {

                x1 = pts[i].x;

                y1 = pts[i].y;

                addSegment(x0, y0, x1, y1);

                x0 = x1;

                y0 = y1;

                ++i;

            }

            // close a subpath

            if (closeSubpaths && (path.flags[i - 1] & splashPathLast) && (pts[i - 1].x != pts[curSubpath].x || pts[i - 1].y != pts[curSubpath].y)) {

                addSegment(x0, y0, xsp, ysp);

            }

        }

    }

    gfree(pts);

}

// Apply the stroke adjust hints to point <pt>: (*<xp>, *<yp>).

void SplashXPath::strokeAdjust(SplashXPathAdjust *adjust, double *xp, double *yp)

{

    double x, y;

    if (adjust->vert) {

        x = *xp;

        if (x > adjust->x0a && x < adjust->x0b) {

            *xp = adjust->x0;

        } else if (x > adjust->xma && x < adjust->xmb) {

            *xp = adjust->xm;

        } else if (x > adjust->x1a && x < adjust->x1b) {

            *xp = adjust->x1;

        }

    } else {

        y = *yp;

        if (y > adjust->x0a && y < adjust->x0b) {

            *yp = adjust->x0;

        } else if (y > adjust->xma && y < adjust->xmb) {

            *yp = adjust->xm;

        } else if (y > adjust->x1a && y < adjust->x1b) {

            *yp = adjust->x1;

        }

    }

}

SplashXPath::~SplashXPath()

{

    gfree(segs);

}

// Add space for <nSegs> more segments

void SplashXPath::grow(int nSegs)

{

    if (length + nSegs > size) {

        if (size == 0) {

            size = 32;

        }

        while (size < length + nSegs) {

            size *= 2;

        }

        segs = static_cast<SplashXPathSeg *>(greallocn_checkoverflow(segs, size, sizeof(SplashXPathSeg)));

        if (unlikely(!segs)) {

            length = 0;

            size = 0;

        }

    }

}

void SplashXPath::addCurve(double x0, double y0, double x1, double y1, double x2, double y2, double x3, double y3, double flatness)

{

    if (!curveData) {

        // allocate on first use

        curveData = std::make_unique<CurveData>();

    }

    double *cx = curveData->cx.data();

    double *cy = curveData->cy.data();

    int *cNext = curveData->cNext.data();

    double xl0, xl1, xl2, xr0, xr1, xr2, xr3, xx1, xx2, xh;

    double yl0, yl1, yl2, yr0, yr1, yr2, yr3, yy1, yy2, yh;

    double dx, dy, mx, my, d1, d2, flatness2;

    int p1, p2, p3;

    flatness2 = flatness * flatness;

    // initial segment

    p1 = 0;

    p2 = splashMaxCurveSplits;

    *(cx + p1 * 3 + 0) = x0;

    *(cx + p1 * 3 + 1) = x1;

    *(cx + p1 * 3 + 2) = x2;

    *(cx + p2 * 3 + 0) = x3;

    *(cy + p1 * 3 + 0) = y0;

    *(cy + p1 * 3 + 1) = y1;

    *(cy + p1 * 3 + 2) = y2;

    *(cy + p2 * 3 + 0) = y3;

    *(cNext + p1) = p2;

    while (p1 < splashMaxCurveSplits) {

        // get the next segment

        xl0 = *(cx + p1 * 3 + 0);

        xx1 = *(cx + p1 * 3 + 1);

        xx2 = *(cx + p1 * 3 + 2);

        yl0 = *(cy + p1 * 3 + 0);

        yy1 = *(cy + p1 * 3 + 1);

        yy2 = *(cy + p1 * 3 + 2);

        p2 = *(cNext + p1);

        xr3 = *(cx + p2 * 3 + 0);

        yr3 = *(cy + p2 * 3 + 0);

        // compute the distances from the control points to the

        // midpoint of the straight line (this is a bit of a hack, but

        // it's much faster than computing the actual distances to the

        // line)

        mx = (xl0 + xr3) * 0.5;

        my = (yl0 + yr3) * 0.5;

        dx = xx1 - mx;

        dy = yy1 - my;

        d1 = dx * dx + dy * dy;

        dx = xx2 - mx;

        dy = yy2 - my;

        d2 = dx * dx + dy * dy;

        // if the curve is flat enough, or no more subdivisions are

        // allowed, add the straight line segment

        if (p2 - p1 == 1 || (d1 <= flatness2 && d2 <= flatness2)) {

            addSegment(xl0, yl0, xr3, yr3);

            p1 = p2;

            // otherwise, subdivide the curve

        } else {

            xl1 = (xl0 + xx1) * 0.5;

            yl1 = (yl0 + yy1) * 0.5;

            xh = (xx1 + xx2) * 0.5;

            yh = (yy1 + yy2) * 0.5;

            xl2 = (xl1 + xh) * 0.5;

            yl2 = (yl1 + yh) * 0.5;

            xr2 = (xx2 + xr3) * 0.5;

            yr2 = (yy2 + yr3) * 0.5;

            xr1 = (xh + xr2) * 0.5;

            yr1 = (yh + yr2) * 0.5;

            xr0 = (xl2 + xr1) * 0.5;

            yr0 = (yl2 + yr1) * 0.5;

            // add the new subdivision points

            p3 = (p1 + p2) / 2;

            *(cx + p1 * 3 + 1) = xl1;

            *(cx + p1 * 3 + 2) = xl2;

            *(cy + p1 * 3 + 1) = yl1;

            *(cy + p1 * 3 + 2) = yl2;

            *(cNext + p1) = p3;

            *(cx + p3 * 3 + 0) = xr0;

            *(cx + p3 * 3 + 1) = xr1;

            *(cx + p3 * 3 + 2) = xr2;

            *(cy + p3 * 3 + 0) = yr0;

            *(cy + p3 * 3 + 1) = yr1;

            *(cy + p3 * 3 + 2) = yr2;

            *(cNext + p3) = p2;

        }

    }

}

void SplashXPath::addSegment(double x0, double y0, double x1, double y1)

{

    grow(1);

    if (unlikely(!segs)) {

        return;

    }

    segs[length].x0 = x0;

    segs[length].y0 = y0;

    segs[length].x1 = x1;

    segs[length].y1 = y1;

    segs[length].flags = 0;

    if (y1 == y0) {

        segs[length].dxdy = 0;

        segs[length].flags |= splashXPathHoriz;

        if (x1 == x0) {

            segs[length].flags |= splashXPathVert;

        }

        ++length;

        return;

    }

    if (x1 == x0) {

        segs[length].dxdy = 0;

        segs[length].flags |= splashXPathVert;

    } else {

        segs[length].dxdy = (x1 - x0) / (y1 - y0);

    }

    if (y0 > y1) {

        segs[length].y1 = y0;

        segs[length].y0 = y1;

        segs[length].x1 = x0;

        segs[length].x0 = x1;

        segs[length].flags |= splashXPathFlipped;

    }

    ++length;

}

void SplashXPath::aaScale()

{

    SplashXPathSeg *seg;

    int i;

    for (i = 0, seg = segs; i < length; ++i, ++seg) {

        seg->x0 *= splashAASize;

        seg->y0 *= splashAASize;

        seg->x1 *= splashAASize;

        seg->y1 *= splashAASize;

    }

}