Speed up line drawing algorithm

2 files changed, 58 insertions, 0 deletions

diff --git a/src/main.c b/src/main.c
index 96682f9..d81a26a 100644
--- a/src/main.c
+++ b/src/main.c
@@ -128,6 +128,19 @@ int main(void) {
         bios_vblank_wait();
 
         PROF(test_clear(), test_clear_cycles);
+        // draw_line(0, 0, 100, 50, 1);
+        // // draw_line(0, 0, 100, 100, 2);
+        // // draw_line(0, 0, 50, 100, 3);
+        // // draw_line(5, 0, 0, 5, 2);
+        // draw_line(100, 0, 0, 50, 1);
+        // // draw_line(100, 0, 0, 100, 2);
+        // // draw_line(50,  0, 0, 100, 3);
+        // txt_render();
+        // txt_clear();
+            // txt_printf("dx: %d\n", dx);
+            // txt_printf("dy: %d\n", dy);
+            // txt_render();
+            // txt_clear();
         PROF(test_lines(), test_lines_cycles);
         PROF(test_rect(), test_rect_cycles);
         PROF(test_fill_rect(), test_fill_rect_cycles);
diff --git a/src/renderer_m4.c b/src/renderer_m4.c
index cbf3c3f..c950763 100644
--- a/src/renderer_m4.c
+++ b/src/renderer_m4.c
@@ -131,6 +131,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
 void
 draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
@@ -144,7 +146,49 @@ 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 {
+#if 1
         // Diagonal line.
+        if (x0 > x1) {
+            SWAP(x0, x1);
+            SWAP(y0, y1);
+        }
+        int dx = x1 - x0;
+        int dy = y0 > y1 ? y0 - y1 : y1 - y0;
+        int x_step = 1;
+        int y_step = y0 > y1 ? -1 : 1;
+        y_step *= SCREEN_WIDTH / 2;
+
+        // Mini-LUT for M4 byte decoding.
+        u16 mask[]   = { ~0xFF,         0xFF };
+        u16 color[]  = {   clr,   (clr << 8) };
+        u8 advance[] = {     0,       x_step };
+        u16 *dst = &backbuf[(x0 + y0 * SCREEN_WIDTH) / 2];
+        if (dx >= dy) {
+            int diff = 2 * dy - dx;
+            for (int i = dx; i >= 0; i--) {
+                *dst = (*dst & mask[x0 & 1]) | color[x0 & 1];
+                if (diff >= 0) {
+                    diff -= 2 * dx;
+                    dst = dst + y_step;
+                }
+                diff += 2 * dy;
+                dst = dst + advance[x0 & 1];
+                x0 += x_step;
+            }
+        } else {
+            int diff = 2 * dx - dy;
+            for (int i = dy; i >= 0; i--) {
+                *dst = (*dst & mask[x0 & 1]) | color[x0 & 1];
+                if (diff >= 0) {
+                    diff -= 2 * dy;
+                    dst = dst + advance[x0 & 1];
+                    x0 += x_step;
+                }
+                diff += 2 * dx;
+                dst = dst + y_step;
+            }
+        }
+#else
         int dx = x0 > x1 ? x0 - x1 : x1 - x0;
         int dy = y0 > y1 ? y1 - y0 : y0 - y1;
         int x_step = x0 < x1 ? 1 : -1;
@@ -162,6 +206,7 @@ draw_line(size_t x0, size_t y0, size_t x1, size_t y1, u8 clr) {
                 y0 += y_step;
             }
         }
+#endif
     }
     screen_updated = true;
 }