aboutsummaryrefslogtreecommitdiffstats
path: root/libtracebitmap_trace.c
diff options
context:
space:
mode:
Diffstat (limited to 'libtracebitmap_trace.c')
-rw-r--r--libtracebitmap_trace.c192
1 files changed, 192 insertions, 0 deletions
diff --git a/libtracebitmap_trace.c b/libtracebitmap_trace.c
new file mode 100644
index 0000000..090c55a
--- /dev/null
+++ b/libtracebitmap_trace.c
@@ -0,0 +1,192 @@
+/* See LICENSE file for copyright and license details. */
+#include "libtracebitmap.h"
+
+#include <stdlib.h>
+#include <unistd.h>
+
+
+#define CLEARED 0
+#define SET 1
+#define NEGATIVE 2
+#define STATUS_MASK 0x03
+
+#define TOP 0x10
+#define RIGHT 0x20
+#define BOTTOM 0x40
+#define LEFT 0x80
+#define EDGE_MASK 0xF0
+
+#define INDEX(Y, X) ((size_t)(Y) * bitmap->width + (size_t)(X))
+
+
+static uint8_t
+read_pixel(struct libtracebitmap_bitmap *bitmap, ssize_t y, ssize_t x)
+{
+ if (y < 0 || x < 0 || (size_t)y >= bitmap->height || (size_t)x >= bitmap->width)
+ return 0;
+ return bitmap->image[INDEX(y, x)];
+}
+
+
+static int
+test_pixel(struct libtracebitmap_bitmap *bitmap, ssize_t y, ssize_t x, uint8_t status)
+{
+ return (read_pixel(bitmap, y, x) & STATUS_MASK) == status;
+}
+
+
+static int
+find_component(size_t *yp, size_t *xp, int *negativep, struct libtracebitmap_bitmap *bitmap)
+{
+ size_t y, x;
+ uint8_t status;
+ for (y = 0; y < bitmap->height; y++) {
+ for (x = 0; x < bitmap->width; x++) {
+ status = (bitmap->image[INDEX(y, x)] & STATUS_MASK);
+ if (status != CLEARED) {
+ *yp = y;
+ *xp = x;
+ *negativep = (status == NEGATIVE);
+ return 1;
+ }
+ }
+ }
+ return 0;
+}
+
+
+static int
+trace_edges(struct libtracebitmap_bitmap *bitmap, size_t tl_y, size_t tl_x, int negative,
+ int (*new_stop)(size_t y, size_t x, void *user_data), void *user_data)
+{
+ uint8_t c = (negative ? NEGATIVE : SET);
+ uint8_t edge = TOP;
+ ssize_t y = (ssize_t)tl_y;
+ ssize_t x = (ssize_t)tl_x;
+ int r;
+ if ((r = new_stop((size_t)y, (size_t)x, user_data)))
+ return r;
+ do {
+ bitmap->image[INDEX(y, x)] |= edge;
+ switch (edge) {
+ case TOP:
+ if (test_pixel(bitmap, y - 1, x + 1, c)) {
+ if ((r = new_stop((size_t)y, (size_t)x + 1, user_data)))
+ return r;
+ x += 1;
+ y -= 1;
+ edge = LEFT;
+ } else if (test_pixel(bitmap, y, x + 1, c)) {
+ x += 1;
+ } else {
+ if ((r = new_stop((size_t)y, (size_t)x + 1, user_data)))
+ return r;
+ edge = RIGHT;
+ }
+ break;
+ case RIGHT:
+ if (test_pixel(bitmap, y + 1, x + 1, c)) {
+ if ((r = new_stop((size_t)y + 1, (size_t)x + 1, user_data)))
+ return r;
+ x += 1;
+ y += 1;
+ edge = TOP;
+ } else if (test_pixel(bitmap, y + 1, x, c)) {
+ y += 1;
+ } else {
+ if ((r = new_stop((size_t)y + 1, (size_t)x + 1, user_data)))
+ return r;
+ edge = BOTTOM;
+ }
+ break;
+ case BOTTOM:
+ if (test_pixel(bitmap, y + 1, x - 1, c)) {
+ if ((r = new_stop((size_t)y + 1, (size_t)x, user_data)))
+ return r;
+ x -= 1;
+ y += 1;
+ edge = RIGHT;
+ } else if (test_pixel(bitmap, y, x - 1, c)) {
+ x -= 1;
+ } else {
+ if ((r = new_stop((size_t)y + 1, (size_t)x, user_data)))
+ return r;
+ edge = LEFT;
+ }
+ break;
+ case LEFT:
+ if (test_pixel(bitmap, y - 1, x - 1, c)) {
+ if ((r = new_stop((size_t)y, (size_t)x, user_data)))
+ return r;
+ x -= 1;
+ y -= 1;
+ edge = BOTTOM;
+ } else if (test_pixel(bitmap, y - 1, x, c)) {
+ y -= 1;
+ } else {
+ if ((r = new_stop((size_t)y, (size_t)x, user_data)))
+ return r;
+ edge = TOP;
+ }
+ break;
+ default:
+ abort();
+ }
+ } while (y != (ssize_t)tl_y || x != (ssize_t)tl_x || edge != TOP);
+ return 0;
+}
+
+
+static void
+erase_traced_component(struct libtracebitmap_bitmap *bitmap, int negative)
+{
+ size_t y, x;
+ int inside;
+ uint8_t c;
+ for (y = 0; y < bitmap->height; y++) {
+ inside = 0;
+ for (x = 0; x < bitmap->width; x++) {
+ c = bitmap->image[INDEX(y, x)];
+ bitmap->image[INDEX(y, x)] &= (uint8_t)~EDGE_MASK;
+ if (c & LEFT)
+ inside = 1;
+ if (inside) {
+ bitmap->image[INDEX(y, x)] &= (uint8_t)~STATUS_MASK;
+ if ((c & STATUS_MASK) != CLEARED)
+ bitmap->image[INDEX(y, x)] |= CLEARED;
+ else if (negative)
+ bitmap->image[INDEX(y, x)] |= SET;
+ else
+ bitmap->image[INDEX(y, x)] |= NEGATIVE;
+ }
+ if (c & RIGHT)
+ inside = 0;
+ }
+ }
+}
+
+
+int
+libtracebitmap_trace(
+ struct libtracebitmap_bitmap *bitmap,
+ int (*new_component)(int negative, void *user_data),
+ int (*new_stop)(size_t y, size_t x, void *user_data),
+ int (*component_finished)(void *user_data),
+ void *user_data)
+{
+ size_t y, x;
+ int negative;
+ int r;
+ for (;;) {
+ if (!find_component(&y, &x, &negative, bitmap))
+ return 0;
+ if ((r = new_component(negative, user_data)))
+ return r;
+ if ((r = trace_edges(bitmap, y, x, negative, new_stop, user_data)))
+ return r;
+ if ((r = component_finished(user_data)))
+ return r;
+ erase_traced_component(bitmap, negative);
+ }
+ return 0;
+}