aboutsummaryrefslogtreecommitdiffstats
path: root/match
diff options
context:
space:
mode:
Diffstat (limited to 'match')
-rw-r--r--match/match.c385
-rw-r--r--match/test.c135
2 files changed, 0 insertions, 520 deletions
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 <rydberg@euromail.se>
- *
- * 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 <string.h>
-#include <stdio.h>
-
-/**
- * Bitmap implementation of the hungarian algorithm (GPL license)
- *
- * Copyright (C) 2008 Henrik Rydberg <rydberg@euromail.se>
- *
- * 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 <rydberg@euromail.se>
- *
- * 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 <xbypass.h>
-#include <stdio.h>
-#include <time.h>
-
-#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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-10 01:56:24 +0000