/* 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;
}
