pgprngpub.c

PGP—Pretty Good Privacy

/*
 * pgpRngPub.c - keyring management public functions.
 *
 * Written by Colin Plumb.
 *
 * $Id: pgpRngPub.c,v 1.83.2.1 1999/06/04 00:28:54 heller Exp $
 */
#include "pgpConfig.h"
#include <string.h>

#include <ctype.h>	/* For tolower() */

#include "pgpDebug.h"
#include "pgpRngPriv.h"
#include "pgpRngPars.h"
#include "pgpTrstPkt.h"
#include "pgpTrust.h"
#include "pgpRngMnt.h"
#include "pgpErrors.h"
#include "pgpPubKey.h"
#include "pgpRngPub.h"
#include "pgpRngRead.h"
#include "pgpSigSpec.h"
#include "pgpMem.h"
#include "pgpContext.h"
#include "pgpEnv.h"
#include "pgpKeyIDPriv.h"
#include "pgpX509Priv.h"

#ifndef NULL
#define NULL 0
#endif

/*
 * The four type bits are encoded as described in pgpRngPriv.h.
 */
int
ringObjectType(union RingObject const *obj)
{
	int const types[] = {
		RINGTYPE_UNK, RINGTYPE_SEC, RINGTYPE_KEY, RINGTYPE_KEY,
		RINGTYPE_SIG, RINGTYPE_NAME, RINGTYPE_CRL };
	PGPByte type_index;

	pgpAssert (obj);
	type_index = (obj->g.flags&RINGOBJF_TYPE) >> RINGOBJ_SHIFT;
	pgpAssert (type_index < sizeof(types)/sizeof(types[0]));
	return types[type_index];
}

/*
 * These are intended to track reference counts for swapping
 * pieces of keyring out of memory, but are currently no-ops.
 *
 * They're called in a few places in the code as placeholders, but
 * that's just for documentation purposes.
 */
void
ringObjectHold(union RingObject *obj)
{
	(void)obj;
}

void
ringObjectRelease(union RingObject *obj)
{
	(void)obj;
}

RingPool *
ringSetPool(RingSet const *set)
{
	if (!set)
		return NULL;
	return set->pool;
}

/*
 * Return errors in all sorts of cases.
 */
RingError const *
ringPoolError(RingPool const *pool)
{
	pgpAssert (pool);
	return &pool->e;
}

void
ringPoolClearError(RingPool *pool)
{
	if (pool) {
		pool->e.f = (RingFile *)NULL;
		pool->e.fpos = (PGPUInt32)-1;
		pool->e.error = kPGPError_NoErr;
		pool->e.syserrno = 0;
	}
}

RingError const *
ringSetError(RingSet const *set)
{
	pgpAssert (set);
	return &set->pool->e;
}

void
ringSetClearError(RingSet *set)
{
	if (set)
		ringPoolClearError(set->pool);
}

RingError const *
ringIterError(RingIterator const *iter)
{
	pgpAssert (iter);
	return &iter->set.pool->e;
}

void
ringIterClearError(RingIterator *iter)
{
	if (iter)
		ringPoolClearError(iter->set.pool);
}

RingError const *
ringFileError(RingFile const *f)
{
	pgpAssert (f);
	return &f->set.pool->e;
}

void
ringFileClearError(RingFile *f)
{
	if (f)
		ringPoolClearError(f->set.pool);
}

PGPError
ringFileSwitchFile(RingFile *file, PGPFile *newPGPFile)
{
	pgpAssertAddrValid(file, RingFile);
	file->f = newPGPFile;
	return kPGPError_NoErr;
}

/*
 * Is the object a member of the set?
 * Returns the level of the object, or 0 if it is not.
 */
int
ringSetIsMember(RingSet const *set, union RingObject const *obj)
{
	int level = 1;

	while (pgpIsRingSetMember(set, obj)) {
		if (OBJISTOP(obj))
			return level;
		obj = obj->g.up;
		level++;
	}
	return 0;	/* Not a member of the iterator */
}

RingSet const *
ringIterSet(RingIterator const *iter)
{
	if (!iter)
		return NULL;
	return &iter->set;
}

RingSet const *
ringFileSet(RingFile const *file)
{
	if (!file)
		return NULL;
	return &file->set;
}

PgpVersion
ringFileVersion(RingFile const *file)
{
        if (!file)
	        return 0;
	return file->version;
}

/*
 * An iterator involves a current position which is a stack, with an
 * accessible stack-depth value.  The stack depth equals the level
 * of the last ringIterNextObject call, and the stack entries
 * are the return values.  If a query is made for a level which
 * is greater than the stack depth, the first entry on the list
 * of descendants of the top entry on the stack is returned.
 * Only the highest-level entry may be NULL; that indicates that the
 * end of the list there has been reached.  It is illegal to
 * ask for descendants of a NULL entry; although returning NULL
 * is another reasonable option, the usefulness is unclear and the
 * stricter rule has the advantage of catching bugs faster.
 */

/*
 * Find the next object of the given level in the given iterator.
 * Returns <0 on error, 0 if there is no object, or the level if
 * there is one.
 */
int
ringIterNextObject(RingIterator *iter, unsigned level)
{
	union RingObject *obj;

	pgpAssert(iter);
	pgpAssert(level);
	pgpAssert(iter->set.type == RINGSET_ITERATOR);

	/* Get the head of the list to search */
	if (level <= iter->level) {
		/* Going along an existing level */
		iter->level = level;
		obj = iter->stack[level-1];
		if (!obj)
			return 0;
		pgpAssert (pgpIsRingSetMember (&iter->set, obj));
		obj = obj->g.next;
	} else {
		/* Going down a level */
		pgpAssert(level == iter->level+1);

		if (level > 1) {
			obj = iter->stack[level-2];
			pgpAssert(obj);
			pgpAssert (pgpIsRingSetMember (&iter->set, obj));
			if (OBJISBOT(obj))
				return 0;
			obj = obj->g.down;
		} else {
			obj = iter->set.pool->keys;
		}
		iter->level = level;
	}

	/* Search for the next item of interest */
	while (obj && !pgpIsRingSetMember (&iter->set, obj))
		obj = obj->g.next;

	pgpAssert(level <= RINGMAXDEPTH);
	iter->stack[level-1] = obj;
	return obj ? level : 0;
}


/*
 * More complex because we need to find the head of the enclosing list and
 * search forwards for the last matching object that's not the target object.
 */
int
ringIterPrevObject(RingIterator *iter, unsigned level)
{
	union RingObject *obj, *found, *target;

	pgpAssert(iter);
	pgpAssert(level);
	pgpAssert(iter->set.type == RINGSET_ITERATOR);

	/* There's nothing before the beginning of a list */
	if (level > iter->level) {
		pgpAssert(level == iter->level+1);
		return 0;
	}

	/* The thing we want the predecessor of */
	target = iter->stack[level-1];

	/* The head of the list to search along */
	if (level > 1) {
		obj = iter->stack[level-2];
		pgpAssert(obj);
		pgpAssert (pgpIsRingSetMember (&iter->set, obj));
		obj = obj->g.down;
		/* obj = iter->stack[level-2]->g.down; */
	} else {
		obj = iter->set.pool->keys;
	}

	/*
	 * Search forward along the list until we hit the current
	 * object, kepping track of the last object in the desired
	 * ringSet.
	 */
	found = NULL;

	while (obj != target) {
		pgpAssert(obj);
		if (pgpIsRingSetMember (&iter->set, obj))
			found = obj;
		obj = obj->g.next;
	}

	if (!found) {
		/* Hit beginning of list, set up as beginning */
		iter->level = level-1;
		return 0;
	}
	iter->stack[level-1] = found;
	if (OBJISBOT(found)) {
		/* Found an object, but no children. */
		return iter->level = level;
	} else {
		/* An object with children - set up that list at end */
		pgpAssert(level <= RINGMAXDEPTH);
		iter->stack[level] = NULL;
		iter->level = level+1;
	}
	return (int)level;
}

/* The level of the most recent ringIterNextObject() call */
unsigned
ringIterCurrentLevel(RingIterator const *iter)
{
	return iter->level;
}

/*
 * A trivial little function that just returns the current object
 * at a given level, again.
 */
union RingObject *
ringIterCurrentObject(RingIterator const *iter, unsigned level)
{
	pgpAssert(iter);
	pgpAssert(level);
	pgpAssert(iter->set.type == RINGSET_ITERATOR);

	return level > iter->level ? NULL : iter->stack[level-1];
}

/*
 * Seek to the next object at the deepest level possible.
 *
 * Equivalent to:
 * int i;
 * unsigned l = ringIterCurrentLevel(iter)+1;
 *
 * while (l && !(i = ringIterNextObject(iter, l)))
 *	--l;
 * return i;
 */
int
ringIterNextObjectAnywhere(RingIterator *iter)
{
	union RingObject *obj;
	unsigned level = iter->level;

	pgpAssert(iter);
	pgpAssert(iter->set.type == RINGSET_ITERATOR);

	/* Find first object to be considered */
	if (!level) {
		level = 1;
		obj = iter->set.pool->keys;
	} else {
		obj = iter->stack[level-1];

		if (obj) {
			pgpAssert (pgpIsRingSetMember (&iter->set, obj));
			if (OBJISBOT(obj)) {
				obj = obj->g.next;
			} else {
				level++;
				obj = obj->g.down;
			}
		}
	}

	for (;;) {
		while (obj) {
			if (pgpIsRingSetMember(&iter->set, obj)) {
				iter->stack[level-1] = obj;
				iter->level = level;
				return (int)level;
			}
			obj = obj->g.next;
		}
		if (!--level)
			break;
		obj = iter->stack[level-1];
		pgpAssert(obj);
		obj = obj->g.next;
	}

	/* End of list, no luck */
	iter->stack[0] = NULL;
	iter->level = 1;
	return 0;
}

/* Reset the iterator to the beginning of the given level */
int
ringIterRewind(RingIterator *iter, unsigned level)
{
	pgpAssert(level);
	pgpAssert(iter->level >= level - 1);
	iter->level = level-1;
	return 0;
}

/* Reset the iterator to the end of the given level */
int
ringIterFastForward(RingIterator *iter, unsigned level)
{
	pgpAssert(level);
	pgpAssert(level <= iter->level + 1);
	if (level > RINGMAXDEPTH)
		level = RINGMAXDEPTH;
	else
		iter->stack[level-1] = NULL;
	iter->level = level;
	return 0;
}

/*
 * Seek the iterator to the given object, state as if it just
 * returned the object.	 Returns the level of the object, or <0
 * on error.
 */
int
ringIterSeekTo(RingIterator *iter, union RingObject *obj)
{
	union RingObject *p, *pp;
	int level;

	pgpAssert(iter->set.type == RINGSET_ITERATOR);

	if (!pgpIsRingSetMember (&iter->set, obj))
		return 0;	/* Not a member */

	/* A bit ad-hoc; there is a general way. */
	if (OBJISTOP(obj)) {
		iter->stack[0] = obj;
		level = 1;
	} else {
		p = obj->g.up;
		pgpAssert(pgpIsRingSetMember(&iter->set, p));
		if (OBJISTOP(p)) {
			iter->stack[0] = p;
			iter->stack[1] = obj;
			level = 2;
		} else {
			pp = p->g.up;
			pgpAssert(pgpIsRingSetMember(&iter->set, pp));
			pgpAssert(OBJISTOP(pp));
			iter->stack[0] = pp;
			iter->stack[1] = p;
			iter->stack[2] = obj;
			level = 3;
		}
	}
	return iter->level = level;
}

static void
ringSetCountList(union RingObject const *obj, PGPVirtMask const *mask,
                 unsigned *counts, unsigned depth)
{
	while (obj) {
		if (pgpVirtMaskIsOverlapping (&obj->g.mask, mask)) {
			counts[0]++;
			if (depth && !OBJISBOT(obj)) {
				ringSetCountList(obj->g.down, mask,
				                 counts+1, depth-1);
			}
		}
		obj = obj->g.next;
	}
}

/*
 * Count the number of objects in an iterator down to a given depth.
 */
int
ringSetCount(RingSet const *set, unsigned *counts, unsigned depth)
{
	unsigned i = 0;

	for (i = 0; i < depth; i++)
		counts[i] = 0;
	if (IsntNull(set) && !pgpVirtMaskIsEmpty(&set->mask) && depth > 0)
		ringSetCountList(set->pool->keys, &set->mask, counts, depth-1);
	return 0;
}

static void
ringSetCountTypesList(union RingObject const *obj, PGPVirtMask const *mask,
                      unsigned *counts, unsigned max)
{
	int t;

	while (obj) {
		if (pgpVirtMaskIsOverlapping (mask, &obj->g.mask)) {
			t = ringObjectType(obj);
			if ((unsigned)t <= max)
				counts[t-1]++;
			if (!OBJISBOT(obj))
				ringSetCountTypesList(obj->g.down, mask,
				                 counts, max);
		}
		obj = obj->g.next;
	}
}

/*
 * Count the number of objects in an iterator of various types.
 */
int
ringSetCountTypes(RingSet const *set, unsigned *counts, unsigned max)
{
	unsigned i = 0;

	for (i = 0; i < max; i++)
		counts[i] = 0;
	if (IsntNull(set) && !pgpVirtMaskIsEmpty(&set->mask) && max > 0)
		ringSetCountTypesList(set->pool->keys, &set->mask, counts, max);
	return 0;
}

RingIterator *
ringIterCreate(RingSet const *set)
{
	RingPool *pool = set->pool;
	RingIterator *iter;

	pgpAssert(!RINGSETISMUTABLE(set));

	/* Allocate the structure */
	iter = pool->freeiter;
	if (iter) {
		pool->freeiter = (RingIterator *)iter->set.next;
		pgpAssert(iter->set.type == RINGSET_FREE);
	} else {
		iter = (RingIterator *)memPoolNew(&pool->structs,
							 RingIterator);
		if (!iter) {
			ringAllocErr(pool);
			return NULL;
		}
	}