huffgen.c

speech signal process tools

/*
 ********************************************************************************
 *
 *  This material contains proprietary software of Entropic Speech, Inc.
 *  Any reproduction, distribution, or publication without the the prior
 *  written permission of Entropic Speech, Inc. is strictly prohibited.
 *  Any public distribution of copies of this work authorized in writing
 *  by Entropic Speech, Inc. must bear the notice:
 *
 *     "Copyright (c) 1987 Entropic Speech, Inc.; all rights reserved"
 *
 *  Program: huffgen
 *
 *  Written by: Jim Elliott
 *
 *  Computes Huffman code tables for type and extension fields, and for
 *  quantized power, pulse length, and spectral parameters.
 *
 ********************************************************************************
 */

/*
 *  SCCS program and date keywords.
 */

#ifndef lint
static char *sccs_id = "@(#)huffgen.c	1.3	11/25/87 ESI";
#endif

/*
 *  System include files.
 */

#include <math.h>
#include <stdio.h>

/*
 *  ESPS include files.
 */

#include <esps/esps.h>
#include <esps/fea.h>
#include <esps/feahuff.h>
#include <esps/feaqhist.h>

/*
 *  Defines.
 */

#define ERROR_EXIT( text ) \
{ \
    Fprintf( stderr, "huffgen: %s - exiting\n", text ); \
    exit( 1 ); \
}

#define SYNTAX USAGE( "huffgen -h hist_file infile.fea outfile.fea" )

/*
 *  System functions and variables.
 */

char *ctime(), *strcpy();
int getopt(), strcmp();
long time();
void exit(), perror();
extern optind;
extern char *optarg;

/*
 *  ESPS functions and variables.
 */

char *get_cmd_line();

/*
 *  Internal functions and variables.
 */

struct tnode *alloc_node(), *combine(), *insert();

/*
 ********************************************************************************
 *  Main program.
 ********************************************************************************
 */

main( argc, argv )

char *argv[];
int argc;
{
    char
	*cmd_line,		/* String for command line */
	*date = "11/25/87",
	*hfn = "huffgen.his",	/* History file name */
	*ifn = NULL,		/* Input file name */
	*ofn = NULL,		/* Output file name */
	*version = "1.3";

    FILE
	*hfp = NULL,		/* History file pointer */
	*ifp = stdin,		/* Input file pointer */
	*ofp = stdout;		/* Output file pointer */

    int
	c,			/* For getopt() return */
	done = NO,		/* Flag for EOF */
	first = 0,		/* First element of circular buffer */
	i,			/* Loop variable */
	last;			/* Last element of circular buffer */

    struct auxqhist
        *auxqhist_rec[ MAX_TBLSIZ ];	/* Auxiliary FEA_QHIST buffer */

    struct feaqhist
	*feaqhist_rec[ MAX_TBLSIZ ];	/* FEA_QHIST record buffer */

    struct header
	*ih,			/* Input file header */
	*oh;			/* Output file header */

    struct tnode
	*p0,			/* Pointer to lightest node */
	*pf;			/* Pointer to first input node */

/*
 *  Read command line and process command line options.
 */

    cmd_line = get_cmd_line( argc, argv );

    while ( ( c = getopt( argc, argv, "h:" ) ) != EOF )
    {
	switch ( c )
	{
	    case 'h':
	        hfn = optarg;
		break;

	    default:
	        SYNTAX;
	}
    }

/*
 *  Process file arguments.
 */

    if ( optind < argc )
    {
	ifn = argv[ optind++ ];
	if ( strcmp( ifn, "-" ) == 0 )
	    ifn = "<stdin>";
	else
	    TRYOPEN( argv[0], ifn, "r", ifp );
    }

    else
    {
	Fprintf( stderr, "huffgen: No input file specified\n" );
	SYNTAX;
    }

    if ( optind < argc )
    {
	ofn = argv[ optind++ ];
	if ( strcmp( ofn, "-" ) == 0 )
	    ofn = "<stdout>";
	else
	    TRYOPEN( argv[0], ofn, "w", ofp );
    }

    else
    {
	Fprintf( stderr, "huffgen: No output file specified\n" );
	SYNTAX;
    }

    TRYOPEN( argv[0], hfn, "w", hfp );

/*
 *  Read and check values from header of input file.
 */

    if ( ( ih = read_header( ifp ) ) == NULL )
        NOTSPS( argv[0], ifn );

    if ( ih->common.type != FT_FEA )
        ERROR_EXIT( "Input file is not a FEA file" );

    if ( ih->hd.fea->fea_type != FEA_QHIST )
        ERROR_EXIT( "Input file is not FEA_QHIST type" );

/*
 *  Create header for output file.
 */

    oh = copy_header( ih );
    add_source_file( oh, ifn, ih );

    (void) strcpy( oh->common.prog, "huffgen" );
    (void) strcpy( oh->common.vers, version );
    (void) strcpy( oh->common.progdate, date );

    add_comment( oh, cmd_line );

/*
 *  Add auxiliary record fields, then write the header.
 */

    if ( init_auxqhist_hd( oh ) )
        ERROR_EXIT( "Error filling auxiliary FEA_QHIST header" )

    write_header( oh, ofp );

/*
 *  Allocate storage. Note that the *OUTPUT* header pointer is used -- this
 *  is safe, as long as the call to init_auxqhist_hd() is made *AFTER* the call
 *  to copy_header(), when the output header is set up.
 */

    for ( i = 0; i < MAX_TBLSIZ; i++ )
    {
	feaqhist_rec[i] = allo_feaqhist_rec( oh );
	auxqhist_rec[i] = allo_auxqhist_rec( oh, feaqhist_rec[i] );
    }

/*
 *  This is the main loop, executed once for each Huffman table.
 */

    while ( !done )
    {
	p0 = pf = NULL;

	fill_buffer( &first, &last, &done, feaqhist_rec, ifp, ih );
	assign_links( first, last, feaqhist_rec, &p0, &pf );

    /*
     *  Reject the degenerate case with all zeros in the histogram.
     */

	if ( p0 == NULL )
	    ERROR_EXIT( "Histogram has all zeros" );

    /*
     *  Combine nodes by weight until the root of the Huffman tree is
     *  reached.
     */

	while ( p0->heavier != p0 )
	    p0 = combine( p0 );

    /*
     *  Generate Huffman codes and code lengths by recursive assignment
     *  of values, beginning at the root. A tree with a single node is
     *  handled as a special case.
     */

	if ( p0->upper == NULL )
	{
	    p0->code = 1;
	    p0->length = 1;
	}

	else
	    assign_codes( p0, 0, 0 );

    /*
     *  Output data records and statistics.
     */

	output_table( first, last, pf, auxqhist_rec, feaqhist_rec, oh, ofp, hfp,
	    ifn, ofn, version, date );
    }

    exit( 0 );
}

/*
 ********************************************************************************
 *  Subroutine to fill the circular buffer associated with one set of input
 *  statistics.
 ********************************************************************************
 */

fill_buffer( first, last, done, feaqhist_rec, ifp, ih )

FILE *ifp;
int *done, *first, *last;
struct feaqhist *feaqhist_rec[];
struct header *ih;
{
    int
	i,			/* Loop variable */
	test;			/* Test flag for EOF */

    static int
	next = NONE;		/* First element for next table */

    static short
	type = NONE,		/* Histogram record type */
	next_type = NONE;	/* Type of next histogram */

/*
 *  Set up the pointers to the circular record buffer. On the first occasion,
 *  we must read an input record to start the process.
 */

    if ( type == NONE )
    {
        if ( get_feaqhist_rec( feaqhist_rec[*first], ih, ifp ) == EOF )
	    ERROR_EXIT( "No data records in input file" );

        type = *feaqhist_rec[*first]->hist_type;
    }

    else
    {
        *first = next;
        type = next_type;
    }

    i = *first;

    do
    {
        i++;
        if ( i == MAX_TBLSIZ )
            i = 0;

        test = get_feaqhist_rec( feaqhist_rec[i], ih, ifp );

        next_type = *feaqhist_rec[i]->hist_type;
    }
    while ( test != EOF && next_type == type );

    if ( test == EOF )
        *done = YES;

    next = i;
    *last = i - 1;
    if ( *last < 0 )
        *last = MAX_TBLSIZ - 1;
}

/*
 ********************************************************************************
 *  Subroutine to read records from circular buffer, store word values and
 *  weights, and assign "later" links according to sequence of input. Also add
 *  nodes to the linked list, corresponding to weights.
 ********************************************************************************
 */

assign_links( first, last, feaqhist_rec, p0, pf )

int first, last;
struct feaqhist *feaqhist_rec[];
struct tnode **p0, **pf;
{
    int
	i;			/* Loop variable */

    struct tnode
	*p,			/* Scratch pointer */
	*pp;			/* Another one */

    i = first;

    for (;;)
    {
        p = alloc_node();

        p->word = *feaqhist_rec[i]->value;
        p->weight = *feaqhist_rec[i]->count;

        if ( *pf == NULL )
	    *pf = pp = p;

        else
        {
	    pp->later = p;
	    pp = p;
        }

        *p0 = insert( *p0, p );

        if ( i == last )
            break;

        i++;
        if ( i == MAX_TBLSIZ )
            i = 0;
    }
}

/*
 ********************************************************************************
 *  Subroutine to insert a pointer in a linked list of pointers. The insertion
 *  is made ahead of the element having equal or greater weight.
 ********************************************************************************
 */

struct tnode
*insert( p0, p )

struct tnode *p0, *p;
{
    struct tnode
	*pl,			/* Pointer to lighter node */
	*ph;			/* Pointer to heavier node */

/*
 *  If the weight is zero, return p0 unchanged. This prevents zero-weight
 *  nodes from being added to the Huffman tree.
 */

    if ( p->weight == 0 )
        return( p0 );

/*
 *  If this is the first entry, p0 will be a NULL pointer: link p with itself,
 *  and copy p to p0.
 */

    if ( p0 == NULL )
    {
	p->heavier = p;
	p0 = p;
	return( p0 );
    }

/*
 *  Insert the entry in the list: if equal to an element already on the list,
 *  the insertion is prior to the existing element; otherwise, the insertion
 *  is between the elements which bracket the new entry.
 */

    pl = NULL;
    ph = p0;
    while ( p->weight > ph->weight )
    {
	pl = ph;
	ph = ph->heavier;
	if ( pl == ph )
	    break;
    }

/*
 *  Special treatment is required if p is to be inserted at the beginning of
 *  the list (pl = NULL), or at the end of the list (pl = ph).
 */

    if ( pl == NULL )		/* Beginning */
    {
	p->heavier = ph;
	p0 = p;
    }

    else if ( pl == ph )	/* End */
    {
	pl->heavier = p;
	p->heavier = p;
    }

    else			/* Middle */
    {
	pl->heavier = p;
	p->heavier = ph;
    }

    return( p0 );
}

/*
 ********************************************************************************
 *  Subroutine to combine two nodes of the Huffman tree. A new node is
 *  created, and inserted in the linked list, according to its weight.
 ********************************************************************************
 */

struct tnode
*combine( p0 )

struct tnode *p0;
{
    struct tnode *p;

    p = alloc_node();

    p->weight = p0->weight + p0->heavier->weight;
    p->upper = p0;
    p->lower = p0->heavier;

    if ( p0->heavier->heavier != p0->heavier )
    {
	p0 = p0->heavier->heavier;
	p0 = insert( p0, p );
    }

    else
    {
	p0 = p;
	p0->heavier = p0;
    }

    return( p0 );
}

/*
 ********************************************************************************
 *  Subroutine to assign Huffman code words and compute code lengths. The
 *  routine calls itself recursively, until the end of a branch is reached.
 ********************************************************************************
 */

assign_codes( p, c, l )

int c, l;
struct tnode *p;
{
    p->code = c;
    p->length = l;

    if ( p->upper != NULL )
    {
        assign_codes( p->upper, 2*p->code + 0, p->length + 1 );
        assign_codes( p->lower, 2*p->code + 1, p->length + 1 );
    }
}

/*
 ********************************************************************************
 *  Subroutine to allocate storage for a node in the Huffman tree.
 ********************************************************************************
 */

struct tnode
*alloc_node()
{
    char *calloc();

    return( ( struct tnode * ) calloc( 1, sizeof( struct tnode ) ) );
}

/*
 ********************************************************************************
 *  Subroutine to output data records and statistcs for a single Huffman
 *  table.
 ********************************************************************************
 */

output_table( first, last, pf, auxqhist_rec, feaqhist_rec, oh, ofp, hfp,
    ifn, ofn, version, date )

char *date, *ifn, *ofn, *version;
FILE *hfp, *ofp;
int first, last;
struct auxqhist *auxqhist_rec[];
struct feaqhist *feaqhist_rec[];
struct header *oh;
struct tnode *pf;
{
    int
	i;			/* Loop variable */

    float
	avg = 0.0,		/* Average bits per codeword */
	ent = 0.0,		/* Entropy */
	wgt = 0.0;		/* Probability */

    long
	tloc;			/* For date and time */

    struct tnode
	*p;			/* Scratch pointer */

    static char
	init = YES;		/* Flag for initial call */

    p = pf;
    i = first;

    for(;;)
    {
	*auxqhist_rec[i]->code = p->code;
	*auxqhist_rec[i]->length = p->length;

	wgt += p->weight;
	avg += p->weight * p->length;

	if ( p->weight )
	    ent += p->weight * log ( (double) p->weight );

	put_feaqhist_rec( feaqhist_rec[i], oh, ofp );

	if ( i == last )
	    break;

	i++;
	if ( i == MAX_TBLSIZ )
	    i = 0;

	p = p->later;
    }

    ent = log( (double) wgt ) - ent / wgt;
    ent /= log( 2.0 );

    avg /= wgt;

    if ( init )
    {
	init = NO;

	tloc = time( 0 );

	Fprintf( hfp, "Huffgen statistics output on %s", ctime( &tloc ) );
	Fprintf( hfp, "Huffgen version %s, date %s\n\n", version, date );

	Fprintf( hfp, "Input file: %s\n", ifn );
	Fprintf( hfp, "Output file: %s\n\n", ofn );

	Fprintf( hfp, "Huffman table combinations:\n\n" );
	Fprintf( hfp, "\tFrequency: %s\n",
	    noyes[ *(short *) get_genhd( "comb_frq", oh ) ] );
	Fprintf( hfp, "\tVoicing: %s\n\n",
	    noyes[ *(short *) get_genhd( "comb_vcg", oh ) ] );

	Fprintf( hfp, "Continuous coding options:\n\n" );
	Fprintf( hfp, "\tPower: %s\n",
	    noyes[ *(short *) get_genhd( "cont_pwr", oh ) ] );
	Fprintf( hfp, "\tSpectrum: %s\n\n",
	    noyes[ *(short *) get_genhd( "cont_spc", oh ) ] );
    }

    Fprintf( hfp, "Huffman Table for %s:\n",
	hist_types[ *feaqhist_rec[last]->hist_type ] );

    Fprintf( hfp, "Entropy: %6.3f\n", ent );
    Fprintf( hfp, "Average bits/word: %6.3f\n\n", avg );
}