How to compress constant data table

[localcrack]

I am developing a one program in keil for Atmel chip AT89C2051. In this program I use constant data table to store constant value in ROM. My base code that will handles one 7 Segment display two switches for up and down and some port handling operation with constant data that will requires around 1 Kb of space. Now my question is that the constant data table space which I needs for this program will also increased to around 2.5 Kb so it will out of space for selected chip. I checked that my data table has lots of repetitive value (around 80% repetitive value) so I needs some technique to compress this data table to fit it on my selected chip. Please note that I do not want to change chip to increase the code space.

Keil supports RW data compression but I think this will works on only ARM controllers. Please see the link for more info.

http://www.keil.com/support/man/docs/armlink/armlink_chddibfi.htm

[titi]

Hi localcrack,

a simple way to compress data is the RLE (Run length encoding) algorithm.

Do a search with google for RLE it was used by PCX image format and some BMP.

Best regards.

[Magnox]

Hmm... RLE is probably the only standard compression method that can be considered really, given the code space limitations. The trick will be making the code smaller than the saving in data.

What format is the data? Is it any value in an 8-bit range, for instance, or only 4 bits, 6 bits, or only certain values within a larger range (like only 2,4,6,8 etc, or whatever)?

There might be other ways to compact the data, or a way to implement a modified form of RLE.

Is it possible to calculate any parts of the data, or is it not related simply to any input?

Another trade of will be speed of course. The more complex the algorithm, the slower your code will run.

[localcrack]

I tried RLE but compression ratio is very low because repeated bytes are not in sequence. Sometimes this algorithm adds two bytes instead of two. I checked my data that there are lot's of similar two byte togather eg. AA BB CC and there are few three bytes together eg. AAA BBB CCC and there are lot's of single repeated bytes between similar byte's pair eg. AA D BB D CC D FF D etc.

If I compress this types of data with RLE then compression ratio is very low or sometimes no compression is possible.

For example,

Uncompressed : AAA D BB C BB FFF E CC = 15 Bytes
Compressed :    3A 1D  2B 1C 2B 3F 1E 2C = 16 Bytes
                           ^        ^          ^
                       Here this algorithm adds two byte instead of one

Uncompressed : AAA D BB C BB FFF E CC = 15 Bytes
Compressed :    3A 1D  2B 1C 2B 3F 1E 2C = 16 Bytes
                       ^                    ^
                      Compression done reduced one byte

Uncompressed : AAA D BB C BB FFF E CC = 15 Bytes
Compressed :    3A 1D  2B 1C 2B 3F 1E 2C = 16 Bytes
                                ^                   ^
                      Compression not possible original and compressed byte count are same.

[Ichan]

Curious i am, googling found Heatsrhink with codes available on GitHub.

No time yet to play with it, let us know if you do..

-ichan

[bigtoy]

Heatshrink - nice find. Looks quite interesting for all kinds of things.