#include <stdio.h>
#include <string.h>

#include <proto/utility.h>

#include "graffiti_ellipse.h"

extern WORD fastsin (WORD, WORD);
extern WORD fastcos (WORD, WORD);

struct EllipseRenderStruct
{
    struct GraffitiData * gd;
    struct GraffitiHookData * ghd;
    UWORD cx, cy; /* center */
    WORD x1, y1; /* Startpoint 1 */
    WORD x2, y2; /* Startpoint 2 */
    void (*SetPoint)(struct EllipseRenderStruct * ers, WORD x, WORD y);
    APTR UserData;
};

/* d = domain (v) ; 2^d > v >= 2^(d-1). It's an external routine written
   in highly optimized assembler code. If you want to do it youself, here's
   the idea:

	for (d=1; v; d ++)
	    v = v >> 1;

    "count how many times v can be shifted right until it's zero". Note that
    we start counting with 1 and not 0 ! */

static ULONG domain (ULONG x)
{
    register ULONG d;

    for (d=1; x; x >>= 1)
	d ++;

    return (d);
} /* domain */

/* This computes the points around the ellipse */
#define compute(rx,dx,y)        rx += y + y;    \
				dx  = rx >> k;	\
				rx &= mask;

/* Simple MAX-macro. */
#define MAX(a,b)    ((a) >= (b) ? (a) : (b))


/* This routine is a 8WS filter. The ellipse routine calculates every point
   around the outline of the ellipse. Ie. if the real point is inbetween
   two pixels both pixels will be set (sometimes at least). This makes the
   ellipse thick at some points and thin at others. This filter filters
   all unneccessary points out. xp/yp are pointers to BOOLs that tell
   "Is the step in x-/y-direction pending ?". dx/dy tell the distance
   to the last set point and xsl/ysl tells the slope (first derative in
   this point).

	Everyone who is interested is invited to read the paper. If you see
    the supplied pictures, you will get the idea soon. */

static BOOL do_put (BOOL * xp, BOOL * yp, int dx, int dy, int xsl, int ysl)
{
    BOOL xst, yst;  /* Here we store "Do step" */
    BOOL xs, ys;    /* Positive slope ? (0 is positive) */

    xst = (dx != 0);    /* Did we move ? */
    yst = (dy != 0);

    /* If we did NOT move, no need to output that point */
    if (xst || yst)
    {
	/* Diagonal steps always succeed */
	if ((xst && (yst || *xp)) || (yst && *yp))
	{
	    *xp = xst;
	    *yp = yst;
	}
	else
	{
	    /* Which slope ? */
	    xs = (xsl >= 0) ? 1 : 0;
	    ys = (ysl >= 0) ? 1 : 0;

	    /* x step */
	    if (xst)
	    {
		/* always move horizontally */
		*xp = TRUE;

		/* y is pending and different slopes ? */
		if (*yp && (xs != ys))
		    *yp = FALSE;    /* No need to do y anymore */
		else
		    return (FALSE); /* Don't output point */
	    }
	    else
	    {
		/* This is basically the same for y */
		*yp = TRUE;

		if (*xp && (xs == ys))
		    *xp = FALSE;
		else
		    return (FALSE);
	    }
	}

	return (TRUE);
    }

    return (FALSE);
} /* do_put */

static UBYTE use[256];
static UWORD slice[2][256];

/* Add a new point to the ellipse. */
static void SetPoint_Draw (struct EllipseRenderStruct * ers, WORD x, WORD y)
{
    Graffiti_SetPixel (GH(ers->gd), ers->cx+x, ers->cy+y);
} /* SetPixel_Draw */

static void SetPoint_Fill (struct EllipseRenderStruct * ers, WORD x, WORD y)
{
    /* Offset the point */
    x += ers->cx;
    y += ers->cy;

    if (ers->gd->gh.FilterList)
    {
	if (x < ers->ghd->x1)
	    ers->ghd->x1 = x;
	if (x > ers->ghd->x2)
	    ers->ghd->x2 = x;
	if (y < ers->ghd->y1)
	    ers->ghd->y1 = y;
	if (y > ers->ghd->y2)
	    ers->ghd->y2 = y;
    }

    /* Clip the point vertically: Ignore all points outside the valid
       rect. */
    if (y >= ers->gd->ClipTop && y <= ers->gd->ClipBottom)
    {
	/* Don't clip horizontally. We do this when we actually draw
	   each slice. This will allow us to suppress all non-visible
	   lines alltogether. See below for more details. */

	/* Depending on how many points already have been collected
	   for this slice ... */
	switch (use[y])
	{
	case 0: /* first time: just remember position */
	    use[y] ++;
	    slice[0][y] = x;
	    break;

	case 1: /* second time: sort from left to right */
	    use[y] ++;
	    if (slice[0][y] <= x)
		slice[1][y] = x;
	    else
	    {
		slice[1][y] = slice[0][y];
		slice[0][y] = x;
	    }
	    break;

	case 2: /* another time: extend left or right */
	    if (slice[0][y] > x)
		slice[0][y] = x;
	    else if (slice[1][y] < x)
		slice[1][y] = x;
	    break;

	} /* switch */
    } /* y valid */
} /* SetPixel_Fill */

/*
    for (k = 0..31)
	N = (int)((PI * (double)(1 << (k-2))) + 0.5);
*/
static const ULONG Ntab[] =
{
    0,
    0,
    3,
    6,
    13,
    25,
    50,
    101,
    201,
    402,
    804,
    1608,
    3217,
    6434,
    12868,
    25736,
    51472,
    102944,
    205887,
    411775,
    823550,
    1647099,
    3294199,
    6588397,
    13176795,
    26353589,
    52707179,
    105414357,
    210828714,
    421657428,
    843314857,
    1686629713,
};

/*  This is the long-awaited routine you do all this crap for. It takes
    two points as parameters. See above for details */
static void ellipse (struct EllipseRenderStruct * ers)
{
#define put_pixel(x,y) (*(ers->SetPoint))(ers, x, y)
    int dx1, dx2, rx1, rx2,
	dy1, dy2, ry1, ry2,
	N;
    int k;
    int mask;
    int xold1, yold1, xold2, yold2;
    BOOL xp1, xp2, yp1, yp2;

    /* The ellipse should be drawn counterclockwise. Find the direction be
       examining the sign of the vector-multiplication */
    if ((ers->x1*ers->y2-ers->y1*ers->x2) < 0)
    {
	ers->x2 = -ers->x2;
	ers->y2 = -ers->y2;
    }

    /* Now we need some constants. These are necessary for some magic in
       compute(). No idea how it works :-) */
    dx1 = ers->x1*ers->x1 + ers->x2*ers->x2;
    dy1 = ers->y1*ers->y1 + ers->y2*ers->y2;

    /* How many bits take the consts at most ? */
    k = ((domain (MAX(dx1, dy1)) + 1) / 2) + 1;

    /* create a mask accordingly. We could use a table here:

	k   mask
	0   cannot happen (k is always > 0)
	1   0x00000001
	2   0x00000003
	3   0x00000007
	4   0x0000000F
	5   0x0000001F
	.	...

	*/
    mask = (1 << k) - 1;

    /* Draw the first 4 pixels. These are always correct */
    put_pixel (+ers->x1, +ers->y1);
    put_pixel (-ers->x1, -ers->y1);
    put_pixel (+ers->x2, +ers->y2);
    put_pixel (-ers->x2, -ers->y2);

    /* Init of all the stuff */
    dx1 = dx2 = dy1 = dy2 = 0;
    rx1 = rx2 = ry1 = ry2 = 1 << (k-1);

    xold1 = ers->x1; yold1 = ers->y1; xold2 = ers->x2; yold2 = ers->y2;
    xp1 = yp1 = xp2 = yp2 = TRUE;

    /* IMPORTANT: This many pixels will be drawn !! Since the ellipse
       needs two points per line, we have N/2 lines ! (necessary for
       filling if we allow dynamic amounts of slices) */
    N = Ntab[k];

    /* NOTE: The algorithm uses the symmetry of the ellipse for speed.
       If you don't need that or have special effects (ie. set every
       20th point only), you calculate N like this:

	    N = (int)((PI * (double)(1 << k)) + 0.5);
					  ^

       and below you don't set two points at once (I will mention it
       again below). */

    while (N > 0)
    {
	N --;

	/* These are in fact two pairs of sin(y)/cos(x) calculations. */
	rx1 -= dx2;
	compute (rx1, dx1, ers->x2);
	ers->x1 += dx1;

	rx2 += dx1;
	compute (rx2, dx2, ers->x1);
	ers->x2 -= dx2;

	ry1 -= dy2;
	compute (ry1, dy1, ers->y2);
	ers->y1 += dy1;

	ry2 += dy1;
	compute (ry2, dy2, ers->y1);
	ers->y2 -= dy2;

	/* Filter the first point */
	if (do_put (&xp1, &yp1, dx1, dy1, ers->x2, ers->y2))
	{
	    put_pixel (+xold1, +yold1);
	    put_pixel (-xold1, -yold1);
	}

	xold1 = ers->x1;
	yold1 = ers->y1;

	/* NOTE: If you want to draw the ellipse without symmetry,
	   drop the next few lines (upto the "yold2 = y2;"). */
	if (do_put (&xp2, &yp2, dx2, dy2, ers->x1, ers->y1))
	{
	    put_pixel (+xold2, +yold2);
	    put_pixel (-xold2, -yold2);
	}

	xold2 = ers->x2;
	yold2 = ers->y2;
    }

    /* Anything left ? */
    if (xp1 || yp1)
    {
	put_pixel (+ers->x1, +ers->y1);
	put_pixel (-ers->x1, -ers->y1);
    }

    /* NOTE: yank these also for a one-way-round ellipse */
    if (xp2 || yp2)
    {
	put_pixel (+ers->x2, +ers->y2);
	put_pixel (-ers->x2, -ers->y2);
    }

} /* ellipse */

void fill_slices (struct EllipseRenderStruct * ers)
{
    struct GraffitiHookData * ghd;
    struct GraffitiData * gd;
    WORD y1, x1, x2;
    UWORD x, y;
    UBYTE col;

    gd = ers->gd;

    if (ers->gd->gh.FilterList)
    {
	ghd = ers->ghd;
	col = ers->gd->gh.FG;
    }

    /* Draw the filled ellipse */
    for (y1=gd->ClipTop; y1<=gd->ClipBottom; y1 ++)
    {
	/* If the slice is ok, it contains 2 points */
	if (use[y1] == 2)
	{
	    /* Read the two points */
	    x1 = slice[0][y1];
	    x2 = slice[1][y1];

	    /* clip them */
	    if (x1 < gd->ClipLeft)
		x1 = gd->ClipLeft;

	    if (x2 > gd->ClipRight)
		x2 = gd->ClipRight;

	    /* draw only if the coordinates are ok. What happens ?
		Look at this:

		    invalid area    |	valid area  | invalid area

		1)	 x1  x2
		2)	 x1		 x2
		3)	 x1				     x2
		4)			 x1  x2
		5)			 x1		     x2
		6)					 x1  x2

		Since we sorted the points, x1 is ALWAYS less than x2.

		Case	    Desciption
		    1	   Do nothing. x1 gets clipped to LEFT and thus
			   becomes greater than x2.
		    2	   x1 get clipped to LEFT and a line is drawn from
			   LEFT to x2. Exactly what we wanted
		    3	   Draws a line from LEFT to RIGHT (x2 gets clipped
			   to RIGHT)
		    4	   Nothing is changed. We draw from x1 to x2.
		    5	   x2 is clipped to RIGHT. We draw from x1 to RIGHT.
		    6	   Now x2 becomes RIGHT and thus is less than x1.
			   The line is not drawn.

	    */

	    if (x1 <= x2)
	    {
		/*  If you want to speed up thinge even more (but then
		    you have to bypass the OS), you can set two points
		    at the start and end of every slice and use the
		    blitter-fill to draw it. */
		if (ers->gd->gh.FilterList)
		{
		    y = y1 - ghd->y1;
		    x = x1 - ghd->x1;

		    for ( ; x1<=x2; x1++,x++)
		    {
			ghd->col = col;

			Graffiti_DrawPixel (GH(gd), x, y, ghd);
		    }
		}
		else
		{
		    Graffiti_FillRect (GH(gd), x1, y1, x2, y1);
		}
	    }
	} /* two point in this slice */
    } /* for all slices */
} /* fill_slices */

void Graffiti_DrawEllipse_x (struct GraffitiData * gd, WORD x, WORD y,
    WORD rx, WORD ry)
{
    struct EllipseRenderStruct ers;
    struct GraffitiHookData ghd;

    if (gd->gh.FilterList)
    {
	ers.ghd = &ghd;

	ghd.x1 = gd->Width;
	ghd.y1 = gd->Height;
	ghd.x2 = 0;
	ghd.y2 = 0;
    }

    ers.gd = gd;
    ers.cx = x;
    ers.cy = y;
    ers.x1 = rx;
    ers.y1 = 0;
    ers.x2 = 0;
    ers.y2 = ry;

    ers.SetPoint = SetPoint_Draw;

    ellipse (&ers);

} /* Graffiti_DrawEllipse_x */

void Graffiti_FillEllipse_x (struct GraffitiData * gd, WORD x, WORD y,
    WORD rx, WORD ry)
{
    struct EllipseRenderStruct ers;
    struct GraffitiHookData ghd;

    if (gd->gh.FilterList)
    {
	ers.ghd = &ghd;

	ghd.x1 = gd->Width;
	ghd.y1 = gd->Height;
	ghd.x2 = 0;
	ghd.y2 = 0;
    }

    /* Init usage array */
    memset (use, 0, sizeof (use));

    ers.gd = gd;
    ers.cx = x;
    ers.cy = y;
    ers.x1 = rx;
    ers.y1 = 0;
    ers.x2 = 0;
    ers.y2 = ry;

    ers.SetPoint = SetPoint_Fill;

    ellipse (&ers);

    fill_slices (&ers);
} /* Graffiti_FillEllipse_x */

/* Same as above, but you can specify the diameters and the angle
   of rotation. rx, ry : radii, w: angle (0..65535) */
void Graffiti_DrawGenEllipse_x (struct GraffitiData * gd, WORD x, WORD y,
    WORD rx, WORD ry, WORD w)
{
    /* WORD rx1, ry1, rx2, ry2; */
    struct EllipseRenderStruct ers;
    struct GraffitiHookData ghd;

    if (gd->gh.FilterList)
    {
	ers.ghd = &ghd;

	ghd.x1 = gd->Width;
	ghd.y1 = gd->Height;
	ghd.x2 = 0;
	ghd.y2 = 0;
    }

    /* Calculate sin/cos for this angle. * /
    rx1 = fastcos (-w, rx);
    rx2 = fastsin (-w, rx);
    ry1 = fastsin (-w, ry);
    ry2 = fastcos (-w, ry); */

    w = -w;

    /* Fill struct */
    ers.gd = gd;
    ers.cx = x;
    ers.cy = y;
    ers.x1 = fastcos (w, rx);
    ers.y1 = fastsin (w, rx);
    ers.x2 = -fastsin (w, ry);
    ers.y2 = fastcos (w, ry);

    ers.SetPoint = SetPoint_Draw;

    /* Draw ellipse */
    ellipse (&ers);

} /* Graffiti_DrawGenEllipse_x */

void Graffiti_FillGenEllipse_x (struct GraffitiData * gd, WORD x, WORD y,
    WORD rx, WORD ry, WORD w)
{
    /* WORD rx1, ry1, rx2, ry2; */
    struct EllipseRenderStruct ers;
    struct GraffitiHookData ghd;

    if (gd->gh.FilterList)
    {
	ers.ghd = &ghd;

	ghd.x1 = gd->Width;
	ghd.y1 = gd->Height;
	ghd.x2 = 0;
	ghd.y2 = 0;
    }

    /* Erase usage array */
    memset (use, 0, sizeof (use));

    w = -w;

    ers.gd = gd;
    ers.gd = gd;
    ers.cx = x;
    ers.cy = y;
    ers.x1 = fastcos (w, rx);
    ers.y1 = fastsin (w, rx);
    ers.x2 = -fastsin (w, ry);
    ers.y2 = fastcos (w, ry);

    ers.SetPoint = SetPoint_Fill;

    /* Draw ellipse */
    ellipse (&ers);

    fill_slices (&ers);
} /* Graffiti_FillGenEllipse_x */