This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

fpaq0 - D - mod

By: a guest on Apr 14th, 2012  |  syntax: D  |  size: 6.33 KB  |  views: 99  |  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. /**
  2. fpaq0 - Stationary order 0 file arithmetic compressor.
  3.  
  4. (C) 2004, Matt Mahoney under GPL, http://www.gnu.org/licenses/gpl.txt
  5.  
  6. Translated to the D language by leonardo maffi, Feb 8 2008.
  7. Modified by ,
  8.  
  9. Copyright: GPL
  10. */
  11.  
  12. // To compile: dmd -O -release -inline fpaq0D.d
  13. // or: gdc -O3 -frelease fpaq0.d -o fpaq0D
  14.  
  15. module fpaq0;
  16.  
  17. import std.c.stdio: FILE, getc, putc, ftell, fopen, fclose, EOF;
  18. import std.c.time: clock, CLOCKS_PER_SEC;
  19. import std.stdio: writefln;
  20. import std.string: toStringz;
  21.  
  22. import core.memory;
  23.  
  24. @system
  25. /**********************************************
  26. A Predictor estimates the probability that the next bit of uncompressed data is 1.
  27. */
  28. struct Predictor {
  29.     int cxt = 1;    // Context: last 0-8 bits with a leading 1
  30.     int[2][512] ct; // 0 and 1 counts in context cxt
  31.  
  32.     /**
  33.     returns P(1) as a 12 bit number (0-4095).
  34.     Assume a stationary order 0 stream of 9-bit symbols.
  35.     */
  36.     nothrow pure const int p() {
  37.         return 4096 * (ct[cxt][1] + 1) / (ct[cxt][0] + ct[cxt][1] + 2);
  38.     }
  39.  
  40.     /// trains the predictor with the actual bit (0 or 1).
  41.     nothrow pure void update(int y) {
  42.         ct[cxt][y]++;
  43.         if (ct[cxt][y] > 65534) {
  44.             ct[cxt][0] >>= 1;
  45.             ct[cxt][1] >>= 1;
  46.         }
  47.         cxt += cxt + y;
  48.         if (cxt >= 512)
  49.             cxt = 1;
  50.     }
  51. }
  52.  
  53.  
  54.  
  55. enum Mode {COMPRESS, DECOMPRESS}
  56.  
  57. /**************************************************
  58. An Encoder does arithmetic encoding.
  59.  
  60. Encoder(COMPRESS, f) creates encoder for compression to archive f, which
  61. must be open past any header for writing in binary mode.
  62.  
  63. Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
  64. which must be open past any header for reading in binary mode.
  65. */
  66. class Encoder {
  67.     private:
  68.         Predictor predictor;
  69.         immutable Mode mode;                // Compress or decompress?
  70.         FILE* archive;            // Compressed data file
  71.         uint x1, x2 = 0xffffffff; // Range, initially [0, 1), scaled by 2^32
  72.         uint x;                   // Last 4 input bytes of archive.
  73.  
  74.     public:
  75.         this (Mode m, FILE* f) {
  76.             this.mode = m;
  77.             this.archive = f;
  78.             // In DECOMPRESS mode, initialize x to the first 4 bytes of the archive
  79.             if (this.mode == Mode.DECOMPRESS) {
  80.                 foreach(i; 0 .. 4) {
  81.                     int c = getc(this.archive);
  82.                     if (c == EOF)
  83.                         c = 0;
  84.                     x = (x << 8) + (c & 0xff);
  85.                 }
  86.             }
  87.         }
  88.  
  89.         /**
  90.         encode(y) -- Encode bit y by splitting the range [x1, x2] in proportion
  91.         to P(1) and P(0) as given by the predictor and narrowing to the appropriate
  92.         subrange. Output leading bytes of the range as they become known.
  93.         */
  94.         nothrow final void encode(int y) {
  95.             // Update the range
  96.             immutable uint xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  97.             assert(xmid >= x1 && xmid < x2);
  98.             if (y)
  99.                 x2 = xmid;
  100.             else
  101.                 x1 = xmid + 1;
  102.             predictor.update(y);
  103.  
  104.             // Shift equal MSB's out
  105.             while (((x1 ^ x2) & 0xff000000) == 0) {
  106.                 putc(x2 >> 24, archive);
  107.                 x1 <<= 8;
  108.                 x2 = (x2 << 8) + 255;
  109.             }
  110.         }
  111.  
  112.         /**
  113.         Decode one bit from the archive, splitting [x1, x2] as in the encoder
  114.         and returning 1 or 0 depending on which subrange the archive point x is in.
  115.         */
  116.         nothrow final int decode() {
  117.             // Update the range
  118.             immutable uint xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  119.             assert(xmid >= x1 && xmid < x2);
  120.             int y = 0;
  121.             if (x <= xmid) {
  122.                 y = 1;
  123.                 x2 = xmid;
  124.             }
  125.             else
  126.                 x1 = xmid + 1;
  127.             predictor.update(y);
  128.  
  129.             // Shift equal MSB's out
  130.             while (((x1 ^ x2) & 0xff000000) == 0) {
  131.                 x1 <<= 8;
  132.                 x2 = (x2 << 8) + 255;
  133.                 int c = getc(this.archive);
  134.                 if (c == EOF)
  135.                     c = 0;
  136.                 x = (x << 8) + c;
  137.             }
  138.             return y;
  139.         }
  140.  
  141.         /// Should be called when there is no more to compress.
  142.         final void flush() {
  143.             // In COMPRESS mode, write out the remaining bytes of x, x1 < x < x2
  144.             if (this.mode == Mode.COMPRESS) {
  145.                 while (((x1 ^ x2) & 0xff000000) == 0) {
  146.                     putc(x2 >> 24, this.archive);
  147.                     x1 <<= 8;
  148.                     x2 = (x2 << 8) + 255;
  149.                 }
  150.                 putc(x2 >> 24, this.archive); // First unequal byte.
  151.             }
  152.         }
  153. }
  154.  
  155.  
  156. ///
  157. void compress(FILE* fin, FILE* fout) {
  158.     auto e = new Encoder(Mode.COMPRESS, fout);
  159.     for ( ; ; ) {
  160.         int c = getc(fin);
  161.         if (c == EOF)
  162.             break;
  163.         e.encode(0);
  164.         for(int i = 7; i >= 0; --i)
  165.             e.encode((c >> i) & 1);
  166.     }
  167.     e.encode(1); // EOF code
  168.     e.flush();
  169. }
  170.  
  171.  
  172. ///
  173. void decompress(FILE* fin, FILE* fout) {
  174.     auto e = new Encoder(Mode.DECOMPRESS, fin);
  175.     while (!e.decode()) {
  176.         int c = 1;
  177.         while (c < 256)
  178.             c += c + e.decode();
  179.         putc(c - 256, fout);
  180.     }
  181. }
  182.  
  183.  
  184. int main(string[] args) {
  185.     // Chech arguments: fpaq0 c/d input output
  186.     if (args.length != 4 || (args[1] != "c" && args[1] != "d")) {
  187.         writefln("To compress:   fpaq0 c input output");
  188.         writefln("To decompress: fpaq0 d input output");
  189.         return 1;
  190.     }
  191.  
  192.     auto start = clock(); // Start timer
  193.  
  194.     // Open files
  195.     FILE* fin = fopen(args[2].toStringz(), "rb".ptr);
  196.     if (!fin) {
  197.         writefln(args[2]);
  198.         return 1;
  199.     }
  200.     FILE* fout = fopen(args[3].toStringz(), "wb".ptr);
  201.     if (!fout) {
  202.         writefln(args[3]);
  203.         return 1;
  204.     }
  205.  
  206.     GC.disable;
  207.     if (args[1] == "c")
  208.         compress(fin, fout);
  209.     else
  210.         decompress(fin, fout);
  211.  
  212.     // Print results
  213.     double stop = (clock() - start) / cast(double)CLOCKS_PER_SEC;
  214.     writefln("%s (%d bytes) -> %s (%d bytes) in %1.2f s",
  215.              args[2], ftell(fin), args[3], ftell(fout), stop);
  216.  
  217.     fclose(fin);
  218.     fclose(fout);
  219.     return 0;
  220. }
clone this paste RAW Paste Data