hufftesc.c

arm ads1.2 with crack.rar

/*
 * Huffman test harness
 * Copyright (C) ARM Limited 1998-1999. All rights reserved.
 */

#include <ctype.h>
#include <stdlib.h>

#include "hufftesc.h"

#include "bitcodes.h"
#include "bitdcods.h"
#include "bstreamc.h"
#include "counts.h"
#include "huffmanc.h"
#include "makct8c.h"
#ifdef	_MAKE_CT_C_
	#undef	_MAKE_CT_C_	/* undefine makctc.h against multiple inclusion */
#endif
#ifdef	MCTPROTOTYPE
	#undef	MCTPROTOTYPE	/* undefine prototype for next inclusion */
#endif
#ifdef	MCTFUNCTIONDECLARATION
	#undef	MCTFUNCTIONDECLARATION	/* undefine declaration for next inclusion */
#endif
#include "makct16c.h"
#ifdef	_MAKE_CT_C_
	#undef	_MAKE_CT_C_	/* undefine makctc.h against multiple inclusion */
#endif
#ifdef	MCTPROTOTYPE
	#undef	MCTPROTOTYPE	/* undefine prototype for next inclusion */
#endif
#ifdef	MCTFUNCTIONDECLARATION
	#undef	MCTFUNCTIONDECLARATION	/* undefine declaration for next inclusion */
#endif
#include "makct32c.h"
#include "mkdct8c.h"
#ifdef	_MAKE_DCT_C_
	#undef	_MAKE_DCT_C_	/* undefine makctc.h against multiple inclusion */
#endif
#ifdef	MDCTPROTOTYPE
	#undef	MDCTPROTOTYPE	/* undefine prototype for next inclusion */
#endif
#ifdef	MDCTFUNCTIONDECLARATION
	#undef	MDCTFUNCTIONDECLARATION	/* undefine declaration for next inclusion */
#endif
#include "mkdct16c.h"
#ifdef	_MAKE_DCT_C_
	#undef	_MAKE_DCT_C_	/* undefine makctc.h against multiple inclusion */
#endif
#ifdef	MDCTPROTOTYPE
	#undef	MDCTPROTOTYPE	/* undefine prototype for next inclusion */
#endif
#ifdef	MDCTFUNCTIONDECLARATION
	#undef	MDCTFUNCTIONDECLARATION	/* undefine declaration for next inclusion */
#endif
#include "mkdct32c.h"

#include "custredc.h"
#include "definesc.h"
#include "fileutlc.h"
#include "optionsc.h"
#include "printinc.h"

#define	HUFFMAN_OPTIONS	3

/* this defines the number of times Bit(De)CodeSymbols will be called for encoding/decoding to prove this feature */
#ifndef CODECSPLIT
	#define CODECSPLIT	11
#endif	/* CODECSPLIT */

/* the maximum length of codeword in bits that will be looked up in table for decoding - rest are tree-decoded */
#ifndef TABLEBITS
	#define	TABLEBITS	10
#endif	/* TABLEBITS */

/*
define maximum number of Fibonacci terms in the data
maximum possible Fibonacci value with 20-bits of data is F27 = 317811 with 832039 total entries
*/
#ifndef MAXFIBTERMS
	#define MAXFIBTERMS		28
#endif	/* MAXFIBTERMS */

/* maximum possible Fibonacci value in 8-bit data is F12 = 233 with 609 total entries (10-bits of data) */
#ifndef MAXFIB8TERMS
	#define MAXFIB8TERMS	13
#endif	/* MAXFIB8TERMS */

/* maximum possible Fibonacci value in 16-bit data is F23 = 46368 with 121392 total entries (17-bits of data) */
#ifndef MAXFIB16TERMS
	#define MAXFIB16TERMS	24
#endif	/* MAXFIB16TERMS */

/* define symbol union - only one symbol type will exist at any time */
typedef union	SymbolUnion	SymbolUnion ;
typedef			SymbolUnion	*SymbolUnionPtr ;

union SymbolUnion {
	unsigned char	byte ;
	unsigned short	hword ;
	unsigned int	word ;
} ;

/* define a symbol as structure of union (actual symbol) and identifier tag to determine symbol type */
typedef struct	Symbol		Symbol ;
typedef			Symbol		*SymbolPtr ;

typedef enum{ BYTE, HWORD, WORD } SymbolType ;

struct Symbol {
	SymbolType	symboltype ;
	SymbolUnion	symbol ;
} ;

/* set up symbol with frequency count structure */
typedef struct	SymbolCount	SymbolCount ;
typedef			SymbolCount	*SymbolCountPtr ;

struct SymbolCount {
	unsigned int	count ;
	Symbol			symbol ;
} ;

static void *CreateFibonacci( unsigned int datatype, unsigned int *n ) ;
static void *HuffmanDecode( void *symbols, unsigned int nSymbols, unsigned int nInputs, BitStreamStatePtr encodedBitStreamDataPtr, unsigned int datatype, unsigned int freqCodeLen[ ], unsigned int maxcwlen ) ;
static BitStreamStatePtr HuffmanEncode( void *inputs, unsigned int nInputs, void *symbols, unsigned int nSymbols, unsigned int datatype, unsigned int freqCodeLen[ ], unsigned int maxcwlen, unsigned int *bitlength ) ;
static void Menu( unsigned int numberOptions ) ;
static unsigned int *PrepareHuffman( void *inputs, unsigned int nInputs, unsigned int datatype, unsigned int maxSymbol, unsigned int maxcwlen, void **symbolsptr ) ;
static int SymbolCountSort( const void *symbolcount1, const void *symbolcount2 ) ;

/**** Code **************************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * obtains a set of data from user (either from test file or Fibonacci data created
 * in this routine), Huffman encodes it, Huffman decodes this immediately and compares
 * the results
 *
 * the decoded data is also written to a file if decoding was successful
 *
 * Inputs
 * ------
 *   option
 *   - a value that should be between 1 and 3 and returned from a call to NextTask
 *     the value corresponds to a menu choice and determines the type of data to be
 *     Huffman encoded/decoded
 *     1 = byte data
 *     2 = half word data
 *     3 = word data
 * Return Values
 * ------ ------
 *     TRUE  - the entire coding process was successful and data written
 *     FALSE - some error occurred during process (memory problems?)
 *
 * History (with dates)
 * -------  ---- -----
 * 1.0.0, 30/06/1998    first release
 *
 ************************************************************************************/
static Boolean Code( unsigned int option )
{
	void				*inputs = NULL ;
	unsigned int		nInputs ;
	unsigned int		datatype ;
	unsigned int		isFib ;
	unsigned int		maxSymbol ;
	unsigned int		*freqCodeLen ;
	void				*symbols ;
	BitStreamStatePtr	encodedBitStreamStatePtr ;
	unsigned int		encodedBitLength ;
	void				*decoded ;
	unsigned int		i ;
	Boolean				failed ;

	printf( "Perform Huffman encoding and decoding...\n\n" ) ;
	
	datatype = 8 << ( option - 1 ) ;
	
	isFib = YesNo( "Huffman encode/decode on a set of Fibonacci data", "Fibonacci", "open test file" ) ;
	switch( isFib ) {
		case 0 :
        	if( ( inputs = GetData( datatype/8, "input", &nInputs ) ) == NULL ) {
        		return FALSE ;
        	}
       		break ;
		case 1 :
        	if( ( inputs = CreateFibonacci( datatype, &nInputs ) ) == NULL ) {
        		return FALSE ;
        	}
        	break ;
		default :
			break ;
	}
	
	printf( "Number of data items for Huffman encoding/decoding is '%d'\n\n", nInputs ) ;
	
	printf( "Determining the maximum symbol value in data...\n\n" ) ;
	
	maxSymbol = 0 ;
	for( i = 0 ; i < nInputs ; i += 1 ) {
		switch( datatype ) {
			case BYTEDATA :
				maxSymbol = MAX( maxSymbol, ( unsigned int )( ( ( unsigned char * )inputs )[ i ] ) ) ;
				break ;
			case HWORDDATA :
				maxSymbol = MAX( maxSymbol, ( unsigned int )( ( ( unsigned short * )inputs )[ i ] ) ) ;
				break ;
			case WORDDATA :
				maxSymbol = MAX( maxSymbol, ( unsigned int )( ( ( unsigned int * )inputs )[ i ] ) ) ;
				break ;
			default :
				break ;
		}
	}
	
	printf( "The maximum symbol value in the input data is 0x" ) ;
	switch( datatype ) {
		case BYTEDATA :
			printf( "%.2x", maxSymbol ) ;
			break ;
		case HWORDDATA :
			printf( "%.4x", maxSymbol ) ;
			break ;
		case WORDDATA :
			printf( "%.8x", maxSymbol ) ;
			break ;
		default :
			break ;
	}
	printf( "\n\n" ) ;
	
	maxSymbol += 1 ;
	
	if( ( freqCodeLen = PrepareHuffman( inputs, nInputs, datatype, maxSymbol, MAXCODEBITS, &symbols ) ) == NULL ) {
		free( inputs ) ;
		return FALSE ;
	}

	encodedBitStreamStatePtr = HuffmanEncode( inputs, nInputs, symbols, maxSymbol, datatype, freqCodeLen, MAXCODEBITS, &encodedBitLength ) ;
	if( !encodedBitStreamStatePtr ) {
		free( inputs ) ;
		free( freqCodeLen ) ;
		free( symbols ) ;
		return FALSE ;
	}
	
	decoded = HuffmanDecode( symbols, maxSymbol, nInputs, encodedBitStreamStatePtr, datatype, freqCodeLen, MAXCODEBITS ) ;

	free( freqCodeLen ) ;
	free( symbols ) ;
	free( encodedBitStreamStatePtr ) ;
	if( !decoded ) {
		free( inputs ) ;
		return FALSE ;
	}

	printf( "Comparing the data input to the Huffam encoder and the data output from the Huffman decoder...\n\n" );
	
	failed = FALSE ;
	for( i = 0 ; i < nInputs ; i += 1 ) {
		switch( datatype ) {
			case BYTEDATA :
				if( ( ( unsigned char * )inputs )[ i ] != ( ( unsigned char * )decoded )[ i ] ) {
					printf( "error in output %d: original value 0x%.2x, retrieved value 0x%.2x\n", i, ( ( unsigned char * )inputs )[ i ], ( ( unsigned char * )decoded )[ i ] ) ;
					failed = TRUE ;
				}
				break ;
			case HWORDDATA :
				if( ( ( unsigned short * )inputs )[ i ] != ( ( unsigned short * )decoded )[ i ] ) {
					printf( "error in output %d: original value 0x%.4x, retrieved value 0x%.4x\n", i, ( ( unsigned short * )inputs )[ i ], ( ( unsigned short * )decoded )[ i ] ) ;
					failed = TRUE ;
				}
				break ;
			case WORDDATA :
				if( ( ( unsigned int * )inputs )[ i ] != ( ( unsigned int * )decoded )[ i ] ) {
					printf( "error in output %d: original value 0x%.8x, retrieved value 0x%.8x\n", i, ( ( unsigned int * )inputs )[ i ], ( ( unsigned int * )decoded )[ i ] ) ;
					failed = TRUE ;
				}
				break ;
			default :
				break ;
		}
	}
	
	if( !failed ) {
		printf( "The input and output data are equal.\n\n" ) ;
		
		if( ( !isFib ) || ( isFib && YesNo( "Do you want to save the Fibonacci data", "save Fibonacci", "don't save Fibonacci" ) ) ) {
			SaveData( decoded, nInputs, datatype/8, 1, "decoded" ) ;
		}
	}
	else {
		printf( "\n" ) ;
		printf( "Errors occurred in Huffman encoding/decoding the data.\n\n" ) ;
	}
	
	free( inputs ) ;
	free( decoded ) ;
	
	if( !failed ) {
		return FALSE ;
	}
	else {
		return TRUE ;
	}
}

/**** CreateFibonacci ***************************************************************
 *
 * Version & Date
 * -------   ----
 * 1.0.0, 30/06/1998
 *
 * Description
 * -----------
 * create a set of Fibonacci data such that for each Fibonacci value, it is placed
 * into the data array as many times as its value e.g. F4 = 5 has five array entries
 * 
 * Inputs
 * ------
 *   datatype
 *   - the type of data to create
 *     BYTEDATA		create byte-size data
 *     HWORDDATA 	create halfword-size data
 *     WORDDATA		create word-size data
 *   n
 *   - pointer to unsigned int to hold the number of data items created
 * Outputs
 * -------
 *   n
 *   - pointer to unsigned int that defines number of data items referenced by array returned
 *     undefined if NULL returned
 * Return Values
 * ------ ------
 *     void * - the created array of data
 *              array is unsigned char, unsigned short or unsigned int data according to value 
 *              of datatype and needs casting to appropriate type before it can be used
 *     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 void *CreateFibonacci( unsigned int datatype, unsigned int *n )
{
	void			*fib ;
	unsigned int	fibn, fibn1 ;
	unsigned int	maxfibterms ;
	unsigned int	fibterms ;
	unsigned int	i, j ;
	
	if( n == NULL ) {
		fprintf( stderr, "[CreateFibonacci] Error in input arguments, aborting.\n\n" ) ;
		/* function name given since intended as internal error for programmer */
		return NULL ;
	}
	
	printf( "Please give the number of Fibonacci terms in the data.\n\n" ) ;
	
	switch( datatype ) {
		case BYTEDATA :
			maxfibterms = MAXFIB8TERMS ;
			break ;
		case HWORDDATA :
			maxfibterms = MAXFIB16TERMS ;
			break ;
		case WORDDATA :
			maxfibterms = MAXFIBTERMS ;
			break ;
		default :
			fprintf( stderr, "[CreateFibonacci] Error in input arguments, aborting.\n\n" ) ;
			/* function name given since intended as internal error for programmer */
			return NULL ;
	}
	
	do {
		printf( "Number of of Fibonacci terms (2 to %d) : ", maxfibterms ) ;
		fibterms = ( int )ReadDouble( ) ;
		if( ( fibterms < 2 ) || ( fibterms > maxfibterms ) ) {
			printf( "'%d' is outside of the valid Fibonacci range, please choose again.\n\n", fibterms ) ;
		}
		else {
			break ;
		}
	} while( 1 ) ;
	
	if( fibterms < 17 ) {
		*n = ( 1 << ( fibterms - ( ( fibterms + 1 )/3 ) + 1 ) ) ;
	}
	else {
		*n = ( 1 << ( fibterms - ( fibterms/3 ) + 2 ) ) ;
	}
	
	printf( "Creating Fibonacci sequence...\n\n" ) ;
	
	if( ( fib = calloc( *n, datatype/8 ) ) == NULL ) {
		fprintf( stderr, "Cannot allocate memory for data, aborting.\n\n" ) ;
		return NULL ;
	}
	
	switch( datatype ) {
		case BYTEDATA :
			( ( unsigned char * )fib )[ 0 ] = ( ( unsigned char * )fib )[ 1 ] = 1 ;
			break ;
		case HWORDDATA :
			( ( unsigned short * )fib )[ 0 ] = ( ( unsigned short * )fib )[ 1 ] = 1 ;
			break ;
		case WORDDATA :
			( ( unsigned int * )fib )[ 0 ] = ( ( unsigned int * )fib )[ 1 ] = 1 ;
			break ;
		default :
			free( fib ) ;