huffmanc.c

arm ads1.2 with crack.rar

	unsigned int	treesize ;
	unsigned int	*freqcodelen ;
		
	if( ( freq == NULL ) || ( nfreqs == 0 ) || ( maxcodewlen > MAXCODEBITS ) ) {
		fprintf( stderr, "[Huffman] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		return NULL ;
	}
	
	/*
	find the first non-zero frequency in the array "freq" with data ordered with increasing frequency
	*/
	i = 0 ;
	while( ( freq[ i ] == 0 ) && ( i < nfreqs ) ) {
		i += 1 ;
	}

	/*
	( ( 1 << maxcodewlen ) -1 ) gives the total number of codewords possible which should be at least
	as large as the number of non-zero frequencies that need codewords
	
	this test need not always be true for the coding to still be accomplished but if the test is true
	coding will always be possible, if it fails it may not thus testing ensures that coding will succeed
	*/
	if( ( ( 1 << maxcodewlen ) - 1 ) < ( nfreqs - i ) ) {
		fprintf( stderr, "[Huffman] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		return NULL ;
	}
	
	if( ( tree = MakeHuffmanTree( freq, nfreqs, &treesize ) ) == NULL ) {
		return NULL ;
	}
	
	/* get the frequency of occurrence for each length of codeword */
	if( ( freqcodelen = GetFreqCodeLen( tree, treesize, maxcodewlen ) ) == NULL ) {
		;
	}
	
	free( ( void * ) tree ) ;
	
	return freqcodelen ;
}

/**** MakeHuffmanTree ***************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * generate a binary Huffman tree to create codewords from
 *
 * Inputs
 * ------
 *   freq
 *   - an array of frequency of occurrence for each symbol in the data to be coded
 *     sorted into increasing order of frequency
 *   nfreqs
 *   - the number of frequencies referenced by the array
 *   treesize
 *   - a pointer to an unsigned int to hold the number of entries referenced by the tree
 * Outputs
 * -------
 *   treesize
 *   - the number of nodes referenced by the tree returned
 *     undefined if NULL returned for the tree
 * Return Values
 * ------ ------
 *     TreePtr - the created Huffman tree with *treesize nodes
 *     NULL	   - some error occurred (memory failed?)
 *
 * Memory allocated (not deallocated)
 * ------ ---------  --- -----------
 * the returned tree
 * deallocate after use
 *
 * History (with dates)
 * -------  ---- -----
 * 1.0.0, 30/06/1998    first release
 *
 ************************************************************************************/
static TreePtr MakeHuffmanTree( unsigned int freq[ ], unsigned int nfreqs, unsigned int *treesize )
{
	TreePtr			treeptr ;
	TreePtr			tree ;
	unsigned int	*freqend ;
	TreeNode		node, child ;
	TreePtr			p, parent ;
	unsigned int	i ;
	
	if( ( treesize == NULL ) || ( freq == NULL ) || ( nfreqs == 0 ) ) {
		fprintf( stderr, "[MakeHuffmanTree] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		return NULL ;
	}
	
	/*
	initialise enough space to hold the tree
	
	the tree will have (2*nfreqs - 1) nodes which contain actual tree data, however an extra node is
	used during the tree creation to determine the current final element in the tree
	*/
	if( ( treeptr = ( TreePtr )calloc( nfreqs*2, sizeof( TreeNode ) ) ) == NULL ) {
		fprintf( stderr, "Cannot allocate memory for data, aborting.\n\n" ) ;
		*treesize = -1 ;
		return NULL ;
	}
	*treesize = nfreqs * 2 ;
	
	tree = treeptr ;					/* tree will be incremented whilst creating the tree but need pointer to start */
	
	/*
	find the first non-zero frequency in the array "freq" with data ordered with increasing frequency
	*/
	i = 0 ;
	while( ( freq[ i ] == 0 ) && ( i < nfreqs ) ) {
		i += 1 ;
	}
	
	if( i == nfreqs ) {					/* ensure frequency array contains non-zero frequencies */
		fprintf( stderr, "[MakeHuffmanTree] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		free( ( void * ) treeptr ) ;
		*treesize = -1 ;
		return NULL ;
	}
	
	freqend = freq + nfreqs ;			/* save the end location for the frequency array for termination use */
	
	freq += i ;							/* shift starting address of freq to first non-zero frequency entry */
	
	/*
	shift starting address of tree pointer so that last 2*i entries of array will contain the tree
	with all the entries before this point being zero
	
	the tree will consist of all data with non-zero frequency counts as leaves and for each pair of
	nodes a parent node will be created and thus the tree requires 2*i - 1 nodes where i is the
	number of non-zero frequency count nodes
	*/
	tree += ( i << 1 ) ;		
	
	/*
	initialise parent and p to point to first entry in tree that will contain the first internal node of the
	tree, those entries prior to this point contain the non-zero frequencies as leaves
	*/
	parent = tree + ( nfreqs - i ) ;	/* allow space for non-zero frequencies as first tree elements */
	p = parent ;						/* likewise */

	( *p ).freq = ( unsigned int )-1 ;	/* initialise the last tree entry with default termination values */
	( *p ).nextnode = ( unsigned int )-1 ;
	
	/*
	beginning with first non-zero frequency, terminating when all non-zero frequency elements have been used
	(next element past that referenced by i is read, hence i stops at nfreqs -1), construct the tree
	*/
	for( ; i < nfreqs - 1 ; i += 1 ) {
		/*
		frequencies are ordered so the following test is true if both freq[ 0 ] and freq[ 1 ] are less than parent[ 0 ] thus 
		these two frequencies are the two smallest frequency counts in the tree and should be added to create
		the next parent node
		*/
		if( ( ( freqend - freq ) > 1 ) && ( freq[ 1 ] < parent[ 0 ].freq ) ) {	/* ensure not past end of frequency array */
			node.nextnode = 0 ;
			node.freq = *freq ++ ;
			
			child.nextnode = 0 ;
			child.freq = *freq ++ ;
		}
		/*
		frequencies are ordered so the following test is true if both freq[ 0 ] and freq[ 1 ] are greater than parent[ 0 ] thus
		the two parent nodes (constructed from other frequencies being added) are the two smallest frequency
		counts in the tree and should be added to create the next parent node
		*/
		else if( ( ( freqend - freq ) == 0 ) || ( freq[ 0 ] > parent[ 1 ].freq ) ) {	/* check if last frequency, then always true */
			node = *parent ++ ;
			
			child = *parent ++ ;
		}
		/*
		otherwise it is always true that freq[ 0 ] and parent[ 0 ] are the two smallest frequency counts in the tree
		(although not necessarily uniquely the smallest) and thus these should be added to create the next node
		*/
		else {	/* true for case freqend - freq == 1 as well and the last frequency is not greater than last two parents */
			node.nextnode = 0 ;
			node.freq = *freq ++ ;
			
			child = *parent ++ ;
		}

		*tree ++ = node ;					/* set next two tree node values */
		*tree ++ = child ;
		
		/*
		node now becomes the parent node data 
		*/
		node.freq += child.freq ;			/* set parent nodes frequency as sum of childrens */
		node.nextnode = i << 1 ;			/* set next node entry as accessor to left child belonging to parent */
		*p ++ = node ;						/* set newest internal node for the tree and increment to next tree element */
		if( p - treeptr < *treesize ) {		/* if the tree is incomplete re-initialise the last node reference */
			( *p ).freq = ( unsigned int )-1 ;
			( *p ).nextnode = ( unsigned int )-1 ;
		}
		else {								/* else, tree complete, cease tree construction */
			break ;
		}
	}
	
	return treeptr ;						/* return the constructed tree */
}