Compression for small-memory devices

Hi!

I'm trying to solve a compression problem for an embedded microcontroller application. I have an Atmel AVR, which has 16kB of Flash, but only one kB of RAM.

The microcontroller only needs to decompress the stream from Flash memory, the compression is done on a normal PC.

The data is highly redundant, so a LZ coding scheme seems optimal.

The problem is, that all the LZ algorithms I saw need some RAM space to hold a sliding window on the decoder side -- LZ codes the offset/length pairs in respect to the decoded stream. The repeating blocks of my data are relatively large (~300 bytes), so I'd need a window of this size, which I don't want to spend.

Is there some LZ variant, that doesn't need a sliding window? I could imagine an algorithm that codes offset/length pairs for repetitions as adresses of the compressed data. (i.e. "hey, here comes a part you already decompressed. just decompress X bytes again, reading from address Y."). The decompressor would then need to recurse into the decompression step, instead of just copying from the sliding window.

I don't have the memory to decompress the whole data, and don't want to use a big window of decompressed data. I _can_ spend a few 100 bytes for a call stack, and I have random access to the compressed data in flash.

Has this been done already? Or is there something I overlooked?

--
"Zuse, Zuse" sprach die Tante, als das Rechenzimmer brannte.
.

Relevant Pages

  • Re: Terse for PC
    ... I have not tried to decompress a file created using terse on PC. ... The appropriate function (compression | ... | you must follow to successfully exchange compressed files with the host. ...
    (bit.listserv.ibm-main)
  • Re: [PATCH] init: bzip2 or lzma -compressed kernels and initrds
    ... Compression is slowest. ... The kernel size is about 33 per cent smaller with lzma, ... I guess this is done on the internal hard disk of the laptop (this is ... disk, decompress, write to disk. ...
    (Linux-Kernel)
  • Re: zlib and zip files
    ... I need to decompress zip archive. ... The zlib module is for reading and writing the gzip compression format, used by the gzip program; it is not the same as a zip archive a la PKZip. ... The zipfile module will let you read and write zip archives. ... The gzip compressor and decompressor can work on the fly, but the format that it produces is a bit other than the format of compressed data zipfile. ...
    (comp.lang.python)
  • Is this a valid LZO compressed byte string?
    ... whenever I try to LZO decompress any of these bytestrings. ... bytestring from a data file or if the bytestrings are truly corrupted. ... decompression as was used for compression. ...
    (comp.compression)
  • Re: copyng large compressed files
    ... buffer. ... transparent compression. ... To read a file you need to decompress it. ... overhead of decompress. ...
    (comp.lang.java.advocacy)