pgprngpriv.c

vc环境下的pgp源码

			mask->nwords = minwords;
		}
	}
	return kPGPError_NoErr;
}

PGPError
pgpVirtMaskOR (RingPool const *pool, PGPVirtMask const *imask,
	PGPVirtMask *omask)
{
	PGPError err;
	PGPUInt32 i;

	err = pgpVirtMaskSizeUp (pool, omask, imask->nwords);
	if (IsPGPError (err))
		return err;
	for (i=0; i<pgpMin(imask->nwords, omask->nwords); ++i)
		omask->words[i] |= imask->words[i];
	return kPGPError_NoErr;
}

PGPError
pgpVirtMaskAND (RingPool const *pool, PGPVirtMask const *imask,
	PGPVirtMask *omask)
{
	PGPUInt32 i;

	(void)pool;
	for (i=0; i<pgpMin(imask->nwords, omask->nwords); ++i)
		omask->words[i] &= imask->words[i];
	for ( ; i<omask->nwords; ++i)
		omask->words[i] = 0;
	return kPGPError_NoErr;

}

PGPError
pgpVirtMaskANDNOT (RingPool const *pool, PGPVirtMask const *imask,
	PGPVirtMask *omask)
{
	PGPUInt32 i;

	(void)pool;
	for (i=0; i<pgpMin(imask->nwords, omask->nwords); ++i)
		omask->words[i] &= ~imask->words[i];
	return kPGPError_NoErr;

}

PGPError
pgpVirtMaskSetBit (RingPool const *pool, PGPVirtMask *mask,
	PGPUInt32 bitnumber)
{
	PGPUInt32 bitword;
	PGPError err;

	bitword = bitnumber / 32;
	err = pgpVirtMaskSizeUp (pool, mask, bitword + 1);
	if (IsPGPError(err))
		return err;
	mask->words[bitword] |= 1 << (bitnumber % 32);
	return kPGPError_NoErr;
}

PGPError
pgpVirtMaskClearBit (RingPool const *pool, PGPVirtMask *mask,
	PGPUInt32 bitnumber)
{
	PGPUInt32 bitword;

	(void) pool;
	bitword = bitnumber / 32;
	if (bitword < mask->nwords)
		mask->words[bitword] &= ~ (1 << (bitnumber % 32) );
	return kPGPError_NoErr;
}

PGPError
pgpVirtMaskClearGreaterBits (RingPool const *pool, PGPVirtMask *mask,
	PGPUInt32 firstbitnumber)
{
	PGPUInt32 bitword;

	(void) pool;
	bitword = firstbitnumber / 32;
	if (bitword < mask->nwords)
		mask->words[bitword] &= (1 << (firstbitnumber % 32) ) - 1;
	for (++bitword; bitword < mask->nwords; ++bitword) {
		mask->words[bitword] = 0;
	}
	return kPGPError_NoErr;
}

/* Complements a mask up to one less than the specified number of bits */
PGPError
pgpVirtMaskNOT (RingPool const *pool, PGPVirtMask *mask,
	PGPUInt32 highbitnumber)
{
	PGPUInt32 highbitword;
	PGPUInt32 i;
	PGPError err;

	highbitword = highbitnumber / 32;
	err = pgpVirtMaskSizeUp (pool, mask, highbitword + 1);
	if (IsPGPError(err))
		return err;
	for (i=0; i<highbitword; ++i)
		mask->words[i] = ~mask->words[i];
	mask->words[highbitword] = ((1 << (highbitnumber % 32)) - 1) &
								~mask->words[highbitword];
	return kPGPError_NoErr;
}
	

PGPError
pgpVirtMaskCopy (RingPool const *pool, PGPVirtMask const *imask,
	PGPVirtMask *omask)
{
	PGPError err;
	PGPUInt32 i;

	err = pgpVirtMaskSizeUp (pool, omask, imask->nwords);
	if (IsPGPError (err))
		return err;
	for (i=0; i<imask->nwords; ++i)
		omask->words[i] = imask->words[i];
	for ( ; i<omask->nwords; ++i)
		omask->words[i] = 0;
	return kPGPError_NoErr;
}

PGPInt32
pgpVirtMaskLSBit (PGPVirtMask const *mask)
{
	PGPUInt32 i;

	for (i=0; i<mask->nwords; ++i) {
		if (mask->words[i])
			return 32*i + ringLsBitFind (mask->words[i]);
	}
	return -1;
}

PGPBoolean
pgpVirtMaskIsEmpty (PGPVirtMask const *mask)
{
	PGPUInt32 i;

	for (i=0; i<mask->nwords; ++i)
		if (mask->words[i])
		return FALSE;
	return TRUE;
}

PGPBoolean
pgpVirtMaskIsEqual (PGPVirtMask const *mask1, PGPVirtMask const *mask2)
{
	PGPUInt32 i;

	/* First compare common length portion */
	for (i=0; i<pgpMin(mask1->nwords, mask2->nwords); ++i)
		if (mask1->words[i] != mask2->words[i])
			return FALSE;
	/* The excess must be all zeros */
	if (mask1->nwords < mask2->nwords) {
		for ( ; i < mask2->nwords; ++i)
			if (mask2->words[i])
				return FALSE;
	} else {
		for ( ; i < mask1->nwords; ++i)
			if (mask1->words[i])
				return FALSE;
	}
	return TRUE;
}

PGPBoolean
pgpVirtMaskIsOverlapping (PGPVirtMask const *mask1, PGPVirtMask const *mask2)
{
	PGPUInt32 i;

	for (i=0; i<pgpMin(mask1->nwords, mask2->nwords); ++i)
		if (mask1->words[i] & mask2->words[i])
			return TRUE;
	return FALSE;
}

#endif /* VIRTMASK */


/*
 * Small helpers to report errors
 */
/* Report an general I/O error */
void
ringErr(RingFile *file, PGPUInt32 pos, PGPError code)
{
	RingError *err = &file->set.pool->e;

	err->f = file;
	err->fpos = pos;
	err->error = code;
	err->syserrno = errno;
}

/* Report a non-I/O error */
void
ringSimpleErr(RingPool *pool, PGPError code)
{
	pool->e.f = (RingFile *)NULL;
	pool->e.fpos = (PGPUInt32)-1;
	pool->e.error = code;
	pool->e.syserrno = errno;
}

/* Report an allocation failure (called from many places) */
void
ringAllocErr(RingPool *pool)
{
	ringSimpleErr(pool, kPGPError_OutOfMemory);
}

/*
 * Hash a string of bytes.  Uses the CRC-32 polynomial, preset
 * to -1, non-invert.  Used to reduce userID collisions and to
 * create a fake keyID for unparseable keys.
 *
 * CRC-32 polynomial in little-endian order:
 *   1+x+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32
 *               1   1   2   2   2   3
 *   0   4   8   2   6   0   4   8   2
 * = 111011011011100010000011001000001
 * =    e   d   b   8   8   3   2   0
 * = 0xedb88320
 */
#define CRCPOLY 0xedb88320
PGPUInt32
ringHashBuf(PGPByte const *buf, size_t len)
{
	PGPUInt32 crc;
	int i, j;
	static PGPUInt32 crctable[256];

	if (!crctable[255]) {
		/* crctable[0] is already 0 */
		crctable[128] = crc = CRCPOLY;
		i = 64;
		do {
			crc = crc>>1 ^ (crc & 1 ? CRCPOLY : 0);
			for (j = 0; j < 256; j += 2*i)
				crctable[i+j] = crc ^ crctable[j];
		} while (i >>= 1);
	}

	crc = 0xffffffff;
	while (len--)
		crc = (crc >> 8) ^ crctable[(crc ^ *buf++) & 255];
	return crc;
}

/*
 * Return the index of the least significant bit in the given mask,
 * or -1 if the mask is all 0.  This uses (almost) no branches,
 * so should be nice and fast on modern processors.
 *
 * Oh, how does it *work*, you ask?  I do confess that this uses
 * two evil bit-twiddling tricks.  The first is one to get a mask
 * of the least-significant set bit in few instructions.
 * Consider a binary number x, be it 11010000 or 00101111.
 * Then think about the form of x-1, 11001111 or 00101110.
 * Notice that the only difference is that some least-significant
 * bits have been complemented.  The bits complemented are
 * those up to and including the least-significant set bit.
 * (x+1 does the same with *clear* bits).  So ANDing the two
 * results in a number like the original, only without the
 * least-significant set bit.  XORing them produces a mask
 * with a number of least-significant bits set, depending on
 * the least-significant set bit,    00011111 or 00000001.
 *
 * Other tricks: x & (x-1) returns x, but with the least-significant
 * bit cleared.  Twos complement negation is -x = ~x+1 = ~(x-1),
 * so x & -x = x & ~(x-1) returns only the least-significant bit
 * set in x.
 *
 * All we need is a routine to count the bits, and we're done.
 * This is the *second* trick.  Consider an 8-bit word:
 * +-+-+-+-+-+-+-+-+
 * |a|b|c|d|e|f|g|h|
 * +-+-+-+-+-+-+-+-+
 * Now copy this word, shift one copy down one bit, and AND both
 * copies with 0x55 (01010101), to produce even and odd bits:
 * +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
 * | |b| |d| |f| |h|  | |a| |c| |e| |g| (the blank squares are zero)
 * +-+-+-+-+-+-+-+-+  +-+-+-+-+-+-+-+-+
 * Then add the words together:
 * +-+-+-+-+-+-+-+-+
 * |a+b|c+d|e+f|g+h|
 * +-+-+-+-+-+-+-+-+
 * Note that each two-bit field contains a count of the number of
 * bits set in that part of the original word.  Repeating this produces:
 * +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+
 * |   |c+d|   |g+h| + |   |a+b|   |e+f| = |a+b+c+d|e+f+g+h|
 * +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+
 * and once more produces:
 * +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+
 * |       |e+f+g+h| + |       |a+b+c+d| = |a+b+c+d+e+f+g+h|
 * +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+   +-+-+-+-+-+-+-+-+
 *
 * Ther masking is needed so that fields don't overflow into
 * adjacent fields.  Once the fields have gotten wide enough,
 * some of it can be reduced or eliminated.  In the last step,
 * ab+c+d and e+f+g+h are both at most 4 (binary 100) and
 * their sum is at most 8 (binary 1000), which still fits into a
 * 4-bit field, so it is possible to not mask the inputs to
 * the addition.  It's still necessary to mask the output, though,
 * since the next step (adding up to a maximum of 16) won't
 * fit into a 4-bit field.  Once you have an 8-bit field, though,
 * you can stop masking until the very end unless you have a
 * 256-bit word.
 */
#define SIZEOFMASK	32
int
ringLsBitFind(PGPUInt32 mask)
{
	if (!mask)
		return -1;
	mask ^= mask-1;	/* Number of bits set is position of lsbit + 1 */
#if SIZEOFMASK > 32
	mask = (mask & 0x5555555555555555) + (mask >> 1 & 0x5555555555555555);
	mask = (mask & 0x3333333333333333) + (mask >> 2 & 0x3333333333333333);
	mask = (mask + (mask >> 4)) & 0x0F0F0F0F0F0F0F0F;
	mask += mask >> 8;
	mask += mask >> 16;
	mask += mask >> 32;
	return (int)(mask & 255)-1;
#elif SIZEOFMASK > 16
	mask = (mask & 0x55555555) + (mask >> 1 & 0x55555555);
	mask = (mask & 0x33333333) + (mask >> 2 & 0x33333333);
	mask = (mask + (mask >> 4)) & 0x0F0F0F0F;
	mask += mask >> 8;
	mask += mask >> 16;
	return (int)(mask & 255)-1;
#elif SIZEOFMASK > 8
	mask = (mask & 0x5555) + (mask >> 1 & 0x5555);
	mask = (mask & 0x3333) + (mask >> 2 & 0x3333);
	mask = (mask + (mask >> 4)) & 0x0F0F;
	mask += mask >> 8;
	return (int)(mask & 255)-1;
#else
	mask = (mask & 0x55) + (mask >> 1 & 0x55);
	mask = (mask & 0x33) + (mask >> 2 & 0x33);
	mask = (mask + (mask >> 4)) & 0x0F;
	return (int)(mask - 1);
#endif
}

/*
 * Return in *omask the mask of bits which are actually in use, excepting the
 * given RingSet, if non-null.  I.e. the mask which would be in use
 * if that RingSet were discarded.  RingFile structures are not
 * included on the sets list, so they are accounted for in the
 * pool->filemask.
 */
PGPError
ringAllocMask(RingPool const *pool, RingSet const *set0,
			  PGPVirtMask *omask)
{
	RingSet const *set;
	PGPVirtMask mask;
	PGPError err = kPGPError_NoErr;

	if (IsPGPError(err = pgpVirtMaskCleanup (pool, omask)))
		return err;
	if (IsPGPError(err = pgpVirtMaskInit (pool, &mask)))
		return err;
	if (IsPGPError(err = pgpVirtMaskCopy (pool, &pool->filemask, &mask)))
		return err;

	for (set = pool->sets; set; set = set->next) {
		if (IsPGPError( err =
				pgpVirtMaskOR (pool, &set->mask, &mask)))
			return err;
	}
	if (set0) {		/* set0 may or may not be on the sets list */
		if (IsPGPError( err =
				pgpVirtMaskANDNOT (pool, &set0->mask, &mask)))
			return err;
	}
	*omask = mask;
	/* No cleanup on mask since it is copied to the output */
	return err;
}

/* Helper function for ringGarbageCollect */
PGPError
ringClearMask(RingPool *pool, union RingObject **objp, PGPVirtMask *andmask,
			  PGPVirtMask *andnotmask, PGPVirtMask *omask)
{
	union RingObject *robj;
	PGPVirtMask objmask;
	PGPVirtMask remmask;
	PGPVirtMask tmpmask;
	PGPError err = kPGPError_NoErr;

	if (IsPGPError( err = pgpVirtMaskInit (pool, &objmask) ) )
		goto error;
	if (IsPGPError( err = pgpVirtMaskInit (pool, &remmask) ) )
		goto error;
	if (IsPGPError( err = pgpVirtMaskInit (pool, &tmpmask) ) )
		goto error;
	while ((robj = *objp) != (union RingObject *) 0) {
		if (IsntNull(andmask) &&
			IsPGPError( err =
				pgpVirtMaskAND (pool, andmask, &robj->g.mask) ) )
			goto error;
		if (IsntNull(andnotmask) &&
			IsPGPError( err =
				pgpVirtMaskANDNOT (pool, andnotmask, &robj->g.mask) ) )
			goto error;
		if (IsPGPError( err =
				pgpVirtMaskCopy (pool, &robj->g.mask, &objmask) ) )
			goto error;
	    if (!OBJISBOT(robj)) {
			if (IsPGPError( err = 
				ringClearMask (pool, &robj->g.down, andmask,
							   andnotmask, &tmpmask) ) )
				goto error;
			if (IsPGPError( err =
					pgpVirtMaskOR (pool, &tmpmask, &remmask) ) )
				goto error;
		}
	    /*  Skip dummy objects (robj->g.mask == 0), but delete
	        objects that are only in the memory ring. Also skip
			keys which must be kept as dummy keys (because they've
			signed something). */
		if (!pgpVirtMaskIsEmpty(&robj->g.mask)) {
			if (IsPGPError( err =
					pgpVirtMaskCopy(pool, &objmask, &tmpmask) ) )
				goto error;
			if (IsPGPError( err =
					pgpVirtMaskANDNOT(pool, &pool->memringmask, &tmpmask) ) )
				goto error;
			if (pgpVirtMaskIsEmpty (&tmpmask)) {
				/* Therefore object is ONLY on MEMRING */
				if (!(OBJISTOPKEY(robj) && robj->k.sigsby != NULL)) {
					/* Also object hasn't made any sigs */
					/*
					 * Delete no-longer-used object.
					 * This does not free the memring data area, however
					 * it will be reclaimed in ringGarbageCollect once no
					 * objects are using that area.
					 */
					pgpAssert(OBJISBOT(robj) || !robj->g.down);
					*objp = robj->g.next;
					ringFreeObject(pool, robj);
					continue;
				}