home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 642a.lha / huffman_v1.0 / huffman.c < prev    next >
C/C++ Source or Header  |  1992-01-18  |  5KB  |  241 lines
  1. /*
  2.  * huffman.c - applies huffman encoding or decoding to files
  3.  *
  4.  * Lucia Darsa & Bruno Costa - 5 Sep 90 - 14 Sep 90
  5.  */
  6.  
  7. #define DEBUG 1
  8.  
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <ctype.h>
  12. #include "bits.h"
  13. #include "encoders.h"
  14.  
  15. #define TRUE  1
  16. #define FALSE 0
  17.  
  18. #define PERCENT100 10000
  19. #define NORMFACTOR 100
  20.  
  21. #define FILEID (((long)'H' << 24) | ((long)'U' << 16) | ((long)'F' << 8))
  22.  
  23.  
  24. int writeheader (FILE *out, unsigned long int size, bitstream code[])
  25. {
  26.  int i, j;
  27.  unsigned long int id = FILEID;
  28.  
  29.  writelong (id, out);
  30.  
  31.  for (i = 0; i < 256; i++)
  32.    if (code[i].len)
  33.    {
  34.      writebyte (i, out);
  35.      writebyte (code[i].len, out);
  36.      for (j = 3 - (code[i].len - 1)/ 32; j < 4; j++)
  37.        writelong (code[i].data[j], out);
  38.    }
  39.  
  40.  writebyte (0, out);            /* code stream terminator */
  41.  writebyte (0, out);
  42.  
  43.  writelong (size, out);
  44.  return TRUE;
  45. }
  46.  
  47.  
  48. int compress (FILE *in, FILE *out, bitstream code[])
  49. {
  50.  int c;
  51.  
  52.  while ((c = getc (in)) != EOF)
  53.    if (!writebits (&code[c], out))
  54.      return FALSE;
  55.  
  56.  flushbits (out);
  57.  
  58.  return TRUE;
  59. }
  60.  
  61.  
  62. unsigned long int getfreq (FILE *in, long int freq[])
  63. {
  64.  int i, c;
  65.  unsigned long int size = 0;
  66.  
  67.  for (i = 0; i < 256; i++)
  68.    freq[i] = 0;
  69.  
  70.  rewind (in);
  71.  
  72.  while ((c = getc (in)) != EOF)
  73.  {
  74.    freq[c]++;
  75.    size++;
  76.  }
  77.  
  78.  rewind (in);
  79.  
  80.  return (size * 8);
  81. }
  82.  
  83.  
  84. int encode (FILE *in, FILE *out)
  85. {
  86.  long int frequencies[256];
  87.  bitstream codes[256];
  88.  unsigned long int oldsize, newsize;
  89.  
  90.  oldsize = getfreq (in, frequencies);
  91.  
  92.  newsize = huffman (frequencies, codes);
  93.  
  94.  if (out)
  95.    if (!writeheader (out, newsize, codes)  ||  !compress (in, out, codes))
  96.      return (0);
  97.  
  98.  return PERCENT100 - (((newsize / 100) * PERCENT100) / (oldsize / 100));
  99. }
  100.  
  101.  
  102. /* returns the number of bits following */
  103. unsigned long int readheader (FILE *in, bitstream code[])
  104. {
  105.  unsigned long int id, size;
  106.  int i, j, len;
  107.  
  108.  id = readlong (in);
  109.  if (id != FILEID)
  110.    return (0);
  111.  
  112.  for (i = 0; i < 256; i++)
  113.  {
  114.    code[i].len = 0;
  115.    for (j = 0; j < 4; j++)
  116.      code[i].data[j] = 0UL;
  117.  }
  118.  
  119.  i = readbyte (in);
  120.  len = readbyte (in);
  121.  while (i != 0  ||  len != 0)
  122.  {
  123.    code[i].len = len;
  124.    for (j = 3 - (len - 1)/32; j < 4; j++)
  125.      code[i].data[j] = readlong (in);
  126.    i = readbyte (in);
  127.    len = readbyte (in);
  128.  }
  129.  
  130.  size = readlong (in);
  131.  return (size);
  132. }
  133.  
  134.  
  135. int decode (FILE *in, FILE *out)
  136. {
  137.  unsigned long int size;
  138.  int bit, c;
  139.  bitstream codes[256];
  140.  
  141.  size = readheader (in, codes);
  142.  
  143.  if (size == 0)
  144.    return FALSE;
  145.  
  146.  do
  147.  {
  148.    bit = getbit (in, size);
  149.    if ((c = matchbit (bit, codes)) != -1)
  150.      putc (c, out);
  151.  } while (bit != EOF);
  152.  
  153.  return TRUE;
  154. }
  155.  
  156.  
  157. void usage (void)
  158. {
  159.  fprintf (stderr, "usage: huffman [-c | -u | -r] [-f | filenames ...]\n");
  160.  exit (10);
  161. }
  162.  
  163.  
  164. int main (int argc, char *argv[])
  165. {
  166.  int i, compress;
  167.  int valid = FALSE;
  168.  int justrate = FALSE;
  169.  
  170.  if (argc == 1)
  171.    usage ();
  172.  
  173.  for (i = 1; i < argc; i++)
  174.  {
  175.    if (argv[i][0] == '-')
  176.      switch (argv[i][1])
  177.      {
  178.        case 'c':
  179.          compress = TRUE;
  180.          valid = TRUE;
  181.          break;
  182.        case 'u':
  183.          compress = FALSE;
  184.          valid = TRUE;
  185.          break;
  186.        case 'r':
  187.          justrate = TRUE;
  188.          valid = TRUE;
  189.          break;
  190.        default:
  191.          fprintf (stderr, "huffman: unknown option %c\n", argv[i][1]);
  192.          usage ();
  193.          break;
  194.      }
  195.    else if (!valid)
  196.      usage ();
  197.    else
  198.    {
  199.      FILE *in = fopen (argv[i], "rb");
  200.      int done = TRUE;
  201.  
  202.      if (!in)
  203.        fprintf (stderr, "huffman: could not open file %s\n", argv[i]);
  204.      else if (justrate)
  205.      {
  206.        int r = encode (in, NULL);
  207.        printf ("%s (%d.%02d%%)\n", argv[i], r/NORMFACTOR, r%NORMFACTOR);
  208.      }
  209.      else
  210.      {
  211.        char outnam[20];
  212.        FILE *out = fopen (tmpnam (outnam), "wb");
  213.        if (!out)
  214.        {
  215.          fprintf (stderr, "huffman: could not open temp file for %s -- aborted!\n", argv[i]);
  216.          exit (20);
  217.        }
  218.        else
  219.        {
  220.          if (compress)
  221.          {
  222.            int r = encode (in, out);
  223.            printf ("%s (%d.%02d%%)\n", argv[i], r/NORMFACTOR, r%NORMFACTOR);
  224.          }
  225.          else
  226.            if (!(done = decode (in, out)))
  227.              fprintf (stderr, "huffman: could not decode %s\n", argv[i]);
  228.          fclose (out);
  229.        }
  230.        fclose (in);
  231.        if (done)
  232.          if (remove (argv[i]) == -1)
  233.            fprintf (stderr, "huffman: could not remove %s\n", argv[i]);
  234.          else if (rename (outnam, argv[i]) == -1)
  235.            fprintf (stderr, "huffman: could not rename %s to %s\n", outnam, argv[i]);
  236.      }
  237.    }
  238.  }
  239.  return (0);
  240. }
  241.