src/asn1-func.c - master - githubmirror/libksba

src/asn1-func.c
1 319 строк31 KB
Werner Koch
New function ksba_cms_add_attribute.
06 май 2026, 16:57
06 май 2026, 16:574cccd02
/* asn1-func.c - Fucntions for the ASN.1 data structures.
 *      Copyright (C) 2000, 2001 Fabio Fiorina
 *      Copyright (C) 2001 Free Software Foundation, Inc.
 *      Copyright (C) 2002, 2003, 2006, 2007, 2010, 2012 g10 Code GmbH
 *
 * KSBA is free software; you can redistribute it and/or modify
 * it under the terms of either
 *
 *   - the GNU Lesser General Public License as published by the Free
 *     Software Foundation; either version 3 of the License, or (at
 *     your option) any later version.
 *
 * or
 *
 *   - the GNU General Public License as published by the Free
 *     Software Foundation; either version 2 of the License, or (at
 *     your option) any later version.
 *
 * or both in parallel, as here.
 *
 * KSBA is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
 * License for more details.
 *
 * You should have received a copies of the GNU General Public License
 * and the GNU Lesser General Public License along with this program;
 * if not, see <http://www.gnu.org/licenses/>.
 */

#ifndef BUILD_GENTOOLS
#include <config.h>
#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

#ifdef BUILD_GENTOOLS
# include "gen-help.h"
#else
# include "util.h"
# include "ksba.h"
#endif

#include "asn1-func.h"

#ifdef BUILD_GENTOOLS
#define gpgrt_log_debug(...)  /**/
#endif


static AsnNode resolve_identifier (AsnNode root, AsnNode node, int nestlevel);


static AsnNode
add_node (node_type_t type)
{
  AsnNode punt;

  punt = xmalloc (sizeof *punt);

  punt->left = NULL;
  punt->name = NULL;
  punt->type = type;
  punt->valuetype = VALTYPE_NULL;
  punt->value.v_cstr = NULL;
  punt->off = -1;
  punt->nhdr = 0;
  punt->len = 0;
  punt->down = NULL;
  punt->right = NULL;
  punt->link_next = NULL;
  return punt;
}

AsnNode
_ksba_asn_new_node (node_type_t type)
{
  return add_node (type);
}


int
_ksba_asn_is_primitive (node_type_t type)
{
  switch (type)
    {
    case TYPE_BOOLEAN:
    case TYPE_INTEGER:
    case TYPE_BIT_STRING:
    case TYPE_OCTET_STRING:
    case TYPE_NULL:
    case TYPE_OBJECT_ID:
    case TYPE_OBJECT_DESCRIPTOR:
    case TYPE_REAL:
    case TYPE_ENUMERATED:
    case TYPE_UTF8_STRING:
    case TYPE_REALTIVE_OID:
    case TYPE_NUMERIC_STRING:
    case TYPE_PRINTABLE_STRING:
    case TYPE_TELETEX_STRING:
    case TYPE_VIDEOTEX_STRING:
    case TYPE_IA5_STRING:
    case TYPE_UTC_TIME:
    case TYPE_GENERALIZED_TIME:
    case TYPE_GRAPHIC_STRING:
    case TYPE_VISIBLE_STRING:
    case TYPE_GENERAL_STRING:
    case TYPE_UNIVERSAL_STRING:
    case TYPE_CHARACTER_STRING:
    case TYPE_BMP_STRING:
    case TYPE_PRE_SEQUENCE:
    case TYPE_PRE_SET_OF:
      return 1;
    default:
      return 0;
    }
}


/* Change the value field of the node to the content of buffer value
   of size LEN.  With VALUE of NULL or LEN of 0 and a VTYPE of
   VALTYPE_NULL the value field is deleted */
void
_ksba_asn_set_value (AsnNode node,
                     enum asn_value_type vtype, const void *value, size_t len)
{
  return_if_fail (node);

  if (node->valuetype)
    {
      if (node->valuetype == VALTYPE_CSTR)
        xfree (node->value.v_cstr);
      else if (node->valuetype == VALTYPE_MEM)
        xfree (node->value.v_mem.buf);
      node->valuetype = 0;
    }

  switch (vtype)
    {
    case VALTYPE_NULL:
      break;
    case VALTYPE_BOOL:
      return_if_fail (len && value);
      node->value.v_bool = !!*(const unsigned *)value;
      break;
    case VALTYPE_CSTR:
      return_if_fail (value);
      node->value.v_cstr = xstrdup (value);
      break;
    case VALTYPE_MEM:
      node->value.v_mem.len = len;
      if (len && value)
        {
          node->value.v_mem.buf = xmalloc (len);
          memcpy (node->value.v_mem.buf, value, len);
        }
      else
          node->value.v_mem.buf = NULL;
      break;
    case VALTYPE_LONG:
      return_if_fail (sizeof (long) == len && value);
      node->value.v_long = *(long *)value;
      break;

    case VALTYPE_ULONG:
      return_if_fail (sizeof (unsigned long) == len && value);
      node->value.v_ulong = *(unsigned long *)value;
      break;

    default:
      return_if_fail (0);
    }
  node->valuetype = vtype;
}

static void
copy_value (AsnNode d, const AsnNode s)
{
  char helpbuf[1];
  const void *buf = NULL;
  size_t len = 0;

  return_if_fail (d != s);

  switch (s->valuetype)
    {
    case VALTYPE_NULL:
      break;
    case VALTYPE_BOOL:
      len = 1;
      helpbuf[0] = s->value.v_bool;
      buf = helpbuf;
      break;
    case VALTYPE_CSTR:
      buf = s->value.v_cstr;
      break;
    case VALTYPE_MEM:
      len = s->value.v_mem.len;
      buf = len? s->value.v_mem.buf : NULL;
      break;
    case VALTYPE_LONG:
      len = sizeof (long);
      buf = &s->value.v_long;
      break;
    case VALTYPE_ULONG:
      len = sizeof (unsigned long);
      buf = &s->value.v_ulong;
      break;

    default:
      return_if_fail (0);
    }
  _ksba_asn_set_value (d, s->valuetype, buf, len);
  d->off = s->off;
  d->nhdr = s->nhdr;
  d->len = s->len;
}

static AsnNode
copy_node (const AsnNode s)
{
  AsnNode d = add_node (s->type);

  if (s->name)
    d->name = xstrdup (s->name);
  d->flags = s->flags;
  copy_value (d, s);
  return d;
}




/* Change the name field of the node to NAME.
   NAME may be NULL */
void
_ksba_asn_set_name (AsnNode node, const char *name)
{
  return_if_fail (node);

  if (node->name)
    {
      xfree (node->name);
      node->name = NULL;
    }

  if (name && *name)
      node->name = xstrdup (name);
}


static AsnNode
set_right (AsnNode  node, AsnNode  right)
{
  if (node == NULL)
    return node;

  node->right = right;
  if (right)
    right->left = node;
  return node;
}


static AsnNode
set_down (AsnNode node, AsnNode down)
{
  if (node == NULL)
    return node;

  node->down = down;
  if (down)
    down->left = node;
  return node;
}


void
_ksba_asn_remove_node (AsnNode  node)
{
  if (node == NULL)
    return;

  xfree (node->name);
  if (node->valuetype == VALTYPE_CSTR)
    xfree (node->value.v_cstr);
  else if (node->valuetype == VALTYPE_MEM)
    xfree (node->value.v_mem.buf);
  xfree (node);
}


/* find the node with the given name.  A name part of "?LAST" matches
   the last element of a SET_OF.  A "+" matches the CHOICE with values
   set. */
static AsnNode
find_node (AsnNode root, const char *name, int resolve)
{
  AsnNode p;
  const char *s;
  char buf[129];
  int i;

  if (!name || !name[0])
    return NULL;

  /* gpgrt_log_debug ("%s: looking for '%s'\n", __func__, name); */
  /* find the first part */
  s = name;
  for (i=0; *s && *s != '.' && i < DIM(buf)-1; s++)
    buf[i++] = *s;
  buf[i] = 0;
  return_null_if_fail (i < DIM(buf)-1);

  for (p = root; p && (!p->name || strcmp (p->name, buf)); p = p->right)
    ;

  /* find other parts */
  while (p && *s)
    {
      assert (*s == '.');
      s++; /* skip the dot */

      if (!p->down)
	return NULL; /* not found */
      p = p->down;

      for (i=0; *s && *s != '.' && i < DIM(buf)-1; s++)
        buf[i++] = *s;
      buf[i] = 0;
      return_null_if_fail (i < DIM(buf)-1);

      if (!*buf)
        {
         /* a double dot can be used to get over an unnamed sequence
            in a set - Actually a hack to workaround a bug.  We should
            rethink the entire node naming issue */
          /* gpgrt_log_debug ("%s: .. to '%s'\n", __func__, p?p->name:""); */
        }
      else if (!strcmp (buf, "?LAST"))
	{
	  if (!p)
	    return NULL;
	  while (p->right)
	    p = p->right;
	}
      else if (*buf == '+' && !buf[1])
        {
          for (; p ; p = p->right)
            if (p->off != -1)
              break;
          /* gpgrt_log_debug ("%s: + to '%s'\n", __func__, p?p->name:""); */
        }
      else
	{
          for (; p ; p = p->right)
            {
              /* gpgrt_log_debug ("%s: '%s' to '%s'\n", */
              /*                  __func__, buf, p?p->name:""); */
              if (p->name && !strcmp (p->name, buf))
                break;
              if (resolve && p->name && p->type == TYPE_IDENTIFIER)
                {
                  AsnNode p2;

                  p2 = resolve_identifier (root, p, 0);
                  if (p2 && p2->name && !strcmp (p2->name, buf))
                    break;
                }
            }

          if (resolve && p && p->type == TYPE_IDENTIFIER)
            p = resolve_identifier (root, p, 0);
	}
    }

  return p;
}

AsnNode
_ksba_asn_find_node (AsnNode root, const char *name)
{
  return find_node (root, name, 0);
}


static AsnNode
_asn1_find_left (AsnNode  node)
{
  if ((node == NULL) || (node->left == NULL) || (node->left->down == node))
    return NULL;

  return node->left;
}


static AsnNode
find_up (AsnNode  node)
{
  AsnNode p;

  if (node == NULL)
    return NULL;

  p = node;
  while ((p->left != NULL) && (p->left->right == p))
    p = p->left;

  return p->left;
}



static void
print_value (AsnNode node, FILE *fp)
{
  if (!node->valuetype)
    return;
  fprintf (fp, " vt=%d val=", node->valuetype);
  switch (node->valuetype)
    {
    case VALTYPE_BOOL:
      fputs (node->value.v_bool? "True":"False", fp);
      break;
    case VALTYPE_CSTR:
      fputs (node->value.v_cstr, fp);
      break;
    case VALTYPE_MEM:
      {
        size_t n;
        unsigned char *p;
        for (p=node->value.v_mem.buf, n=node->value.v_mem.len; n; n--, p++)
          fprintf (fp, "%02X", *p);
      }
      break;
    case VALTYPE_LONG:
      fprintf (fp, "%ld", node->value.v_long);
      break;
    case VALTYPE_ULONG:
      fprintf (fp, "%lu", node->value.v_ulong);
      break;
    default:
      return_if_fail (0);
    }
}

void
_ksba_asn_node_dump (AsnNode p, FILE *fp)
{
  const char *typestr;

  switch (p->type)
    {
    case TYPE_NULL:	    typestr = "NULL"; break;
    case TYPE_CONSTANT:     typestr = "CONST"; break;
    case TYPE_IDENTIFIER:   typestr = "IDENTIFIER"; break;
    case TYPE_INTEGER:	    typestr = "INTEGER"; break;
    case TYPE_ENUMERATED:   typestr = "ENUMERATED"; break;
    case TYPE_UTC_TIME:	    typestr = "UTCTIME"; break;
    case TYPE_GENERALIZED_TIME: typestr = "GENERALIZEDTIME"; break;
    case TYPE_BOOLEAN:	    typestr = "BOOLEAN"; break;
    case TYPE_SEQUENCE:	    typestr = "SEQUENCE"; break;
    case TYPE_PRE_SEQUENCE: typestr = "PRE_SEQUENCE"; break;
    case TYPE_PRE_SET_OF:   typestr = "PRE_SET_OF"; break;
    case TYPE_BIT_STRING:   typestr = "BIT_STR"; break;
    case TYPE_OCTET_STRING: typestr = "OCT_STR"; break;
    case TYPE_TAG:	    typestr = "TAG"; break;
    case TYPE_DEFAULT:	    typestr = "DEFAULT"; break;
    case TYPE_SIZE:	    typestr = "SIZE"; break;
    case TYPE_SEQUENCE_OF:  typestr = "SEQ_OF"; break;
    case TYPE_OBJECT_ID:    typestr = "OBJ_ID"; break;
    case TYPE_ANY:	    typestr = "ANY"; break;
    case TYPE_SET:          typestr = "SET"; break;
    case TYPE_SET_OF: 	    typestr = "SET_OF"; break;
    case TYPE_CHOICE:	    typestr = "CHOICE"; break;
    case TYPE_DEFINITIONS:  typestr = "DEFINITIONS"; break;
    case TYPE_UTF8_STRING:       typestr = "UTF8_STRING"; break;
    case TYPE_NUMERIC_STRING:    typestr = "NUMERIC_STRING"; break;
    case TYPE_PRINTABLE_STRING:  typestr = "PRINTABLE_STRING"; break;
    case TYPE_TELETEX_STRING:    typestr = "TELETEX_STRING"; break;
    case TYPE_IA5_STRING:        typestr = "IA5_STRING"; break;
    default:	            typestr = "ERROR\n"; break;
    }

  fprintf (fp, "%s", typestr);
  if (p->name)
    fprintf (fp, " `%s'", p->name);
  print_value (p, fp);
  fputs ("  ", fp);
  switch (p->flags.class)
    {
    case CLASS_UNIVERSAL:   fputs ("U", fp); break;
    case CLASS_PRIVATE:     fputs ("P", fp); break;
    case CLASS_APPLICATION: fputs ("A", fp); break;
    case CLASS_CONTEXT:     fputs ("C", fp); break;
    }

  if (p->flags.explicit)
    fputs (",explicit", fp);
  if (p->flags.implicit)
    fputs (",implicit", fp);
  if (p->flags.is_implicit)
    fputs (",is_implicit", fp);
  if (p->flags.has_tag)
    fputs (",tag", fp);
  if (p->flags.has_default)
    fputs (",default", fp);
  if (p->flags.is_true)
    fputs (",true", fp);
  if (p->flags.is_false)
    fputs (",false", fp);
  if (p->flags.has_list)
    fputs (",list", fp);
  if (p->flags.has_min_max)
    fputs (",min_max", fp);
  if (p->flags.is_optional)
    fputs (",optional", fp);
  if (p->flags.one_param)
    fputs (",1_param", fp);
  if (p->flags.has_size)
    fputs (",size", fp);
  if (p->flags.has_defined_by)
    fputs (",def_by", fp);
  if (p->flags.has_imports)
    fputs (",imports", fp);
  if (p->flags.assignment)
    fputs (",assign",fp);
  if (p->flags.in_set)
    fputs (",in_set",fp);
  if (p->flags.in_choice)
    fputs (",in_choice",fp);
  if (p->flags.in_array)
    fputs (",in_array",fp);
  if (p->flags.not_used)
    fputs (",not_used",fp);
  if (p->flags.skip_this)
    fputs (",[skip]",fp);
  if (p->flags.is_any)
    fputs (",is_any",fp);
  if (p->off != -1 )
    fprintf (fp, " %d.%d.%d", p->off, p->nhdr, p->len );

}

void
_ksba_asn_node_dump_all (AsnNode root, FILE *fp)
{
  AsnNode p = root;
  int indent = 0;

  while (p)
    {
      fprintf (fp, "%*s", indent, "");
      _ksba_asn_node_dump (p, fp);
      putc ('\n', fp);

      if (p->down)
	{
	  p = p->down;
	  indent += 2;
	}
      else if (p == root)
	{
	  p = NULL;
	  break;
	}
      else if (p->right)
	p = p->right;
      else
	{
	  while (1)
	    {
	      p = find_up (p);
	      if (p == root)
		{
		  p = NULL;
		  break;
		}
	      indent -= 2;
	      if (p->right)
		{
		  p = p->right;
		  break;
		}
	    }
	}
    }
}

/**
 * ksba_asn_tree_dump:
 * @tree: A Parse Tree
 * @name: Name of the element or NULL
 * @fp: dump to this stream
 *
 * If the first character of the name is a '<' the expanded version of
 * the tree will be printed.
 *
 * This function is a debugging aid.
 **/
void
ksba_asn_tree_dump (ksba_asn_tree_t tree, const char *name, FILE *fp)
{
  AsnNode p, root;
  int k, expand=0, indent = 0;

  if (!tree || !tree->parse_tree)
    return;

  if ( name && *name== '<')
    {
      expand = 1;
      name++;
      if (!*name)
        name = NULL;
    }

  root = name? _ksba_asn_find_node (tree->parse_tree, name) : tree->parse_tree;
  if (!root)
    return;

  if (expand)
    root = _ksba_asn_expand_tree (root, NULL);

  p = root;
  while (p)
    {
      for (k = 0; k < indent; k++)
	fprintf (fp, " ");
      _ksba_asn_node_dump (p, fp);
      putc ('\n', fp);

      if (p->down)
	{
	  p = p->down;
	  indent += 2;
	}
      else if (p == root)
	{
	  p = NULL;
	  break;
	}
      else if (p->right)
	p = p->right;
      else
	{
	  while (1)
	    {
	      p = find_up (p);
	      if (p == root)
		{
		  p = NULL;
		  break;
		}
	      indent -= 2;
	      if (p->right)
		{
		  p = p->right;
		  break;
		}
	    }
	}
    }

  if (expand)
    _ksba_asn_release_nodes (root);
}

int
_ksba_asn_delete_structure (AsnNode root)
{
  AsnNode p, p2, p3;

  if (root == NULL)
    return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);

  p = root;
  while (p)
    {
      if (p->down)
	{
	  p = p->down;
	}
      else
	{			/* no down */
	  p2 = p->right;
	  if (p != root)
	    {
	      p3 = find_up (p);
	      set_down (p3, p2);
	      _ksba_asn_remove_node (p);
	      p = p3;
	    }
	  else
	    {			/* p==root */
	      p3 = _asn1_find_left (p);
	      if (!p3)
		{
		  p3 = find_up (p);
		  if (p3)
		    set_down (p3, p2);
		  else
		    {
		      if (p->right)
			p->right->left = NULL;
		    }
		}
	      else
		set_right (p3, p2);
	      _ksba_asn_remove_node (p);
	      p = NULL;
	    }
	}
    }
  return 0;
}


/* check that all identifiers referenced in the tree are available */
int
_ksba_asn_check_identifier (AsnNode node)
{
  AsnNode p, p2;
  char name2[129];

  if (!node)
    return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);

  for (p = node; p; p = _ksba_asn_walk_tree (node, p))
    {
      if (p->type == TYPE_IDENTIFIER && p->valuetype == VALTYPE_CSTR)
	{
          if (strlen (node->name)+strlen(p->value.v_cstr)+2 > DIM(name2))
            return gpg_error (GPG_ERR_BUG); /* well identifier too long */
          strcpy (name2, node->name);
          strcat (name2, ".");
	  strcat (name2, p->value.v_cstr);
	  p2 = _ksba_asn_find_node (node, name2);
	  if (!p2)
	    {
	      fprintf (stderr,"reference to `%s' not found\n", name2);
	      return gpg_error (GPG_ERR_IDENTIFIER_NOT_FOUND);
	    }
/*            fprintf (stdout,"found reference for `%s' (", name2); */
/*            print_node (p2, stdout); */
/*            fputs (")\n", stdout); */
	}
      else if (p->type == TYPE_OBJECT_ID && p->flags.assignment)
	{ /* an object ID in an assignment */
	  p2 = p->down;
	  if (p2 && (p2->type == TYPE_CONSTANT))
            {
	      if (p2->valuetype == VALTYPE_CSTR && !isdigit (p2->value.v_cstr[0]))
		{ /* the first constand below is a reference */
                  if (strlen (node->name)
                      +strlen(p->value.v_cstr)+2 > DIM(name2))
                    return gpg_error (GPG_ERR_BUG); /* well identifier too long */
                  strcpy (name2, node->name);
                  strcat (name2, ".");
		  strcat (name2, p2->value.v_cstr);
		  p2 = _ksba_asn_find_node (node, name2);
		  if (!p2)
                    {
                      fprintf (stderr,"object id reference `%s' not found\n",
                               name2);
                      return gpg_error (GPG_ERR_IDENTIFIER_NOT_FOUND);
                    }
                  else if ( p2->type != TYPE_OBJECT_ID
                            || !p2->flags.assignment )
		    {
		      fprintf (stderr,"`%s' is not an object id\n", name2);
		      return gpg_error (GPG_ERR_IDENTIFIER_NOT_FOUND);
		    }
/*                    fprintf (stdout,"found objid reference for `%s' (", name2); */
/*                    print_node (p2, stdout); */
/*                    fputs (")\n", stdout); */
		}
	    }
	}
    }

  return 0;
}


/* Get the next node until root is reached in which case NULL is
   returned */
AsnNode
_ksba_asn_walk_tree (AsnNode root, AsnNode node)
{
  if (!node)
    ;
  else if (node->down)
    node = node->down;
  else
    {
      if (node == root)
        node = NULL;
      else if (node->right)
        node = node->right;
      else
        {
          for (;;)
            {
              node = find_up (node);
              if (node == root)
                {
                  node = NULL;
                  break;
                }
              if (node->right)
                {
                  node = node->right;
                  break;
                }
            }
        }
    }

  return node;
}

AsnNode
_ksba_asn_walk_tree_up_right (AsnNode root, AsnNode node)
{
  if (node)
    {
      if (node == root)
        node = NULL;
      else
        {
          for (;;)
            {
              node = find_up (node);
              if (node == root)
                {
                  node = NULL;
                  break;
                }
              if (node->right)
                {
                  node = node->right;
                  break;
                }
            }
        }
    }

  return node;
}

/* walk over the tree and change the value type of all integer types
   from string to long. */
int
_ksba_asn_change_integer_value (AsnNode node)
{
  AsnNode p;

  if (node == NULL)
    return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);

  for (p = node; p; p = _ksba_asn_walk_tree (node, p))
    {
      if (p->type == TYPE_INTEGER && p->flags.assignment)
	{
	  if (p->valuetype == VALTYPE_CSTR)
	    {
              long val = strtol (p->value.v_cstr, NULL, 10);
	      _ksba_asn_set_value (p, VALTYPE_LONG, &val, sizeof(val));
	    }
	}
    }

  return 0;
}



/* Expand all object ID constants */
int
_ksba_asn_expand_object_id (AsnNode node)
{
  AsnNode p, p2, p3, p4, p5;
  char name_root[129], name2[129*2+1] = "";

  /* Fixme: Make a cleaner implementation */
  if (!node)
    return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
  if (!node->name)
    return gpg_error (GPG_ERR_INV_VALUE);
  if (strlen(node->name) >= DIM(name_root)-1)
    return gpg_error (GPG_ERR_GENERAL);
  strcpy (name_root, node->name);

 restart:
  for (p = node; p; p = _ksba_asn_walk_tree (node, p))
    {
      if (p->type == TYPE_OBJECT_ID && p->flags.assignment)
        {
          p2 = p->down;
          if (p2 && p2->type == TYPE_CONSTANT)
            {
              if (p2->valuetype == VALTYPE_CSTR
                  && !isdigit (p2->value.v_cstr[0]))
                {
                  if (strlen(p2->value.v_cstr)+1+strlen(name2) >= DIM(name2)-1)
                    return gpg_error (GPG_ERR_GENERAL);
                  strcpy (name2, name_root);
                  strcat (name2, ".");
                  strcat (name2, p2->value.v_cstr);
                  p3 = _ksba_asn_find_node (node, name2);
                  if (!p3 || p3->type != TYPE_OBJECT_ID ||
                      !p3->flags.assignment)
                    return gpg_error (GPG_ERR_ELEMENT_NOT_FOUND);
                  set_down (p, p2->right);
                  _ksba_asn_remove_node (p2);
                  p2 = p;
                  p4 = p3->down;
                  while (p4)
                    {
                      if (p4->type == TYPE_CONSTANT)
                        {
                          p5 = add_node (TYPE_CONSTANT);
                          _ksba_asn_set_name (p5, p4->name);
                          _ksba_asn_set_value (p5, VALTYPE_CSTR,
                                               p4->value.v_cstr, 0);
                          if (p2 == p)
                            {
                              set_right (p5, p->down);
                              set_down (p, p5);
                            }
                          else
                            {
                              set_right (p5, p2->right);
                              set_right (p2, p5);
                            }
                          p2 = p5;
                        }
                      p4 = p4->right;
                    }
                  goto restart;  /* the most simple way to get it right ;-) */
                }
            }
        }
    }
  return 0;
}

/* Walk the parse tree and set the default tag where appropriate.  The
   node must be of type DEFINITIONS */
void
_ksba_asn_set_default_tag (AsnNode node)
{
  AsnNode p;

  return_if_fail (node && node->type == TYPE_DEFINITIONS);

  for (p = node; p; p = _ksba_asn_walk_tree (node, p))
    {
      if ( p->type == TYPE_TAG
           && !p->flags.explicit && !p->flags.implicit)
	{
	  if (node->flags.explicit)
	    p->flags.explicit = 1;
	  else
	    p->flags.implicit = 1;
	}
    }
  /* now mark the nodes which are implicit */
  for (p = node; p; p = _ksba_asn_walk_tree (node, p))
    {
      if ( p->type == TYPE_TAG && p->flags.implicit && p->down)
	{
	  if (p->down->type == TYPE_CHOICE)
            ; /* a CHOICE is per se implicit */
	  else if (p->down->type != TYPE_TAG)
	    p->down->flags.is_implicit = 1;
	}
    }
}

/* Walk the tree and set the is_set and not_used flags for all nodes below
   a node of type SET. */
void
_ksba_asn_type_set_config (AsnNode node)
{
  AsnNode p, p2;

  return_if_fail (node && node->type == TYPE_DEFINITIONS);

  for (p = node; p; p = _ksba_asn_walk_tree (node, p))
    {
      if (p->type == TYPE_SET)
        {
          for (p2 = p->down; p2; p2 = p2->right)
            {
              if (p2->type != TYPE_TAG)
                {
                  p2->flags.in_set = 1;
                  p2->flags.not_used = 1;
                }
            }
        }
      else if (p->type == TYPE_CHOICE)
        {
          for (p2 = p->down; p2; p2 = p2->right)
            {
                p2->flags.in_choice = 1;
            }
        }
      else if (p->type == TYPE_SEQUENCE_OF || p->type == TYPE_SET_OF)
        {
          for (p2 = p->down; p2; p2 = p2->right)
            p2->flags.in_array = 1;
        }
      else if (p->type == TYPE_ANY)
        { /* Help the DER encoder to track ANY tags */
          p->flags.is_any = 1;
        }
    }
}

/* Create a copy the tree at SRC_ROOT. s is a helper which should be
   set to SRC_ROOT by the caller */
static AsnNode
copy_tree (AsnNode src_root, AsnNode s)
{
  AsnNode first=NULL, dprev=NULL, d, down, tmp;
  AsnNode *link_nextp = NULL;

  for (; s; s=s->right )
    {
      down = s->down;
      d = copy_node (s);
      if (link_nextp)
	*link_nextp = d;
      link_nextp = &d->link_next;

      if (!first)
        first = d;
      else
        {
          dprev->right = d;
          d->left = dprev;
        }
      dprev = d;
      if (down)
        {
          tmp = copy_tree (src_root, down);
	  if (tmp)
	    {
	      if (link_nextp)
		*link_nextp = tmp;
	      link_nextp = &tmp->link_next;
	      while (*link_nextp)
		link_nextp = &(*link_nextp)->link_next;
	    }

          if (d->down && tmp)
            { /* Need to merge it with the existing down */
              AsnNode x;

              for (x=d->down; x->right; x = x->right)
                ;
              x->right = tmp;
              tmp->left = x;
            }
          else
            {
              d->down = tmp;
              if (d->down)
                d->down->left = d;
            }
        }
    }
  return first;
}



static AsnNode
resolve_identifier (AsnNode root, AsnNode node, int nestlevel)
{
  char buf_space[50];
  char *buf;
  AsnNode n;
  size_t bufsize;

  if (nestlevel > 20)
    return NULL;

  return_null_if_fail (root);
  return_null_if_fail (node->valuetype == VALTYPE_CSTR);

  bufsize = strlen (root->name) + strlen (node->value.v_cstr) + 2;
  if (bufsize <= sizeof buf_space)
    buf = buf_space;
  else
    {
      buf = xtrymalloc (bufsize);
      return_null_if_fail (buf);
    }
  strcpy (stpcpy (stpcpy (buf, root->name), "."), node->value.v_cstr);
  n = _ksba_asn_find_node (root, buf);

  /* We do just a simple indirection. */
  if (n && n->type == TYPE_IDENTIFIER)
    n = resolve_identifier (root, n, nestlevel+1);

  if (buf != buf_space)
    xfree (buf);

  return n;
}


static AsnNode
do_expand_tree (AsnNode src_root, AsnNode s, int depth)
{
  AsnNode first=NULL, dprev=NULL, d, down, tmp;
  AsnNode *link_nextp = NULL;

  /* On the very first level we do not follow the right pointer so that
     we can break out a valid subtree. */
  for (; s; s=depth?s->right:NULL )
    {
      if (s->type == TYPE_SIZE)
        continue; /* this node gets in the way all the time.  It
                     should be an attribute to a node */

      down = s->down;
      if (s->type == TYPE_IDENTIFIER)
        {
          AsnNode s2, *dp;

          d = resolve_identifier (src_root, s, 0);
          if (!d)
            {
              fprintf (stderr, "RESOLVING IDENTIFIER FAILED\n");
              continue;
            }
          down = d->down;
          d = copy_node (d);
	  if (link_nextp)
	    *link_nextp = d;
	  link_nextp = &d->link_next;
          if (s->flags.is_optional)
            d->flags.is_optional = 1;
          if (s->flags.in_choice)
            d->flags.in_choice = 1;
          if (s->flags.in_array)
            d->flags.in_array = 1;
          if (s->flags.is_implicit)
            d->flags.is_implicit = 1;
          if (s->flags.is_any)
            d->flags.is_any = 1;
          /* we don't want the resolved name - change it back */
          _ksba_asn_set_name (d, s->name);
          /* copy the default and tag attributes */
          tmp = NULL;
          dp = &tmp;
          for (s2=s->down; s2; s2=s2->right)
            {
              AsnNode x;

              x = copy_node (s2);
	      if (link_nextp)
		*link_nextp = x;
	      link_nextp = &x->link_next;
              x->left = *dp? *dp : d;
              *dp = x;
              dp = &(*dp)->right;

              if (x->type == TYPE_TAG)
                d->flags.has_tag =1;
              else if (x->type == TYPE_DEFAULT)
                d->flags.has_default =1;
            }
          d->down = tmp;
        }
      else
        {
	  d = copy_node (s);
	  if (link_nextp)
	    *link_nextp = d;
	  link_nextp = &d->link_next;
	}

      if (!first)
        first = d;
      else
        {
          dprev->right = d;
          d->left = dprev;
        }
      dprev = d;
      if (down)
        {
          if (depth >= 1000)
            {
              fprintf (stderr, "ASN.1 TREE TOO TALL!\n");
              tmp = NULL;
            }
          else
            {
	      tmp = do_expand_tree (src_root, down, depth+1);
	      if (tmp)
		{
		  if (link_nextp)
		    *link_nextp = tmp;
		  link_nextp = &tmp->link_next;
		  while (*link_nextp)
		    link_nextp = &(*link_nextp)->link_next;
		}
	    }
          if (d->down && tmp)
            { /* Need to merge it with the existing down */
              AsnNode x;

              for (x=d->down; x->right; x = x->right)
                ;
              x->right = tmp;
              tmp->left = x;
            }
          else
            {
              d->down = tmp;
              if (d->down)
                d->down->left = d;
            }
        }
    }

  return first;
}


/* Expand the syntax tree so that all references are resolved and we
   are able to store values right in the tree (except for set/sequence
   of).  This expanded tree is also an requirement for doing the DER
   decoding as the resolving of identifiers leads to a lot of
   problems.  We use more memory of course, but this is negligible
   because the entire code will be simpler and faster */
AsnNode
_ksba_asn_expand_tree (AsnNode parse_tree, const char *name)
{
  AsnNode root;

  root = name? find_node (parse_tree, name, 1) : parse_tree;
  return do_expand_tree (parse_tree, root, 0);
}


/* Insert a copy of the entire tree at NODE as the sibling of itself
   and return the copy */
AsnNode
_ksba_asn_insert_copy (AsnNode node)
{
  AsnNode n;
  AsnNode *link_nextp;

  n = copy_tree (node, node);
  if (!n)
    return NULL; /* out of core */
  return_null_if_fail (n->right == node->right);
  node->right = n;
  n->left = node;

  /* FIXME: Consider tail pointer for faster insertion.  */
  link_nextp = &node->link_next;
  while (*link_nextp)
    link_nextp = &(*link_nextp)->link_next;
  *link_nextp = n;

  return n;
}


/* Locate a type value sequence like

  SEQUENCE {
     type    OBJECT IDENTIFIER
     value   ANY
  }

  below root and return the 'value' node.  OIDBUF should contain the
  DER encoding of an OID value.  idx is the number of OIDs to skip;
  this can be used to enumerate structures with the same OID */
AsnNode
_ksba_asn_find_type_value (const unsigned char *image, AsnNode root, int idx,
                           const void *oidbuf, size_t oidlen)
{
  AsnNode n, noid;

  if (!image || !root)
    return NULL;

  for (n = root; n; n = _ksba_asn_walk_tree (root, n) )
    {
      if ( n->type == TYPE_SEQUENCE
           && n->down && n->down->type == TYPE_OBJECT_ID)
        {
          noid = n->down;
          if (noid->off != -1 && noid->len == oidlen
              && !memcmp (image + noid->off + noid->nhdr, oidbuf, oidlen)
              && noid->right)
            {
              if ( !idx-- )
                return noid->right;
            }

        }
    }
  return NULL;
}