scripts/asn1_compiler.c

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