summaryrefslogtreecommitdiff
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 @@
1/***************************************************************************
2 *
3 * Multitouch X driver
4 * Copyright (C) 2008 Henrik Rydberg <rydberg@euromail.se>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 **************************************************************************/
21
22#include "match.h"
23#include <string.h>
24#include <stdio.h>
25
26/**
27 * Bitmap implementation of the hungarian algorithm (GPL license)
28 *
29 * Copyright (C) 2008 Henrik Rydberg <rydberg@euromail.se>
30 *
31 * Based on code released by Markus Buehren (2004) (BSD license)
32 *
33 * Copyright (C) 2004, Markus Buehren. All rights reserved.
34 * See CREDITS file for full license terms.
35 *
36 */
37
38typedef unsigned col_t[1];
39typedef unsigned mat_t[DIM_FINGER];
40
41#define GET1(m, x) ((m[0] >> (x)) & 1U)
42#define SET1(m, x) (m[0] |= (1U << (x)))
43#define CLEAR1(m, x) (m[0] &= ~(1U << (x)))
44
45#define GET2(m, row, col) ((m[col] >> (row)) & 1U)
46#define SET2(m, row, col) (m[col] |= (1U << (row)))
47#define CLEAR2(m, row, col) (m[col] &= ~(1U << (row)))
48
49/********************************************************/
50
51static void buildixvector(int *ix, mat_t mstar, int nrows, int ncols)
52{
53 int row, col;
54 for (row = 0; row < nrows; row++) {
55 for (col = 0; col < ncols; col++) {
56 if (GET2(mstar, row, col)) {
57 ix[row] = col;
58 break;
59 }
60 }
61 }
62}
63
64
65/********************************************************/
66
67static void step2a(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
68 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
69 int dmin);
70static void step2b(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
71 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
72 int dmin);
73static void step3(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
74 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
75 int dmin);
76static void step4(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
77 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
78 int dmin, int row, int col);
79static void step5(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
80 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
81 int dmin);
82
83static void ixoptimal(int *ix, int *mdist, int nrows, int ncols)
84{
85 int *mdistTemp, *mdistEnd, *columnEnd, value, minValue;
86 int dmin, row, col;
87 col_t ccol, crow;
88 mat_t mstar, mprime, nmstar;
89
90 memset(ccol, 0, sizeof(col_t));
91 memset(crow, 0, sizeof(col_t));
92 memset(mstar, 0, sizeof(mat_t));
93 memset(mprime, 0, sizeof(mat_t));
94 memset(nmstar, 0, sizeof(mat_t));
95
96 /* initialization */
97 for (row = 0; row < nrows; row++)
98 ix[row] = -1;
99
100 mdistEnd = mdist + nrows * ncols;
101
102 /* preliminary steps */
103 if (nrows <= ncols) {
104 dmin = nrows;
105
106 for (row = 0; row < nrows; row++) {
107 /* find the smallest element in the row */
108 mdistTemp = mdist + row;
109 minValue = *mdistTemp;
110 mdistTemp += nrows;
111 while (mdistTemp < mdistEnd) {
112 value = *mdistTemp;
113 if (value < minValue)
114 minValue = value;
115 mdistTemp += nrows;
116 }
117
118 /* subtract the smallest element from each element
119 of the row */
120 mdistTemp = mdist + row;
121 while (mdistTemp < mdistEnd) {
122 *mdistTemp -= minValue;
123 mdistTemp += nrows;
124 }
125 }
126
127 /* Steps 1 and 2a */
128 for (row = 0; row < nrows; row++) {
129 for (col = 0; col < ncols; col++) {
130 if (mdist[row + nrows * col] != 0)
131 continue;
132 if (GET1(ccol, col))
133 continue;
134 SET2(mstar, row, col);
135 SET1(ccol, col);
136 break;
137 }
138 }
139 } else {
140 dmin = ncols;
141
142 for (col = 0; col < ncols; col++) {
143 /* find the smallest element in the column */
144 mdistTemp = mdist + nrows*col;
145 columnEnd = mdistTemp + nrows;
146
147 minValue = *mdistTemp++;
148 while (mdistTemp < columnEnd) {
149 value = *mdistTemp++;
150 if (value < minValue)
151 minValue = value;
152 }
153
154 /* subtract the smallest element from each element
155 of the column */
156 mdistTemp = mdist + nrows*col;
157 while (mdistTemp < columnEnd)
158 *mdistTemp++ -= minValue;
159 }
160
161 /* Steps 1 and 2a */
162 for (col = 0; col < ncols; col++) {
163 for (row = 0; row < nrows; row++) {
164 if (mdist[row + nrows * col] != 0)
165 continue;
166 if (GET1(crow, row))
167 continue;
168 SET2(mstar, row, col);
169 SET1(ccol, col);
170 SET1(crow, row);
171 break;
172 }
173 }
174 memset(crow, 0, sizeof(col_t));
175 }
176
177 /* move to step 2b */
178 step2b(ix, mdist, mstar, nmstar,
179 mprime, ccol, crow, nrows, ncols,
180 dmin);
181}
182
183/********************************************************/
184static void step2a(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
185 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
186 int dmin)
187{
188 int col, row;
189
190 /* cover every column containing a starred zero */
191 for (col = 0; col < ncols; col++) {
192 for (row = 0; row < nrows; row++) {
193 if (!GET2(mstar, row, col))
194 continue;
195 SET1(ccol, col);
196 break;
197 }
198 }
199
200 /* move to step 3 */
201 step2b(ix, mdist, mstar, nmstar,
202 mprime, ccol, crow, nrows, ncols,
203 dmin);
204}
205
206/********************************************************/
207static void step2b(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
208 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
209 int dmin)
210{
211 int col, ncc;
212
213 /* count covered columns */
214 ncc = 0;
215 for (col = 0; col < ncols; col++)
216 if (GET1(ccol, col))
217 ncc++;
218
219 if (ncc == dmin) {
220 /* algorithm finished */
221 buildixvector(ix, mstar, nrows, ncols);
222 } else {
223 /* move to step 3 */
224 step3(ix, mdist, mstar, nmstar,
225 mprime, ccol, crow, nrows, ncols,
226 dmin);
227 }
228
229}
230
231/********************************************************/
232static void step3(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
233 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
234 int dmin)
235{
236 int zerosFound;
237 int row, col, cstar;
238
239 zerosFound = 1;
240 while (zerosFound) {
241 zerosFound = 0;
242 for (col = 0; col < ncols; col++) {
243 if (GET1(ccol, col))
244 continue;
245 for (row = 0; row < nrows; row++) {
246 if (mdist[row + nrows * col] != 0)
247 continue;
248 if (GET1(crow, row))
249 continue;
250
251 /* prime zero */
252 SET2(mprime, row, col);
253
254 /* find starred zero in current row */
255 for (cstar = 0; cstar < ncols; cstar++)
256 if (GET2(mstar, row, cstar))
257 break;
258
259 if (cstar == ncols) { /* no starred zero */
260 /* move to step 4 */
261 step4(ix, mdist, mstar, nmstar,
262 mprime, ccol, crow, nrows, ncols,
263 dmin, row, col);
264 return;
265 } else {
266 SET1(crow, row);
267 CLEAR1(ccol, cstar);
268 zerosFound = 1;
269 break;
270 }
271 }
272 }
273 }
274
275 /* move to step 5 */
276 step5(ix, mdist, mstar, nmstar,
277 mprime, ccol, crow, nrows, ncols,
278 dmin);
279}
280
281/********************************************************/
282static void step4(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
283 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
284 int dmin, int row, int col)
285{
286 int n, rstar, cstar, primeRow, primeCol;
287
288 /* generate temporary copy of mstar */
289 memcpy(nmstar, mstar, sizeof(mat_t));
290
291 /* star current zero */
292 SET2(nmstar, row, col);
293
294 /* find starred zero in current column */
295 cstar = col;
296 for (rstar = 0; rstar < nrows; rstar++)
297 if (GET2(mstar, rstar, cstar))
298 break;
299
300 while (rstar < nrows) {
301 /* unstar the starred zero */
302 CLEAR2(nmstar, rstar, cstar);
303
304 /* find primed zero in current row */
305 primeRow = rstar;
306 for (primeCol = 0; primeCol < ncols; primeCol++)
307 if (GET2(mprime, primeRow, primeCol))
308 break;
309
310 /* star the primed zero */
311 SET2(nmstar, primeRow, primeCol);
312
313 /* find starred zero in current column */
314 cstar = primeCol;
315 for (rstar = 0; rstar < nrows; rstar++)
316 if (GET2(mstar, rstar, cstar))
317 break;
318 }
319
320 /* use temporary copy as new mstar */
321 /* delete all primes, uncover all rows */
322 memcpy(mstar, nmstar, sizeof(mat_t));
323 memset(mprime, 0, sizeof(mat_t));
324 memset(crow, 0, sizeof(col_t));
325
326 /* move to step 2a */
327 step2a(ix, mdist, mstar, nmstar,
328 mprime, ccol, crow, nrows, ncols,
329 dmin);
330}
331
332/********************************************************/
333static void step5(int *ix, int *mdist, mat_t mstar, mat_t nmstar,
334 mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols,
335 int dmin)
336{
337 int h = 0, value;
338 int row, col, found = 0;
339
340 /* find smallest uncovered element h */
341 for (row = 0; row < nrows; row++) {
342 if (GET1(crow, row))
343 continue;
344 for (col = 0; col < ncols; col++) {
345 if (GET1(ccol, col))
346 continue;
347 value = mdist[row + nrows * col];
348 if (!found || value < h) {
349 h = value;
350 found = 1;
351 }
352 }
353 }
354
355 /* where to go if nothing uncovered? */
356 if (!found)
357 return;
358
359 /* add h to each covered row */
360 for (row = 0; row < nrows; row++) {
361 if (!GET1(crow, row))
362 continue;
363 for (col = 0; col < ncols; col++)
364 mdist[row + nrows * col] += h;
365 }
366
367 /* subtract h from each uncovered column */
368 for (col = 0; col < ncols; col++) {
369 if (GET1(ccol, col))
370 continue;
371 for (row = 0; row < nrows; row++)
372 mdist[row + nrows * col] -= h;
373 }
374
375 /* move to step 3 */
376 step3(ix, mdist, mstar, nmstar,
377 mprime, ccol, crow, nrows, ncols,
378 dmin);
379}
380
381void match_fingers(int ix[DIM_FINGER], int A[DIM2_FINGER], int nrow, int ncol)
382{
383 ixoptimal(ix, A, nrow, ncol);
384}
385
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 @@
1/***************************************************************************
2 *
3 * Multitouch X driver
4 * Copyright (C) 2008 Henrik Rydberg <rydberg@euromail.se>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 *
20 **************************************************************************/
21
22#include <match.h>
23#include <xbypass.h>
24#include <stdio.h>
25#include <time.h>
26
27#define ITS 1000000
28
29static void test1()
30{
31 int A[] = {
32 1013,
33 3030660,
34 3559354,
35 12505925,
36 19008450,
37 6946421,
38 6118613,
39 698020,
40 3021800,
41 1017,
42 37573,
43 3242018,
44 8152794,
45 1266053,
46 942941,
47 462820,
48 };
49 int index[DIM_FINGER], i;
50 match_fingers(index, A, 4, 4);
51 for (i = 0; i < 4; i++)
52 printf("match[%d] = %d\n", i, index[i]);
53}
54
55static void test2()
56{
57 int A[] = {
58 0,
59 4534330,
60 22653552,
61 12252500,
62 685352,
63 4534330,
64 0,
65 9619317,
66 28409530,
67 6710170,
68 22653552,
69 9619317,
70 0,
71 47015292,
72 29788572,
73 2809040,
74 10428866,
75 38615920,
76 17732500,
77 719528,
78 12113945,
79 28196220,
80 46778656,
81 405,
82 14175493,
83 };
84 int index[DIM_FINGER], i;
85 match_fingers(index, A, 5, 5);
86 for (i = 0; i < 5; i++)
87 printf("match[%d] = %d\n", i, index[i]);
88}
89
90static void speed1()
91{
92 /* column-by-column matrix */
93 int A[DIM2_FINGER];
94 int x1[DIM_FINGER] = { 1, 5, 2, 3, 4, 5, 6, 7, 8 };
95 int y1[DIM_FINGER] = { 1, 5, 2, 3, 4, 6, 6, 7, 8 };
96 int x2[DIM_FINGER] = { 1.1, 3, 2, 4, 5, 6, 7, 8 };
97 int y2[DIM_FINGER] = { 1, 3, 2, 4, 5, 6, 7, 8 };
98 int index[DIM_FINGER];
99 int n1 = 4;
100 int n2 = 7;
101
102 int i, j;
103
104 for (i = 0; i < n1; i++) {
105 for (j = 0; j < n2; j++) {
106 A[i + n1 * j] =
107 (x1[i] - x2[j]) * (x1[i] - x2[j]) +
108 (y1[i] - y2[j]) * (y1[i] - y2[j]);
109 }
110 }
111
112 clock_t t1 = clock();
113 for (i = 0; i < ITS; i++)
114 match_fingers(index, A, n1, n2);
115 clock_t t2 = clock();
116
117 printf("%lf matches per second\n",
118 ITS * ((float)CLOCKS_PER_SEC / (t2 - t1)));
119
120 for (i = 0; i < n1; i++)
121 printf("match[%d] = %d\n", i, index[i]);
122
123}
124
125int main(int argc, char *argv[])
126{
127 printf("test1\n");
128 test1();
129 printf("test2\n");
130 test2();
131 printf("speed1\n");
132 speed1();
133 printf("done\n");
134 return 0;
135}
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-20 19:03:01 +0000