LZ type compressor/decompressor article

Arduino coders,

I've made a simple LZ-type compression system for Arduino that compresses text and data by a fairly respectable ratio - it typically saves ~40% on text or graphics. There's a Python command-line compression utility, and some sample code to decompress from flash. The original thread talking about compression is here:

http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1235582688

My writeup and code for the decompressor is at:

http://excamera.com/sphinx/article-compression.html

Let me know if you have any questions..

1 Like

Good job!

If I have say 30 strings of ~15 bytes = ~500bytes in my application, could I save memory by placing them compressed in (prog)memory?
More precisely formulated what is the compression ratio for relative short strings.

Do you also have written an Arduino compressor ?
so that it can compress sensor / log data before - writing to SDCARD , EEPROM, serial, or over an ethernet socket. 40% compression means less communication time.
Question is then how much time cost it to compress a typical string and is this less that the time gained by communication?

Think I just need some more numbers, can you provide?
tia,
rob

The compression ratio for short strings is always quite poor - LZ compressors need to build up a dictionary of prior data before they can start using backward references. One option is to compress all messages as a single block and then pick out the one you want during decompression.

I looked at compression systems that have fast compression. LZJB aims to do this, which is my it is used in filesystems, but its memory requirements of >64K are way beyond most embedded systems.

Sensor data is often best compressed using some ad-hoc scheme, e.g. only sending differential updates.

OK, you confirmed my expectations wrt compression by the arduino.

that said it still sounds interesting to use the decompressor when using the arduino as (web)server with large content blocks read from sdCard

Do you have any numbers about decompression performance #bytes per second? Or perhaps a complete test sketch?

Suppose serial communication of a 1000 bytes data
BAUD 115200 => uncompressed 104msec => compressed - ~40% = 62 msec savings 40 msec
BAUD 19200 => uncompressed 520msec => compressed - ~40% = 312 msec savings 200msec

if the decompress is faster than savings it would be great.

I'll work up a full example in the next day or two...

Right now I'm using it to decompress graphics data from flash to SPI RAM, and 14 Kbytes takes 600ms: about 23 Kbyte/s This is very unoptimized code, there should be at least a doubling possible.

about 23 Kbyte/s

OK, some cigarbox math:

my example: 1000 bytes data
BAUD 115200 => uncompressed 104msec => compressed - ~40% = 62 msec savings 40 msec
Decompress time (non optimized) for 1000 bytes @23KB/s => 44 msec
So at maximum baudrate there is approx a break even: 104 vs 106 msec
If decompressing can be doubled one would save 22msec for every 1000 bytes transmitted at 115200. (assuming large blocks)
saving 22 msec in 104 = ~ 20%

BAUD 19200 => uncompressed 520msec => compressed - ~40% = 312 msec savings 200msec
decompress time 44 msec so savings would be 160 msec vs 520 msec = 30%
saving 22 msec => 35%

(at trivial speed, indicative)
BAUD 9600 => uncompressed 1000 msec => compressed - 40% = 600 msec savings 400msec - 44 msec => 36% 22 msec => 38%

So in theory the use of decompress for large blocks on serial communication can increase throughput 20-35% - assuming you can double the speed

interesting,
thanx,
Rob