Want more features on Pastebin? Sign Up, it's FREE!
Guest

fpaq0 - D - manual inlining

By: a guest on Apr 14th, 2012  |  syntax: D  |  size: 6.35 KB  |  views: 55  |  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. nothrow void compress(FILE* fin, FILE* fout) {
  54.     Predictor predictor;
  55.     uint x1, x2 = 0xffffffff; // Range, initially [0, 1), scaled by 2^32
  56.     uint x;                   // Last 4 input bytes of archive.
  57.     uint y;
  58.     uint xmid;
  59.  
  60.     for ( ; ; ) {
  61.         int c = getc(fin);
  62.         if (c == EOF)
  63.             break;
  64.  
  65.         //e.encode(0);
  66.         y = 0;
  67.         xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  68.         assert(xmid >= x1 && xmid < x2);
  69.         if (y)
  70.             x2 = xmid;
  71.         else
  72.             x1 = xmid + 1;
  73.         predictor.update(y);
  74.  
  75.         while (((x1 ^ x2) & 0xff000000) == 0) {
  76.             putc(x2 >> 24, fout);
  77.             x1 <<= 8;
  78.             x2 = (x2 << 8) + 255;
  79.         }
  80.  
  81.         for(int i = 7; i >= 0; --i){
  82.             //e.encode((c >> i) & 1);
  83.             y = (c >> i) & 1;
  84.             xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  85.             assert(xmid >= x1 && xmid < x2);
  86.             if (y)
  87.                 x2 = xmid;
  88.             else
  89.                 x1 = xmid + 1;
  90.             predictor.update(y);
  91.  
  92.             while (((x1 ^ x2) & 0xff000000) == 0) {
  93.                 putc(x2 >> 24, fout);
  94.                 x1 <<= 8;
  95.                 x2 = (x2 << 8) + 255;
  96.             }
  97.         }
  98.     }
  99.     //e.encode(1)
  100.     y = 1;
  101.     xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  102.     assert(xmid >= x1 && xmid < x2);
  103.     if (y)
  104.         x2 = xmid;
  105.     else
  106.         x1 = xmid + 1;
  107.     predictor.update(y);
  108.  
  109.     while (((x1 ^ x2) & 0xff000000) == 0) {
  110.         putc(x2 >> 24, fout);
  111.         x1 <<= 8;
  112.         x2 = (x2 << 8) + 255;
  113.     }
  114.  
  115.     // e.flush();
  116.     while (((x1 ^ x2) & 0xff000000) == 0) {
  117.         putc(x2 >> 24, fout);
  118.         x1 <<= 8;
  119.         x2 = (x2 << 8) + 255;
  120.     }
  121.     putc(x2 >> 24, fout); // First unequal byte.
  122. }
  123.  
  124.  
  125.  
  126. nothrow void decompress(FILE* fin, FILE* fout) {
  127.     Predictor predictor;
  128.     uint x1, x2 = 0xffffffff; // Range, initially [0, 1), scaled by 2^32
  129.     uint x;                   // Last 4 input bytes of archive.
  130.     int c;
  131.     uint xmid;
  132.     int y;
  133.  
  134.     // Initialize x to the first 4 bytes of the archive
  135.     foreach(i; 0 .. 4) {
  136.         c = getc(fin);
  137.         if (c == EOF)
  138.             c = 0;
  139.         x = (x << 8) + (c & 0xff);
  140.     }
  141.  
  142.     // pre-encode for while
  143.         xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  144.         assert(xmid >= x1 && xmid < x2);
  145.         y = 0;
  146.         if (x <= xmid) {
  147.             y = 1;
  148.             x2 = xmid;
  149.         }
  150.         else
  151.             x1 = xmid + 1;
  152.         predictor.update(y);
  153.  
  154.         while (((x1 ^ x2) & 0xff000000) == 0) {
  155.             x1 <<= 8;
  156.             x2 = (x2 << 8) + 255;
  157.             int c2 = getc(fin);
  158.             if (c2 == EOF)
  159.                 c2 = 0;
  160.             x = (x << 8) + c2;
  161.         }
  162.  
  163.     while (!y) { //acho que isto vai dar problema
  164.         c = 1;
  165.         while (c < 256) {
  166.             xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  167.             assert(xmid >= x1 && xmid < x2);
  168.             y = 0;
  169.             if (x <= xmid) {
  170.                 y = 1;
  171.                 x2 = xmid;
  172.             }
  173.             else
  174.                 x1 = xmid + 1;
  175.             predictor.update(y);
  176.  
  177.             while (((x1 ^ x2) & 0xff000000) == 0) {
  178.                 x1 <<= 8;
  179.                 x2 = (x2 << 8) + 255;
  180.                 int c2 = getc(fin);
  181.                 if (c2 == EOF)
  182.                     c2 = 0;
  183.                 x = (x << 8) + c2;
  184.             }
  185.             c += c + y;
  186.         }
  187.         putc(c - 256, fout);
  188.  
  189.         // second round, for while definition
  190.         xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
  191.         assert(xmid >= x1 && xmid < x2);
  192.         y = 0;
  193.         if (x <= xmid) {
  194.             y = 1;
  195.             x2 = xmid;
  196.         }
  197.         else
  198.             x1 = xmid + 1;
  199.         predictor.update(y);
  200.  
  201.         while (((x1 ^ x2) & 0xff000000) == 0) {
  202.             x1 <<= 8;
  203.             x2 = (x2 << 8) + 255;
  204.             int c2 = getc(fin);
  205.             if (c2 == EOF)
  206.                 c2 = 0;
  207.             x = (x << 8) + c2;
  208.         }
  209.     }
  210. }
  211.  
  212. int main(string[] args) {
  213.     // Chech arguments: fpaq0 c/d input output
  214.     if (args.length != 4 || (args[1] != "c" && args[1] != "d")) {
  215.         writefln("To compress:   fpaq0 c input output");
  216.         writefln("To decompress: fpaq0 d input output");
  217.         return 1;
  218.     }
  219.  
  220.     auto start = clock(); // Start timer
  221.  
  222.     // Open files
  223.     FILE* fin = fopen(args[2].toStringz(), "rb".ptr);
  224.     if (!fin) {
  225.         writefln(args[2]);
  226.         return 1;
  227.     }
  228.     FILE* fout = fopen(args[3].toStringz(), "wb".ptr);
  229.     if (!fout) {
  230.         writefln(args[3]);
  231.         return 1;
  232.     }
  233.  
  234.     GC.disable;
  235.     if (args[1] == "c")
  236.         compress(fin, fout);
  237.     else
  238.         decompress(fin, fout);
  239.  
  240.     // Print results
  241.     double stop = (clock() - start) / cast(double)CLOCKS_PER_SEC;
  242.     writefln("%s (%d bytes) -> %s (%d bytes) in %1.2f s",
  243.              args[2], ftell(fin), args[3], ftell(fout), stop);
  244.  
  245.     fclose(fin);
  246.     fclose(fout);
  247.     return 0;
  248. }
clone this paste RAW Paste Data