Add and test a simple kernel matcher

This matcher is for up to four fingers, and has these properties:

* Approximately 1.4 times faster at 4 fingers
* Approximately 4.0 times faster at 2 fingers
* Roughly 100 lines of code

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>

4 files changed, 186 insertions, 15 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 33677c0..1c22c33 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -13,7 +13,8 @@ libmtdev_la_SOURCES = \
 	caps.c \
 	core.c \
 	iobuf.c \
-	match.c
+	match.c \
+	match_four.c
 
 AM_CFLAGS = $(CWARNFLAGS)
 
diff --git a/src/match.h b/src/match.h
index 98e1fa5..efba6f5 100644
--- a/src/match.h
+++ b/src/match.h
@@ -40,4 +40,12 @@
 void mtdev_match(int index[DIM_FINGER], int A[DIM2_FINGER],
 		 int nrow, int ncol);
 
+struct trk_coord {
+	int x;
+	int y;
+};
+
+const unsigned char *mtdev_match_four(const struct trk_coord *old, int nslot,
+				      const struct trk_coord *pos, int npos);
+
 #endif
diff --git a/src/match_four.c b/src/match_four.c
new file mode 100644
index 0000000..c7d2cd3
--- /dev/null
+++ b/src/match_four.c
@@ -0,0 +1,129 @@
+#include "match.h"
+#include <limits.h>
+
+typedef unsigned char u8;
+typedef unsigned int u32;
+
+/* generated by mtdev-kernel - do not edit */
+static const u8 match_data[] = {
+	0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 0, 0, 0, 1, 1,
+	1, 0, 0, 0, 1, 2, 1, 1, 0, 2, 2, 1, 2, 0, 0, 0,
+	1, 2, 3, 1, 1, 0, 2, 3, 2, 1, 2, 0, 3, 3, 1, 2,
+	3, 0, 0, 0, 1, 1, 1, 2, 1, 0, 0, 3, 0, 1, 1, 3,
+	1, 0, 2, 2, 3, 1, 2, 0, 0, 4, 0, 1, 2, 2, 4, 2,
+	1, 0, 0, 5, 0, 2, 1, 1, 5, 2, 0, 1, 1, 4, 1, 0,
+	2, 3, 2, 4, 1, 2, 0, 3, 3, 4, 1, 2, 3, 0, 0, 5,
+	0, 1, 2, 3, 2, 5, 2, 1, 0, 3, 3, 5, 2, 1, 3, 0,
+	0, 6, 0, 2, 1, 3, 1, 6, 2, 0, 1, 3, 3, 6, 2, 3,
+	1, 0, 0, 7, 0, 2, 3, 1, 1, 7, 2, 0, 3, 1, 2, 7,
+	2, 3, 0, 1, 0, 0, 1, 1, 2, 2, 1, 2, 1, 0, 0, 3,
+	0, 1, 1, 4, 2, 0, 3, 4, 2, 1, 0, 5, 0, 2, 2, 5,
+	1, 2, 2, 4, 6, 2, 1, 0, 1, 5, 6, 2, 0, 1, 2, 3,
+	7, 1, 2, 0, 0, 5, 7, 0, 2, 1, 1, 3, 8, 1, 0, 2,
+	0, 4, 8, 0, 1, 2, 2, 5, 8, 2, 1, 0, 3, 3, 5, 8,
+	2, 1, 3, 0, 1, 6, 8, 2, 0, 1, 3, 3, 6, 8, 2, 3,
+	1, 0, 1, 7, 8, 2, 0, 3, 1, 2, 7, 8, 2, 3, 0, 1,
+	2, 4, 9, 1, 2, 0, 3, 3, 4, 9, 1, 2, 3, 0, 0, 6,
+	9, 0, 2, 1, 3, 3, 6, 9, 3, 2, 1, 0, 0, 7, 9, 0,
+	2, 3, 1, 2, 7, 9, 3, 2, 0, 1, 1, 4, 10, 1, 0, 2,
+	3, 3, 4, 10, 1, 3, 2, 0, 0, 5, 10, 0, 1, 2, 3, 3,
+	5, 10, 3, 1, 2, 0, 0, 7, 10, 0, 3, 2, 1, 1, 7, 10,
+	3, 0, 2, 1, 1, 4, 11, 1, 0, 3, 2, 2, 4, 11, 1, 3,
+	0, 2, 0, 5, 11, 0, 1, 3, 2, 2, 5, 11, 3, 1, 0, 2,
+	0, 6, 11, 0, 3, 1, 2, 1, 6, 11, 3, 0, 1, 2, 0, 0,
+	1, 1, 2, 2, 3, 3, 1, 2, 1, 0, 0, 3, 0, 1, 1, 4,
+	2, 0, 3, 4, 2, 1, 0, 5, 0, 2, 2, 5, 1, 2, 1, 6,
+	3, 0, 3, 6, 3, 1, 5, 6, 3, 2, 0, 7, 0, 3, 2, 7,
+	1, 3, 4, 7, 2, 3, 2, 4, 6, 2, 1, 0, 1, 5, 6, 2,
+	0, 1, 2, 3, 7, 1, 2, 0, 0, 5, 7, 0, 2, 1, 1, 3,
+	8, 1, 0, 2, 0, 4, 8, 0, 1, 2, 2, 4, 9, 3, 1, 0,
+	1, 5, 9, 3, 0, 1, 2, 7, 9, 3, 2, 0, 5, 7, 9, 3,
+	2, 1, 1, 8, 9, 3, 0, 2, 4, 8, 9, 3, 1, 2, 2, 3,
+	10, 1, 3, 0, 0, 5, 10, 0, 3, 1, 2, 6, 10, 2, 3, 0,
+	5, 6, 10, 2, 3, 1, 0, 8, 10, 0, 3, 2, 3, 8, 10, 1,
+	3, 2, 1, 3, 11, 1, 0, 3, 0, 4, 11, 0, 1, 3, 1, 6,
+	11, 2, 0, 3, 4, 6, 11, 2, 1, 3, 0, 7, 11, 0, 2, 3,
+	3, 7, 11, 1, 2, 3, 3, 6, 9, 12, 3, 2, 1, 0, 2, 7,
+	9, 12, 3, 2, 0, 1, 3, 5, 10, 12, 3, 1, 2, 0, 1, 7,
+	10, 12, 3, 0, 2, 1, 2, 5, 11, 12, 3, 1, 0, 2, 1, 6,
+	11, 12, 3, 0, 1, 2, 3, 6, 8, 13, 2, 3, 1, 0, 2, 7,
+	8, 13, 2, 3, 0, 1, 3, 4, 10, 13, 1, 3, 2, 0, 0, 7,
+	10, 13, 0, 3, 2, 1, 2, 4, 11, 13, 1, 3, 0, 2, 0, 6,
+	11, 13, 0, 3, 1, 2, 3, 5, 8, 14, 2, 1, 3, 0, 1, 7,
+	8, 14, 2, 0, 3, 1, 3, 4, 9, 14, 1, 2, 3, 0, 0, 7,
+	9, 14, 0, 2, 3, 1, 1, 4, 11, 14, 1, 0, 3, 2, 0, 5,
+	11, 14, 0, 1, 3, 2, 2, 5, 8, 15, 2, 1, 0, 3, 1, 6,
+	8, 15, 2, 0, 1, 3, 2, 4, 9, 15, 1, 2, 0, 3, 0, 6,
+	9, 15, 0, 2, 1, 3, 1, 4, 10, 15, 1, 0, 2, 3, 0, 5,
+	10, 15, 0, 1, 2, 3,
+};
+
+/* generated by mtdev-kernel - do not edit */
+static const int match_index[][5] = {
+	{ 0, 0, 1, 3, 6 },
+	{ 10, 10, 12, 18, 30 },
+	{ 50, 50, 54, 62, 92 },
+	{ 164, 164, 170, 194, 230 },
+	{ 398, 398, 406, 454, 598 },
+	{ 790 }
+};
+
+static void set_dist(u32 *dist,
+		     const struct trk_coord *b1, const struct trk_coord *e1,
+		     const struct trk_coord *b2, const struct trk_coord *e2)
+{
+	const struct trk_coord *p, *q;
+
+	for (p = b1; p != e1; p++)
+		for (q = b2; q != e2; q++)
+			*dist++ = abs(q->x - p->x) + abs(q->y - p->y);
+}
+
+const u8 *mtdev_match_four(const struct trk_coord *old, int nslot,
+			   const struct trk_coord *pos, int npos)
+{
+	u32 d[16], obj, t;
+	const u8 *p, *b, *e;
+	const int *at;
+
+	set_dist(d, old, old + nslot, pos, pos + npos);
+
+	at = &match_index[nslot][npos];
+	b = &match_data[at[0]];
+	e = &match_data[at[1]];
+
+	obj = UINT_MAX, p = b;
+
+	switch (minval(nslot, npos)) {
+	case 1:
+		for (; b != e; b += npos) {
+			t = d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	case 2:
+		for (; b != e; b += npos) {
+			t = d[*b++], t += d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	case 3:
+		for (; b != e; b += npos) {
+			t = d[*b++], t += d[*b++], t += d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	case 4:
+		for (; b != e; b += npos) {
+			t = d[*b++], t += d[*b++], t += d[*b++], t += d[*b++];
+			if (t < obj)
+				obj = t, p = b;
+		}
+		break;
+	}
+
+	return p;
+}
diff --git a/test/mtdev-matching.c b/test/mtdev-matching.c
index dc68994..799429f 100644
--- a/test/mtdev-matching.c
+++ b/test/mtdev-matching.c
@@ -30,7 +30,9 @@
 #include <stdio.h>
 #include <time.h>
 
-#define ITS 1000000
+#define ITS 4000000
+const int n1 = 4;
+const int n2 = 4;
 
 static void test1()
 {
@@ -99,32 +101,61 @@ static void speed1()
 	int A[DIM2_FINGER];
 	int x1[DIM_FINGER] = { 1, 5, 2, 3, 4, 5, 6, 7, 8 };
 	int y1[DIM_FINGER] = { 1, 5, 2, 3, 4, 6, 6, 7, 8 };
-	int x2[DIM_FINGER] = { 1.1, 3, 2, 4, 5, 6, 7, 8 };
+	int x2[DIM_FINGER] = { 1, 3, 2, 4, 5, 6, 7, 8 };
 	int y2[DIM_FINGER] = { 1, 3, 2, 4, 5, 6, 7, 8 };
 	int index[DIM_FINGER];
-	int n1 = 4;
-	int n2 = 7;
+	int i, j, k;
 
-	int i, j;
-
-	for (i = 0; i < n1; i++) {
-		for (j = 0; j < n2; j++) {
-			A[i + n1 * j] =
-				(x1[i] - x2[j]) * (x1[i] - x2[j]) +
-				(y1[i] - y2[j]) * (y1[i] - y2[j]);
+	clock_t t1 = clock();
+	for (k = 0; k < ITS; k++) {
+		for (i = 0; i < n1; i++) {
+			for (j = 0; j < n2; j++) {
+				A[i + n1 * j] =
+					(x1[i] - x2[j]) * (x1[i] - x2[j]) +
+					(y1[i] - y2[j]) * (y1[i] - y2[j]);
+			}
 		}
+		mtdev_match(index, A, n1, n2);
 	}
+	clock_t t2 = clock();
+
+	printf("%lf matches per second\n",
+	       ITS * ((float)CLOCKS_PER_SEC / (t2 - t1)));
+
+	for (i = 0; i < n1; i++)
+		printf("match[%d] = %d\n", i, index[i]);
+
+}
+
+static void speed2()
+{
+	struct trk_coord p1[] = {
+		{ 1, 1 },
+		{ 5, 5 },
+		{ 2, 2 },
+		{ 3, 3 },
+		{ 4, 4 },
+	};
+	struct trk_coord p2[] = {
+		{ 1, 1 },
+		{ 3, 3 },
+		{ 2, 2 },
+		{ 4, 4 },
+		{ 5, 5 },
+	};
+	const unsigned char *p;
+	int i;
 
 	clock_t t1 = clock();
 	for (i = 0; i < ITS; i++)
-		mtdev_match(index, A, n1, n2);
+		p = mtdev_match_four(p1, n1, p2, n2);
 	clock_t t2 = clock();
 
 	printf("%lf matches per second\n",
 	       ITS * ((float)CLOCKS_PER_SEC / (t2 - t1)));
 
-	for (i = 0; i < n1; i++)
-		printf("match[%d] = %d\n", i, index[i]);
+	for (i = 0; i < n2; i++)
+		printf("match[%d] = %d\n", i, p[i]);
 
 }
 
@@ -136,6 +167,8 @@ int main(int argc, char *argv[])
 	test2();
 	printf("speed1\n");
 	speed1();
+	printf("speed2\n");
+	speed2();
 	printf("done\n");
 	return 0;
 }