diff options
| -rw-r--r-- | .gitignore | 15 | ||||
| -rw-r--r-- | LICENSE | 15 | ||||
| -rw-r--r-- | Makefile | 71 | ||||
| -rw-r--r-- | config.mk | 8 | ||||
| -rw-r--r-- | demo.c | 198 | ||||
| -rw-r--r-- | libtracebitmap.h | 25 | ||||
| -rw-r--r-- | libtracebitmap_trace.c | 192 | ||||
| -rw-r--r-- | mk/linux.mk | 4 | ||||
| -rw-r--r-- | mk/macos.mk | 4 | ||||
| -rw-r--r-- | mk/windows.mk | 4 |
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 @@ -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 @@ -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) |