rzip looked promising. I started hacking it a bit here and there mainly in main.c and in the stream.c and got rid of libbz in it so now I may use it as preprocessor before gzip.

I threw urandom data at this hacked variant and was not able to decompress what was compressed at -0 and -1 levels. Then i runned original rzip-2.0 against the same urandom data and it shows same bug.

So the hint is: Don't use version 2.0 (rzip.samba.org OR debian's 2.0-2) with compression levels -0 and -1 for anything inmportant before first checking if you can decompress. Other levels were fine with same data but I was not giving it any heavy testing.

Still it's able to cut in 10 minutes from 6538537833B of mail+spam down to 4466144683B at compression level 0 (these data decompresses cleanly) here and that is the hacked version without bzip2 - only rzip's own part. Yet the hacked variant without bzip at level -9 is terribly slow - but the system was swapping/trashing/mmaping(comparing large chunks of data) heavily