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