chuffman.c

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

****************************************************************************/
int CHuffmanShowTree(char *inFile, char *outFile)
{
    FILE *fpIn, *fpOut;
    huffman_node_t *huffmanTree;        /* root of huffman tree */
    int i, length;

    /* 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;
    }

    /* use tree to generate a canonical code */
    if (!BuildCanonicalCode(huffmanTree, canonicalList))
    {
        fclose(fpIn);
        fclose(fpOut);
        FreeHuffmanTree(huffmanTree);     /* free allocated memory */
        return FALSE;
    }

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

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

    for(i = 0; i < NUM_CHARS; i++)
    {
        if(canonicalList[i].codeLen > 0)
        {
            if (canonicalList[i].value != EOF_CHAR)
            {
                fprintf(fpOut,
                        "0x%02X  %02d       ",
                        canonicalList[i].value, canonicalList[i].codeLen);
            }
            else
            {
                fprintf(fpOut,
                        "EOF   %02d       ", canonicalList[i].codeLen);
            }

            /* now write out the code bits */
            for(length = 0; length < canonicalList[i].codeLen; length++)
            {
                if (BitArrayTestBit(canonicalList[i].code, length))
                {
                    fputc('1', fpOut);
                }
                else
                {
                    fputc('0', fpOut);
                }
            }

            fputc('\n', fpOut);
        }
    }

    /* clean up */
    fclose(fpIn);
    fclose(fpOut);

    return TRUE;
}

/****************************************************************************
*   Function   : CompareByCodeLen
*   Description: Compare function to be used by qsort for sorting canonical
*                list items by code length.  In the event of equal lengths,
*                the symbol value will be used.
*   Parameters : item1 - pointer canonical list item
*                item2 - pointer canonical list item
*   Effects    : None
*   Returned   : 1 if item1 > item2
*                -1 if item1 < item 2
*                0 if something went wrong (means item1 == item2)
****************************************************************************/
static int CompareByCodeLen(const void *item1, const void *item2)
{
    if (((canonical_list_t *)item1)->codeLen >
        ((canonical_list_t *)item2)->codeLen)
    {
        /* item1 > item2 */
        return 1;
    }
    else if (((canonical_list_t *)item1)->codeLen <
        ((canonical_list_t *)item2)->codeLen)
    {
        /* item1 < item2 */
        return -1;
    }
    else
    {
        /* both have equal code lengths break the tie using value */
        if (((canonical_list_t *)item1)->value >
            ((canonical_list_t *)item2)->value)
        {
            return 1;
        }
        else
        {
            return -1;
        }
    }

    return 0;   /* we should never get here */
}

/****************************************************************************
*   Function   : CompareBySymbolValue
*   Description: Compare function to be used by qsort for sorting canonical
*                list items by symbol value.
*   Parameters : item1 - pointer canonical list item
*                item2 - pointer canonical list item
*   Effects    : None
*   Returned   : 1 if item1 > item2
*                -1 if item1 < item 2
****************************************************************************/
static int CompareBySymbolValue(const void *item1, const void *item2)
{
    if (((canonical_list_t *)item1)->value >
        ((canonical_list_t *)item2)->value)
    {
        /* item1 > item2 */
        return 1;
    }

    /* it must be the case that item1 < item2 */
    return -1;
}

/****************************************************************************
*   Function   : BuildCanonicalCode
*   Description: This function builds a canonical Huffman code from a
*                Huffman tree.
*   Parameters : ht - pointer to root of tree
*                cl - pointer to canonical list
*   Effects    : cl is filled with the canonical codes sorted by the value
*                of the charcter to be encode.
*   Returned   : TRUE for success, FALSE for failure
****************************************************************************/
static int BuildCanonicalCode(huffman_node_t *ht, canonical_list_t *cl)
{
    int i;
    byte_t depth = 0;

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

    /* fill list with code lengths (depth) from tree */
    for(;;)
    {
        /* follow this branch all the way left */
        while (ht->left != NULL)
        {
            ht = ht->left;
            depth++;
        }

        if (ht->value != COMPOSITE_NODE)
        {
            /* handle one symbol trees */
            if (depth == 0)
            {
                depth++;
            }

            /* enter results in list */
            cl[ht->value].codeLen = depth;
        }

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

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

    /* sort by code length */
    qsort(cl, NUM_CHARS, sizeof(canonical_list_t), CompareByCodeLen);

    if (AssignCanonicalCodes(cl))
    {
        /* re-sort list in lexical order for use by encode algorithm */
        qsort(cl, NUM_CHARS, sizeof(canonical_list_t), CompareBySymbolValue);
        return TRUE;    /* success */
    }

    perror("Code assignment failed");
    return FALSE;       /* assignment failed */
}

/****************************************************************************
*   Function   : AssignCanonicalCode
*   Description: This function accepts a list of symbols sorted by their
*                code lengths, and assigns a canonical Huffman code to each
*                symbol.
*   Parameters : cl - sorted list of symbols to have code values assigned
*   Effects    : cl stores a list of canonical codes sorted by the length
*                of the code used to encode the symbol.
*   Returned   : TRUE for success, FALSE for failure
****************************************************************************/
static int AssignCanonicalCodes(canonical_list_t *cl)
{
    int i;
    byte_t length;
    bit_array_t *code;

    /* assign the new codes */
    code = BitArrayCreate(256);
    BitArrayClearAll(code);

    length = cl[(NUM_CHARS - 1)].codeLen;

    for(i = (NUM_CHARS - 1); i >= 0; i--)
    {
        /* bail if we hit a zero len code */
        if (cl[i].codeLen == 0)
        {
            break;
        }

        /* adjust code if this length is shorter than the previous */
        if (cl[i].codeLen < length)
        {
            BitArrayShiftRight(code, (length - cl[i].codeLen));
            length = cl[i].codeLen;
        }

        /* assign left justified code */
        if ((cl[i].code = BitArrayDuplicate(code)) == NULL)
        {
            perror("Duplicating code");
            BitArrayDestroy(code);
            return FALSE;
        }

        BitArrayShiftLeft(cl[i].code, 256 - length);

        BitArrayIncrement(code);
    }

    BitArrayDestroy(code);
    return TRUE;
}

/****************************************************************************
*   Function   : WriteHeader
*   Description: This function writes the code size for each symbol and the
*                total number of characters in the original file to the
*                specified output file.  If the same algorithm that produced
*                produced the original canonical code is used with these code
*                lengths, an exact copy of the code will be produced.
*   Parameters : cl - pointer to list of canonical Huffman codes
*                bfp - pointer to open binary file to write to.
*   Effects    : Symbol code lengths and symbol count are written to the
*                output file.
*   Returned   : None
****************************************************************************/
static void WriteHeader(canonical_list_t *cl, bit_file_t *bfp)
{
    int i;

    /* write out code size for each symbol */
    for (i = 0; i < NUM_CHARS; i++)
    {
        BitFilePutChar(cl[i].codeLen, 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 : cl - pointer to list of canonical Huffman codes
*                bfp - file to read from
*   Effects    : Code lengths and symbols are read into the canonical list.
*                Total number of symbols encoded is store in totalCount
*   Returned   : TRUE on success, otherwise FALSE.
****************************************************************************/
static int ReadHeader(canonical_list_t *cl, bit_file_t *bfp)
{
    int c;
    int i;

    /* read the code length */
    for (i = 0; i < NUM_CHARS; i++)
    {
        c = BitFileGetChar(bfp);

        if (c != EOF)
        {
            cl[i].value = i;
            cl[i].codeLen = (byte_t)c;
        }
        else
        {
            fprintf(stderr, "error: malformed file header.\n");
            return FALSE;
        }
    }

    return TRUE;
}