Ultra-fast LZ

[m^2]

I can't help you with Windows, but maybe others can.
Here you have a ZFS source tour:
http://hub.opensolaris.org/bin/view/...oup+zfs/source

You may be also interested in a LZO patch:
http://www.wizy.org/wiki/ZFS_on_FUSE#LZO_Compression

[Cyan]

Thanks, the LZO patch is a good starting point

Regards

[Black_Fox]

NTFS-3g is able to read and write transparently compressed files, so that could be some starting point in Windows FS-built-in compression.

[Cyan]

Good point Black_Fox; sounds good,

but where should the code be inserted ?
Probably a driver model i guess; where to find such information ...

[Black_Fox]

ReactOS is far away from this yet and other projects AFAIK don't have the need to make any drop-in replacements, I don't know. Some very basic info about the compression is here: http://msdn.microsoft.com/en-us/library/Aa364219
I think Encode did performance tests against NTFS LZ some time ago, but he most likely did not plug his code into NTFS.

[jethro]

This, if done right, could seriously speed up file transfers. SSD speeds with good old GMR technology (for compressable files ofc)? Me want!

[encode]

2 Shelwien
What do you think, what kind of bit codes are most efficient for match length/offset coding? (128...256 KB window)

[encode]

Most likely, for match length
000
001
010
...
111 00000000
111 00000001
etc.
Is better than
1
01
001
000
...
or
1 xx
01 xxxx
00 xxxxxxxx
and such codes

[Shelwien]

Dump the symbols (lengths or whatever) to a file and process it with http://encode.su/threads/1183-Huffman-code-generator
(it can be also easily modified to work with alphabet size >256)
Then you can reorder the codes however you like, but huffman code lengths are the most efficient, there's a mathematical proof of that.

[encode]

Current results on ENWIK8:

Fast -> 43303422
Normal -> 37321031
Max -> 36596773

Still no Huffman or arithmetic coding, just Bit I/O. And it is FAST!

[m^2]

Dictionary?

[encode]

128 KB

[m^2]

Well well, stronger than LZSS with such a small window? Nice.

[encode]

New performance and comparison of a DEBUG build - i.e. it's unoptimized. With release build I'm expecting the decompression times to be much closer to ULZ 0.02!

No code has to be inserted here.

A quick note. New ULZ has the smallest dictionary of all my programs:
ULZ 0.03 - 128 KB
LZSS - 256 KB
ULZ 0.02 - 512 KB

It compresses better due to:
+ Better LZ-output encoding - variable bit codes VS byte aligned ones
+ Optimized parsing

And the huge difference can be seen on binary files:

MPTRACK.EXE (1,159,172 bytes)
ULZ 0.03a, cx -> 595,631 bytes
LZSS 0.01, ex -> 651,281 bytes
ULZ 0.02, c6 -> 657,110 bytes

So, compared to Deflate, we've got about the same compression level with notable faster decompression...

[encode]

Interesting thing. The longest offsets are the most frequently used ones. At least with ENWIK8. Since the longest match that can be found is usually distant. Hence the common LZH logic is not essentially correct. At the same time short offsets should not be too redundant...

[encode]

New results:

ENWIK8
128K -> 36,107,259 bytes
256K -> 35,306,349 bytes
512K -> 34,643,338 bytes

ENWIK9
128K -> 320,750,811 bytes
256K -> 312,955,293 bytes
512K -> 306,579,737 bytes

world95.txt
128K -> 808,018 bytes
256K -> 768,213 bytes
512K -> 737,721 bytes

OSHO.TXT
128K -> 60,806,644 bytes
256K -> 59,035,580 bytes
512K -> 57,658,231 bytes

bookstar
128K -> 14,597,144 bytes
256K -> 14,138,705 bytes
512K -> 13,760,371 bytes

3200.txt
128K -> 6,130,489 bytes
256K -> 5,963,436 bytes
512K -> 5,841,495 bytes



256K looking good!

[encode]

Got a nice results with a Fast mode and a New Match Finder:
ENWIK8 -> 39,385,478 bytes in about one second!

[encode]

New results (timings are for a DEBUG build):

No code has to be inserted here.

Any comments / suggestions?

[m^2]

Could you give us decompression times? It looks that 1MB sucks, but I'd like to see how does is affect decompression.
And why DEBUG?

[encode]

'DEBUG' is because of a dummy Visual C++ compile. Currently, I'm just concentrating on the actual implementation. I will do some experiments with compilers and their options later.

Okay, here are the results for a slightly improved version:

512K
Compressing...
100000000 -> 34390122 in 16.6 sec
Decompressing...
34390122 -> 100000000 in 0.5 sec
Compressing...
1000000000 -> 304633215 in 146.8 sec
Decompressing...
304633215 -> 1000000000 in 4.2 sec

1M
Compressing...
100000000 -> 33576587 in 35.2 sec
Decompressing...
33576587 -> 100000000 in 0.5 sec
Compressing...
1000000000 -> 296783310 in 284.5 sec
Decompressing...
296783310 -> 1000000000 in 4.1 sec

The decompression with 1 MB is actually faster. The the goal of this software is the FASTEST decompression possible. To be on par with QuickLZ, LZOP or SNAPPY - my LZ77 decoder has the same complexity as the fastest codecs on the planet. At the same time new LZ77 has the COMPRESSION!

[jethro]

New results (timings are for a DEBUG build):

No code has to be inserted here.

Any comments / suggestions?

I like 1MB fast best. Slower modes are not really worth it

[encode]

I like 1MB fast best. Slower modes are not really worth it

Actually worth it. Since the decompression speed is not affected.

[jethro]

Interesting, then those modes are definitely worth keeping.
Have you thought then about support drag&drop aka paq style (compression and decompression) to go with super-fast speed?

[encode]

Such user interface can be added in one minute. Just currently in my mind the algorithm only. It is mainly done, but I need to carefully choose the algorithm parameters. Such as window size.

[encode]

Added a nice feature. Now you can concatenate compressed streams. Say, you compressed:
book1 to book1.cru
book2 to book2.cru
book3 to book3.cru

now if you will concatenate all files:

copy /b book1.cru+book2.cru+book3.cru books.cru

new lz77 compressor will able to decompress that "books.cru" into one file that will be just like all uncompressed files concatenated together.

[Matt Mahoney]

That's a nice feature. zpaq does that too, also bzip2 I think.

[encode]

I'm close to release a new LZ77 encoder called CRUSH. It has 512 KB dictionary. The compression power is favored over compression speed. Although Fast mode is pretty fast, in Normal and Max mode I specially kept a slower match finder that will able to find more matches thus providing a higher compression. The decompression is just extremely fast at any compression mode!

More detailed description of compression modes:

• Fast - Fast string searching. Greedy parsing.
• Normal - Best string searching. Greedy parsing.
• Max - Best string searching. Advanced lazy matching with 1-byte lookahead. I tested lazy matching with 2-byte lookahead and it's not the best idea here, since the literals are sent unencoded, and generally speaking sending extra literals is a bad idea.

Actually, CRUSH in Normal mode is somewhat similar to ULZ at Max mode. The main difference is that CRUSH uses variable length bit codes (not Huffman).

Can it replace Deflate? Probably. Currently, CRUSH has a slower compression (Normal and Max modes), the Fast mode is much faster than Deflate, providing yet a nice compression. The main key is an extremely fast decompression. The decoder is extremely simple and can fit in a few lines of code. Usually, CRUSH has a notable higher compression than Deflate. Anyway, in some cases and due to fact that CRUSH does not encode literals sending them unencoded, Deflate may outperform CRUSH in terms of compression, especially on poor compressible files. Furthermore, currently, CRUSH may increase size of already compressed files like A10.jpg. Anyway, since CRUSH processes blocks independently, I will add a support for unencoded blocks. At least I will do so for the decoder. Unlike nearly all my compressors, I will keep a backward compatibility in CRUSH - i.e. whatever I do with the encoder, I'll keep decoder untouched. As example I may reserve an extra features in he decoder, that may not be available currently in the encoder (like unencoded blocks)...

So anyways, results on ENWIKs:

ENWIK8 -> 33,849,317 bytes
ENWIK9 -> 299,705,455 bytes

Yet better than SLUG and others, providing unmatched decompression speed...

[encode]

OK, continue talking to myself. After some experiments I did some changes:

Increased dictionary size to 1 MB. It's make sense.

Now Max mode is more like an Extreme mode - really exhaustive string searching in pair with more optimized parsing. Normal mode is just the most balanced in terms of compression ratio vs compression time. Fast mode is really something interesting - it's fast and compression is good enough.

Changed the memory usage - increased buffer from 32 MB to 64 MB and increased hash sizes from 20-bit hashes to 24-bit hashes.
Now CRUSH needs about 192 MB for compression, and, 64 MB for decompression. (Previously CRUSH use 40 MB for compression and 32 for decompression)

Interesting thing, new CRUSH compresses ENWIK9 better than some arith(+rolz) based coders like irolz...

[encode]

ENWIK8 -> 32,988,847 bytes
ENWIK9 -> 291,350,973 bytes

Any comments?

[m^2]

OK, continue talking to myself

We're listening, we just have nothing to comment.

ENWIK8 -> 32,988,847 bytes
ENWIK9 -> 291,350,973 bytes

Any comments?

But if you ask:
Looks good.