scripts/asn1_compiler.c

   1 /* Simplified ASN.1 notation parser
   2  *
   3  * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
   4  * Written by David Howells (dhowells@redhat.com)
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public Licence
   8  * as published by the Free Software Foundation; either version
   9  * 2 of the Licence, or (at your option) any later version.
  10  */
  11
  12 #include <stdarg.h>
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <stdint.h>
  16 #include <stdbool.h>
  17 #include <string.h>
  18 #include <ctype.h>
  19 #include <unistd.h>
  20 #include <fcntl.h>
  21 #include <sys/stat.h>
  22 #include <linux/asn1_ber_bytecode.h>
  23
  24 enum token_type {
  25         DIRECTIVE_ABSENT,
  26         DIRECTIVE_ALL,
  27         DIRECTIVE_ANY,
  28         DIRECTIVE_APPLICATION,
  29         DIRECTIVE_AUTOMATIC,
  30         DIRECTIVE_BEGIN,
  31         DIRECTIVE_BIT,
  32         DIRECTIVE_BMPString,
  33         DIRECTIVE_BOOLEAN,
  34         DIRECTIVE_BY,
  35         DIRECTIVE_CHARACTER,
  36         DIRECTIVE_CHOICE,
  37         DIRECTIVE_CLASS,
  38         DIRECTIVE_COMPONENT,
  39         DIRECTIVE_COMPONENTS,
  40         DIRECTIVE_CONSTRAINED,
  41         DIRECTIVE_CONTAINING,
  42         DIRECTIVE_DEFAULT,
  43         DIRECTIVE_DEFINED,
  44         DIRECTIVE_DEFINITIONS,
  45         DIRECTIVE_EMBEDDED,
  46         DIRECTIVE_ENCODED,
  47         DIRECTIVE_ENCODING_CONTROL,
  48         DIRECTIVE_END,
  49         DIRECTIVE_ENUMERATED,
  50         DIRECTIVE_EXCEPT,
  51         DIRECTIVE_EXPLICIT,
  52         DIRECTIVE_EXPORTS,
  53         DIRECTIVE_EXTENSIBILITY,
  54         DIRECTIVE_EXTERNAL,
  55         DIRECTIVE_FALSE,
  56         DIRECTIVE_FROM,
  57         DIRECTIVE_GeneralString,
  58         DIRECTIVE_GeneralizedTime,
  59         DIRECTIVE_GraphicString,
  60         DIRECTIVE_IA5String,
  61         DIRECTIVE_IDENTIFIER,
  62         DIRECTIVE_IMPLICIT,
  63         DIRECTIVE_IMPLIED,
  64         DIRECTIVE_IMPORTS,
  65         DIRECTIVE_INCLUDES,
  66         DIRECTIVE_INSTANCE,
  67         DIRECTIVE_INSTRUCTIONS,
  68         DIRECTIVE_INTEGER,
  69         DIRECTIVE_INTERSECTION,
  70         DIRECTIVE_ISO646String,
  71         DIRECTIVE_MAX,
  72         DIRECTIVE_MIN,
  73         DIRECTIVE_MINUS_INFINITY,
  74         DIRECTIVE_NULL,
  75         DIRECTIVE_NumericString,
  76         DIRECTIVE_OBJECT,
  77         DIRECTIVE_OCTET,
  78         DIRECTIVE_OF,
  79         DIRECTIVE_OPTIONAL,
  80         DIRECTIVE_ObjectDescriptor,
  81         DIRECTIVE_PATTERN,
  82         DIRECTIVE_PDV,
  83         DIRECTIVE_PLUS_INFINITY,
  84         DIRECTIVE_PRESENT,
  85         DIRECTIVE_PRIVATE,
  86         DIRECTIVE_PrintableString,
  87         DIRECTIVE_REAL,
  88         DIRECTIVE_RELATIVE_OID,
  89         DIRECTIVE_SEQUENCE,
  90         DIRECTIVE_SET,
  91         DIRECTIVE_SIZE,
  92         DIRECTIVE_STRING,
  93         DIRECTIVE_SYNTAX,
  94         DIRECTIVE_T61String,
  95         DIRECTIVE_TAGS,
  96         DIRECTIVE_TRUE,
  97         DIRECTIVE_TeletexString,
  98         DIRECTIVE_UNION,
  99         DIRECTIVE_UNIQUE,
 100         DIRECTIVE_UNIVERSAL,
 101         DIRECTIVE_UTCTime,
 102         DIRECTIVE_UTF8String,
 103         DIRECTIVE_UniversalString,
 104         DIRECTIVE_VideotexString,
 105         DIRECTIVE_VisibleString,
 106         DIRECTIVE_WITH,
 107         NR__DIRECTIVES,
 108         TOKEN_ASSIGNMENT = NR__DIRECTIVES,
 109         TOKEN_OPEN_CURLY,
 110         TOKEN_CLOSE_CURLY,
 111         TOKEN_OPEN_SQUARE,
 112         TOKEN_CLOSE_SQUARE,
 113         TOKEN_OPEN_ACTION,
 114         TOKEN_CLOSE_ACTION,
 115         TOKEN_COMMA,
 116         TOKEN_NUMBER,
 117         TOKEN_TYPE_NAME,
 118         TOKEN_ELEMENT_NAME,
 119         NR__TOKENS
 120 };
 121
 122 static const unsigned char token_to_tag[NR__TOKENS] = {
 123         /* EOC goes first */
 124         [DIRECTIVE_BOOLEAN]             = ASN1_BOOL,
 125         [DIRECTIVE_INTEGER]             = ASN1_INT,
 126         [DIRECTIVE_BIT]                 = ASN1_BTS,
 127         [DIRECTIVE_OCTET]               = ASN1_OTS,
 128         [DIRECTIVE_NULL]                = ASN1_NULL,
 129         [DIRECTIVE_OBJECT]              = ASN1_OID,
 130         [DIRECTIVE_ObjectDescriptor]    = ASN1_ODE,
 131         [DIRECTIVE_EXTERNAL]            = ASN1_EXT,
 132         [DIRECTIVE_REAL]                = ASN1_REAL,
 133         [DIRECTIVE_ENUMERATED]          = ASN1_ENUM,
 134         [DIRECTIVE_EMBEDDED]            = 0,
 135         [DIRECTIVE_UTF8String]          = ASN1_UTF8STR,
 136         [DIRECTIVE_RELATIVE_OID]        = ASN1_RELOID,
 137         /* 14 */
 138         /* 15 */
 139         [DIRECTIVE_SEQUENCE]            = ASN1_SEQ,
 140         [DIRECTIVE_SET]                 = ASN1_SET,
 141         [DIRECTIVE_NumericString]       = ASN1_NUMSTR,
 142         [DIRECTIVE_PrintableString]     = ASN1_PRNSTR,
 143         [DIRECTIVE_T61String]           = ASN1_TEXSTR,
 144         [DIRECTIVE_TeletexString]       = ASN1_TEXSTR,
 145         [DIRECTIVE_VideotexString]      = ASN1_VIDSTR,
 146         [DIRECTIVE_IA5String]           = ASN1_IA5STR,
 147         [DIRECTIVE_UTCTime]             = ASN1_UNITIM,
 148         [DIRECTIVE_GeneralizedTime]     = ASN1_GENTIM,
 149         [DIRECTIVE_GraphicString]       = ASN1_GRASTR,
 150         [DIRECTIVE_VisibleString]       = ASN1_VISSTR,
 151         [DIRECTIVE_GeneralString]       = ASN1_GENSTR,
 152         [DIRECTIVE_UniversalString]     = ASN1_UNITIM,
 153         [DIRECTIVE_CHARACTER]           = ASN1_CHRSTR,
 154         [DIRECTIVE_BMPString]           = ASN1_BMPSTR,
 155 };
 156
 157 static const char asn1_classes[4][5] = {
 158         [ASN1_UNIV]     = "UNIV",
 159         [ASN1_APPL]     = "APPL",
 160         [ASN1_CONT]     = "CONT",
 161         [ASN1_PRIV]     = "PRIV"
 162 };
 163
 164 static const char asn1_methods[2][5] = {
 165         [ASN1_UNIV]     = "PRIM",
 166         [ASN1_APPL]     = "CONS"
 167 };
 168
 169 static const char *const asn1_universal_tags[32] = {
 170         "EOC",
 171         "BOOL",
 172         "INT",
 173         "BTS",
 174         "OTS",
 175         "NULL",
 176         "OID",
 177         "ODE",
 178         "EXT",
 179         "REAL",
 180         "ENUM",
 181         "EPDV",
 182         "UTF8STR",
 183         "RELOID",
 184         NULL,           /* 14 */
 185         NULL,           /* 15 */
 186         "SEQ",
 187         "SET",
 188         "NUMSTR",
 189         "PRNSTR",
 190         "TEXSTR",
 191         "VIDSTR",
 192         "IA5STR",
 193         "UNITIM",
 194         "GENTIM",
 195         "GRASTR",
 196         "VISSTR",
 197         "GENSTR",
 198         "UNISTR",
 199         "CHRSTR",
 200         "BMPSTR",
 201         NULL            /* 31 */
 202 };
 203
 204 static const char *filename;
 205 static const char *grammar_name;
 206 static const char *outputname;
 207 static const char *headername;
 208
 209 static const char *const directives[NR__DIRECTIVES] = {
 210 #define _(X) [DIRECTIVE_##X] = #X
 211         _(ABSENT),
 212         _(ALL),
 213         _(ANY),
 214         _(APPLICATION),
 215         _(AUTOMATIC),
 216         _(BEGIN),
 217         _(BIT),
 218         _(BMPString),
 219         _(BOOLEAN),
 220         _(BY),
 221         _(CHARACTER),
 222         _(CHOICE),
 223         _(CLASS),
 224         _(COMPONENT),
 225         _(COMPONENTS),
 226         _(CONSTRAINED),
 227         _(CONTAINING),
 228         _(DEFAULT),
 229         _(DEFINED),
 230         _(DEFINITIONS),
 231         _(EMBEDDED),
 232         _(ENCODED),
 233         [DIRECTIVE_ENCODING_CONTROL] = "ENCODING-CONTROL",
 234         _(END),
 235         _(ENUMERATED),
 236         _(EXCEPT),
 237         _(EXPLICIT),
 238         _(EXPORTS),
 239         _(EXTENSIBILITY),
 240         _(EXTERNAL),
 241         _(FALSE),
 242         _(FROM),
 243         _(GeneralString),
 244         _(GeneralizedTime),
 245         _(GraphicString),
 246         _(IA5String),
 247         _(IDENTIFIER),
 248         _(IMPLICIT),
 249         _(IMPLIED),
 250         _(IMPORTS),
 251         _(INCLUDES),
 252         _(INSTANCE),
 253         _(INSTRUCTIONS),
 254         _(INTEGER),
 255         _(INTERSECTION),
 256         _(ISO646String),
 257         _(MAX),
 258         _(MIN),
 259         [DIRECTIVE_MINUS_INFINITY] = "MINUS-INFINITY",
 260         [DIRECTIVE_NULL] = "NULL",
 261         _(NumericString),
 262         _(OBJECT),
 263         _(OCTET),
 264         _(OF),
 265         _(OPTIONAL),
 266         _(ObjectDescriptor),
 267         _(PATTERN),
 268         _(PDV),
 269         [DIRECTIVE_PLUS_INFINITY] = "PLUS-INFINITY",
 270         _(PRESENT),
 271         _(PRIVATE),
 272         _(PrintableString),
 273         _(REAL),
 274         [DIRECTIVE_RELATIVE_OID] = "RELATIVE-OID",
 275         _(SEQUENCE),
 276         _(SET),
 277         _(SIZE),
 278         _(STRING),
 279         _(SYNTAX),
 280         _(T61String),
 281         _(TAGS),
 282         _(TRUE),
 283         _(TeletexString),
 284         _(UNION),
 285         _(UNIQUE),
 286         _(UNIVERSAL),
 287         _(UTCTime),
 288         _(UTF8String),
 289         _(UniversalString),
 290         _(VideotexString),
 291         _(VisibleString),
 292         _(WITH)
 293 };
 294
 295 struct action {
 296         struct action   *next;
 297         unsigned char   index;
 298         char            name[];
 299 };
 300
 301 static struct action *action_list;
 302 static unsigned nr_actions;
 303
 304 struct token {
 305         unsigned short  line;
 306         enum token_type token_type : 8;
 307         unsigned char   size;
 308         struct action   *action;
 309         const char      *value;
 310         struct type     *type;
 311 };
 312
 313 static struct token *token_list;
 314 static unsigned nr_tokens;
 315 static bool verbose_opt;
 316 static bool debug_opt;
 317
 318 #define verbose(fmt, ...) do { if (verbose_opt) printf(fmt, ## __VA_ARGS__); } while (0)
 319 #define debug(fmt, ...) do { if (debug_opt) printf(fmt, ## __VA_ARGS__); } while (0)
 320
 321 static int directive_compare(const void *_key, const void *_pdir)
 322 {
 323         const struct token *token = _key;
 324         const char *const *pdir = _pdir, *dir = *pdir;
 325         size_t dlen, clen;
 326         int val;
 327
 328         dlen = strlen(dir);
 329         clen = (dlen < token->size) ? dlen : token->size;
 330
 331         //debug("cmp(%*.*s,%s) = ",
 332         //       (int)token->size, (int)token->size, token->value,
 333         //       dir);
 334
 335         val = memcmp(token->value, dir, clen);
 336         if (val != 0) {
 337                 //debug("%d [cmp]\n", val);
 338                 return val;
 339         }
 340
 341         if (dlen == token->size) {
 342                 //debug("0\n");
 343                 return 0;
 344         }
 345         //debug("%d\n", (int)dlen - (int)token->size);
 346         return dlen - token->size; /* shorter -> negative */
 347 }
 348
 349 /*
 350  * Tokenise an ASN.1 grammar
 351  */
 352 static void tokenise(char *buffer, char *end)
 353 {
 354         struct token *tokens;
 355         char *line, *nl, *p, *q;
 356         unsigned tix, lineno;
 357
 358         /* Assume we're going to have half as many tokens as we have
 359          * characters
 360          */
 361         token_list = tokens = calloc((end - buffer) / 2, sizeof(struct token));
 362         if (!tokens) {
 363                 perror(NULL);
 364                 exit(1);
 365         }
 366         tix = 0;
 367
 368         lineno = 0;
 369         while (buffer < end) {
 370                 /* First of all, break out a line */
 371                 lineno++;
 372                 line = buffer;
 373                 nl = memchr(line, '\n', end - buffer);
 374                 if (!nl) {
 375                         buffer = nl = end;
 376                 } else {
 377                         buffer = nl + 1;
 378                         *nl = '\0';
 379                 }
 380
 381                 /* Remove "--" comments */
 382                 p = line;
 383         next_comment:
 384                 while ((p = memchr(p, '-', nl - p))) {
 385                         if (p[1] == '-') {
 386                                 /* Found a comment; see if there's a terminator */
 387                                 q = p + 2;
 388                                 while ((q = memchr(q, '-', nl - q))) {
 389                                         if (q[1] == '-') {
 390                                                 /* There is - excise the comment */
 391                                                 q += 2;
 392                                                 memmove(p, q, nl - q);
 393                                                 goto next_comment;
 394                                         }
 395                                         q++;
 396                                 }
 397                                 *p = '\0';
 398                                 nl = p;
 399                                 break;
 400                         } else {
 401                                 p++;
 402                         }
 403                 }
 404
 405                 p = line;
 406                 while (p < nl) {
 407                         /* Skip white space */
 408                         while (p < nl && isspace(*p))
 409                                 *(p++) = 0;
 410                         if (p >= nl)
 411                                 break;
 412
 413                         tokens[tix].line = lineno;
 414                         tokens[tix].value = p;
 415
 416                         /* Handle string tokens */
 417                         if (isalpha(*p)) {
 418                                 const char **dir;
 419
 420                                 /* Can be a directive, type name or element
 421                                  * name.  Find the end of the name.
 422                                  */
 423                                 q = p + 1;
 424                                 while (q < nl && (isalnum(*q) || *q == '-' || *q == '_'))
 425                                         q++;
 426                                 tokens[tix].size = q - p;
 427                                 p = q;
 428
 429                                 /* If it begins with a lowercase letter then
 430                                  * it's an element name
 431                                  */
 432                                 if (islower(tokens[tix].value[0])) {
 433                                         tokens[tix++].token_type = TOKEN_ELEMENT_NAME;
 434                                         continue;
 435                                 }
 436
 437                                 /* Otherwise we need to search the directive
 438                                  * table
 439                                  */
 440                                 dir = bsearch(&tokens[tix], directives,
 441                                               sizeof(directives) / sizeof(directives[1]),
 442                                               sizeof(directives[1]),
 443                                               directive_compare);
 444                                 if (dir) {
 445                                         tokens[tix++].token_type = dir - directives;
 446                                         continue;
 447                                 }
 448
 449                                 tokens[tix++].token_type = TOKEN_TYPE_NAME;
 450                                 continue;
 451                         }
 452
 453                         /* Handle numbers */
 454                         if (isdigit(*p)) {
 455                                 /* Find the end of the number */
 456                                 q = p + 1;
 457                                 while (q < nl && (isdigit(*q)))
 458                                         q++;
 459                                 tokens[tix].size = q - p;
 460                                 p = q;
 461                                 tokens[tix++].token_type = TOKEN_NUMBER;
 462                                 continue;
 463                         }
 464
 465                         if (nl - p >= 3) {
 466                                 if (memcmp(p, "::=", 3) == 0) {
 467                                         p += 3;
 468                                         tokens[tix].size = 3;
 469                                         tokens[tix++].token_type = TOKEN_ASSIGNMENT;
 470                                         continue;
 471                                 }
 472                         }
 473
 474                         if (nl - p >= 2) {
 475                                 if (memcmp(p, "({", 2) == 0) {
 476                                         p += 2;
 477                                         tokens[tix].size = 2;
 478                                         tokens[tix++].token_type = TOKEN_OPEN_ACTION;
 479                                         continue;
 480                                 }
 481                                 if (memcmp(p, "})", 2) == 0) {
 482                                         p += 2;
 483                                         tokens[tix].size = 2;
 484                                         tokens[tix++].token_type = TOKEN_CLOSE_ACTION;
 485                                         continue;
 486                                 }
 487                         }
 488
 489                         if (nl - p >= 1) {
 490                                 tokens[tix].size = 1;
 491                                 switch (*p) {
 492                                 case '{':
 493                                         p += 1;
 494                                         tokens[tix++].token_type = TOKEN_OPEN_CURLY;
 495                                         continue;
 496                                 case '}':
 497                                         p += 1;
 498                                         tokens[tix++].token_type = TOKEN_CLOSE_CURLY;
 499                                         continue;
 500                                 case '[':
 501                                         p += 1;
 502                                         tokens[tix++].token_type = TOKEN_OPEN_SQUARE;
 503                                         continue;
 504                                 case ']':
 505                                         p += 1;
 506                                         tokens[tix++].token_type = TOKEN_CLOSE_SQUARE;
 507                                         continue;
 508                                 case ',':
 509                                         p += 1;
 510                                         tokens[tix++].token_type = TOKEN_COMMA;
 511                                         continue;
 512                                 default:
 513                                         break;
 514                                 }
 515                         }
 516
 517                         fprintf(stderr, "%s:%u: Unknown character in grammar: '%c'\n",
 518                                 filename, lineno, *p);
 519                         exit(1);
 520                 }
 521         }
 522
 523         nr_tokens = tix;
 524         verbose("Extracted %u tokens\n", nr_tokens);
 525
 526 #if 0
 527         {
 528                 int n;
 529                 for (n = 0; n < nr_tokens; n++)
 530                         debug("Token %3u: '%*.*s'\n",
 531                                n,
 532                                (int)token_list[n].size, (int)token_list[n].size,
 533                                token_list[n].value);
 534         }
 535 #endif
 536 }
 537
 538 static void build_type_list(void);
 539 static void parse(void);
 540 static void dump_elements(void);
 541 static void render(FILE *out, FILE *hdr);
 542
 543 /*
 544  *
 545  */
 546 int main(int argc, char **argv)
 547 {
 548         struct stat st;
 549         ssize_t readlen;
 550         FILE *out, *hdr;
 551         char *buffer, *p;
 552         char *kbuild_verbose;
 553         int fd;
 554
 555         kbuild_verbose = getenv("KBUILD_VERBOSE");
 556         if (kbuild_verbose)
 557                 verbose_opt = atoi(kbuild_verbose);
 558
 559         while (argc > 4) {
 560                 if (strcmp(argv[1], "-v") == 0)
 561                         verbose_opt = true;
 562                 else if (strcmp(argv[1], "-d") == 0)
 563                         debug_opt = true;
 564                 else
 565                         break;
 566                 memmove(&argv[1], &argv[2], (argc - 2) * sizeof(char *));
 567                 argc--;
 568         }
 569
 570         if (argc != 4) {
 571                 fprintf(stderr, "Format: %s [-v] [-d] <grammar-file> <c-file> <hdr-file>\n",
 572                         argv[0]);
 573                 exit(2);
 574         }
 575
 576         filename = argv[1];
 577         outputname = argv[2];
 578         headername = argv[3];
 579
 580         fd = open(filename, O_RDONLY);
 581         if (fd < 0) {
 582                 perror(filename);
 583                 exit(1);
 584         }
 585
 586         if (fstat(fd, &st) < 0) {
 587                 perror(filename);
 588                 exit(1);
 589         }
 590
 591         if (!(buffer = malloc(st.st_size + 1))) {
 592                 perror(NULL);
 593                 exit(1);
 594         }
 595
 596         if ((readlen = read(fd, buffer, st.st_size)) < 0) {
 597                 perror(filename);
 598                 exit(1);
 599         }
 600
 601         if (close(fd) < 0) {
 602                 perror(filename);
 603                 exit(1);
 604         }
 605
 606         if (readlen != st.st_size) {
 607                 fprintf(stderr, "%s: Short read\n", filename);
 608                 exit(1);
 609         }
 610
 611         p = strrchr(argv[1], '/');
 612         p = p ? p + 1 : argv[1];
 613         grammar_name = strdup(p);
 614         if (!p) {
 615                 perror(NULL);
 616                 exit(1);
 617         }
 618         p = strchr(grammar_name, '.');
 619         if (p)
 620                 *p = '\0';
 621
 622         buffer[readlen] = 0;
 623         tokenise(buffer, buffer + readlen);
 624         build_type_list();
 625         parse();
 626         dump_elements();
 627
 628         out = fopen(outputname, "w");
 629         if (!out) {
 630                 perror(outputname);
 631                 exit(1);
 632         }
 633
 634         hdr = fopen(headername, "w");
 635         if (!out) {
 636                 perror(headername);
 637                 exit(1);
 638         }
 639
 640         render(out, hdr);
 641
 642         if (fclose(out) < 0) {
 643                 perror(outputname);
 644                 exit(1);
 645         }
 646
 647         if (fclose(hdr) < 0) {
 648                 perror(headername);
 649                 exit(1);
 650         }
 651
 652         return 0;
 653 }
 654
 655 enum compound {
 656         NOT_COMPOUND,
 657         SET,
 658         SET_OF,
 659         SEQUENCE,
 660         SEQUENCE_OF,
 661         CHOICE,
 662         ANY,
 663         TYPE_REF,
 664         TAG_OVERRIDE
 665 };
 666
 667 struct element {
 668         struct type     *type_def;
 669         struct token    *name;
 670         struct token    *type;
 671         struct action   *action;
 672         struct element  *children;
 673         struct element  *next;
 674         struct element  *render_next;
 675         struct element  *list_next;
 676         uint8_t         n_elements;
 677         enum compound   compound : 8;
 678         enum asn1_class class : 8;
 679         enum asn1_method method : 8;
 680         uint8_t         tag;
 681         unsigned        entry_index;
 682         unsigned        flags;
 683 #define ELEMENT_IMPLICIT        0x0001
 684 #define ELEMENT_EXPLICIT        0x0002
 685 #define ELEMENT_TAG_SPECIFIED   0x0004
 686 #define ELEMENT_RENDERED        0x0008
 687 #define ELEMENT_SKIPPABLE       0x0010
 688 #define ELEMENT_CONDITIONAL     0x0020
 689 };
 690
 691 struct type {
 692         struct token    *name;
 693         struct token    *def;
 694         struct element  *element;
 695         unsigned        ref_count;
 696         unsigned        flags;
 697 #define TYPE_STOP_MARKER        0x0001
 698 #define TYPE_BEGIN              0x0002
 699 };
 700
 701 static struct type *type_list;
 702 static struct type **type_index;
 703 static unsigned nr_types;
 704
 705 static int type_index_compare(const void *_a, const void *_b)
 706 {
 707         const struct type *const *a = _a, *const *b = _b;
 708
 709         if ((*a)->name->size != (*b)->name->size)
 710                 return (*a)->name->size - (*b)->name->size;
 711         else
 712                 return memcmp((*a)->name->value, (*b)->name->value,
 713                               (*a)->name->size);
 714 }
 715
 716 static int type_finder(const void *_key, const void *_ti)
 717 {
 718         const struct token *token = _key;
 719         const struct type *const *ti = _ti;
 720         const struct type *type = *ti;
 721
 722         if (token->size != type->name->size)
 723                 return token->size - type->name->size;
 724         else
 725                 return memcmp(token->value, type->name->value,
 726                               token->size);
 727 }
 728
 729 /*
 730  * Build up a list of types and a sorted index to that list.
 731  */
 732 static void build_type_list(void)
 733 {
 734         struct type *types;
 735         unsigned nr, t, n;
 736
 737         nr = 0;
 738         for (n = 0; n < nr_tokens - 1; n++)
 739                 if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
 740                     token_list[n + 1].token_type == TOKEN_ASSIGNMENT)
 741                         nr++;
 742
 743         if (nr == 0) {
 744                 fprintf(stderr, "%s: No defined types\n", filename);
 745                 exit(1);
 746         }
 747
 748         nr_types = nr;
 749         types = type_list = calloc(nr + 1, sizeof(type_list[0]));
 750         if (!type_list) {
 751                 perror(NULL);
 752                 exit(1);
 753         }
 754         type_index = calloc(nr, sizeof(type_index[0]));
 755         if (!type_index) {
 756                 perror(NULL);
 757                 exit(1);
 758         }
 759
 760         t = 0;
 761         types[t].flags |= TYPE_BEGIN;
 762         for (n = 0; n < nr_tokens - 1; n++) {
 763                 if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
 764                     token_list[n + 1].token_type == TOKEN_ASSIGNMENT) {
 765                         types[t].name = &token_list[n];
 766                         type_index[t] = &types[t];
 767                         t++;
 768                 }
 769         }
 770         types[t].name = &token_list[n + 1];
 771         types[t].flags |= TYPE_STOP_MARKER;
 772
 773         qsort(type_index, nr, sizeof(type_index[0]), type_index_compare);
 774
 775         verbose("Extracted %u types\n", nr_types);
 776 #if 0
 777         for (n = 0; n < nr_types; n++) {
 778                 struct type *type = type_index[n];
 779                 debug("- %*.*s\n",
 780                        (int)type->name->size,
 781                        (int)type->name->size,
 782                        type->name->value);
 783         }
 784 #endif
 785 }
 786
 787 static struct element *parse_type(struct token **_cursor, struct token *stop,
 788                                   struct token *name);
 789
 790 /*
 791  * Parse the token stream
 792  */
 793 static void parse(void)
 794 {
 795         struct token *cursor;
 796         struct type *type;
 797
 798         /* Parse one type definition statement at a time */
 799         type = type_list;
 800         do {
 801                 cursor = type->name;
 802
 803                 if (cursor[0].token_type != TOKEN_TYPE_NAME ||
 804                     cursor[1].token_type != TOKEN_ASSIGNMENT)
 805                         abort();
 806                 cursor += 2;
 807
 808                 type->element = parse_type(&cursor, type[1].name, NULL);
 809                 type->element->type_def = type;
 810
 811                 if (cursor != type[1].name) {
 812                         fprintf(stderr, "%s:%d: Parse error at token '%*.*s'\n",
 813                                 filename, cursor->line,
 814                                 (int)cursor->size, (int)cursor->size, cursor->value);
 815                         exit(1);
 816                 }
 817
 818         } while (type++, !(type->flags & TYPE_STOP_MARKER));
 819
 820         verbose("Extracted %u actions\n", nr_actions);
 821 }
 822
 823 static struct element *element_list;
 824
 825 static struct element *alloc_elem(struct token *type)
 826 {
 827         struct element *e = calloc(1, sizeof(*e));
 828         if (!e) {
 829                 perror(NULL);
 830                 exit(1);
 831         }
 832         e->list_next = element_list;
 833         element_list = e;
 834         return e;
 835 }
 836
 837 static struct element *parse_compound(struct token **_cursor, struct token *end,
 838                                       int alternates);
 839
 840 /*
 841  * Parse one type definition statement
 842  */
 843 static struct element *parse_type(struct token **_cursor, struct token *end,
 844                                   struct token *name)
 845 {
 846         struct element *top, *element;
 847         struct action *action, **ppaction;
 848         struct token *cursor = *_cursor;
 849         struct type **ref;
 850         char *p;
 851         int labelled = 0, implicit = 0;
 852
 853         top = element = alloc_elem(cursor);
 854         element->class = ASN1_UNIV;
 855         element->method = ASN1_PRIM;
 856         element->tag = token_to_tag[cursor->token_type];
 857         element->name = name;
 858
 859         /* Extract the tag value if one given */
 860         if (cursor->token_type == TOKEN_OPEN_SQUARE) {
 861                 cursor++;
 862                 if (cursor >= end)
 863                         goto overrun_error;
 864                 switch (cursor->token_type) {
 865                 case DIRECTIVE_UNIVERSAL:
 866                         element->class = ASN1_UNIV;
 867                         cursor++;
 868                         break;
 869                 case DIRECTIVE_APPLICATION:
 870                         element->class = ASN1_APPL;
 871                         cursor++;
 872                         break;
 873                 case TOKEN_NUMBER:
 874                         element->class = ASN1_CONT;
 875                         break;
 876                 case DIRECTIVE_PRIVATE:
 877                         element->class = ASN1_PRIV;
 878                         cursor++;
 879                         break;
 880                 default:
 881                         fprintf(stderr, "%s:%d: Unrecognised tag class token '%*.*s'\n",
 882                                 filename, cursor->line,
 883                                 (int)cursor->size, (int)cursor->size, cursor->value);
 884                         exit(1);
 885                 }
 886
 887                 if (cursor >= end)
 888                         goto overrun_error;
 889                 if (cursor->token_type != TOKEN_NUMBER) {
 890                         fprintf(stderr, "%s:%d: Missing tag number '%*.*s'\n",
 891                                 filename, cursor->line,
 892                                 (int)cursor->size, (int)cursor->size, cursor->value);
 893                         exit(1);
 894                 }
 895
 896                 element->tag &= ~0x1f;
 897                 element->tag |= strtoul(cursor->value, &p, 10);
 898                 element->flags |= ELEMENT_TAG_SPECIFIED;
 899                 if (p - cursor->value != cursor->size)
 900                         abort();
 901                 cursor++;
 902
 903                 if (cursor >= end)
 904                         goto overrun_error;
 905                 if (cursor->token_type != TOKEN_CLOSE_SQUARE) {
 906                         fprintf(stderr, "%s:%d: Missing closing square bracket '%*.*s'\n",
 907                                 filename, cursor->line,
 908                                 (int)cursor->size, (int)cursor->size, cursor->value);
 909                         exit(1);
 910                 }
 911                 cursor++;
 912                 if (cursor >= end)
 913                         goto overrun_error;
 914                 labelled = 1;
 915         }
 916
 917         /* Handle implicit and explicit markers */
 918         if (cursor->token_type == DIRECTIVE_IMPLICIT) {
 919                 element->flags |= ELEMENT_IMPLICIT;
 920                 implicit = 1;
 921                 cursor++;
 922                 if (cursor >= end)
 923                         goto overrun_error;
 924         } else if (cursor->token_type == DIRECTIVE_EXPLICIT) {
 925                 element->flags |= ELEMENT_EXPLICIT;
 926                 cursor++;
 927                 if (cursor >= end)
 928                         goto overrun_error;
 929         }
 930
 931         if (labelled) {
 932                 if (!implicit)
 933                         element->method |= ASN1_CONS;
 934                 element->compound = implicit ? TAG_OVERRIDE : SEQUENCE;
 935                 element->children = alloc_elem(cursor);
 936                 element = element->children;
 937                 element->class = ASN1_UNIV;
 938                 element->method = ASN1_PRIM;
 939                 element->tag = token_to_tag[cursor->token_type];
 940                 element->name = name;
 941         }
 942
 943         /* Extract the type we're expecting here */
 944         element->type = cursor;
 945         switch (cursor->token_type) {
 946         case DIRECTIVE_ANY:
 947                 element->compound = ANY;
 948                 cursor++;
 949                 break;
 950
 951         case DIRECTIVE_NULL:
 952         case DIRECTIVE_BOOLEAN:
 953         case DIRECTIVE_ENUMERATED:
 954         case DIRECTIVE_INTEGER:
 955                 element->compound = NOT_COMPOUND;
 956                 cursor++;
 957                 break;
 958
 959         case DIRECTIVE_EXTERNAL:
 960                 element->method = ASN1_CONS;
 961
 962         case DIRECTIVE_BMPString:
 963         case DIRECTIVE_GeneralString:
 964         case DIRECTIVE_GraphicString:
 965         case DIRECTIVE_IA5String:
 966         case DIRECTIVE_ISO646String:
 967         case DIRECTIVE_NumericString:
 968         case DIRECTIVE_PrintableString:
 969         case DIRECTIVE_T61String:
 970         case DIRECTIVE_TeletexString:
 971         case DIRECTIVE_UniversalString:
 972         case DIRECTIVE_UTF8String:
 973         case DIRECTIVE_VideotexString:
 974         case DIRECTIVE_VisibleString:
 975         case DIRECTIVE_ObjectDescriptor:
 976         case DIRECTIVE_GeneralizedTime:
 977         case DIRECTIVE_UTCTime:
 978                 element->compound = NOT_COMPOUND;
 979                 cursor++;
 980                 break;
 981
 982         case DIRECTIVE_BIT:
 983         case DIRECTIVE_OCTET:
 984                 element->compound = NOT_COMPOUND;
 985                 cursor++;
 986                 if (cursor >= end)
 987                         goto overrun_error;
 988                 if (cursor->token_type != DIRECTIVE_STRING)
 989                         goto parse_error;
 990                 cursor++;
 991                 break;
 992
 993         case DIRECTIVE_OBJECT:
 994                 element->compound = NOT_COMPOUND;
 995                 cursor++;
 996                 if (cursor >= end)
 997                         goto overrun_error;
 998                 if (cursor->token_type != DIRECTIVE_IDENTIFIER)
 999                         goto parse_error;
1000                 cursor++;
1001                 break;
1002
1003         case TOKEN_TYPE_NAME:
1004                 element->compound = TYPE_REF;
1005                 ref = bsearch(cursor, type_index, nr_types, sizeof(type_index[0]),
1006                               type_finder);
1007                 if (!ref) {
1008                         fprintf(stderr, "%s:%d: Type '%*.*s' undefined\n",
1009                                 filename, cursor->line,
1010                                 (int)cursor->size, (int)cursor->size, cursor->value);
1011                         exit(1);
1012                 }
1013                 cursor->type = *ref;
1014                 (*ref)->ref_count++;
1015                 cursor++;
1016                 break;
1017
1018         case DIRECTIVE_CHOICE:
1019                 element->compound = CHOICE;
1020                 cursor++;
1021                 element->children = parse_compound(&cursor, end, 1);
1022                 break;
1023
1024         case DIRECTIVE_SEQUENCE:
1025                 element->compound = SEQUENCE;
1026                 element->method = ASN1_CONS;
1027                 cursor++;
1028                 if (cursor >= end)
1029                         goto overrun_error;
1030                 if (cursor->token_type == DIRECTIVE_OF) {
1031                         element->compound = SEQUENCE_OF;
1032                         cursor++;
1033                         if (cursor >= end)
1034                                 goto overrun_error;
1035                         element->children = parse_type(&cursor, end, NULL);
1036                 } else {
1037                         element->children = parse_compound(&cursor, end, 0);
1038                 }
1039                 break;
1040
1041         case DIRECTIVE_SET:
1042                 element->compound = SET;
1043                 element->method = ASN1_CONS;
1044                 cursor++;
1045                 if (cursor >= end)
1046                         goto overrun_error;
1047                 if (cursor->token_type == DIRECTIVE_OF) {
1048                         element->compound = SET_OF;
1049                         cursor++;
1050                         if (cursor >= end)
1051                                 goto parse_error;
1052                         element->children = parse_type(&cursor, end, NULL);
1053                 } else {
1054                         element->children = parse_compound(&cursor, end, 1);
1055                 }
1056                 break;
1057
1058         default:
1059                 fprintf(stderr, "%s:%d: Token '%*.*s' does not introduce a type\n",
1060                         filename, cursor->line,
1061                         (int)cursor->size, (int)cursor->size, cursor->value);
1062                 exit(1);
1063         }
1064
1065         /* Handle elements that are optional */
1066         if (cursor < end && (cursor->token_type == DIRECTIVE_OPTIONAL ||
1067                              cursor->token_type == DIRECTIVE_DEFAULT)
1068             ) {
1069                 cursor++;
1070                 top->flags |= ELEMENT_SKIPPABLE;
1071         }
1072
1073         if (cursor < end && cursor->token_type == TOKEN_OPEN_ACTION) {
1074                 cursor++;
1075                 if (cursor >= end)
1076                         goto overrun_error;
1077                 if (cursor->token_type != TOKEN_ELEMENT_NAME) {
1078                         fprintf(stderr, "%s:%d: Token '%*.*s' is not an action function name\n",
1079                                 filename, cursor->line,
1080                                 (int)cursor->size, (int)cursor->size, cursor->value);
1081                         exit(1);
1082                 }
1083
1084                 action = malloc(sizeof(struct action) + cursor->size + 1);
1085                 if (!action) {
1086                         perror(NULL);
1087                         exit(1);
1088                 }
1089                 action->index = 0;
1090                 memcpy(action->name, cursor->value, cursor->size);
1091                 action->name[cursor->size] = 0;
1092
1093                 for (ppaction = &action_list;
1094                      *ppaction;
1095                      ppaction = &(*ppaction)->next
1096                      ) {
1097                         int cmp = strcmp(action->name, (*ppaction)->name);
1098                         if (cmp == 0) {
1099                                 free(action);
1100                                 action = *ppaction;
1101                                 goto found;
1102                         }
1103                         if (cmp < 0) {
1104                                 action->next = *ppaction;
1105                                 *ppaction = action;
1106                                 nr_actions++;
1107                                 goto found;
1108                         }
1109                 }
1110                 action->next = NULL;
1111                 *ppaction = action;
1112                 nr_actions++;
1113         found:
1114
1115                 element->action = action;
1116                 cursor->action = action;
1117                 cursor++;
1118                 if (cursor >= end)
1119                         goto overrun_error;
1120                 if (cursor->token_type != TOKEN_CLOSE_ACTION) {
1121                         fprintf(stderr, "%s:%d: Missing close action, got '%*.*s'\n",
1122                                 filename, cursor->line,
1123                                 (int)cursor->size, (int)cursor->size, cursor->value);
1124                         exit(1);
1125                 }
1126                 cursor++;
1127         }
1128
1129         *_cursor = cursor;
1130         return top;
1131
1132 parse_error:
1133         fprintf(stderr, "%s:%d: Unexpected token '%*.*s'\n",
1134                 filename, cursor->line,
1135                 (int)cursor->size, (int)cursor->size, cursor->value);
1136         exit(1);
1137
1138 overrun_error:
1139         fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1140         exit(1);
1141 }
1142
1143 /*
1144  * Parse a compound type list
1145  */
1146 static struct element *parse_compound(struct token **_cursor, struct token *end,
1147                                       int alternates)
1148 {
1149         struct element *children, **child_p = &children, *element;
1150         struct token *cursor = *_cursor, *name;
1151
1152         if (cursor->token_type != TOKEN_OPEN_CURLY) {
1153                 fprintf(stderr, "%s:%d: Expected compound to start with brace not '%*.*s'\n",
1154                         filename, cursor->line,
1155                         (int)cursor->size, (int)cursor->size, cursor->value);
1156                 exit(1);
1157         }
1158         cursor++;
1159         if (cursor >= end)
1160                 goto overrun_error;
1161
1162         if (cursor->token_type == TOKEN_OPEN_CURLY) {
1163                 fprintf(stderr, "%s:%d: Empty compound\n",
1164                         filename, cursor->line);
1165                 exit(1);
1166         }
1167
1168         for (;;) {
1169                 name = NULL;
1170                 if (cursor->token_type == TOKEN_ELEMENT_NAME) {
1171                         name = cursor;
1172                         cursor++;
1173                         if (cursor >= end)
1174                                 goto overrun_error;
1175                 }
1176
1177                 element = parse_type(&cursor, end, name);
1178                 if (alternates)
1179                         element->flags |= ELEMENT_SKIPPABLE | ELEMENT_CONDITIONAL;
1180
1181                 *child_p = element;
1182                 child_p = &element->next;
1183
1184                 if (cursor >= end)
1185                         goto overrun_error;
1186                 if (cursor->token_type != TOKEN_COMMA)
1187                         break;
1188                 cursor++;
1189                 if (cursor >= end)
1190                         goto overrun_error;
1191         }
1192
1193         children->flags &= ~ELEMENT_CONDITIONAL;
1194
1195         if (cursor->token_type != TOKEN_CLOSE_CURLY) {
1196                 fprintf(stderr, "%s:%d: Expected compound closure, got '%*.*s'\n",
1197                         filename, cursor->line,
1198                         (int)cursor->size, (int)cursor->size, cursor->value);
1199                 exit(1);
1200         }
1201         cursor++;
1202
1203         *_cursor = cursor;
1204         return children;
1205
1206 overrun_error:
1207         fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1208         exit(1);
1209 }
1210
1211 static void dump_element(const struct element *e, int level)
1212 {
1213         const struct element *c;
1214         const struct type *t = e->type_def;
1215         const char *name = e->name ? e->name->value : ".";
1216         int nsize = e->name ? e->name->size : 1;
1217         const char *tname = t && t->name ? t->name->value : ".";
1218         int tnsize = t && t->name ? t->name->size : 1;
1219         char tag[32];
1220
1221         if (e->class == 0 && e->method == 0 && e->tag == 0)
1222                 strcpy(tag, "<...>");
1223         else if (e->class == ASN1_UNIV)
1224                 sprintf(tag, "%s %s %s",
1225                         asn1_classes[e->class],
1226                         asn1_methods[e->method],
1227                         asn1_universal_tags[e->tag]);
1228         else
1229                 sprintf(tag, "%s %s %u",
1230                         asn1_classes[e->class],
1231                         asn1_methods[e->method],
1232                         e->tag);
1233
1234         printf("%c%c%c%c%c %c %*s[*] \e[33m%s\e[m %*.*s %*.*s \e[35m%s\e[m\n",
1235                e->flags & ELEMENT_IMPLICIT ? 'I' : '-',
1236                e->flags & ELEMENT_EXPLICIT ? 'E' : '-',
1237                e->flags & ELEMENT_TAG_SPECIFIED ? 'T' : '-',
1238                e->flags & ELEMENT_SKIPPABLE ? 'S' : '-',
1239                e->flags & ELEMENT_CONDITIONAL ? 'C' : '-',
1240                "-tTqQcaro"[e->compound],
1241                level, "",
1242                tag,
1243                tnsize, tnsize, tname,
1244                nsize, nsize, name,
1245                e->action ? e->action->name : "");
1246         if (e->compound == TYPE_REF)
1247                 dump_element(e->type->type->element, level + 3);
1248         else
1249                 for (c = e->children; c; c = c->next)
1250                         dump_element(c, level + 3);
1251 }
1252
1253 static void dump_elements(void)
1254 {
1255         if (debug_opt)
1256                 dump_element(type_list[0].element, 0);
1257 }
1258
1259 static void render_element(FILE *out, struct element *e, struct element *tag);
1260 static void render_out_of_line_list(FILE *out);
1261
1262 static int nr_entries;
1263 static int render_depth = 1;
1264 static struct element *render_list, **render_list_p = &render_list;
1265
1266 __attribute__((format(printf, 2, 3)))
1267 static void render_opcode(FILE *out, const char *fmt, ...)
1268 {
1269         va_list va;
1270
1271         if (out) {
1272                 fprintf(out, "\t[%4d] =%*s", nr_entries, render_depth, "");
1273                 va_start(va, fmt);
1274                 vfprintf(out, fmt, va);
1275                 va_end(va);
1276         }
1277         nr_entries++;
1278 }
1279
1280 __attribute__((format(printf, 2, 3)))
1281 static void render_more(FILE *out, const char *fmt, ...)
1282 {
1283         va_list va;
1284
1285         if (out) {
1286                 va_start(va, fmt);
1287                 vfprintf(out, fmt, va);
1288                 va_end(va);
1289         }
1290 }
1291
1292 /*
1293  * Render the grammar into a state machine definition.
1294  */
1295 static void render(FILE *out, FILE *hdr)
1296 {
1297         struct element *e;
1298         struct action *action;
1299         struct type *root;
1300         int index;
1301
1302         fprintf(hdr, "/*\n");
1303         fprintf(hdr, " * Automatically generated by asn1_compiler.  Do not edit\n");
1304         fprintf(hdr, " *\n");
1305         fprintf(hdr, " * ASN.1 parser for %s\n", grammar_name);
1306         fprintf(hdr, " */\n");
1307         fprintf(hdr, "#include <linux/asn1_decoder.h>\n");
1308         fprintf(hdr, "\n");
1309         fprintf(hdr, "extern const struct asn1_decoder %s_decoder;\n", grammar_name);
1310         if (ferror(hdr)) {
1311                 perror(headername);
1312                 exit(1);
1313         }
1314
1315         fprintf(out, "/*\n");
1316         fprintf(out, " * Automatically generated by asn1_compiler.  Do not edit\n");
1317         fprintf(out, " *\n");
1318         fprintf(out, " * ASN.1 parser for %s\n", grammar_name);
1319         fprintf(out, " */\n");
1320         fprintf(out, "#include <linux/asn1_ber_bytecode.h>\n");
1321         fprintf(out, "#include \"%s-asn1.h\"\n", grammar_name);
1322         fprintf(out, "\n");
1323         if (ferror(out)) {
1324                 perror(outputname);
1325                 exit(1);
1326         }
1327
1328         /* Tabulate the action functions we might have to call */
1329         fprintf(hdr, "\n");
1330         index = 0;
1331         for (action = action_list; action; action = action->next) {
1332                 action->index = index++;
1333                 fprintf(hdr,
1334                         "extern int %s(void *, size_t, unsigned char,"
1335                         " const void *, size_t);\n",
1336                         action->name);
1337         }
1338         fprintf(hdr, "\n");
1339
1340         fprintf(out, "enum %s_actions {\n", grammar_name);
1341         for (action = action_list; action; action = action->next)
1342                 fprintf(out, "\tACT_%s = %u,\n",
1343                         action->name, action->index);
1344         fprintf(out, "\tNR__%s_actions = %u\n", grammar_name, nr_actions);
1345         fprintf(out, "};\n");
1346
1347         fprintf(out, "\n");
1348         fprintf(out, "static const asn1_action_t %s_action_table[NR__%s_actions] = {\n",
1349                 grammar_name, grammar_name);
1350         for (action = action_list; action; action = action->next)
1351                 fprintf(out, "\t[%4u] = %s,\n", action->index, action->name);
1352         fprintf(out, "};\n");
1353
1354         if (ferror(out)) {
1355                 perror(outputname);
1356                 exit(1);
1357         }
1358
1359         /* We do two passes - the first one calculates all the offsets */
1360         verbose("Pass 1\n");
1361         nr_entries = 0;
1362         root = &type_list[0];
1363         render_element(NULL, root->element, NULL);
1364         render_opcode(NULL, "ASN1_OP_COMPLETE,\n");
1365         render_out_of_line_list(NULL);
1366
1367         for (e = element_list; e; e = e->list_next)
1368                 e->flags &= ~ELEMENT_RENDERED;
1369
1370         /* And then we actually render */
1371         verbose("Pass 2\n");
1372         fprintf(out, "\n");
1373         fprintf(out, "static const unsigned char %s_machine[] = {\n",
1374                 grammar_name);
1375
1376         nr_entries = 0;
1377         root = &type_list[0];
1378         render_element(out, root->element, NULL);
1379         render_opcode(out, "ASN1_OP_COMPLETE,\n");
1380         render_out_of_line_list(out);
1381
1382         fprintf(out, "};\n");
1383
1384         fprintf(out, "\n");
1385         fprintf(out, "const struct asn1_decoder %s_decoder = {\n", grammar_name);
1386         fprintf(out, "\t.machine = %s_machine,\n", grammar_name);
1387         fprintf(out, "\t.machlen = sizeof(%s_machine),\n", grammar_name);
1388         fprintf(out, "\t.actions = %s_action_table,\n", grammar_name);
1389         fprintf(out, "};\n");
1390 }
1391
1392 /*
1393  * Render the out-of-line elements
1394  */
1395 static void render_out_of_line_list(FILE *out)
1396 {
1397         struct element *e, *ce;
1398         const char *act;
1399         int entry;
1400
1401         while ((e = render_list)) {
1402                 render_list = e->render_next;
1403                 if (!render_list)
1404                         render_list_p = &render_list;
1405
1406                 render_more(out, "\n");
1407                 e->entry_index = entry = nr_entries;
1408                 render_depth++;
1409                 for (ce = e->children; ce; ce = ce->next)
1410                         render_element(out, ce, NULL);
1411                 render_depth--;
1412
1413                 act = e->action ? "_ACT" : "";
1414                 switch (e->compound) {
1415                 case SEQUENCE:
1416                         render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
1417                         break;
1418                 case SEQUENCE_OF:
1419                         render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
1420                         render_opcode(out, "_jump_target(%u),\n", entry);
1421                         break;
1422                 case SET:
1423                         render_opcode(out, "ASN1_OP_END_SET%s,\n", act);
1424                         break;
1425                 case SET_OF:
1426                         render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
1427                         render_opcode(out, "_jump_target(%u),\n", entry);
1428                         break;
1429                 default:
1430                         break;
1431                 }
1432                 if (e->action)
1433                         render_opcode(out, "_action(ACT_%s),\n",
1434                                       e->action->name);
1435                 render_opcode(out, "ASN1_OP_RETURN,\n");
1436         }
1437 }
1438
1439 /*
1440  * Render an element.
1441  */
1442 static void render_element(FILE *out, struct element *e, struct element *tag)
1443 {
1444         struct element *ec, *x;
1445         const char *cond, *act;
1446         int entry, skippable = 0, outofline = 0;
1447
1448         if (e->flags & ELEMENT_SKIPPABLE ||
1449             (tag && tag->flags & ELEMENT_SKIPPABLE))
1450                 skippable = 1;
1451
1452         if ((e->type_def && e->type_def->ref_count > 1) ||
1453             skippable)
1454                 outofline = 1;
1455
1456         if (e->type_def && out) {
1457                 render_more(out, "\t// %*.*s\n",
1458                             (int)e->type_def->name->size, (int)e->type_def->name->size,
1459                             e->type_def->name->value);
1460         }
1461
1462         /* Render the operation */
1463         cond = (e->flags & ELEMENT_CONDITIONAL ||
1464                 (tag && tag->flags & ELEMENT_CONDITIONAL)) ? "COND_" : "";
1465         act = e->action ? "_ACT" : "";
1466         switch (e->compound) {
1467         case ANY:
1468                 render_opcode(out, "ASN1_OP_%sMATCH_ANY%s%s,",
1469                               cond, act, skippable ? "_OR_SKIP" : "");
1470                 if (e->name)
1471                         render_more(out, "\t\t// %*.*s",
1472                                     (int)e->name->size, (int)e->name->size,
1473                                     e->name->value);
1474                 render_more(out, "\n");
1475                 goto dont_render_tag;
1476
1477         case TAG_OVERRIDE:
1478                 render_element(out, e->children, e);
1479                 return;
1480
1481         case SEQUENCE:
1482         case SEQUENCE_OF:
1483         case SET:
1484         case SET_OF:
1485                 render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
1486                               cond,
1487                               outofline ? "_JUMP" : "",
1488                               skippable ? "_OR_SKIP" : "");
1489                 break;
1490
1491         case CHOICE:
1492                 goto dont_render_tag;
1493
1494         case TYPE_REF:
1495                 if (e->class == ASN1_UNIV && e->method == ASN1_PRIM && e->tag == 0)
1496                         goto dont_render_tag;
1497         default:
1498                 render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
1499                               cond, act,
1500                               skippable ? "_OR_SKIP" : "");
1501                 break;
1502         }
1503
1504         x = tag ?: e;
1505         if (x->name)
1506                 render_more(out, "\t\t// %*.*s",
1507                             (int)x->name->size, (int)x->name->size,
1508                             x->name->value);
1509         render_more(out, "\n");
1510
1511         /* Render the tag */
1512         if (!tag || !(tag->flags & ELEMENT_TAG_SPECIFIED))
1513                 tag = e;
1514
1515         if (tag->class == ASN1_UNIV &&
1516             tag->tag != 14 &&
1517             tag->tag != 15 &&
1518             tag->tag != 31)
1519                 render_opcode(out, "_tag(%s, %s, %s),\n",
1520                               asn1_classes[tag->class],
1521                               asn1_methods[tag->method | e->method],
1522                               asn1_universal_tags[tag->tag]);
1523         else
1524                 render_opcode(out, "_tagn(%s, %s, %2u),\n",
1525                               asn1_classes[tag->class],
1526                               asn1_methods[tag->method | e->method],
1527                               tag->tag);
1528         tag = NULL;
1529 dont_render_tag:
1530
1531         /* Deal with compound types */
1532         switch (e->compound) {
1533         case TYPE_REF:
1534                 render_element(out, e->type->type->element, tag);
1535                 if (e->action)
1536                         render_opcode(out, "ASN1_OP_%sACT,\n",
1537                                       skippable ? "MAYBE_" : "");
1538                 break;
1539
1540         case SEQUENCE:
1541                 if (outofline) {
1542                         /* Render out-of-line for multiple use or
1543                          * skipability */
1544                         render_opcode(out, "_jump_target(%u),", e->entry_index);
1545                         if (e->type_def && e->type_def->name)
1546                                 render_more(out, "\t\t// --> %*.*s",
1547                                             (int)e->type_def->name->size,
1548                                             (int)e->type_def->name->size,
1549                                             e->type_def->name->value);
1550                         render_more(out, "\n");
1551                         if (!(e->flags & ELEMENT_RENDERED)) {
1552                                 e->flags |= ELEMENT_RENDERED;
1553                                 *render_list_p = e;
1554                                 render_list_p = &e->render_next;
1555                         }
1556                         return;
1557                 } else {
1558                         /* Render inline for single use */
1559                         render_depth++;
1560                         for (ec = e->children; ec; ec = ec->next)
1561                                 render_element(out, ec, NULL);
1562                         render_depth--;
1563                         render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
1564                 }
1565                 break;
1566
1567         case SEQUENCE_OF:
1568         case SET_OF:
1569                 if (outofline) {
1570                         /* Render out-of-line for multiple use or
1571                          * skipability */
1572                         render_opcode(out, "_jump_target(%u),", e->entry_index);
1573                         if (e->type_def && e->type_def->name)
1574                                 render_more(out, "\t\t// --> %*.*s",
1575                                             (int)e->type_def->name->size,
1576                                             (int)e->type_def->name->size,
1577                                             e->type_def->name->value);
1578                         render_more(out, "\n");
1579                         if (!(e->flags & ELEMENT_RENDERED)) {
1580                                 e->flags |= ELEMENT_RENDERED;
1581                                 *render_list_p = e;
1582                                 render_list_p = &e->render_next;
1583                         }
1584                         return;
1585                 } else {
1586                         /* Render inline for single use */
1587                         entry = nr_entries;
1588                         render_depth++;
1589                         render_element(out, e->children, NULL);
1590                         render_depth--;
1591                         if (e->compound == SEQUENCE_OF)
1592                                 render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
1593                         else
1594                                 render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
1595                         render_opcode(out, "_jump_target(%u),\n", entry);
1596                 }
1597                 break;
1598
1599         case SET:
1600                 /* I can't think of a nice way to do SET support without having
1601                  * a stack of bitmasks to make sure no element is repeated.
1602                  * The bitmask has also to be checked that no non-optional
1603                  * elements are left out whilst not preventing optional
1604                  * elements from being left out.
1605                  */
1606                 fprintf(stderr, "The ASN.1 SET type is not currently supported.\n");
1607                 exit(1);
1608
1609         case CHOICE:
1610                 for (ec = e->children; ec; ec = ec->next)
1611                         render_element(out, ec, ec);
1612                 if (!skippable)
1613                         render_opcode(out, "ASN1_OP_COND_FAIL,\n");
1614                 if (e->action)
1615                         render_opcode(out, "ASN1_OP_ACT,\n");
1616                 break;
1617
1618         default:
1619                 break;
1620         }
1621
1622         if (e->action)
1623                 render_opcode(out, "_action(ACT_%s),\n", e->action->name);
1624 }