ferencd@0: // fpaq0 - Stationary order 0 file compressor.
ferencd@0: // (C) 2004, Matt Mahoney under GPL, http://www.gnu.org/licenses/gpl.txt
ferencd@0: // To compile: g++ -O fpaq0.cpp
ferencd@0: 
ferencd@0: #include <cstdio>
ferencd@0: #include <cstdlib>
ferencd@0: #include <cstring>
ferencd@0: #include <ctime>
ferencd@0: #include <cassert>
ferencd@0: #include <iostream>
ferencd@0: #include "fpaq0.h"
ferencd@0: 
ferencd@0: using namespace std;
ferencd@0: 
ferencd@0: 
ferencd@0: // Constructor
ferencd@0: Encoder::Encoder(Mode m, Archive &parchive): predictor(), mode(m), archive(parchive), x1(0),
ferencd@0:     x2(0xffffffff), x(0)
ferencd@0: {
ferencd@0: 
ferencd@0:     // In DECOMPRESS mode, initialize x to the first 4 bytes of the archive
ferencd@0:     if (mode==DECOMPRESS)
ferencd@0:     {
ferencd@0:         for (int i=0; i<4; ++i)
ferencd@0:         {
ferencd@0:             int c = archive.getc();
ferencd@0:             if (c==EOF) c=0;
ferencd@0:             x=(x<<8)+(c&0xff);
ferencd@0:         }
ferencd@0:     }
ferencd@0: }
ferencd@0: 
ferencd@0: /* encode(y) -- Encode bit y by splitting the range [x1, x2] in proportion
ferencd@0: to P(1) and P(0) as given by the predictor and narrowing to the appropriate
ferencd@0: subrange.  Output leading bytes of the range as they become known. */
ferencd@0: 
ferencd@0: inline void Encoder::encode(int y)
ferencd@0: {
ferencd@0: 
ferencd@0:     // Update the range
ferencd@0:     const uint32_t xmid = x1 + ((x2-x1) >> 12) * predictor.p();
ferencd@0:     assert(xmid >= x1 && xmid < x2);
ferencd@0:     if (y)
ferencd@0:         x2=xmid;
ferencd@0:     else
ferencd@0:         x1=xmid+1;
ferencd@0:     predictor.update(y);
ferencd@0: 
ferencd@0:     // Shift equal MSB's out
ferencd@0:     while ( ((x1^x2) & 0xff000000) == 0)
ferencd@0:     {
ferencd@0:         archive.putc(x2>>24);
ferencd@0:         x1 <<= 8;
ferencd@0:         x2 = (x2<<8) + 255;
ferencd@0:     }
ferencd@0: }
ferencd@0: 
ferencd@0: /* Decode one bit from the archive, splitting [x1, x2] as in the encoder
ferencd@0: and returning 1 or 0 depending on which subrange the archive point x is in.
ferencd@0: */
ferencd@0: inline int Encoder::decode()
ferencd@0: {
ferencd@0: 
ferencd@0:     // Update the range
ferencd@0:     const uint32_t xmid = x1 + ((x2-x1) >> 12) * predictor.p();
ferencd@0:     assert(xmid >= x1 && xmid < x2);
ferencd@0:     int y=0;
ferencd@0:     if (x<=xmid)
ferencd@0:     {
ferencd@0:         y=1;
ferencd@0:         x2=xmid;
ferencd@0:     }
ferencd@0:     else
ferencd@0:         x1=xmid+1;
ferencd@0:     predictor.update(y);
ferencd@0: 
ferencd@0:     // Shift equal MSB's out
ferencd@0:     while (((x1^x2)&0xff000000)==0)
ferencd@0:     {
ferencd@0:         x1 <<= 8;
ferencd@0:         x2=(x2<<8)+255;
ferencd@0:         int c = archive.getc();
ferencd@0:         if (c==EOF) c=0;
ferencd@0:         x = (x<<8) + c;
ferencd@0:     }
ferencd@0:     return y;
ferencd@0: }
ferencd@0: 
ferencd@0: // Should be called when there is no more to compress
ferencd@0: void Encoder::flush()
ferencd@0: {
ferencd@0: 
ferencd@0:     // In COMPRESS mode, write out the remaining bytes of x, x1 < x < x2
ferencd@0:     if (mode==COMPRESS)
ferencd@0:     {
ferencd@0:         while (((x1^x2)&0xff000000)==0)
ferencd@0:         {
ferencd@0:             archive.putc(x2>>24);
ferencd@0:             x1 <<= 8;
ferencd@0:             x2 = (x2<<8) + 255;
ferencd@0:         }
ferencd@0:         archive.putc(x2>>24);  // First unequal byte
ferencd@0:     }
ferencd@0: }
ferencd@0: 
ferencd@0: std::vector<unsigned char> compress(const std::string& s)
ferencd@0: {
ferencd@0:     Archive a;
ferencd@0:     Encoder e(COMPRESS, a);
ferencd@0:     char c = 0;
ferencd@0:     size_t idx = 0;
ferencd@0:     while ( idx < s.length() )
ferencd@0:     {
ferencd@0:         c = s[idx];
ferencd@0:         e.encode(0);
ferencd@0:         for (int i=7; i>=0; --i)
ferencd@0:         {
ferencd@0:             e.encode((c>>i)&1);
ferencd@0:         }
ferencd@0:         idx ++;
ferencd@0:     }
ferencd@0:     e.encode(1);  // EOF code
ferencd@0:     e.flush();
ferencd@0: 
ferencd@0:     return a.data();
ferencd@0: }
ferencd@0: 
ferencd@0: std::string decompress(const std::vector<unsigned char>& v)
ferencd@0: {
ferencd@0:     Archive a(v);
ferencd@0:     std::string result;
ferencd@0:     Encoder e(DECOMPRESS, a);
ferencd@0:     while (!e.decode())
ferencd@0:     {
ferencd@0:         int c=1;
ferencd@0:         while (c<256)
ferencd@0:             c += c + e.decode();
ferencd@0: 
ferencd@0:         char temp[2] = {0};
ferencd@0:         temp[0] = c - 256;
ferencd@0: 
ferencd@0:         result += temp;
ferencd@0:     }
ferencd@0:     return result;
ferencd@0: }
ferencd@0: 
ferencd@0: int Predictor::p() const
ferencd@0: {
ferencd@0:     return 4096*(ct[cxt][1]+1)/(ct[cxt][0]+ct[cxt][1]+2);
ferencd@0: }
ferencd@0: 
ferencd@0: void Predictor::update(int y)
ferencd@0: {
ferencd@0:     if (++ct[cxt][y] > 65534)
ferencd@0:     {
ferencd@0:         ct[cxt][0] >>= 1;
ferencd@0:         ct[cxt][1] >>= 1;
ferencd@0:     }
ferencd@0:     if ((cxt+=cxt+y) >= 512)
ferencd@0:         cxt=1;
ferencd@0: }