/***************************************************************************/
/*                                                                         */
/*                                                                         */
/* Raven 3D Engine                                                         */
/* Copyright (C) 1996 by Softdisk Publishing                               */
/*                                                                         */
/* Original Design:                                                        */
/*  John Carmack of id Software                                            */
/*                                                                         */
/* Enhancements by:                                                        */
/*  Robert Morgan of Channel 7............................Main Engine Code */
/*  Todd Lewis of Softdisk Publishing......Tools,Utilities,Special Effects */
/*  John Bianca of Softdisk Publishing..............Low-level Optimization */
/*  Carlos Hasan..........................................Music/Sound Code */
/*                                                                         */
/*                                                                         */
/***************************************************************************/

#include <stdlib.h>
#include "d_global.h"
#include "r_refdef.h"
#include "d_video.h"
#include "d_misc.h"
#include "r_public.h"

/**** VARIABLES ****/

/*a scaled object is just encoded like a span                                                   */
unsigned  spantags[MAXSPANS];
unsigned *starttaglist_p, *endtaglist_p;  // set by SortSpans
span_t    spans[MAXSPANS];
int       spansx[MAXSPANS];
int       spanx;
fixed_t   pointz, afrac, hfrac;
int       numspans;
span_t*   span_p;


/**** FUNCTIONS ****/

#define QUICKSORT_CUTOFF 16
#define SWAP(a, b)                                                                                 \
    {                                                                                              \
        temp = a;                                                                                  \
        a    = b;                                                                                  \
        b    = temp;                                                                               \
    }


void MedianOfThree(unsigned* data, unsigned count)
{
    unsigned temp;

    if (count >= 3)
    {
        unsigned* beg = data;
        unsigned* mid = data + (count / 2);
        unsigned* end = data + (count - 1);
        if (*beg > *mid)
        {
            if (*mid > *end)
                SWAP(*beg, *mid)
            else if (*beg > *end)
                SWAP(*beg, *end)
        }
        else if (*mid > *end)
        {
            if (*beg > *end)
                SWAP(*beg, *end)
        }
        else
            SWAP(*beg, *mid);
    }
}


int Partition(unsigned* data, unsigned count)
{
    unsigned part = data[0];
    int      i    = -1;
    int      j    = count;
    unsigned temp;

    while (i < j)
    {
        while (part > data[--j])
            ;
        while (data[++i] > part)
            ;
        if (i >= j)
            break;
        SWAP(data[i], data[j]);
    }
    return j + 1;
}


void QuickSortHelper(unsigned* data, unsigned count)
{
    int left = 0;
    int part;

    if (count > QUICKSORT_CUTOFF)
    {
        while (count > 1)
        {
            MedianOfThree(data + left, count);
            part = Partition(data + left, count);
            QuickSortHelper(data + left, part);
            left += part;
            count -= part;
        }
    }
}


void InsertionSort(unsigned* data, unsigned count)
{
    int      i, j;
    unsigned t;

    for (i = 1; (unsigned)i < count; i++)
    {
        if (data[i] > data[i - 1])
        {
            t = data[i];
            for (j = i; j && t > data[j - 1]; j--)
                data[j] = data[j - 1];
            data[j] = t;
        }
    }
}


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

void DrawDoorPost(void)
{
    fixed_t top, bottom;    // precise y coordinates for post
    int     topy, bottomy;  // pixel y coordinates for post
    fixed_t fracadjust;     // the amount to prestep for the top pixel
    fixed_t scale;
    int     light;

    scale     = FIXEDMUL(pointz, ISCALE);
    sp_source = span_p->picture;

    if (span_p->shadow == 0)
    {
        light = (pointz >> FRACBITS) + span_p->light;
        if (light > MAXZLIGHT)
            return;
        else if (light < 0)
            light = 0;
        sp_colormap = zcolormap[light];
    }
    else if (span_p->shadow == 1)
        sp_colormap = colormaps + (wallglow << 8);
    else if (span_p->shadow == 2)
        sp_colormap = colormaps + (wallflicker1 << 8);
    else if (span_p->shadow == 3)
        sp_colormap = colormaps + (wallflicker2 << 8);
    else if (span_p->shadow == 4)
        sp_colormap = colormaps + (wallflicker3 << 8);
    else if (span_p->shadow >= 5 && span_p->shadow <= 8)
    {
        if (wallcycle == span_p->shadow - 5)
            sp_colormap = colormaps;
        else
        {
            light = (pointz >> FRACBITS) + span_p->light;
            if (light > MAXZLIGHT)
                light = MAXZLIGHT;
            else if (light < 0)
                light = 0;
            sp_colormap = zcolormap[light];
        }
    }
    else if (span_p->shadow == 9)
    {
        light = (pointz >> FRACBITS) + span_p->light + wallflicker4;
        if (light > MAXZLIGHT)
            light = MAXZLIGHT;
        else if (light < 0)
            light = 0;
        sp_colormap = zcolormap[light];
    }

    sp_fracstep  = FIXEDMUL(pointz, ISCALE);
    top          = FIXEDDIV(span_p->y, scale);
    topy         = top >> FRACBITS;
    fracadjust   = top & (FRACUNIT - 1);
    sp_frac      = FIXEDMUL(fracadjust, sp_fracstep);
    topy         = CENTERY - topy;
    sp_loopvalue = 256 << FRACBITS;
    if (topy < scrollmin)
    {
        sp_frac += (scrollmin - topy) * scale;
        while (sp_frac > sp_loopvalue)
            sp_frac -= sp_loopvalue;
        topy = scrollmin;
    }
    bottom  = FIXEDDIV(span_p->yh, scale);
    bottomy = bottom >= ((CENTERY + scrollmin) << FRACBITS) ? scrollmax - 1
                                                            : CENTERY + (bottom >> FRACBITS);
    if (bottomy <= scrollmin || topy >= scrollmax)
        return;
    sp_count = bottomy - topy + 1;
    sp_dest  = viewylookup[bottomy - scrollmin] + spanx;

    if (span_p->spantype == sp_maskeddoor)
        ScaleMaskedPost();
    else
        ScalePost();
}


void ScaleTransPost()
{
    pixel_t color;

    sp_dest -= windowWidth * (sp_count - 1);  // go to the top
    --sp_loopvalue;
    while (--sp_count)
    {
        color = sp_source[sp_frac >> FRACBITS];
        if (color)
            *sp_dest = *(translookup[sp_colormap[color] - 1] + *sp_dest);
        sp_dest += windowWidth;
        sp_frac += sp_fracstep;
        sp_frac &= sp_loopvalue;
    }
}


void DrawSprite(void)
{
    fixed_t     leftx, scale, xfrac, fracstep;
    fixed_t     shapebottom, topheight, bottomheight;
    int         post, x, topy, bottomy, light, shadow, bitshift;
    special_t   specialtype;
    scalepic_t* pic;
    byte*       collumn;
    scaleobj_t* sp;

    /********* floor shadows ***********/
    specialtype = (special_t) (span_p->shadow >> 8);
    shadow      = span_p->shadow & 255;

    if (specialtype == st_maxlight)
        sp_colormap = colormaps;
    else if (specialtype == st_transparent)
        sp_colormap = colormaps;
    else if (shadow == 0)
    {
        light = (pointz >> FRACBITS) + span_p->light;
        if (light > MAXZLIGHT)
            return;
        else if (light < 0)
            light = 0;
        sp_colormap = zcolormap[light];
    }
    else if (span_p->shadow == 1)
        sp_colormap = colormaps + (wallglow << 8);
    else if (span_p->shadow == 2)
        sp_colormap = colormaps + (wallflicker1 << 8);
    else if (span_p->shadow == 3)
        sp_colormap = colormaps + (wallflicker2 << 8);
    else if (span_p->shadow == 4)
        sp_colormap = colormaps + (wallflicker3 << 8);
    else if (span_p->shadow >= 5 && span_p->shadow <= 8)
    {
        if (wallcycle == span_p->shadow - 5)
            sp_colormap = colormaps;
        else
        {
            light = (pointz >> FRACBITS) + span_p->light;
            if (light > MAXZLIGHT)
                light = MAXZLIGHT;
            else if (light < 0)
                light = 0;
            sp_colormap = zcolormap[light];
        }
    }
    else if (shadow == 9)
    {
        light = (pointz >> FRACBITS) + span_p->light + wallflicker4;
        if (light > MAXZLIGHT)
            light = MAXZLIGHT;
        else if (light < 0)
            light = 0;
        sp_colormap = zcolormap[light];
    }

    pic = (scalepic_t*) span_p->picture;
    sp  = (scaleobj_t*) span_p->structure;

    bitshift = FRACBITS - sp->scale;

    shapebottom = span_p->y;
    // project the x and height
    scale       = FIXEDDIV(SCALE, pointz);
    fracstep    = FIXEDMUL(pointz, ISCALE) << sp->scale;
    sp_fracstep = fracstep;
    leftx       = span_p->x2;
    leftx -= pic->leftoffset << bitshift;
    x = CENTERX + (FIXEDMUL(leftx, scale) >> FRACBITS);
    // step through the shape, drawing posts where visible
    xfrac = 0;
    if (x < 0)
    {
        xfrac -= fracstep * x;
        x = 0;
    }
    sp_loopvalue = (256 << FRACBITS);

    for (; x < windowWidth; x++)
    {
        post = xfrac >> FRACBITS;
        if (post >= pic->width)
            return;  // shape finished drawing
        xfrac += fracstep;
        if (pointz >= wallz[x]
            && (pointz >= wallz[x] + TILEUNIT
                || (specialtype != st_noclip && specialtype != st_transparent)))
            continue;
        // If the offset of the columns is zero then there is no data for the post
        if (pic->collumnofs[post] == 0)
            continue;
        collumn      = (byte*) pic + pic->collumnofs[post];
        topheight    = shapebottom + (*collumn << bitshift);
        bottomheight = shapebottom + (*(collumn + 1) << bitshift);
        collumn += 2;
        // scale a post

        bottomy = CENTERY - (FIXEDMUL(bottomheight, scale) >> FRACBITS);
        if (bottomy < scrollmin)
            continue;
        if (bottomy >= scrollmax)
            bottomy = scrollmax - 1;

        topy = CENTERY - (FIXEDMUL(topheight, scale) >> FRACBITS);
        if (topy < scrollmin)
        {
            sp_frac = (scrollmin - topy) * sp_fracstep;
            topy    = scrollmin;
        }
        else
            sp_frac = 0;

        if (topy >= scrollmax)
            continue;

        sp_count = bottomy - topy + 1;

        sp_dest   = viewylookup[bottomy - scrollmin] + x;
        sp_source = collumn;
        if (specialtype == st_transparent)
            ScaleTransPost();
        else
            ScaleMaskedPost();
    }
}


void DrawSpans(void)
/* Spans farther than MAXZ away should NOT have been entered into the list */
{
    unsigned *spantag_p, tag;
    int       spannum;
    int       x2;
    fixed_t   lastz;  // the pointz for which xystep is valid
    fixed_t   length;
    fixed_t   zerocosine, zerosine;
    fixed_t   zeroxfrac = 0, zeroyfrac = 0;
    fixed_t   xf2, yf2;  // endpoint texture for sloping spans
    int       angle;
    int       light;
    int       px, py, h1, x1, center, y1, x;
    fixed_t   a, w;
    pixel_t   color;

    // set up backdrop stuff
    w      = windowWidth / 2;
    center = viewangle & 255;

    // set up for drawing
    starttaglist_p = spantags;
    if (numspans)
    {
        QuickSortHelper(starttaglist_p, numspans);
        InsertionSort(starttaglist_p, numspans);
    }
    endtaglist_p = starttaglist_p + numspans;
    spantag_p    = starttaglist_p;

    angle = viewfineangle + pixelangle[0];
    angle &= TANANGLES * 4 - 1;
    zerocosine = cosines[angle];
    zerosine   = sines[angle];
    // draw from back to front
    x2    = -1;
    lastz = -1;
    // draw everything else
    while (spantag_p != endtaglist_p)
    {
        tag     = *spantag_p++;
        pointz  = tag >> ZTOFRAC;
        spannum = tag & SPANMASK;
        span_p  = &spans[spannum];
        spanx   = spansx[spannum];
        switch (span_p->spantype)
        {
            case sp_flat:
            case sp_flatsky:
                // floor / ceiling span
                if (pointz != lastz)
                {
                    lastz    = pointz;
                    mr_xstep = FIXEDMUL(pointz, xscale);
                    mr_ystep = FIXEDMUL(pointz, yscale);
                    // calculate starting texture point
                    length    = FIXEDDIV(pointz, pixelcosine[0]);
                    zeroxfrac = mr_xfrac = viewx + FIXEDMUL(length, zerocosine);
                    zeroyfrac = mr_yfrac = viewy - FIXEDMUL(length, zerosine);
                    x2                   = 0;
                }
                if (spanx != x2)
                {
                    mr_xfrac = zeroxfrac + mr_xstep * spanx;
                    mr_yfrac = zeroyfrac + mr_ystep * spanx;
                }

                /* floor shadows */
                if (span_p->shadow == 0)
                {
                    light = (pointz >> FRACBITS) + span_p->light;
                    if (light > MAXZLIGHT)
                        break;
                    else if (light < 0)
                        light = 0;
                    mr_colormap = zcolormap[light];
                }
                else if (span_p->shadow == 9)
                {
                    light = (pointz >> FRACBITS) + span_p->light + wallflicker4;
                    if (light > MAXZLIGHT)
                        break;
                    else if (light < 0)
                        light = 0;
                    mr_colormap = zcolormap[light];
                }
                else
                    mr_colormap = (byte*) span_p->shadow;

                y1 = span_p->y - scrollmin;

                if ((unsigned) y1 >= 200)
                    break;

                mr_dest    = viewylookup[y1] + spanx;
                mr_picture = span_p->picture;
                x2         = span_p->x2;

                if ((unsigned) x2 > 320)
                    break;

                mr_count = x2 - spanx;
                MapRow();

                if (span_p->spantype == sp_flatsky)
                {
                    py       = span_p->y - scrollmin;
                    px       = spanx;
                    mr_count = span_p->x2 - spanx;
                    mr_dest  = viewylookup[py] + px;
                    if (windowHeight != 64)
                        py = span_p->y + 64;
                    h1 = (hfrac * py) >> FRACBITS;
                    if (px <= w)
                    {
                        a = ((TANANGLES / 2) << FRACBITS) + afrac * (w - px);
                        while (px <= w && mr_count > 0)
                        {
                            x  = backtangents[a >> FRACBITS];
                            x2 = center - x + windowWidth - 257;
                            x2 &= 255;
                            if (*mr_dest == 255)
                                *mr_dest = *(backdroplookup[h1] + x2);
                            a -= afrac;
                            px++;
                            mr_count--;
                            mr_dest++;
                        }
                    }
                    if (px > w)
                    {
                        a = ((TANANGLES / 2) << FRACBITS) + afrac * (px - w);
                        while (mr_count > 0)
                        {
                            x1 = center + backtangents[a >> FRACBITS];
                            x1 &= 255;
                            if (*mr_dest == 255)
                                *mr_dest = *(backdroplookup[h1] + x1);
                            a += afrac;
                            px++;
                            mr_count--;
                            mr_dest++;
                        }
                    }
                }

                break;
            case sp_sky:
                py = span_p->y - scrollmin;
                if ((unsigned) py >= 200)
                    break;
                px = spanx;

                if ((unsigned) span_p->x2 > 320)
                    break;

                mr_count = span_p->x2 - spanx;
                mr_dest  = viewylookup[py] + px;
                if (windowHeight != 64)
                    py = span_p->y + 64;
                h1 = (hfrac * py) >> FRACBITS;
                if (px <= w)
                {
                    a = ((TANANGLES / 2) << FRACBITS) + afrac * (w - px);
                    while (px <= w && mr_count > 0)
                    {
                        x  = backtangents[a >> FRACBITS];
                        x2 = center - x + windowWidth - 257;
                        x2 &= 255;
                        *mr_dest = *(backdroplookup[h1] + x2);
                        a -= afrac;
                        px++;
                        mr_count--;
                        mr_dest++;
                    }
                }
                if (px > w)
                {
                    a = ((TANANGLES / 2) << FRACBITS) + afrac * (px - w);
                    while (mr_count > 0)
                    {
                        x1 = center + backtangents[a >> FRACBITS];
                        x1 &= 255;
                        *mr_dest = *(backdroplookup[h1] + x1);
                        a += afrac;
                        px++;
                        mr_count--;
                        mr_dest++;
                    }
                }
                break;
            case sp_step:
                x            = span_p->x2;
                sp_dest      = tpwalls_dest[x];
                sp_source    = span_p->picture;
                sp_colormap  = tpwalls_colormap[x];
                sp_frac      = span_p->y;
                sp_fracstep  = span_p->yh;
                sp_count     = tpwalls_count[x];
                sp_loopvalue = (fixed_t) span_p->light << FRACBITS;
                ScalePost();
                break;
            case sp_shape:
                DrawSprite();
                break;
            case sp_slope:
            case sp_slopesky:
                // sloping floor / ceiling span
                lastz = -1;  // we are going to get out of order here, so

                if (span_p->shadow == 0)
                {
                    light = (pointz >> FRACBITS) + span_p->light;
                    if (light > MAXZLIGHT)
                        break;
                    else if (light < 0)
                        light = 0;
                    mr_colormap = zcolormap[light];
                }
                else if (span_p->shadow == 9)
                {
                    light = (pointz >> FRACBITS) + span_p->light + wallflicker4;
                    if (light > MAXZLIGHT)
                        break;
                    else if (light < 0)
                        light = 0;
                    mr_colormap = zcolormap[light];
                }
                else
                    mr_colormap = (byte*) span_p->shadow;

                x2 = span_p->x2;
                y1 = span_p->y - scrollmin;

                if ((unsigned) y1 >= 200)
                    break;
                if ((unsigned) x2 > 320)
                    break;

                mr_dest    = viewylookup[y1] + spanx;
                mr_picture = span_p->picture;
                mr_count   = x2 - spanx;
                // calculate starting texture point
                length = FIXEDDIV(pointz, pixelcosine[spanx]);
                angle  = viewfineangle + pixelangle[spanx];
                angle &= TANANGLES * 4 - 1;
                mr_xfrac = viewx + FIXEDMUL(length, cosines[angle]);
                mr_yfrac = viewy - FIXEDMUL(length, sines[angle]);
                // calculate ending texture point
                //  (yh is pointz2 for ending point)
                length = FIXEDDIV(span_p->yh, pixelcosine[x2]);
                angle  = viewfineangle + pixelangle[x2];
                angle &= TANANGLES * 4 - 1;
                xf2      = viewx + FIXEDMUL(length, cosines[angle]);
                yf2      = viewy - FIXEDMUL(length, sines[angle]);
                mr_xstep = (xf2 - mr_xfrac) / mr_count;
                mr_ystep = (yf2 - mr_yfrac) / mr_count;
                MapRow();

                if (span_p->spantype == sp_slopesky)
                {
                    py       = span_p->y - scrollmin;
                    px       = spanx;
                    mr_count = span_p->x2 - spanx;
                    mr_dest  = viewylookup[py] + px;
                    if (windowHeight != 64)
                        py = span_p->y + 64;
                    h1 = (hfrac * py) >> FRACBITS;
                    if (px <= w)
                    {
                        a = ((TANANGLES / 2) << FRACBITS) + afrac * (w - px);
                        while (px <= w && mr_count > 0)
                        {
                            x  = backtangents[a >> FRACBITS];
                            x2 = center - x + windowWidth - 257;
                            x2 &= 255;
                            if (*mr_dest == 255)
                                *mr_dest = *(backdroplookup[h1] + x2);
                            a -= afrac;
                            px++;
                            mr_count--;
                            mr_dest++;
                        }
                    }
                    if (px > w)
                    {
                        a = ((TANANGLES / 2) << FRACBITS) + afrac * (px - w);
                        while (mr_count > 0)
                        {
                            x1 = center + backtangents[a >> FRACBITS];
                            x1 &= 255;
                            if (*mr_dest == 255)
                                *mr_dest = *(backdroplookup[h1] + x1);
                            a += afrac;
                            px++;
                            mr_count--;
                            mr_dest++;
                        }
                    }
                }
                break;
            case sp_door:
            case sp_maskeddoor:
                DrawDoorPost();
                break;
            case sp_transparentwall:
                x            = span_p->x2;
                sp_dest      = tpwalls_dest[x];
                sp_source    = span_p->picture;
                sp_colormap  = tpwalls_colormap[x];
                sp_frac      = span_p->y;
                sp_fracstep  = span_p->yh;
                sp_count     = tpwalls_count[x];
                sp_loopvalue = (fixed_t) span_p->light << FRACBITS;
                ScaleMaskedPost();
                break;
            case sp_inviswall:
                x            = span_p->x2;
                sp_dest      = tpwalls_dest[x];
                sp_source    = span_p->picture;
                sp_colormap  = tpwalls_colormap[x];
                sp_frac      = span_p->y;
                sp_fracstep  = span_p->yh;
                sp_count     = tpwalls_count[x];
                sp_loopvalue = (fixed_t) span_p->light << FRACBITS;
                sp_dest -= windowWidth * (sp_count - 1);  // go to the top
                --sp_loopvalue;
                while (sp_count--)
                {
                    color = sp_source[sp_frac >> FRACBITS];
                    if (color)
                        *sp_dest = *(translookup[sp_colormap[color] - 1] + *sp_dest);
                    sp_dest += windowWidth;
                    sp_frac += sp_fracstep;
                    sp_frac &= sp_loopvalue;
                }
                break;
        }
    }
}
