From e9dcbeaba956e84d1e591e9b520f3b7bb4fa6354 Mon Sep 17 00:00:00 2001 From: Henrik Rydberg Date: Sat, 20 Mar 2010 14:18:16 +0100 Subject: 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 --- match/match.c | 35 +++++++++------------- match/match.h | 2 +- match/test.c | 96 +++++++++++++++++++++++++++++------------------------------ src/state.c | 21 ++++++++++--- 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; -- cgit v1.2.3