diff options
| -rw-r--r-- | README.txt | 3 | ||||
| -rw-r--r-- | doc/interview.txt | 166 |
2 files changed, 169 insertions, 0 deletions
@@ -43,6 +43,9 @@ Included in both the source and binary distributions: - doc/fileformat.txt - documents how the ALF file format differs from ARC. +- doc/interview.txt - an email interview with Alfred, author of AlfCrunch + for the Atari 8-bit. + - doc/review.txt - a review of the original ALFCrunch, from an Atari magazine. diff --git a/doc/interview.txt b/doc/interview.txt new file mode 100644 index 0000000..e7d375e --- /dev/null +++ b/doc/interview.txt @@ -0,0 +1,166 @@ +An email interview with Alfred, author of AlfCrunch for the +Atari 8-bit. + +Date: Thu, 20 Nov 2025 12:35:25 -0500 +From: Alfred +To: B. Watson <urchlay@slackware.uk> +Subject: Re: UnAlf + +On 2025-11-20 12:37 a.m., B. Watson wrote: + +> 1. Was AlfCrunch public domain, shareware, or...? + +1. AlfCrunch was public domain, although I never did distribute the +source code, and as I recall nobody ever asked me for it. The programmer +at ICD, Mike Gustafson did the same as you. He disassembled the DZ and +added it to their SpartaDos X along with all the ARC routines so they +could handle almost anything. Bob Puff at CSS did the same, so he could +add it to his SuperUnArc. He phoned me one night to say his code was +faster than mine at decompressing an AlfCrunch file. We had a good laugh +about it. + +> 2. Do you have any old disks (or disk images), or paper +> notes, anything that you used or referred to while developing +> AlfCrunch? Source would be awesome (if you still have it and are +> willing to share it). Even just the original distribution disk would +> be good to have. + +2. I didn't distribute it on disk that I can recall, it was either the +two files posted on my bbs, or perhaps they were Arc'd, I just don't +recall now. Probably Arc'd because there was a doc file with it. + +I've attached the source code for LZ/DZ. This isn't the original which +was done with Mac/65, it's broken up to use the Six Forks assembler +which I had just started using for a bit around then. + +> 3. Why not ARC compatible compression? You said you ported a PC +> program you had the source to... was it just not a matter of having +> the source for ARC? Or did you decide to go for speed rather than +> compatibility? + +3. I didn't have any source code for ARC and I didn't know what the +various compression algorithms were. I vaguely knew about Huffman from +work as one of the big software programs used it, but I had no idea how +it was implemented. I read the LZW paper but I didn't really understand +it then. Everyone hated Walden's ARC because it was so slow and it was +bugged, but it was all there was. One day somewhere I ran across some +guy's implementation of LZW for the pc, and I thought to try porting it +because it had to be faster than ARC. It was in assembler, so I could +kind of understand it. I'd seen some of the ARC source but the C code +was just gibberish to me. It's why my version is so clunky because I was +doing like you, just porting each x86 instruction to its sort of 6502 +variant. I couldn't make changes to the code because I didn't understand +what it was doing back then. + + After I released the first version someone called me and said their +Arcviewer didn't work on .alf files, so I quick fixed the header to be +Arc compatible to the extent you could see what the files were, and +that's the 1.4 version. So if you run across a 1.2, it's the same except +for the header. I don't think hardly anyone saw 1.2 except for some +local people because I released 1.4 so fast. + +> 4. Did you ever work on AlfCrunch after the 1.4 release? You mention a +> couple of possibilities for the next version in your doc file. Did any +> of that ever materialize (even if unreleased)? + +4. I did some work on a LZ 2.0 but I guess I quit on it, I only have +some source for the LZ part. I must have thought 1.4 was good enough and +moved on to something else. + +> 5. Are you OK with me redistributing the decompression code from UnAlf +> under the WTFPL license? +> +> 6. Are you OK with me including your AtariAge handle in my unalf +> documentation (man page)? + +5 & 6. Sure you can distribute whatever you like and mention me in it. +It's not like there's many people around who would remember me, heh. + +LZW is fairly straightforward (now, lol) but it can be a bit hard to get +the idea from just reading code. The way it works is a single token is +output that represents a string, hopefully a really long one like: + +token = $122= "went to the store and bought" string associated with that +token. However I think tokens start as 9 bit values, so you actually +output 9 bits, not just the 8. + +So on the compress side, you start with a table of, I think, 8 bit +tokens, where the value is 0-$FF, which are every possible input value. +If were only doing say ASCII text, you could cut it down to maybe 100 +tokens, not sure how many non-printables there are like SOL etc. + +Anyway, you start reading in bytes of data. You check a byte against the +table and if you don't find it, you add the next token value which would +be $100 and save that byte to that token's entry. Now that can't happen +with the first token, because it has to be one of the starting 256 +bytes. If you find the token, then you remember it and continue by +reading the next character. Now you're checking the table to see if +there's a token for 1st+2nd, which there isn't. So you create a new +token, $100, and add the 2 byte string as its value, and you output the +token for the first byte. Now the third byte probably doesn't match the +first byte, so it'll be the same process. Since there's no string of +3rd+4th, you'll output the token for the third byte, and add a new token +that represents those two bytes. Now with a good matching data file, +like text, you'll probably see 1st+2nd again. So when it sees that first +byte value, it says ok, I have a token for that, so it keeps reading, +and it sees the second byte and it goes, I have a token for 1+2 too, so +then it reads the third byte and now it goes, ok, I don't have a token +for 1+2+3, so it outputs the token for 1+2 and creates a new token and +stores the string 1+2+3 as it's value. + So this process just goes on until you run out of data. With a good +match you'll get longer and longer runs of bytes that match earlier +strings, so you can get to the point where one token is the same as 40 +characters. That's why LZW is so good. However you run into trouble with +something like a GIF or JPG because they're all different, you don't get +runs of bytes. Especially not in JPG because it's already stripped out +all the runs, which is why JPG files are so small. + +The decompress is similar, it just works backwards. You start with the +same 256 byte table. You read the first token, and it matches, so you +output the value (the token is the character initially). Since it +matched, what you would normally do is take the string that you output +just before this and concatenate the first letter of this string to the +last output string and add it to the table as a new token value. Since +there is no previous string when you read the first byte, you do +nothing. So even if you didn't know what the starting table was, you +could rebuild it here, because all the initial tokens will be <$100 +because they didn't match anything longer in the beginning of the +compression, so eventually you will reconstruct the 256 entry table. You +short-circuit that part by starting with the known table. + +So starting with the second token, you end up creating a bunch of second +level entries, which are the initial table value+something. As long as +the next token is in the table, you just keep going outputting strings +and adding new tokens. Now what happens if you get a token that isn't in +the table. This where the math becomes magic, I don't really understand +the theory, but it works. You know it had to have just been created by +the compressor. So the string that this new token represents has to at +least start with the last token to which some new character was added. +So you take the last string output and concatenate it's first character +to itself. So if the last string was the value "ABCD" you create new +token in the table and add "ABCDA" as it's value, and you output the +string "ABCDA". And so on. + +Now you start with 9 bit tokens I think. At some point on the compress +side, and on the decompress, when you code to add a new token, it's +going to take more than 9 bits, you up the bitsize to 10, which also +changes the highest token value you can have, which I think is what the +MAXCDE value represents. Because of the limited memory, I think I send +the clear code at the end of filling a 12 bit table, and start over with +9. Fortunately on the Atari you don't have giant files, so it doesn't +reset too often. + + There are a couple of special tokens, Clear which when you see it you +clear the table, and the End token which tells you that it's the last +token of the data. + +A lot of the code in LZ/DZ is the bit twiddling to concatenate the +varying bitsize tokens in memory. I can't do that sort of math in my +head, so it's a lot brute force shifting bits left and right to align a +new token to the last one in memory. The other thing I didn't understand +is I don't think the code actually stores every full string, maybe it +does, but at the time I thought the guy was using some scheme whereby he +was only storing one character with each new token and it somehow was +chained to the previous string. + +That's about all I can tell you about it. |