aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMattias Andrée <maandree@kth.se>2021-11-08 20:42:43 +0100
committerMattias Andrée <maandree@kth.se>2021-11-08 20:42:43 +0100
commita27311a1e468ec0ea8205cc362dc69386675f704 (patch)
treeeaf006b7660c98025af5302b8df331fb015e2695
downloadlibtracebitmap-a27311a1e468ec0ea8205cc362dc69386675f704.tar.gz
libtracebitmap-a27311a1e468ec0ea8205cc362dc69386675f704.tar.bz2
libtracebitmap-a27311a1e468ec0ea8205cc362dc69386675f704.tar.xz
First commit
Signed-off-by: Mattias Andrée <maandree@kth.se>
-rw-r--r--.gitignore15
-rw-r--r--LICENSE15
-rw-r--r--Makefile71
-rw-r--r--config.mk8
-rw-r--r--demo.c198
-rw-r--r--libtracebitmap.h25
-rw-r--r--libtracebitmap_trace.c192
-rw-r--r--mk/linux.mk4
-rw-r--r--mk/macos.mk4
-rw-r--r--mk/windows.mk4
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)