Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

fpaq0

By: a guest on Apr 14th, 2012  |  syntax: C++  |  size: 5.31 KB  |  hits: 75  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. // fpaq0 - Stationary order 0 file compressor.
  2. // (C) 2004, Matt Mahoney under GPL, http://www.gnu.org/licenses/gpl.txt
  3. // To compile: g++ -O3 -s fpaq0.cpp -o fpaq0
  4.  
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <ctime>
  9. #include <cassert>
  10. namespace std {}  // for MARS compiler
  11. using namespace std;
  12.  
  13. typedef unsigned long U32;  // 32 bit type
  14.  
  15. //////////////////////////// Predictor /////////////////////////
  16.  
  17. /* A Predictor estimates the probability that the next bit of
  18.    uncompressed data is 1.  Methods:
  19.    p() returns P(1) as a 12 bit number (0-4095).
  20.    update(y) trains the predictor with the actual bit (0 or 1).
  21. */
  22.  
  23. class Predictor {
  24.   int cxt;  // Context: last 0-8 bits with a leading 1
  25.   int ct[512][2];  // 0 and 1 counts in context cxt
  26. public:
  27.   Predictor(): cxt(1) {
  28.     memset(ct, 0, sizeof(ct));
  29.   }
  30.  
  31.   // Assume a stationary order 0 stream of 9-bit symbols
  32.   int p() const {
  33.     return 4096*(ct[cxt][1]+1)/(ct[cxt][0]+ct[cxt][1]+2);
  34.   }
  35.  
  36.   void update(int y) {
  37.     if (++ct[cxt][y] > 65534) {
  38.       ct[cxt][0] >>= 1;
  39.       ct[cxt][1] >>= 1;
  40.     }
  41.     if ((cxt+=cxt+y) >= 512)
  42.       cxt=1;
  43.   }
  44. };
  45.  
  46. //////////////////////////// Encoder ////////////////////////////
  47.  
  48. /* An Encoder does arithmetic encoding.  Methods:
  49.    Encoder(COMPRESS, f) creates encoder for compression to archive f, which
  50.      must be open past any header for writing in binary mode
  51.    Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
  52.      which must be open past any header for reading in binary mode
  53.    encode(bit) in COMPRESS mode compresses bit to file f.
  54.    decode() in DECOMPRESS mode returns the next decompressed bit from file f.
  55.    flush() should be called when there is no more to compress.
  56. */
  57.  
  58. typedef enum {COMPRESS, DECOMPRESS} Mode;
  59. class Encoder {
  60. private:
  61.   Predictor predictor;
  62.   const Mode mode;       // Compress or decompress?
  63.   FILE* archive;         // Compressed data file
  64.   U32 x1, x2;            // Range, initially [0, 1), scaled by 2^32
  65.   U32 x;                 // Last 4 input bytes of archive.
  66. public:
  67.   Encoder(Mode m, FILE* f);
  68.   void encode(int y);    // Compress bit y
  69.   int decode();          // Uncompress and return bit y
  70.   void flush();          // Call when done compressing
  71. };
  72.  
  73. // Constructor
  74. Encoder::Encoder(Mode m, FILE* f): predictor(), mode(m), archive(f), x1(0),
  75.                                    x2(0xffffffff), x(0) {
  76.  
  77.   // In DECOMPRESS mode, initialize x to the first 4 bytes of the archive
  78.   if (mode==DECOMPRESS) {
  79.     for (int i=0; i<4; ++i) {
  80.       int c=getc(archive);
  81.       if (c==EOF) c=0;
  82.       x=(x<<8)+(c&0xff);
  83.     }
  84.   }
  85. }
  86.  
  87. /* encode(y) -- Encode bit y by splitting the range [x1, x2] in proportion
  88. to P(1) and P(0) as given by the predictor and narrowing to the appropriate
  89. subrange.  Output leading bytes of the range as they become known. */
  90.  
  91. inline void Encoder::encode(int y) {
  92.  
  93.   // Update the range
  94.   const U32 xmid = x1 + ((x2-x1) >> 12) * predictor.p();
  95.   assert(xmid >= x1 && xmid < x2);
  96.   if (y)
  97.     x2=xmid;
  98.   else
  99.     x1=xmid+1;
  100.   predictor.update(y);
  101.  
  102.   // Shift equal MSB's out
  103.   while (((x1^x2)&0xff000000)==0) {
  104.     putc(x2>>24, archive);
  105.     x1<<=8;
  106.     x2=(x2<<8)+255;
  107.   }
  108. }
  109.  
  110. /* Decode one bit from the archive, splitting [x1, x2] as in the encoder
  111. and returning 1 or 0 depending on which subrange the archive point x is in.
  112. */
  113. inline int Encoder::decode() {
  114.  
  115.   // Update the range
  116.   const U32 xmid = x1 + ((x2-x1) >> 12) * predictor.p();
  117.   assert(xmid >= x1 && xmid < x2);
  118.   int y=0;
  119.   if (x<=xmid) {
  120.     y=1;
  121.     x2=xmid;
  122.   }
  123.   else
  124.     x1=xmid+1;
  125.   predictor.update(y);
  126.  
  127.   // Shift equal MSB's out
  128.   while (((x1^x2)&0xff000000)==0) {
  129.     x1<<=8;
  130.     x2=(x2<<8)+255;
  131.     int c=getc(archive);
  132.     if (c==EOF) c=0;
  133.     x=(x<<8)+c;
  134.   }
  135.   return y;
  136. }
  137.  
  138. // Should be called when there is no more to compress
  139. void Encoder::flush() {
  140.  
  141.   // In COMPRESS mode, write out the remaining bytes of x, x1 < x < x2
  142.   if (mode==COMPRESS) {
  143.     while (((x1^x2)&0xff000000)==0) {
  144.       putc(x2>>24, archive);
  145.       x1<<=8;
  146.       x2=(x2<<8)+255;
  147.     }
  148.     putc(x2>>24, archive);  // First unequal byte
  149.   }
  150. }
  151.  
  152. //////////////////////////// main ////////////////////////////
  153.  
  154. int main(int argc, char** argv) {
  155.  
  156.   // Chech arguments: fpaq0 c/d input output
  157.   if (argc!=4 || (argv[1][0]!='c' && argv[1][0]!='d')) {
  158.     printf("To compress:   fpaq0 c input output\n"
  159.            "To decompress: fpaq0 d input output\n");
  160.     exit(1);
  161.   }
  162.  
  163.   // Start timer
  164.   clock_t start = clock();
  165.  
  166.   // Open files
  167.   FILE *in=fopen(argv[2], "rb");
  168.   if (!in) perror(argv[2]), exit(1);
  169.   FILE *out=fopen(argv[3], "wb");
  170.   if (!out) perror(argv[3]), exit(1);
  171.   int c;
  172.  
  173.   // Compress
  174.   if (argv[1][0]=='c') {
  175.     Encoder e(COMPRESS, out);
  176.     while ((c=getc(in))!=EOF) {
  177.       e.encode(0);
  178.       for (int i=7; i>=0; --i)
  179.         e.encode((c>>i)&1);
  180.     }
  181.     e.encode(1);  // EOF code
  182.     e.flush();
  183.   }
  184.  
  185.   // Decompress
  186.   else {
  187.     Encoder e(DECOMPRESS, in);
  188.     while (!e.decode()) {
  189.       int c=1;
  190.       while (c<256)
  191.         c+=c+e.decode();
  192.       putc(c-256, out);
  193.     }
  194.   }
  195.  
  196.   // Print results
  197.   printf("%s (%ld bytes) -> %s (%ld bytes) in %1.2f s.\n",
  198.     argv[2], ftell(in), argv[3], ftell(out),
  199.     ((double)clock()-start)/CLOCKS_PER_SEC);
  200.   return 0;
  201. }