rangecoder.cpp

// Range coder
// 
// Simplified code as example for the range coding.
//
// by feyd//godX.de
 
#include <stdint.h>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <math.h>
 
class CRangeCoder
{
public:
    CRangeCoder(int nRangeBits=31) : 
        m_nRangeMax(1<<nRangeBits), m_nRangeMin(1<<(nRangeBits-1)), 
        m_nRange(1<<nRangeBits), m_nValue(0),
        m_nCarry(0), m_nCarryPos(0), m_nBitCount(0) {}
    virtual ~CRangeCoder() {}
 
    void AddCode(uint32_t nCode, uint32_t nMax)
    {
        uint32_t nBase = (m_nRange/nMax)*nCode;
        m_nValue += nBase;
        if(m_nValue>=m_nRangeMax) // Overflow
        {
            m_nValue %= m_nRangeMax;
            m_nCarry++;
        }
    }
 
    uint32_t GetCode(uint32_t nMax)
    {
        return m_nValue/(m_nRange/nMax);
    }
 
    void CommitRangeWrite(uint32_t nRange, uint32_t nMax)
    {
        m_nRange = (m_nRange/nMax)*nRange;
        while(m_nRange<=m_nRangeMin) // Range underflow -> normalize
        {
            AddOutput(m_nValue/m_nRangeMin);
            m_nValue %= m_nRangeMin;
            m_nValue <<= 1;
            m_nRange <<= 1;
        }
    }
 
    void CommitRangeRead(uint32_t nBase, uint32_t nRange, uint32_t nMax)
    {
        m_nValue -= (m_nRange/nMax)*nBase;
        m_nRange = (m_nRange/nMax)*nRange;
        while(m_nRange<=m_nRangeMin) // Range underflow -> normalize
        {
            // Load next bit here
            m_nValue <<= 1;
            m_nRange <<= 1;
        }
    }
 
    void CarryOutput()
    {
        if(m_nCarryPos==0)
            return;
 
        m_nCarryPos--;
        printf("%d", (m_nCarry>>m_nCarryPos)&1);
        m_nBitCount++;
        if((m_nBitCount&3)==0)
            printf(" ");
    }
 
    void AddOutput(uint32_t nValue)
    {
        if(m_nCarryPos==32)
            CarryOutput();
        m_nCarry <<= 1;
        m_nCarry |= nValue;
        m_nCarryPos++;
    }
 
    void Flush()
    {
        // Commit unsaved range  
        uint32_t nRange = m_nRange;
        while(nRange!=m_nRangeMax)
        {
            CommitRangeWrite(1, 2);
            if(nRange>=m_nRangeMin)
                break;
            nRange <<= 8;
        }
 
        // Write out all bits in buffer
        while(m_nCarryPos>0)
            CarryOutput();
    }
 
    int GetBitCount() const { return m_nBitCount; }
private:
    uint32_t m_nRangeMax;
    uint32_t m_nRangeMin;
    uint32_t m_nRange;
    uint32_t m_nValue;
    uint32_t m_nCarry;
    int m_nCarryPos;
    int m_nBitCount;
};
 
class CHistogram
{
    struct Histogram
    {
        int nBase;
        int nCount;
    };
 
public:
    CHistogram(CRangeCoder* pRangeCoder, size_t nSymbols) : 
        m_nSymbols(nSymbols), m_histogram(nSymbols), 
        m_pRangeCoder(pRangeCoder), m_nMax(0) {}
    virtual ~CHistogram() {}
 
    void Build(const std::vector<int>& codes)
    {
        // Clear histogram
        for(size_t n=0; n<m_histogram.size(); n++)
        {
            m_histogram[n].nBase = 0;
            m_histogram[n].nCount = 0;
        }
 
        // Build histogram
        for(size_t n=0; n<codes.size(); n++)
        {
            if(codes[n]>=(int)m_nSymbols)
            {
                printf("Error not enough symbols\r\n");
                return;
            }
            m_histogram[codes[n]].nCount++;
        }
 
        // Build bases
        m_nMax = 0;
        for(size_t n=0; n<m_histogram.size(); n++)
        {
            m_histogram[n].nBase = m_nMax;
            m_nMax += m_histogram[n].nCount;
        }
    }
 
    void Encode(const std::vector<int>& codes)
    {
        printf(" Encoded:\r\n   ");
        float fSymbolSizeIn = log((float)m_nSymbols)/log(2.0f);
        for(size_t n=0; n<codes.size(); n++)
        {
            m_pRangeCoder->AddCode(m_histogram[codes[n]].nBase, m_nMax);
            m_pRangeCoder->CommitRangeWrite(m_histogram[codes[n]].nCount, m_nMax);
        }
        m_pRangeCoder->Flush();
 
        printf("\r\n\r\n");
        int nBitsOut = m_pRangeCoder->GetBitCount();
        printf(" Bits in: %.0fx%d=%.0f Bits out: %d = %3.3f bits/code entropy\r\n", fSymbolSizeIn, (int)codes.size(), fSymbolSizeIn*(float)codes.size(), nBitsOut, (float)nBitsOut/(float)codes.size());
 
        // Theoretical entropy
        int nMaxCount = 0;
        for(size_t n=0; n<m_nSymbols; n++)
            nMaxCount+=m_histogram[n].nCount;
 
        float fBits = 0;
        for(size_t n=0; n<m_nSymbols; n++)
        {       
            if(m_histogram[n].nCount==0)
                continue;
 
            fBits += (float)m_histogram[n].nCount*(log((float)m_histogram[n].nCount/(float)nMaxCount)/-log(2.0f));
        }
        printf(" Theoretical lower bound for entropy is: %3.3f bits = %3.3f bits/code\r\n", fBits, fBits/(float)codes.size());
    }
 
    void Print()
    {
        printf(" Tables:\r\n");
        for(size_t n=0; n<m_nSymbols; n++)
        {
            if(m_histogram[n].nCount==0)
                continue;
            printf(" %5d (%c). %d", (int)n, (n<32 || n>=128)?'.':(char)n, m_histogram[n].nCount);
            printf("\r\n");
        }
        printf("\r\n");
    }
 
protected:
    size_t m_nSymbols;
    std::vector<Histogram> m_histogram;
    CRangeCoder* m_pRangeCoder;
    int m_nMax;
};
 
// Application entry point (from libc)
int main(int argc, const char* argv[])
{
    printf("Range coder test...\r\n\r\n");
 
    if(argc<2)
    {
        printf("Not enough parameters.\r\n");
        return -1;
    }
    std::vector<int> codes;
    for(size_t n=0; n<strlen(argv[1]); n++)
        codes.push_back(argv[1][n]);
 
    CRangeCoder rangeOut;
    CHistogram histogram(&rangeOut, 256); 
 
    histogram.Build(codes);
    histogram.Print();
    histogram.Encode(codes);
 
    return 0;
}