makekeys.c revision 47f86ac1 
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#include <X11/X.h>
32#include <X11/Xos.h>
33#include <X11/keysymdef.h>
34#include <stdio.h>
35#include <stdlib.h>
36
37typedef unsigned long Signature;
38
39#define KTNUM 4000
40
41static struct info {
42    char	*name;
43    KeySym	val;
44} info[KTNUM];
45
46#define MIN_REHASH 15
47#define MATCHES 10
48
49static char tab[KTNUM];
50static unsigned short offsets[KTNUM];
51static unsigned short indexes[KTNUM];
52static KeySym values[KTNUM];
53static char buf[1024];
54static int ksnum = 0;
55
56static int
57parse_line(const char *buf, char *key, KeySym *val, char *prefix)
58{
59    int i;
60    char alias[128];
61    char *tmp, *tmpa;
62
63    /* See if we can catch a straight XK_foo 0x1234-style definition first;
64     * the trickery around tmp is to account for prefices. */
65    i = sscanf(buf, "#define %127s 0x%lx", key, val);
66    if (i == 2 && (tmp = strstr(key, "XK_"))) {
67        memcpy(prefix, key, tmp - key);
68        prefix[tmp - key] = '\0';
69        tmp += 3;
70        memmove(key, tmp, strlen(tmp) + 1);
71        return 1;
72    }
73
74    /* Now try to catch alias (XK_foo XK_bar) definitions, and resolve them
75     * immediately: if the target is in the form XF86XK_foo, we need to
76     * canonicalise this to XF86foo before we do the lookup. */
77    i = sscanf(buf, "#define %127s %127s", key, alias);
78    if (i == 2 && (tmp = strstr(key, "XK_")) && (tmpa = strstr(alias, "XK_"))) {
79        memcpy(prefix, key, tmp - key);
80        prefix[tmp - key] = '\0';
81        tmp += 3;
82        memmove(key, tmp, strlen(tmp) + 1);
83        memmove(tmpa, tmpa + 3, strlen(tmpa + 3) + 1);
84
85        for (i = ksnum - 1; i >= 0; i--) {
86            if (strcmp(info[i].name, alias) == 0) {
87                *val = info[i].val;
88                return 1;
89            }
90        }
91
92        fprintf(stderr, "can't find matching definition %s for keysym %s%s\n",
93                alias, prefix, key);
94    }
95
96    return 0;
97}
98
99int
100main(int argc, char *argv[])
101{
102    int max_rehash;
103    Signature sig;
104    int i, j, k, l, z;
105    FILE *fptr;
106    char *name;
107    char c;
108    int first;
109    int best_max_rehash;
110    int best_z = 0;
111    int num_found;
112    KeySym val;
113    char key[128], prefix[128];
114
115    for (l = 1; l < argc; l++) {
116        fptr = fopen(argv[l], "r");
117        if (!fptr) {
118            fprintf(stderr, "couldn't open %s\n", argv[l]);
119            continue;
120        }
121
122        while (fgets(buf, sizeof(buf), fptr)) {
123            if (!parse_line(buf, key, &val, prefix))
124                continue;
125
126            if (val == XK_VoidSymbol)
127                val = 0;
128            if (val > 0x1fffffff) {
129                fprintf(stderr, "ignoring illegal keysym (%s, %lx)\n", key,
130                        val);
131                continue;
132            }
133
134            name = malloc(strlen(prefix) + strlen(key) + 1);
135            if (!name) {
136                fprintf(stderr, "makekeys: out of memory!\n");
137                exit(1);
138            }
139            sprintf(name, "%s%s", prefix, key);
140            info[ksnum].name = name;
141            info[ksnum].val = val;
142            ksnum++;
143            if (ksnum == KTNUM) {
144                fprintf(stderr, "makekeys: too many keysyms!\n");
145                exit(1);
146            }
147        }
148
149        fclose(fptr);
150    }
151
152    printf("/* This file is generated from keysymdef.h. */\n");
153    printf("/* Do not edit. */\n");
154    printf("\n");
155
156    best_max_rehash = ksnum;
157    num_found = 0;
158    for (z = ksnum; z < KTNUM; z++) {
159	max_rehash = 0;
160	for (name = tab, i = z; --i >= 0;)
161		*name++ = 0;
162	for (i = 0; i < ksnum; i++) {
163	    name = info[i].name;
164	    sig = 0;
165	    while ((c = *name++))
166		sig = (sig << 1) + c;
167	    first = j = sig % z;
168	    for (k = 0; tab[j]; k++) {
169		j += first + 1;
170		if (j >= z)
171		    j -= z;
172		if (j == first)
173		    goto next1;
174	    }
175	    tab[j] = 1;
176	    if (k > max_rehash)
177		max_rehash = k;
178	}
179	if (max_rehash < MIN_REHASH) {
180	    if (max_rehash < best_max_rehash) {
181		best_max_rehash = max_rehash;
182		best_z = z;
183	    }
184	    num_found++;
185	    if (num_found >= MATCHES)
186		break;
187	}
188next1:	;
189    }
190
191    z = best_z;
192    if (z == 0) {
193	fprintf(stderr, "makekeys: failed to find small enough hash!\n"
194		"Try increasing KTNUM in makekeys.c\n");
195	exit(1);
196    }
197    printf("#ifdef NEEDKTABLE\n");
198    printf("const unsigned char _XkeyTable[] = {\n");
199    printf("0,\n");
200    k = 1;
201    for (i = 0; i < ksnum; i++) {
202	name = info[i].name;
203	sig = 0;
204	while ((c = *name++))
205	    sig = (sig << 1) + c;
206	first = j = sig % z;
207	while (offsets[j]) {
208	    j += first + 1;
209	    if (j >= z)
210		j -= z;
211	}
212	offsets[j] = k;
213	indexes[i] = k;
214	val = info[i].val;
215	printf("0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
216	       (sig >> 8) & 0xff, sig & 0xff,
217	       (val >> 24) & 0xff, (val >> 16) & 0xff,
218	       (val >> 8) & 0xff, val & 0xff);
219	for (name = info[i].name, k += 7; (c = *name++); k++)
220	    printf("'%c',", c);
221	printf((i == (ksnum-1)) ? "0\n" : "0,\n");
222    }
223    printf("};\n");
224    printf("\n");
225    printf("#define KTABLESIZE %d\n", z);
226    printf("#define KMAXHASH %d\n", best_max_rehash + 1);
227    printf("\n");
228    printf("static const unsigned short hashString[KTABLESIZE] = {\n");
229    for (i = 0; i < z;) {
230	printf("0x%.4x", offsets[i]);
231	i++;
232	if (i == z)
233	    break;
234	printf((i & 7) ? ", " : ",\n");
235    }
236    printf("\n");
237    printf("};\n");
238    printf("#endif /* NEEDKTABLE */\n");
239
240    best_max_rehash = ksnum;
241    num_found = 0;
242    for (z = ksnum; z < KTNUM; z++) {
243	max_rehash = 0;
244	for (name = tab, i = z; --i >= 0;)
245		*name++ = 0;
246	for (i = 0; i < ksnum; i++) {
247	    val = info[i].val;
248	    first = j = val % z;
249	    for (k = 0; tab[j]; k++) {
250		if (values[j] == val)
251		    goto skip1;
252		j += first + 1;
253		if (j >= z)
254		    j -= z;
255		if (j == first)
256		    goto next2;
257	    }
258	    tab[j] = 1;
259	    values[j] = val;
260	    if (k > max_rehash)
261		max_rehash = k;
262skip1:	;
263	}
264	if (max_rehash < MIN_REHASH) {
265	    if (max_rehash < best_max_rehash) {
266		best_max_rehash = max_rehash;
267		best_z = z;
268	    }
269	    num_found++;
270	    if (num_found >= MATCHES)
271		break;
272	}
273next2:	;
274    }
275
276    z = best_z;
277    if (z == 0) {
278	fprintf(stderr, "makekeys: failed to find small enough hash!\n"
279		"Try increasing KTNUM in makekeys.c\n");
280	exit(1);
281    }
282    for (i = z; --i >= 0;)
283	offsets[i] = 0;
284    for (i = 0; i < ksnum; i++) {
285	val = info[i].val;
286	first = j = val % z;
287	while (offsets[j]) {
288	    if (values[j] == val)
289		goto skip2;
290	    j += first + 1;
291	    if (j >= z)
292		j -= z;
293	}
294	offsets[j] = indexes[i] + 2;
295	values[j] = val;
296skip2:	;
297    }
298    printf("\n");
299    printf("#ifdef NEEDVTABLE\n");
300    printf("#define VTABLESIZE %d\n", z);
301    printf("#define VMAXHASH %d\n", best_max_rehash + 1);
302    printf("\n");
303    printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
304    for (i = 0; i < z;) {
305	printf("0x%.4x", offsets[i]);
306	i++;
307	if (i == z)
308	    break;
309	printf((i & 7) ? ", " : ",\n");
310    }
311    printf("\n");
312    printf("};\n");
313    printf("#endif /* NEEDVTABLE */\n");
314
315    exit(0);
316}
317