/**
fpaq0 - Stationary order 0 file arithmetic compressor.

(C) 2004, Matt Mahoney under GPL, http://www.gnu.org/licenses/gpl.txt

Translated to the D language by leonardo maffi, Feb 8 2008.
Modified by ,

Copyright: GPL
*/

// To compile: dmd -O -release -inline fpaq0D.d
// or: gdc -O3 -frelease fpaq0.d -o fpaq0D

module fpaq0;

import std.c.stdio: FILE, getc, putc, ftell, fopen, fclose, EOF;
import std.c.time: clock, CLOCKS_PER_SEC;
import std.stdio: writefln;
import std.string: toStringz;

import core.memory;

@system
/**********************************************
A Predictor estimates the probability that the next bit of uncompressed data is 1.
*/
struct Predictor {
    int cxt = 1;    // Context: last 0-8 bits with a leading 1
    int[2][512] ct; // 0 and 1 counts in context cxt

    /**
    returns P(1) as a 12 bit number (0-4095).
    Assume a stationary order 0 stream of 9-bit symbols.
    */
    nothrow pure const int p() {
        return 4096 * (ct[cxt][1] + 1) / (ct[cxt][0] + ct[cxt][1] + 2);
    }

    /// trains the predictor with the actual bit (0 or 1).
    nothrow pure void update(int y) {
        ct[cxt][y]++;
        if (ct[cxt][y] > 65534) {
            ct[cxt][0] >>= 1;
            ct[cxt][1] >>= 1;
        }
        cxt += cxt + y;
        if (cxt >= 512)
            cxt = 1;
    }
}

nothrow void compress(FILE* fin, FILE* fout) {
    Predictor predictor;
    uint x1, x2 = 0xffffffff; // Range, initially [0, 1), scaled by 2^32
    uint x;                   // Last 4 input bytes of archive.
    uint y;
    uint xmid;

    for ( ; ; ) {
        int c = getc(fin);
        if (c == EOF)
            break;

        //e.encode(0);
        y = 0;
        xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
        assert(xmid >= x1 && xmid < x2);
        if (y)
            x2 = xmid;
        else
            x1 = xmid + 1;
        predictor.update(y);

        while (((x1 ^ x2) & 0xff000000) == 0) {
            putc(x2 >> 24, fout);
            x1 <<= 8;
            x2 = (x2 << 8) + 255;
        }

        for(int i = 7; i >= 0; --i){
            //e.encode((c >> i) & 1);
            y = (c >> i) & 1;
            xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
            assert(xmid >= x1 && xmid < x2);
            if (y)
                x2 = xmid;
            else
                x1 = xmid + 1;
            predictor.update(y);

            while (((x1 ^ x2) & 0xff000000) == 0) {
                putc(x2 >> 24, fout);
                x1 <<= 8;
                x2 = (x2 << 8) + 255;
            }
        }
    }
    //e.encode(1)
    y = 1;
    xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
    assert(xmid >= x1 && xmid < x2);
    if (y)
        x2 = xmid;
    else
        x1 = xmid + 1;
    predictor.update(y);

    while (((x1 ^ x2) & 0xff000000) == 0) {
        putc(x2 >> 24, fout);
        x1 <<= 8;
        x2 = (x2 << 8) + 255;
    }

    // e.flush();
    while (((x1 ^ x2) & 0xff000000) == 0) {
        putc(x2 >> 24, fout);
        x1 <<= 8;
        x2 = (x2 << 8) + 255;
    }
    putc(x2 >> 24, fout); // First unequal byte.
}



nothrow void decompress(FILE* fin, FILE* fout) {
    Predictor predictor;
    uint x1, x2 = 0xffffffff; // Range, initially [0, 1), scaled by 2^32
    uint x;                   // Last 4 input bytes of archive.
    int c;
    uint xmid;
    int y;

    // Initialize x to the first 4 bytes of the archive
    foreach(i; 0 .. 4) {
        c = getc(fin);
        if (c == EOF)
            c = 0;
        x = (x << 8) + (c & 0xff);
    }

    // pre-encode for while
        xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
        assert(xmid >= x1 && xmid < x2);
        y = 0;
        if (x <= xmid) {
            y = 1;
            x2 = xmid;
        }
        else
            x1 = xmid + 1;
        predictor.update(y);

        while (((x1 ^ x2) & 0xff000000) == 0) {
            x1 <<= 8;
            x2 = (x2 << 8) + 255;
            int c2 = getc(fin);
            if (c2 == EOF)
                c2 = 0;
            x = (x << 8) + c2;
        }

    while (!y) { //acho que isto vai dar problema
        c = 1;
        while (c < 256) {
            xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
            assert(xmid >= x1 && xmid < x2);
            y = 0;
            if (x <= xmid) {
                y = 1;
                x2 = xmid;
            }
            else
                x1 = xmid + 1;
            predictor.update(y);

            while (((x1 ^ x2) & 0xff000000) == 0) {
                x1 <<= 8;
                x2 = (x2 << 8) + 255;
                int c2 = getc(fin);
                if (c2 == EOF)
                    c2 = 0;
                x = (x << 8) + c2;
            }
            c += c + y;
        }
        putc(c - 256, fout);

        // second round, for while definition
        xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
        assert(xmid >= x1 && xmid < x2);
        y = 0;
        if (x <= xmid) {
            y = 1;
            x2 = xmid;
        }
        else
            x1 = xmid + 1;
        predictor.update(y);

        while (((x1 ^ x2) & 0xff000000) == 0) {
            x1 <<= 8;
            x2 = (x2 << 8) + 255;
            int c2 = getc(fin);
            if (c2 == EOF)
                c2 = 0;
            x = (x << 8) + c2;
        }
    }
}

int main(string[] args) {
    // Chech arguments: fpaq0 c/d input output
    if (args.length != 4 || (args[1] != "c" && args[1] != "d")) {
        writefln("To compress:   fpaq0 c input output");
        writefln("To decompress: fpaq0 d input output");
        return 1;
    }

    auto start = clock(); // Start timer

    // Open files
    FILE* fin = fopen(args[2].toStringz(), "rb".ptr);
    if (!fin) {
        writefln(args[2]);
        return 1;
    }
    FILE* fout = fopen(args[3].toStringz(), "wb".ptr);
    if (!fout) {
        writefln(args[3]);
        return 1;
    }

    GC.disable;
    if (args[1] == "c")
        compress(fin, fout);
    else
        decompress(fin, fout);

    // Print results
    double stop = (clock() - start) / cast(double)CLOCKS_PER_SEC;
    writefln("%s (%d bytes) -> %s (%d bytes) in %1.2f s",
             args[2], ftell(fin), args[3], ftell(fout), stop);

    fclose(fin);
    fclose(fout);
    return 0;
}