/****************************************************************************

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $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>

QT_BEGIN_NAMESPACE

typedef int Q16Dot16;

#define Q16Dot16ToFloat(i) ((i)/65536.)

#define FloatToQ16Dot16(i) (int)((i) * 65536.)

#define IntToQ16Dot16(i) ((i) << 16)

#define Q16Dot16ToInt(i) ((i) >> 16)

#define Q16Dot16Factor 65536

#define Q16Dot16Multiply(x, y) (int)((qlonglong(x) * qlonglong(y)) >> 16)

#define Q16Dot16FastMultiply(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

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, unsigned int len, int y, unsigned char coverage)

    {

        if (!coverage || !len)

            return;

        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

    {

        Q16Dot16 x;

        Q16Dot16 delta;

        int top, bottom;

        int winding;

    };

private:

    struct Intersection

    {

        int x;

        int winding;

        int left, right;

    };

    inline bool clip(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 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;

    Q16Dot16 m_leftFP;

    Q16Dot16 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 <typename T>

    friend void qScanConvert(QScanConverter &d, T allVertical);

};

class QRasterizerPrivate

{

public:

    bool antialiased;

    ProcessSpans blend;

    void *data;

    QRect clipRect;

    QScanConverter scanConverter;

};

QScanConverter::QScanConverter()

   : m_alloc(0)

   , m_size(0)

   , m_intersections(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 = IntToQ16Dot16(left);

    m_rightFP = IntToQ16Dot16(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;

    }

}

static inline bool topOrder(const QScanConverter::Line &a, const QScanConverter::Line &b)

{

    return a.top < b.top;

}

static inline bool xOrder(const QScanConverter::Line *a, const QScanConverter::Line *b)

{

    return a->x < b->x;

}

template <bool B>

struct QBoolToType

{

    inline bool operator()() const

    {

        return B;

    }

};

// should be a member function but VC6 doesn't support member template functions

template <typename T>

void qScanConvert(QScanConverter &d, T allVertical)

{

    qSort(d.m_lines.data(), d.m_lines.data() + d.m_lines.size(), QT_PREPEND_NAMESPACE(topOrder));

    int line = 0;

    for (int y = d.m_lines.first().top; y <= d.m_bottom; ++y) {

        for (; line < d.m_lines.size() && d.m_lines.at(line).top == y; ++line) {

            // add node to active list

            if (allVertical()) {

                QScanConverter::Line *l = &d.m_lines.at(line);

                d.m_active.resize(d.m_active.size() + 1);

                int j;

                for (j = d.m_active.size() - 2; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(l, d.m_active.at(j)); --j)

                    d.m_active.at(j+1) = d.m_active.at(j);

                d.m_active.at(j+1) = l;

            } else {

                d.m_active << &d.m_lines.at(line);

            }

        }

        int numActive = d.m_active.size();

        if (!allVertical()) {

        // use insertion sort instead of qSort, 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 = d.m_active.at(i);

                int j;

                for (j = i-1; j >= 0 && QT_PREPEND_NAMESPACE(xOrder)(l, d.m_active.at(j)); --j)

                    d.m_active.at(j+1) = d.m_active.at(j);

                d.m_active.at(j+1) = l;

            }

        }

        int x = 0;

        int winding = 0;

        for (int i = 0; i < numActive; ++i) {

            QScanConverter::Line *node = d.m_active.at(i);

            const int current = Q16Dot16ToInt(node->x);

            if (winding & d.m_fillRuleMask)

                d.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)

                    d.m_active.at(j) = d.m_active.at(j+1);

                d.m_active.resize(--numActive);

                --i;

            } else if (!allVertical())

                node->x += node->delta;

        }

    }

    d.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)

            qScanConvert(*this, QBoolToType<true>());

        else

            qScanConvert(*this, QBoolToType<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 = Q16Dot16ToInt(line.x);

                        line.x += line.delta;

                        mergeIntersection(it, isect);

                    }

                } else {

                    isect.x = Q16Dot16ToInt(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 = 0;

    }

    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(Q16Dot16 &xFP, int &iTop, int &iBottom, Q16Dot16 slopeFP, Q16Dot16 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;

        }

    }

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

    if (lastFP == edgeFP) {