Matcher: convert distance matrix to integer

In order to reduce the requirements on the cpu environment running
the matcher, the floating-point operations are converted to integer.
Care is taken as to not overflow the distance matrix.

Signed-off-by: Henrik Rydberg <rydberg@euromail.se>

4 files changed, 80 insertions, 74 deletions

diff --git a/match/match.c b/match/match.c
index a3f4deb..4cb4495 100644
--- a/match/match.c
+++ b/match/match.c
@@ -64,25 +64,25 @@ static void buildixvector(int *ix, mat_t mstar, int nrows, int ncols)
 
 /********************************************************/
 
-static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
+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, float *mdist, mat_t mstar, mat_t nmstar,
+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, float *mdist, mat_t mstar, mat_t nmstar,
+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, float *mdist, mat_t mstar, mat_t nmstar,
+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, float *mdist, mat_t mstar, mat_t nmstar,
+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, float *mdist, int nrows, int ncols)
+static void ixoptimal(int *ix, int *mdist, int nrows, int ncols)
 {
-	float *mdistTemp, *mdistEnd, *columnEnd, value, minValue;
+	int *mdistTemp, *mdistEnd, *columnEnd, value, minValue;
 	int dmin, row, col;
 	col_t ccol, crow;
 	mat_t mstar, mprime, nmstar;
@@ -181,7 +181,7 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols)
 }
 
 /********************************************************/
-static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
+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)
 {
@@ -204,7 +204,7 @@ static void step2a(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
 }
 
 /********************************************************/
-static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
+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)
 {
@@ -229,7 +229,7 @@ static void step2b(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
 }
 
 /********************************************************/
-static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
+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)
 {
@@ -279,7 +279,7 @@ static void step3(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
 }
 
 /********************************************************/
-static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
+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)
 {
@@ -330,11 +330,11 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
 }
 
 /********************************************************/
-static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
+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)
 {
-	float h = 0, value;
+	int h = 0, value;
 	int row, col, found = 0;
 
 	/* find smallest uncovered element h */
@@ -378,15 +378,8 @@ static void step5(int *ix, float *mdist, mat_t mstar, mat_t nmstar,
 	      dmin);
 }
 
-void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol)
+void match_fingers(int ix[DIM_FINGER], int 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 0c4274e..6420b00 100644
--- a/match/match.h
+++ b/match/match.h
@@ -34,7 +34,7 @@
 #define MIN(a, b) ((a) < (b) ? (a) : (b))
 #define MAX(a, b) ((a) < (b) ? (b) : (a))
 
-void match_fingers(int index[DIM_FINGER], float A[DIM2_FINGER],
+void match_fingers(int index[DIM_FINGER], int A[DIM2_FINGER],
 		   int nrow, int ncol);
 
 #endif
diff --git a/match/test.c b/match/test.c
index 192f969..f9f2a27 100644
--- a/match/test.c
+++ b/match/test.c
@@ -27,23 +27,23 @@
 
 static void test1()
 {
-	float A[] = {
-		1013.000000,
-		3030660.000000,
-		3559354.000000,
-		12505925.000000,
-		19008450.000000,
-		6946421.000000,
-		6118613.000000,
-		698020.000000,
-		3021800.000000,
-		1017.000000,
-		37573.000000,
-		3242018.000000,
-		8152794.000000,
-		1266053.000000,
-		942941.000000,
-		462820.000000,
+	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);
@@ -53,32 +53,32 @@ static void test1()
 
 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 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);
@@ -89,11 +89,11 @@ static void test2()
 static void speed1()
 {
 	/* column-by-column matrix */
-	float A[DIM2_FINGER];
-	float x1[DIM_FINGER] = { 1, 5, 2, 3, 4, 5, 6, 7, 8 };
-	float y1[DIM_FINGER] = { 1, 5, 2, 3, 4, 5.1, 6, 7, 8 };
-	float x2[DIM_FINGER] = { 1.1, 3, 2, 4, 5, 6, 7, 8 };
-	float y2[DIM_FINGER] = { 1, 3, 2, 4, 5, 6, 7, 8 };
+	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;
diff --git a/src/state.c b/src/state.c
index 5387828..895d096 100644
--- a/src/state.c
+++ b/src/state.c
@@ -36,10 +36,23 @@ static int fincmp(const void *a, const void *b)
 	return ((struct FingerState *)a)->id - ((struct FingerState *)b)->id;
 }
 
-inline float dist2(const struct FingerData *a, const struct FingerData *b)
+/* seander@cs.stanford.edu */
+inline unsigned abs32(int x)
 {
-	float dx = a->position_x - b->position_x;
-	float dy = a->position_y - b->position_y;
+	int const m = x >> 31;
+	return (x + m) ^ m;
+}
+
+inline int abs15(int x)
+{
+	return 32767 & abs32(x);
+}
+
+/* abslute scale is assumed to fit in 15 bits */
+inline int dist2(const struct FingerData *a, const struct FingerData *b)
+{
+	int dx = abs15(a->position_x - b->position_x);
+	int dy = abs15(a->position_y - b->position_y);
 
 	return dx * dx + dy * dy;
 }
@@ -71,7 +84,7 @@ void modify_state(struct State *s,
 		  const struct HWData *hw,
 		  const struct Capabilities *caps)
 {
-	float A[DIM2_FINGER], *row;
+	int A[DIM2_FINGER], *row;
 	int sid[DIM_FINGER], hw2s[DIM_FINGER];
 	int id, sk, hwk;