lib/gen_tables.c

   1 /* gen_tables.c -- Generator of lookup tables.
   2  * Copyright 2008 Red Hat Inc., Durham, North Carolina.
   3  * All Rights Reserved.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  *
  19  * Authors:
  20  *      Miloslav Trmač <mitr@redhat.com>
  21  */
  22
  23 #include "config.h"
  24 #include <assert.h>
  25 #include <ctype.h>
  26 #include <errno.h>
  27 #include <limits.h>
  28 #include <linux/net.h>
  29 #include <stdbool.h>
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <sys/stat.h>
  34 #include <sys/personality.h>
  35 #include <sys/mount.h>
  36 #ifndef MS_DIRSYNC
  37 #include <linux/fs.h>
  38 #endif
  39 #include "gen_tables.h"
  40 #include "libaudit.h"
  41 #include "interpret.h"
  42
  43 /* This is from asm/ipc.h. Copying it for now as some platforms
  44  *  * have broken headers. */
  45 #define SEMOP            1
  46 #define SEMGET           2
  47 #define SEMCTL           3
  48 #define SEMTIMEDOP       4
  49 #define MSGSND          11
  50 #define MSGRCV          12
  51 #define MSGGET          13
  52 #define MSGCTL          14
  53 #define SHMAT           21
  54 #define SHMDT           22
  55 #define SHMGET          23
  56 #define SHMCTL          24
  57
  58
  59 /* The ratio of table size to number of non-empty elements allowed for a
  60    "direct" s2i table; if the ratio would be bigger, bsearch tables are used
  61    instead.
  62
  63    2 looks like a lot at a first glance, but the bsearch tables need twice as
  64    much space per element, so with the ratio equal to 2 the direct table uses
  65    no more memory and is faster. */
  66 #define DIRECT_THRESHOLD 2
  67
  68 /* Allow more than one string defined for a single integer value */
  69 static bool allow_duplicate_ints; /* = false; */
  70
  71 struct value {
  72         int val;
  73         const char *s;
  74         size_t s_offset;
  75         size_t orig_index;
  76 };
  77
  78 /* The mapping to store. */
  79 static struct value values[] = {
  80 #define _S(VAL, S) { (VAL), (S), 0, 0 },
  81 #include TABLE_H
  82 #undef _S
  83 };
  84
  85 #define NUM_VALUES (sizeof(values) / sizeof(*values))
  86
  87 /* Compare two "struct value" members by name. */
  88 static int
  89 cmp_value_strings(const void *xa, const void *xb)
  90 {
  91         const struct value *a, *b;
  92
  93         a = xa;
  94         b = xb;
  95         return strcmp(a->s, b->s);
  96 }
  97
  98 /* Compare two "struct value" members by value. */
  99 static int
 100 cmp_value_vals(const void *xa, const void *xb)
 101 {
 102         const struct value *a, *b;
 103
 104         a = xa;
 105         b = xb;
 106         if (a->val > b->val)
 107                 return 1;
 108         if (a->val < b->val)
 109                 return -1;
 110         /* Preserve the original order if there is an ambiguity, to always use
 111            the first specified value. */
 112         if (a->orig_index > b->orig_index)
 113                 return 1;
 114         if (a->orig_index < b->orig_index)
 115                 return -1;
 116         return 0;
 117 }
 118
 119 /* Compare two "struct value" members by orig_index. */
 120 static int
 121 cmp_value_orig_index(const void *xa, const void *xb)
 122 {
 123         const struct value *a, *b;
 124
 125         a = xa;
 126         b = xb;
 127         if (a->orig_index > b->orig_index)
 128                 return 1;
 129         if (a->orig_index < b->orig_index)
 130                 return -1;
 131         return 0;
 132 }
 133
 134 /* Output the string table, initialize values[*]->s_offset. */
 135 static void
 136 output_strings(const char *prefix)
 137 {
 138         size_t i, offset;
 139
 140         offset = 0;
 141         for (i = 0; i < NUM_VALUES; i++) {
 142                 values[i].s_offset = offset;
 143                 offset += strlen(values[i].s) + 1;
 144         }
 145         printf("static const char %s_strings[] = \"", prefix);
 146         assert(NUM_VALUES > 0);
 147         for (i = 0; i < NUM_VALUES; i++) {
 148                 const char *c;
 149
 150                 if (i != 0 && i % 10 == 0)
 151                         fputs("\"\n"
 152                               "\t\"", stdout);
 153                 for (c = values[i].s; *c != '\0'; c++) {
 154                         assert(*c != '"' && *c != '\\'
 155                                && isprint((unsigned char)*c));
 156                         putc(*c, stdout);
 157                 }
 158                 if (i != NUM_VALUES - 1)
 159                         fputs("\\0", stdout);
 160         }
 161         fputs("\";\n", stdout);
 162 }
 163
 164 /* Output the string to integer mapping code.
 165    Assume strings are all uppsercase or all lowercase if specified by
 166    parameters; in that case, make the search case-insensitive.
 167    values must be sorted by strings. */
 168 static void
 169 output_s2i(const char *prefix, bool uppercase, bool lowercase)
 170 {
 171         size_t i;
 172
 173         for (i = 0; i < NUM_VALUES - 1; i++) {
 174                 assert(strcmp(values[i].s, values[i + 1].s) <= 0);
 175                 if (strcmp(values[i].s, values[i + 1].s) == 0) {
 176                         fprintf(stderr, "Duplicate value `%s': %d, %d\n",
 177                                 values[i].s, values[i].val, values[i + 1].val);
 178                         abort();
 179                 }
 180         }
 181         printf("static const unsigned %s_s2i_s[] = {", prefix);
 182         for (i = 0; i < NUM_VALUES; i++) {
 183                 if (i % 10 == 0)
 184                         fputs("\n\t", stdout);
 185                 assert(values[i].s_offset <= UINT_MAX);
 186                 printf("%zu,", values[i].s_offset);
 187         }
 188         printf("\n"
 189                "};\n"
 190                "static const int %s_s2i_i[] = {", prefix);
 191         for (i = 0; i < NUM_VALUES; i++) {
 192                 if (i % 10 == 0)
 193                         fputs("\n\t", stdout);
 194                 printf("%d,", values[i].val);
 195         }
 196         fputs("\n"
 197               "};\n", stdout);
 198         assert(!(uppercase && lowercase));
 199         if (uppercase) {
 200                 for (i = 0; i < NUM_VALUES; i++) {
 201                         const char *c;
 202
 203                         for (c = values[i].s; *c != '\0'; c++)
 204                                 assert(isascii((unsigned char)*c)
 205                                        && !GT_ISLOWER(*c));
 206                 }
 207         } else if (lowercase) {
 208                 for (i = 0; i < NUM_VALUES; i++) {
 209                         const char *c;
 210
 211                         for (c = values[i].s; *c != '\0'; c++)
 212                                 assert(isascii((unsigned char)*c)
 213                                        && !GT_ISUPPER(*c));
 214                 }
 215         }
 216         if (uppercase || lowercase) {
 217                 printf("static int %s_s2i(const char *s, int *value) {\n"
 218                        "\tsize_t len, i;\n"
 219                        "\tlen = strlen(s);\n"
 220                        "\t{ char copy[len + 1];\n"
 221                        "\tfor (i = 0; i < len; i++) {\n"
 222                        "\t\tchar c = s[i];\n", prefix);
 223                 if (uppercase)
 224                         fputs("\t\tcopy[i] = GT_ISLOWER(c) ? c - 'a' + 'A' "
 225                                                           ": c;\n", stdout);
 226                 else
 227                         fputs("\t\tcopy[i] = GT_ISUPPER(c) ? c - 'A' + 'a' "
 228                                                           ": c;\n", stdout);
 229                 printf("\t}\n"
 230                        "\tcopy[i] = 0;\n"
 231                        "\treturn s2i__(%s_strings, %s_s2i_s, %s_s2i_i, %zu, "
 232                                       "copy, value);\n"
 233                        "\t}\n"
 234                        "}\n", prefix, prefix, prefix, NUM_VALUES);
 235         } else
 236                 printf("static int %s_s2i(const char *s, int *value) {\n"
 237                        "\treturn s2i__(%s_strings, %s_s2i_s, %s_s2i_i, %zu, s, "
 238                                       "value);\n"
 239                        "}\n", prefix, prefix, prefix, prefix, NUM_VALUES);
 240 }
 241
 242 /* Output the string to integer mapping table.
 243    values must be sorted by strings. */
 244 static void
 245 output_i2s(const char *prefix)
 246 {
 247         struct value *unique_values;
 248         int min_val, max_val;
 249         size_t i, n;
 250
 251         assert(NUM_VALUES > 0);
 252         for (i = 0; i < NUM_VALUES - 1; i++) {
 253                 assert(values[i].val <= values[i + 1].val);
 254                 if (!allow_duplicate_ints
 255                     && values[i].val == values[i + 1].val) {
 256                         fprintf(stderr, "Duplicate value %d: `%s', `%s'\n",
 257                                 values[i].val, values[i].s, values[i + 1].s);
 258                         abort();
 259                 }
 260         }
 261
 262         unique_values = malloc(NUM_VALUES * sizeof(*unique_values));
 263         assert(unique_values != NULL);
 264         n = 0;
 265         for (i = 0; i < NUM_VALUES; i++) {
 266                 if (n == 0 || unique_values[n - 1].val != values[i].val) {
 267                         unique_values[n] = values[i];
 268                         n++;
 269                 }
 270         }
 271
 272         min_val = unique_values[0].val;
 273         max_val = unique_values[n - 1].val;
 274         if (((double)max_val - (double)min_val) / n <= DIRECT_THRESHOLD) {
 275                 int next_index;
 276
 277                 printf("static const unsigned %s_i2s_direct[] = {", prefix);
 278                 next_index = min_val;
 279                 i = 0;
 280                 for (;;) {
 281                         if ((next_index - min_val) % 10 == 0)
 282                                 fputs("\n\t", stdout);
 283                         while (unique_values[i].val < next_index)
 284                                 /* This can happen if (allow_duplicate_ints) */
 285                                 i++;
 286                         if (unique_values[i].val == next_index) {
 287                                 assert(unique_values[i].s_offset <= UINT_MAX);
 288                                 printf("%zu,", unique_values[i].s_offset);
 289                         } else
 290                                 fputs("-1u,", stdout);
 291                         if (next_index == max_val)
 292                                 /* Done like this to avoid integer overflow */
 293                                 break;
 294                         next_index++;
 295                 }
 296                 printf("\n"
 297                        "};\n"
 298                        "static const char *%s_i2s(int v) {\n"
 299                        "\treturn i2s_direct__(%s_strings, %s_i2s_direct, %d, "
 300                                              "%d, v);\n"
 301                        "}\n", prefix, prefix, prefix, min_val, max_val);
 302         } else {
 303                 printf("static const int %s_i2s_i[] = {", prefix);
 304                 for (i = 0; i < n; i++) {
 305                         if (i % 10 == 0)
 306                                 fputs("\n\t", stdout);
 307                         printf("%d,", unique_values[i].val);
 308                 }
 309                 printf("\n"
 310                        "};\n"
 311                        "static const unsigned %s_i2s_s[] = {", prefix);
 312                 for (i = 0; i < n; i++) {
 313                         if (i % 10 == 0)
 314                                 fputs("\n\t", stdout);
 315                         assert(unique_values[i].s_offset <= UINT_MAX);
 316                         printf("%zu,", unique_values[i].s_offset);
 317                 }
 318                 printf("\n"
 319                        "};\n"
 320                        "static const char *%s_i2s(int v) {\n"
 321                        "\treturn i2s_bsearch__(%s_strings, %s_i2s_i, %s_i2s_s, "
 322                               "%zu, v);\n"
 323                        "}\n", prefix, prefix, prefix, prefix, n);
 324         }
 325         free(unique_values);
 326 }
 327
 328 /* Output the string to integer mapping table as a transtab[].
 329    values must be sorted in the desired order. */
 330 static void
 331 output_i2s_transtab(const char *prefix)
 332 {
 333         size_t i;
 334         char *uc_prefix;
 335
 336         printf("static const struct transtab %s_table[] = {", prefix);
 337         for (i = 0; i < NUM_VALUES; i++) {
 338                 if (i % 10 == 0)
 339                         fputs("\n\t", stdout);
 340                 printf("{%d,%zu},", values[i].val, values[i].s_offset);
 341         }
 342         uc_prefix = strdup(prefix);
 343         assert(uc_prefix != NULL);
 344         for (i = 0; uc_prefix[i] != '\0'; i++)
 345                 uc_prefix[i] = toupper((unsigned char)uc_prefix[i]);
 346         printf("\n"
 347                "};\n"
 348                "#define %s_NUM_ENTRIES "
 349                "(sizeof(%s_table) / sizeof(*%s_table))\n", uc_prefix, prefix,
 350                prefix);
 351         free(uc_prefix);
 352 }
 353
 354 int
 355 main(int argc, char **argv)
 356 {
 357         bool gen_i2s, gen_i2s_transtab, gen_s2i, uppercase, lowercase;
 358         char *prefix;
 359         size_t i;
 360
 361         /* This is required by gen_tables.h */
 362         assert(NUM_VALUES <= (SSIZE_MAX / 2 + 1));
 363
 364         /* To make sure GT_ISUPPER and GT_ISLOWER work. */
 365         assert('Z' == 'A' + 25 && 'z' == 'a' + 25);
 366         gen_i2s = false;
 367         gen_i2s_transtab = false;
 368         gen_s2i = false;
 369         uppercase = false;
 370         lowercase = false;
 371         prefix = NULL;
 372         assert (argc > 1);
 373         for (i = 1; i < (size_t)argc; i++) {
 374                 if (strcmp(argv[i], "--i2s") == 0)
 375                         gen_i2s = true;
 376                 else if (strcmp(argv[i], "--i2s-transtab") == 0)
 377                         gen_i2s_transtab = true;
 378                 else if (strcmp(argv[i], "--s2i") == 0)
 379                         gen_s2i = true;
 380                 else if (strcmp(argv[i], "--uppercase") == 0)
 381                         uppercase = true;
 382                 else if (strcmp(argv[i], "--lowercase") == 0)
 383                         lowercase = true;
 384                 else if (strcmp(argv[i], "--duplicate-ints") == 0)
 385                         allow_duplicate_ints = true;
 386                 else {
 387                         assert(*argv[i] != '-');
 388                         assert(prefix == NULL);
 389                         prefix = argv[i];
 390                 }
 391         }
 392         assert(prefix != NULL);
 393         assert(!(uppercase && lowercase));
 394
 395         printf("/* This is a generated file, see Makefile.am for its "
 396                "inputs. */\n");
 397         for (i = 0; i < NUM_VALUES; i++)
 398                 values[i].orig_index = i;
 399         qsort(values, NUM_VALUES, sizeof(*values), cmp_value_strings);
 400         /* FIXME? if (gen_s2i), sort the strings in some other order
 401            (e.g. "first 4 nodes in BFS of the bsearch tree first") to use the
 402            cache better. */
 403         /* FIXME? If the only thing generated is a transtab, keep the strings
 404            in the original order to use the cache better. */
 405         output_strings(prefix);
 406         if (gen_s2i)
 407                 output_s2i(prefix, uppercase, lowercase);
 408         if (gen_i2s) {
 409                 qsort(values, NUM_VALUES, sizeof(*values), cmp_value_vals);
 410                 output_i2s(prefix);
 411         }
 412         if (gen_i2s_transtab) {
 413                 qsort(values, NUM_VALUES, sizeof(*values),
 414                       cmp_value_orig_index);
 415                 output_i2s_transtab(prefix);
 416         }
 417         return EXIT_SUCCESS;
 418 }