MAIN.cpp      
#include 
#include 
using namespace std;    #include "ModelOrder0C.h"    // signature: "ACMC" (0x434D4341, intel byte order)
const int g_Signature = 0x434D4341;    int __cdecl main(int argc, char *argv[])
{
        cout << "Arithmetic Coding" << endl;            if( argc != 3 )
        {
                cout << "Syntax: AC source target" << endl;
                return 1;
        }            fstream source, target;
        ModelI* model;            // choose model, here just order-0
        model = new ModelOrder0C;            source.open( argv[1], ios::in | ios::binary );
        target.open( argv[2], ios::out | ios::binary );            if( !source.is_open() )
        {
                cout << "Cannot open input stream";
                return 2;
        }
        if( !target.is_open() )
        {
                cout << "Cannot open output stream";
                return 3;
        }            unsigned int signature;
        source.read(reinterpret_cast(&signature),sizeof(signature));
        if( signature == g_Signature )
        {
                cout << "Decoding " << argv[1] << " to " << argv[2] << endl;
                model->Process( &source, &target, MODE_DECODE );
        }
        else
        {
                cout << "Encoding " << argv[1] << " to " << argv[2] << endl;
                source.seekg( 0, ios::beg );
                target.write( reinterpret_cast(&g_Signature),
                                                                        sizeof(g_Signature) );
                model->Process( &source, &target, MODE_ENCODE );
        }            source.close();
        target.close();            return 0;
}    ModelOrder0C.h    #ifndef __MODELORDER0C_H__
#define __MODELORDER0C_H__    #include "ModelI.h"    class ModelOrder0C : public ModelI  
{
public:
        ModelOrder0C();    protected:
        void Encode();
        void Decode();            unsigned int mCumCount[ 257 ];
        unsigned int mTotal;
};    #endif     ModelI.h    #ifndef __MODELI_H__
#define __MODELI_H__    #include "ArithmeticCoderC.h"    enum ModeE
{
        MODE_ENCODE = 0,
        MODE_DECODE
};    class ModelI  
{
public:
        void Process( fstream *source, fstream *target, ModeE mode );    protected:
        virtual void Encode() = 0;
        virtual void Decode() = 0;            ArithmeticCoderC mAC;
        fstream *mSource;
        fstream *mTarget;
};    #endif    ArithmeticCoderC.h    #ifndef __ARITHMETICCODERC_H__
#define __ARITHMETICCODERC_H__    #include 
using namespace std;    class ArithmeticCoderC  
{
public:
        ArithmeticCoderC();            void SetFile( fstream *file );            void Encode( const unsigned int low_count, 
                     const unsigned int high_count, 
                     const unsigned int total );
        void EncodeFinish();            void DecodeStart();
        unsigned int DecodeTarget( const unsigned int total );
        void Decode( const unsigned int low_count, 
                                                         const unsigned int high_count );    protected:
        // bit operations
        void SetBit( const unsigned char bit );
        void SetBitFlush();
        unsigned char GetBit();            unsigned char mBitBuffer;
        unsigned char mBitCount;            // in-/output stream
        fstream *mFile;            // encoder & decoder
        unsigned int mLow;
        unsigned int mHigh;
        unsigned int mStep;
        unsigned int mScale;            // decoder
        unsigned int mBuffer;
};    #endif    ModelOrder0C.cpp    #include "ModelOrder0C.h"    ModelOrder0C::ModelOrder0C()
{
        // initialize probabilities with 1
        mTotal = 257; // 256   escape symbol for termination
        for( unsigned int i=0; i<257; i   )
                mCumCount[i] = 1;
}    void ModelOrder0C::Encode()
{            while( !mSource->eof() )
        {
                unsigned char symbol;                    // read symbol
                mSource->read( reinterpret_cast(&symbol), sizeof( symbol ) );                    if( !mSource->eof() )
                {
                        // cumulate frequencies
                        unsigned int low_count = 0;
                        for( unsigned char j=0; jwrite( reinterpret_cast(&symbol), sizeof( char ) );                    // adapt decoder
                mAC.Decode( low_count, low_count   mCumCount[ symbol ] );                    // update model
                mCumCount[ symbol ]  ;
                mTotal  ;
        }
        while( symbol != 256 ); // until termination symbol read
}    ModelI.cpp    #include "ModelI.h"    void ModelI::Process( fstream *source, fstream *target, ModeE mode )
{
        mSource = source;
        mTarget = target;            if( mode == MODE_ENCODE )
        {
                mAC.SetFile( mTarget );                    // encode
                Encode();                    mAC.EncodeFinish();
        }
        else // MODE_DECODE
        {
                mAC.SetFile( mSource );                    mAC.DecodeStart();                    // decode
                Decode();
        }
};    ArithmeticCoderC.cpp    #include "ArithmeticCoderC.h"
#include "tools.h"    // constants to split the number space of 32 bit integers
// most significant bit kept free to prevent overflows
const unsigned int g_FirstQuarter = 0x20000000;
const unsigned int g_ThirdQuarter = 0x60000000;
const unsigned int g_Half         = 0x40000000;    ArithmeticCoderC::ArithmeticCoderC()
{
        mBitCount = 0;
        mBitBuffer = 0;            mLow = 0;
        mHigh = 0x7FFFFFFF; // just work with least significant 31 bits
        mScale = 0;            mBuffer = 0;
        mStep = 0;
}    void ArithmeticCoderC::SetFile( fstream *file )
{
        mFile = file;
}    void ArithmeticCoderC::SetBit( const unsigned char bit )
{
        // add bit to the buffer
        mBitBuffer = (mBitBuffer << 1) | bit;
        mBitCount  ;            if(mBitCount == 8) // buffer full
        {
                // write
                mFile->write(reinterpret_cast(&mBitBuffer),sizeof(mBitBuffer));
                mBitCount = 0;
        }
}    void ArithmeticCoderC::SetBitFlush()
{
        // fill buffer with 0 up to the next byte
        while( mBitCount != 0 )
                SetBit( 0 );
}    unsigned char ArithmeticCoderC::GetBit()
{
        if(mBitCount == 0) // buffer empty
        {
                if( !( mFile->eof() ) ) // file read completely?
                        mFile->read(reinterpret_cast(&mBitBuffer),sizeof(mBitBuffer));
                else
                        mBitBuffer = 0; // append zeros                    mBitCount = 8;
        }            // extract bit from buffer
        unsigned char bit = mBitBuffer >> 7;
        mBitBuffer <<= 1;
        mBitCount--;            return bit;
}    void ArithmeticCoderC::Encode( const unsigned int low_count,
                                                                                                                         const unsigned int high_count,
                                                                                                                         const unsigned int total )
// total < 2^29
{
        // partition number space into single steps
        mStep = ( mHigh - mLow   1 ) / total; // interval open at the top =>  1            // update upper bound
        mHigh = mLow   mStep * high_count - 1; // interval open at the top => -1            // update lower bound
        mLow = mLow   mStep * low_count;            // apply e1/e2 mapping
        while( ( mHigh < g_Half ) || ( mLow >= g_Half ) )
                {
                        if( mHigh < g_Half )
                        {
                                SetBit( 0 );
                                mLow = mLow * 2;
                                mHigh = mHigh * 2   1;                                    // perform e3 mappings
                                for(; mScale > 0; mScale-- )
                                        SetBit( 1 );
                        }
                        else if( mLow >= g_Half )
                        {
                                SetBit( 1 );
                                mLow = 2 * ( mLow - g_Half );
                                mHigh = 2 * ( mHigh - g_Half )   1;                                    // perform e3 mappings
                                for(; mScale > 0; mScale-- )
                                        SetBit( 0 );
                        }
                }            // e3
        while( ( g_FirstQuarter <= mLow ) && ( mHigh < g_ThirdQuarter ) )
        {
                // keep necessary e3 mappings in mind
                mScale  ;
                mLow = 2 * ( mLow - g_FirstQuarter );
                mHigh = 2 * ( mHigh - g_FirstQuarter )   1;
        }
}    void ArithmeticCoderC::EncodeFinish()
{
        // There are two possibilities of how mLow and mHigh can be distributed,
        // which means that two bits are enough to distinguish them.            if( mLow < g_FirstQuarter ) // mLow < FirstQuarter < Half <= mHigh
        {
                SetBit( 0 );                    for( int i=0; i  1            // return current value
        return ( mBuffer - mLow ) / mStep;
}    void ArithmeticCoderC::Decode( const unsigned int low_count,
                                                                                                                         const unsigned int high_count )
{
        // update upper bound
        mHigh = mLow   mStep * high_count - 1; // interval open at the top => -1            // update lower bound
        mLow = mLow   mStep * low_count;            // e1/e2 mapping
        while( ( mHigh < g_Half ) || ( mLow >= g_Half ) )
                {
                        if( mHigh < g_Half )
                        {
                                mLow = mLow * 2;
                                mHigh = mHigh * 2   1;
                                mBuffer = 2 * mBuffer   GetBit();
                        }
                        else if( mLow >= g_Half )
                        {
                                mLow = 2 * ( mLow - g_Half );
                                mHigh = 2 * ( mHigh - g_Half )   1;
                                mBuffer = 2 * ( mBuffer - g_Half )   GetBit();
                        }
                        mScale = 0;
                }            // e3 mapping
        while( ( g_FirstQuarter <= mLow ) && ( mHigh < g_ThirdQuarter ) )
        {
                mScale  ;
                mLow = 2 * ( mLow - g_FirstQuarter );
                mHigh = 2 * ( mHigh - g_FirstQuarter )   1;
                mBuffer = 2 * ( mBuffer - g_FirstQuarter )   GetBit();
        }
}    tools.h    #ifndef __TOOLS_H__
#define __TOOLS_H__    int inline min( int a, int b )
{
        return a