diff options
author | Henrik Rydberg <rydberg@alnilam.(none)> | 2010-02-01 22:00:55 +0100 |
---|---|---|
committer | Henrik Rydberg <rydberg@alnilam.(none)> | 2010-02-01 22:00:55 +0100 |
commit | 30869603dc5d36ad2d82cff82900c7e05a4b35c1 (patch) | |
tree | 9e22c50cd9f6c8a618005d053124640bf9172a32 | |
parent | d1117c8645fc4c0e2ccf0873fcf692c3ffa8b139 (diff) | |
download | xorg-input-kobomultitouch-30869603dc5d36ad2d82cff82900c7e05a4b35c1.tar.gz xorg-input-kobomultitouch-30869603dc5d36ad2d82cff82900c7e05a4b35c1.tar.bz2 xorg-input-kobomultitouch-30869603dc5d36ad2d82cff82900c7e05a4b35c1.zip |
janitor: match: stick to kernel-style formatting
-rw-r--r-- | match/match.c | 283 | ||||
-rw-r--r-- | match/match.h | 6 | ||||
-rw-r--r-- | match/test.c | 14 |
3 files changed, 174 insertions, 129 deletions
diff --git a/match/match.c b/match/match.c index ebeadcd..dbb14ba 100644 --- a/match/match.c +++ b/match/match.c @@ -38,13 +38,13 @@ typedef unsigned short col_t[1]; typedef unsigned short mat_t[DIM_FINGER]; -#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 GET1(m, x) ((m[0] >> (x)) & 1U) +#define SET1(m, x) (m[0] |= (1U << (x))) +#define CLEAR1(m, x) (m[0] &= ~(1U << (x))) -#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))) +#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))) /********************************************************/ @@ -64,11 +64,21 @@ 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, 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 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) { @@ -84,162 +94,194 @@ static void ixoptimal(int *ix, float *mdist, int nrows, int ncols) memset(nmstar, 0, sizeof(mat_t)); /* initialization */ - for(row=0; row<nrows; row++) + for (row = 0; row < nrows; row++) ix[row] = -1; mdistEnd = mdist + nrows * ncols; /* preliminary steps */ - if(nrows <= ncols) { + if (nrows <= ncols) { dmin = nrows; - for(row=0; row<nrows; row++) { + for (row = 0; row < nrows; row++) { /* find the smallest element in the row */ mdistTemp = mdist + row; minValue = *mdistTemp; mdistTemp += nrows; - while(mdistTemp < mdistEnd) { + while (mdistTemp < mdistEnd) { value = *mdistTemp; - if(value < minValue) + if (value < minValue) minValue = value; mdistTemp += nrows; } - /* subtract the smallest element from each element of the row */ + /* subtract the smallest element from each element + of the row */ mdistTemp = mdist + row; - while(mdistTemp < mdistEnd) { + while (mdistTemp < mdistEnd) { *mdistTemp -= minValue; mdistTemp += nrows; } } /* Steps 1 and 2a */ - for(row=0; row<nrows; row++) - for(col=0; col<ncols; col++) - if(mdist[row + nrows*col] == 0) - if(!GET1(ccol, col)) { - SET2(mstar, row, col); - SET1(ccol, col); - break; - } + for (row = 0; row < nrows; row++) { + for (col = 0; col < ncols; col++) { + if (mdist[row + nrows * col] != 0) + continue; + if (GET1(ccol, col)) + continue; + SET2(mstar, row, col); + SET1(ccol, col); + break; + } + } } 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; + mdistTemp = mdist + nrows*col; + columnEnd = mdistTemp + nrows; minValue = *mdistTemp++; - while(mdistTemp < columnEnd) { + while (mdistTemp < columnEnd) { value = *mdistTemp++; - if(value < minValue) + if (value < minValue) minValue = value; } - /* subtract the smallest element from each element of the column */ + /* subtract the smallest element from each element + of the column */ mdistTemp = mdist + nrows*col; - while(mdistTemp < columnEnd) + while (mdistTemp < columnEnd) *mdistTemp++ -= minValue; } /* Steps 1 and 2a */ - for(col=0; col<ncols; col++) - for(row=0; row<nrows; row++) - if(mdist[row + nrows*col] == 0) - if(!GET1(crow, row)) { - SET2(mstar, row, col); - SET1(ccol, col); - SET1(crow, row); - break; - } + for (col = 0; col < ncols; col++) { + for (row = 0; row < nrows; row++) { + if (mdist[row + nrows * col] != 0) + continue; + if (GET1(crow, row)) + continue; + SET2(mstar, row, col); + SET1(ccol, col); + SET1(crow, row); + break; + } + } memset(crow, 0, sizeof(col_t)); } /* move to step 2b */ - step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); + step2b(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + 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 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 = 0; row < nrows; row++) { - if(GET2(mstar, row, col)) { - SET1(ccol, col); - break; - } + for (col = 0; col < ncols; col++) { + for (row = 0; row < nrows; row++) { + if (!GET2(mstar, row, col)) + continue; + SET1(ccol, col); + break; } } /* move to step 3 */ - step2b(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); + step2b(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + 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 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(GET1(ccol, col)) + for (col = 0; col < ncols; col++) + if (GET1(ccol, col)) ncc++; - if(ncc == dmin) { + if (ncc == dmin) { /* algorithm finished */ buildixvector(ix, mstar, nrows, ncols); } else { /* move to step 3 */ - step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); + step3(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + 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 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 zerosFound; int row, col, cstar; zerosFound = 1; - while(zerosFound) { + while (zerosFound) { zerosFound = 0; - for(col=0; col<ncols; col++) - if(!GET1(ccol,col)) - for(row=0; row<nrows; row++) - if((!GET1(crow, row)) && (mdist[row + nrows*col] == 0)) { - /* prime zero */ - SET2(mprime, row, col); - - /* find starred zero in current row */ - for(cstar=0; cstar<ncols; cstar++) - if(GET2(mstar, row, cstar)) - break; - - 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 { - SET1(crow, row); - CLEAR1(ccol, cstar); - zerosFound = 1; - break; - } - } + for (col = 0; col < ncols; col++) { + if (GET1(ccol, col)) + continue; + for (row = 0; row < nrows; row++) { + if (mdist[row + nrows * col] != 0) + continue; + if (GET1(crow, row)) + continue; + + /* prime zero */ + SET2(mprime, row, col); + + /* find starred zero in current row */ + for (cstar = 0; cstar < ncols; cstar++) + if (GET2(mstar, row, cstar)) + break; + + if (cstar == ncols) { /* no starred zero */ + /* move to step 4 */ + step4(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + dmin, row, col); + return; + } else { + SET1(crow, row); + CLEAR1(ccol, cstar); + zerosFound = 1; + break; + } + } + } } /* move to step 5 */ - step5(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); + step5(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + 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 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; @@ -251,18 +293,18 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime /* find starred zero in current column */ cstar = col; - for(rstar=0; rstar<nrows; rstar++) - if(GET2(mstar, rstar, cstar)) + for (rstar = 0; rstar < nrows; rstar++) + if (GET2(mstar, rstar, cstar)) break; - while(rstar<nrows) { + while (rstar < nrows) { /* unstar the starred zero */ CLEAR2(nmstar, rstar, cstar); /* find primed zero in current row */ primeRow = rstar; - for(primeCol=0; primeCol<ncols; primeCol++) - if(GET2(mprime, primeRow, primeCol)) + for (primeCol = 0; primeCol < ncols; primeCol++) + if (GET2(mprime, primeRow, primeCol)) break; /* star the primed zero */ @@ -270,8 +312,8 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime /* find starred zero in current column */ cstar = primeCol; - for(rstar=0; rstar<nrows; rstar++) - if(GET2(mstar, rstar, cstar)) + for (rstar = 0; rstar < nrows; rstar++) + if (GET2(mstar, rstar, cstar)) break; } @@ -282,49 +324,60 @@ static void step4(int *ix, float *mdist, mat_t mstar, mat_t nmstar, mat_t mprime memset(crow, 0, sizeof(col_t)); /* move to step 2a */ - step2a(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); + step2a(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + 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) +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 = 0, value; int row, col, found = 0; /* find smallest uncovered element h */ - for(row=0; row<nrows; row++) - if(!GET1(crow, row)) - for(col=0; col<ncols; col++) - if(!GET1(ccol,col)) { - value = mdist[row + nrows*col]; - if(!found || value < h) { - h = value; - found = 1; - } - } + for (row = 0; row < nrows; row++) { + if (GET1(crow, row)) + continue; + for (col = 0; col < ncols; col++) { + if (GET1(ccol, col)) + continue; + value = mdist[row + nrows * col]; + 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(GET1(crow, row)) - for(col=0; col<ncols; col++) - mdist[row + nrows*col] += h; + for (row = 0; row < nrows; row++) { + if (!GET1(crow, row)) + continue; + for (col = 0; col < ncols; col++) + mdist[row + nrows * col] += h; + } /* subtract h from each uncovered column */ - for(col=0; col<ncols; col++) - if(!GET1(ccol,col)) - for(row=0; row<nrows; row++) - mdist[row + nrows*col] -= h; + for (col = 0; col < ncols; col++) { + if (GET1(ccol, col)) + continue; + for (row = 0; row < nrows; row++) + mdist[row + nrows * col] -= h; + } /* move to step 3 */ - step3(ix, mdist, mstar, nmstar, mprime, ccol, crow, nrows, ncols, dmin); + step3(ix, mdist, mstar, nmstar, + mprime, ccol, crow, nrows, ncols, + dmin); } -//////////////////////////////////////////////////////// - void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol) { int i; @@ -337,5 +390,3 @@ void match_fingers(int ix[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol) ixoptimal(ix, A, nrow, ncol); } -//////////////////////////////////////////////////////// - diff --git a/match/match.h b/match/match.h index 61ac72d..620d046 100644 --- a/match/match.h +++ b/match/match.h @@ -34,13 +34,7 @@ #define MIN(a, b) ((a) < (b) ? (a) : (b)) #define MAX(a, b) ((a) < (b) ? (b) : (a)) -typedef int bool; - -//////////////////////////////////////////////////////// - void match_fingers(int index[DIM_FINGER], float A[DIM2_FINGER], int nrow, int ncol); -//////////////////////////////////////////////////////// - #endif diff --git a/match/test.c b/match/test.c index e60e19a..192f969 100644 --- a/match/test.c +++ b/match/test.c @@ -53,7 +53,7 @@ static void test1() static void test2() { - float A[]={ + float A[] = { 0.000000, 4534330.000000, 22653552.000000, @@ -88,12 +88,12 @@ static void test2() static void speed1() { - // column-by-column matrix + /* 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}; + 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 index[DIM_FINGER]; int n1 = 4; int n2 = 7; @@ -121,7 +121,7 @@ static void speed1() } -int main(int argc,char* argv[]) +int main(int argc, char *argv[]) { printf("test1\n"); test1(); |