/*------------------------------------------------------------------------

 *

 * OpenVG 1.1 Reference Implementation

 * -----------------------------------

 *

 * Copyright (c) 2007 The Khronos Group Inc.

 * Portions copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and /or associated documentation files

 * (the "Materials "), to deal in the Materials without restriction,

 * including without limitation the rights to use, copy, modify, merge,

 * publish, distribute, sublicense, and/or sell copies of the Materials,

 * and to permit persons to whom the Materials are furnished to do so,

 * subject to the following conditions:

 *

 * The above copyright notice and this permission notice shall be included

 * in all copies or substantial portions of the Materials.

 *

 * THE MATERIALS ARE PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF

 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.

 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,

 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR

 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE MATERIALS OR

 * THE USE OR OTHER DEALINGS IN THE MATERIALS.

 *

 *//**

 * \file

 * \brief	Implementation of polygon rasterizer.

 * \note

 *//*-------------------------------------------------------------------*/

#include "riRasterizer.h"

// TEMP!

#ifndef __SFCOMPILER_H

#   include "sfCompiler.h"

#endif

namespace OpenVGRI

{

/*-------------------------------------------------------------------*//*!

* \brief	Rasterizer constructor.

* \param

* \return

* \note

*//*-------------------------------------------------------------------*/

Rasterizer::Rasterizer() :

    m_covBuffer(NULL),

    m_covBufferSz(0),

    m_edges(),

    m_scissorEdges(),

    m_scissor(false),

    m_aa(true),

    m_vpx(0),

    m_vpy(0),

    m_vpwidth(0),

    m_vpheight(0),

    m_fillRule(VG_EVEN_ODD),

    m_pixelPipe(NULL),

    m_nSpans(0)

{}

/*-------------------------------------------------------------------*//*!

* \brief	Rasterizer destructor.

* \param

* \return

* \note

*//*-------------------------------------------------------------------*/

Rasterizer::~Rasterizer()

{

    if(m_covBuffer)

        RI_DELETE_ARRAY(m_covBuffer);

}

/*-------------------------------------------------------------------*//*!

* \brief	Removes all appended edges.

* \param

* \return

* \note

*//*-------------------------------------------------------------------*/

#define EDGE_TERMINATOR 0xFFFFFFFFu

void Rasterizer::clear()

{

    //m_edges.clear();

    for (int i = 0; i < m_edges.size(); i++)

        m_edges[i] = EDGE_TERMINATOR;

    m_edgePool.clear();

    m_edgeMin.set(0x7fffffffu, 0x7fffffffu);

    m_edgeMax.set(0x80000000, 0x80000000);

}

/*-------------------------------------------------------------------*//*!

* \brief	Appends an edge to the rasterizer.

* \param

* \return

* \note

*//*-------------------------------------------------------------------*/

void Rasterizer::addBBox(const IVector2& v)

{

    if(v.x < m_edgeMin.x) m_edgeMin.x = v.x;

    if(v.y < m_edgeMin.y) m_edgeMin.y = v.y;

    if(v.x > m_edgeMax.x) m_edgeMax.x = v.x;

    if(v.y > m_edgeMax.y) m_edgeMax.y = v.y;

}

void Rasterizer::pushEdge(const Edge& edge)

{

    addBBox(edge.v0);

    addBBox(edge.v1);

    // Only add processed edges.

    RI_ASSERT(edge.v0.y >= 0);

    RI_ASSERT(edge.v0.y < edge.v1.y);	//horizontal edges should have been dropped already

    ActiveEdge ae;

    ae.direction = edge.direction;

    // \todo Adjust for non-AA cases

    // \todo verySteep is temporary. Either clip to right edge also, or validate that a proper slope can be

    // calculated here.

    const int slope	= RI_SAT_SHL((edge.v1.x - edge.v0.x), RASTERIZER_BITS - X_BITS) / (edge.v1.y - edge.v0.y);

    //const bool verySteep = RI_INT_ABS(edge.v1.x - edge.v0.x) > (1 << (30-RASTERIZER_BITS)) ? true : false;

    //const int slope	= verySteep ? 1 << 30 : RI_SHL((edge.v1.x - edge.v0.x), RASTERIZER_BITS - X_BITS) / (edge.v1.y - edge.v0.y);

    // slope: SI.(RASTERIZER_BITS - Y_BITS)

    const int yF 	= edge.v0.y & Y_MASK;

    // \todo See verySteep note for this hack also. (Clip to right edge?)

    const int xRef 	= RI_SAT_SHL(edge.v0.x, RASTERIZER_BITS - X_BITS) - (yF * slope);

    //const int xRef 	= edge.v0.x > (1<<(30-RASTERIZER_BITS)) ? 1<<30 : RI_SHL(edge.v0.x, RASTERIZER_BITS - X_BITS) - (yF * slope);

    RI_ASSERT(RI_INT_ABS(edge.v0.y <= 32767));

    RI_ASSERT(RI_INT_ABS(edge.v1.y <= 32767));

    ae.yStart 		= (RIint16)edge.v0.y;

    ae.yEnd 	  	= (RIint16)edge.v1.y;

    ae.xRef 		= xRef;

    ae.slope 		= slope;

    // Scanline range.

    ae.minx         = xRef >> RASTERIZER_BITS;

    ae.maxx         = (xRef + slope * (1<<Y_BITS)) >> RASTERIZER_BITS;

    if (ae.minx > ae.maxx)

        RI_ANY_SWAP(ActiveEdge::XCoord, ae.minx, ae.maxx);

    if (ae.maxx < 0)

        ae.minx = ae.maxx = LEFT_DISCARD_SHORT;

    if (m_edges[ae.yStart>>Y_BITS] == EDGE_TERMINATOR)

        ae.next = EDGE_TERMINATOR;

    else

        ae.next = m_edges[ae.yStart>>Y_BITS];

    m_edgePool.push_back(ae);	//throws bad_alloc

    RI_ASSERT(m_edgePool.size() > 0);

    m_edges[ae.yStart>>Y_BITS] = m_edgePool.size()-1;

}

/**

 * \brief   Clips an edge and if something remains, adds it to the list of edges.

 * \todo    Enhance precision: Currently this just uses doubles and gets away with

 *          it in most cases.

 */

void Rasterizer::clipAndAddEdge(Edge& edge)

{

    //if (m_edges.size() > 48)

        //return;

    // Check y-clips

    // \todo Reduce amount of clips.

    bool outLeft[2] = {(edge.v0.x < m_vpMinx), (edge.v1.x < m_vpMinx)};

    bool outRight[2] = {(edge.v0.x > m_vpMaxx), (edge.v1.x > m_vpMaxx)};

    bool outTop[2] = {(edge.v0.y < m_vpMiny), (edge.v1.y < m_vpMiny)};

    bool outBottom[2] = {(edge.v0.y > m_vpMaxy), (edge.v1.y > m_vpMaxy)};

    if (!(outLeft[0] || outLeft[1] || outRight[0] || outRight[1] || outTop[0] || outTop[1] || outBottom[0] || outBottom[1]))

    {

        pushEdge(edge);

        return;

    }

    // \todo Make sure that checking out-of-right works with the scanconverter.

    if ((outBottom[0] && outBottom[1]) || (outTop[0] && outTop[1]))

        return; // Out of bounds

    // \todo Clip to right edge of screen.

    // \todo Make slope-calculation and signs consistent.

    //

    if (outTop[0] || outBottom[1])

    {

        // Clip to top/bottom.

        double slope = (double)(edge.v1.x - edge.v0.x)/(edge.v1.y - edge.v0.y);

        if (outTop[0])

        {

            RI_ASSERT(-(RIint64)edge.v0.y >= 0);

            RIint32 dx = RI_ROUND_TO_INT(-slope * edge.v0.y);

            edge.v0.y = 0;

            edge.v0.x += dx;

        }

        if (outBottom[1])

        {

            RIint32 dy = edge.v1.y - m_vpMaxy;

            RI_ASSERT(dy >= 0);

            RIint32 dx = -RI_ROUND_TO_INT(slope * dy);

            edge.v1.y = m_vpMaxy;

            edge.v1.x += dx;

        }

    }

    if (edge.v0.y >= edge.v1.y)

        return;

    // \todo Recheck left/right.

    outLeft[0] = (edge.v0.x < m_vpMinx); outLeft[1] = (edge.v1.x < m_vpMinx);

    outRight[1] = (edge.v0.x > m_vpMaxx); outRight[1] = (edge.v1.x > m_vpMaxx);

    if (outLeft[0] && outLeft[1])

    {

        edge.v0.x = m_vpMinx;

        edge.v1.x = m_vpMinx;

        pushEdge(edge);

        return;

    }

    if (outRight[0] && outRight[1])

    {

        edge.v0.x = m_vpMaxx;

        edge.v1.x = m_vpMaxx;

        pushEdge(edge);

        return;

    }

    // From outside -> screen

    if (outLeft[0] || outRight[1])

    {

        // infinite slope?

        double slope = (double)((RIint64)edge.v1.y - edge.v0.y)/((RIint64)edge.v1.x - edge.v0.x);

        if (outLeft[0])

        {

            RIint32 dx = edge.v0.x;

            //RI_ASSERT(dx >= 0);

            // Note the sign.

            RIint32 dy = RI_ROUND_TO_INT(-slope * dx);

            Edge vpart = edge;

            vpart.v1.y = edge.v0.y + dy;

            //vpart.v1.x = edge.v0.x; // = 0?

            // \note This should be flagged instead of setting the smallest possible

            // value because of extremely gentle slopes may cause bugs:

            vpart.v1.x = vpart.v0.x = -0x100000;

            if (vpart.v1.y > vpart.v0.y)

                pushEdge(vpart);

            edge.v0.y += dy;

            edge.v0.x = 0;

        }

    }

    // From screen -> outside

    if (outLeft[1] || outRight[0])

    {

        // infinite slope?

        double slope = (double)((RIint64)edge.v1.y - edge.v0.y)/((RIint64)edge.v1.x - edge.v0.x);

        if (outLeft[1])

        {

            RIint32 dx = edge.v0.x;

            RI_ASSERT(dx >= 0);

            RIint32 dy = RI_ROUND_TO_INT(-slope * dx);

            Edge vpart = edge;

            vpart.v0.y = edge.v0.y + dy;

            vpart.v1.x = vpart.v0.x = LEFT_DISCARD;

            if (vpart.v1.y > vpart.v0.y)

                pushEdge(vpart);

            edge.v1.y = edge.v0.y + dy;

            edge.v1.x = 0;

        }

    }

    if (edge.v0.y >= edge.v1.y)

        return;

    // Finally, add the edge:

    pushEdge(edge);

}

void Rasterizer::addEdge(const Vector2& v0, const Vector2& v1)

{

    if( m_edges.size() >= RI_MAX_EDGES )

        throw std::bad_alloc();	//throw an out of memory error if there are too many edges

    Edge e;

    {

        IVector2 i0(RI_ROUND_TO_INT(v0.x * (1<<X_BITS)), RI_ROUND_TO_INT(v0.y * (1<<Y_BITS)));

        IVector2 i1(RI_ROUND_TO_INT(v1.x * (1<<X_BITS)), RI_ROUND_TO_INT(v1.y * (1<<Y_BITS)));

        if(i0.y == i1.y)

            return;	//skip horizontal edges (they don't affect rasterization since we scan horizontally)

        if (i0.y < i1.y)

        {

            // Edge is going upward

            e.v0 = i0;

            e.v1 = i1;

            e.direction = 1;

        }

        else

        {

            // Edge is going downward

            e.v0 = i1;

            e.v1 = i0;

            e.direction = -1;

        }

    }

    // Clip and insert.

    clipAndAddEdge(e);

}

/*-------------------------------------------------------------------*//*!

* \brief	Set up rasterizer

* \param

* \return

* \note

*//*-------------------------------------------------------------------*/

void Rasterizer::setup(int vpx, int vpy, int vpwidth, int vpheight, VGFillRule fillRule, const PixelPipe* pixelPipe)

{

    RI_ASSERT(vpwidth >= 0 && vpheight >= 0);

    RI_ASSERT(vpx + vpwidth >= vpx && vpy + vpheight >= vpy);

    RI_ASSERT(fillRule == VG_EVEN_ODD || fillRule == VG_NON_ZERO);

    RI_ASSERT(pixelPipe);

    clear();

    m_vpx = vpx;

    m_vpy = vpy;

    m_vpwidth = vpwidth;

    m_vpheight = vpheight;

    if (m_vpheight > m_edges.size())

    {

        int os = m_edges.size();

        m_edges.resize(m_vpheight);

        for (int i = os; i < m_edges.size(); i++)

            m_edges[i] = EDGE_TERMINATOR;

    }

    m_vpMinx = RI_SHL(vpx, X_BITS);

    m_vpMiny = RI_SHL(vpy, Y_BITS);

    m_vpMaxx = RI_SHL(vpx + vpwidth, X_BITS);

    m_vpMaxy = RI_SHL(vpy + vpheight, Y_BITS);

    m_fillRule = fillRule;

    RIuint32 fillRuleMask = fillRule == VG_NON_ZERO ? 0xffffffffu : 1;

    m_fillRuleMask = fillRuleMask;

    m_pixelPipe = pixelPipe;

    m_covMinx = vpx+vpwidth;

    m_covMiny = vpy+vpheight;

    m_covMaxx = vpx;

    m_covMaxy = vpy;

}

/*-------------------------------------------------------------------*//*!

* \brief	Sets scissor rectangles.

* \param

* \return

* \note

*//*-------------------------------------------------------------------*/

void Rasterizer::setScissor(const Array<Rectangle>& scissors)

{

    try

    {

        m_scissorEdges.clear();

        for(int i=0;i<scissors.size();i++)

        {

            if(scissors[i].width > 0 && scissors[i].height > 0)

            {

                ScissorEdge e;

                e.miny = scissors[i].y;

                e.maxy = RI_INT_ADDSATURATE(scissors[i].y, scissors[i].height);

                e.x = scissors[i].x;

                e.direction = 1;

                m_scissorEdges.push_back(e);	//throws bad_alloc

                e.x = RI_INT_ADDSATURATE(scissors[i].x, scissors[i].width);

                e.direction = -1;

                m_scissorEdges.push_back(e);	//throws bad_alloc

            }

        }

    }

    catch(std::bad_alloc)

    {

        m_scissorEdges.clear();

        throw;

    }

}

void Rasterizer::setScissoring(bool enabled)

{

    m_scissor = enabled;

}

static RI_INLINE void small_memcpy32(void* dst, const void* src, size_t n)

{

    RIuint32 *d = (RIuint32*)dst;

    const RIuint32 *s = (const RIuint32*)src;

    while(n)

    {

        *d++ = *s++;

        n-=4;

    }

}

// \todo Move this to some debug file or remove.

#if defined(USE_SSE2) && !defined(_WIN32)

RI_INLINE static void print128(__m128i ll)

{

#if defined(RI_DEBUG)

    unsigned long long v[2];

    _mm_storeu_pd((double*)v, (__m128d)ll);

    RI_PRINTF("0x%016llx %016llx\n", v[0], v[1]);

#else

    (void)ll;

#endif

}

#endif

#if defined(USE_SSE2)

RI_INLINE static __m128i mm_mul4x32(const __m128i a, const __m128i b) {

     __m128i res;

     // \todo Simpler way to do this on intel?

     __m128i m0 = _mm_mul_epu32(a, _mm_shuffle_epi32(b, _MM_SHUFFLE(1, 1, 0, 0)));

     __m128i m1 = _mm_mul_epu32(a, _mm_shuffle_epi32(b, _MM_SHUFFLE(3, 3, 2, 2)));

     res = _mm_castps_si128(_mm_shuffle_ps(_mm_castsi128_ps(m0), _mm_castsi128_ps(m1), _MM_SHUFFLE(2, 0, 2, 0)));

#else

     __asm {

         movdqa xmm1, a;

         movdqa xmm2, b;

         pshufd xmm3, xmm2, 80;

         movdqa xmm0, xmm1;

         pshufd xmm2, xmm2, 250;

         pmuludq xmm0, xmm3;

         pmuludq xmm1, xmm2;

         shufps xmm0, xmm1, 136;

         movdqa res, xmm0;

     }

#endif

     return res;

}

#endif

#if defined(USE_SSE2)

RI_INLINE static void mm_get_xmasks(const __m128i& coords, const __m128i& sampleCoords, __m128i& slWindMask, __m128i& pxWindMask)

{

    const __m128i z = _mm_setzero_si128();

    const __m128i xMask = _mm_cmpeq_epi16(_mm_srai_epi16(coords, Rasterizer::RASTERIZER_BITS), z);

    const __m128i sCmp = _mm_or_si128(_mm_cmpgt_epi16(sampleCoords, coords), _mm_cmpeq_epi16(sampleCoords, coords));

    //const __m128i sCmp = _mm_cmplt_epi16(coords, sampleCoords);

    slWindMask = xMask;

    pxWindMask = _mm_and_si128(xMask, sCmp);

}

#endif