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

[Robin Smidsrød]

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