Fast UZ compressor, drop-in replacement UCC.exe for compress/decompress unreal .uz files

[Buggie]

Fast UZ compressor, drop-in replacement UCC.exe for compress/decompress unreal .uz files

Code: Select all

Usage:
    uz compress files_for_compress [newformat] [update]
    uz decompress files_for_decompress

    newformat       Applies run-length encoding to the compressed files. This increases the compression rate.
    update          Only compress if the uz file does not exist, or if it is older than the corresponding source file.

This tool produce fully compatible .uz file. No need ucc.exe.

Compressed faster in ~5 times.

https://github.com/SeriousBuggie/UZ

Download: https://github.com/SeriousBuggie/UZ/releases/latest

outdated use github instead

Or here:

UZ.zip

[OjitroC]

The core.dll file included in the zip appears to be the one that comes with UT v436 - does that mean that uz.exe only works with that version and not with v451b for example?

Is the decompression with uz.exe faster than with UCC.exe?

[Buggie]

Core.dll from v436. But this does not matter. .uz format is same across all UT versions.
Just store UZ.exe in separate folder with own Core.dll. Do not copy in System.

With other Core.dll it may work or not. Possible not.

Decompression speed is same. Difference can be only because same code compiled not with VC++ 6.0, but with VS2010.
But this does not matter because decompression always fast. Even via UCC.

For example MH-Battle4NaZaliBeta2.unr compressed in 93 seconds via UZ and 492 seconds via UCC.
Both file is same and decompressed near 2.5 seconds.

------
Compared:

Code: Select all

ucc compress ..\Maps\MH-EscapeFromNaZaliBeta2.unr
Compressing ..\Maps\MH-EscapeFromNaZaliBeta2.unr (72873863 bytes)
stage 0: 2.386206 secs
stage 1: 8357.626953 secs
stage 2: 0.823047 secs
stage 3: 1.207998 secs
Total: 8362.044204 secs
Compressed ..\Maps\MH-EscapeFromNaZaliBeta2.unr -> ..\Maps\MH-EscapeFromNaZaliBeta2.unr.uz (6%)

and

Code: Select all

uz compress MH-EscapeFromNaZaliBeta2.unr
Compressing MH-EscapeFromNaZaliBeta2.unr (72873863 bytes)
stage 0: 3.182000 secs
stage 1: 1489.685059 secs
stage 2: 0.811000 secs
stage 3: 1.186000 secs
Total: 1494.864136 secs
Compressed MH-EscapeFromNaZaliBeta2.unr -> MH-EscapeFromNaZaliBeta2.unr.uz (6%)

in 5.6 times faster.

[sektor2111]

Now this is truly an useful thing. It works and... indeed it's faster. UZ compressed file is similar to original (identical more exactly) but compressing task won't take hours, building a redirect goes faster. Nice job, man.
Indeed... it doesn't work with certain Core.dll, but that's no big deal. All processing can be loaded in a batch and pointed to another folder for execution, I've made a folder and I will adjust my UZ batch command for this new compressor.

[Buggie]

I report about this optimization for include in v469. Maybe compress via UCC in v469 will be too fast.

[Higor]

@anth
If you merge this, don't forget that the codecs should reside in Core.dll as exportables.

[Buggie]

I do not understand this note.
FCodec.h is public header. You can just edit CodecBWT class.
After make final release of v469 publish public headers of it.
For what need "that the codecs should reside in Core.dll as exportables."?

[Feralidragon]

This looks indeed very interesting, so I just tried it out on something that the current UCC is unable to deal with for compression, namely this map:
viewtopic.php?f=5&t=13704

And it turns out that your new UZ has the same exact problem as the UCC shipped with the game: it finishes stage 0 without any issues, but it hangs on stage 1 and never finishes the compression.

For a bit more context: I finished this map a while ago mostly as a benchmark for UT99, in an attempt to push the engine to its limits.
It was already used as a benchmark to solve some serious issues and limitations in 469, including some major fixes and improvements in the editor itself as well.

The fact that apparently this map cannot be compressed by the current UCC version is one other issue this map has with the current UT version which hasn't been solved yet in 469, so if you manage to find out why it happens and fix it in your new compressor, that would be another awesome fix to potentially have in 469.

[Buggie]

Worst case for qsort make it O(n*n). So if you make this, then it will take very long time compress. I try look in detail.
-----
Problem not in sorting function.
Problem in comparator.
Strictly speaking, problem in input data.
There present huge blocks of same size.
Which produce big time by many calls memcmp (which very effective inline assembly, but even this not help, when booth blocks is huge and near same content).
memcmp called ~5 500 000 times for each sort call.
If memcmp take long time it can slow down to 16 ms.
This happens not for all cases, but if its count big enough, compression speed goes to hell.
Let's imagine all calls take 16 ms. One call of sort take near 24 hours.

If file contains A big count of same byte sequence then it can be compressed very efficiently. Look at your zip. 87 MB .unr compressed to 11 MB. It is sounds bad.

Obviously BWT (in such implementation) not good thing for compress files. And later, UE use gzip for this.
But we stuck on this because of compatibility things.
-----
https://www.sendspace.com/file/ws43oi 17 MB CTF-Blice-Alpha.unr.uz
4600 seconds on slow debug version. Maybe release UZ from first post make it in 1 hour.
-----
For this map longest sort call is 59 seconds.
-----
As I found this block equals not because filled with one same byte. The equals because filled with repeatable pattern. So I do not see any possible optimization here.
-----
New version 1.1:

Fix bugs.
Add progress counter.

https://github.com/SeriousBuggie/UZ/releases/latest
-------

Code: Select all

uz compress CTF-Blice-Alpha.unr
Compressing CTF-Blice-Alpha.unr (87328898 bytes)
stage 0: 4.321000 secs
stage 1: 4396.403809 secs
stage 2: 2.808000 secs
stage 3: 3.697000 secs
Total: 4407.229492 secs
Compressed CTF-Blice-Alpha.unr -> CTF-Blice-Alpha.unr.uz (20%)

-----
New version 1.2:

Fix crashes at end run.

https://github.com/SeriousBuggie/UZ/releases/latest

[Buggie]

New version 1.3

Fix crashes.
Speed up compression (in some cases in 70 times), but compression is slightly worse (usually 1-2%).

https://github.com/SeriousBuggie/UZ/releases/latest

Code: Select all

uz compress CTF-Blice-Alpha.unr
Compressing CTF-Blice-Alpha.unr (87328898 bytes)
stage 0: 4.259000 secs
stage 1: 52.276001 secs
stage 2: 2.870000 secs
stage 3: 3.900000 secs
Total: 63.305000 secs
Compressed CTF-Blice-Alpha.unr -> CTF-Blice-Alpha.unr.uz (22%)

uz decompress

Code: Select all

uz decompress CTF-Blice-Alpha.unr.uz
stage 0: 2.449000 secs
stage 1: 2.059000 secs
stage 2: 1.170000 secs
stage 3: 3.229000 secs
Total: 8.907000 secs
Decompressed CTF-Blice-Alpha.unr.uz -> CTF-Blice-Alpha.unr

---------------------------
Comparing file contents
---------------------------
These files are the same:

CTF-Blice-Alpha.unr

CTF-Blice-Alpha_orig.unr
---------------------------
ОК
---------------------------

ucc v436 decompress

Code: Select all

ucc decompress CTF-Blice-Alpha.unr.uz
stage 0: 2.812871 secs
stage 1: 2.998637 secs
stage 2: 1.126525 secs
stage 3: 3.886633 secs
Total: 10.824666 secs
Decompressed CTF-Blice-Alpha.unr.uz -> CTF-Blice-Alpha.unr

---------------------------
Comparing file contents
---------------------------
These files are the same:

CTF-Blice-Alpha.unr

CTF-Blice-Alpha_orig.unr
---------------------------
ОК
---------------------------

[Feralidragon]

Nice!

I had a feeling that the problem was something along those lines, although whenever it hanged it didn't really consume any CPU though so it didn't seem to be an algorithm issue at first (concerning time complexity).

Just tried out the latest version, and it does work, and is indeed quite fast now.
Thank you for your great contribution!

This should now indeed maybe be included in 469 in some way.

[Buggie]

Single thread. So you not notice CPU load because multi-core CPU. One core loaded fully but total load still low.

[Feralidragon]

Yes, I know it's single-threaded, but whenever it hanged before the used CPU by the process itself was nearly zero, so it did look like it hanged.
Even in a multi-core CPU that number isn't right, in my case it should sit around 12% of CPU at least (if one of the cores was maxed out).

When this map was first released, some people tried to compress it through UCC and some of them left it compressing for nearly 8 hours until they forcefully canceled, with no CPU usage, so it was really hanging somewhere.

As a matter of fact, I did try your 1.1 version yesterday, and the compression just hanged completed at around 14% (I left it on for about 2 hours, never increased from there).
Only your latest version (1.3) that you released today actually fixed all the issues.

[Deaod]

Reducing the buffer size is not the way to go, IMO. Instead, use a better algorithm to construct the BWT of the input: Use something like https://sites.google.com/site/yuta256/sais that is O(n) in both time and space, given n as the buffer length.

[Buggie]

If reduce buffer size is not an option for you, you can always build own version of UZ, because source code included.
Go ahead, implement sais (or whatever you want) and show result to us.

I highly doubt about any big improvement with full buffer size. In any sorting algorithm.
Full buffer size is 0x40000 (and labeled as /* Hand tuning suggests this is an ideal size */ )
It is 262144.
log2(262144!) = 3 270 678.
It is lower bound of count comparator calls.
Currently qsort called comparator near 5 600 000 times.
So if you implement ideal sorting algorithm, it can call comparator 1.75 times less.
This is absolute maximum of speed improvement with same buffer size.

But you can go ahead and test all yourself.

For me (and I think for all others) buffer size does not matter, and little (1-2%) loss in compression not a problem at all.

For example if you have .unr file of 100 MB, this is mean it can be bigger to 2 MB. But 100 MB .unr file is totally insane.
Usually maps fits to 20 MB, so 2% it is 400 KB. 400 KB worth 100% CPU load for few hours in 2020 year? Or Internet speed allow us ignore this difference?
If you use dial-up modem 56kbps in 2020 year, I have bad news for you.

Currently UZ use buffer of size 0x2000. It can be 0x4000. It can give (or not) better compression. Maybe on 1%. But increase compression time twice.
I do not think 1% worst that. So I use 0x2000 not 0x4000.

CTF map from above built in 112 seconds, not in 63. I think this difference of size is less important rather then time for compress.
1 MB vs 60 seconds of compression - what is more important in 2020 year?