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 "xkbcommon/xkbcommon.h"
  32
  33 #include <X11/keysymdef.h>
  34 #include <inttypes.h>
  35 #include <stdio.h>
  36 #include <stdlib.h>
  37 #include <string.h>
  38
  39 typedef uint32_t Signature;
  40
  41 #define KTNUM 4000
  42
  43 static struct info {
  44     char        *name;
  45     xkb_keysym_t val;
  46 } info[KTNUM];
  47
  48 #define MIN_REHASH 15
  49 #define MATCHES 10
  50
  51 static char tab[KTNUM];
  52 static unsigned short offsets[KTNUM];
  53 static unsigned short indexes[KTNUM];
  54 static xkb_keysym_t values[KTNUM];
  55 static int ksnum = 0;
  56
  57 static int
  58 parse_line(const char *buf, char *key, xkb_keysym_t *val, char *prefix)
  59 {
  60     int i;
  61     char alias[128];
  62     char *tmp, *tmpa;
  63
  64     /* See if we can catch a straight XK_foo 0x1234-style definition first;
  65      * the trickery around tmp is to account for prefices. */
  66     i = sscanf(buf, "#define %127s 0x%lx", key, val);
  67     if (i == 2 && (tmp = strstr(key, "XK_"))) {
  68         memcpy(prefix, key, tmp - key);
  69         prefix[tmp - key] = '\0';
  70         tmp += 3;
  71         memmove(key, tmp, strlen(tmp) + 1);
  72         return 1;
  73     }
  74
  75     /* Now try to catch alias (XK_foo XK_bar) definitions, and resolve them
  76      * immediately: if the target is in the form XF86XK_foo, we need to
  77      * canonicalise this to XF86foo before we do the lookup. */
  78     i = sscanf(buf, "#define %127s %127s", key, alias);
  79     if (i == 2 && (tmp = strstr(key, "XK_")) && (tmpa = strstr(alias, "XK_"))) {
  80         memcpy(prefix, key, tmp - key);
  81         prefix[tmp - key] = '\0';
  82         tmp += 3;
  83         memmove(key, tmp, strlen(tmp) + 1);
  84         memmove(tmpa, tmpa + 3, strlen(tmpa + 3) + 1);
  85
  86         for (i = ksnum - 1; i >= 0; i--) {
  87             if (strcmp(info[i].name, alias) == 0) {
  88                 *val = info[i].val;
  89                 return 1;
  90             }
  91         }
  92
  93         fprintf(stderr, "can't find matching definition %s for keysym %s%s\n",
  94                 alias, prefix, key);
  95     }
  96
  97     return 0;
  98 }
  99
 100 int
 101 main(int argc, char *argv[])
 102 {
 103     FILE *fptr;
 104     int max_rehash;
 105     Signature sig;
 106     int i, j, k, l, z;
 107     char *name;
 108     char c;
 109     int first;
 110     int best_max_rehash;
 111     int best_z = 0;
 112     int num_found;
 113     xkb_keysym_t val;
 114     char key[128], prefix[128];
 115     char buf[1024];
 116
 117     for (l = 1; l < argc; l++) {
 118         fptr = fopen(argv[l], "r");
 119         if (!fptr) {
 120             fprintf(stderr, "couldn't open %s\n", argv[l]);
 121             continue;
 122         }
 123
 124         while (fgets(buf, sizeof(buf), fptr)) {
 125             if (!parse_line(buf, key, &val, prefix))
 126                 continue;
 127
 128             if (val == XK_VoidSymbol)
 129                 val = 0;
 130             if (val > 0x1fffffff) {
 131                 fprintf(stderr, "ignoring illegal keysym (%s, %lx)\n", key,
 132                         val);
 133                 continue;
 134             }
 135
 136             name = malloc(strlen(prefix) + strlen(key) + 1);
 137             if (!name) {
 138                 fprintf(stderr, "makekeys: out of memory!\n");
 139                 exit(1);
 140             }
 141             sprintf(name, "%s%s", prefix, key);
 142             info[ksnum].name = name;
 143             info[ksnum].val = val;
 144             ksnum++;
 145             if (ksnum == KTNUM) {
 146                 fprintf(stderr, "makekeys: too many keysyms!\n");
 147                 exit(1);
 148             }
 149         }
 150
 151         fclose(fptr);
 152     }
 153
 154     /* Special case NoSymbol. */
 155     info[ksnum].name = strdup("NoSymbol");
 156     info[ksnum].val = 0L;
 157     ksnum++;
 158
 159     printf("/* This file is generated from keysymdef.h. */\n");
 160     printf("/* Do not edit. */\n");
 161     printf("\n");
 162
 163     best_max_rehash = ksnum;
 164     num_found = 0;
 165     for (z = ksnum; z < KTNUM; z++) {
 166         max_rehash = 0;
 167         for (name = tab, i = z; --i >= 0;)
 168             *name++ = 0;
 169         for (i = 0; i < ksnum; i++) {
 170             name = info[i].name;
 171             sig = 0;
 172             while ((c = *name++))
 173                 sig = (sig << 1) + c;
 174             first = j = sig % z;
 175             for (k = 0; tab[j]; k++) {
 176                 j += first + 1;
 177                 if (j >= z)
 178                     j -= z;
 179                 if (j == first)
 180                     goto next1;
 181             }
 182             tab[j] = 1;
 183             if (k > max_rehash)
 184                 max_rehash = k;
 185         }
 186         if (max_rehash < MIN_REHASH) {
 187             if (max_rehash < best_max_rehash) {
 188                 best_max_rehash = max_rehash;
 189                 best_z = z;
 190             }
 191             num_found++;
 192             if (num_found >= MATCHES)
 193                 break;
 194         }
 195 next1:  ;
 196     }
 197
 198     z = best_z;
 199     printf("#ifndef KS_TABLES_H\n");
 200     printf("#define KS_TABLES_H\n\n");
 201     printf("static const unsigned char _XkeyTable[] = {\n");
 202     if (z == 0) {
 203         fprintf(stderr, "makekeys: failed to find small enough hash!\n"
 204                 "Try increasing KTNUM in makekeys.c\n");
 205         exit(1);
 206     }
 207     printf("0,\n");
 208     k = 1;
 209     for (i = 0; i < ksnum; i++) {
 210         name = info[i].name;
 211         sig = 0;
 212         while ((c = *name++))
 213             sig = (sig << 1) + c;
 214         first = j = sig % z;
 215         while (offsets[j]) {
 216             j += first + 1;
 217             if (j >= z)
 218                 j -= z;
 219         }
 220         offsets[j] = k;
 221         indexes[i] = k;
 222         val = info[i].val;
 223         printf("0x%.2"PRIx32", 0x%.2"PRIx32", 0x%.2lx, 0x%.2lx, 0x%.2lx, 0x%.2lx, ",
 224                (sig >> 8) & 0xff, sig & 0xff,
 225                (val >> 24) & 0xff, (val >> 16) & 0xff,
 226                (val >> 8) & 0xff, val & 0xff);
 227         for (name = info[i].name, k += 7; (c = *name++); k++)
 228             printf("'%c',", c);
 229         printf((i == (ksnum-1)) ? "0\n" : "0,\n");
 230     }
 231     printf("};\n");
 232     printf("\n");
 233     printf("#define KTABLESIZE %d\n", z);
 234     printf("#define KMAXHASH %d\n", best_max_rehash + 1);
 235     printf("\n");
 236     printf("static const unsigned short hashString[KTABLESIZE] = {\n");
 237     for (i = 0; i < z;) {
 238         printf("0x%.4x", offsets[i]);
 239         i++;
 240         if (i == z)
 241             break;
 242         printf((i & 7) ? ", " : ",\n");
 243     }
 244     printf("\n");
 245     printf("};\n");
 246
 247     best_max_rehash = ksnum;
 248     num_found = 0;
 249     for (z = ksnum; z < KTNUM; z++) {
 250         max_rehash = 0;
 251         for (name = tab, i = z; --i >= 0;)
 252             *name++ = 0;
 253         for (i = 0; i < ksnum; i++) {
 254             val = info[i].val;
 255             first = j = val % z;
 256             for (k = 0; tab[j]; k++) {
 257                 if (values[j] == val)
 258                     goto skip1;
 259                 j += first + 1;
 260                 if (j >= z)
 261                     j -= z;
 262                 if (j == first)
 263                     goto next2;
 264             }
 265             tab[j] = 1;
 266             values[j] = val;
 267             if (k > max_rehash)
 268                 max_rehash = k;
 269 skip1:  ;
 270         }
 271         if (max_rehash < MIN_REHASH) {
 272             if (max_rehash < best_max_rehash) {
 273                 best_max_rehash = max_rehash;
 274                 best_z = z;
 275             }
 276             num_found++;
 277             if (num_found >= MATCHES)
 278                 break;
 279         }
 280 next2:  ;
 281     }
 282
 283     z = best_z;
 284     if (z == 0) {
 285         fprintf(stderr, "makekeys: failed to find small enough hash!\n"
 286                 "Try increasing KTNUM in makekeys.c\n");
 287         exit(1);
 288     }
 289     for (i = z; --i >= 0;)
 290         offsets[i] = 0;
 291     for (i = 0; i < ksnum; i++) {
 292         val = info[i].val;
 293         first = j = val % z;
 294         while (offsets[j]) {
 295             if (values[j] == val)
 296                 goto skip2;
 297             j += first + 1;
 298             if (j >= z)
 299                 j -= z;
 300         }
 301         offsets[j] = indexes[i] + 2;
 302         values[j] = val;
 303 skip2:  ;
 304     }
 305     printf("\n");
 306     printf("#define VTABLESIZE %d\n", z);
 307     printf("#define VMAXHASH %d\n", best_max_rehash + 1);
 308     printf("\n");
 309     printf("static const unsigned short hashKeysym[VTABLESIZE] = {\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     printf("\n#endif /* KS_TABLES_H */\n");
 320
 321     exit(0);
 322 }