Fpaq0pv3 file Compressor

[Nania Francesco]

Fpaq0p v3 released
by Matt Mahoney
have contributed:
- Ilia Muraviev
- Nania Francesco Antonio
it is completely compatible with the version FPAQ0P!
link:
http://www.winturtle.netsons.org/fpaq0pv3.zip

[LovePimple]

Thanks Francesco!

[Shelwien]

For speed optimization I'd suggest removing per-byte EOF
(at least make it blockwise or something)
and replacing putc/getc with some buffered i/o,
and removing that cxt>=512 condition from Predictor::update()
(it can be explicitly set before encoding each byte)
and replacing that if(y) in Predictor::update() with
something like p[cxt]-=int(p[cxt]-((-y)&PSCALE))>>5;
and I don't like that rangecoding either.

But anyway getc/putc are probably the slowest things there,
especially when compiling with gcc and the likes.

[Nania Francesco]

I thank for the suggestion Shelwien , I have tried him but there am no advantages with GCC 4.1.2 and it is not more compatible with Fpaq0p. I believe that even if written badly in C++ for the Gas (G++ assembler) as Compilation goes better.

[Shelwien]

Well, here goes:
http://shelwien.googlepages.com/fpaq0pv4.htm
http://shelwien.googlepages.com/fpaq0pv4.rar

Datasize  Ctime  Dtime Notes 
43872902 10.608 10.625 fpaq0p 
43872902  9.174  9.549 IC 10.1.013 /ML /Ox /QxN /Qipo /DNDEBUG 
43769967  9.110 10.422 fpaq0pv2 
43769967  9.640 10.095 IC 10.1.013 /ML /Ox /QxN /Qipo /DNDEBUG 
43872902  7.988  9.781 fpaq0pv3 GCC 4.1.2/mingw? 
43872902  8.112 12.751 IC 10.1.013 /ML /Ox /arch:ia32 /Qipo- (IntelC build from v3 source) 
43872902  6.612  7.625 fpaq0pv3.cpp5c 
43872902  6.670  7.655 fpaq0pv4 (compatible) 
43783911  6.358  7.436 bytewise eof removed 
43769209  6.142  7.139 fpaq0pv4nc0.cpp, /O2 /Qipo 
43777470  6.048  7.157 exexexex (odd/even different renorm) 
43793403  5.919  7.064 exxexxex 
43805888  5.874  6.954 exxxexxx 
43805888  5.813  6.952 fpaq0pv4nc.cpp, /O2 /Qipo

So I did it myself, and seems that my ideas _did_ help (including getc/putc one),
despite IntelC's apparent inability to compile something competitive
(well, maybe its a matter of libraries, specifically i/o).
Also I don't currently have gcc4/mingw here, so it would be helpful if somebody compiles
my sources with it.

[LovePimple]

Thanks Shelwien!

[Nania Francesco]

Thanks Shelwien! Very good work!

[Nania Francesco]

Test for this versions
MOC Test
Fpaq0pv4nc0-> Crash in compression!
Fpaq0pv4nc_-> Crash in compression!
Fpaq0pv4___-> 231.387.340 B - time enc.22,854 dec. 22,826 s. (All ok!)
Fpaq0p_____-> 231.387.340 B - time enc.23,578 dec. 29,149 s. (All ok!)
SFC Test
Fpaq0pv4nc_-> enc.3,171 s. dec.3,658 s. (All OK!)
Fpaq0pv4nc0-> enc.3,111 s. dec.3,785 s. (All OK!)
Fpaq0pv4___-> enc.3,378 s. dec.3,890 s. (All ok!)
Fpaq0p_____-> enc.3,766 s. dec.4,958 s. (All ok!)

[Nania Francesco]

Fpaq0p v5 released
by Matt Mahoney
have contributed:
- Ilia Muraviev
- Nania Francesco Antonio
- Shelwien
it is completely compatible with the version FPAQ0P! Very faster!
link:
http://www.winturtle.netsons.org/fpaq0pv5.zip

[Nania Francesco]

Test versions 5
MOC Test
Fpaq0pv5-> 231.387.340 B - time enc.19,357 dec. 21,918 s. (All ok!)
Fpaq0pv4-> 231.387.340 B - time enc.22,854 dec. 22,826 s. (All ok!)
Fpaq0pv3-> 231.387.340 B - time enc.23,578 dec. 29,149 s. (All ok!)
Fpaq0p(Old)> 231.387.340 B - time enc.30,801 dec. 29,467 s. (All ok!)
SFC Test
Fpaq0pv5___-> enc.3,171 s. dec.3,658 s. (All OK!)
Fpaq0pv4___-> enc.3,378 s. dec.3,890 s. (All ok!)
Fpaq0pv3___-> enc.3,766 s. dec.4,958 s. (All ok!)
Fpaq0p(old)_-> enc.5,310 s. dec.4,938 s. (All ok!)

[LovePimple]

Thanks Francesco!

[Nania Francesco]

Intel Core duo 2 E6600
Enwik9 test compression time [best of 3 test]
Fpaq0pv5----> 54,56 sec.
Fpaq0pv4----> 55,98 sec.
Fpaq0pv3----> 75,31 sec.
Fpaq0p(Old)-> 98,70 sec.

[Shelwien]

http://shelwien.googlepages.com/fpaq0pv4A.htm
http://shelwien.googlepages.com/fpaq0pv4A.rar

In general:
- coder versions merged
- Predictor/Encoder/Decoder classes merged
- "test" mode added (encode, then decode)
- Speed of all versions improved again

About nc version:
- bug with 1M-aligned file size fixed
- bug on last byte(s) fixed by storing two bytes on flush
(Matt's rangecoder doesn't work properly without improbable
symbol, like eof, at the end - its supposed to do most of flush)

Things that went wrong:
- Got gcc 4.3.0/mingw, but was unable to reach comparable (to Fpaq0pv5.exe)
results without -fprofile-generate/use
- Versions built with IntelC -Qprof_gen/use work slower than without it
- Static allocation of single Coder instance didn't work (ie was slow),
seems that code with ESP offsets (with stack allocation) is significantly
more compact than code with fixed addresses.
- RC renorm. only on low probability took too much additional checks to
implement (damn that rc with its underflows)
- Direct cxt calculation on encoding wasn't faster

Other thoughts:
- These kinds of coders can be easily threaded by separating high and
low bits. Eg. we can use two rangecoders with two buffers, one of which
would encode bits4..7 and other bits0..3. Higher bits are generally more
predictable, so their (de)coding would run faster, so most of execution
time can be overlapped. I'd try it if somebody in this town would only
sell me a Q9450.

[Nania Francesco]

Test All versions
MOC Test [BEST result of 3 test]
Fpaq0pv4Anc--> 230.974.936 B - time enc.16,627 dec. 18,841 s. (All ok!)
Fpaq0pv4Anc0-> 230.945.390 B - time enc.18,776 dec. 19,968 s. (All ok!)
Fpaq0pv4A----> 231.387.340 B - time enc.18,858 dec. 21,408 s. (All ok!)
Fpaq0pv5-----> 231.387.340 B - time enc.19,357 dec. 21,918 s. (All ok!)
Fpaq0pv4-----> 231.387.340 B - time enc.22,854 dec. 22,826 s. (All ok!)
Fpaq0pv3-----> 231.387.340 B - time enc.23,578 dec. 29,149 s. (All ok!)
Fpaq0p(Old)--> 231.387.340 B - time enc.30,801 dec. 29,467 s. (All ok!)
SFC Test [BEST result of 3 test]
Fpaq0pv4Anc--> 35.201.383 B enc.2,624 s. dec.2,922 s. (All ok!)
Fpaq0pv4Anc0-> 35.181.697 B enc.3.033 s. dec.3,281 s. (All ok!)
Fpaq0pv4A----> 35.272.308 B enc.3,095 s. dec.3,343 s. (All ok!)
Fpaq0pv5-----> 35.272.308 B enc.3,171 s. dec.3,658 s. (All oK!)
Fpaq0pv4-----> 35.272.308 B enc.3,378 s. dec.3,890 s. (All ok!)
Fpaq0pv3-----> 35.272.308 B enc.3,766 s. dec.4,958 s. (All ok!)
Fpaq0p(old)--> 35.272.308 B enc.5,310 s. dec.4,938 s. (All ok!)