Skip to content
Snippets Groups Projects
asn1_compiler.c 35.5 KiB
Newer Older
		cursor++;
		break;

	case DIRECTIVE_OBJECT:
		element->compound = NOT_COMPOUND;
		cursor++;
		if (cursor >= end)
			goto overrun_error;
		if (cursor->token_type != DIRECTIVE_IDENTIFIER)
			goto parse_error;
		cursor++;
		break;

	case TOKEN_TYPE_NAME:
		element->compound = TYPE_REF;
		ref = bsearch(cursor, type_index, nr_types, sizeof(type_index[0]),
			      type_finder);
		if (!ref) {
			fprintf(stderr, "%s:%d: Type '%s' undefined\n",
				filename, cursor->line, cursor->content);
			exit(1);
		}
		cursor->type = *ref;
		(*ref)->ref_count++;
		cursor++;
		break;

	case DIRECTIVE_CHOICE:
		element->compound = CHOICE;
		cursor++;
		element->children = parse_compound(&cursor, end, 1);
		break;

	case DIRECTIVE_SEQUENCE:
		element->compound = SEQUENCE;
		element->method = ASN1_CONS;
		cursor++;
		if (cursor >= end)
			goto overrun_error;
		if (cursor->token_type == DIRECTIVE_OF) {
			element->compound = SEQUENCE_OF;
			cursor++;
			if (cursor >= end)
				goto overrun_error;
			element->children = parse_type(&cursor, end, NULL);
		} else {
			element->children = parse_compound(&cursor, end, 0);
		}
		break;

	case DIRECTIVE_SET:
		element->compound = SET;
		element->method = ASN1_CONS;
		cursor++;
		if (cursor >= end)
			goto overrun_error;
		if (cursor->token_type == DIRECTIVE_OF) {
			element->compound = SET_OF;
			cursor++;
			if (cursor >= end)
				goto parse_error;
			element->children = parse_type(&cursor, end, NULL);
		} else {
			element->children = parse_compound(&cursor, end, 1);
		}
		break;

	default:
		fprintf(stderr, "%s:%d: Token '%s' does not introduce a type\n",
			filename, cursor->line, cursor->content);
		exit(1);
	}

	/* Handle elements that are optional */
	if (cursor < end && (cursor->token_type == DIRECTIVE_OPTIONAL ||
			     cursor->token_type == DIRECTIVE_DEFAULT)
	    ) {
		cursor++;
		top->flags |= ELEMENT_SKIPPABLE;
	}

	if (cursor < end && cursor->token_type == TOKEN_OPEN_ACTION) {
		cursor++;
		if (cursor >= end)
			goto overrun_error;
		if (cursor->token_type != TOKEN_ELEMENT_NAME) {
			fprintf(stderr, "%s:%d: Token '%s' is not an action function name\n",
				filename, cursor->line, cursor->content);
		action = malloc(sizeof(struct action));
		if (!action) {
			perror(NULL);
			exit(1);
		}
		action->index = 0;
		action->name = cursor->content;

		for (ppaction = &action_list;
		     *ppaction;
		     ppaction = &(*ppaction)->next
		     ) {
			int cmp = strcmp(action->name, (*ppaction)->name);
			if (cmp == 0) {
				free(action);
				action = *ppaction;
				goto found;
			}
			if (cmp < 0) {
				action->next = *ppaction;
				*ppaction = action;
				nr_actions++;
				goto found;
			}
		}
		action->next = NULL;
		*ppaction = action;
		nr_actions++;
	found:

		element->action = action;
		cursor->action = action;
		cursor++;
		if (cursor >= end)
			goto overrun_error;
		if (cursor->token_type != TOKEN_CLOSE_ACTION) {
			fprintf(stderr, "%s:%d: Missing close action, got '%s'\n",
				filename, cursor->line, cursor->content);
			exit(1);
		}
		cursor++;
	}

	*_cursor = cursor;
	return top;

parse_error:
	fprintf(stderr, "%s:%d: Unexpected token '%s'\n",
		filename, cursor->line, cursor->content);
	exit(1);

overrun_error:
	fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
	exit(1);
}

/*
 * Parse a compound type list
 */
static struct element *parse_compound(struct token **_cursor, struct token *end,
				      int alternates)
{
	struct element *children, **child_p = &children, *element;
	struct token *cursor = *_cursor, *name;

	if (cursor->token_type != TOKEN_OPEN_CURLY) {
		fprintf(stderr, "%s:%d: Expected compound to start with brace not '%s'\n",
			filename, cursor->line, cursor->content);
		exit(1);
	}
	cursor++;
	if (cursor >= end)
		goto overrun_error;

	if (cursor->token_type == TOKEN_OPEN_CURLY) {
		fprintf(stderr, "%s:%d: Empty compound\n",
			filename, cursor->line);
		exit(1);
	}

	for (;;) {
		name = NULL;
		if (cursor->token_type == TOKEN_ELEMENT_NAME) {
			name = cursor;
			cursor++;
			if (cursor >= end)
				goto overrun_error;
		}

		element = parse_type(&cursor, end, name);
		if (alternates)
			element->flags |= ELEMENT_SKIPPABLE | ELEMENT_CONDITIONAL;

		*child_p = element;
		child_p = &element->next;

		if (cursor >= end)
			goto overrun_error;
		if (cursor->token_type != TOKEN_COMMA)
			break;
		cursor++;
		if (cursor >= end)
			goto overrun_error;
	}

	children->flags &= ~ELEMENT_CONDITIONAL;

	if (cursor->token_type != TOKEN_CLOSE_CURLY) {
		fprintf(stderr, "%s:%d: Expected compound closure, got '%s'\n",
			filename, cursor->line, cursor->content);
		exit(1);
	}
	cursor++;

	*_cursor = cursor;
	return children;

overrun_error:
	fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
	exit(1);
}

static void dump_element(const struct element *e, int level)
{
	const struct element *c;
	const struct type *t = e->type_def;
	const char *name = e->name ? e->name->content : ".";
	const char *tname = t && t->name ? t->name->content : ".";
	char tag[32];

	if (e->class == 0 && e->method == 0 && e->tag == 0)
		strcpy(tag, "<...>");
	else if (e->class == ASN1_UNIV)
		sprintf(tag, "%s %s %s",
			asn1_classes[e->class],
			asn1_methods[e->method],
			asn1_universal_tags[e->tag]);
	else
		sprintf(tag, "%s %s %u",
			asn1_classes[e->class],
			asn1_methods[e->method],
			e->tag);

	printf("%c%c%c%c%c %c %*s[*] \e[33m%s\e[m %s %s \e[35m%s\e[m\n",
	       e->flags & ELEMENT_IMPLICIT ? 'I' : '-',
	       e->flags & ELEMENT_EXPLICIT ? 'E' : '-',
	       e->flags & ELEMENT_TAG_SPECIFIED ? 'T' : '-',
	       e->flags & ELEMENT_SKIPPABLE ? 'S' : '-',
	       e->flags & ELEMENT_CONDITIONAL ? 'C' : '-',
	       "-tTqQcaro"[e->compound],
	       level, "",
	       tag,
	       e->action ? e->action->name : "");
	if (e->compound == TYPE_REF)
		dump_element(e->type->type->element, level + 3);
	else
		for (c = e->children; c; c = c->next)
			dump_element(c, level + 3);
}

static void dump_elements(void)
{
	if (debug_opt)
		dump_element(type_list[0].element, 0);
}

static void render_element(FILE *out, struct element *e, struct element *tag);
static void render_out_of_line_list(FILE *out);

static int nr_entries;
static int render_depth = 1;
static struct element *render_list, **render_list_p = &render_list;

__attribute__((format(printf, 2, 3)))
static void render_opcode(FILE *out, const char *fmt, ...)
{
	va_list va;

	if (out) {
		fprintf(out, "\t[%4d] =%*s", nr_entries, render_depth, "");
		va_start(va, fmt);
		vfprintf(out, fmt, va);
		va_end(va);
	}
	nr_entries++;
}

__attribute__((format(printf, 2, 3)))
static void render_more(FILE *out, const char *fmt, ...)
{
	va_list va;

	if (out) {
		va_start(va, fmt);
		vfprintf(out, fmt, va);
		va_end(va);
	}
}

/*
 * Render the grammar into a state machine definition.
 */
static void render(FILE *out, FILE *hdr)
{
	struct element *e;
	struct action *action;
	struct type *root;
	int index;

	fprintf(hdr, "/*\n");
	fprintf(hdr, " * Automatically generated by asn1_compiler.  Do not edit\n");
	fprintf(hdr, " *\n");
	fprintf(hdr, " * ASN.1 parser for %s\n", grammar_name);
	fprintf(hdr, " */\n");
	fprintf(hdr, "#include <linux/asn1_decoder.h>\n");
	fprintf(hdr, "\n");
	fprintf(hdr, "extern const struct asn1_decoder %s_decoder;\n", grammar_name);
	if (ferror(hdr)) {
		perror(headername);
		exit(1);
	}

	fprintf(out, "/*\n");
	fprintf(out, " * Automatically generated by asn1_compiler.  Do not edit\n");
	fprintf(out, " *\n");
	fprintf(out, " * ASN.1 parser for %s\n", grammar_name);
	fprintf(out, " */\n");
	fprintf(out, "#include <linux/asn1_ber_bytecode.h>\n");
	fprintf(out, "#include \"%s-asn1.h\"\n", grammar_name);
	fprintf(out, "\n");
	if (ferror(out)) {
		perror(outputname);
		exit(1);
	}

	/* Tabulate the action functions we might have to call */
	fprintf(hdr, "\n");
	index = 0;
	for (action = action_list; action; action = action->next) {
		action->index = index++;
		fprintf(hdr,
			"extern int %s(void *, size_t, unsigned char,"
			" const void *, size_t);\n",
			action->name);
	}
	fprintf(hdr, "\n");

	fprintf(out, "enum %s_actions {\n", grammar_name);
	for (action = action_list; action; action = action->next)
		fprintf(out, "\tACT_%s = %u,\n",
			action->name, action->index);
	fprintf(out, "\tNR__%s_actions = %u\n", grammar_name, nr_actions);
	fprintf(out, "};\n");

	fprintf(out, "\n");
	fprintf(out, "static const asn1_action_t %s_action_table[NR__%s_actions] = {\n",
		grammar_name, grammar_name);
	for (action = action_list; action; action = action->next)
		fprintf(out, "\t[%4u] = %s,\n", action->index, action->name);
	fprintf(out, "};\n");

	if (ferror(out)) {
		perror(outputname);
		exit(1);
	}

	/* We do two passes - the first one calculates all the offsets */
	nr_entries = 0;
	root = &type_list[0];
	render_element(NULL, root->element, NULL);
	render_opcode(NULL, "ASN1_OP_COMPLETE,\n");
	render_out_of_line_list(NULL);

	for (e = element_list; e; e = e->list_next)
		e->flags &= ~ELEMENT_RENDERED;

	/* And then we actually render */
	fprintf(out, "\n");
	fprintf(out, "static const unsigned char %s_machine[] = {\n",
		grammar_name);

	nr_entries = 0;
	root = &type_list[0];
	render_element(out, root->element, NULL);
	render_opcode(out, "ASN1_OP_COMPLETE,\n");
	render_out_of_line_list(out);

	fprintf(out, "};\n");

	fprintf(out, "\n");
	fprintf(out, "const struct asn1_decoder %s_decoder = {\n", grammar_name);
	fprintf(out, "\t.machine = %s_machine,\n", grammar_name);
	fprintf(out, "\t.machlen = sizeof(%s_machine),\n", grammar_name);
	fprintf(out, "\t.actions = %s_action_table,\n", grammar_name);
	fprintf(out, "};\n");
}

/*
 * Render the out-of-line elements
 */
static void render_out_of_line_list(FILE *out)
{
	struct element *e, *ce;
	const char *act;
	int entry;

	while ((e = render_list)) {
		render_list = e->render_next;
		if (!render_list)
			render_list_p = &render_list;

		render_more(out, "\n");
		e->entry_index = entry = nr_entries;
		render_depth++;
		for (ce = e->children; ce; ce = ce->next)
			render_element(out, ce, NULL);
		render_depth--;

		act = e->action ? "_ACT" : "";
		switch (e->compound) {
		case SEQUENCE:
			render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
			break;
		case SEQUENCE_OF:
			render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
			render_opcode(out, "_jump_target(%u),\n", entry);
			break;
		case SET:
			render_opcode(out, "ASN1_OP_END_SET%s,\n", act);
			break;
		case SET_OF:
			render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
			render_opcode(out, "_jump_target(%u),\n", entry);
			break;
		}
		if (e->action)
			render_opcode(out, "_action(ACT_%s),\n",
				      e->action->name);
		render_opcode(out, "ASN1_OP_RETURN,\n");
	}
}

/*
 * Render an element.
 */
static void render_element(FILE *out, struct element *e, struct element *tag)
{
	struct element *ec, *x;
	const char *cond, *act;
	int entry, skippable = 0, outofline = 0;

	if (e->flags & ELEMENT_SKIPPABLE ||
	    (tag && tag->flags & ELEMENT_SKIPPABLE))
		skippable = 1;

	if ((e->type_def && e->type_def->ref_count > 1) ||
	    skippable)
		outofline = 1;

	if (e->type_def && out) {
		render_more(out, "\t// %s\n", e->type_def->name->content);
	}

	/* Render the operation */
	cond = (e->flags & ELEMENT_CONDITIONAL ||
		(tag && tag->flags & ELEMENT_CONDITIONAL)) ? "COND_" : "";
	act = e->action ? "_ACT" : "";
	switch (e->compound) {
	case ANY:
		render_opcode(out, "ASN1_OP_%sMATCH_ANY%s%s,",
			      cond, act, skippable ? "_OR_SKIP" : "");
			render_more(out, "\t\t// %s", e->name->content);
		render_more(out, "\n");
		goto dont_render_tag;

	case TAG_OVERRIDE:
		render_element(out, e->children, e);
		return;

	case SEQUENCE:
	case SEQUENCE_OF:
	case SET:
	case SET_OF:
		render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
			      cond,
			      outofline ? "_JUMP" : "",
			      skippable ? "_OR_SKIP" : "");
		break;

	case CHOICE:
		goto dont_render_tag;

	case TYPE_REF:
		if (e->class == ASN1_UNIV && e->method == ASN1_PRIM && e->tag == 0)
			goto dont_render_tag;
	default:
		render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
			      cond, act,
			      skippable ? "_OR_SKIP" : "");
		break;
	}

	x = tag ?: e;
	if (x->name)
		render_more(out, "\t\t// %s", x->name->content);
	render_more(out, "\n");

	/* Render the tag */
	if (!tag || !(tag->flags & ELEMENT_TAG_SPECIFIED))
	if (tag->class == ASN1_UNIV &&
	    tag->tag != 14 &&
	    tag->tag != 15 &&
	    tag->tag != 31)
		render_opcode(out, "_tag(%s, %s, %s),\n",
			      asn1_classes[tag->class],
			      asn1_methods[tag->method | e->method],
			      asn1_universal_tags[tag->tag]);
	else
		render_opcode(out, "_tagn(%s, %s, %2u),\n",
			      asn1_classes[tag->class],
			      asn1_methods[tag->method | e->method],
			      tag->tag);
	tag = NULL;
dont_render_tag:

	/* Deal with compound types */
	switch (e->compound) {
	case TYPE_REF:
		render_element(out, e->type->type->element, tag);
		if (e->action)
			render_opcode(out, "ASN1_OP_%sACT,\n",
				      skippable ? "MAYBE_" : "");
		break;

	case SEQUENCE:
		if (outofline) {
			/* Render out-of-line for multiple use or
			 * skipability */
			render_opcode(out, "_jump_target(%u),", e->entry_index);
			if (e->type_def && e->type_def->name)
				render_more(out, "\t\t// --> %s",
					    e->type_def->name->content);
			render_more(out, "\n");
			if (!(e->flags & ELEMENT_RENDERED)) {
				e->flags |= ELEMENT_RENDERED;
				*render_list_p = e;
				render_list_p = &e->render_next;
			}
			return;
		} else {
			/* Render inline for single use */
			render_depth++;
			for (ec = e->children; ec; ec = ec->next)
				render_element(out, ec, NULL);
			render_depth--;
			render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
		}
		break;

	case SEQUENCE_OF:
	case SET_OF:
		if (outofline) {
			/* Render out-of-line for multiple use or
			 * skipability */
			render_opcode(out, "_jump_target(%u),", e->entry_index);
			if (e->type_def && e->type_def->name)
				render_more(out, "\t\t// --> %s",
					    e->type_def->name->content);
			render_more(out, "\n");
			if (!(e->flags & ELEMENT_RENDERED)) {
				e->flags |= ELEMENT_RENDERED;
				*render_list_p = e;
				render_list_p = &e->render_next;
			}
			return;
		} else {
			/* Render inline for single use */
			entry = nr_entries;
			render_depth++;
			render_element(out, e->children, NULL);
			render_depth--;
			if (e->compound == SEQUENCE_OF)
				render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
			else
				render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
			render_opcode(out, "_jump_target(%u),\n", entry);
		}
		break;

	case SET:
		/* I can't think of a nice way to do SET support without having
		 * a stack of bitmasks to make sure no element is repeated.
		 * The bitmask has also to be checked that no non-optional
		 * elements are left out whilst not preventing optional
		 * elements from being left out.
		 */
		fprintf(stderr, "The ASN.1 SET type is not currently supported.\n");
		exit(1);

	case CHOICE:
		for (ec = e->children; ec; ec = ec->next)
			render_element(out, ec, ec);
		if (!skippable)
			render_opcode(out, "ASN1_OP_COND_FAIL,\n");
		if (e->action)
			render_opcode(out, "ASN1_OP_ACT,\n");
		break;

	default:
		break;
	}

	if (e->action)
		render_opcode(out, "_action(ACT_%s),\n", e->action->name);
}