home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 642a.lha / huffman_v1.0 / encoders.c < prev    next >
C/C++ Source or Header  |  1992-01-18  |  4KB  |  214 lines
  1. /*
  2.  * encoders.c - huffman/ASCII code conversion and manipulation functions
  3.  *
  4.  * Lucia Darsa & Bruno Costa - 14 Sep 90 - 14 Sep 90
  5.  */
  6.  
  7. #define DEBUG 1
  8.  
  9. #include <stdio.h>
  10. #include <limits.h>
  11. #include "bits.h"
  12. #include "encoders.h"
  13.  
  14. #define TRUE  1
  15. #define FALSE 0
  16.  
  17.  
  18. typedef struct node_ {
  19.   struct node_ *left;
  20.   struct node_ *right;
  21.   unsigned char c;
  22. } node;
  23.  
  24. typedef struct tree_ {
  25.   node *root;
  26.   long int freq;
  27. } tree;
  28.  
  29. /*
  30.  * internal functions prototypes
  31.  */
  32. static void rbuild (bitstream code, node *root, bitstream codes[]);
  33. static void buildcodes (node *root, bitstream codes[]);
  34. static node *buildtree (bitstream codes[]);
  35.  
  36. /*
  37.  * pseudo-dynamic memory allocation scheme
  38.  * (the algorithms assure that memory is never exhausted)
  39.  *
  40.  *  NOTE: for those that simply cannot understand the line below, the comma
  41.  *        operator executes its operands from left to right, and returns the
  42.  *        value of the rightmost one.
  43.  */
  44. #define mknode() (memory[avail].left = memory[avail].right = NULL, &memory[avail++])
  45. #define freenodes() avail = 0
  46. static node memory[512];
  47. static int avail = 0;
  48.  
  49. static void rbuild (bitstream code, node *root, bitstream codes[])
  50. {
  51.  if (root->left == NULL)        /* is it a leaf? */
  52.    codes[root->c] = code;
  53.  else
  54.  {
  55.    lshift (&code);
  56.    rbuild (code, root->left, codes);
  57.    code.data[3] |= 1;
  58.    rbuild (code, root->right, codes);
  59.  }
  60. }
  61.  
  62.  
  63. static void buildcodes (node *root, bitstream codes[])
  64. {
  65.  int i;
  66.  static bitstream zerocode = {
  67.    {0, 0, 0, 0}, 0
  68.  };
  69.  
  70.  for (i = 0; i < 256; i++)
  71.    codes[i] = zerocode;
  72.  
  73.  rbuild (zerocode, root, codes);
  74. }
  75.  
  76.  
  77. #define HUGEFREQ LONG_MAX
  78.  
  79. unsigned long int huffman (long int frequency[], bitstream codes[])
  80. {
  81.  tree forest[256], *last;
  82.  unsigned long int size = 0;
  83.  int i;
  84.  
  85.  for (i = 0, last = forest; i < 256; i++)
  86.    if (frequency[i] != 0)
  87.    {
  88.      node *r = mknode ();
  89.      r->c = i;
  90.      last->root = r;
  91.      last->freq = frequency[i];
  92.      last++;
  93.    }
  94.  
  95.  for (last--; last > forest; last--)
  96.  {
  97.    node *newroot;
  98.    tree *first, *second, *p;
  99.    long int firstfreq, secondfreq;
  100.  
  101.    first = second = NULL;
  102.    firstfreq = secondfreq = HUGEFREQ;
  103.    for (p = forest; p <= last; p++)
  104.      if (p->freq < firstfreq)
  105.      {
  106.        second = first;
  107.        secondfreq = firstfreq;
  108.        first = p;
  109.        firstfreq = p->freq;
  110.      }
  111.      else if (p->freq < secondfreq)
  112.      {
  113.        second = p;
  114.        secondfreq = p->freq;
  115.      }
  116.  
  117.    newroot = mknode ();
  118.    newroot->left = first->root;
  119.    newroot->right = second->root;
  120.    first->root = newroot;
  121.    first->freq = firstfreq + secondfreq;
  122.  
  123.    second->root = last->root;
  124.    second->freq = last->freq;
  125.  }
  126.  
  127.  buildcodes (forest[0].root, codes);
  128.  
  129.  freenodes ();
  130.  
  131.  for (i = 0; i < 256; i++)
  132.    size += frequency[i] * codes[i].len;
  133.  
  134.  return (size);
  135. }
  136.  
  137.  
  138. static void traverse (node **current, int direction)
  139. {
  140.  if (direction)
  141.  {
  142.    if ((*current)->left == NULL)
  143.      (*current)->left = mknode ();
  144.    *current = (*current)->left;
  145.  }
  146.  else
  147.  {
  148.    if ((*current)->right == NULL)
  149.      (*current)->right = mknode ();
  150.    *current = (*current)->right;
  151.  }
  152. }
  153.  
  154.  
  155. static node *buildtree (bitstream code[])
  156. {
  157.  int i;
  158.  node *root = mknode ();
  159.  node *current = root;
  160.  
  161.  for (i = 0; i < 256; i++)
  162.    if (code[i].len)
  163.    {
  164.      unsigned long int bit;
  165.      int word;
  166.  
  167.      word = 3 - ((code[i].len - 1) / 32);
  168.      for (bit = 1UL << ((code[i].len - 1) % 32); bit; bit >>= 1)
  169.        traverse (¤t, (code[i].data[word] & bit) ? 1 : 0);
  170.  
  171.      for (word++; word < 4; word++)
  172.        for (bit = 0x80000000UL; bit; bit >>= 1)
  173.          traverse (¤t, (code[i].data[word] & bit) ? 1 : 0);
  174.  
  175.      current->c = i;
  176.      current = root;
  177.    }
  178.  return (root);
  179. }
  180.  
  181.  
  182. int matchbit (int bit, bitstream codes[])
  183. {
  184.  static node *root = NULL;
  185.  static node *current = NULL;
  186.  unsigned char c;
  187.  
  188.  if (bit == EOF)
  189.  {
  190.    freenodes ();
  191.    current = root = NULL;
  192.    return (-1);
  193.  }
  194.  
  195.  if (root == NULL)
  196.    current = root = buildtree (codes);
  197.  
  198.  if (bit)
  199.    current = current->left;
  200.  else
  201.    current = current->right;
  202.  
  203.  c = current->c;
  204.  
  205.  if (current->left == NULL  ||  current->right == NULL)
  206.  {
  207.    current = root;
  208.    return (c);
  209.  }
  210.  else
  211.    return (-1);
  212. }
  213.  
  214.