wpchuff.c

su 的源代码库

/* Copyright (c) Colorado School of Mines, 2006.*/
/* All rights reserved.                       */


/* WPCHUFF: $Revision: 1.3 $ ; $Date: 1997/01/10 22:28:41 $	*/

/*********************** self documentation **********************/
/**************************************************************************
WPCHUFF -Routines for in memory Huffman coding/decoding

huffCompress - huffman compress a byte stream in a memory buffer and output 
		the bit stream into another memory buffer
huffDecompress - decompress a huffman coded bit stream in a memory buffer and 
		output the byte stream into another memory buffer   

***************************************************************************
Function Prototypes:
int huffCompress(void *inb, void *outb)
int huffDecompress(void *inb, void *outb)

***************************************************************************
huffCompress:
Input:
inb	buffer holding the input byte stream 
Output:
outb	buffer holding the output bit stream

huffDecompres:
inb	buffer holding the input bit stream 
outb	buffer holding the output byte stream

***************************************************************************
Note:
The algorithm is based on that in Mark Nelson's "Data 
Compression" book. The compression is performed in memory here.

***************************************************************************
Author:		Tong Chen, 08/01/94
**************************************************************************/
/**************** end self doc ********************************/

#include "wpc.h"
#include "wpclib.h"
#include "wpcbuffer.h"
#include "wpcbitbuff.h"

/* definitions used internally */ 
typedef struct huffNodeStruct {
        unsigned int count;
        unsigned int saved_count;
        int child_0;
        int child_1;
} huffNODE;	/* one node in a Huffman tree */


typedef struct huffCodeStruct {
        unsigned int code;
        int code_bits;
} huffCODE;	/* one Huffman code */


#define HUFFNSYMBOL 256
#define HUFFNCODE (HUFFNSYMBOL) + 1 
#define HUFFNNODE 2*(HUFFNCODE) 
#define HUFFENDOFBLK 256
#define HUFFRUNMIN 3
#define HUFFTERM 0
#define HUFFMAXCOUNT 255

/* routines used internally */
void huffCountbytes (wpcBUFF *buff, unsigned int *counts);
void huffScalecounts(unsigned int *counts, huffNODE *nodes);
int huffBuildtree (huffNODE *nodes);
void huffConverttreetocode (huffNODE *nodes, huffCODE *codes,
        unsigned int code_so_far, int bits, int node);
int huffOutputcounts(wpcBITBUFF *bit_buff, huffNODE *nodes);
int huffInputcounts(wpcBITBUFF *bit_buff, huffNODE *nodes);
int huffEncoder(wpcBUFF *buff, wpcBITBUFF *bit_buff, huffCODE *codes);
int huffDecoder(wpcBITBUFF *bit_buff, wpcBUFF *buff,
        huffNODE *nodes, int root_node);


int huffCompress(void *inb, void *outb)
/*************************************************************************
static huffman coding
**************************************************************************
inb	buffer holding the input byte stream 
outb	buffer holding the output bit stream
*************************************************************************/
{
	wpcBUFF *inbuff = (wpcBUFF *)inb;
	wpcBUFF *outbuff = (wpcBUFF *)outb;
	unsigned int *counts;	
	huffNODE *nodes;
	huffCODE *codes;
	int root_node;
	int nbytes=0, retval;
	wpcBITBUFF *bit_buff;

/*
fprintf(stderr,"in Huffman\n");
*/

	/* initialize the bit buffer */
	bitInitbuff(bit_buff, outbuff);
	
	/* allocate and init spaces for hit counts, and tree */
	counts = (unsigned int *) calloc(HUFFNSYMBOL,sizeof(unsigned int));
	nodes = (huffNODE *) calloc (HUFFNNODE,sizeof(huffNODE));
	codes = (huffCODE *) calloc (HUFFNCODE,sizeof(huffCODE));

	/* hit counts of the input symbols */
	huffCountbytes(inbuff, counts);

	/* scale the hit counts to hold them in one byte */
	huffScalecounts(counts, nodes);


	/* save the counts */
	retval = huffOutputcounts(bit_buff, nodes);
/*
	retval = 0;
*/

	if(retval != WPC_EOB){

	    nbytes = retval; 

	    /* build the huffman tree */
	    root_node = huffBuildtree(nodes);


	    /* convert the tree to codes */
	    huffConverttreetocode(nodes, codes, 0, 0, root_node);

	    /* huffman encoding */
	    retval = huffEncoder(inbuff, bit_buff, codes);

	    if(retval != WPC_EOB){
		nbytes += retval;

		bitWindbuff(bit_buff, retval);

	    	if(retval != WPC_EOB) nbytes += retval;
	    }
	}

	/* free the spaces */
	bitFreebuff(bit_buff);

	free((void *) counts);
	free((void *) nodes);
	free((void *) codes);

	return (retval == WPC_EOB? retval : nbytes);
}


int huffDecompress(void *inb, void *outb)
/*************************************************************************
static huffman decoding
**************************************************************************
inb	buffer holding the input bit stream 
outb	buffer holding the output byte stream
*************************************************************************/
{
	wpcBUFF *inbuff = (wpcBUFF *) inb;
	wpcBUFF *outbuff = (wpcBUFF *) outb;
	huffNODE *nodes;
	int root_node;
	wpcBITBUFF *bit_buff;

	/* initialize the bit buffer */
	bitInitbuff(bit_buff, inbuff);

	/* space for the Huffman tree */
	nodes = (huffNODE *) calloc (HUFFNNODE,sizeof(huffNODE));

	/* input the hit counts */
	if(huffInputcounts(bit_buff, nodes) == WPC_EOB) 
		return WPC_EOB;

	/* build the Huffman tree */
	root_node = huffBuildtree(nodes);

	/* decoding */
	if(huffDecoder(bit_buff, outbuff, nodes, root_node) == WPC_EOB)
		return WPC_EOB;

	/* free the spaces */
	bitFreebuff(bit_buff);

	free((void *) nodes);

	return 0;
}


int huffOutputcounts (wpcBITBUFF *bit_buff, huffNODE *nodes)
/*************************************************************************
output the hit count table to the output buffer 
**************************************************************************
bit_buff	buffer holding the encoded bit stream
nodes		array[] of nodes hold the leaves (the symbols) of the
		Huffman tree 
**************************************************************************
Note:	All the side information needed for decoding is this hit count table,
	from which the Huffman tree that is neede for decoding can be built. 
	To reduce the overhead of the hit count table, a simplified 
	runlength coding is used. It contains the first and last symbols 
	in the run, followed by the hit counts of each symbol. The last
	symbol HUFFTERM is used as the terminator. Only runs longer than 
	HUFFRUNMIN is treated this way. 
*************************************************************************/
{
	int first, last, next, i;
	int nbytes = 0;

	/* the first symbol in a run */
	first = 0;
	while(first < (HUFFNSYMBOL-1) && nodes[first].count ==0) first ++;

	for(; first < HUFFNSYMBOL; first=next){

	    /* find the last symbol in this run and the first symbol of the
	     next run */
	    last = first + 1;
	    for (; ; ){
		for(; last < HUFFNSYMBOL; last ++)
		    if(nodes[last].count == 0) break;
		last -- ;
		for(next = last + 1; next < HUFFNSYMBOL; next ++)
		    if(nodes[next].count != 0) break;
		if(next > (HUFFNSYMBOL-1)) break;
		if((next - last) > HUFFRUNMIN) break;

		last = next;
	    }

	   /* output the first, last and hit counts */
	   if(buffPutc(bit_buff->buff, first) == WPC_EOB)
		return WPC_EOB;
	   nbytes ++;

	   if(buffPutc(bit_buff->buff, last) == WPC_EOB)
		return WPC_EOB;
	   nbytes ++;

	   for(i=first; i<=last; i++){ 
		if(buffPutc(bit_buff->buff, nodes[i].count) == WPC_EOB)
		    return WPC_EOB;
	  	nbytes ++;
	    }
	}

	/* output the terminator for the end of count table */
	if(buffPutc(bit_buff->buff, HUFFTERM) == WPC_EOB)
	    return WPC_EOB;
	nbytes ++;