Rework the pixel computation to use areas

This changes the displayio pixel computation from per-pixel to
per-area. This is precursor work to updating portions of the screen
(#1169). It should provide mild speedups because bounds checks are
done once per area rather than once per pixel. Filling by area also
allows TileGrid to maintain a row-associative fill pattern even when
the display's refresh is orthogonal to it.

1 files changed, 145 insertions, 80 deletions

diff --git a/shared-module/displayio/__init__.c b/shared-module/displayio/__init__.c
index 156640440..e816fefda 100644
--- a/shared-module/displayio/__init__.c
+++ b/shared-module/displayio/__init__.c
@@ -10,6 +10,7 @@
 #include "shared-bindings/displayio/Display.h"
 #include "shared-bindings/displayio/Group.h"
 #include "shared-bindings/displayio/Palette.h"
+#include "shared-module/displayio/area.h"
 #include "supervisor/shared/autoreload.h"
 #include "supervisor/shared/display.h"
 #include "supervisor/memory.h"
@@ -17,8 +18,8 @@
 
 primary_display_t displays[CIRCUITPY_DISPLAY_LIMIT];
 
-static inline void swap(uint16_t* a, uint16_t* b) {
-    uint16_t temp = *a;
+static inline void swap(int16_t* a, int16_t* b) {
+    int16_t temp = *a;
     *a = *b;
     *b = temp;
 }
@@ -56,102 +57,112 @@ void displayio_refresh_displays(void) {
             continue;
         }
         if (displayio_display_refresh_queued(display)) {
-            // We compute the pixels. r and c are row and column to match the display memory
-            // structure. x and y match location within the groups.
-            uint16_t c0 = 0;
-            uint16_t r0 = 0;
-            uint16_t c1 = display->width;
-            uint16_t r1 = display->height;
-            if (display->transpose_xy) {
-                swap(&c1, &r1);
-            }
-
             if (!displayio_display_begin_transaction(display)) {
                 // Can't acquire display bus; skip updating this display. Try next display.
                 continue;
             }
-            displayio_display_set_region_to_update(display, c0, r0, c1, r1);
             displayio_display_end_transaction(display);
 
-            uint16_t x0 = 0;
-            uint16_t x1 = display->width - 1;
-            uint16_t startx = 0;
-            int8_t dx = 1;
-            if (display->mirror_x) {
-                dx = -1;
-                startx = x1;
-            }
-            uint16_t y0 = 0;
-            uint16_t y1 = display->height - 1;
-            uint16_t starty = 0;
-            int8_t dy = 1;
-            if (display->mirror_y) {
-                dy = -1;
-                starty = y1;
-            }
-
-            bool transpose = false;
+            displayio_area_t whole_screen = {
+                .x1 = 0,
+                .y1 = 0,
+                .x2 = display->width - 1,
+                .y2 = display->height - 1
+            };
             if (display->transpose_xy) {
-                transpose = true;
-                int8_t temp_dx = dx;
-                dx = dy;
-                dy = temp_dx;
-
-                swap(&starty, &startx);
-                swap(&x0, &y0);
-                swap(&x1, &y1);
+                swap(&whole_screen.x2, &whole_screen.y2);
             }
 
-            size_t index = 0;
-            uint16_t buffer_size = 256;
+            uint16_t buffer_size = 512;
+
+            uint16_t subrectangles = 1;
+            uint16_t rows_per_buffer = displayio_area_height(&whole_screen);
+            if (displayio_area_size(&whole_screen) > buffer_size) {
+                rows_per_buffer = buffer_size / displayio_area_width(&whole_screen);
+                subrectangles = displayio_area_height(&whole_screen) / rows_per_buffer;
+                buffer_size = rows_per_buffer * displayio_area_width(&whole_screen);
+            }
             uint32_t buffer[buffer_size / 2];
-            bool skip_this_display = false;
-
-            for (uint16_t y = starty; y0 <= y && y <= y1; y += dy) {
-                for (uint16_t x = startx; x0 <= x && x <= x1; x += dx) {
-                    uint16_t* pixel = &(((uint16_t*)buffer)[index]);
-                    *pixel = 0;
-
-                    if (display->current_group != NULL) {
-                        if (transpose) {
-                            displayio_group_get_pixel(display->current_group, y, x, pixel);
-                        } else {
-                            displayio_group_get_pixel(display->current_group, x, y, pixel);
-                        }
-                    }
 
-                    index += 1;
-                    // The buffer is full, send it.
-                    if (index >= buffer_size) {
-                        if (!displayio_display_begin_transaction(display)) {
-                            // Can't acquire display bus; skip the rest of the data. Try next display.
-                            index = 0;
-                            skip_this_display = true;
-                            break;
+            for (uint16_t j = 0; j < subrectangles; j++) {
+                displayio_area_t subrectangle = {
+                    .x1 = 0,
+                    .y1 = rows_per_buffer * j,
+                    .x2 = displayio_area_width(&whole_screen) - 1,
+                    .y2 = rows_per_buffer * (j + 1) - 1
+                };
+
+                displayio_display_begin_transaction(display);
+                displayio_display_set_region_to_update(display, subrectangle.x1, subrectangle.y1,
+                                                                subrectangle.x2 + 1, subrectangle.y2 + 1);
+                displayio_display_end_transaction(display);
+
+                // Handle display mirroring and transpose.
+                displayio_area_t transformed_subrectangle;
+                displayio_buffer_transform_t transform;
+                if (display->mirror_x) {
+                    uint16_t width = displayio_area_width(&whole_screen);
+                    transformed_subrectangle.x1 = width - subrectangle.x2 - 1;
+                    transformed_subrectangle.x2 = width - subrectangle.x1 - 1;
+                } else {
+                    transformed_subrectangle.x1 = subrectangle.x1;
+                    transformed_subrectangle.x2 = subrectangle.x2;
+                }
+                if (display->mirror_y != display->transpose_xy) {
+                    uint16_t height = displayio_area_height(&whole_screen);
+                    transformed_subrectangle.y1 = height - subrectangle.y2 - 1;
+                    transformed_subrectangle.y2 = height - subrectangle.y1 - 1;
+                } else {
+                    transformed_subrectangle.y1 = subrectangle.y1;
+                    transformed_subrectangle.y2 = subrectangle.y2;
+                }
+                transform.width = transformed_subrectangle.x2 - transformed_subrectangle.x1 + 1;
+                transform.height = transformed_subrectangle.y2 - transformed_subrectangle.y1 + 1;
+                if (display->transpose_xy) {
+                    int16_t y1 = transformed_subrectangle.y1;
+                    int16_t y2 = transformed_subrectangle.y2;
+                    transformed_subrectangle.y1 = transformed_subrectangle.x1;
+                    transformed_subrectangle.y2 = transformed_subrectangle.x2;
+                    transformed_subrectangle.x1 = y1;
+                    transformed_subrectangle.x2 = y2;
+                }
+                transform.transpose_xy = display->transpose_xy;
+                transform.mirror_x = display->mirror_x;
+                transform.mirror_y = display->mirror_y;
+                transform.scale = 1;
+
+                uint32_t mask[(buffer_size / 32) + 1];
+                for (uint16_t k = 0; k < (buffer_size / 32) + 1; k++) {
+                    mask[k] = 0x00000000;
+                }
+                bool full_coverage = displayio_group_get_area(display->current_group, &transform, &transformed_subrectangle, mask, buffer);
+                if (!full_coverage) {
+                    uint32_t index = 0;
+                    uint32_t current_mask = 0;
+                    for (int16_t y = subrectangle.y1; y <= subrectangle.y2; y++) {
+                        for (int16_t x = subrectangle.x1; x <= subrectangle.x2; x++) {
+                            if (index % 32 == 0) {
+                                current_mask = mask[index / 32];
+                            }
+                            if ((current_mask & (1 << (index % 32))) == 0) {
+                                ((uint16_t*) buffer)[index] = 0x0000;
+                            }
+                            index++;
                         }
-                        displayio_display_send_pixels(display, buffer, buffer_size / 2);
-                        displayio_display_end_transaction(display);
-                        // TODO(tannewt): Make refresh displays faster so we don't starve other
-                        // background tasks.
-                        usb_background();
-                        index = 0;
                     }
                 }
-            }
 
-            if (skip_this_display) {
-                // Go on to next display.
-                continue;
-            }
-            // Send the remaining data.
-            if (index) {
                 if (!displayio_display_begin_transaction(display)) {
-                    // Can't get display bus. Skip the rest of the data. Try next display.
-                    continue;
+                    // Can't acquire display bus; skip the rest of the data. Try next display.
+                    break;
                 }
-                displayio_display_send_pixels(display, buffer, index * 2);
+                displayio_display_send_pixels(display, buffer, buffer_size / 2);
+                displayio_display_end_transaction(display);
+
+                // TODO(tannewt): Make refresh displays faster so we don't starve other
+                // background tasks.
+                usb_background();
             }
-            displayio_display_end_transaction(display);
         }
         displayio_display_finish_refresh(display);
     }
@@ -220,3 +231,57 @@ void reset_displays(void) {
     }
     #endif
 }
+
+void displayio_area_shift(displayio_area_t* area, int16_t dx, int16_t dy) {
+    area->x1 += dx;
+    area->y1 += dy;
+    area->x2 += dx;
+    area->y2 += dy;
+}
+
+bool displayio_area_compute_overlap(const displayio_area_t* a,
+                                    const displayio_area_t* b,
+                                    displayio_area_t* overlap) {
+    overlap->x1 = a->x1;
+    if (b->x1 > overlap->x1) {
+        overlap->x1 = b->x1;
+    }
+    overlap->x2 = a->x2;
+    if (b->x2 < overlap->x2) {
+        overlap->x2 = b->x2;
+    }
+    if (overlap->x1 > overlap->x2) {
+        return false;
+    }
+    overlap->y1 = a->y1;
+    if (b->y1 > overlap->y1) {
+        overlap->y1 = b->y1;
+    }
+    overlap->y2 = a->y2;
+    if (b->y2 < overlap->y2) {
+        overlap->y2 = b->y2;
+    }
+    if (overlap->y1 > overlap->y2) {
+        return false;
+    }
+    return true;
+}
+
+uint16_t displayio_area_width(const displayio_area_t* area) {
+    return area->x2 - area->x1 + 1;
+}
+
+uint16_t displayio_area_height(const displayio_area_t* area) {
+    return area->y2 - area->y1 + 1;
+}
+
+uint32_t displayio_area_size(const displayio_area_t* area) {
+    return displayio_area_width(area) * displayio_area_height(area);
+}
+
+bool displayio_area_equal(const displayio_area_t* a, const displayio_area_t* b) {
+    return a->x1 == b->x1 &&
+           a->y1 == b->y1 &&
+           a->x2 == b->x2 &&
+           a->y2 == b->y2;
+}