makekeys/makekeys.c

   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 #include <X11/X.h>
  32 #include <X11/Xos.h>
  33 #include <X11/keysymdef.h>
  34 #include <inttypes.h>
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37
  38 typedef uint32_t Signature;
  39
  40 #define KTNUM 4000
  41
  42 static struct info {
  43     char        *name;
  44     KeySym      val;
  45 } info[KTNUM];
  46
  47 #define MIN_REHASH 15
  48 #define MATCHES 10
  49
  50 static char tab[KTNUM];
  51 static unsigned short offsets[KTNUM];
  52 static unsigned short indexes[KTNUM];
  53 static KeySym values[KTNUM];
  54
  55 /*
  56  * XFree86 special action keys - for some reason, these have an
  57  * underscore after the XF86 prefix.
  58  */
  59 static const char *xf86_special_keys[] = {
  60     "Switch_VT_1",
  61     "Switch_VT_2",
  62     "Switch_VT_3",
  63     "Switch_VT_4",
  64     "Switch_VT_5",
  65     "Switch_VT_6",
  66     "Switch_VT_7",
  67     "Switch_VT_8",
  68     "Switch_VT_9",
  69     "Switch_VT_10",
  70     "Switch_VT_11",
  71     "Switch_VT_12",
  72     "Ungrab",
  73     "ClearGrab",
  74     "Next_VMode",
  75     "Prev_VMode",
  76     NULL
  77 };
  78
  79 static int
  80 is_xf86_special(const char *key)
  81 {
  82     const char **s = xf86_special_keys;
  83     while (*s) {
  84         if (strcmp(key, *s) == 0)
  85             return 1;
  86         s++;
  87     }
  88     return 0;
  89 }
  90
  91 static int
  92 get_keysym(const char *buf, char *key, int ndx)
  93 {
  94     if (sscanf(buf, "#define XK_%127s 0x%lx", key, &info[ndx].val) != 2)
  95         return 0;
  96     return 1;
  97 }
  98
  99 static int
 100 get_keysym_alias(const char *buf, char *key, int ndx)
 101 {
 102     int i;
 103     char alias[128];
 104
 105     if (sscanf(buf, "#define XK_%127s XK_%127s", key, alias) != 2)
 106         return 0;
 107
 108     for (i = ndx - 1; i >= 0; i--) {
 109         if (strcmp(info[i].name, alias) == 0) {
 110             info[ndx].val = info[i].val;
 111             return 1;
 112         }
 113     }
 114
 115     /* Didn't find a match */
 116     fprintf(stderr, "can't find matching definition %s for keysym %s\n",
 117             alias, key);
 118     return -1;
 119 }
 120
 121 static int
 122 get_xf86_keysym(const char *buf, char *key, size_t len, int ndx)
 123 {
 124     char tmp[128];
 125
 126     if (sscanf(buf, "#define XF86XK_%127s 0x%lx", tmp, &info[ndx].val) != 2)
 127         return 0;
 128
 129     /* Prepend XF86 or XF86_ to the key */
 130     snprintf(key, len, "XF86%s%s", is_xf86_special(tmp) ? "_" : "", tmp);
 131
 132     return 1;
 133 }
 134
 135 static int
 136 get_xf86_keysym_alias(const char *buf, char *key, size_t len, int ndx)
 137 {
 138     int i;
 139     char alias[128], ktmp[128], atmp[128];
 140
 141     /* Try to handle both XF86XK and XK aliases */
 142     if (sscanf(buf, "#define XF86XK_%127s XF86XK_%127s", ktmp, atmp) == 2) {
 143         /* Prepend XF86 to the key and alias */
 144         snprintf(key, len, "XF86%s%s", is_xf86_special(ktmp) ? "_" : "",
 145                  ktmp);
 146         snprintf(alias, sizeof(alias), "XF86%s%s",
 147                  is_xf86_special(atmp) ? "_" : "", atmp);
 148     } else {
 149         if (sscanf(buf, "#define XF86XK_%127s XK_%127s", ktmp, alias) != 2)
 150             return 0;
 151         /* Prepend XF86 to the key */
 152         snprintf(key, len, "XF86%s%s", is_xf86_special(ktmp) ? "_" : "",
 153                  ktmp);
 154     }
 155
 156     for (i = ndx - 1; i >= 0; i--) {
 157         if (strcmp(info[i].name, alias) == 0) {
 158             info[ndx].val = info[i].val;
 159             return 1;
 160         }
 161     }
 162
 163     /* Didn't find a match */
 164     fprintf(stderr, "can't find matching definition %s for keysym %s\n",
 165             alias, key);
 166     return -1;
 167 }
 168
 169 int
 170 main(int argc, char *argv[])
 171 {
 172     int ksnum = 0;
 173     FILE *fptr;
 174     int max_rehash;
 175     Signature sig;
 176     int i, j, k, l, z;
 177     char *name;
 178     char c;
 179     int first;
 180     int best_max_rehash;
 181     int best_z = 0;
 182     int num_found;
 183     KeySym val;
 184     char key[128];
 185     char buf[1024];
 186
 187     for (l = 1; l < argc; l++) {
 188         fptr = fopen(argv[l], "r");
 189         if (!fptr) {
 190             fprintf(stderr, "couldn't open %s\n", argv[l]);
 191             continue;
 192         }
 193
 194         while (fgets(buf, sizeof(buf), fptr)) {
 195             int ret;
 196
 197             /* Manage keysyms from keysymdef.h */
 198             ret = get_keysym(buf, key, ksnum);
 199             if (!ret) {
 200                 ret = get_keysym_alias(buf, key, ksnum);
 201                 if (ret == -1)
 202                     continue;
 203             }
 204
 205             /* Manage keysyms from XF86keysym.h */
 206             if (!ret)
 207                 ret = get_xf86_keysym(buf, key, sizeof(key), ksnum);
 208             if (!ret) {
 209                 ret = get_xf86_keysym_alias(buf, key, sizeof(key), ksnum);
 210                 if (ret < 1)
 211                     continue;
 212             }
 213
 214             if (info[ksnum].val > 0x1fffffff) {
 215                 fprintf(stderr,
 216                         "ignoring illegal keysym (%s), remove it from .h file!\n",
 217                         key);
 218                 continue;
 219             }
 220             name = malloc((unsigned)strlen(key) + 1);
 221             if (!name) {
 222                 fprintf(stderr, "makekeys: out of memory!\n");
 223                 exit(1);
 224             }
 225             (void)strcpy(name, key);
 226             info[ksnum].name = name;
 227             ksnum++;
 228             if (ksnum == KTNUM) {
 229                 fprintf(stderr, "makekeys: too many keysyms!\n");
 230                 exit(1);
 231             }
 232         }
 233
 234         fclose(fptr);
 235     }
 236
 237     /* Special case NoSymbol. */
 238     info[ksnum].name = strdup("NoSymbol");
 239     info[ksnum].val = 0L;
 240     ksnum++;
 241
 242     printf("/* This file is generated from keysymdef.h. */\n");
 243     printf("/* Do not edit. */\n");
 244     printf("\n");
 245
 246     best_max_rehash = ksnum;
 247     num_found = 0;
 248     for (z = ksnum; z < KTNUM; z++) {
 249         max_rehash = 0;
 250         for (name = tab, i = z; --i >= 0;)
 251             *name++ = 0;
 252         for (i = 0; i < ksnum; i++) {
 253             name = info[i].name;
 254             sig = 0;
 255             while ((c = *name++))
 256                 sig = (sig << 1) + c;
 257             first = j = sig % z;
 258             for (k = 0; tab[j]; k++) {
 259                 j += first + 1;
 260                 if (j >= z)
 261                     j -= z;
 262                 if (j == first)
 263                     goto next1;
 264             }
 265             tab[j] = 1;
 266             if (k > max_rehash)
 267                 max_rehash = k;
 268         }
 269         if (max_rehash < MIN_REHASH) {
 270             if (max_rehash < best_max_rehash) {
 271                 best_max_rehash = max_rehash;
 272                 best_z = z;
 273             }
 274             num_found++;
 275             if (num_found >= MATCHES)
 276                 break;
 277         }
 278 next1:  ;
 279     }
 280
 281     z = best_z;
 282     printf("#ifndef KS_TABLES_H\n");
 283     printf("#define KS_TABLES_H\n\n");
 284     printf("static const unsigned char _XkeyTable[] = {\n");
 285     if (z == 0) {
 286         fprintf(stderr, "makekeys: failed to find small enough hash!\n"
 287                 "Try increasing KTNUM in makekeys.c\n");
 288         exit(1);
 289     }
 290     printf("0,\n");
 291     k = 1;
 292     for (i = 0; i < ksnum; i++) {
 293         name = info[i].name;
 294         sig = 0;
 295         while ((c = *name++))
 296             sig = (sig << 1) + c;
 297         first = j = sig % z;
 298         while (offsets[j]) {
 299             j += first + 1;
 300             if (j >= z)
 301                 j -= z;
 302         }
 303         offsets[j] = k;
 304         indexes[i] = k;
 305         val = info[i].val;
 306         printf("0x%.2"PRIx32", 0x%.2"PRIx32", 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
 307                (sig >> 8) & 0xff, sig & 0xff,
 308                (val >> 24) & 0xff, (val >> 16) & 0xff,
 309                (val >> 8) & 0xff, val & 0xff);
 310         for (name = info[i].name, k += 7; (c = *name++); k++)
 311             printf("'%c',", c);
 312         printf((i == (ksnum-1)) ? "0\n" : "0,\n");
 313     }
 314     printf("};\n");
 315     printf("\n");
 316     printf("#define KTABLESIZE %d\n", z);
 317     printf("#define KMAXHASH %d\n", best_max_rehash + 1);
 318     printf("\n");
 319     printf("static const unsigned short hashString[KTABLESIZE] = {\n");
 320     for (i = 0; i < z;) {
 321         printf("0x%.4x", offsets[i]);
 322         i++;
 323         if (i == z)
 324             break;
 325         printf((i & 7) ? ", " : ",\n");
 326     }
 327     printf("\n");
 328     printf("};\n");
 329
 330     best_max_rehash = ksnum;
 331     num_found = 0;
 332     for (z = ksnum; z < KTNUM; z++) {
 333         max_rehash = 0;
 334         for (name = tab, i = z; --i >= 0;)
 335             *name++ = 0;
 336         for (i = 0; i < ksnum; i++) {
 337             val = info[i].val;
 338             first = j = val % z;
 339             for (k = 0; tab[j]; k++) {
 340                 if (values[j] == val)
 341                     goto skip1;
 342                 j += first + 1;
 343                 if (j >= z)
 344                     j -= z;
 345                 if (j == first)
 346                     goto next2;
 347             }
 348             tab[j] = 1;
 349             values[j] = val;
 350             if (k > max_rehash)
 351                 max_rehash = k;
 352 skip1:  ;
 353         }
 354         if (max_rehash < MIN_REHASH) {
 355             if (max_rehash < best_max_rehash) {
 356                 best_max_rehash = max_rehash;
 357                 best_z = z;
 358             }
 359             num_found++;
 360             if (num_found >= MATCHES)
 361                 break;
 362         }
 363 next2:  ;
 364     }
 365
 366     z = best_z;
 367     if (z == 0) {
 368         fprintf(stderr, "makekeys: failed to find small enough hash!\n"
 369                 "Try increasing KTNUM in makekeys.c\n");
 370         exit(1);
 371     }
 372     for (i = z; --i >= 0;)
 373         offsets[i] = 0;
 374     for (i = 0; i < ksnum; i++) {
 375         val = info[i].val;
 376         first = j = val % z;
 377         while (offsets[j]) {
 378             if (values[j] == val)
 379                 goto skip2;
 380             j += first + 1;
 381             if (j >= z)
 382                 j -= z;
 383         }
 384         offsets[j] = indexes[i] + 2;
 385         values[j] = val;
 386 skip2:  ;
 387     }
 388     printf("\n");
 389     printf("#define VTABLESIZE %d\n", z);
 390     printf("#define VMAXHASH %d\n", best_max_rehash + 1);
 391     printf("\n");
 392     printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
 393     for (i = 0; i < z;) {
 394         printf("0x%.4x", offsets[i]);
 395         i++;
 396         if (i == z)
 397             break;
 398         printf((i & 7) ? ", " : ",\n");
 399     }
 400     printf("\n");
 401     printf("};\n");
 402     printf("\n#endif /* KS_TABLES_H */\n");
 403
 404     exit(0);
 405 }