huffman.c

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

    FreeHuffmanTree(huffmanTree);     /* free allocated memory */

    return TRUE;
}

/****************************************************************************
*   Function   : HuffmanShowTree
*   Description: This routine genrates a huffman tree optimized for a file
*                and writes out an ASCII representation of the code
*                represented by the tree.
*   Parameters : inFile - Name of file to create tree for
*                outFile - Name of file to write a tree to
*   Effects    : Huffman tree is written out to a file
*   Returned   : TRUE for success, otherwise FALSE.
****************************************************************************/
int HuffmanShowTree(char *inFile, char *outFile)
{
    FILE *fpIn, *fpOut;
    huffman_node_t *huffmanTree;        /* root of huffman tree */
    huffman_node_t *htp;                /* pointer into tree */
    char code[NUM_CHARS - 1];           /* 1s and 0s in character's code */
    int depth = 0;                      /* depth of tree */

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

    if (outFile == NULL)
    {
        fpOut = stdout;
    }
    else
    {
        if ((fpOut = fopen(outFile, "w")) == NULL)
        {
            perror(outFile);
            fclose(fpIn);
            return FALSE;
        }
    }

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

    /* write out tree */
    /* print heading to make things look pretty (int is 10 char max) */
    fprintf(fpOut, "Char  Count      Encoding\n");
    fprintf(fpOut, "----- ---------- ----------------\n");

    htp = huffmanTree;
    for(;;)
    {
        /* follow this branch all the way left */
        while (htp->left != NULL)
        {
            code[depth] = '0';
            htp = htp->left;
            depth++;
        }

        if (htp->value != COMPOSITE_NODE)
        {
            /* handle the case of a single symbol code */
            if (depth == 0)
            {
                code[depth] = '0';
                depth++;
            }

            /* we hit a character node, print its code */
            code[depth] = '\0';

            if (htp->value != EOF_CHAR)
            {
                fprintf(fpOut, "0x%02X  %10d %s\n",
                    htp->value, htp->count, code);
            }
            else
            {
                fprintf(fpOut, "EOF   %10d %s\n", htp->count, code);
            }
        }

        while (htp->parent != NULL)
        {
            if (htp != htp->parent->right)
            {
                /* try the parent's right */
                code[depth - 1] = '1';
                htp = htp->parent->right;
                break;
            }
            else
            {
                /* parent's right tried, go up one level yet */
                depth--;
                htp = htp->parent;
                code[depth] = '\0';
            }
        }

        if (htp->parent == NULL)
        {
            /* we're at the top with nowhere to go */
            break;
        }
    }

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

    return TRUE;
}

/****************************************************************************
*   Function   : MakeCodeList
*   Description: This function uses a huffman tree to build a list of codes
*                and their length for each encoded symbol.  This simplifies
*                the encoding process.  Instead of traversing a tree to
*                in search of the code for any symbol, the code maybe found
*                by accessing cl[symbol].code.
*   Parameters : ht - pointer to root of huffman tree
*                codeList - code list to populate.
*   Effects    : Code values are filled in for symbols in a code list.
*   Returned   : TRUE for success, FALSE for failure
****************************************************************************/
static int MakeCodeList(huffman_node_t *ht, code_list_t *codeList)
{
    bit_array_t *code;
    byte_t depth = 0;

    if((code = BitArrayCreate(256)) == NULL)
    {
        perror("Unable to allocate bit array");
        return (FALSE);
    }

    BitArrayClearAll(code);

    for(;;)
    {
        /* follow this branch all the way left */
        while (ht->left != NULL)
        {
            BitArrayShiftLeft(code, 1);
            ht = ht->left;
            depth++;
        }

        if (ht->value != COMPOSITE_NODE)
        {
            /* enter results in list */
            codeList[ht->value].codeLen = depth;
            codeList[ht->value].code = BitArrayDuplicate(code);
            if (codeList[ht->value].code == NULL)
            {
                perror("Unable to allocate bit array");
                BitArrayDestroy(code);
                return (FALSE);
            }

            /* now left justify code */
            BitArrayShiftLeft(codeList[ht->value].code, 256 - depth);
        }

        while (ht->parent != NULL)
        {
            if (ht != ht->parent->right)
            {
                /* try the parent's right */
                BitArraySetBit(code, 255);
                ht = ht->parent->right;
                break;
            }
            else
            {
                /* parent's right tried, go up one level yet */
                depth--;
                BitArrayShiftRight(code, 1);
                ht = ht->parent;
            }
        }

        if (ht->parent == NULL)
        {
            /* we're at the top with nowhere to go */
            break;
        }
    }

    BitArrayDestroy(code);
    return (TRUE);
}

/****************************************************************************
*   Function   : WriteHeader
*   Description: This function writes the each symbol contained in a tree
*                as well as its number of occurrences in the original file
*                to the specified output file.  If the same algorithm that
*                produced the original tree is used with these counts, an
*                exact copy of the tree will be produced.
*   Parameters : ht - pointer to root of huffman tree
*                bfp - pointer to open binary file to write to.
*   Effects    : Symbol values and symbol counts are written to a file.
*   Returned   : None
****************************************************************************/
static void WriteHeader(huffman_node_t *ht, bit_file_t *bfp)
{
    int i;

    for(;;)
    {
        /* follow this branch all the way left */
        while (ht->left != NULL)
        {
            ht = ht->left;
        }

        if ((ht->value != COMPOSITE_NODE) &&
            (ht->value != EOF_CHAR))
        {
            /* write symbol and count to header */
            BitFilePutChar(ht->value, bfp);
            BitFilePutBits(bfp, (void *)&(ht->count), 8 * sizeof(count_t));
        }

        while (ht->parent != NULL)
        {
            if (ht != ht->parent->right)
            {
                ht = ht->parent->right;
                break;
            }
            else
            {
                /* parent's right tried, go up one level yet */
                ht = ht->parent;
            }
        }

        if (ht->parent == NULL)
        {
            /* we're at the top with nowhere to go */
            break;
        }
    }

    /* now write end of table char 0 count 0 */
    BitFilePutChar(0, bfp);
    for(i = 0; i < sizeof(count_t); i++)
    {
        BitFilePutChar(0, bfp);
    }
}

/****************************************************************************
*   Function   : ReadHeader
*   Description: This function reads the header information stored by
*                WriteHeader.  If the same algorithm that produced the
*                original tree is used with these counts, an exact copy of
*                the tree will be produced.
*   Parameters : ht - pointer to array of pointers to tree leaves
*                inFile - file to read from
*   Effects    : Frequency information is read into the node of ht
*   Returned   : TRUE for success, otherwise FALSE
****************************************************************************/
static int ReadHeader(huffman_node_t **ht, bit_file_t *bfp)
{
    count_t count;
    int c;
    int status = FALSE;     /* in case of premature EOF */

    while ((c = BitFileGetChar(bfp)) != EOF)
    {
        BitFileGetBits(bfp, (void *)(&count), 8 * sizeof(count_t));

        if ((count == 0) && (c == 0))
        {
            /* we just read end of table marker */
            status = TRUE;
            break;
        }

        ht[c]->count = count;
        ht[c]->ignore = FALSE;
    }

    /* add assumed EOF */
    ht[EOF_CHAR]->count = 1;
    ht[EOF_CHAR]->ignore = FALSE;

    if (status == FALSE)
    {
        /* we hit EOF before we read a full header */
        fprintf(stderr, "error: malformed file header.\n");
    }

    return status;
}