Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
asn1_compiler.c
Go to the documentation of this file.
1 /* Simplified ASN.1 notation parser
2  *
3  * Copyright (C) 2012 Red Hat, Inc. All Rights Reserved.
4  * Written by David Howells ([email protected])
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>
22 
23 enum token_type {
119 };
120 
121 static const unsigned char token_to_tag[NR__TOKENS] = {
122  /* EOC goes first */
133  [DIRECTIVE_EMBEDDED] = 0,
136  /* 14 */
137  /* 15 */
154 };
155 
156 static const char asn1_classes[4][5] = {
157  [ASN1_UNIV] = "UNIV",
158  [ASN1_APPL] = "APPL",
159  [ASN1_CONT] = "CONT",
160  [ASN1_PRIV] = "PRIV"
161 };
162 
163 static const char asn1_methods[2][5] = {
164  [ASN1_UNIV] = "PRIM",
165  [ASN1_APPL] = "CONS"
166 };
167 
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 */
201 };
202 
203 static const char *filename;
204 static const char *grammar_name;
205 static const char *outputname;
206 static const char *headername;
207 
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)
292 };
293 
294 struct action {
295  struct action *next;
296  unsigned char index;
297  char name[];
298 };
299 
300 static struct action *action_list;
301 static unsigned nr_actions;
302 
303 struct token {
304  unsigned short line;
306  unsigned char size;
307  struct action *action;
308  const char *value;
309  struct type *type;
310 };
311 
312 static struct token *token_list;
313 static unsigned nr_tokens;
314 
315 static 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  */
346 static 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 
532 static void build_type_list(void);
533 static void parse(void);
534 static void render(FILE *out, FILE *hdr);
535 
536 /*
537  *
538  */
539 int 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 
631 enum compound {
641 };
642 
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;
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 
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 
677 static struct type *type_list;
678 static struct type **type_index;
679 static unsigned nr_types;
680 
681 static 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 
692 static 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  */
708 static 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 
763 static struct element *parse_type(struct token **_cursor, struct token *stop,
764  struct token *name);
765 
766 /*
767  * Parse the token stream
768  */
769 static 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 
799 static struct element *element_list;
800 
801 static 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 
813 static struct element *parse_compound(struct token **_cursor, struct token *end,
814  int alternates);
815 
816 /*
817  * Parse one type definition statement
818  */
819 static 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;
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:
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:
940  case DIRECTIVE_IA5String:
944  case DIRECTIVE_T61String:
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 
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);
1112 
1113 overrun_error:
1114  fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1115  exit(1);
1116 }
1117 
1118 /*
1119  * Parse a compound type list
1120  */
1121 static 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 
1181 overrun_error:
1182  fprintf(stderr, "%s: Unexpectedly hit EOF\n", filename);
1183  exit(1);
1184 }
1185 
1186 static void render_element(FILE *out, struct element *e, struct element *tag);
1187 static void render_out_of_line_list(FILE *out);
1188 
1189 static int nr_entries;
1190 static int render_depth = 1;
1191 static struct element *render_list, **render_list_p = &render_list;
1192 
1194 static 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)))
1208 static 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  */
1222 static 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  */
1322 static 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  */
1367 static 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;
1451 dont_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 }