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