Adding upstream version 0.7.upstream/0.7upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 108 insertions, 0 deletions

diff --git a/README b/README
new file mode 100644
index 0000000..7395a92
--- /dev/null
+++ b/README
@@ -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.