[A83] Compression update
[Prev][Next][Index][Thread]
[A83] Compression update
Just to let you folks know...
I've been spending the past day or so fiddling with LZSS compression on
my 83+. I managed to write a both a compressor and a decompressor which
did the job, with fairly good results. Equipped with the experience I
gained from that, I'm now re-writing the routines to be more efficient,
flexible, and elegent (I hate messy code :P)
The decompressor was the major worry. As someone pointed out, scanning
the LZSS buffers for matching data is a time consuming process. In the
end, however, compressing 1k of data with a 256-byte buffer only took
about 3-4 seconds. Not fast, but not unacceptably slow.
Compression ratios were fairly good. I tried a couple of 768 byte
images, which got compressed to 200-300 bytes, depending on the
complexity of the image.
Anyway, some of the features I am implementing in the 'proper' library
are:
1) user definable buffer sizes.
Both the sliding window and look-ahead buffer can be set to between
1 and 8 bits
2) optional callback procedure
Useful for displaying status. I might only implement this in the
compressor, since the decompressor is lightning (relatively speaking),
and the decompressor really needs to be a bare-bones, light-weight
utility (ie: for self-extracting programs).
3) 'buffer collision' detection and hopefully repair!
This is for people who want to be tricky. You could, for instance,
set the output pointer to say, 64 bytes behind the input pointer. This
would save lots of memory, but a problem will occur if the output
pointer 'catches up' to the input pointer. If this did occur,
compression/decompression will have to be aborted - however, some of the
original data will be destroyed unless I implement some kind of
'backtracking' (for want of a better word) routine to reverse the
compression/decompression already done.
4) dynamic buffer width
This one is a bit iffy. It would make feature 1 fairly redundant by
dynamically adapting the buffer width to the input. It would probably do
wonders for compression, but may bloat the library a bit.
5) any bugs I can get away with calling features :P
So there you have it! I shall keep you all posted.
Hmmm.... 3am. Time for.... what's that thing called again?.. dinner?..
no... oh that's it! SLEEP! Ahhh... it's been too long :P