From acea9df3381825a634c000a574f58b4ca5293ee8 Mon Sep 17 00:00:00 2001 From: Henrik Rydberg Date: Tue, 12 Oct 2010 15:38:43 +0200 Subject: Same version, but using the mtdev library. Signed-off-by: Henrik Rydberg --- match/match.c | 385 ---------------------------------------------------------- match/test.c | 135 -------------------- 2 files changed, 520 deletions(-) delete mode 100644 match/match.c delete mode 100644 match/test.c (limited to 'match') diff --git a/match/match.c b/match/match.c deleted file mode 100644 index 4cb4495..0000000 --- a/match/match.c +++ /dev/null @@ -1,385 +0,0 @@ -/*************************************************************************** - * - * Multitouch X driver - * Copyright (C) 2008 Henrik Rydberg - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - **************************************************************************/ - -#include "match.h" -#include -#include - -/** - * Bitmap implementation of the hungarian algorithm (GPL license) - * - * Copyright (C) 2008 Henrik Rydberg - * - * Based on code released by Markus Buehren (2004) (BSD license) - * - * Copyright (C) 2004, Markus Buehren. All rights reserved. - * See CREDITS file for full license terms. - * - */ - -typedef unsigned col_t[1]; -typedef unsigned mat_t[DIM_FINGER]; - -#define GET1(m, x) ((m[0] >> (x)) & 1U) -#define SET1(m, x) (m[0] |= (1U << (x))) -#define CLEAR1(m, x) (m[0] &= ~(1U << (x))) - -#define GET2(m, row, col) ((m[col] >> (row)) & 1U) -#define SET2(m, row, col) (m[col] |= (1U << (row))) -#define CLEAR2(m, row, col) (m[col] &= ~(1U << (row))) - -/********************************************************/ - -static void buildixvector(int *ix, mat_t mstar, int nrows, int ncols) -{ - int row, col; - for (row = 0; row < nrows; row++) { - for (col = 0; col < ncols; col++) { - if (GET2(mstar, row, col)) { - ix[row] = col; - break; - } - } - } -} - - -/********************************************************/ - -static void step2a(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin); -static void step2b(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin); -static void step3(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin); -static void step4(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin, int row, int col); -static void step5(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin); - -static void ixoptimal(int *ix, int *mdist, int nrows, int ncols) -{ - int *mdistTemp, *mdistEnd, *columnEnd, value, minValue; - int dmin, row, col; - col_t ccol, crow; - mat_t mstar, mprime, nmstar; - - memset(ccol, 0, sizeof(col_t)); - memset(crow, 0, sizeof(col_t)); - memset(mstar, 0, sizeof(mat_t)); - memset(mprime, 0, sizeof(mat_t)); - memset(nmstar, 0, sizeof(mat_t)); - - /* initialization */ - for (row = 0; row < nrows; row++) - ix[row] = -1; - - mdistEnd = mdist + nrows * ncols; - - /* preliminary steps */ - if (nrows <= ncols) { - dmin = nrows; - - for (row = 0; row < nrows; row++) { - /* find the smallest element in the row */ - mdistTemp = mdist + row; - minValue = *mdistTemp; - mdistTemp += nrows; - while (mdistTemp < mdistEnd) { - value = *mdistTemp; - if (value < minValue) - minValue = value; - mdistTemp += nrows; - } - - /* subtract the smallest element from each element - of the row */ - mdistTemp = mdist + row; - while (mdistTemp < mdistEnd) { - *mdistTemp -= minValue; - mdistTemp += nrows; - } - } - - /* Steps 1 and 2a */ - for (row = 0; row < nrows; row++) { - for (col = 0; col < ncols; col++) { - if (mdist[row + nrows * col] != 0) - continue; - if (GET1(ccol, col)) - continue; - SET2(mstar, row, col); - SET1(ccol, col); - break; - } - } - } else { - dmin = ncols; - - for (col = 0; col < ncols; col++) { - /* find the smallest element in the column */ - mdistTemp = mdist + nrows*col; - columnEnd = mdistTemp + nrows; - - minValue = *mdistTemp++; - while (mdistTemp < columnEnd) { - value = *mdistTemp++; - if (value < minValue) - minValue = value; - } - - /* subtract the smallest element from each element - of the column */ - mdistTemp = mdist + nrows*col; - while (mdistTemp < columnEnd) - *mdistTemp++ -= minValue; - } - - /* Steps 1 and 2a */ - for (col = 0; col < ncols; col++) { - for (row = 0; row < nrows; row++) { - if (mdist[row + nrows * col] != 0) - continue; - if (GET1(crow, row)) - continue; - SET2(mstar, row, col); - SET1(ccol, col); - SET1(crow, row); - break; - } - } - memset(crow, 0, sizeof(col_t)); - } - - /* move to step 2b */ - step2b(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin); -} - -/********************************************************/ -static void step2a(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin) -{ - int col, row; - - /* cover every column containing a starred zero */ - for (col = 0; col < ncols; col++) { - for (row = 0; row < nrows; row++) { - if (!GET2(mstar, row, col)) - continue; - SET1(ccol, col); - break; - } - } - - /* move to step 3 */ - step2b(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin); -} - -/********************************************************/ -static void step2b(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin) -{ - int col, ncc; - - /* count covered columns */ - ncc = 0; - for (col = 0; col < ncols; col++) - if (GET1(ccol, col)) - ncc++; - - if (ncc == dmin) { - /* algorithm finished */ - buildixvector(ix, mstar, nrows, ncols); - } else { - /* move to step 3 */ - step3(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin); - } - -} - -/********************************************************/ -static void step3(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin) -{ - int zerosFound; - int row, col, cstar; - - zerosFound = 1; - while (zerosFound) { - zerosFound = 0; - for (col = 0; col < ncols; col++) { - if (GET1(ccol, col)) - continue; - for (row = 0; row < nrows; row++) { - if (mdist[row + nrows * col] != 0) - continue; - if (GET1(crow, row)) - continue; - - /* prime zero */ - SET2(mprime, row, col); - - /* find starred zero in current row */ - for (cstar = 0; cstar < ncols; cstar++) - if (GET2(mstar, row, cstar)) - break; - - if (cstar == ncols) { /* no starred zero */ - /* move to step 4 */ - step4(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin, row, col); - return; - } else { - SET1(crow, row); - CLEAR1(ccol, cstar); - zerosFound = 1; - break; - } - } - } - } - - /* move to step 5 */ - step5(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin); -} - -/********************************************************/ -static void step4(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin, int row, int col) -{ - int n, rstar, cstar, primeRow, primeCol; - - /* generate temporary copy of mstar */ - memcpy(nmstar, mstar, sizeof(mat_t)); - - /* star current zero */ - SET2(nmstar, row, col); - - /* find starred zero in current column */ - cstar = col; - for (rstar = 0; rstar < nrows; rstar++) - if (GET2(mstar, rstar, cstar)) - break; - - while (rstar < nrows) { - /* unstar the starred zero */ - CLEAR2(nmstar, rstar, cstar); - - /* find primed zero in current row */ - primeRow = rstar; - for (primeCol = 0; primeCol < ncols; primeCol++) - if (GET2(mprime, primeRow, primeCol)) - break; - - /* star the primed zero */ - SET2(nmstar, primeRow, primeCol); - - /* find starred zero in current column */ - cstar = primeCol; - for (rstar = 0; rstar < nrows; rstar++) - if (GET2(mstar, rstar, cstar)) - break; - } - - /* use temporary copy as new mstar */ - /* delete all primes, uncover all rows */ - memcpy(mstar, nmstar, sizeof(mat_t)); - memset(mprime, 0, sizeof(mat_t)); - memset(crow, 0, sizeof(col_t)); - - /* move to step 2a */ - step2a(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin); -} - -/********************************************************/ -static void step5(int *ix, int *mdist, mat_t mstar, mat_t nmstar, - mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, - int dmin) -{ - int h = 0, value; - int row, col, found = 0; - - /* find smallest uncovered element h */ - for (row = 0; row < nrows; row++) { - if (GET1(crow, row)) - continue; - for (col = 0; col < ncols; col++) { - if (GET1(ccol, col)) - continue; - value = mdist[row + nrows * col]; - if (!found || value < h) { - h = value; - found = 1; - } - } - } - - /* where to go if nothing uncovered? */ - if (!found) - return; - - /* add h to each covered row */ - for (row = 0; row < nrows; row++) { - if (!GET1(crow, row)) - continue; - for (col = 0; col < ncols; col++) - mdist[row + nrows * col] += h; - } - - /* subtract h from each uncovered column */ - for (col = 0; col < ncols; col++) { - if (GET1(ccol, col)) - continue; - for (row = 0; row < nrows; row++) - mdist[row + nrows * col] -= h; - } - - /* move to step 3 */ - step3(ix, mdist, mstar, nmstar, - mprime, ccol, crow, nrows, ncols, - dmin); -} - -void match_fingers(int ix[DIM_FINGER], int A[DIM2_FINGER], int nrow, int ncol) -{ - ixoptimal(ix, A, nrow, ncol); -} - diff --git a/match/test.c b/match/test.c deleted file mode 100644 index dabc083..0000000 --- a/match/test.c +++ /dev/null @@ -1,135 +0,0 @@ -/*************************************************************************** - * - * Multitouch X driver - * Copyright (C) 2008 Henrik Rydberg - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software - * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA - * - **************************************************************************/ - -#include -#include -#include -#include - -#define ITS 1000000 - -static void test1() -{ - int A[] = { - 1013, - 3030660, - 3559354, - 12505925, - 19008450, - 6946421, - 6118613, - 698020, - 3021800, - 1017, - 37573, - 3242018, - 8152794, - 1266053, - 942941, - 462820, - }; - int index[DIM_FINGER], i; - match_fingers(index, A, 4, 4); - for (i = 0; i < 4; i++) - printf("match[%d] = %d\n", i, index[i]); -} - -static void test2() -{ - int A[] = { - 0, - 4534330, - 22653552, - 12252500, - 685352, - 4534330, - 0, - 9619317, - 28409530, - 6710170, - 22653552, - 9619317, - 0, - 47015292, - 29788572, - 2809040, - 10428866, - 38615920, - 17732500, - 719528, - 12113945, - 28196220, - 46778656, - 405, - 14175493, - }; - int index[DIM_FINGER], i; - match_fingers(index, A, 5, 5); - for (i = 0; i < 5; i++) - printf("match[%d] = %d\n", i, index[i]); -} - -static void speed1() -{ - /* column-by-column matrix */ - 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 y2[DIM_FINGER] = { 1, 3, 2, 4, 5, 6, 7, 8 }; - int index[DIM_FINGER]; - int n1 = 4; - int n2 = 7; - - 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 (i = 0; i < ITS; i++) - match_fingers(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]); - -} - -int main(int argc, char *argv[]) -{ - printf("test1\n"); - test1(); - printf("test2\n"); - test2(); - printf("speed1\n"); - speed1(); - printf("done\n"); - return 0; -} -- cgit v1.2.3