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