pgpgroups.c

vc环境下的pgp源码

/*____________________________________________________________________________
	Copyright (C) 1997 Network Associates Inc. and affiliated companies.
	All rights reserved.
	
	Core groups-handling code.  Does not, and should not have any
	connection to PGPsdk constructs.  Code of that nature belongs
	in pgpGroupsUtil.c.

	$Id: pgpGroups.c,v 1.14.6.1 1999/06/04 18:34:15 heller Exp $
____________________________________________________________________________*/

#include <string.h>

#include "pgpContext.h"
#include "pgpErrors.h"
#include "pgpFileSpec.h"
#include "pgpKeys.h"
#include "pgpMem.h"
#include "pgpFileUtilities.h"
#include "pgpEndianConversion.h"
#include "pgpFileRef.h"

#include "pgpGroups.h"
#include "pgpGroupsPriv.h"
#include "pgpStrings.h"
#include "pgpMemoryIO.h"

#if PGP_MACINTOSH

#include <NumberFormatting.h>
#include "MacStrings.h"

/* because we include sort code twice */
#pragma once off
#endif

/*____________________________________________________________________________
	Notes:
	
	All data structures are in-memory representations.  On disk storage is
	completely different, including ommitting fields, changing the
	endian-ness, etc.
	
	Data structure explanation:
	
	A "group set" is a data structure which contains groups and all the stuff
	they reference.  A group belongs to one and only one set, and whenever
	an operation is performed, the set is required.  Groups are only
	referred to by a PGPGroupID and thus can freely be rearranged internally.
	
	A "group" contains other groups and/or a key ids, in no particular order.
	Each group has an ID, which is unique to the PGPGroupSet which contains
	it.  The key ids are exported key data from the PGPsdk and the data
	is never interpreted, only stored.
	
	These data structures are implemented using arrays. A few notes on this:
	
	1. the goal was rapid, bug-free implementation.  An assumption was made
	that creating large numbers of groups would occur via user-interface
	interaction and that the speed of adding them was not important. In fact,
	adding n groups is an O( n^2 ) operation.  This sounds bad, but in
	practice is irrelevant.  The same holds true for items within a group.
	So DO NOT change the simple implementation unless there is a proven
	reason that speed is a problem in the UI.
	
	2. Reading groups in and writing them out is O( n ).  It can't get any
	faster in the big O sense.
	
	3. PGPGroupIDs are used heavily.  This is perhaps one relevant place
	to optimize, but again, this shouldn't be done unless there is a
	proven issue.  Currently, a linear search is used; a binary search
	could be used, but the reality is that even with a few thousand
	groups (highly unlikely), the speed would probably still be
	reasonable.  The correct way to optimize would be to keep the groups
	sorted by group ID and them implement a binary search.
____________________________________________________________________________*/

typedef struct PGPExportedGroupItem
{
	PGPGroupItemType	type;
	
	union
	{
		/* type selects which substructure */
		struct	/* if kGroupItem_Group */
		{
			PGPGroupID	id;				
		} group;
		
		struct	/* if kGroupItem_KeyID */
		{
			/* exported key IDs currently take 1 + 8 bytes */
			PGPUInt32	algorithm;
			PGPByte		length;		/* actual size of data */
			PGPByte		exportedKeyID[ 8 + 1 ];
		} key;
	} u;
	
} PGPExportedGroupItem;

typedef struct PGPGroup
{
	PGPGroupID			id;
	PGPGroupName		name;
	PGPGroupDescription	description;
	
	/* array of group IDs */
	PGPUInt32			numItems;
	PGPGroupItem *		itemsArray;
	
	/* these items are not stored to disk: */
	PGPGroupSetRef		set;
	PGPUserValue		userValue;
} PGPGroup;


#define kPGPGroupSetMagic	0x47524F55	/* 'GROU */
struct PGPGroupSet
{
	PGPUInt32		magic;
	PGPUInt32		version;
	PGPUInt32		nextAvailGroupID;
	
	char			pad[ 128 ];
	
	/* groupArray is sorted by ascending group ID */
	PGPUInt32		numGroups;
	PGPGroup *		groupArray;
	
	PGPContextRef	context;
	PGPUInt32		lastAccessIndex;
	PGPBoolean		hasBeenModified;
	
};
typedef struct PGPGroupSet	PGPGroupSet;


	
	PGPBoolean
PGPGroupSetIsValid( PGPGroupSetRef set )
{
	PGPBoolean	isValid;
	
	isValid	= IsntNull( set ) &&
				set->magic == kPGPGroupSetMagic;
	
	return( isValid );
}


static PGPError	sSortGroups( PGPGroupSetRef set );


typedef PGPUInt16	CRC16;

	static PGPUInt16
sCalcCRC16Continue(
	PGPUInt16		startValue,
	const void *	data,
	PGPInt32		len)
{
	const char *	dp	= (const char *)data;
	PGPUInt16		crc	= startValue;
	
	while(len--)
	{
		PGPInt16		i;
	
		crc ^= (PGPUInt16)(*dp++) << 8;
		for (i = 0; i < 8; ++i)
		{
			if (crc & 0x8000)
				crc = (crc << 1) ^ 0x1021;
			else
				crc <<= 1;
		}
	}
	return(crc);
}


#define sChecksumBytes( checksum, bytes, numBytes ) \
			sCalcCRC16Continue( checksum, bytes, numBytes )

	static CRC16
sChecksumUInt32(
	CRC16	checksum,
	PGPUInt32		number )
{
	PGPByte	storage[ sizeof( PGPUInt32 ) ];
	
	PGPUInt32ToStorage( number, storage );
	checksum	= sChecksumBytes( checksum, storage, sizeof( PGPUInt32 ) );
	return( checksum );
}


	static CRC16
sComputeGroupChecksum( PGPGroup const * group)
{
	CRC16		checksum	= 0;
	
	/* these assumptions are made when writing out the data */
	pgpAssert( sizeof( group->id ) == sizeof( PGPUInt32 ) &&
		sizeof( group->numItems ) == sizeof( PGPUInt32 ) );
		
	checksum	= sChecksumUInt32( checksum, (PGPUInt32)group->id );
	
	checksum	= sChecksumBytes( checksum,
					group->name, sizeof( group->name ) );
					
	checksum	= sChecksumBytes( checksum,
					group->description, sizeof( group->description ));
					
	checksum	= sChecksumUInt32( checksum, group->numItems );
	
	return( checksum );
}

	static CRC16
sComputeGroupSetChecksum( PGPGroupSet const * set)
{
	CRC16		checksum	= 0;
	
	/* these assumptions are made when writing out the data */
	pgpAssert( sizeof( set->magic ) == sizeof( PGPUInt32 ) &&
		sizeof( set->version ) == sizeof( PGPUInt32 ) &&
		sizeof( set->nextAvailGroupID ) == sizeof( PGPUInt32 ) &&
		sizeof( set->numGroups ) == sizeof( PGPUInt32 ) );
		
	checksum	= sChecksumUInt32( checksum, set->magic );
	checksum	= sChecksumUInt32( checksum, set->version );
	checksum	= sChecksumUInt32( checksum, set->nextAvailGroupID );
	checksum	= sChecksumUInt32( checksum, set->numGroups );
	
	return( checksum );
}


	static CRC16
sComputeExportedGroupItemChecksum( PGPExportedGroupItem const * item)
{
	CRC16		checksum	= 0;
	
	/* these assumptions are made when writing out the data */
	pgpAssert( sizeof( item->type ) == sizeof( PGPUInt32 ) &&
		sizeof( item->u.group.id ) == sizeof( PGPUInt32 ) &&
		sizeof( item->u.key.algorithm ) == sizeof( PGPUInt32 ) &&
		sizeof( item->u.key.length ) == 1 );
		
	checksum	= sChecksumUInt32( checksum, item->type );
	if ( item->type == kPGPGroupItem_Group )
	{
		checksum	= sChecksumUInt32( checksum, item->u.group.id );
	}
	else if ( item->type == kPGPGroupItem_KeyID )
	{
		checksum	= sChecksumUInt32( checksum, item->u.key.algorithm );
		checksum	= sChecksumBytes( checksum, &item->u.key.length, 1 );
		checksum	= sChecksumBytes( checksum,
							item->u.key.exportedKeyID,
							item->u.key.length );
	}
	
	return( checksum );
}




	static PGPError
sReadUInt32FromIO(
	PGPIORef	io,
	PGPUInt32 *	number)
{
	PGPByte		endianBuf[ sizeof( PGPUInt32 ) ];
	PGPError	err;
	
	err	= PGPIORead( io, sizeof( endianBuf ), endianBuf, NULL );
	
	*number	= PGPStorageToUInt32( endianBuf );
	
	return( err );
}


	static PGPError
sReadUInt16FromIO(
	PGPIORef	io,
	PGPUInt16 *	number)
{
	PGPByte		endianBuf[ sizeof( PGPUInt16 ) ];
	PGPError	err;
	
	err	= PGPIORead( io, sizeof( endianBuf ), endianBuf, NULL );
	
	*number	= PGPStorageToUInt16( endianBuf );
	
	return( err );
}

	static PGPError
sWriteUInt32ToIO(
	PGPUInt32	number,
	PGPIORef	io )
{
	PGPByte		endianBuf[ sizeof( PGPUInt32 ) ];
	
	PGPUInt32ToStorage( number, endianBuf );
	return( PGPIOWrite( io, sizeof( endianBuf ), endianBuf ) );
}


	static PGPError
sWriteUInt16ToIO(
	PGPUInt16	number,
	PGPIORef	io )
{
	PGPByte		endianBuf[ sizeof( PGPUInt16 ) ];
	
	PGPUInt16ToStorage( number, endianBuf );
	return( PGPIOWrite( io, sizeof( endianBuf ), endianBuf ) );
}



#define sWriteChecksumToIO( checksum, io ) \
	sWriteUInt16ToIO( checksum, io )

	static PGPError
sVerifyChecksumFromIO(
	CRC16	checksum,
	PGPIORef		io )
{
	CRC16	ioChecksum;
	PGPError		err	= kPGPError_NoErr;
		
	err	= sReadUInt16FromIO( io, &ioChecksum );
	if ( IsntPGPError( err ) && checksum != ioChecksum )
	{
		err	= kPGPError_CorruptData;
	}
	return( err );
}


	static void
sInitGroup(
	PGPGroupSetRef			set,
	PGPGroupID				id,
	const char *			name,
	const char *			description,
	PGPGroup *				group)
{
	pgpClearMemory( group, sizeof( *group ) );
	group->id			= id;
	group->itemsArray	= NULL;
	group->numItems		= 0;
	group->set			= set;
	if ( IsntNull( name ) )
	{
		strcpy( group->name, name );
	}
	if ( IsntNull( description ) )
	{
		strcpy( group->description, description );
	}
}


	static void
sDestroyGroup(
	PGPGroup *				group)
{
	if ( IsntNull( group->itemsArray ) )
	{
		pgpAssert( IsntNull( group->set ) );
		pgpContextMemFree( group->set->context, group->itemsArray );
		group->itemsArray	= NULL;
	}
}


	static PGPError
sNewGroupSet(
	PGPContextRef			context,
	PGPGroupSetRef *		outSet )
{
	PGPError		err	= kPGPError_NoErr;
	PGPGroupSet *	set	= NULL;
	
	set	= (PGPGroupSet *)pgpContextMemAlloc( context,
			sizeof( *set ), kPGPMemoryMgrFlags_Clear );
	if ( IsntNull( set ) )
	{
		set->magic				= kPGPGroupSetMagic;
		set->context			= context;
		set->nextAvailGroupID	= ((PGPUInt32)kPGPInvalidGroupID) + 1;
		set->groupArray			= NULL;
		set->numGroups			= 0;
		set->hasBeenModified	= TRUE;
	}
	else
	{
		err	= kPGPError_OutOfMemory;
	}
	
	*outSet	= set;
	return( err );
}


	static PGPBoolean
sSearchForID(
	PGPGroup const *	firstGroup,
	PGPGroup const *	lastGroup,
	PGPGroupID			id,
	PGPUInt32 *			outIndex )
{
	PGPGroup const *	curGroup;
	PGPBoolean			foundIt	= FALSE;
	
	/* we could use a sentinel value, but if we're that concerned about
	speed we should implement a binary search */
	curGroup	= firstGroup;
	while ( curGroup <= lastGroup )
	{
		if ( curGroup->id == id )
		{
			foundIt	= TRUE;
			*outIndex	= curGroup - firstGroup;
			break;
		}
		++curGroup;
	}
	
	return( foundIt );
}

/*____________________________________________________________________________
	Maybe to be implemented later as a binary search.  But that requires
	making sure all the items are sorted and is probably not worth it.
	
	The algorithm here works well for sequential, forward access.
____________________________________________________________________________*/
	static PGPError
sGetGroupIndexByID(
	PGPGroupSetRef	set,
	PGPGroupID		id,
	PGPUInt32 *		outIndex )
{
	PGPError	err	= kPGPError_ItemNotFound;
	PGPGroup const *	firstGroup;
	PGPGroup const *	lastGroup;
	PGPGroup const *	curGroup;
	PGPBoolean			foundIt	= FALSE;
	PGPUInt32			foundIndex	= 0;
	
	*outIndex	= 0;
	if ( set->numGroups == 0 )
		return( kPGPError_ItemNotFound );

	firstGroup	= &set->groupArray[ 0 ];
	lastGroup	= firstGroup + (set->numGroups - 1 );
	
	if ( set->lastAccessIndex < set->numGroups )
	{
		/* search from last access forward */
		curGroup	= &set->groupArray[ set->lastAccessIndex ];
		if ( sSearchForID( curGroup, lastGroup, id, &foundIndex ) )
		{
			foundIt		= TRUE;
			foundIndex	+= set->lastAccessIndex;
		}
		
		/* search items preceeding last access */
		if ( ( ! foundIt ) && set->lastAccessIndex != 0 )
		{
			foundIt	= sSearchForID( firstGroup,
						curGroup - 1, id, &foundIndex );
		}
	}
	else
	{
		/* search entire array from beginning */
		foundIt	= sSearchForID( firstGroup, lastGroup, id, &foundIndex );
	}
	
	if ( foundIt)
	{
		*outIndex	= foundIndex;
		set->lastAccessIndex	= foundIndex;
		err	= kPGPError_NoErr;
	}
	else
	{
		err	= kPGPError_ItemNotFound;
	}

	return( err );
}



/*____________________________________________________________________________
	to be implemented later as a binary search
____________________________________________________________________________*/
	static PGPError
sFindGroupByID(
	PGPGroupSetRef	set,
	PGPGroupID		id,
	PGPGroup **		outGroup )
{
	PGPError	err	= kPGPError_NoErr;
	PGPUInt32	groupIndex;
	
	err	= sGetGroupIndexByID( set, id, &groupIndex );
	if ( IsntPGPError( err ) )
	{
		*outGroup	= &set->groupArray[ groupIndex ];
	}

	return( err );
}




	PGPContextRef
PGPGetGroupSetContext( PGPGroupSetRef set )
{
	pgpAssert( PGPGroupSetIsValid( set ) );
	if ( ! PGPGroupSetIsValid( set ) )
		return( NULL );
	return( set->context );
}



/*____________________________________________________________________________
	create a new, empty groups collection
____________________________________________________________________________*/
	PGPError
PGPNewGroupSet(
	PGPContextRef		context,
	PGPGroupSetRef *	outRef )
{
	PGPError	err	= kPGPError_NoErr;
	
	PGPValidatePtr( outRef );
	*outRef	= NULL;
	PGPValidateContext( context );
	
	err	= sNewGroupSet( context, outRef );
	
	return( err );
}