ChrisChunick.com

The source code below is a bit coder class that can be used for reading or writing a compressed file. The source code provides access to a new type of entropy encoder. This new type of coder uses an algorithm I have created which I call frequency coding. The class I provide is  currently using two symbols, but is not limited to two. A frequency coder is a variant of a range coder with some minor similarities with huffman coding. Without getting into details, the main difference between a range coder and a frequency coder is that a frequency coder does not require the use of multiplication or division by only using the frequencies of the symbols but still retaining fractions, where a range coder or arithmetic coder use the probability to output a codeword. Huffman coding does not use fractions or at least retain fractions as the code is being created, where a frequency coder does, but also requires a sorted list of frequencies from lowest to highest to properly handle fractions. I will be putting out a paper in the near future that will explain how a frequency encoder can work for any number base.

download -> bitcoder.h (6886 downloads )

/*
Copyright (c) 2013 Chris Chunick, email@chrischunick.com
All rights reserved.

Redistribution and use in source and binary forms are permitted
provided that the above copyright notice and this paragraph are
duplicated in all such forms and that any documentation,
advertising materials, and other materials related to such
distribution and use acknowledge that the software was developed
by Chris Chunick  The name of Chris Chunick may not be used to 
endorse or promote products derived from this software without 
specific prior written permission.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
*/

class bitcoder
{

private:
    FILE *fin;
    FILE *fout;    
    unsigned int top,bot,range;
    unsigned int code;
    unsigned int m[32];

    void init()
    {
        passed=0;
        bot=0, top=-1;
        range=top-bot;
        code=0;
        for(unsigned int i=0;i<32;i++)m[i]=(0x7FFFFFFF>>(31-i));
    }

public:
    unsigned int passed;
    unsigned int fsize;

    void initcoder(FILE* fin, FILE* fout)
    {
        init();
        this->fin=fin;
        this->fout=fout;
    }

    void startdecoder()
    {
        for(unsigned int i=0;i<4;i++)fsize=(fsize<<8)|getc(fin);
        for(unsigned int i=0;i<4;i++)code=(code<<8)|getc(fin);
    }

    void startencoder()
    {
        fseek(fin,0,SEEK_END),fsize=ftell(fin),fseek(fin,0,SEEK_SET);
        putc((fsize>>24),fout),putc((fsize>>16),fout),putc((fsize>>8),fout),putc(fsize,fout);
        passed+=4;
    }

    void flushencoder()
    {
        putc(bot>>24,fout);putc(bot>>16,fout);putc(bot>>8,fout);putc(bot,fout);
        passed+=4;
    }

    void fencode(const unsigned int bit, const unsigned int c0, const unsigned int c1)
    {
        unsigned int lbit=(c0>c1),w=31,lo=c0,tc=c0+c1,tr=top-bot;

        if(lbit)lo=c1;

        while(((tc)>=(tr>>w))&&w!=-1)w--;

        if(w<-1)
        {
            if (lbit^bit)bot=(((bot>>w)+(lo)+1)<<w)|(bot&m[w]);
            else top=(((bot>>w)+(lo))<<w)|(top&m[w]);
        }
        else 
        {
            top=bot=bot+bit;
        }

        while((top^bot)<=0xFFFFFF || top<bot)
        {
            putc(bot>>24,fout);
            bot<<=8,top=(top<<=8)|0xFF;
            passed++;
        }
    }

    unsigned int fdecode(const unsigned int c0, const unsigned int c1)
    {
        unsigned int lbit=(c0>c1),w=31,lo=c0,bit,tc=c0+c1,tr=top-bot;

        if(lbit)lo=c1;
        while(((tc)>=(tr>>w))&&w!=-1)w--;

        if(w<-1)
        {
            bit=lbit^((code>>w)>((bot>>w)+lo));
            if (lbit^bit)bot=(((bot>>w)+(lo)+1)<<w)|(bot&m[w]);
            else top=(((bot>>w)+(lo))<<w)|(top&m[w]);
        }
        else top=bot=bot+(bit=code!=bot);

        while((top^bot)<=0xFFFFFF || top<bot)
        {
            code=(code<<8)|fgetc(fin);                    
            bot<<=8,top=(top<<=8)|0xFF;
        }

        return bit;
    }

};