huffman.c

掌握如何用C来实现各种算法

/*****************************************************************************
*                                                                            *
*  ------------------------------- huffman.c ------------------------------  *
*                                                                            *
*****************************************************************************/

#include <limits.h>
#include <netinet/in.h>
#include <stdlib.h>
#include <string.h>

#include "bit.h"
#include "bitree.h"
#include "compress.h"
#include "pqueue.h"

/*****************************************************************************
*                                                                            *
*  ----------------------------- compare_freq -----------------------------  *
*                                                                            *
*****************************************************************************/

static int compare_freq(const void *tree1, const void *tree2) {

HuffNode           *root1,
                   *root2;

/*****************************************************************************
*                                                                            *
*  Compare the frequencies stored in the root nodes of two binary trees.     *
*                                                                            *
*****************************************************************************/

root1 = (HuffNode *)bitree_data(bitree_root((const BiTree *)tree1));
root2 = (HuffNode *)bitree_data(bitree_root((const BiTree *)tree2));

if (root1->freq < root2->freq)
   return 1;
else if (root1->freq > root2->freq)
   return -1;
else
   return 0;

}

/*****************************************************************************
*                                                                            *
*  ----------------------------- destroy_tree -----------------------------  *
*                                                                            *
*****************************************************************************/

static void destroy_tree(void *tree) {

/*****************************************************************************
*                                                                            *
*  Destroy and free one binary tree from the priority queue of trees.        *
*                                                                            *
*****************************************************************************/

bitree_destroy(tree);
free(tree);

return;

}

/*****************************************************************************
*                                                                            *
*  ------------------------------ build_tree ------------------------------  *
*                                                                            *
*****************************************************************************/

static int build_tree(int *freqs, BiTree **tree) {

BiTree             *init,
                   *merge,
                   *left,
                   *right;

PQueue             pqueue;

HuffNode           *data;

int                size,
                   c;

/*****************************************************************************
*                                                                            *
*  Initialize the priority queue of binary trees.                            *
*                                                                            *
*****************************************************************************/

*tree = NULL;

pqueue_init(&pqueue, compare_freq, destroy_tree);

for (c = 0; c <= UCHAR_MAX; c++) {

   if (freqs[c] != 0) {

      /***********************************************************************
      *                                                                      *
      *  Set up a binary tree for the current symbol and its frequency.      *
      *                                                                      *
      ***********************************************************************/

      if ((init = (BiTree *)malloc(sizeof(BiTree))) == NULL) {

         pqueue_destroy(&pqueue);
         return -1;

      }

      bitree_init(init, free);

      if ((data = (HuffNode *)malloc(sizeof(HuffNode))) == NULL) {

         pqueue_destroy(&pqueue);
         return -1;

      }

      data->symbol = c;
      data->freq = freqs[c];

      if (bitree_ins_left(init, NULL, data) != 0) {

         free(data);
         bitree_destroy(init);
         free(init);
         pqueue_destroy(&pqueue);
         return -1;

      }

      /***********************************************************************
      *                                                                      *
      *  Insert the binary tree into the priority queue.                     *
      *                                                                      *
      ***********************************************************************/

      if (pqueue_insert(&pqueue, init) != 0) {

         bitree_destroy(init);
         free(init);
         pqueue_destroy(&pqueue);
         return -1;

      }

   }

}

/*****************************************************************************
*                                                                            *
*  Build a Huffman tree by merging trees in the priority queue.              *
*                                                                            *
*****************************************************************************/

size = pqueue_size(&pqueue);

for (c = 1; c <= size - 1; c++) {

   /**************************************************************************
   *                                                                         *
   *  Allocate storage for the next merged tree.                             *
   *                                                                         *
   **************************************************************************/

   if ((merge = (BiTree *)malloc(sizeof(BiTree))) == NULL) {

      pqueue_destroy(&pqueue);
      return -1;

   }

   /**************************************************************************
   *                                                                         *
   *  Extract the two trees whose root nodes have the smallest frequencies.  *
   *                                                                         *
   **************************************************************************/

   if (pqueue_extract(&pqueue, (void **)&left) != 0) {

      pqueue_destroy(&pqueue);
      free(merge);
      return -1;

   }

   if (pqueue_extract(&pqueue, (void **)&right) != 0) {

      pqueue_destroy(&pqueue);
      free(merge);
      return -1;

   }

   /**************************************************************************
   *                                                                         *
   *  Allocate storage for the data in the root node of the merged tree.     *
   *                                                                         *
   **************************************************************************/

   if ((data = (HuffNode *)malloc(sizeof(HuffNode))) == NULL) {

      pqueue_destroy(&pqueue);
      free(merge);
      return -1;

   }

   memset(data, 0, sizeof(HuffNode));

   /**************************************************************************
   *                                                                         *
   *  Sum the frequencies in the root nodes of the trees being merged.       *
   *                                                                         *
   **************************************************************************/

   data->freq = ((HuffNode *)bitree_data(bitree_root(left)))->freq +
      ((HuffNode *)bitree_data(bitree_root(right)))->freq;

   /**************************************************************************
   *                                                                         *
   *  Merge the two trees.                                                   *
   *                                                                         *
   **************************************************************************/

   if (bitree_merge(merge, left, right, data) != 0) {

      pqueue_destroy(&pqueue);
      free(merge);
      return -1;

   }

   /**************************************************************************
   *                                                                         *
   *  Insert the merged tree into the priority queue and free the others.    *
   *                                                                         *
   **************************************************************************/

   if (pqueue_insert(&pqueue, merge) != 0) {

      pqueue_destroy(&pqueue);
      bitree_destroy(merge);
      free(merge);
      return -1;

   }

   free(left);
   free(right);

}

/*****************************************************************************
*                                                                            *
*  The last tree in the priority queue is the Huffman tree.                  *
*                                                                            *
*****************************************************************************/

if (pqueue_extract(&pqueue, (void **)tree) != 0) {

   pqueue_destroy(&pqueue);
   return -1;

   }

else {

   pqueue_destroy(&pqueue);

}

return 0;

}

/*****************************************************************************
*                                                                            *
*  ------------------------------ build_table -----------------------------  *
*                                                                            *
*****************************************************************************/

static void build_table(BiTreeNode *node, unsigned short code, unsigned char
   size, HuffCode *table) {

if (!bitree_is_eob(node)) {

   if (!bitree_is_eob(bitree_left(node))) {

      /***********************************************************************
      *                                                                      *
      *  Move to the left and append 0 to the current code.                  *
      *                                                                      *
      ***********************************************************************/

      build_table(bitree_left(node), code << 1, size + 1, table);

   }

   if (!bitree_is_eob(bitree_right(node))) {

      /***********************************************************************
      *                                                                      *
      *  Move to the right and append 1 to the current code.                 *
      *                                                                      *
      ***********************************************************************/

      build_table(bitree_right(node), (code << 1) | 0x0001, size + 1, table);

   }

   if (bitree_is_eob(bitree_left(node))&&bitree_is_eob(bitree_right(node))) {

      /***********************************************************************
      *                                                                      *
      *  Ensure that the current code is in big-endian format.               *
      *                                                                      *
      ***********************************************************************/

      code = htons(code);

      /***********************************************************************
      *                                                                      *
      *  Assign the current code to the symbol in the leaf node.             *
      *                                                                      *
      ***********************************************************************/

      table[((HuffNode *)bitree_data(node))->symbol].used = 1;
      table[((HuffNode *)bitree_data(node))->symbol].code = code;
      table[((HuffNode *)bitree_data(node))->symbol].size = size;

   }

}

return;

}

/*****************************************************************************
*                                                                            *
*  --------------------------- huffman_compress ---------------------------  *
*                                                                            *
*****************************************************************************/

int huffman_compress(const unsigned char *original, unsigned char
   **compressed, int size) {

BiTree             *tree;
HuffCode           table[UCHAR_MAX + 1];

int                freqs[UCHAR_MAX + 1],
                   max,
                   scale,