summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--match/match.c189
-rw-r--r--match/match.h4
-rw-r--r--match/test.c44
3 files changed, 137 insertions, 100 deletions
diff --git a/match/match.c b/match/match.c
index 551e2f6..3c5ea0c 100644
--- a/match/match.c
+++ b/match/match.c
@@ -8,22 +8,25 @@
8 * modified by Henrik Rydberg (2008) 8 * modified by Henrik Rydberg (2008)
9 */ 9 */
10 10
11const float BIG_VALUE = 1e20; 11typedef unsigned short col_t[1];
12typedef unsigned short mat_t[DIM_FINGER];
12 13
13typedef unsigned short col_t; 14#define GET1(m, x) ((m[0]>>(x))&1U)
15#define SET1(m, x) (m[0]|=(1U<<(x)))
16#define CLEAR1(m, x) (m[0]&=~(1U<<(x)))
14 17
15#define GETBIT2(m, row, col) ((m[col]>>(row))&1U) 18#define GET2(m, row, col) ((m[col]>>(row))&1U)
16#define SETBIT2(m, row, col) (m[col]|=(1U<<(row))) 19#define SET2(m, row, col) (m[col]|=(1U<<(row)))
17#define CLEARBIT2(m, row, col) (m[col]&=~(1U<<(row))) 20#define CLEAR2(m, row, col) (m[col]&=~(1U<<(row)))
18 21
19/********************************************************/ 22/********************************************************/
20 23
21static void buildixvector(int *ix, col_t *mstar, int nrows, int ncols) 24static void buildixvector(int *ix, mat_t mstar, int nrows, int ncols)
22{ 25{
23 int row, col; 26 int row, col;
24 for (row = 0; row < nrows; row++) { 27 for (row = 0; row < nrows; row++) {
25 for (col = 0; col < ncols; col++) { 28 for (col = 0; col < ncols; col++) {
26 if (GETBIT2(mstar, row, col)) { 29 if (GET2(mstar, row, col)) {
27 ix[row] = col; 30 ix[row] = col;
28 break; 31 break;
29 } 32 }
@@ -34,24 +37,25 @@ static void buildixvector(int *ix, col_t *mstar, int nrows, int ncols)
34 37
35/********************************************************/ 38/********************************************************/
36 39
37static void step2a(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 40static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin);
38static void step2b(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 41static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin);
39static void step3 (int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 42static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin);
40static void step4 (int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin, int row, int col); 43static void step4(int *ix, float *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);
41static void step5 (int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin); 44static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin);
42 45
43static void ixoptimal(int *ix, float *mdist, int nrows, int ncols) 46static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
44{ 47{
45 float *mdistTemp, *mdistEnd, *columnEnd, value, minValue; 48 float *mdistTemp, *mdistEnd, *columnEnd, value, minValue;
46 int dmin, row, col; 49 int dmin, row, col;
47 col_t ccol,crow, mstar[DIM_FINGER],mprime[DIM_FINGER],nmstar[DIM_FINGER]; 50 col_t ccol, crow;
51 mat_t mstar, mprime, nmstar;
48 52
49 ccol = crow = 0; 53 memset(ccol, 0, sizeof(col_t));
50 memset(mstar, 0, sizeof(mstar)); 54 memset(crow, 0, sizeof(col_t));
51 memset(mprime, 0, sizeof(mprime)); 55 memset(mstar, 0, sizeof(mat_t));
52 memset(nmstar, 0, sizeof(nmstar)); 56 memset(mprime, 0, sizeof(mat_t));
57 memset(nmstar, 0, sizeof(mat_t));
53 58
54
55 /* initialization */ 59 /* initialization */
56 for(row=0; row<nrows; row++) 60 for(row=0; row<nrows; row++)
57 ix[row] = -1; 61 ix[row] = -1;
@@ -86,25 +90,21 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
86 for(row=0; row<nrows; row++) 90 for(row=0; row<nrows; row++)
87 for(col=0; col<ncols; col++) 91 for(col=0; col<ncols; col++)
88 if(mdist[row + nrows*col] == 0) 92 if(mdist[row + nrows*col] == 0)
89 if(!GETBIT(ccol, col)) { 93 if(!GET1(ccol, col)) {
90 SETBIT2(mstar, row, col); 94 SET2(mstar, row, col);
91 SETBIT(ccol, col); 95 SET1(ccol, col);
92 break; 96 break;
93 } 97 }
94 } 98 } else {
95 else /* if(nrows > ncols) */
96 {
97 dmin = ncols; 99 dmin = ncols;
98 100
99 for(col=0; col<ncols; col++) 101 for(col=0; col<ncols; col++) {
100 {
101 /* find the smallest element in the column */ 102 /* find the smallest element in the column */
102 mdistTemp = mdist + nrows*col; 103 mdistTemp = mdist + nrows*col;
103 columnEnd = mdistTemp + nrows; 104 columnEnd = mdistTemp + nrows;
104 105
105 minValue = *mdistTemp++; 106 minValue = *mdistTemp++;
106 while(mdistTemp < columnEnd) 107 while(mdistTemp < columnEnd) {
107 {
108 value = *mdistTemp++; 108 value = *mdistTemp++;
109 if(value < minValue) 109 if(value < minValue)
110 minValue = value; 110 minValue = value;
@@ -120,16 +120,13 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
120 for(col=0; col<ncols; col++) 120 for(col=0; col<ncols; col++)
121 for(row=0; row<nrows; row++) 121 for(row=0; row<nrows; row++)
122 if(mdist[row + nrows*col] == 0) 122 if(mdist[row + nrows*col] == 0)
123 if(!GETBIT(crow, row)) 123 if(!GET1(crow, row)) {
124 { 124 SET2(mstar, row, col);
125 SETBIT2(mstar, row, col); 125 SET1(ccol, col);
126 SETBIT(ccol, col); 126 SET1(crow, row);
127 SETBIT(crow, row);
128 break; 127 break;
129 } 128 }
130 for(row=0; row<nrows; row++) 129 memset(crow, 0, sizeof(col_t));
131 CLEARBIT(crow, row);
132
133 } 130 }
134 131
135 /* move to step 2b */ 132 /* move to step 2b */
@@ -137,42 +134,39 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
137} 134}
138 135
139/********************************************************/ 136/********************************************************/
140static void step2a(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 137static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin)
141{ 138{
142 int col, row; 139 int col, row;
143 140
144 /* cover every column containing a starred zero */ 141 /* cover every column containing a starred zero */
145 for(col=0; col<ncols; col++) { 142 for(col = 0; col < ncols; col++) {
146 for(row=col;row<nrows;row++) { 143 for(row = 0; row < nrows; row++) {
147 if(GETBIT2(mstar, row, col)) { 144 if(GET2(mstar, row, col)) {
148 SETBIT(ccol, col); 145 SET1(ccol, col);
149 break; 146 break;
150 } 147 }
151 } 148 }
152 } 149 }
153 150
154 /* move to step 3 */ 151 /* move to step 3 */
155 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 152 step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
156} 153}
157 154
158/********************************************************/ 155/********************************************************/
159static void step2b(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 156static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin)
160{ 157{
161 int col, ncc; 158 int col, ncc;
162 159
163 /* count covered columns */ 160 /* count covered columns */
164 ncc = 0; 161 ncc = 0;
165 for(col=0; col<ncols; col++) 162 for(col=0; col<ncols; col++)
166 if(GETBIT(ccol, col)) 163 if(GET1(ccol, col))
167 ncc++; 164 ncc++;
168 165
169 if(ncc == dmin) 166 if(ncc == dmin) {
170 {
171 /* algorithm finished */ 167 /* algorithm finished */
172 buildixvector(ix, mstar, nrows, ncols); 168 buildixvector(ix, mstar, nrows, ncols);
173 } 169 } else {
174 else
175 {
176 /* move to step 3 */ 170 /* move to step 3 */
177 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 171 step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
178 } 172 }
@@ -180,39 +174,34 @@ static void step2b(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mp
180} 174}
181 175
182/********************************************************/ 176/********************************************************/
183static void step3(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 177static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin)
184{ 178{
185 bool zerosFound; 179 bool zerosFound;
186 int row, col, cstar; 180 int row, col, cstar;
187 181
188 zerosFound = 1; 182 zerosFound = 1;
189 while(zerosFound) 183 while(zerosFound) {
190 {
191 zerosFound = 0; 184 zerosFound = 0;
192 for(col=0; col<ncols; col++) 185 for(col=0; col<ncols; col++)
193 if(!GETBIT(ccol,col)) 186 if(!GET1(ccol,col))
194 for(row=0; row<nrows; row++) 187 for(row=0; row<nrows; row++)
195 if((!GETBIT(crow,row)) && (mdist[row + nrows*col] == 0)) 188 if((!GET1(crow, row)) && (mdist[row + nrows*col] == 0)) {
196 {
197 /* prime zero */ 189 /* prime zero */
198 SETBIT2(mprime, row, col); 190 SET2(mprime, row, col);
199 191
200 /* find starred zero in current row */ 192 /* find starred zero in current row */
201 for(cstar=0; cstar<ncols; cstar++) 193 for(cstar=0; cstar<ncols; cstar++)
202 if(GETBIT2(mstar, row, cstar)) 194 if(GET2(mstar, row, cstar))
203 break; 195 break;
204 196
205 if(cstar == ncols) /* no starred zero found */ 197 if(cstar == ncols) { /* no starred zero found */
206 {
207 /* move to step 4 */ 198 /* move to step 4 */
208 step4(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin, row, col); 199 step4(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin, row, col);
209 return; 200 return;
210 } 201 } else {
211 else 202 SET1(crow, row);
212 { 203 CLEAR1(ccol, cstar);
213 SETBIT(crow, row); 204 zerosFound = 1;
214 CLEARBIT(ccol,cstar);
215 zerosFound = 1;
216 break; 205 break;
217 } 206 }
218 } 207 }
@@ -223,80 +212,83 @@ static void step3(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mpr
223} 212}
224 213
225/********************************************************/ 214/********************************************************/
226static void step4(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin, int row, int col) 215static void step4(int *ix, float *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)
227{ 216{
228 int n, rstar, cstar, primeRow, primeCol; 217 int n, rstar, cstar, primeRow, primeCol;
229 218
230 /* generate temporary copy of mstar */ 219 /* generate temporary copy of mstar */
231 memcpy(nmstar, mstar, sizeof(mstar)); 220 memcpy(nmstar, mstar, sizeof(mat_t));
232 221
233 /* star current zero */ 222 /* star current zero */
234 SETBIT2(nmstar, row, col); 223 SET2(nmstar, row, col);
235 224
236 /* find starred zero in current column */ 225 /* find starred zero in current column */
237 cstar = col; 226 cstar = col;
238 for(rstar=0; rstar<nrows; rstar++) 227 for(rstar=0; rstar<nrows; rstar++)
239 if(GETBIT2(mstar, rstar, cstar)) 228 if(GET2(mstar, rstar, cstar))
240 break; 229 break;
241 230
242 while(rstar<nrows) 231 while(rstar<nrows) {
243 {
244 /* unstar the starred zero */ 232 /* unstar the starred zero */
245 CLEARBIT2(nmstar, rstar, cstar); 233 CLEAR2(nmstar, rstar, cstar);
246 234
247 /* find primed zero in current row */ 235 /* find primed zero in current row */
248 primeRow = rstar; 236 primeRow = rstar;
249 for(primeCol=0; primeCol<ncols; primeCol++) 237 for(primeCol=0; primeCol<ncols; primeCol++)
250 if(GETBIT2(mprime, primeRow, primeCol)) 238 if(GET2(mprime, primeRow, primeCol))
251 break; 239 break;
252 240
253 /* star the primed zero */ 241 /* star the primed zero */
254 SETBIT2(nmstar, primeRow, primeCol); 242 SET2(nmstar, primeRow, primeCol);
255 243
256 /* find starred zero in current column */ 244 /* find starred zero in current column */
257 cstar = primeCol; 245 cstar = primeCol;
258 for(rstar=0; rstar<nrows; rstar++) 246 for(rstar=0; rstar<nrows; rstar++)
259 if(GETBIT2(mstar, rstar, cstar)) 247 if(GET2(mstar, rstar, cstar))
260 break; 248 break;
261 } 249 }
262 250
263 /* use temporary copy as new mstar */ 251 /* use temporary copy as new mstar */
264 /* delete all primes, uncover all rows */ 252 /* delete all primes, uncover all rows */
265 memset(mprime, 0, sizeof(mprime)); 253 memcpy(mstar, nmstar, sizeof(mat_t));
266 memcpy(mstar, nmstar, sizeof(nmstar)); 254 memset(mprime, 0, sizeof(mat_t));
267 crow = 0; 255 memset(crow, 0, sizeof(col_t));
268 256
269 /* move to step 2a */ 257 /* move to step 2a */
270 step2a(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); 258 step2a(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
271} 259}
272 260
273/********************************************************/ 261/********************************************************/
274static void step5(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin) 262static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin)
275{ 263{
276 float h, value; 264 float h = 0, value;
277 int row, col; 265 int row, col, found = 0;
278 266
279 /* find smallest uncovered element h */ 267 /* find smallest uncovered element h */
280 h = BIG_VALUE;
281 for(row=0; row<nrows; row++) 268 for(row=0; row<nrows; row++)
282 if(!GETBIT(crow, row)) 269 if(!GET1(crow, row))
283 for(col=0; col<ncols; col++) 270 for(col=0; col<ncols; col++)
284 if(!GETBIT(ccol,col)) 271 if(!GET1(ccol,col)) {
285 {
286 value = mdist[row + nrows*col]; 272 value = mdist[row + nrows*col];
287 if(value < h) 273 if(!found || value < h) {
288 h = value; 274 h = value;
275 found = 1;
276 }
289 } 277 }
290 278
279 /* where to go if nothing uncovered? */
280 if (!found)
281 return;
282
291 /* add h to each covered row */ 283 /* add h to each covered row */
292 for(row=0; row<nrows; row++) 284 for(row=0; row<nrows; row++)
293 if(GETBIT(crow, row)) 285 if(GET1(crow, row))
294 for(col=0; col<ncols; col++) 286 for(col=0; col<ncols; col++)
295 mdist[row + nrows*col] += h; 287 mdist[row + nrows*col] += h;
296 288
297 /* subtract h from each uncovered column */ 289 /* subtract h from each uncovered column */
298 for(col=0; col<ncols; col++) 290 for(col=0; col<ncols; col++)
299 if(!GETBIT(ccol,col)) 291 if(!GET1(ccol,col))
300 for(row=0; row<nrows; row++) 292 for(row=0; row<nrows; row++)
301 mdist[row + nrows*col] -= h; 293 mdist[row + nrows*col] -= h;
302 294
@@ -308,6 +300,13 @@ static void step5(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mpr
308 300
309void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol) 301void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol)
310{ 302{
303 int i;
304 float max = 1;
305 for (i = 0; i < nrow * ncol; i++)
306 if (A[i] > max)
307 max = A[i];
308 for (i = 0; i < nrow * ncol; i++)
309 A[i] /= max;
311 ixoptimal(ix, A, nrow, ncol); 310 ixoptimal(ix, A, nrow, ncol);
312} 311}
313 312
diff --git a/match/match.h b/match/match.h
index 03bf600..8936de4 100644
--- a/match/match.h
+++ b/match/match.h
@@ -13,10 +13,6 @@
13#define MIN(a, b) ((a) < (b) ? (a) : (b)) 13#define MIN(a, b) ((a) < (b) ? (a) : (b))
14#define MAX(a, b) ((a) < (b) ? (b) : (a)) 14#define MAX(a, b) ((a) < (b) ? (b) : (a))
15 15
16#define GETBIT(m, x) ((m>>(x))&1U)
17#define SETBIT(m, x) (m|=(1U<<(x)))
18#define CLEARBIT(m, x) (m&=~(1U<<(x)))
19
20typedef int bool; 16typedef int bool;
21 17
22//////////////////////////////////////////////////////// 18////////////////////////////////////////////////////////
diff --git a/match/test.c b/match/test.c
index ad39370..1f535d1 100644
--- a/match/test.c
+++ b/match/test.c
@@ -24,8 +24,45 @@ static void test1()
24 942941.000000, 24 942941.000000,
25 462820.000000, 25 462820.000000,
26 }; 26 };
27 int index[DIM_FINGER]; 27 int index[DIM_FINGER], i;
28 match_fingers(index, A, 4, 4); 28 match_fingers(index, A, 4, 4);
29 for (i = 0; i < 4; i++)
30 printf("match[%d] = %d\n", i, index[i]);
31}
32
33static void test2()
34{
35 float A[]={
36 0.000000,
37 4534330.000000,
38 22653552.000000,
39 12252500.000000,
40 685352.000000,
41 4534330.000000,
42 0.000000,
43 9619317.000000,
44 28409530.000000,
45 6710170.000000,
46 22653552.000000,
47 9619317.000000,
48 0.000000,
49 47015292.000000,
50 29788572.000000,
51 2809040.000000,
52 10428866.000000,
53 38615920.000000,
54 17732500.000000,
55 719528.000000,
56 12113945.000000,
57 28196220.000000,
58 46778656.000000,
59 405.000000,
60 14175493.000000,
61 };
62 int index[DIM_FINGER], i;
63 match_fingers(index, A, 5, 5);
64 for (i = 0; i < 5; i++)
65 printf("match[%d] = %d\n", i, index[i]);
29} 66}
30 67
31static void speed1() 68static void speed1()
@@ -65,7 +102,12 @@ static void speed1()
65 102
66int main(int argc,char* argv[]) 103int main(int argc,char* argv[])
67{ 104{
105 printf("test1\n");
68 test1(); 106 test1();
107 printf("test2\n");
108 test2();
109 printf("speed1\n");
69 speed1(); 110 speed1();
111 printf("done\n");
70 return 0; 112 return 0;
71} 113}
generated by cgit v1.2.3 (git 2.39.1) at 2026-09-20 19:45:08 +0000