makekeys.c revision 9c019ec5 
1/*
2
3Copyright 1990, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included
12in all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
18OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20OTHER DEALINGS IN THE SOFTWARE.
21
22Except as contained in this notice, the name of The Open Group shall
23not be used in advertising or otherwise to promote the sale, use or
24other dealings in this Software without prior written authorization
25from 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
41typedef uint32_t Signature;
42
43#define KTNUM 4000
44
45#define XK_VoidSymbol                  0xffffff  /* Void symbol */
46
47typedef unsigned long KeySym;
48
49static struct info {
50    char	*name;
51    KeySym	val;
52} info[KTNUM];
53
54#define MIN_REHASH 15
55#define MATCHES 10
56
57static char tab[KTNUM];
58static unsigned short offsets[KTNUM];
59static unsigned short indexes[KTNUM];
60static KeySym values[KTNUM];
61static int ksnum = 0;
62
63static int
64parse_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
106int
107main(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	}
196next1:	;
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;
270skip1:	;
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	}
281next2:	;
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;
304skip2:	;
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