name: Comp6a
author: David Spence
size: 1648
needs: RISC OS
descr.: Single file compression (Slow as written in BASIC)
-----------------------------------------------------------------------------
Comp6a is a single file compression/decompression program, just run it using
the command line:
Comp6a c|d <Infile> <Outfile>
It always give compressed files the filetype &5, which the filetype
information I have tells me is not used. So the command:
"set Alias$@RunType_005 <path?>.comp6a d %%0 D%%0"
would decompress any file double clicked on, prepending a D to the filename.
NOTE: Do not have the in and out file the same, you will simply loose the
origional file!
The algorithm is very simple, it creates a binary tree of bytes, by pairing
the two bytes used the least, then pairs the next two least used bytes,
creating a psudo-byte for each pair, with their compbined usage, and so on
until there is only one byte left. This makes a tree like structure, but
with 2 branches at every node. Then each byte can be found by traveling
from the node, going left or right at every node, which can be represented
as a binary 0 or 1, so a code for each byte is created. The file's
representantion is then changed to this one, and this compresses it. This
method must have a name and inventer but I don't know them, as I worked it
out for myself after reading an artical on binary trees.
I'd love to give you a line by line explanation, but the code is so badly
written it's not possible. I don't normally write code like that, but I
didn't believe it would fit in to 2K ARM Assembly, so wrote it in BASIC
but still was unsure about if it would fit in so wrote it in that form to
start. Now I hope to convert it to ARM assembly, to see if it fits, if I
have the time before next term.
The More directory contains the working versions of the program: COMP, was
the first version, COMP2 changed the algorithm for decompression, changing
the time taken for a 55K file from about half an hour to half a minutie on
my A5000. COMP3 made the algorithm for creating the codes slightly more
efficient while COMP4 completely cahanges it giving a large speed
improvement. COMP5 and COMP6 just change all the numeric variables to
single capital-letter named integers and have a few other improvements.
Finally Comp6a is COMP6, but takes commandline arguments.
I've tested it, but I don't take any resposiblity for loss of files due to
the use of this program.
David Spence
drs32@cam.ac.uk