[Lzip-bug] reducing memory usage when decompressing

[John Reiser]

Hi Antonio,

Sometimes I am willing to use large amounts of memory in order to generate
the smallest possible compressed output, but always I seek small
memory requirements for decompressing.  For instance, compressing with
"-s29" occasionally saves a few more kilobytes, but some of the recipients
cannot decompress those smaller .lz files because their machines lack the
memory and/or paging space.  The tighter compression is not usable
because decompression takes too much space.  It is particularly difficult
to decompress .lz on an embedded machine where resources are much more
limited than on the usual desktop boxes.  Although lzip's tighter compression
would be good for saving space in ROM or on flash memory devices or
download streams, it fails decompression because of small RAM.

When decompressing a compressed file, it seems to me that there is no benefit
to having a decompression buffer that is larger than the original file,
because any match distance (for copying) must be less.  The decompressor
could save space by allocating only
   min((1<<dictionary_bits), uncompressed_size)
bytes for the buffer.  It is somewhat unfortunate that the uncompressed size
appears not in the header of the compressed data, but only in the trailer.
Thus the uncompressed size is available [by seek+read+decode] only when
the input to decompression is a file, and is not available [when needed
at the beginning of decompression] if the input to decompression is
a stream [pipe].

The usage model of limiting the size of the decompression buffer, but
still allowing the compressor to achieve tight compression by using
larger arrays for the probability model, longer than
   (1 << ceil(log2(uncompressed_size))) ,
is also attractive.  However, lzip has coupled together the buffer size
and the model size during compression.

What are your thoughts about reducing memory usage when decompressing,
and allowing a model size that is independent of buffer size?

-- 
John Reiser