home *** CD-ROM | disk | FTP | other *** search
/ World of A1200 / World_Of_A1200.iso / datafiles / text / drdobb / drdobbscompress.lha / huffd.c < prev    next >
C/C++ Source or Header  |  1992-09-20  |  2KB  |  122 lines
  1. /* HUFFMAN DECODING PROG */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. typedef unsigned int BYTECOUNTER;
  7.  
  8. struct htree {
  9.     unsigned char ch;
  10.     BYTECOUNTER cnt;
  11.     struct htree *parent;
  12.     struct htree *right;
  13.     struct htree *left;
  14. };
  15.  
  16. struct htree ht[512];
  17. struct htree *root;
  18.  
  19. void buildtree(void)
  20. {
  21.     int treect = 256;
  22.     int i;
  23.     
  24.     while (1) {
  25.         struct htree *h1 = NULL, *h2 = NULL;
  26.         
  27.         for (i=0; i<treect; i++) {
  28.             if (ht+i != h1) {
  29.                 if (ht[i].cnt>0 && ht[i].parent == NULL) {
  30.                     if (h1==NULL || ht[i].cnt<h1->cnt) {
  31.                         if (h2==NULL || h1->cnt<h2->cnt)
  32.                             h2 = h1;
  33.                         h1 = ht+i;
  34.                     }
  35.                     else if (h2==NULL || ht[i].cnt <h2->cnt)
  36.                         h2 = ht+i;
  37.                 }
  38.             }
  39.         }
  40.         if (h2==NULL) {
  41.             root = h1;
  42.             break;
  43.         }
  44.         h1->parent = ht+treect;
  45.         h2->parent = ht+treect;
  46.         ht[treect].cnt = h1->cnt + h2->cnt;
  47.         ht[treect].right = h1;
  48.         ht[treect].left = h2;
  49.         treect++;
  50.     }
  51. }
  52.     
  53. static int decompress(FILE *fi,struct htree *root);
  54.  
  55. void main(int argc,char *argv[])
  56. {
  57.     FILE *fi,*fo;
  58.     unsigned char c;
  59.     BYTECOUNTER bytectr;
  60.     int count;
  61.     
  62.     if (argc < 3) {
  63.         printf("usage: huffd infile outfile\n");
  64.         exit(1);
  65.     }
  66.     
  67.     if ((fi=fopen(argv[1],"rb"))==NULL) {
  68.         printf("Cannot open input file %s\n",argv[1]);
  69.         exit(1);
  70.     }
  71.     
  72.     if ((fo=fopen(argv[2],"wb"))==NULL) {
  73.         printf("Cannot open output file %s\n",argv[2]);
  74.         exit(1);
  75.     }
  76.     
  77.     fread(&bytectr,sizeof bytectr,1,fi);
  78.     
  79.     for (count=0;count<256;count++) {
  80.         c=fgetc(fi);
  81.         ht[count].cnt=(BYTECOUNTER)c;
  82. #ifdef DEBUG
  83.         fprintf(stderr,"  %3u",ht[count].cnt);
  84. #endif
  85.         ht[count].ch=count;
  86.     }
  87.     
  88.     buildtree();
  89.     
  90.     while (bytectr--)
  91.         fputc(decompress(fi,root),fo);
  92.     fclose(fo);
  93.     fclose(fi);
  94. }
  95.  
  96. static int in8;
  97. static int ct8 = 8;
  98.  
  99. static int inbit(FILE *fi)
  100. {
  101.     int obit;
  102.     if (ct8==8) {
  103.         in8 = fgetc(fi);
  104.         ct8 = 0;
  105.     }
  106.     obit = in8 & 0x80;
  107.     in8 <<= 1;
  108.     ct8++;
  109.     return obit;
  110. }
  111.  
  112. static int decompress(FILE *fi,struct htree *h)
  113. {
  114.     while (h->right != NULL)
  115.         if (inbit(fi))
  116.             h = h->left;
  117.         else
  118.             h = h->right;
  119.     return h->ch;
  120. }
  121.  
  122.