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