summaryrefslogtreecommitdiff
path: root/match/match.c
diff options
context:
space:
mode:
Diffstat (limited to 'match/match.c')
-rw-r--r--match/match.c385
1 files changed, 0 insertions, 385 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
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-20 17:01:18 +0000