Back to home page

LXR

 
 

    


0001 /* Simplified ASN.1 notation parser
0002  *
0003  * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
0004  * Written by David Howells (dhowells@redhat.com)
0005  *
0006  * This program is free software; you can redistribute it and/or
0007  * modify it under the terms of the GNU General Public Licence
0008  * as published by the Free Software Foundation; either version
0009  * 2 of the Licence, or (at your option) any later version.
0010  */
0011 
0012 #include <stdarg.h>
0013 #include <stdio.h>
0014 #include <stdlib.h>
0015 #include <stdint.h>
0016 #include <stdbool.h>
0017 #include <string.h>
0018 #include <ctype.h>
0019 #include <unistd.h>
0020 #include <fcntl.h>
0021 #include <sys/stat.h>
0022 #include <linux/asn1_ber_bytecode.h>
0023 
0024 enum token_type {
0025     DIRECTIVE_ABSENT,
0026     DIRECTIVE_ALL,
0027     DIRECTIVE_ANY,
0028     DIRECTIVE_APPLICATION,
0029     DIRECTIVE_AUTOMATIC,
0030     DIRECTIVE_BEGIN,
0031     DIRECTIVE_BIT,
0032     DIRECTIVE_BMPString,
0033     DIRECTIVE_BOOLEAN,
0034     DIRECTIVE_BY,
0035     DIRECTIVE_CHARACTER,
0036     DIRECTIVE_CHOICE,
0037     DIRECTIVE_CLASS,
0038     DIRECTIVE_COMPONENT,
0039     DIRECTIVE_COMPONENTS,
0040     DIRECTIVE_CONSTRAINED,
0041     DIRECTIVE_CONTAINING,
0042     DIRECTIVE_DEFAULT,
0043     DIRECTIVE_DEFINED,
0044     DIRECTIVE_DEFINITIONS,
0045     DIRECTIVE_EMBEDDED,
0046     DIRECTIVE_ENCODED,
0047     DIRECTIVE_ENCODING_CONTROL,
0048     DIRECTIVE_END,
0049     DIRECTIVE_ENUMERATED,
0050     DIRECTIVE_EXCEPT,
0051     DIRECTIVE_EXPLICIT,
0052     DIRECTIVE_EXPORTS,
0053     DIRECTIVE_EXTENSIBILITY,
0054     DIRECTIVE_EXTERNAL,
0055     DIRECTIVE_FALSE,
0056     DIRECTIVE_FROM,
0057     DIRECTIVE_GeneralString,
0058     DIRECTIVE_GeneralizedTime,
0059     DIRECTIVE_GraphicString,
0060     DIRECTIVE_IA5String,
0061     DIRECTIVE_IDENTIFIER,
0062     DIRECTIVE_IMPLICIT,
0063     DIRECTIVE_IMPLIED,
0064     DIRECTIVE_IMPORTS,
0065     DIRECTIVE_INCLUDES,
0066     DIRECTIVE_INSTANCE,
0067     DIRECTIVE_INSTRUCTIONS,
0068     DIRECTIVE_INTEGER,
0069     DIRECTIVE_INTERSECTION,
0070     DIRECTIVE_ISO646String,
0071     DIRECTIVE_MAX,
0072     DIRECTIVE_MIN,
0073     DIRECTIVE_MINUS_INFINITY,
0074     DIRECTIVE_NULL,
0075     DIRECTIVE_NumericString,
0076     DIRECTIVE_OBJECT,
0077     DIRECTIVE_OCTET,
0078     DIRECTIVE_OF,
0079     DIRECTIVE_OPTIONAL,
0080     DIRECTIVE_ObjectDescriptor,
0081     DIRECTIVE_PATTERN,
0082     DIRECTIVE_PDV,
0083     DIRECTIVE_PLUS_INFINITY,
0084     DIRECTIVE_PRESENT,
0085     DIRECTIVE_PRIVATE,
0086     DIRECTIVE_PrintableString,
0087     DIRECTIVE_REAL,
0088     DIRECTIVE_RELATIVE_OID,
0089     DIRECTIVE_SEQUENCE,
0090     DIRECTIVE_SET,
0091     DIRECTIVE_SIZE,
0092     DIRECTIVE_STRING,
0093     DIRECTIVE_SYNTAX,
0094     DIRECTIVE_T61String,
0095     DIRECTIVE_TAGS,
0096     DIRECTIVE_TRUE,
0097     DIRECTIVE_TeletexString,
0098     DIRECTIVE_UNION,
0099     DIRECTIVE_UNIQUE,
0100     DIRECTIVE_UNIVERSAL,
0101     DIRECTIVE_UTCTime,
0102     DIRECTIVE_UTF8String,
0103     DIRECTIVE_UniversalString,
0104     DIRECTIVE_VideotexString,
0105     DIRECTIVE_VisibleString,
0106     DIRECTIVE_WITH,
0107     NR__DIRECTIVES,
0108     TOKEN_ASSIGNMENT = NR__DIRECTIVES,
0109     TOKEN_OPEN_CURLY,
0110     TOKEN_CLOSE_CURLY,
0111     TOKEN_OPEN_SQUARE,
0112     TOKEN_CLOSE_SQUARE,
0113     TOKEN_OPEN_ACTION,
0114     TOKEN_CLOSE_ACTION,
0115     TOKEN_COMMA,
0116     TOKEN_NUMBER,
0117     TOKEN_TYPE_NAME,
0118     TOKEN_ELEMENT_NAME,
0119     NR__TOKENS
0120 };
0121 
0122 static const unsigned char token_to_tag[NR__TOKENS] = {
0123     /* EOC goes first */
0124     [DIRECTIVE_BOOLEAN]     = ASN1_BOOL,
0125     [DIRECTIVE_INTEGER]     = ASN1_INT,
0126     [DIRECTIVE_BIT]         = ASN1_BTS,
0127     [DIRECTIVE_OCTET]       = ASN1_OTS,
0128     [DIRECTIVE_NULL]        = ASN1_NULL,
0129     [DIRECTIVE_OBJECT]      = ASN1_OID,
0130     [DIRECTIVE_ObjectDescriptor]    = ASN1_ODE,
0131     [DIRECTIVE_EXTERNAL]        = ASN1_EXT,
0132     [DIRECTIVE_REAL]        = ASN1_REAL,
0133     [DIRECTIVE_ENUMERATED]      = ASN1_ENUM,
0134     [DIRECTIVE_EMBEDDED]        = 0,
0135     [DIRECTIVE_UTF8String]      = ASN1_UTF8STR,
0136     [DIRECTIVE_RELATIVE_OID]    = ASN1_RELOID,
0137     /* 14 */
0138     /* 15 */
0139     [DIRECTIVE_SEQUENCE]        = ASN1_SEQ,
0140     [DIRECTIVE_SET]         = ASN1_SET,
0141     [DIRECTIVE_NumericString]   = ASN1_NUMSTR,
0142     [DIRECTIVE_PrintableString] = ASN1_PRNSTR,
0143     [DIRECTIVE_T61String]       = ASN1_TEXSTR,
0144     [DIRECTIVE_TeletexString]   = ASN1_TEXSTR,
0145     [DIRECTIVE_VideotexString]  = ASN1_VIDSTR,
0146     [DIRECTIVE_IA5String]       = ASN1_IA5STR,
0147     [DIRECTIVE_UTCTime]     = ASN1_UNITIM,
0148     [DIRECTIVE_GeneralizedTime] = ASN1_GENTIM,
0149     [DIRECTIVE_GraphicString]   = ASN1_GRASTR,
0150     [DIRECTIVE_VisibleString]   = ASN1_VISSTR,
0151     [DIRECTIVE_GeneralString]   = ASN1_GENSTR,
0152     [DIRECTIVE_UniversalString] = ASN1_UNITIM,
0153     [DIRECTIVE_CHARACTER]       = ASN1_CHRSTR,
0154     [DIRECTIVE_BMPString]       = ASN1_BMPSTR,
0155 };
0156 
0157 static const char asn1_classes[4][5] = {
0158     [ASN1_UNIV] = "UNIV",
0159     [ASN1_APPL] = "APPL",
0160     [ASN1_CONT] = "CONT",
0161     [ASN1_PRIV] = "PRIV"
0162 };
0163 
0164 static const char asn1_methods[2][5] = {
0165     [ASN1_UNIV] = "PRIM",
0166     [ASN1_APPL] = "CONS"
0167 };
0168 
0169 static const char *const asn1_universal_tags[32] = {
0170     "EOC",
0171     "BOOL",
0172     "INT",
0173     "BTS",
0174     "OTS",
0175     "NULL",
0176     "OID",
0177     "ODE",
0178     "EXT",
0179     "REAL",
0180     "ENUM",
0181     "EPDV",
0182     "UTF8STR",
0183     "RELOID",
0184     NULL,       /* 14 */
0185     NULL,       /* 15 */
0186     "SEQ",
0187     "SET",
0188     "NUMSTR",
0189     "PRNSTR",
0190     "TEXSTR",
0191     "VIDSTR",
0192     "IA5STR",
0193     "UNITIM",
0194     "GENTIM",
0195     "GRASTR",
0196     "VISSTR",
0197     "GENSTR",
0198     "UNISTR",
0199     "CHRSTR",
0200     "BMPSTR",
0201     NULL        /* 31 */
0202 };
0203 
0204 static const char *filename;
0205 static const char *grammar_name;
0206 static const char *outputname;
0207 static const char *headername;
0208 
0209 static const char *const directives[NR__DIRECTIVES] = {
0210 #define _(X) [DIRECTIVE_##X] = #X
0211     _(ABSENT),
0212     _(ALL),
0213     _(ANY),
0214     _(APPLICATION),
0215     _(AUTOMATIC),
0216     _(BEGIN),
0217     _(BIT),
0218     _(BMPString),
0219     _(BOOLEAN),
0220     _(BY),
0221     _(CHARACTER),
0222     _(CHOICE),
0223     _(CLASS),
0224     _(COMPONENT),
0225     _(COMPONENTS),
0226     _(CONSTRAINED),
0227     _(CONTAINING),
0228     _(DEFAULT),
0229     _(DEFINED),
0230     _(DEFINITIONS),
0231     _(EMBEDDED),
0232     _(ENCODED),
0233     [DIRECTIVE_ENCODING_CONTROL] = "ENCODING-CONTROL",
0234     _(END),
0235     _(ENUMERATED),
0236     _(EXCEPT),
0237     _(EXPLICIT),
0238     _(EXPORTS),
0239     _(EXTENSIBILITY),
0240     _(EXTERNAL),
0241     _(FALSE),
0242     _(FROM),
0243     _(GeneralString),
0244     _(GeneralizedTime),
0245     _(GraphicString),
0246     _(IA5String),
0247     _(IDENTIFIER),
0248     _(IMPLICIT),
0249     _(IMPLIED),
0250     _(IMPORTS),
0251     _(INCLUDES),
0252     _(INSTANCE),
0253     _(INSTRUCTIONS),
0254     _(INTEGER),
0255     _(INTERSECTION),
0256     _(ISO646String),
0257     _(MAX),
0258     _(MIN),
0259     [DIRECTIVE_MINUS_INFINITY] = "MINUS-INFINITY",
0260     [DIRECTIVE_NULL] = "NULL",
0261     _(NumericString),
0262     _(OBJECT),
0263     _(OCTET),
0264     _(OF),
0265     _(OPTIONAL),
0266     _(ObjectDescriptor),
0267     _(PATTERN),
0268     _(PDV),
0269     [DIRECTIVE_PLUS_INFINITY] = "PLUS-INFINITY",
0270     _(PRESENT),
0271     _(PRIVATE),
0272     _(PrintableString),
0273     _(REAL),
0274     [DIRECTIVE_RELATIVE_OID] = "RELATIVE-OID",
0275     _(SEQUENCE),
0276     _(SET),
0277     _(SIZE),
0278     _(STRING),
0279     _(SYNTAX),
0280     _(T61String),
0281     _(TAGS),
0282     _(TRUE),
0283     _(TeletexString),
0284     _(UNION),
0285     _(UNIQUE),
0286     _(UNIVERSAL),
0287     _(UTCTime),
0288     _(UTF8String),
0289     _(UniversalString),
0290     _(VideotexString),
0291     _(VisibleString),
0292     _(WITH)
0293 };
0294 
0295 struct action {
0296     struct action   *next;
0297     char        *name;
0298     unsigned char   index;
0299 };
0300 
0301 static struct action *action_list;
0302 static unsigned nr_actions;
0303 
0304 struct token {
0305     unsigned short  line;
0306     enum token_type token_type : 8;
0307     unsigned char   size;
0308     struct action   *action;
0309     char        *content;
0310     struct type *type;
0311 };
0312 
0313 static struct token *token_list;
0314 static unsigned nr_tokens;
0315 static bool verbose_opt;
0316 static bool debug_opt;
0317 
0318 #define verbose(fmt, ...) do { if (verbose_opt) printf(fmt, ## __VA_ARGS__); } while (0)
0319 #define debug(fmt, ...) do { if (debug_opt) printf(fmt, ## __VA_ARGS__); } while (0)
0320 
0321 static int directive_compare(const void *_key, const void *_pdir)
0322 {
0323     const struct token *token = _key;
0324     const char *const *pdir = _pdir, *dir = *pdir;
0325     size_t dlen, clen;
0326     int val;
0327 
0328     dlen = strlen(dir);
0329     clen = (dlen < token->size) ? dlen : token->size;
0330 
0331     //debug("cmp(%s,%s) = ", token->content, dir);
0332 
0333     val = memcmp(token->content, dir, clen);
0334     if (val != 0) {
0335         //debug("%d [cmp]\n", val);
0336         return val;
0337     }
0338 
0339     if (dlen == token->size) {
0340         //debug("0\n");
0341         return 0;
0342     }
0343     //debug("%d\n", (int)dlen - (int)token->size);
0344     return dlen - token->size; /* shorter -> negative */
0345 }
0346 
0347 /*
0348  * Tokenise an ASN.1 grammar
0349  */
0350 static void tokenise(char *buffer, char *end)
0351 {
0352     struct token *tokens;
0353     char *line, *nl, *start, *p, *q;
0354     unsigned tix, lineno;
0355 
0356     /* Assume we're going to have half as many tokens as we have
0357      * characters
0358      */
0359     token_list = tokens = calloc((end - buffer) / 2, sizeof(struct token));
0360     if (!tokens) {
0361         perror(NULL);
0362         exit(1);
0363     }
0364     tix = 0;
0365 
0366     lineno = 0;
0367     while (buffer < end) {
0368         /* First of all, break out a line */
0369         lineno++;
0370         line = buffer;
0371         nl = memchr(line, '\n', end - buffer);
0372         if (!nl) {
0373             buffer = nl = end;
0374         } else {
0375             buffer = nl + 1;
0376             *nl = '\0';
0377         }
0378 
0379         /* Remove "--" comments */
0380         p = line;
0381     next_comment:
0382         while ((p = memchr(p, '-', nl - p))) {
0383             if (p[1] == '-') {
0384                 /* Found a comment; see if there's a terminator */
0385                 q = p + 2;
0386                 while ((q = memchr(q, '-', nl - q))) {
0387                     if (q[1] == '-') {
0388                         /* There is - excise the comment */
0389                         q += 2;
0390                         memmove(p, q, nl - q);
0391                         goto next_comment;
0392                     }
0393                     q++;
0394                 }
0395                 *p = '\0';
0396                 nl = p;
0397                 break;
0398             } else {
0399                 p++;
0400             }
0401         }
0402 
0403         p = line;
0404         while (p < nl) {
0405             /* Skip white space */
0406             while (p < nl && isspace(*p))
0407                 *(p++) = 0;
0408             if (p >= nl)
0409                 break;
0410 
0411             tokens[tix].line = lineno;
0412             start = p;
0413 
0414             /* Handle string tokens */
0415             if (isalpha(*p)) {
0416                 const char **dir, *start = p;
0417 
0418                 /* Can be a directive, type name or element
0419                  * name.  Find the end of the name.
0420                  */
0421                 q = p + 1;
0422                 while (q < nl && (isalnum(*q) || *q == '-' || *q == '_'))
0423                     q++;
0424                 tokens[tix].size = q - p;
0425                 p = q;
0426 
0427                 tokens[tix].content = malloc(tokens[tix].size + 1);
0428                 if (!tokens[tix].content) {
0429                     perror(NULL);
0430                     exit(1);
0431                 }
0432                 memcpy(tokens[tix].content, start, tokens[tix].size);
0433                 tokens[tix].content[tokens[tix].size] = 0;
0434                 
0435                 /* If it begins with a lowercase letter then
0436                  * it's an element name
0437                  */
0438                 if (islower(tokens[tix].content[0])) {
0439                     tokens[tix++].token_type = TOKEN_ELEMENT_NAME;
0440                     continue;
0441                 }
0442 
0443                 /* Otherwise we need to search the directive
0444                  * table
0445                  */
0446                 dir = bsearch(&tokens[tix], directives,
0447                           sizeof(directives) / sizeof(directives[1]),
0448                           sizeof(directives[1]),
0449                           directive_compare);
0450                 if (dir) {
0451                     tokens[tix++].token_type = dir - directives;
0452                     continue;
0453                 }
0454 
0455                 tokens[tix++].token_type = TOKEN_TYPE_NAME;
0456                 continue;
0457             }
0458 
0459             /* Handle numbers */
0460             if (isdigit(*p)) {
0461                 /* Find the end of the number */
0462                 q = p + 1;
0463                 while (q < nl && (isdigit(*q)))
0464                     q++;
0465                 tokens[tix].size = q - p;
0466                 p = q;
0467                 tokens[tix].content = malloc(tokens[tix].size + 1);
0468                 if (!tokens[tix].content) {
0469                     perror(NULL);
0470                     exit(1);
0471                 }
0472                 memcpy(tokens[tix].content, start, tokens[tix].size);
0473                 tokens[tix].content[tokens[tix].size] = 0;
0474                 tokens[tix++].token_type = TOKEN_NUMBER;
0475                 continue;
0476             }
0477 
0478             if (nl - p >= 3) {
0479                 if (memcmp(p, "::=", 3) == 0) {
0480                     p += 3;
0481                     tokens[tix].size = 3;
0482                     tokens[tix].content = "::=";
0483                     tokens[tix++].token_type = TOKEN_ASSIGNMENT;
0484                     continue;
0485                 }
0486             }
0487 
0488             if (nl - p >= 2) {
0489                 if (memcmp(p, "({", 2) == 0) {
0490                     p += 2;
0491                     tokens[tix].size = 2;
0492                     tokens[tix].content = "({";
0493                     tokens[tix++].token_type = TOKEN_OPEN_ACTION;
0494                     continue;
0495                 }
0496                 if (memcmp(p, "})", 2) == 0) {
0497                     p += 2;
0498                     tokens[tix].size = 2;
0499                     tokens[tix].content = "})";
0500                     tokens[tix++].token_type = TOKEN_CLOSE_ACTION;
0501                     continue;
0502                 }
0503             }
0504 
0505             if (nl - p >= 1) {
0506                 tokens[tix].size = 1;
0507                 switch (*p) {
0508                 case '{':
0509                     p += 1;
0510                     tokens[tix].content = "{";
0511                     tokens[tix++].token_type = TOKEN_OPEN_CURLY;
0512                     continue;
0513                 case '}':
0514                     p += 1;
0515                     tokens[tix].content = "}";
0516                     tokens[tix++].token_type = TOKEN_CLOSE_CURLY;
0517                     continue;
0518                 case '[':
0519                     p += 1;
0520                     tokens[tix].content = "[";
0521                     tokens[tix++].token_type = TOKEN_OPEN_SQUARE;
0522                     continue;
0523                 case ']':
0524                     p += 1;
0525                     tokens[tix].content = "]";
0526                     tokens[tix++].token_type = TOKEN_CLOSE_SQUARE;
0527                     continue;
0528                 case ',':
0529                     p += 1;
0530                     tokens[tix].content = ",";
0531                     tokens[tix++].token_type = TOKEN_COMMA;
0532                     continue;
0533                 default:
0534                     break;
0535                 }
0536             }
0537 
0538             fprintf(stderr, "%s:%u: Unknown character in grammar: '%c'\n",
0539                 filename, lineno, *p);
0540             exit(1);
0541         }
0542     }
0543 
0544     nr_tokens = tix;
0545     verbose("Extracted %u tokens\n", nr_tokens);
0546 
0547 #if 0
0548     {
0549         int n;
0550         for (n = 0; n < nr_tokens; n++)
0551             debug("Token %3u: '%s'\n", n, token_list[n].content);
0552     }
0553 #endif
0554 }
0555 
0556 static void build_type_list(void);
0557 static void parse(void);
0558 static void dump_elements(void);
0559 static void render(FILE *out, FILE *hdr);
0560 
0561 /*
0562  *
0563  */
0564 int main(int argc, char **argv)
0565 {
0566     struct stat st;
0567     ssize_t readlen;
0568     FILE *out, *hdr;
0569     char *buffer, *p;
0570     char *kbuild_verbose;
0571     int fd;
0572 
0573     kbuild_verbose = getenv("KBUILD_VERBOSE");
0574     if (kbuild_verbose)
0575         verbose_opt = atoi(kbuild_verbose);
0576 
0577     while (argc > 4) {
0578         if (strcmp(argv[1], "-v") == 0)
0579             verbose_opt = true;
0580         else if (strcmp(argv[1], "-d") == 0)
0581             debug_opt = true;
0582         else
0583             break;
0584         memmove(&argv[1], &argv[2], (argc - 2) * sizeof(char *));
0585         argc--;
0586     }
0587 
0588     if (argc != 4) {
0589         fprintf(stderr, "Format: %s [-v] [-d] <grammar-file> <c-file> <hdr-file>\n",
0590             argv[0]);
0591         exit(2);
0592     }
0593 
0594     filename = argv[1];
0595     outputname = argv[2];
0596     headername = argv[3];
0597 
0598     fd = open(filename, O_RDONLY);
0599     if (fd < 0) {
0600         perror(filename);
0601         exit(1);
0602     }
0603 
0604     if (fstat(fd, &st) < 0) {
0605         perror(filename);
0606         exit(1);
0607     }
0608 
0609     if (!(buffer = malloc(st.st_size + 1))) {
0610         perror(NULL);
0611         exit(1);
0612     }
0613 
0614     if ((readlen = read(fd, buffer, st.st_size)) < 0) {
0615         perror(filename);
0616         exit(1);
0617     }
0618 
0619     if (close(fd) < 0) {
0620         perror(filename);
0621         exit(1);
0622     }
0623 
0624     if (readlen != st.st_size) {
0625         fprintf(stderr, "%s: Short read\n", filename);
0626         exit(1);
0627     }
0628 
0629     p = strrchr(argv[1], '/');
0630     p = p ? p + 1 : argv[1];
0631     grammar_name = strdup(p);
0632     if (!p) {
0633         perror(NULL);
0634         exit(1);
0635     }
0636     p = strchr(grammar_name, '.');
0637     if (p)
0638         *p = '\0';
0639 
0640     buffer[readlen] = 0;
0641     tokenise(buffer, buffer + readlen);
0642     build_type_list();
0643     parse();
0644     dump_elements();
0645 
0646     out = fopen(outputname, "w");
0647     if (!out) {
0648         perror(outputname);
0649         exit(1);
0650     }
0651 
0652     hdr = fopen(headername, "w");
0653     if (!hdr) {
0654         perror(headername);
0655         exit(1);
0656     }
0657 
0658     render(out, hdr);
0659 
0660     if (fclose(out) < 0) {
0661         perror(outputname);
0662         exit(1);
0663     }
0664 
0665     if (fclose(hdr) < 0) {
0666         perror(headername);
0667         exit(1);
0668     }
0669 
0670     return 0;
0671 }
0672 
0673 enum compound {
0674     NOT_COMPOUND,
0675     SET,
0676     SET_OF,
0677     SEQUENCE,
0678     SEQUENCE_OF,
0679     CHOICE,
0680     ANY,
0681     TYPE_REF,
0682     TAG_OVERRIDE
0683 };
0684 
0685 struct element {
0686     struct type *type_def;
0687     struct token    *name;
0688     struct token    *type;
0689     struct action   *action;
0690     struct element  *children;
0691     struct element  *next;
0692     struct element  *render_next;
0693     struct element  *list_next;
0694     uint8_t     n_elements;
0695     enum compound   compound : 8;
0696     enum asn1_class class : 8;
0697     enum asn1_method method : 8;
0698     uint8_t     tag;
0699     unsigned    entry_index;
0700     unsigned    flags;
0701 #define ELEMENT_IMPLICIT    0x0001
0702 #define ELEMENT_EXPLICIT    0x0002
0703 #define ELEMENT_TAG_SPECIFIED   0x0004
0704 #define ELEMENT_RENDERED    0x0008
0705 #define ELEMENT_SKIPPABLE   0x0010
0706 #define ELEMENT_CONDITIONAL 0x0020
0707 };
0708 
0709 struct type {
0710     struct token    *name;
0711     struct token    *def;
0712     struct element  *element;
0713     unsigned    ref_count;
0714     unsigned    flags;
0715 #define TYPE_STOP_MARKER    0x0001
0716 #define TYPE_BEGIN      0x0002
0717 };
0718 
0719 static struct type *type_list;
0720 static struct type **type_index;
0721 static unsigned nr_types;
0722 
0723 static int type_index_compare(const void *_a, const void *_b)
0724 {
0725     const struct type *const *a = _a, *const *b = _b;
0726 
0727     if ((*a)->name->size != (*b)->name->size)
0728         return (*a)->name->size - (*b)->name->size;
0729     else
0730         return memcmp((*a)->name->content, (*b)->name->content,
0731                   (*a)->name->size);
0732 }
0733 
0734 static int type_finder(const void *_key, const void *_ti)
0735 {
0736     const struct token *token = _key;
0737     const struct type *const *ti = _ti;
0738     const struct type *type = *ti;
0739 
0740     if (token->size != type->name->size)
0741         return token->size - type->name->size;
0742     else
0743         return memcmp(token->content, type->name->content,
0744                   token->size);
0745 }
0746 
0747 /*
0748  * Build up a list of types and a sorted index to that list.
0749  */
0750 static void build_type_list(void)
0751 {
0752     struct type *types;
0753     unsigned nr, t, n;
0754 
0755     nr = 0;
0756     for (n = 0; n < nr_tokens - 1; n++)
0757         if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
0758             token_list[n + 1].token_type == TOKEN_ASSIGNMENT)
0759             nr++;
0760 
0761     if (nr == 0) {
0762         fprintf(stderr, "%s: No defined types\n", filename);
0763         exit(1);
0764     }
0765 
0766     nr_types = nr;
0767     types = type_list = calloc(nr + 1, sizeof(type_list[0]));
0768     if (!type_list) {
0769         perror(NULL);
0770         exit(1);
0771     }
0772     type_index = calloc(nr, sizeof(type_index[0]));
0773     if (!type_index) {
0774         perror(NULL);
0775         exit(1);
0776     }
0777 
0778     t = 0;
0779     types[t].flags |= TYPE_BEGIN;
0780     for (n = 0; n < nr_tokens - 1; n++) {
0781         if (token_list[n + 0].token_type == TOKEN_TYPE_NAME &&
0782             token_list[n + 1].token_type == TOKEN_ASSIGNMENT) {
0783             types[t].name = &token_list[n];
0784             type_index[t] = &types[t];
0785             t++;
0786         }
0787     }
0788     types[t].name = &token_list[n + 1];
0789     types[t].flags |= TYPE_STOP_MARKER;
0790 
0791     qsort(type_index, nr, sizeof(type_index[0]), type_index_compare);
0792 
0793     verbose("Extracted %u types\n", nr_types);
0794 #if 0
0795     for (n = 0; n < nr_types; n++) {
0796         struct type *type = type_index[n];
0797         debug("- %*.*s\n", type->name->content);
0798     }
0799 #endif
0800 }
0801 
0802 static struct element *parse_type(struct token **_cursor, struct token *stop,
0803                   struct token *name);
0804 
0805 /*
0806  * Parse the token stream
0807  */
0808 static void parse(void)
0809 {
0810     struct token *cursor;
0811     struct type *type;
0812 
0813     /* Parse one type definition statement at a time */
0814     type = type_list;
0815     do {
0816         cursor = type->name;
0817 
0818         if (cursor[0].token_type != TOKEN_TYPE_NAME ||
0819             cursor[1].token_type != TOKEN_ASSIGNMENT)
0820             abort();
0821         cursor += 2;
0822 
0823         type->element = parse_type(&cursor, type[1].name, NULL);
0824         type->element->type_def = type;
0825 
0826         if (cursor != type[1].name) {
0827             fprintf(stderr, "%s:%d: Parse error at token '%s'\n",
0828                 filename, cursor->line, cursor->content);
0829             exit(1);
0830         }
0831 
0832     } while (type++, !(type->flags & TYPE_STOP_MARKER));
0833 
0834     verbose("Extracted %u actions\n", nr_actions);
0835 }
0836 
0837 static struct element *element_list;
0838 
0839 static struct element *alloc_elem(struct token *type)
0840 {
0841     struct element *e = calloc(1, sizeof(*e));
0842     if (!e) {
0843         perror(NULL);
0844         exit(1);
0845     }
0846     e->list_next = element_list;
0847     element_list = e;
0848     return e;
0849 }
0850 
0851 static struct element *parse_compound(struct token **_cursor, struct token *end,
0852                       int alternates);
0853 
0854 /*
0855  * Parse one type definition statement
0856  */
0857 static struct element *parse_type(struct token **_cursor, struct token *end,
0858                   struct token *name)
0859 {
0860     struct element *top, *element;
0861     struct action *action, **ppaction;
0862     struct token *cursor = *_cursor;
0863     struct type **ref;
0864     char *p;
0865     int labelled = 0, implicit = 0;
0866 
0867     top = element = alloc_elem(cursor);
0868     element->class = ASN1_UNIV;
0869     element->method = ASN1_PRIM;
0870     element->tag = token_to_tag[cursor->token_type];
0871     element->name = name;
0872 
0873     /* Extract the tag value if one given */
0874     if (cursor->token_type == TOKEN_OPEN_SQUARE) {
0875         cursor++;
0876         if (cursor >= end)
0877             goto overrun_error;
0878         switch (cursor->token_type) {
0879         case DIRECTIVE_UNIVERSAL:
0880             element->class = ASN1_UNIV;
0881             cursor++;
0882             break;
0883         case DIRECTIVE_APPLICATION:
0884             element->class = ASN1_APPL;
0885             cursor++;
0886             break;
0887         case TOKEN_NUMBER:
0888             element->class = ASN1_CONT;
0889             break;
0890         case DIRECTIVE_PRIVATE:
0891             element->class = ASN1_PRIV;
0892             cursor++;
0893             break;
0894         default:
0895             fprintf(stderr, "%s:%d: Unrecognised tag class token '%s'\n",
0896                 filename, cursor->line, cursor->content);
0897             exit(1);
0898         }
0899 
0900         if (cursor >= end)
0901             goto overrun_error;
0902         if (cursor->token_type != TOKEN_NUMBER) {
0903             fprintf(stderr, "%s:%d: Missing tag number '%s'\n",
0904                 filename, cursor->line, cursor->content);
0905             exit(1);
0906         }
0907 
0908         element->tag &= ~0x1f;
0909         element->tag |= strtoul(cursor->content, &p, 10);
0910         element->flags |= ELEMENT_TAG_SPECIFIED;
0911         if (p - cursor->content != cursor->size)
0912             abort();
0913         cursor++;
0914 
0915         if (cursor >= end)
0916             goto overrun_error;
0917         if (cursor->token_type != TOKEN_CLOSE_SQUARE) {
0918             fprintf(stderr, "%s:%d: Missing closing square bracket '%s'\n",
0919                 filename, cursor->line, cursor->content);
0920             exit(1);
0921         }
0922         cursor++;
0923         if (cursor >= end)
0924             goto overrun_error;
0925         labelled = 1;
0926     }
0927 
0928     /* Handle implicit and explicit markers */
0929     if (cursor->token_type == DIRECTIVE_IMPLICIT) {
0930         element->flags |= ELEMENT_IMPLICIT;
0931         implicit = 1;
0932         cursor++;
0933         if (cursor >= end)
0934             goto overrun_error;
0935     } else if (cursor->token_type == DIRECTIVE_EXPLICIT) {
0936         element->flags |= ELEMENT_EXPLICIT;
0937         cursor++;
0938         if (cursor >= end)
0939             goto overrun_error;
0940     }
0941 
0942     if (labelled) {
0943         if (!implicit)
0944             element->method |= ASN1_CONS;
0945         element->compound = implicit ? TAG_OVERRIDE : SEQUENCE;
0946         element->children = alloc_elem(cursor);
0947         element = element->children;
0948         element->class = ASN1_UNIV;
0949         element->method = ASN1_PRIM;
0950         element->tag = token_to_tag[cursor->token_type];
0951         element->name = name;
0952     }
0953 
0954     /* Extract the type we're expecting here */
0955     element->type = cursor;
0956     switch (cursor->token_type) {
0957     case DIRECTIVE_ANY:
0958         element->compound = ANY;
0959         cursor++;
0960         break;
0961 
0962     case DIRECTIVE_NULL:
0963     case DIRECTIVE_BOOLEAN:
0964     case DIRECTIVE_ENUMERATED:
0965     case DIRECTIVE_INTEGER:
0966         element->compound = NOT_COMPOUND;
0967         cursor++;
0968         break;
0969 
0970     case DIRECTIVE_EXTERNAL:
0971         element->method = ASN1_CONS;
0972 
0973     case DIRECTIVE_BMPString:
0974     case DIRECTIVE_GeneralString:
0975     case DIRECTIVE_GraphicString:
0976     case DIRECTIVE_IA5String:
0977     case DIRECTIVE_ISO646String:
0978     case DIRECTIVE_NumericString:
0979     case DIRECTIVE_PrintableString:
0980     case DIRECTIVE_T61String:
0981     case DIRECTIVE_TeletexString:
0982     case DIRECTIVE_UniversalString:
0983     case DIRECTIVE_UTF8String:
0984     case DIRECTIVE_VideotexString:
0985     case DIRECTIVE_VisibleString:
0986     case DIRECTIVE_ObjectDescriptor:
0987     case DIRECTIVE_GeneralizedTime:
0988     case DIRECTIVE_UTCTime:
0989         element->compound = NOT_COMPOUND;
0990         cursor++;
0991         break;
0992 
0993     case DIRECTIVE_BIT:
0994     case DIRECTIVE_OCTET:
0995         element->compound = NOT_COMPOUND;
0996         cursor++;
0997         if (cursor >= end)
0998             goto overrun_error;
0999         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 }