huffman.c

压缩算法的C语言源程序

/*
   huffman.c
   Implements the huffman algorithm for gsLib
*/
#include <stdlib.h>
#include <string.h>
#include <compress.h>

#define MAX_BITS 15
static int max_length = MAX_BITS;

/*
   static int HuffSortByLength(const void *a,const void *b):
   The sorter function for use with the qsort function. Sorts a HuffTable by
   length
*/
static int HuffSortByLength(const void *a,const void *b)
{
   return (((HuffTable *)a)->len < ((HuffTable *)b)->len ? -1 :
            (((HuffTable *)a)->len > ((HuffTable *)b)->len ? 1 : 0));
}

/*
   static int HuffSortByCode(const void *a,const void *b):
   The sorter function for use with the qsort function. Sorts a HuffTable by
   code
*/
static int HuffSortByCode(const void *a,const void *b)
{
   return (((HuffTable *)a)->code < ((HuffTable *)b)->code ? -1 :
            (((HuffTable *)a)->code > ((HuffTable *)b)->code ? 1 : 0));
}

/*
   static dword ReverseBits(dword code,int len):
   Reverses the bits of `len' length of the code
*/
static dword ReverseBits(dword code,int len)
{
   register dword bit = 0;

   do {
      bit |= code & 1;
      code >>= 1;
      bit <<= 1;
   } while(--len);

   return bit >> 1;
}

/*
   void CalculateMinimumRedundancy(HuffTable *tab,int n):
   Calculated the minimum bits required to represent each code
   See http://www.cs.mu.oz.au/~alistair/abstracts/wads95.html
*/
void CalculateMinimumRedundancy(HuffTable *tab,int n)
{
	int root, leaf, next, avbl, used, dpth;
	HuffTable *hsave;
	int nsave;

	if(n == 0) return;
	if(n == 1) {
		tab[0].len = 1;
		return;
	}

	qsort(tab,n,sizeof(HuffTable),HuffSortByLength);
	for(used = 0;used < n;used++) if(tab[used].len) break;
	if(used >= n-1) {
		tab[n-1].len = 1;
		qsort(tab,n,sizeof(HuffTable),HuffSortByCode);
		return;
	}

	hsave = tab;
	nsave = n;
	for(;!(*tab).len;tab++,n--);

	tab[0].len += tab[1].len;
	root = 0;
	leaf = 2;

	for(next = 1; next < n-1; next++) {
		if(leaf >= n || tab[root].len < tab[leaf].len) {
			tab[next].len = tab[root].len;
			tab[root++].len = next;
		} else {
			tab[next].len = tab[leaf++].len;
		}

		if(leaf >= n || (root < next && tab[root].len < tab[leaf].len)) {
			tab[next].len += tab[root].len;
			tab[root++].len = next;
		} else {
			tab[next].len += tab[leaf++].len;
		}
	}

	tab[n-2].len = 0;
	for(next = n-3; next >= 0; next--)
		tab[next].len = tab[tab[next].len].len + 1;

	avbl = 1;
	used = dpth = 0;
	root = n-2;
	next = n-1;
	while(avbl > 0) {
		while(root >= 0 && tab[root].len == dpth) {
			used++;
			root--;
		}
		while(avbl > used) {
			tab[next--].len = dpth;
			avbl--;
		}
		avbl = 2*used;
		dpth++;
		used = 0;
	}

	tab = hsave;
	n = nsave;

	qsort(tab,n,sizeof(HuffTable),HuffSortByCode);
}

/*
   void BuildHuffTable(HuffTable *tab,int n):
   Builds huffman codes with respect to their length
   Based on algorithm in the RFC-Deflate document
*/
void BuildHuffTable(HuffTable *tab,int n)
{
   dword code = 0;
	int bits, i, len, overflow = 0;
	int bl_count[MAX_BITS + 1] = {0};
	int next_code[MAX_BITS + 1] = {0};

	// Build length table
	for(i = 0;i < n;i++) {
		if(tab[i].len > max_length) {
			overflow++;
			continue;
		}
		bl_count[tab[i].len]++;
	}

	while(overflow > 0) {
		bits = max_length - 1;
		while(!bl_count[bits] && bits >= 0) bits--;
		for(i = 0;i < n;i++)
			if(tab[i].len == bits) { tab[i].len++; break; }
		for(i = 0;i < n;i++)
			if(tab[i].len > max_length) { tab[i].len = bits+1; break; }
		bl_count[bits]--;
		bl_count[bits+1] += 2;
		overflow--;
	}

	// calculate minimum code values
	bl_count[0] = 0;
	for(bits = 1; bits <= MAX_BITS; bits++) {
		code = (code + bl_count[bits - 1]) << 1;
		next_code[bits] = code;
	}

	for(i = 0; i < n; i++) {
		len = tab[i].len;
		if(len != 0) {
			tab[i].bits = next_code[len];
			next_code[len]++;
		}
	}
}

/*
   HuffLookup *BuildHuffmanLookupTable(HuffTable *tab,int n):
   Generates a lookup table for the FetchHuffmanCode() function
   `tab' is the pointer to a HuffTable struct of huffman codes
*/
HuffLookup *BuildHuffmanLookupTable(HuffTable *tab,int n)
{
   register HuffLookup *lookup; // the lookup table
   int i, j, pos, nexttable = 0, entry;
   dword curcode;
   int curlen;

   lookup = (HuffLookup *)malloc(sizeof(HuffLookup));
   if(!lookup) {
      gerror("Not enough memory for HuffLookup table.");
      THROW (E_MEMORY) return NULL;
   }

   memset(lookup,0,sizeof(HuffLookup));

   for(i = 0; i < n; i++) {
      if(!tab[i].len) continue;

      // if is less than 9-bits
      if(tab[i].len <= 9) {
         // shift to left align
         pos = tab[i].bits << (9 - tab[i].len);
      } else {
         // shift for right alignment
         pos = tab[i].bits >> (tab[i].len - 9);
      }

      pos &= 0x1FF;
      lookup->tablelo[pos].code = tab[i].code; // assign code
      if(tab[i].len > 9) { // if len is > 9, use hi table
         if(lookup->tablelo[pos].len & 0x8000) { // if pos has 0x8000 flaged on
            entry = lookup->tablelo[pos].len & 0x7FFF;
         } else { // otherwise allocate new entry
            lookup->tablehi[nexttable] = malloc(256);
            if(!lookup->tablehi[nexttable]) {
               FreeHuffmanLookupTable(lookup);
               gerror("Not enough memory for lookup table.");
               THROW (E_MEMORY) return NULL;
            }
            memset(lookup->tablehi[nexttable],0,256);
            lookup->tablelo[pos].len = 0x8000 | nexttable; // assign len
            entry = nexttable;
            nexttable++;
         }

         // assign code and length
         lookup->tablehi[entry]
               [(tab[i].bits & ((1 << (tab[i].len - 9)) - 1)) << (15 - tab[i].len)].code = tab[i].code;
         lookup->tablehi[entry]
               [(tab[i].bits & ((1 << (tab[i].len - 9)) - 1)) << (15 - tab[i].len)].len = tab[i].len;
      } else {
         lookup->tablelo[pos].len = tab[i].len; // assign len
      }
   }

   curcode = 0;
   curlen = 0;
   // we duplicate entries throughout the table
   for(i = 0; i < 512; i++) {
      if(lookup->tablelo[i].len) {
         if(lookup->tablelo[i].code != curcode || lookup->tablelo[i].len != curlen) {
            curcode = lookup->tablelo[i].code;
            curlen = lookup->tablelo[i].len;
         }
      }
      lookup->tablelo[i].code = curcode;
      lookup->tablelo[i].len = curlen;
   }

   curcode = 0;
   curlen = 0;
   // duplicate for the hi table
   for(i = 0; i < nexttable; i++) {
      for(j = 0; j < 64; j++) {
         if(lookup->tablehi[i][j].len) {
            if(lookup->tablehi[i][j].code != curcode || lookup->tablehi[i][j].len != curlen) {
               curcode = lookup->tablehi[i][j].code;
               curlen = lookup->tablehi[i][j].len;
            }
         }
         lookup->tablehi[i][j].code = curcode;
         lookup->tablehi[i][j].len = curlen;
      }
   }

   return lookup;
}

/*
   void FreeHuffmanLookupTable(HuffLookup *lookup):
   Frees the memory used by a lookup table
*/
void FreeHuffmanLookupTable(HuffLookup *lookup)
{
   int i;

   for(i = 0; i < 256 && lookup->tablehi[i]; i++) free(lookup->tablehi[i]);
   free(lookup);
}

/*
   dword FetchHuffmanCode(STREAM *fp,HuffLookup *lookup):