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