scripts/asn1_compiler.c

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