Add initial wimmel program

5 files changed, 377 insertions, 0 deletions

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..4a6b4bf
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,28 @@
+CC = gcc
+CFLAGS = -ggdb -std=c99 -pedantic -Wall `pkg-config --cflags gtk+-2.0 glib-2.0`
+LDFLAGS = `pkg-config --libs gtk+-2.0 glib-2.0` -lm
+
+PROGS = wimmel wimmel_gl
+OBJS = wimmel.o wimmel_gl.o util.o
+
+all: $(PROGS)
+
+wimmel: wimmel.o util.o
+wimmel_gl: wimmel_gl.o
+
+.PHONY: clean all
+
+%:
+	$(CC) $(CFLAGS) $(LDFLAGS) -o $@ $+
+
+%.o: %.c %.h
+	$(CC) $(CFLAGS) -c -o $@ $<
+
+
+wimmel_gl:
+	$(CC) -lglut `pkg-config --cflags --libs gtk+-2.0 glib-2.0` -o $@ $+
+
+
+
+clean:
+	rm -f $(PROGS) $(OBJS)
diff --git a/commands b/commands
new file mode 100644
index 0000000..b18e0f9
--- /dev/null
+++ b/commands
@@ -0,0 +1,2 @@
+./wimmel Wimmel.png 385 365 55 50
+./wimmel wimmel_small.png 160 152 24 22
diff --git a/util.c b/util.c
new file mode 100644
index 0000000..03551b5
--- /dev/null
+++ b/util.c
@@ -0,0 +1,131 @@
+#include <glib.h>
+#include <gtk/gtk.h>
+
+#include "util.h"
+
+/*
+ * derived from http://www.gnu.org/software/guile-gnome/docs/gdk/html/The-GdkPixbuf-Structure.html
+ */
+guchar *pixbuf_point(GdkPixbuf *pixbuf, point_t point)
+{
+	g_assert(point.x >= 0 && point.x < gdk_pixbuf_get_width (pixbuf));
+	g_assert(point.y >= 0 && point.y < gdk_pixbuf_get_height(pixbuf));
+	g_assert(gdk_pixbuf_get_bits_per_sample(pixbuf) == 8);
+
+	return gdk_pixbuf_get_pixels(pixbuf) 
+		+ point.y * gdk_pixbuf_get_rowstride (pixbuf)
+		+ point.x * gdk_pixbuf_get_n_channels(pixbuf);
+}
+
+void put_pixel(GdkPixbuf *pixbuf, point_t point, color_t color)
+{
+	const gint n_channels = gdk_pixbuf_get_n_channels(pixbuf);
+	g_assert(n_channels == 4 || n_channels == 3);
+	g_assert(gdk_pixbuf_get_colorspace(pixbuf) == GDK_COLORSPACE_RGB);
+	g_assert(gdk_pixbuf_get_bits_per_sample(pixbuf) == 8);
+
+	guchar *p = pixbuf_point(pixbuf, point);
+
+	p[0] = color.r;
+	p[1] = color.g;
+	p[2] = color.b;
+	if (n_channels == 4)
+		p[3] = color.a;
+}
+
+color_t get_pixel(GdkPixbuf *pixbuf, point_t point)
+{
+	const gint n_channels = gdk_pixbuf_get_n_channels(pixbuf);
+	g_assert(gdk_pixbuf_get_colorspace(pixbuf) == GDK_COLORSPACE_RGB);
+	g_assert(gdk_pixbuf_get_bits_per_sample(pixbuf) == 8);
+	g_assert(n_channels == 4 || n_channels == 3);
+
+	guchar *p = pixbuf_point(pixbuf, point);
+
+	return COLOR(p[0], p[1], p[2], n_channels == 4 ? p[3] : COL_MAX);
+}
+
+void color_to_yiq(color_t color, guint8 *y, guint8 *i, guint8 *q)
+{
+	if (y)
+		*y = 0.299    * color.r + 0.587    * color.g + 0.115    * color.b;
+	if (i)
+		*i = 0.595716 * color.r - 0.274453 * color.g - 0.321263 * color.b;
+	if (q)
+		*q = 0.211456 * color.r - 0.522591 * color.g + 0.311135 * color.b;
+}
+
+/*
+ * http://en.wikipedia.org/wiki/Digital_compositing
+ */
+color_t tint(color_t src, color_t tint_color)
+{
+	return COLOR(
+		(tint_color.a * tint_color.r + (255 - tint_color.a) * src.r) / 255,
+		(tint_color.a * tint_color.g + (255 - tint_color.a) * src.g) / 255,
+		(tint_color.a * tint_color.b + (255 - tint_color.a) * src.b) / 255,
+		src.a);
+}
+
+
+color32_t color32_add(color32_t a, color32_t b)
+{
+	return COLOR32(
+			a.r + b.r,
+			a.g + b.g,
+			a.b + b.b
+	);
+}
+
+color32_t color32_mult(color32_t a, gint multiplier)
+{
+	return COLOR32(
+			multiplier * a.r,
+			multiplier * a.g,
+			multiplier * a.b
+	);
+}
+color32_t to_color32(color_t a)
+{
+	return COLOR32(a.r, a.g, a.b);
+}
+
+colord_t colord_add(colord_t a, colord_t b)
+{
+	return COLORD(
+			a.r + b.r,
+			a.g + b.g,
+			a.b + b.b,
+			a.a + b.a
+	);
+}
+colord_t colord_mult(colord_t a, gdouble multiplier)
+{
+	return COLORD(
+			multiplier * a.r,
+			multiplier * a.g,
+			multiplier * a.b,
+			multiplier * a.a
+	);
+}
+colord_t to_colord(color_t a)
+{
+	return COLORD(a.r, a.g, a.b, a.a);
+}
+
+
+void ring_shift(void *_pntr, gint num, size_t size)
+{
+	g_assert(num >= 2);
+
+	guint8 *pntr = (guint8*) _pntr;
+
+	char *tmp = g_malloc(size);
+	g_memmove(tmp, pntr, size);
+
+	for (gint i = 0; i < (num-1)*size; i+=size)
+		g_memmove(pntr+i, pntr+i+size, size);
+
+	g_memmove(pntr + (num-1)*size, tmp, size);
+	g_free(tmp);
+}
diff --git a/util.h b/util.h
new file mode 100644
index 0000000..e0833cf
--- /dev/null
+++ b/util.h
@@ -0,0 +1,58 @@
+#ifndef _UTIL_H_
+#define _UTIL_H_
+
+#include <glib.h>
+#include <gtk/gtk.h>
+
+#include <string.h>
+
+typedef struct _point {
+	gint16 x, y;
+} point_t;
+#define POINT(_x, _y) ((point_t){.x=(_x), .y=(_y)})
+
+/* a vector is the same as a point */
+typedef point_t vector_t;
+#define VECTOR(_x, _y) POINT(_x, _y)
+
+static inline vector_t vector(point_t p1, point_t p2) {
+	return VECTOR(p2.x - p1.x, p2.y - p1.y); 
+}
+
+typedef struct _color {
+	guint8 r, g, b, a;
+} color_t;
+#define COLOR(_r, _g, _b, _a) ((color_t){.r=(_r), .g=(_g), .b=(_b), .a=(_a)})
+#define COL_MAX G_MAXUINT8
+
+typedef struct _color32 {
+	gint32 r, g, b;
+} color32_t;
+
+#define COLOR32(_r, _g, _b) ((color32_t){.r=(_r), .g=(_g), .b=(_b)})
+#define COL32_MAX G_MAXINT32
+
+color32_t color32_add(color32_t, color32_t);
+color32_t color32_mult(color32_t, gint);
+color32_t to_color32(color_t);
+
+typedef struct _colord {
+	gdouble r, g, b, a;
+} colord_t;
+colord_t colord_add(colord_t, colord_t);
+colord_t colord_mult(colord_t, gdouble);
+colord_t to_colord(color_t);
+#define COLORD(_r, _g, _b, _a) ((colord_t){.r=(_r), .g=(_g), .b=(_b), .a=(_a)})
+#define COLORD_MAX G_MAXDOUBLE
+
+void put_pixel(GdkPixbuf *pixbuf, point_t point, color_t color);
+
+color_t get_pixel(GdkPixbuf *pixbuf, point_t point);
+
+void color_to_yiq(color_t color, guint8 *y, guint8 *i, guint8 *q);
+
+color_t tint(color_t src, color_t tint_color);
+
+void ring_shift(void *_pntr, gint num, size_t size);
+
+#endif /* _UTIL_H_ */
diff --git a/wimmel.c b/wimmel.c
new file mode 100644
index 0000000..712dacb
--- /dev/null
+++ b/wimmel.c
@@ -0,0 +1,158 @@
+#include <stdlib.h>
+#include <glib.h>
+#include <gdk-pixbuf/gdk-pixbuf.h>
+
+#include "util.h"
+
+static void
+find_image_in_wimmel(GdkPixbuf *wimmel, GdkPixbuf *match, GdkPixbuf *output)
+{
+	int wimmel_width, wimmel_height;
+	int width, height;
+	int i, j, k, n;
+	int difference, barrier;
+
+	wimmel_width = gdk_pixbuf_get_width(wimmel);
+	wimmel_height = gdk_pixbuf_get_height(wimmel);
+	width = gdk_pixbuf_get_width(match);
+	height = gdk_pixbuf_get_height(match);
+
+	barrier = width * height / 2;
+
+	for (j = 0; j < wimmel_height - height; ++j) {
+		for (i = 0; i < wimmel_width - width; ++i) {
+
+			difference = 0;
+			for (n = 0; n < height; ++n) {
+				for (k = 0; k < width; ++k) {
+					color_t color = get_pixel(wimmel, POINT(i + k, j + n));
+					color_t color_orig = get_pixel(match, POINT(k, n));
+
+#if 1
+					if (abs(color.r - color_orig.r) > 50 ||
+					    abs(color.g - color_orig.g) > 50 ||
+					    abs(color.b - color_orig.b) > 50) {
+						difference++;
+						if (difference > barrier)
+							break;
+					}
+#else
+					difference += 
+						abs(color.r - color_orig.r) + 
+						abs(color.g - color_orig.g) +
+						abs(color.b - color_orig.b);
+						if (difference > barrier * 300)
+							break;
+#endif
+				}
+			}
+
+#if 0
+			if (difference < barrier * 300) {
+#else
+			if (difference < barrier) {
+#endif
+				g_print("kleeblatt @ %d, %d; difference: %d\n", i, j, difference);
+				color_t color = COLOR(255, 0, 0, 0);
+				for (k = i; k < i+width; k++) {
+					put_pixel(output, POINT(k, j), color);
+					put_pixel(output, POINT(k, j+height), color);
+				}
+				for (n = j; n < j+height; n++) {
+					put_pixel(output, POINT(i, n), color);
+					put_pixel(output, POINT(i+width, n), color);
+				}
+			}
+		}
+	}
+}
+struct find_params {
+	GdkPixbuf *wimmel;
+	GdkPixbuf *match;
+	GdkPixbuf *output;
+};
+
+static gpointer
+find_thread(gpointer data)
+{
+	struct find_params *params = data;
+
+	find_image_in_wimmel(params->wimmel, params->match, params->output);
+	g_object_unref(params->wimmel);
+	g_object_unref(params->match);
+	g_object_unref(params->output);
+
+	free(params);
+
+	return NULL;
+}
+
+int
+main(int argc, char *argv[])
+{
+	char *file;
+	GdkPixbuf *wimmel, *output;
+	GdkPixbuf *match_tmp, *match;
+	int i, j;
+	int x1, y1, mwidth, mheight, width, height;
+#define N 4
+#define K 4
+	GThread *thread[N][K];
+
+	g_type_init();
+
+	if (argc < 5)
+		exit(EXIT_FAILURE);
+	
+	file = argv[1];
+	x1 = atoi(argv[2]);
+	y1 = atoi(argv[3]);
+	mwidth = atoi(argv[4]);
+	mheight = atoi(argv[5]);
+
+	wimmel = gdk_pixbuf_new_from_file(file, NULL);
+	if (!wimmel)
+		exit(EXIT_FAILURE);
+
+	output = gdk_pixbuf_copy(wimmel);
+
+	match_tmp = gdk_pixbuf_new_subpixbuf(wimmel, x1, y1, mwidth, mheight);
+	match = gdk_pixbuf_copy(match_tmp);
+	g_object_unref(match_tmp);
+
+	width = gdk_pixbuf_get_width(wimmel);
+	height = gdk_pixbuf_get_height(wimmel);
+
+	int step_x = width / N, step_y = height / K;
+	int x, y;
+	for (i = 0, x = 0; i < N; ++i, x += step_x) {
+		for (j = 0, y = 0; j < K; ++j, y += step_y) {
+			struct find_params *params = malloc(sizeof (struct find_params));;
+			if (!params)
+				exit(EXIT_FAILURE);
+			
+			int w = step_x + mwidth;
+			int h = step_y + mheight;
+
+			if (x + w > width)
+				w = width - x;
+			if (y + h > height)
+				h = height - y;
+
+			params->wimmel = gdk_pixbuf_new_subpixbuf(wimmel, x, y, w, h);
+			params->output = gdk_pixbuf_new_subpixbuf(output, x, y, w, h);
+			params->match = g_object_ref(match);
+
+			thread[i][j] = g_thread_create(find_thread, params, TRUE, NULL);
+		}
+	}
+
+	for (i = 0; i < N; ++i)
+		for (j = 0; j < K; ++j)
+			g_thread_join(thread[i][j]);
+
+	gdk_pixbuf_save(output, "output.png", "png", NULL, NULL);
+	g_object_unref(wimmel);
+	g_object_unref(output);
+	g_object_unref(match);
+}