drivers/rtc/rtc-sirfsoc.c: add rtc drivers for CSR SiRFprimaII and SiRFatlasVI
[linux/fpc-iii.git] / scripts / asn1_compiler.c
blobdb0e5cd34c70866e097e0af91d745d1d96d579fe
1 /* Simplified ASN.1 notation parser
3 * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
4 * Written by David Howells (dhowells@redhat.com)
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.
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>
23 enum 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
121 static 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,
156 static const char asn1_classes[4][5] = {
157 [ASN1_UNIV] = "UNIV",
158 [ASN1_APPL] = "APPL",
159 [ASN1_CONT] = "CONT",
160 [ASN1_PRIV] = "PRIV"
163 static const char asn1_methods[2][5] = {
164 [ASN1_UNIV] = "PRIM",
165 [ASN1_APPL] = "CONS"
168 static 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 */
203 static const char *filename;
204 static const char *grammar_name;
205 static const char *outputname;
206 static const char *headername;
208 static 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)
294 struct action {
295 struct action *next;
296 unsigned char index;
297 char name[];
300 static struct action *action_list;
301 static unsigned nr_actions;
303 struct 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;
312 static struct token *token_list;
313 static unsigned nr_tokens;
315 static int directive_compare(const void *_key, const void *_pdir)
317 const struct token *token = _key;
318 const char *const *pdir = _pdir, *dir = *pdir;
319 size_t dlen, clen;
320 int val;
322 dlen = strlen(dir);
323 clen = (dlen < token->size) ? dlen : token->size;
325 //printf("cmp(%*.*s,%s) = ",
326 // (int)token->size, (int)token->size, token->value,
327 // dir);
329 val = memcmp(token->value, dir, clen);
330 if (val != 0) {
331 //printf("%d [cmp]\n", val);
332 return val;
335 if (dlen == token->size) {
336 //printf("0\n");
337 return 0;
339 //printf("%d\n", (int)dlen - (int)token->size);
340 return dlen - token->size; /* shorter -> negative */
344 * Tokenise an ASN.1 grammar
346 static void tokenise(char *buffer, char *end)
348 struct token *tokens;
349 char *line, *nl, *p, *q;
350 unsigned tix, lineno;
352 /* Assume we're going to have half as many tokens as we have
353 * characters
355 token_list = tokens = calloc((end - buffer) / 2, sizeof(struct token));
356 if (!tokens) {
357 perror(NULL);
358 exit(1);
360 tix = 0;
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';
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;
389 q++;
391 *p = '\0';
392 nl = p;
393 break;
394 } else {
395 p++;
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;
407 tokens[tix].line = lineno;
408 tokens[tix].value = p;
410 /* Handle string tokens */
411 if (isalpha(*p)) {
412 const char **dir;
414 /* Can be a directive, type name or element
415 * name. Find the end of the name.
417 q = p + 1;
418 while (q < nl && (isalnum(*q) || *q == '-' || *q == '_'))
419 q++;
420 tokens[tix].size = q - p;
421 p = q;
423 /* If it begins with a lowercase letter then
424 * it's an element name
426 if (islower(tokens[tix].value[0])) {
427 tokens[tix++].token_type = TOKEN_ELEMENT_NAME;
428 continue;
431 /* Otherwise we need to search the directive
432 * table
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;
443 tokens[tix++].token_type = TOKEN_TYPE_NAME;
444 continue;
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;
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;
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;
475 if (memcmp(p, "})", 2) == 0) {
476 p += 2;
477 tokens[tix].size = 2;
478 tokens[tix++].token_type = TOKEN_CLOSE_ACTION;
479 continue;
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;
511 fprintf(stderr, "%s:%u: Unknown character in grammar: '%c'\n",
512 filename, lineno, *p);
513 exit(1);
517 nr_tokens = tix;
518 printf("Extracted %u tokens\n", nr_tokens);
520 #if 0
522 int n;
523 for (n = 0; n < nr_tokens; n++)
524 printf("Token %3u: '%*.*s'\n",
526 (int)token_list[n].size, (int)token_list[n].size,
527 token_list[n].value);
529 #endif
532 static void build_type_list(void);
533 static void parse(void);
534 static void render(FILE *out, FILE *hdr);
539 int main(int argc, char **argv)
541 struct stat st;
542 ssize_t readlen;
543 FILE *out, *hdr;
544 char *buffer, *p;
545 int fd;
547 if (argc != 4) {
548 fprintf(stderr, "Format: %s <grammar-file> <c-file> <hdr-file>\n",
549 argv[0]);
550 exit(2);
553 filename = argv[1];
554 outputname = argv[2];
555 headername = argv[3];
557 fd = open(filename, O_RDONLY);
558 if (fd < 0) {
559 perror(filename);
560 exit(1);
563 if (fstat(fd, &st) < 0) {
564 perror(filename);
565 exit(1);
568 if (!(buffer = malloc(st.st_size + 1))) {
569 perror(NULL);
570 exit(1);
573 if ((readlen = read(fd, buffer, st.st_size)) < 0) {
574 perror(filename);
575 exit(1);
578 if (close(fd) < 0) {
579 perror(filename);
580 exit(1);
583 if (readlen != st.st_size) {
584 fprintf(stderr, "%s: Short read\n", filename);
585 exit(1);
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);
595 p = strchr(grammar_name, '.');
596 if (p)
597 *p = '\0';
599 buffer[readlen] = 0;
600 tokenise(buffer, buffer + readlen);
601 build_type_list();
602 parse();
604 out = fopen(outputname, "w");
605 if (!out) {
606 perror(outputname);
607 exit(1);
610 hdr = fopen(headername, "w");
611 if (!out) {
612 perror(headername);
613 exit(1);
616 render(out, hdr);
618 if (fclose(out) < 0) {
619 perror(outputname);
620 exit(1);
623 if (fclose(hdr) < 0) {
624 perror(headername);
625 exit(1);
628 return 0;
631 enum compound {
632 NOT_COMPOUND,
633 SET,
634 SET_OF,
635 SEQUENCE,
636 SEQUENCE_OF,
637 CHOICE,
638 ANY,
639 TYPE_REF,
640 TAG_OVERRIDE
643 struct 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
667 struct 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
677 static struct type *type_list;
678 static struct type **type_index;
679 static unsigned nr_types;
681 static int type_index_compare(const void *_a, const void *_b)
683 const struct type *const *a = _a, *const *b = _b;
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);
692 static int type_finder(const void *_key, const void *_ti)
694 const struct token *token = _key;
695 const struct type *const *ti = _ti;
696 const struct type *type = *ti;
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);
706 * Build up a list of types and a sorted index to that list.
708 static void build_type_list(void)
710 struct type *types;
711 unsigned nr, t, n;
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++;
719 if (nr == 0) {
720 fprintf(stderr, "%s: No defined types\n", filename);
721 exit(1);
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);
730 type_index = calloc(nr, sizeof(type_index[0]));
731 if (!type_index) {
732 perror(NULL);
733 exit(1);
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++;
746 types[t].name = &token_list[n + 1];
747 types[t].flags |= TYPE_STOP_MARKER;
749 qsort(type_index, nr, sizeof(type_index[0]), type_index_compare);
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);
760 #endif
763 static struct element *parse_type(struct token **_cursor, struct token *stop,
764 struct token *name);
767 * Parse the token stream
769 static void parse(void)
771 struct token *cursor;
772 struct type *type;
774 /* Parse one type definition statement at a time */
775 type = type_list;
776 do {
777 cursor = type->name;
779 if (cursor[0].token_type != TOKEN_TYPE_NAME ||
780 cursor[1].token_type != TOKEN_ASSIGNMENT)
781 abort();
782 cursor += 2;
784 type->element = parse_type(&cursor, type[1].name, NULL);
785 type->element->type_def = type;
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);
794 } while (type++, !(type->flags & TYPE_STOP_MARKER));
796 printf("Extracted %u actions\n", nr_actions);
799 static struct element *element_list;
801 static struct element *alloc_elem(struct token *type)
803 struct element *e = calloc(1, sizeof(*e));
804 if (!e) {
805 perror(NULL);
806 exit(1);
808 e->list_next = element_list;
809 element_list = e;
810 return e;
813 static struct element *parse_compound(struct token **_cursor, struct token *end,
814 int alternates);
817 * Parse one type definition statement
819 static struct element *parse_type(struct token **_cursor, struct token *end,
820 struct token *name)
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;
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;
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);
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);
872 element->tag &= ~0x1f;
873 element->tag |= strtoul(cursor->value, &p, 10);
874 if (p - cursor->value != cursor->size)
875 abort();
876 cursor++;
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);
886 cursor++;
887 if (cursor >= end)
888 goto overrun_error;
889 labelled = 1;
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;
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;
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;
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;
934 case DIRECTIVE_EXTERNAL:
935 element->method = ASN1_CONS;
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;
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;
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;
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);
988 cursor->type = *ref;
989 (*ref)->ref_count++;
990 cursor++;
991 break;
993 case DIRECTIVE_CHOICE:
994 element->compound = CHOICE;
995 cursor++;
996 element->children = parse_compound(&cursor, end, 1);
997 break;
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);
1014 break;
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);
1031 break;
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);
1040 /* Handle elements that are optional */
1041 if (cursor < end && (cursor->token_type == DIRECTIVE_OPTIONAL ||
1042 cursor->token_type == DIRECTIVE_DEFAULT)
1044 cursor++;
1045 top->flags |= ELEMENT_SKIPPABLE;
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);
1059 action = malloc(sizeof(struct action) + cursor->size + 1);
1060 if (!action) {
1061 perror(NULL);
1062 exit(1);
1064 action->index = 0;
1065 memcpy(action->name, cursor->value, cursor->size);
1066 action->name[cursor->size] = 0;
1068 for (ppaction = &action_list;
1069 *ppaction;
1070 ppaction = &(*ppaction)->next
1072 int cmp = strcmp(action->name, (*ppaction)->name);
1073 if (cmp == 0) {
1074 free(action);
1075 action = *ppaction;
1076 goto found;
1078 if (cmp < 0) {
1079 action->next = *ppaction;
1080 *ppaction = action;
1081 nr_actions++;
1082 goto found;
1085 action->next = NULL;
1086 *ppaction = action;
1087 nr_actions++;
1088 found:
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);
1101 cursor++;
1104 *_cursor = cursor;
1105 return top;
1107 parse_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);
1113 overrun_error:
1114 fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1115 exit(1);
1119 * Parse a compound type list
1121 static struct element *parse_compound(struct token **_cursor, struct token *end,
1122 int alternates)
1124 struct element *children, **child_p = &children, *element;
1125 struct token *cursor = *_cursor, *name;
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);
1133 cursor++;
1134 if (cursor >= end)
1135 goto overrun_error;
1137 if (cursor->token_type == TOKEN_OPEN_CURLY) {
1138 fprintf(stderr, "%s:%d: Empty compound\n",
1139 filename, cursor->line);
1140 exit(1);
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;
1152 element = parse_type(&cursor, end, name);
1153 if (alternates)
1154 element->flags |= ELEMENT_SKIPPABLE | ELEMENT_CONDITIONAL;
1156 *child_p = element;
1157 child_p = &element->next;
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;
1168 children->flags &= ~ELEMENT_CONDITIONAL;
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);
1176 cursor++;
1178 *_cursor = cursor;
1179 return children;
1181 overrun_error:
1182 fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1183 exit(1);
1186 static void render_element(FILE *out, struct element *e, struct element *tag);
1187 static void render_out_of_line_list(FILE *out);
1189 static int nr_entries;
1190 static int render_depth = 1;
1191 static struct element *render_list, **render_list_p = &render_list;
1193 __attribute__((format(printf, 2, 3)))
1194 static void render_opcode(FILE *out, const char *fmt, ...)
1196 va_list va;
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);
1204 nr_entries++;
1207 __attribute__((format(printf, 2, 3)))
1208 static void render_more(FILE *out, const char *fmt, ...)
1210 va_list va;
1212 if (out) {
1213 va_start(va, fmt);
1214 vfprintf(out, fmt, va);
1215 va_end(va);
1220 * Render the grammar into a state machine definition.
1222 static void render(FILE *out, FILE *hdr)
1224 struct element *e;
1225 struct action *action;
1226 struct type *root;
1227 int index;
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);
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);
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);
1265 fprintf(hdr, "\n");
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");
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");
1281 if (ferror(out)) {
1282 perror(outputname);
1283 exit(1);
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);
1294 for (e = element_list; e; e = e->list_next)
1295 e->flags &= ~ELEMENT_RENDERED;
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);
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);
1309 fprintf(out, "};\n");
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");
1320 * Render the out-of-line elements
1322 static void render_out_of_line_list(FILE *out)
1324 struct element *e, *ce;
1325 const char *act;
1326 int entry;
1328 while ((e = render_list)) {
1329 render_list = e->render_next;
1330 if (!render_list)
1331 render_list_p = &render_list;
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--;
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;
1357 if (e->action)
1358 render_opcode(out, "_action(ACT_%s),\n",
1359 e->action->name);
1360 render_opcode(out, "ASN1_OP_RETURN,\n");
1365 * Render an element.
1367 static void render_element(FILE *out, struct element *e, struct element *tag)
1369 struct element *ec;
1370 const char *cond, *act;
1371 int entry, skippable = 0, outofline = 0;
1373 if (e->flags & ELEMENT_SKIPPABLE ||
1374 (tag && tag->flags & ELEMENT_SKIPPABLE))
1375 skippable = 1;
1377 if ((e->type_def && e->type_def->ref_count > 1) ||
1378 skippable)
1379 outofline = 1;
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);
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;
1401 case TAG_OVERRIDE:
1402 render_element(out, e->children, e);
1403 return;
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;
1415 case CHOICE:
1416 goto dont_render_tag;
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;
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");
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;
1451 dont_render_tag:
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;
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;
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);
1486 break;
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;
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);
1518 break;
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.
1527 fprintf(stderr, "The ASN.1 SET type is not currently supported.\n");
1528 exit(1);
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;
1539 default:
1540 break;
1543 if (e->action)
1544 render_opcode(out, "_action(ACT_%s),\n", e->action->name);