Re: Compressing ProDOS File Type Table

[jjp@ecn.ab.ca ()]

Michael J. Mahon (mjmahon@aol.com) wrote:
: Mike Pfaiffer suggested:

: >Jonathyn Bet'nct wrote:
: > > I'm writing a program launcher in assembly language, and I want to
: > > have a table of all 136 defined ProDOS file types (found at
: > > http://www.geocities.com/jonrelay/software/a2info/abftypes.htm) as
: > > part of it.
: > >
: > > To keep the program small and simple, I want to compress the table
: > > like BASIC.SYSTEM compresses its keywords (or at least how I _think_
: > > it does). For example, I can take the types AWP, WPF, PFS, FST, STN,
: > > TNJ, JAP, PTX, TXT, and TOL (totaling 30 bytes) and compress it into
: > > AWPFSTNJAPTXTOL (which is only 15 bytes).
: > >
: > > Doing this by hand, the shortest string I came up with was 277 bytes
: > > long. I want one that's 256 bytes or less (so I can fit it in a
: > > single page of memory).
: > >
: > > Here's my question: Is there a program out there that can compress
: > > strings this way into the shortest string possible so I don't have
: > > to?
: > >
: >	There is something else you can do. If you won't care about speed you 
: >could take the letters (normally 8 bits), disgard the MSB and compress 8 
: >bytes into 7.
: >
: >	You could also come up with a code describing the 26 letters A - Z and 
: >the numbers 0 - 9 and perform a similar compression. Looking at an ASCII 
: >table it could handle from 0 - 63 characters (with some left over) very 
: >nicely. This should compress down to about 25% of the size. You may want 
: >to consider taking the number of possible characters down to 0 - 47 and 
: >get a tighter compression but at 0 - 63 you get four characters per byte 
: >which should make uncompression easier.

: Actually, if you go to a 0-63 encoding (six bits per character) you will
: get a 25% saving in space (at some cost in code space to expand it.

: 64 is 25% of 256, but that just means that it uses two fewer bits.  ;-)

: The good news is that a 25% saving is more than enough for Jonathyn's
: purposes.

: -michael

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.

--

Jerry Penner	jjp (at) ecn.ab.ca