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     int max_rehash;
 174     Signature sig;
 175     int i, j, k, z;
 176     char *name;
 177     char c;
 178     int first;
 179     int best_max_rehash;
 180     int best_z = 0;
 181     int num_found;
 182     KeySym val;
 183     char key[128];
 184     char buf[1024];
 185
 186
 187     while (fgets(buf, sizeof(buf), stdin)) {
 188         int ret;
 189
 190         /* Manage keysyms from keysymdef.h */
 191         ret = get_keysym(buf, key, ksnum);
 192         if (!ret) {
 193             ret = get_keysym_alias(buf, key, ksnum);
 194             if (ret == -1)
 195                 continue;
 196         }
 197
 198         /* Manage keysyms from XF86keysym.h */
 199         if (!ret)
 200             ret = get_xf86_keysym(buf, key, sizeof(key), ksnum);
 201         if (!ret) {
 202             ret = get_xf86_keysym_alias(buf, key, sizeof(key), ksnum);
 203             if (ret < 1)
 204                 continue;
 205         }
 206
 207         if (info[ksnum].val > 0x1fffffff) {
 208             fprintf(stderr,
 209                     "ignoring illegal keysym (%s), remove it from .h file!\n",
 210                     key);
 211             continue;
 212         }
 213         name = malloc((unsigned)strlen(key) + 1);
 214         if (!name) {
 215             fprintf(stderr, "makekeys: out of memory!\n");
 216             exit(1);
 217         }
 218         (void)strcpy(name, key);
 219         info[ksnum].name = name;
 220         ksnum++;
 221         if (ksnum == KTNUM) {
 222             fprintf(stderr, "makekeys: too many keysyms!\n");
 223             exit(1);
 224         }
 225     }
 226
 227     /* Special case NoSymbol. */
 228     info[ksnum].name = strdup("NoSymbol");
 229     info[ksnum].val = 0L;
 230     ksnum++;
 231
 232     printf("/* This file is generated from keysymdef.h. */\n");
 233     printf("/* Do not edit. */\n");
 234     printf("\n");
 235
 236     best_max_rehash = ksnum;
 237     num_found = 0;
 238     for (z = ksnum; z < KTNUM; z++) {
 239         max_rehash = 0;
 240         for (name = tab, i = z; --i >= 0;)
 241             *name++ = 0;
 242         for (i = 0; i < ksnum; i++) {
 243             name = info[i].name;
 244             sig = 0;
 245             while ((c = *name++))
 246                 sig = (sig << 1) + c;
 247             first = j = sig % z;
 248             for (k = 0; tab[j]; k++) {
 249                 j += first + 1;
 250                 if (j >= z)
 251                     j -= z;
 252                 if (j == first)
 253                     goto next1;
 254             }
 255             tab[j] = 1;
 256             if (k > max_rehash)
 257                 max_rehash = k;
 258         }
 259         if (max_rehash < MIN_REHASH) {
 260             if (max_rehash < best_max_rehash) {
 261                 best_max_rehash = max_rehash;
 262                 best_z = z;
 263             }
 264             num_found++;
 265             if (num_found >= MATCHES)
 266                 break;
 267         }
 268 next1:  ;
 269     }
 270
 271     z = best_z;
 272     printf("#ifndef KS_TABLES_H\n");
 273     printf("#define KS_TABLES_H\n\n");
 274     printf("static const unsigned char _XkeyTable[] = {\n");
 275     if (z == 0) {
 276         fprintf(stderr, "makekeys: failed to find small enough hash!\n"
 277                 "Try increasing KTNUM in makekeys.c\n");
 278         exit(1);
 279     }
 280     printf("0,\n");
 281     k = 1;
 282     for (i = 0; i < ksnum; i++) {
 283         name = info[i].name;
 284         sig = 0;
 285         while ((c = *name++))
 286             sig = (sig << 1) + c;
 287         first = j = sig % z;
 288         while (offsets[j]) {
 289             j += first + 1;
 290             if (j >= z)
 291                 j -= z;
 292         }
 293         offsets[j] = k;
 294         indexes[i] = k;
 295         val = info[i].val;
 296         printf("0x%.2"PRIx32", 0x%.2"PRIx32", 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
 297                (sig >> 8) & 0xff, sig & 0xff,
 298                (val >> 24) & 0xff, (val >> 16) & 0xff,
 299                (val >> 8) & 0xff, val & 0xff);
 300         for (name = info[i].name, k += 7; (c = *name++); k++)
 301             printf("'%c',", c);
 302         printf((i == (ksnum-1)) ? "0\n" : "0,\n");
 303     }
 304     printf("};\n");
 305     printf("\n");
 306     printf("#define KTABLESIZE %d\n", z);
 307     printf("#define KMAXHASH %d\n", best_max_rehash + 1);
 308     printf("\n");
 309     printf("static const unsigned short hashString[KTABLESIZE] = {\n");
 310     for (i = 0; i < z;) {
 311         printf("0x%.4x", offsets[i]);
 312         i++;
 313         if (i == z)
 314             break;
 315         printf((i & 7) ? ", " : ",\n");
 316     }
 317     printf("\n");
 318     printf("};\n");
 319
 320     best_max_rehash = ksnum;
 321     num_found = 0;
 322     for (z = ksnum; z < KTNUM; z++) {
 323         max_rehash = 0;
 324         for (name = tab, i = z; --i >= 0;)
 325             *name++ = 0;
 326         for (i = 0; i < ksnum; i++) {
 327             val = info[i].val;
 328             first = j = val % z;
 329             for (k = 0; tab[j]; k++) {
 330                 if (values[j] == val)
 331                     goto skip1;
 332                 j += first + 1;
 333                 if (j >= z)
 334                     j -= z;
 335                 if (j == first)
 336                     goto next2;
 337             }
 338             tab[j] = 1;
 339             values[j] = val;
 340             if (k > max_rehash)
 341                 max_rehash = k;
 342 skip1:  ;
 343         }
 344         if (max_rehash < MIN_REHASH) {
 345             if (max_rehash < best_max_rehash) {
 346                 best_max_rehash = max_rehash;
 347                 best_z = z;
 348             }
 349             num_found++;
 350             if (num_found >= MATCHES)
 351                 break;
 352         }
 353 next2:  ;
 354     }
 355
 356     z = best_z;
 357     if (z == 0) {
 358         fprintf(stderr, "makekeys: failed to find small enough hash!\n"
 359                 "Try increasing KTNUM in makekeys.c\n");
 360         exit(1);
 361     }
 362     for (i = z; --i >= 0;)
 363         offsets[i] = 0;
 364     for (i = 0; i < ksnum; i++) {
 365         val = info[i].val;
 366         first = j = val % z;
 367         while (offsets[j]) {
 368             if (values[j] == val)
 369                 goto skip2;
 370             j += first + 1;
 371             if (j >= z)
 372                 j -= z;
 373         }
 374         offsets[j] = indexes[i] + 2;
 375         values[j] = val;
 376 skip2:  ;
 377     }
 378     printf("\n");
 379     printf("#define VTABLESIZE %d\n", z);
 380     printf("#define VMAXHASH %d\n", best_max_rehash + 1);
 381     printf("\n");
 382     printf("static const unsigned short hashKeysym[VTABLESIZE] = {\n");
 383     for (i = 0; i < z;) {
 384         printf("0x%.4x", offsets[i]);
 385         i++;
 386         if (i == z)
 387             break;
 388         printf((i & 7) ? ", " : ",\n");
 389     }
 390     printf("\n");
 391     printf("};\n");
 392     printf("\n#endif /* KS_TABLES_H */\n");
 393
 394     exit(0);
 395 }