aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Howells <dhowells@redhat.com>2012-09-21 18:31:13 -0400
committerRusty Russell <rusty@rustcorp.com.au>2012-10-07 23:20:19 -0400
commit4520c6a49af833c83de6c74525ce8e07bbe6d783 (patch)
tree66b6b43e95cf270e00aa5cb308a12534f33216d9
parent4f73175d0375a7c1b3ae625e76acee8b39741f28 (diff)
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>
Diffstat
-rw-r--r--include/linux/asn1.h67
-rw-r--r--include/linux/asn1_ber_bytecode.h87
-rw-r--r--init/Kconfig8
-rw-r--r--scripts/.gitignore1
-rw-r--r--scripts/Makefile2
-rw-r--r--scripts/Makefile.build11
-rw-r--r--scripts/asn1_compiler.c1545
7 files changed, 1721 insertions, 0 deletions
diff --git a/include/linux/asn1.h b/include/linux/asn1.h
new file mode 100644
index 000000000000..5c3f4e4b9a23
--- /dev/null
+++ b/include/linux/asn1.h
@@ -0,0 +1,67 @@
1/* ASN.1 BER/DER/CER encoding definitions
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#ifndef _LINUX_ASN1_H
13#define _LINUX_ASN1_H
14
15/* Class */
16enum asn1_class {
17 ASN1_UNIV = 0, /* Universal */
18 ASN1_APPL = 1, /* Application */
19 ASN1_CONT = 2, /* Context */
20 ASN1_PRIV = 3 /* Private */
21};
22#define ASN1_CLASS_BITS 0xc0
23
24
25enum asn1_method {
26 ASN1_PRIM = 0, /* Primitive */
27 ASN1_CONS = 1 /* Constructed */
28};
29#define ASN1_CONS_BIT 0x20
30
31/* Tag */
32enum asn1_tag {
33 ASN1_EOC = 0, /* End Of Contents or N/A */
34 ASN1_BOOL = 1, /* Boolean */
35 ASN1_INT = 2, /* Integer */
36 ASN1_BTS = 3, /* Bit String */
37 ASN1_OTS = 4, /* Octet String */
38 ASN1_NULL = 5, /* Null */
39 ASN1_OID = 6, /* Object Identifier */
40 ASN1_ODE = 7, /* Object Description */
41 ASN1_EXT = 8, /* External */
42 ASN1_REAL = 9, /* Real float */
43 ASN1_ENUM = 10, /* Enumerated */
44 ASN1_EPDV = 11, /* Embedded PDV */
45 ASN1_UTF8STR = 12, /* UTF8 String */
46 ASN1_RELOID = 13, /* Relative OID */
47 /* 14 - Reserved */
48 /* 15 - Reserved */
49 ASN1_SEQ = 16, /* Sequence and Sequence of */
50 ASN1_SET = 17, /* Set and Set of */
51 ASN1_NUMSTR = 18, /* Numerical String */
52 ASN1_PRNSTR = 19, /* Printable String */
53 ASN1_TEXSTR = 20, /* T61 String / Teletext String */
54 ASN1_VIDSTR = 21, /* Videotex String */
55 ASN1_IA5STR = 22, /* IA5 String */
56 ASN1_UNITIM = 23, /* Universal Time */
57 ASN1_GENTIM = 24, /* General Time */
58 ASN1_GRASTR = 25, /* Graphic String */
59 ASN1_VISSTR = 26, /* Visible String */
60 ASN1_GENSTR = 27, /* General String */
61 ASN1_UNISTR = 28, /* Universal String */
62 ASN1_CHRSTR = 29, /* Character String */
63 ASN1_BMPSTR = 30, /* BMP String */
64 ASN1_LONG_TAG = 31 /* Long form tag */
65};
66
67#endif /* _LINUX_ASN1_H */
diff --git a/include/linux/asn1_ber_bytecode.h b/include/linux/asn1_ber_bytecode.h
new file mode 100644
index 000000000000..945d44ae529c
--- /dev/null
+++ b/include/linux/asn1_ber_bytecode.h
@@ -0,0 +1,87 @@
1/* ASN.1 BER/DER/CER parsing state machine internal definitions
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#ifndef _LINUX_ASN1_BER_BYTECODE_H
13#define _LINUX_ASN1_BER_BYTECODE_H
14
15#ifdef __KERNEL__
16#include <linux/types.h>
17#endif
18#include <linux/asn1.h>
19
20typedef int (*asn1_action_t)(void *context,
21 size_t hdrlen, /* In case of ANY type */
22 unsigned char tag, /* In case of ANY type */
23 const void *value, size_t vlen);
24
25struct asn1_decoder {
26 const unsigned char *machine;
27 size_t machlen;
28 const asn1_action_t *actions;
29};
30
31enum asn1_opcode {
32 /* The tag-matching ops come first and the odd-numbered slots
33 * are for OR_SKIP ops.
34 */
35#define ASN1_OP_MATCH__SKIP 0x01
36#define ASN1_OP_MATCH__ACT 0x02
37#define ASN1_OP_MATCH__JUMP 0x04
38#define ASN1_OP_MATCH__ANY 0x08
39#define ASN1_OP_MATCH__COND 0x10
40
41 ASN1_OP_MATCH = 0x00,
42 ASN1_OP_MATCH_OR_SKIP = 0x01,
43 ASN1_OP_MATCH_ACT = 0x02,
44 ASN1_OP_MATCH_ACT_OR_SKIP = 0x03,
45 ASN1_OP_MATCH_JUMP = 0x04,
46 ASN1_OP_MATCH_JUMP_OR_SKIP = 0x05,
47 ASN1_OP_MATCH_ANY = 0x08,
48 ASN1_OP_MATCH_ANY_ACT = 0x0a,
49 /* Everything before here matches unconditionally */
50
51 ASN1_OP_COND_MATCH_OR_SKIP = 0x11,
52 ASN1_OP_COND_MATCH_ACT_OR_SKIP = 0x13,
53 ASN1_OP_COND_MATCH_JUMP_OR_SKIP = 0x15,
54 ASN1_OP_COND_MATCH_ANY = 0x18,
55 ASN1_OP_COND_MATCH_ANY_ACT = 0x1a,
56
57 /* Everything before here will want a tag from the data */
58#define ASN1_OP__MATCHES_TAG ASN1_OP_COND_MATCH_ANY_ACT
59
60 /* These are here to help fill up space */
61 ASN1_OP_COND_FAIL = 0x1b,
62 ASN1_OP_COMPLETE = 0x1c,
63 ASN1_OP_ACT = 0x1d,
64 ASN1_OP_RETURN = 0x1e,
65
66 /* The following eight have bit 0 -> SET, 1 -> OF, 2 -> ACT */
67 ASN1_OP_END_SEQ = 0x20,
68 ASN1_OP_END_SET = 0x21,
69 ASN1_OP_END_SEQ_OF = 0x22,
70 ASN1_OP_END_SET_OF = 0x23,
71 ASN1_OP_END_SEQ_ACT = 0x24,
72 ASN1_OP_END_SET_ACT = 0x25,
73 ASN1_OP_END_SEQ_OF_ACT = 0x26,
74 ASN1_OP_END_SET_OF_ACT = 0x27,
75#define ASN1_OP_END__SET 0x01
76#define ASN1_OP_END__OF 0x02
77#define ASN1_OP_END__ACT 0x04
78
79 ASN1_OP__NR
80};
81
82#define _tag(CLASS, CP, TAG) ((ASN1_##CLASS << 6) | (ASN1_##CP << 5) | ASN1_##TAG)
83#define _tagn(CLASS, CP, TAG) ((ASN1_##CLASS << 6) | (ASN1_##CP << 5) | TAG)
84#define _jump_target(N) (N)
85#define _action(N) (N)
86
87#endif /* _LINUX_ASN1_BER_BYTECODE_H */
diff --git a/init/Kconfig b/init/Kconfig
index af6c7f8ba019..66cc885abbc6 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1612,4 +1612,12 @@ config PADATA
1612 depends on SMP 1612 depends on SMP
1613 bool 1613 bool
1614 1614
1615config ASN1
1616 tristate
1617 help
1618 Build a simple ASN.1 grammar compiler that produces a bytecode output
1619 that can be interpreted by the ASN.1 stream decoder and used to
1620 inform it as to what tags are to be expected in a stream and what
1621 functions to call on what tags.
1622
1615source "kernel/Kconfig.locks" 1623source "kernel/Kconfig.locks"
diff --git a/scripts/.gitignore b/scripts/.gitignore
index 65f362d931b5..fb070fa1038f 100644
--- a/scripts/.gitignore
+++ b/scripts/.gitignore
@@ -10,3 +10,4 @@ ihex2fw
10recordmcount 10recordmcount
11docproc 11docproc
12sortextable 12sortextable
13asn1_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
16hostprogs-$(CONFIG_IKCONFIG) += bin2c 16hostprogs-$(CONFIG_IKCONFIG) += bin2c
17hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount 17hostprogs-$(BUILD_C_RECORDMCOUNT) += recordmcount
18hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable 18hostprogs-$(CONFIG_BUILDTIME_EXTABLE_SORT) += sortextable
19hostprogs-$(CONFIG_ASN1) += asn1_compiler
19 20
20HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include 21HOSTCFLAGS_sortextable.o = -I$(srctree)/tools/include
22HOSTCFLAGS_asn1_compiler.o = -I$(srctree)/include
21 23
22always := $(hostprogs-y) $(hostprogs-m) 24always := $(hostprogs-y) $(hostprogs-m)
23 25
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 $@
354$(obj)/%.lds: $(src)/%.lds.S FORCE 354$(obj)/%.lds: $(src)/%.lds.S FORCE
355 $(call if_changed_dep,cpp_lds_S) 355 $(call if_changed_dep,cpp_lds_S)
356 356
357# ASN.1 grammar
358# ---------------------------------------------------------------------------
359quiet_cmd_asn1_compiler = ASN.1 $@
360 cmd_asn1_compiler = $(objtree)/scripts/asn1_compiler $< \
361 $(subst .h,.c,$@) $(subst .c,.h,$@)
362
363.PRECIOUS: $(objtree)/$(obj)/%-asn1.c $(objtree)/$(obj)/%-asn1.h
364
365$(obj)/%-asn1.c $(obj)/%-asn1.h: $(src)/%.asn1 $(objtree)/scripts/asn1_compiler
366 $(call cmd,asn1_compiler)
367
357# Build the compiled-in targets 368# Build the compiled-in targets
358# --------------------------------------------------------------------------- 369# ---------------------------------------------------------------------------
359 370
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 @@
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 }
1357 if (e->action)
1358 render_opcode(out, "_action(ACT_%s),\n",
1359 e->action->name);
1360 render_opcode(out, "ASN1_OP_RETURN,\n");
1361 }
1362}
1363
1364/*
1365 * Render an element.
1366 */
1367static void render_element(FILE *out, struct element *e, struct element *tag)
1368{
1369 struct element *ec;
1370 const char *cond, *act;
1371 int entry, skippable = 0, outofline = 0;
1372
1373 if (e->flags & ELEMENT_SKIPPABLE ||
1374 (tag && tag->flags & ELEMENT_SKIPPABLE))
1375 skippable = 1;
1376
1377 if ((e->type_def && e->type_def->ref_count > 1) ||
1378 skippable)
1379 outofline = 1;
1380
1381 if (e->type_def && out) {
1382 render_more(out, "\t// %*.*s\n",
1383 (int)e->type_def->name->size, (int)e->type_def->name->size,
1384 e->type_def->name->value);
1385 }
1386
1387 /* Render the operation */
1388 cond = (e->flags & ELEMENT_CONDITIONAL ||
1389 (tag && tag->flags & ELEMENT_CONDITIONAL)) ? "COND_" : "";
1390 act = e->action ? "_ACT" : "";
1391 switch (e->compound) {
1392 case ANY:
1393 render_opcode(out, "ASN1_OP_%sMATCH_ANY%s,", cond, act);
1394 if (e->name)
1395 render_more(out, "\t\t// %*.*s",
1396 (int)e->name->size, (int)e->name->size,
1397 e->name->value);
1398 render_more(out, "\n");
1399 goto dont_render_tag;
1400
1401 case TAG_OVERRIDE:
1402 render_element(out, e->children, e);
1403 return;
1404
1405 case SEQUENCE:
1406 case SEQUENCE_OF:
1407 case SET:
1408 case SET_OF:
1409 render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
1410 cond,
1411 outofline ? "_JUMP" : "",
1412 skippable ? "_OR_SKIP" : "");
1413 break;
1414
1415 case CHOICE:
1416 goto dont_render_tag;
1417
1418 case TYPE_REF:
1419 if (e->class == ASN1_UNIV && e->method == ASN1_PRIM && e->tag == 0)
1420 goto dont_render_tag;
1421 default:
1422 render_opcode(out, "ASN1_OP_%sMATCH%s%s,",
1423 cond, act,
1424 skippable ? "_OR_SKIP" : "");
1425 break;
1426 }
1427
1428 if (e->name)
1429 render_more(out, "\t\t// %*.*s",
1430 (int)e->name->size, (int)e->name->size,
1431 e->name->value);
1432 render_more(out, "\n");
1433
1434 /* Render the tag */
1435 if (!tag)
1436 tag = e;
1437 if (tag->class == ASN1_UNIV &&
1438 tag->tag != 14 &&
1439 tag->tag != 15 &&
1440 tag->tag != 31)
1441 render_opcode(out, "_tag(%s, %s, %s),\n",
1442 asn1_classes[tag->class],
1443 asn1_methods[tag->method | e->method],
1444 asn1_universal_tags[tag->tag]);
1445 else
1446 render_opcode(out, "_tagn(%s, %s, %2u),\n",
1447 asn1_classes[tag->class],
1448 asn1_methods[tag->method | e->method],
1449 tag->tag);
1450 tag = NULL;
1451dont_render_tag:
1452
1453 /* Deal with compound types */
1454 switch (e->compound) {
1455 case TYPE_REF:
1456 render_element(out, e->type->type->element, tag);
1457 if (e->action)
1458 render_opcode(out, "ASN1_OP_ACT,\n");
1459 break;
1460
1461 case SEQUENCE:
1462 if (outofline) {
1463 /* Render out-of-line for multiple use or
1464 * skipability */
1465 render_opcode(out, "_jump_target(%u),", e->entry_index);
1466 if (e->type_def && e->type_def->name)
1467 render_more(out, "\t\t// --> %*.*s",
1468 (int)e->type_def->name->size,
1469 (int)e->type_def->name->size,
1470 e->type_def->name->value);
1471 render_more(out, "\n");
1472 if (!(e->flags & ELEMENT_RENDERED)) {
1473 e->flags |= ELEMENT_RENDERED;
1474 *render_list_p = e;
1475 render_list_p = &e->render_next;
1476 }
1477 return;
1478 } else {
1479 /* Render inline for single use */
1480 render_depth++;
1481 for (ec = e->children; ec; ec = ec->next)
1482 render_element(out, ec, NULL);
1483 render_depth--;
1484 render_opcode(out, "ASN1_OP_END_SEQ%s,\n", act);
1485 }
1486 break;
1487
1488 case SEQUENCE_OF:
1489 case SET_OF:
1490 if (outofline) {
1491 /* Render out-of-line for multiple use or
1492 * skipability */
1493 render_opcode(out, "_jump_target(%u),", e->entry_index);
1494 if (e->type_def && e->type_def->name)
1495 render_more(out, "\t\t// --> %*.*s",
1496 (int)e->type_def->name->size,
1497 (int)e->type_def->name->size,
1498 e->type_def->name->value);
1499 render_more(out, "\n");
1500 if (!(e->flags & ELEMENT_RENDERED)) {
1501 e->flags |= ELEMENT_RENDERED;
1502 *render_list_p = e;
1503 render_list_p = &e->render_next;
1504 }
1505 return;
1506 } else {
1507 /* Render inline for single use */
1508 entry = nr_entries;
1509 render_depth++;
1510 render_element(out, e->children, NULL);
1511 render_depth--;
1512 if (e->compound == SEQUENCE_OF)
1513 render_opcode(out, "ASN1_OP_END_SEQ_OF%s,\n", act);
1514 else
1515 render_opcode(out, "ASN1_OP_END_SET_OF%s,\n", act);
1516 render_opcode(out, "_jump_target(%u),\n", entry);
1517 }
1518 break;
1519
1520 case SET:
1521 /* I can't think of a nice way to do SET support without having
1522 * a stack of bitmasks to make sure no element is repeated.
1523 * The bitmask has also to be checked that no non-optional
1524 * elements are left out whilst not preventing optional
1525 * elements from being left out.
1526 */
1527 fprintf(stderr, "The ASN.1 SET type is not currently supported.\n");
1528 exit(1);
1529
1530 case CHOICE:
1531 for (ec = e->children; ec; ec = ec->next)
1532 render_element(out, ec, NULL);
1533 if (!skippable)
1534 render_opcode(out, "ASN1_OP_COND_FAIL,\n");
1535 if (e->action)
1536 render_opcode(out, "ASN1_OP_ACT,\n");
1537 break;
1538
1539 default:
1540 break;
1541 }
1542
1543 if (e->action)
1544 render_opcode(out, "_action(ACT_%s),\n", e->action->name);
1545}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-04 11:12:10 -0500