Linux Audio

Check our new training course

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