makekeys.c revision 61b2299d 
1/* $Xorg: makekeys.c,v 1.5 2001/02/09 02:03:40 $ */
2/* $XdotOrg: lib/X11/src/util/makekeys.c,v 1.5 2005-07-03 07:00:56 daniels Exp $ */
3/*
4
5Copyright 1990, 1998  The Open Group
6
7Permission to use, copy, modify, distribute, and sell this software and its
8documentation for any purpose is hereby granted without fee, provided that
9the above copyright notice appear in all copies and that both that
10copyright notice and this permission notice appear in supporting
11documentation.
12
13The above copyright notice and this permission notice shall be included
14in all copies or substantial portions of the Software.
15
16THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
17OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
20OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
21ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
22OTHER DEALINGS IN THE SOFTWARE.
23
24Except as contained in this notice, the name of The Open Group shall
25not be used in advertising or otherwise to promote the sale, use or
26other dealings in this Software without prior written authorization
27from The Open Group.
28
29*/
30/* $XFree86: $ */
31
32/* Constructs hash tables for XStringToKeysym and XKeysymToString. */
33
34#include <X11/X.h>
35#include <X11/Xos.h>
36#include <X11/keysymdef.h>
37#include <stdio.h>
38#include <stdlib.h>
39#if defined(macII) && !defined(__STDC__)  /* stdlib.h fails to define these */
40char *malloc();
41#endif /* macII */
42
43typedef unsigned long Signature;
44
45#define KTNUM 4000
46
47static struct info {
48    char	*name;
49    KeySym	val;
50} info[KTNUM];
51
52#define MIN_REHASH 15
53#define MATCHES 10
54
55static char tab[KTNUM];
56static unsigned short offsets[KTNUM];
57static unsigned short indexes[KTNUM];
58static KeySym values[KTNUM];
59static char buf[1024];
60
61int
62main(int argc, char *argv[])
63{
64    int ksnum = 0;
65    int max_rehash;
66    Signature sig;
67    register int i, j, k, z;
68    register char *name;
69    register char c;
70    int first;
71    int best_max_rehash;
72    int best_z = 0;
73    int num_found;
74    KeySym val;
75    char key[128];
76    char alias[128];
77
78
79    while (fgets(buf, sizeof(buf), stdin)) {
80	i = sscanf(buf, "#define XK_%127s 0x%lx", key, &info[ksnum].val);
81	if (i != 2) {
82	    i = sscanf(buf, "#define XK_%127s XK_%127s", key, alias);
83	    if (i != 2)
84		continue;
85	    for (i = ksnum - 1; i >= 0; i--) {
86		if (strcmp(info[i].name, alias) == 0) {
87		    info[ksnum].val = info[i].val;
88		    break;
89		}
90	    }
91	    if (i < 0) {  /* Didn't find a match */
92		fprintf(stderr,
93		    "can't find matching definition %s for keysym %s\n",
94		    alias, key);
95		continue;
96	    }
97	}
98	if (info[ksnum].val == XK_VoidSymbol)
99	    info[ksnum].val = 0;
100	if (info[ksnum].val > 0x1fffffff) {
101	    fprintf(stderr,
102		    "ignoring illegal keysym (%s), remove it from .h file!\n",
103		    key);
104	    continue;
105	}
106	name = malloc((unsigned)strlen(key)+1);
107	if (!name) {
108	    fprintf(stderr, "makekeys: out of memory!\n");
109	    exit(1);
110	}
111	(void)strcpy(name, key);
112	info[ksnum].name = name;
113	ksnum++;
114	if (ksnum == KTNUM) {
115	    fprintf(stderr, "makekeys: too many keysyms!\n");
116	    exit(1);
117	}
118    }
119
120    printf("/* This file is generated from keysymdef.h. */\n");
121    printf("/* Do not edit. */\n");
122    printf("\n");
123
124    best_max_rehash = ksnum;
125    num_found = 0;
126    for (z = ksnum; z < KTNUM; z++) {
127	max_rehash = 0;
128	for (name = tab, i = z; --i >= 0;)
129		*name++ = 0;
130	for (i = 0; i < ksnum; i++) {
131	    name = info[i].name;
132	    sig = 0;
133	    while ((c = *name++))
134		sig = (sig << 1) + c;
135	    first = j = sig % z;
136	    for (k = 0; tab[j]; k++) {
137		j += first + 1;
138		if (j >= z)
139		    j -= z;
140		if (j == first)
141		    goto next1;
142	    }
143	    tab[j] = 1;
144	    if (k > max_rehash)
145		max_rehash = k;
146	}
147	if (max_rehash < MIN_REHASH) {
148	    if (max_rehash < best_max_rehash) {
149		best_max_rehash = max_rehash;
150		best_z = z;
151	    }
152	    num_found++;
153	    if (num_found >= MATCHES)
154		break;
155	}
156next1:	;
157    }
158
159    z = best_z;
160    printf("#ifdef NEEDKTABLE\n");
161    printf("const unsigned char _XkeyTable[] = {\n");
162    printf("0,\n");
163    k = 1;
164    for (i = 0; i < ksnum; i++) {
165	name = info[i].name;
166	sig = 0;
167	while ((c = *name++))
168	    sig = (sig << 1) + c;
169	first = j = sig % z;
170	while (offsets[j]) {
171	    j += first + 1;
172	    if (j >= z)
173		j -= z;
174	}
175	offsets[j] = k;
176	indexes[i] = k;
177	val = info[i].val;
178	printf("0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
179	       (sig >> 8) & 0xff, sig & 0xff,
180	       (val >> 24) & 0xff, (val >> 16) & 0xff,
181	       (val >> 8) & 0xff, val & 0xff);
182	for (name = info[i].name, k += 7; (c = *name++); k++)
183	    printf("'%c',", c);
184	printf((i == (ksnum-1)) ? "0\n" : "0,\n");
185    }
186    printf("};\n");
187    printf("\n");
188    printf("#define KTABLESIZE %d\n", z);
189    printf("#define KMAXHASH %d\n", best_max_rehash + 1);
190    printf("\n");
191    printf("static const unsigned short hashString[KTABLESIZE] = {\n");
192    for (i = 0; i < z;) {
193	printf("0x%.4x", offsets[i]);
194	i++;
195	if (i == z)
196	    break;
197	printf((i & 7) ? ", " : ",\n");
198    }
199    printf("\n");
200    printf("};\n");
201    printf("#endif /* NEEDKTABLE */\n");
202
203    best_max_rehash = ksnum;
204    num_found = 0;
205    for (z = ksnum; z < KTNUM; z++) {
206	max_rehash = 0;
207	for (name = tab, i = z; --i >= 0;)
208		*name++ = 0;
209	for (i = 0; i < ksnum; i++) {
210	    val = info[i].val;
211	    first = j = val % z;
212	    for (k = 0; tab[j]; k++) {
213		if (values[j] == val)
214		    goto skip1;
215		j += first + 1;
216		if (j >= z)
217		    j -= z;
218		if (j == first)
219		    goto next2;
220	    }
221	    tab[j] = 1;
222	    values[j] = val;
223	    if (k > max_rehash)
224		max_rehash = k;
225skip1:	;
226	}
227	if (max_rehash < MIN_REHASH) {
228	    if (max_rehash < best_max_rehash) {
229		best_max_rehash = max_rehash;
230		best_z = z;
231	    }
232	    num_found++;
233	    if (num_found >= MATCHES)
234		break;
235	}
236next2:	;
237    }
238
239    z = best_z;
240    for (i = z; --i >= 0;)
241	offsets[i] = 0;
242    for (i = 0; i < ksnum; i++) {
243	val = info[i].val;
244	first = j = val % z;
245	while (offsets[j]) {
246	    if (values[j] == val)
247		goto skip2;
248	    j += first + 1;
249	    if (j >= z)
250		j -= z;
251	}
252	offsets[j] = indexes[i] + 2;
253	values[j] = val;
254skip2:	;
255    }
256    printf("\n");
257    printf("#ifdef NEEDVTABLE\n");
258    printf("#define VTABLESIZE %d\n", z);
259    printf("#define VMAXHASH %d\n", best_max_rehash + 1);
260    printf("\n");
261    printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
262    for (i = 0; i < z;) {
263	printf("0x%.4x", offsets[i]);
264	i++;
265	if (i == z)
266	    break;
267	printf((i & 7) ? ", " : ",\n");
268    }
269    printf("\n");
270    printf("};\n");
271    printf("#endif /* NEEDVTABLE */\n");
272
273    exit(0);
274}
275