Pages: [1]   Go Down
Author Topic: LZ type compressor/decompressor article  (Read 2683 times)
0 Members and 1 Guest are viewing this topic.
Offline Offline
Newbie
*
Karma: 0
Posts: 7
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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..
Logged


Global Moderator
Netherlands
Online Online
Shannon Member
*****
Karma: 217
Posts: 13740
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Offline Offline
Newbie
*
Karma: 0
Posts: 7
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged


Global Moderator
Netherlands
Online Online
Shannon Member
*****
Karma: 217
Posts: 13740
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Offline Offline
Newbie
*
Karma: 0
Posts: 7
View Profile
WWW
 Bigger Bigger  Smaller Smaller  Reset Reset

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.
Logged


Global Moderator
Netherlands
Online Online
Shannon Member
*****
Karma: 217
Posts: 13740
In theory there is no difference between theory and practice, however in practice there are many...
View Profile
 Bigger Bigger  Smaller Smaller  Reset Reset

Quote
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






Logged

Rob Tillaart

Nederlandse sectie - http://arduino.cc/forum/index.php/board,77.0.html -
(Please do not PM for private consultancy)

Pages: [1]   Go Up
Jump to: