2012/5/7 Robin Smidsrød <[email protected]>: > On 07.05.2012 10:39, Joshua C. wrote: >> 2012/5/6 Joshua C. <[email protected]>: >>> 2012/5/6 Michael Brown <[email protected]>: >>>> 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 > [email protected] > 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 _______________________________________________ ipxe-devel mailing list [email protected] https://lists.ipxe.org/mailman/listinfo/ipxe-devel
