1 /*
2
3 Copyright 1990, 1998 The Open Group
4
5 Permission to use, copy, modify, distribute, and sell this software and its
6 documentation for any purpose is hereby granted without fee, provided that
7 the above copyright notice appear in all copies and that both that
8 copyright notice and this permission notice appear in supporting
9 documentation.
10
11 The above copyright notice and this permission notice shall be included
12 in all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
18 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20 OTHER DEALINGS IN THE SOFTWARE.
21
22 Except as contained in this notice, the name of The Open Group shall
23 not be used in advertising or otherwise to promote the sale, use or
24 other dealings in this Software without prior written authorization
25 from The Open Group.
26
27 */
28
29 /* Constructs hash tables for XStringToKeysym and XKeysymToString. */
30
31 #ifdef HAVE_CONFIG_H
32 #include <config.h>
33 #endif
34
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 #include <stdint.h>
39 #include <inttypes.h>
40
41 typedef uint32_t Signature;
42
43 #define KTNUM 4000
44
45 #define XK_VoidSymbol 0xffffff /* Void symbol */
46
47 typedef unsigned long KeySym;
48
49 static struct info {
50 char *name;
51 KeySym val;
52 } info[KTNUM];
53
54 #define MIN_REHASH 15
55 #define MATCHES 10
56
57 static char tab[KTNUM];
58 static unsigned short offsets[KTNUM];
59 static unsigned short indexes[KTNUM];
60 static KeySym values[KTNUM];
61 static int ksnum = 0;
62
63 static int
parse_line(const char * buf,char * key,KeySym * val,char * prefix)64 parse_line(const char *buf, char *key, KeySym *val, char *prefix)
65 {
66 int i;
67 char alias[128];
68 char *tmp, *tmpa;
69
70 /* See if we can catch a straight XK_foo 0x1234-style definition first;
71 * the trickery around tmp is to account for prefixes. */
72 i = sscanf(buf, "#define %127s 0x%lx", key, val);
73 if (i == 2 && (tmp = strstr(key, "XK_"))) {
74 memcpy(prefix, key, (size_t)(tmp - key));
75 prefix[tmp - key] = '\0';
76 tmp += 3;
77 memmove(key, tmp, strlen(tmp) + 1);
78 return 1;
79 }
80
81 /* Now try to catch alias (XK_foo XK_bar) definitions, and resolve them
82 * immediately: if the target is in the form XF86XK_foo, we need to
83 * canonicalise this to XF86foo before we do the lookup. */
84 i = sscanf(buf, "#define %127s %127s", key, alias);
85 if (i == 2 && (tmp = strstr(key, "XK_")) && (tmpa = strstr(alias, "XK_"))) {
86 memcpy(prefix, key, (size_t)(tmp - key));
87 prefix[tmp - key] = '\0';
88 tmp += 3;
89 memmove(key, tmp, strlen(tmp) + 1);
90 memmove(tmpa, tmpa + 3, strlen(tmpa + 3) + 1);
91
92 for (i = ksnum - 1; i >= 0; i--) {
93 if (strcmp(info[i].name, alias) == 0) {
94 *val = info[i].val;
95 return 1;
96 }
97 }
98
99 fprintf(stderr, "can't find matching definition %s for keysym %s%s\n",
100 alias, prefix, key);
101 }
102
103 return 0;
104 }
105
106 int
main(int argc,char * argv[])107 main(int argc, char *argv[])
108 {
109 int max_rehash;
110 Signature sig;
111 int i, j, k, l, z;
112 FILE *fptr;
113 char *name;
114 char c;
115 int first;
116 int best_max_rehash;
117 int best_z = 0;
118 int num_found;
119 KeySym val;
120 char key[128], prefix[128];
121 static char buf[1024];
122
123 for (l = 1; l < argc; l++) {
124 fptr = fopen(argv[l], "r");
125 if (!fptr) {
126 fprintf(stderr, "couldn't open %s\n", argv[l]);
127 continue;
128 }
129
130 while (fgets(buf, sizeof(buf), fptr)) {
131 if (!parse_line(buf, key, &val, prefix))
132 continue;
133
134 if (val == XK_VoidSymbol)
135 val = 0;
136 if (val > 0x1fffffff) {
137 fprintf(stderr, "ignoring illegal keysym (%s, %lx)\n", key,
138 val);
139 continue;
140 }
141
142 name = malloc(strlen(prefix) + strlen(key) + 1);
143 if (!name) {
144 fprintf(stderr, "makekeys: out of memory!\n");
145 exit(1);
146 }
147 sprintf(name, "%s%s", prefix, key);
148 info[ksnum].name = name;
149 info[ksnum].val = val;
150 ksnum++;
151 if (ksnum == KTNUM) {
152 fprintf(stderr, "makekeys: too many keysyms!\n");
153 exit(1);
154 }
155 }
156
157 fclose(fptr);
158 }
159
160 printf("/* This file is generated from keysymdef.h. */\n");
161 printf("/* Do not edit. */\n");
162 printf("\n");
163
164 best_max_rehash = ksnum;
165 num_found = 0;
166 for (z = ksnum; z < KTNUM; z++) {
167 max_rehash = 0;
168 for (name = tab, i = z; --i >= 0;)
169 *name++ = 0;
170 for (i = 0; i < ksnum; i++) {
171 name = info[i].name;
172 sig = 0;
173 while ((c = *name++))
174 sig = (sig << 1) + c;
175 first = j = sig % z;
176 for (k = 0; tab[j]; k++) {
177 j += first + 1;
178 if (j >= z)
179 j -= z;
180 if (j == first)
181 goto next1;
182 }
183 tab[j] = 1;
184 if (k > max_rehash)
185 max_rehash = k;
186 }
187 if (max_rehash < MIN_REHASH) {
188 if (max_rehash < best_max_rehash) {
189 best_max_rehash = max_rehash;
190 best_z = z;
191 }
192 num_found++;
193 if (num_found >= MATCHES)
194 break;
195 }
196 next1: ;
197 }
198
199 z = best_z;
200 if (z == 0) {
201 fprintf(stderr, "makekeys: failed to find small enough hash!\n"
202 "Try increasing KTNUM in makekeys.c\n");
203 exit(1);
204 }
205 printf("#ifdef NEEDKTABLE\n");
206 printf("const unsigned char _XkeyTable[] = {\n");
207 printf("0,\n");
208 k = 1;
209 for (i = 0; i < ksnum; i++) {
210 name = info[i].name;
211 sig = 0;
212 while ((c = *name++))
213 sig = (sig << 1) + c;
214 first = j = sig % z;
215 while (offsets[j]) {
216 j += first + 1;
217 if (j >= z)
218 j -= z;
219 }
220 offsets[j] = k;
221 indexes[i] = k;
222 val = info[i].val;
223 printf("0x%.2"PRIx32", 0x%.2"PRIx32", 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
224 (sig >> 8) & 0xff, sig & 0xff,
225 (val >> 24) & 0xff, (val >> 16) & 0xff,
226 (val >> 8) & 0xff, val & 0xff);
227 for (name = info[i].name, k += 7; (c = *name++); k++)
228 printf("'%c',", c);
229 printf((i == (ksnum-1)) ? "0\n" : "0,\n");
230 }
231 printf("};\n");
232 printf("\n");
233 printf("#define KTABLESIZE %d\n", z);
234 printf("#define KMAXHASH %d\n", best_max_rehash + 1);
235 printf("\n");
236 printf("static const unsigned short hashString[KTABLESIZE] = {\n");
237 for (i = 0; i < z;) {
238 printf("0x%.4x", offsets[i]);
239 i++;
240 if (i == z)
241 break;
242 printf((i & 7) ? ", " : ",\n");
243 }
244 printf("\n");
245 printf("};\n");
246 printf("#endif /* NEEDKTABLE */\n");
247
248 best_max_rehash = ksnum;
249 num_found = 0;
250 for (z = ksnum; z < KTNUM; z++) {
251 max_rehash = 0;
252 for (name = tab, i = z; --i >= 0;)
253 *name++ = 0;
254 for (i = 0; i < ksnum; i++) {
255 val = info[i].val;
256 first = j = val % z;
257 for (k = 0; tab[j]; k++) {
258 if (values[j] == val)
259 goto skip1;
260 j += first + 1;
261 if (j >= z)
262 j -= z;
263 if (j == first)
264 goto next2;
265 }
266 tab[j] = 1;
267 values[j] = val;
268 if (k > max_rehash)
269 max_rehash = k;
270 skip1: ;
271 }
272 if (max_rehash < MIN_REHASH) {
273 if (max_rehash < best_max_rehash) {
274 best_max_rehash = max_rehash;
275 best_z = z;
276 }
277 num_found++;
278 if (num_found >= MATCHES)
279 break;
280 }
281 next2: ;
282 }
283
284 z = best_z;
285 if (z == 0) {
286 fprintf(stderr, "makekeys: failed to find small enough hash!\n"
287 "Try increasing KTNUM in makekeys.c\n");
288 exit(1);
289 }
290 for (i = z; --i >= 0;)
291 offsets[i] = 0;
292 for (i = 0; i < ksnum; i++) {
293 val = info[i].val;
294 first = j = val % z;
295 while (offsets[j]) {
296 if (values[j] == val)
297 goto skip2;
298 j += first + 1;
299 if (j >= z)
300 j -= z;
301 }
302 offsets[j] = indexes[i] + 2;
303 values[j] = val;
304 skip2: ;
305 }
306 printf("\n");
307 printf("#ifdef NEEDVTABLE\n");
308 printf("#define VTABLESIZE %d\n", z);
309 printf("#define VMAXHASH %d\n", best_max_rehash + 1);
310 printf("\n");
311 printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
312 for (i = 0; i < z;) {
313 printf("0x%.4x", offsets[i]);
314 i++;
315 if (i == z)
316 break;
317 printf((i & 7) ? ", " : ",\n");
318 }
319 printf("\n");
320 printf("};\n");
321 printf("#endif /* NEEDVTABLE */\n");
322
323 exit(0);
324 }
325