💾 Archived View for mirrors.apple2.org.za › archive › apple.cabi.net › Graphics › GIFFYSAVE.SHK.TXT captured on 2024-02-05 at 11:30:03.
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
This is a routine I wrote quite some time ago but never got around to
releasing it to the public. The project initially was to simply create a
public-domain 65816-based assembly code for LZW compression/decompression, but
it quickly expanded to trying to optimize the algorithm and implement it into
something slightly useful. I don't know if I've accomplished either of these,
but here's my attempt. The algorithm is sorta explained below and the program
is simply a GIF saver that saves most any Super Hires image file as a GIF
image.
I could spend a few kilobytes of memory trying to explain what I've
done, but instead I'll just give a REAL brief overview of it and let it go from
there. If there is further interest, then I'd love to hear about it.
Especially if there is a better way of doing this. Right now, all I have ready
to release is the compression part of the project. The decompression is done
and works, but it has yet to be implemented into anything useful. Currently
it's just a GIF loader that only loads very specific formats. I'll try to get
something going with it fairly soon.
Now for the good part, the part where I attempt to explain what I've done.
At first I simply followed the standard LZW decompression algorithm found in
tons of documentation materials, but found it to be quite slow and inefficient.
This is the best I could come up with to get around this problem. At this
point, I'll assume you understand the concept behind LZW compression. If you
do not, then check with other documentation to get a basis on which to build.
Now with that out of the way, let's consider the standard string table.
It's a table listing strings of data that have occurred within the file being
compressed. Once a string has been added to the table, characters are again
read in from the source file and added to a current string until the current
string can not be found in the string table. This occurs when one character
has been added to the current string (which IS in the table) to create a string
that is not in the table. Using this fact, it's possible to represent any
string in the table as a code for a string in the table (a prefix) plus a
character.
This alone increases the speed of searching and significantly decreases the
size of the string table (since every string is now represented by two codes
regardless of the string's actual length). But searching still consists of
searching the entire list of strings to find the right combination of prefix
and character. The routine included with this file works on the concept of
only searching one prefix to see if that prefix has occured with the character
in question. If not, then another branch is added to that prefix and the
character is placed there. This greatly increases speed by allowing the
search routine to completely ignore any string that doesn't even begin with
the prefix in question.
That's basically it. I ain't the best person to try to explain something,
so my suggestion if you're interested in working with this is to simply follow
the source code and I'm sure you'll figure it out. Let me know if this source
code has helped in anyway. I'm not asking that any credit be given if this
routine is used in your own code, but I won't deny it if I am mentioned. Also,
the desktop shell that this program works with was written by Jonah Stich.
Thanks Jonah, saved me ALOT of time.