Date   : Wed, 23 Aug 2006 19:47:06
From   : Philip Pemberton <philpem@...>
Subject: Re: Hard disk backup - another challenge

(one of these days I'll get used to hitting Reply All instead of Reply -
sorry, Sprow!)

Sprow wrote:
 > Just a crude run length encoding is required, can't be more than a couple
of
 > lines of code.
 > Reserve a byte as a token eg. FF. Output the token plus the repeated byte
 > plus the number of repeats (maybe a 2 byte field?). Escape the token with
 > itself to send just the token.

Why not use Packbits?

You have a header byte "n", which is a signed 8-bit byte. If it's between zero
and 127, you copy the next 1+n bytes verbatim into the output stream. If it's
between -127 and 1, you copy the next byte into the output stream 1-N times.
The value -128 is ignored.

There's a bit of information on Wikipedia about Packbits:
   <http://en.wikipedia.org/wiki/PackBits>

And some more information (including some example streams to test your
encoder/decoder routines) on Apple's TechNotes site:
   <http://developer.apple.com/technotes/tn/tn1023.html>

It's a lot more efficient than normal RLE - in RLE, if you have to encode a
group of (say) ten different bytes, you prefix all ten of them with a 0x01
byte (which means "a one byte long run follows"). That ends up doubling the
size of the run. With Packbits, you encode that as a single -9 byte, followed
by the ten bytes of data, which means you're only adding another byte to the
data. Only a ten percent increase, versus 100% for RLE.


--
Phil.                         | Kitsune: Acorn RiscPC SA202 64M+6G ViewFinder
philpem@...                   | Cheetah: Athlon64 3200+ A8VDeluxeV2 512M+100G
http://www.philpem.me.uk/     | Tiger: Toshiba SatPro4600 Celeron700 256M+40G