ZPAQ pre-release

[Matt Mahoney]

ZPAQ v0.01 is released. http://cs.fit.edu/~mmahoney/compression/

This is an experimental level 0 release. This means that the specification is still under development and will probably change in incompatible ways. After more testing and comments, I will release level 1, which should be stable. All level 1 releases after that should be readable by any other level 1 program. Levels 2 and higher will be backward compatible, able to read level 1 (but not 0). When level 1 is released, level 0 is obsolete. Hopefully that will be in about a month.

The most likely changes will be to remove marginally useful components, parameters, and ZPAQL instructions before they become a permanent part of the standard that can't be removed. Features can always be added later to level 2.

One marginally useful component is SSE. It is useful on PAQ8, it turns out, because probabilities very near 0 or 1 get clipped by the squash() and stretch() functions. SSE corrects for stuff like this. That doesn't happen in ZPAQ because all the probability computations are done in the stretched domain. You can also replace SSE with a MIX2 or IMIX2 with one CONST input and a much smaller parameter space (faster learning, less memory), so SSE seems redundant.

I may also change the next-state tables if I can improve compression any.

I may make some changes for optimization purposes. Currently, zpaq 0.01 runs about twice as slow as lpaq1 with a similar model. One optimization I am considering is replacing ZPAQL with a restricted subset of x86 that can be verified safe by the decompressor and executed directly. However, the context hash computation is only 20% of the CPU.

I haven't implemented postprocessing yet. v0.01 won't be able to read archives that use it. I will probably write a E8E9 transform in ZPAQL first, then maybe dictionary coding, LZP, and BWT. This exercise will help me refine the instruction set.

However, it does compress the Calgary corpus to 660K in 37 seconds with one of the supplied config files. I'm sure I could do better with separate config files for each file.

[osmanturan]

Storing restricted x86 code in the archive is a really bad idea. Why don't you use byte-codes and a true VM (with JIT-compiling). It's not so hard and I've some experiment in here (long time ago, I had made a small compiler for delphi which produces native floating point codes with supplied pascal-like code). If you decide your final instruction set, I can help you at here. I personally prefer RISC-like instructions with a few general purpose registers. So, it can be ported any platform. BTW, do you know all Quake3 engine based games used JIT+VM with support both x86 and PowerPC? And it's source code is downloadable from id Software under GPL license. Have a look at the "vm*" files under "quake3-1.32b\code\qcommon" folder. It's used for "mod"s. And all mods compiled with LCC (which is free and very small C compiler - included in the Q3 source) and then it's output (a kind of byte-code) converted to Q3VM and stored in .qvm files like a DLL. And when the game is started, it loads specific .qvm files and parses them and last compiles them into native machine code with JIT.

[Simon Berger]

Thats the same idea toffer posted in the specification thread, isn't it? I also like this idea because it should speed those features up heavily and should minimize the overhead(!?!).
Is there a chance to have faster compression then lpaq with some lightweight models later? zpaq looks like it has the chance to really become useful (besides testing) if the speed would be faster

[Sportman]

I added zpaq to http://www.metacompressor.com/uploads.aspx test files: file17, calgary, calgaryl, file30, file31 it compress mostly better but slower then paq9a with max script.

Surprising is bcm 0.04 compress better and much faster then paq9a at file32.

[mstar]

Test on uncompressed 3D demo data (cna-queen), unzipped and tared(using 7zip), because subfolders seemed not to work.

zpaq.exe cmax.cfg cna-queen.zpaq cna-queen.tar
...
cna-queen.tar 22278656 -> 8187922
Used 298.17 seconds


in comparison, (using defaults/no Parameters):

NanoZip 0.06 alpha
Compressor: nz_optimum1, using 141MB memory.
.../cna-queen.tar
Compressed 22 278 656 into 7 210 481 in 23.20s, 937 KB/s
IO-in: 0.07s, 287 MB/s. IO-out: 0.07s, 89 MB/s

>7z a cna-queen.7z cna-queen.tar
7-Zip 4.65 Copyright (c) 1999-2009 Igor Pavlov 2009-02-03
Scanning
Creating archive cna-queen.7z
Compressing cna-queen.tar
Everything is Ok
...timed in Taskmanager ~10sec, 22278656 to 7499519 Bytes

paq8o8.exe cna-queen.tar
Creating archive cna-queen.tar.paq8o8 with 1 file(s)...
cna-queen.tar 22278656 -> 6457838
22278656 -> 6457875
Time 2467.66 sec, used 226451942 bytes of memory

CPU: AMD X2 4400, 2GB RAM


edit: unpacking:

>zpaq.exe x cna-queen.zpaq
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

Decompressing cna-queen.tar
1 file(s) extracted
Used 298.98 seconds

CRC Checksum and SHA-256 identical (checked with 7-zip)

[Alibert]

For some models it might be useful to process bytes LSB (least significant bit) to MSB (most significant bit) and for other (most!) models MSB to LSB is best. Maybe you want to make this configurable in ZPAQ.

This is just an idea I wanted to share - no request or anything like that.

Alibert

[Matt Mahoney]

For some models it might be useful to process bytes LSB (least significant bit) to MSB (most significant bit) and for other (most!) models MSB to LSB is best. Maybe you want to make this configurable in ZPAQ.

This is just an idea I wanted to share - no request or anything like that.

Alibert

Bit swapping can be done with a preprocessing transform once I implement it. The compressor would swap the bit order and append a ZPAQL program to swap them back. In an earlier version of the spec I wrote all kinds of preprocessing options like bit swap, byte swap, delta coding, E8E9, LZP, BWT, and dictionary. Then I realized these could all be done in a much more flexible way. You could even write a JPEG compressor that undid the Huffman coded DCT coefficients and append a ZPAQL program to redo the Huffman coding. Any existing ZPAQ decompressor could then read your files even though the compression algorithm hadn't even been written yet

A ZPAQL program for bit swap might look like this:

b=a (save a copy of input from a)
c=0 (for the result)
    a>>=7 a&=1 c<>a a|=c c=a (bit 7 to 0, <> means swap)
a=b a>>=5 a&=2 c<>a a|=c c=a (bit 6 to 1)
a=b a>>=3 a&=4 c<>a a|=c c=a (bit 5 to 2)
a=b a>>=1 a&=8 c<>a a|=c c=a (bit 4 to 3)
a=b a<<=1 a&=16 c<>a a|=c c=a (bit 3 to 4)
a=b a<<=3 a&=32 c<>a a|=c c=a (bit 2 to 5)
a=b a<<=5 a&=64 c<>a a|=c c=a (bit 1 to 6)
a=b a<<=7 a&=128 c<>a a|=c (bit 0 to 7)
out (write a to decompressor output)
halt

Note: I did not test this code and there are probably more efficient ways to do this Interpreted ZPAQL is about 8 times slower than optimized C, but it ought to be fast enough. Future implementations will probably compile and optimize the code like they did with Java bytecodes.

The program adds about 70 bytes before compression. A faster version might start with a 256 byte lookup table and some code like this:

jf 4 (to code to initialize M)
b=a (index into lookup table in M)
a=*b (i.e. a=M[b])
out
halt
(insert code here to initialize M and set F to true)

[Mihai Cartoaje]

I thought about having a VM in Libima that converts RAW data into RGB data. Any ideas which VM I should use? GameMonkey, Angelcode, Lua, Java, etc...

[Matt Mahoney]

ZPAQ v0.02. http://cs.fit.edu/~mmahoney/compression/

I added full support for post-processing and an E8E9 transform as a test. The forward transform is written into the C++ code and the reverse transform in ZPAQL, which is appended to the compressed file. To develop, I first wrote the transform both ways in ZPAQL. (The forward and reverse differ by only 1 instruction). I used the ZPAQL "h" command to develop the code and the "p" command to test. I verified the transform first by showing that it improved compression for .exe/.dll for other compressors (ppmonstr) and that the output is restored bit-exact. Then I added an "s" command that converts the ZPAQL code to a list of bytes that I can paste into C++ code. Then I rewrote the forward transform in C++.

During development I realized that both transforms needs to know where the end of the file is. This required an incompatible change to the spec to send an EOF signal to the pre and post processors. (Thus, more testing is required before level 1 is set). Other changes include removing the .= operator (turned out not to be useful) and adding a set of 256 registers (R[0...255]) and a 3 byte jump instruction. These are not needed for E8E9 but might be useful for more complex transforms I still need to write, like dict, LZP, and BWT.

Currently it compresses poorly on large files like when I compress all of maximumcompression.com in a single archive with max.cfg. The last few files get larger. Johan de Bock found a similar problem on a large file. More debugging...

It will be nice in the future to have high level languages compile to ZPAQL, at least add labels, macros, variables, etc. but higher priority now is more testing to refine the standard.

[osmanturan]

With your lastest changes, ZPAQL is now much more like a RISC compatible language Your register banks idea already used in PIC series microcontrollers. But, they have an accumulator (called as W) for most of operation. Adding a single accumulator would make writing a native VM easy for ZPAQL. For example, we can replace single accumulator with EAX in native code.

But, if you want to go on without using an accumulator, it's a good idea to have look GPU fragment programs (written in ARB or NV compatible assembly). In very old specifications (IIRC in NV), the design is similar to yours.

[kaitz]

C:\zpaq\zpaq002>zpaq cmax.cfg enwik8.z enwik8
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

comp 4 9 0 3 19
  0 icm 5
  1 icm 10
  2 icm 14
  3 icm 17
  4 icm 17
  5 icm 17
  6 icm 18
  7 match 21
  8 icm 17
  9 icm 17
  10 icm 10
  11 icm 10
  12 icm 10
  13 icm 16
  14 mix 16 0 14 16 255
  15 mix 8 0 15 16 255
  16 avg 14 15 128
  17 sse 16 16 1 64 255
  18 avg 16 17 160
hcomp
(   0) c++ (17)
(   1) *c=a (104)
(   2) d=0 (28)
(   3) b=c (74)
(   4) a=0 (4)
(   5) d++ (25)
(   6) hash (59)
(   7) *d=a (112)
(   8) b-- (10)
(   9) d++ (25)
(  10) hash (59)
(  11) *d=a (112)
(  12) b-- (10)
(  13) d++ (25)
(  14) hash (59)
(  15) *d=a (112)
(  16) b-- (10)
(  17) d++ (25)
(  18) hash (59)
(  19) *d=a (112)
(  20) b-- (10)
(  21) d++ (25)
(  22) hash (59)
(  23) *d=a (112)
(  24) b-- (10)
(  25) d++ (25)
(  26) hash (59)
(  27) *d=a (112)
(  28) b-- (10)
(  29) d++ (25)
(  30) hash (59)
(  31) *d=a (112)
(  32) b-- (10)
(  33) d++ (25)
(  34) a=*c (69)
(  35) a&~ 32 (183 32)
(  37) a< 65 (231 65)
(  39) jt 11 (to 52) (39 11)
(  41) a> 90 (239 90)
(  43) jt 7 (to 52) (39 7)
(  45) *d<>a (48)
(  46) a+=*d (134)
(  47) a*= 20 (151 20)
(  49) *d=a (112)
(  50) jmp 9 (to 61) (63 9)
(  52) a=*d (70)
(  53) a== 0 (223 0)
(  55) jt 3 (to 60) (39 3)
(  57) d++ (25)
(  58) *d=a (112)
(  59) d-- (26)
(  60) *d=0 (52)
(  61) d++ (25)
(  62) d++ (25)
(  63) b=c (74)
(  64) b-- (10)
(  65) a=0 (4)
(  66) hash (59)
(  67) *d=a (112)
(  68) d++ (25)
(  69) b-- (10)
(  70) a=0 (4)
(  71) hash (59)
(  72) *d=a (112)
(  73) d++ (25)
(  74) b-- (10)
(  75) a=0 (4)
(  76) hash (59)
(  77) *d=a (112)
(  78) d++ (25)
(  79) a=b (65)
(  80) a-= 212 (143 212)
(  82) b=a (72)
(  83) a=0 (4)
(  84) hash (59)
(  85) *d=a (112)
(  86) b<>a (8)
(  87) a-= 216 (143 216)
(  89) b<>a (8)
(  90) a=*b (68)
(  91) a&= 60 (175 60)
(  93) hashd (60)
(  94) d++ (25)
(  95) a=*c (69)
(  96) a<<= 8 (207 8)
(  98) *d=a (112)
(  99) d++ (25)
( 100) d++ (25)
( 101) d++ (25)
( 102) *d=a (112)
( 103) halt (56)
( 104) post (cend=62 hbegin=190 hend=295 hsize=165 Memory=93.162 MB)

0 enwik8 100000000 -> 20681193
Used 1019.63 seconds



C:\zpaq\zpaq002>zpaqd.exe x enwik8.z
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

Decompressing enwik8
1 file(s) extracted
Used 1299.17 seconds

CRC ok.

Core2Duo CPU E4500 @ 2.20GHz
RAM DDR2, PC2-5300 333 MHz

Tested same time when surfing on web.

[Matt Mahoney]

Thanks for testing. I have a new version (v0.03) that fixes poor compression on some large files due to arithmetic overflow in the mixers. Also a simpler stretch() function that slightly improves compression. I still need to make up config files tuned for enwik8/9, uiq, individual files in Calgary corpus, maximumcompression, etc. I think there is a lot of room to improve. The newest version compresses maximumcompression to 10,548,826 with E8E9 transform on for all files, but obviously this is only needed for .exe and .dll and could be turned off for the other 8 for better compression. Text files should benefit from dictionary preprocessing, which I haven't written yet.

Other likely changes: remove SSE, since IMIX2 serves the same purpose and works better with less memory. Maybe change bit history table if I find one that works better. I may fiddle with the instruction set but I can't think of any needed changes right now. I'm sure I will get some ideas when I start writing more complicated transforms. Right now program size is limited to 64K but I doubt anyone would want to write more than that much code in ZPAQL

BTW, the A register in ZPAQL serves as an accumulator. All of the arithmetic and logical operators use it as a destination (except comparison, with result in F). For compiling, A, B, C, D, and F could be mapped to general purpose registers (with F optimized out sometimes), and H, M, and R to memory arrays.

[Hahobas]

Here's some benchmarks comparing different versions of gcc with zpaq003:

Each is an average of 3 runnings:
Test file is the first 2 Megabytes of enwik8
zpaq cmax.cfg archive enwik8_first2M

32-bit Linux executables:
zpaq_gcc_431_O1: 36.84 seconds
zpaq_gcc_431_O2: 34.44 seconds
zpaq_gcc_431_O3: 40.14 seconds

zpaq_gcc_44_O1: 40.51 seconds (9% Slower)
zpaq_gcc_44_O2: 37.04 seconds (9.2% Slower)
zpaq_gcc_44_O3: 49.3 seconds (8.1% Slower)

And now 64-bit Linux executables
zpaq_gcc_432_O2: 34.27 seconds
zpaq_gcc_432_O3: 39.88 seconds

zpaq_gcc_44_O2: 34.21 seconds ( 0.1 % faster)
zpaq_gcc_44_O3: 44.69 seconds (12% slower)

Looks like gcc4.4's 32bit executables suffer some performance regressions from 4.3.1. In the 64-bit arena, it doesn't look as bad, but O3 has a bad performance hit. The 32 vs 64bit comparison isn't very good however because I used gcc 4.4 from Fedora 11 for the 32-bit executables, and I used a probably newer revision (compiled myself from the trunk) for the 64-bit tests. For kicks I also tried the graphite loop optimizations, but as I expected, no difference in performance.

[joerg]

congratulation Matt: zpaq 003 is the first really usable version for me

(the file max.cfg = zpmax.cfg you have changed in every version)
---
The Testfile db.dmp (Oracle-dump-file) has 648331264 bytes.

zpaq czpmin.cfg ..\RESULT\tdzpaqmi ..\ORGDTA\db.dmp
zpaq czpmax.cfg ..\RESULT\tdzpaqma ..\ORGDTA\db.dmp
---
zpaq 0.01
result: tdzpaqmi = 135.916.858 bytes tdzpaqma = 1.235.664.553 bytes ??
zpaq 0.02
result: tdzpaqmi = 135.916.858 bytes tdzpaqma = 1.235.664.553 bytes ??
zpaq 0.03
result: tdzpaqmi = 136.669.356 bytes on CORE2DUO time= 290 sec
tdzpaqma = 17.137.735 bytes on CORE2DUO time= 4920 sec

very good result !
but i remember ...
- with paq8o8 the result was approximately 9.000.000 bytes ...

[kaitz]

C:\zpaq\zpaq003>zpaq cmax.cfg enwik8.z enwik8
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

enwik8 100000000 -> 20093605
-> 20093605
Used 1011.59 seconds

[Black_Fox]

Tested, with pht in 0.01 once again as performance killer 0.03 is OK, though.

[mstar]

Test on same 3D demo data (cna-queen) unzipped and tared. (I've chosen that one because of the uncompressed 3d data. Same TAR as above.)

>zpaq cmax.cfg cna-queen.zpaq003 cna-queen.tar
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

cna-queen.tar 22278656 -> 7153392
-> 7153392
Used 296.01 seconds

>zpaq x cna-queen.zpaq003
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

Decompressing cna-queen.tar
1 file(s) extracted
Used 296.58 seconds

CRC ok.

Nice improvement!

[Matt Mahoney]

zpaq v0.04. http://cs.fit.edu/~mmahoney/compression/

Updated train() and squash() in specification for improved compression. This fixes a bug in SSE that caused poor compression (overflow in CM) that possibly affected other components too. SSE turns out to be superior to IMIX2 so I plan to keep it. Calgary corpus improved from 660K to 655K.

I plan to release level 1 when I can go a month of testing without breaking compatibility. So far the average is about 2 days.

[mstar]

Same Tar with 004:

>zpaq cmax.cfg cna-queen.zpaq004 cna-queen.tar
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

cna-queen.tar 22278656 -> 7181772
-> 7181772
Used 299.61 seconds

>zpaq x cna-queen.zpaq004
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

Decompressing cna-queen.tar
1 file(s) extracted
Used 300.11 seconds

A bit lower compression ratio with 3D Data.

CRC ok.

[Matt Mahoney]

Here are some more experiments where I compare a paq8 and paq9a style models. In the paq8 style, a set of context models with orders 0-5 plus an order-6 match model are mixed at the end. In paq9a style, the predictions are cascaded as a series of 2 input mixers with one input fixed and the contexts in increasing order. The context selects a bit history which selects a set of mixer weights. This differs from paq8 style ICM where the context selects a bit history which selects a probability table entry and a counter to control update rate (StateMap in paq. The models otherwise use the same memory and contexts. Here is the code with the paq8 style commented out:

comp 4 4 0 3 9 (hh hm ph pm n)
(
  (paq8 style context models with mixer at end)
  0 const 160 (not used, for comparison only)
  1 icm 5 (order 0-5 context models)
  2 icm 10
  3 icm 15
  4 icm 16
  5 icm 16
  6 icm 16
  7 match 19 (order 6, 2 MB buffer, 2 MB index)
  8 mix 16 1 7 16 255 (mix everything except const)
)
  (paq9a style mixer chain)
  0 const 160
  1 icm 5
  2 imix2 10 0 1 64 16 (mixes 0 and 1 with order 2 context)
  3 imix2 15 0 2 64 16 (mixes 0 and 2 with order 3 context, etc)
  4 imix2 16 0 3 64 16
  5 imix2 16 0 4 64 16
  6 imix2 16 0 5 64 16
  7 match 19
  8 mix 16 1 7 16 255 (mix everything except const)

hcomp
  c++ *c=a b=c a=0 (save byte in rotating buffer M)
  d= 2 hash *d=a b-- (order 0-5 in comp 1-6)
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a (match order 6)
  d++ a=*c a<<= 8 *d=a (mix order 1)
  halt
post
  0  (0=PASS, x=E8E9. if x, set ph=0, pm=3)
end

Results: Calgary corpus: paq8 = 714090, 14.1 sec. paq9a = 704235, 15.7 sec.

enwik8: paq8 = 22274511, 452 sec. paq9a = 22003374, 504 sec.

This is not exactly paq9a style because the final mixer mixes all the predictions again. This greatly improves compression however.

Of course this compression is not very high because there are no specialized text models, no SSE at the end, and because of the small (21 MB) memory model used.

So it looks like both IMIX2 and SSE are useful, so they stay in the spec.

[mstar]

With paq9a style (copied from your last post) i got the following results:

zpaq cmaxpaq9style.cfg cna-queen.zpaq004 cna-queen.tar

cna-queen.tar 22278656 -> 7638858
-> 7638858
Used 127.02 seconds

>zpaq x cna-queen.zpaq004

Decompressing cna-queen.tar
1 file(s) extracted
Used 127.81 seconds

2.5 times faster with nearly the same compression!

Using the fast config i got the following results:

>zpaq cmin.cfg cna-queen.zpaq004 cna-queen.tar

cna-queen.tar 22278656 -> 12116934
-> 12116934
Used 16.64 seconds

>zpaq x cna-queen.zpaq004

Decompressing cna-queen.tar
1 file(s) extracted
Used 17.06 seconds

Because of the high speed i started playing with the values of the cm model in the config file:

  0 cm 20 12

With lowering the limit from 12 to 2 i got the smallest archive for my file:

  0 cm 20 2

>zpaq cmincm3224.cfg cna-queen.zpaq004a cna-queen.tar

cna-queen.tar 22278656 -> 11312027
-> 11312027
Used 16.63 seconds

edit:
reducing sizebits to 18 gave an additional compression ratio improvement for this file:

  0 cm 18 2

>zpaq cmincm3224.cfg cna-queen.zpaq004a cna-queen.tar

cna-queen.tar 22278656 -> 11000709
-> 11000709
Used 16.09 seconds

[Simon Berger]

Interesting would be to really compare zpaq with paq8, paq9 and lpaq8. If no other one does so already I will try it this evening. What I thought currently is it's for example much slower then lpaq on almost the same compression level. But there seems to be a better possibility to change the model.

[nanoflooder]

aaz@rover:~$ ls -laS calgary.*
-rw-r--r-- 1 aaz aaz 3152896 2007-08-16 04:32 calgary.tar
-rw-r--r-- 1 aaz aaz  676847 2009-02-22 16:36 calgary.tar.paq9a
-rw-r--r-- 1 aaz aaz  676409 2009-02-22 16:28 calgary.tar.lpaq8
-rw-r--r-- 1 aaz aaz  655061 2009-02-22 16:26 calgary.tar.zpaq
-rw-r--r-- 1 aaz aaz  617980 2009-02-22 16:34 calgary.tar.paq8p1_exp04.paq8p1

I would gladly perform a better testing, but don't have Windows anywhere near For the obsolete versions you can watch this table.

[Matt Mahoney]

Also, I think it is possible to enter ZPAQ in the Calgary challenge by playing with the configuration files. http://mailcom.com/challenge/

It will involve probably different configuration files for each file to be compressed, or maybe a common one for the text files. For text, it would also involve probably a dictionary transform, which means writing the forward transform in C++ and the inverse in ZPAQL. There is also a useful transform for GEO I believe (convert the weird IBM floats to integers and use linear predictive filters and store the prediction errors). Then it would involve a separate program UNZPAQ made from a stripped down version of ZPAQ with just the x command to extract.

[Matt Mahoney]

Here is an update. I modified max.cfg to replace the paq8 style mixing with a paq9a chain. This improved the Calgary corpus from 655K to 650K. I also fixed the word order 1 context (it was sparse before) for another 3K. Chaining the order 0 and 1 word contexts improved another 0.4K and increasing the order 6-7 contexts by 1 (skipping order 6) improved another 0.4K.

Mixer chains only work when going from low order to high order of the same kind of contexts. For example, chaining the sparse contexts made compression worse. So does chaining the word contexts onto the end of the character contexts.

(zpaq 0.04 file tuned for high compression (slow)
on the Calgary corpus. Uses 278 MB memory)

comp 5 9 0 3 22 (hh hm ph pm n)
  0 const 160
  1 icm 5  (orders 0-6)
  2 imix2 13 0 1 64 16
  3 imix2 16 0 2 64 16
  4 imix2 18 0 3 64 16
  5 imix2 19 0 4 64 16
  6 imix2 20 0 5 64 16
  7 imix2 20 0 6 64 16
  8 match 22
  9 icm 17 (order 0 word)
  10 imix2 19 0 9 64 16 (order 1 word)
  11 icm 10 (sparse with gaps 1-3)
  12 icm 10
  13 icm 10
  14 icm 14 (pic)
  15 mix 16 0 15 24 255 (mix orders 1 and 0)
  16 mix 8 0 16 10 255 (including last mixer)
  17 avg 15 16 64 (average of both mixers)
  18 sse 8 17 32 255 255 (order 0)
  19 avg 17 18 64
  20 sse 16 19 32 255 255 (order 1)
  21 avg 19 20 96
hcomp
  c++ *c=a b=c a=0 (save in rotating buffer)
  d= 2 hash *d=a b-- (orders 1,2,3,4,5,7)
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash b-- hash *d=a b--
  d++ hash *d=a b-- (match, order 8)
  d++ a=*c a&~ 32 (lowercase words)
    a< 65 jt 14 a> 90 jt 10
    d++ hashd d-- (added: update order 1 word hash)
    *d<>a a+=*d a*= 20 *d=a jmp 9
    a=*d a== 0 jt 3 (order 1 word)
       d++ *d=a d--
    *d=0 d++
  d++ b=c b-- a=0 hash *d=a (sparse 2)
  d++ b-- a=0 hash *d=a (sparse 3)
  d++ b-- a=0 hash *d=a (sparse 4)
  d++ a=b a-= 212 b=a a=0 hash
    *d=a b<>a a-= 216 b<>a a=*b a&= 60 hashd (pic)
  d++ a=*c a<<= 9 *d=a (mix)
  d++
  d++
  d++ d++
  d++ *d=a (sse)
  halt
post
  0  (may be 0 for PASS or x for EXE/DLL (E8E9))
     (if x, set ph=0, pm=3)
end

Result:

278.473 MB memory required.
calgary\BIB 111261 -> 23689
calgary\BOOK1 768771 -> 199077
calgary\BOOK2 610856 -> 124026
calgary\GEO 102400 -> 46856
calgary\NEWS 377109 -> 90774
calgary\OBJ1 21504 -> 8838
calgary\OBJ2 246814 -> 56364
calgary\PAPER1 53161 -> 11192
calgary\PAPER2 82199 -> 17126
calgary\PIC 513216 -> 28690
calgary\PROGC 39611 -> 9137
calgary\PROGL 71646 -> 11062
calgary\PROGP 49379 -> 7977
calgary\TRANS 93695 -> 11628
-> 646436
 1: 271/2048 (13.23%)
 2: 54510/524288 (10.40%)
 3: 654721/4194304 (15.61%)
 4: 2041588/16777216 (12.17%)
 5: 4099140/33554432 (12.22%)
 6: 6439283/67108864 (9.60%)
 7: 11186259/67108864 (16.67%)
 8: 2620974/16777216 (15.62%)
 9: 717822/8388608 (8.56%)
10: 6904750/33554432 (20.58%)
11: 34982/65536 (53.38%)
12: 38923/65536 (59.39%)
13: 42014/65536 (64.11%)
14: 454900/1048576 (43.38%)
Used 43.34 seconds

The results show memory used by component. I'm still developing this code.

[joerg]

The Testfile db.dmp (Oracle-dump-file) has 648331264 bytes.

zpaq czpmin.cfg ..\RESULT\tdzpaqmi ..\ORGDTA\db.dmp
zpaq czpmax.cfg ..\RESULT\tdzpaqma ..\ORGDTA\db.dmp
---
zpaq 0.03 result:

tdzpaqmi = 136.669.356 bytes on CORE2DUO time= 290 sec
tdzpaqma = 17.137.735 bytes on CORE2DUO time= 4920 sec
---
zpaq 0.04 result:

tdzpaqmi = 78.064.730 bytes on CORE2DUO time= 292 sec
tdzpaqma = 15.924.959 bytes on CORE2DUO time= 6090 sec

wonderful
- very good improvement in compression!
- the compression for min.cfg is significantly improved too!

---

"ZPAQ v0.04 archiver" ??

is here a support for a directory-tree?

can i compress/uncompress a whole directory inclusive subdirectories ?

like

zpaq czpmin.cfg -r archivfile D:\ORGDTA\*

means "compress all files and directories under D:\ORGDTA\"

another method could be to support a listfile - like

zpaq czpmin.cfg archivfile @listfile.txt

where listfile.txt contains the filenames inclusively the directory-path

like for example
listfile.txt
---
d:\ORGDTA\db.dmp
d:\ORGDTA\20070101\db.dmp
d:\ORGDTA\20070101\README.TXT
---
---
i propose a later release of the version 1 with full directory-support
---
---
another good thing in the future
would be to have the possiblity to recompress an archiv

should means
in a first run compress the source with min.cfg
and in a second run recompress the resulting file with max.cfg

best regards

[kaitz]

C:\zpaq\zpaq004>zpaq cmax.cfg enwik8.z enwik8
Warning: ZPAQ Level 0 is experimental. Different versions
are not compatible with each other or with level 1. This format will be
obsolete with the release of level 1.

enwik8 100000000 -> 19886751
-> 19886751
Used 1012.51 seconds

E:

C:\paq9a\paq9a a enwik8.a -9 enwik8
enwik8 100000000 -> 19974101
-> 19974112 in 344.05 sec
HashTable<16> 72.7125% full, 25.8159% utilized of 1048576 KiB
LZP hash table 48.8231% full of 262144 KiB
LZP buffer 37.2529% full of 262144 KiB
LZP 68965046 literals, 31034954 matches (31.0350% matched)
Used 1585653 KiB memory

[mstar]

A quick run with the actual paq8-9 cfg taken from your post #25:

>zpaq cmaxpaq9style2.cfg cna-queen.zpaq004b cna-queen.tar

cna-queen.tar 22278656 -> 7114010
-> 7114010
Used 321.20 seconds

>zpaq x cna-queen.zpaq004b

Decompressing cna-queen.tar
1 file(s) extracted
Used 320.97 seconds

[russelms]

I compressed enwik9 over the weekend with a slightly modified cmax.cfg.

The results are pretty good given no special pre-processing is taking place. I look forward to further development of ZPAQ.

zpaq 0.04 cmax_029
enwik9 -> 1000000000.00 -> 166725279.00
Used 8230.50 seconds

zpaq 0.04 cmax_029
enwik8 -> 100000000.00 -> 19599868
Used 821.94 seconds


cmax_029.cfg:

(zpaq 0.04 file tuned for high compression (slow)
on the Calgary corpus. Uses 322 MB memory)

comp 5 9 0 3 22 (hh hm ph pm n)
  0 icm 4  (orders 0-7)
  1 icm 6  
  2 icm 11
  3 icm 17
  4 icm 19
  5 icm 20
  6 icm 19
  7 icm 20
  8 match 23 (order 7)
  9 icm 19 (order 0 word)
  10 icm 19 (order 1 word)
  11 icm 11 (sparse with gaps 1-3)
  12 icm 11
  13 icm 11
  14 icm 16 (pic)
  15 mix 22 0 14 8 255 (mix orders 1 and 0)
  16 sse 16 15 32 255 255 (order 0)
  17 avg 15 16 64 (average of both mixers)
  18 mix 16 0 17 16 255 (including last mixer)
  19 avg 17 18 96
  20 sse 16 19 32 255 255 (order 1)
  21 avg 19 20 96
hcomp
  c++ *c=a (save in rotating buffer)
  d=0 b=c a=0
  d++ hash *d=a b-- (orders 1-6)
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b--
  d++ hash *d=a b-- (match)
  d++ a=*c a&~ 32 (lowercase words)
    a< 65 jt 11 a> 90 jt 7
    *d<>a a+=*d a*= 20 *d=a jmp 9
    a=*d a== 0 jt 3 (order 1 word)
       d++ *d=a d--
    *d=0 d++
  d++ b=c b-- a=0 hash *d=a (sparse 2)  
  d++ b-- a=0 hash *d=a (sparse 3)
  d++ b-- a=0 hash *d=a (sparse 4)
  d++ a=b a-= 212 b=a a=0 hash
    *d=a b<>a a-= 216 b<>a a=*b a&= 60 hashd (pic)
  d++ a=*c a<<= 9 *d=a (mix)
  d++
  d++
  d++ d++
  d++ *d=a (sse)
  halt
post
  0  (may be 0 for PASS or x for EXE/DLL (E8E9))
     (if x, set ph=0, pm=3)
end

[Matt Mahoney]

"ZPAQ v0.04 archiver" ??

is here a support for a directory-tree?

can i compress/uncompress a whole directory inclusive subdirectories ?

Not with the current program, but the archive format supports it. It will only compress the files you name on the command line. In Windows you get wildcard expansion with the g++ compiled versions only (because it is built in to g++). It is still possible to create directory trees this way, however. During extraction, the program will not create new directories, but it will decompress to them if they exist.

PAQ8 has code for recursing subdirectories and creating directories, but it is not portable between Windows and Linux. (You need to compile with -DWINDOWS or -DUNIX). I could put this in, but it is not my priority now. I am working on good compression and a stable format.

Also, I am experimenting with changing the probability precision from 12 bits to 16. This should improve compression slightly on highly redundant files. Also, I am changing the spec so that 32 bit arithmetic overflow in the mixers is impossible (by bounding the weights and probabilities to signed 16 bits). Clamping numbers to 16 bits takes extra instructions but there is a potentially fast implementation in MMX/SSE2 (not writing it yet) and it won't break when ported to 64 bits, so it makes sense to do it.