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