/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtGui module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/

#include "qrasterizer_p.h"

#include <QPoint>
#include <QRect>

#include <private/qmath_p.h>
#include <private/qdatabuffer_p.h>
#include <private/qdrawhelper_p.h>

#include <QtGui/qpainterpath.h>

#include <algorithm>

QT_BEGIN_NAMESPACE

#if Q_PROCESSOR_WORDSIZE == 8
typedef qint64 QScFixed;
#else
typedef int QScFixed;
#endif
#define QScFixedToFloat(i) ((i) * (1./65536.))
#define FloatToQScFixed(i) (QScFixed)((i) * 65536.)
#define IntToQScFixed(i) ((QScFixed)(i) * (1 << 16))
#define QScFixedToInt(i) ((i) >> 16)
#define QScFixedFactor 65536
#define FTPosToQScFixed(i) ((QScFixed)(i) * (1 << 10))

#define QScFixedMultiply(x, y) (QScFixed)((qlonglong(x) * qlonglong(y)) >> 16)
#define QScFixedFastMultiply(x, y) (((x) * (y)) >> 16)

#define SPAN_BUFFER_SIZE 256

#define COORD_ROUNDING 1 // 0: round up, 1: round down
#define COORD_OFFSET 32 // 26.6, 32 is half a pixel

static inline QT_FT_Vector PointToVector(const QPointF &p)
{
    QT_FT_Vector result = { QT_FT_Pos(p.x() * 64), QT_FT_Pos(p.y() * 64) };
    return result;
}

class QSpanBuffer {
public:
    QSpanBuffer(ProcessSpans blend, void *data, const QRect &clipRect)
        : m_spanCount(0)
        , m_blend(blend)
        , m_data(data)
        , m_clipRect(clipRect)
    {
    }

    ~QSpanBuffer()
    {
        flushSpans();
    }

    void addSpan(int x, int len, int y, int coverage)
    {
        if (!coverage || !len)
            return;

        Q_ASSERT(coverage >= 0 && coverage <= 255);
        Q_ASSERT(y >= m_clipRect.top());
        Q_ASSERT(y <= m_clipRect.bottom());
        Q_ASSERT(x >= m_clipRect.left());
        Q_ASSERT(x + int(len) - 1 <= m_clipRect.right());

        m_spans[m_spanCount].x = x;
        m_spans[m_spanCount].len = len;
        m_spans[m_spanCount].y = y;
        m_spans[m_spanCount].coverage = coverage;

        if (++m_spanCount == SPAN_BUFFER_SIZE)
            flushSpans();
    }

private:
    void flushSpans()
    {
        m_blend(m_spanCount, m_spans, m_data);
        m_spanCount = 0;
    }

    QT_FT_Span m_spans[SPAN_BUFFER_SIZE];
    int m_spanCount;

    ProcessSpans m_blend;
    void *m_data;

    QRect m_clipRect;
};

#define CHUNK_SIZE 64
class QScanConverter
{
public:
    QScanConverter();
    ~QScanConverter();

    void begin(int top, int bottom, int left, int right,
               Qt::FillRule fillRule, QSpanBuffer *spanBuffer);
    void end();

    void mergeCurve(const QT_FT_Vector &a, const QT_FT_Vector &b,
                    const QT_FT_Vector &c, const QT_FT_Vector &d);
    void mergeLine(QT_FT_Vector a, QT_FT_Vector b);

    struct Line
    {
        QScFixed x;
        QScFixed delta;

        int top, bottom;

        int winding;
    };

private:
    struct Intersection
    {
        int x;
        int winding;

        int left, right;
    };

    inline bool clip(QScFixed &xFP, int &iTop, int &iBottom, QScFixed slopeFP, QScFixed edgeFP, int winding);
    inline void mergeIntersection(Intersection *head, const Intersection &isect);

    void prepareChunk();

    void emitNode(const Intersection *node);
    void emitSpans(int chunk);

    inline void allocate(int size);

    QDataBuffer<Line> m_lines;

    int m_alloc;
    int m_size;

    int m_top;
    int m_bottom;

    QScFixed m_leftFP;
    QScFixed m_rightFP;

    int m_fillRuleMask;

    int m_x;
    int m_y;
    int m_winding;

    Intersection *m_intersections;

    QSpanBuffer *m_spanBuffer;

    QDataBuffer<Line *> m_active;

    template <bool AllVertical>
    void scanConvert();
};

class QRasterizerPrivate
{
public:
    bool antialiased;
    ProcessSpans blend;
    void *data;
    QRect clipRect;

    QScanConverter scanConverter;
};

QScanConverter::QScanConverter()
   : m_lines(0)
   , m_alloc(0)
   , m_size(0)
   , m_intersections(nullptr)
   , m_active(0)
{
}

QScanConverter::~QScanConverter()
{
    if (m_intersections)
        free(m_intersections);
}

void QScanConverter::begin(int top, int bottom, int left, int right,
                           Qt::FillRule fillRule,
                           QSpanBuffer *spanBuffer)
{
    m_top = top;
    m_bottom = bottom;
    m_leftFP = IntToQScFixed(left);
    m_rightFP = IntToQScFixed(right + 1);

    m_lines.reset();

    m_fillRuleMask = fillRule == Qt::WindingFill ? ~0x0 : 0x1;
    m_spanBuffer = spanBuffer;
}

void QScanConverter::prepareChunk()
{
    m_size = CHUNK_SIZE;

    allocate(CHUNK_SIZE);
    memset(m_intersections, 0, CHUNK_SIZE * sizeof(Intersection));
}

void QScanConverter::emitNode(const Intersection *node)
{
tail_call:
    if (node->left)
        emitNode(node + node->left);

    if (m_winding & m_fillRuleMask)
        m_spanBuffer->addSpan(m_x, node->x - m_x, m_y, 0xff);

    m_x = node->x;
    m_winding += node->winding;

    if (node->right) {
        node += node->right;
        goto tail_call;
    }
}

void QScanConverter::emitSpans(int chunk)
{
    for (int dy = 0; dy < CHUNK_SIZE; ++dy) {
        m_x = 0;
        m_y = chunk + dy;
        m_winding = 0;

        emitNode(&m_intersections[dy]);
    }
}

// split control points b[0] ... b[3] into
// left (b[0] ... b[3]) and right (b[3] ... b[6])
static void split(QT_FT_Vector *b)
{
    b[6] = b[3];

    {
        const QT_FT_Pos temp = (b[1].x + b[2].x)/2;

        b[1].x = (b[0].x + b[1].x)/2;
        b[5].x = (b[2].x + b[3].x)/2;
        b[2].x = (b[1].x + temp)/2;
        b[4].x = (b[5].x + temp)/2;
        b[3].x = (b[2].x + b[4].x)/2;
    }
    {
        const QT_FT_Pos temp = (b[1].y + b[2].y)/2;

        b[1].y = (b[0].y + b[1].y)/2;
        b[5].y = (b[2].y + b[3].y)/2;
        b[2].y = (b[1].y + temp)/2;
        b[4].y = (b[5].y + temp)/2;
        b[3].y = (b[2].y + b[4].y)/2;
    }
}

template <bool AllVertical>
void QScanConverter::scanConvert()
{
    if (!m_lines.size()) {
        m_active.reset();
        return;
    }
    constexpr auto topOrder = [](const Line &a, const Line &b) {
        return a.top < b.top;
    };
    constexpr auto xOrder = [](const Line *a, const Line *b) {
        return a->x < b->x;
    };

    std::sort(m_lines.data(), m_lines.data() + m_lines.size(), topOrder);
    int line = 0;
    for (int y = m_lines.first().top; y <= m_bottom; ++y) {
        for (; line < m_lines.size() && m_lines.at(line).top == y; ++line) {
            // add node to active list
            if constexpr(AllVertical) {
                QScanConverter::Line *l = &m_lines.at(line);
                m_active.resize(m_active.size() + 1);
                int j;
                for (j = m_active.size() - 2; j >= 0 && xOrder(l, m_active.at(j)); --j)
                    m_active.at(j+1) = m_active.at(j);
                m_active.at(j+1) = l;
            } else {
                m_active << &m_lines.at(line);
            }
        }

        int numActive = m_active.size();
        if constexpr(!AllVertical) {
            // use insertion sort instead of std::sort, as the active edge list is quite small
            // and in the average case already sorted
            for (int i = 1; i < numActive; ++i) {
                QScanConverter::Line *l = m_active.at(i);
                int j;
                for (j = i-1; j >= 0 && xOrder(l, m_active.at(j)); --j)
                    m_active.at(j+1) = m_active.at(j);
                m_active.at(j+1) = l;
            }
        }

        int x = 0;
        int winding = 0;
        for (int i = 0; i < numActive; ++i) {
            QScanConverter::Line *node = m_active.at(i);

            const int current = QScFixedToInt(node->x);
            if (winding & m_fillRuleMask)
                m_spanBuffer->addSpan(x, current - x, y, 0xff);

            x = current;
            winding += node->winding;

            if (node->bottom == y) {
                // remove node from active list
                for (int j = i; j < numActive - 1; ++j)
                    m_active.at(j) = m_active.at(j+1);

                m_active.resize(--numActive);
                --i;
            } else {
                if constexpr(!AllVertical)
                    node->x += node->delta;
            }
        }
    }
    m_active.reset();
}

void QScanConverter::end()
{
    if (m_lines.isEmpty())
        return;

    if (m_lines.size() <= 32) {
        bool allVertical = true;
        for (int i = 0; i < m_lines.size(); ++i) {
            if (m_lines.at(i).delta) {
                allVertical = false;
                break;
            }
        }
        if (allVertical)
            scanConvert<true>();
        else
            scanConvert<false>();
    } else {
        for (int chunkTop = m_top; chunkTop <= m_bottom; chunkTop += CHUNK_SIZE) {
            prepareChunk();

            Intersection isect = { 0, 0, 0, 0 };

            const int chunkBottom = chunkTop + CHUNK_SIZE;
            for (int i = 0; i < m_lines.size(); ++i) {
                Line &line = m_lines.at(i);

                if ((line.bottom < chunkTop) || (line.top > chunkBottom))
                    continue;

                const int top = qMax(0, line.top - chunkTop);
                const int bottom = qMin(CHUNK_SIZE, line.bottom + 1 - chunkTop);
                allocate(m_size + bottom - top);

                isect.winding = line.winding;

                Intersection *it = m_intersections + top;
                Intersection *end = m_intersections + bottom;

                if (line.delta) {
                    for (; it != end; ++it) {
                        isect.x = QScFixedToInt(line.x);
                        line.x += line.delta;
                        mergeIntersection(it, isect);
                    }
                } else {
                    isect.x = QScFixedToInt(line.x);
                    for (; it != end; ++it)
                        mergeIntersection(it, isect);
                }
            }

            emitSpans(chunkTop);
        }
    }

    if (m_alloc > 1024) {
        free(m_intersections);
        m_alloc = 0;
        m_size = 0;
        m_intersections = nullptr;
    }

    if (m_lines.size() > 1024)
        m_lines.shrink(1024);
}

inline void QScanConverter::allocate(int size)
{
    if (m_alloc < size) {
        int newAlloc = qMax(size, 2 * m_alloc);
        m_intersections = q_check_ptr((Intersection *)realloc(m_intersections, newAlloc * sizeof(Intersection)));
        m_alloc = newAlloc;
    }
}

inline void QScanConverter::mergeIntersection(Intersection *it, const Intersection &isect)
{
    Intersection *current = it;

    while (isect.x != current->x) {
        int &next = isect.x < current->x ? current->left : current->right;
        if (next)
            current += next;
        else {
            Intersection *last = m_intersections + m_size;
            next = last - current;
            *last = isect;
            ++m_size;
            return;
        }
    }

    current->winding += isect.winding;
}

void QScanConverter::mergeCurve(const QT_FT_Vector &pa, const QT_FT_Vector &pb,
                                const QT_FT_Vector &pc, const QT_FT_Vector &pd)
{
    // make room for 32 splits
    QT_FT_Vector beziers[4 + 3 * 32];

    QT_FT_Vector *b = beziers;

    b[0] = pa;
    b[1] = pb;
    b[2] = pc;
    b[3] = pd;

    const QT_FT_Pos flatness = 16;

    while (b >= beziers) {
        QT_FT_Vector delta = { b[3].x - b[0].x, b[3].y - b[0].y };
        QT_FT_Pos l = qAbs(delta.x) + qAbs(delta.y);

        bool belowThreshold;
        if (l > 64) {
            qlonglong d2 = qAbs(qlonglong(b[1].x-b[0].x) * qlonglong(delta.y) -
                                qlonglong(b[1].y-b[0].y) * qlonglong(delta.x));
            qlonglong d3 = qAbs(qlonglong(b[2].x-b[0].x) * qlonglong(delta.y) -
                                qlonglong(b[2].y-b[0].y) * qlonglong(delta.x));

            qlonglong d = d2 + d3;

            belowThreshold = (d <= qlonglong(flatness) * qlonglong(l));
        } else {
            QT_FT_Pos d = qAbs(b[0].x-b[1].x) + qAbs(b[0].y-b[1].y) +
                          qAbs(b[0].x-b[2].x) + qAbs(b[0].y-b[2].y);

            belowThreshold = (d <= flatness);
        }

        if (belowThreshold || b == beziers + 3 * 32) {
            mergeLine(b[0], b[3]);
            b -= 3;
            continue;
        }

        split(b);
        b += 3;
    }
}

inline bool QScanConverter::clip(QScFixed &xFP, int &iTop, int &iBottom, QScFixed slopeFP, QScFixed edgeFP, int winding)
{
    bool right = edgeFP == m_rightFP;

    if (xFP == edgeFP) {
        if ((slopeFP > 0) ^ right)
            return false;
        else {
            Line line = { edgeFP, 0, iTop, iBottom, winding };
            m_lines.add(line);
            return true;
        }
    }

    QScFixed lastFP = xFP + slopeFP * (iBottom - iTop);

    if (lastFP == edgeFP) {
        if ((slopeFP < 0) ^ right)
            return false;
        else {
            Line line = { edgeFP, 0, iTop, iBottom, winding };
            m_lines.add(line);
            return true;
        }
    }

    // does line cross edge?
    if ((lastFP < edgeFP) ^ (xFP < edgeFP)) {
        QScFixed deltaY = QScFixed((edgeFP - xFP) / QScFixedToFloat(slopeFP));

        if ((xFP < edgeFP) ^ right) {
            // top segment needs to be clipped
            int iHeight = QScFixedToInt(deltaY + 1);
            int iMiddle = iTop + iHeight;

            Line line = { edgeFP, 0, iTop, iMiddle, winding };
            m_lines.add(line);

            if (iMiddle != iBottom) {
                xFP += slopeFP * (iHeight + 1);
                iTop = iMiddle + 1;
            } else
                return true;
        } else {
            // bottom segment needs to be clipped
            int iHeight = QScFixedToInt(deltaY);
            int iMiddle = iTop + iHeight;

            if (iMiddle != iBottom) {
                Line line = { edgeFP, 0, iMiddle + 1, iBottom, winding };
                m_lines.add(line);

                iBottom = iMiddle;
            }
        }
        return false;
    } else if ((xFP < edgeFP) ^ right) {
        Line line = { edgeFP, 0, iTop, iBottom, winding };
        m_lines.add(line);
        return true;
    }

    return false;
}

void QScanConverter::mergeLine(QT_FT_Vector a, QT_FT_Vector b)
{
    int winding = 1;

    if (a.y > b.y) {
        qSwap(a, b);
        winding = -1;
    }

    int iTop = qMax(m_top, int((a.y + 32) >> 6));
    int iBottom = qMin(m_bottom, int((b.y - 32) >> 6));

    if (iTop <= iBottom) {
        QScFixed aFP = QScFixedFactor/2 + FTPosToQScFixed(a.x);

        if (b.x == a.x) {
            Line line = { qBound(m_leftFP, aFP, m_rightFP), 0, iTop, iBottom, winding };
            m_lines.add(line);
        } else {
            const qreal slope = (b.x - a.x) / qreal(b.y - a.y);

            const QScFixed slopeFP = FloatToQScFixed(slope);

            QScFixed xFP = aFP + QScFixedMultiply(slopeFP,
                                                  IntToQScFixed(iTop)
                                                  + QScFixedFactor/2 - FTPosToQScFixed(a.y));

            if (clip(xFP, iTop, iBottom, slopeFP, m_leftFP, winding))
                return;

            if (clip(xFP, iTop, iBottom, slopeFP, m_rightFP, winding))
                return;

            Q_ASSERT(xFP >= m_leftFP);

            Line line = { xFP, slopeFP, iTop, iBottom, winding };
            m_lines.add(line);
        }
    }
}

QRasterizer::QRasterizer()
    : d(new QRasterizerPrivate)
{
}

QRasterizer::~QRasterizer()
{
    delete d;
}

void QRasterizer::setAntialiased(bool antialiased)
{
    d->antialiased = antialiased;
}

void QRasterizer::initialize(ProcessSpans blend, void *data)
{
    d->blend = blend;
    d->data = data;
}

void QRasterizer::setClipRect(const QRect &clipRect)
{
    d->clipRect = clipRect;
}

static QScFixed intersectPixelFP(int x, QScFixed top, QScFixed bottom, QScFixed leftIntersectX, QScFixed rightIntersectX, QScFixed slope, QScFixed invSlope)
{
    QScFixed leftX = IntToQScFixed(x);
    QScFixed rightX = IntToQScFixed(x) + QScFixedFactor;

    QScFixed leftIntersectY, rightIntersectY;
    if (slope > 0) {
        leftIntersectY = top + QScFixedMultiply(leftX - leftIntersectX, invSlope);
        rightIntersectY = leftIntersectY + invSlope;
    } else {
        leftIntersectY = top + QScFixedMultiply(leftX - rightIntersectX, invSlope);
        rightIntersectY = leftIntersectY + invSlope;
    }

    if (leftIntersectX >= leftX && rightIntersectX <= rightX) {
        return QScFixedMultiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1));
    } else if (leftIntersectX >= rightX) {
        return bottom - top;
    } else if (leftIntersectX >= leftX) {
        if (slope > 0) {
            return (bottom - top) - QScFixedFastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top);
        } else {
            return (bottom - top) - QScFixedFastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY);
        }
    } else if (rightIntersectX <= leftX) {
        return 0;
    } else if (rightIntersectX <= rightX) {
        if (slope > 0) {
            return QScFixedFastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY);
        } else {
            return QScFixedFastMultiply((rightIntersectX - leftX) >> 1, leftIntersectY - top);
        }
    } else {
        if (slope > 0) {
            return (bottom - rightIntersectY) + ((rightIntersectY - leftIntersectY) >> 1);
        } else {
            return (rightIntersectY - top) + ((leftIntersectY - rightIntersectY) >> 1);
        }
    }
}

static inline bool q26Dot6Compare(qreal p1, qreal p2)
{
    return int((p2  - p1) * 64.) == 0;
}

static inline QPointF snapTo26Dot6Grid(const QPointF &p)
{
    return QPointF(std::floor(p.x() * 64) * (1 / qreal(64)),
                   std::floor(p.y() * 64) * (1 / qreal(64)));
}

/*
   The rasterize line function relies on some div by zero which should
   result in +/-inf values. However, when floating point exceptions are
   enabled, this will cause crashes, so we return high numbers instead.
   As the returned value is used in further arithmetic, returning
   FLT_MAX/DBL_MAX will also cause values, so instead return a value
   that is well outside the int-range.
 */
static inline qreal qSafeDivide(qreal x, qreal y)
{
    if (y == 0)
        return x > 0 ? 1e20 : -1e20;
    return x / y;
}

/* Conversion to int fails if the value is too large to fit into INT_MAX or
   too small to fit into INT_MIN, so we need this slightly safer conversion
   when floating point exceptions are enabled
 */
static inline QScFixed qSafeFloatToQScFixed(qreal x)
{
    qreal tmp = x * QScFixedFactor;
#if Q_PROCESSOR_WORDSIZE == 8
    if (tmp > qreal(INT_MAX) * QScFixedFactor)
        return QScFixed(INT_MAX) * QScFixedFactor;
    else if (tmp < qreal(INT_MIN) * QScFixedFactor)
        return QScFixed(INT_MIN) * QScFixedFactor;
#else
    if (tmp > qreal(INT_MAX))
        return INT_MAX;
    else if (tmp < qreal(INT_MIN))
        return -INT_MAX;
#endif
    return QScFixed(tmp);
}

void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)
{
    if (a == b || !(width > 0.0) || d->clipRect.isEmpty())
        return;

    QPointF pa = a;
    QPointF pb = b;

    if (squareCap) {
        QPointF delta = pb - pa;
        pa -= (0.5f * width) * delta;
        pb += (0.5f * width) * delta;
    }

    QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5;
    const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);

    if (!clip.contains(pa) || !clip.contains(pb)) {
        qreal t1 = 0;
        qreal t2 = 1;

        const qreal o[2] = { pa.x(), pa.y() };
        const qreal d[2] = { pb.x() - pa.x(), pb.y() - pa.y() };

        const qreal low[2] = { clip.left(), clip.top() };
        const qreal high[2] = { clip.right(), clip.bottom() };

        for (int i = 0; i < 2; ++i) {
            if (d[i] == 0) {
                if (o[i] <= low[i] || o[i] >= high[i])
                    return;
                continue;
            }
            const qreal d_inv = 1 / d[i];
            qreal t_low = (low[i] - o[i]) * d_inv;
            qreal t_high = (high[i] - o[i]) * d_inv;
            if (t_low > t_high)
                qSwap(t_low, t_high);
            if (t1 < t_low)
                t1 = t_low;
            if (t2 > t_high)
                t2 = t_high;
            if (t1 >= t2)
                return;
        }

        QPointF npa = pa + (pb - pa) * t1;
        QPointF npb = pa + (pb - pa) * t2;

        pa = npa;
        pb = npb;
    }

    {
        // old delta
        const QPointF d0 = a - b;
        const qreal w0 = d0.x() * d0.x() + d0.y() * d0.y();

        // new delta
        const QPointF d = pa - pb;
        const qreal w = d.x() * d.x() + d.y() * d.y();

        if (w == 0)
            return;

        // adjust width which is given relative to |b - a|
        width *= qSqrt(w0 / w);
    }

    QSpanBuffer buffer(d->blend, d->data, d->clipRect);

    if (q26Dot6Compare(pa.y(), pb.y())) {
        const qreal x = (pa.x() + pb.x()) * 0.5f;
        const qreal dx = qAbs(pb.x() - pa.x()) * 0.5f;

        const qreal y = pa.y();
        const qreal dy = width * dx;

        pa = QPointF(x, y - dy);
        pb = QPointF(x, y + dy);

        width = 1 / width;
    }

    if (q26Dot6Compare(pa.x(), pb.x())) {
        if (pa.y() > pb.y())
            qSwap(pa, pb);

        const qreal dy = pb.y() - pa.y();
        const qreal halfWidth = 0.5f * width * dy;

        qreal left = pa.x() - halfWidth;
        qreal right = pa.x() + halfWidth;

        left = qBound(qreal(d->clipRect.left()), left, qreal(d->clipRect.right() + 1));
        right = qBound(qreal(d->clipRect.left()), right, qreal(d->clipRect.right() + 1));

        pa.ry() = qBound(qreal(d->clipRect.top()), pa.y(), qreal(d->clipRect.bottom() + 1));
        pb.ry() = qBound(qreal(d->clipRect.top()), pb.y(), qreal(d->clipRect.bottom() + 1));

        if (q26Dot6Compare(left, right) || q26Dot6Compare(pa.y(), pb.y()))
            return;

        if (d->antialiased) {
            const int iLeft = int(left);
            const int iRight = int(right);
            const QScFixed leftWidth = IntToQScFixed(iLeft + 1)
                                       - qSafeFloatToQScFixed(left);
            const QScFixed rightWidth = qSafeFloatToQScFixed(right)
                                        - IntToQScFixed(iRight);

            QScFixed coverage[3];
            int x[3];
            int len[3];

            int n = 1;
            if (iLeft == iRight) {
                if (leftWidth == QScFixedFactor)
                    coverage[0] = rightWidth * 255;
                else
                    coverage[0] = (leftWidth + rightWidth) * 255;
                x[0] = iLeft;
                len[0] = 1;
            } else {
                coverage[0] = leftWidth * 255;
                x[0] = iLeft;
                len[0] = 1;
                if (leftWidth == QScFixedFactor) {
                    len[0] = iRight - iLeft;
                } else if (iRight - iLeft > 1) {
                    coverage[1] = IntToQScFixed(255);
                    x[1] = iLeft + 1;
                    len[1] = iRight - iLeft - 1;
                    ++n;
                }
                if (rightWidth) {
                    coverage[n] = rightWidth * 255;
                    x[n] = iRight;
                    len[n] = 1;
                    ++n;
                }
            }

            const QScFixed iTopFP = IntToQScFixed(int(pa.y()));
            const QScFixed iBottomFP = IntToQScFixed(int(pb.y()));
            const QScFixed yPa = qSafeFloatToQScFixed(pa.y());
            const QScFixed yPb = qSafeFloatToQScFixed(pb.y());
            for (QScFixed yFP = iTopFP; yFP <= iBottomFP; yFP += QScFixedFactor) {
                const QScFixed rowHeight = qMin(yFP + QScFixedFactor, yPb)
                                           - qMax(yFP, yPa);
                const int y = QScFixedToInt(yFP);
                if (y > d->clipRect.bottom())
                    break;
                for (int i = 0; i < n; ++i) {
                    buffer.addSpan(x[i], len[i], y,
                                   QScFixedToInt(QScFixedMultiply(rowHeight, coverage[i])));
                }
            }
        } else { // aliased
            int iTop = int(pa.y() + 0.5f);
            int iBottom = pb.y() < 0.5f ? -1 : int(pb.y() - 0.5f);
            int iLeft = int(left + 0.5f);
            int iRight = right < 0.5f ? -1 : int(right - 0.5f);

            int iWidth = iRight - iLeft + 1;
            for (int y = iTop; y <= iBottom; ++y)
                buffer.addSpan(iLeft, iWidth, y, 255);
        }
    } else {
        if (pa.y() > pb.y())
            qSwap(pa, pb);

        QPointF delta = pb - pa;
        delta *= 0.5f * width;
        const QPointF perp(delta.y(), -delta.x());

        QPointF top;
        QPointF left;
        QPointF right;
        QPointF bottom;

        if (pa.x() < pb.x()) {
            top = pa + perp;
            left = pa - perp;
            right = pb + perp;
            bottom = pb - perp;
        } else {
            top = pa - perp;
            left = pb - perp;
            right = pa + perp;
            bottom = pb + perp;
        }

        top = snapTo26Dot6Grid(top);
        bottom = snapTo26Dot6Grid(bottom);
        left = snapTo26Dot6Grid(left);
        right = snapTo26Dot6Grid(right);

        const qreal topBound = qBound(qreal(d->clipRect.top()), top.y(), qreal(d->clipRect.bottom()));
        const qreal bottomBound = qBound(qreal(d->clipRect.top()), bottom.y(), qreal(d->clipRect.bottom()));

        const QPointF topLeftEdge = left - top;
        const QPointF topRightEdge = right - top;
        const QPointF bottomLeftEdge = bottom - left;
        const QPointF bottomRightEdge = bottom - right;

        const qreal topLeftSlope = qSafeDivide(topLeftEdge.x(), topLeftEdge.y());
        const qreal bottomLeftSlope = qSafeDivide(bottomLeftEdge.x(), bottomLeftEdge.y());

        const qreal topRightSlope = qSafeDivide(topRightEdge.x(), topRightEdge.y());
        const qreal bottomRightSlope = qSafeDivide(bottomRightEdge.x(), bottomRightEdge.y());

        const QScFixed topLeftSlopeFP = qSafeFloatToQScFixed(topLeftSlope);
        const QScFixed topRightSlopeFP = qSafeFloatToQScFixed(topRightSlope);

        const QScFixed bottomLeftSlopeFP = qSafeFloatToQScFixed(bottomLeftSlope);
        const QScFixed bottomRightSlopeFP = qSafeFloatToQScFixed(bottomRightSlope);

        const QScFixed invTopLeftSlopeFP = qSafeFloatToQScFixed(qSafeDivide(1, topLeftSlope));
        const QScFixed invTopRightSlopeFP = qSafeFloatToQScFixed(qSafeDivide(1, topRightSlope));

        const QScFixed invBottomLeftSlopeFP = qSafeFloatToQScFixed(qSafeDivide(1, bottomLeftSlope));
        const QScFixed invBottomRightSlopeFP = qSafeFloatToQScFixed(qSafeDivide(1, bottomRightSlope));

        if (d->antialiased) {
            const QScFixed iTopFP = IntToQScFixed(int(topBound));
            const QScFixed iLeftFP = IntToQScFixed(int(left.y()));
            const QScFixed iRightFP = IntToQScFixed(int(right.y()));
            const QScFixed iBottomFP = IntToQScFixed(int(bottomBound));

            QScFixed leftIntersectAf = qSafeFloatToQScFixed(top.x() + (int(topBound) - top.y()) * topLeftSlope);
            QScFixed rightIntersectAf = qSafeFloatToQScFixed(top.x() + (int(topBound) - top.y()) * topRightSlope);
            QScFixed leftIntersectBf = 0;
            QScFixed rightIntersectBf = 0;

            if (iLeftFP < iTopFP)
                leftIntersectBf = qSafeFloatToQScFixed(left.x() + (int(topBound) - left.y()) * bottomLeftSlope);

            if (iRightFP < iTopFP)
                rightIntersectBf = qSafeFloatToQScFixed(right.x() + (int(topBound) - right.y()) * bottomRightSlope);

            QScFixed rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;
            QScFixed topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;
            QScFixed bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;

            int leftMin, leftMax, rightMin, rightMax;

            const QScFixed yTopFP = qSafeFloatToQScFixed(top.y());
            const QScFixed yLeftFP = qSafeFloatToQScFixed(left.y());
            const QScFixed yRightFP = qSafeFloatToQScFixed(right.y());
            const QScFixed yBottomFP = qSafeFloatToQScFixed(bottom.y());

            rowTop = qMax(iTopFP, yTopFP);
            topLeftIntersectAf = leftIntersectAf +
                                 QScFixedMultiply(topLeftSlopeFP, rowTop - iTopFP);
            topRightIntersectAf = rightIntersectAf +
                                  QScFixedMultiply(topRightSlopeFP, rowTop - iTopFP);

            QScFixed yFP = iTopFP;
            while (yFP <= iBottomFP) {
                rowBottomLeft = qMin(yFP + QScFixedFactor, yLeftFP);
                rowBottomRight = qMin(yFP + QScFixedFactor, yRightFP);
                rowTopLeft = qMax(yFP, yLeftFP);
                rowTopRight = qMax(yFP, yRightFP);
                rowBottom = qMin(yFP + QScFixedFactor, yBottomFP);

                if (yFP == iLeftFP) {
                    const int y = QScFixedToInt(yFP);
                    leftIntersectBf = qSafeFloatToQScFixed(left.x() + (y - left.y()) * bottomLeftSlope);
                    topLeftIntersectBf = leftIntersectBf + QScFixedMultiply(bottomLeftSlopeFP, rowTopLeft - yFP);
                    bottomLeftIntersectAf = leftIntersectAf + QScFixedMultiply(topLeftSlopeFP, rowBottomLeft - yFP);
                } else {
                    topLeftIntersectBf = leftIntersectBf;
                    bottomLeftIntersectAf = leftIntersectAf + topLeftSlopeFP;
                }

                if (yFP == iRightFP) {
                    const int y = QScFixedToInt(yFP);
                    rightIntersectBf = qSafeFloatToQScFixed(right.x() + (y - right.y()) * bottomRightSlope);
                    topRightIntersectBf = rightIntersectBf + QScFixedMultiply(bottomRightSlopeFP, rowTopRight - yFP);
                    bottomRightIntersectAf = rightIntersectAf + QScFixedMultiply(topRightSlopeFP, rowBottomRight - yFP);
                } else {
                    topRightIntersectBf = rightIntersectBf;
                    bottomRightIntersectAf = rightIntersectAf + topRightSlopeFP;
                }

                if (yFP == iBottomFP) {
                    bottomLeftIntersectBf = leftIntersectBf + QScFixedMultiply(bottomLeftSlopeFP, rowBottom - yFP);
                    bottomRightIntersectBf = rightIntersectBf + QScFixedMultiply(bottomRightSlopeFP, rowBottom - yFP);
                } else {
                    bottomLeftIntersectBf = leftIntersectBf + bottomLeftSlopeFP;
                    bottomRightIntersectBf = rightIntersectBf + bottomRightSlopeFP;
                }

                if (yFP < iLeftFP) {
                    leftMin = QScFixedToInt(bottomLeftIntersectAf);
                    leftMax = QScFixedToInt(topLeftIntersectAf);
                } else if (yFP == iLeftFP) {
                    leftMin = QScFixedToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));
                    leftMax = QScFixedToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));
                } else {
                    leftMin = QScFixedToInt(topLeftIntersectBf);
                    leftMax = QScFixedToInt(bottomLeftIntersectBf);
                }

                leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right());
                leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right());

                if (yFP < iRightFP) {
                    rightMin = QScFixedToInt(topRightIntersectAf);
                    rightMax = QScFixedToInt(bottomRightIntersectAf);
                } else if (yFP == iRightFP) {
                    rightMin = QScFixedToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));
                    rightMax = QScFixedToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));
                } else {
                    rightMin = QScFixedToInt(bottomRightIntersectBf);
                    rightMax = QScFixedToInt(topRightIntersectBf);
                }

                rightMin = qBound(d->clipRect.left(), rightMin, d->clipRect.right());
                rightMax = qBound(d->clipRect.left(), rightMax, d->clipRect.right());

                if (leftMax > rightMax)
                    leftMax = rightMax;
                if (rightMin < leftMin)
                    rightMin = leftMin;

                QScFixed rowHeight = rowBottom - rowTop;

                int x = leftMin;
                while (x <= leftMax) {
                    QScFixed excluded = 0;

                    if (yFP <= iLeftFP)
                        excluded += intersectPixelFP(x, rowTop, rowBottomLeft,
                                                     bottomLeftIntersectAf, topLeftIntersectAf,
                                                     topLeftSlopeFP, invTopLeftSlopeFP);
                    if (yFP >= iLeftFP)
                        excluded += intersectPixelFP(x, rowTopLeft, rowBottom,
                                                     topLeftIntersectBf, bottomLeftIntersectBf,
                                                     bottomLeftSlopeFP, invBottomLeftSlopeFP);

                    if (x >= rightMin) {
                        if (yFP <= iRightFP)
                            excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
                                                                                     topRightIntersectAf, bottomRightIntersectAf,
                                                                                     topRightSlopeFP, invTopRightSlopeFP);
                        if (yFP >= iRightFP)
                            excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
                                                                                     bottomRightIntersectBf, topRightIntersectBf,
                                                                                     bottomRightSlopeFP, invBottomRightSlopeFP);
                    }

                    QScFixed coverage = rowHeight - excluded;
                    buffer.addSpan(x, 1, QScFixedToInt(yFP),
                                   QScFixedToInt(255 * coverage));
                    ++x;
                }
                if (x < rightMin) {
                    buffer.addSpan(x, rightMin - x, QScFixedToInt(yFP),
                                   QScFixedToInt(255 * rowHeight));
                    x = rightMin;
                }
                while (x <= rightMax) {
                    QScFixed excluded = 0;
                    if (yFP <= iRightFP)
                        excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
                                                                                 topRightIntersectAf, bottomRightIntersectAf,
                                                                                 topRightSlopeFP, invTopRightSlopeFP);
                    if (yFP >= iRightFP)
                        excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
                                                                                 bottomRightIntersectBf, topRightIntersectBf,
                                                                                 bottomRightSlopeFP, invBottomRightSlopeFP);

                    QScFixed coverage = rowHeight - excluded;
                    buffer.addSpan(x, 1, QScFixedToInt(yFP),
                                   QScFixedToInt(255 * coverage));
                    ++x;
                }

                leftIntersectAf += topLeftSlopeFP;
                leftIntersectBf += bottomLeftSlopeFP;
                rightIntersectAf += topRightSlopeFP;
                rightIntersectBf += bottomRightSlopeFP;
                topLeftIntersectAf = leftIntersectAf;
                topRightIntersectAf = rightIntersectAf;

                yFP += QScFixedFactor;
                rowTop = yFP;
            }
        } else { // aliased
            int iTop = int(top.y() + 0.5f);
            int iLeft = left.y() < 0.5f ? -1 : int(left.y() - 0.5f);
            int iRight = right.y() < 0.5f ? -1 : int(right.y() - 0.5f);
            int iBottom = bottom.y() < 0.5f? -1 : int(bottom.y() - 0.5f);
            int iMiddle = qMin(iLeft, iRight);

            QScFixed leftIntersectAf = qSafeFloatToQScFixed(top.x() + 0.5f + (iTop + 0.5f - top.y()) * topLeftSlope);
            QScFixed leftIntersectBf = qSafeFloatToQScFixed(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * bottomLeftSlope);
            QScFixed rightIntersectAf = qSafeFloatToQScFixed(top.x() - 0.5f + (iTop + 0.5f - top.y()) * topRightSlope);
            QScFixed rightIntersectBf = qSafeFloatToQScFixed(right.x() - 0.5f + (iRight + 1.5f - right.y()) * bottomRightSlope);

            int ny;
            int y = iTop;
#define DO_SEGMENT(next, li, ri, ls, rs) \
            ny = qMin(next + 1, d->clipRect.top()); \
            if (y < ny) { \
                li += ls * (ny - y); \
                ri += rs * (ny - y); \
                y = ny; \
            } \
            if (next > d->clipRect.bottom()) \
                next = d->clipRect.bottom(); \
            for (; y <= next; ++y) { \
                const int x1 = qMax(QScFixedToInt(li), d->clipRect.left()); \
                const int x2 = qMin(QScFixedToInt(ri), d->clipRect.right()); \
                if (x2 >= x1) \
                    buffer.addSpan(x1, x2 - x1 + 1, y, 255); \
                li += ls; \
                ri += rs; \
             }

            DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, topLeftSlopeFP, topRightSlopeFP)
            DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, bottomLeftSlopeFP, topRightSlopeFP)
            DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, topLeftSlopeFP, bottomRightSlopeFP);
            DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, bottomLeftSlopeFP, bottomRightSlopeFP);
#undef DO_SEGMENT
        }
    }
}

void QRasterizer::rasterize(const QT_FT_Outline *outline, Qt::FillRule fillRule)
{
    if (outline->n_points < 3 || outline->n_contours == 0)
        return;

    const QT_FT_Vector *points = outline->points;

    QSpanBuffer buffer(d->blend, d->data, d->clipRect);

    // ### QT_FT_Outline already has a bounding rect which is
    // ### precomputed at this point, so we should probably just be
    // ### using that instead...
    QT_FT_Pos min_y = points[0].y, max_y = points[0].y;
    for (int i = 1; i < outline->n_points; ++i) {
        const QT_FT_Vector &p = points[i];
        min_y = qMin(p.y, min_y);
        max_y = qMax(p.y, max_y);
    }

    int iTopBound = qMax(d->clipRect.top(), int((min_y + 32) >> 6));
    int iBottomBound = qMin(d->clipRect.bottom(), int((max_y - 32) >> 6));

    if (iTopBound > iBottomBound)
        return;

    d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer);

    int first = 0;
    for (int i = 0; i < outline->n_contours; ++i) {
        const int last = outline->contours[i];
        for (int j = first; j < last; ++j) {
            if (outline->tags[j+1] == QT_FT_CURVE_TAG_CUBIC) {
                Q_ASSERT(outline->tags[j+2] == QT_FT_CURVE_TAG_CUBIC);
                d->scanConverter.mergeCurve(points[j], points[j+1], points[j+2], points[j+3]);
                j += 2;
            } else {
                d->scanConverter.mergeLine(points[j], points[j+1]);
            }
        }

        first = last + 1;
    }

    d->scanConverter.end();
}

void QRasterizer::rasterize(const QPainterPath &path, Qt::FillRule fillRule)
{
    if (path.isEmpty())
        return;

    QSpanBuffer buffer(d->blend, d->data, d->clipRect);

    QRectF bounds = path.controlPointRect();

    int iTopBound = qMax(d->clipRect.top(), int(bounds.top() + 0.5));
    int iBottomBound = qMin(d->clipRect.bottom(), int(bounds.bottom() - 0.5));

    if (iTopBound > iBottomBound)
        return;

    d->scanConverter.begin(iTopBound, iBottomBound, d->clipRect.left(), d->clipRect.right(), fillRule, &buffer);

    int subpathStart = 0;
    QT_FT_Vector last = { 0, 0 };
    for (int i = 0; i < path.elementCount(); ++i) {
        switch (path.elementAt(i).type) {
        case QPainterPath::LineToElement:
            {
                QT_FT_Vector p1 = last;
                QT_FT_Vector p2 = PointToVector(path.elementAt(i));
                d->scanConverter.mergeLine(p1, p2);
                last = p2;
                break;
            }
        case QPainterPath::MoveToElement:
            {
                if (i != 0) {
                    QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));
                    // close previous subpath
                    if (first.x != last.x || first.y != last.y)
                        d->scanConverter.mergeLine(last, first);
                }
                subpathStart = i;
                last = PointToVector(path.elementAt(i));
                break;
            }
        case QPainterPath::CurveToElement:
            {
                QT_FT_Vector p1 = last;
                QT_FT_Vector p2 = PointToVector(path.elementAt(i));
                QT_FT_Vector p3 = PointToVector(path.elementAt(++i));
                QT_FT_Vector p4 = PointToVector(path.elementAt(++i));
                d->scanConverter.mergeCurve(p1, p2, p3, p4);
                last = p4;
                break;
            }
        default:
            Q_ASSERT(false);
            break;
        }
    }

    QT_FT_Vector first = PointToVector(path.elementAt(subpathStart));

    // close path
    if (first.x != last.x || first.y != last.y)
        d->scanConverter.mergeLine(last, first);

    d->scanConverter.end();
}

QT_END_NAMESPACE