From 2d96d426e063a4c2c33cabf9c6ebf570db1fcf1b Mon Sep 17 00:00:00 2001
From: Henrik Rydberg <rydberg@euromail.se>
Date: Sat, 8 Nov 2008 22:00:50 +0100
Subject: culprit: step2a row should start at zero

plus cleanup

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>
---
 match/match.c | 189 +++++++++++++++++++++++++++++-----------------------------
 match/match.h |   4 --
 match/test.c  |  44 +++++++++++++-
 3 files changed, 137 insertions(+), 100 deletions(-)

(limited to 'match')

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 @@
  * modified by Henrik Rydberg (2008)
  */
 
-const float BIG_VALUE = 1e20;
+typedef unsigned short col_t[1];
+typedef unsigned short mat_t[DIM_FINGER];
 
-typedef unsigned short col_t;
+#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 GETBIT2(m, row, col) ((m[col]>>(row))&1U)
-#define SETBIT2(m, row, col) (m[col]|=(1U<<(row)))
-#define CLEARBIT2(m, row, col) (m[col]&=~(1U<<(row)))
+#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, col_t *mstar, int nrows, int ncols)
+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 (GETBIT2(mstar, row, col)) {
+			if (GET2(mstar, row, col)) {
 				ix[row] = col;
 				break;
 			}
@@ -34,24 +37,25 @@ static void buildixvector(int *ix, col_t *mstar, int nrows, int ncols)
 
 /********************************************************/
 
-static 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);
-static 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);
-static 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);
-static 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);
-static 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);
+static 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);
+static 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);
+static 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);
+static 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);
+static 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);
 
 static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
 {
 	float *mdistTemp, *mdistEnd, *columnEnd, value, minValue;
 	int dmin, row, col;
-	col_t ccol,crow, mstar[DIM_FINGER],mprime[DIM_FINGER],nmstar[DIM_FINGER];
+	col_t ccol, crow;
+	mat_t mstar, mprime, nmstar;
 
-	ccol = crow = 0;
-	memset(mstar, 0, sizeof(mstar));
-	memset(mprime, 0, sizeof(mprime));
-	memset(nmstar, 0, sizeof(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;
@@ -86,25 +90,21 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
 		for(row=0; row<nrows; row++)
 			for(col=0; col<ncols; col++)
 				if(mdist[row + nrows*col] == 0)
-					if(!GETBIT(ccol, col)) {
-						SETBIT2(mstar, row, col);
-						SETBIT(ccol, col);
+					if(!GET1(ccol, col)) {
+						SET2(mstar, row, col);
+						SET1(ccol, col);
 						break;
 					}
-	}
-	else /* if(nrows > ncols) */
-	{
+	} else {
 		dmin = ncols;
 		
-		for(col=0; col<ncols; col++)
-		{
+		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)
-			{
+			while(mdistTemp < columnEnd) {
 				value = *mdistTemp++;
 				if(value < minValue)
 					minValue = value;
@@ -120,16 +120,13 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
 		for(col=0; col<ncols; col++)
 			for(row=0; row<nrows; row++)
 				if(mdist[row + nrows*col] == 0)
-					if(!GETBIT(crow, row))
-					{
-						SETBIT2(mstar, row, col);
-						SETBIT(ccol, col);
-						SETBIT(crow, row);
+					if(!GET1(crow, row)) {
+						SET2(mstar, row, col);
+						SET1(ccol, col);
+						SET1(crow, row);
 						break;
 					}
-		for(row=0; row<nrows; row++)
-			CLEARBIT(crow, row);
-		
+		memset(crow, 0, sizeof(col_t));
 	}	
 	
 	/* move to step 2b */
@@ -137,42 +134,39 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
 }
 
 /********************************************************/
-static 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)
+static 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)
 {
 	int col, row;
 
 	/* cover every column containing a starred zero */
-	for(col=0; col<ncols; col++) {
-		for(row=col;row<nrows;row++) {
-			if(GETBIT2(mstar, row, col)) {
-				SETBIT(ccol, col);
+	for(col = 0; col < ncols; col++) {
+		for(row = 0; row < nrows; row++) {
+			if(GET2(mstar, row, col)) {
+				SET1(ccol, col);
 				break;
 			}
 		}	
 	}
-
+	
 	/* move to step 3 */
 	step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
 }
 
 /********************************************************/
-static 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)
+static 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)
 {
 	int col, ncc;
 	
 	/* count covered columns */
 	ncc = 0;
 	for(col=0; col<ncols; col++)
-		if(GETBIT(ccol, col))
+		if(GET1(ccol, col))
 			ncc++;
-			
-	if(ncc == dmin)
-	{
+	
+	if(ncc == dmin) {
 		/* algorithm finished */
 		buildixvector(ix, mstar, nrows, ncols);
-	}
-	else
-	{
+	} else {
 		/* move to step 3 */
 		step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin);
 	}
@@ -180,39 +174,34 @@ static void step2b(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mp
 }
 
 /********************************************************/
-static 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)
+static 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)
 {
 	bool zerosFound;
 	int row, col, cstar;
 
 	zerosFound = 1;
-	while(zerosFound)
-	{
+	while(zerosFound) {
 		zerosFound = 0;		
 		for(col=0; col<ncols; col++)
-			if(!GETBIT(ccol,col))
+			if(!GET1(ccol,col))
 				for(row=0; row<nrows; row++)
-					if((!GETBIT(crow,row)) && (mdist[row + nrows*col] == 0))
-					{
+					if((!GET1(crow, row)) && (mdist[row + nrows*col] == 0)) {
 						/* prime zero */
-						SETBIT2(mprime, row, col);
+						SET2(mprime, row, col);
 						
 						/* find starred zero in current row */
 						for(cstar=0; cstar<ncols; cstar++)
-							if(GETBIT2(mstar, row, cstar))
+							if(GET2(mstar, row, cstar))
 								break;
 						
-						if(cstar == ncols) /* no starred zero found */
-						{
+						if(cstar == ncols) { /* no starred zero found */
 							/* move to step 4 */
 							step4(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin, row, col);
 							return;
-						}
-						else
-						{
-							SETBIT(crow, row);
-							CLEARBIT(ccol,cstar);
-							zerosFound              = 1;
+						} else {
+							SET1(crow, row);
+							CLEAR1(ccol, cstar);
+							zerosFound = 1;
 							break;
 						}
 					}
@@ -223,80 +212,83 @@ static void step3(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mpr
 }
 
 /********************************************************/
-static 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)
+static 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)
 {	
 	int n, rstar, cstar, primeRow, primeCol;
-	
+
 	/* generate temporary copy of mstar */
-	memcpy(nmstar, mstar, sizeof(mstar));
+	memcpy(nmstar, mstar, sizeof(mat_t));
 	
 	/* star current zero */
-	SETBIT2(nmstar, row, col);
+	SET2(nmstar, row, col);
 
 	/* find starred zero in current column */
 	cstar = col;
 	for(rstar=0; rstar<nrows; rstar++)
-		if(GETBIT2(mstar, rstar, cstar))
+		if(GET2(mstar, rstar, cstar))
 			break;
 
-	while(rstar<nrows)
-	{
+	while(rstar<nrows) {
 		/* unstar the starred zero */
-		CLEARBIT2(nmstar, rstar, cstar);
-	
+		CLEAR2(nmstar, rstar, cstar);
+		
 		/* find primed zero in current row */
 		primeRow = rstar;
 		for(primeCol=0; primeCol<ncols; primeCol++)
-			if(GETBIT2(mprime, primeRow, primeCol))
+			if(GET2(mprime, primeRow, primeCol))
 				break;
-								
+		
 		/* star the primed zero */
-		SETBIT2(nmstar, primeRow, primeCol);
-	
+		SET2(nmstar, primeRow, primeCol);
+		
 		/* find starred zero in current column */
 		cstar = primeCol;
 		for(rstar=0; rstar<nrows; rstar++)
-			if(GETBIT2(mstar, rstar, cstar))
+			if(GET2(mstar, rstar, cstar))
 				break;
 	}	
-
+	
 	/* use temporary copy as new mstar */
 	/* delete all primes, uncover all rows */
-	memset(mprime, 0, sizeof(mprime));
-	memcpy(mstar, nmstar, sizeof(nmstar));
-	crow = 0;
+	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, float *mdist, col_t *mstar, col_t *nmstar, col_t *mprime, col_t ccol, col_t crow, int nrows, int ncols, int dmin)
+static 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)
 {
-	float h, value;
-	int row, col;
-	
+	float h = 0, value;
+	int row, col, found = 0;
+
 	/* find smallest uncovered element h */
-	h = BIG_VALUE;
 	for(row=0; row<nrows; row++)
-		if(!GETBIT(crow, row))
+		if(!GET1(crow, row))
 			for(col=0; col<ncols; col++)
-				if(!GETBIT(ccol,col))
-				{
+				if(!GET1(ccol,col)) {
 					value = mdist[row + nrows*col];
-					if(value < h)
+					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(GETBIT(crow, row))
+		if(GET1(crow, row))
 			for(col=0; col<ncols; col++)
 				mdist[row + nrows*col] += h;
 	
 	/* subtract h from each uncovered column */
 	for(col=0; col<ncols; col++)
-		if(!GETBIT(ccol,col))
+		if(!GET1(ccol,col))
 			for(row=0; row<nrows; row++)
 				mdist[row + nrows*col] -= h;
 	
@@ -308,6 +300,13 @@ static void step5(int *ix, float *mdist, col_t *mstar, col_t *nmstar, col_t *mpr
 
 void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol)
 {
+	int i;
+	float max = 1;
+	for (i = 0; i < nrow * ncol; i++)
+		if (A[i] > max)
+			max = A[i];
+	for (i = 0; i < nrow * ncol; i++)
+		A[i] /= max;
 	ixoptimal(ix, A, nrow, ncol);
 }
 
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 @@
 #define MIN(a, b) ((a) < (b) ? (a) : (b))
 #define MAX(a, b) ((a) < (b) ? (b) : (a))
 
-#define GETBIT(m, x) ((m>>(x))&1U)
-#define SETBIT(m, x) (m|=(1U<<(x)))
-#define CLEARBIT(m, x) (m&=~(1U<<(x)))
-
 typedef int bool;
 
 ////////////////////////////////////////////////////////
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()
 		942941.000000,
 		462820.000000,
 	};
-	int index[DIM_FINGER];
+	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()
+{
+	float A[]={
+		0.000000,
+		4534330.000000,
+		22653552.000000,
+		12252500.000000,
+		685352.000000,
+		4534330.000000,
+		0.000000,
+		9619317.000000,
+		28409530.000000,
+		6710170.000000,
+		22653552.000000,
+		9619317.000000,
+		0.000000,
+		47015292.000000,
+		29788572.000000,
+		2809040.000000,
+		10428866.000000,
+		38615920.000000,
+		17732500.000000,
+		719528.000000,
+		12113945.000000,
+		28196220.000000,
+		46778656.000000,
+		405.000000,
+		14175493.000000,
+	};
+	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()
@@ -65,7 +102,12 @@ static void speed1()
 
 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