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