huffman.c

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

                   hsize,
                   ipos,
                   opos,
                   cpos,
                   c,
                   i;

unsigned char      *comp,
                   *temp;

/*****************************************************************************
*                                                                            *
*  Initially there is no buffer of compressed data.                          *
*                                                                            *
*****************************************************************************/

*compressed = NULL;

/*****************************************************************************
*                                                                            *
*  Get the frequency of each symbol in the original data.                    *
*                                                                            *
*****************************************************************************/

for (c = 0; c <= UCHAR_MAX; c++)
   freqs[c] = 0;

ipos = 0;

if (size > 0) {

   while (ipos < size) {

      freqs[original[ipos]]++;
      ipos++;

   }

}

/*****************************************************************************
*                                                                            *
*  Scale the frequencies to fit into one byte.                               *
*                                                                            *
*****************************************************************************/

max = UCHAR_MAX;

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

   if (freqs[c] > max)
      max = freqs[c];

}

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

   scale = (int)(freqs[c] / ((double)max / (double)UCHAR_MAX));

   if (scale == 0 && freqs[c] != 0)
      freqs[c] = 1;
   else
      freqs[c] = scale;

}

/*****************************************************************************
*                                                                            *
*  Build the Huffman tree and table of codes for the data.                   *
*                                                                            *
*****************************************************************************/

if (build_tree(freqs, &tree) != 0)
   return -1;

for (c = 0; c <= UCHAR_MAX; c++)
   memset(&table[c], 0, sizeof(HuffCode));

build_table(bitree_root(tree), 0x0000, 0, table);

bitree_destroy(tree);
free(tree);

/*****************************************************************************
*                                                                            *
*  Write the header information.                                             *
*                                                                            *
*****************************************************************************/

hsize = sizeof(int) + (UCHAR_MAX + 1);

if ((comp = (unsigned char *)malloc(hsize)) == NULL)
   return -1;

memcpy(comp, &size, sizeof(int));

for (c = 0; c <= UCHAR_MAX; c++)
   comp[sizeof(int) + c] = (unsigned char)freqs[c];

/*****************************************************************************
*                                                                            *
*  Compress the data.                                                        *
*                                                                            *
*****************************************************************************/

ipos = 0;
opos = hsize * 8;

while (ipos < size) {

   /**************************************************************************
   *                                                                         *
   *  Get the next symbol in the original data.                              *
   *                                                                         *
   **************************************************************************/

   c = original[ipos];

   /**************************************************************************
   *                                                                         *
   *  Write the code for the symbol to the buffer of compressed data.        *
   *                                                                         *
   **************************************************************************/

   for (i = 0; i < table[c].size; i++) {

      if (opos % 8 == 0) {

         /********************************************************************
         *                                                                   *
         *  Allocate another byte for the buffer of compressed data.         *
         *                                                                   *
         ********************************************************************/

         if ((temp = (unsigned char *)realloc(comp,(opos / 8) + 1)) == NULL) {

            free(comp);
            return -1;

         }

         comp = temp;

      }

      cpos = (sizeof(short) * 8) - table[c].size + i;
      bit_set(comp, opos, bit_get((unsigned char *)&table[c].code, cpos));
      opos++;

   }

   ipos++;

}

/*****************************************************************************
*                                                                            *
*  Point to the buffer of compressed data.                                   *
*                                                                            *
*****************************************************************************/

*compressed = comp;

/*****************************************************************************
*                                                                            *
*  Return the number of bytes in the compressed data.                        *
*                                                                            *
*****************************************************************************/

return ((opos - 1) / 8) + 1;

}

/*****************************************************************************
*                                                                            *
*  -------------------------- huffman_uncompress --------------------------  *
*                                                                            *
*****************************************************************************/

int huffman_uncompress(const unsigned char *compressed, unsigned char
   **original) {

BiTree             *tree;
BiTreeNode         *node;

int                freqs[UCHAR_MAX + 1],
                   hsize,
                   size,
                   ipos,
                   opos,
                   state,
                   c;

unsigned char      *orig,
                   *temp;

/*****************************************************************************
*                                                                            *
*  Initially there is no buffer of original data.                            *
*                                                                            *
*****************************************************************************/

*original = orig = NULL;

/*****************************************************************************
*                                                                            *
*  Get the header information from the buffer of compressed data.            *
*                                                                            *
*****************************************************************************/

hsize = sizeof(int) + (UCHAR_MAX + 1);
memcpy(&size, compressed, sizeof(int));

for (c = 0; c <= UCHAR_MAX; c++)
   freqs[c] = compressed[sizeof(int) + c];

/*****************************************************************************
*                                                                            *
*  Rebuild the Huffman tree used previously to compress the data.            *
*                                                                            *
*****************************************************************************/

if (build_tree(freqs, &tree) != 0)
   return -1;

/*****************************************************************************
*                                                                            *
*  Uncompress the data.                                                      *
*                                                                            *
*****************************************************************************/

ipos = hsize * 8;
opos = 0;
node = bitree_root(tree);

while (opos < size) {

   /**************************************************************************
   *                                                                         *
   *  Get the next bit in the compressed data.                               *
   *                                                                         *
   **************************************************************************/

   state = bit_get(compressed, ipos);
   ipos++;

   if (state == 0) {

      /***********************************************************************
      *                                                                      *
      *  Move to the left.                                                   *
      *                                                                      *
      ***********************************************************************/

      if (bitree_is_eob(node) || bitree_is_eob(bitree_left(node))) {

         bitree_destroy(tree);
         free(tree);
         return -1;

         }

      else
         node = bitree_left(node);

      }

   else {

      /***********************************************************************
      *                                                                      *
      *  Move to the right.                                                  *
      *                                                                      *
      ***********************************************************************/

      if (bitree_is_eob(node) || bitree_is_eob(bitree_right(node))) {

         bitree_destroy(tree);
         free(tree);
         return -1;

         }

      else
         node = bitree_right(node);

   }

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

      /***********************************************************************
      *                                                                      *
      *  Write the symbol in the leaf node to the buffer of original data.   *
      *                                                                      *
      ***********************************************************************/

      if (opos > 0) {

         if ((temp = (unsigned char *)realloc(orig, opos + 1)) == NULL) {

            bitree_destroy(tree);
            free(tree);
            free(orig);
            return -1;

         }

         orig = temp;

         }

      else {

         if ((orig = (unsigned char *)malloc(1)) == NULL) {

            bitree_destroy(tree);
            free(tree);
            return -1;

         }

      }

      orig[opos] = ((HuffNode *)bitree_data(node))->symbol;
      opos++;

      /***********************************************************************
      *                                                                      *
      *  Move back to the top of the tree.                                   *
      *                                                                      *
      ***********************************************************************/

      node = bitree_root(tree);

   }

}

bitree_destroy(tree);
free(tree);

/*****************************************************************************
*                                                                            *
*  Point to the buffer of original data.                                     *
*                                                                            *
*****************************************************************************/

*original = orig;

/*****************************************************************************
*                                                                            *
*  Return the number of bytes in the original data.                          *
*                                                                            *
*****************************************************************************/

return opos;

}