rob@modus.sublink.ORG (Roberto O. Buratti) (04/05/90)
In article <754@dksoft.incom.de>, dirk@dksoft.incom.de (Dirk Koeppen) writes: > I'am looking for a compression/decompression algorithm which > needs only a very small RAM space for the decompression. > > The decompressor get's into a ROM, the compressor is host-based > and is not limited in TEXT/DATA space. The packages to be compressed > are always 2 K Byte large. > > I've tried LZW and it looks good but perhaps there is any other > algorithm or 'C' based routines available. > I have written a simple compressor/decompressor based on the LZW algorithm. The "C" program sqz.c implements a modified version of the Lempel-Ziv-Welch algorythm with fixed codeword length (12 binits) - and also a fixed hash size - where unused codes are slowly forgotten while the compression proceeds. This way I can maintain an hash table with large redundancy, thus greatly increasing the speed. Here is the very simple code dictionary structure: #define NCODES 4096 /* 2 ^ 12 */ #define HASHSIZ 8191 /* 50% occupancy */ long tab[HASHSIZ + 1]; /* (w << 8) | k */ short cod[HASHSIZ]; /* map indices into codes */ short idx[NCODES]; /* map codes into indices */ short cnt[NCODES]; /* usage counter */ As You can see this data type occupies less than 64 Kbytes! The program in itself is a little bit slower than the original LZW, but on many compilers You can take advantage of its unexpensive memory requirements to generate a very faster code. For example I compiled this program on a HP9000/540 running HP-UX and the resulting object was about 2 times faster than compress(LZW) with at least 85% compress's efficiency! I am actually porting it under HP-UX on an HP9000/800 series computer and under SCO-UNIX System V 3.2. If You are interested in the source code, please contact me by e-mail. If I receive a large number of requests I'll post the source code as free-software over the network. bye ROB -- MODUS srl Via Aleardo Aleardi, 12 - 20154 Milano (Italy) PHONE : +39 2 3315328 FAX: +39 2 3315778 E-MAIL: rob@modus.sublink.ORG --- Software & Services for Advertising & Marketing --------------------------