hufftesc.c

arm ads1.2 with crack.rar

	printf( "Generating the Huffman encoding table...\n\n" ) ;
	
	switch( datatype ) {
		case BYTEDATA :
			encodeTable = MakeHuffCodeTable8( ( unsigned char * )symbols, nSymbols, freqCodeLen, maxcwlen ) ;
			break ;
		case HWORDDATA :
			encodeTable = MakeHuffCodeTable16( ( unsigned short * )symbols, nSymbols, freqCodeLen, maxcwlen ) ;
			break ;
		case WORDDATA :
			encodeTable = MakeHuffCodeTable32( ( unsigned int * )symbols, nSymbols, freqCodeLen, maxcwlen ) ;
			break ;
		default :
			fprintf( stderr, "[HuffmanEncode] Error in input arguments, aborting.\n\n" ) ;
			encodeTable = NULL ;
	}
	
	if( encodeTable == NULL ) {
		DisposeBitStreamStatePtr( bitStreamStatePtr ) ;
		return NULL ;
	}
	
	printf( "Huffman encoding table generated.\n\n" ) ;
	
	for( i = 0 ; i < nSymbols ; i += 1 ) {
		if( encodeTable[ i ] != 0 ) {
			printf( "symbol 0x" ) ;
			switch( datatype ) {
				case BYTEDATA :
					printf( "%.2x", i ) ;
					break ;
				case HWORDDATA :
					printf( "%.4x", i ) ;
					break ;
				case WORDDATA :
					printf( "%.8x", i ) ;
					break ;
				default :
					break ;
			}
			printf( " has codeword " ) ;
			cwlen = ( encodeTable[ i ] >> MAXCODEBITS ) - 1 ;
			while( cwlen >= 0 ) {
				printf( "%d", ( ( encodeTable[ i ] & ( 1 << cwlen ) ) >> cwlen ) ) ;
				cwlen -= 1 ;
			}
			printf( " (0x%.8x) of length %2d\n", encodeTable[ i ] & ( ( ( unsigned int )0xFFFFFFFF ) >> ( 32 - MAXCODEBITS ) ), encodeTable[ i ] >> MAXCODEBITS ) ;
		}
	}
	printf( "\n" ) ;

	printf( "Huffman encoding the data...\n\n" ) ;
	
	for( i = 0 ; i < CODECSPLIT ; i += 1 ) {
		if( i == CODECSPLIT - 1 ) {
			nCodes = nInputs - ( i * ( nInputs/CODECSPLIT ) ) ;
		}
		else {
			nCodes = nInputs/CODECSPLIT ;
		}
		switch( datatype ) {
			case BYTEDATA :
				bitStreamStatePtr = BitCodeSymbols( ( ( unsigned char * )inputs ) + ( i * ( nInputs/CODECSPLIT ) ), nCodes, bitStreamStatePtr, encodeTable, datatype ) ;
				break ;
			case HWORDDATA :
				bitStreamStatePtr = BitCodeSymbols( ( ( unsigned short * )inputs ) + ( i * ( nInputs/CODECSPLIT ) ), nCodes, bitStreamStatePtr, encodeTable, datatype ) ;
				break ;
			case WORDDATA :
				bitStreamStatePtr = BitCodeSymbols( ( ( unsigned int * )inputs ) + ( i * ( nInputs/CODECSPLIT ) ), nCodes, bitStreamStatePtr, encodeTable, datatype ) ;
				break ;
			default :
				break ;
		}
	}
	
	printf( "Data has been Huffman encoded.\n\n" ) ;
	
	free( ( void * ) encodeTable ) ;
	
	*bitlength = GetNumberBitsInStream( bitStreamStatePtr ) ;
	
	printf( "Coded data in bits = %d, original data in bits = %d, percentage reduction = %d%%\n\n", *bitlength, nInputs*datatype, ( ( nInputs*datatype - *bitlength )*100 )/( nInputs*datatype ) ) ;

	return bitStreamStatePtr ;
}

/**** InitSymbolCount ***************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * create an array of symbol count structures and initialise it with each symbol value and
 * zero count for symbols
 * 
 * Inputs
 * ------
 *   datatype
 *   - the type of the symbols in the data to be counted
 *     BYTEDATA		byte-size data
 *     HWORDDATA 	halfword-size data
 *     WORDDATA		word-size data
 *   maxSymbol
 *   - the maximum symbol value that occurs in the data + 1
 *     the value therefore defines the number of symbols in the data from 0 to maxSymbol
 * Return Values
 * ------ ------
 *     SymbolCountPtr - the created array of symbol count structures
 *     NULL   		  - some error occurred (memory problems?)
 *
 * Memory allocated (not deallocated)
 * ------ ---------  --- -----------
 * the returned array
 * deallocate after use
 *
 * History (with dates)
 * -------  ---- -----
 * 1.0.0, 30/06/1998    first release
 *
 ************************************************************************************/
static SymbolCountPtr InitSymbolCount( unsigned int datatype, unsigned int maxSymbol )
{
	SymbolCountPtr	symbolcountptr ;
	unsigned int	i ;
	
	if( maxSymbol == 0 ) {
		fprintf( stderr, "[InitSymbolCount] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		return NULL ;
	}
	
	if( ( symbolcountptr = ( SymbolCountPtr )calloc( maxSymbol, sizeof( SymbolCount ) ) ) == NULL ) {
		fprintf( stderr, "Cannot allocate memory for data, aborting.\n\n" ) ;
		return NULL ;
	}
	
	printf( "Initialising all possible symbols...\n\n" ) ;
	
	for( i = 0 ; i < maxSymbol ; i += 1 ) {
		symbolcountptr[ i ].count = 0 ;
		switch( datatype ) {
			case BYTEDATA :
				symbolcountptr[ i ].symbol.symboltype = BYTE ;
				symbolcountptr[ i ].symbol.symbol.byte = ( unsigned char )i ;
				break ;
			case HWORDDATA :
				symbolcountptr[ i ].symbol.symboltype = HWORD ;
				symbolcountptr[ i ].symbol.symbol.hword = ( unsigned short )i ;
				break ;
			case WORDDATA :
				symbolcountptr[ i ].symbol.symboltype = WORD ;
				symbolcountptr[ i ].symbol.symbol.word = i ;
				break ;
			default :
				fprintf( stderr, "[InitSymbolCount] Error in input arguments, aborting.\n\n" ) ;
				free( ( void * ) symbolcountptr ) ;
				return NULL ;
		}
	}
	
	printf( "Symbols initialised.\n\n" ) ;
	
	return symbolcountptr ;
}

/**** Menu **************************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * print the menu of options to the screen (defined in standard way for NextTask 
 * function and will be called by NextTask)
 *
 * Inputs
 * ------
 *   numberOptions
 *   - the number of menu options that should be printed
 *
 * History (with dates)
 * -------  ---- -----
 * 1.0.0, 30/06/1998    first release
 *
 ************************************************************************************/
static void Menu( unsigned int numberOptions )
{
	if( numberOptions == HUFFMAN_OPTIONS ) {
		printf( " 1. Huffman encode & decode data of type 'unsigned char'.\n" ) ;
		printf( " 2. Huffman encode & decode data of type 'unsigned short'.\n" ) ;
		printf( " 3. Huffman encode & decode data of type 'unsigned int'.\n" ) ;
	}
	else {
		fprintf( stderr, "[Menu] Error in arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
	}
}

/**** PrepareHuffman ****************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * count the frequency of occurrence of each symbol in the data to be encoded, create
 * an array of all possible symbols, sort this into increasing order of frequency of
 * occurrence and generate frequency of occurrence for each length of codeword 
 * 
 * Inputs
 * ------
 *   inputs
 *   - an array of data that will be encoded
 *     the data is unsigned char, unsigned short or unsigned int determined by datatype
 *   nInputs
 *   - the number of data items from the array to encode
 *   datatype
 *   - the type of the data to be encoded
 *     BYTEDATA		byte-size data
 *     HWORDDATA 	halfword-size data
 *     WORDDATA		word-size data
 *   maxSymbol
 *   - the maximum symbol value that occurs in the data + 1
 *     the value therefore defines the number of symbols in the data from 0 to maxSymbol
 *   maxcodewlen
 *   - the maximum length of codeword that can be created for encoding
 *   symbolsptr
 *   - a pointer to unallocated array to hold the sorted symbols
 * Outputs
 * -------
 *   symbolsptr
 *   - a pointer to an array of symbols sorted into increasing order of frequency of occurrence
 *     with maxSymbol entries
 *     undefined if NULL returned
 * Return Values
 * ------ ------
 *     unsigned int * - a pointer to an array of frequency of occurrence for each length of codeword
 *                      the returned array has (maxcodewlen+1) entries, the first is always zero
 *     NULL           - some error occurred (memory problems?)
 *
 * Memory allocated (not deallocated)
 * ------ ---------  --- -----------
 * the returned array of frequencies for codeword lengths and sorted symbol array
 * deallocate after use
 *
 * History (with dates)
 * -------  ---- -----
 * 1.0.0, 30/06/1998    first release
 *
 ************************************************************************************/
static unsigned int *PrepareHuffman( void *inputs, unsigned int nInputs, unsigned int datatype, unsigned int maxSymbol, unsigned int maxcwlen, void **symbolsptr )
{
	SymbolCountPtr	symbolcountptr ;
	unsigned int	*frequency ;
	unsigned int	i ;
	unsigned int	*freqCodeLen ;
	
	if( ( inputs == NULL ) || ( nInputs == 0 ) || ( maxcwlen == 0 ) || ( maxcwlen > MAXCODEBITS ) || ( symbolsptr == NULL ) ) {
		fprintf( stderr, "[PrepareHuffman] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		return NULL ;
	}
	
	if( ( symbolcountptr = InitSymbolCount( datatype, maxSymbol ) ) == NULL ) {
		return NULL ;
	}

	if( ( frequency = ( unsigned int * )calloc( maxSymbol, sizeof( unsigned int ) ) ) == NULL ) {
		fprintf( stderr, "Cannot allocate memory to hold data, aborting.\n\n" ) ;
		free( ( void * ) symbolcountptr ) ;
		return NULL ;
	}
	
	printf( "Counting the frequency of occurrence for each symbol...\n\n" ) ;
	
	CountSymbols( inputs, nInputs, frequency, 1, datatype ) ;
	
	printf( "Frequency of occurrence for each symbol counted.\n\n" ) ;
	
	for( i = 0 ; i < maxSymbol ; i += 1 ) {
		if( frequency[ i ] != 0 ) {
			printf( "symbol 0x" ) ;
			switch( datatype ) {
				case BYTEDATA :
					printf( "%.2x", i ) ;
					break ;
				case HWORDDATA :
					printf( "%.4x", i ) ;
					break ;
				case WORDDATA :
					printf( "%.8x", i ) ;
					break ;
				default :
					break ;
			}
			printf( " has frequency 0x%.8x\n", frequency[ i ] ) ;
		}
	}
	printf( "\n" ) ;
	printf( "All other possible symbols do not occur and thus have zero frequency.\n\n" ) ;

	printf( "Sorting all possible symbols into ascending order of frequency of occurrence...\n\n" ) ;
	
	for( i = 0 ; i < maxSymbol ; i += 1 ) {
		symbolcountptr[ i ].count = frequency[ i ] ;
	}
	
	qsort( symbolcountptr, maxSymbol, sizeof( SymbolCount ), &SymbolCountSort ) ;
	
	for( i = 0 ; i < maxSymbol ; i += 1 ) {
		frequency[ i ] = symbolcountptr[ i ].count ;
	}
	
	printf( "Symbols have been sorted.\n\n" ) ;
	
	*symbolsptr = GetSymbolsFromSymbolCount( symbolcountptr, maxSymbol ) ;
	free( ( void * ) symbolcountptr ) ;
	if( *symbolsptr == NULL ) {
		free( ( void * ) frequency ) ;
		return NULL ;
	}

	printf( "Generating the frequency for each length of codeword...\n\n" ) ;

	freqCodeLen = Huffman( frequency, maxSymbol, maxcwlen ) ;
	free( ( void * ) frequency ) ;
	if( freqCodeLen == NULL ) {
		return NULL ;
	}
	
	printf( "Frequency of codeword length generated.\n\n" ) ;
	
	for( i = 1 ; i <= maxcwlen ; i += 1 ) { /* can't have codeword of length 0! */
		printf( "number of codewords of length %2d is %d\n", i, freqCodeLen[ i ] ) ;
	}
	printf( "\n" ) ;

	return freqCodeLen ;
}

/**** SymbolCountSort ***************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * sort the current two symbol count structures by increasing count value then for equal
 * count by increasing symbol value
 *
 * define in standard way for C qsort routine
 * 
 * Inputs
 * ------
 *   symbolcount1
 *   - the first symbol count structure (needs casting)
 *   symbolcount2
 *   - the second symbol count structure (needs casting)
 * Return Values
 * ------ ------
 *     1	the first structure is greater than the second
 *     0	the two structures are equal (should never occur since symbols are unique)
 *     -1	the second structure is greater than the first
 *
 * History (with dates)
 * -------  ---- -----
 * 1.0.0, 30/06/1998    first release
 *
 ************************************************************************************/
static int SymbolCountSort( const void *symbolcount1, const void *symbolcount2 )
{
	if( ( *( SymbolCount * )symbolcount1 ).count == ( *( SymbolCount * )symbolcount2 ).count ) {
		switch( ( *( SymbolCount * )symbolcount1 ).symbol.symboltype ) {
			case BYTE :
				if( ( *( SymbolCount * )symbolcount1 ).symbol.symbol.byte == ( *( SymbolCount * )symbolcount2 ).symbol.symbol.byte ) {
					return 0 ;
				}
				else if( ( *( SymbolCount * )symbolcount1 ).symbol.symbol.byte > ( *( SymbolCount * )symbolcount2 ).symbol.symbol.byte ) {
					return 1 ;
				}
				else {
					return -1 ;
				}
			case HWORD :
				if( ( *( SymbolCount * )symbolcount1 ).symbol.symbol.hword == ( *( SymbolCount * )symbolcount2 ).symbol.symbol.hword ) {
					return 0 ;
				}
				else if( ( *( SymbolCount * )symbolcount1 ).symbol.symbol.hword > ( *( SymbolCount * )symbolcount2 ).symbol.symbol.hword ) {
					return 1 ;
				}
				else {
					return -1 ;
				}
			case WORD :
				if( ( *( SymbolCount * )symbolcount1 ).symbol.symbol.word == ( *( SymbolCount * )symbolcount2 ).symbol.symbol.word ) {
					return 0 ;
				}
				else if( ( *( SymbolCount * )symbolcount1 ).symbol.symbol.word > ( *( SymbolCount * )symbolcount2 ).symbol.symbol.word ) {
					return 1 ;
				}
				else {
					return -1 ;
				}
			default :
				return 0 ;
		}
	}
	else if( ( *( SymbolCount * )symbolcount1 ).count > ( *( SymbolCount * )symbolcount2 ).count ) {
		return 1 ;
	}
	else {
		return -1 ;
	}
}