Re: Compressing ProDOS File Type Table

[Mike Guidero <mike@bogus.net>]

jjp@ecn.ab.ca wrote:
> Really, since all the file types are uppercase strings, you only need 5
> bits per character to hold all the letters.  You could do what Wozniak did
> in the monitor's disassembler, and encode the three letters into two
> bytes:
> aaaaabbb bbccccc0
> aaaaa = first letter
> bbbbb = second letter
> ccccc = third letter
> 
> If there is a need for numbers in there too, you are out of luck, unless
> you have no need for all 10 digits.  Five bits gives you 32 values, and
> you could have 26 letters plus 6 digits.
> 
> It's a simple matter to shift the bits out and add the offset back to get
> ASCII letters.

Actually, looking at the table that he intends to encode from, almost all of 
the digits are in the last position... only a few have a digit in positions 
a or b, and in position a, it's either a 3 or an 8, and in position b it's 
always a 1 if it's a digit.

I'd do it like this:

aaaaabbb bbcccccc
aaaaa = first letter or 3 or 8 (could encode 3-8 with remaining 6 values)
bbbbb = first letter or 1 (could encode 0-5 with remaining 6 values)
cccccc = last letter/digit (can encode all digits with extra values)

You get full coding, and you don't waste any bits.

This is about as compact as it can get.  Additional savings, however, might 
be obtained by doing:

aaaaaabb bbbbcccc ccdddddd ...

Where each field represents a letter or digit (and can encode all of the 
uppercase set plus digits), and also use the original idea of 
running-together types like this:

ptx, txt, tdm -> batxtdm

and also using a lookup table to find the correct starting position.

I think the lookup table would probably undo any space savings, though.

With my first method, above you get 256 3-char entries in the type table 
(including ??? for unknown ones, use extra cccccc codes to flag it), and it 
just takes 512 bytes.  that's a 33% savings.  If you were to get another 
33% of that by including the second technique I mentioned, and then have to 
add a 300-400 byte lookup table, you didn't save any space.

Mike