huffman.c

Huffman 压缩/解压算法的ANSI C实现 This archive contains a simple and readable ANSI C implementation of Huffm

/***************************************************************************
*                       Huffman Encoding and Decoding
*
*   File    : huffman.c
*   Purpose : Use huffman coding to compress/decompress files
*   Author  : Michael Dipperstein
*   Date    : November 20, 2002
*
****************************************************************************
*   UPDATES
*
*   Date        Change
*   10/21/03    Fixed one symbol file bug discovered by David A. Scott
*   10/22/03    Corrected fix above to handle decodes of file containing
*               multiples of just one symbol.
*   11/20/03    Correcly handle codes up to 256 bits (the theoretical
*               max).  With symbol counts being limited to 32 bits, 31
*               bits will be the maximum code length.
*
*   $Id: huffman.c,v 1.8 2005/05/23 03:18:04 michael Exp $
*   $Log: huffman.c,v $
*   Revision 1.8  2005/05/23 03:18:04  michael
*   Moved internal routines and definitions common to both canonical and
*   traditional Huffman coding so that they are only declared once.
*
*   Revision 1.7  2004/06/15 13:37:29  michael
*   Change function names and make static functions to allow linkage with chuffman.
*
*   Revision 1.6  2004/02/26 04:55:04  michael
*   Remove main(), allowing code to be generate linkable object file.
*
*   Revision 1.4  2004/01/13 15:49:45  michael
*   Beautify header
*
*   Revision 1.3  2004/01/13 05:45:17  michael
*   Use bit stream library.
*
*   Revision 1.2  2004/01/05 04:04:58  michael
*   Use encoded EOF instead of counting characters.
*
****************************************************************************
*
* Huffman: An ANSI C Huffman Encoding/Decoding Routine
* Copyright (C) 2002 by Michael Dipperstein ([e-mail])
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*
***************************************************************************/

/***************************************************************************
*                             INCLUDED FILES
***************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include "huflocal.h"
#include "bitarray.h"
#include "bitfile.h"

/***************************************************************************
*                            TYPE DEFINITIONS
***************************************************************************/
typedef struct code_list_t
{
    byte_t codeLen;     /* number of bits used in code (1 - 255) */
    bit_array_t *code;  /* code used for symbol (left justified) */
} code_list_t;

/***************************************************************************
*                                CONSTANTS
***************************************************************************/

/***************************************************************************
*                                 MACROS
***************************************************************************/

/***************************************************************************
*                            GLOBAL VARIABLES
***************************************************************************/

/***************************************************************************
*                               PROTOTYPES
***************************************************************************/
/* creates look up table from tree */
static int MakeCodeList(huffman_node_t *ht, code_list_t *codeList);

/* reading/writing tree to file */
static void WriteHeader(huffman_node_t *ht, bit_file_t *bfp);
static int ReadHeader(huffman_node_t **ht, bit_file_t *bfp);

/***************************************************************************
*                                FUNCTIONS
***************************************************************************/

/****************************************************************************
*   Function   : HuffmanEncodeFile
*   Description: This routine genrates a huffman tree optimized for a file
*                and writes out an encoded version of that file.
*   Parameters : inFile - Name of file to encode
*                outFile - Name of file to write a tree to
*   Effects    : File is Huffman encoded
*   Returned   : TRUE for success, otherwise FALSE.
****************************************************************************/
int HuffmanEncodeFile(char *inFile, char *outFile)
{
    huffman_node_t *huffmanTree;        /* root of huffman tree */
    code_list_t codeList[NUM_CHARS];    /* table for quick encode */
    FILE *fpIn;
    bit_file_t *bfpOut;
    int c;

    /* open binary input file and bitfile output file */
    if ((fpIn = fopen(inFile, "rb")) == NULL)
    {
        perror(inFile);
        return FALSE;
    }

    if (outFile == NULL)
    {
        bfpOut = MakeBitFile(stdout, BF_WRITE);
    }
    else
    {
        if ((bfpOut = BitFileOpen(outFile, BF_WRITE)) == NULL)
        {
            perror(outFile);
            fclose(fpIn);
            return FALSE;
        }
    }

    /* build tree */
    if ((huffmanTree = GenerateTreeFromFile(fpIn)) == NULL)
    {
        return FALSE;
    }

    /* build a list of codes for each symbol */

    /* initialize code list */
    for (c = 0; c < NUM_CHARS; c++)
    {
        codeList[c].code = NULL;
        codeList[c].codeLen = 0;
    }

    if (!MakeCodeList(huffmanTree, codeList))
    {
        return FALSE;
    }

    /* write out encoded file */

    /* write header for rebuilding of tree */
    WriteHeader(huffmanTree, bfpOut);

    /* read characters from file and write them to encoded file */
    rewind(fpIn);               /* start another pass on the input file */

    while((c = fgetc(fpIn)) != EOF)
    {
        BitFilePutBits(bfpOut,
            BitArrayGetBits(codeList[c].code),
            codeList[c].codeLen);
    }

    /* now write EOF */
    BitFilePutBits(bfpOut,
        BitArrayGetBits(codeList[EOF_CHAR].code),
        codeList[EOF_CHAR].codeLen);

    /* free the code list */
    for (c = 0; c < NUM_CHARS; c++)
    {
        if (codeList[c].code != NULL)
        {
            BitArrayDestroy(codeList[c].code);
        }
    }


    /* clean up */
    fclose(fpIn);
    BitFileClose(bfpOut);
    FreeHuffmanTree(huffmanTree);     /* free allocated memory */

    return TRUE;
}

/****************************************************************************
*   Function   : HuffmanDecodeFile
*   Description: This routine reads a Huffman coded file and writes out a
*                decoded version of that file.
*   Parameters : inFile - Name of file to decode
*                outFile - Name of file to write a tree to
*   Effects    : Huffman encoded file is decoded
*   Returned   : TRUE for success, otherwise FALSE.
****************************************************************************/
int HuffmanDecodeFile(char *inFile, char *outFile)
{
    huffman_node_t *huffmanTree, *currentNode;
    int i, c;
    bit_file_t *bfpIn;
    FILE *fpOut;

    /* open binary output file and bitfile input file */
    if ((bfpIn = BitFileOpen(inFile, BF_READ)) == NULL)
    {
        perror(inFile);
        return FALSE;
    }

    if (outFile == NULL)
    {
        fpOut = stdout;
    }
    else
    {
        if ((fpOut = fopen(outFile, "wb")) == NULL)
        {
            BitFileClose(bfpIn);
            perror(outFile);
            return FALSE;
        }
    }

    /* allocate array of leaves for all possible characters */
    for (i = 0; i < NUM_CHARS; i++)
    {
        if ((huffmanArray[i] = AllocHuffmanNode(i)) == NULL)
        {
            /* allocation failed clear existing allocations */
            for (i--; i >= 0; i--)
            {
                free(huffmanArray[i]);
            }

            BitFileClose(bfpIn);
            fclose(fpOut);
            return FALSE;
        }
    }

    /* populate leaves with frequency information from file header */
    if (!ReadHeader(huffmanArray, bfpIn))
    {
        for (i = 0; i < NUM_CHARS; i++)
        {
            free(huffmanArray[i]);
        }

        BitFileClose(bfpIn);
        fclose(fpOut);
        return FALSE;
    }

    /* put array of leaves into a huffman tree */
    if ((huffmanTree = BuildHuffmanTree(huffmanArray, NUM_CHARS)) == NULL)
    {
        FreeHuffmanTree(huffmanTree);

        BitFileClose(bfpIn);
        fclose(fpOut);
        return FALSE;
    }

    /* now we should have a tree that matches the tree used on the encode */
    currentNode = huffmanTree;

    while ((c = BitFileGetBit(bfpIn)) != EOF)
    {
        /* traverse the tree finding matches for our characters */
        if (c != 0)
        {
            currentNode = currentNode->right;
        }
        else
        {
            currentNode = currentNode->left;
        }

        if (currentNode->value != COMPOSITE_NODE)
        {
            /* we've found a character */
            if (currentNode->value == EOF_CHAR)
            {
                /* we've just read the EOF */
                break;
            }

            fputc(currentNode->value, fpOut);   /* write out character */
            currentNode = huffmanTree;          /* back to top of tree */
        }
    }

    /* close all files */
    BitFileClose(bfpIn);
    fclose(fpOut);