Decompression algorithms in AVR?

Go To Last Post
12 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

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?

- Jani

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Without knowing the exact shape of your data you're going to find it difficult to specify a compression scheme, and one problem you're likely to have is that compression ratio will not be constant with different data sets.

Unless your data is always going to be the same... in which case once you find something that works, you'll be ok forever.

I agree that RLE is probably not a good way to do it; I think you'll need one of the token schemes that stores the most commone tokens in fewer bits.

1 - analyse your entire dataset as a histogram
2 - sort the byte values into decending frequency
3 - build a reference table (it only needs to be 256 bytes) that maps the frequency to position
4 - assign unique byte patterns in sequence - Elias gamma patterns http://en.wikipedia.org/wiki/Elias_delta_coding look good
5 - select the patterns as required to combine into a bitstream, and chop those into eight-bit bytes to store

Note however, that this kind of entropy encoding is only going to work if there are a significant number of repeated symbols. I suspect you're going to have to experiment.

Neil

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Huffman may be the way to go, since decompression is much simplier than compression an needs less memory/resources. Anyway, this depends strongly on what are you de/compressing.

I had made an algo for this 10 years ago (written in pascal) thad had pretty good compression ratio for text files, but was not tested for exe files.

I also strongly recommend you to experiment, as barnacle had perfectly suggested. In fact hoffman coding is similar in structure, but the bit patterns are automatically assigned: two bits for the most occurrent byte, and more for the rest.

Guillem.

Guillem.
"Common sense is the least common of the senses" Anonymous.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yup, I'd recommend a static analysis Huffman encoding too. As the opcodes of the target CPU are fixed and the ratio in which they are used is probably going to be the same over a block of code as large as 0.5MB then you should get good compression (maybe 5:1 at a rough guess) after having done the probability analysis of the "alphabet"

One thing you won't be able to do is any of the forms of dictionary compression (Lempel Ziv etc.) as they are all RAM hungry for decompression as dynamic trees / tables must be built in RAM but this is the benfit of a static Huffman - you can keep the code table in const memory (so code flash in the case of an AVR)

To do a static Huffman you want to get as much example binary for the target CPU as you can find then for each of the potential bytes 0x00 to 0xFF you use a PC based program to count how frequently each occurs. The one that occurs the most often is assigned the shortest bit code and so on after you have built the "probability tree". The code then just recursively cruises this outputting 0's and 1's at each node so that the least likely symbols are assigned the longest bit codes.

Cliff

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Maybe, if the data field contain some numbers as strings, you can compress it to binary or float representation.

Or if the numbers change only a little, you can store the difference.

Peter

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Currently the firmware for the other MCU is around 480kb, and because of HW limitations, it cannot grow over around 500kb, so basically if I store a Intel Hex file in some kind of binary form instead of textual form, there will be more than enough memory for the 2kb of other data, all uncompressed. So the code and other data is binary and non-contiguous, so it needs to be split into blocks of contiguous data perhaps, which will of course take some header space.

And the Intel Hex has 16 bytes per row, so I will store more bytes or the full contiguous block per my binary record.

I just need to have a backup plan for compression, if for some reasons, it will be possible for the firmware code to grow up to 512kb instead of 500kb.

I have also experimented with Huffman compression some years ago, actually I first read about it from PC Game Programming Encyclopedia article here.
Back then I got the compression part sort of working, analysing the relative occurences and building the code table from that, but I lost interest as the decompression part decompressed more bytes than was stored (because of decompressor worked with full bytes so unused bits in the last byte were also decompressed).

Good thing here is that I can do the compression on a PC, and just store the compressed data into the memory, and let AVR decompress it when necessary. There is no possibility the AVR could do the compression, as with Huffman it needs the whole data before the propability table can be computed. Some other compression scheme might enable the AVR to do the compression on the fly.

- Jani

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Jepael wrote:
as with Huffman it needs the whole data before the propability table can be computed.

That's only true if you are doing dynamic Huffman. If you do static Huffman (on the basis that the code images are always going to be the same "kind" of data) then you only ever need to do the analysis once then keep a fixed symbol table and in future compression is simply a matter of "look up symbol, output code" while decompression is "isolate code, look up, output smbol".

A classic example of static Huffman is the T.4 compression used for fax machines. Back in the mists of time a whole pile of black and white text documents were analysed for black/white run length probabilities and a fixed code table was generated and now that same table is used in all fax machines across the globe and is printed in the "red book" that defines T.4. A fax machine doesn't need to analyse a complete page before deciding to encode it, it can start on pixel line 1 and happily use that same table for all the docuument without needing to first see it all

Same goes for your code, if you can analyse a few megabytes of such code then it's like that initial stack of documents they used for T.4. From then on you can start outputting compressed code images using the fixed analysis without needing to see the whole code image first. In fact the AVR code do it at the last minute as bytes arrive at the UART (or whatever), before it stored to DataFlash

Cliff

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, static Huffman sounds intriguing, I can just analyze a few binaries now, and use that table in the future. Actually I already did some "frequency" analysis over the full 512kb binary image, and the top three of values were 0xff, 0x00, and 0x01, in that order, containing some 5-8% of whole image. 0xff because that's what unused locations are. So using this, the AVR can compress the image as data is sent to it.

But I could also use dynamic Huffman (in the sense that every firmware image has own table), as I can propably do the compressed image on a PC, so extra 256 byte Huffman table is really nothing.

So all that remains now is to write some routines that reads the memory in bit level instead of byte level? Or how working with arbitrary length Huffman bit strings would be most efficient/fast/compact? This is something I have not found yet.

- Jani

BTW, is there a common notation for the Huffman bit stream, i.e. is the most frequent byte represented as a "1" or "0", and if the "1" is used for the most frequent, is the second most frequent byte represented then as "00" or "01"? Just thinking that maybe I could use some existing Huffman code to verify my own routines, or perhaps use some library directly.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Nope you can't do dynamic Huffman because if it's dynamic (changes with each code image) then the AVR would need to hold the table in RAM during the decompression process and unless it's one of the real big AVRs there won't be room. The advanatge of static is that fixed code table can remain fixed IN CODE FLASH, you access it with LPM, virtually no RAM is consumed and you hopefully have plenty of code flash space to hold the table.

You should be able to find "standard" algorithms on the PC for doing all this stuff, Whether 01 is chosen as the most frequent code and all other codes start with a 1 or 10 is used and all others start 0 is kind of immaterial as it should be an easy switch to make in any standard algorithm you find

Cliff

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

PS There seem to be a load of useful links and info (as is always the case with Wikipedia) at:

http://en.wikipedia.org/wiki/Huf...

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hey, this page is really cool:

http://www.cs.sfu.ca/cs/CC/365/l...

I went to the box at the bottom, entered "Now is the time for all good men to come to the aid of the party" and set the Java app going - it gives you a really graphic display of exactly how the process works each time you click the mouse

Cliff

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Alright, thank you for the info and ideas. I'll have to do some more reading and experimenting, but as I stated, this is a backup plan to compress the stuff.

- Jani