LZO support

[Erik Garrison]

On Tue, Jul 15, 2008 at 07:06:53PM +0200, NoiseEHC wrote:
>
>>> Also for speed testing this script seems totally unusable, I would send
>>> my c program but it does not contain ZLIB.
>>>     
>>
>> Do you mean that running the tests inside a python script is bad for
>> speed testing?
>>   
> No, the problem is that you do not know what amount of processing is  
> happening because of reading and piping files, or if the  
> compressors/decompressors are not written in a brain damaged way, or if  
> the extra processing trashes caches and so on. If you think that  
> zpipe/lzop are fine then it is usable as a speed test. You also has to  
> use the minimum time, not the average, if you have multiple runs.

I understand.

For the amount of time I can give to this I'm going to accept that
zpipe/lzop are fine.

The one major change which I can implement is taking the minimum
decompression time instead of the average.  I have updated the test
script to do so.  I'm not observing a significant change in the results.

>>   
>>> Also there is a problem that the LZO included in the kernel is a
>>> modified version of minilzo (x1 LZO algorithm) and the default
>>> compressor does not generate all the possible codes during compression.
>>>     
>>
>> Where could I read more about this?
>>
>>   
> Nowhere. Currently the only documentation of the LZO file format is  
> written by me (attached). There is a file "lzo1.c" in the original LZO  
> library which describes a hypothetical, non existing format,  
> unfortunately the 1x_1 format which is in "minilzo.c" which was  
> kernelized is undocumented spaghetti code...
>

Could you venture a guess at how much time would be required to solve
this, or at least how large the changes to the kernel's codebase would
have to be?

> These ones are not used:
> ; short match???, can only happen after a normal literal
> 0000mmll  mmmmmmmm                       match op-0x801-m,3 ; literal ll
> ; match type <= 15 (m < 0x400) (op-0x400..op-1)
> 0000mmll  mmmmmmmm                       match op-1-m,2 ; literal ll
>

> ...,...0  ...,...1  ...,...2  ...,...3
> ; normal literal, not followed with a short literal (literal ll)
> 0000tttt                                 literal t+3 (3..18)
> 00000000  TTTTTTTT+                      literal 15+T+3 (19..)
> ; short match???, can only happen after a normal literal
> 0000mmll  mmmmmmmm                       match op-0x801-m,3 ; literal ll
> ; match type >= 64 (t >= 2) (m < 0x800) (op-0x800..op-1)
> tttmmmll  mmmmmmmm                       match op-1-m,t-1+2 ; literal ll
> ; match type >= 32 (m < 0x4000) (op-0x4000..op-1)
> 001ttttt  mmmmmmll  mmmmmmmm             match op-1-m,t+2 (3..33) ; literal ll
> 00100000  TTTTTTTT+ mmmmmmll  mmmmmmmm   match op-1-m,31+T+2 (34..) ; literal ll
> ; match type >= 16 (m < 0x8000) (op-0xbfff..op-0x4001)
> 00010xxx  000000yy  00000000             eof (where xxx != 000)
> 0001mttt  mmmmmmll  mmmmmmmm             match op-m-0x4000,t+2 (3..9) (where m != 0) ; literal ll
> 0001m000  TTTTTTTT+ mmmmmmll  mmmmmmmm   match op-m-0x4000,7+T+2 (10..) (where m != 0) ; literal ll
> ; match type <= 15 (m < 0x400) (op-0x400..op-1)
> 0000mmll  mmmmmmmm                       match op-1-m,2 ; literal ll