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 static _Bool verbose;
 315
 316 #define debug(fmt, ...) do { if (verbose) printf(fmt, ## __VA_ARGS__); } while (0)
 317
 318 static int directive_compare(const void *_key, const void *_pdir)
 319 {
 320         const struct token *token = _key;
 321         const char *const *pdir = _pdir, *dir = *pdir;
 322         size_t dlen, clen;
 323         int val;
 324
 325         dlen = strlen(dir);
 326         clen = (dlen < token->size) ? dlen : token->size;
 327
 328         //debug("cmp(%*.*s,%s) = ",
 329         //       (int)token->size, (int)token->size, token->value,
 330         //       dir);
 331
 332         val = memcmp(token->value, dir, clen);
 333         if (val != 0) {
 334                 //debug("%d [cmp]\n", val);
 335                 return val;
 336         }
 337
 338         if (dlen == token->size) {
 339                 //debug("0\n");
 340                 return 0;
 341         }
 342         //debug("%d\n", (int)dlen - (int)token->size);
 343         return dlen - token->size; /* shorter -> negative */
 344 }
 345
 346 /*
 347  * Tokenise an ASN.1 grammar
 348  */
 349 static void tokenise(char *buffer, char *end)
 350 {
 351         struct token *tokens;
 352         char *line, *nl, *p, *q;
 353         unsigned tix, lineno;
 354
 355         /* Assume we're going to have half as many tokens as we have
 356          * characters
 357          */
 358         token_list = tokens = calloc((end - buffer) / 2, sizeof(struct token));
 359         if (!tokens) {
 360                 perror(NULL);
 361                 exit(1);
 362         }
 363         tix = 0;
 364
 365         lineno = 0;
 366         while (buffer < end) {
 367                 /* First of all, break out a line */
 368                 lineno++;
 369                 line = buffer;
 370                 nl = memchr(line, '\n', end - buffer);
 371                 if (!nl) {
 372                         buffer = nl = end;
 373                 } else {
 374                         buffer = nl + 1;
 375                         *nl = '\0';
 376                 }
 377
 378                 /* Remove "--" comments */
 379                 p = line;
 380         next_comment:
 381                 while ((p = memchr(p, '-', nl - p))) {
 382                         if (p[1] == '-') {
 383                                 /* Found a comment; see if there's a terminator */
 384                                 q = p + 2;
 385                                 while ((q = memchr(q, '-', nl - q))) {
 386                                         if (q[1] == '-') {
 387                                                 /* There is - excise the comment */
 388                                                 q += 2;
 389                                                 memmove(p, q, nl - q);
 390                                                 goto next_comment;
 391                                         }
 392                                         q++;
 393                                 }
 394                                 *p = '\0';
 395                                 nl = p;
 396                                 break;
 397                         } else {
 398                                 p++;
 399                         }
 400                 }
 401
 402                 p = line;
 403                 while (p < nl) {
 404                         /* Skip white space */
 405                         while (p < nl && isspace(*p))
 406                                 *(p++) = 0;
 407                         if (p >= nl)
 408                                 break;
 409
 410                         tokens[tix].line = lineno;
 411                         tokens[tix].value = p;
 412
 413                         /* Handle string tokens */
 414                         if (isalpha(*p)) {
 415                                 const char **dir;
 416
 417                                 /* Can be a directive, type name or element
 418                                  * name.  Find the end of the name.
 419                                  */
 420                                 q = p + 1;
 421                                 while (q < nl && (isalnum(*q) || *q == '-' || *q == '_'))
 422                                         q++;
 423                                 tokens[tix].size = q - p;
 424                                 p = q;
 425
 426                                 /* If it begins with a lowercase letter then
 427                                  * it's an element name
 428                                  */
 429                                 if (islower(tokens[tix].value[0])) {
 430                                         tokens[tix++].token_type = TOKEN_ELEMENT_NAME;
 431                                         continue;
 432                                 }
 433
 434                                 /* Otherwise we need to search the directive
 435                                  * table
 436                                  */
 437                                 dir = bsearch(&tokens[tix], directives,
 438                                               sizeof(directives) / sizeof(directives[1]),
 439                                               sizeof(directives[1]),
 440                                               directive_compare);
 441                                 if (dir) {
 442                                         tokens[tix++].token_type = dir - directives;
 443                                         continue;
 444                                 }
 445
 446                                 tokens[tix++].token_type = TOKEN_TYPE_NAME;
 447                                 continue;
 448                         }
 449
 450                         /* Handle numbers */
 451                         if (isdigit(*p)) {
 452                                 /* Find the end of the number */
 453                                 q = p + 1;
 454                                 while (q < nl && (isdigit(*q)))
 455                                         q++;
 456                                 tokens[tix].size = q - p;
 457                                 p = q;
 458                                 tokens[tix++].token_type = TOKEN_NUMBER;
 459                                 continue;
 460                         }
 461
 462                         if (nl - p >= 3) {
 463                                 if (memcmp(p, "::=", 3) == 0) {
 464                                         p += 3;
 465                                         tokens[tix].size = 3;
 466                                         tokens[tix++].token_type = TOKEN_ASSIGNMENT;
 467                                         continue;
 468                                 }
 469                         }
 470
 471                         if (nl - p >= 2) {
 472                                 if (memcmp(p, "({", 2) == 0) {
 473                                         p += 2;
 474                                         tokens[tix].size = 2;
 475                                         tokens[tix++].token_type = TOKEN_OPEN_ACTION;
 476                                         continue;
 477                                 }
 478                                 if (memcmp(p, "})", 2) == 0) {
 479                                         p += 2;
 480                                         tokens[tix].size = 2;
 481                                         tokens[tix++].token_type = TOKEN_CLOSE_ACTION;
 482                                         continue;
 483                                 }
 484                         }
 485
 486                         if (nl - p >= 1) {
 487                                 tokens[tix].size = 1;
 488                                 switch (*p) {
 489                                 case '{':
 490                                         p += 1;
 491                                         tokens[tix++].token_type = TOKEN_OPEN_CURLY;
 492                                         continue;
 493                                 case '}':
 494                                         p += 1;
 495                                         tokens[tix++].token_type = TOKEN_CLOSE_CURLY;
 496                                         continue;
 497                                 case '[':
 498                                         p += 1;
 499                                         tokens[tix++].token_type = TOKEN_OPEN_SQUARE;
 500                                         continue;
 501                                 case ']':
 502                                         p += 1;
 503                                         tokens[tix++].token_type = TOKEN_CLOSE_SQUARE;
 504                                         continue;
 505                                 case ',':
 506                                         p += 1;
 507                                         tokens[tix++].token_type = TOKEN_COMMA;
 508                                         continue;
 509                                 default:
 510                                         break;
 511                                 }
 512                         }
 513
 514                         fprintf(stderr, "%s:%u: Unknown character in grammar: '%c'\n",
 515                                 filename, lineno, *p);
 516                         exit(1);
 517                 }
 518         }
 519
 520         nr_tokens = tix;
 521         debug("Extracted %u tokens\n", nr_tokens);
 522
 523 #if 0
 524         {
 525                 int n;
 526                 for (n = 0; n < nr_tokens; n++)
 527                         debug("Token %3u: '%*.*s'\n",
 528                                n,
 529                                (int)token_list[n].size, (int)token_list[n].size,
 530                                token_list[n].value);
 531         }
 532 #endif
 533 }
 534
 535 static void build_type_list(void);
 536 static void parse(void);
 537 static void render(FILE *out, FILE *hdr);
 538
 539 /*
 540  *
 541  */
 542 int main(int argc, char **argv)
 543 {
 544         struct stat st;
 545         ssize_t readlen;
 546         FILE *out, *hdr;
 547         char *buffer, *p;
 548         char *kbuild_verbose;
 549         int fd;
 550
 551         if (argc != 4) {
 552                 fprintf(stderr, "Format: %s <grammar-file> <c-file> <hdr-file>\n",
 553                         argv[0]);
 554                 exit(2);
 555         }
 556
 557         kbuild_verbose = getenv("KBUILD_VERBOSE");
 558         if (kbuild_verbose)
 559                 verbose = atoi(kbuild_verbose);
 560
 561         filename = argv[1];
 562         outputname = argv[2];
 563         headername = argv[3];
 564
 565         fd = open(filename, O_RDONLY);
 566         if (fd < 0) {
 567                 perror(filename);
 568                 exit(1);
 569         }
 570
 571         if (fstat(fd, &st) < 0) {
 572                 perror(filename);
 573                 exit(1);
 574         }
 575
 576         if (!(buffer = malloc(st.st_size + 1))) {
 577                 perror(NULL);
 578                 exit(1);
 579         }
 580
 581         if ((readlen = read(fd, buffer, st.st_size)) < 0) {
 582                 perror(filename);
 583                 exit(1);
 584         }
 585
 586         if (close(fd) < 0) {
 587                 perror(filename);
 588                 exit(1);
 589         }
 590
 591         if (readlen != st.st_size) {
 592                 fprintf(stderr, "%s: Short read\n", filename);
 593                 exit(1);
 594         }
 595
 596         p = strrchr(argv[1], '/');
 597         p = p ? p + 1 : argv[1];
 598         grammar_name = strdup(p);
 599         if (!p) {
 600                 perror(NULL);
 601                 exit(1);
 602         }
 603         p = strchr(grammar_name, '.');
 604         if (p)
 605                 *p = '\0';
 606
 607         buffer[readlen] = 0;
 608         tokenise(buffer, buffer + readlen);
 609         build_type_list();
 610         parse();
 611
 612         out = fopen(outputname, "w");
 613         if (!out) {
 614                 perror(outputname);
 615                 exit(1);
 616         }
 617
 618         hdr = fopen(headername, "w");
 619         if (!out) {
 620                 perror(headername);
 621                 exit(1);
 622         }
 623
 624         render(out, hdr);
 625
 626         if (fclose(out) < 0) {
 627                 perror(outputname);
 628                 exit(1);
 629         }
 630
 631         if (fclose(hdr) < 0) {
 632                 perror(headername);
 633                 exit(1);
 634         }
 635
 636         return 0;
 637 }
 638
 639 enum compound {
 640         NOT_COMPOUND,
 641         SET,
 642         SET_OF,
 643         SEQUENCE,
 644         SEQUENCE_OF,
 645         CHOICE,
 646         ANY,
 647         TYPE_REF,
 648         TAG_OVERRIDE
 649 };
 650
 651 struct element {
 652         struct type     *type_def;
 653         struct token    *name;
 654         struct token    *type;
 655         struct action   *action;
 656         struct element  *children;
 657         struct element  *next;
 658         struct element  *render_next;
 659         struct element  *list_next;
 660         uint8_t         n_elements;
 661         enum compound   compound : 8;
 662         enum asn1_class class : 8;
 663         enum asn1_method method : 8;
 664         uint8_t         tag;
 665         unsigned        entry_index;
 666         unsigned        flags;
 667 #define ELEMENT_IMPLICIT        0x0001
 668 #define ELEMENT_EXPLICIT        0x0002
 669 #define ELEMENT_TAG_SPECIFIED   0x0004
 670 #define ELEMENT_RENDERED        0x0008
 671 #define ELEMENT_SKIPPABLE       0x0010
 672 #define ELEMENT_CONDITIONAL     0x0020
 673 };
 674
 675 struct type {
 676         struct token    *name;
 677         struct token    *def;
 678         struct element  *element;
 679         unsigned        ref_count;
 680         unsigned        flags;
 681 #define TYPE_STOP_MARKER        0x0001
 682 #define TYPE_BEGIN              0x0002
 683 };
 684
 685 static struct type *type_list;
 686 static struct type **type_index;
 687 static unsigned nr_types;
 688
 689 static int type_index_compare(const void *_a, const void *_b)
 690 {
 691         const struct type *const *a = _a, *const *b = _b;
 692
 693         if ((*a)->name->size != (*b)->name->size)
 694                 return (*a)->name->size - (*b)->name->size;
 695         else
 696                 return memcmp((*a)->name->value, (*b)->name->value,
 697                               (*a)->name->size);
 698 }
 699
 700 static int type_finder(const void *_key, const void *_ti)
 701 {
 702         const struct token *token = _key;
 703         const struct type *const *ti = _ti;
 704         const struct type *type = *ti;
 705
 706         if (token->size != type->name->size)
 707                 return token->size - type->name->size;
 708         else
 709                 return memcmp(token->value, type->name->value,
 710                               token->size);
 711 }
 712
 713 /*
 714  * Build up a list of types and a sorted index to that list.
 715  */
 716 static void build_type_list(void)
 717 {
 718         struct type *types;
 719         unsigned nr, t, n;
 720
 721         nr = 0;
 722         for (n = 0; n < nr_tokens - 1; n++)
 723                 if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
 724                     token_list[n + 1].token_type == TOKEN_ASSIGNMENT)
 725                         nr++;
 726
 727         if (nr == 0) {
 728                 fprintf(stderr, "%s: No defined types\n", filename);
 729                 exit(1);
 730         }
 731
 732         nr_types = nr;
 733         types = type_list = calloc(nr + 1, sizeof(type_list[0]));
 734         if (!type_list) {
 735                 perror(NULL);
 736                 exit(1);
 737         }
 738         type_index = calloc(nr, sizeof(type_index[0]));
 739         if (!type_index) {
 740                 perror(NULL);
 741                 exit(1);
 742         }
 743
 744         t = 0;
 745         types[t].flags |= TYPE_BEGIN;
 746         for (n = 0; n < nr_tokens - 1; n++) {
 747                 if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
 748                     token_list[n + 1].token_type == TOKEN_ASSIGNMENT) {
 749                         types[t].name = &token_list[n];
 750                         type_index[t] = &types[t];
 751                         t++;
 752                 }
 753         }
 754         types[t].name = &token_list[n + 1];
 755         types[t].flags |= TYPE_STOP_MARKER;
 756
 757         qsort(type_index, nr, sizeof(type_index[0]), type_index_compare);
 758
 759         debug("Extracted %u types\n", nr_types);
 760 #if 0
 761         for (n = 0; n < nr_types; n++) {
 762                 struct type *type = type_index[n];
 763                 debug("- %*.*s\n",
 764                        (int)type->name->size,
 765                        (int)type->name->size,
 766                        type->name->value);
 767         }
 768 #endif
 769 }
 770
 771 static struct element *parse_type(struct token **_cursor, struct token *stop,
 772                                   struct token *name);
 773
 774 /*
 775  * Parse the token stream
 776  */
 777 static void parse(void)
 778 {
 779         struct token *cursor;
 780         struct type *type;
 781
 782         /* Parse one type definition statement at a time */
 783         type = type_list;
 784         do {
 785                 cursor = type->name;
 786
 787                 if (cursor[0].token_type != TOKEN_TYPE_NAME ||
 788                     cursor[1].token_type != TOKEN_ASSIGNMENT)
 789                         abort();
 790                 cursor += 2;
 791
 792                 type->element = parse_type(&cursor, type[1].name, NULL);
 793                 type->element->type_def = type;
 794
 795                 if (cursor != type[1].name) {
 796                         fprintf(stderr, "%s:%d: Parse error at token '%*.*s'\n",
 797                                 filename, cursor->line,
 798                                 (int)cursor->size, (int)cursor->size, cursor->value);
 799                         exit(1);
 800                 }
 801
 802         } while (type++, !(type->flags & TYPE_STOP_MARKER));
 803
 804         debug("Extracted %u actions\n", nr_actions);
 805 }
 806
 807 static struct element *element_list;
 808
 809 static struct element *alloc_elem(struct token *type)
 810 {
 811         struct element *e = calloc(1, sizeof(*e));
 812         if (!e) {
 813                 perror(NULL);
 814                 exit(1);
 815         }
 816         e->list_next = element_list;
 817         element_list = e;
 818         return e;
 819 }
 820
 821 static struct element *parse_compound(struct token **_cursor, struct token *end,
 822                                       int alternates);
 823
 824 /*
 825  * Parse one type definition statement
 826  */
 827 static struct element *parse_type(struct token **_cursor, struct token *end,
 828                                   struct token *name)
 829 {
 830         struct element *top, *element;
 831         struct action *action, **ppaction;
 832         struct token *cursor = *_cursor;
 833         struct type **ref;
 834         char *p;
 835         int labelled = 0, implicit = 0;
 836
 837         top = element = alloc_elem(cursor);
 838         element->class = ASN1_UNIV;
 839         element->method = ASN1_PRIM;
 840         element->tag = token_to_tag[cursor->token_type];
 841         element->name = name;
 842
 843         /* Extract the tag value if one given */
 844         if (cursor->token_type == TOKEN_OPEN_SQUARE) {
 845                 cursor++;
 846                 if (cursor >= end)
 847                         goto overrun_error;
 848                 switch (cursor->token_type) {
 849                 case DIRECTIVE_UNIVERSAL:
 850                         element->class = ASN1_UNIV;
 851                         cursor++;
 852                         break;
 853                 case DIRECTIVE_APPLICATION:
 854                         element->class = ASN1_APPL;
 855                         cursor++;
 856                         break;
 857                 case TOKEN_NUMBER:
 858                         element->class = ASN1_CONT;
 859                         break;
 860                 case DIRECTIVE_PRIVATE:
 861                         element->class = ASN1_PRIV;
 862                         cursor++;
 863                         break;
 864                 default:
 865                         fprintf(stderr, "%s:%d: Unrecognised tag class token '%*.*s'\n",
 866                                 filename, cursor->line,
 867                                 (int)cursor->size, (int)cursor->size, cursor->value);
 868                         exit(1);
 869                 }
 870
 871                 if (cursor >= end)
 872                         goto overrun_error;
 873                 if (cursor->token_type != TOKEN_NUMBER) {
 874                         fprintf(stderr, "%s:%d: Missing tag number '%*.*s'\n",
 875                                 filename, cursor->line,
 876                                 (int)cursor->size, (int)cursor->size, cursor->value);
 877                         exit(1);
 878                 }
 879
 880                 element->tag &= ~0x1f;
 881                 element->tag |= strtoul(cursor->value, &p, 10);
 882                 element->flags |= ELEMENT_TAG_SPECIFIED;
 883                 if (p - cursor->value != cursor->size)
 884                         abort();
 885                 cursor++;
 886
 887                 if (cursor >= end)
 888                         goto overrun_error;
 889                 if (cursor->token_type != TOKEN_CLOSE_SQUARE) {
 890                         fprintf(stderr, "%s:%d: Missing closing square bracket '%*.*s'\n",
 891                                 filename, cursor->line,
 892                                 (int)cursor->size, (int)cursor->size, cursor->value);
 893                         exit(1);
 894                 }
 895                 cursor++;
 896                 if (cursor >= end)
 897                         goto overrun_error;
 898                 labelled = 1;
 899         }
 900
 901         /* Handle implicit and explicit markers */
 902         if (cursor->token_type == DIRECTIVE_IMPLICIT) {
 903                 element->flags |= ELEMENT_IMPLICIT;
 904                 implicit = 1;
 905                 cursor++;
 906                 if (cursor >= end)
 907                         goto overrun_error;
 908         } else if (cursor->token_type == DIRECTIVE_EXPLICIT) {
 909                 element->flags |= ELEMENT_EXPLICIT;
 910                 cursor++;
 911                 if (cursor >= end)
 912                         goto overrun_error;
 913         }
 914
 915         if (labelled) {
 916                 if (!implicit)
 917                         element->method |= ASN1_CONS;
 918                 element->compound = implicit ? TAG_OVERRIDE : SEQUENCE;
 919                 element->children = alloc_elem(cursor);
 920                 element = element->children;
 921                 element->class = ASN1_UNIV;
 922                 element->method = ASN1_PRIM;
 923                 element->tag = token_to_tag[cursor->token_type];
 924                 element->name = name;
 925         }
 926
 927         /* Extract the type we're expecting here */
 928         element->type = cursor;
 929         switch (cursor->token_type) {
 930         case DIRECTIVE_ANY:
 931                 element->compound = ANY;
 932                 cursor++;
 933                 break;
 934
 935         case DIRECTIVE_NULL:
 936         case DIRECTIVE_BOOLEAN:
 937         case DIRECTIVE_ENUMERATED:
 938         case DIRECTIVE_INTEGER:
 939                 element->compound = NOT_COMPOUND;
 940                 cursor++;
 941                 break;
 942
 943         case DIRECTIVE_EXTERNAL:
 944                 element->method = ASN1_CONS;
 945
 946         case DIRECTIVE_BMPString:
 947         case DIRECTIVE_GeneralString:
 948         case DIRECTIVE_GraphicString:
 949         case DIRECTIVE_IA5String:
 950         case DIRECTIVE_ISO646String:
 951         case DIRECTIVE_NumericString:
 952         case DIRECTIVE_PrintableString:
 953         case DIRECTIVE_T61String:
 954         case DIRECTIVE_TeletexString:
 955         case DIRECTIVE_UniversalString:
 956         case DIRECTIVE_UTF8String:
 957         case DIRECTIVE_VideotexString:
 958         case DIRECTIVE_VisibleString:
 959         case DIRECTIVE_ObjectDescriptor:
 960         case DIRECTIVE_GeneralizedTime:
 961         case DIRECTIVE_UTCTime:
 962                 element->compound = NOT_COMPOUND;
 963                 cursor++;
 964                 break;
 965
 966         case DIRECTIVE_BIT:
 967         case DIRECTIVE_OCTET:
 968                 element->compound = NOT_COMPOUND;
 969                 cursor++;
 970                 if (cursor >= end)
 971                         goto overrun_error;
 972                 if (cursor->token_type != DIRECTIVE_STRING)
 973                         goto parse_error;
 974                 cursor++;
 975                 break;
 976
 977         case DIRECTIVE_OBJECT:
 978                 element->compound = NOT_COMPOUND;
 979                 cursor++;
 980                 if (cursor >= end)
 981                         goto overrun_error;
 982                 if (cursor->token_type != DIRECTIVE_IDENTIFIER)
 983                         goto parse_error;
 984                 cursor++;
 985                 break;
 986
 987         case TOKEN_TYPE_NAME:
 988                 element->compound = TYPE_REF;
 989                 ref = bsearch(cursor, type_index, nr_types, sizeof(type_index[0]),
 990                               type_finder);
 991                 if (!ref) {
 992                         fprintf(stderr, "%s:%d: Type '%*.*s' undefined\n",
 993                                 filename, cursor->line,
 994                                 (int)cursor->size, (int)cursor->size, cursor->value);
 995                         exit(1);
 996                 }
 997                 cursor->type = *ref;
 998                 (*ref)->ref_count++;
 999                 cursor++;
1000                 break;
1001
1002         case DIRECTIVE_CHOICE:
1003                 element->compound = CHOICE;
1004                 cursor++;
1005                 element->children = parse_compound(&cursor, end, 1);
1006                 break;
1007
1008         case DIRECTIVE_SEQUENCE:
1009                 element->compound = SEQUENCE;
1010                 element->method = ASN1_CONS;
1011                 cursor++;
1012                 if (cursor >= end)
1013                         goto overrun_error;
1014                 if (cursor->token_type == DIRECTIVE_OF) {
1015                         element->compound = SEQUENCE_OF;
1016                         cursor++;
1017                         if (cursor >= end)
1018                                 goto overrun_error;
1019                         element->children = parse_type(&cursor, end, NULL);
1020                 } else {
1021                         element->children = parse_compound(&cursor, end, 0);
1022                 }
1023                 break;
1024
1025         case DIRECTIVE_SET:
1026                 element->compound = SET;
1027                 element->method = ASN1_CONS;
1028                 cursor++;
1029                 if (cursor >= end)
1030                         goto overrun_error;
1031                 if (cursor->token_type == DIRECTIVE_OF) {
1032                         element->compound = SET_OF;
1033                         cursor++;
1034                         if (cursor >= end)
1035                                 goto parse_error;
1036                         element->children = parse_type(&cursor, end, NULL);
1037                 } else {
1038                         element->children = parse_compound(&cursor, end, 1);
1039                 }
1040                 break;
1041
1042         default:
1043                 fprintf(stderr, "%s:%d: Token '%*.*s' does not introduce a type\n",
1044                         filename, cursor->line,
1045                         (int)cursor->size, (int)cursor->size, cursor->value);
1046                 exit(1);
1047         }
1048
1049         /* Handle elements that are optional */
1050         if (cursor < end && (cursor->token_type == DIRECTIVE_OPTIONAL ||
1051                              cursor->token_type == DIRECTIVE_DEFAULT)
1052             ) {
1053                 cursor++;
1054                 top->flags |= ELEMENT_SKIPPABLE;
1055         }
1056
1057         if (cursor < end && cursor->token_type == TOKEN_OPEN_ACTION) {
1058                 cursor++;
1059                 if (cursor >= end)
1060                         goto overrun_error;
1061                 if (cursor->token_type != TOKEN_ELEMENT_NAME) {
1062                         fprintf(stderr, "%s:%d: Token '%*.*s' is not an action function name\n",
1063                                 filename, cursor->line,
1064                                 (int)cursor->size, (int)cursor->size, cursor->value);
1065                         exit(1);
1066                 }
1067
1068                 action = malloc(sizeof(struct action) + cursor->size + 1);
1069                 if (!action) {
1070                         perror(NULL);
1071                         exit(1);
1072                 }
1073                 action->index = 0;
1074                 memcpy(action->name, cursor->value, cursor->size);
1075                 action->name[cursor->size] = 0;
1076
1077                 for (ppaction = &action_list;
1078                      *ppaction;
1079                      ppaction = &(*ppaction)->next
1080                      ) {
1081                         int cmp = strcmp(action->name, (*ppaction)->name);
1082                         if (cmp == 0) {
1083                                 free(action);
1084                                 action = *ppaction;
1085                                 goto found;
1086                         }
1087                         if (cmp < 0) {
1088                                 action->next = *ppaction;
1089                                 *ppaction = action;
1090                                 nr_actions++;
1091                                 goto found;
1092                         }
1093                 }
1094                 action->next = NULL;
1095                 *ppaction = action;
1096                 nr_actions++;
1097         found:
1098
1099                 element->action = action;
1100                 cursor->action = action;
1101                 cursor++;
1102                 if (cursor >= end)
1103                         goto overrun_error;
1104                 if (cursor->token_type != TOKEN_CLOSE_ACTION) {
1105                         fprintf(stderr, "%s:%d: Missing close action, got '%*.*s'\n",
1106                                 filename, cursor->line,
1107                                 (int)cursor->size, (int)cursor->size, cursor->value);
1108                         exit(1);
1109                 }
1110                 cursor++;
1111         }
1112
1113         *_cursor = cursor;
1114         return top;
1115
1116 parse_error:
1117         fprintf(stderr, "%s:%d: Unexpected token '%*.*s'\n",
1118                 filename, cursor->line,
1119                 (int)cursor->size, (int)cursor->size, cursor->value);
1120         exit(1);
1121
1122 overrun_error:
1123         fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1124         exit(1);
1125 }
1126
1127 /*
1128  * Parse a compound type list
1129  */
1130 static struct element *parse_compound(struct token **_cursor, struct token *end,
1131                                       int alternates)
1132 {
1133         struct element *children, **child_p = &children, *element;
1134         struct token *cursor = *_cursor, *name;
1135
1136         if (cursor->token_type != TOKEN_OPEN_CURLY) {
1137                 fprintf(stderr, "%s:%d: Expected compound to start with brace not '%*.*s'\n",
1138                         filename, cursor->line,
1139                         (int)cursor->size, (int)cursor->size, cursor->value);
1140                 exit(1);
1141         }
1142         cursor++;
1143         if (cursor >= end)
1144                 goto overrun_error;
1145
1146         if (cursor->token_type == TOKEN_OPEN_CURLY) {
1147                 fprintf(stderr, "%s:%d: Empty compound\n",
1148                         filename, cursor->line);
1149                 exit(1);
1150         }
1151
1152         for (;;) {
1153                 name = NULL;
1154                 if (cursor->token_type == TOKEN_ELEMENT_NAME) {
1155                         name = cursor;
1156                         cursor++;
1157                         if (cursor >= end)
1158                                 goto overrun_error;
1159                 }
1160
1161                 element = parse_type(&cursor, end, name);
1162                 if (alternates)
1163                         element->flags |= ELEMENT_SKIPPABLE | ELEMENT_CONDITIONAL;
1164
1165                 *child_p = element;
1166                 child_p = &element->next;
1167
1168                 if (cursor >= end)
1169                         goto overrun_error;
1170                 if (cursor->token_type != TOKEN_COMMA)
1171                         break;
1172                 cursor++;
1173                 if (cursor >= end)
1174                         goto overrun_error;
1175         }
1176
1177         children->flags &= ~ELEMENT_CONDITIONAL;
1178
1179         if (cursor->token_type != TOKEN_CLOSE_CURLY) {
1180                 fprintf(stderr, "%s:%d: Expected compound closure, got '%*.*s'\n",
1181                         filename, cursor->line,
1182                         (int)cursor->size, (int)cursor->size, cursor->value);
1183                 exit(1);
1184         }
1185         cursor++;
1186
1187         *_cursor = cursor;
1188         return children;
1189
1190 overrun_error:
1191         fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1192         exit(1);
1193 }
1194
1195 static void render_element(FILE *out, struct element *e, struct element *tag);
1196 static void render_out_of_line_list(FILE *out);
1197
1198 static int nr_entries;
1199 static int render_depth = 1;
1200 static struct element *render_list, **render_list_p = &render_list;
1201
1202 __attribute__((format(printf, 2, 3)))
1203 static void render_opcode(FILE *out, const char *fmt, ...)
1204 {
1205         va_list va;
1206
1207         if (out) {
1208                 fprintf(out, "\t[%4d] =%*s", nr_entries, render_depth, "");
1209                 va_start(va, fmt);
1210                 vfprintf(out, fmt, va);
1211                 va_end(va);
1212         }
1213         nr_entries++;
1214 }
1215
1216 __attribute__((format(printf, 2, 3)))
1217 static void render_more(FILE *out, const char *fmt, ...)
1218 {
1219         va_list va;
1220
1221         if (out) {
1222                 va_start(va, fmt);
1223                 vfprintf(out, fmt, va);
1224                 va_end(va);
1225         }
1226 }
1227
1228 /*
1229  * Render the grammar into a state machine definition.
1230  */
1231 static void render(FILE *out, FILE *hdr)
1232 {
1233         struct element *e;
1234         struct action *action;
1235         struct type *root;
1236         int index;
1237
1238         fprintf(hdr, "/*\n");
1239         fprintf(hdr, " * Automatically generated by asn1_compiler.  Do not edit\n");
1240         fprintf(hdr, " *\n");
1241         fprintf(hdr, " * ASN.1 parser for %s\n", grammar_name);
1242         fprintf(hdr, " */\n");
1243         fprintf(hdr, "#include <linux/asn1_decoder.h>\n");
1244         fprintf(hdr, "\n");
1245         fprintf(hdr, "extern const struct asn1_decoder %s_decoder;\n", grammar_name);
1246         if (ferror(hdr)) {
1247                 perror(headername);
1248                 exit(1);
1249         }
1250
1251         fprintf(out, "/*\n");
1252         fprintf(out, " * Automatically generated by asn1_compiler.  Do not edit\n");
1253         fprintf(out, " *\n");
1254         fprintf(out, " * ASN.1 parser for %s\n", grammar_name);
1255         fprintf(out, " */\n");
1256         fprintf(out, "#include <linux/asn1_ber_bytecode.h>\n");
1257         fprintf(out, "#include \"%s-asn1.h\"\n", grammar_name);
1258         fprintf(out, "\n");
1259         if (ferror(out)) {
1260                 perror(outputname);
1261                 exit(1);
1262         }
1263
1264         /* Tabulate the action functions we might have to call */
1265         fprintf(hdr, "\n");
1266         index = 0;
1267         for (action = action_list; action; action = action->next) {
1268                 action->index = index++;
1269                 fprintf(hdr,
1270                         "extern int %s(void *, size_t, unsigned char,"
1271                         " const void *, size_t);\n",
1272                         action->name);
1273         }
1274         fprintf(hdr, "\n");
1275
1276         fprintf(out, "enum %s_actions {\n", grammar_name);
1277         for (action = action_list; action; action = action->next)
1278                 fprintf(out, "\tACT_%s = %u,\n",
1279                         action->name, action->index);
1280         fprintf(out, "\tNR__%s_actions = %u\n", grammar_name, nr_actions);
1281         fprintf(out, "};\n");
1282
1283         fprintf(out, "\n");
1284         fprintf(out, "static const asn1_action_t %s_action_table[NR__%s_actions] = {\n",
1285                 grammar_name, grammar_name);
1286         for (action = action_list; action; action = action->next)
1287                 fprintf(out, "\t[%4u] = %s,\n", action->index, action->name);
1288         fprintf(out, "};\n");
1289
1290         if (ferror(out)) {
1291                 perror(outputname);
1292                 exit(1);
1293         }
1294
1295         /* We do two passes - the first one calculates all the offsets */
1296         debug("Pass 1\n");
1297         nr_entries = 0;
1298         root = &type_list[0];
1299         render_element(NULL, root->element, NULL);
1300         render_opcode(NULL, "ASN1_OP_COMPLETE,\n");
1301         render_out_of_line_list(NULL);
1302
1303         for (e = element_list; e; e = e->list_next)
1304                 e->flags &= ~ELEMENT_RENDERED;
1305
1306         /* And then we actually render */
1307         debug("Pass 2\n");
1308         fprintf(out, "\n");
1309         fprintf(out, "static const unsigned char %s_machine[] = {\n",
1310                 grammar_name);
1311
1312         nr_entries = 0;
1313         root = &type_list[0];
1314         render_element(out, root->element, NULL);
1315         render_opcode(out, "ASN1_OP_COMPLETE,\n");
1316         render_out_of_line_list(out);
1317
1318         fprintf(out, "};\n");
1319
1320         fprintf(out, "\n");
1321         fprintf(out, "const struct asn1_decoder %s_decoder = {\n", grammar_name);
1322         fprintf(out, "\t.machine = %s_machine,\n", grammar_name);
1323         fprintf(out, "\t.machlen = sizeof(%s_machine),\n", grammar_name);
1324         fprintf(out, "\t.actions = %s_action_table,\n", grammar_name);
1325         fprintf(out, "};\n");
1326 }
1327
1328 /*
1329  * Render the out-of-line elements
1330  */
1331 static void render_out_of_line_list(FILE *out)
1332 {
1333         struct element *e, *ce;
1334         const char *act;
1335         int entry;
1336
1337         while ((e = render_list)) {
1338                 render_list = e->render_next;
1339                 if (!render_list)
1340                         render_list_p = &render_list;
1341
1342                 render_more(out, "\n");
1343                 e->entry_index = entry = nr_entries;
1344                 render_depth++;
1345                 for (ce = e->children; ce; ce = ce->next)
1346                         render_element(out, ce, NULL);
1347                 render_depth--;
1348
1349                 act = e->action ? "_ACT" : "";
1350                 switch (e->compound) {
1351                 case SEQUENCE:
1352                         render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
1353                         break;
1354                 case SEQUENCE_OF:
1355                         render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
1356                         render_opcode(out, "_jump_target(%u),\n", entry);
1357                         break;
1358                 case SET:
1359                         render_opcode(out, "ASN1_OP_END_SET%s,\n", act);
1360                         break;
1361                 case SET_OF:
1362                         render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
1363                         render_opcode(out, "_jump_target(%u),\n", entry);
1364                         break;
1365                 default:
1366                         break;
1367                 }
1368                 if (e->action)
1369                         render_opcode(out, "_action(ACT_%s),\n",
1370                                       e->action->name);
1371                 render_opcode(out, "ASN1_OP_RETURN,\n");
1372         }
1373 }
1374
1375 /*
1376  * Render an element.
1377  */
1378 static void render_element(FILE *out, struct element *e, struct element *tag)
1379 {
1380         struct element *ec, *x;
1381         const char *cond, *act;
1382         int entry, skippable = 0, outofline = 0;
1383
1384         if (e->flags & ELEMENT_SKIPPABLE ||
1385             (tag && tag->flags & ELEMENT_SKIPPABLE))
1386                 skippable = 1;
1387
1388         if ((e->type_def && e->type_def->ref_count > 1) ||
1389             skippable)
1390                 outofline = 1;
1391
1392         if (e->type_def && out) {
1393                 render_more(out, "\t// %*.*s\n",
1394                             (int)e->type_def->name->size, (int)e->type_def->name->size,
1395                             e->type_def->name->value);
1396         }
1397
1398         /* Render the operation */
1399         cond = (e->flags & ELEMENT_CONDITIONAL ||
1400                 (tag && tag->flags & ELEMENT_CONDITIONAL)) ? "COND_" : "";
1401         act = e->action ? "_ACT" : "";
1402         switch (e->compound) {
1403         case ANY:
1404                 render_opcode(out, "ASN1_OP_%sMATCH_ANY%s,", cond, act);
1405                 if (e->name)
1406                         render_more(out, "\t\t// %*.*s",
1407                                     (int)e->name->size, (int)e->name->size,
1408                                     e->name->value);
1409                 render_more(out, "\n");
1410                 goto dont_render_tag;
1411
1412         case TAG_OVERRIDE:
1413                 render_element(out, e->children, e);
1414                 return;
1415
1416         case SEQUENCE:
1417         case SEQUENCE_OF:
1418         case SET:
1419         case SET_OF:
1420                 render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
1421                               cond,
1422                               outofline ? "_JUMP" : "",
1423                               skippable ? "_OR_SKIP" : "");
1424                 break;
1425
1426         case CHOICE:
1427                 goto dont_render_tag;
1428
1429         case TYPE_REF:
1430                 if (e->class == ASN1_UNIV && e->method == ASN1_PRIM && e->tag == 0)
1431                         goto dont_render_tag;
1432         default:
1433                 render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
1434                               cond, act,
1435                               skippable ? "_OR_SKIP" : "");
1436                 break;
1437         }
1438
1439         x = tag ?: e;
1440         if (x->name)
1441                 render_more(out, "\t\t// %*.*s",
1442                             (int)x->name->size, (int)x->name->size,
1443                             x->name->value);
1444         render_more(out, "\n");
1445
1446         /* Render the tag */
1447         if (!tag || !(tag->flags & ELEMENT_TAG_SPECIFIED))
1448                 tag = e;
1449
1450         if (tag->class == ASN1_UNIV &&
1451             tag->tag != 14 &&
1452             tag->tag != 15 &&
1453             tag->tag != 31)
1454                 render_opcode(out, "_tag(%s, %s, %s),\n",
1455                               asn1_classes[tag->class],
1456                               asn1_methods[tag->method | e->method],
1457                               asn1_universal_tags[tag->tag]);
1458         else
1459                 render_opcode(out, "_tagn(%s, %s, %2u),\n",
1460                               asn1_classes[tag->class],
1461                               asn1_methods[tag->method | e->method],
1462                               tag->tag);
1463         tag = NULL;
1464 dont_render_tag:
1465
1466         /* Deal with compound types */
1467         switch (e->compound) {
1468         case TYPE_REF:
1469                 render_element(out, e->type->type->element, tag);
1470                 if (e->action)
1471                         render_opcode(out, "ASN1_OP_ACT,\n");
1472                 break;
1473
1474         case SEQUENCE:
1475                 if (outofline) {
1476                         /* Render out-of-line for multiple use or
1477                          * skipability */
1478                         render_opcode(out, "_jump_target(%u),", e->entry_index);
1479                         if (e->type_def && e->type_def->name)
1480                                 render_more(out, "\t\t// --> %*.*s",
1481                                             (int)e->type_def->name->size,
1482                                             (int)e->type_def->name->size,
1483                                             e->type_def->name->value);
1484                         render_more(out, "\n");
1485                         if (!(e->flags & ELEMENT_RENDERED)) {
1486                                 e->flags |= ELEMENT_RENDERED;
1487                                 *render_list_p = e;
1488                                 render_list_p = &e->render_next;
1489                         }
1490                         return;
1491                 } else {
1492                         /* Render inline for single use */
1493                         render_depth++;
1494                         for (ec = e->children; ec; ec = ec->next)
1495                                 render_element(out, ec, NULL);
1496                         render_depth--;
1497                         render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
1498                 }
1499                 break;
1500
1501         case SEQUENCE_OF:
1502         case SET_OF:
1503                 if (outofline) {
1504                         /* Render out-of-line for multiple use or
1505                          * skipability */
1506                         render_opcode(out, "_jump_target(%u),", e->entry_index);
1507                         if (e->type_def && e->type_def->name)
1508                                 render_more(out, "\t\t// --> %*.*s",
1509                                             (int)e->type_def->name->size,
1510                                             (int)e->type_def->name->size,
1511                                             e->type_def->name->value);
1512                         render_more(out, "\n");
1513                         if (!(e->flags & ELEMENT_RENDERED)) {
1514                                 e->flags |= ELEMENT_RENDERED;
1515                                 *render_list_p = e;
1516                                 render_list_p = &e->render_next;
1517                         }
1518                         return;
1519                 } else {
1520                         /* Render inline for single use */
1521                         entry = nr_entries;
1522                         render_depth++;
1523                         render_element(out, e->children, NULL);
1524                         render_depth--;
1525                         if (e->compound == SEQUENCE_OF)
1526                                 render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
1527                         else
1528                                 render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
1529                         render_opcode(out, "_jump_target(%u),\n", entry);
1530                 }
1531                 break;
1532
1533         case SET:
1534                 /* I can't think of a nice way to do SET support without having
1535                  * a stack of bitmasks to make sure no element is repeated.
1536                  * The bitmask has also to be checked that no non-optional
1537                  * elements are left out whilst not preventing optional
1538                  * elements from being left out.
1539                  */
1540                 fprintf(stderr, "The ASN.1 SET type is not currently supported.\n");
1541                 exit(1);
1542
1543         case CHOICE:
1544                 for (ec = e->children; ec; ec = ec->next)
1545                         render_element(out, ec, ec);
1546                 if (!skippable)
1547                         render_opcode(out, "ASN1_OP_COND_FAIL,\n");
1548                 if (e->action)
1549                         render_opcode(out, "ASN1_OP_ACT,\n");
1550                 break;
1551
1552         default:
1553                 break;
1554         }
1555
1556         if (e->action)
1557                 render_opcode(out, "_action(ACT_%s),\n", e->action->name);
1558 }