FMod - LZW Rage

After opening a gazillion tabs about file formats in my browser, I got to work this morning on the EGA graphics and LZW compression format. The first order of business was to get a quick mock-up of the header ready in the FromFiles method of the new VortGraphics class. With that ready, I put on my pay attention face and added a DecompressLZW method to my compression library.

It took me an hour just to get any idea of what LZW is even supposed to do. I found three different algorithms, two of which were psuedocode and one of which was in C. (I did later find a really messy un-object-oriented one in QuickBasic.) At first I was going to use an jagged array of bytes to manage the dictionary, but realized that would become terrible with the extended-bit entries and changed it to a dictionary of unsigned integer and byte array.

Since bit operations are truly awful in high-level languages, I created a list of booleans to store the each bit. Later, thinking that was a waste of memory, I created a bit getter lambda (which are the super inline functions I wanted) to find a single bit in the data stream. That failed due to weird side effects of the overloaded And operator. So, I created an inline iterator function to figure out the bits as I needed them. That failed because some buffering thing done automatically caused it to read more bytes and get out of sync. At the end of my fiddling with the data handling, it was back to the boolean bit list.

I ran into all kinds of problems with dictionary keys. First, it was crashing with KeyNotFoundException immediately after preemptively adding the value for that key. Then, after I did some value remembering stuff, it crashed with NullReferenceException in the outputter section. Tweaking the data reading loop to accommodate that just resulted in early exit.

The core algorithm has been rewritten at least four times. I have been working with Visual Studio, XVI32, and Keen on this the entire day. It is still not working.