home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / pcbpak1.c < prev    next >
C/C++ Source or Header  |  1991-02-07  |  8KB  |  285 lines
  1. /*
  2. ** general purpose file packer, Copyright (C) Randy Nevin 1989, 1990.
  3. **
  4. ** you may give this software to anyone, make as many copies as you like, and
  5. ** post it on public computer bulletin boards and file servers. you may not
  6. ** sell it or charge any fee for distribution (except for media and postage),
  7. ** remove this comment or the copyright notice from the code, or claim that
  8. ** you wrote this code or anything derived from it. you may modify the code as
  9. ** much as you want (please document clearly with comments, and maintain the
  10. ** coding style), but programs which are derived from this one are subject to
  11. ** the conditions stated here. i am providing this code so that people can
  12. ** learn from it, so if you distribute it, please include source code, not
  13. ** just executables. contact me to report bugs or suggest enhancements; i do
  14. ** not guarantee support, but i will make an effort to help you, and i want to
  15. ** act as a central clearing house for future versions. you should contact me
  16. ** before undertaking a significant development effort, to avoid reinventing
  17. ** the wheel. if you come up with an enhancement you consider particularly
  18. ** useful, i would appreciate being informed so that it can be incorporated in
  19. ** future versions. my address is: Randy Nevin, 1731 211th PL NE, Redmond,
  20. ** WA 98053, USA. this code is available directly from the author; just send a
  21. ** 360k floppy and a self-addressed floppy mailer with sufficient postage.
  22. **
  23. ** HISTORY
  24. ** (name        date        description)
  25. ** ----------------------------------------------------
  26. ** randy nevin        7/16/89        initial version
  27. ** randy nevin        8/15/89        released version 1.00
  28. */
  29.  
  30. /* BUGBUG: doesn't handle files with only one byte value */
  31.  
  32. /*
  33. ** use huffman encoding to find the most frequently used bytes. do this by
  34. ** scanning the input file once, counting the number of times each byte
  35. ** occurs. then build a frequency-weighted binary tree. tree traversal will
  36. ** assign a bit sequence to each byte. for files in which a few bytes occur
  37. ** many times, those bytes are near the top of the tree, and thus have a short
  38. ** encoding scheme. then scan the input file again, writing out the binary
  39. ** tree and the encoded input to the output file.
  40. */
  41.  
  42. #include <stdio.h>
  43. #include <stdlib.h>
  44. #include <string.h>
  45.  
  46. #define MAX 32    /* use a maximum of 32 bits per byte */
  47.  
  48. struct node { /* tree node for huffman encoding */
  49.     long count;
  50.     int byteval;
  51.     char buf[MAX+1];
  52.     char pad;
  53.     struct node *left, *right, *nxtnode;
  54.     } *head = NULL, *tail = NULL;
  55.  
  56. long table[0x100]; /* frequency table */
  57. struct node *ptab[0x100]; /* pointers to the corresponding nodes */
  58.  
  59. void main( int, char *[] );
  60. struct node *getmin( void );
  61. void walk0( struct node *, char [], int );
  62. void walk1( struct node *, FILE * );
  63. void walk2( struct node *, FILE * );
  64. void walk3( struct node * );
  65. void initbit( void );
  66. void flushbit( FILE * );
  67. void outbit( int, FILE * );
  68.  
  69. void main ( argc, argv )
  70.     int argc;
  71.     char *argv[];
  72.     {
  73.     char *self, *t;
  74.     int c, i;
  75.     FILE *fin, *fout;
  76.     struct node *p, *q, *r;
  77.     char buf[MAX+1];
  78.     long total;
  79.  
  80.     printf( "Copyright (C) Randy Nevin, 1989, 1990. Version 1.00\n" );
  81.     printf( "See source code for rights granted.\n\n" );
  82.     self = argv[0];
  83.     /* get rid of initial part of path */
  84.     if ((t = strrchr( self, '\\' )) || (t = strrchr( self, ':' )))
  85.         self = ++t;
  86.     /* get rid of extension */
  87.     if ((t = strrchr( self, '.' )) && !stricmp( t, ".EXE" ))
  88.         *t = 0;
  89.     if (argc != 3) { /* need infile and outfile */
  90.         fprintf( stderr, "usage: %s infile outfile\n", self );
  91.         exit( -1 );
  92.         }
  93.     if (!(fin = fopen( argv[1], "rb" ))) {
  94.         fprintf( stderr, "can't open %s\n", argv[1] );
  95.         exit( -1 );
  96.         }
  97.     if (!(fout = fopen( argv[2], "wb" ))) {
  98.         fprintf( stderr, "can't open %s\n", argv[2] );
  99.         exit( -1 );
  100.         }
  101.     /* initialize the byte count table */
  102.     for (i = 0; i < 0x100; i++)
  103.         table[i] = 0;
  104.     /* count the bytes */
  105.     for (total = 0, c = getc( fin ); c != EOF; total++, c = getc( fin ))
  106.         table[c] += 1L;
  107.     putc( 1, fout ); /* encoding type (1=huffman) */
  108.     putc( (char)total, fout );
  109.     putc( (char)(total >> 8), fout );
  110.     putc( (char)(total >> 16), fout );
  111.     putc( (char)(total >> 24), fout );
  112.     fseek( fin, 0L, SEEK_SET ); /* rewind input file for second pass */
  113.     /* build a node for each byte value, and put them in a list */
  114.     for (i = 0; i < 0x100; i++)
  115.         if (table[i]) {
  116.             if (!(p = (struct node *)malloc(
  117.                     sizeof(struct node) ))) {
  118.                 fprintf( stderr, "out of memory\n" );
  119.                 exit( -1 );
  120.                 }
  121.             p->count = table[i];
  122.             p->byteval = i;
  123.             p->left = p->right = p->nxtnode = NULL;
  124.             if (tail)
  125.                 tail->nxtnode = p;
  126.             else
  127.                 head = p;
  128.             tail = p;
  129.             }
  130.     /* collapse forest to a single tree */
  131.     while (head && head->nxtnode) {
  132.         p = getmin();
  133.         q = getmin();
  134.         if (!(r = (struct node *)malloc( sizeof(struct node) ))) {
  135.             fprintf( stderr, "out of memory\n" );
  136.             exit( -1 );
  137.             }
  138.         r->count = p->count + q->count;
  139.         r->left = p;
  140.         r->right = q;
  141.         r->nxtnode = NULL;
  142.         if (tail)
  143.             tail->nxtnode = r;
  144.         else
  145.             head = r;
  146.         tail = r;
  147.         }
  148.     buf[0] = 0;
  149.     walk0( head, buf, 0 ); /* assign encoded bit strings */
  150.     initbit();
  151.     walk1( head, fout ); /* write out tree skeleton */
  152.     flushbit( fout );
  153.     walk2( head, fout ); /* write out byte values */
  154.     walk3( head ); /* set pointers to corresponding nodes */
  155.     initbit();
  156.     while ((c = getc( fin )) != EOF) { /* encode input file */
  157.         for (t = ptab[c]->buf; *t; t++)
  158.             outbit( (*t == '0') ? 0 : 1, fout );
  159.         }
  160.     flushbit( fout );
  161.     if (ferror( fout ))
  162.         fprintf( stderr, "output error; disk might be full\n" );
  163.     fclose( fout );
  164.     exit( 0 );
  165.     }
  166.  
  167. struct node *getmin () { /* fetch & remove smallest-weighted element */
  168.     struct node *p, *q;
  169.  
  170.     for (p = head, q = p->nxtnode; q; q = q->nxtnode)
  171.         if (q->count < p->count) /* find smallest */
  172.             p = q;
  173.     if (p == head) {
  174.         if (p == tail)
  175.             head = tail = NULL;
  176.         else {
  177.             head = p->nxtnode;
  178.             p->nxtnode = NULL;
  179.             }
  180.         }
  181.     else {
  182.         for (q = head; q && q->nxtnode != p; q = q->nxtnode)
  183.             ;
  184.         if (!q) {
  185.             fprintf( stderr, "internal error\n" );
  186.             exit( -1 );
  187.             }
  188.         q->nxtnode = p->nxtnode;
  189.         p->nxtnode = NULL;
  190.         if (p == tail)
  191.             tail = q;
  192.         }
  193.     return( p );
  194.     }
  195.  
  196. void walk0 ( p, buf, level ) /* assign encoded bit strings */
  197.     struct node *p;
  198.     char buf[];
  199.     int level;
  200.     {
  201.     if (!(p->left) && !(p->right)) {
  202.         strcpy( p->buf, buf );
  203.         /* printf( "str[0x%02X] = %s\n", p->byteval, buf ); */
  204.         }
  205.     else if (level < MAX) {
  206.         buf[level] = '0';
  207.         buf[level+1] = 0;
  208.         walk0( p->left, buf, level+1 );
  209.         buf[level] = '1';
  210.         buf[level+1] = 0;
  211.         walk0( p->right, buf, level+1 );
  212.         buf[level] = 0;
  213.         }
  214.     else {
  215.         fprintf( stderr, "error: skewed tree\n" );
  216.         exit( -1 );
  217.         }
  218.     }
  219.  
  220. void walk1 ( p, fout ) /* output skeletal tree structure */
  221.     struct node *p;
  222.     FILE *fout;
  223.     {
  224.     /* a 1 bit indicates a node has children; 0 means no children */
  225.     if (p->left) {
  226.         outbit( 1, fout );
  227.         walk1( p->left, fout );
  228.         walk1( p->right, fout );
  229.         }
  230.     else
  231.         outbit( 0, fout );
  232.     }
  233.  
  234. void walk2 ( p, fout ) /* write out byte values from the tree */
  235.     struct node *p;
  236.     FILE *fout;
  237.     {
  238.     if (p->left) {
  239.         walk2( p->left, fout );
  240.         walk2( p->right, fout );
  241.         }
  242.     else
  243.         putc( (char)(p->byteval), fout );
  244.     }
  245.  
  246. void walk3 ( p ) /* set pointers to corresponding nodes */
  247.     struct node *p;
  248.     {
  249.     if (p->left) {
  250.         walk3( p->left );
  251.         walk3( p->right );
  252.         }
  253.     else
  254.         ptab[p->byteval] = p;
  255.     }
  256.  
  257. static int shift; /* how far to shift next bit */
  258. static char byte; /* the byte buffer */
  259.  
  260. void initbit () { /* initialize bit output buffer */
  261.     byte = 0;
  262.     shift = 0;
  263.     }
  264.  
  265. void flushbit ( fp ) /* flush bit output buffer */
  266.     FILE *fp;
  267.     {
  268.     if (shift) /* buffer non-empty? */
  269.         putc( byte, fp ); /* yes, output partial byte */
  270.     }
  271.  
  272. void outbit( bit, fp ) /* output a bit using byte buffering */
  273.     int bit;
  274.     FILE *fp;
  275.     {
  276.     byte |= ((char)bit << shift);
  277.     if (shift == 7) {
  278.         putc( byte, fp );
  279.         byte = 0;
  280.         shift = 0;
  281.         }
  282.     else
  283.         shift++;
  284.     }
  285.