[ipxe-devel] [PATCH] Replace the nrv2b compression algorithm with lzo1x

[Joshua C.]

2012/5/7 Robin Smidsrød <robin at smidsrod.no>:
> On 07.05.2012 10:39, Joshua C. wrote:
>> 2012/5/6 Joshua C. <joshuacov at googlemail.com>:
>>> 2012/5/6 Michael Brown <mbrown at fensystems.co.uk>:
>>>> On Sunday 06 May 2012 17:46:33 Joshua C. wrote:
>>>>> The UCL compression library and the nrv2b algorithm haven't been
>>>>> actively developed since 2004. Some parts of the code are incomplete
>>>>> and are set to not compile anyway. I decided to replace the nrv2b
>>>>> algorithm with the lzo (especially the lzo1x_999) because it is in a
>>>>> better shape and achieves a faster decompression speed. More info
>>>>> here: http://www.oberhumer.com/opensource/lzo/#documentation
>>>>>
>>>>> The only thing that needs to  be done is to replace the nrv2b
>>>>> decompressor with the lzo.
>>>>
>>>> Thanks for taking a look at this!
>>>>
>>>> I'm not familiar with LZO.  Do you have an estimate for the expected binary
>>>> code size of the decompressor?  (For reference, the current decompressor is
>>>> just 155 bytes.)  Decompression speed is irrelevant for iPXE; what matters is
>>>> the compression ratio, and the size of the decompressor itself.
>>>>
>>>> Michael
>>>
>>> I did some recompilation and came to the following results (everything
>>> was set to stock, compilation of bin/10ec8168.lkrn):
>>>
>>> with the nrv2b algorithm:
>>> nrv2b-decompressor: 144 bytes
>>> lzo1x-asm-decompressor: 398 bytes
>>>
>>> with the lzo1x algorithm:
>>> nrv2b-decompressor: 144 bytes
>>> lzo1x-asm-decompressor: 395 bytes
>>>
>>> For the testing I just replaced the unnrv2b.S and unnrv2b16.S files
>>> with the asminit.def and lzo1x_s1.S and adjusted the libprefix.S file.
>>> Those are the differences to the size of the lkrn image without any
>>> compressor. I'm not sure if those figures accurately represent the
>>> real size of the decompressors.
>>>
>>> However I have to admit that with the lzo1x compression my lkrn was
>>> with 3452 bytes (3455 bytes) bigger than the one with the nrv2b
>>> algorithm. This falls in line with the documentation of lzo that the
>>> algorithm takes approx 3-4KB. LZO has been developed as a successor to
>>> ucl (which includes versions of the otherwise proprietary nrv
>>> compression) with decompression speed in mind. I think maybe more
>>> testing is needed but in my opinion the lzo1x can do an overall better
>>> job than the ageing and incomplete nrv2b.
>>>
>>> --Joshua
>>
>> I did some more testing with the ipxe.iso/ipxe.lkrn/undionly.kpxe.
>> With the lzo1x_999 algorithm they are all bigger than with the nrv2b.
>> The differences range from 4KB up to 35KB which should be
>> unacceptable. However the lzo library contains other algorithms that
>> are quite similar (in code) to the nrv2b, namely the lzo1b. I'll try
>> the other packers and see if I can squeeze a better compression ratio.
>>
>
> If we're talking about re-evaluating the compression system used in
> iPXE, how about looking at LZMA(2)? It seems to offer even better
> compression than bzip2, with a decompressor size between 2-8KB. More
> information available at
> http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm
> and code available from http://www.7-zip.org/sdk.html
>
> -- Robin
> _______________________________________________
> ipxe-devel mailing list
> ipxe-devel at lists.ipxe.org
> https://lists.ipxe.org/mailman/listinfo/ipxe-devel

In the last days I did some tests with the different lzo algorithms
but couldn’t find one that can give me a better compression than the
nrv2b. Lzo is just designed for speed not for storage (compared to the
nrv).

I also looked at other alternatives like lzma/xz but couldn’t find any
that can satisfy the following conditions: minimal decompressor length
and acceptable compression ratio. Lzma/xz does offer a superior
compression ration but not for already pre-compressed data like the
one we have. The ipxe image is rarely bigger than 100KB (in my case
only the ixpe.lkrn reached ~350kb, in all other cases < 80KB). So if
we take an image of approx 65kb (minus 144bytes for the decompressor)
we barely have anything that can benefit from the more advanced
lzma/xz compression ratios. On the other hand those are much more
complex than what we currently have in place. So with a decoder length
of minimum 8KB we have about 65-8=57KB that need to be better
compressed. In other words we need a better than 13% compression ratio
on a small chunck of already pre-compressed data to beat the current
algorithm (1- 65/57=0,13). Because of the data size we cannot use
large dictionaries (potentially up to the order of gigabytes) which
are one of the strengths of the lzma algorithm (not to mention memory
requirement when decompressing). This leaves us without much choice.

That’s why I looked at different executable packers but the widely
used ones are based on the ucl library (upx especially). The ucl
library last last updated in 2004. Our version of the nrv2b algorithm
was last updated in 2002. I tried adjusting some of the parameters of
the lzo packer but since this is a mathematical algorithm I was just
tapping in the darkness and couldn’t achieve even a close match to the
nrv2b compression. My idea is to update our nrv2b algorithm from 2002
to what is in the ucl-1.03 from 2004. Looking into this code I see
that swd_best_off isn’t defined anymore. This appears again in the lzo
algorithm; that’s why I think it has something to do with finding “the
best offset” that can speed up decompression. I’ll try to remove any
code in the algorithm that’s not compiled and see if it can get worse
than what we currently have ( I hope not though). I’ll post a patch in
the following days.

--Joshua