home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / INFO / COMPRESS / HUFF_SC.ZIP / UNHUF.C < prev    next >
Encoding:
C/C++ Source or Header  |  1991-04-25  |  14.7 KB  |  492 lines
  1. /*******************************************************************************
  2. *                                                                              *
  3. * UNHUF.C   by Shaun Case   April 1991                                         *
  4. *                                                                              *
  5. * Written in Borland C++ 2.0 under MS-DOS 3.3                                  *
  6. *                                                                              *
  7. * Decompresses a single file encoded with companion program HUF,               *
  8. * which uses Huffman encoding.                                                 *
  9. *                                                                              *
  10. * This program is in the public domain.                                        *
  11. *                                                                              *
  12. * atman%ecst.csuchico.edu@RELAY.CS.NET                                         *
  13. *                                                                              *
  14. *                                                                              *
  15. *******************************************************************************/
  16.  
  17. #include <stdio.h>
  18. #include <math.h>
  19.  
  20. #define FALSE 0
  21. #define TRUE !FALSE
  22. #define MAX_DECODE_TABLE_SIZE 520       /* 512 should be enough           */
  23.  
  24.  
  25. /* uncomment the next line to see the decode table at runtime. */
  26.  
  27. /*
  28. #define DEBUG
  29. */
  30.  
  31.  
  32. /* uncomment the next line to only uncompress the exact number of bytes   */
  33. /* that were originally encoded.  If it is not defined, the routine will  */
  34. /* faster, but will generate up to 8 extra bytes at the end of the        */
  35. /* decompressed data.                                                     */
  36.  
  37. #define EXACT
  38.  
  39.  
  40. typedef struct decode_table_element {   /* template for decode table element (wow)  */
  41.     unsigned char letter;               /* which character to decode to             */
  42.     char spare;                         /* force 16-bit word alignment              */
  43.     short left;                         /* index of lower left element from tree    */
  44.     short right;                        /* index of lower right element from tree   */
  45. }decode_table_element;
  46.  
  47.  
  48. short array_max_index;                  /* max number of elements in array (to be   */
  49.                                         /* determined in create_decode_table() )    */
  50.  
  51. unsigned long  total;                   /* total number of unencoded bytes          */
  52. FILE *infile;                           /* file ptr to SYSTEM.HUF (compressed)      */
  53. FILE *outfile;                          /* file ptr to SYSTEM.UNH (decompressed)    */
  54. char *infilename;                       /* name of the input file                   */
  55. char origfilename[13];                  /* name of the original file                */
  56.  
  57. struct decode_table_element             /* array implementation of huffman tree     */
  58.     decode_table[MAX_DECODE_TABLE_SIZE];
  59.  
  60. /******
  61.  *
  62.  * Datafile:  All 16/32 bit quantities in Intel byte ordering
  63.  *
  64.  *  13 bytes    : original filename (8.3 + '\0')
  65.  *  16 bits     : number of array elements needed, N (N == 511 means 512 array
  66.  *                elements -> 0..511)
  67.  *  32 bits     : size of uncompressed original data in bytes
  68.  *  N * 6 bytes : Array elements in order 0 .. N
  69.  *                struct decode_table_element {
  70.  *                     char letter;      8 bits
  71.  *                     char spare;       8 bits
  72.  *                     short left;      16 bits
  73.  *                     short right;     16 bits
  74.  *                 }
  75.  *  <?>          : compressed data, effectively a bit stream
  76.  *
  77.  ******/
  78.  
  79.  
  80. int main(int argc, char **argv)
  81. {
  82.     short read_header(void);                /* prototype */
  83.     void show_bit_sequences(short index);   /* prototype */
  84.     short uncompress(void);                 /* prototype */
  85.  
  86.     if (argc != 2) {                        /* check command line argument validity  */
  87.         puts("'unhuf file' decodes file.");
  88.         return 1;
  89.     }
  90.     puts("Unhuf by Shaun Case, 1991, public domain");
  91.  
  92.     infilename=argv[1];
  93.  
  94.  
  95.     if (read_header() != 0)                 /* read in file name, size, decode table */
  96.         return 1;
  97.  
  98. #ifdef DEBUG
  99.     show_bit_sequences(0);
  100. #endif
  101.  
  102.     if (uncompress() != 0)                  /* uncompress the data & write to file   */
  103.         return 1;
  104.  
  105.     fclose(infile);
  106.  
  107.     return 0;
  108.  
  109. }
  110.  
  111. /*
  112.  * read in the original filename, size, and decode table
  113.  *
  114.  */
  115.  
  116. short read_header(void)
  117. {
  118.     if ((infile=fopen(infilename, "rb")) == NULL)        /* open file           */
  119.     {
  120.         printf("Unable to open %s\n", infilename);
  121.         return 1;
  122.     }
  123.  
  124.  
  125.     if (                                                 /* get original name   */
  126.           fread((void *)origfilename, 1, 13, infile)
  127.           < 13
  128.        )
  129.     {
  130.         printf("Unable to read original filename from %s\n", infilename);
  131.         fclose(infile);
  132.         return 1;
  133.     }
  134.  
  135.                                                          /* get length of decode table */
  136.     if (
  137.           fread((void *)&array_max_index, sizeof(short), 1, infile)
  138.           < 1
  139.        )
  140.     {
  141.         printf("Unable to read number of array elements from %s\n", infilename);
  142.         fclose(infile);
  143.         return 1;
  144.     }
  145.  
  146.         if (                                             /* get filesize in bytes */
  147.               fread((void *)&total, sizeof(unsigned long), 1, infile)
  148.             < 1
  149.        )
  150.     {
  151.         printf("Unable to read original byte count from %s\n", infilename);
  152.         fclose(infile);
  153.         return 1;
  154.     }
  155.  
  156.     printf("Decoding %ld bytes to %s.\n", total, origfilename);
  157.     printf("Decode table contains %d elements.\n",array_max_index + 1);
  158.  
  159.     if (                                                /* get decode table        */
  160.           fread((void *)decode_table, sizeof(decode_table_element), array_max_index + 1, infile)
  161.           < (array_max_index + 1)
  162.        )
  163.     {
  164.         printf("Unable to read decode table from %s\n", infilename);
  165.         fclose(infile);
  166.         return 1;
  167.     }
  168.  
  169.     return 0;
  170. }
  171.  
  172. #ifdef DEBUG
  173. short seq_len=0;  /* routine is recursive, needs global storage  */
  174.                   /* length of current bit sequence              */
  175.                   /* this should probably be static inside sbs() */
  176.  
  177.  
  178. /*
  179.  * display the bit sequences that represent each character.
  180.  * useful for debugging.
  181.  *
  182.  */
  183.  
  184. void show_bit_sequences(short index)
  185. {
  186.  
  187.     static short temp_index=0;
  188.     static char bit_sequence[16];       /* where to build the huffman bit sequence  */
  189.  
  190.     if (decode_table[index].left != 0)  /* if we are not at a leaf, go left         */
  191.     {
  192.         bit_sequence[seq_len++]='1';
  193.         show_bit_sequences(decode_table[index].left);
  194.         seq_len--;
  195.     }
  196.                                         /* returned from going left, now try right  */
  197.     if (decode_table[index].right != 0)
  198.     {
  199.         bit_sequence[seq_len++]='0';    /* if we are not at a leaf, go right        */
  200.         show_bit_sequences(decode_table[index].right);
  201.         seq_len--;
  202.     }
  203.  
  204.     if (decode_table[index].left != NULL)    /* we are at an interior node going back up */
  205.         return;
  206.  
  207.     /* we are at a leaf, therefore we have a complete bit sequence built            */
  208.  
  209.     bit_sequence[seq_len] = 0;          /* append teriminating NULL to string       */
  210.  
  211.     printf("[%3d] %3d == %16s == %3d\n", temp_index, decode_table[index].letter, bit_sequence, seq_len);
  212.     temp_index++;
  213. }
  214.  
  215. #endif
  216.  
  217. /*
  218.  * all the fputc() calls are unrolled for speed.
  219.  *
  220.  */
  221.  
  222. short uncompress(void)
  223. {
  224.  
  225.     /* tcc68 can assign 7 register variables */
  226.  
  227.     register short index         = 0;               /* "ptr" to "node" in "tree"        */
  228.                                                     /* actually an array index          */
  229.     register unsigned unsigned int buffer = 0;      /* 8 bit buffer                     */
  230.     register unsigned short fastleft;               /* fast ptr to next left  element   */
  231.     register unsigned short  fastleft0;             /* fast ptr to left of root         */
  232.     register long running_total = 0L;
  233.  
  234.     if ((outfile=fopen(origfilename, "wb")) == NULL)    /* open file                        */
  235.     {
  236.         printf("Unable to open %s\n", origfilename);
  237.         return 1;
  238.     }
  239.  
  240.     fastleft0 = decode_table[0].left;                   /* setup frequently used vars       */
  241.     fastleft = fastleft0;
  242.  
  243.     while (1)
  244.     {
  245.         buffer=fgetc(infile);                           /* get 8 bits                       */
  246.  
  247.  
  248.         /* branch left if current bit == 1, else branch right                               */
  249.  
  250.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  251.  
  252.         buffer <<= 1;                                   /* rotate next bit to test postion  */
  253.  
  254.         fastleft = decode_table[index].left;            /* set up frequently used var       */
  255.  
  256.         if (fastleft == 0)                              /* if we have decoded a char        */
  257.         {
  258.             if (
  259.                 fputc((int)decode_table[index].letter, outfile)    /* write it to output    */
  260.                 == EOF
  261.                )
  262.             {
  263.                 puts("Error writing to output file, out of disk space?");
  264.                 return 1;
  265.             }
  266.             index = 0;                                  /* set "ptr" to top of "tree"       */
  267.             fastleft = fastleft0;                       /* set up freq. used variable       */
  268. #ifdef EXACT
  269.             if (++running_total == total) goto finished;  /* if we are done, quit.          */
  270. #endif EXACT
  271. #ifndef EXACT
  272.         ++running_total;
  273. #endif EXACT
  274.         }
  275.  
  276.  
  277.         /* and do it again for 2nd bit. */
  278.  
  279.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  280.  
  281.         buffer <<= 1;
  282.  
  283.         fastleft = decode_table[index].left;
  284.  
  285.         if (fastleft == 0)
  286.         {
  287.             if (
  288.                 fputc((int)decode_table[index].letter, outfile)
  289.                 == EOF
  290.                )
  291.             {
  292.                 puts("Error writing to output file, out of disk space?");
  293.                 return 1;
  294.             }
  295.             
  296.             index = 0;
  297.             fastleft = fastleft0;
  298. #ifdef EXACT
  299.             if (++running_total == total) goto finished;
  300. #endif EXACT
  301. #ifndef EXACT
  302.         ++running_total;
  303. #endif EXACT
  304.         }
  305.  
  306.         /* and 3rd bit. */
  307.  
  308.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  309.  
  310.         buffer <<= 1;
  311.  
  312.         fastleft = decode_table[index].left;
  313.  
  314.         if (fastleft == 0)
  315.         {
  316.             if (
  317.                 fputc((int)decode_table[index].letter, outfile)
  318.                 == EOF
  319.                )
  320.             {
  321.                 puts("Error writing to output file, out of disk space?");
  322.                 return 1;
  323.             }
  324.             
  325.             index = 0;
  326.             fastleft = fastleft0;
  327. #ifdef EXACT
  328.             if (++running_total == total) goto finished;
  329. #endif EXACT
  330. #ifndef EXACT
  331.         ++running_total;
  332. #endif EXACT
  333.         }
  334.  
  335.         /* and 4th bit. */
  336.  
  337.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  338.  
  339.         buffer <<= 1;
  340.  
  341.         fastleft = decode_table[index].left;
  342.  
  343.         if (fastleft == 0)
  344.         {
  345.             if (
  346.                 fputc((int)decode_table[index].letter, outfile)
  347.                 == EOF
  348.                )
  349.             {
  350.                 puts("Error writing to output file, out of disk space?");
  351.                 return 1;
  352.             }
  353.             
  354.             index=0;
  355.             fastleft = fastleft0;
  356. #ifdef EXACT
  357.             if (++running_total == total) goto finished;
  358. #endif EXACT
  359. #ifndef EXACT
  360.         ++running_total;
  361. #endif EXACT
  362.         }
  363.  
  364.         /* and 5th bit. */
  365.  
  366.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  367.  
  368.         buffer <<= 1;
  369.  
  370.         fastleft = decode_table[index].left;
  371.  
  372.         if (fastleft == 0)
  373.         {
  374.             if (
  375.                 fputc((int)decode_table[index].letter, outfile)
  376.                 == EOF
  377.                )
  378.             {
  379.                 puts("Error writing to output file, out of disk space?");
  380.                 return 1;
  381.             }
  382.             index = 0;
  383.             fastleft = fastleft0;
  384. #ifdef EXACT
  385.             if (++running_total == total) goto finished;
  386. #endif EXACT
  387. #ifndef EXACT
  388.         ++running_total;
  389. #endif EXACT
  390.         }
  391.  
  392.         /* and 6th bit. */
  393.  
  394.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  395.  
  396.         buffer <<= 1;
  397.  
  398.         fastleft = decode_table[index].left;
  399.  
  400.         if (fastleft == 0)
  401.         {
  402.             if (
  403.                 fputc((int)decode_table[index].letter, outfile)
  404.                 == EOF
  405.                )
  406.             {
  407.                 puts("Error writing to output file, out of disk space?");
  408.                 return 1;
  409.             }
  410.  
  411.             index = 0;
  412.             fastleft = fastleft0;
  413. #ifdef EXACT
  414.             if (++running_total == total) goto finished;
  415. #endif EXACT
  416. #ifndef EXACT
  417.         ++running_total;
  418. #endif EXACT
  419.         }
  420.  
  421.         /* and 7th bit. */
  422.  
  423.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  424.  
  425.         buffer <<= 1;
  426.  
  427.         fastleft = decode_table[index].left;
  428.  
  429.         if (fastleft == 0)
  430.         {
  431.             if (
  432.                 fputc((int)decode_table[index].letter, outfile)
  433.                 == EOF
  434.                )
  435.             {
  436.                 puts("Error writing to output file, out of disk space?");
  437.                 return 1;
  438.             }
  439.  
  440.             index = 0;
  441.             fastleft = fastleft0;
  442. #ifdef EXACT
  443.             if (++running_total == total) goto finished;
  444. #endif EXACT
  445. #ifndef EXACT
  446.         ++running_total;
  447. #endif EXACT
  448.         }
  449.  
  450.         /* and finally, the 8th bit. */
  451.  
  452.         index = ( (buffer & 0x0080) ? fastleft : decode_table[index].right);
  453.  
  454.         buffer <<= 1;
  455.  
  456.         fastleft = decode_table[index].left;
  457.  
  458.         if (fastleft == 0)
  459.         {
  460.             if (
  461.                 fputc((int)decode_table[index].letter, outfile)
  462.                 == EOF
  463.                )
  464.             {
  465.                 puts("Error writing to output file, out of disk space?");
  466.                 return 1;
  467.             }
  468.  
  469.             index = 0;
  470.             fastleft = fastleft0;
  471. #ifdef EXACT
  472.             if (++running_total == total) goto finished;
  473. #endif EXACT
  474. #ifndef EXACT
  475.             ++running_total;
  476. #endif EXACT
  477.         }
  478. #ifndef EXACT
  479.         if (running_total >= total)
  480.             goto finished;
  481. #endif EXACT
  482.  
  483.     }
  484.  
  485. finished:
  486.  
  487.     fclose(outfile);
  488.     printf("Decoded %ld bytes.", running_total);
  489.     return 0;
  490. }
  491.  
  492.