Explore some potential optimizations for fp line drawing

2 files changed, 146 insertions, 16 deletions

diff --git a/src/main.c b/src/main.c
index 1982992..78ee1b2 100644
--- a/src/main.c
+++ b/src/main.c
@@ -101,12 +101,12 @@ test_icn(void) {
 
 void
 test_lines(void) {
-    for (size_t i = 0; i < 20; i++) {
+    for (size_t i = 0; i < 10; i++) {
         draw_line(0, i * 8, (30 * 8 - 1), ((20 - i) * 8 - 1), 5);
     }
-    for (size_t i = 0; i < 30; i++) {
-        draw_line(i * 8, (20 * 8 - 1), ((30 - i) * 8 - 1), 0, 5);
-    }
+    // for (size_t i = 0; i < 30; i++) {
+    //     draw_line(i * 8, (20 * 8 - 1), ((30 - i) * 8 - 1), 0, 5);
+    // }
 }
 
 int main(void) {
@@ -136,11 +136,20 @@ int main(void) {
         // // draw_line(100, 0, 0, 100, 2);
         // // draw_line(50,  0, 0, 100, 3);
         // draw_line(0, 0, 50, 159, 1);
+
         // draw_line(0, 0, 50, 159, 1);
-        // draw_line(1, 1, 50, 159, 2);
-        // draw_line(2, 2, 50, 159, 1);
-        // draw_line(3, 3, 50, 159, 2);
-        // draw_line(4, 4, 50, 159, 1);
+        // draw_line(0, 0, 60, 159, 1);
+        // draw_line(8, 0, 50, 159, 2);
+        // draw_line(8, 0, 60, 159, 2);
+        // draw_line(50, 159,0, 0,  1);
+        // draw_line(60, 159,0, 0,  1);
+        // draw_line(50, 159,8, 0,  2);
+        // draw_line(60, 159,8, 0,  2);
+        // draw_line(0, 0, 100, 50,  1);
+        // draw_line(10, 0, 100, 50, 1);
+        // draw_line(100, 50,0,  0,  2);
+        // draw_line(100, 50,10, 0, 2);
+
         // draw_line(5, 5, 50, 159, 2);
         // draw_line(50, 159, 0, 0, 1);
         // txt_render();
@@ -150,10 +159,11 @@ int main(void) {
             // txt_render();
             // txt_clear();
         PROF(test_lines(), test_lines_cycles);
-        PROF(test_rect(), test_rect_cycles);
-        PROF(test_fill_rect(), test_fill_rect_cycles);
-        PROF(test_chr(), test_chr_cycles);
-        PROF(test_icn(), test_icn_cycles);
+        draw_filled_rect(0, 0, 150, 60, 0);
+        // PROF(test_rect(), test_rect_cycles);
+        // PROF(test_fill_rect(), test_fill_rect_cycles);
+        // PROF(test_chr(), test_chr_cycles);
+        // PROF(test_icn(), test_icn_cycles);
         PROF_SHOW();
         PROF(flip_buffer(), flip_cycles);
     }
diff --git a/src/renderer_m4.c b/src/renderer_m4.c
index a849cfe..e564c1e 100644
--- a/src/renderer_m4.c
+++ b/src/renderer_m4.c
@@ -32,8 +32,11 @@ static bool screen_updated = true;
 #define BOUNDCHECK_SCREEN(X,Y) if ((X) >= SCREEN_WIDTH || (Y) >= SCREEN_HEIGHT) return;
 #endif
 
-// Make sure
-#define MAYBE_SWAP(A,B) if ((A) > (B)) { size_t tmp = (A); (A) = (B); (B) = tmp; }
+// Swap A and B values without a tmp variable.
+#define SWAP(A, B) (((A) ^= (B)), ((B) ^= (A)), ((A) ^= (B)))
+
+// Swap A and B values to make sure A <= B.
+#define MAYBE_SWAP(A,B) if ((A) > (B)) { SWAP(A,B); }
 
 IWRAM_CODE
 void screen_fill(u8 clr)  {
@@ -131,9 +134,8 @@ draw_vline(size_t x0, size_t y0, size_t y1, u8 clr) {
     }
 }
 
-#define SWAP(A,B) do {size_t tmp = (A); (A) = (B); (B) = (tmp);} while(0)
-
 IWRAM_CODE
+UNROLL_LOOPS
 void
 draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
     BOUNDCHECK_SCREEN(x0, y0);
@@ -146,6 +148,123 @@ draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
         MAYBE_SWAP(y0, y1);
         draw_vline(x0, y0, y1, clr);
     } else {
+        // int     dx = x0 > x1 ?       x0 - x1 : x1 - x0;
+        // int     dy = y0 > y1 ?       y0 - y1 : y1 - y0;
+        //
+        // NOTE: Simplified bresenham.
+        // int dx=x1-x0;
+        // int dy=y1-y0;
+        // int d=2*dy-dx;
+        // int e=2*dy;
+        // int ne=2*(dy-dx);
+        // int x=x0;
+        // int y=y0;
+        // for (x=x0;x<=x1;x++) {
+        //     draw_pixel(x, y, clr);
+        //     if (d<=0) {
+        //         d+=e;
+        //     } else {
+        //         d+=ne;
+        //         y++; // sign?
+        //     }
+        // }
+        // NOTE: Simplified fp-line.
+        // s32 f;
+        // int x;
+        // s32 m = ((s32)(y1-y0)<<16)/(x1-x0);
+
+        // f=y0<<16;
+        // for (x=x0;x<=x1;x++,f += m) {
+        //     s32 g = f;
+        //     g += 32767;
+        //     draw_pixel(x, g >> 16, clr);
+        // }
+
+        // u16 *dst = NULL;
+        // uintptr_t addr = ((uintptr_t)backbuf + y0 * SCREEN_WIDTH + x0);
+        // u32 mask = x0 & 1 ? ~0xFF : 0xFF;
+        // u32 color = (clr & 0xFF) | ((clr & 0xFF) << 8);
+#if 0
+        int     dx = x0 > x1 ?       x0 - x1 : x1 - x0;
+        int     dy = y0 > y1 ?       y0 - y1 : y1 - y0;
+
+        u16 *dst = NULL;
+        uintptr_t addr = ((uintptr_t)backbuf + y0 * SCREEN_WIDTH + x0);
+        u32 mask = x0 & 1 ? ~0xFF : 0xFF;
+        u32 color = (clr & 0xFF) | ((clr & 0xFF) << 8);
+
+        if (dx >= dy) {
+            int fp_val = y1 - y0;
+            int fp_div = x1 - x0;
+            int fp_inc = (fp_val << 8) / fp_div;
+            int fp_step = fp_div > 0 ? fp_inc : -fp_inc;
+            int i_step  = fp_div > 0 ? 1 : -1;
+            int y_step = 0;
+            for (int i = 0; i <= dx; i++) {
+                dst = (u16 *)(addr - (mask >> 31));
+                *dst = (*dst & ~mask) | (color & mask);
+                addr += i_step;
+                y_step += fp_step;
+                if (y_step >> 8) {
+                    addr += SCREEN_WIDTH * (y_step >> 8);
+                    y_step -= (y_step >> 8) << 8;
+                }
+                // TODO: +/- inc?
+                // addr += SCREEN_WIDTH * (y_step >> 8);
+                // y_step -= (y_step >> 8) << 8;
+                mask = ~mask;
+            }
+        } else {
+            // int fp_val = x1 - x0;
+            // int fp_div = y1 - y0;
+            // int fp_inc = (fp_val << 8) / fp_div;
+            // int fp_step = fp_div > 0 ? fp_inc : -fp_inc;
+            // int x_step = 0;
+            // u32 masks[] = { ~0xFF, 0xFF, };
+            // u32 colors[] = { color & ~0xFF, color & 0xFF, };
+            // for (int i = 0; i <= dy; i++) {
+            //     // TODO: +/- inc?
+            //     // METHOD 1: Conditional
+            //     // dst = (u16 *)(addr - (mask >> 31));
+            //     // *dst = (*dst & ~mask) | (color & mask);
+            //     // addr -= SCREEN_WIDTH;
+            //     // x_step += fp_step;
+            //     // if (x_step >> 8) {
+            //     //     addr += (x_step >> 8);
+            //     //     x_step -= (x_step >> 8) << 8;
+            //     //     mask = ~mask;
+            //     // }
+
+            //     // METHOD 1-2
+            //     dst = (u16 *)(addr - (masks[(x_step >> 8)] >> 31));
+            //     *dst = (*dst & ~masks[(x_step >> 8)]) | colors[(x_step>>8)];
+            //     addr -= SCREEN_WIDTH;
+            //     x_step += fp_step;
+            //     if (x_step >> 8) {
+            //         addr += (x_step >> 8);
+            //         x_step -= (x_step >> 8) << 8;
+            //     }
+
+            //     // METHOD 2: branchless lut
+            //     // dst = (u16 *)(addr - (masks[(x_step >> 8)] >> 31));
+            //     // *dst = (*dst & ~masks[(x_step >> 8)]) | colors[(x_step>>8)];
+            //     // x_step += fp_step;
+            //     // addr += (x_step >> 8);
+            //     // addr -= SCREEN_WIDTH;
+            //     // x_step -= (x_step >> 8) << 8;
+
+            //     // METHOD 3: branchless bit hacking
+            //     // dst = (u16 *)(addr - (mask >> 31));
+            //     // *dst = (*dst & ~mask) | (color & mask);
+            //     // x_step += fp_step;
+            //     // mask ^= ((x_step >> 8) | -(x_step >> 8));
+            //     // addr += (x_step >> 8);
+            //     // addr -= SCREEN_WIDTH;
+            //     // x_step -= (x_step >> 8) << 8;
+            // }
+        }
+
+#elif 1
         // Diagonal line.
         int     dx = x0 > x1 ?       x0 - x1 : x1 - x0;
         int     dy = y0 > y1 ?       y0 - y1 : y1 - y0;
@@ -183,6 +302,7 @@ draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
                 addr += y_step;
             }
         }
+#endif
     }
     screen_updated = true;
 }