I am making a project in which the AVR would have some kind of external memory (not yet decided), which should hold around 4MBits of data (512kbytes). I think I will use Atmel DataFlash chips, as they come in the range of 1-16 MBits.
However, I already have 4MBit DataFlash samples, and would like to experiment with them.
The problem is, that if the data I need to store (firmware and other data for another MCU) grows up to 512kbytes, I need to compress the data into the DataFlash. The compression ratio is not important, as long as there is space left for some headers to divide the memory into two portions, so even a small compression ratio will do.
What do you suggest, just get a bigger DataFlash like 8Mbits, or just compress the data into the 4Mbit DataFlash?
The compression can be done on a PC, but what kind of decompression routines will run on a smallish AVR, like something between Mega8 and Mega64? I'll propably have to settle for a Mega16 for a balance.
I know some about about different compression algorithms like RLE, Huffman, and Deflate (used in ZIP files), but RLE will propably be bad for binary software which does not have long runs of same values, Huffman would propably need my own kind of file format, and I have a feeling that decompressing ZIP files takes too much of code/data memory on an AVR (based on 7-Zip's C library requirements).
So what kind of standard data decompression algorithms would run on an AVR? Or what do you use?