Back to index

wims  3.65+svn20090927
Defines | Functions | Variables
huffman.c File Reference
#include "../Lib/libwims.h"

Go to the source code of this file.

Defines

#define MAX_ITEMS   2048
#define MAX_CODELEN   100
#define MAX_RADIX   strlen(codechar)

Functions

void error (char *msg)
int indcmp (const void *p1, const void *p2)
void huffman (void)
void output (void)
void getparm (char *p)
int main ()

Variables

const char * codechar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
struct {
double prob
int ind
unsigned char code [MAX_CODELEN]
int codelen
maintab [MAX_ITEMS *2]
int itemcnt
int origcnt
int indtab [MAX_ITEMS]
int indcnt
int radix
double entropy
double avelen

Define Documentation

#define MAX_CODELEN   100

Definition at line 34 of file huffman.c.

#define MAX_ITEMS   2048

Definition at line 33 of file huffman.c.

#define MAX_RADIX   strlen(codechar)

Definition at line 37 of file huffman.c.


Function Documentation

void error ( char *  msg)

Definition at line 54 of file huffman.c.

{
    fprintf(stderr,"%s\n",msg);
    printf("ERROR\n");
    exit(1);
}
void getparm ( char *  p)

Definition at line 124 of file huffman.c.

{
    int i;
    char *p1, *p2;
    double d1, dt;

    origcnt=0; dt=0;
    for(p1=find_word_start(p);
       *p1; p1=find_word_start(p2)) {
       for(p2=p1; *p2 && strchr(",;",*p2)==NULL; p2++);
       if(*p2) *p2++=0;
       d1=strevalue(p1);
       if(!finite(d1) || d1<0) {
           char buf[256];
           snprintf(buf,sizeof(buf),"Bad data: %s",p1);
           error(buf);
       }
       maintab[origcnt++].prob=d1;
       dt+=d1;
    }
    if(dt*1000000<1) error("Empty data sum.");
    if(origcnt<2) error("Insufficient data for encoding.");
    itemcnt=origcnt;
    if(dt!=1) for(i=0; i<origcnt; i++) maintab[i].prob/=dt;
    
    entropy=0;
    for(i=0;i<origcnt;i++) {
       maintab[i].codelen=-1; maintab[i].ind=-1;
       indtab[i]=i;
       d1=maintab[i].prob;
       if(d1>0) entropy-=d1*log(d1);
    }
    entropy=entropy/log(radix);
    indcnt=origcnt;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void huffman ( void  )

Definition at line 73 of file huffman.c.

{
    int t, i, j, l;
    double d;
    
    while(indcnt>radix) {
       qsort(indtab,indcnt,sizeof(indtab[0]),indcmp);
       if(radix>2) t=(indcnt+radix-3)%(radix-1)+2;
       else t=2;
       d=0;
       for(i=indcnt-t; i<indcnt; i++) {
           d+=maintab[indtab[i]].prob;
           maintab[indtab[i]].ind=itemcnt;
       }
       maintab[itemcnt].prob=d;
       maintab[itemcnt].ind=-1;
       maintab[itemcnt].codelen=-1;
       indtab[indcnt-t]=itemcnt;
       indcnt-=t-1; itemcnt++;
    }
    for(i=0;i<indcnt;i++) {
       maintab[indtab[i]].codelen=1;
       maintab[indtab[i]].code[0]=i;
       maintab[indtab[i]].ind=0;
    }
    for(i=itemcnt-1;i>=0;i--) {
       if(maintab[i].codelen>0) continue;
       j=maintab[i].ind; l=maintab[j].codelen;
       if(l>=MAX_CODELEN) error("Code too long.");
       memmove(maintab[i].code,maintab[j].code,l);
       maintab[i].code[l]=maintab[j].ind++;
       maintab[i].codelen=l+1;
       maintab[i].ind=0;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int indcmp ( const void *  p1,
const void *  p2 
)

Definition at line 61 of file huffman.c.

{
    const int *i1, *i2;
    double d1, d2;
    
    i1=p1; i2=p2;
    d1=maintab[*i1].prob; d2=maintab[*i2].prob;
    if(d1==d2) return 0;
    if(d1>d2) return -1;
    else return 1;
}

Here is the caller graph for this function:

int main ( void  )

Definition at line 160 of file huffman.c.

{
    char *p;
    int r;
    
    error1=error; error2=error; error3=error;
    p=getenv("w_huffman_radix");
    if(p==NULL || *p==0) p=getenv("huffman_radix");
    if(p==NULL || *p==0) radix=2;
    else {
       r=atoi(p); if(r!=0) radix=r;
    }
    if(radix<2 || radix>MAX_RADIX) error("Bad radix.");
    
    p=getenv("wims_exec_parm");
    if(p==NULL || *p==0) error("No input data.");
    getparm(p);
    
    huffman();
    output();
    
    return 0;
}

Here is the call graph for this function:

void output ( void  )

Definition at line 109 of file huffman.c.

{
    int i, j;
    double d;

    d=0;
    for(i=0;i<origcnt;i++) d+=maintab[i].prob*maintab[i].codelen;
    printf("%f,%f\n",entropy,d);
    for(i=0;i<origcnt;i++) {
       for(j=0;j<maintab[i].codelen;j++) printf("%c",codechar[(int) maintab[i].code[j]]);
       if(i<origcnt-1) printf(",");
       else printf("\n");
    }
}

Variable Documentation

double avelen

Definition at line 52 of file huffman.c.

const char* codechar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

Definition at line 36 of file huffman.c.

double entropy

Definition at line 52 of file huffman.c.

int indcnt

Definition at line 50 of file huffman.c.

Definition at line 49 of file huffman.c.

int itemcnt

Definition at line 47 of file huffman.c.

struct { ... } maintab[MAX_ITEMS*2]
int origcnt

Definition at line 47 of file huffman.c.

int radix

Definition at line 51 of file huffman.c.