First commit

Signed-off-by: Mattias Andrée <maandree@kth.se>

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;
+}