makekeys.c revision 2e9c7c8c 
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
40typedef unsigned long Signature;
41
42#define KTNUM 4000
43
44static struct info {
45    char	*name;
46    KeySym	val;
47} info[KTNUM];
48
49#define MIN_REHASH 15
50#define MATCHES 10
51
52static char tab[KTNUM];
53static unsigned short offsets[KTNUM];
54static unsigned short indexes[KTNUM];
55static KeySym values[KTNUM];
56static char buf[1024];
57
58int
59main(int argc, char *argv[])
60{
61    int ksnum = 0;
62    int max_rehash;
63    Signature sig;
64    register int i, j, k, z;
65    register char *name;
66    register char c;
67    int first;
68    int best_max_rehash;
69    int best_z = 0;
70    int num_found;
71    KeySym val;
72    char key[128];
73    char alias[128];
74
75
76    while (fgets(buf, sizeof(buf), stdin)) {
77	i = sscanf(buf, "#define XK_%127s 0x%lx", key, &info[ksnum].val);
78	if (i != 2) {
79	    i = sscanf(buf, "#define XK_%127s XK_%127s", key, alias);
80	    if (i != 2)
81		continue;
82	    for (i = ksnum - 1; i >= 0; i--) {
83		if (strcmp(info[i].name, alias) == 0) {
84		    info[ksnum].val = info[i].val;
85		    break;
86		}
87	    }
88	    if (i < 0) {  /* Didn't find a match */
89		fprintf(stderr,
90		    "can't find matching definition %s for keysym %s\n",
91		    alias, key);
92		continue;
93	    }
94	}
95	if (info[ksnum].val == XK_VoidSymbol)
96	    info[ksnum].val = 0;
97	if (info[ksnum].val > 0x1fffffff) {
98	    fprintf(stderr,
99		    "ignoring illegal keysym (%s), remove it from .h file!\n",
100		    key);
101	    continue;
102	}
103	name = strdup(key);
104	if (!name) {
105	    fprintf(stderr, "makekeys: out of memory!\n");
106	    exit(1);
107	}
108	info[ksnum].name = name;
109	ksnum++;
110	if (ksnum == KTNUM) {
111	    fprintf(stderr, "makekeys: too many keysyms!\n");
112	    exit(1);
113	}
114    }
115
116    printf("/* This file is generated from keysymdef.h. */\n");
117    printf("/* Do not edit. */\n");
118    printf("\n");
119
120    best_max_rehash = ksnum;
121    num_found = 0;
122    for (z = ksnum; z < KTNUM; z++) {
123	max_rehash = 0;
124	for (name = tab, i = z; --i >= 0;)
125		*name++ = 0;
126	for (i = 0; i < ksnum; i++) {
127	    name = info[i].name;
128	    sig = 0;
129	    while ((c = *name++))
130		sig = (sig << 1) + c;
131	    first = j = sig % z;
132	    for (k = 0; tab[j]; k++) {
133		j += first + 1;
134		if (j >= z)
135		    j -= z;
136		if (j == first)
137		    goto next1;
138	    }
139	    tab[j] = 1;
140	    if (k > max_rehash)
141		max_rehash = k;
142	}
143	if (max_rehash < MIN_REHASH) {
144	    if (max_rehash < best_max_rehash) {
145		best_max_rehash = max_rehash;
146		best_z = z;
147	    }
148	    num_found++;
149	    if (num_found >= MATCHES)
150		break;
151	}
152next1:	;
153    }
154
155    z = best_z;
156    if (z == 0) {
157	fprintf(stderr, "makekeys: failed to find small enough hash!\n"
158		"Try increasing KTNUM in makekeys.c\n");
159	exit(1);
160    }
161    printf("#ifdef NEEDKTABLE\n");
162    printf("const unsigned char _XkeyTable[] = {\n");
163    printf("0,\n");
164    k = 1;
165    for (i = 0; i < ksnum; i++) {
166	name = info[i].name;
167	sig = 0;
168	while ((c = *name++))
169	    sig = (sig << 1) + c;
170	first = j = sig % z;
171	while (offsets[j]) {
172	    j += first + 1;
173	    if (j >= z)
174		j -= z;
175	}
176	offsets[j] = k;
177	indexes[i] = k;
178	val = info[i].val;
179	printf("0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
180	       (sig >> 8) & 0xff, sig & 0xff,
181	       (val >> 24) & 0xff, (val >> 16) & 0xff,
182	       (val >> 8) & 0xff, val & 0xff);
183	for (name = info[i].name, k += 7; (c = *name++); k++)
184	    printf("'%c',", c);
185	printf((i == (ksnum-1)) ? "0\n" : "0,\n");
186    }
187    printf("};\n");
188    printf("\n");
189    printf("#define KTABLESIZE %d\n", z);
190    printf("#define KMAXHASH %d\n", best_max_rehash + 1);
191    printf("\n");
192    printf("static const unsigned short hashString[KTABLESIZE] = {\n");
193    for (i = 0; i < z;) {
194	printf("0x%.4x", offsets[i]);
195	i++;
196	if (i == z)
197	    break;
198	printf((i & 7) ? ", " : ",\n");
199    }
200    printf("\n");
201    printf("};\n");
202    printf("#endif /* NEEDKTABLE */\n");
203
204    best_max_rehash = ksnum;
205    num_found = 0;
206    for (z = ksnum; z < KTNUM; z++) {
207	max_rehash = 0;
208	for (name = tab, i = z; --i >= 0;)
209		*name++ = 0;
210	for (i = 0; i < ksnum; i++) {
211	    val = info[i].val;
212	    first = j = val % z;
213	    for (k = 0; tab[j]; k++) {
214		if (values[j] == val)
215		    goto skip1;
216		j += first + 1;
217		if (j >= z)
218		    j -= z;
219		if (j == first)
220		    goto next2;
221	    }
222	    tab[j] = 1;
223	    values[j] = val;
224	    if (k > max_rehash)
225		max_rehash = k;
226skip1:	;
227	}
228	if (max_rehash < MIN_REHASH) {
229	    if (max_rehash < best_max_rehash) {
230		best_max_rehash = max_rehash;
231		best_z = z;
232	    }
233	    num_found++;
234	    if (num_found >= MATCHES)
235		break;
236	}
237next2:	;
238    }
239
240    z = best_z;
241    if (z == 0) {
242	fprintf(stderr, "makekeys: failed to find small enough hash!\n"
243		"Try increasing KTNUM in makekeys.c\n");
244	exit(1);
245    }
246    for (i = z; --i >= 0;)
247	offsets[i] = 0;
248    for (i = 0; i < ksnum; i++) {
249	val = info[i].val;
250	first = j = val % z;
251	while (offsets[j]) {
252	    if (values[j] == val)
253		goto skip2;
254	    j += first + 1;
255	    if (j >= z)
256		j -= z;
257	}
258	offsets[j] = indexes[i] + 2;
259	values[j] = val;
260skip2:	;
261    }
262    printf("\n");
263    printf("#ifdef NEEDVTABLE\n");
264    printf("#define VTABLESIZE %d\n", z);
265    printf("#define VMAXHASH %d\n", best_max_rehash + 1);
266    printf("\n");
267    printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
268    for (i = 0; i < z;) {
269	printf("0x%.4x", offsets[i]);
270	i++;
271	if (i == z)
272	    break;
273	printf((i & 7) ? ", " : ",\n");
274    }
275    printf("\n");
276    printf("};\n");
277    printf("#endif /* NEEDVTABLE */\n");
278
279    exit(0);
280}
281