aricoder.cpp

this is source code for image compression following jpeg2000 staandard

/*---------------------------------------------------------------------------*/
// Image Compression Toolbox v1.2
// written by
// Satish Kumar S
// [e-mail]
//
// Copyright 1999 Satish Kumar S
//
// Permission is granted to use this software for research purposes as
// long as this notice stays attached to this software.
/*---------------------------------------------------------------------------*/
#include <stdio.h>
#include <math.h>
#include "aricoder.h"

int writtenBits = 0;
static int eofreached = 0;
//-----------------------------------------------------------
// the BitStream part.
//-----------------------------------------------------------
BitStream::BitStream(FILE *givenfp)
{
    buf = 0;
    nBits = 0;
    numBitsWritten = 0;
    numBitsRead = 0;
    fp = givenfp;
}

BitStream::~BitStream()
{
    buf = 0;
    nBits = 0;
    numBitsWritten = 0;
    fp = NULL;
}

void BitStream::WriteBit(unsigned int bit)
{
    buf = (buf<<1)+bit;
    nBits++;
    if (nBits==8)
    {
        fwrite(&buf,1,1,fp);
        nBits = 0;
        buf = 0;
    }
    numBitsWritten++;
}

void BitStream::Flush()
{
    if (nBits)
    {
        buf = (buf<<(8-nBits));
        fwrite(&buf,1,1,fp);
        nBits = 0;
        buf = 0;
    }
}

unsigned int BitStream::ReadBit()
{
    int bit;
    if (nBits == 0)
    {
        nBits = 8;
        fread(&buf,1,1,fp);
    }
    bit = (buf & 128)>>7;
    buf = buf<<1;
    nBits--;
    numBitsRead++;
    return bit;
}

void BitStream::WriteBits(unsigned int bits, int n)
{
    unsigned int mask = (1<<(n-1));
    while(n--)
    {
        WriteBit((bits & mask)>0);
        bits = bits<<1;
    }
}

unsigned int BitStream::ReadBits(int n)
{
    int bits=0;
    while(n--)
        bits = (bits<<1)+ReadBit();
    return bits;
}

//-----------------------------------------------------------
// the Source Model part.
// the source model is an implementation of 
// "A New Data structure for Cumulative Frequency Tables" by
// Peter M. Fenwick, SOFTWARE-PRACTICE AND EXPERIENCE
// Vol.24(3), pp 327-336 (MARCH 1994)
//-----------------------------------------------------------
AdaptiveModel::AdaptiveModel()
{
    numSyms = 0;

    Tree = NULL;
    totfreq = 0;
}

AdaptiveModel::~AdaptiveModel()
{
    numSyms = 0;

    if (Tree)
        delete[] Tree;
}

int AdaptiveModel::SetNumSyms(int n)
{
    AdaptiveModel::~AdaptiveModel();

    if (Tree) delete[] Tree;
    Tree = new unsigned int[n+1];
    numSyms = n+1;
    totfreq = 0;

    for(int i=0; i<numSyms; i++)
    {
        Tree[i] = 0;
    }

    for(i=0; i<numSyms; i++)
        PutValue(1, i);

    return 0;
}

int AdaptiveModel::GetCumul(int Ix)
{
    unsigned int sum;
    sum = Tree[0];
    while(Ix > 0)
    {
        sum = sum + Tree[Ix];
        Ix = Ix & (Ix - 1);
    }
    return sum;
}

void AdaptiveModel::PutValue(int Val, int Ix)
{
    Ix++;
    while((unsigned int)Ix < numSyms)
    {
        Tree[Ix] = Tree[Ix] + Val;
        Ix = Ix + (Ix & (-Ix));
    }
    totfreq += Val;
}

void AdaptiveModel::Scaledown()
{
    for(int i=numSyms-2; i>=0; i--)
        PutValue(-GetFreq(i)/2, i);
}

int AdaptiveModel::GetFreq(int Ix)
{
    int val, parent;
    Ix++;
    val = Tree[Ix];
    if (Ix > 0)
    {
        parent = Ix & (Ix -1);
        Ix = Ix - 1;
        while(parent != Ix)
        {
            val = val - Tree[Ix];
            Ix = Ix & (Ix - 1);
        }
    }
    return val;
}

int AdaptiveModel::GetIndex(unsigned int Freq)
{
    int Index, TestIx, origFreq=Freq;
    int mask = (numSyms+0)/2;
    Index = 0;
    if (Freq > Tree[0])
    {
        while(mask != 0)
        {
            TestIx = Index+mask;
            if (Freq >= Tree[TestIx])
            {
                Index = TestIx;
                Freq = Freq - Tree[Index];
            }
            mask = mask / 2;
        }
    }
    else return 0;
    return Index;
}

//-----------------------------------------------------------
// the Arithmetic Encoder part.
// implementation of 
//   "Arithmetic coding for Data compression"
//   by Witten, Neal & Cleary, CACM, June 1987 Vol.30
//-----------------------------------------------------------
ArithEncoder::ArithEncoder(BitStream *bitstream)
{
    bs = bitstream;
}

ArithEncoder::~ArithEncoder()
{
}

int ArithEncoder::SetNumSyms(int n)
{
    return SrcModel.SetNumSyms(n);
}

void ArithEncoder::InitEncode()
{
    High = TopValue;
    Low  = 0;
    folw = 0;
}

void ArithEncoder::Flush()
{
    for (int i=CodeValueBits; i>0; i--)
    {
	    if (Low >= Half)
        {
	        WriteBitPlusFollow(1);
	        Low -= Half;
        }
	    else
	        WriteBitPlusFollow(0);
	    Low = 2 * Low;
    }
}

unsigned int ArithEncoder::Encode(unsigned int symbol,int update)
{
    long Range;
    Range = High-Low+1;

    High = Low + (Range*SrcModel.GetCumul(symbol+1))/SrcModel.totfreq - 1;
    Low  = Low + (Range*SrcModel.GetCumul(symbol  ))/SrcModel.totfreq;

    while(1)
    {
        if (High < Half)
        {
            WriteBitPlusFollow(0);
        }
        else if (Low >= Half)
        {
            WriteBitPlusFollow(1);
            Low -= Half;
            High -= Half;
        }
        else if (Low >= FirstQtr && High < ThirdQtr)
        {
            folw++;
            Low -= FirstQtr;
            High -= FirstQtr;
        }
        else break;
        Low = Low << 1;
        High = (High << 1) + 1;
    }
    if (update)
    {
        SrcModel.PutValue(1,symbol);
        if (SrcModel.totfreq > MaxAllowedFreq)
            SrcModel.Scaledown();
    }
    if (High > 65535)
        High = High;
    return 0;
}

double ArithEncoder::EncodingCost(unsigned int symbol)
{
    double cost = -log((double)SrcModel.GetFreq(symbol)/SrcModel.totfreq) * onelog2;
    SrcModel.PutValue(1, symbol);
    if (SrcModel.totfreq > MaxAllowedFreq)
        SrcModel.Scaledown();
    return cost;
}

//-----------------------------------------------------------
// the Arithmetic Decoder part.
// implementation of 
//   "Arithmetic coding for Data compression"
//   by Witten, Neal & Cleary, CACM, June 1987 Vol.30
//-----------------------------------------------------------

ArithDecoder::ArithDecoder(BitStream *b)
{
    bs = b;
}

ArithDecoder::~ArithDecoder()
{
}

int ArithDecoder::SetNumSyms(int n)
{
    return SrcModel.SetNumSyms(n);
}

void ArithDecoder::InitDecode()
{
    Value = 0;
    // Initialize Value.
    for(int i=0; i<CodeValueBits; i++)
        Value = (Value<<1) + bs->ReadBit();

    Low = 0;
    High = TopValue;
}

unsigned int ArithDecoder::Decode()
{
    long Range;
    unsigned int cum, symbol;

    if (eofreached)
        return EOF;
    Range = High-Low+1;
    cum = ( ((long)(Value-Low+1))*SrcModel.totfreq - 1)/Range;

    // Find the symbol with this cumulative frequency.
    symbol = SrcModel.GetIndex(cum);

    // Update the range of the code.
    High = Low + (Range*SrcModel.GetCumul(symbol+1))/SrcModel.totfreq - 1;
    Low  = Low + (Range*SrcModel.GetCumul(symbol  ))/SrcModel.totfreq;

    // Now find thebits which can be send off.
    while(1)
    {
        if (High < Half)
        {
            ;   // Nothing to send.
        }
        else if (Low >= Half)
        {
            Value -= Half;
            Low -= Half;
            High -= Half;
        }
        else if (Low >= FirstQtr && High < ThirdQtr)
        {
            Value -= FirstQtr;
            Low -= FirstQtr;
            High -= FirstQtr;
        }
        else break;
        Low = (Low<<1);
        High = (High<<1)+1;
        Value = (Value<<1)+bs->ReadBit();
    }
    SrcModel.PutValue(1,symbol);
    if (SrcModel.totfreq > MaxAllowedFreq)
        SrcModel.Scaledown();

    return symbol;
}