| 1 |
/* |
| 2 |
|
| 3 |
Copyright 1990, 1998 The Open Group |
| 4 |
|
| 5 |
Permission to use, copy, modify, distribute, and sell this software and its |
| 6 |
documentation for any purpose is hereby granted without fee, provided that |
| 7 |
the above copyright notice appear in all copies and that both that |
| 8 |
copyright notice and this permission notice appear in supporting |
| 9 |
documentation. |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included |
| 12 |
in all copies or substantial portions of the Software. |
| 13 |
|
| 14 |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |
| 15 |
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 16 |
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
| 17 |
IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR |
| 18 |
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, |
| 19 |
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR |
| 20 |
OTHER DEALINGS IN THE SOFTWARE. |
| 21 |
|
| 22 |
Except as contained in this notice, the name of The Open Group shall |
| 23 |
not be used in advertising or otherwise to promote the sale, use or |
| 24 |
other dealings in this Software without prior written authorization |
| 25 |
from 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 |
|
| 41 |
typedef uint32_t Signature; |
| 42 |
|
| 43 |
#define KTNUM 4000 |
| 44 |
|
| 45 |
#define XK_VoidSymbol 0xffffff /* Void symbol */ |
| 46 |
|
| 47 |
typedef unsigned long KeySym; |
| 48 |
|
| 49 |
static struct info { |
| 50 |
char *name; |
| 51 |
KeySym val; |
| 52 |
} info[KTNUM]; |
| 53 |
|
| 54 |
#define MIN_REHASH 15 |
| 55 |
#define MATCHES 10 |
| 56 |
|
| 57 |
static char tab[KTNUM]; |
| 58 |
static unsigned short offsets[KTNUM]; |
| 59 |
static unsigned short indexes[KTNUM]; |
| 60 |
static KeySym values[KTNUM]; |
| 61 |
static int ksnum = 0; |
| 62 |
|
| 63 |
static int |
| 64 |
parse_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 |
/* See if we can parse one of the _EVDEVK symbols */ |
| 82 |
i = sscanf(buf, "#define %127s _EVDEVK(0x%lx)", key, val); |
| 83 |
if (i == 2 && (tmp = strstr(key, "XK_"))) { |
| 84 |
memcpy(prefix, key, (size_t)(tmp - key)); |
| 85 |
prefix[tmp - key] = '\0'; |
| 86 |
tmp += 3; |
| 87 |
memmove(key, tmp, strlen(tmp) + 1); |
| 88 |
|
| 89 |
*val += 0x10081000; |
| 90 |
return 1; |
| 91 |
} |
| 92 |
|
| 93 |
/* Now try to catch alias (XK_foo XK_bar) definitions, and resolve them |
| 94 |
* immediately: if the target is in the form XF86XK_foo, we need to |
| 95 |
* canonicalise this to XF86foo before we do the lookup. */ |
| 96 |
i = sscanf(buf, "#define %127s %127s", key, alias); |
| 97 |
if (i == 2 && (tmp = strstr(key, "XK_")) && (tmpa = strstr(alias, "XK_"))) { |
| 98 |
memcpy(prefix, key, (size_t)(tmp - key)); |
| 99 |
prefix[tmp - key] = '\0'; |
| 100 |
tmp += 3; |
| 101 |
memmove(key, tmp, strlen(tmp) + 1); |
| 102 |
memmove(tmpa, tmpa + 3, strlen(tmpa + 3) + 1); |
| 103 |
|
| 104 |
for (i = ksnum - 1; i >= 0; i--) { |
| 105 |
if (strcmp(info[i].name, alias) == 0) { |
| 106 |
*val = info[i].val; |
| 107 |
return 1; |
| 108 |
} |
| 109 |
} |
| 110 |
|
| 111 |
fprintf(stderr, "can't find matching definition %s for keysym %s%s\n", |
| 112 |
alias, prefix, key); |
| 113 |
} |
| 114 |
|
| 115 |
return 0; |
| 116 |
} |
| 117 |
|
| 118 |
int |
| 119 |
main(int argc, char *argv[]) |
| 120 |
{ |
| 121 |
int max_rehash; |
| 122 |
Signature sig; |
| 123 |
int i, j, k, l, z; |
| 124 |
FILE *fptr; |
| 125 |
char *name; |
| 126 |
char c; |
| 127 |
int first; |
| 128 |
int best_max_rehash; |
| 129 |
int best_z = 0; |
| 130 |
int num_found; |
| 131 |
KeySym val; |
| 132 |
char key[128], prefix[128]; |
| 133 |
static char buf[1024]; |
| 134 |
|
| 135 |
for (l = 1; l < argc; l++) { |
| 136 |
fptr = fopen(argv[l], "r"); |
| 137 |
if (!fptr) { |
| 138 |
fprintf(stderr, "couldn't open %s\n", argv[l]); |
| 139 |
continue; |
| 140 |
} |
| 141 |
|
| 142 |
while (fgets(buf, sizeof(buf), fptr)) { |
| 143 |
if (!parse_line(buf, key, &val, prefix)) |
| 144 |
continue; |
| 145 |
|
| 146 |
if (val == XK_VoidSymbol) |
| 147 |
val = 0; |
| 148 |
if (val > 0x1fffffff) { |
| 149 |
fprintf(stderr, "ignoring illegal keysym (%s, %lx)\n", key, |
| 150 |
val); |
| 151 |
continue; |
| 152 |
} |
| 153 |
|
| 154 |
name = malloc(strlen(prefix) + strlen(key) + 1); |
| 155 |
if (!name) { |
| 156 |
fprintf(stderr, "makekeys: out of memory!\n"); |
| 157 |
exit(1); |
| 158 |
} |
| 159 |
sprintf(name, "%s%s", prefix, key); |
| 160 |
info[ksnum].name = name; |
| 161 |
info[ksnum].val = val; |
| 162 |
ksnum++; |
| 163 |
if (ksnum == KTNUM) { |
| 164 |
fprintf(stderr, "makekeys: too many keysyms!\n"); |
| 165 |
exit(1); |
| 166 |
} |
| 167 |
} |
| 168 |
|
| 169 |
fclose(fptr); |
| 170 |
} |
| 171 |
|
| 172 |
printf("/* This file is generated from keysymdef.h. */\n"); |
| 173 |
printf("/* Do not edit. */\n"); |
| 174 |
printf("\n"); |
| 175 |
|
| 176 |
best_max_rehash = ksnum; |
| 177 |
num_found = 0; |
| 178 |
for (z = ksnum; z < KTNUM; z++) { |
| 179 |
max_rehash = 0; |
| 180 |
for (name = tab, i = z; --i >= 0;) |
| 181 |
*name++ = 0; |
| 182 |
for (i = 0; i < ksnum; i++) { |
| 183 |
name = info[i].name; |
| 184 |
sig = 0; |
| 185 |
while ((c = *name++)) |
| 186 |
sig = (sig << 1) + c; |
| 187 |
first = j = sig % z; |
| 188 |
for (k = 0; tab[j]; k++) { |
| 189 |
j += first + 1; |
| 190 |
if (j >= z) |
| 191 |
j -= z; |
| 192 |
if (j == first) |
| 193 |
goto next1; |
| 194 |
} |
| 195 |
tab[j] = 1; |
| 196 |
if (k > max_rehash) |
| 197 |
max_rehash = k; |
| 198 |
} |
| 199 |
if (max_rehash < MIN_REHASH) { |
| 200 |
if (max_rehash < best_max_rehash) { |
| 201 |
best_max_rehash = max_rehash; |
| 202 |
best_z = z; |
| 203 |
} |
| 204 |
num_found++; |
| 205 |
if (num_found >= MATCHES) |
| 206 |
break; |
| 207 |
} |
| 208 |
next1: ; |
| 209 |
} |
| 210 |
|
| 211 |
z = best_z; |
| 212 |
if (z == 0) { |
| 213 |
fprintf(stderr, "makekeys: failed to find small enough hash!\n" |
| 214 |
"Try increasing KTNUM in makekeys.c\n"); |
| 215 |
exit(1); |
| 216 |
} |
| 217 |
printf("#ifdef NEEDKTABLE\n"); |
| 218 |
printf("const unsigned char _XkeyTable[] = {\n"); |
| 219 |
printf("0,\n"); |
| 220 |
k = 1; |
| 221 |
for (i = 0; i < ksnum; i++) { |
| 222 |
name = info[i].name; |
| 223 |
sig = 0; |
| 224 |
while ((c = *name++)) |
| 225 |
sig = (sig << 1) + c; |
| 226 |
first = j = sig % z; |
| 227 |
while (offsets[j]) { |
| 228 |
j += first + 1; |
| 229 |
if (j >= z) |
| 230 |
j -= z; |
| 231 |
} |
| 232 |
offsets[j] = k; |
| 233 |
indexes[i] = k; |
| 234 |
val = info[i].val; |
| 235 |
printf("0x%.2"PRIx32", 0x%.2"PRIx32", 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ", |
| 236 |
(sig >> 8) & 0xff, sig & 0xff, |
| 237 |
(val >> 24) & 0xff, (val >> 16) & 0xff, |
| 238 |
(val >> 8) & 0xff, val & 0xff); |
| 239 |
for (name = info[i].name, k += 7; (c = *name++); k++) |
| 240 |
printf("'%c',", c); |
| 241 |
printf((i == (ksnum-1)) ? "0\n" : "0,\n"); |
| 242 |
} |
| 243 |
printf("};\n"); |
| 244 |
printf("\n"); |
| 245 |
printf("#define KTABLESIZE %d\n", z); |
| 246 |
printf("#define KMAXHASH %d\n", best_max_rehash + 1); |
| 247 |
printf("\n"); |
| 248 |
printf("static const unsigned short hashString[KTABLESIZE] = {\n"); |
| 249 |
for (i = 0; i < z;) { |
| 250 |
printf("0x%.4x", offsets[i]); |
| 251 |
i++; |
| 252 |
if (i == z) |
| 253 |
break; |
| 254 |
printf((i & 7) ? ", " : ",\n"); |
| 255 |
} |
| 256 |
printf("\n"); |
| 257 |
printf("};\n"); |
| 258 |
printf("#endif /* NEEDKTABLE */\n"); |
| 259 |
|
| 260 |
best_max_rehash = ksnum; |
| 261 |
num_found = 0; |
| 262 |
for (z = ksnum; z < KTNUM; z++) { |
| 263 |
max_rehash = 0; |
| 264 |
for (name = tab, i = z; --i >= 0;) |
| 265 |
*name++ = 0; |
| 266 |
for (i = 0; i < ksnum; i++) { |
| 267 |
val = info[i].val; |
| 268 |
first = j = val % z; |
| 269 |
for (k = 0; tab[j]; k++) { |
| 270 |
if (values[j] == val) |
| 271 |
goto skip1; |
| 272 |
j += first + 1; |
| 273 |
if (j >= z) |
| 274 |
j -= z; |
| 275 |
if (j == first) |
| 276 |
goto next2; |
| 277 |
} |
| 278 |
tab[j] = 1; |
| 279 |
values[j] = val; |
| 280 |
if (k > max_rehash) |
| 281 |
max_rehash = k; |
| 282 |
skip1: ; |
| 283 |
} |
| 284 |
if (max_rehash < MIN_REHASH) { |
| 285 |
if (max_rehash < best_max_rehash) { |
| 286 |
best_max_rehash = max_rehash; |
| 287 |
best_z = z; |
| 288 |
} |
| 289 |
num_found++; |
| 290 |
if (num_found >= MATCHES) |
| 291 |
break; |
| 292 |
} |
| 293 |
next2: ; |
| 294 |
} |
| 295 |
|
| 296 |
z = best_z; |
| 297 |
if (z == 0) { |
| 298 |
fprintf(stderr, "makekeys: failed to find small enough hash!\n" |
| 299 |
"Try increasing KTNUM in makekeys.c\n"); |
| 300 |
exit(1); |
| 301 |
} |
| 302 |
for (i = z; --i >= 0;) |
| 303 |
offsets[i] = 0; |
| 304 |
for (i = 0; i < ksnum; i++) { |
| 305 |
val = info[i].val; |
| 306 |
first = j = val % z; |
| 307 |
while (offsets[j]) { |
| 308 |
if (values[j] == val) |
| 309 |
goto skip2; |
| 310 |
j += first + 1; |
| 311 |
if (j >= z) |
| 312 |
j -= z; |
| 313 |
} |
| 314 |
offsets[j] = indexes[i] + 2; |
| 315 |
values[j] = val; |
| 316 |
skip2: ; |
| 317 |
} |
| 318 |
printf("\n"); |
| 319 |
printf("#ifdef NEEDVTABLE\n"); |
| 320 |
printf("#define VTABLESIZE %d\n", z); |
| 321 |
printf("#define VMAXHASH %d\n", best_max_rehash + 1); |
| 322 |
printf("\n"); |
| 323 |
printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n"); |
| 324 |
for (i = 0; i < z;) { |
| 325 |
printf("0x%.4x", offsets[i]); |
| 326 |
i++; |
| 327 |
if (i == z) |
| 328 |
break; |
| 329 |
printf((i & 7) ? ", " : ",\n"); |
| 330 |
} |
| 331 |
printf("\n"); |
| 332 |
printf("};\n"); |
| 333 |
printf("#endif /* NEEDVTABLE */\n"); |
| 334 |
|
| 335 |
exit(0); |
| 336 |
} |