1 /*****************************************************************************
2 *
3 * mtdev - Multitouch Protocol Translation Library (MIT license)
4 *
5 * Copyright (C) 2010 Henrik Rydberg <rydberg@euromail.se>
6 * Copyright (C) 2010 Canonical Ltd.
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a
9 * copy of this software and associated documentation files (the "Software"),
10 * to deal in the Software without restriction, including without limitation
11 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
12 * and/or sell copies of the Software, and to permit persons to whom the
13 * Software is furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice (including the next
16 * paragraph) shall be included in all copies or substantial portions of the
17 * Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
22 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25 * DEALINGS IN THE SOFTWARE.
26 *
27 ****************************************************************************/
28
29 #include <../src/common.h>
30 #include <stdio.h>
31 #include <stdlib.h>
32 #include <time.h>
33
34 /*
35 * Combinatorial formulation
36 *
37 * x_ij = 1 if slot i and contact j are connected, zero otherwise
38 *
39 * sum_i x_ij <= 1 for all j; each contact picks at most one slot
40 *
41 * sum_j x_ij <= 1 for all i; each slot is picked by at most one contact
42 *
43 * sum_ij x_ij == min(nslot, npos); assign every contact possible
44 *
45 * Arrange x_ij as a bitmask; x_00 x_01 x_02.. x_10 x_11 x_12...
46 *
47 * Up to five slots, this is readily enumerable.
48 */
49
50 #define SLOT_MAX 5
51 #define SLOT_CNT (SLOT_MAX + 1)
52
illegal(int nslot,int npos,unsigned x)53 static int illegal(int nslot, int npos, unsigned x)
54 {
55 int i, j, sum;
56
57 for (j = 0; j < npos; j++) {
58 sum = 0;
59 for (i = 0; i < nslot; i++)
60 sum += GETBIT(x, i * npos + j);
61 if (sum > 1)
62 return 1;
63 }
64 for (i = 0; i < nslot; i++) {
65 sum = 0;
66 for (j = 0; j < npos; j++)
67 sum += GETBIT(x, i * npos + j);
68 if (sum > 1)
69 return 1;
70 }
71
72 sum = bitcount(x);
73 return sum != minval(nslot, npos);
74 }
75
get_slots(int * slots,int nslot,int npos,unsigned x)76 static void get_slots(int *slots, int nslot, int npos, unsigned x)
77 {
78 int i;
79
80 memset(slots, -1, sizeof(slots[0]) * npos);
81 for (i = 0; i < nslot * npos; i++)
82 if (GETBIT(x, i))
83 slots[i % npos] = i / npos;
84 for (i = 0; i < npos; i++)
85 if (slots[i] < 0)
86 slots[i] = nslot++;
87 }
88
generate_assignments(int nslot,int npos)89 static int generate_assignments(int nslot, int npos)
90 {
91 static int ncol;
92 unsigned x, nx = BITMASK(nslot * npos);
93 int slots[SLOT_MAX];
94 int i, n = 0;
95
96 for (x = 0; x < nx; x++) {
97 if (illegal(nslot, npos, x))
98 continue;
99 for (i = 0; i < nslot * npos; i++) {
100 if (GETBIT(x, i)) {
101 if (ncol++ % 16 == 0)
102 printf("\n\t%d,", i);
103 else
104 printf(" %d,", i);
105 n++;
106 }
107 }
108 get_slots(slots, nslot, npos, x);
109 for (i = 0; i < npos; i++) {
110 if (ncol++ % 16 == 0)
111 printf("\n\t%d,", slots[i]);
112 else
113 printf(" %d,", slots[i]);
114 n++;
115 }
116 }
117
118 return n;
119 }
120
main(int argc,char * argv[])121 int main(int argc, char *argv[])
122 {
123 int ix[SLOT_CNT][SLOT_CNT], nix = 0;
124 int eslot, i, j;
125
126 if (argc < 2) {
127 fprintf(stderr, "usage: %s <num_slots>\n", argv[0]);
128 return 1;
129 }
130
131 eslot = atoi(argv[1]) + 1;
132 if (eslot > SLOT_CNT) {
133 fprintf(stderr, "allowed slot range: 2 - %d\n", SLOT_MAX);
134 return 1;
135 }
136
137 printf("\n/* generated by mtdev-kernel - do not edit */\n");
138 printf("static const u8 match_data[] = {");
139 for (i = 0; i < eslot; i++) {
140 for (j = 0; j < eslot; j++) {
141 ix[i][j] = nix;
142 nix += generate_assignments(i, j);
143 }
144 }
145 printf("\n};\n");
146
147 printf("\n/* generated by mtdev-kernel - do not edit */\n");
148 printf("static const int match_index[][%d] = {\n", eslot);
149 for (i = 0; i < eslot; i++) {
150 printf("\t{");
151 for (j = 0; j < eslot; j++)
152 printf(" %d%s", ix[i][j], j < eslot - 1 ? "," : "");
153 printf(" },\n");
154 }
155 printf("\t{ %d }\n", nix);
156 printf("};\n");
157
158 return 0;
159 }
160