home *** CD-ROM | disk | FTP | other *** search
/ HAM Radio 1 / HamRadio.cdr / tech / pcbsrcs2 / pcbunpak.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-02-07  |  7.3 KB  |  251 lines
  1. /*
  2. ** general purpose file unpacker, 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/17/89        initial version
  27. ** randy nevin        8/6/89        changed to handle run-length encoding
  28. **                    in addition to huffman encoding
  29. ** randy nevin        8/15/89        released version 1.00
  30. */
  31.  
  32. /* BUGBUG: doesn't handle files with only one byte value */
  33.  
  34. /*
  35. ** unpack a file that has been packed with huffman or run-length encoding. the
  36. ** file contains a packing identification byte (1=huffman, 2=run-length). for
  37. ** huffman encoding, it also contains the number of bytes, a skeletal tree
  38. ** structure, the corresponding byte values, and the encoded bits. for
  39. ** run-length encoding, it contains the encoding byte, then the encoded file,
  40. ** with the encoding byte indicating the next two bytes are the number of
  41. ** occurrences, and the encoded byte. an exception (for run-length encoding)
  42. ** is if the number of occurrences is 0, in which case this represents just
  43. ** one (literal) encoded byte; there is no following 'encoded byte'.
  44. */
  45.  
  46. #include <stdio.h>
  47. #include <stdlib.h>
  48. #include <string.h>
  49.  
  50. #define MAX 32    /* use a maximum of 32 bits per byte */
  51.  
  52. struct node { /* tree node for huffman encoding */
  53.     int byteval;
  54.     char buf[MAX+1];
  55.     char pad;
  56.     struct node *left, *right;
  57.     } *head = NULL;
  58.  
  59. void main( int, char *[] );
  60. void walk0( struct node *, FILE * );
  61. void walk1( struct node *, char [], int );
  62. void walk2( struct node *, FILE * );
  63. void initbit( void );
  64. int inbit( FILE * );
  65.  
  66. void main ( argc, argv )
  67.     int argc;
  68.     char *argv[];
  69.     {
  70.     char *self, *t;
  71.     int c, enc, i;
  72.     FILE *fin, *fout;
  73.     register struct node *p;
  74.     char buf[MAX+1];
  75.     long total;
  76.     int b1, b2, b3, b4;
  77.  
  78.     printf( "Copyright (C) Randy Nevin, 1989, 1990. Version 1.00\n" );
  79.     printf( "See source code for rights granted.\n\n" );
  80.     self = argv[0];
  81.     /* get rid of initial part of path */
  82.     if ((t = strrchr( self, '\\' )) || (t = strrchr( self, ':' )))
  83.         self = ++t;
  84.     /* get rid of extension */
  85.     if ((t = strrchr( self, '.' )) && !stricmp( t, ".EXE" ))
  86.         *t = 0;
  87.     if (argc != 3) { /* need infile and outfile */
  88.         fprintf( stderr, "usage: %s infile outfile\n", self );
  89.         exit( -1 );
  90.         }
  91.     if (!(fin = fopen( argv[1], "rb" ))) {
  92.         fprintf( stderr, "can't open %s\n", argv[1] );
  93.         exit( -1 );
  94.         }
  95.     if (!(fout = fopen( argv[2], "wb" ))) {
  96.         fprintf( stderr, "can't open %s\n", argv[2] );
  97.         exit( -1 );
  98.         }
  99.     if ((c = getc( fin )) == 1) { /* huffman encoding */
  100.         b1 = getc( fin );
  101.         b2 = getc( fin );
  102.         b3 = getc( fin );
  103.         b4 = getc( fin );
  104.         total = (long)b1 | ((long)b2<<8) | ((long)b3<<16)
  105.             | ((long)b4 << 24);
  106.         /* build the encoding tree */
  107.         if (!(head = (struct node *)malloc( sizeof(struct node) ))) {
  108.             fprintf( stderr, "out of memory\n" );
  109.             exit( -1 );
  110.             }
  111.         head->left = head->right = NULL;
  112.         initbit();
  113.         walk0( head, fin ); /* construct encoded tree */
  114.         buf[0] = 0;
  115.         walk1( head, buf, 0 ); /* assign encoded bit strings */
  116.         walk2( head, fin ); /* read in byte values */
  117.         initbit();
  118.         while (total--) { /* read in each "byte" */
  119.             p = head;
  120.             while (p->left && p->right)
  121.                 p = (inbit( fin )) ? p->right : p->left;
  122.             putc( (char)(p->byteval), fout );
  123.             }
  124.         }
  125.     else if (c == 2) { /* run-length encoding */
  126.         if ((enc = getc( fin )) == EOF) {
  127.             fprintf( stderr, "premature eof\n" );
  128.             exit( -1 );
  129.             }
  130.         while ((c = getc( fin )) != EOF) {
  131.             if (c == enc) {
  132.                 if ((i = getc( fin )) == EOF) {
  133.                     fprintf( stderr, "premature eof\n" );
  134.                     exit( -1 );
  135.                     }
  136.                 if (!i)
  137.                     putc( (char)enc, fout );
  138.                 else {
  139.                     if ((c = getc( fin )) == EOF) {
  140.                         fprintf( stderr,
  141.                             "premature eof\n" );
  142.                         exit( -1 );
  143.                         }
  144.                     while (i--)
  145.                         putc( (char)c, fout );
  146.                     }
  147.                 }
  148.             else
  149.                 putc( (char)c, fout );
  150.             }
  151.         }
  152.     else if (c == EOF) {
  153.         fprintf( stderr, "premature eof\n" );
  154.         exit( -1 );
  155.         }
  156.     else {
  157.         fprintf( stderr, "unrecognized encoding type\n" );
  158.         exit( -1 );
  159.         }
  160.     if (ferror( fout ))
  161.         fprintf( stderr, "output error; disk might be full\n" );
  162.     fclose( fout );
  163.     exit( 0 );
  164.     }
  165.  
  166. void walk0 ( p, fin ) /* input skeletal tree structure */
  167.     struct node *p;
  168.     FILE *fin;
  169.     {
  170.     /* a 1 bit indicates a node has children; 0 means no children */
  171.     if (inbit( fin )) {
  172.         if (!(p->left = (struct node *)malloc(
  173.                 sizeof(struct node) ))
  174.             || !(p->right = (struct node *)malloc(
  175.                 sizeof(struct node) ))) {
  176.             fprintf( stderr, "out of memory\n" );
  177.             exit( -1 );
  178.             }
  179.         p->left->left =
  180.           p->left->right =
  181.             p->right->left =
  182.               p->right->right = NULL;
  183.         walk0( p->left, fin );
  184.         walk0( p->right, fin );
  185.         }
  186.     }
  187.  
  188. void walk1 ( p, buf, level ) /* assign encoded bit strings */
  189.     struct node *p;
  190.     char buf[];
  191.     int level;
  192.     {
  193.     if (!(p->left) && !(p->right)) {
  194.         strcpy( p->buf, buf );
  195.         /* printf( "str[0x%02X] = %s\n", p->byteval, buf ); */
  196.         }
  197.     else if (level < MAX) {
  198.         buf[level] = '0';
  199.         buf[level+1] = 0;
  200.         walk1( p->left, buf, level+1 );
  201.         buf[level] = '1';
  202.         buf[level+1] = 0;
  203.         walk1( p->right, buf, level+1 );
  204.         buf[level] = 0;
  205.         }
  206.     else {
  207.         fprintf( stderr, "error: skewed tree\n" );
  208.         exit( -1 );
  209.         }
  210.     }
  211.  
  212. void walk2 ( p, fin ) /* read in byte values for the tree */
  213.     struct node *p;
  214.     FILE *fin;
  215.     {
  216.     if (p->left) {
  217.         walk2( p->left, fin );
  218.         walk2( p->right, fin );
  219.         }
  220.     else
  221.         p->byteval = getc( fin );
  222.     }
  223.  
  224. static int nbit; /* how many bits remaining in buffer */
  225. static char byte; /* the byte buffer */
  226.  
  227. void initbit () { /* initialize bit output buffer */
  228.     nbit = 0;
  229.     byte = 0;
  230.     }
  231.  
  232. int inbit( fp ) /* input a bit using byte buffering */
  233.     FILE *fp;
  234.     {
  235.     int bit, newbyte;
  236.  
  237.     if (!nbit) {
  238.         if ((newbyte = getc( fp )) == EOF) {
  239.             fprintf( stderr, "unexpected EOF\n" );
  240.             newbyte = 0; /* force zeros */
  241.             }
  242.         byte = (char)newbyte;
  243.         nbit = 8;
  244.         }
  245.  
  246.     bit = byte & 1;
  247.     byte >>= 1;
  248.     nbit--;
  249.     return( bit );
  250.     }
  251.