Ultra-fast LZ

**encode** · 13th July 2017, 23:23

The brand new ULZ v0.06 is here!

It's byte-aligned LZ77 with a 16MB window (=block size). Now it looks like an LZ4 with a large window. For literal run length coding I make use of EncodeMod as described by Charles Bloom. I'm not 100% sure about the Optimal Parsing here - currently ULZ uses some ad hoc solution for hard-to-compress files - and looks like it does work!

Anyway, enjoy new release!

Some testing results (Intel Core i7-4790K @ 4.6GHz, 32GB @ 1866MHz DDR3 RAM, RAMDisk)

Code:

Z:\>ulz c9 enwik9
Compressing enwik9:
1000000000 -> 291028084 in 325.732 sec

Z:\>ulz d enwik9.ulz e9
Decompressing enwik9.ulz:
291028084 -> 1000000000 in 1.110 sec

Z:\>ulz c enwik9
Compressing enwik9:
1000000000 -> 365851618 in 30.323 sec

Z:\>ulz d enwik9.ulz e9
Decompressing enwik9.ulz:
365851618 -> 1000000000 in 1.072 sec

Z:\>ulz c1 enwik9
Compressing enwik9:
1000000000 -> 421011442 in 7.379 sec

Z:\>ulz d enwik9.ulz e9
Decompressing enwik9.ulz:
421011442 -> 1000000000 in 0.950 sec

**Matt Mahoney** · 14th July 2017, 04:47

Congrats on the world's fastest decompressor.

http://mattmahoney.net/dc/text.html

**boxerab** · 31st August 2017, 16:01

Is this compressor open source, or binary only ?

**encode** · 31st August 2017, 18:29

Originally Posted by boxerab

Is this compressor open source, or binary only ?

At this moment, it is binary only!

**encode** · 23rd March 2019, 13:39

Well, I'm about to release the ULZ as an open source (public domain) data compression library. With minimalistic and simplest interface. The library consists of ULZ.HPP - the library itself and ULZ.CPP - simple demo compressor.
The usage is as simple as that:

Code:

int comp_len=ulz->Compress(in, in_len, out, level);

I'm undecided about the compressor configuration. Currently I have:
16-bit window with rep offsets (a la LZ4 competitor)
17-bit window
18-bit window
18-bit window with 4 rep offsets
19-bit window
21-bit window with rep offsets (actual window size is limited to 2 GB)
22-bit window with rep offsets (same unlimited window as with 21-bit version)
24-bit window (ULZ v0.06 modification)

At this time I'm planning to keep the Greedy (unoptimized) parsing only, for simplicity.

**algorithm** · 23rd March 2019, 13:43

Decompressor should include out_len for buffer over run.

**encode** · 23rd March 2019, 13:59

All compressed/raw size storage is up to the user. Simply write raw_len within your stream.
and do

Code:

int out_len=ulz->Decompress(in, comp_len, out);

**algorithm** · 23rd March 2019, 14:05

out_len should be included for malicious files that during decompression produce larger file than specified in the format and thus cause buffer overrun.
should be

Code:

size_t Decompress(in, comp_len, out, out_len) or
int Decompress(in, comp_len, out, out_len)

Also see the LZ4 which has similar API.

**encode** · 23rd March 2019, 15:33

Well, or at least:

Code:

ulz->Decompress(in, comp_len, out, BLOCK_SIZE);

or

ulz->Decompress<BLOCK_SIZE>(in, comp_len, out);

**encode** · 23rd March 2019, 19:18

Added buffer overrun protection!

**encode** · 24th March 2019, 12:31

Here you go:
https://github.com/encode84/ulz

**algorithm** · 24th March 2019, 13:31

So ulz is similar to lz4 with 17 bits window ,3 bit run length 4 bits match length and larger run and match lengths encoded as variable length integers of length multiple of 7 bits.

I think for g++ you must use ftello with _FILE_OFFSET_BITS defined as 64.

**encode** · 24th March 2019, 14:09

Thanks! Added g++ support.
And yep, you are correct about the ULZ algorithm description.

**moisesmcardona** · 24th March 2019, 17:01

A recommendation, for binary files it's best to use the Release section

**Shelwien** · 25th March 2019, 03:29

7820X @ 4.5Ghz, ramdisk

Code:

5.188s  1.000s:  ulz_ic19_SSE2-O1-ipo.exe c1 enwik9 x & ulz_ic19_SSE2-O1-ipo.exe d x y        
5.219s  1.016s:  ulz_ic19_SSE2-O3-ipo-PGO.exe c1 enwik9 x & ulz_ic19_SSE2-O3-ipo-PGO.exe d x y    
5.313s  1.015s:  ulz_VS2017.exe c1 enwik9 x & ulz_VS2017.exe d x y                  
5.328s  1.015s:  ulz_clang9_k8.exe c1 enwik9 x & ulz_clang9_k8.exe d x y               
5.375s  1.015s:  ulz_ic19_SSE2-O3-ipo.exe c1 enwik9 x & ulz_ic19_SSE2-O3-ipo.exe d x y        
5.391s  1.015s:  ulz_ic19_SSE2-O3.exe c1 enwik9 x & ulz_ic19_SSE2-O3.exe d x y            
5.391s  1.032s:  ulz_gcc82_k8.exe c1 enwik9 x & ulz_gcc82_k8.exe d x y                
5.406s  1.015s:  ulz_ic19_SSE2-O2-ipo.exe c1 enwik9 x & ulz_ic19_SSE2-O2-ipo.exe d x y        
5.453s  1.032s:  ulz_gcc82_k8-lto.exe c1 enwik9 x & ulz_gcc82_k8-lto.exe d x y

**dnd** · 29th March 2019, 23:05

ULZ added into Turbobench Compression Benchmark

**FatBit** · 3rd April 2019, 15:03

Dear colleagues,

I woud like to share my results for tar file compression (tarred files from my benchmark for FileOptimizer) on "average" pc.

Best regards,

FatBit

**encode** · 7th April 2019, 00:22

Some testing results of the ULZ with Optimal Parsing + modifications:

No code has to be inserted here.

**jibz** · 14th April 2019, 23:40

Originally Posted by encode

Added buffer overrun protection!

Btw, I found a couple of places where bad input could still result in a buffer overrun, I opened a pull request with some fixes on the GitHub page.

**encode** · 15th April 2019, 01:19

Thanks a bunch! Already added these fixes to the upcoming release!
In addition, I've already added a Fast compression mode (CompressFast())
Completed the CompressOptimal() (but it will be not included in the upcoming release)
My main concern for now is the Normal mode.
Hash chains are good, but 2-byte lookahead in v1.00 is too slow.
Double hash chains / my MMC implementation failed here - too much time spent on pointer setup.
Binary tree with partial updates my main thing for experiments for now...

**encode** · 19th April 2019, 11:53

ULZ v1.01 BETA has been released:
https://github.com/encode84/ulz

+ New fast compression mode (c1, default)
+ Safer decompressor
+ Reconfigured compression levels:

1 - CompressFast(), HashTable-based match finder
2..4 - Compress(), Hash chains, Greedy parsing
5..9 - Compress(), Hash chains, Non-greedy 1-byte lookahead

**smjohn1** · 22nd April 2019, 18:39

What is the O bit?

**encode** · 22nd April 2019, 18:53

Originally Posted by smjohn1

What is the O bit?

Higher bits of an Offset (Match Distance)

**smjohn1** · 22nd April 2019, 22:12

OK, thanks.

Originally Posted by encode

Higher bits of an Offset (Match Distance)

**FatBit** · 28th April 2019, 20:22

Best regards,

FatBit

**Sportman** · 28th April 2019, 23:12

ULZ v1.01 BETA:

Input:
enwik9

Output:
460,463,054 bytes, 3.158 sec. - 0.742 sec., c1
409,136,504 bytes, 5.848 sec. - 0.757 sec., c2
393,640,476 bytes, 7.711 sec. - 0.721 sec., c3
383,318,792 bytes, 10.716 sec. - 0.719 sec., c4
363,151,876 bytes, 23.298 sec. - 0.768 sec., c5
359,939,352 bytes, 31.166 sec. - 0.766 sec., c6
358,155,488 bytes, 39.326 sec. - 0.786 sec., c7
357,230,196 bytes, 47.285 sec. - 0.763 sec., c8
356,494,682 bytes, 65.747 sec. - 0.763 sec., c9

**encode** · 28th April 2019, 23:38

@Sportman
System specs?

**Sportman** · 29th April 2019, 00:18

Originally Posted by encode

System specs?

Z370
i9-9900K at 5.3GHz (16MB cache)
32GB DDR4 4266MHz

**encode** · 29th April 2019, 01:36

Thanks! Traditionally and through the years, you have a very nice PC specs!

Thread: Ultra-fast LZ

Thread Tools

Search Thread

Display

Thanks (7):

Thanks (2):

Thanks:

Thanks (2):

Thanks (2):

Thanks (9):

Thanks:

Thanks:

Thanks (4):

Thanks:

ULZ test

Thanks:

Thanks:

Thanks (2):

Thanks (5):

ULZ timing update

Thanks:

Thanks:

Thanks:

Tags for this Thread

Posting Permissions