XZ (LZMA2) decoder

XZ (LZMA2) decoder

[Lasse Collin]

(Please CC your replies to me, I'm not on the list.)

An initial version of the .xz file format decoder for Linux is now 
available at <git://ctrl.tukaani.org/xz-embedded.git>. It supports both 
stateful and single-call decoding using the LZMA2 algorithm.

Two buffers (1.2 KiB and 28 KiB) are allocated with kmalloc() for 
internal data. For stateful decoding, also a dictionary is allocated 
with vmalloc(), which probably will usually be from 64 KiB to 1 MiB. The 
dictionary is allocated when the decoder is created, so the decoder 
never allocates memory in the middle of decoding. This means that if the 
preallocated dictionary was too small for the input stream, decoding 
will fail. In single-call mode, the destination buffer is used as the 
dictionary, thus a separate dictionary doesn't need to be allocated.

On x86, xz_dec.ko is 11-14 KiB. Stack usage is around 120-240 bytes, 
depending on the GCC version and compiler flags. I hope it is not too 
much, but I can try to reduce it slightly if needed.

BCJ filters are not added yet. They will increase the code size a little 
but they should save more space by increasing compression ratio of 
executables (and naturally it will be possible to disable these filters 
in the kernel config).

There is some code (mostly in xz_boot.c), which hopefully makes it 
easier to add support for XZ compressed kernel and initramfs. I hope 
that someone else does the actual work to get XZ support in the arch-
specific trees (IIRC, there were some patches to add bzip2 and LZMA 
support already), but I'm happy to help if my code needs some 
adjustments to support that work.

I have tried to follow to the kernel coding style as well as I can, but 
if there are style issues that should be fixed, please let me know. I 
want to keep the code usable outside Linux, which why there are some 
extra #ifdefs and such. I hope this is OK.

I haven't tested the code much yet. It appears to work in userspace. The 
kernel module compiles cleanly on x86, but I haven't tested it in kernel 
space, because I currently have no code to feed data to the XZ decoder 
in the kernel space.

-- 
Lasse Collin  |  IRC: Larhzu @ IRCnet & Freenode

Re: XZ (LZMA2) decoder

[Leon Woestenberg]

Hello Lasse,

On Sun, Mar 22, 2009 at 2:57 PM, Lasse Collin <lasse.collin@tukaani.org> wrote:
> (Please CC your replies to me, I'm not on the list.)
>
> An initial version of the .xz file format decoder for Linux is now
> available at <git://ctrl.tukaani.org/xz-embedded.git>. It supports both
> stateful and single-call decoding using the LZMA2 algorithm.
>
Is this something the linux-embedded community must pick up, or maybe
even the LKML?

Regards,
-- 
Leon

Re: XZ (LZMA2) decoder

[Bernhard Reutner-Fischer]

On Wed, Mar 25, 2009 at 10:39:06PM +0100, Leon Woestenberg wrote:
>Hello Lasse,
>
>On Sun, Mar 22, 2009 at 2:57 PM, Lasse Collin <lasse.collin@tukaani.org> wrote:
>> (Please CC your replies to me, I'm not on the list.)
>>
>> An initial version of the .xz file format decoder for Linux is now
>> available at <git://ctrl.tukaani.org/xz-embedded.git>. It supports both
>> stateful and single-call decoding using the LZMA2 algorithm.
>>
>Is this something the linux-embedded community must pick up, or maybe
>even the LKML?

This is certainly the way to go, yes.

Re: XZ (LZMA2) decoder

[Lasse Collin]

On 2009-03-25 Leon Woestenberg wrote:
> Is this something the linux-embedded community must pick up, or maybe
> even the LKML?

In December, there was some discussion on linux-embedded about getting 
LZMA decoder into Linux. I understood that some of the existing patches 
had trouble meeting the kernel quality standards. There were also 
requirements like support for multi-call decoding, which should be 
useful at least in Squashfs. I promised to write a nice-looking .xz file 
format decoder for Linux (.xz will replace the .lzma format) and post to 
linux-embedded when I have something to show.

Assuming there still is interest like there was in December, hope I will 
get some feedback to know if my code looks promising and possibly how it 
should be improved to be good for in-kernel use. This is my first Linux 
kernel related coding project, so there probably are things (other than 
plain bugs) that need to be fixed before the code can be considered for 
inclusion.

If linux-embedded is not the best list for this, I can post to LKML too. 
However, since I promised to post at least to linux-embedded, and the 
discussion on this list in December was very helpful for me to 
understand what is required from an in-kernel decompressor, starting a 
new discussion first on linux-embedded sounded obvious to me.

Stable userspace tools to handle .xz files are still not available. I 
simply haven't worked on them much in the past two months. I naturally 
hope to get the stable release out soon, but my ability work on these 
projects depends on a couple of other things in my life, so it's better 
I don't promise anything detailed. On the positive side, the latest XZ 
Utils beta should be quite good already.

-- 
Lasse Collin  |  IRC: Larhzu @ IRCnet & Freenode

Re: XZ (LZMA2) decoder

[Geert Uytterhoeven]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset="ks_c_5601-1987", Size: 2072 bytes --]

On Thu, 26 Mar 2009, Lasse Collin wrote:
> On 2009-03-25 Leon Woestenberg wrote:
> > Is this something the linux-embedded community must pick up, or maybe
> > even the LKML?
> 
> In December, there was some discussion on linux-embedded about getting 
> LZMA decoder into Linux. I understood that some of the existing patches 
> had trouble meeting the kernel quality standards. There were also 
> requirements like support for multi-call decoding, which should be 
> useful at least in Squashfs. I promised to write a nice-looking .xz file 
> format decoder for Linux (.xz will replace the .lzma format) and post to 
> linux-embedded when I have something to show.

Yes, this is interesting work!

> Assuming there still is interest like there was in December, hope I will 
> get some feedback to know if my code looks promising and possibly how it 
> should be improved to be good for in-kernel use. This is my first Linux 
> kernel related coding project, so there probably are things (other than 
> plain bugs) that need to be fixed before the code can be considered for 
> inclusion.

I gave it a quick test on ppc64, and the kernel part built fine with sparse
checking enabled (make C=1), without any warnings.

> If linux-embedded is not the best list for this, I can post to LKML too. 
> However, since I promised to post at least to linux-embedded, and the 
> discussion on this list in December was very helpful for me to 
> understand what is required from an in-kernel decompressor, starting a 
> new discussion first on linux-embedded sounded obvious to me.

Ccing lkml wouldn't hurt, I think.

With kind regards,

Geert Uytterhoeven
Software Architect

Sony Techsoft Centre Europe
The Corporate Village · Da Vincilaan 7-D1 · B-1935 Zaventem · Belgium

Phone:    +32 (0)2 700 8453
Fax:      +32 (0)2 700 8622
E-mail:   Geert.Uytterhoeven@sonycom.com
Internet: http://www.sony-europe.com/

A division of Sony Europe (Belgium) N.V.
VAT BE 0413.825.160 · RPR Brussels
Fortis · BIC GEBABEBB · IBAN BE41293037680010