fixpoint

1 files changed, 105 insertions, 65 deletions

diff --git a/dda.c b/dda.c
index 08e60f2..20cdc6e 100644
--- a/dda.c
+++ b/dda.c
@@ -1,98 +1,136 @@
 #include <stdlib.h>
 #include <stdio.h>
 #include <math.h>
-
+#include <stdint.h>
 #include "testdata.c"
 
-#define N_STEPS  (4)
-#define STEP  (1/((double)N_STEPS))
+typedef uint32_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) >> 8))
+#define int_to_fixed(i)         ((fixed_t) ((i) << 8))
+#define fixed_frac(f)           ((f) & fixed_1_minus_e)
+#define fixed_floor(f)          ((f) & ~fixed_1_minus_e)
+#define fixed_ceil(f)           fixed_floor ((f) + fixed_1_minus_e)
+#define fixed_mod_2(f)          ((f) & (fixed1 | fixed_1_minus_e))
+#define fixed_max_int           (0x7fffff)
+
+#define fixed_to_double(f)      (double) ((f) / (double) fixed_1)
+#define double_to_fixed(d)      ((fixed_t) ((d) * 256.0))
+
+#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 N_GRID_X               3
-#define N_GRID_Y               3
+#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 BIG_STEP_Y             0.5
-#define SMALL_STEP_Y           0.25
-#define FIRST_STEP_Y           0.125
+#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 BIG_STEP_X             0.5
-#define SMALL_STEP_X           0.25
-#define FIRST_STEP_X           0.125
+#define STEP_X_SMALL(n) (fixed_1 / N_X_FRAC(n))
+#define STEP_X_BIG(n)   (fixed_1 - (N_X_FRAC(n) - 1) * STEP_X_SMALL(n))
 
-static double
+#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))
+
+#define N_GRID_X               N_X_FRAC(8)
+#define N_GRID_Y               N_Y_FRAC(8)
+
+#define BIG_STEP_Y             STEP_Y_BIG(8)
+#define SMALL_STEP_Y           STEP_Y_SMALL(8)
+#define FIRST_STEP_Y           Y_FRAC_FIRST(8)
+
+#define BIG_STEP_X             STEP_X_BIG(8)
+#define SMALL_STEP_X           STEP_X_SMALL(8)
+#define FIRST_STEP_X           X_FRAC_FIRST(8)
+
+static fixed_t
 sample_to_pos (int y)
 {
     return (y >> 8) + (y & 0xff) * SMALL_STEP_Y + FIRST_STEP_Y;
 }
 
 static int
-next_sample_y (double y)
+next_sample_y (fixed_t y)
 {
-    int i = floor (y);
-    int sno = floor ((y - i - FIRST_STEP_Y) / SMALL_STEP_Y) + 1;
-    int r;
+    fixed_t f = fixed_frac (y);
+    fixed_t i = fixed_floor (y);
+    int sno;
 
-    if (sno == N_GRID_X)
-	sno++;
+    sno = ((f - FIRST_STEP_Y + SMALL_STEP_Y) / SMALL_STEP_Y - 1);
 
-    if (sno > N_GRID_X)
+    if (sno == N_GRID_Y)
+	sno++;
+    if (sno > N_GRID_Y)
     {
-	sno -= (N_GRID_X + 1);
-	i++;
+	if (fixed_to_int (i) == fixed_max_int)
+	{
+	    sno = N_GRID_Y; /* saturate */
+	}
+	else
+	{
+	    sno -= (N_GRID_Y + 1);
+	    ++i;
+	}
     }
 
-    r = (i << 8) | sno;
-
-    return r;
+    return i | sno;
 }
 
 static int
-next_sample_x (double x)
+next_sample_x (fixed_t x)
 {
-    return next_sample_y (x);
-}
+    fixed_t f = fixed_frac (x);
+    fixed_t i = fixed_floor (x);
+    int sno;
 
-static double
-sample_step_x_forward (double x)
-{
-    if ((x - floor (x)) == 0.625)
-	return 0.5;
-    else
-	return 0.25;
-}
+    sno = ((f - FIRST_STEP_X + SMALL_STEP_X) / SMALL_STEP_X - 1);
 
-static double
-sample_step_x_backward (double x)
-{
-    if ((x - floor (x)) == 0.125)
-	return 0.5;
-    else
-	return 0.25;
+    if (sno == N_GRID_X)
+	sno++;
+    if (sno > N_GRID_X)
+    {
+	if (fixed_to_int (i) == fixed_max_int)
+	{
+	    sno = N_GRID_X; /* saturate */
+	}
+	else
+	{
+	    sno -= (N_GRID_X + 1);
+	    ++i;
+	}
+    }
+
+    return i | sno;
 }
 
 typedef struct
 {
     int xi;
-    int yi;
     int bottom;
-    double e;
-    double delta_e_big_x;
-    double delta_e_small_x;
-    double delta_e_big_y;
-    double delta_e_small_y;
+    int64_t e;
+    int64_t delta_e_big_x;
+    int64_t delta_e_small_x;
+    int64_t delta_e_big_y;
+    int64_t delta_e_small_y;
 } edge_t;
 
 static void
-edge_init (edge_t *edge, double x0, double y0, double x1, double y1)
+edge_init (edge_t *edge, fixed_t x0, fixed_t y0, fixed_t x1, fixed_t y1)
 {
-    double dx = (x1 - x0);
-    double dy = (y1 - y0);
+    int64_t dx = (x1 - x0);
+    int64_t dy = (y1 - y0);
+    int yi = next_sample_y (y0);
 
     edge->xi = next_sample_x (x0);
-    edge->yi = next_sample_y (y0);
     edge->bottom = next_sample_y (y1);
     edge->e =
 	(sample_to_pos (edge->xi) - x0) * dy -
-	(sample_to_pos (edge->yi) - y0) * dx;
+	(sample_to_pos (yi) - y0) * dx;
     edge->delta_e_big_x = BIG_STEP_X * dy;
     edge->delta_e_small_x = SMALL_STEP_X * dy;
     edge->delta_e_big_y = BIG_STEP_Y * dx;
@@ -100,7 +138,7 @@ edge_init (edge_t *edge, double x0, double y0, double x1, double y1)
 }
 
 static void
-edge_step (edge_t *edge, test_data_t *testdata, int i)
+edge_step (edge_t *edge, test_data_t *testdata, int i, int *yi)
 {
     if (edge->delta_e_small_y >= 0)
     {
@@ -145,44 +183,46 @@ edge_step (edge_t *edge, test_data_t *testdata, int i)
     }
 
     if (testdata->points[i++] != sample_to_pos (edge->xi)		||
-	testdata->points[i++] != sample_to_pos (edge->yi))
+	testdata->points[i++] != sample_to_pos (*yi))
     {
 	printf ("%d error %f %f\n", i, testdata->points[i - 1],
 		sample_to_pos (edge->xi));
 	exit (-1);
     }
 
-    if ((edge->yi & 0xff) == (N_GRID_Y - 1))
+    if (((*yi) & 0xff) == (N_GRID_Y - 1))
     {
 	edge->e -= edge->delta_e_big_y;
-	edge->yi += (1 << 8);
-	edge->yi &= 0xffffff00;
+	(*yi) += (1 << 8);
+	(*yi) &= 0xffffff00;
     }
     else
     {
 	edge->e -= edge->delta_e_small_y;
-	edge->yi++;
+	(*yi)++;
     }
 }
 
 static void
 dda (test_data_t *testdata)
 {
-    double x0 = testdata->segment.x0;
-    double y0 = testdata->segment.y0;
-    double x1 = testdata->segment.x1;
-    double y1 = testdata->segment.y1;
+    fixed_t x0 = testdata->segment.x0;
+    fixed_t y0 = testdata->segment.y0;
+    fixed_t x1 = testdata->segment.x1;
+    fixed_t y1 = testdata->segment.y1;
 #if 0
     printf ("= = = = %f %f %f %f = = = = \n", x0, y0, x1, y1);
 #endif
     edge_t edge;
     int i = 0;
+    int yi;
 
     edge_init (&edge, x0, y0, x1, y1);
 
-    while (edge.yi < edge.bottom)
+    yi = next_sample_y (y0);
+    while (yi < edge.bottom)
     {
-	edge_step (&edge, testdata, i);
+	edge_step (&edge, testdata, i, &yi);
 
 	i += 2;
     }