#include <stdio.h>
#include <math.h>
#include <pixman.h>
#include <gtk/gtk.h>

typedef pixman_fixed_16_16_t	fixed_t;


#define fixed_e			((fixed_t) 1)
#define fixed_1			(int_to_fixed(1))
#define fixed_1_minus_e		(fixed_1 - fixed_e)
#define fixed_to_int(f)		((int) ((f) >> 16))
#define int_to_fixed(i)		((fixed_t) ((i) << 16))
#define fixed_frac(f)		((f) & pixman_fixed_1_minus_e)
#define fixed_floor(f)		((f) & ~pixman_fixed_1_minus_e)
#define fixed_ceil(f)		pixman_fixed_floor ((f) + pixman_fixed_1_minus_e)
#define fixed_mod_2(f)		((f) & (pixman_fixed1 | pixman_fixed_1_minus_e))

#define fixed_to_double(f)	(double) ((f) / (double) pixman_fixed_1)
#define double_to_fixed(d)	((pixman_fixed_t) ((d) * 65536.0))


/*
 *    +--------------------------------------------------+
 *    |                           <Y_FRAC_FIRST>         |
 *    | <X_FRAC_FIRST> * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                * * * * * * * * * * * * * * * * * |
 *    |                          | <BIG_STEP>            |
 *    +--------------------------------------------------+
 */

#define MAX_ALPHA(n)	((1 << (n)) - 1)
#define N_Y_FRAC(n)	((n) == 1 ? 1 : (1 << ((n)/2)) - 1)
#define N_X_FRAC(n)	((n) == 1 ? 1 : (1 << ((n)/2)) + 1)

#define STEP_Y_SMALL(n)	(fixed_1 / N_Y_FRAC(n))
#define STEP_Y_BIG(n)	(fixed_1 - (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))

#define Y_FRAC_FIRST(n)	(STEP_Y_SMALL(n) / 2)
#define Y_FRAC_LAST(n)	(Y_FRAC_FIRST(n) + (N_Y_FRAC(n) - 1) * STEP_Y_SMALL(n))

#define STEP_X_SMALL(n)	(pixman_fixed_1 / N_X_FRAC(n))
#define STEP_X_BIG(n)	(pixman_fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))

#define X_FRAC_FIRST(n)	(STEP_X_SMALL(n) / 2)
#define X_FRAC_LAST(n)	(X_FRAC_FIRST(n) + (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))

typedef struct edge_t edge_t;
struct edge_t
{
    fixed_t			x0;
    fixed_t			y0;
    fixed_t			x1;
    fixed_t			y1;
};

#define N_GRID_X 17
#define N_GRID_Y 15

static fixed_t
next_sample_x (fixed_t x)
{
    pixman_fixed_t   f = pixman_fixed_frac(x);
    pixman_fixed_t   i = pixman_fixed_floor(x);

    f = ((f + Y_FRAC_FIRST(N_GRID_X)) / STEP_Y_SMALL(N_GRID_X)) * STEP_Y_SMALL(N_GRID_X) + Y_FRAC_FIRST(N_GRID_X);
    if (f > Y_FRAC_LAST(N_GRID_X))
    {
	f = Y_FRAC_FIRST(N_GRID_X);
	i += pixman_fixed_1;
    }
    return (i | f);
}

static fixed_t
next_sample_y (fixed_t y)
{
    pixman_fixed_t   f = pixman_fixed_frac(y);
    pixman_fixed_t   i = pixman_fixed_floor(y);

    f = ((f + Y_FRAC_FIRST(N_GRID_Y)) / STEP_Y_SMALL(N_GRID_Y)) * STEP_Y_SMALL(N_GRID_Y) + Y_FRAC_FIRST(N_GRID_Y);
    if (f > Y_FRAC_LAST(N_GRID_Y))
    {
	f = Y_FRAC_FIRST(N_GRID_Y);
	i += pixman_fixed_1;
    }
    return (i | f);
}

static fixed_t
sample_step_x (fixed_t x)
{
    (void)x;

    return 1.0;
}

static fixed_t
sample_step_y (fixed_t y)
{
    if (pixman_fixed_frac (y) == Y_FRAC_LAST (N_GRID_Y))
    {
	return STEP_Y_BIG (N_GRID_Y);
    }
    else
    {
	return STEP_Y_SMALL (N_GRID_Y);
    }
}

static void
dda (fixed x0, fixed y0, fixed x1, fixed y1)
{
    fixed dx = x1 - x0;
    fixed dy = y1 - y0;
    int steep = fabs (dy) > fabs (dx);
    fixed dx_sign;
    fixed dy_sign;
    fixed derror;
    fixed xi;
    fixed err;
    fixed yi;

    printf ("line: (%f %f) -> (%f %f)  %s\n", x0, y0, x1, y1, steep? "[steep]" : "");

    if (steep)
    {
	fixed t;

	t = x0; x0 = y0; y0 = t;
	t = x1; x1 = y1; y1 = t;
    }

    if (x0 > x1)
    {
	fixed t;

	t = x0; x0 = x1; x1 = x0;
	t = y0; y0 = y1; y1 = y0;
    }

    yi = next_sample_y (y0);
    xi = next_sample_x (x0);

    err = (yi - y0) * dx - (xi - x0) * dy;

    dx_sign = (dx > 0) ? 1 : -1;
    dy_sign = (dy > 0) ? 1 : -1;

    derror = dx_sign * dy;

    while (xi < next_sample_x (x1))
    {
	fixed px, py;

	if (steep)
	{
	    px = yi;
	    py = xi;
	}
	else
	{
	    px = xi;
	    py = yi;
	}

	printf ("    (%f %f)  (err: %f)  (de: %f)\n", px, py, err, derror);

	err += derror;

	if (err > dx || err < -dx)
	{
	    yi += dy_sign * sample_step_y (yi);

	    err -= dx;
	}

	xi += sample_step_x (xi);
    }
}

static void
ddda (double x0, double y0, double x1, double y1)
{
    dda (pixman_double_to_fixed (x0),
	 pixman_double_to_fixed (y0),
	 pixman_double_to_fixed (x1),
	 pixman_double_to_fixed (y1));
}

int
main (int argc, char **argv)
{
    gtk_init (&argc, &argv);


    ddda (0.5, 0.5, 2.5, 1.6);
    ddda (0.3, 0.2, 3.7, 2.2);
    ddda (3.7, 2.2, 7.2, 2.8);
    ddda (3.7, 2.2, 4.2, 7.2);
    ddda (0.5, 0.5, 1.5, 1.5);
    ddda (0.5, 0.5, 2.5, 2.5);

    return 0;
}