Date   : Mon, 18 Sep 2006 22:04:53 +0100
From   : Sprow <info@...>
Subject: Re: Compressed ROMFS?

In article <20060918170254.48466.qmail@...>,
   Greg Cook <debounce@...> wrote:

[Huffman]

> > > > For tokenised BASIC you can save 21%
> > > > For 6502 binaries you can save 10%
> > >
> > > Bitmapped data [...] compressed by 61%.
> > >
> > > Lastly I wrote an RLE compressor using the madness proposed in
> > > <4e5b03df85info@...> and that gave
> > >   For 6502 binaries you can save just 1%
> > >   For tokenised BASIC you save -2% (ie.bigger!)
> > >   For bitmap images with high black content 41%
>
> http://homepages.tesco.net/~rainstorm/logohist.gif
>
> "'At's more like it!"

So it's mostly spaces then!
It took over 15 minutes to analyse on the beeb (even after finishing
grinding the floppy heads), thank goodness for ARM coprocessors!

[snip]

> Nice to see interest in compression Beeb-style, 25 years on :-) 
> Regarding RAM, if there may not be SWRAM available the ROM could
> reserve absolute space for itself and not clobber the user's memory. 
> As I understand it though, if it doesn't need much RAM it could just
> use &C0 to &CF to save state between calls.

For Huffman (since the decode table is in ROM) you'd just need one
additional byte of storage somewhere to remember which bit position you were
at within the byte (the MOS already sets aside two bytes to store the byte
offset). 

I estimated the decode table would be about 720 bytes of ROM, assuming that
you could never need more than 256 branches for a 256 character table, with
each table entry needing a left and right branch. But then you've run out of
bits to store when you'd hit a leaf, so I rounded up from 512. Thinking
about it more, the table could itself be compressed since typically branch
numbers don't vary too much and might only need (say) a 4 bit offset from
the other branch. 
With a handful more bytes of RAM the compressed table could be interpretted
on the fly I guess to save gobbling 720 bytes of RAM.

For RLE, again 1 byte, to remember whether you're currently in an expansion
or not.

Both decode algorithms are left as an exercise for the reader,
Sprow.