Best decompression on embedded device

[ikes]

I'm relatively new to compression algorithms so my apologies in advance. I'm running on an older TI DSP (5402) and am running low on code space. We include a large image in our build that gets loaded to a daughter board and I want to compress that image pre-compiling. Then I'll include the decompressor in our code such that the image gets uncompressed as its loaded to the daughter board. So my considerations are:
1. I don't care how fast the compressor is because it will only be done once and on a fast PC (so the code wont be included on my DSP)
2. I need the decompressor as small as possible (obviously smaller than the amount it would save)
3. Open source
4. Decompression speed is not critical, but can't take forever either.

RLE will be huge win, but any additional savings would be great. I've checked source forge. Any suggestions on algorithms would be much appreciated!

Thanks,
Dan

[Bulat Ziganshin]

w/o numbers the question is meaningless

[encode]

I'm relatively new to compression algorithms so my apologies in advance. I'm running on an older TI DSP (5402) and am running low on code space. We include a large image in our build that gets loaded to a daughter board and I want to compress that image pre-compiling. Then I'll include the decompressor in our code such that the image gets uncompressed as its loaded to the daughter board. So my considerations are:
1. I don't care how fast the compressor is because it will only be done once and on a fast PC (so the code wont be included on my DSP)
2. I need the decompressor as small as possible (obviously smaller than the amount it would save)
3. Open source
4. Decompression speed is not critical, but can't take forever either.

RLE will be huge win, but any additional savings would be great. I've checked source forge. Any suggestions on algorithms would be much appreciated!

Thanks,
Dan

Check out BALZ:
http://balz.sourceforge.net/

[osmanturan]

Considering a DSP architecture, there is no any advantage of using LZ/CM/PPM algorithm "especially" for an image. Here is the link for the datasheet of that DSP chip: http://focus.ti.com/lit/ds/symlink/tms320uc5402.pdf

I didn't make a very deep looking of the datasheet but it's clear you should use some light-weight techniques. Because, this cheap has only 4K x 16-bits ROM and 16K x 16-bits RAM and it's computation power is 80 MIPS. So, some questions come to the scene:
1-Could you provide some sample images? Are they artificial drawings or photographs? What's their dimensions and pixel depth?
2-Are you using an extra chip as an auxiliary RAM? Or will you use?
3-What's your expectation from the compression (ratio)?

Two methods came into my mind for your purpose:
1-DCT based JPEG-like compression (of course lossless and much simpler). If your chip doesn't support DCT spectral analyzing, you can achieve same thing with taking symmetric of the input signal and then calculating FFT on over it.
2-A linear predictor (LPC).

If you could provide some extra info, we can help you.

[ikes]

The image I'm trying to compress is 8K. What other numbers do you need?

[ikes]

Thanks for the response. By image, I meant an executable image that gets loaded to the daughter board. Sorry. The image is 8K. About 50% of that will be compressed with RLE. So I'm then trying to squeeze an executable that is about 4K. I don't have a target compression ratio. Whatever I can squeeze out would be great, remembering that I need to factor in the size of the decompression code as well. Also, all of our code is in C/asm.

Thanks again!
Dan

[ikes]

Oh, and we do have plenty of space on an external RAM chip so no concerns there, but limited, if any space in internal RAM.

[osmanturan]

OK. Then you can prefer LZSS style decoder (it's too simple to decode). There are some discussions about it in this forum. Or ask Ilia (encode) for about LZSS (he has some experiments with it).