Pure Pascal LZ4, LZ5 and LIZ

[LemonParty]

I applied your changes and tested compression with this program:

Code: Pascal  [Select][+][-]

1.  
2. {$Mode ObjFPC}{$H+}
3. {$R *.res}
4.  
5. uses
6.   LizSimple;
7.  
8. var
9.   S: String = 'Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word ';
10.   Compressed: String;
11. begin
12.   Compressed:= LIZ(S);
13.   Writeln(Length(S), ' ', Length(Compressed));
14.   Readln;
15. end.
16.  

The output is

170 190

Isn't the algorithm should find a pattern and make the resulting string to be smaller than input?

[Tomxe]

Isn't the algorithm should find a pattern and make the resulting string to be smaller than input?

This is a very short string and Lizard's goal is no to compress efficiently but quickly. Try with something over 1 kB.

[LemonParty]

I tried with this input data:

Code: Pascal  [Select][+][-]

1. {$Mode ObjFPC}{$H+}
2. {$R *.res}
3.  
4. uses
5.   LizSimple;
6.  
7. var
8.   S: String = 'Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word Word ';
9.   Compressed: String;
10. begin
11.   S:= S + S + S + S + S + S + S + S + S + S + S + S + S + S + S + S;
12.   Compressed:= LIZ(S);
13.   Writeln(Length(S), ' ', Length(Compressed));
14.   Readln;
15. end.
16.  

The output is:

2720 64

Nice. It works. Good job.

There is possible improvement to your library. Since FPC by default support overloading of functions (and Delphi too by adding "overload" to your function) you may short names of your functions this way:

Code: Pascal  [Select][+][-]

1. LIZCompressStreams -> LIZCompress
2. LIZDecompressStreams -> LIZDecompress
3. LIZCompressFile -> LIZCompress
4. LIZDecompressFile -> LIZDecompress

According function will be selected depend on argument you pass into it.

[Tomxe]

A candidate for future work may be UPX/UCL

UPX started

[LemonParty]

I want to notice one more thing. Functions LIZ, LZ4, LZ5 under the hood creates streams. This doubles the memory needed for compression. And this may be a problem on machines with limited RAM.

The solution to this is to create LIZCompressBuffer (or whatever name you like) that compress any buffer you pass to it. And configure LIZ function to use LIZCompressBuffer.

[Tomxe]

No a bad idea, thanks!

[LemonParty]

Why bad?

I inspected your code more and found interesting things in DoCompress function(line 134 of LizSimple). There are two buffers: inBuf and outBuf. Every time your library need next chunk of data it filled this two buffers. It is two unnecessary operations, because there is call to Lizard_compress on line 165 and this function is ready for work with buffers directly without all this stream stuff (you waste cycles for copying forward and backward).

So in general for compress 1 string with current implementation you have to double the memory usage and also you should copy memory 2 times more than in best case.

[LemonParty]

Hi.

I wrote a buffer compression for your library. Look attachment. Things I done:
1. Added next two functions:

Code: Pascal  [Select][+][-]

1. function LIZCompress(const Buf; BufSize: SizeUInt; var OutBuf): SizeUInt;overload;
2. function LIZDecompress(const Buf; BufSize: SizeUInt; var OutBuf): SizeUInt;overload;

they do all work without buffers in the middle and of course no streams just direct memory to memory job.
2. I also added this 3 helpful functions:

Code: Pascal  [Select][+][-]

1. function _ReadLE32(const Buf): UInt32;inline;
2. function _ReadLE64(const Buf): UInt64;inline;
3. procedure _WriteLE32(var p; v: UInt32);inline;

they just write/read to the buffer.
3. I also added

Code: Pascal  [Select][+][-]

1. function LIZCompressMaxSize(BufSize: SizeUInt): SizeUInt;inline;

which is needed when you need to find worst possible size of compressed buffer it needed for work of _LIZ but also may be useful with LIZCompress.
4. I didn't touch original LIZ and UnLIZ, but created this functions:

Code: Pascal  [Select][+][-]

1. function _LIZ(Uncompressed: AnsiString): AnsiString;
2. function _UnLIZ(Compressed: AnsiString; UncompressedSize: SizeUInt): AnsiString;

they use LIZCompress and LIZDecompress.

There is one disadvantage: _UnLIZ require to know uncompressed size of passed data.

By the way I found one issue in your project. Since you using variable written of type Integer your functions can only handle up to ~2.1 Gb of input data. In my code there is no such problem because it uses SizeUInt.

paszlib has the same problem as your library. It has no support of raw buffers.

And I have 1 question for LIZ compression. You using the smallest possible block for compression with size 128 * 1024. Is it the designed size for this algorithm or you just pick this size by yourself?