Arduino: Lightweight compression algorithm to store data in EEPROM

Question

I want to store a large amount of data onto my Arduino with a ATmega168/ATmega328 microcontroller, but unfortunately there's only 256 KB / 512 KB of EEPROM storage.

My idea is to make use of an compression algorithm to strip down the size. But well, my knowledge on compression algorithms is quite low and my search for ready-to-use libraries failed.

So, is there a good way to optimize the storage size?

Dragonhead

256 KB of EEPROM? According to the Atmel page for ATmega168 it has 512 bytes of EEPROM (yes, bytes) and ATmega328 has 1024 bytes of EEPROM. Is it EEPROM external to the microcontroller? – Lindley

Answer 1

You might have a look at the LZO algorithm, which is designed to be lightweight. I don't know whether there are any implementations for the AVR system, but it might be something you could implement yourself.

You may be somewhat misinformed about the amount of storage available in EEPROM on your chip though; according to the datasheet I have the EEPROM sizes are:

ATmega48P: 256
ATmega88P: 512
ATmega168P: 512
ATmega256P: 1024

Note that those values are in bytes, not KB as you mention in your question. This is not, by any measure, a "shitload".

Wheresoever

LZO apparently needs 8 or 64 KB of memory during compression, which may be a problem on these processors – Vengeance

I guess it depends on what the application is; the question does not state whether the data will be compressed by the Arduino, or compressed by something else and decompressed by the Arduino. I had assumed the decompression case. – Wheresoever

thanks for your suggestion. Sorry, true sure, I mixed up the EEPROM sizes, Greg is right. In true as well actually I need just the decompression part. well I'll give it a try.. – Dragonhead

There is also minilzo, which consists of just one c file and a few includes. Might not fit in your application, but it will probably work in a lot of cases. – Dionedionis

Answer 2

AVRs only have a few kilobytes of EEPROM at the most, and very few have many more than 64K Flash (no standard Arduinos do).

If you are needing to store something and seldom modify, for instance an image, you could try using the Flash as there is much more space there to work with. For simple images, some crude RLE encoding would go a long way.

Compressing anything more random, for instance logged data, audio, etc, will take a tremendous amount of overhead for the AVR, you will have better luck getting a serial EEPROM chip to hold this data. Arduino's site has a page on interfacing with a 64K chip, which sounds . If you want more than that, look at interfacing with a SD card with SPI, for instance in this audio shield

Tangleberry

Answer 3

A NASA study here (Postscript)

A repost of 1989 article on LZW here

Keep it simple and perform analysis of the cost/payout of adding compression. This includes time and effort, complexity, resource usage, data compressibility, etc.

Congratulate

Answer 4

An algorithm something like LZSS would probably be a good choice for an embedded platform. They are simple algorithms, and don't need much memory.

LZS is one I'm familiar with. It uses a 2 kB dictionary for compression and decompression (the dictionary is the most recent 2 kB of the uncompressed data stream). (LZS was patented by HiFn, however as far as I can tell, all patents have expired.)

But I see that an ATmega328, used on recent Arduinos, only has 512 bytes to 2 kB SRAM, so maybe even LZS is too big for it. I'm sure you could use a variant with a smaller dictionary, but I'm not sure what compression ratios you'd achieve.

Cullin

Answer 5

You might also want to take a look at LZJB, being very short, simple, and lightweight.

Also, FastLZ might be worth a look. It gets better compression ratios than LZJB and has pretty minimal memory requirements for decompression:

Beaverboard

You put a colon at the end of your answer there. Did your answer get cut off? – Sulamith

Answer 6

The method described in the paper “Data Compression Algorithms for Energy-Constrained Devices in Delay Tolerant Networks” might run on an ATmega328.

Reference: C. Sadler and M. Martonosi, “Data Compression Algorithms for Energy-Constrained Devices in Delay Tolerant Networks,” Proceedings of the ACM Conference on Embedded Networked Sensor Systems (SenSys) 2006, November 2006. .pdf. S-LZW Source for MSPGCC: slzw.tar.gz. Updated 10 March 2007.

Solarize

Answer 7

If you just want to remove some repeating zero's or such, use Run-length encoding Repeating byte sequences will be stored as:

<mark><byte><count>

It's super-simple algorithm, which you can probably code yourself in few lines of code.

Corabelle

Answer 8

Is an external EEPROM (for example via I2C) not an option? Even if you use a compression algorithm the down side is that the size of data you may store in the internal EEPROM may not be determined in a simple way any more.. And of corse, if you really mean kBYTES, then consider a SDCard connected to the SPI... There are some light weighted open source FAT-compatible file systems in the net.

Everything

Answer 9

heatshrink is a data compression/decompression library for embedded/real-time systems based on LZSS. It says it can run in under 100 bytes of memory.

Apothecary