Long live Qt for S60!

1 files changed, 1249 insertions, 0 deletions

diff --git a/src/gui/painting/qrasterizer.cpp b/src/gui/painting/qrasterizer.cpp
new file mode 100644
index 0000000000..583885c3bb
--- /dev/null
+++ b/src/gui/painting/qrasterizer.cpp
@@ -0,0 +1,1249 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (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 either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** 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.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@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(), 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 && 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 && 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) {
+        m_alloc = qMax(size, 2 * m_alloc);
+        m_intersections = (Intersection *)realloc(m_intersections, m_alloc * sizeof(Intersection));
+    }
+}
+
+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) {
+        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)) {
+        Q16Dot16 deltaY = Q16Dot16((edgeFP - xFP) / Q16Dot16ToFloat(slopeFP));
+
+        if ((xFP < edgeFP) ^ right) {
+            // top segment needs to be clipped
+            int iHeight = Q16Dot16ToInt(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 = Q16Dot16ToInt(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;
+    }
+
+    a.x += COORD_OFFSET;
+    a.y += COORD_OFFSET;
+    b.x += COORD_OFFSET;
+    b.y += COORD_OFFSET;
+
+    int iTop = qMax(m_top, int((a.y + 32 - COORD_ROUNDING) >> 6));
+    int iBottom = qMin(m_bottom, int((b.y - 32 - COORD_ROUNDING) >> 6));
+
+    if (iTop <= iBottom) {
+        Q16Dot16 aFP = Q16Dot16Factor/2 + (a.x << 10) - COORD_ROUNDING;
+
+        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 Q16Dot16 slopeFP = FloatToQ16Dot16(slope);
+
+            Q16Dot16 xFP = aFP + Q16Dot16Multiply(slopeFP,
+                                                  IntToQ16Dot16(iTop)
+                                                  + Q16Dot16Factor/2 - (a.y << 10));
+
+            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 Q16Dot16 intersectPixelFP(int x, Q16Dot16 top, Q16Dot16 bottom, Q16Dot16 leftIntersectX, Q16Dot16 rightIntersectX, Q16Dot16 slope, Q16Dot16 invSlope)
+{
+    Q16Dot16 leftX = IntToQ16Dot16(x);
+    Q16Dot16 rightX = IntToQ16Dot16(x) + Q16Dot16Factor;
+
+    Q16Dot16 leftIntersectY, rightIntersectY;
+    if (slope > 0) {
+        leftIntersectY = top + Q16Dot16Multiply(leftX - leftIntersectX, invSlope);
+        rightIntersectY = leftIntersectY + invSlope;
+    } else {
+        leftIntersectY = top + Q16Dot16Multiply(leftX - rightIntersectX, invSlope);
+        rightIntersectY = leftIntersectY + invSlope;
+    }
+
+    if (leftIntersectX >= leftX && rightIntersectX <= rightX) {
+        return Q16Dot16Multiply(bottom - top, leftIntersectX - leftX + ((rightIntersectX - leftIntersectX) >> 1));
+    } else if (leftIntersectX >= rightX) {
+        return bottom - top;
+    } else if (leftIntersectX >= leftX) {
+        if (slope > 0) {
+            return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, rightIntersectY - top);
+        } else {
+            return (bottom - top) - Q16Dot16FastMultiply((rightX - leftIntersectX) >> 1, bottom - rightIntersectY);
+        }
+    } else if (rightIntersectX <= leftX) {
+        return 0;
+    } else if (rightIntersectX <= rightX) {
+        if (slope > 0) {
+            return Q16Dot16FastMultiply((rightIntersectX - leftX) >> 1, bottom - leftIntersectY);
+        } else {
+            return Q16Dot16FastMultiply((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 q16Dot16Compare(qreal p1, qreal p2)
+{
+    return FloatToQ16Dot16(p2 - p1) == 0;
+}
+
+static inline qreal qRoundF(qreal v)
+{
+#ifdef QT_USE_MATH_H_FLOATS
+    if (sizeof(qreal) == sizeof(float))
+        return floorf(v + 0.5);
+    else
+#endif
+        return floor(v + 0.5);
+}
+
+void QRasterizer::rasterizeLine(const QPointF &a, const QPointF &b, qreal width, bool squareCap)
+{
+    if (a == b || width == 0)
+        return;
+
+    QPointF pa = a;
+    QPointF pb = b;
+
+    QPointF offs = QPointF(qAbs(b.y() - a.y()), qAbs(b.x() - a.x())) * width * 0.5;
+    if (squareCap)
+        offs += QPointF(offs.y(), offs.x());
+    const QRectF clip(d->clipRect.topLeft() - offs, d->clipRect.bottomRight() + QPoint(1, 1) + offs);
+
+    if (!clip.contains(a) || !clip.contains(b)) {
+        qreal t1 = 0;
+        qreal t2 = 1;
+
+        const qreal o[2] = { a.x(), a.y() };
+        const qreal d[2] = { b.x() - a.x(), b.y() - a.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;
+        }
+        pa = a + (b - a) * t1;
+        pb = a + (b - a) * t2;
+    }
+
+    if (!d->antialiased) {
+        pa.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
+        pa.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
+        pb.rx() += (COORD_OFFSET - COORD_ROUNDING)/64.;
+        pb.ry() += (COORD_OFFSET - COORD_ROUNDING)/64.;
+    }
+
+    {
+        const qreal gridResolution = 64;
+        const qreal reciprocal = 1 / gridResolution;
+
+        // snap to grid to prevent large slopes
+        pa.rx() = qRoundF(pa.rx() * gridResolution) * reciprocal;
+        pa.ry() = qRoundF(pa.ry() * gridResolution) * reciprocal;
+        pb.rx() = qRoundF(pb.rx() * gridResolution) * reciprocal;
+        pb.ry() = qRoundF(pb.ry() * gridResolution) * reciprocal;
+
+        // 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 *= sqrt(w0 / w);
+    }
+
+    QSpanBuffer buffer(d->blend, d->data, d->clipRect);
+
+    if (q16Dot16Compare(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);
+
+        if (squareCap)
+            width = 1 / width + 1.0f;
+        else
+            width = 1 / width;
+
+        squareCap = false;
+    }
+
+    if (q16Dot16Compare(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;
+
+        if (squareCap) {
+            pa.ry() -= halfWidth;
+            pb.ry() += halfWidth;
+        }
+
+        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 (q16Dot16Compare(left, right) || q16Dot16Compare(pa.y(), pb.y()))
+            return;
+
+        if (d->antialiased) {
+            const Q16Dot16 iLeft = int(left);
+            const Q16Dot16 iRight = int(right);
+            const Q16Dot16 leftWidth = IntToQ16Dot16(iLeft + 1)
+                                       - FloatToQ16Dot16(left);
+            const Q16Dot16 rightWidth = FloatToQ16Dot16(right)
+                                        - IntToQ16Dot16(iRight);
+
+            Q16Dot16 coverage[3];
+            int x[3];
+            int len[3];
+
+            int n = 1;
+            if (iLeft == iRight) {
+                coverage[0] = (leftWidth + rightWidth) * 255;
+                x[0] = iLeft;
+                len[0] = 1;
+            } else {
+                coverage[0] = leftWidth * 255;
+                x[0] = iLeft;
+                len[0] = 1;
+                if (leftWidth == Q16Dot16Factor) {
+                    len[0] = iRight - iLeft;
+                } else if (iRight - iLeft > 1) {
+                    coverage[1] = IntToQ16Dot16(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 Q16Dot16 iTopFP = IntToQ16Dot16(int(pa.y()));
+            const Q16Dot16 iBottomFP = IntToQ16Dot16(int(pb.y()));
+            const Q16Dot16 yPa = FloatToQ16Dot16(pa.y());
+            const Q16Dot16 yPb = FloatToQ16Dot16(pb.y());
+            for (Q16Dot16 yFP = iTopFP; yFP <= iBottomFP; yFP += Q16Dot16Factor) {
+                const Q16Dot16 rowHeight = qMin(yFP + Q16Dot16Factor, yPb)
+                                           - qMax(yFP, yPa);
+                const int y = Q16Dot16ToInt(yFP);
+                for (int i = 0; i < n; ++i) {
+                    buffer.addSpan(x[i], len[i], y,
+                                   Q16Dot16ToInt(Q16Dot16Multiply(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());
+
+        if (squareCap) {
+            pa -= delta;
+            pb += delta;
+        }
+
+        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;
+        }
+
+        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 qreal leftSlope = (left.x() - top.x()) / (left.y() - top.y());
+        const qreal rightSlope = -1.0f / leftSlope;
+
+        const Q16Dot16 leftSlopeFP = FloatToQ16Dot16(leftSlope);
+        const Q16Dot16 rightSlopeFP = FloatToQ16Dot16(rightSlope);
+
+        if (d->antialiased) {
+            const Q16Dot16 iTopFP = IntToQ16Dot16(int(topBound));
+            const Q16Dot16 iLeftFP = IntToQ16Dot16(int(left.y()));
+            const Q16Dot16 iRightFP = IntToQ16Dot16(int(right.y()));
+            const Q16Dot16 iBottomFP = IntToQ16Dot16(int(bottomBound));
+
+            Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * leftSlope);
+            Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() + (int(topBound) - top.y()) * rightSlope);
+            Q16Dot16 leftIntersectBf = 0;
+            Q16Dot16 rightIntersectBf = 0;
+
+            if (iLeftFP < iTopFP)
+                leftIntersectBf = FloatToQ16Dot16(left.x() + (int(topBound) - left.y()) * rightSlope);
+
+            if (iRightFP < iTopFP)
+                rightIntersectBf = FloatToQ16Dot16(right.x() + (int(topBound) - right.y()) * leftSlope);
+
+            Q16Dot16 rowTop, rowBottomLeft, rowBottomRight, rowTopLeft, rowTopRight, rowBottom;
+            Q16Dot16 topLeftIntersectAf, topLeftIntersectBf, topRightIntersectAf, topRightIntersectBf;
+            Q16Dot16 bottomLeftIntersectAf, bottomLeftIntersectBf, bottomRightIntersectAf, bottomRightIntersectBf;
+
+            int leftMin, leftMax, rightMin, rightMax;
+
+            const Q16Dot16 yTopFP = FloatToQ16Dot16(top.y());
+            const Q16Dot16 yLeftFP = FloatToQ16Dot16(left.y());
+            const Q16Dot16 yRightFP = FloatToQ16Dot16(right.y());
+            const Q16Dot16 yBottomFP = FloatToQ16Dot16(bottom.y());
+
+            rowTop = qMax(iTopFP, yTopFP);
+            topLeftIntersectAf = leftIntersectAf +
+                                 Q16Dot16Multiply(leftSlopeFP, rowTop - iTopFP);
+            topRightIntersectAf = rightIntersectAf +
+                                  Q16Dot16Multiply(rightSlopeFP, rowTop - iTopFP);
+
+            Q16Dot16 yFP = iTopFP;
+            while (yFP <= iBottomFP) {
+                rowBottomLeft = qMin(yFP + Q16Dot16Factor, yLeftFP);
+                rowBottomRight = qMin(yFP + Q16Dot16Factor, yRightFP);
+                rowTopLeft = qMax(yFP, yLeftFP);
+                rowTopRight = qMax(yFP, yRightFP);
+                rowBottom = qMin(yFP + Q16Dot16Factor, yBottomFP);
+
+                if (yFP == iLeftFP) {
+                    const int y = Q16Dot16ToInt(yFP);
+                    leftIntersectBf = FloatToQ16Dot16(left.x() + (y - left.y()) * rightSlope);
+                    topLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowTopLeft - yFP);
+                    bottomLeftIntersectAf = leftIntersectAf + Q16Dot16Multiply(leftSlopeFP, rowBottomLeft - yFP);
+                } else {
+                    topLeftIntersectBf = leftIntersectBf;
+                    bottomLeftIntersectAf = leftIntersectAf + leftSlopeFP;
+                }
+
+                if (yFP == iRightFP) {
+                    const int y = Q16Dot16ToInt(yFP);
+                    rightIntersectBf = FloatToQ16Dot16(right.x() + (y - right.y()) * leftSlope);
+                    topRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowTopRight - yFP);
+                    bottomRightIntersectAf = rightIntersectAf + Q16Dot16Multiply(rightSlopeFP, rowBottomRight - yFP);
+                } else {
+                    topRightIntersectBf = rightIntersectBf;
+                    bottomRightIntersectAf = rightIntersectAf + rightSlopeFP;
+                }
+
+                if (yFP == iBottomFP) {
+                    bottomLeftIntersectBf = leftIntersectBf + Q16Dot16Multiply(rightSlopeFP, rowBottom - yFP);
+                    bottomRightIntersectBf = rightIntersectBf + Q16Dot16Multiply(leftSlopeFP, rowBottom - yFP);
+                } else {
+                    bottomLeftIntersectBf = leftIntersectBf + rightSlopeFP;
+                    bottomRightIntersectBf = rightIntersectBf + leftSlopeFP;
+                }
+
+                if (yFP < iLeftFP) {
+                    leftMin = Q16Dot16ToInt(bottomLeftIntersectAf);
+                    leftMax = Q16Dot16ToInt(topLeftIntersectAf);
+                } else if (yFP == iLeftFP) {
+                    leftMin = Q16Dot16ToInt(qMax(bottomLeftIntersectAf, topLeftIntersectBf));
+                    leftMax = Q16Dot16ToInt(qMax(topLeftIntersectAf, bottomLeftIntersectBf));
+                } else {
+                    leftMin = Q16Dot16ToInt(topLeftIntersectBf);
+                    leftMax = Q16Dot16ToInt(bottomLeftIntersectBf);
+                }
+
+                leftMin = qBound(d->clipRect.left(), leftMin, d->clipRect.right());
+                leftMax = qBound(d->clipRect.left(), leftMax, d->clipRect.right());
+
+                if (yFP < iRightFP) {
+                    rightMin = Q16Dot16ToInt(topRightIntersectAf);
+                    rightMax = Q16Dot16ToInt(bottomRightIntersectAf);
+                } else if (yFP == iRightFP) {
+                    rightMin = Q16Dot16ToInt(qMin(topRightIntersectAf, bottomRightIntersectBf));
+                    rightMax = Q16Dot16ToInt(qMin(bottomRightIntersectAf, topRightIntersectBf));
+                } else {
+                    rightMin = Q16Dot16ToInt(bottomRightIntersectBf);
+                    rightMax = Q16Dot16ToInt(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;
+
+                Q16Dot16 rowHeight = rowBottom - rowTop;
+
+                int x = leftMin;
+                while (x <= leftMax) {
+                    Q16Dot16 excluded = 0;
+
+                    if (yFP <= iLeftFP)
+                        excluded += intersectPixelFP(x, rowTop, rowBottomLeft,
+                                                     bottomLeftIntersectAf, topLeftIntersectAf,
+                                                     leftSlopeFP, -rightSlopeFP);
+                    if (yFP >= iLeftFP)
+                        excluded += intersectPixelFP(x, rowTopLeft, rowBottom,
+                                                     topLeftIntersectBf, bottomLeftIntersectBf,
+                                                     rightSlopeFP, -leftSlopeFP);
+
+                    if (x >= rightMin) {
+                        if (yFP <= iRightFP)
+                            excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
+                                                                                     topRightIntersectAf, bottomRightIntersectAf,
+                                                                                     rightSlopeFP, -leftSlopeFP);
+                        if (yFP >= iRightFP)
+                            excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
+                                                                                     bottomRightIntersectBf, topRightIntersectBf,
+                                                                                     leftSlopeFP, -rightSlopeFP);
+                    }
+
+                    Q16Dot16 coverage = rowHeight - excluded;
+                    buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
+                                   Q16Dot16ToInt(255 * coverage));
+                    ++x;
+                }
+                if (x < rightMin) {
+                    buffer.addSpan(x, rightMin - x, Q16Dot16ToInt(yFP),
+                                   Q16Dot16ToInt(255 * rowHeight));
+                    x = rightMin;
+                }
+                while (x <= rightMax) {
+                    Q16Dot16 excluded = 0;
+                    if (yFP <= iRightFP)
+                        excluded += (rowBottomRight - rowTop) - intersectPixelFP(x, rowTop, rowBottomRight,
+                                                                                 topRightIntersectAf, bottomRightIntersectAf,
+                                                                                 rightSlopeFP, -leftSlopeFP);
+                    if (yFP >= iRightFP)
+                        excluded += (rowBottom - rowTopRight) - intersectPixelFP(x, rowTopRight, rowBottom,
+                                                                                 bottomRightIntersectBf, topRightIntersectBf,
+                                                                                 leftSlopeFP, -rightSlopeFP);
+
+                    Q16Dot16 coverage = rowHeight - excluded;
+                    buffer.addSpan(x, 1, Q16Dot16ToInt(yFP),
+                                   Q16Dot16ToInt(255 * coverage));
+                    ++x;
+                }
+
+                leftIntersectAf += leftSlopeFP;
+                leftIntersectBf += rightSlopeFP;
+                rightIntersectAf += rightSlopeFP;
+                rightIntersectBf += leftSlopeFP;
+                topLeftIntersectAf = leftIntersectAf;
+                topRightIntersectAf = rightIntersectAf;
+
+                yFP += Q16Dot16Factor;
+                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);
+
+            Q16Dot16 leftIntersectAf = FloatToQ16Dot16(top.x() + 0.5f + (iTop + 0.5f - top.y()) * leftSlope);
+            Q16Dot16 leftIntersectBf = FloatToQ16Dot16(left.x() + 0.5f + (iLeft + 1.5f - left.y()) * rightSlope);
+            Q16Dot16 rightIntersectAf = FloatToQ16Dot16(top.x() - 0.5f + (iTop + 0.5f - top.y()) * rightSlope);
+            Q16Dot16 rightIntersectBf = FloatToQ16Dot16(right.x() - 0.5f + (iRight + 1.5f - right.y()) * leftSlope);
+
+            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(Q16Dot16ToInt(li), d->clipRect.left()); \
+                const int x2 = qMin(Q16Dot16ToInt(ri), d->clipRect.right()); \
+                if (x2 >= x1) \
+                    buffer.addSpan(x1, x2 - x1 + 1, y, 255); \
+                li += ls; \
+                ri += rs; \
+             }
+
+            DO_SEGMENT(iMiddle, leftIntersectAf, rightIntersectAf, leftSlopeFP, rightSlopeFP)
+            DO_SEGMENT(iRight, leftIntersectBf, rightIntersectAf, rightSlopeFP, rightSlopeFP)
+            DO_SEGMENT(iLeft, leftIntersectAf, rightIntersectBf, leftSlopeFP, leftSlopeFP)
+            DO_SEGMENT(iBottom, leftIntersectBf, rightIntersectBf, rightSlopeFP, leftSlopeFP)
+#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 + COORD_OFFSET - COORD_ROUNDING) >> 6));
+    int iBottomBound = qMin(d->clipRect.bottom(), int((max_y - 32 + COORD_OFFSET - COORD_ROUNDING) >> 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();
+}
+
+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;
+}
+
+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 + (COORD_OFFSET - COORD_ROUNDING)/64.));
+    int iBottomBound = qMin(d->clipRect.bottom(), int(bounds.bottom() - 0.5 + (COORD_OFFSET - COORD_ROUNDING)/64.));
+
+    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