WebSVN – wimsdev – Diff – /trunk/wims/src/Misc/huffman.c

 #define MAX_RADIX strlen(codechar)
 #include "../Lib/libwims.h"
 struct {
-    double prob;
+  double prob;
-    int ind;
+  int ind;
-    unsigned char code[MAX_CODELEN];
+  unsigned char code[MAX_CODELEN];
-    int codelen;
+  int codelen;
 } maintab[MAX_ITEMS*2];
 int itemcnt, origcnt;
 int indtab[MAX_ITEMS];
 int indcnt;
 double entropy, avelen;
 int indcmp(const void *p1, const void *p2)
+{
-    const int *i1, *i2;
+  const int *i1, *i2;
-    double d1, d2;
+  double d1, d2;
-    i1=p1; i2=p2;
+  i1=p1; i2=p2;
-    d1=maintab[*i1].prob; d2=maintab[*i2].prob;
+  d1=maintab[*i1].prob; d2=maintab[*i2].prob;
-    if(d1==d2) return 0;
+  if(d1==d2) return 0;
-    if(d1>d2) return -1;
+  if(d1>d2) return -1;
-    else return 1;
+  else return 1;
+}
 void huffman(void)
+{
-    int t, i, j, l;
+  int t, i, j, l;
-    double d;
+  double d;
-    while(indcnt>radix) {
+  while(indcnt>radix) {
-      qsort(indtab,indcnt,sizeof(indtab[0]),indcmp);
+    qsort(indtab,indcnt,sizeof(indtab[0]),indcmp);
-      if(radix>2) t=(indcnt+radix-3)%(radix-1)+2;
+    if(radix>2) t=(indcnt+radix-3)%(radix-1)+2;
-      else t=2;
+    else t=2;
-      d=0;
+    d=0;
-      for(i=indcnt-t; i<indcnt; i++) {
+    for(i=indcnt-t; i<indcnt; i++) {
-          d+=maintab[indtab[i]].prob;
+      d+=maintab[indtab[i]].prob;
-          maintab[indtab[i]].ind=itemcnt;
+      maintab[indtab[i]].ind=itemcnt;
-      }
+    }
-      maintab[itemcnt].prob=d;
+    maintab[itemcnt].prob=d;
-      maintab[itemcnt].ind=-1;
+    maintab[itemcnt].ind=-1;
-      maintab[itemcnt].codelen=-1;
+    maintab[itemcnt].codelen=-1;
-      indtab[indcnt-t]=itemcnt;
+    indtab[indcnt-t]=itemcnt;
-      indcnt-=t-1; itemcnt++;
+    indcnt-=t-1; itemcnt++;
-    }
+  }
-    for(i=0;i<indcnt;i++) {
+  for(i=0;i<indcnt;i++) {
-      maintab[indtab[i]].codelen=1;
+    maintab[indtab[i]].codelen=1;
-      maintab[indtab[i]].code[0]=i;
+    maintab[indtab[i]].code[0]=i;
-      maintab[indtab[i]].ind=0;
+    maintab[indtab[i]].ind=0;
-    }
+  }
-    for(i=itemcnt-1;i>=0;i--) {
+  for(i=itemcnt-1;i>=0;i--) {
-      if(maintab[i].codelen>0) continue;
+    if(maintab[i].codelen>0) continue;
-      j=maintab[i].ind; l=maintab[j].codelen;
+    j=maintab[i].ind; l=maintab[j].codelen;
-      if(l>=MAX_CODELEN) error("Code too long.");
+    if(l>=MAX_CODELEN) error("Code too long.");
-      memmove(maintab[i].code,maintab[j].code,l);
+    memmove(maintab[i].code,maintab[j].code,l);
-      maintab[i].code[l]=maintab[j].ind++;
+    maintab[i].code[l]=maintab[j].ind++;
-      maintab[i].codelen=l+1;
+    maintab[i].codelen=l+1;
-      maintab[i].ind=0;
+    maintab[i].ind=0;
-    }
+  }
 }
 void output(void)
+{
-    int i, j;
+  int i, j;
-    double d;
+  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");
+  }
+}
+void getparm(char *p)
+{
+  int i;
+  char *p1, *p2;
+  double d1, dt;
-    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");
-    }
-}
-void getparm(char *p)
-{
-    int i;
-    char *p1, *p2;
-    double d1, dt;
-    origcnt=0; dt=0;
+  origcnt=0; dt=0;
-    for(p1=find_word_start(p);
+  for(p1=find_word_start(p);
       *p1; p1=find_word_start(p2)) {
-      for(p2=p1; *p2 && strchr(",;",*p2)==NULL; p2++);
+    for(p2=p1; *p2 && strchr(",;",*p2)==NULL; p2++);
-      if(*p2) *p2++=0;
+    if(*p2) *p2++=0;
-      d1=strevalue(p1);
+    d1=strevalue(p1);
-      if(!isfinite(d1) || d1<0) {
+    if(!isfinite(d1) || d1<0) {
-          char buf[256];
+      char buf[256];
-          snprintf(buf,sizeof(buf),"Bad data: %s",p1);
+      snprintf(buf,sizeof(buf),"Bad data: %s",p1);
-          error(buf);
+      error(buf);
-      }
+    }
-      maintab[origcnt++].prob=d1;
+    maintab[origcnt++].prob=d1;
-      dt+=d1;
+    dt+=d1;
-    }
+  }
-    if(dt*1000000<1) error("Empty data sum.");
+  if(dt*1000000<1) error("Empty data sum.");
-    if(origcnt<2) error("Insufficient data for encoding.");
+  if(origcnt<2) error("Insufficient data for encoding.");
-    itemcnt=origcnt;
+  itemcnt=origcnt;
-    if(dt!=1) for(i=0; i<origcnt; i++) maintab[i].prob/=dt;
+  if(dt!=1) for(i=0; i<origcnt; i++) maintab[i].prob/=dt;
-    entropy=0;
+  entropy=0;
-    for(i=0;i<origcnt;i++) {
+  for(i=0;i<origcnt;i++) {
-      maintab[i].codelen=-1; maintab[i].ind=-1;
+    maintab[i].codelen=-1; maintab[i].ind=-1;
-      indtab[i]=i;
+    indtab[i]=i;
-      d1=maintab[i].prob;
+    d1=maintab[i].prob;
-      if(d1>0) entropy-=d1*log(d1);
+    if(d1>0) entropy-=d1*log(d1);
-    }
+  }
-    entropy=entropy/log(radix);
+  entropy=entropy/log(radix);
-    indcnt=origcnt;
+  indcnt=origcnt;
+}
 int main()
+{
-    char *p;
+  char *p;
-    int r;
+  int r;
-    p=getenv("w_huffman_radix");
+  p=getenv("w_huffman_radix");
-    if(p==NULL || *p==0) p=getenv("huffman_radix");
+  if(p==NULL || *p==0) p=getenv("huffman_radix");
-    if(p==NULL || *p==0) radix=2;
+  if(p==NULL || *p==0) radix=2;
-    else {
+  else {
-      r=atoi(p); if(r!=0) radix=r;
+    r=atoi(p); if(r!=0) radix=r;
-    }
+  }
-    if(radix<2 || radix>MAX_RADIX) error("Bad radix.");
+  if(radix<2 || radix>MAX_RADIX) error("Bad radix.");
-    p=getenv("wims_exec_parm");
+  p=getenv("wims_exec_parm");
-    if(p==NULL || *p==0) error("No input data.");
+  if(p==NULL || *p==0) error("No input data.");
-    getparm(p);
+  getparm(p);
-    huffman();
+  huffman();
-    output();
+  output();
-    return 0;
+  return 0;
+}

Subversion Repositories wimsdev

(root)/trunk/wims/src/Misc/huffman.c – Rev 8195 → 12248