Looking for an algorithm for embedded application
rkjnsn
breakdown of what exactly I am looking for, after the ***)
Some background:
I have an embedded application I am developing, and I am looking for a
good data compression algorithm to use. I have some limitations and
requirements which I have to work with, and after a lot of searching I
was not able to find algorithm that worked quite the way I wanted it
to.
Basically, I have between about 90 and 512 kB (it varies) of data that
I need to compress. The data will be compressed ahead of time, and
stored in read only memory. On the target device I have very limited
RAM (less that the size of the ROM), and thus I can only load a few
pieces of this data at a time. Unfortunately, I do not know ahead of
time which pieces I will need when (user interaction).
My current solution is to compress the data as separate 4kB chunks so
that I can access and decompress each piece as needed. The problem
with this method (as you can probably imagine) is that it leads to the
effectiveness of the compression being greatly reduced. (Data which
would normally compress to 50% of its original size now only
compresses to 70%). As the ROM space is also limited (albeit not
quite as much as the RAM), and the user may also want other data
stored in it, I would like to compress the data as much as is
reasonably possible.
One thought I had is that since all of the compressed data will be
accessible at all times, and since many of the blocks will contain
similar data, it would make sense to have some sort of shared
dictionary. I have even found at least one algorithm that can accept
such a dictionary (basically, it treats it as virtual decompressed
data before the real data, which can then be referenced by specifying
an offset that is greater than the current amount of decompressed
data; in other words, it treats it as the initial state of the sliding
dictionary). With a certain test file, I was able to decrease the
compressed size by specifying a shared dictionary that contained a few
pieces of data that I knew were common in the data. Unfortunately, I
have not been able to find an algorithm that can generate such a
dictionary.
***
Long story short, I am looking for a compression algorithm that I can
use that will meet the following requirements:
1. Data can be decompressed in 4kB chunks in a random access fashion.
(So I can access the chunk that I need at any given time.)
2. Some correlation is made between the data in each chunk while still
maintaining random access capability. (For example, by using a shared
initial dictionary state).
3. Relatively straight forward decompression. (It will be running on a
12 MHz processor)
4. Low memory usage for decompression. Ideally it would only only
need the decompression buffer and a few variables during
decompression, but a little auxiliary memory is okay.
5. Compression will occur once on a PC, so it can be as memory/
processor hungry as it wants
I think that's it. I am open to any suggestions you may have.
Thank you,
Erik Jensen
glen herrmannsfeldt
> Some background:
> I have an embedded application I am developing, and I am looking for a
> good data compression algorithm to use. I have some limitations and
> requirements which I have to work with, and after a lot of searching I
> was not able to find algorithm that worked quite the way I wanted it
> to.
> Basically, I have between about 90 and 512 kB (it varies) of data that
> I need to compress. The data will be compressed ahead of time, and
> stored in read only memory. On the target device I have very limited
> RAM (less that the size of the ROM), and thus I can only load a few
> pieces of this data at a time. Unfortunately, I do not know ahead of
> time which pieces I will need when (user interaction).
I have wondered about exactly this problem before.
LZW is commonly used, or the somewhat similar algorithms from IBM,
but they are inconvenient in that decompression takes more RAM
space than compression.
It would be nice to have an LZW-like algorithm where the compression
was harder (likely on a fast machine) and might take more RAM,
but could be decompressed in small memory on a slower machine.
-- glen
sebastian
Well, for what it's worth, I have an open source compressor that could
be easily adapted to such an environment. The main drawbacks, though,
are that (1) it requires 20K of (fixed) working memory, (2) it only
uses the Huffman algorithm, so I'm not sure if the compression levels
would be acceptable, and (3) it requires a C++ compiler.
Bartosz Wójcik
--
Bartosz W�jcik | www.pelock.com
rkjnsn
> Well, for what it's worth, I have an open source compressor that could
> be easily adapted to such an environment. The main drawbacks, though,
> are that (1) it requires 20K of (fixed) working memory, (2) it only
> uses the Huffman algorithm, so I'm not sure if the compression levels
> would be acceptable, and (3) it requires a C++ compiler.
I only have about 160K total RAM, so 20K is quite substantial.
On Nov 24, 12:31 pm, Bartosz Wójcik <antis...@dont.use.it> wrote:
> quicklz.com
>
> --
> Bartosz Wójcik |www.pelock.com
Thank you for the link. Unfortunately, it looks the the primary goal
of this software is fast (and thus not terribly good) compression. My
goal is to compress the data as tightly as I can, and still have it be
decompressible in 4k chunks on limited hardware. My hope was that I
could find an algorithm that took advantage of similarities between
the chunks without sacrificing the ability to decompress a given chunk
on demand, hence my wondering if there was an algorithm that could
generate some sort of shared dictionary.
Thank you for all the replies so far,
Erik Jensen
Yann
I ended up designing an algorithm that was extremely dissymetric,
with ultra-small, ultra-fast, and near-zero memory requirement on the
decoder (embedded side),
while the encoder would perform a lot of computation to achieve
maximum compression.
And it worked well. I used it in a similar fashion, for read-only
objects,
which were in fact libraries of smaller programs or data interacting
with each other.
Each object within the library could be decoded one at a time, on
demand when needed.
Fast decompression means virtually no performance impact, while
nonetheless saving precious ROM space.
Unfortunately, i ended writing this code in assembler, and i don't
believe this language can be of any use today.
Anyway, ideas are re-usable, and writing something similar in C today
seems feasible, certainly less difficult than back in time in
assembler with poor IDE & testing environment ...
John Reiser
> accessible at all times, and since many of the blocks will contain
> similar data, it would make sense to have some sort of shared
> dictionary. I have even found at least one algorithm that can accept
> such a dictionary (basically, it treats it as virtual decompressed
> data before the real data, which can then be referenced by specifying
> an offset that is greater than the current amount of decompressed
> data; in other words, it treats it as the initial state of the sliding
> dictionary).
That property can be used by any algorithm that is based on LZ.
LZO seems to be a good fit for your other criteria: small fast code
for decompression, with zero space overhead.
For the dictionary: make a histogram of short substrings, sort by
payoff (number of occurrences times number of bits saved when compressed)
and put the highest-payoff substrings into the dictionary. For example,
if k is the length of the shortest substring that can be compressed
(usually 3==k or 2==k), then make a histogram of all the substrings
of lengths k, 1+k, 2+k, and 3+k. Of course there is some art to
placing those substrings into the dictionary, taking advantage of
substrings, overlapping, short strings nearer to the high-address end, etc.
The Linux kernel uses a similar technique to compress names of symbols
that are used for printing backtraces of the subroutine calling stack.
See the file scripts/kallsyms.c. For instance,
http://svn.opentom.org/opentom/trunk/linux-2.6/scripts/kallsyms.c
and in general start at http://kernel.org/
--
Mark Adler
> My hope was that I
> could find an algorithm that took advantage of similarities between
> the chunks without sacrificing the ability to decompress a given chunk
> on demand, hence my wondering if there was an algorithm that could
> generate some sort of shared dictionary.
Erik,
zlib and puff could be considered. puff is a very small memory
footprint decompressor, which could be modified to use a preset
dictionary. zlib can compress with a preset dictionary. So once you
have a good dictionary, you just compress and decompress in 4K chunks.
The dictionary can be any size up to 32K.
zlib will not help you construct the dictionary. All you need to do is
use some combination of your data as a dictionary. If your blocks have
significant commonality, a simple concatenation of sample blocks might
make a good dictionary. Or you can try something more sophisticated by
looking for common strings and building a dictionary out of those (with
the most common at the end).
Mark