pgprngmnt.c

vc环境下的pgp源码

	'0','1','2','3','4','5','6','7',
	'8','9','A','B','C','D','E','F'
};

static int
ringTtyPrintKeyID(FILE *f, RingObject *key)
{
	PGPByte *buf;
	int i;

	pgpAssert (OBJISKEY(key));
	buf = key->k.keyID;
	for (i = 4; i < 8; i++) {
		putc(hexchar[buf[i] >> 4 & 15], f);
		putc(hexchar[buf[i] & 15], f);
	}
	return 8;
}

static int
ringTtyPrintKeyName(FILE *f, RingObject *key, RingPool *pool)
{
	RingSet *set = ringSetCreate(pool);
	char const *sname;
	char bname[256];
	size_t len;

	key = key->g.down;
	while (!OBJISNAME(key)) {
		key = key->g.next;
	}
	ringSetAddObject (set, key);
	sname = ringNameName (set, key, &len);
	strncpy (bname, sname, len);
	bname[len] = '\0';
	fputs (bname, f);
	ringSetDestroy (set);
	return 0;
}

static int
ringTtyPrintKey(FILE *f, RingObject *key, RingPool *pool)
{

	ringTtyPrintKeyID (f, key);
	fprintf (f, "(");
	ringTtyPrintKeyName (f, key, pool);
	fprintf (f, ")");
	return 0;
}

static void
ringTtyPrintPath(FILE *f, Path *path, RingPool *pool)
{
	fprintf (f, " Path ");
	while (path) {
		fprintf (f, "from ");
		ringTtyPrintKey (f, path->src, pool);
		fprintf (f, " to ");
		ringTtyPrintKey (f, path->dest, pool);
		fprintf (f, ", conf: %g\n", path->confidence);
		path = path->next;
		if (path)
			fprintf (f, "  ...segment ");
	}
}

static void
ringTtyPrintPathList(FILE *f, PathList *pl, RingPool *pool)
{
	fprintf (f, "Begin PathList\n");
	while (pl) {
		fprintf (f, " (conf=%g) ", pl->confidence);
		ringTtyPrintPath (f, pl->path, pool);
		pl = pl->next;
	}
	fprintf (f, "End PathList\n");
}

#endif /* DEBUGPATH */


/* Allocate a Path segment */
static Path *
pathAlloc (RingPool *pool)
{
	Path       *path = pool->paths;

	if (path) {
		pool->paths = path->next;
	} else {
		path = (Path *) memPoolAlloc (&pool->pathpool, sizeof(Path),
			alignof(Path));
	}
	return path;
}

/* Free a Path segment */
static void
pathFree (Path *path, RingPool *pool)
{
	if (!path)
		return;
	path->next = pool->paths;
	pool->paths = path;
}

/* Free an entire Path */
static void
pathFreeAll (Path *phead, RingPool *pool)
{
	Path **ptail;

	if (!phead)
		return;
	ptail = &phead->next;
	while (*ptail) {
		ptail = &(*ptail)->next;
	}
	*ptail = pool->paths;
	pool->paths = phead;
}

/* Allocate a PathList element */
static PathList *
pathListAlloc (RingPool *pool)
{
	PathList   *plist = pool->pathlists;

	if (plist) {
		pool->pathlists = plist->next;
		plist->next = NULL;
	} else {
		plist = (PathList *) memPoolAlloc (&pool->pathpool,
					sizeof(PathList), alignof(PathList));
	}
	return plist;
}

#if 0
/* Free a PathList element, also freeing any path it points to */
static void
pathListFree (PathList *plist, RingPool *pool)
{
	if (plist->path)
		pathFreeAll (plist->path, pool);
	plist->path = 0;
	plist->confidence = 0.;
	plist->next = pool->pathlists;
	pool->pathlists = plist;
}
#endif

/* Free a whole PathList, also freeing the Paths it points to */
static void
pathListFreeAll (PathList *plhead, RingPool *pool)
{
	PathList **pltail = &plhead->next;
	while (*pltail)
		pltail = &(*pltail)->next;
	*pltail = pool->pathlists;
	pool->pathlists = plhead;
	while (plhead != *pltail) {
		pathFreeAll (plhead->path, pool);
		plhead->path = 0;
		plhead->confidence = 0.;
		plhead = plhead->next;
	}
}


/* Add a Path segment to a Path
 *
 * Returns	updated Path tail pointer
 *
 * tail		tail pointer for Path to be added to
 * seg		pointer to Path segment to add
 *
 */
static Path **
pathAddSeg (Path **tail, Path *seg)
{
	seg->next = *tail;
	*tail = seg;
	return &seg->next;
}

/*
 * Make a copy of a Path, leaving the original untouched.  Optionally return a
 * pointer to the tail of the new Path.
 *
 * Returns	pointer to new cloned path
 *
 * p1		pointer to the path to be cloned
 * ptl		optional return parameter for tail pointer of new path
 * pool		ringpool used for allocations of new path segments
 *
 */
static Path *
pathClone (Path *p1, Path ***ptl, RingPool *pool)
{
	Path       *phead = NULL,
	          **ptail = &phead;

	while (p1) {
		*ptail = pathAlloc(pool);
		if (!*ptail)
			return NULL;
		**ptail = *p1;
		p1 = p1->next;
		ptail = &(*ptail)->next;
	}
	if (ptl)
		*ptl = ptail;
	return phead;
}


/* Add a copy of a Path to the PathList
 *
 * Returns	tail pointer of updated PathList
 *
 * tail		tail pointer of PathList to be added to
 * path		pointer to Path to add to the PathList
 * pool		ringpool to use for memory allocations
 *
 */
static PathList **
pathListAddPathClone (PathList **tail, Path *path, RingPool *pool)
{
	PathList   *pl;

	pl = pathListAlloc(pool);
	if (!pl)
		return NULL;
	if (path)
		pl->path = pathClone (path, &pl->ptail, pool);
	else {
		pl->path = NULL;
		pl->ptail = &pl->path;
	}
	pl->next = *tail;
	*tail = pl;
	return &pl->next;
}


/* Calculate the confidence associated with a path. */
static double
pathConfidence (Path *path)
{
	double     conf = 1.0;

	while (path) {
		conf *= path->confidence;
		path = path->next;
	}
	return conf;
}

/*
 * Prune the PathList to keep only the highest-confidence pathmax Paths.
 * Return the new PathList, free the no longer used Paths.
 *
 * Returns	new PathList with no more than pathmax paths
 *
 * plist	PathList to be pruned
 * pathmax	maximum number of paths to allow
 * pool		ringpool to use for memory allocations
 *
 */
static PathList *
pathListPrune (PathList *plist, unsigned pathmax, RingPool *pool)
{
	PathList   *iplist;			/* Copy of plist */
	PathList  **pl1,			/* Iterator over plist */
	          **maxpl1;			/* Max confidence pl1 pointer */
	PathList   *nplist,			/* New pathlist head */
	          **nptail;			/* New pathlist tail */
	unsigned    npaths,			/* Number of paths in plist initially */
	            newnpaths;		/* Number of paths in final nplist */
	double      maxconf;		/* Best confidence value so far */

	/* Calculate confidence value for each path */
	iplist = plist;
	npaths = 0;
	while (plist) {
		npaths += 1;
		plist->confidence = pathConfidence (plist->path);
		plist = plist->next;
	}
	plist = iplist;

	/* Initialize the new path list */
	nplist = plist;
	if (npaths > pathmax) {
		nplist = NULL;
		nptail = &nplist;
		newnpaths = pgpMin (pathmax, npaths);
		while (newnpaths--) {
			/* Add the best path from plist to nplist */
			pl1 = &plist;
			maxconf = 0.;
			maxpl1 = pl1;
			while (*pl1) {
				/* Find best path in plist in **maxpl1 */
				if ((*pl1)->confidence > maxconf) {
					maxconf = (*pl1)->confidence;
					maxpl1 = pl1;
				}
				pl1 = &(*pl1)->next;
			}
			*nptail = *maxpl1;
			*maxpl1 = (*maxpl1)->next;
			nptail = &(*nptail)->next;
			*nptail = NULL;
		}

		if (plist)
			pathListFreeAll (plist, pool);
	}
	return nplist;
}


/*
 * Append a (copy of a) second path to the first, removing common segments.
 * Return pointer to "next" pointer of last segment (and pass that as ptail)
 *
 * Return	tail pointer for updated Path
 *
 * phead	pointer to Path which gets appended to
 * ptail	tail pointer for Path which gets appended to
 * p2		pointer to Path to append (a copy of)
 * pool		ringpool to use for memory allocations
 *
 */
static Path **
pathUnion (Path *phead, Path **ptail, Path *p2, RingPool *pool)
{
	Path       *p1;
	Path      **iptail = ptail;

	/* Add path p2 but skip those segments in p1 */
	for ( ; p2; p2 = p2->next) {
		p1 = phead;
		for (p1=phead; p1 && p1 != *iptail; p1 = p1->next) {
			/* Eliminate path segments which are in there already */
			if (p2->src == p1->src && p2->dest == p1->dest) {
				/* Make sure our confidence rules are working */
				pgpAssert (p2->confidence == p1->confidence);
				break;
			}
		}
		if (p1 && p1 != *iptail)
			continue;
		*ptail = pathAlloc(pool);
		if (!*ptail)
			return NULL;
		**ptail = *p2;
		ptail = &(*ptail)->next;
		*ptail = NULL;
	}
	return ptail;
}

/*
 * Calculate the confidence for a list of paths.  We add the confidence for
 * each path, subtrace the confidence for the unions of all pairs of paths,
 * add the confidence for the unions for all the triples, and so on.
 * We actually do this by taking each subset of the paths, unioning them,
 * calculating the confidence for that path, and adding or subtracting it
 * based on the parity.
 */
static double
pathListConfidence (PathList *plist, RingPool *pool)
{
    unsigned        pathcount,
                    mask,
	                tmask;
    PathList       *iplist = plist;
    double          conf = 0.;

#ifdef DEBUGPATH
	fprintf (stdout, "Maurer alg:\n");
#endif

	pathcount = 0;
	while (plist) {
		++pathcount;
		plist = plist->next;
	}
	plist = iplist;

	pgpAssert (pathcount < sizeof(unsigned) * 8);
	for (mask=1; mask < (1U<<pathcount); ++mask) {
		double pathconf;
		Path *phead=NULL, **ptail=&phead;
		int oddparity = 0;
		plist = iplist;
		tmask = mask;
		while (plist && tmask) {
			if (tmask & 1) {