diff options
Diffstat (limited to 'README')
| -rw-r--r-- | README | 108 |
1 files changed, 108 insertions, 0 deletions
@@ -0,0 +1,108 @@ +Description + +Xlunzip is a test tool for the lzip decompression code of my lzip patch for +linux. Xlunzip is similar to lunzip, but it uses the lzip_decompress linux +module as a backend. Xlunzip tests the module for stream, buffer-to-buffer, +and mixed decompression modes, including in-place decompression (using the +same buffer for input and output). You can use xlunzip to verify that the +module produces correct results when decompressing single member files, +multimember files, or the concatenation of two or more compressed files. +Xlunzip can be used with unzcrash to test the robustness of the module to +the decompression of corrupted data. + +The distributed index feature of the lzip format allows xlunzip to +decompress concatenated files in place. This can't be guaranteed to work +with formats like gzip or bzip2 because they can't detect whether a high +compression ratio in the first members of the multimember data is being +masked by a low compression ratio in the last members. + +The xlunzip tarball contains a copy of the lzip_decompress module and can be +compiled and tested without downloading or applying the patch to the kernel. + +My lzip patch for linux can be found at +http://download.savannah.gnu.org/releases/lzip/kernel/ + +Lzip related components in the kernel +===================================== + +The lzip_decompress module in lib/lzip_decompress.c provides a versatile +lzip decompression function able to do buffer to buffer decompression or +stream decompression with fill and flush callback functions. The usage of +the function is documented in include/linux/lzip.h. + +For decompressing the kernel image, initramfs, and initrd, there is a +wrapper function in lib/decompress_lunzip.c providing the same common +interface as the other decompress_*.c files, which is defined in +include/linux/decompress/generic.h. + +Analysis of the in-place decompression +====================================== + +In order to decompress the kernel in place (using the same buffer for input +and output), the compressed data is placed at the end of the buffer used to +hold the decompressed data. The buffer must be large enough to contain after +the decompressed data extra space for a marker, a trailer, the maximum +possible data expansion, and (if the compressed data consists of more than +one member) N-1 empty members. + + |------ compressed data ------| + V V +|----------------|-------------------|---------| +^ ^ extra +|-------- decompressed data ---------| + +The input pointer initially points to the beginning of the compressed data +and the output pointer initially points to the beginning of the buffer. +Decompressing compressible data reduces the distance between the pointers, +while decompressing uncompressible data increases the distance. The extra +space must be large enough that the output pointer does not overrun the +input pointer even if all the overlap between compressed and decompressed +data is uncompressible. The worst case is very compressible data followed by +uncompressible data because in this case the output pointer increases faster +when the input pointer is smaller. + + | * <-- input pointer (*) + | * , <-- output pointer (,) + | * , ' + | x ' <-- overrun (x) +memory | * ,' +address | * ,' + |* ,' + | ,' + | ,' + |,' + '-------------------------- + time + +All we need to know to calculate the minimum required extra space is: + The maximum expansion ratio. + The size of the last part of a member required to verify integrity. + For multimember data, the overhead per member. (36 bytes for lzip). + +The maximum expansion ratio of LZMA data is of about 1.4%. Rounding this up +to 1/64 (1.5625%) and adding 36 bytes per input member, the extra space +required to decompress lzip data in place is: + + extra_bytes = ( compressed_size >> 6 ) + members * 36 + +Using the compressed size to calculate the extra_bytes (as in the formula +above) may slightly overestimate the amount of space required in the worst +case. But calculating the extra_bytes from the uncompressed size (as does +linux currently) is wrong (and inefficient for high compression ratios). The +formula used in arch/x86/boot/header.S + + extra_bytes = ( uncompressed_size >> 8 ) + 65536 + +fails to decompress 1 MB of zeros followed by 8 MB of random data, wastes +memory for compression ratios larger than 4:1, and does not even consider +multimember data. + + +Copyright (C) 2016-2021 Antonio Diaz Diaz. + +This file is free documentation: you have unlimited permission to copy, +distribute, and modify it. + +The file Makefile.in is a data file used by configure to produce the +Makefile. It has the same copyright owner and permissions that configure +itself. |