home *** CD-ROM | disk | FTP | other *** search
/ World of A1200 / World_Of_A1200.iso / datafiles / text / drdobb / unpacked / huff.c < prev    next >
C/C++ Source or Header  |  1995-02-27  |  2KB  |  132 lines
  1. /* HUFFMAN ENCODING PROG */
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. typedef unsigned int BYTECOUNTER;
  7.  
  8. struct htree {
  9.     BYTECOUNTER cnt;
  10.     struct htree *parent;
  11.     struct htree *right;
  12.     struct htree *left;
  13. };
  14.  
  15. struct htree ht[512];
  16. struct htree *root;
  17.  
  18. void buildtree(void)
  19. {
  20.     int treect = 256;
  21.     int i;
  22.     
  23.     while (1) {
  24.         struct htree *h1 = NULL, *h2 = NULL;
  25.         
  26.         for (i=0; i<treect; i++) {
  27.             if (ht+i != h1) {
  28.                 if (ht[i].cnt>0 && ht[i].parent == NULL) {
  29.                     if (h1==NULL || ht[i].cnt<h1->cnt) {
  30.                         if (h2==NULL || h1->cnt<h2->cnt)
  31.                             h2 = h1;
  32.                         h1 = ht+i;
  33.                     }
  34.                     else if (h2==NULL || ht[i].cnt <h2->cnt)
  35.                         h2 = ht+i;
  36.                 }
  37.             }
  38.         }
  39.         if (h2==NULL) {
  40.             root = h1;
  41.             break;
  42.         }
  43.         h1->parent = ht+treect;
  44.         h2->parent = ht+treect;
  45.         ht[treect].cnt = h1->cnt + h2->cnt;
  46.         ht[treect].right = h1;
  47.         ht[treect].left = h2;
  48.         treect++;
  49.     }
  50. }
  51.     
  52. static void compress(FILE *fo, struct htree *h, struct htree *child);
  53. static void outbit(FILE *fo, int bit);
  54.  
  55. void main(int argc, char *argv[])
  56. {
  57.     FILE *fi,*fo;
  58.     int c;
  59.     BYTECOUNTER bytectr = 0;
  60.     int maxx = 0;
  61.     
  62.     if (argc<3) {
  63.         printf("usage : huffc 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.     while ((c=fgetc(fi)) != EOF) {
  78.         c &= 255;
  79.         ht[c].cnt++;
  80.         bytectr++;
  81.     }
  82.     
  83.     fwrite (&bytectr,sizeof bytectr,1,fo);
  84.     
  85.     for (c=0;c<256;c++)
  86.         if (ht[c].cnt>maxx) maxx=ht[c].cnt;
  87.             
  88.     for (c=0;c<256;c++) {
  89.         if (ht[c].cnt>0)
  90.             ht[c].cnt=((ht[c].cnt*254)/maxx)+1;
  91.         fputc((unsigned char)ht[c].cnt,fo);
  92. #ifdef DEBUG
  93.         fprintf(stderr,"  %3u",ht[c].cnt);
  94. #endif
  95.     }
  96.     
  97.     buildtree();
  98.     
  99.     fseek(fi,0L,0);
  100.     while ((c=fgetc(fi)) != EOF)
  101.         compress(fo,ht+(c&255),NULL);
  102.     for (c=0;c<8;c++) outbit(fo,0);
  103.     fclose(fi);
  104.     fclose(fo);
  105. }
  106.  
  107. static void compress(FILE *fo,struct htree *h,struct htree *child)
  108. {
  109.     if (h->parent != NULL)
  110.         compress(fo,h->parent,h);
  111.     if (child) {
  112.         if (child==h->right)
  113.             outbit(fo,0);
  114.         else if (child == h->left)
  115.             outbit(fo,1);
  116.     }
  117. }
  118.  
  119. static char out8;
  120. static int ct8;
  121.  
  122. static void outbit(FILE *fo, int bit)
  123. {
  124.     if (ct8==8) {
  125.         fputc(out8,fo);
  126.         ct8=0;
  127.     }
  128.     out8=(out8<<1) | bit;
  129.     ct8++;
  130. }
  131.  
  132.