"Fossies" - the Fresh Open Source Software Archive

Member "libksba-1.6.0/src/asn1-func.c" (18 May 2021, 31230 Bytes) of package /linux/privat/libksba-1.6.0.tar.bz2:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "asn1-func.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 1.5.1_vs_1.6.0.

    1 /* asn1-func.c - Fucntions for the ASN.1 data structures.
    2  *      Copyright (C) 2000, 2001 Fabio Fiorina
    3  *      Copyright (C) 2001 Free Software Foundation, Inc.
    4  *      Copyright (C) 2002, 2003, 2006, 2007, 2010, 2012 g10 Code GmbH
    5  *
    6  * KSBA is free software; you can redistribute it and/or modify
    7  * it under the terms of either
    8  *
    9  *   - the GNU Lesser General Public License as published by the Free
   10  *     Software Foundation; either version 3 of the License, or (at
   11  *     your option) any later version.
   12  *
   13  * or
   14  *
   15  *   - the GNU General Public License as published by the Free
   16  *     Software Foundation; either version 2 of the License, or (at
   17  *     your option) any later version.
   18  *
   19  * or both in parallel, as here.
   20  *
   21  * KSBA is distributed in the hope that it will be useful, but WITHOUT
   22  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
   23  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
   24  * License for more details.
   25  *
   26  * You should have received a copies of the GNU General Public License
   27  * and the GNU Lesser General Public License along with this program;
   28  * if not, see <http://www.gnu.org/licenses/>.
   29  */
   30 
   31 #ifndef BUILD_GENTOOLS
   32 #include <config.h>
   33 #endif
   34 
   35 #include <stdio.h>
   36 #include <stdlib.h>
   37 #include <string.h>
   38 #include <ctype.h>
   39 #include <assert.h>
   40 
   41 #ifdef BUILD_GENTOOLS
   42 # include "gen-help.h"
   43 #else
   44 # include "util.h"
   45 # include "ksba.h"
   46 #endif
   47 
   48 #include "asn1-func.h"
   49 
   50 #ifdef BUILD_GENTOOLS
   51 #define gpgrt_log_debug(...)  /**/
   52 #endif
   53 
   54 
   55 static AsnNode resolve_identifier (AsnNode root, AsnNode node, int nestlevel);
   56 
   57 
   58 static AsnNode
   59 add_node (node_type_t type)
   60 {
   61   AsnNode punt;
   62 
   63   punt = xmalloc (sizeof *punt);
   64 
   65   punt->left = NULL;
   66   punt->name = NULL;
   67   punt->type = type;
   68   punt->valuetype = VALTYPE_NULL;
   69   punt->value.v_cstr = NULL;
   70   punt->off = -1;
   71   punt->nhdr = 0;
   72   punt->len = 0;
   73   punt->down = NULL;
   74   punt->right = NULL;
   75   punt->link_next = NULL;
   76   return punt;
   77 }
   78 
   79 AsnNode
   80 _ksba_asn_new_node (node_type_t type)
   81 {
   82   return add_node (type);
   83 }
   84 
   85 
   86 int
   87 _ksba_asn_is_primitive (node_type_t type)
   88 {
   89   switch (type)
   90     {
   91     case TYPE_BOOLEAN:
   92     case TYPE_INTEGER:
   93     case TYPE_BIT_STRING:
   94     case TYPE_OCTET_STRING:
   95     case TYPE_NULL:
   96     case TYPE_OBJECT_ID:
   97     case TYPE_OBJECT_DESCRIPTOR:
   98     case TYPE_REAL:
   99     case TYPE_ENUMERATED:
  100     case TYPE_UTF8_STRING:
  101     case TYPE_REALTIVE_OID:
  102     case TYPE_NUMERIC_STRING:
  103     case TYPE_PRINTABLE_STRING:
  104     case TYPE_TELETEX_STRING:
  105     case TYPE_VIDEOTEX_STRING:
  106     case TYPE_IA5_STRING:
  107     case TYPE_UTC_TIME:
  108     case TYPE_GENERALIZED_TIME:
  109     case TYPE_GRAPHIC_STRING:
  110     case TYPE_VISIBLE_STRING:
  111     case TYPE_GENERAL_STRING:
  112     case TYPE_UNIVERSAL_STRING:
  113     case TYPE_CHARACTER_STRING:
  114     case TYPE_BMP_STRING:
  115     case TYPE_PRE_SEQUENCE:
  116       return 1;
  117     default:
  118       return 0;
  119     }
  120 }
  121 
  122 
  123 /* Change the value field of the node to the content of buffer value
  124    of size LEN.  With VALUE of NULL or LEN of 0 the value field is
  125    deleted */
  126 void
  127 _ksba_asn_set_value (AsnNode node,
  128                      enum asn_value_type vtype, const void *value, size_t len)
  129 {
  130   return_if_fail (node);
  131 
  132   if (node->valuetype)
  133     {
  134       if (node->valuetype == VALTYPE_CSTR)
  135         xfree (node->value.v_cstr);
  136       else if (node->valuetype == VALTYPE_MEM)
  137         xfree (node->value.v_mem.buf);
  138       node->valuetype = 0;
  139     }
  140 
  141   switch (vtype)
  142     {
  143     case VALTYPE_NULL:
  144       break;
  145     case VALTYPE_BOOL:
  146       return_if_fail (len);
  147       node->value.v_bool = !!(const unsigned *)value;
  148       break;
  149     case VALTYPE_CSTR:
  150       node->value.v_cstr = xstrdup (value);
  151       break;
  152     case VALTYPE_MEM:
  153       node->value.v_mem.len = len;
  154       if (len)
  155         {
  156           node->value.v_mem.buf = xmalloc (len);
  157           memcpy (node->value.v_mem.buf, value, len);
  158         }
  159       else
  160           node->value.v_mem.buf = NULL;
  161       break;
  162     case VALTYPE_LONG:
  163       return_if_fail (sizeof (long) == len);
  164       node->value.v_long = *(long *)value;
  165       break;
  166 
  167     case VALTYPE_ULONG:
  168       return_if_fail (sizeof (unsigned long) == len);
  169       node->value.v_ulong = *(unsigned long *)value;
  170       break;
  171 
  172     default:
  173       return_if_fail (0);
  174     }
  175   node->valuetype = vtype;
  176 }
  177 
  178 static void
  179 copy_value (AsnNode d, const AsnNode s)
  180 {
  181   char helpbuf[1];
  182   const void *buf = NULL;
  183   size_t len = 0;
  184 
  185   return_if_fail (d != s);
  186 
  187   switch (s->valuetype)
  188     {
  189     case VALTYPE_NULL:
  190       break;
  191     case VALTYPE_BOOL:
  192       len = 1;
  193       helpbuf[0] = s->value.v_bool;
  194       buf = helpbuf;
  195       break;
  196     case VALTYPE_CSTR:
  197       buf = s->value.v_cstr;
  198       break;
  199     case VALTYPE_MEM:
  200       len = s->value.v_mem.len;
  201       buf = len? s->value.v_mem.buf : NULL;
  202       break;
  203     case VALTYPE_LONG:
  204       len = sizeof (long);
  205       buf = &s->value.v_long;
  206       break;
  207     case VALTYPE_ULONG:
  208       len = sizeof (unsigned long);
  209       buf = &s->value.v_ulong;
  210       break;
  211 
  212     default:
  213       return_if_fail (0);
  214     }
  215   _ksba_asn_set_value (d, s->valuetype, buf, len);
  216   d->off = s->off;
  217   d->nhdr = s->nhdr;
  218   d->len = s->len;
  219 }
  220 
  221 static AsnNode
  222 copy_node (const AsnNode s)
  223 {
  224   AsnNode d = add_node (s->type);
  225 
  226   if (s->name)
  227     d->name = xstrdup (s->name);
  228   d->flags = s->flags;
  229   copy_value (d, s);
  230   return d;
  231 }
  232 
  233 
  234 
  235 
  236 /* Change the name field of the node to NAME.
  237    NAME may be NULL */
  238 void
  239 _ksba_asn_set_name (AsnNode node, const char *name)
  240 {
  241   return_if_fail (node);
  242 
  243   if (node->name)
  244     {
  245       xfree (node->name);
  246       node->name = NULL;
  247     }
  248 
  249   if (name && *name)
  250       node->name = xstrdup (name);
  251 }
  252 
  253 
  254 static AsnNode
  255 set_right (AsnNode  node, AsnNode  right)
  256 {
  257   if (node == NULL)
  258     return node;
  259 
  260   node->right = right;
  261   if (right)
  262     right->left = node;
  263   return node;
  264 }
  265 
  266 
  267 static AsnNode
  268 set_down (AsnNode node, AsnNode down)
  269 {
  270   if (node == NULL)
  271     return node;
  272 
  273   node->down = down;
  274   if (down)
  275     down->left = node;
  276   return node;
  277 }
  278 
  279 
  280 void
  281 _ksba_asn_remove_node (AsnNode  node)
  282 {
  283   if (node == NULL)
  284     return;
  285 
  286   xfree (node->name);
  287   if (node->valuetype == VALTYPE_CSTR)
  288     xfree (node->value.v_cstr);
  289   else if (node->valuetype == VALTYPE_MEM)
  290     xfree (node->value.v_mem.buf);
  291   xfree (node);
  292 }
  293 
  294 
  295 /* find the node with the given name.  A name part of "?LAST" matches
  296    the last element of a SET_OF.  A "+" matches the CHOICE with values
  297    set. */
  298 static AsnNode
  299 find_node (AsnNode root, const char *name, int resolve)
  300 {
  301   AsnNode p;
  302   const char *s;
  303   char buf[129];
  304   int i;
  305 
  306   if (!name || !name[0])
  307     return NULL;
  308 
  309   /* gpgrt_log_debug ("%s: looking for '%s'\n", __func__, name); */
  310   /* find the first part */
  311   s = name;
  312   for (i=0; *s && *s != '.' && i < DIM(buf)-1; s++)
  313     buf[i++] = *s;
  314   buf[i] = 0;
  315   return_null_if_fail (i < DIM(buf)-1);
  316 
  317   for (p = root; p && (!p->name || strcmp (p->name, buf)); p = p->right)
  318     ;
  319 
  320   /* find other parts */
  321   while (p && *s)
  322     {
  323       assert (*s == '.');
  324       s++; /* skip the dot */
  325 
  326       if (!p->down)
  327     return NULL; /* not found */
  328       p = p->down;
  329 
  330       for (i=0; *s && *s != '.' && i < DIM(buf)-1; s++)
  331         buf[i++] = *s;
  332       buf[i] = 0;
  333       return_null_if_fail (i < DIM(buf)-1);
  334 
  335       if (!*buf)
  336         {
  337          /* a double dot can be used to get over an unnamed sequence
  338             in a set - Actually a hack to workaround a bug.  We should
  339             rethink the entire node naming issue */
  340           /* gpgrt_log_debug ("%s: .. to '%s'\n", __func__, p?p->name:""); */
  341         }
  342       else if (!strcmp (buf, "?LAST"))
  343     {
  344       if (!p)
  345         return NULL;
  346       while (p->right)
  347         p = p->right;
  348     }
  349       else if (*buf == '+' && !buf[1])
  350         {
  351           for (; p ; p = p->right)
  352             if (p->off != -1)
  353               break;
  354           /* gpgrt_log_debug ("%s: + to '%s'\n", __func__, p?p->name:""); */
  355         }
  356       else
  357     {
  358           for (; p ; p = p->right)
  359             {
  360               /* gpgrt_log_debug ("%s: '%s' to '%s'\n", */
  361               /*                  __func__, buf, p?p->name:""); */
  362               if (p->name && !strcmp (p->name, buf))
  363                 break;
  364               if (resolve && p->name && p->type == TYPE_IDENTIFIER)
  365                 {
  366                   AsnNode p2;
  367 
  368                   p2 = resolve_identifier (root, p, 0);
  369                   if (p2 && p2->name && !strcmp (p2->name, buf))
  370                     break;
  371                 }
  372             }
  373 
  374           if (resolve && p && p->type == TYPE_IDENTIFIER)
  375             p = resolve_identifier (root, p, 0);
  376     }
  377     }
  378 
  379   return p;
  380 }
  381 
  382 AsnNode
  383 _ksba_asn_find_node (AsnNode root, const char *name)
  384 {
  385   return find_node (root, name, 0);
  386 }
  387 
  388 
  389 static AsnNode
  390 _asn1_find_left (AsnNode  node)
  391 {
  392   if ((node == NULL) || (node->left == NULL) || (node->left->down == node))
  393     return NULL;
  394 
  395   return node->left;
  396 }
  397 
  398 
  399 static AsnNode
  400 find_up (AsnNode  node)
  401 {
  402   AsnNode p;
  403 
  404   if (node == NULL)
  405     return NULL;
  406 
  407   p = node;
  408   while ((p->left != NULL) && (p->left->right == p))
  409     p = p->left;
  410 
  411   return p->left;
  412 }
  413 
  414 
  415 
  416 static void
  417 print_value (AsnNode node, FILE *fp)
  418 {
  419   if (!node->valuetype)
  420     return;
  421   fprintf (fp, " vt=%d val=", node->valuetype);
  422   switch (node->valuetype)
  423     {
  424     case VALTYPE_BOOL:
  425       fputs (node->value.v_bool? "True":"False", fp);
  426       break;
  427     case VALTYPE_CSTR:
  428       fputs (node->value.v_cstr, fp);
  429       break;
  430     case VALTYPE_MEM:
  431       {
  432         size_t n;
  433         unsigned char *p;
  434         for (p=node->value.v_mem.buf, n=node->value.v_mem.len; n; n--, p++)
  435           fprintf (fp, "%02X", *p);
  436       }
  437       break;
  438     case VALTYPE_LONG:
  439       fprintf (fp, "%ld", node->value.v_long);
  440       break;
  441     case VALTYPE_ULONG:
  442       fprintf (fp, "%lu", node->value.v_ulong);
  443       break;
  444     default:
  445       return_if_fail (0);
  446     }
  447 }
  448 
  449 void
  450 _ksba_asn_node_dump (AsnNode p, FILE *fp)
  451 {
  452   const char *typestr;
  453 
  454   switch (p->type)
  455     {
  456     case TYPE_NULL:     typestr = "NULL"; break;
  457     case TYPE_CONSTANT:     typestr = "CONST"; break;
  458     case TYPE_IDENTIFIER:   typestr = "IDENTIFIER"; break;
  459     case TYPE_INTEGER:      typestr = "INTEGER"; break;
  460     case TYPE_ENUMERATED:   typestr = "ENUMERATED"; break;
  461     case TYPE_UTC_TIME:     typestr = "UTCTIME"; break;
  462     case TYPE_GENERALIZED_TIME: typestr = "GENERALIZEDTIME"; break;
  463     case TYPE_BOOLEAN:      typestr = "BOOLEAN"; break;
  464     case TYPE_SEQUENCE:     typestr = "SEQUENCE"; break;
  465     case TYPE_PRE_SEQUENCE: typestr = "PRE_SEQUENCE"; break;
  466     case TYPE_BIT_STRING:   typestr = "BIT_STR"; break;
  467     case TYPE_OCTET_STRING: typestr = "OCT_STR"; break;
  468     case TYPE_TAG:      typestr = "TAG"; break;
  469     case TYPE_DEFAULT:      typestr = "DEFAULT"; break;
  470     case TYPE_SIZE:     typestr = "SIZE"; break;
  471     case TYPE_SEQUENCE_OF:  typestr = "SEQ_OF"; break;
  472     case TYPE_OBJECT_ID:    typestr = "OBJ_ID"; break;
  473     case TYPE_ANY:      typestr = "ANY"; break;
  474     case TYPE_SET:          typestr = "SET"; break;
  475     case TYPE_SET_OF:       typestr = "SET_OF"; break;
  476     case TYPE_CHOICE:       typestr = "CHOICE"; break;
  477     case TYPE_DEFINITIONS:  typestr = "DEFINITIONS"; break;
  478     case TYPE_UTF8_STRING:       typestr = "UTF8_STRING"; break;
  479     case TYPE_NUMERIC_STRING:    typestr = "NUMERIC_STRING"; break;
  480     case TYPE_PRINTABLE_STRING:  typestr = "PRINTABLE_STRING"; break;
  481     case TYPE_TELETEX_STRING:    typestr = "TELETEX_STRING"; break;
  482     case TYPE_IA5_STRING:        typestr = "IA5_STRING"; break;
  483     default:                typestr = "ERROR\n"; break;
  484     }
  485 
  486   fprintf (fp, "%s", typestr);
  487   if (p->name)
  488     fprintf (fp, " `%s'", p->name);
  489   print_value (p, fp);
  490   fputs ("  ", fp);
  491   switch (p->flags.class)
  492     {
  493     case CLASS_UNIVERSAL:   fputs ("U", fp); break;
  494     case CLASS_PRIVATE:     fputs ("P", fp); break;
  495     case CLASS_APPLICATION: fputs ("A", fp); break;
  496     case CLASS_CONTEXT:     fputs ("C", fp); break;
  497     }
  498 
  499   if (p->flags.explicit)
  500     fputs (",explicit", fp);
  501   if (p->flags.implicit)
  502     fputs (",implicit", fp);
  503   if (p->flags.is_implicit)
  504     fputs (",is_implicit", fp);
  505   if (p->flags.has_tag)
  506     fputs (",tag", fp);
  507   if (p->flags.has_default)
  508     fputs (",default", fp);
  509   if (p->flags.is_true)
  510     fputs (",true", fp);
  511   if (p->flags.is_false)
  512     fputs (",false", fp);
  513   if (p->flags.has_list)
  514     fputs (",list", fp);
  515   if (p->flags.has_min_max)
  516     fputs (",min_max", fp);
  517   if (p->flags.is_optional)
  518     fputs (",optional", fp);
  519   if (p->flags.one_param)
  520     fputs (",1_param", fp);
  521   if (p->flags.has_size)
  522     fputs (",size", fp);
  523   if (p->flags.has_defined_by)
  524     fputs (",def_by", fp);
  525   if (p->flags.has_imports)
  526     fputs (",imports", fp);
  527   if (p->flags.assignment)
  528     fputs (",assign",fp);
  529   if (p->flags.in_set)
  530     fputs (",in_set",fp);
  531   if (p->flags.in_choice)
  532     fputs (",in_choice",fp);
  533   if (p->flags.in_array)
  534     fputs (",in_array",fp);
  535   if (p->flags.not_used)
  536     fputs (",not_used",fp);
  537   if (p->flags.skip_this)
  538     fputs (",[skip]",fp);
  539   if (p->flags.is_any)
  540     fputs (",is_any",fp);
  541   if (p->off != -1 )
  542     fprintf (fp, " %d.%d.%d", p->off, p->nhdr, p->len );
  543 
  544 }
  545 
  546 void
  547 _ksba_asn_node_dump_all (AsnNode root, FILE *fp)
  548 {
  549   AsnNode p = root;
  550   int indent = 0;
  551 
  552   while (p)
  553     {
  554       fprintf (fp, "%*s", indent, "");
  555       _ksba_asn_node_dump (p, fp);
  556       putc ('\n', fp);
  557 
  558       if (p->down)
  559     {
  560       p = p->down;
  561       indent += 2;
  562     }
  563       else if (p == root)
  564     {
  565       p = NULL;
  566       break;
  567     }
  568       else if (p->right)
  569     p = p->right;
  570       else
  571     {
  572       while (1)
  573         {
  574           p = find_up (p);
  575           if (p == root)
  576         {
  577           p = NULL;
  578           break;
  579         }
  580           indent -= 2;
  581           if (p->right)
  582         {
  583           p = p->right;
  584           break;
  585         }
  586         }
  587     }
  588     }
  589 }
  590 
  591 /**
  592  * ksba_asn_tree_dump:
  593  * @tree: A Parse Tree
  594  * @name: Name of the element or NULL
  595  * @fp: dump to this stream
  596  *
  597  * If the first character of the name is a '<' the expanded version of
  598  * the tree will be printed.
  599  *
  600  * This function is a debugging aid.
  601  **/
  602 void
  603 ksba_asn_tree_dump (ksba_asn_tree_t tree, const char *name, FILE *fp)
  604 {
  605   AsnNode p, root;
  606   int k, expand=0, indent = 0;
  607 
  608   if (!tree || !tree->parse_tree)
  609     return;
  610 
  611   if ( name && *name== '<')
  612     {
  613       expand = 1;
  614       name++;
  615       if (!*name)
  616         name = NULL;
  617     }
  618 
  619   root = name? _ksba_asn_find_node (tree->parse_tree, name) : tree->parse_tree;
  620   if (!root)
  621     return;
  622 
  623   if (expand)
  624     root = _ksba_asn_expand_tree (root, NULL);
  625 
  626   p = root;
  627   while (p)
  628     {
  629       for (k = 0; k < indent; k++)
  630     fprintf (fp, " ");
  631       _ksba_asn_node_dump (p, fp);
  632       putc ('\n', fp);
  633 
  634       if (p->down)
  635     {
  636       p = p->down;
  637       indent += 2;
  638     }
  639       else if (p == root)
  640     {
  641       p = NULL;
  642       break;
  643     }
  644       else if (p->right)
  645     p = p->right;
  646       else
  647     {
  648       while (1)
  649         {
  650           p = find_up (p);
  651           if (p == root)
  652         {
  653           p = NULL;
  654           break;
  655         }
  656           indent -= 2;
  657           if (p->right)
  658         {
  659           p = p->right;
  660           break;
  661         }
  662         }
  663     }
  664     }
  665 
  666   if (expand)
  667     _ksba_asn_release_nodes (root);
  668 }
  669 
  670 int
  671 _ksba_asn_delete_structure (AsnNode root)
  672 {
  673   AsnNode p, p2, p3;
  674 
  675   if (root == NULL)
  676     return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
  677 
  678   p = root;
  679   while (p)
  680     {
  681       if (p->down)
  682     {
  683       p = p->down;
  684     }
  685       else
  686     {           /* no down */
  687       p2 = p->right;
  688       if (p != root)
  689         {
  690           p3 = find_up (p);
  691           set_down (p3, p2);
  692           _ksba_asn_remove_node (p);
  693           p = p3;
  694         }
  695       else
  696         {           /* p==root */
  697           p3 = _asn1_find_left (p);
  698           if (!p3)
  699         {
  700           p3 = find_up (p);
  701           if (p3)
  702             set_down (p3, p2);
  703           else
  704             {
  705               if (p->right)
  706             p->right->left = NULL;
  707             }
  708         }
  709           else
  710         set_right (p3, p2);
  711           _ksba_asn_remove_node (p);
  712           p = NULL;
  713         }
  714     }
  715     }
  716   return 0;
  717 }
  718 
  719 
  720 /* check that all identifiers referenced in the tree are available */
  721 int
  722 _ksba_asn_check_identifier (AsnNode node)
  723 {
  724   AsnNode p, p2;
  725   char name2[129];
  726 
  727   if (!node)
  728     return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
  729 
  730   for (p = node; p; p = _ksba_asn_walk_tree (node, p))
  731     {
  732       if (p->type == TYPE_IDENTIFIER && p->valuetype == VALTYPE_CSTR)
  733     {
  734           if (strlen (node->name)+strlen(p->value.v_cstr)+2 > DIM(name2))
  735             return gpg_error (GPG_ERR_BUG); /* well identifier too long */
  736           strcpy (name2, node->name);
  737           strcat (name2, ".");
  738       strcat (name2, p->value.v_cstr);
  739       p2 = _ksba_asn_find_node (node, name2);
  740       if (!p2)
  741         {
  742           fprintf (stderr,"reference to `%s' not found\n", name2);
  743           return gpg_error (GPG_ERR_IDENTIFIER_NOT_FOUND);
  744         }
  745 /*            fprintf (stdout,"found reference for `%s' (", name2); */
  746 /*            print_node (p2, stdout); */
  747 /*            fputs (")\n", stdout); */
  748     }
  749       else if (p->type == TYPE_OBJECT_ID && p->flags.assignment)
  750     { /* an object ID in an assignment */
  751       p2 = p->down;
  752       if (p2 && (p2->type == TYPE_CONSTANT))
  753             {
  754           if (p2->valuetype == VALTYPE_CSTR && !isdigit (p2->value.v_cstr[0]))
  755         { /* the first constand below is a reference */
  756                   if (strlen (node->name)
  757                       +strlen(p->value.v_cstr)+2 > DIM(name2))
  758                     return gpg_error (GPG_ERR_BUG); /* well identifier too long */
  759                   strcpy (name2, node->name);
  760                   strcat (name2, ".");
  761           strcat (name2, p2->value.v_cstr);
  762           p2 = _ksba_asn_find_node (node, name2);
  763           if (!p2)
  764                     {
  765                       fprintf (stderr,"object id reference `%s' not found\n",
  766                                name2);
  767                       return gpg_error (GPG_ERR_IDENTIFIER_NOT_FOUND);
  768                     }
  769                   else if ( p2->type != TYPE_OBJECT_ID
  770                             || !p2->flags.assignment )
  771             {
  772               fprintf (stderr,"`%s' is not an object id\n", name2);
  773               return gpg_error (GPG_ERR_IDENTIFIER_NOT_FOUND);
  774             }
  775 /*                    fprintf (stdout,"found objid reference for `%s' (", name2); */
  776 /*                    print_node (p2, stdout); */
  777 /*                    fputs (")\n", stdout); */
  778         }
  779         }
  780     }
  781     }
  782 
  783   return 0;
  784 }
  785 
  786 
  787 /* Get the next node until root is reached in which case NULL is
  788    returned */
  789 AsnNode
  790 _ksba_asn_walk_tree (AsnNode root, AsnNode node)
  791 {
  792   if (!node)
  793     ;
  794   else if (node->down)
  795     node = node->down;
  796   else
  797     {
  798       if (node == root)
  799         node = NULL;
  800       else if (node->right)
  801         node = node->right;
  802       else
  803         {
  804           for (;;)
  805             {
  806               node = find_up (node);
  807               if (node == root)
  808                 {
  809                   node = NULL;
  810                   break;
  811                 }
  812               if (node->right)
  813                 {
  814                   node = node->right;
  815                   break;
  816                 }
  817             }
  818         }
  819     }
  820 
  821   return node;
  822 }
  823 
  824 AsnNode
  825 _ksba_asn_walk_tree_up_right (AsnNode root, AsnNode node)
  826 {
  827   if (node)
  828     {
  829       if (node == root)
  830         node = NULL;
  831       else
  832         {
  833           for (;;)
  834             {
  835               node = find_up (node);
  836               if (node == root)
  837                 {
  838                   node = NULL;
  839                   break;
  840                 }
  841               if (node->right)
  842                 {
  843                   node = node->right;
  844                   break;
  845                 }
  846             }
  847         }
  848     }
  849 
  850   return node;
  851 }
  852 
  853 /* walk over the tree and change the value type of all integer types
  854    from string to long. */
  855 int
  856 _ksba_asn_change_integer_value (AsnNode node)
  857 {
  858   AsnNode p;
  859 
  860   if (node == NULL)
  861     return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
  862 
  863   for (p = node; p; p = _ksba_asn_walk_tree (node, p))
  864     {
  865       if (p->type == TYPE_INTEGER && p->flags.assignment)
  866     {
  867       if (p->valuetype == VALTYPE_CSTR)
  868         {
  869               long val = strtol (p->value.v_cstr, NULL, 10);
  870           _ksba_asn_set_value (p, VALTYPE_LONG, &val, sizeof(val));
  871         }
  872     }
  873     }
  874 
  875   return 0;
  876 }
  877 
  878 
  879 
  880 /* Expand all object ID constants */
  881 int
  882 _ksba_asn_expand_object_id (AsnNode node)
  883 {
  884   AsnNode p, p2, p3, p4, p5;
  885   char name_root[129], name2[129*2+1] = "";
  886 
  887   /* Fixme: Make a cleaner implementation */
  888   if (!node)
  889     return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
  890   if (!node->name)
  891     return gpg_error (GPG_ERR_INV_VALUE);
  892   if (strlen(node->name) >= DIM(name_root)-1)
  893     return gpg_error (GPG_ERR_GENERAL);
  894   strcpy (name_root, node->name);
  895 
  896  restart:
  897   for (p = node; p; p = _ksba_asn_walk_tree (node, p))
  898     {
  899       if (p->type == TYPE_OBJECT_ID && p->flags.assignment)
  900         {
  901           p2 = p->down;
  902           if (p2 && p2->type == TYPE_CONSTANT)
  903             {
  904               if (p2->valuetype == VALTYPE_CSTR
  905                   && !isdigit (p2->value.v_cstr[0]))
  906                 {
  907                   if (strlen(p2->value.v_cstr)+1+strlen(name2) >= DIM(name2)-1)
  908                     return gpg_error (GPG_ERR_GENERAL);
  909                   strcpy (name2, name_root);
  910                   strcat (name2, ".");
  911                   strcat (name2, p2->value.v_cstr);
  912                   p3 = _ksba_asn_find_node (node, name2);
  913                   if (!p3 || p3->type != TYPE_OBJECT_ID ||
  914                       !p3->flags.assignment)
  915                     return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
  916                   set_down (p, p2->right);
  917                   _ksba_asn_remove_node (p2);
  918                   p2 = p;
  919                   p4 = p3->down;
  920                   while (p4)
  921                     {
  922                       if (p4->type == TYPE_CONSTANT)
  923                         {
  924                           p5 = add_node (TYPE_CONSTANT);
  925                           _ksba_asn_set_name (p5, p4->name);
  926                           _ksba_asn_set_value (p5, VALTYPE_CSTR,
  927                                                p4->value.v_cstr, 0);
  928                           if (p2 == p)
  929                             {
  930                               set_right (p5, p->down);
  931                               set_down (p, p5);
  932                             }
  933                           else
  934                             {
  935                               set_right (p5, p2->right);
  936                               set_right (p2, p5);
  937                             }
  938                           p2 = p5;
  939                         }
  940                       p4 = p4->right;
  941                     }
  942                   goto restart;  /* the most simple way to get it right ;-) */
  943                 }
  944             }
  945         }
  946     }
  947   return 0;
  948 }
  949 
  950 /* Walk the parse tree and set the default tag where appropriate.  The
  951    node must be of type DEFINITIONS */
  952 void
  953 _ksba_asn_set_default_tag (AsnNode node)
  954 {
  955   AsnNode p;
  956 
  957   return_if_fail (node && node->type == TYPE_DEFINITIONS);
  958 
  959   for (p = node; p; p = _ksba_asn_walk_tree (node, p))
  960     {
  961       if ( p->type == TYPE_TAG
  962            && !p->flags.explicit && !p->flags.implicit)
  963     {
  964       if (node->flags.explicit)
  965         p->flags.explicit = 1;
  966       else
  967         p->flags.implicit = 1;
  968     }
  969     }
  970   /* now mark the nodes which are implicit */
  971   for (p = node; p; p = _ksba_asn_walk_tree (node, p))
  972     {
  973       if ( p->type == TYPE_TAG && p->flags.implicit && p->down)
  974     {
  975       if (p->down->type == TYPE_CHOICE)
  976             ; /* a CHOICE is per se implicit */
  977       else if (p->down->type != TYPE_TAG)
  978         p->down->flags.is_implicit = 1;
  979     }
  980     }
  981 }
  982 
  983 /* Walk the tree and set the is_set and not_used flags for all nodes below
  984    a node of type SET. */
  985 void
  986 _ksba_asn_type_set_config (AsnNode node)
  987 {
  988   AsnNode p, p2;
  989 
  990   return_if_fail (node && node->type == TYPE_DEFINITIONS);
  991 
  992   for (p = node; p; p = _ksba_asn_walk_tree (node, p))
  993     {
  994       if (p->type == TYPE_SET)
  995         {
  996           for (p2 = p->down; p2; p2 = p2->right)
  997             {
  998               if (p2->type != TYPE_TAG)
  999                 {
 1000                   p2->flags.in_set = 1;
 1001                   p2->flags.not_used = 1;
 1002                 }
 1003             }
 1004         }
 1005       else if (p->type == TYPE_CHOICE)
 1006         {
 1007           for (p2 = p->down; p2; p2 = p2->right)
 1008             {
 1009                 p2->flags.in_choice = 1;
 1010             }
 1011         }
 1012       else if (p->type == TYPE_SEQUENCE_OF || p->type == TYPE_SET_OF)
 1013         {
 1014           for (p2 = p->down; p2; p2 = p2->right)
 1015             p2->flags.in_array = 1;
 1016         }
 1017       else if (p->type == TYPE_ANY)
 1018         { /* Help the DER encoder to track ANY tags */
 1019           p->flags.is_any = 1;
 1020         }
 1021     }
 1022 }
 1023 
 1024 /* Create a copy the tree at SRC_ROOT. s is a helper which should be
 1025    set to SRC_ROOT by the caller */
 1026 static AsnNode
 1027 copy_tree (AsnNode src_root, AsnNode s)
 1028 {
 1029   AsnNode first=NULL, dprev=NULL, d, down, tmp;
 1030   AsnNode *link_nextp = NULL;
 1031 
 1032   for (; s; s=s->right )
 1033     {
 1034       down = s->down;
 1035       d = copy_node (s);
 1036       if (link_nextp)
 1037     *link_nextp = d;
 1038       link_nextp = &d->link_next;
 1039 
 1040       if (!first)
 1041         first = d;
 1042       else
 1043         {
 1044           dprev->right = d;
 1045           d->left = dprev;
 1046         }
 1047       dprev = d;
 1048       if (down)
 1049         {
 1050           tmp = copy_tree (src_root, down);
 1051       if (tmp)
 1052         {
 1053           if (link_nextp)
 1054         *link_nextp = tmp;
 1055           link_nextp = &tmp->link_next;
 1056           while (*link_nextp)
 1057         link_nextp = &(*link_nextp)->link_next;
 1058         }
 1059 
 1060           if (d->down && tmp)
 1061             { /* Need to merge it with the existing down */
 1062               AsnNode x;
 1063 
 1064               for (x=d->down; x->right; x = x->right)
 1065                 ;
 1066               x->right = tmp;
 1067               tmp->left = x;
 1068             }
 1069           else
 1070             {
 1071               d->down = tmp;
 1072               if (d->down)
 1073                 d->down->left = d;
 1074             }
 1075         }
 1076     }
 1077   return first;
 1078 }
 1079 
 1080 
 1081 
 1082 static AsnNode
 1083 resolve_identifier (AsnNode root, AsnNode node, int nestlevel)
 1084 {
 1085   char buf_space[50];
 1086   char *buf;
 1087   AsnNode n;
 1088   size_t bufsize;
 1089 
 1090   if (nestlevel > 20)
 1091     return NULL;
 1092 
 1093   return_null_if_fail (root);
 1094   return_null_if_fail (node->valuetype == VALTYPE_CSTR);
 1095 
 1096   bufsize = strlen (root->name) + strlen (node->value.v_cstr) + 2;
 1097   if (bufsize <= sizeof buf_space)
 1098     buf = buf_space;
 1099   else
 1100     {
 1101       buf = xtrymalloc (bufsize);
 1102       return_null_if_fail (buf);
 1103     }
 1104   strcpy (stpcpy (stpcpy (buf, root->name), "."), node->value.v_cstr);
 1105   n = _ksba_asn_find_node (root, buf);
 1106 
 1107   /* We do just a simple indirection. */
 1108   if (n && n->type == TYPE_IDENTIFIER)
 1109     n = resolve_identifier (root, n, nestlevel+1);
 1110 
 1111   if (buf != buf_space)
 1112     xfree (buf);
 1113 
 1114   return n;
 1115 }
 1116 
 1117 
 1118 static AsnNode
 1119 do_expand_tree (AsnNode src_root, AsnNode s, int depth)
 1120 {
 1121   AsnNode first=NULL, dprev=NULL, d, down, tmp;
 1122   AsnNode *link_nextp = NULL;
 1123 
 1124   /* On the very first level we do not follow the right pointer so that
 1125      we can break out a valid subtree. */
 1126   for (; s; s=depth?s->right:NULL )
 1127     {
 1128       if (s->type == TYPE_SIZE)
 1129         continue; /* this node gets in the way all the time.  It
 1130                      should be an attribute to a node */
 1131 
 1132       down = s->down;
 1133       if (s->type == TYPE_IDENTIFIER)
 1134         {
 1135           AsnNode s2, *dp;
 1136 
 1137           d = resolve_identifier (src_root, s, 0);
 1138           if (!d)
 1139             {
 1140               fprintf (stderr, "RESOLVING IDENTIFIER FAILED\n");
 1141               continue;
 1142             }
 1143           down = d->down;
 1144           d = copy_node (d);
 1145       if (link_nextp)
 1146         *link_nextp = d;
 1147       link_nextp = &d->link_next;
 1148           if (s->flags.is_optional)
 1149             d->flags.is_optional = 1;
 1150           if (s->flags.in_choice)
 1151             d->flags.in_choice = 1;
 1152           if (s->flags.in_array)
 1153             d->flags.in_array = 1;
 1154           if (s->flags.is_implicit)
 1155             d->flags.is_implicit = 1;
 1156           if (s->flags.is_any)
 1157             d->flags.is_any = 1;
 1158           /* we don't want the resolved name - change it back */
 1159           _ksba_asn_set_name (d, s->name);
 1160           /* copy the default and tag attributes */
 1161           tmp = NULL;
 1162           dp = &tmp;
 1163           for (s2=s->down; s2; s2=s2->right)
 1164             {
 1165               AsnNode x;
 1166 
 1167               x = copy_node (s2);
 1168           if (link_nextp)
 1169         *link_nextp = x;
 1170           link_nextp = &x->link_next;
 1171               x->left = *dp? *dp : d;
 1172               *dp = x;
 1173               dp = &(*dp)->right;
 1174 
 1175               if (x->type == TYPE_TAG)
 1176                 d->flags.has_tag =1;
 1177               else if (x->type == TYPE_DEFAULT)
 1178                 d->flags.has_default =1;
 1179             }
 1180           d->down = tmp;
 1181         }
 1182       else
 1183         {
 1184       d = copy_node (s);
 1185       if (link_nextp)
 1186         *link_nextp = d;
 1187       link_nextp = &d->link_next;
 1188     }
 1189 
 1190       if (!first)
 1191         first = d;
 1192       else
 1193         {
 1194           dprev->right = d;
 1195           d->left = dprev;
 1196         }
 1197       dprev = d;
 1198       if (down)
 1199         {
 1200           if (depth >= 1000)
 1201             {
 1202               fprintf (stderr, "ASN.1 TREE TOO TALL!\n");
 1203               tmp = NULL;
 1204             }
 1205           else
 1206             {
 1207           tmp = do_expand_tree (src_root, down, depth+1);
 1208           if (tmp)
 1209         {
 1210           if (link_nextp)
 1211             *link_nextp = tmp;
 1212           link_nextp = &tmp->link_next;
 1213           while (*link_nextp)
 1214             link_nextp = &(*link_nextp)->link_next;
 1215         }
 1216         }
 1217           if (d->down && tmp)
 1218             { /* Need to merge it with the existing down */
 1219               AsnNode x;
 1220 
 1221               for (x=d->down; x->right; x = x->right)
 1222                 ;
 1223               x->right = tmp;
 1224               tmp->left = x;
 1225             }
 1226           else
 1227             {
 1228               d->down = tmp;
 1229               if (d->down)
 1230                 d->down->left = d;
 1231             }
 1232         }
 1233     }
 1234 
 1235   return first;
 1236 }
 1237 
 1238 
 1239 /* Expand the syntax tree so that all references are resolved and we
 1240    are able to store values right in the tree (except for set/sequence
 1241    of).  This expanded tree is also an requirement for doing the DER
 1242    decoding as the resolving of identifiers leads to a lot of
 1243    problems.  We use more memory of course, but this is negligible
 1244    because the entire code will be simpler and faster */
 1245 AsnNode
 1246 _ksba_asn_expand_tree (AsnNode parse_tree, const char *name)
 1247 {
 1248   AsnNode root;
 1249 
 1250   root = name? find_node (parse_tree, name, 1) : parse_tree;
 1251   return do_expand_tree (parse_tree, root, 0);
 1252 }
 1253 
 1254 
 1255 /* Insert a copy of the entire tree at NODE as the sibling of itself
 1256    and return the copy */
 1257 AsnNode
 1258 _ksba_asn_insert_copy (AsnNode node)
 1259 {
 1260   AsnNode n;
 1261   AsnNode *link_nextp;
 1262 
 1263   n = copy_tree (node, node);
 1264   if (!n)
 1265     return NULL; /* out of core */
 1266   return_null_if_fail (n->right == node->right);
 1267   node->right = n;
 1268   n->left = node;
 1269 
 1270   /* FIXME: Consider tail pointer for faster insertion.  */
 1271   link_nextp = &node->link_next;
 1272   while (*link_nextp)
 1273     link_nextp = &(*link_nextp)->link_next;
 1274   *link_nextp = n;
 1275 
 1276   return n;
 1277 }
 1278 
 1279 
 1280 /* Locate a type value sequence like
 1281 
 1282   SEQUENCE {
 1283      type    OBJECT IDENTIFIER
 1284      value   ANY
 1285   }
 1286 
 1287   below root and return the 'value' node.  OIDBUF should contain the
 1288   DER encoding of an OID value.  idx is the number of OIDs to skip;
 1289   this can be used to enumerate structures with the same OID */
 1290 AsnNode
 1291 _ksba_asn_find_type_value (const unsigned char *image, AsnNode root, int idx,
 1292                            const void *oidbuf, size_t oidlen)
 1293 {
 1294   AsnNode n, noid;
 1295 
 1296   if (!image || !root)
 1297     return NULL;
 1298 
 1299   for (n = root; n; n = _ksba_asn_walk_tree (root, n) )
 1300     {
 1301       if ( n->type == TYPE_SEQUENCE
 1302            && n->down && n->down->type == TYPE_OBJECT_ID)
 1303         {
 1304           noid = n->down;
 1305           if (noid->off != -1 && noid->len == oidlen
 1306               && !memcmp (image + noid->off + noid->nhdr, oidbuf, oidlen)
 1307               && noid->right)
 1308             {
 1309               if ( !idx-- )
 1310                 return noid->right;
 1311             }
 1312 
 1313         }
 1314     }
 1315   return NULL;
 1316 }