Precomp 0.4.1

[schnaader]

As an early christmas present: Precomp 0.4.1 is out. List of changes:

* New switch -c for on-the-fly compression, bZip2 used by default ("-c-" restores old behaviour).
* Old switches -c and -m merged to the new -zl ("zlib levels") switch.
* Fixed bugs in multi PNG, GIF and penalty bytes handling that led to differences in the recompressed file.
* Time output is human readable now.
* Various small bugfixes.
* ZLIB1.DLL is needed again - static linking led to crashes in some cases.

Have a look at http://schnaader.info/precomp.php

[zody]

Yeah, amazing!
Great, I will do some test with files, which had errors on last version, in a few days =)
Thanks schnaader !

[Shelwien]

Thanks.
If you'd like, I can make an exe with integrated dlls for it, with dllmerge.
Also what do you think about lzma recompression?

[schnaader]

Thanks.
If you'd like, I can make an exe with integrated dlls for it, with dllmerge.

Didn't know there's something like this. This would indeed be useful.

Also what do you think about lzma recompression?

I'm working on it. After the long delay, I just wanted to quickly release another version and it wasn't even planned to add the compression switch, but I had some debugging luck today and fixed some bugs that were left in it. So, yes, LZMA recompression should be available in the next release.

[Shelwien]

> Didn't know there's something like this. This would indeed be useful.

Well, here's a demo for you - run make.bat to get a single (seemingly) working precomp.exe
of size 246272.

http://nishi.dreamhosters.com/u/dllmerge-precomp041.rar

About dllmerge:
dllmerge combines the sections from 1 exe PE32 file and 1 PE32
dll, and creates a single exe with resolved dll calls and added
explicit dll init/uninit calls.
Its possible to merge multiple dlls with exe one by one.
I made it for reverse-engineering purposes actually, because
Ida doesn't support working with multiple binary modules at once.
But integrating dlls into tools such as precomp also seems convenient.
Unfortunately there's some manual tweaking involved to make it work.
Its necessary to fix up the dll's relocations to make it a part of
executable. But atm this part is done with rebase.exe from
windows SDK (hacked to allow unaligned bases).
So its necessary to first look up the exe's ImageBase (usually 0x400000)
and ImageSize, and rebase the dll to ImageBase+ImageSize-0x1000
(-1000 because of implied dll header section which we're discarding).
Its also commonly necessary to resolve various dll's quirks first -
like unpack it with upx, or (not in this case) remove manifests,
signatures, and various other similar stuff which won't let exe work
after modification.
Btw, packjpg.dll contains debuginfo for unknown reason, which can
be stripped with mingw/cygwin "strip" tool, but dllmerge doesn't copy
it anyway.

> So, yes, LZMA recompression should be available in the next release.

Ah, that's good too, but I actually meant my own lzma recompression,
from http://encode.su/threads/1177
Its a different type of recompression than yours, though, symmetric one
(I think we discussed that before).
There's not much gain though, I'd expect 2-5% on average (maybe more
for streams w/o parsing optimization? i didn't test), but at least
its possible at all, while compressing unpacked binary data better than
lzma is pretty troublesome, unless you can use something like paq8.

[BuraQ]

I do not know if there is any technique or tool present to alter the file name from even it has an error of dll. or file specified. Please tell me how to make dllmerge and the things described in the forum about Lzma.I will be looking forward

[VoLT]

Thx!
Have is some news on dll for inno?

Спасибо!
Есть ли какие нибудь новости об DLL для Inno

[Intrinsic]

Superb thanks Schnaader! I guess this is using the latest PackJPG right?

[schnaader]

I actually meant my own lzma recompression, from http://encode.su/threads/1177
Its a different type of recompression than yours, though, symmetric one (I think we discussed that before).

Trying to compress the different raw LZMA codes (dist,len,literals...) with different algorithms, if I understand correctly - has the big advantage to be well-defined. Looks promising indeed.
Have you tried similar things on zLib streams? You'd get much better compression there.

There's not much gain though, I'd expect 2-5% on average (maybe more
for streams w/o parsing optimization? i didn't test), but at least
its possible at all, while compressing unpacked binary data better than
lzma is pretty troublesome, unless you can use something like paq8.

The downside is it only sees the raw codes, not the decompressed data, right? That's what gives Precomp the biggest compression boost, f.e. I'm planning to support the XZ format which basically is LZMA - just decompressing and recompressing with f.e. 7-Zip Ultra (or even PAQ) doesn't improve compression or even makes it worse and supporting XZ would be useless. But f.e. Precomp recognizes a PDF stream inside the decompressed XZ stream which can be optimized:

Original: 10,2 MB - best compression about 10 MB
Decompressed: 20,7 MB - best compression about 9,9 MB
Decompressed+Precomp: 49,8 MB - best compression about 5,5 MB (at this point even bZip2 helps: 7,5 MB)

Superb thanks Schnaader! I guess this is using the latest PackJPG right?

No, unfortunately it's still the old WIP version, I need to ask Matthias for a new DLL. Might be available in the next release. But I'm still not sure about PackJPG, perhaps it will be turned off by default in the next version because there are some JPG files that even crash the original PackJPG reproducable - these are corrupt JPGs and they aren't common, but I'd like to maximize stability for Precomp as much as possible.

[Shelwien]

> Trying to compress the different raw LZMA codes
> (dist,len,literals...) with different algorithms,

I ended up with 4 distinct streams there: id (0..6), literal,
len (0..271), dist (0..2^32-1).
Besides simple literals and matches there're also rep0..3 and rep0long ids.

> if I understand correctly - has the big advantage to be well-defined.

But dumping them and "compressing with different algorithms" (ie external compressors)
doesn't really work at all (except for literals) - only paq8 handles numbers better
than unaligned sequences of bytes, and even paq8 is pretty bad at it.

> Looks promising indeed.

Not quite:

icl.exe SFC     enwik8
996740 12172597 24560059 (original lzma)
991153 12076928 24496752 (lit model with SSE)
972802 12051193 24502170 15.12.2010 (logistic mix-3 in lit model)
969626 12020481 24497848 20.12.2010 (+len model SSE)

(1-969626/996740)*100 = 2.72026807392098
(1-12020481/12172597)*100 = 1.24965937835616
(1-24497848/24560059)*100 = 0.25330150876266

For now I replaced the submodels for literals and ids,
and that's what I've got (with SFC tuning).
However, the important point is that all these streams
were produced with parsing optimization for original lzma codes.

Actually I'm not aiming for recompression, just trying to
design a LZ method with better compression than lzma,
and recompression is accidentally a reliable way to do that

> Have you tried similar things on zLib streams?
> You'd get much better compression there.

Certainly, because of rc vs huffman (while lzma already uses
the same rangecoder and counters which I do).
But deflate also has a very small window, so its recompression
can't be that simple.

> The downside is it only sees the raw codes, not the decompressed data, right?

No. In fact, its impossible to decode the lzma literals without having full decoded data,
because of literal masking after matches.

> But f.e. Precomp recognizes a PDF stream inside the decompressed XZ
> stream which can be optimized:

I just got an idea about this. What about _partial_ recompression?
ie you decode the lzma stream, find the PDF in it, and recompress
only the part of lzma stream which contains the PDF?

P.S. Any comments about dllmerge?

[schnaader]

But dumping them and "compressing with different algorithms" (ie external compressors)
doesn't really work at all (except for literals) - only paq8 handles numbers better
than unaligned sequences of bytes, and even paq8 is pretty bad at it.

I see, I was a bit enthusiastic because the literal stream in enwik was compressed so much better by PAQ, but I realized later that this is one of the smallest parts, so compressing only literals better doesn't help much.

Certainly, because of rc vs huffman (while lzma already uses
the same rangecoder and counters which I do).
But deflate also has a very small window, so its recompression
can't be that simple.

Why does a small window complicate the recompression? I'd rather expect better recompression as there are more literals. Seems I'm still missing something about this concept.

> The downside is it only sees the raw codes, not the decompressed data, right?

No. In fact, its impossible to decode the lzma literals without having full decoded data,
because of literal masking after matches.

OK, my fault. I meant the downside to be you can't modify and output the decoded data directly (which would give you the possibility for more optimizations), but have to modify and output the LZMA code streams instead.

> But f.e. Precomp recognizes a PDF stream inside the decompressed XZ
> stream which can be optimized:

I just got an idea about this. What about _partial_ recompression?
ie you decode the lzma stream, find the PDF in it, and recompress
only the part of lzma stream which contains the PDF?

Good idea, I'll have a look at this. For zLib streams, this makes no sense as we get better compression anyway, but it'd make sense for LZMA streams - speeds up the process and makes sure we get better compression even if we use an compression worse than LZMA.

P.S. Any comments about dllmerge?

I tested the executable from your demo a bit and it seems to work for me. Guess I'll provide the merged executable as an alternative version and if there are no problems with it, completely switch to it on the next release.

[Shelwien]

> I see, I was a bit enthusiastic because the literal stream in enwik
> was compressed so much better by PAQ,

That's actually because lzma leaves whole words as literals sometimes,
ie CM is still helpful for the literal stream.
But occasionally even paq8 can lose on lzma's literals, because lzma
can mask them.

> but I realized later that this is one of the smallest parts, so
> compressing only literals better doesn't help much.

I still have some hope for distances though - distances >128 are
stored mostly uncompressed by lzma (except for 4 low bits and 1 msb).

> Why does a small window complicate the recompression? I'd rather
> expect better recompression as there are more literals. Seems I'm
> still missing something about this concept.

I mean, if I'd just recompress the deflate's raw codes (even with
some reasonable data contexts, like order2), I'd still lose to, for example,
precomp+lzma, because long-distance matches would be hard to find.

So in deflate case, it would be necessary to simulate its match finder
and use its output as context for deflate codes (i mean the symmetric
recompression, the one able to handle any deflate streams, not only
zlib ones).

And in lzma case, same approach would be in theory helpful too, but it'd be
awfully hard to implement - first we'd need a codec which always provides
better compression than lzma (and texts aside, its pretty troublesome),
and then a "simulator" for lzma's optimal parsing... %)

> OK, my fault. I meant the downside to be you can't modify and output
> the decoded data directly (which would give you the possibility for
> more optimizations), but have to modify and output the LZMA code
> streams instead.

I can decode the data, but can't encode it better than lzma does.
Well, I can with CM, but it doesn't fit the spec in my case, so
for now i'm working on entropy side, while letting lzma do the parsing.

> it'd make sense for LZMA streams - speeds up the process and makes sure we get better compression

Yeah - I guess you can just skip literals in such parts (take them
from uncompressed part for decoding), but leave the matches as is
(redundant, but too much trouble to reproduce).

[Sebastian]

Sorry for the ot but I thought you find LZ77 quite boring
An improvement for literal encoding could be sparse contexts and disabled offset masking for offsets <= 4

p=mix(p0,p1), where p1=mix(mix(mix(p1b,p1c),p1d),p1a) and p1a=data[-1] and so on
p=mix(p,p2)
this gave me 48k on geo

Distance coding could be improved if you try to estimate the distribution better
Instead of mapping fixed distance->bucket you can adaptively optimize the mapping in the sense of conditional entropy, same applies to sse.

[Shelwien]

This is lzma literal dump for SFC files: http://nishi.dreamhosters.com/v/lit.rar
My current result for that is 6646806, with 3 counters and 2 logistic mixers.
If you can compress it better without complicating things too much, I sure would like to know how
(o2+ models are not a good idea though)

[schnaader]

Have you already tried to fill the match gaps with 0 bytes or something else (assuming you can skip them later as you know the match lengths)? This might help algorithms by not destroying too much structures in the data. Although I guess this won't save much in most cases and you'll end up with worse compression, it's worth a try.

[Shelwien]

I'd probably have to do just that when I'd try to reimplement bsdiff later.
But for now it would defeat the whole point of using LZ - I'd just use CM if I could,
but I don't know how to make a CM with decoding speed comparable to lzma and better compression.

[Sebastian]

This is lzma literal dump for SFC files

This is no use for me, since context structure is destroyed in pure literal dump.

but I don't know how to make a CM with decoding speed comparable to lzma and better compression.

Make it compilicated now, and wait a few cpu-generations...

happy Xmas

[SvenBent]

ohh nice beeen waiting for this. two remark though

1: bzip2 compression as default is kinda uninterested. can't we make non compression as default and bzip2 with a command switch ? that way we break less batch file compatibility to
2:ECM filter into precomp ? it would be nice to to reduce my amount of tools to prefilter a file. mostly to avoid alot of the I/O and thereby decompressions file decompression time

[Shelwien]

@Sebastian:

> This is no use for me, since context structure is destroyed in pure literal dump.

 7776119 = uncompressed 
 7010534 = ppmonstr -o2
 6924774 = mix_test 09g2
 6798849 = paq8p -6
 6793047 = paq8px69 -6
 6670767 = 14h result for literals (+ rc flush)

I still think it makes sense to test even with lost context - if there really
are strong sparse-context dependencies, it would at least do better than mix_test.

> Make it compilicated now, and wait a few cpu-generations...

Amounts of data grow faster than cpu speeds, and the new trend for parallel computing
doesn't help at all.

> happy Xmas

Same to you

[Bulat Ziganshin]

with new freearc version fully supporting stdin-to-stdout decompression in unarc.dll, we are eagerly need this mode in precomp decompression stage. can you do it?

it will allow to perform usual precomp+srep+lzma decompression w/o trashing HDD with tempfiles

[Skymmer]

With a huge delay I've finally tested the PreComp v0.4.1 Thanks for release, schnaader !

First of all its interesting to see how the new version will deal with some previous issues reported by me. So lets check...

1.) Do you remember the issue I reported here ? I just ran both 0.4.1 and 0.4.0 versions on that file (mp_crash_snow.ff) and both versions work correctly. So I'm completely confused and cannot explain this. Why previously the 0.4.0 version wasn't able to process that file ? And you also confirmed the issue in your reply in that thread. Do you have that file provided by me? Maybe I have uploaded the wrong file in that case... ??? I'm pretty sure that not... But lets dig it.

2.) The problem with Ubuntu image reported here.
Now it works fine.

3.) The issue reported at this message.
Now it works fine.

4.) JPEG detection issue reported here.
Still no luck.

I'm also have a quite nasty additional report. A friend of mine provided me a pair of files which are normaly processed with 0.4.1 version. And precomp -r gives no error. But the output files are different to original in size and content.
So, if you're interested, I can provide you with any additional info and details. Hope it will help.

Anyway, thank you for your efforts and good work.

[lunaris]

Shelwien and schaader

Are there plans to implement a recompressor/precompressor for djvu files??

[Shelwien]

>> djvu files

No, why? Even ogg is more reasonable than that.
However I can provide a simple CM backend in exchange for a lossless dumper, like mp3dump.

[schnaader]

General note:

I'll start with experimental/unstable Precomp branches soon, to make the development process and exchange with users/testers more flexible without putting the stability of the official release version at risk. So when I'm talking about "experimental switches", this means there will be switches added in the unstable branch people can try and test for errors and those will find their way to the stable version when working.

with new freearc version fully supporting stdin-to-stdout decompression in unarc.dll, we are eagerly need this mode in precomp decompression stage. can you do it?

it will allow to perform usual precomp+srep+lzma decompression w/o trashing HDD with tempfiles

As I'm not quite sure if we're talking about the same stage when you say "decompression stage", let me elaborate this a bit: The stage "file->PCF" involves much seeking in the input file for certain streams, f.e. when processing PNG files with multiple chunks or in -pdfbmp mode. That will not change in one of the next minor releases because the best way to make this stdin/out-compatible is a major rewrite. Also, this stage uses tempfiles very often and so we're trashing HDD anyway until usage of tempfiles is removed.

The other stage, "PCF->file", however, avoids tempfiles (with some exceptions like JPG streams) and only does some seeking f.e. when processing penalty bytes that would need to be changed. So this is where I can try to add a stdin-to-stdout mode and where changes for success are good. I'll try to add that as an experimental switch.

First of all its interesting to see how the new version will deal with some previous issues reported by me. So lets check...

1.) I still have the file you uploaded and can reproduce the behaviour with both Precomp 0.4.1 and 0.4 (only 1/206 recompressed streams in slow mode). Note there was no crash, only zLib streams that couldn't be processed because they aren't complete or something similar. I'll have a look at that again, maybe adding an experimental switch that ignores zlib errors and tries to recompress anyway. The file is mp_crash_snow.ff, 36.546.380 bytes, md5sum 1aa281e5ded0349b64cc90dd6d27183b. I can reupload it somewhere if you want.

2.) This was one of the various crashes caused by using zLib code instead of the DLL in Precomp 0.4.

3.) Could be the same as 2.), but I also made some changes in the GIF code, f.e. partial matches are supported and some various small bugs were fixed in this process.

4.) JPEG streams and their detection still are a problem and I'm not sure when/how to fix this. When Matthias released the PackJPG Development tools, I thought I might use these to improve JPEG detection and resolve some of the JPEG crashes, but they also occur when using the devtools (as you can also see in the rejpeg thread where I posted an example JPG) - so I'm thinking about disabling packJPG by default until these issues are fixed.

I'm also have a quite nasty additional report. A friend of mine provided me a pair of files which are normaly processed with 0.4.1 version. And precomp -r gives no error. But the output files are different to original in size and content.
So, if you're interested, I can provide you with any additional info and details. Hope it will help.

Yes, I'm highly interested in these kind of errors (incorrect recompression). There were similar errors in the PNG code with 0.4 which are fixed now, but it shows that although the processes are relatively safe as identical recompression is checked at various stages, there can still be errors occuring. So if you can, please send me the files and I'll have a look at it.

Shelwien and schnaader

Are there plans to implement a recompressor/precompressor for djvu files??

No, AFAIK djvu files are using their very own ways of improving compression ratio for documents, so it would be much effort to implement this and only djvu files, which aren't that popular f.e. compared to PDF, could be improved. Additionally, last time I had a look at djvu documents, it seems that compression ratio was very good and so I doubt recompression can improve it that much or at all.

[Shelwien]

> djvu files

[...] a fast binary adaptive
quasi-arithmetic coder named ZP-Coder. Because of its speed and
convenience, the ZP-Coder is used in several parts of the DjVu reference
library (See BSByteStream.h, JB2Image.h, IW44Image.h ).

That thing is a 16-bit state-machine arithmetic coder, like all these other patented arithmetics.
Its not impressive at all, so I'd expect at least 10% recompression gain with a proper modern model.
But its a huge amount of work, because we'd have to rewrite the format parser from scratch
(to remove its own entropy coding), and libdjvu is ~2.5M of C++ source.

Its likely much simpler to make a new format for that task, with better compression.

[Skymmer]

1.) I still have the file you uploaded and can reproduce the behaviour with both Precomp 0.4.1 and 0.4 ..... I can reupload it somewhere if you want.

Yes, it would be nice. My current mp_crash_snow.ff is 43 864 387 bytes and this is definitely strange.

Yes, I'm highly interested in these kind of errors (incorrect recompression) ..... So if you can, please send me the files and I'll have a look at it.

Sure. The files are available here:
http://www.sendspace.com/file/3sf285
http://www.sendspace.com/file/2q35n5
The error appears while processing with -slow -c-

[schnaader]

Yes, it would be nice. My current mp_crash_snow.ff is 43 864 387 bytes and this is definitely strange.

http://www.sendspace.com/file/if5nle

Sure. The files are available here:
http://www.sendspace.com/file/3sf285
http://www.sendspace.com/file/2q35n5
The error appears while processing with -slow -c-

Thanks, I'll have a look at them.

[Bulat Ziganshin]

As I'm not quite sure if we're talking about the same stage when you say "decompression stage"

i mean pcf->file stage

[Mushoz]

General note:

I'll start with experimental/unstable Precomp branches soon, to make the development process and exchange with users/testers more flexible without putting the stability of the official release version at risk. So when I'm talking about "experimental switches", this means there will be switches added in the unstable branch people can try and test for errors and those will find their way to the stable version when working.

Wooohooo! Looking forward to new features in IMO one of the most innovative data compression program of the world! Great job!

[Shelwien]

I've got some interesting results with precomp and zip archives created by various programs:

                                       zip+slow raw+brute
book1__7z.zip   299877  book1__7z.pcf   299907  301343
book1__izip.zip 312506  book1__izip.pcf 769062  768905
book1__jar.zip  313710  book1__jar.pcf  768946  768907
book1__kzip.zip 299547  book1__kzip.pcf 299579  299985
book1__pacl.zip 312912  book1__pacl.pcf 350801  351266
book1__pk.zip   312600  book1__pk.pcf   312630  313361
book1__pks.zip  311357  book1__pks.pcf  311388  312404
book1__wz.zip   312157  book1__wz.pcf   312187  313431
wcc386_7z.zip   303186  wcc386_7z.pcf   303216  304942
wcc386_izip.zip 315201  wcc386_izip.pcf 315233  316982
wcc386_jar.zip  314314  wcc386_jar.pcf  536799  536760
wcc386_kzip.zip 302690  wcc386_kzip.pcf 302722  303077
wcc386_pacl.zip 314144  wcc386_pacl.pcf 328233  329319
wcc386_pk.zip   313405  wcc386_pk.pcf   313435  314689
wcc386_pks.zip  312927  wcc386_pks.pcf  312958  313292
wcc386_wz.zip   315024  wcc386_wz.pcf   315054  317798

_7z      7z a -tzip -mx=9
_izip    zip -9 (infozip)
_jar     jar.exe cvfM
_kzip    kzip
_pacl    PA console -c19
_pk      pkzip/DOS 2.04e -ex
_pks     securezip 12 -ex
_wz      winzip console -ex

768xxx .pcf size for book1 and 536xxx for wcc386 mean successful recompression,
pcf_size ~= zip_size+30 means no recompression,
pcf_size-zip_size>1000 likely means misdetection.
I wonder about pacl case though, it looks like one real block got recompressed.

Obviously, this doesn't include any deflate64 or pkware DCL samples.
Question: what would be the recompression gain if it actually worked for all deflate streams?