diff options
author | Henrik Rydberg <rydberg@euromail.se> | 2010-11-07 17:56:56 +0100 |
---|---|---|
committer | Henrik Rydberg <rydberg@euromail.se> | 2010-11-07 17:56:56 +0100 |
commit | 868f53c8a5684524bc6b1e7cd39aabed56fad9df (patch) | |
tree | 8897e21f91bb1679d7b3f6c5f2779fd7ef12670c /test/mtdev-kernel.c | |
parent | 561af7f537b80f3952ab228bcc992ad75ced280b (diff) | |
download | mtdev-git-868f53c8a5684524bc6b1e7cd39aabed56fad9df.tar.gz |
Generate kernel matcher data
This application generates the matcher tables of the tracking
library in the linux kernel.
Signed-off-by: Henrik Rydberg <rydberg@euromail.se>
Diffstat (limited to 'test/mtdev-kernel.c')
-rw-r--r-- | test/mtdev-kernel.c | 158 |
1 files changed, 158 insertions, 0 deletions
diff --git a/test/mtdev-kernel.c b/test/mtdev-kernel.c new file mode 100644 index 0000000..1f33c3e --- /dev/null +++ b/test/mtdev-kernel.c @@ -0,0 +1,158 @@ +/***************************************************************************** + * + * mtdev - Multitouch Protocol Translation Library (MIT license) + * + * Copyright (C) 2010 Henrik Rydberg <rydberg@euromail.se> + * Copyright (C) 2010 Canonical Ltd. + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + * + ****************************************************************************/ + +#include <../src/common.h> +#include <stdio.h> +#include <time.h> + +/* + * Combinatorial formulation + * + * x_ij = 1 if slot i and contact j are connected, zero otherwise + * + * sum_i x_ij <= 1 for all j; each contact picks at most one slot + * + * sum_j x_ij <= 1 for all i; each slot is picked by at most one contact + * + * sum_ij x_ij == min(nslot, npos); assign every contact possible + * + * Arrange x_ij as a bitmask; x_00 x_01 x_02.. x_10 x_11 x_12... + * + * Up to five slots, this is readily enumerable. + */ + +#define SLOT_MAX 5 +#define SLOT_CNT (SLOT_MAX + 1) + +static int illegal(int nslot, int npos, unsigned x) +{ + int i, j, sum; + + for (j = 0; j < npos; j++) { + sum = 0; + for (i = 0; i < nslot; i++) + sum += GETBIT(x, i * npos + j); + if (sum > 1) + return 1; + } + for (i = 0; i < nslot; i++) { + sum = 0; + for (j = 0; j < npos; j++) + sum += GETBIT(x, i * npos + j); + if (sum > 1) + return 1; + } + + sum = bitcount(x); + return sum != minval(nslot, npos); +} + +static void get_slots(int *slots, int nslot, int npos, unsigned x) +{ + int i; + + memset(slots, -1, sizeof(slots[0]) * npos); + for (i = 0; i < nslot * npos; i++) + if (GETBIT(x, i)) + slots[i % npos] = i / npos; + for (i = 0; i < npos; i++) + if (slots[i] < 0) + slots[i] = nslot++; +} + +static int generate_assignments(int nslot, int npos) +{ + static int ncol; + unsigned x, nx = BITMASK(nslot * npos); + int slots[SLOT_MAX]; + int i, n = 0; + + for (x = 0; x < nx; x++) { + if (illegal(nslot, npos, x)) + continue; + for (i = 0; i < nslot * npos; i++) { + if (GETBIT(x, i)) { + if (ncol++ % 16 == 0) + printf("\n\t%d,", i); + else + printf(" %d,", i); + n++; + } + } + get_slots(slots, nslot, npos, x); + for (i = 0; i < npos; i++) { + if (ncol++ % 16 == 0) + printf("\n\t%d,", slots[i]); + else + printf(" %d,", slots[i]); + n++; + } + } + + return n; +} + +int main(int argc, char *argv[]) +{ + int ix[SLOT_CNT][SLOT_CNT], nix = 0; + int eslot, i, j; + + if (argc < 2) { + fprintf(stderr, "usage: %s <num_slots>\n", argv[0]); + return 1; + } + + eslot = atoi(argv[1]) + 1; + if (eslot > SLOT_CNT) { + fprintf(stderr, "allowed slot range: 2 - %d\n", SLOT_MAX); + return 1; + } + + printf("\n/* generated by mtdev-kernel - do not edit */\n"); + printf("static const u8 match_data[] = {"); + for (i = 0; i < eslot; i++) { + for (j = 0; j < eslot; j++) { + ix[i][j] = nix; + nix += generate_assignments(i, j); + } + } + printf("\n};\n"); + + printf("\n/* generated by mtdev-kernel - do not edit */\n"); + printf("static const int match_index[][%d] = {\n", eslot); + for (i = 0; i < eslot; i++) { + printf("\t{"); + for (j = 0; j < eslot; j++) + printf(" %d%s", ix[i][j], j < eslot - 1 ? "," : ""); + printf(" },\n"); + } + printf("\t{ %d }\n", nix); + printf("};\n"); + + return 0; +} |