src/asn1-func.c

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