8051 data compression

Looking for lightweight data compression code for the 8051.  Preferably in 
C.  Can anyone offer links to pursue?  Speed is not all that important, code 
size is.


Thanks,

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
x@y
where
x = "martineu"
y = "pacbell.net"

Hi Martin,

What are you wanting to compress? We used a lookup table to compress
common html tags and sequences that repeated often. It's only really
suitable if the data does not contain all 256 possible values - you use
the spare values to index a lookup table.

Regards - Rocky

On Sat, 12 Nov 2005 16:54:21 GMT, "Martin" <0_0_0_0_@pacbell.net> wrote:

>Looking for lightweight data compression code for the 8051.  Preferably in 
>C.  Can anyone offer links to pursue?  Speed is not all that important, code 
>size is.

It's not possible to give a good answer without knowing what it is
that you are trying to compress. The solutions will differ for, say,
long strings of ASCII numeric characters versus image bitmaps versus
pseudo-random values. There are general purpose compression routines,
such as gzip, zip, arc, zoo (remember that one?) but general purpose
means a larger code size.

What about a lossy compression? For some applications, keeping only
"the important stuff" and discarding the rest is perfectly acceptable.

In addition to code size, how constrained are you with respect to
variable storage? Are you limited to 128 bytes in the register space
or do you have many KBs of external memory for table generation?

-- 
Rich Webb   Norfolk, VA

Rich Webb wrote:
> On Sat, 12 Nov 2005 16:54:21 GMT, "Martin" <0_0_0_0_@pacbell.net> wrote:
> 
> 
>>Looking for lightweight data compression code for the 8051.  Preferably in 
>>C.  Can anyone offer links to pursue?  Speed is not all that important, code 
>>size is.
> 

google for "zlib"   Its free, in C and _not_ fast.

Martin wrote:
> Looking for lightweight data compression code for the 8051.  Preferably in 
> C.  Can anyone offer links to pursue?  Speed is not all that important, code 
> size is.


  Run length encoding can be very compact & RAM frugal - some versions 
will fit into a CPLD. If you can tune, to match repeat patterns on your 
data, it can get even more efficent.
  All compressions are very data-content dependant, and truly random
data compresses the worst.
-jg

I should have been more precise.  Trying to consider compressing a Virtex II 
bitfile.  Storage would be in an external SPI FLASH device.  The 
uncompressed bit image is just under 512K-bytes.  In looking at it, there 
are lots of 0x00 bytes.  It should compress very well.

Lossy compression is not an option, obvisouly.

-Martin



"Martin" <0_0_0_0_@pacbell.net> wrote in message 
news:17pdf.26091$6e1.2999@newssvr14.news.prodigy.com...
> Looking for lightweight data compression code for the 8051.  Preferably in 
> C.  Can anyone offer links to pursue?  Speed is not all that important, 
> code size is.
>
>
> Thanks,
>
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> Martin Euredjian
>
> To send private email:
> x@y
> where
> x = "martineu"
> y = "pacbell.net"
>
>
> 

To add to that, obviously I only need to expand with the 8051.  The 
compression part would be done on a PC.

-Martin


"Martin" <0_0_0_0_@pacbell.net> wrote in message 
news:B6udf.17160$tV6.13013@newssvr27.news.prodigy.net...
>I should have been more precise.  Trying to consider compressing a Virtex 
>II bitfile.  Storage would be in an external SPI FLASH device.  The 
>uncompressed bit image is just under 512K-bytes.  In looking at it, there 
>are lots of 0x00 bytes.  It should compress very well.
>
> Lossy compression is not an option, obvisouly.
>
> -Martin
>
>
>
> "Martin" <0_0_0_0_@pacbell.net> wrote in message 
> news:17pdf.26091$6e1.2999@newssvr14.news.prodigy.com...
>> Looking for lightweight data compression code for the 8051.  Preferably 
>> in C.  Can anyone offer links to pursue?  Speed is not all that 
>> important, code size is.
>>
>>
>> Thanks,
>>
>> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>> Martin Euredjian
>>
>> To send private email:
>> x@y
>> where
>> x = "martineu"
>> y = "pacbell.net"
>>
>>
>>
>
> 

Martin wrote:

> To add to that, obviously I only need to expand with the 8051.  The 
> compression part would be done on a PC.

  Then the PC can search for the best RLC lengths, and you can even look
at adding a simple table, if the best pattern repeats are > 1 byte.
  Unused portions of the bitstream should compress very well.

  In the most vanilla form, RLC is Value.Count, but it can expand to
TableIndex.Count, expecially if a PC can do the leg-work, of checking
the table values, and patterns.
  ZIP the bitstream, and you have a target of what complex compression 
gives.
-jg

Jim Granville wrote:

>  Then the PC can search for the best RLC lengths, and you can even look
> at adding a simple table, if the best pattern repeats are > 1 byte.
>  Unused portions of the bitstream should compress very well.

I'm familiar with plain RLC.  I need to research the table approach.

>  ZIP the bitstream, and you have a target of what complex compression 
> gives.

I did do that.  500K compressed down to 100K~112K, depending on settings. I 
think that I can safely assume that allocating 250K of FLASH should do the 
job.  I need to allow for changes in code affecting compression.  That's the 
toughest aspect of this to guestimate.

I am going to post to comp.arch.fpga to see if anyone might have statistics 
on attainable compression ratios for different design densities.

Thanks,

-- 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Martin Euredjian

To send private email:
x@y
where
x  =  "martineu"
y = "pacbell.net"

On Sat, 12 Nov 2005 22:35:13 GMT, "Martin" <0_0_0_0_@pacbell.net> wrote:

>I should have been more precise.  Trying to consider compressing a Virtex II 
>bitfile.  Storage would be in an external SPI FLASH device.  The 
>uncompressed bit image is just under 512K-bytes.  In looking at it, there 
>are lots of 0x00 bytes.  It should compress very well.
>
>Lossy compression is not an option, obvisouly.

Then the easiest is probably good old run length encoding (google for
RLE). http://datacompression.info/RLE.shtml is probably the easiest
place to start; several links to pseudo-code there. Wikipedia also has
a short entry on it.

-- 
Rich Webb   Norfolk, VA