First commit

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

10 files changed, 536 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..9e13a6f
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,15 @@
+*\#*
+*~
+*.o
+*.a
+*.lo
+*.su
+*.so
+*.so.*
+*.dll
+*.dylib
+*.gch
+*.gcov
+*.gcno
+*.gcda
+/demo
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..c44b2d9
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,15 @@
+ISC License
+
+© 2021 Mattias Andrée <maandree@kth.se>
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted, provided that the above
+copyright notice and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..5390abd
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,71 @@
+.POSIX:
+
+CONFIGFILE = config.mk
+include $(CONFIGFILE)
+
+OS = linux
+# Linux:   linux
+# Mac OS:  macos
+# Windows: windows
+include mk/$(OS).mk
+
+
+LIB_MAJOR = 1
+LIB_MINOR = 0
+LIB_VERSION = $(LIB_MAJOR).$(LIB_MINOR)
+LIB_NAME = tracebitmap
+
+
+OBJ =\
+	libtracebitmap_trace.o
+
+HDR =\
+	libtracebitmap.h
+
+LOBJ = $(OBJ:.o=.lo)
+
+
+all: libtracebitmap.a libtracebitmap.$(LIBEXT) demo
+$(OBJ): $(HDR)
+$(LOBJ): $(HDR)
+
+.c.o:
+	$(CC) -c -o $@ $< $(CFLAGS) $(CPPFLAGS)
+
+.c.lo:
+	$(CC) -fPIC -c -o $@ $< $(CFLAGS) $(CPPFLAGS)
+
+demo: demo.o libtracebitmap.a
+	$(CC) -o $@ demo.o libtracebitmap.a $(CFLAGS) $(CPPFLAGS)
+
+libtracebitmap.a: $(OBJ)
+	@rm -f -- $@
+	$(AR) rc $@ $(OBJ)
+
+libtracebitmap.$(LIBEXT): $(LOBJ)
+	$(CC) $(LIBFLAGS) -o $@ $(LOBJ) $(LDFLAGS)
+
+install: libtracebitmap.a libtracebitmap.$(LIBEXT)
+	mkdir -p -- "$(DESTDIR)$(PREFIX)/lib"
+	mkdir -p -- "$(DESTDIR)$(PREFIX)/include"
+	cp -- libtracebitmap.a "$(DESTDIR)$(PREFIX)/lib/"
+	cp -- libtracebitmap.$(LIBEXT) "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.$(LIBMINOREXT)"
+	ln -sf -- libtracebitmap.$(LIBMINOREXT) "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.$(LIBMAJOREXT)"
+	ln -sf -- libtracebitmap.$(LIBMAJOREXT) "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.$(LIBEXT)"
+	cp -- libtracebitmap.h "$(DESTDIR)$(PREFIX)/include/"
+
+uninstall:
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.a"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.$(LIBMAJOREXT)"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.$(LIBMINOREXT)"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/lib/libtracebitmap.$(LIBEXT)"
+	-rm -f -- "$(DESTDIR)$(PREFIX)/include/libtracebitmap.h"
+
+clean:
+	-rm -f -- *.o *.a *.lo *.su *.so *.so.* *.dll *.dylib
+	-rm -f -- *.gch *.gcov *.gcno *.gcda *.$(LIBEXT) demo
+
+.SUFFIXES:
+.SUFFIXES: .lo .o .c
+
+.PHONY: all install uninstall clean
diff --git a/config.mk b/config.mk
new file mode 100644
index 0000000..f262b1e
--- /dev/null
+++ b/config.mk
@@ -0,0 +1,8 @@
+PREFIX    = /usr
+MANPREFIX = $(PREFIX)/share/man
+
+CC = cc
+
+CPPFLAGS = -D_DEFAULT_SOURCE -D_BSD_SOURCE -D_XOPEN_SOURCE=700 -D_GNU_SOURCE
+CFLAGS   = -std=c99 -Wall -O2
+LDFLAGS  = -s
diff --git a/demo.c b/demo.c
new file mode 100644
index 0000000..168c9e4
--- /dev/null
+++ b/demo.c
@@ -0,0 +1,198 @@
+/* See LICENSE file for copyright and license details. */
+#include "libtracebitmap.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#define MIN(A, B) ((A) < (B) ? (A) : (B))
+#define MAX(A, B) ((A) > (B) ? (A) : (B))
+
+
+struct data {
+	size_t height;
+	size_t width;
+	size_t y;
+	size_t x;
+	int beginning;
+	const char ***plot;
+};
+
+
+static int
+new_component(int negative, void *user_data)
+{
+	struct data *data = user_data;
+	data->beginning = 1;
+	printf("%s", negative ? "-" : "+");
+	fflush(stdout);
+	return 0;
+}
+
+static const char *
+mix(const char *a, const char *b)
+{
+	static const struct {
+		const char *text;
+		uint16_t bits;
+	} symbols[] = {
+		{" ", 0x0000}, {"┼", 0x1111},
+		{"╵", 0x1000}, {"┬", 0x0111},
+		{"╶", 0x0100}, {"┤", 0x1011},
+		{"╷", 0x0010}, {"┴", 0x1101},
+		{"╴", 0x0001}, {"├", 0x1110},
+		{"│", 0x1010}, {"─", 0x0101},
+		{"└", 0x1100}, {"┐", 0x0011},
+		{"┘", 0x1001}, {"┌", 0x0110}
+	};
+	uint16_t bits;
+	size_t i, j;
+	for (i = 0; strcmp(a, symbols[i].text); i++);
+	for (j = 0; strcmp(b, symbols[j].text); j++);
+	bits = symbols[i].bits | symbols[j].bits;
+	for (i = 0; bits != symbols[i].bits; i++);
+	return symbols[i].text;
+}
+
+static int
+new_stop(size_t y, size_t x, void *user_data)
+{
+	struct data *data = user_data;
+	size_t y0, y1, y2;
+	size_t x0, x1, x2;
+	printf(" (%zu,%zu)", y, x);
+	fflush(stdout);
+	if (data->beginning) {
+		data->beginning = 0;
+		data->y = y;
+		data->x = x;
+	} else {
+		y0 = MIN(data->y, y);
+		x0 = MIN(data->x, x);
+		y2 = MAX(data->y, y);
+		x2 = MAX(data->x, x);
+		if (y0 == y2) {
+			y1 = y0;
+			for (x1 = x0; x1 < x2; x1++) {
+				data->plot[y1 * 2][x1 * 2 + 0] = mix(data->plot[y1 * 2][x1 * 2 + 0], "╶");
+				data->plot[y1 * 2][x1 * 2 + 1] = mix(data->plot[y1 * 2][x1 * 2 + 1], "─");
+				data->plot[y1 * 2][x1 * 2 + 2] = mix(data->plot[y1 * 2][x1 * 2 + 2], "╴");
+			}
+		} else {
+			x1 = x0;
+			for (y1 = y0; y1 < y2; y1++) {
+				data->plot[y1 * 2 + 0][x1 * 2] = mix(data->plot[y1 * 2 + 0][x1 * 2], "╷");
+				data->plot[y1 * 2 + 1][x1 * 2] = mix(data->plot[y1 * 2 + 1][x1 * 2], "│");
+				data->plot[y1 * 2 + 2][x1 * 2] = mix(data->plot[y1 * 2 + 2][x1 * 2], "╵");
+			}
+		}
+		data->y = y;
+		data->x = x;
+	}
+	return 0;
+}
+
+
+static int
+component_finished(void *user_data)
+{
+	(void) user_data;
+	printf("\n");
+	fflush(stdout);
+	return 0;
+}
+
+
+int
+main(void)
+{
+	struct libtracebitmap_bitmap bitmap;
+	size_t size = 0;
+	size_t len = 0;
+	ssize_t rd;
+	size_t width, i, j;
+	size_t y, x;
+	int r;
+	const char ***plot;
+	struct data data;
+
+	bitmap.image = NULL;
+	for (;;) {
+		if (len == size) {
+			size += 1024;
+			bitmap.image = realloc(bitmap.image, size);
+			if (!bitmap.image) {
+				perror("realloc");
+				exit(1);
+			}
+		}
+		rd = read(STDIN_FILENO, &bitmap.image[len], size - len);
+		if (rd <= 0) {
+			if (!rd)
+				break;
+			perror("read");
+			exit(1);
+		}
+		len += (size_t)rd;
+	}
+
+	bitmap.height = 0;
+	bitmap.width = 0;
+	width = 0;
+	for (i = j = 0; j < len; j++) {
+		if ((char)bitmap.image[j] == '\n') {
+			if (!bitmap.height++) {
+				bitmap.width = width;
+			} else {
+				if (bitmap.width != width) {
+					fprintf(stderr, "Invalid input: each line must have the same length.\n");
+					exit(1);
+				}
+			}
+			width = 0;
+		} else if ((char)bitmap.image[j] == '.') {
+			bitmap.image[i++] = LIBTRACEBITMAP_INK_OFF;
+			width += 1;
+		} else if ((char)bitmap.image[j] == 'x') {
+			bitmap.image[i++] = LIBTRACEBITMAP_INK_ON;
+			width += 1;
+		} else {
+			fprintf(stderr, "Invalid input: may only contain '.', 'x', and <newline> characters.\n");
+			exit(1);
+		}
+	}
+	if (width) {
+		fprintf(stderr, "Invalid input: must end with <newline> character.\n");
+		exit(1);
+	}
+
+	plot = calloc(bitmap.height * 2 + 1, sizeof(*plot));
+	for (y = 0; y < bitmap.height * 2 + 1; y++) {
+		plot[y] = calloc(bitmap.width * 2 + 1, sizeof(**plot));
+		for (x = 0; x < bitmap.width * 2 + 1; x++)
+			plot[y][x] = " ";
+	}
+	for (y = 0, i = 0; y < bitmap.height; y++)
+		for (x = 0; x < bitmap.width; x++, i++)
+			plot[y * 2 + 1][x * 2 + 1] = (bitmap.image[i] == LIBTRACEBITMAP_INK_ON ? "x" : ".");
+
+	data.height = bitmap.height;
+	data.width  = bitmap.width;
+	data.plot   = plot;
+
+	r = libtracebitmap_trace(&bitmap, new_component, new_stop, component_finished, &data);
+	if (r)
+		exit(r);
+
+	for (y = 0; y < bitmap.height * 2 + 1; y++) {
+		for (x = 0; x < bitmap.width * 2 + 1; x++)
+			printf("%s", plot[y][x]);
+		printf("\n");
+		free(plot[y]);
+	}
+
+	free(plot);
+	free(bitmap.image);
+	return 0;
+}
diff --git a/libtracebitmap.h b/libtracebitmap.h
new file mode 100644
index 0000000..1f8b13e
--- /dev/null
+++ b/libtracebitmap.h
@@ -0,0 +1,25 @@
+/* See LICENSE file for copyright and license details. */
+#ifndef LIBTRACEBITMAP_H
+#define LIBTRACEBITMAP_H
+
+#include <stddef.h>
+#include <stdint.h>
+
+#define LIBTRACEBITMAP_INK_OFF 0
+#define LIBTRACEBITMAP_INK_ON  1
+/* Other values in (struct libtracebitmap_bitmap).image invoke undefined behaviour */
+
+struct libtracebitmap_bitmap {
+	size_t height;
+	size_t width;
+	uint8_t *image; /* (uint8_t [.height][.width]) */
+};
+
+int libtracebitmap_trace(
+	struct libtracebitmap_bitmap *bitmap, /* image will be erased, but not deallocated */
+	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);
+
+#endif
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;
+}
diff --git a/mk/linux.mk b/mk/linux.mk
new file mode 100644
index 0000000..d016d31
--- /dev/null
+++ b/mk/linux.mk
@@ -0,0 +1,4 @@
+LIBEXT      = so
+LIBFLAGS    = -shared -Wl,-soname,lib$(LIB_NAME).$(LIBEXT).$(LIB_MAJOR)
+LIBMAJOREXT = $(LIBEXT).$(LIB_MAJOR)
+LIBMINOREXT = $(LIBEXT).$(LIB_VERSION)
diff --git a/mk/macos.mk b/mk/macos.mk
new file mode 100644
index 0000000..bd92de6
--- /dev/null
+++ b/mk/macos.mk
@@ -0,0 +1,4 @@
+LIBEXT      = dylib
+LIBFLAGS    = -dynamiclib
+LIBMAJOREXT = $(LIB_MAJOR).$(LIBEXT)
+LIBMINOREXT = $(LIB_VERSION).$(LIBEXT)
diff --git a/mk/windows.mk b/mk/windows.mk
new file mode 100644
index 0000000..e9602e1
--- /dev/null
+++ b/mk/windows.mk
@@ -0,0 +1,4 @@
+LIBEXT      = dll
+LIBFLAGS    = -mdll
+LIBMAJOREXT = $(LIB_MAJOR).$(LIBEXT)
+LIBMINOREXT = $(LIB_VERSION).$(LIBEXT)