makekeys.c revision eb411b4b 
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/Xresource.h>
34#include <X11/keysymdef.h>
35#include <stdio.h>
36#include <stdlib.h>
37
38#include "../Xresinternal.h"
39
40#define KTNUM 4000
41
42static struct info {
43    char	*name;
44    KeySym	val;
45} info[KTNUM];
46
47#define MIN_REHASH 15
48#define MATCHES 10
49
50static char tab[KTNUM];
51static unsigned short offsets[KTNUM];
52static unsigned short indexes[KTNUM];
53static KeySym values[KTNUM];
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    static char buf[1024];
115
116    for (l = 1; l < argc; l++) {
117        fptr = fopen(argv[l], "r");
118        if (!fptr) {
119            fprintf(stderr, "couldn't open %s\n", argv[l]);
120            continue;
121        }
122
123        while (fgets(buf, sizeof(buf), fptr)) {
124            if (!parse_line(buf, key, &val, prefix))
125                continue;
126
127            if (val == XK_VoidSymbol)
128                val = 0;
129            if (val > 0x1fffffff) {
130                fprintf(stderr, "ignoring illegal keysym (%s, %lx)\n", key,
131                        val);
132                continue;
133            }
134
135            name = malloc(strlen(prefix) + strlen(key) + 1);
136            if (!name) {
137                fprintf(stderr, "makekeys: out of memory!\n");
138                exit(1);
139            }
140            sprintf(name, "%s%s", prefix, key);
141            info[ksnum].name = name;
142            info[ksnum].val = val;
143            ksnum++;
144            if (ksnum == KTNUM) {
145                fprintf(stderr, "makekeys: too many keysyms!\n");
146                exit(1);
147            }
148        }
149
150        fclose(fptr);
151    }
152
153    printf("/* This file is generated from keysymdef.h. */\n");
154    printf("/* Do not edit. */\n");
155    printf("\n");
156
157    best_max_rehash = ksnum;
158    num_found = 0;
159    for (z = ksnum; z < KTNUM; z++) {
160	max_rehash = 0;
161	for (name = tab, i = z; --i >= 0;)
162		*name++ = 0;
163	for (i = 0; i < ksnum; i++) {
164	    name = info[i].name;
165	    sig = 0;
166	    while ((c = *name++))
167		sig = (sig << 1) + c;
168	    first = j = sig % z;
169	    for (k = 0; tab[j]; k++) {
170		j += first + 1;
171		if (j >= z)
172		    j -= z;
173		if (j == first)
174		    goto next1;
175	    }
176	    tab[j] = 1;
177	    if (k > max_rehash)
178		max_rehash = k;
179	}
180	if (max_rehash < MIN_REHASH) {
181	    if (max_rehash < best_max_rehash) {
182		best_max_rehash = max_rehash;
183		best_z = z;
184	    }
185	    num_found++;
186	    if (num_found >= MATCHES)
187		break;
188	}
189next1:	;
190    }
191
192    z = best_z;
193    if (z == 0) {
194	fprintf(stderr, "makekeys: failed to find small enough hash!\n"
195		"Try increasing KTNUM in makekeys.c\n");
196	exit(1);
197    }
198    printf("#ifdef NEEDKTABLE\n");
199    printf("const unsigned char _XkeyTable[] = {\n");
200    printf("0,\n");
201    k = 1;
202    for (i = 0; i < ksnum; i++) {
203	name = info[i].name;
204	sig = 0;
205	while ((c = *name++))
206	    sig = (sig << 1) + c;
207	first = j = sig % z;
208	while (offsets[j]) {
209	    j += first + 1;
210	    if (j >= z)
211		j -= z;
212	}
213	offsets[j] = k;
214	indexes[i] = k;
215	val = info[i].val;
216	printf("0x%.2"PRIx32", 0x%.2"PRIx32", 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
217	       (sig >> 8) & 0xff, sig & 0xff,
218	       (val >> 24) & 0xff, (val >> 16) & 0xff,
219	       (val >> 8) & 0xff, val & 0xff);
220	for (name = info[i].name, k += 7; (c = *name++); k++)
221	    printf("'%c',", c);
222	printf((i == (ksnum-1)) ? "0\n" : "0,\n");
223    }
224    printf("};\n");
225    printf("\n");
226    printf("#define KTABLESIZE %d\n", z);
227    printf("#define KMAXHASH %d\n", best_max_rehash + 1);
228    printf("\n");
229    printf("static const unsigned short hashString[KTABLESIZE] = {\n");
230    for (i = 0; i < z;) {
231	printf("0x%.4x", offsets[i]);
232	i++;
233	if (i == z)
234	    break;
235	printf((i & 7) ? ", " : ",\n");
236    }
237    printf("\n");
238    printf("};\n");
239    printf("#endif /* NEEDKTABLE */\n");
240
241    best_max_rehash = ksnum;
242    num_found = 0;
243    for (z = ksnum; z < KTNUM; z++) {
244	max_rehash = 0;
245	for (name = tab, i = z; --i >= 0;)
246		*name++ = 0;
247	for (i = 0; i < ksnum; i++) {
248	    val = info[i].val;
249	    first = j = val % z;
250	    for (k = 0; tab[j]; k++) {
251		if (values[j] == val)
252		    goto skip1;
253		j += first + 1;
254		if (j >= z)
255		    j -= z;
256		if (j == first)
257		    goto next2;
258	    }
259	    tab[j] = 1;
260	    values[j] = val;
261	    if (k > max_rehash)
262		max_rehash = k;
263skip1:	;
264	}
265	if (max_rehash < MIN_REHASH) {
266	    if (max_rehash < best_max_rehash) {
267		best_max_rehash = max_rehash;
268		best_z = z;
269	    }
270	    num_found++;
271	    if (num_found >= MATCHES)
272		break;
273	}
274next2:	;
275    }
276
277    z = best_z;
278    if (z == 0) {
279	fprintf(stderr, "makekeys: failed to find small enough hash!\n"
280		"Try increasing KTNUM in makekeys.c\n");
281	exit(1);
282    }
283    for (i = z; --i >= 0;)
284	offsets[i] = 0;
285    for (i = 0; i < ksnum; i++) {
286	val = info[i].val;
287	first = j = val % z;
288	while (offsets[j]) {
289	    if (values[j] == val)
290		goto skip2;
291	    j += first + 1;
292	    if (j >= z)
293		j -= z;
294	}
295	offsets[j] = indexes[i] + 2;
296	values[j] = val;
297skip2:	;
298    }
299    printf("\n");
300    printf("#ifdef NEEDVTABLE\n");
301    printf("#define VTABLESIZE %d\n", z);
302    printf("#define VMAXHASH %d\n", best_max_rehash + 1);
303    printf("\n");
304    printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
305    for (i = 0; i < z;) {
306	printf("0x%.4x", offsets[i]);
307	i++;
308	if (i == z)
309	    break;
310	printf((i & 7) ? ", " : ",\n");
311    }
312    printf("\n");
313    printf("};\n");
314    printf("#endif /* NEEDVTABLE */\n");
315
316    exit(0);
317}
318