ferencd@0: #ifndef FPAQ0
ferencd@0: #define FPAQ0
ferencd@0: 
ferencd@0: #include <vector>
ferencd@0: #include <string>
ferencd@0: #include <stdint.h>
ferencd@0: 
ferencd@0: #include <string.h>
ferencd@0: 
ferencd@0: class Archive
ferencd@0: {
ferencd@0: public:
ferencd@0: 
ferencd@0:     Archive(const std::vector<unsigned char>& s) : content(s.begin(), s.end()), it(content.begin()) {}
ferencd@0:     Archive() : content(), it(content.begin()) {}
ferencd@0: 
ferencd@0:     int getc() const
ferencd@0:     {
ferencd@0:         if(it == content.end())
ferencd@0:         {
ferencd@0:             return EOF;
ferencd@0:         }
ferencd@0:         int v = static_cast<int> (*it);
ferencd@0:         ++ it;
ferencd@0:         return v;
ferencd@0:     }
ferencd@0: 
ferencd@0:     void putc(char c)
ferencd@0:     {
ferencd@0:         content.push_back(c);
ferencd@0:     }
ferencd@0: 
ferencd@0:     std::vector<unsigned char> data() const
ferencd@0:     {
ferencd@0:         return content;
ferencd@0:     }
ferencd@0: 
ferencd@0: private:
ferencd@0:     std::vector<unsigned char> content;         // Compressed data file
ferencd@0:     mutable std::vector<unsigned char>::iterator it;
ferencd@0: };
ferencd@0: 
ferencd@0: //////////////////////////// Predictor /////////////////////////
ferencd@0: 
ferencd@0: /* A Predictor estimates the probability that the next bit of
ferencd@0:    uncompressed data is 1.  Methods:
ferencd@0:    p() returns P(1) as a 12 bit number (0-4095).
ferencd@0:    update(y) trains the predictor with the actual bit (0 or 1).
ferencd@0: */
ferencd@0: 
ferencd@0: class Predictor
ferencd@0: {
ferencd@0:     int cxt;  // Context: last 0-8 bits with a leading 1
ferencd@0:     int ct[512][2];  // 0 and 1 counts in context cxt
ferencd@0: public:
ferencd@0:     Predictor(): cxt(1)
ferencd@0:     {
ferencd@0:         memset(ct, 0, sizeof(ct));
ferencd@0:     }
ferencd@0: 
ferencd@0:     // Assume a stationary order 0 stream of 9-bit symbols
ferencd@0:     int p() const;
ferencd@0: 
ferencd@0:     void update(int y);
ferencd@0: };
ferencd@0: 
ferencd@0: 
ferencd@0: //////////////////////////// Encoder ////////////////////////////
ferencd@0: 
ferencd@0: /* An Encoder does arithmetic encoding.  Methods:
ferencd@0:    Encoder(COMPRESS, f) creates encoder for compression to archive f, which
ferencd@0:      must be open past any header for writing in binary mode
ferencd@0:    Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
ferencd@0:      which must be open past any header for reading in binary mode
ferencd@0:    encode(bit) in COMPRESS mode compresses bit to file f.
ferencd@0:    decode() in DECOMPRESS mode returns the next decompressed bit from file f.
ferencd@0:    flush() should be called when there is no more to compress.
ferencd@0: */
ferencd@0: 
ferencd@0: typedef enum {COMPRESS, DECOMPRESS} Mode;
ferencd@0: class Encoder
ferencd@0: {
ferencd@0: public:
ferencd@0:     Encoder(Mode m, Archive& archive);
ferencd@0:     void encode(int y);    // Compress bit y
ferencd@0:     int decode();          // Uncompress and return bit y
ferencd@0:     void flush();          // Call when done compressing
ferencd@0: private:
ferencd@0:     Predictor predictor;
ferencd@0:     const Mode mode;       // Compress or decompress?
ferencd@0:     Archive& archive;
ferencd@0:     uint32_t x1, x2;            // Range, initially [0, 1), scaled by 2^32
ferencd@0:     uint32_t x;                 // Last 4 input bytes of archive.
ferencd@0: };
ferencd@0: 
ferencd@0: std::vector<unsigned char> compress(const std::string& s);
ferencd@0: 
ferencd@0: std::string decompress(const std::vector<unsigned char>& v);
ferencd@0: 
ferencd@0: #endif // FPAQ0
ferencd@0: