xref: /openbmc/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