X.509: Add simple ASN.1 grammar compiler

Add a simple ASN.1 grammar compiler.  This produces a bytecode output that can
be fed to a decoder to inform the decoder how to interpret the ASN.1 stream it
is trying to parse.

Action functions can be specified in the grammar by interpolating:

	({ foo })

after a type, for example:

	SubjectPublicKeyInfo ::= SEQUENCE {
		algorithm		AlgorithmIdentifier,
		subjectPublicKey	BIT STRING ({ do_key_data })
		}

The decoder is expected to call these after matching this type and parsing the
contents if it is a constructed type.

The grammar compiler does not currently support the SET type (though it does
support SET OF) as I can't see a good way of tracking which members have been
encountered yet without using up extra stack space.

Currently, the grammar compiler will fail if more than 256 bytes of bytecode
would be produced or more than 256 actions have been specified as it uses
8-bit jump values and action indices to keep space usage down.

Signed-off-by: David Howells <dhowells@redhat.com>
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>

4 files changed, 1559 insertions, 0 deletions

diff --git a/scripts/.gitignore b/scripts/.gitignore
index 65f362d931b5..fb070fa1038f 100644
--- a/scripts/.gitignore
+++ b/scripts/.gitignore
@@ -10,3 +10,4 @@ ihex2fw
 recordmcount
 docproc
 sortextable
+asn1_compiler
diff --git a/scripts/Makefile b/scripts/Makefile
index a55b0067758a..01e7adb838d9 100644
--- a/scripts/Makefile
+++ b/scripts/Makefile
@@ -16,8 +16,10 @@ hostprogs-$(CONFIG_VT)           += conmakehash
 hostprogs-$(CONFIG_IKCONFIG)     += bin2c
 hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
 hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
+hostprogs-$(CONFIG_ASN1)         += asn1_compiler
 
 HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include
+HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
 
 always          := $(hostprogs-y) $(hostprogs-m)
 
diff --git a/scripts/Makefile.build b/scripts/Makefile.build
index ff1720d28d0c..0e801c3cdaf8 100644
--- a/scripts/Makefile.build
+++ b/scripts/Makefile.build
@@ -354,6 +354,17 @@ quiet_cmd_cpp_lds_S = LDS     $@
 $(obj)/%.lds: $(src)/%.lds.S FORCE
         $(call if_changed_dep,cpp_lds_S)
 
+# ASN.1 grammar
+# ---------------------------------------------------------------------------
+quiet_cmd_asn1_compiler = ASN.1   $@
+      cmd_asn1_compiler = $(objtree)/scripts/asn1_compiler $< \
+                                $(subst .h,.c,$@) $(subst .c,.h,$@)
+
+.PRECIOUS: $(objtree)/$(obj)/%-asn1.c $(objtree)/$(obj)/%-asn1.h
+
+$(obj)/%-asn1.c $(obj)/%-asn1.h: $(src)/%.asn1 $(objtree)/scripts/asn1_compiler
+        $(call cmd,asn1_compiler)
+
 # Build the compiled-in targets
 # ---------------------------------------------------------------------------
 
diff --git a/scripts/asn1_compiler.c b/scripts/asn1_compiler.c
new file mode 100644
index 000000000000..db0e5cd34c70
--- /dev/null
+++ b/scripts/asn1_compiler.c
@@ -0,0 +1,1545 @@
+/* Simplified ASN.1 notation parser
+ *
+ * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public Licence
+ * as published by the Free Software Foundation; either version
+ * 2 of the Licence, or (at your option) any later version.
+ */
+
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <ctype.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <linux/asn1_ber_bytecode.h>
+
+enum token_type {
+        DIRECTIVE_ABSENT,
+        DIRECTIVE_ALL,
+        DIRECTIVE_ANY,
+        DIRECTIVE_APPLICATION,
+        DIRECTIVE_AUTOMATIC,
+        DIRECTIVE_BEGIN,
+        DIRECTIVE_BIT,
+        DIRECTIVE_BMPString,
+        DIRECTIVE_BOOLEAN,
+        DIRECTIVE_BY,
+        DIRECTIVE_CHARACTER,
+        DIRECTIVE_CHOICE,
+        DIRECTIVE_CLASS,
+        DIRECTIVE_COMPONENT,
+        DIRECTIVE_COMPONENTS,
+        DIRECTIVE_CONSTRAINED,
+        DIRECTIVE_CONTAINING,
+        DIRECTIVE_DEFAULT,
+        DIRECTIVE_DEFINED,
+        DIRECTIVE_DEFINITIONS,
+        DIRECTIVE_EMBEDDED,
+        DIRECTIVE_ENCODED,
+        DIRECTIVE_ENCODING_CONTROL,
+        DIRECTIVE_END,
+        DIRECTIVE_ENUMERATED,
+        DIRECTIVE_EXCEPT,
+        DIRECTIVE_EXPLICIT,
+        DIRECTIVE_EXPORTS,
+        DIRECTIVE_EXTENSIBILITY,
+        DIRECTIVE_EXTERNAL,
+        DIRECTIVE_FALSE,
+        DIRECTIVE_FROM,
+        DIRECTIVE_GeneralString,
+        DIRECTIVE_GeneralizedTime,
+        DIRECTIVE_GraphicString,
+        DIRECTIVE_IA5String,
+        DIRECTIVE_IDENTIFIER,
+        DIRECTIVE_IMPLICIT,
+        DIRECTIVE_IMPLIED,
+        DIRECTIVE_IMPORTS,
+        DIRECTIVE_INCLUDES,
+        DIRECTIVE_INSTANCE,
+        DIRECTIVE_INSTRUCTIONS,
+        DIRECTIVE_INTEGER,
+        DIRECTIVE_INTERSECTION,
+        DIRECTIVE_ISO646String,
+        DIRECTIVE_MAX,
+        DIRECTIVE_MIN,
+        DIRECTIVE_MINUS_INFINITY,
+        DIRECTIVE_NULL,
+        DIRECTIVE_NumericString,
+        DIRECTIVE_OBJECT,
+        DIRECTIVE_OCTET,
+        DIRECTIVE_OF,
+        DIRECTIVE_OPTIONAL,
+        DIRECTIVE_ObjectDescriptor,
+        DIRECTIVE_PATTERN,
+        DIRECTIVE_PDV,
+        DIRECTIVE_PLUS_INFINITY,
+        DIRECTIVE_PRESENT,
+        DIRECTIVE_PRIVATE,
+        DIRECTIVE_PrintableString,
+        DIRECTIVE_REAL,
+        DIRECTIVE_RELATIVE_OID,
+        DIRECTIVE_SEQUENCE,
+        DIRECTIVE_SET,
+        DIRECTIVE_SIZE,
+        DIRECTIVE_STRING,
+        DIRECTIVE_SYNTAX,
+        DIRECTIVE_T61String,
+        DIRECTIVE_TAGS,
+        DIRECTIVE_TRUE,
+        DIRECTIVE_TeletexString,
+        DIRECTIVE_UNION,
+        DIRECTIVE_UNIQUE,
+        DIRECTIVE_UNIVERSAL,
+        DIRECTIVE_UTCTime,
+        DIRECTIVE_UTF8String,
+        DIRECTIVE_UniversalString,
+        DIRECTIVE_VideotexString,
+        DIRECTIVE_VisibleString,
+        DIRECTIVE_WITH,
+        NR__DIRECTIVES,
+        TOKEN_ASSIGNMENT = NR__DIRECTIVES,
+        TOKEN_OPEN_CURLY,
+        TOKEN_CLOSE_CURLY,
+        TOKEN_OPEN_SQUARE,
+        TOKEN_CLOSE_SQUARE,
+        TOKEN_OPEN_ACTION,
+        TOKEN_CLOSE_ACTION,
+        TOKEN_COMMA,
+        TOKEN_NUMBER,
+        TOKEN_TYPE_NAME,
+        TOKEN_ELEMENT_NAME,
+        NR__TOKENS
+};
+
+static const unsigned char token_to_tag[NR__TOKENS] = {
+        /* EOC goes first */
+        [DIRECTIVE_BOOLEAN]             = ASN1_BOOL,
+        [DIRECTIVE_INTEGER]             = ASN1_INT,
+        [DIRECTIVE_BIT]                 = ASN1_BTS,
+        [DIRECTIVE_OCTET]               = ASN1_OTS,
+        [DIRECTIVE_NULL]                = ASN1_NULL,
+        [DIRECTIVE_OBJECT]              = ASN1_OID,
+        [DIRECTIVE_ObjectDescriptor]    = ASN1_ODE,
+        [DIRECTIVE_EXTERNAL]            = ASN1_EXT,
+        [DIRECTIVE_REAL]                = ASN1_REAL,
+        [DIRECTIVE_ENUMERATED]          = ASN1_ENUM,
+        [DIRECTIVE_EMBEDDED]            = 0,
+        [DIRECTIVE_UTF8String]          = ASN1_UTF8STR,
+        [DIRECTIVE_RELATIVE_OID]        = ASN1_RELOID,
+        /* 14 */
+        /* 15 */
+        [DIRECTIVE_SEQUENCE]            = ASN1_SEQ,
+        [DIRECTIVE_SET]                 = ASN1_SET,
+        [DIRECTIVE_NumericString]       = ASN1_NUMSTR,
+        [DIRECTIVE_PrintableString]     = ASN1_PRNSTR,
+        [DIRECTIVE_T61String]           = ASN1_TEXSTR,
+        [DIRECTIVE_TeletexString]       = ASN1_TEXSTR,
+        [DIRECTIVE_VideotexString]      = ASN1_VIDSTR,
+        [DIRECTIVE_IA5String]           = ASN1_IA5STR,
+