linux/scripts/asn1_compiler.c
<<
>>
Prefs
   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
  24enum 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
 122static 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
 157static const char asn1_classes[4][5] = {
 158        [ASN1_UNIV]     = "UNIV",
 159        [ASN1_APPL]     = "APPL",
 160        [ASN1_CONT]     = "CONT",
 161        [ASN1_PRIV]     = "PRIV"
 162};
 163
 164static const char asn1_methods[2][5] = {
 165        [ASN1_UNIV]     = "PRIM",
 166        [ASN1_APPL]     = "CONS"
 167};
 168
 169static 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
 204static const char *filename;
 205static const char *grammar_name;
 206static const char *outputname;
 207static const char *headername;
 208
 209static 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
 295struct action {
 296        struct action   *next;
 297        char            *name;
 298        unsigned char   index;
 299};
 300
 301static struct action *action_list;
 302static unsigned nr_actions;
 303
 304struct 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
 313static struct token *token_list;
 314static unsigned nr_tokens;
 315static bool verbose_opt;
 316static 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
 321static 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 */
 350static 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
 556static void build_type_list(void);
 557static void parse(void);
 558static void dump_elements(void);
 559static void render(FILE *out, FILE *hdr);
 560
 561/*
 562 *
 563 */
 564int 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
 673enum 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
 685struct 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
 709struct 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
 719static struct type *type_list;
 720static struct type **type_index;
 721static unsigned nr_types;
 722
 723static 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
 734static 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 */
 750static 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
 802static struct element *parse_type(struct token **_cursor, struct token *stop,
 803                                  struct token *name);
 804
 805/*
 806 * Parse the token stream
 807 */
 808static 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
 837static struct element *element_list;
 838
 839static 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
 851static struct element *parse_compound(struct token **_cursor, struct token *end,
 852                                      int alternates);
 853
 854/*
 855 * Parse one type definition statement
 856 */
 857static 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
1138parse_error:
1139        fprintf(stderr, "%s:%d: Unexpected token '%s'\n",
1140                filename, cursor->line, cursor->content);
1141        exit(1);
1142
1143overrun_error:
1144        fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1145        exit(1);
1146}
1147
1148/*
1149 * Parse a compound type list
1150 */
1151static 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
1209overrun_error:
1210        fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1211        exit(1);
1212}
1213
1214static 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
1254static void dump_elements(void)
1255{
1256        if (debug_opt)
1257                dump_element(type_list[0].element, 0);
1258}
1259
1260static void render_element(FILE *out, struct element *e, struct element *tag);
1261static void render_out_of_line_list(FILE *out);
1262
1263static int nr_entries;
1264static int render_depth = 1;
1265static struct element *render_list, **render_list_p = &render_list;
1266
1267__attribute__((format(printf, 2, 3)))
1268static 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)))
1282static 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 */
1296static 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 */
1396static 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 */
1443static 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;
1524dont_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}
1616