fpaq0 - D - mod

/**
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;
    }
}



enum Mode {COMPRESS, DECOMPRESS}

/**************************************************
An Encoder does arithmetic encoding.

Encoder(COMPRESS, f) creates encoder for compression to archive f, which
must be open past any header for writing in binary mode.

Encoder(DECOMPRESS, f) creates encoder for decompression from archive f,
which must be open past any header for reading in binary mode.
*/
class Encoder {
    private:
        Predictor predictor;
        immutable Mode mode;                // Compress or decompress?
        FILE* archive;            // Compressed data file
        uint x1, x2 = 0xffffffff; // Range, initially [0, 1), scaled by 2^32
        uint x;                   // Last 4 input bytes of archive.

    public:
        this (Mode m, FILE* f) {
            this.mode = m;
            this.archive = f;
            // In DECOMPRESS mode, initialize x to the first 4 bytes of the archive
            if (this.mode == Mode.DECOMPRESS) {
                foreach(i; 0 .. 4) {
                    int c = getc(this.archive);
                    if (c == EOF)
                        c = 0;
                    x = (x << 8) + (c & 0xff);
                }
            }
        }

        /**
        encode(y) -- Encode bit y by splitting the range [x1, x2] in proportion
        to P(1) and P(0) as given by the predictor and narrowing to the appropriate
        subrange. Output leading bytes of the range as they become known.
        */
        nothrow final void encode(int y) {
            // Update the range
            immutable uint xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
            assert(xmid >= x1 && xmid < x2);
            if (y)
                x2 = xmid;
            else
                x1 = xmid + 1;
            predictor.update(y);

            // Shift equal MSB's out
            while (((x1 ^ x2) & 0xff000000) == 0) {
                putc(x2 >> 24, archive);
                x1 <<= 8;
                x2 = (x2 << 8) + 255;
            }
        }

        /**
        Decode one bit from the archive, splitting [x1, x2] as in the encoder
        and returning 1 or 0 depending on which subrange the archive point x is in.
        */
        nothrow final int decode() {
            // Update the range
            immutable uint xmid = x1 + ((x2 - x1) >> 12) * predictor.p();
            assert(xmid >= x1 && xmid < x2);
            int y = 0;
            if (x <= xmid) {
                y = 1;
                x2 = xmid;
            }
            else
                x1 = xmid + 1;
            predictor.update(y);

            // Shift equal MSB's out
            while (((x1 ^ x2) & 0xff000000) == 0) {
                x1 <<= 8;
                x2 = (x2 << 8) + 255;
                int c = getc(this.archive);
                if (c == EOF)
                    c = 0;
                x = (x << 8) + c;
            }
            return y;
        }

        /// Should be called when there is no more to compress.
        final void flush() {
            // In COMPRESS mode, write out the remaining bytes of x, x1 < x < x2
            if (this.mode == Mode.COMPRESS) {
                while (((x1 ^ x2) & 0xff000000) == 0) {
                    putc(x2 >> 24, this.archive);
                    x1 <<= 8;
                    x2 = (x2 << 8) + 255;
                }
                putc(x2 >> 24, this.archive); // First unequal byte.
            }
        }
}


///
void compress(FILE* fin, FILE* fout) {
    auto e = new Encoder(Mode.COMPRESS, fout);
    for ( ; ; ) {
        int c = getc(fin);
        if (c == EOF)
            break;
        e.encode(0);
        for(int i = 7; i >= 0; --i)
            e.encode((c >> i) & 1);
    }
    e.encode(1); // EOF code
    e.flush();
}


///
void decompress(FILE* fin, FILE* fout) {
    auto e = new Encoder(Mode.DECOMPRESS, fin);
    while (!e.decode()) {
        int c = 1;
        while (c < 256)
            c += c + e.decode();
        putc(c - 256, fout);
    }
}


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;
}