Simple and fast Huffman coding

• Download demo project - 74.7 Kb
• Download source - 13.9 Kb

Introduction

This article describes the simplest and fastest Huffman code you can find in the net, not using any external library like STL or components, just using simple C functions like: memset, memmove, qsort, malloc, realloc, and memcpy.

So, any one will find it easy to understand the code or even to modify it.

Background

Huffman compression is a lossless compression algorithm that is ideal for compressing text or program files. Huffman compression belongs into a family of algorithms with a variable codeword length. That means that individual symbols (characters in a text file, for instance) are replaced by bit sequences that have a distinct length. So, symbols that occur a lot in a file are given a short sequence while others that are used seldom get a longer bit sequence.

Using the code

I wrote the code as simple C functions to make it easy to use anywhere. You can put them in a class or just use the function. And I made it in a simple format, just in and out buffer, no input or output files like in many articles.

    bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);
    bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen);

Points of Interest

Speed

I spent a long time to make it (huffman.cpp) so fast and at the same time I don't use any libraries like STL or MFC. It compresses 16 MB in less than 1 sec (PIII processor, 1G speed).

Compression

The compression code is so simple, it starts by initializing 511 of Huffman nodes by its ASCII values:

    CHuffmanNode nodes[511];
    for(int nCount = 0; nCount < 256; nCount++)
        nodes[nCount].byAscii = nCount;

Then, it calculates each ASCII frequency in the input buffer:

    for(nCount = 0; nCount < nSrcLen; nCount++)
        nodes[pSrc[nCount]].nFrequency++;

Then, it sorts ASCII characters depending on frequency:

    qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);

Now, it constructs Huffman tree, to get each ASCII code bit that will be replaced in the output buffer:

    int nNodeCount = GetHuffmanTree(nodes);

Constructing Huffman tree is so simple; it is just putting all nodes in a queue, and replacing the two lowest frequency nodes with one node that has the sum of their frequencies so that this new node will be the parent of these two nodes. And do this step till the queue just contains one node (tree root).

    // parent node
    pNode = &nodes[nParentNode++];
    // pop first child
    pNode->pLeft = PopNode(pNodes, nBackNode--, false);
    // pop second child
    pNode->pRight = PopNode(pNodes, nBackNode--, true);
    // adjust parent of the two poped nodes
    pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
    // adjust parent frequency
    pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

I made a good trick here to avoid using any queue module. I knew before that ASCII is 256 characters, but I allocated 511 (CHuffmanNode nodes[511];), and made use of the 255 nodes after the first 256 to be used as the parents in the Huffman tree. And just use an array of points (CHuffmanNode* pNodes[256]) to point to these nodes at the time of constructing the tree. Also, use two variables to handle queue indexing (int nParentNode = nNodeCount, nBackNode = nNodeCount-1;).

Then, the final step in the compression is to write each ASCII code in the output buffer:

    int nDesIndex = 0;
    // loop to write codes
    for(nCount = 0; nCount < nSrcLen; nCount++)
    {
        *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= 
                  nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
        nDesIndex += nodes[pSrc[nCount]].nCodeLength;
    }

• (nDesIndex>>3): >>3 to divide by 8 to reach the right byte to start with.
• (nDesIndex&7): &7 to get the remainder of dividing by 8, to get the start bit.

Note: at the compressed buffer, we should save Huffman tree nodes with its frequencies so we can construct Huffman tree again at the time of decompression (just the ASCIIs that have a frequency).

Decompression

The decompression is more easier as we just need to construct Huffman tree, then loop in the input buffer to replace each code with its ASCII. Just remember that the input buffer, in this case, is a stream of bits that contain the codes of each ASCII. So, to replace the code with the ASCII, we need to iterate Huffman tree with the bit stream till we find a leaf. Then, we can append its ASCII at the output buffer:

    int nDesIndex = 0;
    DWORD nCode;
    while(nDesIndex < nDesLen)
    {
        nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
        pNode = pRoot;
        while(pNode->pLeft)
        {
            pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
            nCode >>= 1;
            nSrcIndex++;
        }
        pDes[nDesIndex++] = pNode->byAscii;
    }

• (nSrcIndex>>3): >>3 to divide by 8 to reach the right byte to start with.
• (nSrcIndex&7): &7 to get the remainder of dividing by 8, to get the start bit.

Source code files

• huffman.cpp,
• huffman.h.

Updates

• 1-1-2005:
  • Increasing compression speed by replacing:

        dwCode = nodes[pSrc[nCount]].dwCode;
        nCodeLength = nodes[pSrc[nCount]].nCodeLength;
        while(nCodeLength--)
        {
            if(dwCode&1)
                SetBit(pDesPtr, nDesIndex);
            dwCode >>= 1, nDesIndex++;
        }

    with

        *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= 
              nodes[pSrc[nCount]].dwCode << (nDesIndex&7);

    at the compression function, so I avoided the use of SetBit macro which was slow to be done in a loop.

  • Increasing decompression speed by replacing:

        while(pNode->pLeft)    // if node has pLeft then it must has pRight
        {
            // node not leaf
            pNode = GetBit(pSrc, nSrcIndex) ? pNode->pRight : pNode->pLeft;
            nSrcIndex++;
        }

    with

        nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
        while(pNode->pLeft)    // if node has pLeft then it must has pRight
        {
            // node not leaf
            pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
            nCode >>= 1;
            nSrcIndex++;
        }

    at the decompression function, so I avoided the use of GetBit macro which was slow to be done in a loop.

Thanks to...

I owe a lot to my colleagues for helping me in implementing and testing this code. (JAK)